A Survey on Connected Dominating Sets (CDS) Both in the Wireless Sensor Networks and Wireless Ad Hoc Networks

A Survey on Connected Dominating Sets (CDS) Both in the Wireless Sensor Networks and Wireless Ad Hoc Networks

aS. Vijayasharmila, bDr. P. Ganesh Kumar

Department of Information technology, KLN college of engineering.

Sivagangai,India.

cS. Kamalesh,

Department of Information technology, Velammal college of engineering and technology, Madurai,INDIA.

Abstract – Wireless sensor networks consist of large number of tiny sensors that are deployed randomly. The sensor nodes may be static or mobile forming ad hoc or Sensor networks respectively. These two networks have few similar properties but have their own uniqueness. The ad hoc networks have node mobility. Energy consumption is a fundamental issue in both wireless ad hoc and sensor networks.Sensor nodes in the network monitor different regions of an area.To extend the lifetime of the network and to improve the performance we construct the connected dominant sets (CDS). The CDS acts as the virtual backbone of the network. Given a query over the sensor networks the minimum connected sensor, it should cover the full coverage area. A single sensor node failure in the connected dominant sets leads to network portioning and loss of connectivity. In this paper different types of algorithms of CDS and related problems were discussed. Adding to that some open problems and issues also proposed in this paper.

Keyword- Connected Dominant Set, Wireless sensor networks, Wireless ad hoc networks, Fault tolerance, Energy consumption.

