改進(jìn)人工蜂群算法的無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化

李華+盧靜

摘 要： 由于無(wú)線傳感器網(wǎng)絡(luò)覆蓋屬于組合優(yōu)化范疇，為了在有限節(jié)點(diǎn)數(shù)量情況下提高其覆蓋率，引入人工蜂群算法并進(jìn)行改進(jìn)。通過(guò)注入全局最優(yōu)個(gè)體反饋來(lái)提高收斂速度，并升級(jí)了偵查蜂更新方法，采用一維高斯變異的方法，充分利用粒子先驗(yàn)知識(shí)，使粒子既能夠保證足夠的活力，又提高了算法的全局搜索能力。在40個(gè)節(jié)點(diǎn)數(shù)量條件下進(jìn)行仿真實(shí)驗(yàn)，提出的改進(jìn)算法覆蓋率達(dá)到了87.2%，與改進(jìn)蛙跳算法和標(biāo)準(zhǔn)人工蜂群算法的覆蓋率相比分別提高了1.6%和3.87%。

關(guān)鍵詞： 無(wú)線傳感器網(wǎng)絡(luò)； 人工蜂群； 全局最優(yōu)； 一維高斯變異； 概率測(cè)量模型； 覆蓋優(yōu)化

中圖分類號(hào)： TN711?34； TP393.04 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2018）03?0014?05

Abstract： Since the wireless sensor networks coverage belongs to the combinatorial optimization category， the artificial bee colony algorithm is introduced and perfected to improve the coverage rate in the condition of limited node quantity. The global optimal individual feedback is injected to improve the convergence rate， and update the refresh method of investigation bee. The one?dimensional Gaussian mutation method and particle prior knowledge are used fully to make the particles active， and improve the global search capability of the algorithm. The algorithm with 40 nodes was carried out with simulation experiment. The experimental results show that the coverage rate of the improved algorithm can reach up to 87.2%， and is increased by 1.6% and 3.87% respectively than that of the improved shuffled frog leaping algorithm and standard artificial bee colony algorithm.

Keywords： wireless sensor network； artificial bee colony； global optimization； one?dimensional Gaussian mutation； probabilistic measurement model； coverage optimization

0 引 言

無(wú)線傳感器網(wǎng)絡(luò)[1]具有低功耗和方便組網(wǎng)的優(yōu)勢(shì)，在物聯(lián)網(wǎng)、智能交通、目標(biāo)定位和環(huán)境探測(cè)等領(lǐng)域得到了廣泛應(yīng)用[2?3]。但隨著網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)數(shù)量的不斷增加，節(jié)點(diǎn)冗余問題也越加突出，怎樣才能低成本投入且高效的利用成為研究熱門，增大網(wǎng)絡(luò)的覆蓋面積成為無(wú)線傳感器網(wǎng)絡(luò)應(yīng)用的關(guān)鍵問題。

由于傳統(tǒng)算法[4?5]存在節(jié)點(diǎn)覆蓋程度低的問題，要想實(shí)現(xiàn)全局最優(yōu)在技術(shù)層面還有欠缺，鑒于無(wú)線傳感網(wǎng)絡(luò)的結(jié)構(gòu)與群體智能算法的特點(diǎn)極其相似，因此，大量的學(xué)者開始使用智能算法優(yōu)化無(wú)線傳感器網(wǎng)絡(luò)。

文獻(xiàn)[6]將改進(jìn)的粒子群算法應(yīng)用到無(wú)線傳感網(wǎng)絡(luò)的自組織中，有效地提高了節(jié)點(diǎn)的覆蓋面積；文獻(xiàn)[7]根據(jù)節(jié)點(diǎn)位置信息建立部署模型，提出一種基于改進(jìn)混合蛙跳算法；文獻(xiàn)[8]將遺傳算法應(yīng)用于優(yōu)化無(wú)線傳感器網(wǎng)絡(luò)覆蓋；文獻(xiàn)[9]將螢火蟲算法用于網(wǎng)絡(luò)覆蓋優(yōu)化。但這些應(yīng)用于無(wú)線傳感網(wǎng)絡(luò)覆蓋問題的群體智能算法由于本身存在一些缺點(diǎn)，導(dǎo)致其優(yōu)化的結(jié)果不是很理想。

人工蜂群算法[10?11]具有良好的全局性，已經(jīng)在很多領(lǐng)域內(nèi)被證明優(yōu)于其他一些算法。結(jié)合無(wú)線傳感器網(wǎng)絡(luò)的結(jié)構(gòu)特點(diǎn)，把節(jié)點(diǎn)的部署看成是蜂群尋找最優(yōu)蜜源的過(guò)程，將改進(jìn)人工蜂群算法應(yīng)用到無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化中，與其他幾種算法的比較實(shí)驗(yàn)說(shuō)明，提出算法得到的效果有明顯改善。

