萊維飛行的粒子群優(yōu)化算法在WSNs 覆蓋增強中的應用*

盧 玲，謝佳華

(武警工程大學 信息工程系，陜西 西安710086)

0 引 言

無線傳感器網(wǎng)絡(wireless sensor networks，WSNs)廣泛應用到國防軍事、環(huán)境監(jiān)測、交通管理、醫(yī)療健康、工商服務、反恐抗災等諸多領域［1，2］。WSNs 最早源于軍事應用，也是目前最為成熟的應用領域，廣為人知的有美國的智能微塵、C4ISRT 系統(tǒng)、沙地直線等，這些系統(tǒng)的共同特點是協(xié)助實現(xiàn)了戰(zhàn)場態(tài)勢的有效感知，以其獨特的優(yōu)勢，達到了實時性、準確性、全面性獲取戰(zhàn)場信息的目的［3，4］。

WSNs 面臨的挑戰(zhàn)之一是節(jié)點能量的有限性，一般情況下節(jié)點的能量不能補充，能量耗盡后節(jié)點就不能完成信息的采集、傳輸?shù)热蝿?，關鍵節(jié)點死亡后，還可能破壞網(wǎng)絡的性能，導致整個網(wǎng)絡癱瘓。節(jié)點的合理部署是WSNs 應用中首先要考慮的問題，能夠為解決節(jié)點能量、網(wǎng)絡通信帶寬、計算處理能力等資源受限難題提供條件［5，6］。通過節(jié)點部署，能夠優(yōu)化利用網(wǎng)絡資源、提高網(wǎng)絡效率，進而改善感知、傳感、通信等服務質(zhì)量［7］。

目前，國內(nèi)外諸多學者對WSNs 的覆蓋控制進行了深入的研究，提出和改進了大量切實可行的算法應用到該領域，達到了很好的效果。Ian F Akylidiz 在文獻［8］中深入地總結(jié)了覆蓋中應該考慮的問題和解決的方法。陶丹等人在文獻［9］中綜述該領域國內(nèi)外研究進展的同時，討論了有向傳感器網(wǎng)絡覆蓋的基本理論和算法，并提出亟待解決的問題。文獻［10 ～12］分別從不同的角度改進粒子群優(yōu)化(particle swarm optimization，PSO)算法并應用到WSNs 的覆蓋控制中。文獻［13］證明了PSO 算法比其他算法在WSNs 覆蓋優(yōu)化中具有明顯的優(yōu)勢。

PSO 算法存在的最大缺點是容易陷入局部最優(yōu)，可能搜索不到全局最優(yōu)值［14］，為了解決這一問題，本文提出一種將萊維飛行(Levy flight，LF)策略與PSO 相結(jié)合的(LFPSO)算法。在WSNs 覆蓋優(yōu)化過程中，每次粒子更新完位置后，不直接計算優(yōu)化覆蓋目標函數(shù)，而是使用LF 進一步更新個體的位置，而后再計算目標函數(shù)值，避免陷入局部最優(yōu)，達到提高粒子群算法的優(yōu)化性能的目的，從而提高了PSO 算法的收斂速度和求解能力。

1 相關模型的建立

本文根據(jù)研究實際，建立了節(jié)點感知模型、網(wǎng)絡覆蓋模型和覆蓋優(yōu)化數(shù)學模型，并對模型進行了具體的描述。

1.1 感知模型

感知模型的確定是研究WSNs 覆蓋的基礎［15］。目前，主要的感知模型包括布爾感知模型、概率感知模型、精確感知模型和有向感知模型四種［16］，如圖1 所示，根據(jù)應用的實際需求和研究目的的不同，可以選取不同的感知模型。

圖1 節(jié)點感知模型Fig 1 Node sensing model

本文采用精確感知模型，具體數(shù)學描述如下:設監(jiān)測區(qū)域為二維區(qū)域，可以設Si(i=1，2，3，…，N)為傳感器節(jié)點集，N 為節(jié)點個數(shù)，其中，Si的坐標為(xi，yi)。Pj為監(jiān)測區(qū)域內(nèi)的任意一點，則Si對Pj的感知概率為

