基于小世界与能效的容迟网络路由算法

周朝荣，徐小琼，杨 柳，马小霞(. 四川师范大学物理与电子工程学院 成都 600；2. 无线传感器网络四川省高校重点实验室 成都 600)



基于小世界与能效的容迟网络路由算法

周朝荣1,2，徐小琼1,2，杨 柳1，马小霞1
(1. 四川师范大学物理与电子工程学院 成都 610101；2. 无线传感器网络四川省高校重点实验室 成都 610101)

【摘要】容迟网络(DTN)具有小世界特性，一条消息至多需要五至六跳中间节点就可从源节点到达目的节点。为此，算法(TBSF)结合小世界特性通过限制中间节点数目来提高消息的交付率，但该方法没有考虑节点的能耗以及社会权威的问题。该文从节点能效与社会权威出发提出一种改进的算法。该算法设计了能量控制机制，并在扩展度中心性的基础上讨论节点的社会权威，在消息的转发过程中突出权威节点的作用。仿真结果表明，该算法在保持较高消息交付率的同时能够降低网络的能耗。

关 键 词度中心性； 容迟网络； 能量控制； 小世界特性； 社会权威

A Routing Algorithm Based on Small World and Energy Efficiency in Delay Tolerant Network

ZHOU Zhao-rong1,2, XU Xiao-qiong1,2, YANG Liu1, and MA Xiao-xia1
(1. School of Physics and Electronic Engineering, Sichuan Normal University Chengdu 610101; 2. Key Laboratory of Wireless Sensor Networks, Sichuan Province Higher Education System Chengdu 610101)

Abstract Due to the small-world property in delay tolerant network (DTN), messages can reach destination nodes at most by five or six intermediate nodes. Therefore, the algorithm of the-best-so-far (TBSF) improved the delivery probability by limiting the number of intermediate nodes with the small-world property. Nevertheless, the issues of energy efficiency and social authority are not concerned in TBSF. In this paper, an enhanced algorithm is proposed by considering energy efficiency and social authority. The algorithm includes the energy control mechanism, considers the social authority of nodes by extending the degree centricity and highlights the role of nodes with higher social authority during forwarding messages. The corresponding simulation results show that the proposed algorithm can maintain the high message delivery probability and reduce the energy consumption..

Key words degree centricity; DTN; energy control; small-world property; social authority

DTN是一类特殊的移动自组织网络，这类网络具有拓扑变化快、传输时延高、间歇性连通等特点。任意节点对之间不一定存在端到端的即时通信路径，消息在网络中的传播采用“存储→携带→转发”的路由机制。节点之间若要进行通信，需要借助相对运动所形成的通信机会。相应地，路由算法成为这类网络相关研究工作中的关键[1]。由于网络带宽资源以及消息生存时间的限制，经历多跳中间节点后依然滞留在网络中的消息副本不仅无助于提升消息的交付率，反而会造成不必要的资源开销。因此，需要在路由算法中考虑如何限制中间节点的数目。此外，由于便携性的要求，移动节点设备的能量极其有限，路由算法的设计还需要兼顾节点的能量控制机制。这些问题在现有的路由算法中未能较好地解决，因此，还有深入研究路由算法的必要。

1 相关工作

近年来，研究人员针对DTN的不同应用场景提出了多种路由算法。其中，泛洪路由算法Epidemic[2]基于消息的洪泛机制，可以实现较高的消息交付率，但同时产生了大量的消息副本，占用较多的网络资源，容易造成网络的堵塞。为了解决这一问题，文献[3]提出了ProphetV2算法。该算法利用节点间相遇的历史信息估算节点对消息的转发概率，虽然消息交付率低于Epidemic算法，但极大地降低了网络资源的开销。需要说明的是，ProphetV2算法仅仅基于节点的历史接触信息，并未考虑节点的社会属性。节点设备通常是人们所使用或携带的，人的行为具有社会属性，对应的节点设备也将表现出一定的社会属性，因此，有必要从社会属性的角度设计路由算法。Simbet算法[4]结合社会相似性与介数性指标，提出了如何选取合适的中间节点转发消息。文献[5]基于社团与中心性两种指标提出了Bubble rap的转发机制，该机制分别基于全局中心性与局部中心性采用冒泡过程实现消息的转发。此外，考虑到便携性的要求，节点设备的能量极其有限，路由算法中还需要兼顾能耗的问题。为此，文献[6]在Bubble rap算法的基础上给出了节点能量敏感的路由算法，该算法在估算转发概率时引入能量模块，将消息转发给高能效的节点。需要指出的是，上述算法虽然在一定程度上降低了消息的传输时延、提高了交付率，但没有限制消息转发过程中的中间节点数目。根据小世界特性[7-8]，文献[9]根据小世界特性提出了TBSF算法，该算法限制消息传播过程中的中间节点数目，但没有考虑节点的能耗以及社会权威等问题。本文将在TBSF算法的基础上设计节点的能量控制机制并结合度中心性讨论节点的社会权威，进一步地提出能效敏感的改进路由算法。

