基于山區(qū)地形的無(wú)線傳感器網(wǎng)絡(luò)三維定位機(jī)制*

胡中棟,謝金偉

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

?

基于山區(qū)地形的無(wú)線傳感器網(wǎng)絡(luò)三維定位機(jī)制*

胡中棟*,謝金偉

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

針對(duì)三維DV-hop無(wú)線傳感器定位算法在實(shí)際地形中定位時(shí)誤差較大的問(wèn)題,提出了根據(jù)山區(qū)地形的網(wǎng)格數(shù)據(jù)進(jìn)行較近點(diǎn)投影校正的無(wú)線傳感器網(wǎng)絡(luò)非測(cè)距三維定位算法。經(jīng)典的三維DV-hop算法求出未知節(jié)點(diǎn)位置后,在該節(jié)點(diǎn)附近搜索3個(gè)離該節(jié)點(diǎn)較近且非共線的山區(qū)地形網(wǎng)格上的點(diǎn),將該節(jié)點(diǎn)向上述3個(gè)點(diǎn)確定的面進(jìn)行投影,投影點(diǎn)即為校正后的未知節(jié)點(diǎn)位置。山區(qū)地形多場(chǎng)景實(shí)驗(yàn)表明,該方法較大幅度減小了定位誤差。

無(wú)線傳感器網(wǎng)絡(luò);三維DV-hop;適應(yīng)地形;較近點(diǎn)投影

因人們對(duì)數(shù)據(jù)采集的需求越來(lái)越大,無(wú)線傳感器在當(dāng)今世界扮演著越來(lái)越重要的作用,無(wú)線傳感器網(wǎng)絡(luò)也被評(píng)為了21世紀(jì)最有影響力的21項(xiàng)技術(shù)和改變世界的10大技術(shù)[1]。大部分的無(wú)線傳感器不能確定自己的位置[2],所以無(wú)線傳感器必須先為自己定位,無(wú)線傳感器定位是指?jìng)鞲衅魍ㄟ^(guò)輔助條件來(lái)確定自己的位置,輔助條件如GPS或其他已知自己位置的傳感器節(jié)點(diǎn)[3]。目前已經(jīng)有許多學(xué)者提出了無(wú)線傳感器定位算法,如SpotON[4]、APS[5]、MDS-MAP[6]和Constrained 3-D[7]等。程秀芝等人[8]使用了RSSI差分校正的方法提高了最小二乘-擬牛頓定位算法的定位精度;喬欣等人[9]使用了跳距修正的方法提高了WSN擬牛頓迭代定位算法的精度;陳嘉興等人[10]采用了三維序列內(nèi)心來(lái)確定傳感器的位置,較有效的提高了定位精度。以目前的條件來(lái)看,非測(cè)距的定位方法所能提供的條件有限,定位精度已經(jīng)達(dá)到了一個(gè)瓶頸,只有充分利用外在條件,才有可能較大幅度的提高算法的定位精度。本文結(jié)合實(shí)際地形的網(wǎng)格數(shù)據(jù)提出了基于較近點(diǎn)投影校正的無(wú)線傳感器網(wǎng)絡(luò)三維定位算法,有效的利用了地形信息,提高了定位精度。

基于山區(qū)地形的無(wú)線傳感器網(wǎng)絡(luò)三維定位方法:根據(jù)實(shí)際山區(qū)地形的網(wǎng)格數(shù)據(jù),應(yīng)用較近點(diǎn)投影的方法來(lái)修正經(jīng)典DV-hop算法的定位精度。在三維DV-hop定位算法求解結(jié)果的基礎(chǔ)上進(jìn)行較近點(diǎn)投影修正來(lái)減小定位誤差。若P點(diǎn)為三維DV-hop的定位結(jié)果,根據(jù)網(wǎng)格的疏密度確定一個(gè)以P點(diǎn)為中心的局部搜索區(qū)域,在該區(qū)域內(nèi)尋找離P點(diǎn)最近且不共線的3個(gè)網(wǎng)格上的點(diǎn)P1、P2、P3,由這3個(gè)點(diǎn)確定一個(gè)平面M,將P點(diǎn)垂直投影到平面M上,得到投影點(diǎn)P′,P′就是P點(diǎn)經(jīng)過(guò)最近點(diǎn)投影修正后的位置。由于傳感器是部署在地形表面上的,如果經(jīng)典三維DV-hop算法所定位出P′點(diǎn)不在地形表面,則一定是偏離了實(shí)際位置。經(jīng)過(guò)本算法的投影,無(wú)線傳感器的位置最大程度的接近了地形表面,能夠較大幅度的提高傳感器的定位精度。

1 三維DV-hop算法

1.1 DV-hop算法

