嵌入虛擬力的人工蜂群優(yōu)化覆蓋策略

戴　歡　李克清*　張　騫,2　葛柳飛,2

1(常熟理工學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院　江蘇 常熟 215500)

2(中國礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院　江蘇 徐州 221116)

?

嵌入虛擬力的人工蜂群優(yōu)化覆蓋策略

戴歡1李克清1*張騫1,2葛柳飛1,2

1(常熟理工學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院江蘇 常熟 215500)

2(中國礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院江蘇 徐州 221116)

摘要蜂群算法在優(yōu)化傳感網(wǎng)感知覆蓋時(shí)，直接放棄達(dá)到迭代次數(shù)而未進(jìn)化的解向量，由于沒有先驗(yàn)條件，隨機(jī)生成新的解不夠好，導(dǎo)致收斂速度變慢，無法應(yīng)對具有大量移動(dòng)節(jié)點(diǎn)的網(wǎng)絡(luò)布局優(yōu)化。針對上述問題，提出嵌入虛擬力的人工蜂群優(yōu)化覆蓋策略，利用節(jié)點(diǎn)間虛擬的作用力引導(dǎo)陷入退化現(xiàn)象的解向量，加快收斂速度，實(shí)現(xiàn)在高維空間的布局優(yōu)化。仿真結(jié)果表明，該算法在覆蓋優(yōu)化效果和算法收斂速度上均優(yōu)于傳統(tǒng)的蜂群策略。

關(guān)鍵詞動(dòng)態(tài)部署虛擬力人工蜂群算法移動(dòng)節(jié)點(diǎn)

0引言

無線傳感器網(wǎng)絡(luò)WSN[1-4]由大量傳感器節(jié)點(diǎn)構(gòu)成，具有感知外界環(huán)境的能力，被廣泛應(yīng)用于軍事、民用領(lǐng)域。區(qū)域覆蓋是WSN的基本問題之一，區(qū)域覆蓋率作為WSN服務(wù)質(zhì)量的基本標(biāo)準(zhǔn)之一。移動(dòng)節(jié)點(diǎn)的加入使得WSN具有了更多的靈活性，通過移動(dòng)節(jié)點(diǎn)對覆蓋空洞的修復(fù)，提高WSN的覆蓋率，有利于提高WSN的服務(wù)質(zhì)量。文獻(xiàn)[5-7]使用ABC(Artificial Bee Colony)算法優(yōu)化WSN網(wǎng)絡(luò)布局，ABC是模擬蜜蜂采蜜行為的新興智能群算法[8,9]，具有控制參數(shù)少，健壯性的優(yōu)點(diǎn)[10,11]，被廣泛應(yīng)用與各個(gè)領(lǐng)域。

在WSN覆蓋優(yōu)化應(yīng)用中，ABC當(dāng)某個(gè)解迭代次數(shù)達(dá)到閾值時(shí)，該解會(huì)被自動(dòng)丟棄，并在解向量空間中隨機(jī)生成一個(gè)新的解。被丟棄的解中往往包含部分維的最優(yōu)值，且由于沒有先驗(yàn)條件，隨機(jī)生成的解往往不夠好，且導(dǎo)致算法收斂速度變慢。尤其在面對大量移動(dòng)節(jié)點(diǎn)的WSN覆蓋優(yōu)化時(shí)，解向量維數(shù)大，更易出現(xiàn)上述現(xiàn)象。虛擬力VF(Virtual Forces)算法[12-14]是通過建立傳感器節(jié)點(diǎn)、障礙物與熱點(diǎn)區(qū)域的虛擬力模型，根據(jù)受力平衡優(yōu)化移動(dòng)節(jié)點(diǎn)位置的算法。針對上述現(xiàn)象，本文在ABC中不直接丟棄退化的解向量，利用節(jié)點(diǎn)間虛擬的作用力引導(dǎo)陷入退化現(xiàn)象的解向量進(jìn)化，加速算法收斂速度，完成在高維空間的搜索過程。

