多移動信標(biāo)輔助的分布式節(jié)點(diǎn)定位方法

崔煥慶，王英龍，郭強(qiáng)，呂家亮

(1. 山東科技大學(xué) 信息科學(xué)與工程學(xué)院，山東 青島 266590；2. 山東省計算機(jī)網(wǎng)絡(luò)重點(diǎn)實(shí)驗(yàn)室 山東省計算中心，山東 濟(jì)南 250014)

1 引言

通過在目標(biāo)區(qū)域部署大量傳感器節(jié)點(diǎn)，可以實(shí)現(xiàn)諸如軍事防御、目標(biāo)跟蹤、環(huán)境監(jiān)測、空間探索、醫(yī)療衛(wèi)生等諸多應(yīng)用。對于大多數(shù)應(yīng)用，位置信息可使感知數(shù)據(jù)獲得地理意義；位置信息還可輔助進(jìn)行無線傳感器網(wǎng)絡(luò)的路由、拓?fù)涔芾淼?，因此，定位成為無線傳感器網(wǎng)絡(luò)的關(guān)鍵技術(shù)之一[1]。

無線傳感器網(wǎng)絡(luò)的定位包含網(wǎng)絡(luò)節(jié)點(diǎn)定位和外部目標(biāo)定位2類問題，前者是后者的基礎(chǔ)。節(jié)點(diǎn)定位即通過一定的技術(shù)、方法和手段獲取無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的絕對或相對位置的過程，可分為基于信標(biāo)和無信標(biāo)的定位方法[1,2]?；谛艠?biāo)的方法需在網(wǎng)絡(luò)中部署若干已知自身位置的信標(biāo)，而后其他節(jié)點(diǎn)，即未知節(jié)點(diǎn)通過測量到信標(biāo)的距離、角度等信息進(jìn)行定位。無信標(biāo)的方法利用節(jié)點(diǎn)間的相互關(guān)系，各節(jié)點(diǎn)以自身為參考點(diǎn)建立相對坐標(biāo)。使用基于信標(biāo)比無信標(biāo)的方法能得到更高的定位精度，而且信標(biāo)越多，定位精度越高，但是信標(biāo)比未知節(jié)點(diǎn)的成本要高很多。使用移動信標(biāo)進(jìn)行定位既能達(dá)到基于固定信標(biāo)定位方法的精度，又可降低網(wǎng)絡(luò)成本和能耗，成為當(dāng)前的研究熱點(diǎn)。一般而言，移動信標(biāo)輔助定位方法包含如下階段。

1) 信標(biāo)沿著一定的路徑遍歷整個網(wǎng)絡(luò)部署區(qū)域，并同時廣播數(shù)據(jù)分組。將每個廣播消息的信標(biāo)位置稱為虛擬信標(biāo)。

2) 未知節(jié)點(diǎn)接收虛擬信標(biāo)信息，并存儲在一個虛擬信標(biāo)信息表中。

3) 未知節(jié)點(diǎn)利用所記錄的信息估算位置。

一個未知節(jié)點(diǎn)至少需要接收到 3個非共線（二維）或者4個非共面（三維）虛擬信標(biāo)信息，才可實(shí)現(xiàn)定位，因此使用一個移動信標(biāo)的定位方法需要信標(biāo)多次經(jīng)過一個未知節(jié)點(diǎn)。本文提出一種多個移動信標(biāo)輔助的定位方法，同一時刻可產(chǎn)生多個虛擬信標(biāo)，那么每個未知節(jié)點(diǎn)便可實(shí)現(xiàn)一次性定位。

2 相關(guān)工作

使用移動信標(biāo)進(jìn)行定位的最簡單方法就是在信標(biāo)移動過程中，隨機(jī)停留在某些位置并放置一個普通的傳感器節(jié)點(diǎn)，或者直接將移動信標(biāo)位置作為離它最近的未知節(jié)點(diǎn)的位置，再把這些節(jié)點(diǎn)看作固定信標(biāo)，輔助其他節(jié)點(diǎn)的定位。如移動信標(biāo)輔助的DV-Hop定位方法[3]利用移動信標(biāo)產(chǎn)生固定信標(biāo)，接著用DV-Hop方法實(shí)現(xiàn)定位。這種方法需要進(jìn)行迭代計算，誤差較大，而且轉(zhuǎn)換為固定信標(biāo)的節(jié)點(diǎn)能量消耗較快。因此，絕大多數(shù)的移動信標(biāo)輔助定位方法利用移動信標(biāo)產(chǎn)生虛擬信標(biāo)，以輔助未知節(jié)點(diǎn)定位。

