定向Ad hoc网络中一种带冲突避免的邻居发现算法*

景中源，曾浩洋，李大双，毛建兵

(中国电子科技集团公司第三十研究所，四川 成都 610041)



定向Ad hoc网络中一种带冲突避免的邻居发现算法*

景中源，曾浩洋，李大双，毛建兵

(中国电子科技集团公司第三十研究所，四川 成都 610041)

定向天线应用于ad hoc网络，一方面能显著提升网络性能，另一方面也需要新的MAC和路由协议来控制定向天线系统。邻居发现算法作为其中最重要的协议之一，是定向ad hoc网络组网的基础和前提，针对现有文献中提出的各种邻居发现算法大多没有考虑同一定向波束扇区内存在多个节点时的冲突情况，提出一种带冲突避免的定向邻居发现算法DAND/CA。DAND/CA通过随机选择发送控制消息占用的微时隙，能有效避免碰撞冲突的发生。仿真结果表明，提出的DAND/CA算法在邻居发现时间和成功率等方面明显优于现有算法。

定向天线；Ad hoc网络；邻居发现；冲突避免

0 引 言

多跳无线自组织网络中，节点邻域信息在路由、分群和媒介访问控制等方面起着至关重要的作用[1]。基于全向天线的ad hoc网络中，节点传输范围内的所有节点能很容易地侦听到其发送的邻居请求广播消息，邻居发现过程相对简单，不需要专门为其设计相应的通信协议，而在基于定向天线的ad hoc网络中，定向天线和定向通信自身特点使邻居发现变得较为困难[2]：

(1)定向天线将射频信号能量集中在特定的窄波束内进行辐射，只能覆盖较小的局部空间范围，必须多次重复调度切换定向波束才能覆盖整个空间方位角，即定向天线难于实现广播通信。

(2)节点必须在正确的时间、将正确的波束方向指向对方，且彼此收发模式相反，才能有效通信，即定向天线发生有效通信的条件十分苛刻。

本文首先介绍了定向邻居发现原理，然后结合定向邻居发现的特点，针对现有邻居发现算法大多没有考虑在同一个波束内同时存在多个节点时的冲突问题，提出一种基于TDMA协议的带冲突避免的定向邻居发现算法DAND/CA(Directional Antenna Neighbor Discovery with Collision Avoidance algorithm)，通过划分微时隙和随机选择节点发送邻居发现消息所占用的微时隙，允许同一波束扇区内的多个邻居节点在不同微时隙内独立完成邻居发现过程，从而有效地避免了邻居发现过程中的消息碰撞冲突，仿真结果显示DAND/CA算法能有效缩短邻居发现时间并提高邻居发现成功率。

1 邻居发现原理

邻居发现是指节点开机后，在没有邻节点任何先验信息的条件下，通过基于一定的互盲或自盲算法协议迅速发现其1跳范围内的所有其他节点(同时被其他节点所发现)，并建立基本通信连接的过程[3]。

在全向天线系统中，节点通过广播邻居请求分组搜集邻域信息，其一跳覆盖范围内的所有处于接收状态的邻居节点必定都能收到该广播信号。在定向天线系统中，由于定向窄波束只能覆盖空间局部区域，上述“必定”的条件并不存在，同时节点之间能有效通信的条件如图1所示，即需要满足发送和接收必须同时对准时隙和方向。

图1 定向邻居节点有效通信示例

因此相比于全向天线，在定向天线系统中解决邻居发现问题时需要考虑更多的内容，具体包括天线模式选择算法设计、多波束切换天线扫描图案设计以及控制消息交互机制设计等。

其中，天线模式指节点天线的工作状态，包括发送和接收2种。若天线工作状态为发送，则在特定的空间波束方向上定向发送邻居请求消 息；若为接收，则在特定的空间波束方向上侦听信道，等待接收邻居请求消息。

在基于多波束切换天线的Ad hoc网络中，由于定向天线难于实现广播通信，当节点需要对多个节点广播数据消息时，须按照某种调度顺序对整个空间区域进行“扫描”。扫描过程，即多波束天线不断切换其当前所使用定向波束扇区的过程，其中定向波束切换的顺序和方法称为定向天线的扫描图案。

应当注意，天线模式和天线扫描图案既相互关联又相互约束，二者共同决定某次邻居发现过程成功的统计特性，并直接影响邻居发现过程的性能指标。

