室內(nèi)定位系統(tǒng)中基于最短路徑算法的同步鏈自動生成

蔣汝雯，樓喜中，金 寧，葉凱楓，王戍斌

(中國計量大學(xué)信息工程學(xué)院，浙江省電磁波信息技術(shù)與計量檢測重點實驗室，浙江 杭州 310018)

無線定位系統(tǒng)利用已知位置的基站節(jié)點與待測節(jié)點之間的信息交互計算待測節(jié)點的位置，在物聯(lián)網(wǎng)中的應(yīng)用日益廣泛。系統(tǒng)定位性能與基站同步精度密切相關(guān)，特別是對于基于時間測量原理的定位系統(tǒng)，例如，在基于到達時間差(Time Difference of Arrival，TDoA)的超寬帶厘米級定位系統(tǒng)中，1ns的時間測量誤差可能導(dǎo)致30 cm定位誤差[1]。因此，基站間高精度的時間同步是提高TDoA定位性能的關(guān)鍵。

基站的同步采用有線方式，通過部署一個參考時鐘及傳輸設(shè)備統(tǒng)一全網(wǎng)時鐘來同步[2]，但該方式需布設(shè)大量電纜連接所有基站，施工不便且成本高昂。無線定位系統(tǒng)更傾向于采用無線同步方式，即基站節(jié)點通過無線信號傳遞時間戳[3－4]，基于某種規(guī)則、協(xié)議和算法實現(xiàn)時鐘分布式同步[5]。通過傳遞時間戳消息實現(xiàn)節(jié)點時鐘同步已經(jīng)有較多的研究，典型同步協(xié)議有:傳感器網(wǎng)絡(luò)時間同步協(xié)議(timing-sync protocol of sensor network，TPSN)[6]、泛洪時間同步協(xié)議(flooding time synchronization protocol，F(xiàn)TSP)[7]、參考廣播同步算法(reference broadcast synchronization，RBS)[8]、IEEE 1588V2協(xié)議[9]等，上述協(xié)議同步精度僅達微秒級，不適合用于同步精度要求高達納秒級的定位系統(tǒng)。

基于TDoA的無線定位系統(tǒng)一般由主基站提供全網(wǎng)參考時間，其余基站通過其父基站逐級同步于主基站。O.Jean等人討論了可擴展網(wǎng)絡(luò)及其在參考時間下的同步算法[10－11]；也有文獻研究基站擺放的幾何問題[12]和多基站的同步協(xié)調(diào)問題[13－14]；彭鐸等人通過優(yōu)化基站間跳數(shù)和距離提高同步精度[15]，還可利用基站間的分組通信獲得經(jīng)驗值建立延遲估計模型[16]。上述研究著眼于在已確定的同步路徑下，如何更精確地計算傳播時延、糾正基站之間時鐘偏差和漂移。而如何確定父子基站，生成每個基站的同步路徑卻鮮有文獻涉及。目前對于小規(guī)模無線定位系統(tǒng)，基本是由人工根據(jù)經(jīng)驗指定每個基站的同步鏈。該方法存在效率低、不能動態(tài)自動規(guī)劃調(diào)整、同步質(zhì)量非最優(yōu)等問題，對于大規(guī)模定位系統(tǒng)這些問題尤為突出。故如何合理高效地自動生成同步鏈是無線定位系統(tǒng)一個亟待解決的重要工程問題。

本文針對無線定位系統(tǒng)基站之間精確同步的需求，提出一種自動高效生成基站同步鏈的方法。該方法采用基站間測距方式獲得通信質(zhì)量參數(shù)，將該參數(shù)作為父子基站成立的判據(jù)，并量化為兩個節(jié)點的邊的權(quán)重，構(gòu)建同步網(wǎng)絡(luò)圖。再將基站同步鏈生成問題抽象為有向圖的單源最短路徑問題，采用Dijkstra算法和Viterbi算法實現(xiàn)了自動解算。

1 定位系統(tǒng)同步模型

