基于時間序列啟發式信息的室內軌跡跟蹤算法

秦俊平 鄧慶緒 孫詩文 仁慶道爾吉 佟海濱 蘇憲利

1(東北大學計算機科學與工程學院 沈陽 110819) 2(內蒙古工業大學信息工程學院 呼和浩特 010080)

基于時間序列啟發式信息的室內軌跡跟蹤算法

秦俊平1,2鄧慶緒1孫詩文2仁慶道爾吉2佟海濱1蘇憲利1

1(東北大學計算機科學與工程學院 沈陽 110819)2(內蒙古工業大學信息工程學院 呼和浩特 010080)

(qinjuping30999@sina.com)

現有的無線傳感器網絡室內軌跡跟蹤算法是通過定位形成軌跡的,沒有利用一定空間范圍內相鄰信標節點RSSI定位信息在一段時間內的啟發式信息.提出了基于RSSI時間序列啟發式信息的軌跡跟蹤算法,該算法構建基于定位信息時空關聯特性的軌跡跟蹤模型,對定位信息進行一維重構邊界時間序列、二維重構區域統計量、移動最小二乘法檢測分別得到動態時間窗口及與之匹配的區域信息及邊界信息,在此基礎上完成受啟發式信息約束的動態時間彎曲軌跡跟蹤,并對時空關聯模型軌跡跟蹤算法中定位信息融合處理的原理進行了嚴謹的數學論證.通過現場實驗與仿真實驗表明:該算法軌跡光滑、誤差不累積、環境適應性好,相比現有方法基于啟發式信息有效克服噪聲的影響、減小搜索范圍,提高軌跡跟蹤的準確性.

無線傳感器網絡;接收信號強度指示；時間序列；啟發式信息；軌跡跟蹤

由于成本低、部署簡單、不受通視條件影響，無線傳感器網絡(wireless sensor network, WSN)被廣泛應用于各類室內監控系統中，包括煤礦安全生產監控系統、地鐵施工安全實時預警系統、室內精準導航系統等，無線傳感器網絡的室內應用還處于快速擴展之中.

對于許多室內應用，目標的位置與運動軌跡是最基礎信息，也是基于位置服務(location based service, LBS)實現的基礎.如在煤礦安全生產監控系統中,人員、移動設備的軌跡是重要的監控內容；地鐵施工安全實時預警系統中根據人員與設備、設備與設備的運動軌跡預測并觸發預警信號.

室內移動對象的位置信息包括當前位置與移動軌跡2個方面，目前提出的軌跡跟蹤模型[1]大都將移動對象的軌跡定義為通過室內定位設備感知的位置序列，也就是先定位再形成軌跡.由于定位計算誤差不可避免，軌跡中包含的原始位置信息在空間上不一定連續，造成這種現象的原因是定位時沒有考慮定位信息是在連續的位置產生的.

研究人員提出多種室內無線傳感器網絡軌跡跟蹤(或者預測)算法,這些算法有的是在對目標定位的基礎上形成目標的運動軌跡，有的是基于視頻識別形成目標的運動軌跡，還有基于加速度信息形成目標的運動軌跡.

具體到目標定位，由于接收信號強度指示(re-ceived signal strength indicator, RSSI)易于獲取，基于RSSI的定位技術一直受到持續的關注[2].從本質上來說，基于RSSI的定位屬于基于測距的定位技術,常規的作法是先建立RSSI的測距模型,在定位過程中根據所測得RSSI值換算出未知節點與信標節點之間的距離,列出3邊定位方程或者多邊定位方程求解得到未知節點的當前位置,持續這一過程所得一系列離散點就構成了未知節點的軌跡.這一方法的主要問題是室內RSSI的測距模型受到多徑、繞射、測量技術等多種因素的影響而導致有強時變特性,其定位精度相對較低[3],定位成功率不高[4].

未知節點在某一位置接收到信標節點發來的RSSI定位信號從而形成這一位置的指紋(fingerprinting),位置指紋定位先離線采集(位置、指紋)數據對并保存在數據庫中,定位時用測量值與數據庫中指紋進行匹配來確定未知節點位置.由于指紋數據庫的RSSI樣本是在實際環境中獲取的,室內環境指紋定位法的精度明顯高于基于測距的定位方法[5].

基于上面的原理,美國微軟研究院于2000年設計了RADAR[6]室內定位系統,在線階段用KNN(Knearest neighbor)算法選擇與測量值最接近的K個指紋,取它們的中心位置作為未知節點的當前位置.鑒于RSSI的測量值一般服從一定的概率模型或者近似服從某種概率模型,通過對采集到的數據進行分析,文獻[7]描述了移動設備的RSSI概率分布服從正態分布,這是移動設備概率定位法的理論基礎；文獻[8]對利用概率特性的方法定位與普通非概率定位方法進行了性能比較,從理論上證明概率方法可獲得更高的定位精度.

美國馬里蘭大學的Youssef等人[9]提出的Horus定位系統,在離線階段建立指紋數據庫時考慮了指紋的概率分布,將RSSI信息具有相似特征的信標節點劃分為一簇,形成一個定位子區域；在線階段先將未知節點初步定位于某個子區域,再進行精確定位.

