移动社交网络中一种基于社交关系的自适应路由算法∗

黄嘉玲 李建波 李 英

（青岛大学计算机科学技术学院 青岛 266071）

1 引言

容迟网络（Delay Tolerant Network，DTN）最初是为星际网络（InterPlanetary Network，IPN）通信而提出来的，其主要目标是针对时延长、链路连接间歇性等特点的网络，进行互联和互操作［1］。现在，IPN的研究者将其架构应用在其他的挑战性网络中，如移动社交网络（MSNs）［2～3］、车载自组网络［4～5］、军事网络［6］等。移动社交网络作为容迟网络应用中的一种，一直是国内外研究的主要趋势，随着移动智能终端的迅速发展和普及，社交网络已将其业务扩展到移动终端，其主要由无线便携式设备形成，例如由人类携带的iPad、PDA、智能手机等。由于节点的随机移动性，任何两个节点之间不存在持久连接，因此数据传输通常采用“存储—携带—转发”通信模式：节点向相遇节点发送消息，接收消息的节点携带该消息直到遇到可发送的其他节点，以便该消息到达目的节点，这是MSNs中数据传输和路由的基本原理。但从源节点到目的地的路径是间歇性连接的，导致常规路由协议通常不适用，因此路由成为MSNs中极具挑战性的一个问题［7］。

早期 Vahdat和 Becker提出了 Epidemic［8］算法，一种针对在间歇性连接网络中进行的路由协议，该算法是最简单的复制路由协议。每个用户维护一个数据队列，当两个用户相遇时只传输对方没有存储的数据，显然Epidemic Routing在路由算法中具有较高的数据传输成功率，但是这种不受限制的复制消息策略也带来了极大的网络开销。为了克服Epidemic算法带来的过量副本问题，T.Spyropoulos等人提出了经典的 Spray and Wait算法［9］，首先，在Spray阶段该算法将复制副本折半传输给所有相遇邻居节点来改进传统传输机制；其次，在消息副本仅剩一个时候，进入等待阶段，此时节点仅将消息传递于目的节点。Lindgren等［10］使用节点相遇和传输的历史数据，计算节点之间的转发概率，并提出了基于转发概率的路由协议Prophet。在文献［11］中，普通节点采用随机运动，轮渡节点协助普通节点沿着恒定路径传递消息。这解决了传统DTN中的许多问题，但轮渡节点的路径选择对研究人员来说仍然是一个难题。因此这激发了DTN中社交网络［12］应用的想法。

当人类参与网络活动时，移动节点的行为表现出一定的社会关系与属性。一些研究［13］表明，节点之间的社会关系与属性对节点相遇事件有着重要影响，有助于减少路由开销和提高数据传输的成功率。因此，许多研究人员充分利用节点的社会属性来设计数据转发机制，并取得了良好的效果。从长远来看，基于节点间社会关系的数据传输机制比其他转发模式更稳定［13］。

在基于社会属性的路由算法中，关键点在于发现和测量节点之间的社会关系，这取决于对节点相遇历史数据的分析［14～15］。许多研究使用历史数据来预测节点相遇概率，从而设计出最佳的消息转发算法。SimBet［16］借鉴社交网络的想法，基于节点社会相似性、中介性和联系强度分析到达目的地的路径，提高了交付率和时间。在文献［17～18］中，作者利用机会主义和预期接触节点等效用函数决定是否将消息转发给机会接触的节点或预期接触的节点，该算法利用节点属性评估其消息传递的有效性。Bubble Rap［19］通过对社交网络的理解，利用节点的中心性来确保消息成功传递。在整个网络和局部社区为每个节点分别设定两个索引等级：全局等级（Global Rankness）和局部等级（Local Rank⁃ness）。发送消息时，节点重复将消息传递于网络中全局等级更高的节点直到遇到目标节点社区节点。在目标节点所在的社区中，该消息进一步被转发到具有更高局部等级的节点，直至到达目的节点。但该路由方法并未考虑如果目标节点属于全局中心性较低社区的可能性，因此该路由方法容易造成较长延迟。

