一种结合休眠机制的改进Epidemic机会网络 节能路由算法

周春月,董耀聪,田 慧

(北京交通大学 电子信息工程学院，北京 100044)

无线传感器网络(Wireless Sensor Networks，WSNs)作为21世纪最具影响力的技术之一，自问世以来，由于其应用广泛，学术拓展性强、学科交叉广等特点一直都是无线通信领域的研究热点.但许多移动无线传感器网络(Mobile Wireless Sensor Networks，MWSNs)的应用场景中，如复杂自然环境中的手持设备组网，自然保护区野生动物行为特性观测组网、灾难后的迅速组网等，传感器节点移动的不确定性会带来网络的连通性下降甚至连接中断等现象，这将导致整体网络的性能下降，下降的原因在于传统的路由方法在不连通的网络中无法起到作用.

一般的WSNs网络层路由算法中，如AODV，LEACH协议等，源节点到目的节点必须存在至少一条完整的通信路径.而在上述的场景中，这种方法显然不可行，所以研究者们提出了机会网络(Opportunistic Networks)的概念[1].机会网络是一种节点移动性较强的WSNs，节点之间靠移动带来的相遇机会进行通信，源节点和目的节点可以位于两个不同的网络区域，可以不存在完整的路由路径，节点以“存储—携带—转发”的方式进行分组交换，但这种网络的延迟会大幅度上升(几分钟至几小时都有可能).不过在某些对延迟容忍程度较高的移动场景中，机会网络是非常合适的组网形式.

比较经典的机会网络的路由算法有Epidemic算法[2]、Spray and Wait算法[3]等，其中Epidemic算法简单易实现，是许多应用场景中的首选.Epidemic算法的目标是最大化数据分组的传输率、最小化网络延迟，其主要思想是让两个相遇的节点交换彼此没有的数据分组，理论上只要时间充足，网络中的每个节点都将拥有所有的数据分组.数据分组的副本会大量充斥在网络中，过多的数据交换会导致节点能量的大量消耗.而机会网络的应用场景中，一般难以随时更换传感器节点的能源，节点能量耗尽后就会进入死亡状态，一些转发任务较多的节点则会更早的进入死亡状态，造成整个网络的寿命减小，因此能耗问题一直都是机会网络路由算法首要考虑的问题之一[4].Epidemic算法作为最可能进行部署实现的算法之一，其资源消耗过大和节点传输容易过度洪泛的问题亟待解决.

关于Epidemic算法的改进一直都是学者们研究的热点.文献[3]提出的Spray and Wait算法也是基于洪泛策略，但它限制了数据分组的副本数量从而避免了过度洪泛.它将数据交换过程分为了Spray和Wait两个阶段，Spray阶段中，依旧使用洪泛，源节点向邻节点发送数目为L的数据分组的副本，L可根据网络节点密度设定；Wait阶段中，停止洪泛，如果数据分组已经送达目的节点，则停止转发该分组，如果没送达目的节点，则通过直传的方式，等遇到目的节点再转发出去.这种算法显著地降低了分组传输量，并且具有较强的适应性和鲁棒性，无论网络负载和节点密度如何变化都可通过设置不同的L来进行调整.但节点在Spray阶段仍会消耗不少的能量.

文献[5]以节点剩余能量和节点缓存区大小为标准对Epidemic算法进行了改进，提出了EAE算法，它规定只有当邻节点的剩余能量和空闲缓存比自己大时，才进行信息的传送，但是在一些移动性比较强的网络中，仅仅因为这两个指标就拒绝邻节点的通信可能会导致节点丧失大量的通信机会.

文献[6]提出了一种结合休眠制度的算法ERASA，该算法主要是令孤立节点进入到低功耗的休眠状态，并将概要向量(Summary Vector，SV)分组的单播方式改为广播，虽然在网络整体的能量平衡方面能够达到节省开销、延长网络寿命的目的，但针对的主要是孤立节点和特定场景，实际上节点更多的是处在一种运动的状态，孤立节点的数量在整个网络中也并不是多数，因此该算法有局限性.此外还有许多通过如限制跳数[7]、限制数据分组生存时间[8]、或根据节点活跃度[9]选择下一跳节点等方式来减小Epidemic算法开销的研究.

