基于周期果蠅算法的無線傳感網(wǎng)覆蓋優(yōu)化

尹向兵，吳良超

（1.安徽警官職業(yè)學(xué)院 教務(wù)處，安徽 合肥 230031；2.安徽大學(xué) 計(jì)算智能與信號處理重點(diǎn)實(shí)驗(yàn)室，安徽 合肥 230039）

基于周期果蠅算法的無線傳感網(wǎng)覆蓋優(yōu)化

尹向兵1，吳良超2

（1.安徽警官職業(yè)學(xué)院 教務(wù)處，安徽 合肥 230031；2.安徽大學(xué) 計(jì)算智能與信號處理重點(diǎn)實(shí)驗(yàn)室，安徽 合肥 230039）

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks,WSN)是一種分布式傳感網(wǎng)絡(luò)，由大量可移動(dòng)的微型傳感器節(jié)點(diǎn)以自組織的方式組成，信息通過節(jié)點(diǎn)進(jìn)行多跳傳輸.在無線傳感器網(wǎng)絡(luò)覆蓋問題上，傳統(tǒng)的節(jié)點(diǎn)部署策略會出現(xiàn)部署速度慢，覆蓋范圍小，服務(wù)質(zhì)量差等問題.本文將提出一種改進(jìn)的果蠅算法，實(shí)現(xiàn)網(wǎng)絡(luò)覆蓋的優(yōu)化.果蠅算法具有很多優(yōu)點(diǎn)，例如計(jì)算量較小，運(yùn)行時(shí)間短，算法復(fù)雜度低，且尋優(yōu)精度較高等.本文將果蠅算法與WSN覆蓋模型相結(jié)合，可以快速實(shí)現(xiàn)節(jié)點(diǎn)布局優(yōu)化，得到更高的網(wǎng)絡(luò)覆蓋率.通過仿真對比實(shí)驗(yàn)，可以看出改進(jìn)果蠅算法的有效性和優(yōu)越性，在尋優(yōu)性能方面明顯優(yōu)于其它幾種算法.

WSN；果蠅算法；傳感器節(jié)點(diǎn)；覆蓋優(yōu)化

1 引言

無線傳感器網(wǎng)絡(luò)[1]是一種分布式傳感，面對多節(jié)點(diǎn)、多任務(wù)的無線自組織網(wǎng)絡(luò).無線傳感器網(wǎng)絡(luò)是由大量部署在監(jiān)測區(qū)域內(nèi)的傳感器節(jié)點(diǎn)組成，通過傳感器節(jié)點(diǎn)對監(jiān)測區(qū)域的信息進(jìn)行實(shí)時(shí)收集.WSN作為一門新的技術(shù)，被廣泛應(yīng)用于軍事領(lǐng)域、農(nóng)業(yè)生產(chǎn)、生態(tài)監(jiān)測與災(zāi)害預(yù)警、基礎(chǔ)設(shè)施狀態(tài)檢測、工業(yè)領(lǐng)域、智能家居等.傳感器網(wǎng)絡(luò)的一個(gè)關(guān)鍵問題就是節(jié)點(diǎn)的部署優(yōu)化，對于如何提高網(wǎng)絡(luò)的覆蓋率、降低網(wǎng)絡(luò)的能耗、簡化網(wǎng)絡(luò)模型，最終提高服務(wù)質(zhì)量，這是目前研究的一大熱門問題，也是未來無線傳感技術(shù)發(fā)展的基礎(chǔ).

