金杰 柯煒,2 陸俊 王彥力 唐萬春,2

(1.南京師范大學(xué)物理科學(xué)與技術(shù)學(xué)院,南京 210023;

2. 江蘇省地理信息資源開發(fā)與利用協(xié)同創(chuàng)新中心,南京 210023)

引 言

無設(shè)備目標(biāo)定位(device-free localization, DFL)一般是通過在待檢測區(qū)域周圍設(shè)置若干無線收發(fā)節(jié)點(diǎn)來實(shí)現(xiàn)．無線節(jié)點(diǎn)間能夠相互通信,在空間內(nèi)形成許多無線鏈路,當(dāng)一個目標(biāo)進(jìn)入該區(qū)域,便會衰減一部分鏈路,相應(yīng)的這一部分鏈路的接收信號強(qiáng)度(received signal strength,RSS)值也會發(fā)生變化．因此,可以通過RSS值的變化來獲得目標(biāo)的位置信息．文獻(xiàn)[2-3]中將DFL問題建模成一個機(jī)器學(xué)習(xí)問題并通過指紋匹配的方法將其成功解決,它通過當(dāng)前鏈路測量值與訓(xùn)練數(shù)據(jù)庫進(jìn)行比較來估計(jì)目標(biāo)位置．受計(jì)算層析成像算法的啟發(fā),文獻(xiàn)[4-7]中將DFL問題轉(zhuǎn)換成無線電層析成像問題,并使用正則化的方法進(jìn)行求解．隨后,Wang J等人將DFL推廣到多維測量條件[8],并通過改進(jìn)陰影衰減模型進(jìn)一步提高了DFL的定位精度[9-11]．常儷瓊等人針對環(huán)境噪聲對鏈路接收信號的影響提出了一種能夠有效消除環(huán)境噪聲的DFL方法[12];劉凱等人也就射頻層析成像(radio tomographic imaging, RTI)方法的實(shí)時性問題提出了自己的改進(jìn)方法[13]．

隨著壓縮感知(compressive sensing,CS)[14-15]的迅速發(fā)展,根據(jù)目標(biāo)的空間稀疏性,文獻(xiàn)[16]將DFL成功建模成一個稀疏信號重建問題并提出了一種貪婪匹配追蹤(greedy matching pursuit, GMP)算法來解決．GMP算法通過排查部署區(qū)域里所有位置來確定目標(biāo),但是如果部署區(qū)域太大,其計(jì)算復(fù)雜度也會大大提高,并不適用于實(shí)時定位．在GMP的基礎(chǔ)上,文獻(xiàn)[17]提出了貝葉斯貪婪匹配追蹤(Bayesian greedy matching pursuit, BGMP)算法,充分利用先驗(yàn)條件加速了算法并過濾了部分誤差位置,在運(yùn)算速度和定位精度上都有了一定提高．

上述這些方法雖都成功地將CS應(yīng)用到DFL,但由于CS模型中所采用的權(quán)重字典都是基于經(jīng)驗(yàn)?zāi)Ｐ蜆?gòu)建,與實(shí)際情況往往存在偏差,所以定位性能達(dá)不到預(yù)期的效果．針對權(quán)重字典的模型誤差,文獻(xiàn)[18-19]都提出了采用字典學(xué)習(xí)的算法來糾正原權(quán)重字典的模型誤差．

此外,在DFL求解目標(biāo)位置時,傳統(tǒng)做法是將無線傳感網(wǎng)中的所有鏈路的變化情況都考慮進(jìn)計(jì)算,然而實(shí)際情況是目標(biāo)僅會遮擋、衰減一部分的鏈路．如果計(jì)算所有鏈路的變化情況不僅會導(dǎo)致冗余的計(jì)算步驟,影響DFL系統(tǒng)的實(shí)時性,而且也會因?yàn)橛?jì)算誤差的累積和“無關(guān)”鏈路的擾動誤差導(dǎo)致定位誤差．

本文針對上述兩方面問題,提出了一種基于鏈路選擇學(xué)習(xí)(link selection learning,LSL)的DFL算法．不同于文獻(xiàn)[18-19]中的字典學(xué)習(xí)方法,該算法在更新字典的過程中,不僅糾正了原權(quán)重字典的模型誤差,而且結(jié)合位置的物理空間信息,完成了有效鏈路選取,實(shí)現(xiàn)了對字典維數(shù)的壓縮以及對野值目標(biāo)位置的過濾．