关于Epidemic算法的改进方法，一般是在网络性能与资源消耗之间做取舍与平衡，本文作者以减小节点能耗、延长网络寿命为主要目标，为提高Epidemic算法在机会网络中的整体效率与表现，结合实际应用场景中节点的特性，对Epidemic算法做出改进，提出一种结合休眠机制的机会网络节能路由(Energy-saving Opportunistic Networks Routing based on Sleeping Mechanism and Epidemic Routing，ERSE)算法.

1 Epidemic算法研究

Epidemic算法的每个节点缓存区内，都保存一个独特的散列表，称为概要向量或SV向量[2]，用来记录该节点中存有哪些数据分组.每个数据分组都会带有一个32位的全局唯一标识，数据分组将自己的全局唯一标识映射成为SV向量.

如图1所示，A、B两个节点在进入各自的通信范围后，分组交换的过程可分为3个步骤：

1)节点A将自己的概要向量SVA发送给节点B，SVA代表了节点A缓存区中的全部分组.

3)A接收到该分组后，根据其中的信息可知晓哪些分组是节点B需要的，随后将这些分组发送给节点B.

图1 Epidemic算法路由过程Fig.1 Epidemic routing process

实际上这只是整个通信过程的一半，节点B也会按这个步骤重复一遍，向节点A发送其没有的数据分组，才算完成整个信息交换过程.

Epidemic算法虽然简单，但需要考虑许多问题，如：

1)路由的不确定性：源节点并不清楚目的节点与其他中继节点的位置，因此在数据传输过程中存在随机性因素，会影响分组的传输成功率.

2)资源分配：因为信息交换是基于对数据分组的复制，所以需要网络在性能和资源消耗之间进行选择.

3)可靠性和安全性问题：源节点无法立即收到目标节点发来的ACK信息，所以不能对网络进行QoS等方面的评价，并且因为数据分组长期存在于网络中，理论上可以从任何节点处进行窃取.

2 ERSE算法

2.1 算法模型

ERSE参照一般的无线传感器网络，对节点的通信模型做了简化，并借鉴文献[10]给出的关于通信范围、感知范围和干扰范围的定义.

通信范围(Communication Range)Rc是指两个节点可以正常进行数据收发并正确编解码的范围；感知范围(Searching Range)Rs指的是根据天线的灵敏度等硬件条件计算得出的节点能感知到的最大区域；干扰范围(Interference Range)RI指通信范围和感知范围之间的区域，在这个区域内节点能感知到其他节点的信号，但无法进行通信,见图2.

图2 节点通信系统模型Fig.2 Node communication model

通信范围和感知范围都与节点的功率相关，一般感知范围大于等于通信范围，即

Rs=γRc,γ≥1

(1)

为了讨论和计算方便，假设Rc=Rs(即γ=1)，也就是当节点感知到有其他节点进入自己的通信范围时，两者就可以进行数据交换，并忽略可能的边界效应对通信过程带来的影响.

节点的状态分为休眠状态和激活状态，休眠状态就是节点进入休眠、关闭自身大多数模块的状态，而节点正常进行监测、数据收发等动作的状态则为激活状态.设T为一个休眠期,则

T=T休眠+T激活

(2)

机会网络中节点移动性比较强，数据传输机会与其他网络相比较少，休眠算法也应保证在减小节点能耗的同时尽量不错过节点可能遇到的通信机会.

2.2 休眠状态的判决条件

ERSE算法中节点判决自己是否进入休眠的流程分为3个步骤，设当前节点处在t0时刻并处于激活状态.

1)如果从(t0-TA)至t0时刻，节点进行的数据交换次数(与一个节点交换多个数据分组记为1次)n满足如下条件

n≤Ns

(3)

则节点进入步骤2)，Ns的取值视不同的网络场景而定，一般设置为0；如果不满足，则节点保持激活状态.即，如果处在激活状态的节点某一段时间TA内并未进行数据交换或数据交换次数有限(遇到的节点数量有限)，则节点进入休眠判决的第一步.

2)计算当前t0时刻节点剩余能量百分比εt.

(4)

假设网络中部署的每个节点的初始能量Et都是一致且已知的,部署后节点的当前能量可量化为

Ep=Et-Eb-Ed

(5)

