延迟容忍网络中基于地点偏好的社会感知多播路由协议设计

陈家旭,唐亚哲,胡成臣,王换招

(西安交通大学计算机科学与技术系,710049,西安)

延迟容忍网络中基于地点偏好的社会感知多播路由协议设计

陈家旭,唐亚哲,胡成臣,王换招

(西安交通大学计算机科学与技术系,710049,西安)

根据延迟容忍网络中人类运动体现出的地点偏好特征,提出了一个社会感知路由协议,并采用了点到社区的多播方式。相应地设计了节点分布式地获取社区及其地理位置的方法,其中的分布式社区检测算法独立于路由协议,并具有灵活、准确的特征。协议以文中发掘出的新的社会感知量——地点偏好为中心,将消息不断地向目的社区所在的地理位置推进,在消息抵达社区成员节点之后利用社区结构所蕴含的强社会关系在社区内部继续传送消息,并激活消息复制机制。本协议基于社会网络分析,从地理位置的角度准确预测节点运动从而进行路由。实验结果表明:本协议与两个未采用地点偏好的社会感知路由协议相比,在不增加协议开销的情况下提升了至少10%的发包成功率;在社区及其地理位置已知的场景下具有更好的性能,在保持最高的发包成功率的同时缩减了50%以上的开销。

延迟容忍网络;地点偏好;社会感知;社区

在延迟容忍网络中,由于缺乏端到端链路,路由协议通常采用存储-携带-转发的传输模式,即借助节点运动造成的相遇来完成消息的传输。当前延迟容忍网络的场景大多是由人类携带的移动通信设备所组成,理解人类运动并加以利用可以有效提升路由协议的性能。人们喜欢访问对其具有吸引力的少数几个地点[1],并在这些地点停留较长时间。人们对于这些地点的频繁访问和较长时间的停留在本文中被称为地点偏好。地点偏好是造成人类运动的接触间隔时间呈幂律-指数分布的根本原因[2],因此在路由协议设计中把握人类运动中地点偏好的特点,可以更准确地预测到节点之间的相遇,从而提升协议性能。

当前对延迟容忍网络路由协议的研究[3-8]虽然也注意到了理解人类运动的重要性,但地点偏好的特征从未得到发掘与应用。本文针对此问题,围绕地点偏好并基于社区结构来设计路由协议。社区是社会网络中的重要概念,在由人类组成的延迟容忍网络中,具有相同兴趣的人们以极大的可能性共存于相近的地理位置,从而彼此之间产生较多的相遇而形成社区[8]。上述地理位置相当于对社区成员有较大的吸引力,地点偏好特征依然存在。容易看出,处于同一社区的人更容易彼此碰面,反之,拥有一定程度的社会关系的人群才会形成社区。因此,社区内消息的传输将比全网范围内消息传输更加便利。此外,社区的概念非常有利于在路由协议的设计中采用多播传输的模式,与单播传输模式相比,多播传输可明显提高消息传输效率。本协议即采用了点到社区的多播方式。协议的原理是将消息不断地向目的社区所对应的地理位置推进,由于社区的所有成员都是消息的目的节点,因此理论上可以提升协议的发包成功率,然而为得到此地理位置信息,会产生额外的开销,表现在需要先得到网络的社区结构,并由各社区成员所偏好访问的地点坐标近似估算出社区对应的地理位置。本文将k-clique社区检测算法[9]分布化,设计了相匹配的控制信息交换策略,根据这些信息分布式地估算出社区对应的地理位置,从而能够达到与未采用地点偏好的社会感知协议相比,在减少或不增加协议开销的基础上提高协议的发包成功率。在社区及其地理位置已知的场景下,本协议将不用进行额外的控制信息交换而直接使用社区偏好地点的地理位置信息,可以在提升发包成功率的同时显著降低协议开销。

1 分布式社区检测

文献[9]中提出了采用k-clique社区检测算法从社会网络中发现社区,然而运行k-clique需要全网的接触时长矩阵。本节介绍采用控制包辅助的方式来帮助各节点在本地搜集全局相关信息,从而实现分布式的k-clique社区检测算法。

节点n在本地保存它与全部节点的接触时长Dn,它所知道的全网所有节点的接触时长矩阵Mn以及用来存储社区检测结果的Rn。当节点n遇到其他节点(例如节点i)时,彼此交换控制信息。节点n产生的控制信息包含节点id和Mn。在节点n产生控制信息之前,用最新的Dn信息去更新本地的Mn,以保证所交换的接触时长矩阵中含有当前节点的最新接触时长信息。在节点n收到对方的控制信息后,用本地的Mn与收到的Mi中每一个元素的较大值来更新本地的Mn。节点n通过与其他节点不断地进行控制信息交换来保证本地的Mn含有它所能得到的尽可能准确的全网接触时长信息,以便随时在本地执行k-clique社区检测算法,具体的伪代码如下。

