距離誤差加權(quán)與多通信半徑的蝙蝠優(yōu)化無線網(wǎng)絡(luò)節(jié)點(diǎn)定位算法*

溫斯琴

(呼和浩特民族學(xué)院計(jì)算機(jī)系,呼和浩特 010051)

近年來,無線傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Network)被廣泛應(yīng)用于醫(yī)療、軍事偵察、環(huán)境監(jiān)測(cè)、森林防火等各領(lǐng)域中,但各種應(yīng)用都是以定位作為基礎(chǔ),因此,節(jié)點(diǎn)定位一直是無線傳感網(wǎng)絡(luò)研究的熱點(diǎn)問題。獲取無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)坐標(biāo)算法以是否需要測(cè)量節(jié)點(diǎn)間的距離分為基于測(cè)距的定位算法和免于測(cè)距的定位算法。基于測(cè)距算法主要是應(yīng)用附加的硬件獲取節(jié)點(diǎn)相應(yīng)的角度、信號(hào)強(qiáng)度、距離等信息,以此進(jìn)行節(jié)點(diǎn)定位,主要的算法有到達(dá)角度測(cè)距法AOA[1](Angle of Arrival)、到達(dá)時(shí)間差測(cè)距法TDOA(Time Difference of Arrival)、接收信號(hào)強(qiáng)度指示法RSSI(Received Signal Strength Indicator)[2]等,此類算法定位精度較高,與之相應(yīng)的硬件成本也高,無形增加無線網(wǎng)絡(luò)的能耗。另一類算法是免于測(cè)距的定位算法,此類算法在定位過程中無需借助外界硬件,只需借助無線網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)或連通性就可以實(shí)現(xiàn)節(jié)點(diǎn)的定位,典型的算法有質(zhì)心算法、DV-Hop算法[3]、APIT(Approximate Point-In triangulation)算法、Amorphous算法等,此類算法節(jié)點(diǎn)成本低、無線網(wǎng)絡(luò)的能耗也較低,但節(jié)點(diǎn)定位精度不高。

DV-Hop(Distance Vector-Hop)定位算法是目前應(yīng)用最廣泛的免測(cè)距定位算法之一[4],其基本思想是利用距離矢量-跳數(shù)機(jī)制。由于不需要測(cè)距,DV-Hop算法受網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的影響頗大,特別在網(wǎng)絡(luò)拓?fù)洳灰?guī)則情況下定位精度較低。針對(duì)于此,國(guó)內(nèi)不少學(xué)者都提出了相應(yīng)的改進(jìn)。文獻(xiàn)[5]在不同的階段采用不同的遺傳算法,將蛙跳算法和粒子群算法融于DV-Hop定位算法中;文獻(xiàn)[6]將加權(quán)DV-Hop與加權(quán)雙曲線定位算法相結(jié)合,提出了一種新的定位算法;文獻(xiàn)[7]對(duì)原始算法中利用最小二乘法進(jìn)行位置預(yù)估進(jìn)行改進(jìn),通過利用高斯-牛頓迭代法的非線性方法實(shí)現(xiàn)了較為準(zhǔn)確的定位;文獻(xiàn)[8]利用多維尺度分析來估計(jì)未知節(jié)點(diǎn)的坐標(biāo),使用多功率傳輸方法細(xì)化具有較大誤差的節(jié)點(diǎn)坐標(biāo),提出了一種稱為邊界改進(jìn)的非定態(tài)多維多維縮放定位方法,取得了較好的定位效果;文獻(xiàn)[9-11]用遺傳機(jī)制改進(jìn)的粒子群算法代替原始DV-Hop算法中的最小二乘法求解未知節(jié)點(diǎn)坐標(biāo),以降低平均跳數(shù)與跳距誤差帶來的位置偏差累積,取得了較好的結(jié)果;文獻(xiàn)[12-15]通過對(duì)平均跳距或跳數(shù)進(jìn)行改進(jìn)來降低估算距離誤差,防止跳距或跳數(shù)誤差的原始累積,從源頭上提高定位精度。本文引入多通信半徑廣播方法修正最小跳數(shù),采用距離誤差和跳數(shù)歸一化思想修正平均跳距,利用改進(jìn)的蝙蝠算法定位未知節(jié)點(diǎn)。

1 DV-Hop算法及誤差分析

1.1 DV-Hop算法

DV-Hop算法是由Rutgers大學(xué)的Dragons等人基于矢量路由提出的一種無需測(cè)距的定位算法,該定位算法主要包括3個(gè)階段。

①基于路由泛洪廣播協(xié)議計(jì)算節(jié)點(diǎn)間最小跳數(shù)

所有錨節(jié)點(diǎn)廣播信息數(shù)據(jù)包,利用節(jié)點(diǎn)間的相互通信,使得所有節(jié)點(diǎn)獲取跳數(shù)信息,廣播數(shù)據(jù)包格式為{IDi,xi,yi,hopsizei},IDi表示節(jié)點(diǎn)的標(biāo)識(shí),(xi,yi)表示節(jié)點(diǎn)坐標(biāo),hopsizei表示節(jié)點(diǎn)間的跳數(shù)。鄰居節(jié)點(diǎn)接收錨節(jié)點(diǎn)廣播信息,將跳數(shù)值hopsizei加1。未知節(jié)點(diǎn)只保留通往錨節(jié)點(diǎn)的最小跳數(shù)信息。

