基于TDMA的工業無線網時間同步算法改進與實現

林雄民，楊劍鋒，郭成城，何澤瑞

(武漢大學 電子信息學院，湖北 武漢 430072)

基于TDMA的工業無線網時間同步算法改進與實現

林雄民，楊劍鋒，郭成城，何澤瑞

(武漢大學 電子信息學院，湖北 武漢 430072)

摘要:基于TDMA機制的MAC層接入協議在工業控制網絡的實時性保證方面具有極大的優勢。然而要保證該機制微秒級的時隙調度，網絡中所有的節點必須保持時間同步的高精度。針對現有的一些同步算法并不能完全滿足這種高精度時間同步要求的問題，在傳統的時間同步算法基礎上，添加時鐘漂移預測與補償機制，改進得到一種具有同步精度高、能量消耗低等優點的同步算法——ITR(Improved Wireless Sensor Networks Time Synchronization Algorithm Based On TPSN and RBS)，并在RouterBOARD493G路由節點上進行實驗測試。實驗結果表明ITR同步算法的平均同步誤差比傳統同步算法降低了約52%。

關鍵詞:TDMA；時間同步算法；時鐘漂移；ITR；ath9k

IEEE802.11協議標準是由IEEE(國際電氣和電子工程協會)制定于1997年的無線局域網絡標準，因其高速靈活的特點而成為工業無線控制網的首選技術[1]。然而該協議標準在數據鏈路層采用載波偵聽多路訪問/沖突退避(CarrierSenseMultipleAccesswithCollisionAvoidance，CSMA/CA)通信機制。雖然CSMA機制具有高靈活性和高能量效率等特點，但其采用信道檢測沖突退避的機制難以保證通信時延。TDMA機制的無競爭信道接入方式可以有效地提高信道利用率，避免碰撞沖突，保障嚴格的時延要求[2]。在TDMA機制能夠進一步地應用于現代工業控制網絡的過程中，時間同步算法起到了重要作用。

時間同步算法一般有3類：參考廣播時間同步算法(如RBS算法等)、雙向時間同步算法(如TPSN算法等)和單向時間同步算法(如FTSP算法、DMTS算法等)[3]。這3種同步算法適用的場景不同，各方面也有所差異。

在RBS(ReferenceBroadcastSynchronization)算法的過程中，同步并不是在發送節點與接收節點之間進行，而是在被動接收的節點之間進行，發送同步消息報文的節點并不是全網的標準同步源，接收節點收到消息包后立即記錄本地時鐘值，然后根據該時間值來判斷計算待同步節點間的時間偏差，兩個進行同步的節點中的一個根據時間偏差值來調整本地時鐘來實現同步[4]。

然而RBS算法具有同步精度不高、在大規模多跳網絡中擴展性不好等缺點，而且由于在實際應用中發送節點也需要進行同步，必須尋找網絡中另一節點作為發送節點，造成了同步的復雜度和能耗提高。

TPSN(Timing-syncProtocolforSensorNetworks)算法的核心思想是，為網絡中的每個節點分配具有唯一性的ID號，節點間的時間同步通過雙向交換帶時間值的消息來進行[5]。在網絡中，以一個根節點的時鐘作為全網的基準時鐘，所有子節點的時間都和根節點的時間保持同步。TPSN算法的同步過程可以分為層次發現階段與時間同步階段。TPSN算法采用在同步消息即將要發往無線信道的時候才在MAC層添加時間戳的方式，來消除由訪問時間帶來的時間同步延遲，實現更高的同步精度。此外，TPSN算法還消除或降低了傳播時間延遲和接收時間延遲，進一步提高了同步精度。

但是TPSN算法最大缺陷就是，如果根節點失效，網絡的時間同步將無法進行。此外，當有新的節點加入網絡時，需要對整個網絡重新進行分層，在能耗極大增加的同時，算法穩定性也降低了[6]。

因此，本文在RBS算法和TPSN算法的基礎上，添加了時鐘漂移預測和在非同步周期進行補償的機制，并在能量消耗、同步精度及穩定性方面做出一些優化，改進得到了適用于多跳網絡的時間同步算法——ITR(ImprovedWirelessSensorNetworksTimeSynchronizationAlgorithmBasedOnTPSNandRBS)。通過在硬件平臺RB494G上進行實驗測試，驗證了ITR算法的高同步精度和高能耗效率。

1改進的時間同步算法ITR

