基于贝叶斯压缩感知多目标定位算法

吴哲夫，许丽敏，陈滨，覃亚丽

(1.浙江工业大学信息学院，浙江杭州310023;2.浙江工业大学 艺术学院，浙江杭州310023)

基于地理位置服务(location based service，LBS)是当前无线网络的主要应用之一，而能更好满足室内用户的定位需求是实现LBS服务的前提。通过将压缩感知［1］(compressive sensing，CS)理论和无线网络技术相结合的室内多目标定位系统，实现的框架和方法能在资源受限的智能终端上独立开发与应用。目前基于无线信号的定位技术主要包括到达时间(TOA)［2］、到达时间差(TDOA)［3］、到达角度(AOA)［4］、接收信号强度(RSS)［5］等。其中 TOA、TDOA技术在测量传播时间时需要发射机和接收机严格满足时间同步;AOA方法并不需要时间同步，但是需要额外的硬件设备测量信号入射角;而基于RSS的定位技术具有无需时间同步、无需额外的硬件设备、数据容易获取等特点，因而被广泛采用。

P.Pivato［6］等基于 RSS定位技术提出了质心概念相关的2种方法——WCL和REWL，其不足之处在于锚节点上信号强度与位置的强相关性，且较难通过增加锚节点来提高定位精确性。Guo Xiaonan［7］等利用传输信号的多频性，提出了视距指纹匹配方法，其不足之处在于最多只能估计3个移动设备的位置。冯辰［8］等虽通过CS理论提出了将WSN中多目标定位问题转化为K个稀疏度为1的N维向量的重构问题，但在传输数据时没有进一步“压缩”，定位系统的通信开销比较大。何风行［9］等利用残差最优化匹配的方法对压缩感知重构算法进行了改进，提出了根据重构结构判断定位是否成功的算法框架，其不足之处在于在噪声的情况下性能较差。Zhang Bowu等［10］提出了从多个类别中计算和定位多个移动设备的框架，并用贪婪算法(greedy matching pursuit，GMP)重构原始信号，但是该方法在噪声或其他因素影响的情况下容易将目标移动设备定位到相邻网格中。通过压缩感知算法实现优化系统开销、提高系统抗噪性能是当前室内定位研究的热点。

本文基于文献［11］提出了一种将压缩感知与贝叶斯框架结合的具有一定抗噪性能的改进算法，降低基于RSS的多目标定位系统中数据采集和通信开销，给出了明确的系统模型、信号重构和优化估计算法。

1 系统模型

系统模型如图1所示，将移动设备的定位范围划分为N个网格的方形区域。区域内随机布置L个AP点，其位置为已知;同时有K个移动设备，其位置未知。这是一个基于网格的多目标定位问题，要求通过接收信号强度确定移动设备处于N个网格中的位置。

图1 系统模型Fig.1 System model

多移动设备的定位过程包括2个阶段:离线阶段和在线阶段。离线阶段用于建立指纹库，在每个网格处分别多次采集并记录来自每个APi的信号强度平均值和对应网格位置，绘制位置指纹库Ψ并存储于中心服务器。在线阶段工作时，移动设备接收系统每次随机选择APi上的信号强度传递给中心服务器。系统应用基于拉普拉斯先验模型的贝叶斯压缩定位算法，以及结合最大似然函数法和迭代逼近法计算出移动设备位于N个网格的相应位置。在系统模型中，某个时刻移动设备的位置可用N×1的稀疏向量ΘN×1来表示。定义观测矩阵Φ＇为AP的一个M×L随机选择矩阵，变换矩阵Ψ为离线阶段构建的位置指纹库，如式(1)所示:

式中:ψi，j表示网格点GPj接收来自APi的接收信号强度时间平均值;L表示区域中可检测到的AP个数。

在线阶段测量值y可表示为

式中:ξ表示均值为0，方差为σ2的高斯分布噪声。

