机会路由算法中层次化的辅助信息获取机制*

宋明阳，袁培燕

河南师范大学 计算机与信息工程学院，河南 新乡 453000

1 引言

移动机会网络[1]被广泛应用于车载通信、深空网络、环境监测等场景。在传输数据时，由于数据包的源节点和目的节点之间不存在可靠的端到端路径，数据包的传输依赖节点的移动性和偶发性接触，以“存储、携带、转发”的模式工作。

为了选择有效的中继节点，通常需要引入额外的信息进行决策判断（本文称之为辅助信息），协助路由算法转发数据包。这些辅助性信息主要包括数据属性、节点信息、拓扑信息以及信息融合等4类。比如数据包效用值和存活时间、节点的移动速度、社会关系以及节点之间的接触概率、网络的局部拓扑等。

明显地，辅助信息对于机会路由算法的性能有着重要的影响。然而，在目前的信息辅助型机会路由算法中普遍采用一种基于节点间机会接触的洪泛型扩散方式来共享辅助信息，即每当两个节点接触时，它们就会向对方请求并获取相关信息来完成辅助信息的共享。然而由于便携式设备（节点）存储容量和能量有限，既要存储感知数据（数据包），又要存储辅助信息，将对移动设备的容量提出更高的要求。同时，大量的辅助信息的交换也会带来浪费网络带宽和设备能量等问题。因此如何解决信息的共享需求与移动设备资源受限之间的矛盾是机会网络中的关键性问题。针对此问题，本文提出了一种层次化的辅助信息获取机制，该机制通过两个层面来对节点进行定义与划分，并使节点间有选择性地进行辅助信息的共享：首先，为保证网络中辅助信息的更新速度较快，将网络中具有紧密关系的节点定义为邻居，令互为邻居的两个节点间进行信息获取。其次，为保证辅助信息的网络覆盖率较高，将网络中的节点划分为社会性节点和普通节点，使信息的获取主要发生在社会性节点与普通节点之间。这样一来，理论上可以在不影响网络性能的基础上减少节点之间信息的获取次数。本文的主要贡献如下：

（1）通过观察节点间的机会性接触，分析节点间的接触规律，将机会网络中隐性的邻居关系以显性的方式表现出来，提出了一种机会网络邻居发现机制。

（2）在邻居发现的基础上，提出了一种分层的辅助信息获取机制。一方面，令少部分社会性节点负责辅助信息的交换；另一方面，令互为邻居的节点间进行辅助信息的交换。

（3）提出的辅助信息获取机制可以无缝地集成于经典的信息辅助型机会路由算法之中。实验结果显示，在不显著影响路由投递率、延时与包投递备份数的基础上，大幅度减少了节点之间辅助信息的获取次数，节省了网络资源。

本文组织结构如下：第2章对当前的信息辅助型机会路由算法进行了回顾；第3章描述了层次化辅助信息的获取机制；第4章讨论了如何将提出的辅助信息获取机制集成到经典的路由算法PRoPHET的过程；第5章进行实验分析；最后对全文进行总结。

2 相关工作

利用一些额外的信息协助节点进行数据包转发决策是当前机会网络路由算法研究的重点之一。常用的信息主要包括数据包属性、节点信息、拓扑信息以及上述信息的融合等4类[2]。

基于数据包属性的路由算法主要指利用数据包的效用值、投递优先级、包存活时间（time to live，TTL）以及备份数目等辅助性信息来定制路由策略。如文献[3]根据TTL、跳数、包的备份数量和大小等知识将节点携带的数据包进行排序，并提出一种基于包存活时间的路由协议（TTL based routing，TBR），该协议根据排序结果管理节点缓冲区中数据包的转发和删除。文献[4]提出了一种基于数据包时间敏感效用的路由协议（time-sensitive opportunistic utilitybased routing，TOUR），其中每一个包维护一个随时间线性递减的效用值，随着数据包在节点间的不断转发，包的效用值会随着包的投递延时和代价的增大而逐渐递减，当效用值为0时包被丢弃。

