鄭 天，馮秀芳

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

0 引 言

定位方法的研究目標是圍繞降低定位服務成本、提高室內定位精度、適應復雜多變的室內環(huán)境等[1]?；赪LAN的室內定位方法主要有兩種：參數化室內定位方法和非參數化室內定位方法[2]。

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

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

1 VSE-MDS算法

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

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

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

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

表1 VSE-MDS算法主要框架

1.1 向量相似性指標

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

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

(1)

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

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

1.2 相關性修正模型

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

構建相關性修正模型，假設rx=(rx(1),rx(2),…,rx(n))，ry=(ry(1),ry(2),…,ry(n)) 是兩個n維向量。輸入重構維度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引入相關性指標cosine記為f，對任意i≤n-m有

(2)

于是可以定義

(3)

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

(4)

并且得到

(5)

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

(6)

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

1.3 節(jié)點位置計算

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

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

(7)

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

(8)

JN+1為中心矩陣。我們假設距離沒有誤差，則可以將矩陣轉換為

B=XXT

(9)

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

B=VΛVT

(10)

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

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

(11)

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

(12)

2 仿真實驗及分析

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

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

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

(13)

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

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

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

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

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

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

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

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

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

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

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

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

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

3 結束語

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