胡 堅，胡峰俊，張 紅，朱 穎

(1.浙江經(jīng)貿(mào)職業(yè)技術(shù)學(xué)院 信息技術(shù)系， 浙江 杭州 310018； 2.浙江樹人大學(xué) 信息科技學(xué)院，浙江 杭州310015)

無線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSNs)是一種分布式傳感網(wǎng)絡(luò)，它的末梢是可以感知和檢查一定范圍的靜止或移動的傳感器節(jié)點(diǎn)[1-2]。WSNs中的傳感器通過無線方式通信，可以跟互聯(lián)網(wǎng)進(jìn)行有線或無線方式的連接進(jìn)而形成一個多跳的自組織網(wǎng)絡(luò)系統(tǒng)，由于其密集型和隨機(jī)分布等特點(diǎn)，被廣泛應(yīng)用于環(huán)境監(jiān)測、醫(yī)療護(hù)理、目標(biāo)跟蹤及交通控制等領(lǐng)域[3-6]。傳統(tǒng)傳感器節(jié)點(diǎn)部署的隨機(jī)性和盲目性使傳感器對目標(biāo)區(qū)域不能進(jìn)行有效合理的監(jiān)測，合理的傳感器部署方案成為WSNs系統(tǒng)中重點(diǎn)關(guān)注的環(huán)節(jié)。

傳感器網(wǎng)絡(luò)部署是一個優(yōu)化問題[7]。一個水質(zhì)監(jiān)測系統(tǒng)要實現(xiàn)好的監(jiān)測效果需要對水質(zhì)監(jiān)測無線傳感器進(jìn)行合理的部署。目前，眾多研究者對WSNs網(wǎng)絡(luò)部署進(jìn)行了深入研究，針對不同水域情況，采用適當(dāng)優(yōu)化策略對特定區(qū)域的傳感器節(jié)點(diǎn)進(jìn)行部署，在保證傳感器覆蓋率最大化的條件下，盡可能少地使用傳感器，實現(xiàn)資源的最大化利用?；艋刍鄣萚8-9]用果蠅算法和魚群算法對傳感器節(jié)點(diǎn)進(jìn)行優(yōu)化布局，并取得了不錯的效果；劉維亭等[10]采用混沌粒子群算法覆蓋優(yōu)化無線傳感器網(wǎng)絡(luò)，該算法的尋優(yōu)速度較快，但仍舊沒有擺脫粒子群算法易陷入局部極值點(diǎn)的缺點(diǎn)；彭麗英[11]提出了基于改進(jìn)的蟻群算法優(yōu)化網(wǎng)絡(luò)節(jié)點(diǎn)，該方法局部搜索能力強(qiáng)，但搜索速度較慢。隨著優(yōu)化算法研究的深入，越來越多的優(yōu)化技術(shù)應(yīng)用于WSNs網(wǎng)絡(luò)優(yōu)化部署中。

布谷鳥搜索(cuckoo search， CS)算法是一種全局性能優(yōu)異的群智能優(yōu)化算法[12]。為進(jìn)一步提升CS算法的全局優(yōu)化性能，提出Momentum-CS、RMSprop-CS與Adam-CS三種改進(jìn)算法，并將其應(yīng)用于水質(zhì)監(jiān)測無線傳感器網(wǎng)絡(luò)優(yōu)化部署，以無線傳感器網(wǎng)絡(luò)覆蓋率最大為優(yōu)化目標(biāo)，布谷鳥個體作為單個傳感器，模擬雛鳥不被寄主發(fā)現(xiàn)的過程。仿真結(jié)果表明，改進(jìn)的布谷鳥搜索算法在水質(zhì)監(jiān)測無線傳感器網(wǎng)絡(luò)優(yōu)化部署問題中效果提升明顯，驗證了采用改進(jìn)布谷鳥搜索算法的有效性。

圖1 無線傳感器部署示意圖Fig.1 Schematic diagram of wireless sensor deployment

1 傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署模型

