基于改進(jìn)粒子群算法的無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化

梁俊卿

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

關(guān)鍵詞： 粒子群算法； 無線傳感器； 網(wǎng)絡(luò)覆蓋； 收斂效率

中圖分類號： TN711?34； TP212.9 文獻(xiàn)標(biāo)識碼： 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 引 言

隨著科學(xué)技術(shù)的高速發(fā)展，無線傳感器網(wǎng)絡(luò)在工業(yè)、農(nóng)業(yè)以及軍事等領(lǐng)域具有重要的應(yīng)用價(jià)值。無線網(wǎng)絡(luò)應(yīng)用時(shí)的網(wǎng)絡(luò)覆蓋問題決定了網(wǎng)絡(luò)監(jiān)測質(zhì)量[1]。高效的無線傳感節(jié)點(diǎn)分布方案可增強(qiáng)無線傳感網(wǎng)絡(luò)的覆蓋率，提高傳感器網(wǎng)絡(luò)資源的利用率，最大化網(wǎng)絡(luò)使用周期。傳統(tǒng)無線傳感網(wǎng)絡(luò)節(jié)點(diǎn)分布方法部署了大量的靜態(tài)節(jié)點(diǎn)，這些節(jié)點(diǎn)無法解決地形環(huán)境以及部署方式的干擾，導(dǎo)致網(wǎng)絡(luò)通信出現(xiàn)沖突問題[2]，而部署移動傳感節(jié)點(diǎn)能夠解決網(wǎng)絡(luò)通信沖突問題。受到移動節(jié)點(diǎn)成本因素的干擾，應(yīng)對移動節(jié)點(diǎn)位置實(shí)施優(yōu)化，通過有限的節(jié)點(diǎn)實(shí)現(xiàn)最高的無線傳感網(wǎng)絡(luò)覆蓋率，成為相關(guān)學(xué)者分析的熱點(diǎn)問題。

當(dāng)前基本粒子群算法的無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化方法存在容易陷入局部收斂的問題，因此，提出基于改進(jìn)粒子群算法的無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化方法，實(shí)現(xiàn)傳感節(jié)點(diǎn)的有效部署，最大化傳感網(wǎng)絡(luò)的覆蓋率和使用率。

1 改進(jìn)粒子群算法的無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化

1.1 基本粒子群算法的無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化

1.1.1 基本粒子群算法

粒子群算法是一種優(yōu)化算法，其內(nèi)各粒子同解區(qū)域的一個(gè)解對應(yīng)，粒子按照同伴和自身的檢索經(jīng)驗(yàn)，對當(dāng)前的位置和速度實(shí)施修正[3]。若粒子群中存在個(gè)粒子，粒子會按照式（1）對自身位置和速度實(shí)施修正：

（1）

式中：和分別用于描述第個(gè)粒子的位置和速度；用于描述粒子的過往最佳位置；用于描述全部粒子的過往最佳位置；以及取中的任意數(shù)；用于描述慣性權(quán)重，也就是學(xué)習(xí)因子，本文設(shè)置其值為1。

1.1.2 粒子編碼

進(jìn)行粒子編碼是對粒子的位置和速度實(shí)施編碼，若無線傳感網(wǎng)絡(luò)內(nèi)的各點(diǎn)都包括兩個(gè)位置坐標(biāo)，將網(wǎng)絡(luò)覆蓋率當(dāng)成優(yōu)化目標(biāo)[4]，則無線傳感網(wǎng)絡(luò)節(jié)點(diǎn)最佳分布位置的維數(shù)空間是將粒子編碼也看成是容量為的向量。向量內(nèi)的各分量用于描述傳感器節(jié)點(diǎn)的或方向的位置。各粒子位置的編碼如下：endprint

（2）

各粒子速度的編碼為：

（3）

粒子群內(nèi)的全部粒子的位置和速度編碼都一致，并獨(dú)立運(yùn)算各粒子的位置和速度向量。

1.1.3 適應(yīng)度函數(shù)

對無線傳感器網(wǎng)絡(luò)覆蓋實(shí)施優(yōu)化，全面分析網(wǎng)絡(luò)覆蓋率和移動距離的網(wǎng)絡(luò)覆蓋優(yōu)化目標(biāo)函數(shù)，即適應(yīng)度函數(shù)為：

