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

1、無(wú)線傳感器網(wǎng)絡(luò)是由多個(gè)節(jié)點(diǎn)組成的面向任務(wù)的無(wú)線自組織網(wǎng)絡(luò)。它綜合了傳感器技術(shù)、嵌入式計(jì)算技術(shù)、現(xiàn)代網(wǎng)絡(luò)及無(wú)線通信技術(shù)、分布式信息處理技術(shù)等，通過(guò)衛(wèi)星傳感器對(duì)目標(biāo)信息進(jìn)行實(shí)時(shí)監(jiān)測(cè)，對(duì)信息進(jìn)行處理，從而將信息傳遞給遠(yuǎn)程監(jiān)控中心。無(wú)線傳感器網(wǎng)絡(luò)具有感知、計(jì)算和通信能力。大量的無(wú)線傳感器節(jié)點(diǎn)分布在需要監(jiān)測(cè)的區(qū)域，監(jiān)測(cè)特定的信息、物理參量等。但是無(wú)線傳感器節(jié)點(diǎn)往往分布在惡劣的環(huán)境中，傳感器節(jié)點(diǎn)很容易損壞，且傳感器網(wǎng)絡(luò)是由電池供電的，電池的續(xù)航能力

2、較小。在許多應(yīng)用領(lǐng)域中，常常無(wú)法更換電池或?qū)﹄姵爻潆?，?dāng)傳感器節(jié)點(diǎn)電能用完，該節(jié)點(diǎn)就失去了作用。因此在對(duì)進(jìn)行無(wú)線傳感器網(wǎng)絡(luò)設(shè)計(jì)時(shí)，能耗問(wèn)題是我們關(guān)注的一大問(wèn)題。通過(guò)向無(wú)線傳感器網(wǎng)絡(luò)中放置功能更加強(qiáng)大的中繼器也成為了減少網(wǎng)絡(luò)能耗延長(zhǎng)網(wǎng)絡(luò)使用壽命的的重要策略。
　　本文的主要研究工作集中在雙層無(wú)線傳感器網(wǎng)絡(luò)的中繼器放置問(wèn)題的一類(lèi)特殊問(wèn)題。由于中繼器的成本相對(duì)較高，所以我們希望通過(guò)放置數(shù)目最少的中繼器以實(shí)現(xiàn)的網(wǎng)絡(luò)的連通性和覆蓋性。本文所

3、討論的問(wèn)題都是NP問(wèn)題，所以針對(duì)的相應(yīng)的問(wèn)題的設(shè)計(jì)的算法均是近似算法。本文結(jié)構(gòu)如下：
　　第1章緒論介紹了本文有關(guān)圖論與網(wǎng)絡(luò)的基本知識(shí)、組合優(yōu)化問(wèn)題中的有關(guān)定義、算法的基本內(nèi)容，為后面的章節(jié)做鋪墊。
　　第2章概述了無(wú)線傳感器網(wǎng)絡(luò)中放置問(wèn)題的發(fā)展歷史、研究現(xiàn)狀及意義,分別介紹了單層無(wú)線傳感器網(wǎng)絡(luò)模型、雙層無(wú)線傳感器網(wǎng)絡(luò)模型和混合型無(wú)線傳感器網(wǎng)絡(luò)模型。對(duì)于其中的某些文獻(xiàn)，給出了單層、雙層、混合型無(wú)線傳感器網(wǎng)絡(luò)的現(xiàn)有算法以及算法

4、的性能比。本章對(duì)這些同類(lèi)型問(wèn)題的不同算法的結(jié)果進(jìn)行了比較，并分析了這些算法的優(yōu)缺點(diǎn)。
　　第3章為本文的重要章節(jié)，由于傳感器節(jié)點(diǎn)容易損壞，所以容錯(cuò)性研究在無(wú)線傳感器網(wǎng)絡(luò)的研究領(lǐng)域至關(guān)重要。本章首先研究了二維平面中含有基站的雙層無(wú)線傳感器網(wǎng)絡(luò)放置問(wèn)題。根據(jù)特定的中繼器與傳感器傳輸半徑關(guān)系以及不同的算法分區(qū)因子，針對(duì)k-覆蓋2-連通問(wèn)題分別設(shè)計(jì)了性能比為常數(shù)的近似算法，并給出算法的界估計(jì)。在此基礎(chǔ)上，加以推廣，設(shè)計(jì)了k-覆蓋k-連通問(wèn)

5、題的近似算法，并給出算法的性能比分析。
　　第4章在第三章的基礎(chǔ)上，研究了三維空間上的無(wú)線傳感器網(wǎng)絡(luò)的中繼器放置問(wèn)題。隨著研究的深入和實(shí)際應(yīng)用的需求，三維無(wú)線傳感器網(wǎng)絡(luò)的需求也逐漸增大。本章將無(wú)線傳感器網(wǎng)絡(luò)的研究從二維平面延伸到三維空間中，對(duì)于三維空間中的無(wú)線傳感器網(wǎng)絡(luò)的k-覆蓋2-連通問(wèn)題，設(shè)計(jì)算法，給出性能比及分析，緊接著將其容錯(cuò)性研究推廣到k-覆蓋k-連通問(wèn)題，并設(shè)計(jì)相應(yīng)的算法，給出常數(shù)性能比。
　　第5章對(duì)全本文進(jìn)行