1 系統(tǒng)模型及問題描述

本節(jié),我們首先介紹將RSS測量值與目標(biāo)空間位置關(guān)聯(lián)起來的CS系統(tǒng)模型,再討論字典不匹配以及鏈路選取問題．

1.1 系統(tǒng)模型

假設(shè)定位區(qū)域周圍布置了L個無線節(jié)點(diǎn),并且將定位區(qū)域劃分為N個網(wǎng)格,可以形象地將這些網(wǎng)格稱為“像素”．假設(shè)區(qū)域中有K個待檢測目標(biāo),如果網(wǎng)格足夠密集,那么每一個目標(biāo)都可以保證有一個像素點(diǎn)與它對應(yīng)．如果K?N,離散空間域中的目標(biāo)位置可以精確地表示為稀疏向量x．如果目標(biāo)位于定位區(qū)域的相應(yīng)位置,向量x中對應(yīng)位置的元素則有非零值,而向量x中其他元素等于零．如上所述,可將DFL轉(zhuǎn)換為在稀疏向量x中確定非零元素及其特定位置的問題．則稀疏定位模型可以表示為

y=Dx+n．

(1)

式中:y是RSS測量值向量;D為權(quán)重字典;n為測量噪聲．傳統(tǒng)的做法是通過經(jīng)驗(yàn)?zāi)Ｐ蜆?gòu)建固定的權(quán)重字典D,再通過CS重構(gòu)算法求解稀疏向量x,從而得到目標(biāo)的位置信息．

1.2 問題描述

對于DFL問題中的權(quán)重字典,傳統(tǒng)做法都采用一個固定的模型來描述．最常用的為橢圓模型[4],該模型假設(shè)目標(biāo)只對鏈路所在直線為直徑的橢圓區(qū)域產(chǎn)生影響,當(dāng)像素中心到兩個節(jié)點(diǎn)的距離的和大于橢圓直徑加上短軸長度時,判斷該像素有權(quán)值．根據(jù)該方法,權(quán)重字典中的元素Dij可表示為

(2)

式中:dij為節(jié)點(diǎn)i到節(jié)點(diǎn)j的距離;di、dj分別為像素中心到節(jié)點(diǎn)i和節(jié)點(diǎn)j的距離;ρ為橢圓的短軸長．該模型假設(shè)權(quán)重值與鏈路的長度成反比,缺乏理論依據(jù),并且一個橢圓內(nèi)所有格點(diǎn)對應(yīng)的權(quán)重相同也不符合實(shí)際．因此,基于橢圓模型構(gòu)造的字典D與實(shí)際字典D0之間不可避免地存在誤差．為清楚起見,用一個誤差字典矩陣Γ來描述數(shù)學(xué)解析字典與理想字典之間的差異,則CS框架下的稀疏定位模型可以表述為

y=Dx+n=(D0+Γ)x+n．

(3)

值得注意的是,誤差矩陣Γ不僅是未知的,而且隨著時間和環(huán)境的變化而變化．由于模型字典D與理想字典D0之間存在不匹配,所以在稀疏恢復(fù)過程中出現(xiàn)誤差是不可避免的．為了獲得準(zhǔn)確的定位結(jié)果,本文算法采用自學(xué)習(xí)的方式來訓(xùn)練字典,減輕模型誤差．

在解決DFL問題時,如何選擇受到目標(biāo)影響的有效鏈路也是影響定位結(jié)果的一個重要因素．傳統(tǒng)的做法是考慮無線傳感網(wǎng)(wireless sensor network, WSN)中所有鏈路的變化情況,如參考文獻(xiàn)[4-7],或者為了滿足CS扁矩陣的要求,隨機(jī)選取一定的鏈路數(shù)參與計(jì)算[16]．考慮所有鏈路的變化情況,不僅會導(dǎo)致冗余的計(jì)算步驟,影響DFL系統(tǒng)的實(shí)時性,而且也會因?yàn)橛?jì)算誤差的累積和“無關(guān)”鏈路的擾動誤差導(dǎo)致定位誤差．而隨機(jī)選取一定的鏈路參與計(jì)算,則會因?yàn)橛袝r鏈路選擇的不準(zhǔn)確性,導(dǎo)致較大的定位誤差．為了規(guī)避兩種鏈路處理方法的弊端,本文算法根據(jù)移動目標(biāo)的位置相關(guān)性,在字典更新的同時,完成對參與計(jì)算鏈路的選取,不僅壓縮了字典維度,加速了算法,而且也濾除了部分野值目標(biāo)位置．

