基于压缩感知的室内多目标无线定位算法*

任 进，姬丽彬

(北方工业大学 信息学院，北京 100144)

0 引 言

自21世纪以来，随着无线通信和信号处理技术的不断进步，无线传感器网络(Wireless Sensor Network，WSN)[1]作为无线传感技术的重要领域，正处在一个高速发展的阶段。然而，节点能量受限是WSN技术发展与应用所面临的重要挑战，因此，研究如何保证低功耗的情况下对目标节点进行高精度的定位成为一个热点问题。

近年来，对于如何优化WSN网络中定位算法，国内外学者进行了很多研究。已有研究人员将压缩感知(Compressed Sensing,CS)[2]技术与WSN相结合，利用 CS 技术降低信号的采集、传输、融合的能量消耗，同时实现网络的定位，且取得了相应的成果。文献[3-7]将机器学习运用于无线定位中：Ji等人[3]利用二元蜂群算法与压缩感知结合进行定位，具有一定的智能性；李依纯[4]利用提出的邻域加强的二分 K-means 区域划分算法，在离线阶段对指纹库区域进行聚类划分,通过提出的改进的CS定位算法获得定位坐标；Zhao等人[5]提出一种结合贝叶斯压缩感知理论和离线指纹数据库的构建方法，利用Co-Forest算法训练的随机森林分类器的决策结果以及多数原则获得定位结果，为用户完成实时定位；Zhang等人[6]提出一种基于信号到达相位差(Phase Difference of Arrival,PDOA)和接收信号强度(Received Signal Strength,RSS)的人工神经网络(Artificial Neural Network,ANN)方案；刘夏等人[7]提出了一种利用模糊C均值聚类算法和模拟退火自适应遗传算法去优化径向基函数神经网络的室内定位算法，显著提高了传统的径向基函数神经网络定位精度。文献[8-9]通过处理节点接收信号强度进行优化:Khan等人[8]将多个待定位节点的RSS值进行叠加，再将压缩的数据传输给信标节点，减少了流量开销；Yu等人[9]利用多个待定位节点接收到的信号强度差(Received Signal Strength Difference,RSSD)代替传统的RSS，提出一种基于接收信号强度差和压缩感知的融合方法，减小终端异质性带来的影响。文献[10-11]则通过改进各类匹配追踪(Matching Pursuit,MP)方法提高定位精度:Wu等人[10]提出利用阶段式正交匹配追踪算法(Stagewise Orthogonal Matching Pursuit,StOMP)提高运算速度，但造成了稳定性的下降；Li等人[11]将基于Voronoi图的贪婪匹配追踪(Greedy Matching Pursuit,GMP)方法用于在局部分区中搜索候选网格，大大减少了时间复杂度。

本文同时考虑低功耗和高性能的要求，提出了一种改进的基于贝叶斯压缩感知(Bayesian Compressive Sensing,BCS)[12]的室内多目标定位算法。实验仿真结果表明，与传统的多目标定位算法相比，本文算法在网络模型中估计出的未知节点位置和最终未知节点位置更为相近，定位效果有了显著提高，同时大大减少了系统的通信量。

1 贝叶斯压缩感知理论

BCS算法由压缩感知理论和稀疏贝叶斯学习(Sparse Bayesian Learning,SBL)[13]结合所得，它通过符合某种先验分布的随机向量，计算出信号的先验概率进而确定先验分布；然后根据样本信息，运用贝叶斯框架，计算最大后验概率分布，得出信号的均值和方差，均值即为原信号恢复的估计值。

(1)

y实际上就是信号X在观测矩阵Φ下的线性投影。

y=ΦX=ΦΨS=ΘS。

(2)

由于实际情况中存在噪声的情况，所以公式(2)可进一步表示为

y=ΦX+n=ΘS+n。

(3)

(4)

广泛应用的稀疏先验是拉普拉斯密度函数，然而，拉普拉斯密度函数的主要缺点是它无法共轭。 因此，我们考虑一个零均值的高斯先验如下:

(5)

式中：α是N个独立超参数的逆方差，即高斯先验分布的精度。

假设α已知，我们的目的是估计参数S和σ2。那么给定α和y，将条件分布(4)与公式(5)中的先验分布结合，通过贝叶斯准则来描述S后验条件概率并使其最大化，这样就得到了

(6)

式中：S的后验概率分布满足均值为μ、协方差为Ω的多变量高斯分布，即

