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

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

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

王楠楠，禹继国，李桂青

曲阜师范大学计算机科学学院，山东日照 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

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

摘要/Abstract

摘要： 在无线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

王楠楠，禹继国，李桂青. 无线ad hoc网络中定向连通控制集的局部构造算法[J]. 计算机工程与应用, 2012, 48(5): 102-106.

WANG Nannan, YU Jiguo, LI Guiqing. Local algorithm for constructing directional connected dominating sets in wireless ad hoc networks[J]. Computer Engineering and Applications, 2012, 48(5): 102-106.

[1]	刘立军1，2，花丽1，周爱平1. 认知无线Ad Hoc网络干扰约束和能量高效路由算法[J]. 计算机工程与应用, 2017, 53(17): 112-116.
[2]	龚媛媛. 一种基于域的无线Ad HOC网络入侵检测系统[J]. 计算机工程与应用, 2012, 48(28): 123-126.
[3]	吴翠萍，蔡明. AODV路由协议的改进[J]. 计算机工程与应用, 2012, 48(24): 91-94.
[4]	刘占军,侯维娜,李云,陈前斌. 无线Ad hoc网络中的丢包分析模型研究[J]. 计算机工程与应用, 2009, 45(9): 108-109.
[5]	杨清^1,2,李方敏¹. 移动Ad Hoc网络联合路由入侵检测模型研究[J]. 计算机工程与应用, 2009, 45(13): 114-118.