基于KDDA和SFLA-LSSVR算法的WLAN室內定位算法

張 勇 李飛騰 王昱潔

1(合肥工業大學計算機與信息學院 合肥 230009)2 (蕪湖創業園留學人員博士后科研工作站 安徽蕪湖 241000) (hfgdwhb@163.com)

基于KDDA和SFLA-LSSVR算法的WLAN室內定位算法

張 勇1,2李飛騰1王昱潔1

1(合肥工業大學計算機與信息學院 合肥 230009)2(蕪湖創業園留學人員博士后科研工作站 安徽蕪湖 241000) (hfgdwhb@163.com)

針對接收信號強度(received signal strength, RSS)的時變性降低WLAN室內定位精度的問題，提出了一種基于核直接判別分析(kernel direct discriminant analysis, KDDA)和混洗蛙跳最小二乘支持向量回歸機(SFLA-LSSVR)的定位算法,該算法通過核函數策略將采集的各接入點(access point, AP)的RSS信號映射到非線性領域，有效提取了非線性定位特征，重組定位信息，去除冗余定位特征和噪聲；然后采用LSSVR算法構建指紋點定位特征數據與物理位置的映射關系模型，采用SFLA算法優化該關系模型的參數，并用該關系模型對測試點的位置進行回歸預測.實驗結果表明:提出算法在相同的采樣次數下的定位精度明顯優于WKNN,ANN,LSSVR算法，并且在相同的定位精度下，采樣次數較大減少，是一種性能良好的WLAN室內定位算法.

接收信號強度;無線局域網;室內定位;核直接判別分析;混洗蛙跳算法;最小二乘支持向量回歸機

隨著智能手機的普及以及移動互聯網的發展，室內位置服務越來越受到重視，尤其在復雜的室內環境，如機場大廳、醫院、地鐵站、地下停車場等環境中，常常需要確定用戶在室內環境的位置信息[1].在室內環境中，基于接收信號強度(received signal strength, RSS)的無線局域網(wireless local area network, WLAN)室內定位技術[2]要比北斗、GPS、蜂窩網等定位技術的定位精度更高一些.該定位系統熱點廉價、部署容易、無需專門的硬件、接入方便，其帶寬高、穿透力強、覆蓋范圍廣，因此得到了廣泛的關注.

WLAN室內定位主要方法有定位感知、幾何測量、場景分析等[3].場景分析法包括指紋識別法和信號傳播模型法.指紋識別法由于其算法靈活、定位相對準確，成為了研究的熱門方向.

位置指紋定位算法[4]分為2個方面：1)離線階段無線電地圖(radio map)的建立方法；2)在線階段匹配radio map實現定位的方法.其中匹配定位算法主要有加權K鄰居(weightedk-nearest neighbors, WKNN)算法、人工神經網絡(artificial neural network, ANN)算法[5]、概率法以及支持向量機(support vector machine, SVM)算法等.WKNN算法[6]找出多個測試點RSS和指紋點RSS有著最小距離的指紋點，然后根據距離的大小加權，將指紋點坐標的加權值作為測試點的坐標；WKNN算法簡單且容易實現，但是由于其只是考慮到單一的測試點和指紋點之間的關系，而忽略了不同指紋點之間的RSS更深層次的關系，因此定位精度不高.文獻[7]提出一種基于BP神經網絡定位的模型，由于BP神經網絡本質上是梯度下降法且是一種局部搜索的優化方法，因此收斂速度慢且容易陷入局部最優.文獻[8]提出采用SVR構建接收信號強度與物理位置的非線性映射關系，使得定位精度有所提高，但其受RSS的時變性影響較大.radio map的建立方法主要是RSS特征值法.

