基于改進(jìn)鯨魚優(yōu)化算法的傳感網(wǎng)絡(luò)節(jié)點(diǎn)移動(dòng)策略*

張?zhí)K穎，竺興妹，許曙青

(1.江蘇聯(lián)合職業(yè)技術(shù)學(xué)院南京工程分院電子工程系，江蘇 南京 210035；2.中國礦業(yè)大學(xué)經(jīng)濟(jì)與管理學(xué)院，江蘇 徐州 221116)

在信息處理與無線通信技術(shù)的高速發(fā)展背景下，傳感網(wǎng)絡(luò)已經(jīng)廣泛應(yīng)用在環(huán)境監(jiān)測等領(lǐng)域，主要特征為:無中心節(jié)點(diǎn)，所有節(jié)點(diǎn)擁有相同地位，修復(fù)與重構(gòu)能力較強(qiáng)，可適應(yīng)動(dòng)態(tài)拓?fù)洌煌ㄐ欧秶芟?，由于?jié)點(diǎn)處于不斷變化的狀態(tài)，任意一個(gè)節(jié)點(diǎn)的計(jì)算、儲(chǔ)存與通信能力都是有限的，只能實(shí)現(xiàn)近距離感知；多跳路由，無需專業(yè)路由設(shè)施，普通節(jié)點(diǎn)即可實(shí)現(xiàn)路由功能，既能扮演數(shù)據(jù)始發(fā)者的角色，也能承擔(dān)轉(zhuǎn)發(fā)者的任務(wù)。但傳感網(wǎng)絡(luò)需要大量節(jié)點(diǎn)協(xié)同合作，工作環(huán)境通常比較復(fù)雜。因此，如何最大程度覆蓋目標(biāo)區(qū)域，高效實(shí)現(xiàn)環(huán)境感知對建設(shè)傳感網(wǎng)絡(luò)具有重大意義。

近年來，節(jié)點(diǎn)移動(dòng)策略在傳感網(wǎng)絡(luò)覆蓋優(yōu)化問題中獲得廣大學(xué)者關(guān)注，國內(nèi)外學(xué)者紛紛對傳感網(wǎng)絡(luò)節(jié)點(diǎn)移動(dòng)策略做出了研究。楊海波等人[1]提出基于信噪比-虛擬力的節(jié)點(diǎn)移動(dòng)方法探究，綜合分析信道傳輸特征，建立信噪比模型；結(jié)合信噪比與節(jié)點(diǎn)度兩個(gè)指標(biāo)修正虛擬力模型，得出對應(yīng)節(jié)點(diǎn)移動(dòng)策略。Habib等人[2]提出基于節(jié)能移動(dòng)性簇頭選擇機(jī)制的節(jié)點(diǎn)移動(dòng)算法。利用CH選擇算法選擇對傳感器能耗有巨大影響的專用參數(shù)。根據(jù)節(jié)點(diǎn)的移動(dòng)水平、剩余能量、下沉距離和鄰居密度計(jì)算每個(gè)節(jié)點(diǎn)的權(quán)重。當(dāng)?shù)螖?shù)最大時(shí)輸出全局最優(yōu)解，即節(jié)點(diǎn)移動(dòng)位置。向庭立等人[3]提出基于布谷鳥搜索的混合傳感器網(wǎng)絡(luò)節(jié)點(diǎn)移動(dòng)策略，基于混雜傳感節(jié)點(diǎn)在目標(biāo)區(qū)域內(nèi)隨機(jī)部署，初步確定移動(dòng)傳感器節(jié)點(diǎn)的候選目標(biāo)位置，并用位置優(yōu)化方法求取最優(yōu)目標(biāo)位置，實(shí)現(xiàn)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)移動(dòng)位置優(yōu)化。Thomson等人[4]提出基于移動(dòng)感知任務(wù)循環(huán)和動(dòng)態(tài)前導(dǎo)算法的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)移動(dòng)策略。根據(jù)靜態(tài)節(jié)點(diǎn)建立的閾值與移動(dòng)宿節(jié)點(diǎn)的位置之間的關(guān)系，做出與節(jié)點(diǎn)休眠功能、轉(zhuǎn)向清除信道評估和隨后發(fā)送前同步碼相關(guān)的決策。

