無線傳感器網(wǎng)絡(luò)中k-連通k-支配集的集中式構(gòu)造研究.pdf

1、無線傳感器網(wǎng)絡(luò)是計算、通信和傳感器這三項(xiàng)技術(shù)相結(jié)合的產(chǎn)物，它隨著微處理器和無線通信技術(shù)的發(fā)展，在軍事、醫(yī)療、環(huán)境等方面具有廣泛的應(yīng)用潛力。由于傳感器節(jié)點(diǎn)能量有限，節(jié)點(diǎn)的失效會導(dǎo)致網(wǎng)絡(luò)鏈路失敗，因此在無線傳感器網(wǎng)絡(luò)中，通常采用連通支配集來構(gòu)成一個虛擬骨干網(wǎng)進(jìn)行分層路由，對重要的目標(biāo)或環(huán)境需要構(gòu)造容錯性高，可靠性好的虛擬骨干網(wǎng)。本文采用集中式算法研究連通支配集的構(gòu)造，主要適用于具有中心控制或管理節(jié)點(diǎn)的無線傳感器網(wǎng)絡(luò)。
　　對于1-連通

2、1-支配集的構(gòu)造，本文詳細(xì)系統(tǒng)地比較了單方向搜索和多方向搜索兩種集中式算法。通過比較得出，單方向搜索算法運(yùn)行的時間短，多方向搜索算法構(gòu)造的連通支配集小。
　　為了提高網(wǎng)絡(luò)的容錯性和可靠性，本文提出兩種2-連通2-支配集的集中式構(gòu)造算法，分別是先回路后支配和先支配后回路。前一種算法是先形成一個由支配點(diǎn)組成的回路，然后以此回路為基礎(chǔ)不斷地擴(kuò)充此回路，直到不在回路中的節(jié)點(diǎn)為2-被支配為止；后一種算法是首先保證每個非支配點(diǎn)的狀態(tài)都為2-被

3、支配，然后再使圖中所有支配點(diǎn)構(gòu)成回路。仿真結(jié)果表明算法先回路后支配適用于節(jié)點(diǎn)密度較低的網(wǎng)絡(luò)，而算法先支配后回路適用于節(jié)點(diǎn)密度較高的網(wǎng)絡(luò)。
　　在某些特殊領(lǐng)域，需要構(gòu)造容錯性更高和可靠性更好的網(wǎng)絡(luò)，本文提出k-連通k-支配集的集中式構(gòu)造算法，k適用于任意自然數(shù)。該算法被稱作先支配后連通，即首先保證圖中所有節(jié)點(diǎn)都變?yōu)橹潼c(diǎn)或k-被支配點(diǎn)，其次選擇一個邊緣支配點(diǎn)著色，然后對其它支配點(diǎn)逐點(diǎn)著色，著色的條件是該點(diǎn)是已著色節(jié)點(diǎn)的鄰接點(diǎn)，且和已