基于定向天线无线自组网的快速随机邻居发现算法

刘岩　刘成朋　杨健

摘要：为了减少无线自组网的组网所需时间，提升随机发现算法邻居发现的概率，提出了一种基于定向天线的随机邻居发现算法。根据相控阵天线能够自由切换宽波束和窄波束的特点，发挥宽波束搜索能力强、窄波束传输能力强的优势，使用宽波束和窄波束来进行邻居发现，并结合碰撞重传机制和邻居节点辅助发现机制，对碰撞重传的最优竞争窗口值进行了计算。仿真实验表明，算法降低了邻居再发现的时间开销，增加了邻居的发现概率，满足快速组网和高速通信的需求。在不同节点数下，邻居发现所需时隙数均少于基于碰撞避免的随机发现算法，具备更快的邻居发现速度。所提算法可为无线自组网提供一种高效的邻居发现方案，提高无线自组织网络性能，在飞行器组网等应用场景中具有一定的实用价值。

关键词：无线通信技术;无线自组网;定向天线;邻居发现;随机发现;波束宽度

中图分类号：TN929.5文献标识码：A

DOI： 10.7535/hbgykj.2022yx02002

Fast random neighbor discovery algorithm based onwireless Ad hoc network of directional antennas

LIU Yan，LIU Chengpeng，YANG Jian

（The 54th Research Institution of CETC，Shijiazhuang，Hebei 050081，China）

Abstract：In order to reduce the time required for wireless Ad hoc network and improve the probability of neighbor discovery in random discovery algorithm，a fast random neighbor discovery algorithm based on directional antennas wireless Ad hoc network was proposedBased on the characteristics of the free switch between wide and narrow beams of phased array antenna，the proposed algorithm gave full play to the advantages of strong wide beam search ability and narrow beam transmission ability，used wide beam and narrow beam for neighbor discovery，and combined the collision retransmission mechanism and neighbor node auxiliary discovery mechanism to calculate the optimal competition window value of the collision retransmissionIt reduced the time cost of the neighbor rediscoveryThe simulation experiment shows that the algorithm increased the probability of neighbor discovery，and met the needs of fast networking and high-speed communication，and under different numbers of nodes，the number of time slots required for neighbor discovery of the proposed algorithm is less than that of the random discovery algorithm based on collision avoidance，and has a faster neighbor discovery speedThis design method can provide an efficient neighbor discovery scheme for wireless Ad hoc network，improve the performance of wireless Ad hoc network，and has certain practical value in application scenarios such as aircraft network

Keywords： wireless communication technology;wireless Ad hoc network;directional antenna;neighbor discovery;random discovery;beam width

隨着无线通信技术的高速发展，无线自组网由于具备自组织、抗毁性强和无中心等特点，引起了研究者们的广泛关注[1]，其应用范围也得到了扩展。目前传统的无线自组织网络大多采用全向天线模式[2]，该模式具有辐射无方向性的特点，存在节点间传输距离受限、信息易截获和信道利用率低[3]等问题。为解决上述问题，研究人员将定向天线引入无线自组网中[4]。定向天线在特定方向具有很高的收发增益，而在其他方向上增益很小，故具备传输距离远、抗截获能力强和信道利用率高等优点[5-7]。然而，定向天线的引入使邻居发现变得较为困难，邻居互相发现必须满足以下3个条件：1）通信的双方必须满足同一时间进行信息交互;2）同一时间通信双方的波束必须彼此指向对方;3）2个节点的距离应该小于此场景下的最远传输距离。目前，邻居发现算法主要分为确定型发现算法[8-10]和随机型发现算法[11-14]两类。确定型发现算法协调了所有节点的发送和接收方向，增加了检测概率，但同时增加了碰撞概率;相反，随机型发现算法中收发状态随机和方向随机的方案降低了检测概率和碰撞概率。B43F9E47-26B5-44BC-8274-6197D0BDF388

