A Survey on Connected Dominating Set Construction Algorithm for Wireless Sensor Networks

INTRODUCTION

Recent advances in miniaturization and low-power design have led to the development of small-sized battery-operated sensors that are capable of detecting ambient conditions such as temperature and sound. Sensors are generally equipped with data processing and communication capabilities. The sensing circuitry measures parameters from the environment surrounding the sensor and transforms them into an electric signal. Processing such a signal reveals some properties about objects located and events happening in the vicinity of the sensor. Each sensor has an onboard radio that can be used to send the collected data to interested parties. Such technological development has encouraged practitioners to envision aggregating the limited capabilities of the individual sensors in a large scale network that can operate unattended (Abbasi and Younis, 2007; Akyildiz et al., 2002; Chong and Kumar, 2003. Deborah et al., 1999; Pottie and Kaiser, 2000; Wang et al., 2003; Rabaey et al., 2000; Kahn et al., 1999).

Numerous civil and military applications can be leveraged by networked sensors (Fig. 1). A network of sensors can be employed to gather meteorological variables such as temperature and pressure.


Fig. 1:	WSN’s application examples


Fig. 2:	Architecture of WSNs

These measurements can be then used in preparing forecasts or detecting harsh natural phenomena. In disaster management situations such as earthquakes, sensor networks can be used to selectively map the affected regions directing emergency response units to survivors.

In military situations, sensor networks can be used in surveillance missions and can be used to detect moving targets, chemical gases, or the presence of micro-agents.

Wireless Sensor Networks (WSN) consist a number of wireless nodes. The architecture of WSN is shown in Fig. 2. The WSNs can be divided into three parts: data collection networks, base-station and data management center.

In WSN, there is no fixed or pre-defined infrastructure. Nodes in wireless networks communication via a shared medium, either through a single hop or multi-hops. Such sharing reduces the network performance due to aggravated ratio interference. At same time it raises energy consumption since packet retransmission is needed when interference occurs. Moreover, the energy consumption could be increased if we don’t limit number of active sensor nodes for the data relays. Backbone can be utilized to address the above problems. Backbone will remove unnecessary transmission links by shutting down some of redundant nodes. Nevertheless backbone will still guarantee network connectivity in order to deliver data efficiently in a wireless sensor network. In virtual backboned based WSNs, some nodes are chosen as dominator node (backbone node) in the backbone construction process.


Fig. 3:	CDS construction schematic diagram

