張亞杰,段渭軍*,王福豹,高 昂

(1.西北工業(yè)大學電子信息學院,西安 710072;2.物聯(lián)網技術及應用國家地方聯(lián)合工程實驗室,西安 710072)

?

改進的距離重構三維定位算法*

張亞杰1,2,段渭軍1,2*,王福豹1,2,高 昂1,2

(1.西北工業(yè)大學電子信息學院,西安 710072;2.物聯(lián)網技術及應用國家地方聯(lián)合工程實驗室,西安 710072)

針對三維定位算法中節(jié)點坐標轉換精度低的問題,在距離重構多維定位算法DR-MDS的基礎上,提出了改進的距離重構三維定位算法。該算法在距離重構和MDS-MPA算法的思想下,采用優(yōu)化的最小均方根偏差幾何中心修正算法RMSD-GCC(Root Mean Square Deviation-Geometric Center Correction),先計算出坐標轉換矩陣,然后利用錨節(jié)點的幾何中心對所有節(jié)點進行修正,實現(xiàn)節(jié)點從相對坐標向絕對坐標較高精度的轉換。算法可以實現(xiàn)有效的坐標轉換,獲得較好的定位效果。實驗結果顯示,與原多維定位算法相比,在不引入測距誤差的情況下,改進算法在測距半徑為15 m時定位精度提高14%,定位誤差縮小至0.63 m,測距半徑為35 m時,定位精度提高87%,定位誤差幾乎為0。該改進算法在三維空間中有更高的節(jié)點定位精度。

無線傳感器網絡;三維定位;坐標轉換;幾何中心修正

作為新一代的傳感器網絡,無線傳感器網絡WSNs(Wireless Sensor Networks)在軍事國防、環(huán)境監(jiān)測、智能家居、建筑物狀態(tài)監(jiān)控、城市交通、空間探索以及醫(yī)療健康監(jiān)測等領域都有重要的科研價值和非常廣泛的應用前景[1]。

無線傳感器網絡由大量微小型傳感器節(jié)點組成,以無線通信的方式形成一個局部網絡系統(tǒng),實現(xiàn)目標物、目標區(qū)域的信息感知、數(shù)據采集以及對感知對象的信息處理,并發(fā)送給觀察者。沒有位置信息的數(shù)據采集是毫無意義可言的,節(jié)點的絕對位置信息在無線傳感器網絡的應用中至關重要。

當前,無線傳感器網絡節(jié)點定位的研究及實現(xiàn)都主要集中在二維平面的定位上[2],而在實際的節(jié)點部署中,節(jié)點通常被隨機放置在三維空間中,二維空間定位已經無法滿足當前的需求。而三維定位需要更加充分的位置信息,其網絡大小、密度以及空間復雜度也隨之增加,使得二維空間的定位算法無法直接在三維定位中使用[3-4]。實現(xiàn)高精度的無線傳感器網絡節(jié)點定位不僅必要,而且具有很重要的現(xiàn)實意義[5]。

1 相關工作

現(xiàn)在已經有很多關于三維空間定位的研究。全球定位系統(tǒng)GPS(Global Position System)是目前最為成熟、使用最廣泛的定位系統(tǒng),具有定位精度高、實時性好、抗干擾能力強等特點。但是無線傳感器網絡節(jié)點通常能源有限、體積較小、成本較低,GPS設備不適合在無線傳感器網絡中過多使用。

文獻[3]提出一種基于LQI置信度的三維空間定位求精算法,依據大量的節(jié)點實驗劃分LQI置信度,并基于置信度修正RSSI值,減小測距誤差對定位的影響。實驗結果表明其算法較大程度提高了三維定位精度。

文獻[4]通過信標節(jié)點發(fā)送廣播信號的方法來進行測距,未知節(jié)點基于信號強度來獲得與信標節(jié)點之間的距離,采用球域交叉位置的重心來估計未知節(jié)點的坐標。

