基于多维特征分析的移动社会网络消息传输

朱子青 曹玖新 周 涛 胥 帅 马 卓 刘 波

(东南大学计算机科学与工程学院 南京 211189) (计算机网络和信息集成教育部重点实验室(东南大学) 南京 211189) (zzqxztc@seu.edu.cn)

基于多维特征分析的移动社会网络消息传输

朱子青 曹玖新 周 涛 胥 帅 马 卓 刘 波

(东南大学计算机科学与工程学院 南京 211189) (计算机网络和信息集成教育部重点实验室(东南大学) 南京 211189) (zzqxztc@seu.edu.cn)

基于延迟容忍特征，移动社会网络采用“存储—运载—转发”模式在节点之间进行消息传输.如何选定合适的中继节点进行消息的高效传输是当前研究中备受关注的热点问题.从不同的角度对网络中的多维社会特征展开分析.首先，根据节点间的交互关系，确定节点间社会关系模型；其次，依据网络拓扑给出了邻居集合和本地社区的定义，提出了一种移动社会网络的本地社区划分方法，进而建立了节点间的社区关系；然后，基于节点间的行为特征给出了节点活跃度定义，通过PageRank算法获得节点的多维属性特征PR值，并利用PR值给出节点间传输值，从而获得节点的不同传输效用值.在此基础之上，综合考虑节点社区关系和节点的不同传输效用值，设计并实现了移动社会网络的消息传输算法.实验表明，算法在传输成功率、传输冗余率、平均延时等多个方面具有优势.

移动社会网络；延迟容忍网络；社区划分；PageRank算法；动态网络

随着手机等移动设备的大量普及，利用移动设备建立的连接进行设备之间的直接信息传输引起了广泛的关注.移动社会网络(mobile social network, MSN)是由人随身携带的移动设备构成，具有社会网络的社会性和移动通信网络的移动性.如何解决MSN网络中的消息传输和共享一直是人们研究的热点问题.在网络中，设备会随着人移动，由于人的移动性，即人们之间的相遇时间间隔与相遇频率等因素会影响设备间消息的传输成功率或者传输延时.当前大量的研究表明，随着人移动的设备在移动过程中存在着明显的移动规律.文献[1]通过对大量的实验数据进行分析，得出网络中的移动设备之间相遇间隔时间服从幂律分布的结论.文献[2]则指出人们所携带的网络节点之间的相遇间隔时间在某时间阈值范围内服从幂律分布，而超过该阈值则服从指数分布.文献[3-4]也对随着人移动的设备间相遇规律开展了研究，表明网络中的节点移动行为确实存在基于社会行为的移动规律.

如何利用移动社会网络中的社会规律，分析节点之间的社会关系特征，从而设计消息传输算法是一个重要的研究问题.

本文综合考虑移动社会网络中节点所存在的多维社会特征.基于网络的局部拓扑和交互关系设计了本地社区算法；根据节点的移动行为规律提出了节点的社会活跃度概念；利用PageRank算法使节点之间根据传输状况特征的不同进行相互评价，从而获得节点的多属性特征PR特征值，并给出节点间传输值的定义；最终，设计实现了移动社会网络消息传输算法.

1 相关工作

近年来，业界对延迟容忍网络(delay tolerant network, DTN)[5]消息传输已经开展了大量研究工作.有基于传统路由转发策略扩展改进的MED，EDAQ，LP，PLSR路由[6]；基于多副本传染型传输策略改进的Spray系列路由[7-8]、利用路由节点概率效用值进行传输的Prophet路由[9]；结合新型智能优化算法[10-11]的路由.传统DTN路由算法的设计都没有涉及网络中存在的社会规律.因而在移动社会网络环境下，开展了很多结合社会网络规律设计的基于社会属性(social based)的路由算法的研究.

Daly等人[12]利用复杂网络中度(degree)、接近中心度(closeness centrality)、介数中心度(betweenness centrality)、节点间相似性(similarity)等特性对网络中的社会特征进行分析，提出了SimBet算法，实现路由消息传输.Pan等人[13-14]分析了网络中存在的社区结构，提出了BubbleRap算法，消息依据节点间的社区关系进行传播，提高了网络中消息的传输性能.Wu等人[15]依据网络中移动节点所存在的“Home”属性，提出了类似Spray路由机制的Homing Spread算法，可以有效提高消息传输性能.Li等人[16]分析了节点之间的相遇频率、每次平均通信时间、历史通信总时间和平均最短分离时间对节点之间交互紧密程度的影响，进而从中选择合适的指标建立节点间社会关系.而Gao等人[17]则着重研究了节点之间的瞬时连接对消息传输的作用.