無線傳感器網(wǎng)絡(luò)在水下環(huán)境監(jiān)測應(yīng)用廣泛，圖1所示為水質(zhì)監(jiān)測無線傳感器節(jié)點(diǎn)部署示意圖。在無線傳感器節(jié)點(diǎn)部署問題中，通常采用增加傳感器數(shù)量以提高水域環(huán)境中的網(wǎng)絡(luò)覆蓋問題。然而部署過多傳感器會產(chǎn)生大量冗余節(jié)點(diǎn)，造成數(shù)據(jù)傳輸沖突，浪費(fèi)資源且影響網(wǎng)絡(luò)穩(wěn)定性。因此，在傳感器網(wǎng)絡(luò)布局階段，同時考慮節(jié)點(diǎn)數(shù)目和網(wǎng)絡(luò)覆蓋率。

假設(shè)每個傳感器都有相同的通信半徑和感知半徑，設(shè)s={s1，s2，s3…sn}是一組無線傳感器集合，(xi，yi)為集合中任意一個無線傳感器節(jié)點(diǎn)si的坐標(biāo)，(xj，yj)為監(jiān)測區(qū)域中任意一點(diǎn)sj的坐標(biāo)，則節(jié)點(diǎn)si到點(diǎn)sj的歐氏距離定義為：

(1)

將監(jiān)測區(qū)域A離散化為個網(wǎng)格點(diǎn)，坐標(biāo)為(x，y)的K點(diǎn)，判斷K點(diǎn)是否被傳感器節(jié)點(diǎn)si所覆蓋，可用式(2)表示：

(2)

對任意的坐標(biāo)點(diǎn)(x，y)，只要節(jié)點(diǎn)C集中存在一個傳感器節(jié)點(diǎn)使得pcov(x，y，ci)=1，則說明該點(diǎn)至少被一個傳感器節(jié)點(diǎn)所覆蓋，則節(jié)點(diǎn)集的聯(lián)合測量覆蓋率Pcov(C)為：

(3)

再把小格點(diǎn)簡化成網(wǎng)格點(diǎn)后，無線傳感器網(wǎng)絡(luò)覆蓋率定義為被發(fā)現(xiàn)的網(wǎng)格個數(shù)占總網(wǎng)格個數(shù)的比例，即：

(4)

為便于采用優(yōu)化算法解決水質(zhì)監(jiān)測無線傳感器網(wǎng)絡(luò)優(yōu)化部署問題，定義目標(biāo)函數(shù)如下：

(5)

2 布谷鳥搜索算法

布谷鳥搜索(cuckoo search， CS)算法是由英國學(xué)者Yang于2009年受布谷鳥巢寄生育雛行為的啟發(fā)提出的群智能優(yōu)化算法[13]。CS算法通過模擬布谷鳥巢寄生育雛行為，結(jié)合鳥類、果蠅等的萊維飛行(Lévy flights)機(jī)制進(jìn)行尋優(yōu)操作，能夠快速有效地找到問題的最優(yōu)解。CS算法的關(guān)鍵參數(shù)僅為外來鳥蛋被發(fā)現(xiàn)的概率和種群數(shù)目，整個算法操作簡單、易于實現(xiàn)。CS算法利用萊維飛行進(jìn)行全局搜索，具有良好的全局尋優(yōu)能力。為了模擬布谷鳥尋窩的方式，需要設(shè)定以下3種理性的狀態(tài)：1)每只布谷鳥每次隨機(jī)選擇一個巢并且產(chǎn)生一個卵；2)在隨機(jī)選擇的一組寄生巢中，最好的寄生巢將會被保留到下一代；3)可利用的寄生巢數(shù)量是固定的，寄生巢的主人能發(fā)現(xiàn)一個外來鳥蛋的概率為Pa。

CS算法包括全局搜索的隨機(jī)游走和局部隨機(jī)游走，假設(shè)一個布谷鳥為x=[x1，x2，…，xD]，則全局搜索的隨機(jī)游走如式(6)所示[14]：

