移动社会网络中基于社会感知的数据转发算法

邓 敏，徐 方，熊曾刚，叶从欢，夏洪星

(湖北工程学院 计算机与信息科学学院，湖北 孝感 432000)

0 引 言

移动社会网络[1](mobile social networks，MSNs)为用户提供方便灵活的网络服务，能广泛应用于智慧城市、车载网络、应急救援和健康医疗等领域[2]。然而，移动社会网络中的节点通常是稀疏的，并且节点之间的链路频繁变化，经常不存在端到端的通路，传统移动自组网中使用的转发数据的方式不再适用。因而研究高效的移动社会网络数据转发算法是当前亟待解决的难题。

移动社会网络中的节点为人们携带的智能移动设备，因而人们的社会关系极大地影响着节点的移动行为[3]。PRoPHET算法[4]通过统计网络节点之间相互接触的信息预测节点未来移动的规律。社群是社会网络的重要属性之一，具有共同社会属性和兴趣的人们通常会组成一个群体，称之为社群，相比于社群之间成员的社会交往，群体内部成员的社会交往会更加频繁。为了在不同的社群之间转发数据，可以使用社群间的活跃节点作为社群之间数据传输的桥梁。其它较知名的基于社群的路由协议还有：SGBR[5]、CAOR[6]等。

携带者的社会关系极大影响着网络中节点的相遇情况，利用这些信息的优点在于它更能适应现实世界。dLife[7]利用设备携带者日常活动的规律帮助提高路由的效率。根据接触时间的持续情况，该路由协议关注不同层次的社会交往的轨迹。通过观察节点的日常活动预测节点每天在不同时段与其它节点的相遇情况，dLife充分利用这些社会交往规律进行路由决策。HiBOp[8]路由算法的主要思想是寻找与已知目的节点的上下文属性匹配程度不断增高的中间节点。一个节点与目的节点的匹配程度越高，意味着该节点与目的节点的相似度越高。其它较为知名的基于社会关系统的数据转发算法还有Fresh[9]、SMART[10]和HSFR[11]等。

以上分析表明，在移动社会网络中利用社会属性感知的方法有利于提高数据转发的性能。本文提出了一种基于社会感知的数据转发算法(EncoCent)，利用节点携带者的社会上下文信息计算节点之间的社会相似度，利用社会网络计算节点的介数中心度。如果数据发送节点不知道数据目的节点的位置，则数据被转发到中心度高的节点，从而有更多机会找到适合的中继节点，并有利于数据被高效的发送到目的节点。本文将利用两种社会属性来提高网络数据转发的性能，EncoCent结合社会相似度和介数中心度获得节点的社交强度和其在社会网络中的重要性，利用这些信息发送节点可以找到最优中继节点，从而提高数据转发的效率。

1 系统型模

1.1 社会相似性建模

研究表明[12]，具有相同兴趣倾向和相似社会特征的人们容易相聚在一起。根据这一规律，我们为每个节点设计了一个社会属性表，用于比较节点之间的社会相似性。通过社会相似性比较，可以找到更适合的中继节点，利用这些中继节点高效地把消息传递到目的节点。

(1)社会属性表

本文使用社会属性表描述节点携带者的社会上下文信息，这些信息主要包含设备携带者的信息(姓名、住址、工作单位、爱好等)，由社会属性ei与对应的取值vi组成，考虑到便于比较和隐私保护方面的因素，我们采用哈希函数对属性和值进行了处理，哈希函数H(ei,vi)采用MD5算法实现，并且把函数生成哈希值存入对应的社会属性表中。如表1所示，社会属性表由成对的属性(evidence)、值(value)、哈希值H(ei,vi)组成。

表1 社会属性表

表2描述了节点的社会属性表，每个节点具有相同的表项且按顺序排列，根据实际的应用场景赋予社会属性相应的权重以体现该属性的重要性。

表2 社会属性表举例

(2)社会相似性计算

当两个节点相遇时，它们可以互相交换信息，并且假设网络中的节点都是无私的，愿意为其它节点转发数据。通过匹配节点的属性表，可以计算两个节点的社会相似性。节点N的社会属性表中的属性(evidence)和对应值(value) 的集合记为N(e,v)；目的节点D的属性表中成对的属性和值的集合记为D(e,v)；节点N和目的节点D的属性值的交集记为M(e,v)，如式(1)所示

