基于位置預(yù)測的社會性DTN路由算法

張 滔，徐建波

ZHANG Tao,XU Jianbo

湖南科技大學(xué) 計算機科學(xué)與工程學(xué)院，湖南 湘潭 411201

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

1 引言

多年來，延遲容忍網(wǎng)絡(luò)（Delay Tolerant Network，DTN）[1]，受到了眾多學(xué)者的廣泛關(guān)注。由于節(jié)點的隨機移動、缺乏持續(xù)的端對端路徑以及傳輸?shù)呢撦d有限，導(dǎo)致網(wǎng)絡(luò)中數(shù)據(jù)傳輸成功率低、傳輸延遲較大、誤碼率高[2]等問題，DTN網(wǎng)絡(luò)一般采用“存儲-攜帶-轉(zhuǎn)發(fā)”的方式完成數(shù)據(jù)的傳輸。

隨著平板、智能手機等各種擁有無線通信接口的便攜式設(shè)備大量涌現(xiàn)，人攜帶這些充當(dāng)網(wǎng)絡(luò)節(jié)點的設(shè)備，隨機移動形成的這種網(wǎng)絡(luò)具有社會網(wǎng)絡(luò)的很多特征，將這種網(wǎng)絡(luò)稱為具有社會性的DTN[3]。在具有社會性的DTN中，人的移動使得節(jié)點間連接頻繁斷開、網(wǎng)絡(luò)拓撲結(jié)構(gòu)迅速變化，導(dǎo)致節(jié)點之間不再存在穩(wěn)定的端到端連接，在此前提下如何有效地把數(shù)據(jù)從源節(jié)點傳輸給目的節(jié)點，達到數(shù)據(jù)傳輸成功率、傳輸延遲以及傳輸開銷的有效平衡，成為DTN需要解決的關(guān)鍵問題。

2 相關(guān)工作

近年來，研究人員提出了一些適合DTN的路由算法，如感染路由算法（Epidemic routing）[4]，PROPHET[5]，F(xiàn)AD[6]等。Epidemic路由算法的消息轉(zhuǎn)發(fā)采用洪泛機制，在網(wǎng)絡(luò)資源充裕的情況下，消息可以在最小延遲內(nèi)到達目的節(jié)點。Lindgren[5]等人利用了節(jié)點之間的歷史相遇信息和傳遞性提出了Prophet協(xié)議。當(dāng)兩節(jié)點相遇時，如果另外一個節(jié)點傳遞到目的節(jié)點的可預(yù)測性概率更高，則將消息傳給該節(jié)點。

目前有不少研究人員針對社會網(wǎng)絡(luò)中存在的穩(wěn)定特征和規(guī)律來輔助研究DTN路由機制。Hui和Crowcroft提出的LABEL[7]路由協(xié)議，LABEL路由將所有節(jié)點分成不同的小組，給各個小組貼上不同的標簽，在進行數(shù)據(jù)傳輸時，源節(jié)點選擇與目的節(jié)點具有相同標簽的節(jié)點作為數(shù)據(jù)傳輸?shù)南乱惶?。Pan等人提出了一種Bubble[8-9]路由策略，Bubble路由對節(jié)點之間的聯(lián)系狀況進行分析獲取節(jié)點的集中性（centrality），然后將節(jié)點分成不同的區(qū)域，同一節(jié)點可能隸屬于多個區(qū)域。節(jié)點的集中性分為全局集中性和節(jié)點所在區(qū)域的局部集中性。在進行數(shù)據(jù)傳輸?shù)倪^程中，先把消息傳輸給全局集中性較高的節(jié)點，等到消息到達目的節(jié)點所在區(qū)域，然后在目的節(jié)點所在區(qū)域內(nèi)將消息逐級傳送給局部集中性相對較高的節(jié)點，直到把消息傳送給目的節(jié)點。Daly等研究人員觀察注意到DTN接觸模型和社會網(wǎng)絡(luò)模型有一定的相似性，利用社會網(wǎng)絡(luò)中存在的“小世界（small world）”特征，提出了一種SimBet[10]路由協(xié)議，SimBet策略根據(jù)節(jié)點的橋接性以及節(jié)點與目的節(jié)點的社會相似性來度量數(shù)據(jù)傳輸。