2 LSL算法

本節(jié)詳細(xì)介紹LSL算法,算法包括兩個階段:訓(xùn)練階段和定位階段,如圖1所示．在訓(xùn)練階段中我們同時完成字典更新以及鏈路選擇,得到降維后的匹配字典;在定位階段,使用修正后的匹配字典作為權(quán)重矩陣,進(jìn)行稀疏重構(gòu)．

圖1 LSL算法流程圖Fig.1 Flowchart of LSL algorithm

2.1 訓(xùn)練階段

2.1.1 字典學(xué)習(xí)

1996年,Olshausen發(fā)表了著名的Sparsenet字典學(xué)習(xí)算法[20],該算法奠定了字典學(xué)習(xí)理論的基礎(chǔ),隨后許多改進(jìn)的字典學(xué)習(xí)算法也相繼出現(xiàn)了．Lee等提高了Olshausen字典學(xué)習(xí)算法的速度[21];受廣義聚類算法的啟發(fā),Engan等對Olshausen的Sparsenet字典學(xué)習(xí)算法進(jìn)行了改進(jìn),提出了最優(yōu)方向(method of optimal directions, MOD)字典學(xué)習(xí)算法[22];為減小MOD算法的復(fù)雜度,Aharon等又提出了逐列更新字典的KSVD算法[23]．本文借鑒上述字典學(xué)習(xí)的思路,對模型字典進(jìn)行更新．

由于有L個無線節(jié)點(diǎn),一共可以組成M=(L-1)L/2條無線鏈路,這意味著一次測量可以得到M維的測量矢量yi=[y1,y2,…,yM]T．考慮到訓(xùn)練要求,我們一共采集P個這樣的測量矢量,組成訓(xùn)練矩陣Y;其對應(yīng)的稀疏矢量xi(i=1,2,…,P)組成稀疏矩陣X．根據(jù)字典學(xué)習(xí)理論,要尋找權(quán)重字典的最優(yōu)表示D,我們僅需求解

(4)

(5)

圖2 LSL算法字典學(xué)習(xí)階段流程Fig.2 Dictionary learning stage process of LSL algorithm

式(5)中,DX被分解為N個秩為1的矩陣的和,假設(shè)其中N-1項(xiàng)都是固定的,剩下的第n列就是需要處理更新的．矩陣En表示去掉原子dn的成分在所有N個樣本中造成的誤差,稱為誤差矩陣,如下所示:

(6)

(7)

(8)

2.1.2 鏈路選取

為了加速字典學(xué)習(xí)過程,同時消除野值鏈路的影響,提出一種鏈路選取方法．根據(jù)移動目標(biāo)的時空相關(guān)性,可以依據(jù)目標(biāo)上一時刻位置來判定下一時刻目標(biāo)可能出現(xiàn)的區(qū)域,僅選取通過該先驗(yàn)區(qū)域中的鏈路參與計(jì)算．

假設(shè)目標(biāo)初始位置位于像素j處,下一時刻目標(biāo)可能出現(xiàn)的位置一定是在以像素j為圓心,半徑為h的圓內(nèi)．半徑h設(shè)置如下:

h=Vmax×tint．

(9)

式中:Vmax為定位目標(biāo)的最大速度;tint為兩次定位算法運(yùn)行的時間間隔．由于目標(biāo)只可能出現(xiàn)在先驗(yàn)區(qū)域內(nèi),因此只有經(jīng)過先驗(yàn)區(qū)域的鏈路才可能真正被目標(biāo)所影響．為了判斷鏈路是否經(jīng)過置信區(qū)域,可以將鏈路看作一條直線,于是上述問題便轉(zhuǎn)化為直線是否經(jīng)過圓的數(shù)學(xué)問題．如圖3中節(jié)點(diǎn)6到節(jié)點(diǎn)19的鏈路所示,要判斷該條鏈路是否經(jīng)過置信區(qū)域,只需判斷圓心到直線的距離H是否小于圓的半徑h．由于在DFL問題中,像素點(diǎn)到無線節(jié)點(diǎn)的距離及無線節(jié)點(diǎn)間的距離都是容易獲得的,因此對于這個問題我們可以根據(jù)海倫公式和三角形面積公式很方便地求得H,即

