基于泛克里金插值的WSN位置指紋預處理*

樂燕芬,張賀娜,施偉斌

(上海理工大學光電信息與計算機工程學院,上海 200093)

隨著物聯網、移動智能終端的快速發(fā)展,近年來位置相關的服務和應用,如展覽館、商場、倉庫、機場等樓宇環(huán)境內基于位置的用戶信息的傳遞導航等受到了廣泛的關注。而無線傳感器技術(WSN,Wireless Sensor Networks)由于其安裝方便、即插即用、低功耗等特點廣泛應用于智能樓宇中,使得基于WSN的室內定位的實用性和必要性日趨顯著[1]。其中基于接收信號強度(RSS,Received Signal Strength)的方法由于不需要額外的硬件設備且具有非視距傳輸的特點而成為室內定位技術的重要實現手段。

基于測距RSS的定位技術要求基于信號傳播特征建立無線信道模型再匹配測量數據完成定位[2]。這就要求模型能精確反映空間的信號傳播特性。而室內環(huán)境有墻體等障礙物存在并有較頻繁人員活動,使得無線信號因多徑效應、斑塊效應等出現擾動,表現出復雜、時變的傳播特性,使得由信號強度估算傳播距離有較大的誤差,因此也有文獻采用多維標度法,直接利用無線信號強度進行定位以期克服擾動對定位的影響[3]。

RSS定位算法的另一類是位置指紋識別法。該方法通過離線階段采集的監(jiān)測區(qū)域內的采樣點RSS獲得該區(qū)域信號分布的指紋描述。在線階段通過測量信號與指紋的匹配來估計目標位置。這種方法不需要預設信號的傳播衰減模型,更關注離線與在線階段的RSS信號是否具有一致的分布模式。對于RSS指紋定位技術目前的工作集中在2個方面,一個是定位匹配算法的研究,包括基于機器學習的建模[4]、特征提取[5]等尋求RSS信號與位置的非線性關系;另一個研究重點在于位置指紋庫的構建。后者主要的研究目的就是在保持甚至提高定位精度的前提下盡可能降低離線階段建立位置指紋庫所需的人力、時間成本。在此研究方向目前也已有不少的研究成果。如文獻6采用德洛內三角剖分(Denaunay Triangulation)算法,把所有采樣點進行三角形網格劃分,以采樣點為頂點構成的三角區(qū)域內的插值則通過該3個采樣點線性生成[6]。文中的實驗表明該算法與反距離加權插值(IDW,INVERSE DISTANCE WEIght)有相當的插值精度。由于RSS信號衰減與傳播距離總體上并不滿足線性關系,為了克服此線性插值的不足,文獻7提出了三次三角插值。該方法用二元三次多項式描述三角區(qū)域內RSS信號強度與三角形頂點的距離關系,從而確定插值點的RSS值[7]。這在一定程度上解決了線性插值的局限性。但德洛內三角剖分純粹從離散幾何角度出發(fā),按采樣點的絕對物理位置坐標進行劃分,并不考慮室內具體環(huán)境的布置和構造對RSS信號的影響。近年來,克里金方法(Kriging)也逐漸被應用到室內定位的RSS插值中,并針對室內RSS信號的分布特點,進行了各種方式的探索和改進。如文獻8在用普通克里金(OK,Ordinary Kriging)插值時用模擬退火算法改進了理論變異函數的擬合精度[8];文獻9則采用RSS信號與鏈路通訊質量LQI作為主輔變量,利用協同克里金法完成空間插值[9];而文獻10針對不同時間段內室內人員活動度不同,采用普通克里金插值法構建相應時段的位置指紋庫[10]。上述方法都利用了RSS信號的空間相關性,用克里金方法挖掘RSS信號在空間的分布特性,但應用這兩類克里金方法的前提是,空間變量也即RSS信號在監(jiān)測區(qū)域內具有一致的變異性,也即樣本數據具有同樣的期望和方差。而對于RSS信號,在整個監(jiān)測區(qū)域內測量值不可能為常數。不僅是因為復雜的室內環(huán)境,同時也因為無線信號總體上隨傳播距離的增加而衰減。這使得這兩類克里金插值算法在生成RSS指紋庫時有其局限性。

