趙小平，馬嘉楠，饒 瑞，宮 婧

(南京郵電大學(xué) 理學(xué)院，江蘇 南京 210023)

0 引 言

隨著無線傳感網(wǎng)絡(luò)(WSN)的飛速發(fā)展，其在工業(yè)環(huán)境、智能交通、軍事等領(lǐng)域應(yīng)用廣泛。在無線傳感網(wǎng)絡(luò)研究中，節(jié)點(diǎn)定位算法是一個(gè)至關(guān)重要的問題，同時(shí)也是一個(gè)技術(shù)難點(diǎn)。

節(jié)點(diǎn)定位算法，是根據(jù)已知坐標(biāo)的錨節(jié)點(diǎn)(通過自身攜帶GPS定位)，對(duì)未知節(jié)點(diǎn)進(jìn)行定位。節(jié)點(diǎn)定位算法可以分為基于測(cè)距和基于無測(cè)距的定位算法[1]，基于測(cè)距的定位算法，是根據(jù)硬件測(cè)量節(jié)點(diǎn)之間的距離，開銷較大，如RSSI、TOA、TDOA等；而基于非測(cè)距的定位算法，是通過間接的手段來獲取節(jié)點(diǎn)之間的距離，如Amorphous、APIT、DV-hop等。得到節(jié)點(diǎn)之間的距離后，利用最小二乘法、遺傳算法、蟻群算法等優(yōu)化算法來求解，得到未知節(jié)點(diǎn)的坐標(biāo)。研究定位算法，主要考慮定位精度、能耗開銷、硬件成本等。研究定位算法的改進(jìn)目標(biāo)就是通過更小的代價(jià)實(shí)現(xiàn)更高的定位精度。

文中重點(diǎn)研究DV-hop定位算法，通過對(duì)未知節(jié)點(diǎn)附近錨節(jié)點(diǎn)跳距進(jìn)行加權(quán)得到未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的跳距，權(quán)重由未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的跳數(shù)，并結(jié)合信標(biāo)節(jié)點(diǎn)跳距的可信度確定。信標(biāo)節(jié)點(diǎn)可信度根據(jù)信標(biāo)節(jié)點(diǎn)實(shí)際距離和通過算法求得的跳距乘以跳數(shù)得到的距離之間的誤差得到。最后對(duì)算法精度進(jìn)行驗(yàn)證。

1 經(jīng)典DV-hop算法

DV-hop定位算法是一種分布式非測(cè)距算法[2]。算法受環(huán)境的影響較小，也不需要額外的硬件設(shè)備支持，所以適應(yīng)于成本低、規(guī)模大、節(jié)點(diǎn)配置簡單的無線傳感網(wǎng)絡(luò)[3]。

1.1 算法描述

經(jīng)典DV-hop算法非常類似于傳統(tǒng)網(wǎng)絡(luò)中的距離向量路由機(jī)制，從而可以將其大致分為三步[4]：

(1)信標(biāo)節(jié)點(diǎn)進(jìn)行信息廣播，計(jì)算未知節(jié)點(diǎn)與每個(gè)信標(biāo)節(jié)點(diǎn)的最小跳數(shù)；

(2)計(jì)算未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的實(shí)際跳距；

(3)根據(jù)求得的未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的估計(jì)距離，計(jì)算未知節(jié)點(diǎn)自身坐標(biāo)。

1.2 算法誤差分析

DV-hop是一種完全依靠網(wǎng)絡(luò)連通度來對(duì)未知節(jié)點(diǎn)進(jìn)行定位的算法[5]，在定位的過程中，外部環(huán)境和定位算法本身都會(huì)產(chǎn)生一定的誤差。產(chǎn)生誤差的方面具體如下：

(1)鏡像誤差。

在定位過程中，由于用作未知節(jié)點(diǎn)定位的信標(biāo)節(jié)點(diǎn)近似共線[6]，未知節(jié)點(diǎn)可能出現(xiàn)誤判，如圖1所示。