肖亞龍等人[10]利用不同位置之間的RSSI指紋向量差異來表征對應的物理空間距離,在獲取未知節點的大概位置后,通過縮小目標對象的可能取值范圍并利用最近的信標節點來進行迭代計算,算法本質上是一種區域細化的定位方法,利用了不同信標節點提供的指紋信息質量的差異來提高定位精度.算法將室內環境的未知節點在每個位置接收到的信標節點信號組織為RSSI指紋向量,則任意2個位置之間的物理距離與對應的RSSI指紋向量之間的差異存在強的相關性,多次測量的統計結果更加穩定.算法采用分層次縮小未知節點所在區域的定位策略,首先根據信標節點位置對區域進行劃分,然后根據估算出的位置所屬區域對應信標節點位置優化并進行精確定位.

文獻[11]考慮到指紋信息的有效利用,采用主成分分析(principal component analysis, PCA)降維算法將原始的RSSI位置指紋轉換為PCs(principal components)主成分.PCs模型一方面離線階段可以減小指紋庫的規模,另一方面在線匹配階段可以減少計算量、提高精度.通過PCA降維,根據信標節點選擇指紋的2個準則——最大均值與最大信息增益都被滿足,其中最大均值準則優先選擇距離未知節點最近的信標節點,最大增益準則選擇最富含定位區分能力的信標節點進行定位,同時在降維過程中丟棄的是噪聲部分,從而提高定位精度.這些算法沒有利用軌跡跟蹤過程中同一未知節點連續位置指紋之間的關聯.

文獻[12]提出的魯棒性軌跡跟蹤算法,在離線階段采集用戶的軌跡指紋信息存放在軌跡指紋數據庫中,在線階段采用魯棒性的多元統計算法匹配實測軌跡指紋與數據庫中的軌跡指紋信息.進行軌跡匹配時先將軌跡根據移動步數分成若干段,多元最小方差算法可以克服采集的低質量的軌跡數據的異常波動,提高映射軌跡指紋到物理位置的精度；為了進行軌跡分段,設備需要有加速度傳感器,檢測移動步數.

考慮到節點的位置變化受制于現場環境及移動速度,文獻[13]引入Markov鏈描述的狀態轉移矩陣對位置指紋匹配的搜索范圍加以限制,將節點定位看成貝葉斯最大后驗概率計算問題；為了克服未知節點移動速度不同對定位造成的影響,文獻[14]引入動態時間彎曲(dynamic time warping, DTW)算法進行位置指紋匹配.

視頻軌跡跟蹤是機器視覺領域中的熱點研究問題,為了獲得魯棒性的跟蹤效果,設計能夠適應跟蹤目標外觀變化的外觀模型成為算法研究中的一項重要內容.將機器學習理論引入外觀模型檢測[15]中的思想大大推動了視頻軌跡跟蹤研究的發展.文獻[16]將視頻跟蹤問題轉換成二分類問題,視頻跟蹤模型設計機制采用判別式外觀模型學習跟蹤方法,依據目標和背景的分離邊界建立自適應性外觀模型實現軌跡跟蹤.梯度特征通常以區域統計的形式描述目標外觀,尺度不變性特征轉換算子[17]被用來描述目標的結構性外觀變化并取得了不錯的效果.基于外觀模型的視頻軌跡跟蹤算法要求對場景進行全方位監控,而且光線充足才能保證軌跡精度.

對于離散的、誤差較大的定位所得目標位置信息進行時空數據挖掘得到(或者預測)目標的運動軌跡.時空數據挖掘[18]就是從具有海量、高維、高噪聲和非線性等特性的時空數據中提取出隱含的、人們事先不知道的、但又潛在有用的信息及知識的過程.時空數據挖掘的關鍵在于發現與具體問題相關的時空信息中蘊含的有用信息,必要時可以對原始信息進行變換或者重構[18].

本文提出的算法利用沒有特殊硬件要求的RSSI位置指紋實現軌跡跟蹤，將軌跡跟蹤問題中RSSI定位信息概率分布特征與時空數據挖掘統籌考慮,通過合理部署信標節點發現啟發式信息并利用基于啟發式信息受限的指紋匹配算法實現高精度的軌跡跟蹤.

本文的主要貢獻有4個方面：

1) 算法構建基于定位信息時空關聯特性的軌跡跟蹤模型,采用RSSI時間序列考慮軌跡跟蹤問題,將離散的定位問題轉換為連續的時間序列特征發現問題；

2) 提出移動最小二乘啟發式信息檢測算法,對于啟發式信息出現的理論依據進行了數學證明,并且根據啟發式信息實現了動態時間窗口劃分,與該時間窗口對應的軌跡坐落于定位空間某區域；

3) 軌跡跟蹤采用受限的DTW位置指紋匹配,有效克服了噪聲的影響,提高了軌跡跟蹤準確度；

4) 現場實驗與仿真實驗證明了基于啟發式信息的軌跡跟蹤算法的正確性,從實踐層面驗證了算法的有效性.

1 基于定位信息時空關聯特性的軌跡跟蹤模型

為了充分利用移動的未知節點定位信息概率分布統計特性,針對室內應用(信標節點可人為部署),提出軌跡跟蹤模型定義,以2維平面為例，如圖1所示進行描述.

定義1. 區域(subarea).2維平面由縱橫相鄰的4個信標節點所劃分的平面子部分,圖1中每個小方格為一個區域.

Fig. 1 Trajectory tracking model圖1 軌跡跟蹤模型

定義2. 邊界(boundary).2維平面由水平/垂直方向的信標節點所構成的平面分界線,圖1中每條橫線/縱線(Bh/Bv)為一條邊界.

模型中未知節點發送通知信號,接收到通知信號的鄰近信標節點以相同頻率獨立地發射定位信號,未知節點接收到來自每個信標節點的定位信號按照到達時間的先后構成一個RSSI時間序列(time series)

