改進自適應粒子群算法在WSN覆蓋優(yōu)化中的應用*

吳意樂，何　慶，徐同偉

（貴州大學大數據與信息工程學院，貴陽550025）

改進自適應粒子群算法在WSN覆蓋優(yōu)化中的應用*

吳意樂，何慶*，徐同偉

（貴州大學大數據與信息工程學院，貴陽550025）

針對無線傳感器網絡（WSN）節(jié)點覆蓋不均勻導致覆蓋率低下的問題，提出了一種基于改進自適應粒子群優(yōu)化算法的覆蓋優(yōu)化方法。首先，建立WSN覆蓋優(yōu)化的數學模型；然后將進化因子和聚合因子引入粒子群優(yōu)化（PSO）算法中的慣性權重系數，使改進算法具有很強的自適應能力；接著在算法迭代過程中引入碰撞回彈策略保證粒子群的多樣性，克服改進粒子群優(yōu)化算法在優(yōu)化后期容易陷入局部最優(yōu)的弱點。實驗表明，本文算法對WSN優(yōu)化后的網絡覆蓋率均比其它文獻算法提高了2%～6%，且傳感器節(jié)點分布更加均勻。因此它能有效提高無線傳感器網絡的性能，是一種應用性較強的WSN覆蓋優(yōu)化算法。

無線傳感器網絡；覆蓋優(yōu)化；改進自適應粒子群算法；慣性權重系數；碰撞回彈策略

EEACC:6150P；7230doi:10.3969/j.issn.1004-1699.2016.04.016

隨著計算機網絡技術的迅速發(fā)展，無線傳感器網絡（WSN）應運而生。無線傳感器網絡由多個功能相同或不同的終端傳感器節(jié)點、路由器和協(xié)調器通過自建網絡互連的方式組成，它們通過無線通信的方式完成目標監(jiān)測和信息交互。

目前，WSN網絡的節(jié)點部署方式可以分為確定性節(jié)點部署和自組織節(jié)點部署［1］，由于在實際應用中，確定性部署方式存在局限性，自組織節(jié)點部署方式得到了廣泛的應用。對一個WSN網絡來說，如果能及時檢測網絡的覆蓋率并做有效的調整，能夠提高網絡中數據的傳輸質量，減少資源浪費，延長網絡生命周期［2］。

近年來，許多國內外學者對WSN網絡的覆蓋優(yōu)化策略進行了大量的研究和改進:文獻［3］設計了基于共軛梯度法的改進人工螢火蟲算法，對WSN網絡節(jié)點進行優(yōu)化后，節(jié)點分布均勻，覆蓋率較高，但是邊界盲區(qū)較多；文獻［4］提出了基于分群和視野動態(tài)調整的改進魚群算法指導WSN網絡傳感器節(jié)點的部署，它能使節(jié)點較均勻地分布于整個監(jiān)測區(qū)域，相比基本人工魚群算法的優(yōu)化結果，覆蓋率提高了17.4%；文獻［5］在視野自適應變化的基礎上將變異因子引入適應度差的個體中，提出了一種改進人工魚群算法，在WSN網絡覆蓋優(yōu)化應用中取得了不錯的效果，提高了網絡的覆蓋率，然而節(jié)點覆蓋冗余度較高；文獻［6］提出了一種人工魚群算法與模式搜索法相結合的混合算法，優(yōu)化后節(jié)點覆蓋均勻，但存在許多較大盲區(qū)；文獻［7］通過引入混沌初始化、自適應步長以及視野的機制對人工魚群算法算法做相應改進，提高了優(yōu)化穩(wěn)定性，獲得了較高的網絡覆蓋率，但是邊界存在較多盲區(qū)，中心冗余度較高；文獻［8］提出了一種基于劃分搜索空間的粒子群優(yōu)化算法，算法全局收斂能力較強，能夠快速找到覆蓋率較高的WSN網絡節(jié)點分布，然而算法優(yōu)化后期局部搜索能力較弱；文獻［9］則采用混沌逃逸粒子群優(yōu)化算法對WSN網絡覆蓋率進行優(yōu)化，效率較高，收斂速度快，但覆蓋率較低；文獻［10］設計了一種基于逐維判斷PSO算法值的WSN網絡覆蓋優(yōu)化策略，優(yōu)化效果較理想。

