Data collection is one of the most important operations in wireless sensor networks. Currently, many researches focus on using a connected dominating set to construct a virtual backbone for data collection in WSNs. Most researchers concentrate on how to construct a minimum connected dominating set because a small virtual backbone incurs less maintenance. Unfortunately, computing a minimum size CDS is NP-hard, and the minimum connected dominating sets may result in unbalanced energy consumption among nodes. In this paper, we investigate the problem of constructing an energy-balanced CDS to effectively preserve the energy of nodes in order to extend the network lifetime in data collection. An energy-balanced connected dominating set scheme named DGA-EBCDS is proposed, and each node in the network can effectively transmit its data to the sink through the virtual backbone. When constructing the virtual backbone in DGA-EBCDS, we prioritize selecting those nodes with higher energy and larger degree. This method makes the energy consumption among nodes more balanced. Furthermore, the routing decision in DGA-EBCDS considers both the path length and the remaining energy of nodes in the path; it further prolongs the lifetime of nodes in the backbone. Our conclusions are verified by extensive simulation results. 13], which means that the data sensed by nodes should be transmitted to the sink for further processing. How to conserve the limited energy of nodes and extend the lifetime of the network is an important issue in data collection [14, 15] . The network lifetime is usually defined as the duration of the network until the first node depletes its energy. So, the network lifetime effectively ends with the first node death (FND). Due to incomplete data, the remaining energy in the surviving nodes is of no use after FND. In order to effectively extend the lifetime of a WSN (delay the death of the first node), many algorithms construct a virtual backbone of the 2 International Journal of Distributed Sensor Networks network and only use the nodes in the virtual backbone to receive and transmit data for data collection. Nodes that are not in the backbone can go to sleep mode periodically to conserve the limited energy. Because of the number of nodes in the virtual backbone is relatively small, the impact of the broadcast storm problem can be greatly reduced, and the routing path search space can also be limited to the nodes that are in the set of the backbone. So, the virtual backbone can bring several benefits to network management. Connected dominating set (CDS) plays an important role in the construction of virtual backbone in wireless sensor networks [16] . A dominating set (DS) of a network is a subset of all its nodes, which makes every node out of the set adjacent to at least one node in the set. A dominating set is called a connected dominating set when the nodes in the dominating set can form a connected graph. A CDS can be used as a virtual backbone to help each node transfer its data to the sink. Many researches focus on finding the minimum connected dominating set (MCDS) to construct the network virtual backbone [10] . However, MCDS-based algorithms may result in too much energy consumption of nodes in the backbone, and may cause unbalanced energy consumption among all the nodes, which will shorten the network lifetime and narrow their applications. Motivated by the above problem, an energy-balanced connected dominating set scheme (DGA-EBCDS) is proposed in this paper, which well balances energy consumption among nodes that are in the backbone and consequently prolongs the lifetime of the network. In DGA-EBCDS, we prioritize selecting nodes that have higher energy and larger degree to form the backbone. By transmitting data through the backbone with small routing cost, each node can preserve its energy effectively. Moreover, the nodes in the virtual backbone would not die quickly because of their high energy level. The proposed algorithm creates a small-size connected dominating set, which performs well in energy saving and efficiently affords more numbers of rounds in data collection. The main contributions of this paper are summarized as follows. First, we introduce the concept of energy-balanced connected dominating set in Section 3. Using this scheme, DGA-EBCDS can well balance energy consumption among nodes and consequently prolong the lifetime of the network. Second, we theoretically analyze DGA-EBCDS algorithm in Section 4. Theoretical analyses prove that the set of the dominators is a maximal independent set (MIS) when the first stage for DGA-EBCDS terminates and the message complexity of DGA-EBCDS is ( log ). Third, we support our algorithm analysis with extensive simulations in Section 5. Compared with another dominating set-based algorithm mr-CDS [17], the average energy consumption of DGA-EBCDS is reduced by 33.3% in the formation of CDS, and the network lifetime is prolonged by 57.8%. The rest of the paper is organized as follows. In Section 2, we briefly introduce the related work. Section 3 presents the system model and problem statement. In Section 4, we describe and analyze the proposed DGA-EBCDS protocol in detail. The simulation results and corresponding discussions are given in Section 5. Finally, Section 6 concludes the paper and presents the further research work.
Kui et al., REF proposed an energy-balanced connected dominating set scheme (DGA-EBCDS) for data collection in wireless sensor networks.
Constructing a CDS-Based Network Backbone for Data Collection in Wireless Sensor Networks
International Journal of Distributed Sensor Networks
Computer Science