为克服移动社交网络中源节点与目的节点之间连通路径不稳定的情况，本文提出了一种基于社交关系的自适应路由算法（ARASR）。受移动社交网络中人类社会行为的启发，我们针对移动用户经常传递消息于社交关系密切的用户，提出了目标区域加权中心度和有效传输能力，并根据副本的数量选择不同策略传输数据。其中，目标区域加权中心度主要针对目的区域节点，具有较大目标区域加权中心度的节点遇到目的社区中节点的频率也越高，而有效传输能力通过节点活跃度和节点转发意愿度定义。该算法一方面考虑当携带消息节点副本数量仅剩一个时，为将消息尽可能传递到目的节点区域，ARASR算法选择用户与目标区域加权中心度较高的节点实现消息传输，提高消息到达目的区域可能性。另一方面，当消息副本大于一个时，由于有效传输能力能够反映节点在社区间与其他节点的交互情况，因此根据有效传输能力自适应地平衡每对节点之间的消息副本的数量，允许具有较高传输能力的用户可获得更多消息副本促进消息有效传播，提高数据传输率。

2 ARASR算法

本节将主要介绍ARASR算法中提出的节点有效传输能力以及目标区域加权中心度的计算，并详细解释如何通过节点活跃度以及节点转发意愿度评估节点的有效传输能力，最后说明如何实现消息副本控制机制。算法实现具体流程如图1所示，其中Vd表示目的节点，与传统路由算法不同的是，我们首先判断携带消息节点与目的节点是否属于同一社区，如果属于同一社区，则将消息直接传递给目标节点。其次，根据判定消息副本数量是否大于1选择不同策略确定中继节点，加速消息传播到目标节点区域。因此ARASR算法的主要工作是在第二部分路由策略的选择，根据所提出的两种指标（目标区域加权中心度和有效传输能力）选择下一跳节点，并自适应的调整每对节点之间的消息副本数量，该方法不仅有助于尽可能快地传播消息副本，而且还能确保与目标区域接触频繁的节点可以携带更多的消息副本。

图1 ARASR流程图

2.1 目标区域加权中心度

由于本文的主要工作是在移动社交网络背景下设计路由方法提高信息投递率，并不主要探讨社区划分算法，因此本文根据现有算法中针对没有明确社区结构的网络环境提出的社区检测算法［20～21］，将节点轻松划分到不同社区，并且假设网络中源节点已知目的节点所在区域。

为权衡多社区内节点的中心度，提出针对目的社区的目标区域加权中心度。众所周知，网络中任意一对节点Vi与Vj之间的相遇时间间隔遵循具有参数的指数分布［22］，换句话说，其他节点Vj到达给定节点 Vi的到达率遵循泊松过程。因此，是每对节点Vi和Vj之间的接触频率，值越大，Vi和Vj相遇的频率越高。由此可得，节点Vi遇到其他节点来自子集Z⊆V的相遇时间间隔也遵循指数分布，即鉴于以上考虑，节点Vi与其他节点来自目标社区D的相遇时间间隔通过加权中心度定义如式（1）所示：

节点Vi与目标节点所在区域D内节点的参数λVi，D越大表示目标区域加权中心度越高。因此，具有较大目标区域加权中心度的节点遇到目的社区中节点的频率越高。

2.2 节点有效传输能力计算

本节根据节点活跃度（Activeness Degree）和节点转发意愿度评估节点的有效传输能力，这是由于节点活跃度可以有效反映当前节点在移动社交网络中的受欢迎程度，而节点的转发意愿度能够体现节点在网络中的合群性。

图2 节点活跃时间示意图

因此，为评估节点活跃度我们分别计算了节点在不同时间段里的相遇次数：总时间段tnow-t_initial以及最近时间段tnow-t1，如图2所示。由于总时间里的平均相遇数能够反映整个过程中节点大体的活动状态，而最近一段时间内的平均相遇次数能够反映当前节点状态。所以在计算节点活跃度时，为避免忽略节点长时间里的活动起伏和当前活动行为，本文将两个时间段相结合定义节点活跃性。节点活跃度ADVi计算公式如式（2）所示。

其 中 ，EVi，Vj表示一对节点的接触次数，表示最近时间段内与其他节点的平均相遇次数，表示总时间内与其他节点的平均相遇次数，参数∂为初始化常量，用于反映节点活动中两段时间的权重。

移动社交网络中，活跃度更高的节点接触其他节点的概率越高，则更有可能将消息副本扩散到网络中，但节点转发意愿度同样不可忽略。本文通过式（3）使用节点的出度定义转发意愿度，其定义如下：