②求錨節(jié)點(diǎn)的平均跳距

無線網(wǎng)絡(luò)中通過第1步路由泛洪得到了錨節(jié)點(diǎn)的位置及與其他錨節(jié)點(diǎn)的最小跳數(shù),然后求取每一跳的平均跳距:

(1)

hij表示錨節(jié)點(diǎn)i,j之間的最小跳數(shù)

錨節(jié)點(diǎn)i將計(jì)算得到的Hopi通過多跳方式向無線網(wǎng)絡(luò)廣播,未知節(jié)點(diǎn)只記錄第1個(gè)獲得的平均跳距。未知節(jié)點(diǎn)得到平均跳距后,利用自身存儲(chǔ)的最小跳數(shù),計(jì)算它距錨節(jié)點(diǎn)的距離:

Disi=hi×Hopi

(2)

Disi表示未知節(jié)點(diǎn)到錨節(jié)點(diǎn)i的估算距離。

③計(jì)算未知節(jié)點(diǎn)坐標(biāo)

根據(jù)前兩步得到的估算距離和最小跳數(shù)利用三邊測(cè)量或極大似然估計(jì)求取未知節(jié)點(diǎn)位置。

1.2 DV-Hop算法誤差分析

影響DV-Hop算法精度的因素較多,但主要由無線網(wǎng)絡(luò)節(jié)點(diǎn)分布不均勻、錨節(jié)點(diǎn)布置密度較低及算法自身等因素:

①異常節(jié)點(diǎn)

有些無線網(wǎng)絡(luò)節(jié)點(diǎn)的部署存在隨機(jī)性,致使錨節(jié)點(diǎn)處于距離未知節(jié)點(diǎn)較遠(yuǎn)的區(qū)域,或者該錨節(jié)點(diǎn)只與最近的鄰居節(jié)點(diǎn)有通信,與其他節(jié)點(diǎn)不在通信范圍內(nèi)。如果這些異常節(jié)點(diǎn)參與未知節(jié)點(diǎn)的定位,因其位置的邊緣或孤立,勢(shì)必會(huì)影響整個(gè)無線網(wǎng)絡(luò)的位置定位精度。

②節(jié)點(diǎn)間跳數(shù)計(jì)算

DV-Hop定位算法中計(jì)算節(jié)點(diǎn)間跳數(shù)時(shí),只要在節(jié)點(diǎn)通信范圍內(nèi),不管距離多遠(yuǎn),都按照1跳計(jì)算,但在實(shí)際無線網(wǎng)絡(luò)中,節(jié)點(diǎn)間每一跳的距離是長(zhǎng)短不一的,按照統(tǒng)一的1跳計(jì)算,會(huì)造成較大的誤差。

③平均每跳的估算

在DV-Hop定位算法中,未知節(jié)點(diǎn)與錨節(jié)點(diǎn)的距離計(jì)算是按照跳數(shù)與平均跳距的乘積,而平均跳距是將錨節(jié)點(diǎn)間的距離除以錨節(jié)點(diǎn)間的最小總跳數(shù)。邊緣錨節(jié)點(diǎn)或節(jié)點(diǎn)分布異常勢(shì)必會(huì)影響平均跳距的計(jì)算結(jié)果,平均跳距出現(xiàn)誤差繼而會(huì)影響平均每跳的估算。另一方面,原始DV-Hop算法中,利用距離未知節(jié)點(diǎn)最近錨節(jié)點(diǎn)來進(jìn)行定位也不符合無線網(wǎng)絡(luò)的實(shí)際分布,并不能反映整個(gè)無線網(wǎng)絡(luò)的現(xiàn)實(shí)情況。

(4)計(jì)算方法誤差

節(jié)點(diǎn)間的距離都是基于數(shù)據(jù)估計(jì),導(dǎo)致估算距離與實(shí)際距離間產(chǎn)生較大誤差。估算距離求出后,利用三邊測(cè)量法、多邊定位或極大似然法對(duì)未知節(jié)點(diǎn)坐標(biāo)進(jìn)行估算。三邊測(cè)量法雖然定位簡(jiǎn)單、計(jì)算復(fù)雜度低,但對(duì)誤差累積較為敏感,特別對(duì)節(jié)點(diǎn)分布不均或節(jié)點(diǎn)分布異常(節(jié)點(diǎn)排列成線)時(shí),3個(gè)圓不能相交于一點(diǎn),導(dǎo)致無法定位。多邊定位或極大似然法是通過方程求解,系數(shù)矩陣的微小誤差也會(huì)對(duì)最終定位造成較大干擾。

2 改進(jìn)DV-Hop算法

