陶 冶，趙 龍

(1.北京航空航天大學(xué)自動(dòng)化科學(xué)與電氣工程學(xué)院，北京 100191； 2.北京航空航天大學(xué)數(shù)字導(dǎo)航中心，北京 100191)

0 引言

隨著移動(dòng)設(shè)備的發(fā)展，基于位置服務(wù)的需求越來(lái)越旺盛。在室外，可以通過(guò)衛(wèi)星信號(hào)獲得載體的高精度定位結(jié)果，但由于室內(nèi)環(huán)境的復(fù)雜性，使得衛(wèi)星信號(hào)在室內(nèi)無(wú)法定位。而基于WiFi的室內(nèi)定位技術(shù)不需要安裝額外的硬件，使得該項(xiàng)技術(shù)成為常用的室內(nèi)定位方案之一[1-2]。

基于WiFi的室內(nèi)定位技術(shù)通常被分為兩類，一類是基于三邊測(cè)距的定位算法[3]，另一類是基于指紋的定位算法。但在非視距的情況下，三邊測(cè)距的定位精度不如指紋定位。因此，WiFi指紋定位技術(shù)被廣泛研究和應(yīng)用。

通常WiFi指紋定位技術(shù)的流程分為兩步[4]，第一步：線下指紋庫(kù)的建立,該過(guò)程需要在線下采集不同點(diǎn)接收到的WiFi接入點(diǎn)(Access Point, AP)的信號(hào)強(qiáng)度，這些點(diǎn)又被叫作參考點(diǎn)；第二步：在線定位,該過(guò)程是將用戶上傳的測(cè)試數(shù)據(jù)與指紋庫(kù)中的信號(hào)強(qiáng)度進(jìn)行匹配，選擇匹配度高的參考點(diǎn)進(jìn)行加權(quán)平均定位。其定位步驟示意圖如圖1所示。

(a)離線采集 指紋庫(kù)

(b)采集測(cè)試 數(shù)據(jù)庫(kù)

(c)定位過(guò)程

WiFi指紋容易受到環(huán)境因素的影響，例如障礙物的移動(dòng)、溫度、濕度、AP發(fā)射功率和位置變化等，因此指紋庫(kù)的時(shí)效性很低，需要不斷地更新指紋庫(kù)來(lái)保證定位精度[5]。此外，不同的指紋匹配算法也會(huì)影響定位精度[6]。

在指紋匹配算法方面，較為經(jīng)典的算法有K近鄰(K-Nearest Neighbor，KNN)[7]和加權(quán)K近鄰(Weighted K-Nearest Neighbor，WKNN)算法[8]，但是這些算法都沒(méi)有考慮環(huán)境和指紋動(dòng)態(tài)特性對(duì)定位精度的影響，因此往往定位精度較低。針對(duì)部分AP休眠、位置改變和AP在線信號(hào)突然探測(cè)不到等現(xiàn)象引起的定位誤差問(wèn)題，DorFin[9]利用強(qiáng)回歸(Robust Regression)修正在線接收到的信號(hào)強(qiáng)度；LAAFU(Localization with Altered APs and Fingerprint Updating)[10]利用不同APs的信號(hào)強(qiáng)度子集篩除出變化的AP;自適應(yīng)區(qū)域搜索(Adap-tive Area Search，AAS)[11]利用參考點(diǎn)排序算法削弱這些現(xiàn)象對(duì)于定位的影響。但是這些算法都沒(méi)有考慮信號(hào)本身所具有的動(dòng)態(tài)變化問(wèn)題。對(duì)于信號(hào)自身存在的動(dòng)態(tài)變化問(wèn)題，在采集指紋庫(kù)時(shí)，往往通過(guò)在每一個(gè)參考點(diǎn)采集多組數(shù)據(jù)進(jìn)行平均來(lái)解決。但由于在線定位階段，用戶一般只在一個(gè)點(diǎn)停留1～2s，因此上傳的測(cè)試數(shù)據(jù)具有噪聲，無(wú)法很好地反映當(dāng)前測(cè)試點(diǎn)的真實(shí)信號(hào)強(qiáng)度。

