基于鯨魚(yú)算法優(yōu)化DV Hop的人員定位算法

劉 哲董 楦張德廣何子?xùn)|靳健欣

(1.國(guó)網(wǎng)河北省電力有限公司,河北 石家莊 050021;2.河北省送變電有限公司,河北 石家莊 050051;3.國(guó)網(wǎng)河北省電力有限公司經(jīng)濟(jì)技術(shù)研究院,河北 石家莊 050022;4.國(guó)網(wǎng)河北省電力有限公司建設(shè)公司,河北 石家莊 050030)

0 引言

電力企業(yè)是我國(guó)社會(huì)、經(jīng)濟(jì)發(fā)展的基礎(chǔ)產(chǎn)業(yè),其性質(zhì)和特點(diǎn)決定了具有易燃、易爆、易觸電、高壓以及帶電工作等特點(diǎn),且發(fā)生安全事故影響面廣、破壞性強(qiáng)、波及范圍大等問(wèn)題,其安全管理屬于重點(diǎn)及難點(diǎn)問(wèn)題,該行業(yè)易發(fā)生安全事故,直接威脅著現(xiàn)場(chǎng)工作人員的生命安全。因此,精確定位人員位置對(duì)建立快速救援機(jī)制和搶救傷員具有重要意義。無(wú)線傳感網(wǎng)絡(luò)(Wireless Sensor Network,WSN)被廣泛地應(yīng)用于環(huán)境監(jiān)測(cè)、國(guó)防軍事、危險(xiǎn)區(qū)域遠(yuǎn)程控制、搶險(xiǎn)救災(zāi)、人員定位等諸多領(lǐng)域[1]。對(duì)于WSN 而言,網(wǎng)絡(luò)節(jié)點(diǎn)的位置信息是設(shè)計(jì)定位網(wǎng)絡(luò)結(jié)構(gòu)、數(shù)據(jù)標(biāo)記和網(wǎng)絡(luò)節(jié)點(diǎn)跟蹤的基礎(chǔ)。因此,人員定位的本質(zhì)是進(jìn)行網(wǎng)絡(luò)節(jié)點(diǎn)的位置坐標(biāo)進(jìn)行估計(jì)。傳統(tǒng)的WSN 定位算法分為測(cè)距式算法和非測(cè)距式算法[25],前者主要包括達(dá)到時(shí)間(TOA)、達(dá)到角度(AOA)、達(dá)到時(shí)間差(TDOA)和信號(hào)接收強(qiáng)度(RSSI)等,后者主要有APIT、質(zhì)心算法和DV-Hop。與測(cè)距式算法相比,非測(cè)距式算法具有成本低、網(wǎng)絡(luò)壽命長(zhǎng)和抗干擾能力強(qiáng)的優(yōu)點(diǎn)。由于DV-Hop 算法具有功耗低、方便使用和定位精度高的優(yōu)點(diǎn),因此DV-Hop算法被廣泛地應(yīng)用于WSN 中。

為提高人員定位的精度,選擇鯨魚(yú)優(yōu)化算法[6](Whale Optimization Algorithm,WOA)改進(jìn)DV-Hop 算法,提出一種基于WOA-DV-Hop人員定位算法。結(jié)合無(wú)線傳感網(wǎng)絡(luò)技術(shù),針對(duì)人員定位的經(jīng)典算法-距離向量跳段算法(DV-Hop算法)定位誤差大的問(wèn)題,引入群智能尋優(yōu)鯨魚(yú)算法優(yōu)化多目標(biāo)定位的執(zhí)行過(guò)程,解決DV-Hop算法本身存在的錨節(jié)點(diǎn)與未知節(jié)點(diǎn)之間的距離估計(jì)的誤差問(wèn)題。研究結(jié)果表明,與普通的DV-Hop人員定位算法相比較,WOA-DV-Hop 人員定位算法可以有效提高人員定位的精度。

1 鯨魚(yú)優(yōu)化算法

在鯨魚(yú)優(yōu)化算法中,包括包圍獵物、狩獵行為以及搜索捕食[7]等3種行為方式。每只鯨魚(yú)的位置表示一個(gè)可行解。

1.1 包圍獵物

