Ad Hoc網絡中確定性廣播算法的優(yōu)化研究與設計.pdf

1、廣播是Ad Hoc網絡中的重要操作，其目的是將源節(jié)點發(fā)送的消息傳送給網絡中所有的通信節(jié)點。多種Ad Hoc網絡路由協(xié)議(如AODV、OLSR、ODMDP等)使用廣播進行路由選擇并在網絡節(jié)點之間更新路由信息，一個高效的廣播算法將直接對Ad Hoc網絡通訊協(xié)議棧的性能產生影響。實現(xiàn)廣播的最常見方式是簡單泛洪，但該種方法將導致嚴重的廣播信息冗余、信道競爭和碰撞等廣播風暴問題。為避免Ad Hoc網絡中產生廣播風暴，需要減少網絡中廣播包的數量，在

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

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

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

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