基于運動軌跡捕捉與正交覆蓋的WSN節(jié)點定位算法

杜 剛,張善文,邱力軍

(1.西京學(xué)院 a.機(jī)電技術(shù)系; b.信息工程學(xué)院,西安 710123;2.空軍軍醫(yī)大學(xué) 生物醫(yī)學(xué)工程系,西安 710012)

0 概述

網(wǎng)絡(luò)節(jié)點定位算法是無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network,WSN)從固定式逐步轉(zhuǎn)向移動式部署過程的核心解決方案之一[1]。固定式WSN中節(jié)點坐標(biāo)是固定不變的,當(dāng)且僅當(dāng)節(jié)點處于失效狀態(tài)時根據(jù)節(jié)點坐標(biāo)進(jìn)行失效節(jié)點的替換[2]。由于移動狀態(tài)下WSN節(jié)點拓?fù)渚嚯x不斷發(fā)生變化,采用固定式WSN中常用的節(jié)點定位算法時需要頻繁進(jìn)行網(wǎng)絡(luò)數(shù)據(jù)通信[3],且需要采用復(fù)雜校驗機(jī)制進(jìn)行定位精度提升,容易因網(wǎng)絡(luò)節(jié)點能量消耗過大而降低網(wǎng)絡(luò)的適用性能[4]。因此,解決移動節(jié)點條件下的WSN節(jié)點定位問題,成為WSN的熱門研究方向[5]。

文獻(xiàn)[6]鑒于當(dāng)前機(jī)制普遍存在拓?fù)涔?jié)點感知延遲度較高、難以適應(yīng)移動節(jié)點的不足,提出一種基于盒式錨區(qū)域捕捉機(jī)制的WSN信號定位算法,采用信號覆蓋重疊域維度裁決的方式,選取覆蓋度最高的節(jié)點作為錨節(jié)點并引入三角定位機(jī)制進(jìn)行信號方位捕捉。該機(jī)制能夠滿足拓?fù)渥儎訔l件下的網(wǎng)絡(luò)信號定位需求，但也存在僅能適應(yīng)節(jié)點稀疏環(huán)境的不足,難以進(jìn)一步在實踐中推廣應(yīng)用。文獻(xiàn)[7]提出一種基于采樣盒-密度映射機(jī)制的WSN信號定位算法,通過捕捉功率譜密度最強(qiáng)的節(jié)點作為錨節(jié)點并在節(jié)點稀疏密度條件下持續(xù)發(fā)揮定位作用,獲得了較高的定位精度。與文獻(xiàn)[6]算法相比,該機(jī)制雖能在節(jié)點稀疏的情況下獲得較好的定位精度,但在節(jié)點密集條件下適應(yīng)度不佳,特別是在高密度環(huán)境下網(wǎng)絡(luò)鏈路抖動嚴(yán)重,具有較大的局限性。針對文獻(xiàn)[6-7]算法難以同時適應(yīng)不同節(jié)點密度環(huán)境的問題,文獻(xiàn)[8]提出了一種基于迭代預(yù)測采樣機(jī)制的WSN信號定位算法,通過引入最小二乘預(yù)測機(jī)制并針對捕捉到的錨節(jié)點進(jìn)行過濾采樣,顯著提高了捕捉成功率,并且能夠適應(yīng)低密度錨節(jié)點的網(wǎng)絡(luò)情況，但該算法由于主要適用于固定節(jié)點條件下的WSN環(huán)境,對拓?fù)渥兓^快的移動式WSN適應(yīng)性較差。

為改善WSN信號定位對高拓?fù)渥兓h(huán)境的適應(yīng)性,提高檢測精度,本文提出一種基于運動軌跡捕捉與正交覆蓋機(jī)制的WSN節(jié)點定位算法。通過覆蓋定位方式選擇性能最優(yōu)的錨節(jié)點進(jìn)行定位,應(yīng)對節(jié)點運動過程中因拓?fù)浣Y(jié)構(gòu)顯著變化導(dǎo)致的鏈路抖動現(xiàn)象。同時基于拉格朗日插值法進(jìn)行運動軌跡捕捉,定量獲取橫向及縱向坐標(biāo)維度,捕捉節(jié)點運動矢量并預(yù)測下一時刻節(jié)點坐標(biāo),將節(jié)點坐標(biāo)精確定位于多個錨節(jié)點所共同決定的覆蓋區(qū)域內(nèi),從而有效提高定位精度。

1 WSN節(jié)點定位算法

