一种适于波束切换移动自组网的邻居发现改进算法

李 丽，郑博文，刘丽哲

(1.海军参谋部，北京 100000；2.中国电子科技集团公司第五十四研究所，河北 石家庄 050081)

0 引言

随着人们对业务需求的快速增长，对无线通信系统的通信速率、工作频段以及组网节点数量均提出了更高的要求，有学者预测每秒兆位链路在未来十年内将成为现实[3]，有学者建议第六代通信技术应用于太赫兹频段(0.1～10 THz)[4]。更高的载波频率带来了更高的空间损耗，全向天线通信系统也越来越无法满足通信覆盖要求；节点数量的增加，或者节点通信容量的增加都对移动自组网的容量提出了挑战。

综上所述，采用定向天线能够显著提高移动自组网网络容量，更好地满足业务对移动自组网提出的要求。

在定向天线移动自组网中，邻居发现是进行任何通信的前提，是指节点开机后，在没有邻节点任何先验信息的条件下，通过基于一定的互盲或自盲算法协议发现其一跳范围内的其他节点，同时被其他节点发现并建立通信连接的过程。由于定向天线的窄波束特性，节点必须在正确的时间、将正确的波束指向对方，而且彼此收发模式相反，才能有效通信，这给邻居发现算法带来了很大的挑战。另外，节点的移动、入网和离开网络等动作都会增加邻居发现算法的难度，因此研究定向天线移动自组网邻居发现算法十分有必要。

文中，首先讨论定向天线移动自组网邻居发现算法的研究现状[9-18]，然后指出现有基于波束扫描的邻居发现算法在波束切换移动自组网中存在的问题，并提出一种适于波束切换移动自组网的邻居发现改进算法。

1 定向天线邻居发现算法

定向天线移动自组网邻居发现算法可分为随机算法和同步算法两大类，随机算法是网络节点没有时钟同步情况下，每个节点收发波束、发送和接收状态独立随机选择；同步算法是在网络节点时钟同步的前提下，设计了一种机制让多个节点协同地进行收发波束、发送和接收状态选择。研究证明，同步算法的邻居发现性能优于随机算法，因此，基于同步的邻居算法研究文献居多，其中Xiong W[17]等人提出的基于扫描的邻居发现算法(Scan-Based Algorithm，SBA)性能优越，较为经典。该算法有如下假设：

① 每个节点配备定向扫描天线，波束宽度为α(0≤α≤2π)；

② 半双工通信方式，节点或处于发送模式，或处于接收模式；

③ 所有节点均通过GPS或其他方法精准同步，分为多个时隙，每个时隙又分为3个子时隙，用以实现3次握手；

④ 如果一个节点同时从多个邻居节点接收到信号，则认为发生冲突。

SBA算法的基本思想是：将扫描定义为一系列方向，并且每个扫描周期应覆盖全部天线方向，且不得重复。在每次扫描起始，节点以概率pt随机进入发送状态，并以概率1-pt进入侦听状态，节点保持收发状态不变，直到完成一次扫描；在发送时，节点通过在每个指定的方向上发送广播包；侦听时，节点也在指定方向上接收广播包，如果接收到广播包，则回复确认包。扫描时发射波束指向与接收波束指向相对，令θ表示发送节点波束指向，则θ′=(θ+π)mod2π表示接收节点波束指向，SBA算法扫描方案的一个例子如图1所示[17]。在时隙t1，节点1和节点2在0°方向上发送，节点3和节点4在180°方向上接收；在时隙t2，节点1和节点2在45°方向上发送，节点3和节点4在135°方向上接收，在时隙t2，节点2和节点3能够彼此发现。在一次扫描中完成360°扫描覆盖。

SBA算法以概率的方式选择收发状态，能够在一定程度上缓解一个定向波束中存在多个节点时，邻居发现帧冲突所引起的邻居发现失败和发现时间过长的问题。为了更好地解决该问题以缩短邻居发现时间，王昕羽[18]等人在SBA算法的基础上进行改进，提出了一种使用定向天线的Ad Hoc网络邻居发现算法，即引入静默机制，减小了同一波束角内节点握手信息碰撞的概率。经王昕羽等人改进后的邻居发现算法可使节点有效地发现邻居，节点间顺利建立一跳网络，同时，可根据节点的入网时间或已扫描次数，动态调整该节点进入静默状态的概率，使得邻居发现效率提高，节点入网建立网络连接的速度加快[18]。

图1 SBA算法收发方向示意图Fig.1 Overview of SBA

2 SBA算法的改进

2.1 现有SBA算法的问题