在指紋庫(kù)更新算法方面，基于Matern核的Zero_GPR[12]算法得到了廣泛的研究，但是該算法沒(méi)有考慮WiFi信號(hào)自身的傳播特性；DNCIPS[13]利用在固定節(jié)點(diǎn)放置設(shè)備，實(shí)時(shí)采集信號(hào)強(qiáng)度，并通過(guò)WiFi信號(hào)傳播擬合公式(LDPL模型)[13]和基于SE核的高斯過(guò)程回歸(Gaussian Process Regres-sion，GPR)提出了LDPL_GPR算法進(jìn)行指紋庫(kù)更新，但是該算法需要在固定位置額外放置設(shè)備。

為了解決上述問(wèn)題，本文提出了一種新的WiFi室內(nèi)定位系統(tǒng)，該系統(tǒng)包括一個(gè)新的定位算法和指紋更新算法。新的定位算法改進(jìn)了基礎(chǔ)參考點(diǎn)排序算法，同時(shí)考慮了測(cè)試信號(hào)本身的動(dòng)態(tài)變化特性。該改進(jìn)算法將處于同一范圍內(nèi)的參考點(diǎn)排序視為與測(cè)試點(diǎn)具有相同的相似度，這是因?yàn)樗@取的測(cè)試信號(hào)強(qiáng)度受到了噪聲干擾，而這些噪聲使得參考點(diǎn)排序結(jié)果不穩(wěn)定，所以采用模糊化的方法會(huì)更好地刻畫每一個(gè)參考點(diǎn)與測(cè)試點(diǎn)之間的信號(hào)強(qiáng)度相關(guān)性。指紋庫(kù)自更新算法考慮了WiFi傳播特性，利用其傳播模型模擬每一個(gè)點(diǎn)的信號(hào)強(qiáng)度，并結(jié)合GPR算法以逼近真實(shí)的信號(hào)強(qiáng)度。與DNCIPS[13]不同的是，該算法利用上傳的測(cè)試數(shù)據(jù)預(yù)測(cè)未知點(diǎn)的信號(hào)強(qiáng)度，而不需要在固定位置處放置設(shè)備來(lái)實(shí)時(shí)獲得信號(hào)強(qiáng)度，這使得新的指紋更新算法更加靈活，且該算法利用Matern核更好地刻畫了坐標(biāo)點(diǎn)與相對(duì)應(yīng)的信號(hào)強(qiáng)度之間的非線性關(guān)系。

為了驗(yàn)證系統(tǒng)的有效性，在北京航空航天大學(xué)新主樓4層采集了真實(shí)數(shù)據(jù)，并與已有的算法進(jìn)行了大量的對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果顯示，該系統(tǒng)可以很好地提高定位精度和指紋更新精度。

1 系統(tǒng)簡(jiǎn)介

本文提出的WiFi室內(nèi)定位系統(tǒng)的實(shí)現(xiàn)過(guò)程示意圖如圖2所示，主要包括在線定位和在線指紋自更新兩部分。

圖2 WiFi定位系統(tǒng)實(shí)現(xiàn)過(guò)程Fig.2 Implementation process of WiFi positioning system

在線定位時(shí)，將接收到的測(cè)試點(diǎn)信號(hào)強(qiáng)度與指紋庫(kù)進(jìn)行對(duì)比，通過(guò)改進(jìn)的參考點(diǎn)排序算法進(jìn)行匹配得到定位結(jié)果(x,y)。由于改進(jìn)的參考點(diǎn)排序算法可以提供較高的定位精度，因此在線進(jìn)行指紋自更新時(shí)，LDPL_GPR+Matern算法將定位結(jié)果(x,y)作為真實(shí)位置，并利用對(duì)應(yīng)接收到的信號(hào)強(qiáng)度去預(yù)測(cè)其余未知點(diǎn)的信號(hào)強(qiáng)度，從而實(shí)現(xiàn)了指紋庫(kù)的在線自更新。

