任建新，自俊林，宋凱月

(西北工業(yè)大學(xué)自動化學(xué)院，西安 710072)

0 引言

無線局域網(wǎng)絡(luò)(Wireless Local Area Networks,WLAN)室內(nèi)定位技術(shù)屬于無線局域網(wǎng)定位技術(shù)，是當前最主要的室內(nèi)定位技術(shù)之一，具有十分廣泛的應(yīng)用前景。由于WLAN技術(shù)的飛速發(fā)展以及網(wǎng)絡(luò)的迅速普及，越來越多的路由器接入點(Access Point,AP)被安置在各種公共場所。只要人們攜帶配置了無線網(wǎng)卡的設(shè)備進入AP覆蓋區(qū)域，即可掃描連接到該AP所在的網(wǎng)絡(luò)，進而進行聯(lián)網(wǎng)活動。隨著AP布設(shè)范圍越來越廣以及人們對室內(nèi)定位需求的增加，越來越多的科研人員與工作者將目光放在AP發(fā)出的WLAN信號與接入設(shè)備位置之間的關(guān)系。目前，WLAN室內(nèi)定位技術(shù)主要是基于傳播模型[1]或場景分析[2]兩種原理。

基于傳播模型的WLAN室內(nèi)定位技術(shù)通過獲得AP位置和接收者與AP之間的距離反推接收者位置，主要利用幾何學(xué)的計算方法，其中以三邊定位法[3-4]為主。基于場景分析的WLAN室內(nèi)定位技術(shù)通過事先獲取定位區(qū)域不同位置點的信號特征，與接收端獲取的信號特征進行匹配，進而判斷接收者位置，主要方法為位置指紋定位法[5-6]。

本文介紹了三邊定位法和位置指紋法，分析了上述兩種WLAN定位方法的優(yōu)缺點，結(jié)合現(xiàn)有方法的優(yōu)點并針對實際工作條件進行改進，提出新的定位解算方法——粗定位迭代校準法。通過設(shè)計實驗驗證新算法的實時性和可靠性，并得到以下結(jié)論：

1)粗定位迭代校準法的定位結(jié)果能夠滿足行人定位需求，定點定位精度2～3m，移動定位精度3～5m，表明了該算法具有可靠性。

2)相比于一般加權(quán)K近鄰算法(Weighted K-Nearest Neighborhood,WKNN)，迭代算法通過控制運算量，大大降低了運行時間，單次定位所使用的時間可控制在2ms以內(nèi)。

1 三邊定位法

三邊定位法在定位過程中主要分為2個環(huán)節(jié)，分別是測距環(huán)節(jié)與定位環(huán)節(jié)。

1.1 測距環(huán)節(jié)

使用三邊定位法計算位置目標，首先需要在定位區(qū)域內(nèi)安裝至少3臺不共線AP，且3臺AP位置信息已知。當待定目標進入AP覆蓋區(qū)域后，接收端分別接收來自3臺AP發(fā)出的無線信號，同時獲得不同信號的接收信號強度(Received Signal Strength Indication，RSSI)。根據(jù)式(1)的無線信號傳播模型即可計算得到接收機端與AP之間的距離

(1)

其中，Pr(d)為接收機端接收到的無線電信號功率；Pt為發(fā)射端即AP的發(fā)射功率；Gt為發(fā)射端增益；Gr為接收端增益；λ為無線電電波波長；L為損耗系數(shù)，由信號傳播環(huán)境決定；d為接收端與發(fā)射端之間的距離，即無線電傳播距離。

然而，在實際無線電信號傳播過程中，上述傳播模型往往會受到路徑損耗、物體遮擋[7]等因素的影響而導(dǎo)致計算結(jié)果不準確。因此，在實際應(yīng)用中，通常采用式(2)所述模型進行測距

Pr(d)=K-10εlg(d)

(2)

其中，ε為實際環(huán)境中無線電信號損耗系數(shù)；K為發(fā)射端發(fā)射功率，對于每臺固定AP而言通常為常值。

1.2 定位環(huán)節(jié)

