The Research On Constructing Virtual Backbone In Wireless Sensor Network

In this paper, we considered several combinatorial optimization problems related to virtual backbone construction of the network. Due to its extensive applications in various filed, wireless sensor network (WSN) have been received as a premier and hot research topic in recently years. In WSN, there is no fixed or pre-defined infrastructure and the nodes need to carry other nodes’traffic and are vulnerable to fail. It is desire to consider a fault tolerant virtual backbone to make sure that many sensors monitor the same data and the data reports via different paths. A virtual backbone network was proposed to reduce the broadcast storm caused by flooding in WSN. The nodes on the backbone are responsible for routing and control of the whole network. It deeply reduces the redundancy of information, save the energy consumption, improves the performance of the whole network.We mainly studied the two types of problems in this paper, We firstly consider the minimum m-connected k-totally dominating problem for general m and k, we proposed an approximation algorithm with better approximation ratio. Secondly, we consider minimum connected r-hop k-dominating set problem in general disk graph. We proposed a two stage approximation algorithm. In the first stage, we use3-color algorithm to obtain a minimal r-hop dominating set. In the second stage, a new nodes in it step by step to form a connected r-hop k-dominating set. At last the performance ratio of the algorithm is proposed.The main contribute is to generalize related virtual backbone network construction problem, and then design corresponding approximation algorithm with better performance ratio.