首页 | 本学科首页   官方微博 | 高级检索  
     


Zone-based virtual backbone formation in wireless ad hoc networks
Authors:Bo Han
Affiliation:1. School of Computer and Information Engineering, Chuzhou University, Anhui 239000, PR China;2. School of Electronics and Information Engineering, Beijing Jiaotong University, Beijing, 100044, PR China;3. School of Computer Science and Technology, Tianjin University, Tianjin, 300072, PR China;4. School of Systems Information Science, Future University Hakodate, 116-2, Kameda Nakano-Cho, Hakodate, Hokkaido, 041-8655, Japan
Abstract:Efficient protocol for clustering and backbone formation is one of the most important issues in wireless ad hoc networks. Connected dominating set (CDS) formation is a promising approach for constructing virtual backbone. However, finding the minimum CDS in an arbitrary graph is a NP-Hard problem. In this paper, we present a novel zone-based distributed algorithm for CDS formation in wireless ad hoc networks. In this Zone algorithm, we combine the zone and level concepts to sparsify the CDS constructed by previous well-known approaches. Therefore, this proposed algorithm can significantly reduce the CDS size. Particularly, we partition the wireless network into different zones, construct a dominating tree for each zone and connect adjacent zones by inserting additional connectors into the final CDS (at the zone borders). Our comprehensive simulation study using a custom simulator shows that this zone-based algorithm is more effective than previous approaches. The number of nodes in the CDS formed by this Zone algorithm is up to around 66% less than that constructed by others. Moreover, we also compare the performance of Zone algorithm with some recently proposed CDS formation protocols in ns2 simulator.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号