无线网络中基于RSS的多个移动设备定位问题可转换为通过M个测量值重构N维稀疏向量的压缩感知问题。但由于M值远远小于变量N，这是一个欠定线性方程组求解问题。压缩感知理论证明，如果Θ是稀疏且观测矩阵Φ＇满足RIP条件［12］，那么式(2)中的稀疏信号Θ可以由测量值y通过求解l1范数最小的最优化问题精确重构［1］:即为了提高定位算法的自适应能力、定位的精确性，利用贝叶斯压缩感知理论并提出了对稀疏信号Θ采用拉普拉斯先验算法，其表达形式如下:

2 稀疏贝叶斯模型

2.1 观测模型

根据式(2)有

令β=σ-2，高斯分布方差的倒数的共轭概率分布为Gamma分布［13］，则β的超先验概率分布为

引入分层概念［14］，每个Θi为零均值高斯分布:

式中:γ=［γ1γ2...γN］T为超参数。对变量γi引入超参数α，变量γi为指数先验分布:

故有

对参数α使用Gamma超先验分布，得

式中:v为超参数。

通过使用拉普拉斯先验重构稀疏信号，主要根据测量值y、观测矩阵Φ'和变换矩阵ψ求出稀疏矩阵Θ、模型中的超参数及噪声方差σ2。根据贝叶斯公式，有

Θ的后验分布p(Θ|y，γ，α，β)服从均值为u，方差为Σ的多变量高斯分布:

式 中:A 为 (γ1，γ2，...，γN) 的 对 角 线。 因p(γ，β，α|y)=p(γ，β，α，y)/p(y)∝p(γ，β，α，y)，所以只需对联合概率p(γ，β，α，y)求最大值进行超参数估计。使用最大化似然函数来求其最大值，有

式中:

2.2 最大边缘似然函数

使用最大边缘似然函数估计超参数时，超参数更新需要计算后验概率的协方差矩阵，矩阵求逆需要计算时间复杂度O(M3)和空间复杂度O(M2)。为了促进稀疏性和减少计算需求，在每次迭代计算时只更新单个γi。从下文的论述中即可知道，仅更新单个超参数就会使矩阵Σ和均值u产生有效的更新。由于每个超参数 γi，i∈ {1，2，...，M}都是独立的，故可以将式(15)中的C分解为

式中:C-i是C中去除第i个基函数后的矩阵。式(16)通过Woodbury判别式，可以得到:

利用行列式判别式，则有

因此可求得式(14)的似然函数为

式中:si为稀疏因子，反映了基函数φi与其余所有基函数的重叠程度;而qi为质量因子，反映了去除基函数φi后对模型误差的矫正。式(19)关于γi的导数的表达式可以写为如下形式:

且si2+4qi2α＞(si+2α)2，即qi2-si＞α ，由式(22)可以发现，由此可知当且仅当γ=γi时，L(γ)取得最大值。

一旦利用式(24)对超参数γi进行更新，则变量si，qi，u，Σ可得到有效的更新。同理分别对超参数β，α，ν求导并令其导数为零，可得

假如si=ΦTiC-1Φi，Qi=ΦTiC-1y，根据文献［15］利用Woodbury恒等式可以计算出:

在实际应用中，需要给出各超参数初始值并根据(12)、(13)、(24)、(25)、(26)和(27)进行迭代计算。由文献［16］，设初始值 β-1=0.01×var(y)。由文献［11］可知，利用式(27)估计超参数v的重构性要比v=0时差，所以将v固定为0。

通过上述等式，在每次迭代中都可以通过更新一个超参数 γi来获得迭代处理，并更新si，qi，u，Σ 。

3 仿真与结果分析

以下对所提出的基于贝叶斯压缩感知BCS算法在 Matlab 中进行仿真，并与基于 OMP［17］、BP［18］压缩重构定位算法的性能进行定量比较和分析。

