潘麗姣，吳紅英

(義烏工商職業(yè)技術學院，浙江義烏， 322000)

0 引言

無線傳感器網(wǎng)絡(wireless sensor networks，WSN)是一種由大量能量有限的微型傳感器節(jié)點通過自組織形式形成的網(wǎng)絡，它往往部署于環(huán)境惡劣、人不易到達的地方，且不易對節(jié)點更換電池或充電。WSN覆蓋關系到節(jié)點的分布，分布越均勻，覆蓋率越高，因此，覆蓋優(yōu)化的目標就是在足夠覆蓋監(jiān)測區(qū)域條件下，盡可能延長網(wǎng)絡生存時間，對WSN應用至關重要［1］。如何尋找最優(yōu)的WSN覆蓋優(yōu)化算法，保持整個網(wǎng)絡能量的平衡，成為當前研究的熱點［2］。

針對WSN節(jié)點覆蓋優(yōu)化問題，國內外學者進行了廣泛而深入的研究，提出了大量的WSN節(jié)點覆蓋優(yōu)化算法。傳統(tǒng)覆蓋優(yōu)化算法包括圖論和探測算法，圖論算法假設WSN監(jiān)測區(qū)域內，任意位置均能找到一個節(jié)點，這與WSN實際部署情況不一致，沒有什么實際應用意義;探測覆蓋優(yōu)化算法只適合于小規(guī)模的WSN，對于現(xiàn)代大規(guī)模WSN，無法獲得覆蓋率高的方案［3］。隨著人工智能技術發(fā)展，學者們提出了基于遺傳算法、人工魚群算法、模擬退火算法、粒子群優(yōu)化算法、蟻群算法等WSN傳感器節(jié)點覆蓋優(yōu)化算法，相對于傳統(tǒng)優(yōu)化算法，智能算法可以獲得更優(yōu)的覆蓋方案，使整個網(wǎng)絡節(jié)點的分布更加均勻，能量利用率更高，整個網(wǎng)絡生存周期得到延長［4－7］。尤其是粒子群優(yōu)化(particle swarm optimization，PSO)算法具有參數(shù)設置少，全局搜索能力強等優(yōu)點，在WSN覆蓋優(yōu)化應用最為范圍。然而，在實際應用過程中，標準PSO算法易早熟收斂，陷入局部最優(yōu)解，局部搜索能力差，影響其在WSN覆蓋優(yōu)化中的應用［8］。

為了獲得更優(yōu)的WSN傳感器節(jié)點覆蓋率，克服標準粒子群優(yōu)化算法存在的缺陷，提出一種混沌逃逸粒子群優(yōu)化(chaotic escape particle swarm optimization，ECPSO)算法的WSN覆蓋優(yōu)化方法，并通過具體仿真對比實驗驗證算法的性能。

1 無線傳感器網(wǎng)絡覆蓋模型

1.1 WSN傳感器節(jié)點覆蓋優(yōu)化問題描述

設WSN的節(jié)點si的坐標為(xi，yi)，目標區(qū)域為二維矩形區(qū)域，則節(jié)點si對目標點p(xp，yp)的檢測概率為

(1)式中:Rs和Re分別為傳感器節(jié)點感知半徑和通信半徑;λ1，λ2，β1，β2是與傳感器節(jié)點特性相關的測量參數(shù);d(si，p)為傳感器節(jié)點si與目標點p的歐氏距離;

(3)式中，Sall表示測量目標傳感節(jié)點集合。

設無線傳感器目標節(jié)點可以被檢測到的概率閾值為Cth，那么，傳感器目標節(jié)點能被檢測到的限制條件為

1.2 WSN傳感器節(jié)點覆蓋優(yōu)化的數(shù)學模型

為了有效評價整個無線傳感器網(wǎng)絡的覆蓋率，將無線傳感器監(jiān)測區(qū)域劃分為m×n個網(wǎng)格，然后將網(wǎng)格簡化成為像素點。在本研究中，WSN傳感器節(jié)點覆蓋率定義為滿足(4)式要求的網(wǎng)格數(shù)量與監(jiān)測區(qū)域網(wǎng)絡數(shù)量之比，即:

(6)式中:|S'|表示工作傳感器節(jié)點數(shù);|S|為所有傳感器的節(jié)點數(shù)?？紤]到無線傳感器網(wǎng)絡能量消耗均衡性，引入如下2個定義。

1 )區(qū)域能量Ek。將無線傳感器監(jiān)測區(qū)域均勻分為K個網(wǎng)格，該網(wǎng)格能量等于該網(wǎng)格中全部傳感器節(jié)點的剩余能量與該網(wǎng)格中全部傳感器節(jié)點個數(shù)之比，即

(7)式中:mk為第k個網(wǎng)格中的傳感器節(jié)點數(shù)目;Eki為第k個網(wǎng)格中傳感器節(jié)點i的剩余能量。

2 )能量均衡系數(shù)Ea。Ea計算公式為

Ea描述了傳感器網(wǎng)絡區(qū)域間能耗均衡程度，Ea越小，能耗越均勻，反之，能耗越不均勻。

在最優(yōu)覆蓋節(jié)點集選取基礎上，增加一個能量均衡系數(shù)子函數(shù)，用于描述網(wǎng)絡的能量均衡性，即令f3=Ea。綜合考慮傳感器節(jié)點的覆蓋率、工作節(jié)點數(shù)和能量均衡，在滿足一定覆蓋率基礎上，既節(jié)省能量消耗并保持能量均衡，因此，將WSN覆蓋優(yōu)化的目標函數(shù)定義為

綜合上述可知，要找到最優(yōu)WSN覆蓋方案，實質就是要找到最優(yōu)的w1，w2和w3以及節(jié)點位置。本研究通過采用混沌逃逸粒子群優(yōu)化算法對(9)式進行求解，找到最優(yōu)WSN傳感器節(jié)點覆蓋方案。

2 混沌逃逸粒子群優(yōu)化算法

2.1 標準粒子群優(yōu)化算法

在標準PSO算法中，每一個粒子代表待求解問題的一個潛在解，適應度函數(shù)確定粒子的優(yōu)劣程度。首先隨機產(chǎn)生一群粒子，然后計算粒子的適應度值，最后粒子在解的空間不斷飛行，最終找到問題的解［9］。

分別表示粒子i當前的位置和速度，pbest和gbest分別為粒子自身和群體經(jīng)歷過的最好位置，那么粒子速度和位置更新公式為

(10)式中:c1，c2為加速度系數(shù);k為當前迭代次數(shù);r1和2為［0，1］的隨機數(shù);ω 為慣性權重。

設Vmax和Xmax分別表示粒子的最大速度和最大位置，那么對粒子速度和位置采用(12)式和(13)式進行限制，防止越界。

2.2 混沌逃逸粒子群優(yōu)化算法

一個粒子若發(fā)現(xiàn)一個當前最優(yōu)位置，其他粒子就迅速向其聚集，如果該最優(yōu)位置為一局部最優(yōu)點，那么粒子群出現(xiàn)“早熟”現(xiàn)象，陷入局部最優(yōu)。混沌具有對初始條件敏感性、遍歷性、隨機性等特點，利用混沌運動的這些性質幫助粒子群逃逸局部最優(yōu)。要幫助粒子群逃逸局部最優(yōu)，最為關鍵就是判斷何時出現(xiàn)“早熟”收斂現(xiàn)象，本文通過粒子群體多樣性和平均適應度進行判斷。

1 )粒子群多樣性。設粒子飛行空間對角線的長度為L;粒子群大小為m，所示問題的解空間維數(shù)為p;pid表示粒子i的第d維坐標值，pd表示粒子群第d維坐標的增均值，那么粒子群的多樣性可以采用(14)式描述。

對(14)式進行分析可知，D(t)越大表示粒子群越分散，相反粒子群越集中。

2 )粒子群的適應度方差。隨著粒子群不斷迭代，粒子間差異變小，粒子間差異由適應度值判斷，因此可根據(jù)粒子群適應度變化對“早熟”收斂現(xiàn)象進行判斷。粒子群的適應度方差σ2定義為

σ2越大，表示粒子群中個體聚集程度越小，反之越大。

