基于壓縮感知的室內(nèi)多目標(biāo)無線定位算法*

任 進(jìn)，姬麗彬

(北方工業(yè)大學(xué) 信息學(xué)院，北京 100144)

0 引 言

自21世紀(jì)以來，隨著無線通信和信號處理技術(shù)的不斷進(jìn)步，無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network，WSN)[1]作為無線傳感技術(shù)的重要領(lǐng)域，正處在一個高速發(fā)展的階段。然而，節(jié)點能量受限是WSN技術(shù)發(fā)展與應(yīng)用所面臨的重要挑戰(zhàn)，因此，研究如何保證低功耗的情況下對目標(biāo)節(jié)點進(jìn)行高精度的定位成為一個熱點問題。

近年來，對于如何優(yōu)化WSN網(wǎng)絡(luò)中定位算法，國內(nèi)外學(xué)者進(jìn)行了很多研究。已有研究人員將壓縮感知(Compressed Sensing,CS)[2]技術(shù)與WSN相結(jié)合，利用 CS 技術(shù)降低信號的采集、傳輸、融合的能量消耗，同時實現(xiàn)網(wǎng)絡(luò)的定位，且取得了相應(yīng)的成果。文獻(xiàn)[3-7]將機器學(xué)習(xí)運用于無線定位中：Ji等人[3]利用二元蜂群算法與壓縮感知結(jié)合進(jìn)行定位，具有一定的智能性；李依純[4]利用提出的鄰域加強的二分 K-means 區(qū)域劃分算法，在離線階段對指紋庫區(qū)域進(jìn)行聚類劃分,通過提出的改進(jìn)的CS定位算法獲得定位坐標(biāo)；Zhao等人[5]提出一種結(jié)合貝葉斯壓縮感知理論和離線指紋數(shù)據(jù)庫的構(gòu)建方法，利用Co-Forest算法訓(xùn)練的隨機森林分類器的決策結(jié)果以及多數(shù)原則獲得定位結(jié)果，為用戶完成實時定位；Zhang等人[6]提出一種基于信號到達(dá)相位差(Phase Difference of Arrival,PDOA)和接收信號強度(Received Signal Strength,RSS)的人工神經(jīng)網(wǎng)絡(luò)(Artificial Neural Network,ANN)方案；劉夏等人[7]提出了一種利用模糊C均值聚類算法和模擬退火自適應(yīng)遺傳算法去優(yōu)化徑向基函數(shù)神經(jīng)網(wǎng)絡(luò)的室內(nèi)定位算法，顯著提高了傳統(tǒng)的徑向基函數(shù)神經(jīng)網(wǎng)絡(luò)定位精度。文獻(xiàn)[8-9]通過處理節(jié)點接收信號強度進(jìn)行優(yōu)化:Khan等人[8]將多個待定位節(jié)點的RSS值進(jìn)行疊加，再將壓縮的數(shù)據(jù)傳輸給信標(biāo)節(jié)點，減少了流量開銷；Yu等人[9]利用多個待定位節(jié)點接收到的信號強度差(Received Signal Strength Difference,RSSD)代替?zhèn)鹘y(tǒng)的RSS，提出一種基于接收信號強度差和壓縮感知的融合方法，減小終端異質(zhì)性帶來的影響。文獻(xiàn)[10-11]則通過改進(jìn)各類匹配追蹤(Matching Pursuit,MP)方法提高定位精度:Wu等人[10]提出利用階段式正交匹配追蹤算法(Stagewise Orthogonal Matching Pursuit,StOMP)提高運算速度，但造成了穩(wěn)定性的下降；Li等人[11]將基于Voronoi圖的貪婪匹配追蹤(Greedy Matching Pursuit,GMP)方法用于在局部分區(qū)中搜索候選網(wǎng)格，大大減少了時間復(fù)雜度。

本文同時考慮低功耗和高性能的要求，提出了一種改進(jìn)的基于貝葉斯壓縮感知(Bayesian Compressive Sensing,BCS)[12]的室內(nèi)多目標(biāo)定位算法。實驗仿真結(jié)果表明，與傳統(tǒng)的多目標(biāo)定位算法相比，本文算法在網(wǎng)絡(luò)模型中估計出的未知節(jié)點位置和最終未知節(jié)點位置更為相近，定位效果有了顯著提高，同時大大減少了系統(tǒng)的通信量。

1 貝葉斯壓縮感知理論

