一種基于連接持續(xù)時間預(yù)測的DTN路由算法

摘 要：DTN是一種新型網(wǎng)絡(luò)體系結(jié)構(gòu)，其網(wǎng)絡(luò)頻繁斷裂的特點常常導(dǎo)致消息傳輸失敗，針對這個問題，提出一種基于連接持續(xù)時間預(yù)測的DTN路由算法CPBRA。利用相遇節(jié)點的移動速度、方向，傳輸范圍等信息預(yù)測節(jié)點的連接的持續(xù)時間，并依據(jù)消息的大小選擇適當?shù)南鬏斅窂?，以減少消息重傳的錯誤操作，提高資源利用率，有效地控制網(wǎng)絡(luò)開銷。

關(guān)鍵詞：容遲網(wǎng)絡(luò)；路由算法；連接持續(xù)時間；同伴節(jié)點；預(yù)測

中圖分類號：TP393.04

隨著微電子技術(shù)的發(fā)展，越來越多的新型無線網(wǎng)絡(luò)開始出現(xiàn)，如陸地移動網(wǎng)絡(luò)、軍事無線自組織網(wǎng)絡(luò)等。這些網(wǎng)絡(luò)存在共同的特點：間歇性連接、缺少端到端路徑、資源受限等。傳統(tǒng)的無線網(wǎng)絡(luò)傳輸模式要求通信源和目標節(jié)點之間存在至少一條完整的路徑，因而無法在這些網(wǎng)絡(luò)環(huán)境中運行。為了解決這些新型網(wǎng)絡(luò)中的通信問題，F(xiàn)all等科學(xué)家提出了容遲網(wǎng)絡(luò)[1]（Delay Tolerant Network，DTN）的架構(gòu)。DTN充分利用節(jié)點移動形成的通信機會，采用“存儲-攜帶-轉(zhuǎn)發(fā)”模式進行消息轉(zhuǎn)發(fā)。

由于DTN網(wǎng)絡(luò)拓撲的動態(tài)性，從而導(dǎo)致了鏈路間歇性斷裂而且中斷時間較長。如果消息在轉(zhuǎn)發(fā)過程中中斷鏈接，則直接導(dǎo)致消息傳輸失敗，必須等待鏈接成功后續(xù)傳，這樣使得DTN有限的資源被大量消耗。如果能在消息轉(zhuǎn)發(fā)前，先根據(jù)連接的容量大小、預(yù)測節(jié)點連接的持續(xù)時間等因素來選擇合適的消息進行轉(zhuǎn)發(fā)，將能有效地提高消息傳輸?shù)目煽啃?，減少消息重傳操作?；谝陨纤枷?，本文提出一種基于連接持續(xù)時間預(yù)測的路由算法（A Routing Algorithm Based on Contact-duration Prediction，CPBRA），該算法采用Binary Spray and Wait（BSW）[2]算法進行消息擴散傳輸，使消息快速傳達目標同伴節(jié)點，然后在目標同伴節(jié)點間進行消息分發(fā)以控制網(wǎng)絡(luò)開銷。

1 相關(guān)研究

目前DTN路由策略可以劃分為擴散性路由、概率性路由和確定性路由[2]。

