貝葉斯預測蜂群算法在無線傳感器網絡優化中的應用

付光杰 胡明哲

摘要：針對無線傳感器網絡（WSN，wireless sensor network）節點分布不合理，存在較多的監測盲區等不足，提出了利用貝葉斯預測人工蜂群算法（BPABC，Bayesian predictive artificial bee colony algorithm）制定節點分布方案。BPABC算法借鑒貝葉斯預測算法的思想對蜂群算法中各蜜源存在最優解的概率進行預測，并以此為依據指導跟隨蜂尋優工作。采用BPABC算法對WSN中的節點分布進行優化，與人工蜂群算法、全局人工蜂群算法制定的優化方案進行比較。結果表明，BPABC在平均覆蓋率、最差覆蓋率等方面均優于其他兩種算法，并且BPABC算法在迭代收斂速度方面也有明顯的優勢。為了進一步驗證改進算法的實用性，采用BPABC制定不同監測區域的WSN節點分布方案。WSN的覆蓋率均在97%左右，并且標準差不超過0.005%。由此可見，基于BPABC的WSN節點分布優化方案具有較高的覆蓋率、良好的適應性和穩定性。

關鍵詞：無線傳感器網絡；節點分布；人工蜂群算法；貝葉斯預測算法；覆蓋率

中圖分類號：TP212.9 文獻標志碼：A文章編號：1000-582X（2018）05-015-08

Abstract： The node distribution of wireless sensor network（WSN） is often unreasonable， and always has many monitoring blind spots. Aiming at this problem， Bayesian predictive artificial bee colony algorithm（BPABC） is proposed to develop a node distribution scheme. Based on the idea of Bayesian prediction algorithm， this algorithm predicts the probability of optimal solution of each nectar source in the bee colony algorithm， and guides the followed bees to seek optimal solution. A designed algorithm is used to optimize the distribution of nodes in WSN， and the effect is compared with those of artificial bee colony algorithm and global artificial bee colony algorithm. The results show that BPABC is superior to the other two algorithms in terms of average coverage and worst coverage. Besides， this algorithm also has obvious advantages in iterative convergence rate. In order to further verify the practicability of the improved algorithm， this paper uses BPABC algorithm to develop WSN node distribution scheme for different monitoring areas. Coverage for all WSNs is around 97% with a standard deviation no more than 0.005%. It can be seen that the WSN node distribution optimization scheme based on BPABC has high coverage， good adaptability and stability.

Keywords： wireless sensor network （WSN）； node distribution； artificial bee colony algorithm； Bayesian prediction algorithm； coverage rate

無線傳感器網絡（WSN， wireless sensor network）中存在大量傳感器節點， 其中每個節點的位置均會直接影響WSN的感知能力和工作效率，只有合理部署各節點的位置才能保證WSN對目標區域進行高效穩定的監測[1-3]。因此WSN節點部署算法研究對WSN的發展具有重要意義。文獻[4]將混沌算法與粒子群算法相結合，增強粒子群逃逸局部最優的能力，但運用此種方法收斂速度和平均覆蓋率均不理想。文獻[5]針對WSN節點分布優化問題，以果蠅算法為基礎，改進氣味函數，使其更好地應用于點覆蓋。但此算法中的目標函數需要對ω進行設定，不同的ω對WSN的優化效果有較大影響。文獻[6]所用算法吸取了粒子群算法與協同進化算法的優勢，進一步增強搜索進化能力，由于每次變異交叉操作均采用簡單的隨機方式，因此搜索效率低，尋優速度較慢。文獻[7]采用人工蜂群算法對WSN部署方案進行制定，所得方案覆蓋率高，但收斂速度過慢。文獻[8]將差分進化算法與蜂群算法相結合，增強蜜蜂的搜索能力，可以在短時間內獲取最佳部署方案。

為了更好地優化WSN節點分布，采用覆蓋率較高的傳統人工蜂群算法（ABC，artificial bee colony）作為基礎算法，再借鑒貝葉斯預測算法的思想，在收斂速度方面進行改進，提出貝葉斯預測人工蜂群算法（BPABC， Bayesian prediction artificial bee colony algorithm），并應用此算法制定節點分布方案，再與傳統蜂群算法及全局引導蜂群算法（GABC， global artificial bee colony）的優化方案進行對比，以驗證BPABC算法的優越性。

1 問題描述

在實際應用中，最簡單的WSN節點分布方法是隨機部署，這種方式會出現大量重復覆蓋的區域，造成資源浪費，無法完成預定的監測任務。而經過優化后的部署方案，可以使WSN最大限度地覆蓋監測區域。因此，WSN的節點分布情況會直接影響其對目標區域的監測效果，合理部署其中各節點可以提升WSN的工作性能以及監測能力。此問題具體模型描述如下[9-11]：

