非对称异步移动传感网中低延时邻居发现算法

黄庭培，张 亚，李世宝，刘建航

(1.中国石油大学(华东)计算机科学与技术学院，山东 青岛 266580; 2.中国石油大学(华东)海洋与空间信息学院，山东 青岛 266580)

0 引 言

移动传感网络(Mobile Sensor Network, MSN)[1]功能灵活，易于部署，广泛应用于物联网、车载网络、移动社交网络[2-5]等许多领域。在MSN中，传感器节点之间的地理位置和分布常常是不确定的，节点之间需要经过互相发现才能自组织形成网络[6]。因此，邻居发现是移动传感网络中必不可少的一部分。

在实际应用中，网络往往是异步[7]的，不同需求的节点往往也具有不同的调度方式。例如，电源供应充足的节点会设置较大的占空比[8]来迅速地发现邻居，这是对称邻居发现协议[9]无法处理的。非对称邻居发现协议不要求每个节点有相同的调度方式，每个节点的占空比可以根据需求调用。占空比即一周期内节点处于活动状态的时间与节点的总时间之间的比例。

针对此问题，算法Nihao[10]采用多说少听的原则，信标可以在活动、睡眠时隙广播。然而，该算法中节点严格遵循预定义的调度表来实现邻居发现，造成了较大的发现时延。Q-Connect[11]算法提出信标在工作周期的不同时隙内进行广播以保证邻居发现的确定性。基于上述思想，本文提出一种名为BMCS的低延时的主动式邻居发现算法。

本文的主要工作包括以下3个方面：

1)提出BMCS-A算法，该算法适用于异步对称场景，其中节点信标与活动时隙分离，信标在工作周期的不同时隙内进行广播以保证邻居发现的确定性。

2)进一步扩展BMCS-A算法，提出持续性广播[12]的BMCS-B算法。该算法适用于节点具有不同参数的异步不对称场景[13]，并且基于邻居关系的传递性[14]，利用已发现的邻居发现潜在邻居，加快邻居发现的过程。

3)通过仿真实验评估所提出的BMCS算法，仿真结果表明，在平均能耗相同的条件下，BMCS算法的最坏发现时延低于现有的其他邻居发现算法。

1 相关工作

根据网络中节点的苏醒方式，将已经存在的邻居发现算法划分为主动式邻居发现算法[15]和被动式邻居发现算法[16]。

1.1 被动式邻居发现算法

被动式邻居发现算法是指每个节点按照预先设定好的睡眠苏醒调度表有规律地苏醒，从而进行相互发现。在基于Quorum[17]系统的邻居发现算法中时间被划分成m2个连续的时隙，并被组织成一个二维m×m的矩阵。每个节点随机选择任意一行和一列作为自己的活动时隙，并在其他时隙内处于休眠状态。从而，在m2个连续的时隙内，任意2个节点间的活动时隙至少能够重叠2次。为了得到相同发现时延要求下比算法Quorum更低的占空比，Dutta等人[18]基于中国剩余定理设计了一种分布式的非对称邻居发现算法，即Disco算法。每个节点单独选择2个素数p1和p2，使得2个素数的倒数之和为节点的占空比。Disco算法的最大邻居发现延时即为2个素数的乘积。Disco算法的缺点是需要针对不同网络场景选择不同的素数对，如果节点选择了相同的素数对，则会导致大的发现延时。

上述几种发现算法，节点均采用被动式邻居发现的方式，通过一定的策略来降低2个节点同时苏醒的等待时间。这种方式的优点是任意2个节点间不需要信息交互，但也存在任意2个节点间可能需要等待很长的时间才能完成相互发现的缺点。

1.2 主动式邻居发现算法

Chen等人[11]提出了一种节点主动苏醒的邻居发现算法Q-Connect。该算法中信标在工作周期的不同时隙内进行广播以保证邻居发现的确定性。Q-Connect算法，降低了平均发现时延，但Q-Connect算法只适用于对称的场景。

Qiu等人[10]基于“多说少听”的原则提出了一种主动式的邻居发现算法Nihao。Nihao通过增加信标广播的数量来降低发现时延。节点在一个周期(m×n)的前m个时隙处于监听状态，每隔m个时隙进入广播状态，整个周期内发送n个信标消息。在该算法中，节点在睡眠状态主动苏醒进行发送信标，因此，2个节点可以在较少的时间内完成双向发现，减少了发现时延。Nihao发送了多个信标消息，造成了较高的能耗，并且没有考虑节点时钟偏移等问题。

综上所述，主动式邻居发现算法可以在平均时延和能耗方面取得一个较好的平衡，但是依然存在限定时延下发现邻居概率不高等问题。

2 算法设计

本章中，首先介绍信标与活动时隙分离的邻居发现模型，其次介绍提出的BMCS-A邻居发现算法的基本邻居发现过程，之后将BMCS-A算法进行扩展，提出适用于异步非对称场景的BMCS-B算法，并利用信标消息的传递性，加快邻居发现的过程。