本文研究針對如圖1所示的定位系統(tǒng)模型，在特定區(qū)域內(nèi)部署位置已知的基站作為定位節(jié)點，這些基站根據(jù)同步關(guān)系分為參考基站、中繼基站和普通基站。參考基站是唯一指定的，是系統(tǒng)參考時間的來源；中繼基站將相對于參考基站的時鐘偏移通過時分方式廣播。除參考基站外，其余基站處理父基站的廣播信息，完成與參考基站同步，從而實現(xiàn)全網(wǎng)同步。服務(wù)器和參考基站以有線方式相連，實現(xiàn)對定位系統(tǒng)的控制、計算和管理。

圖1 定位系統(tǒng)基站同步模型

在圖1的模型中，每個基站都有唯一的一條同步鏈。由于基站在物理空間的位置不同且存在環(huán)境障礙物阻擋等因素，使得基站之間的無線信道質(zhì)量差異比較大，甚至有些基站之間通信不可達。用一個分層的網(wǎng)狀圖來描述基站之間可能形成的同步路徑，如圖2所示，假設(shè)參考基站A1作為第一層，與A1能夠直接通信的基站作為第二層，如圖中的A2、A3、A4，能與第二層基站直接通信的基站作為第三層，如圖中的A5、A6、A7。如此，以A1為起始節(jié)點，將所有基站之間可能構(gòu)成的同步路徑用線連接，構(gòu)建出系統(tǒng)的同步網(wǎng)絡(luò)圖。在同步網(wǎng)絡(luò)圖中以某種規(guī)則或算法確定每個基站的父基站，即為形成同步鏈的過程，圖3是由圖2生成的一個同步鏈示例。

圖2 同步網(wǎng)絡(luò)圖

圖3 同步鏈圖

基于以上模型部署的定位系統(tǒng)在執(zhí)行定位任務(wù)之前，需要完成基站時鐘同步，同步流程如下:①構(gòu)建同步網(wǎng)絡(luò)圖；②生成同步鏈，同步鏈的計算由服務(wù)器端完成；③服務(wù)器發(fā)送父基站配置指令至參考基站，從參考基站開始以多級透傳方式下發(fā)父基站配置信息至每個基站，并確認成功；④各個基站配置父基站。所有基站完成父基站配置后，服務(wù)器發(fā)送同步指令；⑤基站接收父基站的同步信息，調(diào)整時鐘偏移，實現(xiàn)全網(wǎng)基站自動時鐘同步。本文主要研究同步網(wǎng)絡(luò)圖的構(gòu)建方法，以及基于同步網(wǎng)絡(luò)圖的最佳同步鏈獲取算法。

2 同步網(wǎng)絡(luò)圖的構(gòu)建

2.1 父子基站的評判標準

工程上，基站之間的真實距離是恒定且已知的，在基站配置參數(shù)(如晶振相對抖動等)固定的前提下，父子基站之間的信道質(zhì)量越好意味著時間戳的接收越及時準確，是保障時鐘同步精度的關(guān)鍵因素。接收信號強度在發(fā)送功率一致時，可以表示單向信道質(zhì)量，基站之間測距的有效性和準確性可以表征雙向信道質(zhì)量。據(jù)此，本文選擇了接收信號強度(Received Signal Strength Indicator，RSSI)、測距誤差和標準差、測距次數(shù)和成功率等參數(shù)作為父子基站成立的評判依據(jù)，為每個參數(shù)設(shè)置閾值作為評判標準，如表1所示。兩基站之間所有參數(shù)都滿足表1設(shè)定的閾值，才可能成為父子基站。

表1 評價標準

由于距離或障礙物影響可能導(dǎo)致兩基站間的測距失敗[17]。在RT次測距中，假設(shè)成功次數(shù)為ST，測距成功率定義為:

測距成功率的閾值根據(jù)工程經(jīng)驗，本文設(shè)定為100%。測距誤差和標準差的閾值設(shè)定可以根據(jù)系統(tǒng)的同步精度要求推算?；就骄仁芟抻诨揪д窆逃械南鄬Χ秳?，如果晶振相對抖動為10－6fs，則同步精度理論上只能達到103fs(ns)。假定系統(tǒng)要求達到的同步精度為ASync(ns)，C為光速，RT為測距次數(shù)，則測距誤差和標準差分別為:

本文實驗中，使用規(guī)格fs＝10－4ppm的晶振，設(shè)定系統(tǒng)同步精度要求是ASync≤0.4 ns，取ASync＝0.4 ns，測距次數(shù)RT＝100次，經(jīng)計算可得測距誤差和標準差的閾值分別為:Demax＝12 cm，Dsmax＝1.2 cm。

接收信號強度的閾值定義為[18]，

式中:P T為發(fā)射信號功率，f c為信道中心頻率，D為發(fā)送和接收端的距離。實驗選取f c＝4 GHz，P T＝10 dBm，D＝10 m，則RSSImin＝－34.4 dB。

基于以上參數(shù)，本文定義兩基站的通信質(zhì)量量化值q計算如下:

式中:d e是兩基站的實際測距誤差。q越小表示兩基站通信質(zhì)量越好，不滿足表1條件基站的q視為∞。

2.2 同步網(wǎng)絡(luò)圖的形成

2.2.1 TWR方法

對于一個無線定位系統(tǒng)，獲得基站間通信質(zhì)量的一個通常方法是雙邊測距(Two-Way Ranging，TWR)[19]，即基站之間兩兩測距。設(shè)共有N個基站，每個有效測距結(jié)果通過RT次測距取平均值得到，總測距次數(shù)記為W，有:

由式(6)可得TWR方法測距次數(shù)與基站數(shù)量的平方成正比。為降低測距次數(shù)，本文提出全信息圖(full information graph，F(xiàn)IG)方法。

2.2.2 FIG方法

FIG方法的思路是提前找到無法通信的基站對，避免大量無效測距，從而縮短同步網(wǎng)絡(luò)圖的生成時間。利用廣播幀測試可以找到這些基站對:一個基站多次發(fā)送廣播幀，若另一個基站接收不到，則這兩個基站可視為非通信基站對。在FIG方法中，首先利用廣播幀快速找到非通信基站對，然后僅對通信基站對進行雙邊測距，得到基站間的通信質(zhì)量量化值，從而生成同步網(wǎng)絡(luò)圖。方法1給出了FIG的生成步驟，表2為方法1中出現(xiàn)的符號及含義。

方法1 FIG的生成

表2 符號說明

假設(shè)共有N個基站，一個基站可以與8個基站通信[20]，分成N/8層，每層基站C28×N/8測距組合；共有(N/8－1)個上下層之間互相測距，每兩層之間的測距組合為82；均測距RT次。假設(shè)發(fā)送BT次廣播幀，由于廣播所需時間約為測距所需時間的1/4，將發(fā)送的廣播幀折算為BT×N/4測距幀。計算層數(shù)時，不能整除時均向上取整且忽略參考基站。則FIG方法總測距次數(shù)W為:

測距完成后，按照表1的限制條件篩選出可能的父子基站對，利用式(5)計算通信質(zhì)量量化值，即完成了FIG的構(gòu)建。

2.2.3 KIG方法

兩對通信質(zhì)量相近的基站，同步精度差異可忽略不計。若基站與同層基站的通信質(zhì)量和另不同層基站相近，則可以忽略同層之間的連接，進一步簡化同步網(wǎng)絡(luò)圖?；诖?，本文提出了關(guān)鍵信息圖(key information graph，KIG)方法，如方法2。

方法2 KIG的生成

KIG消除了同層之間的連接，進一步減少了測距次數(shù)。與FIG相比，取消了每層的基站組合N/8。因此，KIG的總測距次數(shù)為:

3 基站同步鏈的生成

將圖中基站視為節(jié)點，參考基站為源節(jié)點，兩個基站間的通信質(zhì)量q視為節(jié)點的邊的權(quán)值，則同步網(wǎng)絡(luò)圖可視為賦權(quán)有向圖，最佳同步鏈問題即抽象為有向圖的單源最短路徑問題。

3.1 經(jīng)典Dijkstra算法

