定向自组织网络中一种基于双令牌的非同步邻居发现协议

2021-03-02张航李波闫中江李心茹杨懋秦建存

西北工业大学学报 2021年1期

关键词：扇区全网波束

张航, 李波, 闫中江, 李心茹, 杨懋, 秦建存

(1.西北工业大学电子信息学院, 陕西西安 710129;2.中国电子科技集团公司第五十四研究所, 河北石家庄 050081;3.中电网络通信集团有限公司, 河北石家庄 050081)

定向自组织网络是采用定向波束进行通信的自组织网络。因为定向波束带来的窄波束、高增益特性,使定向自组织网络具备了单跳传输距离远、传输速率高、抗干扰能力强的优势。

定向自组织网络的挑战在于其采用了定向窄波束进行通信,各通信节点在进行有效通信之前,需要先进行基于窄波束的邻居发现,确定周围具体有几个邻居节点存在,并识别所在波束。如果各邻居节点在非同步条件下完成此项工作,则尤为困难。

现有研究按照是否存在统一的同步信息,可分为基于全网同步的发现算法和全网非同步邻居发现算法。非同步邻居发现算法不依赖统一的外同步源授时,具有重要的研究价值。

SAND协议是一种基于全网非同步下的邻居发现算法,采用令牌(Token)传递的形式依次进行邻居发现,在之后Q-SAND等协议在此基础上进行了改进,其基础同样是基于Token传递完成的。该类型协议的问题是邻居发现时间长,Token需要被所有节点持有,并顺序进行邻居发现,邻居发现时间和全网节点数是呈线性正比关系。

本文提出了一种基于双Token的定向自组织非同步邻居发现协议,在发现过程中,以不互相干扰为原则,产生双Token,由双Token持有节点并行完成邻节点发现,从而缩短全网完成邻居发现的时间。

主要贡献点:

1) 针对非同步下的定向波束邻居发现问题,提出了一种双Token协议,相比单Token协议,全网邻节点发现效率得到提升。

2) 进行了理论分析,分析了双Token干扰避免的条件,验证了双Token传递的可行性和有效性。

3) 完成了仿真,对双Token协议与单Token协议进行了对比分析,可以看到双Token较单Token协议节省了全网邻节点发现时间。

1 研究现状

按照节点的时钟状态,可以将邻居节点发现协议分为同步邻居节点发现和异步邻居节点发现。

文献[1]提出的SAND(sectored antennas neighbor discovery)协议是一种基于扇区天线的串行化邻居发现协议,不同节点在异步条件下完成邻居发现,为了避免节点之间的冲突干扰,采用Token传递机制协调不同节点的工作过程,只由当前的Token持有节点执行邻居节点发现。该协议中的节点均采用扇区可切换的定向天线,节点之间不需要进行全局时间同步,即可以完成全定向扇区天线的节点间邻居发现。是当前用于全定向波束邻居发现的一种先进有效的协议机制。

基于SAND协议,文献[2]中提出了一种Q-SAND(quick SAND)协议,对SAND协议进行了改进,以减少邻居发现时间。文献[6]提出了DANDi协议,在Hello-Reply阶段提出了一种时隙分配的优化方法。

以下重点对SAND协议和Q-SAND协议进行介绍。SAND协议的协议操作主要分为3个阶段,包括:①吸引邻居的注意;②Hello-Reply过程;③令牌传递或释放。具体的操作过程如下:

1) 吸引邻居的注意

该阶段又称为Hone-In阶段。Token持有节点在该阶段依次向自己的每个扇区方向发送一系列的Hone-In消息,提醒收到该消息的节点即将进行邻居节点发现。Token持有节点的邻居节点处在快速扫描模式,周期性遍历自己的每个扇区,在收到该Hone-In消息后,邻居节点将停止扫描,保持扇区指向Token持有节点,并启动计时器,在一定时间后与Token持有节点同时进入邻居节点发现阶段。

2) Hello-Reply过程