本文提出了一種基于節(jié)點位置預(yù)測和社會性的DTN路由 LPSN（Location Prediction and Social Network based routing），該算法首先根據(jù)節(jié)點的介數(shù)中心性和節(jié)點間的相似性來衡量節(jié)點的社會特性，再結(jié)合節(jié)點的歷史軌跡和當(dāng)前位置，運用Markov模型對節(jié)點的下一個位置進行預(yù)測，最后選擇節(jié)點綜合效用值最高的節(jié)點進行數(shù)據(jù)傳輸。

3 LPSN網(wǎng)絡(luò)模型與算法描述

基于位置預(yù)測的社會性DTN路由算法LPSN中，如何利用節(jié)點的社會性特征、節(jié)點的歷史軌跡以及當(dāng)前的位置信息，選擇最優(yōu)的轉(zhuǎn)發(fā)節(jié)點，把數(shù)據(jù)從源節(jié)點傳送到匯聚節(jié)點，成為決定消息投遞性能的關(guān)鍵。本文研究的社會性DTN網(wǎng)絡(luò)模型如下。

3.1 網(wǎng)絡(luò)模型

研究模型假定滿足以下條件：

（1）假定所有節(jié)點運動規(guī)律符合移動社區(qū)模型[11-12]，整個網(wǎng)絡(luò)分為若干子社區(qū)，sink節(jié)點靜止地位于數(shù)據(jù)收集區(qū)，以基站的形式出現(xiàn)，假定其能量無限。

（2）網(wǎng)絡(luò)內(nèi)所有節(jié)點攜帶GPS模塊，節(jié)點可以隨時獲取自己的位置信息和移動速度矢量，其位置且為所有節(jié)點所已知。

（3）節(jié)點的運動能力各有差異，各節(jié)點在數(shù)據(jù)傳輸?shù)幕钴S程度也不同，網(wǎng)絡(luò)內(nèi)的節(jié)點根據(jù)節(jié)點實際的社會特性進行移動。

（4）假定采用NTP（Network Time Protocol）時鐘同步技術(shù)，各節(jié)點時鐘同步。

3.2 LPSN算法描述

LPSN路由算法主要包括節(jié)點社會特性活躍度計算和基于Markov進行位置預(yù)測兩個部分。

3.2.1 節(jié)點社會特性活躍度的計算

在社會性的DTN中，節(jié)點的一些社會特性能反應(yīng)節(jié)點在整個網(wǎng)絡(luò)中的通信能力和節(jié)點間的傳送能力[13]。DTN中節(jié)點的活躍能力各有差異，較活躍的節(jié)點，具有較強傳播能力，能讓消息擴散到更多的節(jié)點，選擇活躍的節(jié)點作為轉(zhuǎn)發(fā)節(jié)點比較合理。從節(jié)點社會特性來看，節(jié)點的相似性和介數(shù)中心性是衡量節(jié)點特征的兩個重要尺度[14]。其中每個節(jié)點與其他節(jié)點共同擁有朋友的數(shù)量多少被稱為與對方的相似性（similarity），而每個節(jié)點為其他節(jié)點之間通信充當(dāng)橋梁的能力被稱為該節(jié)點的介數(shù)中心性（betweenness centrality），節(jié)點的社會效用由相似性和介數(shù)中心性構(gòu)成，在此，采用計算節(jié)點的相似性和介數(shù)中心性作為衡量節(jié)點活躍性的度量。

節(jié)點的介數(shù)中心性主要體現(xiàn)在節(jié)點在社區(qū)間的傳播能力，節(jié)點的介數(shù)中心性表示為BetN，節(jié)點N所遇到的節(jié)點之間的連接可以用一個P×P的對稱矩陣F來表示，其中P表示節(jié)點N遇到的節(jié)點數(shù)量。如果矩陣行和列代表的節(jié)點存在連接，則矩陣F中元素的Fij值為1，否則為0。BetN值的計算如公式（1）所示。

