一种基于速度的移动传感网快速邻居发现算法

陈彦如，魏亮雄，郭 兵

(四川大学计算机学院，四川 成都 610065)

目前，物联网呈现井喷发展趋势.无线传感网作为物联网的一项重要支撑技术也备受关注[1].在无线传感网中，邻居发现是路由和组网的前提，所以它是一个非常重要的步骤[2].由于传感网中传感器节点的能量(或者电量)非常有限，这些节点通常工作在低占空比模式.低占空比是指时间被划分成时隙，只有少量的时隙节点处于苏醒状态，而其余时隙节点处于休眠状态.在低占空比模式下进行高效的邻居发现非常困难，因为节点同时苏醒的机会很小.一般而言，给定能量越小，发现延迟小；给定能量越大，发现延迟大[3].研究者提出了大量的邻居发现算法，旨在给定能量条件下，减小邻居发现延迟.研究者提出了两两成对的邻居发现算法，该类算法只关注两两节点的发现.该类算法分为概率性算法和确定性算法.在概率性算法中，节点的工作状态不是事先确定的而是由某个概率分布确定的.确定性邻居算法的工作计划表是事先确定好的.

最近几年，又有研究者提出了基于组的邻居发现算法.这类算法主要利用邻居关系的传递性来加速邻居发现，工作于基于节点对的发现算法之上，所以也可以看作邻居发现中间件.基于组的邻居发现算法包括 Acc[4]，Group-based[5]、EQS[6]和 Wiflock[7].据我们所知，目前基于组的邻居发现算法都没有充分考虑移动传感网中节点移动速度对苏醒时隙选择延迟和能耗的影响.在本文中，基于Group-based邻居发现算法，我们提出一种高效的基于组的邻居发现算法，在对额外时隙进行选择时，该算法量化分析节点移动速度对能耗和发现延迟的影响，选择在验证时刻仍然具有较大概率是邻居的节点进行验证.

1 相关研究

因为在传感网中，在邻居发现之前进行时钟同步比较困难，所以目前主要的邻居发现算法都是异步的.基于发现延迟是否有界，即能否保证一定时间内两个利用低占空比工作的节点必定能够实现相互发现，现有的异步的两两成对的邻居发现算法分为概率性邻居发现和确定性邻居发现.

概率性邻居发现算法主要包括Birthday[8]，PSBA[9]，Panda[10]等.对于Birthday算法，每个节点按照一定概率选择当前时隙应该处于休眠还是苏醒状态.PSBA利用概率性和确定性发现算法的优势，减小了概率性算法发现延迟的长尾.最近的一个典型概率性邻居发现算法是Panda.在Panda中，每个传感器在起初保持睡眠状态，节点的休眠时间服从指数分布.睡眠之后，传感器苏醒并倾听一段恒定时间.如果在侦听状态中没有接收到数据包，则节点向其他邻近节点广播数据包.

最初的确定性发现算法基于Quorum[11].在这类算法中[11-12]，时间被划分为m2个等长时隙.这些时隙可以看作一个二维数组，节点任意选择该数组的一行和一列作为苏醒时隙.Quorum算法保证在m2个时隙内两个节点能够相互发现.早期的确定性方法还包括基于素数的算法，包括Disco[13]，U-connect[14]等.为了进一步提升能效，后来的研究者提出了Searchlight[3].在Searchlight算法中，每个周期有两个苏醒时隙：A时隙和P时隙.A时隙固定在每个周期的第一个时隙.由于周期长度相同，两个节点A时隙的相对位置是永远固定的，这样P时隙被引入用来探测另外一个节点的A时隙.后来的研究者发现，采用等长时隙，在两个节点苏醒时隙的重叠之间存在冗余，这对于提升能效造成不利影响.因此，采用不等长苏醒时隙的确定性邻居发现算法研究开始兴起.这类算法包括Searchlight-Striped[3]，Non-integer[15]，Lightning[2].

近年来，随着移动无线传感网的兴起，对邻居发现的能效要求越来越严苛.于是，又有研究者提出通过邻居关系的传递性来加速邻居发现过程的中间件邻居发现算法.因为这类算法底层仍然采用基于节点对的算法，所以也称作邻居发现中间件.中间件邻居发现算法在基于节点对邻居发现的基础上重新规划少量时隙的工作状态，即休眠还是苏醒，来加快邻居发现进度.中间件该类邻居发现算法包括Acc，Groupbased和EQS等.在ACC算法中，节点选择增加一些额外苏醒时隙，这些额外时隙在底层的基于节点对的发现算法中处于休眠状态，但其在ACC中间件层变成了苏醒状态.这些额外时隙的选择依据是根据时间差异性和空间相似性.两个节点的时间差异性取决于这两个节点工作表的差异性.两个节点的空间相似性取决于这两个节点的公有邻居数量.ACC通过使用少量的额外苏醒时隙在一定程度上加速了邻居发现进度，但问题是其中时间差异性的获得需要很多邻居的信息，在网络中节点密度较低的情况下，ACC在选择额外的苏醒时隙方面显得低效.Group-based也加入了少量的额外苏醒时隙，通过推荐-验证的方式加速邻居发现，但其在选择额外苏醒时隙方面效率有进一步提升的空间.EQS利用Quorum图论滤除不必要的苏醒时隙，提升了邻居发现能效.

