黃慶展， 毛 力， 吳 濱， 楊 弘， 肖 煒

(1.江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無(wú)錫 214122; 2.中國(guó)水產(chǎn)科學(xué)研究院 淡水漁業(yè)研究中心，江蘇 無(wú)錫 214081)

0 引 言

在水產(chǎn)養(yǎng)殖中，魚(yú)類的產(chǎn)量和質(zhì)量與池塘的水質(zhì)狀況息息相關(guān)，需要建立良好的無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor networks,WSNs)用于實(shí)時(shí)監(jiān)測(cè)養(yǎng)殖水域的水體參數(shù)[1]。而傳感器節(jié)點(diǎn)的部署一直是一個(gè)關(guān)鍵性的問(wèn)題，同時(shí)網(wǎng)絡(luò)覆蓋率也是衡量網(wǎng)絡(luò)優(yōu)劣的重要指標(biāo)之一[2]。

傳統(tǒng)的網(wǎng)絡(luò)覆蓋算法主要有3種：虛擬力法、Voronoi圖法和Delaunay三角剖分法[3],均存在各自的不足之處：基于虛擬力法的前提是假定初始節(jié)點(diǎn)分布密集[4]，通過(guò)力的排斥作用實(shí)現(xiàn)均勻覆蓋，而實(shí)際工作中，既存在節(jié)點(diǎn)分布密集需要擴(kuò)散的區(qū)域，也存在分布稀疏需要收斂的區(qū)域。Voronoi圖法和Delaunay三角剖分法，均需要經(jīng)過(guò)較大的計(jì)算量[5]，導(dǎo)致能耗的增加。近年來(lái)，將群體智能算法應(yīng)用于WSNs覆蓋優(yōu)化，取得了不錯(cuò)成果[6]。人工蜂群(artificial bee colony，ABC)算法因?yàn)榫哂袆趧?dòng)分工和協(xié)作機(jī)制，算法更加靈活，易與其他技術(shù)結(jié)合，相較于其他群體智能算法有著更加廣泛的應(yīng)用[7]。但傳統(tǒng)的ABC算法存在著容易陷入局部最優(yōu)值發(fā)生過(guò)早收斂，后期收斂速度較慢等問(wèn)題[8]，不能直接與實(shí)際應(yīng)用相結(jié)合。

根據(jù)養(yǎng)殖魚(yú)塘WSNs分布情況，本文提出了改進(jìn)的ABC(improved ABC,IABC)算法，改進(jìn)后的算法在收斂精度和速度上均有明顯提升。應(yīng)用于WSNs之后，加快了網(wǎng)絡(luò)的部署速度，提高了網(wǎng)絡(luò)覆蓋率，同時(shí)也改善了網(wǎng)絡(luò)的穩(wěn)定性。

1 WSNs覆蓋問(wèn)題

1.1 問(wèn)題假設(shè)

1)假設(shè)監(jiān)測(cè)區(qū)域是一個(gè)面積為A的平面矩形，將其離散化為m×n個(gè)像素點(diǎn)，可以用像素點(diǎn)的覆蓋情況表示監(jiān)測(cè)區(qū)域內(nèi)WSNs覆蓋情況。

2)WSNs由同型傳感器節(jié)點(diǎn)S1,S2,…,Sn構(gòu)成，各傳感器節(jié)點(diǎn)具有相同的發(fā)射功率和監(jiān)測(cè)半徑。

3)WSNs節(jié)點(diǎn)位置初始隨機(jī)部署，在迭代過(guò)程中可以動(dòng)態(tài)移動(dòng)。

4)為了方便計(jì)算，傳感器覆蓋模型采用“0～1”模型[9]。

1.2 節(jié)點(diǎn)覆蓋率計(jì)算

假設(shè)傳感器節(jié)點(diǎn)Si的監(jiān)測(cè)半徑為Rs，位置為(xi,yi)，目標(biāo)點(diǎn)p的位置為(xp,yp)，Si和p之間的歐氏距離記為

(1)

p被Si覆蓋的概率為

(2)

p在傳感器網(wǎng)絡(luò)中被覆蓋的概率為

(3)

WSNs的覆蓋率可以表示為

(4)

2 IABC算法

采用啟發(fā)式搜索策略的ABC算法有3個(gè)蜂種，在一定條件下又可以相互轉(zhuǎn)化，使算法不僅能夠進(jìn)行局部搜索，同時(shí)也具有全局尋優(yōu)能力[10～12]。但也存在局部搜索能力不強(qiáng)、收斂速度不快、容易陷入局部最優(yōu)等。針對(duì)上述缺點(diǎn)，同時(shí)結(jié)合養(yǎng)殖魚(yú)塘WSNs部署實(shí)際，對(duì)ABC算法進(jìn)行改進(jìn)，IABC算法如下：

