Research On Fault-Tolerant Virtual Backbones Of Wireless Sensor Networks

Wireless sensor networks have many small,cheap and battery-powered wireless sensors.Wireless sensor networks have no predefined infrastructure,so the network topology of wireless sensor networks often changes dynamically.The power of communication between wireless sensors in the network is provided by batteries,which makes energy saving becomes one important focus of the research.In order to stabilize the topology of the network and save the energy of the communication,the researchers proposed the concept of the virtual backbone.For the sake of convenience,a wireless sensor network is usually modeled as a unit disk graph and the virtual backbone of the network is abstracted as the connected dominating set in the corresponding unit disk graph.In this paper,we mainly study the construction problem of the multi-connected virtual backbone with somedegree of fault-tolerance under the corresponding mathematical model in respect to the studied network.The communication between wireless sensor nodes is based on flood routing.In order to solve the information redundancy caused by flood routing,the clustering method is introduced.Meanwhile,to improve the fault-tolerant ability of wireless sensor networks,the method of enhance connectivity is also proposed.Based on above two points,it introduces a3-connected r-hops dominating set with the same transmission radius in the plane,a strong connected d-hops dominating set with different transmission radius and a 1-connected m-dominating set in the threedimensional space.Through theoretical analysis and make full use of geometric knowledge,the size of above connected dominating sets are(?),(?)and(?),respectively,where*U represents the optimal 3-connected dominating set in unit disk graphs,r,d represent hops between two nodes,k represents the transmission ratio of networks.In the end of this paper,simulation results demonstrate proposed algorithms are effective and meets the expectation.