良 梓 ，任哲坡 ，吳曉軍 ，

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

2.西北工業(yè)大學 自動化學院，西安 710072

1 引言

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

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

2 問題描述

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

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

3 CARA路由算法

3.1 算法思想

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

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

（2）報文轉(zhuǎn)發(fā)數(shù)目。報文轉(zhuǎn)發(fā)數(shù)目按照轉(zhuǎn)發(fā)概率動態(tài)分配。節(jié)點轉(zhuǎn)發(fā)概率越高，獲得的報文數(shù)目也越多，反之，則獲得的報文數(shù)目越少。

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

3.2 路由過程

3.2.1 改進的轉(zhuǎn)發(fā)概率

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

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

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

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

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

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

改進的轉(zhuǎn)發(fā)概率變化公式分三種：概率更新公式、衰減公式和傳遞公式。

（1）概率更新公式：

（2）概率衰減公式：

（3）概率傳遞公式：

按照上述轉(zhuǎn)發(fā)概率的變化，節(jié)點維護一張轉(zhuǎn)發(fā)概率表，根據(jù)此表選擇下一跳節(jié)點。

3.2.2 散發(fā)階段

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

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

（3）S報文數(shù)目為L，轉(zhuǎn)發(fā)給節(jié)點B的報文數(shù)目為L′，若L＞1，L′=PSR?L。

（4）判斷是否發(fā)生擁塞，如擁塞，則進行擁塞避免，如無擁塞，數(shù)據(jù)發(fā)送成功。

3.2.3 等待階段

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

（2）隨著報文的散發(fā)，報文副本數(shù)減小。若當前中繼節(jié)點上該報文副本數(shù)為1，則進行（3），若副本數(shù)不為1，繼續(xù)散發(fā)，進行（2）。

（3）不再散發(fā)報文，直到該節(jié)點遇到信宿節(jié)點時才遞交，即轉(zhuǎn)為直接傳輸模式。

（4）判斷是否發(fā)生擁塞，如擁塞，則進行擁塞避免，如無擁塞，數(shù)據(jù)發(fā)送成功。

3.2.4 擁塞檢測及避免

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

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

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

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

圖1 擁塞策略流程

4 仿真及性能分析

4.1 仿真參數(shù)

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

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

4.2 仿真結果及分析

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

（1）報文遞交率

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

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

圖2 遞交率隨時間的變化

（2）平均延遲

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

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

（3）開銷率

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

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

圖4 開銷率隨時間的變化

5 結語

本文分析了時間因素對路由選擇和網(wǎng)絡擁塞的影響，提出了一種基于時間因素的擁塞感知路由算法CARA?？紤]節(jié)點相遇持續(xù)時間對報文完整傳遞的影響，改進了傳統(tǒng)概率路由的轉(zhuǎn)發(fā)概率，根據(jù)改進的轉(zhuǎn)發(fā)概率動態(tài)分配轉(zhuǎn)發(fā)報文，同時定義報文保存率來衡量報文的保存價值，以擁塞感知的方式實現(xiàn)擁塞控制的優(yōu)化。實驗表明，與其他算法相比，CARA算法在降低網(wǎng)絡延遲和開銷，提高網(wǎng)絡投遞率上，優(yōu)越性明顯。

[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]樊秀梅，單志廣，張寶賢，等.容遲網(wǎng)絡體系結構及其關鍵技術研究[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，F(xiàn)all 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中一種網(wǎng)絡狀態(tài)感知的概率路由算法[J].小型微型計算機系統(tǒng)，2013，34（1）：145-149.

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

[14]張振京，金志剛，舒炎泰.基于節(jié)點運動預測的社會性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.