近年来，为了提升邻居发现算法的性能，邻居辅助发现方法被许多研究者关注。文献[15]通过引入DSN的邻居协作发现机制，使节点在不同扇区交换轮询消息，间接发现邻居。然而，该算法只能保证在短时间内发现90%的邻居。文献[16]采用慢扫描模式，以较低的延迟将邻居发现概率提高至接近100%。文献[17]在相邻节点之间寻找邻居集合的发现交集，利用公共邻居来提高发现效率，加快了邻居发现的进程。

消息碰撞问题是影响邻居发现速度的因素之一。当网络中的节点数较少时，碰撞几乎没有出现，若采用节点以一定概率保持静默的策略来降低碰撞概率，则会降低发现概率，反而影响发现速度。随着网络内节点数的增加，碰撞问题会随之增加，合理的碰撞避免机制会降低碰撞概率，合理的碰撞解决机制会快速再发现，相比重新发现耗时短，从而加快发现速度。为了解决消息碰撞问题，文献[18]提出SBA-PI算法引入了静默状态，使节点具备发送、接收以及静默3种状态，这一操作通过碰撞避免机制减少冲突。此外，文献[19]在随机发现的基础上，引入选择性回复机制，节点一次握手成功后，以概率ρ进行回复，减少了二次握手中的碰撞冲突，但是在碰撞较少的情况下，降低了邻居发现的概率。文献[20]通过随机选择发送控制消息的微时隙，有效避免了碰撞冲突的产生。以上算法都通过避免碰撞的方式来提升邻居发现速度，但这会降低邻居发现的概率。因此，文献[21]在经典的随机发现算法[22]的基础上，结合邻居辅助发现方法，提出了碰撞重传机制来解决碰撞问题。[JP2]该方法在碰撞后重新预约时隙进行重传，改善了碰撞带来的影响。在随机算法中，相比于碰撞避免的方式，碰撞解决机制能避免浪费此次波束对准的机会，快速再发现，从而加快发现速度。

然而，在实际应用中，定向天线的加入对无线自组网提出了快速组网和高速通信的需求。而普通的随机发现算法已无法满足性能要求，采用窄波束搜索、窄波束监听的方式，导致邻居发现概率较低，发现时间较长。因此本文提出一种基于定向天线无线自组网的快速随机邻居发现算法，根据相控阵天线能够自由切换宽波束和窄波束的特点，发挥宽波束搜索能力强、窄波束传输能力强的优势，采用窄波束搜索、宽波束监听策略进行邻居发现，增加邻居的发现概率，满足快速组网和高速通信的需求。

1网络模型描述

假设每个节点都配备一副可以调整为宽波束和窄波束的一维相控阵天线，其中发送节点窄波束个数为K₁，接收节点宽波束个数为K₂。此外，节点还具有以下特点。

1）网络节点总数为N，每个节点都有唯一的ID标识。

2）一个邻居发现时隙可以分为2个子时隙，在每个子时隙中，节点可以完成握手的过程。邻居发现时隙划分如图1所示。

3）假设2个具有定向天线的节点可以互相通信，需要一个节点处于接收状态，另一个节点处于发射状态，并且它们的收发波束相互覆盖。因此，2个节点必须要同时指向其波束，并且发送和接收状态相反。

4）如果有2个或者2个以上的波束到达一个节点的接收波束上，则会发生消息碰撞，碰撞之后，节点不会收到数据包。在子时隙1，A节点进行发送，B节点进行接收。在子时隙2，2个节点收发状态相反，通信成功的案例如图2所示。

当一个节点同时从其给定波束中的2个或多个邻居接收发现数据包时，就会发生碰撞，碰撞案例如图3所示。在这种情况下，节点无法解析信息，因此认为数据包丢失了。每个节点可以通过一个简单的能量探测器区分空时隙和一个碰撞的时隙。

2基于定向天线无线自组网的快速随机邻居发现算法

2.1改进思路

为了在远距离的条件下快速地发现邻居，建立网络，达到数据高速通信的目的。所提算法使用定向天线，采用两次握手的工作机制完成邻居发现，握手过程如图4所示。一次握手阶段发送节点使用窄波束扫描，接收节点使用宽波束监听，二次握手阶段接收节点使用窄波束回复，发送节点使用窄波束监听，增大节点发现概率，并结合碰撞重传机制和邻居辅助发现机制，加快邻居发现进程，满足快速发现邻居的需求。