Ri=(ri1,ri2,ri3,…,rik,…,riL)，

(1)

其中，rik表示第i個信標節點的對應時間序列Ri中第k個RSSI值.一段時間內,每個信標節點向當前未知節點發送的定位信息按照到達時間的先后組成一個Ri,i表示信標節點ID號,Ri存放在未知節點處并進行處理.在較小范圍內(相對于節點通信半徑)討論問題時,假設臨近信標節點所發射定位信號未知節點都可接收到,則在同一個時間窗口內不同時間序列的長度相等,不同時間序列同一下標的分量對應幾乎同一時間點，如圖1所示,或者說,相當于在某個位置,未知節點幾乎同時接收到其臨近信標節點發射的定位信號,當未知節點移動到下一位置后,再次接收到這些信標節點發送的定位信號,以次類推.下標的分量k隱含表示相對時間信息,即相對于時間窗口起點的時間為k×(1/f),f為信標節點發射定位信號頻率(發射次數/秒).

時間序列Ri的值為帶有噪聲的RSSI值,不同環境的噪聲影響是不相同的；同一環境下,噪聲的影響也是時變的[19].雖然有多種RSSI與距離的衰減模型,但對于實際問題,很難精確地選定模型及這些模型的參數[20].但有一點是研究者公認的,距離越近,RSSI值越大.

另一方面,文獻[7]指出有多種RSSI測量值中噪聲近似服從正態分布,文獻[8]提出了基于概率分布的定位算法并進行了理論證明.

當在2維平面定義了區域與邊界后,未知節點的正常移動就是從一個區域到另一個相鄰區域,其間跨躍某一(幾)條邊界的過程.不失一般性,假設未知節點在較小范圍內做近似勻速運動(較長時間的停頓可以依據RSSI變化檢測出來).在現場實驗中只要速度變化不劇烈,就可以取得不錯的軌跡跟蹤效果.

對于軌跡跟蹤問題,未知節點是連續移動的,在引入區域與邊界后,定義區域統計量與邊界時間序列.區域與邊界是按照特定位置關系形成的信標節點組合,以定位信號重構的形式考慮區域與邊界所涉及的信標節點,這些定位信號蘊含豐富的時空信息.在時間窗口中分析這些統計量,可以有效地降低噪聲影響,并且可以從整體上分析這些統計量的變化趨勢.

定義3. 區域RSSI時間窗口統計量.

/L，

(2)

其中，n為區域S包含信標節點個數,L為時間序列長度,L與時間窗口大小T1成正比例,即：

L=T1×f.

(3)

W(S,T1)集中表示了時間窗口T1內未知節點周圍信標節點以區域為單位RSSI大小,是對原始定位信息的2維重構,W(S,T1)反映了區域與未知節點一段時間內的相對距離關系.

定義4. 邊界RSSI時間序列.

Rb=(rb1,rb2,rb3,…,rbk,…,rbJ)，

(4)

其中，

rbk=(ri1+ri2)/2.

(5)

J為邊界時間序列長度,Rb的每個分量rbk是從邊界b的時間序列第k個分量上選擇的2個信標節點(邊界上相鄰的、一段時間內強度最強的2個)對應的RSSI均值,邊界RSSI時間序列對應時間窗口T2為相鄰區域時間窗口T1中點之間時間段，如圖2所示.Rb反映了時間窗口T2以邊界為單位的RSSI變化情況,是對原始定位信息的一維重構.

Fig. 2 Boundary time window and SBE detection圖2 邊界時間窗口與SBE檢測

定義5. 邊界跨越事件(spanning boundary event, SBE).未知節點從一個區域到達相鄰區域,必然要在期間某個時間點跨躍邊界(Bh/Bv),如圖2中虛線所示,邊界跨越事件可以表示為

espan(T2,t,b)，

(6)

其中，T2為該事件所在的時間窗口,T2取相鄰T1窗口的中間部分，t為事件發生的時間點,b為所跨躍的邊界編號.邊界跨越事件的物理含義為在T2內,未知節點逐步接近、到達b,之后又遠離b,期間在時間點t與b相交,下面分析跨越邊界過程中Rb的變化趨勢.

定理1. 在不考慮噪聲的情況下,未知節點在邊界上取得邊界時間序列Rb中最大值.

證明. 如圖3所示，未知節點逐步接近邊界,之后逐步離開,其中,q為區域邊長.在每個位置pk,未知節點接收到邊界上信標節點發射的定位信號,計算rbk作為Rb的第k個分量(下面的證明中未知節點作以水平方向為主的運動,以垂直方向為主的運動同理).

Fig. 3 Rb’s tendency圖3 Rb的變化趨勢

Shadowing模型是目前在無線傳感器網絡研究中最普遍使用的路徑損耗模型,綜合考慮了信號在傳輸過程中衰減與距離之間的關系以及各向異性傳播特征,RSSI的理論模型[20]為

(7)

R(d)=10lgP(d)，

(8)

R(d)=R(d0)-10βlg(d/d0)，

(9)

其中，R(d)表示距離為d處的RSSI,R(d0)表示距離為d0的參考點處RSSI.從理論模型可見,當β取值處于一定范圍內時,RSSI隨著d的增加而減小,且減小的速度先快后慢.

P(d)表示距離信號發射點d處的能量均值(單位mW),P(d0)表示距離d0處的能量均值,d0=1 m,β為路徑衰減因子,環境不同,β取值不同,在較小范圍內,可以認為β取值不變.由式(7)可得:

(10)

(11)

證畢.

