基于位置预测的社会性DTN路由算法

张 滔，徐建波

ZHANG Tao,XU Jianbo

湖南科技大学 计算机科学与工程学院，湖南 湘潭 411201

School of Computer Science and Engineering,Hunan University of Science and Technology,Xiangtan,Hunan 411201,China

1 引言

多年来，延迟容忍网络（Delay Tolerant Network，DTN）[1]，受到了众多学者的广泛关注。由于节点的随机移动、缺乏持续的端对端路径以及传输的负载有限，导致网络中数据传输成功率低、传输延迟较大、误码率高[2]等问题，DTN网络一般采用“存储-携带-转发”的方式完成数据的传输。

随着平板、智能手机等各种拥有无线通信接口的便携式设备大量涌现，人携带这些充当网络节点的设备，随机移动形成的这种网络具有社会网络的很多特征，将这种网络称为具有社会性的DTN[3]。在具有社会性的DTN中，人的移动使得节点间连接频繁断开、网络拓扑结构迅速变化，导致节点之间不再存在稳定的端到端连接，在此前提下如何有效地把数据从源节点传输给目的节点，达到数据传输成功率、传输延迟以及传输开销的有效平衡，成为DTN需要解决的关键问题。

2 相关工作

近年来，研究人员提出了一些适合DTN的路由算法，如感染路由算法（Epidemic routing）[4]，PROPHET[5]，FAD[6]等。Epidemic路由算法的消息转发采用洪泛机制，在网络资源充裕的情况下，消息可以在最小延迟内到达目的节点。Lindgren[5]等人利用了节点之间的历史相遇信息和传递性提出了Prophet协议。当两节点相遇时，如果另外一个节点传递到目的节点的可预测性概率更高，则将消息传给该节点。

目前有不少研究人员针对社会网络中存在的稳定特征和规律来辅助研究DTN路由机制。Hui和Crowcroft提出的LABEL[7]路由协议，LABEL路由将所有节点分成不同的小组，给各个小组贴上不同的标签，在进行数据传输时，源节点选择与目的节点具有相同标签的节点作为数据传输的下一跳。Pan等人提出了一种Bubble[8-9]路由策略，Bubble路由对节点之间的联系状况进行分析获取节点的集中性（centrality），然后将节点分成不同的区域，同一节点可能隶属于多个区域。节点的集中性分为全局集中性和节点所在区域的局部集中性。在进行数据传输的过程中，先把消息传输给全局集中性较高的节点，等到消息到达目的节点所在区域，然后在目的节点所在区域内将消息逐级传送给局部集中性相对较高的节点，直到把消息传送给目的节点。Daly等研究人员观察注意到DTN接触模型和社会网络模型有一定的相似性，利用社会网络中存在的“小世界（small world）”特征，提出了一种SimBet[10]路由协议，SimBet策略根据节点的桥接性以及节点与目的节点的社会相似性来度量数据传输。

本文提出了一种基于节点位置预测和社会性的DTN路由 LPSN（Location Prediction and Social Network based routing），该算法首先根据节点的介数中心性和节点间的相似性来衡量节点的社会特性，再结合节点的历史轨迹和当前位置，运用Markov模型对节点的下一个位置进行预测，最后选择节点综合效用值最高的节点进行数据传输。

3 LPSN网络模型与算法描述

基于位置预测的社会性DTN路由算法LPSN中，如何利用节点的社会性特征、节点的历史轨迹以及当前的位置信息，选择最优的转发节点，把数据从源节点传送到汇聚节点，成为决定消息投递性能的关键。本文研究的社会性DTN网络模型如下。

3.1 网络模型

研究模型假定满足以下条件：

（1）假定所有节点运动规律符合移动社区模型[11-12]，整个网络分为若干子社区，sink节点静止地位于数据收集区，以基站的形式出现，假定其能量无限。

（2）网络内所有节点携带GPS模块，节点可以随时获取自己的位置信息和移动速度矢量，其位置且为所有节点所已知。

（3）节点的运动能力各有差异，各节点在数据传输的活跃程度也不同，网络内的节点根据节点实际的社会特性进行移动。

（4）假定采用NTP（Network Time Protocol）时钟同步技术，各节点时钟同步。

