基于改進粒子群算法和特征點集的無線傳感器網(wǎng)絡覆蓋問題研究

丁 旭，吳曉蓓，黃 成

（南京理工大學自動化學院，江蘇南京210094）

基于改進粒子群算法和特征點集的無線傳感器網(wǎng)絡覆蓋問題研究

丁 旭，吳曉蓓，黃 成

（南京理工大學自動化學院，江蘇南京210094）

本文針對基于網(wǎng)格點的區(qū)域覆蓋算法未考慮網(wǎng)絡的固有特征，導致算法存在近似及復雜度偏高等問題，通過研究區(qū)域覆蓋的特征，結(jié)合概率感知模型，對區(qū)域內(nèi)兩點的覆蓋率關系進行分析，定義了特征點集的概念；對特征點集進行建模，將區(qū)域覆蓋轉(zhuǎn)化為基于特征點集的優(yōu)化問題.利用改進粒子群算法解算此優(yōu)化問題，通過慣性權(quán)重及局部增強因子擾動項，避免其陷入早熟狀態(tài)；同時，針對集中式PSO算法不適用于無線傳感網(wǎng)的問題，本文提出了一種并行分區(qū)式策略.仿真分析驗證了所提算法的優(yōu)越性和特征點距上界的存在性，該方法為區(qū)域覆蓋問題的研究提供了新的思路.

無線傳感器網(wǎng)絡；覆蓋約束優(yōu)化；概率感知模型；特征點集；慣性權(quán)重；并行分區(qū)式粒子群算法

1 引言

覆蓋問題是無線傳感器網(wǎng)絡的一個基本問題［1］，已有許多研究成果［2，3］，其中大多數(shù)是基于二元感知模型的.更符合實際的研究表明，感知模型是概率性的［4］，傳感器以概率ρ感知目標，概率隨著傳感和通信半徑的改變而變化［5］.由于覆蓋重疊區(qū)域并不規(guī)則，覆蓋率的計算比較困難，一些學者又提出了基于網(wǎng)格點的方法［6，7］，這時，覆蓋率近似為被覆蓋的網(wǎng)格點占總網(wǎng)格點的比值.該方法的精確度取決于網(wǎng)格的大小，但網(wǎng)格越小，計算復雜度越大［7］，拓展性不是很好，為此，學者們還提出了一些優(yōu)化算法［8，15～18］.由于未考慮網(wǎng)絡的固有特征，往往導致算法存在過度近似或復雜度高的問題，耗費過多資源.

許多基于網(wǎng)格的覆蓋算法都利用了進化理論思想，如粒子群算法（PSO）［13～18］，遺傳算法（GA）［10，11］和免疫算法（AIS）［9］，且有著各自的優(yōu)越性.文獻［10］利用Monte Carlo設計進化函數(shù)，同時使用歸一化指派法優(yōu)化GA中的交叉問題.文獻［14］在 PSO的基礎上結(jié)合混沌思想獲得了更好的覆蓋效果.但由于這些方法均采用迭代計算，容易陷入局部最優(yōu)解，同時也會帶來算法的復雜度更高.

針對上述問題，本文從網(wǎng)絡自身的特征著手，通過研究兩點間覆蓋率的關系，提出特征點集的概念.對特征點集進行建模，將傳統(tǒng)的區(qū)域覆蓋轉(zhuǎn)化為基于特征點集優(yōu)化覆蓋問題.

2 網(wǎng)絡模型與問題描述

本文研究的對象假設如下：

（1）被監(jiān)測區(qū)域S=l1×l2，其中l(wèi)1，l2是區(qū)域的長和寬；

（2）N個節(jié)點ci（i=1，2，…，N）的初始位置為（xi，yi）；

（3）節(jié)點同構(gòu)且感知半徑RS和通信半徑RC滿足RC=2RS.

設點p被節(jié)點ci覆蓋的概率為［14］：

其中，p是區(qū)域內(nèi)任一點；ci是第i個傳感器節(jié)點；Re（0 ≤Re≤Rs）是反映節(jié)點測量可靠性的參數(shù)；d（ci，p）是ci與p的距離；α1，α2，β1，β2是與節(jié)點本身相關的參數(shù)［14］；λ1，λ2定義如式（2）所示：

因此，多個傳感器節(jié)點同時監(jiān)測到點p的聯(lián)合監(jiān)測概率為：

