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.
Cao Yongtao He Chen Wang Jun Zheng Chunlei
Dept. of Electronics Engineering Shanghai Jiao Tong Univ. Shanghai, China Inst. of Communication Engineering Nanjing Univ. of Posts and Telecommunications Nanjing, China Shanghai Inst. of Microsystem and Information System Shanghai, China
国际会议
2006 International Conference on Communications,Circuits and Systems(第四届国际通信、电路与系统学术会议)
广西桂林
英文
1472-1476
2006-06-25（万方平台首次上网日期，不代表论文的发表时间）