座頭鯨發(fā)現(xiàn)獵物之后將快速包圍獵物,同時(shí)按式(1)和式(2)更新鯨魚(yú)位置:

式中:、為系數(shù);t為當(dāng)前迭代次數(shù);||為絕對(duì)值;和(t)分別為鯨魚(yú)個(gè)體的最佳位置和當(dāng)前位置。的計(jì)算表達(dá)式如式(3)所示:

式中:M為最大迭代次數(shù);r∈[0,1]的隨機(jī)數(shù);a∈[2,0]的隨機(jī)數(shù)。

1.2 狩獵行為

座頭鯨采用螺旋運(yùn)動(dòng)進(jìn)行狩獵,鯨魚(yú)個(gè)體首先計(jì)算與當(dāng)前最優(yōu)鯨魚(yú)的距離,見(jiàn)式(4),然后再以螺旋方式游走,進(jìn)行食物的搜索,螺旋游走方式的數(shù)學(xué)模型如式(5)所示:

式中:b為螺旋形狀控制參數(shù);l∈[-1,1]的隨機(jī)數(shù)。使用式(4)獲得當(dāng)前鯨魚(yú)個(gè)體到最好位置的鯨魚(yú)個(gè)體的距離向量。

使用式(6)來(lái)指代實(shí)現(xiàn)收縮包圍圈和螺旋更新位置同步模型,過(guò)程中通過(guò)概率p完成進(jìn)行收縮包圍,在狩獵過(guò)程中,鯨魚(yú)將以50%的概率包圍獵物或狩獵[8-9]:

1.3 搜索捕食

如果|A|>1,那么鯨魚(yú)將離開(kāi)現(xiàn)在所包圍的獵物去尋找新的獵物,位置更新式如式(7)和(8)所示:

式中:Xrand為隨機(jī)選擇的鯨魚(yú)位置。

2 基于WOA-DV-Hop的人員定位

DV-Hop算法是基于跳數(shù)的定位算法[10],估算信標(biāo)節(jié)點(diǎn)i的平均跳距Hopsizei如式(9)所示:

式中:(xi,yi)和(xj,yj)為信標(biāo)節(jié)點(diǎn)i和信標(biāo)節(jié)點(diǎn)j的坐標(biāo);Hopsi為信標(biāo)節(jié)點(diǎn)i和信標(biāo)節(jié)點(diǎn)j(i≠j)之間的最小跳數(shù)。因?yàn)闇y(cè)量誤差的存在,導(dǎo)致人員定位時(shí)必然存在定位誤差,因此人員定位問(wèn)題本質(zhì)上就是求解人員定位誤差最小化的問(wèn)題。

如果未知節(jié)點(diǎn)的位置坐標(biāo)為(x,y),未知節(jié)點(diǎn)和第i個(gè)信標(biāo)節(jié)點(diǎn)之間的距離di,那么人員定位誤差問(wèn)題如式(10)所示:

式中:di為dj的實(shí)際測(cè)量距離。

為實(shí)現(xiàn)人員定位誤差的校正,基于WOA-DVHop的人員定位的目標(biāo)函數(shù)如式(11)所示[11]:

式中:n為未知節(jié)點(diǎn)的數(shù)量為未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)i之間跳數(shù)值的倒數(shù)。通過(guò)WOA 算法優(yōu)化DV-Hop進(jìn)行人員定位,就是將尋找到的最優(yōu)解作為未知節(jié)點(diǎn)(人員位置)的最終估算位置。

通過(guò)對(duì)DV-Hop算法進(jìn)行人員定位的具體的執(zhí)行過(guò)程分析可以發(fā)現(xiàn),在算法執(zhí)行的第三階段測(cè)量錨節(jié)點(diǎn)與未知節(jié)點(diǎn)間距離時(shí),由于外界因素及內(nèi)部測(cè)量的誤差使得誤差較大。誤差產(chǎn)生的原因在于錨節(jié)點(diǎn)與最小跳數(shù)的準(zhǔn)確性以及計(jì)算未知節(jié)點(diǎn)的AHD、多目標(biāo)定位的優(yōu)化所產(chǎn)生的誤差。為了減少誤差,使用鯨魚(yú)算法優(yōu)化目標(biāo)定位階段的定位精度,在DV-Hop算法的第三階段使用目標(biāo)優(yōu)化公式,建立了WOA-DV-Hop的人員定位的算法,完成對(duì)未知節(jié)點(diǎn)坐標(biāo)的估計(jì)和人員的精確定位。

