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

胡 敏，王言通，黃春妮

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

0 引 言

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

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

1 節點關系強度感知

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

1.1 節點關系

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

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

圖1 節點運動場景

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

圖2 網絡中節點關系變化

1.2 節點關系強度感知

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

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

(1)

定義1 共遇節點變化度

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

(2)

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

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

定義2 節點連接度

節點連接度是指節點a與節點b的共遇節點數目與兩節點所有相遇節點數目的比值，記

(3)

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

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

定義3 相遇節點變化度

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

(4)

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

相遇節點變化度反映節點因移動造成相遇節點的變化程度，體現節點移動能力大小，變化度值越大，移動能力越強。

節點a，d的關系強度函數記為

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

(5)

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

1.3 節點的轉發能力

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

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

圖3 節點連接狀態變化過程

圖3中λ、μ分別表示節點間的連接狀態由斷開轉變為連通、由連通轉變為斷開的概率，設連接的持續時間與連接的間隔時間分別用ct、ict來表示，則λ=∑ct/∑t,μ=∑ict/∑t。

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

(6)

即狀態轉移矩陣為

(7)

節點a、b間連接狀態由斷開到斷開的轉移速率為

(8)

同理，連接狀態由連通到連通的轉移速率為

(9)

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

(10)

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

(11)

根據求解方程得到，節點a、b間連接狀態由斷開到連接的概率為

(12)

則節點a、b相遇概率值為

(13)

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

節點a、b間轉發能力函數記為for(a,b)

(14)

2 NMAR路由機制

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

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

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

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

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

圖4 算法實現流程

3 仿真與分析

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

3.1 仿真結果與分析

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

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

3.2 網絡性能與節點緩存大小

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

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

表1 NMAR路由算法實現代碼

表2 仿真參數設置

圖5 投遞率隨節點緩存大小的變化

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

圖7 開銷比隨節點緩存大小的變化

3.3 網絡性能與節點數目

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

圖8 消息投遞率隨節點數量的變化

圖9 平均時延隨節點數量的變化

圖10 開銷比隨節點數量的變化

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

4 結束語

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

[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).[吳大鵬,孔曉龍,張洪沛,等.社會屬性感知的間斷連接無線網絡數據轉發策略[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.]