多時鐘同步方案的比較與測試

，，

(清華大學 計算機科學與技術系，北京 100084)

0 引言

傳統(tǒng)的網(wǎng)絡通信，網(wǎng)絡通常采用“事件觸發(fā)”機制。在事件觸發(fā)網(wǎng)絡中，節(jié)點可能在任意時刻發(fā)送或接收數(shù)據(jù)，一旦網(wǎng)絡負載較大而發(fā)生沖突，會產(chǎn)生丟包等問題，效率低且可靠性差。另外，多個節(jié)點在同一個時間段內(nèi)進行數(shù)據(jù)的收發(fā)，通信延遲高，無法保證消息傳遞的確定性。

采用時間觸發(fā)機制的網(wǎng)絡通信是指在整個網(wǎng)絡當中建立一個統(tǒng)一的時間基準，節(jié)點根據(jù)預先設定的通信任務調(diào)度表，按照時間先后次序進行數(shù)據(jù)收發(fā)。在時間觸發(fā)機制網(wǎng)絡中，網(wǎng)絡的利用率可以達到80%～90%，比事件觸發(fā)網(wǎng)絡的利用率高，確定性好。網(wǎng)絡通信按照調(diào)度表進行，收發(fā)數(shù)據(jù)的時間可以預估，而且建立全局系統(tǒng)狀態(tài)有利于系統(tǒng)的維護操作。時間觸發(fā)機制在網(wǎng)絡發(fā)展的新形勢下，在航空航天等對于網(wǎng)絡傳輸確定性有高要求的領域中將會有更加廣泛的應用。

時間觸發(fā)網(wǎng)絡通信的關鍵技術主要涉及全局的時間同步與調(diào)度表的設計，其中全局的時間同步尤為關鍵，不同的同步方法會有不同的耗時及通信開銷和同步精度，對時間觸發(fā)網(wǎng)絡的性能效果有很大的影響。目前存在多種時間同步方法，能否適用于時間觸發(fā)通信的實際系統(tǒng)尚待研究，在多種方法中選擇更為合適的方案是時間觸發(fā)網(wǎng)絡研究的重要課題。

1 相關工作

近年來， 時間觸發(fā)網(wǎng)絡TTP[1]與TTE[2]憑借著良好的通信實時性與應用廣泛的無線傳感網(wǎng)絡[3]一同成為了通信領域的熱門方向。其中關鍵技術——時間同步也就成為了研究的熱點。時間同步方案分類有多種方式[4]，有內(nèi)部同步與外部同步，概率同步[5]與確定同步，立即修正同步與維護時間同步，而下文介紹的最常用的分類方法是主從同步與互同步，不同方法有不同的應用背景。

在同步問題被提出時，時鐘模型一般被抽象為C(t)=ax+b(x為單位時間，a為時鐘漂移速率，b為時鐘偏置)，時間同步就是通過校正使多個不同的時鐘模型最終具有相同的時鐘速率和偏置，實現(xiàn)時間同步。1985年NTP[6]被提出，是最早且當時應用較廣的時間同步方法之一。隨后，時間同步一方面延續(xù)NTP的同步思路發(fā)展：有NTP拓展的TPSN[7]算法，有現(xiàn)今應用較為廣泛的IEEE1588協(xié)議，以及TPSN的優(yōu)化LTS低深度生成樹算法[8]。除了節(jié)點成對同步算法之外，也有單向通信的同步算法，相比于成對同步，它犧牲了一部分時間精度，但節(jié)約了能耗和開銷，同時也能避免通信交互帶來的不確定性，代表算法有 FTSP[8]與DMTS[9]，主要思想為發(fā)送方在消息發(fā)送時刻獲取本地時間打上時間戳，消息的接收方獲得時間戳，并記錄接收消息的本地時間，并以此為依據(jù)同步。主從同步是主節(jié)點發(fā)送帶有自身信息的分組，其他節(jié)點參照分組信息對自身時鐘進行校正。因此，由于對主控節(jié)點的選取和維護方法不同，除了上述方法外，也有如全節(jié)點同步的新主從同步方法被提出。