圖1 鏡像誤差分析圖

圖中，A、B、C為信標(biāo)節(jié)點(diǎn)，i為未知節(jié)點(diǎn)，由于信標(biāo)節(jié)點(diǎn)近似共線，導(dǎo)致誤判成為i'。這種現(xiàn)象稱為鏡像誤差現(xiàn)象，經(jīng)典DV-hop未考慮這種誤差的影響。

(2)定位計(jì)算方法。

在求得未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)之間的距離之后，一般采用極大似然估計(jì)法或三邊測(cè)量法等估算算法來計(jì)算未知節(jié)點(diǎn)的坐標(biāo)[7]。主要是因?yàn)樗惴ê唵我讓?shí)現(xiàn)，求得的結(jié)果都會(huì)有一定的誤差，并且容易造成一定范圍內(nèi)的誤差積累。

(3)無法定位節(jié)點(diǎn)(不良節(jié)點(diǎn))。

無線傳感網(wǎng)絡(luò)中的節(jié)點(diǎn)是隨機(jī)分布的，很容易造成分布不均[5]。如果未知節(jié)點(diǎn)周圍的信標(biāo)節(jié)點(diǎn)數(shù)量小于3個(gè)，無法對(duì)其進(jìn)行定位，從而產(chǎn)生了定位盲點(diǎn)。

(4)跳數(shù)誤差。

在節(jié)點(diǎn)跳數(shù)獲取階段，信標(biāo)節(jié)點(diǎn)以通信半徑R廣播位置信息，收到該信息的節(jié)點(diǎn)均計(jì)為1跳。如圖2所示，A、B節(jié)點(diǎn)均在信標(biāo)節(jié)點(diǎn)S通信范圍內(nèi),都能接收到信標(biāo)節(jié)點(diǎn)的位置信息，并且跳數(shù)都為1跳，未知節(jié)點(diǎn)C在信標(biāo)節(jié)點(diǎn)通信的邊緣，但是收不到信標(biāo)節(jié)點(diǎn)廣播的信息，而是接收到節(jié)點(diǎn)B轉(zhuǎn)發(fā)來的信標(biāo)節(jié)點(diǎn)的位置信息，所以未知節(jié)點(diǎn)C的跳數(shù)為2跳。A靠近信標(biāo)節(jié)點(diǎn)，B、C位置接近，而A到信標(biāo)節(jié)點(diǎn)的距離與B相等，是C到信標(biāo)節(jié)點(diǎn)的一半，顯而易見，這樣誤差較大[8]。

圖2 跳數(shù)誤差分析圖

(5)平均跳距誤差。

當(dāng)錨節(jié)點(diǎn)間的跳數(shù)嚴(yán)重偏離直線路徑時(shí)[9]，采用公式計(jì)算誤差較大，用來估計(jì)未知節(jié)點(diǎn)到錨節(jié)點(diǎn)之間的距離時(shí)誤差也較大。

2 基于跳距加權(quán)的改進(jìn)DV-hop算法

由于經(jīng)典DV-hop算法的誤差較大，于是考慮從跳距方面進(jìn)行改進(jìn)。文中通過對(duì)未知節(jié)點(diǎn)周圍信標(biāo)節(jié)點(diǎn)的跳距進(jìn)行加權(quán)，從而得到比較準(zhǔn)確的跳距。影響一個(gè)錨節(jié)點(diǎn)對(duì)未知節(jié)點(diǎn)的重要性因素，主要分為錨節(jié)點(diǎn)到未知節(jié)點(diǎn)的距離和錨節(jié)點(diǎn)跳距的可信度。而錨節(jié)點(diǎn)到未知節(jié)點(diǎn)的距離可以用兩者之間的跳距來衡量，錨節(jié)點(diǎn)跳距的可信度可用錨節(jié)點(diǎn)之間真實(shí)距離與估算距離兩者的誤差來度量，兩者誤差越大，可信度越低。

2.1 信息廣播和跳數(shù)計(jì)算

