基于节点属性的机会网络节能路由算法

郑永刚 孙文胜

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

0 引 言

随着智能移动终端的普及和短距离无线通信技术的飞速发展，机会网络这种新形式的网络在过去几年得到迅速发展。由于这种网络的间歇性连接，源节点和目的节点之间很少存在端到端的路径[1]。在延迟容忍网络和机会网络中，为了解决节点移动带来的链路间歇性连接问题，基于存储-携带-转发的数据传输模式引起研究者的关注。

由于机会网络的载体往往为微型嵌入式移动设备，因此节点的资源是有限的。资源有限主要分为两个方面：一是节点的缓存空间是有限的。虽然目前存储技术得到迅速发展，移动节点的缓存空间也得到较大的提升，但是如果毫无节制地转发、复制、携带消息，缓存终将会耗尽，对节点自身也会带来较大的负担。二是节点携带的能量是有限的。由于移动节点一般采用电池来维持其通信所需的能量，再加上节点本身体积的限制，无法储蓄太多电量。就机会网络的实际应用场景而言，节点通常会被放在人烟稀少或者条件恶劣甚至危险的环境中，不易于更换电池或者进行能量的补给。如果某些节点的能量或者缓存耗尽，整个网络的性能会因为这些节点无法转发消息而迅速下降，最终使得网络不能保证预期的服务质量[2]。

因此，在机会网络当中如何以有限的能量完成消息的高效传输，达到低时延、高传递成功率、低功耗等效果，成为当前研究需要迫切解决的问题之一。

1 相关工作

为了应对机会网络中节点资源过快耗尽的问题。研究者们提出了许多高效节能的路由算法。通过控制网络中消息副本数量能够有效地缓解缓存不足的问题。文献[3]提出了一种基于节点质量度的Spray and Focus改进路由算法，该算法分为Spray和Focus两个阶段。在Spray阶段时算法首先通过一个参数L限制网络中消息的最大副本数，接着提取节点属性值，计算每个节点的质量度，并将消息转发给质量度高的节点，然后进入Focus阶段。在这个阶段中，携带消息副本的节点只有在遇到目的节点时才会进行消息传输。整个过程网络中消息副本的数量是固定的，因此可以缓解节点缓存不足的压力。

对于节点能量有限的问题，文献[4]提出了一种基于接触概率的低时延休眠算法。该算法通过预测节点之间的接触概率来动态地调整休眠时间，确保节点间在唤醒状态下有更多接触机会，在休眠节能的同时不降低网络的性能。

以携带智能无线设备的人类作为节点载体的网络是机会网络应用的重要领域之一。而人类的活动一般具有社区性、中心性、相似性等特点，这些特性都会影响节点消息的传递成功概率和节点能量的消耗。研究者提出了许多基于节点社会属性的路由算法。在文献[5]中，作者提出的Bubble Rap算法充分考虑了节点的社会属性，引入节点全局中心度和局部中心度两个特性，决定消息的下一个传输节点。该算法使网络性能得到了较好的提升，但由于在选择中继节点时没有考虑节点剩余能量和可用缓存等自身属性，频繁接收或转发数据包的节点将迅速耗尽能量和缓存空间而“死亡”。这可能导致消息传输失败，进而使得机会网络的性能迅速下降。

为了解决上述问题，本文提出了一种更为实用的路由算法，称为EABNA。该算法在选择中继节点时，充分考虑了节点本身的社会属性，及剩余能量和缓存空间的动态变化情况。由于选择中继节点时考虑到能量和缓存等因素，该路由算法实现了在降低消息时延和提高消息传递成功率的同时延长了节点在网络中的生命周期。

2 网络模型和节点属性

2.1 网络模型

将机会网络抽象为对称加权图G(V,E)，V是节点集合，V={V1,V2,…，VN},N≥1，N是网络中的节点数量。E表示边的集合，E={e12,e13，…，eij,…},i≠j，1≤i,j≤N，而eij表示节点i和j之间的权重。机会网络结构的模型图如图1所示。该模型一共有五个节点，分别是1、2、3、4、5。每对节点之间的连线表示它们之间至少有一次物理接触，连线上值表示两个通信节点之间的权重。

