基于坐標(biāo)修正的改進WSN節(jié)點定位算法

柏 植，許海峰，郭 凱，李 昊

(宿州學(xué)院 機械與電子工程學(xué)院，安徽 宿州 234000)

無線傳感器網(wǎng)絡(luò)(WSN)是由很多具有無線通信收發(fā)能力的節(jié)點組成的多跳自組織的網(wǎng)絡(luò)，隨著科技的不斷進步，WSN被廣泛應(yīng)用到軍事、環(huán)境監(jiān)測、健康防護、醫(yī)療救護等領(lǐng)域，因此無數(shù)的學(xué)者都投入到節(jié)點定位的研究之中[1-2]。

目前定位技術(shù)可以分為兩大類：非測距定位和測距定位。其中測距定位算法就需要兩相鄰節(jié)點間的歐氏距離或角度的信息，這勢必會提高對硬件設(shè)備的要求，其優(yōu)點在于定位的精度比較高，常用的測距定位算法有：AOA、TOA、RSSI等，非測距定位算法是可以不通過測距的方法實現(xiàn)對節(jié)點的定位，主要是利用網(wǎng)絡(luò)的拓撲關(guān)系和網(wǎng)絡(luò)的連通性來實現(xiàn)對未知節(jié)點的定位，不需要昂貴的硬件，相比于測距定位算法具有成本低和易于實施等優(yōu)點，但其缺點是誤差較大，常見的非測距定位算法有：質(zhì)心算法、DV-Hop、Amorphous和APIT等[3]。

為了提升DV-Hop算法的定位精度，提出了分別修正跳距和優(yōu)化坐標(biāo)來改進DV-Hop算法，在修正跳距階段，通過計算得到每個信標(biāo)節(jié)點與其他信標(biāo)節(jié)點間的偽距誤差因子，除去誤差較大的信標(biāo)節(jié)點，求得平均跳距，然后運用三邊定位算法和最小二乘法求得未知節(jié)點的坐標(biāo)信息，在優(yōu)化坐標(biāo)階段，使用擴展卡爾曼濾波算法(EKF)優(yōu)化坐標(biāo)，調(diào)整觀測噪聲矩陣在合適的值，從而有效的提升節(jié)點定位精度。

1 DV-hop算法及誤差分析

1.1 經(jīng)典DV-Hop算法

DV-Hop算法是非測距定位算法中基于距離矢量路由原理的算法，主要有通過以下三個階段來完成定位的。

1.1.1 所有的信標(biāo)節(jié)點通過網(wǎng)絡(luò)泛洪的形式將自身的坐標(biāo)和初始的跳數(shù)廣播出去，由于節(jié)點的功率有限，所以只有在通信半徑內(nèi)的鄰居節(jié)點才能收到，所以信標(biāo)節(jié)點可以接收到其他信標(biāo)節(jié)點的坐標(biāo)和最小跳數(shù)的信息，同理，未知節(jié)點也可以接收到距自己最近的信標(biāo)節(jié)點坐標(biāo)和最小跳數(shù)的信息。

1.1.2 信標(biāo)節(jié)點之間相互通信之后，根據(jù)式(1)計算出信標(biāo)節(jié)點i的平均跳距。

(1)

式中：Hopi為信標(biāo)節(jié)點i的平均跳距，(xi,yi)和(xj,yj)為信標(biāo)節(jié)點i和j的坐標(biāo)，hij為信標(biāo)節(jié)點i和j間的最小跳數(shù)。

(2)

1.1.3 得到上述的估計距離后，使用最小二乘法法完成定位。假設(shè)第i個信標(biāo)節(jié)點的坐標(biāo)是(xi,yi)，未知節(jié)點u的坐標(biāo)是(x,y)，未知節(jié)點u到第i個信標(biāo)節(jié)點的歐氏距離是di，所以有式(3)所示的方程組[4]。

(3)

上述的方程組可以轉(zhuǎn)換為AX=B的形式，其中：

(4)

(5)

(6)

使用最小二乘法可計算得X，如式(7)所示。

X=(ATA)-1ATB

(7)

1.2 誤差分析

DV-Hop在定位時精度較低，通過分析后發(fā)現(xiàn)該算法主要誤差來源為以下三個方面。

(1)信標(biāo)節(jié)點的分布狀態(tài)和密度。WSN中信標(biāo)節(jié)點都是隨機分布的，這就會產(chǎn)生節(jié)點分布不均的情況，如圖1所示，若節(jié)點間的跳數(shù)偏多，則它們間的理論距離就偏大于真實距離，就會產(chǎn)生誤差[5]。

圖1 信標(biāo)節(jié)點分布狀態(tài)對定位的影響