然而，這些WSN網絡覆蓋優(yōu)化算法都有一些不足之處，比如改進的人工魚群算法和螢火蟲算法的收斂速度緩慢，雖然能得到較高的WSN網絡覆蓋率，但運行時間較長，而改進的粒子群算法雖然收斂速度快，但是穩(wěn)定性較低，局部搜索能力較差，優(yōu)化后WSN網絡覆蓋率不理想。

針對以上算法的不足以及WSN網絡覆蓋優(yōu)化目標，本文設計了基于碰撞回彈策略的一種慣性因子動態(tài)變化的自適應粒子群優(yōu)化算法并應用于WSN網絡的覆蓋優(yōu)化當中，最后通過實驗結果驗證了本文算法的優(yōu)越性。

1　WSN覆蓋模型

1.1問題分析

①由于WSN網絡中每個傳感器節(jié)點的覆蓋范圍都是以自身為中心固定半徑的圓內，所有傳感器節(jié)點對監(jiān)測區(qū)域的總覆蓋率難以用公式求解，所以，為了簡化區(qū)域內的覆蓋問題，被測區(qū)域可以離散化為m×n個像素點，假設有x個像素點被WSN網絡覆蓋，則覆蓋率為x/（m×n）。

②被測區(qū)域內WSN網絡所有傳感器節(jié)點具有相同的感知半徑和通信半徑，且在通信半徑大于等于兩倍的感知半徑時，假如WSN網絡能夠實現對監(jiān)測區(qū)域的感知范圍全覆蓋，則所有傳感器節(jié)點必然聯(lián)通［11］。

1.2覆蓋模型描述

將被測區(qū)域離散化為m×n個像素點，WSN網絡中有N個傳感器節(jié)點，所有節(jié)點感知（覆蓋）半徑均為r。傳感器節(jié)點集合為G=｛g1，g2，…，gN｝，其中，第i個傳感器節(jié)點為gi（i=1，2，…，N），它的坐標為（xi，yi）。設像素點H的坐標為（xH，yH），則該像素點到第i個傳感器節(jié)點的距離為。傳感器感知模型這里使用布爾（0-1）感知模型，所以像素點H處被傳感器節(jié)點i感知的概率為［12］:

一般情況下，一個傳感器節(jié)點可以被多個傳感器節(jié)點同時感知，那么像素點H處的傳感器節(jié)點被WSN網絡節(jié)點集合G感知的聯(lián)合概率為:

根據1.1節(jié)中分析的覆蓋率算法，節(jié)點集合G對監(jiān)測區(qū)域的覆蓋率為:

式（3）就是無線傳感器網絡覆蓋優(yōu)化模型的目標函數。

2　粒子群優(yōu)化（PSO）算法簡介

粒子群優(yōu)化（PSO）算法是一種新的全局優(yōu)化智能算法，它通過個體之間的協(xié)作和信息共享來實現對解空間的全局搜索［13］。PSO算法的優(yōu)勢在于參數少，能夠簡單容易的實現許多優(yōu)化問題，目前已經被廣泛應用與各種應用領域當中［14］。

PSO算法的數學描述為:假設粒子群中總共有m個粒子，表示為:X=（x1，x2，…，xm）T；粒子搜索空間為n維，于是第i個粒子可表示為:xi=（xi1，xi2，…，xin）T，（i=1，2，…，m），同時，它以vi=（vi1，vi2，…，vin）T的速度飛行，它代表粒子i每次迭代的移動位移。算法優(yōu)化過程中有兩個最優(yōu)解，一個是該粒子本身在迭代過程中的最優(yōu)解，即局部最優(yōu)解locbesti=（xli1，xli2，…，xlin）T，另一個是所有粒子在迭代過程中產生的最優(yōu)解，即全局最優(yōu)解globest=（xg1，xg2，…xgn）T。粒子每次迭代的速度vi通過locbesti和globest進行動態(tài)更新。第k+1次迭代的粒子i第d維的速度和位置更新的公式為［15］:

其中，wk為第k次迭代的慣性權重系數，當wk較大，算法有較強的全局搜索能力，當wk較小，算法有良好的局部搜索能力，式（6）說明算法在初期具有很強的全局搜索能力，而在后期具有不錯的局部搜索能力［16］；c1和c2為跟蹤局部最優(yōu)解和全局最優(yōu)解的學習因子，rand（）為0～1的隨機數；和分別為粒子i在第k+1次迭代和第k次迭代中第d維的速度，和分別為粒子i在第k+1次迭代后和第k次迭代后第d維的位置，和分別表示粒子i在第k次迭代中后第d維的局部最優(yōu)解和全局最優(yōu)解，d=1，2，…，n，kmax為最大迭代次數。

由于算法對慣性權重系數wk的變化非常敏感［17］。而通過公式（5）可以看出wk只是隨著迭代次數的增大而減小，沒有考慮粒子群進化程度和聚合程度的實時變化:進化程度包括單個粒子尋優(yōu)程度、粒子群局部最優(yōu)平均值尋優(yōu)程度和粒子群全局最優(yōu)值尋優(yōu)程度，聚合程度主要是當前粒子群平均函數值相對于粒子群局部最優(yōu)值平均值的整體接近程度，因此算法實時性能較差；同時，隨著迭代次數的增加，粒子群內多個粒子可能會在搜索空間內出現重疊，需要采取措施將重疊的粒子彈離。

3　基于碰撞彈回策略的改進自適應PSO算法

本文將粒子群進化程度和聚合程度引入慣性權重系數中，使之具有很強的自適應能力，利于算法的尋優(yōu)效果；同時，在算法迭代過程中引入碰撞回彈策略，減小粒子群粒子在搜索空間中的重疊程度，保證粒子群的多樣性。

3.1進化因子和聚合因子

設粒子xi第k次迭代后的函數值為，局部最優(yōu)函數值為，第k次迭代后粒子群全局最優(yōu)函數值為 f（globestk）。

在設計進化因子和聚合因子之前，我們先定義粒子群中第k次迭代后每個粒子的局部最優(yōu)值的平均值為:

定義第k次迭代后所有粒子函數值的平均值為:

3.1.1進化因子

上節(jié)中講到，進化程度受單個粒子局部最優(yōu)值尋優(yōu)程度、粒子群局部最優(yōu)平均值尋優(yōu)程度和粒子群全局最優(yōu)值尋優(yōu)程度影響。

定義粒子i第k次迭代的尋優(yōu)度為:

h1i能夠實時反映粒子i在經過每次迭代后的進化程度。當h1i＜1時，說明粒子i找到了更優(yōu)秀的解；當h1i=1時，說明粒子i可能有停滯的趨勢。

定義第k次迭代的粒子群局部最優(yōu)值平均值的尋優(yōu)度為:

當h2=1時，從某種意義上可以認定算法找到了全局最優(yōu)解或者陷入局部最優(yōu)解。

定義第k次迭代的粒子群全局最優(yōu)值尋優(yōu)度為:

當h3=1時，算法可能找到了全局最優(yōu)值或者趨于停滯。

定義第k次迭代的進化因子公式為:

其中，a1，a2，a3為0～1的相關系數，a1+a2+a3=1，由于進化因子要以全局最優(yōu)值尋優(yōu)度為主，所以a3＞max（a1，a2）。

3.1.2聚合因子

上節(jié)中講到，聚合程度主要是當前粒子群平均函數值相對于粒子群局部最優(yōu)值平均值的整體接近程度。

定義第k次迭代的聚合因子公式為:

3.2改進自適應慣性權重系數wi

慣性權重系數較大，算法有較強的全局搜索能力；慣性權重系數較小，算法有良好的局部搜索能力。當進化因子較大，粒子群進化程度較差，需要減小慣性權重系數以增強算法局部搜索能力，而當聚合因子較大，粒子群聚合度較高，需要增大慣性權重系數以增強算法全局搜索能力。因此，定義第k次迭代時粒子i的改進自適應慣性權重系數公式為:

其中，w為原始慣性權重系數（常數），b1和b2分別為進化因子和聚合因子的調節(jié)系數，0＜b1，b2＜w 且b1+b2=1。

所以第k+1次迭代時粒子i第d維的改進速度更新公式為:

3.3碰撞回彈策略

第k次迭代后粒子i和j（i≠j且i，j=1，2，…，m）之間的n維歐式距離為:設粒子之間距離最小閾值為Δr，假如說明粒子i和 j在n維搜索空間中的距離過小，則判定粒子i和 j發(fā)生碰撞，通過如下公式對粒子i和j做回彈操作（公式為粒子i第l維的回彈操作）:

其中，rand（）為0～1的隨機數。

以此類推，對所有粒子之間的距離進行計算，如果小于閾值，則做回彈操作。

4　WSN覆蓋優(yōu)化算法設計

本文設計改進算法的優(yōu)化目標為:將第1節(jié)中提出的WSN網絡覆蓋優(yōu)化模型的目標函數（式（3））最大化，輸出優(yōu)化后的網絡覆蓋率和所有傳感器節(jié)點的坐標。

其中，粒子群中的一個粒子表示WSN網絡所有傳感器節(jié)點的一個覆蓋分布（不是某個傳感器節(jié)點）。粒子的維數為區(qū)域內傳感器節(jié)點數的兩倍，其中第2d-1維表示第d個節(jié)點的橫坐標，第2d維表示第d個節(jié)點的縱坐標。局部最優(yōu)值表示每個粒子在經過一定次數迭代后各自達到的網絡最大覆蓋率，而全局最優(yōu)值表示經過一定次數迭代后粒子群達到的網絡最大覆蓋率。

在選取碰撞最小閾值Δr時，首先要確定粒子之間維數對應的兩個傳感器節(jié)點的平均距離平方的最小值，假設WSN網絡中有x個傳感器節(jié)點，則Δr的取值為:

當粒子之間距離小于Δr，說明兩個粒子表示的WSN網絡節(jié)點覆蓋分布重疊率較高，粒子之間維數對應的兩個傳感器節(jié)點的距離都過于接近。

4.1算法步驟

下面是算法的步驟:

②初始化迭代次數k=1。

⑤判斷k是否等于最大迭代次數kmax，如果不等于kmax，則k=k+1，返回步驟（3），如果等于kmax，則輸出全局最優(yōu)函數值COV（globestkmax）（最大覆蓋率）及其向量（所有傳感器節(jié)點的坐標），算法結束。

4.2算法流程

算法流程如圖1所示。

圖1　基于碰撞回彈策略的改進自適應PSO算法

5　仿真實驗和分析

5.1實驗環(huán)境

為了驗證本文所設計的基于碰撞回彈策略的改進自適應PSO算法的性能，在VC++6.0中對其進行仿真實驗并通過Matlab進行展示。同時，通過設置不同的參數值后將實驗結果與相關文獻算法的仿真結果作對比。

5.2相關參數設置與實驗結果對比

5.2.1與文獻［3-4，6-7］作對比

設監(jiān)測區(qū)域為50 m×50 m的正方形區(qū)域，將其離散化為51×51個像素點；區(qū)域內分布40個傳感器節(jié)點，每個傳感器節(jié)點的感知半徑為5 m，通信半徑為10 m；參數a1=0.2，a2=0.2，a3=0.6，b1=b2=0.5；， 則Δr=20。

圖2和圖3分別為本文覆蓋優(yōu)化算法結果和優(yōu)化后節(jié)點覆蓋分布圖，本文算法與文獻［3，4，6-7］算法在相同條件下的優(yōu)化結果對比如表1所示。

圖2　本文覆蓋優(yōu)化算法結果

圖3　節(jié)點覆蓋分布圖

表1　算法優(yōu)化效果對比

5.2.2與文獻［5］作對比

設監(jiān)測區(qū)域為50 m×50 m的正方形區(qū)域，將其離散化為51×51個像素點；區(qū)域內分布50個傳感器節(jié)點，每個傳感器節(jié)點的感知半徑為5 m，通信半徑為10 m；參數a1=0.1，a2=0.3，a3=0.6，b1=b2=0.5；，則Δr=25。

圖4和圖5分別為本文優(yōu)化算法結果和優(yōu)化后節(jié)點覆蓋分布圖，本文算法與文獻［5］算法在相同條件下的優(yōu)化結果對比如表2所示。