（4）

式中：Cov用于描述覆蓋率；Dis用于描述傳感器節(jié)點(diǎn)移動距離；用于描述目標(biāo)范圍中的傳感器節(jié)點(diǎn)數(shù)；用于描述目標(biāo)范圍是的矩形區(qū)域邊長；和分別用于描述覆蓋率和移動距離占據(jù)的權(quán)重。

式（4）綜合分析了無線傳感網(wǎng)絡(luò)覆蓋區(qū)域以及傳感節(jié)點(diǎn)數(shù)量的變化情況。

1.1.4 算法流程

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

（1） 對算法參數(shù)和傳感器節(jié)點(diǎn)屬性進(jìn)行初始化設(shè)置。

（2） 對粒子群實(shí)施初始化設(shè)置，在目標(biāo)區(qū)域中，采用個(gè)隨機(jī)數(shù)組成個(gè)傳感器節(jié)點(diǎn)的初始位置基于該位置組成的向量對總體粒子群內(nèi)全部粒子的位置向量實(shí)施初始化設(shè)置[5]，則粒子群內(nèi)全部粒子的位置向量為。設(shè)置粒子初始速度是0，粒子群內(nèi)全部粒子的速度向量為。

（3） 采用式（4）的適應(yīng)度函數(shù)運(yùn)算粒子的適應(yīng)度值。

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

（5） 循環(huán)迭代，分析是否符合終止規(guī)范要求。若符合，則算法結(jié)束，輸出全局最佳位置；否則，循環(huán)迭代，運(yùn)行步驟（3）。

1.2 改進(jìn)粒子群算法的無線傳感網(wǎng)絡(luò)覆蓋優(yōu)化

上述分析的基本粒子群算法在迭代收斂過程中容易出現(xiàn)局部最佳解問題，為了實(shí)現(xiàn)無線傳感器網(wǎng)絡(luò)覆蓋的優(yōu)化，本文融合擬物力算法以及粒子群算法提出擬物力導(dǎo)向粒子群算法的無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化方法，其通過擬物力對粒子群算法的速度修正過程實(shí)施優(yōu)化[6]，提高收斂效率，均衡傳感節(jié)點(diǎn)間的距離，降低重復(fù)覆蓋率。

1.2.1 擬物力算法原理

本文針對無線傳感器網(wǎng)絡(luò)區(qū)域覆蓋問題，提出擬萬有引力和庫侖力兩種擬物方案。

（1） 擬萬有引力模型。通過網(wǎng)格法將目標(biāo)范圍均衡地分割成個(gè)像素，將各像素作為一個(gè)質(zhì)點(diǎn)，構(gòu)成個(gè)質(zhì)點(diǎn)，將各傳感器節(jié)點(diǎn)當(dāng)成感知半徑是的圓。若無線傳感網(wǎng)絡(luò)中沒有被覆蓋的質(zhì)點(diǎn)對臨近的圓是有價(jià)值的，則基于萬有引力模型設(shè)置第個(gè)質(zhì)點(diǎn)對第個(gè)圓的擬萬有引力函數(shù)為：

（5）

式中：用于描述質(zhì)點(diǎn)到圓心的距離；用于描述圓的質(zhì)量；用于描述沒有被覆蓋的質(zhì)點(diǎn)對圓形成的引力；對引力的作用區(qū)域進(jìn)行約束[7]。

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

（6）

式中：以及是圓形成的電量；用于描述兩個(gè)圓心間的距離，可將排斥力的作用區(qū)域限制在鄰居節(jié)點(diǎn)之間。

1.2.2 擬物力導(dǎo)向粒子群覆蓋優(yōu)化方案

擬物力算法可對移動傳感節(jié)點(diǎn)的散布過程實(shí)施調(diào)控，通過擬萬有引力和庫侖力對傳感節(jié)點(diǎn)的距離實(shí)施有效調(diào)控，降低重復(fù)覆蓋率。

（1） 擬物力導(dǎo)向粒子群優(yōu)化方案設(shè)計(jì)

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

（7）

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

（8）

是庫侖力的價(jià)值力因子，其采用式（6）運(yùn)算出各粒子內(nèi)某個(gè)傳感節(jié)點(diǎn)對其他傳感節(jié)點(diǎn)的庫侖力函數(shù)值，再采用式（9）運(yùn)算該節(jié)點(diǎn)對其他節(jié)點(diǎn)的庫侖力函數(shù)和：

