DTN中基于時間因素的擁塞感知路由算法

良 梓 ，任哲坡 ，吳曉軍 ，

1.陜西師范大學 計算機科學學院，西安 710062

2.西北工業大學 自動化學院，西安 710072

1 引言

延遲容斷網絡[1]（Disruption Tolerant Network）的概念由美國國防部高級研究局DARPA在2004年提出，主要研究Internet交互式應用協議，來解決Internet通信時連接頻繁斷開的問題。Kevin Fall等科學家在SIGCOMM會議上首次提出DTN架構，它是一種位于區域網絡（各種不同類型的網絡，包括因特網）之上的覆蓋網，以克服受限網絡環境[2-4]中網絡斷開頻繁、延遲高和異構性強[5]等問題。

在DTN網絡中，網絡節點的移動性強且緩存資源有限，網絡拓撲結構呈動態變化[6]，通常不存在一條完整的端到端路徑，這導致網絡存在傳輸延遲大，投遞效率低等問題[7]。因此，傳統路由協議不能在DTN網絡中取得理想效果，DTN路由協議的研究，對提高DTN網絡性能具有重要意義。

2 問題描述

目前，在DTN的研究中，路由算法主要分為單拷貝路由協議[8]和多拷貝路由協議。典型的單拷貝路由協議有Direct Delivery和First Contact，這兩種路由協議雖然網絡開銷小、能耗低，但報文到達信宿節點的延遲大、概率低，無法保障網絡性能。多拷貝路由協議中最具代表的路由協議有蔓延路由（Epidemic）[9]、散發等待路由（Spray and Wait）[10]和概率路由（Prophet）[11]。蔓延路由采用多副本洪泛機制傳遞報文，源節點對報文的下一跳節點的選擇不做任何限制，其缺點是會導致網絡中存在大量冗余副本。散發等待路由限制了轉發的報文副本數量，避免了冗余報文的傳輸，但在轉發報文時，直接將報文轉發給最先遇到的節點，具有一定盲目性。概率路由基于節點相遇的歷史信息定義轉發概率，通過轉發概率來選擇下一跳節點，對下一跳節點給定一定的限制，但轉發概率并不能完全代表報文實際遞交的概率，節點相遇并不一定能保證報文轉發成功。

針對上述存在的問題，目前已有一些改進算法。如文獻[12]依據節點之間的歷史接觸成功率獲取網絡狀態信息，在轉發決策時引入接觸成功率的影響，降低網絡開銷，文獻[13]采用根據節點能量消耗改進轉發概率，降低傳輸延遲，文獻[14]根據節點間相遇概率對節點進行分簇，提出簇間轉發算法，提高了消息投遞率。但這些算法都不能在降低網絡延時和開銷的同時提高網絡投遞率。本文從時間因素的角度進行如下分析。首先，報文傳輸是需要一定時間的，節點的移動會導致正在傳輸的報文中斷，所以，轉發概率還需考慮節點相遇持續時間對報文完整傳遞的影響。另外，時間因素對網絡擁塞也有一定影響，因為對于某些數據包會存在以下兩種情況：一種是該包傳輸延時大，即節點間斷開持續時間長，被成功傳遞的可能性小；另一種是經本節點的路徑很難達到目的地，導致該包跳數較多，已生存時間較長。以上兩種情況中的數據包都應該被丟棄。因此，可以通過計算節點斷開持續時間、節點本身蘊含的跳數值和TTL值等信息來定義一個報文保存率，在網絡擁塞時，通過該報文保存率衡量報文被保存的價值，以擁塞感知自適應的方式來優化路由算法。基于以上分析，本文結合概率路由和散發等待路由的各自優點，提出基于時間因素的擁塞感知路由算法（Congestion-Aware Routing Algorithm based on time factor，CARA 路由算法）。

3 CARA路由算法

3.1 算法思想

CARA算法采用改進的轉發概率來進行路由選擇，以擁塞感知自適應的方式進行擁塞控制。主要改進有以下三方面：