圖4　本文覆蓋優(yōu)化算法結果

圖5　節(jié)點覆蓋分布圖

表2　算法優(yōu)化效果對比

5.2.3與文獻［10］和文獻［15］作對比

設監(jiān)測區(qū)域為100 m×100 m的正方形區(qū)域，將其離散化為101×101個像素點；區(qū)域內分布30個傳感器節(jié)點，每個傳感器節(jié)點的感知半徑為13 m，通信半徑為26 m；參數a1=0.2，a2=0.3，a3=0.5， b1=b2=0.5；，則Δr=30。

圖6和圖7分別為本文優(yōu)化算法結果和優(yōu)化后節(jié)點覆蓋分布圖，本文算法與文獻［10］和文獻［15］算法在相同條件下的優(yōu)化結果對比如表 3所示。

圖6　本文覆蓋優(yōu)化算法結果

圖7　節(jié)點覆蓋分布圖

表3　算法優(yōu)化效果對比

5.3實驗分析

通過上述仿真實驗結果對比可以看出，本文設計的改進自適應PSO算法在WSN網絡覆蓋優(yōu)化的應用中取得了不錯的效果，優(yōu)化后網絡覆蓋率都高于97.5%，相比其它文獻中的優(yōu)化結果均有2%以上的提升，且算法容易實現，應用適應性更強。從圖3、圖5、圖7可以看出，經過本文算法優(yōu)化，WSN網絡傳感器節(jié)點分布均勻，基本達到了監(jiān)測區(qū)域全覆蓋，雖然圖中存在一些較小的覆蓋漏洞，但這在無線傳感器網絡的聯(lián)通范圍內是允許存在的，不會影響WSN網絡的正常運行。

6　結束語

本文在綜合分析粒子群優(yōu)化（PSO）算法的基本原理和不足之處的基礎上，提出了一種改進自適應粒子群優(yōu)化算法，相比傳統(tǒng)PSO算法，該算法:①將進化因子和聚合因子引入慣性權重系數wi（不同粒子相同迭代次數的慣性權重系數不同）中，實時調整每個粒子的迭代速度。②粒子群迭代后，通過碰撞回彈策略調整所有粒子在搜索空間內的位置，適當增加粒子群的多樣性，避免算法陷入局部最優(yōu)。

通過實驗結果表明:本文算法有效提高了粒子群對空間的搜索能力，相比其它文獻WSN覆蓋優(yōu)化算法，本文算法對WSN網絡優(yōu)化后的覆蓋率均有2%到6%的提升，且算法容易實現，應用適應性更強。從優(yōu)化后傳感器節(jié)點分布圖可以看出WSN網絡傳感器節(jié)點分布更加均勻，基本達到了監(jiān)測區(qū)域全覆蓋。因此，本文設計的改進自適應PSO算法能夠在一定程度上提高無線傳感器網絡的性能。

［1］ 任彥，張思東，張宏科.無線傳感器網絡中覆蓋控制理論與算法［J］.軟件學報，2006，17（3）:422-433.

［2］ Wang Y，Wang R C，Cheng X.Improved Multipath Routing with WNN for the Open Networks［J］.The Journal of China Universities of Posts and Telecommunications，2008，15（2）:107-113.

［3］ 賴錦輝，梁松.基于改進人工螢火蟲算法的無線傳感網絡覆蓋優(yōu)化［J］.計算機測量與控制，2014，22（6）:1862-1864，1874.李麗，李會，張?zhí)禧悾?基于改進魚群算法的WSN覆蓋優(yōu)化策略［J］.微電子學與計算機，2013，30（2）:83-86.

［4］ 王明亮，閔新力，薛君志.基于改進人工魚群算法的WSN覆蓋優(yōu)化策略［J］.微電子學與計算機，2015，32（6）:78-81.

［5］ 廖燦星，張平，李行善，等.基于混合人工魚群算法的傳感器網絡優(yōu)化［J］.北京航空航天大學學報，2010，36（3）:373-377.

［6］ 李顯，劉明生，李燕，等.基于混沌魚群改進算法的無線傳感網覆蓋優(yōu)化［J］.激光雜志，2015，36（1）:98-101.

