Research On The Construction Of High Quality Virtual Backbone In Wireless Sensor Networks

In wireless sensor networks,by constructing virtual backbone and using it to undertake the routing task of the whole network,the possibility of signal conflict and interference in communication between nodes can be greatly reduced,and then the broadcast storm problem can be effectively alleviated,the stability of the network can be improved,and the life of the network can be prolonged.The size of virtual backbone is an important index to measure its performance,and the smaller the virtual backbone,the better.However,in addition to size,the virtual backbone should contain some other characteristics,such as fault tolerance or guaranteed routing cost.Compared with the general virtual backbone that only considers the basic communication function,the virtual backbone with fault tolerance or other characteristics has better performance.This paper calls this kind of virtual backbone with other excellent characteristics as high quality virtual backbone.This paper studies the construction problem of three types of high quality virtual backbones,and the research results are as follows:The first one is the virtual backbone with guaranteed routing cost in homogeneous wireless sensor networks.This paper proposed an approximation algorithm:RCC-CDS,whose approximation ratio is 142.758.For any input connected unit disk graph G=(V,E),the algorithm RCC-CDS can output a connected dominating set D such that for any pair of nodes u,v ?V,the length of the shortest path between them satisfies l(u,v)? 4lD(u,v),where lD(u,v)is the length of the shortest path that all nodes except u and v are in D.The second one is the virtual backbone with bounded diameter in homogeneous wireless sensor networks.This paper proposed an approximation algorithm:BD-CDS,whose approximate ratio is 13.596,and the diameter of its output connected dominating set is not more than 8/3 Diam(OPT)+14/3,where Diam(OPT)represents the diameter of any minimum connected dominating set.The third one is the virtual backbone with fault tolerance in heterogeneous wireless sensor networks.This paper proposed an approximate algorithm for constructing rigorous(1,m)-strongly connected dominating and absorbent set and an approximate algorithm for constructing(k,m)-strongly connected dominating and absorbent set(m? k? 2).The approximation ratio of these two algorithm is(m+4)(?/m+1)and(2k(5^k-1-1)+1)(?+m+4(?/m 1)),respectively,where ? is the maximum number of independent nodes within the signal transmission range of any node.The simulation results verify the correctness of the algorithms proposed by this paper,and show that the performance of these proposed algorithms are better than the corresponding existing algorithms.