景秀眉,張仁貢

(1.浙江同濟科技職業(yè)學院信息系,杭州 311231;2.浙江同濟科技職業(yè)學院機電系,杭州 311231)

?

基于移動錨節(jié)點與多級通信的三維傳感器網(wǎng)絡節(jié)點自定位算法研究*

景秀眉1*,張仁貢2

(1.浙江同濟科技職業(yè)學院信息系,杭州 311231;2.浙江同濟科技職業(yè)學院機電系,杭州 311231)

在基于移動錨節(jié)點的三維傳感器網(wǎng)絡節(jié)點自定位算法SNLSFA(Sensor Node Localization Scheme based on Flying Anchors)的基礎上,提出了一種新的基于移動錨節(jié)點與多級通信的三維傳感器網(wǎng)絡節(jié)點自定位算法SNLSFAMC(Sensor Node Localization Scheme based on Flying Anchors and Multi-level Communication)。首先由移動錨節(jié)點提供3個或4個輔助定位點,再由輔助定位點得到兩條非平行線段,然后過線段中點分別做垂直于線段的平面,經(jīng)兩平面相交后得到一條經(jīng)過待定位節(jié)點的直線,最后利用輔助定位點與待定位節(jié)點之間的距離作為通信半徑即可得到待定位節(jié)點的位置。仿真結果表明,與SNLSFA相比,在相同錨節(jié)點數(shù)量下,SNLSFAMC提高了定位精度,且在相同定位精度下,SNLSFAMC降低了對錨節(jié)點數(shù)量的需求,提高了算法的響應時間。

移動錨節(jié)點;多級通信;三維節(jié)點自定位

無線傳感器網(wǎng)絡WSN(Wireless Sensor Network)是一種傳感器節(jié)點通過自組織方式快速形成的分布式網(wǎng)絡。各個節(jié)點采集的數(shù)據(jù)必須結合其位置信息才有意義,且網(wǎng)絡的覆蓋控制、目標跟蹤等都依賴于對各個節(jié)點的有效定位[1-7]。因此,如何確定節(jié)點的自身位置是傳感器網(wǎng)絡的一項重要支撐技術。

現(xiàn)有的定位技術大多使用安裝GPS的錨節(jié)點為待定位節(jié)點提供位置信息,根據(jù)錨節(jié)點是否移動,定位算法可分為基于靜態(tài)錨節(jié)點和基于移動錨節(jié)點的定位。基于靜態(tài)錨節(jié)點的定位算法中,為完成對整個網(wǎng)絡未知位置節(jié)點的定位,需要布設較多的錨節(jié)點,大大增加了整個網(wǎng)絡的成本以及定位算法的計算負荷和網(wǎng)絡的通訊負荷[8-12]?；谝苿渝^節(jié)點的定位算法中,由于錨節(jié)點可自由移動,因此僅需布設較少的錨節(jié)點,降低了定位算法對錨節(jié)點密度的依賴程度,且能降低網(wǎng)絡拓撲結構復雜度及網(wǎng)絡能耗[13-15]。因此利用移動錨節(jié)點輔助定位已成為節(jié)點自定位算法的重要研究方向。

Zhang等人提出了一種Landscape-3D空間定位算法[16],采用一種輔助定位裝置LA(Location Assistant)在監(jiān)測區(qū)域上空飛行并周期性廣播自身位置信息,待定位節(jié)點接收信息后采用RSSI技術測量其與LA之間的距離,進而計算出自身位置。

Fu Y等人提出了一種基于單個移動錨節(jié)點的與測距無關的三維節(jié)點自定位算法[17],錨節(jié)點遍歷整個三維空間收集待定位節(jié)點的信息,并根據(jù)移動模型計算節(jié)點位置,當錨節(jié)點再次穿越待定位節(jié)點的通信球體時,實現(xiàn)對待定位節(jié)點的再定位。

Yu等人提出了一種協(xié)作定位算法[18],傳感器節(jié)點從移動錨節(jié)點組接收消息并估計位置,移動錨節(jié)點組由3個移動錨節(jié)點組成,每個錨節(jié)點分別位于等邊三角形的一個頂點,定位精度與錨節(jié)點數(shù)量成正比。算法要求錨節(jié)點間具有較強的協(xié)調(diào)能力,且錨節(jié)點組的成本較高。