定義1（點覆蓋） 對于區(qū)域內(nèi)任一點p，如果p的聯(lián)合監(jiān)測概率滿足ρcov（C，p）≥ε，則p被覆蓋；否則p未被覆蓋.其中ε是概率閾值.

定義2（ε-概率區(qū)域覆蓋） ε-概率區(qū)域覆蓋是指區(qū)域內(nèi)所有點均滿足：?pi∈ROI，ρcov（C，pi）≥ε.當ε= 1時為全覆蓋.

ε-概率區(qū)域覆蓋可以表示為：

其中，pi（i=1，2，…，M）是區(qū)域內(nèi)所有M個被監(jiān)測點，ρth為設定的覆蓋率下界.

3 網(wǎng)絡特征建模

3.1點覆蓋率問題

如圖1，p1，p2是相距為L的兩個被監(jiān)測點，N個節(jié)點對p1和p2的聯(lián)合覆蓋率分別為ρ1和ρ2.設N=1時，在以p1為圓心，p1A為半徑的圓周上任一處部署此節(jié)點均滿足p1的覆蓋率為ρ1.

定理1［12］當N=1且節(jié)點在A處，A為p1，p2連線上與圓p1相交，并且距p2更遠的那一點，ρ2取最小值ρ2min.

結(jié)合定理1和概率模型（1），得到以下引理.

引理1 p1，p2相距為L，ρ1，ρ2分別是其對應的覆蓋率.當ρ1=ε時，滿足ρ2≥f1（ε，L），其中：

證明 式（1）中取α1=β1=β2=1，α2=0［14］.結(jié)合圖1得p1處的覆蓋率：ρ1=e-（Re+η）/（Re-η）=ε.其中η=d-Rs.所以有：

結(jié)合定理1滿足ρ2取最小值的情況，p2處的最小覆蓋率為：

將式（5）帶入式（6）中得：

令f1（ε，L）=ρ2min，則有P2≥f1（ε，L）成立.

證畢.

由引理1可得到區(qū)域點特性的一般性結(jié)論.

定理2 p是區(qū)域內(nèi)任意點，當其覆蓋率滿足ρ= f2（ε，L）時，在以其為圓心，以L為半徑的區(qū)域內(nèi)的點的覆蓋率都不小于ε，其中：

由上述定理可知，ρ2min與ρ1和L有關，這表明區(qū)域內(nèi)兩點間覆蓋率存在相關關系，被監(jiān)測區(qū)域可以通過這些關聯(lián)表示出來.同時，由于上述定理是在假設網(wǎng)絡存在唯一節(jié)點的情況下討論的.而由概率聯(lián)合覆蓋式（3）可知，網(wǎng)絡中存在多個節(jié)點時，對區(qū)域的聯(lián)合覆蓋率均大于單一節(jié)點的覆蓋率.因此，每個點p的實際被覆蓋率大于定理2所述，定理2是實際覆蓋率的下界.

得到區(qū)域特征后，我們通過分析表征區(qū)域特征的“特征點集”，即等價于分析整個區(qū)域的性能.

定義3（特征點） 特征點（Feature Point，F(xiàn)P）是指區(qū)域內(nèi)一類點.當該點覆蓋率達到一定值，并以其為圓心，L為半徑的區(qū)域內(nèi)所有點的覆蓋率都大于ε.

定義4（特征點集） 特征點集（FP Set，F(xiàn)PS）是指能夠覆蓋整個區(qū)域的最少特征點組成的集合.

3.2特征點集的選取

定義5（特征點距） 特征點距（FP Distance，F(xiàn)PD）是指特征點集內(nèi)相鄰特征點之間的歐式距離.

定義6（最大特征點距） 最大特征點距（Maximum FPD，MFPD）是指所有FPD的最大值.

定理3 以MFPD為間距選取特征點，與以其它任意FPD為間距相比，選取的特征點數(shù)最少.

定理3可以很容易的由最大特征點距的概念得出.因此為選取最少的特征點，可設定特征點距均為MFPD.如圖2所示，將區(qū)域劃分為多個面積為Sgrid=MFPD ×MFPD的網(wǎng)格，每個網(wǎng)格的頂點為特征點.為滿足定理2的覆蓋特性，設定「MFPD=2L.由推論1可知，MFPD存在上界，設此上界值為MFPD，即可得滿足條件的最少特征點.