for alld∈Mn

ifd>=Tththen∥Tth为接触时长的权重阈值

d=1

else

d=0

end if

end for

在Mn中找到所有大小为k的完全子图(k-clique)

for allk-clique ∈Mn

Rn←k-clique

if ∃k′-clique s.t.(k′-clique中的节点数量) ∩ (Rn里任意一个大小为k的完全子图中的节点数量)=k-1 then

Rn←(在k′-clique中但不在此大小为k的完全子图中的节点)

end if

end for

删除Rn中重复的社区

虽然k-clique社区检测算法复杂度较大,但在应用于较少节点组成的实验场景中时(100人以下,例如文献[3]中用来运行k-clique的若干实际场景)并非大规模网络,因此暂不考虑算法复杂度带来的影响。

执行k-clique所需信息已存于节点本地,且随网络运行不断更新,因此本文算法具有灵活性,即可以在任何时间运行并多次运行。本文算法检测结果的准确性将通过把本文算法对人类真实运动数据[10]的检测结果与原k-clique算法及Hui等在文献[11]中提出的另一种分布式k-clique社区检测算法的检测结果进行对比验证。使用Jaccard指数来描述两个社区结构(Γj和Γi)的相似性,即

(1)

式中:Γi是社区i的成员集合,|Γi|为集合Γi的势,值为Γi中成员的数量。这里Γi为原k-clique社区检测算法检测出的社区,Γj则是被评估的分布式k-clique社区检测算法所检测出的社区。对于通过原k-clique算法所检测到的规模最大的社区内的所有成员,均用本文提出的分布式k-clique算法与文献[11]中的分布式k-clique算法分别对自己所在社区进行检测,并将结果与原k-clique社区检测算法进行比较并计算出Jaccard指数,如图1所示。检测中采用的运动数据[10]是2006年INFOCOM会议采集到的,包括了78个携带移动通信设备的与会者在3天的相遇情况。3个k-clique算法参数取值相同,即k=4,接触时长的权重阈值为10ks。

图1 两种分布式k-clique社区检测算法的对比

图1中,横坐标代表此图所示社区的成员节点id,为原k-clique算法的检测结果。纵坐标分别是本文提出的分布式k-clique算法及文献[11]提出的分布式k-clique算法与原k-clique算法之间的Jaccard指数。由图1可见,本文所设计的分布式k-clique社区检测算法,在节点检测自己所在社区的情况下,基本上可以得到与原k-clique社区检测算法完全一致的结果。这是因为社区内节点相遇频繁,能够及时并准确地更新社区内成员的接触信息。文献[11]中的分布式算法显示出与原k-clique算法较明显的偏差。

2 路由协议设计

有了分布式k-clique社区检测算法,还需要设计相匹配的控制信息交换策略,才能使各节点根据交换所得信息分布式地估算出社区对应的地理位置,从而基于地点偏好实现路由协议。分布式k-clique算法和控制信息交换策略虽然在功能上有所区分,但实际上可以由同样的控制包携带,而分布式社区地理位置生成算法也是紧跟在分布式k-clique之后,在各节点本地执行,因此这两个功能可以在同一模块中实现。节点n只需在本地同时保存最常访问的若干地点的坐标及其概率的数据结构Cn以及它所知道的所有节点的Cx(x为任意节点)信息的矩阵Fn,在与其他节点相遇而进行控制信息交换时,将Cn附在它产生的控制信息中。在收到节点i发来的控制信息之后,将Fn中每一个节点的最常访问地点的坐标及概率进行更新,将Fi与Fn中对应节点的地点偏好信息按照权重重新排序,保留权重最大的若干个。

在节点n进行完分布式k-clique算法之后,根据所检测到的各社区的所有成员的Cy(y为社区成员节点id)信息(从Fn中读取),取Cy中各热点的加权平均值近似地作为该社区在地理上的位置,其中权重值为对应的节点访问该热点的概率。至此,节点n能够大致估算出网络中存在的社区及每个社区对应的地理位置所在。估算此地理位置的伪代码如下。

for allRn中的社区

for all 此社区的成员节点

L←Fn中这些节点对应信息的加权平均值

end for

end for

