劉子恒，焦良葆，孫宏偉，袁 楓，路繩方

(南京工程學(xué)院 人工智能產(chǎn)業(yè)技術(shù)研究院，南京 211167)

0 引言

近年來，隨著物聯(lián)網(wǎng)技術(shù)的發(fā)展和自動化水平的不斷提高，國家對高危工業(yè)環(huán)境的安全要求越來越高。在復(fù)雜的工業(yè)環(huán)境中對作業(yè)人員進行高精度的定位，可以滿足各種作業(yè)場地的應(yīng)用需求，有效保證作業(yè)人員的人身安全[1]。目前國內(nèi)外常見的無線定位技術(shù)主要有：射頻識別技術(shù)(RFID, radio frequency identification)、超寬帶(UWB, ultra-wide band)、無線局域網(wǎng)(WLAN,wireless local area network)、激光雷達(LiDAR, light detection and ranging)、超聲波、藍牙、紅外線、全球定位系統(tǒng)(GPS, global positioning system)等[2]。與其他定位技術(shù)相比，UWB定位技術(shù)具有傳輸速率高、穿透性強、定位精度高、抗多徑干擾能力強、發(fā)射功率低、時間分辨率好的優(yōu)點[3]，因此廣泛應(yīng)用在高精度室內(nèi)定位中。

UWB室內(nèi)定位技術(shù)中常用的測距方法有：接收信號強度[4](RSS, receive signal strength)、接收信號角度[5](AOA，angle of arrival)、接收信號時間差[6](TDOA，time difference of arrival)、接收信號時間[7](TOA, time of arrival)，其中TOA和TDOA測距算法是室內(nèi)定位技術(shù)中應(yīng)用最廣泛的兩種算法[8]，TDOA算法充分利用了UWB信號對時間的高精度分辨能力，通過檢測信號到達兩個基站的絕對時間差，而不是到達的飛行時間來確定目標的位置，整個過程只需與基站交互一次，具有測距通信量少、延遲率低、抗多徑干擾能力強的優(yōu)點。TDOA算法降低了標簽與各基站之間的時間同步難度，但它提高了基站間的時間同步要求，基站間必須保證嚴格的時鐘同步，這在一定程度上加大了技術(shù)方案的實施難度[9]。TOA測距算法主要通過基站標簽間多次通信實現(xiàn)，具有實現(xiàn)難度低、硬件要求低的優(yōu)點。與TDOA算法要求基站間嚴格時鐘同步不同，TOA算法僅要求基站和標簽之間時鐘準同步[10]，并且增加標簽與基站間的通信次數(shù)可以在一定程度上減少晶振偏移帶來的計時誤差[11],提高測距系統(tǒng)的精度，因其實現(xiàn)難度比TDOA低，故本文選用TOA算法為測距算法。

文獻[12]設(shè)計的室內(nèi)定位系統(tǒng)以UWB技術(shù)為基礎(chǔ)，通過TOA算法來確定目標的位置。雖然該定位系統(tǒng)測距均值與真實值誤差不超過15 cm，均值與真實值間誤差不超過30 cm，實現(xiàn)了較高的測距精度和定位精度，但當系統(tǒng)接入標簽量較多時存在嚴重的通信沖突，測距信息大量丟失，實際使用效果并不好[13]。本文針對TOA算法通信質(zhì)量無法保證、多標簽情況下通信沖突的問題，本文提出了一種基于洪泛機制準同步的高效UWB定位方法，先通過洪泛機制實現(xiàn)時鐘準同步，再對每個設(shè)備序列號進行時隙分配，在保證精度的同時有效減少了標簽之間的沖突，從而提高了系統(tǒng)標簽容納量，并通過減少標簽與基站間的無效通信降低了系統(tǒng)功耗，能夠滿足較高的工業(yè)級要求。

1 原理及其誤差分析

UWB定位系統(tǒng)一般可分為測距和定位兩部分，接下來針對這兩部分進行原理介紹及誤差分析。

1.1 測距原理

