無線傳感器網絡中k-連通k-支配集的集中式構造研究.pdf

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

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

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