All nodes then can directly or indirectly communicate with other nodes via these dominator nodes. The dominator form the backbone and the non-selected nodes can perform sleeping schedule or turn-off the ratio to save the energy consumption. Although, there is no physical backbone infrastructure, a virtual backbone can be formed by constructing a Connected Dominating Set (CDS). Given an undirected graph G = (V, E), a subset V'⊆V))fV is a CDS of G if for each node u ε V, u is either in V' or there exist a node v ε V' such that uv ε E and the sub-graph induced by V', i.e., G(V'), is connected. The node in the CDS are called dominator (backbone node), other nodes are called dominatee (non-backbone node) (Fig. 3). With the help of CDS, routing is easier and can adapt quickly to network topology changes. To reduces the traffic during communication and simplify the connectivity management, it is desirable to constructed a minimum CDS. Constructing a MCDS is proved a NP-hard problem (Jeremy et al., 2004) and in recent years many algorithms of constructing an approximate MCDS have been proposed.

A good CDS should first and foremost be small, additionally, it should have other characteristics such as robustness to node failures and low stretch (routing in the backbone should not be much longer than the shortest routes over the network topology graph).

In this study, we opt to categorize CDS construction algorithms proposed in the literature for WSNs. We report on the state of the research and summarize their feature and shortcomings. We also compare the different approached.

CDS CONSTRUCTION ALGORITHM COMPARISON

We can compare the CDS construction algorithms in some main aspects. In particular, we have considered the following metrics:

•	Algorithm duration: The time needed by each protocol to complete CDS construction
•	The overhead per node (in bytes): Associated to the protocol operations. (These are physical layer measurements, which account for collisions and for the corresponding automatic packet retransmissions at the MAC layer)
•	Energy consumption per node: This metric is important for assessing the application of CDS construction to networks whose nodes are energy constrained. If the energy and the overhead cost of maintaining a CDS is high, then CDS reorganization may impose a non-negligible burden to the network. On the other hand, CDS reorganization in terms of gateway rotation is needed to prevent nodes with more demanding roles from depleting their energy, possibly impairing network operations
•	CDS size: The fraction of the network nodes that are in the CDS (percentage). A smaller CDS is desirable for minimizing the routing overhead. In sensor networks with nodes that can turn off their radio interface (energy saving sleep mode), the CDS size is also a measure of how many nodes need to stay awake for data transport. Usually, the nodes in the CDS stay up or have a higher duty cycle for guaranteeing routes to the sink and hence, the smaller the CDS, the more nodes can be in energy conserving mode
•	Over the sub-graph G_b of the network topology graph induced by the CDS construction. (G_b is the graph where there are no links between ordinary nodes). This metric gives a measure of how well a routing protocol can perform over the CDS
•	Defined as the number of CDS nodes whose removal (because of failure or energy depletion), causes CDS disconnection or the uncovering of ordinary nodes. This is the metric that provides an indirect measure on how long the network will be operational before requiring a CDS re-computation

TAXONOMY OF CDS CONSTRUCTION ALGORITHM

From different aspects, CDS construction algorithms can be classified into different types. Here, some classifications are proposed below.


Fig. 4:	DGB link

UDG and DGB:
The CDS construction algorithms can classified into two classes, which are Unit Disk Graph (UDG) based algorithms and Disk Graphs with Bidirectional (DGB) links (Thai et al., 2007) based algorithms. In UDG and DGB, the link between any pair of nodes is bidirectional. The nodes transmission ranges in UDG are the same, while in DGB are different.

The CDS problem has been studied intensively in UDG, in which each node has the same transmission range. The minimum problem in UDG has been shown to be NP-hard.

However in practice, the transmission ranges of all nodes are not necessary equal. In this case, a WSN can be modeled using a directed graph (G = V, E) (Fig. 4). The nodes in the V are located in a Euclidean plane and each node v_i ε V has a transmission range r_i ε [r_min, r_max]. A directed edge (v_i, v_j) ε E if and only if d(v_i, v_j)≤r_i where d(v_i, v_j) denotes the Euclidean distance between v_i and v_j. Such graph are called disk graphs. An edge (v_i, v_j) is bidirectional if both (v_i, v_j) and (v_j, v_i) are in E, d(v_i, v_j)≤min{r_i, r_j}. In other words, the edge (v_i, v_j) is bidirectional if v_i is in the disk D_j centered at v_j with radius r_j and v_i is in the disk D_i centered at v_i with radius r_j. The minimum CDS problem in DGB is NP-hard since the minimum problem in UDG is NP-hard and UDG is a special case of DGB.

MIS based and Non-MIS based:
Independent set (IS(IS⊆V) is a subset of V. In IS, any pair of nodes is disconnected. Given an Independent Set (IS), if any one node v(vεV–IS) is added into the IS, there will be a pair of nodes connected, then the IS is a Maximum Independent Set (MIS). In MIS, any pair of nodes is disconnected and any node not belonging to MIS is adjacent to at least one node in MIS.

In both UDG and DGB, the CDS construction algorithms are mainly based on the Maximum Independent Set (MIS).

Li et al. (2005) proposed some distributed connected dominating set construction algorithms. Li et al. (2005) proposed a greedy algorithm called S-MIS. The S-MIS has two phases. In the first phase, the MIS construction algorithm is described by Wan et al. (2002). The second phase is the main contribution of Li et al. (2005) and in this phase, black-blue component is proposed, which is a connected component of the sub-graph induced only by black and blue nodes and by ignoring connections between blue nodes. The black node is the dominator of the first phase and the blue node is the dominator of the second phase. In the second phase, a greedy algorithm is used to find some gray nodes adjacent to at least 2 black nodes in different black-blue components. The performance of S-MIS is (5.8+ln 4)opt+1.2.

The MIS based algorithms mainly have two kinds of realization. The first one is the two phase based realization, which constructs a MIS at first and then find some optimal nodes to connect the MIS nodes together. The second one is the one phase based realization, which selects the MIS nodes and the optimal intermediate nodes simultaneously. The optimal nodes selection is based on some criterions such as node degree, residual energy of node and node id, etc.

The MIS based algorithms such as Das and Bharghavan (1997), Raei et al. (2008, 2009), Rai et al. (2009), Zeng et al. (2006), Funke et al. (2006), Yingchang et al. (2009) and Dai and Wu (2004) are mainly have two stages. The first stage is constructing a MIS and the second stage is finding some connectors to connect the nodes in MIS and finally get a CDS. The CDS construction algorithms can have different criterions. The criterion is the node degree (Das and Bharghavan, 1997; Raei et al., 2008; Rai et al., 2009). For example, the node degree is the number of the unmarked neighbors in the first stage and in the second stage, the node degree is the number of unmarked nodes adjacent to the non-fragment nodes (Das and Bharghavan, 1997). The algorithm has the performance ratio 2H(Δ)+1 (Das and Bharghavan, 1997). The time and message complexities are O((n+|C|)Δ) and O(n|C|+m+n log n), respectively. The criterion for constructing a CDS is a timer, which is based on the transmission ranges of nodes (Raei et al., 2009). The criterion is the weight of node and the weight is composed of the node degree and the battery power. The criterion is the node id (Funke et al., 2006; Yingchang et al., 2009). The node with the largest id will become a dominator (Funke et al., 2006), while the node with the smallest id will become a dominator (Yingchang et al., 2009).

Many algorithms are MIS based. There are also some non-MIS based algorithms (Dai and Wu, 2004; Rong et al., 2009).

Wu and Li (1999) and Dai and Wu (2004) proposed some distributed algorithms in UDG and DGB. A very simple marking process is proposed by Wu and Li (1999). In the marking process every node v exchanges its open neighbor set N(v) with its neighbors and if there exist two unconnected neighbors, v will mark itself. All the marked nodes form a CDS. The CDS constructed in the first phase contains many redundant nodes. Wu and Li (1999) proposed two prune algorithms called Rule-1 and 2 to delete some redundant marked nodes. The performance ratio is not given by Wu and Li (1999), but by Wan et al. (2002) the performance ratio of this algorithm is proved O(n), where n is the number of nodes. The message complexity is Θ(m), where m is the number of edges in the unit-disk graph. The time complexity is O(Δ³), where Δ is the maximum degree. Dai and Wu (2004) proposed an extended algorithm for the algorithm. The marking process is the same as that by Wu and Li (1999), but the pruning process is improved and denoted by Rule-k. Based on the Rule-k, the size of the final constructed CDS is reduced. A hierarchical graph is constructed at first and then the essential nodes are determinate in the graph according to the Rule 1 (Rong et al., 2009). After the essential nodes determination phase is ended, there are some redundant dominators, which are deleted according to the Rule-2 in (Rong et al., 2009). The performance ratio of the algorithm is O(log n) (Rong et al., 2009).

Centralized algorithm and decentralized algorithm:
Algorithms that construct a CDS can be divided into two categories: centralized algorithms and decentralized algorithm.

Centralized algorithms:
The centralized algorithms in general yield a smaller CDS with a better performance ratio than that of decentralized algorithm. Guha and Khuller (1998) proposed two polynomial time algorithms to construct a CDS in general graph G. These algorithms are greedy and centralized. The first one has the approximation ratio of 2(H(Δ)+1) where Δ is the maximum degree of G and H is a harmonic function. The idea of this algorithm is to build a spanning tree T rooted at the nodes with maximum degree and grow T until all nodes are added to T. The non-leaf nodes in T form a CDS. In particular, all nodes in a given network are white initially. The greedy function that the algorithm uses to add nodes into T is the number of the white neighbors of each node or a pair of nodes. The one with the largest such number is marked black and its neighbors are marked grey. These nodes are then added into T. The algorithm stops when no white node exists in G. The second algorithm is an improvement of the first one. This algorithm consists of two phases. The first phase is to construct a dominating set and the second phase is to connect the dominating set using a Steinter tree algorithm. With such improved, the second algorithm has the performance factor of H(Δ)+2. These algorithms later were studied and implemented by Das et al. (1997), Das and Bharghavan (1997) and Sivakumar et al. (1998). Ruan et al. (2004) introduced another centralized and greedy algorithm of which the approximation ratio is (2+ln Δ).

Decentralized algorithms:
The decentralized algorithms can be further divided into two categories: distributed algorithms and localized algorithms. In distributed algorithm, the decision process is decentralized. In the localized algorithm, the decision process is not only distributed but also requires only a constant number of communication rounds. Most of the distributed algorithm find a MIS and connect this set. Note that in an undirected graph, an MIS is also a Dominating Set (DS). Wan et al. (2002) and Alzoubi et al. (2002a) proposed a distributed algorithm for a CDS problem in UDG. This algorithm consists two phases and has the constant approximation ratio of 8. The algorithm first constructs a spanning tree. Then each node in a tree is examined to find an MIS for the first phase. All nodes in an MIS are colored black. At the second phase, more nodes are added (color blue) to connect the black nodes. Later, Cadei et al. (2002) presented another 2-phase distributed algorithm for a CDS in UDG. This algorithm has the same performance ratio as the previous one. However, the improvement over (Wan et al., 2002) is the message complexity. The root does not need to wait for the complete message from the furthest nodes. Recently, Li et al. (2005) proposed another distributed algorithm with a better approximation ratio, which is (4.8+ln 5). This algorithm also has two phases. At the first phase, an MIS is found. At the second phase, a Steiner tree algorithm is used to connect the MIS.

For the localized algorithms, Wu and Li (1999) proposed a simple algorithm that can quickly determine a CDS based on the connectivity information within the 2-hops neighbors. This approach uses a marking process. In particular, each node is marked true if it has two unconnected neighbors. All the marked nodes form a CDS. The researchers also introduced some dominant pruning rules to reduce the size of the CDS. Wan et al. (2002) showed that the performance ratio of Wu and Li (1999) is within a factor of O(n) where n is the number of nodes in a network. Taxonomy of CDS construction algorithm is shown in Fig. 5.


Fig. 5:	Taxonomy of CDS construction algorithm

Alzoubi et al. (2002b) proposed another localized 2-phase algorithms with the performance ratio of 192. At the first phase, an MIS is constructed using the 2-hops neighbors information. Specifically, once a node knows that it has the smallest ID within its neighbors, it becomes a dominator. At the second phase, the dominators are responsible for identifying a path to connect the MIS. Li et al. (2004) proposed another localized algorithm with the performance ratio of 172. This localized algorithm has only 1 phase. A node marks itself as a dominator if it can cover the most white nodes compared to its 2-hops neighbors.

CDS CONSTRUCTION ALGORITHMS FOR WSNs

Generally, WSNs involve a large number of sensors ranging in the hundreds or even thousands. The CDS construction is an effective mean for managing such high population of nodes. Here, we present a literature survey of published algorithms for constructing CDS in WSN. Following the increased interest in wireless sensor networks, many distributed approaches have been proposed because of no requirements for global network topology knowledge.

Distributed approximation algorithms for MCDS in WSN were first developed in a series of papers (Das and Bharghavan, 1997; Sivakumar et al., 1998). These algorithms provided distributed implementations of the greedy heuristics (Guha and Khuller, 1998). The CDS is referred to in these papers as a spine and functions as a virtual backbone. The primary task of the spine is the route computation and maintenance. Nodes in the spine maintain up to date information about their domains (neighbors of the CDS nodes) and are used to exchange such information between each other to store global information of the network. The advantage of this strategy is the storage of global information in fewer nodes than the num number of nodes in the network, which reduces the access overhead for this information and reduces the update overhead. According to this strategy, it is highly desirable to reduce the size of the CDS in order to minimize the access and update overhead. The spine is not necessarily used to route packets in the network, even though it can be used to provide a temporary backup routes for fault tolerance.

We notice that these algorithms lack mechanisms to bridge two consecutive stages. Specifically, individual nodes have no way to tell when the next stage should begin. Furthermore, these approximation algorithms suffer from high performance ratio and high implementation complexities, O(n) time and messages. The construction of the minimum CDS requires 2-hop neighborhood knowledge, which means larger message size, frequent updates, slower convergence speed and more memory.

Alzoubi et al. (2002c) proposed two famous distributed heuristics algorithms: (1) ID-based approach for CDS and (2) level-based approach for CDS.

ID-based approach:
The construction of the CDS uses the MIS generated by the ID-Based approach for rank assignment. A variation of this algorithm was proposed by Alzoubi et al. (2002b), but the level-based approach was used for rank assignment. Thus, the performance ratio was 8 instead of 12. Here, the distributed algorithm for CDS consists of three procedures

•	Leader Election
•	MIS construction
•	Dominating tree construction

The leader election procedure elects a node e.g., with the smallest ID, as the leader. The distributed algorithm in (Cidon and Mokryn, 1998) for leader election can be adopted. This algorithm has a message complexity of O(n log n). When the leader is found, it broadcasts its identity to all the nodes in the network.

When a node receives the leader’s identity, it starts the MIS construction procedure, which is described earlier and using the ID-based approach for rank assignment. Each node will either be colored with black (as a dominator) or gray (as a dominatee). The leader will also select a black node as the root of the dominating tree as follows: If the leader is marked black, it selects itself as the root of the tree, otherwise it selects one of the black neighbors to be the root.

The dominating tree construction procedure is initiated by the root to construct a tree containing all black nodes in addition to some gray nodes. All nodes in this dominating tree form a CDS. The root joins the dominating tree first, then it sends an invitation message to all black nodes within 3-hop distance to join the tree. When a node receives an invitation message and all its neighbors have been marked either black or gray, it responds to the message. When each black node joins the dominating tree, it will also send an invitation to all black nodes within 3-hop distance to join the tree. This invitation will be relayed through the gray nodes within 2-hops distance. Each black node will join the tree when it receives the invitation for the first time together with the gray nodes which relays the invitation to itself. This process should be repeated until all black nodes are in the tree.

Result:
All nodes in the dominating tree form a CDS with size at most 12opt+3. In addition, the algorithm has O(n log n) message complexity and O(n) time complexity.

Level-based approach:
The construction of the CDS uses the MIS generated by the level-based approach for rank assignment. This algorithm can be divided into three phases: The leader election phase, the level calculation phase and the color marking phase. The distributed algorithm for leader election can be adopted by Cidon and Mokryn (1998). This algorithm has O(n log n) message complexity and O(n) time complexity. After the construction of the spanning tree is completed and when the root receives level-complete messages from all its children, each node knows the level numbers of all its neighbors. The pair (level, ID) of a node defines the rank of this node. The ranks of all nodes are sorted in the lexicographic order. Thus the leader, which is at level 0, has the lowest rank. In the color marking phase all nodes are initially unmarked (white) and will eventually get marked either black or gray. Two types of messages are used by the nodes during this phase, the dominator message and the dominatee message. The dominator message is sent by a node after it marks itself black and the dominatee message is sent by a node after it marks itself gray. Both messages contain the sender’s ID. The algorithm can be described as a color markup process. Initially, the root marks itself black and then broadcasts to its neighbors a dominator message. All other nodes act according to the following principles.

•	Whenever a white node receives a dominator message from a white neighbor for the first time, it marks itself gray and broadcasts the dominatee message


Fig. 6:	State transition diagram

•	When a white node has received a dominatee message from each of its neighbors of lower rank, it marks itself black and broadcasts the dominator message
•	When a gray node receives a dominator message for the first time from one of its children in T, which has never sent a dominatee message, it remarks itself black and broadcasts the dominator message

Figure 6 shows the state transition diagram of this phase. Eventually each node will be either black (a dominator) or gray (dominatee). A reporting process, if necessary, can be performed to notify the root of the completion. When a leaf node has determined its status, it transmits a report complete message to its parent. Each internal node will wait till it receives this report complete message from each of its children and then forward it up the tree to the root. When the root receives the report complete message from all its children then the tree is completed.

Result:
All nodes form a CDS with size at most 8opt+1. In addition, the message complexity of the algorithm is O(n log n) and the time complexity is O(n).

Das et al.’s algorithm:
The centralized version of the distributed algorithm proposed by Das et al. (1997) consists of three stages. The first stage finds an approximation to minimum dominating set, which is essentially the well-studied set cover problem. Not surprisingly, the heuristic proposed by Das et al. (1997), Bharghavan and Das (1999), Das and Bharghavan (1997) and Sivakumar et al. (1998) is a translation of Chvatal’s greedy algorithm (Chvátal, 1979) for set cover and thus guarantees an approximation factor of H(Δ), where Δ is the maximum degree and H is the harmonic function. Let U denote the dominating set output in this stage. The second stage constructs a spanning forest F. Each tree component in F is a union of stars centered at the nodes in U.


Fig. 7:	Instance for which the size of solution output by Das et al.’s algorithm

The stars are generated by letting each dominatee node pick up an arbitrary neighbor in U. The third stage expands the spanning forest F to a spanning tree T. All internal nodes in T form a CDS. It is easy to show that the CDS generated in this way contains at most 3|U| nodes and therefore is a 3H(Δ) approximation of minimum CDS.

Figure 7 shows a family of instances for which the size of the solution computed by the above greedy algorithms is larger than the optimum solution by a logarithm factor. All points lie in a rectangle whose horizontal side has length one and whose vertical side has length (the selection of the value is based on the fact for any two points whose y-coordinates are differed by , they are connected if and only if their x-coordinates are differed by at most 1/(2(k–1)). The two nodes v₁ and v_k are the centers of the left and right vertical sides, respectively. The k–2 nodes v₂, v₃,...,v_k–1 are evenly distributed within the line segment between and from left to right. The two nodes u₁ and u₂ are the centers of the two sub-rectangles above and below the segment between v₁ and v_k, respectively. The rest points lie in the two horizontal sides. In each horizontal side, 2⁰ = 1 node lies to the left of (and excluding) the perpendicular bisector of v₁v₂, 2^k–1 nodes lie to the right of the perpendicular bisector of v_k–1v_k and 2^i–1 nodes lie between the perpendicular bisector of v_i–1v_i and the perpendicular bisector of v_iv_i+1. Thus, the total number of nodes is:

where, u₁ is adjacent to all nodes lying in the top subrectangle, u₂ is adjacent to all nodes lying in the bottom subrectangle and they are adjacent to each other. Thus, {u₁, u₂} forms a minimum CDS.

Result:
All nodes form a CDS with size at most 3H(Δ). In addition, the message complexity of the algorithm is O(n²) and the time complexity is O(n²).

Wu and Li’s algorithm:
While the algorithm proposed by Das et al. first finds a DS and then grow this DS into a CDS, the algorithm proposed by Wu and Li (1999) takes an opposite approach. The algorithm in Wu and Li (1999) first finds a CDS and then prune certain redundant nodes from the CDS. The initial CDS U consists of all nodes which have at least two non-adjacent neighbors. A node u in U is considered as locally redundant if it has either a neighbor in U with larger ID which dominates all other neighbors of u or two adjacent neighbors with larger IDs which together dominate all other neighbors of u. The algorithm then removes all locally redundant nodes from U. This algorithm applies only to wireless ad hoc networks whose unit-disk graph is not a complete graph. As indicated by Wu and Li (1999), the approximation factor of this algorithm remains unspecified. Obviously, the MCDS of any wireless ad hoc network whose unit-disk graph is not complete graph consists of at least two nodes. On the other hand, any CDS contains at most n nodes. Thus, the approximation factor of the above algorithm is at most n/2 where n is the number of nodes. Next, we show that the approximation factor of the above algorithm is exactly n/2. This means that the above algorithm does perform extremely poorly over certain instances.

When n is even, we consider the instance illustrated in Fig. 8a. These nodes are evenly distributed over the two horizontal sides of a unit-square. Each node has exactly m neighbors, one in the opposite horizontal side and the rest in the same horizontal side. The two nodes at the left two corners of the unit-square form an minimum CDS. However, the CDS output by the algorithm in (Wu and Li, 1999) consists of all nodes. Indeed, for each node u, the unique neighbor lying in the opposite horizontal side is not adjacent to all other neighbors of u. Thus, the initial CDS U consists of all nodes. In addition, no single neighbor of a node u can dominate all other neighbors of u. Furthermore, if a pair of neighbors of u is adjacent, they must lie in the same horizontal side as u and therefore neither of them is adjacent to the unique neighbor of u lying in the opposite horizontal side. So, no node is locally redundant. Consequently the output CDS still consists of all nodes.


Fig. 8:	Instance for which the CDS output by Wu and Li’s algorithm

When n is odd, we consider the instance illustrated in Fig. 8b. The node with the largest ID, denoted by u*, is the center of the left vertical side of a unit-square and all other n–1 nodes are evenly distributed over the two horizontal sides of the unit-square. The two nodes at the left two corners of the unit-square form a minimum CDS. On the other hand, the CDS output by the algorithm by Wu and Li (1999) also consists of all nodes. In fact, following the same argument as in the even case, all nodes other than u* are in the initial CDS U. The node u* is also in the initial CDS U as well. Since, u* is not adjacent to the two nodes at the right corners of the unit-square, all nodes other than u* are not locally redundant. The u* itself is also not locally redundant as it has the maximum ID. Therefore, the output CDS still consists of all nodes.

Result:
All nodes form a CDS with size at most n/2. In addition, the message complexity of the algorithm is Θ(m) and the time complexity is o(Δ³).

Stojmenovic et al.’s algorithm:
In the context of clustering and broadcasting, Stojmenovic et al. (2001) presented three synchronized distributed constructions of CDS. In each of the three constructions, the CDS consists of two types of nodes: the cluster-heads and the border-nodes. The cluster-heads form a Maximal Independent Set (MIS), i.e., a dominating set in which any pair nodes are nonadjacent. A node is a border-node if it is not a cluster-head and there are at least two cluster-heads within its 2-hop neighborhood. The set of cluster-heads is induced by a ranking of nodes which give rise to a total ordering of all nodes. Three rankings are used: the ID only (Gerla et al., 1995; Lin and Gerla, 1997), an ordered pair of degree and ID (Chen and Stojmenovic, 1999) and an order pair of degree and location (Stojmenovic et al., 2001). The selection of the cluster-heads is given by a synchronized distributed algorithm, which can be generalized to the following framework.

Initially all nodes are colored white. In each stage of the synchronized distributed algorithm, all white nodes which have the lowest rank among all white neighbors are colored black; then all white nodes adjacent to the these black nodes are colored gray; finally the ranks of the remaining white nodes are updated. The algorithm ends when all nodes are colored either black or gray. All black nodes then form the cluster-heads.

Regardless of the choice of the ranking, the algorithms by Stojmenovic et al. (2001) have a Θ(n) approximation factor. Such inefficiency stems from the non-selective inclusion of all order-nodes. In fact, if the rank is ID only, Fig. 9 shows a family of instances which would imply the approximation factor to be exactly n, the worst possible. In these instances, the node with the largest ID is located at the center of a unit-disk and all other nodes are evenly distributed in the boundary of the unit-disk. After the cluster-heads are selected, all other nodes become border-nodes. Thus the CDS would consist of all nodes. On the other hand, the node at the center dominates all other nodes. If the rank is an ordered pair of degree and ID or an order pair of degree and location, the instances shown in Fig. 8 imply that their approximation factors are at least n/2.

All algorithms by Stojmenovic et al. (2001) have o(n²) message complexity and Ω(n) time complexity. This can be illustrated in the following instance: All n nodes are evenly distributed in an interval of length n±1 with two nodes being the endpoints of the interval. The ith node from the left endpoint of interval has ID i.

Result:
All nodes form a CDS with size at most n. In addition, the message complexity of the algorithm is O(n²) and the time complexity is Ω(n).


Fig. 9:	Instance for which the CDS output by Stojmenovic et al.’s algorithm

Zhuo Liu et al.’s algorithm:
Liu et al. (2010a, b) proposed a good performance CDS construction algorithm with small size for WSNs. The algorithm has three stages. The first stage is constructing a connected set CS (connected set) and the second stage is constructing a connected dominating set CDS and the third stage is pruning the redundant dominators of CDS.

We compare the size of CDS constructed by ATISA with four algorithms: Wu’s algorithm (Wu and Li, 1999) (denoted by WUA), Wang’s algorithm (Wan et al., 2002) (denoted by WAA), the first algorithm of Xiang’s algorithms by Yingchang et al. (2009) (denoted by XA) and the first algorithm of Thai’s algorithms by Thai et al. (2007) (denoted by TFA) (Fig. 10).

Result:
All nodes form a CDS with size at most (9.67+19n_k)opt. In addition, the message complexity of the algorithm is O(n) and the time complexity is O(n).

Table 1:	Performance comparison


Fig. 10:	The size of the CDS

We have surveyed some famous CDS construction algorithms. Performance comparison of more algorithms is shown in Table 1.

CONCLUSIONS

The CDS have proven to be an effective construct within which to solve a variety of problems that arise in wireless networks. Significant attention has been paid to CDS construction algorithms yielding a large number of publications. In this study, we surveyed and classified the CDS construction algorithms and classified.

As WSN moves from the research labs to the real world, additional requirements will certainly arise. Issues that will likely arise include the security and survivability of CDS-based applications. In infrastructure-based wireless networks, the infrastructure plays a key role for security purposes. A perimeter is established around the infrastructure, regulating access to the network. A CDS could perform similar actions through forming a virtual network infrastructure. However, significant issues must first be addressed including the real-time assurance of the trust worthiness of mobile hosts. Similarly, performance of the CDS construction algorithms in the face of security attacks must be evaluated in order to ensure robust, survivable network functionality.

ACKNOWLEDGMENTS

This study is supported by two grants from the National Natural Science Foundation of China (No. 60773190, No. 60802002)