基于混沌量子粒子群算法的無線傳感器網絡覆蓋優化*

王　偉，朱娟娟，萬家山，喬　焰，李　旸*

（1.安徽農業大學信息與計算機學院，合肥230036；2.農業部農業物聯網技術集成與應用重點實驗室，合肥230036；3.安徽工程大學機電學院，安徽蕪湖241000）

?

基于混沌量子粒子群算法的無線傳感器網絡覆蓋優化*

王偉1，2，朱娟娟1，2，萬家山3，喬焰1，2，李旸1，2*

（1.安徽農業大學信息與計算機學院，合肥230036；2.農業部農業物聯網技術集成與應用重點實驗室，合肥230036；3.安徽工程大學機電學院，安徽蕪湖241000）

摘要：針對傳統粒子群算法在求解無線傳感器網絡覆蓋問題上存在的收斂速度慢、易陷入局部極值等缺陷，以提高傳感器網絡覆蓋率為主要優化目標，提出了基于量子粒子群和Logistic混沌映射相結合的優化算法CQPSO。該算法基于量子δ勢阱模型，同時引入精英個體適應值方差的早熟判斷機制，提高了搜索效率。仿真結果表明，對比基本粒子群、混沌粒子群以及量子粒子群三種算法，該算法在覆蓋率、均勻度以及平均移動距離指標方面具有更好的覆蓋優化效果。

關鍵詞：無線傳感器網絡；混沌搜索；量子粒子群；覆蓋優化

自溫總理提出“感知中國”以來，我國物聯網產業進入健康快速的發展期。作為當前物聯網領域的熱門研究方向，無線傳感器網絡［1］WSN（Wireless Sensor Networks）的研究與開發也越來越得到重視。作為一種目標區域監測和信息獲取的重要技術，無線傳感器網絡在環境保護［2-3］、智慧醫療［4］、智能建筑、農業物聯網［5］等諸多領域發揮著重大作用。

覆蓋率是無線傳感器網絡的一個重要的衡量指標［6-7］，如何使用有限數量的傳感節點最大范圍的覆蓋目標區域，同時盡可能的延長網絡生存時間，一直是無線傳感器網絡研究的熱點。因此，傳感節點在待測區域的部署數量以及分布位置的合理性對于網絡服務質量的影響顯得尤為重要。針對WSN覆蓋優化問題，群體智能算法［8］在這方面的研究越來越廣泛，國內外學者們相繼提出了基于遺傳算法［9］、蟻群算法［10-11］、粒子群優化算法［12］、人工蜂群算法［13］、人工魚群算法［14］、蛙跳算法［15］以及相關算法的改進組合［16-17］等的WSN覆蓋優化算法。這些算法均能夠有效提高覆蓋率，并使整個網絡節點的分布更加均勻。但算法本身也存在著不足之處，均存在“早熟”收斂、局部最優解［18］等問題。

為了獲得更優的傳感器節點覆蓋率，提高算法搜索效率，并克服標準粒子群算法群體智能程度低，協同搜索能力差［19］等缺陷，本文提出一種基于混沌量子粒子群CQPSO（Chaos Quantum-Behaved Particle Swarm Optimization）的WSN覆蓋優化算法，通過覆蓋率、均勻度、平均移動距離、耗時4個典型的傳感器網絡性能評價指標，并同基本粒子群、混沌粒子群以及量子粒子群三種算法做對比仿真實驗，對CQPSO算法的性能進行驗證。

1　相關工作

1.1無線傳感器網絡覆蓋優化問題概述

本文中，傳感節點的感知模型采用混合感知模型［20］，相比于圓盤模型，該模型能較為客觀的反映現實網絡部署環境。假設監測區域為一個二維平面區域，各個傳感器節點可以部署在該區域內的任意位置。設傳感器網絡中傳感節點si的坐標為（xi，yi），監測區域中任意點p（像素節點）的坐標為（xp，yp），則節點si對目標點p的監測概率為：