2 节点的社会权威与能量控制机制

2.1 节点权威性

在人类社会中，不同的人有着不同的社会属性，比如不同的社会权威或者社会影响力，若能够充分利用这类社会属性，将有效地提高信息的传播效率。在DTN中，节点设备的携带者通常为具有一定社会属性的人，相应地，由多个节点设备所构成的网络类似于人类社会，不同的节点设备体现不同的社会权威，在消息转发的过程中发挥不同的作用。刻画社会权威可以借助度中心性，定义为：

式中，ni表示与节点i直接相连的邻居个数；K为网络中的节点总数。节点的度中心性越高，意味着与该节点直接相连的邻居节点数目越多，该节点就越有可能位于网络的中心位置，也就具有更高的社会权威。相应地，这类节点可在消息转发的过程中扮演更加重要的角色。

需要指出的是，上述度中心性只考虑一跳邻居节点的情况，这样定义的社会权威仅仅涉及局部信息，不能全面地反映节点在整个网络中的影响力。本文扩展上述度中心性的定义，除了一跳邻居之外，还考虑其他多跳的邻居。在同时考虑一跳与两跳邻居节点的前提下，扩展后的度中心性定义为：

式中，nk为节点k的邻居节点个数；n(i , k )为节点i和k的共同邻居节点数目。扩展后的度中心性能够更加准确地反映节点在整个网络的社会权威。

2.2 能量控制机制

为了降低节点的能量损耗并提高消息的交付率，按照如下的方法设计能量控制机制。首先，定义节点的当前可用能量比( ava_energyratio )以及能量比阈值(energy_threshold )为：

式中，current_energy为节点的当前能量；initial_energy为节点的初始能量；N为节点所携带的消息总数；mk为消息k的字节大小；transmit_energy为传输每字节所需要的能量；e为基准的可用能量比。

对应的能量控制机制为：

1) 若ava_energyratio< e，意味着节点的剩余能量不多，由于节点活跃需要耗能，为了增加节点的生存时间，节点只将消息转发给相遇节点为消息目的地的节点。

3 结合能效的改进路由算法

3.1 算法思想

首先，比较相邻节点的度中心性使消息尽量流向社会权威较高的节点；然后，根据小世界特性，控制消息转发过程中的中间节点数目，减少网络中的消息副本数量，提高带宽的利用率；最后，通过比较邻居节点的连接强度，将消息交给邻居节点中连接强度大的节点进行转发。

3.2 算法流程

在改进的算法中，首先初始化各条消息的跳数Hop= 0，消息每经过一次中间节点的转发，跳数Hop就加1。当Hop= 6时，为了抑制网络中的消息副本数量，消息被丢弃。假设节点i携带有目的节点为d的一条消息，当节点i与另一节点j相遇，节点i根据以下的准则判断是否将该消息转发给节点j。

1) 若节点i的ava_energyratio小于e或者节点j的ava_energyratio小于energy_threshold，则节点i不向j转发消息；否则，执行下一步。

2) 若节点i的ava_energyratio小于energy_ threshold且大于等于e，连接强度P( j , d )大于为了不因能量耗尽而丢弃缓存中的消息，节点i将消息转发给节点j。

3) 若节点i的ava_energyratio大于等于energy_threshold，节点有足够的能量转发消息，根据消息的Hop来决定是否将消息交由节点j转发。

