基于LS-SVR的混合定位算法

夏 斌，梁春燕，袁文浩，謝 楠

(山東理工大學 計算機科學與技術學院，山東 淄博 255000)

0 引 言

準確地獲取節點的位置信息是物聯網應用中的基本要求。例如，智能機器人[1,2]、交通運輸[3,4]等應用均需節點的位置信息。因此，精確定位的研究對物聯網的位置服務應用至關重要。機器學習是利用經驗來改善自身性能的一種學習方法，而最小二乘支持向量回歸[5,6](least-square support vector regression，LS-SVR)作為機器學習中的一種模式，在解決小樣本、非線性及高維模式識別等方面有著其特有的優勢?；贚S-SVR的節點定位算法利用機器學習算法的特性，實現物聯網節點定位，成為近年來一個研究熱點。

文獻[7]提出了基于測距的支持向量回歸定位算法，采用一對一決策準則。文獻[8]采用粒子群優化算法對最小二乘支持向量回歸參數進行優化；文獻[9]采用人工蜂群算法解決支持向量回歸的參數選擇問題；文獻[10]提出了利用差分進化算法進行優化的LS-SVR算法等。通過不同算法與LS-SVR相結合，在定位精度方面有所改進，但沒有考慮在定位過程中，未知節點之間的距離信息對定位的有效修正作用，導致得到的定位精度并不高。文獻[11,12]利用未知節點間的距離信息，對傳統的Taylor定位模型進行了改進。改進后的多元Taylor定位模型在定位精度上有所提高，但是算法的精度嚴重依賴初始值。鑒于此，本文提出了一種混合定位算法，充分發揮多元Taylor級數展開法和LS-SVR算法的優點，實現定位性能的整體最優化。

1 LS-SVR算法

LS-SVR算法的主要思想是將優化目標中松弛變量的一次懲罰項，轉變成二次約束條件，從而將二次規劃問題簡化為較易計算的線性方程組問題，提高了計算效率。其具體步驟如下：

步驟1 設已知訓練樣本集T={(u1,v1),…,(uM,vM)}，其中um為輸入向量，vm是輸出變量(m=1,2,…,M)；

步驟2 選擇核函數K(um,un)及適當的正則化參數γ(γ>0)；

步驟3 構造并求最優化問題

(1)

s.t.vm=wTφ(um)+b+ζm

(2)

其中，αm∈R。分別求L(w,b,ζ,α)對w,b,ζ,α偏微分，根據最優化條件可以得到如下線性方程

(3)

進而求出α,b解析表達式

(4)

步驟4 構造決策函數

(5)

2 基于LS-SVR的混合定位算法

傳統的LS-SVR定位算法未考慮未知節點之間的距離信息在定位過程中的有效修正作用，導致定位信息不夠全面，定位精度不高。因此，提出了一種基于LS-SVR的混合算法，充分利用未知節點之間的距離信息，提高定位精度。首先利用LS-SVR算法求得未知節點的初始位置，其次對構建的多元Taylor定位模型進行精確求解。具體步驟如下：

步驟1 用t×t的方格對定位區域進行網格化，得到不同的網格節點，根據網格節點的坐標以及它到錨節點的實際距離組成的距離向量，構建訓練樣本集。

步驟2 由于徑向基(radial basis function，RBF)核函數在大樣本、小樣本、高維度、低維度等情況下，都能帶來比較好的回歸效果。并且此核函數具有較寬的收斂域，唯一最佳逼近的特性，同時在學習和訓練樣本過程中有較快的收斂速度。因此，我們選取RBF核函數。

步驟3 選擇適當的正則化參數γ和RBF的核參數σ′2，利用LS-SVR算法對訓練樣本集進行學習，得到定位回歸模型。

步驟4 將測量得到的未知節點到錨節點之間的距離數據輸入已經建立好的定位回歸模型，通過計算得到未知節點的初始值。

(6)

步驟6 利用加權最小二乘法可求解出節點位置偏差為

(7)

(8)

混合算法的流程如圖1所示。

圖1 混合定位算法的流程

3 仿真結果和分析

3.1 測距誤差對定位誤差的影響

LS-SVR算法和混合算法的定位誤差隨測距誤差的方差變化如圖2所示。從圖中可得，隨著測距誤差方差的增加，這兩種算法的定位誤差也都增加，但是混合算法的定位誤差卻明顯小于LS-SVR定位算法。這是因為多元Taylor模型在定位過程中多考慮了未知節點間的距離信息，使混合算法的定位精度相對于LS-SVR算法有明顯提高。

表1 仿真參數

圖2 測距誤差對定位誤差的影響(γ=15，σ′2=5)

3.2 定位誤差的累積分布函數

如圖3和圖4所示，橫坐標表示定位誤差，縱坐標表示當前定位誤差對應的累積分布函數。從圖3可以看出，在90%的累積分布點，傳統算法的定位誤差在1.8 m以內，而混合算法的定位精度在0.5 m以內，混合算法的定位精度相比于傳統算法得到進一步提高。

圖3 σ2為0.5時，累積分布函數(K=4，γ=15，σ′2=5)

圖4 σ2為1時，累積分布函數(K=4，γ=15，σ′2=5)

3.3 核參數的選取對定位誤差的影響

圖5給出了核參數對定位誤差影響的曲線。當正則化參數γ一定時，增加核參數，LS-SVR定位誤差顯著降低，當增加到一定值時，定位誤差趨于穩定。當σ′2<5時，核參數的選取影響LS-SVR定位算法的精度，而對混合算法精度的影響較小。這說明混合算法采用的多元Taylor級數展開模型充分利用未知節點之間的距離信息，減少了核參數對定位誤差的影響。

圖5 核參數對定位誤差影響的曲線(K=4)

3.4 正則化參數的選取對定位誤差的影響

圖6給出了正則化參數對定位誤差影響的曲線圖。從圖可以看出正則化參數γ的選取明顯影響LS-SVR定位算法的精度，而對混合算法精度的影響較小，說明混合定位算法能減少正則化參數對定位誤差的影響。

圖6 正則化參數對定位誤差影響的曲線(K=4)

4 結束語

物聯網精確定位具有巨大的社會價值和商業價值，對基于位置服務的實現、提高人們生活質量有重要的基礎支撐與保障作用。在傳統LS-SVR算法基礎上，通過多元Taylor級數展開法，充分利用未知節點之間的距離信息，實現未知節點位置的最優。仿真結果表明：混合定位算法在測距誤差、核參數、正則化參數等評價定位性能方面，均優于傳統LS-SVR定位算法。