(10)

式中:a、b、c為三角形的三邊長;p為三角形的半周長;H為三角形c邊上的高．凡是滿足H

但對于邊界鏈路,這種判定方法會產(chǎn)生誤判,如圖3中節(jié)點(diǎn)4到節(jié)點(diǎn)5的鏈路所示．從圖上直觀地看到,從先驗(yàn)區(qū)域圓心處到無線節(jié)點(diǎn)4、5之間鏈路所在直線的垂直距離明顯小于先驗(yàn)區(qū)域半徑,但節(jié)點(diǎn)4到節(jié)點(diǎn)5這條鏈路卻不經(jīng)過先驗(yàn)區(qū)域．不過,由于DFL通常只考慮邊界內(nèi)的目標(biāo)定位,目標(biāo)出現(xiàn)在邊界上的特殊情況實(shí)際中一般不會出現(xiàn),因此邊界鏈路可以直接排除,所以并不影響上述鏈路選取方法．

圖3 鏈路選取Fig.3 Link selection

2.2 稀疏恢復(fù)階段

在完成訓(xùn)練階段后,我們得到一個更新后的匹配字典;稀疏恢復(fù)階段,我們用該字典替代原始權(quán)重字典,并從鏈路索引表index中挑選對應(yīng)的RSS變化值,最后使用CS稀疏重構(gòu)算法求解目標(biāo)位置．文獻(xiàn)[16]中提出了一種BGMP算法得到了較好的定位效果,因此本文也延用了這種方法．

3 實(shí)驗(yàn)驗(yàn)證

為了體現(xiàn)本文提出算法的性能,本文分別在室外和室內(nèi)環(huán)境下進(jìn)行實(shí)驗(yàn)驗(yàn)證．為了便于與文獻(xiàn)[17]的結(jié)果進(jìn)行比較,其中室外實(shí)驗(yàn)數(shù)據(jù)采用猶他州大學(xué)SPAN實(shí)驗(yàn)室提供的數(shù)據(jù);室內(nèi)實(shí)驗(yàn)數(shù)據(jù)則由本實(shí)驗(yàn)室搭建的DFL系統(tǒng)測量得到．實(shí)驗(yàn)中,我們先采集目標(biāo)在各個位置處的RSS值作為訓(xùn)練數(shù)據(jù),根據(jù)本文所提的鏈路選擇學(xué)習(xí)方法,自適應(yīng)學(xué)習(xí)得到匹配字典;再使用匹配字典以及實(shí)時采集的RSS數(shù)據(jù),求解目標(biāo)位置．另外,參考文獻(xiàn)[24]的做法,不失一般性,我們假設(shè)目標(biāo)的初始位置是已知的,首先保證了起點(diǎn)不會出現(xiàn)偏差,但為了保證統(tǒng)計(jì)結(jié)果的有效性,起點(diǎn)位置坐標(biāo)不參與統(tǒng)計(jì)．

3.1 室外情況

3.1.1 實(shí)驗(yàn)設(shè)置

室外實(shí)驗(yàn)直接采用SPAN實(shí)驗(yàn)室提供的數(shù)據(jù)進(jìn)行[數(shù)據(jù)來源:http://span.ece.utah.edu/rti-data-set]．該實(shí)驗(yàn)的定位區(qū)域大小為6.3 m×6.3 m,在定位區(qū)域邊緣以0.9 m的間隔共部署了28個無線節(jié)點(diǎn),為了與文獻(xiàn)[17]中的方法進(jìn)行比較,本文也將區(qū)域劃分為49個小網(wǎng)格,數(shù)據(jù)集給出了目標(biāo)位于其中35個參考位置的RSS值,即P=35,并且數(shù)據(jù)集中也給出了采集這35個參考位置數(shù)據(jù)時目標(biāo)的移動軌跡,如圖4所示(我們可以根據(jù)移動軌跡來進(jìn)行鏈路選取)．其他參數(shù)設(shè)置如下:初始字典采用橢圓模型構(gòu)造,鏈路選擇區(qū)域閾值設(shè)置為h=1.5 m．

圖4 室外實(shí)驗(yàn)?zāi)繕?biāo)移動軌跡圖Fig.4 Target track map of the outdoor experiment