在Hone-In阶段结束后,所有收到Hone-In消息的潜在邻居节点切换到第一个扇区,Token持有节点开始通过轮询邻居并在随后的若干时隙等待它们的响应来发现它的邻居。这种双向握手方式可以确保发现节点之间的双向链接。在Hello-Reply过程中,Token持有节点和它的潜在邻居节点都按照预先确定的顺序(顺时针或逆时针)依次遍历其K个扇区,确保对所有的扇区组合方式进行测试,以便于选出最好的通信链路。SAND协议中一个Token持有节点的Hello-Reply过程需要尝试K2种扇区组合方式。

3) 令牌传递或释放

令牌传递或释放又称为Token Passing或Token Releasing。Token持有节点完成前2个阶段后,会根据自身和周围邻居节点状态选择进行令牌传递。令牌传递的目的节点是下一跳未持有过Token的节点或者是自己的父节点。令牌释放则是针对当前拿到Token的节点已持有过Token即已经完成邻居发现的状态所执行的一种释放机制,以将Token交回初始节点。

当Token回到第一个Token持有节点,且网络中所有的节点都已持有过Token时,全网的邻居节点发现过程结束。

Q-SAND协议引入了扇区方位,依靠方位信息,对于扇区个数K为偶数的节点,只需要尝试K种扇区组合;对于扇区个数K为奇数的节点,需要尝试2K种扇区组合,即可以找到与邻居节点的最佳匹配扇区,与SAND协议中尝试K2种扇区组合相比,Q-SAND协议可以减少Hello-Reply阶段的通信开销提高节点发现效率。在其他阶段与SAND协议保持一致。因此Q-SAND协议的邻居发现总时间相比SAND协议得到提升。

2 系统模型

定向自组织网络的节点相互之间对等,在本协议中根据邻居发现时的角色定义了若干节点类型,分别是:

主Token持有节点(master token holder,MTH):该节点当前持有主Token,主动进行邻居节点发现,完成相应流程后,将主Token传递给下一个目标节点。下一跳的MTH称为nMTH。

从Token持有节点(slave token holder,STH):该节点当前持有从Token,进行邻居节点发现,完成相应流程后,将从Token销毁。

主Token持有节点的父节点(master token parent,MTP):当前主Token持有节点的上一级Token来源节点。该节点传递主Token给下一跳节点之后转换为NN节点,在接收到启动信息后才按照该角色进行工作。

邻居节点(neighbor node,NN):除MTH、STH、MTP之外的节点统称NN节点,如上所述MTP启动之前也为NN节点。

每个通信节点均由K个定向扇区天线组成,但需要注意实际的定向波束方向图不是理想的,旁瓣仍然有增益,但一般会显著小于主瓣增益。定义R为单跳最大通信距离。

通信节点依靠邻居发现可定位到周围的邻居节点及其所在的波束,在通信时,波束可以快速调整到需要通信的节点方向完成通信。

所有节点在存在方位信息的情况下,通信节点将指向正北方向的扇区定义为扇区0。节点之间的扇区连线存在如下关系:

定义Ka为图1左扇区图的某一个扇区,Kb为右扇区图与左扇区图连线上的扇区。

图1 在K为偶数时,扇区之间的连线关系

K为偶数时,Kb=mod(Ka+K/2)。如图1所示,K为6,扇区Ka为1,所对应的Kb为4。该连线关系反映了节点通信时,扇区波束的相互匹配关系。

图2 在K为奇数时,扇区之间的连线关系

如图2所示,K为奇数时,Kb=mod(Ka+(K+1)/2)或者Kb=mod(Ka+(K-1)/2)。出现2种对应关系主要是由节点对之间相对位置不同造成的。

在后续进行计算和仿真时,为简单起见假定扇区K为偶数。当K为奇数时,需要考虑图2中的2种情况。

3 协议描述

3.1 协议机制

D-SAND协议的核心思想是提出了一个基于双Token的邻居发现协议,持有双Token的节点可并行工作,解决由于单Token依次传递带来的发现慢的问题。主Token持有节点(MTH)完成发现过程后,把主Token传递给nMTH,同时将nMTH的位置信息告知MTP,接着由MTP查看是否存在与nMTH距离大于2R的邻节点(R为单跳节点最大通信距离),如果存在则由MTP产生临时的并发Token,并传递给该节点进行邻居发现。

