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

盧 玲，謝佳華

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

0 引 言

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

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

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

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

1 相關(guān)模型的建立

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

1.1 感知模型

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

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

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

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

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

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

1.2 覆蓋模型

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

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

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

其中

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

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

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

其中，w1，w2和w3為權(quán)值，w1+w2+w3=1。

2 LF-PSO 算法

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

2.1 LF 策略

LF 行實(shí)際上是一種隨機(jī)行走的方程，更新公式為

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

2.2 LF－PSO 算法步驟

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

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

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

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

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

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

3 仿真優(yōu)化

3.1 參數(shù)設(shè)置

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

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

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

3.2 仿真實(shí)驗(yàn)

本文設(shè)置以下3 個(gè)仿真實(shí)驗(yàn)分別從不同的角度驗(yàn)證算法的有效性:

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

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

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

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

實(shí)驗(yàn)3:在監(jiān)測(cè)區(qū)域隨機(jī)拋撒35 個(gè)傳感器節(jié)點(diǎn)，計(jì)算其覆蓋率，并計(jì)算在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 仿真分析

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

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

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

4 結(jié) 論

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

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

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

［3］ 魏 勛.基于虛擬勢(shì)場(chǎng)的三維傳感網(wǎng)覆蓋控制技術(shù)研究［D］.南京:南京郵電大學(xué)，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)絡(luò)覆蓋增強(qiáng)方法［D］.南京:南京郵電大學(xué)，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)絡(luò)覆蓋控制算法［J］.軟件學(xué)報(bào)，2011，22(10):2318－2334.

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

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

［12］王華東，李 巍.混沌粒子群算法在WSNs 覆蓋優(yōu)化中的應(yīng)用［J］.科技通報(bào)，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］朱海系，李 平，程 劍.基于改進(jìn)算法的PSO 算法的WSNs覆蓋優(yōu)化方法［J］.計(jì)算機(jī)工程，2011，37(8):82－84.

［15］趙 旭，雷 霖，代傳龍.無線傳感器網(wǎng)絡(luò)的覆蓋控制［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)絡(luò)覆蓋優(yōu)化［J］.計(jì)算機(jī)應(yīng)用研究，2013，30(2):554－556.

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

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