改進人工蜂群算法在WSNs覆蓋優(yōu)化中的應用*

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

(1.江南大學 物聯網工程學院，江蘇 無錫 214122; 2.中國水產科學研究院 淡水漁業(yè)研究中心，江蘇 無錫 214081)

0 引 言

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

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

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

1 WSNs覆蓋問題

1.1 問題假設

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

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

3)WSNs節(jié)點位置初始隨機部署，在迭代過程中可以動態(tài)移動。

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

1.2 節(jié)點覆蓋率計算

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

(1)

p被Si覆蓋的概率為

(2)

p在傳感器網絡中被覆蓋的概率為

(3)

WSNs的覆蓋率可以表示為

(4)

2 IABC算法

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

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

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

(5)

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

圖1 傳感器節(jié)點隨機分布情況

改進后的觀察蜂選擇算子重新定義為

(6)

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

(7)

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

2)結合反饋策略，改進采蜜蜂搜索過程。

(8)

產生新蜜源

(9)

(10)

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

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

(11)

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

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

(12)

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

圖2 改進后的采蜜蜂搜索策略

3 仿真實驗

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

如圖1，假設監(jiān)測區(qū)域為一個100 m×100 m的平面區(qū)域，在該區(qū)域內隨機放置45個同型傳感器，每個傳感器節(jié)點的監(jiān)測半徑為10 m。算法均在主頻為3.2 GHz的Windows操作系統(tǒng)下，基于MATLAB 2012a仿真實驗平臺實現。算法最高迭代次數100次。

1)初始化種群數量為90，其中采蜜蜂的數量和觀察蜂的數量相等均為45，設置迭代次數為100，蜜源最大開采度為10，計算初始時網絡覆蓋率。

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

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

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

5)如果一個蜜源的位置經過10次均未更新，則該位置的采蜜蜂變?yōu)閭刹榉?，隨機產生一個新蜜源。若新蜜源使得網絡的覆蓋率增大，則用新蜜源代替舊蜜源；否則，保留原位置。

6)重復步驟(2)～步驟(5)，直到達到最高迭代次數或網絡的覆蓋率達到100 %。

3.2 實驗結果比較與分析

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

表1 2種算法運行結果比較

由表1數據分析可知，引入反饋策略的IABC算法，搜索效率更高，明顯提升了網絡覆蓋率。同時，由于IABC算法具有自適應性，得到的標準差較小，說明網絡更加穩(wěn)定。經過100次IABC算法迭代的傳感器節(jié)點分布和IABC算法、ABC算法在迭代過程中傳感器覆蓋率，結果如圖3和圖4所示?？梢钥闯觯篒ABC算法引入覆蓋因子CovRate(i)后，搜索速度更快，經過10次左右的迭代，達到了ABC算法100次迭代之后的網絡覆蓋率，大幅減少了WSNs的部署時間。

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

圖4 傳感器網絡覆蓋率

4 結束語

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

參考文獻:

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

[2] 錢志鴻,王義君.面向物聯網的無線傳感器網絡綜述[J].電子與信息學報,2013,35(1):215-227.

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

[4] 張 濤， 余翔宇， 藍俊健.改進的無線傳感器網絡節(jié)點虛擬力部署方法[J].計算機應用研究,2015,32(11):3356-3358，3363.

[5] 方 偉，宋鑫宏.基于Voronoi圖盲區(qū)的無線傳感器網絡覆蓋控制部署策略[J].物理學報,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] 孟凡治,王換招，何 暉.基于聯合感知模型的無線傳感器網絡連通性覆蓋協(xié)議[J].電子學報,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] 江銘炎,袁東風.人工蜂群算法及其應用[M].北京：科學出版社，2014:11.

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