基于粒子群優化在線順序極限學習機動態環境室內定位算法

韓承毅，蘇勝君，施偉斌，樂燕芬，李瑞祥

（上海理工大學光電信息與計算機工程學院，上海 200093）

引 言

在室內定位中，基于接收信號強度值（Receive signal strength，RSS）的解決方案具備成本低，易實現，精度較高等特性［1?3］，在靜態室內環境定位問題中得到廣泛的運用。但是，障礙物和人員位置等室內環境因素發生變化時，基于RSS方案會導致定位誤差較大等問題。如果重構指紋數據庫和訓練模型，會導致實驗成本高、耗時長。在線順序極限學習機（Online sequential extreme learning machine，OS?ELM）算法［4］適合在動態環境下進行室內定位，在變換的新環境中，只需在少量的參考點上采集新的指紋庫數據信息，用來更新補充上一次訓練模型的參數，就可以在新環境中進行在線估計位置信息。在室內動態環境中，該算法相比于靜態室內定位算法，在定位時間上和性能上有較高的提升。但是，OS?ELM算法在模型輸入層和隱含層之間的權重和隱含層上的偏置是隨機賦值的，這就導致了隱含層輸出矩陣和其轉置矩陣乘法結果可能具有奇異性或者病態性［5］。當在新環境中采集的數據流發生變化時，隨機賦值的權重和偏置，會導致OS?ELM算法隱含層輸出矩陣和其轉置之間的矩陣乘法結果不具有可逆解，這一缺陷導致了OS?ELM算法的泛化性能較差［6］。

針對此問題，本文提出了PSO?OS?ELM算法，利用粒子群優化算法（Particle swarm optimization，PSO），解決OS?ELM算法中輸入層和隱含層權重和隱含層的偏置隨機賦值問題，從而有效地控制了OS?ELM算法中的隱含層輸出矩陣和其轉置矩陣乘積為奇異矩陣或者病態矩陣的問題。本文算法繼承了OS?ELM算法框架，引入PSO算法尋優環節，且解決了以下3點問題：（1）解決了RSS的時變性問題；（2）解決了OS?ELM算法隱含層輸出矩陣和其轉置乘法結果可能為奇異矩陣或者病態矩陣的問題；（3）解決了定位算法耗時長問題。

1 算法的框架與原理

針對動態室內定位環境問題，Yang等［7］利用在線順序極限學習機方法，在新環境中采集新數據來更新調節模型參數，有效降低了在動態變化環境中重復大規模采集數據的成本，能夠自動及時適應環境變化，算法收斂速度較快，具有較高的定位精度。但是OS?ELM算法中輸入層到隱含層之間的輸入權重和隱含層閾值的隨機性，導致了算法的魯棒性并不很好［8］。

1.1 OS?ELM算法

極限學習機（Extreme learning machine，ELM）是一種單隱層前饋神經網絡架構［9］，在ELM模型之上引入在線順序機制，就形成OS?ELM網絡模型。OS?ELM網絡模型由輸入層、隱含層、輸出層構建形成，整個網絡模型如圖1所示。在圖1中，為第j次采集數據且來自于第d個AP的信號強度，w i為隱含層第i個神經元與輸入層所有神經元連接的權重，為隱含層第i個神經元與輸入層第j個神經元連接的權重，b i為隱含層第i個神經元的閾值大小，g(?)為隱含層神經元的激活函數，βi為隱含層第i個神經元與輸出神經元之間的權重為第j次輸出層的第k個維度的數值，L為隱含層神經元的個數；OS?ELM算法分為初始化階段和在線學習階段。

圖1 OS-ELM算法網絡模型Fig.1 OS-ELM algorithm network model

（1）初始化階段

步驟1輸入權重w i和閾值b i在［-1，1］范圍內等概率地隨機賦值，i=1，2，…，L。

步驟2計算隱含層初始輸出矩陣H0，是一個N0維L列向量。

步驟3 計算初始輸出權重

整個網絡模型可寫為

式（1）可以簡寫為

式中

整個問題就等價于式（3）。

式中H0代表著初始時刻系統矩陣。由于OS?ELM算法中的輸入權重和隱含層輸入閾值是隨機賦值的，這就導致矩陣HT0H0可能是不可逆矩陣或者是病態矩陣。如果矩陣HT0H0可逆［10］，那么β(0)=P0HT0T0，其中P0=(HT0H0)-1，記K0為初始時刻P0的逆矩陣參數

步驟4設置k=0，k表示數據采集的次數。

（2）順序學習階段

當環境發生變化時，就需要在新環境中采集新數據集。

