基于誤差加權的三維雙曲線定位算法

任克強,李 娜

(江西理工大學信息工程學院,江西 贛州 341000)

?

基于誤差加權的三維雙曲線定位算法

任克強*,李 娜

(江西理工大學信息工程學院,江西 贛州 341000)

為了減小三維空間中對未知節點定位的誤差,提高三維DV-Hop算法的定位精度,提出一種基于誤差加權和三維雙曲線定位的三維DV-Hop改進算法。改進算法首先采用誤差加權的方法處理未知節點的平均每跳距離,然后分類選擇未知節點與錨節點之間的跳段距離,最后將二維雙曲線法擴展到三維空間計算未知節點的坐標。仿真實驗結果表明,改進算法在三維WSN環境中可以對未知節點進行有效的定位,平均定位誤差和定位精度顯著優于三維DV-Hop算法,相較于對比文獻也有一定的提升,并且錨節點密度和通信半徑對平均定位誤差和定位精度的影響較小。

無線傳感器網絡;節點定位;三維DV-Hop算法;誤差加權;雙曲線定位

無線傳感器網絡WSN(Wireless Sensor Network)是由多個低成本、低功耗的傳感器節點經過近距離通信和數據交換構成的自適應網絡[1-2]。這種傳感器網絡具有感知功能、計算功能、信息處理功能以及無線通信功能,可以對信息進行實時監測和處理,然后傳送給觀測者[3]。WSN在包括結構監測、環境監測、戰場監視和動物跟蹤等許多領域被廣泛地應用,其使用價值能否成功體現出來,關鍵在于節點的位置信息是否準確[4],因此,確定事情發生的具體所在地對于傳感器節點來說是最根本的功能之一。

WSN定位算法的研究成果眾多,但大多是針對二維平面的定位[5-6],對于三維復雜環境空間的定位算法相對較少,而三維環境定位比二維平面定位對于位置信息的要求更加充分,其空間的復雜度和對網絡的連通度、密度也相應的增加,因此二維平面情況下的定位算法不能直接應用在三維環境中[7-8]。圍繞在三維空間中實現較高精確度的節點定位問題,國內外的相關研究人員提出了眾多三維空間節點定位算法。文獻[9]基于二維Euclidean算法,把節點距離估算問題轉換成求解六面體模型各個頂點間的距離問題,并利用坐標法和四邊定位法對未知節點坐標進行確定,可以有效實現三維環境節點定位,但該算法需要節點進行兩次洪泛,增加了計算通信量,且該算法的抗干擾性也有待加強。文獻[10]將加權平均思想引入到三維DV-Hop定位算法中,建立加權平均跳距的思想來達到減小節點定位誤差的目的,但該算法沒有考慮三維DV-Hop定位算法在計算求解未知節點坐標時其自身本就存在著較大誤差問題。文獻[11]將APIT算法延伸至三維空間環境中,形成3D-GPIT算法,通過獲取未知節點的最佳估算區域,使用三維網格方法對其估算區域進行優化,有效降低了定位誤判的問題,但該算法在節點稀少的條件下不能完成網格定位而失效。文獻[12]在三維APIT基礎上提出了一種基于多面體質心循環迭代的APIT定位算法,用質心迭代法代替網格掃描法提高算法的計算效率,并且對節點稀少的情況進行再次定位,解決了三維WSN環境中APIT定位算法覆蓋率低的問題。文獻[13]通過采取粒子群優化技術的慣性權重的方法,對三維DV-Hop算法得到的未知節點估算坐標進行修正,在不增添格外的硬件設施和通訊成本的情形下提升了算法定位精度和穩定性。文獻[14]通過MDS-MAP算法對節點的坐標位置進行計算,并且采用更加有效的坐標映射方法來實現更高精度的坐標轉化,這使得節點在三維環境定位精度上有很大的提升。文獻[15]加入了計算未知節點時出現的偏差值,使用DV-Hop算法中節點間跳數和平均每跳距離的求解方法,并且利用加權質心方法對未知節點估算坐標進行修正,獲得了較好的定位性能。

針對三維空間中的節點定位問題,本文在分析和研究經典三維DV-Hop算法的基礎上,提出一種基于誤差加權的三維DV-Hop改進算法,以改善三維空間的節點定位精度,提高三維DV-Hop算法的定位性能。

1 三維DV-Hop算法分析

1.1 三維DV-Hop算法原理

