移动低占空比无线传感网中低能耗的主动邻居发现算法

梁俊斌，周翔，李陶深

（广西大学计算机与电子信息学院广西多媒体通信与网络技术重点实验室，广西 南宁 530004）

1 引言

移动低占空比无线传感网（MLDC-WSN,mobile low-duty-cycle wireless sensor network）是近年出现的一种新型自组织网络。它与传统的无线传感器网络（WSN,wireless sensor network）一样，由大量能量、通信范围、存储容量和计算能力均有限的节点组成，主要部署在人类无法进入的恶劣环境中，从事长期的监测或跟踪任务[1,2]。但是，它与WSN有明显的区别：WSN中节点是静止且保持苏醒的，而MLDC-WSN中的节点会长时间进入睡眠状态以保存能量，仅在少量时刻苏醒并通过移动来执行任务[3]。因此，MLDC-WSN的拓扑变化会更加频繁，导致节点邻居也不时地发生改变。

邻居发现是网络中的一个重要的操作，网络中的节点需要快速地相互发现，才能自组织形成网络。由于邻居发现在移动的网络中需要周期性多次执行，因此，以较小的能耗实现快速的邻居发现，是网络能正常开展工作及延长生命周期的重要保障[4,5]。在MLDC-WSN中，节点采用低占空比工作模式（即节点在每个工作周期中的大部分时间处于睡眠状态，仅在少量时刻苏醒），而节点间的邻居发现又要求节点同时处于苏醒状态，使节点等待被发现的邻居苏醒所需要的时间很长，造成巨大的时延。此外，节点苏醒时的移动会导致网络拓扑结构不断改变，使节点的邻居也会不时发生变化。因此，实现低时延、低能耗的邻居发现非常困难。

目前，已有的典型工作是采用节点主动苏醒的方式来进行邻居发现，但是这种方式要求节点多次主动苏醒，从而耗费较多的能耗。如何减少主动苏醒的次数、降低能耗，同时快速地完成邻居发现，仍然是一个亟待解决的难题。

本文提出了一种新的低能耗的选择性主动苏醒邻居发现（SPND,energy saving selectively proactive neighbor discovery）算法。在SPND算法中，节点能够结合网络中节点的移动模型，根据集合的划分，选择性地在邻居苏醒的时刻同时苏醒，与邻居节点进行确认。例如，节点i在某时刻已经拥有了自身的邻居集合，网络中节点经过一段时间的移动后，某些节点已经不再是节点i的邻居。在下一时刻，节点i只需选择性地主动苏醒发现那些可能成为自身邻居的节点。

2 相关工作

根据唤醒调度模式的确定性，邻居发现算法可以分为概率性邻居发现和确定性邻居发现。在确定性邻居发现算法中，根据节点是否主动苏醒发现邻居，又可以进一步划分为主动式邻居发现和被动式邻居发现。

2.1 概率性邻居发现

概率性邻居发现算法采用随机唤醒的调度方式，通过设置节点在每个时间片所处状态的概率，可以获得较低的平均发现时延，但是最坏情况下发现时延可能会非常大。Mcglynn等[6]提出了一种典型的概率性邻居发现算法 Birthday，它利用生日悖论的概率性原理，即在随机抽取n个人组成的集合中，当n很大时，有人生日在同一天的概率会很大。因此，节点以某种概率来选择当前时隙节点的状态（包括睡眠、发送、侦听），通过细致地设置各个状态的概率值，节点在一段连续时间内会有很高的概率可以相互发现。该算法能够实现邻居发现过程中能量消耗和发现时延之间的良好平衡，但它无法限定最坏情况下的发现时延。针对这个问题，You等[7]提出了 ALOHA-Like 算法，它分析任意节点发现n-1个邻居节点的期望时间，有很高的概率能限定最坏情况下的发现时延。

2.2 确定性邻居发现

确定性邻居发现中，节点采用固定的唤醒调度模式，即节点处于睡眠或苏醒状态按照预定的睡眠苏醒调度表周期性地重复。

2.2.1 被动式邻居发现

被动式邻居发现算法是指节点完全按照预定的苏醒时刻苏醒进行邻居发现。一个典型的被动式邻居发现算法是 Jiang等[8]提出的 TQS（torus quorum system）邻居发现算法。该算法将节点工作周期编排成t×w矩阵，工作周期长度为n=t×w。节点任选其中一列 c的所有元素，再从所选)列任意位置选择个元素，作为节点的苏醒时间片。TQS能实现较优的能耗时延指标，但是不适用于每个节点采用不同的唤醒调度模式的情况。为了解决这个问题，Zheng等[9]实现了一种不需要时隙对准的异步苏醒协议（AWP,asynchronous wakeup protocol）算法，该算法中节点可以根据其在网络中的不同角色灵活设置占空比。AWP将邻居发现问题简化为一个图的最小顶点覆盖问题，而解决图的最小顶点覆盖问题都是集中式的方法，但集中式的方法在节点分散的无线传感网中并不适用。