其中，连接强度的计算类似文献[9]，完整的算法伪码如下。

节点i向节点j转发消息的伪代码：if 节点i的可用能量比小于e or节点j的可用能量比小于能量阈值 then

continue else

for (节点i缓存中的消息) {

if 节点i的可用能量比小于能量阈值 &&

节点i向节点j转发消息；

else if 节点i可用能量比不小于能量阈值 then

switch (节点i缓存消息的Hop )

case (Hop< 2 ) :

节点i向节点j转发消息； break;

节点i向节点j转发消息； break;

节点i向节点j转发消息； break;

else

continue

end if

end for

end if

4 仿真结果分析

4.1 仿真场景

本文采用机会网络环境(opportunistic network environment, ONE)仿真器[10]进行路由算法的仿真比较。为了使实验更接近真实情况，采用MIT数据[11]、Pmtrs数据[12]以及Infocom06数据[13]3种真实的移动Trace。MIT数据记录了97个持有智能手机Nokia6600的师生在9个月里的接触信息；Pmtrs数据持续19天，通过49个移动轨迹记录器记录设备间的接触信息；Infocom06数据来自于2006年某会议现场的数据收集，记录了78个参会人员携带的蓝牙设备以及20个静止设备之间的接触信息。

4.2 仿真参数设置

初始化基准的可用能量比为e =0.1，度中心性调节因子β=1.2，节点能耗的设置参考文献[14]，此外，考虑到各个场景对应着不同的仿真时长，对于仿真时长较高的场景，应该允许更加宽松的消息生存时间，对应的参数设置如表2所示。

表2　仿真参数设置

4.3 算法评价指标

为了比较路由算法的性能，评价指标如下：

1) 消息交付率，定义为网络中成功转发的消息数与产生的总消息数的比值，高的消息交付率意味着网络中更多的消息能够成功到达到目的节点，这是评价路由算法性能优劣的最重要指标。

2) 网络开销，它是衡量网络带宽效率的重要指标，定义为成功转发一条消息平均需要的消息副本数。开销越大意味着消息副本越多，由于存储转发节点的资源有限而极易造成网络传输性能的下降。

3) 能量损耗，考虑到节点能耗的因素，定义能量损耗指标为平均每节点成功交付一条消息所消耗的能量，计算为：

式中，cost_energy表示能量损耗；total_energy为网络消耗的总能量；K为网络中的节点总数；M为成功交付的消息数。能量损耗可用于评价路由算法在有限能量前提下的资源利用率。

4.4 仿真结果分析

基于上述真实移动Trace的场景，在不同消息生存周期下仿真比较了TBSF、ProphetV2以及本文提出的改进路由算法的网络性能。

4.4.1 3种场景下的交付率

图1～图3分别给出MIT、Pmtrs以及Infocom06 在3种场景下的消息交付率，此处的TBSFMODI代表本文所提出的改进路由算法。从图中可以看出，在不同的场景下，TBSFMODI的消息交付率均优于ProphetV2与TBSF。这是由于TBSFMODI算法在度中心性的基础上扩展了节点的社会权威，并在消息的转发过程中突出权威节点的作用，从而使得消息在有限的跳数和生存时间内更快地被转发至目的节点。

图1　MIT场景下的交付率

图2　Pmtrs场景下的交付率

图3　Infocom06场景下的交付率

4.4.2 3种场景下的网络开销

图4~图6分别给出3种场景下的网络开销。由于TBSFMODI考虑了容迟网络的小世界特性，在消息转发时限制消息的中间节点数目，降低了过多消息副本所带来的网络开销，因此，TBSFMODI的网络开销明显低于ProphetV2算法与TBSF算法。

图4　MIT场景下的网络开销

图5　Pmtrs场景下的网络开销

图6　Infocom06场景下的网络开销

4.4.3 3种场景下的能量损耗

图7~图9展示了在3种场景下的能量损耗。结果表明，TBSFMODI的能量损耗均低于其他两种算法。这是由于TBSFMODI算法设计了合理的能量控制机制，在消息转发时根据节点当前剩余能量来设计消息转发方式，并且针对消息的转发跳数进行了更加细致的划分，从而有效地减少了能量损耗。

图7 MIT场景下的能量损耗