三維DV-Hop定位算法是由二維DV-Hop定位算法拓展而來,它的基本思想與二維定位算法類似,其定位過程主要分為3個階段:

①錨節點通過廣播的方式在網絡中發送自身節點的信息,其中包括自身位置的坐標信息和跳數值信息,并設置為0。接收到此信息的所有節點都僅保存最小跳數信息后,將跳數的值加上1發送給鄰居節點,直到全部節點都獲得到整個網絡的錨節點的最小跳數值。

②獲取到整個網絡的錨節點具體位置信息和相距最小跳數值后,采用式(1)可以求解出錨節點i的平均每跳距離。

(1)

式中:(xi,yi,zi)、(xj,yj,zj)分別為錨節點i與錨節點j的實際位置坐標,hij是錨節點i與錨節點j(i≠j)兩者間的最小跳數值。

然后錨節點將獲得的平均每跳距離信息發送到網絡當中,未知節點只是保留最開始得到的錨節點數據信息,并發送給鄰居節點,再根據到全部錨節點的最小跳數值可以求解其與全部錨節點間的跳段距離。

③當未知節點得到4個或4個以上已知錨節點的具體信息后,選擇用極大似然估計法[16]來確定自己的位置坐標。

1.2 三維DV-Hop算法存在的問題

三維DV-Hop算法具有對硬件設施條件要求不高,計算簡單等優點,但此算法的定位主要是依靠網絡連通度來進行,故在對節點定位時本身就會形成一定誤差。

①節點的精度和覆蓋率都會因為已知的錨節點密集程度及其分布情況的變化而變化。錨節點位置越密集,分布越均勻,則節點的定位精確度就會越高。而在實際情況下,常常隨機的將錨節點安置在被監測的區域中,因此其分布極大可能是不均勻的。另外一方面,錨節點一般是攜帶GTP定位技術的節點,其費用非常的高,大量且均勻放置錨節點是不經濟的。所以,只是靠網絡中少數錨節點數據信息來進行定位會有較大誤差形成,網絡邊沿的未知節點也會因為接收到少量錨節點的信息或者接收不到錨節點的信息而不能進行定位,這會降低節點的定位覆蓋率。

②未知節點和錨節點用它們間的跳數值乘上錨節點的平均每跳距離來表示它們之間的跳段距離,但在實際環境情況中錨節點到未知節點的途徑一般都不成直線,并且節點密度越小折線率越高,估算出來的距離偏差就會越大,定位精度就會越不準確。例如在圖1中,S1、S2、S3是3個錨節點,節點A和其他節點是未知節點,如果已知全部錨節點間的實際距離和各節點間的跳數值,那么就可以求解出各錨節點的平均每跳距離。

圖1 未知節點與錨節點距離示意圖

由式(1)得到S2的平均每跳距離是(40+85)/(2+5)=17.85m,因為A是從距離它最近的錨節點獲取平均每跳距離的,所以A到S1、S2、S3的距離分別是:

如假設節點A到S1、S2和S3之間呈一條直線,則實際上A到S1、S2和S3之間的距離分別為88m、48m和68m,那么節點A由跳數值和平均每跳距離相乘得到的距離與實際距離就分別相差16.6m、12.3m和14.45m。由此可見,計算距離與實際跳距有著較大的誤差,而且實際節點之間的每一跳距離都不是相等的,因為在節點的通信區域內未知節點相距錨節點的遠近程度基本上都不一樣,但未知節點從自己得到的信息來考慮都認為自己是在距離錨節點一跳的地方。例如在圖2中,假設實心圓點代表錨節點,空心圓點代表未知節點,R代表節點的通信半徑,那么節點A的1跳范圍如圖2所示。

圖2 節點的一跳區域示意圖

由圖2可以看出,節點A到節點B的距離比到節點C的距離要短得多,但是節點A判斷節點B、C都在它的一跳位置。根據三維DV-Hop算法計算出來的A到B的跳段距離和A到C的跳段距離相等,但實際上A到B的距離與A到C的距離并不相等,所以求解出的跳段距離和實際距離有著較大的偏差。

③在未知節點獲取錨節點的平均每跳距離之后,選擇用極大似然估計法來求解得出它的坐標。采用極大似然估計法求解未知節點坐標時,即求解線性方程Ax=b,而兩個矩陣A和b都會對未知節點坐標的求解產生很大影響,因為矩陣b中有些未知節點與錨節點的距離偏差比較大,直接用于求解會出現不小的誤差。另一方面是由于硬件設備自身的某些缺陷也會對矩陣A造成一定的誤差。

