2. 中国船舶重工集团公司第七一五研究所, 杭州 310023
2. The 715 th Research Institute of China Shipbuilding Industry Corporation, Hangzhou Zhejiang 310023, China
随着物联网技术的蓬勃发展及日益普及,作为室外全球定位系统(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):
$\begin{array}{*{20}{c}} {{\rm{min}}\;{\rm{rank}}\left( \mathit{\boldsymbol{X}} \right)}\\ {{\rm{s}}{\rm{.}}\;{\rm{t}}{\rm{.}}\quad {X_{ij}} = {M_{ij}},i,j \in \mathit{\Omega }} \end{array}$ | (1) |
其中:X表示矩阵,Xij表示矩阵X的第i行、第j列元素;M表示由m个元素组成的n1×n2的不完整矩阵,Mij表示矩阵M的第i行、第j列元素;Ω表示矩阵中被观测到的元素的位置的集合。
由于式(1) 表示的优化问题是一个NP-hard问题,所以该优化问题的求解可以转化为一个凸优化问题进行[12-13],如式(2) 或式(3) 所示:
$\begin{array}{*{20}{c}} {{\rm{min}}\quad {{\left\| \mathit{\boldsymbol{X}} \right\|}_*}}\\ {{\rm{s}}{\rm{.}}\;{\rm{t}}{\rm{.}}\quad {X_{ij}} = {\mathit{\boldsymbol{M}}_{ij}},i,j \in \mathit{\Omega }} \end{array}$ | (2) |
${\rm{min}}\frac{1}{2}\left\| {{P_\mathit{\Omega }}\left( {\mathit{\boldsymbol{X}} - \mathit{\boldsymbol{M}}} \right)} \right\|_2^2 + \mu {\left\| \mathit{\boldsymbol{X}} \right\|_*}$ | (3) |
其中:‖X‖*表示核范数,
由式(2) ~(3) 可知,矩阵填充求解问题的目的在于找到满足PΩ(X)=PΩ(M),且使得‖X‖*最小的X,如式(4) 所示:
$\begin{array}{*{20}{c}} {{\rm{min}}\quad {{\left\| \mathit{\boldsymbol{X}} \right\|}_*}}\\ {{\rm{s}}{\rm{.}}\;{\rm{t}}{\rm{.}}\quad {P_\mathit{\Omega }}\left( \mathit{\boldsymbol{X}} \right) = {P_\mathit{\Omega }}\left( \mathit{\boldsymbol{M}} \right),i,j \in \mathit{\Omega }} \end{array}$ | (4) |
其中,PΩ对于M矩阵而言,就是使得矩阵M在Ω外消失的正交投影,即:如果(i, j)∈Ω,则PΩ(M)的第(i, j)项等于Mij,其他项为零。式(4) 进一步可以等价为式(5):
$\begin{array}{*{20}{c}} {{\rm{min}}\;\tau \;{{\left\| \mathit{\boldsymbol{X}} \right\|}_*} + \frac{1}{2}\left\| \mathit{\boldsymbol{X}} \right\|_F^2}\\ {{\rm{s}}{\rm{.}}\;{\rm{t}}{\rm{.}}\quad {P_\mathit{\Omega }}\left( \mathit{\boldsymbol{X}} \right) = {P_\mathit{\Omega }}\left( \mathit{\boldsymbol{M}} \right),i,j \in \mathit{\Omega }} \end{array}$ | (5) |
式(5) 中:
${\left\| \mathit{\boldsymbol{X}} \right\|_F} = {\left\langle {\mathit{\boldsymbol{X}},\mathit{\boldsymbol{X}}} \right\rangle ^{1/2}} = {\left( {\sum\limits_{j = 1}^n {{\sigma _j}{{\left( \mathit{\boldsymbol{X}} \right)}^2}} } \right)^{1/2}}$ | (6) |
$\tau = 5n$ | (7) |
$n = {\rm{max}}\left\{ {{n_1},{n_2}} \right\};\mathit{\boldsymbol{M}}{\rm{矩阵维数为}}{n_1} \cdot {n_2}$ | (8) |
为了解决式(5) 这种优化问题,Cai等[14]提出了奇异值阈值(SVT)算法,SVT算法是最早的也是最常用的解决矩阵填充问题的一种算法,是一种典型的Lagrange乘子算法。式(5) 中,其Lagrangian函数如式(9) 所示:
$L\left( {\mathit{\boldsymbol{X}},\mathit{\boldsymbol{Y}}} \right) = \tau {\left\| \mathit{\boldsymbol{X}} \right\|_*} + \frac{1}{2}\left\| \mathit{\boldsymbol{X}} \right\|_F^2 + \left\langle {\mathit{\boldsymbol{Y}},{P_\mathit{\Omega }}\left( {\mathit{\boldsymbol{M}} - \mathit{\boldsymbol{X}}} \right)} \right\rangle $ | (9) |
SVT算法基本步骤归纳如下:
输入:样本集合Ω和样本项PΩ(M),步长σ,参数τ,容差ε>0,增量l,迭代常数Kmax。
输出:矩阵Xopt。
步骤1 初始化。设k0满足式(10),Y0的取值见式(11):
$\frac{\tau }{{\sigma {{\left\| {{P_\mathit{\Omega }}\left( \mathit{\boldsymbol{M}} \right)} \right\|}_2}}} \in \left( {{k_0} - 1,{k_0}} \right]$ | (10) |
${\mathit{\boldsymbol{Y}}_0} = {k_0}\sigma {P_\mathit{\Omega }}\left( \mathit{\boldsymbol{M}} \right)$ | (11) |
$\sigma = 1.2 \times {n_1} \cdot {n_2}/m;\mathit{\boldsymbol{M}}{\rm{矩阵维数为}}{n_1} \cdot {n_2}$ | (12) |
参数τ的取值见式(7),同时令k=1,h0=0,s1=1。
步骤2 奇异值分解(Singular Value Decomposition,SVD)。
① 矩阵Yk通过奇异值分解可以转化为3个矩阵乘积的形式:
${\mathit{\boldsymbol{Y}}^k} = {\mathit{\boldsymbol{U}}^k}{\mathit{\boldsymbol{ \boldsymbol{\varSigma} }}^k}{\left( {{\mathit{\boldsymbol{V}}^k}} \right)^{\rm{T}}}$ | (13) |
Yk执行奇异值分解得到:[Uk, Σk, Vk]sk。式(13) 中,Uk=[u1k, u2k, …, urk],Vk=[v1k, v2k, …, vrk],(Vk)T是Vk的共轭转置;Σk=diag(η1k, η2k, …, ηrk),包含了r个降序排列的奇异值:η1k, η2k, …, ηrk。
② 迭代:令sk=sk+l,循环执行①~②,直到奇异值满足ηk-1sk-l≤τ时,迭代停止。
步骤3 迭代。更新矩阵及其迭代条件,得到满足条件的矩阵Xk。
${h_k} = {\text{max}}\left\{ {j:\eta _j^{k - 1} > \tau } \right\}$ | (14) |
${\mathit{\boldsymbol{X}}^k} = \sum\limits_{j = 1}^{{h_k}} {\left( {\eta _j^{k - 1} - \tau } \right)u_j^{k - 1}v_j^{k - 1}} $ | (15) |
$Y_{ij}^k = \left\{ {\begin{array}{*{20}{l}} {0,}&{\left( {i,j} \right) \notin \mathit{\boldsymbol{ \boldsymbol{\varOmega} }}} \\ {Y_{ij}^{k - 1} + \sigma \left( {{M_{ij}} - X_{ij}^k} \right),}&{\left( {i,j} \right) \in \mathit{\boldsymbol{ \boldsymbol{\varOmega} }}} \end{array}} \right.$ | (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选取:
${\mathit{\boldsymbol{Q}}_i} = {\mathit{\boldsymbol{X}}^{{\rm{opt}}}},{H_{i,j}} \sim {\rm{U(}}lo{w_j},u{p_j}{\rm{)}}$ | (17) |
其中:i=1, 2, …, NP,NP表示种群规模;j=1, 2, …, D,D表示种群维数;low、up分别表示搜索空间范围的下界和上界;U表示随机均匀分布;此处Hi, j表示(lowj, upj)上服从均匀分布的随机数。
步骤2 选择Ⅰ。选择Ⅰ的主要作用是选择一个新的历史种群。其基本思路如式(18) 所示:
$\begin{array}{*{20}{c}} {{\rm{if}}}&{a < b}&{{\rm{then}}}&{\mathit{\boldsymbol{H}} = \mathit{\boldsymbol{Q}}} \end{array}$ | (18) |
式(18) 中a, b满足a, b~U(0.1)。式(18) 的作用是在前代种群中选择并记住一个历史种群,直到该历史种群再次发生改变。
步骤3 种群变异。在历史种群H确定之后,对历史种群H中的个体随机排序,然后又重新赋予H,这一过程称为种群变异。变异如式(19) 所示:
$\mathit{\boldsymbol{E}} = \mathit{\boldsymbol{Q}} + F \cdot \left( {\mathit{\boldsymbol{H}} - \mathit{\boldsymbol{Q}}} \right)$ | (19) |
式(19) 中,F表示尺度系数,作用是控制种群变异的幅度,大小为F=3·randn,randn~N(0, 1)。
步骤4 种群交叉。BSA的种群交叉是一种通过交叉概率Ⅰ控制两种交叉方式等概率调用的较为复杂的联合交叉方法,种群交叉的目的是产生新一代的种群。BSA新一代种群T的个体的产生如式(20):
${T_{i,j}} = \left\{ \begin{gathered} {E_{i,j}},\quad \quad {Z_{i,j}} = 1 \hfill \\ {Q_{i,j}},\quad \quad {Z_{i,j}} = 0 \hfill \\ \end{gathered} \right.$ | (20) |
式(20) 中,Z是NP×D的整数矩阵,初始赋值取1,具体计算见式(21):
$\left\{ \begin{gathered} {Z_{i,u{\text{(1:[}}mr \cdot rand \cdot D{\text{]) }}}} = 0,\quad \quad a < b \hfill \\ {Z_{i,randi{\text{(}}D{\text{)}}}} = 0,\quad \quad \quad \quad a \geqslant b \hfill \\ \end{gathered} \right.$ | (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) 所示:
${\mathit{\boldsymbol{Q}}_i} = \left\{ {\begin{array}{*{20}{l}} {{\mathit{\boldsymbol{T}}_i},}&{fitness{\rm{(}}{\mathit{\boldsymbol{T}}_i}{\rm{)}} < fitness{\rm{(}}{\mathit{\boldsymbol{Q}}_i}{\rm{)}}} \\ {{\mathit{\boldsymbol{Q}}_i},}&{\rm{其他}} \end{array}} \right.$ | (22) |
由式(4) 可知,矩阵填充解决的是求解一个最小核范数问题,因此设式(23) 为适应度函数:
$fitness\left( {{\mathit{\boldsymbol{P}}_i}} \right) = \frac{{{{\left\| {{P_\mathit{\Omega }}\left( {{\mathit{\boldsymbol{P}}_i} - \mathit{\boldsymbol{M}}} \right)} \right\|}_F}}}{{{{\left\| {{P_\mathit{\Omega }}\left( \mathit{\boldsymbol{M}} \right)} \right\|}_F}}}$ | (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所示,各单元格对应参考点网格。
${P_r}\left( d \right) = \bar P\left( {{d_0}} \right) - 10n\;{\text{lo}}{{\text{g}}_n}\left( {d/{d_0}} \right) - {X_\sigma }$ | (24) |
其中,d表示射频标签与阅读器之间的实际物理距离,d0表示预设的参考距离,Pr(d)表示在距离d处接收到的信号强度值(RSSI),P(d0)表示在距离为d0的位置平均信号强度损耗值,n表示路径损耗指数,Xσ表示高斯噪声分布。
下面将利用拉丁超立方抽样(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数据分析可知,在已知参考点强度值占比较小如低于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<P_SVT。
由表 2可见,显然矩阵填充算法求解误差较两种插值算法平均误差要低,尤其是在已知参考点占比较低如低于40%时相差更加显著,主要原因在于:IDW插值算法简单,不能充分利用已知数据;而Kriging插值在计算过程依据经验选取的变差函数不能保证是最优,从而影响了求解精度;而矩阵填充算法能够充分利用位置指纹数据间的相关性及全局性,因此求解精度更高。由表 2误差数据及表 3~4求解结果对比很明显可以看出,尤其在采用BSA对传统的SVT矩阵填充算法进行改进后,克服了原有算法的缺陷,使得求解精度进一步提高,更能符合位置指纹库构建的准确性要求,为更高精度地实现在线定位提供保障。
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中所示的参考点位置移动标签,阅读器采集信号强度值,建立位置指纹库。
实验采用的是低成本的RFID系统,硬件稳定性有限,同时考虑到射频信号的时变性,为保证获得准确的信号强度测量值,对每个采样点均进行50次采样,取平均值为该采样点最终的位置指纹数据。为了更加直观地显示位置指纹库中的数据,用直方图表示各参考点处信号强度值,全采法得到的位置指纹数据库如图 5。横坐标表示28个采样点,每个采样点处有6组数值,表示来自6个阅读器采集到的标签在每个参考点处的信号强度值。
实验中,为了保证取点的连贯性和重构精度,选取55%的参考点进行采样,采样结果如图 6所示,即采集部分强度值组成不完整位置指纹数据库,作为待填充的未知矩阵对象。
通过BSA-SVT进行矩阵填充求解,得到重构后的位置指纹库如图 7。为了更直观地观察位置指纹库填充效果,与图 5所示的全采法得到的位置指纹库作差比较,误差结果如图 8所示。
通过SVT算法进行矩阵填充求解,得到重构后的位置指纹库如图 9,与图 5所示的全采法得到的位置指纹库作差比较,误差结果如图 10所示。
位置指纹库构建实验中,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<P_SVT。通过对以上实验结果对比分析可知,相比SVT算法,BSA-SVT能够更加精确地对位置指纹库进行重构,由图 8及图 10的误差对比可知,BSA-SVT求解结果的误差更加均匀,说明数据的平滑性更好,即所提算法在保证计算精度的前提下,极大提高了位置指纹库构建的效率。
3.2 室内定位实验为进一步验证本文所提位置指纹库构建算法用于实际定位的可行性,分别采用图 7所示的利用BSA-SVT填充所得的位置指纹库和图 5所示的全采法得到的位置指纹库进行了基于贝叶斯压缩感知的定位实验[18]。为了消除实验中的随机性和偶然误差,保证实验结果的真实可靠,对每个待定位点分别在两种位置指纹库情况下分别进行50次定位实验,然后取平均值,得到最终的定位结果如图 11所示,定位误差曲线如图 12所示,定位误差统计对比分析如表 5。
由以上实验结果可知,在相同环境采用同样的定位算法的前提下,BSA-SVT构建的位置指纹库和全采法得到的位置指纹库相比,应用在室内定位中产生的定位误差相差微小,定位结果仍然比较精确。也就表明,在位置指纹库的构建过程中,BSA-SVT在保证位置指纹库构建精度的同时,可以有效地起到减轻离线采集工作量、提高位置指纹库构建效率的作用。这里需要说明的是表 5中所产生的定位误差主要是因为RFID硬件的分辨率及稳定性限制,加之射频信号的时变特性及室内环境噪声等影响所致,可通过改进在线阶段定位算法的性能来进一步提升定位精度。
4 结语本文在分析了已有离线位置指纹库建立方法所存在的不足的基础上,提出了一种基于回溯搜索优化算法改进奇异值阈值矩阵填充算法的离线位置指纹库高效构建方法(BSA-SVT)。只须采集定位区域内部分参考点的位置指纹数据,利用各参考点处位置指纹的相关性,将位置指纹库构建问题转换为低秩矩阵填充问题,并引入回溯搜索优化算法,利用其理想的全局搜索特性对奇异值阈值矩阵填充算法的寻优过程进行了改进,进而实现了定位区域内完整的位置指纹数据库的高效准确构建,进一步增加了室内位置指纹定位技术的实用性,推进其从理论研究向实际应用转变的进程。
本文所提离线位置指纹构建算法不仅适合于RFID室内定位系统,对基于Wi-Fi及ZigBee的无线室内定位系统,只要是基于信号强度来建立位置指纹,虽然可能形式不同,但因在定位区域内各参考点处位置指纹数据之间均具有较强的相关性,可认为具有低秩性,均可采用本文算法来建立位置指纹库,因此本文算法具有较好的普适性。
但目前本文所提算法尚需要50%左右的已知参考点的位置指纹数据才能比较准确地重构完整的位置指纹库,如何减少利用更少的已知数据快速准确地建立完整的位置指纹库尚待进一步研究。
[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. DOI:10.1007/s11277-012-0868-z |
[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. DOI:10.3390/s151027322 |
[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. DOI:10.1145/2184319 |
[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. DOI:10.1109/TSP.2014.2301139 |
[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. DOI:10.1016/j.sigpro.2010.12.005 |
[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. DOI:10.11772/j.issn.1001-9081.2014.06.1587) |
[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. DOI:10.1109/TIT.2010.2044061 |
[12] | CANDES E J, PLAN Y. Matrix completion with noise[J]. Pro-ceedings of the IEEE, 2010, 98(6): 925-936. DOI:10.1109/JPROC.2009.2035722 |
[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. DOI:10.1137/080738970 |
[15] | CIVICIOGLU P. Backtracking search optimization algorithm for numerical optimization problems[J]. Applied Mathematics and Computation, 2013, 219(15): 8121-8144. DOI:10.1016/j.amc.2013.02.017 |
[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. DOI:10.11772/j.issn.1001-9081.2014.09.2543) |
[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. DOI:10.3969/j.issn.1006-7043.201306064) |