基于近似投影校正的無線傳感器網絡三維定位機制*

胡中棟,謝金偉

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

?

基于近似投影校正的無線傳感器網絡三維定位機制*

胡中棟*,謝金偉

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

針對三維DV-Hop無線傳感器定位算法存在定位誤差較大的問題,提出了近似投影校正的無線傳感器網絡非測距三維定位算法。充分利用已有的地形特點,將經典的三維DV-Hop算法所求得的結果進行近似投影,盡可能投影到離地形表明較近的地方,大幅度減小了定位誤差。用二維高斯分布密度函數模擬山頭地形的場景中,相對定位誤差為35%左右,較大幅度提高了定位精度,有較高的實用價值。

無線傳感器網絡;三維DV-Hop;山頭地形;近似投影

隨著萬物互聯的理念不斷深入人心,采集信息就成了許多領域的重要工作。而就目前而言,帶有GPS功能的無線傳感器因其價格太高無法大范圍部署,因此無線傳感器網絡中大部分傳感器節點都不具有定位功能。無法定位的傳感器很多情況下不能承擔采集需求信息的任務,所采集的信息不具有實際意義[1],因此定位就成了無線傳感器網絡領域的研究熱點,且定位信息對路由也起著重要的作用[2]。有許多不同的定位算法,APIT(Approximate Point In Triangle)[3]算法是一種不基于其它測量設備的自定位算法,文獻[4]將其應用擴展到了三維;陳歲生[5]等人利用MDS-MAP和非線性濾波的方法設計了WSN定位算法;黃亮[6]等人根據距離重構原理提高了定位精度;程秀芝[7]等人利用RSSI對傳統定位方法進行校正;張亞明[8]等人對不對稱鏈路環境下WSN定位算法進行了研究;江禹生[9]等通過加權質心算法對未知節點進行定位。

基于近似投影校正的無線傳感器網絡三維定位:因山頭不能抽象成具體的函數模型,很難直接進行投影,本文提出了近似投影校正的方法。在三維DV-Hop定位算法求解結果的基礎上進行近似投影修正以提高定位精度。假設三維DV-Hop求解的結果為P,首先將P點沿x,y,z坐標軸投影到山頭地形表面,得到三個新的點P1,P2,P3。求出過P1,P2,P3三個點的平面,將P點投影到該平面上,得到投影點P′,用P′代替P。該方法能夠修正未知節點的位置,較大幅度的提高傳感器節點的定位精度。

1 三維DV-Hop算法

1.1 DV-Hop算法

Niculescu D等人利用距離矢量路由的原理提出DV-Hop算法[10]。本文暫未考慮無法求解的孤立點等特殊情況。通過廣播在所有節點間進行信息交換,得到每一個節點到其它節點的最小跳數信息。每一個錨節點都根據自身的位置及與其它所有錨節點之間的最小跳數計算出平均每跳距離。根據未知節點i到錨節點j的最小跳數,再用到未知節點i最近錨節點的平均跳距估算出未知節點i到錨節點j的距離。

根據以上信息通過最小二乘法(極大似然估計法)計算自身坐標[11]。若未知節點的坐標為(x,y,z),已求出該未知節點到錨節點(x1,y1,z1),(x2,y2,z2),…,(xn,yn,zn)的距離分別為d1,d2,…dn(n≥4)?？傻妹芊匠探M:

AX=B

(1)

其中:

若矛盾方程組有解則可得:

X=(ATA)-1ATB

(2)

1.2 性能評價

一般用相對定位誤差來評價算法的性能[12]。

若某個未知節點的估算坐標(xi,yi,zi)和實際坐標(ai,bi,ci)的差距Δdi為:

(3)

則n個未知節點的平均定位誤差Δ可表示為:

(4)

2 近似投影校正的三維定位算法

用二維高斯分布的密度函數來模擬山頭地形比規則函數更具有一般性,能夠較好的證明算法的優越性。設二維高斯分布的密度函數為:

(5)

作過點(0,0,L)且平行于xoy的平面,其中0

近似投影校正的具體方法如圖1所示,設三維DV-Hop求解的結果為P,首先將P點沿x坐標向山頭表面投影得到P1點,然后將P沿y坐標軸進行投影得到P2點,最后將P沿z坐標軸進行投影得到P3點。過P1,P2,P3三個點作平面,然后將P點垂直投影到該平面上,投影點為P′,P′即為P修正后的解。在上述投影過程中,有可能存在偏離山頭無法投影的特殊點,下文將進行具體說明。