(2)未知節(jié)點平均跳距的影響。信標(biāo)節(jié)點與未知節(jié)點間的距離是跳距估計值與跳數(shù)之積，但如果獲取的平均跳距值偏差較大，就會影響定位的精度[11]。

(3)未知節(jié)點坐標(biāo)求解方法的影響。運用三邊定位法和最小二乘法求解未知節(jié)點的坐標(biāo)信息，使用最小二乘法獲取坐標(biāo)時，將有誤差的矩陣帶入計算也會降低定位精度。

2 DV-Hop算法的改進

2.1 平均跳距修正

根據(jù)經(jīng)典的DV-Hop算法理論，信標(biāo)節(jié)點i和j間的偽距表達式如式(8)所示。

(8)

設(shè)信標(biāo)節(jié)點i和j間的真實歐氏距離為dij，則它們之間的偽距誤差因子表達式為：

(9)

在現(xiàn)實環(huán)境中偽距和真實距離通常存在誤差，所以對節(jié)點i和j之間偽距誤差因子降序排序，取排序的后k個節(jié)點來計算信標(biāo)節(jié)點i的平均跳距，根據(jù)測試，k取值是總信標(biāo)節(jié)點數(shù)的1/3-1/2倍時效果最佳。最終i的跳距修正為：

(10)

將修正后的平均跳距再用上節(jié)中式(2)計算跳距，根據(jù)式(7)定位未知節(jié)點，即可提高定位精度。

2.2 坐標(biāo)修正

由于網(wǎng)絡(luò)結(jié)構(gòu)具有隨機性和復(fù)雜性的特點，使得計算平均跳距值存在誤差，運用最小二乘法求得的未知節(jié)點的坐標(biāo)也會存在偏差，所以為了減少偏差，使用EKF算法對未知節(jié)點坐標(biāo)進行修正，建立系統(tǒng)的狀態(tài)方程和觀測方程[6]為：

(11)

其中wk和vk分別表示在第k個信標(biāo)節(jié)點定位時的狀態(tài)噪聲和觀測噪聲，它們的方差分別為Qk和Rk，且相互獨立。

(12)

系統(tǒng)以未知節(jié)點到信標(biāo)節(jié)點的歐氏距離的估計值作為觀測量，系統(tǒng)的觀測向量表達式為：

(13)

式中(xk,yk)為第k個信標(biāo)節(jié)點的坐標(biāo)，對h(k,Xk)求偏導(dǎo)即可得雅克比矩陣Hk如式(14)所示。

(14)

應(yīng)用EKF算法定位的過程可分為兩大部分，具體如下所示[7]。

(1)時間更新。用上一狀態(tài)真實坐標(biāo)計算這一狀態(tài)的預(yù)測坐標(biāo)，并得到預(yù)測誤差值的方差。

(2)量測更新。根據(jù)求得的雅克比矩陣，即可以得到狀態(tài)增益矩陣，進而可以得到這一狀態(tài)的估計值和協(xié)方差矩陣。

通過使用EKF濾波算法進一步修正未知節(jié)點的定位坐標(biāo)，進而提高定位的精度。

2.3 定位算法過程

綜合2.1和2.2所述的方法，下面對定位方法做簡要的描述。

首先網(wǎng)絡(luò)初始化，信標(biāo)節(jié)點向網(wǎng)絡(luò)中廣播自身位置，運用經(jīng)典的距離矢量交換協(xié)議，根據(jù)式(1)得到每個信標(biāo)節(jié)點的初始跳距，并定義偽距誤差因子，根據(jù)式(10)修正信標(biāo)節(jié)點的跳距。未知節(jié)點收到廣播后，判斷是否是第一次收到，若是就保存該信標(biāo)節(jié)點位置信息，否則與緩沖區(qū)的條數(shù)值比較，保存較小的跳數(shù)值。然后根據(jù)式(2)重新計算每個未知節(jié)點的跳距，根據(jù)式(7)利用最小二乘法估算未知節(jié)點的初始坐標(biāo)。將該初始坐標(biāo)作為EKF的初始值，以未知節(jié)點到信標(biāo)節(jié)點的歐氏距離的估計值作為觀測量進行濾波融合，最終得到未知節(jié)點的坐標(biāo)，流程圖如圖2所示。

圖2 EKF-DV-Hop定位算法流程

3 仿真與分析

為驗證提出算法的有效性，對經(jīng)典的DV-Hop算法和改進后的算法分別在MATLAB仿真平臺上做仿真驗證，為評判不同定位算法的性能，定義平均相對誤差，其計算公式如式(15)所示[8]。

(15)

