李麗娜，李文浩,2，尤洪祥，王 越

(1.遼寧大學(xué) 物理學(xué)院，沈陽 110036； 2. 中國船舶重工集團(tuán)公司第七一五研究所，杭州 310023) (*通信作者電子郵箱lilina73@163.com)

回溯搜索優(yōu)化改進(jìn)矩陣填充的高效位置指紋庫構(gòu)建

李麗娜1*，李文浩1,2，尤洪祥1，王 越1

(1.遼寧大學(xué) 物理學(xué)院，沈陽 110036； 2. 中國船舶重工集團(tuán)公司第七一五研究所，杭州 310023) (*通信作者電子郵箱lilina73@163.com)

針對基于信號強(qiáng)度指示(RSSI)的位置指紋定位過程中用于其離線位置指紋庫構(gòu)建的全采法采集工作量較大、位置指紋庫構(gòu)建效率較低、而插值法通常精度有限等問題，提出一種基于回溯搜索優(yōu)化算法改進(jìn)奇異值閾值(SVT)矩陣填充(MC)算法的離線位置指紋庫高效構(gòu)建方法。首先，利用定位區(qū)域內(nèi)采集到的部分參考點的位置指紋數(shù)據(jù)建立低秩矩陣填充模型；然后通過基于奇異值閾值的低秩矩陣填充算法來求解該模型，進(jìn)而快速準(zhǔn)確重構(gòu)出完整的位置指紋數(shù)據(jù)庫；同時，針對傳統(tǒng)矩陣填充算法最優(yōu)解模糊及平滑性欠佳的問題，引入回溯搜索優(yōu)化算法，以核范數(shù)最小建立適應(yīng)度函數(shù)，對矩陣填充算法的尋優(yōu)過程進(jìn)行改進(jìn)，進(jìn)一步提高了求解精度。實驗結(jié)果表明，利用所提方法構(gòu)建的位置指紋庫與實際采集的位置指紋庫之間的平均誤差僅為2.705 4 dB，平均定位誤差僅相差0.086 3 m，但卻節(jié)約了近50%的離線采集工作量。上述結(jié)果表明所提算法用于離線位置指紋庫構(gòu)建可以在保證精度的基礎(chǔ)上，有效降低離線采集階段的工作量，顯著提高位置指紋庫構(gòu)建效率，在一定程度上提高位置指紋定位方法的實用性。

矩陣填充；奇異值閾值；回溯搜索優(yōu)化算法；位置指紋數(shù)據(jù)庫；室內(nèi)定位

0 引言

隨著物聯(lián)網(wǎng)技術(shù)的蓬勃發(fā)展及日益普及，作為室外全球定位系統(tǒng)(Global Positioning System， GPS)的有力補(bǔ)充，室內(nèi)定位技術(shù)的相關(guān)研究近年來備受關(guān)注。其中，基于接收信號強(qiáng)度指示(Received Signal Strength Indication， RSSI)的位置指紋定位方法因其定位精度高、受室內(nèi)多徑效應(yīng)與環(huán)境噪聲影響小而成為無線室內(nèi)定位技術(shù)中的主流方法，得到了越來越廣泛的應(yīng)用。位置指紋定位法包括離線位置指紋數(shù)據(jù)庫構(gòu)建與在線位置指紋匹配定位兩個階段，而根據(jù)定位區(qū)域內(nèi)不同參考點處接收的無線信號強(qiáng)度值建立能準(zhǔn)確體現(xiàn)出各位置特征的位置指紋庫，是有效實現(xiàn)室內(nèi)定位的基礎(chǔ)[1-2]。

傳統(tǒng)位置指紋庫構(gòu)建方法主要有全采法和插值法。全采法需要針對同一個參考點進(jìn)行多次測量，取平均值，然后由每個樣本點采集得到的各個參考點(Reference Point， RP)的信號強(qiáng)度值直接建立位置指紋庫[3]。顯然，全采法離線采集工作量較大，尤其當(dāng)定位區(qū)域較大時，位置指紋信息的采集工作將變得非常繁瑣，位置指紋庫的構(gòu)建效率偏低，同時數(shù)據(jù)量大也將導(dǎo)致存儲及傳輸成本高，實用性較差；另外一種比較常用的位置指紋庫構(gòu)建方法是插值法[4]，其主要思路是預(yù)先采集部分參考點的信號強(qiáng)度值，然后利用此數(shù)據(jù)插值計算估計相鄰參考點之間的信號強(qiáng)度值，以此來構(gòu)建位置指紋庫。主要包括基于反距離加權(quán)(Inverse Distance Weighted， IDW)插值法和克里金(Kriging)插值法兩種。其中，IDW插值法計算簡單，但精度較低；而Kriging插值算法實現(xiàn)靈活，能提供誤差估計機(jī)制，精度相對較高，但其早期變差函數(shù)通常依據(jù)經(jīng)驗選取，往往不是最優(yōu)參數(shù)，將直接影響插值精度?？傊?，插值法可以大大減少離線采集工作量，位置指紋庫的建立過程相對快捷，但插值法計算精度受限，且通常不能充分利用全局信息，因此計算得到的位置指紋庫往往準(zhǔn)確度不夠，最終將直接影響定位精度。

