室內定位系統中基于最短路徑算法的同步鏈自動生成

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

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

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

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

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

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

1 定位系統同步模型

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

圖1 定位系統基站同步模型

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

圖2 同步網絡圖

圖3 同步鏈圖

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

2 同步網絡圖的構建

2.1 父子基站的評判標準

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

表1 評價標準

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

測距成功率的閾值根據工程經驗，本文設定為100%。測距誤差和標準差的閾值設定可以根據系統的同步精度要求推算。基站同步精度受限于基站晶振固有的相對抖動，如果晶振相對抖動為10－6fs，則同步精度理論上只能達到103fs(ns)。假定系統要求達到的同步精度為ASync(ns)，C為光速，RT為測距次數，則測距誤差和標準差分別為:

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

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

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

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

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

2.2 同步網絡圖的形成

2.2.1 TWR方法

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

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

2.2.2 FIG方法

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

方法1 FIG的生成

表2 符號說明

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

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

2.2.3 KIG方法

兩對通信質量相近的基站，同步精度差異可忽略不計。若基站與同層基站的通信質量和另不同層基站相近，則可以忽略同層之間的連接，進一步簡化同步網絡圖。基于此，本文提出了關鍵信息圖(key information graph，KIG)方法，如方法2。

方法2 KIG的生成

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

3 基站同步鏈的生成

將圖中基站視為節點，參考基站為源節點，兩個基站間的通信質量q視為節點的邊的權值，則同步網絡圖可視為賦權有向圖，最佳同步鏈問題即抽象為有向圖的單源最短路徑問題。

3.1 經典Dijkstra算法

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

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

Step 1 初始化:S＝{V0}

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

Step 3 重復上述步驟step2，直到S中包含所有節點。

3.2 優化的Dijkstra算法

基站在實際部署中遵循“僅夠用”原則，故同步網絡圖是稀疏圖。基于稀疏圖論，本文采用堆優化方案，降低經典Dijkstra算法的復雜度。優化部分說明如下:首先，將所有頂點設置為一個小的頂部堆，此時堆頂部必須是起點。在每次迭代中，將堆的頂部元素取出，然后調整堆。重復多次，直到將堆中的所有頂點都添加到S。在此基礎上，還可以使用二項式或斐波那契堆降低復雜度[22]。

3.3 Viterbi算法

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

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

圖4 KIG的同步網絡圖解算

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

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

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

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

4 復雜度和性能分析

本節主要討論FIG和KIG這兩種同步鏈生成方法的同步性能，測距復雜度，以及相應的最短路徑算法復雜度。其中，父子基站評價標準僅改變同步網絡圖的權值數值，不改變相對大小，因此不影響同步鏈和同步精度。

4.1 FIG和KIG的性能差異分析

TWR和FIG最終生成的都是全信息圖，而KIG取消了同層基站的有向連接，部分信息的丟失可能會導致依據KIG生成的同步鏈是次優同步鏈。假設同步網絡圖如圖5所示，實線表示不同層基站之間的連接，虛線表示同層之間的連接；每條邊的權重如表3所示。

圖5 同步網絡圖

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

表3 圖5各條邊的權重

圖6 FIG/KIG方法的最短路徑結果

4.2 生成同步網絡圖的測距次數分析

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

表4 三種方案測距次數的比較

圖7繪制了TWR、FIG和KIG三種方法的總測距次數隨基站數量增大的變化趨勢，可以看出，隨著基站規模的增大，FIG和KIG可以顯著提高同步網絡圖的生成效率。由于取消了部分有向連接，KIG在大規模系統更具有優勢。

圖7 比較不同方法的測距次數

4.3 基站同步鏈解算的復雜度分析

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

表5 比較求解算法的復雜度

優化后的Dijkstra算法復雜度從N2降低到到N，Vterbi算法則只與每層基站數量相關。對于FIG的最佳同步鏈解算，優化的Dijkstra算法復雜度比經典算法低96.4%。對于KIG，優化后Dijkstra算法的復雜度比經典Dijkstra算法低97.6%，Viterbi算法的復雜度比經典Dijkstra算法低99.2%。

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

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

5 結論

針對大規模無線定位系統中基站同步問題，提出了一種最佳同步鏈的自動生成方法。該方法首先將基站間的測距結果量化為無線鏈路的通信質量，并以基站為節點、父子基站之間的連接為邊、以通信質量為邊的權重，構建基站同步網絡圖的數學模型。提出了FIG和KIG兩種同步網絡圖的構建方案，與常規的TWR相比，有效減少了測距次數，提高了同步網絡圖的生成效率。

基于生成的同步網絡圖，將最佳同步鏈問題抽象為有向圖的單源最短路徑問題。通過優化的Dijkstra算法和Viterbi算法分別求解FIG和KIG的最短路徑，快速準確地實現基站最佳同步鏈的解算。該方法生成的同步鏈在環境因素和基站規模變動時，可以實現動態自適應調整。

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