在WLAN室內定位環境中，多徑效應和人員走動造成信號受到不規律干擾，陰影效應造成信號損耗,以上這幾種影響使得在相同位置接收到各個接入點(access point, AP)的RSS值具有復雜的時變統計特性，從而降低了室內定位的精度.在建立radio map過程中，如果直接采用各個AP的RSS值作為輸入的定位特征值，那么RSS信號的時變性、不同AP之間的相關性，以及判別能力弱的AP的RSS值將會受采集設備硬件所產生的噪聲和外界環境影響所產生的噪聲的影響比較大，以上3個因素對室內定位的精度影響較大.針對這個問題，本文提出應用基于核直接判別分析[9-10](kernel direct discriminant analysis, KDDA)變換將采集各個AP的原始RSS信號映射到高維非線性空間，挖掘非線性定位特征，提取主要定位特征.在在線匹配定位過程中，由于SVM在統計樣本量較少的情況下也能獲得良好的統計規律；混洗蛙跳算法[11](shuffled frog leaping algorithm, SFLA)因其容易實現和更強的全局優化能力的特點而被廣泛應用于多元函數優化、帶約束優化問題等.本文提出應用基于混洗蛙跳算法優化的最小二乘支持向量回歸機(SFLA-LSSVR)，首先使用最小二乘支持向量回歸機[12-14](least square support vector regression, LSSVR)來建立radio map與其對應位置坐標的非線性關系；其次，通過SFLA算法對LSSVR進行參數優化；最后，以優化后的關系對測試點的位置進行回歸預測.通過實驗對比驗證了KDDA提取非線性定位特征的有效性及SFLA-LSSVR的參數優化和建立回歸方程的優勢.同時通過與LSSVR,WKNN,ANN,KDDA-LSSVR算法的實驗結果對比，表明了該算法具有較高的定位精度.

1 KDDA-SFLA-LSSVR算法

指紋識別算法是通過觀察者在場景中各個指紋點和測試點上測得來自各AP的信號強度值，然后將測試點的信號強度值和指紋點的信號強度值進行匹配，預測出測試點的位置信息.指紋識別算法分為2個部分：離線階段和在線階段.

1) 離線階段.在場景中選定指紋點，然后采集各個指紋點上的RSS值，通過KDDA變換提取原始RSS樣本的定位特征值；將定位特征和相應的指紋點位置為輸入樣本對，采用SFLA算法來優化LSSVR算法的參數，完成LSSVR的學習訓練過程，得出定位特征和物理位置的最小二乘支持向量回歸函數.

2) 在線階段，在場景中選定測試點，將采集到的測試點RSS值通過KDDA變換，輸入構建好的最小二乘支持向量回歸函數中，估計出測試點的實際位置.該定位算法的流程如圖1所示：

Fig. 1 KDDA-SFLA-LSSVR localization algorithm process圖1 KDDA-SFLA-LSSVR定位算法流程

1.1 KDDA變換原理

KDDA變換基本原理：通過建立從輸入空間到隱式的高維特征空間的非線性映射，使得在輸入空間非線性和復雜的分布模型在高維特征空間變得線性可分和簡單化，再應用常規的Fisher線性判別分析[15](linear discriminant analysis, LDA)提取有效的非線性定位特征.

設RSS樣本集為Zij∈N，定位環境中參考點的數目為C，每個樣本采集各AP的RSS值的次數為Ci，RSS樣本總數為表示使用AP的個數，Zij表示在第i個參考點上第j次采集各AP的RSS值，其中i=1,2,…,C，j=1,2,…,Ci.

將原始的RSS信號映射到高維非線性空間：Zij∈N→φ(Zij)∈F.特征空間F中的類間、類內散度矩陣分別為

KDDA變換的優化目標是在F中找出最具判別力的M維基向量Ψ：

滿足式(3)的最具判別力基向量Ψ所提取的原始RSS樣本的定位特征具有類間離散度最大化、類內離散度最小化，因此KDDA變換能最大程度上的區分不同參考點從而有效地判別定位.

KDDA變換首先計算出SBTW的特征值和相應的特征向量，分別設為λi和ei，然后選取m個最大的特征值及其對應的特征向量，m≤C-1.令：

E=(e1,e2,…,em)V=(v1,v2,…,vm)=ΦbE，

UTSBTWU=I.

計算出UTSWTHU的特征值和特征向量，分別記為λi和pi，其中i=1,2,…,m;然后選取最小的M(≤m)個特征值及其所對應的特征向量，分別記為

Λw=diag(λ1,λ2,…,λM)，

P=(p1,p2,…,pM).

設矩陣Q=UP可以得到：

QTSWIHQ=ΛW，

那么最優判別基向量可以表示為

因此RSS樣本集Zij在最優判別基上的投影系數為

YZ=ΨT·φ(Z)=Θ·γ(φ(Z))，