xg+1，i=xg，i+?⊕L(ψ) (i=1，2，…n)。

(6)

其中：xg，i表示個鳥巢在第g代的鳥巢位置；⊕表示點(diǎn)對點(diǎn)乘法；?表示步長控制量即

?=?0(xg，i-xbest)。

(7)

其中：xbest為當(dāng)前最優(yōu)解；L(ψ)表示萊維隨機(jī)搜索路徑，其是一種隨機(jī)運(yùn)動，服從萊維概率分布：

Lévy～σ2=t-ψ(1≤ψ≤3)。

(8)

為方便計算，采用式(9)生成Lévy隨機(jī)數(shù)：

(9)

綜上，布谷鳥按式(10)更新位置：

(10)

CS算法按一定概率pa丟棄部分解后，采用式(11)局部隨機(jī)游走重新生成相同數(shù)量的新解:

xg+1，i=xg，i+r(xg，j-xg，k) 。

(11)

其中，r是縮放因子，是(0，1)區(qū)間內(nèi)的均勻分布隨機(jī)數(shù)；xg，i、xg，k表示g代的兩個隨機(jī)數(shù)。CS算法流程圖如圖2所示。

3 布谷鳥搜索算法的改進(jìn)

CS算法與其他群智能優(yōu)化算法一樣，其優(yōu)化性能仍存在提升空間。影響CS算法性能的是萊維飛行步長控制量和淘汰概率的選擇。CS算法中布谷鳥優(yōu)勝劣汰的過程是一個不斷迭代用優(yōu)的可行解取代較差可行解的過程，因此提出采用梯度下降法搜索全局最優(yōu)解的方法。本文通過用動量梯度下降法(gradientdescent with momentum)、均方根算法(root mean square prop)、Adam優(yōu)化算法(adam optimization algorithm)改進(jìn)CS算法以提升CS算法的全局優(yōu)化性能。

3.1 動量梯度下降法

圖2 CS算法流程圖Fig.2 CS algorithm flowchart

動量梯度下降法的基本思想是計算梯度的指數(shù)加權(quán)平均數(shù)，并利用該梯度更新權(quán)重。采用動量梯度下降法改進(jìn)布谷鳥搜索算法中萊維飛行步長，記作Momentum-CS。該算法中采用動量梯度下降思想更新萊維飛行步長，即每次步長的更新由前一步的步長變化和當(dāng)前階段的步長變化共同來決定，如式(12)所示：

Δlx=β1Δlx，t-1+(1-β1)Δlx，t

Δly=β1Δly，t-1+(1-β1)Δly，t

lx=l-ηΔlx

ly=l-ηΔly。

(12)

3.2 均方根算法

均方根算法(root mean square prop， RMSprop)是在梯度下降中，緩解縱向?qū)W習(xí)率且加速橫向?qū)W習(xí)率，使下降速度變快。采用均方根算法改進(jìn)布谷鳥搜索算法中萊維飛行步長，記作RMSprop-CS，如式(13)所示：

(13)

其中，dx表示步長在x軸方向的變化率；dy表示步長在y軸方向的變化率；β2是縮放因子；為防止分母為零，保證CS算法穩(wěn)定，ε是趨于0的正數(shù)。

3.3 Adam優(yōu)化算法

為結(jié)合動量梯度下降法與均方根算法的優(yōu)勢，采用Adam優(yōu)化算法進(jìn)行CS算法的改進(jìn)，記作Adam-CS。在Adam-CS中，改進(jìn)算法融合了動量梯度下降法與均方根算法，并增加修正偏差，在此基礎(chǔ)上，采用自適應(yīng)淘汰概率進(jìn)一步提升算法的性能。布谷鳥搜索算法中萊維飛行步長更新采用Adam思想：

(14)

