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

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

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

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