Research On Virtual Backbone Approximation Algorithm Base On Connected Dominating Set In Wireless Sensor Network

Wireless Sensor Network(WSN) are composed of a large number ofwireless sensor nodes through self-organization forming a large-scale networksystem, which can make use of sensor to real-time collect useful information ina specific area. The information acquired by sensors is transmitted to the sinknode with multi-hop manner by WSN in order to realize the target’s surveillanceand tracking. As it has these characteristics mentioned above, WSN is widelyused in many key areas, such as military affairs, disaster survived, smart homeand so on.On WSN, on the one hand, broadcast operation usually uses the floodingtechnology which is likely to bring the broadcast storm problem when these areno limited means. On the other hand the sensor nodes have very limited power.For the above, virtual backbone based on the theory of connected dominating set(CDS) has been proposed by researchers. Only backbone nodes do responsiblefor forwarding data, and those non-backbone nodes can close thecommunication module to save energy when they do not need to work. It willnot only reduce the routing overhead, balanced energy consumption, but alsocan improve the broadcast efficiency, enhance self-organization in the wirelesssensor network.The thesis started from topology optimization for large-scale WSN, inwhich homogenous nodes are random distributed, proposed a reference energycentralized algorithm for minimum connected dominating set（MCDS-EC）based on the theory of CDS. MCDS-EC considers the factors of the residual energy and degree of nodes comprehensively. MCDS-EC algorithm defines areasonable weight formula, and established the vertex order table according tothe weight value of each node. It omits the widely used process of structuring atree in the centralized algorithm. The time complexity of MCDS-EC algorithmis O(n3). Simulation results show that connected dominating set generated bythe energy consumption, compared with the algorithms in the relative literatures.In addition, the paper also proposes an energy-balanced minimumconnected dominating set distributed algorithm (MCDS-ED). MCDS-EDalgorithm is an algorithm based on neighbor information, which needs to knowthe2-hops nodes’ information. Since the communication distance is directlyrelated to the node energy consumption, when set weight parameters for thenode, MCDS-ED considers not only the residual energy and degree of nodes,but also the average distance between nodes and its neighbor nodes. At the sametime, in order to further balance the network energy consumption, MCDS-EDalgorithm set energy monitors for each node. The node will exit the virtualbackbone network if the node energy below the threshold, and the algorithmwill search for new backbone nodes. The time complexity and messagecomplexity of MCDS-ED algorithm are O(△2) and O(n△),△is the maximumdegree of a node in the graph G,The feasibility and good effect of the algorithmare proved in theory.