傳感器網(wǎng)絡(luò)拓?fù)淇刂七B通支配集算法研究.pdf

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

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

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