基于貝葉斯壓縮感知多目標定位算法

吳哲夫，許麗敏，陳濱，覃亞麗

(1.浙江工業(yè)大學信息學院，浙江杭州310023;2.浙江工業(yè)大學 藝術學院，浙江杭州310023)

基于地理位置服務(location based service，LBS)是當前無線網(wǎng)絡的主要應用之一，而能更好滿足室內(nèi)用戶的定位需求是實現(xiàn)LBS服務的前提。通過將壓縮感知［1］(compressive sensing，CS)理論和無線網(wǎng)絡技術相結(jié)合的室內(nèi)多目標定位系統(tǒng)，實現(xiàn)的框架和方法能在資源受限的智能終端上獨立開發(fā)與應用。目前基于無線信號的定位技術主要包括到達時間(TOA)［2］、到達時間差(TDOA)［3］、到達角度(AOA)［4］、接收信號強度(RSS)［5］等。其中 TOA、TDOA技術在測量傳播時間時需要發(fā)射機和接收機嚴格滿足時間同步;AOA方法并不需要時間同步，但是需要額外的硬件設備測量信號入射角;而基于RSS的定位技術具有無需時間同步、無需額外的硬件設備、數(shù)據(jù)容易獲取等特點，因而被廣泛采用。

P.Pivato［6］等基于 RSS定位技術提出了質(zhì)心概念相關的2種方法——WCL和REWL，其不足之處在于錨節(jié)點上信號強度與位置的強相關性，且較難通過增加錨節(jié)點來提高定位精確性。Guo Xiaonan［7］等利用傳輸信號的多頻性，提出了視距指紋匹配方法，其不足之處在于最多只能估計3個移動設備的位置。馮辰［8］等雖通過CS理論提出了將WSN中多目標定位問題轉(zhuǎn)化為K個稀疏度為1的N維向量的重構(gòu)問題，但在傳輸數(shù)據(jù)時沒有進一步“壓縮”，定位系統(tǒng)的通信開銷比較大。何風行［9］等利用殘差最優(yōu)化匹配的方法對壓縮感知重構(gòu)算法進行了改進，提出了根據(jù)重構(gòu)結(jié)構(gòu)判斷定位是否成功的算法框架，其不足之處在于在噪聲的情況下性能較差。Zhang Bowu等［10］提出了從多個類別中計算和定位多個移動設備的框架，并用貪婪算法(greedy matching pursuit，GMP)重構(gòu)原始信號，但是該方法在噪聲或其他因素影響的情況下容易將目標移動設備定位到相鄰網(wǎng)格中。通過壓縮感知算法實現(xiàn)優(yōu)化系統(tǒng)開銷、提高系統(tǒng)抗噪性能是當前室內(nèi)定位研究的熱點。

本文基于文獻［11］提出了一種將壓縮感知與貝葉斯框架結(jié)合的具有一定抗噪性能的改進算法，降低基于RSS的多目標定位系統(tǒng)中數(shù)據(jù)采集和通信開銷，給出了明確的系統(tǒng)模型、信號重構(gòu)和優(yōu)化估計算法。

1 系統(tǒng)模型

系統(tǒng)模型如圖1所示，將移動設備的定位范圍劃分為N個網(wǎng)格的方形區(qū)域。區(qū)域內(nèi)隨機布置L個AP點，其位置為已知;同時有K個移動設備，其位置未知。這是一個基于網(wǎng)格的多目標定位問題，要求通過接收信號強度確定移動設備處于N個網(wǎng)格中的位置。

圖1 系統(tǒng)模型Fig.1 System model

