基于UWB測距的分布式室內定位系統

濰坊第一中學 劉晏寧

基于UWB測距的分布式室內定位系統

濰坊第一中學 劉晏寧

隨著電子信息技術和物聯網的發展，家居智能化的時代正在到來。室內定位系統可以提供室內人員物品的定位服務，是智能家居中重要而基本的組成系統。本文提出了一種基于超寬帶（UWB）測距技術的分布式室內定位系統。它基于UWB通信模塊通過飛行時間法測出的節點間的距離信息，在最小平方誤差準則下，將定位問題轉化為凸優化問題。進一步地，應用分布式凸優化算法解決這個問題。分布式室內定位系統較傳統的集中式定位方法的優點在于錨點易于布設，數量易于拓展且系統魯棒性好。最后，本文給出了實際搭建系統的定位結果以驗證本文提出方法的有效性和實用性。

室內定位；UWB；分布式

1.引言

在日常的生活中，有很多的應用場景我們需要知道一個物體的位置信息。室外的應用場景比如在搜救時需要知道人員的位置，又或者汽車的自動駕駛和導航也需要知道自己的位置。而在室內，位置信息的應用就更多了，例如在養老院中需要監控老人的位置，家庭機器人需要定位，就連我們在家中尋找一些小物件時，知道他們的位置也會方便很多。在室內，由于衛星信號的遮擋和多徑傳輸，衛星導航系統（GNSS）定位一般不準確，這樣各種不同的室內定位方式便應運而生了[1][2]。例如Vicon公司的基于紅外視覺的室內定位系統，或是基于激光雷達和攝像頭的SLAM方法等等。

近年來，隨著射頻技術的發展與芯片的小型化，應用超寬帶(Ultra-Wideband，UWB)技術的射頻芯片已經可以做到指甲蓋的大小,這樣就大大拓展了UWB技術的應用范圍。由于超寬帶技術所發出的電磁波波長很短，直接使用飛行時間法（TOF）進行測距就能達到厘米級的精度。本文就是針對室內定位場景提出了一種基于UWB測距的分布式室內定位系統。該系統的優勢在于只需要幾個小型又廉價的UWB射頻芯片, 通過與多個錨點間的距離確定位置,成本低廉，架設簡單。

由于種種優勢，基于UWB的定位方式得到了廣泛的關注與研究。在文獻[3]中，作者給出了基于時間的測距技術，提出了基于TOA的超寬帶無線傳感器網絡測距方法。而文獻[4]將定位環境近似為二維平面的應用場景，提出了二維的分布式節點自定位系統。凸優化方法也在目標定位問題中有所應用，例如文獻[5]就提出了一種基于ADMM算法的分布式目標定位技術。

不同于以上文獻，本文不光給出了二維的分布式定位算法，而且將其拓展到了三維空間中。該方法基于UWB的飛行時間法測距，根據得到的距離信息，將定位問題分別在二維和三位情況下轉化成為凸優化問題，并應用分布式凸優化算法求解，導出了基于距離的分布式定位算法。最后通過實驗表明，本文提出的方法可以成功實現對位置未知的節點進行定位，并且簡單易行，易于使用。

2.基于UWB的飛行時間（TOF）測距

2.1 UWB通訊節點

UWB節點本定位系統基本的組成部分。這里的UWB指的是超寬帶（Ultra-Wideband）通訊技術。它是一種無載波的通訊技術，利用納秒級的非正弦窄脈沖傳輸數據。UWB既可以用來應用在近距離高速數據傳輸，又可以利用其亞納秒超窄脈沖來做近距離精確室內定位。UWB的優點在于抗干擾性能強，傳輸速率高，系統容量大發送功率非常小，其電磁波輻射對人體的影響也很小。

如圖1所示，本文使用基于DecaWave公司開發的DW1000芯片的超寬帶無線收發模塊，其在實時定位系統中用于物體的定位，精度高達10厘米。模塊集成天線，物理尺寸很小，非常容易的集成到實時定位系統（RTLS）和無線傳感網絡（WSN）中，其中包括農業，樓宇控制，工廠自動化，醫療，安全和倉儲等行業。每一個UWB模塊被稱為節點或者標簽。它們都有相互之間通信的能力，并通過通信可以得到節點間的距離。