本文提出的基于運動軌跡捕捉與正交覆蓋機(jī)制的WSN網(wǎng)絡(luò)信號定位檢測算法過程如圖1所示。

圖1 本文算法流程

本文算法通過以下3個階段實現(xiàn)對WSN網(wǎng)絡(luò)節(jié)點的精確定位:

1)信號發(fā)射測距與覆蓋定位,使算法能夠便捷地獲取錨節(jié)點定位信號,且選取的錨節(jié)點具有明顯的定位優(yōu)勢,可減少因錨節(jié)點失效或信號強(qiáng)度較弱而導(dǎo)致的弱定位現(xiàn)象。

2)基于拉格朗日插值函數(shù)的運動軌跡捕捉方法,獲取節(jié)點坐標(biāo)及速度條件下后能以較高精度進(jìn)行定位預(yù)測,修正節(jié)點的運動矢量,獲取下一時刻節(jié)點運動方位,按時捕捉節(jié)點的運動軌跡。

3)基于過濾機(jī)制的區(qū)域優(yōu)化,引入基于隨機(jī)數(shù)機(jī)制的正交覆蓋方式,在已獲取的捕捉運動軌跡基礎(chǔ)上,對下一時刻節(jié)點所在的坐標(biāo)進(jìn)行精確預(yù)測,可實現(xiàn)覆蓋區(qū)域內(nèi)的精度精確控制。

1.1 信號發(fā)射測距與覆蓋定位

由于WSN節(jié)點均采用射頻方式進(jìn)行數(shù)據(jù)通信,因此實際過程中需要采取一定方式獲取待測節(jié)點與基準(zhǔn)節(jié)點間的物理拓?fù)渚嚯x[9]?？紤]到網(wǎng)絡(luò)覆蓋環(huán)境往往具有復(fù)雜度較高的特性(信號呈現(xiàn)多徑傳輸以及無線鏈路覆蓋范圍內(nèi)存在障礙物等可能),本文采用文獻(xiàn)[9]提出的對數(shù)路徑測距機(jī)制實現(xiàn)對物理拓?fù)渚嚯x的精確測量。首先通過式(1)獲取待測信號的射頻強(qiáng)度R(G,d)。

(1)

其中:P表示W(wǎng)SN節(jié)點信號的設(shè)計發(fā)射強(qiáng)度;G表示W(wǎng)SN節(jié)點發(fā)射信號時內(nèi)部天線的發(fā)射增益;L表示信道噪聲,一般為高斯噪聲,其均值為μ,方差為σ;e表示自然對數(shù);d表示節(jié)點當(dāng)前覆蓋范圍。顯然,當(dāng)有多條路徑時,路徑損耗較小。

在實踐中,式(1)所示模型可以直接通過節(jié)點進(jìn)行計算,當(dāng)僅當(dāng)信道噪聲強(qiáng)度過高時失效。因此,通過該模型可直接獲取當(dāng)前節(jié)點的覆蓋范圍d。由于路徑呈現(xiàn)多條時,節(jié)點接收到的信號會呈現(xiàn)泊松分布特性[10],因此僅需要獲取最大覆蓋范圍即可,如圖2所示。

圖2 節(jié)點覆蓋示意圖

覆蓋范圍d可由式(2)獲取[11]。

(2)

當(dāng)WSN節(jié)點處于移動狀態(tài)時需要就近獲取3個錨節(jié)點,以便能夠準(zhǔn)確獲取自身的坐標(biāo)位置。由于錨節(jié)點處于固定位置,因此僅當(dāng)WSN能夠進(jìn)入圖2所示的覆蓋區(qū)域內(nèi)時,首先通過式(1)接收3個錨節(jié)點的射頻強(qiáng)度,進(jìn)入覆蓋區(qū)域內(nèi)時利用式(3)～式(6)獲取其當(dāng)前區(qū)域估計。

x(low)=min(xi-ri)

(3)

x(high)=max(xi-ri)

(4)

y(low)=min(yi-ri)

(5)

y(high)=max(yi-ri)

(6)

其中:x(low)、x(high)、y(low)、y(high)分別表示圖2中WSN節(jié)點移動過程中對應(yīng)的橫軸與縱軸的邊際值;i取值為1～3,分別表示圖2中3個錨節(jié)點;ri表示定位距離,獲取方式如式(7)所示。

ri=min(Ri,di)

(7)

其中:di表示待測節(jié)點與3個錨節(jié)點之間的覆蓋范圍,可通過式(2)所示模型獲取;Ri表示3個錨節(jié)點中,覆蓋能力最強(qiáng)的錨節(jié)點的覆蓋半徑。