文獻[6]根據建筑物樓層高度固定的結構特點,提出一種分層結構的定位算法,相比于DV-Hop算法,定位精度有較大的提高。但該算法僅限于樓層明確的樓宇中。

文獻[7]基于Euclidean定位算法,將信標節(jié)點與未知節(jié)點之間的距離抽象為六面體定點之間的距離,并利用坐標法進行求解。

文獻[8]提出一種基于球面坐標的動態(tài)定位機制,將定位問題抽象為多元線性方程組求解問題,最終利用克萊姆法則獲得未知節(jié)點的坐標。同時引入最小二乘法減小節(jié)點移動以及廣播周期等過程中的誤差。由于計算開銷較大,節(jié)點無法長時間保持工作狀態(tài)。

綜上所述,目前無線傳感器網絡節(jié)點的三維定位算法還難以高效的實現(xiàn)較高精度的定位,這主要是由節(jié)點間距離和坐標轉換精度不高引起的。針對距離重構的多維定位算法[9]在三維定位中坐標轉換精度存在的問題,本文在距離重構的基礎上,通過MDS-MAP算法得到節(jié)點間的相對坐標位置,同時采用更加精確的坐標轉換方法來優(yōu)化原有算法中的坐標變換過程,實現(xiàn)較高精度的三維坐標轉換。仿真實驗表明,改進算法在三維定位精度上有較大的提高。

2 算法描述及其改進

基于距離重構的多維定標算法利用節(jié)點之間的距離信息,進行距離重構,得到較精確地距離矩陣,然后使用MDS-MAP算法進行相對坐標計算,得到各節(jié)點之間的相對位置,最后使用最小均方根偏差幾何中心算法得到三維空間中的絕對坐標。

2.1 線性距離重構及坐標計算

假設傳感器網絡中有5個節(jié)點,分別為1,2,3,i,j,其中除節(jié)點i,j之間的距離dij未知外,其他任意兩個節(jié)點之間的距離均已知,這5個節(jié)點構成的平方距離矩陣為:

(1)

在獲得節(jié)點對的距離信息后,通過距離重構的方法可以得到其他未知節(jié)點之間較精確的距離信息,未能成功重構的距離項仍采用最短路徑替代。然后采用MDS-MAP算法進行坐標計算就可以得到網絡中節(jié)點的位置坐標。根據各個節(jié)點之間的坐標構成一組相對坐標矩陣XR。

2.2 MDS-MAP算法三維坐標轉換方法

通過計算得到節(jié)點的相對坐標以及錨節(jié)點的絕對坐標,經過平移、翻轉和旋轉等一系列的線性變換,將相對坐標轉換到錨節(jié)點所在的坐標系中。

(2)

(3)

(4)

(5)

這樣,在已知4個錨節(jié)點及其對應的相對坐標的情況下,可得

(6)

保留式(6)中非零項,得

(7)

即可求得轉換矩陣中的對應各項得值。將除去錨節(jié)點外的其余m-4個傳感器節(jié)點用相同的方法進行轉換,有

(8)

這樣,便得到所有節(jié)點的絕對坐標。

2.3 改進的坐標轉換方法

采用MDS-MAP算法將相對坐標向絕對坐標的轉換過程,其轉換矩陣僅由4個錨節(jié)點進行確定,并不能較精確地實現(xiàn)相對坐標到絕對坐標之間的轉換,增大了節(jié)點絕對位置的定位的誤差。本文提出了RMSD-GCC算法,來實現(xiàn)較高精度的三維定位。

設錨節(jié)點坐標矩陣為Y,其對應的相對坐標矩陣為X,則定義:

(9)

其中,Q是旋轉矩陣,QQT=I。當RMSD(X,Y)的值取到最小值,轉換矩陣的轉換精度最優(yōu)。

令C=XTY,對C進行奇異值分解有

C=U∑VT

(10)

Q=UVT

(11)

不難驗證Q=UVT為上述最小值問題的最優(yōu)解[12]。

XA=XRQ

(12)