在本文中，我们在Group-based的基础上提出了一种基于组的高效邻居发现算法.特别指出，我们提出的算法与其他算法是相互补充的，而不具有排它性.也就是说不同种类的邻居发现中间件可以同时使用来提高邻居发现的性能.比如EQS和我们提出的算法可以同时使用，分别用于移除低效苏醒时隙和增加高效苏醒时隙.此外，据我们所知，在邻居发现中间件算法中，我们提出的算法充分考虑了节点移动速度对于选择的苏醒时隙能效的影响，由此我们提出了节点移动速度对邻居关系影响的定量化分析方法.

2 算法设计

基于组的邻居发现算法的核心思路是通过在各个节点之间共享已经发现的邻居关系信息来预测未来时间内哪个时隙节点苏醒能够发现更多邻居或者对邻居发现具有最大的信息贡献.上节已经提到，已有的基于组的邻居发现算法都只是依据已有的邻居表和其对应的工作表信息来推测未来的邻居关系但忽略了在移动传感网中移动节点速度对邻居关系的影响.我们在本文中提出的SFND算法核心思路是基于Group-based方法，考虑节点移动速度对额外增加的苏醒时隙能效的影响，尽可能地选择在验证时刻有很大概率仍然是邻居且在验证时刻在苏醒状态的潜在节点进行验证.因为我们提出的算法是对已有Group-based方法的改进，所以在接下来的第一小节我们首先介绍已有的Group-based方法.然后第二小节给出我们提出算法的详细设计思路.

2.1 Group-based方法介绍

图1表示Group-based的工作过程：灰色小圆A，B，C，D分别表示四个传感器节点，它们相互在各自的通信范围之内.假定A和B在先前通过某个基于节点对的发现算法已经相互发现，节点C和D也通过基于节点对的算法实现相互发现.接下来，Groupbased中间件算法按照如下的步骤进行工作：

(1)当B发现了一个新的邻居C时，B和C分别将自己的所有邻居信息推荐给对方，节点B知道了节点D的工作时间表，节点C知道了节点A的工作时间表.我们把推荐者B和C叫做推荐节点，被推荐者A、D叫做被推荐节点.因为B接收了C的推荐，所以B叫做C的接收节点.事实上B和C互为对方的推荐节点和接收节点.

(2)由于被推荐者可能不在接收节点的通信范围之内，因此有必要对被推荐节点进行验证以确认是否是接收节点的邻居.当节点B接收到推荐信息后，它将对所有的被推荐节点进行验证.也就是说B会在D的下一个苏醒时隙主动苏醒，以进行邻居发现，也就是相互确认.如果B收到了D的数据包，则将其加入自己的邻居表.同理C也在A的下一个苏醒时隙主动苏醒进行验证，从而发现了节点A.

图1 Group-based算法发现过程图Fig 1 Group-based algorithm discovery process diagram

接收节点需要对被推荐节点进行验证，然而当被推荐节点与接收节点相距较远时，被推荐节点有很大概率不是接收者的邻居，此时的验证对能效的贡献率很低或者为负.尤其在节点密度比较大的无线传感网络中，被推荐节点个数很多，如果不对验证进行有效选择，将导致低效验证过多而给接收节点乃至整个网络带来较大的能耗负担.因此有必要对被推荐节点进行筛选，选择具有潜在较大收益的节点进行验证.在Group-based算法中，主要依据接收节点和被推荐节点之间已经发现的公有邻居作为选择验证节点的依据.作者们通过推导得出，两个节点的距离Dxy=其中α表示一个常数，Nx和Ny分别表示节点x和节点y已经发现的邻居个数，Nc表示这两个节点的公共邻居数.

虽然Group-based算法取得了良好性能，尤其在静态无线传感网络(静态是指其中的节点位置保持不变)中，其对验证节点的选择效率较高.但在移动无线传感网中，依据接收节点和被推荐节点发现时刻的公共邻居数来预测验证时刻的邻居关系有时显得低效，尤其考虑接收节点和被推荐节点发现时刻与验证时刻相差很大时，很可能在接收节点和被推荐节点发现时刻具有较多公有邻居的被验证节点在验证时刻已经不是接收节点的邻居.本文中，我们充分考虑节点移动速度对验证选择的影响，力图选择在验证时刻有很大可能仍然是邻居的节点进行验证，从而提升验证能效而进一步加快邻居发现进度.