基于WOA-DV-Hop的人員定位的算法流程可以詳細(xì)描述如下。

Step1:初始化DV-Hop算法和WOA-DV-Hop算法參數(shù),設(shè)置網(wǎng)絡(luò)區(qū)域?yàn)?00×100 mm ,隨機(jī)生成取值范圍從1~100的隨機(jī)數(shù)分別作為節(jié)點(diǎn)的二維坐標(biāo),區(qū)域內(nèi)所有節(jié)點(diǎn)總數(shù)為100,其中信標(biāo)節(jié)點(diǎn)和未知節(jié)點(diǎn)數(shù)目分別為8和92。WOA 算法,種群規(guī)模popsize=100,最大迭代次數(shù)Tmax=100,令當(dāng)前迭代次數(shù)t=0;

Step2:隨機(jī)初始化鯨魚(yú)種群;

Step3:以式(11)為目標(biāo)函數(shù),計(jì)算鯨魚(yú)種群適應(yīng)度大小并排序,找出種群當(dāng)前的全局最優(yōu)解的位置;

Step4:如果t≤Tmax,則更新A、C和a;反之,迭代尋優(yōu);

Step5:當(dāng)p<0.5時(shí),如果|A|<1,則按式(1)更新鯨魚(yú)個(gè)體的位置;如果|A|≥1,則隨機(jī)選擇鯨魚(yú)個(gè)體位置Xrand,按式(7)更新鯨魚(yú)個(gè)體的位置;

Step6:當(dāng)p≥0.5時(shí),則按式(6)更新鯨魚(yú)個(gè)體的位置;

Step7:限制鯨魚(yú)搜索范圍,防止超出搜索范圍;

1.平針繡法：平針繡是天水繡花鞋墊最為常見(jiàn)的一種針?lè)?，就是上下扎針將繡線在圖案紋樣內(nèi)排列均勻整齊，不重疊，不交叉，不露底，拉線輕重一致，達(dá)到繡面針腳勻、齊、平、密的藝術(shù)效果。平繡工藝是比較精致、寫(xiě)實(shí)的刺繡形式，極富表現(xiàn)力，多用來(lái)描繪自然生物如花卉和禽類(lèi)題材，形象栩栩如生，常用對(duì)比和暈色手法，視覺(jué)效果強(qiáng)烈。

Step8:計(jì)算鯨魚(yú)個(gè)體的適應(yīng)度并進(jìn)行排序,找到適應(yīng)度最佳時(shí)所對(duì)應(yīng)的鯨魚(yú)個(gè)體X*,并進(jìn)行保存;若t>Tmax,那么執(zhí)行Step9;否則,重復(fù)執(zhí)行Step4-Step8;

Step9:輸出人員定位的最佳位置(x*,y*)。

3 仿真與分析

為了評(píng)價(jià)人員定位的效果,本文利用Matlab仿真軟件,并選擇歸一化定位誤差erra作為評(píng)價(jià)標(biāo)準(zhǔn),歸一化定位誤差erra計(jì)算式如式(12)所示[12]:

式中:K為總節(jié)點(diǎn)數(shù);N為信標(biāo)節(jié)點(diǎn)位置;R為通信半徑;(x′j,y′j)和(xj,yj)分別為未知節(jié)點(diǎn)j的估計(jì)位置和實(shí)際位置。

假設(shè)節(jié)點(diǎn)的通信半徑R=30 m,仿真區(qū)域正方形平面區(qū)域[13],大小為100 m×100 m。DVHop算法:總節(jié)點(diǎn)數(shù)K=100,信標(biāo)節(jié)點(diǎn)數(shù)N=8。WOA 算法:種群規(guī)模popsize=100,最大迭代次數(shù)Tmax=100。算法定位效果圖如圖1所示。

圖1 算法定位效果