式中：d(si,p)為傳感器節點si與目標點p的歐氏距離；re(0＜re＜Rs)是傳感節點測量可靠性參數；α1=re-Rs+d(si,p)，α2=re+Rs-d(si,p)；λ1,λ2,β1,β2是與節點特性有關的測量參數。

整個監測區域的傳感節點對目標點p同時進行檢測的聯合檢測概率為：

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

假設無線傳感器監測區域為m×n（m2）的矩形，將該待測區域劃分成大小相等、面積為1的m×n個相同網格，然后再將網格簡化成為像素點，其離散精度為1。本研究中，WSN傳感器節點覆蓋率定義為滿足式（3）要求的網格數量與待測區域網格總數之比，即：

那么，覆蓋優化問題簡述如下：

Step 1利用式（1）計算一個像素點對各個傳感節點的覆蓋率；

Step 2利用式（2）計算該像素點對各個傳感節點的聯合覆蓋率；

Step 3重復Step 1～Step 2，計算各個像素點對各個傳感節點的聯合覆蓋率；

Step 4利用式（3）～式（4）計算該監測區域的區域覆蓋率，把式（4）作為覆蓋優化算法的目標函數f。

1.2量子粒子群算法描述

2004年，孫俊博士等從量子力學的角度出發提出了一種新的PSO（Particle Swarm Optimization，PSO）算法模型，該模型是以δ勢阱為基礎，認為粒子具有量子的行為，并據此提出了量子粒子群算法［21］。在量子空間中粒子滿足聚集態的性質完全不同，它可以在整個可行解空間中進行搜索，因而QPSO（Quantum- behaved Particle Swarm Optimization）算法的全局搜索性能優于標準PSO算法，且群體智能化程度高，協同搜索能力強［19］。

設搜索空間為j維，則基于δ勢阱模型的粒子位置更新公式如式（5）～式（8）所示：

QPSO算法詳細描述如下：

Initialize X；%初始化種群中每個粒子的位置向量

for t=1：t_max

belta=（1.0-0.5）*（t_max-t）/t_max+0.5 %收縮-擴張系數β%從1.0到0.5線性遞減

mbest=mean（X）%計算平均最好位置

for i=1 to種群規模N

if f（Xi）＞f（Pi）then Pi=Xi%P保存個體最優值

Pg=max（Pi）% Pg保存群體最優值

for j=1 to粒子維度D

u=rand（0，1）v=rand（0，1）

p=u*Pid+（1-u）*Pg%局部吸引子坐標公式

if v＞=0.5 %位置更新公式

Xid=p+β*abs（mbest-Xid）*ln（1/v）

else Xid=p-β*abs（mbest-Xid）*ln（1/v）

將更新后的粒子位置限制在搜索范圍中

直到達到終止條件

1.3Logistic混沌映射

混沌運動具有隨機性、規律性、遍歷性的特點，這些特性應用到優化搜索中將帶來很大的優越性［22］。混沌的隨機性可以讓搜索形成負反饋，避免陷入局部最優；規律性使得搜索有章可循，新解由確定的迭代方程式產生；遍歷性可以無重復的搜索整個可行解區域，提高算法的全局尋優能力。本文使用典型的Logistic混沌映射，方程式如（9）所示：

式中：u為控制參量，N為混沌搜索次數，當u=4，0≤Z0≤1，Logistic完全處于混沌狀態。

2　基于混沌量子粒子群的WSN網絡覆蓋優化算法

2.1算法基本思想

為了解決粒子群算法在求解無線傳感器網絡覆蓋問題上存在的收斂速度慢、易陷入局部極值等問題，本文基于量子粒子群的強全局收斂性和混沌運動的特性，提出了混沌量子粒子群的WSN網絡覆蓋優化算法。該算法迭代尋優過程中依據精英適應值方差的早熟判斷機制，在當前最優解局部進行精細化搜索，避免算法陷入局部極值而停滯，保證了粒子的種群多樣性。

2.2基于精英個體適應值方差的早熟判斷機制

