基于改進(jìn)混合粒子群優(yōu)化算法的移動(dòng)節(jié)點(diǎn)部署研究*

朱正偉， 刁小敏， 郭 曉， 劉 晨

0 引 言

覆蓋率是衡量無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor networks,WSNs)[1]質(zhì)量的重要指標(biāo)。在WSNs中，數(shù)據(jù)采集節(jié)點(diǎn)分為靜態(tài)節(jié)點(diǎn)和移動(dòng)節(jié)點(diǎn)。移動(dòng)節(jié)點(diǎn)部署能夠在初始隨機(jī)部署后，改變網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，實(shí)現(xiàn)網(wǎng)絡(luò)自組織，提高網(wǎng)絡(luò)的覆蓋質(zhì)量。

Mateska A等人[2]設(shè)計(jì)了一種分布式算法用于提高網(wǎng)絡(luò)連通性和網(wǎng)絡(luò)覆蓋率。劉繼忠等人[3]提出了免疫粒子群算法通過(guò)在部署區(qū)域給定傳感器節(jié)點(diǎn)數(shù)量，最大化網(wǎng)絡(luò)覆蓋率和在區(qū)域具有所需覆蓋率的傳感器節(jié)點(diǎn)數(shù)目最小化。周劍波等人[4]提出了一種虛擬力擾動(dòng)指數(shù)權(quán)值遞減型粒子群算法，用于加快算法收斂速度，提高覆蓋率。袁曦等人[5]提出了改進(jìn)蝙蝠算法，改善傳感器節(jié)點(diǎn)的覆蓋密度，使得分布相對(duì)比較均勻。

基于粒子群優(yōu)化(particle swarm optimization,PSO)算法[6～10]的WSNs覆蓋應(yīng)用研究較多。本文將模擬退火算法[11，12]和改進(jìn)粒子群優(yōu)化算法[13]相結(jié)合即改進(jìn)混合粒子群優(yōu)化 (improved hybrid PSO,IM-HPSO) 算法優(yōu)化移動(dòng)節(jié)點(diǎn)的部署。同時(shí)在建立傳感器節(jié)點(diǎn)部署模型時(shí)同時(shí)考慮了網(wǎng)絡(luò)覆蓋率和節(jié)點(diǎn)的移動(dòng)能耗即多目標(biāo)函數(shù)[14,15]，提高了網(wǎng)絡(luò)服務(wù)質(zhì)量。

1 傳感器節(jié)點(diǎn)部署模型

移動(dòng)傳感器節(jié)點(diǎn)感知模型采用概率感知優(yōu)化模型。

定義移動(dòng)節(jié)點(diǎn)部署區(qū)域?yàn)閃×W的二維區(qū)域并將其網(wǎng)格化，假設(shè)在該區(qū)域隨機(jī)部署N個(gè)移動(dòng)節(jié)點(diǎn)(N=n1,n2,…,ni,…,nN)，每個(gè)移動(dòng)節(jié)點(diǎn)感知半徑為R，通信半徑為2R，以確保網(wǎng)絡(luò)的連通性。移動(dòng)節(jié)點(diǎn)ni覆蓋二維區(qū)域的目標(biāo)點(diǎn)Tj的概率如下

(1)

式中rθ為移動(dòng)節(jié)點(diǎn)檢測(cè)誤差的范圍;Ei0為節(jié)點(diǎn)初始能量大小;Eis為節(jié)點(diǎn)剩余能量大小;λ，β，β′為由傳感器節(jié)點(diǎn)的物理特性決定的性能參數(shù);α=D-(r-rθ)，α′=(r+rθ)-D;D(ni,Tj)為傳感器節(jié)點(diǎn)ni=(xi,yi)到目標(biāo)點(diǎn)Tj=(xj,yj)的距離

(2)