式中：Eb是节点维护缓存区及自身其他元器件等方面的硬件消耗;Ed是数据传输过程中的能量消耗，与传输次数和节点的发射、接收功率相关，每个节点由于其所处的外部环境不同、相遇节点的通信情景不同等原因，相同时刻的剩余能量都会不同.

节点计算出t0时刻的εt后，按以下条件判断

(6)

此强制休眠状态与步骤3)要讨论的休眠状态并不相同，强制休眠状态的持续时间为一个固定的时间段TC，但一般都比较长.β为固定值，可以根据实际网络场景取值[11]，影响β取值的因素为网络节点密度，单位时间节点平均能耗等，其默认取值为0.15～0.25，即当节点能量少于15%～25%时会进入强制休眠状态.

3)根据缓存区内的TV向量判断节点是否进入休眠.ERSE算法规定节点除了使用SV向量记录数据分组的标识以外，还需维护一个散列表时间向量(Time Vector，TV)用来记录节点最近一段时间内收到的SV向量的个数和标识，与SV向量不同，TV向量并不需要发送给其他节点.TV向量的长度能记录最近一段时间ΔT内收到的SV向量即可.

节点读取TV向量后，可以得到ΔT时间段内接收SV向量的数量NΔT，之后节点按以下规则判决是否进入休眠：

(7)

式中：Nl可根据不同的网络场景中的节点密度来设置.ERSE算法通过对历史信息的查询，做出判断：如果节点在ΔT内接收了数量比较少的SV分组，因为SV向量是单播发送且每个节点的SV向量都是不同且唯一的.虽然机会网络中假定节点的运动是随机的，但在实际场景中，两个相邻的较短的时间段内(这两段时间可以不相等)，大部分节点的运动规律并不会出现太大的偏差，因此，预测节点在未来的一段时间里也有很大的可能遇到的节点数量较少，这段时间就用来让节点休眠.如果节点在这段时间里接收到了比较多的SV向量分组，则预测节点在未来一段时间也会有比较大的可能性遇到更多的节点，这样ERSE算法就尽量保证了节点在不丧失大多数通信机会的情况下能够进入休眠状态,从而尽最大可能节省自己的能量.

2.3 休眠状态的唤醒条件

机会网络中的节点都是移动的，所以休眠状态Ts的大小由每个节点各自的运动速度和通信模型所决定.因此ERSE算法休眠时间为

(8)

式中：RCR为节点的通信范围的半径；vi为节点i的移动速度，一般情况下设置为节点当前的移动速度.

这样计算休眠时间是因为ERSE假设了一个比较特殊的情况，如图3所示.

图3 ERSE算法设想的极端情况Fig.3 An extreme situation in ERSE Routing

其中，节点A的通信范围用实心圆表示，节点B的通信范围用空心圆表示，t0时刻的节点用A、B表示，t1时刻的节点用A′，B′表示.假设t0时刻，节点B刚好进入节点A的通信范围内，同时节点A按判决条件进入了休眠状态，虽然节点移动的轨迹一般不会是一条直线，但假设节点A正以其当前的移动速度(或其他合理的速度)直线运动，这样节点A可以移动理论上最远的距离，同时假设节点B正以任意速度向远离A的方向移动，这样如果节点B的速度不大于节点A的速度，那么在t1时刻，由休眠状态唤醒的节点A仍然处在可以和节点B进行通信的范围内.也就是说，首先假设两个节点同向而行并移动了最远的直线距离，然后保证两个节点依然可以进行通信，那么在大多数情况下节点并非直线移动，两个节点移动后的距离可能更近，节点的休眠并不会影响它与其他节点通信的机会.当然在某些情况下，如节点B保持大于节点A的速度同向直线远离A，那么节点A就会丧失与节点B的通信机会，不过在随机移动的实际场景中，节点并不会时刻保持直线运动.

节点结束一个休眠时间后，将自动唤醒并感知节点通信范围内的其他节点数量，此步骤与上一小节的步骤1是基本是相同的.如果节点唤醒后通信范围内的其他节点数量n大于一个阈值NA(设置条件与Ns相同，通常设置为0)则节点进入激活状态与其他节点进行正常的数据交换；如果不超过该阈值，则节点继续进入下一次休眠，此休眠时间与上次休眠时间相同；如果激活状态下的节点在一段时间TA内没有进行数据交换或者说数据交换的次数不超过某个设定的阈值(此规则同样适用于强制休眠状态)，则节点重新进入休眠判决的步骤1).TA可根据节点的移动速度和实际网络场景来设置，通常情况下，TA与Ts有着正相关的关系，即