基于节点信息的路由算法以节点属性（运动模式、能量、邻节点变化情况等）、节点社会性以及节点间接触率为依据制定路由协议。在这方面，文献[5]提出了经典的利用接触和传输记录的概率路由算法（probabilistic routing protocol using history of encounters and transitivity，PRoPHET），其根据节点间的接触概率进行路由决策，当两个节点发生接触时，它们的接触概率相应增加，而当它们经过一段时间没有发生接触时，接触概率相应下降。文献[6]提出了一种结合喷雾-等待策略并考虑缓冲区管理的多备份概率路由（hybrid probabilistic routing scheme using multi-copies，HUM）。文献[7]提出了利用直接接触的节点和两跳邻居节点的历史接触信息计算接触概率的改进型概率路由（improved probabilistic routing algorithm，IPRA）。通过研究人类活动的社会性规律，文献[8]提出了冒泡路由算法（BUBBLE），其根据社会性划分节点的社会等级，并根据节点的社会等级和所处的社区来决定数据包的转发。文献[9]通过研究节点间的历史性接触信息、节点移动模式、节点的社会性，并受网页排名算法（PageRank）[10]启发，提出了人群排名路由算法（PeopleRank），其将机会网络描绘为一个社交网络图，并通过计算节点间的社交关系来获得节点的社会性并按其排序，最后根据节点的社会性高低进行路由决策。文献[11]利用邻居节点的接触信息，分布式地估计节点的中心度和相似度，并融合二者提出基于中心度与相似度的路由算法（routing based on betweenness centrality and similarity，SimBet）。当两个节点相遇时，需要交换各自邻域知识，计算中心度和相似度，然后将数据包转发给效用值较高的节点。

基于拓扑属性的路由算法主要指利用机会网络的局部拓扑变化、链路信息等制定路由决策。文献[12]通过观察发现，机会网络中的一些节点在特定的时间段内会形成一个暂时性的联通子网，因而提出了瞬态社区结构的概念。其表示在不同时间段内，机会网络中某些节点可以组成连通的社区，并且一个节点在不同的时刻可以属于不同的社区。该概念有助于区分机会网络的社区边界，并在网络中适当的范围内评估节点的中心性。

信息融合策略是将上述方法的特点进行结合的路由算法。文献[13]提出了一种结合节点投递概率与数据包优先级的转发策略。首先对节点之间的投递概率进行比较来决定是否转发数据包，当决定转发时，优先考虑存活时间较短的数据包。

上述类型的信息辅助型路由算法所关注的是数据包的转发问题。然而对于节点间辅助信息如何有效地收集与获取这一关键问题，尚无相关工作。本文则围绕这一问题进行讨论，并提出层次化的辅助信息获取机制。

3 层次化辅助信息获取机制

3.1 节点间邻居关系

辅助信息的高效共享依赖于节点之间的邻居关系，但是与传统强连通网络中显性的邻居关系不同，移动机会网络中，节点的接触情况是时变的、复杂的。有的节点对频繁接触，有的偶尔接触，有的接触时间长，有的间隔时间长。节点之间更多时候呈现的是一种隐性的连接方式。针对这种隐性的连接方式，本文联合节点接触情况的稳定性、规律性来判别节点的邻居关系：如果一对节点在接触时长和接触时间间隔方面有较高的稳定性和较好的规律性，则将它们定义为邻居。通过识别节点的邻居关系，一方面可以将机会网络中具有紧密关系的节点对更清晰地刻画出来，另一方面邻居节点之间信息的传播速度也更快。因此，在机会网络中通过该方法确定邻居关系，并通过邻居关系来决定节点间信息是否进行共享，可以在保证辅助信息更新速度较快的基础上减少辅助信息的获取次数。本文用到的主要术语见表1。

Table 1 Major used notations表1 本文主要术语

3.1.1 节点间接触稳定性

本文对机会网络中节点间接触的稳定性描述为：在时间段内，如果两个节点的平均接触时长大于或等于某个阈值，说明这两个节点的接触具有稳定性。数学描述如下：对于时间段内的机会网络G(V)，任意节点a,b∈V并且a≠b。Ca,b表示a和b在时间段内的接触次数，SCa,b表示a和b在时间段内接触的总时长。a和b在时间段内的单次平均接触时长为ACa,b=SCa,b/Ca,b。a与其他节点的单次平均接触时长之和的平均值为。若ACa,b≥ASCa，则a与b的接触是稳定的。

3.1.2 节点间接触规律性

本文用信息熵来量化节点的接触规律性。信息熵是用来描述一个概率事件有序化程度的度量，事件越是无序，其熵值越高，反之熵值越低。根据最大熵原理可知，如果某个随机事件的概率分布是最平均的，也就是说该随机事件的各种表现形式出现的概率是接近相等的，此时概率分布的信息熵最大。由于机会网络中节点移动是随机的，节点对之间的间隔时长出现的长短也是一个随机事件。如果该随机事件的信息熵越大，则节点对之间各间隔时长越趋于一致，说明节点对之间接触越有规律。