在上述准备工作的基础上,可以设计并实现基于地点偏好的路由协议,协议在两节点相遇时生效。为使用消息的目的社区对应的地理位置(以L表示)信息来实现地点偏好的设计,相遇的两节点应先交换Landmark Vector控制信息。节点n产生的Landmark Vector包括了节点id;节点n下一次停止运动所在的地点dest(n);节点n在从当前位置到dest(n)的运动中所能到达的与L的最近距离distance(n,L);节点n所处的社区标签com(n);以及对于n缓存中的每一个消息m的id及其目的社区标签label(m)。当两个节点相遇时,它们首先销毁各自缓存中所有超出生存时间的消息,然后交换Landmark Vector。对于两个节点缓存中的每一个消息,如果对方节点是此消息的目的节点并且尚未收到过此消息,那么应将此消息复制给对方(留副本),收到该消息的节点将此消息id记录到已收到消息的id集合中并投递到(不留副本)之上的应用层,然后根据协议选择当前消息下一跳的中继节点。

协议采用了点到社区的多播方式,即目的社区的所有成员都是消息的目的节点。消息在生成的时候会标记上其目的社区的标签label(m),以此来协助节点辨别是否应接收该消息。同时,节点n在本地对自己所在社区的标签以com(n)表示。通过这种方式,节点可以判断自己是否应该接收某消息。协议主体思想的伪代码如下:

if com(i)=label(m) and com(j)=label(m) then

copy(m)

end if

if com(i)=label(m) and com(j)≠label(m) then

new_carrier(m)←i

end if

if com(i)≠label(m) and com(j)=label(m) then

new_carrier(m)←j

end if

if com(i)≠label(m) and com(j)≠label(m) then

if distance(i,L)

new_carrier(m)←i

end if

if distance(i,L)>distance(j,L) then

new_carrier(m)←j

end if

end if

其中copy(m)代表将消息m从当前的携带者复制到另一个节点中,而new_carrier(m)代表此次相遇后消息m新的携带者,即另一方不应再携带m。

该策略决定了消息在传输过程中每一跳的中继节点。可见在本协议中,“消息目的社区的成员节点”比“地点偏好”有更高的优先级。因为“消息目的社区的成员节点”意味着该节点与非社区成员节点相比,有更大的可能性遇到目的社区的其他成员节点。仅当相遇的两节点都不属于消息目的社区的成员节点时,协议才依照“地点偏好”选择消息的下一跳中继节点,即由两节点中在当前运动阶段可以到达更接近L的节点来携带消息。这样的设计原理可保证将消息不断地向其目的社区所在的地理位置推进,直到其中一个目的节点收到此消息。之后由此节点携带消息,并在遇到同样属于目的社区的节点时激活消息的复制机制(上述伪代码的第2行),以加快消息的传播。

3 模拟及性能评估

本节对上一节所提出的路由协议进行了编程实现,并与两个未使用地点偏好的社会感知路由协议SocialCast[8]和SGBR[7]进行了性能对比。其中SocialCast采用的是发布/订阅架构的多播模式,假设了社区与兴趣之间的一一映射关系,因此SocialCast可以直接采用本文所定义的点到社区的多播模式。SGBR虽然采用了单播的方式,但由于各个消息独立选择路由,将SGBR扩展为本文中的点到社区的多播模式不会影响SGBR的性能。

采用开销和发包成功率两个量来衡量路由协议的性能。开销指成功发送一个数据包所需要的代价,表征了路由协议的效率,计算式为c=(Rc+Dd)/Rd,其中Rc为收到的控制包数,Dd为生成的数据包副本数,Rd为收到的数据包数。发包成功率是指发送出的数据包被成功接收的概率,衡量了路由协议的有效性,计算式为p=Rd/Gd,其中Gd为生成的数据包数。

模拟中使用SWIM[1]来刻画节点运动,因为SWIM是一个优秀的人类运动模型,表现在其能够重现与实际人类运动相匹配的统计量,例如接触间隔时间、接触时长和接触数量;能够还原指定网络场景下的社区结构;能够用来准确预测路由协议在真实场景下的性能[1]。网络区域为5 km×5 km,其中有100个节点,每个节点的传输半径为250m,保证了稀疏的节点密度从而形成延迟容忍网络的环境。SWIM的相关系数取值为0.25,停止时间服从[10s,1 440s]范围内斜率为1.45的幂律分布,运动时间为10s。模拟时间设置为3d(259 200s)。