由于从Token是在主Token传递过程中临时产生的,接下来以MTH为主线介绍D-SAND协议整体工作流程。图3给出了MTH进行邻居发现时的基本帧结构，其中包括Hone-In阶段、Hello-Reply阶段和主Token传递阶段。

图3 MTH的基本帧结构示意图

此外，与MTH类似，STH也有Hone-In和Hello-Reply阶段,其工作过程是相同的,而STH完成Hello-Reply后进行从Token销毁。对于已经完成了邻居发现的节点，再次收到主Token时执行Token释放机制。

1) Hone-In阶段

MTH在每个扇区周期性的广播h个Hone-In消息,其周期为tHone-In,以此来吸引NN节点的注意,并使邻节点与MTH保持一个初步的同步。为了保证在该扇区下的NN节点都能够收到消息,NN节点扇区切换速度比MTH扇区切换快,即NN节点扇区切换时间tswitch应大于tHone-In。h应满足

h≥Ktswitch/tHone-In

(1)

为了保证NN节点能够完整接收Hone-In消息,取tswitch=2tHone-In有

h≥2K

(2)

MTH在Hone-In阶段总计发送hK个Hone-In 消息(K为扇区数量)即进入Hello-Reply阶段。Hone-In消息中包含了启动下一阶段剩余的消息分组个数,NN节点在收到Hone-In消息后将自己的工作扇区指向MTH,并依据剩余消息分组个数启动计数器倒计时,倒计时计数到零后,所有的NN节点进入Hello-Reply状态。

2) Hello-Reply阶段

该阶段的主要目的是发现周围邻居节点与MTH所在扇区,并形成一个可通信的邻居表。

MTH在每个扇区周期性的广播Hello 包,NN节点基于与MTH的扇区对应关系进行接收,并在收到Hello包后进行回复。回复过程NN节点分时隙进行,时隙数量为Nslots,并随机选择一个时隙进行回复,以减小多个节点同时回复带来的碰撞概率。完成一轮Hello-Reply之后,启动下一轮,轮数为Nrounds,以让所有的NN节点能够被MTH发现。

在该阶段结束时,NN节点的扇区工作波束指向MTH。

3) Token传递阶段

Token传递阶段(Token Passing, TP)主要包括:主Token传递和从Token传递的过程。图4给出了MTH、MTP、STH和NN 4种节点类型的转换关系。

图4 MTH、MTP、STH和NN 4种节点类型的转换关系

(1) 主Token传递

MTH在完成Hello-Reply阶段后形成邻居表,该邻居表用Nm表示。该表记录的信息有:邻居节点号、邻节点所在扇区和其位置信息,并标记出不同的邻居节点类型:第一类为未完成邻居发现的节点,为可能的nMTH集合;第二类为已经完成邻居发现,但未持有过主Token的节点(成为过STH,并销毁了从Token);第三类为已完成邻居发现且持有过主Token的节点。

MTH的主Token传递对象首先从邻居表中的第一类节点集合中选择,作为nMTH;否则从第二类节点集合中选择;如果前2类节点均不存在,则将主Token传递给MTH的父节点。

MTH在主Token传递阶段向所有扇区依次广播GoToFastScan 消息。该消息的主要作用是使得MTP和下一跳Token持有节点之外的邻居节点回到快速搜索状态,如果存在nMTH的情况下启动MTP,并将主Token传递给nMTH,如果不存在nMTH则不启动MTP,意味着不具备从Token产生的条件。

GoToFastScan消息中包含: MTH的邻居表、NN节点快速扫描指示、MTP启动指示、nMTH的ID号和位置信息。如果需要启动MTP,则GoToFastScan消息先向MTP所在扇区发送,收到该消息后,MTP启动从Token产生决策机制,同扇区的其他NN节点则进入快速扫描状态。之后MTH依次指向其他扇区继续发送消息。主Token下一跳节点也会在所在扇区收到GoToFastScan消息,MTH在该扇区发送完GoToFastScan消息后,接收返回的ACK,确保主Token正确传递了出去。每一条GoToFastScan消息中均含有一个倒计时器,用于下一跳主Token持有节点在收到消息后,计算还有多长时间启动工作。

(2) 从Token传递

MTP本身维护了一张自有邻居表(Np),MTP接收到GoToFastScan消息之后,提取MTH的邻居表(Nm)。

