基于RSSI測距的改進DV-Hop定位算法

劉少楠

(東北大學秦皇島分校，河北 秦皇島 066000)

無線傳感器網絡(Wireless Sensor Network，WSN)是由多個節(jié)點組成的自組織網絡，其優(yōu)點是成本低、功耗低、對環(huán)境適應性強，現在已被廣泛應用于戰(zhàn)場監(jiān)視、工業(yè)控制、土壤環(huán)境監(jiān)測等多種應用場合中[1-2]。近年來，WSN定位算法成為科研人員研究的熱點之一。通常WSN定位算法被分類為距離有關和距離無關的算法[3-4]。信號到達時間(Time of Arrival，TOA)、信號到達時間差(Time Difference of Arrival，TDOA)、信號到達角度(Angle of Arrival，AOA)以及接收信號強度(Received Signal Strength Indicator，RSSI)等都屬于距離有關的算法，該類算法需要獲得測量距離，并輔以定位算法求出未知點的位置，效果較好[5]。其中，TOA、TDOA和AOA算法的測距結果較準確，但它們需要復雜和昂貴的硬件設備[6]。RSSI算法不需要額外的硬件，但在測距中會受到多徑傳播、信道衰落的影響，造成測距精度下降[7]。DV-Hop、APIT和MDS-MAP等算法則屬于距離無關的算法，它們的定位精度較低[8]。

DV-Hop算法的復雜性低、成本低，使得其在WSN定位中的應用較為廣泛，許多改進的DV-Hop算法被提出：文獻[9]提出了一種基于三角不等式的加權雙曲線DV-Hop定位算法，利用三角不等式約束節(jié)點間的跳距，以減小誤差；文獻[10]提出一種改進的DV-Hop定位算法，利用加權的方式計算較優(yōu)平均跳距，并將已定位的節(jié)點當作新的錨節(jié)點進行其余未知節(jié)點的定位；文獻[11]提出一種基于最優(yōu)輔助距離估計錨節(jié)點的DV-Hop定位算法，根據不同的估距類型計算節(jié)點間的估計距離，并將加權因子的概念引入到三邊定位法中，以提高定位精度；文獻[12]提出一種加權距離估計方法，通過對來自多個錨節(jié)點的加權跳數進行運算，使網絡平均跳距估計更準確。本文提出了一種基于RSSI測距的改進DV-Hop定位算法，利用RSSI測距優(yōu)化兩個節(jié)點之間的跳數，同時，設置校正因子修正平均跳距，再根據無約束優(yōu)化算法估計未知節(jié)點的位置。

1 DV-Hop定位算法

DV-Hop算法采用泛洪來獲得兩個節(jié)點之間的最短路徑和網絡中的平均跳數，然后使用三邊測量法來估計節(jié)點位置。DV-Hop算法可以分成3個步驟執(zhí)行[13]：

步驟1 獲取未知節(jié)點和錨節(jié)點之間的最小跳數。每個錨節(jié)點向其他節(jié)點廣播兩個參數：自身坐標和跳數，其中在算法開始時初始化跳數為0。每個鄰居節(jié)點將錨節(jié)點的坐標信息和其到錨節(jié)點的最小跳數保存在自身列表中，并將最小跳數增加1發(fā)送給其鄰居節(jié)點。如果一個節(jié)點接收到來自同一個錨的另一個消息，但是與其列表中保存的跳數相比，跳數更高，則忽略該消息。

步驟2 計算錨節(jié)點的平均每跳距離：定義一個Hopsize參數，它表示錨節(jié)點的平均每跳距離，由以下公式計算得出：

(1)

式(1)中：(xk,yk)和(xl,yl)分別表示錨節(jié)點k和l的坐標；n表示錨節(jié)點的數量；hkl表示這兩個錨節(jié)點間的最小跳數。錨節(jié)點向其他節(jié)點廣播它的平均每跳距離，未知節(jié)點接收并保存距離最近錨節(jié)點的平均每跳距離并將其轉發(fā)。

步驟3 未知節(jié)點Ui到錨節(jié)點Ak的距離可以表示為：

dik=c×hik

(2)

假設n個錨節(jié)點的坐標分別為(x1,y1),(x2,y2),…,(xn,yn)，每個錨節(jié)點到未知節(jié)點的距離為d1,d2,…,dn，設未知節(jié)點Ui的坐標是(x,y)，可以得到一組方程組，即：

(3)

上述公式每一個等式的左右兩邊都分別減去最后一個等式的左右兩邊，由此得到：

(4)

用線性方程組表示為AX=b，其中：

(5)

(6)

(7)

根據最小二乘法，求出未知節(jié)點坐標為：

X=(ATA)-1ATb

(8)

在DV-Hop算法中，用于計算的兩個節(jié)點之間的跳數是一個整數，但實際的跳數通常不是整數。在圖1中，節(jié)點B和節(jié)點C在節(jié)點A的通信范圍R內。此時B、A之間的距離和C、A之間的距離并不相等，但節(jié)點B、C與節(jié)點A之間的跳數都被看作是1。此外，當使用最近的錨節(jié)點的平均跳距，而不是使用網絡中所有錨節(jié)點的平均跳距計算定位結果時，誤差通常會更大。因此，必須找到一種更加精確的改進DV-Hop定位算法。

