移动社会网络中基于社区的消息转发技术

陈志鸣，陈安邦

(南京邮电大学 计算机学院、软件学院、网络空间安全学院，江苏 南京 210023)

0 引 言

延迟容忍网络(delay tolerant network，DTN)是一种具有挑战性的网络，其中通信设备之间的联系是间歇的。因此，源和目的地之间的端到端路径很少存在。在延迟容忍网络中，节点通常具有高度移动性，并且经常移出节点的范围，导致整个网络中的节点之间只能暂时处于连接状态[1]。

移动社会网络(mobile social networks，MSN)由移动用户组成，移动用户可以采用短距离通信模式以低成本交换消息，比如多媒体等较大文件[2]。这种移动社会网络可以被视为一种特殊的延迟容忍网络。

由于固有的间歇性连接，消息转发是该网络最具挑战性的方面之一。在文中，节点中心性和运动方向的理论被用来解决这个特定问题。提出了一种新颖的转发策略，即混合消息转发(mixed message forwarding，MMF)，利用边界投递箱(boundarybox)特殊设施来减少传输延迟。

1 相关工作

早期提出的Epidemic[3]不加选择地向网络直接扩散信息，具有最高的传输率和交付时间，但也付出了最高的传输成本。为了降低传输成本，一些移动机会网络算法利用各种社会性质的度量来选择中继节点，典型的有SimBet[4]、Bubble RAP[5]和Friendship[6]。SimBet使用相似性和中介中心性度量来确定具有更好传递性的中继节点。类似地，Bubble RAP使用中心性和社区来做出转发决策，Friendship通过引入节点之间友谊质量的度量来衡量节点之间的关系强弱。

Zhang Huijuan等在文献[7]中提出的协议扩展了Kim等的工作[8]，这个协议另外添加了端点偏向扩展的自我中介中心性的使用。基于接触频率的方法(CFBA)和基于接触持续时间的方法(CDBA)[9]都使用基于联系持续时间的k-clique方法将节点分成社区，并使用中心性(表示网络连接性的度量)来选择中继节点。基于社交的单一副本路由SBSCR[9]是一种基于社区的路由机制，其中路由决策是基于社交的效用(SBU)来考虑相似性和友谊值。Chen和Lou[10]提出的两种路由，预期相遇路由(EER)和社区感知路由(CAR)，是使用了基于节点之间的交互历史确定的度量。IRS[11]是一种基于激励的路由策略。在这种方法中，节点可以参与并获得奖励以牺牲它们的自私。Choksatid等提出协议SEd[12]对Epidemic路由方案进行了改进。由Igarashi等[13]提出的使用名为社区和中心性的参数控制每个节点的消息转发。ICMPF[14]利用多跳MSN中的网络节点的各种自私行为，是一种激励型的多拷贝分组转发协议。FCNS[15]是一种模糊路由转发算法，利用了移动机会网络中的综合节点相似性(移动和社会相似性)来决定节点的传输。

通过分析以上方法，笔者认为移动社会网络中的转发算法主要存在消息投递率低、传输延迟高的问题。还有就是中心性度量如何改进，以及在某个社区内(小范围)和各个社区间(大范围)资源消耗权衡的问题。基于此，文中改进了中心性度量，并且在某个社区内和各个社区间采用不同的转发方法。

2 MMF概述

为了解决这些问题，文中提出了一种基于社区的机会网络算法MMF。MMF算法分为四个部分：内转发，外转发，漫游和获取，如图1所示。

图1 算法模型

(1)社区内转发阶段，节点在源节点所属的社区中传输消息，直到节点遇到边界投递箱。节点更倾向于将消息发送到边界投递箱。

(2)社区外转发阶段，当边界投递箱接收到消息拷贝时，它将消息传播到其传输区域内邻近社区的节点。

(3)在漫游阶段，节点优先将消息转发给边界投递箱。使用基于节点移动方向的多拷贝方法将信息扩散到其他社区。

(4)在消息获取阶段，目的节点将从任何首次遇到的携带消息的设备提取消息。携带消息的设备可以是节点或边界投递箱。

在上述方案中，四个阶段不一定遵循顺序，该顺序由源节点和目的节点位置确定。源节点和目的节点在一个社区中，因此可以直接进入第四部分。或者，如果目标位于源节点的社区附近，则不会执行第三阶段。

3 MMF算法

本节将详细介绍MMF算法。文中仅关注消息传输，只要每个携带消息的设备有足够的缓存空间且链路具有足够的带宽，它就可以发送消息。此外，任何两个节点之间以及节点和边界投递箱之间的通信时间是独立的。

3.1 内转发阶段

中心效用值可用于衡量节点在消息传输中的重要性。文中定义的中心效用值由两个参数组成，即节点转发消息的数量和邻居节点更新数。中心效用值计算如下：

节点j在某一时隙的转发消息的数量标准化计算方法如下：

(1)

(2)

其中，vj(t)是当前时隙的邻居节点集合；vj(told)是前一个时隙的邻居节点集合。

节点j在某一时隙的邻居节点更新数标准化计算方法如下：

(3)