另一方面，由于主從同步方法在大規(guī)模網(wǎng)絡與動態(tài)拓撲網(wǎng)絡中的表現(xiàn)不佳，理論上更適用于大型網(wǎng)絡的互同步方法進入了時間同步的研究范圍，RBS[10]是最早提出的應用最廣的互同步方法之一，而后也衍生出PBS[11]等同步方案。此外，互同步方案不同于主從同步，它的核心思想是每個節(jié)點都從多個其他節(jié)點收集時鐘的參考值，考慮節(jié)點距離與校正次數(shù)等不同的影響因素，在一個時刻通過多個節(jié)點時間值的不同加權方法得到一個估算值。在互同步中，每個節(jié)點重復這種獲取估算值的操作，讓所有節(jié)點的時鐘值不斷收斂，最終趨向于統(tǒng)一化。此類收斂函數(shù)式。的互同步方案代表性的方法有2006年提出的同步擴散[12]與非同步擴散方案[14]，其中使用了節(jié)點交換信息的隨機矩陣，開拓了數(shù)學與時間同步的結合研究領域；也有平均時間同步ATS算法[15]和分布式時間同步DTS算法，其核心思想是把同步分為斜率同步和偏差同步兩個階段[14]，而2012年提出的CCS算法結合了兩個同步的階段，并在估計加權上提出了置信參數(shù)的方法，取得了比原有加權方法更好的效果。但以上收斂函數(shù)式互同步方案較為復雜，僅在數(shù)學理論與仿真中檢驗了正確性，在實際系統(tǒng)中的效果有待于進一步研究。

總體看來，隨著網(wǎng)絡通信的發(fā)展，時間觸發(fā)網(wǎng)絡得到了更廣泛的應用，作為時間觸發(fā)網(wǎng)絡的關鍵——時間同步技術產(chǎn)生了諸多方法上的創(chuàng)新，每種方法都有各自特點。隨著時間網(wǎng)絡系統(tǒng)種類的多樣化，探究不同方案適合的網(wǎng)絡情況必將是值得關注的研究領域。

2 方案介紹

結合上述的介紹，主從同步方案中，IEEE1588協(xié)議優(yōu)化方法多，同步精度高，適用條件寬泛，實際應用較多；環(huán)型主從同步(全節(jié)點同步)通信開銷較小，將一段通信時間平均到每個相似節(jié)點的算法思路具有啟發(fā)意義；而互同步中RBS同步方案較為成熟，具有代表性且在實際中檢驗了可行性與正確性。因此，本文選擇了星型主從同步(基于IEEE1588協(xié)議)，環(huán)型主從同步與RBS同步作為主從同步與互同步的代表方案進行理論分析并結合試驗進行測試。

2.1 星型主從同步方案

2.1.1 同步原理

星型主從同步的主要結合了IEEE1588協(xié)議進行工作。其同步原理為成對同步，對于一對節(jié)點，確定一個為主時鐘，另一個為從時鐘。兩個CPU通過兩次互相收發(fā)帶有時間戳的報文計算兩個CPU之間的通信延遲和時鐘偏差來完成時間同步，具體執(zhí)行過程如圖1所示。

圖1 IEEE1588協(xié)議流程

1)主時鐘發(fā)送Sync報文，同時記錄下發(fā)送報文的本地時間t1;

2)主時鐘再發(fā)送Follow_up報文，帶有時間戳t1;

3)從時鐘接收報文，收到Sync報文時記錄本地時間t2，從Follow_up報文中解析時間t1;

4)從時鐘發(fā)送Delay_request報文，同時記錄發(fā)送報文的本地時間t3;

5)主時鐘接收到Delay_request報文，記錄本地時間t4，發(fā)送帶有t4時間戳的Delay_response報文;

6)從時鐘解析t4后通過t1,t2,t3,t4四個時間進行計算與時鐘校正[17]，由圖1可知：

t2-t1=tdelay-toffse

t4-t3=toffset+tdelay

tmaster=tslave+toffset

由此，可以計算出時間偏置。

2.1.2 系統(tǒng)實現(xiàn)

星型主從同步系統(tǒng)框架如圖2所示。

圖2 星型同步系統(tǒng)框架