圖1 DWM1000寬帶無線收發模塊及模塊框圖

2.2 飛行時間法（TOF）測距

顧名思義，飛行時間法測距的基本原理就是通過測量節點發出的電磁波的飛行時間，來推算出節點間的距離。

具體來說，我們假設測量的是節點A和節點B之間的距離。節點A首先發出一串特殊的信息，并記錄下發射時的時間戳。節點B接收到信息，記錄下接收時間戳。接下來節點B將自己的標簽信息、接收時間戳和這條信息從節點B發送的時間一并返回發送到節點A。最后節點A接收到信息后記錄下到達時間戳。通過這些時間戳，我們就可以計算出傳遞信息的電磁波的飛行時間。

然后飛行時間與光速的乘積就是兩節點間的距離。

通過平均多次測量的平均值，可以減少節點間時間同步和時間測量誤差的影響，從而減少測距誤差。

3.基于錨點距離的定位問題

在這一章節中，我們將基于通過章節2.2所描述的方法得到的位置未知節點與各個錨點間的距離，將定位問題以最小平方誤差準則轉化為一個凸優化問題。

3.1 二維平面中的問題描述

為了對定位問題有一個直觀的理解，我們先來看在二維平面中的簡化問題。首先先定義一個平面的全局坐標系，假設我們想要測量的位置未知節點st的平面坐標位置為[xt , yt]。在平面中，事先有位置坐標已知的N個UWB測距節點作為錨點。我們將第i個錨點si的坐標記為[xi , yi]，其中i=1,2,…N。在平面中我們需要假設不共線的錨點數量大于等于3個，以保證可以解出唯一的待測節點。

根據平面中點與點間的直線距離公式，我們可以得到錨點si與待測節點st的理想距離為：

而在實際情況中，由于噪聲的存在，通過UWB測量得到的距離di一般不等于這個理想的實際距離disti，它們之間的差就是測量噪聲wi，如下面公式(4)所示：

理想情況下，待測節點的位置就在以各個錨點為圓心，距離disti為半徑的圓的交點上。如圖2中的虛線圓所示，五角星為待測節點，圓圈為錨點，待測節點的位置就在三個虛線圓的交點上。然而節點間實際的距離我們是不知道的，我們只知道測量到的距離。而由于測量噪聲的存在，我們以測量到的結果di為半徑畫圓時，往往相交不到一個點上，我們只能知道待測節點在這些圓交點密集的那個區域附近。

圖2 二維定位原理示意圖

這時就需要一個準則來決定選取哪個點作為位置未知的待測節點的位置，是在得到的測量結果的情況下能計算出來的最好的。我們假設測量噪聲wi是獨立同分布的高斯白噪聲，這樣選取最小平方準則就是最優的。最小平方準則指的是，每個錨點以它和待測節點的位置結果的距離和測量的距離間的差的平方作為自己的損失函數。這個損失函數值越小，就意味著待測節點的位置結果越滿足這個錨點的測量結果。

而總體的損失函數是所有錨點各自的損失函數的和：

這樣我們就將定位問題轉化為了一個優化問題，即找到一個最好的待測節點st位置[xt , yt]，使得所有錨點的損失函數和最小。這時的[xt , yt]就是我們要找到的待測節點st在最小平方準則下的最優位置。這個優化問題可以描述為如下的形式：

我們需要約束待測節點在錨點構成的凸包Ω內。這樣優化函數F(st)是凸函數，并且約束條件也是凸的，因此這是一個凸優化問題，我們可以找到唯一的最優解。

3.2 三維空間中的問題描述

同理，當我們解決實際三維空間中的問題時，只需要將二維表述做適當的維數拓展即可。同樣假設我們想要測量的位置未知節st點的實際坐標位置為[xt , yt , zt]。將第i個錨點si的坐標記為[xi , yi , zi]，其中i=1,2,…N。假設待測節點的位置在錨點形成的凸包中，也就是說待測節點在錨點所包圍的空間內部。同時錨點布設時需要令不共面的錨點數量大于等于4個，以保證可以解出唯一的待測節點位置的解。在三維空間中，這個解的位置就是在以錨點為球心，測量距離為半徑的球面相交區域的附近。

