一種基于DV-Hop節(jié)點的室內(nèi)定位改進算法

干建勇, 張 靜

(上海師范大學 信息與機電工程學院,上海 200234)

一種基于DV-Hop節(jié)點的室內(nèi)定位改進算法

干建勇, 張 靜

(上海師范大學 信息與機電工程學院,上海 200234)

對現(xiàn)有基于最小二乘法的DV-Hop定位算法進行分析和仿真,針對該算法定位精度依賴信標節(jié)點之間跳距和跳數(shù)這兩個信息的不足,給出一種可對信標節(jié)點之間的跳距和跳數(shù)關系做出誤差修正的改進的誤差修正DV-Hop(ECDV-Hop)算法.仿真結果表明:在相同的室內(nèi)環(huán)境下,ECDV-Hop算法與傳統(tǒng)DV-Hop算法相比,定位精度得到一定的提高.

無線傳感器網(wǎng)絡; 室內(nèi)定位; DV-Hop; 最小二乘法; 誤差修正

0 引 言

隨著信息科技的發(fā)展,無線傳感器網(wǎng)絡(WSN)的應用越來越多地跨學科交織、融合.在室內(nèi)定位應用中,如何用已知定位信息的錨節(jié)點(信標節(jié)點)來確定該環(huán)境下未知節(jié)點的信息是目前WSN熱門研究課題之一.

WSN定位算法可以分成兩類,即基于距離的定位和與距離無關的定位.基于距離的定位算法需要掌握信標節(jié)點和未知節(jié)點之間任意的一種相互度量關系,如角度、距離、信號強度等,以此來計算未知節(jié)點的位置[1],測距方法包括TOA法、TDOA法、AOA法和RSSI 法[2];與距離無關的定位算法主要有質(zhì)心算法、DV-Hop算法、APIT算法等[3].其中DV-Hop算法具有部署網(wǎng)絡成本低的優(yōu)點,缺點是精度不夠高.[4-6]改進了該算法并取得了一定的效果,但每種改進算法均存在一定的缺陷.

本文作者在DV-Hop算法的基礎上,通過修正信標節(jié)點之間的跳數(shù)信息和相對距離來提高定位精度,提出了改進的定位算法ECDV-Hop,并仿真對比了改進算法與DV-Hop算法的優(yōu)劣.

1 DV-Hop定位算法

DV-Hop算法的基本思想是通過計算平均每跳距離來獲取未知節(jié)點到信標節(jié)點之間的距離,然后使用最小二乘法求出未知節(jié)點的位置信息.算法主要分為3個階段:

1)計算所有未知節(jié)點到每個信標節(jié)點的最小跳數(shù).每個信標節(jié)點向鄰節(jié)點廣播自身的位置信息,每個未知節(jié)點都有一張數(shù)據(jù)表(xi,yi,hi),其中xi和yi是該節(jié)點收到的某一個信標節(jié)點的坐標,hi是該節(jié)點到信標節(jié)點的最小跳數(shù).未知節(jié)點只有在與鄰節(jié)點交換信息時才會更新該表.未知節(jié)點記錄每個信標節(jié)點到自身的最小跳數(shù),忽略來自同一個信標節(jié)點的較大跳數(shù).然后將跳數(shù)值加1并轉(zhuǎn)發(fā)給鄰節(jié)點.通過這個方法,網(wǎng)絡中的所有未知節(jié)點能夠記錄其到每個信標節(jié)點的最小跳數(shù)[4].

2)計算未知節(jié)點到信標節(jié)點的平均距離.每個信標節(jié)點根據(jù)第一個階段中記錄的位置和跳數(shù)信息,得到每跳的平均距離為

(1)

式中hij是信標節(jié)點i和j(i≠j)之間的跳數(shù),(xi,yi)、(xj,yj)分別為信標節(jié)點i、j的坐標,n為整個網(wǎng)絡中的信標節(jié)點總數(shù).

未知節(jié)點從距其最近的信標節(jié)點獲得平均每跳距離,并轉(zhuǎn)發(fā)給鄰節(jié)點.這個廣播策略確保大多數(shù)未知節(jié)點從其最近的信標節(jié)點處獲得平均每跳距離.未知節(jié)點根據(jù)每跳跳數(shù)和平均每跳距離計算其到信標節(jié)點的跳距

(2)

式中h是未知節(jié)點到信標節(jié)點i的跳數(shù).

3)計算未知節(jié)點的坐標.在已知3個或者更多信標節(jié)點信息的情況下,利用最小二乘法計算未知節(jié)點坐標.設(x,y)是未知節(jié)點P的坐標,(xi,yi)是第i個信標節(jié)點的坐標,di是第i個信標節(jié)點到P的距離,有[5]:

(3)

將(3)式中所有等式兩邊平方,用前n-1個等式分別減去第n式后,變換為:

AX=B,

(4)

(5)

2 改進的ECDV-Hop定位算法

2.1 誤差分析

圖1 DV-Hop平均跳距示意圖

