基于改進粒子群算法的無線傳感器網絡覆蓋優化

梁俊卿

摘 要： 為了解決粒子群算法的無線傳感器網絡覆蓋方法存在的容易出現局部收斂的問題，提出基于改進粒子群的無線傳感器網絡覆蓋優化方法。分析基本粒子群算法進行無線傳感器網絡覆蓋優化的過程，找出其存在的局部收斂問題，通過采用擬萬有引力和庫侖力兩種擬物方案，在粒子速度進化過程中融入擬物力，對基本粒子群算法的速度修正過程實施優化，避免粒子群算法出現局部收斂問題，降低重復覆蓋率，完成無線傳感器網絡覆蓋優化。實驗結果表明，改進粒子群算法具有更快的收斂效率，對無線傳感網絡的覆蓋優化效果更好。

關鍵詞： 粒子群算法； 無線傳感器； 網絡覆蓋； 收斂效率

中圖分類號： TN711?34； TP212.9 文獻標識碼： A 文章編號： 1004?373X（2017）17?0032?04

Wireless sensor network coverage optimization based on

improved particle swarm optimization

LIANG Junqing

（Institute of Computer Engineering， Qingdao University of Technology， Qingdao 266033， China）

Abstract： Since the traditional wireless sensor network coverage methods are prone to produce local convergence， a method of wireless sensor network coverage optimization based on improved particle swarm optimization is proposed. The process of wireless sensor network coverage optimization based on particle swarm optimization is analyzed to find out the local convergence problem. The schemes of quasi universal gravitation and quasi Coulomb force are used to integrate into the quasi physical force in process of particle velocity evolutionary. The velocity correction process of basic particle swarm optimization algorithm is optimized to avoid the local convergence problem of particle swarm algorithm， reduce the coverage of duplication， and realize the wireless sensor network coverage optimization. The experimental results show that the improved particle swarm optimization algorithm has fast convergence efficiency， and perfect coverage optimization effect for wireless sensor networks.

Keywords： particle swarm optimization algorithm； wireless sensor； network coverage； convergence efficiency

0 引 言

隨著科學技術的高速發展，無線傳感器網絡在工業、農業以及軍事等領域具有重要的應用價值。無線網絡應用時的網絡覆蓋問題決定了網絡監測質量[1]。高效的無線傳感節點分布方案可增強無線傳感網絡的覆蓋率，提高傳感器網絡資源的利用率，最大化網絡使用周期。傳統無線傳感網絡節點分布方法部署了大量的靜態節點，這些節點無法解決地形環境以及部署方式的干擾，導致網絡通信出現沖突問題[2]，而部署移動傳感節點能夠解決網絡通信沖突問題。受到移動節點成本因素的干擾，應對移動節點位置實施優化，通過有限的節點實現最高的無線傳感網絡覆蓋率，成為相關學者分析的熱點問題。

當前基本粒子群算法的無線傳感器網絡覆蓋優化方法存在容易陷入局部收斂的問題，因此，提出基于改進粒子群算法的無線傳感器網絡覆蓋優化方法，實現傳感節點的有效部署，最大化傳感網絡的覆蓋率和使用率。

1 改進粒子群算法的無線傳感器網絡覆蓋優化

1.1 基本粒子群算法的無線傳感器網絡覆蓋優化

1.1.1 基本粒子群算法

粒子群算法是一種優化算法，其內各粒子同解區域的一個解對應，粒子按照同伴和自身的檢索經驗，對當前的位置和速度實施修正[3]。若粒子群中存在個粒子，粒子會按照式（1）對自身位置和速度實施修正：

（1）

式中：和分別用于描述第個粒子的位置和速度；用于描述粒子的過往最佳位置；用于描述全部粒子的過往最佳位置；以及取中的任意數；用于描述慣性權重，也就是學習因子，本文設置其值為1。

1.1.2 粒子編碼

進行粒子編碼是對粒子的位置和速度實施編碼，若無線傳感網絡內的各點都包括兩個位置坐標，將網絡覆蓋率當成優化目標[4]，則無線傳感網絡節點最佳分布位置的維數空間是將粒子編碼也看成是容量為的向量。向量內的各分量用于描述傳感器節點的或方向的位置。各粒子位置的編碼如下：endprint

（2）

各粒子速度的編碼為：

（3）

粒子群內的全部粒子的位置和速度編碼都一致，并獨立運算各粒子的位置和速度向量。

1.1.3 適應度函數

對無線傳感器網絡覆蓋實施優化，全面分析網絡覆蓋率和移動距離的網絡覆蓋優化目標函數，即適應度函數為：

（4）