設經典三維DV-Hop算法所求得的解P對應的坐標為(a,b,c),沿x,y,z坐標軸投影得到的三個點為P1,P2,P3,對應的坐標為(x1,y1,z1),(x2,y2,z2),(x3,y3,z3)。

首先消除過高和過低點,在式(5)模擬的山頭中不可能有比山高的點,也不可能有比山低的點,但是經典三維DV-Hop算法可能求出越界的點。假設P(a,b,c)點的c大于上界H,則將P更新為(a,b,H-0.001),若c小于下限L,則將P更新為(a,b,L+0.001),因在山頂和山底無法投影,所以需要小幅修正。

將式(5)解出x,y可得:

(6)

(7)

根據式(5)～式(7)可求得P點沿x,y,z坐標軸線投影所得的點,即過P點且與坐標軸平行的直線與山體表面的交點。正常情況下可得兩個交點,取與P點坐標分量值符號相同的交點,如P點坐標(a,b,c)中若a>0則取兩個交點中x坐標值為正的交點,否則取x坐標值為負的交點。也可能發生無法投影的情況,具體過程如下:

情況1:若-ln(c/H)-(b/5)2≥0與-ln(c/H)-(a/5)2≥0均成立,則說明P沿x,y坐標軸線可以投影,投影后得到的投影點P1,P2,P3為:

情況2:若-ln(c/H)-(b/5)2<0與-ln(c/H)-(a/5)2≥0均成立,則表明沿x坐標軸線無法投影,一般為x值接近0的情況。將沿x坐標軸線的投影修正為先將P點改為(0,b,c),然后再沿y坐標軸線投影,投影后得到的投影點P1為:

沿y,z坐標軸線的投影結果與情況1相同。

情況3:若-ln(c/H)-(b/5)2≥0與-ln(c/H)-(a/5)2<0均成立,則表明沿y坐標軸線無法投影,一般為y值接近0的情況。將沿y坐標軸線的投影修正為先將P點改為(a,0,c),然后再沿x坐標軸線投影,投影后得到的投影點P2為:

沿x,z坐標軸線的投影結果與情況1相同。

情況4:若-ln(c/H)-(b/5)2<0與-ln(c/H)-(a/5)2<0均成立,則表明沿x,y坐標軸線均無法投影,分別進行情況2和情況3的操作得到P1,P2,當求P1時P更新為(0,b,c),當求P2時P更新為(a,0,c):

沿z坐標軸線的投影結果與情況1相同。

因進行了修正,P1,P2,P3必定不在一條直線上,可求得過P1,P2,P3三點的平面為:

Ax+By+Cz+D=0

(8)

其中:

A=y1z2-y1z3-y2z1+y2z3+y3z1-y3z2
B=-x1z2+x1z3+x2z1-x2z3-x3z1+x3z2
C=x1y2-x1y3-x2y1+x2y3+x3y1-x3y2
D=-x1y2z3+x1y3z2+x2y1z3-x2y3z1-x3y1z2+x3y2z1

P′點即為近似投影修正后的定位結果。

3 仿真實驗

采用Matlab對本文設計的近似投影校正算法進行了仿真實驗,實驗用三種方法進行了對比實驗,分別為經典的三維DV-Hop定位算法、基于平均跳距修正的三維DV-Hop定位算法和本文提出的近似投影校正算法。用式(5)模擬山頭,以10 m為一個單位,其中L=H·e-1,實驗分為山頭高度不同、信標節點比例不同與節點總數不同3種情況進行。實驗中節點的通信半徑設置為20 m,其它參數根據不同的情況進行設置,節點隨機分布的一個實例如圖2所示。

3.1 不同山頭高度的實驗

實驗中傳感器節點總數設為200,信標節點占10%。式(5)中的H分別設為8、9、10、11、12、13、14進行實驗,對每個不同的H值均進行100次實驗,每次實驗的傳感器節點都是隨機分布的,相對定位誤差取100次實驗結果的平均值,實驗結果如圖3所示,雖然隨著山的高度不斷增加,兩種算法相對定位誤差都在增加,但經近似投影的節點定位精度明顯高于經典的三維DV-Hop定位算法與基于平均跳距修正的三維DV-Hop定位算法。

圖2 傳感器節點隨機分布圖

圖3 不同山頭高度的平均定位誤差

3.2 不同錨點比例實驗