BCS算法由壓縮感知理論和稀疏貝葉斯學(xué)習(xí)(Sparse Bayesian Learning,SBL)[13]結(jié)合所得，它通過符合某種先驗分布的隨機向量，計算出信號的先驗概率進(jìn)而確定先驗分布；然后根據(jù)樣本信息，運用貝葉斯框架，計算最大后驗概率分布，得出信號的均值和方差，均值即為原信號恢復(fù)的估計值。

(1)

y實際上就是信號X在觀測矩陣Φ下的線性投影。

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

(2)

由于實際情況中存在噪聲的情況，所以公式(2)可進(jìn)一步表示為

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

(3)

(4)

廣泛應(yīng)用的稀疏先驗是拉普拉斯密度函數(shù)，然而，拉普拉斯密度函數(shù)的主要缺點是它無法共軛。 因此，我們考慮一個零均值的高斯先驗如下:

(5)

式中：α是N個獨立超參數(shù)的逆方差，即高斯先驗分布的精度。

假設(shè)α已知，我們的目的是估計參數(shù)S和σ2。那么給定α和y，將條件分布(4)與公式(5)中的先驗分布結(jié)合，通過貝葉斯準(zhǔn)則來描述S后驗條件概率并使其最大化，這樣就得到了

(6)

式中：S的后驗概率分布滿足均值為μ、協(xié)方差為Ω的多變量高斯分布，即

μ=σ-2ΩΘTy，

(7)

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

(8)

式中：Λ～diag{α1,α2,…,αN} 。因此，觀測值y的后驗密度函數(shù)是一個具有均值E[y]=Θμ和協(xié)方差Cov[y]=ΘΩΘT的多變量正態(tài)分布。

貝葉斯壓縮感知重構(gòu)算法的解釋如下：

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

(9)

式中：μi是由式(7)所得的第i個后驗平均權(quán)重。定義γi=1-αiΩii，Ωi1是式(8)中的對角線元素。對于噪聲方差σ2，

(10)

2 室內(nèi)多目標(biāo)定位的算法設(shè)計

室內(nèi)多目標(biāo)定位的過程如圖1所示。

圖1 室內(nèi)定位算法的流程示意圖

這一過程主要包含兩個階段，即離線階段和在線階段。

