Research On The Construction Of Virtual Backbone In Heterogeneous Wireless Network

In wireless network,the size of virtual backbone is an important factor to measure the quality of a network,the smaller the virtual backbone is,the less the network routing overhead is.Therefore,in the research,the problem of constructing minimum virtual backbone problem is often abstracted as the problem of solving minimum connected dominating set in graph theory.Solving the minimum connected dominating set has been proved to be an NP-hard problem,which can generally be solved by designing an approximation algorithm,and a key parameter that determines the approximation ratio is the upper bound of the maximal independent set.Furthermore,since each sensor node in a homogeneous wireless network has the same transmission range,which is clearly not consistent with the most situations in reality,so the research of heterogeneous wireless networks with different transmission range have practical significance.In allusion to the problems mentioned above,two aspects of unit ball graph and directed graph of virtual backbone network of wireless network are deeply studied in this paper.The innovation of research on the following three aspects:(1)Under the unit ball graph model,the upper bound of the maximal independent set is optimized to 10.5385,and an approximate algorithm is proposed in this paper,the approximate ratio of the connected dominating set generated by the algorithm is 12.5385 + 7)9)11;(2)Under the directed graph model,this paper extends the geometric method in the study of the virtual backbone network of the threedimensional homogeneous wireless network to the research of the threedimensional heterogeneous wireless network,and proposes a strongly connected dominating and absorbing set construction algorithm;(3)This paper further expands the research on virtual backbone network of heterogeneous wireless network with routing guarantee,and proposes two strongly connected dominating and absorbing set construction algorithms with routing guarantee.In addition,the feasibility of the proposed algorithms is verified by simulation experiments.At the same time,the experimental results show that the proposed algorithms have better performance than the existing algorithms in other literatures.