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

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

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