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

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

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

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

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

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

为了降低节点的能量损耗并提高消息的交付率，按照如下的方法设计能量控制机制。首先，定义节点的当前可用能量比($\text{ava }\!\!\_\!\!\text{ energyratio}$)以及能量比阈值($\text{energy }\!\!\_\!\!\text{ threshold}$)为：

式中，$\text{current }\!\!\_\!\!\text{ energy}$为节点的当前能量；$\text{initial }\!\!\_\!\!\text{ energy}$为节点的初始能量；N为节点所携带的消息总数；m_k为消息k的字节大小；$\text{transmit }\!\!\_\!\!\text{ energy}$为传输每字节所需要的能量；e为基准的可用能量比。

对应的能量控制机制为：

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

2) 若$e\le \text{ava }\!\!\_\!\!\text{ energyratio}<\text{energy }\!\!\_\!\!\text{ threshold}$，意味着节点能够转发消息，但没有足够的能量将所有消息转发给其他节点。此时该节点只接收目的节点为自身的消息，并尽可能多地将缓存中的消息转发给相遇节点，避免大量消息在等待目的节点的过程中因为生存周期的限制而无法到达目的节点的情况。

3) 若$\text{ava }\!\!\_\!\!\text{ energyratio}\ge \text{energy }\!\!\_\!\!\text{ threshold}$，意味着节点能量充裕。为了提高消息的交付率，当前节点不仅将消息转发给中间节点，还将帮助其他节点转发消息。

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

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

1) 若节点i的$\text{ava }\!\!\_\!\!\text{ energyratio}$小于e或者节点j的$\text{ava }\!\!\_\!\!\text{ energyratio}$小于$\text{energy }\!\!\_\!\!\text{ threshold}$，则节点i不向j转发消息；否则，执行下一步。

2) 若节点i的$\text{ava }\!\!\_\!\!\text{ energyratio}$小于$\text{energy }\!\!\_\!\!\text{ threshold}$且大于等于e，连接强度P(j,d)大于P(i,d)，为了不因能量耗尽而丢弃缓存中的消息，节点i将消息转发给节点j。

3) 若节点i的$\text{ava }\!\!\_\!\!\text{ energyratio}$大于等于$\text{energy }\!\!\_\!\!\text{ threshold}$，节点有足够的能量转发消息，根据消息的Hop来决定是否将消息交由节点j转发。

① 若$\text{Hop}<2$且$\text{Ext}{{D}_{j}}>\beta \text{Ext}{{D}_{i}}$(β为大于1的调节因子)，节点i将消息转发给节点j。否则，不转发此消息；

② 若$2\le \text{Hop}<4$，节点j的某个邻居节点k满足$P(k,d)>P(i,d)$或节点j的连接强度P(j,d)>P(i,d)，为了不因转发次数的限制而丢弃消息，节点i将消息转发给节点j；

③ 若$4\le \text{Hop}<6$且$P(j,d)>P(i,d)$，节点i将消息转发给节点j。否则，不转发此消息。

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

节点i向节点j转发消息的伪代码：

if 节点i的可用能量比小于e or

节点j的可用能量比小于能量阈值 then

　　continue

else

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

　if 节点i的可用能量比小于能量阈值 &&连接强度 $P\left( j,d \right)>P\left( i,d \right)$then

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

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

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

　case (Hop<2) :

　if $\text{Ext}{{D}_{j}}>\beta \text{Ext}{{D}_{i}}$then

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

case ($2\le \text{Hop}<4$) :

　if 连接强度$P\left( j,d \right)>P(i,d)$ or
节点j邻居k的连接强度$P\left( k,d \right)>P(i,d)$ then

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

case ($4\le \text{Hop}<6$) :

　if 连接强度$P\left( j,d \right)>P(i,d)$ then

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

　else

　　continue

　end if

end for
end if

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

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

表2

表2 仿真参数设置

表2 仿真参数设置 仿真参数 数据 MIT Pmtrs Infocom06 节点数 97 49 98 仿真时间/s 3000000 70000 50000 消息产生间隔/s 200～300 200～300 200～300 消息大小/M 0.5～1 0.5～1 0.5～1 消息生存周期/min 0～240 0～50 0～40 缓存空间/M 10 10 10 消息转发耗能 /mAh×KB-1 0.003 0.003 0.003 节点活跃耗能 /mAh×s-1 0.005 0.005 0.005 节点初始能量 /mAh 1000～4000 1000～4000 1000～4000

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

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

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

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

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

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

图1

图1 MIT场景下的交付率

图2

图2 Pmtrs场景下的交付率

图3

图3 Infocom06场景下的交付率

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

图4

图4 MIT场景下的网络开销

图5

图5 Pmtrs场景下的网络开销

图6

图6 Infocom06场景下的网络开销

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

图7

图7 MIT场景下的能量损耗

图8

图8 Pmtrs场景下的能量损耗

图9

图9 Infocom06场景下的能量损耗

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