一种基于时隙优化的邻居发现算法研究

庞利平，殷峰

（1.四川大学计算机学院，成都 610065；2.西南民族大学校园网络管理中心，成都 610064）

一种基于时隙优化的邻居发现算法研究

庞利平1，殷峰2

（1.四川大学计算机学院，成都 610065；2.西南民族大学校园网络管理中心，成都 610064）

作为无线传感器网络组网及路由的先决条件，邻居发现问题受到越来越人们的关注。为了提高无线传感器网络中节点的发现概率，减少发现延时，提出一种基于时隙优化的邻居发现算法（SOND）。SOND算法基于Searchlight[1]原理，对Searchlight中时隙进行优化，从而提高邻居节点之间的发现效率和减少邻居的发现延迟。仿真实验表明SOND算法具有良好的发现性能。

无线传感器网络（WSNs）；邻居发现算法；时隙优化

0 引言

为了解决低占空比无线传感器网络中的邻居发现问题，相关领域的研究人员对邻居发现算法做了大量的研究。目前邻居发现算法可分为两大类：确定性邻居发现算法和概率性生日协议[2]邻居发现算法。确定性邻居发现算法又可分为基于中国剩余定理的算法，最著名的是Disco[3]算法。确定性邻居发现算法可以提供最差情况下的发现时延，保证传感器节点在该时延内一定可以发现其邻居。相比于确定性邻居发现算法，概率性邻居发现算法具有较好的平均发现时延，但是其拖尾较长。本文主要在确定性邻居算法典型算法Searchlight基础之上做出研究。

Searchlight算法核心思想：时间被分成多个连续的等长时隙（长度大小为τ），t个时隙构成一个周期。每个周期有两个苏醒时隙，其余时隙都为休眠时隙。两个苏醒时隙分别是A（Anchor）时隙和探测P（Probe）时隙。A时隙固定在每个周期的第0个时隙。每个周期P时隙的位置由以下公式决定（其中Pi表示第i个周期所处在本周期的第几个时隙，每个周期所有时隙从0到t-1编号，Pi=1）：

下图是Searchlight时序分配图。

图1 Searchlight时隙分布（t=8）

Searchlight发现原理：把t/2个周期看作一个t/2*t的矩阵（如图1所示），各行的P时隙投影到最后一行后，最后一行从1到t/2的所有时隙都是P时隙投影，从而保证一个节点的A时隙与另外一个节点A时隙的重叠，或者一个节点的A时隙与另外一个节点P时隙的重叠，实现邻居发现。但如何保证P的个数与矩阵行数之间的关系来达到能量最优以及P时隙苏醒时隙的大小是Searchlight尚未研究的。针对这些问题，本文在Searchlight的基础上对苏醒时隙进行了优化改进,以及探讨了周期数与占空比之间的最优关系。

1 SOND算法

本文提出了SOND算法，相比于Searchlight，SOND算法对A时隙进行了改变，A时隙向后溢出δ长度，其中δ是节点发送信息的最小时间单位，在一个δ时间长度内，节点只能发送一个Beacon信息，δ大小跟传感器节点硬件环境相关。同时对探测时隙P时隙进行了优化，并将其改为C（Compound）时隙（如图2中所示），它由IP（Inoperative Part）和BP（Beacon Part）两部分构成。IP部分时节点处于idle状态（在idle状态，RF模块不能发送和接收数据，但电路没有完全关闭，此时的节点可以快速地转换到active状态）。BP时隙的长度只足够发一个数据包（Beaconing Packet），其大小用δ表示。由于BP的长度δ只能保证单向发现，但单向发现后，双向发现容易获得。为了确保在最坏发现延迟内至少有一次重叠时间大于等于δ的重叠,C时隙向后“溢出”δ。SOND时隙分布图（t=8）如图2所示。

图2 SOND时隙分布图（t=8）

相比于Searchlight算法，SOND的第二个改进是允许在一个周期内增加多个C时隙。我们用n（图2中n= t/2）个周期构建一个大小为t*n时隙的矩阵，由于这个矩阵所定义的苏醒模式每隔t*n时隙就会重复，所以t*n时隙被叫作超级周期（T）。为确保每行的C时隙投影到最后一行后，最后一行从1到t/2的所有时隙都是C时隙即可保证在n个周期内一个节点的A时隙与另外一个节点A时隙的重叠，或者一个节点的A时隙与另外一个节点C时隙的重叠来实现邻居发现。因此可以增加一行中C时隙个数，从而减小矩阵行数n。但在一行内增加了C时隙就增加了节点的占空比，这样会导致能耗的增加。那么n取值多少时能量是最优的呢？已知节点在IP状态时消耗的能量远小于节点在BP状态下的能量消耗，为了便于计算，假定一个时隙的长度τ=1，IP状态下的能量消耗是BP状态下能量消耗的β倍，β值大小和硬件环境相关。根据图2中的统计数据，若超级周期中苏醒时隙工作的总时长用tw表示，可以得到如下公式。

