基于校正節點的DV-Hop定位算法改進

梁建國, 于建志, 張 浩, 傅 游

(1. 山東科技大學 計算機科學與工程學院, 山東 青島 266590;2. 青島港灣職業技術學院 信息與電氣工程學院, 山東 青島 266404)

目前,隨著“互聯網+”行動計劃的提出,互聯網產業發展勢頭更加迅猛,而“互聯網+”的發展,必將帶來“大數據+”“云計算+”以及“物聯網+”等的發展,因為它們是其發展的基石,也是其通往云端的天梯.其中的物聯網技術作為“互聯網+”的發展的基石,其發展也是日新月異,它的應用已經使我們的生產生活方式發生了巨大變化.無線傳感器網絡WSN(wireless sensor network)技術作為物聯網發展的重要組成部分從一出現就備受關注[1].它融合了目前先進的傳感器技術、微電子技術以及無線通信技術等信息技術,是一個交叉科學.目前無線傳感器網絡技術已經在智能醫療、智能農業、智能交通、智能物流以及環境監測等領域被廣泛使用,其關鍵技術主要有節點定位技術、自組織網絡路由技術、能耗技術、數據融合技術以及信息安全技術等,而作為其發展基礎的節點定位技術的研究一直是眾多研究者關注的熱點,因為在無線傳感器網絡中,失去位置信息的節點將變得毫無意義[2-3].

目前,眾多研究者提出的無線傳感器網絡節點定位算法根據是否需要進行距離的測量可以分為兩類,一類是基于測距的節點定位算法,另一類是無需測距的節點定位算法.前者主要利用已有的測距技術,包括RSSI(radio signal strength indicator)、AOA(angle of arrival)、TDOA(time difference of arrival)等,進行點與點之間的距離或方向的測量,其定位精度高,但需要額外增加測距設備,成本較高[4];后者主要通過已知節點與未知節點之間進行信息交換來進行節點的距離測量,該類算法以質心定位算法、凸規劃定位算法、DV-Hop定位算法等為其典型代表,雖然其定位精度不高,但是功耗低,對節點的硬件要求也不高,并且能滿足多數應用中對節點定位的需求[5-14].

DV-Hop定位算法作為一種無需測距的算法,由于其計算速度快,一直備受關注,然而,在一些場景下,DV-Hop定位算法的定位精度并不高.為了提高定位精度,研究者提出了很多改進方法.文獻[15]提出了基于測距技術RSSI估算節點間的距離來減低測距誤差,文獻[16]中利用跳數的倒數進行加權同時對求解的最小二乘法進行加權而進行優化,另一些研究者將粒子群優化算法[17],蛙跳算法[18],蜂群算法[19],人工魚群算法[20], 細菌覓食優化算[21],布谷鳥搜索算法[22-23]等智能算法引入DV-Hop定位算法對其改進,然而上述這些算法在提高精度的同時,有的需要增加硬件,有的計算復雜度較高,給本身計算能力就很有限的無線傳感器網絡節點帶來較大壓力,同時也增加了能量的消耗.

針對DV-Hop定位算法存在的問題, 本文提出一種改進的DV-Hop定位算法, 其主要思想是: 在不增加硬件的同時盡量保持算法復雜度的基礎上, 利用相同網絡拓撲結構中, 未知節點與距離自己較近的錨節點受到環境等各方面因素的影響相近的原則, 通過尋找距離未知節點最近的錨節點作為校正節點, 將找出的校正節點作為未知節點, 用DV-Hop定位算法估算其位置信息, 求出未知節點的校正誤差值, 最后利用校正誤差值對未知節點進行校正, 減小未知節點的定位誤差.

1 DV-Hop定位算法

