基于向量相似性的多維標度定位算法

鄭 天，馮秀芳

(1.太原理工大學(xué) 信息與計算機學(xué)院，山西 晉中 030600；2.太原理工大學(xué) 軟件學(xué)院，山西 晉中 030600)

0 引 言

定位方法的研究目標是圍繞降低定位服務(wù)成本、提高室內(nèi)定位精度、適應(yīng)復(fù)雜多變的室內(nèi)環(huán)境等[1]。基于WLAN的室內(nèi)定位方法主要有兩種：參數(shù)化室內(nèi)定位方法和非參數(shù)化室內(nèi)定位方法[2]。

在參數(shù)化室內(nèi)定位方法中，多維標度(multidimensional scaling, MDS)算法采用目標間的歐幾里得距離作為相似性度量，當給定目標間的歐式距離之后，算法可以確定低維空間的相對位置。其中，石欣等將信號強度指示作為目標間的度量值構(gòu)建相異性矩陣[3]。一些系統(tǒng)將多維標度算法與指紋定位相結(jié)合[4,5]，在離線階段降低了指紋信息采集的開銷，減少了所需參考點的個數(shù)。Parviainen M等在一種動態(tài)聲學(xué)自定位系統(tǒng)中使用多維標度算法來映射節(jié)點位置[6]。一部分學(xué)者對多維標度算法進行了修正，縮小了最短路徑與歐式距離的差異值，優(yōu)化了節(jié)點間相關(guān)性關(guān)系并提高了定位精度[7-10]。

本文提出一種基于向量相似性的多維標度定位算法。該算法在構(gòu)建相關(guān)性矩陣方面進行改進，以解決復(fù)雜環(huán)境對無線信號影響導(dǎo)致的定位精度較低的問題。該研究主要包含兩個方面：①以節(jié)點采集到的各發(fā)射節(jié)點的無線信號強度指示構(gòu)建信號向量，以向量間相似性作為度量節(jié)點間距離的度量標準；②使用相關(guān)性修正模型對向量間相似度進行修正完善，進而提高定位精度。

1 VSE-MDS算法

本文提出了一種基于向量相似性的多維標度定位方法，引入測量信號參數(shù)向量間的相似度作為節(jié)點距離的度量標準，在一定程度上打破了傳統(tǒng)基于測量信號參數(shù)方法的局限性，可以適應(yīng)復(fù)雜環(huán)境下的實時定位。

首先，引入測量信號向量相似性指標cosine，它在一定程度上可以衡量兩個向量間的相似程度。將兩測量信號向量的cosine作為基準，可以有效利用向量特征為節(jié)點的相對位置關(guān)系提供度量標準。

其次，提出了基于樣本熵的相關(guān)性修正模型，在使用多維標度算法進行定位前，先利用模型對基準環(huán)境下的所有測量信號向量的相似度進行修正，然后利用多維標度算法對修正后的相關(guān)性矩陣進行降維，得到目標節(jié)點的相對位置坐標。

VSE-MDS(vector sample entropy multidimensional scaling)算法是一種利用測量信號向量間的相似關(guān)系來表征目標節(jié)點間距離遠近關(guān)系的多維標度定位算法，并通過樣本熵構(gòu)建相關(guān)性修正模型達到進一步優(yōu)化節(jié)點相關(guān)性的目的。VES-MDS算法的算法框架見表1。

表1 VSE-MDS算法主要框架

1.1 向量相似性指標

以各目標節(jié)點RSSI構(gòu)建測量信號向量矩陣R，矩陣中的每一行是每一個目標節(jié)點的n維RSSI向量，考慮到向量特征，本文引入測量信號向量相似性指標cosine，定義如下：

定義1 信號向量相似性指標cosine。對于向量x，序列y與其的相似度為

(1)

式中：cosine的取值范圍為[0,1]。向量間的相似度越高cosine取值越大，當兩個向量完全一致時cosine取值為1。

在實驗中發(fā)現(xiàn)，使用向量相似性指標對向量間相似度進行表征時，由于cosine是針對兩向量整體相似性進行表征，存在向量相似性表征不準確的情況。針對這種情況，提出了一種基于樣本熵的相關(guān)性修正模型。

1.2 相關(guān)性修正模型