實驗中,由于定位信號的發射有一定間隔,未知節點可能在最接近邊界處取得極大值,在定位信號發射間隔較小的情況下,引起的誤差較小.

實際中,未知節點接收到的定位信號RSSI滿足[20]:

R(d)=R(d0)-10βlg(d/d0)+X，

(12)

其中,X表示多徑、繞射、障礙物等多種因素引起的RSSI噪聲,X被看作一個以0為均值、σ2為方差的高斯白噪聲,即:

X～N(μ,σ2)，

(13)

X的概率密度函數為

(14)

隨著環境不同,σ取值不同.

假設：

1) 未知節點在時間窗口T1中一直位于某個區域內部,如一直位于區域SA,如圖4所示,接下來以SA周圍的區域SB，SC作為對比,說明不同區域W(S,T1)的統計特性差異，其中S表示區域號，A,B,C表示區域類別.

2) 在遠小于節點通信半徑的范圍內,可以保證信標節點發射并且為未知節點所接收的定位信號個數是相同的且為L；對于次數少于L的區域,其位于對比范圍之外.

Fig. 4 Subarea relation圖4 區域關系

3) 在軌跡跟蹤模型中,所有信標節點發射定位信號的參數設置(發射功率大小)相同、所配置天線相同,2維平面被劃分為多個區域,區域內及區域判定算法涉及的相鄰區域較小范圍內(遠小于節點通信半徑),假設β與σ2取值相同.

定義6. 區域RSSI向量.

VS=(rul,rur,rlr,rll)，

(15)

VS表示某時間點未知節點所接收的來自某區域順時針方向，見圖1中弧形箭頭，從左上角到左下角4個信標節點RSSI所組成向量.

定義7. 區域RSSI向量之和.

(16)

YS用矩陣相乘的形式表示4個分量的累加和,一方面說明在和值中每個分量的權重相同,另一方面說明YS表示該時間點未知節點與區域的相對關系.

定理2.YS～N(μul+μur+μlr+μll,(2σ)2),其中μul，μur，μlr，μll分別為未知節點相對于4個信標節點當前RSSI均值,均值的大小取決于信標節點與未知節點之間的距離,σ為區域當前RSSI方差.

證明. 由式(12)可得,任一RSSI測量值R(d)由理論值式(8)與噪聲X累加而成,將其看作隨機變量,根據前面的假設,在較小范圍內對于某個未知節點所在的某位置pi(如圖4虛線上小圓圈),d確定后理論值R(d0)-10βlg(d/d0)是確定的,相當于常量,故：

R(d)～N(R(d0)-10βlg(d/d0),σ2)，

(17)

σ2為噪聲X的方差.

YS為4個獨立信標節點對應RSSI值的累加和,各個信標節點獨立地發射定位信號,未知節點接收并形成RSSI向量VS,故VS包含的4個分量相對獨立,根據相互獨立的隨機變量之和仍然服從正態分布可得：

(18)

其中，σul，σur，σlr，σll分別為對應區域4個信標節點當前RSSI方差,根據假設,σul=σur=σlr=σll=σ,σ為所涉及區域的RSSI標準差,故：

YS～N(μul+μur+μlr+μll,(2σ)2).

(19)

證畢.

定理3.

(20)

其中，μ1,μ2,…,μL-1,μL分別為在區域內不同點處YS分布的均值,σ2為區域當前RSSI方差.

證明.

其中，W(S,T1)表示未知節點在某區域內L個位置時信標節點以區域為單位測量并計算的YS均值，如圖4所示.同樣,在每個未知節點位置pi,YS相互獨立，

(21)

證畢.

從統計量W(S,T1)相對于YS的分布均值與方差變化速率來看,在L個位置pi，如圖4所示，測量YS并求統計量均值W(S,T1),分布均值與方差的變化速率是不相同的,方差有變小的趨勢(L越大效果越好),即減少了噪聲的影響,這是利用W(S,T1)推斷區域的重要原因.

Fig. 5 Subarea W(S,T1) relation圖5 區域W(S,T1)關系

W(S,T1)由L個位置pi處YS計算均值得到,根據式(22)可見,W(S,T1)相當于在區域S內某定點多次測量計算均值的效果(從減少方差的角度看).

(22)

區域RSSI時間窗口統計量、邊界RSSI時間序列與邊界跨越事件espan都包含豐富的時間、空間信息.

下面將詳細介紹用移動最小二乘法檢測邊界跨越事件、判定動態切分時間窗口內軌跡所在區域、計算軌跡的算法.在上述模型定義的基礎上,基于啟發式信息的軌跡跟蹤算法步驟如下：

1) 在定位空間內按照縱橫方向等間距網格狀部署信標節點,將信標節點信息(NodeID,(x,y))保存在每個未知節點處,在未知節點形成區域信息與邊界信息,其中NodeID為信標節點的ID,(x,y)為其坐標；

2) 接收到通知信息的信標節點以固定頻率發射定位信號,未知節點接收并按照信標節點分別形成多個時間序列Ri；

3) 各未知節點根據移動最小二乘法檢測邊界跨越事件、動態切分時間窗口、構建區域時間窗口統計量,推斷當前區域；

4) 根據當前區域信息進行受限的位置指紋匹配,形成軌跡.

2 啟發式信息檢測

構建基于定位信息時空關聯特性的軌跡跟蹤模型后,未知節點在移動過程中會產生邊界信息、區域信息,下面闡述啟發式信息檢測算法.

2.1 移動最小二乘法檢測邊界信息