由荷蘭計算機科學(xué)家E.W.Dijkstra提出的經(jīng)典Dijkstra算法能有效解決有向圖最短路徑問題。該算法基于貪心思想找到從源節(jié)點到其他節(jié)點的最短路徑，產(chǎn)生一個最短路徑樹(最佳同步鏈)。針對FIG，經(jīng)典Dijkstra算法[21]求解基站同步鏈的步驟如下:

Vi:第i個節(jié)點；V0:源點；S:獲得最短路徑的節(jié)點；T:尚未獲得最短路徑的節(jié)點

Step 1 初始化:S＝{V0}

Step 2 從T中選取一個與S中有連線且權(quán)值最小的節(jié)點Q，加入S；修改T中節(jié)點的距離值:加入中間節(jié)點Q，從V0到Vi的距離值縮短，則修改成功。

Step 3 重復(fù)上述步驟step2，直到S中包含所有節(jié)點。

3.2 優(yōu)化的Dijkstra算法

基站在實際部署中遵循“僅夠用”原則，故同步網(wǎng)絡(luò)圖是稀疏圖?；谙∈鑸D論，本文采用堆優(yōu)化方案，降低經(jīng)典Dijkstra算法的復(fù)雜度。優(yōu)化部分說明如下:首先，將所有頂點設(shè)置為一個小的頂部堆，此時堆頂部必須是起點。在每次迭代中，將堆的頂部元素取出，然后調(diào)整堆。重復(fù)多次，直到將堆中的所有頂點都添加到S。在此基礎(chǔ)上，還可以使用二項式或斐波那契堆降低復(fù)雜度[22]。

3.3 Viterbi算法

Viterbi算法是基于動態(tài)規(guī)劃的思想，它用于查找符合隱馬爾可夫模型的最短路徑[23]。KIG特點為同層之間無連接，符合隱馬爾可夫模型，可以用Viterbi算法解算出最佳同步鏈。

如圖4所示，Viterbi算法的流程如下:

圖4 KIG的同步網(wǎng)絡(luò)圖解算

Step 1 從點S0開始。對于第一層中的兩個節(jié)點，計算它們的權(quán)重q(S0，A1)，q(S0，A2)。

Step 2 計算S0到B層所有節(jié)點的最短距離:min[q(S0，Bj)]＝q(S0，Ai)＋q(Ai，Bj)，i，j＝1，2，3。

Step 3 計算S0到C層所有節(jié)點的最短距離:min[q(S0，C j)]＝q(S0，Bi)＋q(Bi，Cj)，i，j＝1，2，3。

以上計算過程表明，當同步網(wǎng)絡(luò)圖有m層，每層有n個節(jié)點時，算法的復(fù)雜度為O(m×n2)。

4 復(fù)雜度和性能分析

本節(jié)主要討論FIG和KIG這兩種同步鏈生成方法的同步性能，測距復(fù)雜度，以及相應(yīng)的最短路徑算法復(fù)雜度。其中，父子基站評價標準僅改變同步網(wǎng)絡(luò)圖的權(quán)值數(shù)值，不改變相對大小，因此不影響同步鏈和同步精度。

4.1 FIG和KIG的性能差異分析

TWR和FIG最終生成的都是全信息圖，而KIG取消了同層基站的有向連接，部分信息的丟失可能會導(dǎo)致依據(jù)KIG生成的同步鏈是次優(yōu)同步鏈。假設(shè)同步網(wǎng)絡(luò)圖如圖5所示，實線表示不同層基站之間的連接，虛線表示同層之間的連接；每條邊的權(quán)重如表3所示。

圖5 同步網(wǎng)絡(luò)圖

在本例中，根據(jù)表3和圖5，F(xiàn)IG和KIG用經(jīng)典Dijkstra算法，最后均獲得了如圖6所示的同步鏈。FIG與KIG相比，F(xiàn)IG的生成復(fù)雜度遠高于KIG，二者最后獲得的最佳同步鏈基本等價。

表3 圖5各條邊的權(quán)重

圖6 FIG/KIG方法的最短路徑結(jié)果

4.2 生成同步網(wǎng)絡(luò)圖的測距次數(shù)分析