1. INTRODUCTION

   Wireless sensor networks are highly distributed networks of small, lightweight wireless nodes, deployed in large numbers to monitor the environment or system by the measurement of physical parameters such as temperature, moisture, relative humidity or pressure. Building sensors has been made possible by the recent advances in micro- electro mechanical systems(MEMS) technology. Each node of the sensor network consists of three subsystems: the sensor subsystem which senses the environment, the processing subsystem which performs the local computation of the sensed data, and the communication subsystem which is responsible for message exchange with neighboring sensor nodes. While individual sensors have limited sensing region, processing power and energy, networking a large number of sensors give rise to a robust, reliable and accurate sensor covering a wider region. The network is fault-tolerant because many nodes are sensing the same events. Further, the nodes cooperate and collaborate on their data which leads to accurate sensing in the environment. The two important operations in a sensor

   network are data dissemination, which is the propagation of data/ queries throughout the network, and data gathering, that is, the collection of observed data from the individual sensor nodes to a sink. The nodes form a network by using connected dominant set(CDS). The CDS used in the network as a virtual backbone to improve the performance. Such a network consists of many sensor nodes, each of which is not only a mobile host but also a router. The nodes forward the packets according to the routing protocols.

   The principle behind the ad hoc networking is multi-hop relaying and is capable of operating without the support of any fixed infrastructure. The absence of any central coordinator or base station makes the routing complex. PRNET used a combination of ALOHA and carrier sense multiple access for access to the shared channel. The radio interface employed the direct- sequence (DS) spread spectrum scheme. The system was designed to self-organize, self-configure, and detect radio connectivity for the dynamic operation of a routing protocol without any support from fixed infrastructure.

   As a decentralized distributed systems and it does not have any central coordinator, each subscriber possesses the functions of router and host. So it is easy to implement the rapid wireless communication. It does not relay on existing or predefined network infrastructure. Mobile nodes are deployed randomly. So guarantee of high-signal communication when terminal nodes are mobile is a key problem in the research field. In order to prevent node failure by network redundancy, many modes are deployed in a small region. The issues related to redundant nodes are mutual interference between the nodes, variety of routing possible methods. And also the nodes undergoes direct communication with distant nodes by using a lager power. It consumes unnecessary energy and limited reuse of wireless bandwidth.

   Though the nodes are mobile and if it moves even a small distance the routing protocols have to be calculated. Replacement of failure nodes by either direct or cascaded movement improve the lifetime of the network.In the wireless network, once the nodes are deployed, each node communicates with other nodes within a certain distance. The communication links are established between those nodes to ensure that the radio signal can be detected. Once the nodes are deployed it is impossible to recharge the

   battery or replace it. So it is most important to save the power source. Changing the transmission power of the nodes reduces the network topology, it saves energy and also it improves the lifetime of the network while preserving the connection between the nodes and coverage area[2].

   The applications of wireless sensor and ad hoc networks are military, civil, environment monitoring, biological detection, vehicle tracking, and battlefield surveillance.WSNs can be used for a wide variety of applications dealing monitoring which includes health environments, seismic etc., and in control which includes object detection and tracking. In environmental applications, sensor networks have been used to monitor a variety of environmental parameters or conditions in marine, soil and atmospheric contexts[3]. The broadcasting, activity scheduling and sensor area coverage algorithms rely on the concept of backbone. The backbone is nothing but a subset of nodes which is able to perform data communication tasks and it also serve the nodes which are not in the backbone. In order to achieve the scalability and efficiency of a wireless network, it is necessary to construct the virtual backbone network base station to organize the network into a hierarchical structure. A virtual backbone network can be used as a spine for routing in a network. This includes few nodes in the backbone and it greatly reduces the routing overhead. It has an important role in broadcasting. A connected dominating set(CDS) of a graph usually forms the virtual backbone of the network to improve the performance[4].

   In the wireless sensor network, the packets are either transferred between adjacent nodes or transferred through intermediate nodes. Those intermediate nodes form the virtual backbone structure which is a connected dominant sets in the graph setting. It transmits the messages quickly. A dominating clique can provide a virtual backbone structure for a wireless communication network which has the shortest communication time. The messages will be transmitted between the dominating clique members. Any message that transmitted from source to destination can reach at 3 hops but the existence of the dominating clique in wireless networks may be costly. The dominating s-club provides advantages over the CDS in terms of speed of communication, energy consumption and reliability[8]. During node mobility, the topologies changes frequently. Even if one node leave the network or else new node added to the network, the topology should be changed. The topology changes takes place during the node failure also. If the changes takes place frequently, then more energy is needed to form the new topology each time[7]. In Wireless sensor network applications, individual nodes cannot easily be connected to a wired power supply. Mobility plays a critical role n WSN self-healing and self-repair[2]. As the requirement differs for each application, the design of wireless sensor networks is not unique. But the sensors are cheap devices. In unit disk graph every sensors have the same power and it communicates with the other nodes within the unit distance so that the topology of the sensor network can be formulated[6].

   A unit disk is a disk with radius one. A unit disk graph is associated with a set of unit disks in the Euclidean plane. The graph G=(V,E) where each vertex V in the graph is the center of a unit disk and egde E exists between two vertices u and v if and nly if |uv|<= 1 where |uv| is the Euclidean distance between u and v. It means that two vertices are connected by an edge if and only if us disk covers v and vs disk covers u. The CDS is often used to improve communication and storage performance. Smaller the virtual backbone gives the better performance. Computing the Minimum connected dominating set is NP- hard even in unit disk graphs[6].

   The application of wireless networks includes:

   • CDS can be created to improve the performance of the network. A sensor node (SN) is a dominator of another SN if the dominated SN is in the transmission range of the dominator.

   • CDS used to improve the fault tolerance and helps to form the resilient failure network[2].

   • CDS can be created by dominating clique which provide a virtual backbone structure for a wireless communication that has shortest communication time[8].

   • In the wireless sensor networks, based upon the CDS approach, power efficient scheduling algorithm is designed to extend the lifetime of the sensor nodes[7].

   • The minimum connected dominant set construction is based on the construction of maximal independent set[6].

   • Using CDS a compact integer programming formulation for the minimum dominating s-club problem and developed some variable fixing rules and valid inequalities[8].

