基于自適應(yīng)粒子群算法的WSN 覆蓋優(yōu)化

范賢志

（合肥學院先進制造工程學院，安徽 合肥 230000）

無線傳感器網(wǎng)絡(luò)（WSN）由分布式傳感器構(gòu)成，是一種自組織、多節(jié)點的無線網(wǎng)絡(luò)[1]。WSN 覆蓋優(yōu)化目標是實現(xiàn)區(qū)域內(nèi)無空洞覆蓋[2]。通常WSN 所處的監(jiān)測物理環(huán)境相對較差，難以借助人為方式進行確定性部署[3]。動態(tài)節(jié)點能夠適應(yīng)復雜多變的物理環(huán)境，但其部署不確定性較強，難以均勻、全面的覆蓋監(jiān)測區(qū)域，覆蓋質(zhì)量通常情況下低于預期。采用粒子群算法（PSO）能夠顯著提升動態(tài)節(jié)點覆蓋率，但覆蓋重疊、局部最優(yōu)等現(xiàn)象依然存在。目前國內(nèi)眾多學者研究PSO 的改進方法，文獻[4]在基本PSO 的基礎(chǔ)上引入模擬退火方法，替換掉適應(yīng)性不強的粒子，克服了基本PSO 易陷入局部最優(yōu)的劣勢，同時更新權(quán)重因子，加快收斂速度。文獻[5]借助虛擬勢場法的I-PSO，在WSN 節(jié)點之間構(gòu)建虛擬勢場，降低引力、斥力的波蕩，加快粒子收斂速度。文獻[6]將WSN 劃分為通信范圍大小不等的圓形區(qū)域，建立能耗模型，通過免疫算法和模擬退火粒子群算法相結(jié)合求解優(yōu)化模型，獲取能耗最小的匯聚節(jié)點移動路徑。

1 WSN 覆蓋數(shù)學模型

公式（3）為WSN 覆蓋優(yōu)化模型目標函數(shù)。

2 基本粒子群算法

PSO 是一種智能優(yōu)化算法，最早僅作為單目標優(yōu)化算法而被應(yīng)用，PSO 不同于生物遺傳計算中變異、雜交等因子，而是模擬蟻群、蜂群、魚群等生物群體行為完成探索[8]。PSO 本身具備設(shè)置參數(shù)少、使用便捷、并行性號等優(yōu)勢。但由于基本PSO 無法適應(yīng)多目標優(yōu)化需求，所以需要不斷對其進行拓展[9]。和多數(shù)進化算法相類似，PSO 也具備“進化”、“群體”的概念，借助各個粒子間的競爭與合作完成搜索區(qū)域最優(yōu)解的實現(xiàn)。改進后的PSO 算法隱含并行性，一次進化能夠求得多組解，十分匹配多目標優(yōu)化問題的求解，已經(jīng)廣泛應(yīng)用在工業(yè)生產(chǎn)、能源勘測、電力運輸?shù)阮I(lǐng)域。

PSO 主要借助兩個迭代公式完成較優(yōu)解的搜尋，公式（4）和公式（5）分別進行計算：

總粒子數(shù)目為N，t 代表PSO 迭代次數(shù)，其中t≤T；i表示當前粒子Ni（i=1，2，…，N），n 表示當前維度；vNin表示粒子在當前維度的速度；e1、e2分別為認知、社交因子；Drand1、Drand2是介于0 到1 之間的隨機數(shù)；Popti為粒子自身計算所得最優(yōu)解；Gopti 為粒子群計算所得最優(yōu)解；ω 表示權(quán)重因子，正是由于該因子的存在，才能有效均衡PSO全局、局部搜索能力；ω 數(shù)值越大，PSO 局部搜索能力越弱；ω 數(shù)值越小，PSO 全局搜索能力越弱。

PSO 具體算法流程（圖1）為：

圖1 粒子群算法流程圖

