無線傳感器網絡中繼器放置問題算法研究.pdf

1、無線傳感器網絡是由大量隨機分布在惡劣環(huán)境中的價格低廉的傳感器節(jié)點組成，這些傳感器節(jié)點具有區(qū)域監(jiān)測、數(shù)據處理和短距離通訊的功能，由于傳感器節(jié)點本身安裝的電池不能隨意更換或者充電，而傳輸信息需要消耗能量，并且通訊能量的消耗也是以距離的指數(shù)形式增長，因而如何減少信息傳輸過程中的能量損耗將是今后重點研究的課題。
　　 本文的主要工作是討論無線傳感器網絡中具有不同條件的兩個中繼器放置問題，對這兩個問題都設計了近似算法并且給出其相應的性能比

2、的證明，本文結構如下：
　　 第一章為緒論，主要介紹圖、網絡以及組合優(yōu)化的相關基礎知識。
　　 第二章主要介紹無線傳感器網絡的發(fā)展背景、無線傳感器網絡中繼器放置問題目前已經取得的主要研究成果以及進展，主要是簡單描述一些重要參考文獻中所用的方法，以及在相同類型的問題中，針對不同的文章提出的算法的特點進行分析。
　　 第三章針對單層網絡模型上具有位置限制且連通度要求不同的中繼器放置問題設計了一個近似算法，并給出該算法

3、性能比的證明。該算法首先是通過給每條邊設定不同的權值，然后找出滿足不同傳感器到基站之間有不同數(shù)目的點不相交的路的要求，并且最終的網絡是所有邊的權重之和最小的連通網絡，經證明該算法的性能比是10。
　　 第四章討論無線傳感器網絡上當R=r時的中繼器放置問題，通過設計算法，滿足每個傳感器到基站都至少存在兩條點不相交的路的要求，并給出了其性能比的證明。
　　 第五章主要是全文內容的概括和總結，并對接下來的研究進行了展望。