霍慧慧， 李國(guó)勇

(太原理工大學(xué) 信息工程學(xué)院，山西 太原 030024)

?

改進(jìn)的離散果蠅優(yōu)化算法在WSNs覆蓋中的應(yīng)用*

霍慧慧， 李國(guó)勇

(太原理工大學(xué) 信息工程學(xué)院，山西 太原 030024)

摘要:針對(duì)無(wú)線傳感器網(wǎng)絡(luò)(WSNs)隨機(jī)部署產(chǎn)生的區(qū)域覆蓋率低、節(jié)點(diǎn)利用率差問(wèn)題，提出一種改進(jìn)的離散果蠅優(yōu)化算法(FOA)對(duì)WSNs覆蓋進(jìn)行優(yōu)化。新算法引入自適應(yīng)步長(zhǎng)的分類嗅覺(jué)隨機(jī)搜索和基于移民操作及精英庫(kù)的多種群協(xié)同進(jìn)化機(jī)制，提高了優(yōu)化精度和效率。仿真實(shí)驗(yàn)結(jié)果表明：新算法有效解決了WSNs覆蓋問(wèn)題，在確保網(wǎng)絡(luò)覆蓋率最大化的同時(shí)節(jié)點(diǎn)利用率較大，延長(zhǎng)網(wǎng)絡(luò)壽命。

關(guān)鍵詞:無(wú)線傳感器網(wǎng)絡(luò)； 覆蓋； 果蠅優(yōu)化算法； 多種群； 自適應(yīng)步長(zhǎng)

0引言

無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSNs)廣泛應(yīng)用于軍事、環(huán)境保護(hù)、農(nóng)業(yè)和醫(yī)療等其他領(lǐng)域。由于傳感器節(jié)點(diǎn)的能量受限和區(qū)域的特殊性，經(jīng)常需要由飛行器將傳感器節(jié)點(diǎn)隨機(jī)撒播在監(jiān)測(cè)區(qū)域進(jìn)行大規(guī)模隨機(jī)部署，由此可能會(huì)導(dǎo)致部分區(qū)域覆蓋盲區(qū)或高密度節(jié)點(diǎn)部署，覆蓋盲區(qū)直接影響監(jiān)測(cè)質(zhì)量，節(jié)點(diǎn)密度大則會(huì)在匯聚節(jié)點(diǎn)接收、處理和轉(zhuǎn)發(fā)數(shù)據(jù)時(shí)浪費(fèi)能量，且過(guò)多的冗余數(shù)據(jù)會(huì)堵塞信道和產(chǎn)生數(shù)據(jù)干擾，影響網(wǎng)絡(luò)的可靠性。因此，設(shè)計(jì)一種最大改善初始覆蓋率且低能耗的覆蓋算法對(duì)于WSNs服務(wù)質(zhì)量的提升是很有價(jià)值和意義的。

目前，利用群智能優(yōu)化算法來(lái)優(yōu)化WSNs覆蓋已經(jīng)成為研究的熱點(diǎn)，例如：遺傳算法、粒子群算法、模擬退火算法等[1～4]。果蠅優(yōu)化算法(fruit-fly optimization algorithm，F(xiàn)OA)是我國(guó)臺(tái)灣學(xué)者潘文超教授提出的一種新的群智能優(yōu)化算法[5]，具有全局尋優(yōu)、計(jì)算量小、精度高、收斂快速及易于實(shí)現(xiàn)等優(yōu)勢(shì)。FOA目前已被應(yīng)用于解決交通事件、企業(yè)經(jīng)營(yíng)績(jī)效等實(shí)際問(wèn)題，但對(duì)于解決WSNs覆蓋問(wèn)題還未查到相關(guān)研究?；诖?，本文創(chuàng)新性提出一種改進(jìn)的果蠅優(yōu)化算法—多種群自適應(yīng)離散果蠅優(yōu)化算法(multi-po-pulation adaptive discrete fruit-fly optimization algorithm，MADFOA)， 仿真實(shí)驗(yàn)驗(yàn)證了算法的有效性和穩(wěn)定性。

1WSNs覆蓋問(wèn)題描述

1.1問(wèn)題模型

隨機(jī)部署M個(gè)固定傳感器節(jié)點(diǎn)構(gòu)成節(jié)點(diǎn)集S={s1,s2,…,si,…,sM}至二維矩形目標(biāo)區(qū)域A，其中，傳感器節(jié)點(diǎn)數(shù)量M足夠大，可以基本滿足目標(biāo)區(qū)域的全覆蓋。研究的問(wèn)題是：在保證覆蓋率的前提下，將盡可能多的傳感器節(jié)點(diǎn)置于休眠狀態(tài)，達(dá)到網(wǎng)絡(luò)全連通并且整體低能耗的效果。