實驗中H的值設定為10,傳感器節點總數設為200,信標節點的比例取5%、10%、15%、20%、25%、30%和35%進行實驗,對每種不同比例分別進行100次模擬實驗,每次實驗的傳感器節點分布都是隨機的,相對定位誤差取100次實驗結果的平均值,實驗結果如圖4所示,當錨點比例超過20%時,在復雜的模擬環境下,近似投影算法的相對定位誤差已經降低到40%以下,大幅度提高了算法的可用性。

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

3.3 傳感器節點數不同的實驗

實驗中H的值設定為10,錨節點比例固定為10%,實驗中節點總數分別為140、150、160、170、180、190和200的情況下進行,對每組數據進行100次實驗,每次實驗時傳感器節點分布都是隨機的,相對定位誤差取100次實驗結果的平均值,實驗結果如圖5所示,結果顯示如果合理部署傳感器節點,基于近似投影的非測距三維定位算法的相對定位誤差低于40%,較原有算法定位精度有較大幅度的提高。

圖5 不同節點總數的平均定位誤差

4 總結

本文設計的基于近似投影的無線傳感器網絡三維定位算法有效的利用了外部環境的特點,用近似投影的方法有效的克服了不規則圖形無法直接投影的缺陷。通過多角度的仿真對比實驗證明,本文設計的算法在近似真實山頭模型中表現良好,有效提高了無線傳感器網絡非測距定位算法精度,具有較高的實用價值。

[1] 謝亞琴,張業榮. 基于APIT和TSE算法的混合定位方法[J]. 南京郵電大學學報(自然科學版),2007,27(6):68-71.

[2]Rao A,Ratnasamy S,Papadimitriou C,et al. Geographic Rollting without Location Information[C]//MobiCom. San Diego:ACM Press,2003:96-108.

[3]He Tian,Huang Chengdu,Blum B M,et al. Range-Free Localization Schemes for Large Scale Sensor Networks[C]//MobiCom. San Diego:ACM Press,2003:81-95.

[4]劉玉恒,蒲菊華,赫陽. 無線傳感器網絡三維自身定位方法[J]. 北京航天航空大學學報,2008,34(6):647-651.

[5]陳歲生,盧建剛,樓曉春. 基于MDS-MAP和非線性濾波的WSN定位算法[J]. 浙江大學學報(工學版),2012,46(5):866-872.

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

[7]程秀芝,朱達榮,張申,等. 基于RSSI差分校正的最小二乘—擬牛頓定位算法[J]. 傳感技術學報,2014(1):123-127.

[8]張亞明,史浩山,劉燕,等. 不對稱鏈路環境下的WSN節點定位算法[J]. 傳感技術學報,2014,27(3):320-326.

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

[10]Niculescu D,Nath B. DV-Based Positioning in Ad Hoc Networks[J]. Journal of Teleconununication Systems,2003,22(1-4):267-280.

[11]嚴筱永,錢煥延,高德民,等. 一種基于多重共線性的三維DV-Hop定位算法[J]. 計算機科學,2011,38(5):37-40,44.

[12]胡中棟,曾珽,肖紅,等. 基于地形改正的無線傳感器網絡DV-Hop定位算法[J]. 傳感器與微系統,2013,32(6):147-149.

胡中棟(1958-),男,漢族,江西婺源人,江西理工大學教授,碩士研究生導師,主要研究方向為無線傳感器網絡,智能計算,jxhzd@163.com;

謝金偉(1987-),男,漢族,江蘇淮安人,江西理工大學碩士研究生,主要研究方向為無線傳感器網絡,智能計算。

The3DLocalizationMechanismforWirelessSensorNetworksBasedonApproximateProjectionCorrection*

HUZhongdong*,XIEJinwei

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

This paper presents a non-dimensional distance wireless sensor network localization algorithm based on approximate projection correction for the problem that the localization error is large. The results which get by using the least squares method is approximate projected as close as possible to the surface of the mountain which full use of existing terrain features,greatly reducing the location error. In the two-dimensional Gaussian distribution density function simulation scenarios,the relative localization error is about 35%,dramatically increased the accuracy of location and it have high practical value.

WSN;3D DV-Hop;mountain terrain;approximate projection

項目來源:江西省教育廳項目(GJJ10492);國家基金項目(61462034);江西省教育廳自然科學基金項目(GJJ13413)

2014-07-01修改日期:2014-09-16

10.3969/j.issn.1004-1699.2014.11.024

TP393

:A

:1004-1699(2014)11-1573-05