由圖1可知,與普通的DV-Hop人員定位算法相比較,WOA-DV-Hop 人員定位算法可以有效提高人員定位的精度。WOA-DV-Hop尋優(yōu)迭代圖如圖2所示。

圖2 WOA-DV-Hop尋優(yōu)迭代示意

為了進(jìn)一步說(shuō)明人員定位的效果,分別研究信標(biāo)節(jié)點(diǎn)比例、通信半徑R和節(jié)點(diǎn)總數(shù)對(duì)歸一化平均定位誤差的影響,研究結(jié)果如圖3-5所示。

圖3 信標(biāo)節(jié)點(diǎn)比例對(duì)歸一化平均定位誤差的影響

圖3中,通信半徑R=30,節(jié)點(diǎn)總數(shù)K=150,信標(biāo)節(jié)點(diǎn)比例由10%逐漸增加到31%。隨著信標(biāo)節(jié)點(diǎn)比例的增加,定位誤差持續(xù)降低,且整體上本文提出的WOA-DV-Hop算法的誤差值略低于DV-Hop定位算法,定位精度有提高,但是定位精度提升趨勢(shì)放緩。

圖4中,信標(biāo)節(jié)點(diǎn)比例為20%,節(jié)點(diǎn)總數(shù)K=150,通信半徑由21 m 逐漸增加到45 m,增加步長(zhǎng)為3 m。隨著通信半徑的增加,定位誤差呈現(xiàn)下降趨勢(shì),且整體上本文提出的WOA-DV-Hop算法的誤差值低于DV-Hop定位算法,這是因?yàn)殡S著通信半徑的增加,節(jié)點(diǎn)間的跳數(shù)越小,其計(jì)算出的距離誤差也隨之變小,定位精度不斷提高。

圖4 通信半徑對(duì)歸一化平均定位誤差的影響

圖5中,信標(biāo)節(jié)點(diǎn)比例為20%,通信半徑R=30,節(jié)點(diǎn)總數(shù)由100按照步長(zhǎng)20逐漸增加到200。隨著節(jié)點(diǎn)總數(shù)的增加,未知節(jié)點(diǎn)和信標(biāo)節(jié)點(diǎn)的分布將更加均勻,使得網(wǎng)絡(luò)的連通性更好,因此與普通的DV-Hop 人員定位算法對(duì)比,本文提出的WOA-DV-Hop人員定位算法與的定位誤差值遠(yuǎn)低于DV-Hop算法,且隨著節(jié)點(diǎn)增加誤差持續(xù)降低,定位精度不斷提高。

圖5 節(jié)點(diǎn)總數(shù)對(duì)歸一化平均定位誤差的影響

4 結(jié)論

為了改善電力企業(yè)高危崗位存在的人員主觀安全風(fēng)險(xiǎn)問(wèn)題,本文提出了一種改進(jìn)的人員定位算法,運(yùn)用科技手段強(qiáng)化現(xiàn)場(chǎng)安全監(jiān)管,提升生產(chǎn)穩(wěn)定性及人員安全。在經(jīng)典的DV-Hop定位算法的基礎(chǔ)上,引入群智能尋優(yōu)鯨魚(yú)算法優(yōu)化多目標(biāo)定位的執(zhí)行過(guò)程,在DV-Hop算法中使用目標(biāo)優(yōu)化公式,降低了DV-Hop算法本身存在的錨節(jié)點(diǎn)與未知節(jié)點(diǎn)之間的距離估計(jì)誤差,實(shí)現(xiàn)了對(duì)未知節(jié)點(diǎn)坐標(biāo)的估計(jì)和人員的精確定位。研究結(jié)果表明,WOA-DV-Hop 人員定位算法可以有效提高人員定位的精度,并且隨著信標(biāo)節(jié)點(diǎn)比例、通信半徑R和節(jié)點(diǎn)總數(shù)等參數(shù)的增加,人員定位精度將持續(xù)增加。另外由于計(jì)算信標(biāo)節(jié)點(diǎn)間的估算距離,一定程度增加網(wǎng)絡(luò)節(jié)點(diǎn)之間的通信量,降低了執(zhí)行效率。后續(xù)將研究引入分布式系統(tǒng)提高效率和降低網(wǎng)絡(luò)能耗。