设在时间段内节点a和节点b有w次接触间隔，QIal,b代表第l次接触间隔的时长。a和b的接触间隔时长的总和表示为SIa,b。第l次接触间隔时长出现的概率用表示。根据信息熵的公式得，a和b的接触间隔的信息熵为lgPRl a,b)。节点a与其他节点的接触间隔信息熵之和的平均值为。由最大熵原理可知，当节点对的接触间隔时长信息熵越大，则代表节点对接触间隔时长出现的概率越是趋于平均，节点对之间的接触越有规律。本文定义：当Ea,b≥AEa，则说明a和b的接触是有规律的。

3.1.3 邻居发现算法

邻居发现算法主要是用于判断机会网络中的节点对是否相互为邻居，如算法1所示。

算法1IdentifyNeighbor

输入：机会网络节点集合V，节点a,b∈V。

输出：邻居节点集合NE。

1.NE←∅

2.for任意节点a∈Vdo

3.for任意节点b∈Vdo

4. 计算a与b在时间段内的单次接触平均时长ACa,b

5. 设w为a与b在时间段内的接触间隔次数

6. forl=1towdo

7. 计算第l次接触间隔时长出现的概率

8. end for

9. 计算接触间隔信息熵Ea,b

10.end for

11.计算a与其他节点的单次平均接触时长之和的平均值ASCa

12.计算a与其他节点的接触间隔信息熵之和的平均值AEa

13.ifACa,b≥ASCa⋂Ea,b≥AEathen

14.NE=NE⋃(a,b)

15.end if

16.end for

17.returnNE

算法2～4行（进入二层循环），对于任意节点a，计算它与任意节点b的平均接触时长ACa,b。算法6～8行计算a和b的每一次接触间隔时长出现的概率。算法9～10行计算a和b的接触间隔时长的信息熵Ea,b，退出内层循环。算法11～12行分别计算出a与其他节点在时间段内平均接触时长之和的平均值ASCa和接触间隔时长信息熵之和的平均值AEa。算法13～17行判断是否ACa,b≥ASCa且Ea,b≥AEa，如满足条件则a和b为邻居并将该节点对加入邻居关系集合NE中，算法最后退出循环并返回NE。

3.2 辅助信息选择性移交

本文使用辅助信息的选择性移交方法来减少信息的获取次数，其核心思想如下：选取一部分节点作为社会性节点，而剩下的节点作为普通节点。当需要进行辅助信息共享的时候，社会性节点负责和其他节点进行辅助信息的交换，而普通节点之间则不进行信息交换。使用该方法，辅助信息的交换将主要发生在特殊节点与普通节点之间。这样一来，理论上可以大量减少节点间辅助信息的获取次数。本文将这种节点间有条件地选择信息交换对象的方法称为辅助信息的选择性移交。

由文献[9]可知，PeopleRank算法可以通过计算机会网络中节点的社会性，并根据节点社会性的大小做出路由决策。该算法通过计算PeopleRank值来描述节点的社会性。通常具有较高社会性（People-Rank值）的节点与大部分节点具有较高的接触可能性。图1表示一个包含8个节点的小型机会网络。

图中节点u和v代表社会性节点（具有较高社会性的节点），而其他节点则代表普通节点，节点之间连接的虚线表示在某时间段内它们具有较高的接触可能性。从图中可以看出，节点u与节点a、b、c具有较高的接触可能性，而节点v则与节点d、e、f有较高的接触可能性。如果将节点u、v设为一个社会性节点集合，那么在该时间段内，该节点集合具有较大的几率接触到网络中所有的节点。

Fig.1 Example of selective handover图1 选择性移交图例

本文使用上述的社会性节点负责向其他节点进行辅助信息的交换工作，而普通节点之间不进行辅助信息交换而只和社会性节点进行信息交换。如图1所示，当社会性节点u与普通节点a、b、c接触时进行辅助信息的交换，节点v与节点d、e、f同上。当两个社会性节点u和v相遇时也进行信息交换。而两个普通节点（如a和b），即使接触也不进行信息交换。这样一来，可以在减少节点间信息交换次数的基础上，保证辅助信息的网络覆盖率较高。

4 应用

以下主要阐述的内容是如何将所提出的辅助信息获取机制集成到PRoPHET算法中。

4.1 PRoPHET算法简介

PRoPHET算法以节点之间的接触概率为辅助信息来为数据包选择合适的下一跳节点。PRoPHET计算节点之间接触概率主要包括三方面：平滑、衰退及传递。这里以3个节点a、b、c为例说明它们之间的信息交换过程。当a接触b时，其接触概率平滑为：

其中，P(a,b)old表示a和b上一次接触时计算的接触概率；Pinit为节点间接触概率的初值。

如果一段时间后两节点没有发生接触，则它们的接触概率衰退如下：