目前已有多種智能算法運(yùn)用在無線傳感器網(wǎng)絡(luò)的覆蓋優(yōu)化問題上，例如粒子群算法、魚群算法、遺傳算法等.這些算法雖然在覆蓋的優(yōu)化問題上取得了良好的效果和重大的進(jìn)步，但依然存在著一些明顯的不足，例如某些算法的結(jié)構(gòu)過于復(fù)雜，導(dǎo)致整體的計(jì)算速度太慢，達(dá)不到實(shí)時(shí)的要求，某些算法的性能太差，導(dǎo)致最后的覆蓋效果太差，遠(yuǎn)遠(yuǎn)達(dá)不到用戶的服務(wù)要求，某些算法的參數(shù)太多，導(dǎo)致網(wǎng)絡(luò)模型過于復(fù)雜，實(shí)際的部署方式往往不容易做到，等等.因此本文將運(yùn)用一種改進(jìn)的果蠅算法，解決以上算法在無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化問題上的弊端，實(shí)現(xiàn)對網(wǎng)絡(luò)覆蓋的進(jìn)一步優(yōu)化.

2 果蠅算法

果蠅優(yōu)化算法[2]（Fruit Fly Optimization Algorithm，F(xiàn)OA）是臺灣學(xué)者潘文超經(jīng)過研究發(fā)現(xiàn)，并于2011年提出的一種新型智能優(yōu)化算法，它具有很好的全局優(yōu)化性能，能夠解決很多的優(yōu)化求解問題.果蠅有著優(yōu)于其它生物的感官知覺，特別是視覺與嗅覺，依靠靈敏的嗅覺，果蠅可以很好的感知到空氣中的各種氣味分子，甚至可以嗅到幾十公里以外的食物.同時(shí)利用敏銳的視覺與其它果蠅聚集，并向該方向移動(dòng).果蠅算法就是模仿果蠅的覓食過程而提出一種新型的群智能優(yōu)化算法.

2.1 基本果蠅算法：

果蠅擁有優(yōu)于其它物種的感官，它可以收集空氣中的氣味分子搜尋遠(yuǎn)處的食物，然后聚集同伴朝食物方向并攏. FOA算法就是模擬果蠅群體的覓食過程而衍生的優(yōu)化算法，其步驟可以歸納為：

①初始化種群大小Sizepop,最大迭代次數(shù)Maxgen,隨機(jī)初始化果蠅群體位置X_axis,Y_axis.

②果蠅個(gè)體隨機(jī)向各個(gè)方向的位置進(jìn)行搜尋.

③計(jì)算果蠅個(gè)體與原點(diǎn)距離d,再將距離的倒數(shù)做為果蠅個(gè)體的味道濃度判定值Si.

④將味道濃度判定值 Si代入適應(yīng)度函數(shù)（Fitness function），求出果蠅個(gè)體的味道濃度.

⑤找出果蠅群體中Smelli最佳的果蠅

⑥記錄并保留最佳味道濃度值bestSmelli與X,Y坐標(biāo).

⑦開始迭代，重復(fù)執(zhí)行②～⑤，并判斷最佳味道濃度是否優(yōu)于前一次迭代得到的味道濃度，并且當(dāng)前迭代次數(shù)小于最大迭代數(shù)Maxgen,則執(zhí)行⑥，否則，算法結(jié)束.

2.2 改進(jìn)步長果蠅算法

根據(jù)上一節(jié)對果蠅算法的介紹，果蠅算法中的果蠅個(gè)體每次迭代從相同的起點(diǎn)出發(fā)，然后向隨機(jī)的方向進(jìn)行搜索，搜索步長為固定區(qū)間[-H,H]內(nèi)的隨機(jī)數(shù).當(dāng)H設(shè)置比較大時(shí)，算法的全局搜索能力較強(qiáng)，收斂的速度較快，但算法局部搜索能力較低，導(dǎo)致后期收斂精度不夠.相反，如果H設(shè)置比較小時(shí)，局部搜索能力較強(qiáng)，全局搜索能力較低，導(dǎo)致算法收斂速度較慢，而且算法在小區(qū)域內(nèi)搜索，收斂結(jié)果易陷入局部最優(yōu)的錯(cuò)誤解集中.針對以上所述的局限性，本文提出的可變步長果蠅算法（CS-FOA,Change the Step of FOA）將搜索分為若干個(gè)周期，如取50次迭代為一個(gè)周期T，每個(gè)周期內(nèi)步長采用Sin(x)的形式進(jìn)行跌宕變化，表示如下：