信標(biāo)節(jié)點(diǎn)通過洪范方式廣播自身的坐標(biāo)信息[10]，設(shè)初始跳數(shù)為0。未知節(jié)點(diǎn)記錄收到每一個(gè)信標(biāo)節(jié)點(diǎn)的最小跳數(shù)，同時(shí)忽略同一信標(biāo)節(jié)點(diǎn)其他跳數(shù)較大的路徑，然后將跳數(shù)值加1，繼續(xù)轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn)，這樣每一未知節(jié)點(diǎn)可以得到信標(biāo)節(jié)點(diǎn)的最小跳數(shù)。

2.2 信標(biāo)節(jié)點(diǎn)跳距計(jì)算

設(shè)信標(biāo)節(jié)點(diǎn)Sk的坐標(biāo)為(xk,yk),它的鄰居節(jié)點(diǎn)Si(i=1,2,…,N)的坐標(biāo)為(xi,yi)。每個(gè)信標(biāo)節(jié)點(diǎn)根據(jù)獲得的到其他信標(biāo)節(jié)點(diǎn)的坐標(biāo)和到其的最小跳距[11]求得跳距，公式如下：

(1)

其中，hik為信標(biāo)節(jié)點(diǎn)Si和Sk之間的最小跳數(shù)。

2.3 未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的跳距

信標(biāo)節(jié)點(diǎn)到未知節(jié)點(diǎn)的跳距越大，即相距越遠(yuǎn)，信標(biāo)節(jié)點(diǎn)對(duì)未知節(jié)點(diǎn)的貢獻(xiàn)越小。為了提高定位精度，應(yīng)充分利用網(wǎng)絡(luò)中的信息，并賦予近距離錨節(jié)點(diǎn)較大的權(quán)重，故利用反距離加權(quán)處理平均每跳距離[12]，表示為：

(2)

其中，Hopij為錨節(jié)點(diǎn)Si和Sj之間的跳距。

2.4 信標(biāo)節(jié)點(diǎn)跳距可信度

利用信標(biāo)節(jié)點(diǎn)誤差來度量其跳距可信度[13]。首先，利用經(jīng)典DV-hop算法求得的跳距來估算錨節(jié)點(diǎn)之間的距離；其次，與實(shí)際距離比較，求出誤差值；最后，利用誤差大小來確定跳距的權(quán)重。

(1)計(jì)算錨節(jié)點(diǎn)誤差。

利用經(jīng)典DV-hop算法中第二步求得的跳距乘以最小跳數(shù)，求得估算距離，從而實(shí)際距離與估算距離之間的誤差為：

(3)

其中，Dij為錨節(jié)點(diǎn)Si和Sj之間的實(shí)際距離；Hopsizej為錨節(jié)點(diǎn)Sj的跳距；Hopij為錨節(jié)點(diǎn)Si和Sj之間的跳距。

(2)權(quán)重確定。

用誤差的倒數(shù)作為權(quán)重，并進(jìn)行歸一化，如下：

(4)

(5)

其中，KHopi為距未知節(jié)點(diǎn)跳距小于k跳的錨節(jié)點(diǎn)。

2.5 計(jì)算最終平均跳距

結(jié)合信標(biāo)節(jié)點(diǎn)可信度和信標(biāo)節(jié)點(diǎn)離未知節(jié)點(diǎn)的跳距，確定最終權(quán)重，如下：

ωj=αγj+(1-α)βj

(6)

其中，α為系數(shù)，用來衡量信標(biāo)節(jié)點(diǎn)可信度和信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)之間的跳距兩者的重要性。

未知節(jié)點(diǎn)使用距其k跳(經(jīng)典DV-hop所求)的錨節(jié)點(diǎn)跳距并結(jié)合上述權(quán)重進(jìn)行加權(quán)，作為最終的跳距，公式如下：

(7)

其中，HopSizej為未知節(jié)點(diǎn)Xi的修正跳距。