與使用固定信標(biāo)的定位方法相同，移動信標(biāo)輔助定位方法可分為基于測距和無需測距的定位方法?；跍y距的方法需測量未知節(jié)點(diǎn)與虛擬信標(biāo)之間的距離。Zhang等[4]提出使用 TDoA（time difference of arrival）測距，而后使用三邊測量法估算位置的方法。Zhong 等[5]提出根據(jù)聲波能量與傳播距離的關(guān)系及來自不同虛擬信標(biāo)的能量來估算未知節(jié)點(diǎn)的位置，并采用中垂線策略、速度調(diào)整策略和虛擬排斥力策略提高定位性能。根據(jù)節(jié)點(diǎn)之間的鄰接關(guān)系，MBL(ndc)（mobile beacon-assisted localization algorithm based on network-density clustering）算法[6]首先對未知節(jié)點(diǎn)進(jìn)行分簇，在每個簇內(nèi)獲得各個未知節(jié)點(diǎn)相對坐標(biāo)，接著利用移動信標(biāo)對簇頭節(jié)點(diǎn)進(jìn)行定位，而后便可定位其他節(jié)點(diǎn)。Kim等[7]還給出了采用加權(quán)最小二乘法提高使用移動信標(biāo)時測距精度的方法。

無需測距的定位方法可以用（加權(quán)）質(zhì)心算法計算位置。如 MACL（mobile anchor centroid localization）算法[8]中，未知節(jié)點(diǎn)取所接收到的虛擬信標(biāo)的位置平均值為自己的位置，陳娟等[9]則使用加權(quán)質(zhì)心算法。ADO（arrival and departure overlap）算法[10]利用未知節(jié)點(diǎn)進(jìn)入和離開移動信標(biāo)通信范圍的交叉部分構(gòu)成ADO區(qū)域，再求取HADO（half ADO）的質(zhì)心作為未知節(jié)點(diǎn)的位置。Lee等[11]選擇3個虛擬信標(biāo)，使用其中2個構(gòu)建交叉區(qū)域，再用第3個計算未知節(jié)點(diǎn)位置。MBB（mobile bounding box）算法[12]使用正方形近似表示信標(biāo)通信區(qū)域，對網(wǎng)絡(luò)進(jìn)行網(wǎng)格劃分后，信標(biāo)沿網(wǎng)格頂點(diǎn)移動，未知節(jié)點(diǎn)利用接收的虛擬信標(biāo)的位置平均值作為位置估計值。RROI（radiate region of intersection）算法[13]需移動信標(biāo)帶有定向天線，以多個虛擬信標(biāo)波束交叉區(qū)域的質(zhì)心作為未知節(jié)點(diǎn)的估計位置。史清江等[14]使用多功率移動信標(biāo)為每個未知節(jié)點(diǎn)構(gòu)造不等式約束，再使用凸規(guī)劃算法求解位置，Chen等[15]給出了在有障礙物的場景中使用該方法時的改進(jìn)措施。

利用移動信標(biāo)也可確定多條通過未知節(jié)點(diǎn)的直線，取它們的交點(diǎn)作為估計位置。PI（perpendicular intersection）算法[16]要求信標(biāo)沿三角形移動，將 2條邊上具有最大RSS（received signal strength）值的點(diǎn)看作未知節(jié)點(diǎn)在邊上的投影點(diǎn)，取通過這2個點(diǎn)的垂線交點(diǎn)為未知節(jié)點(diǎn)的位置。MAP（mobile anchor positioning）算法[17]以最初進(jìn)入和最后離開的虛擬信標(biāo)通信區(qū)域的交點(diǎn)作為2個候選位置，再使用已定位鄰居節(jié)點(diǎn)或其他虛擬信標(biāo)確定可行位置。使用攜帶定向天線的移動信標(biāo)，未知節(jié)點(diǎn)可選擇最初進(jìn)入和最后離開的虛擬信標(biāo)的2個邊界線交點(diǎn)[13]，或2個最大RSS值對應(yīng)的定向波束的中線交點(diǎn)作為估計位置[18]。Ou等[19]提出的方法需要攜帶定向天線的信標(biāo)沿直線運(yùn)動，未知節(jié)點(diǎn)維護(hù)一個按照接收時間排列的虛擬信標(biāo)列表，取居中的虛擬信標(biāo)作為自己的位置。