鑒于以上分析，本文提出引入矩陣填充(Matrix Completion， MC)理論實現(xiàn)離線位置指紋庫的高效構(gòu)建方法，利用定位區(qū)域內(nèi)采集到的部分參考點的位置指紋信息，采用基于奇異值閾值(Singular Value Thresholding， SVT)低秩矩陣填充算法重構(gòu)出定位區(qū)域內(nèi)完整的位置指紋庫[5-7]。同時，針對標(biāo)準(zhǔn)矩陣填充算法SVT的最優(yōu)解模糊及平滑性欠佳的問題[8]，引入了回溯搜索優(yōu)化算法(Backtracking Search optimization Algorithm， BSA)，以核范數(shù)最小建立適應(yīng)度函數(shù)，利用回溯搜索優(yōu)化算法理想的全局搜索特性對矩陣填充算法的尋優(yōu)過程進(jìn)行了改進(jìn)，提出了新型的位置指紋庫構(gòu)建算法——BSA-SVT(Backtracking Search optimization Algorithm-Singular Value Thresholding)，在保證位置指紋庫重構(gòu)精度的基礎(chǔ)上，有效降低了離線采樣階段的工作量。

1 位置指紋構(gòu)建原理及算法描述

1.1 矩陣填充算法

矩陣填充是指在矩陣中元素不完整的情況下對矩陣中缺失的數(shù)據(jù)進(jìn)行填充，主要是利用原始數(shù)據(jù)矩陣的低秩性進(jìn)行矩陣的重建[9]。眾所周知，采用全采法來構(gòu)建位置指紋數(shù)據(jù)庫缺乏實用性，因此通常只采集定位區(qū)域內(nèi)部分位置指紋數(shù)據(jù)，即定位區(qū)域內(nèi)的RSSI矩陣是不完整的，考慮到位置指紋數(shù)據(jù)即RSSI值分布通常具有較強(qiáng)的空間和時間相關(guān)性，可以認(rèn)為定位區(qū)域內(nèi)的位置指紋數(shù)據(jù)矩陣是具有低秩特性的，因此可以通過采集到的部分位置指紋數(shù)據(jù)利用矩陣填充理論來重構(gòu)完整的位置指紋數(shù)據(jù)庫。

矩陣填充理論解決的問題是：如果已知一個未知矩陣的部分元素，設(shè)為m個元素，能否利用這m個元素組成的一個不完整矩陣完全恢復(fù)出這個未知矩陣。在利用矩陣填充理論解決實際問題時，由于未知矩陣是一個低秩矩陣或近似低秩的矩陣，所以可以通過解決一個優(yōu)化問題的方法來解決矩陣填充問題[10-11]，如式(1)：

min rank(X)

s.t.Xij=Mij,i,j∈Ω

(1)

其中：X表示矩陣，Xij表示矩陣X的第i行、第j列元素；M表示由m個元素組成的n1×n2的不完整矩陣，Mij表示矩陣M的第i行、第j列元素；Ω表示矩陣中被觀測到的元素的位置的集合。

由于式(1)表示的優(yōu)化問題是一個NP-hard問題，所以該優(yōu)化問題的求解可以轉(zhuǎn)化為一個凸優(yōu)化問題進(jìn)行[12-13]，如式(2)或式(3)所示：

min ‖X‖*

s.t.Xij=Mij,i,j∈Ω

(2)

(3)

由式(2)～(3)可知，矩陣填充求解問題的目的在于找到滿足PΩ(X)=PΩ(M)，且使得‖X‖*最小的X，如式(4)所示：

min ‖X‖*

s.t.PΩ(X)=PΩ(M),i,j∈Ω

(4)

其中，PΩ對于M矩陣而言，就是使得矩陣M在Ω外消失的正交投影，即：如果(i,j)∈Ω，則PΩ(M)的第(i,j)項等于Mij，其他項為零。式(4)進(jìn)一步可以等價為式(5)：

s.t.PΩ(X)=PΩ(M),i,j∈Ω