（1）報文轉發方式。CARA算法中，節點之間轉發報文的條件由轉發概率確定。為提高估算精準度，估算傳輸概率時考慮時間因素對轉發概率的影響，優先選擇轉發概率較高的節點作為中繼節點。

（2）報文轉發數目。報文轉發數目按照轉發概率動態分配。節點轉發概率越高，獲得的報文數目也越多，反之，則獲得的報文數目越少。

（3）擁塞控制。CARA算法中，根據節點斷開持續時間、節點的跳數(Hopsm)、TTL值來定義報文保存率，衡量報文應被保存的價值大小。在報文轉發過程中，先進行擁塞檢測，若無擁塞，則轉發報文；若擁塞，則執行擁塞避免，依次丟棄報文保存率小的報文，緩解擁塞，再轉發報文。

3.2 路由過程

3.2.1 改進的轉發概率

概率路由是根據節點歷史相遇信息來預測節點移動方式，在節點相遇時，交換擁有相遇概率信息的摘要矢量，然后選擇下一跳轉發的節點[10]。本文將該算法進行改進，考慮節點相遇持續時間對轉發概率的影響，通過分析兩個節點建立連接的方式，定義需要提取的時間參數。

定義1（相遇時間）節點A和B在0時刻從初始位置開始移動，它們第一次到達對方通信范圍內所需要的時間。

Sa(t)表示節點a在t時刻在網絡中的位置，K是節點通信范圍。

定義2（相遇持續時間）節點A和B最初在信息通信范圍之外，假設在0時刻，到達對方的通信范圍內，這兩個節點在移出通信范圍之前保持聯系的時間為相遇持續時間。

定義3（相遇間隔時刻）在0時刻節點A和B在對方通信范圍之內，在t1時刻移出通信范圍，定義相遇間隔時刻為t1。

定義4（斷開持續時間）A和B兩節點再次到達對方通信范圍需要的時間。

改進的轉發概率變化公式分三種：概率更新公式、衰減公式和傳遞公式。

（1）概率更新公式：

（2）概率衰減公式：

（3）概率傳遞公式：

按照上述轉發概率的變化，節點維護一張轉發概率表，根據此表選擇下一跳節點。

3.2.2 散發階段

（1）S（源節點）要發送消息到目的節點R，S初始化報文拷貝數L(L＞1)。

（2）S（或中繼節點A）與中繼節點B相遇時，更新各自摘要矢量并計算轉發概率，PSR（S到達目的節點R的概率）＜PBR（B到達R的概率），則S將報文轉發給B，如果PSR≥PBR，則不轉發，繼續尋找下一節點。

（3）S報文數目為L，轉發給節點B的報文數目為L′，若L＞1，L′=PSR?L。

（4）判斷是否發生擁塞，如擁塞，則進行擁塞避免，如無擁塞，數據發送成功。

3.2.3 等待階段

（1）判斷散發階段是否與信宿節點相遇，若遇到，則遞交報文，終止傳輸；若沒遇到，按上述方式選擇中繼節點，繼續散發報文。

（2）隨著報文的散發，報文副本數減小。若當前中繼節點上該報文副本數為1，則進行（3），若副本數不為1，繼續散發，進行（2）。

（3）不再散發報文，直到該節點遇到信宿節點時才遞交，即轉為直接傳輸模式。

（4）判斷是否發生擁塞，如擁塞，則進行擁塞避免，如無擁塞，數據發送成功。

3.2.4 擁塞檢測及避免

定義5（報文保存率）反映報文應被保存的價值大小。

報文保存率見公式（9）：

其中，公式（9）中w1，w2為權重系數，Qm為報文m的質量，Zm為報文m的生存時間分量。公式（10）中N表示全網節點數，Hopsm表示報文m的轉發次數，即跳數。公式（11）中TTL為報文m的生存時間，δab為斷開持續時間，可由公式（3）、（4）求出。由公式可見，Hopsm越大，TTL越小，δab越大，Pm越小，報文保存率越小，可被成功投遞的可能性就越小。當網絡擁塞時，丟棄報文保存率小的報文緩解擁塞。