相较于传统随机发现算法采用窄波束相互扫描的方式。所提算法使用窄波束扫描，宽波束监听的策略，并采用低速率模式进行邻居发现以提高可靠性，增加了接收灵敏度，如式（1）和式（2）所示，能够提高邻居发现概率，缩短邻居发现的时间。

发射功率-接收灵敏度=LOS， （1）

S=10lg（kTB）+NF+SNR， （2）

式中：S代表接收灵敏度，接收灵敏度越小，则接收机的接收性能越好;k代表玻尔兹曼常数，T代表绝对温度，B代表信号带宽，kTB整体表示带宽范围内的热噪声功率;NF代表系统噪声系数;SNR代表解调所需信噪比。由此可知，选择低速率通信，则接收灵敏度越小，便于发现邻居。

2.2工作流程

本文算法主要包括参数初始化、碰撞解决阶段和邻居辅助发现阶段3个过程。其中参数初始化中主要完成节点收发状态和天线方向的选取，碰撞解决阶段完成碰撞节点的信息重传过程，邻居辅助发现阶段根据收到的信息包，判断是否有自身未含有的邻居信息，间接进行邻居发现，加快邻居发现进程。综上，所提算法的工作流程如图5所示。

2.2.1算法步骤

步骤1：生成N個处于随机位置的初始节点，所有节点已通过外部授时或自带铷钟进行时间同步。

步骤2：每个节点以一定概率成为发送节点或接收节点。1）成为发送节点概率p_t，在子时隙1向随机方向用窄波束搜索，[JP2]在子时隙2向相同的方向用窄波束监听。2）成为接收节点的概率为1-p_t，在子时隙1向随机方向用宽波束监听。如果子时隙1成功收到信息包，则在子时隙2判断来时信息的方向，切换窄波束进行回复，否则需判断是碰撞还是未收到信息包。若发生碰撞则进入碰撞解决机制，否则将在子时隙2保持静默状态，保存节点能量。B43F9E47-26B5-44BC-8274-6197D0BDF388

步骤3：若节点间在邻居发现阶段完成两次握手，则2个节点成为邻居，并且收到对方的邻居列表。例如，节点A和B互为邻居，节点B和C互为邻居，A和C通过B节点提供的邻居列表，进行间接邻居发现。

步骤4：当发现网络中全部节点间所有链路时，邻居发现成功。

对参数初始化、碰撞解决阶段和邻居辅助发现阶段进行详细介绍。

2.2.2节点参数初始化

节点参数包括节点收发状态和天线方向，若定义发送节点窄波束个数为K₁，接收节点窄波束个数为K₂。具体初始化步骤如下。

1）当节点启动后，首先根据当前的时隙号搜索退避列表，判断是否要进行退避。

2）如果不需要退避，则开始按照算法随机选择节点的收发状态和天线方向。

3）如果需要退避则按照退避列表选择节点的收发状态和天线方向。

节点收发状态的选取需要对发送概率进行研究。在每个时隙开始时，一跳邻域中的每个节点分别以p_t和1-p_t的概率随机选择发送或者接收。如果节点发送概率p_t设置过高，将导致较多的碰撞，减慢邻居发现速度。相反，如果节点发送概率p_t设置过低，将导致信道利用率不足，从而降低邻居发现效率。因此，求解最优的发送概率才能获得最大的邻居发现概率。为了评估邻居发现算法的性能，这里计算了节点i和节点j在给定时隙t中发现彼此的概率，用p_s表示。对于邻居发现过程，节点应该在2个子时隙中成功传输。

假设节点i作为发送节点，节点j作为接收节点，二者互相发现彼此，需要满足3个条件。

1）对于节点i，在子时隙1，节点i向节点j的方向发送消息的概率为A=（1/K₁）p_t，在子时隙2，节点j回复节点i的概率为1。

2）对于节点j，在子时隙1，节点j在节点i的方向接收消息的概率为B=（1/K₂）pt，在子时隙2，节点i指向原来发送方向保持接收的概率为1。