Chia-Ho Ou等人[19]提出了一種基于移動錨節(jié)點的二維傳感器網(wǎng)絡節(jié)點自定位算法,由錨節(jié)點的移動特性求出待定位節(jié)點通信圓周上的臨界通信點,并利用圓周上的兩個臨界通信點作線段,然后作該線段的中垂線,由兩條中垂線相交求出待定位節(jié)點的估計位置。在此基礎上,Chia-Ho Ou提出了基于移動錨節(jié)點的三維傳感器網(wǎng)絡節(jié)點自定位算法SNLSFA(Sensor Node Localization Scheme based on Flying Anchors)[20],其原理與文獻[19]的算法相似,亦是利用兩條垂直于通信球內(nèi)切圓平面的直線相交進而得到待定位節(jié)點的估計位置。與其他利用移動錨節(jié)點的三維傳感器網(wǎng)絡節(jié)點自定位算法相比,SNLSFA只需移動錨節(jié)點與待定位節(jié)點之間的通信信息便可估計出待定位節(jié)點位置,使其在小范圍的三維傳感器網(wǎng)絡節(jié)點自定位應用中有較大優(yōu)勢。

但是SNLSFA存在以下問題:①定位精度依賴于錨節(jié)點密度;②定位需要較長時間,實時性不高;③依靠兩垂線的交點得到待定位節(jié)點位置,實際的通信模型中節(jié)點的通信范圍并不一定是完美的球形,即算法得到的兩條垂線不一定相交,使定位精度受到影響。

本文在SNLSFA的基礎上提出了一種基于移動錨節(jié)點與多級通信的三維傳感器網(wǎng)絡節(jié)點自定位算法SNLSFAMC(Sensor Node Localization Scheme based on Flying Anchors and Multi-level Communication),通過移動錨節(jié)點提供3個或4個非共面的輔助定位點,由輔助定位點得到兩條非平行線段,過線段中點分別作垂直于線段的平面,經(jīng)兩平面相交得到一條經(jīng)過待定位節(jié)點的直線,利用輔助定位點與待定位節(jié)點間的距離為通信半徑得到待定位節(jié)點的位置。避免了SNLSFA中兩直線不相交的情形,同時SNLSFAMC只需3個臨界通訊信息點即可開始定位,與SNLSFA相比減少了一個臨界通訊信息點,并且SNLSFAMC將待定位節(jié)點的通訊半徑分為兩級,使錨節(jié)點在穿越待定位節(jié)點通信覆蓋范圍時多了一次獲得待定位節(jié)點臨界通訊信息點的機會,降低了對錨節(jié)點數(shù)量的需求并提高了算法響應時間。仿真結果表明,在相同的錨節(jié)點數(shù)下,相對于SNLSFA,SNLSFAMC的定位精度明顯提高,且在相同定位精度下,SNLSFAMC降低了對錨節(jié)點數(shù)量的需求,提高了算法的實時性。

1 算法原理與流程

1.1 算法原理

SNLSFAMC是一種基于移動錨節(jié)點與多級通信的三維空間節(jié)點自定位算法,與SNLSFA類似,算法分為準備階段與定位階段。

1.1.1 準備階段

假設節(jié)點發(fā)射功率可調(diào)節(jié),且分為兩級,Ⅰ級通信半徑為50 m,Ⅱ級通信半徑為100 m,如圖1所示。

圖1 節(jié)點通信級別圖

圖2 錨節(jié)點運動軌跡圖

同時假設錨節(jié)點可在監(jiān)測區(qū)域內(nèi)自由移動,其運動軌跡如圖2所示,當錨節(jié)點進入或離開待定位節(jié)點的通信范圍時,待定位節(jié)點記錄錨節(jié)點在t1,t2,t3,t4時刻的位置,分別以A,B,C,D四點表示。當A,B,C,D四點在同一平面時,其坐標的求解過程與SNLSFA類似,在此不再贅述(詳見文獻[20])。當A,B,C,D四點不在同一平面時,SNLSFAMC進入定位階段。

1.1.2 定位階段

(1)

(2)

圖3 SNLSFAMC定位原理圖

由式(3)得到經(jīng)過點S1且垂直于向量AB的平面方程N1:

(3)

