Ad Hoc網(wǎng)絡(luò)中確定性廣播算法的優(yōu)化研究與設(shè)計(jì).pdf

1、廣播是Ad Hoc網(wǎng)絡(luò)中的重要操作，其目的是將源節(jié)點(diǎn)發(fā)送的消息傳送給網(wǎng)絡(luò)中所有的通信節(jié)點(diǎn)。多種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)生影響。實(shí)現(xiàn)廣播的最常見方式是簡(jiǎn)單泛洪，但該種方法將導(dǎo)致嚴(yán)重的廣播信息冗余、信道競(jìng)爭(zhēng)和碰撞等廣播風(fēng)暴問題。為避免Ad Hoc網(wǎng)絡(luò)中產(chǎn)生廣播風(fēng)暴，需要減少網(wǎng)絡(luò)中廣播包的數(shù)量，在

2、廣播算法中體現(xiàn)為選擇盡可能少的節(jié)點(diǎn)轉(zhuǎn)發(fā)廣播包。現(xiàn)有廣播算法可分為確定性廣播算法和非確定性廣播算法。由于非確定性廣播算法的覆蓋性欠佳，理論上不能確保網(wǎng)絡(luò)中所有節(jié)點(diǎn)均能收到廣播包，所以本文選用確定性廣播算法進(jìn)行研究。
　　 本研究將圖論中的支配集理論運(yùn)用于Ad Hoc網(wǎng)絡(luò)后，廣播算法中試圖尋找盡可能少的轉(zhuǎn)發(fā)節(jié)點(diǎn)這一問題轉(zhuǎn)化為尋找網(wǎng)絡(luò)中的近似最小連通支配集的問題。因此，確定性廣播算法的實(shí)質(zhì)就是網(wǎng)絡(luò)中連通支配集(Connected Do

3、minating Set，CDS)的構(gòu)造算法，可分為基于自裁減策略、基于極大獨(dú)立集、基于鄰節(jié)點(diǎn)選擇等三類CDS構(gòu)造算法。由于基于鄰節(jié)點(diǎn)選擇的CDS構(gòu)造算法具有即時(shí)生成CDS的特點(diǎn)，其算法流程較前兩類更為簡(jiǎn)單，適應(yīng)于帶寬有限且網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)變化的Ad Hoc網(wǎng)絡(luò)，所以本文進(jìn)一步選取該類算法進(jìn)行研究。在基于鄰節(jié)點(diǎn)選擇的CDS構(gòu)造算法中，因?yàn)閰^(qū)域裁減算法(Dominant Pruning，DP)具有較好的性能，所以該類CDS構(gòu)造算法的后續(xù)研究中

4、很多都是針對(duì)DP算法進(jìn)行優(yōu)化。但這些優(yōu)化算法都沒有考慮本地支配節(jié)點(diǎn)和同級(jí)支配節(jié)點(diǎn)的關(guān)聯(lián)關(guān)系對(duì)下一跳支配節(jié)點(diǎn)選擇結(jié)果的影響，同時(shí)忽略了網(wǎng)絡(luò)前一時(shí)刻狀態(tài)對(duì)后續(xù)支配節(jié)點(diǎn)選擇結(jié)果的影響。因此，本文從以上兩個(gè)角度對(duì)DP算法進(jìn)行優(yōu)化：利用同級(jí)支配節(jié)點(diǎn)代替本地支配節(jié)點(diǎn)完成其后續(xù)覆蓋過(guò)程，以減少本地支配節(jié)點(diǎn)所選擇的下一跳支配節(jié)點(diǎn)的數(shù)量，從而在CDS構(gòu)造過(guò)程中選擇更少的支配節(jié)點(diǎn)；考慮網(wǎng)絡(luò)前一時(shí)刻狀態(tài)對(duì)支配節(jié)點(diǎn)選擇結(jié)果的影響，進(jìn)一步壓縮本地支配節(jié)點(diǎn)兩跳范圍

5、內(nèi)需要被支配節(jié)點(diǎn)覆蓋、但暫未被覆蓋的節(jié)點(diǎn)數(shù)量，從而在CDS構(gòu)造的過(guò)程中選擇更少的支配節(jié)點(diǎn)。在此基礎(chǔ)上，本文設(shè)計(jì)了改進(jìn)型區(qū)域裁減算法(Impoved DominantPruning，IDP)，擬減少CDS構(gòu)造過(guò)程中被選擇的支配節(jié)點(diǎn)數(shù)量，抑制冗余廣播包的產(chǎn)生。最后，證明了IDP算法的正確性和可靠性，并對(duì)IDP算法和DP算法進(jìn)行仿真。兩個(gè)算法在不同網(wǎng)絡(luò)節(jié)點(diǎn)密度和不同節(jié)點(diǎn)最大移動(dòng)速度的場(chǎng)景下，分別對(duì)廣播包的到達(dá)率、選擇的轉(zhuǎn)發(fā)節(jié)點(diǎn)數(shù)和產(chǎn)生的網(wǎng)絡(luò)開