1)引入覆蓋因子CovRate(i)，改進(jìn)觀察蜂選擇算子。

由圖1可以看出，初始時(shí)傳感器節(jié)點(diǎn)分布不均勻，在一部分區(qū)域“扎堆”現(xiàn)象嚴(yán)重，在另一部分區(qū)域卻存在“真空地帶”，形成覆蓋盲區(qū)。理想化的分布情況是，絕大部分監(jiān)測(cè)區(qū)域僅被1只傳感器節(jié)點(diǎn)覆蓋，存在少部分監(jiān)測(cè)點(diǎn)被 2只傳感器節(jié)點(diǎn)同時(shí)覆蓋。因此，觀察蜂在選擇蜜源時(shí)，應(yīng)當(dāng)優(yōu)先選擇覆蓋重合率較高的區(qū)域。為此引入傳感器覆蓋因子CovRate(i)，改進(jìn)觀察蜂概率選擇公式，CovRate(i)的定義為

(5)

式中N(i)為在傳感器節(jié)點(diǎn)i監(jiān)測(cè)半徑范圍內(nèi)，其他傳感器節(jié)點(diǎn)的個(gè)數(shù);A為在當(dāng)前分布情況下，覆蓋重合率最高的傳感器節(jié)點(diǎn)周圍其他傳感器節(jié)點(diǎn)的個(gè)數(shù)。

圖1 傳感器節(jié)點(diǎn)隨機(jī)分布情況

改進(jìn)后的觀察蜂選擇算子重新定義為

(6)

式中B，C為待定系數(shù)，取值根據(jù)傳感器分布情況動(dòng)態(tài)變化，計(jì)算如下

(7)

突出了覆蓋因子的作用，保證了覆蓋重合率較高的蜜源具有較高的被選擇概率。

2)結(jié)合反饋策略，改進(jìn)采蜜蜂搜索過(guò)程。

(8)

產(chǎn)生新蜜源

(9)

(10)

3)采用基于當(dāng)前最優(yōu)值的自適應(yīng)偵查策略。

由經(jīng)驗(yàn)易知：當(dāng)算法的當(dāng)前最優(yōu)值Max(i)遠(yuǎn)小于理論最優(yōu)值TheVal(i)時(shí)，應(yīng)當(dāng)提高收斂速度，加大搜索步長(zhǎng)；而當(dāng)Max(i)與TheVal(i)相接近時(shí)，則應(yīng)當(dāng)提高收斂精度，減小搜索步長(zhǎng)。所以采用自適應(yīng)的偵查策略，改進(jìn)采蜜蜂變異公式

(11)

式中α為縮放因子，取值如式(12)

α=(1-Max(i))×3

(12)

該搜索策略，兼顧了算法的收斂速度與精度，更具有合理性。

圖2 改進(jìn)后的采蜜蜂搜索策略

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

3.1 IABC用于傳感器節(jié)點(diǎn)部署步驟

如圖1，假設(shè)監(jiān)測(cè)區(qū)域?yàn)橐粋€(gè)100 m×100 m的平面區(qū)域，在該區(qū)域內(nèi)隨機(jī)放置45個(gè)同型傳感器，每個(gè)傳感器節(jié)點(diǎn)的監(jiān)測(cè)半徑為10 m。算法均在主頻為3.2 GHz的Windows操作系統(tǒng)下，基于MATLAB 2012a仿真實(shí)驗(yàn)平臺(tái)實(shí)現(xiàn)。算法最高迭代次數(shù)100次。

1)初始化種群數(shù)量為90，其中采蜜蜂的數(shù)量和觀察蜂的數(shù)量相等均為45，設(shè)置迭代次數(shù)為100，蜜源最大開(kāi)采度為10，計(jì)算初始時(shí)網(wǎng)絡(luò)覆蓋率。

2)采蜜蜂按照式(11)在鄰域內(nèi)搜索新蜜源，并計(jì)算此時(shí)的覆蓋率。

3)比較新舊蜜源的覆蓋率，取覆蓋率較高的蜜源，并記錄此時(shí)的位置。

4)觀察蜂按照式(6)選擇蜜源，并按照式(11)在蜜源鄰域內(nèi)尋找新的蜜源，同樣計(jì)算比較新舊蜜源的覆蓋率，取較高的一個(gè)，并記錄此時(shí)蜜源的位置。

5)如果一個(gè)蜜源的位置經(jīng)過(guò)10次均未更新，則該位置的采蜜蜂變?yōu)閭刹榉洌S機(jī)產(chǎn)生一個(gè)新蜜源。若新蜜源使得網(wǎng)絡(luò)的覆蓋率增大，則用新蜜源代替舊蜜源；否則，保留原位置。