設定第k+1次采集的新數據集為

式中N j為第j次采集RSS數據集的大小。

步驟1隱含層輸出矩陣H k+1

式中H k+1為第k+1次隱含層神經元輸出結果，由新環境下采集到的錨節點信號強度數據計算得出。

步驟2隱含層到輸出層之間的權重β(k+1)

將式（6）轉換為式（8），有

步驟3k=k+1返回順序學習階段。

1.2 PSO?OS?ELM算法

Han等［11］指出OS?ELM算法中輸入權重w和隱含層閾值b是隨機賦值，矩陣HTH可能出現病態矩陣，導致整個算法魯棒性較差。根據文獻［12?15］可知，矩陣的條件數是可以作為判斷矩陣是否病態的一種度量。條件數越大，矩陣越病態。矩陣H的條件數可以寫為

式中：λmax(HTH)為矩陣HTH的最大特征值，λmin(HTH)為矩陣HTH的最小特征值。當HTH的條件數越小時，說明HTH病態性越小，模型的魯棒性越強，模型的誤差越小。本文PSO算法中的矩陣H的條件數K2(H)作為尋找OS?ELM算法中輸入層和隱含層之間的權重w和隱含層偏置b的最優值準則，使算法魯棒性更強、計算耗時少、定位誤差小。PSO?OS?ELM算法流程如圖2所示。

圖2 PSO-OS-ELM算法框Fig.2 Schematic diagram of PSO-OS-ELM algorithm

步驟1初始化算法中相關參數

PSO算法中的粒子代表著OS?ELM算法中的輸入層權重w和隱含層閾值b的可行解，即粒子p i=[w1，…，w L，b1，…，b L]，每次粒子都有其對應的最優解p ib。f(x)為適應度函數，在本實驗中f(x)=其中t為參考點的實際位置。

步驟2更新每個粒子的局部最優解p ib

式中K i為第i個粒子的條件數，K ib為第i個粒子最小的條件數。

步驟3更新全局最優解p g

式中K g為全局最小的條件數。