雖然上述算法較大程度覆蓋了監(jiān)測區(qū)域，但也存在一定盲區(qū)，且節(jié)點(diǎn)移動(dòng)總路程較長，會(huì)造成能耗與成本的浪費(fèi)?；诖耍疚睦酶倪M(jìn)鯨魚算法在傳感網(wǎng)絡(luò)中設(shè)計(jì)一種新的節(jié)點(diǎn)移動(dòng)策略，鯨魚算法屬于高度智能算法，具有較強(qiáng)的尋優(yōu)能力，但也容易陷入局部最優(yōu)，降低算法搜索性能。為此，本文構(gòu)建傳感網(wǎng)絡(luò)節(jié)點(diǎn)與信道基本模型，設(shè)置自適應(yīng)步長參數(shù)改進(jìn)鯨魚算法，提升局部與全局的搜索能力，并將該算法用于構(gòu)建的傳感網(wǎng)絡(luò)節(jié)點(diǎn)與信道基本模型中，計(jì)算大量節(jié)點(diǎn)位置并優(yōu)化，得到了較好的傳感網(wǎng)絡(luò)節(jié)點(diǎn)移動(dòng)策略。

1 傳感網(wǎng)絡(luò)節(jié)點(diǎn)與信道基本模型建立

1.1 節(jié)點(diǎn)模型

如果在某傳感網(wǎng)絡(luò)中布置N個(gè)節(jié)點(diǎn)，所有節(jié)點(diǎn)的覆蓋半徑Rcov均一致，那么在實(shí)際環(huán)境下，傳感器能夠獲取以自身為圓心，Rcov半徑范圍內(nèi)的監(jiān)測數(shù)據(jù)，且所有節(jié)點(diǎn)都存在同樣大小的通信半徑Rcom。為方便表示網(wǎng)絡(luò)節(jié)點(diǎn)之間相互連接情況，利用0-1的連通矩陣T＝(tij)N×N，該矩陣中各元素表示意義如下:當(dāng)tij＝1時(shí)，代表位置為i的傳感器能夠和位置為j的傳感器通信，當(dāng)tij＝0時(shí)則說明兩個(gè)傳感器之間無法通信。

上述兩個(gè)傳感器節(jié)點(diǎn)的坐標(biāo)分別描述成(xci，yci，zci)和(xcj，ycj，zcj)，其中，i＝1，2，…，N，j＝1，2，…，N。連通矩陣元素表達(dá)式為:

將節(jié)點(diǎn)通信區(qū)間內(nèi)鄰居節(jié)點(diǎn)數(shù)目當(dāng)作節(jié)點(diǎn)度[5]，則位置為i的節(jié)點(diǎn)度ndi表達(dá)式為:

覆蓋率屬于傳感節(jié)點(diǎn)布置和節(jié)點(diǎn)移動(dòng)方法的重要指標(biāo)，為準(zhǔn)確表現(xiàn)出網(wǎng)絡(luò)的覆蓋情況，將網(wǎng)絡(luò)劃分為K×M×L的長方體網(wǎng)格。利用覆蓋矩陣維數(shù)P表示網(wǎng)格點(diǎn)的整體數(shù)量[6]，計(jì)算公式如下:

建立下述覆蓋矩陣:

矩陣中，若fij＝1代表位于i處的傳感器能夠感知j處的數(shù)據(jù)；若fij＝0則表示該傳感器無法感知j處的數(shù)據(jù)。

兩個(gè)位置的傳感器探測點(diǎn)坐標(biāo)描述為(xgi，ygi，zgi)和(xgj，ygj，zgj)，則覆蓋矩陣元素表達(dá)式為:

分析覆蓋矩陣F＝(fij)N×P，能夠得出任意一格點(diǎn)的覆蓋狀況K＝(ki)1×P，矩陣元素表達(dá)式如下:

