一种基于历史信息的社会机会网络路由算法

杨云辉，王小明，张立臣，刘 森，林亚光

(1.陕西师范大学 现代教学技术教育部重点实验室，陕西 西安 710119；2.陕西师范大学 计算机科学学院,陕西 西安 710119)

0 引 言

现如今随着短距离无线通讯技术的飞速发展以及移动手持智能设备的大量普及，两者之间的结合开始变得越来越成熟，移动无线网络逐渐被人们所接受，移动手持智能设备所具有的功能也越来越丰富，这些设备附带的功能不仅满足了人们的日常需求，也改变了传统移动网络的通信方式。手持这些移动智能设备，利用设备附带的Wi-Fi或蓝牙接口使设备之间组成机会网络，通过这些设备实现消息数据的传输服务。这种结合了人类活动的社会属性和物理运动的移动属性的社会机会网络[1](social opportunistic networks)受到了研究学者的广泛关注。由于该网络不需要基础通讯设施、网络部署成本低、组网便捷，在一些网络环境极端的条件下往往能发挥出较好的优势，迎合了目前大量的区域性无线通信需求。相关的科研工作者利用社会机会网络的网络特性，已经应用在多个领域，例如极端环境下的自组织通讯网络[2-4]、灾后紧急救援网络[5]、校园环境下的知识共享网络[6]等等。社会机会网络不仅弥补了有线网络的缺陷，同时也给无线自组织网络带来了新的挑战和机遇。

社会机会网络以人为中心，人们的移动行为和社会特性影响着整个网络路由的通信质量，相关学者利用网络中节点的社会性[7-9]，提出了许多改善路由投递性能的算法。例如，Prophet路由协议[10]利用时隙滑动窗口机制维护节点间相遇的细粒度实时统计数据，定义三个概率更新公式，通过概率更新公式来预测节点间的相遇概率，从而进行转发决策，优化消息的转发路径。文献[11-12]根据节点不同的社会属性将节点进行社区划分，同属于一个社区的节点间相遇比较频繁，由此为基础提出了一种基于社区的路由策略。文献[13]介绍了一种新的衡量标准—节点之间友谊的质量，据此周期性更新节点间的友谊关系，从而提出一种基于关系友好度的机会路由来进行转发决策。文献[14]通过社会网络中节点的兴趣属性，将网络中的节点划分为不同的兴趣组，不仅提高了社会机会网络的路由效率，而且保护了节点的隐私。以上这些算法虽然在一定程度上考虑了节点的社会属性，提高了网络路由的通讯性能，但是由于其忽略了社会机会网络中节点的移动规律和活跃度，未能考虑节点间相遇的历史信息对节点通讯性能的影响，因此仍需要进行进一步的研究。

文中以节点的历史相遇信息作为参考，根据其历史相遇记录，计算节点间相对社会关系强弱和其平均相遇持续时间，并分析其对路由性能的影响。然后，根据节点在网络中的有效转发能力，提出了一种基于历史相遇信息的路由算法。在该算法中，消息始终转发给与目的节点相遇概率更大且平均相遇持续时间更长的节点，直至消息达到目的节点或者消息失效。最后，通过仿真实验对该路由算法进行验证。

1 网络模型

在这种以人为载体，通过手持移动智能设备不断移动形成的通信机会来传输消息数据的社会机会网络中，节点设备活动的区域和规律受到人类社会行为的影响，经常表现出“小世界”的现象并且具有一定的规律性，符合人类的日常生活习惯。如果记录一个人长期的历史轨迹，就可以得到这个人的生活规律，同理如果记录网络中所有节点的一个长期时间序列轨迹，就可以得到整个网络的时间序列拓扑变化情况，从而根据节点的移动规律优化消息转发策略。

为了刻画社会机会网络的网络拓扑变化，便于分析网络中节点间的关系，将有限的时间序列T以τ为时间单位划分为l个时间间隔，则第m个时间间隔为τm(m≤l)，网络中节点集合为V={v1,v2,…,vn}。在任意时刻t∈T，网络的静态拓扑图可以表示为G=(V,E)，其中G为有向带权图，E为定义在G上的边集。将τm内节点vi同节点vj的相遇次数表示为E(i,j)(τm)，则在时间间隔τm内，节点vi同其他节点相遇的次数Ni(τm)可表示为：

(1)

定义1(节点活跃度)：节点活跃度是指社会机会网络中的节点在时间间隔τ内与不同节点相遇的频繁程度。节点的活跃度越高，表示当前节点在整个社会机会网络中与其他不同节点的联系越密切，同时该节点的消息转发效率也越高。假设在时间间隔τ内，节点vi相遇过的节点集合可表示为S={v1,v2,…,vn}，其中Si(τm-1)指在时间间隔τm-1内节点vi同其他相遇节点的集合，Si(τm)指在时间间隔τm内节点vi同其他节点相遇的集合，则节点vi在时间间隔τm内的活跃度Di(τm)可以表示为：