APS(ad hoc positioning system)是最早被提出的利用已知位置的錨節點找到未知節點位置的系列分布式定位算法, 主要包括DV-Hop, DV-Distance和Euclidean三種算法. 其中DV-Hop定位算法由于利用網絡的連通度和節點間的跳數值而不引入任何測量工具備受青睞[24]. DV-Hop定位算法根據每階段的實現任務不同可以分為計算最小跳數、 估算實際距離和定位未知節點坐標3個階段, 下面詳細說明這3個階段的實現過程.

1.1 計算最小跳數階段

在網絡初始化結束以后,網絡中的節點進行信息交互,其中的錨節點會將包含自身位置信息的分組(包括初始值為0的跳數字段)在網絡中進行廣播.網絡中的接收節點用表(xi,yi,hopi)對其接收的信息進行標識,其中(xi,yi)是錨節點i的坐標,hopi是錨節點i距離接收節點間的最小跳數.如果第一次接收廣播信息,直接記錄并且跳數加1,之后繼續轉發;如果已經接收過來自該節點的廣播信息,則進行比較,如果接收的跳數信息值比記錄的值大則拋棄,小則保留并且跳數加1,之后繼續轉發.通過這種方式,使得每個節點記錄的跳數距離值總是距離錨節點的跳數最小.

1.2 估算實際距離階段

在第1階段結束以后,網絡中未知節點與錨節點的跳數已經獲得,而網絡中錨節點的位置信息是已知的.因此可以用式(1)估算錨節點的平均每跳距離,其中錨節點i,j的橫縱坐標分別為(xi,yi), (xj,yj) ,錨節點i,j之間的最小跳數為hj,其中i,j不相等.

(1)

通過式(1)的計算,網絡中所有錨節點的平均每跳距離被求出,之后每個錨節點將自己的所擁有的平均每跳距離在網絡中進行廣播,未知節點接收所有廣播值,但僅記錄距離自己最近的錨節點的廣播值,同時將接收的廣播轉發給鄰居節點,并將自己記錄的值作為自己與其他錨節點的平均每跳距離.

假如HopSizei為未知節點i,j記錄的平均每跳距離,hoppk為其與錨節點i之間的最小跳數,可以用式(2)計算兩者之間的跳段距離

dpk=HopSizei×hoppk.

(2)

1.3 定位未知節點坐標階段

通過第2階段的計算,未知節點與3個或3個以上的錨節點之間的距離被求出,這樣就可以利用基本的定位測量方法(例如三邊測量法、極大似然估計法或最小二乘法)進行未知節點的定位.未知節點p的坐標可以通過式(3)計算,

(3)

將式(3)視為線性方程組AX=b,解之可得X=(ATA)-1ATb,其中A,X,b如下.

2 利用校正節點改進DV-Hop定位算法

在DV-Hop定位算法估算實際距離階段,雖然對于每個錨節點來說其計算的平均每跳距離都是準確的,但是實際的網絡拓撲結構中,存在這樣兩個問題:一個是節點之間的路徑通常為折線而非直線;另一個是網絡中的節點分布是隨機的,而非均勻分布,同時跳段之間的距離也是非均勻的.這兩個問題的存在使得估算出的距離與實際距離之間存在著偏差,并且節點間距離越遠,這種偏差也會變得越大,因此必須找出一種合理的方法對其進行修正.

本文提出的改進算法是建立在原DV-Hop定位算法的基礎上,不改變其前2個階段的計算過程,著重關注第3階段的改進.通過上面分析可知,未知節點與錨節點之間的距離估算誤差是傳統DV-Hop算法的定位誤差主要來源所在,本算法改進的思路是盡量減小第二部分中產生的誤差造成的誤差偏大的影響.

(4)

式中,di表示利用傳統DV-Hop定位算法計算出的未知節點p與錨節點i之間距離,ei表示計算出di與未知節點p與錨節點i真實距離之間的誤差.根據式(4),則式(3)可以用式(5)表示:

(5)

由此可見,DV-Hop定位算法如果要取得較高的定位率,可以通過減小距離誤差值ei來獲得.考慮到在相同網絡拓撲結構中,未知節點與距離自己較近的錨節點受到環境等各方面因素的影響相近,因此,本文提出的算法用與未知節點距離較近的錨節點來校正其距離誤差值.