式中：Cov用于描述覆蓋率；Dis用于描述傳感器節點移動距離；用于描述目標范圍中的傳感器節點數；用于描述目標范圍是的矩形區域邊長；和分別用于描述覆蓋率和移動距離占據的權重。

式（4）綜合分析了無線傳感網絡覆蓋區域以及傳感節點數量的變化情況。

1.1.4 算法流程

基本粒子群算法流程具體如下：

（1） 對算法參數和傳感器節點屬性進行初始化設置。

（2） 對粒子群實施初始化設置，在目標區域中，采用個隨機數組成個傳感器節點的初始位置基于該位置組成的向量對總體粒子群內全部粒子的位置向量實施初始化設置[5]，則粒子群內全部粒子的位置向量為。設置粒子初始速度是0，粒子群內全部粒子的速度向量為。

（3） 采用式（4）的適應度函數運算粒子的適應度值。

（4） 對粒子的速度和位置實施迭代調整，如果算法進行第次迭代，則全部粒子檢索的歷史最佳位置是用最佳位置替換全局最佳位置gbest。算法進行第次迭代時，采用位置和速度更新方差對全部粒子的位置和速度進行修正，并設置粒子的速度上下限分別是以及位置的上下限分別是posMax以及posMin。

（5） 循環迭代，分析是否符合終止規范要求。若符合，則算法結束，輸出全局最佳位置；否則，循環迭代，運行步驟（3）。

1.2 改進粒子群算法的無線傳感網絡覆蓋優化

上述分析的基本粒子群算法在迭代收斂過程中容易出現局部最佳解問題，為了實現無線傳感器網絡覆蓋的優化，本文融合擬物力算法以及粒子群算法提出擬物力導向粒子群算法的無線傳感器網絡覆蓋優化方法，其通過擬物力對粒子群算法的速度修正過程實施優化[6]，提高收斂效率，均衡傳感節點間的距離，降低重復覆蓋率。

1.2.1 擬物力算法原理

本文針對無線傳感器網絡區域覆蓋問題，提出擬萬有引力和庫侖力兩種擬物方案。

（1） 擬萬有引力模型。通過網格法將目標范圍均衡地分割成個像素，將各像素作為一個質點，構成個質點，將各傳感器節點當成感知半徑是的圓。若無線傳感網絡中沒有被覆蓋的質點對臨近的圓是有價值的，則基于萬有引力模型設置第個質點對第個圓的擬萬有引力函數為：

（5）

式中：用于描述質點到圓心的距離；用于描述圓的質量；用于描述沒有被覆蓋的質點對圓形成的引力；對引力的作用區域進行約束[7]。

（2） 構建庫侖力模型。各傳感器節點當成感知半徑為的圓間庫侖力，在質點沒有被完全覆蓋的情況下，不存在庫侖力，而當全部質點都被覆蓋的情況下，存在的庫侖力能夠確保圓中的傳感節點部署均衡[8]，降低重復覆蓋問題，獲取最佳的覆蓋結果。設置圓間相互排斥的庫侖力函數為：

（6）

式中：以及是圓形成的電量；用于描述兩個圓心間的距離，可將排斥力的作用區域限制在鄰居節點之間。

1.2.2 擬物力導向粒子群覆蓋優化方案

擬物力算法可對移動傳感節點的散布過程實施調控，通過擬萬有引力和庫侖力對傳感節點的距離實施有效調控，降低重復覆蓋率。

（1） 擬物力導向粒子群優化方案設計

融合擬物力算法以及粒子群算法提出擬物力導向粒子群優化方案，分析式（1）可得，粒子群算法的粒子速度進化同粒子最佳位置以及粒子群的最佳位置相關，而粒子的原始位置和速度是隨機產生的，若粒子數量較低，則優化效果較差，部分粒子會產生偏離最佳解的退化問題[9]。因此，為了提高粒子群算法的收斂效率，控制粒子向全局最佳解方向進化，擬物力導向粒子群優化方法在粒子速度進化過程中融入了擬物力，具體過程可描述為：

（7）

式中：是粒子的速度；是粒子的歷史最佳位置；是粒子自身加速度權重系數；為全局加速度權重系數；是慣性系數；和分別是擬萬有引力和庫侖力的加速因子；是擬萬有引力的價值力因子，其采用式（5）運算出個粒子內的個傳感節點對某個像素的萬有引力函數值，再采用式（8）運算個像素的萬有引力函數值和：

（8）

是庫侖力的價值力因子，其采用式（6）運算出各粒子內某個傳感節點對其他傳感節點的庫侖力函數值，再采用式（9）運算該節點對其他節點的庫侖力函數和：