TA=αTs，

(9)

式中：α一般默认设置为0.5～1，表示当节点移动出一个通信半径一半以上的距离时如果依然没有遇到通信的机会，那么节点可以开始判决自己进行休眠，影响α取值的因素主要为节点密度，如果节点密度特别大，那么α的取值可适当减小，这是因为节点密度比较小时，节点可能很长一段时间都碰不到其他节点，但为了不错过通信的机会，仍然要保持激活的状态持续一个适当的时间后再进行休眠；而当节点密度比较大时，节点遇到其他节点的概率大大增加，因此可以减小α值，以让节点有机会可以进行休眠，否则节点可能会一直处于激活状态.当然如果将TA时间段内数据交换次数的阈值设为0，步骤1)节点t0时刻的节点数量参数Ns也设置为0.

2.4 ERSE算法流程及复杂度分析

图4为算法节点可能出现的状态.

图4 节点随时间的状态变化Fig.4 Node state changes when time flows

图4中横坐标为时间，纵坐标为节点能耗.判决步骤3)中的ΔT取值范围一般包括上一次节点的激活状态，可令

(10)

节点不同时间的移动速度可能不同，所以图4(b)中前后两对Ts的长度并不相同(假设由当前移动速度计算得出).两个图中节点从休眠状态醒来，感知周围节点并做出继续休眠的判决的这段时间记为TD，TD的时间一般很短，图4为了显示清楚而拉长了这段流程的宽度.

整个ERSE算法流程的伪代码如下.

1:For each Nodeiin activation state,When in a period of timeTA

2: Ifn>Ns

3: Thenimaintain the activation state and make data switch with others

4: Else ifεt<β

5: Thenienter the forced sleeping state

6:Ts=TC

7: Else ifNΔT≥Nl

8: Thenimaintain the activation state for a timeTA

9:TA=αTs，α≤1

10: Elseienter the normal sleeping state

12: End if

13: End if

14: End if

15: For each Nodeiin sleeping state,Wheniawakes att0

16: Ifn

17: Thenienter the sleeping state

18:Ts=Tsbefore

19: Elseienter the activation state and make data switch with others

20: End if

可以看到，因为不存在循环操作，对于每一个节点，ERSE算法的时间复杂度为O(1)，但对节点数为n的网络，若每个节点都参与转发，算法复杂度则为O(n).

3 仿真结果及分析

本文选用ONE(Opportunistic Network Environment)仿真平台对ERSE算法进行仿真.ONE是基于Java语言开发的开源仿真平台，主要功能是搭建机会网络环境，对网络各参数进行仿真模拟.本文选取节点的运动模型为基于地图约束的随机模型，路由算法为ERSE算法.

其他参数方面，节点总数设置为100～300个，节点初始能量为2 000 mAh，扫描一次的能耗为0.2 mAh，传输一个数据分组的能耗为1 mAh，节点最大可通信范围为20 m，缓存区大小为100 MB，传输速率500 KB/s，数据分组大小为100 KB～1 MB不等.

为了全面的比较ERSE算法的优劣之处，本文选取了Epidemic算法和Spray and Wait算法作为比较对象.而结果方面则选取了分组传输成功率，传输延迟，节点剩余能量3个指标来衡量路由算法的性能.图5为这3种算法在分组传输成功率方面的表现.

图5 分组传输成功率Fig.5 Message delivery rate

从图5中可以看出，Spray and Wait算法因为采用了一部分直传的路由策略，所以在节点数量比较少的时候体现出比较高的数据传输成功率.由于ERSE算法采取的是与Epidemic算法一致的洪泛策略，所以在节点数量较多时，只要保证节点能把握住与其他节点的通信机会，就能够在长时间的通信过程中呈现出比较高的分组传输成功率，而ERSE算法采取了节点间非同步的休眠机制，只让节点在确定通信范围内没有其他节点时才进入休眠，这就保证了整个网络中处在通信范围内的两个节点几乎不会错过通信的机会，因此，ERSE算法在仿真中体现出的分组传输成功率与Epidemic算法接近.在多次仿真中，在节点密度增加时，3种算法表现出的传输成功率几乎不相上下，而当节点密度上升时，由于可中继的节点变多了，传输成功率也会上升.