Niculescu D[11]等人提出了DV-hop算法,該算法是通過(guò)距離矢量路由原理來(lái)實(shí)現(xiàn)的[7]。無(wú)線傳感器網(wǎng)絡(luò)中的所有節(jié)點(diǎn)泛洪交換信息,每一個(gè)節(jié)點(diǎn)計(jì)算出到其他所有節(jié)點(diǎn)的最小跳數(shù)。所有錨節(jié)點(diǎn)通過(guò)GPS確定自身的位置,錨節(jié)點(diǎn)根據(jù)到其他錨節(jié)點(diǎn)的最小跳數(shù)計(jì)算出自身平均每跳距離。未知節(jié)點(diǎn)根據(jù)到錨節(jié)點(diǎn)的最小跳數(shù)和最近錨節(jié)點(diǎn)的平均每跳距離得出到所有錨節(jié)點(diǎn)的距離。

最小二乘法(極大似然估計(jì)法)計(jì)算自身坐標(biāo)過(guò)程如下[12]:

若未知節(jié)點(diǎn)的坐標(biāo)為(x,y,z),已知未知節(jié)點(diǎn)到所有錨節(jié)點(diǎn)的距離為d1,d2,…dn(n≥4),其對(duì)應(yīng)的錨節(jié)點(diǎn)坐標(biāo)為(x1,y1,z1),(x2,y2,z2),…,(xn,yn,zn)。

可得矛盾方程組:

AX=B

(1)

式中:

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

X=(ATA)-1ATB

(2)

由式(2)求出的X=(x,y,z)T就是未知節(jié)點(diǎn)的估算坐標(biāo)。

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

相對(duì)定位誤差是用來(lái)評(píng)價(jià)算法性能的主要方法[13]:

未知節(jié)點(diǎn)的估算坐標(biāo)(xi,yi,zi)和實(shí)際坐標(biāo)(ai,bi,ci)的差距Δdi如式(3)所示。

(3)

無(wú)線傳感器網(wǎng)絡(luò)中的n個(gè)未知節(jié)點(diǎn)的平均定位誤差Δ可表示為:

(4)

式中R表示傳感器的通信半徑。

2 較近點(diǎn)投影校正的三維定位算法

較近點(diǎn)投影校正的過(guò)程如圖1所示,若經(jīng)典三維DV-hop定位某個(gè)未知點(diǎn)的位置為P。根據(jù)P點(diǎn)對(duì)應(yīng)的x和y坐標(biāo)確定一個(gè)搜索區(qū)域,在該區(qū)域中搜索離P點(diǎn)最近且不共線的3個(gè)點(diǎn)P1,P2,P3,從全局來(lái)看P1,P2,P3這3個(gè)點(diǎn)不一定是離P點(diǎn)是最近的,但這3個(gè)點(diǎn)所形成的面已經(jīng)能夠較好的逼近地形表面。因?yàn)镻1,P2,P33點(diǎn)不在一條直線上,故可以確定一個(gè)平面。過(guò)P點(diǎn)向該平面垂直投影,所得的投影點(diǎn)P′即為P點(diǎn)經(jīng)過(guò)較近點(diǎn)投影修正后的位置。

圖1 近似投影方法

設(shè)地形的網(wǎng)格數(shù)據(jù)在xoy面的投影是x,y以步長(zhǎng)為l所構(gòu)成的m×n個(gè)小正方形。經(jīng)典三維DV-hop算法定位某個(gè)位置節(jié)點(diǎn)的位置為P,其坐標(biāo)為(a,b,c),則可以確定局部搜索區(qū)域?yàn)?

(5)

若P點(diǎn)靠近地形網(wǎng)格數(shù)據(jù)的邊緣,則不能滿足式(5)所約束的正方形區(qū)域,此時(shí)可將搜索區(qū)域向邊界的反方向擴(kuò)展。例如,若a-5l已經(jīng)超出邊界范圍超過(guò)l,設(shè)邊界數(shù)值M,有M-l

(6)

P點(diǎn)處于其他邊界位置可仿照式(6)進(jìn)行處理,這樣可以保證搜索在5×5的網(wǎng)格區(qū)域內(nèi)進(jìn)行,保證投影的可靠性。

首先在區(qū)域內(nèi)尋找與P點(diǎn)距離最近的點(diǎn)P1,設(shè)其坐標(biāo)為(x1,y1,z1)。然后距離次近的點(diǎn)P2,設(shè)其坐標(biāo)為(x2,y2,z2)。最后尋找P1,P2點(diǎn)外距離最近的點(diǎn)P3,坐標(biāo)為(x3,y3,z3),若P1,P2,P33點(diǎn)不共線,則得到搜索結(jié)果,否則繼續(xù)搜索下一個(gè),直到搜索到不共線的3點(diǎn)P1、P2、P3。