2.6 未知節(jié)點(diǎn)定位

利用得到的跳距乘以跳數(shù)得到節(jié)點(diǎn)之間的距離，結(jié)合最小二乘法[14]進(jìn)行求解，得到未知節(jié)點(diǎn)的坐標(biāo)。

首先，計(jì)算未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離，利用未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的最小跳數(shù)和信標(biāo)節(jié)點(diǎn)的跳距，得到如下公式：

dij=reHopSize×hij

(8)

其中，dij為未知節(jié)點(diǎn)Xi到錨節(jié)點(diǎn)Sj的距離；hij為未知節(jié)點(diǎn)Xi到錨節(jié)點(diǎn)Sj的跳數(shù)。

然后，設(shè)未知節(jié)點(diǎn)坐標(biāo)為(x,y),錨節(jié)點(diǎn)Sj的坐標(biāo)為(xj,yj)，得到未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)之間的距離di。利用歐氏距離公式有：

(9)

把上式轉(zhuǎn)化為線性方程組，形式如下：

AX=b

(10)

從而解得未知節(jié)點(diǎn)X的坐標(biāo):

X=A+b=(ATA)-1ATb

(11)

其中：

(12)

(13)

3 仿真結(jié)果與分析

為了驗(yàn)證基于跳距加權(quán)的改進(jìn)DV-hop算法的性能，利用MATLAB對(duì)DV-hop算法和改進(jìn)DV-hop算法進(jìn)行對(duì)比，并用仿真數(shù)據(jù)進(jìn)行分析。實(shí)驗(yàn)中的參數(shù)設(shè)置如表1所示。

表1 仿真參數(shù)設(shè)置

仿真中，錨節(jié)點(diǎn)和未知節(jié)點(diǎn)隨機(jī)分布在1000m×1000m的區(qū)域內(nèi)，信標(biāo)節(jié)點(diǎn)和未知節(jié)點(diǎn)都是隨機(jī)生成的，在有些區(qū)域信標(biāo)節(jié)點(diǎn)比較密集，有些地方信標(biāo)節(jié)點(diǎn)數(shù)量較少，從而會(huì)導(dǎo)致一定的定位誤差，尤其在信標(biāo)節(jié)點(diǎn)稀疏區(qū)域，誤差較大。

分析經(jīng)典DV-hop算法和改進(jìn)DV-hop算法的定位精度，得到的誤差圖如圖3和圖4所示。

圖3 經(jīng)典DV-hop誤差圖

圖4 改進(jìn)DV-hop誤差圖

由圖可知，改進(jìn)DV-hop的每個(gè)未知節(jié)點(diǎn)的估計(jì)位置偏離真實(shí)位置要比經(jīng)典算法小，從而表明改進(jìn)DV-hop的精度要比經(jīng)典DV-hop精度高。而且在信標(biāo)節(jié)點(diǎn)較為密集的區(qū)域，誤差較小；而在信標(biāo)節(jié)點(diǎn)較為稀疏的區(qū)域，定位誤差較大。下面從誤差值來考慮。定義平均誤差[15]，即所有未知節(jié)點(diǎn)的估計(jì)位置與真實(shí)位置的偏離之和除以通信半徑和未知節(jié)點(diǎn)數(shù)量，公式如下：

(14)

利用平均誤差公式，計(jì)算得到原始DV-hop和改進(jìn)DV-hop定位算法10次實(shí)驗(yàn)的平均誤差，并作圖進(jìn)行對(duì)比，如圖5所示。

圖5 改進(jìn)DV-hop和經(jīng)典DV-hop的誤差對(duì)比

