一种改进的邻节点发现算法

李经安徐志平

（1中国电子科技集团公司第五十四研究所，河北石家庄 050081）

（2中国人民解放军96275部队，河南洛阳 471003）

一种改进的邻节点发现算法

李经安1徐志平2

（1中国电子科技集团公司第五十四研究所，河北石家庄 050081）

（2中国人民解放军96275部队，河南洛阳 471003）

邻节点发现是无线Ad Hoc网络自组织过程中的关键步骤之一，邻节点发现效率的高低直接影响着网络的性能。以定向天线模式下的无线Ad Hoc网络为研究对象，对邻居发现问题进行深入探讨，通过归纳和总结现有邻节点发现算法的实现机理，找出现有邻节点算法的不足，适当改进算法，针对定向天线，提出一种采用慢扫描时多次发送Hello数据包的方案，并对算法进行了仿真，验证了邻节点发现算法的合理性且完全符合预期结果。

无线自组网 邻节点发现 定向天线 波束扫描

1 引言

当今，由于移动通信、无线网络和因特网技术的高速发展，当前信息领域的研究方向便转向了如何更好的运用通信及网络技术为人们提供便利的服务。无线网络自身具有灵活性和方便性等特点，这些特点引起了研究者的关注，它的应用范围也得到了扩展。

邻节点发现是无线网络初始化过程中的关键步骤之一，有效的邻节点发现算法对于大部分的基于无线网络的MAC协议、路由算法和拓扑控制算法是必不可少的[1]，邻节点发现算法的效率的高低是网络性能的制约。以定向天线模式下的无线Ad Hoc网络为研究对象，讨论现有邻节点算法存在的不足，并提出一种改进的邻节点算法。

2 定向天线的Ad Hoc邻节点发现算法

2.1 定向邻节点发现(DND)算法

邻节点发现在采用全向天线的Ad Hoc网络中是一件简单的事情，但是在采用定向天线的Ad Hoc网络中，并不如此。由于定向天线在一段时间内只能向某个扇区中发射信号，而在这段时间中只有恰好在定向天线覆盖区域内的邻节点才能收到信号，其他收不到信号的邻节点，也就不可能被发现。同样，当邻节点收到信号向源节点回复信息时，只有天线对准源节点，才能收到回复。为了将定向天线运用于Ad Hoc网络，对定向邻节点发现(DND)机制及算法进行了研究。

从物理信道的区别，DND主要分为2种工作模式：定向发射模式TD和定向发射定向接收模式TRD[2,3]。TD模式下，定向天线用于发射，全向天线用于接收，而TRD模式下，收发都用定向天线，但收发扫描速度和方向性是不一样的。从对其他信息的依赖性方面区分，DND分为辅助DND和非辅助DND。顾名思义，辅助DND需要借助定位系统或其他设施的辅助，而非辅助DND的实现过程具有很强的独立性，不需要其他信息辅助。

在军事领域中，战术网络依赖于GPS是不可取的。因此提出了非辅助TD模式和TRD模式的定向邻节点发现算法。

慢速扫描院天线以角速度赘沿一定的方向对360毅范围内各个覆盖区进行慢速扫描。它在每个波束覆盖区的停留时间大于，即天线的波束在1个覆盖区停留的时间应大于快扫描时天线波束扫描1周的时间。设天线的波束宽度也是琢（弧度），则天线的慢扫描周期s。例如：

3 改进的邻节点发现算法

3.1 现有算法存在的问题

2.2 非辅助TD模式的定向邻节点发现算法

非辅助TD模式的定向邻节点发现算法[4]是不用GPS和其他信息辅助，采用定向发送Hello分组，使用全向天线接收Hello分组的DND算法。定向天线和全向天线的方向图如图1所示，定向模式下，波束角为60°，6个定向天线覆盖360°。每次只能在一个方向上发送Hello分组，全向模式下，可以接收所有方向上发送来的分组。

据彝良县外宣办介绍，此次滑坡塌方量达1万立方米以上，并阻断小河形成堰塞湖；油房小学教学楼全部被掩埋，据初查18名学生被埋在垮塌的教学楼内；学校附近2户农户房舍被掩埋，其中1户农户1家3口全部逃离，另1户1人被掩埋。

该算法有主动发现算法和被动发现算法，根据不同应用环境，邻节点发现算法可以按周期执行，也可以根据事件触发。

在上一章中详细介绍了非辅助邻节点发现算法DND[5]。该算法体现了定向天线的优势，但同时也有一些不足之处：会产生“听不见”问题[6]，从而降低邻节点发现性能。

3.2 改进的邻节点发现算法的提出

本文针对现有算法存在的问题对算法进行了改进，第一假设每个节点都有自己的时钟且不同步；第二假设所有节点均采用波束宽度为60毅的定向天线。

改进算法下的2种天线波束扫描方式如下：

快速扫描：天线波束以角速度棕沿一定的方向对360毅范围内各个覆盖区进行快速扫描。设天线波束宽度为琢（弧度），在每个覆盖区停留时间为子s，则扫描角速度应满足等式单位是弧度/s；快速扫描周期位是s。例如：

慢速扫描：天线以角速度赘沿一定的方向对360毅范围内各个覆盖区进行慢速扫描。它在每个波束覆盖区的停留时间大于，即天线的波束在1个覆盖区停留的时间应大于快扫描时天线波束扫描1周的时间。设天线的波束宽度也是琢（弧度），则天线的慢扫描周期

图1 定向天线与全向天线方向示意图

2.3 非辅助TRD模式的定向邻节点发现算法