（9）

（2） 擬物力導(dǎo)向粒子群算法的運(yùn)行過程

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

① 初始化粒子種群數(shù)任意形成個(gè)原始解和個(gè)原始速度，運(yùn)算各粒子的原始覆蓋率；

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

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

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

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

⑥ 循環(huán)運(yùn)行步驟（2）～步驟（5），直至符合終止規(guī)范。

2 實(shí)驗(yàn)結(jié)果與分析

2.1 覆蓋性能分析

為了檢測本文方法的覆蓋性能，在不同原始節(jié)點(diǎn)部署狀態(tài)下，分別進(jìn)行10次獨(dú)立的優(yōu)化實(shí)驗(yàn)，本文方法和基本粒子群算法的平均覆蓋率、400次迭代平均耗時(shí)、平均網(wǎng)絡(luò)均勻度以及各節(jié)點(diǎn)的平均移動距離見表1。endprint

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

2.2 覆蓋優(yōu)化效率的分析

實(shí)驗(yàn)設(shè)置某無線傳感器網(wǎng)絡(luò)的種群數(shù)量是13，傳感節(jié)點(diǎn)的傳感半徑是2.3 m，分別采用本文方法和基本粒子群算法對無線傳感器網(wǎng)絡(luò)實(shí)施覆蓋優(yōu)化，優(yōu)化后的傳感節(jié)點(diǎn)位置數(shù)據(jù)如圖1所示。

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

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

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

分析圖2（a）能夠看出，本文方法的覆蓋率高于基本粒子群方法，當(dāng)感知半徑低于2 m時(shí)，兩種方法的覆蓋率較為相近，當(dāng)感知半徑高于5 m時(shí)，兩種方法都實(shí)現(xiàn)了完全覆蓋。分析圖2（b）可得，在相同感知半徑狀態(tài)下，本文方法的收斂次數(shù)低于基本粒子群算法，具有較強(qiáng)的尋優(yōu)性能。綜合分析圖2中的結(jié)果可得，本文方法比基本粒子群算法的覆蓋率高，迭代次數(shù)低，主要是因?yàn)楸疚姆椒ㄔ诨玖Ｗ尤核惴ǖ幕A(chǔ)上融入了擬物力算法，降低了重復(fù)覆蓋率，提升了覆蓋率和收斂率，具有更高的覆蓋優(yōu)化性能。

3 結(jié) 論

為了解決基本粒子群算法在迭代收斂過程中出現(xiàn)的局部最佳解問題，本文提出改進(jìn)粒子群的無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化方法，該方法擁有較高的全局搜索性能，可更快地獲取全局最佳解，增強(qiáng)無線傳感器網(wǎng)絡(luò)的有效覆蓋率。

參考文獻(xiàn)

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

[2] 王偉，朱娟娟，萬家山，等.基于混沌量子粒子群算法的無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化[J].傳感技術(shù)學(xué)報(bào)，2016，29（2）：290?296.

[3] 丁旭，吳曉蓓，黃成.基于改進(jìn)粒子群算法和特征點(diǎn)集的無線傳感器網(wǎng)絡(luò)覆蓋問題研究[J].電子學(xué)報(bào)，2016，44（4）：967?973.

[4] 謝佳華，劉軍.無線網(wǎng)絡(luò)通信覆蓋優(yōu)化仿真研究[J].計(jì)算機(jī)仿真，2015，32（6）：271?275.

[5] 仲元昌，陳鋒，李發(fā)傳，等.大規(guī)模無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法[J].傳感器與微系統(tǒng)，2014，33（11）：117?120.

[6] 陳麓屹，張翼，戴國勇.融合信任機(jī)制和蜜蜂交配優(yōu)化算法的無線傳感器網(wǎng)絡(luò)能耗均衡分簇方法[J].科學(xué)技術(shù)與工程，2015，15（3）：105?110.

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

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

[9] 陳樹，錢成.一種多目標(biāo)的覆蓋優(yōu)化策略在WSNs中的應(yīng)用[J].傳感器與微系統(tǒng)，2014，33（10）：151?154.endprint