1 人工蜂群算法及改進(jìn)方法

1.1 人工蜂群算法描述

根據(jù)蜜蜂在活動(dòng)中扮演的角色，將其歸納為觀察蜂、采蜜蜂以及偵查蜂三種類型。偵查蜂在正常情況下是不存在的，當(dāng)采蜜蜂結(jié)束采蜜后自動(dòng)轉(zhuǎn)化為偵查蜂[12?13]。其搜索步驟為：首先采蜜蜂選取周圍最近的一個(gè)蜜源，然后觀察蜂通過(guò)信息跟隨其中一只采蜜蜂，在這個(gè)過(guò)程中選取出較好的蜜源，最后采蜜蜂放棄蜜源，轉(zhuǎn)化為偵查蜂，隨機(jī)搜索新蜜源。

上述過(guò)程即為一個(gè)優(yōu)化問題，將每個(gè)蜜源的位置看成一個(gè)解。假設(shè)蜜源位置表示為總數(shù)為其中，第個(gè)蜜源表示為為其收益度值。觀察蜂選取蜜源的概率表示如下[14]：

觀察蜂對(duì)周邊的蜜源進(jìn)行權(quán)衡后，會(huì)選取較好的蜜源，蜜源位置更新公式為：

式中：為[0，1]之間的隨機(jī)數(shù)。如果，那么觀察蜂就會(huì)更新位置，否則不變。在更新的同時(shí)限定次數(shù)加1，當(dāng)循環(huán)次數(shù)達(dá)到限定閾值時(shí)，會(huì)丟棄該蜜源，轉(zhuǎn)化為偵查蜂，生成位置公式為：

1.2 改進(jìn)的人工蜂群算法

在蜂群算法中，當(dāng)達(dá)到一定次數(shù)后適應(yīng)值仍然沒有改進(jìn)時(shí)，該蜜蜂會(huì)變成偵查蜂，然后隨機(jī)生成新的蜜源位置代替原位置。采用偵查蜂隨機(jī)搜索的目的是當(dāng)算法處于收斂狀態(tài)，全部蜜蜂均匯聚在同一蜜源時(shí)，把蜜蜂強(qiáng)制轉(zhuǎn)移，以此保證蜜蜂的活力。但由于這種策略放棄了原來(lái)蜜源的所有信息，導(dǎo)致算法收斂速度較慢，為了讓蜜蜂既能夠保證足夠的活力，同時(shí)又可以充分地利用先驗(yàn)知識(shí)，采用一維高斯變異的搜索策略，計(jì)算公式如下：endprint

人工蜂群算法采用概率選擇蜜源位置進(jìn)行更新，所以具有全局搜索能力，從而使粒子具有很強(qiáng)的隨機(jī)性，即便是加入了收益度值的判定，并沒有明顯提高其收斂速度。所以又在更新公式中增加了最優(yōu)蜜源位置這樣就使得其性能更加均衡，改進(jìn)算法位置更新的表達(dá)式為：

改進(jìn)人工蜂群算法的步驟如圖1所示。

2 網(wǎng)絡(luò)覆蓋優(yōu)化的問題

無(wú)線傳感網(wǎng)絡(luò)覆蓋優(yōu)化的問題可以描述為：在一個(gè)已知大小的空間內(nèi)布置多個(gè)能夠感應(yīng)與通信的節(jié)點(diǎn)，在保證節(jié)點(diǎn)之間連通性的同時(shí)，采取一定的措施來(lái)部署節(jié)點(diǎn)，且盡可能使用較少的節(jié)點(diǎn)達(dá)到網(wǎng)絡(luò)覆蓋范圍最大化。其中網(wǎng)絡(luò)覆蓋率是最重要的一個(gè)衡量標(biāo)準(zhǔn)。

常用的節(jié)點(diǎn)測(cè)量有二元測(cè)量法和概率測(cè)量法兩種模型[15]。由于前者具有本身的局限，容易導(dǎo)致測(cè)量的精度偏低，故這里通過(guò)概率測(cè)量模型研究無(wú)線傳感器網(wǎng)絡(luò)覆蓋率的問題。設(shè)測(cè)量范圍內(nèi)有個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)用表示，其中且每個(gè)節(jié)點(diǎn)的屬性和參數(shù)均相同，通信半徑為感應(yīng)半徑為同時(shí)滿足

