最小連通支配集算法研究.pdf

1、最小連通支配集在無線傳感器網(wǎng)絡(WSN)中發(fā)揮著重要的作用，它可以作為一個“虛擬骨干網(wǎng)”從而可以減少節(jié)點的能量損耗、網(wǎng)絡拓撲維護的開銷，減輕廣播風暴的影響等。構造一個最小連通支配集被證明是一個NP完全問題，并且無線傳感器網(wǎng)絡中的節(jié)點具有能量、存儲和計算方面的約束，以及無線傳感器網(wǎng)絡的無中心自組織成網(wǎng)、多跳通信的特征，因此許多學者對在無線傳感器網(wǎng)絡中構造最小連接支配集這一問題展開了廣泛而又深入的研究。
　　作者以靜態(tài)的無線傳感器網(wǎng)絡

2、為研究目標，設計了四個近似最小連通支配集的分布式算法。算法-Ⅰ是一個完全異步并行的算法，網(wǎng)絡中的每個節(jié)點異步并同時執(zhí)行相同的算法且只根據(jù)一跳鄰居的消息來決定自己是否加入連通支配集。根據(jù)最大獨立集亦是一個支配集，算法-Ⅰ首先構造一個最大獨立集，然后通過“信息三跳中繼”結合相應的規(guī)則使其它一些節(jié)點加入最大獨立集，使最大獨立集連通，最終生成連通支配集。在算法-Ⅱ中，以“有效度”代替節(jié)點的度數(shù)來作為選取屬于最大獨立集中的支配點的標準，可以有效減

3、少生成的連通支配集的大小。算法-Ⅰ與算法-Ⅱ構建的近似最小連通支配集的收斂時間與網(wǎng)絡規(guī)模、拓撲結構等直接相關，存在收斂時間不可直接控制和估計等問題。因此作者設計了算法-Ⅲ。算法-Ⅲ分為兩個階段，分別為初始化階段和狀態(tài)更新階段。通過對不同規(guī)模和拓撲結構的無線傳感器網(wǎng)絡進行計算機仿真，可以得到構造近似最小連通支配集所需的相關時間參數(shù)。在算法-Ⅳ中，作者首次提出把兩個支配點之間的節(jié)點個數(shù)等效轉化成帶有權值的路徑，從而轉化成有權圖，然后在這個圖