本文從異常節(jié)點(diǎn)、節(jié)點(diǎn)跳數(shù)、平均跳距和未知節(jié)點(diǎn)坐標(biāo)計(jì)算方法4個(gè)方面對(duì)原始DV-Hop算法進(jìn)行改進(jìn),以期得到較高精度的節(jié)點(diǎn)坐標(biāo)。

2.1 錨節(jié)點(diǎn)優(yōu)選

對(duì)未知節(jié)點(diǎn)的定位其實(shí)并不需要所有錨節(jié)點(diǎn)的參與,那些位置邊緣或孤立的錨節(jié)點(diǎn)一旦參與平均跳距的計(jì)算,不僅不會(huì)提高未知節(jié)點(diǎn)的定位精度,往往還會(huì)適得其反。為了防止異常錨節(jié)點(diǎn)對(duì)未知節(jié)點(diǎn)定位的影響,本文設(shè)定錨節(jié)點(diǎn)到未知節(jié)點(diǎn)的跳數(shù)大小,使參與節(jié)點(diǎn)定位的錨節(jié)點(diǎn)都在一定的跳數(shù)范圍內(nèi),當(dāng)參與節(jié)點(diǎn)定位的錨節(jié)點(diǎn)與未知節(jié)點(diǎn)跳數(shù)大于閾值α?xí)r,定位算法不會(huì)考慮此錨節(jié)點(diǎn)的跳數(shù)信息。

2.2 最小跳數(shù)修正

原始DV-Hop算法計(jì)算節(jié)點(diǎn)間跳數(shù)時(shí),不管距離多遠(yuǎn),都按照1跳計(jì)算,這不僅與無線網(wǎng)絡(luò)實(shí)際情況有出入,還直接影響著節(jié)點(diǎn)的定位精度。文獻(xiàn)[16]提出錨節(jié)點(diǎn)雙通信半徑進(jìn)行泛洪廣播,改變了未知節(jié)點(diǎn)與錨節(jié)點(diǎn)間統(tǒng)一按1跳的計(jì)算方式,當(dāng)未知節(jié)點(diǎn)與錨節(jié)點(diǎn)的跳數(shù)不到1跳時(shí)按0.5跳計(jì)算,提高了定位精度,但在通信半徑內(nèi),沒有闡述錨節(jié)點(diǎn)與未知節(jié)點(diǎn)的距離關(guān)系,本文在借鑒前人研究結(jié)果的基礎(chǔ)上,進(jìn)一步細(xì)化錨節(jié)點(diǎn)的通信半徑,并研究跳數(shù)與距離間的關(guān)系。為了提高定位精度,本文細(xì)化未知節(jié)點(diǎn)與錨節(jié)點(diǎn)間的跳數(shù),設(shè)錨節(jié)點(diǎn)的通信最大半徑為R,將錨節(jié)點(diǎn)分為多個(gè)通信半徑R/n,R/(n-1),…,R。

錨節(jié)點(diǎn)首先以R/n向網(wǎng)絡(luò)泛洪廣播數(shù)據(jù),將接收節(jié)點(diǎn)與錨節(jié)點(diǎn)間的跳數(shù)記為1/n跳,信息包其他格式與原DV-Hop算法一致;一定時(shí)間后,錨節(jié)點(diǎn)再以R/(n-1)向網(wǎng)絡(luò)泛洪廣播數(shù)據(jù),接收到錨節(jié)點(diǎn)信號(hào)的節(jié)點(diǎn)首先查詢是否接收到過此錨節(jié)點(diǎn)的跳數(shù)信息,若有,則維持之前跳數(shù)信息不變,若沒有,則將該未知節(jié)點(diǎn)與錨節(jié)點(diǎn)間的跳數(shù)記為2/n跳;以此類推,最后錨節(jié)點(diǎn)以半徑R向網(wǎng)絡(luò)泛洪廣播數(shù)據(jù),接收到錨節(jié)點(diǎn)信號(hào)的節(jié)點(diǎn)首先查詢是否接收到過此錨節(jié)點(diǎn)的跳數(shù)信息,若有,則維持之前跳數(shù)信息不變,若沒有,則將該未知節(jié)點(diǎn)與錨節(jié)點(diǎn)間的跳數(shù)記為1跳。

錨節(jié)點(diǎn)與其相鄰節(jié)點(diǎn)的實(shí)際距離為d,跳數(shù)為h,則通過不同半徑進(jìn)行跳數(shù)細(xì)化后,跳數(shù)h為:

(3)

通信半徑越多,無線網(wǎng)絡(luò)節(jié)點(diǎn)的能耗越大,在節(jié)點(diǎn)能量有限的前提下,為了節(jié)省節(jié)點(diǎn)能量延長(zhǎng)無線網(wǎng)絡(luò)生存時(shí)間,本文將原DV-Hop算法的通信半徑細(xì)化為4個(gè),即0.25R,0.5R,0.75R,R,這樣跳數(shù)h為:

(4)

2.3 平均跳距修正

