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

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

0 引 言

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

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

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

1 覆蓋模型與問題描述

1.1 覆蓋模型

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

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

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

網(wǎng)格點(diǎn)Q被有效覆蓋的評(píng)測(cè)標(biāo)準(zhǔn)其中cth是有效覆蓋閾值。

1.2 區(qū)域覆蓋率

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

1.3 覆蓋問題描述

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

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

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

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

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

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

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

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

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

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

圖2 向量分割

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

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

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

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

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

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

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

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

REPEAT

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

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

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

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

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

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

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

END FOR

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

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

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

圖3 移動(dòng)路徑繞遠(yuǎn)

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

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

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

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

在監(jiān)測(cè)區(qū)域面積10000 m2，即邊長(zhǎng)100 m的正方形區(qū)域中，部署30個(gè)靜態(tài)節(jié)點(diǎn)、20個(gè)移動(dòng)節(jié)點(diǎn)，檢測(cè)半徑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é)點(diǎn)隨機(jī)部署后的位置，覆蓋率為38.08%，圖4（b）是使用PSO算法優(yōu)化后的節(jié)點(diǎn)位置，圖4（c）是使用ABC算法優(yōu)化后的節(jié)點(diǎn)位置，圖4（d）是使用CABC算法優(yōu)化后的節(jié)點(diǎn)位置，可以看出CABC覆蓋優(yōu)化策略明顯優(yōu)于PSO、ABC覆蓋優(yōu)化策略。

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

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

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

表1 PSO、ABC、CABC策略對(duì)比

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

圖6 移動(dòng)節(jié)點(diǎn)比例覆蓋率收斂

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

表2 移動(dòng)節(jié)點(diǎn)平均移動(dòng)距離

6 結(jié)束語(yǔ)

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

［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ú)線傳感網(wǎng)絡(luò)移動(dòng)節(jié)點(diǎn)位置并行微粒群優(yōu)化策略［J］.計(jì)算機(jī)學(xué)報(bào)，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ú)線傳感網(wǎng)絡(luò)布局的虛擬力導(dǎo)向微粒群優(yōu)化策略［J］.電子學(xué)報(bào)，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ú)線傳感網(wǎng)絡(luò)覆蓋優(yōu)化策略中的應(yīng)用研究［D］.成都:電子科技大學(xué)，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］.管理學(xué)報(bào)，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）.［王翔，鄭建國(guó).求解約束優(yōu)化問題的多成員人工蜂群算法［J］.西安交通大學(xué)學(xué)報(bào)，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）.［張超群，鄭建國(guó)，王翔.蜂群算法研究綜述［J］.計(jì)算機(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.