以上研究所具有的共同特点在于网络中消息传输算法所利用的网络社会关系特征都是通过节点之间的移动交互“探索”得到的，被称为探索型社会网络(detected social networks)[18].也有一部分研究不通过节点之间的“探索”获得社会关系.而是直接利用网络中节点之间已经存在的社会连接关系分析节点间社会特征，此类型的移动社会网络被称为自我宣称型社会网络(self-reported social networks)[18].在移动社会网络中，有文献利用社会关系问卷调查、社交网络朋友关注等已知的社会关系来分析网络中的社会特征，进而设计消息传输算法.如文献[19-20]利用了用户线上Facebook的社交关系建立了社会关系拓扑，而文献[21]则是利用INFOCOM2006的与会人员填写的问卷调查建立已知的社会关系网络.

然而现有的相关研究工作仍然存在一些不足：

1) 当前一些研究[21]是建立在整个网络中节点之间社会关系已经确定的基础之上，对全局网络的社会属性特征进行分析，进而设计中继节点选择算法.而移动网络的特性决定了网络中各节点只能动态地获得局部的网络拓扑结构或部分节点之间的关系，因此应该更注重节点的局部动态连接关系分析.

2) 很多学者[14]对网络中存在的社区关系展开了研究.然而社区之间的划分是建立在网络中节点全局关系已完全建立的基础之上.这不适用于移动社会网络的局部动态连接情况.在移动社会网络中，节点动态地获取周围节点的连接信息，通过局部的网络信息，和周围节点建立社区关系.一部分学者[16,21]在移动社会网络的环境下，对局部社区探测进行了探讨.但是通过局部信息建立的本地社区(local community)只关注社区关系形成的过程，没有关注时间流逝之后节点社区的老化问题.

3) 社会网络中存在的幂律性特征，例如网络中度数小的节点要比度数大的节点数量高很多，所以在传输时，只考虑节点自身的度指标会产生传输数据向某些节点过度集中的问题.这造成了消息传输的不公平性，个别节点上的消息负载相对过高.社会网络领域的研究中就发现小度数节点或者弱连接对信息在网络中的传播有重要作用[22].Ioannidis等人[23]便研究过如何利用网络中弱社会关系对消息进行路由传输.节点自身不活跃而邻居很活跃，节点也可以将持有的消息扩散出去.因此，应该应用一种更科学的指标来使消息向“非中心性”节点传输.考虑节点在传输时，节点自身的传输状况对周围节点的影响.

2 节点社会关系模型

由于节点间相遇的间断性，移动社会网络的网络拓扑会不断改变.本文将节点间不断变化的节点移动相遇关系转变为相对稳定的社会关系.然后对网络中存在的社会特征展开分析.

在移动社会网络中，社会关系紧密的节点，节点之间也会进行频繁的通信，因而可以用节点间的通信累计时间表示节点间的社会关系.本文将移动社会网络建模为具有多属性的节点无向网络图，其形式化描述如下：

给定Gt(V,E),其中V是网络中的节点集合，E为网络中2个节点之间社会关系连接边的集合，t表示网络在一段时期的状态.网络中节点u，v之间的边关系权重表示为wt(u,v)，表示为节点u，v之间在一段时期t的累计通信时间.每个节点与其他节点的相遇频率、相遇时间间隔等特征，作为节点集合V中节点所具有的自身属性.

3 本地社区发现

携带消息的节点在网络中根据和其相遇节点的社区关系，选择不同的消息路由策略.因此本文参考文献[24]的思想提出改进的本地社区探测算法LAC(local aging community).

3.1 邻居集合和本地社区

为便于描述，本文定义相关的概念.

定义1. 节点直接邻居关系.是指两相遇节点之间的累积相遇时间超过设定的阈值，则这2个节点之间形成直接邻居关系，体现了节点之间通信连接的紧密性.

对于一个给定的节点u，其直接邻居的节点集合可形式化表示为：

Nu={v|wt(u，v)>Tth,v∈Mu}，

其中，wt(u,v)表示u与v之间的边权重；Tth表示邻居关系时间阈值；Mu表示和节点u相遇过的节点集合.

定义2. 节点间接邻居关系.是指两相遇节点没有形成直接邻居关系，但是2节点之间的直接邻居重合程度超过设定阈值，则这2个节点之间形成间接邻居关系，体现了节点之间再通信的可能性.

对于一个给定的节点u，其间接邻居的节点集合可形式化表示为：

其中，Tth为设定的时间阈值；Nu和Nv分别表示u与v的直接邻居节点集合；Mu表示和节点u相遇过的节点集合；λ为重合度设定阈值.

定义3. 节点本地社区.是指和节点同处一个社区的节点组成的集合.其包括所有直接邻居节点和间接邻居节点的集合，以及节点本地社区在形成过程中，两相遇节点互相合并本地社区时，不存在直接邻居和间接邻居关系的节点.

对于一个给定的节点u，其本地社区的成员集合可形式化表示为：

定义4. 节点间接社区关系.是指两相遇节点之间的本地社区满足条件合并后，新本地社区中不属于2个节点原本地社区的节点.2个节点分别和不属于原本地社区的节点形成节点间接社区关系.节点间接社区关系，体现了节点之间形成社区或者相遇通信的可能性.

对于一个给定的节点u，其节点间接社区成员集合可形式化表示为：

3.2 本地社区发现算法

