基于社区与社会性的机会网络路由算法

李 豪，陈志刚，吴 嘉

（1．中南大学软件学院，长沙410075；2．“移动医疗”教育部－中国移动联合实验室，长沙410083）

1 概述

机会网络源于容忍延迟网络与移动自组网［1］。在机会网络中，网络规模没有进行事先设置，节点位置不固定，节点间不要求有确定的链路，依靠节点运动创造的通信条件逐跳地传输消息，采用“存储－携带－转发”的方式完成消息传输［2］。机会网络不要求存在贯穿始终的端到端连接，不依赖基础设施，可以满足恶劣条件下的网络通信需要，其典型应用包括野生动物研究、手持设备组网、车载网络、偏远地区网络覆盖等。

在机会网络特定应用环境中，由于终端携带者为社会成员，网络表现出社会特性，称这种网络为机会社会网络［3］。与一般的机会网络中节点迅速运动、网络拓扑结构快速改变不同，在机会社会网络中，人与人之间的社会关系比较稳定，并且表现出关联性。网络中关系密切的节点聚集在一起，进而产生社区。同一社区中节点间的交互次数较多，来自不同社区的节点间交互次数较少，有的节点比较活跃，与较多的节点接触，体现了较高的社会性［4］。

针对目前广泛分布的由人持有通信机器构成的机会社会网络，本文提出一种基于社区和社会性［5］的机会网络路由算法（Opportunistic Network routing algorithm based on Community and Sociality，ONCS）。该算法周期性地统计节点间的相遇频繁程度，把机会社会网络中的节点动态划分为多个社区，使用目标社区的节点充当中介节点，提高消息传输成功率；使用社会性高的节点充当中继节点，驱动消息的转发。

2 相关工作

在机会网络中，信息转发是指信息由源节点经过一跳或者多跳传输到目标节点的过程。如何有效地进行信息转发是目前机会网络研究的重要领域。

文献［6］提出了Spray and Wait（SW）算法，该算法分为2个过程：Spray和 Wait。在Spray过程中，源节点中每个数据分组向网络中注入固定数目L的数据分组副本，L是算法参数，可以设定。然后进入Wait过程，假如数据分组副本在上一过程未找到目标节点，则带有数据分组副本的L个节点采用直接传输的策略将数据分组副本传输到目标节点。

文献［7］提出的PRoPHET算法则基于概率策略，该算法定义了一系列公式预测消息成功传输的概率。当节点相遇时，节点重新计算彼此的预测成功传输概率，根据更新后的概率选择性地复制数据分组。实验结果表明，PRoPHET算法在社区场景中的性能较优。

文献［8］提出了一种基于社区的机会网络消息传输算法（Community－based Message Transmission Scheme，CMTS），该算法按节点间的相遇频率将网络划分为许多个社区，自适应地控制消息的副本数目，并通过活跃节点把消息转发到目标社区。算法严格控制消息拷贝数量与转发条件，在提高投递率的同时减小了路由开销。

文献［9］提出了机会网络中基于社区的转发算法Bubble Rap，根据节点间的交互次数记录得到节点的活跃度，体现节点作为潜在报文转发中继节点的概率。该算法将所有节点按照活跃度排序，得到2个排名：全局排名与社区排名。算法路由策略如下：节点把报文发送至全局排名比自己大的节点，直至把报文发送至目标社区节点。此节点再把报文发送至社区排名比自己大的节点，直至和目标节点相遇。该算法考虑活跃度高的节点与更多其他节点交互的特点，通过活跃度高的节点驱动报文转发，其采用一个副本的策略，投递率低，转发延迟高。

3 ONCS算法

3．1 社区的动态划分策略

由于人与人之间的社会关系，人类表现出聚集现象，整个社会被分割为许多个社区。同一社区的节点间比不同社区的节点间交流更加密切。社区内所有节点能够通过直接连接或间接连接到达。

同一社区中节点间的交互次数较多。来自不同社区的节点间的交互次数较少。所以，根据节点的相遇频率把网络划分成许多个社区。

定义1 数据分组平均传输时间t—，表示节点完整传输数据分组所需平均时间，等于数据分组平均大小除以数据传输速率。

定义2 稳定连接。每个节点记录和其他节点的相遇情况，若节点a与节点b连接时间t大于等于数据分组平均传输时间t—，则节点a与节点b稳定连接次数加1。