节点具有更高的u和v值，更有可能遇到目地节点。所以通过以下公式组合这两个参数来定义节点j的中心效用值：

Uj=αv+βu

(4)

其中，α，β是设置的权重。

当节点接收到邻居节点的中心效用值Uj时，该节点将它的值与最大值进行比较。如果此节点的值较低，则它会将消息转发到具有中心效用值的节点。

3.2 扩散阶段

在传播阶段，当边界投递箱接收到某个节点发送的消息副本时，边界投递箱将消息副本扩散给其他没有消息的节点，而这些节点在发送该副本节点所属的社区之外。

3.3 漫游阶段

|cosθ|=

(5)

其中，k≤1。

3.4 获取阶段

在提取阶段，目的节点只是在遇到携带消息者时获取消息。这个消息携带者可能处于源节点社区内转发阶段，外转发阶段或者漫游阶段。最糟糕的情况是，数据包被扩散到每个社区，目的节点才获取到消息。

4 仿真实验

4.1 算法的比较

文中只关注移动社会网络中的转发算法。为了进行公平的性能比较，将文中算法与现有的零知识多拷贝路由算法进行比较：Epidemic、Prophet和HS。

算法Epidemic、Prophet和HS都是通过复制传递消息的。Prophet算法是一种基于效用的多拷贝路由算法。HS算法中数据包携带者采用二分法将副本分割给遇到的节点或投递箱。

4.2 参数设置

文中模拟的场景相对较大，节点随机移动，节点的初始位置也是随机生成的。边界投递箱在初始化时生成并具有固定位置。另外，可以根据需要改变参数值，以便观察每个参数值对结果的影响，得出最优结果，有利于与其他算法进行比较，评估算法的优缺点。

文中模型的场景是一个矩形。为了简化模拟，将场景的长度和宽度设置为相同。节点的传输半径设置为15，社区数量固定为9。实验大致分为三个：平均投递率的比较，平均传输时间的比较和MMF算法中余弦值对平均传输时间的影响。在第一个实验中，四种算法的社区长度和宽度D被设置为50,60和70，然后进行比较。在第二个实验中，四种算法中的节点数N被设置为1 000,2 000和3 000，然后进行比较。评估参数如表1所示。

表1 参数设置

在此模拟中评估的指标是平均投递率和平均传输时间。平均投递率是成功交付数量与消息总数之比，平均传输时间是第一个副本到达目的地的传递时间。

4.3 仿真结果和分析

通过四组仿真实验来评估算法的各项参数对性能的影响。在第一组模拟中，将四种算法的社区长宽D依次设置为50，60和70，同时设置N=2 000，θ=0.5。在第二组模拟中，将四种算法的节点数量N依次设置为1 000，2 000和3 000，同时设置D=50，θ=0.5。为了更加具体地观察各个算法之间的差别，在这两组实验中将依次在t=240，t=600，t=6 000的条件下观察各个算法的走向，如图3和4所示。

图3显示，随着社区长度和宽度的增加，四种算法的平均投递率随之降低。相反，HS算法在D=70时具有最差的平均投递率。Prophet的概率选择机制导

(a)t=240

(b)t=600

(c)t=6 000 图3 平均投递率的比较

致消息不断接近目的节点，但由于Prophet仅依靠节点转发消息，因此它的性能相对较低。MMF主要是由于边界投递箱的外部转发功能，使得消息能够快速传播到其他社区，因此它的性能优于上述两种算法。Epidemic的消息数量和转发节点数量不受限制，因此在小情况下扩散速度非常快，但随着整个场景变大，扩频消息需要更多的传输时间。

(a)t=240

(b)t=600

(c)t=6 000 图4 平均传输时间的比较

接下来还进行了三组模拟，以便根据平均传输时间来评估上述算法的性能。图4中的结果表明，随着节点数量的增加，平均传输时间都有减少。在t=240和t=600时，Prophet在n=1 000时具有最长的传输时间。当t=6 000时，HS的传输时间大于其他三种算法。总的来说，t越长，HS越不稳定。因为边界投递箱在HS中的作用只是在社区中传播消息，所以社区之间的消息传播仅依赖于进出社区的节点，因此节点的数量对它有很大的影响。而在MMF中，因为边界投递箱的外转发和漫游功能，消息可以快速传播到其他社区，因此除了Epidemic之外，它在三种算法中的平均传输时间更短。

图5 MMF角度余弦值对平均传输时间的影响

接下来研究MMF在漫游阶段使用的角度余弦值K的变化对平均传输时间的影响。设置N=2 000，D=50，t=240。如图5所示，比较了在K=0.1，K=0.5，K=0.8和K=1时的平均传输时间。结果表明，K越接近1，平均传输时间越小，但这将导致大量拷贝，不必要的能量消耗和无用的带宽占用。

5 结束语

研究了一个特殊的移动社交网络，其中运行场景包括一些节点，社区和边界投递箱，并提出一种零知识多拷贝路由算法MMF。MMF为边界投递箱设置了更高的优先级，以帮助快速传播信息。理论分析和仿真结果表明，边界投递箱在信息传播过程中起着重要作用。通过使用边界投递箱，MMF取得了比现有的几种零知识MSN路由算法更好的性能。