为防止SWIM生成不明确的社会关系,节点的家并非在网络区域上随机平均选取。在100个节点中随机选择20个节点,令它们的家相距较近,从而这些节点中的大部分将属于同一社区,且此社区的规模为20左右。为给SWIM模型以充分的时间来形成稳定的社区结构,在第200ks时,系统进行k-clique社区检测算法,之后赋给规模最大的社区一个标签。在第200ks时,各节点执行分布式k-clique社区检测算法。Δt之后,网络中开始产生数据包。其中Δt设为较小的值即可,并不影响结果。发包持续时间为1 ks,发包间隔为60s,与文献[8]中相同,随机选择半数的节点为发包者,包中附有标记着目的社区的标签,该社区的所有成员都将是接收者。由于发包节点是从所有节点之中随机选取,目的节点也主要是由初始被设置为离家较近的随机选择的20个节点中的大部分组成,因此这样设定可以保证包的源节点到目的节点之间的一种随机的社会关系,而不会影响到协议的性能。k-clique算法的k取值为4,接触时长的权重阈值为60ks。假设所有节点缓存足够大。实验在用C++编写的离散事件模拟器中运行。

路由协议中包与其副本的总数r在本文提出的协议中设置为4,在SocialCast中设置为5,而在SGBR中设置为32。本协议并不依赖于复制机制,故取3个协议中的最小值,由于采用了平均分配副本数量的机制(即相遇双方节点在复制包的时候各持有半数的包副本,因此r需设置为2的幂次方),故r取值为4。SocialCast对复制机制的依赖性次之,同时为避免SocialCast与本协议对比时由于r值过小的原因而对协议性能造成的影响,故r取略大于4的值。SGBR较依赖复制机制并采用了平均分配副本数量的机制,从而r设为较大值32(即25)。SocialCast中的其他参数如ωcdc、ωcol、λ和ε(参数定义见文献[8])都取了与文献[8]中相同的值。同样地,SGBR中的其他参数如α、γ、Cth和Dth(参数定义见文献[7])也都取了与文献[7]中相同的值。对于每个实验数据,取20次运行结果的平均值,其中每次运行都采用了不同的随机数种子。协议性能对比结果如图2、图3所示。

图2 3个路由协议的开销

图3 3个路由协议的发包成功率

虽然延迟容忍网络中消息传递对运动的依赖性导致Rd直接受节点运动的影响,但是在运动模型及参数都确定的情况下,可以认为Rd是运动模型的无关变量。然而,协议对Rd却可产生较大影响。假设在不考虑生存时间的情况下数据包到达目的节点的平均延迟为d,协议的参数中将数据包的生存时间设置为H,那么Rd与H和d的关系如下:当H≤d时,大部分数据包在还没有到达端到端延迟期望值的情况下就已经因为到达生存时间而被销毁,这将导致很低的Rd值。从H>d开始,Rd值将显著增加,但当H增加到一定程度之后,社区中相对可达的节点都已经收到了数据包,Rd值随H的增幅又将变缓慢,因而开销c=(Rc+Dd)/Rd≈Rc/Rd在一定范围内呈现出如图2所示的与Rd大致成反比的关系。同理,发包成功率p=Rd/Gd中,Gd在模拟参数指定的情况下为常量,因此p与Rd成正比。结合Rd与H的关系,即有图3所描述的发包成功率随生存时间的变化情况。

前述场景中社区对应的地理位置为未知信息,并通过节点交换控制信息分布式地获得。实际上,在其他场景,例如人们熟悉的环境中,社区及其对应的地理位置为已知信息,不再需要分布式社区检测与控制信息交换,本协议的开销可以大大降低,从而相对于其他协议体现出更明显的优势。作者同样进行了这种场景下的模拟,即将运动模型从SWIM换成HCMM[12]再次观测3个协议的性能。HCMM刻画了社区及对应地理位置已知的网络环境,设置模拟时间为28 800s,发包时间为3～4 ks,运动速度服从1～6 m/s的平均分布,停止时间为10s,网络中社区数量为4,本协议中包不再采用复制机制,其他参数均与上述场景相同。限于篇幅,此处并未给出具体图示,然而模拟结果表明在不需要主动获得社区及所对应的地理位置的场景下,与SocialCast及SGBR相比,本协议可以在保持最高发包成功率的基础上缩减协议开销达50%以上。

4 结 论

针对延迟容忍网络中人类运动的地点偏好特征,提出了一个社会感知多播路由协议。协议将消息逐渐向目的社区所在的地理位置传送,当到达其中一个目的节点后,利用社区之间的强社会关系,由此节点一直携带并激活复制机制,以便于其他目的节点收到消息。实验结果表明,与两个未采用地点偏好的社会感知路由协议相比,本协议在不增加开销的情况下提升了发包成功率,而在无需主动获得社区地理位置信息的场景中,可在保持最高发包成功率的同时大幅降低开销。