定义3 强连接。在指定的统计周期T内，若节点a与节点b稳定连接次数大于阈值λ，则认为节点a与节点b之间存在强连接。

在指定的统计周期T内，节点之间存在强连接，即节点之间稳定连接次数大于阈值λ，节点对之间才可以用边连接。本文使用8个节点图示说明社区划分算法，示例取稳定连接次数阈值λ为3。当节点稳定连接次数矩阵表示为式（1）时，社区划分结构表示如图1所示。在式（1）中，矩阵中第i行j列元素表示节点i与节点j之间的稳定连接次数，对角线上第i行i列元素值为∞，表示节点与自身不会存在稳定连接。在图1中，左边节点1～节点4划分为一个社区，右边节点5～节点8划分为一个社区。

图1 社区划分结果

社区结构在短周期中保持不变，经过一段时间，因为节点运动、节点动态加入或离开（比如节点能量耗尽），节点间的社会关系将发生改变，社区结构也将相应发生改变。所以，本文周期性地对节点对的稳定连接次数进行统计，相应地，周期性地划分网络社区结构。

考虑到社区内节点交互次数较多的特点，假如把消息发送至目标社区的其他节点，则它和目标节点相遇的概率很大，使消息传输到目标节点的概率增大。如果源节点与目标节点处于同一社区，由社区内其他节点中继转发消息，则消息就能高效地传输到达。把消息限制在社区内转发，不需要传输到社区外相遇不频繁的节点。同样地，在社区间进行消息传输时，使用社会性高的节点充当中继节点，通过它们把消息发送至目标社区，进而完成消息的高效转发。

3．2 节点社会性度量

在机会社会网络中，节点的社会性表现为节点的通信能力和中继能力。文献［10］提出选择介数中心性与相似性作为社会性度量的2个考虑因素。介数中心性是节点连接其他节点路径能力的度量，它测量节点落在2个其他节点的最短路径上的次数，能够体现节点作为消息转发中继节点的重要性。相似性度量节点和目标节点的共同邻居数，体现节点和目标节点相遇的概率。节点的社会性由介数中心性和相似性构成。

节点N的介数中心性表示为BetN，节点N所遇到的节点之间的连接能够用一个K×K的对称矩阵A来表示，其中，K代表节点N遇到的节点数目。假如矩阵行与列所表示的节点之间存在连接，那么矩阵A中元素Aij的值为1，否则为0。BetN值的计算公式为：

对式（2）计算进行图示说明。当网络连接如图2所示时，节点 w8的对称矩阵A 如式（3）所示，A2［1－A］计算结果如式（4）所示，其中，A与A 进行矩阵相乘，得到的矩阵再与［1－A］得到的矩阵进行点乘（矩阵对应的元素相乘），得到结果矩阵。

图2 网络连接图

由于A2［1－A］是对称的，因此只需要考虑对角线上的非零元素。A2［1－A］对角线上剩余的非零元素为3，倒数为0．33，即节点w8的介数中心性为0．33。

节点N与目标节点D的相似性表示为：

其中，NN与ND分别表示节点N与节点D遇到的节点的集合。

本文假定节点N需要将消息传输给目标节点D。当节点N遇到M时，节点N相对于节点M的介数中心性效用和相似性效用的计算公式如下：

节点N把消息传输给目标节点D，社会性的整体效用计算如下：

其中，α与β是可变参数，分别表示介数中心性效用与相似性效用在社会性计算中的权重，α＋β＝1。

通过以上公式可以计算节点N到目标节点D的社会性效用。当节点在社区中移动时，选择社会性效用大于自己的节点充当消息转发的中继节点。

3．3 算法设计

本文算法的设计思路如下：

郑君之死，是我从有关他的讣告上得知的。本来，死亡的原因是讣告的一个要件，然那个讣告没有他死亡的原因。后来，我得知他是死于其逆子的刀下。

（1）人们在社会中有不同的受欢迎程度，机会社会网络中的节点也一样，转发策略的第1部分是将消息转发给比当前节点更受欢迎（社会性更高）的节点。

（2）人们在社会生活中形成社区，机会社会网络中的节点也一样，转发策略的第2部分是动态划分社区，将消息往目标节点社区转发。

对于本文算法，做出如下假定：（1）节点属于一个或多个社区；（2）节点有一个到达目标节点的社会性效用。