(5)

式(5)中：

(6)

τ=5n

(7)

n=max{n1,n2};M矩陣維數(shù)為n1·n2

(8)

為了解決式(5)這種優(yōu)化問題，Cai等[14]提出了奇異值閾值(SVT)算法，SVT算法是最早的也是最常用的解決矩陣填充問題的一種算法，是一種典型的Lagrange乘子算法。式(5)中，其Lagrangian函數(shù)如式(9)所示：

(9)

SVT算法基本步驟歸納如下：

輸入：樣本集合Ω和樣本項PΩ(M)，步長σ，參數(shù)τ，容差ε>0，增量l，迭代常數(shù)Kmax。

輸出：矩陣Xopt。

步驟1 初始化。設(shè)k0滿足式(10)，Y0的取值見式(11)：

(10)

Y0=k0σPΩ(M)

(11)

σ=1.2×n1·n2/m;M矩陣維數(shù)為n1·n2

(12)

參數(shù)τ的取值見式(7)，同時令k=1，h0=0，s1=1。

步驟2 奇異值分解(Singular Value Decomposition，SVD)。

①矩陣Yk通過奇異值分解可以轉(zhuǎn)化為3個矩陣乘積的形式：

Yk=UkΣk(Vk)T

(13)

步驟3 迭代。更新矩陣及其迭代條件，得到滿足條件的矩陣Xk。

(14)

(15)

(16)

令sk=hk-1+1，k=k+1，循環(huán)執(zhí)行步驟2～3，直到滿足迭代次數(shù)k=kmax時，迭代停止。

步驟4 輸出。返回矩陣Xopt=Xk。

1.2 回溯搜索優(yōu)化改進(jìn)的矩陣填充算法

將以上基于SVT的矩陣填充算法用于離線位置指紋庫的構(gòu)建，僅需采集定位區(qū)域內(nèi)部分參考點的位置指紋數(shù)據(jù)即可求解出完整的位置指紋庫，可極大節(jié)省工作時間及工作量、提高位置指紋庫構(gòu)建效率，但是無法準(zhǔn)確地判斷出每次執(zhí)行的結(jié)果是否是當(dāng)前的最優(yōu)解，同時重構(gòu)得到的位置指紋庫數(shù)據(jù)平滑性欠佳，將直接影響位置指紋定位的精度。

回溯搜索優(yōu)化算法(BSA)是Civicioglu[15]于2013年提出的一種基于種群的新型進(jìn)化算法。BSA的運算過程由6部分組成[16]：種群初始化、選擇Ⅰ、種群變異、種群交叉、選擇Ⅱ、輸出最優(yōu)解。本文引入BSA，利用其良好的快速收斂性和全局搜索性，用以指導(dǎo)SVT尋優(yōu)過程，提出了新型的BSA-SVT用于離線位置指紋庫的構(gòu)建，以便進(jìn)一步提升算法精度。

BSA-SVT的基本思想是：依據(jù)適應(yīng)度函數(shù)值來衡量每個個體的情況，并通過種群的交叉變異和選擇操作來更新種群，由此迭代得到最優(yōu)化問題的最優(yōu)解。BSA-SVT流程如圖1所示，具體算法步驟如下。

步驟1 初始化。初始化算法參數(shù)：種群規(guī)模NP、交叉概率mr、搜索空間范圍、最大進(jìn)化次數(shù)ep。初始化種群：歷史種群H的初始化根據(jù)式(17)選取，種群Q的初始化根據(jù)執(zhí)行SVT算法所得的填充結(jié)果Xopt選?。?/p>

Qi=Xopt，Hi,j～U(lowj,upj)

(17)

其中：i=1,2,…,NP，NP表示種群規(guī)模；j=1,2,…,D，D表示種群維數(shù)；low、up分別表示搜索空間范圍的下界和上界；U表示隨機(jī)均勻分布；此處Hi,j表示(lowj,upj)上服從均勻分布的隨機(jī)數(shù)。

步驟2 選擇Ⅰ。選擇Ⅰ的主要作用是選擇一個新的歷史種群。其基本思路如式(18)所示：

ifa

(18)

式(18)中a,b滿足a,b～U(0.1)。式(18)的作用是在前代種群中選擇并記住一個歷史種群，直到該歷史種群再次發(fā)生改變。

步驟3 種群變異。在歷史種群H確定之后，對歷史種群H中的個體隨機(jī)排序，然后又重新賦予H，這一過程稱為種群變異。變異如式(19)所示：

E=Q+F·(H-Q)

(19)