上述算法都是確定性的，也有學(xué)者提出了概率性算法。Caballero等[20]提出了在三維室外環(huán)境下基于測距的粒子濾波定位方法。MBL[21]算法使用分布式的概率算法給出未知節(jié)點(diǎn)可能位于的區(qū)域及該估計的可能性。A-MBL（adapting MBL）[21]算法在MBL算法的基礎(chǔ)上調(diào)整估計過程中抽樣集合的規(guī)模和動態(tài)模型的參數(shù)，SA-MBL（self-adapting MBL）[22]算法在保證A-MBL算法精度的前提下，給出了判斷達(dá)到定位穩(wěn)定狀態(tài)的方法，從而提高了算法的靈活性。Huang等[23]提出由信標(biāo)使用蒙特卡羅抽樣方法來估算未知節(jié)點(diǎn)位置。

使用多個移動信標(biāo)可提高定位性能。虛擬尺[24]方法將2個信標(biāo)置于長度固定的車輛上，移動期間測量未知節(jié)點(diǎn)對之間的距離，然后使用集中或分布式算法計算未知節(jié)點(diǎn)位置，該方法需要移動信標(biāo)定向發(fā)射超聲波信號，適用于室內(nèi)場景。張正勇等[25]將9個移動信標(biāo)構(gòu)成一個圓形，未知節(jié)點(diǎn)通過比較來自不同信標(biāo)的RSS值確定可行區(qū)域，并取該區(qū)域的質(zhì)心作為其估計位置。Patro等[26]使用 4個移動信標(biāo)在未知節(jié)點(diǎn)周圍構(gòu)成一個正方形，未知節(jié)點(diǎn)取正方形的質(zhì)心作為位置估計值。由于正三角形可完整覆蓋一個平面，Zhang等[27]使用由3個信標(biāo)構(gòu)成的GMAN（group of mobile anchor nodes）遍歷網(wǎng)絡(luò)部署區(qū)域，未知節(jié)點(diǎn)根據(jù)RSS求出自己所在的3條直線，取其交點(diǎn)為自身位置估計值。該方法需選擇來自不同信標(biāo)的相同RSS值，而RSS受各種環(huán)境因素影響較大，部分未知節(jié)點(diǎn)可能無法接收到來自不同信標(biāo)的相同RSS。這些方法都沒有探討移動信標(biāo)的路徑規(guī)劃問題。

本文針對室外二維傳感器網(wǎng)絡(luò)，提出基于TDoA測距的3個移動信標(biāo)輔助的定位方法，以實(shí)現(xiàn)高精度定位；探討了信標(biāo)移動路徑規(guī)劃方法，以覆蓋整個網(wǎng)絡(luò)部署區(qū)域。在下文中，假定s是一個未知節(jié)點(diǎn)，且估計位置為 (,)，真實(shí)位置為(xs,ys)；信標(biāo)Bi(i=1, 2, 3)的坐標(biāo)為Bi(xi, yi)，且傳輸范圍是半徑為R的圓。

3 3個移動信標(biāo)輔助的定位方法

3.1 信標(biāo)的位置關(guān)系

3個信標(biāo)可以在一條直線上，也可構(gòu)成一個三角形。如果3個信標(biāo)在一條直線上（如圖1(a)所示），那么即使未知節(jié)點(diǎn)同時接收到3個信標(biāo)的信息，也不能實(shí)現(xiàn)定位；如果3個信標(biāo)構(gòu)成邊長大于R的三角形（如圖1(b)所示），那么它們的交叉區(qū)域會很小，每個時刻可定位的未知節(jié)點(diǎn)個數(shù)就會很少；如果 3個信標(biāo)構(gòu)成邊長小于 R的三角形（圖 1(c)），信標(biāo)兩兩之間會產(chǎn)生較大的信號干擾。因此將3個信標(biāo)排列成邊長為R的等邊三角形（如圖2所示），這也是文獻(xiàn)[27]所使用的位置關(guān)系。

圖1 3個信標(biāo)之間的位置關(guān)系

如圖2示，設(shè)3個信標(biāo)按順時針序排列，它們的通信區(qū)域有6個交點(diǎn)，其中，3個交點(diǎn)即3個信標(biāo)，另3個記為A1、A2和A3。顯然，位于ΔB1B2B3內(nèi)的未知節(jié)點(diǎn)可同時接收到來自3個信標(biāo)的信息而實(shí)現(xiàn)定位。如果未知節(jié)點(diǎn)只能接收到2個信標(biāo)發(fā)送的消息，則必位于ΔB1B2A1、ΔB1B3A3和ΔB3B2A2之一的內(nèi)部，也可實(shí)現(xiàn)定位。因此，只要一個未知節(jié)點(diǎn)能夠接收到至少2個信標(biāo)同一時刻發(fā)送的信息，便可實(shí)現(xiàn)定位。

信標(biāo)在遍歷網(wǎng)絡(luò)部署區(qū)域時保持相對位置不變，并同時發(fā)送數(shù)據(jù)分組。

圖2 3個信標(biāo)形成等邊三角形

