延遲容忍網(wǎng)絡(luò)中路由與緩存管理算法.pdf

1、延遲容忍網(wǎng)絡(luò)(delay tolerant networks，DTN)是一種新型的網(wǎng)絡(luò)體系結(jié)構(gòu)。在這種類型的網(wǎng)絡(luò)中，節(jié)點(diǎn)具有存儲(chǔ)空間小、計(jì)算能力低的特點(diǎn)。由于節(jié)點(diǎn)頻繁的移動(dòng)、稀疏的分布或者節(jié)省能量等原因，經(jīng)常造成鏈路中斷、網(wǎng)絡(luò)分割的現(xiàn)象。因此，源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間長期不存在端到端的路徑，從而導(dǎo)致消息在節(jié)點(diǎn)之間傳輸?shù)难訒r(shí)非常大。消息傳遞的方式發(fā)生了重大的改變，傳統(tǒng)的路由方式已經(jīng)不能適應(yīng)這樣的網(wǎng)絡(luò)。延遲容忍網(wǎng)絡(luò)中如何將消息成功地發(fā)送到目的地

2、是一個(gè)挑戰(zhàn)性的問題。因此，路由是延遲容忍網(wǎng)絡(luò)中最主要的問題。本文針對(duì)各種不同環(huán)境的延遲容忍網(wǎng)絡(luò)的路由技術(shù)以及對(duì)路由性能影響很大的緩存管理技術(shù)進(jìn)行了深入的研究，本文的主要研究工作包括以下幾個(gè)方面的內(nèi)容。
　　 (1)掌握節(jié)點(diǎn)的移動(dòng)特征，有利于設(shè)計(jì)高效的路由算法。在網(wǎng)絡(luò)狀態(tài)未知的情況下，提出了一種基于節(jié)點(diǎn)運(yùn)動(dòng)移動(dòng)范圍感知的路由算法MSAR。不需要地理位置定位等硬件的支持，根據(jù)節(jié)點(diǎn)的歷史相遇記錄來比較消息攜帶節(jié)點(diǎn)和相遇節(jié)點(diǎn)的移動(dòng)范圍的

3、相似性，以及消息攜帶節(jié)點(diǎn)和相遇節(jié)點(diǎn)兩者與目的節(jié)點(diǎn)的移動(dòng)相似性，并以此作為消息復(fù)制轉(zhuǎn)發(fā)的依據(jù)。實(shí)驗(yàn)結(jié)果表明，MSAR路由算法能夠有效的提高節(jié)點(diǎn)的交付比率并降低網(wǎng)絡(luò)的開銷。
　　 (2)通過實(shí)際的行蹤數(shù)據(jù)分析發(fā)現(xiàn)，采用中心性作為路由度量尺度具有冪律分布的特點(diǎn)。如果采用中心性較大的節(jié)點(diǎn)作為中繼節(jié)點(diǎn)，會(huì)使這些節(jié)點(diǎn)成為熱區(qū)節(jié)點(diǎn)，造成網(wǎng)絡(luò)的擁塞，導(dǎo)致消息大量的丟棄和重傳而浪費(fèi)網(wǎng)絡(luò)資源。在中心性作為路由度量的基礎(chǔ)上提出了一種負(fù)載感知的路由算法

4、，該算法使用介數(shù)中心性和相似性以及節(jié)點(diǎn)的負(fù)載狀況作為中繼節(jié)點(diǎn)選擇的依據(jù)，避免了消息傳播能力強(qiáng)的節(jié)點(diǎn)產(chǎn)生嚴(yán)重的擁塞，均衡網(wǎng)絡(luò)流量。仿真結(jié)果表明，該算法在容忍消息延時(shí)的情況下能夠提高網(wǎng)絡(luò)的交付比率，減小網(wǎng)絡(luò)的開銷。
　　 (3)針對(duì)基于固定消息副本數(shù)量的噴射與等待這類算法在節(jié)點(diǎn)密度較大的情況下會(huì)過早地將消息副本分發(fā)完畢，使消息局限于一個(gè)局部區(qū)域，會(huì)造成較大的延時(shí)并降低交付比率的問題，提出了一種基于節(jié)點(diǎn)密度自適應(yīng)的噴射與轉(zhuǎn)發(fā)路由算法D

5、ASF。DASF通過估計(jì)當(dāng)前節(jié)點(diǎn)所在位置的節(jié)點(diǎn)密度，控制每次用于分配的消息副本數(shù)量，然后根據(jù)節(jié)點(diǎn)活躍程度按比例分配消息副本數(shù)量。仿真結(jié)果表明，該算法能夠在提高交付比率的基礎(chǔ)上，明顯地減小消息傳遞的平均延時(shí)。
　　 (4)延遲容忍網(wǎng)絡(luò)中節(jié)點(diǎn)采用“存儲(chǔ)-攜帶-轉(zhuǎn)發(fā)”的方式傳遞消息。在緩存空間有限時(shí)，不同的緩存管理策略對(duì)路由算法的性能有很大的影響。從整個(gè)網(wǎng)絡(luò)的角度來看，一個(gè)消息過分地復(fù)制轉(zhuǎn)發(fā)會(huì)耗盡節(jié)點(diǎn)的緩存，減少了其他消息對(duì)緩存使用的

6、概率，從而導(dǎo)致了交付比率的下降。受微觀經(jīng)濟(jì)學(xué)邊際效用遞減法則的啟示，提出了一種分布式的基于消息傳播狀態(tài)的緩存管理方法。當(dāng)緩存不夠時(shí)，節(jié)點(diǎn)將消息復(fù)制數(shù)量多和傳遞速率快的消息丟棄，而在轉(zhuǎn)發(fā)時(shí)則優(yōu)先發(fā)送消息復(fù)制數(shù)量少和傳遞速率慢的消息，保證了副本數(shù)量較少的消息獲得更多的傳輸機(jī)會(huì)。仿真實(shí)驗(yàn)結(jié)果表明，該方法能夠提高消息的交付比率并且具有相對(duì)較小的開銷比率。
　　 本文對(duì)延遲容忍網(wǎng)絡(luò)中的路由和相關(guān)技術(shù)進(jìn)行了深入的研究，這些研究工作能夠較好地