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

引用本文

周春月, 董耀聪, 田慧. 一种结合休眠机制的改进Epidemic机会网络节能路由算法[J]. 北京交通大学学报, 2019,43(2): 18-24.
ZHOU Chunyue, DONG Yaocong, TIAN Hui. An opportunistic networks energy-saving routing algorithm based on Epidemic and sleeping mechanism[J]. JOURNAL OF BEIJING JIAOTONG UNIVERSITY, 2019,43(2): 18-24.
Doi:10.11860/j.issn.1673-0291.20180113 复制到剪切板

Permissions

北京交通大学学报编辑部所有

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

周春月, 董耀聪, 田慧

北京交通大学电子信息工程学院,北京 100044

第一作者:周春月(1973—),女,黑龙江大庆人,高级工程师,博士.研究方向为下一代通信网络技术和信息安全.email:chyzhou@bjtu.edu.cn.

收稿日期: 2018-07-31

基金: 北京市自然科学基金(4172045)

摘要

机会网络是一种节点运动性较强的无线传感器网络,网络拓扑的动态变化导致节点之间的通信路径经常断裂,因此传统的路由机制并不适用.在分析机会网络的经典路由Epidemic的基础上,以降低节点能耗为目标,结合休眠机制对Epidemic进行了优化改进,提出了一种全新的机会网络路由算法(Energy-saving Opportunistic Networks Routing based on Sleeping Mechanism and Epidemic Routing,ERSE).该算法在判决节点进入休眠的问题上,做了三次判断.第一次是为了让节点不错过当前可能的通信机会,当有一段时间没有遇到其他节点时,才进入休眠判决过程;第二次是为了防止让转发任务较重的节点过早陷入死亡状态,让低于能量阈值的节点进入强制休眠状态;第三次则是根据节点以往的运动规律预测未来可能出现的场景,并对休眠时间做了一个极端的假设,保证节点尽量不错过大部分的通信机会.仿真结果表明,与经典的机会网络路由算法相比,ERSE算法在保证了网络性能基本不下降的同时,大幅度降低了节点的能耗.

关键词: 无线传感器网络; 机会网络; 路由算法; 休眠机制; 节能

中图分类号:TP393 文献标志码:A 文章编号:1673-0291(2019)02-0018-07

An opportunistic networks energy-saving routing algorithm based on Epidemic and sleeping mechanism

ZHOU Chunyue, DONG Yaocong, TIAN Hui

School of Electronic and Information Engineering, Beijing Jiaotong University, Beijing 100044,China

Fund:Beijing Municipal Natural Science Foundation (4172045)

Abstract

The opportunistic network is a wireless sensor network in which nodes have a strong motion.The dynamic change of the network topology makes the path between two nodes break frequently.Therefore the traditional routing algorithm can not be suitable.This paper analyzes the classic opportunistic networks routing algorithm Epidemic. Based on the analysis, it proposes a new algorithm ERSE combined with the sleeping mechanism which target is to reduce the energy consumption of nodes. ERSE makes three steps to judge the node whether to fall into the sleeping state. The first step is to make the node do not miss the current opportunity to communicate with others. Only the nodes who do not meet other nodes for a period of time will enter the sleeping judge process. The second step is to prevent the node with heavy forwarding task from falling into a state of death.It makes a threshold for nodes to judge itself whether to enter the mandatory sleeping. The last step is making the nodes predict future scenarios based on the previous motion so that the nodes can not miss the vast majority of the communication opportunities with others. The simulation results show that compared with the classical routing algorithms,the ERSE algorithm ensures that the network performance is not obviously changed while the energy consumption of the nodes is greatly reduced.

Keyword: wireless sensor networks; opportunistic networks; routing algorithm; sleeping mechanism; energy-saving

文章图片