當(dāng)網(wǎng)絡(luò)總體節(jié)點密度較高且節(jié)點移動速度較快時,獲取的定位距離不僅波動范圍較大而且可能處于不斷下降的態(tài)勢,如文獻(xiàn)[10]所提及的100個/m2的節(jié)點密度、移動速度均大于2 m/s的情況。由圖3可知,定位精度隨著節(jié)點運動時間的不斷增加而呈現(xiàn)強(qiáng)烈波動,定位誤差呈現(xiàn)穩(wěn)定性較差的趨勢,顯然網(wǎng)絡(luò)的定位效果也出現(xiàn)了一定的波動,因此，需要采取必要的精度修正措施。

圖3 文獻(xiàn)[10]所述情況下定位誤差隨運動時間的變化

Fig.3 Positioning error varing with the movement time in the case described in literature[10]

1.2 基于拉格朗日插值法的節(jié)點運動軌跡捕捉

文獻(xiàn)[12]采用實踐中常用的大數(shù)據(jù)統(tǒng)計機(jī)制進(jìn)行精度修正,但該機(jī)制也存在著統(tǒng)計復(fù)雜的不足。由于WSN節(jié)點可以通過式(1)直接獲取錨節(jié)點的信號強(qiáng)度,且采取式(2)可便捷計算出與錨節(jié)點的距離,因此在本文算法中,主要是通過拉格朗日插值方式進(jìn)行精度修正。

首先,按圖2所示的覆蓋方法所獲取的WSN節(jié)點坐標(biāo)均為一次性坐標(biāo),即下一時刻WSN節(jié)點坐標(biāo)可能隨著自身運動進(jìn)入新的覆蓋區(qū)域。由于典型的移動無線傳感網(wǎng)節(jié)點均處于低速狀態(tài),移動速率一般不超過4 Mb/s,且覆蓋半徑一般不低于50 m[13],因此可設(shè)在3 s范圍內(nèi)節(jié)點均將處于圖2所示的覆蓋區(qū)域內(nèi)。

假設(shè)節(jié)點在k時刻對應(yīng)的坐標(biāo)為(Xk,Yk),拉格朗日插值函數(shù)L(k)對應(yīng)k時刻的取值。本文算法根據(jù)拉格朗日插值函數(shù)L(k)并通過獲取最近時刻的節(jié)點坐標(biāo)進(jìn)行拉格朗日預(yù)測,以便獲得k+1時刻的精確位置,具體如下[14]:

Xk=L(t)=L1Xk-1+L2Xk-2

(8)

(9)

(10)

(11)

采用式(8)～式(11)所示模型即可便捷地獲取k時刻節(jié)點的橫坐標(biāo)Xk,并可通過相同方式獲取節(jié)點的縱坐標(biāo)Yk:

Yk=F(t)=L1Yk-1+L2Yk-2

(12)

(13)

(14)

(15)

結(jié)合式(7)、式(11)可獲取節(jié)點在k+1時刻的移動速度矢量(vx,vy),獲取方式如下:

(16)

(17)

通過式(15)、式(16)所示模型可精確獲取節(jié)點在k+1時刻的運動速率V:

(18)

由于同一時刻網(wǎng)絡(luò)中運動節(jié)點不唯一,因此通過式(16)～式(17)可獲取到n個節(jié)點全部的移動速度矢量及運動速率。對單一移動節(jié)點而言,本文節(jié)點中最大運動速率為該節(jié)點的初始始運動速率,其絕對值為抽樣區(qū)域,如圖4所示。節(jié)點在通過式(7)～式(14)所示模型精確獲取自身移動速度矢量(vx,yy)及運動速率V后,對抽樣區(qū)域內(nèi)存在的錨節(jié)點進(jìn)行掃描,并按式(3)～式(7)所示模型繼續(xù)進(jìn)行下一時刻的信號發(fā)射測距與覆蓋定位過程。

圖4 抽樣區(qū)域的確定

1.3 基于過濾機(jī)制的區(qū)域優(yōu)化

不妨設(shè)任意2個抽樣樣本為(X1,Y1)、(X2,Y2);按照節(jié)點1、節(jié)點2樣本的橫坐標(biāo)與縱坐標(biāo)劃分正交區(qū)域,引入隨機(jī)正交機(jī)制[15]進(jìn)行正交覆蓋,覆蓋操作見式(19)～式(21),其中,(Xtest,Ytest)為第一步確定的抽樣值,(X,Y)為最終確定的抽樣值,β、α表示隨機(jī)數(shù),取值為0～1,滿足α+β=1,可通過式(13)所示的隨機(jī)算法獲取。正交區(qū)域內(nèi)可獲取多個樣本值,見節(jié)點3～節(jié)點6所處位置。

