无线网络中最小权虚拟骨干网连通 部分的新方法.

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]