基于KDMSPCS-GRNN 的室內定位技術研究*

王 超 ，單志勇

(1.東華大學 信息科學與技術學院，上海201620；2.數字化紡織技術教育部工程中心，上海201620)

0 引言

隨著第四代網絡通信技術的成熟和微電子行業的迅速發展，移動終端設備在人們日常生活中得到很大程度的普及，人們對基于用戶位置服務(Location Based Services，LBS)[1]的需求愈來愈廣泛。而室內定位技術作為LBS 中必不可少的底層技術，它的好壞將直接影響服務的質量，因此室內定位領域受到技術人員廣泛關注，無線定位技術得到了極大的發展。 目前已經提出的定位技術有RFID、UWB、ZigBee[2]和WiFi[3]等。 相比于其他幾種技術而言，WiFi 在人們日常生活中的覆蓋率更高，且對硬件設備要求較低， 故而更具實踐價值。 目前WiFi 定位技術已經成為室內定位技術研究的主要熱點之一。

WiFi 定位方法很多，其中得到關注較多的是基于位置指紋定位法，該方法的內在機制是通過分析空間中WiFi 接收信號強度(Received Signal Strength，RSS)[4]來搭建RSS 與坐標之間的關系模型，以此來實現室內定位。 文獻[5]構建了基于WiFi 的電磁指紋庫的室內定位系統，分析了影響RSS 信號值的多種因素，使用了BP(Back Propagation)算法對數據進行非線性矯正，但是BP 神經網絡的收斂速度并不理想。 文獻[6]使用了粒子群(Particle Swarm Optimization，PSO)算法來優化BP 神經網絡，構造PSO-BP 模型，但神經網絡結構的復雜性限制了網絡的輸出精度。 文獻[7]通過引入GRNN 網絡來代替BP 神經網絡，構建了GRNN 定位預測模型，但是模型參數的選擇過于依賴人為調整，其多領域推廣性價值不足。 文獻[8]分別通過人為設置、交叉驗證和智能尋優三種方式為GRNN 選擇參數，對比發現，使用智能算法為GRNN 選擇合適的參數具有更好的定位效果。 文獻[9]利用遺傳算法(Genetic Algorithm，GA)全局優化平滑因子構建了GA-GRNN 定位模型，提高了網絡模型的泛化能力，降低了算法復雜度，提升了GRNN 回歸預測效果。 文獻[10]利用蜂群算法優化GRNN 模型參數，使參數因子逼近全局最優，同時引入自適應變化策略，解決了算法后期延滯問題[11]。 文獻[12]將PSO 算法引入GRNN 預測模型，利用PSO 算法種群粒子的趨優性來尋找GRNN 預測模型的最優平滑因子，降低了算法復雜度，提升了GRNN 回歸預測效果。

受上述策略的啟發，本文通過分析多種智能優化算法的優劣性，研究不同算法之間的互補可融性，基于動態分群策略，提出了一種混合LDCPSO 和CS的智能尋優算法，即KDMSPCS 算法。 然后利用此算法為GRNN 選擇最佳的參數，構建定位模型，以此來提高定位預測精度。

1 算法原理

1.1 LDCPSO 算法

PSO 算法是由Kennedy 和Eberhart 根據自然界中群鳥捕食的特點，提出的一種啟發性算法。 標準PSO 算法非常容易陷入局部最優，最終導致得到的優化結果不準確。 故而為了避免陷入局部最優，加快算法的收斂效率，文獻[13]引入自適應選擇策略，通過大量實驗得出標準PSO 算法的迭代參數的變化范圍，構造LDCPSO 算法，并給出新的迭代公式，如下所示：

式中，c1和c2為兩個學習因子，它們的最佳取值范圍是c1∈[1.4，1.6]，c2∈[1.4，1.6]。w為權 重 因子，它的最佳取值范圍為w∈[0.6，0.8]，r1和r2為(0，1)區間的隨機數，pbestid為第i個粒子在第d維空間的個體歷史最優值，gbestd為種群在第d維的歷史最優值，為第i個粒子在第d維空間的分量的第k次迭代位置，為第i個粒子在第d維空間的分量的第k次迭代速度。

1.2 CS 算法

CS 算法由劍橋大學Yang 等人根據自然界鳥類繁衍習性，模擬布谷鳥尋巢產卵的過程，提出的一種新型群體智能算法。 其思想主要是巢寄生特性和萊維飛行機制(Lévy Flight)[14]，通過隨機游走的方式尋找一個最優的寄生巢穴。

在布谷鳥算法中，假設在D維搜索空間中有N個鳥蛋，第i個鳥蛋在第k次迭代的位置為。 布谷鳥的路徑和位置更新公式如式(6)所示：

式中δi為需要進行的位置變化量，如式(7)所示：