（9）

（2） 擬物力導向粒子群算法的運行過程

在基本粒子群算法內融入擬萬有引力以及庫侖力，能夠降低無線傳感網絡的重復覆蓋問題，提高收斂效率，具體過程為：

① 初始化粒子種群數任意形成個原始解和個原始速度，運算各粒子的原始覆蓋率；

② 修正各粒子的速度和位置，運算各粒子新位置的覆蓋率；

③ 如果粒子覆蓋率高于歷史最佳值pbest，則將pbest設置成即刻的適應度；

④ 基于粒子的歷史最佳解pbest檢索全局最佳值gbest；

⑤ 分析周圍是否完全覆蓋，融入擬萬有引力以及庫侖力；

⑥ 循環運行步驟（2）～步驟（5），直至符合終止規范。

2 實驗結果與分析

2.1 覆蓋性能分析

為了檢測本文方法的覆蓋性能，在不同原始節點部署狀態下，分別進行10次獨立的優化實驗，本文方法和基本粒子群算法的平均覆蓋率、400次迭代平均耗時、平均網絡均勻度以及各節點的平均移動距離見表1。endprint

分析表1可得，本文方法的覆蓋率比基本粒子群算法提升了8%，并且平均網絡均衡度也較低，說明本文方法部署下的無線傳感網絡的節點分布和能耗更為均衡，并且各節點的平均移動距離降低了4.63 m，解決了節點移動產生的能耗問題。

2.2 覆蓋優化效率的分析

實驗設置某無線傳感器網絡的種群數量是13，傳感節點的傳感半徑是2.3 m，分別采用本文方法和基本粒子群算法對無線傳感器網絡實施覆蓋優化，優化后的傳感節點位置數據如圖1所示。

分析圖1可得，基本粒子群算法到達收斂的迭代次數為375次，而本文方法到達收斂的迭代次數為265次，收斂效率提升了34.6%，說明本文方法具有更快的收斂效率，使無線傳感器網絡覆蓋優化效率得到提高。

2.3 不同感知半徑下各方法的覆蓋性能

實驗檢測不同感知半徑下，本文方法和基本粒子群算法的覆蓋率以及迭代次數的變化情況見圖2。

分析圖2（a）能夠看出，本文方法的覆蓋率高于基本粒子群方法，當感知半徑低于2 m時，兩種方法的覆蓋率較為相近，當感知半徑高于5 m時，兩種方法都實現了完全覆蓋。分析圖2（b）可得，在相同感知半徑狀態下，本文方法的收斂次數低于基本粒子群算法，具有較強的尋優性能。綜合分析圖2中的結果可得，本文方法比基本粒子群算法的覆蓋率高，迭代次數低，主要是因為本文方法在基本粒子群算法的基礎上融入了擬物力算法，降低了重復覆蓋率，提升了覆蓋率和收斂率，具有更高的覆蓋優化性能。

3 結 論

為了解決基本粒子群算法在迭代收斂過程中出現的局部最佳解問題，本文提出改進粒子群的無線傳感器網絡覆蓋優化方法，該方法擁有較高的全局搜索性能，可更快地獲取全局最佳解，增強無線傳感器網絡的有效覆蓋率。

參考文獻

[1] 馮秀芳，呂淑芳.基于RSSI和分步粒子群算法的無線傳感器網絡定位算法[J].控制與決策，2014，29（11）：1966?1972.

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

[3] 丁旭，吳曉蓓，黃成.基于改進粒子群算法和特征點集的無線傳感器網絡覆蓋問題研究[J].電子學報，2016，44（4）：967?973.

[4] 謝佳華，劉軍.無線網絡通信覆蓋優化仿真研究[J].計算機仿真，2015，32（6）：271?275.

[5] 仲元昌，陳鋒，李發傳，等.大規模無線傳感器網絡覆蓋優化算法[J].傳感器與微系統，2014，33（11）：117?120.

[6] 陳麓屹，張翼，戴國勇.融合信任機制和蜜蜂交配優化算法的無線傳感器網絡能耗均衡分簇方法[J].科學技術與工程，2015，15（3）：105?110.

[7] 王康，王峰，蔣馥珍.基于分跳跳距和粒子群優化算法的DV?Hop定位算法改進[J].計算機測量與控制，2014，22（3）：810?812.

[8] 王芳芳.無線傳感器網絡中一種基于遺傳算法的路由算法研究[J].科技通報，2016，32（5）：82?85.

[9] 陳樹，錢成.一種多目標的覆蓋優化策略在WSNs中的應用[J].傳感器與微系統，2014，33（10）：151?154.endprint