ITR算法通過加入時鐘漂移預測與補償機制，適當增大了同步周期，在提高算法同步精度的同時，也降低了節點能耗。該算法的實現過程分兩個階段：網絡分層階段和時間同步階段。

1.1網絡分層階段

該階段的主要目的是使網絡形成一個多層次的拓撲結構，為每個節點分配一個層次號。首先，選取某一個節點作為根節點，并為該節點分配一個層次號0。然后該節點廣播分層消息報文，報文中包含該節點的ID和層次號。當根節點廣播范圍之內的其他子節點收到消息報文時，提取出其中的層次號，并檢查本節點是否已經擁有層次號。如果沒有，就將提取得到的層次號加上1作為本節點的層次號；如果有，并且本節點的層次號比提取得到的層次號小1，則將發送消息的節點的ID添加到子節點表中；如果有，并且層次號比提取得到的層次號大或者相等，那么就不做處理。重復以上過程，最后整個網絡形成了一個樹型的多層次拓撲結構，且每個非葉子節點都有自己廣播范圍內的下層子節點的ID號，如圖1所示。

圖1　層次生成樹

當新節點加入網絡時，ITR算法不需要對網絡重新進行分層。新節點向樹型拓撲網廣播包含本節點ID的層次號請求消息，鄰居節點接收到該請求包后，將回復一個響應消息，該消息中含有本節點的ID和層次號。新節點收到響應消息以后，提取其中的層次號，并將層次號最小的節點作為父節點，從而完成新節點加入到原本穩定的拓撲網絡中。

1.2時間同步階段

本階段采用發送端—接收端雙向交換時間值的方式來計算時間偏差，然后根節點通過單向參考廣播的方式向下層的子節點廣播時間偏差值，子節點根據偏差值進行相應修改。同步逐層進行，直至全網節點都完成與根節點的同步。首先，根節點選擇與一個最近的子節點來進行雙向同步(例如圖1中的根節點A選擇與子節點C進行同步)，以減小節點間的物理距離引起的傳輸延遲，提升同步精度。根節點向網絡廣播同步分組報文，該報文的信息包含有根節點的ID、層次號、指定應答的子節點ID和根節點的發送時間值T1。在根節點廣播范圍里所有的一跳子節點收到了該消息后，記錄接收到該消息時的本地時間值T2'。但是只有消息中指定ID的子節點進行應答，應答消息中包含該子節點ID、層次號、時間值T1、時間值T2(該應答子節點收到廣播同步消息報文時的本地時鐘值)以及發送應答消息時的本地時間值T3。根節點收到應答消息后，記錄下本地時間值T4。于是根節點就得到4個時間值：T1，T2，T3和T4。

根節點計算節點時間偏差值Offset與傳播延遲Delay的過程如圖2所示，其中用D表示傳播時延，用F表示時間偏差。

圖2　雙向時鐘同步算法原理

由關系式T1+D+F=T2與T3+D-F=T4可得到

(1)

(2)

接著，根節點再向網絡廣播一個同步消息包，該消息中含有該節點的ID、時間值T2和式(2)所計算得到的時間偏差F。一跳范圍內的子節點根據該消息包中的時間偏差值F來調整本地時鐘。每個子節點將消息中提取得到的T2值與之前記錄下的T2′值進行比較，得到一個參考性的時間差值F′=T2′-T2，F′表示本節點與同層次中被指定應答的節點的時鐘偏差，最后一跳范圍內所有的子節點修改本地時鐘值為T-F-F′，T為修改前的本地時鐘值。使用同樣的方法，最后網絡中的所有子節點都與根節點完成了同步。

1.3時鐘漂移估計與補償

一般的時間同步算法(如TPSN、RBS算法)僅能保證在同步時刻的精度，卻沒有考慮非同步周期內時鐘漂移的影響[7]。為保證節點同步間隙內的時間同步的準確性，本文的ITR算法加入了時鐘漂移的估計與補償技術。同步節點根據之前接收到的時鐘偏差值F來動態地估算下一次同步操作時刻的時鐘偏移量，并且在非同步周期內根據該估算值進行補償，從而有效地控制時間誤差在兩次同步之間的自由增長，進一步提高精度。此外，這一技術使節點的時間同步不需要完全按照同步周期進行，在不影響正常通信的前提下，可適當增大同步周期，以減少節點的同步信息發送量，降低能耗，延長節點的壽命。

本文采用加權平均的方式來估算時鐘偏移量，即距離當前時刻越遠的時間偏差的權重越小，而距離當前時刻越近的時間偏差權重越大。同步節點根據估算得到的下次同步操作時的時鐘偏差量，再根據本地的時間值和同步周期來做補償[8]。