2 DAND/CA算法描述

2.1 系统模型和节点假设

图2 理想的K扇区多波束切换天线

多波束切换天线通过选择不同的天线单元就能实现波束扇区的切换，是定向天线中最简单且最易于实现的一种，DAND/CA算法相关结论就是基于多波束切换天线得出的，但应当注意它同样可以很容易地扩展到其他类型的定向天线系统中去。

节点还应当满足以下假设条件：

(1)通信模式为半双工，任何时刻节点只能处于收发工作模式中的一种，但能在传输与接收模式之间快速切换。

(2)任何时刻，节点最多只能在一个定向波束扇区内进行消息分组发送或接收，但能在不同扇区之间快速地切换。

(3)时间是基于时隙划分的，所有节点通过GPS或北斗系统能够达到精确的时钟同步。

(4)传输功率固定不变，即所有节点定向天线增益完全相同，避免了天线增益不一致引发的通信距离不对称等问题。

(5)同时收到2个及2个以上邻居节点的消息分组时，将发生碰撞冲突而无法正确接收和解析消息分组[4]。

2.2 信道时帧结构

DAND/CA算法设计的TDMA时帧循环结构如图3所示，将信道资源划分为连续的、周期性重复的TDMA帧，每帧由邻居发现子帧和业务数据传输子帧组成，其中业务数据传输子帧包含M个数据时隙，邻居发现子帧包含探测、响应和确认3个阶段，每个阶段由N个持续时间更短的引导微时隙组成；每个时隙的持续时间为T，每个引导微时隙的持续时间为T/N。

图3 TDMA帧结构示意

在周期性的TDMA帧结构内，与邻居发现过程相关的各类时隙定义如下：

邻居探测引导(NiDB，Neighbor Detect Bootstrap)时隙：为邻居发现过程中随机分派给各发送模式节点使用的时隙。邻域探测引导时隙用于主动发起邻居发现过程的节点在特定的波束扇区内发送邻居请求消息分组，分组信息包含有节点的ID编号、1跳邻域信息以及节点HRFS时隙分配信息。每帧中邻域探测引导时隙NiDB配置数量为N。

邻居应答引导(NiRB，Neighbor Reply Bootstrap)时隙：随机分派给成功接收邻居请求消息分组的节点，用于传输邻居响应和HRFS时隙分配所需的信息。每帧中邻居应答引导时隙NiRB配置数量为N。

邻居确认引导(NiAB，Neighbor Acknowledge Bootstrap)时隙：为分派给成功接收邻居响应消息分组节点使用的时隙，其分配情况与NiDB完全一致，用于传输邻居发现确认及HRFS时隙分配结果等信息。每帧中邻居响应引导时隙NiAB配置数量为N。

2.3 天线收发模式选择

为了消除孤立节点和近在咫尺的节点无法发现等问题，DAND/CA采用基于节点ID二进制编码的方法确定收发模式，将每个节点全网唯一的ID编号j和网络节点数量N作为静态参数在节点开机时进行自动加注，并根据图4所示天线收发模式算法流程决定当前时刻天线是处于发送模式或侦听模式，其中当前扫描周期数i计算公式为：

i=⎣Frame_sequence/K/w」

(1)

式中，Frame_sequence为信道帧序号，K为定向多波束天线扇区数，w表示在每个波束扇区内驻留的信道帧数。应当注意，1轮扫描周期内节点天线的收发模式将保持不变，并在每个波束扇区内重复执行w次收发操作后，顺序切换至下一个波束扇区，当遍历完所有的波束扇区后本轮扫描周期结束。

图4 DAND/CA天线模式选择流程

2.4 天线扫描图案

确定节点工作模式后，DAND/CA算法将根据当前天线工作模式进行天线扫描图案的设计。第i轮天线扫描周期开始时，主动发送模式的节点将在编号为i的波束扇区内定向发送邻居请求消息，并在该波束扇区内驻留w个信道帧，即重复执行w次发送操作，然后节点顺时针切换至编号为i+1的定向波束扇区内重复执行上述过程。

第i轮天线扫描周期开始时，被动侦听节点将在编号为[(i+K/2) %K]的定向波束扇区内定向接收邻居请求消息，其中K为多波束天线扇区数，节点在该波束扇区内驻留w个信道帧，即重复执行w次接收操作，然后节点切换至编号为[(i+1+K/2)%K]的定向波束扇区内重复执行上述过程。