針對此問題,本文提出了一種基于泛克里金(UK,Universal Kriging)插值的指紋預處理方式,通過漂移函數的加入解決傳播距離引起的RSS信號衰減,用變異函數描述室內環(huán)境下RSS信號的空間變化,并以一個典型辦公區(qū)域為例,通過環(huán)境分析結合RSS值的分布確定變異函數的形式,對真實RSS指紋進行插值構建位置指紋庫。通過在線階段加權K近鄰算法驗證了所構建指紋庫對降低離線人力時間成本及提高在線定位精度的有效性。

1 泛克里金插值算法原理

克里金插值法又稱空間局部插值法。該方法考察空間屬性在空間位置上的相關性與變異分布,由待插值點影響距離范圍內的采樣點來估計待插點的屬性值,是有限區(qū)域內對區(qū)域變量的一種無偏最優(yōu)估計。普通克里金插值法計算公式為:

(1)

變異函數γ也稱為半方差函數,定義為:

(2)

該函數只與采樣點間的分離距離h有關,而與位置s和s+h無關,反映信號的空間結構性和隨機性變化。實際應用時,常用樣本變異函數擬合獲得理論變異函數。樣本變異函數的計算采用下式:

(3)

式中:Nh是分離間距為h的采樣點對個數,是隨h變化的量。樣本變異函數給出了當前采樣空間內信號的離散變異結構,通過擬合的方式獲得理論變異函數來表征采樣空間內任意距離下的信號變異特性。球狀模型、指數模型、高斯模型等都是常用的擬合函數模型。

普通克里金法要求信號滿足二階平穩(wěn)假設,即E[Z(s)]=m,m在空間上是常量。而實際應用中空間信號很難滿足此假設,也即E[Z(s)]=m(s),是空間位置s的非平穩(wěn)函數。針對這種情況,泛克里金插值通過增加一個確定性漂移,把在位置s上的信號表示為:

Z(s)=m(s)+r(s)

(4)

式中:m(s)為采樣信號的確定性漂移函數,也稱趨勢;r(s)是期望為0的殘差量,滿足二階平穩(wěn)條件。漂移形式需依據背景資料分析、樣本變異函數的圖形觀察來確定[11],如文獻12中f(s)采用路徑結合墻壁的信號衰減模型[12],更常用的是采用位置s相關的多項式來表達[11,13-14],此時m(s)用P個坐標相關函數fp(s)的線性組合來表示:

(5)

這樣,泛克里金插值公式可表示為:

(6)

式中:

(7)

按照無偏估計的原則,要求下式成立:

(8)

即要滿足:

FTW=F0

(9)

式中

F0=[1,f1(s0),…,fP(s0)]T

(10)

此時估計方差可表示為:

(11)

式中:

(12)

γ=[γ(s0-s1)…γ(s0-sN)]T

(13)

這樣問題就轉化為:

(14)

采用Lagrange乘數法解決此問題,可以得到一個線性方程[15]:

(15)

式中:λ是引入的Lagrange算子。解此方程可得權重系數wn。

實際應用時,根據式(3)獲得樣本函數,擬合后獲得理論變異函數γ,而本文的漂移函數采用二元二次多項式,表示為:

(16)

式中:(x,y)是位置點s的坐標,系數β=[β0,β1,…,β5]T是待定的回歸參數,Fs=[1,x,y,x2,xy,y2]T。

圖1給出了基于泛克里金插值的指紋預處理過程。通過對離線采集的RSS信號預處理,分析信號的空間分布趨勢,對監(jiān)測區(qū)域進行劃分。對每個區(qū)域通過變異函數和漂移函數的擬合,按照無偏和最小方差的準則,利用Lagrange乘數法求解獲得插值權重。確定區(qū)域的插值密度,對離線指紋庫插值后構建預處理后的位置指紋庫。利用該指紋庫可完成在線階段的位置估計。

圖1 基于泛克里金插值的指紋庫預處理過程

2 基于泛克里金的RSS插值

2.1 數據預處理

