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

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

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

3、過啟發(fā)式的方法求得最優(yōu)解。求取連通支配集的算法主要分為集中式和分布式兩種，因?yàn)閃SN的動(dòng)態(tài)性特點(diǎn)，集中式算法難以適應(yīng)網(wǎng)絡(luò)的實(shí)時(shí)變化，故多采用分布式的求取算法。本文提出了兩個(gè)優(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)絡(luò)分層模型，首先根據(jù)網(wǎng)絡(luò)的規(guī)模選取數(shù)個(gè)源節(jié)點(diǎn)，源節(jié)點(diǎn)獨(dú)立地進(jìn)行各自區(qū)域范圍內(nèi)的網(wǎng)絡(luò)劃分，得到分層結(jié)構(gòu)，網(wǎng)絡(luò)各層分布式地求取本層的CDS。最后，不同源節(jié)點(diǎn)的CDS通過橋梁節(jié)點(diǎn)連通，完成整個(gè)網(wǎng)絡(luò)CDS的構(gòu)造。MI-LCDS算法的時(shí)間復(fù)雜度為O(Δ2)。
　　FNDB算法只需一跳鄰居節(jié)點(diǎn)信息，在成功求