圖1 節(jié)點位置示意圖

2 基于RSSI測距的改進DV-Hop定位算法

本文提出的基于RSSI測距的加權DV-Hop定位算法包括3個步驟。首先，利用RSSI算法計算節(jié)點之間的加權跳數；然后使用校正因子來改進平均跳距；最后，使用無約束優(yōu)化算法估計未知節(jié)點的位置。

2.1 基于RSSI測距的節(jié)點加權跳數計算

RSSI測距傳輸常用的損耗模型[14]如式(9)所示：

(9)

式(9)中：Pr(d0)是發(fā)射機和接收機之間距離為d0時的接收信號功率;Pr(d)是距離為d時的接收信號功率；η是路徑損耗指數，其取值范圍為1.5和5之間；Xσ是均值為零，標準差為σ的高斯隨機變量，σ的值在4 dBm和12 dBm之間。

對于給定的RSSI誤差，當節(jié)點間的距離越大時，最終的定位誤差也越大。因此，在算法的步驟1中，將RSSIj添加到廣播消息中，該廣播消息對應于從錨節(jié)點Ak到未知節(jié)點Ui的第j個廣播之后的接收信號。如果錨節(jié)點接收到的消息對應的跳數大于另一個消息對應的跳數，則錨節(jié)點丟棄對應跳數較大的消息，跳數可表示為：

hj=hj-1+Hjh1

(10)

式(10)中h1是給定的初始跳數，可由式(11)計算得出：

(11)

且有：

(12)

式(12)中，RSSI0由式(9)計算得到。

2.2 使用校正因子改進平均跳距

本文使用校正因子來改進DV-Hop算法中的平均距離，校正因子表示為：

(13)

(14)

2.3 未知節(jié)點的位置計算

由于根據最小二乘法計算未知節(jié)點的坐標會導致誤差積累，效果不佳[15]。因此本文利用無約束優(yōu)化算法[16]估計未知節(jié)點的坐標，可得如下方程組：

(15)

式(15)中：(x,y)和(xk,yk)表示未知節(jié)點Ui和錨節(jié)點Ak,k=1,2,…,n的坐標；dk,k=1,2,…,n表示錨節(jié)點和未知節(jié)點之間的距離；ek,k=1,2,…,n表示誤差。上述公式每一個等式的左右兩邊都分別減去最后一個等式的左右兩邊，得到一個超定方程組。定義常數ai，bi，ci，c和Di。i=1,2,…,n-1，且有：

(16)

(17)

那么超定方程組就可以寫成矩陣形式：

Gz=d

(18)

且有：

(19)

(20)

(21)

等式(18)可以寫成二次規(guī)劃問題

(22)

(23)

未知節(jié)點坐標可以通過求解式(22)得到。為方便求解，將式(22)轉化為無約束優(yōu)化問題，如式(24)所示：

(24)

求解式(24)可得：

z=(P+GTG+ΔI)-1GTD

(25)

ΔI是Δ>0時的正則化項，I是n+2階的單位矩陣，并且

(26)

3 仿真實驗分析

3.1 仿真參數選擇

利用Matlab軟件對本文算法進行仿真分析，并與傳統(tǒng)的DV-Hop算法、文獻[10]提出的改進的DV-Hop定位算法、文獻[11]提出的基于最優(yōu)輔助距離估計錨節(jié)點的DV-Hop定位算法以及基于RSSI測距的改進DV-Hop定位算法(最小二乘法求解)進行比較。在傳輸損耗模型中，令η=4，σ=4 dBm。仿真區(qū)域為100 m×100 m的二維平面。為了減小算法的偶然性帶來的誤差，將各個算法重復運行50次，取平均值作為最終的結果，用平均定位誤差(Average Localization Error，ALE)衡量算法性能：

(27)

式(27)中：N表示未知節(jié)點的數量；(xi,yi)表示未知節(jié)點Ui的實際坐標；(Xi,Yi)表示未知節(jié)點Ui的估計位置坐標；R表示通信半徑。

上文提到，λ是用于平衡網絡中平均跳距的參數，它與網絡環(huán)境有關。本節(jié)通過多次仿真實驗選取出合適的λ值。圖2給出了對應于不同λ值時本文算法的平均定位誤差。假設網絡中有200個節(jié)點，3種情況下錨節(jié)點數量分別為20，40，60，通信半徑為R=20 m。由圖2可知，在錨節(jié)點數量逐漸增加的過程中，平均定位誤差越來越小，綜合考慮三種不同錨節(jié)點比例下的平均定位誤差，當λ=0.7時，3種情況下的平均定位誤差都較小。因此在本文算法中，選擇λ=0.7作為仿真參數。

圖2 λ取不同值時本文算法的平均定位誤差曲線

3.2 結果分析

1)節(jié)點總數變化對平均定位誤差的影響