2. DEFINITIONS AND TERMINOLOGIES:

   1. Terminologies:

      Strongly connected: . A graph G is said to be strongly connected if for any pair of nodes u; v 2 V, there exists a directed pathbetween them. Likewise, a subset S of V is called a strongly connectedset if G[S] is strongly connected[4].

      Independent set (IS). An IS is a subset S of V such that there isno edge in G[S][4].

      Maximal independent set (MIS). An MIS is an IS such that addingany node not in the set breaks the independence property ofthe set. Thus, any node not in the MIS must be adjacent to somenode in the set[4].

      Dominating set (DS). Let D be a subset of V; D is a DS if eachnode in V n D is adjacent to at least one node in D. Thus, everyMIS is a DS. However, since nodes in a DS may be adjacent toeach other, not every DS is an MIS. Finding a minimum dominatingset [MDS] is NP-hard[9]. Connected dominating set (CDS). A CDS C is a DS of G, and G[C]is connected. There exist many CDS construction algorithms. Inthe next section, we give a specific summary of these algorithms[9].

      Minimum connected dominating set (MCDS). A MCDS is aCDS with minimum cardinality. Finding the MCDS is also NPhard[9].

      Network model:In wireless sensor network, a graph G=(V,E) represents a network where each node is a radio sensor and each undirected edge is a communication link between nodes. Few of the network models are Unit Disk Graph(UGD), Disk Graph(DG), Unit Ball Graph(UBG),

      sensing area with si, i.e., if A(si)A(sj) , sj S then sj Nc(si)[2].

      i

      j

      Definition 3: The transmission neighbors of a sensor node si(Nt (si)) is the set of all sensor nodes that si can directlycommunicate with, i.e., if d(si, sj) <rt , where s S

      Cooperative communication (CC) approximation model and Antenna model.

      d-CDS( d-hop connected dominating set): D-hop connected dominant set(d-CDS) is: given a graph G=(V,E), d-CDS is a vertex subset D of V such that for any vertex u, either u D or there exists a vertex v D, and we can find a path in G from u to v within d hops. The sub graph induced by G[D] is connected. If we consider only the dominating properties, the selected subset is called d-hop dominating set(d-DS) for short[5].

      Weight of the node:The weight of the node is calculated by the following equation:

      Weight(u)= ( ) + ( )

      max ()

      Where EDG(u) is the effective degree of node u, CE(u) is the current remaining energy of the node, max DG is a constantof the max degree of the network graph and FE(u) full energy of u[1].

   2. Definitions:

   Definition 1: The sensing area of a sensor node si(A(si)) is

   and d(si, sj) is the distance between si and sj then sj Nt (si)[2].

   Definition 4:The communication area of a SN (C(si )) is the area in which si can communicate directly with other SNs[3].

   Definition 5: The communication neighbors of a SN si (N(si)) is the set of all SNs that located inside C(si)[3].

   Definition 6: The ReachabilityTable (RTBL(si) of a SN si is the table that maintains the reachability information for each SN sj 2 CN. The RTBL structure is formed from the attributes ID, Path, where ID is the SN identification number, and Path is a sequence/path of SNs that form the shortest communication path connecting si with sj.[3].

   Definition 7: The available total energy Etotal(x,y) for monitoring a location is defined as follows:

   Etotal(x,y)= :(, )( ) ()

   for each point (x,y) of the monitored area, where () is the remaining energy of a SN sj[3].

   Definition 8: The minimum-weight coverage cost of a SN si is defined as[10] :

   C (s )=max 1 , (x.y) ()

   the area in which si can sense a physical phenomenon[2]. Definition 2: Coverage neighbors of a sensor node si(Nc (si)) is the set of all sensor nodes that have a common

   mw i

   Etotal (x,y)

3. CDS CONSTRUCTING ALGORITHMS:

The CDS construction algorithms are classified into different types. It is based on whether the network topology is prescient or not, network models, efficiency of the algorithm in forming a small size CDS and its time and information complexity.

3.2.1 According to the network topology is prescient or not, the CDS construction algorithms can be classified into two types:

1. Centralized algorithms- The centralized algorithms give better performance ratio with small size CDS. But it works in an assumption that the whole network topology is known. Such kind of assumption is not feasible in real time applications. The centralized algorithms construct CDS based on the finding a small weakly connected dominating set (WCDS). Different algorithms for WCDS is designed and the performance is analyzed by finding the size of the resultant WCDS. It has also been compared with minimum WCDS. The centralized algorithms also include independent set based algorithms. It is implemented in both Unit Disk Graph and Disk Graph.

2. Decentralized algorithms: The decentralized algorithm is classified into two types. They are

   1. Distributed algorithms- In distributed algorithm, the decision process for construction of CDS is decentralized. It is further divided into Prune based and MIS (Minimum Independent Set) based.

      In Prune based algorithm, different types of algorithms are used. In [11] the Dominating Set (DS) is constructed first and then DS is connected to form the Connected Dominatin Set (CDS). In [12] the CDS is constructed first and then redundant nodes are removed from CDS.

      In MIS based algorithms, MIS is constructed first and then interconnection of nodes is given in MIS next step. The MIS based algorithms is further divided into two types of algorithm namely Single initiator and Multi-Initiator algorithms Single initiator algorithms are used in routing protocols. It is used to construct routing methods in ad hoc wireless networks by using both Minimum Connected Dominating Sets (MCDS) and Spine. But this algorithm has poor quality i.e O(log n) and it is also very expensive to maintain CDS[18,19]. In Multi-Initiator algorithms, the paper [20] proposes two message/time efficient distributed algorithms. In this paper the problem in constructing virtual backbone for wireless ad hoc networks is studied. This is designed by computing minimum connected dominating sets (MCDS) problem in UDG. It is NP-hard in computational complexity theory[20].

   2. Localized algorithms- In localized algorithms, the decision process for construction of CDS is distributed. The localized algorithm is further divided into two types based on the nature of the algorithms. They are addition- based and subtraction-based algorithms.

      1. Addition-Based algorithms: In addition based CDS construction algorithms, it starts with subset of nodes

         which are commonly disconnected and then nodes are added to the subset of nodes to form the CDS. The addition based algorithms are further divided into two types based on the initial subset. They are MIS-based CDS algorithms and Tree-based CDS algorithms.

         1. MIS-based CDS algorithms [13,14]: In this type of algorithms, initially the Maximal Independent Sets (MIS) are constructed by recursively selecting the nodes which are located closely to each other. The nodes in the MIS forms virtual backbone of CDS. Then the localized search is done to add additional nodes to the MIS and it forms the CDS.

         2. Tree-based CDS algorithms [13,14]: In this type of algorithms, initially it starts with subset of nodes which are called as initiators and a CDS tree has been constructed from each of the initiators. These types of algorithms have 3 stages. Initially the number of initiators is selected from the given network. Then each initiators uses the timer to extend the tree by adding more neighbor nodes to the tree. Finally connecting nodes or bridge nodes are used to connect the tree.

      2. Subtraction-based CDS algorithms: The subtraction based algorithms are opposite to addition-based algorithms. In subtraction-based algorithms, CDS constructions start with set of all the nodes in the network and then by different methods or rules are applied to removed few nodes to form the CDS.[4] The addition-based algorithms generally produce smaller CDS than the subtraction-based algorithms and the tree-based algorithms yield low communication overhead[17].

3.2. According to the network models, the CDS construction algorithms can be classified into two types:

1. Undirected graphs[15,16]: Undirected graph is further divided into General undirected graphs and Unit disk

   graphs (UDG). In General undirected graph type network model, the performance ratio of the algorithm is related to the maximum degree of the graph G. In Unit disk graph type network model the performance ratio is constant due to the special geometric structure of UDG.

2. Directed graphs: In wireless sensor networks, the transmission range of all the nodes need not be same. Wireless sensor networks can be constructed with the help of directed graph. Instead of using virtual backbone of a wireless network with unidirectional links, the Strongly Connected Dominating Sets (SCDS) is proposed[4].

1. According to the efficiency of the algorithm while forming the minimum CDS, the CDS construction algorithms can be further divided into four types.

   1. Global protocols: The global protocols yield smallest CDS but its maintenance cost is high. It assumes that global information about the network is available in the central point of the network and CDS is constructed based on that information[4].

1. Quasi-global protocols: This protocol it depends on the global coordination rather than global information. The computation starts from central point and is propagated to the entire network. This algorithm has high overhead of the global infrastructure makes less attractive[4].

2. Quasi-local protocols: It assumes no central point but propagation of information is possible. This protocols have large constant approximation ration in UDG but moderate overhead as the nodes are selected in parallel to form MIS[4].

3. Local protocols: This type of protocol depends on local information and there is no sequential propagation. This protocols have constant deterministic approximation ratios. In random UDG, the expected size of the resultant CDS is O(1) times that of the minimum CDS[4].

   Figure 1. Taxonomy of CDS construction algorithms.

   4.CDS RELATED ALGORITHMS:

   1. Mobility-Assisted minimum connected sensor cover(MCSC):

      A new algorithm is designed to select the minimum number of sensor nodes which can entirely cover a monitored region. As a result of this step, the redundant sensor nodes are determined. Then appropriate redundant sensor node to replace the failure that would occur in minimum connected sensor cover by relocating. The picked redundant sensor node using a weighted based shortest path algorithm. This algorithm includes four phases namely: initial, connectivity, finding minimum connected cover, and mobility assistance. In the initial phase, the sensors are grouped into grids. Each grid has a Cluster Head (CH) and many cluster members. The cluster members may be sensing node or non-sensing node. The cluster head collect information from its members and send to neighboring Cluster head. In the connectivity phase, it includes 3 detailed processes. They are initialization setup and finding the direct communicated sensor nodes to CH, determining the hop count for each sensor node and finally constructing the connected routing path for each sensor node to its CH.In the finding minimum connected cover phase, power-aware selection method is used to select the sensor nodes that has largest coverage area with highest residual energy and minimum communications cost from unselected sensor nodes.In the mobility assistance phase,

      each sensor node periodically checks its energy level with the predefined threshold values. To recover the failure node, three cases occur in order to recover. They are cluster head has no redundant nodes, cluster head has no redundant nodes but its neighbor cluster head have redundant nodes and neither cluster head nor of its neighbor cluster head has no redundant nodes. This algorithm greatly reduces the energy consumption. This algorithm considers the network energy to replace the faulty node by either direct or cascaded movement and reduce the location distance[2].

   2. Minimum connected cover determination:

      In this algorithm a minimum connected sensor node (SN) that cover the monitored region or queried region. This algorithm includes two steps namely: initial phase which is constructing the coverage neighbors set and Identification phase. In the first phase, initially the coverage neighbor set is empty. Then the cluster members are added to that if it is within the coverage area of the cluster head. Broadcast coverage neighbor discovery request CovReq(s) is sent to representative nodes to find coverage information. The ProcessCovReq procedure function is executed. It includes current node, target node and the CovReq(s) owner to

      execute this procedure function. In the identification phase

      , each SN broadcasts an update packet with information about its remaining energy to its coverage neighbors. In order to reduce the packet collisions, the sensor node use Random Back-offs before sending the update packets. Each sensor node executes the algorithm in order to find whether the node is sensing node or not. The minimum-weight coverage cost is used as metric by which SN determines whether to be a sensing node or not. This algorithm has a lower communication overhead than the greedy algorithms. It reduces the number of redundant Sensor nodes[3].

   3. DFRN: Detection and replacement approach of a failing node for connectivity maintenance in the wireless sensor networks:

In this approach, if a sensor node fails due to its power drain then its neighbor node has to move to replace it and ensure the functions of this failing node. The node which is replaced in the place of failing node has to be replaced by its neighbor node to ensure its functions. This replacement process continues until either a node where its zone is completely covered by its neighbors or else to arrive at a node which does not have any other node than the node subject for the replacement. In this case, this node must ensure its functions and the functions of the replaced node in intermittency by making back and forth between its place and the place of the replaced node until its weight decreases compared to the other neighbors of the replaced node. The idea is to imply in the replacement a node which has a potential energy higher than a node which has a low potential energy. The number of neighbors and the distance between the sensors can also be a significant criteria. The implication of several nodes permits to share the energy consumption and thus to extend the global network lifetime.This approach has two algorithms namely: detect- fail() to detect the fault node and the repl-fail() to replace

Hop neighbor of all nodes. The idle nodes are picked and mark it as dominator node and all of its d-Hop neighbors as dominate. The second phase is connecting the dominating sets gained in the first phase and optimizing the connected paths. Minimum d-CDS problem is NP-complete in Unit Disk Graph[5].

1. Minimum connected dominating sets and maximal independent sets in unit disk graphs:

   The relation between between the size mis(G) of a maximum independent set and the size cds(G) of a minimum connected dominating set in the same graph G plays an important role in establishing the performance ratio of those approximation algorithms. Every maximal independent set is a dominating set and it is easy to construct, one usually constructs a maximal independent set at the first step. Therefore, the approximation performance ratio can be determined by two facts. The first is how large a maximal independent set can be compared with a minimum connected dominating set. The second is how many vertices are required to connect a maximal independent set. It is shown that in every unit disk graph G,

   mis(G) 4. cds(G) +1,

   Where mis(G) is the size of a maximum independent set and cds(G) is the size f a minimum connected dominating set in G. In this paper it is proved

   mis(G) 3.8. cds(G) +1.2.

   The performance ratios are improved[6].

2. On connected dominating sets of restricted diameter:

club

The minimum dominating s-club problem is focused in this paper. Given a graph G=(V,E) and a positive integer constant s, find a smallest dominating set D V such that diam(G[D]) s, or decide that non exist. When a dominating s-club exists in G, then the size of a minimum dominating s-club the dominating s-club number

the fault node. In the fault node detecting algorithm each

of G and denote it by s

(G). Not every graph has

node sends message detect packet to its neighbor node. If it does not receive any reply packets from its neighbor for certain duration then it is a failing neighbor node. In the repl- fail(), if a failing node is detected, then for each of its direct neighbor node information message of displacement is sent. If a node is elected substitute, then to displace to ensure the functions of the failing node. If its direct neighboring list is empty, then remain a quantum to remain it its place. This algorithm restore the network connectivity by exploiting the sensors mobility taking into account the energy constraint. It uses less displacements than C3R approach. It efficiently contributes to prolong the lifetime of the network. It consumes less energy and improves the coverage area with minimum number of sensor nodes[1].

4.4 d-Hop Connected Dominant Sets:

d-Hop connected dominating set is constructed to greatly reduce the size of the dominating set. The d-hop Dominating Set (d-DS) are connected to form the d-Hop Connected dominant sets(d-CDS). In this approach, the algorithm is divided into two phase. In the first phase, Constructing d-Hop cluster and all cluster heads of each cluster to form d-Hop dominating set. It calculate the d-

dominating s-club, as evidenced by the class of disconnected graphs. In the minimum connected dominant set problem, two different ways to solve the problem. In first approach use any MCDS heuristic to find a decent upper bound U on c(G)by the proposition, Suppose U is an upper bound c(G). A solution to the minimum dominating s-club problem, where s=(U-1), solves the MCDS problem. In the second approach it use a proposition, Suppose P solves the minimum dominating s-club problem in G. If |p| s+2, then P solves the MCDS problem in G. This paper considers the problem of finding the smallest diameter-restricted dominating set. It provides a compact integer programming formulation for the minimum dominating s-club problem and develop some variable fixing rules and valid inequalities[8].

4.7 Efficient scheduling scheme using connected dominant sets for Sensed data aggregators in sensor networks.

An efficient scheduling scheme is used for improving the lifetime of the sensor nodes on wireless sensor network. The power efficient sleep scheduling algorithm is designed based on the connected dominant sets. The connected dominant set is constructed first fr

parent selection and the conjugative sleep scheduler scheme is used for data aggregation.The main objective is to combine the features of connected dominant set along with the conjugative sleep schedule algorithm to extend the lifetime of the network. Some of the features are the formation process should be distributed and as simple as possible, the resultant dominant set should be connected and minimum and the set should includes all the intermediate nodes of any shortest path. In conjugative power efficient sleep scheduling scheme, conjugative sleep schedule operation and conjugative power efficient sleep scheduling algorithm is used. In conjugative operation there are two states: 1) A state in which no target is