转发的具体实现步骤如下：在社区外，节点首先按照社会性排行，将消息转发给社会性更高的节点，直至和目标社区节点相遇，将消息转发给目标社区节点；然后在社区内使用社会性排行，将消息发送至社会性更高的节点，直至遇到目标节点。节点不需要了解系统中所有其他节点的排名，只要求和相遇节点的排名进行比较，使用贪心策略转发消息。为了降低路由开销，本文规定，当消息由社区外传入社区内时，之前的消息携带者将消息从缓存中删除，阻止继续在社区外转发。

对于每个相遇节点，满足以下4种情况则进行消息转发：

（1）如果相遇节点为目标节点，目标节点复制消息，当前节点删除消息。全局广播消息成功到达确认消息，在网络中删除指定源节点和目标节点的消息，结束消息转发。

（2）如果当前节点和目标节点社区相同，并且相遇节点和目标节点社区相同并且相遇节点社会性大于当前节点，相遇节点复制消息。

（3）如果当前节点和目标节点社区不同，并且相遇节点和目标节点社区相同，相遇节点复制消息，当前节点删除消息。

（4）如果当前节点和目标节点社区不同，并且相遇节点社会性大于当前节点，相遇节点复制消息。

消息由社区外传入社区内时，中继节点复制消息，当前节点删除消息，把消息限制在社区内转发，减小路由开销。

算法伪代码如下：

算法 基于社区和社会性的机会网络路由算法ONCS

其中，ETNode表示相遇节点；CNode表示当前节点；DNode表示目标节点；Community（Node）表示节点的社区；SimBetUtil（Node）表示节点的社会性。

由ONCS算法可知，在由人携带的移动设备组成的机会社会网络场景中，当社区结构划分合理时，消息进入目标社区后，将消息限制在目标社区内转发，效率相对未考虑节点社区性质的算法将有很大提升。当节点社会性梯度明显时，消息不停由社会性低的节点发送至社会性高的节点，最终转发到目标节点，效率相对没有考虑社会性的算法将有很大提升。但该算法可能存在不足：当节点与其他节点稳定连接次数都较少时，节点自身将成为离群点，形成孤立社区，路由算法效率会有所降低。

4 仿真实验与结果分析

4．1 仿真场景及算法参数

本文 使 用 ONE（Opportunistic Network Environ－ment）［11］仿真环境模拟持有智能蓝牙设备的行人于真实城市步行的场景，实现算法ONCS，并与Spray and Wait和PRoPHET算法进行性能比较。选用传输成功率、传输延迟、路由开销3个性能指标［12］对算法进行分析。仿真场景设置如表1所示，算法参数设置如表2所示。

表1 仿真场景设置

表2 算法参数设置

通过实验表明，当λ＝3，α＝0．5，β＝0．5时，ONCS算法性能综合最优。

4．2 实验结果分析

4．2．1 社区划分周期对消息传输成功率的影响

社区划分周期对消息传输成功率的影响如图3所示（本文算法结果），该图表明，当选取较小的社区划分周期时，由于社区结构仍不稳定，造成社区划分对路由算法指导效果不佳，传输成功率较低。随着划分周期增大，传输成功率相应提高。周期选取为900 s时，算法取得最高的传输成功率82%。随着划分周期继续增大，传输成功率下降。周期选取为2 700 s时，传输成功率是62%，算法性能比周期选取为900 s时的算法性能差。由于社区划分周期过大，节点间的社会关系发生变化，之前的社区划分结果不能很好地表示最新的社区结构。

图3 社区划分周期对消息传输成功率的影响

4．2．2 节点缓存对路由算法的影响

Spray and Wait算法、PRoPHET算法和ONCS算法在不同节点缓存大小下的消息传输成功率如图4所示。该图表明，节点缓存较小时传输成功率都较低，这是因为节点缓存有限，丢弃消息。从趋势上看，增大节点缓存，传输成功率相应提高。ONCS算法利用网络中的强连接把网络划分成许多个社区，通过社会性高的节点驱动消息转发，将消息逐渐向更接近目标节点的中继节点转发，与目标社区节点相遇后将消息限制在目标社区内转发，相对于Spray and Wait算法被动等待与目标节点相遇、PRoPHET算法利用传输概率选择性地复制数据分组策略更优，传输成功率也高于上述2种算法。

图4 节点缓存对消息传输成功率的影响