本文给出适用于移动社会网络的本地社区划分算法LAC，其基本思想是：

1) 本地社区形成过程.节点的直接邻居关系和间接关系节点首先成为其本地社区成员；然后节点间在每次相遇过程中，通过本地社区的重合条件进行合并，产生新的本地社区成员.

2) 本地社区维护过程.节点首先检测其直接邻居关系节点是否老化，如果节点的直接邻居关系节点出现老化，则检测节点的间接邻居关系节点；最后检测和节点存在间接社区关系节点是否老化.因而算法流程包括本地形成和社区维护2个过程.

过程1. LAC本地社区形成.

过程1和过程2分别表示LAC算法中本地社区形成和随时间流逝的维护过程.其中，过程1的行⑤～⑦表示节点间的直接邻居关系形成.行⑧～表示节点间的间接邻居关系形成.行～表示节点的本地社区合并，并产生存在间接社区关系的节点.而过程2中，行④～⑧表示随时间流逝，节点之间的边权重改变，引起节点间的直接邻居关系老化；行⑨～表示随时间流逝节点间的间接邻居关系老化；行～表示节点的本地社区中间接社区关系节点被删除；行～进行DO WHILE循环检测，是因为间接社区关系节点在每次社区合并过程中，会使新的间接社区关系节点加入，因而每次本地社区成员改变了，要循环检测其余存在间接社区关系的节点是否应该被删除.

对于LAC的算法时间复杂度，过程1的时间消耗主要集中在行④、行⑧和行，即节点u判断相遇节点v是否存在于其本地社区以及判断邻居或者社区的重合度.节点u本地社区成员数目为|Cu|，显然都要比节点的邻居数目要大，因而算法时间复杂度为O(|Cu|).而过程2的时间消耗主要集中在行①、行④、行⑨和行的节点集合遍历，和行⑩和行，检测原先条件满足时所记录的重合集合Nu∩Nv，Cu∩Cv的状态.而存在间接社区关系的节点，在每轮维护中，某种情况下可以通过DO WHILE循环检测依次全部删除，假设节点u的间接社区成员数目为，则其为递减数列因而最坏情况下，算法时间复杂度为，一般情况下相遇过的节点数量|Mu|要比都要大，因而时间复杂度为O(|Mu|).

4 节点传输效用值

进行消息传输时，节点在判断和相遇节点的社区关系基础上，通过考虑相遇节点的传输效用值，在社区间和社区内选择合适的中继节点.

4.1 节点社会活跃度

在网络中相遇节点数量多的节点，其本身具有更高的消息传播可能性.同时，节点和周围节点相遇比较频繁，也能增加节点传播消息的能力.本文利用节点的相遇节点数目和与其他节点相遇时间间隔来描述节点的活跃程度，即社会活跃度(social activity, SA)，其定义为：

SA(u)=|Mu|a-δTu，

(1)

其中,|Mu|表示节点u在网络中相遇过的节点数量,而Tu为一段时间内节点u和所有相遇过节点的最近相遇间隔时间的平均值,δ为平滑因子.

如文献[1-2]所指出的，基于节点之间相遇时间间隔的幂指特性分布，只有很少一部分节点的相遇时间间隔会很大.所以本文将节点社会活跃度定义为关于时间的幂函数形式，当和其他节点相遇时间间隔变大，其社会活跃度也会快速下降.

4.2 节点多维属性特征PR值

当消息在节点之间进行传输时，为了避免消息向个别中心节点过度聚集现象，本文使用新的指标来改进消息的传输性能.网页排名的PageRank算法[25]使网站的重要度得分由自身和其他网站共同决定.

4.2.1 多维属性特征分析

本文采用PageRank算法的思想建立节点的传输评分特征值.综合网络中节点的3种属性特征展开分析.

1) 节点的社会活跃度属性

对于节点的社会活跃度属性，本文规定低活跃度的节点向周边高活跃度的直接邻居节点给予评分，反之，不评分.因而可以抽象为如图1所示的有向图.

Fig. 1 Node social activity relations图1 节点社会活跃度关系

节点间的评分函数为：

A(v,u)×PR(v)，

(2)

其中，PR(v)为节点v的PageRank值，A(v,u)为节点v对直接邻居节点u活跃度权重比例分配计算函数：

(3)

Fig. 2 Node interaction frequency relations图2 节点交互频率关系

节点依据周围直接邻居节点的社会活跃度和其自身的社会活跃度关系给予不同的评价权重.得分比较高的节点，表示其周围直接邻居都认为此节点有更高的社会活跃度.

2) 节点之间的相遇频率属性

对于节点和其他节点的相遇频率属性，可以抽象为如图2所示的有向图.

每个节点通过与周边节点的交互频率向直接邻居给予评分，周围邻居出现频率越高，则对其评分权重越大.本文给出节点按照相遇频率得到的周围邻居评分函数：

Pv(u)×PR(v)，

(4)

其中，Pv(u)为节点v相遇其邻居节点u的频率.