图1 机会网络结构模型

在机会网络中，每个节点可以移动，边的权重eij被定义为节点i与节点j接触的紧密程度，即到目前为止这两节点之间的接触次数在所有节点接触次数中所占的比重。

2.2 节点属性

在机会网络中，哪个节点可以被选为最佳的中继节点，何时以及如何传递消息是需要考虑的问题。为了解决这些问题，可以从网络节点中提取一些属性，并设计适当的转发策略。社会属性，如社区和中心地位相对稳定的节点，可以作为路由决策设计的基础[6]；节点本身的属性，例如能量和缓存空间是时变的，这些也是路由选择的重要因素。以下是机会网络中节点的几个重要属性的定义，可以根据这些属性设计路由算法。

2.2.1 社 区

在实际应用中，构成机会网络的节点通常是一些被人类携带的智能移动设备，而由于兴趣、工作和一些其他方面的原因，大多数人的活动仅限于某一区域。整个网络可以被划分为若干个不同的社区，与社区之间的节点相比，社区内部节点间的连接更为紧密，拥有更高的消息传递成功概率以及更低的消息时延。通过分析节点的移动数据并提取其社区属性，可以设计出更优的路由算法。

2.2.2 节点的中心性

中心性[8]反映了机会网络中节点的社会状态。如果一个节点具有较强的中心性，则代表着它有更多的机会遇到其他节点，因此比较适合作为消息转发的中继节点。

本文中，使用中心度表示节点与网络中其他节点的关联程度。在具有n个节点的无向图中，一个节点的中心度指的是与该节点有直接接触的相邻节点的总数。通过归一化消除节点之间的差异。可以得到节点的中心性表达式如下：

(1)

式中：xij表示节点i与节点j之间是否存在直接接触，如果它们之间存在直接接触，则xij为1，否则为0。

由于节点具有社区属性，根据节点是否处于社区当中，可以将节点的中心性划分为针对社区的局部中心和针对整个网络的全局中心。相应地，当计算节点的全局中心度时，n指整个网络的节点数量；当计算局部中心度时，n指当前社区的节点数量。

2.2.3 剩余能量

在实际应用环境中，任何节点的能量都是有限的，一旦节点的能量耗尽，将无法继续工作。因此，设计路由策略时，能量也是一个需要关注的要素。假设节点的初始能量为Einit，能量消耗主要集中在消息转发或接收、探测扫描周围节点、响应周围节点扫描等方面。

假设节点待机状态下的功耗为Ps，能量更新的周期为Tr；接收或发送一次消息时的能耗都为Et，Tr时间内发送和接收消息的次数为Nt；扫描一次周围节点的能耗为Es，Tr时间内扫描的次数为Ns；响应一次扫描的能耗为Er，Tr时间内响应扫描的次数为Nr。因此，根据上述条件能够得出节点的剩余能量。剩余能量可以表示为[9]:

Enew=Eold-Et×Nt-Es×Ns-Ps×Tr

(2)

在初始阶段Eold=Einit，当在仿真过程中更新能量时将最后剩余能量值设置为Eold。

2.2.4 剩余缓存空间

在实际环境中，节点的缓存空间也是有限的。节点携带或者转发消息都需要一定的缓存空间，一旦节点的缓存空间耗尽，在接收到新消息时就可能将有用的消息丢弃，导致网络的性能下降[10]。因此在指定下一跳节点时，需要考虑节点的剩余缓存空间。假设每个节点的初始缓存空间相同并且都为Binit，每个消息的大小为Bp，节点中当前携带的消息数量为Cn。因此，可以根据节点中携带的消息的数量来计算剩余缓存。节点的剩余缓存可以表示为：

Bres=Binit-Bp×Cn

(3)

仿真过程中在更新节点剩余能量的同时需要更新其剩余缓存空间的值。

3 EABNA算法设计

