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

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

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

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