本文的時間同步的通信中的每個報文長度都是16字節(jié)，具體劃分如圖3所示。

圖3 報文結構

2.1.3 時鐘漂移速率校正

星型系統(tǒng)中，在完成系統(tǒng)一個周期的整體同步之后，可以認為每一個節(jié)點都與主節(jié)點時間一致。而傳統(tǒng)的IEEE1588協(xié)議只能保證在同步的一個時刻，兩個時鐘的值相等，然而時鐘的漂移速率仍有差異，同步間隔中，時鐘之間的偏差會持續(xù)增大，無法達到時間觸發(fā)系統(tǒng)的要求。在已有的研究中，有論文提出了寄存器存儲頻率比系數(shù)輔助速率校正[18]，然而經(jīng)過實踐檢驗，這種方法在STM32F407芯片上效果不佳，究其原因有二：首先，STM32F407芯片不支持double類型，頻率比系數(shù)必須要很高的精度才能取得校正小誤差的效果，因此從系統(tǒng)實現(xiàn)角度來看，無法使用高精度小數(shù)修正時鐘速率。其次，在本實驗系統(tǒng)中使用float類型進行校正，然而float類型有效位數(shù)少，精度太低，每次浮點數(shù)向整數(shù)轉換也存在舍去的精度，修正可在一定程度上提高同步精度，但是最終效果無法令人滿意為了解決STM32F407中的時鐘漂移速率修正的問題，經(jīng)過思考與實踐，本文最終在系統(tǒng)中采用了一種人工計算和設置結合而不使用小數(shù)的修正從時鐘速率的方法如圖4所示。

圖4 時鐘速率修正算法示意圖

1)確定一個時鐘周期，在每個周期同一位置做標記；

2)相鄰兩個周期的時鐘counter作差，分別記錄不同CPU在同一時間段內(nèi)的計數(shù)；

3)計算主從時鐘計數(shù)的偏差值，用主時鐘計數(shù)值/偏差值作為變量a(偏差相對時鐘計數(shù)較小，則a會取成比較大的整數(shù))；

4)在時鐘中斷處再設立一個計數(shù)器change_counter，它在和counter執(zhí)行同樣操作基礎上，每當change_counter計數(shù)達到a時，清零change_counter，如果從時鐘相對于主時鐘慢，給從時鐘counter加1；相對主時鐘快，則給從時鐘counter減1；

圖5為本文時鐘修正速率方法的示意圖，把偏差分散均勻校正。

圖5 時鐘速率修正效果圖

通過加入上述的時鐘漂移速率校正方法，星型主從同步可以取得更高的精度，實驗對比結果詳見后文。本文后續(xù)介紹的方案都需要通信節(jié)點參數(shù)相同，因而都需要使用上述的校正時鐘速率的方法。

2.2 環(huán)型主從同步方案

2.2.1 同步原理

環(huán)型主從同步也被稱為基于全節(jié)點的同步，需要同步的節(jié)點構成環(huán)型拓撲，在一輪同步過程中，主節(jié)點發(fā)送的報文環(huán)繞節(jié)點一周，每個從節(jié)點記錄接收報文的本地時間及在環(huán)型中的順序，同時記錄主節(jié)點發(fā)送報文的起始和結束時間，隨后將這一時間段平均到每一個從節(jié)點上。在環(huán)型當中的節(jié)點處理數(shù)據(jù)的能力與速度基本相同，且每一條通信線路上報文傳播時間基本相同的情況下，可以通過從節(jié)點先前的本地時間和在環(huán)型中的位置估算主時鐘和從時鐘之間的偏差，從而進行校正。

2.2.2 系統(tǒng)實現(xiàn)

環(huán)型主從同步系統(tǒng)實現(xiàn)是建立在一個將所有節(jié)點排成環(huán)型的拓撲上(保證數(shù)據(jù)包至少經(jīng)過每個節(jié)點一次)，選定一個節(jié)點作為主節(jié)點，按照如圖6所示的算法進行：

圖6 環(huán)型主從同步算法示意圖

1)通過本文上述的同步時鐘速率方案統(tǒng)一所有通信節(jié)點的時鐘速率；