3.2 定位方法

RSS是一種常用的測距方法，實(shí)現(xiàn)簡單，成本低，但實(shí)際環(huán)境中的溫度、多徑效應(yīng)等使其精確度較差，可能產(chǎn)生最大50%的測距誤差[28]。TDoA測距技術(shù)通常使用超聲波/聲波和射頻信號之間的速度差測距，精度高，但是受限于LOS（line of sight），且超聲波/聲波的傳播距離有限。考慮到移動信標(biāo)通常攜帶GPS（global positioning system）以獲取絕對坐標(biāo)，而GPS也可實(shí)現(xiàn)精確測距時，本文使用另一種TDoA技術(shù)進(jìn)行測距。如圖3所示，發(fā)射節(jié)點(diǎn)在時刻t1發(fā)射速度為v的射頻信號，接收節(jié)點(diǎn)在t2時刻接收到信息后，立即回復(fù)一個射頻信號，發(fā)射節(jié)點(diǎn)在時刻t3接收到回復(fù)信號，可計算出兩者之間的距離d為

圖3 TDoA測距示意

這種方法在不增加網(wǎng)絡(luò)中普通傳感器節(jié)點(diǎn)成本的前提下，可實(shí)現(xiàn)較高精度的測距。

設(shè)di(i=1,2,3)是s與Bi之間的距離，即

那么，若s測得了到具有相同時間戳的3個虛擬信標(biāo)的距離，可使用三邊測量法進(jìn)行定位。若 s僅測得2個具有相同時間戳的虛擬信標(biāo)的距離，如圖4所示，設(shè)s測得到B1、B2的距離分別為d1、d2，但未收到同一時刻來自B3的信號，求解式(3)得到2個對稱的位置s和s'，由于s必位于ΔB1B2A1內(nèi)，所以可排除s'，實(shí)現(xiàn)唯一定位。

圖4 s的2種可能位置

最后，取所有時刻計算出的估計位置的平均值作為s的最終估計位置。

算法 1給出了該算法的過程。Beacons()是 3個信標(biāo)執(zhí)行的過程，第7行的條件“finish”有2種可能：一是為定位過程預(yù)設(shè)的運(yùn)行時間消耗完；二是信標(biāo)已經(jīng)遍歷完整個網(wǎng)絡(luò)部署區(qū)域。UnknownNode(s)是未知節(jié)點(diǎn)s要執(zhí)行的過程，變量distList用于記錄所有的虛擬信標(biāo)數(shù)據(jù)分組，第8行的條件“finish receiving packets”也有2種可能：一是按照某種規(guī)則 s進(jìn)入了休眠期，二是信標(biāo)已經(jīng)完成了遍歷，第23行的變量lfinal就是未知節(jié)點(diǎn)的估計位置。

設(shè)3個信標(biāo)實(shí)現(xiàn)了時鐘同步，且廣播測距消息的t1時刻是相同的，并以t1作為發(fā)送距離信息給s時的時間戳。

算法1 多移動信標(biāo)輔助定位算法

輸入：信標(biāo)Bi(i=1,2,3)的初始坐標(biāo)、移動路徑

輸出：網(wǎng)絡(luò)中未知節(jié)點(diǎn)的坐標(biāo)

4 信標(biāo)移動路徑

信標(biāo)移動路徑是決定一跳內(nèi)可定位節(jié)點(diǎn)數(shù)目、定位精度等性能的重要因素，一個好的移動路徑應(yīng)盡可能精確地定位可能多的節(jié)點(diǎn)[29]，還應(yīng)盡量縮短移動路徑以降低成本[30]。假設(shè)網(wǎng)絡(luò)部署區(qū)域是一個(W×L)的矩形，且W和L可分別被 3R和R整除，本文采用如下幾種路徑。

4.1 RWP模型

RWP（random waypoint）模型最早用于在移動通信系統(tǒng)中模擬用戶的移動過程。在移動信標(biāo)輔助定位算法中，也可用于模擬信標(biāo)移動過程[11,21,22,24]。其規(guī)則是：從網(wǎng)絡(luò)部署區(qū)域內(nèi)的任意一個位置開始，隨機(jī)選擇區(qū)域內(nèi)的一個點(diǎn)作為目標(biāo)位置，并隨機(jī)選擇[vmin,vmax]內(nèi)的一個速度，而后按照此速度從起始位置移動到目標(biāo)位置，在移動過程中周期性地發(fā)送數(shù)據(jù)分組。

為使 3個信標(biāo)在移動過程中保持相對位置不變，假定信標(biāo)B1負(fù)責(zé)選擇目標(biāo)位置和移動速度，而B2和B3根據(jù)B1選擇的值以及相對于B1的位置進(jìn)行移動。