依照节点周围直接邻居出现的频率，节点对周围直接邻居节点出现的不同频率，给予不同的评分权重.评分比较高的节点，表示其周围邻居节点都认为该节点经常出现，或者节点本身和某一评分较高的节点经常相遇.

3) 节点的直接邻居数属性

对于节点在网络中的邻居数属性，即指节点的周围的直接邻居数量，如图3所示.本文给出节点评分函数：

(5)

其中，Nv表示节点v的直接邻居.

Fig. 3 Node direct neighbor relations图3 节点的直接邻居关系

依照节点周围直接邻居的数量，节点对每个邻居均等地给予评分.评分高的节点，表示获得了很多节点的评分，或者此节点和高评分的节点存在直接邻居关系.

最后，本文综合考虑不同方面的特征分析，给出基于PageRank算法的节点u得分特征值函数：

(6)

其中，α+β+γ=1，d为PageRank中的衰减因子.

4.2.2 节点PR值计算流程

对于PR值的计算迭代简单实例如图4所示.计算过程中，节点A需要接收节点B和C传来的PR值分量才进行迭代计算.同理，节点B，C也要分别接收和传输邻居的PR值分量才能完成自己的PR值计算.

Fig. 4 Simple network topology图4 简单网络拓扑示意图

因此，本文给出移动社会网络下的PR值计算规则：

1) 每一个节点在传输完成自己的所有出度边PR值分量和接收其他邻居节点PR值分量后，更新自己的PR值.

2) 如果相遇节点之间的PR值和上次相遇时相同，则不进行节点之间的PR分量值传输.

在移动网络的环境下，节点和直接邻居关系节点在已经建立连接情况下，可以完成PR值每一轮计算，而每个节点PR值和网络拓扑有关.因而当网络拓扑越稳定，节点之间相遇越频繁，连接越持续，则会向节点PR值的收敛稳定值趋近得越快.

4.3 节点间的传输值

为了使消息在网络中的消息路由传输过程中具有目的性和方向性，减少传输开销，本文分析PageRank算法分量的传输过程.如图4所示，本文假定节点A，B，C的PR值当前都为1，因子d=0.85.出度边的权重都为1.

假定节点B和节点A，C经常相遇，而节点C又经常和节点A经常相遇，本文分析节点B的PR值传输过程.

那么当节点B和节点A相遇时，节点A依据出边权重向节点B传输PR值分量0.425.

当节点B和节点C相遇时，节点C获得B传来的PR值分量0.425.然后，节点C再和节点A相遇，节点C会依据自身出边权重向节点A传输节点B的PR值分量0.361.

节点A将保留每次获得的更大的传输值，作为节点对其的传输值.

因而在原始PageRank公式上定义节点u获得节点v的传输值函数为：

(7)

其中，path(v,u)表示节点v对节点u的所有可能的传输路径，m表示传输路径上的一点，O(m)表示节点m的出度边的集合，|L|表示其中一条路径的长度.

式(7)中O(m)出度边集合在本文中由有向评分权重函数代替,所以本文的基于PageRank算法的节点v对节点u的传输值函数为：

(8)

在移动网络环境下，节点v每次将自己当前的PR值按照评分权重传输给周围的直接邻居，直接邻居记录这些节点v的PR值分量，然后再将这些分量继续传输给自己的直接邻居.因而任意一个节点会比较所有从邻居节点获得的节点v传输值，选取最大的值作为节点v对其的传输值.

5 移动社会网络的消息传输算法

本文消息传输算法的基本思想是通过节点之间的社区关系选择不同的传输策略，利用网络的社会特征，在节点社区内和社区间选择合适的中继节点.从而防止社区内部消息在社区间的传输以及减少跨社区的消息在非目的节点社区内部的传输，使消息传输更有方向性、减少冗余的消息传输.

5.1 传输策略的选择

本文算法根据消息传输的目的地节点和相遇节点之间的社区关系，选择不同的路由策略.当节点u携带目的地为节点d的消息，和节点v相遇时，节点u会根据和相遇节点v的不同社区关系，同时考虑节点u，v之间的社会活跃度、消息目标节点的传输值等特征选择不同的路由传输策略.具体策略如下：

1) 如果消息携带节点u及相遇节点v都不和消息目的地节点d处于同一社区，那么将消息传输到社会活跃度高的节点或者PR值和消息目标节点d的传输值都很高的节点，从而增大发现和目的地节点d处于同一社区的节点机会.

这里PR值仍然需要和传输值组合在一起作为节点选择的依据，这是因为节点的PR值可以由直接邻居节点的传输值组成，如对于节点u：

(9)

那么：

(10)

因而，节点传输值无法完全体现出节点自身的PR值特征.

2) 当消息携带节点u及相遇节点v都和目的地节点d处于同一社区，表明消息已经很接近目的地节点，则将消息向PR值和传输值都很高的节点传输.

3) 当消息携带节点u不和目的地节点d节点在同一社区，而相遇节点v和目的地节点d处于同一社区，那么就将消息传输给节点相遇节点v.

