節(jié)點關系強度感知的延遲容忍網絡路由機制

胡 敏，王言通，黃春妮

(重慶郵電大學 通信與信息工程學院，重慶 400065)

0 引 言

目前國內外研究機構在延遲容忍網絡(delay tolerant network，DTN)路由機制方面的研究中，研究熱點是利用節(jié)點關系(如社會關系、相遇概率)確定消息轉發(fā)節(jié)點[1,2]，完成消息傳輸過程。Pan等[3]提出的Bubble Rap路由，依據(jù)節(jié)點的移動信息對節(jié)點劃分社區(qū)，同時利用網絡拓撲結構和節(jié)點屬性計算節(jié)點活躍度并排序，根據(jù)節(jié)點排名選擇轉發(fā)消息節(jié)點；Abdelkader等[4]利用社會網絡中“小世界”特性制定路由策略，依據(jù)節(jié)點相似性和中心性確定轉發(fā)節(jié)點；吳大鵬等[5]提出根據(jù)節(jié)點社會屬性感知的數(shù)據(jù)轉發(fā)策略，利用節(jié)點連接持續(xù)時間評估節(jié)點關系。此外，研究人員發(fā)現(xiàn)利用節(jié)點的歷史信息可以對節(jié)點的運動進行預測。王恩等[6]利用節(jié)點歷史信息預測節(jié)點相遇概率并根據(jù)預測值確定轉發(fā)節(jié)點；Peng等[7]提出的基于投遞概率預測的高效路由(delivery probability prediction based on efficient routing，DPER)，根據(jù)節(jié)點投遞概率預測值選擇節(jié)點并根據(jù)預測值分配消息副本。在上述研究的節(jié)點關系評估中，忽略了節(jié)點間關系強度受其連接節(jié)點的影響，使所得結果與節(jié)點在網絡中的實際關系強度不相吻合，從而錯誤評估了節(jié)點轉發(fā)能力，降低網絡傳輸性能。

針對上述問題，本文提出節(jié)點關系強度感知的延遲容忍網絡路由機制(node relationship magnanimity aesthesis routing，NMAR)，該機制利用相遇節(jié)點信息衡量節(jié)點關系強度變化，并依據(jù)節(jié)點連接狀態(tài)信息估計節(jié)點相遇概率，并結合節(jié)點關系預測節(jié)點轉發(fā)能力，根據(jù)節(jié)點關系強度和轉發(fā)能力值選擇轉發(fā)節(jié)點，提高消息轉發(fā)效率，提高網絡性能。

1 節(jié)點關系強度感知

節(jié)點關系通?？紤]節(jié)點間的相遇時間或相遇頻率[8]，節(jié)點關系強度能夠反映節(jié)點間連接的緊密情況。但節(jié)點關系強度并不能僅考慮兩節(jié)點的連接情況，其它節(jié)點也會對兩節(jié)點關系產生影響。

1.1 節(jié)點關系

網絡中的節(jié)點選擇任意方向移動，并依靠與其它節(jié)點相遇建立的連接轉發(fā)消息。節(jié)點運動場景如圖1所示。

節(jié)點運動使節(jié)點間關系產生變化，由此節(jié)點間關系變化取決于節(jié)點運動情況。移動過程中相遇節(jié)點信息反映節(jié)點運動情況，利用相遇節(jié)點數(shù)量的變化分析節(jié)點運動情況，評估節(jié)點間關系的變化。

圖1 節(jié)點運動場景

相遇節(jié)點信息是記錄存儲該節(jié)點移動過程中相遇節(jié)點的信息，包括節(jié)點ID、相遇次數(shù)、開始時間、結束時間等。本文利用相遇節(jié)點的數(shù)量衡量節(jié)點關系強度，利用兩節(jié)點共同相遇節(jié)點(共遇節(jié)點)的數(shù)量變化描述節(jié)點關系強度變化，即共遇節(jié)點數(shù)目增加，則節(jié)點關系強度增加；反之，節(jié)點關系強度減弱。節(jié)點關系強度變化如圖2所示。兩節(jié)點間關系越強，節(jié)點間轉發(fā)消息的能力越強，消息的傳輸效率越高。

圖2 網絡中節(jié)點關系變化

1.2 節(jié)點關系強度感知