4.2 Scan路徑

如圖 5(a)示，Scan路徑[10,14,27,29]由多段平行直線組成。為使網(wǎng)絡(luò)中的每個未知節(jié)點(diǎn)至少被ΔB1B2B3覆蓋一次，將區(qū)域的左右邊界分別擴(kuò)展=/2l R 。設(shè)信標(biāo)的移動速度為 v，如圖 6(a)所示，當(dāng)v＞R時，陰影部分的未知節(jié)點(diǎn)將無法實(shí)現(xiàn)定位。如圖6(b)所示，當(dāng)Scan路徑中相鄰2條平行直線的間距（稱為Scan路徑的分辨率）時，上下相鄰直線之間沒有空隙。因此，取 v≤R且，可定位部署區(qū)域內(nèi)的所有節(jié)點(diǎn)。

圖5 3種移動路徑

圖6 移動路徑的覆蓋情況

4.3 STC和LTC路徑

李石堅(jiān)等[30]指出，三重覆蓋可保證網(wǎng)絡(luò)部署區(qū)域的任意位置都可接收到至少3個信標(biāo)信號，并使用等距三重優(yōu)化覆蓋研究了單個移動信標(biāo)輔助定位時的最佳路徑問題。由于等距三重優(yōu)化覆蓋中，各位置點(diǎn)構(gòu)成等邊三角形，而本文提出的算法中的3個移動信標(biāo)恰好也構(gòu)成一個等邊三角形，從而可設(shè)計出最佳路徑。

若形成等距三重優(yōu)化覆蓋的三角形是ΔB1B2B3（圖 5(b)所示），稱此時的移動信標(biāo)路徑為STC（small triangle coverage）。若形成等距三重優(yōu)化覆蓋的三角形是ΔA1A2A3（圖 5(c)所示），稱此時的移動信標(biāo)路徑為 LTC（large triangle coverage）。圖 5(c)中實(shí)心圓代表 B1、B2、B3位置，而空心圓表示A1、A2、A3位置。

如圖7(a)示，為使3個信標(biāo)在STC路徑中保持正三角形，從最左側(cè)上ΔB1B2B3開始，B1移動到對稱于線段 B2B3的位置，形成下ΔB3B2B1；接著，B2移動到對稱于線段 B1B3的位置，形成上ΔB3B1B2；隨后，B3移動到對稱于線段 B1B2的位置，形成下ΔB2B1B3；這樣 B1、B2、B3不斷逐個輪流移動，便可實(shí)現(xiàn)STC路徑?？梢姡谠撀窂降?個相鄰三角形間，一個信標(biāo)關(guān)于公共邊對稱，需移動 3R的距離，另2個信標(biāo)不移動。每段平行于x軸的路徑由個ΔB1B2B3組成，共段，所以其路徑長度為

如圖 7(b)所示，為實(shí)現(xiàn) LTC路徑，從最左側(cè)下ΔB2B1B3開始，B3和B1輪流水平移動，B2輪流沿斜率為1和-1的直線向上和向下移動。因此在2個相鄰ΔA1A2A3間，B2移動距離為 3R，B1與B3移動距離之和為 2R。每段平行于 x軸的路徑由個ΔA1A2A3組成，共段，所以其路徑長度為

圖7 相鄰三角形位置變換

STC和LTC路徑的長度均與R無關(guān)，僅取決于W和L，而且STC路徑比LTC更短。

5 性能評價

本節(jié)將本文提出的算法（簡記為TMBL）與使用單個移動信標(biāo)的三邊測量法（簡記為TRI）、文獻(xiàn)[25]的方法（簡記為 NINE）、文獻(xiàn)[26]的方法（簡記為FOUR）和文獻(xiàn)[27]的算法（簡記為GMAN）進(jìn)行對比，以分析其性能。移動信標(biāo)輔助定位方法應(yīng)以盡可能短的信標(biāo)移動路徑、盡可能高的精度定位盡可能多的未知節(jié)點(diǎn)，因此從以下3方面分析算法的性能。

1) 可定位節(jié)點(diǎn)數(shù)。指在信標(biāo)一跳范圍內(nèi)可被定位的未知節(jié)點(diǎn)數(shù)量，反映了移動信標(biāo)路徑的覆蓋情況。

2) 定位誤差。僅對可定位節(jié)點(diǎn)的誤差進(jìn)行分析，定位誤差定義為[14]

其中，N是可定位節(jié)點(diǎn)的個數(shù)。

3) 信標(biāo)移動路徑長度。指所有移動信標(biāo)在定位期間移動路徑的總長度。

