基于社會環(huán)境的一種優(yōu)化Prophet延遲容忍網絡路由算法

萬 冰

（摩托羅拉系統(tǒng)（中國）有限公司 成都分公司，四川 成都 611731）

基于社會環(huán)境的一種優(yōu)化Prophet延遲容忍網絡路由算法

萬 冰

（摩托羅拉系統(tǒng)（中國）有限公司 成都分公司，四川 成都 611731）

在移動智能終端普及的今天，延遲容忍網絡作為數(shù)據(jù)的補充傳輸方案具有重要的意義。在社會環(huán)境中，節(jié)點移動規(guī)律具有明顯周期性，Prophet路由算法在該類場景中效果較好。因此文章提出了一種基于加強傳統(tǒng)概率的路由算法，其在工作日模型下對E Prophet算法進行了仿真實驗。實驗結果表明，所提出的E Prophet算法在該場景下優(yōu)于傳統(tǒng)的Prophet算法。

延遲容忍網絡；社會環(huán)境；移動規(guī)律；路由算法

延遲容忍網絡（（Delay Tolerant Network，DTN））又稱為容斷或容遲網絡，由多個移動對象攜帶具備無線通信能力的傳感器組成[1]。在延遲容忍網絡中數(shù)據(jù)利用節(jié)點之間相遇的機會進行轉發(fā)，因此這種“存儲—攜帶—轉發(fā)”的傳輸方式可以較少地依賴于基礎設施，網絡中的鏈接頻繁中斷[2]。因此從延遲容忍網絡出現(xiàn)就廣泛圍繞挑戰(zhàn)性環(huán)境中的應用討論，如戰(zhàn)場環(huán)境[3]、車輛交通環(huán)境[4]、水下場景[5]等。隨著智能移動終端的普及，在城市區(qū)域中利用移動智能終端所構建的延遲容忍網絡具有傳輸成本低、移動性支持好、對通信基礎設施需求較低等優(yōu)勢。不同場景中節(jié)點的移動規(guī)律不一致，導致現(xiàn)有的延遲容忍網絡路由算法不能在城市場景中發(fā)揮網絡應有的性能[6]。

前期研究表面，社會環(huán)境中節(jié)點具有一定的周期移動規(guī)律性，所以基于概率預測的Prophet在社會環(huán)境中具有較好的表現(xiàn)[7]。

為了提升延遲容忍網絡在城市環(huán)境中的性能表現(xiàn)，本文提出一種適用于社會環(huán)境的優(yōu)化Prophet路由算法（Enhanced Prophet，E Prophet），E Prophet算法中的衰老因子符合城市環(huán)境中節(jié)點的相遇規(guī)律。本文利用工作日模型（Working Day Mode，WDM），建立了趨于真實社會環(huán)境節(jié)點的移動狀態(tài)，并在多次實驗的基礎上，觀察了隨時間變化下兩種算法在社會環(huán)境中的網絡關鍵性能指標，并對結果進行了相關的分析。

1 Prophet路由算法簡介

Prophet算法由A·Lindgren等[8]提出，其基本思想是在節(jié)點中加入冗余知識，以便記錄節(jié)點之間的相遇概率。在Prophet算法中，每個節(jié)點都存在一個概率據(jù)測矩陣，依據(jù)所設計的策略進行概率預測值的更新。如節(jié)點a與節(jié)點b的相遇概率定義如式1所示。

其中P(a,b)old表示上一個狀態(tài)的相遇概率，Pinit表示初始化概率。在算法中狀態(tài)值P(a,b)s1與P(a,b)s2分別表示兩個時間狀態(tài)下節(jié)點之間概率預測值。狀態(tài)S1，S2兩個狀態(tài)之間預測值變化函數(shù)，它基于算法中所設計的衰老因子γ的設計。當節(jié)點a與節(jié)點b分開后，由于衰老因子的存在，導致兩個節(jié)點之間的概率預測值持續(xù)減少。其衰減計算函數(shù)如式2所示。

式中γk因子是一個冪指數(shù)函數(shù)，其中0＜γ＜1，k為與時間相關整數(shù)。由于冪指數(shù)的存在，隨著時間的增加節(jié)點之間概率預測值會持續(xù)降低。通過這樣的設計，相互接觸較為頻繁的節(jié)點，其概率預測值會維持一個較為高的預測值。在社會環(huán)境中，由于節(jié)點之間的存在的社會屬性，因此可以用社交圖（Social Graph）（見圖1）表現(xiàn)節(jié)點之間的接觸或社交情況[9]。

圖1 社會環(huán)境中節(jié)點社交