DAND/CA算法中的天线扫描图案，可以确保在具有相同的方向基准前提下，处于收发模式的邻居节点尽可能将当前激活波束扇区互相指向对方，从而满足定向节点有效通信的条件。

2.5 Hello-Reply-Ack 3步握手机制

DAND/CA算法采用一种3步握手机制确保节点之间发现的所有通信链路均为双向链路[5]。下面以第i轮天线扫描周期过程为例，详细介绍DAND/CA算法的3步握手过程，并对其邻居发现过程中的消息碰撞冲突避免机制进行重点分析。

图5为邻居发现过程中同一个波束扇区内存在多个邻居节点时的一种可能的冲突情形。图中节点A、B为发送模式，其当前激活的波束扇区覆盖范围内有节点C、D、E和F为侦听模式，且节点A、B和节点C、D、E、F的波束相互指向对方，即节点A、节点B和节点C、D、E之间满足定向通信的条件，当节点A、节点B同时发送消息时，将在所有侦听节点处发生消息碰撞冲突，导致邻居发现过程失败。现有的定向邻居发现算法，如PRA[6]、SBA[6]等，没有考虑图5的冲突情形，因此它们仅适用于节点较少的稀疏网络，当网络内邻居节点数增加时算法性能会明显下降。

图5 冲突情形：1个波束扇区内存在多个邻居节点

DAND/CA算法，在充分考虑图5所示冲突情形对邻居发现过程影响的基础上，将信道帧结构内的邻居发现子帧划分多个持续时间更短的引导微时隙，节点通过随机选择发送邻居交互信息所占用的微时隙，允许同一波束扇区内的多个邻居节点在不同的微时隙内独立完成邻居发现过程，从而有效地避免了邻居发现过程中的消息碰撞冲突。

DAND/CA算法中实现邻域信息交互、完成预约协商并初步建立定向通信链路的3步握手机制描述如下，为了便于描述，令参数w=3。

(1)邻居发现阶段1

邻居发现过程的第1阶段在信道帧的NiDB时隙内进行。主动发送模式节点A、B，分别从N个NiDB中随机选取1个时隙，用于定向广播发送邻居请求消息hello_request；侦听节点C、D、E和F在所有的NiDB时隙内处于信道监听状态，等待接收hello_request消息。冲突避免见图6。

图6 DAND/CA算法hello_request消息冲突避免

图6中，节点A、B在第1个信道帧内，均随机选择在第1个NiDB时隙定向发送邻居请求消息hello_request，将在邻居节点C、D、E和F处发生消息冲突碰撞，宣告第1个信道帧内的邻居发现过程失败；在第2个信道帧内，节点A、节点B分别随机选择在第0个、第2个NiDB时隙内发送hello_request消息，可成功被帧听节点接受并解析，而进入邻居发现过程的第2阶段。成功完成邻居发现过程第1阶段的节点A、节点B，将不再参与后续信道帧NiDB时隙的竞争使用，能进一步避免可能存在的消息冲突碰撞，并增加其他发送节点成功发送hello_request消息的概率。

(2)邻居发现阶段2

邻居发现过程的第2阶段在信道帧的NiRB时隙内进行。被动侦听模式节点C、D、E和F，如果在NiDB时隙内成功接收并解析来自节点A、B的邻居请求消息hello_request，则将从邻居发现子帧的N个NiRB时隙中随机选取1个时隙，用于定向广播发送邻居应答消息hello_reply；节点A、节点B在所有的NiRB时隙内处于信道监听状态，等待接收hello_reply消息。 该过程见图7。

图7 DAND/CA算法reply消息冲突避免过程

图7中，Discovery-Cycle的第1个信道帧内，节点A和节点B在同一个NiDB时隙发送而导致节点C、D、E和F处发生消息冲突碰撞，因此邻居应答引导时隙NiRB内，节点C、D、E和F将不会发送hello_reply消息分组，而处于静默状态；在Discovery-Cycle的第2个信道帧内，成功接收并解析hello_request消息分组的节点C、D、E和节点F，将在该帧内的NiRB时隙对其进行响应应答，响应过程如下：