網絡G由n個節(jié)點構成，N為節(jié)點集合。節(jié)點a與節(jié)點b為網絡中任意兩個節(jié)點，節(jié)點a的相遇節(jié)點集合記為表示為M(a)={ni|ni∈N},ni為網絡中節(jié)點。節(jié)點a和節(jié)點b的共遇節(jié)點集合記為

CM(a,b)={ni|ni∈M(a),ni∈M(b),ni∈N}

(1)

定義1 共遇節(jié)點變化度

共遇節(jié)點變化度指節(jié)點a與節(jié)點b的相鄰兩個時間周期內共遇節(jié)點數(shù)目的變化值與非共遇節(jié)點數(shù)目的比值，記為

(2)

式中：CM(a,b)i表示節(jié)點a與節(jié)點b在第i個周期內的共遇節(jié)點集，CM(a,b)i-1表示節(jié)點a與節(jié)點b在第i-1個周期內的共遇節(jié)點集。

共遇節(jié)點變化度反映節(jié)點關系強度變化，當共遇節(jié)點變化度大于零，共遇節(jié)點數(shù)目增多，節(jié)點關系強度增加；反之，節(jié)點關系強度減弱。同時共遇節(jié)點變化度的絕對值表征節(jié)點間關系強度的變化程度，絕對值越大，節(jié)點關系強度變化越劇烈。

定義2 節(jié)點連接度

節(jié)點連接度是指節(jié)點a與節(jié)點b的共遇節(jié)點數(shù)目與兩節(jié)點所有相遇節(jié)點數(shù)目的比值，記

(3)

式中：CM(a,b)i表示節(jié)點a與節(jié)點b在第i個周期內的共遇節(jié)點集，M(a)i,M(b)i表示為節(jié)點a與節(jié)點b在第i個周期內的相遇節(jié)點集。

節(jié)點連接度表征節(jié)點間關系強度，連接度越大，節(jié)點間關系強度越高。

定義3 相遇節(jié)點變化度

相遇節(jié)點變化度是指節(jié)點a在兩個相鄰的時間周期內相遇節(jié)點數(shù)目變化值與相遇節(jié)點數(shù)目的比值，記為

(4)

式中：M(a)i為節(jié)點a在第i個時間周期內的相遇節(jié)點集合，M(a)i-1為節(jié)點a在第i-1個時間周期內的相遇節(jié)點集合。

相遇節(jié)點變化度反映節(jié)點因移動造成相遇節(jié)點的變化程度，體現(xiàn)節(jié)點移動能力大小，變化度值越大，移動能力越強。

節(jié)點a，d的關系強度函數(shù)記為

Re(a,d)=μCon(a,d)+εDis(a,d)+Var(a)

(5)

式中：μ、ε和為權重因子，μ+ε+=1，μ=0.5，ε=0.3，=0.2。

1.3 節(jié)點的轉發(fā)能力

節(jié)點關系強度反映節(jié)點間連接路徑的數(shù)量。消息轉發(fā)效率不僅與路徑數(shù)目多少相關，還與各個路徑的節(jié)點轉發(fā)能力有關。節(jié)點轉發(fā)能力包括相遇轉發(fā)能力和鄰接轉發(fā)能力，相遇轉發(fā)能力是指與目的節(jié)點相遇完成消息轉發(fā)的能力，鄰接轉發(fā)能力是指由非目的節(jié)點完成消息轉發(fā)的能力。轉發(fā)能力用相遇概率描述，而相遇概率由節(jié)點間連接狀態(tài)預測得到。

網絡中任意兩個節(jié)點之間的連接狀態(tài)由連通和斷開交替變化，并且兩節(jié)點a、b在將來tk+1時刻的狀態(tài)(連通/斷開)只與當前時刻tk的狀態(tài)有關而與過去其它時刻無關，如圖3所示。因此，節(jié)點連接狀態(tài)的變化過程可視作連續(xù)時間的馬爾可夫鏈。

圖3 節(jié)點連接狀態(tài)變化過程

圖3中λ、μ分別表示節(jié)點間的連接狀態(tài)由斷開轉變?yōu)檫B通、由連通轉變?yōu)閿嚅_的概率，設連接的持續(xù)時間與連接的間隔時間分別用ct、ict來表示，則λ=∑ct/∑t,μ=∑ict/∑t。

該馬爾可夫鏈是一個齊次馬爾可夫過程，其狀態(tài)轉移概率為

(6)

