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

（上海理工大學(xué)光電信息與計算機(jī)工程學(xué)院，上海 200093）

引 言

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

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

1 算法的框架與原理

針對動態(tài)室內(nèi)定位環(huán)境問題，Yang等［7］利用在線順序極限學(xué)習(xí)機(jī)方法，在新環(huán)境中采集新數(shù)據(jù)來更新調(diào)節(jié)模型參數(shù)，有效降低了在動態(tài)變化環(huán)境中重復(fù)大規(guī)模采集數(shù)據(jù)的成本，能夠自動及時適應(yīng)環(huán)境變化，算法收斂速度較快，具有較高的定位精度。但是OS?ELM算法中輸入層到隱含層之間的輸入權(quán)重和隱含層閾值的隨機(jī)性，導(dǎo)致了算法的魯棒性并不很好［8］。

1.1 OS?ELM算法

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

圖1 OS-ELM算法網(wǎng)絡(luò)模型Fig.1 OS-ELM algorithm network model

（1）初始化階段

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

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

步驟3 計算初始輸出權(quán)重

整個網(wǎng)絡(luò)模型可寫為

式（1）可以簡寫為

式中

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

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

步驟4設(shè)置k=0，k表示數(shù)據(jù)采集的次數(shù)。

（2）順序?qū)W習(xí)階段

當(dāng)環(huán)境發(fā)生變化時，就需要在新環(huán)境中采集新數(shù)據(jù)集。

設(shè)定第k+1次采集的新數(shù)據(jù)集為

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

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

式中H k+1為第k+1次隱含層神經(jīng)元輸出結(jié)果，由新環(huán)境下采集到的錨節(jié)點(diǎn)信號強(qiáng)度數(shù)據(jù)計算得出。

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

將式（6）轉(zhuǎn)換為式（8），有

步驟3k=k+1返回順序?qū)W習(xí)階段。

1.2 PSO?OS?ELM算法

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

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

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

步驟1初始化算法中相關(guān)參數(shù)

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

步驟2更新每個粒子的局部最優(yōu)解p ib

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

步驟3更新全局最優(yōu)解p g

式中K g為全局最小的條件數(shù)。

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

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

式中：i=1，2，…，D，D為粒子的總個數(shù)；c1、c2為學(xué)習(xí)因子；r1、r2為［-1，1］范圍內(nèi)的隨機(jī)數(shù)；α為約束因子，控制位置更迭速度；vi為第i個粒子的速度；λ為慣性因子，為非負(fù)數(shù)，當(dāng)該值較大，全局尋優(yōu)能力強(qiáng)，局部尋優(yōu)能力弱；當(dāng)該值較小，全局尋優(yōu)能力弱，局部尋優(yōu)能力強(qiáng)。

步驟5未達(dá)到一定的迭代次數(shù)或未滿足一定的誤差范圍，則跳轉(zhuǎn)到步驟（2）。

步驟6達(dá)到結(jié)束條件，執(zhí)行OS?ELM算法流程，在不同的環(huán)境中，采集新的數(shù)據(jù)，按照式（7）進(jìn)行迭代更新計算。

2 實驗結(jié)果及分析

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

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

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

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

將CC2530開發(fā)板設(shè)備放置于藍(lán)色參考點(diǎn)上，在3種不同環(huán)境中沿著圖3黑色虛線移動，收集到26個AP節(jié)點(diǎn)信號強(qiáng)度值。在同一位置多次接收的信號進(jìn)行數(shù)值處理后作為信號強(qiáng)度值，和參考點(diǎn)坐標(biāo)同時記錄在離線階段的數(shù)據(jù)指紋庫中。實驗中未接收到的RSS信號強(qiáng)度統(tǒng)一用最小值90 dBm填充。由于接收信號強(qiáng)度的不穩(wěn)定性，在每個測試點(diǎn)上進(jìn)行反復(fù)測試100次，然后對接收的信號求平均值，作為該點(diǎn)的信號強(qiáng)度值。在順序?qū)W習(xí)階段中，在圖3中的紅色圓圈中的位置重新采集RSS信號，每個點(diǎn)采集300次，構(gòu)建一個新的信號強(qiáng)度數(shù)據(jù)集，避免了重復(fù)測量全部點(diǎn)。

利用3種環(huán)境中采集到的數(shù)據(jù)，將本文提出的PSO?OS?ELM算法與OS?ELM算法、WKNN算法（加權(quán)K近鄰算法）進(jìn)行對比分析。本實驗中，經(jīng)對WKNN算法的K參數(shù)大量調(diào)優(yōu)后，當(dāng)K為4時算法定位精度最佳，故將K取為4。實驗采用平均定位誤差（Mean error，ME）、定位算法耗時、定位誤差的累計密度函數(shù)（Cumulative density function，CDF）作為標(biāo)準(zhǔn)來評估算法的性能。

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

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

由表2可知，從算法耗時角度來看，在3種環(huán)境下，雖然PSO?OS?ELM算法引入了粒子群算法，但與OS?ELM耗時相當(dāng)，說明粒子群算法的時間復(fù)雜度比較小。從WKNN算法的耗時長來看，說明了在動態(tài)變化的室內(nèi)環(huán)境中，與重新構(gòu)建指紋庫訓(xùn)練預(yù)測的方法相比，在線順序?qū)W習(xí)更新的方法能夠有效減少計算和提高定位算法效率。PSO?OS?ELM算法繼承了OS?ELM算法耗時短的特點(diǎn)，算法耗時相較于傳統(tǒng)定位算法WKNN算法減少了55%左右。

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

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

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

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

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

3 結(jié)束語

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