節(jié)點的相似性主要體現(xiàn)在同一社區(qū)內(nèi)節(jié)點與目的節(jié)點在過去時間內(nèi)遇到相同節(jié)點的數(shù)量，節(jié)點N和目的節(jié)點D的相似性表示為SimN(D)，計算公式如式（2）所示。

其中NN和ND分別表示節(jié)點N和節(jié)點D相遇節(jié)點的集合。

文中假定節(jié)點N需要轉(zhuǎn)發(fā)消息給目的節(jié)點D。當(dāng)節(jié)點N遇到M時，相似度和介數(shù)中心度分別為：

當(dāng)節(jié)點N把消息傳送給目的節(jié)點D時，節(jié)點社會特性的綜合效用SimBet值為：

其中，α+β=1，α和β是兩個可調(diào)參數(shù)，其值均取0.5。

可以通過以上公式計算任一節(jié)點到目的節(jié)點D的SimBet(D)值。當(dāng)節(jié)點N在社區(qū)中移動時，向其通信半徑范圍內(nèi)的節(jié)點進行消息廣播，比較各自的社會特性綜合效用值，選擇社會特性綜合效用值大于自己的節(jié)點作為消息轉(zhuǎn)發(fā)的候選節(jié)點。

3.2.2 Markov位置預(yù)測階段

在DTN中，節(jié)點的移動具有延續(xù)性，節(jié)點的下一個位置決定了與匯聚節(jié)點的距離，下一個時刻節(jié)點的位置不僅與當(dāng)前的位置有關(guān)，還與節(jié)點的歷史位置有關(guān)。根據(jù)相關(guān)知識，可以用Markov模型對節(jié)點位置進行預(yù)測[15-16]。多重馬爾可夫鏈假定系統(tǒng)在n+1時刻的狀態(tài)僅與前n個時刻的狀態(tài)有關(guān)，而與n個時刻以前的狀態(tài)無關(guān)。在此，運用多重Markov對節(jié)點下一個時刻的位置進行預(yù)測。

具體過程描述如下：

假定匯聚節(jié)點為圓心，以網(wǎng)絡(luò)中到匯聚節(jié)點最遠的節(jié)點距離為半徑，把網(wǎng)絡(luò)等距離劃分成數(shù)個寬度相等的同心圓環(huán)。每個環(huán)之間寬度為等距的d。用C表示環(huán)的序列。C0表示匯聚節(jié)點，Cn表示距離最遠的環(huán)。用Z表示所有位置點序列的集合Z={C1，C2，…，Cn}。

節(jié)點可以根據(jù)GPS定位知道自身的地理位置所在的環(huán)，假設(shè)移動節(jié)點當(dāng)前的位置坐標為(xi，yi)，匯聚節(jié)點的坐標為(xd，yd)，由此可以求得節(jié)點i當(dāng)前位置與匯聚節(jié)點的距離di為：

節(jié)點i當(dāng)前所在環(huán)的編號Ccur為：

每隔ΔT時間對當(dāng)前節(jié)點的位置進行采樣記錄，并根據(jù)上式計算得到節(jié)點所處的環(huán)，因此可得節(jié)點采樣時間間隔為：

其中ΔT為采樣的時間間隔，d為網(wǎng)絡(luò)場景設(shè)定的最小單位間距，vˉ為平均速度，λ為控制采樣精度的比例因子，且0＜λ＜1。

假設(shè)節(jié)點的位置變量X是一個隨機變量，Xi表示節(jié)點在采樣時刻i的位置，隨機變量序列 X構(gòu)成一個Markov過程。用S表示節(jié)點運動經(jīng)過的環(huán)的歷史軌跡，S=C1，C2，…，Cn，其中 Ci表示節(jié)點在第 i個時刻所在位置且Ci∈Z，用Hk表示節(jié)點最近k個采樣時刻所經(jīng)過的環(huán)序列，Hk=aj-k+1，aj-k+2，…，aj。用 C 表示任意的一個環(huán)。在假定已知節(jié)點最近k個采樣時刻的節(jié)點歷史位置信息的情況下，節(jié)點下一個采樣時刻出現(xiàn)在環(huán)C的條件轉(zhuǎn)移概率為：