6.SUMMARIZATION AND OPEN PROBLEMS:

The CDS related problems in the existing literature can be summarized as follows:

• The minimum d-CDS problem is NP-complete in UDG. The future work is of maintaining the d-CDS through some of rounds when moving around with the Random-Walk Mobility and Guass-Markov mobility models. Most of the studies in this area focus on reducing the size of CDS[5].

• The values of , while calculating the weight of the node which is given by

  involved and 2) A state which target is involved. The energy efficient sleep scheduling algorithm involves in tracking the states. For each node n in the tracking neighbors, the distance to the neighbor root node is

  Wn= %

  +

  optimized[1].

  should be

  calculated. The angle between the root node andnode n is calculated and Tend, Tstart also computed. The duty cycle is calculated and it is set as the next cycle values as DCmax. Then set the nodes duty cycle recovery number as Round(Tend-Tstart)/TC where Round is the rounding function and TC is toggling function. If the Tstart= minimum_sleep_time then i) set node n state as SLEEP, ii) reset node n waking up state as Tstart. After the parent is selected by using the CDS and then the data aggregation is continued by sleep scheduler strategy. The connected dominant set is recalculated based on two different topological conditionssuch as sensor node as ON condition and OFF condition.The conjugative scheduler scheme for data aggregation in wireless senor network provides an efficient routing algorithm. The properties of both connected dominant set and Minimum Spanning Tree for finding the shortest path tree routing schemes are used. As the result, even though the node density increases, the life time increases with the applications of CDS.The sleep schedulealgorithm is more suitable for extending the life time. By applying the distributed sleep scheduling algorithm, the performance is improved on the high density networks. Better lifetime and better energy savings is achieved in wireless sensor networks by the performance of conjugative power efficient scheduling scheme with and without the application of CDS[7].

  5. SIMULATION TOOLS:

  More number of network simulators have been is proposed by many researchers. In general,the network simulators can be classified into 3 major categories based on the complexity. 1. Algorithm level simulator: This type of simulator focus on the logic, presentation of the algorithms and data structure. 2.Packet level simulator: This simulator implements the data link and physical layersin the SI network stack. The most popular and widely used network simulator is ns2. The extension of ns2 is sensorism which provides battery models, radio propogation models and sensor channel models. 3.Instruction level simulator: This simulators model the CPU execution at the level of instructions or even cycles. They are often called as emulators.