根據邊界時間序列檢測邊界跨越事件,就是要根據離散數據發現時間序列的變化規律并找出一段時間內的極大值.考慮到軌跡的連續光滑要求及噪聲影響,選用移動最小二乘法進行分段的曲線擬合:

線性基:

p(x)=(1,x)T，

(23)

系數向量:

a(x)=A-1(x)B(x)y，

(24)

其中：

(25)

n為影響區域內節點個數，

B(x)=(w(x-x1)p(x1),
w(x-x2)p(x2),…,w(x-xn)p(xn))，

(26)

yT=(y1,y2,…,yn)，

(27)

擬合函數為

(28)

其中，m為線性基函數的項數，權函數選用三次樣條權函數：

(29)

γ=(x-xi)/γmax，

(30)

其中，γmax為影響區域的長度,對于每個數據點,根據權函數選擇其周圍的若干個數據點以不同的權值參與擬合,越靠近的數據權值越大,基函數p(x)的階數決定了曲線的精度,根據實驗結果選用線性階基函數可以保證精度.

為找出極值點,要保證曲線前后的連續性,這是選用移動最小二乘法的主要原因.從理論上來說,跨越邊界時rbk取得極大值,由于噪聲的影響為了避免偽峰值對極值點加以限定引入閾值Tb,Tb要現場多次測量確定.

算法1. SBE檢測算法.

輸入：邊界時間序列Rb；

輸出：espan對應時間點及邊界號.

1) 對本區段Rb進行移動最小二乘擬合處理；

2) 上一區段與本區段連接；

3) 檢測極值點mb,要求mb≥Tb,mb存在則執行4),不存在則返回1)等待新的區段邊界時間序列；

4) 返回espan對應時間點tb及邊界號b,時間點表示未知節點經過邊界b的時間點.

2.2 基于最小錯誤率貝葉斯決策規則的區域檢測

檢測到未知節點跨越邊界的時間點后,2條相鄰邊界對應時間點確定出一個時間窗口T1(符合定理3的假設),下面確定未知節點在T1時間窗口所在區域.

對于未知節點來說,在時間窗口T1內YS與W(S,T1)的分布如圖6所示,圖6(a)為YS的分布,圖6(b)為W(S,T1)的分布.

Fig. 6 W(S,T1) and YS’ Distributions圖6 W(S,T1)與YS分布

在模式識別中,已知每類事物的總體概率分布,及類的條件概率密度,用Bayes決策理論實現分類的方法如下(假設共有2個類別?1與?2)，已知p(?1),p(?2)且：

p(?1)+p(?2)=1，

(31)

p(z|?1)表示在?1中觀察到z的概率密度,p(z|?2)表示在?2中觀察到z的概率密度,則：

(32)

表示觀察到z屬于哪個類別?i的概率.根據最小錯誤率貝葉斯決策規則,如果p(?i|z)=max (p(?i|z)),則z∈?i.

圖6中陰影區域表示發生誤判的情況.顯然不同類別的隨機變量μ相距越遠,σ越小,越有利于分類.

根據W(S,T1)判定區域的算法中,對未知節點所在區域的判斷,當放在時間窗口中研究時,大量現場實驗證實,只需要考慮SA,SB,SC這3類區域,也就是:

p(SA|W(S,T1))+p(SB|W(S,T1))+
p(SC|W(S,T1))=1.

(33)

由于每類區域W(S,T1)的分布均值不固定(取決于未知節點的運動軌跡),故選定相對量進行分類.基于W(S,T1)區域判定算法,在T1內以區域為單位分別計算W(S,T1),以

arg max(W(Si,T1))

(34)

作為未知節點在T內所在區域.

區域判定算法準確度,在T內由于噪聲的影響使非未知節點當前所在區域的W(S,T1)超過當前所在區域時,即發生了區域誤判.下面討論誤判發生可能性的影響因素.

若區域判定正確,也就是滿足：

(W(SA,T1)>W(SB,T1))∩
(W(SA,T1)>W(SC,T1))，

(35)

區域誤判也就是：

(W(SA,T1)(W(SA,T1)

(36)

算法2. 區域檢測算法(subarea judgement algorithm, SJA).

輸入：相鄰邊界時間點；

輸出：該時間窗口對應區域號.

1) 計算時間窗口T內相鄰邊界間各窗口W(S,T1)；

2) 返回arg max(W(Si,T1))對應區域.

3 受限的DTW位置指紋匹配算法

位置指紋定位先離線采集(位置,指紋)數據對并保存在指紋數據庫中,定位時根據指紋數據進行匹配來確定未知節點位置.指紋數據的噪聲不可避免,在啟發式信息的限定下進行位置指紋匹配,有效減小匹配范圍并提高定位精度.

受樣本采集、存儲以及定位計算開銷等的限制,基于位置指紋的定位方法需要對連續位置空間進行離散化處理,即把室內空間劃分成若干個網格，如圖7所示,每個網格采集其中心位置的位置指紋并存儲在數據庫中用于目標位置推斷.位置指紋以區域RSSI向量VS的形式表示,采集到RSSI樣本后,一旦確定其T1內所屬區域,則形成區域RSSI向量并進行匹配.

Fig. 7 Restricted position fingerprint matching圖7 受限的位置指紋匹配

為提高指紋數據的精度,離線數據庫在一個位置采集多次,取其均值存放.采樣位置密度高,數據庫占用空間大,定位精度高；反之則精度低.本文算法用于軌跡跟蹤,考慮人的正常移動速度0.7 m/s,選擇采樣間隔0.5 m.

(37)

