無線時鐘同步算法在UWB定位技術中的研究與應用

羅勃　沈重　朱雨豪

摘 要： 以無線時鐘同步為主，提出一種以卡爾曼濾波算法為基礎的無線時鐘同步算法，同時也分析了無線時鐘不同步的情況及原因，并且使用Hainan?EVK 1.0作為硬件平臺進行了實驗。實驗結果表明，以卡爾曼濾波算法為基礎的無線時鐘同步算法能夠滿足TDOA定位算法的需求。

關鍵詞： UWB； TDOA； 無線時鐘同步算法； 卡爾曼濾波算法

中圖分類號： TN915?34； TN919.72 文獻標識碼： A 文章編號： 1004?373X（2017）06?0031?04

Abstract： Studied for wireless clock synchronization， a wireless clock synchronization algorithm based on Kalman filter algorithm is proposed， and the wireless clock asynchronism and its reason are analyzed. The experiments for the algorithm was carried out with Hainan?EVK1.0. The results show that wireless clock synchronization algorithm based on Kalman filtering algorithm can meet the needs of TDOA location algorithm.

Keywords： UWB； TDOA； wireless clock synchronization algorithm； kalman filtering algorithm

0 引 言

無線定位系統是在指定的空間內通過測量無線電波的物理特性對目標進行實時監控。在室內，基于傳統無線電技術的各類定位解決方案仍然是一個未解決的問題；因為室內信號傳播環境相比室外更加復雜，很難精確分析信號到達時間或到達角度等參數[1]。2007年3月IEEE發布了基于UWB物理層的IEEE 802.15.4a?2007協議標準，這一標準旨在為無線個域網中使用超低數據速率、超低功耗和超低復雜度的器件進行短距離數據傳輸提供支持。IEEE 802.15.4a協議是IEEE 802.15.4協議的修訂版，有兩種物理層實現方式， 即超寬帶技術UWB和 Chirp擴頻（Chirp Spread Spectrum，CSS）技術。IEEE 802.15.4a超寬帶（Ultra Wideband， UWB）基帶如果用于定位，其在精確度、實時性能和數據帶寬等方面具有絕對的優勢。其中，UWB物理層可以工作在1 GHz，3～5 GHz和6～10 GHz這三種頻率范圍， 工作效率高， 即使在較低的發送功率下仍具有較好的魯棒性[2]。而本文的實驗則采用了愛爾蘭Decawave公司生產的DW1000 UWB芯片組，其物理層協議為IEEE 802.15.4a。脈沖無線電超寬帶 （Impulse Radio Ultra?Wideband，IR?UWB）的脈沖寬度僅為納秒級或亞納秒級，響應頻率和脈沖寬度決定了UWB的定位精度在理論上可以達到厘米級。UWB技術實時響應頻率可達到10～40 Hz，而其他定位技術普遍在1 Hz以下； UWB技術抗多徑能力強，且時間分辨率很高，具有一定的穿透能力，這些特點有利于在室內復雜多徑環境中進行實時定位和動態數據收集需求。目前國內UWB技術還主要集中在帶寬應用及高速率接入等方向，UWB RTLS（Real Time Location System）定位技術鑒于其硬件起步較晚，無線時鐘同步[3]、標簽容量模型[4]及網絡可擴展[5]通信協議難點，目前還尚未開展。而本文將針對TDOA定位算法中的無線時鐘同步問題進行研究，并以Hainan EVK 1.0為實驗平臺，驗證改進后的時鐘同步算法的可行性。

1 影響無線時鐘同步的因素及研究現狀

由于每個基站都有自己獨立的時鐘源，使得每個基站測量到的標簽信號到達時間（Time Of Arrival，TOA）沒有一定的聯系，并且每個基站的時鐘源所用的不同晶振都存在不同的頻率偏差，該頻率偏差并不是個常數，而是隨著溫度的變化呈現出非線性變化，所以不同基站的晶振本身存在工藝上的差異和與環境溫度之間的關系特性是影響時鐘同步的主要原因；每個基站的啟動時間不同也會導致標簽信號的到達時間存在差異；如果主從基站的坐標擺放有偏差，或主從基站之間有障礙物阻擋就會導致計算出來的飛行時間不精確，從而影響無線時鐘同步的性能。以上種種原因使得TDOA算法無法正確使用。因為TDOA定位算法要求所有參與定位的基站都基于相同的時鐘基準，使得主從基站之間的時鐘同步顯得尤其重要。