1覆蓋模型與假設(shè)

假設(shè)監(jiān)測區(qū)域?yàn)槎S平面A，在該區(qū)域上隨機(jī)部署N個(gè)傳感器節(jié)點(diǎn)，節(jié)點(diǎn)坐標(biāo)已知，且所有節(jié)點(diǎn)性能一致。用節(jié)點(diǎn)集S{S1,S2,…,SN}表示。Si{xi,yi,sr,cr}表示節(jié)點(diǎn)i的位置為(xi,yi)，感知半徑為sr，通信半徑為cr，其中cr=2sr，監(jiān)測點(diǎn)Q的坐標(biāo)為(x,y)，則Q與節(jié)點(diǎn)Si的歐式距離如下式：

(1)

假定傳感器的感知模型使用布爾模型，則節(jié)點(diǎn)Si對目標(biāo)Q的監(jiān)測概率為：

(2)

節(jié)點(diǎn)集S對監(jiān)測區(qū)域A的覆蓋率定義為節(jié)點(diǎn)集覆蓋面積的總和與區(qū)域A總面積之比。將監(jiān)測區(qū)域A離散化為m×n個(gè)網(wǎng)格點(diǎn)，離散化的精度(即網(wǎng)格的邊長)由求解問題的精度決定，每個(gè)網(wǎng)格點(diǎn)是否被覆蓋可用式(2)衡量，則問題簡化為被覆蓋的網(wǎng)格點(diǎn)數(shù)count與m×n的比值，即：

(3)

為簡化模型，假設(shè)以下條件：

(1) WSN中存在一個(gè)具有較強(qiáng)計(jì)算能力且具有數(shù)據(jù)融合能力的Sink節(jié)點(diǎn)，用于實(shí)現(xiàn)移動(dòng)節(jié)點(diǎn)位置的優(yōu)化計(jì)算；

(2) 所有傳感器節(jié)點(diǎn)可以獲取自身位置；

(3) 移動(dòng)節(jié)點(diǎn)具有足夠能量且可以準(zhǔn)確移動(dòng)到優(yōu)化后位置。

2嵌入虛擬力的蜂群覆蓋優(yōu)化策略

在ABC中，當(dāng)某個(gè)解迭代次數(shù)達(dá)到閾值時(shí)，該解向量會(huì)被自動(dòng)丟棄，并在解向量空間中隨機(jī)生成一個(gè)新的解向量。由于沒有先驗(yàn)條件，隨機(jī)生成的解向量通常不夠理想，導(dǎo)致算法收斂速度變慢。針對上述問題，在ABC偵查蜂時(shí)期，對于要丟棄的解向量，使用虛擬力算法建立全局節(jié)點(diǎn)受力圖，利用受力平衡原則，使移動(dòng)節(jié)點(diǎn)向受力方向移動(dòng)，引導(dǎo)退化的解向量進(jìn)化，即建立節(jié)點(diǎn)間虛擬力受力模型，使得解向量的每一維都在虛擬力引導(dǎo)下進(jìn)化。由于虛擬力的作用，新生成的解向量通常優(yōu)于隨機(jī)生成的解向量，最終加快ABC收斂速度，完成移動(dòng)節(jié)點(diǎn)位置的搜索，虛擬力算法及嵌入虛擬力的蜂群覆蓋優(yōu)化策略如下所述。

2.1虛擬力算法基本原理

虛擬力算法是受到機(jī)器人虛擬力場的啟發(fā)，考慮傳感器節(jié)點(diǎn)、障礙物、熱點(diǎn)區(qū)域間引力和斥力的一種自組織算法。在WSN動(dòng)態(tài)部署時(shí)，移動(dòng)節(jié)點(diǎn)根據(jù)所受到的虛擬力，向監(jiān)測區(qū)域的其他區(qū)域移動(dòng)，直至達(dá)到受力平衡。文獻(xiàn)[12]給出虛擬力模型，節(jié)點(diǎn)Si受到的合力Fi如下式所示：