實(shí)際網(wǎng)絡(luò)中節(jié)點(diǎn)部署是隨意的,計(jì)算平均跳距時(shí),由于路徑曲折,用原始DV-Hop算法計(jì)算出的平均跳距小于實(shí)際值,隨著錨節(jié)點(diǎn)數(shù)量、跳數(shù)的增加,計(jì)算方法的預(yù)估,容易造成誤差累積,影響節(jié)點(diǎn)最終的定位精度,本文采取距離誤差和加權(quán)跳數(shù)修正平均跳距,過程如下:

設(shè)無線網(wǎng)絡(luò)中錨節(jié)點(diǎn)i,j的坐標(biāo)為(xi,yi)、(xj,yj),兩錨節(jié)點(diǎn)實(shí)際距離為:

(5)

錨節(jié)點(diǎn)i,j之間預(yù)估距離為:

Disi,j=hi,j×Hopi

(6)

實(shí)際無線網(wǎng)絡(luò)路徑有時(shí)會(huì)曲折重疊,錨節(jié)點(diǎn)間的預(yù)估距離Disi,j和實(shí)際距離di,j并不是等同的,存在一定的誤差,則此路徑上平均跳距產(chǎn)生的誤差εi:

(7)

錨節(jié)點(diǎn)權(quán)值受路徑上跳數(shù)與距離誤差的影響,本文在錨節(jié)點(diǎn)優(yōu)選小節(jié)中,對(duì)錨節(jié)點(diǎn)的跳數(shù)進(jìn)行了一定的閾值設(shè)定,在對(duì)錨節(jié)點(diǎn)權(quán)值求解時(shí),跳數(shù)就限制在預(yù)先設(shè)定的閾值內(nèi),同時(shí)參與也就限定了參與平均跳距計(jì)算的錨節(jié)點(diǎn)的個(gè)數(shù),統(tǒng)一加權(quán)系數(shù)wi:

(8)

(9)

2.4 基于改進(jìn)蝙蝠算法定位未知節(jié)點(diǎn)

(10)

(11)

當(dāng)目標(biāo)函數(shù)(11)取最小值時(shí),估算坐標(biāo)誤差最為精確,因此可將定位問題轉(zhuǎn)化為求最優(yōu)值,本文改進(jìn)原始DV-Hop算法坐標(biāo)定位計(jì)算方法,利用改進(jìn)的蝙蝠算法對(duì)目標(biāo)函數(shù)求解最優(yōu)值。

2.4.1 蝙蝠算法

Xin-She Yang教授于2010提出了一種新型群智能優(yōu)化算法-蝙蝠算法BA(Bat Algorithm)。算法通過模仿蝙蝠聲吶探物,不斷調(diào)整頻率、脈沖等因素在解空間中搜索最優(yōu)值。,雖然蝙蝠算法在求解無約束優(yōu)化問題上優(yōu)于其他粒子群優(yōu)化算法[17],但也存在智能優(yōu)化算法的缺陷,為此,本文從種群初始化、提升局部最優(yōu)和加速算法收斂3個(gè)方面對(duì)其進(jìn)行改進(jìn)。算法對(duì)蝙蝠位置和速度按照以下公式進(jìn)行迭代:

pi=pmin+(pmax-pmin)α

(12)

(13)

(14)

Xnew=Xold+δAt

(15)

式(13):δ為[-1,1]上隨機(jī)數(shù),At表示t次迭代平均響度。隨著尋優(yōu)進(jìn)程,蝙蝠的脈沖頻率和響度更新如下:

(16)

(17)

2.4.2 改進(jìn)蝙蝠算法

雖然蝙蝠算法在求解無約束優(yōu)化問題上優(yōu)于其他粒子群優(yōu)化算法,但也存在其他智能優(yōu)化算法的缺陷,本文首先利用立方映射對(duì)蝙蝠種群進(jìn)行速度和位置的均勻化,提高種群數(shù)據(jù)解的質(zhì)量,然后引入Levy飛行特征,以加強(qiáng)算法跳出局部最優(yōu)的能力;在得到最優(yōu)蝙蝠值后對(duì)其進(jìn)行Powell局部搜索,加快算法收斂。

①利用立方映射初始化蝙蝠種群

混沌作為非線性現(xiàn)象具有隨機(jī)無序性,能對(duì)原始數(shù)據(jù)進(jìn)行隨機(jī)遍歷,產(chǎn)生較為均勻的數(shù)據(jù)。Logistic映射和立方映射是最常用的混沌模型,但立方映射產(chǎn)生的序列比Logistic映射更均勻[18]。本文利用立方映射產(chǎn)生序列來初始化蝙蝠種群。立方映射表達(dá)式如下:

g(k+1)=4g(k)3-3g(k)-1≤g(k)≤1,k=0,1,2,…

(18)

利用立方映射產(chǎn)生序列初始化蝙蝠種群步驟:

步驟1 對(duì)n維空間中的M個(gè)蝙蝠個(gè)體隨機(jī)產(chǎn)生n維向量,對(duì)任意蝙蝠個(gè)體G=(g1,g2,…,gn)-1≤gi≤1,i=0,1,2,…,n;

