連通控制集的構造與維護算法研究.pdf

1、無線傳感器網絡是由一組帶有無線收發(fā)設備的傳感器節(jié)點組成的多跳的臨時性無中心網絡，可以在任何時刻、任何地點、快速的構建起一個移動通信網絡，并且不需要現(xiàn)有網絡基礎設施的支持。一個典型的傳感器節(jié)點一般由傳感系統(tǒng)、處理系統(tǒng)、無線通信系統(tǒng)和能源設備構成。傳感系統(tǒng)用來獲取周圍環(huán)境中的數(shù)據(jù)；處理系統(tǒng)用于本地數(shù)據(jù)處理和存儲；無線通信系統(tǒng)用來進行數(shù)據(jù)傳輸；能源設備則用于提供系統(tǒng)完成任務所需要的能量。
　　 在無線傳感器網絡中，節(jié)點不僅要負責通信任

2、務，同時還要擔當路由功能。而基于洪泛的路由機制會引起廣播風暴問題，這將消耗大量的網絡資源。由于網絡拓撲結構動態(tài)變化性、多跳通信特性和資源的有限性，合理的路由設計成了一個挑戰(zhàn)性的問題。對此，許多學者提出了構造虛擬骨干網，將網絡分級來實現(xiàn)網絡的穩(wěn)定性和高效性。通過在無線傳感器網絡中構造虛擬骨干網即可將網絡中節(jié)點進行分級，而這一過程正是圖論中連通控制集理論的一個應用。可以將路由簡化到由最小連通控制集構造成的虛擬骨干網中去。信息由源節(jié)點出發(fā)，沿

3、著連通控制集中的節(jié)點傳遞到離目的節(jié)點最近的控制節(jié)點，最終到達目的節(jié)點。
　　 本文以連通控制集作為研究問題的理論基礎，對傳統(tǒng)的構造連通控制集的方法進行了深入研究，并在現(xiàn)有算法的基礎上提出了一個改進最小連通控制集算法，該算法首先構造一個極大獨立集，在此基礎上利用兩跳局部網絡信息選擇連通點，形成連通控制集。對于構造連通控制集的算法，有以下四個方面的因素度量算法的性能：近似比、局部性、時間復雜度和消息復雜度、以及穩(wěn)定性。理論和仿真實驗

4、都表明，本文所提出的改進的算法與現(xiàn)有的算法相比，能得到一個更小的虛擬骨干網，即有更小的近似比6.906。
　　 近年來，為了適應無線網絡的復雜環(huán)境，具有更好容錯性，更強健壯性的k-連通m-控制集問題及其構造算法也相繼出現(xiàn)。但是，大多數(shù)構造算法在面臨網絡中節(jié)點的移動時都要重新構造kmCDS，這無疑增加了開銷?；诖吮疚倪€給出了一個移動情況下k-連通m-控制集的維護算法。在由現(xiàn)有算法構造出kmCDS骨干網的無線網絡中，當節(jié)點移動時，