图6为3种算法在传输延迟方面的性能表现.

图6 传输时延比较Fig.6 Delay of message transmission

网络时延是网络的一个重要性能之一，但机会网络属于延迟容忍网络(DTN)的一种，不论采取何种类型的路由算法，时延都会比较高.图6中，3种算法的网络时延大小与节点的数量关系不大，Spray and Wait算法的传输时延要优于其他算法，这是因为该算法在第二阶段采取了直传方式，因此延时会较前两者有所降低.理论上，节点数量变得越来越多后，可中继的节点数目变多了，所以传输时延应该会有比较明显的下降，但在仿真场景里，300个节点还达不到高节点密度的要求，因此并未显示出较明显的变化.仿真结果表明：ERSE算法并未因节点进入休眠而使传输延迟增加太多，但是有少量的增加，这是因为在ERSE算法中，一旦某个转发任务重的节点剩余能量超过了规定的阈值，该节点会强制进入休眠时间固定的休眠状态，而在节点数量不多时，或多或少都会影响到网络的传输时延，不过由于机会网络中节点的运动性较强，因此中心节点的作用被弱化，只需保证节点不过快的进入死亡状态，就能够使传输时延不过多的增加，这也是ERSE算法在休眠判决条件中加入能量阈值判断条件的原因.

图7表示了3种算法节点的平均能耗随时间变化的表现.

图7 节点平均能耗比较Fig.7 Node energy consumption

可以看出，ERSE通过采用休眠机制，大大减小了节点的能耗，并延长了网络的生命周期.反观Epidemic算法，在仿真进行到一半时已经基本耗光了节点内的所有能量，而选择性进行数据发送的Spray and Wait算法由于前期采用的是与Epidemic算法一样的洪泛策略，所以它的能耗也是比较高的，但是比Epidemic算法要好.在仿真将要结束时，ERSE算法的节点仍保持有平均约30%左右的能量.这里要说明的是，由于仿真时间有限，所以本文中节点总能量设置是偏低的，节点发送和扫描的能耗设置则偏高.实际场景中节点的能量会有很大程度的增强，而能耗方面也会因工业工艺的发展而降低不少，所以实际应用场景中ERSE能够让节点保持更长时间的活跃状态，保证网络的性能在长时间内不会下降.

4 结论

机会网络作为无线传感器网络的一种，其路由算法需要重点解决两个方面的问题：节点能耗和节点运动性，本文主要针对能耗问题做了研究，具体结论如下.

1)在分析机会网络经典的洪泛路由Epidemic算法的基础上，针对Epidemic算法的洪泛特性消耗了大量网络资源，及算法缺少判断机制等缺点，综合考虑机会网络无中心节点的分布式结构和节点移动性较强的特点，在前人研究的基础上，对Epidemic算法做了新的改进，提出了一种结合休眠机制并同时结合了节点运动特性的节能路由算法—ERSE，

2)算法的核心思想是让节点通过三个步骤判断自身是否进入休眠，具体做法是在节点缓存区内维护一个TV向量表，用来记录节点过去一段时间的数据交换信息，以此判断节点未来一段时间可能的状态；同时对节点的休眠时间做了科学的假设和讨论，提出了以节点的移动速度和通信模型为参数，动态调整休眠时间的方法.

3)仿真结果表明，ERSE算法在保证Epidemic算法原有的优点上，通过动态调整休眠时间和唤醒时机，可以让节点不错过大多数的通信机会，同时让空闲的节点进入休眠状态保存自己的能量，并极大延长了转发任务较重的核心节点的生存时间，由这两点改进出发，从整体上提高了网络的寿命，提升了网络的稳定性和效率.

关于机会网络路由算法，未来工作是设计一种节点能够判断和预测自己可能的运动路径的路由机制，让节点优先选择符合自己运动规律的中继转发节点，从而降低转发分组的次数，达到节省能量和提高转发效率的目标.