μ=σ-2ΩΘTy，

(7)

Ω=(Λ+σ-2ΘTΘ)-1。

(8)

式中：Λ～diag{α1,α2,…,αN} 。因此，观测值y的后验密度函数是一个具有均值E[y]=Θμ和协方差Cov[y]=ΘΩΘT的多变量正态分布。

贝叶斯压缩感知重构算法的解释如下：

Step2 由于yl和Θ已知，使用公式(7)和(8)计算yl的均值μ和协方差Ω。

(9)

式中：μi是由式(7)所得的第i个后验平均权重。定义γi=1-αiΩii，Ωi1是式(8)中的对角线元素。对于噪声方差σ2，

(10)

2 室内多目标定位的算法设计

室内多目标定位的过程如图1所示。

图1 室内定位算法的流程示意图

这一过程主要包含两个阶段，即离线阶段和在线阶段。

(1)处于离线阶段时，无线接入点对定位区域内的每个网格节点的坐标位置进行记录从而构建出该区域的位置指纹库。首先，将被监测区域均匀划分为N个网格，对网格按照一定的顺序进行编号，本文按自左往右的顺序编号，即N为网格的编号;将信标节点自上往下进行编号，M即表示区域中信标节点的编号。M个信标节点采集信息后构建的位置指纹库Φ∈RM×N(M<

(11)

(2)处于在线阶段即定位阶段时，通过被监测区域信标节点对位置节点距离信息进行采集，并将这一测量值矩阵y上传到中心服务器，中心服务器通过稀疏矩阵Ψ将上传的这一系列数据进行随机亚采样和信号重构。由此，经过一系列的转换将多目标定位问题转换为稀疏信号重构的问题。同时，考虑到实际定位区域存在噪声，则上述过程可以通过公式表示为

(12)

最后，利用压缩采样所得的测量值矩阵y，离线阶段所构建出的位置指纹库Φ和稀疏变换矩阵Ψ，通过以贝叶斯压缩感知算法为基础的定位算法进行最大似然估计，进而计算出稀疏信号位置向量S，查找信号中最大值的位序，将其对应到位置指纹库中，即可精确计算出未知节点的位置坐标，有效实现定位的目的。

因此，本文的目的就是设计更加合理的稀疏变换基和观测矩阵，在实现CS的两个前提条件即稀疏性(sparsity)、不相关性(incoherence)的基础上，实现更低的功耗和误差。

3 改进矩阵设计及分析

3.1 稀疏变换基

由于室内环境中未知节点数量K远小于网格数量N(K<

(13)

式中：Ψ为N×N的单位矩阵。位置向量S在矩阵Ψ下的投影向量为

(14)

所以，向量X∈RN×K同样具有稀疏性，并且具有可压缩性，即矩阵中的大部分元素为0或接近于0。

3.2 观测矩阵

3.2.1 节点连通性的判断

传统DV-Hop[14]算法采用距离矢量交换协议，监控区域内的所有节点均可获得信标节点的跳数信息，网络规模越大则成本开销亦越大,会造成较大的浪费。因此,我们的目标是希望利用较少的通信量来做到更准确的定位。

在这里，如果网络中任意节点通过单跳路由均可和其他节点进行信息交换，则网络是连通的，进行定位之前信标节点向周围以r为半径的圆广播一个消息，即利用公式(15)判断节点之间的连通性，若第m个信标节点和第n个网格节点之间的距离dm,n小于信标节点的通信半径R，则两个节点之间可以直接通信(单跳)，连通性为1；否则无法通信，连通性为0，即

Distancem,n=dm,n

(15)

式中：第m个信标节点和第n个网格的欧式距离dm,n为

(16)

通过合理设置信标节点的通信半径将定位区域等面积划分，利用边界框(Bounding-Box)思想将待定位节点位置缩小到某块可能性区域，形成无缝覆盖的网络，最终构造出全连通的网络。

3.2.2 观测矩阵分析

压缩感知的关键是观测矩阵的构造，观测矩阵性能的好坏直接影响恢复信号和原信号之间误差的大小。CS理论大多采用随机矩阵(例如高斯随机矩阵)作为观测矩阵，这类矩阵占用的存储空间较大，且实际应用中很难用硬件实现。本文选用确定性观测矩阵，考虑用(通信半径-距离)/通信半径的算法进行构建确定性观测矩阵。

当节点之间连通时，观测矩阵Φm,n被构建为

(17)

当节点之间连通性为0时，观测矩阵Φm,n权重被设置为无穷小。

作为感知的前端，观测矩阵主要有以下几个评价标准：RIP、构造计算复杂度、矩阵维数及重构性能[15]。

(1)RIP：Baraniuk在文献[16]中提出，RIP的等价条件为稀疏变换基Ψ与观测矩阵Φ不相关。也就是说，Φ的行Φi不能由Ψ的列Ψj稀疏表示，同时Ψ的列Ψj不能由Φ的行Φi稀疏表示。由于信标节点在网格中均匀分布，而稀疏变换基Ψ的列是一个一阶稀疏的向量，显然，本文所构造的观测矩阵和稀疏变换基有很强的不相关性。

(2)构造复杂度：本文所构建的确定性观测矩阵为一次方程，通过简单的数学运算即可得到。进行存储或者传输时，只需要存储或者传输方程及参数，大大节省了存储空间，传输效率也随之提高，尤其在矩阵较大时，观测矩阵的优越性则更为明显。

(3)矩阵维度：观测矩阵的维数应尽可能不受限制以适应大面积的实际应用，本文中M为信标节点的个数，N为仿真范围与步长之比的平方，矩阵的维度较为灵活。

(4)重构性能：见下文对比图。

4 实验仿真与结果分析

本节对本文提出的改进的基于贝叶斯压缩感知的多目标定位算法进行仿真实验，并分别与基于DV-Hop的最小二乘定位算法以及基于BCS、OMP的压缩重构算法进行对比，验证本文算法定位性能的优越性；然后，分别从定位误差和定位耗时两方面研究网络步长对定位效果的影响。

4.1 仿真场景

在Matlab平台上进行仿真实验，具体参数设置如表1所示，定位区域设为100 m×100 m的方形区域，感知节点为151个，其中信标节点为121个，其余为未知节点，信标节点的通信半径为15 m。

表1 仿真场景的参数设置

4.2 实验结果及分析

考虑评价标准的普适性，采用绝对误差和通信半径的比值作为定位误差d：

(18)

本文提出的改进算法的效果如图2所示。

图2 实际位置和估计位置对比

图3展示了未知节点进入等面积划分区域后，充满随机性，不像红色信标节点的坐标均匀分布规则排列。通过将改进的BCS预测出的未知节点位置坐标与通过DV-hop算法、BCS算法、OMP算法预测出的位置进行对比，可以直观地看出改进观测矩阵的BCS算法预测定位效果最好，OMP、BCS算法效果次之，各自存在一定的缺陷，DV-hop算法最差，预测效果不够理想。

图3 不同算法的定位效果图

由图4可以得出，在同一通信半径R=15 m时，DV-hop算法预测未知节点误差百分比最大，预测位置与实际位置对比有明显差距；BCS算法和OMP算法预测定位效果相差不大，定位误差百分比均较低；改进观测矩阵的BCS的定位算法节点误差最低，定位效果最优。由表2可以得出，改进的BCS算法波动最小，OMP的误差波动不大，原BCS算法的预测误差波动较大，稳定性较差。图4和表 2表明，改进观测矩阵后，BCS的定位精度明显上升且误差波动最低。

图4 不同算法预测节点误差对比

表2 不同算法预测节点的均方误差

当通信半径为15 m时，在传感器监测区域内，不同的歩长对定位算法的影响如图5和图6所示。

图5 网络步长对定位误差的影响

图6 网络步长对定位耗时的影响

如图5所示，当网络步长增大，可能性区域中的小方格数目减少，定位难度变大，所产生的定位误差也就越大；在网络步长为1～4 m时，步长为1.1 m左右定位误差最小。从图6可以看出，随着网络步长的增长，观测矩阵的维度也在减少，通信量降低。利用不同算法进行重构时，算法计算量也相应减少，整体上定位耗时随网络步长增大而减少。由此可见，步长的设置对定位效果影响较大。而本文设定为固定步长，在稀疏度未知的情况下灵活性较低。

5 结束语

为了解决当前无线传感器网络都会存在的低功耗和高性能无法共存的问题，本文设计了一种基于压缩感知的多目标定位算法。改进观测矩阵后的BCS定位算法具有良好的重构性能，实现了定位性能与节点能量的均衡考虑。而本文算法是针对静态多目标进行研究的，在接下来的工作中，将进一步对所提算法进行改进，应用到动态目标定位和稀疏度未知的情况中去，扩大适用范围。