3.1 消息转发度量

根据2.2节中定义的节点属性，将消息的转发度量如下定义：

Met=lg(aCD+10)lg(bE+10)lg(cB+10)

(4)

式中：CD代表节点的中心度，E代表节点的剩余能量，B代表节点的剩余缓存空间，a、b、c是调谐参数。对数运算是为了消除参数的异方差性。从式(4)可以看出，如a=1、b=0、c=0时，则节点转发度量Met仅由中心度CD决定，即为Bubble Rap算法的做法。因为随着存储技术的发展，剩余缓存相比于节点中心度和剩余能量对整个网络的性能的影响会稍差一些，因此可以取系数a=2、b=2、c=1。在后续的仿真实验中可以看出，使用三个系数CD、E和B来决定转发度量可以获得更好的网络性能并达到节能的效果。当CD为局部中心度时，可以通过式(4)计算得到局部转发度量Met(Lo_Met)；当CD表示节点的全局中心度时，可计算得出全局转发度量Met(Glo_Met)。其中Met可以表示为二元组(Lo_Met，Glo_Met)。当更新Met时，节点的局部和全局转发度量值需要同时更新。

3.2 消息转发策略

本文提出的EABNA算法实际上是对Bubble Rap算法的改进。它采用简单检测算法，将网络划分成若干个社区，并且每个节点的社区信息会随着自身的移动实时更新。另外EABNA算法中存在两张信息表，分别记录了网络中所有节点的全局转发度量排名和局部转发度量排名。该算法具体的转发过程可以分为两个阶段：第一阶段消息未进入目标节点的本地社区。当携带消息的节点在移动过程中遇到其他节点时，如果相遇节点为目标节点则直接进行消息传递，本次通信结束，否则判断相遇节点是否与目标节点同属一个社区。如果是，则将消息转发给该节点，进入第二阶段，否则查询节点的全局转发度量排名表，将消息转发给第一个排名比自己大的相遇节点，由该节点重复上述流程。第二阶段是消息进入目标节点的本地社区之后。在这个阶段，根据局部转发度量进行消息传输，节点在移动过程中向局部转发度量比自身高的节点发送消息，直到遇到目标节点。EABNA算法转发消息的具体过程如图2所示。

图2 EABNA算法示意图

根据EABNA算法的转发策略，总结其伪代码如下：

ifj=Dthen

Forward(m,j);

Update(i,energy,buffer,Met);

Update(j,energy,buffer,Met);

end if

else ifComm(i)≠Comm(D) then

ifComm(j)=Comm(D) orGlo_Met(i)

Forward(m,j);

Update(i,energy,buffer,Met);

Update(j,energy,buffer,Met);

end if

else ifComm(j)=Comm(D) andLo_Met(i)

Forward(m,j);

Update(i,energy,buffer,Met);

Update(j,energy,buffer,Met);

end if

其中：Forward(m,j)表示将消息m转发给节点j；Comm(j)=Comm(D)表示节点j和节点D在同一个社区当中；Update(i,energy,buffer,Met)表示同时更新节点i的剩余能量、剩余缓存和转发度量。

4 仿真和结果分析

4.1 仿真环境设置

为了评估EABNA算法的性能，本文采用ONE模拟器搭建仿真平台[11]，并与其他两种路由算法进行对比。另外仿真中使用由Haggle Project收集的两个实验数据集，称为Cambridge[12]和Infocom06[12]。在Infocom06中，人们大多数时间处在相对集中的会议厅中，活动范围较小，节点之间的接触比较密集。而Cambridge中由于实验对象大多为学生，他们的活动范围较大，因此该数据集中节点的接触时间间隔较长。表1展示了两个数据集的详细信息。

表1 两组实验数据的特征

由于ONE模拟器对于外部输入数据的格式有特殊的要求，而从DTN 数据集的提供者CRAWDAD社区[13]下载的Infocom06和Cambridge数据集无法直接使用，需要将其格式化成表2。

表2 ONE数据集标准格式