其中，γ为衰退因子；κ为上次接触后经历的时间段。

如果a和b有接触，同时b和c有接触，而a和c无接触，a也可以通过传递性（即a通过获取b中存储的b到c接触概率）来计算a和c的接触概率，公式如下：

其中，β为传递因子。

4.2 PRoPHET层次化辅助信息获取机制应用

由3.1节可知，PRoPHET算法的辅助信息交换主要发生在计算接触概率的传递性过程中，因此应用于PRoPHET算法的层次化辅助信息共享机制主要用来决定当两节点接触时是否进行接触概率的传递。其一般过程如下：

首先根据PeopleRank算法计算出机会网络中每个节点的社会性（PeopleRank值）。取固定值TH为区分节点社会性高低的阈值，PeopleRank值低于TH值的节点为普通节点，反之为社会性节点。本文对TH值的取值为：将所有节点按PeopleRank值从大到小排列，将TH值作为前10%的高社会性节点和剩下90%节点的PeopleRank值的分界值。接下来，对于任意节点a,b∈V，当a和b接触时，判断a或b是否属于社会性节点，或根据邻居关系发现算法判断是否a和b是邻居。如果满足上述任意条件，则计算接触概率的传递性。应用层次化辅助信息收集机制的PRoPHET如算法2所示。

算法2PRoPHET（选择性移交）

输入：机会网络节点集合V。

输出：辅助信息交换次数EAI。

1.HC←∅，EAI=0

2.for任意节点a∈Vdo

3.ifa的PeopleRank值＞THthen

4.HCi+1←HCi⋃a

5.end if

6.end for

7.for任意节点a∈Vdo

8. for任意节点b∈Vdo

9. ifa与b接触 then

10. 通过式（1）计算a与b的接触概率平滑性

11. if(a,b)∈NE⋃a∈HC⋃b∈HCthen

12.a获取b到其他节点的接触概率

13.a根据从b获取到的接触概率并通过式(3)计算接触概率的传递性

14.EAI++

15. end if

16. end if

17. end for

18.end for

19.returnEAI

算法2～6行将社会性节点加入集合HC中。算法7～10行进入二层循环，首先判断任意节点a是否与任意节点b接触，如果是则根据式（1）计算接触概率平滑性。算法11～14行判断a与b是否为邻居或者a或b是否为社会性节点，如果满足则a获取b对于其他节点的接触概率，然后根据式（3）计算接触概率的传递性，并记录一次辅助信息的获取次数。算法15～19行退出所有循环并返回辅助信息获取次数。

5 实验结果

本文对提出的辅助信息收集策略在Visual C++平台上进行了集成，并结合PRoPHET算法进行性能分析。实验场景如下：节点间最大通信距离为25 m，每隔30 s作为一个时间段，仿真时间为15 000 s。采用的数据集为RealTrace-KAIST，该数据集来源于韩国科学技术院（Korea Advanced Institute of Science and Technology，KAIST），其记录了大学校园内人群的日常活动行为轨迹。共有34人参与到数据的收集过程，每人手持GPS定位系统收集其92天的日常移动轨迹，关于该数据集的具体细节可以在文献[14]中查阅。本文使用4个指标来评价路由算法的性能：（1）投递率，网络中被成功接收的包的数量和产生的包的数量的比值，其代表了网络中包可以被成功投递到目的节点的比率。（2）包传输延时，网络中所有到达目的地的包从产生到传输至目的节点所需的时间的平均值。（3）平均备份数，平均投递一个包所需的备份个数，即所有的包产生的备份数与包的个数的比值。（4）辅助信息获取次数，网络中所有节点通过其他节点获取辅助信息的总次数。

下面对使用层次化辅助信息收集机制的PRo-PHET（信息收集机制）与未使用信息收集机制的PRo-PHET（洪泛）的各项指标性能实验结果进行详细分析。从图2中可以看出，在仿真时间第2 250 s到14 000 s时，信息收集机制略高于洪泛约0.03左右。而在14 000 s之后则略微低于洪泛约0.02左右。图3展示了包传输延时方面的性能对比情况。可以看出在仿真时间第2 250 s到第9 000 s期间，二者无明显差异。而在第9 000 s到15 000 s期间，信息收集机制的延时逐渐降低，二者最大差距约300 ms（＜7%）。在数据包投递备份数方面（图4）相比于洪泛，信息收集机制略高，但总体控制在4个数据包左右（＜4%）。

Fig.2 Comparison of packet delivery ratio图2 投递率指标对比

Fig.3 Comparison of packet transmission delay图3 包传输延时指标对比