推論1 MFPD存在上界 M'（ε，Re），其中：M'（ε，Re）「=2 2Re/（1-lnε）.

證明 由于覆蓋率滿足0≤ρ≤1，由式（5）知：

其中，ROI是被監(jiān)測區(qū)域，M是特征點的數(shù)量，p是區(qū)域內(nèi)任一點，Pj是第j個特征點，D（p，Pj）表示區(qū)域任一點p到Pj的距離，ρi，Pj表示第i個節(jié)點對Pj的覆蓋率，ρPj表示所有節(jié)點對Pj的聯(lián)合覆蓋率，ρ是所有Pj的覆蓋率ρPj中的最小值.

第一個條件表示區(qū)域內(nèi)任一點都至少被一個FP包絡，第二、三個條件分別表示每個FP的聯(lián)合覆蓋率以及其中的最小值，第四個條件表示ρ需滿足條件ε≤ρ≤1，ε是本文設定的FPS覆蓋率下限.

定理4 ε-區(qū)域覆蓋式（4）與FPS優(yōu)化覆蓋式（8）等價.

證明 當式（8）中ρ≥ε時，由于ρ=min｛［ρPj］M×1｝，則ρPj

≥ε，?Pj∈FPS成立，即FPS中所有FP的覆蓋率都不小于ε.由定理2得知，當任一FP滿足ρPj≥ρth（ε，L）時，在其MFPD范圍內(nèi)的點均滿足ρpi≥f2（ρth，L），pi為MFPD范圍內(nèi)的點.由于 FPS中所有 FP可包絡整個區(qū)域，式（4）和式（8）等價.

證畢.

4 并行分區(qū)式粒子群算法

針對網(wǎng)絡分布式的特點，本節(jié)提出并行分區(qū)式PSO來求解優(yōu)化問題（8）.

4.1改進粒子群算法IWPSO

PSO算法［13］包含速度更新和位置更新這兩個重要的操作，如式（9）和（10）所示：

其中，t為當前進化次數(shù)，c1和c2是學習因子，r1和r2是［0，1］內(nèi)的隨機數(shù)，x（t+1）和 v（t+1）分別為粒子在t +1次迭代的位置和速度，pbest是單個粒子個體極值所處的位置，gbest表示所有微粒經(jīng)歷的最好位置.

為克服算法收斂性較差和容易早熟的不足［16］，本文引入新的慣性權(quán)重w并設計了速度增強因子Δv.改進的速度更新公式如下：

式中，w（t）為第t次迭代中的慣性權(quán)重：

其中U（α，1）表示（α，1）的隨機均勻分布，wmin，wmax對應權(quán)重系數(shù)的最大和最小值［20］.

圖3為不同α時的權(quán)值變化.為保證迭代前期權(quán)重跳變不大，α不能太??；而α值過大時對系統(tǒng)的擾動不是很明顯.所以本文α取0.9.與文獻［16］不同，后次的權(quán)重不一定比前次小，這有利于維持算法的全局搜索.

Δv（t+1）是粒子在t+1次迭代時的增強因子.當粒子處于局部最優(yōu)時，增強因子能增加粒子活性，使其跳出局部最優(yōu).Δv（t+1）的計算如下：其中，c3，c4均為常數(shù)，r3為隨機數(shù)，Cbig為大常數(shù)精度因子，Vc為速度增強常數(shù)因子.

定理5 IWPSO可以很快跳出局部最優(yōu)解，并最終收斂到全局最優(yōu)解.

證明 正常情況下，在粒子運行過程中|fit（pbest）-fit（gbest）|≥δ，Δv（t+1）=0，此時采取與PSO相同的方式向最優(yōu)點運動；

當粒子運行滿足|fit（pbest）-fit（gbest）|＜δ但個體pbest≠gbest，即此時粒子陷入局部最優(yōu).由于 Cbig?1，exp（-Cbig·x）→1，則Δv→c3r3Vcc4增強了式（11）中的速度，使粒子快速跳出局部最優(yōu).當其跳出局部最優(yōu)后，Δv（t+1）=0，又按照與PSO相同的方式繼續(xù)搜索最優(yōu)位置.這樣，類似于文獻［16，17］的分析，IWPSO最終是依概率收斂到全局最優(yōu).

