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

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

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

2、送和緩存占用。關(guān)鍵詞機(jī)會(huì)網(wǎng)絡(luò)；路由算法；緩存；清理中圖分類號(hào)TP393文獻(xiàn)標(biāo)識(shí)碼A文章編號(hào)1008-5599（2014）02-0085-04[1]機(jī)會(huì)網(wǎng)絡(luò)(OpportunisticNetworks)是一種不需（RBER，ReduceBufferoverheadbasedEpidemic要源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間存在完整路徑，利用節(jié)點(diǎn)移動(dòng)Routing）算法，通過優(yōu)先刪除目的地址為對方節(jié)點(diǎn)的帶來的相遇機(jī)會(huì)實(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ī)會(huì)網(wǎng)絡(luò)路由算法中，應(yīng)用和研究較為廣泛的是基于復(fù)制的路由算法。在機(jī)會(huì)1相關(guān)工作網(wǎng)絡(luò)中為了能夠有效的進(jìn)行數(shù)據(jù)的傳輸，“存儲(chǔ)-攜帶-[3]轉(zhuǎn)發(fā)”的路由模式成為優(yōu)先考慮的一種機(jī)制。在這種機(jī)Harras等提出了ControlledFlooding路由算法。制中，節(jié)點(diǎn)在收到數(shù)據(jù)分組時(shí)，通常將數(shù)據(jù)分組存儲(chǔ)到該算法假定每個(gè)節(jié)點(diǎn)只知道自身以及自己攜帶的消息信本節(jié)點(diǎn)，攜帶著數(shù)據(jù)分組一起移動(dòng)，當(dāng)遇到合適的節(jié)點(diǎn)息，并且能夠完全自主作出轉(zhuǎn)發(fā)決策。該算法通過意愿時(shí)再將數(shù)據(jù)分組轉(zhuǎn)發(fā)出去。數(shù)據(jù)分組在節(jié)點(diǎn)相遇時(shí)被多概率、生存時(shí)間(TTS，Time-To-S

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

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

6、時(shí)可以取得高的消息投遞率和低的端到端時(shí)延，無需對鏈路狀態(tài)進(jìn)行預(yù)測與估計(jì)，實(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一個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)增加一個(gè)相遇計(jì)數(shù)器。該計(jì)數(shù)器記錄節(jié)點(diǎn)作如下位運(yùn)算：遇到的帶

7、有相同消息拷貝的不同節(jié)點(diǎn)的數(shù)目。如果計(jì)數(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ù)分組。制分組開銷的同時(shí)，將冗余拷貝高效的控制在一個(gè)相對（3）節(jié)點(diǎn)X收到RequestX后，向節(jié)點(diǎn)Y發(fā)送對應(yīng)低的水平并且可以顯著減少節(jié)點(diǎn)緩存占用。但是，由于的請求分組。節(jié)點(diǎn)移動(dòng)的隨機(jī)性，合理門限值的選定比較困難。并且，（4

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