無(wú)線傳感器網(wǎng)絡(luò)中繼節(jié)點(diǎn)部署算法的研究.pdf

1、節(jié)點(diǎn)部署問(wèn)題是無(wú)線傳感器網(wǎng)絡(luò)的研究熱點(diǎn)之一，也是無(wú)線傳感器網(wǎng)絡(luò)的關(guān)鍵技術(shù)之一。傳感節(jié)點(diǎn)耗能最多的環(huán)節(jié)是傳輸數(shù)據(jù)的過(guò)程，并且傳感節(jié)點(diǎn)間的距離越大，其耗能越多。所以，當(dāng)前許多研究者提出部署中繼節(jié)點(diǎn)來(lái)分擔(dān)傳感節(jié)點(diǎn)的傳輸壓力。鑒于中繼節(jié)點(diǎn)的成本較高，所以在部署時(shí)要盡可能的減少中繼節(jié)點(diǎn)的部署數(shù)目。
　　本文提出的兩種算法，目標(biāo)是在監(jiān)測(cè)區(qū)域部署中繼節(jié)點(diǎn)，以便所有的傳感節(jié)點(diǎn)都能和至少一個(gè)中繼節(jié)點(diǎn)進(jìn)行通信，同時(shí)保證中繼節(jié)點(diǎn)數(shù)目最小化。主要研究?jī)?nèi)容

2、是在傳感節(jié)點(diǎn)的重疊區(qū)域中找到部署中繼節(jié)點(diǎn)的候選區(qū)域，進(jìn)而通過(guò)我們提出的ILP最優(yōu)解算法和啟發(fā)式算法，對(duì)這些候選區(qū)域進(jìn)行處理，以達(dá)到在最少數(shù)目的候選區(qū)域部署中繼節(jié)點(diǎn)同時(shí)，可以覆蓋到所有的傳感節(jié)點(diǎn)。由于如何擺放最少數(shù)目的中繼節(jié)點(diǎn)已經(jīng)被證明是NP-hard問(wèn)題，計(jì)算需要大量的時(shí)間，所以一般會(huì)采用近似算法來(lái)求近似解。本文中，當(dāng)傳感網(wǎng)絡(luò)規(guī)模較小時(shí)，我們采用ILP最優(yōu)解算法求其最佳解，而當(dāng)傳感網(wǎng)絡(luò)規(guī)模較大時(shí)，我們進(jìn)一步提出了啟發(fā)式算法求其近似解。<

3、br>　　在具體的算法設(shè)計(jì)中，首先找到部署中繼節(jié)點(diǎn)的候選區(qū)域CRegions;其次提出ILP最優(yōu)解算法，通過(guò)數(shù)學(xué)上的整數(shù)線性規(guī)劃的方法找到部署中繼節(jié)點(diǎn)的最佳區(qū)域;對(duì)于傳感網(wǎng)絡(luò)規(guī)模較大時(shí)，我們提出啟發(fā)式算法，由于某一個(gè)CRegions集合中含有的傳感節(jié)點(diǎn)元素越多就意味著在這個(gè)區(qū)域內(nèi)部署中繼節(jié)點(diǎn)將覆蓋的傳感節(jié)點(diǎn)數(shù)目越多，在此區(qū)域部署中繼節(jié)點(diǎn)的效益也就越高，因此將每一次排序后含傳感節(jié)點(diǎn)個(gè)數(shù)最多的集合作為部署區(qū)域，經(jīng)過(guò)多次循環(huán)排序后近似的找到部