仿真相关参数设置如下：每个节点的缓存为50 MB，每个消息的大小为500 KB，每个节点的缓存管理模式是FIFO。设定消息的通信速率为250 KB/s，每个消息都有一个对应的TTL，用来表示它在网络中的存活时长。当TTL变为0时，该消息自动被丢弃，节点属性的更新周期为300 s。

根据在2.2.1节中对社区以及社区检测的详细介绍，仿真过程中社区检测的相关参数设置如下：熟人个数的阈值α设置为5，即当两个节点的历史相遇次数大于5时，将相遇节点加入到对方的熟人集合中。熟人节点加入当前节点本地社区集合的阈值β设置为0.5。将相遇节点的本地社区与当前节点的本地社区合并的阈值γ设置为0.5，即当两个节点本地社区的交集为并集的一半时，将两个社区合并成一个本地社区。

网络中节点工作时能量的消耗情况如表3所示。本文中节点携带的能量的初始值设定为100 kJ。

表3 节点能量消耗表

4.2 仿真结果与性能分析

EABNA算法是基于Bubble Rap改进的节能路由算法，它借鉴了Bubble Rap算法的思想，将机会网络分成多个社区。但在转发消息的过程当中不仅依靠节点的本地中心度和全局中心度等属性，而且还考虑了节点的剩余能量以及剩余缓存空间。Epidemic算法是机会网络中最为典型的一种路由算法，因此将Epidemic和Bubble Rap这两种算法作为比较的对象来评价EABNA的性能。本文主要通过消息的传递成功概率、消息平均传输时延、节点存活率、路由开销这四个指标来体现EABNA算法的优劣[14]。

(1) 消息传递成功率 图3描绘了消息传递成功概率随着消息存活时间(TTL)的变化情况。从整体上看三种路由算法在两种数据集中的消息传递成功概率随着TTL的增加而增加。当TTL较小时，由于机会网络中消息的整体时延较大，部分消息在未到达目标节点时就提前失效，导致各种路由算法的消息传递成功概率也较低。但是随着消息存活时间TTL的逐渐增加，有更多的消息成功到达目标节点，因此，消息的传递成功概率也相应地增大。

(a) 在Cambridge数据集中不同路由算法的消息传递成功概率

(b) 在Infocom06数据集中不同路由算法的消息传递成功概率图3 消息传递成功概率

在相同的TTL下，Cambridge数据集中的消息传递成功概率会略小于Infocom06。因为Cambridge数据集节点的分布比较稀疏，平均每天每对节点的接触次数远小于Infocom06数据集。

对于实验中的数据集来说，Epidemic算法消息传递成功概率最差，Bubble Rap次之，EABNA最好。EABNA算法的传递成功概率比Epidemic高约32%、比Bubble Rap高约17%。根据3.2节中定义的转发度量函数，在初始阶段由于每个节点具有相同的剩余能量和缓存空间，所以中继节点的选择主要依赖于节点的中心度CD。随着时间的推移，具有较高中心度的节点的剩余能量和缓存空间迅速下降，而具有较低中心度的节点仍然具有较大的剩余能量和缓存空间。此时，尚未成功传递的消息可以由具有略低中心度和较高剩余能量及缓存空间的节点传递，从而避免由于高中心度的节点过早“死亡”导致的消息传递成功率快速降低。因此，EABNA算法可以实现比Bubble Rap和Epidemic更高的消息传递成功率。

(2) 消息平均传输时延 两种数据集中应用不同的算法的消息平均传输时延如图4所示。消息的平均传输时延随TTL的增加而增大，到达一定值之后增长速度逐渐放缓。时延较大的消息在未到达目标节点之前就会因为存活时间不足而被丢弃，而这部分消息并不计算在消息的平均时延之内，因此消息的平均传输时延和TTL成正比关系。当TTL到达一定值后大部分消息都能够在此TTL之内完成传输，于是消息平均时延的增速就会趋于平缓。

(a) 在Cambridge数据集中不同路由算法的消息平均传输时延

