A Distributed Algorithm for Connecting Dominating Sets in Wireless Ad Hoc Networks

The virtual backbone is an approach for solving routing problems in wireless ad hoc networks. Recently, a connected dominating set (CDS) has been proposed as a virtual backbone to improve the performance of wireless networks. The quality of a virtual backbone is measured not only by approximation factor, which is the ratio of its size to that of minimum CDS, but also time complexity and message complexity. In this paper, we present a distributed algorithm to construct a minimum CDS (MCDS) for ad hoc networks. By destroying triangular loops in the virtual backbone, the proposed algorithm can effectively construct a CDS with smaller size. Moreover, our algorithm, which is fully localized, has a constant approximation ratio, linear message and time complexity, and low implementation complexity. Simulation results and theoretical analysis show that our algorithm has better efficiency and performance than conventional approaches