基于協(xié)同進化蜂群算法的覆蓋優(yōu)化策略

張 騫，李克清，戴 歡，劉 帥

（1.中國礦業(yè)大學計算機科學與技術(shù)學院，江蘇徐州221116；2.常熟理工學院計算機科學與工程學院，江蘇常熟215500）

0 引 言

無線傳感器網(wǎng)絡(luò)（wireless sensor networks，WSN）由不同類型的傳感器節(jié)點構(gòu)成，被廣泛應(yīng)用于軍事、環(huán)境監(jiān)測等領(lǐng)域。WSN的性能取決于傳感器部署后，節(jié)點對監(jiān)測區(qū)域的有效覆蓋面積。移動節(jié)點使得傳感器動態(tài)部署成為可能，在傳感器動態(tài)部署中，隨機部署傳感器節(jié)點，然后使用覆蓋優(yōu)化策略優(yōu)化調(diào)整移動節(jié)點位置，重組WSN的布局，擴大對監(jiān)測區(qū)域的有效覆蓋，提高WSN的監(jiān)測能力，有利于提高WSN的工作效率。

為了提高監(jiān)測區(qū)域覆蓋率，近年來，研究人員提出了許多行之有效的覆蓋優(yōu)化策略［1－4］。文獻［5，6］使用人工蜂群（artificial bee colony，ABC）算法優(yōu)化網(wǎng)絡(luò)布局，也取得了較好的效果。人工蜂群算法是模擬蜜蜂采蜜行為的智能群算法，具有控制參數(shù)少，健壯性的優(yōu)點［7］，可以解決連續(xù)、組合優(yōu)化問題，已成功應(yīng)用到神經(jīng)網(wǎng)絡(luò)的訓練［8］、求解約束優(yōu)化問題［9］等領(lǐng)域，且取得了良好的效果。但與其他智能群算法一樣，ABC算法也存在早熟成熟、后期收斂速度變慢的缺點［10］。

本文基于文獻［11］中協(xié)同進化人工蜂群（cooperative to artificial bee colony，CABC）的思想，增加解決方案的多樣性，提高收斂速度，搜索移動節(jié)點的最優(yōu)位置，重組網(wǎng)絡(luò)布局。針對節(jié)點在移動過程中的路徑繞遠現(xiàn)象，基于貪婪法，提出一種移動路徑優(yōu)化策略。

1 覆蓋模型與問題描述

1.1 覆蓋模型

假設(shè)WSN監(jiān)測區(qū)域為二維平面A，在該區(qū)域上有N個傳感器，節(jié)點坐標已知，且所有節(jié)點性能一致。為了保證WSN的連通性，通信半徑C設(shè)為感知半徑r的兩倍，即C＝2r。所有節(jié)點集合表示為S｛S1，S2，…，SN｝，其中Si＝｛xi，yi，r｝，Si是以（xi，yi）為圓心，r為監(jiān)測半徑的傳感器節(jié)點。對監(jiān)測區(qū)域A進行離散化，得m×n個網(wǎng)格點，離散化的精度（即網(wǎng)格的邊長）由求解問題的精度決定。假設(shè)網(wǎng)格點Q的坐標為（x，y），則Q與節(jié)點Si的距離為d（Si，Q）。在布爾模型中，則節(jié)點Si對目標Q的監(jiān)測概率由式（1）得

在實際環(huán)境中，由于受到噪聲等因素的干擾，傳感器節(jié)點測量模型呈現(xiàn)出某種特性的概率分布，即

其中，re（0＜re＜r）是傳感器節(jié)點測量可靠性參數(shù)α1，β1，β2為監(jiān)測概率度量參數(shù)，α2為擾動因子，λ1＝re－r＋d（Si，Q），λ2＝re＋r－d（Si，Q）。因此對點的監(jiān)測概率可能小于1，為了提高目標點的檢測概率，通常采用多個傳感器節(jié)點聯(lián)合測量，概率如下

網(wǎng)格點Q被有效覆蓋的評測標準其中cth是有效覆蓋閾值。

1.2 區(qū)域覆蓋率

節(jié)點集S對監(jiān)測區(qū)域A的覆蓋率定義為節(jié)點集覆蓋面積的總和與區(qū)域A總面積之比。A離散化為m×n網(wǎng)格點，每個網(wǎng)格點是否被覆蓋可用式（4）衡量，則問題簡化為有效覆蓋的網(wǎng)格點數(shù)count與m×n的比值，即

1.3 覆蓋問題描述

假設(shè)監(jiān)測區(qū)域A為邊長10×10的正方形，離散化為10×10個網(wǎng)格點，并在該區(qū)域隨機部署20個傳感器節(jié)點，如圖1所示，圖1中使用＊表示節(jié)點位置，計算覆蓋率方法如下:

（1）利用式（2），式（3），式（4）評估傳感器節(jié)點集對一個網(wǎng)格點的有效覆蓋。

（2）重復(fù)步驟（1）統(tǒng)計被有效覆蓋網(wǎng)格點數(shù)count。

（3）通過式（5）計算得出覆蓋率，并把式（5）作為覆蓋優(yōu)化問題的目標函數(shù)。

圖1 監(jiān)測區(qū)域二維圖

基于離散化的評估方法具有易于理解、容易實現(xiàn)的優(yōu)點，但是該法也存在耗時較長的缺點，并且耗時隨離散化的精度的提高而增加，增大了傳感器節(jié)點的能量消耗。針對WSN通常由大量固定節(jié)點與少量移動節(jié)點構(gòu)成的特點，本文采用分步計算區(qū)域覆蓋率的方法，在隨機部署傳感器節(jié)點階段，先行計算出固定節(jié)點的區(qū)域覆蓋率，在移動節(jié)點位置優(yōu)化時，只需要再計算移動節(jié)點對于剩余區(qū)域的覆蓋率，最后相加求出區(qū)域覆蓋率。通過分步計算，可以節(jié)省大量重復(fù)計算時間，提高了運行效率。

2 協(xié)同進化人工蜂群算法

人工蜂群算法是模擬蜜蜂采蜜行為的智能群算法，與其他智能群算法一樣，ABC算法也存在早熟、后期收斂速度變慢的現(xiàn)象。假設(shè)食物源向量為D維，一個解向量雖然可能不是最優(yōu)解，但是它其中的某些維可能是最優(yōu)解，ABC算法使用式（8）得到新的食物源Vi，然后在Xi和Vi中使用貪婪法則進行選擇，另一個直接丟棄，這種做法可能導致部分最優(yōu)解丟失。CABC算法引入向量分割技術(shù)，把一個D維食物源向量劃分為D個一維向量，如圖2所示，將Xk（x1，x2，…，xD）劃分成D個一維向量，并把第i個一維向量分配給蜂巢i的食物源k，形成D個蜂巢，多個蜂巢間協(xié)同進化，每個蜂巢優(yōu)化解向量的一維。

適應(yīng)度函數(shù)f（x）的輸入條件是D維向量，而Ck.Xi為一維向量，對于Ck.Xi的適應(yīng)值，需要引進拼接函數(shù)b，把Ck.Xi和其余蜂巢的最好食物源組合成D維向量

其中Ci.Y表示蜂巢i的最好食物源Y。

圖2 向量分割

3 基于CABC的網(wǎng)絡(luò)覆蓋優(yōu)化策略

WSN的移動節(jié)點位置優(yōu)化可以看成以移動節(jié)點位置構(gòu)成的解向量為輸入，網(wǎng)絡(luò)有效覆蓋面積為目標的優(yōu)化問題。假設(shè)網(wǎng)絡(luò)由s個固定節(jié)點和m個移動節(jié)點構(gòu)成。解向量對應(yīng)移動節(jié)點的位置（x1，y1，x2，y2，…，xm，ym），其中x1，y1是移動傳感器i的橫坐標、縱坐標，解向量的維數(shù)為2 m，網(wǎng)格評估法作為優(yōu)化目標函數(shù)，使用CABC搜索最優(yōu)解，即移動節(jié)點的最佳位置。

下面給出CABC的網(wǎng)絡(luò)覆蓋優(yōu)化策略:

（1）初始化參數(shù):監(jiān)測半徑r，監(jiān)測區(qū)域A大小，靜態(tài)節(jié)點數(shù)s，移動節(jié)點數(shù)m，蜂巢大小cs，最大迭代次數(shù)cycleMax，探尋閾值limit。

（2）隨機部署靜態(tài)節(jié)點，使用網(wǎng)格評估法f（x）評估監(jiān)測區(qū)域的有效覆蓋率。

（3）隨機使用式（7）生成解向量Xi，i＝1，2，…，cs/2

其中，Xij代表解向量i的j維，lb是監(jiān)測區(qū)域的下界，ub是監(jiān)測區(qū)域的上界。

（4）使用向量分割技術(shù)分Xi，i＝1，2，…，cs/2，并計算Ci.Xk的適應(yīng)度，記錄Ci的最好解向量Y，生成完整解sol＝（C1.Y，…，C2m.Y）

REPEAT

FOR Ck，k＝1，2，…，2 m do

使用式（8）產(chǎn)生一個新的解向量Vi，判斷Vij否脫離監(jiān)測區(qū)域，若脫離，則重新生成Vij，使用貪婪法則在Xi，Vi進行選擇

其中，解向量Xk是解向量Xi的鄰居（k≠i），φ是［－1，1］之間的隨機數(shù)。

