【摘要】：容遲/容斷網(wǎng)絡(luò)(DTN)是一類支持在大時延、鏈路間歇中斷等受限條件下進行通信的新型網(wǎng)絡(luò)體系.針對DTN中由于節(jié)點移動性、緩存空間受限等而不能保證消息可靠傳輸?shù)膯栴},提出一種網(wǎng)絡(luò)狀態(tài)感知的概率路由算法NSAPR(network situation-aware probabilistic routing algorithm).該算法依據(jù)節(jié)點之間的歷史接觸成功率獲取網(wǎng)絡(luò)狀態(tài)信息,在轉(zhuǎn)發(fā)決策時引入接觸成功率的影響,并根據(jù)網(wǎng)絡(luò)狀態(tài)采取自適應(yīng)的參數(shù)選取策略進行消息的轉(zhuǎn)發(fā)和副本的刪除,同時進行相應(yīng)的隊列管理和擁塞控制,從而優(yōu)化中繼節(jié)點的選擇和減少對網(wǎng)絡(luò)資源的浪費.仿真實驗表明,與現(xiàn)有其他幾種算法相比,該算法能夠在不同網(wǎng)絡(luò)狀態(tài)下提高消息交付率并降低網(wǎng)絡(luò)開銷,具有較好的網(wǎng)絡(luò)適應(yīng)性.
【圖文】：

狀態(tài)．PROPHET僅根據(jù)歷史接觸頻率進行轉(zhuǎn)發(fā)決策，而沒有考慮節(jié)點的自身性能，難以反映投遞概率值的準確性．如圖1所示，節(jié)點A有消息m需要發(fā)送給節(jié)點D，B和C為中間轉(zhuǎn)發(fā)節(jié)點，且與A的接觸頻率基本相同．節(jié)點C的緩存空間比較有限，A與C之間數(shù)據(jù)傳輸率較低，消息傳輸經(jīng)常失敗，而節(jié)點B的性能較好，與A之間消息傳輸成功的可能性較大．PROPHET以歷史接觸頻率為依據(jù)，則A對B與C的投遞概率值幾乎相同．然而B為較理想的轉(zhuǎn)發(fā)節(jié)點，將更多的消息轉(zhuǎn)發(fā)給節(jié)點B會提高消息到達目的節(jié)點D的可能性．圖1PROPHET算法示例Fig．1ExampleofPROPHETalgorithm基于此，本文提出接觸成功率(probabilityofsuccessfulcontact)的概念，記為Ps=N/M(N≤M)，其中M為兩節(jié)點的歷史接觸次數(shù)，N為兩節(jié)點的接觸成功次數(shù)，接觸成功即消息在節(jié)點之間傳輸成功．Ps的大小反映了兩節(jié)點的歷史傳輸消息狀況，假設(shè)節(jié)點性能不會發(fā)生突變，則Ps在很大程度上決定了未來的接觸成敗情況．本文基于PROPHET算法提出一種網(wǎng)絡(luò)狀態(tài)感知的概率路由算法(networksituation-awareprobabilisticroutingalgorithm，NSAPR)，在計算投遞概率時同時考慮歷史接觸頻率和接觸成功率，根據(jù)網(wǎng)絡(luò)狀態(tài)自適應(yīng)調(diào)整路由參數(shù)，使消息在傳輸過程中能夠選擇更有可能接觸成功的理想節(jié)點，從而提高消息的交付率．2．2算法合理性分析本文采用馬爾可夫鏈對算法的合理性進行分析．假設(shè)節(jié)點A與節(jié)點B的歷史接觸次數(shù)為M，接觸成功次數(shù)為N，建立N的有限狀態(tài)空間的馬爾科夫鏈X(n)(n=0，1，2，…)，狀態(tài)空間為{0，1，2，…，i，…，M}．N的初始狀態(tài)為0，接觸成功時N由狀態(tài)i變?yōu)闋顟B(tài)i+1，接觸失敗時N保持狀態(tài)i不變．設(shè)由狀態(tài)i轉(zhuǎn)移到狀態(tài)i+1的概率為Pi，i+1，由狀態(tài)i轉(zhuǎn)移到狀態(tài)i的概率為Pi，i．以歷史接觸

