基于周期果蠅算法的無線傳感網覆蓋優化

尹向兵，吳良超

（1.安徽警官職業學院 教務處，安徽 合肥 230031；2.安徽大學 計算智能與信號處理重點實驗室，安徽 合肥 230039）

基于周期果蠅算法的無線傳感網覆蓋優化

尹向兵1，吳良超2

（1.安徽警官職業學院 教務處，安徽 合肥 230031；2.安徽大學 計算智能與信號處理重點實驗室，安徽 合肥 230039）

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

WSN；果蠅算法；傳感器節點；覆蓋優化

1 引言

無線傳感器網絡[1]是一種分布式傳感，面對多節點、多任務的無線自組織網絡.無線傳感器網絡是由大量部署在監測區域內的傳感器節點組成，通過傳感器節點對監測區域的信息進行實時收集.WSN作為一門新的技術，被廣泛應用于軍事領域、農業生產、生態監測與災害預警、基礎設施狀態檢測、工業領域、智能家居等.傳感器網絡的一個關鍵問題就是節點的部署優化，對于如何提高網絡的覆蓋率、降低網絡的能耗、簡化網絡模型，最終提高服務質量，這是目前研究的一大熱門問題，也是未來無線傳感技術發展的基礎.

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

2 果蠅算法

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

2.1 基本果蠅算法：

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

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

②果蠅個體隨機向各個方向的位置進行搜尋.

③計算果蠅個體與原點距離d,再將距離的倒數做為果蠅個體的味道濃度判定值Si.

④將味道濃度判定值 Si代入適應度函數（Fitness function），求出果蠅個體的味道濃度.

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

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

⑦開始迭代，重復執行②～⑤，并判斷最佳味道濃度是否優于前一次迭代得到的味道濃度，并且當前迭代次數小于最大迭代數Maxgen,則執行⑥，否則，算法結束.

2.2 改進步長果蠅算法

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

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

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

3 WSN節點模型

本文采用是網格覆蓋模型[3].在一個a×b的二維區域內，區域被離散化為a×b個接收點，每個接收點的位置表示為(at,bt).在該目標區域內隨機部署N個傳感器節點，節點覆蓋的額定有效半徑為R.每個節點將自身位置發給Sink節點，由Sink節點完成優化運算.每組傳感器節點可以表示為：

節點wi與接收點(ak.bk)距離表示為：

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

接收點(ak.bk)能接收到這組節點發射的信號的概率表示為：

最后，發射器W對這片區域的信號覆蓋率表示為：

4 改進果蠅算法的應用

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

①初始化無線傳感器網絡相關參數，包括區域長a，寬b，節點的額定有效覆蓋半徑R，該區域布置傳感器節點個數N；

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

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

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

⑤進入迭代尋優計算，果蠅個體根據式（7）確定搜索步長，隨機向各個方向搜尋.

⑥執行步驟④，找出其中覆蓋率最大的果蠅個體，記錄此果蠅的位置和覆蓋率，并將此果蠅的覆蓋率與上一代最佳果蠅的覆蓋率比較，如果此果蠅覆蓋率大于上一代覆蓋率，那么將此果蠅標記為最佳果蠅.最佳果蠅的位置設為節點位置，也是下一次搜索的果蠅初始位置，所有果蠅向此果蠅聚攏.

⑦循環執行步驟⑤⑥，直至迭代次數達到Maxgen，記錄最終的結果.此時得到無線傳感器網絡最大的覆蓋率bestG和對應節點位置G_axis.

5 仿真實驗

5.1實驗參數設置

實驗測試平臺 Window XP,Matlab7,機器主頻為3.3GHz，內存為2GB.

在50m×50m的正方形監測區域內放置25個無線傳感器節點，這些節點具有位置可移動，額定有效半徑固定的特點.節點的額定有效半徑R為5m，通信半徑為2R.

5.2 實驗結果分析

圖1 CS-FOA覆蓋節點分布圖

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

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

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

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

表1 算法覆蓋率比較表

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

6 結束語

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

〔1〕王保云.物聯網技術研究綜述[J].電子測量與儀器學報, 2009(12):1-7.

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

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

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

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

〔6〕袁曦,張曦煌.基于改進蝙蝠算法的無線傳感器網絡的移動節點部署[J].傳感器與微系統,2016,35(3):144-146.

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

TN926；TP393

A

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

2017-05-06

本文為安徽省高校自然科學研究項目“《基于云平臺實驗實訓教學資源庫系統開發與應用》（12219zrkx2015B02）”的研究成果