樣本熵(sample entropy，SE)是一種用于比較兩個不同時間序列相關(guān)性程度的算法[11]。樣本熵決定了向量中有多少分向量出現(xiàn)在統(tǒng)計上顯著的范圍內(nèi)。當一對向量比另一對向量更相似時，對于所測試的所有條件，它應(yīng)該具有更低的樣本熵?？梢钥闯?，樣本熵將向量從一個整體拆分為多個小的向量分量并計算各分向量對的cosine指標，通過統(tǒng)計在規(guī)定范圍內(nèi)的cosine指標數(shù)量來進一步反應(yīng)向量間的相似程度求得向量樣本熵(vector sample entropy，VSE)，進而達到對向量間相關(guān)性進行修正優(yōu)化的目的。

構(gòu)建相關(guān)性修正模型，假設(shè)rx=(rx(1),rx(2),…,rx(n))，ry=(ry(1),ry(2),…,ry(n)) 是兩個n維向量。輸入重構(gòu)維度m， 考慮到目標節(jié)點的分布環(huán)境m一般取值為2或3。修正后的向量為：xm(i)=(rx(i),rx(i+1),…,rx(i+m-1)),1≤i≤n-m，ym(i)=(ry(i),ry(i+1),…,ry(i+m-1)),1≤i≤n-m引入相關(guān)性指標cosine記為f，對任意i≤n-m有

(2)

于是可以定義

(3)

令向量重構(gòu)維度變?yōu)閙+1，于是可以定義

(4)

并且得到

(5)

令1≤x≤n,1≤y≤n， 可以定義各節(jié)點向量間的樣本熵為

(6)

通過基于樣本熵的相關(guān)性修正模型對測量信號向量間相似度進行修正，得到各目標節(jié)點間測量信號向量樣本熵。以各節(jié)點間的向量樣本熵構(gòu)成多維標度算法中的相關(guān)性矩陣，通過多維標度法對相關(guān)性矩陣進行降維得到節(jié)點間的相對位置坐標。

1.3 節(jié)點位置計算

根據(jù)前一節(jié)的結(jié)果，基于所獲取到的各節(jié)點之間的相似性關(guān)系，我們可以利用多維標度[12]算法來計算待測節(jié)點與各發(fā)射節(jié)點之間的相對位置，最后通過坐標轉(zhuǎn)換的方式，以發(fā)射節(jié)點的實際物理位置計算出待測節(jié)點的位置。

以各節(jié)點間的向量樣本熵構(gòu)建矩陣，用V表示，矩陣如下

(7)

使用雙重中心化的方法得到內(nèi)積矩陣，其形式如下

(8)

JN+1為中心矩陣。我們假設(shè)距離沒有誤差，則可以將矩陣轉(zhuǎn)換為

B=XXT

(9)

其中，X=[x1,x2,x3,…,xN]， 用特征值因式分解法可將B分解為

B=VΛVT

(10)

其中， Λ=diag(λ1,λ2,…,λN+1) 是B的特征矩陣，V=[v1,v2,…,vN+1] 是一個標準正交矩陣，其列向量是對應(yīng)的特征向量。在沒有誤差的情況下，B的秩為2，B可以轉(zhuǎn)變?yōu)橐韵滦问?/p>

B=(V2Ω)Λ2(V2Ω)T

(11)

其中， Λ2=diag(λ1,λ2)，V2=[v1,v2]， Ω為正交矩陣。根據(jù)式(9)和式(11)我們可以得到主軸解

(12)

2 仿真實驗及分析

為驗證VSE-MDS算法的性能，在MATLAB R2016a中進行仿真實驗。實驗的目標區(qū)域為10m*10m的方形區(qū)域，在區(qū)域內(nèi)隨機部署10個無線傳感器發(fā)射節(jié)點，其中9個為發(fā)射節(jié)點，1個為待測節(jié)點，對待測節(jié)點位置進行測量。

本文與傳統(tǒng)基于RSSI的多維標度算法進行了對比，驗證了算法的改進效果。同時為了驗證算法的定位精度，選用Regular Model以及Logarithmic Attenuation Model分別模擬理想傳播空間以及非理想傳播空間下的無線信號傳播方式對算法進行了驗證[13]。

本文使用歸一化的誤差分析模型對算法的性能進行評估

(13)