將傳感網(wǎng)絡(luò)覆蓋率轉(zhuǎn)換為該區(qū)域被覆蓋的格點(diǎn)數(shù)量和網(wǎng)格整體數(shù)量的比。則覆蓋率指標(biāo)g的計(jì)算公式為:

1.2 通信信道模型

傳感網(wǎng)絡(luò)節(jié)點(diǎn)在通信過程中，不但需符合連貫性標(biāo)準(zhǔn)tij＝1，還要滿足信噪比需求，所以，需建立通信信道模型。假設(shè)傳輸節(jié)點(diǎn)S向目標(biāo)節(jié)點(diǎn)D傳輸數(shù)據(jù)時(shí)，節(jié)點(diǎn)D通信范圍內(nèi)的其余節(jié)點(diǎn)R1和R2會(huì)對通信造成干擾[7]。

利用hSD描述從節(jié)點(diǎn)S向D傳輸數(shù)據(jù)時(shí)產(chǎn)生的信道增益，計(jì)算公式為:

式中:dSD表示兩個(gè)節(jié)點(diǎn)的傳輸距離，α代表吸收系數(shù)，θ2是信道自身衰減系數(shù)，A描述傳輸損耗。本文假設(shè)A＝0且θ2＝0。則增益計(jì)算式可作如下簡化處理:

如果兩個(gè)節(jié)點(diǎn)通信產(chǎn)生的信噪比SINRSD符合下述條件，則表明兩節(jié)點(diǎn)通信正常，信噪比表達(dá)式為:

式中:r S代表節(jié)點(diǎn)傳輸方向，且r S∈[0，1]，P′S是信息傳輸功率，tSD代表兩節(jié)點(diǎn)的傳輸耗時(shí)，l描述干擾節(jié)點(diǎn)標(biāo)記號(hào)，rl代表干擾節(jié)點(diǎn)傳輸方向，P′l代表干擾節(jié)點(diǎn)信息傳輸功率，hjD代表干擾節(jié)點(diǎn)傳輸信道增益，tlD代表干擾節(jié)點(diǎn)傳輸耗時(shí)，η代表噪聲功率，β為信噪比閾值。

完成通信信道建模后，還需設(shè)定路由協(xié)議，本文利用基于流量與傳輸質(zhì)量的協(xié)議。此種協(xié)議不但能分析數(shù)據(jù)傳輸?shù)淖罴崖窂?，還可綜合考慮傳輸延時(shí)與通信質(zhì)量之間的關(guān)系，此類協(xié)議中代表性最強(qiáng)的就是SAR協(xié)議，該協(xié)議非常重視通信質(zhì)量，在選取傳輸路徑時(shí)綜合分析服務(wù)質(zhì)量與能耗等各類因素[8]。當(dāng)兩個(gè)節(jié)點(diǎn)進(jìn)行數(shù)據(jù)傳輸時(shí)，中間節(jié)點(diǎn)會(huì)考慮數(shù)據(jù)延時(shí)與服務(wù)質(zhì)量，確定最優(yōu)轉(zhuǎn)發(fā)路徑；對于中間節(jié)點(diǎn)的選擇，通常挑選能耗較低的。此種方法能夠保證拓?fù)浣Y(jié)構(gòu)改變時(shí)，協(xié)議網(wǎng)絡(luò)可尋找新的傳輸路徑，具備較強(qiáng)的自適應(yīng)性能。與只分析路徑能耗的協(xié)議相比，該協(xié)議能夠確保網(wǎng)絡(luò)的連通性與實(shí)時(shí)性。

2 基于改進(jìn)鯨魚算法的節(jié)點(diǎn)移動(dòng)策略

根據(jù)上文構(gòu)建的傳感網(wǎng)絡(luò)節(jié)點(diǎn)與信道基本模型，為保證節(jié)點(diǎn)傳輸質(zhì)量，在此基礎(chǔ)上采用改進(jìn)鯨魚算法，通過引用自適應(yīng)步長參數(shù)提升局部與全局的搜索能力，對大量節(jié)點(diǎn)進(jìn)行位置優(yōu)化，得到節(jié)點(diǎn)移動(dòng)策略。

2.1 傳統(tǒng)鯨魚算法

