Search

The virtual backbone (VB) in wireless networks is a subset of some wireless nodes, such that only VB nodes are responsible for routing related tasks. The smaller the weight of VB, the less the overhead. In a node-weighted wireless network, not only the number of nodes in VB should be considered, but also the total weight should be considered. Frequently, a weighted wireless network is modeled as a node-weighted unit disk graph ( UDG) . Correspondingly, the minimum-weighted VB problem in the weighted wireless network is abstracted as the minimum-weighted connected dominating set ( MWCDS) problem in the node-weighted UDG. Finding MWCDS is a NP-hard problem. To reduce the approximate ratio of the connected part of the MW CDS problem in node-weighted UDG, this paper proposed a new method-degree-based node-weighted Steiner tree algorithm in the connected part. Combining the best results at present, it will obtain a ( 3. 32 + s ) -approximation algorithm for MWCDS problem in UDG. Similarly, it will also obtain a ( 3. 3 2 + s) -approximation algorithm for MWCVC problem in UDG. It is proved that the method of reducing the approximate ratio of the MWCDS problem in node-weighted UDG is feasible by improving the approximate ratio of connected parts. [ABSTRACT FROM AUTHOR]

A virtual backbone of wireless sensor networks is a subset of nodes and only virtual backbone nodes are responsible for routing-related tasks. The smaller a virtual backbone is, the less the network overhead, the size of a virtual backbone is the key factor to measure the quality of the vi11ual backbone. Frequently, the unit disk graph is used to model a wireless sensor network. In a wireless sensor network, the problem of finding the minimum virtual backbone is abstracted to the problem of finding the minimum connected dominating set in the unit disk graph corresponding to the wireless network. However, the problem of finding the minimum connected dominating set in the unit disk graph is a NP-hard problem, many works contribute to obtain the approximation algorithm of the minimum connected dominating set rather than finding the minimum connected dominating set in the unit disk graph. Constructing a 3-connected r-hop dominating set in wireless sensor networks is an effective means to obtain a connected dominating set with a smaller size such that can reduce the total amount of information forwarded between any nodes, which is a better approximation for finding the minimum virtual backbone. This paper proposed an algorithm to construct a 3-connected r-hop dominating set in wireless sensor network. It shows that the size of a 3-connected r-hop dominating set produced by the algorithm is no more than 5 (2r + 2β + 1) (r + 1) β| U' I - 10(2 + β) (r + 1) - 5r - 12. At the end, it analyzed the performance of the proposed algorithm by experiment simulation, and the experimental results are consistent with what expected. [ABSTRACT FROM AUTHOR]