同理,已知向量CD及其中點S2,由式(4)得到經(jīng)過點S2且垂直于向量CD的平面方程N2:

(4)

由于點S為待定位節(jié)點通信球的球心,因此線段SA與SB長度相等,且點S1為線段AB的中點,根據(jù)等腰三角形特性可知,線段SS1垂直于線段AB,如圖4所示。

圖4 線段垂直于線段AB圖

由于線段SS1經(jīng)過點S1,因此SS1必定在經(jīng)過點S1且垂直于線段AB的平面N1上,即待定位節(jié)點通信球心在平面N1上。同理,線段SS2必定在經(jīng)過點S2且垂直于線段CD的平面N2上,即待定位節(jié)點通信球心同樣在平面N2上,因此點S位于平面N1與N2的相交線上。

聯(lián)立式(3)與式(4)可得出平面N1與N2的相交線的一般方程,如式(5)所示:

(5)

進而得到直線l的方向向量l(i,j,k),如式(6)所示:

(6)

取直線l上的任意一點P(xp,yp,zp)代入式(6)可得到直線對稱方程,如式(7)所示:

(7)

已知點A及直線l的方向向量l(i,j,k),即可求出經(jīng)過A點并且垂直于直線l的平面NT:

NT:i(x-xa)+j(y-ya)+k(z-za)=0

(8)

聯(lián)立式(7)與式(8)得到平面NT與直線l的交點的坐標,這里記為點H(xh,yh,zh):

(9)

根據(jù)點A坐標及三維空間中點到直線的距離公式,得到點A到直線l的距離da,則圓心的坐標如式(10)所示:

(10)

同理,可求出B點在直線l上的投影點Q的坐標如式(11)所示:

(11)

根據(jù)點B坐標及三維空間中點到直線的距離公式,得到點B到直線l的距離db,則圓心坐標如式(12)所示:

(12)

聯(lián)立式(10)、(12)得到待定位節(jié)點的估計位置(xs,ys,zs),定位過程結束。

從上述SNLSFAMC的算法原理可以看出,通過移動錨節(jié)點提供3個或4個非共面的輔助定位點,由輔助定位點得到兩條非平行線段,過線段中點分別作垂直于線段的平面,經(jīng)兩平面相交得到一條經(jīng)過待定位節(jié)點的直線,利用輔助定位點與待定位節(jié)點之間的距離為通信半徑即可得到待定位節(jié)點的位置。避免了SNLSFA中出現(xiàn)兩直線不相交的情形,同時SNLSFAMC只需3個臨界通訊信息點即可開始定位,與SNLSFA相比減少了一個臨界通訊信息點的需求,并且SNLSFAMC將待定位節(jié)點的通訊半徑分為兩級,使錨節(jié)點在穿越待定位節(jié)點通信覆蓋范圍時多了一次獲得待定位節(jié)點臨界通訊信息點的機會,降低了對錨節(jié)點數(shù)量的需求,提高了算法實時性。

1.2 算法流程

2 算法仿真與分析

2.1 仿真參數(shù)設置

為分析SNLSFAMC的有效性,對SNLSFAMC與SNLSFA的相對定位誤差、定位時長、可定位節(jié)點數(shù)等指標進行仿真、分析和比較。節(jié)點廣播時隙、錨節(jié)點運動速度均參照文獻[18],其他參數(shù)如表1所示。

表1 仿真參數(shù)設置

相對定位誤差定義為:

(13)

2.2 仿真算例

SNLSFAMC與SNLSFA都需要錨節(jié)點反復穿越待定位節(jié)點的覆蓋空間以幫助待定位節(jié)點獲取輔助定位信息。仿真時,設置錨節(jié)點每0.3 s隨機改變一次運動方向,以此完成遍歷整個三維空間的運動。當錨節(jié)點為50個,算法運行60 s后的錨節(jié)點運動軌跡如圖5所示,可以看出錨節(jié)點幾乎遍歷了整個三維空間。

圖5 錨節(jié)點運動軌跡圖

