無線傳感器網(wǎng)絡(luò)若干中繼器放置問題研究.pdf

1、節(jié)能是無線傳感器網(wǎng)絡(luò)研究的核心問題。傳感器隨機分布在惡劣環(huán)境中，能量由電池提供，電池不能夠隨意更換。但是長距離通訊中能量消耗以距離指數(shù)形式增長，因此放置功能強大的中繼器成為了減少能量損耗的重要方法。本文主要研究在不同類型的無線傳感器網(wǎng)絡(luò)中放置最少數(shù)目的中繼器達到一定的覆蓋和連通要求。
　　 首先從圖與網(wǎng)絡(luò)及組合優(yōu)化的基本理論知識入手，為后續(xù)章節(jié)作鋪墊。
　　 第2章闡述無線傳感器網(wǎng)絡(luò)相關(guān)知識背景和研究進展，主要針對重要文

2、獻，介紹常用的數(shù)學(xué)模型和典型方法、算法，并對其優(yōu)缺點進行比較、分析。
　　 第3章至第5章為本文重點內(nèi)容，這里討論的問題均為NP-hard 問題，故針對每個問題設(shè)計了相應(yīng)的近似算法。
　　 第3章首先討論含有基站的單層無線傳感器網(wǎng)絡(luò)放置問題，根據(jù)傳感器和中繼器傳輸半徑的不同情況，分別設(shè)計了性能比為3和7的近似算法，并且對于后者，給出了算法的下界估計。繼而在雙層無線傳感器網(wǎng)絡(luò)中引入基站，設(shè)計了性能比為5ε+的近似算法，為第

3、4章的研究奠定基礎(chǔ)。傳感器節(jié)點很容易被破壞，在任何情況下都可能由于能量損耗、環(huán)境侵蝕或是受到惡意攻擊而失效，因此有關(guān)容錯性的設(shè)計至關(guān)重要。
　　 第4章分別研究了含有基站的單層和雙層無線傳感器網(wǎng)絡(luò)的容錯性。對于單層無線傳感器網(wǎng)絡(luò)，研究k-連通問題；對于雙層無線傳感器網(wǎng)絡(luò)，首先對雙覆蓋雙連通問題設(shè)計近似算法，并將其容錯性推廣到k-覆蓋2-連通，給出算法及性能比。隨著定位系統(tǒng)的日益發(fā)展，二維空間的研究漸漸不能夠滿足人們的需求。