胡中棟,謝金偉

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

?

基于近似投影校正的無線傳感器網(wǎng)絡(luò)三維定位機制*

胡中棟*,謝金偉

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

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

無線傳感器網(wǎng)絡(luò);三維DV-Hop;山頭地形;近似投影

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

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

1 三維DV-Hop算法

1.1 DV-Hop算法

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

根據(jù)以上信息通過最小二乘法(極大似然估計法)計算自身坐標[11]。若未知節(jié)點的坐標為(x,y,z),已求出該未知節(jié)點到錨節(jié)點(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]。

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

(3)

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

(4)

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

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

(5)

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

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

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

首先消除過高和過低點,在式(5)模擬的山頭中不可能有比山高的點,也不可能有比山低的點,但是經(jīng)典三維DV-Hop算法可能求出越界的點。假設(shè)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)

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

情況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坐標軸線的投影結(jié)果與情況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坐標軸線的投影結(jié)果與情況1相同。

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

沿z坐標軸線的投影結(jié)果與情況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′點即為近似投影修正后的定位結(jié)果。

3 仿真實驗

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

3.1 不同山頭高度的實驗

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

圖2 傳感器節(jié)點隨機分布圖

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

3.2 不同錨點比例實驗

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

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

3.3 傳感器節(jié)點數(shù)不同的實驗

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

圖5 不同節(jié)點總數(shù)的平均定位誤差

4 總結(jié)

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

[1] 謝亞琴,張業(yè)榮. 基于APIT和TSE算法的混合定位方法[J]. 南京郵電大學(xué)學(xué)報(自然科學(xué)版),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]劉玉恒,蒲菊華,赫陽. 無線傳感器網(wǎng)絡(luò)三維自身定位方法[J]. 北京航天航空大學(xué)學(xué)報,2008,34(6):647-651.

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

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

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

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

[9]江禹生,馮硯毫,管芳,等. 無線傳感網(wǎng)非測距三維節(jié)點定位算法[J]. 西安電子科技大學(xué)學(xué)報(自然科學(xué)版),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]. 計算機科學(xué),2011,38(5):37-40,44.

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

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

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

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);江西省教育廳自然科學(xué)基金項目(GJJ13413)

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

10.3969/j.issn.1004-1699.2014.11.024

TP393

:A

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