2 三維DV-Hop算法的改進

本文為了降低三維DV-Hop算法定位不準確、誤差較大兩方面的問題,分別從未知節點平均每跳距離、未知節點到錨節點間的跳段距離以及求解未知節點坐標3個方面對三維DV-Hop算法進行改進。

2.1 求解未知節點平均每跳距離的改進

在節點隨機放置的WSN環境中,所有錨節點的平均每跳距離誤差值都不一樣,未知節點僅僅依據距離最近的錨節點來求解其平均每跳距離,求解出來的結果會有較大的誤差,而且一個最近的錨節點并不能確切地說明全網實際周邊的相關情況。因此,本文算法在計算未知節點平均每跳距離時,將把全部錨節點的平均每跳距離都考慮進去,并采用跳距誤差加權策略對接收到的全部錨節點平均每跳距離做加權處理,對誤差較小的錨節點賦給較大權值,通過這樣的權值處理就可以平衡總體影響未知節點定位誤差的因素,從而可以更好地說明未知節點周圍網絡的情況,以提升算法對節點的定位精度。

如果用(xi,yi,zi)和(xj,yj,zj)分別代表錨節點i和j的實際位置坐標,則錨節點i的平均每跳距離HoTPizei可以用式(1)計算得到。

按照各錨節點間的最小跳數值可以求出錨節點i與j之間的跳段距離:

(2)

已經知道錨節點間的坐標信息,則可以得到錨節點i與j之間的實際距離:

(3)

在WSN中,假定錨節點數量為m,那么通過式(2)中的跳段距離和式(3)中的實際距離可以得到錨節點i的平均每跳距離誤差:

(4)

通過式(4)中得到的平均每跳距離誤差可以求解出錨節點i的有效平均每跳距離:

HoTPizeeff(i)=HoTPizei+errori

(5)

全部錨節點通過式(4)得到平均每跳距離誤差后,相加求其平均值當作該網絡的平均每跳距離誤差,再對該網絡的平均每跳距離進行修正。則全網錨節點平均每跳距離誤差:

(6)

網絡中如果錨節點和未知節點相距越近,那么它們之間的平均每跳距離誤差就會越小,則對未知節點跳段距離的估算就能越準確。假設未知節點M已經得到n個錨節點位置信息,則未知節點M對得到的n個錨節點位置信息賦給不同的權值。對n個錨節點的權值按式(7)所示進行處理:

(7)

最后,未知節點對得到的n個錨節點有效平均每跳距離做出基于wi的加權處理,所以它自身的平均每跳距離:

(8)

2.2 求解未知節點到錨節點間的跳段距離的改進

三維DV-Hop算法中未知節點選擇用存在誤差的跳段距離來替代節點間的實際距離,這無疑會使得該方法本身就存在誤差。本文在求解未知節點到錨節點的跳段距離時,將考慮它們的相關信息,因為在WSN中未知節點與錨節點離得越近其定位就能越準確,所以在求解未知節點到相距1跳的錨節點的距離時使用三維DV-Hop算法的思想來求解,而在求解未知節點到相距非1跳錨節點的距離時則采用以下方法求解。

將未知節點A附近的錨節點按跳數分成1跳錨節點和非1跳錨節點兩大類,例如在圖3中,C、D都是距離A非1跳錨節點,而B則是距離A的1跳錨節點。

圖3 錨節點跳數分類示意圖

假定s是離未知節點非1跳錨節點,j是離未知節點1跳的錨節點。Dsj為s與j之間的實際距離,hsj為s與j之間的最小跳數。

對于距離未知節點1跳的錨節點,用式(9)求解它們兩者間的跳段距離。

dij=Hi×hij

(9)

對于距離未知節點非1跳錨節點,用式(10)求解它們兩者間的跳段距離。

(10)

2.3 求解未知節點坐標的改進

三維DV-Hop算法運用極大似然估計法這一經典方法來求解未知節點位置坐標時,其求解結果會產生較大偏差。本文的策略是將二維雙曲線法引入到三維空間中代替原始算法中的經典方法求解節點位置坐標,以進一步提升算法對節點的定位精度。

假設錨節點i的實際坐標是(xi,yi,zi),未知節點的位置坐標是(x,y,z),則它們兩者之間的歐氏距離是:

(11)

展開式(11)得:

(12)

(13)

GaZa=Ha

(14)

利用最小二乘法可得:

(15)

最后得到未知節點i的坐標:

(16)

通過雙曲線方法,可以避免方程組的直接相減,減少由估距誤差帶來的累積誤差,能夠有效提高定位算法的精度。

3 仿真結果及分析

為了測試本文算法的性能,基于Windows7+MATLAB R2015b仿真平臺對三維DV-Hop算法、文獻[15]算法和本文算法進行仿真比較,并對仿真得出的結果進行對照分析。仿真實驗環境:在100 m×100 m×50 m的三維空間環境區域內隨機安置500個節點,包括未知節點和錨節點,圖4是一次實驗的節點隨機部署圖,圖中實心圓點代表未知節點,菱形代表錨節點。

圖4 節點隨機分布圖

(17)

(18)

式中:(xi,yi,zi)和(ai,bi,ci)分別為未知節點i的估算坐標和實際坐標。

圖5是在相同場景下三維DV-Hop算法與本文算法對未知節點的定位誤差對比圖。由圖5可以得出,除了極少數的幾個點外,本文算法的定位誤差顯然小于三維DV-Hop算法,且本文算法的定位誤差波動也比較穩定。

圖5 未知節點定位誤差對比圖

圖6是在通信半徑R=30 m,錨節點取從20到45之間變化情形下,三維DV-Hop算法、文獻[15]算法和本文算法的定位性能對比曲線。在取定節點總量和通信半徑條件下3種算法的平均定位誤差和定位精度曲線都隨著錨節點數量的不斷增加而呈現遞減變化,即平均定位誤差降低、定位精度提升;當錨節點數量一樣時,本文改進算法的平均定位誤差和定位精度均比三維DV-Hop算法和文獻[15]算法要好,且本文改進算法的平均定位誤差曲線和定位精度曲線始終處于最下方。由此可見,本文所提出的算法相比三維DV-Hop算法很顯然減小了節點定位誤差,提升了算法定位精度,算法性能優于三維DV-Hop算法和文獻[15]算法,且節點平均定位誤差曲線和定位精度曲線都較為平穩,受錨節點數量的影響較小。

圖6 不同錨節點數量的算法定位性能對比曲線

圖7 不同通信半徑的算法定位性能對比曲線

圖7是在錨節點數量為20,通信半徑取從20 m到45 m之間變化的情形下,三維DV-Hop算法、文獻[15]算法和本文算法的定位性能對比曲線。在取定節點總量和錨節點數量條件下,隨著通信半徑的不斷加大3種算法的平均定位誤差都有緩慢增大的趨勢,如圖7(a)所示,這是因為通信半徑的不斷加大會使得節點間跳數的誤差增大,導致節點平均每跳距離誤差增大,所以平均定位誤差會隨著節點通信半徑的加大而有所增大;但3種算法的定位精度都隨著通信半徑的加大而呈現遞減變化,如圖7(b)所示。當通信半徑一樣時,本文改進算法的平均定位誤差和定位精度均比三維DV-Hop定位算法和文獻[15]算法要好,且本文改進算法的平均定位誤差曲線和定位精度曲線同樣始終處于最下方。由此可見,本文所提出的算法相比三維DV-Hop算法很顯然減小了節點定位誤差,提升了節點定位精度,算法性能優于三維DV-Hop算法和文獻[15]算法,且平均定位誤差曲線和定位精度曲線都比較穩定,受通信半徑的影響相對要小一些。

4 結論

分析了三維DV-Hop算法在估算節點跳距和未知節點坐標時存在的缺陷,在此基礎上,以降低節點定位誤差,提升節點定位精度為目的,提出了一種基于誤差加權和三維雙曲線定位的三維DV-Hop改進算法。改進算法采用誤差加權、錨節點按跳數分類以及三維雙曲線定位3種策略對三維DV-Hop算法進行改進,并在節點總量不變、錨節點數量和節點通信半徑變化的三維WSN環境下進行了算法定位性能比較仿真實驗。從實驗數據可以得出,本文改進方案在不增加硬件設施和通信成本的前提下,改進方案的性能均好于三維DV-Hop算法及相關文獻,且本文改進方案的平均定位誤差和定位精度受錨節點密度和通信半徑的影響較小,可以更好的適應隨機分布的三維WSN環境。如何進一步改善三維空間的節點定位精度是后續研究的重點工作。

[1] Zhu C,Zheng C L,Shu L,et al. A Survey on Coverage and Connectivity Issues in Wireless Sensor Networks[J]. Journal of Network and Computer Applications,2012,35(2):619-632.