2 新定位系統(tǒng)的理論和算法

本節(jié)在簡(jiǎn)單介紹參考點(diǎn)排序算法的基礎(chǔ)上，重點(diǎn)介紹了改進(jìn)的參考點(diǎn)排序定位算法和指紋更新算法。

2.1 參考點(diǎn)排序

對(duì)于同一AP，首先計(jì)算參考點(diǎn)與測(cè)試點(diǎn)接收到的信號(hào)強(qiáng)度差的絕對(duì)值，其計(jì)算公式為[11]

errorji=|sij-tj|

(1)

式中，errorji表示第i個(gè)參考點(diǎn)接收到的第j個(gè)AP的信號(hào)強(qiáng)度與測(cè)試點(diǎn)接收到的第j個(gè)AP的信號(hào)強(qiáng)度之間差的絕對(duì)值；sij表示第i個(gè)參考點(diǎn)接收到的第j個(gè)AP的信號(hào)強(qiáng)度；tj表示測(cè)試點(diǎn)在線接收到的第j個(gè)AP的信號(hào)強(qiáng)度。

然后，將信號(hào)強(qiáng)度差的絕對(duì)值轉(zhuǎn)換為從1～m的排序，其轉(zhuǎn)換公式為[11]

rank(RPij)=find(errorji=sort(errorj))

(2)

式中，rank(RPij)表示第i個(gè)參考點(diǎn)接收到的第j個(gè)AP的信號(hào)強(qiáng)度與測(cè)試點(diǎn)接收到的第j個(gè)AP的信號(hào)強(qiáng)度之間的差在所有參考點(diǎn)與測(cè)試點(diǎn)信號(hào)強(qiáng)度差中的排序；errorj=[errorj1,errorj2,…,errorjm]；sort(*)表示對(duì)向量由小到大進(jìn)行排序；find(A==B)表示元素A在向量B中的索引；m表示參考點(diǎn)的數(shù)量。

同理，逐一計(jì)算參考點(diǎn)在每一個(gè)AP下的排序，然后計(jì)算每一個(gè)參考點(diǎn)在所有AP下的排序平均值，并將其作為該參考點(diǎn)的最終排序。其第i個(gè)參考點(diǎn)的綜合排序計(jì)算公式為[11]

(3)

式中，n表示AP的數(shù)量。

最后，根據(jù)每一個(gè)參考點(diǎn)的綜合排序，選擇排名靠前的k個(gè)參考點(diǎn)進(jìn)行加權(quán)平均定位，其對(duì)應(yīng)權(quán)重可表示為[11]

(4)

于是，最終的定位結(jié)果可表示為

(5)

式中，loci=(xi,yi)為所選取的第i個(gè)參考點(diǎn)的坐標(biāo)；loct為最終預(yù)測(cè)的測(cè)試點(diǎn)的位置結(jié)果。

2.2 改進(jìn)的參考點(diǎn)排序算法

圖3所示為1min內(nèi)在同一點(diǎn)連續(xù)接收同一AP的信號(hào)強(qiáng)度值的統(tǒng)計(jì)直方圖。從圖3中可以看出，信號(hào)強(qiáng)度會(huì)隨著時(shí)間的變化而變化，因此直接將絕對(duì)差值轉(zhuǎn)換為排序，忽略了信號(hào)強(qiáng)度動(dòng)態(tài)變化帶來(lái)的誤差，這會(huì)導(dǎo)致系統(tǒng)的定位精度降低。

圖3 1min收集到的定點(diǎn)信號(hào)強(qiáng)度分布Fig.3 Distribution of RSS collected at a fixed point in one minute

為解決該問(wèn)題，本文提出了一種改進(jìn)的算法，該算法采用模糊的思想，將處在同一個(gè)范圍內(nèi)的排序結(jié)果視為相同的排序，其數(shù)學(xué)表達(dá)式為