M(e,v)=N(e,v)∩D(e,v)

(1)

定义1 社会相似性度量：社会相似性度量是度量节点N与目的节点D的社会属性相似程度，表示为EncoSimN(D)，如式(2)所示。

网络中每个节点存在一个含有属性和对应取值的社会属性表，节点N和目的节点D之间的社会相似性计算，可以通过匹配两个节点的社会属性表来实现。社会相似性计算主要利用社会属性表(见表1)中的数据和属性的权值。本文设M(e,v)中属性权值Wm权的集合为W，目的节点D(e,v)中属性权值Wm节的集合为WD。则节点N和目的节点D之间的社会相似性EncoSimN(D)的计算方法如式(2)如下

(2)

则节点N相比于节点V，投递一个消息到目的节点D的社会相似性效用值EncoUtilN如式(3)所示

(3)

1.2 介数中心度建模

社会网络中一个节点的中心度表明该节点在社群中与其它节点联系的紧密程度。在分析一个节点在社会网络中所扮演的角色时，中心度是一个很有价值的度量。中心度也可以应用于其它类型的网络，包括引文网络、计算机网络和生物网络。中心性度包含：度中心度(degree centra-lity)、介数中心度(betweenness centrality)和接近中心度(closeness centrality)。

网络中一个节点的中心度是衡量该节点在网络结构上的重要性。通常情况下，中央节点有很强的连接其它网络成员的能力。介数中心度用于测量指定节点位于网络图中其它节点“中间”的程度，在各种中心度的测量中，其计算最为复杂。介数中心度定义为网络中包含指定节点的最短路径点所有最短路径的比例。因此介数中心度较高的节点可以或多或少地控制其它节点之间的数据交换。在移动社会网络中，我们认为有较高介数中心度的节点可以促进网络中其它节点之间的通信。介数中心度的计算方法如式(4)所示

(4)

式中：gjk是网络中连接节点pj和pk的最短路径长度，gjk(pi)是网络中连接节点pj和pk并且经过节点pi的最短路径长度。介数中心度可以用于测量一个节点在网络中其它节点链路上的桥接程度，衡量该节点对网络中信息流通的控制程度。具有较高介数中心度的节点，能够促进网络中节点间的通信，适合于被选作数据转发的中继节点。较高介数中心度的节点的桥接作用可以用于社群之间的通信，可以有效连接不同的社群。

在网络规模很大时介数中心度变得难以计算，因为需要完整的网络拓扑知识。因此，我们引入自我网络(ego networks)的概念。在没有完整网络拓扑信息的情况下，自我网络分析可以利用个体节点的本地邻居进行计算，利用自我网络替代移动社会网络，进行介数中心度计算是一种高效的，误差可接受的方法。文献[13]中Marsden详细地描述了利用自我网络计算介数中数度的方法，本文在下一节中采用了其计算方法。

1.3 转发效用值计算

转发效用值由社会相似性效用和介数中心度效用组成，采用归一化的权重来体现这两个因素的重要性。在移动社会网络中进行数据转发时，中继节点的选择是一个多目标决策的问题，通常希望选择的节点在投递消息给目的节点时具有最大效用值。在给目的节点D投递消息时，节点N的社会相似性效用(EncoUtilN)计算方法如式(3)所示。在计算介数中心度效用时，采用上面提到的文献[14]中的方法计算的社会网络的介数中心性，节点N的介数中心度记为CentN。在投递消息到目的节点D时，在节点N的介数中心度效用可以用如式(5)表示，其中节点V为网络中的相遇节点

(5)

转发效用值EncoCent(N)由两部分组成，分别是社会相似性效用EncoUtilN和介数中心度效用CentUtilN，计算方法如式(6)所示，根据实际情况，通过参数α和β来调整两部分对转发效用的影响，且α+β=1

EncoCent(N)=αEncoUtilN(D)+βCentUtilN

(6)

转发效用值为一种新的度量用于移动社会网络中的中继节点的选择，该度量结合社会相似性和介数中心度，用于预测节点N把消息成功投递到目的节点D的转发效用。度量值EncoCent(N)越大，节点N越适合作为中继节点。接下来本文将利用这个度量值设计高效的数据转发算法。