2)主節(jié)點發(fā)送一個報文，同時記錄發(fā)送報文時刻的本地時間tstart，報文當中包含報文在接收之前經(jīng)過了多少個節(jié)點(假設環(huán)型上共有n個節(jié)點)；

3)每個從節(jié)點在接收到報文時，記錄自己在環(huán)型當中的相對順序k，以及接收報文時刻的本地時間tk，對報文進行處理后轉發(fā)；

4)當報文傳輸過每一個節(jié)點至少一次之后，記錄報文返回到主節(jié)點的本地時間tend；

5)主節(jié)點再次發(fā)送報文，報文當中包含tstart與tend的時間戳信息，其中時間戳要打在數(shù)據(jù)幀的相同位置，保證各節(jié)點的通信延遲基本相等；

6)對于每一個從節(jié)點k，從主節(jié)點發(fā)送的報文當中提取起始時間和結束時間的信息，計算(tend-tstart)*(k-1)/n，取與其數(shù)值上更為接近的整數(shù)，設為x；

7)對于從節(jié)點k，當前其本地時間為t，則將其時鐘調(diào)整為(t-tk+tstart+x)。

上述的式子可以拆開分析，在報文到達k節(jié)點時，k節(jié)點時間為tk，而(tstart+x)可以認為是起始時間加報文到k節(jié)點的傳輸時間，即主節(jié)點此時的對應時間，相減得到從節(jié)點與主節(jié)點的時鐘偏差，最后通過偏差值對從時鐘進行校正。

2.3 RBS同步方案

RBS同步是一種常見的互同步方案，其同步原理是通過參考節(jié)點發(fā)送廣播報文實現(xiàn)接收節(jié)點之間的同步如圖7[19]。

發(fā)送的報文本身不需要帶有時間戳，具體發(fā)送時間沒有硬性要求，只需要保證連接正常，信道暢通即可。RBS同步通過一次報文的廣播使得多個接收數(shù)據(jù)節(jié)點進行時間同步，在足夠多次的廣播與同步后，節(jié)點的時鐘達到一致。

基于STM32F407芯片實現(xiàn)的RBS方案具體實施如下：

1)同步所有通信節(jié)點的時鐘速率;

2)選定發(fā)送節(jié)點，同時向a，b兩個節(jié)點(也可多個)廣播不帶有時間戳的報文;

3)兩個接收節(jié)點記錄接收報文時刻本地時間，通過報文返回發(fā)送節(jié)點(a，b之間有通信連接也可以直接通信完成校正);

4)發(fā)送節(jié)點處理a，b節(jié)點反饋的報文，計算時鐘偏差值;

5)接收節(jié)點根據(jù)時鐘偏差信息完成校正。

3 理論分析

以下本文會結合上述的原理介紹對3種方法進行理論分析，主要對比3個方案優(yōu)勢，缺陷以及其適用場景。

3.1 優(yōu)勢與缺陷

星型主從同步方案和環(huán)型主從同步方案過程簡單，從節(jié)點校正目標明確，同步效果可控，收斂速度快，由于算法是確定性的，在編寫難度上較小。其中星型主從同步方案基于IEEE1588協(xié)議實現(xiàn)，應用廣泛，適用于分布式系統(tǒng)，同步精度高[17]。而環(huán)型主從同步，在每輪同步過程當中，每個節(jié)點僅需要收發(fā)報文兩次，相比于其他算法，通信開銷低，節(jié)約能耗。

兩種方案有主從同步固有的優(yōu)勢，也有主從同步無法回避的缺陷：兩個方案都極度依賴于主節(jié)點，當主節(jié)點發(fā)生變化或離開網(wǎng)絡時，時間同步會受到很大的影響。此外，兩個方案在大型網(wǎng)絡以及拓撲結構變化較大的網(wǎng)絡上不適用，星型主從同步的主節(jié)點本身通信負擔較重，容易產(chǎn)生擁塞，一旦節(jié)點過多則會對系統(tǒng)性能產(chǎn)生很大影響；而環(huán)型主從同步對連接的形式要求較高，在多節(jié)點網(wǎng)絡和動態(tài)網(wǎng)絡較難實現(xiàn)環(huán)型的通信傳輸，同步周期較長，此外，一旦拓撲上的一個節(jié)點出現(xiàn)故障，可能會引起整個系統(tǒng)無法正常運行。

