航空信標(biāo)輔助WSN三維定位的移動路徑規(guī)劃方法

譚中華，徐 玉

(溫州大學(xué) 物理與電子信息工程學(xué)院，浙江 溫州 325035)

航空信標(biāo)輔助WSN三維定位的移動路徑規(guī)劃方法

譚中華，徐 玉

(溫州大學(xué) 物理與電子信息工程學(xué)院，浙江 溫州 325035)

三維定位對于相當(dāng)多的無線傳感器網(wǎng)絡(luò)(WSN)應(yīng)用非常重要，但通常復(fù)雜度與成本較高?；谝苿?航空)信標(biāo)輔助的三維定位是相對節(jié)約成本的一類方法。針對這類方法需要解決的移動路徑規(guī)劃問題，提出了一種實現(xiàn)簡單、路徑長度短的三維移動路徑規(guī)劃方法。在三維空間中，航空信標(biāo)只需在兩平面上對三維部署區(qū)域進(jìn)行兩次相互獨立的二維掃描。3D SCAN、3D DOUBLE SCAN、3D HILBERT、3D CIRCLES、3D S-CURVES和3D LMAT是該方法的六種典型實現(xiàn)。仿真實驗結(jié)果表明，基于該路徑規(guī)劃方法的六種典型路徑都能夠滿足三維定位需要。其中，3D S-CURVES路徑長度最短、定位精度最高。

三維；無線傳感器網(wǎng)絡(luò)；定位；航空信標(biāo)；路徑規(guī)劃

0 引 言

近年來，無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks,WSNs)在環(huán)境監(jiān)測與保護(hù)、軍事偵查、目標(biāo)追蹤等領(lǐng)域有著非常廣泛的應(yīng)用。在這些應(yīng)用中，位置是最基本的上下文信息之一。因此，節(jié)點的定位問題受到了研究者的廣泛關(guān)注。

定位是指節(jié)點運用某種技術(shù)或方法，確定自身位置?，F(xiàn)有的無線傳感網(wǎng)絡(luò)采用更多的是基于信標(biāo)節(jié)點(已知自身位置的節(jié)點)的定位方法，如基于測距的RSS[1]、TDoA[2]、TOA[3]和AOA[4-5]和非測距的質(zhì)心定位[6-7]、DV-Hop[8]、MDS-MAP[9]等。在這些基于靜態(tài)信標(biāo)節(jié)點的定位方法中，節(jié)點的定位精度與其附近信標(biāo)節(jié)點的數(shù)量和質(zhì)量直接相關(guān)。為了獲得好的定位精度，就需要在部署區(qū)域中放置大量的靜態(tài)信標(biāo)節(jié)點，這勢必會導(dǎo)致定位成本的大幅上升。為此，研究者提出了基于移動信標(biāo)節(jié)點的輔助定位方法[10]。移動信標(biāo)節(jié)點沿一定的軌跡掃描整個部署區(qū)域，在移動的過程中以一定的頻率廣播包含自身動態(tài)位置信息的虛擬信標(biāo)；未知節(jié)點接收通信范圍內(nèi)的虛擬信標(biāo)，根據(jù)其與虛擬信標(biāo)的距離或方位信息計算自身位置。在該方法中，可重復(fù)利用的移動信標(biāo)節(jié)點取代了大量的靜態(tài)信標(biāo)節(jié)點，降低了定位成本；移動信標(biāo)節(jié)點給未知節(jié)點提供大量的虛擬信標(biāo)，降低了估測誤差，提高了定位精度。

目前，常用的移動信標(biāo)有兩類：基于無線遙控車[11]的地面移動信標(biāo)和基于無人機(UAV)[12-13]的航空移動信標(biāo)。相較于地面移動信標(biāo)，航空移動信標(biāo)具有如下優(yōu)勢：

(1)裝備有GPS/SINS組合導(dǎo)航系統(tǒng)的UAV能夠給航空信標(biāo)提供實時的高精度位置信息。