（1）初始化粒子群，設(shè)置參數(shù)有：粒子數(shù)量Ni（i=1,2,…，N）、迭代次數(shù)t、權(quán)重因子ω、認知因子e1、社交因子e2及速度上下限值[vmin，vmax]；

（2）按照函數(shù)或公式對適應(yīng)度值進行計算；

（3）計算所得的個體最優(yōu)解Popti，對比Ni（i=1，2，…，N）個粒子對應(yīng)的個體最優(yōu)解，直至搜尋得到全局最優(yōu)解Gopti；

（4）按照公式（4）與公式（5）迭代所得當前粒子的速度及坐標，搜尋更優(yōu)的解，粒子速度不能超過限制，避免超出尋優(yōu)范圍。

（5）是否已經(jīng)為最大迭代次數(shù)或理論最優(yōu)值，若不是則返回步驟2，否則輸出結(jié)果同時結(jié)束運行。

3 自適應(yīng)粒子群優(yōu)化算法（PSO-H）

3.1 進化因子與匯聚因子

規(guī)定第t 次迭代的PSO 全局最優(yōu)值尋優(yōu)度為：

3.2 權(quán)重因子的自適應(yīng)調(diào)整

前文提到過，權(quán)重因子的大小直接決定了PSO 全局、局部尋優(yōu)能力的強弱。當ω 數(shù)值較大時，粒子全局尋優(yōu)的能力較強；當ω 數(shù)值較小時，粒子局部尋優(yōu)的能力較強。若進化因子很大，PSO 整體進化程度不強，需要降低ω 以提升粒子局部尋優(yōu)能力；若進化因子很小，PSO 整體進化程度較強，需要提升ω 以提升粒子全局尋優(yōu)能力；所以按照粒子當前的進化狀態(tài)對權(quán)重因子進行調(diào)解能夠保證粒子更快達到收斂狀態(tài)。本文定義進行第t 次迭代后粒子i 的自適應(yīng)ωti可以表達為：

其中，ω 為權(quán)重因子，a1、a2分別代表進化因子、聚合因子調(diào)整系數(shù)，同時a1∈（0，+∞）、a2∈（-∞，ω），且a1+a2=1。

3.3 選取最優(yōu)粒子

PSO 在對多目標優(yōu)化過程中，選取最優(yōu)粒子直接影響到最終的尋優(yōu)結(jié)果。本文選取粒子建立在解的分配、隨機原則之上，個體最優(yōu)粒子為進化粒子所支配，當前粒子個體最優(yōu)粒子為進化后的解。若進化后的解和當前個體最優(yōu)粒子相互不支配，隨機更新個體最優(yōu)粒子，不然將維持個體最優(yōu)粒子的數(shù)量為恒值，以此確保解的非支配性、精確性。多目標粒子群的尋優(yōu)過程是一個逐漸迭代的過程，保證其逐漸逼近真實值前沿的現(xiàn)象。相對于整個粒子群，其得到的非支配解組成的解集對于目前或從前的全部種群均為非支配，借助層次分析法能夠較為全面的評判數(shù)個非支配目標。而相對于全局最優(yōu)粒子，充分借助進化過程獲取進化信息，選取綜合效用較低的粒子當做全局最優(yōu)粒子，以此確保選取全局最優(yōu)粒子的有效性、準確性。

3.4 外部歸檔集的更新和維護策略

恰當?shù)母峦獠繗w檔集合、維護方式能夠確保PSO進化過程中具備良好的多樣性、分布性，確保了算法的準確性與可行性。筆者根據(jù)擁擠度的相關(guān)排序策略完成外部歸檔集完成更新和完善，定義表示了解的具體分布，擁擠度值越大表示解的分布性越完善，反之表示其分布性越差。所以在對外部歸檔集展開修復、更新的過程中，對于擁擠度較大的情況能夠予以保留，同時刪除那些擁擠度較小的狀況，確保其節(jié)點分布性、全面性，具體的擁擠度計算過程為：

（1）目前外部歸檔集中擁擠度初始化值設(shè)為0，解集大小定義為Ni（i=1，2，…，N），當前目標為N1，總目標數(shù)為M；

