吳意樂，何　慶，徐同偉

（貴州大學(xué)大數(shù)據(jù)與信息工程學(xué)院，貴陽550025）

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

吳意樂，何慶*，徐同偉

（貴州大學(xué)大數(shù)據(jù)與信息工程學(xué)院，貴陽550025）

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

無線傳感器網(wǎng)絡(luò)；覆蓋優(yōu)化；改進(jìn)自適應(yīng)粒子群算法；慣性權(quán)重系數(shù)；碰撞回彈策略

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

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

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

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

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

針對以上算法的不足以及WSN網(wǎng)絡(luò)覆蓋優(yōu)化目標(biāo)，本文設(shè)計(jì)了基于碰撞回彈策略的一種慣性因子動(dòng)態(tài)變化的自適應(yīng)粒子群優(yōu)化算法并應(yīng)用于WSN網(wǎng)絡(luò)的覆蓋優(yōu)化當(dāng)中，最后通過實(shí)驗(yàn)結(jié)果驗(yàn)證了本文算法的優(yōu)越性。

1　WSN覆蓋模型

1.1問題分析

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

②被測區(qū)域內(nèi)WSN網(wǎng)絡(luò)所有傳感器節(jié)點(diǎn)具有相同的感知半徑和通信半徑，且在通信半徑大于等于兩倍的感知半徑時(shí)，假如WSN網(wǎng)絡(luò)能夠?qū)崿F(xiàn)對監(jiān)測區(qū)域的感知范圍全覆蓋，則所有傳感器節(jié)點(diǎn)必然聯(lián)通［11］。

1.2覆蓋模型描述

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

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

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

式（3）就是無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化模型的目標(biāo)函數(shù)。

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

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

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

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

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

3　基于碰撞彈回策略的改進(jìn)自適應(yīng)PSO算法

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

3.1進(jìn)化因子和聚合因子

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

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

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

3.1.1進(jìn)化因子

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

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

h1i能夠?qū)崟r(shí)反映粒子i在經(jīng)過每次迭代后的進(jìn)化程度。當(dāng)h1i＜1時(shí)，說明粒子i找到了更優(yōu)秀的解；當(dāng)h1i=1時(shí)，說明粒子i可能有停滯的趨勢。

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

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

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

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

定義第k次迭代的進(jìn)化因子公式為:

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

3.1.2聚合因子

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

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

3.2改進(jìn)自適應(yīng)慣性權(quán)重系數(shù)wi

慣性權(quán)重系數(shù)較大，算法有較強(qiáng)的全局搜索能力；慣性權(quán)重系數(shù)較小，算法有良好的局部搜索能力。當(dāng)進(jìn)化因子較大，粒子群進(jìn)化程度較差，需要減小慣性權(quán)重系數(shù)以增強(qiáng)算法局部搜索能力，而當(dāng)聚合因子較大，粒子群聚合度較高，需要增大慣性權(quán)重系數(shù)以增強(qiáng)算法全局搜索能力。因此，定義第k次迭代時(shí)粒子i的改進(jìn)自適應(yīng)慣性權(quán)重系數(shù)公式為:

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

所以第k+1次迭代時(shí)粒子i第d維的改進(jìn)速度更新公式為:

3.3碰撞回彈策略

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

其中，rand（）為0～1的隨機(jī)數(shù)。

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

4　WSN覆蓋優(yōu)化算法設(shè)計(jì)

本文設(shè)計(jì)改進(jìn)算法的優(yōu)化目標(biāo)為:將第1節(jié)中提出的WSN網(wǎng)絡(luò)覆蓋優(yōu)化模型的目標(biāo)函數(shù)（式（3））最大化，輸出優(yōu)化后的網(wǎng)絡(luò)覆蓋率和所有傳感器節(jié)點(diǎn)的坐標(biāo)。

其中，粒子群中的一個(gè)粒子表示W(wǎng)SN網(wǎng)絡(luò)所有傳感器節(jié)點(diǎn)的一個(gè)覆蓋分布（不是某個(gè)傳感器節(jié)點(diǎn)）。粒子的維數(shù)為區(qū)域內(nèi)傳感器節(jié)點(diǎn)數(shù)的兩倍，其中第2d-1維表示第d個(gè)節(jié)點(diǎn)的橫坐標(biāo)，第2d維表示第d個(gè)節(jié)點(diǎn)的縱坐標(biāo)。局部最優(yōu)值表示每個(gè)粒子在經(jīng)過一定次數(shù)迭代后各自達(dá)到的網(wǎng)絡(luò)最大覆蓋率，而全局最優(yōu)值表示經(jīng)過一定次數(shù)迭代后粒子群達(dá)到的網(wǎng)絡(luò)最大覆蓋率。

