# Introduction ireless Sensor Network [3,4] (WSN) consists of sensor nodes dispersed randomly over the area under consideration. These nodes communicate among each other by multi hop are single hop depending upon the energy of the nodes. The Base Station (BS) is a node which is powered externally does the job of data aggregation to the IoT channel or any other interpreting software as desired. The BS can also communicate the information to each node in the same way. Because of the harsh environmental condition these sensor nodes once deployed can have limited chances of battery replenishment. Hence gathering sensed data in an energy efficient manner is time critical for the sensor network over a long period of time [5]. Hence limiting the energy dissipation and stretching the network lifetime is one of the most important factors in WSN [4,5]. This paper focuses on cluster based data transmission schemes as it helps to prolong the network lifetime of WSNs. In this technique nodes are elected as CHs from a subset of nodes which are eligible to become CH on the basis of energy consideration and belong to connected dominating set as additional requirement. The remaining nodes act as non-CH to save its own energy, and transmits its data to the elected CH. CH performs data aggregation on the data received from its member nodes. This method of data transmission is energy efficient as the energy required for communication is high compared to the energy required for computation [6], [7]. The CH should be on rotational basis and so are the cluster members to avoid early death of CHs. This is required because many actions are performed by each elected CH, including cluster head announcement through hello packets, an announcement of data transmission schedule to the member nodes, reception of data from member nodes, data aggregation, and transmission of collected data to base station. Clustering algorithms are divided into two types as Distributed Clustering and Centralized Clustering. Distributed clustering method is again split into four sub types based on the cluster formation idea and parameters used for CH election as Identity based, Neighborhood information based, Probabilistic, and Iterative respectively. Linked Cluster Algorithm [8] belongs to Identity based clustering technique that takes unique node identifiers as primary key to select the cluster heads. In another improvement Linked Cluster Algorithm also helps to eliminate chances of multiple cluster head selection [8]. There are a good number of protocols devised using Neighborhood Information based approach. Highest Connectivity Cluster Algorithm (HCCA) [8], is based on choosing a sensor node as cluster head which has greatest number of neighbors at 1-hop distance with clock synchronization as an additional requirement. Max-Min D-Cluster Algorithm [9], selects cluster head in such a way that no neighbors are at d-hop distance away from it and thus giving better load balancing without any clock synchronization requirement. Weighted Clustering Algorithm (WCA) [10], functions on the basis of the principle of non-periodic initialization of itself only when topology reconfiguration has become unavoidable due to a particular node dissipating energy. This loss of energy leads to losing connectivity with its cluster head which in turn tries to balance the combination of several required parameters called 'combined weight'. Grid-clustering routing Protocol (GROUP) [11], uses multiple sinks among which one of them is considered as 'primary sink'. This being responsible for dynamically selecting cluster heads which forms a grid-like structure. Probabilistic Approaches for clustering in WSN relies upon a prior assigned probability values for sensor nodes. Low-Energy Adaptive Clustering Hierarchy (LEACH) protocol in [12] provides a rational use of energy by random rotation of cluster heads on the basis of energy. This process meanwhile assures uniform load balancing in one-hop sensor networks. Hybrid Energy Efficient Distributed Clustering (HEED) proposes a way in which the remaining energy of sensor nodes and intra-cluster data exchange costs in the competitive way of selecting the cluster heads in multi hop sensor networks [14,15]. Energy Efficient Clustering Scheme (EECS) proposes dynamic, and localized hierarchy based process for selection of cluster heads based on the basis of energy of sensor nodes providing lower message overhead and uniform distribution of cluster heads [14]. Two-Level LEACH (TL-LEACH) is proposed in [13], which is an extension to LEACH, proposing primary and secondary tier of cluster head selection to minimize energy utilization. Iterative clustering protocols that is be mentioned here are: DCA [16], SPAN [17], and ACE [18]. Distributed Clustering Algorithm (DCA) protocol uses time delayed notification technique for any sensor before selecting the cluster head and thus giving a chance for other hierarchical preference conditions neighbor sensor nodes to become the cluster heads. SPAN is a randomized cluster head selection process with spatial decision making process which is based on number of sensor nodes being benefited and its own energy levels for a sensor node that is likely to become cluster head. Algorithm for Cluster Establishment is one the sought protocol primarily used for energy saving, with two distinct phases of cluster head selection: a randomized new cluster 'spawning phase' and 'migration phase' for existing clusters to achieve highly uniform non-overlapping cluster formation. But iterative clustering suffers from too much dependency on neighbors and thus the network diameter. Our communication is divided into six sections the first section is the brief introduction to the connected dominating set algorithms and clustering process in sensor network, second section deals with the brief review of the protocols on which will be used to modify hierarchical protocol , the third section gives the list of assumptions and the theoretical framework of how the connected dominating set be integrated with LEACH , the fourth section deals with simulator specifics built on MATLAB , the fifth section deals with results and discussions on the data generated by the simulator, sixth section concludes the paper with conclusions and future work. II. Brief Review on the Protocols used LEACH: LEACH is one of the popular clustering routing protocols for wireless sensor networks (WSNs) to increase the lifespan of network. It is a self-organizing protocol that balances the energy load equally among all the sensors of the network. In LEACH, nodes elect cluster head (CH) and one node from that cluster acts as its CH. LEACH chooses high energy sensor node as CH but after a round has been performed, it rotates CH among all nodes of the network so that the energy of a single node is not drained completely. Thus LEACH reduces energy dissipation and increases network lifetime. For each round, sensors elect themselves as CH with certain probability determined by a function. The status of these CHs is broadcasted within the network with the help of Hello messages. Each sensor node selects its CH by choosing the one which requires minimum communication energy by evaluating the Euclidian distance between the nodes. Then the CH uses TDMA for the nodes to transmit data. In this way, nodes transmit data to the CH in their time slot and are in sleep condition for the rest of the time. So, the energy consumption of non-CH sensor node is minimized. When the CH receives all the data from non-CH sensor node within its cluster, it collects that data and sends it to BS. In this way, energy dissipation of the whole network is reduced. A CH uses more energy as compared to member nodes. To overcome this issue, LEACH has a fixed number of CH and a CH is selfelected at every round. For a node to become CH depends on energy of that node. So, node with higher remaining energy acts as CH for that round. Connected Dominating Set algorithm: This algorithm is especially attractive in ad hoc networking in the area of mobile communication and sensor networks. This algorithm actually is very easy to compute and has the complexity of O(n). For example, to connect a backbone nodes in ad hoc sensor networks to perform efficient routing and broadcasting. A Connected Dominating Set (CDS) can be used as a backbone. Backbones improves the routing procedure and reduces the communication overhead, decreases the overall energy consumption, increases the bandwidth efficiency, and, at last, increases network lifetime in a WSN. The nodes in CDS are called dominator (backbone node) other nodes are called dominatee (non-backbone node). This process is easy to adapt in case of WSN. Rai et al. [1] proposed an algorithm for finding Minimum Connected Dominating Set (MCDS) which are connected through Steiner tree. The approximation algorithm includes of three stages. ? The DS is determined through recognizing the maximum degree of those nodes to discover the highest cover nodes. Year 2020 ( ) ? The connectivity of the nodes in the DS is verified through a Steiner tree. ? At last, this tree prunes to form the MCDS. Xie et al. [3] called their algorithm as Connected Dominating Set-Hierarchical Graph (CDS-HG). It is a approximate distributed MCDS algorithm. The authors proved that this algorithm generates smaller CDS as compared with other existing algorithms. Their algorithm operates of two phases. ? At first, in the first phase, (Essential Node Determination) is used. According to this step, a set of dominators select for each level so that all nodes in the next upper level are dominated by these dominators. A greedy algorithm is used to select the dominators for creating a small initial DS. ? In the second phase, is used to remove the redundant dominators. This process repeated from the lowest level to the highest level of the graph. Thus the greedy strategy used in previous step provides the result as connected DS. III. # Assumptions and Theoritical Background Any protocol that guarantees certain properties has to make certain valid assumptions. However if the assumptions are explicit then it becomes the responsibility of the developer to satisfy the assumptions. These assumptions are mostly network latency and bandwidth, processing time, failures, and so on. So in the premise of LEACH [19] the following are the assumptions: 1. The sensors in the wireless sensor network are distributed randomly in a two dimensional space. 2. The communication environment is contention-and error-free; hence, sensors do not have to retransmit any data. # Data exchanged between two communicating sensors not within each others' radio range is forwarded by other sensors. 4. The radio model considered is similar to LEACH. 5. Randomized, adaptive and self-configuring cluster forming. 6. Localized control over data transfers. In the premise of CDS construction Li et al. [2] algorithm for constructing CDS is used. It is called as Approximation Two Independent Sets based Algorithm (ATISA). The ATISA has three stages: ? Constructing a connected set (CS) ? Constructing a Connected Dominating Set ? Pruning the redundant dominators of CDS. ATISA constructs the CDS with the smallest size, compared with some well-known CDS construction algorithms. The message complexity of this algorithm is O(n). Keeping the view of message complexity part the choice of using Li et al algorithm is used. In LEACH the distributive algorithm works on the basis of selecting clusters which have higher energy than threshold value. But the logic of the choice is entirely based on energy levels but the connectivity part is not taken care of. As the result not all nodes in the cluster may be able to send the data to the cluster head. Thus by considering the connected dominating set the cluster head positions will be in a perfect position to receive the data. So by using the concept of connected dominating as an additional requirement other than energy requirements is incorporated in LEACH algorithm to get improved performance results. Below depicts the hybrid CDS-LEACH flow chart for selecting heads and their operation in tandem. Simulator Specifics V. # Results and Discussions The Simulator as described is used with two kind of protocols 1. LEACH 2. CDS-LEACH When these protocols are run according to the standard algorithm the following are the output regarding the cluster formation and cluster heads. The node distribution over the network area is random and the base station is at the origin bottom left not shown in the picture. Similarly for CDS-LEACH the simulation was carried out and the screen short of the last round of the simulation is as depicted in the figure below. From Figure 4 and 5 it can be easily seen that the performance is not that significant in case of 250 nodes but it becomes quite significant in case of 400 nodes structure. Below is some of the representative statistics of 250/400 node simulation figures. The above table depicts the comparison of LEACH and CDS-LEACH parameters. Hence it can be implied that the CDS-LEACH is more energy efficient than that of LEACH. # VI. # Conclusions and Future Work It can be easily seen that merely having the conditions of higher energy in selecting clusters is not energy efficient but having added criteria such as connect dominating set helps in proper dissemination of the data within the cluster .Moreover the energy savings for 400 nodes may be seeming less but this figure may find its significance when the number of nodes cross 1000. In future work, the intension is to extend this concept of dominating sets in LEACH like protocols TEEN, APTEEN, and HEED etc. 1![Figure 1: CDS-LEACH cluster head selection algorithm](image-2.png "Figure 1 :") 2![Figure 2: The LEACH protocol implementation for 250 nodes network. The cluster shapes are represented in voronoi cells and cluster heads in green circles for the last round. And the yellow triangles are the normal nodesThe node distribution over the network area is random and the base station is at the origin bottom left not shown in the picture.Similarly for CDS-LEACH the simulation was carried out and the screen short of the last round of the simulation is as depicted in the figure below.](image-3.png "Figure 2 :") 3![Figure 3: The screen shot for the last round of the execution of CDS-LEACH protocol for 400 nodes. The asterisk nodes were the cluster head nodes for the last round .Here the base station is in the bottom left not shown in the figure. The circles are positions of CDS fulfilled nodes](image-4.png "Figure 3 :") 1Sr. No.DescriptionValue1Radio electronic energy50nJ2Bitrate1mbps3Antenna height from the ground1.5 m4Antenna Gain factor15Signal wavelength0.325m6Radio Amplifier energy10pJ/bit/m27Network size100mX100m8Radio propagation speed3X10^89Base Station Coordinates(0,0)10Optimum Cluster Size [19]C*?N*M/d^2 2S. No.ParametersProtocols250 nodes400 nodes1First dead node roundLEACH CDS-LEACH6 127 132Total energy expended by CHsLEACH 5.978611 8.113001 CDS-LEACH 5.924069 6.2708373Data Transferred to CHsLEACH CDS-LEACH19007 1927626902 27800 © 2020 Global Journals * A Power Aware Minimum Connected Dominating Set for Wireless Sensor Networks MRai Sh ShVerma Tapaswi Journal of networks 4 6 August 2009 * Approximation Two Independent Sets Based Connected Dominating Set Construction Algorithm for Wireless Sensor Networks ZLiu BWang QTang Inform. Technol. J 9 5 2010 * Next century challenges: scalable coordination in sensor networks DEstrin RGovindan JSHeidemann SKumar Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking the 5th annual ACM/IEEE international conference on Mobile computing and networkingSeattle, USA 1999. August 15-20 * Wireless sensor networks: a survey IAkyidiz WSu YSankarasubramaniam ECayirci Computer Networks 38 4 2002 * Data gathering algorithms in sensor networks using energy metrics SLindsey CRaghavendra IEEE Transactions on Parallel and Distributed Systems 13 9 2002 * WALEACH: Weight based energy efficient Advanced LEACH algorithm AThakkar KKotecha Computer Science & Information Technology (CS & IT) 2 4 2012 * Energy-efficient sensing in wireless sensor networks using compressed sensing MARazzaque SDobson Sensors 14 2 2014 * Algorithms for Node Clustering in Wireless Sensor Networks: A Survey PKumarawadu DJDechene MLuccini ASauer Proceedings of IEEE IEEE 2008 * Max-Min D-Cluster Formation in Wireless AdHoc Networks AlanDAmis RaviPrakash HPThai TVuong Dung Huynh Proceedings of IEEE conference INFOCOM IEEE conference INFOCOM 2000 * WCA: A Weighted Clustering Algorithm for wireless adhoc networks Maniak Chatterjee .KSajal DamlaturgutDas Journal of cluster computing 2002 * GROUP: a Grid-clustering Routing Protocol for LiyangYu NengWang WeiZhang ChunleiZheng * Wendi Rabiner, Heinzelman, Anantha Chandrakasan, HariBalakrishnan. Energy-Efficient Communication Protocol for Wireless Microsensor Networks Proceedings of IEEE conference on Wireless communications, Networking and Mobile Computing (WiCOM) IEEE conference on Wireless communications, Networking and Mobile Computing (WiCOM) 2006 13. 2000 Proceedings of IEEE * A Two-Levels Hierarchy for Low-Energy Adaptive Clustering Hierarchy (TL-LEACH) VLoscrì GMorabito SMarano 7803-9152-7/05 Proceedings of IEEE 2005 IEEE 2005 * HEED: A Hybrid, Energy-Efficient, Distributed Clustering Approach for Ad-hoc Sensor Networks OssamaYounis SoniaFahmy IEEE transactions on Mobile computing 3 4 Oct-Dec 2004 * Algorithms for Node Clustering in Wireless Sensor Networks: A Survey PKumarawadu DJDechene MLuccini ASauer Proceedings of IEEE IEEE 2008 * Span: An Energy Efficient Coordination Algorithm for Topology Maintenance in Ad Hoc Wireless Networks BenjieChen KyleJamieson HariBalakrishnan RobertMorris Wireless Networks 8 2002 Kluwer Academic Publisher * ACE: An Emergent Algorithm for Highly Uniform Cluster Formation HaowenChan AdrianPerrig Proceedings of the First European Workshop on Sensor Networks (EWSN) the First European Workshop on Sensor Networks (EWSN) Springer 2004 2920 * Application-specific protocol architectures for wireless networks WHeinzelman Massachusetts Institute of Technology * MACambridge 2000 PhD Thesis