XA即為相對坐標旋轉后得到的估計坐標位置。此時,分別計算錨節(jié)點的實際位置矩陣Y的幾何中心以及經過旋轉矩陣得到的估計位置矩陣X′的幾何中心:

(13)

(14)

這樣,錨節(jié)點的真實坐標和估計坐標就有相同的幾何中心[13]。

2.4 算法實現(xiàn)過程

算法的實現(xiàn)過程可分為相對坐標計算過程和坐標轉換過程。相對坐標計算過程中,距離矩陣經過距離重構并使用MDS-MAP算法計算出節(jié)點相對坐標位置。坐標轉換過程中,相對坐標矩陣利用最小均方偏差和幾何中心修正得到節(jié)點絕對坐標。

算法的偽代碼實現(xiàn)如下:

1.Begin

2.Setdijbe the distance of nodei,j.

4.Search the numberkof unknown terms included inDN.

5.IFdijis unknown,

Select three public nodes ofi,j,using the formula(1)to calculatedij.

k=k-1

ENDIF

6.IFk>0,

goto 3.

ENDIF

7.XRis calculated as MDS-MAP algorithm.

8.SetY,X,X′ separately be the anchor node coordinate matrix,corresponding relative coordinate matrix and converted relative coordinate matrix.

9.Qis calculated as Equation(9),(10),(11).

10.XAis calculated as Equation(12).

11.Setyc,xcseparately be the geometric center of the anchor nodes and converted relative coordinate matrix.

13.End

3 算法仿真分析及相關定義

3.1 相關定義

定義1設在三維空間中采用的定位誤差計算為:

(15)

定義2設N為空間內部署節(jié)點數(shù)目,err為平均定位誤差,則

(16)

圖1 節(jié)點定位效果圖

3.2 算法仿真測試

本文主要通過改變節(jié)點的數(shù)量、測距半徑、測距誤差以及錨節(jié)點密度這4個參數(shù),觀察分析它們在仿真中分別對定位精度的影響,使得在硬件平臺上使用時避免系統(tǒng)誤差的產生。

為了驗證算法的性能,本文使用MATLAB軟件對該算法進行仿真實驗。為了與現(xiàn)實空間大小相似,三維仿真環(huán)境設置為長寬均為30 m,高為10 m的立方體空間,在該區(qū)域內隨機部署40個節(jié)點,每個節(jié)點的測距半徑為15 m。實驗中將已知節(jié)點均勻分布在網絡區(qū)域內,并保證其分布的隨機性。定位效果如圖1所示。圖中紅色圓圈表示隨機產生的節(jié)點的真實坐標,藍色“×”號表示定位算法計算得到的坐標。從圖中可以看出該定位算法計算得到的節(jié)點坐標與節(jié)點真實坐標基本重合,定位誤差較小。

3.3 算法性能分析

3.3.1 測距半徑和節(jié)點數(shù)量對定位精度的影響

設置測距半徑分別為15 m、20 m、25 m、30 m和35 m,節(jié)點數(shù)量分別為30個、40個、50個、60個,通過改變測距半徑,觀察不同節(jié)點數(shù)量對應的節(jié)點定位誤差。

從圖2中可以看出隨著測距半徑的增加,定位誤差逐步減小。當測距半徑為25m時,節(jié)點之間的定位誤差縮小至0.3 m以下。當測距半徑超過30 m時,測距誤差幾乎為0。這是由于測距半徑增大時,測距誤差減小,定位精度提高。在測距半徑相同的情況下,節(jié)點數(shù)量越多,定位誤差越小。這是因為在替代不可測的距離在距離重構時,有更多可以選擇的路徑進行替代,更容易得到精確地距離,從而降低定位誤差。

圖2 測距半徑和節(jié)點數(shù)量對定位誤差的影響

圖3 錨節(jié)點密度對定位誤差的影響

3.3.2 錨節(jié)點密度對定位精度的影響

