Time Synchronization Algorithm with Cross-layer Cooperation and Group Marking
Jia Ya，Liu Rong-wei
(National Mobile Communications Research Laboratory, Nanjing, 210096)
Abstract: Time synchronization is vital to communication network, and both TDMA and event response need time synchronization support. In this paper, we propose a new time synchronization algorithm, which coordinates PHY layer and MAC layer to improve the synchronization precision, and also estimates the time drift to make the algorithm have certain self-learning ability. Finally the simulation is made to verify the performance.
Keywords: time synchronization、cross-layer cooperation、drift、marking
1 引言
基于TDD方式的雙向通信在時間軸分割信號維，各終端在不同的時隙內提出通信需求，需要通信的節點之間時隙對準，這樣才可以實現無沖突的高效傳輸。例如在GSM和TD-SCDMA網絡中[1][2]，基站多配置高精度GPS或通過PDH、SDH獲取同步時鐘，成本高昂。而多數情況下，節點之間不存在統一時鐘源，僅靠自身晶振來維持一個本地時鐘，晶振相位存在隨機偏移和漂移，需要周期性的的數據交互將時間偏差控制在一定范圍內，并且當系統具有監控功能時，需要記錄事件的發生時間，這都需要時鐘同步的支持。
2 時間同步概述
在當前的無線通信系統中，幾乎所有節點都通過一個特定頻率的晶振來產生本地時間，由于晶振存在誤差，即使晶振相同，在不同環境下也存在著頻率漂移。假設本地節點 的硬件時鐘為 ，則本地軟件時鐘的方法可對 做映射變換來獲得：
(1)
其中 是相位偏移， 是漂移率，可以通過調整 和 來矯正本地時鐘。在實際系統中，所有節點都是在不同時間開機的，它們的初始相位 服從隨機分布；受限于制造工藝，并且由于壓力、溫度等環境因素和振蕩器老化等，晶振存在漂移 ；據此可知，本地時鐘在每時每刻不停的漂移，為了達到時間同步的目的，需要周期性地補償 造成的偏差。目前提出的很多時間同步算法都是通過周期性的數據交互將時間偏差控制在一定范圍內，可分為四類：基于接收者-接收者的參考廣播同步、基于發送者-接收者的雙向同步、基于發送者-接收者的單向同步和參數擬合同步，代表算法分別為RBS[3]、TPSN[4]、DMTS[5]和TS/MS[6]等。它們都試圖通過頻繁的時間比對來達到全網同步，實現復雜，據此，本文提出一種簡單的分組標記時間同步算法，將通信網劃分為不同的區域，區域內同步和區域間標記來支持TDMA接入，通過時標轉換實現監控。
網絡拓撲結構如圖 1所示，通過合理放置中心節點將整個網絡人為劃分為不同的同步組，組內拓撲可以為線性或網狀。
圖 1：時間同步網絡拓撲結構
3 時間同步協議
系統被劃分為多個同步時間域，域內劃分等級，每個節點周期接收來自高等級節點的時間同步信息包，完成自身時間的初始同步和同步更新。各域相對獨立，域內時間等級結構隨系統的架設而確定，并不需要專門的拓撲發現階段，節約了系統開銷�；具^程如下：
(1) 中心節點加入網絡時，設置自己的時間等級為0，并將同步狀態更改為已同步，然后競爭時隙向外發送時間同步信息包，其中包括自己的時間戳、時間同步域ID和時間等級。
(2) 新加入節點的同步狀態和時間等級設置為未同步和未初始化，節點持續偵聽網絡，接收時間同步信息包。
(3) 當節點接收到時間同步信息包時，對包進行解析，比較發送方和自身的時間等級（未初始化等級最低），如果優先級高于自身，則發起多次握手過程（將在下面具體介紹），校正自身時間，設置同步狀態為已同步，標記自身所屬時間同步域，并將數據包等級加一作為自身的時間等級。
(4) 節點完成同步后，按自身時間和等級組裝時間同步信息包并競爭時隙向外發送。
(5) 當收到等級不高于自身的時間同步數據包時，節點并不與該數據包同步，比較數據包所屬時間同步域的ID和自身所在域的ID，如果不同則標記自身為該時間同步域的邊緣節點，存儲時間差，反向通知對方然后拋棄數據包。
系統中，節點之間物理距離可能較大，因此必須對路徑傳播時延加以估計，如前面所提的多次握手過程。
假設節點 已同步好，現在通過多次握手讓節點 同步于自身：節點 發送時間同步信息數據包通知節點 發起多次握手過程，數據包內包含了節點 的MAC層時間戳 ，節點 標記自身物理層時間戳 （DMA中斷完成后標記），得到物理層數據處理時延 并存儲于緩存中。節點 收到時間同步信息包時，拋棄該數據包，并發起雙向同步過程。節點 組裝時間數據信息包（包含MAC標記時間戳 ）并發送給節點 ，在發送的同時存儲DMA完成中斷時刻 ，節點 在本地時間 （DMA中斷標記）收到時間同步信息包，在 時刻向節點 發送確認時間信息包，包中包括MAC層標記時間 和節點 物理層處理時延 ，節點 在DMA中斷時刻 收到該確認信息包，最終可得到關系式如下：
(2)
假設節點 和 收到對方的時間信息數據包時都立即發送確認，則在多次握手過程中時鐘的漂移影響和信道變化可以忽略不計，則節點 到節點 的傳播時延 與節點 到節點 的傳播時延 近似相等，用同一值 表示；兩者時間偏差 。對于節點 而言，它的硬件設備和處理速度是確定的，則可以認為物理層處理時延 ，由此可以得到傳播時延 和時鐘偏差 的估計值：
(3)
節點 根據估計得到的時鐘偏差 調整自身時間，完成三次握手，節點 和 的時間同步，這樣通過三次握手完成了兩節點初始同步，其它節點也按此過程通過三次握手完成初始同步。
通過三次握手，完成了物理層處理時延估計，考慮到三次握手的同步效率較低，且處理時延基本不變，在同步追蹤階段采用雙程同步來糾正時間偏移。假設同步周期為 秒，節點在同步完成后進行計時，經過 秒后向上一級節點發起新的時間同步過程�；具^程與三次握手相同，但省略了物理層處理時延的估計，因此不再詳述。
假設TDMA幀長 ms，兩域邊緣節點標記時間偏差 ms（域 時間滯后），則當 時， ，當域 傳輸數據給域 時，則向后推遲 ms，反之向后推遲 ms，因為幀是最大的資源調度單位，所以系統只需競爭下一個完整幀的可用時隙。因此，雖然從域 的節點 到域 的節點 需要經過 跳，但我們只需在邊緣節點進行確定延時，從而避免了復雜的全網同步。數據包每經過一個時間同步域，就根據邊緣節點存儲的標記時間差進行時標轉換，最終都轉換到標準時間。
4 頻率漂移估計
假設節點x按上節的同步方案重復地運行，它在 時刻估計的時鐘偏差分別為 ，節點x在每一次同步完成以后立即減去 來調整它的時鐘�？梢缘玫剑�
(4)
式(4)中 是兩個時鐘在參考時間 時的偏差， 和 是獨立同分布的高斯隨機變量，均值為0，方差分別為 和 。則偏移值 的對數似然函數為：
(5)
令導數 ，求解式(5)得到：
(6)
5 性能仿真
為了評估本文時間同步協議的性能，本節對其進行了仿真驗證，仿真中我們屏蔽了物理層的細節，只需保證硬件的一致性和時間同步信息包大小相同即可。仿真信道采用SUI-3，據此可以計算得出，單跳傳播時延估計誤差 滿足均值為0，方差 的高斯分布。根據正態分布，99%的傳播時延估計誤差出現在2.3倍的標準差附近，而且多跳環境下，時延估計會出現正負相抵，因此誤差會出現在一個固定的范圍內。SUI-3信道下一千萬次仿真結果如圖 2所示，其中的每點為每次仿真的絕對值最大的誤差量，可以看到以為正負效應，誤差不隨跳數線性增大。
圖 2：20跳傳播時延估計誤差
下面我們進一步考察本文提出的時鐘漂移估計方案的性能。取同步周期為10s，盡量減弱加性噪聲 對 的影響；存儲50各個樣值進行線性擬合，結果如圖 3所示，可以看到算法具有較好的漂移估計性能。通過一段時間的時間偏差積累后，系統可以通過漂移估計進行自學習，逐步增大時間同步周期，降低時間同步數據包對系統帶寬造成的浪費。
圖 3：不同偏差樣本下的漂移估計精度
6 結論
本文提出的時間同步算法，通過跨層協作消除了物理層處理時延的影響，通過MAC層打標來避免資源調度的不確定性，采用雙程同步來估計傳播時延，仿真表明算法具有較好的同步精度，并且進一步提出了采用時間偏差估計晶振漂移，仿真表明算法對晶振不穩定具有較好的抵抗能力。
參考文獻
[1] 韓斌杰、杜新顏和張建斌，“GSM原理及其網絡優化（第2版）”，北京：機械工業出版社，2009.1.
[2] 李立華、陶小峰和張平等，“TD-SCDMA無線網絡技術”，北京：人民郵電出版社，2007.8.
[3] Jeremy Elson, Kay Romer, “Wireless Sensor Networks: A New Regime for Time Synchronization”. In: Proc 1st Workshop on Hot Topics in Networks，2002.
[4] S. Ganeriwal, R. Kumar, MB. Srivastava, “Timing-sync Protocol for Sensor Networks,” Proceeding of the 1st International Conference on Embedded Networked, pp138-149, 2003.
[5] S. Ping, “Delay Measurement Time Synchronization for Berkeley Lab,” June 2003.
[6] M. L. Sichitiu, C. Veerarittiphan, “Simple, Accurate Time Synchronization for Wireless Sensor Networks,” IEEE Wireless Communication and Networking, VOL.2, pp16-20, 2003.
作者簡介：
賈雅 女，1986年4月生于河南省許昌市，東南大學信息科學與工程學院碩士研究生，2007年畢業于華中科技大學電信系，獲工學學士學位，目前主要研究方向為無線傳感器網絡。<