其中,γ(φ(Z))為RSS樣本集Zij∈N的核矩陣：

Θ是一個M×L的變換矩陣：

1.2 SFLA-LSSVR算法

由式(11)得出通過KDDA變換分別得到新的指紋點定位特征樣本集Z′=Yzi∈M和新的測試點定位特征測試集T′=Ycj∈M；與其相對應的物理坐標分別為LPi=(xpi,ypi)和LQj=(xqj,yqj)，其中i=1,2,…,L，j=1,2,…,Qc，L為指紋點的總個數，Qc為測試點的總個數.LSSVR是支持向量回歸機(support vector regression, SVR)的改進，很好地解決了小樣本、非線性、高維數的問題，提高了求解速度和泛化能力.依據結構風險化最小原則，LSSVR優化問題如下：

s.t.yi=ωTΦ(Z′)+b+ηi,

其中，i=1,2,…,L，ω為權系數，b為偏置，C為懲罰參數，ηi為誤差，Φ(·)為輸入空間到特征空間的映射.

可采用拉格朗日函數求解式(14)(15)：

其中，α=(a1,a2,…,ap)T，αi是拉格朗日乘子.

LSSVR使用的是參數相對少、適應能力較強的徑向基核函數：

因此得出位置坐標和RSS值的回歸函數分別是：

核寬度δ和懲罰參數C是LSSVR算法重要的2個參數，它們的選取直接影響著該算法的學習能力和泛化能力.

SFLA有著良好的全局優化能力，并且參數設置比較簡單，可以對LSSVR模型的(C,δ)的參數組合進行優化；因而采用SFLA和LSSVR的混合算法來計算最小二乘支持向量回歸函數.

使用SFLA-LSSVR算法回歸預測步驟如下：

步驟1. 初始化種群，種群的數目F=M×N，M表示整個種群被分成子種群的個數，N表示每個子種群青蛙的個數，每個子種群最大迭代次數Nmax，在C∈[Cmin,Cmax]和δ∈[δmin,δmax]的范圍中隨機給每只青蛙一組參數序列(C,δ).

步驟2. 將整個種群中的F只青蛙按照指定的適應度的降序排序，適應度計算：

fit=1(1+E)，

步驟3. 將整個種群分成M組：Y1,Y2,…,YM，每組有N只青蛙，第1只青蛙進入Y1，第2只青蛙進入Y2，直到第M只青蛙進入到YM，然后再將第M+1只青蛙分入Y1，第M+2只青蛙分入Y2，以此類推，直到所有青蛙分配完畢.

步驟4. 用Pg表示整個種群中最好位置的青蛙，Pb表示本組位置最好的青蛙，Pw表示本組位置最差的青蛙，每次進化中更新最差位置的青蛙：

蛙跳步長更新：

Si=rand()×(Pb-Pw).

位置更新：

Pw(k+1)=Pw(k)+Si，

其中，Smax≥Si≥-Smax，rand()∈[0,1]，k=1,2,…,N，Smax是允許青蛙移動的最大距離.如果計算后新的解較優，則用其替代最差個體，否則用Pg代替Pb重復上過程，如果還不能生成更好的青蛙，就隨機生成一個新的位置的青蛙取代原來最壞的青蛙Pw.

步驟5. 將青蛙混合，重新按照適應度的值降序排序，并且及時更新Pg.每個子種群執行著自身的局部搜索策略，直到子群體進化到一定階段后，再將所有青蛙混合來實現各子種群之間的全局交換，全局交換和局部深度搜索的平衡策略使得該算法能夠跳出局部極值點，向著全局最優的方向進行.

步驟6. 達到最大迭代次數Nmax時，停止迭代，輸出(C,δ)最優參數組合，轉入步驟7；否則跳轉至步驟3.

步驟7. 用優化得到(C,δ)構建最小二乘支持向量回歸函數，將T′輸入到回歸函數中，得出測試點的估計物理位置.

2 實驗結果與分析

2.1 實驗條件