在WSN室內定位中,采集的樣本數據是每個參考點接收的來自各個錨節(jié)點的RSS信號。首先需要分析數據的空間分布趨勢。實驗監(jiān)測區(qū)域為40 m×15 m的辦公樓面,包括兩側走廊和中央大廳。在兩側走廊天花板上間距4.2 m共布置了18個錨節(jié)點,分別標記為#1～#18。整個監(jiān)測區(qū)域內間隔1.8 m設置參考采樣點,共90個。

圖2給出了位于(33.8,14.4)坐標的#18錨節(jié)點在每個采樣點的RSS測量值。由于信號的RSS值在負幾十dBm范圍,為了直觀顯示信號強度,顯示的時候每個RSS測量值加了100。從圖中可看出,不同采樣點采集的RSS信號強度變化較大,甚至在某些采樣點無法采集到有效的RSS信號。針對實際物理環(huán)境中RSS的分布,引入漂移函數來描述區(qū)域內RSS信號的非平穩(wěn)或區(qū)域異常變化;其次針對具體的監(jiān)測觀察區(qū)域,可根據物理布局劃分多個子塊進行變異函數的擬合,避免出現在全局范圍進行變異函數擬合時過于復雜、難以擬合的情況。

圖2 RSS信號在各采樣點的強度分布

2.2 擬合的變異函數和漂移函數

變異函數主要描述空間不同采樣距離與信號之間的關系;而這個關系在復雜室內環(huán)境下具有很強的局部性,隨空間布局而變化。圖3虛點線給出了4個錨節(jié)點在中央大廳區(qū)域采樣點的樣本變異函數。橫坐標是歸一化的分離距離。從圖3中可看出,處于空間不同位置的每個錨節(jié)點有自己獨特的變異函數。針對此實驗現象,為更準確描述信號的空間分布特性,對每個錨節(jié)點分別進行變異函數擬合。

圖3 樣本變異函數及擬合的理論變異函數

變異函數模型目前常用的有球狀模型[8,15]、高斯模型和指數模型,也有文獻采用高次多項式進行擬合[13-14]。具體采用何種理論模式可根據插值區(qū)域樣本變異函數的趨勢進行選擇,使擬合結果較優(yōu)。本文采用交叉驗證法進行檢驗,保證插值的剩余誤差平均值和方差最小[13]。圖3中實點線是其中#1、#6錨節(jié)點基于模型獲得的理論變異函數。這兩個錨節(jié)點分別采用指數模型和高斯模型確定理論變異函數。從圖中可看出不同錨節(jié)點擬合后的變異函數存在較大的差異,說明分布于走廊末端的1號錨節(jié)點與分布在中央大廳邊側的6號錨節(jié)點具有不同的信號傳播衰減特性,同時也表明在室內環(huán)境下,錨節(jié)點的分布會影響信號的變異模型。

通過實驗中采集的樣本數據,采用最小二乘法確定了漂移函數的系數β。表1給出了其中幾個錨節(jié)點的漂移函數系數。

表1 各錨節(jié)點漂移系數

2.3 插值結果與分析

圖4分別給出了#1與#12錨節(jié)點基于中央區(qū)域64個采樣點,插值形成484個位置指紋的RSS分布圖。每個錨節(jié)點插值時采用相應的變異函數參數和漂移系數。從圖4可看出錨節(jié)點有各自的RSS分布特性,插值形成的RSS與實測值基本吻合。

圖4 插值后的RSS分布

為了進一步分析擬合模型的有效性和準確性,采用了交叉證實法,從中央區(qū)域的64個采樣點,選取1個測量值,并從采樣值序列中暫時去除該值,利用余下的63個采樣點確定變異函數參數和漂移系數。再利用泛克里金預測該采樣點的估計值,并與實際測量值進行比較。圖5逐點給出了采樣區(qū)域內3個錨節(jié)點各自的擬合殘差,平均擬合殘差分別為4.3 dBm、3.5 dBm及9.1 dBm。從圖中可看出,某些位置的擬合殘差較大,甚至達到了20 dBm。分析采樣數據可發(fā)現,這些采樣點由于某些原因均未收到相應的錨節(jié)點信號,在指紋庫中記錄為-100 dBm,與其周圍采樣點的信號值有較大異常,很難用模型精確描述,插值結果也相對誤差較高。

圖5 擬合精度比較

3 定位精度分析

