A Greedy Algorithm on Constructing the Minimum Connected Dominating Set in Wireless Network

Abstract

In the past 20 years, the connected dominating set (CDS) as a virtual backbone network has been widely used in the wireless networks. Many researchers have been devoted to designing approximate algorithms for CDS problem since constructing the minimum CDS (MCDS) is NP-hard problem. Different from the most existing algorithms with two phases, we employ greedy strategy to design a centralized algorithm GR_CDS in only one phase to get MCDS, with the time complexity of $O(({\mathrm{\Delta }}^{\mathrm{2}}+\log n)n)$ . Afterwards, another algorithm P_CDS is designed for pruning redundant nodes in the obtained MCDS with the time complexity of $O(n^{\mathrm{2}})$ .

1. Introduction

Wireless networks are widely used in many fields [1] such as environment monitoring, disaster forecast, battlefield detection, traffic control, and disease diagnosis. In recent years, CDS as the virtual backbone network in wireless ad hoc and wireless sensor networks (WSNs) has attracted more and more attention of researchers, since the CDS can prolong the lifetime of the wireless network, optimize the energy consumption, transfer data fast, and so forth. Further, how to minimize the size of the CDS is a significant research direction.

In wireless networks, each node can only communicate with neighbors and its computing capacity is finite. Therefore, the nodes need to cooperate with each other to complete an overall task. If a node wants to transfer information to other nodes outside of the transmitting range (i.e., the destination has multiple hops away from it), a backbone network is needed to transmit the messages effectively. Once the backbone network is constructed, all nodes can communicate with other nonneighbor nodes through intermediate nodes in the backbone network. Therefore, the nodes that are not in the backbone network can sleep intermittently or shut off for saving energy consumption.

It was verified that CDS is an optimal selection as a backbone network for transferring messages [2, 3]. In wireless networks, CDS as a virtual backbone network was first proposed [4]. Beyond that, CDS has many practical applications such as topology control [5], routing [6], and broadcasting [7]. In addition to the size of CDS, our goal is to design an optimization algorithm for considering other algorithm performance indexes such as CDS size, throughput size, time complexity, and message complexity.

In this paper, assume that the algorithm is executed in wireless network and the nodes are deployed on a two-dimensional plane. The topology of the network is modeled with a unit disk graph (UDG) $G=(V,E)$ , where V represents the set of nodes in the network and E represents the collection of the network link. And assume that each node $v\in V$ has a unique $id$ and its maximum transmission range is R. In addition, if node u is in the maximum transmission range of node v, we think that there is an undirected link between u and v, which is the undirected edge between u and v on graph G. Let $N(v)$ be the neighbor set of node v and let $d_v=|N(v)|$ be the degree of node v. And let $\Delta =\max \left\{d_v\mid v\in V\right\}$ be the maximum degree of the graph.

Let $G=(V,E)$ be the original network topology and DS $V^{\prime }$ is a subset of set V in graph G. For arbitrary node $v\in V$ , if node v is not in set $V^{\prime }$ , there is at least a neighbor node of v in set $V^{\prime }$ . For any two nodes $u,v\in V^{\prime }$ , if there exists a path that can make them connected by other intermediate nodes which belongs to set $V^{\prime }$ , then we denote set $V^{\prime }$ as CDS. We just need to store the routing information into the nodes in the CDS, which can route messages as soon as quickly. It is clear that the smaller the size of the CDS is, the faster the messages are transmitted and the less the energy consumption of the node is. Therefore, it is important to construct the minimum CDS (MCDS). Unfortunately, it was proved that the MCDS problem was NP-complete [8]. Hence, most of researchers have been devoted to designing approximate algorithm for constructing the MCDS.

In this paper, we propose a greedy centralized GR_CDS algorithm with the time complexity of $O(({\Delta }^{\mathrm{2}}+\log n)n)$ . Afterwards, we put forward an algorithm P_CDS to prune redundant nodes in CDS with the time complexity of $O(n^{\mathrm{2}})$ , which can remove all of the redundant nodes from the obtained CDS eventually.

2. Related Work

2.1. Related Network Model and Notations

In order to minimize the size of CDS, we devoted to designing approximate algorithm to obtain CDS by the approximation factor $\left|\mathrm{o}\mathrm{p}\mathrm{t}\right|$ , which is as little as possible. In many cases, however, we need to consider the other performance parameters such as the diameter of CDS, communication consumption of nodes.

