基于平均傳遞概率的容遲網(wǎng)絡(luò)路由算法的設(shè)計(jì)

摘 要：本文概要地總結(jié)了容遲網(wǎng)絡(luò)（DTN）的特點(diǎn)及其體系結(jié)構(gòu)，分析了目前比較常用的容遲網(wǎng)絡(luò)路由算法，并比較它們的優(yōu)劣。為了實(shí)現(xiàn)提高傳遞率、降低傳輸延遲、對(duì)節(jié)點(diǎn)緩存區(qū)進(jìn)行更加有效地管理的目的，采用ONE模擬器對(duì)設(shè)計(jì)的路由算法和已有的幾種常見(jiàn)的DTN路由算法進(jìn)行了基于特定場(chǎng)景的比較。仿真結(jié)果表明，該算法在節(jié)點(diǎn)的緩存區(qū)大小不同以及網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)目不同兩種情況下，傳遞率和路由開(kāi)銷(xiāo)比率的性能均優(yōu)于本文中用于比較的其它路由算法。

關(guān)鍵詞：容遲網(wǎng)絡(luò)；路由算法；平均傳遞概率

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

從某種意義上來(lái)說(shuō)，DTN的架構(gòu)為異構(gòu)互聯(lián)網(wǎng)關(guān)及代理提供了一種通用的方法，即使用存儲(chǔ)轉(zhuǎn)發(fā)的路由策略來(lái)克服通訊中斷的問(wèn)題。它提供的是一種類似電子郵件的服務(wù)，但增加了命名空間、路由策略以及安全保障的功能。無(wú)法支持這種架構(gòu)所需全部功能的節(jié)點(diǎn)可使用應(yīng)用層代理實(shí)現(xiàn)DTN應(yīng)用。容遲網(wǎng)絡(luò)的目標(biāo)是為性能差異極大的各類網(wǎng)絡(luò)提供互操作通信。由于它能夠連接性能差異很大、網(wǎng)絡(luò)類型非常不同的網(wǎng)絡(luò)，它對(duì)于底層協(xié)議棧的假設(shè)比TCP/IP協(xié)議更少，因而比因特網(wǎng)模型更為通用。

1 基于平均傳遞概率的路由算法基本原理

RAB-ADP算法實(shí)現(xiàn)的過(guò)程中，主要的屬性如表1所示。

2 算法仿真及結(jié)果分析

2.1 仿真場(chǎng)景參數(shù)設(shè)置

對(duì)仿真場(chǎng)景的參數(shù)設(shè)置是在與routing同級(jí)的目錄下rabadp_settings.txt文件中進(jìn)行的。

2.1.1 仿真場(chǎng)景的整體設(shè)置。仿真場(chǎng)景名為RabAdp，同時(shí)模擬了連接，每隔0.1秒更新一次。整個(gè)仿真的過(guò)程持續(xù)時(shí)間為43k秒，大約相當(dāng)于真實(shí)世界中的12個(gè)小時(shí)。在整個(gè)仿真過(guò)程中共設(shè)置了6個(gè)節(jié)點(diǎn)組。

2.1.2 節(jié)點(diǎn)組設(shè)置。首先對(duì)仿真場(chǎng)景中的節(jié)點(diǎn)進(jìn)行了公共的參數(shù)，它們使用的運(yùn)動(dòng)模型是基于地圖的最短路徑算法，使用Dijkstra算法計(jì)算節(jié)點(diǎn)從當(dāng)前位置到隨機(jī)選取的目的節(jié)點(diǎn)的最短路徑。采用了RAB-ADP路由算法，為每個(gè)節(jié)點(diǎn)設(shè)置的緩存區(qū)大小為10M，節(jié)點(diǎn)的移動(dòng)速度為0.5米/秒-1.5米/秒，并有0-120秒的等待時(shí)間。每個(gè)分組設(shè)置了50個(gè)節(jié)點(diǎn)。

由于在本次仿真試驗(yàn)中共設(shè)置了126個(gè)節(jié)點(diǎn)，分為6組：2組行人分別有40個(gè)節(jié)點(diǎn)；1組汽車(chē)，有40個(gè)節(jié)點(diǎn)；3組電車(chē)，每組分別有2個(gè)節(jié)點(diǎn)。每組節(jié)點(diǎn)分別有其特殊的屬性，所以還需要單獨(dú)為每組節(jié)點(diǎn)進(jìn)行參數(shù)的設(shè)置。