我們將所提LSL算法與文獻(xiàn)[17]中所提算法進(jìn)行比較,將文獻(xiàn)[17]所提算法記為算法A,為了比較不同算法間的重構(gòu)性能差異,還與最小化l1范數(shù)算法進(jìn)行了比較,將其記為算法B．我們采用真實(shí)位置和估計(jì)位置之間的均方誤差作為評估算法定位精度的標(biāo)準(zhǔn)．

3.1.2 實(shí)驗(yàn)結(jié)果分析

為了直觀反映定位效果,本節(jié)先給出目標(biāo)在一個位置的定位結(jié)果對比圖,然后給出統(tǒng)計(jì)分析結(jié)果．

圖5為當(dāng)目標(biāo)位于(0.9,2.7)m位置時,三種算法的定位結(jié)果比較．可以看到:算法B效果并不理想,不僅目標(biāo)估計(jì)位置與真實(shí)位置間相差較大,并且會伴隨有偽目標(biāo)的情況;而算法A對于某些位置的目標(biāo)定位結(jié)果會出現(xiàn)一至兩個格點(diǎn)的偏差,如圖5(a)所示;而本文算法能夠?qū)崿F(xiàn)準(zhǔn)確的定位．

(a) 真實(shí)位置(單位:m) (b) 算法A定位結(jié)果 (a) Real location(m) (b) Location result of algorithm A

(c) 算法B最小化定位結(jié)果 (d) LSL定位結(jié)果 (c) Minimized location result of algorithm B (d) Location result of LSL 圖5 室外環(huán)境三種算法定位結(jié)果對比Fig.5 Comparison of positioning results of three algorithms in the outdoor environment

圖6給出了在單目標(biāo)情況下,本文算法和算法A、算法B的定位誤差累積概率分布圖．由于劃分的像素點(diǎn)的尺寸為0.9 m,并且當(dāng)目標(biāo)位于某個像素點(diǎn)時,都默認(rèn)為該目標(biāo)在這個像素點(diǎn)的中心位置,因此,定位誤差的累積分布函數(shù)圖會呈現(xiàn)折線的形狀．從圖中可以看到,由于LSL與算法A最大定位誤差較小,所以累積分布函數(shù)圖呈現(xiàn)一種陡峭的上升趨勢．而LSL相比于算法A其優(yōu)勢體現(xiàn)在,由于學(xué)習(xí)字典不僅糾正了傳統(tǒng)權(quán)重矩陣的模型誤差并且也過濾部分誤差位置,從而使得絕大部分點(diǎn)都能夠準(zhǔn)確定位．定位誤差的詳細(xì)統(tǒng)計(jì)結(jié)果如表1所示,我們可以看到,本文所提的LSL算法在室外環(huán)境下,定位平均誤差以及均方根誤差上都有米級以上的提升．

圖6 室外環(huán)境三種算法定位誤差的累積分布函數(shù)Fig.6 CDF of three algorithms in the outdoor environment

表1 室外環(huán)境定位誤差對比Tab.1 Comparison of positioning error in the outdoor environment

3.2 室內(nèi)情況

3.2.1 實(shí)驗(yàn)設(shè)置

室內(nèi)實(shí)驗(yàn)在南京師范大學(xué)行健樓一樓大廳進(jìn)行,實(shí)測環(huán)境布局如圖7所示,該定位環(huán)境三面為磚墻,一面為全玻璃墻面．實(shí)測數(shù)據(jù)采用的是TI CC2530無線節(jié)點(diǎn),采用IEEE802.15.4協(xié)議和2.4 GHz頻率．此實(shí)驗(yàn)定位區(qū)域?yàn)? m×5 m,在區(qū)域邊緣以1 m的間隔共部署了20個無線節(jié)點(diǎn),我們將該定位區(qū)域以1 m為邊長劃分為25個小網(wǎng)格點(diǎn)．采集目標(biāo)位于各位置時的RSS數(shù)據(jù),并記錄目標(biāo)移動軌跡,如圖8所示．