针对TQS算法及AWP算法的不足，Dutta等[10]提出了 Disco算法。Disco算法中每个节点选择 2个素数作为其工作周期，节点大部分时间处于睡眠状态，每个节点拥有一个独立的计数器，一旦节点计数器能够整除其任何一个素数工作周期，使该节点处于苏醒状态。根据中国剩余定理[11]，2个节点的苏醒时隙必然能够周期性地重叠或部分重叠，Disco算法能够确保一直在邻居范围内的2个节点能够在一定的时限内相互发现。

为了统一解决节点唤醒调度模式异步和同步的问题，Kandhalu等[12]提出了U-Connect邻居发现算法。U-Connect算法选择素数q作为其基本工作周期，然后，在连续T个时隙内构建q×q的网格矩阵（T=q×q），并在矩阵内任选某列和某行的一半时隙作为节点的苏醒时隙，当该行后面的时隙数不足一半时，返回到该行的首列继续选择。U-Connect算法融合了中国剩余定理和 TQS算法的思想。U-Connect算法的能耗—时延指标是最优理论系统的1.5倍左右，在能耗时延均衡方面优于TQS算法和Disco算法。

2.2.2 主动式邻居发现

已有的邻居发现算法有很多，但是它们都基于节点被动式苏醒进行邻居发现。Chen等[13]提出了一种节点主动苏醒的邻居发现算法Q-connect。该算法分析了节点从睡眠状态切换到苏醒状态所需的能耗，考虑到该部分能耗不可忽视，Q-connect 算法将节点时间片细分为几个部分，在第一部分主动苏醒广播 beacon 消息，在第四部分主动苏醒接收beacon 消息。Q-connect 算法能提高网络的能效利用率，但是节点平均发现时延较大。

为了充分利用beacon 消息减少发现时延，Qiu等[4]提出了一种主动式的邻居发现算法 Nihao。Nihao算法基于“多说少听”（TMLL,talk more listen less）的原则，节点在一个周期（m×n）的前 m 个时间片处于“听”（苏醒）状态，并在整个周期中每隔 m个时间片进入“说”（主动苏醒发送一个beacon消息）状态，即一共发送n个beacon消息。在Nihao算法中，beacon消息可以在节点睡眠状态主动苏醒发送，因此，使节点在较少时间片内相互发现，减少发现时延。

Kindt等[14]提出了一种主动式邻居发现算法Griassdi。在Griassdi算法中，节点周期性地苏醒与发送beacon消息，且苏醒与beacon消息的发送相互独立。节点在某个时间片内苏醒收到其他节点的beacon消息后，会根据其他节点的下一次苏醒时间，调整自身下一次发送beacon消息的时刻，以实现快速与其他节点相互发现。

这部分算法都要求节点在一个时间片的部分时刻发送beacon消息，Chen等[15]提出了一种不需要发送beacon消息的节点主动苏醒发现邻居GBD（group-based discovery）算法。在 GBD 算法中，相互发现的节点位于一个组中。组中的节点根据移动低占空比网络的时空特性，选择性地将它们部分现有邻居的睡眠和苏醒时刻分享给新发现的加入组中的邻居节点。新发现的节点就能快速地获得周围节点的苏醒时刻表，在周围节点苏醒的时刻主动苏醒，从而判断2个节点是否是邻居。针对节点密度较大的网络，Chen等[15]又对GBD算法进行改进，提出了AGBD（advanced group-based discovery）算法。在AGBD算法中，节点遵循一个基于移动网络时空特性的选择机制，这种机制能减少节点部分不必要的主动苏醒，但是可能会漏掉邻居节点。GBD算法的优点是平均发现时延较低，节点能在潜在的邻居节点苏醒时主动苏醒进行邻居发现，减小了网络低占空比特性增大的发现时延。但是，GBD算法存在2个方面的不足。

1) 节点选择性地主动苏醒进行邻居发现，无法限定最坏情况的最大发现时延。

2) 节点基于概率的选择性转发会降低节点发现邻居的可靠性。

以上是针对低占空比网络的一些典型邻居发现算法，可以发现，概率性邻居发现算法能取得较低的网络能耗且以较小的时间发现大部分邻居，但是无法限定最坏情况下的全网最大发现时延。确定性邻居发现中，被动式邻居发现算法时延往往较大，主动式邻居发现算法能取得较小的发现时延，但是需要节点主动苏醒或主动发送beacon消息，网络能耗较大。本文将针对这些算法的优缺点进行建模，并提出优化的解决方案。