式(19)中，F(xiàn)表示尺度系數(shù)，作用是控制種群變異的幅度，大小為F=3·randn，randn～N(0,1)。

圖1 BSA-SVT流程

步驟4 種群交叉。BSA的種群交叉是一種通過交叉概率Ⅰ控制兩種交叉方式等概率調(diào)用的較為復(fù)雜的聯(lián)合交叉方法，種群交叉的目的是產(chǎn)生新一代的種群。BSA新一代種群T的個體的產(chǎn)生如式(20)：

(20)

式(20)中，Z是NP×D的整數(shù)矩陣，初始賦值取1，具體計算見式(21)：

(21)

式(21)中：randi(D)表示從[0,D]上隨機(jī)取的一個整數(shù)；mr表示交叉概率，取mr=1；rand滿足rand～U(0,1)的隨機(jī)數(shù)；a,b是滿足a,b～U(0,1)的隨機(jī)數(shù)。BSA通過[mr·rand·D]和randi(D)有效控制了新一代種群T中元素的個數(shù)。

特別注意的是，在新一代種群產(chǎn)生后，種群中的元素有可能超出搜索邊界的范圍，如果含有此類元素，則返回步驟1重新執(zhí)行SVT算法產(chǎn)生新的種群，最終生成新一代種群T。

步驟5 選擇Ⅱ。選擇新一代種群T和種群Q中同位置適應(yīng)度(fitness)函數(shù)值較好的個體Ti作為當(dāng)前的最優(yōu)解，否則更新初始種群，返回步驟2完成一次迭代。如式(22)所示：

(22)

由式(4)可知，矩陣填充解決的是求解一個最小核范數(shù)問題，因此設(shè)式(23)為適應(yīng)度函數(shù)：

(23)

其中：PΩ(M)表示樣本項，Pi表示Ti和Qi的統(tǒng)稱。

步驟6 輸出最優(yōu)解。輸出當(dāng)前的最優(yōu)解Ti，繼續(xù)執(zhí)行程序，直到達(dá)到最大進(jìn)化次數(shù)ep停止，選擇輸出結(jié)果中適應(yīng)度函數(shù)值最小的個體作為執(zhí)行一次BSA-SVT算法的最優(yōu)解。

2 仿真研究

為了驗證本文算法的可行性，在Matlab 7.0軟件中進(jìn)行了位置指紋庫構(gòu)建仿真實驗，實驗所采用的計算機(jī)配置為：Intel Core i5雙核CPU,主頻3.20 GHz，內(nèi)存8 GB。

仿真場景為一個19 m×9 m的室內(nèi)區(qū)域，區(qū)域內(nèi)布置有50個參考標(biāo)簽，采用10×5布局，均勻分布在定位區(qū)域內(nèi)，1個閱讀器。仿真實驗的布局如圖2所示。

根據(jù)無線信號在室內(nèi)傳播的規(guī)律，即無線信號傳播損耗模型公式，如式(24)所示，計算各參考標(biāo)簽處的信號強(qiáng)度得到原始位置指紋數(shù)據(jù)庫，數(shù)據(jù)如表1所示，各單元格對應(yīng)參考點網(wǎng)格。

(24)

下面將利用拉丁超立方抽樣(Latin Hypercube Sampling， LHS)算法[17]取表1中部分參考點的強(qiáng)度值為已知，其余置零，作為待填充的不完整位置指紋庫矩陣，利用矩陣填充算法進(jìn)行位置指紋庫構(gòu)建仿真實驗，并與常見的兩種插值算法反距離加權(quán)(IDW)插值法和克里金(Kriging)插值法求解結(jié)果進(jìn)行了誤差對比分析。仿真實驗中，BSA-SVT參數(shù)選取如下：問題維數(shù)D為10，種群規(guī)模NP為5，交叉概率mr取1，搜索空間范圍[low,up]設(shè)定為low=zeros(1,D),up=120·ones(1,D)，其中zeros函數(shù)用來按指定維數(shù)生成零矩陣，ones函數(shù)用來按指定維數(shù)生成全1矩陣，最大進(jìn)化次數(shù)ep取2 500。

考慮到已知參考點強(qiáng)度值的占比會對求解結(jié)果產(chǎn)生較大的影響，因此，在位置指紋庫構(gòu)建仿真實驗中對不同占比情況分別進(jìn)行了仿真分析，分別計算了已知參考點強(qiáng)度值在不同占比取值情況下各種算法求解獲得的位置指紋庫的平均誤差值，如表2所示。

圖2 仿真實驗布局

表1原始位置指紋庫的RSSI dB

Tab. 1 RSSI of original location fingerprint database dB

