摘 要： 针对机会网络主流路由协议没有考虑到节点的社区特性，提出了一种基于社区的冗余效用混合转发机制。该算法从合理降低洪泛度和准确预测效用值方面出发，通过消息筛选、消息优先级和活跃节点机制对消息进行有效处理和转发。与经典的Epidemic和Prophet算法相比，该算法具有消息传达率较高、传输延时小和网络开销低的特点。

关键词： 机会网络；社区；冗余效用

0 引言

　　机会网络是一种不需要源节点和目标节点之间存在完整链路，利用节点移动带来的相遇机会实现通信的自组织网络，其主要应用集中在野生动物追踪、车载网络、偏远地区网络传输等场合[1]。随着大量智能手机等手持设备的出现，以人为载体的移动节点的数据交换频繁，逐渐出现以人为主体的机会网络。由于人们之间社会关系相对稳定且存在一定的依赖性，网络中会出现节点的聚集现象，从而形成不同的社区。社区内的节点移动缓慢，相遇概率高，不同社区内的节点相遇概率低，往往需要通过一些活跃节点来增加社区之间的联系，与以节点移动快速、网络拓扑变化频繁的普通机会网络相比有明显的区别[2]。

1 相关工作

　　2006年，MUSOLESI M等人提出了基于人类社会关系的移动自组织网络移动模型，引起了人们的广泛关注[3]。2007年，Pan Hui等人提出为每个消息包贴上社区标签，转发时只需进行简单的标签号比较就能判断是否允许发送，进而提高了消息的投递成功率[4]。2009年，牛建伟根据节点之间的通信频繁程度，自动将节点划分成不同的社区，自适应地控制消息的拷贝数量并依靠活跃节点将消息传输到目标社区[2]。2013年，刘亚翃等人根据节点间的社会关系强度，动态自适应地将节点划分为不同的社区，通过限制消息副本数来减少网络中消息的冗余，并利用活跃性高的节点带动消息的转发[5]。2014年，周军海等人提出一种基于社区的低功耗消息路由算法，能自适应地控制消息拷贝数量并能自动调整节点的活跃度，依靠活跃度较高的节点来完成消息传输[6]。针对社区机会网络的特点，本文提出一种基于社区的冗余效用混合转发机制，该算法根据现实社会节点的移动特性在传染路由的基础上对消息路由做改进，对社区内消息包进行优先级分类和消息筛选，通过活跃节点进行社区间消息传递，具有传达率高、网络资源消耗低、传输延时小的特点。

2 基于社区的冗余效用混合路由算法

　　机会网络路由技术从不同的角度可分为不同的种类。根据路由策略来分，可以分为基于复制的路由和基于效用的路由[7]。基于复制的路由通过洪泛的方式进行转发，但资源占用率高。基于效用的路由能有效减少过多的消息复制，但传达率较低，延时较大。由于社区内节点相对聚集，不同社区之间节点联系较少，普通机会网络路由算法在社区网络内效率不高。综合以上两种算法优点的冗余效用混合路由在降低资源消耗的前提下有利于消息转发率的提高，在社区机会网络的消息转发机制中使用尤为合适。算法主要包括消息筛选、优先级和活跃节点3种机制。

2.1 消息筛选机制

　　当社区中节点携带有以本社区内其他节点为目的节点的消息包时，一方面，由于有社区归属的节点很大概率是在本社区内部活动，且社区内节点间相遇频繁，消息包可以通过本社区的中继节点经过多跳很快传达到目的节点；另一方面，外部社区的节点到本社区活动的概率很低，假如把上述消息转发给外部社区节点，消息很有可能只会在外部社区扩散，很难回传到本社区，不仅不能提高传达率，反而盲目地增加了网络中消息的副本数，增加网络资源的消耗。因此，本社区内的消息没有必要扩散至其他社区。算法中加入消息筛选机制，当该机制检测到相遇节点归属于不同社区且自身节点存储有以同一社区内节点为目的节点的消息包时，把该类消息包从转发队列中过滤掉。

2.2 消息优先级机制

　　由于节点移动的不确定性，节点间从建立连接到断开，中间的持续时间可能只是一瞬间。考虑到网络连通时间的不确定性，为了让消息的转发更具有效用性，可以提前判断消息的效用值，按效用值由高到低顺序转发。算法加入了消息优先级机制，优先级高的一类消息包优先转发，同类的按顺序转发。优先级分类如下：

　　（1）第一优先级。转发节点的消息缓冲区中可能存储有以对方节点为目的节点的消息包，这类消息包只需要再经过一跳就能传达到目的节点。

　　（2）第二优先级。在消息筛选机制中已分析到社区内部的消息包在本社区中继节点的协助下可以经过多跳以较快的速度传达，在本社区消息不外传的前提下，该类消息的副本仅仅在本社区内扩散，实现以较低的消息副本数获得较小的传达延时，因而该类效用值较高的消息以第二优先级被转发。

　　（3）第三优先级。转发节点的消息缓冲区可能存储有对方节点社区内的消息包，由于对方节点与消息目的节点归属社区相同，那么两节点很大概率在本社区内活动，通过直接相遇或者本社区其他中继节点转发，消息可以较快传达。

　　2.3 活跃节点机制

　　在现实社会，有一些人经常穿梭于各大社区之间，比如快递员、送餐员和上下班的职员等。社区间的消息可以利用这些活跃的人群进行传送。这种机制让网络中的活跃节点承担社区间的副本扩散任务。其优点有两方面：一方面，控制了网络中消息的洪泛程度，避免了副本盲目、过度地增加；另一方面，减少不必要的传输，使网络资源的利用更加充分有效。

