文獻標識碼: A
DOI:10.16157/j.issn.0258-7998.191073
中文引用格式: 申志平,孫茜,,王小藝,,等. 改進布谷鳥算法在水質傳感器部署上的應用[J].電子技術應用,2020,,46(3):76-79,,85.
英文引用格式: Shen Zhiping,Sun Qian,,Wang Xiaoyi,,et al. Application of improved cuckoo algorithm in water quality sensor deployment[J]. Application of Electronic Technique,2020,,46(3):76-79,,85.
0 引言
無線傳感器網(wǎng)絡(Wireless Sensor Networks,,WSNs)是一種分布式傳感網(wǎng)絡。WSNs中的傳感器通過無線方式通信,,可以與互聯(lián)網(wǎng)進行有線或無線方式的連接進而形成一個多跳的自組織網(wǎng)絡系統(tǒng)[1],。由于其密集型和隨機分布等特點,被廣泛應用于環(huán)境監(jiān)測,、醫(yī)療護理,、目標跟蹤及交通控制等領域[2-4]。由于傳統(tǒng)傳感器節(jié)點部署的隨機性和盲目性,,使傳感器對目標區(qū)域不能進行有效合理的監(jiān)測,,因此采用合理的傳感器部署方案成為WSNs應用中首先要考慮的問題。
傳感器網(wǎng)絡優(yōu)化部署是一個多目標優(yōu)化問題,,一個水質監(jiān)測系統(tǒng)要實現(xiàn)好的監(jiān)測效果需要對水質傳感器進行合理的部署,。目前,,國內外許多學者對WSNs的覆蓋部署進行了深入的研究,,其問題的關鍵是針對不同的水域情況,通過采用適當?shù)膬?yōu)化策略對特定區(qū)域的傳感器節(jié)點進行部署,,在保證傳感器覆蓋率最大化的條件下,,盡可能少地使用傳感器,達到資源的有效利用,。隨著群智能優(yōu)化算法的興起,,其越來越多地成為研究者關注的焦點。文獻[5]-[6]用果蠅算法和魚群算法對傳感器節(jié)點進行優(yōu)化布局,,并取得了不錯的效果,;文獻[7]提出了采用加權因子調整的粒子群算法對傳感器節(jié)點進行自適應部署,但算法中參數(shù)值的設定需根據(jù)經(jīng)驗值進行設定,;文獻[8]采用混沌粒子群算法覆蓋優(yōu)化無線傳感器網(wǎng)絡,,該算法的尋優(yōu)速度較快,但其仍舊沒有擺脫粒子群算法易陷入局部極值點的缺點,;文獻[9]提出了基于改進的蟻群算法優(yōu)化網(wǎng)絡節(jié)點,,該方法局部搜索能力強,,但搜索速度較慢;文獻[10]提出了把萊維飛行和粒子群相結合的算法來優(yōu)化傳感器節(jié)點,,該算法利用萊維飛行搜索的遍歷性大大提高了網(wǎng)絡的覆蓋率,,克服了傳統(tǒng)粒子群算法容易陷入局部最優(yōu)的缺點;文獻[11]提出分布式布谷鳥算法在無線傳感器網(wǎng)絡布局優(yōu)化中的應用,,證明了分布式布谷鳥算法在優(yōu)化時間上要強于粒子群算法,,但優(yōu)化精度不高;文獻[12]提出了一種可變參數(shù)的改進CS算法,,提高了收斂的速度,;文獻[13]提出了動態(tài)適應布谷鳥算法,對布谷鳥的發(fā)現(xiàn)概率和搜索步長進行動態(tài)調整,,使得算法的收斂速度和精度都得到了一定的改善,。
本文布谷鳥算法中用布谷鳥個體作為單個傳感器,模擬雛鳥不被寄主發(fā)現(xiàn)的過程,,將無線傳感器網(wǎng)絡中覆蓋率作為優(yōu)化目標,,布谷鳥優(yōu)勝劣汰的過程是一個不斷迭代,用好的可行解取代較差可行解的過程,,因此,,在這個過程中可以引入梯度下降求局部最優(yōu)解的方法。本文通過采用動量梯度下降法,、均方根算法,、Adam優(yōu)化算法等深度學習中常用的優(yōu)化算法的思想,通過更新節(jié)點的位置快速計算每次迭代的最優(yōu)解,,能夠有效提高問題的優(yōu)化效率,。
1 水質傳感器網(wǎng)絡覆蓋模型
在水質傳感器網(wǎng)絡覆蓋中,通常通過增加傳感器個數(shù)以提高覆蓋率,。然而傳感器節(jié)點個數(shù)過多,,會產生大量冗余節(jié)點,造成數(shù)據(jù)傳輸沖突,,影響網(wǎng)絡穩(wěn)定性,,且造成資源浪費。因此,,在水質傳感器網(wǎng)絡布局階段,,節(jié)點數(shù)目和網(wǎng)絡覆蓋率需要同時考慮。
本文在監(jiān)測水域的二維平面內,,運用布谷鳥算法對節(jié)點自行進行布置,,以實現(xiàn)對固定區(qū)域內最大覆蓋率為目標,在保證監(jiān)測數(shù)據(jù)有效的前提條件下,使傳感器資源得到進一步的利用,。假設每個傳感器都有相同的通信半徑和感知半徑[14],,設s={s1,s2,,s3,,…,sn}是一組無線傳感器集合,,(xi,,yi)為集合中任意一個無線傳感器節(jié)點si的坐標,(xj,,yj)為監(jiān)測區(qū)域中任意一點pj的坐標,,則節(jié)點si到點pj的歐氏距離定義為:
2 算法設計
布谷鳥搜索(Cuckoo Search,CS)算法是由英國學者Yang于2009年受布谷鳥巢寄生育雛行為的啟發(fā)提出的一種新型的群智能優(yōu)化算法,。CS算法通過模擬布谷鳥巢寄生育雛行為,,結合鳥類、果蠅等的Lévy飛行機制進行尋優(yōu)操作,,能夠快速有效地找到問題的最優(yōu)解,。CS算法的關鍵參數(shù)僅為外來鳥蛋被發(fā)現(xiàn)的概率和種群數(shù)目,整個算法操作簡單,、易于實現(xiàn),。CS算法利用Lévy飛行進行全局搜索,具有良好的全局尋優(yōu)能力,。
為了模擬布谷鳥尋窩的方式,,需要設定一下3種理性的狀態(tài):
(1)每只布谷鳥每次隨機選擇一個巢并且產生一個卵;
(2)在隨機選擇的一組寄生巢中,,最好的寄生巢將會被保留到下一代,;
(3)可利用的寄生巢數(shù)量是固定的,寄生巢的主人能發(fā)現(xiàn)一個外來鳥蛋的概率為Pa,。
布谷鳥算法中使用D維向量X=[X1,,X2,,…,,XD]表示每一個布谷鳥,結合了全局搜索的隨機游走和局部的隨機游走,,其中,,全局搜索的隨機游走如式(5)所示:
其中,r是縮放因子,,是(0,,1)區(qū)間內的隨機數(shù);Xg,i,,Xg,,k表示g代的兩個隨機數(shù)。CS算法流程如下:
(1)初始化種群,,用每一個D維向量代表一個巢穴,,同時計算出每個個體的適應度。
(2)更新每個巢穴,,按照式(9)產生新的解,,產生的新解比原來的解好,則用新解替代舊解,。
(3)對每個巢穴,,任選其他兩個不一樣的巢穴,對D維向量中的每個元素按照式(11)進行組合產生新解,,產生的新解比原來的解好,,則用新解替代舊解。
(4)記錄整個過程中的最優(yōu)解,,得到的最優(yōu)解不滿足設定的條件時返回步驟(2),,直到滿足條件或達到最大迭代次數(shù)則返回最優(yōu)解。
在布谷鳥算法中影響布谷鳥尋優(yōu)效率的是Lévy飛行步長控制量的選擇和淘汰概率,,本文基于深度學習優(yōu)化算法的思想來更新其參數(shù),。
3 基于深度學習的優(yōu)化算法更新Lévy飛行步長
在深度學習中,為解決目標函數(shù)的最小值,,常用梯度下降法進行優(yōu)化,,其基本思想是在每次迭代中,對每個變量,,按照目標函數(shù)在該變量梯度的相反方向,,更新對應的參數(shù)值,如式(12)所示:
其中,,J(θ)表示損失函數(shù),,η表示學習率,其決定了在沿著讓目標函數(shù)下降最大的方向上,,下降的步長有多大,。
本文根據(jù)動量梯度下降法(Gradient Descent with Momentum)、均方根算法(Root Mean Square prop)和Adam優(yōu)化算法(Adam Optimization Algorithm)來更新布谷鳥算法中Lévy飛行的步長,。
3.1 動量梯度下降法
動量梯度下降法的基本思想是計算梯度的指數(shù)加權平均數(shù),,并利用該梯度更新權重,如式(13)所示:
式中,,Vdw是速度更新的大小,,β1是權重,,Vt-1是t-1時刻的速度,Vt是當前時刻速度的大小,,η是動量梯度下降中的學習率,。
布谷鳥算法中Lévy飛行步長更新采用動量梯度下降法的思想,即每次步長的更新由前一步的步長變化和當前階段的步長變化共同來決定,,如式(14)所示:
其中,,Δl是步長更新的大小,Δlt-1是前一個時刻步長的更新,,η是步長更新的學習率,。
3.2 均方根算法
均方根算法的基本思想是在梯度下降中,想緩解縱軸方向的學習率,,然后加速橫軸方向的學習率,,則采用式(15)所示的微分平方的加權平均數(shù),使下降速度變快,。
其中,,Sdx為x方向上的速度變化,Sdy為 y方向上的速度變化,,β2是均方根中的權重,,α是均方根算法中的學習率,ε是一個防止分母為零的十分小的正向量矩陣,。通過改變Sdx和Sdy的大小來改變其在某一方向上的尋優(yōu)速度,。
本文布谷鳥算法中Lévy飛行步長更新采用均方根算法的思想,如式(16)所示:
其中,,Sdxy表示循環(huán)中每個個體到種群最優(yōu)位置距離的平均值,,Xg是尋優(yōu)中的每個個體位置,Xbest是種群的最優(yōu)位置,。
3.3 Adam優(yōu)化算法
Adam優(yōu)化算法基本上是將動量梯度下降法和均方根算法結合在一起,,且要加上修正偏差。本文布谷鳥算法中Lévy飛行步長更新采用Adam優(yōu)化算法的思想,,如式(17)所示:
式中,,ω為Adam中的學習率。由式(17)可以看出在Adam優(yōu)化算法中采用了動量梯度下降法的優(yōu)點,,使得在尋優(yōu)過程中可以跳出局部最優(yōu)解,,同時也吸收了均方根算法的優(yōu)點,加快了在尋優(yōu)方向上的搜尋步長,,減少了不利的擾動對尋優(yōu)過程造成的影響,。
4 更新淘汰概率Pa
在梯度下降法尋找最優(yōu)值的過程中,,因為噪音的存在,,隨著迭代次數(shù)的增加,,結果會在最優(yōu)解的附近擺動,不會精確地收斂,,此時的學習率是個固定值,,因此需要隨著迭代次數(shù)的增加慢慢減少學習率。
在本文布谷鳥算法的改進中淘汰概率Pa利用梯度下降的思想,,隨迭代次數(shù)的變化如式(18)所示:
5 仿真結果
5.1 實驗設計
本文采用基于深度學習的優(yōu)化方法改進布谷鳥算法對傳感器節(jié)點在監(jiān)測區(qū)域內進行網(wǎng)絡覆蓋率的最優(yōu)部署,,在100 m×100 m的水域內,以2 m為邊長劃分網(wǎng)格計算覆蓋率,。設定傳感器半徑為10 m,,最大迭代次數(shù)為1 000,初始淘汰概率設為0.25,,β1設置大小為0.1,,β2設置大小為1,ε設為10-4,,在本文算法中步長控制量以及淘汰概率Pa隨迭代次數(shù)變化,。迭代計算中,當?shù)螖?shù)大于最大迭代次數(shù)時跳出循環(huán),,則計算停止,,保存最優(yōu)結果退出布谷鳥更新過程。
5.2 實驗結果與分析
實驗中隨機生成30個傳感器節(jié)點,,圖1為原始的傳感器隨機分布圖,,X、Y為二維平面的橫縱坐標,。由圖1可以看出,,原始的傳感器分布比較雜亂,在隨機分配傳感器的條件下,,其覆蓋率比較低,只有59.64%,,實際工作中無法達到預期的監(jiān)測結果。
圖2為在隨機分布傳感器節(jié)點的條件下,,節(jié)點通過基于Adam算法改進的布谷鳥算法Adam-CS迭代更新之后的最優(yōu)位置分布圖,,在此分布條件下傳感器的覆蓋率達到最優(yōu)。從圖2中可以看出,,優(yōu)化后的傳感器節(jié)點分布比較均勻,,傳感器的重合度降低,覆蓋率達到86.48%,,進而使得水質傳感器節(jié)點部署得到優(yōu)化,,可有效提高傳感器網(wǎng)絡的監(jiān)測性能。
圖3為原始布谷鳥算法(CS),、基于動量梯度下降法改進的布谷鳥算法(Momentum-CS),、基于均方根算法改進的布谷鳥算法(RMSprop-CS)以及Adam-CS 4種方法的實驗對比圖,。在相同的區(qū)域面積部署相同數(shù)量及大小的傳感器節(jié)點??紤]到隨機部署的不確定性對實驗結果的影響,,對4種方法各進行了10次實驗,對實驗結果做均值處理,。由圖3可知,,在相同的初始條件下,Adam-CS算法可以更有效地提高網(wǎng)絡的部署效果,。隨著迭代次數(shù)的增加,,4條曲線趨于平衡,規(guī)定每增加30次迭代次數(shù)覆蓋率增長少于0.05%的情況下為曲線達到的平衡狀態(tài),,則4種方法的結果如表1所示,。可見,,Adam-CS算法可以利用更少的迭代次數(shù)實現(xiàn)更好的部署效果,。
6 結論
本文基于深度學習的優(yōu)化方法改進布谷鳥算法,以水質傳感器網(wǎng)絡覆蓋率達到最優(yōu)為目標,,對傳感器節(jié)點進行優(yōu)化部署,。在充分利用布谷鳥算法優(yōu)點的基礎上,對布谷鳥算法中的步長控制量和淘汰概率利用深度學習的優(yōu)化方法進行調整,,大大提高了算法的尋優(yōu)性能,。仿真結果表明,改進后的算法能高效地搜索全局空間,,獲得更加精確的結果,,實現(xiàn)了深度學習方法和群智能優(yōu)化算法的結合,同時把改進的算法應用在水質傳感器網(wǎng)絡的布局優(yōu)化中,,在水環(huán)境監(jiān)測中有一定的實踐意義,。
參考文獻
[1] 毛鶯池,陳力軍,,陳道蓄.無線傳感器網(wǎng)絡覆蓋控制技術研究[J].計算機科學,,2007,34(3):20-22.
[2] PUCCINELLI D,,HAENGGI M.Wireless sensor networks:applications and challenges of ubiquitous sensing[J].Circuits & Systems Magazine IEEE,,2005,5(3):19-31.
[3] 徐凱,,張秋菊,,李克修,等.基于ZigBee的水產養(yǎng)殖無線監(jiān)控系統(tǒng)設計[J].電子技術應用,,2012,,38(4):67-69.
[4] 李建勇,,李洋,劉雪梅.基于ZigBee的糧庫環(huán)境監(jiān)控系統(tǒng)設計[J].電子技術應用,,2016,,42(1):65-67.
[5] 霍慧慧,,李國勇.改進的離散果蠅優(yōu)化算法在WSNs覆蓋中的應用[J].傳感器與微系統(tǒng),,2016,35(2):157-160.
[6] 何旭,,彭珍瑞,,董海棠,等.加權質心魚群算法在WSNs節(jié)點優(yōu)化布置中的應用[J].傳感器與微系統(tǒng),,2018,,37(10):157-160.
[7] 余幸運,孫茜,,王小藝,,等.基于粒子群優(yōu)化算法的水質傳感器優(yōu)化部署研究[J].傳感器與微系統(tǒng),2016,,35(12):30-32.
[8] 劉維亭,,范洲遠.基于混沌粒子群算法的無線傳感器網(wǎng)絡覆蓋優(yōu)化[J].計算機應用,2011,,31(2):338-340.
[9] 彭麗英.改進的蟻群算法網(wǎng)絡節(jié)點覆蓋優(yōu)化研究[J].計算機仿真,,2011,28(9):151-153.
[10] 盧玲,,謝佳華.萊維飛行的粒子群優(yōu)化算法在WSNs覆蓋增強中的應用[J].傳感器與微系統(tǒng),,2015,34(11):157-160.
[11] 劉小壘,,張小松.分布式布谷鳥算法在無線傳感器網(wǎng)絡布局優(yōu)化中的應用[J].計算機應用研究,,2018,35(7):2063-2065.
[12] 王稼磊,,張會紅,,汪鵬君,等.基于參數(shù)自適應布谷鳥算法的RM電路面積優(yōu)化[J].計算機應用研究,,2018,,35(9):135-137,141.
[13] 明波,,黃強,,王義民,等.基于改進布谷鳥算法的梯級水庫優(yōu)化調度研究[J].水利學報,,2015,,46(3):341-349.
[14] 劉偉,,胡安林.無線傳感器網(wǎng)絡覆蓋率與節(jié)能性研究[J].電子技術應用,2016,,42(6):98-100.
作者信息:
申志平,,孫 茜,王小藝,,許繼平,,張慧妍,王 立
(北京工商大學 計算機與信息工程學院,,北京100048)