• The number of displacements in the repl-fail()

  algorithm can be reduced[1].

• The node failure is non negligible event. So they must provide enough fault tolerance and robustness for dominators to form the resilient networks[1].

• As the nodes in the ad hoc networks are mobile, even if the nodes move if the nodes move a small distance the topology should be reconstructed using efficient routing protocol methods which use minimum energy.

• The minimum connected dominant sets and maximal independent sets in unit disk graphs, the problem is how smallest the value of constant and in the relation between the size mis(G) <=.cds(G)<=+, where mis(G) is the size of maximal independent set and cds(G) is the size of minimum connected dominant set[6].

• The important open problem is whether a similar relation between the minimum connected dominating set and the maximal independent set hold in unit disk graph? In fact if such a relation is established, then it can imply the existence of constant-bounded polynomial-time approximations for the minimum connected dominating set in disk graph[6].

• The complexity of the minimum dominating s-club problem in unit disk graphs is an open question. Because the MCDS(minimum connected dominating sets) problem remains hard in the class of graphs[8].

7. CONCLUSION:

By analyzing different papers regarding the connected dominant sets, a multi-objective algorithm is going to be designed which concentrates on fault tolerance and extend the lifetime of the network. The main objective is to form a resilient network and increase the capability of the WSN.

REFERENCES:

[1]AbdelmalekBoudries, MakhloufAliouat, Patrick Siarry, Detection and replacement of a failing node in the wireless sensors networks, November 2013.

[2]. Ahmed M. Khedr ,WalidOsamy, Mobility-assisted minimum connected cover in a wireless sensor network, published on April 2013.

[3]. Ahmed M. Khedr ,WalidOsamy, Minimum connected cover of a query region in heterogeneous wireless sensor networks, published on October 2012.

[4]. Jiguo Yu a,b,, Nannan Wang a, Guanghui Wangc, Dongxiao Yu,Connected dominating sets in wireless ad hoc and sensor networks A comprehensive survey, October 2012.

[5]. Chan Zhenga,b,, Ling Yinb, Shixin Sun, Construction of d- Hop Connected Dominating Sets in Wireless Sensor Networks, published in 2011.

[6]. Weili Wua,,1, Hongwei Dub, Xiaohua Jiab, Yingshu Lic, Scott C.-H. Huangb, Minimum connected dominating sets and maximal independent sets in unit disk graphs, published on august 2005.

s[7]. K. P. Sampoornama, K. Rameshwaranb, Efficient Scheduling Scheme Using Connected Dominating Set

for Sensed Data Aggregators in Sensor Networks, published on 2011.

[8]. Austin Buchanan ,Je Sang Sung,Vladimir Boginski, Sergiy Butenko,On connected dominating sets of restricted diameter, published on November 2013.

