基于发现矩阵的邻居发现算法：Swift

李旭，袁平，殷锋

（四川大学计算机学院，成都 610065）

0 引言

邻居发现一直是低占空比无线传感器网络的一个核心问题，为了解决这个问题很多有名的算法被提了出来，例如 Searchlight、Striped-Searchlight和 Search⁃light-trim。在这些知名算法中，时间总是被分成连续的时隙，时隙的长度固定为t。节点在某些时隙保持苏醒，处在苏醒时隙的节点能给邻居节点发送信息也能接受邻居节点发送的信息，为了节省能量节点其他时隙都保持睡眠。为了简化研究学者们通常假设只要2个节点的活动时隙重合足够发送和接收一个数据帧，2个相邻节点之间就能相互发现。

以上这些算法的主要区别是，其发现矩阵有不同，导致能量效率也不同。在这些发现算法中苏醒时隙被分为 2类（Anchor slots和 Probe slots）。Anchor slot和Probe slot有相同的能耗，但是他们在发现矩阵中的位置不相同。DM的第一列（0th）都是Anchor slots，Probe slots的位置各不相同，因此他们的DM的大小也不相同。

Searchlight和Searchlight-trim的发现矩阵都是的矩阵，但是Striped-Searchlight的发现矩阵是的矩阵。Striped-Searchlight通过让所有的An⁃chor slot和Probe slot向后溢出σ，能够将Probe slots的数量和发现矩阵的行数减少为Searchlight的一半。Searchlight-trim将Anchor slot和Probe slot的长度变为了原来的Striped-Searchlight和Searchlight-trim都有效地提高能效，但是都没有尽可能的让Probe slot的苏醒长度变得更短，也没有尝试在同一行中部署多个Probe slots，来提高邻居发现的能量利用率。

为了实现确定性的双向邻居发现，本文提出了DM。在 DM中我们用 Special slot代替 Probe slot。Special slot由处在idle状态的IP部分和处在苏醒状态的AP共同构成。通过缩短Special slot中苏醒时长，可以节约能量。除此之外DM的大小可以按照应用的需求动态的配置。基于DM我们提出了Swift算法，Swift能够有效地提高能量地利用率。

1 算法实现

在DM中，时间被划分成连续的等长时隙，长度用t表示。T个连续的时隙构成一个周期。n个相邻的周期构成一个超级周期。在DM和超级周期有相同大小，但是DM中的活动时隙分为2中Anchor slots和Special slots。Special slot由处在idle状态的IP部分和处在苏醒状态的AP部分共同构成。节点在idle状态下消耗的能量大概是苏醒状态下的，处在idle状态下的节点能很快的从idle恢复到苏醒状态，因此可以将AP的长度缩减到只够发送和接受一帧数据。这样做能够有效地提高能量的利用率，因为Special slot消耗的能量是Probe slot的，此外我们还能按需来改变DM中Special slot的个数和位置。

图1 发现矩阵

2 发现定理

对于两个相邻节点x和y，x和y的DM大小分别是：nx*tx,ny*ty，只要tx等于ty，在 max{nx*tx,ny*ty}个时隙之内两个相邻的节点一定能相互发现。

图2 φ(x,y)定义

证明：

假设n=max{nx,ny}(nx≥1,ny≥1)，tx=ty=T，φ(x,y)表示节点x的Anchor slot（Ax）和节点y的Anchor slot（AY）之间的相位差。当φ(x,y)≤t时，Ax和AY将会重合，并且重合的长度大于等于σ，因为t+σ-φ(x,y)≥σ。当，y节点的 A时隙必然落在DMx的一列或者相邻的两列之间。因此在n*T个slot内AY和APY一定会重合，重合部分的长度为σ。因为在x节点的发现矩阵中，任意两个APY之间的距离必然等于t-σ.因此有(t-σ)-(t-σ)=2σ，这意味着AY和APX必然重合。当时和上面原因类似，这种情况下有APY和Ax必然重合。因此只要tx=ty，x和 y在max{nx*tx,ny*ty}个slot内一定能相互发现。

图3 图解发现定理

如图3所示，当tx=ty=8时，nx=3和ny=2，无论φ(x,y)的值如何变化，节点x，y在24个slot内一定能相互发现。

3 性能分析

在这个部分主要讨论Swift的性能，Swift的最坏发现延迟是n*Tslots，因为两个相邻的节点在一个超级周期内一定能相互发现。在一个DM中有n个An⁃chor slots，APs和IPs各有个。IPs的长度有2种情况t或者t-σ，当IP跟在Anchor slot或者Special slot之后（图1）。在这里我们只讨论最坏的情况，在这种情况下只有一个长度为t-σ的IPs，其他的IPs长度都为 t。在 DM 中 Anchor slot，APs，IPs的总长度分别是：Swift的占空比是：(t视为基本单位)。