节点缓存对消息传输延迟的影响如图5所示。该图表明，随着节点缓存增大，各算法传输延迟增大。PRoPHET算法基于简单概率策略，节点与目标节点遇到的可能性相对较小，传输延迟最大；ONCS算法利用社会性高的节点转发消息，即同时考虑节点的介数中心性和与目标节点的相似性，将消息逐渐向更接近目标节点的中继节点转发，与目标社区节点相遇后将消息限制在目标社区内转发，限制消息的传输范围，进而减少消息的传输延迟，传输延迟最小；Spray and Wait算法复制完消息后通过Direct Delivery的方式将消息传输到目标节点，等待与目标节点相遇，传输延迟也较大。

图5 节点缓存对消息传输延迟的影响

节点缓存对路由开销的影响如图6所示。该图表明，ONCS算法和PRoPHET算法随着节点缓存的增加路由开销会显著减少。SW算法受节点缓存影响不大。Spray and Wait算法在Spray阶段复制消息，在 Wait阶段通过Direct Delivery的方式，遇到目标节点才转发消息，路由开销稳定，在3种算法中也最小。PRoPHET算法简单地利用概率策略转发消息，路由开销最大。ONCS算法把消息选择性地发送至目标社区节点或社会性更高的节点，利用具有社会特性的转发策略有效降低路由开销，路由开销适中，在路由开销指标可接受的情况下能有效提高消息传输成功率，降低传输延迟。

图6 节点缓存对路由开销的影响

5 结束语

本文提出一种基于社区和社会性的机会网络路由算法（ONCS）。按照节点间的稳定连接次数选取节点间的强连接，将网络动态划分成多个社区，根据介数中心性和相似性定义社会性，选取社会性高的节点作为中继节点，带动消息转发，将消息逐渐向与目标节点相同社区的节点或社会性高的节点转发，最后传输到目标节点。

仿真结果表明，ONCS算法通过选择性复制消息，在路由开销指标适中的情况下，具有较高的传输成功率和较低的传输延迟，适用于由人持有移动设备构成的机会社会网络场景。下一步将继续优化社区动态划分策略，使ONCS算法适用于实际场景。

［1］熊永平，孙利民，牛建伟，等．机会网络［J］．软件学报，2009，20（1）：124－137．

［2］刘亚翃，高 媛，乔晋龙，等．机会社会网络中基于社区的消息传输算法［J］．计算机应用，2013，33（5）：1212－1216．

［3］Pietilänen A K，Diot C．Dissemination in Opportunistic Social Networks：The Role of Temporal Communities［C］／／Proceedings of the 13th ACM International Symposium on Mobile Ad Hoc Networking and Computing．New York，USA：ACM Press，2012：165－174．

［4］蔡青松，牛建伟，刘 畅．一种机会网络中的消息发布／订阅算法［J］．计算机工程，2011，37（12）：19－22，25．

［5］Nguyen H A，Giordano S．Context Information Prediction for Social－based Routing in Opportunistic Networks［J］．Ad Hoc Networks，2012，10（8）：1557－1569．

［6］Spyropoulos T，Psounis K，Raghavendra C S．Spray and Wait：An Efficient Routing Scheme for Intermittently Connected Mobile Networks ［C］／／Proceedings of ACM SIGCOMM Workshop on Delaytolerant Networking．New York，USA：ACM Press，2005：252－259．

［7］Lindgren A，Doria A，Schelén O．Probabilistic Routing in Intermittently Connected Networks ［J］． ACM SIGMOBILE：Mobile Computing and Communications Review，2003，7（3）：19－20．

［8］牛建伟，周 兴，刘 燕，等．一种基于社区机会网络的消息传输算法［J］．计算机研究与发展，2009，46（12）：2068－2075．

［9］Hui P，Crowcroft J，Yoneki E．BUBBLE Rap：Socialbased Forwarding in Delay－tolerant Networks［J］．IEEE Transactions on Mobile Computing，2011，10（11）：1576－1589．

［10］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．New York，USA：ACM Press，2007：32－40．

［11］王 朕，王新华，隋敬麒．机会网络模拟器ONE及其扩展研究［J］．计算机应用研究，2012，29（1）：272－277．

［12］孙践知，刘乃瑞，张迎新，等．机会网络典型路由算法性能分析［J］．计算机工程，2011，37（16）：86－89．