As a critical performance index, the size of CDS has attracted more attention of researchers. For constructing CDS as virtual backbone networks in wireless network, Guha and Khuller [9] proposed two heuristic centralized algorithms. The fist algorithm firstly put up all nodes are transformed into white. And the white node with the maximum number of neighbors is selected to be colored black, and all its white neighbors are marked gray. Finally, they formed CDS by all black nodes. The approximation ratio of the algorithm is $\mathrm{2}(\mathrm{1}+H(\Delta ))$ . The second algorithm is divided into two phases. The first stage is to delete redundant nodes of graph as many as possible. The second phase is to build a Steiner tree for constructing CDS. And it was proved that the approximation ratio is $\ln \Delta +\mathrm{3}$ . Afterwards, two distributed versions of algorithms in [10, 11] were proposed by Das et al. Then Wu and Li proposed a distributed algorithm [12] to construct a CDS based on two-hop information of neighbors. For arbitrary node in the network, it is added to CDS if there are two nonadjacent neighbors, and all redundant nodes are moved from the network. When topology of network contains complete subgraphs, however, the algorithm cannot execute successfully. In [13], Wan et al. proved that the approximation ratio of [12] is $O(n)$ , and they proved that the approximation ratio of any MIS is $\mathrm{4}\left|\mathrm{o}\mathrm{p}\mathrm{t}\right|+\mathrm{1}$ in the unit disk graph (i.e., $\mathrm{M}\mathrm{I}\mathrm{S}(G)=\mathrm{4}\left|\mathrm{o}\mathrm{p}\mathrm{t}\right|+\mathrm{1}$ ), where $\mathrm{o}\mathrm{p}\mathrm{t}$ is the optimal set of CDS. Afterwards, they proposed a distributed algorithm to construct CDS in unit disk graph. In the first phase, they constructed a spanning tree and obtained $\mathrm{M}\mathrm{I}\mathrm{S}$ with the method of searching nodes layer by layer. Later, they constructed a dominating tree whose internal nodes can consist of CDS with performance ratio $\mathrm{8}\left|\mathrm{o}\mathrm{p}\mathrm{t}\right|-\mathrm{2}$ and the time complexity and message complexity of $O(n)$ , respectively, where opt is the size of optimal solution of CDS and n is the number of nodes in the network. In [14], Funke et al. proved that the approximation ratio of MIS is $\mathrm{3.453}\left|\mathrm{o}\mathrm{p}\mathrm{t}\right|+\mathrm{8.292}$ by analyzing the coverage area of nodes, and they got CDS with the approximation ratio of 6.9. In [15] and [16], Li et al. and Das et al., respectively, proposed different distributed algorithm of approximation ratio $\left(\mathrm{4.8}+\ln \mathrm{5}\right)\left|\mathrm{o}\mathrm{p}\mathrm{t}\right|+\mathrm{1.2}$ . All of these algorithms first construct $\mathrm{M}\mathrm{I}\mathrm{S}$ and then obtain CDS by connecting the $\mathrm{M}\mathrm{I}\mathrm{S}$ nodes through some connectors.

Except the size of CDS, communication consumption of nodes is also an important performance index. It not only involves the energy consumption but also contains the time consumption in communication cost, which are related to the number of hops. Then reducing the number of hops is the most effective way to increase the transmission range. However, the battery power of nodes in backbone requires higher volume. So more and more researchers have been devoted to studying the routing efficient CDS [17–20]. At the same time, the works about minimizing the diameter of CDS are gradually being taken seriously. An algorithm [21] is proposed for constructing CDS with the small diameter, which guaranteed that not only is the diameter of acquired CDS limited to $\mathrm{3}{D}^{\ast }+\mathrm{7}$ (where $D^{\ast }$ is the diameter of the MCDS), but also the size of CDS is limited to $\mathrm{11.4}\left|\mathrm{o}\mathrm{p}\mathrm{t}\right|+\mathrm{1.6}$ . Additionally, some other research facets such as k-connected m-dominating set [22], weakly-dominating set [23], and k-hop [24] have also attracted much attention by researchers.

3. Algorithm GR_CDS

In this section, we propose a greedy centralized GR_CDS algorithm with time complexity of $O(({\Delta }^{\mathrm{2}}+\log n)n)$ for constructing MCDS. The pseudocode of the algorithm is described as algorithm GR_CDS (Greedy Redundant Connected Dominating Set).

In this paper, three states of a node are represented by colors white, black, and gray. Initially, all nodes are remarked white, also called initial state. A global parameter count (its initial value is n, i.e., the number of nodes) is a parameter that is to record the current number of white nodes. We first choose node v with the maximum degree among all neighbors as the initial node of the CDS and it turns into black and all of its neighbors are colored gray. Irrespective of the color of node v, the value of the parameter count substracts 1. And for any node $w\in N(v)$ , node v is removed from set $N(w)$ ; that is, $N(w)=N(w)\setminus v$ . Then all the nodes in $N(w)$ are white. As long as the value of count is greater than 0, each time we select gray node v that has the largest number of white neighbor nodes among all gray nodes as a new node in the CDS and it is marked black and all its white neighbors turn into gray. When two or more gray nodes have the same number of white neighbors and the number of adjacent white nodes is more than others, we choose the biggest one as a new element of CDS. The operations are performed iteratively until all nodes are colored to either black or gray.