即狀態(tài)轉移矩陣為

(7)

節(jié)點a、b間連接狀態(tài)由斷開到斷開的轉移速率為

(8)

同理，連接狀態(tài)由連通到連通的轉移速率為

(9)

即上述演化過程的Q矩陣為

(10)

由柯爾莫哥洛夫向前方程可以得到

(11)

根據(jù)求解方程得到，節(jié)點a、b間連接狀態(tài)由斷開到連接的概率為

(12)

則節(jié)點a、b相遇概率值為

(13)

式中：ict′為平均間隔時間，td為當前時刻距上一次相遇的間隔時間。

節(jié)點a、b間轉發(fā)能力函數(shù)記為for(a,b)

(14)

2 NMAR路由機制

為提高消息的傳輸效率，降低網絡開銷，本文提出了一個感知節(jié)點間關系強度的路由機制NMAR。該路由機制消息傳輸流程如圖4所示，描述如下：

(1)當兩節(jié)點進入彼此通信半徑內(相遇)，比較相遇節(jié)點是否為消息目的節(jié)點。若是則直接將消息轉發(fā)給目的節(jié)點，同時刪除該消息副本；

(2)若相遇節(jié)點不是消息的目的節(jié)點且攜帶消息的副本，則不轉發(fā)消息；

(3)若相遇節(jié)點不是消息的目的節(jié)點且沒有攜帶消息的副本，計算節(jié)點關系強度函數(shù)，并且與當前節(jié)點的函數(shù)值進行比較，當相遇節(jié)點關系強度值大于當前節(jié)點時，進入步驟(4)，否則不轉發(fā)消息。

(4)計算節(jié)點轉發(fā)能力值，并與當前節(jié)點能力值進行比較，當相遇節(jié)點大于當前節(jié)點時，將消息轉發(fā)給中繼節(jié)點，否則不轉發(fā)消息。

圖4 算法實現(xiàn)流程

3 仿真與分析

本文采用機會網絡環(huán)境模擬器ONE(opportunistic network environment)[9]對消息投遞率、開銷比、平均傳輸時延等網絡性能指標進行仿真分析。

3.1 仿真結果與分析

NMAR路由算法選擇運動能力和投遞能力更強的節(jié)點來轉發(fā)消息，算法偽代碼見表1。

仿真中引入考慮節(jié)點投遞能力的Prophet路由算法[10]，控制網絡開銷的SprayandWait路由算法[11](SnW)和考慮節(jié)點運動的DPER進行仿真驗證。仿真參數(shù)設置見表2。

3.2 網絡性能與節(jié)點緩存大小

設置網絡節(jié)點的數(shù)目為120，節(jié)點緩存空間變化范圍為5 M至50 M，變化間隔為5 M。仿真結果如圖5～圖7所示。

由圖5可以看出網絡中消息投遞率隨節(jié)點緩存的增加而提高，在達到最佳效果后趨于平穩(wěn)，然后消息投遞率不再受緩存增加的影響。相比于Prophet、SprayandWait和DPER路由算法，NMAR的消息投遞率分別提升了9.55%、5.72%和3.21%。圖6為路由算法的平均傳輸時延與節(jié)點緩存關系的對比圖，平均傳輸時延隨著節(jié)點緩存的增加呈現(xiàn)出先下降后上升的趨勢直至趨于平穩(wěn)狀態(tài)，NMAR路由算法的平均傳輸時延低于Prophet、SprayandWait和DPER路由算法。圖7描述了網絡的開銷比隨節(jié)點緩存增加的變化趨勢。從整體看，4種路由算法的開銷比隨著節(jié)點緩存的增加而減小，逐步趨于平穩(wěn)，NMAR路由算法的開銷比整體較小，優(yōu)于其它3種路由算法。

表1 NMAR路由算法實現(xiàn)代碼

表2 仿真參數(shù)設置

圖5 投遞率隨節(jié)點緩存大小的變化

圖6 平均時延隨節(jié)點緩存大小的變化

圖7 開銷比隨節(jié)點緩存大小的變化

3.3 網絡性能與節(jié)點數(shù)目

結合上一小節(jié)的仿真實驗結果，將節(jié)點緩存空間大小設置為38 M，其它仿真參數(shù)保持不變，節(jié)點數(shù)目變化范圍為40到200，增幅間隔為40。仿真結果如圖8～圖10所示。