表2 已知參考點不同占比下各種算法的位置指紋庫誤差 dB

對表2數(shù)據(jù)分析可知，在已知參考點強(qiáng)度值占比較小如低于40%的情況下誤差較大，當(dāng)占比大于60%時，占比加大對于精度提高的貢獻(xiàn)已很微小，考慮在保證重構(gòu)精度的基礎(chǔ)上盡可能減輕人工采集數(shù)據(jù)的勞動量，一般盡可能保證信號強(qiáng)度誤差在2 dB以內(nèi)。通過分析可知，已知參考點強(qiáng)度值占比取值在50%～60%是最合理區(qū)間。

為更直觀地展示求解結(jié)果，給出了已知參考點強(qiáng)度值的占比為55%時的位置指紋庫構(gòu)建結(jié)果，即取表1中55%的強(qiáng)度值為已知，其余置零，作為待填充的不完整位置指紋庫，如表3所示。執(zhí)行BSA-SVT矩陣填充算法計算得到的位置指紋庫結(jié)果如表4所示。計算BSA-SVT、SVT位置指紋庫求解結(jié)果的平均誤差值(單位為dB)，分別用P_BSA-SVT、P_SVT表示。其中：P_BSA-SVT=1.743 1 dB，P_SVT=1.952 4 dB?？梢奝_BSA-SVT

由表2可見，顯然矩陣填充算法求解誤差較兩種插值算法平均誤差要低，尤其是在已知參考點占比較低如低于40%時相差更加顯著，主要原因在于：IDW插值算法簡單，不能充分利用已知數(shù)據(jù)；而Kriging插值在計算過程依據(jù)經(jīng)驗選取的變差函數(shù)不能保證是最優(yōu)，從而影響了求解精度；而矩陣填充算法能夠充分利用位置指紋數(shù)據(jù)間的相關(guān)性及全局性，因此求解精度更高。由表2誤差數(shù)據(jù)及表3～4求解結(jié)果對比很明顯可以看出，尤其在采用BSA對傳統(tǒng)的SVT矩陣填充算法進(jìn)行改進(jìn)后，克服了原有算法的缺陷，使得求解精度進(jìn)一步提高，更能符合位置指紋庫構(gòu)建的準(zhǔn)確性要求，為更高精度地實現(xiàn)在線定位提供保障。

表3 不完整位置指紋庫的RSSI dB

表4 2種算法計算得到的RSSI對比 dB

3 實驗結(jié)果與分析

3.1 位置指紋庫構(gòu)建實驗

仿真實驗已經(jīng)驗證了本文算法的可行性及優(yōu)越性，為進(jìn)一步驗證算法的實用性，選擇面積為13 m×5 m大小的實驗室環(huán)境，利用以CC2530為核心的2.4 GHz無線射頻裝置搭建了室內(nèi)定位系統(tǒng)，并開展了相關(guān)實驗研究。

圖3所示為本次實驗的實景照片，實驗布局如圖4所示。整個定位區(qū)域被均勻劃分成7×4共28個參考網(wǎng)格，即共28個參考點?，F(xiàn)場布置6個射頻識別(Radio Frequency Identification, RFID)閱讀器，1個RFID標(biāo)簽，服務(wù)器由PC機(jī)及無線接收器構(gòu)成。在實驗中根據(jù)圖4中所示的參考點位置移動標(biāo)簽，閱讀器采集信號強(qiáng)度值，建立位置指紋庫。

圖3 實驗現(xiàn)場

實驗采用的是低成本的RFID系統(tǒng)，硬件穩(wěn)定性有限，同時考慮到射頻信號的時變性，為保證獲得準(zhǔn)確的信號強(qiáng)度測量值，對每個采樣點均進(jìn)行50次采樣，取平均值為該采樣點最終的位置指紋數(shù)據(jù)。為了更加直觀地顯示位置指紋庫中的數(shù)據(jù)，用直方圖表示各參考點處信號強(qiáng)度值，全采法得到的位置指紋數(shù)據(jù)庫如圖5。橫坐標(biāo)表示28個采樣點，每個采樣點處有6組數(shù)值，表示來自6個閱讀器采集到的標(biāo)簽在每個參考點處的信號強(qiáng)度值。

圖4 定位實驗布局

圖5 全采法獲得的位置指紋庫

實驗中，為了保證取點的連貫性和重構(gòu)精度，選取55%的參考點進(jìn)行采樣，采樣結(jié)果如圖6所示，即采集部分強(qiáng)度值組成不完整位置指紋數(shù)據(jù)庫，作為待填充的未知矩陣對象。

