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

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

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

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