The result description of constructing operation of CDS is shown in Figure 1 with executing algorithm GR_CDS (Algorithm 1). At first, node 6 is colored black because it has the maximum degree among all neighbor nodes. Then, nodes 1, 3, 7, 8, and 9 are colored gray since they are neighbors of node 6. Afterward, node 8 is colored black since it has the largest number of white neighbors among all gray nodes. As well, its white neighbors 4 and 5 are colored gray. By the same token, nodes 5 and 4 are colored black.

Algorithm 1: Algorithm GR_CDS.

Input: $G(V,E)$

Output: CDS

( $\mathit{1}$ )  $count=n$ ;

( $\mathit{2}$ ) Select a node $v\in V$ with the maximum degree among all nodes in $N(v)\cup v$ ;

( $\mathit{3}$ )  ${Color}_v=black$ ;

( $\mathit{4}$ )  $count=count-\mathrm{1}$ ;

( $\mathit{5}$ ) For each node $w\in N(v)$

( $\mathit{6}$ )    $N(w)=N(w)\setminus v$ ;

( $\mathit{7}$ ) End for

( $\mathit{8}$ ) For each node $u\in N(v)$

( $\mathit{9}$ )    ${Color}_u=gray$ ;

     $count=count-\mathrm{1}$

( $\mathit{10}$ ) End for

( $\mathit{11}$ ) For each gray node u

    For each gray node $w\in N(u)$

      $N(w)=N(w)\setminus u$

    End for

( $\mathit{12}$ ) End for

( $\mathit{13}$ ) While $count>\mathrm{0}$ do

( $\mathit{14}$ )  Select a gray node v with the largest number of white neighbors among all gray nodes;

( $\mathit{15}$ )    ${Color}_v=black$ ;

( $\mathit{16}$ )    $count=count-\mathrm{1}$ ;

( $\mathit{17}$ )  For each node $u\in N(v)$

( $\mathit{18}$ )    ${Color}_u=gray$ ;

( $\mathit{19}$ )    $count=count-\mathrm{1}$ ;

( $\mathit{20}$ )  End for

( $\mathit{21}$ )  For each gray node u

( $\mathit{22}$ )   For each gray node $w\in N(u)$

( $\mathit{23}$ )     $N(w)=N(w)\setminus u$ ;

( $\mathit{24}$ )   End for

( $\mathit{25}$ )  End for

( $\mathit{26}$ ) End while

( $\mathit{27}$ ) For all nodes in V

( $\mathit{28}$ )  If ${Color}_v=black$ then

( $\mathit{29}$ )    $\mathrm{C}\mathrm{D}\mathrm{S}=\mathrm{C}\mathrm{D}\mathrm{S}\cup \left\{v\right\}$

( $\mathit{30}$ )  End if

( $\mathit{31}$ ) End for

Figure 1

Example showing CDS construction.

Lemma 1.

CDS is a correct connected dominating set.

Proof.

Let us use deduction to prove that set CDS is a connected dominating set. Assume that $\mathrm{C}\mathrm{D}\mathrm{S}=\{v_{\mathrm{1}},v_{\mathrm{2}},v_{\mathrm{3}}\cdots v_{\mathrm{c}\mathrm{d}\mathrm{s}}\}$ and node $v_i\in \mathrm{C}\mathrm{D}\mathrm{S}$ cannot connect with other nodes in the CDS, where cds is the number of nodes in CDS. Then node $v_i$ is colored black and all its neighbors are colored gray. According to the algorithm, when node $v_i$ is white, there must exist one of gray nodes at least has one white neighbor; that is, the value of count is not 0. Therefore, one of its neighbors must become black, which means that each black node has a path to connect other nodes in CDS. The result conflicts with the hypothetic premises. If CDS is divided into two parts, there must exist two local sets CDS _i and CDS _j such that there are at most three hops between node $v_i\in \mathrm{C}\mathrm{D}{\mathrm{S}}_i$ and node $v_j\in \mathrm{C}\mathrm{D}{\mathrm{S}}_j$ .

Theorem 2.

The time complexity of the algorithm is $O(({\Delta }^{\mathrm{2}}+\log n)n)$ .

Proof.

Firstly, a node is selected which has the maximum node degree as the beginning of the algorithm and the time of ordering all the nodes needs $O(\log n)$ . Secondly, for each neighbor node, the operation time of deleting the colored neighbor nodes requires $O({\Delta }^{\mathrm{2}})$ . Thirdly, due to the initial value of $count$   n, the execution time of the while loop is n. Fourthly, in the interior of the cycle, we define gray node v with the largest number of white neighbors as a new node in the CDS; thus the time required for sorting all gray nodes is $O(\log n)$ . At last, for each neighbor node, when node v is changed into black, the operation time of deleting the colored neighbor nodes requires $O(\log n)$ . As a result, the time complexity of constructing the CDS is $O(({\Delta }^{\mathrm{2}}+\log n)n)$ .