證畢.

4.2特征點集覆蓋的并行分區(qū)式IWPSO算法

IWPSO中粒子需要相互通信得到運行信息并作為下一步運行的依據(jù).而WSNs由于能量和通信距離受限，節(jié)點間只能局部通信，這種集中式的運行將給節(jié)點帶來很大負擔.為此本文提出并行分區(qū)式 IWPSO策略，算法基本原理如下所述.

根據(jù)各FP位置，將區(qū)域劃分為 Nc個簇，每個簇內(nèi)節(jié)點數(shù)相同.各節(jié)點通過粒子坐標確定其所屬簇.由于各簇邊界的覆蓋率由本簇邊界和臨簇邊界節(jié)點共同決定，所以節(jié)點應擴大搜索范圍.由式（1）知相距大于（Rs+Re）的節(jié)點對任一點p沒有聯(lián)合覆蓋效果，因此本文設定簇邊界擴展距離為（Rs+Re）.

完成簇后，通信就在簇內(nèi)小范圍進行.各簇的節(jié)點并行利用IWPSO完成相應簇的位置優(yōu)化，并將結(jié)果傳遞給設定的中心節(jié)點（Central Point，CP）完成最終融合.由于各簇優(yōu)化過程相互獨立，可能出現(xiàn)節(jié)點位置重疊的情況.這時，若出現(xiàn)部分節(jié)點間距離小于Rs的情況，由于這些節(jié)點相對較少，則CP可將其余優(yōu)化后的節(jié)點視為固定節(jié)點，在整個測量范圍內(nèi)重新優(yōu)化此類節(jié)點位置，最終實現(xiàn)全局優(yōu)化.

設微粒數(shù)有 M1個，每個微粒帶有N個節(jié)點，Xi（t）表示微粒i中節(jié)點在t次迭代時的位置集合，Xi=（xi1，yi1，xi2，yi2，…，xiN，yiN），Xi中各元素依次代表節(jié)點1到N的橫縱坐標，它所經(jīng)歷的最好位置為pbesti=（pbesti1，pbesti2，…，pbestid），d=2N，所有微粒經(jīng)歷的最好位置為gbest.不同微粒中節(jié)點具有不同的位置，所以對應不同的覆蓋率.算法1給出了最終算法具體步驟，其中式（15）表示當節(jié)點超出搜索區(qū)域時的返回區(qū)域的操作，各區(qū)域邊界Xmax不同：

算法1 并行分區(qū)式IWPSO解（8）輸入：MaxStep，ρth，N，M1，Nc，適應函數(shù)ρ=min｛［ρPj］M×1｝

輸出：節(jié)點最終位置

（1）隨機生成各個微粒的速度和位置，pbest=gbest=0；

（2）按選取的FP和初始位置節(jié)點條件劃分監(jiān)測區(qū)域；

（3）對每個子區(qū)域并行操作（4-14）；

（4）for t=1 to MaxStep

（5） 按當前節(jié)點位置計算各微粒適應值ρ；

（6） if（ρ≥ρth）then執(zhí)行步（15）；else執(zhí)行步（8）；

（7） end if

（8） 各微粒對應ρ與pbest對應的ρ比較，如果較大，則更新pbest；

（9） 將最優(yōu)pbest對應ρ與gbest對應ρ比較，如果較大，則更新gbest；

（10） 將對應pbest的各個微粒，按式（10-11）更新速度和位置；

（11） if（更新后位置未跳出各搜索區(qū)域）then執(zhí)行步（13）；

else執(zhí)行式（15）操作；

（12） end if

（13） 返回步（5）；

（14）end for%對應的gbest即為最終節(jié)點位置.

（15） 各區(qū)域?qū)?yōu)化結(jié)果傳遞給CP進行分析；

（16） if（存在節(jié)點間距＜Rs）then CP對此類節(jié)點執(zhí)行步（4-14）優(yōu)化過程；

（17） end if

4.3復雜度分析

設簇數(shù)為num，由于各簇并行運行，則PSO參數(shù)更新的復雜度為O（M1×2N/num），如圖2所示，總的FP數(shù)為「l1l2/2L2」，各簇內(nèi)FP數(shù)滿足?j∈num，|FPj|≤「l1l2/2L2」.因此，各簇內(nèi)計算覆蓋率的復雜度不大于O（M1×「l1l2/2L2」），算法總的復雜度不大于O（M1× 2N/num+M1×「l1l2/2L2」）.