擁塞策略流程如圖1所示。

圖1 擁塞策略流程

4 仿真及性能分析

4.1 仿真參數

為了檢驗CARA算法的有效性，本文采用離散事件模擬器ONE[15]（Opportunity Networking Environment）對CARA算法進行仿真。本文采用ONE中自帶的芬蘭首都赫爾辛基（Helsinki）地圖[16]，仿真場景大小為4 500 m×3 400 m。仿真網絡共126個節點，分為6組，第一、三組為行人節點，第二組為出租車節點，第四、五、六組為有軌電車節點，具體如表1所示。消息大小為350 kB，傳輸速率250 kB/s，仿真時間20 h，數據包產生間隔時間30～40 s，采用基于地圖路徑方式[17-18]移動。實驗仿真參數見表1。

表1 實驗仿真參數

4.2 仿真結果及分析

為了全面驗證CARA算法，本文通過仿真實驗，將Prophet算法、二分散發等待路由（BSW）算法、Epidemic算法、CS-DTN[14]同CARA算法相比較，分析在報文遞交率、平均延遲及網絡開銷率三方面[19-20]隨時間的變化情況。

（1）報文遞交率

報文遞交率可以衡量路由算法對報文的傳遞能力，其定義如下。

實驗結果如圖2所示。從圖2中可以看出，Epidemic算法在起始階段遞交率高，增加速度快，但到10 000 s之后，開始逐漸降低，這是由于Epidemic算法的洪泛機制易使網絡擁塞所致。圖中還可以看出，CARA算法比Prophet算法、CS-DTN算法的遞交率都有了明顯提高，這是由于本文在Prophet算法的基礎上考慮了節點持續連接時間對遞交概率的影響，同時，擁塞感知策略丟棄了節點緩存中保存率小的報文，使到達目的節點可能性高的報文得以保存和轉發，從而提高了全網報文遞交率。

圖2 遞交率隨時間的變化

（2）平均延遲

平均延遲用來衡量算法的性能，其定義如下。

實驗結果如圖3所示。從圖3中可以看出，Epidemic算法的平均延遲開始較低，但隨時間的增加延遲逐漸增大，這是因為Epidemic算法的洪泛機制導致節點處報文擁塞無法遞交，而使得延遲增大。Prophet算法、CS-DTN算法同CARA算法相比，CARA算法延遲要小于前兩個算法。這是因為CARA算法限制了對中繼節點的選擇，使報文轉發概率不會隨節點之間相遇頻率的增加而增加，所以延遲逐漸增加，但隨著時間的增加，這種增加的趨勢逐漸減小，平均延時趨于穩定。這是由于CARA算法中采用擁塞感知機制，拋棄那些持續斷開時間很長的報文，使得全網平均延遲變小。

（3）開銷率

開銷率可以用來衡量路由算法的總體傳輸性能，其定義如下。

實驗結果如圖4所示。從圖4中看出，Epidemic算法開銷最大，這是因為Epidemic算法的洪泛機制使報文遞交效用低，所以開銷大。BSW算法在源端限制報文拷貝數，所以其開銷率小且穩定。從圖4中可以看出，CS-DTN算法比BSW算法的開銷大，這是因為CS-DTN算法中，消息不斷地向中心性高的節點累計，簇間的轉發導致開銷大。而CARA算法開銷最小，這是因為CARA算法合理地丟棄冗余報文，增大了成功遞交數據包數量，減小了網絡中冗余報文的存儲和轉發，進而減小網絡開銷。

圖4 開銷率隨時間的變化

5 結語