4) 当消息携带节点u不和目的地节点d节点处于同一社区，而相遇节点v和目的地节点d也不处于同一社区，那么就不进行消息传输.

5.2 算法流程

消息传输算法综合考虑节点社区关系和节点的传输效用值，从而实现消息传输.其具体算法实现如下：

算法1. 消息传输算法.

算法1中，行③～⑦表示节点携带消息和相遇节点以及目标节点在同一社区内的传输情况;行～表示节点携带消息和相遇节点都不处于同一个社区的传输情况;而其他行，则表示消息优先将消息传输给和目标节点同属一个社区的相遇节点，否则不进行传输.

对于算法1的时间复杂度，其时间消耗主要集中在行③、行⑧和行，即节点u和相遇节点v消息目的节点d是否处于同一社区.假设节点u和节点v的本地社区成员数目分别为|Cu|和|Cv|，因而算法时间复杂度为O(|Cu|+|Cv|).

显然算法的有效工作依赖于节点相关特征属性的计算和本地社区的发现.因此在网络当中，每当2个节点相遇时，都要优先互相交换自身特征属性信息和获得的其他节点特征属性信息.

6 实验与分析

为了评估算法的性能，本文实验采用仿真工具ONE[26]，此仿真工具是专门为评估DTN网络路由和算法协议设计的.本文将所提出的消息传输算法与Epidemic算法、Prophet算法、BubbleRap算法、Simbet算法在相同实验环境下的传输性能进行了比较.其中,Epidemic算法对任何相遇的节点都进行消息传输,在不考虑缓存大小的理想情况下，能够获得最好的传输效果，本文把Epidemic算法作为一个性能比较的上界;Prophet算法是依照节点相遇概率进行消息传输的方法.而BubblRap算法和Simbet算法都是典型的带有社会属性的消息传输方法.

6.1 实验数据

本文使用INFOCOM2005和INFOCOM2006数据集验证算法在真实场景中的性能.

1) INFOCOM2005.该数据集采集自分发给2005年参与INFOCOM学生研讨会的大概50名学生的移动设备.这些参与者属于不同的国家、区域或者研究课题组.

2) INFOCOM2006.该数据集采集自分发给2006年参与INFOCOM会议的与会人员携带的移动设备.人数相比INFOCOM2005更多，超过80人.2组数据集的一些基本特征如表1所示.数据集的用户活动范围小、记录周期短，但是相比其他的数据集，INFOCOM2005和INFOCOM2006都具有节点连接发生频率高的特点.

Table 1 Data Basic Information表1 数据基本信息

6.2 参数设置

本文对算法1中的每个阈值参数进行选择.根据人类生活规律，人们会在一段时间内进行周期性的活动，这一段时间可以是以每周(7 d)作为基础单元，按照每月(约4周)、每年(约48周)进行一段时期的固定规律活动，而在这一段时间之后人的行为可能会改变.而INFOCOM2005和INFOCOM2006数据集的数据记录只有3 d左右，所以本文把每天人们的日常活动分为上午、下午、夜晚、午夜4个时段[13](各6 h).以每个时段作为基础单元，以每个基础单元的倍数作为一段时期活动的周期时间单元.

对于INFOCOM2005和INFOCOM2006数据集，本文认为如果2个节点同时出席听取同一场学术报告，这2个节点更有可能具有“社会邻居”关系[13].考虑在进行学术报告时大家基本是不动的，所以本文把上午或下午时段内，学术报告会时长10 800 s(3 h)作为INFOCOM2005和INFOCOM2006数据集的邻居关系建立阈值.

本文观察INFOCOM2005和INFOCOM2006数据集的节点对通信间隔的累积分布log-log图像，如图5所示.可以发现，在43 200 s(2×6 h)之前呈现明显的幂率分布特征.通过如图6的log-line图像可知，43 200 s(2×6 h)之后，节点对的通信间隔大小分布由幂率分布特征转变为指数分布特征.也就是说，固定的活动规律有所改变.所以对于算法1在实验中的参数，邻居关系移除的时间阈值和平滑因子都以12 h作为选取点.

Fig. 5 Node contact interval time of log-log complementary cumulative distribution图5 节点通信时间间隔互补累计分布log-log图

Fig. 6 Node interval time of log-line complementary cumulative distribution图6 节点时间间隔互补累计分布log-line图

本文认为节点属性的多个方面是同等重要的，因而PR特征值中的参数α,β,γ分别取为13.对本地社区发现算法中的相关参数λ、σ则参考文献[24]中的实验选取0.8.因而本文采用如表2所示的实验参数.

Table 2 Selection of Threshold Parameter表2 阈值参数的选取

6.3 仿真场景

本文在实验中采用50 MB大小的缓存，每45～150 s随机产生一个5 KB左右大小的信息数据包，由网络中某一节点随机向另外一个节点发送.

6.4 算法评估

本文用以下指标来评估相关算法的性能.

