基于偏度-峰度檢驗的無線局域網室內定位算法

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

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

1 引言

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

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

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

2 基于偏度-峰度檢驗的室內定位算法

2.1 偏度與峰度

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

偏度和峰度分別是描述總體中所有取值分布形態對稱性和陡緩程度的統計量。隨機變量X的偏度和峰度是指X的標準化變量階矩和四階矩[15]：

其中，E(X)和D(X)分別為隨機變量的期望和方差。當隨機變量X服從正態分布時，偏度ν1=0且峰度ν2=3。

2.2 提出假設

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

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

若總體X為正態變量，則有

提出假設：

其中，H0和H1分別為零假設和備則假設。

當H0為真且n充分大時，有

取顯著性水平為α(0＜α＜1)，則H0的拒絕域為

2.3 正態估計

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

其中，μ和σ為正態分布的參數。使用最大似然估計法可以估計正態分布的參數，即

2.4 核函數估計

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

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

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

拒絕H0的樣本利用指數核函數估計其總體的概率密度函數：

2.5 貝葉斯匹配

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

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

2.6 定位算法步驟

基于偏度-峰度檢驗的室內定位算法的主要步驟如下，其中，step1～step4為離線訓練階段，step5～step6為在線實時定位階段。

step1 在定位區域選定參考位置點，在每個參考位置點處采集來自不同 AP的一定數量的 RSS值，組成RSS樣本。

step2 設定顯著性水平α和指數核函數寬度h。

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

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

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

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

基于偏度-峰度檢驗的室內定位算法的流程如圖1所示。

圖1 基于偏度-峰度檢驗的室內定位算法流程

3 實驗結果與分析

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

圖2 WLAN室內定位環境(圓圈代表參考參考位置點，代表此區域存在的AP)

定位誤差的評判標準為估計位置點?l和真實位置點坐標l之間的歐式距離，即

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

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

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

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

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

核寬度h是核函數的平滑參數。圖4所示為當α=0.1，RSS樣本的容量為60時，核寬度h與平均定位誤差之間的關系。從圖中可以看出，核寬度h取值太大或太小都有較大的定位誤差。這是因為若h取得太小，隨機干擾增大，估計結果會失去準確性；若h過大，估計曲線太平坦，以至于無法表征樣本分布的變化情況。可以看出h取 2.2時平均定位誤差最小。

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

3.2 與其他算法比較

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

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

圖5 不同訓練樣本容量下的平均定位誤差

圖6給出了當RSS訓練樣本容量為60的條件下幾種定位算法的定位誤差的累積概率分布。可見，使用基于偏度-峰度的定位算法誤差在2m以內的概率為 63.3%，高于其他算法的 57.1%、52.5%和46.4%。表2給出了當RSS訓練樣本容量為60的條件下不同算法的定位誤差比較。可以看出，基于偏度-峰度的定位算法的平均定位誤差比核函數方法、多項式擬合方法和直方圖方法分別減少0.41m(15.0%)，0.54m(18.9%)和0.85m (26.8%)，而且基于偏度-峰度的定位算法具有更小的誤差標準差。這表明該算法在有效提高定位精度的同時還具有較好的穩定性。原因是在復雜的室內環境下，基于偏度-峰度的定位算法準確地估計了所有RSS樣本總體的概率密度，使似然函數計算更準確，從而能更精確地估計位置。

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

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

4 結束語

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

[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] 林以明, 羅海勇, 李錦濤等. 基于動態 radio map的粒子濾波室內無線定位算法[J]. 計算機研究與發展, 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室內定位算法[J]. 電子與信息學報, 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] 李裕奇, 趙聯文, 王沁等. 非參數統計方法[M]. 成都: 西南交通大學出版社, 2010.LI Y Q, ZHAO L W, WANG Q, et al. Nonparametric Statistics Methods[M]. Chengdu: Southwest Jiaotong University Press, 2010.