粒子群智能優化算法在無線傳感器網絡覆蓋中的應用

甘娜

摘要：針對無線傳感器網絡覆蓋的問題，提出一種求解無線傳感器網絡覆蓋問題的粒子群智能優化算法。該算法在粒子群算法的基礎上，對PSO算法適應度函數加入選擇算子的關聯。通過無線傳感器網絡覆蓋的仿真，實驗結果表明，該優化算法既克服了PSO算法陷入局部最優的不足，又提升了收斂精度。在提高傳感器節點覆蓋率、網絡負載均衡等方面有較好的效果。

關鍵詞：無線傳感器;網絡覆蓋;覆蓋度;PSO算法

中圖分類號：TP393? ? ? 文獻標識碼：A

文章編號：1009-3044（2022）21-0028-02

開放科學（資源服務）標識碼（OSID）：

無線傳感器網絡覆蓋是根據被監測目標或區域的分布情況，無線傳感器節點間相互通信，采集和處理覆蓋區域中監測對象的信息，并發送給監測者[1]。網絡覆蓋優化目標是要保證目標區域盡可能被網絡內的節點覆蓋[2]。

粒子群算法（PSO）在求解無線傳感器網絡覆蓋問題中很難得到最優值，針對以上問題，本文在PSO算法的基礎上，適應度函數中加入選擇算子的關聯，提出粒子群智能優化算法，求解無線傳感器網絡覆蓋問題中傳感器節點覆蓋度、負載均衡等性能指標。仿真結果表明，該算法克服了PSO算法收斂精度較低、陷入局部極值的不足，證明了粒子群智能優化算法解決無線傳感器網絡覆蓋問題的有效性。

1 無線傳感器網絡覆蓋模型

1.1無線傳感器網絡覆蓋模型描述

