連通控制集的構(gòu)造與維護算法研究.pdf

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

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

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

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