2 EncoCent转发算法

为提高移动社会网络中的数据转发效率，结合以上系统建模和转发度量，本文设计了一种轻量级的基于社会感知的数据转发算法EncoCent。

图1描述了EncoCent数据转发算法的数据转发。图中源节点S要把消息发送给目的节点D，由于当前网络不存在节点S到节点D的完整通路，此时，节点S把消息转发给中继节点N，节点N经过一段时间的移动后，又将信息发送下一中继节点V，节点V经过一段时间的移动后，与目的节点D相遇，最终将消息发送给节点D，完成数据投递过程。在整个转发过程中，如何选择适合的中继节点是算法要解决的关键问题。

图1 EncoCent数据转发

EncoCent的初始状态为源节点S中存在发往目的节点D的数据，中间节点N、V缓存中有大量空闲空间，且存在满足数据转发的CPU资源，目的节点D有足够大的空闲缓存空间接收相关数据。算法1描述了当节点N遇到节点V时，节点N的处理过程。接下来，我们分3个阶段详细说明节点N进行数据转发的过程。

算法1： EncoCent Forwarding Algorithm (procedures onNwhen it meetsV)

(1)uponreception of Hello messagehfrom nodeVdo

(2)ifVis a new neighbour ofN

(3)ifmsgQueuehas messages for destinationV

(4) deliver the messages toV

(5) delete the messages inmsgQueue

(6)endif

(7) exchange Node profile(np) and Encounters vector(ev)

(8)endif

(9)

(10)uponreception ofnpandevfrom nodeVdo

(11) updateCentUtilN(D) andCentUtilV(D)

(12)foralldestinationD∈msgQueuedo

(13) calculateEncoUtilV(D)

(14) calculateEncoCent(N)

(15) calculateEncoCent(V)

(16)ifEncoCent(V)

(17) addDtomfQueue(messages forwarding queue)

(18)endfor

(19)forallmessages ∈mfQueuedo

(20) send the messages toV

(21) delete the messages inN’smsgQueue

(22)endfor

(23)

(24)uponreception of transfer messages from nodeVdo

(25) add the messages toN’smsgQueue

(26) calculateEncoUtilN(D)

(1)当节点N收到节点V发来的HELLO报文后，节点N验证节点V是否是新的邻居节点。如果是新邻居节点，并且节点N的消息队列msgQueue中有发往节点V的消息，则节点N将该消息发送给节点V并在消息队列msgQueue中删除这些消息。然后两个节点交换社会属性表(np)和相遇矢量(ev)，相遇矢量描述了该节点与其它节点的历史接触信息。

(2)当节点N收到节点V的社会属性表(np)和相遇矢量(ev)后，相遇矢量(ev)用于更新介数中心度效用值，计算方法见式(5)；对于消息队列msgQueue中所有消息的目地节点D，计算节点V到节点D之间的社会相似性效用值，计算方法见式(3)，最后计算转发效用值EncoCent，如式(6)所示。如果节点V的转发效用高于节点N的转发效用，则把目的节点为D的消息添加到消息转发队列(mfQueue)，然后将该队列中的所有消息发送给节点V，并删除节点N消息队列中的相应消息。

(3)当节点N收到节点V发送过来的消息后，消息被存入节点N的消息队列msgQueue，然后根据该消息的目的节点信息，分别计算介数中心度效用值和社会相似性效用值并缓存在节点中。

基于以上算法的设计原则，本算法的关键任务是为路由的每一跳选择最佳转发节点，从而为移动社会网络的分布是数据转发决策提供支持。

3 性能评估

为了评估EncoCent算法的性能，我们进行了大量的仿真实验，并将仿真实验结果与dLife、Fresh、Prophet这3种著名算法进行了比较分析。进行对比分析的4种算法都利用了网络节点的社会上下文信息，并且通过单拷贝的方式转发消息，从而使得对比分析更有说服力。

3.1 参数设置