1) 传输成功率(delivery ratio).算法的首要目标就是获得更高的传输成功率.消息成功率就是在消息整个传输的过程中目标节点成功接收到消息数与在源节点所传输的所有消息数比值，反映了传输成功率.

2) 传输冗余率(overhead ratio).冗余率定义为每当成功接收一个消息数据包所需要的额外传输次数.此参数反映了消息的冗余传输次数.节点在移动社会网络中进行间歇性通信，节点之间的相遇机会有限，能以越少冗余传输次数完成消息传输，说明算法性能越好.同时，对于复制型的算法，节点会在每次传输时创建消息副本，冗余传输次数过多，会产生更多的消息副本，影响网络传输性能.

传输冗余率=

3) 平均延时(average delay).消息延时是指节点发送的消息从源节点成功到达目标节点所需的时间.平均消息延时体现了网络的实时性，同时也间接反映了整个网络的消息流通是否正常.虽然在延迟容忍网络环境下，无法像传统网络那样要求消息的传输延时，但是消息的传输延时比较低时，节点可以尽早释放缓存中的数据，提升网络的传输性能.

Fig. 7 Message delivery ratio图7 消息传输成功率

6.5 结果分析

在仿真过程当中，本文通过改变每次实验的不同生存时间(time to live, TTL)来比较各个路由算法的消息传输成功率、网络传输冗余率、传输平均延时.

本文首先对比每一个算法的消息传输成功率.如图7所示，随着TTL增加，消息传输的成功率开始提高.这是因为消息的TTL增大使数据信息在缓存中驻留的时间更长了.因此携带消息的节点更有可能和目的地节点相遇.

Fig. 8 Message overhead ratio图8 消息传输冗余率

很明显，相比带有社会属性的SimBet算法和同样使用社区发现策略的BubbleRap算法，本文提出的SocialEvalution算法的传输成功率要更好.相比SimBet在INFOCOM2005和INFOCOM2006数据集中，最高的成功率提升了约6.8%和29.3%，相比BubbleRap算法提升了约3%和4%.从实验可知，SimBet算法非常不适应现实稀疏特征的数据集，其传输成功率很低.而本文算法和Prophet算法的传输成功率比较接近，甚至在INFOCOM2005的数据集中，本文的SocialEvalution算法和Prophet算法都非常逼近Epidemic算法的发送成功率.

对于实验中每个算法的传输冗余率，从图8中可以观察到，因为Epidemic算法的无差异洪泛性传输，节点之间的冗余中继传输次数很多.在消息的传输过程中，网络中的大多数节点都对消息进行了传输.因而2个数据集中，Epidemic算法的消息冗余中继传输次数非常高，而SimBet算法的传输冗余率在2个数据集的仿真实验中都比较小，但是实验结果表明其相比其他算法的传输成功率要低.Bubble算法的传输冗余率要比本文的算法和Prophet算法的传输冗余率要小，但是其传输成功率相比本文算法要低.

对于算法的传输冗余率，显然携带消息的节点直接等待消息传输的目的节点出现的传输冗余率是最低的，但是这种模式的传输效果显然是最差的.如果消息通过一些中继节点更快地被传输到目的节点，那么消息在传输过程中的中继节点很多会造成其传输次数增多，这将导致算法的冗余率升高，但是却可以保证消息传输的延时和传输成功率.因而还需要比较各个算法的平均延时.

Fig. 9 Message average delay图9 网络传输平均延时

本文的SocialEvalution算法避免消息向个别节点过于集中传输，节点会选择其他的候选节点作为消息中继节点，因而这会造成消息的冗余传输次数增加.所以SocialEvalutio算法的冗余率比SimBet和Bubble都要高，但是本文的SocialEvalution算法显然要比Prophet算法冗余率要低，而且算法的传输成功率和Prophet相比没有下降.

如图9所示，实验表明SimBet算法和BubbleRap算法的平均传输延时很高，而Epidemic算法的消息传输的洪泛策略使消息的平均延时最低.INFOCOM2005数据集中，本文SocialEvalution算法的发送延时和Prophet算法很接近.而在2个数据集中，当消息的TTL大于12 h时，SocialEvalution算法的消息平均延时相比Prophet算法的平均延时出现升高.

这种结果的出现是由于SocialEvalution中如6.2节实验设置部分所述，将邻居关系移除阈值设定为12 h，而12 h之后社区算法删除了一些老化的社区成员节点.在实验中，这些被删除的节点可能依然会偶尔和消息携带节点产生相遇，进而有机会获得消息，并将消息传输给目的节点，这种情况降低了Prophet算法的传输平均延时.

7 总结与展望

本文基于建立的网络拓扑设计了本地社区算法；根据节点的移动行为规律提出了节点的社会活跃度概念；利用PageRank算法计算节点的多属性特征PR特征值，并给出节点间传输值的定义；在此基础之上，设计和实现了移动社会网络消息传输算法；最后在真实数据集合上验证本文消息传输算法的性能.实验表明本文的路由算法相比其他算法具有更好的传输效果.