3 系统模型和问题描述

本节将给出MLDC-WSN的网络模型及本文研究问题的描述，同时对相关术语进行定义。

3.1 相关定义

定义1 通信半径[16]。节点以一定功率通信能保障消息被其他节点接收到的最远距离。

定义2 节点的发现概率[17]。距离在通信范围内的2个节点能相互发现的概率。

定义3 节点的发现比率[17]。网络的任意节点发现的邻居节点数目占所有通信范围内节点数目的比率。

定义4 发现时延[17]。从节点移动到通信范围内的时刻开始到它们相互发现时的时间间隔。

3.2 网络模型

假设一个拥有n个移动节点的无线传感器网络Gnet={V,E}，其中，V表示网络中节点的集合，E表示网络中节点间是否连通的信息。Gnet中节点采用低占空比工作模式，将移动节点的工作状态定义为睡眠（sleep）—苏醒（active）状态，如图 1所示，即节点大部分时间处于 sleep状态，关闭除去定时器以外所有其他功能模块，只在少部分时间，如第3、12个时间片处于active状态，感知数据和通信。节点能在任何时候主动苏醒发送数据分组，但是只能在计划的苏醒时刻接收数据分组。

图1 占空比示意

为了考虑网络分布较为均匀的情况，网络的节点采取 Random Waypoint移动模型。在 Random Waypoint移动模型[18]中，每个移动节点随机选取一个方向作为目标方向，然后选定一个范围在[0,vmax]的恒定速度v移动，其中，vmax为节点能移动的最大速度。节点间方向及速度的选取相对独立。网络中节点在特定的时间段Δt内移动，节点在一个Δt时间段内移动的距离范围为[0,vmax×Δt]。

3.3 问题描述

网络中的节点i与节点j能在某个时刻t实现相互发现需要满足2个条件。

1) 在某个时间段Δt内，节点i与节点j在通信范围内，假设网络中节点的通信半径一致为R。

2) 节点i与节点j在Δt内同时处于苏醒状态，且Δt不小于节点实现邻居发现所需的最小时间。

节点间同时满足以上2个条件，才能被称为节点i与节点j能在[t,t+Δt]实现相互发现。

在MLDC-WSN中，节点的邻居发现时延是指从2个节点可以相互通信的时刻t0开始，到它们完成相互发现的时刻t+Δt为止的时间间隔δ，即

节点的发现概率是指在通信范围内的2个节点i和节点j能相互发现的概率Pij，Pij的取值范围为[0,1]。Pij(t)=0表示节点在t时间内无法相互发现，Pij(t)=1 表示节点在t时间内肯定能相互发现。用比率Pi(t)表示节点i在t时间内发现的邻居节点占所有通信范围内邻居的比率。因此，MLDC-WSN中邻居发现问题可以归纳为以最小的能耗实现发现时延δ的最小化与以最小的时间实现发现比率Pi的最大化问题，即

其中，δ=t+Δt-t0，由于Δt通常是常量无法调节，只有t-t0可以通过算法进行优化。在已有的能实现较低发现时延的算法中，通常无法使P接近1。本文提出一种新的节点主动式邻居发现算法SPND，能实现低能耗的快速邻居发现，以下是其详细的描述。

4 算法设计

本节将给出 SPND算法的基本思想及详细设计，并从理论上将SPND算法和已有的邻居发现算法进行对比。考虑到已有的典型算法采用了节点的主动苏醒来减小邻居发现时延，SPND算法专注于结合网络移动性模型，减少节点主动苏醒次数，从而实现低能耗的主动式邻居发现。

4.1 算法基本思想

在SPND算法中，对于刚部署的传感器网络，每个节点分布式地开展邻居发现工作。针对移动传感器网络的特点，将节点的邻居发现分为2步。步骤1根据基于组的邻居发现算法构建节点初始邻居集合，依据这样一个原则：新加入组中的邻居节点将自身的邻居集合信息分享给组中的其他节点，组中的其他节点就能快速地获取潜在的邻居节点的苏醒时间，从而在该时间主动苏醒进行邻居发现。步骤2结合节点的移动模型，选择性地指定节点的主动苏醒时刻，节点主动苏醒发现该时刻的邻居集合，依据这样一个原则：网络中节点经过一段时间的移动后，节点只选择那些移动后可能在通信范围内的潜在邻居节点进行主动式苏醒的邻居发现；将肯定在邻居范围内的节点按既定的睡眠苏醒状态进行邻居发现；将肯定移动出邻居范围内的节点剔除出邻居集合。

4.2 算法详细设计