設存在二維監測區域A，用于目標區域的WSN中存在N個傳感器節點，每個節點的感知半徑都是r，所有節點可記為{s1，s2，…，sN}。（xi，yi）代表節點si在區域A中的位置坐標。為了方便計算覆蓋率，將目標區域A離散成m×n個點pj，其中m、n分別為橫縱坐標的離散點總數，任意點的坐標為（x，y）。定義節點si與離散點pj之間的距離為d（si，pj）=（xi-x）2+（yi-y）2。

（5）2 傳統人工蜂群算法

人工蜂群算法（ABC，artificial bee colony a lgorithm）是仿照蜜蜂種群中各蜜蜂之間協作搜尋蜜源的過程而演化成的一種智能算法[12]。此種算法將蜂群中的蜜蜂劃分為雇傭蜂、跟隨蜂、偵查蜂3類。3種蜜蜂相互配合搜索最優蜜源。算法中的蜜源為優化問題的可行解。

傳統ABC算法采用輪盤賭概率法反映各蜜源的狀態，跟隨蜂以此為依據對蜜源進行搜索更新。若算法運行過程中某一蜜源的局部搜索次數達到l（l為單個蜜源的最大搜索次數），則認為在這個蜜源的鄰域內不存在適應度更好的蜜源，偵查蜂將舍棄該蜜源并按照式（6）重新獲取新蜜源。

通過以上的分析可以得出，由于傳統人工蜂群算法每次搜索只改變一個維度的元素，因此需要大量的迭代才能找到最優解，導致收斂速度過慢。除此之外，每次搜索都是以單純的隨機函數方式對元素進行更新，導致在搜索過程中產生大量較差的可行解，浪費計算資源，降低搜索效率。

3 貝葉斯預測人工蜂群算法

針對傳統蜂群算法搜索效率低，收斂速度慢等缺陷，文中算法借鑒文獻[16]中的貝葉斯預測算法思想，對蜂群算法進行改進。首先需要對傳統蜂群算法中的蜂群數量進行調整，在傳統蜂群算法中，雇傭蜂和跟隨蜂的數量是相等的，以滿足所有蜜源的更新需求。在此算法中，設置少量初始雇傭蜂，其數量為a。雇傭蜂的更新公式與傳統蜂群算法相同。跟隨蜂的數量為b，其包括兩部分：一部分用于局部搜索（b1）；另一部分在搜索過程中當滿足一定條件可轉化為雇傭蜂（b2）。

在算法運行過程中，當某個蜜源的預測概率超過50%時，BPABC算法對蜜源劃分成2個二級蜜源進行分區搜索，每個蜜源的預測概率均為原來的1/2，并且更新公式不變，只是2個二級蜜源的α取值與先前不同，分別為-1～0和0～1的隨機數。篩選每個二級蜜源附近適應度函數值最好的跟隨蜂作為新的蜜源，若此蜜源附近所有跟隨蜂的結果均不如劃分前的蜜源，則保留原來的原蜜源結果與預測概率，局部搜索次數加1。

貝葉斯預測蜂群算法具體運行流程如下：

Step1 初始化。對算法中的各參數進行設定，并初始化雇傭蜂搜索的蜜源，各蜜源的先驗概率均設置為1/a。對每個蜜源進行評價并獲得后驗概率。按照式（6）計算初始蜜源的預測概率向量。

Step2 雇傭蜂環節。雇傭蜂對相應蜜源按照式（7）進行搜索。完成評價后，對所有蜜源和預測概率進行優化更新操作，局部搜索次數c置0。對于不滿足更新條件的蜜源，則其局部搜索次數c增加1。

Step3 跟隨蜂環節。對照預測概率產生二級蜜源，并根據式（9）對所有跟隨蜂進行分配。按照式（10）和式（11）對各蜜源進行搜索，評價，并完成蜜源、局部搜索次數的替換更新工作。統計蜜源以及跟隨蜂的數量。

Step4 蜜源淘汰環節。當蜜源的數量超過蜜源數量上限M時，算法按照上一環節所評價的質量，淘汰質量差的蜜源，直至蜜源數量滿足要求。隨后獲取現存蜜源的預測概率向量。并記錄全局最優蜜源xbest。

Step5 偵查蜂環節。若某一蜜源的局部搜索次數達到l，偵查蜂會對蜜源重新進行初始化。并更新預測概率向量。