多移動設備的定位過程包括2個階段:離線階段和在線階段。離線階段用于建立指紋庫，在每個網(wǎng)格處分別多次采集并記錄來自每個APi的信號強度平均值和對應網(wǎng)格位置，繪制位置指紋庫Ψ并存儲于中心服務器。在線階段工作時，移動設備接收系統(tǒng)每次隨機選擇APi上的信號強度傳遞給中心服務器。系統(tǒng)應用基于拉普拉斯先驗模型的貝葉斯壓縮定位算法，以及結(jié)合最大似然函數(shù)法和迭代逼近法計算出移動設備位于N個網(wǎng)格的相應位置。在系統(tǒng)模型中，某個時刻移動設備的位置可用N×1的稀疏向量ΘN×1來表示。定義觀測矩陣Φ＇為AP的一個M×L隨機選擇矩陣，變換矩陣Ψ為離線階段構(gòu)建的位置指紋庫，如式(1)所示:

式中:ψi，j表示網(wǎng)格點GPj接收來自APi的接收信號強度時間平均值;L表示區(qū)域中可檢測到的AP個數(shù)。

在線階段測量值y可表示為

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

無線網(wǎng)絡中基于RSS的多個移動設備定位問題可轉(zhuǎn)換為通過M個測量值重構(gòu)N維稀疏向量的壓縮感知問題。但由于M值遠遠小于變量N，這是一個欠定線性方程組求解問題。壓縮感知理論證明，如果Θ是稀疏且觀測矩陣Φ＇滿足RIP條件［12］，那么式(2)中的稀疏信號Θ可以由測量值y通過求解l1范數(shù)最小的最優(yōu)化問題精確重構(gòu)［1］:即為了提高定位算法的自適應能力、定位的精確性，利用貝葉斯壓縮感知理論并提出了對稀疏信號Θ采用拉普拉斯先驗算法，其表達形式如下:

2 稀疏貝葉斯模型

2.1 觀測模型

根據(jù)式(2)有

令β=σ-2，高斯分布方差的倒數(shù)的共軛概率分布為Gamma分布［13］，則β的超先驗概率分布為

引入分層概念［14］，每個Θi為零均值高斯分布:

式中:γ=［γ1γ2...γN］T為超參數(shù)。對變量γi引入超參數(shù)α，變量γi為指數(shù)先驗分布:

故有

對參數(shù)α使用Gamma超先驗分布，得

式中:v為超參數(shù)。

通過使用拉普拉斯先驗重構(gòu)稀疏信號，主要根據(jù)測量值y、觀測矩陣Φ'和變換矩陣ψ求出稀疏矩陣Θ、模型中的超參數(shù)及噪聲方差σ2。根據(jù)貝葉斯公式，有

Θ的后驗分布p(Θ|y，γ，α，β)服從均值為u，方差為Σ的多變量高斯分布:

式 中:A 為 (γ1，γ2，...，γN) 的 對 角 線。 因p(γ，β，α|y)=p(γ，β，α，y)/p(y)∝p(γ，β，α，y)，所以只需對聯(lián)合概率p(γ，β，α，y)求最大值進行超參數(shù)估計。使用最大化似然函數(shù)來求其最大值，有

式中:

2.2 最大邊緣似然函數(shù)

使用最大邊緣似然函數(shù)估計超參數(shù)時，超參數(shù)更新需要計算后驗概率的協(xié)方差矩陣，矩陣求逆需要計算時間復雜度O(M3)和空間復雜度O(M2)。為了促進稀疏性和減少計算需求，在每次迭代計算時只更新單個γi。從下文的論述中即可知道，僅更新單個超參數(shù)就會使矩陣Σ和均值u產(chǎn)生有效的更新。由于每個超參數(shù) γi，i∈ {1，2，...，M}都是獨立的，故可以將式(15)中的C分解為

式中:C-i是C中去除第i個基函數(shù)后的矩陣。式(16)通過Woodbury判別式，可以得到:

利用行列式判別式，則有

因此可求得式(14)的似然函數(shù)為

式中:si為稀疏因子，反映了基函數(shù)φi與其余所有基函數(shù)的重疊程度;而qi為質(zhì)量因子，反映了去除基函數(shù)φi后對模型誤差的矯正。式(19)關于γi的導數(shù)的表達式可以寫為如下形式:

且si2+4qi2α＞(si+2α)2，即qi2-si＞α ，由式(22)可以發(fā)現(xiàn)，由此可知當且僅當γ=γi時，L(γ)取得最大值。