式中⊕為點乘，ebest為目前找到的最好鳥巢位置。 隨機步長是由對稱的Lévy 分布產生的，通過Mantegna算法產生si，如式(8)所示：

式中(u1，u2，…，uD)和(v1，v2，…，vD)為D維空間的向量，且有β=1.5。 u 和v 的每個分量服從如式(9)的正態分布，其中u 分布的方差如式(10)所示。

1.3 K-means 聚類算法

K-means 算法[15]是一個依據數據特性，將數據均值作為類中心，循環性變更類中心點以及更新類內部成員的過程。K是算法迭代結束后，根據群體數據特性計算而得到的超參數，它代表類的個數且要小于訓練集樣本數。

K-means 算法的具體步驟描述如下：

(1)確定樣本集{x1，x2，…，xN}、聚類數K以及最大迭代次數T。

(2)根據不同有效性指標，從樣本集中隨機選擇K個樣本作為初始中心向 量{μ1，μ2，…，μK}。

(3)計算樣本xi(i=1，…，N)到每個中心向量μj(j=1，…，K)的距離dij，即dij=||xi-uj||2。 將xi歸為dij最小所對應的類。

(4)計算每一類樣本的均值，并將均值更新為新的中心向量。

(5)循環步驟(2)、(3)，直至達到終止條件。

1.4 GRNN 算法

GRNN 算法[16]是由美國學者SPECHT D F 提出的一種基于非線性回歸理論的神經網絡模型。 其主要原理是根據輸入信號的徑向基函數和神經元參數的線性組合來預測輸出。 對應網絡輸入x=(x1，x2，…，xn)T，其輸出為y=(y1，y2，…，yk)T。 結構如圖1所示。

圖1 GRNN 預測模型結構

輸入層：該層神經元數等于訓練樣本維數n，輸入變量通過線性函數直接傳遞給模式層。

模式層： 該層神經元數量與訓練樣本數量mi相等，各神經元與不同的樣本對應，模式層神經元傳遞函數如式(11)所示：

式中神經元i的輸出為輸入變量與其對應的訓練樣本X 之間Euclid 距離平方，如下式(12)所示：

式中x 為網絡輸入變量，xi為第i個神經元對應的訓練樣本。

求和層：該層節點個數等于輸出樣本維度加一，求和層的輸出分為兩部分，第一個節點輸出為模式層輸出的算術和，其余k個節點的輸出為模式層輸出的加權和，即：第一個節點的輸出如式(13)所示，其余k個節點的輸出如式(14)所示。

式(14)中，yij表示第i個模式層點對應訓練樣本的標簽的第j個元素。

輸出層：輸出層節點個數等于標簽向量的維度，每個節點的輸出等于對應的求和層輸出與求和層第一個節點輸出相除。

2 KDMSPCS 算法

2.1 KDMSPCS 算法的構建

在常見的智能優化算法中，對于種群規模較大的群體，LDCPSO 算法有著較快的收斂速度，并伴存陷入局部的缺點，CS 算法有著較高的收斂精度，但也因大量計算，影響收斂速度。 考慮到進化算法尋優過程中種群多樣性逐步降低的特性，利用分群思想和隨機重組策略，在分群優化的基礎上汲取LDCPSO 算法高速性和CS 算法高精度性，搭建動態多種群LDCPSO 和CS 混合算法。 首先采用K-means算法將種群劃分為多個子群，每個子群底層采用LDCPSO 算法進行優化；然后將各子群的最優粒子送至高層作為CS 算法的種群粒子進行深度優化，并將最終得到的最優粒子返回底層，繼而進行下一次的迭代優化。

在底層優化時，隨著迭代的進行，各個小種群內部粒子總會朝著某個或多個最佳粒子聚集，而一旦有子群在尋優中陷入局部，那么將會喪失部分群體的多樣性，影響最終的收斂結果。 故而為了加強種群粒子之間的信息交流，增加種群的多樣性，本文采用K-means 算法周期性地更新子群， 提高各個子群跳出局部的能力。 而在算法進行高層優化時，CS 優化算法對應的種群規模如果僅僅取決于底層子群個數，那么對于一個進化算法來說，這樣的種群規模太小，多樣性不足。 故而在保證高層優化種群多樣性的同時，也加強高層種群特性對底層種群特性的繼承，本文在底層使用聚類算法分群后，采用文獻[17]提出的多樣性度量方法，選擇一個多樣性較好的子群不做底層優化，直接與其他子群的最優粒子混合進行高層的深度優化，進而增加高層優化種群的規模。 算法1 給出了KDMSPCS 算法的偽代碼。

算法1 KDMSPCS

2.2 算法的性能分析

2.2.1 算法測試函數

為了進一步驗證KDMSPCS 算法的理論分析，研究算法的性能，本文取Sphere、Ackley、Griewank、Bukin、Booth、Sum square 和Beal 七個進化計算常用的基準函數進行測試，各函數的屬性如下：