由于Adam-CS算法迭代優(yōu)化過程存在噪聲干擾，隨著迭代次數(shù)的增加，固定淘汰概率值易導(dǎo)致優(yōu)化結(jié)果在最優(yōu)解附近擺動但不易精確收斂。通常情況，淘汰概率越小易使算法收斂到全局最優(yōu)解，較大的淘汰概率接受較大步伐?；诖耍O(shè)計式(15)所示自適應(yīng)淘汰概率，保證pa在迭代初期具有較大淘汰概率，迭代后期算法開始收斂時具有較小淘汰概率。

pa=0.95iterationpa，0。

(15)

其中，pa，0為初始淘汰概率；iteration為迭代次數(shù)，隨著iteration的增加，pa成指數(shù)下降。

4 仿真實驗

本文在監(jiān)測水域的二維平面內(nèi)，運(yùn)用布谷鳥搜索算法對節(jié)點(diǎn)進(jìn)行優(yōu)化部署。以網(wǎng)絡(luò)覆蓋率最優(yōu)為目標(biāo)，采用Adam-CS算法對水質(zhì)監(jiān)測無線傳感器節(jié)點(diǎn)部署進(jìn)行優(yōu)化，實現(xiàn)固定同構(gòu)無線傳感器節(jié)點(diǎn)下最大化覆蓋率。在長寬均為100 m的水域內(nèi)，以2 m為邊長劃分網(wǎng)格以計算覆蓋率。參數(shù)設(shè)置如下：傳感器半徑為10 m、迭代次數(shù)為200、最小覆蓋率為40%、初始淘汰概率為0.25、β1與β2均為0.9、ε為10～8。改進(jìn)的CS算法中，步長控制量與淘汰概率pa隨迭代次數(shù)變化。終止條件為滿足最大迭代次數(shù)或低于設(shè)定覆蓋率時結(jié)束優(yōu)化，獲得最優(yōu)解。

圖3所示為實驗隨機(jī)生成的30個傳感器節(jié)點(diǎn)，可以看出，原始傳感器分布雜亂，在隨機(jī)分配傳感器的條件下，覆蓋率比較低，只有52.17%，難以滿足實際工作中傳感器網(wǎng)絡(luò)全方位覆蓋的需求。

圖4為采用Adam-CS算法優(yōu)化之后的傳感器最優(yōu)位置分布圖?？梢钥闯觯瑑?yōu)化后的傳感器位置分布比較均勻，傳感器重合度降低，覆蓋率達(dá)到90.35%，根據(jù)優(yōu)化得到的水質(zhì)傳感器位置部署傳感器節(jié)點(diǎn)，可有效提高傳感器網(wǎng)絡(luò)的監(jiān)測性能。

圖3 傳感器網(wǎng)絡(luò)隨機(jī)分布Fig.3 Randomly distributed of the sensor network

圖4 Adam-CS算法傳感器優(yōu)化部署Fig.4 Adam-CS algorithm for sensor optimization deployment

進(jìn)一步驗證改進(jìn)CS算法的性能，采用CS、Momentum-CS、RMSprop-CS和Adam-CS四種算法進(jìn)行水質(zhì)傳感器部署優(yōu)化。4種算法均在相同區(qū)域面積部署相同數(shù)量及大小的水質(zhì)監(jiān)測無線傳感器節(jié)點(diǎn)。表1中記錄了20次獨(dú)立實驗獲取的性能指標(biāo)平均值。圖5為4種算法優(yōu)化傳感器網(wǎng)絡(luò)部署的網(wǎng)絡(luò)覆蓋率與迭代次數(shù)的變化曲線。

由表1可知，采用4種算法優(yōu)化水質(zhì)監(jiān)測無線傳感器節(jié)點(diǎn)部署取得的平均覆蓋率均高于隨機(jī)部署的52.17%，表明采用CS及改進(jìn)算法優(yōu)化水質(zhì)監(jiān)測無線傳感器節(jié)點(diǎn)部署是有效的。此外，對比表1中4種算法的優(yōu)化性能，Momentum-CS與RMSprop-CS相對CS算法的覆蓋率指標(biāo)均有提升，而Adam-CS算法的覆蓋率是最高的，達(dá)到90.35%，可見Adam-CS算法對于無線傳感器節(jié)點(diǎn)優(yōu)化部署問題效果最優(yōu)。由表1可知，Adam-CS算法平均耗時為57.4 s，優(yōu)化速度相對其余3種算法更快。圖5直觀地顯示出Adam-CS算法優(yōu)化無線傳感器節(jié)點(diǎn)部署取得的網(wǎng)絡(luò)覆蓋率最高、效率更優(yōu)。

