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

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

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

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

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