孫順遠，徐逸飛，秦寧寧，2*

(1.江南大學(xué)輕工過程先進控制教育部重點實驗室 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫 214122；2.南京航空航天大學(xué)電磁頻譜空間認知動態(tài)系統(tǒng)工信部重點實驗室，江蘇 南京 211106)

近年來，位置服務(wù)(Location Based Services，LBS)不斷普及，人們對于高精度的室內(nèi)定位需求也不斷增加。不同于傳統(tǒng)的衛(wèi)星定位系統(tǒng)，如GPS、北斗定位系統(tǒng)等，能夠在室外實現(xiàn)精確的定位與導(dǎo)航[1]，但室內(nèi)定位通常面鄰諸多問題。由于室內(nèi)衛(wèi)星信號衰減，同時還有電磁干擾等，定位精度達不到使用要求，因此如何實現(xiàn)高精度室內(nèi)定位成為了當(dāng)前定位導(dǎo)航領(lǐng)域的研究重點[2]。針對室內(nèi)定位存在的各種問題，國內(nèi)外的學(xué)者提出了很多定位技術(shù)，如Wi-Fi、Bluetooth、RFID、UWB 等[3-6]。其中，基于Bluetooth 的定位方法成本較低，可以實現(xiàn)低功耗定位，且大部分智能終端都集成了藍牙模塊，為該技術(shù)的推廣應(yīng)用提供了良好的基礎(chǔ)。

使用藍牙技術(shù)進行室內(nèi)定位時，需要預(yù)先在定位場景中布置藍牙信標節(jié)點也就是接入點(Access Point，AP)，但這些信標節(jié)點只能向外廣播信號強度，無法提供到達時間差等信息，因此采用基于接收信號強度(Received Signal Strength，RSS)的指紋法實現(xiàn)定位[7]。為了找出待測點信號與指紋庫中各信號之間的關(guān)系，許多學(xué)者提出了機器學(xué)習(xí)的方法，如KNN[8]、神經(jīng)網(wǎng)絡(luò)[9]等，但是傳統(tǒng)的定位方法存在著定位精度低、訓(xùn)練時間長、環(huán)境適應(yīng)性差等缺點。文獻[10]提出了基于極限學(xué)習(xí)機(Extreme Learning Machine，ELM)的室內(nèi)定位方法，該算法網(wǎng)絡(luò)結(jié)構(gòu)緊密，無需調(diào)整中間權(quán)值，極大的減少了訓(xùn)練時間。文獻[11]將樽海鞘群優(yōu)化算法(Slap Swarm Algorithm，SSA)應(yīng)用到ELM 中，優(yōu)化了網(wǎng)絡(luò)中隨機產(chǎn)生的輸入連接權(quán)值和隱藏層的偏置值，提高了ELM 的泛化能力且避免了過擬合的問題。文獻[12]在ELM 的基礎(chǔ)上引入了核函數(shù)，提出了基于核函數(shù)極限學(xué)習(xí)機(Kernel Based Extreme Learning Machine，KELM)的室內(nèi)定位方法，提高了定位精度同時泛化性能更好。文獻[13]則是進一步優(yōu)化ELM 算法，加入了在線順序?qū)W習(xí)階段。該方法可以逐個或逐組學(xué)習(xí)新加入的數(shù)據(jù)，能夠快速適應(yīng)環(huán)境的變化，不需要重新學(xué)習(xí)所有數(shù)據(jù)，靈活性更強。

