基于向量相似性的多維標(biāo)度定位算法

鄭 天，馮秀芳

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

0 引 言

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

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

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

1 VSE-MDS算法

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

首先，引入測(cè)量信號(hào)向量相似性指標(biāo)cosine，它在一定程度上可以衡量?jī)蓚€(gè)向量間的相似程度。將兩測(cè)量信號(hào)向量的cosine作為基準(zhǔn)，可以有效利用向量特征為節(jié)點(diǎn)的相對(duì)位置關(guān)系提供度量標(biāo)準(zhǔn)。

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

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

表1 VSE-MDS算法主要框架

1.1 向量相似性指標(biāo)

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

定義1 信號(hào)向量相似性指標(biāo)cosine。對(duì)于向量x，序列y與其的相似度為

(1)

式中：cosine的取值范圍為[0,1]。向量間的相似度越高cosine取值越大，當(dāng)兩個(gè)向量完全一致時(shí)cosine取值為1。

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

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

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

構(gòu)建相關(guān)性修正模型，假設(shè)rx=(rx(1),rx(2),…,rx(n))，ry=(ry(1),ry(2),…,ry(n)) 是兩個(gè)n維向量。輸入重構(gòu)維度m， 考慮到目標(biāo)節(jié)點(diǎn)的分布環(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)性指標(biāo)cosine記為f，對(duì)任意i≤n-m有

(2)

于是可以定義

(3)

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

(4)

并且得到

(5)

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

(6)

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

1.3 節(jié)點(diǎn)位置計(jì)算

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

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

(7)

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

(8)

JN+1為中心矩陣。我們假設(shè)距離沒(méi)有誤差，則可以將矩陣轉(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] 是一個(gè)標(biāo)準(zhǔn)正交矩陣，其列向量是對(duì)應(yīng)的特征向量。在沒(méi)有誤差的情況下，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 仿真實(shí)驗(yàn)及分析

為驗(yàn)證VSE-MDS算法的性能，在MATLAB R2016a中進(jìn)行仿真實(shí)驗(yàn)。實(shí)驗(yàn)的目標(biāo)區(qū)域?yàn)?0m*10m的方形區(qū)域，在區(qū)域內(nèi)隨機(jī)部署10個(gè)無(wú)線傳感器發(fā)射節(jié)點(diǎn)，其中9個(gè)為發(fā)射節(jié)點(diǎn)，1個(gè)為待測(cè)節(jié)點(diǎn)，對(duì)待測(cè)節(jié)點(diǎn)位置進(jìn)行測(cè)量。

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

本文使用歸一化的誤差分析模型對(duì)算法的性能進(jìn)行評(píng)估

(13)

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

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

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

對(duì)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。從平均定位精度可以看出無(wú)論是在理想傳播模型的環(huán)境下還是在非理想傳播模型的環(huán)境下，基于VSE-MDS的室內(nèi)定位方法相較于RSSI-MDS都擁有更加準(zhǔn)確的定位精度。

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

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

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

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

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

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

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

圖4 實(shí)際測(cè)量平均誤差及方差

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

3 結(jié)束語(yǔ)

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