4. Algorithm P_CDS

In this section, we design algorithm P_CDS (Pruning for CDS) with time complexity which is $O(n^{\mathrm{2}})$ to delete the redundant nodes from the obtained CDS with algorithm GR_CDS, aiming at making the CDS smaller.

The pseudocode of the algorithm is shown in algorithm P_CDS (Algorithm 2). Firstly, it is a preparation of making a judge on each node $v\in \mathrm{C}\mathrm{D}\mathrm{S}$ . Node v is colored gray if all its gray neighbor nodes are connected with other black nodes, and there is still a linked path between all its black nodes when the node v is deleted. In this way, some redundant black nodes can be removed from the CDS, and the rest of the CDS is denoted as CCDS (Concise CDS). After executing the algorithm P_CDS, the final CCDS is shown in Figure 1(f).

Algorithm 2: Algorithm P_CDS.

( $\mathit{1}$ ) Input: $G(V,E)$

( $\mathit{2}$ ) Output: CCDS

( $\mathit{3}$ ) CCDS = CDS

( $\mathit{4}$ ) For each node $v\in \mathrm{C}\mathrm{C}\mathrm{D}\mathrm{S}$

( $\mathit{5}$ )   If each node $u\in N(v)$ such that node u is black or u has another black neighbor in CCDS, then

( $\mathit{6}$ )    Delete v from CCDS;

( $\mathit{7}$ )    If any two black neighbors of node v has a path by nodes in CCDS, then

( $\mathit{8}$ )      ${Color}_v=gray$

( $\mathit{9}$ )    Else

( $\mathit{10}$ )      $\mathrm{C}\mathrm{C}\mathrm{D}\mathrm{S}=\mathrm{C}\mathrm{C}\mathrm{D}\mathrm{S}\cup \left\{v\right\}$

( $\mathit{11}$ )    End if

( $\mathit{12}$ )   End if

( $\mathit{13}$ ) End for

Lemma 3.

Set CCDS is a correct CDS.

Proof.

As proof in by Lemma 1, set $\mathrm{C}\mathrm{C}\mathrm{D}\mathrm{S}$ is a CDS. According to the algorithm, when all the neighbor nodes of node $v\in \mathrm{C}\mathrm{C}\mathrm{D}\mathrm{S}$ are connected with $\mathrm{C}\mathrm{C}\mathrm{D}\mathrm{S}\setminus \left\{v\right\}$ , either node v is the cut point which is connecting two black nodes or it becomes the redundant black nodes, since node v must be adjacent to the black nodes at least. After deleting node v, if there is still an adjacent path between any two black nodes, node v is not the cut point. That is, v is the redundant node. So the set CCDS is a correct CDS.

Theorem 4.

The time complexity of the algorithm P_CDS is $O(n^{\mathrm{2}})$ .

Proof.

As the number of nodes in the set $\mathrm{C}\mathrm{C}\mathrm{D}\mathrm{S}$ is less than $n/(\Delta +\mathrm{1})$ . So the number of nodes in $\mathrm{C}\mathrm{C}\mathrm{D}\mathrm{S}$ is less than or equal to $n/(\Delta +\mathrm{1})$ . For each node $v\in \mathrm{C}\mathrm{C}\mathrm{D}\mathrm{S}$ , it needs to judge whether all the neighbor nodes connect with other nodes in $\mathrm{C}\mathrm{C}\mathrm{D}\mathrm{S}$ . The convenient way is to judge the biggest degree of the network Δ. After deleting node v from the $\mathrm{C}\mathrm{C}\mathrm{D}\mathrm{S}$ , the operation of judging whether the set $\mathrm{C}\mathrm{C}\mathrm{D}\mathrm{S}\setminus v$ is connected needs the time of $O\left(n\right)$ . Therefore, the time complexity of the algorithm P_CDS is $O(n^{\mathrm{2}})=O(n\ast \Delta +n\ast n)$ .

5. Conclusion

Traditionally, most existing algorithms have two phases. The first phase is to construct maximal independent set (MIS) as dominating set (DS). The second is to construct a Steiner tree for connecting nodes in DS through adding to connectors. In this paper, a new algorithm GR_CDS with greedy strategy is proposed to get a relatively optimal size of the CDS, and the time complexity of the algorithm is $O(({\Delta }^{\mathrm{2}}+\log n)n)$ . Further, an algorithm P_CDS is developed to make the CDS smaller, with the time complexity of $O(n^{\mathrm{2}})$ . It reduces the size of the CDS algorithm effectively, sacrificing some performance of time.