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

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

(山東理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山東 淄博 255000)

0 引 言

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

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

1 LS-SVR算法

LS-SVR算法的主要思想是將優(yōu)化目標(biāo)中松弛變量的一次懲罰項(xiàng)，轉(zhuǎn)變成二次約束條件，從而將二次規(guī)劃問題簡化為較易計(jì)算的線性方程組問題，提高了計(jì)算效率。其具體步驟如下：

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

步驟2 選擇核函數(shù)K(um,un)及適當(dāng)?shù)恼齽t化參數(shù)γ(γ>0)；

步驟3 構(gòu)造并求最優(yōu)化問題

(1)

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

(2)

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

(3)

進(jìn)而求出α,b解析表達(dá)式

(4)

步驟4 構(gòu)造決策函數(shù)

(5)

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

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

步驟1 用t×t的方格對定位區(qū)域進(jìn)行網(wǎng)格化，得到不同的網(wǎng)格節(jié)點(diǎn)，根據(jù)網(wǎng)格節(jié)點(diǎn)的坐標(biāo)以及它到錨節(jié)點(diǎn)的實(shí)際距離組成的距離向量，構(gòu)建訓(xùn)練樣本集。

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

步驟3 選擇適當(dāng)?shù)恼齽t化參數(shù)γ和RBF的核參數(shù)σ′2，利用LS-SVR算法對訓(xùn)練樣本集進(jìn)行學(xué)習(xí)，得到定位回歸模型。

步驟4 將測量得到的未知節(jié)點(diǎn)到錨節(jié)點(diǎn)之間的距離數(shù)據(jù)輸入已經(jīng)建立好的定位回歸模型，通過計(jì)算得到未知節(jié)點(diǎn)的初始值。

(6)

步驟6 利用加權(quán)最小二乘法可求解出節(jié)點(diǎn)位置偏差為

(7)

(8)

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

圖1 混合定位算法的流程

3 仿真結(jié)果和分析

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

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

表1 仿真參數(shù)

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

3.2 定位誤差的累積分布函數(shù)

如圖3和圖4所示，橫坐標(biāo)表示定位誤差，縱坐標(biāo)表示當(dāng)前定位誤差對應(yīng)的累積分布函數(shù)。從圖3可以看出，在90%的累積分布點(diǎn)，傳統(tǒng)算法的定位誤差在1.8 m以內(nèi)，而混合算法的定位精度在0.5 m以內(nèi)，混合算法的定位精度相比于傳統(tǒng)算法得到進(jìn)一步提高。

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

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

3.3 核參數(shù)的選取對定位誤差的影響

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

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

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

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

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

4 結(jié)束語

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