自組織網(wǎng)絡(luò)廣播算法研究與應(yīng)用.pdf

1、在Ad Hoc網(wǎng)絡(luò)中，廣播被廣泛的使用于地址解析、路由發(fā)現(xiàn)和許多其他的網(wǎng)絡(luò)服務(wù)中。多種Ad Hoc網(wǎng)絡(luò)路由協(xié)議(如AODV、OLSR、ODMDP等)使用廣播進(jìn)行路由選擇并在網(wǎng)絡(luò)節(jié)點(diǎn)之間更新路由信息，因此一個(gè)高效的廣播算法將直接對(duì)Ad Hoc網(wǎng)絡(luò)通訊協(xié)議棧的性能產(chǎn)生影響。Ad Hoc網(wǎng)絡(luò)中的廣播采用一種簡(jiǎn)單的泛洪算法，保證消息被盡可能多的移動(dòng)節(jié)點(diǎn)收到。但是，簡(jiǎn)單的泛洪算法可能會(huì)造成過(guò)多的重播，引發(fā)廣播風(fēng)暴，導(dǎo)致整個(gè)網(wǎng)絡(luò)吞吐量的下降，并加劇

2、網(wǎng)絡(luò)中有限資源的消耗。
　　 現(xiàn)有的廣播算法可以可以?xún)纱箢?lèi)：非確定性算法和確定性算法。非確定性算法，雖然可以很好的限制廣播冗余，但覆蓋率較低。由于Ad Hoc本身具有不可靠和移動(dòng)性的特點(diǎn)，因此本文從網(wǎng)絡(luò)節(jié)點(diǎn)覆蓋率著手，決定選用確定性算法進(jìn)行研究。在綜合的考慮了各種確定性算法的優(yōu)缺點(diǎn)后，本文選用確定性算法中的基于自裁剪的CDS構(gòu)造算法作為研究的基礎(chǔ)。本文對(duì)已有的各種基于自裁剪的CDS構(gòu)造算法即PCDS(Self-Pruning b

3、ased on CDS)算法進(jìn)行了簡(jiǎn)要的分析后發(fā)現(xiàn)目前這些算法中普遍存在計(jì)算復(fù)雜度較高、通信開(kāi)銷(xiāo)大和網(wǎng)絡(luò)中CDS閉合環(huán)路上的冗余節(jié)點(diǎn)無(wú)法有效去除的問(wèn)題。
　　 通過(guò)加入節(jié)點(diǎn)度數(shù)，節(jié)點(diǎn)編號(hào)等參數(shù)對(duì)已有的PCDS算法進(jìn)行改進(jìn)，提出一種改進(jìn)型基于自裁剪的CDS構(gòu)造算法即IPCDS(Improved Self-Pruning based onCDS)算法。IPCDS算法可以解決現(xiàn)有算法中存在的計(jì)算復(fù)雜度高、通信開(kāi)銷(xiāo)大和閉合環(huán)上冗余節(jié)點(diǎn)多

4、的問(wèn)題，使之可以適用于節(jié)點(diǎn)密度比較大網(wǎng)絡(luò)環(huán)境中。IPCDS算法的主要思路是通過(guò)對(duì)已裁剪過(guò)的粗略的CDS中節(jié)點(diǎn)的度和編號(hào)等參數(shù)的一系列對(duì)比去除已有的粗略的CDS上的冗余節(jié)點(diǎn)來(lái)構(gòu)造精簡(jiǎn)的CDS。
　　 本文詳細(xì)闡述了IPCDS算法的工作原理、步驟、規(guī)則并對(duì)IPCDS算法的可靠性、正確性以及計(jì)算復(fù)雜度進(jìn)行了證明。通過(guò)一系列的證明，我們可以得到結(jié)論，IPCDS算法具有在Ad Hoc網(wǎng)絡(luò)中使用的可行性。
　　 最后，為了驗(yàn)證IPC