基于偏度-峰度檢驗(yàn)的無線局域網(wǎng)室內(nèi)定位算法

宋震龍，蔣剛毅，黃晁，郁梅，張家樂

（1.寧波大學(xué) 信息科學(xué)與工程學(xué)院，浙江 寧波 315211；2.中國科學(xué)院 計(jì)算技術(shù)研究所，北京 100080；3.寧波中科集成電路設(shè)計(jì)中心，浙江 寧波 315040）

1 引言

隨著物聯(lián)網(wǎng)和智慧城市建設(shè)的興起和快速發(fā)展，基于位置的服務(wù)應(yīng)用越來越廣泛。傳統(tǒng)的GPS和蜂窩網(wǎng)定位技術(shù)在室外能達(dá)到較高的定位精度，但在室內(nèi)環(huán)境下，由于射頻信號(hào)受到阻隔而無法有效定位。學(xué)者們提出了許多針對室內(nèi)定位的定位技術(shù)，其中 WLAN定位技術(shù)可以充分利用已經(jīng)普遍存在的無線局域網(wǎng)資源，不需要部署其他硬件設(shè)施，具有低成本優(yōu)勢。因此基于 WLAN的室內(nèi)定位技術(shù)越來越受到關(guān)注[1～3]。

目前 WLAN室內(nèi)定位方法中應(yīng)用最普遍的是位置指紋定位法[4～6]，該方法分為離線訓(xùn)練和在線定位2個(gè)階段。離線訓(xùn)練階段在待定位區(qū)域選定一系列參考位置點(diǎn)，在這些參考位置點(diǎn)處采集來自不同無線接入點(diǎn)(AP, access point)的RSS值，將參考位置點(diǎn)坐標(biāo)和采集的RSS數(shù)據(jù)存儲(chǔ)在數(shù)據(jù)庫中，組成射電地圖(RM, radio map)。在線定位階段通過匹配算法比較實(shí)時(shí)采集的 RSS信息和射電地圖中的信息，估計(jì)用戶的位置。

室內(nèi)環(huán)境下射頻信號(hào)傳播非常復(fù)雜，墻壁、門窗和桌椅等基礎(chǔ)設(shè)施以及人員走動(dòng)的影響導(dǎo)致射頻信號(hào)傳播產(chǎn)生顯著的多徑現(xiàn)象和陰影效應(yīng)，因此室內(nèi)固定位置處 RSS信號(hào)的時(shí)變性很強(qiáng)[7,8]。Kaemarungsi統(tǒng)計(jì)了室內(nèi)WLAN環(huán)境下RSS樣本的總體分布情況[9]，共選取了299個(gè)RSS樣本，每個(gè)樣本中含有2 962～3 956個(gè)RSS信號(hào)值，統(tǒng)計(jì)結(jié)果表明，有214個(gè)樣本（約占總樣本數(shù)的71.6%）的總體分布服從正態(tài)分布，其余樣本的總體分布則表現(xiàn)為嚴(yán)重左偏、嚴(yán)重右偏、多峰或其他非正態(tài)分布。RSS樣本總體分布不一致，使室內(nèi)定位產(chǎn)生較大的定位誤差[9～11]。Yousief等人提出了一種直方圖室內(nèi)定位算法[12]，但是RSS樣本直方圖不平滑，經(jīng)常出現(xiàn)一些零值，定位精度不高。Kushki等人提出了一種基于核函數(shù)的定位方法[13]，在RSS樣本總體分布未知的情況下，利用核函數(shù)估計(jì)總體的概率密度，但有限的 RSS樣本數(shù)據(jù)無法準(zhǔn)確估計(jì)樣本總體的分布。Ma等人提出用多項(xiàng)式函數(shù)擬合RSS樣本的概率直方圖分布[14]，但這種方法有時(shí)會(huì)出現(xiàn)函數(shù)不收斂的情況，無法準(zhǔn)確擬合出樣本總體的分布函數(shù)。為了準(zhǔn)確估計(jì)所有RSS樣本總體的概率密度，本文提出了一種基于偏度-峰度檢驗(yàn)的室內(nèi)定位算法：離線訓(xùn)練階段根據(jù)偏度-峰度檢驗(yàn)法檢驗(yàn) RSS樣本是否來自正態(tài)總體，對于接受和拒絕零假設(shè)的樣本分別利用正態(tài)分布和核函數(shù)估計(jì)其總體的概率密度，在線定位階段利用貝葉斯匹配法估計(jì)位置。實(shí)驗(yàn)結(jié)果表明，本文算法比傳統(tǒng)算法有更高的定位精度，平均定位誤差減小15%以上，而且在達(dá)到相同定位精度的情況下離線階段訓(xùn)練樣本數(shù)比傳統(tǒng)算法少，能明顯降低離線階段的工作量。