假定基站數(shù)量N＝1000，測距次數(shù)結(jié)果如表4所示。與TWR相比，F(xiàn)IG和KIG的復(fù)雜度從N2降低到N；FIG的測距效率提高了97.8%，KIG提高了98.6%，KIG比FIG少了4×105次測距。

表4 三種方案測距次數(shù)的比較

圖7繪制了TWR、FIG和KIG三種方法的總測距次數(shù)隨基站數(shù)量增大的變化趨勢，可以看出，隨著基站規(guī)模的增大，F(xiàn)IG和KIG可以顯著提高同步網(wǎng)絡(luò)圖的生成效率。由于取消了部分有向連接，KIG在大規(guī)模系統(tǒng)更具有優(yōu)勢。

圖7 比較不同方法的測距次數(shù)

4.3 基站同步鏈解算的復(fù)雜度分析

表5對比了FIG和KIG兩種方案適用的最佳同步鏈生成算法的復(fù)雜度。基站數(shù)量為N，邊的數(shù)量為M，假定N＝1000，則M＝W/RT。根據(jù)式(7)和式(8)，以及Vterbi算法推導(dǎo)可知KIG中m＝125，n＝8。

表5 比較求解算法的復(fù)雜度

優(yōu)化后的Dijkstra算法復(fù)雜度從N2降低到到N，Vterbi算法則只與每層基站數(shù)量相關(guān)。對于FIG的最佳同步鏈解算，優(yōu)化的Dijkstra算法復(fù)雜度比經(jīng)典算法低96.4%。對于KIG，優(yōu)化后Dijkstra算法的復(fù)雜度比經(jīng)典Dijkstra算法低97.6%，Viterbi算法的復(fù)雜度比經(jīng)典Dijkstra算法低99.2%。

圖8繪制了FIG和KIG最佳同步鏈的計算復(fù)雜度和相應(yīng)計算時間隨基站數(shù)量增大的變化趨勢。由圖可知，KIG-Viterbi的復(fù)雜度最低。這是因為KIG與FIG相比，忽略了同層之間的連接，減少了有向圖中邊的數(shù)量，從而減少了搜索路徑數(shù)，且Viterbi算法是基于動態(tài)規(guī)劃進行路徑搜索，其效率更高，當基站數(shù)量達到1000時，計算時間僅為1.8 s。結(jié)合第4.2節(jié)的結(jié)論，我們得出KIG-Viterbi是針對大規(guī)模定位系統(tǒng)最佳同步鏈路解算的高性能方法。

圖8 比較求解算法的復(fù)雜度和運行時間

5 結(jié)論

針對大規(guī)模無線定位系統(tǒng)中基站同步問題，提出了一種最佳同步鏈的自動生成方法。該方法首先將基站間的測距結(jié)果量化為無線鏈路的通信質(zhì)量，并以基站為節(jié)點、父子基站之間的連接為邊、以通信質(zhì)量為邊的權(quán)重，構(gòu)建基站同步網(wǎng)絡(luò)圖的數(shù)學(xué)模型。提出了FIG和KIG兩種同步網(wǎng)絡(luò)圖的構(gòu)建方案，與常規(guī)的TWR相比，有效減少了測距次數(shù)，提高了同步網(wǎng)絡(luò)圖的生成效率。

基于生成的同步網(wǎng)絡(luò)圖，將最佳同步鏈問題抽象為有向圖的單源最短路徑問題。通過優(yōu)化的Dijkstra算法和Viterbi算法分別求解FIG和KIG的最短路徑，快速準確地實現(xiàn)基站最佳同步鏈的解算。該方法生成的同步鏈在環(huán)境因素和基站規(guī)模變動時，可以實現(xiàn)動態(tài)自適應(yīng)調(diào)整。

本文提出方法的實用性和有效性已經(jīng)在實際工程中得到檢驗。在總面積約7200 m2的兩層地下車庫鋪設(shè)121個基站，采用DW1000芯片，UWB信號的中心頻率為4 GHz。系統(tǒng)采用KIG-Viterbi方式，用時2 min完成同步鏈計算和配置。最終同步精度為0.4 ns，系統(tǒng)達到的定位精度為0.5 m。