基于鯨魚(yú)優(yōu)化算法和天牛須搜索的WSNs分簇路由協(xié)議*

趙 鋒， 高 楠， 張坤鈺

(西安郵電大學(xué) 通信與信息工程學(xué)院，陜西 西安 710121)

0 引 言

無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor networks,WSNs)由大量小型傳感器節(jié)點(diǎn)構(gòu)成，網(wǎng)絡(luò)可以進(jìn)行采集信息并將采集的信息發(fā)送給檢測(cè)人[1,2]。由于傳感器常常布設(shè)在比較復(fù)雜的環(huán)境中，因此,很難對(duì)節(jié)點(diǎn)的能量進(jìn)行補(bǔ)充，高效使用每個(gè)節(jié)點(diǎn)的有限能量并延長(zhǎng)生命周期成為研究的重點(diǎn)[3]。分簇協(xié)議中基站選擇合適的數(shù)量傳感器節(jié)點(diǎn)作為簇首，其他節(jié)點(diǎn)加入簇首形成簇，簇接收并融合簇內(nèi)成員節(jié)點(diǎn)發(fā)送的信息，導(dǎo)致簇首節(jié)點(diǎn)的任務(wù)過(guò)重，加大了能量的損耗，因此，為了盡可能降低簇首能耗，應(yīng)合理選取簇首位置，避免與基站的距離過(guò)大[4]。

LEACH[5]協(xié)議作為最早的分簇路由協(xié)議之一，它通過(guò)設(shè)定閾值，周期性更換簇頭來(lái)平衡網(wǎng)絡(luò)能耗。但選擇的簇首過(guò)于隨機(jī)，易使得能量損耗過(guò)多的節(jié)點(diǎn)擔(dān)任簇首，同時(shí)也可能會(huì)出現(xiàn)的網(wǎng)絡(luò)簇首數(shù)目過(guò)少和簇首與基站太遠(yuǎn)等情況。Kuila P等人提出一種基于的能量感知分簇優(yōu)化算法(PSO-C)[6]，該算法中考慮了簇首能量以及簇首與簇內(nèi)成員距離，并利用粒子群優(yōu)化(particle swarm optimization,PSO)算法進(jìn)行迭代，選出最優(yōu)簇首集。Zhao Y等人[7]提出將監(jiān)測(cè)區(qū)域分成多個(gè)扇形區(qū)域，并對(duì)扇形區(qū)域進(jìn)行分層，形成大小不同的簇，減少網(wǎng)絡(luò)能耗。Bozorgi S M等人[8]將WSNs的監(jiān)測(cè)區(qū)域分成4層，依據(jù)能量狀態(tài)和獲取狀態(tài)選取合適的節(jié)點(diǎn)擔(dān)任簇首，提出一種基于能量非均勻多跳的分簇路由算法,即NEEC(new energy-efficient clustering wireless sensor network protocol)。以上對(duì)于節(jié)點(diǎn)入簇時(shí)均沒(méi)有同時(shí)考慮簇首和節(jié)點(diǎn)各自能量、簇首與節(jié)點(diǎn)距離、簇首和基站距離這三個(gè)因素對(duì)網(wǎng)絡(luò)成簇是否合理的影響。而在節(jié)點(diǎn)入簇階段，設(shè)計(jì)了一種基于簇首與節(jié)點(diǎn)兩者的能量和距離以及簇首與基站距離的入簇選擇函數(shù)，使得普通節(jié)點(diǎn)選擇加入簇首更加合理。對(duì)于WSNs中簇首選取采用鯨魚(yú)優(yōu)化算法(WOA)，WOA相比其他算法所需的參數(shù)少，具有簡(jiǎn)單易實(shí)現(xiàn)，收斂精度高等優(yōu)點(diǎn)，但WOA存在收斂速度慢，并且采用其他個(gè)體向最優(yōu)個(gè)體移動(dòng)方式，極易陷入局部最優(yōu)解[9，10]。而新型智能天牛觸須搜索(beetle antennae search,BAS)算法[11]，僅需一個(gè)個(gè)體，運(yùn)算簡(jiǎn)單，具有很強(qiáng)的全局收索能力。

本文將WOA和BAS算法很好地結(jié)合起來(lái)，得到具有良好的收斂性和跳出局部最優(yōu)解能力的BAS-WOA，同時(shí)通過(guò)分析網(wǎng)絡(luò)中通信能耗的影響因子，將簇首選擇轉(zhuǎn)化為NP困難問(wèn)題模型，設(shè)計(jì)出評(píng)價(jià)簇首的適應(yīng)度函數(shù)，通過(guò)對(duì)監(jiān)測(cè)區(qū)域分區(qū)選取節(jié)點(diǎn)進(jìn)行初始化種群，提高種群多樣性，利用BAS-WOA選出較優(yōu)的簇首集，均衡了傳感器節(jié)點(diǎn)的能耗，從而延長(zhǎng)了網(wǎng)絡(luò)的生命周期。

