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

任克強,李 娜

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

?

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

任克強*,李 娜

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

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

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

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

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

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

1 三維DV-Hop算法分析

1.1 三維DV-Hop算法原理

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

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

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

(1)

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

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

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

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

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

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

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

圖1 未知節(jié)點與錨節(jié)點距離示意圖

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

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

圖2 節(jié)點的一跳區(qū)域示意圖

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

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

2 三維DV-Hop算法的改進

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

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

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

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

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

(2)

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

(3)

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

(4)

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

HoTPizeeff(i)=HoTPizei+errori

(5)

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

(6)

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

(7)

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

(8)

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

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

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

圖3 錨節(jié)點跳數分類示意圖

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

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

dij=Hi×hij

(9)

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

(10)

2.3 求解未知節(jié)點坐標的改進

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

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

(11)

展開式(11)得:

(12)

(13)

GaZa=Ha

(14)

利用最小二乘法可得:

(15)

最后得到未知節(jié)點i的坐標:

(16)

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

3 仿真結果及分析

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

圖4 節(jié)點隨機分布圖

(17)

(18)

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

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

圖5 未知節(jié)點定位誤差對比圖

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

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

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

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

4 結論

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

[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] 相衛(wèi)華,賈超,王華奎,等. 無線傳感器網絡三維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] 江禹生,馮硯毫,管芳,等. 無線傳感網非測距三維節(jié)點定位算法[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