量子粒子群算法在迭代尋優過程中，如果一些粒子暫時找到局部最優解，則其他粒子通過局部吸引子式（6）迅速向其靠攏，導致整個算法易陷入局部最優，即所謂的“早熟”收斂現象。當種群發生早熟收斂，所有粒子聚集在一起時，算法要么陷入了局部最優解，要么就是找到了全局最優解。此時算法尋優過程十分緩慢，降低搜索效率。為保持種群粒子的多樣性，文獻［23-25］提出了基于群體適應值方差的早熟收斂判斷機制，較好的幫助粒子逃離局部最優。然而，這種機制運算量大、耗時多。為此，本文提出基于精英個體適應度方差的早熟判斷機制，其理論依據在于：一個種群發生早熟收斂時，主要應看這個種群中當前適應度暫時最大的那些個體是否有重復或相互趨同的現象。定義如下：

精英個體的適應值方差設粒子種群數量為N，其第t代種群粒子的適應度分別為f1(t),f2(t),…,fN(t)，種群個體的平均適應度記為f_avg(t)，如式（10）所示。將粒子適應度值大于平均適應度的個體成為精英個體，假設有m個（m＜N），記全體精英個體的適應度平均值為f_elite(t)，定義精英個體適應值方差σ2(t)，計算方式如式（11）所示。

其中：F為歸一化因子，作用是限制σ2的大小。在本文中，F的取值如式（12）所示。

此處計算f_elite(t)與fi(t)之間的差值，而不是計算fi(t),i∈(1,N)與f_avg(t)之間的差值，主要是為避免適應值差的個體對整個計算結果帶來的不利影響，最大程度的反映種群在搜索過程中的收斂情況。

2.3算法流程

①設置WSN傳感器節點的覆蓋模型參數，利用混沌算法產生初始化的傳感節點位置，并根據目標函數計算對應粒子的網絡覆蓋率；②初始化每個粒子的個體最優Pbest和群體最優Pg；③收縮擴張系數β隨迭代次數從1.0到0.5線性減小；④根據式（8）計算種群的平均最好位置mbest，并利用式（5）更新每個粒子的位置，并根據目標函數f計算每個粒子更新后的網絡覆蓋率；⑤將每個粒子更新位置后的覆蓋率與Pbest對應的覆蓋率相比較，如果前者較大，則更新Pbest；⑥將種群中的每個粒子的個體最優Pbest對應的覆蓋率與Pg對應的覆蓋率相比較，如果前者較大，則更新Pg；⑦根據式（11）計算種群適應度的方差σ2，如果σ2＜C（C為判斷早熟收斂的停滯閾值，其值根據算法前期測試情況而定），則根據式（9）進行N次（具體算法中取30）混沌搜索，得到最優解向量Y和對應的適應值Ybest，若Ybest＞Pg則Pg=Ybest；⑧如果循環未達到預設最大迭代次數，則返回2）；否則算法結束，并返回群體最優分布。

3　仿真實驗

3.1仿真設置與平臺

根據1.1節覆蓋網絡模型，在20 m×20 m的平面監測區域部署30個無線傳感器節點。所有節點感知半徑Rs=2.5 m，通信半徑Rc=2Rs=5 m。概率模型中，λ1=1，λ2=0，β1=1，β2=1.5，Cth=0.6，t_max=500，測量可靠性參數re=1.25 m，使用MATLAB 2010進行實驗仿真（算法使用元胞數組保存傳感節點位置坐標，每個粒子包含30個傳感節點位置坐標）。

3.2停滯閾值C的影響

CQPSO算法的主要參數包括種群規模，收-擴因子β以及停滯閾值C等。對收-擴因子β進行討論的文獻已有很多。因此，本節將重點研究停滯閾值C對算法搜索性能的影響。

種群數量取30，收-擴因子β從1.0到0.5線性減少，停滯閾值C分別取0.002 5，0.003 0，0.003 5，0.004 0，0.004 5。對目標函數f分別進行10次優化，函數的維度取30，迭代次數500，優化結果見下表1。同時，為了更好的評估影響，除主要指標覆蓋率外，引入最優值迭代次數（算法尋得最優值之前的迭代次數）、均勻度、平均移動距離、耗時4個性能指標。