首先,尋找網絡中未知節點的最近錨節點,尋找依據是使用傳統DV-Hop定位算法計算出的錨節點的平均每跳距離與未知節點距其最小跳數之積求出的距離,距離最小者的錨節點將作為該未知節點的校正節點,如圖1所示,如果距離未知節點p最近的錨節點為k,則將其作為未知節點p的校正節點.

圖1校正節點選取示意圖
Fig.1 Correcting node selection diagram

(6)

由于錨節點k與未知節點p距離最近,在使用DV-Hop定位算法估算其預測值時,受到的測距誤差因素相同,因此可以近似認為未知節點與錨節點具有相同的誤差值,因此將錨節點k作為未知節點p的校正節點,并將其誤差值作為未知節點p的校正誤差值,則未知節點p與錨節點i之間的距離可以用式(7)表示,

(7)

在實際應用的過程中,如果選取的校正節點與未知節點在1跳通信半徑范圍之內,那么可以使用,如果在1跳通信范圍內無校正節點,就需要尋找次校正節點,可以通過2種方式尋找次校正節點,一種是尋找1跳通信范圍之外的錨節點,另一種是將已經定位的節點升級為錨節點進行校正,如果未知節點周圍錨節點分布較少,可以選擇后者,如果未知節點1跳通信范圍內無錨節點,2跳范圍內有錨節點,則可以選擇前者,具體選擇哪種,需要根據實際情況來選擇.

3 改進后DV-Hop定位算法的實現

假設M個錨節點的坐標為(x1,y1),(x2,y2),…,(xM,yM),錨節點的標識為id,N個未知節點隨機分布在網絡中,節點通信半徑為R,限制廣播包最大跳數為hmax.

1) 初始化網絡,設定網絡中錨節點數為M,未知節點數為N,節點通信半徑為R,限制廣播包最大跳數為hmax.

2) 錨節點向網絡中其他節點廣播包含自身位置、跳數以及廣播包最大跳數的數據報,數據包格式為{id,xi,yi,hi,hmax},hi初始值為0.

3) 網絡中的節點接收廣播包,如果已經接收,則與已經接受的信息進行比較并保存包含最小跳數的信息;如果沒有接收,則直接保存信息.

4) 每個錨節點利用式(1)計算平均每跳距離,并將包含距離信息的數據包廣播到網絡中.

5) 網絡中的所有未知節點接收步驟4中錨節點發送廣播信息,如果第一次接收,直接保存,否則通過與自身已經保存的廣播信息進行比較,將與自己最近的錨節點信息進行記錄.在廣播結束以后,使用式(2)計算所有未知節點到每個錨節點的距離.

6) 未知節點通過使用標準的最小均方差估計法計算未知節點的坐標信息.

7) 未知節點尋找最近的錨節點將其作為校正節點,同時將其作為未知節點,使用未知節點的坐標計算方法估算錨節點即校正節點的坐標.

8) 根據式(6)計算錨節點預測值與精確值之間的誤差,并將包含誤差值的數據包廣播到網絡中.

9) 未知節點在接收到校正節點的校正誤差值以后,利用式(7)重新計算未知節點的坐標.

4 仿真實驗及分析

本部分主要介紹算法的仿真以及仿真定位誤差結果的分析,為了比較本文提出的算法與改進前算法的定位性能,同時與文獻[25]中提出的算法(記作IDV-Hop),文獻[26]中提出的算法(記作PDV-Hop)進行仿真實驗對比,利用MATLAB 7.0軟件對其進行仿真,每次仿真4種算法都被測試100次,然后取其平均值作為測試結果.網絡拓撲結構的參數模型如下:所有節點分布在100 m×100 m的正方形區域中,未知節點與錨節點被隨機分布在此區域中,并且假定所有節點通信半徑相同,分別研究錨節點數、通信半徑以及網絡密度的變化對改進前后算法的性能影響.如圖2所示,圓圈代表未知節點, 星型代表錨節點.

