樂燕芬,張賀娜,施偉斌

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

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

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

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

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

1 泛克里金插值算法原理

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

(1)

變異函數(shù)γ也稱為半方差函數(shù),定義為:

(2)

該函數(shù)只與采樣點(diǎn)間的分離距離h有關(guān),而與位置s和s+h無關(guān),反映信號的空間結(jié)構(gòu)性和隨機(jī)性變化。實(shí)際應(yīng)用時,常用樣本變異函數(shù)擬合獲得理論變異函數(shù)。樣本變異函數(shù)的計(jì)算采用下式:

(3)

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

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

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

(4)

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

(5)

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

(6)

式中:

(7)

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

(8)

即要滿足:

FTW=F0

(9)

式中

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

(10)

此時估計(jì)方差可表示為:

(11)

式中:

(12)

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

(13)

這樣問題就轉(zhuǎn)化為:

(14)

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

(15)

式中:λ是引入的Lagrange算子。解此方程可得權(quán)重系數(shù)wn。

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

(16)

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

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

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

2 基于泛克里金的RSS插值

2.1 數(shù)據(jù)預(yù)處理

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

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

圖2 RSS信號在各采樣點(diǎn)的強(qiáng)度分布

2.2 擬合的變異函數(shù)和漂移函數(shù)

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

圖3 樣本變異函數(shù)及擬合的理論變異函數(shù)

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

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

表1 各錨節(jié)點(diǎn)漂移系數(shù)

2.3 插值結(jié)果與分析

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

圖4 插值后的RSS分布

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

圖5 擬合精度比較

3 定位精度分析

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

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

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

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

本實(shí)驗(yàn)中走廊兩側(cè)共布置了18個錨節(jié)點(diǎn),本文也分析研究了插值精度與錨節(jié)點(diǎn)數(shù)量的關(guān)系。表3給出了基于不用數(shù)量錨節(jié)點(diǎn),利用UK插值構(gòu)建指紋庫的定位誤差。

表3 錨節(jié)點(diǎn)數(shù)量對指紋庫構(gòu)建精度的影響

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

4 結(jié)束語

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