SPND算法分为2个阶段。网络刚部署，构建节点初始邻居集合为第一阶段。选择性地指定节点的主动苏醒时刻，节点主动苏醒发现该时刻的邻居集合为第二阶段。网络中的节点分布式地完成第一阶段的邻居发现过程，然后节点间完全异步地从第一阶段切换到第二阶段。

4.2.1 构建初始邻居集合

MLDC-WSN部署后，首先在t时刻，网络中任意一个节点i分布式地生成自己的邻居集合中节点个数为1时，节点i将依次在自己的苏醒时刻发送广播消息来发现邻居，直到在某个时刻发现了第一个邻居节点k，并将节点k加入集合中，此时，节点i的集合= {i,k}中节点个数为2。当Gi≥ 2 时，如图2所示，节点i按以下步骤进行下一步的邻居发现。

图2 构建初始邻居集合

1) 网络中的每个节点在苏醒时刻会广播一个消息，告知网络自己的存在。如图2所示，在某个时刻t0，节点i与节点j在通信范围内，收到了彼此的广播消息，即节点i和节点j相互发现成为邻居节点并能获取彼此的睡眠苏醒时刻表。

2) 节点j将在节点i的下一次苏醒时刻t1主动苏醒，将已经位于Gj中的邻居节点的睡眠苏醒时刻表信息发送给节点i。节点i则会在节点j的下一次苏醒时刻t2将已经位于Gi中的邻居节点（如节点k）的睡眠苏醒时刻表信息发送给节点j。

3) 节点j在收到节点i的邻居信息后，将依次在节点i的邻居节点（如节点k）的下一次苏醒时刻t3主动苏醒，然后发送消息，来确认该节点是否是节点j的邻居。节点i以同样的方式确认节点j的邻居是否是节点i的邻居。

具体算法如算法1所示。

算法1 构建初始邻居集合

1) for (网络中每一个节点i) {

2) while (t＜T) {

3) if (节点i苏醒发现节点h) {

4) 节点i和节点h共享G;

5) } else {节点i睡眠}

6) if (节点h的邻居苏醒) {

7) 节点i主动苏醒;

8) 节点i与节点k确认;

9) } } }

每当节点i的邻居集合Gi加入新的邻居节点，循环执行与新加入节点的邻居进行确认的步骤，即算法 1中的步骤 6)～步骤 8)，直到收到的所有邻居信息都被确认完毕，完成第一阶段的初始邻居集合构建。

4.2.2 选择性指定苏醒时刻

节点构建完初始邻居集合即进入第二阶段的邻居发现工作，即当节点i周围有节点移动后，为节点i选择性地指定其后主动苏醒进行邻居发现的时刻。网络中节点采用Random Waypoint移动模型，即节点每次移动的最大距离为ΔS=vmax×Δt，方向随机。在网络中，假设节点的通信半径一致为R。节点i在某个时刻t的邻居集合为，经过一段时间Δt的移动后，节点i的新邻居集合为。如图3所示，根据网络模型可知，中与节点i的距离在[0,R-ΔS)范围内的节点肯定在中，与节点i的距离在[R+ΔS,+∞)范围内的节点肯定不在中，距离在[R-ΔS,R+ΔS)范围内的节点可能在中。因此，对于节点i而言，在经过Δt时间移动后，下一次进行邻居发现时，可以只需考虑距离在[R-ΔS,R+ΔS)范围内的节点。

图3 节点移动示意

传感器网络中，节点可以通过 RSSI信号强度来大致估计互为邻居的节点间的距离。对于已经获取了邻居集合的节点i而言，如图4(a)所示，可以根据节点间的距离将邻居集合划分为 2个子集合和。其中，集合中节点k具有的性质是节点k与节点i之间的距离lik在[0,R-ΔS)范围内。集合中节点h具有的性质是节点h与节点i之间的距离lih在[R-ΔS,R+ΔS)范围内。

图4 集合划分示意

对于在集合[R,R+ΔS)范围内的节点g，可以通过节点h来获取。如图4(b)所示，令r=R+ΔS-lih，节点h位于集合内，并且拥有自己的邻居集合，则需要将集合中与节点h距离在[0,r]范围内的邻居节点的信息发送给节点i，构建节点i的邻居集合。具体算法如算法2所示。

算法2 集合划分与确认邻居节点

1) for (网络中每一个节点i) {

2) if (节点i的邻居集合Gi非空) {

3) for (集合Gi中任意节点j){

4) if (节点i和节点j的距离＜R-ΔS){

6) }else if (R-ΔS＜节点i和节点j的距离＜R+ΔS) {

8) }}

11) }

13) 节点i主动苏醒与节点l确认;

14)} } }

4.3 理论分析