TOA測距算法又稱作TOF(timeofflight)算法，主要是根據(jù)測量接收信號在基站和標簽之間的到達時間并將其轉(zhuǎn)換為距離，從而進行定位。TOA測距方法的時間取決于時鐘精度，為減少時鐘偏移造成的測距誤差，通常采用正反兩個方向的測量方法[14]，通過測量飛行時間平均值來減少兩者之間的時間偏移，從而提高測距精度。目前TOA定位方案有兩種發(fā)展趨勢：基于通信節(jié)點間嚴格時間同步的單向測距[15](OWR，one way ranging)方案和基于雙向信號傳輸雙向測距[16](TWR，two way ranging)方案。OWR算法原理簡單，但需要嚴格同步系統(tǒng)中所有器件的時鐘，考慮到UWB對定位精度的要求非常高，對處于移動中的標簽實現(xiàn)同步難度大。TWR方案通過標簽和基站間交換時間戳信息來降低設(shè)備間時鐘同步的難度[17]，實現(xiàn)了系統(tǒng)復(fù)雜度和成本的降低，但其定位精度受設(shè)備自身晶振偏移影響[18]。本文采用的是雙邊雙向測距(DS-TWR, double sided -two way ranging)算法，該方法有效降低了晶振偏移帶來的測距誤差[19]。

在測距階段，標簽與基站會進行三次信息交互并記錄相應(yīng)時間節(jié)點的時間戳，進而計算出飛行距離[20]，其測距原理如圖1所示。

第一步：任意時間點節(jié)點A接收到測距請求后，發(fā)送rng消息并記錄發(fā)送時間戳TSP，等待節(jié)點B回復(fù)。

第二步：節(jié)點B接收到消息后立即記錄當前時間戳TRP，在短暫時延后回復(fù)節(jié)點A一個res消息，記錄下發(fā)送回復(fù)消息的時間戳TSR。

第三步：節(jié)點A一旦收到res消息，則立刻記錄接收時間戳TRR，一定時延后回復(fù)節(jié)點A一個fin消息，并記錄回復(fù)時間戳TSF。

第四步：節(jié)點B收到A回復(fù)的fin信息后，記錄該時刻時間戳TRF，根據(jù)整個測距過程中產(chǎn)生的6個時間戳求解出消息在空氣中的飛行時間T，飛行時間T乘以電磁波傳輸速率即可得到基站與標簽間的距離。

圖1 DS-TWR測距原理

由圖1可得式(1)：

(1)

計算整個過程中無線信號的飛行時間：

(2)

由于式(2)是無線信號在兩節(jié)點之間傳播四次的結(jié)果，聯(lián)立式(1)和式(2)可得理想信號飛行時間T：

(3)

1.2 定位原理

以基站作為參考節(jié)點，標簽為非參考節(jié)點，非參考節(jié)點所在范圍內(nèi)參考節(jié)點坐標已知，根據(jù)立體幾何原理，以各參考點為球心，非參考點與各參考點間距離為半徑畫球，標簽所在位置即為各球的交點。在定位空間內(nèi)建立坐標系，則基站坐標(xi，yi，zi)與標簽坐標(x，y，z)應(yīng)滿足以下關(guān)系：

(4)

如圖2所示，空間內(nèi)存在4個基站時，利用融合Taylor級數(shù)和無跡卡爾曼濾波的定位算法對標簽位置的求解超限定方程組式(6)[20]，求解出的x、y、z即為標簽在定位空間內(nèi)的三維坐標。

圖2 TOA定位過程

1.3 誤差分析

UWB定位系統(tǒng)中最常見的兩類誤差為多址干擾造成的誤差和時鐘精度帶來的誤差[21]。

多址干擾是指在多標簽環(huán)境下，其他標簽的信號對目標信號造成干擾從而降低了估計的準確性。針對該問題本文通過把來自不同標簽的信號從時間上分開，降低了多址干擾情況的發(fā)生。

由于TOA定位算法需要目標節(jié)點與參考節(jié)點之間的精確的時間同步，非精確的時間同步將導(dǎo)致UWB系統(tǒng)的定位誤差。假設(shè)ka和kb為兩節(jié)點實際時鐘頻率和期望時鐘頻率之比，則真實信號飛行時間為：

(5)

假設(shè)無線信號的飛行速度為c，則測距誤差可寫為：

(6)

響應(yīng)時間分別為50 μs、100 μs、200 μs時不同時鐘差與測距誤差之間的關(guān)系如圖3所示。從圖中可以看出，響應(yīng)時間及時鐘差均與測距誤差成正比[22]，響應(yīng)時間越短，時鐘差越小，則測距誤差越小。由于響應(yīng)時間的大小無法人為控制，本文選擇通過降低時鐘差來提高精度。