步驟2 將G的每一維度利用立方映射表達(dá)式(18)進(jìn)行M-1次迭代,產(chǎn)生M-1個(gè)剩余蝙蝠個(gè)體;

步驟3 將產(chǎn)生的立方映射序列按式(19)映射到蝙蝠搜索空間:

xin=Sn+(1+gin)[(Sn+Un)/2]

(19)

式中:xin表示第i個(gè)蝙蝠在搜索空間中的n維坐標(biāo),gin表示第i個(gè)蝙蝠的n維坐標(biāo),Sn、Un表示n維搜索空間的上下限。

②利用Levy飛行特征提升局部尋優(yōu)能力

Levy飛行過程具有隨機(jī)游走和隨機(jī)發(fā)現(xiàn)的特性,能夠節(jié)約活動(dòng)成本和縮短活動(dòng)距離,是一種有效地提高活動(dòng)效率的方式。保持局部搜索能力的同時(shí),有效避免了陷入局部最優(yōu)的風(fēng)險(xiǎn),在智能算法中采用Levy飛行策略可以擴(kuò)大算法的搜索范圍,種群的多樣性得到提高。本文將Levy飛行特性引入蝙蝠算法中,利用Levy飛行特性擴(kuò)展搜索空間,對(duì)蝙蝠的位置進(jìn)行改進(jìn):

(20)

式中:⊕表示點(diǎn)乘積,Levy(ξ)是隨機(jī)搜索路徑,步長(zhǎng)的大小通過levy分布隨機(jī)數(shù)產(chǎn)生且1≤ξ≤3。改進(jìn)后蝙蝠算法的搜索脈沖頻率依舊決定蝙蝠移動(dòng)的速度,與原算法的搜索行為一致,而引進(jìn)levy分布后擴(kuò)展了蝙蝠的搜索空間,能夠避免陷入局部最優(yōu)。

③利用Powell局部搜索加速算法收斂

Powell算法又稱鮑威爾共軛方向法或方向加速算法,該方法不需要對(duì)目標(biāo)函數(shù)進(jìn)行求導(dǎo)。對(duì)n維正定二次函數(shù),共軛搜索方向具有n次收斂的特性,威爾共軛方向法是一種十分有效的直接搜索法,但其缺點(diǎn)是對(duì)初始點(diǎn)要求頗高,本文利用立方映射初始化對(duì)蝙蝠種群的速度和位置,提高初始蝙蝠種群的均勻度。稱鮑威爾共軛方向法步驟如下:

步驟1 將蝙蝠算法此次迭代搜索到的結(jié)果作為初始點(diǎn)c(0),設(shè)搜索精度為ε′,給定n個(gè)初始無關(guān)搜索方向d(i)(i=0,1,2,…,n-1),一般取n個(gè)坐標(biāo)軸方向,j=0;

步驟2 令c(0)=c(j),從c(0)開始依次沿d(i)(i=0,1,2,…,n-1)方向進(jìn)行一維搜索,可得c(i)(i=1,2,…,n):

f(c(i)+ωid(i))=minf(c(i)+ωd(i))

(21)

c(i+1)=c(i)+ωid(i),(i=0,1,2,…,n)

(22)

ω、ωi為步長(zhǎng),其中ωi為精確搜索得到的一維最優(yōu)解;

步驟3 設(shè)d(n)=c(n)-c(0),若||d(n)||≤ε,求得c(n)后結(jié)束;否則沿d(n)方向線性搜索求得c(n+1);

步驟4 按照式(21)計(jì)算指標(biāo)m:

(23)

步驟5 若f(c(0))-2f(c(n))+f(2c(n)-c(0))≥2[f(c(m))-f(c(m+1))],則d(0),d(1),…,d(n-1)線性無關(guān),搜索方向不變,c(j+1)=c(n),j=j+1,返回步驟2,否則執(zhí)行下一步;

步驟6 說明以上搜索方向線性相關(guān),需調(diào)整方向,令d(m+i)=d(m+i+1)i=0,1,…,m-n-1,保證新搜索方向線性無關(guān),c(0)=c(j+1),j++,返回步驟2。

基于改進(jìn)蝙蝠算法定位坐標(biāo)流程:

步驟1 初始化蝙蝠種群的速度、脈沖頻率、脈沖響度和脈沖發(fā)射速率等基本參數(shù),設(shè)t=1;

步驟3 計(jì)算每個(gè)蝙蝠的適應(yīng)度值,找出最優(yōu)蝙蝠位置;并根據(jù)式(12)、式(13)、式(20)生成新的蝙蝠位置和速度;

步驟4 產(chǎn)生一個(gè)隨機(jī)數(shù)R1,if(R1>ri)則對(duì)當(dāng)前群體中最優(yōu)蝙蝠位置進(jìn)行隨機(jī)擾動(dòng),用擾動(dòng)得到位置替換當(dāng)前蝙蝠位置;

