基于圖論的WSN虛擬骨干網(wǎng)算法研究.pdf

1、由于無線傳感器網(wǎng)絡具有獨特的優(yōu)點，因此其在軍事和民用領域都具有廣泛的應用前景。目前，無線傳感器網(wǎng)絡正在受到越來越多的關注，因此許多與無線傳感器網(wǎng)絡相關的研究正在成為學術界的研究熱點，其中，作為網(wǎng)絡路由基礎的虛擬骨干網(wǎng)已經(jīng)成為熱門的研究課題之一。由于傳感器節(jié)點在電池能量、存儲空間和運算速度等方面受到嚴格的約束，因此在設計相關無線傳感器網(wǎng)絡的算法時應該綜合地考慮這些制約因素。
　　 本文基于圖論分別從能量高效、負載均衡和網(wǎng)絡容錯這三

2、個方面對無線傳感器網(wǎng)絡的虛擬骨干網(wǎng)算法進行了研究，主要工作包括：
　　 (1)針對集中式虛擬骨干網(wǎng)算法的構造成本過大和分布式虛擬骨干網(wǎng)算法的骨干網(wǎng)規(guī)模過大的問題，本文提出了一種基于連通支配集的虛擬骨干網(wǎng)構造算法。該算法運用圖論中的連通支配集理論以極低的成本構造了一個虛擬骨干網(wǎng)絡，并且運用修剪規(guī)則縮小了虛擬骨干網(wǎng)的規(guī)模。算法綜合考慮節(jié)點的能量和距離，使得虛擬骨干網(wǎng)的壽命更長。理論分析證明了在同構傳感器網(wǎng)絡環(huán)境下虛擬骨干網(wǎng)規(guī)模的最大

3、值和算法的消息、時間復雜度。仿真分析顯示了該算法在骨干網(wǎng)規(guī)模、消息總數(shù)和總能耗方面都要好于其它算法。
　　 (2)針對需要數(shù)據(jù)轉發(fā)與融合的骨干節(jié)點會比非骨干節(jié)點因能量消耗過快而提早失效的問題，本文提出了一種基于連通坡面劃分的多重虛擬骨干網(wǎng)輪換算法。該算法運用圖論中的連通坡面劃分理論構造了若干個沒有公共節(jié)點的虛擬骨干網(wǎng)，并且使它們按照輪換周期依次承擔數(shù)據(jù)轉發(fā)與融合的任務，達到了均衡節(jié)點負載的目的。理論分析證明了在同構傳感器網(wǎng)絡環(huán)境

4、下虛擬骨干網(wǎng)個數(shù)的最小值和算法的消息、時間復雜度。仿真分析顯示了該算法在骨干網(wǎng)平均規(guī)模、骨干網(wǎng)總數(shù)和網(wǎng)絡壽命方面都要好于其它算法。
　　 (3)針對在異構傳感器網(wǎng)絡環(huán)境下虛擬骨干網(wǎng)修復算法研究的不足，本文提出了一種基于連通支配樹的異構虛擬骨干網(wǎng)修復算法。該算法運用圖論中的連通支配樹理論在異構傳感器網(wǎng)絡環(huán)境下構造了一個異構的虛擬骨干網(wǎng)。當失效的骨干節(jié)點造成虛擬骨干網(wǎng)不能連通和覆蓋其它節(jié)點時，算法會對虛擬骨干網(wǎng)進行局部修復以恢復它的