圖3 不同ka-kb下的測距誤差

2 改進方案

改進方案分為兩部分，先通過洪泛機制實現(xiàn)時鐘準同步，在此基礎(chǔ)上再進行時隙分配。接下來對這兩部分進行詳細介紹。

2.1 時鐘準同步

洪泛算法是一種無線傳感器網(wǎng)絡(luò)領(lǐng)域常用的算法，它可以通過單個同步分組實現(xiàn)節(jié)點對之間的同步，具有魯棒性好、適應(yīng)性強的優(yōu)點。本文采用了洪泛算法，需要設(shè)定一個主基站，其余基站均為被分配適應(yīng)級別的從基站?；诤榉簷C制準同步的UWB定位整體流程如下：

Step1：主機站作為時間基準點向空間內(nèi)廣播發(fā)送包含當前時鐘讀數(shù)的SYN消息；

Step2：從基站和標簽接收到SYN消息后估算時延等參數(shù)并調(diào)整自身邏輯時鐘值以和基準點達成同步；

Step3：達成同步后的從基站或標簽以自身為新的基準點一環(huán)一環(huán)向外同步，實現(xiàn)所有從基站、標簽與主基站時鐘準同步；

Step4：標簽與距離最近的基站通信，在接收到基站發(fā)出的注冊表后，記錄發(fā)送時間戳Trng_tx，給基站回復(fù)RNG消息；

Step5：基站接收到RNG消息后記錄接收時間戳Trng_rx，記錄發(fā)送時間戳Tres_tx并給標簽回復(fù)RES消息；

Step6：標簽接收到RES消息后記錄接收時間戳Tres_rx，記錄發(fā)送時間戳Tfin_tx后將消息裝填入FIN消息中并發(fā)送；

Step7：基站接收到FIN消息后記錄Tfin_rx，根據(jù)解析FIN消息獲得的6個時間戳運用DS-TWR算法求解測距距離；

Step8：由于標簽所在范圍內(nèi)基站坐標已知，根據(jù)測得的標簽到各基站的距離可求解定位空間內(nèi)各標簽的位置；

假設(shè)經(jīng)過3次洪泛傳播后標簽與基站開始測距，主基站為0級，從基站可分為1級和2級，改進后的DS-TWR算法測距流程如圖4所示。

圖4 改進DS-TWR算法示意圖

洪泛機制中存在的最大問題是基站一級一級向下傳遞會產(chǎn)生誤差的積累，而累計誤差會影響系統(tǒng)的測距效果。若此處標簽是與主基站通信，則時延和硬件帶來的誤差會累計3次，這將極大影響測距效果。但是在本方案中，標簽只需要與相鄰的基站進行測距交互，不受累計誤差的影響。

改進后的DS-TWR算法利用洪泛機制實現(xiàn)了標簽和基站之間的時鐘準同步，在一定程度上提高了TOA算法的測距精度，同時為接下來的時隙分配法奠定了基礎(chǔ)。

2.2 時隙分配法

散列算法又稱哈希算法或雜湊算法，是一種從任意文件中創(chuàng)造小的數(shù)字的方法。本文采用散列算法實現(xiàn)了科學(xué)的時隙分配，解決UWB通信中多標簽情況下的通信沖突問題。

由于通信分配沒有協(xié)調(diào)好，會經(jīng)常出現(xiàn)通信沖突：多個標簽同時向一個基站通信，先與基站交互的標簽先通信，后到的標簽必須要等一定的響應(yīng)時間后才能與其他基站通信，這樣導(dǎo)致基站與標簽之間通信速度慢，系統(tǒng)反應(yīng)慢。假設(shè)在有定位需求的場所中有基站m個(m>3)，標簽n個。在主基站發(fā)送SYN報文通過洪泛機制實現(xiàn)標簽和基站、基站和基站之間的時鐘準同步后，基站側(cè)以發(fā)送SYN報文的時刻作為循環(huán)周期起始時刻，標簽側(cè)以收到SYN報文的時刻作為的循環(huán)周期起始時刻，忽略掉信號在空中的傳播時間；從起始時刻開始，設(shè)置一個時隙段，通過Hash運算后得到的散列序號給每個標簽和基站分配不同的時隙，圖5為時隙分配流程圖。