其中，L為算法搜索區(qū)間長度，T為單位周期的迭代次數(shù)，mod(i,T)為第i次迭代相對于T取余.

從公式（1）可以看出，CS-FOA首先將整個(gè)搜索過程分為若干個(gè)周期，這樣做可以增加搜索過程的多樣性，使算法能夠有效跳出局部收斂，大大減小局部收斂的可能性.其次CS-FOA在每個(gè)周期內(nèi)采用Sin(x)函數(shù)，使步長在單位周期T內(nèi)可以跌宕變化.在Sin(x)單調(diào)遞增時(shí)，步長指數(shù)型增大，算法具有很強(qiáng)的全局搜索能力，可以實(shí)現(xiàn)快速收斂，并且收斂結(jié)果不易陷入局部最優(yōu)，同時(shí)步長的增大可以解決Sin(x)在上個(gè)單調(diào)遞減區(qū)間內(nèi)可能存在的局部收斂問題.在Sin(x)單調(diào)遞減區(qū)間內(nèi)，步長指數(shù)型減小，可以使算法在小范圍內(nèi)完成高精度的搜索，結(jié)果具有更好的收斂效果.

3 WSN節(jié)點(diǎn)模型

本文采用是網(wǎng)格覆蓋模型[3].在一個(gè)a×b的二維區(qū)域內(nèi)，區(qū)域被離散化為a×b個(gè)接收點(diǎn)，每個(gè)接收點(diǎn)的位置表示為(at,bt).在該目標(biāo)區(qū)域內(nèi)隨機(jī)部署N個(gè)傳感器節(jié)點(diǎn)，節(jié)點(diǎn)覆蓋的額定有效半徑為R.每個(gè)節(jié)點(diǎn)將自身位置發(fā)給Sink節(jié)點(diǎn)，由Sink節(jié)點(diǎn)完成優(yōu)化運(yùn)算.每組傳感器節(jié)點(diǎn)可以表示為：

節(jié)點(diǎn)wi與接收點(diǎn)(ak.bk)距離表示為：

接收點(diǎn)(ak.bk)可以接受到節(jié)點(diǎn)wi信號的概率表示為：

接收點(diǎn)(ak.bk)能接收到這組節(jié)點(diǎn)發(fā)射的信號的概率表示為：

最后，發(fā)射器W對這片區(qū)域的信號覆蓋率表示為：

4 改進(jìn)果蠅算法的應(yīng)用

將CS-FOA應(yīng)用于解決WSN問題的算法步驟如下：

①初始化無線傳感器網(wǎng)絡(luò)相關(guān)參數(shù)，包括區(qū)域長a，寬b，節(jié)點(diǎn)的額定有效覆蓋半徑R，該區(qū)域布置傳感器節(jié)點(diǎn)個(gè)數(shù)N；

②初始化CS-FOA的相關(guān)參數(shù)，包括果蠅種群大小Sizepop，最大迭代次數(shù)Maxgen，單位周期迭代次數(shù)T，搜索區(qū)間長度L；

③隨機(jī)初始Sizepop個(gè)果蠅的位置Wt，根據(jù)式（2），第t個(gè)果蠅的傳感器節(jié)點(diǎn)表示為wt,i=(xt,i,yt,i)，其中t∈[1,Sizepop]，i∈[1,N]；

④根據(jù)式（3）～（6）計(jì)算出GW，將GW最大的果蠅標(biāo)記為最佳果蠅，記錄此果蠅的GW以及位置W：

⑤進(jìn)入迭代尋優(yōu)計(jì)算，果蠅個(gè)體根據(jù)式（7）確定搜索步長，隨機(jī)向各個(gè)方向搜尋.