图8　Pmtrs场景下的能量损耗

图9　Infocom06场景下的能量损耗

5 结 束 语

本文针对容迟网络中现有路由算法的不足，通过扩展度中心性讨论节点的社会权威，并结合容迟网络的小世界特性，在设计能量控制机制的基础上，提出了改进的路由算法。进一步地，根据真实移动场景进行了仿真实验。仿真结果表明，本文所提出的改进算法有着较好的系统性能，能够在保持高交付率、低开销的同时节省能量。

参 考 文 献

[1] FALL K. A delay-tolerant network architecture for challenged internets[C]//Proceedings of the 2003 Conference on Applications, Technologies, Architectures, And Protocols for Computer Communications. Karlsruhe, Germany: ACM, 2003: 27-34.

[2] VAHDAT A, BECKER D. Epidemic routing for partially connected ad hoc networks[EB/OL]. [2014-10-10]. http:// link.springer.com/chapter/10.1007%2F978-3-540-27767-5_ 24.

[3] GRASIC S, DAVIES E, LINDGREN A, et al. The evolution of a DTN routing protocol-PRoPHETv2[C]//Proceedings of the 6th ACM Workshop on Challenged Network. Las Vegas, Nevada: ACM, 2011: 27-30.

[4] DALY E, HAAHR M. Social network analysis for routing in disconnected delay-tolerant MANET[C]//Proceedings of the 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing. Montreal, Canada: ACM, 2007: 32-40.

[5] HUI P, CROWCROFT J, YONEKI E. Bubble rap: Social-based forwarding in delay-tolerant networks[J]. IEEE Transactions on Mobile Computing, 2011, 10(11): 1576-1589.

[6] CHILIPIREA C, PETRE A, DOBRE C. Energy-aware social-based routing in opportunistic networks[C]//27th International Conference on Advanced Information Networking and Applications Workshops (WAINA). Murcia, Spain: IEEE, 2013: 791-796.

[7] MILGRAM S. The small world problem[J]. Psychology Today, 1967, 2(1): 60-67.

[8] ANGELA S, FRANCESCO C, MARCELLO C. Human-mobility enabled networks in urban environments:Is there any (mobile wireless) small world out there?[J]. Ad Hoc Networks, 2012(10): 1520-1531.

[9] WEI K, ZENG D, GUO S, et al. Social-aware relay node selection in delay tolerant networks[C]//22nd International Conference on ICCCN: Computer Communications and Networks. Nassau, Bahamas: IEEE, 2013: 1-7.

[10] KERANEN A, OTT J, KARKKAINEN T. The one simulator for DTN protocol evaluation[C]//Proceedings of the 3rd International ICST Conference on Simulation Tools and Techniques. Arizona, USA: IEEE, 2009.

[11] EAGLE N, PENTLAND A. Reality mining: Sensing complex social systems[J]. Personal and Ubiquitous Computing, 2006, 10(4): 255-268.

[12] MERONI P, GAITTO S, PAGANI E, et al, Data setunimi/pmtr[DB/OL]. [2014-09-30]. http://crawdad.cs. dartmouth.edu /unimi/pmtr, Dec. 2008.

[13] SCOTT J, GASS R, CROWCROFT J, HUI P, et al. DataSetCambridge/haggle/imote/infocom2006[DB/OL]. [2009-05-29].http://crawdad.cs.d-artmouth.edu/cambridge/ haggle/imote/infocom2006, May 2009.

[14] DERANGO F, AMELIO S, FAZIO P. Enhancements of epidemic routing in delay tolerant networks from an energy perspective[C]//9th International Wireless Communications and Mobile Computing Conference (IWCMC). Valencia, Italy: IEEE, 2013: 731-735.

编 辑 叶 芳

作者简介：周朝荣(1975 − )，男，博士，副教授，主要从事无线网络方面的研究.

基金项目：四川省教育厅重点项目(14ZA0033, 15CZ0004)；无线传感器网络四川省高校重点实验室开放项目(SCWSN201404)

收稿日期：2015 − 01 − 10；修回日期： 2015 − 10 − 30

中图分类号TP393

文献标志码A

doi:10.3969/j.issn.1001-0548.2016.01.022