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

胡中棟,謝金偉

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

?

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

胡中棟*,謝金偉

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

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

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

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

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

1 三維DV-Hop算法

1.1 DV-Hop算法

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

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

AX=B

(1)

其中:

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

X=(ATA)-1ATB

(2)

1.2 性能評(píng)價(jià)

一般用相對(duì)定位誤差來(lái)評(píng)價(jià)算法的性能[12]。

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

(3)

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

(4)

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

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

(5)

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

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

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

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

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

(6)

(7)

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

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

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

沿y,z坐標(biāo)軸線的投影結(jié)果與情況1相同。

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

沿x,z坐標(biāo)軸線的投影結(jié)果與情況1相同。

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

沿z坐標(biāo)軸線的投影結(jié)果與情況1相同。

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

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′點(diǎn)即為近似投影修正后的定位結(jié)果。

3 仿真實(shí)驗(yàn)

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

3.1 不同山頭高度的實(shí)驗(yàn)

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

圖2 傳感器節(jié)點(diǎn)隨機(jī)分布圖

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

3.2 不同錨點(diǎn)比例實(shí)驗(yàn)

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

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

3.3 傳感器節(jié)點(diǎn)數(shù)不同的實(shí)驗(yàn)

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

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

4 總結(jié)

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

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

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

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

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

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

[9]江禹生,馮硯毫,管芳,等. 無(wú)線傳感網(wǎng)非測(cè)距三維節(jié)點(diǎn)定位算法[J]. 西安電子科技大學(xué)學(xué)報(bào)(自然科學(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]嚴(yán)筱永,錢煥延,高德民,等. 一種基于多重共線性的三維DV-Hop定位算法[J]. 計(jì)算機(jī)科學(xué),2011,38(5):37-40,44.

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

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

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

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

項(xiàng)目來(lái)源:江西省教育廳項(xiàng)目(GJJ10492);國(guó)家基金項(xiàng)目(61462034);江西省教育廳自然科學(xué)基金項(xiàng)目(GJJ13413)

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

10.3969/j.issn.1004-1699.2014.11.024

TP393

:A

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