當粒子群的D(t)和σ2小于預先給定的閾值時，則表示粒子群可能出現(xiàn)了“早熟”收斂現(xiàn)象，此時，本文采用混沌機制對粒子進行擾動，保證粒子群多樣性，使其逃逸局部最優(yōu)點進而尋找全局最優(yōu)點。

2.3 粒子群的混沌擾動

一個典型的Logistic方程見(17)式，根據(jù)(17)式可知，由任意初值z0，可迭代出一個確定的時間序列 z1，z2，z3，…。

(17)式中，μ為控制參量。

粒子群的混沌擾動過程具體如下:

1 )粒子i的pbesti將通過(18)式映射到(17)式Logistic方程的定義域［0，1］上。

5 )從當前粒子群中隨機選擇一個粒子，用P*的位置向量代替選出粒子的位置向量。

2.4 ECPSO的WSN傳感器節(jié)點覆蓋優(yōu)化步驟

1 )設置WSN傳感器節(jié)點覆蓋環(huán)境，并隨機產(chǎn)生一組初始粒子。

2 )根據(jù)(10)式計算每一個粒子的適應度值、初始個體極值Pbestt和群體極值gbest。

3 )根據(jù)(10)式和(11)式更新粒子的速度和位置，產(chǎn)生新一代粒子群。

4 )計算新一代粒子群的個體適應度值。

5 )對于每個粒子來說，若粒子適應度值優(yōu)于自身歷史最優(yōu)值，則用該粒子位置替代個體歷史最優(yōu)位置。

6 )對于每個粒子來說，若粒子適應度值優(yōu)于群體最優(yōu)適應度值，則用該粒子位置替代群體歷史最優(yōu)位置。

7 )計算粒子群的D(t)和σ2值，如果小于閾值時，轉步驟8)，否則根據(jù)正常狀態(tài)進行，轉步驟9)。

8 )對粒子群的最優(yōu)位置向量進行混沌擾動操作。

9 )若達到最大迭代次數(shù)，那么返回全局最優(yōu)粒子位置，否則跳轉步驟3)繼續(xù)搜索。

10 )輸出WSN傳感器覆蓋的最優(yōu)解。

3 仿真實驗

3.1 仿真環(huán)境

為了驗證 ECPSO算法的性能，在 MATLAB 2007工具箱進行仿真實驗，并與基本PSO算法進行比較。其中Cth=0.65，D(t)，σ2的值根據(jù)(14)式和(15)式進行計算。WSN傳感器監(jiān)測區(qū)域大小為10 m×10 m的正方形區(qū)域，節(jié)點感知半徑均為1m，20個節(jié)點隨機分布在監(jiān)測區(qū)域內，節(jié)點初始化位置具體見表1。

表1 傳感器節(jié)點的初始分布Tab.1 Initial distribution of the sensor nodes

3.2 結果與分析

3.2.1 與標準PSO算法的性能對比

PSO和ECPSO算法的WSN節(jié)點覆蓋方案如圖1和圖2所示。

圖1 PSO算法的傳感器節(jié)點分布圖Fig.1 Sensor node distribution map of PSO algorithm

圖2 ECPSO算法的傳感器節(jié)點分布圖Fig.2 Sensor node distribution map of ECPSO algorithm

在圖1和2中，圓表示節(jié)點的感知半徑，實心點表示節(jié)點的位置。對圖1和圖2進行分析對比得知，PSO算法覆蓋方案的節(jié)點分布極不均勻，出現(xiàn)大面積重復覆蓋。而ECPSO文算法不僅節(jié)點覆蓋均勻性優(yōu)于PSO算法，而且重復覆蓋區(qū)域大幅度減少。仿真結果表明，ECPSO由于引入混沌機制，可以幫助PSO算法逃逸局部最優(yōu)解，大幅度提高了節(jié)點的覆蓋率。

3.2.2 與其他優(yōu)化算法性能對比

對ECPSO算法與其他WSN覆蓋優(yōu)化算法進行對比，在相同環(huán)境下，采用遺傳算法(genetic algorithm，GA)、人工魚群算法(artificial fish swarm algorithm，AFSA)、蟻群算法(ant colony optimization algorithm，ACOA)進行對比實驗，結果見表2。