in(1－NM)n(11－NM－1)i，0≤i≤n0，i＞{n(n≤M)(3)2)當N=0即每次接觸均失敗時:狀態(tài)轉(zhuǎn)移概率為Pi，i+1=0Pi，i{=1，Q(M+1)×(M+1)為M+1階單位陣，P(n)i=(1，0，0，…，0)．3)當N=M即每次接觸均成功時:狀態(tài)轉(zhuǎn)移概率為Pi，i+1=1Pi，i{=0，P(n)i=(0，0，…，1，…，0)(僅當i=n時為1，其余為0)．由此可以求出n步轉(zhuǎn)移后狀態(tài)為i的概率P{X(n)=i}．在式(3)中令i=n，則P{X(n)=n}=(N/M)n，n分別取5和10，，N/M在0～1之間取值，P的變化如圖2所示．由圖2可圖2狀態(tài)轉(zhuǎn)移概率Fig．2Statetransitionprobability以看出，隨著歷史接觸成功率的增加，n步轉(zhuǎn)移后狀態(tài)為n即每次接觸均成功的概率也逐漸增加，且轉(zhuǎn)移步數(shù)越少概率越大，因此基于歷史接觸成功率進行轉(zhuǎn)發(fā)決策是比較合理的．3算法設(shè)計3．1消息轉(zhuǎn)發(fā)在NSAPR算法中，概率更新公式(4)和老化公式(5)引入接觸成功率，傳遞公式(6)與PROPHET保持一致．P(a，b)=P(a，b)·old+(1－P(a，b)old－δ)×Pinit×CNM(4)P(a，b)=P(a，b)old×γk(1－NM)(5)P(a，b)=P(a，c)old+(1－P(a，c)old)×P(a，b)×P(b，c)×β(6)其中，C為接觸成功率對投遞概率的影響因子(C＞1且Pinit·C＜1)，δ為P(a，b)的上限因子．該算法基于歷史信息，接觸成功率越高則投遞概率越大，節(jié)點之間越容易進行消息轉(zhuǎn)發(fā);同時，接觸成功率高則對該節(jié)點的投遞概率老化變慢，可146小型微型計算機系統(tǒng)2013年
【作者單位】： 空軍工程大學信息與導(dǎo)航學院;
【基金】：全軍軍事學研究生課題(2011XXXXX-523)資助
【分類號】：TP393.02

【相似文獻】

相關(guān)期刊論文 前10條

1 鄧宏文;網(wǎng)絡(luò)路由技術(shù)基礎(chǔ)[J];機械管理開發(fā);2005年05期

2 王敏;高太平;劉桂枝;劉宏英;;交叉立方體網(wǎng)絡(luò)上的一種雙向搜索路由算法[J];計算機工程與應(yīng)用;2007年35期

3 段新明;楊愚魯;;Mesh網(wǎng)絡(luò)耐故障蟲孔路由[J];計算機科學;2007年11期

4 焦鋒;;基因算法在路由算法中的應(yīng)用[J];山西科技;2008年03期

5 李昌兵;胡華;吳建;曹長修;;基于協(xié)同進化蟻群算法的多播QoS路由算法[J];計算機工程與應(yīng)用;2008年24期

6 李向群;劉立祥;胡曉惠;曾開祥;;延遲/中斷可容忍網(wǎng)絡(luò)研究進展[J];計算機研究與發(fā)展;2009年08期

7 章?lián)P;洪利;;一種基于遺傳算法的QoS多播路由算法[J];計算機應(yīng)用與軟件;2009年09期

8 張先勇;李勇;;一種基于改進蟻群優(yōu)化的QoS路由算法[J];計算機與網(wǎng)絡(luò);2009年10期

9 李照奎;石祥濱;王巖;;基于自組織聚類及自決定聚首的路由算法[J];計算機工程;2010年07期

10 尹騰飛;陳戈;呂智涵;田蕾;;基于DHT對等網(wǎng)絡(luò)的虛擬場景數(shù)據(jù)發(fā)布[J];微計算機信息;2011年06期

相關(guān)會議論文 前10條

1 李婷;;多約束條件下的QoS路由算法研究[A];第十二屆中國青年信息與管理學者大會論文集[C];2010年

2 楊丞;張剛林;劉光燦;王路露;;一種針對P2P網(wǎng)絡(luò)優(yōu)化的Kademlia路由算法[A];2009年全國開放式分布與并行計算機學術(shù)會議論文集(下冊)[C];2009年

3 葉嘉;彭偉;;MintRouteEE:一種無線傳感器網(wǎng)絡(luò)能量有效的路由協(xié)議[A];2006年全國開放式分布與并行計算學術(shù)會議論文集（一）[C];2006年

4 李e

本文編號：2541027