各個錨點測量得到的錨點si與待測節點st的距離記為di。根據我們假設的坐標計算，錨點si與待測節點st的實際距離為：

與章節3.1中的二維情況類似，我們可以寫出錨點的損失函數。

同樣的，三維空間的定位問題也可以轉化為一個凸優化問題。

4.定位問題的分布式凸優化算法

根據文章[6]中的結論，本文所研究的定位問題滿足凸優化問題且優化函數是各節點優化函數的加和形式這兩個條件，所以可以用分布式的方法來解決本文我們關心的問題。而分布式的解法相對于集中式算法有很多優勢。一是分布式算法將計算分散到各個節點中，省去了中心計算中心，降低了成本；二是分布式算法易于拓展，這使得錨點易于布設，且數量易于增減，魯棒性高。同集中式梯度下降法[7]類似，本文的分布式凸優化算法也是基于優化函數的梯度的。區別在于集中式算法的梯度是整體優化函數的梯度，而分布式算法每個節點只需要自己的優化函數的梯度。

我們首先定義錨點間可以直接通信的，稱為鄰居節點。所有錨點都有至少一個鄰居節點，并且所有節點都可以通過間接地傳遞連接到一起。算法計算時，首先需要每一個錨點假設一個自認為的待測節點的位置，然后根據自己得到的與待測節點間的距離，按照公式(9)計算出自己的損失函數的梯度。接著這個錨點需要將此時自認為的待測節點的位置與鄰居認為的待測節點的位置做平均，然后按照梯度下降法沿梯度方向移動一個步長α，作為下一時刻自認為的待測節點的位置。以x軸分量為例，用公式表示如下：

這里的Ni指的是錨點si通訊上的鄰居，包括它自己。y和z軸分量的計算式與公式(11)類似。

經過如上的步驟，每個錨點更新自認為的待測節點的位置，經過若干次迭代，便可以全部收斂到凸優化問題的最優解，完成定位。

5.實驗結果

為測試本文所提出的基于UWB測距的分布式室內定位方法的正確性與可行性，我搭建了實驗系統，在室內做了實際實驗。實驗中一共布設的4個錨點，分別位于室內的頂點處。待測節點在室內的位置是[3,4,5]，步長α選取0.15。按照章節3所敘述的算法進行實驗，結果如下圖所示。

圖3 定位實驗結果

這三幅圖分別代表錨點認為的待測節點位置的x,y,z坐標，每幅圖中有四條曲線，分別是四個錨點的。從圖中可以看到，錨點認為的待測節點位置在一開始是隨機選取的，并不一致。但是經過大約50步迭代后，每個錨點認為的待測節點位置一致且收斂到最優位置。從而驗證了本文所提算法的有效性。

6.結論

本文提出了一種基于UWB測距的分布式室內定位系統。文中介紹了UWB的飛行時間測距原理。并分別在二維和三維的情況下，將定位問題在最小平方誤差準則下轉化為凸優化問題。然后通過分布式凸優化的方法，推導了問題求解算法的分布式形式。最后文章給出了實際系統的實驗結果，驗證了本文提出的方法的有效性。

[1]趙銳,鐘榜,朱祖禮,等．室內定位技術及應用綜述[J]．電子科技,2014,27(3)：154-157．

[2]阮陵,張翎,許越,等．室內定位：分類、方法與應用綜述[J]．地理信息世界,2015(2)：8-14．

[3]王蕓．基于UWB無線傳感器網絡的定位技術研究[D]．江西理工大學,2012．

[4]石琴琴．無線傳感器網絡節點自定位系統及其算法研究[D]．上海交通大學,2009．

[5]呂瑞娟．基于凸優化的分布式目標定位技術研究[J]．科教導刊：電子版,2016(11)：166-166．

[6]洪奕光,張艷瓊．分布式優化：算法設計和收斂性分析[J]．控制理論與應用,2014,31(7)：850-857．

[7]劉穎超,張紀元．梯度下降法[J]．南京理工大學學報,1993(2)：12-16．

劉晏寧（2000—），山東人，現就讀于濰坊第一中學高三十三班。