节点C、D、E和节点F，在[0，N-1]中随机选取1个整数值作为其占用的NiRB时隙号。假设节点C占用0号NiRB时隙、节点D、E占用1号NiRB时隙、节点F占用N-1号NiRB时隙发送hello_reply消息分组，根据消息分组冲突碰撞规则分析，节点A、B能够正确接收并解析节点C、节点F的hello_reply消息分组，但无法正确接收并成功解析节点D、节点E的hello_reply消息分组。

节点A、B解析节点C、F的hello_reply消息分组后，将节点C、F的节点标识、位置信息等添加到本地邻居信息表项中，并进入邻居发现过程的第3阶段，即向节点C、节点F发送邻居发现确认消息分组hello_ack，通知节点C、F已经成功被发现以及关于后续通信时隙预约的相关结果信息，hello_ack分组内还包含该波束扇区内已经被发现节点的ID标识；节点D、E通过分析接收到的hello_ack消息分组中携带的已经被发现节点的ID标识信息，知道其在NiRB时隙发送的hello _ reply消息分组可能由于冲突碰撞而未被正确接收和解析，将在Discovery-Cycle的第3个信道帧内，重复执行上述hello_reply消息分组发送过程。图7中的第3个信道帧内，节点C、F将不再参与NiRB时隙的竞争使用，节点D、节点E分别随机、无冲突地占用2号NiRB时隙和0号NiRB时隙发送hello_reply消息分组，消息分组能够被节点A和节点B正确接收并解析，从而成功进入邻居发现过程的第3阶段。

(3)邻居发现阶段3

邻居发现过程的第3阶段在信道帧的NiAB时隙内进行。节点A、B在NiRB时隙内向成功发送hello_reply消息分组的节点定向广播邻居确认消息分组hello_ack，其占用的NiAB时隙号不是通过随机方式产生的，而是与NiDB时隙的占用情况有关，即节点选取的NiAB时隙号和NiDB时隙号占用情况完全一致，这种方法可以进一步避免采用随机占用时可能产生的消息冲突碰撞，确保消息分组hello_ack一定能被目标节点正确接收和解析。

对比分析图6和图8，节点A、B占用的NiDB时隙和NiAB时隙编号完全相同，确保了邻居确认时隙一定无消息分组冲突碰撞的发生，这对提高邻居发现成功概率有十分重要的作用和意义。

图8 DAND/CA算法ack消息冲突避免过程

3 DAND/CA仿真分析

本节采用OPNET网络仿真工具进行仿真实验，对基于TDMA协议的带冲突避免的定向邻居发现算法DAND/CA的性能进行实验验证。在仿真实验中，比较对象是PRA、SBA算法和一种增强型的SBA算法I- SBA[4]。现在以下仿真场景中对这4种定向邻居发现算法进行性能仿真和比较。

3.1 仿真场景和参数设置

(1)仿真拓扑结构采用6×6网格拓扑，36个节点随机分布在10 km×10 km的区域内，节点定向传输半径为15 km，网络的每个节点都互为1跳邻居。

(2)多波束切换天线由12个波束构成，每个波束主瓣宽度为30°，可无缝覆盖整个360°水平空间范围。

(3)信道速率设为2 Mb/s，信道带宽为10 kHz，传输频率为30 MHz，调制方式为QAM64；N取值为8，T为0.125 ms。

同时，为了减小网络仿真时仿真随机数种子的选取对实验结果的影响，在实验中对每个数据点取5次不同随机数种子情况下的实验结果平均值作为最终结果[7]。

3.2 仿真结果分析

图9给出了在PRA、SBA、I-SBA和DAND/CA算法下，定向邻居节点平均发现时延的对比关系。

图9 邻居发现算法性能对比

由图9可以看出，组网开始阶段，所有节点都将尝试发送邻居发现控制消息，消息碰撞冲突严重，4种定向邻居发现算法的性能差距较大，带冲突避免的DAND/CA算法表现最好，能快速发现周围所有邻居节点，且算法收敛性好；I-SBA在SBA基础上，在收发状态间新添1个“空闲”状态，处于空闲状态的节点既不发送控制消息也不接收控制消息，在一定程度上避免了消息碰撞冲突；PRA是完全随机的邻居发现算法，无冲突避免机制，在开始阶段冲突碰撞严重的情况下，算法性能较差，但随着时间推移和消息碰撞冲突情况的缓解，PRA算法性能明显变好。