对上述公式进行变换求导计算，根据现有邻居发现算法的硬件环境，取得α=0.1，β=0.1，可求得到n的最优值与节点占空比之间的关系。

SOND算法发现原理：设x，y为传感器网络中的两个邻居节点，P（x，y）是x的A时隙到的A时隙的相对位移。当P（x，y）小于τ时，必定有x节点的A时隙与y节点的A时隙在第一个周期内重叠。当P（x，y）大于等于τ并且小于t/2*τ时，必定有x的C时隙和y的A时隙在n个周期（即一个超级周期）内的某一个时隙重叠。当P（x，y）大于等于t/2*τ，必有y的A时隙与的C时隙在t/2周期内的某一个时隙重叠。

2 算法比较

本文将SOND算法与Searchlight、Birthday、Disco算法在不同比较条件下进行了仿真实验比较。

图3是在静态场景下的几种算法的发现延迟分析比较，我们可以很直观得出本文提出的算法SOND比其他3种算法更好地减少了邻居节点间的发现时延，能较快地实现节点之间的邻居发现。

图3 发现延迟累积分布图（CDF）

图4是在动态场景下占空比DC（Duty Cycle）从1%变化到5%时几种算法的ADLs（Average Discovery Latency）平均发现延时的比较，我们可以看出几种算法的平均发现延时都随占空比的增大而降低，但在同一DC下，我们发现SOND算法的平均发现延时比其他3种算法的ADLs低。

图4 占空比对几种算法的ADLs影响

3 结语

随着硬件技术的提高，基于无线传感器网络的应用已经广泛影响到包括工业、医疗、农业、军事及户外探索在内的多个领域。而近些年社交网络、社区游戏的兴起，更是吸引了许多业内人士对该领域的探索。无线传感器网络中的邻居发现算法是无线传感器网络的重要研究方向和热点，本文在经典的邻居发现算法Searchlight之上，基于Searchlight算法中存在的不足，提出了一种基于时隙优化来提高无线传感器网络中的邻居发现效率和减少邻居节点间的发现延时，并通过仿真实验表明，本文在Searchlight基础之上提高了邻居节点间的发现效率并且减少了节点之间的发现延时。同时，相比其他几种林发发现算法具有更好的性能。

[1]M.Bakht，R.Kravets.SearchLight:Asynchronous Neighbor Discovery Using Systematic Probing.ACM SIGMOBILE Mobile Computing and Communications Review，vol.14，no.4，pp.31-33，2011.

[2]M.J.McGlynn，S.A.Borbash.Birthday Protocols for Low Energy Deployment and Flexible Neighbor Discovery in Ad Hoc Wireless Networks.in Proceedings of MobiHoc'01.ACM，pp.137-145.2001.

[3]P.Dutta，and D.Culler.Practical Asynchronous Neighbor Discovery and Rendezvous for Mobile Sensing Applications.In Proceedings of the 6th ACM Conference on Embedded Network Sensor Systems，pp.71-84.Nov.2008.

A Neighbor Discovery Algorithm Based on Time Slot Optimization

PANG Li-ping1，YIN Feng2
（1.College of Computer Science，Sichuan University，Chengdu 610065；2.Campus Network Management Center，Southwest University of Nationalities，Chengdu 610064）

As a prerequisite for networking and routing in wireless sensor networks,neighbor discovery is concerned by more and more people.In order to improve the discovery probability of nodes in wireless sensor networks and reduce the delay of discovery,proposes a neighbor discovery algorithm based on time slot optimization(SOND).SOND algorithm based on the principle of Searchlight,the Searchlight in the slot is optimized,so as to improve the efficiency of the discovery between neighbor nodes and reduce the delay of the neighbor discovery. Simulation results show that the SOND algorithm has good performance.

Wireless Sensor Networks(WSNs);Neighbor Discovery Algorithm;Slot Optimization

1007-1423（2017）05-0011-03

10.3969/j.issn.1007-1423.2017.05.003

庞利平（1992-），女，四川广安人，硕士研究生，研究方向无线传感与网络技术

2016-12-06

2017-02-10

殷锋（1972-），男，贵州榕江人，副主任，教授，研究方向为数据挖掘、中间件、分布式计算、软件测试