MTP决策是否可以产生从Token过程如下:

将Nm和Np进行对比,检查在Np集合的节点中是否存在一个非共有邻居集合,即可能的STH的集合Ns。

Ns={ni|ni∈Np且ni∉Nm}

(3)

定义D(Ns,nMTH)表示Ns中与nMTH的距离集合

dmax=max(D(Ns,nMTH))

(4)

要求dmax>2R,其中R为单跳最大通信距离。

如果存在dmax>2R的节点,则将该距离对应的Ns中的节点作为STH,从Token由MTP生成传递给该从Token持有节点。

这样STH和nMTH一定是相距两跳之外的,可以保证STH和nMTH之间不存在一个节点既是STH的邻居,又是nMTH的邻居。

MTP决策从Token可以产生之后,MTP将扇区波束对准目标STH,并持续发送mini-Hone-In消息,mini-Hone-In消息中包含Token节点信息,只在一个扇区进行发送。目标STH收到消息之后,扇区波束停止切换,接收到从 Token之后,回复ACK,同时MTP收到ACK之后,转换到快速扫描状态。

目标STH收到从Token之后,开始完成Hone-In和Hello-Reply过程,完成Hello-Reply之后,则将从Token进行销毁,不再进行传递。其邻节点自动进入到快速扫描状态。

4) Token释放机制

Token释放机制(token releasing,TR)是针对主Token在不同节点之间传递时,经过的节点如果发现自身已经完成过邻居发现,则将主Token释放给未持有过主Token的邻居节点,如果不存在此节点,则将此节点交回父节点。Token释放采用mini-Hone-In机制在目标节点所在扇区持续发送消息。

依照上述传递和释放规则,主Token可以在网络内所有节点遍历一次,当主Token再次回到起始源节点,并且源节点不存在未发现邻居的邻节点时,则全网的邻居发现结束。

由上一小节描述可知,从Token仅是临时产生的,持有过从Token的节点会标识自己已经完成了邻居发现过程,当主Token再次到达该节点,不再进行邻居发现,直接执行Token释放的过程。

3.2 协议复杂度分析

D-SAND协议与Q-SAND协议在Hone-In、Hello-Reply阶段传递信息相同,处理方式相同,所以在这两个阶段协议复杂度相当;在Token传递阶段,D-SAND协议相比Q-SAND协议在计算复杂度上主要增加了STH的决策算法。该决策过程主要是计算MTP邻居节点与nMTH节点的距离,并选出与nMTH距离最大的节点。该计算过程通过遍历算法即可以进行运算完成。设邻居表中最大邻居数为n,计算时间复杂度可以表示为O(n)。存储资源与n也呈线性关系,存储空间复杂度也为O(n)。

决策算法在运算时,计算负载实现了节点间的分担，只增加了MTP节点一定的运算量,不会带来MTH节点运算负荷的加重。

从全网发包数量上分析,可以反映出协议在网络上运行的复杂度。如果不能产生从Token时,发包数量和Q-SAND协议相同。在可以产生从Token时,MTP将发送mini-Hone-In消息给STH节点,该发包过程是D-SAND协议特有的,但STH工作过程相比MTH又减少了Token传递阶段，总体来说，从Token发现过程相比主Token发现过程会带来发包略有增加，而且仅在双Token并行工作时，发包数量才会发生增加。

3.3 协议运行示例图

图5说明了双Token的形成和传递过程。具体说明见图中注释。

图5 并发Token的形成和传递示例图

3.4 理论分析

1) 双Token并行工作时间分析

图6 双Token并行工作时间

如图6所示，从Token持有节点STH是与主Token持有节点nMTH并行工作的,如果主Token在从Token工作期间已经被传递,则主Token节点可能与STH存在共有邻居。因此，STH邻居发现完成时间相比nMTH的发现完成时间应提前或同时结束。

令t0,t1,t2,t3,t4,t5。t0表示MTH完成Hello-Reply的时刻,t1表示完成MTH向MTP发送GoToFastScan的时刻,t2表示完成MTH向nMTH发送GoToFastScan的时刻,即nMTH开始Hone-In的时刻,t3表示STH开始Hone-In的时刻,t4表示STH完成邻居发现的时刻,t5表示nMTH完成邻居发现的时刻。由上述分析可知,t5≥t4。不失一般性,将t0设为0。