實驗環境如圖2所示，該室內定位環境是在合肥工業大學逸夫樓6樓，定位區域包括辦公室、過道，辦公室內有辦公桌椅、書柜等物品，墻的材料是混凝土，鋁合金窗戶和金屬門，其中辦公室為定位區域A，過道為定位區域B.實驗選用6個型號為DWL-2414N的AP，固定高度為2 m，使用三星GT-N5110的平板電腦采集各AP的RSS值，采集位置離地高度是1.2 m.實驗選取了25個指紋點和30個測試點，其中A區域選取9個指紋點和10個測試點，B區域選取16個指紋點和20個測試點.指紋點的間距是3 m，測試點位置是隨機選取.每個位置采集200個樣本，每秒2個樣本.

Fig. 2 Experimental environment of WLAN indoor positioning圖2 WLAN 室內定位實驗環境

定義第i個測試點的定位誤差erri和平均定位誤差AverErr：

2.2 實驗結果分析

為了驗證KDDA-SFLA-LSSVR算法的有效性，實驗對比了WKNN算法、ANN算法、LSSVR算法和KDDA-LSSVR算法.KDDA算法中m表示保留類間散度矩陣最大特征值所對應的特征向量的個數，M表示保留類內散度矩陣最小特征值所對應的特征向量的個數，通過多次試驗在50次、100次、150次、200次采樣樣本時最優參數組合m和M的取值分別是：7，4；8，5；9，5；10，8.SFLA算法種群數目為1000，子種群數為100，迭代次數為6，Cmin，Cmax，δmin，δmax分別為0.01，1000，0.01，1000.KDDA算法和LSSVR都是選擇高斯核函數；WKNN算法的近鄰數K為3；ANN算法隱藏層神經元數為20的6-20-2的3層BP神經網絡結構.

圖3所示是在KDDA變換中參數m和M的變化對KDDA-LSSVR算法平均定位誤差的影響，實驗使用了100個樣本.隨著m的增大，最優平均定位誤差分別是2.285 m，2.122 m，1.989 m，1.913 m，2.062 m，其中m=8且M=5時，平均定位誤差最小.隨著m的變大，所獲得的類間離散度信息變大，定位特征的判別力變大，平均定位誤差減小；當m=8且M=5時到達拐點，此時平均定位誤差最小；當m繼續變大時，所加入的定位特征判別能力弱，且引入了采集設備硬件所產生的噪聲、外界環境影響所產生的噪聲等，導致平均定位誤差變大.

Fig. 3 The influence of parameters m and M on the average positioning error 圖3 參數m和M對平均定位誤差的影響

圖4所示的是使用SFLA優化算法平均定位誤差的對比，對于由KDDA提取出的有效的定位特征通過LSSVR構建定位特征和物理位置的映射關系的過程，SFLA有著良好的全局優化LSSVR算法的核寬度參數δ和懲罰參數C的能力，使得LSSSVR有著更好的學習能力和泛化能力，在采樣次數為50，100，150，200次時，KDDA-LSSVR比KDDA-SFLA-LSSVR平均定位誤差分別高出11.03%，8.98%，7.61%，3.05%，結果表明使用SFLA優化算法對KDDA-LSSVR算法的定位精度有著較大的提高.

Fig. 4 The average positioning error comparison for the use of SFLA optimization algorithm圖4 使用SFLA算法優化算法平均定位誤差的對比

圖5所示的是在不同的采樣次數下4種定位算法平均定位誤差的對比.LSSVR算法平均定位精度要比WKNN和ANN算法高.WKNN算法沒有充分利用到RSS的統計特性，平均定位誤差最大；ANN算法利用到了RSS的統計特性，但是容易陷入局部最優，平均定位精度要高于WKNN算法；LSSVR算法相對于ANN算法有著更快的求解速度和更好的泛化能力，因此以上3種算法中LSSVR算法平均定位精度最高.KDDA-SFLA-LSSVR算法定位精度明顯高于上面3種算法，在采樣次數為50次時，KDDA-SFLA-LSSVR算法平均定位誤差為1.985 m，小于上面3種算法在采樣次數200次時的平均定位誤差，它們分別是2.120 m，2.099 m，2.053 m，因而使用KDDA-SFLA-LSSVR算法能夠較大減少樣本的采樣次數.KDDA算法對原始RSS信號進行了有效的定位特征挖掘和提取，SFLA算法優化LSSVR參數，使得KDDA-SFLA-LSSVR算法平均定位精度明顯要高于WKNN，ANN，LSSVR算法.