由于移動(dòng)節(jié)點(diǎn)部署WSNs(mobile WSNs,MWSNs)由N個(gè)移動(dòng)節(jié)點(diǎn)組成，則目標(biāo)點(diǎn)Tj被所有移動(dòng)節(jié)點(diǎn)覆蓋概率為

(3)

WSNs在二維平面區(qū)域Q的覆蓋率為

(4)

(5)

IM-HPSO算法通過(guò)重新調(diào)整位置來(lái)提高M(jìn)WSNs的覆蓋率，假設(shè)節(jié)點(diǎn)移動(dòng)單位距離所需能量相同，移動(dòng)距離為節(jié)點(diǎn)從初始位置移動(dòng)到目標(biāo)位置之間的距離，則MWSNs中網(wǎng)絡(luò)能耗主要指所有移動(dòng)節(jié)點(diǎn)的移動(dòng)距離之和與單位距離消耗能量的乘積 ,即

(6)

式中k為單位距離能耗系數(shù);D(ni,di)為移動(dòng)節(jié)點(diǎn)ni從初始位置移動(dòng)到最終位置di之間的線性距離。

在MWSNs節(jié)點(diǎn)部署模型中，設(shè)f為適應(yīng)度函數(shù)，函數(shù)值設(shè)置為高覆蓋率和少的能量消耗，公式如下

f=w×PC(N,Q)+(1+w)EN

(7)

式中w為無(wú)線傳感網(wǎng)覆蓋率和網(wǎng)絡(luò)能耗在該函數(shù)中所占比重。

2 基于IM-HPSO算法的移動(dòng)節(jié)點(diǎn)部署

2.1 IM_HPSO算法

1)改進(jìn)粒子群算法

自適應(yīng)權(quán)重粒子群算法根據(jù)粒子位置來(lái)改變權(quán)重系數(shù)，避免粒子的局部最優(yōu)問(wèn)題，權(quán)重系數(shù)變化如下

(8)

式中w為變化的慣性權(quán)重；wmax為粒子慣性權(quán)重的最大值；wmin為粒子慣性權(quán)重的最小值；f為當(dāng)前粒子的適應(yīng)度函數(shù)值；fmin為種群的最小函數(shù)值；favg為種群的平均函數(shù)值。

在自適應(yīng)權(quán)重PSO算法中，引入收縮因子φ

(9)

φ用于改變粒子的速度，調(diào)整粒子的位置，實(shí)現(xiàn)局部最優(yōu)和全局最優(yōu)之間的平衡，避免算法陷入早熟收斂，粒子的速度和位置更新公式為

xij(t+1)=xij(t)+vij(t+1)

(10)

vij(t+1)=φ{(diào)w×vij(t)+c1r1(pbestij(t)-xij(t))+

c2r2(gbestij(t)-xij(t))}

(11)

式中vij(t+1)為第i個(gè)粒子在t次迭代后的速度；vij(t)為粒子當(dāng)前的速度;c1，c2為學(xué)習(xí)因子，取2左右的隨機(jī)數(shù);pbestij(t)為第i個(gè)粒子在第t次迭代時(shí)的個(gè)體極值;gbestij為第i個(gè)粒子在第t次迭代時(shí)的全局極值。

為了進(jìn)一步保持種群中粒子多樣性，在自適應(yīng)權(quán)重粒子群算法中融入自然選擇操作機(jī)理。按照粒子群更新之后的函數(shù)值大小排序，用函數(shù)值較好的粒子根據(jù)比例進(jìn)行替換函數(shù)值較差的粒子，并記錄每個(gè)粒子的歷史個(gè)體最優(yōu)值。

2)模擬退火算法

3)IM-HPSO算法

將SA算法引入改進(jìn)PSO算法提出了IM-HPSO。當(dāng)粒子群陷入局部極值時(shí)，該算法能夠根據(jù)Metropolis準(zhǔn)則以一定的概率修改該極值，從而繼續(xù)搜索，跳出局部極值，尋找整體最優(yōu)解。