1 網(wǎng)絡(luò)模型

1.1 模型假設(shè)

本文在M×M區(qū)域內(nèi)隨機(jī)部署N個(gè)傳感器節(jié)點(diǎn)和1個(gè)基站(BS)，對(duì)網(wǎng)絡(luò)模型作如下假設(shè)：1)假設(shè)所有普通節(jié)點(diǎn)的能量均是有限的，基站的能量不受限；2)節(jié)點(diǎn)均是相同類型，具有相同的性能；3)節(jié)點(diǎn)一旦部署完成，節(jié)點(diǎn)均不可移動(dòng)；4)節(jié)點(diǎn)具有代表自己身份的唯一ID；5)節(jié)點(diǎn)可以隨時(shí)檢測(cè)周圍信息并將信息發(fā)給對(duì)應(yīng)的簇首。

1.2 能耗模型

網(wǎng)絡(luò)的能耗直接影響著網(wǎng)絡(luò)的生命周期，根據(jù)文獻(xiàn)[12]的網(wǎng)絡(luò)通信模型，節(jié)點(diǎn)傳輸bbit的數(shù)據(jù)，通信距離為d的消息，所需要的發(fā)射能耗表達(dá)式為

(1)

(2)

式中Eelec為發(fā)送和接收1 bit的能量消耗，εfs為自由空間信道模型的信號(hào)的信道放大功率，εamp為多路信道衰減模型的能耗放大功率，d0為距離閾值,根據(jù)不同距離的d選取不同的放大模型。

節(jié)點(diǎn)接收bbit的數(shù)據(jù)所消耗的能量公式如下

ERX=b×Eelec

(3)

2 BAS-WOA分簇路由協(xié)議

2.1 簇首選擇

2.1.1 簇首初始化

由于改進(jìn)的WOA計(jì)算相對(duì)復(fù)雜，故而由能量不受限制的基站完成，以減少節(jié)點(diǎn)的能耗，所有節(jié)點(diǎn)將自身ID,能量和位置信息發(fā)送給基站，基站保留節(jié)點(diǎn)信息，進(jìn)行改進(jìn)的WOA選擇簇首，各節(jié)點(diǎn)根據(jù)入簇條件形成簇。

WOA種群中的一條鯨魚(yú)代表一種分簇方案，采取隨機(jī)方式初始化鯨魚(yú)種群，這種方式易使算法陷入局部最優(yōu)，導(dǎo)致簇頭分布不均衡，因此，假設(shè)WSNs中有m個(gè)簇首，在監(jiān)測(cè)區(qū)域隨機(jī)選取m個(gè)節(jié)點(diǎn)，組成一條鯨魚(yú)；并進(jìn)行N次選取，生成N條鯨魚(yú)，即N個(gè)初始分簇方案。

2.1.2 適應(yīng)度函數(shù)

由于簇首承擔(dān)著接收簇內(nèi)成員信息并融合轉(zhuǎn)發(fā)至基站的任務(wù)，簇首節(jié)點(diǎn)的能耗較大，由能耗模型可以知道簇首的能耗與距基站的距離有關(guān)，故在選取簇首時(shí)要同時(shí)考慮節(jié)點(diǎn)的剩余能量和節(jié)點(diǎn)到基站的距離，設(shè)計(jì)適應(yīng)度值函數(shù)F如下

(4)

式中c為系數(shù)，Er為剩余節(jié)點(diǎn)能量，E0為初始節(jié)點(diǎn)能量，di為第i個(gè)節(jié)點(diǎn)距基站的距離，dmax為節(jié)點(diǎn)到基站的最大距離。

2.1.3 BAS-WOA位置更新

WOA收縮包圍階段將當(dāng)前最優(yōu)個(gè)體作為最接近目標(biāo)獵物的位置或者目標(biāo)獵物位置，其他鯨魚(yú)將向最佳位置進(jìn)行移動(dòng)，位置更新數(shù)學(xué)表達(dá)式

X(j+2)=X*(j)+A·D

(5)

D=|CX*(j)-X(j)|

(6)

A=2a·r-a

(7)

C=2·r

(8)