Fig. 5 The average positioning error comparison under four kinds of positioning algorithms圖5 4種定位算法平均定位誤差的對比

Fig. 6 The positioning error’s cumulative distribution probability under four kinds of positioning algorithms圖6 4種定位算法定位誤差累計概率分布對比

圖6所示的是在RSS信號采樣次數為150次時，4種定位算法定位誤差累計概率分布曲線圖.當定位誤差小于等于2 m時，KDDA-SFLA-LSSVR算法累計概率是73.33%，WKNN，ANN，LSSVR算法的累計概率分別是43.33%，46.67%，60.00%，當累計概率為50%時，KDDA-SFLA-LSSVR，LSSVR，ANN，WKNN算法定位誤差值分別為1.28 m，1.71 m，2.07 m，2.16 m，從統計學概率分布可以得出相比于其他3種算法，KDDA-SFLA-LSSVR算法有著更高的定位精度.

3 結束語

針對RSS的時變性影響WLAN室內定位精度的問題，本文提出了一種基于KDDA和SFLA-LSSVR結合的WLAN室內定位算法.一方面從理論分析說明了該算法的可行性，首先將原始的RSS信號通過KDDA算法映射到高維的非線性空間，挖掘出非線性定位特征，使得各樣本點之間離散度最大、樣本點內部之間的離散度最小，去除冗余定位特征和噪聲;然后將提取出的定位特征和物理坐標作為輸入樣本對輸入到LSSVR算法中來建立定位特征和物理位置的最小二乘支持向量回歸函數，通過SFLA算法優化LSSVR算法的核寬度參數δ和懲罰參數C;最后將測試點RSS信號經KDDA變換后輸入回歸函數，得到測試點估計位置.另一方面通過實驗對比可以看出KDDA-SFLA-LSSVR算法在相同的采樣次數情況下的定位精度明顯高于WKNN，ANN，LSSVR算法，在定位精度相同的情況下能較大減少采樣樣本數，是一種性能良好的WLAN室內定位方法.

[1]Yang Yinggu, Lo A, Niemegeers I. A survey of indoor positioning systems for wireless personal networks [J]. IEEE Communications Surveys & Tutorials, 2009, 11(1): 13-32

[2]Zhang Minghua, Zhang Shensheng, Cao Jian. Indoor location based on signal strength in wireless local area network [J]. Computer Science, 2007, 34(6): 68-75 (in Chinese)(張明華, 張申生, 曹健. 無線局域網中基于信號強度的室內定位[J]. 計算機科學, 2007, 34(6): 68-75)

[3]Du Feng, Tian Shiwei, Li Guangxia. WLAN positioning review[C/CD/OL] //Proc of the 5th China Satellite Navigation Conf. Beijing: CNKI, 2014 [2016-01-01]. http://www.docin.com/p-1412405289.html (in Chinese) (杜峰, 田世偉, 李廣俠. WLAN定位綜述[C/CD/OL]. //第5屆中國衛星導航學術年會論文集. 北京: 中國知網, 2014 [2016-01-01]. http://www.docin.com/p-1412405289.html)

[4]Liu Jianglong, Wan Yihe, Xu Baogen, et al. A novel indoor positioning method based on location fingerprinting [C] //Proc of the 9th Int Conf on Communications, Circuits and Systems (ICCCAS). Piscataway, NJ: IEEE, 2013: 239-242

[5]Borenovic M, Neskovic A. ANN based models for positioning in indoor WLAN environments [C] //Proc of the 19th Telecommunications Forum. Piscataway, NJ: IEEE, 2011: 305-312

[6]Zhang Guowei, Xu Zhan, Liu Dan. Research and improvement on indoor localization based on RSSI fingerprint database and K-nearest neighbor points [C] //Proc of the 9th Int Conf on Communications, Circuits and Systems (ICCCAS). Piscataway, NJ: IEEE, 2013: 68-71

[7]Li Ying, Hu Zhigang. An indoor location model based on BP neural network [J]. Computer Technology and Automation, 2007, 26(2): 78-80 (in Chinese)(李瑛, 胡志剛. 一種基于BP神經網絡的室內定位模型 [J]. 計算機技術與自動化, 2007, 26(2): 78-80)