通過BSA-SVT進(jìn)行矩陣填充求解，得到重構(gòu)后的位置指紋庫如圖7。為了更直觀地觀察位置指紋庫填充效果，與圖5所示的全采法得到的位置指紋庫作差比較，誤差結(jié)果如圖8所示。

通過SVT算法進(jìn)行矩陣填充求解，得到重構(gòu)后的位置指紋庫如圖9，與圖5所示的全采法得到的位置指紋庫作差比較，誤差結(jié)果如圖10所示。

圖6 不完整位置指紋庫

圖7 BSA-SVT計算得到的位置指紋庫

圖8 BSA-SVT計算位置指紋庫誤差

圖9 SVT計算得到的位置指紋庫

圖10 SVT計算位置指紋庫誤差

位置指紋庫構(gòu)建實驗中，BSA-SVT的參數(shù)取值如下：問題維數(shù)D為6，種群規(guī)模NP為28，交叉概率mr取1，搜索空間范圍[low,up]設(shè)定為low=zeros(1,D),up=250·ones(1,D)，最大進(jìn)化次數(shù)ep取2 500。

計算BSA-SVT、SVT重構(gòu)結(jié)果的平均誤差值(單位：dB)，分別用P_BSA-SVT、P_SVT表示。P_BSA-SVT=2.705 4，P_SVT=3.924 9，P_BSA-SVT

3.2 室內(nèi)定位實驗

為進(jìn)一步驗證本文所提位置指紋庫構(gòu)建算法用于實際定位的可行性，分別采用圖7所示的利用BSA-SVT填充所得的位置指紋庫和圖5所示的全采法得到的位置指紋庫進(jìn)行了基于貝葉斯壓縮感知的定位實驗[18]。為了消除實驗中的隨機(jī)性和偶然誤差，保證實驗結(jié)果的真實可靠，對每個待定位點分別在兩種位置指紋庫情況下分別進(jìn)行50次定位實驗，然后取平均值，得到最終的定位結(jié)果如圖11所示，定位誤差曲線如圖12所示，定位誤差統(tǒng)計對比分析如表5。

圖11 定位實驗結(jié)果對比

圖12 定位誤差曲線

表5定位誤差對比分析m

Tab. 5 Positioning error analysis m

由以上實驗結(jié)果可知，在相同環(huán)境采用同樣的定位算法的前提下，BSA-SVT構(gòu)建的位置指紋庫和全采法得到的位置指紋庫相比，應(yīng)用在室內(nèi)定位中產(chǎn)生的定位誤差相差微小，定位結(jié)果仍然比較精確。也就表明，在位置指紋庫的構(gòu)建過程中，BSA-SVT在保證位置指紋庫構(gòu)建精度的同時，可以有效地起到減輕離線采集工作量、提高位置指紋庫構(gòu)建效率的作用。這里需要說明的是表5中所產(chǎn)生的定位誤差主要是因為RFID硬件的分辨率及穩(wěn)定性限制，加之射頻信號的時變特性及室內(nèi)環(huán)境噪聲等影響所致，可通過改進(jìn)在線階段定位算法的性能來進(jìn)一步提升定位精度。

4 結(jié)語

本文在分析了已有離線位置指紋庫建立方法所存在的不足的基礎(chǔ)上，提出了一種基于回溯搜索優(yōu)化算法改進(jìn)奇異值閾值矩陣填充算法的離線位置指紋庫高效構(gòu)建方法(BSA-SVT)。只須采集定位區(qū)域內(nèi)部分參考點的位置指紋數(shù)據(jù)，利用各參考點處位置指紋的相關(guān)性，將位置指紋庫構(gòu)建問題轉(zhuǎn)換為低秩矩陣填充問題，并引入回溯搜索優(yōu)化算法，利用其理想的全局搜索特性對奇異值閾值矩陣填充算法的尋優(yōu)過程進(jìn)行了改進(jìn)，進(jìn)而實現(xiàn)了定位區(qū)域內(nèi)完整的位置指紋數(shù)據(jù)庫的高效準(zhǔn)確構(gòu)建，進(jìn)一步增加了室內(nèi)位置指紋定位技術(shù)的實用性，推進(jìn)其從理論研究向?qū)嶋H應(yīng)用轉(zhuǎn)變的進(jìn)程。

本文所提離線位置指紋構(gòu)建算法不僅適合于RFID室內(nèi)定位系統(tǒng)，對基于Wi-Fi及ZigBee的無線室內(nèi)定位系統(tǒng)，只要是基于信號強(qiáng)度來建立位置指紋，雖然可能形式不同，但因在定位區(qū)域內(nèi)各參考點處位置指紋數(shù)據(jù)之間均具有較強(qiáng)的相關(guān)性，可認(rèn)為具有低秩性，均可采用本文算法來建立位置指紋庫，因此本文算法具有較好的普適性。