WSN中的傳感器節(jié)點部署是隨機的，節(jié)點總數量對定位精度有著重要影響。圖3為在不同數量的傳感器節(jié)點情況下，不同算法的平均定位誤差曲線。在100 m×100 m的二維平面內，令節(jié)點的總數量從100增加到400，而錨節(jié)點的比例始終保持在20%。每個節(jié)點的通信半徑R=20 m。由圖3可知，當傳感器節(jié)點數量不斷增加時，平均定位誤差越來越小。其原因是傳感器節(jié)點數量的增加使得節(jié)點密度也隨之提高，網絡連通性越來越好，此時未知節(jié)點可以獲得更多的定位所需的信息，并且使用無約束優(yōu)化的算法能夠提高定位精度。而當網絡中的傳感器節(jié)點數量達到一定的值時，平均定位誤差只會發(fā)生微小的變化。與其他算法相比，本文算法在定位精度方面表現更好，當節(jié)點數量為150時，本文算法的平均定位誤差為0.25，DV-Hop算法、文獻[10]算法、文獻[11]算法的平均定位誤差分別為0.53、0.49、0.41，本文算法和其余3種算法相比，平均定位誤差降低了52.8%、49.0%、39.1%。

圖3 節(jié)點總數變化時的平均定位誤差曲線

2)錨節(jié)點比值變化對平均定位誤差的影響

圖4為在不同錨節(jié)點比值的情況下，不同算法的平均定位誤差曲線。在100 m×100 m的二維平面內部署300個節(jié)點，設置通信半徑為30 m，錨節(jié)點比值從5%增加到30%。由圖4可知，在錨節(jié)點比值逐漸增大的過程中，所有算法的平均定位誤差均減小，其原因是錨節(jié)點比值的增加意味著錨節(jié)點密度增大，錨節(jié)點間的估計距離會變得更加準確，此時利用RSSI算法計算出的節(jié)點之間的加權跳數會更精確，平均跳距也會更精確。另外我們還可以看出，相同條件下，本文算法的平均定位誤差始終是最小的。當錨節(jié)點比例為30%時，本文算法的平均定位誤差有最小值0.28，此時DV-Hop算法、文獻[10]算法、文獻[11]算法的平均定位誤差分別為0.67、0.51、0.42，本文算法和其余3種算法相比，平均定位誤差降低了58.2%、45.1%、33.3%。

圖4 錨節(jié)點比值變化時的平均定位誤差曲線

3)通信半徑變化對平均定位誤差的影響

圖5為在不同通信半徑的情況下，不同算法的平均定位誤差曲線。在100 m×100 m的二維平面內部署300個節(jié)點，其中錨節(jié)點個數為60，設置通信半徑的變化范圍在15～40 m。

圖5 通信半徑變化時的平均定位誤差曲線

由圖5可知，在通信半徑逐漸增大的過程中，所有算法的平均定位誤差均在減小，這是因為在未知節(jié)點位置的計算過程中使用了無約束優(yōu)化算法，它充分考慮了節(jié)點間的測距誤差對定位結果的影響，將定位結果的計算轉化為無約束優(yōu)化問題，提高了定位精度。本文算法的定位效果始終是最好的。當通信半徑為30 m時，本文算法的平均定位誤差為0.19，此時DV-Hop算法、文獻[10]算法、文獻[11]算法的平均定位誤差分別為0.55、0.45、0.38，本文算法和其余3種算法相比，平均定位誤差降低了65.5%、57.8%、50.0%。

4)不同的定位算法對平均定位誤差的影響

圖6為利用無約束優(yōu)化算法(本文算法)和最小二乘法進行定位計算求解得到的平均定位誤差圖。在100 m×100 m的二維平面內部署300個節(jié)點，其中錨節(jié)點個數為80，設置通信半徑的變化范圍在15～40 m。由圖6可知，在通信半徑逐漸增大的過程中，兩種算法的平均定位誤差均在減小，但是，利用無約束優(yōu)化算法求得的平均定位誤差始終小于利用最小二乘法求得的平均定位誤差。因為在利用無約束優(yōu)化算法求解的過程中，加入了節(jié)點的跳數信息以及節(jié)點間的測距誤差信息，從而優(yōu)化了定位結果。當通信半徑為40 m時，利用無約束優(yōu)化算法可以獲得最小平均定位誤差為0.16。

圖6 通信半徑變化時利用最小二乘法和無約束優(yōu)化算法計算的平均定位誤差曲線

4 結論

提出一種RSSI測距和DV-Hop算法相結合的改進DV-Hop算法。首先根據節(jié)點間的RSSI測距值計算節(jié)點間的跳數，根據所有錨節(jié)點的平均每跳距離以及網絡環(huán)境參數設置校正因子以修正平均跳距，采用無約束優(yōu)化算法代替?zhèn)鹘y(tǒng)的最小二乘法計算未知節(jié)點的坐標，減小了定位誤差的累計。本文提出的改進DV-Hop算法不需要額外的硬件，和同類型的算法相比有更好的節(jié)點定位精度。