针对一个定向波束覆盖多个节点的情况，已有研究学者进行了深入研究[17-18]，但是在实际工程应用中，采用多波束切换实现全方位扫描是一种常见实现形式。为了保证多个定向天线能实现360°的覆盖以及波束边缘时的通信容量，定向天线波束宽度α(0≤α≤2π)与定向天线数量B，应满足α·B>2π。当邻居节点位于两个定向天线波束相重合的位置时，若采用基于扫描的方法会出现多个定向天线波束发现同一个邻居节点的情况，如图2所示，采用基于随机方法的情况如图3所示。

基于扫描的传统方法[17-18]在上述情况下会以波束扫描中最后一次实现握手的定向天线波束作为该邻居节点的通信波束，但是该波束不一定是信道质量最好的波束，从而影响通信质量。

图2 SBA方法多个定向天线波束发现同一个 邻居节点的情况示意图Fig.2 Problem of SBA when multiple beams find the same node

图3 基于随机方法多个定向天线波束发现同一个 邻居节点的情况示意图Fig.3 Problem of generic random neighbor discovery algorithm when multiple beams find the same node

2.2 改进算法

为了解决基于扫描的传统方法在多个定向天线波束发现同一个邻居节点时，无法选取最优波束的问题，本文提出了一种适于波束切换移动自组网的邻居发现改进算法。改进算法的基本思想是在王昕羽等人提出的SBA算法基础上增加接收信号质量评估机制，针对波束交叠区域，节点通过判定接收特征参数决定是否继续进行握手，选择最佳波束，从而避免当节点处于两个波束共同覆盖区域时选择了差的波束，增强网络的稳定性，改进后的算法与原算法邻居发现时间相同。

与SBA算法[17-18]一样，本文作出如下假设：

① 每个节点配备一副基于波束切换的多波束天线，实现360°覆盖，波束数目为B，每个波束的宽度为α(0≤α≤2π)，满足α·B>2π；

② 每个节点配备测向和授时设备，例如GPS/北斗或电子罗盘等；

③ 半双工通信方式，节点或处于发送模式，或处于接收模式；

④ 如果一个节点同时从多个邻居节点接收信号，则会发生冲突。

本文提出的改进算法时隙设计如下：整个时隙周期包含邻居发现阶段和数据阶段，其中邻居发现阶段包括3次扫描过程，每次扫描由B个时隙构成，完成对360°范围内的扫描，每个时隙进一步分为3个子时隙。时隙结构如图4所示。

邻居发现阶段扫描方式设计如下：在一次扫描起始之前，每个节点以pt的概率作为主动扫描节点进行主动发送，以概率1-pt作为被动收听节点对信道进行侦听接收。选择主动扫描的节点将在后续B个时隙，于每一个时隙的第一子时隙发送邻居发现帧1(Neighbor Discovery 1,ND1)，其中ND1中包含本机节点号；选择被动收听的节点将在后续B个时隙，于每一个时隙的第一子时隙收听信道。以B=16时为例，图5为邻居发现阶段主动扫描节点和被动扫描节点的扫描流程详细说明。

图4 时隙结构Fig.4 Time slots

图5 动态邻居发现示意图Fig.5 Overview of the proposed modified SBA

对16个定向天线进行编号，与电子罗盘参考基线方向对齐的波束定为1波束，按照逆时针方向对16个定向天线依次编号；根据正北方向与电子罗盘的参考基线方向的顺时针夹角计算主动扫描节点在当前时隙的第一子时隙发送ND1帧的定向天线编号，并通过此定向天线发送ND1帧；计算主动扫描节点在当前时隙的第一子时隙发送ND1帧的定向天线编号为：

式中，S为主动扫描节点在当前时隙的第一子时隙发送ND1帧的定向天线编号，θ为电子罗盘参考基线方向与正北方向的顺时针夹角，i代表定向天线编号。

具体发现过程如下：

步骤1：根据发送ND1帧的定向天线编号计算被动收听节点在当前时隙的第一子时隙侦听ND1帧的定向天线编号，并通过此定向天线侦听ND1帧，如果被动收听节点在当前时隙的第一子时隙侦听到了ND1帧，则计算ND1帧的接收功率并解析ND1帧中的节点号，执行步骤2；如果被动收听节点在当前时隙的第一子时隙未侦听到ND1帧，则转入步骤5；被动收听节点在当前时隙的第一子时隙侦听ND1帧的定向天线编号为K=(S+8)mod16，其中，K为被动收听节点在当前时隙的第一子时隙侦听ND1帧的定向天线编号，AmodB代表A除以B的余数。