对于辅助信息的获取次数，从图5中可以看出，从第2 250 s开始，信息收集机制就远远低于洪泛，并且随着时间的推移，信息收集机制的辅助信息获取次数的涨幅也远远低于洪泛，在仿真时间第15 000 s，洪泛的信息获取次数在76万次，而信息收集机制则仅有12万次左右，增益约7倍左右。其原因正如上文分析的那样，在信息收集机制中辅助信息只是由很少的一部分节点负责交换，而洪泛则是所有的节点都参与到交换工作，因此随着时间的推移，二者在辅助信息获取次数上的差距将会越来越明显。

Fig.4 Comparison of packet delivery copies图4 包投递备份数指标对比

Fig.5 Comparison of auxiliary-information acquisition times图5 辅助信息获取次数指标对比

6 结束语

本文针对信息辅助型机会路由算法的洪泛式信息共享方式所造成的网络资源浪费问题，提出了层次化的辅助信息获取机制。首先通过分析机会网络中节点间接触的规律性和稳定性提出了新的机会网络邻居关系发现算法。其次通过结合节点的社会性提出了辅助信息的选择性移交机制。最后将二者有机地集成在经典的信息辅助型机会路由算法PRo-PHET中，并通过实验验证了其有效性。未来将本文的信息获取机制应用到更多的机会路由算法中，以评估其通用性。

[1]Jindal A,Psounis K.Contention-aware analysis of routing schemes for mobile opportunistic networks[C]//Proceedings of the 1st International MobiSys Workshop on Mobile Opportunistic Networking,San Juan,Jun 11,2007.New York:ACM,2007:1-8.

[2]Ma Huadong,Yuan Peiyan,Zhao Dong.Research progress on routing problem in mobile opportunistic networks[J].Journal of Software,2015,26(3):600-616.

[3]Prodhan A T,Das R,Kabir H,et al.TTL based routing in opportunistic networks[J].Journal of Network and Computer Applications,2011,34(5):1660-1670.

[4]Xiao Mingjun,Wu Jie,Liu Cong,et al.TOUR:time-sensitive opportunistic utility-based routing in delay tolerant networks[C]//Proceedings of the 32nd IEEE International Conference on Computer Communications,Turin,Apr 14-19,2013.Piscataway:IEEE,2013:2085-2091.

[5]Lindgren A,Doria A,Schelén O.Probabilistic routing in intermittently connected networks[J].Mobile Computing and Communications Review,2003,7(3):19-20.

[6]Li Ze,Shen Haiying.Probabilistic routing with multi-copies in delay tolerant networks[C]//Proceedings of the 28th IEEE International Conference on Distributed Computing Systems Workshops,Beijing,Jun 17-20,2008.Washington:IEEE Computer Society,2008:471-476.

[7]Wang Xu,He Rongxi,Lin Bin,et al.Probabilistic routing based on two-hop information in delay/disruption tolerant networks[J].Journal of Electrical and Computer Engineering,2015,3:1-11.

[8]Hui Pan,Crowcroft J,Yoneki E.BUBBLE Rap:social-based forwarding in delay-tolerant networks[J].IEEE Transactions on Mobile Computing,2011,10(11):1576-1589.

[9]Mtibaa A,May M,Diot C,et al.PeopleRank:social opportunistic forwarding[C]//Proceedings of the 29th IEEE International Conference on Computer Communications,Joint Conference of the IEEE Computer and Communications Societies,San Diego,Mar 15-19,2010.Piscataway:IEEE,2010:111-115.

[10]Brin S,Page L.The anatomy of a large-scale hypertextual Web search engine[J].Computer Networks&ISDN Systems,1998,30(1/7):107-117.

[11]Daly E M,Haahr M.Social network analysis for routing in disconnected delay-tolerant MANETs[C]//Proceedings of the 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing,Montreal,Sep 9-14,2007.New York:ACM,2007:32-40.

[12]Gao Wei,Cao Guohong,Porta T L,et al.On exploiting transient social contact patterns for data forwarding in delaytolerant networks[J].IEEE Transactions on Mobile Computing,2013,12(1):151-165.

[13]Burgess J,Gallagher B,Jensen D,et al.MaxProp:routing for vehicle-based disruption-tolerant networks[C]//Proceedings of the 25th IEEE International Conference on Computer Communications,Barcelona,Apr 23-29,2006.Piscataway:IEEE,2006:1-11.

[14]Rhee I,Shin M,Hong S,et al.On the Levy-walk nature of human mobility[J].IEEE/ACM Transactions on Networking,2011,19(3):630-643.

附中文参考文献：

[2]马华东,袁培燕,赵东.移动机会网络路由问题研究进展[J].软件学报,2015,26(3):600-616.