由圖可知，改進(jìn)DV-hop的平均定位誤差明顯比經(jīng)典DV-hop的低，并且改進(jìn)定位算法的平均誤差相對(duì)比較穩(wěn)定。因?yàn)楦倪M(jìn)的DV-hop算法考慮未知節(jié)點(diǎn)附近參考信標(biāo)節(jié)點(diǎn)的可信度和信標(biāo)節(jié)點(diǎn)到未知節(jié)點(diǎn)的跳距，這樣使離未知節(jié)點(diǎn)越遠(yuǎn)的信標(biāo)節(jié)點(diǎn)對(duì)其定位起的作用較小。同理信標(biāo)節(jié)點(diǎn)的可信度越低，對(duì)未知節(jié)點(diǎn)定位時(shí)賦予其較小的權(quán)重。這樣使得未知節(jié)點(diǎn)得到的跳距更接近真實(shí)值，從而減小誤差。

4 結(jié)束語

對(duì)無線傳感網(wǎng)絡(luò)的節(jié)點(diǎn)定位進(jìn)行了簡要分析，對(duì)DV-hop定位算法的原理和實(shí)現(xiàn)過程進(jìn)行了詳細(xì)陳述，并就其定位誤差進(jìn)行分析。利用加權(quán)的思想對(duì)DV-hop的跳距進(jìn)行修正，提高了精度。最后通過仿真實(shí)驗(yàn)對(duì)改進(jìn)DV-hop和經(jīng)典DV-hop進(jìn)行對(duì)比，得出改進(jìn)DV-hop的誤差有較大的優(yōu)化。

[1] 申屠明.無線傳感器網(wǎng)絡(luò)定位算法研究[D].杭州:浙江大學(xué),2007.

[2] 馬淑麗,趙建平.多通信半徑的無線傳感器網(wǎng)絡(luò)DV-Hop定位算法[J].傳感技術(shù)學(xué)報(bào),2016,29(4):593-600.

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

[4] 劉 嘯,劉玉龍.一種改進(jìn)的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法[J].計(jì)算機(jī)技術(shù)與發(fā)展，2014，24(4):92-95.

[5] 李 冬.基于DV-Hop的無線傳感器網(wǎng)絡(luò)定位算法研究與改進(jìn)[D].南京:南京理工大學(xué),2013.

[6] LI Changyun,ZHAO Peizhe,ZENG Yu.Improved DV-Hop localization algorithm for wireless nodes in the smart grid[C]//26th Chinese control and decision conference.[s.l.]:IEEE,2014:4535-4540.

[7] 顧亦然，蔣璐璐.一種改進(jìn)無線傳感器網(wǎng)絡(luò)的DV-Hop定位算法[J].計(jì)算機(jī)技術(shù)與發(fā)展，2012,22(12):109-112.

[8] 潘琢金,劉文春,羅 振,等.無線傳感器網(wǎng)絡(luò)DV-Hop定位算法的改進(jìn)[J].計(jì)算機(jī)工程與設(shè)計(jì),2016,37(7):1701-1704.

[9] 王小輝，李圣普，呂海蓮.基于布谷鳥算法的WSN節(jié)點(diǎn)定位研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2014,24(12):208-211.

[10] ZHOU Gongqian,YANG Lujing,LIU Zhong.Wireless sensor network node localization based on error bound DV-Hop algorithm[C]//28th Chinese control and decision conference.[s.l.]:IEEE,2016：2390-2396.

[11] ZHANG Ying,ZHU Zhuling.A novel DV-Hop method for localization of network nodes[C]//Proceeding of the 35th Chinese control conference.[s.l.]:[s.n.],2016：8346-8351.

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

[13] WANG Ying,FANG Zhiyi,CHEN Lin.A new type of weighted DV-Hop algorithm based on correction factor in WSNs[J].Journal of Communications，2014，9(9):699-705.

[14] ZHENG Jiuhu, QIAN Huanyan, WANG Lie.An improved DV-Hop positioning algorithm for wireless sensor network[C]//IEEE international conference on progress in information and computing.[s.l.]:IEEE,2015：492-497.

[15] 侯志偉,包理群,安麗霞.基于殘差加權(quán)的三維DV-Hop改進(jìn)WSN定位算法[J].計(jì)算機(jī)應(yīng)用與軟件,2016,33(1):112-115.