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

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

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

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