○—未知節點; ?—錨節點.
圖2 WSN拓撲結構
Fig.2 WSN topology diagram

在仿真過程中,定位誤差由平均定位誤差函數表示,

(8)

4.1 不同節點總數對算法定位性能的影響

仿真實驗過程中,節點總數從50變化到150,變化步長為10,錨節點數為節點總數的20%,節點通信半徑為30 m.

從圖3折線變化趨勢可以看出,在節點通信半徑保持不變的情況下,節點總數的增加會使算法定位誤差呈現減小趨勢.出現此種變化趨勢的原因是由于隨著網絡中節點總數的增加,網絡中每個節點的鄰居節點也在增加,使得整個網絡的連通性加強,從而使求得的錨節點平均每跳距離誤差減小,同時也使得求出的未知節點與錨節點的距離更加接近真實距離,因此4種定位算法的定位誤差也在減小.

圖3不同節點總數下的平均定位誤差對比

Fig.3 Comparison of average locationerrors under different numbers of nodes

從圖3還可以看出,改進后的算法比傳統DV-Hop,IDV-Hop和PDV-Hop算法定位精度分別提高大約13.5%,8.9%,5.6%,因此可知改進的算法的定位率在相同情況下高于其他3種定位算法.

4.2 不同錨節點數對算法定位性能的影響

在本次仿真實驗過程中,錨節點數占節點總數的比例從5%變化到40%,變化步長為5%,節點總數保持100,節點通信半徑為30 m.

從圖4折線變化趨勢可以看出,在網絡中錨節點數逐漸增加的情況下,4種定位算法的定位誤差都在減小,并且在錨節點數增加到一定程度后,下降趨勢變緩.究其原因是由于在固定網絡拓撲結構中,在錨節點數量比例增加的情況下,網絡連通度增大,錨節點與未知節點間的跳數在減少,從而使錨節點和未知節點之間的估算距離更加接近真實距離,因此算法的定位誤差在減小.

圖4不同錨節點比例下平均定位誤差比較

Fig.4 Comparison of average position error with different numbers of anchor nodes

從圖4還可以看出,改進后的算法比傳統DV-Hop,IDV-Hop和PDV-Hop算法定位精度分別提高大約14%,9.3%,5.5%,這說明改進的算法在相同情況下定位率優于其他3種定位算法.

4.3 不同節點通信半徑對算法定位性能的影響

在仿真過程中,網絡中節點通信半徑取值為20 m,25 m,……,50 m,節點總數保持100,錨節點數占節點總數的20%.

圖5所示的折線變化趨勢表明,在節點通信半徑逐漸增加的情況下,4種定位算法的定位誤差都在逐漸減小,并且在節點通信半徑增加到一定程度后,減少趨勢逐漸變緩,這是由于在節點總數一定的情況下,隨著節點通信半徑的增加,網絡的連通度在增加,這樣網絡中的未知節點的鄰居節點也在增加,因此算法的定位誤差在減小.

圖5不同節點通信半徑下平均定位誤差比較

Fig.5 Comparison of average position error with different communication radius

從圖5還可以看出,改進后的算法比傳統DV-Hop,IDV-Hop和PDV-Hop算法定位精度分別提高大約12.8%,9.2%,5.5%,這說明改進的算法在相同情況下定位率優于其他3種算法.

5 結 論

無需測距的定位算法DV-Hop由于其易于實現以及對硬件依賴性小而在無線傳感器網絡中廣泛使用,但是由于定位誤差大不適合在定位精度要求較高的場合,為此本文在研究DV-Hop定位算法基礎上提出利用距離最近的錨節點作為校正節點的改進算法,最后并對提出的算法進行仿真驗證,通過驗證表明,提出的算法在減小定位誤差上有明顯的效果,說明其具有良好的性能.