在不影響問(wèn)題本質(zhì)的情況下，對(duì)WSNs進(jìn)行相關(guān)假設(shè)：1)所有傳感器節(jié)點(diǎn)均是物理同構(gòu)的，具有相同的感知半徑Rs和通信半徑Rc，并且通信半徑是感知半徑的2倍，即Rc=2Rs；2)所有節(jié)點(diǎn)均采用全向型天線發(fā)射；3)所有傳感器節(jié)點(diǎn)初始能量相同；4)所有傳感器節(jié)點(diǎn)均可以獲得自己的準(zhǔn)確位置信息；5)所有傳感器節(jié)點(diǎn)均包括工作、偵測(cè)和休眠三種狀態(tài);6)將目標(biāo)區(qū)域離散化為l×n個(gè)像素點(diǎn)。

1.2節(jié)點(diǎn)感知模型

傳感器節(jié)點(diǎn)感知模型一般分為二元感知模型和概率感知模型，由于節(jié)點(diǎn)的感知信號(hào)會(huì)受環(huán)境、距離等因素影響，傳感器節(jié)點(diǎn)與監(jiān)測(cè)像素點(diǎn)的歐氏距離越近，像素點(diǎn)被感知到的概率就越大，數(shù)據(jù)的可靠性越高；反之，則越小，數(shù)據(jù)的可靠性越低。鑒于此，引入概率感知模型來(lái)表示節(jié)點(diǎn)感知信號(hào)強(qiáng)度的不確定性。像素點(diǎn)p(xp,yp)可以被節(jié)點(diǎn)si(xi,yi)感知到的概率可以表示為

(1)

節(jié)點(diǎn)集S聯(lián)合監(jiān)測(cè)像素點(diǎn)p的概率為

(2)

由于在概率低于閾值Cth時(shí)，像素點(diǎn)不能被有效感知，即像素點(diǎn)被有效感知的條件是Cp(S,p)≥Cth。由于Cp(S,p)取值在0～1之間，為簡(jiǎn)化計(jì)算，將像素點(diǎn)p的監(jiān)測(cè)概率設(shè)為

(3)

1.3WSNs交叉覆蓋模型

(4)

進(jìn)一步得出傳感器節(jié)點(diǎn)si的平均重疊覆蓋率為

(5)

1.4WSNs覆蓋目標(biāo)

根據(jù)問(wèn)題模型，覆蓋目標(biāo)為尋找滿足覆蓋質(zhì)量的最小覆蓋集。文獻(xiàn)[6]已經(jīng)證明了在滿足全覆蓋的條件下，Rc,Rs滿足Rc=2Rs時(shí)網(wǎng)絡(luò)可以達(dá)到全連通，因此，可以將網(wǎng)絡(luò)連通性的目標(biāo)忽略掉。本文定義子集S′?S，對(duì)于子集S′應(yīng)滿足兩個(gè)目標(biāo)：

目標(biāo)1：覆蓋率Pcov(S′)最大，即

(6)

目標(biāo)2：WSNs中，工作節(jié)點(diǎn)數(shù)最小，即節(jié)點(diǎn)休眠率最大

maxf2=1-|S′|/|S|.

(7)

其中，|S′|為工作節(jié)點(diǎn)總數(shù)；|S|為WSNs中部署的傳感器節(jié)點(diǎn)總數(shù)。

由于WSNs覆蓋目標(biāo)為兩個(gè)目標(biāo)，即多目標(biāo)優(yōu)化問(wèn)題，本文采用加權(quán)法將多目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)化為單目標(biāo)優(yōu)化問(wèn)題，即本文目標(biāo)函數(shù)(味道判決函數(shù))為

maxf=w1f1+w2f2.

(8)

其中，w1和w2為加權(quán)系數(shù)，代表兩個(gè)目標(biāo)函數(shù)的權(quán)重，由決策者對(duì)于目標(biāo)的側(cè)重性決定其大小，二者之和為1。

2MADFOA優(yōu)化WSNs覆蓋

MADFOA不同于基本FOA：各個(gè)種群內(nèi)部采用自適應(yīng)步長(zhǎng)的分類嗅覺(jué)隨機(jī)搜索策略，種群之間通過(guò)移民操作協(xié)同進(jìn)化并采用精英個(gè)體最少保持代數(shù)替代人為設(shè)置的最大迭代次數(shù)作為終止條件。