3）对于任意一个其他节点，假如此节点不干扰到节点i和节点j正常通信的概率可描述为C=p_t（1-1/K₁K₂）+（1-p_t）[1-（p_t/K₁²）]，第1部分表示在子时隙1，其他节点没有选择向节点j接收方向发送的概率，在子时隙2，节点不会再發送。第2部分表示在子时隙1，其他节点保持接收状态，在子时隙2，没有向节点i的方向回复信息的概率。

结合上述3点，同理可得，节点j作为发送节点，节点i作为接收节点的概率，故节点i和节点j在时隙t成功发现彼此的概率如式（3）：

p_s=2ABC^n-1， （3）

式中n-1为节点的邻居节点个数。

2.2.3碰撞解决阶段

碰撞解决流程如图6所示，假定一跳的邻域内有4个节点A，B，C，D，在子时隙1中，节点A，C和D处于发送模式，而节点B处于接收模式。在这种情况下，节点B可能接收到多个发现包，导致冲突，在子时隙2中，节点B使用相同的波束传输碰撞确认信息，4个节点进入碰撞解决阶段[20]。

节点B一直保持接收模式，直到它成功接收到2个信息包为止，代表重传成功。而节点A，C，D将在接下来的几个时隙计划重传，在竞争窗口CW中随机选择一个重传时隙，其他时隙节点可以进行发送或者接收。但是如果节点A进入了碰撞解决机制，那么它在接收到B的成功回复之前，不会再对B计划新的重传。如果多个节点选择同一个时隙进行重传，那么将根据竞争窗口值选取新的时隙进行重传，保证碰撞解决。

在碰撞解决机制中，为了降低多个节点选取同一时隙进行重传的概率，避免邻居发现包再次碰撞，需要定义恰好一个节点选择一个给定时隙进行重传的概率，找到最优的竞争窗口值CW，使成功重传的概率取最大值。

定义i个节点选择同一个时隙进行重传的概率为p_s（i）。每个节点周围有n个邻居节点，其中恰好有i个节点需要进行重传，每个节点选择重传时隙的概率为1/CW，此时模型可以视为二项式分布n，1CW，可以得出：

综上，所提算法在碰撞解决阶段设置竞争窗口大小为n时最优。

2.2.4邻居辅助发现阶段

网络时帧分为邻居发现阶段、管控阶段及数据传输3个阶段。邻居发现阶段进行互相发现，邻居发现包携带自身邻居信息，发现成功后将得知潜在的邻居;管控阶段完成所有节点的波束跟踪，业务请求和时隙分配功能，两两节点彼此对准一次。若节点A和B在邻居发现阶段成为邻居，则互相收到对方的邻居发现包，记录潜在的邻居，将在管控阶段进行对准，包括与潜在邻居的对准，此为邻居辅助发现过程[17]。节点拓扑关系如图7所示。

3仿真结果分析

为了验证所提算法的有效性，在Matlab平台上进行仿真验证。实验中，在5 000×5 000的区域内随机生成节点，本算法两节点间的最大传输距离设置为1 000，以发现全部节点间所有链路所需时隙数为指标。仿真实验结果表明，相较于文献[21]中的算法以及经典的随机算法，所提算法具有更高的邻居发现概率，且发现全部邻居所用时隙数更少，邻居发现的效率更高。

3.1最佳发送概率选取的仿真及分析

由22节的式（3）可得，当节点发送概率p_t为05时，发现概率p_s取最大值。通过实验对以上结论进行验证，此处设置窄波束个数K₁=12，宽波束个数K₂=4，节点个数N分别设置为16，32，48以代表低密度、中密度、高密度3种情况。每个概率p_t重复10次实验取p_s的平均值，仿真结果如图8和图9所示。其中图8展示了发现概率p_s随发送概率的变化图，图9展示了发送概率p_t对总时隙数的影响。B43F9E47-26B5-44BC-8274-6197D0BDF388