圖8 消息投遞率隨節(jié)點數(shù)量的變化

圖9 平均時延隨節(jié)點數(shù)量的變化

圖10 開銷比隨節(jié)點數(shù)量的變化

從圖8可以看出消息投遞率隨節(jié)點數(shù)目增加而增加，相比于Prophet、SprayandWait和DPER路由算法，NMAR的消息投遞率優(yōu)于其它3種路由算法，分別提升了15.47%、12.02%和5.68%。由圖9可以看出隨著網絡節(jié)點數(shù)目的增加，消息平均傳輸時延不斷減小后趨于平穩(wěn)，NMAR的平均傳輸時延低于Prophet、SprayandWait和DPER路由算法。圖10描述了網絡開銷比隨節(jié)點數(shù)目增加的變化趨勢。從整體看，4種路由算法的開銷比均隨著節(jié)點數(shù)目的增加表現(xiàn)出上升趨勢。從局部看，NMAR路由算法的開銷比整體較小，優(yōu)于其它3種路由算法。

4 結束語

本文研究了延遲網絡節(jié)點關系強度，通過節(jié)點連通狀態(tài)的分析給出了節(jié)點強度關系的感知和度量方法，進一步給出了基于節(jié)點關系強度感知的延遲容忍網絡路由機制，該機制利用運動過程中相遇節(jié)點數(shù)量的增減描述節(jié)點間關系強度的變化，同時依據(jù)節(jié)點之間的連接狀態(tài)預測節(jié)點相遇概率，并結合節(jié)點關系評估節(jié)點的轉發(fā)能力，根據(jù)節(jié)點關系強度和轉發(fā)能力值選擇合適的轉發(fā)節(jié)點，優(yōu)化消息的傳輸，提升消息的轉發(fā)效率。仿真實驗驗證了該路由機制具有很高的擴展性，提高了消息傳輸效率，改善了網絡性能，提升了資源的利用率。

[1]Khabbaz M J,Assi C M,Fawaz W F.Disruption-tolerant networking:A comprehensive survey on recent developments and persisting challenges[J].Communications Surveys & Tuto-rials,IEEE,2012,14(2):607-640.

[2]Cao Yue,Sun Zhili.Routing in delay/disruption tolerant networks:A taxonomy,survey and challenges[J].IEEE Communications Surveys & Tutorials,2013,15(2):654-677.

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

[4]Abdelkader T,Naik K,Nayak A,et al.SGBR:A routing protocol for delay tolerant networks using social grouping[J].IEEE Transactions on Parallel and Distributed Systems,2013,24(12):2472-2481.

[5]WU Dapeng,KONG Xiaolong,ZHANG Hongpei,et al.Social attributes aware data forwarding strategy in intermittently connected wireless networks[J].Journal on Communications,2015,36(1):42-51(in Chinese).[吳大鵬,孔曉龍,張洪沛,等.社會屬性感知的間斷連接無線網絡數(shù)據(jù)轉發(fā)策略[J].通信學報,2015,36(1):42-51.]

[6]Wang En,Yang Yongjian,Li li.A clustering routing method based on semi-Markov process and path-finding strategy in DTN[J].Chinese Journal of Computers,2015,38(3):483-499.

[7]Wang E,Yang Y,Chen X,et al.The improved algorithm of spray and wait routing protocol in delay tolerant network[J].International Journal of Advancements in Computing Technology,2013,5(7):238-245.

[8]Bulut E,Geyik S C,Szymanski B K.Utilizing correlated node mobility for efficient DTN routing[J].Pervasive and Mobile Computing,2014,13(4):150-163.

[9]Ayub Q,Rashid S,Zahid M S M,et al.Contact quality based forwarding strategy for delay tolerant network[J].Journal of Network and Computer Applications,2014,39(1):302-309.

[10]Mota V F S,Cunha F D,Macedo D F,et al.Protocols,mobility models and tools in opportunistic networks:A survey[J].Computer Communications,2014,48(8):5-19.

[11]ZHANG Feng,WANG Xiaoming,ZHANG Shanshan.Buffer aware ProPhet routing algorithm for opportunistic networks[J].Computer Engineering and Design,2015,36(5):1145-1149(in Chinese).[張峰,王小明,張珊珊.機會網絡中考慮緩存的ProPhet路由算法[J].計算機工程與設計,2015,36(5):1145-1149.]