本文分析了時間因素對路由選擇和網絡擁塞的影響，提出了一種基于時間因素的擁塞感知路由算法CARA。考慮節點相遇持續時間對報文完整傳遞的影響，改進了傳統概率路由的轉發概率，根據改進的轉發概率動態分配轉發報文，同時定義報文保存率來衡量報文的保存價值，以擁塞感知的方式實現擁塞控制的優化。實驗表明，與其他算法相比，CARA算法在降低網絡延遲和開銷，提高網絡投遞率上，優越性明顯。

[1]Fall K.A delay tolerant network architecture for challenged Internets[C]//SIGCOMM，2003：27-34.

[2]Nichols R A，Hammons A R.DTN-based free-space optical and directional RF networks[C]//Military Communications Conference，2008：1-6.

[3]Luo Peien，Huang Hongyu，Li Minglu，et al.Performance evaluation of vehicular DTN routing under realistic mobility models[C]//Wireless Communications and Networking Conference.Las Vegas，NV：[s.n.]，2008：2206-2211.

[4]Chan C Y M，Motani M.An integrated energy efficient data retrieval protocol for underwater delay tolerant net-works[C]//IEEE Oceans.Washington DC：IEEE，2007：1-6.

[5]樊秀梅，單志廣，張寶賢，等.容遲網絡體系結構及其關鍵技術研究[J].電子學報，2008，36（1）：161-170.

[6]Daly E M，Hahr M.The challenges of disconnected delay tolerant MANETs[J].Ad Hoc Networks，2010，8：241-250.

[7]Whitbeck J，Conan V.HYMAD：hybrid DTN-MANET routing for dense and highly dynamic wireless networks[C]//IEEE WoWMoM Workshop on Autonomic and Opportunistic Communications，2010.

[8]Jain S，Fall K，Patra R.Routing in a delay tolerant network[C]//Proceedings of the 2004 Conference on Applications，Technologies，Architectures，and Protocols for Computer Communications，NewYork，2004：145-158.

[9]Vahdat A，Becker D.Epidemic routing for partially connected ad hoc networks[R].San Diego：University of Carolina，2000.

[10]Spyropoulos T，Psounis K，Raghavendra C.Spray and wait，an efficient routing scheme for intermittently connected mobile networks[C]//WDTN’05，2005：252-259.

[11]Lindgreny A，Doria A，Schelen O.Probabilistic routing in intermittentlyconnectednetworks[J].ACM SIGMOBILE Mobile Computing and Communications Review，2003，7（3）：19-20.

[12]付凱，夏靖波，尹波.DTN中一種網絡狀態感知的概率路由算法[J].小型微型計算機系統，2013，34（1）：145-149.

[13]劉唐，彭艦，楊進.異構延遲容忍移動傳感器網絡中基于轉發概率的數據傳輸[J].軟件學報，2013，24（2）：215-229.

[14]張振京，金志剛，舒炎泰.基于節點運動預測的社會性DTN高效路由[J].計算機學報，2013，36（3）：626-635.

[15]TKK/COMNET.Project page of the ONE simulator[EB/OL].[2012-12-11].http：//www.netlab.tkk.fi/tutkimus/dtn/theone.

[16]Keranen A，Ott J，Karkkainen T.The ONE simulator for DTN protocol evaluation[C]//Proceedings of the 2nd International Conference on Simulation Tools and Techniques，2009：1-10.

[17]Keranen A，Ott J.Increasing reality for DTN protocol simulations[R].[S.l.]：Networking Laboratory，Helsinki University of Technology，2007.

[18]Peng Min.Research on mobility model and routing in delay tolerant network[D].Hefei：University of Science and Technology of China，2010.

[19]Ahmed S，Kanhere S.Cluster-based forwarding in delay tolerant public transport networks[C]//Proceedings of the 32nd IEEE Conference on Local Computer Networks，2007：625-634.

[20]Li Yun，Chen Xinjian，Liu Qilie，et al.A novel congestion controlstrategy in delay tolerantnetworks[C]//IEEE 2010 2nd International Conference on Future Networks，China，2010：233-237.