表1　停滯閾值C對算法的影響

表1中：elite/all：elite表示基于精英個體適應值方差的早熟判斷機制的優化結果，all表示基于群體適應值方差的早熟收斂判斷機制的優化結果。網絡均勻度指標計算公式如式（13）式所示：

式中：n為節點總數；ki為節點i的鄰居數；Di,j為節點i、j之間的歐氏距離；Mi為節點i與其所有鄰居節點之間歐氏距離的平均值；U為網絡均勻度，U越小，則覆蓋均勻性越好。

從表1數據可以發現，C值太小或太大都會影響算法的優化性能。總體來看，基于精英個體適應值方差的早熟判斷機制的表現比基于群體適應值方差的早熟收斂判斷機制性能的函數優化結果要優越些。在小于及大于0.003 5的范圍結果較差。這是由于C取太小會使得粒子非常聚集時才進行擾動，容易陷入局部極值。而C太大，則使得粒子還沒有對局部區域仔細搜索就被擾動，影響其局部搜索能力。考慮圖1所示兩種機制對主要指標覆蓋率影響，本次實驗中的停滯閾值C取0.003 5。

圖1　C的取值對兩種機制下覆蓋率的影響

3.3實驗結果與分析

3.3.1初始傳感節點覆蓋情況分析

為了分析兩種不同算法所產生的初始傳感節點位置分布情況，在待測區域生成如圖2、圖3所示的節點位置分布圖（圖中的“+”表示傳感節點的位置，圓周表示傳感節點的感知范圍），可以看出：隨機生成的傳感節點分布雜亂無章，重復覆蓋區域較多；而結合混沌算法優化后節點布局較為均勻，重復覆蓋區域相對較少。

圖2　隨機生成的傳感節點位置分布

圖3　混沌生成的傳感節點位置分布

對種群的20個粒子位置分布情況求取平均值，計算出初始覆蓋率、均勻度，如表2所示。從表中可以看出，混沌算法產生的初始節點位置分布的覆蓋率、均勻度分別為0.712 0、0.824 7，相比于隨機生成的0.676 0、1.042 0分別提高3.60%、0.217 3，可見經混沌優化后的傳感節點分布具有相對更好的覆蓋效果。

表2　傳感節點初始位置生成情況對比

3.3.24種算法的實驗結果對比

為了驗證算法性能，選擇基本粒子群（PSO）、混沌粒子群CPSO（Chaos Particle Swarm Optimization）以及量子粒子群（QPSO）3種粒子群算法做對比實驗。圖4～圖7分別代表PSO、CPSO、QPSO以及CQPSO算法優化后的傳感節點位置分布。從圖4～圖7可以看出，CPSO和CQPSO算法優化后的節點在待測區域內分布更加均勻。如圖8所示，4種算法經500次迭代進化后，CQPSO、CPSO、QPSO和PSO算法的網絡覆蓋率分別為88.13%、86.17%、80.17%和75.92%，CQPSO相比于其他3種算法分別提高1.96%、7.96%和12.21%。

圖5　混沌粒子群算法優化后的節點分布

圖6　量子粒子群算法優化后的節點分布

圖8　4種優化算法的網絡覆蓋率收斂曲線

3.3.3性能指標對比結果

為了更好的評價算法，對4種算法分別進行20次獨立的優化實驗求各指標均值，比較每種算法在各個性能指標上的優劣，每種算法的性能指標數據如表3所示。

表3　算法運行20次結果對比