為了評估所提泛克里金插值方法構建指紋庫的性能,在監(jiān)測區(qū)域內隨機挑選了26個位置點在線采集RSS信號,基于不同的位置指紋庫,利用WKNN(WeightedK-nearest Neighbor)[16-17]算法進行定位。該算法比較在線采集的RSS信號與指紋庫內各指紋的歐氏距離,選取距離最小的K個指紋,并取歐氏距離的倒數作為權重,利用這K個指紋位置的加權平均作為估計位置來完成定位。本實驗中K取4。表2給出了相應的平均定位誤差。其中OK或UK分別指普通克里金插值和所提的泛克里金插值,其后的數字表示插值后形成的指紋庫的指紋數量,比如UK_484表示采用泛克里金插值形成484個指紋。IDW插值時采用了2種方法:IDW_484表示利用全部采樣點估計形成484個指紋,而IDW6_484則表示利用距離最近的6個采樣點插值估計形成484個指紋,其中距離指數都取2。

表2 基于不同指紋庫時的定位精度比較

由表2首先可知,不管采樣密度大小,基于UK_484指紋庫的定位精度均高于OK_484、IDW_484、IDW6_484及原指紋庫;當間隔1.8 m進行采樣,利用UK算法插值形成484個參考指紋后,定位精度甚至達到0.86 m,相比較基于原指紋庫的定位誤差1.56 m,定位誤差降低約45%;其次隨著插值點數量的減小,相應的定位精度也有所降低,但UK_225仍具有與OK_484相近的定位精度。

同時也可觀察到,隨著采樣點的稀疏,并不是插值密度越大,構建的指紋庫越能反映RSS分布特點。比如采樣點數量為16個時,UK_225的定位精度相對最高,而幾種不同方法生成的484插值點構成的指紋庫定位精度反而降低。這說明插值要根據采樣點的間隔選擇合理的插值密度。結合表中64個采樣點時基于UK_484的定位精度最高,而32個和16個采樣點時,分別是基于UK_225和UK_100指紋庫的定位精度相對高,說明6倍～8倍的插值密度較合適。另外從表中也觀察到,利用32個采樣點插值形成的UK_225與包含64個采樣點的原指紋庫的定位精度相當,說明適當降低離線階段的采樣數量,插值構建指紋庫后依舊可以得到相當的定位精度。

本實驗中走廊兩側共布置了18個錨節(jié)點,本文也分析研究了插值精度與錨節(jié)點數量的關系。表3給出了基于不用數量錨節(jié)點,利用UK插值構建指紋庫的定位誤差。

表3 錨節(jié)點數量對指紋庫構建精度的影響

從表3可看出,在本文實驗區(qū)域內,包含12個錨節(jié)點構建的指紋庫定位精度最高,而錨節(jié)點數量的減少對指紋庫精度影響不大,如在5個錨節(jié)點的情況下,UK_484的平均定位精度仍然達到了將近1 m;而過多的錨節(jié)點反而會引起定位精度下降。這也說明多個錨節(jié)點的RSS信號存在冗余,并且這種冗余反而使RSS的特征模糊,不利于定位匹配。在實際應用中,錨節(jié)點的數量也需要與監(jiān)測區(qū)域面積相匹配,布置過多的錨節(jié)點可能使RSS信號特征模糊,并不一定有利于定位精度的提高。

4 結束語

本文針對基于RSS信號的指紋定位技術,提出一種基于泛克里金插值的指紋預處理方式。根據每個錨節(jié)點RSS信號空間分布特點,構建相匹配的變異函數和漂移函數找到位置與RSS信號的關系,通過插值形成分布密度高的位置指紋從而降低離線階段的人力、時間成本或提高在線定位精度。實驗結果表明,①基于此方法構建的離線指紋庫在采用同樣的在線定位算法時有更高的定位精度,在本實驗中原始1.8 m的參考點密度經插值后定位精度可達約0.9 m;②為使構建的位置指紋庫能有效體現RSS信號的空間特性,插值點數量與采樣點的數量宜在6倍～8倍;③需根據監(jiān)測定位區(qū)域選擇合適數量的錨節(jié)點以構建最能反映空間信號特征的位置指紋庫;④基于泛克里金插值的指紋預處理方式能有效降低離線階段的人力和時間成本。