仿真实验采用移动社会网络和机会网络中广泛使用的ONE(opportunistic network environment)仿真平台[14]。为了使用仿真环境尽可以地接近真实场景，本文采用MIT实际数据集[15]作为网络节点移动的轨迹数据。MIT实际数据集(MIT reality data)反映了MIT校园内移动节点的接触轨迹。该数据集中的节点是由97个MIT的学生和职员组成，他们每个人携带型号为Nokia 6600的智能手机，这97个节点在校园内活动形成了一个移动社会网络。该数据集收集了连续9个月的节点接触情况的监测数据，节点之间利用蓝牙技术进行通信。

为了简化问题的分析，我们假设每个节点内存在社会属性表和对应的权重集合，在本文中并不讨论如何获取这些信息。本文认为在该场景中效用值EncoUtilN和效用值CentUtilN具有同等重要的作用，因此将α和β的值均设为0.5。其它仿真参数见表3。

表3 仿真参数设置

每个仿真实验运行30次，然后分别收集统计数据，取平均值。在对各算法的实验数据进行统计分析时，我们采用如下统计量：投递比率(delivery ratio)、投递开销(delivery cost)、路由效率(routing efficiency)，和平均时延(average latency)。投递比率是成功到达目的节点的数据分组数与总共生成数据分组数的比值；投递开销是未成功投递的消息副本总数与成功投递到目的节点的消息总数的比值；路由效率是投递比率与投递开销的比值；平均时延是数据分组被创建到成功到达目的节点的平时时间。

3.2 仿真结果分析

在相同的仿真环境下，本文将EncoCent算法与其它3种经典的相关算法进行了对比实验。实验中，假设每个节点有足够大的存储空间来存储需要转发的消息，节点之间的带宽足够大使得节点相遇时足以完成数据的交换。图2描述了4种算法随时间变化时投递比率的变化情况，EncoCent算法表现较好，紧次于投递比率最高的Fresh算法，在第20天时投递比较达到76%。Prophet算法在投递比率方面表现最差。

从图3可以看出，本文提出的EncoCent算法具有最小的平均投递开销。相比于dLife算法减少了约20%的投递开销。由于Prophet算法需要处理大量的历史相遇信息，因而其投递开销最大。虽然在4种算法中，Fresh算法拥有最高的投递比率，但是该算法在投递开销方面却表现较差。

图2 投递比率

图3 投递开销

图4描述了4种算法的路由效率，从图上可以看出，EncoCent算法具有最高的路由效率，分别比dLife，Fresh和Prophet算法提高了15%，78%和124%。这是因为，EncoCent算法在进行中继节点选择时，不仅考虑了节点携带者的社会相似性对节点移动的影响，而且还充分利用了节点介数中心度在数据转发的桥梁作用。其它算法只考虑了某个单一方面的因素，因而只是在网络性能的某个统计量方面有较好的表现。

图4 路由效率

图5描述了随着仿真时间的变化，网络平均时延的变化情况。从图中可以看出在4种算法中，Fresh算法具有最高的平均时延，可能是因为其仅仅是利用了网络节点间相遇的历史信息，而没利用节点的社会上下文信息，从而导致算法的自适应性不够。相比于Prophet算法，dLife和EncoCent的平均时延分别减少了16.6%和19.7%。这是因为dLife和EncoCent算法在选择中继节点时都利用了节点携带者之间的社会关系，因而在平时的时延方面表现更好。

图5 平均时延

本文提出的算法在数据转发过程中充分考虑网络节点携带者的社会上下文信息，通过研究节点的社会属性，掌握网络节点的移动规律，对这些移动规律的应用，能大大提高数据分组的投递效率。为了使用数据能尽快地，高效地送到目地节点，EncoCent算法充分利用了社会相似性和介数中心度两个因素选择最优中继节点。经过上述的仿真实验和数据分析，验证了EncoCent算法的有效性。

4 结束语

在移动社会网络中，节点携带者的社会上下文信息对于辅助网络中的数据转发具有非常重要的意义。本文提出的EncoCent算法结合社会相似性效用和介数中心度效用分别获取节点间的社交强度和中心性，基于这两个因素本文提出了一种数据转发度量EncoCent，为最优中继节点的选择提供理论依据。最后本文采用ONE仿真平台进行了大量的仿真实验和分析，验证本文提出的算法的有效性和优越性。本文的研究能促进移动社会网络中数据转发的效率与智能化，并为以人为中心的智能网络和普适计算的研究提供理论参考和技术支持。