基于低占空因子休眠和有效度转发的节能算法

郑永刚，孙文胜

(杭州电子科技大学 通信工程学院，浙江 杭州 310018)

0 引 言

在机会网络当中，节点携带的能量是有限的，如果一个设备节点的能量过快耗尽，就会丧失接收和转发消息的能力，从而影响整个机会网络的性能。如何节约机会网络中移动节点的能量变得至关重要。为了解决这个问题，许多研究者采用周期性的休眠和唤醒移动节点的方式。但当两个节点处在休眠状态下时，它们可能无法检测到对方，导致消息在机会网络中传递的时延增加，因此需要合理的转发策略来降低消息时延[1]。

在真实的环境中，大多数的消息具有时效性，例如天气、交通信号等消息。过期的消息是毫无价值的。因此，在这种情况下，需要预先给定一个预期的消息可容忍时延时间，并且设定一个合理的周期性休眠时间，确保消息传递过程中的时延在可容忍的范围之内。

机会网络中，设计合理的休眠周期可以快速降低节点的功耗。虽然休眠对消息的时延会造成较大的影响，但如果唤醒期间采用Epdemic路由算法进行大量的消息转发，同样会使得节点的能量过早耗尽[2]。如果唤醒期间采用Direct Delivery算法，该算法在消息传输过程当中，只有遇到目的节点才会进行转发，则消息的时延显然是无法接受的。

因此需要找到一种同时拥有合理的休眠占空因子和消息转发策略的算法。本文首先利用推导得到一个占空因子，在这基础上为每个节点设置一个有效度，代表当前节点与目的节点相遇的机会大小，通过该有效度判断是否对消息进行转发。该算法的休眠机制可以明显延长节点生命周期，而其转发策略可以显著降低消息的时延，提高消息传递成功的概率。

1 相关工作

机会网络往往由一些便携设备组成，如手机、蓝牙设备等，这些移动设备的工作状况可以影响整个网络的性能。显然，能量充足的节点及其转发策略，在消息传递过程中起决定性作用。因此，如何节约机会网络中节点的能量和设计合理的转发策略，变成了一个亟待解决的问题[3]。

利用固定占空比休眠策略，文献[4]提出了一种探索式路由算法，该算法通过优化节点间接触检测方式来节约能量。通过理论分析和计算，证明了在某些特定的假设情况下，以固定占空比的形式进行休眠可以达到最佳的节能效果。虽然移动节点以固定占空比进行休眠能够达到节能的效果，但是它增加了节点检测到对方的时间和消息时延,最终影响消息传递成功的概率。

在文献[5]中，作者提出了一种基于Spray and Focus改进的算法MSAF，该算法通过为每个节点维护一个代表与目的节点相遇机会大小的有效度，比较节点自身有效度和其邻居节点有效度的大小，向有效值度大的节点转发消息。通过不断的比较相遇节点的有效度，消息会迅速向目的节点靠近。该算法虽然可以降低消息的时延但其节能效果不佳。