式中 d(Si，Pj)為感知節(jié)點Si到監(jiān)測區(qū)域內(nèi)點Pj的歐氏距離，當節(jié)點的感知半徑為Re時，則在本文中設r1=0.5Re，r2=Re。α 是與傳感器節(jié)點物理性能和感知環(huán)境有關的參數(shù)。

根據(jù)上式，對于監(jiān)測區(qū)域內(nèi)確定的一點Pj，所有傳感器對它的聯(lián)合檢測概率可以表示為

式中 Sall為該監(jiān)測區(qū)域內(nèi)的所有感知節(jié)點集合。設置一個目標被傳感器檢測到的聯(lián)合概率閾值φ，則傳感器被監(jiān)測到的限制條件為

1.2 覆蓋模型

監(jiān)測區(qū)域可以劃分為m×n 的網(wǎng)格，每個網(wǎng)格是否被覆蓋用式(2)來確定，而是否滿足覆蓋率用式(3)判斷。所以，區(qū)域覆蓋率可以定義為滿足式(2)且滿足式(3)的網(wǎng)格數(shù)與總的網(wǎng)格數(shù)m×n 的比值

設監(jiān)測區(qū)域的總節(jié)點數(shù)為S，工作節(jié)點數(shù)為S'，則工作節(jié)點利用率可用表示為

節(jié)點均勻分布的WSNs，其能量的消耗會均衡一些，這樣可以避免失效節(jié)點過早出現(xiàn)，起到平衡負載、節(jié)省能量的作用。覆蓋均勻性一般用節(jié)點間距離的標準差來表示，即

其中

式中 Ci為第i 個節(jié)點與鄰居節(jié)點的距離;n 為節(jié)點總數(shù)目;Ki為第i 個節(jié)點的鄰居節(jié)點(傳感范圍相交的節(jié)點)的個數(shù);Dij為第i 個節(jié)點與第j 個節(jié)點之間的距離;Mi為第i個節(jié)點與其所有鄰居節(jié)點的距離的平均值。

1.3 覆蓋優(yōu)化數(shù)學模型

根據(jù)覆蓋模型可知，在WSNs 工作過程中，希望在滿足一定覆蓋率的前提下，工作節(jié)點數(shù)越少越好，節(jié)點利用率越低越好，另外，節(jié)點之間的均勻性也對網(wǎng)絡的性能起到重要作用，顯然，節(jié)點的覆蓋均勻性值越小越好。所以，綜合式(4)、式(6)、式(7)的加權作為WSNs 覆蓋優(yōu)化的目標函數(shù)

其中，w1，w2和w3為權值，w1+w2+w3=1。

2 LF-PSO 算法

本文嘗試引入布谷鳥算法與PSO 算法結(jié)合，降低陷入局部最優(yōu)的概率。

2.1 LF 策略

LF 行實際上是一種隨機行走的方程，更新公式為

其中，α 為步長因子，⊕表示點對點的乘法，由上式可知，下一次位置由當前位置和轉(zhuǎn)移概率共同決定，L(λ)為服參數(shù)λ 的隨機搜索向量，L(λ):μ=t－λ，1 ＜λ ＜3，該分布說明了位置的變動符合冪律分布的隨機變動過程。LF 的位置更新策略可表示為

2.2 LF－PSO 算法步驟

PSO 算法在計算早期具有較好的收斂速度，但在后期計算中容易陷入局部最優(yōu)解，是因為在計算初期能保持很高的種群多樣性，然而隨著迭代次數(shù)的增多，大多數(shù)群體集中在一個最優(yōu)解的附近，便出現(xiàn)了早熟現(xiàn)象。為了解決這一問題，在處理WSNs 覆蓋問題的過程中，本文提出LF—PSO 算法，其流程如下:

1)設置WSNs 傳感器節(jié)點覆蓋環(huán)境;

2)初始化參數(shù):種群規(guī)模，粒子速度、位置，最大迭代次數(shù)maxIter;

4)判斷是否符合設定的終止條件，若符合，轉(zhuǎn)步驟(8)，否則，轉(zhuǎn)步驟(5);

7)r 為隨機產(chǎn)生的一個數(shù)，r∈［0，1］，若r ＞0.5，則根據(jù)式(9)重新更新鳥巢的位置，并繼續(xù)更新個體的歷史最優(yōu)位置和全局最優(yōu)位置，否則，轉(zhuǎn)向步驟(5);

