無線傳感器網(wǎng)絡(luò)中連通支配集的構(gòu)造算法研究.pdf

1、無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks, WSNs)通常是指由數(shù)目眾多的傳感器節(jié)點大規(guī)模布局而形成的網(wǎng)絡(luò)系統(tǒng),節(jié)點利用無線通訊、多跳和自組織的方式把收集的信息傳遞到基站。在現(xiàn)實生活中,它被廣泛地運用于戰(zhàn)場偵測、家居智能和管理自動化等眾多領(lǐng)域。WSNs因在應(yīng)用方面有很多優(yōu)點而成為了眾多高校和機(jī)構(gòu)研究的熱門方向。由于傳感器節(jié)點具備體積小、能量低、處理和存儲能力較低等特點,且它一般地處人類無法抵達(dá)的地方(不能對它進(jìn)行

2、人為補充能量),因此怎樣高效利用網(wǎng)絡(luò)中的節(jié)點能量從而使它的壽命最長,從一開始就成為了WSNs中值得研究的熱點課題。而連通支配集作為WSNs的虛擬主干網(wǎng)在高效利用網(wǎng)絡(luò)能量上具有良好的表現(xiàn)。
　　本研究為了解決WSNs中無固定的基本設(shè)施和節(jié)點能量消耗不均衡的問題,設(shè)計了構(gòu)建連通支配集的分布式近似方案,此算法綜合考慮了節(jié)點的剩余能量、連通支配集規(guī)模和連通支配集重構(gòu)等因素。我們從理論上證明了算法的正確性,實驗結(jié)果表明,與相關(guān)的分布式算法相

3、比,此算法構(gòu)造的連通支配集在規(guī)模上更優(yōu),可使網(wǎng)絡(luò)壽命更長。此外,為了解決因節(jié)點失效或節(jié)點間無法通信而引起的連通支配集要經(jīng)常重新構(gòu)建的問題,本文還設(shè)計了一種構(gòu)建具有容錯性的連通支配集分布式近似算法,即在網(wǎng)絡(luò)中構(gòu)造一個k-連通m-支配的集合(也稱為(k, m)-連通支配集)。該算法綜合考慮了(k, m)-連通支配集的規(guī)模和節(jié)點的剩余能量等因素,且本文從理論上證明了算法的正確性。仿真實驗結(jié)果與相關(guān)算法比較,該算法得到的(k, m)-連通支配集