3.2 LPSN算法描述

LPSN路由算法主要包括节点社会特性活跃度计算和基于Markov进行位置预测两个部分。

3.2.1 节点社会特性活跃度的计算

在社会性的DTN中，节点的一些社会特性能反应节点在整个网络中的通信能力和节点间的传送能力[13]。DTN中节点的活跃能力各有差异，较活跃的节点，具有较强传播能力，能让消息扩散到更多的节点，选择活跃的节点作为转发节点比较合理。从节点社会特性来看，节点的相似性和介数中心性是衡量节点特征的两个重要尺度[14]。其中每个节点与其他节点共同拥有朋友的数量多少被称为与对方的相似性（similarity），而每个节点为其他节点之间通信充当桥梁的能力被称为该节点的介数中心性（betweenness centrality），节点的社会效用由相似性和介数中心性构成，在此，采用计算节点的相似性和介数中心性作为衡量节点活跃性的度量。

节点的介数中心性主要体现在节点在社区间的传播能力，节点的介数中心性表示为BetN，节点N所遇到的节点之间的连接可以用一个P×P的对称矩阵F来表示，其中P表示节点N遇到的节点数量。如果矩阵行和列代表的节点存在连接，则矩阵F中元素的Fij值为1，否则为0。BetN值的计算如公式（1）所示。

节点的相似性主要体现在同一社区内节点与目的节点在过去时间内遇到相同节点的数量，节点N和目的节点D的相似性表示为SimN(D)，计算公式如式（2）所示。

其中NN和ND分别表示节点N和节点D相遇节点的集合。

文中假定节点N需要转发消息给目的节点D。当节点N遇到M时，相似度和介数中心度分别为：

当节点N把消息传送给目的节点D时，节点社会特性的综合效用SimBet值为：

其中，α+β=1，α和β是两个可调参数，其值均取0.5。

可以通过以上公式计算任一节点到目的节点D的SimBet(D)值。当节点N在社区中移动时，向其通信半径范围内的节点进行消息广播，比较各自的社会特性综合效用值，选择社会特性综合效用值大于自己的节点作为消息转发的候选节点。

3.2.2 Markov位置预测阶段

在DTN中，节点的移动具有延续性，节点的下一个位置决定了与汇聚节点的距离，下一个时刻节点的位置不仅与当前的位置有关，还与节点的历史位置有关。根据相关知识，可以用Markov模型对节点位置进行预测[15-16]。多重马尔可夫链假定系统在n+1时刻的状态仅与前n个时刻的状态有关，而与n个时刻以前的状态无关。在此，运用多重Markov对节点下一个时刻的位置进行预测。

具体过程描述如下：

假定汇聚节点为圆心，以网络中到汇聚节点最远的节点距离为半径，把网络等距离划分成数个宽度相等的同心圆环。每个环之间宽度为等距的d。用C表示环的序列。C0表示汇聚节点，Cn表示距离最远的环。用Z表示所有位置点序列的集合Z={C1，C2，…，Cn}。

节点可以根据GPS定位知道自身的地理位置所在的环，假设移动节点当前的位置坐标为(xi，yi)，汇聚节点的坐标为(xd，yd)，由此可以求得节点i当前位置与汇聚节点的距离di为：

节点i当前所在环的编号Ccur为：

每隔ΔT时间对当前节点的位置进行采样记录，并根据上式计算得到节点所处的环，因此可得节点采样时间间隔为：

其中ΔT为采样的时间间隔，d为网络场景设定的最小单位间距，vˉ为平均速度，λ为控制采样精度的比例因子，且0＜λ＜1。

假设节点的位置变量X是一个随机变量，Xi表示节点在采样时刻i的位置，随机变量序列 X构成一个Markov过程。用S表示节点运动经过的环的历史轨迹，S=C1，C2，…，Cn，其中 Ci表示节点在第 i个时刻所在位置且Ci∈Z，用Hk表示节点最近k个采样时刻所经过的环序列，Hk=aj-k+1，aj-k+2，…，aj。用 C 表示任意的一个环。在假定已知节点最近k个采样时刻的节点历史位置信息的情况下，节点下一个采样时刻出现在环C的条件转移概率为：