(2)空中飛行的航空信標(biāo)具有更好的無線電通信環(huán)境和更廣闊的信號覆蓋。

(3)在幾乎沒有障礙的空中，航空信標(biāo)能夠準(zhǔn)確地跟蹤復(fù)雜的移動路徑。

(4)航空信標(biāo)能夠安全地出入人工干預(yù)困難或危險的區(qū)域。

1 問題與挑戰(zhàn)分析

就基于移動信標(biāo)節(jié)點的輔助定位而言，無論是采用地面移動信標(biāo)還是航空移動信標(biāo)，都需要解決移動信標(biāo)的路徑規(guī)劃問題。路徑直接影響節(jié)點的定位精度和航空信標(biāo)的飛行距離。就二維定位，文獻(xiàn)[14]對移動信標(biāo)的路徑規(guī)劃提出了兩個基本要求：首先，移動路徑應(yīng)盡可能覆蓋整個部署區(qū)域；其次，移動路徑應(yīng)確保未知節(jié)點能夠獲得定位所需條件，且讓移動信標(biāo)盡可能近地經(jīng)過未知節(jié)點。文獻(xiàn)[15]提出了SCAN、DOUBLE SCAN和HILBERT三種線性路徑方案。文獻(xiàn)[16]提出了同心圓路徑CIRCLES和“S”形路徑S-CURVES。文獻(xiàn)[17]提出一種等邊三角形路徑LMAT。然而，就三維定位的路徑規(guī)劃而言，除了滿足文獻(xiàn)[14]所提出的兩個基本要求外，還需要確保未知節(jié)點至少能夠接收到四個不共面的虛擬信標(biāo)才能完成自身定位，從而移動信標(biāo)節(jié)點至少需要在兩個不同高度的平面中運動；同時，飛行路徑的路徑長度應(yīng)盡可能短，以減少航空信標(biāo)的能量消耗。

為此，如何在滿足上述四個基本條件的基礎(chǔ)上尋找出實現(xiàn)簡單、路徑長度短,同時又能獲得較高定位精度的移動路徑成為了關(guān)鍵問題。為了解決這個關(guān)鍵問題，文中提出一種新的三維路徑規(guī)劃方法。下面將對新路徑規(guī)劃方法進(jìn)行介紹，且給出六種典型實現(xiàn)路徑。以最小二乘三維定位算法為例，對六種典型實現(xiàn)路徑進(jìn)行了模擬仿真實驗。實驗結(jié)果表明，該方法能夠滿足三維定位對移動路徑的需要。

2 三維路徑規(guī)劃方法

2.1 基本思想

對于布置在山地、深林、沼澤和水下等環(huán)境中的三維WSN定位，可將WSN部署區(qū)域看作三維空間底部的一個三維區(qū)域，如圖1所示。未知節(jié)點部署在一個凹凸不平的三維空間中，且移動信標(biāo)只能在部署區(qū)域的上空運動。此時，關(guān)鍵是如何設(shè)計航空信標(biāo)節(jié)點的移動路徑，既能使能量消耗最少，又能獲得良好的定位精度。

圖1 航空信標(biāo)輔助三維定位路徑規(guī)劃說明

文中提出的移動路徑規(guī)劃如圖1所示。航空信標(biāo)只需要在兩個不同高度的二維平面上對底部的三維部署區(qū)域進(jìn)行兩次相互獨立的二維平面掃描。每次二維平面掃描應(yīng)盡可能覆蓋整個部署區(qū)域，且航空信標(biāo)應(yīng)盡可能近地經(jīng)過未知節(jié)點。不同高度的兩次二維掃描應(yīng)確保部署區(qū)域內(nèi)的未知節(jié)點至少接收到4個不共面的虛擬信標(biāo)。這樣的移動路徑規(guī)劃方法既能確保未知節(jié)點獲得定位自身的條件，又能使移動路徑長度相對最短。兩次二維平面掃描是相互獨立的，這是規(guī)劃方法靈活性的體現(xiàn)，兩次掃描可以是任意的平面掃描路徑。例如，下層平面使用Nl階SCAN路徑，上層路徑使用Nh階HILBERT路徑。