(2)

2 基于历史相遇信息的路由算法

基于历史相遇信息的路由算法遵循人类的常规思维，既要尽可能使消息在有效生存期内成功投递给目的节点，又要保证消息的完整传输，避免由于节点间相遇持续时间过短，造成通信机会的浪费。

2.1 有效转发能力计算

对一个人来说，他同朋友之间见面比较频繁，同陌生人见面稀少，见面的频率能够反映他同此人的人际关系的强弱。同理在社会机会网络中，可以根据节点间的历史相遇次数，用以衡量节点间的社会关系强弱。节点间相遇的次数越多，表明节点间社会关系越强；反之，则表明节点间社会关系较弱。在时间间隔τm内，节点vi对节点vj的社会关系强度F(i,j)(τm)可以表示为：

(3)

其中，E(i,j)(τm)为在时间间隔τm内，节点vi与节点vj的相遇次数；Ni(τm)为节点vi在时间间隔τm内同其他任意节点的相遇次数。

节点活跃度反映的是在时间间隔τ内当前节点遇见不同新节点的个数占总个数的大小，而节点的社会关系强弱则反映的是在时间间隔τ内当前节点同某个特定节点相遇的次数占当前节点与其他节点相遇的总次数的大小。通过综合考虑节点的活跃度和社会关系强弱，从而计算节点vi在时间间隔τm内对某个特定节点的有效转发能力Q(i,k)(τm)：

Q(i,k)(τm)=F(i,k)(τm)*Di(τm)

(4)

2.2 平均相遇持续时间

在社会机会网络中，绝大多数的路由算法都假设：一旦网络中的两个节点进行消息数据的转发，其消息数据都可以成功投递，而在实际路由过程中，若节点相遇的持续时间过短、网络带宽较小或者要传输的消息数据过大时，都可能无法保证消息数据的完整投递。因此，将消息数据传递给节点间相遇持续时间更长的节点，更能保证消息数据的完整投递，同时也从另一方面提高了消息的成功投递率。

将节点间的相遇持续时间定义为相遇的两个节点从彼此进入通讯范围开始到离开相互的通讯范围为止所经过的时间。每次相遇，节点都会将其相遇的经过记录到一个ET(encounter table)表中，表中记录相遇节点的id、通信连接的建立时间、通信连接的断开时间。然后通过此ET表计算两个节点间每次相遇的持续时间。

图1为某对节点历史相遇情况的时序表，每次相遇的持续时间记为{T1,T2,…,Tn}。

图1 某对节点相遇历史时序表

依据节点间历史的相遇持续时间记录，首先计算其在时间间隔τm内总的相遇持续时间，如下所示：

(5)

其中，Tk为节点vi与节点vj第k次相遇的持续时间。

(6)

节点每次相遇时，尽量将消息转发给平均相遇持续时间较长的节点，保证消息的完整转发,提高消息投递的成功率。

2.3 相遇概率

根据节点的历史相遇记录以及节点的有效转发能力预估节点间未来的相遇概率。当网络中的任意节点vi与节点vj相遇时，其相遇概率P(i,j)按照式(7)进行更新。

P(i,j)=P(i,j)old+(1-P(i,j)old)*Q(i,j)(τx)

(7)

其中,P(i,j)表示当前节点vi与节点vj的相遇概率；P(i,j)old表示更新之前节点vi与节点vj的相遇概率；Q(i,j)(τx)表示根据历史记录计算的在当前的时间间隔τx内节点vi对节点vj的有效转发能力。若在当前时间间隔τx内，节点vi对节点vj的有效转发能力越强，则节点vi与节点vj未来相遇概率越大；反之，则未来相遇的概率越小。

节点间的相遇概率随着时间动态变化，如果节点vi与节点vj在长时间内没有再次相遇，则表明节点vi与节点vj在未来的相遇概率也会随着时间变小。对于节点间的相遇概率，引入衰减函数，两节点间的相遇概率会随着时间变化而衰减。其衰减的过程如下所示：

P(i,j)=P(i,j)old*γk

(8)

其中，γ∈(0,1)表示一个衰减常数，γ值越小表示该衰减过程的衰减越快，也就是对节点间的相遇概率影响越大；k表示单位时间个数，表明两节点多久未曾相遇。

同时节点间的相遇概率也应该具有传递性。如果节点vi想要把消息数据传递给节点vo，而节点vi在移动过程中又很少遇到节点vo，但是节点vi在移动过程中经常遇到节点vj，节点vj在移动过程中可以经常遇到节点vo，那么节点vi就可以通过节点vj把消息成功传递给节点vo。因此，节点vi与节点vo的相遇概率更新公式计算如下：