(4)

其中，F(xiàn)ij為節(jié)點(diǎn)Sj對節(jié)點(diǎn)Si的力，包括引力和斥力，F(xiàn)iR為障礙物對Si的斥力，F(xiàn)iA為熱點(diǎn)區(qū)域?qū)?jié)點(diǎn)Si的引力，本文只考慮節(jié)點(diǎn)間的作用力。

虛擬力算法采用距離閾值dth調(diào)整節(jié)點(diǎn)間相互作用力的屬性。dij為節(jié)點(diǎn)Si與節(jié)點(diǎn)Sj的距離，F(xiàn)ij與dij和通信半徑cr的關(guān)系如下式所示：

(5)

其中，αij為節(jié)點(diǎn)Si與節(jié)點(diǎn)Sj之間的方位角，wA和wR分別表示虛擬力的引力系數(shù)和斥力系數(shù)。動(dòng)態(tài)部署后的節(jié)點(diǎn)疏密程度取決于距離閾值dth，當(dāng)dth過小時(shí)，節(jié)點(diǎn)布局較密，無法保證覆蓋率，當(dāng)dth過大時(shí)，節(jié)點(diǎn)稀疏，容易產(chǎn)生監(jiān)測盲區(qū)。

在虛擬力的作用下，各移動(dòng)節(jié)點(diǎn)根據(jù)虛擬力將原位置(xold,yold)更新為新位置(xnew,ynew)：

(6)

(7)

其中，MaxStep是節(jié)點(diǎn)的最大移動(dòng)距離，F(xiàn)是節(jié)點(diǎn)受到的虛擬力，F(xiàn)x、Fy是虛擬力在x軸和y軸的分量。

2.2嵌入虛擬力的蜂群覆蓋優(yōu)化策略

嵌入虛擬力的蜂群EVFABC(Embed Virtual Force Artificial Bee Colony)覆蓋優(yōu)化算法如下：

算法1嵌入虛擬力的蜂群覆蓋優(yōu)化算法

① 初始化參數(shù)：監(jiān)測半徑sr，監(jiān)測區(qū)域A大小，靜態(tài)節(jié)點(diǎn)數(shù)s，移動(dòng)節(jié)點(diǎn)數(shù)m，蜂巢大小cs，最大迭代次數(shù)cycleMax，偵查蜂探尋閾值limit=cs/2。獲取固定節(jié)點(diǎn)位置，并隨機(jī)生成cs/2個(gè)解向量，使用網(wǎng)格評估法計(jì)算覆蓋率。

REPEAT

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

Vij=Xij+φ(xij-xkj)

(8)

其中，解向量Xk是解向量Xi的鄰居(k≠i)，φ是[-1,1]之間的隨機(jī)數(shù)。

③ 使用式(9)計(jì)算解向量Xi的概率，若rand(0,1)

(9)

④ 如果一個(gè)解向量的搜索次數(shù)達(dá)到閾值limit，使用式(10)生成新的解向量，并計(jì)算其適應(yīng)度。

Rij=Xij+rand(0,1)×gij

(10)

其中rand(0,1)表示[0,1]之間的隨機(jī)數(shù)，gij對應(yīng)于解向量i的第j維元素在虛擬力作用下的距離，如式(11)所示：

gij=F(i,(j+1)/2)xF(i,(j+1)/2)×MaxStep×exp-1F(i,(j+1)/2)() j為奇數(shù)F(i,j/2)yF(i,j/2)×MaxStep×exp-1F(i,j/2)() j為偶數(shù)ì?í????

(11)

其中，各元素上標(biāo)表示解向量的序號和元素序號，下標(biāo)對應(yīng)虛擬力在相應(yīng)坐標(biāo)軸的分量。

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

UTILL達(dá)到最大迭代次數(shù)cycleMax。

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