(1)Sphere 函數

式中xi∈[-5.12，5.12]，i=1，…，d。 當x*=(0，…，0)時，函數f(x*)取得最優值0。

(2)Ackley 函數

式中xi∈[-32.768，32.768]，i=1，…，d，a=20，b=0.2，c=2π。 當x*=(0，…，0)時，函數f(x*)取得最優值0。

(3)Griewank 函數

式中xi∈[-600，600]，i=1，…，d。 當x*=(0，…，0)時，函數f(x*)取得最優值0。

(4)Bukin 函數

其中x1∈[-15，5]，x2∈[-3，3]。 當x*=(-10，1)時，函數f(x*)取得最優值0。

(5)Booth 函數

式中xi∈[-10，10]，i=1，2。 當x*=(1，3)時，函 數f(x*)取得最優值0。

(6)Sum square 函數

式中xi∈[-5.12，5.12] orxi∈[-10，10]，i=1，…，d。當x*=(0，…，0)時，函數f(x*)取得最優值0。

(7)Beal Function

式中xi∈[-4.5，4.5]，i=1，2。 當x*=(3，0.5)時，函數f(x*)取得最優值0。

2.2.2 收斂特性仿真

在KDMSPCS 算法中，子群數量K和動態調整周期R的設定至關重要，如果K值過大或R值過小，則會增加算法的計算量，影響搜索效率；而如果K值過小或R值過大，則會降低種群粒子之間的信息交流，影響算法的搜索精度。 故而本文選擇多峰函數Griewank 來估算最佳的K值和R值。其中參數設定有：維數設為2，最大迭代次數設為100，單個實驗重復次數設為20，種群規模設為1 000，調整周期設為2、5、10、15、20 等多種情況，子群個數設為3、5、7、9、11 等多種情況。以此進行實驗，表1 給出 了不同的參數(R，K)組合在Griewank 函數重復運行20 次的平均最優值。

表1 不同參數(R，K)在Griewank 函數的運行結果

通過表1 可以看出，K、R取值對收斂結果的影響完全符合實驗前的猜測，而當R=10、K=7 時，種群得到相對最好的收斂效果。

然后依據得到的最佳(R，K)組合，參照上文中的參數設置，分別針對收斂精度和收斂速度兩方面對LDCPSO 算法、CS 算法和KDMSPCS 算法進行測試。 表2 給出了三種優化算法針對7 種標準測試函數獨立運行20 次的平均測試結果以及程序運行的總時長。 圖2～圖5 給出了一個單峰和三個多峰測試函數在迭代尋優過程中適應度值的變化。

通過表2 以及圖2～圖5 可以看出，在不同的測試函數下，KDMSPCS 算法相比于LDCPSO 算法在收斂精度上具有絕對優勢，且從三種優化算法針對7種標準測試函數獨立運行20 次的總時長來看，KDMSPCS 算法在優化速度上要明顯優于CS 算法。故而得出KDMSPCS 算法在收斂精度以及收斂速度的綜合性能上要優于LDCPSO 算法或CS 算法。

表2 不同測試函數優化結果及時間

圖2 Ackley 測試函數適應度變化

圖3 Bukin 測試函數的適應度變化

3 KDMSPCS-GRNN 的定位模型設計

3.1 KDMSPCS-GRNN 室內定位基本方案

基于KDMSPCS-GRNN 室內定位模型構建的主要思想是將GRNN 模型的平滑因子參數看作是KDMSPCS 算法的粒子，將模型測試集各點預測值與真實值的均方根誤差函數作為KDMSPCS 算法的適應度函數，通過算法底層的迭代優化獲取GRNN 定位模型最優平滑因子，構建KDMSPCS-GRNN 定位模型。

定位模型的構建主要分為數據、訓練和測試三個階段。 首先根據室內環境特性，將定位區域內等間隔劃分多個數據采集點以及布置多個發送信號的AP 節點； 其次在每個采集點采集形如[RSSi1，RSSi2，…，RSSin]的信號，標記對應點的坐標，構建形如[RSSi1，RSSi1，…，RSSin，Xi，Yi]的數據，并納入樣本庫中；然后考慮到數據采集過程中會受到人員擾動、多徑傳播、環境變化等因素的影響，使得采集的實時數據保真性不足，不具代表性，因此本文采用文獻[18]提出的高斯濾波方案對樣本庫中的數據做進一步的處理，使得納入樣本庫中的數據盡可能有效。最后將樣本庫中測試集數據和訓練集數據作為GRNN 網絡的輸入，進行測試和訓練。 其方案流程圖如圖6 所示。

圖4 Griewank 測試函數的適應度變化

圖5 Sphere 測試函數的適應度變化

圖6 定位模型流程圖

3.2 實驗平臺的搭建與結果分析