根據(jù)k個采樣時刻的歷史位置信息，可以用k重Markov模型對節(jié)點下一個位置進行預(yù)測，k重Markov模型要求隨機時齊的Xi滿足以下要求：

由上兩式可知，節(jié)點下一個時刻的位置只與最近的k個采樣時刻的位置有關(guān)，節(jié)點最近k個時刻的位置序列相同，那么下一個采樣時刻節(jié)點出現(xiàn)在同一個環(huán)C的概率也相同。

根據(jù)歷史的運動軌跡S和最近k個采樣時刻的運動軌跡Hk，預(yù)測下一個時刻節(jié)點在環(huán)C的轉(zhuǎn)移概率為：

其中C為下一個時刻節(jié)點所在的位置，N(HkC，S)為位置序列HkC在歷史軌跡S中出現(xiàn)的次數(shù)，N(Hk，S)為位置序列Hk在歷史軌跡S中出現(xiàn)的次數(shù)，P(Xj+1=C|X(j-k+1，j)=Hk)表示預(yù)測的目標節(jié)點的下一個時刻在位置C的轉(zhuǎn)移概率。

假設(shè)節(jié)點當(dāng)前所在環(huán)為Ccur，節(jié)點下一個時刻在某個環(huán)出現(xiàn)的概率為Pi，設(shè)

下一個位置所在的位置環(huán)編號為Cnext，Cnext為節(jié)點在下一跳可能出現(xiàn)的各環(huán)的加權(quán)平均值，即

其中i為環(huán)的編號，Pi為各環(huán)出現(xiàn)的概率。根據(jù)節(jié)點下一跳位置的環(huán)的編號大小，比較環(huán)的編號大小，根據(jù)上文可知，節(jié)點的編號越小，離匯聚節(jié)點越近，即為相對更優(yōu)的轉(zhuǎn)發(fā)節(jié)點。

4 LPSN算法的實現(xiàn)

LPSN算法為了能滿足網(wǎng)絡(luò)中數(shù)據(jù)能以最優(yōu)的方式從源節(jié)點轉(zhuǎn)發(fā)給匯聚節(jié)點sink，在進行數(shù)據(jù)轉(zhuǎn)發(fā)前，根據(jù)節(jié)點的社會特性效用值和節(jié)點下一跳預(yù)測的位置進行綜合分析，選擇更優(yōu)的轉(zhuǎn)發(fā)節(jié)點。設(shè)節(jié)點的綜合效用值為Q(D)，計算方式如下：

算法基本原理為：節(jié)點N有消息m需要傳送給匯聚節(jié)點，節(jié)點N通信范圍內(nèi)有若干鄰居節(jié)點，節(jié)點N首先通過簡單的握手與其鄰居節(jié)點進行信息交換，包括相遇節(jié)點矢量（Encounter Vector，EV）、消息匯總矢量（Summary Vector，SV）、消息請求矢量（Message Request Vector，MRV）等信息，然后計算節(jié)點社會特性效用值和下一跳預(yù)測位置，得知節(jié)點的綜合效用值。節(jié)點N是否轉(zhuǎn)發(fā)消息給某節(jié)點M，根據(jù)相遇節(jié)點兩者之間的節(jié)點綜合效用Q(D)決定。如果QN(D)＜QM(D)，則進行消息轉(zhuǎn)發(fā)，否則，繼續(xù)自由移動，尋找更優(yōu)節(jié)點。

其中EV表示節(jié)點曾經(jīng)相遇的節(jié)點集合，SV表示節(jié)點攜帶消息的目的節(jié)點的集合，MRV表示鄰居節(jié)點請求消息的目的節(jié)點的集合。

以下對節(jié)點N和節(jié)點M相遇后的通信過程用偽代碼的形式進行相關(guān)描述。

5 仿真實驗

5.1 仿真環(huán)境與參數(shù)

為了驗證LPSN路由算法的性能，本文采用了ONE[17]平臺進行仿真。