圖7 RBS同步原理

除了機制上的缺陷，星型主從同步基于IEEE1588協(xié)議，要求節(jié)點成對通信時往返傳輸延遲是相同的錯誤！未找到引用源。，然而實際的網(wǎng)絡未必能完全滿足這個假設前提，往往會產(chǎn)生一定的偏差，對同步的效果造成影響。同理，環(huán)型主從同步建立在“節(jié)點處理數(shù)據(jù)能力相同，所有線路傳輸延遲相同”的假設條件下，這個假設條件在實際系統(tǒng)中很難成立，因此實際精度受到影響。

RBS同步通過廣播消除了發(fā)送方延遲對同步精度的影響，算法的運行不依賴于某一個節(jié)點，滿足連接要求的節(jié)點都可以實現(xiàn)時間同步。其同步算法可以分別在某一個局部運行，通信開銷較為均勻，不易產(chǎn)生因為同步通信導致的擁塞問題，因此，RBS同步可用于大型網(wǎng)絡以及動態(tài)拓撲結構網(wǎng)絡。

缺陷方面，RBS同步相比于上述的方案編寫算法更加復雜，系統(tǒng)中的節(jié)點達到時間同步需要一定的收斂時間，無法像主從同步一樣讓通信的幾個節(jié)點立刻同步。在節(jié)點數(shù)較少的情況下，同步精度與收斂速度會比適用的主從同步方案差。

3.2 適用場景

結合上述的優(yōu)勢與缺陷的分析，可以總結各方案特點，確定方案的適用場景如表1所示。

表1 同步方案特點總結

4 時間同步測試

在進行了上述的理論分析后，使用3個STM32F407芯片搭建CPU，使用不同的拓撲形式，實現(xiàn)上述的3種時間同步方式的性能測試與對比。

4.1 時間同步測試方案

每一個方案的測試過程首先是分別給CPU進行上電，可以保證每個CPU在初始運行時刻時鐘各不相同。在CPU通信時，保證通信方式與參數(shù)均相同。

檢驗時間同步的效果主要使用示波器進行正確性檢測在時鐘中斷處根據(jù)時鐘值觸發(fā)GPIO引腳輸出方波，使用示波器的多個通道對比方波的跳變邊沿，差值在微秒級。

4.2 測試結果與分析

使用相同的STM32F407芯片，分別運行不同的時間同步方法，時鐘穩(wěn)定運行后，每次同步間隔5 s，記錄100次以上的同步結果，求取平均值作為衡量同步方案的指標，時鐘速率校正方法測試結果如表2所示。

表2 速率校正測試結果

3種使用本文提出的校正時鐘速率方法后的方案測試結果如表3所示。

表3 多方案同步測試結果

從上述的實驗結果當中可以看出，3種時間同步方案的精度都可以達到微秒級，可以滿足一般的時間觸發(fā)總線的通信要求。比較分析，在需要參與時間同步節(jié)點數(shù)目較少的情況下，基于IEEE1588協(xié)議的星型主從同步方法，通信負擔較重，但在同步精度上明顯好于其他兩種方法。環(huán)型主從同步與RBS同步在同步精度和網(wǎng)絡負擔上較為相近，在節(jié)點較少的情況下不適用，環(huán)型主從同步更適用于網(wǎng)絡情況節(jié)點數(shù)較少，連接方式能形成環(huán)型，各節(jié)點與線路在處理數(shù)據(jù)和通信傳輸能力相似，在系統(tǒng)采用的節(jié)點和線路有所差別時，會產(chǎn)生一定的偏差。而RBS同步更適合動態(tài)拓撲網(wǎng)絡，對于網(wǎng)絡連接方式要求不高，但在所有節(jié)點的同步速度會較慢，在節(jié)點數(shù)目較少的情況下，精度會比適用的主從同步差。測試結果檢驗了上文理論分析的正確性。

5 結語

