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

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

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

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

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

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