基于坐標修正的改進WSN節點定位算法

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

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

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

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

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

1 DV-hop算法及誤差分析

1.1 經典DV-Hop算法

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

1.1.1 所有的信標節點通過網絡泛洪的形式將自身的坐標和初始的跳數廣播出去，由于節點的功率有限，所以只有在通信半徑內的鄰居節點才能收到，所以信標節點可以接收到其他信標節點的坐標和最小跳數的信息，同理，未知節點也可以接收到距自己最近的信標節點坐標和最小跳數的信息。

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

(1)

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

(2)

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

(3)

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

(4)

(5)

(6)

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

X=(ATA)-1ATB

(7)

1.2 誤差分析

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

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

圖1 信標節點分布狀態對定位的影響

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

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

2 DV-Hop算法的改進

2.1 平均跳距修正

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

(8)

設信標節點i和j間的真實歐氏距離為dij，則它們之間的偽距誤差因子表達式為：

(9)

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

(10)

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

2.2 坐標修正

由于網絡結構具有隨機性和復雜性的特點，使得計算平均跳距值存在誤差，運用最小二乘法求得的未知節點的坐標也會存在偏差，所以為了減少偏差，使用EKF算法對未知節點坐標進行修正，建立系統的狀態方程和觀測方程[6]為：

(11)

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

(12)

系統以未知節點到信標節點的歐氏距離的估計值作為觀測量，系統的觀測向量表達式為：

(13)

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

(14)

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

(1)時間更新。用上一狀態真實坐標計算這一狀態的預測坐標，并得到預測誤差值的方差。

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

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

2.3 定位算法過程

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

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

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

3 仿真與分析

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

(15)

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

仿真區域設置為100m×100m的矩形空間，在該區域中隨機產生節點。分別使用傳統的DV-Hop算法、跳距修正的DV-Hop算法、EKF-DV-Hop算法進行100次仿真，取其平均值作為最終的數據。

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

圖3 平均定位誤差隨信標節點比例變化

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

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

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

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

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

圖5 平均定位誤差隨節點總數變化

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

4 結論

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