针对发现时延，将SPND与已有的典型算法进行对比，并分析SPND算法的能耗和发现概率。首先，从理论上定性地证明SPND算法发现时延优于已有的被动式苏醒邻居发现算法，然后定量地比较节点发现所有邻居节点时延的期望值。

4.3.1 发现时延分析

假定一对已经相互发现的邻居节点i和节点j，节点 i的邻居集合中包含节点 k，下文分析节点 j发现节点k的时延。为了简化问题模型，假定节点j与节点k在一个周期开始之前恰好移动到通信范围内。设集合C为节点j和节点k可能的发现时间集合，当节点i与节点j以被动式的苏醒进行邻居发现时，则有 C =τj∩τk，即节点j与节点k的最小发现时延为min C。当采用SPND算法构建节点初始邻居集合时，节点j能通过节点i提前获取节点k的苏醒时刻，主动苏醒进行邻居发现，即会增加节点j的工作模式τj中的苏醒时间片。节点j新的工作模式为τ′j，则有C因为 τj⊆ τ ′j，则有C⊆C′。即选择性主动苏醒邻居发现算法的发现时延小于或等于传统的被动式苏醒邻居发现算法的发现时延。

不失一般性地，本文选取 Disco算法作为定量比较的对象。与其他被动式苏醒算法U-connect和 Searchlight一样，Disco算法中网络中的每个节点在网络部署前规划好自身的睡眠苏醒时刻表，网络部署后，节点按时刻表苏醒进行邻居发现。其特性是能限定节点 j和节点 k发现的最大时延即当节点 j与节点 k在通信范围内的时间时，肯定能相互发现。当时，节点j和节点k能相互发现的概率为p=f(j,k,t)。即节点j与节点k在t时间内相互发现的概率可以表示为

则节点j采用Disco算法在t时间内发现所有n-1邻居节点的概率可以表示为。它的密度函数可以表示为

通过概率密度函数计算节点j发现所有邻居节点的期望时间为

当采用SPND算法构建节点初始邻居集合时，节点i被动苏醒，在时间t内发现通信范围内第一个邻居节点j的概率(t)可以表示为

它的概率密度函数为

通过概率密度函数计算节点i发现所有邻居节点的期望时间为

其中，max(Th)是节点h的连续2个苏醒时间最大间隔。节点 i以(t)的期望时间发现第一个邻居节点后，最多还需要2max(Th)的时间来进行邻居确认和分享自身的邻居集合信息。第5节将通过仿真实验，比较Disco算法的期望发现时延和SPND算法的期望发现时延。

4.3.2 苏醒及主动苏醒次数分析

节点用于邻居发现的苏醒时间片主要包括2个部分：按既定的睡眠苏醒时刻表上苏醒的时间片和主动苏醒的时间片。在SPND算法中，节点j通过邻居节点i获取了节点i的邻居后，通过增加节点j的工作模式τj中的苏醒时间片进行邻居发现，能减小发现时延，增大发现概率。为了减少增加的苏醒时间片带来的能耗，本文设计了选择性地指定节点主动苏醒时刻。

假设网络中节点一致分布，密度为 ρ，即网络在单位面积的范围内拥有ρ个节点，则在节点i周围距离R范围内平均有 Ni=πR2ρ个节点。现有的节点主动式苏醒的算法中，节点i需要主动苏醒发现在集合、和中的所有潜在邻居节点，即平均主动苏醒= π (R+Δ S)2ρ次。在本文设计中，节点i只需主动苏醒发现在集合和中的所有潜在邻居节点，即平均主动苏醒次数为

节点i可以减少约φ次的主动苏醒次数，φ表示为

其中，ΔS是网络中节点一次移动的最大距离，可见在ΔS不为0的情况下，节点i能减少的苏醒次数是很可观的一部分。

4.3.3 能耗分析

无线传感器网络中节点的能耗 En主要包括 3个部分：处理器模块的能耗 Ep、通信模块的能耗Ec和感知模块的能耗Es。处理器模块有3个工作状态，分别是运行态（run）、空闲态（idle）和睡眠态（sleep）。通信模块一般有 6种状态，分别是发送（send）、接收（recv）、关闭（off）、空闲（idle）、睡眠（sleep）和信道检测评估（CCA/ED）。感知模块则只有开（on）、关（off）2种状态。在评估网络邻居发现能耗时，可以认为感知模块独立于其他 2个模块，因此，本文评估 SPND算法能耗 En-SPND时主要考虑处理器模块与通信模块的能耗，即

