机会社会网络中一种基于社区的高效路由算法

任 智，黄希凯，谭永银

（重庆邮电大学移动通信技术重庆市重点实验室，重庆 400065）

机会社会网络中一种基于社区的高效路由算法

任 智，黄希凯，谭永银

（重庆邮电大学移动通信技术重庆市重点实验室，重庆 400065）

针对机会社会网络中RADR（机会社会网络消息传送算法）存在消息传输时延偏大和消息传输成功率偏低的问题，提出一种ECRA（基于社区的高效的机会社会网络路由算法）。ECRA只选取与消息目的节点在同一个社区的邻居节点来计算重要度，并且利用连通拓扑侦听相遇节点，检测相遇节点的邻居节点中是否存在更高重要度的节点，若存在，则利用相遇节点将消息传递给具有更高重要度的邻居节点。理论分析和仿真结果表明，ECRA与RADR及相关对比算法比较，在消息传输成功率、平均端到端时延等方面的性能均得到了提升。

机会社会网络；路由算法；社区；重要度；侦听机制

0 引 言

机会网络是一种特殊的移动自组织网络，它能够在网络链路处于间歇性连接的状态下，提供端到端的通信服务［1］。随着移动终端设备的高速发展，利用移动设备进行消息传输也越来越普遍，将社会关系引用到机会网络当中，能更好地优化机会网络的消息传输机制［2］。

目前，研究人员已提出一些有效的机会社会网络路由算法：SGBR（基于社会群组的路由算法）［3］利用节点间相遇的频繁程度计算出连通度值，通过设定连通度阈值划分社区，向与目的节点连通度值大的节点转发消息，该算法的缺点是无序发送消息时可能导致生存期剩余时间小的消息到期被删除，降低了传输成功率。CHMTS（社区分层消息传输）算法［4］利用EO（外部优化）算法划分社区，并使用改进的Prophet算法进行消息传输，该算法的缺点是消息转发时没有考虑整个传输链路的高效性。文献［5］提出了一种RADR（机会社会网络消息传输算法），该算法使用k-Clique算法［6］进行社区检测，在消息传输阶段根据节点重要度进行路由选择，但是该算法存在节点重要度计算不准确以及路由选择单一的问题。针对RADR出现的问题，本文提出一种ECRA（基于社区的高效的机会社会网络路由算法）。

1 社区划分与问题描述

1.1社区划分

ECRA采用k-Clique算法进行社区划分，k-Clique算法中熟悉集Fi为节点vi的相遇节点中持续相遇时间超过阈值的节点集合，vj是vi熟悉集内的节点，不完全熟悉集为FCj，即vi得到的vj的熟悉集。Co为局部社区。当节点vo与节点vi相遇，算法执行步骤如下：

步骤1：节点初始化，Co=｛vo｝，Fo=Ø，FCj=Ø。

步骤2：当节点vo与节点vi相遇时，交换彼此局部社区Ci、熟悉集Fi和不完全熟悉集FCj的信息。步骤3：若vi不在vo的熟悉集Fo中，则vo更新与节点vi的持续时间，然后执行步骤4；如果持续时间超过阈值，则将vi加入vo的熟悉集Fo和局部社区Cv中。

步骤4：若熟悉集Fi至少包括Co中的k-1个节点，则也将节点vi加入到Co中。

步骤5：若vi已是Co中节点，且vi熟悉集中的节点vj满足|FCj∩Co|≥k-1，则将vj加入到Co中。

1.2问题描述

RADR存在以下问题：

（1）原算法考虑节点的重要度是为了将消息尽快转发到目的节点所在社区，而在计算节点重要度时，将节点的所有邻居节点的社会强度加权计算进去，没有考虑邻居节点中存在非消息目的节点所在社区的节点，会对节点重要度的计算造成干扰，影响传输效率。

（2）原算法认为节点重要度高的节点遇见目的节点的概率更高，并且将消息转发到目的节点社区的概率更高，没有考虑到利用连通拓扑结构侦听机制来转发消息，降低了传输成功率和消息转发效率，并增加了传输时延。

2 ECRA

本文提出的ECRA旨在解决RADR存在的两个问题，新算法中为节点重要度计算和消息转发设计了两种新机制，从而达到降低消息传输时延、提高传输成功率和转发效率的目的。

2.1社会权重和重要度计算

RADR使用社会权重和重要度来衡量节点的社会性。

（1）社会权重的计算

在第i个时间片段ΔTi内，节点x与节点y有n次接触，第k次接触为CD（x，y）k，则在这个时间片段内的接触时间TCT（x，y）i的计算公式为

在第j天的第i个时间片段ΔTi，节点x与y的平均累积接触持续时间为AD（x，y）ji，计算公式为

节点x与节点y的社会权重由下式计算得到：

式中，t为一天划分的时间片段数。