根据k个采样时刻的历史位置信息，可以用k重Markov模型对节点下一个位置进行预测，k重Markov模型要求随机时齐的Xi满足以下要求：

由上两式可知，节点下一个时刻的位置只与最近的k个采样时刻的位置有关，节点最近k个时刻的位置序列相同，那么下一个采样时刻节点出现在同一个环C的概率也相同。

根据历史的运动轨迹S和最近k个采样时刻的运动轨迹Hk，预测下一个时刻节点在环C的转移概率为：

其中C为下一个时刻节点所在的位置，N(HkC，S)为位置序列HkC在历史轨迹S中出现的次数，N(Hk，S)为位置序列Hk在历史轨迹S中出现的次数，P(Xj+1=C|X(j-k+1，j)=Hk)表示预测的目标节点的下一个时刻在位置C的转移概率。

假设节点当前所在环为Ccur，节点下一个时刻在某个环出现的概率为Pi，设

下一个位置所在的位置环编号为Cnext，Cnext为节点在下一跳可能出现的各环的加权平均值，即

其中i为环的编号，Pi为各环出现的概率。根据节点下一跳位置的环的编号大小，比较环的编号大小，根据上文可知，节点的编号越小，离汇聚节点越近，即为相对更优的转发节点。

4 LPSN算法的实现

LPSN算法为了能满足网络中数据能以最优的方式从源节点转发给汇聚节点sink，在进行数据转发前，根据节点的社会特性效用值和节点下一跳预测的位置进行综合分析，选择更优的转发节点。设节点的综合效用值为Q(D)，计算方式如下：

算法基本原理为：节点N有消息m需要传送给汇聚节点，节点N通信范围内有若干邻居节点，节点N首先通过简单的握手与其邻居节点进行信息交换，包括相遇节点矢量（Encounter Vector，EV）、消息汇总矢量（Summary Vector，SV）、消息请求矢量（Message Request Vector，MRV）等信息，然后计算节点社会特性效用值和下一跳预测位置，得知节点的综合效用值。节点N是否转发消息给某节点M，根据相遇节点两者之间的节点综合效用Q(D)决定。如果QN(D)＜QM(D)，则进行消息转发，否则，继续自由移动，寻找更优节点。

其中EV表示节点曾经相遇的节点集合，SV表示节点携带消息的目的节点的集合，MRV表示邻居节点请求消息的目的节点的集合。

以下对节点N和节点M相遇后的通信过程用伪代码的形式进行相关描述。

5 仿真实验

5.1 仿真环境与参数

为了验证LPSN路由算法的性能，本文采用了ONE[17]平台进行仿真。

仿真环境采用芬兰赫尔辛基市作为节点移动的区域，面积为4 500 m×3 400 m，整个网络由120个节点组成。节点的平均移动速度为1.5 m/s、5 m/s、9 m/s，分别表示步行、跑步以及骑车三种不同活动的平均速度，停滞时间为0～120 s。在对各候选节点下一跳位置预测阶段，多次实验可知，多重马尔可夫链的阶数k越大，预测准确性逐渐提高。但当选取k=4时，预测结果的准确性较高，基本趋于稳定。

对LPSN算法进行仿真时，选取与经典的算法Epidemic、适合社区移动模型的Prophet路由算法和多副本的社会网络SimBet路由算法进行比较。主要从在传输开销比、传输成功率、平均延迟三个方面指标考察各路由算法的性能。表1为进行仿真实验的相关参数。

表1 仿真实验参数

5.2 仿真分析

5.2.1 不同缓存下性能比较

图1（a） 不同缓存下交付比

图1（b） 不同缓存下开销比

图1（c） 不同缓存下平均延时

图1（a）～（c）分别表示在不同的缓存情况下，节点的传输交付比、开销比以及传输平均延时。观察各图可知，由于LPSN路由算法选择性地选取传输节点，减少节点转发的次数，提高了传送成功交付比，减少了传输副本，降低了开销，在消息容忍范围内，传输性能比其他算法更加优越。

5.2.2 不同节点运动速度比较