2.1種群編碼與初始化

每個(gè)果蠅個(gè)體對(duì)應(yīng)一個(gè)WSNs覆蓋狀態(tài)。本文采用長(zhǎng)度為n的二進(jìn)制編碼，表示所有傳感器節(jié)點(diǎn)的工作狀態(tài)，其中,n為飛行器隨機(jī)部署的固定傳感器節(jié)點(diǎn)數(shù)，0,1分別表示傳感器處于休眠與工作的狀態(tài)。

隨機(jī)初始化N個(gè)果蠅個(gè)體，并將其隨機(jī)劃分為M個(gè)果蠅種群。初始迭代次數(shù)g=0，初始精英個(gè)體保持次數(shù)k=0，終止條件：精英個(gè)體最少保持次數(shù)為kmax。

2.2基于自適應(yīng)步長(zhǎng)的分類嗅覺(jué)隨機(jī)搜索機(jī)制

果蠅在嗅覺(jué)搜索階段的步長(zhǎng)設(shè)置會(huì)影響算法的收斂性能。步長(zhǎng)越大，個(gè)體尋優(yōu)范圍越廣，全局尋優(yōu)性能強(qiáng)；步長(zhǎng)越小，尋優(yōu)范圍減小，個(gè)體進(jìn)行精細(xì)化搜索，局部尋優(yōu)能力強(qiáng)；如果步長(zhǎng)過(guò)小，個(gè)體易陷入局部最優(yōu)。而傳統(tǒng)的固定覓食步長(zhǎng)，不能兼顧收斂精度與收斂效率，因此，本文提出了基于自適應(yīng)步長(zhǎng)的分類嗅覺(jué)搜索策略，在平衡尋優(yōu)精度和效率的同時(shí)，有效避免算法早熟。

1)自適應(yīng)步長(zhǎng)設(shè)計(jì)

本文根據(jù)果蠅個(gè)體之間的相異度(又稱距離)來(lái)調(diào)整其嗅覺(jué)隨機(jī)搜索階段的步長(zhǎng)值。果蠅個(gè)體間的相異度定義為二進(jìn)制編碼中相同位置處不同基因位的數(shù)目，表達(dá)式為

S(xi,xj)=|{xim|xim≠xjm,xim∈xi,xjm∈xj}|.

(9)

例如:假定n=8，xi=(01100010)，xj=(11010111)，則相異度S(xi,xj)=5。本文中果蠅個(gè)體的自適應(yīng)步長(zhǎng)策略為L(zhǎng)i=S(xi,xbest)，其中,xbest為上一代果蠅個(gè)體的最優(yōu)個(gè)體。

2)分類嗅覺(jué)隨機(jī)搜索策略

本文針對(duì)不同的步長(zhǎng)值，果蠅個(gè)體采取逆轉(zhuǎn)和交換兩種不同的嗅覺(jué)隨機(jī)搜索策略。

逆轉(zhuǎn)策略：當(dāng)步長(zhǎng)值Li≥2時(shí)，在個(gè)體xi中隨機(jī)選定某個(gè)位置(視為隨機(jī)搜索方向)，對(duì)該位置及其后續(xù)的Li-1個(gè)位置的編碼進(jìn)行逆轉(zhuǎn)操作。通過(guò)采取該搜索方案，隨著果蠅個(gè)體與最優(yōu)個(gè)體相異度的減小，逆轉(zhuǎn)操作的力度逐漸減小，使得算法由前期的全局尋優(yōu)，逐步向后期局部搜索轉(zhuǎn)變，形成自適應(yīng)的嗅覺(jué)隨機(jī)搜索機(jī)制，使算法在尋優(yōu)精度與搜索效率上獲得動(dòng)態(tài)平衡。

交換策略：當(dāng)步長(zhǎng)值Li=1時(shí)，此時(shí)果蠅個(gè)體較為集中，種群多樣性減少，容易陷入局部最優(yōu)。此時(shí)，在個(gè)體xi中隨機(jī)選取兩個(gè)位置(視為隨機(jī)搜索方向)，并對(duì)相應(yīng)位置的編碼進(jìn)行交換。在果蠅個(gè)體差異度很小時(shí)，通過(guò)對(duì)果蠅個(gè)體任意兩個(gè)位置的二進(jìn)制編碼進(jìn)行交換操作，增強(qiáng)了種群多樣性，使其能夠跳出局部最優(yōu)，有效避免早熟，進(jìn)而提高算法的收斂性能。