为了计算一个给定的占空比d的最坏发现延迟，用ϕ(n,t)来表示Swift的最坏发现延迟，则有：

当a=2(1+σ)，b=0.1+σ，c=-(0.3σ+0.1)，通过计算可以得到ϕ(n,t)的最小值是：当n和t有可能不是整数，此时应该向下取整。

图4 Swift算法理论性能分析

图4显示当占空比从1%变到5%，不同算法的理论最坏发送延迟，从图中可以看出当占空比为1%时，和Searchlight相比Swift降低了48%的最坏发现延迟。

4 仿真

在这部分我们将通过和现在最好的邻居发现算法Striped-Searchlight和Searchlight-Trim做对比来评估Swift的性能。仿真的场景如下：一个500×500（m）的矩形，被平均分成10000个小块，200个传感器节点被随机的部署在该区域。当节点到达每个小区域的顶点时，能够改变方向（向左，向右，向下，向上）。我们研究静态条件下最坏发现延迟的累积分布函数（CDF）。此外还在动态场景（节点移动）下评估了DC和speed对平均发现延迟（ADL）的影响。在仿真环境下节点的通信半径为50m~100m,t=10ms。

在占空比为2%的静态环境下，和Search-Trim相比Swift能减少48.08%的最坏发现延迟，两者之间的相关关系如图5。图6表明当占空比从1%变化到5%，不同算法的平均发现延迟。3个算法的平均发现延迟随着占空比的增加都在增加。当占空比为2%时，Swift比Search-Trim减少了39.6%的平均发现延迟。图7显示了当节点移动速度从2m/s变化到10m/s时，速度变化对平均发现延迟的影响。对所有的节点来说随着速度的增加，平均发现延迟增加了。这是因为随着速度的增加节点之间保持邻居关系的时间变短了。

所有的对比都显示了在相同条件下Swift的性能比现有的算法好。

图5 最坏发现延迟和占空比之间的关系

5 结语

在这篇文章中，基于DM提出了一个确定性的双向邻居发现算法Swift。理论分析当Swift和Search⁃light占空比相同的时候，Swift相比Searchlight降低了48%的最坏发现延迟。理论分析和实验仿真都证明了Swift的优越性。

图6 占空比和平均发现延迟之间的关系

图7 速度对平均发现延迟的影响

参考文献：

[1]Bakht,Mehedi,M.Trower,R.Kravets.Searchlight:Helping Mobile Devices Find Their Neighbors[J].ACM Sigops Operating Systems Review，2011，45.3：71-76.

[2]Michael J.McGlynn and Steven A.Borbash.Birthday Protocols for Low Energy Deployment and Flexible Neighbor Discovery in Ad Hoc Wireless Networks[R].In MobiHoc 01:Proceedings of the 2nd ACM International Symposium on Mobile Ad Hoc Networking&Computing,New York,NY,USA,ACM，2001：137-145.

[3]Zhou,H.Y.,Luo,D.Y.,Gao,Y.,Zuo,D.C.Modeling of Node Energy Consumption for Wireless Sensor Networks[J].Wireless Sensor Network,2011：3（1）：18-23.

[4]Bakht,M.,Trower,M.,&Kravets,R.H.Searchlight:Won't You be My Neighbor[R].Proceedings of the 18th Annual International Conference on Mobile Computing And Networking，2012：185-196.

[6]Chen,S.,Russell,A.,Jin,R.,Qin,Y.,Wang,B.,&Vasudevan,S.Asynchronous Neighbor Discovery on Duty-cycled Mobile Devices:Integer and Non-Integer Schedules[J].MobiHoc,2015：47-56.

[7]Arvind Kandhalu,Karthik Lakshmanan,Ragunathan Rajkumar.U-connect:a Low-latency Energy-efficient Asynchronous Neighbor Discovery Protocol[R].In IPSN 10:International Conference on Information Processing in Sensor Networks，2010：350-361.

[8]Prabal Dutta and David Culler.Practical Asynchronous Neighbor Discovery and Rendezvous for Mobile Sensing Applications[R].In SenSys 08:Proceedings of the 6th ACM conference on Embedded network sensor systems,New York,NY,USA,ACM，2008：71-84.

[9]ZHANG Lan,DING Xuan,WAN Zhi-guo,GU Ming,LI Xiang-yang.Wiface:a Secure Geosocial Networking System Usingwifi-based Multihop Manet[J].In MCS 10:Proceedings of the 1stACMWorkshop on Mobile Cloud Computing&Services,ACM，2010：1-8.

[10]Wei,L.,Zhou,B.,Ma,X.,Chen,D.,Zhang,J.,Peng,J.,...&Chen,L.Lightning:A High-efficient Neighbor Discovery Protocol for Low Duty Cycle Wsns[J].IEEE Communications Letters,2016，20（5）：966-969.