groupID是每個(gè)節(jié)點(diǎn)組的特殊標(biāo)記，在運(yùn)行仿真實(shí)驗(yàn)時(shí)可以在圖形化界面中很容易地區(qū)分各個(gè)節(jié)點(diǎn)組：兩個(gè)行人組的groupID分別為p和w，汽車(chē)組的為c，三個(gè)電車(chē)組均為t。電車(chē)組使用的是基于路線的移動(dòng)模型，具體的移動(dòng)路線是從外部文件tram3.wkt中導(dǎo)入的，并根據(jù)routeType屬性規(guī)定了路線的類型。由于電車(chē)與行人在緩存區(qū)大小、移動(dòng)速度和等待時(shí)間等屬性上是有差異的，所以進(jìn)行了重新的設(shè)置。

2.2 仿真結(jié)果分析

節(jié)點(diǎn)的緩存區(qū)資源是有限的，當(dāng)消息過(guò)多超出緩存區(qū)容納的范圍時(shí)需要根據(jù)一定的隊(duì)列策略刪除消息。而不同的緩存區(qū)大小影響著刪除的消息數(shù)量，從而影響了算法的性能。

緩存區(qū)大小分別取2M、5M、10M、20M、30M五種情況進(jìn)行比較。網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)目為126個(gè)。

當(dāng)緩沖區(qū)大小達(dá)到較高水平時(shí)，逐漸趨近于BinarySpray and Wait算法。分析其具體原因?yàn)椋海?）Epidemic算法采用的是洪泛策略，隨著緩存區(qū)大小的增加，緩存中能夠保存的消息數(shù)量增加，但是網(wǎng)絡(luò)中產(chǎn)生的消息副本也在大規(guī)模增加，緩存區(qū)會(huì)不斷地根據(jù)相應(yīng)的隊(duì)列策略刪除舊消息，為新消息提供更多的空間。這樣使得節(jié)點(diǎn)間隨機(jī)相遇的概率降低，導(dǎo)致傳遞率降低；（2）PROPHET算法是基于歷史和可傳遞性的概率路由算法，在轉(zhuǎn)發(fā)時(shí)會(huì)根據(jù)相遇歷史計(jì)算出傳遞預(yù)測(cè)概率值來(lái)決定是否轉(zhuǎn)發(fā)，從而在緩沖區(qū)的較小的情況下優(yōu)于Epidemic算法。然而，在網(wǎng)絡(luò)中產(chǎn)生的消息緩沖區(qū)大小和拷貝的大量增加，節(jié)點(diǎn)滿足減少可能的節(jié)點(diǎn)的概率，長(zhǎng)時(shí)間不能滿足，導(dǎo)致預(yù)測(cè)的概率大大衰減，從而降低轉(zhuǎn)移，轉(zhuǎn)移率；（3）Binary Spray and Wait算法和RAB-ADP算法對(duì)轉(zhuǎn)發(fā)過(guò)程中的消息副本數(shù)進(jìn)行了限制，從而節(jié)省了緩存空間用來(lái)保存更多的消息，更加有效地為更多的消息提供服務(wù)。因此這兩種算法隨著緩存區(qū)大小的增加傳遞率增長(zhǎng)較快；（4）隨著緩存區(qū)大小的增加四種路由算法的平均延遲時(shí)間變化情況。可以看出RAB-ADP算法的平均延遲時(shí)間處于高于Binary Spray and Wait算法，但是低于PROPHET算法和Epidemic算法。這是由于在進(jìn)行消息轉(zhuǎn)發(fā)時(shí)，RAB-ADP算法要根據(jù)平均傳遞預(yù)測(cè)概率值來(lái)決定是否進(jìn)行轉(zhuǎn)發(fā)，因而需要在緩存區(qū)中停留更長(zhǎng)的時(shí)間來(lái)等待更好的轉(zhuǎn)發(fā)機(jī)會(huì)，所以平均延遲時(shí)間較長(zhǎng)，這個(gè)指標(biāo)也是RAB-ADP算法在繼續(xù)研究過(guò)程中需要改進(jìn)的方向。

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

在兩個(gè)實(shí)驗(yàn)中可以看出，在不同的網(wǎng)絡(luò)節(jié)點(diǎn)中的緩沖和不同的兩種情況下，Rab-ADP算法中看到的傳遞率一直高于PROPHET、Epidemic和Binary Spray and Wait三種算法，路由開(kāi)銷(xiāo)率在四算法的最低水平，性能優(yōu)于其他三算法。而平均延遲性能不理想，總是很高，需要繼續(xù)提高在未來(lái)的研究過(guò)程。

參考文獻(xiàn)：

[1]Kevin Fall.A delay-tolerant network architecture for challenged Internets[R].Intel Research Technical Report，IRB-TR-03-003，2003.

[2]Dave Wick.Delay Tolerant Networks in a Nutshell[R].Institute of Computer Science and Applied Mathematics （IAM）University of Bern，2007.

[3]V.Cerf.Delay-Tolerant Network Architecture[R].IETF RFC 4838，2007.

作者單位：中共天水市委黨校，甘肅天水 741000