步骤2：将接信噪比(SNR)和当前TDMA周期内该节点的累计接收SNR最大值进行比较，如果接收SNR不小于该节点的累计接收SNR最大值，则更新该节点的累计接收SNR最大值，并在当前时隙的第二子时隙回复ND2帧，执行步骤3；如果接收功率小于该节点的累计接收SNR最大值，则转入步骤5；其中，该节点为当前时隙接收到的ND1帧中的节点号所对应的节点，ND2帧中包含自身节点号，累计接收SNR最大值的初始值设置为零。

步骤3：如果主动扫描节点在当前时隙的第二子时隙收到ND2帧，则在当前时隙的第三子时隙回复ND3帧，执行步骤4；如果主动扫描节点在当前时隙的第二子时隙未收到ND2帧，则转入步骤5。

步骤4：被动收听节点在当前时隙的第三子时隙接收并读取ND3帧。

步骤5：判断当前时隙的时隙号是否为16，如果是，则累计接收功率最大值所对应的波束即为所选波束，结束本流程；如果不是，则等待进入下一时隙，转入步骤4。

现以具体实例对改进算法进行说明，如图6所示，节点1为主动扫描节点，节点2为被动侦听节点。在时隙1，节点2收到节点1的ND1帧，接收信噪比为snr1，记录当前节点1的累计最大接收信噪比为Max1=snr1，并在接下来的时隙ND2和时隙ND3完成与节点1的3次握手；在时隙2，节点2收到节点1的ND1帧，接收信噪比为snr2，其中snr2Max1，并在接下来的时隙ND2和时隙ND3完成与节点1的3次握手。

图6 一种适于波束切换移动自组网的邻居发现改进算法举例Fig.6 Example of the proposed algorithm

3 改进算法性能仿真及分析

为了验证本文提出的适于波束切换移动自组网的邻居发现改进算法的有效性，用python对该算法进行了仿真，仿真中心频率为4 GHz，发射机输出功率40 dBm，仿真中用于邻居发现的信令帧接收灵敏度为-105 dBm，仿真场景采用20 km×20 km的正方形区域，随机在20 km×20 km的区域产生16个节点，随机产生每个节点的基线方向，仿真节点分布如图7所示。

图7 仿真节点分布图Fig.7 Scatter of nodes in 20 km×20 km square

天线采用4阵元、6阵元和8阵元平面天线，天线方向图如图8所示，可以看出4阵元天线3 dB波束宽度约为35°，6阵元天线3 dB波束宽度约为23°，8阵元天线3 dB波束宽度为17°。下面分别在4阵元、6阵元和8阵元平面天线，用α代表交叠波束和波束宽度比值，在α为1/4和1/8情况下，对本文提出的邻居发现改进算法的累计平均接收电平与传统SBA[18]算法进行比较。

图8 单波束天线方向图Fig.8 Radiation pattern of single antenna beam

在上述仿真场景和参数设置情况下，将本文提出的邻居发现改进算法的接收电平累计概率分布与传统SBA[18]算法进行比较，如图9、图10和图11所示。其中横坐标为接收信号强度，纵坐标为累计分布函数(Cumulative Distribution Function,CDF)。

图9 4阵元累计平均接收电平对比Fig.9 Cumulative reception level equipped with 4-element antenna

图10 6阵元累计平均接收电平对比Fig.10 Cumulative reception level equipped with 6-element antenna

图11 8阵元累计平均接收电平对比Fig.11 Cumulative reception level equipped with 8-element antenna

由图 9、图 10和图 11可以看出，本文提出的邻居发现改进算法的累计平均接收电平相较于传统SBA算法提高约15 dB，可支撑更高的通信容量、或增强网络的稳定性；随着天线阵元数量增多，天线增益变大，传统SBA算法选择的非最优波束的概率在逐渐增加，例如，在交叠波束占波束宽度1/8时，在4阵元、6阵元和8阵元时分别为60%，80%，90%，而本文提出的改进算法始终能选择最优波束，具有更高的网络容量，且随着天线阵元数量增多，网络吞吐量的提升越大。

4 结束语

本文针对基于多波束切换的移动自组网在波束交叠的情况下，邻居发现过程无法选择最优通信波束的问题，提出了一种适于波束切换移动自组网的邻居发现改进算法，该算法在基于扫描的邻居发现算法的基础上通过接收信号质量评估选择最佳波束。仿真结果表明，在波束交叠情况下，采用本文提出的改进算法，系统能够选择最优通信波束，累计平均接收电平优于传统的基于扫描的邻居发现算法，并且单波束宽度越窄、波束交叠占波束宽度的比例越大，网络吞吐量提升越明显。