Research On Virtual Backbone Network Algorithms For Wireless Sensor Networks Based On Graph Theory

Since the wireless sensor network has unique advantages, it has a wide range of applications in the military and civilian areas. Currently, the wireless sensor network is being paid more and more attention on, so many researches relevant to the wireless sensor network are becoming academic hot spots, where the virtual backbone network which is a network routing base has become a hot research topic. Since the sensor node is subject to strict constraints in battery power, storage space and computing speed and so on, the design of algorithms related to the wireless sensor network should be integrated to consider these constraints.This paper studied virtual backbone network algorithms for wireless sensor networks based on graph theory from three aspects of energy efficiency, load balancing, and network fault tolerance, main works include:(1) For the problem of the too large construction cost of the centralized virtual backbone network algorithm and the too large backbone network scale of the distributed virtual backbone network algorithm, this paper brings forward a virtual backbone network construction algorithm based on the connected dominating set. The algorithm uses the connected dominating set theory of graph theory to construct a virtual backbone network at low cost, and uses pruning rules to reduce the size of the virtual backbone network. The algorithm considers energy and distance of the node to make the life of the virtual backbone network longer. The theoretical analysis demonstrates that the maximum size of virtual backbone network in the homogeneous sensor network environment, message and time complexity of the algorithm. The simulation analysis shows that the algorithm is better than other algorithms in the size of the backbone network, the total number of messages and the total energy consumption.(2) For the problem of the premature failure of the backbone nodes which need forward and integrate data than the non-backbone nodes because of excessive energy consumption, this paper brings forward a multiple virtual backbone rotation algorithm based on the connected domatic partition. The algorithm uses the connected domatic partition theory of graph theory to construct a number of virtual backbone networks which have no public nodes, and makes them commit the task of forwarding and integrating data in accordance with the rotation cycle in order to reach the purpose of balancing the node load. The theoretical analysis demonstrates that the minimum number of virtual backbone networks in the homogeneous sensor network environment, message and time complexity of the algorithm. The simulation analysis shows that the algorithm is better than other algorithms in the average size of the backbone network, the total number of backbone networks and the network lifetime.(3) For the lack of the virtual backbone network restoration algorithm in the heterogeneous sensor network environment, this paper brings forward a heterogeneous virtual backbone network restoration algorithm based on the connected dominating tree. The algorithm uses the connected dominating tree theory of graph theory to construct a heterogeneous virtual backbone network in the heterogeneous sensor network environment. When the failed node causes that the virtual backbone network can not connect and cover other nodes, the algorithm will partially restore the virtual backbone network to come back its connectivity and coverage. The theoretical analysis demonstrates that the maximum size of the initial virtual backbone network, the maximum number of nodes which fix the virtual backbone network, message and time complexity of the algorithm. The simulation analysis shows that the algorithm is better than other algorithms in the size of the backbone network, the total number of messages and the network lifetime.Although this paper studied the virtual backbone network algorithm of the wireless sensor network and acquired some productions, there are still some unsolved problems which need further study in future work.