（2）設(shè)置N1、NN粒子的擁擠度無窮大，對j=1 目標展開降序排列；

（3）除N1外，其余粒子根據(jù)公式（14）對擁擠度距離進行計算：

（4）判斷粒子是否大于N=1，若不是，則跳回執(zhí)行步驟3；若是，則繼續(xù)執(zhí)行步驟5；

（5）令i=i+1，判斷當前粒子是否大于N，若不是，則跳回執(zhí)行步驟2；若是，則程序終止。

4 仿真結(jié)果驗證

本文用MATLAB 作為仿真驗證工具，對本文自適應(yīng)粒子群算法（PSO-H）進行仿真驗證，對其性能分別和PSO、蟻群算法（ACO）進行對比。為了保證測試的精準性，能夠充分體現(xiàn)PSO-H 算法優(yōu)勢，同時確保各個算法實驗參數(shù)一致性。在進行算法覆蓋范圍的仿真、比較過程中，取算法運行10 次的平均值來作為最終體現(xiàn)其覆蓋性能的依據(jù)，具體仿真參數(shù)見表1。

表1 仿真參數(shù)

為了驗證自適應(yīng)粒子群效果，若在同構(gòu)網(wǎng)絡(luò)中WSN覆蓋半徑為5 米，仿真結(jié)果如圖2 至圖5 所示。圖2 為WSN 初始節(jié)點分布圖；圖3 為PSO 仿真節(jié)點覆蓋圖；圖4 為ACO 仿真節(jié)點覆蓋圖；圖5 為PSO-H 仿真節(jié)點覆蓋圖。圖中矩形區(qū)域表示W(wǎng)SN 待監(jiān)測區(qū)域，圓形區(qū)域代表WSN 節(jié)點覆蓋范圍。如圖，在監(jiān)測區(qū)域隨機散落WSN節(jié)點，在基本參數(shù)完全一致的情況下，分別采用PSO、ACO 和PSO-H 對節(jié)點覆蓋進行優(yōu)化。通過對比4 張節(jié)點覆蓋圖的變化進行分析，PSO、ACO 較初始節(jié)點分布在監(jiān)測范圍內(nèi)取得了一定改善，但是監(jiān)測區(qū)域仍然存在大量的覆蓋重疊和空洞現(xiàn)象，在經(jīng)過自適應(yīng)粒子群算法進行優(yōu)化后，節(jié)點分布更加均勻，重疊區(qū)域、空洞現(xiàn)象大幅度降低。

圖2 WSN 初始節(jié)點分布

圖3 基本PSO 節(jié)點覆蓋圖

圖4 基本ACO 節(jié)點覆蓋圖

圖5 PSO-H 節(jié)點覆蓋圖

PSO 在算法運行85 次迭代后趨于收斂，ACO 在算法運行90 次迭代后趨于收斂，PSO 算法覆蓋率59.7%，無效覆蓋率為34.2%；ACO 算法覆蓋率63.4%，無效覆蓋率為31.7%。

仿真結(jié)果顯示，粒子數(shù)量、迭代次數(shù)完全一致的情況下，PSO-H 相較于基本粒子群算法和蟻群算法，對覆蓋區(qū)域面積有著更大、覆蓋效果更優(yōu)的優(yōu)勢。

5 結(jié)論

為了確保WSN 部署的有效性，增強WSN 在相同節(jié)點下的覆蓋質(zhì)量。本文研究分析，在基本粒子群中引入進化因子、匯聚因子，同時自適應(yīng)調(diào)整權(quán)重因子，及時更新粒子選取、外部歸檔集更新及維護策略，增強算法尋找最優(yōu)解的能力。同時經(jīng)過仿真驗證，分別和PSO、ACO算法進行比較，從覆蓋性能、無效覆蓋率進行分析。PSO-H 收斂速度更快、覆蓋率更高，極大的避免了算法早熟陷入局部最優(yōu)的情況，增強了WSN 節(jié)點部署能力。