在节点苏醒及主动苏醒的时间片内，处理器可能处于运行态或空闲态，运行态处理器一个时间片内正常执行指令需要消耗能量Ep-run，空闲态部分功能暂停执行，能耗 Ep-idle相对较小。通信模块则可能处于发送、接收或信道检测评估状态。在节点处于睡眠状态时，处理器模块与通信模块也都处于睡眠态，此时节点的大部分模块关闭，系统能耗Ep-sleep、Ec-sleep最小。

根据文献[12]可知，节点在一个苏醒状态时间片内进行信道检测评估的能耗Ec-CCA/ED和收发数据需要的能耗Ec-send、Ec-recv基本相等。即节点在苏醒及主动苏醒的时间片内，通信模块消耗Ec的能量是一定的，处理器模块根据处于运行态与空闲态的不同，能耗有差异，但都大于节点处于睡眠态的处理器模块能耗Ep-sleep。

因此，本文将SPND算法的能耗En-SPND模型定义为节点处于苏醒及主动苏醒的次数N与节点每个时间片内苏醒的能耗En的乘积，然后加上节点处于睡眠状态的能耗，即

其中，N表示节点苏醒及主动苏醒次数，NS表示节点处于睡眠的时间片个数。Nrun表示N中处理器模块处于运行态的次数，Nidle表示N中节点处理器模块处于空闲态的次数。Ec表示通信模块进行一次收发数据或信道检测评估能耗的均值。Ec-sleep表示通信模块一个时间片内处于睡眠的能耗。

4.3.4 发现概率分析

现有的主动式苏醒算法中，GBD算法能实现时延、能耗较优的邻居发现，本文将与该算法比较节点i发现所有邻居的概率。在GBD算法中，节点i根据节点间的距离lik和lij判断是否在节点k的苏醒时刻主动苏醒，其中，k是节点j的邻居。计算节点k是节点i的邻居的概率式为

通过为Pj,ik(ljk,lij)设置不同的临界值来判断节点i是否主动苏醒发现节点k。该算法仅通过概率来判断是否主动苏醒进行邻居发现，这会导致节点i可能主动苏醒发现不在邻居范围内的节点，也可能错过主动苏醒发现邻居范围内的节点，造成节点i在t时间内发现所有邻居节点的概率Pi(t)较小。

在SPND算法中，节点i的3个子集合、和中,的节点在t+Δt时刻仍然是节点i的邻居，通过被动式苏醒可以发现。和中的节点在t+Δt时刻可能是节点i的邻居，通过主动式苏醒可以发现，即节点i能发现3个子集合、和中所有邻居节点。需要注意的是，在实际网络情况下，由于存在分组丢失率、节点移动可能频繁或速度较快、子集合可能无法获取[R,R+ΔS)范围内的所有节点等问题，造成节点i无法在t+Δt时刻发现所有邻居节点。但是这些假设的存在只会影响SPND算法的性能，不会改变SPND算法发现概率高的可靠性。

5 实验及分析

本文通过仿真实验测试SPND算法性能，并将SPND算法的实验数据与已有的典型算法的数据进行对比。为了减少实验误差造成的影响，每组实验进行1 000次，数据取平均值。

5.1 实验环境

本文使用C++语言搭建了一个仿真平台，然后在该平台上分别实现了SPND算法与Disco、GBD、Birthday这3个对比算法的仿真。在仿真中，假设网络部署在1 000 m×1 000 m的范围内，由完全随机分布的500个移动低占空比节点组成。所有节点均在网络部署区域范围内移动，且节点的移动采用Random Waypoint 移动模型。节点默认的平均移动速度为1 m/s，在1±0.3 m/s范围内随机取值，即节点最大移动速度为1.3 m/s，最小移动速度为0.7 m/s。节点的占空比设置为5%，表示节点每20个时间片将会有一个时间片处于苏醒状态，其他时间片处于睡眠状态。网络中节点的默认通信半径一致为100 m。网络中节点邻居信息的TTL（即邻居信息失效的时间）设置为5 000个时间片，每个时间片为10 ms。这个设定是合乎实际场景的，例如，一个 CC2420无线传感器节点收发1 B的数据大约需要0.032 ms，因此，在网络完全异步的情况下，10 ms的时间片也能在极大限度内保证2个节点能在一个同时苏醒的时间片内完成邻居发现工作。

5.2 性能表现

本文分别测定了网络平均发现时延、节点苏醒次数、节点能耗及限定时延内的节点发现比率这 4个方面的数据，通过这4组仿真实验数据进行SPND算法与其他算法的对比分析。

5.2.1 网络平均发现时延

本节测定了不同网络占空比和节点移动速度情况下网络的平均发现时延。首先测定了网络中每个节点发现所有邻居节点的发现时延，然后取所有节点发现时延的平均值作为整个网络的平均发现时延。设置网络节点移动速度为1 m/s，占空比从1%到10%，得到占空比不同的发现时延如图5(a)所示。设置网络中节点占空比为3%，移动速度从1 m/s到10 m/s，得到移动速度不同的发现时延如图5(b)所示。