2 基于偏度-峰度檢驗(yàn)的室內(nèi)定位算法

2.1 偏度與峰度

檢驗(yàn)一個(gè)樣本是否服從正態(tài)分布的方法有很多，包括 Kolmogorov檢驗(yàn)、χ2擬合優(yōu)度檢驗(yàn)、Shapiro-Will檢驗(yàn)和偏度-峰度檢驗(yàn)等[15]。Kolmogorov檢驗(yàn)是一種較準(zhǔn)確的檢驗(yàn)方法，但Kolmogorov檢驗(yàn)只有當(dāng)假設(shè)的分布完全已知的時(shí)候才適用，假設(shè)的分布不包含需要從樣本里估計(jì)的未知參數(shù)。χ2擬合優(yōu)度檢驗(yàn)比較靈活，允許分布中包含待估的未知參數(shù)，但χ2檢驗(yàn)要求數(shù)據(jù)分組，且χ2檢驗(yàn)犯第二類錯(cuò)誤（接受了不正確零假設(shè)的錯(cuò)誤）的概率往往較大。Shapiro-Will檢驗(yàn)法能有效地檢驗(yàn)樣本正態(tài)性，但Shapiro-Will檢驗(yàn)要求樣本容量不大于50。偏度-峰度檢驗(yàn)法通過計(jì)算樣本偏度和峰度檢驗(yàn)樣本總體是否服從正態(tài)分布，是一種快速、有效的正態(tài)性檢驗(yàn)方法，且對樣本容量沒有嚴(yán)格要求。因此本文選用偏度-峰度檢驗(yàn)法檢驗(yàn) RSS樣本是否來自正態(tài)總體。

偏度和峰度分別是描述總體中所有取值分布形態(tài)對稱性和陡緩程度的統(tǒng)計(jì)量。隨機(jī)變量X的偏度和峰度是指X的標(biāo)準(zhǔn)化變量階矩和四階矩[15]：

其中，E(X)和D(X)分別為隨機(jī)變量的期望和方差。當(dāng)隨機(jī)變量X服從正態(tài)分布時(shí)，偏度ν1=0且峰度ν2=3。

2.2 提出假設(shè)

設(shè)X1,X2,…,Xn是來自RSS總體X的樣本，則ν1和ν2的矩估計(jì)量分別為

其中，Bk(k=2,3,4)是樣本k階中心矩，G1，G2分別為樣本偏度和樣本峰度。

若總體X為正態(tài)變量，則有

提出假設(shè)：

其中，H0和H1分別為零假設(shè)和備則假設(shè)。

當(dāng)H0為真且n充分大時(shí)，有

取顯著性水平為α(0＜α＜1)，則H0的拒絕域?yàn)?/p>

2.3 正態(tài)估計(jì)

將離線階段采集的 RSS樣本按式(5)檢驗(yàn)|u1|和|u2|是否滿足H0的拒絕域，如果不滿足則接受H0，認(rèn)為該樣本的總體在顯著水平為α(0＜α＜1)時(shí)服從正態(tài)分布，此樣本的概率密度函數(shù)近似為

其中，μ和σ為正態(tài)分布的參數(shù)。使用最大似然估計(jì)法可以估計(jì)正態(tài)分布的參數(shù)，即

2.4 核函數(shù)估計(jì)

如果離線階段采集的RSS樣本按式(5)檢驗(yàn)|u1|和|u2|滿足H0的拒絕域，則認(rèn)為這些樣本的總體分布在顯著水平為α?xí)r與正態(tài)分布有較大差異。本文中用核函數(shù)方法估計(jì)這些樣本的總體分布。核估計(jì)方法是一種在總體分布未知的情況下估計(jì)總體概率密度的方法[16]。

定義設(shè)總體X具有概率密度f(x)，f(x)未知，X1,X2,…,Xn為取自總體X的一個(gè)樣本，存在全直線上一有界函數(shù)k(y)≥ 0 ，滿足

滿足上述定義的核函數(shù)有很多，其中指數(shù)核函數(shù)對樣本的概率密度估計(jì)效果較好[11]，因此本文選用指數(shù)核函數(shù)：

拒絕H0的樣本利用指數(shù)核函數(shù)估計(jì)其總體的概率密度函數(shù)：

2.5 貝葉斯匹配

其中，m表示 AP的數(shù)目，表示在參考位置l處采集的來自第i個(gè) AP的 RSS樣本的似然函數(shù)，按式(7)或式(11)計(jì)算。

