Algorithms And Applications For Virtual Backbone Network In Wireless Sensor Networks

Wireless sensor networks has a wide range of applications in the health care, military and civilian areas because of the unique advantages it has. Since the wireless sensor networks has harsh energy constraint, energy conservation has been becom-ing a major topic of research and the most important challenge in wireless sensor networks. First of all, we proposed a virtual backbone network algorithm, which is energy-efficient, fault-tolerant and load balancing. Secondly, the nodes in the virtual backbone network consume so much extra overheads, such as processing and forward-ing data information, such that these nodes die earlier than the other nodes in the networks. Aiming at this kind of problem, we proposed a sleeping scheduling algo-rithm based on virtual backbone network. The energy can load balancing by using this approach. At last, the purposed of wireless sensor networks is collecting data in the monitoring area. The performance of data collection can be greatly improved by using virtual backbone network. Main works include in the paper:(1) In this paper, we have developed an algorithm for constructing 2-connected R-hop K-dominating virtual backbone using R-hop maximal independent set, which can be used many times to construct K-dominating sets. The dominating sets become connected by adding connecting nodes. Finally, expanding the R-hop connected K-dominating sets to 2-connected. Not only ensure the dominating sets fault tolerance (2-connected), but also ensure dominated nodes fault tolerance (K-dominating). The complexity, approximation ratio and performance of the algorithm were given through theoretical analysis and simulations.(2) For the problem of the earlier die of the nodes in backbones, which need for-ward and integrate data than the non-backbone nodes because of consuming so much extra overheads, we proposed a multiple virtual backbone rotation algorithm based Connected Domatic Partition(CDP). This algorithm uses the connected domatic par-tition theory of graph theory to construct a several of virtual backbone networks, and makes them undertake the task of forwarding and integrating data in terms of the rotation cycle in order to achieve the purpose of load balancing of the node. The scale of virtual backbone networks, the number of rotation virtual backbone networks and the lifetime of networks were given through simulations.(3) The non-backbone nodes transmit the data of the monitoring area to back-bone nodes nearby. After received the data, the backbone nodes integrate the received data into coding data by using network coding, and transmit it to user through the virtual backbone networks. Network coding can improved the network throughput and reduced energy consumption. Simulation shows that the collection rate can be improved by using network coding and virtual backbone networks relative to the con-ventional data collection.