在各類實時定位系統里，數據采集和實時控制必須具有全網統一的時鐘，一旦出現時鐘偏差，就會導致數據失效或控制錯誤。因此系統里各個節點如何保持時鐘同步是關鍵技術問題，國內外文獻提出了大量關于時間同步的算法。自校正的時間同步算法[6]中每個節點根據一個參考時鐘來調整自己時鐘，從而保持時間同步，節點之間無任何信息交換；文獻[7]提出一種基于卡爾曼濾波的并行分布算法，每個節點利用其他節點的估計狀態，投票選出一個虛擬的全局主時鐘，與其保持時間同步；文獻[8]通過兩種具有自適應性的卡爾曼濾波模型來實現時鐘同步，分別為基于最大期望值的遞歸算法與基于假設校驗的自適應多模型算法；文獻[9]利用卡爾曼濾波來跟蹤時間偏移，從同步時間間隔中獲取所需誤差界限，再調整同步時鐘從而保證系統中節點的時間同步；文獻[10]結合傳感器網絡，對現有的時鐘同步協議進行了總結，基于接收者?接收者交換的參考廣播同步技術通過雙向鏈路和信息包的交換實現網絡中節點的時間同步，但該算法只在單跳網絡中才能確保較高的精確度；文獻[11]提出了成對報文時間同步協議，采用層次結構，可以實現整個網絡節點的時間同步；文獻[12]在成對報文時間同步協議基礎上進行改進，使網絡中傳感器節點的能量消耗和平衡時間更加有效；另外，在節點失效、移動及復雜通信環境中，可以使用異步時鐘協議[13]，異步時鐘協議允許網絡中每個節點在任何時間以任何順序跟它的鄰居節點進行時間同步；而洪泛時間同步協議[14]使用廣播消息來實現發送節點和接收節點間的時鐘同步，具有通信帶寬小、精確度高等特點。

本文提出基于卡爾曼濾波的主從基站之間的無線時鐘同步算法，同時還提出了判斷時鐘同步性能的檢測指標。當時鐘校驗包和標簽數據包發生碰撞時，此時的檢測指標將高于預設的閾值從而通過濾波算法將這個錯誤排除，有效地增加算法可靠性。

2 改進的無線時鐘同步算法

本文提出了一種基于改進的卡爾曼濾波的無線時鐘同步算法，指定一個參考“主”基站周期性地向從基站發送時鐘校驗包（Clock Correct Package， CCP）。時鐘校驗包是用來跟蹤從基站的時鐘相對于主基站的時鐘是如何隨著時間變化。標簽向所在標簽發送范圍內的每個基站節點快速發送數據包，并且每個基站以自己的時間戳記錄數據包的到達時間（TOA）。了解基站的時鐘相對于主基站的時鐘是如何隨著時間變化，數據包到達從基站本地時間的修正或轉換成以主基站時間為基準的數據包到達時間，需要知道修正的一個重要組成部分是主基站與從基站之間的固定時間偏移和天線延時時間。固定時間偏移實際上是時鐘校驗包在主基站和從基站之間的飛行時間，這飛行時間可以由已知的主從基站坐標計算得到或是用雙向測距方法測得到，天線延時時間包括天線的傳播時間和信號的調制解調等時間，如圖1所示。

圖1由一個主基站、三個從基站以及標簽組成。主基站定時向從基站發送時鐘校驗包，保證主從基站之間的時鐘同步，也就是說除了主基站外，其他三個從基站都需要通過時鐘同步算法使得自身的時鐘與主基站時鐘同步，與此同時標簽向四個基站發送數據包，其中數據包中包含了標簽的發包序號信息、地址信息等。標簽通過到達時間差的定位方法確定了其自身在該系統中的位置。

由于主從基站晶振的頻率特性、溫度和老化效應的不同，導致晶振頻率會產生漂移，其中晶振的溫度漂移是造成其精確度偏差的主要原因，這使得主從基站的時鐘頻率之間存在偏差。然而，傳輸網絡中的各種干擾使得主從基站時鐘之間的偏差無法進行精確測量。改進后的無線時鐘同步算法采用卡爾曼濾波算法能更精確地估算時間偏差，消除時鐘以及傳輸過程中帶來的干擾。因此將通過卡爾曼濾波算法來使得從基站的時鐘偏移能夠與主基站的時鐘偏移保持一致。卡爾曼濾波是以最小均方誤差為估計的最佳準則，來尋求一套遞推估計的算法，其基本思想是：采用信號與噪聲的狀態空間模型，利用前一時刻的估計值和現時刻的觀測值來更新對狀態變量的估計，求出現時刻的估計值。