Step6 若全局迭代次數t未到達Gmax，則跳轉到Step2；否則，結束算法運行。

4 實驗仿真

研究采用Matlab編寫算法對貝葉斯預測蜂群算法的運行效果進行測試，并對其應用于WSN節點分布優化方面的優越性進行驗證。將BPABC、GABC、ABC 3種算法的優化結果進行對比。設WSN中存在60個完全相同的傳感器節點，其感知半徑皆為20 m。為了突顯BPABC的算法性能，因此這里隨機對算法的參數進行設定，預設的參數如下：a=20，b=80（其中b1=60，b2=20），l=20，Gmax=500。WSN應用于200 m×200 m的監測區域中。其他2種算法相關參數與上述參數相同，3種算法分別運行200次，運行結果如表1所示。

由表1可知，經過多次實驗，基于BPABC算法的WSN可以覆蓋目標區域97%左右的面積，此種算法最差的覆蓋結果也可達95%以上。在尋優速度方面，BPABC可以在大約166次時得到最優分布方案。對比其他2種算法可知，BPABC算法在以上這些方面具有明顯的優勢。3種算法的迭代優化曲線如圖1所示。

由圖1可知，相比于ABC、GABC算法，BPABC算法能夠在最短時間內獲取最佳節點分布方案，并且此方案的覆蓋率同樣優于其他2種算法。除此之外，運用BPABC算法覆蓋率大致保持增長趨勢，有效地擺脫局部最優的狀態。因此，綜上所述，應用BPABC算法可以更好地完成節點優化任務。

采用BPABC算法制定的WSN節點分布方案如圖2所示。對比2圖可知，若不對節點分布進行規劃則會出現大量的監測重疊區域（如圖2（a）），降低WSN的工作效率。采用BPABC算法對節點分布進行優化（如圖2（b）），優化結果顯示，每個節點分布較為合理，覆蓋盲區較少，大幅度提升WSN的監測性能。

為了進一步檢測BPABC算法的性能，采用3種算法對節點數目不同的WSN進行優化，在節點數目不同時，3種算法的覆蓋率變化如圖3所示。當WSN中節點不充足時，對比3種算法生成的方案，節點之間的覆蓋區域幾乎不存在交集，因此3種方案具有相似的覆蓋率。3種優化算法的覆蓋率隨著節點數目的增加而增加，增加速率逐漸變小，但BPABC的優化效果始終優于其他2種，并且當節點數達到60時，BPABC算法的優勢體現得更加明顯。

以上分析結果皆針對正四邊形監測區域，為了驗證文中所用算法的推廣價值，將BPABC算法應用于與上述監測面積相同的正三角形、矩形、正五邊形、正六邊形監測區域。經過算法優化后，各監測區域的節點分布圖如圖4所示。

運用BPABC算法對各監測區域中的節點優化部署200次，運行結果如表2。

根據以上的數據和分布圖可知，經過BPABC算法優化后的節點部署方案對各監測區域具有較高的覆蓋率，雖然運用ABC、GABC算法同樣能實現較均勻部署，但覆蓋率方面仍然不如BPABC算法制定的方案。通過仿真對比，BPABC算法對任意區域的平均覆蓋率和最差覆蓋率均可達到95%以上。且覆蓋率的標準差不超過0.005。這說明采用BPABC算法具有很強的適應性和較高的穩定性，在進行節點分布優化時可以不受監測區域形狀的影響，只與其面積有關。因此將BPABC算法應用于WSN節點分布優化問題具有一定的推廣價值。

5 結 論

針對WSN網絡節點優化問題提出了BPABC算法，此種算法引入貝葉斯預測算法思想，預測人工蜂群算法中各蜜源存在最優解的概率，根據所得的預測結果對各蜜源進行有針對性地搜索，有效地提高了搜索效率。對BPABC算法進行編程仿真，仿真實驗表明，BPABC算法可以在較少的迭代次數下獲取高覆蓋率的節點分布方案，并且對于任意監測區域均可制定滿足監測需求的方案，由此可見，算法具有良好的適應性。未來可以根據實際需求在算法中增加其他優化目標函數，使優化后的方案更好地在實際中進行應用。

參考文獻：

[1] Benatia M A， Sahnoun M， Baudry D， et al. Multi-objective WSN deployment using genetic algorithms under cost， coverage， and connectivity constraints[J]. Wireless Personal Communications， 2017：1-30.

[2] Yang H， Xunbo L I， Wang Z， et al. A novel sensor deployment method based on image processing and wavelet transform to optimize the surface coverage in WSNs[J]. Chinese Journal of Electronics， 2016， 25（3）：495-502.

