基于改進混合粒子群優化算法的移動節點部署研究*

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

0 引 言

覆蓋率是衡量無線傳感器網絡(wireless sensor networks,WSNs)[1]質量的重要指標。在WSNs中，數據采集節點分為靜態節點和移動節點。移動節點部署能夠在初始隨機部署后，改變網絡的拓撲結構，實現網絡自組織，提高網絡的覆蓋質量。

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

基于粒子群優化(particle swarm optimization,PSO)算法[6～10]的WSNs覆蓋應用研究較多。本文將模擬退火算法[11，12]和改進粒子群優化算法[13]相結合即改進混合粒子群優化 (improved hybrid PSO,IM-HPSO) 算法優化移動節點的部署。同時在建立傳感器節點部署模型時同時考慮了網絡覆蓋率和節點的移動能耗即多目標函數[14,15]，提高了網絡服務質量。

1 傳感器節點部署模型

移動傳感器節點感知模型采用概率感知優化模型。

定義移動節點部署區域為W×W的二維區域并將其網格化，假設在該區域隨機部署N個移動節點(N=n1,n2,…,ni,…,nN)，每個移動節點感知半徑為R，通信半徑為2R，以確保網絡的連通性。移動節點ni覆蓋二維區域的目標點Tj的概率如下

(1)

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

(2)

由于移動節點部署WSNs(mobile WSNs,MWSNs)由N個移動節點組成，則目標點Tj被所有移動節點覆蓋概率為

(3)

WSNs在二維平面區域Q的覆蓋率為

(4)

(5)

IM-HPSO算法通過重新調整位置來提高MWSNs的覆蓋率，假設節點移動單位距離所需能量相同，移動距離為節點從初始位置移動到目標位置之間的距離，則MWSNs中網絡能耗主要指所有移動節點的移動距離之和與單位距離消耗能量的乘積 ,即

(6)

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

在MWSNs節點部署模型中，設f為適應度函數，函數值設置為高覆蓋率和少的能量消耗，公式如下

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

(7)

式中w為無線傳感網覆蓋率和網絡能耗在該函數中所占比重。

2 基于IM-HPSO算法的移動節點部署

2.1 IM_HPSO算法

1)改進粒子群算法

自適應權重粒子群算法根據粒子位置來改變權重系數，避免粒子的局部最優問題，權重系數變化如下

(8)

式中w為變化的慣性權重；wmax為粒子慣性權重的最大值；wmin為粒子慣性權重的最小值；f為當前粒子的適應度函數值；fmin為種群的最小函數值；favg為種群的平均函數值。

在自適應權重PSO算法中，引入收縮因子φ

(9)

φ用于改變粒子的速度，調整粒子的位置，實現局部最優和全局最優之間的平衡，避免算法陷入早熟收斂，粒子的速度和位置更新公式為

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

(10)

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

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

(11)

式中vij(t+1)為第i個粒子在t次迭代后的速度；vij(t)為粒子當前的速度;c1，c2為學習因子，取2左右的隨機數;pbestij(t)為第i個粒子在第t次迭代時的個體極值;gbestij為第i個粒子在第t次迭代時的全局極值。

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

2)模擬退火算法

3)IM-HPSO算法

將SA算法引入改進PSO算法提出了IM-HPSO。當粒子群陷入局部極值時，該算法能夠根據Metropolis準則以一定的概率修改該極值，從而繼續搜索，跳出局部極值，尋找整體最優解。

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

(12)

式中f(pi)為當前粒子的最優目標函數值;f(g)為粒子群最優目標函數值。

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

xij(t))}

(13)

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

2.2 移動節點部署策略

策略如下：

1)根據式(1)～ 式(7)，在WSNs移動節點模型中定義適應度為網絡覆蓋率以及能量消耗的多目標函數。

2)確定種群數量M，隨機分布各個粒子群體。

3)通過適應度函數評價每個粒子的適應度值，確定粒子的個體最優值pbest，以及從所有個體最優中選擇全局最優值gbest。

