VGC:虚拟组协同邻居发现算法

孙伟杰，袁平，殷锋

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

0 引言

在无线传感器网络中，邻居发现扮演了重要角色，它是路由和网络组建的先决条件，为了加快邻居发现，许多邻居发现算法相继被提出，现存的邻居发现算法主要分为两类，基于点的成对发现算法和基于组的邻居发现算法，其中成对发现算法又分为概率性邻居发现算法和确定性邻居发现算法。

概率性邻居发现算法节点以一定概率在各时隙随机苏醒如Birthday[1]等，通常具有较低的平均发现延迟，但无法保证一个确定的发现延迟上限。确定性邻居发现算法节点按照预先设定的时刻表进行苏醒，如Disco[2]，Search⁃Light[3]，U-connect[4]等能够保正一个确定的发现延迟上限，但平均发现延迟略高于概率性邻居发现算法。

近几年，一些基于组的邻居发现被提出，该类算法将一些相邻的节点看成一个组，利用组内节点的邻居信息加快其他节点的发现，WiFlock[5]提到了所有的一跳相邻节点（即一个组内）的苏醒时隙相错以使分布平均化，使组外节点更快发现组内节点，而Group-based-Discovery[6]提出了在不改变底层发现协议的基础上，通过组间节点的邻居推荐加快新了节点的邻居发现。

本文中我们在基于组的邻居发现基础之上提出了一种新的邻居发现算法VGC，通过对组内的各个节点进行协同形成一个大的虚拟节点，该虚拟节点工作时隙满足底层成对发现算法的分布特征，同时这该虚拟节点的占空比远大于组内节点的任何节点，因而它能更快地发现邻居，提高了整个组的能量使用效率。

1 算法设计

在我们的工作中，我们设定了工作场景如下：许多没有相互发现的节点一致地分布在一定区域内。传感器网络的辐射范围是以半径为r的圆，并且所有的节点都在一跳的通信范围内。首先根据成对发现算法把已经相互发现的节点看作一个组，如果一个节点属于一个组它将不能再属于其他组。在这个场景中一个单独的节点和一个组以及一个组和另一个组都能相互发现。最终所有节点都完成了发现过程。

为了充分利用所有组内节点的活动时隙进行组发现，我们把所有在时空上分布在网络的组内节点作为一个虚拟节点，换句话说，这个虚拟节点代表了所有组内节点进行邻居发现。通常虚拟节点的活动时隙是不规则的并且在全局时间内有重叠，另外，虚拟节点依赖于成对发现算法他们的发现邻居，所以这虚拟节点需要对组内节点的时课表进行协同调整以确保虚拟节点的时隙分布特征和成对发现算法的相一致，最终所有的组内的节点的活跃时隙被虚拟节点所协同，所有的组内节点根据该协同的时刻表工作。这样我们充分利用了占空比大于所有组内节点的虚拟节点使用成对发现算法来进行虚拟节点和他的邻居之间的快速发现。

由于每个节点携带的能量是有限的，我们把协同计算分配给每一个新发现的节点以确保每一个节点的生命周期，当一个节点新加入一个组时，将会调整整个组内节点的时序，组内大部分其他节点此时一般是休眠状态，对他们的协同要求需要挂起等待直至被要求协同的节点苏醒，才会将协同要求传送给他们，而并不会马上传达到。本文从协同要求延时出发，采用如下方法：

（1）当新发现一个邻居节点时，更新组内的节点数目及组的总占空比，并依照节点占空比计算一个周期内每个节点应该苏醒的时隙数目；

（2）依照节点的下一次的原有苏醒时隙，按照从早到晚排序，以确定新的时序中各组内节点的苏醒次序，越早苏醒的节点在新的时序中排位越靠前；

（3）将产生的协同信息通知组内其余各个节点；

（4）组内节点收到协同信息后调整自己的工作时刻表。

最终所有节点完成了协同过程，形成一个虚拟节点，该虚拟节点没有任何的重叠时隙，并且其时序分布特征和底层成对发现算法相一致。

2 算法分析

虚拟的节点的时隙分布特征和底层成对发现算法相关，在这里我们使用SearchLight进行分析，为了证明虚拟节点的优势，我们使用DCg代表所有组内节点的占空比总和，在SearchLight我们知道在t时间内每个节点有两个活跃时隙，因此：

其中n是组内节点的数量，DCi代表节点i的占空比，ti代表节点i的周期，对于虚拟节点，我们假定只要任一时刻至少有一个组内节点处于苏醒状态，我们就认为该虚拟节点该时刻处于苏醒状态，我们使用DCfg代表其占空比，因而：

其中 Ln表示 t1，t2，…，tn的最小公倍数，即 Ln=lcm（t1，t2，t3，…），Nc表示所有组内节点在 Ln内时间内的重叠时隙个数。

直观地，DCg将随着新加入到组的节点而动态的增加，DCfg也相应的随之增加，然而DCg和DCfg之间难免有一些理论上的偏差，这是因为组内节点之间存在重叠时隙，即Nc的存在，导致虚拟节点减少了发现未知邻居的概率。

图1