(b) 在Infocom06数据集中不同路由算法的消息平均传输时延图4 消息平均传输时延

在相同TTL的条件下，Cambridge数据集中的消息平均时延会略大于Infoncom06数据集。造成这个结果的主要原因是Infoncom06数据集中的节点比较密集，消息有更多的机会传输到目标节点。

在两种数据集当中EABNA算法的表现均优于Bubble Rap和Epidemic算法。从仿真结果来看，EABNA算法中消息的平均时延比Bubble Rap降低了10%左右，比Epidemic降低了28%左右。虽然在节点资源充足的情况下，Bubble Rap和Epidemic的消息时延都低于EABNA算法，但随着部分节点资源耗尽，Epidemic和Bubble Rap算法的时延会迅速上升。因此，从整体上来看EABNA算法在消息平均时延方面的表现更好。

(3) 节点生存率 图5反映了EABNA、Bubble Rap、Epidemic三种路由算法的节点存活率在两种数据集中随TTL的变化情况。从整体上来看，三种算法随着消息存活时间TTL呈递减趋势，而且在Infocom06数据集中节点存活率下降的速度相对于Cambridge数据集较快。当TTL维持在一个较小值时，由于消息快速失效，节点间的通信频率较低，减少了对节点的资源如能量和缓存空间的消耗，延长了节点的存活时间。但随着消息存活时间TTL的增大，网络中节点间通信次数也会递增并伴随资源消耗的增加，导致节点存活率下降。在节点通信相对频繁的Infocom06数据集中，节点更加容易“死亡”，其存活率比Cambridge数据集低。

(a) 在Cambridge数据集中不同路由算法的节点存活率

(b) 在Infocom06数据集中不同路由算法的节点存活率图5 节点生存概率

从两种数据集中都能够得出，在相同的TTL下Epidemic算法的节点存活率最低，Bubble Rap次之，而EABNA算法的节点存活率最高。与其他两种算法相比，EABNA算法的节点存活率可以提高245%左右，即在仿真结束时还有更多的节点仍然存活。Epidemic算法采用消息的泛洪传输机制，因此表现最差。而Bubble Rap算法中一味将消息转发给中心度高的节点，导致这些节点转发过多的消息而耗尽资源的不足。EABNA算法在选择中继节点时均衡了节点中心度、剩余能量、剩余缓存空间三者之间的关系，从一定程度上延长了网络生命周期。

(4) 路由开销 图6为三种算法在路由开销方面的仿真结果。显然在任何数据集当中，Epidemic的路由开销是最大的，而Bubble Rap和EABNA算法的路由开销的性能相差不大，都为Epidemic的1/3左右，并且随着TTL的增大缓慢增加。因为Epidemic在传输消息的过程中会大量复制消息副本，并发送给所有接触的节点，大大增加了路由开销。而EABNA算法的路由开销略微的大于Bubble Rap算法。Bubble Rap算法对节点中心度的依赖更高，在资源充足的情况下可以减少消息的转发次数。但是当资源不足时，Bubble Rap算法的路由开销会大于EABNA算法。综合上述原因再结合仿真结果可得出EABNA和Bubble Rap算法的路由开销基本相近。

(a) 在Cambridge数据集中不同路由算法的路由开销

(b) 在Infocom06数据集中不同路由算法的路由开销图6 路由开销

5 结 语

本文提出了一种基于节点属性的高效节能路由算法EABNA。当选择中继节点时充分考虑了节点的社会属性和其本身属性的动态变化。本文使用两种现实生活中的移动数据集对EABNA、BubbeRap、Epidemic三种算法进行仿真。通过详细比较和分析实验结果，最终可以得出EABNA算法虽然略微牺牲了路由开销方面的性能，但是其消息传递成功率、消息平均传输时延、节点存活率方面的性能都有较大的提升，延长了机会网络生命周期。

机会网络中在选择消息转发的中继节点时还可以考虑更多的属性，例如节点的时空属性[15]等。通过这些属性减少转发次数，延长网络的生命周期，达到一定的节能效果。