采用MATLAB 7.0對上述各種算法進(jìn)行仿真實(shí)驗(yàn)。設(shè)定網(wǎng)絡(luò)部署區(qū)域是(173×100)m2的矩形區(qū)域，有200個未知節(jié)點(diǎn)均勻分布于區(qū)域內(nèi)。移動信標(biāo)的傳輸半徑是各向?qū)ΨQ的，即其通信范圍是一個圓形。設(shè)信標(biāo)通信半徑R=5m、10m、20m和25m，分別考察不同R下的定位性能。假設(shè)TMBL與TRI均采用 3.2節(jié)中所提出的測距方法，測距誤差是10%。未知節(jié)點(diǎn)s與第i個虛擬信標(biāo)之間的測量距離 ?sid 服從均值為真實(shí)距離dsi、標(biāo)準(zhǔn)差為0.1dsi的正態(tài)分布。GMAN和NINE所使用的RSS采用不考慮任何干擾的理想模型。

對于RWP模型，取vmin=1m/s，vmax=Rm/s，信標(biāo)每隔 1s廣播一次數(shù)據(jù)分組，運(yùn)行時間分別取1～10min各10種情況。對于Scan路徑，取信標(biāo)移動速度v=0.5Rm/s，分辨率，每隔1s廣播一次數(shù)據(jù)分組。所有定位結(jié)果均取5次運(yùn)行結(jié)果的平均值進(jìn)行比較。

5.1 RWP模型

因?yàn)槲墨I(xiàn)[27]的GMAN算法需采用Scan路徑，所以這里比較另外4種方法。

RWP模型通常無法覆蓋整個網(wǎng)絡(luò)部署區(qū)域[24]，部分未知節(jié)點(diǎn)無法接收到信標(biāo)信息，所以4種方法都無法定位全部未知節(jié)點(diǎn)。4種方法的可定位節(jié)點(diǎn)數(shù)如圖8所示。隨著運(yùn)行時間和R的增加，4種算法的可定位節(jié)點(diǎn)數(shù)均增加。在R和運(yùn)行時間相同情況下，TMBL和NINE最多，F(xiàn)OUR次之，TRI的可定位節(jié)點(diǎn)數(shù)最少。在R=25m，運(yùn)行 10min后，TMBL可定位98.7%的節(jié)點(diǎn)，NINE可定位96.2%的節(jié)點(diǎn)，而FOUR和TRI分別可定位77%和32.7%的節(jié)點(diǎn)。

4種算法的平均定位誤差如表1所示，TRI的誤差最大，F(xiàn)OUR和NINE次之，TMBL的誤差最小。不同的R值下，TMBL的平均定位誤差都在6%左右，約為FOUR和NINE的31%、TRI的12%。

圖8 RWP模型下的可定位節(jié)點(diǎn)數(shù)

表1 RWP模型下的平均定位誤差/%

5.2 Scan路徑

TMBL使用給定參數(shù)的 Scan路徑可定位全部節(jié)點(diǎn)，但另外4種算法無法定位全部節(jié)點(diǎn)（見表2），可見這些算法不能覆蓋全部的網(wǎng)絡(luò)部署區(qū)域。

表2 Scan路徑下的可定位節(jié)點(diǎn)數(shù)

表3給出了采用Scan路徑時的平均定位誤差，其中GMAN的誤差最大，TRI、FOUR和NINE的次之，TMBL的誤差最小。此外，TMBL算法在Scan路徑下的定位誤差略小于RWP模型下的誤差。

表3 Scan路徑下的平均定位誤差/%

5.3 STC和LTC路徑

移動信標(biāo)只有在到達(dá)新位置后才發(fā)送數(shù)據(jù)分組。這2種路徑僅適用于TMBL算法，可定位全部未知節(jié)點(diǎn)。2種路徑下的平均定位誤差如表4所示，由于LTC使用ΔA1A2A3作為掃描三角形，其面積要大于ΔB1B2B3，所以其誤差要比STC大。

表4 STC和LTC路徑的平均定位誤差/%

5.4 路徑長度

在W和L一定的情況下，使用同一種路徑時，信標(biāo)路徑總長度與信標(biāo)個數(shù)成正比。

RWP的路徑長度與 R無關(guān)，但隨著運(yùn)行時間的增加而接近線性增長（如圖9所示），當(dāng)運(yùn)行10min時，3個信標(biāo)移動超過21 000m的距離；隨著信標(biāo)個數(shù)增加，信標(biāo)路徑總長度隨之增長。

圖9 RWP路徑長度

如圖10所示，Scan路徑長度是關(guān)于變量R的減函數(shù)，當(dāng)R=5m時，3個信標(biāo)移動距離約為37 500m，當(dāng)R=25m時，其距離約為8 500m。在R相同的情況下，路徑長度與信標(biāo)個數(shù)成正比。

