干建勇, 張 靜

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

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

干建勇, 張 靜

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

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

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

0 引 言

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

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

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

1 DV-Hop定位算法

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

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

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

(1)

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

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

(2)

式中h是未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)i的跳數(shù).

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

(3)

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

AX=B,

(4)

(5)

2 改進(jìn)的ECDV-Hop定位算法

2.1 誤差分析

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

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

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

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

2.2 改進(jìn)算法ECDV-Hop

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

(6)

則每個(gè)未知節(jié)點(diǎn)計(jì)算到各個(gè)信標(biāo)節(jié)點(diǎn)的估計(jì)距離為

(7)

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

信標(biāo)節(jié)點(diǎn)i的平均每跳距離誤差為

(8)

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

(9)

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

(10)

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

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

(11)

當(dāng)未知節(jié)點(diǎn)得到信標(biāo)節(jié)點(diǎn)的估算距離之后,利用(5)式就能算出自己的估計(jì)坐標(biāo).

3 實(shí)驗(yàn)仿真與比較

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

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

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

3.2k的選擇

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

3.3 節(jié)點(diǎn)通信距離對(duì)定位精度的影響

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

圖3 平均定位誤差與k值關(guān)系圖

圖4 平均定位誤差與通信距離關(guān)系圖

3.4 信標(biāo)節(jié)點(diǎn)數(shù)對(duì)定位精度的影響

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

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

圖5 平均定位誤差與信標(biāo)節(jié)點(diǎn)數(shù)關(guān)系圖

4 結(jié) 論

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

[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] 林金朝,劉海波,李國(guó)軍,等.無線傳感器網(wǎng)絡(luò)中DV-Hop節(jié)點(diǎn)定位改進(jìn)算法研究 [J].計(jì)算機(jī)應(yīng)用研究,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)絡(luò)節(jié)點(diǎn)定位機(jī)制的研究 [J].計(jì)算機(jī)工程與應(yīng)用,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.

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

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-),男,碩士研究生,主要從事移動(dòng)信號(hào)室內(nèi)定位方面的研究.E-mail:76038645@qq.com

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

TN 929.5

A

1000-5137(2017)01-0048-06