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

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

作　　者：王楠楠[1] 禹继国[1] 李桂青[1] 

机构地区：[1]曲阜师范大学计算机科学学院,山东日照276826

出　　处：《计算机工程与应用》2012年第5期102-106,共5页Computer Engineering and Applications

基　　金：国家自然科学基金(No.10471078);山东省自然科学基金(No.ZR2009GM2009;ZR2009AM013);山东省高校科技计划(No.J10LG09)

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

分 类 号：TP393.01[自动化与计算机技术—计算机应用技术]