如圖1所示，利用幾何關(guān)系計算接收機位置。圖1中，A、B、C為3臺AP位置且坐標已知，分別為(x1,y1)、(x2,y2)、(x3,y3)，D為待定位目標位置(x,y)，AD、BD、CD為待定位目標與3臺AP間的距離，分別為d1、d2、d3。將方程式(3)、式(4)、式(5)聯(lián)立求解出目標位置

(3)

(4)

(5)

圖1 三邊定位法示意圖Fig.1 Schematic of trilateral positioning method

但是，非理想情況下，三圓很難相交于一點，極大可能出現(xiàn)未相交空白區(qū)域或者三圓重疊區(qū)域，導(dǎo)致上述方程聯(lián)立求解時無解。針對三圓出現(xiàn)未相交空白區(qū)域或者三圓重疊區(qū)域兩種情況，可以使用三圓多個交點坐標計算近似坐標作為目標位置，近似坐標求解思路如下：

根據(jù)方程式(3)和式(4)聯(lián)立求解得到A圓與B圓的2個交點坐標(xAB1,yAB1)和(xAB2,yAB2)，將交點坐標與圓心C坐標代入平面兩點距離式(6)

(6)

式中，P1(xP1,yP1)和P2(xP2,yP2)為兩點坐標；dP1P2為兩點距離。計算兩圓交點與圓心C之間的距離，取距離圓心C較近交點作為近似坐標計算點，記為(xAB,yAB)。同理，按照相同的方法，可計算出近似坐標計算點(xAC,yAC)和(xBC,yBC)。3個近似坐標計算點的均值即為定位點坐標，如式(7)所示

(7)

除此之外，三邊定位法還存在AP的選擇問題。在實際應(yīng)用中，觀測到的AP數(shù)量往往多于3個，如果直接選擇信號最強的3臺AP進行三邊定位，有可能導(dǎo)致DOP不佳，并且丟失信息。在AP數(shù)量多于3個的情況下可以基于信息增益[8](Infor-mation Gain，InfoGain)方法，選擇最能反映待定位點信息的AP，根據(jù)InfoGain準則估計每一個AP的區(qū)分度能力D，并選擇區(qū)分度能力最高的3個AP用于三邊定位。

三邊定位法的精度主要由測距環(huán)節(jié)得到的3個距離精度決定，而距離精度又由無線電信號傳播模型精度決定。在實際環(huán)境中，傳播模型中的損耗系數(shù)難以準確確定，不同室內(nèi)環(huán)境中的信號傳播模型均不一樣。所以，在實際應(yīng)用中使用三邊定位法難以實現(xiàn)較為準確的定位目的，但是該方法根據(jù)3個信號強度值及3臺AP坐標即可推算自身坐標位置，具有運算速度快的優(yōu)點。

2 位置指紋定位法

位置指紋定位法利用接收機端RSSI與接收端物理位置之間的關(guān)聯(lián)性進行定位，指紋定位工作流程主要分為離線數(shù)據(jù)采集建立指紋庫環(huán)節(jié)和在線位置解算環(huán)節(jié)[9]。

2.1 離線環(huán)節(jié)

離線環(huán)節(jié)的主要工作是對定位區(qū)域進行指紋網(wǎng)格劃分，確定指紋點坐標，采集指紋點(Finger Point,FP)處WLAN信息，包括MAC地址和RSSI值，將三者合并作為一條指紋信息保存起來，所有指紋信息將構(gòu)成定位所需的指紋數(shù)據(jù)庫。離線環(huán)節(jié)中對定位區(qū)域進行指紋網(wǎng)格劃分，確定指紋點坐標如圖2所示。在圖2中，AP1、AP2、AP3及AP4是在定位區(qū)域內(nèi)布設(shè)的4臺AP，其坐標已知；FP1、FP2、FP3、…、FP16為通過網(wǎng)格劃分得到的指紋點。將每個指紋點分別接收到4臺AP的RSSI記為RSSI1、RSSI2、RSSI3、RSSI4，則指紋的信息采集如圖3所示。

圖2 指紋網(wǎng)格劃分示意圖Fig.2 Fingerprint grid division diagram