4)確定初始溫度

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

(14)

5)根據式(12)確定當前溫度下各粒子的適應值。

6)從適應值中選擇全局最優值的替換值 ，根據式(8)～式(13)更新各粒子的位置，速度和權重。

7)計算各個粒子新的適應度，并與個體最優值比較，再與全局最優值比較，更新結果。

8)按照更新后的適應值大小來排序，適應值較好的粒子根據比例替換適應值較差的粒子，并記錄每個粒子的歷史個體最優值。

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

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

(15)

10)當迭代次數達到設定值或者連續若干解未被接受，輸出MWSNs節點部署最優位置，WSNs覆蓋率以及能量消耗;否則,返回步驟(4)。

3 仿真結果

在MATLAB R2014a仿真工具上進行實驗。設置待部署區域為40×40的網格點，初始時隨機部署40個移動節點，傳感器節點的參數設置如下：傳感半徑R=4，通信半徑2R=8，λ=1，rij=0.8，β=1，β′=0.5。

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

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

在傳感器節點部署模型下，應用IM-HPSO算法進行MWSNs的傳感器節點部署，則最終節點部署如圖1(b)所示。

圖1 IM-HPSO算法節點布置

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

表1 覆蓋率和移動能耗對比結果

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

圖2 不同算法的覆蓋率對比

從圖2可以看出，初始時，覆蓋率提升較為明顯，隨著迭代次數的增多，覆蓋率提升較為緩慢，迭代200次后，逐漸趨于穩定。初始時， QPSO算法覆蓋率提升幅度大于PSO算法，且收斂性能優于PSO算法，而IM-HPSO算法覆蓋率提高幅度優于QPSO算法，且收斂性能優于QPSO算法。當迭代300次后，IM-HPSO算法覆蓋率為90.83 %，QPSO算法覆蓋率為85.89 %，PSO算法覆蓋率為78.97 %。結果表明：在提高網絡覆蓋率及收斂性能方面，IM-HPSO算法均優于QPSO算法和PSO算法。

綜上，IM-HPSO算法的覆蓋率和網絡能耗優于其他2種算法。

在相同網絡環境，對比IM-HPSO算法的網絡生命周期與另外2種算法進行了對比，結果如圖3所示。

圖3 存活節點數對比

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

4 結 論

通過減少移動節點的移動距離減少網絡能量消耗。仿真結果表明：IM-HPSO算法可達到較高的覆蓋率，較低的移動消耗，并延長網絡生命周期。未來將在此基礎上結合其他群智能算法進行優化，進一步提高MWSNs覆蓋率等。

參考文獻:

[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] 周劍波,劉宏立,徐 琨.一種結合粒子群和虛擬力的動態節點部署策略[J].計算機工程與應用,2016,52(10):118-123.

[5] 袁 曦,張曦煌.基于改進蝙蝠算法的無線傳感器網絡的移動節點部署[J].傳感器與微系統,2016,35(3):144-146.

[6] 王 霞,陳 潔.混合無線傳感器網絡節點覆蓋優化[J].計算機仿真,2013,30(4):204-207.

[7] 陳樂瑞，潘秋萍，李甜甜.基于遺傳粒子群的微機運動網絡優化研究[J].自動化技術與應用，2016,35(8)：13-17.

[8] 王建華,史明岳,王婷婷.基于量子粒子群算法的移動節點覆蓋優化[J].微電子學與計算機,2012,29(6):96-99.

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

[10] 謝世龍，周玉國，劉 真.一種基于神經網絡的粒子濾波算法設計[J].自動化技術與應用，2017,36(11)：1-4.

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

[12] 黃 炯,艾劍良,萬 婧.基于模擬退火粒子群算法的飛機氣動參數辨識[J].復旦學報:自然科學版,2016,55(3):336-341.

[13] 丁婷婷，高美鳳.改進粒子濾波的無線傳感器網絡目標跟蹤算法[J].傳感器與微系統，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.