從表3數據可以得出：在均勻度方面，CQPSO算法的均勻度最高，20次測試平均值為0.6846，比CPSO、QPSO和PSO算法分別提高了2.51%、9.06%以及16.05%；在平均移動距離方面，CQPSO算法平均移動距離為9.24m，比CPSO、QPSO和PSO算法平均少移動了0.35 m、0.72 m和1.28 m；然而在整個算法耗時方面，CQPSO算法平均耗時21 986 s，比QPSO和PSO算法延時2 182 s和1 587 s，但比CP?SO算法耗時快了約710 s，這是由于CQPSO算法有比CPSO算法更好的全局收斂性（位置更新公式的不同），混沌優化次數較少。

綜合上述可知，CQPSO算法相比于其他3種算法在網絡覆蓋率、均勻度以及平均移動距離3個指標方面具有更優的表現，混沌優化后的傳感節點分布更加均勻，交叉重復覆蓋相對較小，節點能量消耗相對均衡；同時，每個節點平均移動距離減少，降低了節點移動的能量耗損。由于CQPSO算法中增加了混沌優化環節，導致計算復雜度有一定增加，計算耗時相應增多。

4　結語

鑒于覆蓋優化問題在當前無線傳感器網絡研究中的重要性，以網絡覆蓋率為優化目標，本文將量子粒子群算法和混沌優化相結合，提出了基于混沌量子粒子群算法的無線傳感器網絡覆蓋優化算法。該算法基于量子粒子群算法提高算法的全局收斂性，以及精英個體適應值方差的機制判斷算法是否陷入過早收斂；若陷入局部極值，算法對局部極值位置進行混沌搜索，引導其跳出局部最優。仿真結果表明，相對于其他3種粒子群WSN覆蓋優化算法，CQPSO算法提高了WSN節點覆蓋率，網絡均勻度較低，平均移動距離較少，提高了WSN網絡的整體性能。

參考文獻：

［1］孫利民，李建中，陳渝.無線傳感器網絡［M］.北京：清華大學出版，2005.

［2］高德民，林海峰，劉云飛，等.基于無線傳感網的森林火災FWI系統分析［J］.林業科技開發，2015，29（1）：105-109.

［3］李光輝，趙軍，王智.基于無線傳感器網絡的森林火災監測預警系統［J］.傳感技術學報，2007，19（6）：2760-2764.

［4］趙澤，崔莉.一種基于無線傳感器網絡的遠程醫療監護系統［J］.信息與控制，2006，35（2）：265-269.

［5］常超，鮮曉東，胡穎.基于WSN的精準農業遠程環境監測系統設計［J］.傳感技術學報，2011，24（6）：879-883.

［6］Huang C F，Tseng Y C.The Coverage Problem in A Wireless Sen?sor Network［J］.Mobile Networks and Applications，2005，10（4）：519-528.

［7］Cardei M，Wu J.Energy-efficient Coverage Problems in Wireless Ad Hoc Sensor Networks［J］.Computer Communications，2006，29 （4）：413-420.

［8］胡中功，李靜.群智能算法的研究進展［J］.自動化技術與應用，2008，27（2）：13-15.

［9］賈杰，陳劍，常桂然，等.無線傳感器網絡中基于遺傳算法的優化覆蓋機制［J］.控制與決策，2007，22（11）：1259-1292.

［10］黃亮.基于改進蟻群算法的無線傳感器網絡節點部署［J］.計算機測量與控制，2010，18（9）：2210-2212.

［11］毛科技，方凱，戴國勇，等.基于改進蟻群算法的無線傳感器網絡柵欄覆蓋優化研究［J］.傳感技術學報，2015，28（7）：1058-1065

［12］林祝亮，馮遠進.基于粒子群算法的無線傳感器網絡覆蓋優化策略［J］.計算機仿真，2009，26（4）：190-193.

［13］文政穎，翟紅生.基于混沌人工蜂群算法的無線傳感器網絡覆蓋優化［J］.計算機測量與控制，2014，22（5）：1609-1612.

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

［15］龍騰，孫輝，趙嘉.基于改進蛙跳算法WSN移動節點部署研究［J］.計算機工程，2012，38（5）：96-98，116.

［16］李忠.采用遺傳模擬退火策略的WSN節點部署優化［J］.系統仿真學報，2014，26（2）：353-356.

