Research On Construction Of Connected Dominating Sets In Wireless Sensor Networks

Wireless Sensor Networks (WSNs) are composed of a large number of sensor nodesthrough wireless communication, multi-hop transmission and self-organization forming alarge-scale network system. In real life, wireless sensor networks are widely used inBattlefield Detection, Smart Home, Management Automation and many other fields.Wireless sensor networks have so many advantages in the aspect of application thatthey become hot research direction for many scholars and institutions. As we know thesensor node has small size, low energy supply, limited computing, little storage capacityand other characteristics, and it is generally located in places that humans can notarrive(it can not be artificially replace the battery). Therefore, how to efficiently usenode’s energy to maximize the network life has became a hot topic. The ConnectedDominating Set (CDS) servering as a virtual backbone of wireless sensor networks has agood performance on the efficiently use of node’s energy.In this paper, in order to solve the problem that wireless sensor network has no fixedinfrastructure and node energy consumption is not balanced, we propose a distributedalgorithm to construct a CDS taking the residual energy of nodes and the scale of CDSinto account. We prove the correctness of the algorithm theoretically and simulationresults show the superiority of the algorithm over other existing distributed algorithms interms of the CDS size, residual energy and network life. In addition, in order to solvefrequent reconstructing of the connected dominating set caused by the node energydepletion or link failures, this paper also proposes a distributed algorithm for CDS withfault-tolerance, that is constructing a k-Connected m-Dominated Set (kmCDS), alsodefined as (k, m)-CDS. This algorithm takes the residual energy of network nodes,kmCDS size and other factors into consideration, and we prove the correctnesstheoretically. In addition, it can be seen in the simulation that our algorithm is superior to other existing distributed algorithms in terms of the kmCDS size and the averageremaining energy of kmCDS’s node. Thus, kmCDS can work longer in WSNs, therebyreducing the energy consumption due to the construction of connected dominating setfrequently. Therefore, our algorithm can make the network life longer.