[3] Cong C. A coverage algorithm for WSN based on the improved PSO[C]// International Conference on Intelligent Transportation， Big Data and Smart City. [S.l.]：IEEE， 2015：12-15.

[4] 潘麗姣， 吳紅英. 混沌逃逸粒子群優化算法在WSN覆蓋優化中的應用[J]. 重慶郵電大學學報（自然科學版）， 2014， 26（2）：177-181.

PAN Lijiao， WU Hongying. Application of chaotic escape particle swarm optimization algorithm in coverage optimization of wireless sensor networks[J]. Journal of Chongqing University of Posts and Telecommunications（Natural Science Edition）， 2014， 26（2）： 177-181. （in Chinese）

[5] 姚勇濤， 吳雪， 吳喆. 基于改進的果蠅優化算法的WSN節點部署設計[J]. 華東理工大學學報（自然科學版）， 2016， 42（4）：545-551.

YAO Yongtao， WU Xue， WU Zhe. Wireless sensor network node deployment design based on improved fruit fly optimization algorithm[J]. Journal of East China University of Science and Technology（Natural Science Edition）， 2016， 42（4）： 545-551.（in Chinese）

[6] 王長清， 黃靜. 基于協同進化粒子群算法的無線傳感器網絡節能優化覆蓋算法[J]. 河南師范大學學報（自然版）， 2016， 44（1）：54-58.

WANG Changqing， HUANG Jing. Energy-saving coverage algorithm for wireless sensor network based on co-evolutionary particle swarm optimization[J]. Journal of Henan Normal University（Natural Science Edition）， 2016， 44（1）： 54-58. （in Chinese）

[7] Xu X， Zhou G， Chen T. Research on coverage optimisation of wireless sensor networks based on an artificial bee colony algorithm[M]. Geneva： Inderscience Publishers， 2015.

[8] 熊偉麗， 劉欣， 陳敏芳，等. 基于差分蜂群算法的無線傳感器網絡節點分布優化[J]. 控制工程， 2014， 21（6）：1036-1040.

XIONG Weili， LIU Xin， CHEN Minfang， et al. Node distribution optimization in wireless sensor networks based on differential bee colony algorithm[J]. Control Engineering of China， 2014， 21（6）：1036-1040. （in Chinese）

[9] Yang H， Li X， Wang Z， et al. A novel sensor deployment method based on image processing and wavelet transform to optimize the surface coverage in WSNs[J]. Chinese Journal of Electronics， 2016， 25（3）：495-502.

[10] Guo Y N， Cheng J， Liu H Y， et al. A novel knowledge-guided evolutionary scheduling strategy for energy-efficient connected coverage optimization in WSNs[J]. Peer-to-Peer Networking and Applications， 2017， 10（3）：547-558.

[11] 陳樹， 錢成. 一種多目標的覆蓋優化策略在WSNs中的應用[J]. 傳感器與微系統， 2014， 33（10）：151-154.

CHEN Shu， QIAN Cheng. Application of a multi-objective coverage optimization strategy in WSNs[J]. Transducer and Microsystem Technologies， 2014， 33（10）： 151-154. （in Chinese）

[12] 朱志潔， 張宏偉， 王春明. 基于人工蜂群算法優化支持向量機的采場底板破壞深度預測[J]. 重慶大學學報：自然科學版， 2015， 38（6）：37-43.

ZHU Zhijie， ZHANG Hongwei， WANG Chunming. Prediction of floor damaged depth in working area based on support vector machine and artificial bee colony algorithm[J]. Journal of Chongqing University. 2015， 38（6）： 37-43. （in Chinese）

[13] Kiran M S， Hakli H， Gunduz M， et al. Artificial bee colony algorithm with variable search strategy for continuous optimization[J]. Information Sciences， 2015， 300（S）：140-157.

[14] Brajevic I. Crossover-based artificial bee colony algorithm for constrained optimization problems[J]. Neural Computing & Applications， 2015， 26（7）：1587-1601.

[15] Maeda M， Tsuda S. Reduction of artificial bee colony algorithm for global optimization[J]. Neurocomputing， 2015， 148（33）：70-74.

[16] 姜允志， 郝志峰， 張宇山， 等. 貝葉斯預測型進化算法[J]. 計算機學報， 2014， 37（8）：1846-1858.

JIANG Yunzhi， HAO Zhifeng， ZHANG Yushan， et al. Bayesian forecasting evolutionary algorithm[J]. Chinese Journal of Computers， 2014， 37（8）： 1846-1858. （in Chinese）

（編輯 詹燕平）