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

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

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

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

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