［17］劉洲洲，王福豹，張克旺.改進螢火蟲算法性能分析及其在WSNs網絡覆蓋中的應用［J］.傳感技術學報，2013，26（5）：675-682.

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

［19］孫俊.量子行為粒子群優化算法研究［D］.無錫：江南大學，2009.

［20］Li S J，Xu C F，Pan W K.Sensor Deployment Optimization for De?tecting Maneuvering Targets［C］//Proceedings of 7th International Conference on Information Fusion.Washington，DC：IEEE Com?puter Society，2005：1629-1635.

［21］Sun J，Feng B，Xu W B.Particle Swarm Optimization with Parti?cles Having Quantum Behavior［C］.Proceedings of 2004 Congresson Evolution Computation.Piscataway，NJ：IEEE Press，2004：325-331.

［22］申清明，閻立軍.基于混沌搜索的特征選擇方法［J］.兵工學，2013，34（12）：1616-1619.

［23］逄珊，楊欣毅，張小峰.混沌映射的多種群量子粒子群優化算法［J］.計算機工程與應用，2012，48（33）：56-62.

［24］谷海紅，齊名軍，李士勇.基于混沌機制的混合量子粒子群優化算法［J］.計算機工程，2009，35（12）：164-165，168.

［25］林星，馮斌，孫俊.混沌量子粒子群優化算法［J］.計算機工程與設計，2008，29（10）：2610-2612.

王　偉（1989-），男，安徽六安人，碩士研究生，主要從事計算機應用技術、計算機網絡安全方面的研究，17009636880，wwang0211@163.com；

李　旸（1963-），男，安徽懷遠人，現任安徽農業大學教授、碩士生導師、院學術委員會副主任、院教學專家組組長，主要研究方向為計算機網絡分析管理、智能交通、智能建筑與安全防范技術、農業網絡信息工程應用等；擔任安徽省及合肥市政府采購資深專家評委；安徽省智能交通協會理事；安徽省建筑智能化資深專家；安徽省教育信息化專家委員會委員，lyand@ahau.edu.cn。

朱娟娟（1991-），女，安徽肥東人，碩士研究生，主要從事從事計算機應用技術、智能農業信息技術方面的研究，15056977902，15056977902@163.com；

Coverage Optimization of Wireless Sensor Networks Based on Chaotic Quantum-Behaved Particle Swarm Algorithm*

WANG Wei1，2，ZHU Juanjuan1，2，WAN Jiashan3，QIAO Yan1，2，LI Yang1，2*
（1.School of Information &Computer Science，Anhui Agriculture University，Hefei 230036，China；2.Key Laboratory of Technology Integration and Application in Agricultural Internet of Things，Ministry of Agriculture，Hefei 230036，China；3.College of Mechanical &Electrical Engineering，Anhui Polytechnic University，Wuhu Anhui 241000，China）

Abstract：The conventional PSO algorithm has its own shortages of low convergence speed，sensitivity to local con?vergence in solving problems of the WSN coverage rate.To address these problems，based on the combined utiliza?tion of quantum-behaved particle swarm algorithm and logistic chaotic map，taking the network coverage rate as the optimized goal，a hybrid optimal algorithm（chaos quantum-behaved particle swarm optimization，CQPSO）is pro?posed.By using the new model based delta potential and judging the local convergence by the variance of the elite individuals’fitness，the algorithm improves the search's efficiency and precision.Simulating results show that the proposed algorithm is superior to other algorithms（namely PSO，QPSO and CPSO algorithm）on the coverage rate，network evenness and average traveling distance.

Key words：wireless sensor networks（WSN）；chaos searching；QPSO；coverage optimization

doi：EEACC：621010.3969/j.issn.1004-1699.2016.02.023

收稿日期：2015-08-10修改日期：2015-12-04

中圖分類號：TP391.9

文獻標識碼：A

文章編號：1004-1699（2016）02-0290-07

項目來源：國家自然科學基金項目（61402013）；省科技攻關計劃項目（1301b042008）