在二維空間中研究該問題，假設(shè)節(jié)點(diǎn)所處的位置為，測(cè)量范圍內(nèi)任意點(diǎn)坐標(biāo)為，所以相對(duì)的檢測(cè)概率可表示如下：

式中：是傳感節(jié)點(diǎn)測(cè)量的可靠性參數(shù)，且是到的歐氏距離；為傳感器節(jié)點(diǎn)屬性相關(guān)參數(shù)，且滿足與是輸入?yún)?shù)。

通過(guò)得到的能夠算出測(cè)量范圍內(nèi)傳感器節(jié)點(diǎn)對(duì)點(diǎn)的聯(lián)合檢測(cè)概率，可表示如下：

式中表示測(cè)量范圍內(nèi)的全部節(jié)點(diǎn)。在這里設(shè)定的檢測(cè)閾值為0.8，也就是說(shuō)，當(dāng)聯(lián)合檢測(cè)概率小于0.8時(shí)，就可以認(rèn)為點(diǎn)不被檢測(cè)；反之，就認(rèn)為點(diǎn)可以被檢測(cè)。

假設(shè)檢測(cè)區(qū)域?yàn)橐?guī)則矩形，為了計(jì)算無(wú)線傳感器網(wǎng)絡(luò)覆蓋率，在檢測(cè)區(qū)域上劃分個(gè)面積相等的小矩形，然后把小矩形看作點(diǎn)利用式（8）算出所有點(diǎn)的檢測(cè)概率，同時(shí)計(jì)算出被檢測(cè)點(diǎn)的數(shù)量，兩者的乘積即為覆蓋面積，那么覆蓋率可以表示為：

3 實(shí)驗(yàn)結(jié)果及分析

為了驗(yàn)證改進(jìn)人工蜂群算法在無(wú)線傳感器網(wǎng)絡(luò)覆蓋中的效果，使用Matlab軟件對(duì)其進(jìn)行仿真實(shí)驗(yàn)，并與標(biāo)準(zhǔn)粒子群算法、標(biāo)準(zhǔn)人工蜂群算法和文獻(xiàn)[7]中的改進(jìn)蛙跳算法進(jìn)行對(duì)比，進(jìn)而說(shuō)明本文提出算法的有效性。

3.1 相同節(jié)點(diǎn)數(shù)量對(duì)比實(shí)驗(yàn)

在邊長(zhǎng)50 m的正方形區(qū)域內(nèi)，隨機(jī)部署40個(gè)節(jié)點(diǎn)，感應(yīng)半徑5 m，通信半徑10 m，傳感節(jié)點(diǎn)測(cè)量的可靠性參數(shù)傳感器節(jié)點(diǎn)屬性相關(guān)參數(shù)。

參與比較算法的迭代次數(shù)極限為500，粒子數(shù)為50。其中，標(biāo)準(zhǔn)人工蜂群算法和改進(jìn)人工蜂群算法參數(shù)設(shè)置一致，最大采蜜次數(shù)為50，改進(jìn)蛙跳算法的迭代次數(shù)為5，粒子群算法參數(shù)且從0.5～0.2線性遞減。

為了驗(yàn)證提出的改進(jìn)算法的優(yōu)越性，將標(biāo)準(zhǔn)粒子群算法（PSO）、改進(jìn)蛙跳算法（GSFLA）和標(biāo)準(zhǔn)人工蜂群算法（ABCA）進(jìn)行比較，得到的結(jié)果如表1所示。

從表1得到的結(jié)果可以看出，采用改進(jìn)人工蜂群算法的無(wú)線傳感器網(wǎng)絡(luò)覆蓋率達(dá)到了87.2%，與改進(jìn)蛙跳算法相比提高了1.6%，與標(biāo)準(zhǔn)人工蜂群算法相比提高了3.87%，網(wǎng)絡(luò)覆蓋率得到了明顯的改善。

為了從直觀上觀察覆蓋效果，將上述實(shí)驗(yàn)結(jié)果輸出，分別得到40個(gè)初始節(jié)點(diǎn)、改進(jìn)蛙跳算法、標(biāo)準(zhǔn)人工蜂群算法和改進(jìn)人工蜂群算法的直觀覆蓋效果如圖2～圖6所示。

從上面幾種算法對(duì)應(yīng)的覆蓋圖可以看出，利用智能算法對(duì)初始節(jié)點(diǎn)覆蓋進(jìn)行優(yōu)化后，大塊空白的現(xiàn)象消失，節(jié)點(diǎn)分布趨于均衡，改進(jìn)人工蜂群算法的優(yōu)化效果最佳。