(9)

其中，P(i,j)表示节点vi与节点vj当前时间的相遇概率；P(i,j)old表示更新之前节点vi与节点vj的相遇概率；P(j,o)表示节点vj与节点vo当前时间的相遇概率；Q(i,j)(τx)和Q(j,o)(τx)分别为根据历史记录计算的在当前时间间隔τx内节点vi对节点vj的消息有效转发能力和节点vj对节点vo的消息有效转发能力。

2.4 转发策略

在消息的转发决策阶段，节点根据有效转发能力和节点间的相遇概率进行消息数据的转发。为了将消息完整地传递，考虑了节点间的相遇持续时间。设定一个最小相遇持续时间阈值，当节点间的相遇持续时间大于此阈值时才进行消息的转发活动，避免因节点间相遇持续时间过短而导致消息传输失败，不仅浪费节点的通信机会，也造成网络的路由性能下降。

提出的路由算法转发策略的具体运行流程如图2所示。

当网络中两个节点相遇时，首先判断该相遇的节点是否为目的节点，若是，则将消息投递给目的节点，完成此次消息投递任务，若不是，则接着判断两节点间的平均相遇持续时间是否大于规定阈值，若不大于规定阈值则因节点间相遇持续时间过短而忽略此相遇节点，若大于规定阈值则进一步判断两节点同目的节点的相遇概率，从而最终决定是否进行消息转发或者继续持有该消息并更新这两节点间的相遇概率，完成此次的消息转发活动。

3 实验与仿真

3.1 实验设置

采用ONE(opportunistic network environment)[15]仿真工具进行路由算法的仿真实验。为了更贴近实际应用环境，使用两个真实移动轨迹数据集对路由算法的性能进行分析和评价。

(1)Infocom 2006[16]。

该数据集为参加Infocom2006大会的77个研究人员携带的iMotes设备在参加会议的3天产生的移动轨迹记录数据，此数据集合时间跨度较短，但节点间连接比较频繁。

(2)MIT reality mining[17]。

该数据集为97个麻省理工学院的学生通过携带的蓝牙设备记录大约9个月的相互之间的连接信息。此数据集时间跨度较长，但是节点间连接比较稀疏。

通过这两个真实数据集，在ONE仿真工具上将文中提出的路由算法同现有的Epidemic、BubbleRap、Prophet等路由算法在多个路由评价指标上进行性能对比。为了更好地进行仿真实验，在使用这两个数据集之前将其进行简单处理：对于Infocom 2006数据集，将其前48小时的数据记录作为历史相遇信息，后24小时的数据记录作为仿真实验的实验信息。对于MIT reality mining数据集，由于该数据集时间跨度较大，历史记录较多，取其两个月的历史记录数据进行仿真实验。其中前30天的历史记录作为历史相遇信息，后30天的历史记录作为仿真实验的实验信息。然后，分别对比分析在这两种不同的数据集场景下各个路由算法的性能优劣。仿真实验中，节点的初始相遇概率取0.8，γ=0.95，其他具体的网络仿真实验场景参数设置如表1和表2所示。

表1 Infocom 2006数据集仿真场景参数设置

表2 MIT数据集仿真场景参数设置

3.2 评价指标

文中主要从以下几个方面评价路由算法的性能：

(1)消息的成功投递率：指成功到达目标节点的消息数同源节点产生的消息总数的比值，是评价路由算法优劣的基本指标之一。

(2)消息的平均时延：指消息从源节点产生到成功投递目标节点所花费的平均时间。该指标体现了路由算法的高效性。消息的平均时延越小，目标节点需要等待的时间越少，网络资源的再利用率也会越高。

(3)消息冗余率：指网络中存在的消息副本数同成功投递到目标节点的消息数之比。消息冗余率越高，意味网络中充斥着越多的待投递的消息，不仅容易造成网络拥塞，也浪费网络资源。

3.3 实验分析

在3.1节规定的实验仿真场景设置下，分别采用不同的路由算法进行仿真，结果如图3～5所示。

从图3可以看出，随着消息生命周期的增大，各个算法的投递成功率都有不同的增长。不同的是，相较于MIT数据集，Infocom数据集中的各个路由算法消息成功投递率相对较高，这是由于Infocom 2006数据集节点间连接频繁，节点间相遇的机会更多。并且,从图中也可以看出，文中提出的基于历史相遇信息的机会路由算法同其他路由算法相比，在节点连接稀疏和频繁的场景下消息投递成功率都较高。

(a)Infocom数据集 (b)MIT数据集

(a)Infocom数据集 (b)MIT数据集