在实际环境中，网络中的移动节点移动方式复杂多变.移动社会网络的消息传输研究难点，便在于如何挖掘和利用节点之间潜在的行为模式信息，进而实现消息的路由传输.因为网络本身所具有的社会性特征，利用网络中存在的社会特性可以预测节点的移动行为，改善网络传输性能.

未来计划更加深入地分析消息在节点间的传输特性，研究节点之间存在的社会关系，从而探索更好的社区发现算法和深入挖掘节点的社会特征.

[1]Chaintreau A, Pan Hui, Crowcroft J, et al. Impact of human mobility on opportunistic forwarding algorithms [J]. IEEE Trans on Mobile Computing, 2007, 6(6): 606-620

[2]Karagiannis T, Boudec L J Y, Vojnovic＇ M, et al. Power law and exponential decay of inter contact times between mobile devices[C] //Proc of the 13th Annual ACM Int Conf on Mobile Computing and Networking (MobiCom’07). New York: ACM, 2007: 183-194

[3]Passarella A, Conti M, Boldrini C, et al. Modelling inter-contact times in social pervasive networks[C] //Proc of the 14th ACM Int Conf on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWi M’11). New York: ACM, 2011: 333-340

[4]Tian Ye, Li Jiang. Heterogeneity of device contact process in pocket switched networks[C] //Proc of the 5th Int Conf on Wireless Algorithms, Systems and Applications(WASA’10). New York: ACM, 2010: 157-166

[5]Fall K. A delay-tolerant network architecture for challenged Internets[C] //Proc of the 2003 Applications, Technologies, Architectures and Protocols for Computer Communications (SIGCOMM’03). New York: ACM, 2003: 27-34

[6]Jain S, Fall K, Patra R. Routing in a delay tolerant network[C] //Proc of the 2004 Applications, Technologies, Architectures and Protocols for Computer Communications(SIGCOMM’04). New York: ACM, 2004: 145-158

[7]Spyropoulos T, Psounis K, Raghavendra C S. Efficient routing in intermittently connected mobile networks: The single-copy case [J]. IEEE/ACM Trans on Network, 2008, 16(1): 63-76

[8]Spyropoulos T, INRIA, Psounis K, et al. Efficient routing in intermittently connected mobile networks: The multiple-copy case[J]. IEEE/ACM Trans on Network, 2008, 16(1): 77-90

[9]Lindgren A, Doria A, Schelen O. Probabilistic routing in intermittently connected networks[J]. ACM SIGMOBILE Mobile Computing and Communications Review, 2003, 7(3): 19-20

[10]Yang Zhenguo, Huang Liusheng, Xiao Mingjun, et al. ACR: An ant-colony-based routing in delay tolerant networks[J]. Journal of Computer Research and Development, 2012, 49(12): 2501-2514 (in Chinese)(杨振国, 黄刘生, 肖明军, 等.一种基于蚁群算法的容迟网络路由策略[J]. 计算机研究与发展, 2012, 49 (12): 2501-2514)

[11]Wang En, Yang Yongjian, Li Li. Game of life based congestion control strategy in delay tolerant networks[J]. Journal of Computer Research and Development, 2014, 51(11): 2393-2407 (in Chinese)(王恩, 杨永健, 李莅. DTN中基于生命游戏的拥塞控制策略[J]. 计算机研究与发展, 2014, 51 (11): 2393-2407)

[12]Daly E M, Haahr M. Social network analysis for routing in disconnected delay-tolerant MANETs[C] //Proc of the 8th ACM Int Symp on Mobile Ad Hoc Networking and Computing (MobiHoc’07). New York: ACM, 2007: 32-40

[13]Pan Hui, Crowcroft J, Yoneki E. Bubble rap: Social-based forwarding in delay tolerant networks[C] //Proc of the 9th ACM Int Symp on Mobile Ad Hoc Networking and Computing (MobiHoc’08). New York: ACM, 2008: 241-250

[14]Pan Hui, Crowcroft J, Yoneki E. Bubble rap: Social-based forwarding in delay-tolerant networks[J]. IEEE Trans on Mobile Computing, 2011, 10(11): 1576-1589

[15]Wu Jie, Xiao Mingjun, Huang Liusheng. Homing spread: Community home-based multi-copy routing in mobile social networks[C] //Proc of the 2003 Int Conf on Computer Communications (INFOCOM’03).Piscataway, NJ: IEEE, 2013: 2319-2327

[16]Li Feng, Wu Jie. LocalCom: A community-based epidemic forwarding scheme in disruption-tolerant networks[C] //Proc of the 2009 Society Conf on Mesh and Ad Hoc Communications and Networks (SECON’09).Piscataway, NJ: IEEE, 2009: 1-9

[17]Gao Wei, Cao Guohong, Porta L T, et al. On exploiting transient social contact patterns for data forwarding in delay-tolerant networks[J]. IEEE Trans on Mobile Computing, 2013, 12 (1): 151-165