為考量VSE-MDS算法在不同傳播空間下的定位性能，分別在理想和非理想兩種不同的傳播空間下，分別對基于RSSI的多維標度算法和VSE-MDS算法進行了10次連續(xù)測量，連續(xù)10次定位結(jié)果見表2、表3。

表2 理想傳播模型環(huán)境下定位10次結(jié)果

表3 非理想傳播模型環(huán)境下定位10次結(jié)果

對10次定位結(jié)果求平均值，我們可以得出在理想傳播型的環(huán)境下，基于RSSI-MDS的室內(nèi)定位方法的平均定位精度為3.04 m，基于VSE-MDS的室內(nèi)定位方法的平均定位精度為2.28 m。在非理想傳播模型的環(huán)境下，基于RSSI-MDS的室內(nèi)定位方法的平均定位精度為3.69 m，基于VSE-MDS的室內(nèi)定位方法的平均定位精度為2.41 m。從平均定位精度可以看出無論是在理想傳播模型的環(huán)境下還是在非理想傳播模型的環(huán)境下，基于VSE-MDS的室內(nèi)定位方法相較于RSSI-MDS都擁有更加準確的定位精度。

為驗證兩個算法受環(huán)境因素影響的程度，對VSE-MDS算法以及RSSI-MDS算法在不同環(huán)境下的10次定位結(jié)果進行比對分析，分析結(jié)果如圖1、圖2所示。

圖1 Regular Model環(huán)境下定位精度

圖2 Logarithmic Attenuation Model環(huán)境下定位精度

基于VSE-MDS的室內(nèi)定位方法在多次測量中，定位結(jié)果較為一致，同時對比在理想傳播模型環(huán)境下的定位結(jié)果和在非理想傳播模型環(huán)境下的平均定位精度，基于VSE-MDS的室內(nèi)定位方法不因環(huán)境的變化而產(chǎn)生較大的誤差波動。反觀基于RSSI-MDS的室內(nèi)定位方法在多次測量中，定位誤差波動較大，同時在環(huán)境發(fā)生變化后，算法誤差產(chǎn)生了較大的變化。因此可以得出基于VSE-MDS的室內(nèi)定位方法在擁有較高定位精度的前提下，受環(huán)境因素影響較小。

為進一步驗證算法在實際情況下的實用性，使用4臺HUAWEI-WS5200路由器作為AP發(fā)射端，一臺筆記本電腦作為接收端，實驗在8m*10m的環(huán)境較為復(fù)雜的實驗室內(nèi)進行，在室內(nèi)各處皆擺放了桌椅。在室內(nèi)環(huán)境中，隨機取10個任意位置作為待測點進行實驗。室內(nèi)環(huán)境如圖3所示。

圖3 室內(nèi)環(huán)境布局

在實際隨機選取的位置分別連續(xù)進行10次測量，并使用VSE-MDS算法對目標節(jié)點進行定位，對定位誤差進行統(tǒng)計分析的結(jié)果如圖4所示。

圖4 實際測量平均誤差及方差

在圖4中柱形圖表示節(jié)點定位的平均誤差，折線圖表示節(jié)點定位誤差的方差。根據(jù)對各位置定位誤差的方差分析可以得出，VSE-MDS算法在同一位置的不同時間段內(nèi)的定位誤差的方差為0.05左右，驗證定位誤差的波動較小。通過對不同位置的平均定位誤差的對比分析可以得出，VSE-MDS算法在不同位置上的定位誤差在2.5 m左右，各位置的定位誤差較為一致。因此可以得出VSE-MDS算法在實際情況下受復(fù)雜環(huán)境的影響較小。

3 結(jié)束語

提出了一種基于向量相關(guān)性的多維標度定位算法VSE-MDS。研究了傳統(tǒng)基于RSSI的多維標度的室內(nèi)定位方法，在傳統(tǒng)方法中使用RSSI值構(gòu)建相異性矩陣會導(dǎo)致定位精度不高、受環(huán)境因素影響較大。仿真實驗結(jié)果表明，基于VSE-MDS的室內(nèi)定位算法解決了多維標度算法中相關(guān)性矩陣優(yōu)化的問題，同時降低了環(huán)境因素對定位結(jié)果的影響程度。進一步優(yōu)化算法定位精度，并將算法引入到移動節(jié)點定位中，將是下一步的研究方向。