（2）节点重要度的计算

节点的重要度与节点的社会权重有关，其计算公式为

式中，N（x）为节点x的所有邻居节点集合，d为随机因子。

2.2ECRA包含的新机制

2.2.1节点重要度的计算更新

由2.1节可知，RADR计算节点的重要度时，N（x）是节点x的所有邻居节点集合，如图1所示，图中Ui表示节点所在社区。式（4）将节点A的所有邻居节点的社会权重加权代入公式计算，这样计算出来的结果不能准确地反应出是节点到目标社区的重要度大，因为节点到其他社区的加权可能会导致总的节点重要度大。因此，为了准确衡量节点到目的节点社区的重要度，ECRA在运用式（4）计算时，N（x）只包含与目的节点同一个社区的节点，这样更能体现到达目的节点社区的概率，消息能更快地传递到目的节点所在社区。

图1　节点重要度计算示意图

2.2.2利用连通拓扑图侦听相遇节点

ECRA利用连通拓扑的有利条件提出了节点侦听的思路，利用中间节点将消息转发给重要度更高的节点，可以提高传输可靠性和传输效率，降低端到端时延。图2所示为通信重叠区域内消息传输示意图。由图可知，消息携带节点S向其周围的节点广播Hello消息，确定通信范围内周围的邻居节点。邻居关系确定后，节点S利用MAC（媒体访问控制）层侦听它的邻居节点B发出的装载数据和控制信息的消息，判断消息类型并提取头部的MAC地址。获得帧中MAC地址后，MAC层通过跨层信息共享的方式将其送往网络层；网络层收到该MAC地址后做一次反向ARP（地址解析协议）处理，获知邻居节点与哪些节点进行通信。如果节点S的网络层发现节点A是B的邻居，即使B的重要度相对更低，也将消息m发送给B，以便使消息通过B传递到A，利用节点A让消息尽快到达与目的节点相遇概率更高的节点，从而提高传输成功率。

图2　通信重叠区域内消息传输示意图

2.3算法操作步骤

根据相遇节点与消息目的节点是否同属于一个社区，ECRA分为两种传输方式：

（1）相遇节点与消息目的节点同属于一个社区

步骤1：节点i、j在网络中移动，携带消息m的节点i与节点j相遇，节点i判断节点j是否是消息m的目的节点；

步骤2：如果邻居节点j是消息的目的节点，则i直接将消息m发送给目的节点j，完成消息传递，否则进行下一步；

步骤3：节点i和j相互交换双方的存储矢量表，若节点j中存在消息m，则双方不做操作，继续移动，否则转向下一步；

步骤4：节点i与节点j交换双方的社会信息表，如果节点j到消息m的目的节点D的社会权重大于节点i到节点D的社会权重，则节点i将消息m拷贝一份，传递给节点j，否则转向下一步；

步骤5：如果节点j到目的节点D的社会权重小于节点i到节点D的社会权重，则由当前节点i继续携带消息在网络中移动。

（2）相遇节点与消息目的节点不属于同一个社区

步骤1：节点i、j在网络中移动，携带消息m的节点i与节点j相遇，节点i判断节点j是否是消息m的目的节点；

步骤2：如果邻居节点j是消息的目的节点，则i直接将消息m发送给目的节点j，完成消息传递，否则转向下一步；

步骤3：节点i和j相互交换双方的存储矢量表，若节点j中存在消息m，则双方不做操作，继续移动，否则转向下一步；

步骤4：节点i与节点j交换双方的社会信息表，如果节点j到消息m的目的节点D的重要度大于节点i到节点D的重要度，则节点i将消息m拷贝一份，传递给节点j；否则转向下一步；

步骤5：利用连通拓扑图跨层侦听辅助传输机制，节点i侦听相遇节点j的邻居节点信息，判断节点j的邻居中有没有重要度大于节点i的邻居节点，若有，则将消息m拷贝一份，转发给节点j，否则转向下一步；

步骤6：当前节点i继续携带消息在网络中移动。

3 ECRA仿真实验及分析

本文使用ONE［7］作为仿真平台，仿真场景参数设定如表1所示。

表1　仿真场景参数设定

本节通过改变节点缓存的大小，分析比较ECRA、RADR和CHMTS算法在消息传输成功率、平均端到端时延、转发效率和消息平均存储时间4个方面的性能。

（1）消息传输成功率

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

图3所示为节点缓存对消息传输成功率的影响。由图可知，当节点缓存不断变大时，消息成功传输的概率均有所提高。ECRA消息成功传输的概率要优于另外两种算法，这是因为ECRA利用有效连通拓扑侦听邻居节点，将消息转发给更有利于数据包到达目的节点的节点，使转发更具有效性，同时在计算节点重要度时，只计算与目的节点同一个社区的邻居节点，使节点重要度的计算更准确，更有利于消息的传递，从而有效地提高了算法的消息传输成功率。