在具體的實現過程中，通過第n個同步周期的從基站CCP接收時間的最優估計值和第n+1的預測值精確地估計第n+1個同步周期主從基站的時鐘偏移之間的偏差與漂移。定義T為時鐘同步周期，dt為主基站現時刻CCP發送時間與上一周期時刻CCP發送時間的差值，[θn]，[γn]分別為nT時刻從基站節點的最優估算CCP接收時間值和時鐘漂移值。[θn+1]，[γn+1]分別為（n+1）T時刻從基站節點修正前的預測CCP接收時間和時鐘偏移值。

在（n+1）T時刻，相鄰時鐘同步周期內時鐘偏差與時鐘漂移的關系式為：

通過卡爾曼濾波算法，第n+1時鐘同步周期修正后的[xn+1=θn+1γn+1T]，相應的設置[un+1=xn+1]，對時間偏差以及時鐘漂移進行補償，從而確保主從基站間的時鐘同步。

卡爾曼濾波的計算基于這樣的一個假設：所有的測量結果都是由真實信號和可加性高斯噪聲組成的。如果上述假設成立，卡爾曼濾波可以有效地從含噪聲的測量結果中得到信號信息。但是如果主基站的時鐘同步校正包和標簽含有TOA的數據包產生了碰撞，那么這個假設將不成立。卡爾曼濾波器會把這個碰撞當作可信的時鐘偏差的數據，而以此進行計算。而卡爾曼濾波本身是一種低通濾波器，其反應和修正的速度都較慢。因此，一個由碰撞產生的錯誤會在較長時間內嚴重降低時鐘同步算法的性能。

因此本研究提出了一種對碰撞產生的錯誤的監測以及避免辦法。

卡爾曼增益公式已經由式（9）給出，定義其中一項Y信息矩陣為：

[Y=（Rn+1+Hn+1Pn+1|n（Hn+1）T）-1] （12）

式中，Y用來表示實際時鐘偏差與預測時鐘偏差的差值。這個信息可以用來提示當前的輸入和當前的濾波器狀態的吻合程度：

[OMn+1=（xn+1-xn+1）*Y*（xn+1-xn+1）] （13）

如果偏離指數（Outlier Metric，OM）大于一個預設的閾值，就認為當前輸入不可信，不更新當前狀態，直接丟棄此次數據，從而避免讓錯誤數據包對濾波器造成很大的影響。

3 算法分析

算法的檢驗中，選取13 m[×]7 m[×]3 m的房間為測試環境，而且室內環境都是可視距的，四個基站分別放置四個角落。四個基站分別標注為M1，S2，S3和S4，選取M1為主基站，其余三個為從基站，其電路板圖（四個基站的電路板都一樣）如圖2所示。經過手工準確測量得到各個基站的坐標：M1（1.1， 1.17，1.93），S2（11.3， 1.17，1.21），S3（11.3，5.37，1.95），S4（1.1，5.37，1.22）。主基站到各個從基站的飛行時間分別標注為TOF12、TOF13和TOF14，可經過三角公式計算分別得到TOF12為0.000 000 034 123 193 s，TOF13為0.000 000 036 806 046 s，TOF14為0.000 000 014 223 998 s。對于測量噪聲[vn+1]和過程噪聲[ωn]分別給定一個值為[3×10-20]和[5×10-20]，天線延時時間經過精確測量為0.000 000 258 114 s。在實驗過程中，主基站每隔150 ms進行一次同步數據包（CCP）廣播發送，從基站接收到CCP后，提取CCP包里的CCP發送時間，然后調用卡爾曼濾波算法進行時鐘同步。可根據圖3提供的方法，比較從基站實際時間偏移量和最佳估計時間偏移量的差值，差值越小說明時鐘同步算法的性能越好，如圖3所示。

根據圖3，利用主從基站回傳的CCP發送時間、CCP接收時間和最佳估計時間等數據，得出從基站時間相對偏移量和最佳估計時間相對偏移量，選取從基站S2的數據用Matlab繪制成圖，如圖4所示。