从图4可以看出，当消息的生命周期较小时，各个算法的消息平均时延相差不大，但是当图4(a)中消息的生命周期增大到3 h，图4(b)中消息的生命周期增大到24 h时，各个算法的平均时延差异开始增大。这是由于基于历史相遇信息的机会路由算法在提高消息投递率的同时能有效控制消息的转发途径，尽量避免不必要的消息传输，将消息数据较快地转发给目标节点。

(a)Infocom数据集 (b)MIT数据集

从图5中可以看出，Epidemic路由算法消息冗余率最大，远远大于其他路由算法。相较于图5(a)，图5(b)中随着消息的生命周期增大，网络的冗余率变化更为缓慢，这是由于MIT数据集节点接触时间间隔较大，节点接触机会较少。同时也可以看出，在这两个数据集中，基于历史相遇的自适应路由算法的消息冗余率增长平稳，在保证消息投递率的同时，其网络中消息冗余较少。

4 结束语

提出了一种基于历史相遇信息的社会机会网络路由算法，该算法在消息的剩余生命周期时间内，通过历史记录的节点间相遇信息评价节点对之间的有效转发能力，并且不断更新节点对之间的相遇概率，始终将消息转发给跟目的节点相遇概率高的中继节点。此外，通过ET表中保存的节点间的相遇持续时间计算节点间的平均相遇持续时间，并设定一个最小平均相遇持续时间阈值来避免消息数据不必要的转发活动，优化消息转发决策。仿真实验表明，提出的路由算法在节点通讯频繁和节点通讯稀少的情况下都能够有效地提升消息的成功投递率、降低网络通讯时延、减少网络中消息的冗余率。

[1] MOREIRA W,MENDES P.Impact of human behavior on social opportunistic forwarding[J].Ad Hoc Networks,2015,25:293-302.

[2] YAO L,MAN Y,HUANG Z,et al.Secure routing based on social similarity in opportunistic networks[J].IEEE Transactions on Wireless Communications,2016,15(1):594-605.

[3] REINA D G,ASKALANI M,TORAL S L,et al.A survey on multihop ad hoc networks for disaster response scenarios[J].International Journal of Distributed Sensor Networks,2015,2015:3.

[4] LU Z,CAO G,PORTA T L.Networking smartphones for disaster recovery[C]//IEEE international conference on pervasive computing and communications.[s.l.]:IEEE,2016:1-9.

[5] 薛莉思,张 杰,杜 江.基于DTN的地震应急通信路由协议的研究[J].计算机技术与发展,2017,27(2):182-186.

[6] ELSHERIEF M,ELBATT T,ZAHRAN A,et al.An information-theoretic model for knowledge sharing in opportunistic social networks[C]//IEEE international conference on smart city/socialcom/sustaincom.[s.l.]:IEEE,2015:446-451.

[7] DZIEKONSKI A M,SCHOENEICH R O.DTN routing algorithm for networks with nodes social behavior[J].International Journal of Computers,Communications & Control,2016,11(4):457-471.

[8] ANTHRU S V,JAYAKUMAR T P.Opportunistic routing protocols in human working day model delay tolerant networks[J].International Journal of Engineering and Computer Science,2014,3(5):5960-5965.

[9] WANG X,LIN Y,ZHAO Y,et al.A novel approach for inhibiting misinformation propagation in human mobile oppor-

tunistic networks[J].Peer-to-Peer Networking and Applications,2017,10(2):377-394.

[10] PATEL D,SHAH R.Improved PROPHET routing protocol in DTN[J].International Research Journal of Engineering Technology,2016,3(6):503-509.

[11] GONDALIYA N,SHAH M,KATHIRIYA D.A node scheduling approach in community based routing in social delay tolerant networks[C]//International conference on advances in computing,communications and informatics.[s.l.]:IEEE,2015:594-600.

[12] XIAO M,WU J,HUANG L.Community-aware opportunistic routing in mobile social networks[J].IEEE Transactions on Computers,2014,63(7):1682-1695.

[13] BULUT E, SZYMANSKI B K. Exploiting friendship relations for efficient routing in mobile social networks[J].IEEE Transactions on Parallel and Distributed Systems,2012,23(12):2254-2265.

[14] COSTANTINO G,MARTINELLI F,SANTI P.Privacy-preserving interest-casting in opportunistic networks[C]//Wireless communications and networking conference.[s.l.]:IEEE,2012:2829-2834.

[15] DIWAKER C,SAINI S.An enhanced cluster based movement model using multiple ferries nodes in VANET[J].International Journal of Management,IT and Engineering,2016,6(10):68-78.

[16] WU J,WANG Y.Hypercube-based multipath social feature routing in human contact networks[J].IEEE Transactions on Computers,2014,63(2):383-396.

[17] NUNES I O,DE MELO P O S V,LOUREIRO A A F.Leveraging D2D multihop communication through social group meeting awareness[J].IEEE Wireless Communications,2016,23(4):12-19.