3.2 不同節(jié)點(diǎn)數(shù)量對(duì)比實(shí)驗(yàn)

為進(jìn)一步驗(yàn)證改進(jìn)人工蜂群算法在無(wú)線傳感器網(wǎng)絡(luò)覆蓋中的效果，與標(biāo)準(zhǔn)人工蜂群與改進(jìn)蛙跳算法在不同節(jié)點(diǎn)數(shù)量下的覆蓋率進(jìn)行了對(duì)比實(shí)驗(yàn)，配置參數(shù)不變，得到的結(jié)果如表2所示。

從表2可以看出，改進(jìn)人工蜂群算法不管是在節(jié)點(diǎn)數(shù)量較多時(shí)，還是在節(jié)點(diǎn)數(shù)較少時(shí)均比其他幾種算法能更加有效地提高無(wú)線傳感器網(wǎng)絡(luò)覆蓋率。為方便對(duì)比在節(jié)點(diǎn)變化情況下算法覆蓋優(yōu)化效果變化差異，將節(jié)點(diǎn)數(shù)量與覆蓋率的關(guān)系變化繪制成曲線圖，如圖7所示。

從節(jié)點(diǎn)數(shù)量與覆蓋率關(guān)系曲線圖中可以看出：隨著無(wú)線傳感器節(jié)點(diǎn)數(shù)量的增多，網(wǎng)絡(luò)覆蓋率均得到了明顯的提升。節(jié)點(diǎn)的利用率體現(xiàn)在曲線的斜率上，隨著無(wú)線傳感器節(jié)點(diǎn)數(shù)量的增多，均表現(xiàn)出減弱的趨勢(shì)，但是改進(jìn)人工蜂群算法的下降速率要小于標(biāo)準(zhǔn)人工蜂群的下降速率，說(shuō)明改進(jìn)人工蜂群算法的全局搜索能力更強(qiáng)，在同等條件下具有更優(yōu)的節(jié)點(diǎn)利用率，網(wǎng)絡(luò)覆蓋效果更好。

4 結(jié) 語(yǔ)

結(jié)合無(wú)線傳感器網(wǎng)絡(luò)的結(jié)構(gòu)特點(diǎn)，引入改進(jìn)人工蜂群算法，在更新策略中添加全局最優(yōu)個(gè)體反饋，提升了算法的收斂速度，并借助一維高斯變異的更新方法，保證了粒子的活力，同時(shí)具有良好的全局搜索能力。在40個(gè)節(jié)點(diǎn)時(shí)進(jìn)行了對(duì)比實(shí)驗(yàn)，結(jié)果顯示，使用改進(jìn)人工蜂群算法的網(wǎng)絡(luò)覆蓋率均優(yōu)于其他幾種算法，比改進(jìn)蛙跳算法提高了1.6%，比標(biāo)準(zhǔn)人工蜂群算法提高了3.87%，且能夠使節(jié)點(diǎn)分布更加均勻，在不同節(jié)點(diǎn)的實(shí)驗(yàn)中，改進(jìn)人工蜂群算法依然能夠保持較好的全局搜索能力和魯棒性，相比其他算法具有更優(yōu)的節(jié)點(diǎn)利用率和覆蓋效果。

參考文獻(xiàn)

[1] 龍宇翔，趙英杰.基于WSN覆蓋問題及自愈算法的研究[J].現(xiàn)代電子技術(shù)，2016，39（1）：27?30.

LONG Yuxiang， ZHAO Yingjie. Study on coverage control problem for WSN and self?healing algorithm [J]. Modern electronics technique， 2016， 39（1）： 27?30.

[2] FERNANDO L， ANTONIO?JAVIER G， FELIPE G， et al. A comprehensive approach to WSN?based ITS applications： a survey [J]. Sensors， 2011（11）： 10220?10265.endprint

[3] 張敖木翰，張平，曹劍東.基于物聯(lián)網(wǎng)的公路交通運(yùn)行狀態(tài)評(píng)估與預(yù)測(cè)[J].公路，2015，60（9）：178?183.

ZHANG Aomuhan， ZHANG Ping， CAO Jiandong. Estimate and prediction of traffic state on expressway under Internet of Things [J]. Highway， 2015， 60（9）： 178?183.

[4] CRISTINA A， PEDRO S， ANDR?S I， et al. Wireless sensor networks for oceanographic monitoring： a systematic review [J]. Sensors， 2010， 10（7）： 6948?6968.

