一种定向无线自组网邻居发现算法*

胡郑峰，王 建

(中国船舶重工集团公司第七二四研究所，南京 211106)

0 引 言

采用定向天线波束扫描的无线移动自组网技术，空间复用度和信道利用率高，节点间通信距离远，同时节点间的定向传输信道大大降低了通信信号被截获与干扰的风险，是现代无线移动自组织网络技术研究的重点[1]。

节点邻居发现是无线移动自组网建网的第一步，组网前首先需要开机进行各节点邻居搜索，建立邻居节点表之后，才能申请加入已有网络或新建网络。采用定向天线时，由于节点搜索波束很窄，相邻节点如何在短时间内完成波束对准成为邻居发现过程中的难点[2]。现有基于定向天线的邻居发现算法的研究中，通常假定节点携带GPS等同步设备，可预先完成时间同步[3-4]，这对节点组网设备要求较高，在许多实际应用场景中难以实现。而针对节点时钟异步的发现算法，节点的波束方向与收发模式大多采用随机选取的方式[5]，这对节点初始协调要求较低，但各节点随机选取波束方向与收发状态容易导致发现总时长波动较大，有时会造成严重的时长拖尾问题。文献[6-7]通过构建特殊的节点波束扫描方向序列，可以在确定周期内完成任意两节点的波束对准，但都没有同时确定相应的节点收发模式，在随机收发模式下不具有稳定的搜索时长上界。文献[8]研究了基于网格式quorum系统的确定性邻居发现算法，利用quorum系统的旋转封闭特性，可以实现异步网络中的节点波束稳定交会，其发现时长与天线波束数量成正比。但该算法需采用多波束天线，要求节点天线能同时进行发送与接收，这对节点设备要求较高。此外，在节点间时延差较大时，该算法性能较差。文献[9]对常用的SAND协议进行改进，通过令牌判定当前进行邻居发现的主节点，主节点经过轮询完成邻居发现后将令牌传递给下一节点，直到遍历完所有节点。该算法通过引入扇区方位信息，减少扇区组合数目，提高了节点发现效率。但由于令牌传递机制，其完成邻居发现所需时长与全网节点数成正比，在节点数较多时耗时仍然较长。

针对这些问题，文献[10]提出了一种确定性邻居发现算法，将基于二进制编码的收发序列应用于采用定向发送、全向接收天线的无线组网系统，通过规律性改变收发序列的方法，使其可以在异步系统中完成节点的邻居发现。本文将二进制编码序列收发模式扩展应用到发送和接收全部采用定向天线的无线移动自组网系统中，针对不同时延情况下对编码序列的选择要求，给出了确定的天线扫描策略和采用一种二进制编码序列的收发状态切换模式，可以满足节点不同时间差的异步发现要求。与未确定收发模式的异步邻居发现算法相比，本文所提算法具有更短的平均搜索时间与更小的搜索时间上界。

1 邻居发现过程

在本文中，假设无线自组网中的节点具有如下性质：

(2)所有节点采用半双工方式通信，每个时刻节点只能处于发送或接收中的一个模式。只有当两个节点处于通信距离内，波束扇区互相指向对方，且一个处于发送模式，另一个处于接收模式，才能进行通信。节点以特定的方式选择其发送与接收状态，称为收发模式。

(3)节点无需GPS等同步设备进行提前时间同步，节点在开机时处于时间异步状态。

(4)节点采用频分多址，各节点随机在M个载频上选择一个载频发送信息。

如图1(a)所示，A、B两节点当且仅当其波束相互对准且收发状态互异时可以成功发现。图1(b)中两节点未处于一发一收状态或图1(c)中两节点波束未相互对准都会导致发现失败。同时，如图1(d)所示，当同一时隙有两个发送节点向同一接收节点发送数据包时，数据包会发生碰撞，如果未采用频分多址或码分多址等方式进行规避，会使两个发送节点与接收节点发现失败。

图1 节点邻居发现示意图

从图1可以看出，邻居发现问题的关键在于设计节点收发模式与天线波束扫描策略，使其从开机扫描到相互发现的时间更短，同时尽可能减少节点之间的碰撞。

2 基于二进制编码序列的邻居发现算法

2.1 算法原理

2.1.1 收发模式编码序列

规定每个节点配备独立的二进制编码，节点随时间顺序按位选择二进制编码序列的码字，一个码字持续时间为tcode，以此确定每个时隙的节点收发模式：码字为 1 时，节点进入发送模式，发送邻居发现信息；编码为0时，节点处于接收状态。不同编码示例对应的收发模式如表1所示。

表1 节点编码对应收发模式