非辅助TRD模式的定向邻节点发现算法也是不需要GPS和其他信息辅助，收发分组均采用定向天线的DND算法。在Ad Hoc网络中如何利用定向天线的优势对定向天线进行合理的控制是非常重要的。

这种非辅助TRD算法称为盲TRD算法[4]。定义了以下2种天线波束扫描方式。

快速扫描：天线波束以角速度棕沿一定的方向对360毅范围内各个覆盖区进行快速扫描。设天线波束宽度为琢（弧度），在每个覆盖区停留时间为子s，则扫描角速度应满足等式

主动邻节点发现过程流程图如图2所示。参数定义如下：

图2 主动邻居发现过程流程表

3.3 算法实现状态图

根据上一节中对算法的详细描述可以得到如图3所示的状态图。其中Idle为空闲状态；Sniffer为快扫描侦听状态；Send为慢扫描发送状态；Judge为判断状态，用来判断时间是否超过门限值；为慢扫描周期。

图3 邻节点发现过程状态转移表

4 仿真结果分析

根据状态转移图即可编写仿真程序，采用Xilinx公司的ISE 14.3集成开发环境作为平台对以上算法进行仿真实现，仿真结果如图4耀图6所示。

图4中，相同颜色的波形代表同一个波束扇区的波形，上方为输入波形，下方为输出波形，第一条黑色波形为时钟信号，第二条黑色波形为复位信号，接下来的第3至第8条绿色、红色、浅蓝色、黄色、棕色、深绿色、蓝色波形分别为6个扇区的输入波形，第9至第14条波形分别为6个扇区的输出波形。可以看到在对应扇区内，如果有Hello数据包被接收到，则节点随机等待一段时间后会发送回复信息，仿真结果符合预期期望。

图4 每个扇区轮流收到Hello数据包仿真图

如图5所示，其中各波形含义同上所述。可以看出，当扫描波束位于第4扇区时，第三扇区和第四扇区方向都有Hello数据包，但由于扫描波束位于第四扇区，所以只能接收到第四扇区的Hello数据包，不能接收到第三扇区的数据包，所以第四扇区有回复信息，而第三扇区没有回复信息。第五扇区和第六扇区同样如此，可见仿真结果符合定向天线的特征，仿真结果符合预期结果。

图5 定向天线同时收到Hello数据包状态仿真图

如图6所示，当节点的某个扇区信道空闲时间大于慢扫描时在一个扇区停留时间时，该扇区进入主动邻居发现程序，定向天线等间隔发送六次分组信息，发送间隔和节点快速扫描在一个扇区的停留时间是相同的，如果该节点收到邻居的回复信息，则将此节点的相关信息写入自己的邻节点信息列表中，并将此节点标记为已发现。从图中扇区输出信号的第二、第四、第五、第六波形可以看到仿真结果和理论分析情况符合，仿真结果符合期望。

图6 主动邻居发现过程仿真图

5 结束语

由以上几幅仿真结果截图以及分析可以看出，仿真程序符合上文所提出的邻节点发现协议的流程要求，仿真结果完全符合预期结果。该改进算法避免“听不见”问题，提高了邻节点发现的速度和效率。仿真结果表明，此次基于FPGA的邻节点发现协议的设计与实现是成功的，仿真结果符合预期期望。在DND邻居发现算法的实验中假设信道为理想信道，没有考虑多径效应、信道衰落等问题。如何使得邻居发现方法以适用于非理想的信道条件下的应用是个待研究的问题。

[1]王金龙,王呈贵,吴启晖,等.Ad Hoc移动无线网络[M].北京:国防工业出版社,2004.

[2]Z.Zhang.DTRA:Directional Transmission and Reception Algorithms in WLANs with directional antennas for QoSsupport[J].In IEEE Networks,2005,19(3):27-32.

[3]Z.Zhang and B.Li.Neighbor discovery in mobile ad hoc self-onfiguring networks with directional antennas:algorithms and comparisons[J].In IEEE Transactions on Wireless Communications,2008,7(5-1):1540-1549.

[4]赵瑞琴,文爱军,刘增基，等.有效支持智能天线的MANET邻节点发现算法与分析[J].西安电子科技大学学报（自然不科学版）,2007,34(3):343-344.

[5]赵瑞琴,刘增基.采用定向天线的MANET邻节点发现算法研究[J].无线电子通信技术,2006,32(4):30-31．

[6]李瑞睿,郑相全,王靖,等.一种基于定向天线的邻节点发现算法[J].现代电子技术,2011,34(5):36-30.

An Improved Neighbor Discovery Algorithm

LI Jing-an1,XU Zhi-ping2
（1 The 54th Research Institute of CETC,Shijiazhuang Hebei 050081,China）
（2 Unit 96275,PLA,Luoyang He爷nan 471003,China）

Neighbor discovery is one of the important steps in the process of self-organization of wireless Ad Hoc networks,which has significant impact on the network performance.Based on the directional antenna mode of wireless Ad Hoc network as the research object,through summarizing the existing implementation mechanism of the neighbor discovery algorithms,this paper points out the insufficiencies of the existing neighbor discovery algorithms,and proposes the appropriate modification of the existing algorithms.For directional antenna,a kind of wireless Ad Hoc network neighbor discovery algorithm is put forward in which Hello packets are sent multiple times duringslow scanning,the simulation of the algorithm verifies that the improved algorithm is reasonable and the simulation result is in accordance with the expected results.

Ad Hoc network;neighbor discovery;directional antenna;beam scanning

TP391.4

A

1008-1739（2015）12-47-3

定稿日期：2015-05-26