Connected Dominating Set Construction And Maintenance Of WSN

Wireless sensor network (WSN) is a large-scale, wireless, multi-hop，self-organizing network without infrastructure support. Since WSN has these properties,It is possible to build up a WSN at any time and any place quickly, in which sensornodes not only have the function of collecting data, but also finish communication task,even undertake routing sometimes. WSN is widely used in military affairs, nationaldefense, environmental monitoring, health care, smart home, disaster survived and so on,as it has these characteristics mentioned above. As a widely used route method, theflooding technology easily leads to the forwarding of redundant packets, channelcontention, conflict of communication and other serious broadcast storm problems,when these are no limited means. To solve this problem effectively, virtual backbonebased on the theory of connected dominating set (CDS) has been proposed. By usingvirtual backbone, messages are transferred from source node to destination nodethrough virtual backbone. This manner restricts most of routing and forwardingactivities occurred in virtual backbone network. As a result, the energy consuming isdecreased observably and lifetime of whole network is prolonged obviously.Started from topology optimization for large-scale WSN, in which homogenousnodes are random distributed, this paper proposed an energy-balanced minimumconnected dominating set constructing algorithm (named EB-MCDS) based on thetheory of CDS and with the idea of virtual backbone network. EB-MCDS considers thefactors of the size of CDS, the residual energy and degree of nodes comprehensively.This algorithm is a heuristic algorithm based on the information of neighbour. Itcarefully weighed the residual energy and degree of nodes, when selecting dominators.In EB-MCDS, a dominator Dafirstly collects information of nodes within2hops, thanelects the node, which is its2hops neighbour and has the maxim weight value in its2hops neighbour set, as a dominator Db, at last it will select a node belonging to itsneighbour and Db’s neighbour simultaneously and having the maxim weight value inthis set as a dominator Dc. The new dominator repeats above process until the networkhas converged. By considering the residual energy and degree of nodes, EB-MCDSconstructs an energy-balance minimum connected dominating set. In addition, a strategy for maintaining CDS is presented. This maintenance strategy discusses maintainingmethods in four different cases:(1) there are dominators in its neighbour after a newnode joined network;(2) there are no dominators in its neighbour after a new nodejoined network;(3) dominatee withdraws from network;(4) dominator withdraws fromnetwork.The experiment results and performance analysis show that the constructionalgorithm and maintenance strategy of connected dominating set reduce and balance thenetwork energy consumption, and increase the message throughput rate of dominators,and prolong the life cycle of network effectively.