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

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

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

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

1 系統(tǒng)模型

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

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

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

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

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

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

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

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)求最大值進(jìn)行超參數(shù)估計。使用最大化似然函數(shù)來求其最大值，有

式中:

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

使用最大邊緣似然函數(shù)估計超參數(shù)時，超參數(shù)更新需要計算后驗概率的協(xié)方差矩陣，矩陣求逆需要計算時間復(fù)雜度O(M3)和空間復(fù)雜度O(M2)。為了促進(jìn)稀疏性和減少計算需求，在每次迭代計算時只更新單個γ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)關(guān)于γi的導(dǎo)數(shù)的表達(dá)式可以寫為如下形式:

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

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

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

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

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

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

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

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

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

實驗中定位誤差的計算方法為［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)境下如取測量數(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è)備個數(shù)K與平均定位誤差分別對基于BCS、OMP和BP算法進(jìn)行討論。

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

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

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

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

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

由圖6可發(fā)現(xiàn)隨著移動設(shè)備個數(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個移動設(shè)備。這與已知K=10，根據(jù)M≥Klb(N/K)算出M≈35相符合。

4 結(jié)束語

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