付光杰 胡明哲

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

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；節(jié)點分布；人工蜂群算法；貝葉斯預(yù)測算法；覆蓋率

中圖分類號：TP212.9 文獻(xiàn)標(biāo)志碼：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

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

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

1 問題描述

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

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

（5）2 傳統(tǒng)人工蜂群算法

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

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

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

3 貝葉斯預(yù)測人工蜂群算法

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

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

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

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

Step2 雇傭蜂環(huán)節(jié)。雇傭蜂對相應(yīng)蜜源按照式（7）進(jìn)行搜索。完成評價后，對所有蜜源和預(yù)測概率進(jìn)行優(yōu)化更新操作，局部搜索次數(shù)c置0。對于不滿足更新條件的蜜源，則其局部搜索次數(shù)c增加1。

Step3 跟隨蜂環(huán)節(jié)。對照預(yù)測概率產(chǎn)生二級蜜源，并根據(jù)式（9）對所有跟隨蜂進(jìn)行分配。按照式（10）和式（11）對各蜜源進(jìn)行搜索，評價，并完成蜜源、局部搜索次數(shù)的替換更新工作。統(tǒng)計蜜源以及跟隨蜂的數(shù)量。

Step4 蜜源淘汰環(huán)節(jié)。當(dāng)蜜源的數(shù)量超過蜜源數(shù)量上限M時，算法按照上一環(huán)節(jié)所評價的質(zhì)量，淘汰質(zhì)量差的蜜源，直至蜜源數(shù)量滿足要求。隨后獲取現(xiàn)存蜜源的預(yù)測概率向量。并記錄全局最優(yōu)蜜源xbest。

Step5 偵查蜂環(huán)節(jié)。若某一蜜源的局部搜索次數(shù)達(dá)到l，偵查蜂會對蜜源重新進(jìn)行初始化。并更新預(yù)測概率向量。

Step6 若全局迭代次數(shù)t未到達(dá)Gmax，則跳轉(zhuǎn)到Step2；否則，結(jié)束算法運行。

4 實驗仿真

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

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

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

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

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

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

運用BPABC算法對各監(jiān)測區(qū)域中的節(jié)點優(yōu)化部署200次，運行結(jié)果如表2。

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

5 結(jié) 論

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

參考文獻(xiàn)：

[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] 潘麗姣， 吳紅英. 混沌逃逸粒子群優(yōu)化算法在WSN覆蓋優(yōu)化中的應(yīng)用[J]. 重慶郵電大學(xué)學(xué)報（自然科學(xué)版）， 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] 姚勇濤， 吳雪， 吳喆. 基于改進(jìn)的果蠅優(yōu)化算法的WSN節(jié)點部署設(shè)計[J]. 華東理工大學(xué)學(xué)報（自然科學(xué)版）， 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] 王長清， 黃靜. 基于協(xié)同進(jìn)化粒子群算法的無線傳感器網(wǎng)絡(luò)節(jié)能優(yōu)化覆蓋算法[J]. 河南師范大學(xué)學(xué)報（自然版）， 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] 熊偉麗， 劉欣， 陳敏芳，等. 基于差分蜂群算法的無線傳感器網(wǎng)絡(luò)節(jié)點分布優(yōu)化[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] 陳樹， 錢成. 一種多目標(biāo)的覆蓋優(yōu)化策略在WSNs中的應(yīng)用[J]. 傳感器與微系統(tǒng)， 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] 朱志潔， 張宏偉， 王春明. 基于人工蜂群算法優(yōu)化支持向量機(jī)的采場底板破壞深度預(yù)測[J]. 重慶大學(xué)學(xué)報：自然科學(xué)版， 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] 姜允志， 郝志峰， 張宇山， 等. 貝葉斯預(yù)測型進(jìn)化算法[J]. 計算機(jī)學(xué)報， 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）

（編輯 詹燕平）