圖6為SNLSFAMC與SNLSFA的相對定位誤差隨錨節(jié)點數(shù)量變化對比圖,可以看出SNLSFAMC與SNLSFA的相對定位誤差均隨錨節(jié)點數(shù)量增加而下降,SNLSFAMC的相對定位誤差始終小于SNLSFA,說明SNLSFAMC對錨節(jié)點密度依賴較小,相對于SNLSFA,達到相同的定位精度,需要更少的錨節(jié)點。這是因為SNLSFAMC引入了通信半徑分級機制,當錨節(jié)點穿過待定位節(jié)點通信范圍時,錨節(jié)點提供了兩次相對位置信息,實現(xiàn)了對錨節(jié)點的再利用,而在SNLSFA中,每次錨節(jié)點穿過待定位節(jié)點通信范圍時,只提供一次相對位置信息。因此在相同的錨節(jié)點數(shù)量下,SNLSFAMC中待定位節(jié)點獲得的輔助定位信息更豐富,定位更準確、相對定位誤差更低。

圖6 相對定位誤差隨錨節(jié)點數(shù)量變化對比圖

圖7為SNLSFAMC與SNLSFA定位網(wǎng)絡95%以上待定位節(jié)點所需時間隨錨節(jié)點數(shù)量變化對比圖,可以看出,SNLSFAMC與SNLSFA完成定位所需時間均隨錨節(jié)點數(shù)量增加而減少。當錨節(jié)點數(shù)量小于210個時,在相同的錨節(jié)點數(shù)量下,SNLSFA定位所需時間始終大于SNLSFAMC,當錨節(jié)點數(shù)量為10個時,SNLSFA定位95%待定位節(jié)點所需時間在140 s左右,而SNLSFAMC定位95%待定位節(jié)點所需時間在100 s左右。當錨節(jié)點數(shù)量大于210個時,兩者定位所需時間基本相同。這是因為SNLSFAMC中引入了通信半徑分級方法使得錨節(jié)點得以再次利用,且只需3個輔助定位點即可開始定位,縮短了定位時間,而SNLSFA需要4個輔助定位點才可開始定位,因此在相同錨節(jié)點數(shù)量下,SNLSFAMC定位所需時間小于SNLSFA所需時間。

圖7 算法定位時長隨錨節(jié)點數(shù)量變化對比圖

圖8 已定位節(jié)點數(shù)量隨算法執(zhí)行時間變化關系圖

圖8為當錨節(jié)點數(shù)量為50個時,SNLSFAMC與SNLSFA已定位節(jié)點數(shù)量隨算法執(zhí)行時間變化對比圖,可以看出,當算法運行相同時間時,SNLSFAMC完成定位的節(jié)點數(shù)量始終大于SNLSFA。當算法運行10 s時,SNLSFAMC定位了近150個節(jié)點,SNLSFA定位了約100個節(jié)點。當算法運行50 s時,SNLSFAMC定位了約470個節(jié)點,SNLSFA法定位了約420個節(jié)點。這是因為SNLSFAMC只需3個輔助定位點節(jié)點即可開始定位,而SNLSFA需要4個輔助定位點才開始定位。因此算法開始運行的一段時間內(nèi),SNLSFAMC所定位的節(jié)點數(shù)量要多于SNLSFA所定位的節(jié)點數(shù)量。當算法運行時間大于50 s后,SNLSFAMC與SNLSFA所定位的節(jié)點數(shù)量差距逐漸縮小且定位增速越來越慢。這是因為無論SNLSFAMC還是SNLSFA,隨著算法的運行網(wǎng)絡中已定位的節(jié)點越來越多,網(wǎng)絡所能提供的輔助定位點信息也越來越豐富,導致兩者可定位節(jié)點數(shù)的差距越來越小,同時由于在前面的一段時間內(nèi)錨節(jié)點所遍歷的區(qū)域內(nèi)待定位節(jié)點多數(shù)已被定位,剩余的待定位節(jié)點需要靠錨節(jié)點運動至某些角落區(qū)域方可定位,導致可定位節(jié)點數(shù)的增速越來越慢。