綜合上述方法的優(yōu)點，提出了一種基于SSAOSKELM 指紋庫自適應(yīng)的室內(nèi)定位算法。在定位場景中的各參考點(Reference Point，RP)采集RSS 數(shù)據(jù)構(gòu)建指紋庫，使用以皮爾森相關(guān)系數(shù)為距離標準的K-means 聚類算法對定位場景進行分區(qū)；然后使用KELM 算法對各個分區(qū)建立定位模型，并使用SSA算法優(yōu)化KELM 中待確定的參數(shù)，提高定位精度，提升模型的泛化性能。當(dāng)環(huán)境發(fā)生變化，有新數(shù)據(jù)加入時，先將新數(shù)據(jù)分配至相應(yīng)的分區(qū)，然后利用在線順序?qū)W習(xí)將新增數(shù)據(jù)集加入定位模型，使用更新后的模型進行定位，使該模型能夠跟上環(huán)境的變化，提高了自適應(yīng)性。

1 指紋庫構(gòu)建

1.1 指紋數(shù)據(jù)采集

在離線階段，根據(jù)藍牙信標信號強度的衰減模型確定各AP 的安裝間距，隨后在定位區(qū)域中選取若干RP，在RP 采集接收到的各AP 的RSS 和該參考點的實際坐標，并將其存入指紋庫中。其中，包括M 個AP，記為APm，m＝1，2，…，M，和N個RP，記為RPn，n＝1，2，…，N，則在RPn處接收到來自APm信號的信號強度可記為rssmn。因此，指紋庫可定義為:

為了減小定位時的數(shù)據(jù)計算量同時提高定位精度，通常會將定位區(qū)域劃分為K個更小的目標區(qū)域，記為Ck，k∈{1，2，…，K}，則分區(qū)指紋庫可定義為:

1.2 基于K-means 的指紋數(shù)據(jù)劃分

通常定位指紋庫包含了從大量參考點收集到的RSS 數(shù)據(jù)，而定位測試點只需要使用部分指紋庫的參考點數(shù)據(jù)即可。并且室內(nèi)環(huán)境中存在著噪聲，導(dǎo)致異常指紋點的產(chǎn)生，從而使定位產(chǎn)生較大的偏差。因此，采集到指紋數(shù)據(jù)庫后，可以根據(jù)各RP 的信號強度以及其所在位置，使用改進的K-Means 聚類算法對指紋庫進行劃分。將原本的大區(qū)域劃分成各個小區(qū)域，再進行定位。本文使用皮爾森相關(guān)系數(shù)[14]計算兩個點之間的相關(guān)性，對于指紋庫中的兩個參考點fi和fj，相關(guān)系數(shù)可表示為:

皮爾森相關(guān)系數(shù)是一種線性相關(guān)系數(shù)，定義為兩點的協(xié)方差和標準差乘積的比值。皮爾森系數(shù)的值介于-1 到1 之間，值越大，fi和fj之間的相關(guān)性就越強。根據(jù)各個參考點RSS 的相關(guān)性將相似度高的RP 聚為一類，則第k個分區(qū)的聚類中心可以用分區(qū)中所有RSS 的均值表示:

式中，｜Ck｜表示第k個分區(qū)所包含的數(shù)據(jù)個數(shù)。

2 基于SSAOS_KELM 的精確定位方法

2.1 核極限學(xué)習(xí)機原理

極限學(xué)習(xí)機(ELM)本質(zhì)上是一種只有單層前饋網(wǎng)絡(luò)的神經(jīng)網(wǎng)絡(luò)。不同于傳統(tǒng)的神經(jīng)網(wǎng)絡(luò)，在任意選擇輸入權(quán)值和隱藏層偏差后，ELM 只需求出隱藏層輸出矩陣的廣義逆矩陣就可以得到輸出權(quán)值。ELM 以一種新型的學(xué)習(xí)方式，解決了傳統(tǒng)神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)速度慢、易陷入局部最優(yōu)等缺點。

由1.2 節(jié)可知，定位場景已經(jīng)被分割成了K個小區(qū)域。則在區(qū)域Ck中，以該區(qū)域中參考點的rssn，k作為輸入，以各參考點的位置標簽tn，k作為輸出訓(xùn)練定位模型，其公式如下:

式中，h(x)和H為隱藏層輸出矩陣，wi為連接輸入層和隱藏層的權(quán)值，bi為隱藏層節(jié)點的閾值；β為連接隱藏層與輸出層的權(quán)值；ν為正則化系數(shù)；x為輸入向量；T為訓(xùn)練集標簽，Nh為隱藏層數(shù)。

當(dāng)輸出矩陣H未知時，可以使用核函數(shù)來代替，映射函數(shù)g(x)的具體形式可不用給出。核函數(shù)可以將指紋數(shù)據(jù)升維，把原本在低維空間中并不線性可分的rss 向量映射到高維空間，增大其線性可分的可能性，從而更精準地實現(xiàn)定位。在分區(qū)Ck中，KELM 核矩陣可定義為ΩELM＝HHT和Ωij＝h(rssi，k)h(rssj，k)T＝K(rssi，k，rssi，k)，根據(jù)式(5)可知，KELM 的輸出公式如下所示:

常用的核函數(shù)如線性核函數(shù)、多項式核函數(shù)和徑向基核函數(shù)(Radial Basis Function，RBF)也稱為高斯核函數(shù)等都可用于KELM。經(jīng)過實驗，使用RBF 時定位精度最高，其公式如(8)所示:

式中，‖x-y‖為樣本間歐氏距離的范數(shù)，σ為高斯核參數(shù)。

KELM 使用核函數(shù)矩陣代替了ELM 中的隨機映射矩陣，根據(jù)式(7)和式(8)可知，只有正則化系數(shù)ν和高斯核參數(shù)σ會對該分類器產(chǎn)生影響，只需調(diào)整這兩個參數(shù)即可。

2.2 基于樽海鞘優(yōu)化算法的KELM

2017 年Mirjalili 等人提出了樽海鞘優(yōu)化算法(SSA)[15]，該算法根據(jù)海洋里樽海鞘鏈的群體覓食行為，進而發(fā)展演化而來。樽海鞘鏈由兩種類型的樽海鞘組成:領(lǐng)導(dǎo)者和追隨者，領(lǐng)導(dǎo)者處于鏈的頭部，帶領(lǐng)群體移動，鏈上后邊的都是追隨者角色。

SSA 優(yōu)化算法主要分為以下2 個部分:

①領(lǐng)導(dǎo)者位置更新

假設(shè)樽海鞘群由Q個維度為D的樽海鞘組成，構(gòu)成了一個D×Q的歐式空間。由2.1 節(jié)可知，KELM 只有正則化系數(shù)ν和高斯核參數(shù)σ需要優(yōu)化，因此每個樽海鞘個體的維度D即為2。在搜索空間中，每個樽海鞘的空間位置用n＝1，2，…，Q表示，樽海鞘群搜索的食物位置用S＝[s1，s2]T表示。樽海鞘群搜索的上界用ub ＝[vmax，σmax]表示，下界用lb＝[vmin，σmin]表示，規(guī)定了參數(shù)ν和σ的范圍。隨后按照式(9)隨機初始化種群:

在樽海鞘鏈移動和覓食的過程中，處于鏈頭部的即為領(lǐng)導(dǎo)者。在種群初始化完成或樽海鞘群位置更新后，SSA 算法以測試集的平均定位誤差e為依據(jù)，重新確定領(lǐng)導(dǎo)者。e的值越小，則表明該個體離食物越近，將該個體作為領(lǐng)導(dǎo)者，其位置作為新一輪迭代的食物位置。在分區(qū)Ck中，平均定位誤差e的公式如式(10)所示:

得到食物位置后，用X1表示領(lǐng)導(dǎo)者在搜索空間中的位置，其位置更新公式如式(11)所示:

由式(11)可以發(fā)現(xiàn)，領(lǐng)導(dǎo)者位置的更新僅與食物來源有關(guān)。式中，控制參數(shù)θ2，θ3是均勻分布于0和1 之間的隨機數(shù)，可以增強X1的隨機性，從而提高樽海鞘鏈全局搜索和個體的多樣性?？刂茀?shù)θ1主要用于控制整個群體的探索能力和開發(fā)能力，是SSA中最重要的參數(shù)。當(dāng)θ1的值比較大時，樽海鞘群的探索能力較強，而當(dāng)值比較小時，則有助于提升局部開發(fā)能力。其定義如式(12)所示:

式中，l是當(dāng)前迭代次數(shù)，L是最大迭代次數(shù)。

②追隨者位置更新

在樽海鞘移動和覓食的過程中，追隨者的前后個體是相互影響的，能夠有效避免因領(lǐng)導(dǎo)者前期搜索不充分而陷入局部極值的情況發(fā)生，并且還能夠有效地搜索全局最優(yōu)。追隨者按照式(13)更新其位置:

式中，Xn和Xn-1是彼此緊連的兩個樽海鞘的位置，因此所有的追隨者都由領(lǐng)導(dǎo)者直接或間接引領(lǐng)。

2.3 在線連續(xù)學(xué)習(xí)

對于許多使用單層前饋網(wǎng)絡(luò)的應(yīng)用來說，通常采用的是批量學(xué)習(xí)的方法。當(dāng)定位場景發(fā)生變化時，需要將新數(shù)據(jù)和舊數(shù)據(jù)一起重新訓(xùn)練，從而消耗了大量的時間。而在線順序極限學(xué)習(xí)機(Online Sequential Extreme Learning Machine，OS-ELM)克服了此缺點，該方法能夠?qū)﹄[藏層輸出權(quán)值矩陣進行分解，不需要重新訓(xùn)練定位模型，因此能夠更好地適應(yīng)環(huán)境變化。OS-ELM 不僅可以逐個學(xué)習(xí)訓(xùn)練數(shù)據(jù)，還可以逐塊學(xué)習(xí)訓(xùn)練數(shù)據(jù)，并且可以丟棄之前已經(jīng)訓(xùn)練好的數(shù)據(jù)，是一種通用的順序?qū)W習(xí)算法。

使用KELM 替代ELM 后，為簡單起見，令A(yù)＝(I/v＋ΩELM)。沒有新數(shù)據(jù)加入時，在分區(qū)Ck中，記A矩陣為At，k，其公式如式(14)所示:

在輸入一組新測得的指紋數(shù)據(jù)fadd，n＝{rssadd，n，(xadd，n，yadd，n)｜n＝1，2，…，h}后，通過計算新增數(shù)據(jù)的rssadd，n與各聚類中心之間的皮爾森相關(guān)系數(shù)，將該數(shù)據(jù)分配至已劃分好的相應(yīng)區(qū)域，判斷依據(jù)如下:

在各分區(qū)收到新增數(shù)據(jù)后，記A矩陣為At＋1，k，公式如式(16)所示:

式中，Ut，k和Dt，k的公式如下:

在線階段，初始化定位模型訓(xùn)練完成后加入幾組新數(shù)據(jù)，數(shù)據(jù)的總數(shù)量為π，經(jīng)過訓(xùn)練后得到Aπ。隨后，在實際場景中采集Nt組數(shù)據(jù)，記為ftest，n＝{rsstest，n，(xtest，n，ytest，n)，ttest，n｜n＝1，2，…，Nt}。按照式(15)將測試數(shù)據(jù)分配至相應(yīng)分區(qū)作為該分區(qū)定位模型的輸入，可得:

2.4 算法計算復(fù)雜度分析

在OS-KELM 算法中，At＋1是在At的基礎(chǔ)上得出的。因此，在線順序?qū)W習(xí)的過程中，At需要一直保存而不能像OS-ELM 一樣用完即棄。該方法都能將新采集的數(shù)據(jù)加入定位模型中，不需要重新訓(xùn)練，大幅減輕了計算量，提高了模型的自適應(yīng)性。At＋1的計算成本的公式如下:

式中，cost () 表示括號內(nèi)變量的計算成本，cost(*｜*)表示括號內(nèi)后一個變量已知的情況下，前一個變量的計算成本。其中，矩陣的維度為N×N，矩陣Ut的維度為N×h，矩陣Ct的維度為h×h，則At＋1的計算成本為:

2.5 算法流程

基于SSAOS-KELM 的指紋定位算法流程如表1所示。

表1 SSAOS-KELM 算法流程

3 實驗分析

3.1 實驗配置

實驗場景為江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院C 區(qū)一樓“L”型走廊區(qū)域。本實驗研究的是基于藍牙的室內(nèi)定位技術(shù)，采用NRF52832 低功耗藍牙模塊作為信標節(jié)點。根據(jù)測試所得的藍牙信號強度衰減趨勢，在走廊的邊沿每隔一定距離布置一個藍牙信標作為AP。場景細節(jié)描述如下:

“L”型走廊區(qū)域由兩個連通的矩形區(qū)域組成，區(qū)域中共放置了11 個AP，如圖1 所示。以1 m×1 m為單位進行劃分，在場景中共得到156 個點并將其作為采樣點，即為RP。在每個RP 采集四次RSS 數(shù)據(jù)，與各RP 的實際位置和標簽一起組成定位指紋數(shù)據(jù)庫。將其中468 組數(shù)據(jù)作為訓(xùn)練集，156組數(shù)據(jù)用于測試和驗證，用于訓(xùn)練的468 組數(shù)據(jù)中再分出156 組數(shù)據(jù)作為新增數(shù)據(jù)集。

圖1 實驗場景平面圖

在仿真階段，采用MATLAB2019b 仿真平臺，選取ELM、BP 神經(jīng)網(wǎng)絡(luò)作為對比算法與本文提出的算法進行對比分析。算法中SSA 優(yōu)化部分參數(shù)配置為:種群數(shù)量Q＝30，最大迭代次數(shù)L＝30，正則化系數(shù)ν的搜索范圍為[0，200]，高斯核參數(shù)σ的搜索范圍為[0，100]。對比分析聚類前后效果、新增數(shù)據(jù)加入前后效果以及各算法的定位精度。

3.2 聚類效果分析

本文采用了基于皮爾森相關(guān)系數(shù)的K-means 聚類方法對指紋庫中的RP 進行劃分，將相關(guān)度高的RP 歸為一類。在“L”型走廊區(qū)域中，某個AP 周圍的信號強度分布如圖2 所示。不難看出，靠得越近則信號強度越大，總體呈高斯分布。因此，可以根據(jù)各RP 的信號強度對該區(qū)域進行聚類，聚類效果如圖3 所示。

圖2 實驗場景中某AP 信號分布

圖3 聚類效果圖

將“L”形走廊場景中的156 組測試數(shù)據(jù)采用本文所提出的算法進行測試，在聚類前和聚類后各做一組實驗，通過累計誤差分布圖(Cumulative Distribution Function，CDF)展示定位誤差，如圖4 所示。由圖可知在聚類前，僅有60%的測試點定位誤差小于2 m，而聚類后90%左右的測試點定位誤差小于2 m，定位精度明顯提高。同時，定位誤差的最大值也從6.2 m 下降至3.5 m，穩(wěn)定性也得到了明顯提升。故采用皮爾森相關(guān)系數(shù)改進的K-Means 算法能有效提升定位的精度與穩(wěn)定性，對抗環(huán)境干擾。

圖4 SSA-OSKELM 聚類前后誤差分析

3.3 在線順序?qū)W習(xí)對自適應(yīng)性的影響

3.3.1 定位精度分析

在實際應(yīng)用中，可能存在指紋庫數(shù)據(jù)收集不全面、環(huán)境發(fā)生改變等情況。當(dāng)新數(shù)據(jù)加入時，傳統(tǒng)的定位方法通常需要重新訓(xùn)練模型。本文提出了使用在線順序?qū)W習(xí)新加入數(shù)據(jù)，避免模型的重新訓(xùn)練，在某種程度上可以減少離線階段的人力和時間成本，提高算法對環(huán)境的自適應(yīng)性。