[9]. S. Schmid, R. Wattenhofer, Algorithmic models for sensor networks, in: Proceeding of the 20th International parallel and Distributed Processing Symposium(IPDS), April 2006.

[10]. S. Soro, W.B. Heinzelman, Cluster head election techniques for coverage preservation in WSNs, in: Ad Hoc Netw., 2008. [11]. Khaled M. Alzoubi Peng-Jun Wan Ophir Frieder (2002). New Distributed Algorithm for Connected Dominating Set in Wireless Ad Hoc Networks. In: Proceedings of the 35th Hawaii International Conference on System Sciences IEEE.

(pp. 3849-3855).

[12]. J. Wu and H.L. Li (1999). On calculating connected dominating set for efficient routing in ad hoc wireless networks. In: Proceeding of the 3rd ACM, workshop on discrete algorithms and methods for mobile computing and communications, 714.

[13]. Y. Li, M.T. Thai, F. Wang, C.W. Yi, P.J. Wan, D.Z. Du, On

greedy construction of connected dominating sets in wireless networks, Wireless Communications and Mobile Computing 5 (8) (2005) 927932.

1. P. Wan, K. Alzoubi, O. Frieder, Distributed construction of connected

   dominating set in wireless networks, in: Proceedings of IEEE Conference on, Computer Communications (INFOCOM), April 2002, pp. 141149.