无线传感器网络(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个步骤:

	Figure Option View Download New Window
	图1 Epidemic算法路由过程Fig.1 Epidemic routing process

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

2)节点 $B$ 在接收到 $S V_{A}$ 后, 先对自己的概要向量 $S V_{B}$ 进行一次逻辑非运算, 得到 ${\bar{SV}}_{B}$ , 然后再和 $S V_{A}$ 进行逻辑与运算, 得到的结果就代表了A节点有但B节点没有的数据分组, 并将这个向量发回给节点A.

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

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

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

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

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

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

2 ERSE算法

2.1 算法模型

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

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

	Figure Option View Download New Window
	图2 节点通信系统模型Fig.2 Node communication model

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

$R_{s} = γ R_{c}, γ \geq 1 (1)$

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

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

T=T_休眠+T_激活 (2)

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

2.2 休眠状态的判决条件

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

1)如果从 $(t_{0} - T_{A})$ 至 $t_{0}$ 时刻, 节点进行的数据交换次数(与一个节点交换多个数据分组记为1次) $n$ 满足如下条件

$n \leq N_{s} (3)$

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

2)计算当前 $t_{0}$ 时刻节点剩余能量百分比 $ε_{t} .$

$ε_{t} = \frac{E_{p}}{E_{t}} (4)$

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

$E_{p} = E_{t} - E_{b} - E_{d} (5)$

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

节点计算出 $t_{0}$ 时刻的 $ε_{t}$ 后, 按以下条件判断

$\{\begin{array}{l} ε_{t} \geq β, 进行步骤 3) \\ ε_{t} < β, 节点进入强制休眠状态并跳过步骤 3) \end{array} (6)$

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

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

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

