關(guān)于無線傳感器網(wǎng)絡(luò)虛擬骨干網(wǎng)構(gòu)造算法的研究.pdf

1、無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）是一種全新的信息獲取平臺，能夠利用各種各樣的傳感器，實時監(jiān)測和采集網(wǎng)絡(luò)分布區(qū)域內(nèi)的各種監(jiān)測對象的信息，并將這些信息通過無線網(wǎng)絡(luò)發(fā)送到任務(wù)管理節(jié)點，以實現(xiàn)目標(biāo)對象的監(jiān)視與跟蹤。無線傳感器網(wǎng)絡(luò)具有快速展開、大范圍監(jiān)測和抗毀性強等特點，已經(jīng)引起了各國政府與研究組織的興趣，構(gòu)建虛擬骨干網(wǎng)是無線傳感器網(wǎng)絡(luò)一個熱門的研究領(lǐng)域。
　　由于無線傳感器網(wǎng)絡(luò)無基礎(chǔ)設(shè)施的特點，使得

2、網(wǎng)絡(luò)管理以及路由等問題凸顯，而傳感器節(jié)點資源又十分有限，因此，有必要構(gòu)造一個虛擬骨干網(wǎng)充當(dāng)基礎(chǔ)設(shè)施，提高資源利用率，優(yōu)化網(wǎng)絡(luò)性能。虛擬骨干網(wǎng)的構(gòu)造在數(shù)學(xué)上等同于求圖的最小連通支配集，最小連通支配集的求取問題已經(jīng)被證明是NP完全問題，目前通用的方法是采用啟發(fā)式的方法求取一個最優(yōu)解。求取連通支配集（Connected Dominating Set，CDS）的算法被分為集中式算法和分布式算法，由于無線傳感器網(wǎng)絡(luò)拓?fù)涞膭討B(tài)性特點，采用集中式算法

3、并不適合，因此多采用分布式的求取算法。本文提出了兩個分布式的CDS求取算法：FWCDS（A Forword set Based CDS Distributed Construction Algorithm）算法和LCDS（A Layer Based CDS Construction Alogrithm）算法。
　　FWCDS算法僅利用了1-hop的鄰節(jié)點信息，在每個節(jié)點上分布式的構(gòu)造一個轉(zhuǎn)發(fā)集，然后采用一個廣播染色算法，從這些轉(zhuǎn)發(fā)

4、集中選擇一部分節(jié)點作為支配節(jié)點，構(gòu)造一個連通支配集。FWCDS算法改進了OHDC算法[51]。仿真結(jié)果表明，F(xiàn)WCDS算法有約等于支配節(jié)點數(shù)的額外消息數(shù)，同時有約等于網(wǎng)絡(luò)直徑的收斂時間，而且得到了一個較小的CDS。小的額外消息數(shù)，快速的收斂以及較小的CDS，決定了FWCDS算法非常適合于動態(tài)性較強的無線傳感器網(wǎng)絡(luò)。
　　LCDS算法提出了一個分層模型，首先選取一個源節(jié)點（sink或簇頭節(jié)點），然后以此節(jié)點將網(wǎng)絡(luò)按跳數(shù)劃分成若干層。