(1)處于離線階段時，無線接入點對定位區(qū)域內(nèi)的每個網(wǎng)格節(jié)點的坐標(biāo)位置進(jìn)行記錄從而構(gòu)建出該區(qū)域的位置指紋庫。首先，將被監(jiān)測區(qū)域均勻劃分為N個網(wǎng)格，對網(wǎng)格按照一定的順序進(jìn)行編號，本文按自左往右的順序編號，即N為網(wǎng)格的編號;將信標(biāo)節(jié)點自上往下進(jìn)行編號，M即表示區(qū)域中信標(biāo)節(jié)點的編號。M個信標(biāo)節(jié)點采集信息后構(gòu)建的位置指紋庫Φ∈RM×N(M<

(11)

(2)處于在線階段即定位階段時，通過被監(jiān)測區(qū)域信標(biāo)節(jié)點對位置節(jié)點距離信息進(jìn)行采集，并將這一測量值矩陣y上傳到中心服務(wù)器，中心服務(wù)器通過稀疏矩陣Ψ將上傳的這一系列數(shù)據(jù)進(jìn)行隨機亞采樣和信號重構(gòu)。由此，經(jīng)過一系列的轉(zhuǎn)換將多目標(biāo)定位問題轉(zhuǎn)換為稀疏信號重構(gòu)的問題。同時，考慮到實際定位區(qū)域存在噪聲，則上述過程可以通過公式表示為

(12)

最后，利用壓縮采樣所得的測量值矩陣y，離線階段所構(gòu)建出的位置指紋庫Φ和稀疏變換矩陣Ψ，通過以貝葉斯壓縮感知算法為基礎(chǔ)的定位算法進(jìn)行最大似然估計，進(jìn)而計算出稀疏信號位置向量S，查找信號中最大值的位序，將其對應(yīng)到位置指紋庫中，即可精確計算出未知節(jié)點的位置坐標(biāo)，有效實現(xiàn)定位的目的。

因此，本文的目的就是設(shè)計更加合理的稀疏變換基和觀測矩陣，在實現(xiàn)CS的兩個前提條件即稀疏性(sparsity)、不相關(guān)性(incoherence)的基礎(chǔ)上，實現(xiàn)更低的功耗和誤差。

3 改進(jìn)矩陣設(shè)計及分析

3.1 稀疏變換基

由于室內(nèi)環(huán)境中未知節(jié)點數(shù)量K遠(yuǎn)小于網(wǎng)格數(shù)量N(K<

(13)

式中：Ψ為N×N的單位矩陣。位置向量S在矩陣Ψ下的投影向量為

(14)

所以，向量X∈RN×K同樣具有稀疏性，并且具有可壓縮性，即矩陣中的大部分元素為0或接近于0。

3.2 觀測矩陣

3.2.1 節(jié)點連通性的判斷

傳統(tǒng)DV-Hop[14]算法采用距離矢量交換協(xié)議，監(jiān)控區(qū)域內(nèi)的所有節(jié)點均可獲得信標(biāo)節(jié)點的跳數(shù)信息，網(wǎng)絡(luò)規(guī)模越大則成本開銷亦越大,會造成較大的浪費。因此,我們的目標(biāo)是希望利用較少的通信量來做到更準(zhǔn)確的定位。

在這里，如果網(wǎng)絡(luò)中任意節(jié)點通過單跳路由均可和其他節(jié)點進(jìn)行信息交換，則網(wǎng)絡(luò)是連通的，進(jìn)行定位之前信標(biāo)節(jié)點向周圍以r為半徑的圓廣播一個消息，即利用公式(15)判斷節(jié)點之間的連通性，若第m個信標(biāo)節(jié)點和第n個網(wǎng)格節(jié)點之間的距離dm,n小于信標(biāo)節(jié)點的通信半徑R，則兩個節(jié)點之間可以直接通信(單跳)，連通性為1；否則無法通信，連通性為0，即

Distancem,n=dm,n

(15)

式中：第m個信標(biāo)節(jié)點和第n個網(wǎng)格的歐式距離dm,n為

(16)

通過合理設(shè)置信標(biāo)節(jié)點的通信半徑將定位區(qū)域等面積劃分，利用邊界框(Bounding-Box)思想將待定位節(jié)點位置縮小到某塊可能性區(qū)域，形成無縫覆蓋的網(wǎng)絡(luò)，最終構(gòu)造出全連通的網(wǎng)絡(luò)。

3.2.2 觀測矩陣分析

壓縮感知的關(guān)鍵是觀測矩陣的構(gòu)造，觀測矩陣性能的好壞直接影響恢復(fù)信號和原信號之間誤差的大小。CS理論大多采用隨機矩陣(例如高斯隨機矩陣)作為觀測矩陣，這類矩陣占用的存儲空間較大，且實際應(yīng)用中很難用硬件實現(xiàn)。本文選用確定性觀測矩陣，考慮用(通信半徑-距離)/通信半徑的算法進(jìn)行構(gòu)建確定性觀測矩陣。

當(dāng)節(jié)點之間連通時，觀測矩陣Φm,n被構(gòu)建為

(17)

當(dāng)節(jié)點之間連通性為0時，觀測矩陣Φm,n權(quán)重被設(shè)置為無窮小。

作為感知的前端，觀測矩陣主要有以下幾個評價標(biāo)準(zhǔn)：RIP、構(gòu)造計算復(fù)雜度、矩陣維數(shù)及重構(gòu)性能[15]。

(1)RIP：Baraniuk在文獻(xiàn)[16]中提出，RIP的等價條件為稀疏變換基Ψ與觀測矩陣Φ不相關(guān)。也就是說，Φ的行Φi不能由Ψ的列Ψj稀疏表示，同時Ψ的列Ψj不能由Φ的行Φi稀疏表示。由于信標(biāo)節(jié)點在網(wǎng)格中均勻分布，而稀疏變換基Ψ的列是一個一階稀疏的向量，顯然，本文所構(gòu)造的觀測矩陣和稀疏變換基有很強的不相關(guān)性。

(2)構(gòu)造復(fù)雜度：本文所構(gòu)建的確定性觀測矩陣為一次方程，通過簡單的數(shù)學(xué)運算即可得到。進(jìn)行存儲或者傳輸時，只需要存儲或者傳輸方程及參數(shù)，大大節(jié)省了存儲空間，傳輸效率也隨之提高，尤其在矩陣較大時，觀測矩陣的優(yōu)越性則更為明顯。

(3)矩陣維度：觀測矩陣的維數(shù)應(yīng)盡可能不受限制以適應(yīng)大面積的實際應(yīng)用，本文中M為信標(biāo)節(jié)點的個數(shù)，N為仿真范圍與步長之比的平方，矩陣的維度較為靈活。

(4)重構(gòu)性能：見下文對比圖。

4 實驗仿真與結(jié)果分析

本節(jié)對本文提出的改進(jìn)的基于貝葉斯壓縮感知的多目標(biāo)定位算法進(jìn)行仿真實驗，并分別與基于DV-Hop的最小二乘定位算法以及基于BCS、OMP的壓縮重構(gòu)算法進(jìn)行對比，驗證本文算法定位性能的優(yōu)越性；然后，分別從定位誤差和定位耗時兩方面研究網(wǎng)絡(luò)步長對定位效果的影響。

4.1 仿真場景

在Matlab平臺上進(jìn)行仿真實驗，具體參數(shù)設(shè)置如表1所示，定位區(qū)域設(shè)為100 m×100 m的方形區(qū)域，感知節(jié)點為151個，其中信標(biāo)節(jié)點為121個，其余為未知節(jié)點，信標(biāo)節(jié)點的通信半徑為15 m。

表1 仿真場景的參數(shù)設(shè)置

4.2 實驗結(jié)果及分析

考慮評價標(biāo)準(zhǔn)的普適性，采用絕對誤差和通信半徑的比值作為定位誤差d：

(18)

本文提出的改進(jìn)算法的效果如圖2所示。

圖2 實際位置和估計位置對比

圖3展示了未知節(jié)點進(jìn)入等面積劃分區(qū)域后，充滿隨機性，不像紅色信標(biāo)節(jié)點的坐標(biāo)均勻分布規(guī)則排列。通過將改進(jìn)的BCS預(yù)測出的未知節(jié)點位置坐標(biāo)與通過DV-hop算法、BCS算法、OMP算法預(yù)測出的位置進(jìn)行對比，可以直觀地看出改進(jìn)觀測矩陣的BCS算法預(yù)測定位效果最好，OMP、BCS算法效果次之，各自存在一定的缺陷，DV-hop算法最差，預(yù)測效果不夠理想。

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

由圖4可以得出，在同一通信半徑R=15 m時，DV-hop算法預(yù)測未知節(jié)點誤差百分比最大，預(yù)測位置與實際位置對比有明顯差距；BCS算法和OMP算法預(yù)測定位效果相差不大，定位誤差百分比均較低；改進(jìn)觀測矩陣的BCS的定位算法節(jié)點誤差最低，定位效果最優(yōu)。由表2可以得出，改進(jìn)的BCS算法波動最小，OMP的誤差波動不大，原BCS算法的預(yù)測誤差波動較大，穩(wěn)定性較差。圖4和表 2表明，改進(jìn)觀測矩陣后，BCS的定位精度明顯上升且誤差波動最低。

圖4 不同算法預(yù)測節(jié)點誤差對比

表2 不同算法預(yù)測節(jié)點的均方誤差

當(dāng)通信半徑為15 m時，在傳感器監(jiān)測區(qū)域內(nèi)，不同的歩長對定位算法的影響如圖5和圖6所示。

圖5 網(wǎng)絡(luò)步長對定位誤差的影響

圖6 網(wǎng)絡(luò)步長對定位耗時的影響

如圖5所示，當(dāng)網(wǎng)絡(luò)步長增大，可能性區(qū)域中的小方格數(shù)目減少，定位難度變大，所產(chǎn)生的定位誤差也就越大；在網(wǎng)絡(luò)步長為1～4 m時，步長為1.1 m左右定位誤差最小。從圖6可以看出，隨著網(wǎng)絡(luò)步長的增長，觀測矩陣的維度也在減少，通信量降低。利用不同算法進(jìn)行重構(gòu)時，算法計算量也相應(yīng)減少，整體上定位耗時隨網(wǎng)絡(luò)步長增大而減少。由此可見，步長的設(shè)置對定位效果影響較大。而本文設(shè)定為固定步長，在稀疏度未知的情況下靈活性較低。

5 結(jié)束語

為了解決當(dāng)前無線傳感器網(wǎng)絡(luò)都會存在的低功耗和高性能無法共存的問題，本文設(shè)計了一種基于壓縮感知的多目標(biāo)定位算法。改進(jìn)觀測矩陣后的BCS定位算法具有良好的重構(gòu)性能，實現(xiàn)了定位性能與節(jié)點能量的均衡考慮。而本文算法是針對靜態(tài)多目標(biāo)進(jìn)行研究的，在接下來的工作中，將進(jìn)一步對所提算法進(jìn)行改進(jìn)，應(yīng)用到動態(tài)目標(biāo)定位和稀疏度未知的情況中去，擴大適用范圍。