圖10 Scan路徑長度

在給定的W和L取值下，STC與LTC的路徑長度是一個常數(shù)，分別約為865m和892m，LTC比STC約長0.26Lm。

綜上，TMBL算法在各種路徑下的平均定位誤差最小，而且TMBL算法在STC路徑下的平均定位誤差小于RWP模型、Scan路徑和LTC路徑下的定位誤差。同時，STC路徑的長度最短。因此采用STC路徑的TMBL算法具有最佳性能。

6 結(jié)束語

移動信標(biāo)輔助定位方法使用移動信標(biāo)在遍歷網(wǎng)絡(luò)部署區(qū)域過程中產(chǎn)生的虛擬信標(biāo)代替固定信標(biāo)，保證了定位精度，同時降低了定位成本。本文提出了一種基于3個移動信標(biāo)和TDoA測距技術(shù)在二維環(huán)境下的定位算法，并給出了4種移動路徑規(guī)劃方法。實(shí)驗(yàn)表明，在使用同一移動路徑時，本文所給出的方法比使用單一移動信標(biāo)的三邊測量法以及文獻(xiàn)[25,26,27]提出的方法具有更好的性能。根據(jù)等距三重最優(yōu)覆蓋策略設(shè)計的STC路徑可以覆蓋整個網(wǎng)絡(luò)部署區(qū)域，其長度僅與區(qū)域大小有關(guān)，長度最短，而且使用該路徑與使用 Scan路徑的定位精度大致相同，高于使用LTC路徑的定位精度。

下一步，將著重研究使用多個移動信標(biāo)在三維場景以及非理想（如存在障礙物、非理想傳輸范圍）情況下的定位問題。

[1] LIU Y,YANG Z,WANG X,et al. Location, localization, and localizability[J].Journal of Computer Science and Technology, 2010,25(2): 274-297.

[2] WANG J, GHOSH R, DAS S. A survey on sensor localization[J].Journal of Control Theory and Applications, 2010, 8(1): 2-11.

[3] 姚忠孝, 俞立, 董齊芬.基于移動信標(biāo)的 DV-Hop無線傳感器網(wǎng)絡(luò)定位算法[J]. 傳感技術(shù)學(xué)報,2009,22(10):1504-1509.YAO Z X, YU L, DONG Q F. Beacon-based DV-hop localization algorithm in wireless sensor networks[J]. Chinese Journal of Sensors and Actuators, 2009,22(10): 1504-1509.

[4] ZHANG B, YU F. An energy efficient localization algorithm for wireless sensor networks using a mobile anchor node[A]. Proceedings of IEEE International Conference on Information and Automation[C].Changsha, China, 2008.215-219.

[5] ZHONG Z,LUO D, LIU S,et al. An adaptive localization approach for wireless sensor networks based on gauss-markov mobility model[J].Acta Automatica Sinica,2010, 36(11): 1557-1568.

[6] 趙方, 馬嚴(yán), 羅海勇等. 一種基于網(wǎng)絡(luò)密度分簇的移動信標(biāo)輔助定位方法[J]. 電子與信息學(xué)報, 2009, 31(12): 2988-2992.ZHAO F, MA Y, LUO H Y, et al. A mobile beacon-assisted node localization algorithm using network-density-based clustering for wireless sensor networks[J]. Journal of Electronics and Information Technology, 2009, 31(12): 2988-2992.

[7] KIM E, KIM K. Distance estimation with weighted least squares for mobile beacon-based localization in wireless sensor networks[J]. IEEE Signal Processing Letters,2010, 17(6): 559-562.

[8] HU Z,GU D, SONG Z, et al. Localization in wireless sensor networks using a mobile anchor node[A]. Proceedings of IEEE/ASME International Conference on Advanced Intelligent Mechatronics[C].Xi'An, China, 2008.602- 607.

[9] 陳娟, 李長庚, 寧新鮮. 基于移動信標(biāo)的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位[J]. 傳感技術(shù)學(xué)報,2009,22(1):121-125.CHEN J, LI C, NINIG X. Node Localization of wireless sensor networks based on mobile beacon[J]. Chinese Journal of Sensors and Actuators, 2009, 22(1):121-125.

[10] XIAO B,CHEN H,ZHOU S. Distributed localization using a moving beacon in wireless sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2008,19(5): 587-600.

[11] LEE S,KIM E,KIM C,et al.Localization with a mobile beacon based on geometric constraints in wireless sensor networks[J].IEEE Transactions on Wireless Communications, 2009,8(12):5801-5905.