圖3 指紋點信息采集Fig.3 Fingerprint points information collection

2.2 在線環(huán)節(jié)

指紋庫建立完成后，接收端進入定位區(qū)域并采集所處位置接收到的所有WLAN信號的MAC地址及RSSI值。采集完畢后，首先篩選有效定位AP信息，將不在指紋庫內(nèi)或者強度非常低的AP濾除，以免干擾指紋匹配導(dǎo)致指紋點漏選或錯選。篩選完畢后，將剩余AP信息與指紋庫內(nèi)指紋點信息進行比對，選出相似程度最大的指紋點，即最接近當前所處位置的指紋點。指紋定位流程如圖4所示。

圖4 指紋定位流程Fig.4 Fingerprint location process

當接收端獲取掃描到AP信號的MAC地址及RSSI值后，需要從指紋庫中尋找到最為相似的指紋點用于坐標解算。目前所應(yīng)用的指紋點匹配方法很多，包括：最近鄰法(Nearest Neighborhood,NN)、K近鄰算法(K-Nearest Neighborhood,KNN )、WKNN神經(jīng)網(wǎng)絡(luò)法、支持向量回歸法[10]等。由于本文以手機作為接收端實現(xiàn)WLAN定位，從程序運算量及手機處理器運算性能考慮，所選方法運算量和數(shù)據(jù)量不能過大，所以本文對前三種方法進行對比介紹[11-12]。

2.2.1 最近鄰法

最鄰近法首先根據(jù)接收端實時采集到的RSSI值與指紋庫內(nèi)的指紋點RSSI值,計算二者之間的歐氏距離，如式(8)所示

(8)

2.2.2 K近鄰算法

K近鄰法是最近鄰法的改進，利用式(8)計算得到所有指紋點的歐氏距離后，選取K(K≥2)個距離最小的指紋點，將這K個指紋點坐標進行均值計算得到接收端位置坐標，如式(9)所示

(9)

最近鄰法可以看成是K=1時的K近鄰法，相比于最近鄰法，K近鄰法提高了定位精度。

2.2.3 加權(quán)K近鄰算法

考慮到K近鄰算法中所選取的K個指紋點RSSI值與實測RSSI值之間的差別，相應(yīng)地,最終計算坐標時的貢獻也有所不同，與實測點距離更近的指紋點RSSI值匹配程度更高。因此，在坐標計算時權(quán)重更高。式(9)中的均值計算方法導(dǎo)致更有利于定位的指紋點沒有被充分利用。加權(quán)K近鄰算法坐標計算如式(10)所示

(10)

其中，di為第i個指紋點與實測點間的歐式距離；η為歸一化加權(quán)系數(shù)；ε為避免分母為0而設(shè)計的很小的常值。式中，加權(quán)系數(shù)與歐式距離成反比，保證距離實測點越近的指紋點在計算坐標時貢獻越大，從而在一定程度上提高了系統(tǒng)的定位精度。

最近鄰法、K近鄰算法和加權(quán)K近鄰算法在定位精度上逐步提高，但運算量也相對增大，目前主要以加權(quán)K近鄰算法作為指紋匹配算法。

3 粗定位迭代校準法

三邊定位法定位迅速、計算量小，但由于環(huán)境因素對無線信號影響的不確定性導(dǎo)致其精度降低；位置指紋定位法事先采集環(huán)境中的信號特征，在一定程度上弱化了環(huán)境因素的影響，提高了定位精度，但隨著定位區(qū)域的擴大，指紋點數(shù)量激增，利用指紋法計算位置時會存在大量無關(guān)指紋點計算，增大了計算量，影響實時性?？紤]兩種方法的工作原理，若將兩種方法進行融合，利用三邊定位法確定大致區(qū)域范圍，再從指紋庫中提取出該范圍內(nèi)的相關(guān)指紋點，進而利用指紋法進行定位，則可以大大提高精度且減少運算時間。但如果三邊定位法所確定范圍偏差較大，則直接影響后續(xù)指紋法的定位精度。因此，本文提出了利用多次定位迭代校準的方法修正初始定位偏差，將三邊定位法、指紋定位加權(quán)K近鄰算法和迭代校準三部分融合成新的定位算法——粗定位迭代校準法。

