無線傳感器網(wǎng)絡(luò)中連通支配集近似算法的設(shè)計與仿真.pdf

1、無線傳感器網(wǎng)絡(luò)(WirelessSensorNetwork，WSN)是一種全新的信息獲取平臺，能夠利用各種各樣的傳感器，實時監(jiān)測和采集網(wǎng)絡(luò)分布區(qū)域內(nèi)的各種監(jiān)測對象的信息，并將這些信息通過無線網(wǎng)絡(luò)發(fā)送到匯聚節(jié)點(diǎn)，以實現(xiàn)目標(biāo)對象的監(jiān)視與跟蹤。因此是目前研究的熱點(diǎn)。
　　一方面由于無線傳感器網(wǎng)絡(luò)無基礎(chǔ)設(shè)施的特點(diǎn)，使得網(wǎng)絡(luò)管理以及路由等問題凸顯。另一方面?zhèn)鞲衅鞴?jié)點(diǎn)資源又十分有限。因此，為提高節(jié)點(diǎn)資源利用率和優(yōu)化網(wǎng)絡(luò)性能有必要構(gòu)造一個虛擬骨

2、干網(wǎng)充當(dāng)基礎(chǔ)設(shè)施。虛擬骨干網(wǎng)的構(gòu)造在數(shù)學(xué)上等同于求圖的最小連通支配集，最小連通支配集的求取問題已經(jīng)被證明是NP難問題，本文從求支配集出發(fā)來進(jìn)行研究。具體主要工作如下：
　　(1)綜述無線傳感器網(wǎng)絡(luò)體系結(jié)構(gòu)、組成、特點(diǎn)及其應(yīng)用。引入由連通支配集組成的虛擬骨干網(wǎng)思想，并對現(xiàn)在的連通支配集算法進(jìn)行說明。
　　(2)引入一些圖論基本知識，基于圖論知識對抽象為單位圓圖的無線傳感器網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行了敘述。
　　(3)從圖的覆蓋和連

3、通兩方面來分析圖的連通性。首先進(jìn)行了覆蓋與連通的比較，其次建立相應(yīng)模型從通信半徑、鄰居節(jié)點(diǎn)個數(shù)進(jìn)行連通概率分析。最后從各個方面進(jìn)行了仿真實驗。
　　(4)給出了連通支配集定義和性質(zhì)，并對已有經(jīng)典的連通支配集算法進(jìn)行論述。
　　(5)從一次處理多個節(jié)點(diǎn)和獲取點(diǎn)數(shù)更少的2-hop支配集兩個角度，分別提出了連通支配集構(gòu)造算法GCDS和2-hop支配集算法2-DSGA。不同多數(shù)每次處理一個節(jié)點(diǎn)的求CDS算法，GCDS算法基于貪心策略