因P1,P2,P33點(diǎn)不共線,可求得過(guò)P1,P2,P33點(diǎn)的平面為:

Ax+By+Cz+D=0

(7)

式中:

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)即為P經(jīng)過(guò)較近點(diǎn)投影校正后的定位結(jié)果。

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

用MATLAB對(duì)較近點(diǎn)投影校正算法進(jìn)行了模擬實(shí)驗(yàn),兩組實(shí)驗(yàn)中的計(jì)算公式和繪圖的數(shù)據(jù)都以10 m為一個(gè)單位。為了驗(yàn)證算法的有效性,選擇了兩個(gè)較典型的場(chǎng)景進(jìn)行模擬實(shí)驗(yàn),一個(gè)采用山頭地形的網(wǎng)格數(shù)據(jù)進(jìn)行實(shí)驗(yàn),另一個(gè)則采用有不同高度山頭、山溝和平地的復(fù)雜地形進(jìn)行實(shí)驗(yàn)。用3種無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法進(jìn)行了對(duì)比實(shí)驗(yàn),分別為經(jīng)典的三維DV-Hop定位算法、基于平均跳距修正的三維DV-Hop定位算法和本文提出的較近點(diǎn)投影校正算法。

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

3.1 山頭地形實(shí)驗(yàn)

對(duì)式z=10e-((x/5)2+(y/5)2)網(wǎng)格化模擬山頭地形,本實(shí)驗(yàn)僅在式中高度為[10e-1,10]的區(qū)域進(jìn)行布點(diǎn),模擬高度約為63.2 m的模擬山頭場(chǎng)景。實(shí)驗(yàn)中無(wú)線傳感器節(jié)點(diǎn)的通信半徑設(shè)為20 m,實(shí)驗(yàn)分為不同錨節(jié)點(diǎn)比例和不同節(jié)點(diǎn)總數(shù)進(jìn)行,隨機(jī)布點(diǎn)實(shí)例如圖2所示。

①山頭地形不同錨點(diǎn)比例實(shí)驗(yàn)

傳感器總節(jié)點(diǎn)數(shù)設(shè)置為200,錨節(jié)點(diǎn)的比例取5%、10%、15%、20%、25%、30%和35%進(jìn)行實(shí)驗(yàn),每組實(shí)驗(yàn)進(jìn)行100次,實(shí)驗(yàn)結(jié)果取平均值,每次實(shí)驗(yàn)均隨機(jī)布點(diǎn)。由圖3的實(shí)驗(yàn)結(jié)果可以看到,山頭地形中當(dāng)錨節(jié)點(diǎn)比例大于15%時(shí),定位誤差的變化幅度已經(jīng)較小了。

圖3 山頭地形不同錨節(jié)點(diǎn)比例的平均定位誤差

②山頭地形傳感器節(jié)點(diǎn)數(shù)不同的實(shí)驗(yàn)

錨節(jié)點(diǎn)比例固定為10%,實(shí)驗(yàn)在節(jié)點(diǎn)總數(shù)分別為170、180、190、200、210、220和230的情況下進(jìn)行,每組數(shù)據(jù)進(jìn)行100次實(shí)驗(yàn),結(jié)果取平均值,每次均隨機(jī)布點(diǎn)。通過(guò)圖4可以看到,隨著節(jié)點(diǎn)的增加,定位精度更高。

圖4 山頭地形不同節(jié)點(diǎn)總數(shù)的平均定位誤差

3.2 復(fù)雜地形實(shí)驗(yàn)

對(duì)式z=3(1-x/4)2e-(x/4)2-(y/4+1)2-10[x/10-(x/4)2-(y/4)5]e-(x/4)2-(y/4)2-(1/3)e-[(x/4)+1]2-(y/4)2網(wǎng)格化模擬復(fù)雜地形,在式中x,y范圍為24×24的區(qū)域內(nèi)進(jìn)行實(shí)驗(yàn),即在240 m×240 m的復(fù)雜地形中進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)中無(wú)線傳感器節(jié)點(diǎn)的通信半徑設(shè)為40 m,實(shí)驗(yàn)分為不同錨節(jié)點(diǎn)比例和不同節(jié)點(diǎn)總數(shù)進(jìn)行,隨機(jī)布點(diǎn)實(shí)例如圖5所示。

①?gòu)?fù)雜地形不同錨點(diǎn)比例實(shí)驗(yàn)

傳感器總節(jié)點(diǎn)數(shù)設(shè)置為300,錨節(jié)點(diǎn)的比例取5%、10%、15%、20%、25%、30%和35%進(jìn)行實(shí)驗(yàn),每組實(shí)驗(yàn)進(jìn)行100次,實(shí)驗(yàn)結(jié)果取平均值,每次實(shí)驗(yàn)均隨機(jī)布點(diǎn)。圖6顯示,在復(fù)雜地形中錨節(jié)點(diǎn)比例大于10%時(shí)定位誤差相似,所以實(shí)際應(yīng)用中可以將錨節(jié)點(diǎn)比例設(shè)為10%。