擴散性路由通常使用復(fù)制技術(shù)，通過傳染轉(zhuǎn)發(fā)方式（epidemic forwarding，EF）[3將同一消息的多份拷貝注入網(wǎng)絡(luò)的一種簡單的擴散性算法，每個攜帶消息的節(jié)點將消息轉(zhuǎn)發(fā)給所有的鄰居節(jié)點。因此該算法較易產(chǎn)生較大網(wǎng)絡(luò)負載。BSW[2]算法在源節(jié)點指定消息允許的最大拷貝數(shù)為L，并使用基于二叉樹的方法來產(chǎn)生L份拷貝。相比EF算法，BSW控制了網(wǎng)絡(luò)開銷，有較好的可擴展性。

概率性路由的工作原理是通過節(jié)點相遇歷史信息對消息轉(zhuǎn)發(fā)的有用性進行評估，給每個節(jié)點賦予轉(zhuǎn)發(fā)效用值。PROPHET是一種比較有代表性的概率性路由，該算法使用節(jié)點相遇頻率來估算傳輸概率。當節(jié)點相遇時交換消息列表及傳輸概率向量，消息不斷地從傳輸概率小的節(jié)點轉(zhuǎn)發(fā)到傳輸概率大的節(jié)點，直到遇到目標節(jié)點。

確定性路由假設(shè)節(jié)點移動路徑等一些信息是可以確定或預(yù)知的，該類路由往往有較高的傳輸效率，但需要一些輔助設(shè)備（如GPS等）。基于位置路由算法（Location-Based Routing），使用GPS導(dǎo)航設(shè)備獲取節(jié)點的坐標。節(jié)點可以根據(jù)自身的坐標、目標節(jié)點坐標和潛在下一跳的坐標信息選擇最佳的傳輸路徑，有較高的傳輸效率，但是節(jié)點坐標信息在網(wǎng)絡(luò)中的擴散一定程度上增加了網(wǎng)絡(luò)負載。

2 CPBRA算法

2.1 網(wǎng)絡(luò)模型。網(wǎng)絡(luò)是由N個移動節(jié)點組成，一旦節(jié)點進入彼此通信范圍內(nèi)，便建立了連接，可以進行直接通信。當節(jié)點不在直接通信范圍內(nèi)，可以通過其它中間節(jié)點進行通信。節(jié)點的能量和緩存空間有限，節(jié)點間連接時間有限。目標節(jié)點有足夠的空間存儲接收的消息，只有傳輸中的消息受有限存儲空間的限制。每個節(jié)點可攜帶多個需要送達各目標節(jié)點的消息，同一消息的所有拷貝具有相同ID。

2.2 同伴節(jié)點。每個節(jié)點記錄與其他節(jié)點相遇的歷史信息，包括接觸頻率和相遇時的連通時長。根據(jù)這些信息，該節(jié)點每隔時間窗口T，利用公式（1）、（2）估算與其它節(jié)點的“相鄰值”。相鄰值表示節(jié)點的鄰近程度，相鄰值越大，表明節(jié)點接觸的可能性越大。每個節(jié)點選擇相鄰值最大的F個節(jié)點作為自己的同伴節(jié)點。

3 性能評估

3.1 仿真環(huán)境模擬設(shè)置。CPBRA中參數(shù)γ，α分別取0.98和0.2；tunit，T分別為4秒和180秒；參數(shù)F，L1，L2分別取6、6和8。BSW[2]中L取6。PROPHET[4]中Pinit為0.75，參數(shù)γ，β分別取0.98和0.25。

3.2 模擬結(jié)果與性能分析。本文從消息成功傳輸率和通信開銷方面分析路由算法的性能。圖1所示為網(wǎng)絡(luò)流量確定為3000的情況下，消息成功傳輸率隨著消息大小變化的曲線圖。從圖中可以看到CPBRA算法具有較高的消息成功傳輸率。當網(wǎng)絡(luò)中的消息大小較小時，BSW算法的消息成功傳輸率與CPBRA算法接近，但是，當消息大小變大時，BSW算法的消息成功傳輸率低于CPBRA算法。

4 結(jié)束語

本文提出的CPBRA算法是基于連接預(yù)測和控制復(fù)制思想，該算法對節(jié)點相遇所能維持的時間長度進行預(yù)測，估算連接容量，根據(jù)消息大小選擇合適的消息轉(zhuǎn)發(fā)路徑。從實驗結(jié)果可以看出，CPBRA在消息成功傳輸率和通信開銷方面都優(yōu)于其他算法。

參考文獻：

[1]FALL K.A delay-tolerant network architecture for challenged Internets[C].Proceedings of ACM SIGCOMM.New York：ACM Press，2003：27-34.

[2]曹元大，殷磊，馬明輝.容遲網(wǎng)絡(luò)中低資源消耗Advanced Epidemic路由算法[J].計算機應(yīng)用，2009（01）：281-283.

作者簡介：黃勇萍（1985-），碩士研究生，講師，研究方向：計算機網(wǎng)絡(luò)。

作者單位：廣西民族師范學(xué)院 數(shù)學(xué)與計算機科學(xué)系，廣西崇左 532200

基金項目：廣西民族師范學(xué)院2011年度資助項目（項目編號：XYYB2011023）。