An Approximation Algorithm for Constructing a 2-Connected k-Dominating Virtual Backbone in Wireless Ad Hoc Networks

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 to construct a fault-tolerant virtual backbone with a k-connected k-dominating set,and evaluated the performance of their algorithms via simulations.Feng Wang et al.have designed an approximation algorithm to construct a 2-connected fault-tolerant virtual backbone in wireless ad hoc networks.In this paper,a constant ratio approximation algorithm is designed to find a 2-connected k-dominating virtual backbone.