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

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

中圖分類號(hào)：TP393.04

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

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

1 相關(guān)研究

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

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

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

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

2 CPBRA算法

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

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

3 性能評(píng)估

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算法具有較高的消息成功傳輸率。當(dāng)網(wǎng)絡(luò)中的消息大小較小時(shí)，BSW算法的消息成功傳輸率與CPBRA算法接近，但是，當(dāng)消息大小變大時(shí)，BSW算法的消息成功傳輸率低于CPBRA算法。

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

[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].計(jì)算機(jī)應(yīng)用，2009（01）：281-283.

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

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

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