基于位置預測的社會性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.