[18]Wei Kaimin, Liang Xiao, Xu Ke. A survey of social-aware routing protocols in delay tolerant networks: Applications, taxonomy and design-related issues[J]. Communications Surveys & Tutorials, 2014, 16(1): 556-578

[19]Socievole A, Yoneki E, Rango F D, et al. Opportunistic message routing using multi-layer social networks[C] //Proc of the 2nd ACM Workshop on High Performance Mobile Opportunistic Systems(HP-MOSys’13). New York: ACM, 2013: 39-46

[20]Pietiläinen AK, Oliver E, LeBrun J, et al. Mobiclique: Middleware for mobile social networking[C] //Proc of the 2nd ACM Workshop on Online Social Networks(WOSN’09). New York: ACM, 2009: 49-54

[21]Mtibaa A, May M, Diot C, et al. PeopleRank: Social opportunistic forwarding[C] //Proc of the 2010 Int Conf on Computer Communications (INFOCOM’10).Piscataway, NJ: IEEE, 2010: 1-5

[22]Granovetter M S. The strength of weak ties [J]. American Journal of Sociology, 1973, 78(6): 1360-1380

[23]Ioannidis S, Chaintreau A. On the strength of weak ties in mobile social networks[C] //Proc of the 2nd ACM EuroSys Workshop on Social Network Systems (SNS’09). New York: ACM, 2009: 19-25

[24]Pan Hui, Yoneki E, Chan Shuyan, et al. Distributed community detection in delay tolerant networks[C] //Proc of the 2nd ACM/IEEE Int Workshop on Mobility in The Evolving Internet Architecture(MobiArch’07). New York: ACM, 2007: No.7

[25]Brin S, Page L. The anatomy of a large-scale hypertextual Web search engine[J]. Computer Networks and ISDN Systems, 1998, 30(1): 107-117

[26]Helsinki University of Technology. ONE: Opportunistic network environment[CP]. 2009 [2015-12-03]. http://www.netlab.tkk.fi/tutkimus/dtn/theone

Zhu Ziqing, born in 1990. PhD candidate of Southeast University. His current research interests include social computing and computer network.

Cao Jiuxin, born in 1967. Professor and PhD supervisor of Southeast University. His current research interests include social computing, computer network and complex network.

Zhou Tao, born in 1989. PhD candidate of Southeast University. His current research interests include social computing and complex network.

Xu Shuai, born in 1991. PhD candidate of Southeast University. His current research interests include social computing.

Ma Zhuo, born in 1993. Master candidate of Southeast University. Her current research interests include social computing.

Liu Bo, born in 1975. Professor and master supervisor of Southeast University. Her current research interests include social computing and distributed network management.

Multi-Feature Based Message Transmitting in Mobile Social Network

Zhu Ziqing, Cao Jiuxin, Zhou Tao, Xu Shuai, Ma Zhuo, and Liu Bo

(SchoolofComputerScienceandEngineering,SoutheastUniversity,Nanjing211189) (KeyLaboratoryofComputerNetworkandInformationIntegration(SoutheastUniversity),MinistryofEducation,Nanjing211189)

Based on the features of delay tolerant network (DTN), mobile social network (MSN) uses “storage-carry-forwards” approach for message transmission between nodes. How to select a suitable relay node for efficient message transmission is an urgent issue in the current research fields. This paper focuses on the problem by analyzing the social characteristics of network in different perspectives. Firstly, based on the interaction between nodes, the model of social relations between nodes is constructed. Secondly, this paper gives the definition of neighbor set and local community based on the network topology and establishes the community relationship between the nodes. Furthermore, this paper defines the social activity based on the behavior of nodes and takes advantage of the PageRank algorithm to obtainPRvalues on the basis of multiple features of nodes. Then, transmission values of nodes is defined by usingPRvalues and different utility values of nodes can be obtained. On this basis, considering community relations of nodes and different transmission utility values of nodes, this paper designs and implements a message transmission algorithm in mobile social network. Finally, experiments show that the algorithm has advantages in delivery ratio, overhead ratio and average delay.

mobile social network (MSN); delay tolerant network (DTN); community detection; PageRank algorithm; dynamic network

2015-12-03；

2016-03-22

国家“九七三”重点基础研究发展计划基金项目(2010CB328104)；国家“八六三”高技术研究发展计划基金项目(2013AA013503)；国家自然科学基金项目(61272531，61202449，61272054，61370207，61370208，61300024，61320106007，61472081)；江苏省网络与信息安全重点实验室基金项目(BM2003201)；江苏省科技计划基金资助项目(SBY2014021039-10) This work was supported by the National Basic Research Program of China (973 Program) (2010CB328104), the National High Technology Research and Development Program of China (863 Program) (2013AA013503), the National Natural Science Foundation of China (61272531, 61202449, 61272054, 61370207, 61370208, 61300024, 61320106007, 61472081), the Jiangsu Provincial Key Laboratory of Network and Information Security Foundation (BM2003201), and the Science and Technology Planning Project of Jiangsu Province (SBY2014021039-10).

曹玖新(jx.cao@seu.edu.cn)

TP393