2.2 典型路徑

根據(jù)上述的路徑規(guī)劃思想，設(shè)計了六種較為典型的路徑，當(dāng)然也可以進(jìn)行任意組合。

以3D SCAN路徑為例，如圖2(a)所示，該路徑在Z坐標(biāo)為z和z+dz的XY平面上沿Y軸方向?qū)Σ渴饏^(qū)域進(jìn)行兩次相互獨立的平面掃描。兩次平面掃描分別以Nl階和Nh階SCAN進(jìn)行。在XY平面路徑上，Y軸方向平行路徑之間的距離為該層路徑的分辨率。因此，3DSCAN的路徑分辨率由下層路徑分辨率dl和上層路徑分辨率dh共同決定。

同理可知，3DDOUBLESCAN、3DHILBERT、3DCIRCLES、3DS-CURVES和3DLMAT都是通過對應(yīng)的二維掃描路徑對三維空間進(jìn)行兩次相互獨立的掃描，如圖2所示。

圖2 六種典型實現(xiàn)路徑

假設(shè)三維部署區(qū)域的XY平面是W×W的正方形區(qū)域，路徑的分辨率為(dl,dh)，則路徑長度L的計算公式如下：

L3D SCAN=(4Nl-1)×dl+(4Nh-1)×dh

(1)

L3D DOUBLE SCAN=(4Nl+2Nl-4)×dl+(4Nh+2Nh- 4)×dh

(2)

L3D HILBERT=4Nl×dl+4Nh×dh

(3)

(4)

(5)

(6)

3 仿真實驗

運用MATLAB工具模擬如山地、深林和沼澤等三維WSN定位實現(xiàn)。在這些區(qū)域中，所有的未知節(jié)點都位于航空信標(biāo)節(jié)點的底部。仿真實驗中，三維區(qū)域中隨機部署N個未知節(jié)點，航空移動信標(biāo)沿著六條典型路徑飛行，且在移動過程中以一定的頻率廣播信號，未知節(jié)點接收到至少四個不共面的虛擬信標(biāo)，并通過最小二乘三維定位算法計算自身位置。

3.1 最小二乘三維定位算法

(7)

消除二項式(前n-1個等式減去第n個等式)得：

Kθ=D+E

(8)

其中：

(9)

(10)

(11)

D=

(12)

由式(8)可得θ的最小二乘估計：

θ=(KTK)-1KTD

(13)

3.2 仿真參數(shù)

仿真參數(shù)及其取值如表1所示。

表1 仿真參數(shù)

其中，WSN三維部署區(qū)域的長、寬、高為X,Y,Z；未知節(jié)點個數(shù)為Nodes，典型路徑分辨率為(dl,dh)；下層路徑Z坐標(biāo)為z；上下兩層路徑的Z坐標(biāo)差為dz；RSS對數(shù)正態(tài)陰影衰減模型的標(biāo)準(zhǔn)差為σ；實驗仿真次數(shù)為times。

4 結(jié)果與分析

Aerr(xyz)=

(14)

(15)

(16)

4.1Z坐標(biāo)對定位精度的影響

典型路徑的Z坐標(biāo)由下層路徑z坐標(biāo)和上下兩層路徑的z坐標(biāo)差dz共同決定。它是直接影響信標(biāo)節(jié)點與未知節(jié)點實際距離的重要因素。

如圖3(a)所示，隨著z的增大，各典型路徑的平均定位誤差都隨之增大。由此可知，z取值越小，定位誤差越小。z坐標(biāo)越大，未知節(jié)點與虛擬信標(biāo)節(jié)點的實際距離就會增大，定位誤差也就會越大。如圖3(b)所示，各典型路徑的平均定位誤差隨dz的增加呈現(xiàn)出先

圖3 Z坐標(biāo)對定位精度的影響

