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

1、無線傳感器網(wǎng)絡(luò)是由大量成本較低，能量較少的傳感器構(gòu)成的。傳感器最重要的任務(wù)是監(jiān)控一定區(qū)域，采集信息，并把信息傳輸?shù)交?。在真實環(huán)境中存在某些位置不能放置中繼器。這些位置可能受到各種信號干擾過強，或者在具體問題中不能被考慮，或者其他原因而不能放置中繼器。為了解決這個問題，我們可以考慮事先給出大量的可供選擇放置中繼器的位置，從中選出數(shù)量最少的位置放置中繼器來實現(xiàn)網(wǎng)絡(luò)連通。網(wǎng)絡(luò)壽命決定無線傳感器網(wǎng)絡(luò)采集信息的數(shù)量。向無線傳感器網(wǎng)絡(luò)中添加中繼器

2、不僅可以使網(wǎng)絡(luò)連通，而且能延長網(wǎng)絡(luò)壽命。中繼器不是為了監(jiān)控環(huán)境、采集信息而是能夠與傳感器保持通訊，使得傳感器采集的信息通過若干個中繼器到達基站。由于中繼器成本比較高，本研究希望放置數(shù)量最少的中繼器使網(wǎng)絡(luò)壽命達到T。
　　 本文的主要工作是討論雙層無線傳感器網(wǎng)絡(luò)上，具有位置限制的單覆蓋單連通中繼器放置問題和網(wǎng)絡(luò)壽命最大化的中繼器放置問題。因為這些問題是NP-hard，所以本文對第一個問題設(shè)計一個近似算法并且給出其性能比，對第二個問

3、題設(shè)計一個啟發(fā)式算法。
　　 本文結(jié)構(gòu)如下：
　　 第一章為緒論，主要介紹圖論和組合優(yōu)化的相關(guān)重要基礎(chǔ)知識。
　　 第二章介紹無線傳感器網(wǎng)絡(luò)的背景和無線傳感器網(wǎng)絡(luò)中繼器放置問題的相關(guān)研究成果及進展，內(nèi)容包括對重要文獻所用方法的描述和對相同類型問題不同算法的特點分析。
　　 第三章針對雙層網(wǎng)絡(luò)模型具有位置限制的單覆蓋單連通中繼器放置問題設(shè)計了一個近似算法并給出性能比。該算法先找到數(shù)量最少的可選位置放置中繼器

4、來覆蓋網(wǎng)絡(luò)中的傳感器，再找到數(shù)量最少的可選位置放置中繼器使得覆蓋傳感器的中繼器和基站網(wǎng)絡(luò)連通。本章證明了該算法性能比為2 9 log+d，d為一個中繼器所能覆蓋傳感器個數(shù)最大值。
　　 第四章基于貪婪算法思想，對無線傳感器網(wǎng)絡(luò)壽命最大化的中繼器放置問題設(shè)計一個啟發(fā)式算法并通過例子對該算法得到的解與最優(yōu)解比較。該算法先放置數(shù)量盡可能少的中繼器使得整個無線傳感器網(wǎng)絡(luò)連通，再對已放置的中繼器進行數(shù)量補充來使網(wǎng)絡(luò)壽命達到T。