[8]Deng Zhian, Xu Yubing. A support vector regression algorithm for indoor positioning in wireless local area network [J]. Chinese Journal of Scientific Instrument, 2009, 30(6): 578-582 (in Chinese)(鄧志安, 徐玉濱. 基于支持向量機回歸算法的WLAN室內定位系統[J]. 儀器儀表學報, 2009, 30(6): 578-582)

[9]Lu J W, Plataniotis K N, Venetsanopoulos A N. Face recognition using kernel direct discriminant analysis algorithms [J]. IEEE Trans on Neural Networks, 2003, 14(1): 117-126

[10]Guo Jinyu, Li Yuan, Kong Xiaoguang, et al. Palm print identification based on local projection and kernel direct discriminant analysis [J]. Journal of Optoelectronics Laser, 2011, 22(1): 128-130 (in Chinese)(郭金玉, 李元, 孔曉光, 等. 基于局部保持投影和核直接判別分析的掌紋識別 [J]. 光電子激光, 2011, 22(1): 128-130)

[11]Hasanien H M. Shuffled frog leaping algorithm-based static synchronous compensator for transient stability improvement of a grid-connected wind farm [J]. IET Renewable Power Generation, 2014, 8(6): 722-730

[12]Mustafa M W, Sulaiman M H, Shareefh H, et al. Reactive power tracing in pool-based power system utilising the hybrid genetic algorithm and least squares support vector machine [J]. IET Generation, Transmission & Distribution, 2012, 6(2): 133-141

[13]Issac N S, Palanisamy P, Zhang W J, et al. Log-gabor wavelets based breast carcinoma classification using least square support vector machine [C] //Proc of the 4th IEEE Int Conf on Imaging Systems and Techniques (IST). Piscataway, NJ: IEEE, 2011: 219-223

[14]Suykens J A K, Gestel T V, Brabanter J D, et al. Least Square Support Vector Machines [M]. River Edge, NJ: World Scientific Publishing, 2002: 71-111

[15]Lu J W, Plataniotis K N, Venetsanopoulos A N. Face recognition using LDA-based algorithms[J]. IEEE Trans on Neural Networks, 2003, 14(1): 192-200

Indoor Positioning Algorithm for WLAN Based on KDDA and SFLA-LSSVR

Zhang Yong1,2, Li Feiteng1, and Wang Yujie1

1(School of Computer and Information, Hefei University of Technology, Hefei 230009)2(Post-Doctoral Research Center of Wuhu Overseas Student Pioneer Park, Wuhu, Anhui 241000)

The time-varying received signal strength (RSS) degrades the indoor positioning accuracy in wireless local area network (WLAN). A novel indoor positioning algorithm based on kernel direct discriminant analysis (KDDA) and shuffled frog leaping algorithm and least square support vector regression (SFLA-LSSVR) is proposed to address the problem. Firstly the proposed algorithm employs kernel function strategy to map RSS signal to the field of nonlinear, which is sampled from each access point (AP), and extracts nonlinear features effectively, and reconstructs the positioning information, and discards the redundant positioning features and noise. Secondly, LSSVR algorithm is employed to build the mapping relation model between positioning features and physical locations, and SFLA is employed to optimize the parameters of the relation model, and then test points’ locations are predicted by using the relation model. Experimental results show that the positioning accuracy of the proposed algorithm is much superior to WKNN, ANN, LSSVR algorithm under the condition of the same sampling numbers, and the number of RSS signal which is sampled from each AP is significantly reduced in the same positioning accuracy, and the proposed algorithm is a WLAN indoor positioning algorithm with good performance.

received signal strength (RSS); wireless local area network (WLAN); indoor positioning; kernel direct discriminant analysis (KDDA); shuffled frog leaping algorithm (SFLA); least square support vector regression (LSSVR)

Zhang Yong, born in 1973. Postdoctoral, associate professor. His main research interests include intelligent information processing, WLAN indoor positioning.

Li Feiteng, born in 1991. Master candidate. His main research interests include intelligent information processing, WLAN indoor positioning, pattern recognition.

Wang Yujie, born in 1980. PhD, lecturer. Her main research interests include intelligent information processing, pattern recognition.

2016-01-13；

2016-04-13

國家科技支撐計劃項目(2013BAH52F01) This work was supported by the National Key Technology Research & Development Program of China (2013BAH52F01).

李飛騰(18205697955@163.com)

TP393.17