[12] 石為人, 許磊, 徐揚(yáng)生. 一種基于移動錨節(jié)點(diǎn)的靜態(tài)無線傳感器網(wǎng)絡(luò)定位算法[J].儀器儀表學(xué)報,2007,28(3):385-393.SHI W R, XU L, XU Y S. Localization algorithm with mobile anchor in static wireless sensor network[J]. Chinese Journal of Scientific Instrument, 2007,28(3):385-393.

[13] ZHANG B, YU F. LSWD: localization scheme for wireless sensor networks using directional antenna[J]. IEEE Transactions on Comsumer Electronics, 2010, 56(4): 2208- 2216.

[14] 史清江, 何晨. 多功率移動錨節(jié)點(diǎn)輔助的分布式節(jié)點(diǎn)定位方法[J].通信學(xué)報, 2009,30(10):8-13.SHI Q J, HE C. Multi-power level mobile beacon assisted distributed node localization algorithm[J]. Journal on Communications, 2009,30(10): 8-13.

[15] CHEN H, SHI Q, TAN R, et al.Mobile element assisted cooperative localization for wireless sensor networks with obstacles[J].IEEE Transactions on Wireless Communications, 2010, 9(3): 956-963.

[16] GUO Z, GUO Y, HONG F, et al.Perpendicular intersection: locating wireless sensors with mobile beacon[J]. IEEE Transactions on Vehicular Technology,2010,59(7): 3501- 3509.

[17] LIAO H, LEE C, KEDIA S P. Mobile anchor positioning for wireless sensor networks[J]. IET Communications,2011, 5(7): 914-921.

[18] ZHANG B, YU F. Low-complex energy-efficient localisation algorithm for wireless sensor networks using directional antenna[J].IET Communications,2010, 13(4): 1617-1623.

[19] OU C H. A localization scheme for wireless sensor networks using mobile anchors with directional antennas[J]. IEEE Sensor Journal,2011, 11(7):1607-1616.

[20] CABALLERO F, MERINO L, MAZA I, et al.A particle filtering method for wireless sensor network localization with an aerial robot beacon[A]. Proceedings of IEEE International Conference on Robotics and Automation[C]. Pasadena, USA, 2008. 596-601.

[21] TENG G,ZHENG K,DONG W.Adapting mobile beacon-assisted localization in wireless sensor networks[J]. Sensors, 2009,9(4):2760-2779.

[22] TENG G,ZHENG K,DONG W. An efficient and self-adapting localization in static wireless sensor networks[J]. Sensors, 2009,9(8):6150-6170.

[23] HUANG R,ZARUBA G.V.Monte carlo localization of wireless sensor networks with a single mobile beacon[J]. Wireless Networks, 2009,15(8): 978-990.

[24] DING Y,WANG C,XIAO L.Using mobile beacons to locate sensors in obstructed environments[J]. Journal of Parallel and Distributed Computing, 2010,70(6):644-656.

[25] 張正勇, 孫智, 王剛等. .基于移動錨節(jié)點(diǎn)的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位[J]. 清華大學(xué)學(xué)報(自然科學(xué)版), 2007,47(4):534- 537.ZHANG Z Y, SUN Z, WANG G, et al. Localization in wireless sensor networks with mobile anchor nodes[J]. Journal of Tsinghua University(Sci & Tech), 2007,47(4):534- 537.

[26] PATRO R K. Localization in wireless sensor network with mobile beacons[A].Proceedings of 23rd IEEE Convention of Electrical and Electronics Engineers in Israel[C]. Eliat, Israel, 2004. 22-24.

[27] ZHANG B, YU F, ZHANG Z. Collaborative localization algorithm for wireless sensor networks using mobile anchors[A].Proceedings of 2nd Asia-Pacific Conference on Computational Intelligence and Industrial Applications[C]. Wuhan, China,2009.309-312.

[28] 孫利民, 李建中, 陳渝等. 無線傳感器網(wǎng)絡(luò)[M]. 北京: 清華大學(xué)出版社, 2008.SUN L M, LI J Z, CHEN Y, et al. Wireless Sensor Networks[M].Beijing: Tsinghua University Press, 2008.

[29] KOUTSONIKOLAS D, DAS S M, HU Y C. Path planning of mobile landmarks for localization in wireless sensor networks[J]. Computer Communications, 2007, 30(13): 2577-2592.

[30] 李石堅(jiān),徐從富,楊旸等.面向傳感器節(jié)點(diǎn)定位的移動信標(biāo)路徑獲取[J]. 軟件學(xué)報,2008,19(2):455-467.LI S J, XU C F, YANG Y, et al. Getting mobile beacon path for sensor localization[J]. Journal of Software,2008, 19(2):455- 467.