如图1所示，三个节点A，B，C他们占空比分别为DCa=2/16,DCb=DCc=2/32，在初始阶段这些节点通过Searchlight进行相互发现，根据等式（1）和等式（2）我们知道DCg=8/32和DCfg=5/32，DCg和DCfg之间的理论偏差是3/32，并且该组的时隙分布并不满足Search Light的时隙分布特征，不能直接将其作为一个虚拟节点进行邻居发现。

在对组内节点的工作周期进行协同后，其时隙分布特征满足Search Light的时隙分布特征，并且Nc=0，DCfg能够达到最大值DCg，像图2所示的那样我们能够看到DCfg从5/32增加到了8/32，并且没有增加任何的活跃时隙，通过和没有进行组内节点协同的相比较，虚拟节点发现其邻居的概率增加了60%。从等式1我们能 够 看 出DCg＞＞DCi，所 以 易 知DCfg＞＞DCi。 结 合Search Light，我们能够充分利用虚拟节点的占空更大的优势减少平均发现延迟和提高组的能量使用效率。

图2

3 算法比较

为了更好地评估VGC的性能，我们在仿真实验中实现了它和Search Light,Group-based Discovery和Wi⁃Flock（底层都基于Search Light）。我们每个仿真做了10000次测试，然后去他们的平均值进行分析：

图3

这第一个仿真是在静态场景中，仿真参数如下：（1）整个网络区域范围是 100×100m；（2）每个节点的辐射范围是 140m；（3）节点数量是 20；（4）一个时隙的长度是10ms；（5）平均占空比是1/20。图3表现了Search⁃Light,Group-based Discovery,WiFlock和VGC的表现。很容易看到：对所有的发现策略，发现百分比都随这时隙数量的增加而增加。当时隙数固定的时候，VGC能够比其他的算法发现更多的邻居。尤其是在500个时隙的时候，VGC发现了98%的邻居。我们注意到：在刚开始的时候，VGC和Group-based Discovery的发现率几乎相同，一段时间后，VGC的发现率比Group-base Dis⁃covery增长地更快。这是因为随着时间的增长，虚拟节点的大小（属于当前虚拟节点的节点数量）增长地更大，所以VGC能够比其他算法更快地发现邻居。

图4

图5

在第二个仿真中，我们使用随机路径模型[6]作为移动多跳网络中的移动模型。仿真参数如下：（1）整个网络区域为500×500m；（2）每个节点的辐射半径是40m；（3）节点数量是 400；（4）一个时隙的长度是 10ms；（5）平均占空比是1/20。图4描绘了平均发现时延和节点移动速度的关系，速度从1m/s到40m/s，增量为5m/s，从图4中我们能够看出VGC的曲线在每种速度下都明显好于其他算法。图5表明了占空比变化对三种算法的平均发现延时的影响。很容易看出，当消耗相同能量时，VGC比其他两种算法更快的完成发现过程。原因和第一个仿真相同。结合图4和图5我们能够得出结论VGC能够显著地提高平均发现延迟和能量使用效率。

4 结语

本文我们为低占空比的无线传感器网络提出了一个新的邻居发现算法，叫做虚拟组协同邻居发现算法。VGC的主要思想是一个组基于预测性的协同策略整合他的所有组内节点的工作时刻表，以至于把所有组内节点作为一个虚拟节点考虑来发现他的邻居。我们在静态和动态场景中都做了仿真。通过和WiFlock以及Group-based Discovery相比较，VGC能够更进一步地减少平均发现实验和提高能量效率。

参考文献：

[1]M.J.McGlynn and S.A.Borbash.Birthday Protocols for Low Energy Deployment and Flexible Neighbor Discovery in Ad Hoc Wireless Networks[J].MobiHoc'01:Proceedings of the 2nd ACM International Symposium on Mobile Ad hoc Networking&Computing,pages 137-145,2001.

[2]P.Duttaand D.Culler.Practical Asynchronous Neighbor Discovery and Rendezvous for Mobile Sensing Applications[J].Proceedings of the 6th International Conference on Embedded Networked Sensor Systems（SenSys'08）,71-84,2008.

[3]Bakht,M.,Kravets,R.:‘SearchLight:Asynchronous Neighbor Discovery Using Systematic Probing.ACM SIGMOBILE Mobile Computing and Communications Review,2010：31-33.

[4]Kandhalu,A.,Lakshmanan,K.,Rajkumar,R.R.:‘U-Connect:a Lowlatency Energy-Efficient Asynchronous Neighbor Discovery Protocol[J].Proceedings of the9th International Conferenceon Information Processing in Sensor Networks（IPSN'10）,2010：350-361.

[5]Purohit,A.,Priyantha,B.,Liu,J.:‘Wiflock:Collaborative Group Discovery and Maintenance in Mobile Sensor Networks.Information Processing in Sensor Networks（IPSN）,2011 10th International Conference on,2011：37-48.

[6]Chen,L.,Gu,Y.,Guo,S.,He,T.,Shu,Y.,Zhang,F.,and Chen,J.:‘Groupbased Discovery in Low-Duty-Cycle Mobile Sensor Networks’,Sensor,Mesh and Ad Hoc Communications and Networks（SECON）,2012 9th Annual IEEE Communications Society Conference on.IEEE,2012：542-550