粗定位迭代校準法的思想是，首先使用三邊定位法粗略確定接收機位置，然后多次利用小范圍指紋定位不斷將計算坐標向真實坐標逼近。此種方法既可以彌補初始三邊定位誤差較大的缺陷，又可以節(jié)約直接使用指紋法時計算大量無關(guān)指紋點消耗的時間。粗定位迭代校準法示意圖如圖5所示。圖5中，矩形框為整體定位區(qū)域，四角黑色實心圓點為4臺定位AP，矩形框內(nèi)空心圓和交叉線圓點為指紋點，其中交叉圓點代表迭代定位區(qū)域圓心，黑色五角星為行人實際位置，黑色三角形為三邊定位法定位結(jié)果。

圖5 粗定位迭代校準法示意圖Fig.5 Rough positioning iterative calibration method diagram

首先，利用三邊定位法計算得到初始坐標，即黑色三角形位置。以該初始坐標為圓心確定初始定位區(qū)域R1，只選用該區(qū)域內(nèi)的指紋點做WKNN算法計算，該次計算結(jié)果落于R1范圍內(nèi)，但位于接近五角星方向。該次計算除了得到坐標值，同時還保留了WKNN法計算時權(quán)重最高的指紋點，權(quán)重越高代表距離實際距離越近，即圖5中的交叉圓點FP1。以FP1作為圓心確定新的定位區(qū)域R2，R2相比R1距離實際距離更近，重復(fù)上述工作得到FP2、R3、FP3、R4……直到某2次WKNN法計算結(jié)果差值小于設(shè)定閾值，則認為所選定位區(qū)域覆蓋實際位置，定位完成。

由于粗定位迭代校準法中迭代校準環(huán)節(jié)可有效彌補三邊定位法初始坐標計算誤差較大的缺陷，所以在使用三邊定位法粗略計算接收機位置時可不用式(1)或式(2)所述模型，根據(jù)式(11)和式(12)進行三邊定位法計算初始坐標

(11)

(12)

式中，(X,Y)為初始定位坐標；(Xi,Yi)為用于計算的AP坐標；K為AP數(shù)量；RSSIi為接收機收到每臺AP的信號強度。在式(11)、式(12)中只使用了信號強度一個參數(shù)，而式(1)或式(2)所述模型均需要已知大量如發(fā)射功率、接收功率等相關(guān)參數(shù)。因此，利用式(11)、式(12)計算初始坐標降低了運算的復(fù)雜度，減少了運算時間。

4 實驗驗證與分析

為了驗證本文所提出的粗定位迭代校準法的可行性，進行了包括定點定位實驗、行走定位實驗以及運算速度檢測3個部分的實驗，以驗證該定位算法下WLAN定位的定位精度以及該定位算法的實時性。實驗過程中以手機作為信號接收端。

4.1 WLAN定點定位實驗

用于定點定位實驗的實驗室平面圖如圖6所示。實驗室長7.5m，寬7.5m，在四角布置4臺家用普通AP，實驗室內(nèi)擺放有金屬柜、桌椅、金屬實驗器材等物件，對WLAN信號有一定干擾作用，可認為實驗室接近或等同真實使用環(huán)境，定位結(jié)果具有實際參考意義。

圖6 實驗室平面示意圖Fig.6 Laboratory plan diagram

圖6中，黑色實心圓點代表4臺AP，分別布置在4個角落。室內(nèi)坐標系以左下角為原點，X軸正向向右，Y軸正向向上。

在實驗室內(nèi)以1.8m為間隔選取指紋點，共25個指紋點。實驗室內(nèi)隨機設(shè)立10個測試點，覆蓋實驗室角落、邊緣和中心地帶，每個測試點采集100組有效定位數(shù)據(jù)，共1000組有效數(shù)據(jù)。以實驗室選取的測試點真實坐標值為實際坐標，每一測試點的100組計算坐標的均值作為定位坐標，定位坐標與實際坐標間的距離為坐標誤差，100組定位誤差的均值為誤差平均值。得到的定點定位實驗數(shù)據(jù)見表1。