(3)

式中：x表示權值，其大小關系滿足xN>xN-1>…>x3>x2>x1且xN+xN-1+…+x3+x2+x1=1。

通過上式估算出的時鐘漂移值，在非同步周期完成時鐘補償。補償的方法是

(4)

2ITR時間同步算法的實現

2.1ITR時間同步算法的程序流程

2.1.1根節點

根節點開機啟動后進行系統初始化，然后完成網絡分層和時間同步。具體流程如圖3所示。

圖3　根節點同步流程

2.1.2子節點

子節點先判斷是否加入了網絡中，即檢查是否擁有一個層次號。如果沒有，就向網絡發送一個層次號請求包，進行加入網絡的過程。接著進行同步過程，具體流程如圖4所示。

圖4　子節點同步流程

2.2修改ath9k網卡驅動實現ITR時間同步算法

ITR時間同步算法的實現采用的是硬件時間戳法。Atheros無線網卡芯片自帶TSF定時器，它是一個64bit的定時器，工作頻率1MHz，每計一次數的時間是1μs。為了達到時間同步的要求，發送端應能夠在其物理層信標幀上的24～31byte打上時間戳，即TSF定時器的計數值。而接收端則提取出信標幀內包含的TSF值的低32位并記錄下來。在實現雙向時間同步算法時，通過帶有TSF值的beacon幀來完成時間戳值的交換，然后計算時間偏差值，所以需要對beacon幀的結構做出相應的修改。

對于根節點，需要在發送時間同步信息時附需帶本節點的時間值，即在廣播beacon幀時，需要在幀結構的可添加字段上添加TSF計數值。這可以通過修改OpenWrt路由操作系統ath9k驅動中beacon.c文件下的ath9k_beacon_generate函數及ath9k_beacon_tasklet函數來實現。先增加一個structath_hw*ah函數參數，再在函數中添加提取得到的TSF值到timestamp時戳中：

mgmt_hdr->u.beacon.timestamp=cpu_to_le64(ath9k_hw_gettsf64(ah))

這其中的ath9k_hw_gettsf64函數用于獲取本地的TSF定時器計數值[9]。

對于參與同步的子節點，在收到根節點廣播的beacon同步信息幀時，首先通過if(ID_num== 0x01)檢查該幀是否來自根節點。這里通過ID號來過濾識別，只對目標根節點的beacon幀進行處理。之后提取出beacon幀中的數據以及時間偏差值：

u64q_tsf0 = 0;

structieee80211_mgmt*mgmt= (void*)skb->data;

q_tsf0=le64_to_cpu(mgmt->u.beacon.timestamp);

最后重置本地的TSF定時器計數值：

ath9k_hw_settsf64(ah，q_tsf0);

其中ath9k_hw_settsf64函數的功能是通過對硬件寄存器寫入來完成重置TSF計數值。

上文中提出的時鐘漂移估計與補償機制，也是在底層驅動ath9k中實現的。下面的Clock_Drift_Prediction和Clock_Modify偽代碼分別實現時鐘漂移估計和時鐘漂移補償。

u64Clock_Drift_Prediction(u64F[]，intn)

處理之前得到的n個時鐘偏差值