8)輸出WSNs 節(jié)點覆蓋的最優(yōu)解;結(jié)束。

3 仿真優(yōu)化

3.1 參數(shù)設置

為了驗證LF－PSO 算法在WSNs 覆蓋優(yōu)化中的有效性，對該算法在Matlab 2008 上進行仿真。

首先找出在規(guī)定區(qū)域內(nèi)達到預期覆蓋率所需要的節(jié)點數(shù)，并求出覆蓋率隨著節(jié)點數(shù)增加的增長率;然后在不同節(jié)點數(shù)的情況下分別比較PSO 算法和LF—PSO 算法的優(yōu)化效果;最后分別比較在相同仿真條件下不同算法覆蓋優(yōu)化性能。

參數(shù)設置為:區(qū)域為10 m×30 m;節(jié)點數(shù)為35;感知半徑1 為3 m;網(wǎng)格為20(row)×60(column));迭代次數(shù)為200。

3.2 仿真實驗

本文設置以下3 個仿真實驗分別從不同的角度驗證算法的有效性:

實驗1:在規(guī)定的監(jiān)測區(qū)域內(nèi)分別隨機拋撒從15 個到50 個傳感器節(jié)點，每次傳感器數(shù)比上一次遞增5 個且每次隨機拋撒5 次，并分別計算它們的覆蓋率的平均值(平均值為5 次拋撒所得覆蓋率的平均值)及其覆蓋率的增長率。仿真結(jié)果圖如圖2 所示。

圖2 節(jié)點數(shù)與覆蓋率及其覆蓋率增長率的關系Fig 2 Relationship between number of node and coverage ratio and its rate of increase

實驗2:在規(guī)定的區(qū)域內(nèi)分別隨機拋撒從15 ～50 個傳感器節(jié)點，每次傳感器數(shù)比上一次遞增5 個，分別用PSO 算法和本文提出算法進行覆蓋優(yōu)化，覆蓋率情況如圖3 所示。

圖3 兩種PSO 算法的覆蓋優(yōu)化性能比較Fig 3 Coverage performance comparison between two kinds of PSO algorithms

實驗3:在監(jiān)測區(qū)域隨機拋撒35 個傳感器節(jié)點，計算其覆蓋率，并計算在PSO［12］、人工魚群算法［17］(artificial fish swarm algorithm，AFSA)、遺 傳 算 法［18］(genetic algorithm，GA)在相同優(yōu)化條件下的覆蓋率以及LF—PSO 算法的覆蓋率。在覆蓋率的求解過程中，采取5 次拋撒求平均覆蓋率的方法。比較結(jié)果如表1。

表1 不同算法優(yōu)化下的覆蓋率比較Tab 1 Comparison of coverage rate under different algorithms optimization

3.3 仿真分析

實驗1 的仿真結(jié)果顯示:在隨機部署的情況下，對于規(guī)定的監(jiān)控區(qū)域(10 m×30 m)，當傳感器節(jié)點數(shù)低于35 個時，覆蓋率隨著節(jié)點數(shù)的增加而以較快速度增長，當節(jié)點數(shù)多于35 個時，覆蓋率的增長率隨著節(jié)點數(shù)的增加而緩慢增長，綜合覆蓋率曲線圖和覆蓋率增長率曲線圖可知，當傳感器節(jié)點數(shù)目為35 個時，為覆蓋率增長的臨界點，所以，對于該區(qū)域，選取35 個傳感器節(jié)點進行優(yōu)化比較合適。

由實驗2 仿真結(jié)果可知，傳感器節(jié)點數(shù)目不同的情況下，分別用PSO 算法和LF—PSO 算法進行優(yōu)化，后者的優(yōu)化效果明顯比前者的要好，證明了LF—PSO 算法性能的優(yōu)越性。

實驗3 通過與其它文獻提出的覆蓋優(yōu)化算法進行比較，在相同環(huán)境下的仿真結(jié)果顯示:LF—PSO 算法能夠較大程度地提高覆蓋率，其原因主要在于LF—PSO 算法能夠跳出局部最優(yōu)值，使搜索結(jié)果最大限度的接近最優(yōu)值，所以，該算法尋優(yōu)能力更強。