(6)

式中，β為長(zhǎng)度參數(shù)，控制排名的范圍。

由于參考點(diǎn)與測(cè)試點(diǎn)位置越接近，其對(duì)應(yīng)的參考點(diǎn)會(huì)在更多的AP下具有更好的排序?；谶@一事實(shí)，本文提出的改進(jìn)算法重新定義了參考點(diǎn)的綜合排序計(jì)算方法，其中第i個(gè)參考點(diǎn)的綜合排序計(jì)算公式可表示為

(7)

于是權(quán)重表示為

(8)

2.3 指紋更新算法

Zero_GPR[12，14]是一種適合非線性回歸問(wèn)題的無(wú)參數(shù)模型，可通過(guò)訓(xùn)練數(shù)據(jù)的輸入限制先驗(yàn)分布實(shí)現(xiàn)貝葉斯框架下的后驗(yàn)分布狀態(tài)預(yù)測(cè)，輸出預(yù)測(cè)的均值和方差，預(yù)測(cè)結(jié)果具備不確定表達(dá)能力。其回歸模型可表示為

s=f(w)+η

(9)

假設(shè)有m個(gè)訓(xùn)練數(shù)據(jù)，其輸入為w，則觀測(cè)值s的先驗(yàn)分布可表示為

f(w)～GP(0,k(wi,wj))

(10)

式中，核函數(shù)k(wi,wj)一般表示為SE核函數(shù)，其表達(dá)式為

(11)

且當(dāng)wi=wj時(shí)，有

(12)

式中，σf表示協(xié)方差因子；l表示長(zhǎng)度參數(shù)。

對(duì)于未知點(diǎn)w*處信號(hào)強(qiáng)度的預(yù)測(cè)值s*和觀測(cè)值s之間服從聯(lián)合分布

(13)

式中

預(yù)測(cè)值的后驗(yàn)分布模型為

(14)

因此，未知點(diǎn)處信號(hào)強(qiáng)度的預(yù)測(cè)均值為

s*=K*K-1s

(15)

在文獻(xiàn)[12]中發(fā)現(xiàn)，基于高斯過(guò)程回歸的GPR模型，使用Matern核對(duì)信號(hào)強(qiáng)度的預(yù)測(cè)效果要優(yōu)于使用SE核的預(yù)測(cè)效果，Matern核的表達(dá)式為

(16)

而單獨(dú)使用Zero_GPR預(yù)測(cè)未知點(diǎn)的信號(hào)強(qiáng)度時(shí)，在預(yù)測(cè)遠(yuǎn)離訓(xùn)練點(diǎn)的未知點(diǎn)的信號(hào)強(qiáng)度的預(yù)測(cè)均值在0附近，這顯然不符合WiFi信號(hào)強(qiáng)度的傳播特性。本文結(jié)合WiFi傳播模型，對(duì)基于Matern核的Zero_GPR算法進(jìn)行了改進(jìn)，并提出了LDP_GPR+Matern預(yù)測(cè)模型。WiFi傳播模型可表示為L(zhǎng)DPL模型[13]，其表達(dá)式為

(17)

式中，wAP=[xAP,yAP]；C表示參考點(diǎn)距離AP為1m時(shí)接收到的信號(hào)強(qiáng)度；α為衰減系數(shù)。

對(duì)于w*接收到第j個(gè)AP的信號(hào)強(qiáng)度的預(yù)測(cè)表達(dá)式為

(18)

本文利用最小殘差思想求解Cj、α、xAPj、yAPj，其目標(biāo)函數(shù)表達(dá)式為

(19)

本文利用最大似然估計(jì)求解LDPL_GPR+Matern算法的最優(yōu)參數(shù)l、σn，其目標(biāo)函數(shù)表達(dá)式為

(20)

式中，z=s-m(w)。

在此基礎(chǔ)上，本文利用煙花算法[15]進(jìn)行尋優(yōu)求解以獲得所求參數(shù)。