图5 网络平均发现时延

由图5(a)可以发现，随着节点占空比的增加，节点拥有更多的苏醒时间片进行邻居发现，能减少节点的邻居发现时延。当节点占空比达到0.05及以上时，SPND算法能实现10 s以内的邻居发现时延。由图5(b) 可以发现，随着节点移动速度的增大，所有算法的发现时延均有一定程度的减小。这是因为节点移动速度增大，造成节点在通信范围内的时间减少，节点能发现的邻居节点数目也就较少，因此节点发现时延减小，整个网络的平均发现时延随之减小。

5.2.2 节点苏醒次数

本节主要测定了不同占空比和移动速度情况下节点发现所有邻居节点需要的苏醒次数。这里的苏醒次数包括有节点按睡眠苏醒时刻表被动苏醒的次数以及节点根据邻居集合信息主动苏醒的次数，得到仿真实验数据如图6所示。由图6可知，SPND算法中节点主动苏醒平均次数占节点总苏醒平均次数不到30%，带来的额外能耗优于已有的主动苏醒邻居发现算法。

图6 节点苏醒次数

由图6(a)可以发现，在节点占空比增大时，节点的总苏醒次数会减小，而节点的主动苏醒次数基本保持稳定。这是因为节点占空比的变化不影响节点在某个时刻需要发现的邻居节点的数目，而较大的占空比使节点拥有更多的被动苏醒时间，因此，总苏醒次数会减小。由图 6(b)可以发现，在节点移动速度增大时，节点主动苏醒次数会先增加后持平，总苏醒次数也随之增加。这是因为增大的移动速度会使节点周围邻居集合变化快，节点需要更多的主动苏醒时间发现新的邻居节点。而当节点速度增大到一定程度，使节点在通信范围内的时间不足以进行邻居发现工作，节点主动苏醒次数就保持稳定。

5.2.3 节点能耗

本节将展示SPND算法的网络能耗，并与现有的主动式邻居发现算法 GBD进行对比。在此处的网络能耗中，仿真实验考虑了与节点邻居发现相关的处理器模块的能耗和通信模块的能耗。各项参数值设置如表1所示。

表1 能耗分析参数值

仿真实验分别测定了占空比不同与节点移动速度不同情况下，网络中任意一个节点完成一次邻居发现的平均能耗，得到的数据如图7所示。

图7 节点平均能耗

由图7(a)可以发现，SPND算法中节点能实现较小的能耗，且随着占空比的增加，节点用于邻居发现的能耗能减少很可观的一部分，而GBD算法中节点能耗则趋于稳定。由图 7(b)可以发现，网络中节点能耗会因为节点的移动速度增大而增大，但是SPND算法总能取得比GBD算法更小的网络能耗。

5.2.4 限定时延内的节点发现比率

本节将展示在限定时延情况下的节点发现比率，并将SPND算法与经典的Disco算法与Birthday算法进行对比。当网络中节点占空比为 0.05，节点移动速度为3 m/s时，得到节点限定时延的发现比率如图8所示。

图8 限定时延的发现比率

由图 8可以发现，当限定时延较小时，SPND算法与 Birthday算法一样，发现比率上升较快，Disco算法上升较慢。而到一定比率后，Birthday算法出现了上升较慢的问题，而 SPND算法能与Disco算法一样保持较快的上升速度。最终，SPND算法能实现在1 300个时间片左右实现发现比率收敛到1，比Disco算法快大约200个时间片。

5.3 实验总结

本文通过将SPND算法与其他算法的性能进行比较，分别从网络平均发现时延、节点苏醒次数、节点能耗及限定时延内的节点发现比率这4个方面进行对比。仿真实验数据表明，SPND算法的邻居发现时延比GBD算法减小了约19%，同时网络能耗减少了约30%。此外，在限定时延的发现比率方面，SPND发现比率收敛到1的速度比Disco算法快13%。算法性能对比如表2所示。

表2 算法性能对比

其中，Disco、Birthday算法均属于被动式苏醒算法，节点不会主动苏醒。

6 结束语

本文针对移动低占空比无线传感网中节点主动苏醒发现邻居能耗较高的问题，提出了一种新的低能耗的选择性主动苏醒快速邻居发现（SPND）算法。该算法在使用共享邻居信息方法构建节点初始邻居集合后，在下一步发现邻居时，通过划分节点邻居子集合，有选择地进行指定节点主动苏醒时刻，实现节点低能耗的邻居发现。理论分析及实验表明，SPND算法在网络能耗大幅度优于 Disco、GBD等算法的同时，还能实现发现时延比Disco、GBD等算法更小。

