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

摘要

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