使用式（9）計算解向量Xi的概率，若rand（0，1）＜Pi，則選中Xi，使用式（9）生成Vi并判斷是否脫離邊界，若脫離，則重新生成Vij，使用貪婪法則在Xi，Vi進行選擇

如果一個解向量的勘探次數(shù)達到閾值limit，則拋棄它，并使用式（7）生成新的解向量，并計算其適應(yīng)度。

記錄目前出現(xiàn)最好解向量Y。

（5）產(chǎn)生新的完整解newsol＝（C1.Y，…，C2m.Y），使用f（x）評估newsol，若比sol好，則更新完整解。

END FOR

UTILL滿足最大迭代次數(shù)cycleMax

4 移動路徑優(yōu)化策略

移動節(jié)點使得動態(tài)部署成為可能，在節(jié)點隨機部署后，可以根據(jù)覆蓋優(yōu)化策略調(diào)整移動節(jié)點位置，增大有效覆蓋面積，提高網(wǎng)絡(luò)性能，但在移動節(jié)點移動過程中普遍存在的路徑繞遠現(xiàn)象，增加了能量的消耗。路徑繞遠現(xiàn)象如圖3所示，節(jié)點1、節(jié)點2的初始位置距離移動位置較遠，但節(jié)點1的初始位置距離節(jié)點2的移動位置很近、節(jié)點2的初始位置距離節(jié)點1的移動位置很近，如果盲目移動，會造成許多不必要能量消耗，這對于傳感器節(jié)點來說是致命的。通過節(jié)點1移動到節(jié)點2的移動位置、節(jié)點2移動到節(jié)點1的移動位置，減少了移動距離，節(jié)省能量消耗，提高整個網(wǎng)絡(luò)的生存時間。

圖3 移動路徑繞遠

針對上述現(xiàn)象，基于貪婪法提出移動路徑優(yōu)化策略。移動路徑優(yōu)化策略描述如下:針對一個傳感器，尋找它到可移動位置里最短距離的位置，選中，在可移動位置中標記，然后依次類推，尋找下一個傳感器的最短距離的移動位置。

5 仿真實驗分析

為了驗證CABC覆蓋優(yōu)化策略的收斂效果，與ABC、微粒群（particle swam optimization，PSO）覆蓋優(yōu)化策略做了對比實驗。仿真環(huán)境:matlab 2012，以下實驗均獨立運行100次求平均值。

圖4 傳感器節(jié)點分布

在監(jiān)測區(qū)域面積10000 m2，即邊長100 m的正方形區(qū)域中，部署30個靜態(tài)節(jié)點、20個移動節(jié)點，檢測半徑12m，使用概率模型，re＝0.5r＝6，α1＝1，α2＝0，β1＝1，β2＝0.5，cth＝0.7。PSO參數(shù):種群大小20，c1＝c2＝1；ABC參數(shù):蜂巢大小cs＝20（雇傭蜂數(shù)、食物源數(shù)＝cs/2），limit＝100；CABC參數(shù):cs＝20，limit＝100；迭代次數(shù)1000。圖4（a）是固定節(jié)點隨機部署后的位置，覆蓋率為38.08%，圖4（b）是使用PSO算法優(yōu)化后的節(jié)點位置，圖4（c）是使用ABC算法優(yōu)化后的節(jié)點位置，圖4（d）是使用CABC算法優(yōu)化后的節(jié)點位置，可以看出CABC覆蓋優(yōu)化策略明顯優(yōu)于PSO、ABC覆蓋優(yōu)化策略。

為了進一步驗證CABC覆蓋優(yōu)化策略的性能，對PSO、ABC、CABC的收斂速度進行比較，圖5是PSO、ABC、CABC覆蓋率收斂曲線，顯然CABC要優(yōu)于ABC、PSO。CABC只需迭代至20代左右就能快速收斂到82.17%，PSO、ABC直至1000代還沒完成搜索過程。

將PSO、ABC、CABC策略分別獨立運行100次，其平均有效覆蓋率如表1所示，CABC優(yōu)化后覆蓋率達到82.17%，較PSO、ABC分別提高了13.94%、12.18%，其原因是，CABC覆蓋優(yōu)化策略顯著地增加了解向量的多樣性，提高了魯棒性和全局搜索能力，而ABC、PSO算法陷入局部最優(yōu)解。

圖5 PSO、ABC、CABC覆蓋率收斂曲線

表1 PSO、ABC、CABC策略對比

移動節(jié)點部署后可以通過移動，提高有效覆蓋面積，顯然，在總節(jié)點數(shù)不變下，移動節(jié)點越多優(yōu)化后有效覆蓋面積越大，但移動節(jié)點造價較高，不適用于大量使用?？偣?jié)點數(shù)50，CABC策略參數(shù)不變，獨立運行100次。實驗結(jié)果見圖6，隨移動節(jié)點比例增大覆蓋率逐漸增大。

圖6 移動節(jié)點比例覆蓋率收斂