仿真環(huán)境采用芬蘭赫爾辛基市作為節(jié)點移動的區(qū)域，面積為4 500 m×3 400 m，整個網(wǎng)絡(luò)由120個節(jié)點組成。節(jié)點的平均移動速度為1.5 m/s、5 m/s、9 m/s，分別表示步行、跑步以及騎車三種不同活動的平均速度，停滯時間為0～120 s。在對各候選節(jié)點下一跳位置預(yù)測階段，多次實驗可知，多重馬爾可夫鏈的階數(shù)k越大，預(yù)測準確性逐漸提高。但當(dāng)選取k=4時，預(yù)測結(jié)果的準確性較高，基本趨于穩(wěn)定。

對LPSN算法進行仿真時，選取與經(jīng)典的算法Epidemic、適合社區(qū)移動模型的Prophet路由算法和多副本的社會網(wǎng)絡(luò)SimBet路由算法進行比較。主要從在傳輸開銷比、傳輸成功率、平均延遲三個方面指標考察各路由算法的性能。表1為進行仿真實驗的相關(guān)參數(shù)。

表1 仿真實驗參數(shù)

5.2 仿真分析

5.2.1 不同緩存下性能比較

圖1（a） 不同緩存下交付比

圖1（b） 不同緩存下開銷比

圖1（c） 不同緩存下平均延時

圖1（a）～（c）分別表示在不同的緩存情況下，節(jié)點的傳輸交付比、開銷比以及傳輸平均延時。觀察各圖可知，由于LPSN路由算法選擇性地選取傳輸節(jié)點，減少節(jié)點轉(zhuǎn)發(fā)的次數(shù)，提高了傳送成功交付比，減少了傳輸副本，降低了開銷，在消息容忍范圍內(nèi)，傳輸性能比其他算法更加優(yōu)越。

5.2.2 不同節(jié)點運動速度比較

觀察圖2（a）～（c），其分別表明在不同的節(jié)點運行速度情況下，各算法的傳輸交付比、開銷比以及傳輸平均延時。本實驗分別取節(jié)點在1.5 m/s、5 m/s、9 m/s的速度下，各算法的網(wǎng)絡(luò)性能進行對比。節(jié)點速度增大時，消息傳播的速度隨之增大，各算法的平均延時也隨之變小。在消息容忍的范圍內(nèi)，LPSN的性能在傳輸開銷比、交付比相對優(yōu)越。

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

圖2（b） 不同速度下開銷比

圖2（c） 不同速度下平均延時

6 結(jié)束語

針對移動社區(qū)模型，提出了一種基于節(jié)點社會特性和節(jié)點運動歷史軌跡的路由算法：根據(jù)節(jié)點的社會屬性計算其活躍度綜合效用值，然后根據(jù)節(jié)點的歷史位置預(yù)測節(jié)點的下一個時刻的位置，綜合考慮選擇更優(yōu)的轉(zhuǎn)發(fā)節(jié)點，選擇最優(yōu)的數(shù)據(jù)傳輸路徑。利用網(wǎng)絡(luò)中與目的節(jié)點相遇可能性最大并且下一跳離匯聚節(jié)點位置較近的移動節(jié)點傳送消息，仿真結(jié)果表明，LPSN路由算法選擇性地轉(zhuǎn)發(fā)數(shù)據(jù)，減少了傳輸過程中消息不必要的轉(zhuǎn)發(fā)次數(shù)，提高了節(jié)點數(shù)據(jù)傳輸?shù)某晒β剩瑴p少副本數(shù)量，降低了開銷比，最終可以較快的速度、較小的開銷把消息傳送給目的節(jié)點。

[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]夏磊，張樂君，國林，等.節(jié)點相似度標簽傳播在社會網(wǎng)絡(luò)中的應(yīng)用研究[J].計算機工程與應(yīng)用，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]劉耀，王建新，黃元南.延遲容忍網(wǎng)絡(luò)中基于社會屬性的負載感知路由[J].系統(tǒng)工程與電子技術(shù)，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]劉杰彥.延遲容忍網(wǎng)絡(luò)路由協(xié)議研究[D].成都：電子科技大學(xué)，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.