機(jī)會網(wǎng)絡(luò)中一種低緩存占用的Epidemic路由算法.pdf

《機(jī)會網(wǎng)絡(luò)中一種低緩存占用的Epidemic路由算法.pdf》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

1、開發(fā)與研究DEVELOPMENTANDRESEARCH電信工程技術(shù)與標(biāo)準(zhǔn)化機(jī)會網(wǎng)絡(luò)中一種低緩存占用的Epidemic路由算法左成章，劉智虎，孫希勝，索建偉（重慶郵電大學(xué)移動通信技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室，重慶400065）摘　要由于機(jī)會網(wǎng)絡(luò)中節(jié)點(diǎn)的緩存空間有限，容易導(dǎo)致數(shù)據(jù)分組丟失和時延增加。針對部分?jǐn)?shù)據(jù)分組已經(jīng)到達(dá)目的節(jié)點(diǎn)，但是該類分組仍在網(wǎng)絡(luò)中其它節(jié)點(diǎn)存儲、傳輸問題，提出一種低緩存占用的Epidemic路由算法（RBER）。該算法通過SV運(yùn)算進(jìn)行節(jié)點(diǎn)緩存清理，從而避免這類冗余數(shù)據(jù)分組對緩存的占用。理論分析和仿真結(jié)果表明，該機(jī)制能夠降低網(wǎng)絡(luò)開銷、數(shù)據(jù)分組的發(fā)

2、送和緩存占用。關(guān)鍵詞機(jī)會網(wǎng)絡(luò)；路由算法；緩存；清理中圖分類號TP393文獻(xiàn)標(biāo)識碼A文章編號1008-5599（2014）02-0085-04[1]機(jī)會網(wǎng)絡(luò)(OpportunisticNetworks)是一種不需（RBER，ReduceBufferoverheadbasedEpidemic要源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間存在完整路徑，利用節(jié)點(diǎn)移動Routing）算法，通過優(yōu)先刪除目的地址為對方節(jié)點(diǎn)的帶來的相遇機(jī)會實(shí)現(xiàn)網(wǎng)絡(luò)通信的自組織網(wǎng)絡(luò)。網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù)分組，減少了網(wǎng)絡(luò)中數(shù)據(jù)分組副本的擴(kuò)散，降低網(wǎng)結(jié)構(gòu)頻繁改變，不能保證連通性，信息源節(jié)點(diǎn)與目的節(jié)絡(luò)資源開銷，提高緩存利用率

3、。點(diǎn)之間不一定存在傳輸路徑。在機(jī)會網(wǎng)絡(luò)路由算法中，應(yīng)用和研究較為廣泛的是基于復(fù)制的路由算法。在機(jī)會1相關(guān)工作網(wǎng)絡(luò)中為了能夠有效的進(jìn)行數(shù)據(jù)的傳輸，“存儲-攜帶-[3]轉(zhuǎn)發(fā)”的路由模式成為優(yōu)先考慮的一種機(jī)制。在這種機(jī)Harras等提出了ControlledFlooding路由算法。制中，節(jié)點(diǎn)在收到數(shù)據(jù)分組時，通常將數(shù)據(jù)分組存儲到該算法假定每個節(jié)點(diǎn)只知道自身以及自己攜帶的消息信本節(jié)點(diǎn)，攜帶著數(shù)據(jù)分組一起移動，當(dāng)遇到合適的節(jié)點(diǎn)息，并且能夠完全自主作出轉(zhuǎn)發(fā)決策。該算法通過意愿時再將數(shù)據(jù)分組轉(zhuǎn)發(fā)出去。數(shù)據(jù)分組在節(jié)點(diǎn)相遇時被多概率、生存時間(TTS，Time-To-S

4、end)和死亡時間次的轉(zhuǎn)發(fā)，網(wǎng)絡(luò)中存在多個數(shù)據(jù)分組的副本。(TTL，Time-To-Live)3個參數(shù)來控制消息泛洪。此[2]其中，最為典型的算法就是Epidemic路由算法。外，通過廣播免疫信息來及時刪除已達(dá)目的節(jié)點(diǎn)的數(shù)據(jù)該算法因其較高的投遞率和較低的時延特性而備受關(guān)注。分組。該算法在保證可靠投遞的同時減少了網(wǎng)絡(luò)開銷。但是，該算法類似于泛洪機(jī)制，對網(wǎng)絡(luò)資源的要求比較高，Epidemic路由算法是一種基于洪泛策略和復(fù)制的在苛刻的機(jī)會網(wǎng)絡(luò)環(huán)境中，算法性能的提升受到限制。路由協(xié)議。每一個攜帶數(shù)據(jù)的節(jié)點(diǎn)都將數(shù)據(jù)的副本傳遞為此，本文提出一種低緩存占用的Epide

