任 進(jìn),姬麗彬
(北方工業(yè)大學(xué) 信息學(xué)院,北京 100144)
自21世紀(jì)以來,隨著無線通信和信號(hào)處理技術(shù)的不斷進(jìn)步,無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network,WSN)[1]作為無線傳感技術(shù)的重要領(lǐng)域,正處在一個(gè)高速發(fā)展的階段。然而,節(jié)點(diǎn)能量受限是WSN技術(shù)發(fā)展與應(yīng)用所面臨的重要挑戰(zhàn),因此,研究如何保證低功耗的情況下對(duì)目標(biāo)節(jié)點(diǎn)進(jìn)行高精度的定位成為一個(gè)熱點(diǎn)問題。
近年來,對(duì)于如何優(yōu)化WSN網(wǎng)絡(luò)中定位算法,國(guó)內(nèi)外學(xué)者進(jìn)行了很多研究。已有研究人員將壓縮感知(Compressed Sensing,CS)[2]技術(shù)與WSN相結(jié)合,利用 CS 技術(shù)降低信號(hào)的采集、傳輸、融合的能量消耗,同時(shí)實(shí)現(xiàn)網(wǎng)絡(luò)的定位,且取得了相應(yīng)的成果。文獻(xiàn)[3-7]將機(jī)器學(xué)習(xí)運(yùn)用于無線定位中:Ji等人[3]利用二元蜂群算法與壓縮感知結(jié)合進(jìn)行定位,具有一定的智能性;李依純[4]利用提出的鄰域加強(qiáng)的二分 K-means 區(qū)域劃分算法,在離線階段對(duì)指紋庫區(qū)域進(jìn)行聚類劃分,通過提出的改進(jìn)的CS定位算法獲得定位坐標(biāo);Zhao等人[5]提出一種結(jié)合貝葉斯壓縮感知理論和離線指紋數(shù)據(jù)庫的構(gòu)建方法,利用Co-Forest算法訓(xùn)練的隨機(jī)森林分類器的決策結(jié)果以及多數(shù)原則獲得定位結(jié)果,為用戶完成實(shí)時(shí)定位;Zhang等人[6]提出一種基于信號(hào)到達(dá)相位差(Phase Difference of Arrival,PDOA)和接收信號(hào)強(qiáng)度(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é)點(diǎn)接收信號(hào)強(qiáng)度進(jìn)行優(yōu)化:Khan等人[8]將多個(gè)待定位節(jié)點(diǎn)的RSS值進(jìn)行疊加,再將壓縮的數(shù)據(jù)傳輸給信標(biāo)節(jié)點(diǎn),減少了流量開銷;Yu等人[9]利用多個(gè)待定位節(jié)點(diǎn)接收到的信號(hào)強(qiáng)度差(Received Signal Strength Difference,RSSD)代替?zhèn)鹘y(tǒng)的RSS,提出一種基于接收信號(hào)強(qiáng)度差和壓縮感知的融合方法,減小終端異質(zhì)性帶來的影響。文獻(xiàn)[10-11]則通過改進(jìn)各類匹配追蹤(Matching Pursuit,MP)方法提高定位精度:Wu等人[10]提出利用階段式正交匹配追蹤算法(Stagewise Orthogonal Matching Pursuit,StOMP)提高運(yùn)算速度,但造成了穩(wěn)定性的下降;Li等人[11]將基于Voronoi圖的貪婪匹配追蹤(Greedy Matching Pursuit,GMP)方法用于在局部分區(qū)中搜索候選網(wǎng)格,大大減少了時(shí)間復(fù)雜度。
本文同時(shí)考慮低功耗和高性能的要求,提出了一種改進(jìn)的基于貝葉斯壓縮感知(Bayesian Compressive Sensing,BCS)[12]的室內(nèi)多目標(biāo)定位算法。實(shí)驗(yàn)仿真結(jié)果表明,與傳統(tǒng)的多目標(biāo)定位算法相比,本文算法在網(wǎng)絡(luò)模型中估計(jì)出的未知節(jié)點(diǎn)位置和最終未知節(jié)點(diǎn)位置更為相近,定位效果有了顯著提高,同時(shí)大大減少了系統(tǒng)的通信量。
BCS算法由壓縮感知理論和稀疏貝葉斯學(xué)習(xí)(Sparse Bayesian Learning,SBL)[13]結(jié)合所得,它通過符合某種先驗(yàn)分布的隨機(jī)向量,計(jì)算出信號(hào)的先驗(yàn)概率進(jìn)而確定先驗(yàn)分布;然后根據(jù)樣本信息,運(yùn)用貝葉斯框架,計(jì)算最大后驗(yàn)概率分布,得出信號(hào)的均值和方差,均值即為原信號(hào)恢復(fù)的估計(jì)值。
(1)
y實(shí)際上就是信號(hào)X在觀測(cè)矩陣Φ下的線性投影。
y=ΦX=ΦΨS=ΘS。
(2)
由于實(shí)際情況中存在噪聲的情況,所以公式(2)可進(jìn)一步表示為
y=ΦX+n=ΘS+n。
(3)
(4)
廣泛應(yīng)用的稀疏先驗(yàn)是拉普拉斯密度函數(shù),然而,拉普拉斯密度函數(shù)的主要缺點(diǎn)是它無法共軛。 因此,我們考慮一個(gè)零均值的高斯先驗(yàn)如下:
(5)
式中:α是N個(gè)獨(dú)立超參數(shù)的逆方差,即高斯先驗(yàn)分布的精度。
假設(shè)α已知,我們的目的是估計(jì)參數(shù)S和σ2。那么給定α和y,將條件分布(4)與公式(5)中的先驗(yàn)分布結(jié)合,通過貝葉斯準(zhǔn)則來描述S后驗(yàn)條件概率并使其最大化,這樣就得到了
(6)
式中:S的后驗(yàn)概率分布滿足均值為μ、協(xié)方差為Ω的多變量高斯分布,即
μ=σ-2ΩΘTy,
(7)
Ω=(Λ+σ-2ΘTΘ)-1。
(8)
式中:Λ~diag{α1,α2,…,αN} 。因此,觀測(cè)值y的后驗(yàn)密度函數(shù)是一個(gè)具有均值E[y]=Θμ和協(xié)方差Cov[y]=ΘΩΘT的多變量正態(tài)分布。
貝葉斯壓縮感知重構(gòu)算法的解釋如下:
Step2 由于yl和Θ已知,使用公式(7)和(8)計(jì)算yl的均值μ和協(xié)方差Ω。
(9)
式中:μi是由式(7)所得的第i個(gè)后驗(yàn)平均權(quán)重。定義γi=1-αiΩii,Ωi1是式(8)中的對(duì)角線元素。對(duì)于噪聲方差σ2,
(10)
室內(nèi)多目標(biāo)定位的過程如圖1所示。
圖1 室內(nèi)定位算法的流程示意圖
這一過程主要包含兩個(gè)階段,即離線階段和在線階段。
(1)處于離線階段時(shí),無線接入點(diǎn)對(duì)定位區(qū)域內(nèi)的每個(gè)網(wǎng)格節(jié)點(diǎn)的坐標(biāo)位置進(jìn)行記錄從而構(gòu)建出該區(qū)域的位置指紋庫。首先,將被監(jiān)測(cè)區(qū)域均勻劃分為N個(gè)網(wǎng)格,對(duì)網(wǎng)格按照一定的順序進(jìn)行編號(hào),本文按自左往右的順序編號(hào),即N為網(wǎng)格的編號(hào);將信標(biāo)節(jié)點(diǎn)自上往下進(jìn)行編號(hào),M即表示區(qū)域中信標(biāo)節(jié)點(diǎn)的編號(hào)。M個(gè)信標(biāo)節(jié)點(diǎn)采集信息后構(gòu)建的位置指紋庫Φ∈RM×N(M< (11) (2)處于在線階段即定位階段時(shí),通過被監(jiān)測(cè)區(qū)域信標(biāo)節(jié)點(diǎn)對(duì)位置節(jié)點(diǎn)距離信息進(jìn)行采集,并將這一測(cè)量值矩陣y上傳到中心服務(wù)器,中心服務(wù)器通過稀疏矩陣Ψ將上傳的這一系列數(shù)據(jù)進(jìn)行隨機(jī)亞采樣和信號(hào)重構(gòu)。由此,經(jīng)過一系列的轉(zhuǎn)換將多目標(biāo)定位問題轉(zhuǎn)換為稀疏信號(hào)重構(gòu)的問題。同時(shí),考慮到實(shí)際定位區(qū)域存在噪聲,則上述過程可以通過公式表示為 (12) 最后,利用壓縮采樣所得的測(cè)量值矩陣y,離線階段所構(gòu)建出的位置指紋庫Φ和稀疏變換矩陣Ψ,通過以貝葉斯壓縮感知算法為基礎(chǔ)的定位算法進(jìn)行最大似然估計(jì),進(jìn)而計(jì)算出稀疏信號(hào)位置向量S,查找信號(hào)中最大值的位序,將其對(duì)應(yīng)到位置指紋庫中,即可精確計(jì)算出未知節(jié)點(diǎn)的位置坐標(biāo),有效實(shí)現(xiàn)定位的目的。 因此,本文的目的就是設(shè)計(jì)更加合理的稀疏變換基和觀測(cè)矩陣,在實(shí)現(xiàn)CS的兩個(gè)前提條件即稀疏性(sparsity)、不相關(guān)性(incoherence)的基礎(chǔ)上,實(shí)現(xiàn)更低的功耗和誤差。 由于室內(nèi)環(huán)境中未知節(jié)點(diǎn)數(shù)量K遠(yuǎn)小于網(wǎng)格數(shù)量N(K< (13) 式中:Ψ為N×N的單位矩陣。位置向量S在矩陣Ψ下的投影向量為 (14) 所以,向量X∈RN×K同樣具有稀疏性,并且具有可壓縮性,即矩陣中的大部分元素為0或接近于0。 3.2.1 節(jié)點(diǎn)連通性的判斷 傳統(tǒng)DV-Hop[14]算法采用距離矢量交換協(xié)議,監(jiān)控區(qū)域內(nèi)的所有節(jié)點(diǎn)均可獲得信標(biāo)節(jié)點(diǎn)的跳數(shù)信息,網(wǎng)絡(luò)規(guī)模越大則成本開銷亦越大,會(huì)造成較大的浪費(fèi)。因此,我們的目標(biāo)是希望利用較少的通信量來做到更準(zhǔn)確的定位。 在這里,如果網(wǎng)絡(luò)中任意節(jié)點(diǎn)通過單跳路由均可和其他節(jié)點(diǎn)進(jìn)行信息交換,則網(wǎng)絡(luò)是連通的,進(jìn)行定位之前信標(biāo)節(jié)點(diǎn)向周圍以r為半徑的圓廣播一個(gè)消息,即利用公式(15)判斷節(jié)點(diǎn)之間的連通性,若第m個(gè)信標(biāo)節(jié)點(diǎn)和第n個(gè)網(wǎng)格節(jié)點(diǎn)之間的距離dm,n小于信標(biāo)節(jié)點(diǎn)的通信半徑R,則兩個(gè)節(jié)點(diǎn)之間可以直接通信(單跳),連通性為1;否則無法通信,連通性為0,即 Distancem,n=dm,n (15) 式中:第m個(gè)信標(biāo)節(jié)點(diǎn)和第n個(gè)網(wǎng)格的歐式距離dm,n為 (16) 通過合理設(shè)置信標(biāo)節(jié)點(diǎn)的通信半徑將定位區(qū)域等面積劃分,利用邊界框(Bounding-Box)思想將待定位節(jié)點(diǎn)位置縮小到某塊可能性區(qū)域,形成無縫覆蓋的網(wǎng)絡(luò),最終構(gòu)造出全連通的網(wǎng)絡(luò)。 3.2.2 觀測(cè)矩陣分析 壓縮感知的關(guān)鍵是觀測(cè)矩陣的構(gòu)造,觀測(cè)矩陣性能的好壞直接影響恢復(fù)信號(hào)和原信號(hào)之間誤差的大小。CS理論大多采用隨機(jī)矩陣(例如高斯隨機(jī)矩陣)作為觀測(cè)矩陣,這類矩陣占用的存儲(chǔ)空間較大,且實(shí)際應(yīng)用中很難用硬件實(shí)現(xiàn)。本文選用確定性觀測(cè)矩陣,考慮用(通信半徑-距離)/通信半徑的算法進(jìn)行構(gòu)建確定性觀測(cè)矩陣。 當(dāng)節(jié)點(diǎn)之間連通時(shí),觀測(cè)矩陣Φm,n被構(gòu)建為 (17) 當(dāng)節(jié)點(diǎn)之間連通性為0時(shí),觀測(cè)矩陣Φm,n權(quán)重被設(shè)置為無窮小。 作為感知的前端,觀測(cè)矩陣主要有以下幾個(gè)評(píng)價(jià)標(biāo)準(zhǔn):RIP、構(gòu)造計(jì)算復(fù)雜度、矩陣維數(shù)及重構(gòu)性能[15]。 (1)RIP:Baraniuk在文獻(xiàn)[16]中提出,RIP的等價(jià)條件為稀疏變換基Ψ與觀測(cè)矩陣Φ不相關(guān)。也就是說,Φ的行Φi不能由Ψ的列Ψj稀疏表示,同時(shí)Ψ的列Ψj不能由Φ的行Φi稀疏表示。由于信標(biāo)節(jié)點(diǎn)在網(wǎng)格中均勻分布,而稀疏變換基Ψ的列是一個(gè)一階稀疏的向量,顯然,本文所構(gòu)造的觀測(cè)矩陣和稀疏變換基有很強(qiáng)的不相關(guān)性。 (2)構(gòu)造復(fù)雜度:本文所構(gòu)建的確定性觀測(cè)矩陣為一次方程,通過簡(jiǎn)單的數(shù)學(xué)運(yùn)算即可得到。進(jìn)行存儲(chǔ)或者傳輸時(shí),只需要存儲(chǔ)或者傳輸方程及參數(shù),大大節(jié)省了存儲(chǔ)空間,傳輸效率也隨之提高,尤其在矩陣較大時(shí),觀測(cè)矩陣的優(yōu)越性則更為明顯。 (3)矩陣維度:觀測(cè)矩陣的維數(shù)應(yīng)盡可能不受限制以適應(yīng)大面積的實(shí)際應(yīng)用,本文中M為信標(biāo)節(jié)點(diǎn)的個(gè)數(shù),N為仿真范圍與步長(zhǎng)之比的平方,矩陣的維度較為靈活。 (4)重構(gòu)性能:見下文對(duì)比圖。 本節(jié)對(duì)本文提出的改進(jìn)的基于貝葉斯壓縮感知的多目標(biāo)定位算法進(jìn)行仿真實(shí)驗(yàn),并分別與基于DV-Hop的最小二乘定位算法以及基于BCS、OMP的壓縮重構(gòu)算法進(jìn)行對(duì)比,驗(yàn)證本文算法定位性能的優(yōu)越性;然后,分別從定位誤差和定位耗時(shí)兩方面研究網(wǎng)絡(luò)步長(zhǎng)對(duì)定位效果的影響。 在Matlab平臺(tái)上進(jìn)行仿真實(shí)驗(yàn),具體參數(shù)設(shè)置如表1所示,定位區(qū)域設(shè)為100 m×100 m的方形區(qū)域,感知節(jié)點(diǎn)為151個(gè),其中信標(biāo)節(jié)點(diǎn)為121個(gè),其余為未知節(jié)點(diǎn),信標(biāo)節(jié)點(diǎn)的通信半徑為15 m。 表1 仿真場(chǎng)景的參數(shù)設(shè)置 考慮評(píng)價(jià)標(biāo)準(zhǔn)的普適性,采用絕對(duì)誤差和通信半徑的比值作為定位誤差d: (18) 本文提出的改進(jìn)算法的效果如圖2所示。 圖2 實(shí)際位置和估計(jì)位置對(duì)比 圖3展示了未知節(jié)點(diǎn)進(jìn)入等面積劃分區(qū)域后,充滿隨機(jī)性,不像紅色信標(biāo)節(jié)點(diǎn)的坐標(biāo)均勻分布規(guī)則排列。通過將改進(jìn)的BCS預(yù)測(cè)出的未知節(jié)點(diǎn)位置坐標(biāo)與通過DV-hop算法、BCS算法、OMP算法預(yù)測(cè)出的位置進(jìn)行對(duì)比,可以直觀地看出改進(jìn)觀測(cè)矩陣的BCS算法預(yù)測(cè)定位效果最好,OMP、BCS算法效果次之,各自存在一定的缺陷,DV-hop算法最差,預(yù)測(cè)效果不夠理想。 圖3 不同算法的定位效果圖 由圖4可以得出,在同一通信半徑R=15 m時(shí),DV-hop算法預(yù)測(cè)未知節(jié)點(diǎn)誤差百分比最大,預(yù)測(cè)位置與實(shí)際位置對(duì)比有明顯差距;BCS算法和OMP算法預(yù)測(cè)定位效果相差不大,定位誤差百分比均較低;改進(jìn)觀測(cè)矩陣的BCS的定位算法節(jié)點(diǎn)誤差最低,定位效果最優(yōu)。由表2可以得出,改進(jìn)的BCS算法波動(dòng)最小,OMP的誤差波動(dòng)不大,原BCS算法的預(yù)測(cè)誤差波動(dòng)較大,穩(wěn)定性較差。圖4和表 2表明,改進(jìn)觀測(cè)矩陣后,BCS的定位精度明顯上升且誤差波動(dòng)最低。 圖4 不同算法預(yù)測(cè)節(jié)點(diǎn)誤差對(duì)比 表2 不同算法預(yù)測(cè)節(jié)點(diǎn)的均方誤差 當(dāng)通信半徑為15 m時(shí),在傳感器監(jiān)測(cè)區(qū)域內(nèi),不同的歩長(zhǎng)對(duì)定位算法的影響如圖5和圖6所示。 圖5 網(wǎng)絡(luò)步長(zhǎng)對(duì)定位誤差的影響 圖6 網(wǎng)絡(luò)步長(zhǎng)對(duì)定位耗時(shí)的影響 如圖5所示,當(dāng)網(wǎng)絡(luò)步長(zhǎng)增大,可能性區(qū)域中的小方格數(shù)目減少,定位難度變大,所產(chǎn)生的定位誤差也就越大;在網(wǎng)絡(luò)步長(zhǎng)為1~4 m時(shí),步長(zhǎng)為1.1 m左右定位誤差最小。從圖6可以看出,隨著網(wǎng)絡(luò)步長(zhǎng)的增長(zhǎng),觀測(cè)矩陣的維度也在減少,通信量降低。利用不同算法進(jìn)行重構(gòu)時(shí),算法計(jì)算量也相應(yīng)減少,整體上定位耗時(shí)隨網(wǎng)絡(luò)步長(zhǎng)增大而減少。由此可見,步長(zhǎng)的設(shè)置對(duì)定位效果影響較大。而本文設(shè)定為固定步長(zhǎng),在稀疏度未知的情況下靈活性較低。 為了解決當(dāng)前無線傳感器網(wǎng)絡(luò)都會(huì)存在的低功耗和高性能無法共存的問題,本文設(shè)計(jì)了一種基于壓縮感知的多目標(biāo)定位算法。改進(jìn)觀測(cè)矩陣后的BCS定位算法具有良好的重構(gòu)性能,實(shí)現(xiàn)了定位性能與節(jié)點(diǎn)能量的均衡考慮。而本文算法是針對(duì)靜態(tài)多目標(biāo)進(jìn)行研究的,在接下來的工作中,將進(jìn)一步對(duì)所提算法進(jìn)行改進(jìn),應(yīng)用到動(dòng)態(tài)目標(biāo)定位和稀疏度未知的情況中去,擴(kuò)大適用范圍。3 改進(jìn)矩陣設(shè)計(jì)及分析
3.1 稀疏變換基
3.2 觀測(cè)矩陣
4 實(shí)驗(yàn)仿真與結(jié)果分析
4.1 仿真場(chǎng)景
4.2 實(shí)驗(yàn)結(jié)果及分析
5 結(jié)束語