無(wú)線傳感器網(wǎng)絡(luò)中多跳連通簇群集的構(gòu)造與分析.pdf

1、目前，無(wú)線傳感器網(wǎng)絡(luò)已經(jīng)被應(yīng)用在許多生活場(chǎng)景中。為了提高傳感器節(jié)點(diǎn)收集數(shù)據(jù)的效率，我們通常會(huì)將整個(gè)網(wǎng)絡(luò)劃分成許多個(gè)重疊較少的簇（Cluster），每個(gè)簇中有個(gè)簇頭（Cluster Head，CH）負(fù)責(zé)相應(yīng)簇內(nèi)部其它傳感器的數(shù)據(jù)傳輸以及和外界其它簇的通信。很明顯，對(duì)一個(gè)無(wú)線傳感器網(wǎng)絡(luò)進(jìn)行劃分的方式有非常多種，但是為了提高最終簇群的工作效率，選擇一個(gè)有效的劃分方式尤為重要。本文中，我們討論的劃分滿足兩個(gè)限制約束，一個(gè)是保證簇中普通傳感器和相

2、應(yīng)簇頭的距離不超過(guò)d，其中d是一個(gè)系統(tǒng)參數(shù)；其次，相鄰簇的簇頭可以互相通信。另外，為了使得網(wǎng)絡(luò)管理更加的高效，我們希望劃分出來(lái)的結(jié)果中簇的數(shù)量應(yīng)該盡可能的少。如何從一個(gè)無(wú)線傳感器網(wǎng)絡(luò)中尋找滿足以上兩個(gè)條件，并且保證選出的簇群數(shù)量最少呢？在數(shù)學(xué)上，這個(gè)問(wèn)題可以轉(zhuǎn)變成d跳最小連通支配集（d-MCDS)問(wèn)題。并且前人已經(jīng)證明了，d-MCDS問(wèn)題是NP完全的。
　　本文中，我們將討論如何給出d-MCDS問(wèn)題的一個(gè)近似解，并且分析其與最優(yōu)解

3、的近似程度。結(jié)合無(wú)線傳感器網(wǎng)絡(luò)本身的特性，我們提出了一個(gè)分布式的近似算法（CS-Cluster）用于求解d-MCDS問(wèn)題。CS-Cluster分為三個(gè)階段執(zhí)行：首先它先構(gòu)造一個(gè)稀疏的d跳最大無(wú)關(guān)集（d-MIS）；然后，通過(guò)向d-MIS中添加一些額外的傳感器節(jié)點(diǎn)，使得d-MIS中的傳感器節(jié)點(diǎn)可以連通；最后，算法通過(guò)去除冗余節(jié)點(diǎn)，使得最終的簇群數(shù)量更小。對(duì)于CS-Cluster，我們還從理論上分析了它的性能，并且給出了它的一個(gè)常數(shù)級(jí)近似比(