在节点时间同步情况下，当任意两节点二进制编码间的汉明距离大于1时，必定存在一个码字时间，节点对处于一发一收状态。

2.1.2 波束扫描策略

在基于二进制编码序列确定收发模式基础上，引入天线波束扫描策略。设编码长度为L，天线扇区数为K，用时隙tslot表示波束指向最短驻留时间切片的长度，一个码字持续时间tcode为K×K个时隙。当节点进入接收状态时，接收波束按逆时针方向扫描，每个扇区内驻留K个时隙。当节点进入发送状态时，发送波束同样按逆时针扫描，每个扇区内驻留1个时隙。

在一个码字持续时间内，发送节点与接收节点的波束扫描方式如表2所示。

表2 节点波束扫描方式

在节点时间同步情况下，由于接收节点的接收波束在一个方向驻留时间内，发送节点的发送波束可以完成所有方向的扫描，因此在接收节点的接收波束进行全方位扫描过程中，发送节点的波束覆盖扇区与接收节点的波束覆盖扇区完成相互对准的遍历，收发波束相互波束对准概率为1。结合二进制编码收发模式，可以确保任意节点对相互发现的最大时长tsyn为

tsyn=L×K×K×tslot。

(1)

2.2 异步收发编码设计

在定向收发无线网络内各节点之间时间异步时，仅两两间汉明距离大于1的二进制编码序列，无法满足节点间收发模式互异的要求，需要对序列组做出改进。下面对节点间不同异步情况分别进行分析。

2.2.1 旋转相似性

当节点之间的时钟差Δt为一个编码时间长度的整数倍时，即

Δt=m×tcode=m×K×K×tslot。

(2)

式中：m为任意整数；K为节点天线扇区数目。引入旋转相似的定义：设序列A长度为L，定义rotate(A,i)为

rotate(A,i)={A((i+1)modL),A((i+2)modL),…,

A((i+L)modL)}。

(3)

对长度为L的序列A和B，若

∃i∈{0,1,…,L-1}:rotate(A,i)=B，

(4)

则称序列A与B旋转相似，记为Rsimilar(A,B)=1；若序列组M中任意序列都不旋转相似，记Rsimilar(M)=0。

当两节点的收发模式编码序列旋转相似时，可能会因为时延导致两节点的码字在同一码字时间内始终相同，无法进入收发互异状态，从而导致永远无法相互发现。因此收发编码序列设计时，要避免序列组内任意两序列出现旋转相似，才能作为节点的收发编码序列。

2.2.2 旋转互异性

当节点间时钟相差Δt为时隙长度的整数倍时，即

Δt=m×tslot。

(5)

式中：m为任意整数。引入旋转互异性的定义：对二进制序列A和B，令Ar=rotate(A,i)，其中i∈{0,1,…,L-1}。令Ar(l)表示序列Ar第l个码字，若∃l1,l2∈{0,1,…,L-1}，满足

(6)

则称序列A与序列B旋转互异，记为Rdiffer(A,B)=1；若序列组M中任意序列都旋转互异，记Rdiffer(M)=1。

对时钟异步且编码长度为L的两个节点I、J，不妨设节点J在一个收发编码内进入扫描扇区时间滞后于节点I，令I(tcode_n)、J(tcode_n) 分别表示两节点原本在码字时间tcode_n内的码字。当两节点序列相互旋转互异时，∃tcode_1,tcode_2∈{0,1,…,L-1}，满足

(7)

由于两节点开始进行波束扫描的时间差Δt以I节点时钟为时间基准，在编码时间tcode_1内，虽然I节点由于节点间时差导致天线波束扫描扇区的前n个扇区未能与J节点交会，但J节点原本应在tcode_2-tcode码字时间内扫描的后n个扇区，却因滞后可以在tcode_2码字时间内与节点I的前n个扇区交会。当序列满足该性质时，无论节点间时延相差多少，总能实现扫描扇区的交会，如图2所示。

图2 旋转互异序列扇区交会示意图

2.2.3 一种二进制编码序列构建方法

当序列组同时满足旋转相似与旋转互异性时，可以选择其作为二进制编码异步邻居发现的收发编码序列组。一种满足两条性质的序列组的构建方法如下：

(1)设节点数为N，为每个节点配置唯一且长度相同的数字ID，设其大小为nnode；再将ID转为二进制，长度为L,L>2。如数字6，二进制表示为110，此时序列组虽然相互汉明距离大于0，但不满足之前讨论的两种性质。

(2)在已生成的二进制编码序列后增加L位，新增的L位序列取值为节点数字编号加2的二进制形式，当nnode+2>2L时，新增编码为(nnode+2)mod(2L)，新序列长度为2L，新生成的序列组记为[N|N+2]。例如ID为6的节点，其二进制编码为110000。

