计算机工程与应用 ›› 2012, Vol. 48 ›› Issue (5): 102-106.

• 网络、通信、安全 • 上一篇    下一篇

无线ad hoc网络中定向连通控制集的局部构造算法

王楠楠,禹继国,李桂青   

  1. 曲阜师范大学 计算机科学学院,山东 日照 276826
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2012-02-11 发布日期:2012-02-11

Local algorithm for constructing directional connected dominating sets in wireless ad hoc networks

WANG Nannan, YU Jiguo, LI Guiqing   

  1. School of Computer Science, Qufu Normal University, Rizhao, Shandong 276826, China
  • Received:1900-01-01 Revised:1900-01-01 Online:2012-02-11 Published:2012-02-11

摘要: 在无线ad hoc网络中采用定向天线模型寻找定向连通控制集(DCDS)是构造虚拟骨干网的有效方法。由于求解最小DCDS问题是NPC的。提出了一种在无线ad hoc网络中构造DCDS的局部启发式算法。该算法同时选择转发节点和转发边,极大地减少了时间开销,时间和信息复杂度分别为O(1)和O(n)。理论分析和仿真实验都证明该算法具有良好的性能。

关键词: 无线ad hoc网络, 定向天线模型, 定向虚拟骨干网, 定向连通控制集, 局部算法

Abstract: Constructing a Directional Connected Dominating Set(DCDS) using a directional antenna model is an effective method to find a directional network backbone in wireless ad hoc networks. Because finding a minimum DCDS is NP-Complete, this paper develops a locally heuristic algorithm for constructing a DCDS in wireless ad hoc networks. This algorithm selects the forward nodes and forward edges at the same time, greatly reducing the time overhead. The time complexity is O(1)and the message complexity is O(n). Theoretical analysis and simulation show that the algorithm has a good performance.

Key words: wireless ad hoc network, directional antenna model, directional virtual backbone network, Directional Connected Dominating Set(DCDS), local algorithm