設置總節(jié)點數(shù)量為40個,通過增加錨節(jié)點的密度,觀察節(jié)點在測距半徑分別為15 m、20 m、25 m、30 m時的定位精度,得到的圖形數(shù)據如圖3所示。在測距半徑較小的情況下,節(jié)點的定位誤差受錨節(jié)點密度變化影響較大,錨節(jié)點數(shù)量越多,定位誤差越小;在測距半徑較大的情況下,錨節(jié)點密度對定位誤差的影響變小。這主要是因為測距半徑較小時,節(jié)點間的測距值誤差較大,導致定位后節(jié)點的幾何中心和真實節(jié)點的幾何中心之間的偏差比較大,增加錨節(jié)點的數(shù)量可以更好的修正節(jié)點的幾何中心;在測距半徑較大時,各節(jié)點之間的距離值更加準確,定位幾何中心與真實幾何中心偏差縮小,增加錨節(jié)點的數(shù)量對幾何中心修正效果不明顯。

3.3.3 DR-MDS算法與改進算法的平均定位誤差的比較

設置節(jié)點的數(shù)目為40個,節(jié)點的測距半徑為15 m,控制節(jié)點的原始位置不變,只對誤差參數(shù)進行改變。乘性正態(tài)誤差服從均值為0,方差為er2;均勻誤差服從[-er2,er2]的均勻分布。經過100次實驗后,取平均值作為仿真的結果。

圖4(a)反映的是原算法與改進算法的節(jié)點在測量本節(jié)點與鄰居節(jié)點之間的距離時,是否引入誤差,引入哪種類型的誤差對定位精度的影響的比較。其中,er2在乘性正態(tài)誤差中表示方差值,在乘性均勻誤差中表示最大偏差距離值。從圖中可以看出,在3種情況下,隨著誤差參數(shù)的增加,兩種算法的定位誤差都逐步增加,由于正態(tài)誤差的隨機性,引入的誤差更大。這表明節(jié)點間的測距精度對算法有一定的影響,當測距精度越高,定位誤差越小。同時,在引入同類型誤差的情況下,改進算法比原算法有更高的定位精度。

圖4 改進算法與DR-MDS算法的比較

在不引入測量距離誤差,錨節(jié)點和總節(jié)點的個數(shù)分別為4個和40個的情況下,原算法和改進算法都有較好的定位性能,對兩種算法進行定位算法性能的比較。

從圖4(b)中可以看出,節(jié)點的測距半徑從15 m到35 m,隨著節(jié)點測距半徑的增加,兩種算法的定位誤差也逐步減小。在測距半徑分別為15 m、20 m、25 m、30 m和35 m時,定位精度分別提高了14%、19.6%、28%、78%和87%。這主要是由于測距半徑增加,節(jié)點之間的距離值更加準確,定位精度整體得到提高。同時,改進算法對幾何中心進行修正,使得其平均定位誤差更小。從數(shù)據中可以出,改進算法的定位精度至少提高了14%,定位誤差縮小至0.7 m以內。

4 結束語

本文分析了多維空間定位中的距離重構算法,在距離重構和MDS-MAP算法的基礎上,通過最小均方根偏差幾何中心修正算法進行節(jié)點定位及其幾何中心修正,對節(jié)點實現(xiàn)三維空間上坐標的較高精度轉換。仿真結果表明,在不考慮測距誤差的情況下,該改進算法在節(jié)點隨機分布、測距半徑較小時,定位精度可以提高14%,定位誤差縮小至0.63 m,在測距半徑較大時,定位精度可以提高87%,定位誤差幾乎為0,可以實現(xiàn)較高精度的三維空間定位。下一步我們希望使用該算法在硬件節(jié)點上進行實際測試,進一步驗證算法的有效性和可靠性。

[1] 向滿天,羅嗣力,戴美思. 無線傳感器網絡中一種改進的凸規(guī)劃定位算法[J]. 傳感技術學報,2014(8):1138-1142.

[2]劉健,沈海斌. 無線傳感器網絡的三維定位算法研究[J]. 傳感器與微系統(tǒng),2013(9):66-68,71.

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