不失一般性,设定

tGoToFastScan=tHone-In=1/2tTokenAck=τ

(11)

为了避免产生额外的干扰,需要有

t5-t4≥0

(12)

将(10)至(11)式代入(12)式可得

h≤2K

(13)

再根据(2)式，h=2K时,双Token可实现并行工作不产生额外的干扰。

2) 邻居发现总时间计算

Q-SAND协议的时间为

TQSAND=n(THI+THR+TTP)+(n-2)TTR

(14)

Q-SAND协议的总传递次数为2(n-1),其中n代表全网n个节点。其中每一个节点均要完成一次发现的全过程,即进行n次的Token传递,总传递次数为Token传递和Token释放次数的总和,那么Token 释放的次数为2(n-1)-n=n-2。

其中Hone-In阶段的时长为

THI=hKtHone-In

(15)

Hello-Reply阶段的时长为

THR=KNroundsNslotstslots

(16)

Token传递阶段的时长为

TTP=(K-1)tGoToFastScan+tTokenAck

(17)

Token释放机制的时长为

TTR=(h-1)tHone-In+tTokenAck

(18)

D-SAND协议的时间为

TDSAND=

(n-n′)(THI+THR+TTP)+(n+n′-2)TTR

(19)

式中,n′为并发Token的次数,即有n′个节点的邻居发现是并行进行的,在统计节点进行邻居发现的时间时不需要计算在总时间内。

相比Q-SAND(14)式,D-SAND协议的主Token总传递次数仍为2(n-1),总传递次数为主Token传递和主Token释放次数的总和。n-n′个节点要进行邻居发现全过程,那么主Token释放的次数为2(n-1)-(n-n′)=n+n′-2,相比Q-SAND的Token释放次数增加了n′次。

由于THI+THR+TTP远大于TTR,可知n′越大,D-SAND的总时间将越小。

4 仿真

搭建MATLAB仿真平台,对提出的双Token的D-SAND协议和单Token的Q-SAND协议进行了仿真比较。协议的仿真参数见表1。

表1 D-SAND和Q-SAND协议在仿真中的参数

仿真场景参数设置见表2,节点在一定区域内随机分布,在仿真时要求随机分布的各个节点间需要形成可连通的网络拓扑,如果出现随机的孤立节点,则此次形成的网络拓扑不计入统计结果。每个节点都有一个独立的ID,以ID为1的节点作为起始的MTH。

表2 网络场景仿真参数

首先仿真了不同节点数下的从Token的并发次数和并发概率,如图7所示。节点个数一定的情况下,并发次数和网络拓扑是有关联的,为了说明趋势,按照表2的参数取20次平均。如图所示,网络中节点数增加后,并发概率在随之增大。

图7 不同节点个数下的STH并发次数及并发概率

图8 不同节点数量下的D-SAND和Q-SAND发现时间图9 不同节点数量下的D-SAND和Q-SAND全网发包对比图10 波束个数对D-SAND和Q-SAND发现时间的影响

图8仿真了全网的邻居发现时间,对D-SAND协议和Q-SAND协议进行了对比,Q-SAND理论时间和仿真时间是保持一致的,验证了基础仿真的正确性。

Q-SAND协议相比经典的SAND协议,改进目标是缩短全网邻居发现的时间。由图8可以看到本文提出的D-SAND协议相比Q-SAND协议更优,且随着节点数量的上升,D-SAND相比Q-SAND优势越发明显,原因是节点数量增长,双Token并发的概率也在随之增加。从整体上来看,D-SAND发现时间相比Q-SAND提升约10%。

图9对D-SAND和Q-SAND 2种协议在不同网络节点数下的发包数量进行了仿真分析,由仿真可见,D-SAND协议增加发包数量有限,以仿真中发包数量最多的112节点为例,D-SAND协议增加的发包数量比例为1.2%。

最后对波束个数变化和节点发现时间的关系进行了仿真,如图10所示,固定节点个数为64,D-SAND和Q-SAND的发现时间随波束数量增加线性增长。