2. M.A. Rajan, M. Girish Chandra, Lokanatha C. Reddy, Prakash Hiremath, Concepts of graph theory relevant to ad hoc networks, International Journal of Computers, Communications and Control (2008) 465469.

3. S. Schmid, R. Wattenhofer, Algorithmic models for sensor networks, in: Proceeding of the 20th International Parallel and Distributed Processing Symposium (IPDPS), April 2006.

[17]. D. Zhou, M.T. Sun, T. Lai, A timer-based protocol for connected dominating set construction in IEEE 802.11 wireless networks, in: Proceedings of International Symposium on Applications and the Internet (SAINT), January 2005, pp. 28.

[18]. V. Bharghavan and B. Das (1997). Routing in Ad Hoc Networks Using Minimum Connected Dominating Sets. In: Proceeding of International Conference on Communications ICC 97, Montreal, Que, vol. 1, (pp. 376-380).

[19]. B. Das, R. Sivakumar, and V. Bhargavan (1997). Routing in Ad-Hoc Networks Using a Spine. In: Proceeding of International Conference on Computers and Communications Networks 97. Las Vegas, NV, (pp. 34-39). [20]. X. Cheng, M. Ding, D. H. Du and X. Jia (2006). Virtual backbone construction in multihop ad hoc Wireless networks. Wireless Communications and Mobile Computing

(WCMC), vol. 6, no. 2,183- 190.