算法分別在邊界進行單點匹配確定區域內起點位置ps與終點位置pe,如圖7中深灰色位置所示.

W=(w1,w2,…,wn2),

n1,n2分別為2個序列的長度，則:

(38)

用歐幾里德距離作為Dbase及2點間距離,由DDTW的遞歸定義可見,DDTW可以衡量長度不同的2個時間序列的相似度.可能軌跡需要滿足的3個基本條件：

1) 每條可能軌跡的起點為ps,終點為pe；

2) 軌跡要求連續,即如果當前時間點t匹配位置p(如圖7所示,橫底紋位置),時間點t+1秒(實驗中每秒發射1次定位信號)僅需在其附近可能到達的范圍內進行匹配,也就是在上、右上、右、右下、下、左下、左、左上等位置搜索；

3) 軌跡上相鄰點要滿足單調性要求,此條件與運動方向有關,例如當前時間點t匹配位置p(見圖7,橫底紋位置),時間點t+1秒僅需搜索其右側、右下位置(豎底紋位置).

算法3. 受限的DTW位置指紋匹配算法.

輸出：區域內最匹配軌跡.

1) 以區域為單位對RSSI向量進行移動最小二乘擬合處理；

2) 依據式(37)計算起點與終點在邊界上位置；

3) for 滿足3個基本條件的每一條路徑

計算DDTW；

end for

4) 輸出相似度最高的可能軌跡作為軌跡跟蹤結果.

4 實驗結果與分析

算法的驗證既有仿真實驗,也有現場實驗.現場實驗信標節點信息(NodeID,(x,y))保存在每個未知節點處,指紋數據庫保存在匯聚節點,各未知節點獨立地進行邊界檢測與區域檢測,將邊界信息與區域信息上傳至匯聚節點,匯聚節點據此完成指紋匹配,區域邊長q=6.5 m,信標節點部署如圖1所示,現場實驗采用的無線收發芯片為CC2530.

仿真實驗在NS-2環境進行,采用Shadowing模型,分別選標準差σ為5 dBm與10 dBm、節點最大通信距離為50 m、路徑損耗系數β=3作為實驗參數進行實驗.

第1組實驗檢測邊界,觀察邊界時間序列的變化趨勢,按照圖3所示運動方向進行測試.

從實驗結果可見,無論是現場實驗還是仿真實驗,當未知節點經過邊界時,邊界時間序列都會出現一個明顯的上升、下降過程,理論上極值點在邊界(如圖8中虛線所示)處取得,實驗中可能會略有偏移(見圖8(b)實際極值點相對邊界靠右1 s),導致極值點偏移的可能原因有噪聲較強,也可能是定位信號發射時錯開邊界位置所致.

第2組實驗檢測區域,依據最小錯誤率貝葉斯決策規則判斷時間窗口內未知節點所屬區域,按照圖3所示運動方向進行測試.

Fig. 8 Detecting boundary圖8 檢測邊界

圖9(a)為q=6.5 m時的區域判定準確率,其他參數不變,q=13 m時的區域判定結果如圖9(b)所示.可見,隨著定位信號單位時間發射次數的增多,依據最小錯誤率貝葉斯決策規則判定區域的算法準確率都有所提高，但總的來說,q=13 m時的區域準確度明顯好于q=6.5 m時的情況,這主要是由于隨著時間窗口的增大,W(S,T1)的統計特性更好所致.算法準確率也受到RSSI噪聲的影響,噪聲越小、準確率越高.

質心(centroid)算法與多維標度(MDS-MAP)算法以多次定位中所在區域正確的比例衡量區域準確率,質心算法的區域判定性能比較差,因為沒有利用定位信息的統計特性；多維標度算法進行多維轉換確定位置,區域準確度介于質心算法與本文算法之間.

軌跡跟蹤全部采用現場實驗進行驗證,選擇q=6.5 m間距部署信標節點,人手持未知節點以正常行走速度0.7 m/s移動,所得軌跡如圖10所示.圖10中實線表示真實軌跡,虛線表示本文提出基于時間序列啟發式信息的室內軌跡跟蹤算法所得到軌跡,三角符號表示采用質心定位算法計算所得離散點位置,在此基礎上形成軌跡如點虛線所示,注意定位結果包含野值.

Fig. 10 Trajectory tracking圖10 軌跡跟蹤

算法運行過程中,依次檢測到Bv1,Bv2,Bh3,Bv3,Bv4,Bv5各邊界,判斷出依次經過S1,S2,S3,S4,S5各區域，區域標識如圖11所示,在區域內得出的軌跡如圖10所示.

Fig. 11 Trajectory tracking at the speed of 0.3 m/s圖11 0.3 m/s移動速度下的軌跡跟蹤結果

從圖10可見,本文算法有高的精度,現場實驗軌跡精度可以達到1.0 m以內,高精度是以室內空間網格狀部署信標節點從而可以獲得啟發式信息為基礎得到的.

為了比較不同移動速度下的算法性能,在與圖10相同的信標節點部署條件下,人手持未知節點以行走速度0.3 m/s移動,所得軌跡如圖11所示.算法依次檢出的邊界、區域與行走速度0.7 m/s時相同.2次軌跡由于RSSI噪聲的影響有細微差異.

對于運動速度不均勻的場合,算法是根據邊界時間序列Rb的變化趨勢動態劃分時間窗口并根據統計量W(S,T1)來判定所在區域的,區域檢測不受影響.