本文首先對時間同步的相關工作進行了介紹，從中選取了3種典型的方案——星型主從同步，環(huán)型主從同步與RBS同步進行了算法介紹和系統(tǒng)實現(xiàn)。隨后，本文從3個方案的特點進行了理論分析，明確了3種方案的優(yōu)勢，缺陷以及適用的場景。最后，本文結合基于STM32F407芯片搭建的時間同步系統(tǒng)，通過示波器檢驗驗證了系統(tǒng)的正確性；試驗結果表明，3種同步方案精度可以達到微秒級別；比較了在需要同步節(jié)點較少情況下，3種方案取得同步效果的優(yōu)劣，進一步驗證了之前所做分析——“星型主從同步更適用于節(jié)點數(shù)目少的時間觸發(fā)網(wǎng)絡”。

參考文獻：

[1] Kopetz H, Grunsteidl G. TTP - A time-triggered protocol for fault-tolerant real-time systems[J]. 1993:524-533.

[2] Kopetz, Hermann, Ademaj, et al. The Time-Triggered Ethernet (TTE) Design[J]. 2005:22-33.

[3] Wu Y C, Chaudhari Q, Serpedin E. Clock synchronization of wireless sensor networks[J]. IEEE Signal Processing Magazine, 2010, 28(1):124-138.

[4] Rhee I K, Lee J, Kim J, et al. Clock synchronization in wireless sensor networks: an Overview[J]. Sensors, 2009, 9(1):56.

[5] Cristian F, Fetzer C. Probabilistic internal clock synchronization[J]. IEEE Symp on Reliable Distributed Systems, 2003:22 - 31.

[6] 王曉冬. 以太網(wǎng)時間同步技術的研究[D]. 南京:南京郵電大學, 2009.

[7] Ganeriwal S. Timing-sync protocol for sensor networks[A]. International Conference on Embedded Networked Sensor Systems[C]. ACM, 2003:138-149.

[8] 康冠林, 王福豹, 段渭軍. 無線傳感器網(wǎng)絡時間同步綜述[J]. 計算機測量與控制, 2005, 13(10):1021-1024.

[9] Ping S. Delay measurement time synchronization for wireless sensor networks[J]. IRB, 2003.

[10] Elson J, Girod L, Estrin D. Fine-grained network time synchronization using reference broadcasts[J]. Acm Sigops Operating Systems Review, 2002, 36(SI):147-163.

[11] Noh K L, Serpedin E, Qaraqe K. A new approach for time synchronization in wireless sensor networks: pairwise broadcast synchronization[J]. IEEE Transactions on Wireless Communications, 2008, 7(9):3318-3322.

[12] 鄭 錦,劉萬軍.實時分布式系統(tǒng)的時間同步化策略[J].遼寧工程技術大學學報(自然科學版),2004,23(1):92-94.

[13] Su, Weilian, Akyildiz, et al. Time-diffusion synchronization protocol for wireless sensor networks[J]. IEEE/ACM Transactions on Networking, 2005, 13(2):384-397.

[14] Li Q, Rus D. Global Clock Synchronization in Sensor Networks[J]. IEEE Transactions on Computers, 2006, 55(2):214-226.

[15] Schenato L, Fiorentin F. Average TimeSynch: A consensus-based protocol for clock synchronization in wireless sensor networks [J]. Automatica, 2011, 47(9):1878-1886.

[16] Maggs M K.Consensus clock synchronization for wireless sensor networks[J]. IEEE Sensors Journal,2012,12(6):2269 - 2277.

[17] 寇海洋, 段雄英. 基于STM32F407的時鐘同步系統(tǒng)的實現(xiàn)[J]. 計算機測量與控制, 2015, 23(8):2759-2761.

[18] 孔亞廣, 孫祥祥. 基于ARM的IEEE1588精密時間同步協(xié)議的實現(xiàn)[J]. 計算機應用, 2013, 33(s1):315-317.

[19] 李文鋒, 王汝傳, 孫力娟. 基于RBS的無線傳感器網(wǎng)絡時間同步算法[J]. 通信學報, 2008, 29(6):82-86.

[20] 于鵬飛,喻 強,鄧 輝, 等.IEEE 1588精確時間同步協(xié)議的應用方案 [J]. 電力系統(tǒng)自動化,2009,33(13):99-103.