$\{\begin{array}{l} N_{Δ T} < N_{l}, 节点进入休眠状态 \\ N_{Δ T} \geq N_{l}, 节点不进入休眠状态, \\ 再次进行时长为 T_{A} 的监测 \end{array} (7)$

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

2.3 休眠状态的唤醒条件

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

$T_{s} = \frac{R_{CR}}{v_{i}} (8)$

式中R_CR为节点的通信范围的半径; $v_{i}$ 为节点 $i$ 的移动速度, 一般情况下设置为节点当前的移动速度.

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

	Figure Option View Download New Window
	图3 ERSE算法设想的极端情况Fig.3 An extreme situation in ERSE Routing

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

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

$T_{A} = α T_{s}, (9)$

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

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

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

	Figure Option View Download New Window
	图4 节点随时间的状态变化Fig.4 Node state changes when time flows

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

$Δ T = \frac{m \times 2 R_{CR}}{{\overset{̅}{v}}_{i}} (10)$

式中: $m$ 为从上一次激活状态至这次判决过程中节点休眠的次数; ${\overset{̅}{v}}_{i}$ 为节点的平均移动速度.这样取值的原因是为了保证 $Δ T$ 尽量覆盖两次或更多的激活状态, 保证作出休眠判决时, 节点能读取到的TV表中的数据不会因为太旧而失去参考价值, 也不会因为太新而陷入永远判决节点进入休眠的死循环.

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

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

1:For each Node $i$ in activation state, When in a period of time $T_{A}$

2: If $n > N_{s}$

3: Then i maintain the activation state and make data switch with others

4: Else if $ε_{t} < β$

5: Then $i$ enter the forced sleeping state

6: $T_{s} = T_{C}$

7: Else if $N_{Δ T} \geq N_{l}$

8: Then $i$ maintain the activation state for a time $T_{A}$

9: $T_{A} = α T_{s}$ , $α \leq$ 1

10: Else $i$ enter the normal sleeping state

11: $T_{s} = \frac{R_{CR}}{v_{i}}$

12: End if

13: End if

14: End if

15: For each Node $i$ in sleeping state, When $i$ awakes at $t_{0}$

16: If $n < N_{A}$

17: Then i enter the sleeping state

18: $T_{s} = T_{sbefore}$

19: Else $i$ enter 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算法.

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

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

	Figure Option View Download New Window
	图5 分组传输成功率Fig.5 Message delivery rate

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

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

	Figure Option View Download New Window
	图6 传输时延比较Fig.6 Delay of message transmission

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

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

	Figure Option View Download New Window
	图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算法原有的优点上, 通过动态调整休眠时间和唤醒时机, 可以让节点不错过大多数的通信机会, 同时让空闲的节点进入休眠状态保存自己的能量, 并极大延长了转发任务较重的核心节点的生存时间, 由这两点改进出发, 从整体上提高了网络的寿命, 提升了网络的稳定性和效率.

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

参考文献

文献列表

[1]	熊永民, 孙利民, 牛建伟, 等. 机会网络[J]. 软件学报, 2009, 20(1): 124-137. XIONG Yongmin, SUN Limin, NIU Jianwei, et al. Opportunistic networks[J]. Journal of Softwre, 2009, 20(1): 124-137. (in Chinese) [本文引用:1]
[2]	VAHDAT A, BECKER D. Epidemic routing for partially connected Ad Hoc networks[R]. Durham: Duke University, 2000. [本文引用:2]
[3]	SPYROPOULOS T, PSOUNIS K, RAGHAVENDRA C S. Spray and wait: an efficient routing scheme for intermittently connected mobile networks[C]//Proceedings of the ACM SIGCOMM Workshop on Delay-tolerant Networking, 2005: 252-259. [本文引用:2]
[4]	孙践知. 机会网络路由算法[M]. 北京: 人民邮电出版社, 2013: 1-16. SUN Jianzhi. Opportunistic network routing algorithm[M]. Beijing: Posts & Telecom Press, 2013: 1-16. (in Chinese) [本文引用:1]
[5]	BHED B B. Improving energy consumption of epidemic routing in delay tolerant networks[C]//10th International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing, 2016: 278-283. [本文引用:1]
[6]	郑文茜. 机会网络节能路由算法[D]. 重庆: 重庆邮电大学, 2013. ZHENG Wenqian. A study on energy-saving routing algorithms for opportunistic networks[D]. Chongqing: Chongqing University of Posts and Telecommunications, 2013. (in Chinese) [本文引用:1]
[7]	BAYHAN S, HYYTI E, KANGASHARJU J. Analysis of hop limit in opportunistic networks by static and time-aggregated graphs[C]//IEEE International Conference on Communications, 2015: 3287-3292. [本文引用:1]
[8]	SRIVIDYAC H, RAKESH N. Enhancement and performance analysis of epidemic routing protocol for delay tolerant networks[C]//International Conference on Inventive Systems and Control, 2017: 1-5. [本文引用:1]
[9]	NGUYEN D T, MINH Q T. Adaptive spray: An efficient restricted epidemic routing scheme for delay tolerant networks[C]//15th IEEE Annual Consumer Communications & Networking Conference, 2018: 1-2. [本文引用:1]
[10]	SHIHK P, CHEN Y D, CHANG C C. A physical/virtual carrier-sense-based power control MAC protocol for collision avoidance in wireless Ad Hoc networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2011, 22(2): 193-207. [本文引用:1]
[11]	杨鹏, 刘豆, 王汝言, 等. 节点剩余能量均衡的机会网络路由机制[J]. 系统工程与电子技术, 2015, 37(8): 1894-1901. YANG Peng, LIU Dou, WANG Ruyan, et al. Node residual energy balanced routing mechanism for opportunistic networks[J]. Systems Engineering and Electronics, 2015, 37(8): 1894-1901. (in Chinese) [本文引用:1]

2009

0.0

... 而在上述的场景中,这种方法显然不可行,所以研究者们提出了机会网络(Opportunistic Networks)的概念^[1] ...

2000

0.0

... 比较经典的机会网络的路由算法有Epidemic算法^[2]、Spray and Wait算法^[3]等,其中Epidemic算法简单易实现,是许多应用场景中的首选 ...

... 1 Epidemic算法研究Epidemic算法的每个节点缓存区内,都保存一个独特的散列表,称为概要向量或SV向量^[2],用来记录该节点中存有哪些数据分组 ...

2005

0.0

... 比较经典的机会网络的路由算法有Epidemic算法^[2]、Spray and Wait算法^[3]等,其中Epidemic算法简单易实现,是许多应用场景中的首选 ...

... 文献[3]提出的Spray and Wait算法也是基于洪泛策略,但它限制了数据分组的副本数量从而避免了过度洪泛 ...

2013

0.0

... 而机会网络的应用场景中,一般难以随时更换传感器节点的能源,节点能量耗尽后就会进入死亡状态,一些转发任务较多的节点则会更早的进入死亡状态,造成整个网络的寿命减小,因此能耗问题一直都是机会网络路由算法首要考虑的问题之一^[4] ...

2016

0.0

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

2013

0.0

... 文献[6]提出了一种结合休眠制度的算法ERASA,该算法主要是令孤立节点进入到低功耗的休眠状态,并将概要向量(Summary Vector,SV)分组的单播方式改为广播,虽然在网络整体的能量平衡方面能够达到节省开销、延长网络寿命的目的,但针对的主要是孤立节点和特定场景,实际上节点更多的是处在一种运动的状态,孤立节点的数量在整个网络中也并不是多数,因此该算法有局限性 ...

2015

0.0

... 此外还有许多通过如限制跳数^[7]、限制数据分组生存时间^[8]、或根据节点活跃度^[9]选择下一跳节点等方式来减小Epidemic算法开销的研究 ...

2017

0.0

... 此外还有许多通过如限制跳数^[7]、限制数据分组生存时间^[8]、或根据节点活跃度^[9]选择下一跳节点等方式来减小Epidemic算法开销的研究 ...

2018

0.0

... 此外还有许多通过如限制跳数^[7]、限制数据分组生存时间^[8]、或根据节点活跃度^[9]选择下一跳节点等方式来减小Epidemic算法开销的研究 ...

2011

0.0

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

2015

0.0

杨鹏, 刘豆, 王汝言, 等. 节点剩余能量均衡的机会网络路由机制[J]. 系统工程与电子技术, 2015, 37(8): 1894-1901.

YANG

Peng

, LIU

Dou

, WANG

Ruyan

, et al. Node residual energy balanced routing mechanism for opportunistic networks[J]. Systems Engineering and Electronics, 2015, 37(8): 1894-1901. (in Chinese)

In opportunistic networks, the node energy is limited and hard to recharge, and the energy consumption has a determinant impact on the network lifetime and performance. To solve the problem that socially popular nodes may quickly deplete their energy resources and consequently not participate in the routing process, the node activity and residual-energy are exploited to evaluate the comprehensive forwarding ability, and then an node residual energy balanced routing mechanism (NREB) for opportunistic networks is introduced. The NREB saves energy by rationally choosing the next-hop node to avoid unnecessary forwarding, which can also balance the network overhead. Simulation results show that the proposed mechanism can ensure the delivery ratio while balancing the energy consumption between nodes and thus to prolong the network lifetime.

1. Broadband Ubiquitous Network Research Laboratory, Chongqing University of Posts and Telecommunications,Chongqing 400065, China; 2. China Academy of Telecommunications Research, Beijing 100191, China

机会网络中的节点能量受限且难以补充,其能量消耗情况影响着整个网络的生命周期和性能。针对社区机会网络中部分活跃节点频繁转发数据所导致的能量消耗过快问题,提出一种节点剩余能量均衡的机会网络路由机制,根据节点剩余能量及其在网络中的活跃程度感知其综合转发能力,进而合理地选择下一跳节点,有效减少不必要的转发次数,均衡网络负载。数值结果表明,所提出的机制能够在保证网络投递率的同时均衡网络能耗,延长网络生命周期。

... β为固定值,可以根据实际网络场景取值^[11],影响 β取值的因素为网络节点密度,单位时间节点平均能耗等,其默认取值为0 ...