式中A,C均為系數(shù)變量；X(j+1)為當(dāng)前更新的位置；X(j)為當(dāng)前迭代位置；X*(j)為當(dāng)前迭代最佳位置；j為當(dāng)前迭代次數(shù)。a的值隨著迭代的次數(shù)增加，線性的從2降到0；r為[0,1]中的一個(gè)隨機(jī)數(shù)。

由于WOA中的收縮包圍采用當(dāng)前最優(yōu)鯨魚(yú)個(gè)體作為參考物，其他個(gè)體向最優(yōu)個(gè)體移動(dòng)，這種移動(dòng)方式，極易使算法陷入局部最優(yōu)解，而B(niǎo)AS算法具有很強(qiáng)的全局搜索能力，運(yùn)算量低，故將兩種算法結(jié)合得到BAS-WOA，在WOA執(zhí)行收縮包圍進(jìn)行位置更新后，將更新的位置代入BAS算法中再次進(jìn)行位置更新，然后,比較WOA更新位置的適應(yīng)度函數(shù)值和BAS算法更新位置的適應(yīng)度函數(shù)值，若BAS算法更新位置的適應(yīng)值函數(shù)值較小，則使用BAS算法更新的位置，反之，則繼續(xù)使用WOA更新的位置，位置更新公式如下

(9)

Blt(j)=X(j+1)+d0*b/2

(10)

Brt(j)=X(j+1)-d0*b/2

(11)

B(j+1)=X(j+1)-δ(j)*

sign(F(Blt(j)-F(Brt(j)))

(12)

(13)

式中 rank(k,1)為隨機(jī)生成k維變量；d0為天牛觸須的感應(yīng)長(zhǎng)度；X(j+1)為執(zhí)行WOA中收縮包圍階段更新后的位置；Blt(j),Brt(j)分別為天牛左須和右須的位置；B(j+1)為BAS算法更新的位置；其中,sign為符號(hào)函數(shù)；δ(j)為天牛移動(dòng)在第j次迭代的步長(zhǎng)；F為適應(yīng)度函數(shù)。

在BAS-WOA中沒(méi)有加入新的循環(huán)，與WOA相比并沒(méi)有提高算法的復(fù)雜度。BAS-WOA算法的部分偽代碼具體步驟如表1。

表1 BAS-WOA 部分算法執(zhí)行過(guò)程

2.1.4位置映射

在WSNs中隨機(jī)分布節(jié)點(diǎn)的監(jiān)測(cè)區(qū)域內(nèi)，傳感節(jié)點(diǎn)位置是離散的，而用BAS-WOA進(jìn)行更新的節(jié)點(diǎn)位置并不一定對(duì)應(yīng)著實(shí)際監(jiān)測(cè)區(qū)域內(nèi)的節(jié)點(diǎn)位置，因此,需要將更新的節(jié)點(diǎn)位置映射到實(shí)際節(jié)點(diǎn)的位置，采用就近原理，通過(guò)計(jì)算更新節(jié)點(diǎn)到實(shí)際節(jié)點(diǎn)的歐氏距離，選擇較小的歐氏距離進(jìn)行映射。具體公式如下

p(Xp)={Xn|min[d(Xp,Xn)],1≤n≤N}

(14)

式中Xp為迭代后候選簇首的位置；Xn為實(shí)際監(jiān)測(cè)區(qū)域內(nèi)的節(jié)點(diǎn)位置；d(Xp,Xn)為迭代的候選簇首與實(shí)際節(jié)點(diǎn)的距離。

2.2 入簇方式

簇頭選舉成功后，一般采用就近原則，節(jié)點(diǎn)選擇較近的簇首入簇，這樣易出現(xiàn)部分簇內(nèi)節(jié)點(diǎn)過(guò)多，部分簇內(nèi)節(jié)點(diǎn)過(guò)少的現(xiàn)象，容易造成網(wǎng)絡(luò)中的節(jié)點(diǎn)能耗不均衡。所以,普通節(jié)點(diǎn)入選擇加入的簇首時(shí)，不僅要考慮節(jié)點(diǎn)與簇首的距離，還應(yīng)考慮節(jié)點(diǎn)和簇首的各自能量，又因?yàn)榫嚯x基站越遠(yuǎn)的簇首轉(zhuǎn)發(fā)同等信息量時(shí)消耗的能量越高，因此,也要考慮簇首與基站的距離因素，故本文參考庫(kù)侖定律公式[13]并根據(jù)以上三個(gè)因素建立入簇選擇函數(shù)如下

1≤j≤Ncluster

(15)

(16)