湖北省63種藥品價格、藥品流通成本現(xiàn)狀調(diào)查與規(guī)范價格政策研究 ……………………………………… 王 競等（8）：1019

Xtest=βX1+αX2

(19)

Ytest=βY1+αY2

(20)

X=βXtest+αXtest

(21)

X=βYtest+αYtest

(22)

常規(guī)算法對節(jié)點在下一時刻的抽樣區(qū)域采取隨機(jī)分布機(jī)制,即隨機(jī)抽取節(jié)點在圖5所示的抽樣區(qū)域中任意位置作為下一時刻的坐標(biāo)[16],具有簡便的優(yōu)勢同時卻降低了定位檢測的精度。

圖5 正交覆蓋示意圖

針對上述不足,本文通過區(qū)域覆蓋范圍調(diào)整的方式優(yōu)化覆蓋范圍,優(yōu)化方式如下:

N=max(L,P(N))

(23)

(24)

其中,L表示節(jié)點密度,d可通過式(2)所示模型獲取,μ表示錨節(jié)點密度,N是定位過程中選取的待測坐標(biāo)個數(shù)。

圖6 基于過濾機(jī)制的區(qū)域優(yōu)化過程

Fig.6Regional optimization process based on filtering

mechanism

區(qū)域優(yōu)化的具體步驟如下:

1)從覆蓋區(qū)域內(nèi)按照式(1)模型的信號強(qiáng)度,逐次獲取N個錨節(jié)點的信號強(qiáng)度,作為覆蓋區(qū)域的錨節(jié)點基礎(chǔ)樣本。

2)選取處于前三個信號強(qiáng)度最大錨節(jié)點的覆蓋區(qū)域內(nèi)的n個待測坐標(biāo),作為待測坐標(biāo)樣本。

3)從第2個步驟選取的n個待測坐標(biāo),隨機(jī)選取2個作為初始樣本值,并轉(zhuǎn)步驟4進(jìn)行正交覆蓋,獲取最新的n個待測坐標(biāo)。

4)結(jié)合式(8)、式(15),選取與基準(zhǔn)位置最接近的坐標(biāo)作為最終定位坐標(biāo),算法結(jié)束。

2 實驗結(jié)果與分析

本文仿真實驗使用NS2仿真環(huán)境[17-18],網(wǎng)絡(luò)區(qū)域為矩形區(qū)域,大小為1 024 m×1 024 m;節(jié)點采取可控移動模式,即能夠預(yù)設(shè)移動路徑;節(jié)點覆蓋半徑不低于64 m;節(jié)點移動速度不超過4 m/s;錨節(jié)點個數(shù)為100個;其余節(jié)點個數(shù)為50個;節(jié)點信號采用LTE-5G制式信號,頻率為2.048 GHz。為突出本文算法的優(yōu)勢,選取超歐里幾何區(qū)域自旋信號檢測機(jī)制[19](Detection Mechanism of Spin Signal in Hypereuclidean Geometry Region,2S-HGR)和拓?fù)淦贫ㄎ槐O(jiān)測機(jī)制[20](Topology Drift Location Monitoring Mechanism,TDLM)進(jìn)行對比。

2.1 移動路徑定位

預(yù)設(shè)節(jié)點移動路徑如下:從坐標(biāo)原點處移至(1 000 m,1 000 m),如圖7所示。顯然,在2種不同的節(jié)點運動速度下,本文算法預(yù)測路徑均與實際路徑較為吻合,2S-HGR機(jī)制與TDLM機(jī)制存在較多的誤預(yù)測情形，說明本文算法采取的運動軌跡捕捉方法具有優(yōu)良的預(yù)測性能,且精度較高。2S-HGR機(jī)制主要通過檢測信號頻率偏移的方式間接進(jìn)行方位角定位,在復(fù)雜的網(wǎng)絡(luò)條件下容易出現(xiàn)較多誤報情形。TDLM機(jī)制由于采用單純的跳數(shù)機(jī)制進(jìn)行軌跡捕捉,其精確度只能精確到節(jié)點一跳范圍以內(nèi),因此定位檢測的精度低于本文算法。

圖7 移動路徑定位實驗結(jié)果

2.2 定位誤差測試