[1] KOSTA S,MEI A,STEFA J.Large-scale synthetic social mobile networks with SWIM [J].IEEE Transactions on Mobile Computing,2014,13(1): 116-129.

[2] MAITI R R,MALLYA A,GANGULY N.Characterizing Mobility Models for Human Movement [J/OL].(2013-02-19) [2013-10-15].http:∥web.engr.illinois.edu/～amallya2/trial/aCleanerWebsite/files/MobilityModel_CHANTS.pdf.

[3] HUI Pan,CROWCROFT J,YONEKI E.Bubble rap: social-based forwarding in delay-tolerant networks [J].IEEE Transactions on Mobile Computing,2011,10(11): 1576-1589.

[4] GAO Wei,CAO Guohong.User-centric data dissemination in disruption tolerant networks [C]∥Proceedings of the 30th Conference on Computer Communications.Piscataway,NJ,USA: IEEE,2011: 3119-3127.

[5] LI Feng,WU Jie.Mops: providing content-based service in disruption-tolerant networks [C]∥Proceedings of the 29th IEEE International Conference on Distributed Computing Systems.Piscataway,NJ,USA: IEEE,2009: 526-533.

[6] BULUT E,SZYMANSKI B K.Friendship based routing in delay tolerant mobile social networks [C]∥Proceedings of the Global Telecommunications Conference.Piscataway,NJ,USA: IEEE,2010: 1-5.

[7] 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.

[8] COSTA P,MASCOLO C,MUSOLESI M,et al.Socially-aware routing for publish-subscribe in delay-tolerant mobile ad hoc networks [J].IEEE Journal on Selected Areas in Communications,2008,26(5): 748-760.

[9] PALLA G,DERNYI I,FARKAS I,et al.Uncovering the overlapping community structure of complex networks in nature and society [J].Nature,2005,435(7043): 814-818.

[10]HUI Pan,SCOTT J,CHAINTREAU A.CRAWDAD metadata: cambridge/haggle/imote/infocom2006 [EB/OL].(2009-05-29) [2013-07-30].http:∥crawdad.cs.dartmouth.dartmouth.edu/cambridge/haggle/imote/infocom2006.

[11]HUI Pan,YONEKI E,CHAN S Y,et al.Distributed community detection in delay tolerant networks [C]∥Proceedings of the 2nd ACM/IEEE International Workshop on Mobility in the Evolving Internet Architecture.New York,USA: ACM,2007: 7.

[12]BOLDRINI C,PASSARELLA A.HCMM: modeling spatial and temporal properties of human mobility driven by users’ social relationships [J].Computer Communications,2010,33(9): 1056-1074.

(编辑 武红江)

DesignofaSocial-AwareMulticastRoutingProtocolBasedonLocationPreferenceinDelayTolerantNetworks

CHEN Jiaxu,TANG Yazhe,HU Chengchen,WANG Huanzhao

(Department of Computer Science and Technology,Xi’an Jiaotong University,Xi’an 710049,China)

A social-aware routing protocol utilizing a ‘one-to-community’ multicast scheme is proposed.The protocol is based on the characteristics of location preference in human mobility in delay tolerant networks.A distributed method is designed to obtain the community structure and its geographical position,where the distributed community detection algorithm is independent of the routing protocol and has features of flexibility and accuracy.The protocol concentrates on the exploited social-aware metric,namely location preference,and forwards messages towards the geographical position of the destination community.Once the message arrives one of the destination nodes,strong social relations inside the destination community can be utilized to accelerate the message’s arrival at other destination nodes by means of duplicating replicas.The protocol accurately predicts node mobility in geography based on social network analysis.Simulation results given by comparing the proposed protocol with two existing social-aware routing protocols without using location preference show that the packet delivery ratio raises at least 10% without increasing the cost.It is also observed that the proposed protocol has better performance in the scenario where communities and their geographical positions are known.The cost reduces more than 50% while the packet delivery ratio is the highest.

delay tolerant networks; location preference; social-aware; community

2014-01-12。

陈家旭(1983—),男,博士生;胡成臣(通信作者),男,副教授。

国家自然科学基金资助项目(61170245)。

时间:2014-05-30

10.7652/xjtuxb201406003

TP393

:A

:0253-987X(2014)06-0013-06

网络出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20140530.1615.003.html