減后增的變化，且在dz=15m時定位誤差最小。dz對系統(tǒng)定位精度的影響受到了通信距離變大和定位算法的相互影響，所以會呈現(xiàn)出先減后增的變化。

4.2 路徑分辨率對定位精度的影響

路徑分辨率(dl,dh)由下層路徑分辨率dl與上層路徑分辨率dh共同決定。圖4為9種(dl,dh)取值下各典型路徑的平均定位誤差變化。

圖4 路徑分辨率(dl,dh)對定位精度的影響

當(dāng)路徑分辨率(dl,dh)取值越大，系統(tǒng)的平均定位誤差越大。比較(60,30)和(30,60)，(60,15)和(15,60)，(30,15)和(15,30)的結(jié)果可知，dl>dh的平均定位誤差要小于dl

4.3 環(huán)境噪聲對定位精度的影響

環(huán)境噪聲直接影響節(jié)點之間距離的估測。在仿真環(huán)境中，通過RSS對數(shù)陰影正態(tài)估測模型中的標(biāo)準(zhǔn)差σ來控制環(huán)境噪聲的影響。σ取值越大，環(huán)境噪聲影響越嚴(yán)重，距離估測誤差就越大。如圖5所示，隨著變量σ的逐漸增大，各典型路徑的平均定位誤差都隨之增大。

圖5 標(biāo)準(zhǔn)差σ對定位精度的影響

5 結(jié)束語

文中以三維定位對移動路徑規(guī)劃的基本要求為基礎(chǔ)，結(jié)合航空信標(biāo)輔助三維定位的特點，提出了一種實現(xiàn)簡單、路徑長度最短的新三維移動路徑規(guī)劃方法。該方法適用于航空信標(biāo)節(jié)點輔助三維定位，具有較好的靈活性。設(shè)計了六種典型實現(xiàn)路徑，且能夠任意組合，如SCAN和S-CURVES結(jié)合的三維移動路徑等。靈活多變的移動路徑給人們提供了更多的路徑規(guī)劃選擇，較短的移動路徑長度降低了航空信標(biāo)節(jié)點的能量消耗。未來的工作方向是尋找到適合該類規(guī)劃方法的定位方法，從而提高該類三維定位的定位精度。

[1]BahlP,PadmanabhanVN.RADAR:anin-buildingRF-baseduserlocationandtrackingsystem[C]//ProceedingsofIEEEINFOCOM.[s.l.]:IEEE,2000:775-784.

[2]WengY,XiaoW,XieL.TotalleastsquaresmethodforrobustsourcelocalizationinsensornetworksusingTDOAmeasurements[J].InternationalJournalofDistributedSensorNetworks,2011(3):1063-1067.

[3]GirodL,EstrinD.Robustrangeestimationusingacousticandmultimodalsensing[C]//ProceedingsofIEEE/RSJinternationalconferenceontheintelligentrobotsandsystems.[s.l.]:IEEE,2001.

[4]WangJ,ChenY,FuX,etal.3DLoc:threedimensionalwirelesslocalizationtoolkit[C]//IEEE30thinternationalconferenceondistributedcomputingsystems.[s.l.]:IEEE,2010:30-39.

[5]ChenY,LiuZ,FuX,etal.TheoryunderlyingmeasurementofAOAwitharotatingdirectionalantenna[C]//ProceedingsofIEEEINFOCOM.[s.l.]:IEEE,2013:2490-2498.

[6] 林 瑋,陳傳峰.基于RSSI的無線傳感器網(wǎng)絡(luò)三角形質(zhì)心定位算法[J].現(xiàn)代電子技術(shù),2009,32(2):180-182.

[7] 唐明虎,張長宏,昝風(fēng)彪.無線傳感器網(wǎng)絡(luò)APIT定位算法[J].微型機與應(yīng)用,2010,29(21):1-4.