通过仿真验证，序列组[N|N+2]满足旋转互异性，同时序列组内所有序列两两间都不旋转相似，因此在节点时间异步情况下，可以采用该编码方法产生节点邻居发现的收发编码序列。

2.3 波束扫描策略设计

针对上述收发编码邻居发现算法，相应的天线波束扫描策略需进行如下调整：

(1)节点在开机后，随机选择两个方向，分别作为发送波束起始方向与接收波束起始方向，之后按逆时针方向扫描，在完整的2L×K2×tslot编码周期内，每次进入发送或接收状态的起始波束方向不变。

(2)节点每经过长为2L×K2×tslot的收发编码周期，重新选择发送波束与接收波束的起始方向。

节点i在时隙tslot_n内扇区方向S(i,t)满足

(8)

式中：tslot_n为最先开机节点的时隙，作为时钟基准；delayi为i节点与时钟基准的开机时间差；kt、kr分别为节点随机选择的初始发送接收扇区方向，每隔一个编码周期重新随机选择；u(i,t)为tslot_n时隙内节点i的编码。

采用该序列的节点一个完整的收发编码周期为2L×K2×tslot，其中，K为节点扇区数目，tslot为时隙长度。在不考虑碰撞情况下，以先开机节点的开机时间为起始，节点间开机时间差为Δt，任意两节点发现时长的上界tdiscover_max为

tdiscover_max=Δt+2L×K2×tslot。

(9)

2.4 碰撞概率分析

当接收节点同时收到多个发送节点的数据包时会产生冲突，造成接收失败，称为波束碰撞。在任意时隙，由于其发送节点初始波束方向随机，所以相邻发送节点间波束方向同时指向同一接收节点的概率为1/K，当扇区数越大时，相邻节点之间波束碰撞的概率越小。

由于节点组合不同的空间分布以及各节点在空间中处于不同位置，其每个扇区内包含的节点数目不同，节点在每个扇区内发生波束碰撞的概率也不相同。为简化场景，设在同一时刻，一个接收节点在其接收扇区范围内有c个相邻节点处于发送状态，c的大小与节点的空间分布形状、节点密度以及通信距离有关。设c个节点随机分布于接收节点周围，节点采用频分多址，载频数为M，扇区数为K,则一个接收节点A在与其中一发送节点B进行扇区交会时，与其他发送节点不发生碰撞的条件如下：

(1)其他发送节点位于其他扇区，此时不会发生碰撞，令psector(0)为该情况发生的概率，则有

(10)

(2)其他c-1个节点中有v个节点与发送节点B位于一个扇区内，v≤c-1，令psector(v)为该情况发生的概率，则有

(11)

此时，其余v个节点的载频都与发送节点B不同，发送节点B的信息传输不会发生碰撞。令pf(v)为该情况发生概率，则有

(12)

综上所述，节点A在一次波束交会中，正确发现的概率p(c,K,M)为

(13)

以c=4，K=16，M=4为例，在相邻节点的一次发现过程中，成功发现的概率为95.39%。节点每过一个编码周期，初始波束扫描方向会重新随机选择，避免前一周期波束碰撞的两个发送节点在下一周期继续发生碰撞。令一个周期内碰撞概率为pcollide，连续n个周期都发生碰撞的概率为pncollide，当pcollide较小时，两个周期同时发生碰撞的概率很低。

2.5 节点工作流程

节点开机后，首先选择初始收发波束方向，并判断第一位编码码字：码字为1，进入发送状态，每个时隙旋转一次发送波束方向；码字为0，进入接收状态，每K个时隙旋转一次接收波束方向。每过K2个时隙，节点进入下一位编码，直到经过2L位编码码字后，结束一个波束扫描搜索周期。若要继续进行扫描搜索，则重新选择初始收发波束方向后，开始下一个周期的波束扫描搜索，直到搜索时间超过预定搜索时长上限，结束搜索。节点的搜索流程如图3所示，St与Sr分别为发送节点与接收节点的初始波束方向，t为当前搜索时隙，k为波束方向计数，K为扇区总数，i为码字位数标记，t_end为搜索时间上限。

图3 节点搜索方式流程图

3 仿真结果分析