实验将10 m×10 m的方形区域划分为10×10个网格节点，并部署了7个无线接入点和随机分布K个待测移动设备。每次测量时随机选择一个APi，将K个移动设备接收来自该APi的信号强度传递给中心服务器，共采集M次测量值形成 y=［y1y2...ym］T。仿真参数如表1所示。由文献［19］可知，要用较少的测量值估计出移动设备的位置，N、M和K三者之间必须满足M≥cKlb(N/K)，其中c是一个较小的常数。

表1 仿真实验中使用的参数Table 1 Parameters in the simulation

实验中定位误差的计算方法为［7］

图2 平均定位误差与SNR的关系Fig.2 Average localization error versus SNR

图3是K=5，M=25，SNR=25 dB的定位效果图。通过仿真100次得到平均定位误差为0.20 m。

如将K增加到10，在相同环境下如取测量数M=40，可得到平均定位误差为0.14 m，定位情况如图4所示。

图3 K=5，M=25的定位效果图Fig.3 The result of localization when K=5，M=25

图4 K=10，M=40的定位效果图Fig.4 The result of localization when K=10，M=40

下面针对测量数M、移动设备个数K与平均定位误差分别对基于BCS、OMP和BP算法进行讨论。

1)测量数与平均定位误差的关系:取K=5，SNR=25 dB，当M从10～40变化时与平均定位误差的关系如图5所示。

图5 平均定位误差随测量次数变化Fig.5 The average localization error changes along with the number of measurement

如图5所示，平均定位误差随着测量次数增加而快速递减。当M=25时，BCS和BP算法已可定位出移动设备，这与Klb(N/K)≈25相符合。M较小时，BCS算法的平均定位误差比BP算法大，但M值增加且当M≥25时，BCS算法的定位精确度要比其他2种算法高。相比于OMP算法，其平均定位误差至少下降了52.2%(M=40:(0.111 2-0.053 2)/0.111 2≈52.2%);与 BP 算法相比，其平均定位误差至少下降了 13.7%(M=25:(0.286 1-0.247 0)/0.286 1 ≈13.7%)。当M=30 时，BCS 算法能够精确恢复移动设备的位置，其精确度几乎接近100%。

2)移动设备数与定位误差的关系:在相同实验环境下，取M=35，SNR=25 dB，K分别为 5、6、7、8、9、10时与平均定位误差关系如图6所示。

图6 平均定位误差随移动设备个数变化Fig.6 The average localization error changes along with the number of mobile devices

由图6可发现随着移动设备个数K增加即信号稀疏度逐渐变差时，3种算法的平均定位误差都逐渐变大;与OMP和BP相比，BCS算法至少降低平均定位误差 8.7%(K=10:(0.521 8-0.476 3)/0.521 8≈8.7%)～ 47.2%(K=5:(0.110 3-0.058 3)/0.110 3≈47.2%)。在测量数M=35时，BCS算法能在平均误差0.5 m之内定位10个移动设备。这与已知K=10，根据M≥Klb(N/K)算出M≈35相符合。

4 结束语

本文提出了将贝叶斯压缩感知算法应用到无线网络多移动设备定位的系统框架中，采用将拉普拉斯先验模型与贝叶斯压缩感知理论相结合的算法对多移动设备进行定位。压缩感知理论根据信号稀疏性特征采用在线处理信号的方式，不仅节省采样时间，还显著地减少了节点能耗和通信开销。相较于其他重构算法，基于拉普拉斯先验的贝叶斯压缩感知具有重构速度快、估计未知信号的同时获得模型参数等特点，通过与OMP、BP算法的比较，可以发现该算法具有较高定位精确度和较低稀疏度要求。但该算法复杂度稍高，还需在后续工作中进一步开展降低计算复杂度的研究。

［1］DONOHO D L.Compressed sensing［J］.Transactions on Information Theory，2006，52(4):1289-1306.