3 實(shí)驗(yàn)驗(yàn)證與分析

3.1 實(shí)驗(yàn)環(huán)境與測(cè)試條件

為了驗(yàn)證系統(tǒng)中算法的有效性，在北京航空航天大學(xué)新主樓4層采集數(shù)據(jù)，并進(jìn)行了實(shí)驗(yàn)驗(yàn)證。圖4所示為實(shí)驗(yàn)環(huán)境的布局，長(zhǎng)為70m，寬為15m。圖4中，紅色圓圈表示線下建庫(kù)時(shí)的指紋參考點(diǎn)，一共125個(gè)，每一個(gè)參考點(diǎn)的采樣時(shí)間為60s；綠色方框點(diǎn)表示在線測(cè)試點(diǎn)，一共79個(gè)，實(shí)驗(yàn)過(guò)程中每一個(gè)測(cè)試點(diǎn)的采樣時(shí)間為1～2s。為了測(cè)試算法在陌生環(huán)境下的工作性能，沒(méi)有對(duì)AP的相關(guān)信息(位置、發(fā)射功率等)進(jìn)行提前調(diào)研，所探測(cè)到的AP的信息均是未知的，在這樣的環(huán)境下進(jìn)行實(shí)驗(yàn)測(cè)試更能說(shuō)明算法的普適性。本文利用熵信息[16]篩選出50個(gè)區(qū)分度大的AP進(jìn)行定位，以減少在線定位運(yùn)算時(shí)間。

圖4 實(shí)驗(yàn)區(qū)域分布圖Fig.4 Layout of experimental area

3.2 定位實(shí)驗(yàn)結(jié)果及分析

為驗(yàn)證定位算法的有效性，本次實(shí)驗(yàn)利用參考點(diǎn)預(yù)測(cè)79個(gè)測(cè)試點(diǎn)的位置，且實(shí)驗(yàn)時(shí)設(shè)置了不同的β值進(jìn)行了多次定位實(shí)驗(yàn)，最終取平均結(jié)果代表該改進(jìn)排序算法的最終定位精度，β=(0.04,0.08,0.12,0.16,0.20,0.24,0.28,0.32)。將所提算法的定位結(jié)果與KNN、WKNN和已有的參考點(diǎn)排序算法進(jìn)行對(duì)比分析。文中KNN與WKNN算法使用測(cè)試點(diǎn)與參考點(diǎn)之間信號(hào)強(qiáng)度的歐式距離篩選與測(cè)試點(diǎn)相似的參考點(diǎn)，且將歐氏距離的倒數(shù)作為WKNN算法中相似參考點(diǎn)的權(quán)重。當(dāng)k=5時(shí)，不同算法的累計(jì)誤差概率分布(Cumulative Distribu-tion Function，CDF)如圖5所示。

圖5 不同算法的累計(jì)誤差概率分布圖Fig.5 Cumulative distributions of positioning error of different algorithms

從圖5中可以看出，基于參考點(diǎn)排序和改進(jìn)的參考點(diǎn)排序算法的定位結(jié)果曲線幾乎都位于KNN和WKNN定位曲線的上方，這說(shuō)明基于參考點(diǎn)排序算法是有效的，而且改進(jìn)算法的定位結(jié)果相對(duì)于參考點(diǎn)排序算法在均值誤差和標(biāo)準(zhǔn)差方面均有所提升。為了進(jìn)一步量化所提算法的優(yōu)越性，對(duì)定位結(jié)果進(jìn)行了相應(yīng)的統(tǒng)計(jì)，統(tǒng)計(jì)結(jié)果如表1所示。

表1 不同算法的定位結(jié)果統(tǒng)計(jì)