2.2 考虑速度因素的快速邻居发现中间件算法

我们根据接收节点和被推荐节点相互发现时刻，接收节点和被推荐节点的公有邻居个数作为评估此时这两个节点距离的依据，就像Group-based算法一样.此外，我们还要评估接收节点和被推荐节点相互发现时刻和验证时刻，即当被推荐节点的下个苏醒时隙时刻，这两个时刻的间隔时间内，移动节点速度对这两个节点距离的影响.为简化分析，假设所有节点移动速度都相等，值为S.设Δtxy为接收节点x和被推荐节点y的验证时刻减去x和y相互发现时刻.在这段时间内，这两个节点距离增加量为速度s和Δtxy的函数，表示为Δl(s，Δtxy).综合x和y发现时刻的距离估计以及Δtxy时间内的距离增量估计，我们得到验证时刻x和y的距离估计lxy=Dxy+Δl(s，Δtxy).

在实际的移动传感网络场景中，Δl(s，Δtxy)的表达式取决于节点的移动模型.往往获取Δl(s，Δtxy)的准确表示比较困难.不过我们能够通过测试，找到能使验证尽可能高效的Δl(s，Δtxy)的大致估计.例如在下节的仿真评估所使用的模型中，我们将Δl(s，Δtxy)的表达式简化得到，lxy=Dxy+β1sΔt+β2/，其中β1和β2是与节点移动模型相关的常数.

对lxy设置阈值lu，当lxy小于等于 lu时，该验证时隙被选择苏醒，否则认为这是低效或者无效的验证而让其休眠.在选择阈值lu时，可以依据给定的额外能量预算，以及因为每个节点剩余能量的不同而对不同的节点选择不同的阈值.比如，当节点剩余能量较少时，可选择一个较小的阈值.

在移动无线传感网中，Group-based算法考虑了接收节点和被推荐节在相互发现时它们是邻居的概率，但在验证时刻很可能它们已经不再是邻居.SFND算法直接考虑在验证时刻，这两个节点是邻居的概率，并选择有较大概率是邻居(即距离较短的邻居)的验证，有效地过滤了低效验证，从而提升了验证的能效.

3 仿真评估

我们通过仿真评估提出的SFND算法，并和其他算法进行比较.底层的基于节点对的算法采用Searchlight，其余要对比的中间件算法包括 ACC和Group-based.为了公平比较，将所有算法总的能量预算即总占空比设定为2%.我们首先对比节点移动速度对 Searchlight， ACC+Searchlight， Group-based+Searchlight，SFND+Searchlight的平均发现延迟的影响.然后，对比网络中节点密度对这些算法平均发现延迟的影响.实验环境描述如下：网络场地为边长为500米的矩形区域，这个区域被划分为2500个等大小的网格.节点只能部署于网格顶点并沿着网格边移动.当移动到网格顶点，节点的移动方向可向上下左右随机改变.

图2 速度对平均发现延迟的影响Fig 2 The effect of velocity on the average discovery delay

图2显示了节点移动速度对平均发现延迟的影响.我们看到，所有算法包括Searchlight，其平均发现延迟都随着速度的增加而减少.这是因为随着速度增加，节点成为邻居的时间减小，那些发现延迟较大的邻居发现没能成功进行.另外，我们看到，随着速度的变化，我们的算法SFND的发现延迟总小于其他算法.比如在节点速度为4m/s时，相比 Group-based，SFND算法降低发现延迟高达18.9%.

图3 节点密度对平均发现延迟的影响Fig 3 Influence of node density on average discovery delay

图3显示了节点密度对平均发现延迟的影响.我们看到Searchlight算法的平均发现延迟几乎不受节点密度的影响，而其他算法的平均发现延迟随着节点密度增大而减少.这是因为节点密度越大，节点之间能够共享的邻居信息越多，对于中间件算法邻居发现进度加速越明显.而对于基于节点对的Searchlight算法，因为不考虑间接邻居信息，所以其平均发现延迟不受节点密度的影响.另外，我们看到随着节点密度变化，SFND的发现延迟总是小于其他算法.

4 结论

在移动无线传感网中，由于节点之间的邻居关系快速变化，要求低占空比下的邻居发现必须更加高效.不同于已有算法，本文中我们提出了一种基于节点移动速度来选择有效验证的高效邻居发现中间件算法SFND.我们量化分析了节点移动速度和时间对两个节点期望距离的影响，并将其作为高效验证选择的依据.最后我们通过仿真评估验证了SFND的有效性.缺点是节点移动速度和时间对两个节点期望距离评估仍然不够精确，以后我们将针对不同的移动模型分别考虑更加精确的速度-时间-距离评估模型，以进一步提升邻居发现中间件算法的能效.