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

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

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

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