⑥執(zhí)行步驟④，找出其中覆蓋率最大的果蠅個(gè)體，記錄此果蠅的位置和覆蓋率，并將此果蠅的覆蓋率與上一代最佳果蠅的覆蓋率比較，如果此果蠅覆蓋率大于上一代覆蓋率，那么將此果蠅標(biāo)記為最佳果蠅.最佳果蠅的位置設(shè)為節(jié)點(diǎn)位置，也是下一次搜索的果蠅初始位置，所有果蠅向此果蠅聚攏.

⑦循環(huán)執(zhí)行步驟⑤⑥，直至迭代次數(shù)達(dá)到Maxgen，記錄最終的結(jié)果.此時(shí)得到無線傳感器網(wǎng)絡(luò)最大的覆蓋率bestG和對應(yīng)節(jié)點(diǎn)位置G_axis.

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

5.1實(shí)驗(yàn)參數(shù)設(shè)置

實(shí)驗(yàn)測試平臺 Window XP,Matlab7,機(jī)器主頻為3.3GHz，內(nèi)存為2GB.

在50m×50m的正方形監(jiān)測區(qū)域內(nèi)放置25個(gè)無線傳感器節(jié)點(diǎn)，這些節(jié)點(diǎn)具有位置可移動(dòng)，額定有效半徑固定的特點(diǎn).節(jié)點(diǎn)的額定有效半徑R為5m，通信半徑為2R.

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

圖1 CS-FOA覆蓋節(jié)點(diǎn)分布圖

在上述無線傳感器網(wǎng)絡(luò)模型下，選取了FOA、DS-FOA[4]和本文提出的CS-FOA三種算法，設(shè)迭代次數(shù)Maxgen=200，果蠅種群數(shù)量Sizepop=50,搜索長度L=5m，搜索區(qū)間為[0,50].仿真實(shí)驗(yàn)運(yùn)行50次，最后對實(shí)驗(yàn)結(jié)果進(jìn)行平均.圖4為理論最大覆蓋率的節(jié)點(diǎn)分布圖，理論最大覆蓋率為78.5%.圖5～7分別是上述3種果蠅算法在迭代結(jié)束后的節(jié)點(diǎn)分布圖.在迭代200次后，CS-FOA的覆蓋率為77.12%，達(dá)到理論最大覆蓋率的 98.24%，DS-FOA的覆蓋率為75.03%，達(dá)到理論最大覆蓋率的95.54%，而FOA的覆蓋率為68.28%，達(dá)到理論最大覆蓋率為86.98%.通過比較可以看出，在果蠅優(yōu)化算法和改進(jìn)果蠅算法中，CS-FOA能更好的結(jié)合無線傳感器網(wǎng)絡(luò)模型，在相同參數(shù)的條件下，得到更高的網(wǎng)絡(luò)覆蓋率，問題能夠得到更有效的解決.

圖2 3種果蠅算法收斂比較圖

圖2為在上述無線傳感器網(wǎng)絡(luò)模型下，分別應(yīng)用FOA、DS-FOA和CS-FOA三種果蠅算法對節(jié)點(diǎn)分布尋優(yōu)的覆蓋率變化圖.從圖8可以看出，F(xiàn)OA由于搜索步長固定，所以導(dǎo)致在100次迭代以后，陷入了局部收斂，隨著迭代次數(shù)的增加，算法自身并不能跳出局部收斂，最后結(jié)果的收斂精度不夠理想.DS-FOA由于前期搜索步長過大，所以導(dǎo)致算法的收斂速度太慢，到中期的收斂精度依然不高，影響了收斂的整體進(jìn)度，導(dǎo)致后期的尋優(yōu)收斂起點(diǎn)太差，算法需要更多次的迭代才能達(dá)到一定的效果.相比于FOA和DS-FOA， CS-FOA具有很快收斂速度的同時(shí)，也具有很高的收斂精度.CS-FOA通過步長的周期性和跌宕性變化，在尋優(yōu)周期的前期，隨著步長的增加可以使搜索達(dá)到快速的收斂，很快的接近理論覆蓋率，在尋優(yōu)周期的后期，算法在小范圍內(nèi)搜索，使搜索結(jié)果達(dá)到很高的精度，得到更高的網(wǎng)絡(luò)覆蓋率.