p表示參考位置l與在線階段真實(shí)位置的接近程度，通過式(14)估計(jì)用戶位置：

2.6 定位算法步驟

基于偏度-峰度檢驗(yàn)的室內(nèi)定位算法的主要步驟如下，其中，step1～step4為離線訓(xùn)練階段，step5～step6為在線實(shí)時(shí)定位階段。

step1 在定位區(qū)域選定參考位置點(diǎn)，在每個(gè)參考位置點(diǎn)處采集來自不同 AP的一定數(shù)量的 RSS值，組成RSS樣本。

step2 設(shè)定顯著性水平α和指數(shù)核函數(shù)寬度h。

step3 按式(5)檢驗(yàn)RSS樣本是否接受H0。

step4 如果接受H0，則認(rèn)為該樣本來自正態(tài)總體，根據(jù)式(8)和式(9)計(jì)算正態(tài)分布參數(shù)的估計(jì)值并存入數(shù)據(jù)庫，否則將RSS樣本原始值存入數(shù)據(jù)庫。

step5 實(shí)時(shí)采集 RSS值，并根據(jù)數(shù)據(jù)庫中存儲(chǔ)的數(shù)據(jù)按式(7)或式(11)計(jì)算參考位置l的來自第i個(gè)AP的RSS樣本的似然函數(shù)，并按式(13)計(jì)算參考位置l的似然函數(shù)。

step6 按式(14)估計(jì)用戶的位置。

基于偏度-峰度檢驗(yàn)的室內(nèi)定位算法的流程如圖1所示。

圖1 基于偏度-峰度檢驗(yàn)的室內(nèi)定位算法流程

3 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)環(huán)境為如圖2所示的典型的WLAN室內(nèi)定位場景，面積為37.2m×18m。此區(qū)域有4個(gè)型號(hào)為NETGEAR WG602的AP，分別位于606室、607室、610室和613室。RSS采集裝置選用惠普dv2305TX筆記本電腦，無線網(wǎng)卡型號(hào)為 Intel PRO/wireless 3945ABG，操作系統(tǒng)為 Windows 7。參考位置點(diǎn)主要在走廊、電梯口、610室和613室選取，每個(gè)參考位置點(diǎn)間隔2m，共有64個(gè)，利用筆者開發(fā)的RSS采集軟件在每個(gè)位置點(diǎn)采集RSS樣本，采集速率為2sample/s。本文用于定位的AP數(shù)目為4個(gè)，總的訓(xùn)練RSS樣本數(shù)目為64×4=256個(gè)。

圖2 WLAN室內(nèi)定位環(huán)境(圓圈代表參考參考位置點(diǎn)，代表此區(qū)域存在的AP)

定位誤差的評(píng)判標(biāo)準(zhǔn)為估計(jì)位置點(diǎn)?l和真實(shí)位置點(diǎn)坐標(biāo)l之間的歐式距離，即

3.1 顯著性水平和核寬度分析

顯著性水平α表示當(dāng)H0為真時(shí)拒絕H0的概率。表1給出了顯著性水平α與接受H0的樣本數(shù)的關(guān)系，其中，總的RSS訓(xùn)練樣本為256個(gè)，每個(gè)RSS樣本的樣本容量為60。從表1中可以看出α較小時(shí)，接受H0的樣本數(shù)占總樣本數(shù)的80%以上，α較大時(shí)，接受H0的樣本數(shù)占總樣本數(shù)的比例不足20%。這2種情況下都有較多的樣本導(dǎo)致了誤判，影響定位精度。

表1 顯著性水平α與接受H0的樣本數(shù)

圖3給出了顯著性水平α取不同值時(shí)對平均定位誤差的影響。從圖中可以看出，α取0.1時(shí)平均定位誤差最小，此時(shí)大約有71.09%的樣本近似為正態(tài)分布。從圖中還可以看出當(dāng)α小于0.06時(shí)，平均定位誤差的變化趨勢比較陡峭，這是由于有較多的不服從正態(tài)分布的樣本如嚴(yán)重左偏、嚴(yán)重右偏或多峰的樣本被誤判為了正態(tài)分布。當(dāng)α大于0.4時(shí)，平均定位誤差的變化趨勢比較緩慢，這是由于α大于0.4時(shí)接受H0的樣本的偏度和峰度都比較小，此時(shí)指數(shù)核函數(shù)估計(jì)的概率密度與正態(tài)分布很接近。

圖3α取不同值時(shí)對平均定位誤差的影響