鯨魚算法是根據(jù)座頭鯨捕食方式演化提出的，鯨魚會(huì)慢慢游向海洋深處，在獵物附近構(gòu)成氣泡進(jìn)行捕獵，通常包括包圍、攻擊和搜索三個(gè)主要過程。

當(dāng)包圍獵物時(shí)，假定現(xiàn)階段最佳位置就是獵物位置，鯨魚群中的個(gè)體都會(huì)向最佳位置靠近，此過程通過下述公式表示:

式中:t′代表現(xiàn)階段迭代次數(shù)，X(t′)為鯨魚目前節(jié)點(diǎn)位置，X*(t′)描述最佳位置，C和A′都代表系數(shù)矢量，能夠操控鯨魚游走形式。表達(dá)式分別如下:

式中:γ屬于[0，1]區(qū)間內(nèi)的隨機(jī)數(shù)，鯨魚的包圍機(jī)制是逐漸縮小的，且順著指定路徑向目標(biāo)靠近。在鯨魚算法中，將a由2縮小到0，來模擬包圍行為，則a的計(jì)算公式為:

式中:Maxiter代表最大迭代次數(shù)。

鯨魚是通過群體協(xié)作方式捕食的，針對鯨魚發(fā)出的氣泡攻擊，每個(gè)個(gè)體會(huì)結(jié)合隨機(jī)概率值選擇利用螺旋式還是收縮包圍方法更新當(dāng)前位置[9]。其中收縮包圍方式表達(dá)式如式(12)，螺旋式如下:

式中:b描述螺旋形狀，l′代表[-1，1]區(qū)間內(nèi)的隨機(jī)數(shù)。假設(shè)p代表[0，1]內(nèi)的任意隨機(jī)數(shù)，氣泡網(wǎng)攻擊通過下述公式描述:

在尋找獵物過程中，鯨魚結(jié)合其他個(gè)體位置尋找目標(biāo)，便于提高全局搜索性能，利用下述模型描述:

式中:Xrand(t′)代表位置隨機(jī)矢量。

2.2 改進(jìn)搜索過程

傳統(tǒng)鯨魚算法搜索目標(biāo)時(shí)，隨機(jī)矢量Xrand(t′)以及A′、D′的值共同決定了位置更新情況。當(dāng)A′的取值區(qū)間為[-2，2]時(shí)，｜A′｜由2逐步下降至0；當(dāng)｜A′｜≥1，會(huì)擴(kuò)大搜索范圍，無法獲得較好的候選解；當(dāng)｜A′｜＜1，搜索范圍變小，容易陷入局部最優(yōu)，算法的搜索能力有限。另外在迭代初始時(shí)刻，｜A′｜＞1的概率較低，進(jìn)一步降低全局搜索性能[10]。

為解決上述問題，本文設(shè)置一個(gè)自適應(yīng)步長參數(shù)U，它具有較強(qiáng)的自適應(yīng)性，能夠?qū)崟r(shí)調(diào)節(jié)步長，使局部與全局的搜索能力更加平均[11]。參數(shù)U的表達(dá)式如下:

式中:rand是[0，1]內(nèi)的隨機(jī)數(shù)，利用下述兩個(gè)公式替換式(16)和式(17):

式中:sign(·)代表符號(hào)函數(shù)，取值可以是-1、1和0。

2.3 節(jié)點(diǎn)移動(dòng)策略

基于改進(jìn)鯨魚算法的節(jié)點(diǎn)移動(dòng)策略就是對大量節(jié)點(diǎn)進(jìn)行位置優(yōu)化，確保監(jiān)測感知范圍最大，即計(jì)算傳感器節(jié)點(diǎn)的最佳位置。因此將覆蓋優(yōu)化問題變換成將最大覆蓋率g當(dāng)作目標(biāo)函數(shù)的尋優(yōu)問題。將位置尋優(yōu)過程看作鯨魚群包圍目標(biāo)的行為，計(jì)算出的最佳解即為節(jié)點(diǎn)位置[12]。在該方法中，每個(gè)鯨魚都描述不同的覆蓋分布，假設(shè)共有N個(gè)節(jié)點(diǎn)，則移動(dòng)策略詳細(xì)步驟如下:

步驟1 設(shè)置節(jié)點(diǎn)數(shù)量N、覆蓋半徑Rcov以及監(jiān)測區(qū)域邊長，設(shè)定參數(shù)U＝30；

步驟2 計(jì)算多個(gè)位置的適應(yīng)度值，結(jié)合計(jì)算結(jié)果排序，選取最佳前q個(gè)個(gè)體當(dāng)作原始種群；

步驟3 將覆蓋率當(dāng)作目標(biāo)函數(shù)，計(jì)算種群適應(yīng)度，確定目前種群全局最佳解的方位[13]；

步驟4 判定[0，1]中的隨機(jī)數(shù)rand大小，如果低于0.5，繼續(xù)執(zhí)行下一步驟，反之通過螺旋式完成位置更新；

步驟5 更新A′值，如果｜A｜＜1，繼續(xù)更新位置，若｜A｜≥1執(zhí)行下一步驟；

步驟6 將更新位置和初始位置對比，若優(yōu)于原來位置則保留，反之舍棄[14]；

步驟7 分析算法是否滿足最大迭代次數(shù)，如果滿足，獲得全局最優(yōu)解，也就是傳感器節(jié)點(diǎn)的最佳位置，若不滿足，返回步驟3。

本文設(shè)計(jì)改進(jìn)鯨魚算法的偽代碼如下:

表1 改進(jìn)鯨魚算法偽代碼

7:if1(p＜0.5)8:if2(｜A｜＜1)9:Update the position of the current search agent by the Eq(2)10:else if2(｜A｜≥1)11:Select a random search agent(X rand)12:Update the position of the current search agent by the Eq(8)13:end for 14:Check if any search agent goes beyond the search space and amend it 15:Calculate the fitness of each search agent 16:Update X*if there is better solution 17:t＝t+1 18:end while 19:return X*

3 仿真數(shù)據(jù)分析與研究

3.1 仿真參數(shù)選擇

為評價(jià)改進(jìn)鯨魚算法性能，在MATLAB仿真軟件中搭建仿真網(wǎng)絡(luò)平臺(tái)，為保證傳感網(wǎng)絡(luò)性能測試的準(zhǔn)確性，在一個(gè)70 m×70 m的區(qū)域內(nèi)隨機(jī)散布70個(gè)傳感器節(jié)點(diǎn)，保證數(shù)據(jù)多樣化。設(shè)置節(jié)點(diǎn)覆蓋半徑為10 m，通信半徑是15 m，通信信道的信噪比是30 dB，且所有節(jié)點(diǎn)的移動(dòng)速度均相同，節(jié)點(diǎn)原始能量設(shè)置為8 J以保證節(jié)點(diǎn)移動(dòng)能耗測試條件的統(tǒng)一。傳感器節(jié)點(diǎn)分布圖如圖1所示。

圖1 傳感器節(jié)點(diǎn)分布圖

在三臺(tái)PC機(jī)上分別利用所提方法、文獻(xiàn)[1]方法、文獻(xiàn)[2]方法及文獻(xiàn)[3]方法進(jìn)行節(jié)點(diǎn)移動(dòng)策略布置，通過對比仿真驗(yàn)證所提方法的有效性。

3.2 仿真結(jié)果分析

為了對傳統(tǒng)鯨魚算法進(jìn)行改進(jìn)，本文引入自適應(yīng)步長U，仿真中需驗(yàn)證該參數(shù)在算法中發(fā)揮的作用。U經(jīng)過多次迭代后，其變化趨勢如圖2所示。

由圖2可知，U值隨迭代次數(shù)的增多，大體上表現(xiàn)出下降趨勢，既存在較大步長，也會(huì)有小步長出現(xiàn)，能夠增加搜索過程的多樣性，具有自適應(yīng)調(diào)節(jié)功能。迭代過程的初始階段，步長較大可以增強(qiáng)全局搜索性能；迭代后期，步長逐漸縮小，能減少全局優(yōu)現(xiàn)象，提高收斂能力。

