关键词: 2-连通是一支配集 近似算法 无线自组织网络 虚拟主干网

Abstract:

Some nodes are often chosen to form a virtual backbone in wireless ad hoc networks in order to support routing and other tasks such as area monitoring. Because of the inherent node （link） failures in wireless networks, virtual backbones should be fault-tolerant. Recently,researchers have suggested t   to construct a fault-tolerant virtual backbone with a kconnected k-dominating set, and evaluated the performance of their algorithms via simulations. Fe ng Wang et al. have designed an approximation algorithm to construct a 2-connected fault-tolerant virtual backbone in wireless ad hoe networks. In this   paper,a constant ratio approximation algorithm is designed to find a 2-connected k-dominating virtual backbone.

Key words: 2-connected k-dominating set, approximation algorithm, wireless ad hoc network, virtual backbone