Biondi E研究中[6]提出的EEAODC算法，在充分考虑到可接受的消息传递时延的情况下，提出两个节点之间以合理的占空因子进行周期性休眠。Biondi E假设消息的时延小于预期时延的最大值dmax时的最小概率为Pmin，即P{DΔopt

2 FLADC算法

2.1 主要符号的含义

FLADC算法中用到的主要符号，其详细描述见表1。

2.2 求解最佳的占空因子

节点通信的时间间隔表示在机会网络当中两个移动节点成功连接并通信到下一次接触并成功传递消息的时间间隔。

表1 符号描述

通过考虑机会网络当中的所有节点，推导得出一个占空因子。假设Pmin表示消息时延大于dmax的最小概率，则有P{D

(1)

(2)

Bracciale L在其文献[8]中证明了节点在周期性休眠模式下的机会网络中通信的时间间隔仍然服从指数分布，其中休眠模式下指数分布的参数为λΔ=λΔ(λΔ=E[tΔ]-1)。当考虑网络中所有节点时，则可以得出休眠模式下消息传递成功的时延仍然近似的服从指数分布，其中指数分布的参数为λDΔ=λΔ/H，则有λDΔ=λΔ/H=λΔ/H(1≤H≤N-1)。因此，可以得出。

当节点通信的时间间隔t服从参数为λ指数分布时，基于最小概率Pmin的消息的延迟时间小于dmax。则可求出最佳占空因子为

(3)

证明：

由式(2)可以得出

(4)

由式(1)可以得出

(5)

结合式(4)和式(5)可以得出

(6)

由式(6)可推断出DΔ的概率分布函数为

(7)

由P{DΔ

(8)

即可得式(9)

(9)

由文献[9]给出的随机网络中计算平均路径长度的方法可得H

H≈logN/log(psN)

(10)

其中，N表示网络中节点的个数，ps表示在机会网络中任意两个节点通信的概率。

结合式(9)和式(10)可得

证毕。

在给定可容忍的消息时延和传递成功概率的条件下，可得到节点周期性休眠的最佳占空因子ΔFLADC。

2.3 求解节点的有效度

节点Vi的平均消息转发率Rfwd为

(11)

节点Vi的平均消息删除率Rdrop为

(12)

节点Vi的缓存占用率Roccupy为

(13)

定义节点属性FVi函数为[5]

(14)

其中，α,β,γ分别为节点Vi在当前时刻Rfwd,Rdrop和Roccupy的权重因子，并且α+β+γ=1。

节点之间的相遇属性Fcon，定义如下[5]

(15)

其中，Ncon表示节点Vi截至当前与目标节点相遇的总次数。Tcon表示相遇的总持续时间。Tint表示节点相遇的时间间隔，Ttatal表示仿真时间。

节点的有效度QVi用于决策消息的转发过程，将消息转发给与目的节点接触机会较大的中继节点，即向有效度高的节点转发消息，这样有助于提高消息的转发效率，定义如下

QVi=FVi×Fcon

(16)

3 FLADC算法的提出与实施

根据2.2中的结论，在给定消息传递时延和传递成功概率的条件下，由式(3)可以得出最佳占空因子ΔFALDC。

机会网络中节点交替进行休眠和唤醒的周期T是固定的。对每一个节点来说，如果当前系统时间等于最后醒来的时间加ton，该节点自动将自己转入睡眠状态，并将最后一次睡眠时间设置为当前系统时间。如果当前系统时间等于最后休眠的时间加(T-ton)，则节点将自动转为唤醒状态并将最后一次唤醒的时间设置为当前系统时间。

图1 FLADC算法的具体流程

4 仿真和结果分析

4.1 实验设置

在实验过程中，将FLADC与EEAODC，MSAF以及Epdemic算法进行对比。

本文使用的仿真工具ONE[11]是一款专门针对DTN网络环境开发的仿真平台，具有面向对象，离散事件驱动、可以模拟真实网络环境的特点。仿真实验是使用ONE中的工作日模型来进行的，该移动模型可以很好地模拟人类活动的真实轨迹并且具有可调控、可配置等优点。实验收集了12小时内360个节点的移动数据。仿真的具体参数设置见表2。

表2 实验所需参数

本章根据文献[12]中提出的基于工作日模型的数据拟合方法，对没有部署占空比节能策略产生的节点接触间隔时间数据进行了分析，得出该数据集服从指数分布且参数λ=5.19×10-4。设定预期最大消息延迟时间为dmax=10800s，最小概率Pmin=0.8。网络中任意两个节点通信的概率为ps=0.4，根据式(3)可以计算出ΔFLADC=0.3401，根据文献[6]中的结论可以得出ΔEEAODC=0.3612。设备的能耗功率值见表3，本文中节点的初始能量设定为17 000 J。

表3 设备的能耗功率值

4.2 剩余能量的分析与比较

在机会网络中，移动节点主要依靠电池供电其能量有限。节点在扫描周围设备，传输消息和休眠时都会不可避免地消耗能量。图2展示了在应用FLADC，EEALODC，MSAF和Epidemic算法下的机会网络中所有节点的剩余能量的平均值的变化情况，仿真结果表明在4种算法当中FLADC功耗最低，节能效果最佳，而Epidemic最差，MSAF和EEAODC算法次之。网络的生命周期指从机会网络创建开始到最后一个节点能量耗尽所经历的时间。网络的生命周期与节点的功耗成反比，因此4种算法的生命周期为TFLADC>TEEAODC>TMSAF>TEpidemic。在仿真中节点休眠占空因子的大小对节能效果起决定性作用，转发策略也会影响节点的功耗，但为次要因素。而ΔFLADC<ΔEEAODC<ΔMSAF=ΔEpidemic，与仿真结果相符。

图2 随着时间的推移节点携带平均剩余能量

4.3 消息传递概率分析与比较

消息传递概率等于成功到达目的节点的消息数量与网络中创建的所有消息的总数之比。在图3中，前6个小时内Epidemic和MSAF的消息传递概率高于FLADC和EEAODC算。因为在Epidemic和MSAF算法中，节点总是处于唤醒状态而且能量充足，不会错过任何有效的接触，而Epidemic算法传递概率会略高于MSAF，因为Epidemic是泛洪传播，效率更高，不过功耗也更大。后6个小时，部分节点因能量耗尽而失去通信能力。这种情况削弱了机会网络节点的连通性。此外，它影响消息的传递概率，因此Epidemic和MSAF的消息传递概率会快速下降而此时EEAOD和FLADC算法中节点的能量充足，消息传递概率几乎不变。

图3 随着时间的推移消息投递成功的概率

对于EEAOD算法由于其在唤醒状态采用的转发策略与Epidemic一致，所以开始时其消息传递概率略高于FLADC算法，而经过8小时左右之后FLADC算法会优于EEAODC，因为EEAODC算法没有对转发消息进行限制，对节点能量和缓存空间的消耗高于FLADC算法，一旦节点的能量或缓存空间耗尽就无法转发消息，从而影响消息传递成功概率。FLADC算法在兼顾消息传递概率的同时更加节能。

4.4 消息时延的分析与比较

消息时延等于消息从创建开始到到达目的节点所经历的时间。如图4所示，FLADC和EEAODC平均消息延迟低于MSAF和Epidemic算法。在后期仿真实验中，MSAF和Epidemic算法有更多的节点耗尽能量并失去通信能力。EEAODC在唤醒状态下的转发策略相比于FLADC算法没有进行优化，因此功耗更大节点也会较快死亡，因此FLADC的平均时延优于EEAODC算法。FLADC算法在拥有较好的节能效果的同时，兼顾了消息延迟和传递概率之间的平衡。机会网络中，FLADC算法可以确保一定的消息延时和传递成功概率，节省更多的能量，延长网络的生命周期。

图4 随着时间的推移消息传递过程中平均时延

5 结束语

在本文中，假设机会网络中任意两个节点之间的通信时间间隔服从指数分布。在给定预期最大消息时延和消息传递概率的条件下，可以计算出一个全局最佳占空因子ΔFLADC。然后根据ΔFLADC设计节点周期性休眠和唤醒的时间，在唤醒时优化了消息的转发策略，在不影响网络性能的情况下降低了功耗。最后，实验结果表明FLADC是比Epidemic，MSAF和EEAODC算法更高效的算法，可以节省更多的能量。

在真实场景中，人类之间的接触时间间隔也可能服从幂律分布[13]，而网络的结构往往会更加不均匀。在未来的工作中，可以考虑这些因素，提出更加高效的节能算法。