溫斯琴

(呼和浩特民族學院計算機系,呼和浩特 010051)

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

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

1 DV-Hop算法及誤差分析

1.1 DV-Hop算法

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

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

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

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

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

(1)

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

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

Disi=hi×Hopi

(2)

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

③計算未知節(jié)點坐標

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

1.2 DV-Hop算法誤差分析

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

①異常節(jié)點

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

②節(jié)點間跳數(shù)計算

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

③平均每跳的估算

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

(4)計算方法誤差

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

2 改進DV-Hop算法

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

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

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

2.2 最小跳數(shù)修正

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

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

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

(3)

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

(4)

2.3 平均跳距修正

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

設無線網(wǎng)絡中錨節(jié)點i,j的坐標為(xi,yi)、(xj,yj),兩錨節(jié)點實際距離為:

(5)

錨節(jié)點i,j之間預估距離為:

Disi,j=hi,j×Hopi

(6)

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

(7)

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

(8)

(9)

2.4 基于改進蝙蝠算法定位未知節(jié)點

(10)

(11)

當目標函數(shù)(11)取最小值時,估算坐標誤差最為精確,因此可將定位問題轉(zhuǎn)化為求最優(yōu)值,本文改進原始DV-Hop算法坐標定位計算方法,利用改進的蝙蝠算法對目標函數(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個方面對其進行改進。算法對蝙蝠位置和速度按照以下公式進行迭代:

pi=pmin+(pmax-pmin)α

(12)

(13)

(14)

Xnew=Xold+δAt

(15)

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

(16)

(17)

2.4.2 改進蝙蝠算法

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

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

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

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

(18)

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

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

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

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

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

(19)

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

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

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

(20)

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

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

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

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

步驟2 令c(0)=c(j),從c(0)開始依次沿d(i)(i=0,1,2,…,n-1)方向進行一維搜索,可得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為步長,其中ωi為精確搜索得到的一維最優(yōu)解;

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

步驟4 按照式(21)計算指標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)線性無關,搜索方向不變,c(j+1)=c(n),j=j+1,返回步驟2,否則執(zhí)行下一步;

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

基于改進蝙蝠算法定位坐標流程:

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

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

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

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

步驟6 對當前最優(yōu)蝙蝠位置進行Powell局部搜索;

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

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

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

3 仿真實驗與分析

3.1 參數(shù)設置

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

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

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

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

圖1 本文改進算法與DV-Hop算法位置估計對比圖

(23)

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

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

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

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

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

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

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

3.3 不同通信半徑

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

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

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

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

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

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

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

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

3.5 定位所耗時間

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

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

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

4 結論

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

參考文獻:

[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] 范時平,羅丹,劉艷林. 基于GSO與加權質(zhì)心的DV-Hop定位算法[J]. 儀表技術與傳感器,2017(1):164-168.

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

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

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

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

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

[15] 任克強,李亞杰. WSN中DV-Hop節(jié)點定位算法的改進[J]. 傳感技術學報,2017,30(4):611-618.

[16] 李娟,劉禹,錢志鴻,等. 基于雙通信半徑的傳感器網(wǎng)絡DV-Hop定位算法[J]. 吉林大學學報,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] 周燕,劉培玉,趙靜,等. 基于自適應慣性權重的混沌粒子群算法[J]. 山東大學學報(理學版),2012,47(30):l-6.

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

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