核寬度h是核函數(shù)的平滑參數(shù)。圖4所示為當(dāng)α=0.1，RSS樣本的容量為60時(shí)，核寬度h與平均定位誤差之間的關(guān)系。從圖中可以看出，核寬度h取值太大或太小都有較大的定位誤差。這是因?yàn)槿鬶取得太小，隨機(jī)干擾增大，估計(jì)結(jié)果會(huì)失去準(zhǔn)確性；若h過大，估計(jì)曲線太平坦，以至于無法表征樣本分布的變化情況?？梢钥闯鰄取 2.2時(shí)平均定位誤差最小。

圖4 核寬度h取不同值時(shí)的平均定位誤差

3.2 與其他算法比較

比較了本文提出算法與現(xiàn)有的直方圖方法[12]、多項(xiàng)式擬合方法[14]和核函數(shù)方法[13]等算法的定位性能。本文算法顯著性水平α取0.1，核寬度h取2.2。

離線階段樣本容量決定了離線階段的工作量，也決定了室內(nèi)定位法的效率。如圖5所示為提出的算法與現(xiàn)有的幾種定位算法在不同的訓(xùn)練樣本容量下的定位精度，訓(xùn)練樣本容量選擇[10,120]區(qū)間內(nèi)的 12組數(shù)據(jù)。從圖中可以看出隨著訓(xùn)練樣本容量的增加，4種算法的平均定位誤差都逐漸減小，當(dāng)樣本容量大于100時(shí)定位誤差趨于穩(wěn)定，這說明不能通過無限地增大樣本容量使定位精度無限提高。其原因是當(dāng)樣本容量較小時(shí)無法準(zhǔn)確表征復(fù)雜室內(nèi)環(huán)境下的位置信息，但當(dāng)樣本容量增大到一定程度時(shí)RSS樣本所含的位置信息基本保持不變。從圖中還可以看出基于偏度-峰度的定位算法在相同的樣本容量下具有最小的平均定位誤差，這是由于該算法能夠在有限的樣本容量下更準(zhǔn)確地估計(jì)所有樣本的總體分布，使似然函數(shù)更加準(zhǔn)確，從而按式(14)估計(jì)的位置更精確。而且，基于偏度-峰度的定位算法只需要較少的訓(xùn)練樣本容量就能到達(dá)其他算法同樣的定位精度。例如，要達(dá)到小于 2.6m的平均定位誤差，基于偏度-峰度的定位算法只需要在離線階段采集30個(gè)RSS值，而核函數(shù)算法則至少需要 80個(gè)。這表明在相同的定位精度下，本文算法能夠有效減少離線階段的數(shù)據(jù)采集時(shí)間，節(jié)省人力成本投入。

圖5 不同訓(xùn)練樣本容量下的平均定位誤差

圖6給出了當(dāng)RSS訓(xùn)練樣本容量為60的條件下幾種定位算法的定位誤差的累積概率分布?？梢姡褂没谄?峰度的定位算法誤差在2m以內(nèi)的概率為 63.3%，高于其他算法的 57.1%、52.5%和46.4%。表2給出了當(dāng)RSS訓(xùn)練樣本容量為60的條件下不同算法的定位誤差比較?？梢钥闯觯谄?峰度的定位算法的平均定位誤差比核函數(shù)方法、多項(xiàng)式擬合方法和直方圖方法分別減少0.41m(15.0%)，0.54m(18.9%)和0.85m (26.8%)，而且基于偏度-峰度的定位算法具有更小的誤差標(biāo)準(zhǔn)差。這表明該算法在有效提高定位精度的同時(shí)還具有較好的穩(wěn)定性。原因是在復(fù)雜的室內(nèi)環(huán)境下，基于偏度-峰度的定位算法準(zhǔn)確地估計(jì)了所有RSS樣本總體的概率密度，使似然函數(shù)計(jì)算更準(zhǔn)確，從而能更精確地估計(jì)位置。

圖6 不同算法定位誤差的累積概率分布

表2 不同算法的平均定位誤差比較/m

4 結(jié)束語