圖7 室內(nèi)實(shí)驗(yàn)環(huán)境Fig.7 Indoor experiment environment

圖8 室內(nèi)實(shí)驗(yàn)?zāi)繕?biāo)移動軌跡圖Fig.8 Target movement track map of indoor experiment

3.2.2 實(shí)驗(yàn)結(jié)果分析

圖9為當(dāng)目標(biāo)位于(1,1)m位置時,三種算法的定位結(jié)果比較．

(a) 真實(shí)位置(單位:m) (b) 算法A定位結(jié)果 (a) Real location(m) (b) Location result of algorithm A

(c) 算法B最小化定位結(jié)果 (d) LSL定位結(jié)果 (c) Minimized location result of algorithm B (d) location result of LSL 圖9 室內(nèi)環(huán)境三種算法定位結(jié)果對比Fig.9 Comparison of positioning results of three algorithms in the indoor environment

從圖9我們可以得出和室外環(huán)境一致的結(jié)論:本文所提的LSL算法,能夠有效修正原傳統(tǒng)權(quán)重字典的模型誤差,并且能夠過濾部分誤差位置,因此對于大部分目標(biāo)位置都能夠?qū)崿F(xiàn)較準(zhǔn)確的定位．現(xiàn)給出在室內(nèi)情況,目標(biāo)位于各個位置,多次實(shí)驗(yàn)的統(tǒng)計(jì)結(jié)果(其中每個位置我們都進(jìn)行了110次實(shí)驗(yàn)):圖10為在單目標(biāo)情況下,本文算法和已有算法的定位誤差累積概率分布．本文算法,無論是能準(zhǔn)確定位到目標(biāo)點(diǎn)的概率,還是最大定位誤差,都優(yōu)于其他算法．本文算法在定位精度上有較大幅度的提升．室內(nèi)環(huán)境定位誤差的詳細(xì)統(tǒng)計(jì)結(jié)果,如表2所示,本文所提算法相比算法B在平均誤差上提高了1.9 m左右,相比算法A平均誤差大致提高了0.5 m;所提LSL算法的均方根誤差也相比算法B、算法A,分別提高了29.7%和14.5%.

圖10 室內(nèi)環(huán)境三種算法定位誤差的累積分布函數(shù)圖Fig.10 CDF of three algorithms in the indoor environment

表2 室內(nèi)環(huán)境定位誤差對比Tab.2 Comparison of positioning error in the indoor environment

綜上所述,本文所提的LSL算法無論是室外環(huán)境,還是室內(nèi)環(huán)境,其定位精度都大幅優(yōu)于其他算法,因此具有很好的定位性能．

3.3 算法運(yùn)行時間分析

圖11給出了算法B、算法A與LSL算法在室外和室內(nèi)情況下的運(yùn)行時間對比．

圖11 三種算法的運(yùn)行時間Fig.11 Running time of three algorithms

如圖11所示,盡管本文算法增加了字典學(xué)習(xí)環(huán)節(jié),但由于LSL算法在訓(xùn)練階段完成了對鏈路的篩選,學(xué)習(xí)字典的維度大大下降,使得在稀疏重構(gòu)階段,計(jì)算量大大減少,因此算法運(yùn)行速度較其他算法非但沒有下降,相反還有較大的提升．

4 結(jié) 論

本文針對CS框架下DFL的傳統(tǒng)模型權(quán)重字典存在字典不匹配問題,提出了一種鏈路選擇學(xué)習(xí)算法(LSL),能夠在字典更新過程中進(jìn)行鏈路選取,同時解決了字典不匹配以及有效鏈路選擇的問題．經(jīng)室外及室內(nèi)實(shí)驗(yàn)驗(yàn)證,這種算法不僅很好地解決了傳統(tǒng)方法的字典不匹配問題,而且能夠過濾部分誤差位置,在定位精度和算法運(yùn)行時間上都有優(yōu)異的表現(xiàn)．下一步將考慮該方法誤差的克勞美·羅界,并將該方法推廣到多目標(biāo)DFL定位．