基于圖1社會環(huán)境中的社交圖可以發(fā)現(xiàn)，在網絡中節(jié)點之間的接觸規(guī)律受制于節(jié)點的社交圈。而在社會網絡中社交圈的存在，也表明了節(jié)點與節(jié)點之間的接觸概率并不服從均勻分布。由此，Prophet算法中的概率預測方式，在社會環(huán)境的延遲容忍網絡中符合節(jié)點的相遇規(guī)則，因此也可以得到較好的表現(xiàn)。

2 Prophet算法在社會環(huán)境下延遲容忍網絡中的問題

基于概率預測的Prophet算法從提出到現(xiàn)在并沒有針對的場景，但是其概率預測的方式，較為適應一些具有相遇規(guī)律的場景，因此在基于社會網絡的延遲容忍網絡中，得到了眾多學者的關注[10]。在社會環(huán)境中，具有通信能力的移動節(jié)點往往由移動智能終端與攜帶智能終端的車輛等組成，因此移動節(jié)點同樣具有社會屬性。在社會環(huán)境中，白天人們活動，具有一定的目的性與規(guī)律性，如上班、逛街等。晚上人們在家休息活動范圍局限在一個較小的范圍當中，甚至不移動。這也就構成了社會環(huán)境中節(jié)點移動的基本規(guī)律。通過Infocom數(shù)據(jù)集（41節(jié)點）在72小時采集的相遇數(shù)據(jù)如圖2所示。

圖2 Infocom數(shù)據(jù)集在72小時的相遇規(guī)律

基于圖1可以看到，節(jié)點在不同的時間段中相遇次數(shù)具有較大的差別。節(jié)點相遇具有一定的周期性。在一個周期中，節(jié)點具有高相遇次數(shù)期間與低相遇次數(shù)期間。低相遇次數(shù)期間，網絡中節(jié)點總體的相遇次數(shù)趨近于零，這也是人們晚上休息所導致的。在高相遇次數(shù)期間，節(jié)點相遇次數(shù)出現(xiàn)了較大的波動，可以理解為在社會環(huán)境中人們的早高峰與晚高峰。從周期上面看，其總體的相遇規(guī)律可以由式3所示。

fn(t)=f(t+NT) （3）

其中，fn(t)表示在當前時間網絡中節(jié)點相遇次數(shù)，N為整數(shù)，T為12小時常量。可以看到，在低相遇期間，時間持續(xù)較長為12小時，因此在Prophet路由算法中，由于如式2中衰老因此的存在，預測矩陣中節(jié)點之間的預測概率值，會在這個低相遇次數(shù)周期中由于節(jié)點間相遇次數(shù)的減少而持續(xù)降低。當節(jié)點相遇次數(shù)再次進入到高相遇周期時，節(jié)點之間的預測概率值都處于一個較低的水平，節(jié)點之間的預測概率需要一個重新收斂的過程。因此，Prophet算法在社會場景中，無法較好地適應這種節(jié)點的相遇周期，影響了算法的性能發(fā)揮。

3 一種優(yōu)化的E Prophet路由算法

基于Prophet在社會環(huán)境中無法較好適應低相遇次數(shù)周期與高次數(shù)相遇周期的問題，文章提出了一種優(yōu)化的Prophet路由算法。重新設計了衰老因子的策略方式。同樣路由算法基于節(jié)點之間相遇的情況，其算法的描述如下。

步驟1：網絡中全體節(jié)點建立相遇概率矩陣E，以存儲全體網絡節(jié)點的預測概率值。

步驟2：基于式1進行相遇概率連續(xù)狀態(tài)的更新。

步驟3：基于式4進行相遇概率衰減。

式中，T1表示在低相遇次數(shù)周期中時間，反之T2表示在高相遇周期中時間。衰老方式計算在不同節(jié)點所處時間段中存在區(qū)別。其中K1與K2如式5—6所示。

式中tnow表示網絡運行的當前時間，tT為上一更新時間，β為常量。

其中定義時間周期判斷(tnow/Thour)/δ為真時，為T2時間區(qū)間，反之亦然。

4 仿真環(huán)境與實驗結果

由于真實數(shù)據(jù)集的節(jié)點過少，或部分真實數(shù)據(jù)集節(jié)點移動范圍過小，因此這里選擇由F.EKman等提出的工作日模型（Working Day Movement Model，WDM）[11]。

其仿真場景中節(jié)點分組如表1所示。

表1 節(jié)點分組類型

仿真場景中選擇了其關鍵仿真參數(shù)如表2所示。