为了验证基于二进制编码的邻居发现算法的性能，采用Matlab仿真平台对节点的单次发现概率、发现的平均时长和总时长等性能进行仿真分析，并与文献[7]提出的确定性发现算法(简称算法1)进行比较。算法1通过节点ID规定了确定的扇区扫描序列，异步状态下可以在固定周期内完成节点间任意扇区对的汇聚，但其未对节点的收发状态做出约束。在下列仿真中采用随机选择的方式来确定收发状态，进入接收与发送状态的概率都为0.5，同时假定节点的分布随机且时间同步误差随机。两种算法均进行1 000次蒙特卡洛仿真，然后取结果的平均值进行比较分析。主要仿真参数如表3所示。

表3 主要仿真参数设置

3.1 波束交会时长

两种算法的波束交会时长随扇区数变化和随ID位数变化情况的仿真结果分别如图4(a)和图4(b)所示。两种算法都基于节点唯一ID确定波束扫描策略，节点的初始ID均从0开始选取，N个节点的ID的二进制编码长度L取最小值⎣lbN」。

(a)扇区交会时长随扇区数变化(ID位数为4)

(b)扇区交会时长随ID位数变化(扇区数为8)图4 波束交会时长比较

由图4可以看出，在节点初始ID长度相同时，两种算法的波束交会时长都随扇区数K的增大而增大，且增长的速度与K2近似成正比关系，本文的算法在波束交会平均时长与最大交会时长上都小于算法1。在节点扇区数相同时，两种算法的波束交会时长都近似与节点初始ID位数成正比，本文算法在ID位数为3～7位时，波束交会时长性能优于算法1。这是由于当ID位数较大时，本文的交会时长与2L成正比，算法1波束交会时长近似与1.5L+3成正比，当ID位数更大且扇区数相同时，其波束交会时长可能更短。

3.2 单次交会发现成功概率

由于两算法在各自扫描周期内完成波束交会的概率都为1，但在不同扇区数目与邻居节点数目下，当两相邻节点波束交会时，两种算法可以成功发现的概率(即处于收发互异状态且未发生节点碰撞的概率)存在较大差异，如图5所示。

(a)发现概率随扇区数变化(Nnei=8)

(b)发现概率随邻居节点数变化(扇区数为8)图5 波束交会时发现成功率比较

设节点的邻居节点数为Nnei，由图5可以看出，当Nnei固定时，相邻节点在一次波束交会中发现成功的概率随扇区数的增大而增大。各发送节点发送波束方向随机，扇区数的增加会使得其余发送节点波束方向与当前通信节点冲突的概率降低，从而使得发现成功率上升。而当扇区数K固定时，空间中邻居节点数越大，发生碰撞的概率越大，一对节点在一次波束交会中能够成功发现的概率将变得越低。

同时可以看出，本文算法邻居节点对在一次交会中成功发现的概率约为算法1的2倍。这是由于算法1在扇区交会时未确定节点收发状态，采用随机收发模式，扇区交会时收发状态互异的概率期望为0.5；本文算法由于首先确定收发模式，再进行扫描策略设计，收发互异的概率为1。

3.3 邻居发现时长

对多节点网络进行完整的邻居发现所需时长的仿真结果如图6所示，其中分别给出了在不同扇区数与节点数目下网络中各个节点分别完成所有邻居发现的平均时长与网络完成所有节点邻居发现的总时长。假定节点间通信距离与扇区数K成正比，节点波束越窄，通信距离越远，其可发现的邻居节点越多，扇区数为32时通信距离为最大。

(a)邻居发现时长随扇区数变化(节点数为32)

(b)邻居发现时长随节点数变化(扇区数为12)图6 邻居发现时长比较

由图6仿真结果可见，本文算法在完成全网邻居发现的最大时长和各节点平均时长上，性能均较算法1有较大提升，在不同扇区数和不同节点数目下，都能将发现时长缩短一倍左右。这是因为本文提出的方法在波束交会间隔略优于算法1的情况下，通过联合设计确定节点收发模式，将每次交会时的节点发现概率较采用随机收发模式提升了近一倍，仿真结果与理论推导一致。

4 结束语

本文针对定向天线无线自组织网络的特点，提出一种适用于定向发送定向接收天线无线移动网络，具有确定性搜索时间上界的邻居发现算法。该算法通过每个节点独立ID生成的二进制编码来确定节点收发模式，同时给出收发节点的波束扫描策略，可以实现时隙异步节点的邻居发现。仿真结果表明，通过设计特定编码序列和波束扫描策略，可以实现节点间确定时间内的波束交会，同时通过与收发模式联合设计，在存在时间异步与相邻节点碰撞情况下，较随机收发模式下的邻居发现算法在发现耗时性能上有较大提升。

由于本文算法要求网络中各节点的天线初始配置相同，在各节点天线波束宽度或最大通信距离不同时，基于二进制编码序列确定的网络节点收发模式及天线扫描策略有待进一步研究。