[4]Gang H,Xinjiang X,Yehua W. A Three-Dimensional Positioning Algorithm for Wireless Sensor Networks Based on the Ball Field Intersection[C]//Electronics,Communications and Control(ICECC),2011 International Conference on. IEEE,2011:101-104.

[5]李彬,王文杰,殷勤業(yè),等. 一種利用天線旋轉的無線傳感器網絡定位算法[J]. 西安交通大學學報,2011(4):60-66.

[6]毛科技,戴光麟,夏明,等. 采用分層結構的WSN室內三位定位算法的研究和設計[J]. 小型微型計算機系統(tǒng),2013,34(2):277-280.

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

[8]戴桂蘭,趙沖沖,邱巖. 一種基于球面坐標的無線傳感器網絡三維定位機制[J]. 電子學報,2008,36(7):1297-1303.

[9]黃亮,王福豹,段渭軍,等. 基于距離重構的無線傳感器網絡多維定標定位算法[J]. 傳感技術學報,2013,26(9):1284-1287.

[10]Regalia P A,Wang J. On Distance Reconstruction for Sensor Network Localization[C]//Acoustics Speech and Signal Processing(ICASSP),2010 IEEE International Conference on. IEEE,2010:2866-2869.

[11]Arfken G,Weber H J. Mathematical Methods for Physicists Academic[J]. New York,1985,19852:309.

[12]Golub G H,Van Loan C F. Matrix Computations[M]. Johns Hopkins University Press,1989.

[13]Wu D,Wu Z. An Updated Geometric Build-up Algorithm for Solving the Molecular Distance Geometry Problems with Sparse Distance Data[J]. Journal of Global Optimization,2007,37(4):661-673.

張亞杰(1990-),男,山西運城人,碩士研究生,主要研究方向為無線通信及分布式組網通信技術,1040464779@qq.com;

段渭軍(1962-),男,陜西渭南人,研究員,碩士生導師,主要研究方向為無線傳感器、網絡信號處理,duanwj@nwpu.edu.cn;

王福豹(1963-),男,山西運城人,教授,博士生導師,主要研究方向為計算機網絡、無線通信網絡,wangfubao@nwpu.edu.cn。

AnImprovedDistanceReconstructingThree-DimensionalLocalizationAlgorithm*

ZHANGYajie1,2,DUANWeijun1,2*,WANGFubao1,2,GAOAng1,2

(1.School of Electronics and Information,Northwestern Polytechnical University,Xi’an 710072,China;2.State and Local Joint Engineering Laboratory of IoT Technology and Application,Xi’an 710072,China)

In order to solve the problem of localization algorithm that node transformation accuracy from relative coordinate to absolute coordinate is low in three-dimensional,we proposed a improved distance reconstruct three-dimensional localization algorithm based on the distance reconstruct multi-dimensional localization algorithm. The algorithm based on the distance reconstruct and MDS-MAP algorithm adopted optimized Root Mean Square Deviation-Geometric Center Correction(RMSD-GCC)algorithm,first calculate the coordinate transformation matrix,then use the geometric center of the anchor node correct all nodes position,and realized node transformation from relative coordinate to absolute coordinate. The proposed algorithm can effectively transform coordinate,and get better location performance. Compared with old algorithm,the result shows that positioning accuracy in advanced algorithm increased by 14% and location error reduced to 0.8 m in distance radius equal to 15 m,positioning accuracy increased by 87% and location error almost reduced to 0 in distance radius equal to 35m under the condition of not introduce ranging error. The improved algorithm in three-dimension space has higher node localization accuracy.

wireless sensor networks(WSNs);three-dimensional localization;coordinate transformation;geometric center correction

項目來源:中央高?；究蒲袠I(yè)務費專項資金項目(3102014KYJD033;3102014KYJD034)

2014-08-26修改日期:2014-10-19

TP393

:A

:1004-1699(2014)12-1681-06

10.3969/j.issn.1004-1699.2014.12.018