式中S(i)E為第i個(gè)節(jié)點(diǎn)的剩余能量,C(j)E為第j個(gè)簇頭的剩余能量,E0為初始節(jié)點(diǎn)能量,dS(i),C(j)為第i個(gè)節(jié)點(diǎn)到第j個(gè)簇首的距離,Ncluster為簇首數(shù)目,Dmax為節(jié)點(diǎn)最大通信距離,dmax為節(jié)點(diǎn)到基站的最大距離,dC(i),BS第j個(gè)簇首到基站的距離。通過(guò)計(jì)算WSNs中每個(gè)節(jié)點(diǎn)與各個(gè)簇首的入簇選擇函數(shù)Foption，普通傳感器節(jié)點(diǎn)加入入簇選擇函數(shù)較大的簇首。

3 仿真結(jié)果

3.1 實(shí)驗(yàn)設(shè)計(jì)

使用MATLAB 2016a軟件，并根據(jù)表2中給定的參數(shù)搭建實(shí)驗(yàn)仿真場(chǎng)景，監(jiān)測(cè)區(qū)域內(nèi)隨機(jī)分布100個(gè)傳感器節(jié)點(diǎn)，根據(jù)傳感器節(jié)點(diǎn)的存活個(gè)數(shù)、剩余能量和基站接收的數(shù)據(jù)分組數(shù)作為評(píng)價(jià)性能指標(biāo)，通過(guò)與LEACH、WOA-C[14]、NWOA-CT[15]算法對(duì)比，驗(yàn)證本文算法的優(yōu)越性。

表2 實(shí)驗(yàn)參數(shù)設(shè)置

3.2 不同協(xié)議的網(wǎng)絡(luò)生命周期對(duì)比

從圖1可以看出,BAS-WOA首個(gè)節(jié)點(diǎn)死亡輪數(shù)大于其他算法協(xié)議，LEACH協(xié)議、WOA-C協(xié)議、NWOA-CT協(xié)議和本文協(xié)議節(jié)點(diǎn)死亡數(shù)目達(dá)到50 %分別為750,1 200,1 320,1 500輪，故可知本文協(xié)議的網(wǎng)絡(luò)穩(wěn)定傳輸數(shù)據(jù)時(shí)間更長(zhǎng)，基站獲得監(jiān)測(cè)信息更可靠。從圖2可以看到,BAS-WOA協(xié)議的節(jié)點(diǎn)剩余總能量下降坡度更緩，網(wǎng)絡(luò)每輪的能量消耗更少，節(jié)點(diǎn)的能耗更加均衡，極大地延長(zhǎng)了網(wǎng)絡(luò)的生命周期。

圖1 存活節(jié)點(diǎn)的個(gè)數(shù)對(duì)比

圖2 網(wǎng)絡(luò)剩余總能量對(duì)比

3.3 基站接收分組數(shù)

通過(guò)觀察基站接收的分組數(shù)，可以知道網(wǎng)絡(luò)的信息采集能力。圖3中BAS-WOA協(xié)議基站所獲得的分組數(shù)比LEACH、WOA-C和NWOA-CT算法協(xié)議更加多，可以證明BAS-WOA協(xié)議擁有更好的信息采集能力，因?yàn)锽AS-WOA協(xié)議更加理的選擇簇首和網(wǎng)絡(luò)分簇，網(wǎng)絡(luò)傳輸穩(wěn)定時(shí)間和生命周期更長(zhǎng)，因此,產(chǎn)生的數(shù)據(jù)分組數(shù)也較多。

圖3 數(shù)據(jù)接收量對(duì)比

4 結(jié)束語(yǔ)

針對(duì)WSNs分簇路由協(xié)議存在能耗不均衡的問(wèn)題，本文提出一種WOA和BAS的WSNs分簇路由協(xié)議。首先，考慮了節(jié)點(diǎn)的能耗以及節(jié)點(diǎn)與基站的距離，合理地選擇簇首的位置，然后，根據(jù)節(jié)點(diǎn)和簇首的能量以及之間的距離，并引入簇首與基站距離因素，使得網(wǎng)絡(luò)成簇更加合理。最后，本文通過(guò)與LEACH、WOA-C和NWOA-CT算法協(xié)議在網(wǎng)絡(luò)節(jié)點(diǎn)存活個(gè)數(shù)、網(wǎng)絡(luò)剩余總能量和基站接收的數(shù)據(jù)分組數(shù)進(jìn)行性能對(duì)比。通過(guò)仿真所得數(shù)據(jù)圖像可知：本文提出的算法協(xié)議在網(wǎng)絡(luò)分簇機(jī)制、數(shù)據(jù)傳輸穩(wěn)定、能量利用率和信息采集能力方面要優(yōu)于其他算法協(xié)議。