步驟5 生成隨機(jī)數(shù)R2,if(R2

步驟6 對(duì)當(dāng)前最優(yōu)蝙蝠位置進(jìn)行Powell局部搜索;

步驟7 根據(jù)以上搜索結(jié)果移動(dòng)蝙蝠位置,找出當(dāng)前最優(yōu)位置;

步驟8 判斷算法是否達(dá)到結(jié)束條件,若是,執(zhí)行下一步;否則,t++,返回步驟3;

步驟9 輸出全局最優(yōu)值,算法結(jié)束。

3 仿真實(shí)驗(yàn)與分析

3.1 參數(shù)設(shè)置

為了檢驗(yàn)和對(duì)比各定位算法的性能,本文在MATLAB 7.10平臺(tái)上對(duì)本文改進(jìn)的算法與文獻(xiàn)[9](簡(jiǎn)稱BIDV-Hop)、文獻(xiàn)[10](簡(jiǎn)稱GAPSODV-Hop)兩種算法進(jìn)行進(jìn)行仿真和對(duì)比分析,仿真是在Windows 7系統(tǒng)下,CPU:i5-6500@3.2 GHz,RAM:4 GB。參數(shù)如表1和表2所示。

表1 網(wǎng)絡(luò)參數(shù)初始值

表2 改進(jìn)蝙蝠算法參數(shù)初始值

根據(jù)線性降低慣性權(quán)重,其他兩種改進(jìn)粒子群參數(shù)設(shè)置為:c1=c2=1.496 2,ωmax=0.9,ωmin=0.4。定位誤差用節(jié)點(diǎn)通信半徑歸一化后的平均定位誤差表示[19]:

圖1 本文改進(jìn)算法與DV-Hop算法位置估計(jì)對(duì)比圖

(23)

3.2 不同錨節(jié)點(diǎn)比例

錨節(jié)點(diǎn)的比例對(duì)未知節(jié)點(diǎn)的定位有直接的影響,適當(dāng)?shù)腻^節(jié)點(diǎn)比例不僅可以節(jié)省無線網(wǎng)絡(luò)的部署成本還會(huì)提高節(jié)點(diǎn)的定位精度,本文在固定通信半徑的前提下,將本文算法與BIDV-Hop、GAPSODV-Hop、DV-Hop等3種算法進(jìn)行節(jié)點(diǎn)隨機(jī)部署仿真,當(dāng)節(jié)點(diǎn)通信半徑R=20時(shí),不同錨節(jié)點(diǎn)比例下各算法的歸一化平均定位誤差如圖2所示。

圖2 通信半徑R=20下錨節(jié)點(diǎn)比例對(duì)定位誤差的影響

從各算法的曲線圖中可以得出,本文改進(jìn)算法節(jié)點(diǎn)歸一化平均定位誤差最小,GAPSODV-Hop算法次之,DV-Hop算法最差。隨著錨節(jié)點(diǎn)比例的不斷加大,各算法節(jié)點(diǎn)的歸一化平均定位誤差逐漸變小,錨節(jié)點(diǎn)比例在20%之前,節(jié)點(diǎn)歸一化平均定位誤差變化率較大,當(dāng)錨節(jié)點(diǎn)比例大于20%后,節(jié)點(diǎn)歸一化平均定位誤差變化率小即遞減趨于平緩。綜合無線網(wǎng)絡(luò)部署成本,20%的錨節(jié)點(diǎn)比例較為合適。當(dāng)錨節(jié)點(diǎn)比例為20%時(shí),DV-Hop算法節(jié)點(diǎn)歸一化平均定位誤差為0.51,BIDV-Hop算法節(jié)點(diǎn)歸一化平均定位誤差為0.42,GAPSODV-Hop算法節(jié)點(diǎn)歸一化平均定位誤差為0.38,本文改進(jìn)算法節(jié)點(diǎn)歸一化平均定位誤差為0.31。

當(dāng)節(jié)點(diǎn)通信半徑R=30時(shí),不同錨節(jié)點(diǎn)比例下各算法的歸一化平均定位誤差如圖3所示。

圖3 通信半徑R=30下錨節(jié)點(diǎn)比例對(duì)定位誤差的影響

從圖3各算法曲線可以得出,當(dāng)通信半徑R=30時(shí)本文改進(jìn)算法節(jié)點(diǎn)歸一化平均定位誤差依舊最小。隨著錨節(jié)點(diǎn)比例的不斷加大,各算法節(jié)點(diǎn)的歸一化平均定位誤差逐漸變小,變化的趨勢(shì)和走向與圖2 相似。當(dāng)錨節(jié)點(diǎn)比例為20%時(shí),DV-Hop算法節(jié)點(diǎn)歸一化平均定位誤差為0.30,BIDV-Hop算法節(jié)點(diǎn)歸一化平均定位誤差為0.21,GAPSODV-Hop算法節(jié)點(diǎn)歸一化平均定位誤差為0.20,本文改進(jìn)算法節(jié)點(diǎn)歸一化平均定位誤差為0.17。

3.3 不同通信半徑

