傳感器網(wǎng)絡(luò)拓撲控制連通支配集算法研究.pdf

1、網(wǎng)絡(luò)拓撲控制是無線傳感器網(wǎng)絡(luò)的關(guān)鍵技術(shù)之一，用圖論中的最小連通支配集思想在網(wǎng)絡(luò)中組織一個虛擬的層次型骨干網(wǎng)絡(luò)是實現(xiàn)拓撲控制一種常用的方式。而圖論中的最小連通支配集問題是NP完全問題。 在簡單無向圖上，求解最小連通支配集問題等效于求解最大葉節(jié)點生成樹問題。本論文以鄰近圖結(jié)構(gòu)為基礎(chǔ)，提出一種基于環(huán)路上節(jié)點最小度的近似最大葉節(jié)點生成樹MDRST(Minimum-DegreeRelatedSpanningTree)構(gòu)建算法。該算法以節(jié)點

2、度為鄰居判定依據(jù)，通過刪除原圖中每條環(huán)路上最小度節(jié)點所在的一條邊來構(gòu)建多葉節(jié)點生成樹。MDRST是集中式構(gòu)建算法，其時間復(fù)雜性為O(N2)。 為實現(xiàn)分布式構(gòu)建算法，論文在MDRST的基礎(chǔ)上提出一種基于三角形和四邊形環(huán)路上節(jié)點最小度的MDRSG(Minimum-DegreeRelatedSpanningGraph)結(jié)構(gòu)。MDRSG同樣以節(jié)點度為鄰居判定依據(jù)，但不消除原圖中所有的環(huán)路，而只刪除三角形和四邊形環(huán)路上度最小節(jié)點所在的一條

3、邊。MDRSG需要節(jié)點一跳鄰居的鄰接表和二跳鄰居節(jié)點度的信息，可以用具有多項式時間復(fù)雜度的分布式算法構(gòu)建。 論文將MDRSG應(yīng)用于傳感器網(wǎng)絡(luò)的拓撲控制。為了克服MDRSG非平面性和沒有考慮節(jié)點間邊的權(quán)值的弱點，將MDRSG和相關(guān)鄰居圖RNG結(jié)合使用，實現(xiàn)了一種具有骨干網(wǎng)絡(luò)的拓撲控制方法。方法首先用MDRSG生成連通支配集，再用RNG將支配集中的節(jié)點組成平面型骨干網(wǎng)絡(luò)，而被支配節(jié)點選擇離自己最近的支配點連接到骨干網(wǎng)絡(luò)。這種拓撲結(jié)構(gòu)