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

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

1(常熟理工學院計算機科學與工程學院　江蘇 常熟 215500)

2(中國礦業(yè)大學計算機科學與技術學院　江蘇 徐州 221116)

?

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

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

1(常熟理工學院計算機科學與工程學院江蘇 常熟 215500)

2(中國礦業(yè)大學計算機科學與技術學院江蘇 徐州 221116)

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

關鍵詞動態(tài)部署虛擬力人工蜂群算法移動節(jié)點

0引言

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

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

1覆蓋模型與假設

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

(1)

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

(2)

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

(3)

為簡化模型，假設以下條件：

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

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

(3) 移動節(jié)點具有足夠能量且可以準確移動到優(yōu)化后位置。

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

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

2.1虛擬力算法基本原理

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

(4)

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

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

(5)

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

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

(6)

(7)

其中，MaxStep是節(jié)點的最大移動距離，F(xiàn)是節(jié)點受到的虛擬力，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é)點數(shù)s，移動節(jié)點數(shù)m，蜂巢大小cs，最大迭代次數(shù)cycleMax，偵查蜂探尋閾值limit=cs/2。獲取固定節(jié)點位置，并隨機生成cs/2個解向量，使用網(wǎng)格評估法計算覆蓋率。

REPEAT

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

Vij=Xij+φ(xij-xkj)

(8)

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

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

(9)

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

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

(10)

其中rand(0,1)表示[0,1]之間的隨機數(shù)，gij對應于解向量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)

其中，各元素上標表示解向量的序號和元素序號，下標對應虛擬力在相應坐標軸的分量。

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

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

3仿真實驗分析

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

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

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

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

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

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

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

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

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

4結語

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

參考文獻

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

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

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

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

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

[8] 冀俊忠,魏紅凱,劉椿年,等.基于引導素更新和擴散機制的人工蜂群算法[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].計算機應用與研究,2011,28(9):3201-3205.

[11] 向萬里,馬壽峰.基于輪盤賭反向選擇機制的蜂群優(yōu)化算法[J].計算機應用研究,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] 陳杭,王東,李曉鴻.一種基于虛擬力的移動傳感器網(wǎng)絡再部署算法[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

文獻標識碼A

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

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