［2］CHANG A C，CHUNG C M.Covariance shaping leastsquares location estimation using TOA measurements［J］.IEICE Transactions on Fundamentals of Estimation，Communication and Computer Sciences，2007，90(3):691-693.

［3］SO H C，HUI S P.Constrained location algorithm using TDOA measurements［J］.IEICE Transactions on Fundamentals of Electronics，Communications and Computer Sciences，2003，86(12):3291-3293.

［4］RONG P，SICHITIU M L.Angle of arrival localization for wireless sensor networks［C］//Proceedings of Third Annual IEEE Communications Society on Sensor and Ad Hoc Communications and Networks.Reston，USA，2006:374-382.

［6］PIVATO P，PALOPOLI L，PETRI D.Accuracy of RSS-based centroid localization algorithms in an indoor environment［J］.IEEE Transactions on Instrumentation and Measurement，2011，60(10):3451-3460.

［7］GUO Xiaonan，ZHANG Dian，NI Lionelm.Localizing multiple objects in an RF-based dynamic environment［C］//IEEE 32nd International Conference on Distributed Computing Systems.Macau，China，2012:576-585.

［8］FENG Chen，SHAHROKH V，TAN Zhenhui.Multiple target localization using compressive Sensing［C］//IEEE Global Telecommunications Conference.Hawaii，USA，2009:1-6.

［9］何风行，余志军，刘海涛.基于压缩感知的无线传感器网络多目标定位算法［J］.电子与信息学报，2012，34(3):716-721.HE Fenghang，YU Zhijun，LIU Haitao.Multiple target localization via compressed sensing in wireless sensor networks［J］.Journal of Electronics and Information Technology，2012，34(3):716-721.

［10］ZHANG B W，CHENG X Z，ZHANG N，et al.Sparse target counting and localization in sensor networks based on compressive sensing［C］//IEEE INFOCOM.Shanghai，China，2011:2255-2263.

［11］BABACAN S D，MOLINA R，KATSAGGELOS A K.Bayesian compressive sensing using laplace priors［J］.IEEE Transactions on Image Processing，2010，19(1):53-63.

［12］CANDES E J，ROMBERG J，TAO T.Robust uncertainty principles:exact signal reconstruction from highly incomplete frequency in information［J］.IEEE Transactions on Information theory，2006，52(2):489-509.

［13］TIPPING M E.Sparse Bayesian learning and the relevance vector machine［J］.Journal of Machine Learning Research，2001，1(3):211-244.

［14］FIGUEIREDO M A T.Adaptive sparseness for supervised learning［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2003，25(9):1150-1159.

［15］TIPPING M E，FAUL A C.Fast marginal likelihood maximization for sparse Bayesian models［C］//Proceedings of the Ninth International Workshop on Artificial Intelligence and Statistics.Key West，USA，2003:1-8.

［16］章坚武，颜欢，包建荣.改进的基于拉普拉斯先验的贝叶斯压缩感知算法［J］.电路与系统学报，2012，17(1):34-40.ZHANG Jianwu，YAN Huan，BAO Jianrong.Improved Bayesian compressive sensing algorithm with Laplace priors［J］.Journal of Circuits and Systems，2012，17(1):34-40.

［17］TROPP J A，GILBERT A C.Signal recovery from random measurements via orthogonal matching pursuit［J］.IEEE Transactions on Information Theory，2007，53(12):4655-4666.

［18］CHEN S S，DONOHO D L，SAUNDERS M A.Atomic decomposition by basis pursuit［J］.SIAM Review，2001，43(1):129-159.

［19］朱翠涛，瞿毅.基于压缩感知的稀疏事件检测［J］.中南民族大学学报:自然科学版，2011，30(1):80-83.ZHU Cuitao，QU Yi.Sparse event detection based on compressive sensing［J］.Journal of South-Central University for Nationalities:Natural Science Edition，2011，30(1):80-83.