移動路徑的長度反映能量的消耗，長度越短消耗能量越少。為了驗證移動路徑優(yōu)化策略的效果，對比PSO、ABC、CABC使用策略之前和之后的節(jié)點平均移動距離。實驗環(huán)境不變，獨立運行100次，移動節(jié)點平均移動距離如表2所示，移動路徑優(yōu)化策略大大降低移動距離，減少了能量的消耗。使用了路徑優(yōu)化的CABC網(wǎng)絡(luò)覆蓋優(yōu)化策略節(jié)點平均移動距離小于PSO、ABC策略。

表2 移動節(jié)點平均移動距離

6 結(jié)束語

動態(tài)部署是WSN的關(guān)鍵問題之一，通過改變移動節(jié)點的位置重組網(wǎng)絡(luò)，有效提高了WSN的覆蓋率。本文提出的CABC覆蓋優(yōu)化策略，以網(wǎng)絡(luò)覆蓋率為優(yōu)化目標，搜索移動節(jié)點最優(yōu)位置，提高網(wǎng)絡(luò)有效覆蓋面積，并提出移動路徑優(yōu)化策略，降低能量消耗。經(jīng)仿真表明，CABC覆蓋優(yōu)化策略較PSO、ABC策略分別提高了12.66%、13.56%的覆蓋率，使用移動路徑優(yōu)化策略后節(jié)點移動距離減少，降低了能量的消耗，延長了網(wǎng)絡(luò)生存時間。

［1］Zou Y，Chakrabarty K.Sensor deployment and target localization based on virtual forces［C］//Twenty－Second Annual Joint Conference of the IEEE Computer and Communications，2003:1293－1303.

［2］WANG Xue，WANG Sheng，MA Junjie.Parallel particle swarm optimization basedmobile sensor node deployment in wireless sensor networks［J］.Chinese Journal of Computers，2007（4）:563－568（in Chinese）.［王雪，王晟，馬俊杰.無線傳感網(wǎng)絡(luò)移動節(jié)點位置并行微粒群優(yōu)化策略［J］.計算機學報，2007（4）:563－568.］

［3］WANG Xue，WANG Sheng，MA Junjie.Dynamic sensor deployment strategy based on virtual force－directed particle swarm optimization in wireless sensor networks［J］.ELEC Journal，2007（11）:2038－2042（in Chinese）.［王雪，王晟，馬俊杰.無線傳感網(wǎng)絡(luò)布局的虛擬力導向微粒群優(yōu)化策略［J］.電子學報，2007（11）:2038－2042.］

［4］WANG Xue，WANG Sheng，MA Junjie.An improved co－evolutionary particle swarm optimization for wireless sensor networks with dynamic deployment［J］.Sensors，2007，7（3）:354－370.

［5］HU Ke.Application research of wireless sensor network coverage optimization strategy based on artificial bee colony algorithm［D］.Chengdu:Electronic Science and Technology，2012（in Chinese）.［胡珂.基于人工蜂群算法在無線傳感網(wǎng)絡(luò)覆蓋優(yōu)化策略中的應(yīng)用研究［D］.成都:電子科技大學，2012.］

［6］Ozturk C，Karaboga D，Gorkemli B.Probabilistic dynamic deployment of wireless sensor networks by artificial bee colony algorithm［J］.Sensors，2011，11（6）:6056－6065.

［7］Karaboga D，Basturk B.On the performance of artificial bee colony（ABC）algorithm［J］.Applied Soft Computing，2008，8（1）:687－697.

［8］LUO Bin，SHAO Peiji，LUO Jinyao，et al.Customer churn research based on multiple classifier fusing rough sets－neural network－artificial bee colony algorithm［J］.Management，2011（2）:265－272（in Chinese）.［羅彬，邵培基，羅盡堯，等.基于粗糙集理論－神經(jīng)網(wǎng)絡(luò)－蜂群算法集成的客戶流失研究［J］.管理學報，2011（2）:265－272.］

［9］WANG Xiang，ZHENG Jianguo.A multi－member artificial bee colony algorithm for constrained optimization problems［J］.Xi'an Jiaotong University，2012（2）:38－44（in Chinese）.［王翔，鄭建國.求解約束優(yōu)化問題的多成員人工蜂群算法［J］.西安交通大學學報，2012（2）:38－44.］

［10］ZHANG Chaoqun，ZHENG Jianguo，WANG Xiang.Overview of research on bee colony algorithms［J］.Application Research of Computers，2011，28（9）:3201－3205（in Chinese）.［張超群，鄭建國，王翔.蜂群算法研究綜述［J］.計算機應(yīng)用研究，2011，28（9）:3201－3205.］

［11］El Abd M.A cooperative approach to the artificial bee colony algorithm［C］//IEEE Congress on Evolutionary Computation，2010:1－5.