［7］ 曹劍煒，陳慶奎，莊松林，等.UPSO:基于劃分空間粒子群優(yōu)化的WSN動態(tài)覆蓋優(yōu)化算法［J］.計算機科學，2014，41（6）: 255-257，269.

［8］ 潘麗姣，吳紅英.混沌逃逸粒子群優(yōu)化算法在WSN覆蓋優(yōu)化中的應用［J］.重慶郵電大學學報（自然科學版），2014，26（2）: 177-181.

［9］ 馮琳，冉曉旻，孫韜.逐維判斷PSO算法值的WSN覆蓋優(yōu)化［J］.計算機應用研究，2015，32（12）:3765-3768.

［10］Zhang H，Hou J C.Maintaining Sensing Coverage and Connectivity in Large Sensor Networks［C］//Ad Hoc and Sensor Wireless Networks.2005:89-124.穆天圓，喬學工，張敏.基于Voronoi圖的蜂群優(yōu)化算法在WSN覆蓋中的應用［J］.傳感技術學報，2015，28（10）:1525-1530.

［11］李榮龍，羅杰.一種改進的粒子群優(yōu)化算法［J］.計算機技術與發(fā)展，2015，25（7）:67-71.

［12］劉政.基于粒子群優(yōu)化的多維標度節(jié)點定位算法［J］.傳感技術學報，2015，28（8）:1228-1232.

［13］張娟.基于粒子群優(yōu)化算法的無線傳感器網絡節(jié)能覆蓋研究［D］.上海:華東理工大學，2014.

［14］馮智博，黃宏光，李奕.基于改進粒子群算法的WSN覆蓋優(yōu)化策略［J］.計算機應用研究，2011，28（4）:1272-1275.

［15］Yang C W，Gao W，LIU N G，et al.Low-Discrepancy Sequence Initialized Particle Swarm Optimization Algorithm with High-Order Nonlinear Time-Varying Inertia Weight［J］.Applied Soft Computing，2015，29（4）:386-394.

吳意樂（1991-），男，碩士研究生，貴州大學大數據與信息工程學院，主要研究方向為無線傳感器網絡、智能算法，250770274@qq.com；

何慶（1982-），男，副教授，碩士生導師，貴州大學大數據與信息工程學院，主要研究方向為無線傳感器網絡，認知無線網絡，16353735@qq.com；

徐同偉（1991-），男，碩士研究生，貴州大學大數據與信息工程學院，主要研究方向為認知無線網絡，981667856@qq.com。

Application of Improved Adaptive Particle Swarm Optimization Algorithm in WSN Coverage Optimization*

WU Yile，HE Qing*，XU Tongwei
（College of Big Data and Information Engineering，Guizhou University，Guiyang 550025，China）

Aiming at the problem that the coverage rate of Wireless Sensor Network（WSN）is low due to the uneven coverage of nodes，a method of coverage optimization based on improved adaptive particle swarm optimization algorithm is proposed.Firstly，the mathematical model of WSN coverage optimization is established.Then，the evolutionary factor and the polymerization factor are introduced in the inertia weight coefficient of the particle swarm optimization （PSO）algorithm in order to make the improved algorithm have a strong adaptive ability.And then，the collision resilient strategyisintroducedintheiterativeprocessofthealgorithminordertoovercometheweaknessthattheimprovedparticle swarm optimization algorithm is easy to fall into local optimum in the late optimization.The experimental shows that the network coverage rates after optimizations of WSN by the algorithm in this paper are improved by 2%～6%compared with algorithms in other literatures and the distribution of sensor nodes is more uniform.Therefore，it can effectivelyimprovetheperformanceofwirelesssensornetworks，isastrongapplicationcoverageoptimizationalgorithm.

wireless sensor network；coverage optimization；improved adaptive particle swarm optimization algorithm；inertia weight coefficient；collision resilient strategy

TP183；TP393

A

1004-1699（2016）04-0559-07

項目來源:貴州省科技廳基金項目（黔科合LH字［2014］7628）；貴州省科技廳基金項目（黔科合J字［2012］2171）；貴州大學博士基金項目（貴大人基合字）（［2010］010）；貴州大學研究生創(chuàng)新基金項目（研理工2016066）

2015-11-10修改日期:2016-01-12