[2] 錢志鴻,王義君. 面向物聯網的無線傳感器網絡綜述[J]. 電子與信息學報,2013,35(1):215-227.

[3] Gui L Q,Val T,Wei A,et al. Improvement of Range-Free Localization Technology by a Novel DV-Hop Protocol in Wireless Sensor Networks[J]. Ad Hoc Networks,2015,24(Part B):55-73.

[4] Xu E Y,Ding Z,Dasgupta S. Source Localization in Wireless Sensor Network from Signal Time-of-Arrival Measurements[J]. IEEE Transations on Signal Processing,2011,59(6):2887-2897.

[5] 周玲,康志偉,何怡剛. 基于三角不等式的加權雙曲線定位DV-Hop算法[J]. 電子測量與儀器學報,2013,27(5):389-395.

[6] 范時平,羅丹,劉艷林. 基于跳距與改進粒子群算法的DV-Hop定位算法[J]. 傳感技術學報,2016,29(9):1410-1415.

[7] 舒堅,劉琳嵐,陳宇斌,等. 3D-RABLC:一種基于LQI置信度的三維空間定位求精算法[J]. 通信學報,2012,33(7):125-134.

[8] Zhang B,Fan J,Dai G,et al. A Hybrid Localization Approach in 3D Wireless Sensor Network[J]. Internation Journal of Distributed Sensor Networks,2015,2015:1-11.

[9] 唐良瑞,宮月,羅藝婷,等. 一種基于Euclidean的無線傳感器網絡三維定位算法[J]. 電子學報,2012,40(4):821-825.

[10] 李琳,趙可,林志貴,等. 基于加權的三維DV-Hop定位算法[J]. 控制工程,2015,22(4):761-764.

[11] 相衛華,賈超,王華奎,等. 無線傳感器網絡三維APIT網格化算法[J]. 傳感技術學報,2012,25(5):639-643.

[12] 胡偉,朱西平,文紅,等. 基于四面體質心迭代的三維APIT定位算法研究[J]. 傳感技術學報,2013,26(10):1432-1436.

[13] Chen X,Zhang B. 3D DV-Hop Localization Scheme Based on Particle Swarm Optimization in Wireless Sensor Networks[J]. International Journal of Sensor Networks,2014,16(2):100-105.

[14] 張亞杰,段渭軍,王福豹,等. 改進的距離重構三維定位算法[J]. 傳感技術學報,2014,27(12):1681-1686.

[15] 江禹生,馮硯毫,管芳,等. 無線傳感網非測距三維節點定位算法[J]. 西安電子科技大學學報(自然科學版),2012,39(5):140-147.

[16] Safa H. A Novel Localization Algorithm for Large Scale Wireless Sensor Networks[J]. Computer Communications,2014,45(3):32-46.

Three Dimensional Hyperbolic Localization Algorithm Based on Error Weighting

REN Keqiang*,LI Na

(School of Information Engineering,Jiangxi University of Science and Technology,Ganzhou Jiangxi 341000,China)

In order to reduce the error of localization for unknown nodes in the three dimensional space,an improved three dimensional DV-Hop algorithm based on the error weighting and the three dimensional hyperbolic localization was proposed to enhance the localization accuracy of three dimensional DV-Hop algorithm. Firstly,the improved algorithm used the error weighting method to deal with the average per-hop distance of unknown nodes. Then,the hop distance between unknown nodes and anchor nodes was classified and selected. Finally,the two dimensional hyperbolic method is extended to the three dimensional space to calculate the coordinates of unknown nodes. The simulation experimental results show that the improved algorithm can effectively locate unknown nodes in the three dimensional WSN environment,the average localization error and localization accuracy are obviously superior to three dimensional DV-Hop algorithm,compared with comparative literature also has a certain improvement,and anchor node density and communication radius have less effect on the average localization error and localization accuracy.

wireless sensor network;node localization;3D DV-Hop algorithm;error weighting;hyperbolic localization

任克強(1959-),男,教授,碩士研究生導師,主要研究方向為圖像與視頻處理、無線傳感器網絡、信息隱藏,jxrenkeqiang@163.com;

李 娜(1991-),女,碩士研究生,主要研究方向為無線傳感器網絡。

2016-10-16 修改日期:2016-12-22

TP393

A

1004-1699(2017)05-0752-06

C:6150P

10.3969/j.issn.1004-1699.2017.05.020