由式(11)可知，算法采用了全局最優(yōu)位置，粒子群所有個(gè)體向該位置靠近，此時(shí)，如果處于局部極小值，則所有粒子陷入局部極值，導(dǎo)致種群全局搜索能力變差，根據(jù)IM-HPSO算法，能夠根據(jù)Metropolis準(zhǔn)則以一定的概率修改該局部極值,則概率如下

(12)

式中f(pi)為當(dāng)前粒子的最優(yōu)目標(biāo)函數(shù)值;f(g)為粒子群最優(yōu)目標(biāo)函數(shù)值。

vij(t+1)=φ{(diào)w×vij(t)+c1r1(pbestij(t)-xij(t))+

xij(t))}

(13)

因此，IM-HPSO算法能夠跳出局部極值，繼續(xù)搜索，尋找全局最優(yōu)解，提高算法的收斂速度，避免陷入局部最優(yōu)以及早熟收斂。

2.2 移動(dòng)節(jié)點(diǎn)部署策略

策略如下：

1)根據(jù)式(1)～ 式(7)，在WSNs移動(dòng)節(jié)點(diǎn)模型中定義適應(yīng)度為網(wǎng)絡(luò)覆蓋率以及能量消耗的多目標(biāo)函數(shù)。

2)確定種群數(shù)量M，隨機(jī)分布各個(gè)粒子群體。

3)通過(guò)適應(yīng)度函數(shù)評(píng)價(jià)每個(gè)粒子的適應(yīng)度值，確定粒子的個(gè)體最優(yōu)值pbest，以及從所有個(gè)體最優(yōu)中選擇全局最優(yōu)值gbest。

4)確定初始溫度

t0=f(pbestij(t))/ln 5

(14)

5)根據(jù)式(12)確定當(dāng)前溫度下各粒子的適應(yīng)值。

6)從適應(yīng)值中選擇全局最優(yōu)值的替換值 ，根據(jù)式(8)～式(13)更新各粒子的位置，速度和權(quán)重。

7)計(jì)算各個(gè)粒子新的適應(yīng)度，并與個(gè)體最優(yōu)值比較，再與全局最優(yōu)值比較，更新結(jié)果。

8)按照更新后的適應(yīng)值大小來(lái)排序，適應(yīng)值較好的粒子根據(jù)比例替換適應(yīng)值較差的粒子，并記錄每個(gè)粒子的歷史個(gè)體最優(yōu)值。

9)退溫操作，退溫方式為

tk+1=mtk,m∈(0,1)

(15)

10)當(dāng)?shù)螖?shù)達(dá)到設(shè)定值或者連續(xù)若干解未被接受，輸出MWSNs節(jié)點(diǎn)部署最優(yōu)位置，WSNs覆蓋率以及能量消耗;否則,返回步驟(4)。

3 仿真結(jié)果

在MATLAB R2014a仿真工具上進(jìn)行實(shí)驗(yàn)。設(shè)置待部署區(qū)域?yàn)?0×40的網(wǎng)格點(diǎn)，初始時(shí)隨機(jī)部署40個(gè)移動(dòng)節(jié)點(diǎn)，傳感器節(jié)點(diǎn)的參數(shù)設(shè)置如下：傳感半徑R=4，通信半徑2R=8，λ=1，rij=0.8，β=1，β′=0.5。

為了消除算法的隨機(jī)性，每次仿真運(yùn)行10次，計(jì)算結(jié)果的平均值。算法參數(shù)值設(shè)置如下:種群數(shù)目為M=100，c1=c2=2，wmax=0.8，wmin=0.6，迭代次數(shù)為300，初始能量Ei0=0.5 J。

覆蓋模型為以“*”為傳感器節(jié)點(diǎn)位置，r為半徑的圓形區(qū)域，覆蓋率為圓形區(qū)域所占面積在矩形區(qū)域所占比例，初始時(shí)刻隨機(jī)分布的傳感器節(jié)點(diǎn)如圖1(a)所示。