但目前本文所提算法尚需要50%左右的已知參考點的位置指紋數(shù)據(jù)才能比較準(zhǔn)確地重構(gòu)完整的位置指紋庫，如何減少利用更少的已知數(shù)據(jù)快速準(zhǔn)確地建立完整的位置指紋庫尚待進(jìn)一步研究。

References)

[1] YU F J, M H, L J. Improved AdaBoost-based fingerprint algorithm for WiFi indoor localization [C]// Proceedings of the 2014 IEEE 7th Joint International Information Technology and Artificial Intelligence Conference. Piscataway, NJ: IEEE, 2014: 4-5.

[2] JAIN V K, TAPASWI S. SHUKLA A. RSS fingerprints based Distributed Semi-Supervised Locally Linear Embedding (DSSLLE) location estimation system for indoor WLAN [J]. Wireless Personal Communications, 2013, 71(2): 1175-1192.

[3] EZPELETA S, CLAVER J M, PéREZ-SOLANO J J, et al. RF-based location using interpolation functions to reduce fingerprint mapping [J]. Sensors, 2015, 15(10): 27322-27340.

[4] 曾碧，毛勤.改進(jìn)的構(gòu)建Wi-Fi位置指紋庫算法研究[J].廣東工業(yè)大學(xué)學(xué)報,2016,33(2):51-56.(ZENG B, MAO Q. A research on algorithm of building Wi-Fi location fingerprint database [J]. Journal of Guangdong University of Technology, 2016, 33(2): 51-56.)

[5] CANDES E J, RECHT B. Exact matrix completion via convex optimization [J]. Communications of the ACM, 2012, 55(6): 111-119.

[6] MA R, BARZIGAR N, ROOZGARD A, et al. Decomposition approach for low-rank matrix completion and its applications [J]. IEEE Transactions on Signal Processing, 2014, 62(7): 1671-1683.

[7] 韋仙.基于矩陣填充技術(shù)重構(gòu)低秩密度矩陣[J].武漢工程大學(xué)學(xué)報,2015,37(2):72-76.(WEI X. Reconstructing low-rank density matrix via matrix completion [J]. Journal of Wuhan Institute of Technology, 2015, 37(2): 72-76.)

[8] MAJUMDAR A, WARD R K. Some empirical advances in matrix completion [J]. Signal Processing, 2011, 91(5): 1334-1338.

[9] 李文浩,李麗娜,徐攀峰,等.基于矩陣填充的室內(nèi)定位位置指紋庫構(gòu)建[J].遼寧大學(xué)學(xué)報(自然科學(xué)版),2015,42(4):325-329.(LI W H, LI L N, XU P F, et al. Construction of indoor location fingerprint database based on matrix completion [J]. Journal of Liaoning University (Natural Science Edition), 2015, 42(4): 325-329.)

[10] 王萍，蔡思佳，劉宇.基于隨機(jī)投影技術(shù)的矩陣填充算法的改進(jìn)[J].計算機(jī)應(yīng)用,2014,34(6):1587-1590.(WANG P, CAI S J, LIU Y. Improvement of matrix completion algorithm based on random projection [J]. Journal of Computer Applications, 2014, 34(6): 1587-1590.)

[11] CANDES E J, TAO T. The power of convex relaxation: near-optimal matrix completion [J]. IEEE Transactions on Information Theory, 2010, 56(5): 2053-2080.

[12] CANDES E J, PLAN Y. Matrix completion with noise [J]. Pro-ceedings of the IEEE, 2010, 98(6): 925-936.

[13] ZHANG Z L, ZHANG H X, JIA J, et al. Low-rank matrix recovery with discriminant regularization [C]// PAKDD 2013: Proceedings of the 17th Pacific-Asia Conference on Knowledge Discovery and Data Mining, LNCS 7819. Berlin: Springer, 2013: 437-448.

[14] CAI J F, CANDES E J, SHEN Z W. A singular value thresholding algorithm for matrix completion [J]. SIAM Journal on Optimization, 2010, 20(4): 1956-1982.

[15] CIVICIOGLU P. Backtracking search optimization algorithm for numerical optimization problems [J]. Applied Mathematics and Computation, 2013,219(15): 8121- 8144.