需要注意的是，上述仿真给出了DAND/CA算法的性能结果，但未对算法中的参数N、K、w的不同取值对DAND/CA算法性能的影响进行仿真和分析，如何对参数进行优化设计是需要进一步研究和仿真的重点。

4 结 语

本文详细介绍了定向Ad hoc网络邻居发现原理，对其中的天线收发模式选择、天线扫描图案等关键技术进行了重点分析，在此基础上，针对现有定向邻居发现算法没有充分考虑同一个波束内同时存在多个节点时的冲突问题，提出一种带冲突避免的定向邻居发现算法DAND/CA。仿真结果表明，DAND/CA算法在不显著增加网络控制复杂度的情况下，适用于从稀疏到密集的所有网络场景，可快速、可靠地发现网络内所有1跳邻居节点并初步建立起定向通信链路，从而快速组建定向Ad hoc网络。

[1] Murawski R, Felemban E,Ekici E,et al. Neighbor Discovery in Wireless Networks with Sectored Antennas[C].Ad Hoc Networks,2012(10):1-18.

[2] 景中源，曾浩洋，李大双等.定向Ad hoc网络MAC组网技术研究[J].通信技术，2014(09)：1041-1047. JING Zhong-yuan，ZENG Hao-yang，LI Da-shuang，et al. The MAC Layer Networking Technology Research in Ad hoc Network with Directional Antennas[J].Communications Technology,2014(09):1041-1047.

[3] 蔡浩，刘勃，归琳.定向天线的Ad hoc网络邻居发现[J]. 信息安全与通信保密，2011(09)：63-66. CAI Hao,LIU Bo,GUI Lin. Neighbor Discovery in Ad Hoc Network using Directional Antennas [J]. Communications Technology,2011(09):63-66.

[4] CAI Hao,LIU Bo,GUI Lin,et al. Neighbor Discovery Algorthms in Wireless Networks Using Directional Antennas[C]//Ad hoc and Sensor Networking Symposium.[s.l.]: [s.n.],2012:767-772.

[5] Woongsoo Na, Laihyuk Park, Sungrae. Deafness-Aware MAC Protocol for Directional Antennas[C]//IEEE International Conference on Consumer Electornics(ICCE) .[s.l.]: [s.n.], 2013: 625-626.

[6] ZHANG Zhen-sheng, Ryu B,et al. Performance of All -Directional Transmission and Reception Algorithmsin Wireless Ad Hoc Networks with Directional Antennas[C]//IEEE MILCOM.[s.l.]:[s.n.],2005:225-230.

[7] 戴英.定向Ad hoc网络的MAC协议研究[D].成都：西南交通大学,2013. DAI Ying. MAC Protocol Research in Ad hoc Network with Direction Antenna[D]. Chengdu: Southwest Jiaotong University, 2013.

A Neighbor Discovery Algorithm with Collision Avoidance in Ad hoc Networks Using Directional Antennas

JING Zhong-yuan，ZENG Hao-yang，LI Da-shuang ，MAO Jian-bing

(No.30 Institute of CETC, Chengdu Sichuan 610041, China)

Directional antennas applied in Ad hoc network, could obviously improve network performance, and however,also needs new MAC and routing protocols to control the directional antenna system. Neighbor discovery algorithm, as one of the most important protocols, is the basis and premise for ad hoc networking. In the light that most of the proposed neighbor discovery algorithms consider no the collision case that multiple nodes exist in the same directional beam sector, a new directional neighbor discovery algorithm with collision avoidance called DAND/CA (Directional Antenna Neighbor Discovery with Collision Avoidance) is proposed. DAND/CA algorithm could efficiently avoid collision case by randomly selecting mini-slot to transmit control messages. Simulation results indicate that the proposed DAND/CA is remarkably superior to the existing algorithms in terms of neighbor discovery time and success ratio.

directional antennas; ad hoc network; neighbor discovery; collision avoidance

10.3969/j.issn.1002-0802.2015.05.015

2014-11-10；

2015-03-07 Received date:2014-11-10；Revised date：2015-03-07

TP393

A

1002-0802(2015)05-0582-07

景中源(1988—)，男，硕士研究生，主要研究方向为战术网络组网；

曾浩洋1968—)，男，硕士，研究员，主要研究方向为战术通信网络；

李大双(1963—)，男，博士，研究员，主要研究方向为战术网络组网与路由技术；

毛建兵(1981—)，男，博士，高级工程师，主要研究方向为无线传感器网络。