圖1是隨機(jī)部署的節(jié)點(diǎn)分布圖，覆蓋率為84.88%，圖2是使用ABC算法優(yōu)化后的節(jié)點(diǎn)分布圖，覆蓋率為88.13%，圖3是使用EVFABC算法優(yōu)化后的節(jié)點(diǎn)分布圖，覆蓋率為96.85%。通過對比可知，在面對100個(gè)移動(dòng)節(jié)點(diǎn)的情況下， EVFABC覆蓋優(yōu)化算法明顯優(yōu)于ABC覆蓋優(yōu)化算法。主要原因在于，ABC算法直接丟棄迭代次數(shù)達(dá)到閾值的解，然后隨機(jī)生成一個(gè)新的解向量，由于沒有先驗(yàn)信息，新的解向量質(zhì)量往往不夠好，導(dǎo)致收斂速度變慢，影響搜索過程。

圖1　隨機(jī)部署的固定節(jié)點(diǎn)分布圖　　圖2　ABC優(yōu)化后的節(jié)點(diǎn)分布圖

圖3　EVFABC優(yōu)化后的節(jié)點(diǎn)分布圖

為進(jìn)一步驗(yàn)證EVFABC覆蓋優(yōu)化策略的性能，圖4給出VF、ABC、EVFABC的收斂曲線對比圖，可知：ABC陷入局部極值，后期收斂速度極慢，VF算法中，移動(dòng)節(jié)點(diǎn)受到固定節(jié)點(diǎn)的干擾，也陷入局部極值，相較于ABC、VF算法，EVFABC擺脫VF、ABC陷入的局部極值，達(dá)到了較好的收斂效果。

圖4　ABC、VF、EVFABC收斂曲線圖

VF、ABC、EVFABC策略分別獨(dú)立運(yùn)行100次，其平均覆蓋率如表1所示。EVFABC優(yōu)化后覆蓋率達(dá)到96.85%，較VF、ABC分別提高了3.14%、8.72%，EVFABC在迭代300次完成搜索過程，而VF、ABC陷入局部極值，迭代500次仍未完成搜索過程。

表1　VF、ABC、EVFABC策略對比表

在低維空間：固定節(jié)點(diǎn)20個(gè)、移動(dòng)節(jié)點(diǎn)10個(gè)，sr=12 m；高維空間：固定節(jié)點(diǎn)200個(gè)，移動(dòng)節(jié)點(diǎn)100個(gè)，sr=4.5 m，其他參數(shù)不變的情況下，作對比實(shí)現(xiàn)，驗(yàn)證ABC、EVFABC在低維空間、高維空間的收斂效果，仿真結(jié)果如圖5所示?？芍狝BC受到高維空間影響較大，甚至無法完成布局優(yōu)化，EVFABC受到高維空間的影響較小，可以完成布局優(yōu)化。

圖5　ABC、EVFABC低維空間、高維空間收斂對比圖

4結(jié)語

本文提出嵌入虛擬力的蜂群覆蓋優(yōu)化策略，使用虛擬力算子進(jìn)化要丟棄的解向量，幫助其加快收斂速度，實(shí)現(xiàn)在高維空間的布局優(yōu)化。仿真結(jié)果表明，EVFABC優(yōu)化后覆蓋率達(dá)到96.85%，較VF、ABC分別提高了3.14%、8.72%。

參考文獻(xiàn)

[1] 張希偉,戴海鵬,徐力杰,等.無線傳感器網(wǎng)絡(luò)中移動(dòng)協(xié)助的數(shù)據(jù)收集策略[J].軟件學(xué)報(bào),2013(2):198-214.

[2] 張曉玲,梁煒,于海斌,等.無線傳感器網(wǎng)絡(luò)傳輸調(diào)度方法綜述[J].通信學(xué)報(bào),2012,33(5):143-157.

