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

杜 剛,張善文,邱力軍

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

0 概述

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

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

為改善WSN信號定位對高拓撲變化環境的適應性,提高檢測精度,本文提出一種基于運動軌跡捕捉與正交覆蓋機制的WSN節點定位算法。通過覆蓋定位方式選擇性能最優的錨節點進行定位,應對節點運動過程中因拓撲結構顯著變化導致的鏈路抖動現象。同時基于拉格朗日插值法進行運動軌跡捕捉,定量獲取橫向及縱向坐標維度,捕捉節點運動矢量并預測下一時刻節點坐標,將節點坐標精確定位于多個錨節點所共同決定的覆蓋區域內,從而有效提高定位精度。

1 WSN節點定位算法

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

圖1 本文算法流程

本文算法通過以下3個階段實現對WSN網絡節點的精確定位:

1)信號發射測距與覆蓋定位,使算法能夠便捷地獲取錨節點定位信號,且選取的錨節點具有明顯的定位優勢,可減少因錨節點失效或信號強度較弱而導致的弱定位現象。

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

3)基于過濾機制的區域優化,引入基于隨機數機制的正交覆蓋方式,在已獲取的捕捉運動軌跡基礎上,對下一時刻節點所在的坐標進行精確預測,可實現覆蓋區域內的精度精確控制。

1.1 信號發射測距與覆蓋定位

由于WSN節點均采用射頻方式進行數據通信,因此實際過程中需要采取一定方式獲取待測節點與基準節點間的物理拓撲距離[9]?？紤]到網絡覆蓋環境往往具有復雜度較高的特性(信號呈現多徑傳輸以及無線鏈路覆蓋范圍內存在障礙物等可能),本文采用文獻[9]提出的對數路徑測距機制實現對物理拓撲距離的精確測量。首先通過式(1)獲取待測信號的射頻強度R(G,d)。

(1)

其中:P表示WSN節點信號的設計發射強度;G表示WSN節點發射信號時內部天線的發射增益;L表示信道噪聲,一般為高斯噪聲,其均值為μ,方差為σ;e表示自然對數;d表示節點當前覆蓋范圍。顯然,當有多條路徑時,路徑損耗較小。

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

圖2 節點覆蓋示意圖

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

(2)

當WSN節點處于移動狀態時需要就近獲取3個錨節點,以便能夠準確獲取自身的坐標位置。由于錨節點處于固定位置,因此僅當WSN能夠進入圖2所示的覆蓋區域內時,首先通過式(1)接收3個錨節點的射頻強度,進入覆蓋區域內時利用式(3)～式(6)獲取其當前區域估計。

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節點移動過程中對應的橫軸與縱軸的邊際值;i取值為1～3,分別表示圖2中3個錨節點;ri表示定位距離,獲取方式如式(7)所示。

ri=min(Ri,di)

(7)

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

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

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

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

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

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

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

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

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

(8)

(9)

(10)

(11)

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

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

(12)

(13)

(14)

(15)

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

(16)

(17)

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

(18)

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

圖4 抽樣區域的確定

1.3 基于過濾機制的區域優化

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

湖北省63種藥品價格、藥品流通成本現狀調查與規范價格政策研究 ……………………………………… 王 競等（8）：1019

Xtest=βX1+αX2

(19)

Ytest=βY1+αY2

(20)

X=βXtest+αXtest

(21)

X=βYtest+αYtest

(22)

常規算法對節點在下一時刻的抽樣區域采取隨機分布機制,即隨機抽取節點在圖5所示的抽樣區域中任意位置作為下一時刻的坐標[16],具有簡便的優勢同時卻降低了定位檢測的精度。

圖5 正交覆蓋示意圖

針對上述不足,本文通過區域覆蓋范圍調整的方式優化覆蓋范圍,優化方式如下:

N=max(L,P(N))

(23)

(24)

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

圖6 基于過濾機制的區域優化過程

Fig.6Regional optimization process based on filtering

mechanism

區域優化的具體步驟如下:

1)從覆蓋區域內按照式(1)模型的信號強度,逐次獲取N個錨節點的信號強度,作為覆蓋區域的錨節點基礎樣本。

2)選取處于前三個信號強度最大錨節點的覆蓋區域內的n個待測坐標,作為待測坐標樣本。

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

4)結合式(8)、式(15),選取與基準位置最接近的坐標作為最終定位坐標,算法結束。

2 實驗結果與分析

本文仿真實驗使用NS2仿真環境[17-18],網絡區域為矩形區域,大小為1 024 m×1 024 m;節點采取可控移動模式,即能夠預設移動路徑;節點覆蓋半徑不低于64 m;節點移動速度不超過4 m/s;錨節點個數為100個;其余節點個數為50個;節點信號采用LTE-5G制式信號,頻率為2.048 GHz。為突出本文算法的優勢,選取超歐里幾何區域自旋信號檢測機制[19](Detection Mechanism of Spin Signal in Hypereuclidean Geometry Region,2S-HGR)和拓撲漂移定位監測機制[20](Topology Drift Location Monitoring Mechanism,TDLM)進行對比。

2.1 移動路徑定位

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

圖7 移動路徑定位實驗結果

2.2 定位誤差測試

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

圖8 定位誤差比較

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

表1 定位誤差實驗數據Table 1 Experimental results of location error m

2.3 坐標定位精度

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

圖9 坐標定位結果比較

3 結束語

為提高移動WSN網絡節點定位精度,本文提出一種基于運動軌跡捕捉與正交覆蓋機制的節點定位算法,通過捕捉性能最優錨節點的方式應對拓撲結構變動時鏈路抖動的情況,實現對節點運動矢量及坐標的精確捕捉,動態獲取節點運動軌跡。下一步將針對WSN網絡節點定位過程中難以實時捕捉網絡整體拓撲結構的問題,引入超歐里幾何拓撲映射機制,并采用區域映射算法將復雜拓撲結構轉化為平面拓撲結構,進一步提高本文算法對移動WSN的適應性。