濰坊第一中學 劉晏寧
基于UWB測距的分布式室內(nèi)定位系統(tǒng)
濰坊第一中學 劉晏寧
隨著電子信息技術和物聯(lián)網(wǎng)的發(fā)展,家居智能化的時代正在到來。室內(nèi)定位系統(tǒng)可以提供室內(nèi)人員物品的定位服務,是智能家居中重要而基本的組成系統(tǒng)。本文提出了一種基于超寬帶(UWB)測距技術的分布式室內(nèi)定位系統(tǒng)。它基于UWB通信模塊通過飛行時間法測出的節(jié)點間的距離信息,在最小平方誤差準則下,將定位問題轉(zhuǎn)化為凸優(yōu)化問題。進一步地,應用分布式凸優(yōu)化算法解決這個問題。分布式室內(nèi)定位系統(tǒng)較傳統(tǒng)的集中式定位方法的優(yōu)點在于錨點易于布設,數(shù)量易于拓展且系統(tǒng)魯棒性好。最后,本文給出了實際搭建系統(tǒng)的定位結果以驗證本文提出方法的有效性和實用性。
室內(nèi)定位;UWB;分布式
在日常的生活中,有很多的應用場景我們需要知道一個物體的位置信息。室外的應用場景比如在搜救時需要知道人員的位置,又或者汽車的自動駕駛和導航也需要知道自己的位置。而在室內(nèi),位置信息的應用就更多了,例如在養(yǎng)老院中需要監(jiān)控老人的位置,家庭機器人需要定位,就連我們在家中尋找一些小物件時,知道他們的位置也會方便很多。在室內(nèi),由于衛(wèi)星信號的遮擋和多徑傳輸,衛(wèi)星導航系統(tǒng)(GNSS)定位一般不準確,這樣各種不同的室內(nèi)定位方式便應運而生了[1][2]。例如Vicon公司的基于紅外視覺的室內(nèi)定位系統(tǒng),或是基于激光雷達和攝像頭的SLAM方法等等。
近年來,隨著射頻技術的發(fā)展與芯片的小型化,應用超寬帶(Ultra-Wideband,UWB)技術的射頻芯片已經(jīng)可以做到指甲蓋的大小,這樣就大大拓展了UWB技術的應用范圍。由于超寬帶技術所發(fā)出的電磁波波長很短,直接使用飛行時間法(TOF)進行測距就能達到厘米級的精度。本文就是針對室內(nèi)定位場景提出了一種基于UWB測距的分布式室內(nèi)定位系統(tǒng)。該系統(tǒng)的優(yōu)勢在于只需要幾個小型又廉價的UWB射頻芯片, 通過與多個錨點間的距離確定位置,成本低廉,架設簡單。
由于種種優(yōu)勢,基于UWB的定位方式得到了廣泛的關注與研究。在文獻[3]中,作者給出了基于時間的測距技術,提出了基于TOA的超寬帶無線傳感器網(wǎng)絡測距方法。而文獻[4]將定位環(huán)境近似為二維平面的應用場景,提出了二維的分布式節(jié)點自定位系統(tǒng)。凸優(yōu)化方法也在目標定位問題中有所應用,例如文獻[5]就提出了一種基于ADMM算法的分布式目標定位技術。
不同于以上文獻,本文不光給出了二維的分布式定位算法,而且將其拓展到了三維空間中。該方法基于UWB的飛行時間法測距,根據(jù)得到的距離信息,將定位問題分別在二維和三位情況下轉(zhuǎn)化成為凸優(yōu)化問題,并應用分布式凸優(yōu)化算法求解,導出了基于距離的分布式定位算法。最后通過實驗表明,本文提出的方法可以成功實現(xiàn)對位置未知的節(jié)點進行定位,并且簡單易行,易于使用。
UWB節(jié)點本定位系統(tǒng)基本的組成部分。這里的UWB指的是超寬帶(Ultra-Wideband)通訊技術。它是一種無載波的通訊技術,利用納秒級的非正弦窄脈沖傳輸數(shù)據(jù)。UWB既可以用來應用在近距離高速數(shù)據(jù)傳輸,又可以利用其亞納秒超窄脈沖來做近距離精確室內(nèi)定位。UWB的優(yōu)點在于抗干擾性能強,傳輸速率高,系統(tǒng)容量大發(fā)送功率非常小,其電磁波輻射對人體的影響也很小。
如圖1所示,本文使用基于DecaWave公司開發(fā)的DW1000芯片的超寬帶無線收發(fā)模塊,其在實時定位系統(tǒng)中用于物體的定位,精度高達10厘米。模塊集成天線,物理尺寸很小,非常容易的集成到實時定位系統(tǒng)(RTLS)和無線傳感網(wǎng)絡(WSN)中,其中包括農(nóng)業(yè),樓宇控制,工廠自動化,醫(yī)療,安全和倉儲等行業(yè)。每一個UWB模塊被稱為節(jié)點或者標簽。它們都有相互之間通信的能力,并通過通信可以得到節(jié)點間的距離。
圖1 DWM1000寬帶無線收發(fā)模塊及模塊框圖
顧名思義,飛行時間法測距的基本原理就是通過測量節(jié)點發(fā)出的電磁波的飛行時間,來推算出節(jié)點間的距離。
具體來說,我們假設測量的是節(jié)點A和節(jié)點B之間的距離。節(jié)點A首先發(fā)出一串特殊的信息,并記錄下發(fā)射時的時間戳。節(jié)點B接收到信息,記錄下接收時間戳。接下來節(jié)點B將自己的標簽信息、接收時間戳和這條信息從節(jié)點B發(fā)送的時間一并返回發(fā)送到節(jié)點A。最后節(jié)點A接收到信息后記錄下到達時間戳。通過這些時間戳,我們就可以計算出傳遞信息的電磁波的飛行時間。
然后飛行時間與光速的乘積就是兩節(jié)點間的距離。
通過平均多次測量的平均值,可以減少節(jié)點間時間同步和時間測量誤差的影響,從而減少測距誤差。
在這一章節(jié)中,我們將基于通過章節(jié)2.2所描述的方法得到的位置未知節(jié)點與各個錨點間的距離,將定位問題以最小平方誤差準則轉(zhuǎn)化為一個凸優(yōu)化問題。
為了對定位問題有一個直觀的理解,我們先來看在二維平面中的簡化問題。首先先定義一個平面的全局坐標系,假設我們想要測量的位置未知節(jié)點st的平面坐標位置為[xt , yt]。在平面中,事先有位置坐標已知的N個UWB測距節(jié)點作為錨點。我們將第i個錨點si的坐標記為[xi , yi],其中i=1,2,…N。在平面中我們需要假設不共線的錨點數(shù)量大于等于3個,以保證可以解出唯一的待測節(jié)點。
根據(jù)平面中點與點間的直線距離公式,我們可以得到錨點si與待測節(jié)點st的理想距離為:
而在實際情況中,由于噪聲的存在,通過UWB測量得到的距離di一般不等于這個理想的實際距離disti,它們之間的差就是測量噪聲wi,如下面公式(4)所示:
理想情況下,待測節(jié)點的位置就在以各個錨點為圓心,距離disti為半徑的圓的交點上。如圖2中的虛線圓所示,五角星為待測節(jié)點,圓圈為錨點,待測節(jié)點的位置就在三個虛線圓的交點上。然而節(jié)點間實際的距離我們是不知道的,我們只知道測量到的距離。而由于測量噪聲的存在,我們以測量到的結果di為半徑畫圓時,往往相交不到一個點上,我們只能知道待測節(jié)點在這些圓交點密集的那個區(qū)域附近。
圖2 二維定位原理示意圖
這時就需要一個準則來決定選取哪個點作為位置未知的待測節(jié)點的位置,是在得到的測量結果的情況下能計算出來的最好的。我們假設測量噪聲wi是獨立同分布的高斯白噪聲,這樣選取最小平方準則就是最優(yōu)的。最小平方準則指的是,每個錨點以它和待測節(jié)點的位置結果的距離和測量的距離間的差的平方作為自己的損失函數(shù)。這個損失函數(shù)值越小,就意味著待測節(jié)點的位置結果越滿足這個錨點的測量結果。
而總體的損失函數(shù)是所有錨點各自的損失函數(shù)的和:
這樣我們就將定位問題轉(zhuǎn)化為了一個優(yōu)化問題,即找到一個最好的待測節(jié)點st位置[xt , yt],使得所有錨點的損失函數(shù)和最小。這時的[xt , yt]就是我們要找到的待測節(jié)點st在最小平方準則下的最優(yōu)位置。這個優(yōu)化問題可以描述為如下的形式:
我們需要約束待測節(jié)點在錨點構成的凸包Ω內(nèi)。這樣優(yōu)化函數(shù)F(st)是凸函數(shù),并且約束條件也是凸的,因此這是一個凸優(yōu)化問題,我們可以找到唯一的最優(yōu)解。
同理,當我們解決實際三維空間中的問題時,只需要將二維表述做適當?shù)木S數(shù)拓展即可。同樣假設我們想要測量的位置未知節(jié)st點的實際坐標位置為[xt , yt , zt]。將第i個錨點si的坐標記為[xi , yi , zi],其中i=1,2,…N。假設待測節(jié)點的位置在錨點形成的凸包中,也就是說待測節(jié)點在錨點所包圍的空間內(nèi)部。同時錨點布設時需要令不共面的錨點數(shù)量大于等于4個,以保證可以解出唯一的待測節(jié)點位置的解。在三維空間中,這個解的位置就是在以錨點為球心,測量距離為半徑的球面相交區(qū)域的附近。
各個錨點測量得到的錨點si與待測節(jié)點st的距離記為di。根據(jù)我們假設的坐標計算,錨點si與待測節(jié)點st的實際距離為:
與章節(jié)3.1中的二維情況類似,我們可以寫出錨點的損失函數(shù)。
同樣的,三維空間的定位問題也可以轉(zhuǎn)化為一個凸優(yōu)化問題。
根據(jù)文章[6]中的結論,本文所研究的定位問題滿足凸優(yōu)化問題且優(yōu)化函數(shù)是各節(jié)點優(yōu)化函數(shù)的加和形式這兩個條件,所以可以用分布式的方法來解決本文我們關心的問題。而分布式的解法相對于集中式算法有很多優(yōu)勢。一是分布式算法將計算分散到各個節(jié)點中,省去了中心計算中心,降低了成本;二是分布式算法易于拓展,這使得錨點易于布設,且數(shù)量易于增減,魯棒性高。同集中式梯度下降法[7]類似,本文的分布式凸優(yōu)化算法也是基于優(yōu)化函數(shù)的梯度的。區(qū)別在于集中式算法的梯度是整體優(yōu)化函數(shù)的梯度,而分布式算法每個節(jié)點只需要自己的優(yōu)化函數(shù)的梯度。
我們首先定義錨點間可以直接通信的,稱為鄰居節(jié)點。所有錨點都有至少一個鄰居節(jié)點,并且所有節(jié)點都可以通過間接地傳遞連接到一起。算法計算時,首先需要每一個錨點假設一個自認為的待測節(jié)點的位置,然后根據(jù)自己得到的與待測節(jié)點間的距離,按照公式(9)計算出自己的損失函數(shù)的梯度。接著這個錨點需要將此時自認為的待測節(jié)點的位置與鄰居認為的待測節(jié)點的位置做平均,然后按照梯度下降法沿梯度方向移動一個步長α,作為下一時刻自認為的待測節(jié)點的位置。以x軸分量為例,用公式表示如下:
這里的Ni指的是錨點si通訊上的鄰居,包括它自己。y和z軸分量的計算式與公式(11)類似。
經(jīng)過如上的步驟,每個錨點更新自認為的待測節(jié)點的位置,經(jīng)過若干次迭代,便可以全部收斂到凸優(yōu)化問題的最優(yōu)解,完成定位。
為測試本文所提出的基于UWB測距的分布式室內(nèi)定位方法的正確性與可行性,我搭建了實驗系統(tǒng),在室內(nèi)做了實際實驗。實驗中一共布設的4個錨點,分別位于室內(nèi)的頂點處。待測節(jié)點在室內(nèi)的位置是[3,4,5],步長α選取0.15。按照章節(jié)3所敘述的算法進行實驗,結果如下圖所示。
圖3 定位實驗結果
這三幅圖分別代表錨點認為的待測節(jié)點位置的x,y,z坐標,每幅圖中有四條曲線,分別是四個錨點的。從圖中可以看到,錨點認為的待測節(jié)點位置在一開始是隨機選取的,并不一致。但是經(jīng)過大約50步迭代后,每個錨點認為的待測節(jié)點位置一致且收斂到最優(yōu)位置。從而驗證了本文所提算法的有效性。
本文提出了一種基于UWB測距的分布式室內(nèi)定位系統(tǒng)。文中介紹了UWB的飛行時間測距原理。并分別在二維和三維的情況下,將定位問題在最小平方誤差準則下轉(zhuǎn)化為凸優(yōu)化問題。然后通過分布式凸優(yōu)化的方法,推導了問題求解算法的分布式形式。最后文章給出了實際系統(tǒng)的實驗結果,驗證了本文提出的方法的有效性。
[1]趙銳,鐘榜,朱祖禮,等.室內(nèi)定位技術及應用綜述[J].電子科技,2014,27(3):154-157.
[2]阮陵,張翎,許越,等.室內(nèi)定位:分類、方法與應用綜述[J].地理信息世界,2015(2):8-14.
[3]王蕓.基于UWB無線傳感器網(wǎng)絡的定位技術研究[D].江西理工大學,2012.
[4]石琴琴.無線傳感器網(wǎng)絡節(jié)點自定位系統(tǒng)及其算法研究[D].上海交通大學,2009.
[5]呂瑞娟.基于凸優(yōu)化的分布式目標定位技術研究[J].科教導刊:電子版,2016(11):166-166.
[6]洪奕光,張艷瓊.分布式優(yōu)化:算法設計和收斂性分析[J].控制理論與應用,2014,31(7):850-857.
[7]劉穎超,張紀元.梯度下降法[J].南京理工大學學報,1993(2):12-16.
劉晏寧(2000—),山東人,現(xiàn)就讀于濰坊第一中學高三十三班。