節(jié)點(diǎn)通信半徑的增大一定程度上會(huì)降低節(jié)點(diǎn)的定位誤差,但是節(jié)點(diǎn)過大的通信半徑勢(shì)必會(huì)消耗節(jié)點(diǎn)的能量。為了對(duì)比不同節(jié)點(diǎn)通信半徑下各算法節(jié)點(diǎn)的平均定位誤差,設(shè)置錨節(jié)點(diǎn)比例為20%,將本文改進(jìn)算法與各定位算法進(jìn)行100次節(jié)點(diǎn)隨機(jī)仿真,求得平均定位誤差,結(jié)果如圖4所示。

圖4 錨節(jié)點(diǎn)比例為20%下通信半徑對(duì)平均定位誤差的影響

從圖4可以看出,4種節(jié)點(diǎn)定位算法的歸一化平均定位誤差隨節(jié)點(diǎn)通信半徑的增大先降低而后微微上升。本文定位算法的定位誤差最低,GAPSODV-Hop算法次之,BIDV-Hop算法其后,DV-Hop算法最差。當(dāng)節(jié)點(diǎn)通信半徑為30 m時(shí),各定位算法的定位誤差最低,DV-Hop算法節(jié)點(diǎn)歸一化平均定位誤差為0.31,BIDV-Hop算法節(jié)點(diǎn)歸一化平均定位誤差為0.25,GAPSODV-Hop算法節(jié)點(diǎn)歸一化平均定位誤差為0.20,本文改進(jìn)算法節(jié)點(diǎn)歸一化平均定位誤差為0.17。

3.4 不同節(jié)點(diǎn)總數(shù)

錨節(jié)點(diǎn)比例為20%,節(jié)點(diǎn)通信半徑為30 m時(shí),不同節(jié)點(diǎn)總數(shù)下各算法的歸一化平均定位誤差如圖5所示。

圖5 不同節(jié)點(diǎn)總數(shù)對(duì)定位誤差的影響

從各算法的曲線圖中可以得出,隨著節(jié)點(diǎn)總數(shù)的不斷增多,定位算法的節(jié)點(diǎn)歸一化平均定位誤差越來越小,但節(jié)點(diǎn)總數(shù)在100～200之間時(shí),定位誤差降低明顯,當(dāng)節(jié)點(diǎn)總數(shù)超過200以后,定位誤差趨于平緩,這是由于節(jié)點(diǎn)總數(shù)達(dá)到200后,制約定位誤差的因素不再是節(jié)點(diǎn)總數(shù)。

綜合以上仿真分析,我們可以看出DV-Hop算法存在明顯的定位不足,定位結(jié)果較差;BIDV-Hop算法雖然利用改進(jìn)的粒子群算法優(yōu)化定位坐標(biāo),但是未對(duì)粒子群初始數(shù)據(jù)進(jìn)行處理,優(yōu)化算法已陷入局部最優(yōu),且后期收斂緩慢,定位精度相比DV-Hop算法有一定的提升;GAPSODV-Hop算法采用遺傳算法中的交叉和變異策略改進(jìn)粒子群搜索的方向和軌跡,克服了局部最優(yōu),定位結(jié)果相比BIDV-Hop算法有較大的提升。本文算法通過設(shè)置跳數(shù)閾值,修正最小跳數(shù)和平均跳距,利用改進(jìn)的蝙蝠算法定位未知節(jié)點(diǎn),取得了較好的定位效果。

3.5 定位所耗時(shí)間

定位完成的時(shí)間是反映定位算法的重要指標(biāo)。在定位精度一定的情況下,定位時(shí)間越短,節(jié)點(diǎn)能耗就會(huì)越小,無線網(wǎng)絡(luò)使用壽命將越長(zhǎng)。將本文改進(jìn)算法與各定位算法進(jìn)行100次仿真,求取平均時(shí)間。錨節(jié)點(diǎn)比例與定位所需時(shí)間(ms)關(guān)系如表3所示。

表3 錨節(jié)點(diǎn)比例與定位所需時(shí)間 單位:ms

由表3數(shù)據(jù)可知,隨著錨節(jié)點(diǎn)比例的增大,各算法定位所需時(shí)間呈先降后增的趨勢(shì),這是由于當(dāng)錨節(jié)點(diǎn)數(shù)目不足時(shí),節(jié)點(diǎn)定位所需計(jì)算的節(jié)點(diǎn)跳數(shù)、平均跳距所耗時(shí)間就多,定位時(shí)間就會(huì)延長(zhǎng),但當(dāng)錨節(jié)點(diǎn)比例過多時(shí),節(jié)點(diǎn)間無效通信時(shí)間就會(huì)增多,勢(shì)必延長(zhǎng)定位時(shí)間。本文算法相較于其他3種定位算法,在定位時(shí)間上稍好,但是當(dāng)錨節(jié)點(diǎn)比例過多時(shí),本文定位所需時(shí)間比其他算法多,這是由于本文算法節(jié)點(diǎn)間多通信半徑的所耗時(shí)間的累積。

4 結(jié)論