（2）平均端到端时延

图4所示为节点缓存对平均端到端时延的影响。由图可知，随着节点缓存不断增加，3种算法的平均端到端时延也在变大，而ECRA的平均端到端时延要优于其他两种算法。这是因为ECRA通过侦听判断通信范围重叠区域内节点发送的矢量信息，获知被侦听节点中是否存在节点重要度更高的邻居节点，若有，则将消息发送给被侦听的节点，由该节点将消息转发给其节点重要度更高的邻居节点，使消息更快地到达与目的节点相遇概率更高的节点，从而降低了消息传输所消耗的时间，相比其他两种算法表现出了更低的时延特性。

图4　节点缓存对平均端到端时延的影响

（3）消息转发效率

图5所示为节点缓存对消息转发效率的影响。由图可知，ECRA的消息转发效率优于其他两种算法，这是因为ECRA改进了节点重要度的计算，避免了将消息转发给其他不必要的节点，降低了消息副本数，使消息转发更加有效，改善了网络的拥塞情况，进而提高了转发效率。而其他两种算法在限制消息副本数和减少不必要消息转发上均存在不足，所以在消息转发效率这个性能指标上要低于ECRA。

图5　节点缓存对消息转发效率的影响

（4）消息平均存储时间

图6所示为节点缓存对消息平均存储时间的影响。由图可知，ECRA的消息平均存储时间在3种算法中是最小的，这是因为ECRA对RADR做了改进，在消息传递时充分利用到目的节点重要度较高的节点转发消息，在相对短的时间内把消息投递给了目的节点，缩短了消息的存储时间。

图6　节点缓存对消息平均存储时间的影响

4 结束语

本文针对RADR存在的问题，提出了一种ECRA，该算法提出连通拓扑图节点侦听机制，并改进节点重要度计算公式。仿真结果表明，ECRA较RADR及其他对比算法表现出了更好的消息传输成功率、转发效率和更低的传输时延、平均存储时间。

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

［2]Wu J，Wang Y.Opportunistic Mobile Social Networks ［M］.Boca Raton：CRC Press，2014：256-266.

［3]Abdelkader T，Naik K，Nayak A，et al.SGBR：A Routing Protocol for Delay Tolerant Networks Using Social Grouping［J］.IEEE Transactions on Parallel and Distributed Systems，2013，24（12）：2472-2481.

［4]Wang L，Geng X.A community-driven hierarchical message transmission scheme in opportunistic networks［J］.Smart Computing Review，2011，1（1）：85-94.

［5]Moreira W，Mendes P，Sargento S.Opportunistic Routing Based on Daily Routines［C］//Proc of the IEEE International Symposium on Wireless，Mobile and Multimedia Networks 2012.San Francisco，US：IEEE，2012：1-6.

［6]Hui P，Yoneki E，Chan S Y，et al.Distributed Community Detection in Delay Tolerant Networks［C］// Proc of ACM/IEEE international workshop on Mobility in the evolving internet architecture 2007.New York，US：ACM Press，2007：716-722.

［7]Keranen A，Ott J，Karkkainen T.The ONE simulator for DTN protocol evaluation［C］//Proc of the International Conference on Simulation Tools and Techniques 2009.Brussels，Belgium：IEEE，2009：55-59.

An Efficient Community-based Routing Algorithm in Opportunistic Social Networks

REN Zhi，HUANG Xi-kai，TAN Yong-yin
（Chongqing Key Laboratory of Mobile Communication Technology，Chongqing University of Posts and Telecommunications，Chongqing 400065，China）

To solve the problems of high transmission delay and low forwarding efficiency in the Routing Algorithm based on Daily Routines（RADR）in opportunistic social networks，an Efficient Community-based Routing Algorithm is proposed （ECRA）.The algorithm only selects the neighbor nodes which are in the same community with message destination node to calculate the node’s important degree.The algorithm uses topological connections to intercept the encounter node.If there exists node which has higher node’s importance than the encounter nodes neighbor，the message is transmitted to the encounter node neighbor nodes by the encounter node.Theoretical analysis and simulation results show that ECRA outperforms existing RADR and the correlation algorithms in terms of delivery ratio，average end-end delivery delay，relay ratio and average storage time.

opportunistic social networks；routing algorithms；communities；important degree；interceptionmechanism

TP393

A

1005-8788（2016）02-0063-04

10.13756/j.gtxyj.2016.02.020

2015-12-07

国家自然科学基金资助项目（61379159）；重庆市自然科学基金资助项目（cstc2012jjaA40051）

任智（1971-），男，四川内江人。教授，博士，主要研究方向为宽带无线移动通信网络及网络仿真技术。

黄希凯，硕士研究生。E-mail：413575446@qq.com