表1 定點定位坐標及誤差Tab.1 Fixed points positioning coordinates and errors cm

1000組定位誤差累積分布曲線如圖7所示。由表1的定位誤差數(shù)據(jù)可得，10組測試數(shù)據(jù)的單次定位誤差主要集中在2～3m，而每一測試點100組數(shù)據(jù)平均后的定位誤差，即表1中的坐標誤差主要在2m以內(nèi)。同時，由圖7的累積分布曲線可得，1000次定位結(jié)果中95%的定位誤差在3.3m以內(nèi)，67%在2m以內(nèi)，50%在1.5m以內(nèi)，定位精度較高。

圖7 定位誤差累積分布曲線Fig.7 Positioning error cumulative distribution curve

綜上所述，對于移動緩慢或者靜止狀態(tài)的定位對象，可以通過多次定位求平均值的方法提高定位精度。

4.2 WLAN行走定位實驗

行走定位實驗的實驗場地為實驗室所在地的主樓，主樓定位區(qū)域由3條室內(nèi)走廊及1條室外走廊構(gòu)成。每條走廊長約64m，寬約2.3m，室內(nèi)走廊每間隔15m安裝1臺吸頂AP，共11臺。圖8所示為主樓平面示意圖，黑心實圓點代表11臺AP，主樓坐標系以左下角為原點，X軸正向向右，Y軸正向向上。

圖8 主樓平面示意圖Fig.8 Main building floor plan diagram

在行走定位實驗時，主樓走廊以2.5m間隔選取指紋點，共102個。移動實驗路線為U型走廊一端至另一端，為計算并分析定位精度，在移動路線上選取20個位置作為測試點,且每次定位解算為單次掃描，即每個測試點只采集1組數(shù)據(jù)。20個測試點定位解算結(jié)果及對應(yīng)誤差數(shù)據(jù)見表2。根據(jù)表1和表2的誤差數(shù)據(jù)可知，在移動過程中，坐標誤差要大于定點實驗的坐標誤差。如表2所示，行走定位實驗的坐標誤差一般為3～5m。

表2 定位測試點坐標及誤差Tab.2 Positioning test point coordinates and error cm

4.3 WLAN定位算法速度檢測

為了驗證迭代算法與一般WKNN算法的計算速度，本文在已有指紋庫的基礎(chǔ)上利用插值方法進行擴充，得到粗定位迭代校準法與一般WKNN法的運行時間見表3。

表3 迭代算法與一般WKNN法運行時間Tab.3 Iterative algorithm and general WKNN method running time

由表3可以看出，相比于一般WKNN法，迭代算法有效地控制了運算量，極大程度地降低了運算時間。

5 結(jié)論

本文首先介紹了WLAN室內(nèi)定位技術(shù)的兩種基本原理以及基于不同原理的定位方法，主要是：三邊定位法和位置指紋定位法；闡述了兩種主要方法的工作原理并對比分析其優(yōu)缺點；結(jié)合現(xiàn)有方法的優(yōu)點并針對實際工作條件進行改進，提出了新的定位解算方法：粗定位迭代校準法。通過設(shè)置合適的實驗環(huán)境，利用已有WLAN設(shè)備或鋪設(shè)WLAN設(shè)備設(shè)計實驗驗證算法的可行性。實驗共分為定點定位實驗、行走定位實驗以及運算速度檢測3個部分。綜合上述3個部分的實驗數(shù)據(jù)結(jié)果表明，本文提出的粗定位迭代校準法在初始階段使用三邊定位法確定粗略位置可以大大減少無關(guān)指紋點的計算量，引入迭代校準定位方式可以有效降低初始三邊定位大誤差對最終結(jié)果的影響。從定位結(jié)果來看，定點定位精度2～3m，移動定位精度3～5m，不存在定位失效情況，滿足行人定位需求。并且此種定位思想大大減少了計算量，降低了運算時間，單次定位所使用的時間可控制在2ms以內(nèi)，大大降低了運行時間。