圖5 時隙分配流程圖

本文采用的Hash算法為除留余數(shù)法，其計算方法如下：該標簽所得基站列表即為m個基站的列表A[1…m]，該列表為基站的序號列表，且所有標簽列表一致；若M>5,首先對列表A[1…m]進行散列，得到5個下標I[1…5]，第一次定位需要至少4個基站，并設(shè)置一個冗余基站：

I[i]=((TID+7)*i)%5,i=1，...，5

(7)

THash1(TID)={(TID+Q)*A[I[i]]}%P，

i=1，...，5

(8)

式(15)中，TID為標簽的序列號，P表示幀的長度，此處P取大小接近幀長度的質(zhì)數(shù)目的是為了均勻分配時隙，保證運算效果。A[I[i]]為散列后的基站序列號；Q為任意取值的質(zhì)數(shù)，目的是為了讓得到的時隙號能夠散列開。

在經(jīng)過一次hash計算后，標簽之間依舊可能存在沖突。當再次遇到?jīng)_突時引入上次散列后的結(jié)果再次進行散列，直至沖突消失，計算公式如下：

THashj(TID)={(TID+Q+THashj-1)*A[I[i]]}%

[P+THashj-1]

i=1，...，5,j為大于1的正整數(shù)

(9)

在實際工程領(lǐng)域中具體時隙段格式如下：

R0|T0[1] |T0[2] |...|T0[31] |R2|T1[1] |T1[2] |...|T1[31] | 。

其中:N為洪泛次數(shù)，R0和R1為冗余時隙，基站和標簽在冗余時隙中進行時鐘準同步；測距時隙為T0和T1，在測距時隙中標簽和基站通信記錄收發(fā)時間戳。

時隙分配如圖6所示，通過多次Hash運算分配時隙能夠顯著降低標簽之間以及標簽和基站之間的通信沖突，有效增加系統(tǒng)中標簽的容量。

圖6 時隙分配示意圖

3 軟件設(shè)計

定位系統(tǒng)由上位機和下位機兩部分組成，上位機采用Ubuntu系統(tǒng)編寫，在將上報的測距信息記錄進數(shù)據(jù)庫后，根據(jù)庫中數(shù)據(jù)解析出目標位置；下位機采用Keil uVision5軟件編寫，負責點對點之間的測距。下位機主要通過3個定時器控制測距流程：定時器1控制整個測距周期，定時向上位機發(fā)送測距結(jié)果；定時器2控制基站定時廣播blk消息發(fā)起測距，由標簽先發(fā)出測距信息，通過裝填測距信息中的注冊表記錄每次收發(fā)的時間戳，完成測距信息交互后基站根據(jù)注冊表中信息可計算出點對點間的距離；為防止出現(xiàn)標簽老化，設(shè)定定時器3定時等待應(yīng)答，若無應(yīng)答則重新發(fā)起測距。下位機基站和標簽測距流程如圖7、圖8所示。

圖7 標簽測距流程

圖8 基站測距流程

為了方便在上位機實時定位目標的位置，通過QT軟件設(shè)計室內(nèi)定位人員軌跡展示界面。一只手舉著標簽在定位區(qū)域內(nèi)以約1.5 m/s的速度快速移動獲得的定位軌跡如圖9所示，標簽軌跡基本符合人員實際活動軌跡。

圖9 室內(nèi)定位人員軌跡展示圖

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

為了驗證優(yōu)化效果，搭建了相應(yīng)的實驗環(huán)境并對改進后的系統(tǒng)進行了測試。

4.1 實驗環(huán)境的搭建

以STM32高性能微處理器和DWM1000射頻收發(fā)芯片為基礎(chǔ)，結(jié)合各種外圍電路設(shè)計了室內(nèi)定位系統(tǒng)硬件平臺，主要包括測距模塊、stm32主控制模塊、數(shù)據(jù)傳輸模塊和指示模塊。相對于標簽而言，基站處理的任務(wù)更多，因此基站采用性能較高的STM32F407ZET6處理器，標簽采用性能較低的STM32F105RCT6處理器。

4.2 功耗實驗