种子节点的选择不但要考虑节点在网络中与其他节点的连接紧密程度，也要考虑节点是否可以有效传递消息。为了加速消息传递到目的区域D，最终通过结合节点活跃度和节点转发意愿程度评估节点Vi的有效传输能力QVi，由式（4）表示。

2.3 消息副本控制机制

ARASR算法通过每对接触节点之间定义的度量指标进行不对称分配消息副本数量。由于网络中节点内存大小固定，经常存在一部分节点不能快速有效传递消息。因此我们考虑针对不同节点分配不同数量的消息副本，即将携带消息节点Vi与相遇节点Vj的副本数量利用式（5）进行分配，该方法有效减少了丢包率并且提高消息的投递概率。

时选择Vj作为下一跳中继节点并根据节点有效传输能力重新分配副本数量。最后，节点Vi将分配的消息副本发送到相应节点后并更新自身的副本数量如式（6）所示。

当副本数量超过一个的节点仍将不对称的分发消息副本，直到该节点遇到目的节点或仅剩一个消息副本。该方案有助于缩短消息在整个网络中传播的时间。

2.4 ARASR算法实现

本节将主要介绍ARASR路由算法的实现，根据现有的社区检测算法，我们假设网络中源节点已知目的节点所在区域，并且消息m的副本的初始数量为固定值h。综合上述方案，我们最终实现ARASR算法，其具体算法实现策略见算法1。算法1 ARASR路由算法

input：

n：current node

v：encounter node

d：destination node

m：message carried by n

Num_n：number of copies of n

if n∈D then

n forwards m to d，finishes the transmission

else

when n encounters v

for（Num_n＞1）

if（Qv＞Qn）then

n forwards the calculated number of message m that v

could be assigned

else

n still carries the replica of message m

for（Num_n ≤ 1）

if Wv＞Wnthen

n forwards a copy of m to v

3 仿真实验

3.1 仿真环境

本节采用ONE仿真模拟器（Opportunistic Net⁃work Environment）［23］仿 真 评 估 ARASR 算法 的性能，并同时加入Prophet、Epidemic和First Contact算法与本文提出算法比较，First Contact路由协议只考虑消息在一跳范围内时进行转发消息，Epidemic路由协议通过简单复制方法将消息分发给每个可能遇到的节点，Prophet算法在相遇节点中权衡转发到目的节点概率更高的节点投递消息。

为模拟现实生活中移动社交网络场景，本文选取Helsinki City作为仿真场景进行实验，该模型更能体现人类真实社会的交互情况。赫尔辛基城市场景的网络覆盖范围设定为4500×3400m2，其中包括126个移动节点被分为80个运动速度为0.5m/s～1.5m/s的行人，6个7m/s～10m/s的电车以及 40个2.7m/s～13.9m/s的汽车，缓存区大小设置足够大，因此消息不会由于缓存区过早耗尽而丢失。通讯设备使用传输速度和半径分别为250KBps和20m的蓝牙设备作为标准。为考虑到MSNs间歇性连接和频繁断开的特性，我们设置每条消息的默认生存周期设定为2个小时，默认时间间隔为30s。在这次模拟实验中，我们使用四种评估指标来评估算法的性能，即投递率、网络负载率、平均时延和平均跳数，并且通过改变缓存空间大小，消息生成时间间隔和消息的生存时间来查看这些度量的变化。仿真结果表明，我们提出的方案显著提高了路由性能，表1总结了模拟中使用的其他仿真参数。

表1 仿真参数设置

3.2 仿真结果分析

在这次模拟实验中，我们使用四种评估指标来评估算法的性能，即投递率、网络负载率、平均时延和平均跳数，并且通过改变缓存空间大小，消息生成时间间隔和消息的生存时间来查看这些度量的变化。

3.2.1 改变节点缓存空间

我们通过不同路由方案在不同节点缓存空间大小下的性能比较得出，ARASR相比较其他三个算法在消息投递率、平均时延、平均跳数等方面都取得明显优势。这是由于ARASR算法充分考虑节点在移动社交网络中的社会属性，根据目标区域加权中心度和有效传输能力等指标选择下一跳中继节点，减少了消息丢包的概率。图3为节点缓冲区从4MB增加到18MB的模拟结果。

图3 不同缓存空间下四种算法的性能表现