在傳感器節(jié)點(diǎn)部署模型下，應(yīng)用IM-HPSO算法進(jìn)行MWSNs的傳感器節(jié)點(diǎn)部署，則最終節(jié)點(diǎn)部署如圖1(b)所示。

圖1 IM-HPSO算法節(jié)點(diǎn)布置

從圖1對(duì)比，可以看出:覆蓋率得到大幅地提升。為了評(píng)估文中算法的覆蓋效果和能耗，在相同情況下，將IM-HPSO算法與量子PSO (quantum PSO,QPSO) 算法和 PSO 算法進(jìn)行對(duì)比，結(jié)果如表1和圖2。

表1 覆蓋率和移動(dòng)能耗對(duì)比結(jié)果

從表1看出，IM-HPSO算法的移動(dòng)距離少于QPSO和PSO算法，從而IM-HPSO算法的移動(dòng)能耗少于QPSO算法，QPSO算法的移動(dòng)能耗少于PSO算法。

圖2 不同算法的覆蓋率對(duì)比

從圖2可以看出，初始時(shí)，覆蓋率提升較為明顯，隨著迭代次數(shù)的增多，覆蓋率提升較為緩慢，迭代200次后，逐漸趨于穩(wěn)定。初始時(shí)， QPSO算法覆蓋率提升幅度大于PSO算法，且收斂性能優(yōu)于PSO算法，而IM-HPSO算法覆蓋率提高幅度優(yōu)于QPSO算法，且收斂性能優(yōu)于QPSO算法。當(dāng)?shù)?00次后，IM-HPSO算法覆蓋率為90.83 %，QPSO算法覆蓋率為85.89 %，PSO算法覆蓋率為78.97 %。結(jié)果表明：在提高網(wǎng)絡(luò)覆蓋率及收斂性能方面，IM-HPSO算法均優(yōu)于QPSO算法和PSO算法。

綜上，IM-HPSO算法的覆蓋率和網(wǎng)絡(luò)能耗優(yōu)于其他2種算法。

在相同網(wǎng)絡(luò)環(huán)境，對(duì)比IM-HPSO算法的網(wǎng)絡(luò)生命周期與另外2種算法進(jìn)行了對(duì)比，結(jié)果如圖3所示。

圖3 存活節(jié)點(diǎn)數(shù)對(duì)比

圖3顯示了3種算法運(yùn)行200輪時(shí)的存活節(jié)點(diǎn)數(shù)對(duì)比。由于存活節(jié)點(diǎn)數(shù)受剩余能量的影響，說(shuō)明存活節(jié)點(diǎn)數(shù)越多，剩余能量越多，能量消耗越少，網(wǎng)絡(luò)生命周期越長(zhǎng)。從圖中可以看出：初始時(shí)，在相同輪數(shù)時(shí)，QPSO算法存活節(jié)點(diǎn)數(shù)多于PSO算法，PSO算法穩(wěn)定運(yùn)行80輪，存活節(jié)點(diǎn)數(shù)開(kāi)始衰減，而QPSO 算法穩(wěn)定運(yùn)行123輪，存活節(jié)點(diǎn)數(shù)才開(kāi)始衰減，說(shuō)明QPSO在相同模型下，算法性能優(yōu)于PSO算法，但隨著運(yùn)行輪數(shù)的增加，QPSO算法能量消耗較多，存活節(jié)點(diǎn)數(shù)較小，后期衰敗較快。而IM-HPSO能夠穩(wěn)定運(yùn)行131輪，網(wǎng)絡(luò)生命周期為182輪。結(jié)果表明，IM-HPSO算法在能耗，網(wǎng)絡(luò)覆蓋率，網(wǎng)絡(luò)生命周期方面均優(yōu)于QPSO算法和PSO算法。

4 結(jié) 論

