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

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

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

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