在主动式邻居发现算法中，节点根据邻居信息主动苏醒，要求苏醒时能与潜在邻居节点通信，因此，对网络中节点时钟同步的要求较高。但是，网络经过一段时间的工作后，节点的时钟会发生漂移。因此，下一步将针对节点时钟会发生漂移的异步网络进行研究。

参考文献：

[1]RAZAQUE A,ELLEITHY K M. Low duty cycle,energy-efficient and mobility-based boarder node-MAC hybrid protocol for wireless sensor networks[J]. Journal of Signal Processing Systems,2015,81(2): 265-284.

[2]GUO S,YANG Y,WANG C. DaGCM: a concurrent data uploading framework for mobile data gathering in wireless sensor networks[J].IEEE Transactions on Mobile Computing,2016,15(3): 610-626.

[3]陈权,高宏. 低占空比无线传感器网络中基于动态切换的实时路由协议[J]. 通信学报,2015,10(36): 224-234.CHEN Q,GAO H. Dynamic switching based real-time routing in low-duty-cycle wireless sensor networks[J]. Journal on Communications,2015,10(36): 224-234.

[4]QIU Y,LI S,XU X,et al. Talk more listen less: energy-efficient neighbor discovery in wireless sensor networks[C]// IEEE International Conference on Computer Communications. 2016: 1-9.

[5]MENG T,WU F,CHEN G. Code-based neighbor discovery protocols in mobile wireless networks[J]. IEEE Transactions on Networking,2016,24(2): 806-819.

[6]MCGLYNN M J,BORBASH S A. Birthday protocols for low energy deployment and flexible neighbor discovery in ad hoc wireless networks[C]// The ACM MobiHoc. 2001: 137-145.

[7]YOU L,YUAN Z,YANG P,et al. ALOHA-like neighbor discovery in low-duty-cycle wireless sensor networks[C]//2011 IEEE Wireless Communications and Networking Conference (WCNC). 2011: 749-754.

[8]JIANG J R,TSENG Y C,HSU C S,et al. Quorum-based asynchronous power-saving protocols for IEEE 802.11 ad hoc networks[C]//Proceedings of Mobile Networks and Applications. 2005,10(12):169-181.[9]ZHENG R,HOU J C,SHA L. Asynchronous wakeup for ad hoc networks[C]// The 4th ACM International Symposium on Mobile Ad Hoc Networking & Computing. 2003: 35-45.

[10]DUTTA P,CULLER D. Practical asynchronous neighbor discovery and rendezvous for mobile sensing applications[C]//The 6th ACM Conference on Embedded Network Sensor Systems. 2008: 71-84.

[11]NIVEN I,ZUCKERMAN H S. An introduction to the theory of numbers.4th ed[J]. American Mathematical Monthly,1961,68(6): 401-405.

[12]KANDHALU A,LAKSHMANAN K,RAJKUMAR R R. U-connect:a low-latency energy-efficient asynchronous neighbor discovery protocol[C]//The 9th ACM/IEEE International Conference on Information Processing in Sensor Networks. 2010: 350-361.

[13]CHEN H,LOU W,WANG Z,et al. On achieving asynchronous energy-efficient neighbor discovery for mobile sensor networks[J]. IEEE Transactions on Emerging Topics in Computing,2016,PP(99): 1-12.

[14]KINDT P H,YUNGE D,REINERTH G,et al. Griassdi: mutually assisted slotless neighbor discovery[C]//ACM/IEEE International Conference on Information Processing in Sensor Networks. 2017: 93-104.

[15]CHEN L,SHU Y,GU Y,et al. Group-based neighbor discovery in low-duty-cycle mobile sensor networks[J]. IEEE Transactions on Mobile Computing,2016,15(8): 1996-2009.

[16]陈良银,颜秉姝,张靖宇,等. 移动低占空比传感网邻居发现算法[J].软件学报,2014,25(6): 1352-1368.CHEN L Y,YAN B S,ZHANG J Y,et al. Neighbor discovery algorithm in mobile low-duty-cycle wireless sensor networks[J]. Journal of Software,2014,25(6): 1352-1368.

[17]HUANG T,CHEN H,ZHANG Y,et al. EasiND: effective neighbor discovery algorithms for asynchronous and asymmetric-duty-cycle multi-channel mobile WSNs[J]. Wireless Personal Communications,2015,84(4): 3031-3055.

[18]CAMP T,BOLENG J,DAVIES V. A survey of mobility models for ad hoc network research[J]. Wireless Communications and Mobile Computing,2002,2(5): 483-502.