[16] 王曉娟，劉三陽，田文凱.帶高效變異尺度系數(shù)和貪婪交叉策略的回溯搜索優(yōu)化算法[J].計算機(jī)應(yīng)用,2014,34(9):2543-2546.(WANG X J, LIU S Y, TIAN W K. Improved backtracking search optimization algorithm with new effective mutation scale factor and greedy crossover strategy [J]. Journal of Computer Applications, 2014, 34(9): 2543-2546.)

[17] 繆鵬彬,余娟,史樂峰,等.基于改進(jìn)非參數(shù)核密度估計和拉丁超立方抽樣的電動公共客車負(fù)荷模型[J].電工技術(shù)學(xué)報,2016,31(4):187-193.(MIU P B, YU J, SHI L F, et al. Electric public bus load model based on improved kernel density estimation and Latin hypercube sampling [J]. Transactions of China Electrotechnical Society, 2016, 31(4): 187-193.)

[18] 吳哲夫,許麗敏,陳濱,等.基于貝葉斯壓縮感知多目標(biāo)定位算法[J].哈爾濱工程大學(xué)學(xué)報,2014,35(10):1282-1287.(WU Z F, XU L M, CHEN B, et al. Bayesian compressive sensing algorithm for multiple target localization [J]. Journal of Harbin Engineering University, 2014, 35(10): 1282-1287.)

This work is partially supported by the National Natural Science Foundation of China (61403176), Science and Technology Research Project of Liaoning Province Education Department (L2013003).

LILina, born in 1973, Ph. D., associate professor. Her research interests include indoor positioning, navigating technology.

LIWenhao, born in 1990, M. S. candidate. His research interests include indoor position based on RFID.

YOUHongxiang, born in 1991, M. S. candidate. His research interests include wireless indoor positioning.

WANGYue, born in 1993, M. S. candidate. His research interests include wireless sensor network.

Highefficientconstructionoflocationfingerprintdatabasebasedonmatrixcompletionimprovedbybacktrackingsearchoptimization

LI Lina1*, LI Wenhao1,2, YOU Hongxiang1, WANG Yue1

(1.CollegeofPhysics,LiaoningUniversity,ShenyangLiaoning110036,China;2.The715thResearchInstituteofChinaShipbuildingIndustryCorporation,HangzhouZhejiang310023,China)

To solve the problems existing in the off-line construction method of location fingerprint database for location fingerprint positioning based on

Signal Strength Indication (RSSI), including large workload of collecting all the fingerprint information in the location, low construction efficiency of the location fingerprint database, and the limited precision of interpolation, a high efficient off-line construction method of the location fingerprint database based on the Singular Value Thresholding (SVT) Matrix Completion (MC) algorithm improved by the Backtracking Search optimization Algorithm (BSA) was proposed. Firstly, using the collected location fingerprint data of some reference nodes, a low-rank matrix completion model was established. Then the model was solved by the low rank MC algorithm based on the SVT. Finally, the complete location fingerprint database could be reconstructed in the location area. At the same time, the BSA was introduced to improve the optimization process of MC algorithm with the minimum kernel norm as the fitness function to solve the problem of the fuzzy optimal solution and the poor smoothness of the traditional MC theory, which could further improve the accuracy of the solution. The experimental results show that the average error between the location fingerprint database constructed by the proposed method and the actual collected location fingerprint database is only 2.705 4 dB, and the average positioning error is only 0.086 3 m, but nearly 50% of the off-line collection workload can be saved. The above results show that the proposed off-line construction method of the location fingerprint database can effectively reduce the workload of off-line collection stage while ensuring the accuracy, significantly improve the construction efficiency of location fingerprint database, and improve the practicability of fingerprint positioning method to a certain extent.

Matrix Completion (MC); Singular Value Thresholding (SVT); Backtracking Search optimization Algorithm (BSA); location fingerprint database; indoor positioning

TP391.4

:A

2016- 12- 02;

:2017- 02- 05。

國家自然科學(xué)基金資助項目(61403176)；遼寧省教育廳科學(xué)技術(shù)研究項目(L2013003)。

李麗娜(1973—)，女，遼寧本溪人，副教授，博士，主要研究方向：室內(nèi)定位、導(dǎo)航技術(shù)； 李文浩(1990—)，男，甘肅會寧人，碩士研究生，主要研究方向：RFID室內(nèi)定位； 尤洪祥(1991—)，男，山東臨沂人，碩士研究生，主要研究方向：無線室內(nèi)定位； 王越(1993—)，男，遼寧本溪人，碩士研究生，主要研究方向：無線傳感網(wǎng)絡(luò)。

1001- 9081(2017)07- 1893- 07

10.11772/j.issn.1001- 9081.2017.07.1893