基于接收者的无线传感器网络时间同步算法研究

谷呈星，赵训威，*，张春玲

（1.上海电力大学，上海 201306；2.国网信息通信产业集团有限公司，北京 100032）

0 引言

随着无线通信、微机电系统和信号处理技术的迅速发展，低成本的无线传感器网络(Wireless Sensor Network，WSN）［1］设备在军事、农业、医疗、航空航天、智能家居和环境监测等领域有着广泛应用。时间同步技术作为无线传感器网络的底层支撑技术之一，是数据的可靠传输、节能监测定位、目标追踪、休眠调度等功能实现的基础，故研究WSN的时间同步具有重要意义［2］。

现有的多数同步算法是在MAC层时间戳可用的条件下才能实现高的同步精度。基于发送者-接收者的单向同步、基于发送者-接收者的双向同步和基于接收者-接收者的同步是同步算法的3种同步方式。泛洪时间同步协议(Flooding Time Synchronization Protocol，FTSP）［3］、多跳平均共识时间同步［4］(Multihop Average Consensus time Synchronization，MACTS）等属于发送者-接收者单向同步方式的算法。传感器网络时间同步协议(Timing sync-Protocol for Sensor Networks，TPSN）［5］、Mini-Sync协议和Tiny-Sync协议［6］等属于发送者-接收者双向同步方式的算法。上述发送者-接收者方式的算法用MAC层时间戳消除了发送时延和访问时延，但忽视了不是所有无线芯片都支持MAC层时间戳这个问题。产生MAC层时间戳需要无线射频模块的支持，无线射频模块接收完一个数据包后会向微处理器(Micro Controller Unit，MCU）发送请求信号，MCU在收到请求信号时，会产生中断并在传输中的数据包上打MAC层时间戳。但是现在很多Zigbee，WiFi和蓝牙等无线射频模块在MCU收到请求信号时，需要立即安排下一个数据包，也就无法在传输中的数据包上打时间戳。当MAC层时间戳不可用时，受访问时延的影响，发送方-接收方算法的同步精度会大幅降低。参考广播同步(Reference Broadcast Synchronization，RBS）［7］、参 考 广 播 基 础 同 步［8］(Reference Broadcast Infrastructure Synchronization，RBIS）等属于接收者-接收者的同步方式。此方式的算法利用参考节点广播的方式消除了发送方的时延，在无MAC层时间戳时也可以实现较高的同步精度，但是存在同步开销大的缺点。

本文在RBS算法的基础上，提出了一种基于接收者-接收者方式的时间同步算法(LPSN算法），利用广播关键参数的方法减少了同步开销，降低了能耗。在实验中本文算法没有与对硬件和软件有较高要求的同步算法作比较，比如PulseSync算法［9］，而是与适用性强，可以在任何硬件上实现的经典算法相比较。实验结果证明算法无须MAC层时间戳也能实现较高同步精度。

1 模型及符号表示

在WSN中，节点的晶振频率易受到温度、湿度、电磁辐射等因素的影响，这将导致不同节点间的本地时钟出现偏差。随着时间的推移时钟偏差会逐渐变大，最终影响WSN中节点的正常工作。时间的相对时钟偏移和相对漂移是节点时钟同步的重要参数，相对时钟偏移和相对漂移分别指两个时钟之间的时间差和两个时钟频率之间的差。

假设监测区域内有N个节点，任意一个节点i将本地时钟建模为：

其中，t i是本地时钟读数，a i和b i是节点时钟相对于标准时间t UTC的绝对时钟漂移和偏移。

依据晶振频率的特性，可以认为a i和b i在一段时间内为常数。因此，两个传感器节点的本地时钟是线性相关的。任意两个节点i和j的时间关系可以建模为：

其中，a i j和b i j是节点i的本地时钟t i相对于节点j的本地时钟t j的相对漂移和偏移。

将任意两个节点i，j的本地时间与t UTC代入公式(1）可得到两个等式。利用t UTC相同这一条件，进行等式变形便可得出t i(t）与t i(t）之间的关系，a i j和b i j便可计算出来。

2 LPSN算法

2.1 算法实现

采用簇型网络拓扑结构，按照地理位置选出合适节点作为参考节点。算法定义同步周期T=N T R，其中，N是参考节点广播数据包的次数，T R是参考节点广播的两个连续数据包之间的时间间隔，同步周期T是广播N次数据包所需要的时间。典型的单跳同步示例如图1所示，设节点O为时间基准点，节点R为参考节点，节点A为普通节点，A是希望与O同步的节点。

图1 单跳同步示例

同步算法的过程可分为3个阶段，过程如下：

2.1.1 参考节点广播阶段

在同步周期内，R定时广播信标数据包，每个信标包中含有节点的标识ID、包的序号、周期号和一个时间戳，该时间戳记录了应用层生成包时R的本地时间。O和A在收到信标包时将各自的本地时间作为接收时间，并将接收时间和信标包中的时间成对地存储在大小为N的循环缓冲区中。在无丢包的情况下，会形成N对时间标(信标包中的时间，接收时间）。当循环缓冲区中有N对时间标时就建立线性回归方程，采用最小二乘法求解，见公式(3）和(4），便可计算出相对时钟漂移和偏移。

2.1.2 参数传递阶段

在同步周期结束时(周期号的增加代表了上一个周期的结束），O将构建并广播一次同步信息包，信息包中含有时间基准点ID，参考节点参考节点收到信息包后会转发此信息包。

2.1.3 普通节点与时间基准点同步阶段

2.2 误差分析

发送方节点的应用层时间戳到达接收方节点的过程中，会遇到多个时延，这些时延会降低同步精度。无线链路的时延组成如图2所示。在WSN中无线消息传播链路上的时延可以分为：发送时延、访问时延、传输时延、传播时延、接收时延和接收处理时延［10］。

图2 无线链路的时延组成

其中访问时延是影响同步精度的主要原因，采用MAC层时间戳的同步算法可以消除发送、访问和接收处理时延。在MAC层时间戳不可用的条件下，需要MAC层时间戳的算法的同步精度会大幅降低。本文算法借鉴了RBS算法的思想，消除了发送方的时延，而传播时延与节点间的距离有关，300 m内的传播时间小于1 us。与访问时延相比，接收时延和接收处理时延对同步精度的影响较小。因此，在理论上本文算法可以实现较好的同步精度。

3 性能比较

3.1 同步开销比较

在WSN的应用中，传感器节点的功耗是由通信主导而不是由计算主导［11］，节点的能量主要在发射、接收数据包的过程中消耗。Bae［12］中的能耗分析模型指出在确定了区域范围和区域内节点的数量后，可以用发送和接收报文的次数来衡量能耗的大小。

在静态WSN中，因为确定层次结构或者从属关系的数据包只需要用一次，所以没有考虑它们的开销。为了便于比较，有频率漂移和偏移估计的算法都用8对时间标进行估计，无频率漂移和偏移估计的算法需交换8次信息。根据几种算法各自的原理计算同步开销，表1示出了几种算法在一跳内同步的开销，n为需要同步的节点个数。

表1 不同算法开销比较

从表1中可以看出，与同为接收者-接收者方式的RBS算法相比，本文算法大幅减少了开销，具有很大优势。与发送者-接收者方式的TPSN算法和FTSP算法相比，本文算法优于TPSN算法，劣于FTSP算法。

3.2 同步精度比较

通过实验比较了各个算法在没有MAC层时间戳的情况下的同步精度。在实验环境中，采用外接32 kHz晶体振荡器的CC1310物联网射频芯片来实现不同的算法。用公差为5～30 ppm的晶振作为内部数字控制振荡器的时钟源。

本文算法用3个CC1310模块按照图1的拓扑结构进行同步实验。参考节点每秒钟广播一次数据包。在普通节点与时间基准点同步后，将普通节点估计出的时间与时间基准点的实际时间的差作为同步误差，时间基准点的实际时间可以用指令在CC1310上查看。其余同步算法也通过CC1310实现，为了模拟传感器节点的在线处理过程，在收到信标后，接收节点会通过USB线将信标包传输到基站。基站收集并跟踪带时间戳的数据包。在实现TPSN和FTSP同步算法时，普通节点在接收到信标包后立即将确认消息发送回时间基准点。每种算法统计了3个小时的实验数据并求出平均同步误差。实验结果如图3所示，显示了广播信标包次数与平均同步误差的关系。

图3 无MAC层时间戳

实验结果表明随着广播包次数的增加，几种算法的时间同步精度略有提高，在无MAC层时间戳的情况下，消除了发送方时延的RBS和本文算法的精度远大于未能消除访问时延的FTSP与TPSN算法。N=10时，本文算法的同步精度约为7 us。实验结果证明在无MAC层时间戳的情况下，本文算法可以实现微秒级的同步精度。

4 结语

现有的多数同步算法要在MAC层时间戳可用这一条件下才能实现较高的同步精度，但是很多现代的无线射频芯片不支持MAC层时间戳，这限制了设备选择芯片类型的范围。本文针对传感器节点的射频芯片不支持MAC层时间戳的情况，提出了基于接收者的时间同步算法。接收节点会在同步周期内存储时间戳并利用最小二乘法计算出相对时钟漂移和偏移，时间基准点在同步周期结束时会通过广播参数的方法减少同步报文交换的次数，进而降低能量消耗。在同步精度方面，通过与几种经典算法的对比可知，本文算法在芯片不支持MAC层时间戳的情况下也能实现较好的同步精度。在未来工作中，将完善算法在大规模高密集场景中的功能，提升算法的泛化能力。