無線傳感器網(wǎng)絡分布式連通支配集構造方法研究.pdf

1、無線傳感器網(wǎng)絡（Wireless Sensor Network，WSN）是21世紀極具應用價值的新興學科之一。通過WSN人們可以即時監(jiān)控，收集并分析WSN監(jiān)測區(qū)域內(nèi)監(jiān)測對象的各種有效信息，并可將有效信息通過WIFI、GPRS、移動數(shù)據(jù)網(wǎng)絡等多種方式傳送到任務管理節(jié)點，以此達到對監(jiān)測目標情況變化的實時監(jiān)控與及時報警。WSN具有易于布置、監(jiān)控區(qū)域廣和環(huán)境適應力強等特點，如今，無論在軍事、商用還是民用領域，WSN技術都受到越來越多的重視，而有

2、效地構造WSN的虛擬骨干網(wǎng)（Virtual-Backbone）則是當今WSN領域的一個熱點研究課題。
　　因為WSN傳感器節(jié)點體積小，分布范圍廣，所以對傳感器節(jié)點的管理和維護十分困難，構造一個高效的虛擬骨干網(wǎng)，可以從軟件方面延長網(wǎng)絡的生存時間，降低維護成本。本文通過求解性能最優(yōu)的連通支配集（Connected Dominating Set，CDS）來構造虛擬骨干網(wǎng)。最小連通支配集的求取已經(jīng)被證明是NP完全問題，現(xiàn)在最通用的手段是通

3、過啟發(fā)式的方法求得最優(yōu)解。求取連通支配集的算法主要分為集中式和分布式兩種，因為WSN的動態(tài)性特點，集中式算法難以適應網(wǎng)絡的實時變化，故多采用分布式的求取算法。本文提出了兩個優(yōu)化的分布式CDS求解算法：MI-LCDS（Multi-Initiator Layer Based CDS Construction Algorithm）算法和FNDB（A Forward1-hop neighbor Information set Based Dis

4、tributed algorithm for Virtual Backbone）算法。
　　MI-LCDS算法提出了基于多發(fā)起者的網(wǎng)絡分層模型，首先根據(jù)網(wǎng)絡的規(guī)模選取數(shù)個源節(jié)點，源節(jié)點獨立地進行各自區(qū)域范圍內(nèi)的網(wǎng)絡劃分，得到分層結構，網(wǎng)絡各層分布式地求取本層的CDS。最后，不同源節(jié)點的CDS通過橋梁節(jié)點連通，完成整個網(wǎng)絡CDS的構造。MI-LCDS算法的時間復雜度為O(Δ2)。
　　FNDB算法只需一跳鄰居節(jié)點信息，在成功求