定義一：感知模型。假設傳感器節點[Si0

傳感器節點[Si]感知范圍：

[RSi=x-xi2+y-yi2]? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （1）

其中[RSi≤ri]。

定義二：鄰居節點。傳感器節點[Si]的通信范圍是以[rj]為通信半徑的圓。當兩個傳感器節點的距離小于或等于節點的[rj]時，這兩個節點互為鄰居節點。

傳感器節點[Si]的鄰居節點為：

[NSi=xi-xj2+yi-yj2]? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（2）

其中[RSi≤rj]。

定義三：覆蓋率。

網絡監測區域覆蓋率：

[Npk=1n1≤i≤n1-1≤i≤n1-xi-xj2+yi-yj2]? ? ? （3）

1.2 無線傳感器網絡覆蓋目標約束函數

1.2.1 覆蓋度目標約束函數

當傳感器節點正確地覆蓋監測區域，網絡才能夠順利獲取監測的數據，完成監測任務[3]。覆蓋率[Np]為監測區域內所有節點覆蓋的面積與監測區域面積之比，覆蓋率優化問題的目標函數的定義如下：

[Np=Npkm×n]? ? ? ? ? ? ? ? ? ? ? ? ? （4）

1.2.2網絡性能分析目標約束函數

負載均衡關系到是否可以合理分配傳感器節點源，提升網絡的監測能力和質量[4]，提升傳感器節點的利用率。因此，負載均衡也是無線傳感器網絡覆蓋中重要的優化目標。優化需求可以轉化為目標約束函數，如下：

[factor=1-Si-averageSilastSi+averageSilast]? ? ? ? ? ? ? ? ? ? ? ? （5）

其中，[averageSilast]表示傳感器節點[Si]在上一次迭代中的平均執行時間。

傳感器節點的負載均衡因子factor越高，則傳感器節點的綜合能力越強。

負載均衡目標函數如下：

[load_balance=n/i=1mj=1nSim]? ? ? ? ? ? ? ? ? ? ? ? ? ?（6）

其中，[i=1nj=1mSi]表示完成任務集所需的執行時間。由式（6）可知，[load_balance]的值越大，則傳感器節點利用率越高，負載越均勻。

2? 粒子群智能優化算法

2.1標準粒子群算法

假設搜索空間為[d]維，粒子總數為[n]，粒子[i]在時刻[t（t>0）]在搜索空間中所處的位置為[Xidt]，粒子在搜索空間中運動速度為[Vidt]，代表飛行的方向和速度[5-6]。在搜索過程中，粒子[i]（[1≤i≤n]）按公式（7）（8）來更新其速度和位置：

[Xidt=Xidt+Vidt]? ? ? ? ? ? ? ? ? ? （8）

其中[C1]、[C2]為粒子的學習因子，表示粒子對個體經驗與群體經驗的依賴程度，[w]是慣性權重，[t]為迭代次數，[r1]、[r2]為均勻分布在區間[0，1]上的隨機數。

飛行歷史中粒子的個體最優位置為[Pidt]，整個種群中所找到的全局最優位置[Pgdt]為所有粒子的[Pidt]中的極值，通過公式（9）（10）更新個體最優[Pidt]和全局最優[Pgdt]，向最優位置搜索移動。

[Pgdt=argminPidtfPidt]? ? ? ? ? ? ? ? ? （10）

2.2粒子群智能優化算法

為了克服PSO算法求解無線傳感器網絡覆蓋問題，陷入局部極值及收斂精度較低等缺點[7-8]，本文設計了一種粒子群智能優化算法，對PSO算法適應度函數加入選擇算子的關聯，以提升算法的收斂精度，克服PSO算法易陷入局部最優的不足。算法改進和優化主要體現在兩個方面：

第一，為避免過早陷入局部最優的問題，采用實數編碼的方式，產生一群更適應問題環境的種群;

第二，為避免收斂精度較低的問題，對適應度函數中引入選擇算子，選擇適應度值較好的粒子，進行更精細的局部搜索，獲取問題的最優解。

通過改進后的公式（11）選擇適應度值最優的粒子：

式中[Pgdt]為下一代種群的個體，[Vgdt]是目前為止最優個體，[Ogdt-1]是目前為止適應值較好的個體。

3 算法流程

Step1：編碼。優化數值，產生一群更適應問題環境的種群。

實數編碼方式如下：

[ρ=12nt=1n2tbi]? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（12）

其中[ρ]為編碼實數，[n]為二進制編碼位數，[bi]為第[i]位的二進制值。

Step2：產生初始種群。設置搜索空間為[D]維，粒子的數量為[M]，設置最大迭代次數，搜索最優解;其中第[i]個粒子位置[χ]，第[i]個粒子的飛行速度[υ]，獲取學習因子[c1]，[c2]，[c3]和慣性權重[ω];

Step3：對粒子的優化問題進行求解。初始化粒子群，粒子數量變量取值范圍內隨機初始化粒子的速度和初始位置，根據粒子速度和位置函數（7）（8）算出粒子所經歷的最好位置;

Step4：評價粒子群中每個粒子的適應度值，找出各個粒子的適應度最佳值和群體適應度最佳值。根據覆蓋率適應度函數（11）算出粒子的適應度最佳值，更新各個粒子的速度與位置，算出粒子各自的適應度值;繼續下一次迭代，而適應度值低的粒子被舍棄;

Step5：根據問題的目標函數更新粒子適應度值，更新個體最優位置和領域內的最優位置;

Step6：將種群最優粒子組成一個群體，進入下一次迭代，更新局部最優解和全局最優解;

Step7：將粒子群中最優粒子組成一個群體，判斷是否最大迭代次數？條件為真，則輸出最優值，算法結束。條件為假，則轉到Step 4，進行下一次迭代。

4? 數值仿真與性能分析

本文將PSO算法與粒子群優化算法在無線傳感器網絡覆蓋中的應用進行仿真實驗結果對比。實驗使用式（4）和式（6）作為算法中所需要評價的目標函數，通過Matlab仿真平臺來模擬無線傳感器網絡覆蓋過程，評價傳感器節點覆蓋度、負載均衡程度等指標。

本實驗假設監測區域[30×30m]、傳感器節點數目為40的情況下，進行無線傳感器網絡覆蓋優化。粒子群優化算法參數設置如下：設定粒子群的初始規模為250，主群最小規模限制為50，粒子維度5，學習因子0.5～2.5，慣性權重0.4～1.0，最大迭代次數200。

無線傳感器網絡覆蓋優化方案中，在不同傳感器節點數目的情況下，從圖1可以看出，在傳感器節點覆蓋度方面，粒子群智能算法優于PSO算法。

從圖2可以分析出，粒子群智能算法傳感器節點的負載均衡程度高于PSO算法。該算法克服了陷入局部最優解，具有較好的全局搜索能力。

5? 結論

本文將粒子群智能算法應用到無線傳感器網絡覆蓋優化問題中，設計了一種粒子群智能優化算法，對PSO算法適應度函數加入選擇算子的關聯，利用感知模型，以區域覆蓋率和負載均衡程度為目標函數，算法收斂精度高，克服PSO算法易陷入局部最優的不足，提高傳感器網絡覆蓋的質量和效果，優化無線傳感器網絡性能。

參考文獻：

[1]范興剛，楊靜靜，王恒.一種無線傳感器網絡的概率覆蓋增強算法[J].軟件學報，2016，27（2）：418-431.

[2] 周杰.基于進化算法的大規模無線傳感器網絡覆蓋關鍵技術研究[D].北京：北京郵電大學，2015.

[3] 神顯豪，李軍，奈何.感知受限的移動傳感器節點掃描覆蓋優化算法[J].計算機應用，2017，37（1）：60-64，102.

[4] 王偉，朱娟娟，萬家山，等.基于混沌量子粒子群算法的無線傳感器網絡覆蓋優化[J].傳感技術學報，2016，29（2）：290-296.

[5] 馬發民，張林，王錦彪.粒子群算法的改進及其在優化函數中的應用[J].計算機與數字工程，2017，45（7）：1252-1255，1293.

[6] 林詩潔，董晨，陳明志，等.新型群智能優化算法綜述[J].計算機工程與應用，2018，54（12）：1-9.

[7] 吳定會，高聰，紀志成.混合粒子群算法在微電網經濟優化運行的應用[J].控制理論與應用，2018，35（4）：457-467.

[8] Arora S，Singh H，Sharma M，et al.A new hybrid algorithm based on grey wolf optimization and crow search algorithm for unconstrained function optimization and feature selection[J].IEEE Access，2019，7：26343-26361.

【通聯編輯：唐一東】