A Distributed Virtual Backbone Formation for Wireless Ad Hoc and Sensor Networks  

作　　者：曹涌涛 何晨 蒋铃鸽 

机构地区：[1]Dept.of Electronic Eng.,Shanghai Jiaotong Univ.

出　　处：《Journal of Shanghai Jiaotong university(Science)》2007年第1期23-28,34,共7页上海交通大学学报（英文版）

基　　金：The National Natural Science Foundation ofChina(No.60272082);The Important Science and Technology Key Item of Shanghai(No.05dzl5004)

摘　　要：The virtual backbone is an approach for solving routing problems in wireless ad hoc and sensor networks. A connected dominating set (CDS) was 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, a distributed algorithm is presented to construct a minimum CDS for ad hoc and sensor 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. The simulation results and theoretical analysis show that our algorithm has better efficiency and performance than conventional approaches.The virtual backbone is an approach for solving routing problems in wireless ad hoc and sensor networks. A connected dominating set （CDS） was 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, a distributed algorithm is presented to construct a minimum CDS for ad hoc and sensor 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. The simulation results and theoretical analysis show that our algorithm has better efficiency and performance than conventional approaches.

关 键 词：virtual backbone connected dominating sets（CDS） wireless sensor networks 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]