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

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

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

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

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