一旦利用式(24)對超參數(shù)γi進行更新，則變量si，qi，u，Σ可得到有效的更新。同理分別對超參數(shù)β，α，ν求導并令其導數(shù)為零，可得

假如si=ΦTiC-1Φi，Qi=ΦTiC-1y，根據(jù)文獻［15］利用Woodbury恒等式可以計算出:

在實際應用中，需要給出各超參數(shù)初始值并根據(jù)(12)、(13)、(24)、(25)、(26)和(27)進行迭代計算。由文獻［16］，設初始值 β-1=0.01×var(y)。由文獻［11］可知，利用式(27)估計超參數(shù)v的重構(gòu)性要比v=0時差，所以將v固定為0。

通過上述等式，在每次迭代中都可以通過更新一個超參數(shù) γi來獲得迭代處理，并更新si，qi，u，Σ 。

3 仿真與結(jié)果分析

以下對所提出的基于貝葉斯壓縮感知BCS算法在 Matlab 中進行仿真，并與基于 OMP［17］、BP［18］壓縮重構(gòu)定位算法的性能進行定量比較和分析。

實驗將10 m×10 m的方形區(qū)域劃分為10×10個網(wǎng)格節(jié)點，并部署了7個無線接入點和隨機分布K個待測移動設備。每次測量時隨機選擇一個APi，將K個移動設備接收來自該APi的信號強度傳遞給中心服務器，共采集M次測量值形成 y=［y1y2...ym］T。仿真參數(shù)如表1所示。由文獻［19］可知，要用較少的測量值估計出移動設備的位置，N、M和K三者之間必須滿足M≥cKlb(N/K)，其中c是一個較小的常數(shù)。

表1 仿真實驗中使用的參數(shù)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，在相同環(huán)境下如取測量數(shù)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

下面針對測量數(shù)M、移動設備個數(shù)K與平均定位誤差分別對基于BCS、OMP和BP算法進行討論。

1)測量數(shù)與平均定位誤差的關系:取K=5，SNR=25 dB，當M從10～40變化時與平均定位誤差的關系如圖5所示。

圖5 平均定位誤差隨測量次數(shù)變化Fig.5 The average localization error changes along with the number of measurement

如圖5所示，平均定位誤差隨著測量次數(shù)增加而快速遞減。當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)移動設備數(shù)與定位誤差的關系:在相同實驗環(huán)境下，取M=35，SNR=25 dB，K分別為 5、6、7、8、9、10時與平均定位誤差關系如圖6所示。

圖6 平均定位誤差隨移動設備個數(shù)變化Fig.6 The average localization error changes along with the number of mobile devices

由圖6可發(fā)現(xiàn)隨著移動設備個數(shù)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%)。在測量數(shù)M=35時，BCS算法能在平均誤差0.5 m之內(nèi)定位10個移動設備。這與已知K=10，根據(jù)M≥Klb(N/K)算出M≈35相符合。

4 結(jié)束語

本文提出了將貝葉斯壓縮感知算法應用到無線網(wǎng)絡多移動設備定位的系統(tǒng)框架中，采用將拉普拉斯先驗模型與貝葉斯壓縮感知理論相結(jié)合的算法對多移動設備進行定位。壓縮感知理論根據(jù)信號稀疏性特征采用在線處理信號的方式，不僅節(jié)省采樣時間，還顯著地減少了節(jié)點能耗和通信開銷。相較于其他重構(gòu)算法，基于拉普拉斯先驗的貝葉斯壓縮感知具有重構(gòu)速度快、估計未知信號的同時獲得模型參數(shù)等特點，通過與OMP、BP算法的比較，可以發(fā)現(xiàn)該算法具有較高定位精確度和較低稀疏度要求。但該算法復雜度稍高，還需在后續(xù)工作中進一步開展降低計算復雜度的研究。

［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］何風行，余志軍，劉海濤.基于壓縮感知的無線傳感器網(wǎng)絡多目標定位算法［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，F(xiàn)AUL 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］.電路與系統(tǒng)學報，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.