[5] 戴寧，毛劍琳，付麗霞，等.基于虛擬勢(shì)場(chǎng)的有向傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用研究，2014，31（3）：905?907.

DAI Ning， MAO Jianlin， FU Lixia， et al. Virtual potential field based coverage optimization algorithm for directional sensor networks [J]. Application research of computers， 2014， 31（3）： 905?907.

[6] 王巍，彭力.基于改進(jìn)微粒群算法的移動(dòng)傳感器網(wǎng)絡(luò)自組織[J].計(jì)算機(jī)工程與設(shè)計(jì)，2009，30（3）：654?659.

WANG Wei， PENG Li. Self?deployment of mobile sensor network based on improved particle swarm optimization [J]. Computer engineering and design， 2009， 30（3）： 654?659.

[7] 李響，鄭瑞娟.基于改進(jìn)蛙跳算法的無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化[J].計(jì)算機(jī)測(cè)量與控制，2014，22（6）：1993?1995.

LI Xiang， ZHENG Ruijuan. Wireless sensor network coverage optimization based on improved leapfrog algorithm [J]. Computer measurement & control， 2014， 22（6）： 1993?1995.

[8] 屈巍，汪晉寬，趙旭，等.基于遺傳算法的無(wú)線傳感器網(wǎng)絡(luò)覆蓋控制優(yōu)化策略[J].系統(tǒng)工程與電子技術(shù)，2010，32（11）：2476?2479.

QU Wei， WANG Jinkuan， ZHAO Xu， et al. Optimal coverage stra?tegy based on genetic algorithm in wireless sensor networks [J]. Systems engineering and electronics， 2010， 32（11）： 2476?2479.

[9] 劉洲洲，王福豹，張克旺.基于改進(jìn)螢火蟲優(yōu)化算法的WSN覆蓋優(yōu)化分析[J].傳感技術(shù)學(xué)報(bào)，2013，26（5）：675?682.

LIU Zhouzhou， WANG Fubao， ZHANG Kewang. Performance analysis of improved glowworm swarm optimization algorithm and the application in coverage optimization of WSNs [J]. Chinese journal of sensors and actuators， 2013， 26（5）： 675?682.

[10] 張鵬，劉弘，劉鵬.改進(jìn)的蜂群算法及其在CBD選址規(guī)劃中的應(yīng)用[J].計(jì)算機(jī)科學(xué)，2013，40（8）：210?213.

ZHANG Peng， LIU Hong， LIU Peng. Improved artificial bee colony algorithm and its application in CBD location planning [J]. Computer science， 2013， 40（8）： 210?213.

[11] 陳杰，沈艷霞，陸欣.基于信息反饋和改進(jìn)適應(yīng)度評(píng)價(jià)的人工蜂群算法[J].智能系統(tǒng)學(xué)報(bào)，2016，11（2）：172?179.

CHEN Jie， SHEN Yanxia， LU Xin. Artificial bee colony algorithm based on information feedback and an improved fitness value evaluation [J]. CAAI transactions on intelligent systems， 2016， 11（2）： 172?179.

[12] BARRON J L， FLEET D J， BEAUCHEMIN S S. Performance of optical flow techniques [C]// Proceedings of 1992 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Washington， DC： IEEE Computer Society， 1992： 236?242.

[13] 張玲，王玲，吳桐.基于改進(jìn)的粒子群算法優(yōu)化反向傳播神經(jīng)網(wǎng)絡(luò)的熱舒適度預(yù)測(cè)模型[J].計(jì)算機(jī)應(yīng)用，2014，34（3）：775?779.

ZHANG Ling， WANG Ling， WU Tong. Thermal comfort prediction model based on improved particle swarm optimization?back propagation neural network [J]. Journal of computer applications， 2014， 34（3）： 775?779.

[14] 孫澤宇，伍衛(wèi)國(guó)，王換招，等.概率模型下的一種優(yōu)化覆蓋算法[J].軟件學(xué)報(bào)，2016，27（5）：1285?1300.

SUN Zeyu， WU Weiguo， WANG Huanzhao， et al. Optimized coverage algorithm in probability model [J]. Journal of software， 2016， 27（5）： 1285?1300.

[15] 孫偉，朱正禮，鄭磊，等.基于人工魚群和微粒群混合算法的WSN節(jié)點(diǎn)部署策略[J].計(jì)算機(jī)科學(xué)，2012，39（11）：83?85.

SUN Wei， ZHU Zhengli， ZHENG Lei， et al. Deployment strategy of wireless sensor network nodes based on AFSA?PSO hybrid algorithm [J]. Computer science， 2012， 39（11）： 83?85.endprint