由图8可知，在低密度、中密度、高密度3种情况下，当发送概率p_t取05时，发现概率p_s最大，可以达到最佳的发现效果，与式（3）推导结论相符。此外，由图9可知，当p_t取05时，邻居发现所需总时隙数slots最少，该趋势与理论推导相符。

3.2算法性能对比

为了客观验证所提算法的有效性，本节将所提算法进行仿真，并与文献[21]中的算法及经典的随机算法进行对比，使用发现全部节点间所有链路所需时隙数slots作为性能指标。所提算法设置窄波束个数K₁=12，宽波束个数K₂=4，文献[21]中的算法及经典的随机算法，设置发节点和收节点窄波束个数均为K=12。邻居发现时间性能进行对比如图10所示。其中横坐标表示节点个数N，纵坐标表示邻居发现所需总时隙数slots。

由图10可知，所提算法发现所有节点所需的时间均小于文献[21]中随机算法及经典的随机算法所需时间，并且随着节点数的增多，所提算法与其他算法相比，增长的时间较少，具备更优的性能。为了进一步考察所提算法的性能，将节点个数N增加到100个，如图11所示。

由图11可知，随着节点个数的增大，所提算法完成邻居发现所需时隙数为线性增长，当网络节点数为100时，所需时隙数仅约为450个。

4结语

本文研究了基于定向天线的无线自组网邻居发现问题，为了提升邻居发现的效率，根据相控阵天线能够自由切换宽波束和窄波束的特点，发挥宽波束搜索能力强，窄波束传输能力强的优势，使用窄波束搜索，宽波束接收来进行邻居发现，增加了邻居的发现概率，满足快速组网和高速通信的需求。仿真实验表明，所提算法能计算出节点的最佳发送概率和碰撞重传的最佳窗口值，从而取得最优的邻居发现效果，加快邻居发现速度，并且随着节点数增加，所提算法性能更优。

邻居发现阶段使用低速率模式通信，实现邻居发现和前期握手，这导致邻居发现阶段的信息传输速率受到了一定程度的限制。因此，如何在邻居发现阶段取得较好的发现效果，同时达到较高的邻居传输速率，是未来可进一步研究的方向。

参考文献/References：

[1]邵瑋璐移动自组网中混合接入协议的研究[D]上海：上海师范大学，2020SHAO WeiluResearch on Hybrid Access Protocol in Mobile Ad Hoc Network[D]Shanghai：Shanghai Normal University，2020.

[2]NICHOLS RDirectional network discovery performance[C]//34th IEEE Sarnoff Symposium，PrincetonNJ：IEEE，2011：1-5

[3]李丽，郑博文，刘丽哲一种适于波束切换移动自组网的邻居发现改进算法[J].无线电通信技术，2020，46（3）：286-292LI Li，ZHENG Bowen，LIU LizheImproved neighbor discovery algorithm for beam switching mobile ad hoc network[J].Radio Communications Technology，2020，46（3）：286-292.

[4]伍芸荻无人机通信系统中信息和能量传输优化研究[D]合肥：中国科学技术大学，2019WU YundiResearch on Information and Energy Transmission Optimization in UAV Communication System[D]Hefei：University of Science and Technology of China，2019.

[5]杨欣无线自组网MAC层协议及跨层协同技术研究[D]西安：西北工业大学，2018YANG XinResearch on Medium Access Control Protocol and Cross-Layer Cooperation Technology of Wireless Ad Hoc Networks[D]Xi′an：Northwestern Polytechnical University，2018.

[6]梁志公无线自组网定向天线邻居发现技术研究[D]成都：电子科技大学，2020LIANG ZhigongResearch on Neighbor Discovery Technology for Directional Antenna Enabled Wireless Ad Hoc Networks[D]Chengdu：University of Electronic Science and Technology of China，2020.

[7]徐大凤无线Ad hoc网络定向MAC协议研究[D]成都：电子科技大学，2017XU DafengResearch on Directional MAC Protocol for Ad Hoc Networks[D]Chengdu：University of Electronic Science and Technology of China，2017.