[3] 楊小軍.無線傳感器網(wǎng)絡(luò)下分布式?jīng)Q策融合方法綜述[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(11):1-6.

[4] 熊偉麗,劉欣,孫順遠(yuǎn),等.WSNs能量異構(gòu)節(jié)點(diǎn)部署與區(qū)域覆蓋優(yōu)化[J].傳感器與微系統(tǒng),2013,32(11):59-62.

[5] 胡珂.基于人工蜂群算法在無線傳感網(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] 袁浩.基于改進(jìn)蜂群算法無線傳感器感知節(jié)點(diǎn)部署優(yōu)化[J].計(jì)算機(jī)應(yīng)用研究,2010,27(7):2704-2708.

[8] 冀俊忠,魏紅凱,劉椿年,等.基于引導(dǎo)素更新和擴(kuò)散機(jī)制的人工蜂群算法[J].計(jì)算機(jī)研究與發(fā)展,2013,50(9):2005-2014.

[9] Karaboga D,Basturk B.On the performance of artificial bee colony (ABC) algorithm[J].Applied Soft Computing,2008,8(1):687-697.

[10] 張超群,鄭建國,王翔.蜂群算法研究綜述[J].計(jì)算機(jī)應(yīng)用與研究,2011,28(9):3201-3205.

[11] 向萬里,馬壽峰.基于輪盤賭反向選擇機(jī)制的蜂群優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用研究,2013,30(1):86-89.

[12] Zou Y,Chakrabarty K.Sensor deployment and target localization based on virtual forces (INFOCOM 2003)[C]//San Francisco,CA,USA.2003:1293-1303.

[13] Li Shijian,Xu Congfu,Pan Weike,et al.Sensor deployment optimization for detecting maneuvering targets(International Conference on Information Fusion) [C]//Philadelphia,PA,USA.2005.2005:7.

[14] 陳杭,王東,李曉鴻.一種基于虛擬力的移動(dòng)傳感器網(wǎng)絡(luò)再部署算法[J].Computer Engineering and Applications,2014,50(1):63-67.

STRATEGY OF OPTIMISING COVERAGE WITH VIRTUAL FORCE-EMBEDDED ARTIFICIAL BEE COLONY

Dai Huan1Li Keqing1*Zhang Qian1,2Ge Liufei1,2

1(SchoolofComputerScienceandEngineering,ChangshuInstituteofTechnology,Changshu215500,Jiangsu,China)2(SchoolofComputerScienceandTechnology,ChinaUniversityofMiningandTechnology,Xuzhou221116,Jiangsu,China))

AbstractWhen optimising sensor network sensing coverage, the artificial bee colony algorithm directly abandons the solution vector which reaches the iteration times but failed in evolution. Since there are no priori conditions, the new solution randomly generated is not good enough, this results in slow convergence and unable to cope with the network layout optimisation with a large number of mobile nodes. To address the above problems, we proposed the strategy of optimising the coverage with virtual force-embedded artificial bee colony. It uses virtual acting force between the nodes to lead the solution vector falling into degradation phenomenon and accelerates the convergence rate, realises the layout optimisation in high-dimensional space. Simulation results show that the proposed algorithm is better than the traditional artificial bee colony strategy in coverage optimisation effect and the convergence rate of the algorithm.

KeywordsDynamic deploymentVirtual forceArtificial bee colony algorithmMobile nodes

中圖分類號TP393

文獻(xiàn)標(biāo)識碼A

DOI:10.3969/j.issn.1000-386x.2016.01.026

收稿日期：2014-05-04。國家自然科學(xué)基金項(xiàng)目(61300186)；江蘇省科技支撐計(jì)劃項(xiàng)目-社發(fā)(BE2012672)；江蘇省高校自然科學(xué)研究面上項(xiàng)目(13KJB510001)；科研啟動(dòng)項(xiàng)目(KYZ2013002Z)；常熟市社發(fā)重點(diǎn)項(xiàng)目(CS201102)。戴歡，講師，主研領(lǐng)域：無線傳感器網(wǎng)絡(luò)，模式識別。李克清，教授。張騫，碩士。葛柳飛，碩士。