從表2可知，ECPSO算法的平均覆蓋率要高于對比算法，并且休眠率以及能量均衡性均優(yōu)于其他算法。搜索最優(yōu)覆蓋方案的速度最快，對比結果表明，ECPSO是一種高效的、覆蓋率高的WSN傳感器節(jié)點覆蓋算法。

表2 不同覆蓋優(yōu)化算法的性能對比Tab.2 Performance comparison of different coverage optimization algorithm

4 結束語

覆蓋優(yōu)化是當前WSN中的一個重要研究方向，在分析WSN覆蓋優(yōu)化問題基礎上，建立了覆蓋優(yōu)化的數(shù)學模型，并提出采用混沌逃逸粒子群優(yōu)化算法對數(shù)學模型進行求解。仿真結果表明，相對其他WSN覆蓋優(yōu)化算法，ECPSO提高了WSN節(jié)點覆蓋率，重復區(qū)域減少，提高了整個WSN網(wǎng)絡的性能。

［1］WANG Yang，WANG Ruchuan，CHENG Xi.Improved multipath routing with WNN for the Open Networks［J］.The Journal of China Universities of Posts and Telecommunications，2008，15(2):107－113.

［2］張靜，黃憲通，楊新鋒.基于傳感器網(wǎng)絡節(jié)點配置優(yōu)化仿真研究［J］. 計算機仿真，2012，2(11):85－88.

ZHANG Jing，HUANG Xiantong，YANG Xin－feng.Research on Sensor Deployment Based on Probabilistic Detection Model［J］.Computer Simulation，2012，2(11):85－88.

［3］張晉，劉大昕，徐悅竹，等.WSN關鍵區(qū)域覆蓋啟發(fā)式優(yōu)化算法［J］. 計算機工程，2009，35(14):162－164.

ZHANG Jin，LIU Daxin，XU Yuezhu，et al.Critical Area Coverage Heuristic Optimization Algorithm in WSN［J］.Computer Engineering，2009，35(14):162－164.

［4］李燕君，潘建.無線傳感器網(wǎng)絡的節(jié)點智能部署方法研究［J］.計算機科學，2012，39(8):115－118.

LI Yanjun PAN Jian. Intelligent Node Deployment Scheme for Wireless Sensor Networks［J］.Computer Science，2012，39(8):115－118.

［5］賈杰，陳劍，常杜然，等.無線傳感器網(wǎng)絡中基于遺傳算法的優(yōu)化覆蓋機制［J］.控制與決策，2007，22(11):1289－1301.

JIA Jie，CHEN Jian，CHANG Guiran，ZHAO Lin－liang，et al.Optimal coverage scheme based on genetic algorithm in wireless sensor networks［J］.Control and Decision，2007，22(11):1289－1301.

［6］劉麗萍，李桂丹，王智，等.無線傳感器網(wǎng)絡多重覆蓋算法［J］.天津大學學報:自然科學與工程技術版，2009，42(4):310－314.

LIU Liping，LIGuidan，WANG Zhi，et al.A Weighted Multiple Coverage Algorithm in Wireless Sensor Networks［J］.Journal of Tianjin University:Science and Technology，2009，42(4):310－314.

［7］XU Bo，GUAN Qing，CHEN Ke.Multi－Agent Coalition Formation Based on Quantum－behaved Particle Swarm Optimization［J］.Journal of Information ＆ Computational Science，2010，7(5):1059－1064.

［8］赫然，王永吉，王青，等.一種改進的自適應逃逸微粒群算法及實驗分析［J］.軟件學報，2005，16(12):2036－2044.

HE Ran，WANG YongJi，WANG Qing，et al.An Improved Particle Swarm Optimization Based on Self－Adaptive Escape Velocity［J］.Journal of Software，2005，16(12):2036－2044.

［9］馮昌利，高雷阜.一種結合混沌和逃逸的自適應粒子群優(yōu)化方法［J］.計算機工程與應用，2011，47(26):35－38.

FENG Changli，GAO Leifu.Improved adaptive particle swarm optimization method based on self－adaptive escape and chaos［J］.Computer Engineering and Applications，2011，47(26):35－38.

(編輯:魏琴芳)