　2.4 转发策略

　　开始时，消息发送方遇到对方节点，双方建立连接。逐个遍历缓冲区的消息，如果满足来自不同社区且为社区内的消息则被筛选机制过滤掉不加入发送队列，否则依次经过优先级一、二、三以及活跃节点机制进行判断，符合条件则加入对应队列，都不符合则放弃转发。直到完成遍历，把消息依次按队列一、二、三和普通发送队列给接收方，最后结束本次任务。具体流程如图1所示。

3 仿真实验和结果分析

　　3.1 模拟环境设置

　　本文采用ONE模拟器为仿真平台实现算法，采用Epidemic和Prophet算法在本文设计的江门市蓬江区运动场景中进行对比测试。

　　3.1.1 地图场景

　　现实生活中，人们的移动性强，社会关系复杂，移动特性各异。为真实还原机会网络的社区特性，以江门市蓬江区16个主要社区作为仿真场景，实现了对真实世界移动模型的模拟，采用OpenJUMP软件绘制地图，如图2所示。

　　3.1.2 线路规划

　　人类社会中不同移动节点具有不同的偏好位置和有效活动范围，本文设计了机动车线路、公交线路和社区线路，控制各类节点的运动。机动车线路限制了汽车节点的有效活动范围，公交线路上不定距离设有站点。

　　3.1.3 节点规划

　　网络中有人、汽车等可以携带无线通信设备的移动节点，根据节点的不同移动特性设有5类节点，具体如下：

　　（1）普通行人节点：只参与消息包的转发和接收，但不加入任何社区。

　　（2）有社区归属行人节点：大部分在本社区内活动。

　　（3）普通汽车节点：在机动车线路上活动，速度快，活动性强。

　　（4）公交汽车节点：在公交线路上移动，缓存大，线路固定，尽可能不调头。

　　（5）动态社区归属节点：在仿真范围内随机活动，当进入某一社区就加入该社区，离开则退出该社区，用以模拟社区内部节点构成的动态变化。

　　活跃节点来自上述部分节点，其中包括有社区归属且经常活动于其他社区的节点、汽车节点、公交节点和动态社区归属行人节点。

　　3.1.4 仿真参数

　　根据以上的规划，本文采用的仿真主要参数如表1所示。

　3.2 缓存对网络性能的影响

　　与路由算法Epidemic和Prophet相比，基于社区的冗余效用混合算法（用Community表示）在缓存大小不同的情况下，对消息传达率、平均延时和路由开销比率3种性能指标下影响分析如下。

　　3.2.1 消息传递成功率

　　当缓存较小时，网络中由于消息副本量大而不能满足消息的缓存要求，旧的消息包会较快被新接收的挤掉，造成大量包被丢弃，因而3种路由算法传达率都不高。随着缓存容量的增大，传达率都有不同程度的上升。Epidemic以高传输延时为代价，因而传达率比Prophet高。本文算法对消息副本洪泛程度控制有效，转发效率较高，因此传达率较高。具体如图3所示。

　　3.2.2 消息传递平均延时

　　对于消息传递平均延时，Epidemic明显高于其他两种算法，由于向网络中洪泛消息副本，有限的网络资源会使消息包被大量丢弃，很难找到较短传输路径把消息传到目的节点，传输延时大。Prophet和本文算法都提前对消息转发效用值做预测，更容易找到较短路径，延时较低。具体如图4所示。

　　3.2.3 路由开销比率

　　从总体上看，随着缓存的增大，网络中节点的丢包量减小，更多的消息被成功传输，开销越来越低。本文算法明显低于Epidemic和Prophet，这是因为：一方面，洪泛程度低，网络中消息副本较少；另一方面，消息转发效用高，传达率高，因此开销低。Prophet也对消息洪泛做了控制，但由于传达率低，在开销上与Epidemic相比并没有明显优势。具体如图5所示。

4 结论

　　本文提出了一种基于社区的冗余效用混合传输机制，目标是解决普通机会网络路由算法在社区网络中性能不高的问题。本文首先分析了目前社区机会网络的研究现状，针对基于复制的路由和基于效用的路由存在的问题，提出将冗余效用混合算法应用于基于社区的机会网络中。以江门市蓬江区为主要场景进行了模拟，并与Epidemic和Prophet算法进行了比较。实验结果表明，冗余效用混合转发机制在消息投递成功率、传递平均延时和路由开销比上均有明显改善。

参考文献

　　[1] 熊永平，孙利民，牛建伟.机会网络[J].软件学报，2009，20（1）：124-137.

　　[2] 牛建伟，周兴，刘燕.一种基于社区机会网络的消息传输算法[J].计算机研究与发展，2009，46（12）：2068-2075.

　　[3] MUSOLESI M， MASCOLO C. A community based mobility model for ad hoc network research[C]. Proceedings of the 2nd International Workshop on Multi-hop ad Hoc Networks： from Theory to Reality， New York： ACM， 2006： 31-38.

　　[4] Pan Hui， CROWCROFT J． How small labels create big improvements[C]. Fifth Annual IEEE International Conference on Pervasive Computing and Communications Workshops，New York，2007：65-70.

　　[5] 刘亚翃，高媛，乔晋龙.机会社会网络中基于社区的消息传输算法[J].计算机应用，2013，33（5）：1212-1216.

　　[6] 周军海，林亚平，周四望.一种低功耗的社区机会网络消息路由算法[J].计算机科学，2014，41（1）：178-182.

　　[7] 徐佳，王汝传，徐杰.基于效用的容迟网络路由技术研究[J].计算机应用研究，2011，28（4）：1211-1215.