从结果可以看出，ARASR算法在各方面明显优于其他算法，与Prophet和Epidemic路由策略相比，ARASR的投递率增加约29%和32%，平均时延分别降低约10%和15%。其中，Epidemic路由协议的网络负载率最高，主要由于该算法没有限制网络中消息副本数量，从而造成网络负担严重，而本文提出的路由方法在最初就限定了副本数量，而且提出了副本控制机制，有效地限制了消息在网络中的扩散。由此可见本文提出的算法相比其他算法具有更好的表现。

3.2.2 改变消息生存时间

消息生存时间长短与缓存空间大小密切相关。现实生活中每条消息都会受到消息生存时间TTL（Time to live）的限制，而随着生存周期的延长，消息则会长时间活动并占用大量缓存区空间。本次仿真模拟中设定消息生存周期从2小时增长到5.5小时，观察TTL的变化对路由性能带来的影响，其结果如图4所示。

从图中可以看出，Epidemic、Prophet算法随着消息生存时间的增长投递率逐渐下降，而具有自适应副本分配的ARASR算法提供了最大传输率和最低平均跳数，并且ARASR的网络负载率也远低于其余三种算法。这是由于随着消息生存周期的增长导致节点缓存空间不足，而ARASR为避免缓存空间过度消耗，针对缓存空间内消息副本数量不同采取不同的衡量指标投递消息，First Contact路由算法在网络中转发消息的副本数量仅有一个，所以投递率呈现增长趋势，但在其他方面表现远不如ARASR算法。因此结果显示ARASR与Epidemic、Prophet算法在平均时延方面虽然基本持平，但各方面性能比其他算法更加优秀。

图4 不同消息生存期下四种算法的性能表现

3.2.3 改变消息生成时间间隔

图5 不同消息生成时间间隔下四种算法的性能表现

图5 描述在Helsinki City模型中不同消息生成时间间隔对四种路由算法的性能影响结果，可以观察到ARASR稳定运行。我们设置消息生存时间间隔以10s为增量增加到90s，从图5的结果来看，ARASR在消息投递率、开销率、平均时延和平均跳数等方面表现都优于对比的其他三种算法，进一步证明我们提出的路由算法可以提高网络传输性能。由于随着消息生成时间间隔的增长，移动社交网络中生成大量消息，可以看出除First Contact算法以外其他算法的网络负载率呈上升趋势，但First Contact算法消息投递率始终低于0.4，原因在于该路由方法虽然是基于转发路由策略中的代表算法之一，但携带消息的源节点随机选择任意邻居节点转发消息，并且副本数量只有一个，从而造成传输延迟长且投递率低。Prophet算法虽然根据与目标节点的接触概率选择中继节点，但并未考虑节点转发意愿度等社会属性，因此不可避免产生较高负载率。从图5可以明显看出ARASR和Prophet算法的平均跳数和时延一直保持最低，这是因为其余算法没有对中继节点的性能进行评估，从而导致盲目选择下一跳节点增加了传输时延和跳数。而ARASR的网络负载只有Epidemic和Prophet算法的24%、34%。简而言之，所提出的方法显着提高了在移动社交网络上的路由性能，并且利用多种衡量指标筛选下一跳节点进行消息传递，综合各方面表现优于其他算法。

4 结语

在本文中，我们提出了一种针对移动社交网络的自适应路由协议ARASR，根据节点携带消息副本数量的不同，通过分析路由中两个关键属性解决优化问题，分别是有效传输能力和目标区域加权中心度。为优化选择中继节点，ARASR在社交网络场景中引入节点加权中心度，利用任何节点对之间的接触时间间隔遵循指数分布来评估节点与目标社区间的关系。此外，基于有效传输能力提出了消息副本控制机制，避免网络中生成过多冗余消息。最后我们将本文提出的算法在ONE模拟器上进行评估，并通过Helsinki City模型的广泛仿真演示了ARASR算法如何显著优于Prophet、Epidemic和First Contact路由算法。对于路由算法来说，较低的路由开销可以减少中继消息的数量和不必要的缓存空间占用，并且提高节点的有效投递率，而ARASR实现了较低的路由开销并在消息传输率方面表现优异，更加适用于MSNs中的消息传输。未来工作将集中在进一步降低开销率增加ARASR的投递，并考虑通过额外约束条件来优化下一跳中继节点的选择。