②復(fù)雜地形傳感器節(jié)點(diǎn)數(shù)不同的實(shí)驗(yàn)

錨節(jié)點(diǎn)比例固定為10%,實(shí)驗(yàn)在節(jié)點(diǎn)總數(shù)分別為270、280、290、300、310、320和330的情況下進(jìn)行,每組數(shù)據(jù)進(jìn)行100次實(shí)驗(yàn),結(jié)果取平均值,每次均隨機(jī)布點(diǎn)。圖7顯示,當(dāng)節(jié)點(diǎn)總數(shù)大于290時(shí),定位精度趨同。

圖5 復(fù)雜地形傳感器節(jié)點(diǎn)隨機(jī)分布圖

圖6 復(fù)雜地形不同錨節(jié)點(diǎn)比例的平均定位誤差

圖7 復(fù)雜地形不同節(jié)點(diǎn)總數(shù)的平均定位誤差

4 總結(jié)

通過(guò)對(duì)比實(shí)驗(yàn)可以看到本文設(shè)計(jì)的較近點(diǎn)投影校正的無(wú)線傳感器網(wǎng)絡(luò)三維定位算法不僅在常規(guī)的山頭環(huán)境中能夠有效的提高定位精度,在復(fù)雜地形中也有較好的表現(xiàn)。用最近點(diǎn)投影的方法有效的利用了地形的網(wǎng)格數(shù)據(jù),使得定位精度有大幅度提高。因?qū)嶒?yàn)是在不同地形的網(wǎng)格數(shù)據(jù)下進(jìn)行的,能夠較真實(shí)的模擬實(shí)際地形環(huán)境,具有較大的實(shí)際應(yīng)用價(jià)值。

[1]張國(guó)清,王敬華. 基于畫圖算法的WSN節(jié)點(diǎn)定位算法[J]. 計(jì)算機(jī)工程,2009,35(20):25-27.

[2]Zhao F,Shin J,Reich J. Information-Driven Dynamic Sensor Collaboration[J]. IEEE Signal Processing Magazine,2002,19(2):68-77.

[3]Ma Zuchang,Sun Yining,Mei Tao. Summary for Wireless Sensor Network[J]. Journal of China Institute of Communications,2004,25(4):114-124.

[4]Hightower J,Boriello G,Want R. SpotON:An Indoor 3D Location Sensing Technology Based on RF Signal Strength[C]//Technical Report UW CSE 2000,Seattle:Department of Computer Science and Engineering. University of Washington,2000:452-463.

[5]Nicolescu D,Nath B. Ad-Hoc Positioning Systems(APS)[C]//Proc of the 2001 IEEE Global Telecommunications Conf. Vol.5,San Antonio:IEEE Communications Society,2001:2926-2931.

[6]Shang Y,Ruml W,Zhang Y,et al. Localization from Mere Connectivity[C]//Proc of the 4th ACM Int’l Symposium on Mobile Ad Hoc Networking and Computing. Annapolis:ACM Press,2003:201-212.

[7]Liang J L,Shao J,Xu Y,et al. Sensor Network Localization in Constrained 3-D Spaces[C]//Proceedings of IEEE International Conference on Mechatronics and Automation. USA:IEEE Press,2006:49-54.

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

[9]喬欣,常飛,丁恩杰,等. 基于跳距修正的WSN擬牛頓迭代定位算法[J]. 傳感技術(shù)學(xué)報(bào),2014(6):797-801.

[10]陳嘉興,劉志華. 無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的三維序列內(nèi)心定位算法[J]. 南京理工大學(xué)學(xué)報(bào):自然科學(xué)版,2011,35(3):371-375.

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

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

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

The 3D Localization Mechanism for Wireless Sensor Networks Based on Mountainous Terrain*

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 closer points projection correction which use the mountainous terrain mesh data for the problem that the localization error is large when 3D DV-hop algorithm is carried out in the actual terrain. After get the location of a node by using 3D DV-hop algorithm,search three points near the location of the node which is non-collinear and on the mountainous terrain mesh and make the node project toward the surface which is determined by the above three points. Projection point is the node’s location after correction. Multi-scene experiments show that this method can greatly reduce the position error.

WSN;3D DV-hop;adapt to terrain;closer points projection

胡中棟(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ì)算。

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

2014-07-21 修改日期:2014-12-26

C:6150P;7230

10.3969/j.issn.1004-1699.2015.03.019

TP393

A

1004-1699(2015)03-0408-04