預(yù)設(shè)100個節(jié)點,運動速度均為4 m/s,按照移動路徑定位測試步驟逐秒進(jìn)行定位誤差捕捉,直到節(jié)點全部從坐標(biāo)原點處移至(1 000 m,1 000 m),基準(zhǔn)定位誤差為0,表示與節(jié)點實際移動軌跡之間的拓?fù)渚嚯x為0。圖8顯示了3種不同算法的定位誤差對比。顯然,本文算法的定位誤差要顯著低于對比算法,與節(jié)點基準(zhǔn)定位的匹配度較高。例如,當(dāng)節(jié)點移動距離為200 m時,本文算法的預(yù)測軌跡與實際軌跡之間的誤差(拓?fù)渚嚯x)為-21.767 12 m,而2S-HGR機(jī)制和TDLM機(jī)制的預(yù)測軌跡與實際軌跡之間的拓?fù)渚嚯x分別為102.340 55 m、-208.543 01 m。

圖8 定位誤差比較

為直觀顯示三者的定位誤差,本文統(tǒng)計了10個位置的誤差數(shù)據(jù),結(jié)果見表1。由表中數(shù)據(jù)可以發(fā)現(xiàn),對于任意一個位置,本文算法的定位誤差始終是最小的,最大定位誤差僅為-26.506 73 m,而2S-HGR機(jī)制、TDLM機(jī)制的最大誤差分別達(dá)到154.300 76 m和-246.284 38 m。可見,本文算法的定位誤差要顯著低于對比算法,與節(jié)點基準(zhǔn)定位的匹配度較高,說明本文算法采取的基于過濾機(jī)制的區(qū)域優(yōu)化方法能夠較好地降低定位誤差,特別本文采用的正交覆蓋方式可優(yōu)化定位坐標(biāo)在區(qū)域內(nèi)的分布,有效防止因信道噪聲的干擾而導(dǎo)致信號弱定位的情形,同時也說明本文算法采取的機(jī)制優(yōu)于2S-HGR機(jī)制及TDLM機(jī)制中采用的信號頻率偏移及跳數(shù)預(yù)測方式。

表1 定位誤差實驗數(shù)據(jù)Table 1 Experimental results of location error m

2.3 坐標(biāo)定位精度

預(yù)設(shè)20個節(jié)點,運動速度均為4 m/s,錨節(jié)點個數(shù)為20,節(jié)點沿著錨節(jié)點運動,逐個捕捉節(jié)點坐標(biāo),并與本文算法、2S-HGR機(jī)制及TDLM機(jī)制的定位精度進(jìn)行對比,由圖9可知本文算法坐標(biāo)定位精度較高,與錨節(jié)點的距離均保持在4 m以內(nèi),存在離散的情況較少,且相當(dāng)一部分節(jié)點的坐標(biāo)與實際位置高度重合,說明本文算法通過信號發(fā)射測距與覆蓋定位技術(shù)、基于拉格朗日插值方法的運動軌跡捕捉方法,以及基于過濾機(jī)制的區(qū)域優(yōu)化方法,能夠精確捕捉節(jié)點運動軌跡及坐標(biāo),這主要是由于本文算法能夠?qū)?jié)點運動速度進(jìn)行實時捕捉,完成捕捉過程后可使用正交覆蓋的方式對獲取的節(jié)點坐標(biāo)進(jìn)行精度提升,因此坐標(biāo)精度較高,其較2S-HGR機(jī)制采取的頻移檢測方式及TDLM機(jī)制采取的跳數(shù)檢測機(jī)制具有明顯優(yōu)勢。

圖9 坐標(biāo)定位結(jié)果比較

3 結(jié)束語

為提高移動WSN網(wǎng)絡(luò)節(jié)點定位精度,本文提出一種基于運動軌跡捕捉與正交覆蓋機(jī)制的節(jié)點定位算法,通過捕捉性能最優(yōu)錨節(jié)點的方式應(yīng)對拓?fù)浣Y(jié)構(gòu)變動時鏈路抖動的情況,實現(xiàn)對節(jié)點運動矢量及坐標(biāo)的精確捕捉,動態(tài)獲取節(jié)點運動軌跡。下一步將針對WSN網(wǎng)絡(luò)節(jié)點定位過程中難以實時捕捉網(wǎng)絡(luò)整體拓?fù)浣Y(jié)構(gòu)的問題,引入超歐里幾何拓?fù)溆成錂C(jī)制,并采用區(qū)域映射算法將復(fù)雜拓?fù)浣Y(jié)構(gòu)轉(zhuǎn)化為平面拓?fù)浣Y(jié)構(gòu),進(jìn)一步提高本文算法對移動WSN的適應(yīng)性。