為了驗(yàn)證CS-FOA在無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化問題上的優(yōu)越性，在迭代次數(shù)為200次，覆蓋區(qū)域面積為50m× 50m，節(jié)點(diǎn)額定有效半徑為5m的條件下，選取CS-FOA、改進(jìn)虛擬力粒子群算法[5]（VFPSO）、改進(jìn)蝙蝠算法[6]（BA）、改進(jìn)混沌魚群算法[7]、DS-FOA五種算法進(jìn)行無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化的仿真實(shí)驗(yàn)，取50次實(shí)驗(yàn)的結(jié)果平均值作為結(jié)果.最后得到結(jié)果如表1所示（設(shè)理論覆蓋率為1）.

表1 算法覆蓋率比較表

從表1可以看出，在相同的情況下，相對于其它幾種應(yīng)用在無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化問題上的改進(jìn)優(yōu)化算法，CS-FOA最后得到的網(wǎng)絡(luò)覆蓋率最高，可以得到理論覆蓋率的98.24%，相比DS-FOA、改進(jìn)VFPSO、改進(jìn)BA和改進(jìn)魚群算法，分別提高了2.7%、0.23%、8.98%和1.94%.由于CS-FOA緊密結(jié)合無線傳感器網(wǎng)絡(luò)模型和算法高性能的特點(diǎn)，所以在可移動(dòng)節(jié)點(diǎn)的無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化問題上具有更好的效果.

6 結(jié)束語

針對無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化問題，本文應(yīng)用了一種改進(jìn)的果蠅算法（CS-FOA）.通過對仿真實(shí)驗(yàn)的數(shù)據(jù)展示和分析，可以看出CS-FOA在無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化問題上具有良好的性能（收斂精度和收斂速度），相對于其它幾種應(yīng)用于無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化問題的改進(jìn)智能優(yōu)化算法，本文算法能夠更好的結(jié)合網(wǎng)絡(luò)模型，具有更好的效果和過程更加穩(wěn)定，最后得到更高的網(wǎng)絡(luò)覆蓋率，更適用于無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化.

〔1〕王保云.物聯(lián)網(wǎng)技術(shù)研究綜述[J].電子測量與儀器學(xué)報(bào), 2009(12):1-7.

〔2〕潘文超.果蠅最佳化演算法[M].臺北:滄海書局,2011.10-12.

〔3〕徐躍州,張欣.基于混沌果蠅算法的WSN優(yōu)化布局[J].計(jì)算機(jī)工程與設(shè)計(jì),2015(4).

〔4〕寧劍平,王冰,李洪儒,等.遞減步長果蠅優(yōu)化算法及應(yīng)用[J].深圳大學(xué)學(xué)報(bào)(理工版),2014,31(4):367-373.

〔5〕宋明智,楊樂.改進(jìn)VFPSO算法于WSN節(jié)點(diǎn)隨機(jī)部署中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用,2016,52(2):141-145.

〔6〕袁曦,張曦煌.基于改進(jìn)蝙蝠算法的無線傳感器網(wǎng)絡(luò)的移動(dòng)節(jié)點(diǎn)部署[J].傳感器與微系統(tǒng),2016,35(3):144-146.

〔7〕李顯,劉明生,李燕,等.基于混沌魚群改進(jìn)算法的無線傳感網(wǎng)覆蓋優(yōu)化[J].激光雜志,2015(1):98-101.

TN926；TP393

A

1673-260X（2017）08-0015-03

2017-05-06

本文為安徽省高校自然科學(xué)研究項(xiàng)目“《基于云平臺實(shí)驗(yàn)實(shí)訓(xùn)教學(xué)資源庫系統(tǒng)開發(fā)與應(yīng)用》（12219zrkx2015B02）”的研究成果