傳統(tǒng)DV-Hop算法的主要誤差來源是將平均跳距和平均跳數(shù)作為未知節(jié)點到信標節(jié)點的距離,未知節(jié)點僅僅將信標節(jié)點的平均跳距作為該節(jié)點自身的平均跳距,但是,隨機部署的網(wǎng)絡拓撲結構通常不規(guī)則,從而導致估算距離的誤差;同時,信標節(jié)點間的跳距只是通過兩個信標節(jié)點間的距離和與總跳數(shù)之比計算得出,在一定程度上會影響定位精度,如圖1所示,其中信標節(jié)點L1、L2、L3位置已知,相互之間的歐式距離分別為DL1L2、DL1L3、DL1L3.

根據(jù)DV-Hop定位算法求得的信標節(jié)點間的跳數(shù)值為hL1L2=2,hL1L3=7,hL2L3=5,利用(2)式計算得到信標節(jié)點的平均跳距為:

由圖1可知,信標節(jié)點與未知節(jié)點、信標節(jié)點與信標節(jié)點間的跳段距離往往不是直線,直接用(2)式計算信標節(jié)點的平均跳距必然存在著較大的誤差.并在定位過程中不斷累加,因此信標節(jié)點的平均跳距的精確度十分重要.

2.2 改進算法ECDV-Hop

針對上述的傳統(tǒng)DV-Hop算法的不足,改進算法首先是將每跳距離平均得到全網(wǎng)的平均每跳距離,然后計算每個信標節(jié)點每跳距離的平均誤差,得到更加準確的網(wǎng)絡平均每跳距離:

(6)

則每個未知節(jié)點計算到各個信標節(jié)點的估計距離為

(7)

利用整個網(wǎng)絡平均跳距替代最近的信標節(jié)點的平均每跳距離,使未知節(jié)點與各信標節(jié)點之間的估算距離更接近實際距離,從而提高定位精度.但當用計算出的全網(wǎng)平均跳距去計算信標節(jié)點之間的距離時,發(fā)現(xiàn)仍舊存在著誤差.因此,在已知平均每跳距離的基礎上,通過分析每個信標節(jié)點的平均跳距誤差,多次迭代來修正之前得到的全網(wǎng)平均跳距,進一步提高定位精度[6].

信標節(jié)點i的平均每跳距離誤差為

(8)

為了實施改進算法,需在定位的第二個階段增加信標節(jié)點轉(zhuǎn)發(fā)信息到鄰節(jié)點的階段,通過計算整個網(wǎng)絡的平均跳距,用(8)式多次迭代計算各個信標節(jié)點的平均每跳距離誤差,并且將該誤差廣播至其他信標節(jié)點.每個未知節(jié)點接收到erri后,繼續(xù)向其鄰節(jié)點廣播.經(jīng)過該階段的多次廣播和轉(zhuǎn)發(fā)后,所有節(jié)點(包括信標節(jié)點和未知節(jié)點)都已知所有信標節(jié)點計算的平均跳距誤差,然后再將所有的平均每跳距離誤差取平均,誤差修正后得到全網(wǎng)的平均每跳距離誤差:

(9)

由此迭代得到整個網(wǎng)絡的平均每跳距離,修正得到新的網(wǎng)絡平均每跳距離為

(10)

式中k為變量參數(shù),取值隨具體的網(wǎng)絡環(huán)境而定,k的取值大小也影響著誤差修正的效果,從而影響定位精度.

循環(huán)(8)～(10)式進行K次迭代,直到誤差修正的變化值趨于穩(wěn)定,此時,每個未知節(jié)點到各個信標節(jié)點的估算距離為

(11)

當未知節(jié)點得到信標節(jié)點的估算距離之后,利用(5)式就能算出自己的估計坐標.

3 實驗仿真與比較

3.1 迭代次數(shù)的選擇

根據(jù)(8)～(10)式,在100 m×100 m的正方形區(qū)域內(nèi),隨機放置200個傳感器節(jié)點(包括20個信標節(jié)點和180個未知節(jié)點),每個節(jié)點的通信距離是50 m,k都取0.6,比較多次迭代的效果選出最優(yōu)迭代次數(shù).當?shù)螖?shù)為2時,根據(jù)全網(wǎng)平均每跳距離得到的定位誤差最小,因此選此時的平均距離作為估計距離值,如圖2所示.

圖2 平均定位誤差與迭代次數(shù)關系圖

3.2k的選擇

在ECDV-Hop算法的式(10)中,k的值影響著定位精度.在實驗中,通過改變k(從-1到1,以0.1為間隔)觀察其對定位誤差的影響,仿真結果如圖3所示.由圖3可知,當節(jié)點總數(shù)和信標節(jié)點數(shù)固定的情況下,定位誤差取決于k的值.當k從-1增加到0.6時,定位誤差隨k值的變大而減小,因此當k=0.6時,定位誤差最小,定位精度最高.以下都取k=0.6.

3.3 節(jié)點通信距離對定位精度的影響