基于網(wǎng)格點的方法中［15］，區(qū)域網(wǎng)格點數(shù)mn≥l1l2，則算法復雜度為O（M1×2N+M1×mn）.設算法迭代次數(shù)相同，由 mn≥l1l2?l1l2/2L2可知，本文復雜度明顯降低.

5 仿真研究

5.1基于FPS的區(qū)域覆蓋和特征點距分析

本節(jié)對所提算法進行仿真分析，同時驗證了特征點距上界的存在性，對在上界內(nèi)和超過上界的情況進行了對比.設區(qū)域S=100m×100m，節(jié)點N=25，Rs= 15m，傳感器參數(shù)：Re=1/3Rs，α1=β1=β2=1，α2=0，種群數(shù)M1=10，MaxStep=1000，覆蓋閾值ε=0.70.通過推論1 得MFPD≤10.42，取MFPD為10.為了減輕算法隨機性造成的影響，取10次獨立實驗和95%置信區(qū)間.

由圖4和表1可以看到，本文FPS思想最終可以滿足覆蓋的要求，達到的覆蓋率均值超過95%.同時區(qū)域覆蓋率有95%的概率在區(qū)間［0.9511，0.9572］中，而實驗中樣本標準差只有0.004226，表明其波動很小，優(yōu)化算法的結(jié)果穩(wěn)定.

表1　隨機實驗下覆蓋率的統(tǒng)計結(jié)果分析

在圖5中，當選取MFPD≤10.42時，網(wǎng)絡覆蓋率均保持了很好的效果.而超過MFPD上界時，覆蓋率迅速下滑，同時有很大的波動.當MFPD=20時，覆蓋率約為83%，這和初始覆蓋率78.7%相比，并沒有多大的改善.驗證了選擇MFPD≤10.42上界條件的正確性.

圖6對比了MFPD=10和MFPD=20（超過上界）時隨迭代次數(shù)的FPS及區(qū)域覆蓋率變化，當MFPD=10時，F(xiàn)PS覆蓋和區(qū)域覆蓋呈現(xiàn)很好的相關性.MFPD=20時，F(xiàn)PS覆蓋不會對網(wǎng)絡覆蓋有很大的提升.事實上，為了滿足FPS達到覆蓋率要求，節(jié)點會向FP所在位置移動，當距離超過上界時，節(jié)點“聚集”在這些點的周邊，不能很好的滿足區(qū)域的整體要求.

5.2不同算法比較

本節(jié)對4種算法進行比較，包括：Case1（GA［10］），Case2（VFPSO［18］），Case3（PSO［15］），Case4（本文FPS-based IWPSO）.

A.最壞情況分析

取S=20m×20m，N=20～30，Rs=3，MaxStep= 1000.設區(qū)域覆蓋閾值ρth=1，此設置即為最壞情況.因為根據(jù)概率特性，ρ=1不易達到.圖7是N=24時不同協(xié)議的收斂速度.可以看到本文思想的收斂速度最快，其跳出局部最優(yōu)的能力最強.在迭代到約50次時就可到達93%，而其它算法到最大迭代次數(shù)時仍未達到93%.

圖8和圖9分別比較了4種算法在不同節(jié)點數(shù)下的覆蓋率和迭代耗時.可以看到，覆蓋率滿足Case4＞Case3＞Case1＞Case2，而耗時Case1＞Case3＞Case2＞＞Case4.傳統(tǒng)方法達到更好的覆蓋率會損失更多的運算復雜度：覆蓋率滿足Case3＞Case2，則迭代耗時也有Case3＞Case2.本文算法在滿足更大覆蓋率時，其平均耗時只有25s左右，而其余算法均大于150s.另外，GA的覆蓋效果和PSO相似，但耗時更多.

B.一般情況分析

取N=26，ρth=0.85，分析四種算法到達85%覆蓋率時的結(jié)果，如表2所示，其中Ave為均值，SD為標準差，AE為95%置信水平的允許誤差.

定義7（均衡度） 網(wǎng)絡中所有節(jié)點間距離標準差的均值.網(wǎng)絡均衡度表示了節(jié)點分布是否均衡.

表2　四種算法不同性能比較