在PSO算法迭代更新p ib、p g中，式（9，10）引入矩陣條件f(p ib)-f(p i)<ηf(p ib)、(K i

步驟4根據式（11，12）更新粒子的速度和位置。

式中：i=1，2，…，D，D為粒子的總個數；c1、c2為學習因子；r1、r2為［-1，1］范圍內的隨機數；α為約束因子，控制位置更迭速度；vi為第i個粒子的速度；λ為慣性因子，為非負數，當該值較大，全局尋優能力強，局部尋優能力弱；當該值較小，全局尋優能力弱，局部尋優能力強。

步驟5未達到一定的迭代次數或未滿足一定的誤差范圍，則跳轉到步驟（2）。

步驟6達到結束條件，執行OS?ELM算法流程，在不同的環境中，采集新的數據，按照式（7）進行迭代更新計算。

2 實驗結果及分析

為評估本文提出的PSO?OS?ELM算法的性能，實驗將算法分別同OS?ELM算法和加權K近鄰算法（Weighted K?nearest neighbor，WKNN）算法作對比，評估定位精度、算法耗時和魯棒性等指標。

本次實驗場地為上海理工大學光電樓9樓實驗樓，實驗場地的形狀為矩形，其面積為14 m×58 m。圖3中，紅色三角形標記為錨節點，負責發送信號，在整個實驗場地兩側共分布了13×2個AP節點，每個錨節點間隔4.8 m；黑色方形為測試節點；藍色圓圈為參考節點；紅色圓圈為重新采集點的位置；陰影區域為墻壁或辦公室區域。在不同時間段下，整個實驗場景的空間環境不同、信號強度不同。在大多數的工作日下午的時間段，人員隨機走動或休憩，信號容易受到干擾；在大多數的工作日晚上時間段，人員稀少，空間十分空曠，障礙物少，信號強度一般較好；在非工作日的上午，實驗場地障礙物分布較多，信號強度會受到干擾衰減。

圖3 實驗平面實驗圖Fig.3 Schematic diagram of experimental area

本次實驗將整個實驗環境劃分為3個主要時間段：（1）工作日晚上時間段，無人無障礙物環境；（2）工作日下午時間段，有人無障礙物環境；（3）非工作日上午時間段，有人有障礙物環境。

將CC2530開發板設備放置于藍色參考點上，在3種不同環境中沿著圖3黑色虛線移動，收集到26個AP節點信號強度值。在同一位置多次接收的信號進行數值處理后作為信號強度值，和參考點坐標同時記錄在離線階段的數據指紋庫中。實驗中未接收到的RSS信號強度統一用最小值90 dBm填充。由于接收信號強度的不穩定性，在每個測試點上進行反復測試100次，然后對接收的信號求平均值，作為該點的信號強度值。在順序學習階段中，在圖3中的紅色圓圈中的位置重新采集RSS信號，每個點采集300次，構建一個新的信號強度數據集，避免了重復測量全部點。

利用3種環境中采集到的數據，將本文提出的PSO?OS?ELM算法與OS?ELM算法、WKNN算法（加權K近鄰算法）進行對比分析。本實驗中，經對WKNN算法的K參數大量調優后，當K為4時算法定位精度最佳，故將K取為4。實驗采用平均定位誤差（Mean error，ME）、定位算法耗時、定位誤差的累計密度函數（Cumulative density function，CDF）作為標準來評估算法的性能。

由表1可知，在無人無障礙物情況下，PSO?OS?ELM算法定位誤差相較于OS?ELM算法減少了11.1%、相較于WKNN算法減少了8.48%；在有人無障礙物，PSO?OS?ELM算法定位誤差相較于OS?ELM算法減少了19.4%，相較于WKNN算法減少了24.34%。有人有障礙物的環境下，PSO?OS?ELM算法定位誤差相較于OS?ELM算法減少了27.5%，相較于WKNN算法減少了33.95%。PSO粒子群優化算法確保了OS?ELM算法的魯棒性，削弱了動態環境因素對定位精度的影響。

表1 3種算法在3種不同環境下的平均定位誤差Table 1 Average positioning error of three algorithms in three different environments m

由表2可知，從算法耗時角度來看，在3種環境下，雖然PSO?OS?ELM算法引入了粒子群算法，但與OS?ELM耗時相當，說明粒子群算法的時間復雜度比較小。從WKNN算法的耗時長來看，說明了在動態變化的室內環境中，與重新構建指紋庫訓練預測的方法相比，在線順序學習更新的方法能夠有效減少計算和提高定位算法效率。PSO?OS?ELM算法繼承了OS?ELM算法耗時短的特點，算法耗時相較于傳統定位算法WKNN算法減少了55%左右。

表2 3種算法在3種不同環境下的定位算法耗時Table 2 Time consuming of three algorithms in three different envir onments s

在3種環境下，記錄PSO?OS?ELM算法和OS?ELM算法中的隱含層神經元輸出的矩陣H的條件數K2(H)的最大值，如表3所示?？梢园l現在環境發生變化的情況下，PSO算法可以有效地減小條件數K2(H)，使輸入層到隱含層的權值處于最佳值。結合圖4，可以發現PSO?OS?ELM算法相較于OS?ELM算法，更有效地控制定位誤差，說明算法在動態變化的環境中魯棒性更強。

表3 在3種不同環境下K 2(H)的最大值Table 3 The max value of K 2(H)in three different envir onments

從圖4可知，在每種環境中，PSO?OS?ELM算法在誤差1～1.8 m范圍內，誤差累積分布就達到90%，說明PSO?OS?ELM算法的定位誤差更??；同時，與傳統的WKNN算法相比，通過迭代和更新方式比重建訓練方式更加高效和快速，大大減少訓練的時間。通過圖4（a，b）可知，在3次動態變換的環境中，PSO?OS?ELM算法相較于OS?ELM算法，定位誤差累積分布曲線更加趨同性，能根據外界變化的環境不斷更新調整算法中輸入層和隱含層權重和隱含層的偏置數值，確保定位誤差變小，說明算法在動態變化的環境中魯棒性更強。

圖4 3種算法在3種環境中誤差累積分布函數圖Fig.4 Cumulative distribution function of positioning error about three algorithms in three environments

3 結束語

本文利用PSO算法尋找OS?ELM算法中輸入層和隱含層之間的權重w和隱含層偏置b的最優值，有效地解決OS?ELM算法中的隱含層輸出矩陣和其轉置矩陣乘法結果可能為奇異矩陣或者病態矩陣的問題，使算法魯棒性更強、計算耗時少且定位誤差小。通過實驗結果分析，在有限空間的無人無障礙物、有人無障礙物和有人有障礙物情況下，同WKNN算法相比，PSO?OS?ELM算法定位誤差分別減少了8.48%、24.34%和33.95%；同OS?ELM算法相比，PSO?OS?ELM算法保持較好的魯棒性，并且很好地繼承了OS?ELM算法的泛化能力和較強的非線性逼近特性。本實驗還未針對更大區域范圍內的動態變化室內環境進行定位實驗，這也是本算法的下一階段研究分析目標。