表2 關鍵仿真參數(shù)

設置與社交環(huán)境較為近似的仿真場景后，對延遲容忍網絡中關鍵指標如網絡投遞成功率、平均投遞延遲與網絡負載比3個關鍵指標與傳統(tǒng)Prophet指標進行對比分析如圖3—5所示，以觀察優(yōu)化的Prophet算法與Prophet算法性能。

圖3 兩種算法的網絡投遞成功率

圖4 兩種算法的平均投遞延遲

圖5 兩種算法的網絡負載比

通過兩種算法在3種延遲容忍網絡的關鍵指標中對比發(fā)現(xiàn)，所提出的E Prophet路由算法在社會環(huán)境中明顯優(yōu)于原始的Prophet算法。由于WDM模型中節(jié)點相遇分布在時間維度的劇烈波動，也導致了3種指標隨著時間出現(xiàn)了較為劇烈的波動。

5 結語

隨著智慧城市的發(fā)展，社會環(huán)境中對數(shù)據(jù)的需求具有多種多樣的解決方案，而延遲容忍網絡作為數(shù)據(jù)傳輸?shù)囊环N解決方案具有移動性支持強、成本低、系統(tǒng)抗災性強的特點。文章提出的E Prophet算法一定程度上提升了Prophet算法在社會環(huán)境中延遲容忍網絡的系統(tǒng)性能，有利于提高基于延遲容忍網絡的應用系統(tǒng)的性能。

[1]GAO L, YU S, LUAN T H, et al. Routing Protocols in Delay Tolerant Networks[M].German：Springer International Publishing, 2015.

[2]MAYER C P, WALDHORST O P. Offloading Infrastructure Using Delay Tolerant Networks and Assurance of Delivery[J]. Jochen Furthmüller, 2011（1）：1-7.

[3]DINI G, DUCA A L. Towards a reputation-based routing protocol to contrast blackholes in a delay tolerant network[J]. Ad Hoc Networks, 2012（7）：1167-1178.

[4]UCHIDA N, ITO K, HIRAKAWA G, et al. Vehicle-to-Vehicle Delay Tolerant Networks with Area of Interest for Road Surveillance System[C]. Poland：International Conference on Broadband and Wireless Computing, Communication and Applications[A] .Computer Society, 2015：466-471.

[5]劉燦.容延容斷網絡中基于負載均衡的路由算法的研究[D].長沙：國防科學技術大學，2011.

[6]李文藻，林鋒.節(jié)點緩沖區(qū)大小對城市部署的DTN網絡的影響分析[J].無線互聯(lián)科技，2014（10）：117-119.

[7]MOREIRA W，F(xiàn)ERREIRA R，CIRQUEIRA D，et al. SocialDTN：a DTN implementation for digital and social inclusion[C].ACM MOBICOM Workshop on Lowest Cost Denominator NETWORKING for Universal Access. ACM，2013：25-28.

[8]LINDGREN A, DORIA A, SCHELéN O. Probabilistic Routing in Intermittently Connected Networks[J]. Acm Sigmobile Mobile Computing & Communications Review, 2004（3）：19-20.

[9]BONNEAU J, ANDERSON J, ANDERSON R, et al. Eight friends are enough：social graph approximation via public listings[J]. ACM EUROSYS Workshop on Social Network Systems, 2009（3）：13-18.

[10]SCHURGOT M R, COMANICIU C, JAFFRES R K. Beyond traditional DTN routing: social networks for opportunisticcommunication[J]. Communications Magazine, 2012（7）：155- 162.

[11]EMAN F, KER, NEN A, et al.Working day movement model[C].ACM Wi-Fi Multimedia, 2008：33-40.

An optimized Prophet delay tolerant network routing algorithm based on social environment

Wan Bing
（Chengdu Branch of Motorola Systems（China）Co., Ltd., Chengdu 611731, China）

With the popularity of the mobile terminal today, as a supplement to the data transmission project, delay tolerant network is of great significance. In the social environment, node movement law has obvious periodic node movement, prophet routing algorithm has better effect in the scene. Therefore, this paper proposes a kind of routing algorithm based on .strengthening traditional probability. The E Prophet algorithm is simulated under the mode during the working day.The simulation results show that the proposed E Prophet algorithm is superior to the traditional Prophet algorithm in this scenario.

delay tolerant network; social environment; movement law; routing algorithm

四川省科技廳軟科學項目；項目編號：2014ZR0146。四川省教育廳重點項目；項目編號：16ZA0218。

萬冰（1978— ），女，四川成都，碩士；研究方向：計算機通信與網絡研究設計。