改進人工蜂群算法在WSNs覆蓋優化中的應用*

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

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

0 引 言

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

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

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

1 WSNs覆蓋問題

1.1 問題假設

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

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

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

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

1.2 節點覆蓋率計算

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

(1)

p被Si覆蓋的概率為

(2)

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

(3)

WSNs的覆蓋率可以表示為

(4)

2 IABC算法

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

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

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

(5)

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

圖1 傳感器節點隨機分布情況

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

(6)

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

(7)

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

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

(8)

產生新蜜源

(9)

(10)

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

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

(11)

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

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

(12)

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

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

3 仿真實驗

3.1 IABC用于傳感器節點部署步驟

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

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

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

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

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

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

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

3.2 實驗結果比較與分析

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

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

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

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

圖4 傳感器網絡覆蓋率

4 結束語

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

參考文獻:

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

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

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

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

[5] 方 偉，宋鑫宏.基于Voronoi圖盲區的無線傳感器網絡覆蓋控制部署策略[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] 羅 鈞,李 妍.具有混沌搜索策略的蜂群優化算法[J].控制與決策,2010,25(12): 1913-1916.

[9] 孟凡治,王換招，何 暉.基于聯合感知模型的無線傳感器網絡連通性覆蓋協議[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] 張榮博，曹建福.利用蟻群優化的非均勻分簇無線傳感器網絡路由算法[J]. 西安交通大學學報,2010,44(6):33-38.