6)重復(fù)步驟(2)～步驟(5)，直到達(dá)到最高迭代次數(shù)或網(wǎng)絡(luò)的覆蓋率達(dá)到100 %。

3.2 實(shí)驗(yàn)結(jié)果比較與分析

將ABC算法與IABC各自獨(dú)立運(yùn)行20次，比較2種算法的優(yōu)劣，運(yùn)行結(jié)果如表1所示。

表1 2種算法運(yùn)行結(jié)果比較

由表1數(shù)據(jù)分析可知，引入反饋策略的IABC算法，搜索效率更高，明顯提升了網(wǎng)絡(luò)覆蓋率。同時(shí)，由于IABC算法具有自適應(yīng)性，得到的標(biāo)準(zhǔn)差較小，說(shuō)明網(wǎng)絡(luò)更加穩(wěn)定。經(jīng)過(guò)100次IABC算法迭代的傳感器節(jié)點(diǎn)分布和IABC算法、ABC算法在迭代過(guò)程中傳感器覆蓋率，結(jié)果如圖3和圖4所示。可以看出：IABC算法引入覆蓋因子CovRate(i)后，搜索速度更快，經(jīng)過(guò)10次左右的迭代，達(dá)到了ABC算法100次迭代之后的網(wǎng)絡(luò)覆蓋率，大幅減少了WSNs的部署時(shí)間。

圖3 算法迭代完成后傳感器節(jié)點(diǎn)分布情況

圖4 傳感器網(wǎng)絡(luò)覆蓋率

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

提出了一種基于IABC算法的WSNs覆蓋優(yōu)化方法。仿真實(shí)驗(yàn)結(jié)果表明：方法可以加快WSNs的部署速度，提高網(wǎng)絡(luò)的穩(wěn)定性和覆蓋率。目前，該方法已經(jīng)在國(guó)家羅非魚(yú)產(chǎn)業(yè)技術(shù)研發(fā)中心無(wú)錫育種和保種基地得到了廣泛應(yīng)用，經(jīng)過(guò)一年多的實(shí)踐表明：該方法省時(shí)高效、穩(wěn)定性高，大幅提升了水產(chǎn)養(yǎng)殖基地的智能化、精準(zhǔn)化、信息化水平，具有良好的應(yīng)用前景。

參考文獻(xiàn):

[1] 吳 濱，黃慶展，毛 力.基于物聯(lián)網(wǎng)的水產(chǎn)養(yǎng)殖水質(zhì)監(jiān)控系統(tǒng)設(shè)計(jì)[J].傳感器與微系統(tǒng),2016,35(11):1-4.

[2] 錢志鴻,王義君.面向物聯(lián)網(wǎng)的無(wú)線傳感器網(wǎng)絡(luò)綜述[J].電子與信息學(xué)報(bào),2013,35(1):215-227.

[3] 黨小超， 沈思成， 郝占軍.WSNs中基于虛擬力的移動(dòng)覆蓋算法[J].計(jì)算機(jī)工程與應(yīng)用,2016,52(11):88-93.

[4] 張 濤， 余翔宇， 藍(lán)俊健.改進(jìn)的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)虛擬力部署方法[J].計(jì)算機(jī)應(yīng)用研究,2015,32(11):3356-3358，3363.

[5] 方 偉，宋鑫宏.基于Voronoi圖盲區(qū)的無(wú)線傳感器網(wǎng)絡(luò)覆蓋控制部署策略[J].物理學(xué)報(bào),2014,63(22):132-141.

[6] Xiao Y，Chen H，Wu K.Coverage and detection of a randomized scheduling algorithm in wireless sensor networks[J].IEEE Tran-sactions on Computers,2009,59(4):507-521.

[7] Karaboga D，Akay B．A survey：Algorithms simulating bee swarm intelligence[J]．Artificial Intelligence Review，2009，31(1-4):61-85．

[8] 羅 鈞,李 妍.具有混沌搜索策略的蜂群優(yōu)化算法[J].控制與決策,2010,25(12): 1913-1916.

[9] 孟凡治,王換招，何 暉.基于聯(lián)合感知模型的無(wú)線傳感器網(wǎng)絡(luò)連通性覆蓋協(xié)議[J].電子學(xué)報(bào),2011,39(4):772-779.

[10] Karaboga D.An idea based on honey bee swarm for numerical optimization[R]. Kayseri,Turkey:Erciyes University,2005.

[11] 江銘炎,袁東風(fēng).人工蜂群算法及其應(yīng)用[M].北京：科學(xué)出版社，2014:11.

[12] 張榮博，曹建福.利用蟻群優(yōu)化的非均勻分簇?zé)o線傳感器網(wǎng)絡(luò)路由算法[J]. 西安交通大學(xué)學(xué)報(bào),2010,44(6):33-38.