為進(jìn)一步驗證Adam-CS算法優(yōu)化水質(zhì)監(jiān)測無線傳感器部署的性能，將Adam-CS算法優(yōu)化結(jié)果與EABC和ESCA算法[15]優(yōu)化結(jié)果進(jìn)行比較。監(jiān)測水域仍為長寬100 m的二維正方形平面，該水域中分別放入V=50和V=46個同構(gòu)傳感器節(jié)點(diǎn)，Adam-CS、EABC與ESCA優(yōu)化覆蓋率結(jié)果如表2所示。由表2可知，在V=50情況下，Adam-CS取得覆蓋率相比EABC算法提高了7.61%，很大程度上縮減了無線傳感器的覆蓋盲區(qū)。通過反復(fù)實驗得知，Adam-CS僅部署30個節(jié)點(diǎn)便使覆蓋率達(dá)到90.35%，相對減小了20個傳感器節(jié)點(diǎn)；何慶等[15]指出ESCA算法優(yōu)化達(dá)到98.58%的覆蓋率很接近，表現(xiàn)出優(yōu)異的優(yōu)化性能,能，本研究中Adam-CS的優(yōu)化結(jié)果與此相仿。綜上所述，Adam-CS算法能有效地進(jìn)行水質(zhì)監(jiān)測傳感器優(yōu)化部署。

表1 四種算法優(yōu)化性能對比

Table 1 Comparison of optimization performance of 4 algorithms

算法Algorithm平均覆蓋率Average coverage/%最高覆蓋率Maximum coverage/%最低覆蓋率Minimum coverage/%平均耗時Average time/s最大迭代數(shù)Maximum iterated algebraCS83.8986.4679.2192.3138M-CS86.9787.3982.9470.5100RM-CS87.6889.7784.3787.2135A-CS90.3592.2598.9757.498

M-CS，Momentum-CS；RM-CS，RMSprop-CS；A-CS，Adam-CS。

圖5 覆蓋率趨勢圖Fig.5 Coverage trend chart

表2 Adam-CS、EABC與ESCA優(yōu)化覆蓋率結(jié)果對比

Table 2 Comparison of Adam-CS， EABC and ESCA on optimized coverage results %

算法Algorithm覆蓋率CoverageV=50V=46A-CS98.4798.12EABC90.8690.86ESCA98.5897.26

5 結(jié)論

針對水質(zhì)監(jiān)測無線傳感器隨機(jī)部署網(wǎng)絡(luò)覆蓋率低的問題，采用CS算法進(jìn)行傳感器節(jié)點(diǎn)部署優(yōu)化。為了提升優(yōu)化性能，文章提出了Momentum-CS、RMSprop-CS與Adam-CS三種改進(jìn)算法，并將應(yīng)用于長寬為100 m水域的傳感器節(jié)點(diǎn)部署優(yōu)化仿真實驗。Adam-CS算法采用動量梯度下降法使尋優(yōu)過程易跳出局部最優(yōu)；同時，RMSprop-CS算法引入加快了尋優(yōu)過程中尋優(yōu)步長變化，且淘汰率自適應(yīng)改變都將有效改善CS算法優(yōu)化性能。仿真結(jié)果表明，Adam-CS算法能在98次迭代過程中獲得90.35%的網(wǎng)絡(luò)覆蓋率，改進(jìn)的布谷鳥搜索算法對于水環(huán)境監(jiān)測中無線傳感器節(jié)點(diǎn)部署具有指導(dǎo)意義。