無線傳感器網(wǎng)絡(luò)中最小連通傳感器覆蓋問題的研究.pdf

1、近年來，隨著各種微技術(shù)的迅速發(fā)展，具有感知、通信、數(shù)據(jù)處理、存儲(chǔ)能力的傳感器節(jié)點(diǎn)構(gòu)成的無線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks, WSNs）引起了社會(huì)各界學(xué)者的廣泛關(guān)注。在WSN中，覆蓋體現(xiàn)了該WSN對物理監(jiān)測區(qū)域的感知程度，而連通則表明了WSN中節(jié)點(diǎn)間發(fā)送和接收數(shù)據(jù)的能力。覆蓋和連通作為WSN中的兩個(gè)基礎(chǔ)問題，對網(wǎng)絡(luò)的能量消耗與生存周期有著重要影響。
　　在WSN執(zhí)行監(jiān)測任務(wù)時(shí)，選擇盡量少的傳感器節(jié)點(diǎn)參與

2、，不僅可以降低網(wǎng)絡(luò)能耗，提升網(wǎng)絡(luò)能量的高效性，還能減少傳感器節(jié)點(diǎn)間的通信開銷，降低鄰近傳感器節(jié)點(diǎn)間感知數(shù)據(jù)的冗余度。基于此點(diǎn)，本文綜合考慮WSN中的覆蓋與連通問題，找到感知區(qū)域滿足覆蓋整個(gè)目標(biāo)區(qū)域，且所誘導(dǎo)出的網(wǎng)絡(luò)為一個(gè)連通網(wǎng)絡(luò)的最小工作傳感器節(jié)點(diǎn)集，從而延長網(wǎng)絡(luò)的生存周期。
　　本文首先提出了一種能夠滿足網(wǎng)絡(luò)覆蓋與連通要求的基于 Connected Benefit的節(jié)點(diǎn)選擇算法。該算法首先通過計(jì)算節(jié)點(diǎn)對覆蓋的貢獻(xiàn)量，選擇出滿足覆

3、蓋條件的節(jié)點(diǎn)集合，然后根據(jù)節(jié)點(diǎn)的Connected Benefit值補(bǔ)充最少的節(jié)點(diǎn)到結(jié)果集，使之滿足連通條件，從而選擇出數(shù)目最少的節(jié)點(diǎn)執(zhí)行監(jiān)測任務(wù)。
　　本文接著利用最小生成樹（MST）的基本思想，提出了另一種新的節(jié)點(diǎn)選擇算法。該算法在連通階段，通過構(gòu)造一棵權(quán)重之和最小的MST對節(jié)點(diǎn)進(jìn)行選擇，使之滿足覆蓋與連通條件。
　　最后本文提出了一種基于Group Steiner Tree與線性規(guī)劃的節(jié)點(diǎn)選擇算法。該算法通過構(gòu)造Gro

4、up Steiner Tree并用線性規(guī)劃對其求解，計(jì)算出每個(gè)節(jié)點(diǎn)被選擇的概率，為找到近似解提供正確的方向，然后利用求得的節(jié)點(diǎn)概率值與隨機(jī)rounding技術(shù)選擇出滿足覆蓋與連通的節(jié)點(diǎn)集合。
　　基于Connected Benefit與基于MST的節(jié)點(diǎn)選擇算法，均將覆蓋和連通分開來考慮，而基于Group Steiner Tree與線性規(guī)劃的節(jié)點(diǎn)選擇算法將二者聯(lián)合考慮。通過實(shí)驗(yàn)對比驗(yàn)證，本文提出的三種算法在不同的網(wǎng)絡(luò)環(huán)境中，性能有所