2.3多種群協(xié)同進(jìn)化機(jī)制

針對(duì)原始果蠅算法存在早熟現(xiàn)象和人為設(shè)置最大迭代次數(shù)的不合理性，本文提出基于移民操作和精華庫(kù)的多種群協(xié)同進(jìn)化機(jī)制。其中，通過(guò)精華庫(kù)收集和保留所有種群公認(rèn)的最優(yōu)個(gè)體(即精英個(gè)體)，實(shí)現(xiàn)種群間的信息共享，并將精英個(gè)體最少保持代數(shù)作為終止條件；各個(gè)種群通過(guò)移民操作進(jìn)行種群間的信息交換，實(shí)現(xiàn)多種群的協(xié)同進(jìn)化。

基于精英庫(kù)的信息共享機(jī)制。精華庫(kù)對(duì)精英個(gè)體的保留操作偽代碼實(shí)現(xiàn)如下：

ifmax(f(bestj))≤f(elitek-1)

elitek=elitek-1;

k=k+1;

else

elitek=b_best;

k=1.

其中，本次迭代各種群的最優(yōu)個(gè)體bestj(j=1,2,…,M)，上次迭代得到的精英個(gè)體elitek-1，本次精英個(gè)體為elitek，b_best表示bestj中的最好值。

基于移民操作的信息交換機(jī)制。移民操作具體為：M個(gè)種群本次迭代得到的最優(yōu)個(gè)體分別為bestj(j=1,2,…,M)，則將種群j+1的最差個(gè)體替換為bestj，將第1個(gè)種群的最差個(gè)體替換為bestM。通過(guò)移民操作使各果蠅種群間進(jìn)行有效的信息交換，實(shí)現(xiàn)種群間的協(xié)同進(jìn)化。

2.4MADFOA流程

MADFOA主要提出兩個(gè)重要改進(jìn)：1)基于移民操作和精華種群的多種群協(xié)同機(jī)制；2)各種群內(nèi)部采用基于自適應(yīng)步長(zhǎng)的分類嗅覺(jué)隨機(jī)搜索機(jī)制。新算法具體流程如圖1所示。

圖1　MADFOA的流程圖Fig 1　Flow chart of MADFOA

3實(shí)驗(yàn)結(jié)果與分析

3.1算法有效性與穩(wěn)定性

參數(shù)設(shè)置為：區(qū)域D為100 m×100 m，M為200，感知半徑為Rs=13 m，通信半徑為Rc=26 m,容錯(cuò)感知半徑為Re=5 m,λ=0.5,β=0.5，感知概率門限Cth=0.7，w1=0.8，w2=0.2。

1)檢驗(yàn)算法的可行性:由參數(shù)設(shè)定，得出WSNs初始覆蓋如圖2所示。

圖2　WSNs初始節(jié)點(diǎn)分布與覆蓋區(qū)域Fig 2　Distribution and coverage area of initial node

由圖2可知，WSNs初始隨機(jī)部署后，覆蓋區(qū)域具有明顯的覆蓋冗余，需要算法對(duì)其進(jìn)行優(yōu)化。算法優(yōu)化過(guò)程中的部分迭代次數(shù)的最優(yōu)覆蓋集如圖3所示。

圖3　進(jìn)化過(guò)程節(jié)點(diǎn)分布圖Fig 3　Node distribution diagram of evolution process

由圖3知，隨著算法迭代次數(shù)的增加，冗余節(jié)點(diǎn)在逐漸減少，各個(gè)目標(biāo)值變化如表1所示。

表1　進(jìn)化過(guò)程目標(biāo)值

經(jīng)過(guò)本文算法優(yōu)化后，覆蓋率增加明顯，節(jié)點(diǎn)休眠率也明顯增大。

2)檢驗(yàn)算法的穩(wěn)定性:將算法執(zhí)行10次，得出實(shí)驗(yàn)結(jié)果如圖4所示。 圖中數(shù)字表示工作節(jié)點(diǎn)數(shù)，通過(guò)算法優(yōu)化可以使WSNs覆蓋率均可以達(dá)到97 %以上，且使得網(wǎng)絡(luò)中的冗余節(jié)點(diǎn)均處于休眠狀態(tài)，延長(zhǎng)網(wǎng)絡(luò)壽命。

圖4　優(yōu)化前后覆蓋率對(duì)比Fig 4　Coverage rate comparison before and after optimization