[8]FELEMBAN E，MURAWSKI R，EKICI E，et alSAND：Sectored-antennaneighbor discovery protocol for wireless networks[C]//2010 7th Annual IEEE Communications Society Conference on Sensor，Mesh and Ad Hoc Communications and Networks （SECON）Boston：IEEE，2010：1-9.B43F9E47-26B5-44BC-8274-6197D0BDF388

[9]GAMMARANO N，SCHANDY J，STEINFELD LQ-SAND：A quick neighbor discovery protocol for wireless networks with sectored antennas[C]//2018 Ninth Argentine Symposium and Conference on Embedded SystemsCordoba：IEEE，2018：19-24.

[10]欧阳峰，刘强，郝琦，等基于定向天线的移动自组网技术研究综述[J].电视技术，2017，41（sup1）：148-153OUYANG Feng，LIU Qiang，HAO Qi，et alResearch summary of MANETs based on directional antenna[J].Video Engineering，2017，41（sup1）：148-153.

[11]SUDEVAN S，TOWSLEY D，GOECKEL D，et alNeighbor discovery in wireless networks and the coupon collector′s problem[C]//Proceedings of the 15th Annual International Conference on Mobile Computing and Networking[Sl]：[sn]，2009：181-192.

[12]TIAN Feng，LIU Bo，CAI Hao，et alPractical asynchronous neighbor discovery in Ad hoc networks with directional antennas[J].IEEE Transactions on Vehicular Technology，2016，65（5）：3614-3627.

[13]DU Jingzhe，KRANAKIS E，PONCE O M，et alNeighbor discovery in a sensor network with directional antennae[J]Ad-Hoc & Sensor Wireless Networks，2016，30（3/4）：261-286.

[14]MCGLYNN M J，BORBASH S ABirthday protocols for low energy deployment and flexible neighbor discovery in ad hoc wireless networks[C]//Proceedings of the 2nd ACM International Symposium on Mobile Ad Hoc Networking & Computing[Sl]：[sn]，2001：137-145.

[15]NUR F N，SHARMIN S，HABIB M A，et alCollaborative neighbor discovery in directional wireless sensor networks[C]//2016 IEEE Region 10 Conference （TENCON）Singapore：IEEE，2016：1097-1100.

[16]SOOD N，NAGARAJU S，V S，et alCollaborative neighbor discovery with slow scan for directional sensor networks[C]//2018 28th International Telecommunication Networks and Applications Conference （ITNAC）Sydney：IEEE，2018：1-3.

[17]洪亮，羅鹏涛，燕熊，等一种基于定向天线的蜂群组网邻居发现算法[J].西北工业大学学报，2020，38（1）：191-198HONG Liang，LUO Pengtao，YAN Xiong，et alA neighbor discovery algorithm for UAV networking based on directional antennas[J].Journal of Northwestern Polytechnical University，2020，38（1）：191-198.

[18]LIU Bo，RONG Bo，HU R Q，et alNeighbor discovery algorithms in directional antenna based synchronous and asynchronous wireless ad hoc networks[J].IEEE Wireless Communications，2013，20（6）：106-112.

[19]CAI Hao，WOLF TOn 2-way neighbor discovery in wireless networks with directional antennas[C]//2015 IEEE Conference on Computer Communications （INFOCOM）Hong Kong：IEEE，2015：702-710.

[20]景中源，曾浩洋，李大双，等定向Ad hoc网络中一种带冲突避免的邻居发现算法[J].通信技术，2015，48（5）：582-588JING Zhongyuan，ZENG Haoyang，LI Dashuang，et alA neighbor discovery algorithm with collision avoidance in Ad hoc networks using directional antennas[J].Communications Techno-logy，2015，48（5）：582-588.

[21]el KHAMLICHI B，NGUYEN D H N，el ABBADI J，et alCollision-aware neighbor discovery with directional antennas[C]//2018 International Conference on Computing，Networking and Communications （ICNC）Maui：IEEE，2018：220-225.

[22]ZHANG Zhensheng，LI BoNeighbor discovery in mobile Ad hoc self-configuring networks with directional antennas：Algorithms and comparisons[J].IEEE Transactions on Wireless Communications，2008，7（5）：1540-1549..B43F9E47-26B5-44BC-8274-6197D0BDF388