在實驗中,通過改變節(jié)點的通信距離來觀察其對定位誤差的影響,仿真結果如圖4所示.從圖4可知,在相同的網(wǎng)絡環(huán)境下,ECDV-Hop算法的定位誤差比 DV-Hop小,定位誤差隨著節(jié)點的通信距離變大而增大,需找到平均定位誤差和通信距離之間的平衡,以下通信距離選為40 m.

圖3 平均定位誤差與k值關系圖

圖4 平均定位誤差與通信距離關系圖

3.4 信標節(jié)點數(shù)對定位精度的影響

定位誤差和信標節(jié)點數(shù)的關系如圖5所示,圖中的傳感器節(jié)點總數(shù)為300個,其中信標節(jié)點為20個.從圖5可知,DV-Hop算法和ECDV-Hop算法的定位誤差都隨著信標節(jié)點數(shù)的增加而減少.ECDV-Hop算法的誤差減少更加顯著,因為在ECDV-Hop算法中,信標節(jié)點的覆蓋率越高,平均每跳距離更接近于實際每跳距離;隨著信標節(jié)點數(shù)的增加,未知節(jié)點到信標節(jié)點的跳數(shù)減小,定位誤差也隨之變小.

最后,設置仿真環(huán)境為在100 m×100 m的區(qū)域內(nèi)隨機放置100個傳感器節(jié)點,其中包括10個信標節(jié)點,通信的平均距離為40 m,進行多遍不同次數(shù)的仿真,結果如圖6所示.由圖6可知,ECDV-Hop算法的定位誤差要明顯地小于DV-Hop算法,通過計算可以得知,ECDV-Hop算法的平均定位誤差為0.2633,DV-Hop算法的平均定位誤差為0.3122,因此改進算法具有一定的精度優(yōu)勢.

圖5 平均定位誤差與信標節(jié)點數(shù)關系圖

4 結 論

分析了DV-Hop算法的原理和誤差并且給出了改進的ECDV-Hop算法.該改進算法采用加權每跳距離來修正全網(wǎng)平均每跳距離的誤差,使其更接近于實際的平均每跳距離.該算法不需要額外的硬件支持.仿真結果表明,改進算法的定位精度優(yōu)于傳統(tǒng)算法.與此同時,改進算法也存在不足,通信量和計算量要高于傳統(tǒng)算法,這也導致了更大的算法代價.

[1] Wang L H,Zhang G X,Shen X F.Mobile anchor nodes aided DV-hop(M-A-DV-hop) algorithm [J].Journal of Hangzhou Dianzi University,2008(5):312-315.

[2] 林金朝,劉海波,李國軍,等.無線傳感器網(wǎng)絡中DV-Hop節(jié)點定位改進算法研究 [J].計算機應用研究,2009,26(4):1272-1275.

Lin J C,Liu H B,Li G J,et al.Study for improved DV-Hop localization algorithm in WSN [J].Application Research of Computers,2009,26(4):1272-1275.

[3] Brito L A,Liu Y,Garcia Y.An improved error localization on DV-Hop scheme for wireless sensors networks [J].2010 3rd International Conference on Advanced Computer Theory and Engineering (ICACTE),2010,6:V2-80-V2-84.

[4] Cui H M,Wang Y F,Liu L N.Improvement of DV-HOP localization algorithm [C]//IEEE.Identification and Control (ICMIC),Sousse:IEEE,2015.

[5] 彭剛,曹元大,孫利民.無線傳感器網(wǎng)絡節(jié)點定位機制的研究 [J].計算機工程與應用,2004,40(35):27-29.

Peng G,Cao Y D,Sun L M.Study of localization schemes for wireless sensor networks [J].Computer Engineering and Applications,2004,40(35):27-29.

[6] Wei Q,Han J,Zhong D,et al.An improved multihop distance estimation for DV-Hop localization algorithm in wireless sensor networks [C]//IEEE.2012 IEEE Vehicular Technology Conference (VTC Fall),Quebec City:IEEE,2012.

(責任編輯：顧浩然,包震宇)

An improved algorithm of indoor positioning based on DV-Hop nodes

Gan Jianyong, Zhang Jing

(College of Information,Mechanical and Electrical Engineering,Shanghai Normal University,Shanghai 200234,China)

In this paper,we analyzes and simulates DV-Hop algorithms based on the least square estimation frame.The accuracy of the algorithms depends on the information of jump number among beacon nodes.To overcome this drawback,we presents an improved algorithm of error correction DV-Hop (ECDV-Hop).The simulation results show that,in the same indoor environment,the positioning accuracy of ECDV-Hop algorithm is higher than DV-Hop algorithm.

wireless sensor networks; indoor positioning; DV-Hop; least squares; error correction

10.3969/J.ISSN.1000-5137.2017.01.009

2016-11-29

干建勇(1993-),男,碩士研究生,主要從事移動信號室內(nèi)定位方面的研究.E-mail:76038645@qq.com

導師簡介: 張 靜(1971-),女,博士,副教授,碩士生導師,主要從事移動通信信號處理方面的研究. E-mail:jannety@shnu.edu.cn(通信聯(lián)系人)

TN 929.5

A

1000-5137(2017)01-0048-06