無(wú)線傳感器網(wǎng)絡(luò)中位置受限的中繼器放置問(wèn)題.pdf

1、無(wú)線傳感器網(wǎng)絡(luò)是一種特殊的Ad-Hoc網(wǎng)絡(luò)，是基于數(shù)據(jù)采集、數(shù)據(jù)處理、數(shù)據(jù)傳輸于一體的復(fù)雜系統(tǒng)，它是由大量隨機(jī)分布的具有無(wú)線通信模塊、無(wú)線處理模塊、傳感器模塊和電源模塊的無(wú)線傳感器節(jié)點(diǎn)組成。單個(gè)傳感器節(jié)點(diǎn)可以感知它的周圍環(huán)境、執(zhí)行簡(jiǎn)單且有效的計(jì)算，并與其通信半徑內(nèi)的鄰居節(jié)點(diǎn)進(jìn)行信息傳輸，把所采集的信息最終傳輸?shù)交?。由于一個(gè)低能量的傳感器節(jié)點(diǎn)會(huì)導(dǎo)致網(wǎng)絡(luò)過(guò)早的癱瘓，人們希望通過(guò)在網(wǎng)絡(luò)中放置具有高能量的中繼器來(lái)延長(zhǎng)網(wǎng)絡(luò)的使用壽命。然而，現(xiàn)實(shí)

2、中存在著許多不定性因素，這使得有些位置不允許放置中繼器，為了解決這個(gè)問(wèn)題，就要從事先給定的可放置中繼器的位置集合中選出滿足網(wǎng)絡(luò)連通性要求的最小位置子集合來(lái)放置中繼器。中繼器的作用不是為了感知它的周圍環(huán)境和采集信息，而是為了與傳感器及其他中繼器保持通信，使傳感器采集的信息可以通過(guò)若干個(gè)中繼器成功的傳輸?shù)交?。由于中繼器的成本比較高，所以放置最少數(shù)量的中繼器也滿足了降低成本的需求。
　　在本文中，我們討論了雙層帶位置限制的無(wú)線傳感器網(wǎng)

3、絡(luò)模型，研究了怎樣放置最少個(gè)數(shù)的中繼器使無(wú)線傳感器網(wǎng)絡(luò)滿足單覆蓋單連通或雙覆蓋雙連通，提出了解決這個(gè)問(wèn)題的近似算法并給出了算法性能比分析。本文概述如下：
　　第一章介紹了有關(guān)圖論、算法理論和組合優(yōu)化方向的一些概念和定義。
　　第二章重點(diǎn)介紹無(wú)線傳感器網(wǎng)絡(luò)理論和無(wú)線傳感器網(wǎng)絡(luò)中繼器放置問(wèn)題的研究成果。
　　第三章針對(duì)雙層帶位置限制能量收獲無(wú)線傳感器網(wǎng)絡(luò)的中繼器放置問(wèn)題展開(kāi)研究，得到了一個(gè)滿足單覆蓋單連通要求性能比為9.7

4、5?的近似算法和一個(gè)滿足雙覆蓋雙連通要求ε性能比為O)(log n的近似算法。
　　第四章主要研究了無(wú)線傳感器網(wǎng)絡(luò)低干擾中繼器放置問(wèn)題，研究目的是在網(wǎng)絡(luò)中放置盡可能少的中繼器使網(wǎng)絡(luò)滿足所要求的連通水平并且總干擾值盡可能的小。本章設(shè)計(jì)了一個(gè)滿足單連通要求性能比為7.75的近似算法和一個(gè)滿足雙連通要求性能比為15的近似算法。
　　第五章主要討論了雙層帶限制無(wú)線傳感器網(wǎng)絡(luò)中繼器放置問(wèn)題，設(shè)計(jì)了一個(gè)使無(wú)線傳感器網(wǎng)絡(luò)滿足k覆蓋2連通要