5、mic路由給它所遇到的未帶有該消息節(jié)點(diǎn)，通過“存儲-攜帶-收稿日期：2014-01-01·2014年第2期·85開發(fā)與研究DEVELOPMENTANDRESEARCHTELECOMENGINEERINGTECHNICSANDSTANDARDIZATION轉(zhuǎn)發(fā)”逐跳傳遞將消息送達(dá)目的節(jié)點(diǎn)。每個節(jié)點(diǎn)維護(hù)一行鄰居發(fā)現(xiàn)，某一時刻，節(jié)點(diǎn)X和節(jié)點(diǎn)Y相遇，其數(shù)個摘要矢量(SV，SummaryVector)，當(dāng)兩個節(jié)點(diǎn)能夠據(jù)交互過程如圖1所示。連接時通過交換消息向量來彼此交換較少的消息。經(jīng)過一段時間，網(wǎng)絡(luò)中的每個節(jié)點(diǎn)將接收到所有的消息。優(yōu)點(diǎn)是不需要額外的拓?fù)淇刂菩畔?，?/p>

6、時可以取得高的消息投遞率和低的端到端時延，無需對鏈路狀態(tài)進(jìn)行預(yù)測與估計，實(shí)施起來較為簡單。缺點(diǎn)是網(wǎng)絡(luò)中存在大量的圖1Epidemic算法數(shù)據(jù)交互過程冗余副本將導(dǎo)致節(jié)點(diǎn)能耗增加和緩存溢出，進(jìn)而導(dǎo)致網(wǎng)絡(luò)的資源利用率低和網(wǎng)絡(luò)性能下降。（1）節(jié)點(diǎn)X向節(jié)點(diǎn)Y發(fā)送摘要矢量SVX，告知節(jié)MRRMR(MessageRedundancyRemovalof點(diǎn)Y節(jié)點(diǎn)X當(dāng)前緩存中存有的數(shù)據(jù)分組。[4]Multi-copyRouting)算法在ER算法的基礎(chǔ)上為每（2）節(jié)點(diǎn)Y收到SVX后，通過與自己保存的SVY一個網(wǎng)絡(luò)節(jié)點(diǎn)增加一個相遇計數(shù)器。該計數(shù)器記錄節(jié)點(diǎn)作如下位運(yùn)算：遇到的帶

7、有相同消息拷貝的不同節(jié)點(diǎn)的數(shù)目。如果計數(shù)RequestX=SVX&?SVY(1)器的值達(dá)到了所設(shè)置的門限值，則節(jié)點(diǎn)將該消息拷貝從通過上述運(yùn)算，節(jié)點(diǎn)Y獲得節(jié)點(diǎn)X緩存中有而本緩存中移除，并且之后不再接收該消息拷貝。通過設(shè)置身沒有的數(shù)據(jù)分組信息，并向節(jié)點(diǎn)X發(fā)送RequestX控合理的門限值，可以在保證消息投遞成功率和不增加控制分組來請求這些數(shù)據(jù)分組。制分組開銷的同時，將冗余拷貝高效的控制在一個相對（3）節(jié)點(diǎn)X收到RequestX后，向節(jié)點(diǎn)Y發(fā)送對應(yīng)低的水平并且可以顯著減少節(jié)點(diǎn)緩存占用。但是，由于的請求分組。節(jié)點(diǎn)移動的隨機(jī)性，合理門限值的選定比較困難。并且，（4

8、）節(jié)點(diǎn)Y收到數(shù)據(jù)分組后，更新自己的SVY。此外，消息拷貝的過早移除，還會導(dǎo)致傳輸