| A Distributed Virtual Backbone Formation for Wireless Ad Hoc and Sensor Networks |
| |
| 作者姓名： | 曹涌涛 何晨 蒋铃鸽 |
| |
| 作者单位： | Dept.of Electronic Eng. Shanghai Jiaotong Univ.，Dept.of Electronic Eng.，Shanghai Jiaotong Univ.，Dept.of Electronic Eng.，Shanghai Jiaotong Univ.，Shanghai 200240 China，Shanghai 200240 China，Shanghai 200240 China |
| |
| 摘 要： | 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.
|
| 关 键 词： | 虚拟中枢 无限传感器网络 连接系 方法 |
| 文章编号： | 1007-1172（2007）01-0023-06 |
| 修稿时间： | 2006-03-29 |
A Distributed Virtual Backbone Formation for Wireless Ad Hoc and Sensor Networks |
| |
| CAO Yong-tao,HE Chen,JIANG Ling-ge.A Distributed Virtual Backbone Formation for Wireless Ad Hoc and Sensor Networks[J].Journal of Shanghai Jiaotong university,2007,12(1):23-28,34. |
| |
| Authors: | CAO Yong-tao HE Chen JIANG Ling-ge |
| |
| Institution: | Dept. of Electronic Eng. , Shanghai Jiaotong Univ. , Shanghai 200240, China |
| |
| Abstract: | 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. |
| |
| Keywords: | virtual backbone connected dominating sets(CDS) wireless sensor networks |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
