基于貝葉斯壓縮感知多目標(biāo)定位算法

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

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

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

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

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

1 系統(tǒng)模型

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

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

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

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

在線階段測(cè)量值y可表示為

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

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

2 稀疏貝葉斯模型

2.1 觀測(cè)模型

根據(jù)式(2)有

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

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

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

故有

對(duì)參數(shù)α使用Gamma超先驗(yàn)分布，得

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

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

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

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

式中:

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

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

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

利用行列式判別式，則有

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

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

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

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

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

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

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

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

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

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

表1 仿真實(shí)驗(yàn)中使用的參數(shù)Table 1 Parameters in the simulation

實(shí)驗(yàn)中定位誤差的計(jì)算方法為［7］

圖2 平均定位誤差與SNR的關(guān)系Fig.2 Average localization error versus SNR

圖3是K=5，M=25，SNR=25 dB的定位效果圖。通過仿真100次得到平均定位誤差為0.20 m。

如將K增加到10，在相同環(huán)境下如取測(cè)量數(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

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

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

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

如圖5所示，平均定位誤差隨著測(cè)量次數(shù)增加而快速遞減。當(dāng)M=25時(shí)，BCS和BP算法已可定位出移動(dòng)設(shè)備，這與Klb(N/K)≈25相符合。M較小時(shí)，BCS算法的平均定位誤差比BP算法大，但M值增加且當(dāng)M≥25時(shí)，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%)。當(dāng)M=30 時(shí)，BCS 算法能夠精確恢復(fù)移動(dòng)設(shè)備的位置，其精確度幾乎接近100%。

2)移動(dòng)設(shè)備數(shù)與定位誤差的關(guān)系:在相同實(shí)驗(yàn)環(huán)境下，取M=35，SNR=25 dB，K分別為 5、6、7、8、9、10時(shí)與平均定位誤差關(guān)系如圖6所示。

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

由圖6可發(fā)現(xiàn)隨著移動(dòng)設(shè)備個(gè)數(shù)K增加即信號(hào)稀疏度逐漸變差時(shí)，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%)。在測(cè)量數(shù)M=35時(shí)，BCS算法能在平均誤差0.5 m之內(nèi)定位10個(gè)移動(dòng)設(shè)備。這與已知K=10，根據(jù)M≥Klb(N/K)算出M≈35相符合。

4 結(jié)束語

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

［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］何風(fēng)行，余志軍，劉海濤.基于壓縮感知的無線傳感器網(wǎng)絡(luò)多目標(biāo)定位算法［J］.電子與信息學(xué)報(bào)，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］章堅(jiān)武，顏歡，包建榮.改進(jìn)的基于拉普拉斯先驗(yàn)的貝葉斯壓縮感知算法［J］.電路與系統(tǒng)學(xué)報(bào)，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］朱翠濤，瞿毅.基于壓縮感知的稀疏事件檢測(cè)［J］.中南民族大學(xué)學(xué)報(bào):自然科學(xué)版，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.