{

intF_sum= 0；

for(inti=0；i

{

F_sum=F_sum+F[i] *pow(1/2，n+1-i)；

}

u64F_Pre=F_sum/n；

returnF_Pre；

}

Clock_Drift_Prediction中的時鐘漂移預測權值的基準為1/2，最近的權值(即最大權值)為1/2，下一個為1/2的平方，再下一個為1/2的三次方，依次按1/2的n次方對權值進行指數遞減設置。

voidClock_Modify(structath_hw*ah，u64F_Pre，u64Tb，u64Tb0，u64T)

{

u64F_Mod；

F_Mod=F_Pre*(Tb-Tb0)/T；

ath9k_hw_settsf64(ah，F_Mod)；

}

Modify_Time函數參數中的preF參數是時鐘漂移預測值，Tb為當前節點的本地時鐘值，Tb0為上一次同步操作時刻的本地時鐘值，T則為時間同步的周期。

3實驗過程及結果分析

實驗場景如圖5所示，3個與便攜式計算機相連并運行OpenWrt系統的RB493G路由器作為節點，節點A為根節點，節點B和節點C為同步子節點，其中節點C被指定為應答的子節點。

圖5　實驗場景圖

實驗過程中，根節點A每隔200ms向網絡廣播同步beacon幀，beacon幀中附帶本節點的發送時間值T1，子節點B和子節點C收到該beacon幀后，分別讀取本地的TSF計數值并記錄下來，若此時子節點B和子節點C的TSF值分別為T2′和T2，之后子節點C回復根節點A一個消息包，且該消息中帶有子節點C發送回復消息時的時間值T3，當根節點A收到來自子節點C的應答消息包時記錄下本地時間值T4，這樣根節點A與子節點C間的同步操作就完成了。此時在根節點A處會有4組時間值，即T1，T2，T3和T4，然后根據上文的計算式得到根節點A與子節點C之間的時間偏差

(5)

之后根節點A再向網絡廣播一個包含時間值T2與時間偏差值F的同步廣播消息，子節點B接收到該消息后，先提取出T2值，計算出子節點B與子節點C的時鐘偏差值F′=T2′-T2，再根據子節點C與根節點A的時間偏移值F做出相應的調整，修改本地時間為：T=t-F-F′，其中t表示子節點B調整之前的本地時間值，T表示子節點B調整之后的時間值。到此，一跳范圍內的所有節點的時間同步操作就完成了。

進行50次時間同步測試，并記錄得到的時間偏差值，處理后得到的同步算法精度圖如圖6所示。由圖可以看出，根節點A與子節點C每次同步后的時間差的范圍在6μs到10μs，計算得到50次同步的平均精度約為8μs。

圖6　ITR同步算法的精度

由于ITR算法采用交換雙向同步消息報文的方法來計算時間偏差F，降低了傳播延遲對同步精度帶來的影響。此外，在對時間戳值進行的標記和提取的時刻上也作出相應改進，發送消息時間值的添加不是在應用層進行，而是在消息即將發往無線信道中的時候才在MAC層打上時間戳，以消除發送時間延遲的影響；同樣，當消息到達MAC層時立刻提取時間值，以消除接收處理時間延遲的影響。另外，本算法也采用了廣播參考同步消息報文的方式來同步應答節點之外的其他節點，有效地降低了發送延遲和訪問延遲帶來的誤差影響。同時，還添加了時鐘漂移與補償的機制來進一步提高精度。因此，ITR算法的同步精度比傳統的TPSN算法大為提高。

對于能耗問題，ITR同步算法結合了雙向同步信息交換的機制與單向廣播參考同步消息的機制，在提高時間同步精度的同時，也大大減少了節點的數據發送次數，而節點數據接收時產生的能耗遠小于數據發送時產生的能耗[10]。節點的能耗表示如下

E=ECommunicate+EProcess

(6)

式中：ECommunicate是發送數據和接收數據的能耗，EProcess是處理數據的能耗。

RBS算法中兩個待同步的節點之間需要傳遞3次信息，如果多個節點需要進行同步，那么進行同步信息傳遞的次數將成倍增長。TPSN算法同步中兩個節點需要傳遞2次信息。因此，TPSN算法的ECommunicate能耗比RBS算法的能耗小[11]。

假設在網絡中，待同步節點的個數為N，那么ITR算法和TPSN算法發送數據的次數和接收數據的次數如表3所示。由此可見ITR算法的ECommunicate能耗更小。

表3ITR算法和TPSN算法同步消息交換次數

算法類別發送數據次數接收數據次數TPSN算法2N2NITR算法22N+1

對于EProcess，傳統雙向同步算法中，各個同步子節點都要進行時鐘偏差值的計算，而ITR算法的時鐘偏差值的計算是在根節點完成，然后廣播發送給子節點。在如圖5所示的實驗場景中，對于TPSN算法，子節點B和C都要完成一次時鐘偏差值的計算處理；但是對于ITR算法，則只需要在根節點A完成一次時鐘偏差值的計算處理。隨著一跳范圍內同步節點數目的增加，TPSN算法的計算量會不斷增大，而ITR算法的計算量則保持不變。因此ITR同步算法在能量效率方面更高。

3種同步算法的能耗和精度對比結果如表4所示。

表43種時間同步算法對比

算法實驗平臺同步方式復雜度同步誤差/μs能耗RBSMICA接收—接收較高29.13高TPSNMICA發送—接收一般16.90中ITR自建發送—接收一般8.00低

4結束語

本文在RBS算法和TPSN算法的基礎上，改進得到ITR時間同步算法。ITR同步算法相比于傳統時間同步算法在同步精度上有大幅提高，平均同步誤差控制在8μs左右，并且能耗大為降低。目前，基于TDMA機制的工業無線控制網絡的時隙調度長度一般都在10μs[12]以上，并且相鄰兩個調度的時隙之間都會有一定的保護間隔來避免同步誤差帶來的影響，而這種保護間隔的長度一般都在幾十微秒以上。因此，ITR算法的8μs左右的同步誤差完全能夠達到基于TDMA機制的時隙調度的誤差要求，滿足工業無線控制網絡高實時性、高可靠性的要求。

參考文獻：

[1]楊雨沱，梁煒，張曉玲，等. 面向工廠自動化無線網絡的時間同步方法[J]. 計算機研究與發展，2014，51(3)：511-518.

[2]林俊如，曾鵬，于海斌. 面向高速工業無線網絡的TDMAMAC協議設計與實現[J]. 計算機科學，2011，38(10)：299-304.

[3]孫新偉，申興發，張能貴. 無線傳感器網絡節點周期性休眠時間同步研究[J].機電工程，2010，27(5)：75-77.

[4]周婭，郎朗，陳孟元.無線傳感器網絡的多跳時間同步優化算法[J].計算機工程與應用，2015，51(4)：96-99.

[5]陶志勇，胡明. 基于等級層次結構的TPSN算法改進[J]. 傳感技術學報，2012，25(5)：691-695.

[6]張春梅，白鳳山，王梅，等.一種改進的TPSN時間同步算法的實現[J].內蒙古大學學報(自然科學版)，2013，44(3):316-319.

[7]MARCELB.Handlingtimeandreactivityforsynchronizationandclockdriftcalculationinwirelesssensor/actuatornetworks[C]//Proc.the3rdInternationalConferenceonSensorNetworks. [S.l.]：IEEEPress，2014：63-72.

[8]楊朔. 無線傳感器網絡時間同步算法研究[D].長沙：中南大學，2014.

[9]GASTMS. 802.11OReilly802.11Wirelessnetworksthedefinitiveguide[M]. 2nded.Nanjing：SoutheastUniversityPress，2007.

[10]張韜. 無線傳感器網絡節能數據傳輸問題研究[D].南京：南京大學，2012.

[11]GANERIWALS，KUMARR，SRIVASTAVAMB.Timing-syncprotocolforsensornetworks[C]//Proc.the1stInternationalConferenceonEmbeddedNetworkedSensorSystems.NewYork：ACMPress，2003：138-149.

[12]曲金鑫.AdHoc網絡TDMA動態時隙分配算法研究[D].哈爾濱：哈爾濱工業大學，2013.

ImprovementandimplementationofindustrywirelessnetworksynchronizationalgorithmbasedonTDMAmechanism

LINXiongmin,YANGJianfeng,GUOChengcheng,HEZerui

(Electronic Information School， Wuhan University, Wuhan 430072, China)

Abstract:The MAC layer access protocol based on TDMA mechanism has great advantage to guarantee timeliness in industry control network. But in order to guarantee slot time scheduling in microsecond level, all the nodes in the network must keep high precision in time synchronization. Aiming at the problem that some current synchronization algorithms could not meet the requirement of high precision, on the base of traditional synchronization algorithms, adding the mechanism of clock drift forecasting and compensation, get an improved synchronization algorithm with high precision and low power consumption——ITR (Improved Wireless Sensor Networks Time Synchronization Algorithm Based on TPSN and RBS), and then do test on route node RouterBOARD493G. The result demonstrates that synchronization algorithm ITR’s average synchronization error decreases about 52% than traditional synchronization algorithm.

Key words:TDMA; time synchronization algorithm; clock drift; ITR; ath9k

中圖分類號:TP393

文獻標志碼:A

DOI：10.16280/j.videoe.2016.03.012

基金項目：國家“863”計劃項目(2012AA010904)；四川省科技計劃項目(2013GZ0016)；成都大學項目(20804)

作者簡介：

林雄民(1990— )，碩士，主要研究方向為無線網絡與嵌入式系統；

楊劍鋒(1976— )，副教授，主要研究方向為無線網絡與嵌入式系統。

責任編輯：許盈

收稿日期：2015-11-08

文獻引用格式：林雄民，楊劍鋒，郭成城，等. 基于TDMA的工業無線網時間同步算法改進與實現[J].電視技術，2016，40(3)：54-59.

LINXM，YANGJF，GUOCC，etal.ImprovementandimplementationofindustrywirelessnetworksynchronizationalgorithmbasedonTDMAmechanism[J].Videoengineering，2016，40(3)：54-59.