式中(xi,yi)、(Xi,Yi)分別指的是未知節(jié)點i的估計坐標(biāo)和真實坐標(biāo)，n為未知節(jié)點的數(shù)目，R為節(jié)點間的通信半徑。

仿真區(qū)域設(shè)置為100m×100m的矩形空間，在該區(qū)域中隨機產(chǎn)生節(jié)點。分別使用傳統(tǒng)的DV-Hop算法、跳距修正的DV-Hop算法、EKF-DV-Hop算法進行100次仿真，取其平均值作為最終的數(shù)據(jù)。

分析信標(biāo)節(jié)點所占比例對定位的平均相對誤差的影響，隨機產(chǎn)生100個節(jié)點，仿真中設(shè)置節(jié)點的通信半徑是30m，信標(biāo)節(jié)點所占比例從5%到40%并以步長為5%變化，仿真數(shù)據(jù)如圖3所示。

圖3 平均定位誤差隨信標(biāo)節(jié)點比例變化

從圖3不難得出，隨著信標(biāo)節(jié)點所占比例的不斷增加，平均定位誤差隨之不斷減小，并逐漸趨向平穩(wěn)，這是因為信標(biāo)節(jié)點比例增加，提高計算跳距的準(zhǔn)確度的同時，還降低了節(jié)點之間的最小跳數(shù)，誤差也就隨之減小。信標(biāo)節(jié)點所占比例小于15%時，平均定位誤差受其影響較大，大于15%時，平均定位誤差處于緩慢平穩(wěn)狀態(tài)。與傳統(tǒng)的DV-Hop定位算法相比，跳距修正的DV-Hop和EKF-DV-Hop算法的平均定位誤差降低了約1.7%和12.26%，證明了提出的EKF-DV-Hop算法的可行性和有效性。

分析節(jié)點之間的通信半徑的變化對平均定位誤差的影響。仿真時，隨機產(chǎn)生100個節(jié)點，設(shè)置信標(biāo)節(jié)點所占比例是30%，節(jié)點之間的通信半徑從24m到44m并以步長4m增長，仿真結(jié)果如圖4所示。

圖4 平均定位誤差隨通信半徑變化

從圖4不難得出，圖中所示的四種算法，節(jié)點間通信半徑的不斷增加，未知節(jié)點的平均定位誤差都隨之呈現(xiàn)不斷減小的趨勢，這是由于節(jié)點間的通信半徑變大就會增加系統(tǒng)的連通度，計算得到的跳距就會更準(zhǔn)確。當(dāng)通信半徑大于30m的時候，減小的趨勢開始變緩，并趨于平穩(wěn)；和傳統(tǒng)的DV-Hop算法相比，跳距修正的DV-Hop算法和EKF-DV-Hop算法平均定位誤差降低了約1.459%和12.674%；通信的半徑的持續(xù)增加時，平均定位誤差反而有變化的趨勢，說明通信半徑并不是越大越好。所以，提出的定位算法是優(yōu)于其他兩種定位算法的。

分析節(jié)點總數(shù)的變化對平均定位誤差的影響。仿真時，設(shè)置節(jié)點的通信半徑為20m，信標(biāo)節(jié)點所占的比例為30%，節(jié)點總數(shù)從100到300，并以40為步長增加，仿真圖如圖5所示。

圖5 平均定位誤差隨節(jié)點總數(shù)變化

從圖5可以看出，隨著節(jié)點總數(shù)不斷增加，四種算法的定位誤差都在下降，主要是因為隨著節(jié)點數(shù)目的增加，網(wǎng)絡(luò)節(jié)點的密度隨之增加，在節(jié)點的通信半徑內(nèi)就會出現(xiàn)更多的鄰居節(jié)點，使得網(wǎng)絡(luò)的拓撲結(jié)構(gòu)更加的規(guī)則，誤差也會隨之減小，相比于傳統(tǒng)的DV-Hop定位算法，跳距修正的DV-Hop算法、EKF-DV-Hop算法的平均定位誤差降低了約1.334%和16.703%。實驗結(jié)果表明本文提出的算法更優(yōu)，可以進一步減小定位誤差。

4 結(jié)論

針對DV-Hop在定位過程中，平均跳距估算不準(zhǔn)確，定位偏差較大，環(huán)境適應(yīng)力弱的問題，使用跳距修正和坐標(biāo)優(yōu)化的方法，提高了算法定位精度和環(huán)境適應(yīng)力。首先使用偽誤差因子的方法，降低了平均跳距的誤差，然后使用EKF算法對未知節(jié)點的估計坐標(biāo)進行優(yōu)。仿真表明，提出的算法能夠明顯的提升未知節(jié)點的定位精度，具有一定的參考價值。