回溯搜索優化改進矩陣填充的高效位置指紋庫構建

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

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

回溯搜索優化改進矩陣填充的高效位置指紋庫構建

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

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

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

矩陣填充；奇異值閾值；回溯搜索優化算法；位置指紋數據庫；室內定位

0 引言

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

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

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

1 位置指紋構建原理及算法描述

1.1 矩陣填充算法

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

矩陣填充理論解決的問題是：如果已知一個未知矩陣的部分元素，設為m個元素，能否利用這m個元素組成的一個不完整矩陣完全恢復出這個未知矩陣。在利用矩陣填充理論解決實際問題時，由于未知矩陣是一個低秩矩陣或近似低秩的矩陣，所以可以通過解決一個優化問題的方法來解決矩陣填充問題[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)表示的優化問題是一個NP-hard問題，所以該優化問題的求解可以轉化為一個凸優化問題進行[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)進一步可以等價為式(5)：

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

(5)

式(5)中：

(6)

τ=5n

(7)

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

(8)

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

(9)

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

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

輸出：矩陣Xopt。

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

(10)

Y0=k0σPΩ(M)

(11)

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

(12)

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

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

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

Yk=UkΣk(Vk)T

(13)

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

(14)

(15)

(16)

令sk=hk-1+1，k=k+1，循環執行步驟2～3，直到滿足迭代次數k=kmax時，迭代停止。

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

1.2 回溯搜索優化改進的矩陣填充算法

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

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

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

步驟1 初始化。初始化算法參數：種群規模NP、交叉概率mr、搜索空間范圍、最大進化次數ep。初始化種群：歷史種群H的初始化根據式(17)選取，種群Q的初始化根據執行SVT算法所得的填充結果Xopt選取：

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

(17)

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

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

ifa

(18)

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

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

E=Q+F·(H-Q)

(19)

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

圖1 BSA-SVT流程

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

(20)

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

(21)

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

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

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

(22)

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

(23)

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

步驟6 輸出最優解。輸出當前的最優解Ti，繼續執行程序，直到達到最大進化次數ep停止，選擇輸出結果中適應度函數值最小的個體作為執行一次BSA-SVT算法的最優解。

2 仿真研究

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

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

根據無線信號在室內傳播的規律，即無線信號傳播損耗模型公式，如式(24)所示，計算各參考標簽處的信號強度得到原始位置指紋數據庫，數據如表1所示，各單元格對應參考點網格。

(24)

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

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

圖2 仿真實驗布局

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

Tab. 1 RSSI of original location fingerprint database dB

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

對表2數據分析可知，在已知參考點強度值占比較小如低于40%的情況下誤差較大，當占比大于60%時，占比加大對于精度提高的貢獻已很微小，考慮在保證重構精度的基礎上盡可能減輕人工采集數據的勞動量，一般盡可能保證信號強度誤差在2 dB以內。通過分析可知，已知參考點強度值占比取值在50%～60%是最合理區間。

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

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

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

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

3 實驗結果與分析

3.1 位置指紋庫構建實驗

仿真實驗已經驗證了本文算法的可行性及優越性，為進一步驗證算法的實用性，選擇面積為13 m×5 m大小的實驗室環境，利用以CC2530為核心的2.4 GHz無線射頻裝置搭建了室內定位系統，并開展了相關實驗研究。

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

圖3 實驗現場

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

圖4 定位實驗布局

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

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

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

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

圖6 不完整位置指紋庫

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

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

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

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

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

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

3.2 室內定位實驗

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

圖11 定位實驗結果對比

圖12 定位誤差曲線

表5定位誤差對比分析m

Tab. 5 Positioning error analysis m

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

4 結語

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

本文所提離線位置指紋構建算法不僅適合于RFID室內定位系統，對基于Wi-Fi及ZigBee的無線室內定位系統，只要是基于信號強度來建立位置指紋，雖然可能形式不同，但因在定位區域內各參考點處位置指紋數據之間均具有較強的相關性，可認為具有低秩性，均可采用本文算法來建立位置指紋庫，因此本文算法具有較好的普適性。

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

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] 曾碧，毛勤.改進的構建Wi-Fi位置指紋庫算法研究[J].廣東工業大學學報,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] 韋仙.基于矩陣填充技術重構低秩密度矩陣[J].武漢工程大學學報,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] 李文浩,李麗娜,徐攀峰,等.基于矩陣填充的室內定位位置指紋庫構建[J].遼寧大學學報(自然科學版),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].計算機應用,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] 王曉娟，劉三陽，田文凱.帶高效變異尺度系數和貪婪交叉策略的回溯搜索優化算法[J].計算機應用,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].電工技術學報,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] 吳哲夫,許麗敏,陳濱,等.基于貝葉斯壓縮感知多目標定位算法[J].哈爾濱工程大學學報,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。

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

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

1001- 9081(2017)07- 1893- 07

10.11772/j.issn.1001- 9081.2017.07.1893