根據圖4可知，藍色線條表示從基站相對時間的偏移量，紅色線條表示最佳估計時間相對偏移量。經過卡爾曼濾波算法后的時鐘同步，紅色線條顯得更平穩些。而藍色線條受到一些噪聲和溫飄的影響顯得波動較大。由圖4中可知道誤差在30 ns左右，但對于光速來說納秒級別的誤差影響也是很大的。所以卡爾曼濾波算法也起到了濾波的作用，使得誤差變得平滑平穩。因此，實驗表明卡爾曼濾波算法的無線時鐘同步可以較好地跟蹤主基站的時鐘偏移，進而得出最佳的預測使得從基站的時鐘和主基站的時鐘基本一致，這很有利于提高標簽的定位精確度。

4 結 論

無線時鐘同步算法通過卡爾曼濾波和遞歸算法，理論上時鐘同步誤差可達到0.1 ns級別，優化了所有基站的時鐘同步。本文提出的新算法在IEEE 802.15.4a UWB技術基礎上，不僅能有效地消除時鐘偏差的測量噪聲，還能通過測量所得的時鐘偏差對時鐘偏差、時鐘漂移以及時鐘漂移變化率進行估計，從而提高系統時鐘同步的精度。另一方面，針對低通濾波算法對偶發錯誤的敏感性，本文提出的檢測算法運行狀態的環節，可以剔除網絡中的碰撞或者接收錯誤給時鐘同步帶來的負面影響，從而增加了系統的容量與可靠性。

參考文獻

[1] HWANG S S， KWON G R， PYUN J Y， et al. AOA selection algorithm for multiple GPS signals [C]// 2013 Asilomar Conference on Signals， Systems and Computers. [S.l.]： IEEE， 2013： 481?485.

[2] SHAH SAADON E I， ABDULLAH J， ISMAIL N. Evaluating the IEEE 802.15.4a UWB physical layer for WSN applications [C]// 2013 IEEE Symposium on Wireless Technology and Applications （ISWTA）. [S.l.]： IEEE， 2013： 68?73.

[3] MCELROY C， NEIRYNCK D， MCLAUGHLIN M. Comparison of wireless clock synchronization algorithms for indoor location systems [C]// 2014 IEEE International Conference on Communications Workshops （ICC）. [S.l.]： IEEE， 2014： 157?162.

[4] CHEN Y， SHEN Y， JIANG X， et al. Throughput capacity of ALOHA MANETs [C]// 2013 IEEE/CIC International Conference on Communications in China. [S.l.]： IEEE， 2013： 71?75.

[5] SHIN W Y， LUCANI D E， MEDARD M， et al. Multi?hop routing is order?optimal in underwater extended networks [C]// IEEE International Symposium on Information Theory. [S.l.]： Institute of Electrical and Electronics Engineers， 2012： 510 ? 514.

[6] WENTAO J， LIMIN S. A prediction based long?cycle time synchronization algorithm for sensor networks [C]// Global Telecommunications Conference. Miami： [s.n.]， 2010： 1?5.

[7] LIU B， REN F， SHEN J， et al. Advanced self?correcting time synchronization in wireless sensor networks [J]. IEEE communications letters， 2010， 14（4）： 309?311.

[8] KIRSCH F， VOSSIEK M. Distributed Kalman filter for precise and robust clock synchronization in wireless networks [C]// Radio and Wireless Symposium. [S.l.]： IEEE， 2009： 482?485.

[9] LUO Yanfen. Research on adaptive information fusion Kalman filter algorithm [C]// 2012 International Conference on Microwave and Millimeter Wave Technology. [S.l.]： IEEEXplore， 2012， 5： 1?4.

[10] CHE H， CHEN Z. Energy?efficient time synchronization algorithm for wireless sensor networks [J]. Ordnance industry automation， 2010， 39： 530?534.

[11] BO G. Research on clock synchronization mechanism in wireless sensor networks[C]// International Forum on Information Technology and Applications. [S.l.]： IEEE， 2009： 57?60.

[12] LENG M， WU Y C. Distributed clock synchronization for wireless sensor networks using belief propagation [J]. IEEE transactions on signal processing， 2011， 59（11）： 5404?5414.

[13] CHOI B J， LIANG H， SHEN X， et al. DCS： distributed asynchronous clock synchronization in delay tolerant networks [J]. IEEE transactions on parallel & distributed systems， 2012， 23（3）： 491?504.

[14] SINAN Y K， KANTARCI A. Time synchronization based on slow?flooding in wireless sensor networks [J]. IEEE transactions on parallel & distributed systems， 2014， 25（1）： 244?253.