观察图2（a）～（c），其分别表明在不同的节点运行速度情况下，各算法的传输交付比、开销比以及传输平均延时。本实验分别取节点在1.5 m/s、5 m/s、9 m/s的速度下，各算法的网络性能进行对比。节点速度增大时，消息传播的速度随之增大，各算法的平均延时也随之变小。在消息容忍的范围内，LPSN的性能在传输开销比、交付比相对优越。

图2（a） 不同速度下交付比

图2（b） 不同速度下开销比

图2（c） 不同速度下平均延时

6 结束语

针对移动社区模型，提出了一种基于节点社会特性和节点运动历史轨迹的路由算法：根据节点的社会属性计算其活跃度综合效用值，然后根据节点的历史位置预测节点的下一个时刻的位置，综合考虑选择更优的转发节点，选择最优的数据传输路径。利用网络中与目的节点相遇可能性最大并且下一跳离汇聚节点位置较近的移动节点传送消息，仿真结果表明，LPSN路由算法选择性地转发数据，减少了传输过程中消息不必要的转发次数，提高了节点数据传输的成功率，减少副本数量，降低了开销比，最终可以较快的速度、较小的开销把消息传送给目的节点。

[1]Fall K.A delay-tolerant network architecture for challenged Internets[C]//Proceedings of SIGCOMM’03.New York：ACM，2003：27-34.

[2]Wang Y,Wu H.Delay/fault-tolerant mobile sensor network（dft-msn）：a new paradigm for pervasive information gathering[J].IEEE Transactions on Mobile Computing，2007，6（9）：1021-1034.

[3]夏磊，张乐君，国林，等.节点相似度标签传播在社会网络中的应用研究[J].计算机工程与应用，2014，50（14）：103-109.

[4]Musolesi M，Hailes S.Adaptive routing for intermittently connected mobile ad hoc networks[C]//Proceedings of WOWMOM’2005.Taormina：IEEE Computer Society Press，2005：813-820.

[5]Lindgren A，Doria A，Sehelen O.Probabilistic routing in intermittently connected networks[J].ACM SIGMOBILE Mobile Computing and Communications Review，2003，7（3）：19-20.

[6]Wang Y，Wu H.Analytic，simulation，and empirical evaluation of delay-fault-tolerant mobile sensor networks[J].IEEE Transactions on Wireless Communications，2007，6（9）：3287-3296.

[7]Hui P，Crowcroft J.How small labels create big improvements[C]//The 5th Annual IEEE International Conference on Pervasive Computing and Communications Workshops Cover，2007：65-70.

[8]Schurgot M R，Comaniciu C.Beyond traditional DTN routing：social networks for opportunistic communication[J].IEEE Communications Magazine，2012，7：155-162.

[9]Hui P，Crowcroft J，Yoneki E.Bubble rap：social-based forwarding in delay tolerant networks[C]//Proceedings of ACM Mobihoc，2008：241-250.

[10]Daly E，Haahr M.Social network analysis for routing in disconnected delay-tolerant MANETs[C]//Proceedings of ACM Mobi-Hoc，2007：32-40.

[11]Zhu Y，Xu B，Shi X.A survey of social-based routing in delay tolerant networks：positive and negative social effects[J].Communications Surveys& Tutorials，2013，15（1）：387-401.

[12]Ghosh J，Philip J S，Qiao C M.Sociological orbit aware location approximation and routing in MANET[C]//Proceedings of International Conference on Broadband Networks，Boston，MA，USA，2005：641-650.

[13]刘耀，王建新，黄元南.延迟容忍网络中基于社会属性的负载感知路由[J].系统工程与电子技术，2012，34（1）：185-190.

[14]Pujol J M，Toledo A L，Rodriguez.Fair routing in delay tolerant networks[C]//Proceedings of the 28th International Conference on Computer Communications.Piscataway，NJ：IEEE，2009：837-845.

[15]刘杰彦.延迟容忍网络路由协议研究[D].成都：电子科技大学，2012.

[16]Yuan Quan，Cardei I，Wu Jie.An efficient prediction-based routing in disruption-tolerant networks[J].IEEE Transactions on Parallel and Distributed Systems，2012，1：19-31.

[17]Keranen A，Ott J，Karkkainen T.The ONE simulator for DTN protocol evaluation[C]//SIMUTools’09：Proceedings of the 2nd International Conference on Simulation Tools and Techniques，New York，NY，USA，2009.