區域內的軌跡是采用受限的DTW位置指紋匹配算法以區域為單位進行位置指紋匹配求取的,對于非勻速運動的目標,算法根據軌跡對應的RSSI序列與指紋數據庫中的指紋進行匹配,所檢測的軌跡形狀沒有問題,但是以時間點來看,位置會向前或者向后發生一定的偏離,這種偏離僅限于區域內,下一個區域又會以區域邊界為起點/終點進行新一輪匹配計算,所以這種偏離引起的誤差不會在區域間累積.如圖12所示,實驗中開始移動速度較快,之后速度變慢,圖12中實心點表示位置有較大偏移(>1 m),但這種偏移是沿著跟蹤到的軌跡方向的,從軌跡跟蹤的角度來說,算法有較好的魯棒性；從定位的角度來說,由于在每個區域內先確定起點與終點,之后進行指紋匹配,所以區域間定位誤差不會累積,靠近兩端的點位置偏移較少.

Fig. 12 Trajectory tracking at nonuniform speed圖12 非均勻移動速度下的軌跡跟蹤

Fig. 13 Experimental Nodes圖13 實驗節點

圖13(a)所示為現場實驗所用信標節點，圖13(b)所示為未知節點.

算法首先完成邊界檢測、區域檢測,再進行區域內軌跡跟蹤,是分階段實施的.其中的邊界檢測與區域檢測各未知節點獨立進行,各未知節點獨立地劃分動態時間窗口,時間窗口內軌跡跟蹤涉及指紋數據庫,在匯聚節點完成.算法僅需要將所確定區域對應RSSI數據上傳,減少了定位信息通信量.

5 總 結

同一未知節點時間上連續的指紋信號,對應的空間位置也必然相鄰.為了充分挖掘這種時空關聯特性,本文構造了基于定位信息時空關聯特性的軌跡跟蹤模型并設計了相應算法.

邊界檢測算法是根據邊界時間序列的變化趨勢設計的,根據邊界所劃分的動態時間窗口內區域判定算法依據最小錯誤率貝葉斯決策規則設計,區域內軌跡跟蹤采用動態時間彎曲位置指紋匹配算法.

算法將一段時間內的軌跡跟蹤作為連續變化的時間序列來考慮,充分利用序列的變化趨勢、統計特性得到重要的啟發式信息.算法在時間窗口內整體判斷統計量分布及邊界時間序列變化趨勢,可以有效降低噪聲影響,減少野值出現.關于區域RSSI統計量的分布及邊界時間序列的變化趨勢理論上滿足文中結論.區域以動態時間窗口為單位判斷,誤差不累積,且區域判斷采用相對指標使算法能適應不同的環境.

算法采用分階段實施的方式,充分利用節點的計算能力,只向匯聚節點傳輸部分信息,相關數據結構在未知節點存儲需要一定的存儲空間開銷.

本文的軌跡跟蹤模型要求信標節點網格化部署,未來的研究方向是使算法能適應信標節點位置不規律的場景.

[1]Jin Peiquan, Wang Na, Zhang Xiaoxiang, et al. Moving object data management for indoor space[J]. Chinese Journal of Computers, 2015, 38(9): 1777-1795 (in Chinese)(金培權, 汪娜, 張曉翔, 等. 面向室內空間的移動對象數據管理[J]. 計算機學報, 2015, 38(9): 1777-1795)

[2] Yang Zheng, Liu Yunhao, Li Xiangyang. Beyond trilatera-tion: On the localizability of wireless ad-hoc networks[J]. ACM Trans on Networking, 2010, 18(6): 1806-1814

[3] Meguerdichian S, Slijepcevic S, Karayan V, et al. Localized algorithms in wireless ad-hoc networks: Location discovery and sensor exposure[C] //Proc of the 2nd ACM Int Symp on Mobile Ad-Hoc Networking & Computing. New York: ACM, 2001: 106-116

[4] Wang Fubao, Shi Long, Ren Fengyuan. Self localization systems and algorithms for wireless sensor networks[J]. Journal of Software, 2005, 16(5): 1148-1157 (in Chinese)(王福豹, 史龍, 任豐原. 無線傳感器網絡中的自身定位系統和算法[J]. 軟件學報, 2005, 16(5): 1148-1157)

[5] Hossain AKMM, Soh WS. A survey of calibration free indoor positioning systems[J]. Computer Communications, 2015, 66(1): 1-18

[6] Bahl P, Padmanabhan V N. RADAR: An in-building RF based user location and tracking system[C] //Proc of the 19th IEEE Int Conf on Computer and Communications. Piscataway, NJ: IEEE, 2000: 775-784

[7] Kaemarungsi K, Krishnamurthy P. Analysis of WLAN’s received signal strength indication for indoor location fingerprinting[J]. Pervasive and Mobile Computing, 2012, 8(2): 292-316

[8] Roos T, Myllymaki P, Tirri H, et al. A probabilistic approach to WLAN user location estimation[J]. International Journal Wireless Information Networks, 2002, 9(3): 155-164

[9] Youssef M, Agrawala A. The Horus WLAN location determination system[C] //Proc of the 3rd Int Conf on Mobile Systems, Applications, and Services. New York: ACM, 2005: 205-218

[10] Xiao Yalong, Zhang Shigeng, Wang Jianxin. An indoor localization algorithm based on multidimensional scaling and region refinement[J]. Chinese Journal of Computers, 2017, 40(8): 1918-1932 (in Chinese)(肖亞龍, 張士庚, 王建新. 一種基于多維標度和區域細化的無線室內定位方法[J]. 計算機學報, 2017, 40(8), 1918-1932)