通過(guò)減少移動(dòng)節(jié)點(diǎn)的移動(dòng)距離減少網(wǎng)絡(luò)能量消耗。仿真結(jié)果表明：IM-HPSO算法可達(dá)到較高的覆蓋率，較低的移動(dòng)消耗，并延長(zhǎng)網(wǎng)絡(luò)生命周期。未來(lái)將在此基礎(chǔ)上結(jié)合其他群智能算法進(jìn)行優(yōu)化，進(jìn)一步提高M(jìn)WSNs覆蓋率等。

參考文獻(xiàn):

[1] Abo-Zahhad M,Sabor N,Sasaki S,et al.A centralized immune-Voronoi deployment algorithm for coverage maximization and energy conservation in mobile wireless sensor networks[J].Information Fusion,2016,30(C):36-51.

[2] Mateska A,Gavrilovska L.WSNs coverage & connectivity improvement utilizing sensors mobility[C]∥Wireless Conference 2011—Sustainable Wireless Technologies,2011:1-8.

[3] Liu J Z,Wang B L,Ao J Y,et al.An immune-swarm intelligence based algorithm for deterministic coverage problems of wireless sensor networks[J].Journal of Central South University,2012,19(11):3154-3161.

[4] 周劍波,劉宏立,徐 琨.一種結(jié)合粒子群和虛擬力的動(dòng)態(tài)節(jié)點(diǎn)部署策略[J].計(jì)算機(jī)工程與應(yīng)用,2016,52(10):118-123.

[5] 袁 曦,張曦煌.基于改進(jìn)蝙蝠算法的無(wú)線傳感器網(wǎng)絡(luò)的移動(dòng)節(jié)點(diǎn)部署[J].傳感器與微系統(tǒng),2016,35(3):144-146.

[6] 王 霞,陳 潔.混合無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)覆蓋優(yōu)化[J].計(jì)算機(jī)仿真,2013,30(4):204-207.

[7] 陳樂(lè)瑞，潘秋萍，李甜甜.基于遺傳粒子群的微機(jī)運(yùn)動(dòng)網(wǎng)絡(luò)優(yōu)化研究[J].自動(dòng)化技術(shù)與應(yīng)用，2016,35(8)：13-17.

[8] 王建華,史明岳,王婷婷.基于量子粒子群算法的移動(dòng)節(jié)點(diǎn)覆蓋優(yōu)化[J].微電子學(xué)與計(jì)算機(jī),2012,29(6):96-99.

[9] 艾 兵,董明剛.基于高斯擾動(dòng)和自然選擇的改進(jìn)粒子群優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用,2016,36(3):687-691.

[10] 謝世龍，周玉國(guó)，劉 真.一種基于神經(jīng)網(wǎng)絡(luò)的粒子濾波算法設(shè)計(jì)[J].自動(dòng)化技術(shù)與應(yīng)用，2017,36(11)：1-4.

[11] 岳 翀,熊 芝,薛 彬.基于模擬退火—粒子群算法的wMPS布局優(yōu)化[J].光電工程,2016,43(7):67-73.

[12] 黃 炯,艾劍良,萬(wàn) 婧.基于模擬退火粒子群算法的飛機(jī)氣動(dòng)參數(shù)辨識(shí)[J].復(fù)旦學(xué)報(bào):自然科學(xué)版,2016,55(3):336-341.

[13] 丁婷婷，高美鳳.改進(jìn)粒子濾波的無(wú)線傳感器網(wǎng)絡(luò)目標(biāo)跟蹤算法[J].傳感器與微系統(tǒng)，2016,35(7)：140-142.

[14] Luo C Y,Chen M Y,Li H.Advances in swarm and computational intelligence[M].Berlin Haidelberg:Springer International Publishing,2015:479-486.

[15] Tian J,Gao M,Ge G.Wireless sensor networks node optimal coverage based on improved genetic algorithm and binary ant colony algorithm[J].Eurasip Journal on Wireless Communications & Networking,2016,2016(1):1-11.