其中，Ni為節(jié)點i的鄰節(jié)點數(shù)，dij為節(jié)點i和j的距離，Di為i與其所有鄰節(jié)點距離的均值，H為網(wǎng)絡的均衡度.H越小，網(wǎng)絡均衡性越好.

如表2，Case1的迭代次數(shù)少于Case3，但移動距離卻是Case3的兩倍多.本文Case4平均迭代30.4次，僅耗時1.73s.其迭代次數(shù)比其它算法分別減少了52.1%，96.5%，76.2%，移動距離分別減少了58.6%，60.0%，57.6%.同時，計算耗時有95%的概率在區(qū)間［1.48，1.98］內(nèi)，移動距離有95%的概率在區(qū)間［126.2，279.6］內(nèi)，表明在隨機情況下仍能保持收斂速度快且移動距離少的優(yōu)勢.均衡度滿足Case3＜Case1＜Case2＜Case4，充分說明本文算法對解決覆蓋問題有著各方面的優(yōu)勢.

6 總結(jié)

本文通過定義特征點集，將傳統(tǒng)的區(qū)域覆蓋問題轉(zhuǎn)換為基于特征點集的優(yōu)化問題.針對WSNs分布式的特點，提出了并行分區(qū)IWPSO算法，改進了傳統(tǒng)算法容易陷入局部最優(yōu)的缺點.理論分析和仿真證明了該方法能夠較好地解決區(qū)域覆蓋問題，其計算復雜度和收斂性都大大優(yōu)于傳統(tǒng)的方法；另外，本文可以應用在不同的概率感知模型和區(qū)域內(nèi)，包括在不規(guī)則區(qū)域上的應用，這也是今后研究的重點方向.

［1］李勁，岳昆，等.基于融合的無線傳感器網(wǎng)絡k-集覆蓋的分布式算法［J］.電子學報，2013，41（4）：659-665. LI Jin，YUE Kun，et al.Distributed set k-cover algorithms for fusion-based coverage in wireless sensor networks［J］. Acta Electronica Sinica，2013，41（4）：659-665.（in Chinese）

［2］WANG Xue-qing，ZHANG Shu-qin.Research on efficient coverage problem of node in wireless sensor networks ［A］.Proceedings of International Conference on Industrial Mechatronics and Automation［C］.Chengdu，China：IEEE，2009.9-13.

［3］陸克中，等.有向傳感器網(wǎng)絡覆蓋增強問題的貪婪迭代算法［J］.電子學報，2012，40（4）：688-694.LU Ke-zhong，et al.A greedy iterative algorithm of coverage enhancing problem in direction sensor network［J］.Acta Electronica Sinica，2012，40（4）：688-694.（in Chinese）

［4］J Li，J Chen，T H Lai.Energy-efficient intrusion detection with a barrier of probabilistic sensors［A］.Proceedings of IEEE Infocom［C］.Orlando：IEEE，2012.118-126.

［5］M T XIANG，et al.Condition for the coverage and connectivity of wireless sensor network［A］.Proceedings of Advanced Materials Research［C］.Switzerland：TTP，2012. 2589-2592.

［6］LI Hui，ZHANG Xiao-guang，et al.A hybrid deployment algorithm based on clonal selection and artificial physics optimization for wireless sensor network［J］.Information Technology Journal，2013，12（5）：917-925.

［7］Shen，et al.Grid scan：a simple and effective approach for coverage issue in wireless sensor networks［A］.Proceedings of IEEE International Conference Communications ［C］.Istanbul：IEEE，2006.3480-3484.

［8］M HEFEEDA，H AHMADI.Energy-efficient protocol for deterministic and probabilistic coverage in sensor networks ［J］.IEEE Transactions on Parallel and Distributed Systems，2010，21（5）：579-593.

［9］KUMLACHEW M W，GARY G Y.Vaccine-enhanced artificial immune system for multimodal function optimization ［J］.IEEE Transactions on System，Man，and Cybernetics-Part B：Cybernetics，2010，40（1）：218-228.

［10］Y YOON，Y H KIM.An efficient genetic algorithm for maximum coverage deployment in wireless sensor networks［J］.IEEE Transactions on Cybernetics，2013，43 （5）：2168-2267.

