基于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.