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

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