［11］Hu X M，Zhang J，et al.Hybrid genetic algorithm using a forward encoding scheme for lifetime maximization of wireless sensor networks［J］.IEEE Trans Evol Comput，2010，14（5）：766-781.

［12］Yang Q，He S，et al.Energy-efficient probabilistic full coverage in wireless sensor networks［A］.Proceedings of IEEE GlobeCom［C］.Anaheim：IEEE，2012.591-596.

［13］B ANAND，I AAKASH.Improvisation of particle swarm optimization algorithm［A］.Proceedings of International Conference on Signal Processing and Integrated Networks ［C］.Noida：IEEE，2014.20-24.

［14］劉維亭，范洲遠.基于混沌粒子群算法的無線傳感器網(wǎng)絡覆蓋優(yōu)化［J］.計算機應用，2011，31（2）：338-341. LIU Wei-ting，F(xiàn)AN Zhou-yuan.Coverage optimization of wireless sensor network based on chaos particle swarm optimization algorithm［J］.Journal of Computer Applications，2011，31（2）：338-341.（in Chinese）

［15］W Z W，et al.Study on coverage in wireless sensor network using grid based strategy and particle swarm optimization［A］.Proceedings of IEEE Asia Pacific Conference on Circuits and Systems［C］.Kuala Lumpur：IEEE，2010. 1175-1178.

［16］S Y H，et al.Empirical study of particle swarm optimization［A］.Proceedings of the IEEE Congress on Evolutionary Computation［C］.Washington DC：IEEE，1999.1945 -1950.

［17］KULKARNI R V，et al.Particle swarm optimization in wireless sensor networks：a brief survey［J］.IEEE Trans on Systems，Man and Cybernetics，2010，41（2）：262 -267.

［18］王雪，等.無線傳感網(wǎng)絡布局的虛擬力導向微粒群優(yōu)化策略［J］.電子學報，2007，35（11）：2039-2042. WANG Xue，et al.Dynamic sensor deployment strategy based on virtual force-directed particle swarm optimization in wireless sensor networks［J］.Acta Electronica Sinica，2007，35（11）：2039-2042.（in Chinese）

丁 旭 男，1991年2月生于江蘇鹽城.博士研究生，研究方向為無線傳感器網(wǎng)絡覆蓋優(yōu)化、動態(tài)博弈網(wǎng)絡編碼及數(shù)據(jù)處理.

E-mail：xdnjust@163.com

吳曉蓓（通信作者） 女，1958年8月生于四川成都.教授，博士生導師.研究方向為無線傳感器網(wǎng)絡、智能控制.曾獲得部省級科技進步二等獎和三等獎；獲國家教學成果一、二等獎；國家級教學名師；發(fā)表論文80余篇等.

E-mail：wuxb@njust.edu.cn

黃 成 男，1975年7月生于江蘇南通.博士研究生，講師.研究方向為無線傳感器網(wǎng)絡、自動化檢測技術.

E-mail：hearthc@163.com

Area Coverage Problem Based on Improved PSO Algorithm and Feature Point Set in Wireless Sensor Networks

DING Xu，WU Xiao-bei，HUANG Cheng

（Institute of Automation，Nanjing University of Science and Technology，Nanjing，Jiangsu 210094，China）

Traditional grid point-based area coverage methods are committed to algorithm optimization，causing coarse approximation and high complexity problems.In order to solve these problems，based on the probabilistic sensing model，we first study the sensing probabilities of two adjacent points and obtain the fundamental mathematical relationship between them.According to this relationship，we define the concept of feature point set（FPS）to character the area.Then，we transform the probabilistic area coverage into optimization problem of FPS.Further，we design an improved particle swarm optimization（IWPSO）algorithm to solve this optimization problem，which can effectively avoid the premature problems in the convergence of PSO algorithm.Finally，through extensive simulations，we demonstrate that our algorithm outperforms the proposed solutions significantly，and provides a new train of thought for area coverage problem.

wireless sensor networks；coverage optimization problem；probabilistic sensing model；feature point set；inertia weight；parallel local particle swarm optimization

TP393.02

A

0372-2112（2016）04-0967-07

電子學報URL：http：//www.ejournal.org.cn 10.3969/j.issn.0372-2112.2016.04.030

2014-10-13；

2015-04-28；責任編輯：李勇鋒

教育部博士點專項基金（No.20113219110028）；江蘇省自然科學基金（No.BK2012803）