圖9為錨節(jié)點數(shù)量為50個、節(jié)點廣播時隙為0.3 s時,SNLSFAMC與SNLSFA的相對定位誤差隨錨節(jié)點運動速度變化對比圖,可以看出,SNLSFAMC與SNLSFA的定位誤差均隨錨節(jié)點運動速度增大而增大。這是因為當節(jié)點廣播時隙為0.3 s、錨節(jié)點速度為10 m/s時,錨節(jié)點每次在時隙中的運動距離為3 m,因此輔助定位節(jié)點位置的誤差在3 m以內(nèi),可以得到較精確的定位結果。隨著錨節(jié)點運動速度增加時,輔助定位信息誤差越大,對算法的影響也越來越大,因此相對定位誤差也隨之增大。但是在相同的錨節(jié)點運動速度下,SNLSFAMC的相對定位誤差小于SNLSFA。當錨節(jié)點速度為30 m/s時,SNLSFA的相對定位誤差在0.08左右,SNLSFAMC的相對定位誤差在0.06左右。這是因為SNLSFAMC采用了通訊半徑分級的方式使得在相同的錨節(jié)點穿越次數(shù)下,待定位節(jié)點能獲得較多的輔助定位點位置,并且輔助定位點數(shù)量為3個時算法即可開始定位,所以當錨節(jié)點運動速度相同時,SNLSFAMC的相對定位誤差始終小于SNLSFA。

圖9 待定位節(jié)點相對定位誤差隨錨節(jié)點運動速度變化關系圖

3 結語

本文在基于移動錨節(jié)點的三維傳感器網(wǎng)絡節(jié)點自定位算法SNLSFA的基礎上,提出了一種新的基于移動錨節(jié)點與多級通信的三維傳感器網(wǎng)絡節(jié)點自定位算法SNLSFAMC。與SNLSFA相比,SNLSFAMC只需3個臨界通訊信息點即可開始定位,減少了一個臨界通訊信息點,同時SNLSFAMC將待定位節(jié)點的通訊半徑分為兩級,當錨節(jié)點在穿越待定位節(jié)點通信覆蓋范圍時,使得待定位節(jié)點多了一次獲取臨界通訊信息點的機會,提高了錨節(jié)點的利用率。仿真結果表明,在相同的錨節(jié)點數(shù)量下,相對于SNLSFA,SNLSFAMC的定位精度顯著提高,且在相同定位精度的情況下,SNLSFAMC降低了對錨節(jié)點數(shù)量的需求,提高了算法的響應時間。

[1] Mao G,Fidan B,Anderson B.Wireless Sensor Network Localization Techniques[J].Computer Networks,2007,51(10):2529-2553.

[2]Viani F,Rocca P,Oliveri G,et al.Localization,Tracking,and Imaging of Targets in Wireless Sensor Networks:An Invited Review[J].Radio Science,2011,46(5):21-30.

[3]Pal A.Localization Algorithms in Wireless Sensor Networks:Current Approaches and Future Challenges[J].Network Protocols and Algorithms,2010,2(1):46-73.

[4]Wang J,Ghosh R K,Das S K.A Survey on Sensor Localization[J].Journal of Control Theory and Applications,2010,8(1):2-11.

[5]Suo H,Wan J,Huang L,et al.Issues and Challenges of Wireless Sensor Networks Localization in Emerging Applications[C]//International Conference on Computer Science and Electronics Engineering,2012:447-451.

[6]Kuriakose J,Joshi S,Raju R V,et al.A Review on Localization in Wireless Sensor Networks[M].Advances in Intelligent Systems and Computing,Springer International Publishing,2014:599-610.

[7]Han G,Xu H,Duong T Q,et al.Localization Algorithms of Wireless Sensor Networks:A Survey[J].Telecommunication Systems,2013,52(4):2419-2436.

[8]Wei N,Guo Q,Shu M L,et al.Three-Dimensional Localization Algorithm of Wireless Sensor Networks Base on Particle Swarm Optimization[J].The Journal of China Universities of Posts and Telecommunications,2012,19(2):7-12.

[9]Guo H,Low K S,Nguyen H A.Optimizing the Localization of a Wireless Sensor Network in Real Time Based on a Low-cost Microcontroller[J].IEEE Transactions on Industrial Electronics,2011,58(3):741-749.

[10]Kumar A,Khosla A,Saini J S,et al.Stochastic Algorithms for 3D Node Localization in Anisotropic Wireless Sensor Networks[C]//7th International Conference on Bio-Inspired Computing:Theories and Applications.Springer India,2013:1-14.

[11]Jiang H,Zhang Y,Cui H,et al.Fast Three-Dimensional Node Localization in UWB Wireless Sensor Network Using Propagator Method Digest of Technical Papers[C]//2013 IEEE International Conference on Consumer Electronics,2013:627-628.