為進(jìn)一步說(shuō)明改進(jìn)算法的優(yōu)勢(shì)，本次實(shí)驗(yàn)統(tǒng)計(jì)了k取不同值時(shí)不同算法的定位精度，其結(jié)果分別如圖6和表2所示。其中，圖6所示為k取不同值時(shí)不同算法的均值誤差；表2所示為k取不同值時(shí)不同算法的均值誤差和標(biāo)準(zhǔn)差。從圖6和表2中可以看出，在均值誤差方面，改進(jìn)的參考點(diǎn)排序算法相對(duì)于KNN、WKNN和參考點(diǎn)排序算法分別提升了25.52%、25.52%和4.05%；在標(biāo)準(zhǔn)差方面，改進(jìn)的算法相對(duì)于KNN、WKNN和參考點(diǎn)排序算法分別提升了33.86%、30.86%和8.70%。

圖6 不同算法下的平均定位誤差Fig.6 Mean positioning errors with different algorithms

表2 不同算法的定位結(jié)果統(tǒng)計(jì)

3.3 指紋更新實(shí)驗(yàn)結(jié)果及分析

為了驗(yàn)證指紋更新算法的有效性，本次實(shí)驗(yàn)利用參考點(diǎn)預(yù)測(cè)40個(gè)測(cè)試點(diǎn)的位置，在定位的基礎(chǔ)上，利用40個(gè)點(diǎn)的信息和指紋更新算法預(yù)測(cè)剩下39個(gè)測(cè)試點(diǎn)的信號(hào)強(qiáng)度，并與真實(shí)信號(hào)強(qiáng)度進(jìn)行對(duì)比，得到信號(hào)強(qiáng)度的預(yù)測(cè)誤差。本次實(shí)驗(yàn)將LDPL_GPR+Matern的預(yù)測(cè)結(jié)果分別與ZERO_GPR+SE和ZERO_GPR+Matern進(jìn)行對(duì)比，不同算法預(yù)測(cè)結(jié)果的均值誤差和標(biāo)準(zhǔn)差如表3所示。

表3 不同算法的信號(hào)強(qiáng)度預(yù)測(cè)誤差統(tǒng)計(jì)

從表3中可以看出，ZERO_GPR+Matern算法的均值誤差和標(biāo)準(zhǔn)差比ZERO_GPR+SE算法的都小，這說(shuō)明Matern核相較于SE核確實(shí)更適用于預(yù)測(cè)WiFi信號(hào)的信號(hào)強(qiáng)度。與ZERO_GPR+Matern相比，LDPL_GPR+Matern的標(biāo)準(zhǔn)差幾乎保持不變的同時(shí)，均值誤差降低了34.52%，這說(shuō)明結(jié)合LDPL模型和GPR模型可以有效提高對(duì)于未知點(diǎn)信號(hào)強(qiáng)度的預(yù)測(cè)精度。

4 結(jié)論

本文提出了一種新的WiFi指紋定位系統(tǒng)，該系統(tǒng)可以長(zhǎng)期封閉式運(yùn)行，且保持較高的定位精度。該系統(tǒng)在定位方面，改進(jìn)了參考點(diǎn)排序算法，以提升定位精度；在指紋更新方面，利用LDPL模型和基于Matern核的GPR算法在線進(jìn)行指紋自更新，以避免線下指紋庫(kù)更新的繁瑣。根據(jù)相關(guān)分析及實(shí)驗(yàn)結(jié)果表明：

1)所提出的基于模糊思想的參考點(diǎn)排序算法，考慮了WiFi自身的動(dòng)態(tài)特性。相較于傳統(tǒng)的定位算法(KNN和WKNN)，該算法能夠提升25%以上的定位精度。

2)所提出的指紋更新算法利用Matern核更好地刻畫了參考點(diǎn)坐標(biāo)和RSS之間的非線性關(guān)系，且使用LDPL模型克服了Zero-GPR的零均值問(wèn)題。相較于已有的指紋更新算法，該算法能夠提升34%以上的指紋還原精度。

在未來(lái)的工作中，將探索不同的長(zhǎng)度參數(shù)β對(duì)于定位結(jié)果的影響，以及嘗試尋找合適的參數(shù)自適應(yīng)確定方法。