2.1 邻居发现模型

在确定型邻居发现算法中，时隙模型[19]将连续的时间片分为相同的间隔，称为时隙。时隙分为唤醒时隙和睡眠时隙。在唤醒时隙，节点进入活动状态，在时隙的开头或结尾广播信标，之后切换成监听状态来接收邻近节点的信标消息。因此，节点在发送或者接收信标时都处于活动状态，这对邻居发现来说是不节能的。基于将信标的监听和广播分配到不同的时隙可能更节能的想法，将唤醒时隙分为广播时隙和监听时隙。在信标与活动时隙分离的邻居发现模型[8]的基础上，定义如下的邻居发现模型：

定义1 广播时隙：节点在时隙的开头或结尾广播信标，并在时隙的其余部分保持睡眠状态。

定义2 监听时隙：在该时隙中，节点保持在监听状态以接收信标。

定义3 睡眠时隙：节点保持睡眠状态的时隙。

如图1所示，时隙0是监听时隙，时隙1～时隙3是广播时隙，时隙4～时隙7是睡眠时隙，黑色箭头代表信标。为了便于描述，将节点m的睡眠苏醒调度定义为：

(1)

其中θ是发送信标的时间与广播时隙持续时间之间的比例，头信标和尾信标分别表示信标在广播时隙的开头或结尾广播的信标。

Kandhalu等人[20]提出，当2个相邻节点同时处于活动时隙时，一对相邻节点可以实现发现成功。基于信标的广播和活动时隙分离的发现模型，将2个相邻节点之间的发现定义为它们可以从彼此接收信标：

(2)

当节点B发现节点A时，t1和t2分别表示2个相邻节点A和B的本地时隙索引；当节点A发现节点B时，t3和t4分别表示2个相邻节点A和B的本地时隙索引。公式(2)表示节点A和节点B能够在监听时隙中接收到彼此的信标消息，可以实现双向发现。

2.2 BMCS-A算法

本文首先考虑异步对称场景，如果节点A的第i个时隙的开头与节点B的第j个时隙的开头对齐，i和j不相等，在这种场景下仍然是异步的。保证2个相邻节点最终能够以足够高的能量效率发现彼此是一个挑战。为了解决这一问题，本文提出高效的BMCS-A邻居发现算法。

第一阶段，节点A在任意一时刻苏醒，按照预先设定的睡眠苏醒调度表有规律地苏醒，广播信标探测周围的邻居节点。第二阶段，节点B接收到节点A的信标消息后，通过调整自身信标的发送时刻，主动苏醒广播信标，实现双向发现。

2.2.1 动态广播信标

为了更清楚地描述BMCS-A算法，定义周期和子周期，如下所示：

定义4 子周期：2个监听时隙的周期，等于2个连续监听时隙之间的时隙数，用字母C表示。

定义5 周期：睡眠苏醒调度的总周期，等于一个周期中的时隙数，用字母T表示。

定义6 距离：当前的广播时隙到下一个监听时隙的间隔，等于这个区间内的时隙数，用字母d表示，被包含在信标消息中。

BMCS-A算法的睡眠苏醒调度[21]如下：

2)每个子周期的开始时隙是一个监听时隙。

如图2所示，在一个周期中有2个子周期，即子周期0和1。其中C=8,r=2,N=2。在子周期0内，广播时隙位于第1个时隙到第2个时隙，在子周期1内，广播时隙位于第3个时隙到第4个时隙内。

(3)

在图2中，时隙0和时隙8是监听时隙，因此Ψ(m,0)=1,Ψ(m,8)=1。时隙1和时隙2为广播时隙，Ψ(m,1)=Ψ(m,2)=θ+。同样时隙11和时隙12为子周期1的广播时隙，Ψ(m,11)=Ψ(m,12)=θ+。

2.2.2 主动广播信标

当邻居节点接收信标后，它可以在某个时隙主动广播信标消息，其索引根据距离d计算。如图3所示，当节点B从节点A接收信标后，获取节点A从当前广播时隙到下一个监听时隙的距离d。节点B得知点节点A将在5个时隙后处于监听状态。因此，节点B将在5个时隙后，即节点B的本地时隙6的末尾主动地广播信标。节点A和B的时隙t状态的函数Ψ(A,t1)和Ψ(B,t2)表述为公式(4)和公式(5)。

(4)

(5)

2.3 BMCS-B算法

在实际应用中，很难实现不同节点的占空比相同，因此有必要进一步考虑节点不对称的情况。在节点不对称的情况下，如果节点的时隙模式设计得不好，可能2个相邻节点的广播时隙和监听时隙总是相互错过，从而导致它们永远无法发现对方。为了解决这一问题，基于“多说少听”的思想，本文提出适用于非对称异步的BMCS-B邻居发现算法。