[11] Fang Shihhau, Lin Tsungnan. Principal component localization in indoor WLAN environments[J]. IEEE Trans on Mobile Computing, 2012, 11(1): 100-110

[12] Zhang Xinglin, Yang Zheng, Wu Chenshu, et al. Robust trajectory estimation for crowdsourcing based mobile application[J]. IEEE Trans on Parallel and Distributed Systems, 2014, 25(7): 1876-1885

[13] Zhao Fang, Luo Haiyong, Ma Yan, et al. An accurate fingerprinting localization algorithm based on common beacons[J]. Journal of Computer Research and Development, 2012, 49(2): 243-252 (in Chinese)(趙方, 羅海勇, 馬嚴, 等. 基于公共信標集的高精度射頻指紋定位算法[J]. 計算機研究與發展, 2012, 49(2): 243-252)

[14] Wang Jue, Katabi D. Dude, where’s my card: RFID positioning that works with multipath and non-line of sight[J]. ACM SIGCOMM Computer Communication Review, 2013, 43(4): 51-62

[15] Zhang Huanlong, Hu Shiqiang, Yang Guosheng. Video object tracking based on appearence models learning[J]. Journal of Computer Research and Development, 2015, 52(1): 177-190 (in Chinese)(張煥龍, 胡士強, 楊國勝. 基于外觀模型學習的視頻目標跟蹤方法綜述[J]. 計算機研究與發展, 2015, 52(1): 177-190)

[16] Song Yizhe, Li Chuan, Wang Liang, et al. Robust visual tracking using structural region hierarchy and graph matching[J]. Neurocomputing, 2012, 89(10): 12-20

[17] Hare S, Saffari A, Torr PHS. Struck: Structured output tracking with kernels[C] //Proc of the 13th IEEE Int Conf on Computer Vision. Los Alamitos, CA: IEEE Computer Society, 2011:263-270

[18] Liu Dayou, Chen Huiling, Qi Hong, et al. Advanced in spatiotemporal data mining[J]. Journal of Computer Research and Development, 2013, 50(2): 225-239 (in Chinese)(劉大有, 陳慧靈, 齊紅, 等. 時空數據挖掘研究進展[J]. 計算機研究與發展, 2013, 50(2): 225-239

[19] Huang He, Chen Guoliang, Sun Yu’e, et al. Localization algorithm in complex area[J]. Journal of Computer Research and Development, 2011, 48(3): 364-373 (in Chinese)(黃河, 陳國良, 孫玉娥, 等. 復雜區域節點定位算法研究[J]. 計算機研究與發展, 2011, 48(3): 364-373)

[20] Rappaport T S. Wireless Communications: Principle and Practice[M]. Upper Saddle River, NJ:Prentice Hall, 1999

IndoorTrajectoryTrackingAlgorithmBasedonTimeSeriesHeuristicInformation

Qin Junping1,2, Deng Qingxu1, Sun Shiwen2, Renqing Daoerji2, Tong Haibin1, and Su Xianli1

1(SchoolofComputerScienceandEngineering,NortheasternUniversity,Shenyang110819)2(CollegeofInformationEngineering,InnerMongoliaUniversityofTechnology,Hohhot010080)

Existing indoor trajectory tracking algorithms on wireless sensor network are based on continuous localization and can not make use of the heuristic information of RSSI time series within a certain temporal and spatial range. The heuristic information of RSSI time series is a key factor of trajectory tracking procedure. This paper proposes a new trajectory tracking algorithm on spatiotemporal correlation model based on heuristic information. According to the heuristic information related to moving trajectory, the new method contains the following essential phases. Firstly, we model the trajectory tracking model reflecting spatiotemporal correlation and statistical characteristics. Secondly, we detect spanning boundary event and judge which subarea the unknown node was in by means of information fusion of RSSI time series and moving least square method. Finally, the moving trajectory of unknown node is formed by means of dynamic time warping fingerprinting matching algorithm with heuristic information constraints. The principles of information fusion are strictly proved in mathematics. The field experiments and the simulation experiments show that the algorithm has good environment adaptability, smooth trajectory and the error does not accumulate among the subareas. Compared with the existing methods, the accuracy of trajectory tracked is improved.

wireless sensor network (WSN);

signal strength indicator (RSSI); time series; heuristic information; trajectory tracking

2016-11-08；

2017-02-21

國家自然科學基金項目(61472072，61540004)；內蒙古自然科學基金項目(2015MS0619，2013MS0920)；內蒙古高等學校科學研究項目(NJZY091)

This work was supported by the National Natural Science Foundation of China (61472072, 61540004), the Natural Science Foundation of Inner Mongolia of China (2015MS0619, 2013MS0920), and the Higher Educational Scientific Research Project of Inner Mongolia (NJZY091).

TP393

QinJunping, born in 1974. PhD candidate. Associate professor. Member of CCF. His main research interests include pattern recognition, localization, and information fusion in WSN.

DengQingxu, born in 1970. PhD. Professor and PhD supervisor. Senior Member of CCF. His main research interests include reconfigurable computing systems, multi-processor real time scheduling and formal methods in real-time system analysis.

SunShiwen, born in 1991. Master candidate. Her main research interests include image recognition based on machine learning and localization in WSN.

RenqingDaoerji, born in 1983. PhD. Associate professor. His main research interests include moving object data mining and optimization.

TongHaibin, born in 1986. PhD candidate. His main research interests include information security technology in WSN and industrial detection technology.

SuXianli, born in 1980. PhD candidate. His main research interests include cyber physical systems and intelligent optimiza-tion method.