在多標簽與單基站通信的情況下，某一時刻多個標簽同時向基站發(fā)出通信請求，此時只有第一個與基站通信的標簽發(fā)出的請求有效，其余標簽發(fā)出的請求均為無效。假設(shè)1個基站與50個標簽通信，若要所有標簽都與基站完成通信則共計需發(fā)出1 275次通信請求，這就大大提高了系統(tǒng)的功耗。而本文提出的時隙分配法可以使標簽按順序與基站通信，大量減少了無效通信的次數(shù)。在1個基站與50個標簽通信的情況下標簽僅需發(fā)出50次通信請求，這就極大地降低了功耗。

功耗實驗測試改進前后多標簽情況下系統(tǒng)中某一標簽從滿電到電量耗盡過程中的樣本數(shù)量和通信時長。實驗采用1 700毫安的鋰電池給標簽供電，在給所有電池充滿電后，測試改進前后4個基站與20個標簽在通信距離相同的情況下系統(tǒng)中某一標簽的功耗情況。圖10和11為改進前后系統(tǒng)在單基站多標簽情況下通信獲得的測距數(shù)據(jù)分析圖，其中橫坐標為樣本數(shù)量，縱坐標為標簽與基站間距離。

圖10 改進前的測距信息

圖11 改進后的測距信息

改進前后方案對比數(shù)據(jù)如表1所示，改進后系統(tǒng)中標簽?zāi)芎南鄬Ω倪M前降低了30%，單位時間內(nèi)獲取數(shù)據(jù)量提高了27.8%。實驗結(jié)果證明，改進后的方案功耗更低，獲得數(shù)據(jù)更多，且測距效果不會受標簽剩余電量影響產(chǎn)生大幅波動，系統(tǒng)魯棒性得到了提升。

改進前后通信時長和單位時間內(nèi)通信次數(shù)提升效率表達式如下所示：

Ph=(h2-h1)/h2*100%

(10)

PN=(N2-N1)/N2*100%

(11)

式中,h1和h2分別為改進前后的通信時長；N1和N2分別為改進前后的單位時間內(nèi)的通信次數(shù)。

表1 方案對比數(shù)據(jù)表

4.3 通信成功率實驗

標簽通信流程如下：在時鐘準同步后，各標簽與4個末級基站依次通信，若基站a與標簽a處于通信狀態(tài)時，標簽b向基站a發(fā)出通信請求，則記為一次沖突；標簽b在等待1秒后向基站b發(fā)出通信請求，若基站b也處于通信狀態(tài)，則記為二次沖突；繼續(xù)等待1秒后再與下一個基站通信……依此類推，直至成功與某一基站進入通信狀態(tài)。

針對通信成功率進行仿真實驗，設(shè)定從200個標簽和50個基站中隨機選擇5個基站，20個標簽進行十萬次通信。如圖12所示為對改進前數(shù)據(jù)做的直方概率圖，圖中橫坐標為對應(yīng)每一次通信的通信成功率，左側(cè)坐標為通信次數(shù)，右側(cè)縱坐標為累計百分比。改進前在發(fā)生沖突情況下通信成功率最高80%，最低40%，平均通信成功率僅有62%，通信成功率較低，數(shù)據(jù)丟包嚴重。

圖12 改進前

保持條件不變，對改進后的代碼進行仿真，對仿真后得到的數(shù)據(jù)集作直方概率圖如圖13所示。改進后通信成功率最高為100%，最低為60%，平均通信成功率達到了78%，相較于改進前提高了16%，系統(tǒng)在多標簽情況下的通信成功率得到了顯著提高。

圖13 改進后

5 結(jié)束語

針對UWB定位中的標簽容量限制和通信沖突的問題，提出了一種基于洪泛機制準同步的改進定位方法。利用洪泛機制實現(xiàn)了系統(tǒng)內(nèi)所有設(shè)備間的時鐘準同步，一方面滿足了TOA算法對基站和標簽時鐘準同步的需求，在一定程度上提高了測距精度；另一方面為時隙分配法奠定了基礎(chǔ)。針對多標簽情況下易產(chǎn)生沖突的問題，提出一種基于Hash運算的時隙分配法，在時鐘準同步后通過Hash運算給每個標簽分配唯一的時隙編號，有效降低了多標簽下的沖突率，使得通信成功率大大提高。