在選取碰撞最小閾值Δr時(shí)，首先要確定粒子之間維數(shù)對應(yīng)的兩個(gè)傳感器節(jié)點(diǎn)的平均距離平方的最小值，假設(shè)WSN網(wǎng)絡(luò)中有x個(gè)傳感器節(jié)點(diǎn)，則Δr的取值為:

當(dāng)粒子之間距離小于Δr，說明兩個(gè)粒子表示的WSN網(wǎng)絡(luò)節(jié)點(diǎn)覆蓋分布重疊率較高，粒子之間維數(shù)對應(yīng)的兩個(gè)傳感器節(jié)點(diǎn)的距離都過于接近。

4.1算法步驟

下面是算法的步驟:

②初始化迭代次數(shù)k=1。

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

4.2算法流程

算法流程如圖1所示。

圖1　基于碰撞回彈策略的改進(jìn)自適應(yīng)PSO算法

5　仿真實(shí)驗(yàn)和分析

5.1實(shí)驗(yàn)環(huán)境

為了驗(yàn)證本文所設(shè)計(jì)的基于碰撞回彈策略的改進(jìn)自適應(yīng)PSO算法的性能，在VC++6.0中對其進(jìn)行仿真實(shí)驗(yàn)并通過Matlab進(jìn)行展示。同時(shí)，通過設(shè)置不同的參數(shù)值后將實(shí)驗(yàn)結(jié)果與相關(guān)文獻(xiàn)算法的仿真結(jié)果作對比。

5.2相關(guān)參數(shù)設(shè)置與實(shí)驗(yàn)結(jié)果對比

5.2.1與文獻(xiàn)［3-4，6-7］作對比

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

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

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

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

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

5.2.2與文獻(xiàn)［5］作對比

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

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

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

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

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

5.2.3與文獻(xiàn)［10］和文獻(xiàn)［15］作對比

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

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

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

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

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

5.3實(shí)驗(yàn)分析

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

6　結(jié)束語

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

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

［1］ 任彥，張思東，張宏科.無線傳感器網(wǎng)絡(luò)中覆蓋控制理論與算法［J］.軟件學(xué)報(bào)，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］ 賴錦輝，梁松.基于改進(jìn)人工螢火蟲算法的無線傳感網(wǎng)絡(luò)覆蓋優(yōu)化［J］.計(jì)算機(jī)測量與控制，2014，22（6）:1862-1864，1874.李麗，李會(huì)，張?zhí)禧?，?基于改進(jìn)魚群算法的WSN覆蓋優(yōu)化策略［J］.微電子學(xué)與計(jì)算機(jī)，2013，30（2）:83-86.

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

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

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

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

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

［9］ 馮琳，冉曉旻，孫韜.逐維判斷PSO算法值的WSN覆蓋優(yōu)化［J］.計(jì)算機(jī)應(yīng)用研究，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.穆天圓，喬學(xué)工，張敏.基于Voronoi圖的蜂群優(yōu)化算法在WSN覆蓋中的應(yīng)用［J］.傳感技術(shù)學(xué)報(bào)，2015，28（10）:1525-1530.

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

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

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

［14］馮智博，黃宏光，李奕.基于改進(jìn)粒子群算法的WSN覆蓋優(yōu)化策略［J］.計(jì)算機(jī)應(yīng)用研究，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-），男，碩士研究生，貴州大學(xué)大數(shù)據(jù)與信息工程學(xué)院，主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)、智能算法，250770274@qq.com；

何慶（1982-），男，副教授，碩士生導(dǎo)師，貴州大學(xué)大數(shù)據(jù)與信息工程學(xué)院，主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)，認(rèn)知無線網(wǎng)絡(luò)，16353735@qq.com；

徐同偉（1991-），男，碩士研究生，貴州大學(xué)大數(shù)據(jù)與信息工程學(xué)院，主要研究方向?yàn)檎J(rèn)知無線網(wǎng)絡(luò)，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

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

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