在“L”形走廊場景中，將新增數(shù)據(jù)集分兩次加入。由表2 可知，除了分區(qū)三由于第一次更新時，新增數(shù)據(jù)集存在異常數(shù)據(jù)，導(dǎo)致定位誤差增大外，其他分區(qū)定位誤差都會隨著新增數(shù)據(jù)加入而變小。兩次模型更新后，在新增加了1/3 數(shù)據(jù)的情況下，總體平均誤差也由1.26 m 降至1.06 m，定位精度提升了15%。因此，當(dāng)環(huán)境發(fā)生變化時，本文所提出的算法能夠在原有定位模型的基礎(chǔ)上更新模型，自適應(yīng)性更好。

表2 在線學(xué)習(xí)前后的平均定位誤差 單位:m

3.3.2 時間復(fù)雜度分析

當(dāng)新增數(shù)據(jù)加入時，使用在線順序?qū)W習(xí)和模型重新訓(xùn)練所需的時間如表3 所示。

表3 SSAOS-KELM 與SSA-KELM 比較

從表中可以看出，在原有數(shù)據(jù)庫基礎(chǔ)上新增了兩組數(shù)據(jù)后，對156 個參考點的數(shù)據(jù)整體進行訓(xùn)練將耗費近30 s 的時間，而使用在線順序?qū)W習(xí)加入兩組數(shù)據(jù)在1 s 以內(nèi)就可以完成。因此當(dāng)目標區(qū)域越大時，重新訓(xùn)練模型耗費的時間越多，本文所提出的方法避免了重新訓(xùn)練，可以大大減少訓(xùn)練時間。

3.4 定位誤差分析

定位誤差主要選取誤差箱型圖和累計誤差分布(CDF)來進行分析，在“L”形走廊場景中分別使用ELM、BP 神經(jīng)網(wǎng)絡(luò)和SSAOS-KELM 算法進行測試，實驗結(jié)果如圖5 和圖6 所示。

由圖5 可知，本文提出的SSAOS-KELM 算法與其他兩種算法相比，有著最低的誤差中位線，約為0.63 m 左右，定位精度最高；BP 神經(jīng)網(wǎng)絡(luò)與該算法誤差中位線相近，但其誤差分布較廣，離群點多，穩(wěn)定性稍差。所有的算法經(jīng)過聚類后，離群點變少，定位精度均有所上升。

圖5 三種方法的定位誤差箱型圖

由圖6 可知，本文提出的算法近90%的測試點定位誤差在2 m 以內(nèi)，最大定位誤差也是最小的；BP 神經(jīng)網(wǎng)絡(luò)次之，但其聚類前后誤差相差不大，最大定位誤差稍有減??；ELM 算法定位誤差最大。在聚類后，這三種算法的累計誤差均有不同程度的提升?？傮w而言，本文所提出的算法相較于其他兩種算法定位精度和穩(wěn)定性更好。

圖6 三種方法的累計定位誤差分布圖

4 結(jié)論

基于SSAOS-KELM 指紋庫自適應(yīng)的室內(nèi)定位算法，利用皮爾森相關(guān)系數(shù)改進的K-means 算法對待定位區(qū)域進行聚類劃分；隨后通過樽海鞘(SSA)算法優(yōu)化KELM 參數(shù)為每個分區(qū)建立定位模型；最后通過在線順序?qū)W習(xí)添加新數(shù)據(jù)，更新定位模型，并實現(xiàn)定位。從實驗結(jié)果可以看出，算法的定位精度明顯提高，且對環(huán)境的適應(yīng)性更好。但該算法只能在定位模型中加入新數(shù)據(jù)，并不能將模型中已經(jīng)發(fā)生改變的舊數(shù)據(jù)清除，有待改進。