3.2.1 采集系統的搭建與相關環節處理

本文選取東華大學二號學院樓7 m×7 m 的實驗室作為實驗環境，在該環境中每隔0.4 m×0.4 m 設置1 個數據采集點，共設置300 個數據采集點，另外分別在(0 m，0 m)、(7 m，7 m)、(7 m，0 m)、(0 m，7 m)和(3.5 m，3.5 m)坐標處各放置一部iPhone 6s 手機充當AP 節點，用于發射RSS 信號。 實驗室與AP 節點部署平面如圖7 所示。

為了進一步完善實驗條件，驗證KDMSPCS-GRNN的有效性，本文使用Python 開發一個簡易的RSS 信號采集系統，并將該系統封裝成終端可執行文件，然后在Dell 筆記本上運行該文件，執行RSS 信號采集功能，其中采集程序的交互式界面如圖8 所示。

圖8 顯示該系統主要有三個功能，功能一是掃描并在狀態欄中顯示定位點接收到WiFi 的RSS 信息;功能二是對單個定位點進行多次掃描，并將獲取的各WiFi 的RSS 信息導入底層數據庫;功能三是將底層數據庫里的數據導出并轉化成Excel 文件。而為了進一步驗證采集設備的實用性以及采集數據的準確性，在(2.8 m，2.8 m)的位置處分別對5 個AP 節點進行多次采集，在該點收到的各AP 節點的RSS 信號情況如圖9 所示。

從圖9 可以看出，在位置相同的條件下，同一個AP 節點的RSS 值具有一定的波動性。 而造成RSS 波動的原因除了精準采集設備的匱乏、高性能環境搭建所需人力的不足以及無線傳輸信道自帶的時變特性等因素，主要還受到定位環境內人員走動、多徑傳播以及噪聲干擾因素的影響。 故而為了保證采集到RSS 信號值的有效性，最大限度減少外在因素的影響，本文采用高斯濾波，先對數據做一定的濾波處理，然后再將每個采集點獲取的有效樣本數據存放入樣本庫中。 因為本文主要是針對定位算法的討論，至于模型搭建過程中詳細數據處理不是本文研討的重點，故而在此不做過多的贅述，而在下文所進行的多種模型定位效果對比實驗中，所需要的數據都是使用前文的搭建采集系統在同種條件下采集的數據。

3.2.2 定位模型效果對比

為了評估本文提出的定位模型的定位效果，隨機從300 個樣本中抽取250 個樣本用于訓練，剩余50 個樣本用于測試。 然后與GRNN 預測模型和BP預測模型的結果進行比較。 圖10 描述了三種定位模型在訓練次數相同的情況下，各個定位模型預測值與真實值在不同測試點的相對誤差。

圖7 實驗室AP 節點部署平面圖

圖8 采集程序的交互式界面

圖9 各AP 點RSS 信號波動圖

圖10 不同預測模型各點的相對誤差

從圖10 的結果可以看出相比于PSO-GRNN 定位模型和PSO-BP 定位模型，本文構建的定位模型在預測結果上更接近于真實值，具有更好的擬合效果。 而且為了更清晰地對比不同定位模型的預測效果，本文對測試集內各測試點的預測誤差做進一步的數值處理，獲得所有點的平均預測誤差和均方根預測誤差，并設定2 m 的有效預測界限，計算各模型的定位準確度。 依據均方根誤差函數和平方根誤差函數的特性可知，均方誤差值越低，定位準確率越高，則模型的定位效果越好。 三種定位模型測試結果如表3 所示，其中均方根誤差(RMSE)和平均相對誤差(ARE)計算方法如式(22)和式(23)所示：

其中?i表示測試點的真實值，βi表示測試點的預測值，N表示測試點的個數。

表3 定位模型預測的對比結果

通過表3 可以看出， 本文提出的定位模型與PSO-GRNN 定位模型和PSO-BP 定位模型相比，其在訓練誤差上具有一定的優勢，而且在預測準確性和穩定性方面也明顯優于GRNN 定位模型和BP 定位模型，具有更好的定位效果。

4 結論

本文基于動態分群策略，結合LDCPSO 算法和CS算法各自的優勢，構造了KDMSPCS 算法，并利用此算法為GRNN 選擇最優參數，構建定位預測模型。通過實驗得出，相比于其他智能算法，KDMSPCS 算法具有更好的收斂速度和收斂精度。相比于其他定位模型，利用該算法搭建的定位模型也具有更好的定位效果。 但因為實驗條件有限，實際環境較為復雜，故而該定位模型的大范圍推廣還需具體考證。后續將通過擴大實驗區域， 納入更多的環境多變因素，改善RSS 信號的獲取方法等方式來提高RSS 信號的真實有效性，繼而再進一步提高定位模型的預測精度和預測效率，同時提高算法模型的推廣能力。