針對(duì)DV-Hop算法定位誤差較大,改進(jìn)的常規(guī)粒子群優(yōu)化算法易陷入局部最優(yōu)和后期收斂過慢等問題,本文從異常節(jié)點(diǎn)、節(jié)點(diǎn)跳數(shù)、平均跳距等3個(gè)方面對(duì)DV-Hop算法的不足進(jìn)行改進(jìn),通過利用立方映射均勻化初始蝙蝠種群,引入Levy飛行特征加強(qiáng)算法跳出局部最優(yōu)能力,使用Powell局部搜索加快算法收斂等三方面改進(jìn)蝙蝠算法,利用改進(jìn)的蝙蝠算法定位未知節(jié)點(diǎn)。仿真結(jié)果表明,相比DV-Hop、BIDV-Hop、GAPSODV-Hop 3種算法,本文的改進(jìn)算法有較低的定位誤差。

參考文獻(xiàn):

[1] Tian H,Wang S,Xie H.Localization Using Cooperative AOA Approach[C]//International Conference on Wireless Communications,NETWORKING and Mobile Computing. IEEE,2007:2416-2419.

[2] Wu R H,Lee Y H,Tseng H W,et al. Study of Characteristics of RSSI Signal[C]//IEEE International Conference on Industrial Technology. IEEE,2008:1-3.

[3] JaehunLee,Wooyong Chung,EuntaiKim. Robust DV-Hop a Lgorithm for localization in Wireless Sensor Network[C]//ICCAS. 2010:2506-2509.

[4] Jeon Y,Lee S,Schoi D Y Kim. Consumer Electronics[J]. IEEE Transactions,2010,56(1):27-28.

[5] Mehrabi M,Taheri H,Taghdiri P. An Improved DV-Hop Localization Algorithm Based on Evolutionary Algorithms[J]. Telecommunication Systems,2017,64(4):639-647.

[6] Mass-Sanchez J,Ruiz-Ibarra E,Cortez-Gonzlez J,et al. Weighted Hyperbolic DV-Hop Positioning Node Localization Algorithm in WSNs[J]. Wireless Personal Communications,2017,96(4):5011-5033.

[7] Kaur A,Kumar P,Gupta G P.A Novel DV-Hop Algorithm Based on Gauss-Newton method[C]//Fourth International Conference on Parallel,Distributed and Grid Computing. IEEE,2017:625-629.

[8] Tseng C L,Liu F Y,Lin C H,et al. A Hop-Count Localization Method with Boundary Improvement for Wireless Sensor Networks[C]//International Symposium on Computer,Consumer and Control.IEEE,2016:18-21.

[9] 范時(shí)平,羅丹,劉艷林. 基于GSO與加權(quán)質(zhì)心的DV-Hop定位算法[J]. 儀表技術(shù)與傳感器,2017(1):164-168.

[10] 高美鳳,李鳳超. 遺傳粒子群優(yōu)化的DV-Hop定位算法[J]. 傳感技術(shù)學(xué)報(bào),2017,30(7):1083-1089.

[11] 程超,錢志鴻,付彩欣,等. 一種基于誤差距離加權(quán)與跳段算法選擇的遺傳優(yōu)化DV-Hop定位算法[J]. 電子與信息學(xué)報(bào),2015,37(10):2418-2424.

[12] 梁潘. 基于橢圓測(cè)距的WSN的DV-Hop定位算法[J]. 計(jì)算機(jī)工程與設(shè)計(jì),2017,38(6):1468-1473.

[13] 黨宏社,李振偉. 一種改進(jìn)的DV-Hop無線傳感器網(wǎng)絡(luò)定位算法[J]. 儀表技術(shù)與傳感器,2017(1):1159-1163.

[14] 景路路,張玲華. 基于跳距優(yōu)化的改進(jìn)型DV-Hop定位算法[J]. 傳感技術(shù)學(xué)報(bào),2017,30(4):582-587.

[15] 任克強(qiáng),李亞杰. WSN中DV-Hop節(jié)點(diǎn)定位算法的改進(jìn)[J]. 傳感技術(shù)學(xué)報(bào),2017,30(4):611-618.

[16] 李娟,劉禹,錢志鴻,等. 基于雙通信半徑的傳感器網(wǎng)絡(luò)DV-Hop定位算法[J]. 吉林大學(xué)學(xué)報(bào),2014,44(2):502-507.

[17] Yang X S. Nature Inspired Meta-Heuristic Algorithms[M]. 2nd ed. Frome,UK:Luniver Press 2010:97-104.

[18] 周燕,劉培玉,趙靜,等. 基于自適應(yīng)慣性權(quán)重的混沌粒子群算法[J]. 山東大學(xué)學(xué)報(bào)(理學(xué)版),2012,47(30):l-6.

[19] 向滿天,王勝,楊友華. 基于閾值機(jī)制與距離校正的WSN改進(jìn)DV-Hop定位算法[J]. 傳感技術(shù)學(xué)報(bào),2016,29(6):920-927.

[20] 劉士興,黃俊杰,劉宏銀,等. 基于多通信半徑的加權(quán)DV-Hop定位算法[J]. 傳感技術(shù)學(xué)報(bào),2015,28(6):883-886.