3.2與其他算法進(jìn)行比較

為進(jìn)一步驗(yàn)證算法的性能，將本文算法與原始的FOA、覆蓋配置協(xié)議(coverage configuration protocol,CCP)算法[7]及遺傳算法(GA)進(jìn)行比較分析，得出性能比較曲線如圖5所示。

由圖5可知，在工作節(jié)點(diǎn)數(shù)相同的情況下，本文算法可以獲得更高的覆蓋率。

圖5　性能對(duì)比曲線Fig 5　Performance comparison curves

4結(jié)束語(yǔ)

本文對(duì)WSNs覆蓋問(wèn)題進(jìn)行分析，并提出MADFOA對(duì)其進(jìn)行優(yōu)化。新算法采用基于自適應(yīng)步長(zhǎng)的分類嗅覺(jué)隨機(jī)搜索和多種群協(xié)同進(jìn)化策略，提高了優(yōu)化精度與效率。通過(guò)實(shí)驗(yàn)仿真驗(yàn)證了新算法求解WSNs覆蓋優(yōu)化問(wèn)題的有效性和穩(wěn)定性。通過(guò)與其他算法的比較，發(fā)現(xiàn)在工作節(jié)點(diǎn)數(shù)相同的情況下，本文算法可以得到更高的覆蓋率，增大節(jié)點(diǎn)利用率，延長(zhǎng)網(wǎng)絡(luò)壽命。

參考文獻(xiàn):

[1]Mo Yuanbin,Liu Jizhong,Wang Baolei,et al.A novel swarm intelligence algorithm and its application in solving wireless sensor networks coverage problems[J].Journal of Networks,2012,7(12):2037-2043.

[2]張輪,陸琰,董德存,等.一種無(wú)線傳感器網(wǎng)絡(luò)覆蓋的粒子群優(yōu)化算法[J].同濟(jì)大學(xué)學(xué)報(bào),2009,37(2):262-266.

[3]屈巍,汪晉寬,趙旭,等.基于遺傳算法的無(wú)線傳感器網(wǎng)絡(luò)覆蓋控制優(yōu)化策略[J].系統(tǒng)工程與電子技術(shù),2010,32(11):2476-2479.

[4]關(guān)志艷,耿巖.虛擬力導(dǎo)向群聚智能優(yōu)化的無(wú)線傳感器網(wǎng)絡(luò)覆蓋策略[J].傳感器與微系統(tǒng),2015,34(1):40-42,46.

[5]Pan Wen-Tsao.A new fruit-fly optimization algorithm:Taking the financial distress model as an example[J].Knowledge-Based Systems,2012,26(2):69-74.

[6]Zhang H,Hou J C.Maintaining sensing coverage and connectivity in large sensor networks[J].Ad Hoc & Sensor Wireless Networks,2005,1(1/2):89-124.

[7]Wang X,Xing G,Zhang Y,et al.Integrated coverage and connectivity configuration in wireless sensor networks [C]∥Procee-dings of the ACM International Conference on Embedded Networked Sensor Systems (SenSys),New York:ACM,2003:28-39.

Application of improved discrete fruit-fly optimization algorithm in WSNs coverage*

HUO Hui-hui, LI Guo-yong

(College of Information Engineering,Taiyuan University of Technology,Taiyuan 030024,China)

Abstract:An improved discrete fruit-fly optimization algorithm(FOA) is proposed,aiming at problems of low area coverage rate and poor utilization rate of node caused by random deployment of wireless sensor networks(WSNs).Adaptive classify smell-based random search step size and different random search methods for different steps adopted,migration-based operation and elite library are introduced in multiple population co-evolution mechanism,which improves precision and efficiency of optimization.Simulation result shows that this new algorithm effectively resolve problem of WSNs coverage,it has the highest nodes usage while maximizing the network coverage rate and extend the network lifetime.

Key words:wireless sensor networks(WSNs); coverage; fruit-fly optimization algorithm(FOA); multi-population; adaptive size

DOI:10.13873/J.1000—9787(2016)02—0157—04

收稿日期：2015—05—28

*基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(51075291)

中圖分類號(hào):TP 212

文獻(xiàn)標(biāo)識(shí)碼:A

文章編號(hào):1000—9787(2016)02—0157—04

作者簡(jiǎn)介:

霍慧慧(1988-)，山西文水人，碩士，主要從事預(yù)測(cè)控制、智能控制理論與應(yīng)用等研究。

李國(guó)勇，通訊作者，E—mail:tygdlgy@163.com。