在無線局域網(wǎng)室內(nèi)環(huán)境下，RSS樣本的總體分布呈現(xiàn)不一致的現(xiàn)象，如何準(zhǔn)確估計(jì)樣本總體的分布是提高定位精度的關(guān)鍵。本文提出了一種基于偏度-峰度檢驗(yàn)的室內(nèi)定位算法，接受和拒絕零假設(shè)的樣本分別利用正態(tài)分布和核函數(shù)估計(jì)其總體的概率密度，可準(zhǔn)確估計(jì)所有 RSS樣本總體的概率密度，使位置估計(jì)更加精確。實(shí)驗(yàn)結(jié)果表明提出算法的定位精度比傳統(tǒng)方法提高15%以上，且在相同定位精度下，需要更少的訓(xùn)練樣本容量，大大減小了離線階段的工作量。提出的算法不僅適合于WLAN室內(nèi)定位技術(shù)，而且適合其他基于RSS的室內(nèi)無線定位技術(shù)，如RFID定位技術(shù)和藍(lán)牙定位技術(shù)等。需要說明的是，本文算法在線定位階段沒有考慮當(dāng)前定位狀態(tài)與下一定位狀態(tài)之間的相關(guān)性，因此不適合運(yùn)動(dòng)速度較快的目標(biāo)定位。下一步研究中，針對快速運(yùn)動(dòng)目標(biāo)跟蹤定位問題，須考慮定位狀態(tài)之間的相關(guān)性，提高動(dòng)態(tài)跟蹤定位精度。

[1] VERA R, OCHOA S F, ALDUNATE R G. EDIPS: an easy to deploy indoor positioning system to support loosely coupled mobile work[J].Personal and Ubiquitous Computing, 2011, 15(4): 365-376.

[2] 林以明, 羅海勇, 李錦濤等. 基于動(dòng)態(tài) radio map的粒子濾波室內(nèi)無線定位算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2011, 48(1): 139-146.LIN Y M, LUO H Y, LI J T, et al. Dynamic radio map based particle filter for indoor wireless localization[J]. Journal of Computer Research and Development, 2011, 48(1): 139-146.

[3] GU Y Y, LO A, NIEMEGEERS I. A survey of indoor positioning systems for wireless personal networks[J]. IEEE Communications Surveys & Tutorials, 2009, 11(1): 13-32.

[4] KUSHKI A, PLATANIOTIS K N, VENETSANOPOULOS A N.Intelligent dynamic radio tracking in indoor wireless local area networks[J]. IEEE Transactions on Mobile Computing, 2010, 9(3):405-419.

[5] FANG S H, LIN T N. A dynamic system approach for radio location fingerprinting in wireless local area networks[J]. IEEE Transactions on Communications, 2010, 58(4): 1020-1026.

[6] 徐玉濱, 鄧志安, 馬琳. 基于核直接判別分析和支持向量回歸的WLAN室內(nèi)定位算法[J]. 電子與信息學(xué)報(bào), 2011, 33(4): 896-901.XU Y B, DENG Z A, MA L. WLAN indoor positioning algorithm based on KDDA and SVR[J]. Journal of Electronics & Information Technology, 2011, 33(4): 896-901.

[7] FANG S H, LIN T N, LEE K C. A novel algorithm for multipath fingerprinting in indoor WLAN environments[J]. IEEE Transactions on Wireless Communications, 2008, 7(9): 3579-3588.

[8] MAZUELAS S, BAHILLO A, LORENZO R M, et al. Robust indoor positioning provided by real-time RSSI values in unmodif i ed WLAN networks[J]. IEEE Journal of Selected Topics in Signal Processing,2009, 3(5): 821-830.

[9] KAEMARUNGSI K. Design of Indoor Positioning Systems Based on Location Fingerprinting Technique[D]. Pittsburgh, USA: University of Pittsburgh, 2005.

[11] HONKAVIRTA V, PERALA T, LOYTTY S A, et al. A comparative survey of WLAN location fingerprinting methods[A]. Proceedings of the 6th Workshop on Positioning, Navigation and Communication[C].Hannover, 2009. 243-251.

[12] YOUSIEF M, AGRAWALA A. The Horus WLAN location determination system[A]. The 3rd International Conference on Mobile Systems Applications, and Services[C]. New York, 2005. 205-218.

[13] KUSHKI A, PLATANIOTIS K, VENETSANOPOULOS A. Kernel-based positioning in wireless local area networks[J]. IEEE Transactions on Mobile Computing, 2007, 6(6): 689-705.

[14] MA L, XU Y B, ZHOU M. Accuracy enhancement for fingerprint-based WLAN indoor probability positioning algorithm[A]. The 1st International Conference on Pervasive Computing, Signal Processing and Applications[C]. Harbin, China, 2010. 167-170.

[15] KVAM P H, VIDAKOVIC B. Nonparametric Statistics with Applications to Science and Engineering[M]. Hoboken: John Wiley & Sons,2007.

[16] 李裕奇, 趙聯(lián)文, 王沁等. 非參數(shù)統(tǒng)計(jì)方法[M]. 成都: 西南交通大學(xué)出版社, 2010.LI Y Q, ZHAO L W, WANG Q, et al. Nonparametric Statistics Methods[M]. Chengdu: Southwest Jiaotong University Press, 2010.