圖2 自適應(yīng)步長參數(shù)變化趨勢

傳感網(wǎng)絡(luò)壽命是節(jié)點(diǎn)移動(dòng)策略好壞的重要指標(biāo)，利用上述四種算法，在節(jié)點(diǎn)數(shù)量為30、60、90、120、150以及180時(shí)，分別進(jìn)行20次仿真，計(jì)算平均網(wǎng)絡(luò)壽命。

結(jié)合圖3分析，能夠發(fā)現(xiàn)改進(jìn)鯨魚算法可延長傳感網(wǎng)絡(luò)壽命，同時(shí)隨著節(jié)點(diǎn)數(shù)目增多，效果越發(fā)顯著。當(dāng)節(jié)點(diǎn)數(shù)量為180個(gè)時(shí)，文獻(xiàn)[1]方法、文獻(xiàn)[2]方法、文獻(xiàn)[3]方法的傳感網(wǎng)絡(luò)節(jié)點(diǎn)壽命分別為13 min、15 min及14.5 min，而本文方法的傳感網(wǎng)絡(luò)節(jié)點(diǎn)壽命為28 min，表明該算法的擴(kuò)展性能優(yōu)于其他方法，能夠較好地適應(yīng)大量節(jié)點(diǎn)布撒。

圖3 不同方法下傳感網(wǎng)絡(luò)壽命

節(jié)點(diǎn)移動(dòng)的另一個(gè)重要目標(biāo)就是利用最低能耗在監(jiān)測區(qū)域內(nèi)完成感知任務(wù)。也就是說要保證節(jié)點(diǎn)移動(dòng)總路徑最短。要想準(zhǔn)確評價(jià)節(jié)點(diǎn)移動(dòng)策略，可將理想路徑和全部可能的解空間(即為所有路徑之和，表示為M)進(jìn)行對比，理想路徑的計(jì)算公式如下:

式中:x′i′代表路程排列順序值，ρi′則是與其相對應(yīng)的概率值。

如圖4所示，縱坐標(biāo)代表總路程理想值和解空間之比，橫坐標(biāo)則描述不斷增加的節(jié)點(diǎn)數(shù)量。縱坐標(biāo)比值越小表明移動(dòng)路徑方法的性能越好。當(dāng)節(jié)點(diǎn)數(shù)量為10時(shí)，文獻(xiàn)[1]方法、文獻(xiàn)[2]方法、文獻(xiàn)[3]方法和本文方法的總路程理想值和解空間之比分別為0.136、0.145、0.155及0.112。因此得出，所提策略移動(dòng)路徑較短、能耗低、且隨節(jié)點(diǎn)數(shù)量的增多縱坐標(biāo)比值顯著下降，更加凸顯該算法優(yōu)越性。這是由于鯨魚搜索獵物的過程就是尋找最優(yōu)目標(biāo)節(jié)點(diǎn)位置的過程，經(jīng)過多次搜索，不斷尋找最佳位置，能夠最大程度縮短移動(dòng)距離，降低節(jié)點(diǎn)移動(dòng)能耗。

圖4 節(jié)點(diǎn)移動(dòng)能耗評價(jià)結(jié)果

4 結(jié)論

由于節(jié)點(diǎn)移動(dòng)路徑影響傳感網(wǎng)絡(luò)的覆蓋性能，降低網(wǎng)絡(luò)穩(wěn)定性，因此本文提出基于改進(jìn)鯨魚算法的節(jié)點(diǎn)移動(dòng)策略。通過增加自適應(yīng)步長參數(shù)，完成對傳統(tǒng)鯨魚算法的改進(jìn)，將覆蓋率作為目標(biāo)函數(shù)不斷更新節(jié)點(diǎn)最優(yōu)位置，得到移動(dòng)的最佳解。仿真結(jié)果表明，所提方法可延長傳感網(wǎng)絡(luò)壽命，降低能耗。在今后研究中應(yīng)引入定位算法，提高節(jié)點(diǎn)定位精度，使網(wǎng)絡(luò)覆蓋率更高。