[12]Chaurasiya V K,Jain N,Nandi G C.A Novel Distance Estimation Approach for 3D Localization in Wireless Sensor Network Using Multi-Dimensional Scaling[J].Information Fusion(Special issue),2014,15:5-18.

[13]Hongyang C.Mobile Element Assisted Cooperative Localization for Wireless Sensor Networks with Obstacles[J].IEEE Transactions on Wireless Communications,2010,9(3):956-963.

[14]Guerrero E,Alvarez J,Rivero L.3D-ADAL:A Three-Dimensional Distributed Range-Free Localization Algorithm for Wireless Sensor Networks Based on Unmanned Aerial Vehicles[C]//5th International Conference on Digital Information Management,2010:332-338.

[15]Erol-Kantarci M.A Survey of Architectures and Localization Techniques for Underwater Acoustic Sensor Networks[J].IEEE Communications Surveys and Tutorials,2011,13(3):478-502.

[16]Zhang L,Zhou X B,Cheng Q.Landscape-3D:A Robust Localization Scheme for Sensor Networks over Complex 3D Terrains[C]//IEEE Conference on Local Computer Networks,2006:239-246.

[17]Fu Y J,Lee T H,Chang L,et al.A Single Mobile Anchor Localization Scheme for Wireless Sensor Networks[C]//IEEE International Conference on High Performance Computing and Communications,2011:946-950.

[18]Zhang Z,Yu F.Collaborative Localization Algorithm for Wireless Sensor Networks Using Mobile Anchors[C]//Asia-Pacific Conference on Computational Intelligence and Industrial Applica-tions,2009:309-312.

[19]Chia-Ho O.Range-Free Node Localization for Mobile Wireless Sensor Networks[C]//Wireless Pervasive Computing,2008:535-539.

[20]Chia-Ho O,Kuo-Feng S.Sensor Position Determination with Flying Anchors in Three-Dimensional Wireless Sensor Networks[J].IEEE Transactions on Mobile Computing,2008,7(9):1084-1097.

景秀眉(1975-),女,碩士,浙江同濟科技職業(yè)學院副教授,主要研究方向為無線傳感器網(wǎng)絡、計算機技術及應用;

張仁貢(1975-),男,博士,浙江同濟科技職業(yè)學院副教授,主要研究方向為無線傳感器網(wǎng)絡、工業(yè)自動化。

Three-DimensionalSensorNetworkNodeSelf-LocalizationAlgorithmBasedonMobilityAnchorNodesandMulti-LevelCommunication*

JINGXiumei1*,ZHANGRengong2

(1.Department of Information,Zhejiang Tongji Vocational College of Science and Technology,Hangzhou 311231,China;2.Department of Mechanical and Electrical Engineering,Zhejiang Tongji Vocational College of Science and Technology,Hangzhou 311231,China)

A new sensor node localization algorithm based on the flying anchor and the multi-level communication(SNLSFAMC)on the basis of the sensor node localization scheme with flying anchors(SNLSFA)is present.First,the mobile anchor nodes provide three or four auxiliary anchor points,which help us to get two non-parallel line segments.And then we can get two planes which are perpendicular to the two line segments and go through the midpoint of them.These two planes will intersect with each other to form a line which goes through the node to be positioned.Finally,the distance between the auxiliary anchor point and the un-positioned node,as the communication radius,can be used to obtain the position of the un-positioned node.The simulation results show that on the condition of the same number of nodes,the SNLSFAMC algorithm can improve the positioning accuracy compared with SNLSFA algorithm;And on the condition of the same positioning accuracy,the SNLSFAMC algorithm need less anchor nodes,as well as can improve the response time.

mobile anchor nodes;multi-level communication;three-dimensional node self-localization

項目來源:國家“十二五”支撐計劃項目(2012BAD10B01);浙江省重點科技創(chuàng)新團隊項目(2012BAD10B01);浙江省科技廳高技能人才培養(yǎng)和創(chuàng)新技術項目(2013R30058);浙江省教育廳高等教育改革項目(jg2013391)

2014-05-12修改日期:2014-05-29

10.3969/j.issn.1004-1699.2014.06.022

TP393

:A

:1004-1699(2014)06-0828-07