4 結(jié) 論

本文針對傳統(tǒng)的PSO 算法在實際應用中存在的不足，將LF 搜索的遍歷性的特點與PSO 算法結(jié)合起來，克服了傳統(tǒng)粒子群算法容易陷入局部最優(yōu)的缺點，大大提高了算法的尋優(yōu)能力。通過仿真實驗表明:本文的算法有效可靠，能夠較好地解決網(wǎng)絡覆蓋的優(yōu)化問題。但在具體應用中如何使用PSO 算法進行覆蓋優(yōu)化，還需要進一步研究。

［1］ 劉 軍，朱維杰，陳嵐嵐，WSNs 在戰(zhàn)場態(tài)勢感知應用中的關鍵技術研究［M］.北京:人民警出版社，2014.

［2］ 邢冬平，段 富，樊茂森.基于極坐標的無線傳感器網(wǎng)絡覆蓋盲區(qū)發(fā)現(xiàn)算法［J］.傳感器與微系統(tǒng)，2014，33(9):117－119.

［3］ 魏 勛.基于虛擬勢場的三維傳感網(wǎng)覆蓋控制技術研究［D］.南京:南京郵電大學，2014.

［4］ Sajadian S，Ibrahim A，Pignaton de Freitas，et al.Improving connectivity of nodes in mobile WSNs［C］∥2011 IEEE International Conference on Advanced Information Networking and Applications(AINA)，IEEE，2011:364－371.

［5］ He Xin，Yin Ke，Gui Xiaolin.The area coverage algorithm to maintain connectivity for WSNs［C］∥Ninth IEEE International Conference on Computer and Information Technology，CIT’09，IEEE，2009:81－86.

［6］ 孫 朋.基于概率模型的無線傳感器網(wǎng)絡覆蓋增強方法［D］.南京:南京郵電大學，2014.

［7］ Wang Bang，Lim Hock Beng，Ma Di.A survey of movement strategies for improving network coverage in wireless sensor networks［J］.Computer Communications，2009(32):1427－1436.

［8］ Ian F Akyildiz，Mehmet Can Vuran.Wireless sensor networks［M］.HoboKen:John Wiley＆Sons Ltd，2010.

［9］ 陶 丹，馬華東.有向傳感器網(wǎng)絡覆蓋控制算法［J］.軟件學報，2011，22(10):2318－2334.

［10］劉麗萍，王 智.基于改進PSO 算法的WSNs 覆蓋優(yōu)化方法［J］.計算機工程，2011，37(8):82－84.

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

［12］王華東，李 巍.混沌粒子群算法在WSNs 覆蓋優(yōu)化中的應用［J］.科技通報，2012，28(8):114－119.

［13］Pratyay Kuila，Prasanta K Jana.Energy efficient clustering and routing algorithms for wireless sensor networks:Particle swarm optimization approach［J］.Engineering Applications of Artificial Intelligence，2014(33):124－140.

［14］朱海系，李 平，程 劍.基于改進算法的PSO 算法的WSNs覆蓋優(yōu)化方法［J］.計算機工程，2011，37(8):82－84.

［15］趙 旭，雷 霖，代傳龍.無線傳感器網(wǎng)絡的覆蓋控制［J］.傳感器與微系統(tǒng)，2007(8):62－66.

［16］Wang P，Dai R，Akyildiz I F.A differential coding－based scheduling framework for wireless multimedia sensor networks［J］.IEEE Transactions on Multimedia，2013，15(3):684－697.

［17］黃瑜岳，李克清.基于人工魚群算法的無線傳感器網(wǎng)絡覆蓋優(yōu)化［J］.計算機應用研究，2013，30(2):554－556.

［18］殷衛(wèi)莉，陳 巍.遺傳算法在無線傳感器網(wǎng)絡覆蓋中仿真研究［J］.計算機仿真，2010，27(10):120－123.

［19］仲元昌，陳 鋒，李發(fā)傳，等.大規(guī)模無線傳感器網(wǎng)絡覆蓋優(yōu)化算法［J］.傳感器與微系統(tǒng)，2014，33(11):117－120.