[8] 張 震,閆連山,劉江濤,等.基于DV-hop的無線傳感器網(wǎng)絡(luò)定位算法研究[J].傳感技術(shù)學(xué)報,2011,24(10):1469-1472.

[9] 馬 震,劉 云,沈 波.分布式無線傳感器網(wǎng)絡(luò)定位算法MDS-MAP(D)[J].通信學(xué)報,2008,29(6):57-62.

[10]PriyanthaNB,BalakrishnanH,DemaineED,etal.Mobile-assistedlocalizationinwirelesssensornetworks[C]//ProceedingsoftheIEEEINFOCOM.Miami,FL:IEEE,2005.

[11]SichitiuML,RamaduraiV.Localizationofwirelesssensornetworkswithamobilebeacon[C]//IEEEinternationalconferenceonmobilead-hocandsensorsystems.[s.l.]:IEEE,2004:174-183.

[12]KimK,LeeW.MBAL:amobilebeacon-assistedlocalizationschemeforwirelesssensornetworks[C]//Proceedingsof16thinternationalconferenceoncomputercommunicationsandnetworks.[s.l.]:IEEE,2007:57-62.

[13]LiuZ,ChenY,LiuB,etal.HAWK:anunmannedminihelicopter-basedaerialwirelesskitforlocalization[C]//ProceedingsofIEEEINFOCOM.[s.l.]:IEEE,2012:2219-2227.

[14]SsuKF,OuCH,JiauHC.Localizationwithmobileanchorpointsinwirelesssensornetworks[J].IEEETransactionsonVehicularTechnology,2005,54(3):1187-1197.

[15]KoutsonikolasD,DasSM,HuYC.Pathplanningofmobilelandmarksforlocalizationinwirelesssensornetworks[J].ComputerCommunications,2006,30(13):86.

[16]HuangR,ZarubaGV.Staticpathplanningformobilebeaconstolocalizesensornetworks[C]//IEEEinternationalconferenceonpervasivecomputingandcommunicationsworkshops.[s.l.]:IEEE,2007:323-330.

[17]JiangJ,HanG,XuH,etal.LMAT:localizationwithamobileanchornodebasedontrilaterationinwirelesssensornetworks[C]//Globaltelecommunicationsconference.[s.l.]:IEEE,2011:1-6.

A Path Planning Method of Aerial Beacon Assisted Localization in Three-dimensional Wireless Sensor Network

TAN Zhong-hua,XU Yu

(College of Physics and Electronic Information Engineering,Wenzhou University, Wenzhou 325035,China)

Three-dimensional localization methods play a major role in many WSN applications but usually have high complexity and cost.The method based on mobile (aerial) beacon assisted three-dimensional localization is relatively cost-saving.Path planning for mobile is the fundamental problem for that.A novel three-dimensional mobile planning method is proposed,which is simple implementation and short path.The method is based on the basic requirements of the travel path for three-dimensional localization,and just two-dimensional scanning at two planes of the three-dimensional deployment area.3D SCAN,3D DOUBLE SCAN,3D HILBERT,3D CIRCLES,3D S-CURVES and 3D LMAT are typical implementation of that.Simulation shows that the six type of path based on path planning method proposed can meet the requirements of three-dimensional localization,of which 3D S-CURVES has shortest path length and highest positioning accuracy.

3D;wireless sensor network;localization;aerial beacon;path planning

2016-03-03

2016-06-15

時間：2016-11-22

國家自然科學(xué)基金資助項目(61303211)；浙江省自然科學(xué)基金資助項目(LQ13F020010)；溫州大學(xué)研究生創(chuàng)新基金研究項目(3162014038)

譚中華(1990-)，男，研究生，研究方向為無線傳感器網(wǎng)絡(luò)定位；徐 玉,副教授,研究方向為空中飛行機器人與無線傳感網(wǎng)絡(luò)。

http://www.cnki.net/kcms/detail/61.1450.TP.20161122.1228.046.html

TP393

A

1673-629X(2017)01-0134-05

10.3969/j.issn.1673-629X.2017.01.030