在Nihao算法中，节点通过增加信标消息的发送次数来减少自身苏醒的次数，从而达到降低时延的目的；本节中基于“多说少听”的原则提出一种持续性广播的主动式邻居发现算法。“持续性”是指节点在第一个子周期内持续性地广播信标，邻居节点在接收到信标后，获得发送节点下一次的苏醒时刻，通过调整自身下一次信标的发送时间，使发送节点可以接收到邻居节点的信标消息，实现双向发现成功。

假设可以预先获取所有节点的占空比，BMCS-B分为2个阶段。第一阶段，如图4所示，节点K的占空比最小，节点K在某一时刻苏醒，在自己的第一个子周期(除了监听时隙)的时隙内连续发送信标，探测周围的邻居节点。在网络通信较好的场景下，在C(9)个时隙内，能够保证节点K通信范围内的节点(如I、J等)都可以接收到它发送的信标消息。信标包含节点K在C个时隙后的第一次苏醒时刻的消息。第二阶段，节点I在时隙8接收到节点K的信标消息之后，主动在时隙13发送信标，节点K会在时隙10接收到节点I的信标，从而实现双向发现。

节点I、J和K的时隙t状态的函数如公式(6)与公式(7)所示。Ψ(I,t2)=Ψ(J,t3)和Ψ(K,t1)表示如下：

(6)

(7)

2.4 协作式BMCS-B算法

基于信标消息的传递性，为节点设计了邻居发现列表[22]。节点K发现第一个邻居节点I时，将节点I加入到自身的邻居发现的列表中，并获得了节点I的睡眠苏醒时刻表。当节点K发现新的邻居节点J时，将节点J加入到自身的邻居发现列表中，并将自身的邻居发现列表分享给节点J。节点J根据节点K的邻居发现列表得知节点I下一次的苏醒时间，因此，节点J在该时刻主动地苏醒广播信标来进行邻居发现。

3 性能仿真分析

3.1 仿真环境

本文使用Matlab[23-24]仿真平台，在该平台上实现BMCS算法与其他经典算法对比的仿真。为了减少实验误差造成的影响，每组实验进行10000次，数据取平均值，比较同一占空比下的最坏发现时延。σ的值设置为0.054,r的值由定理1计算给出。其次，本文还对不同节点具有不同占空比的非对称场景进行了性能比较。

3.2 性能指标

3.2.1 BMCS-A算法的性能指标

1)平均能耗。

(8)

2)最坏发现时延。

3)参数r。

(9)

为了获得最小的最坏发现时延，信标数量r[26]的值，如公式(10)。

(10)

(11)

3.2.2 BMCS-B算法的性能指标

占空比时延乘积[21]。

(12)

对于在同一通信范围内的S个节点来说，平均能耗P平均可以表示为：

文献[27]提出了将占空比与时延的乘积作为评价邻居发现算法性能的指标。如果2个指标都小，则它们的乘积也小，算法性能更好。本文采用同样的方式对BMCS-B算法进行评估，占空比和发现时延乘积为：

(13)

(14)

3.3 实验结果

3.3.1 对称场景

本文将BMCS-A与Disco、Searchlight[28]、U-Connect、Q-ConnectUI在异步对称场景中进行对比。在图6(a)中，DC=5%, BMCS-A算法中节点可以在160个时隙之内发现成功，该算法最坏发现时延明显低于其他算法。在图6(b)中，DC=10%, Q-ConnectUI的最坏发现时延为70个时隙，而BMCS-A算法仅仅为50个时隙。基于上述分析，可以声称所提出的BMCS-A算法在异步对称场景中具有较好的性能。

3.3.2 非对称场景

如图7(a)所示，占空比分别为1%和5%的节点的累积发现时延。BMCS-B可以在1400个时隙之内成功发现彼此，比BMCS-A少了1200个时隙。在图7(b)中，节点占空比分别为1%和10%时，BMCS-B的最坏发现时延为900个时隙，BMCS-A的最坏发现时延为2100个时隙。BMCS-B算法比Searchlight(3900)、G-Nihao(4200)、Disco(3300)最坏发现时延分别降低了76.92%、78.57%和72.73%。因此，可以证明BMCS-B算法在平均能耗相同的情况下，最坏发现时延远低于其他算法。

此外，本文将协作式BMCS-B算法与经典算法进行了对比分析。如图8(a)所示，DC=1%和DC=5%协作式BMCS-B在700个时隙内保证2个节点发现成功。如图8(b)所示，协作式BMCS-B可以在600个时隙内保证发现成功，比Searchlight算法、G-Nihao算法、Disco算法发现时延分别降低了84.62%、85.71%和81.82%。基于以上分析，可以得出协作式BMCS-B算法在较低的占空比下的性能更高。

4 结束语

在本文中，基于信标与活动时隙分离的模型提出的BMCS-A算法在异步对称场景中具有更低的最坏发现时延。此外，针对于异步非对称场景，提出了一种基于主动唤醒的持续性广播的算法BMCS-B，并且利用已发现的邻居信息去发现潜在的邻居，加快了邻居发现的过程。最后，通过仿真实验验证了在平均能耗相同的情况下，发现时延比Searchlight、G-Nihao和Disco等算法更低。