物联网与传感器技术中的时钟同步技术

1.时钟同步

时钟同步对任何分布式系统而言都是很重要的，无线传感器网络中许多算法或协议也需要节点间的时钟同步作为支撑。在无线传感器网络的应用中，传感器节点采集的数据如果没有空间和时间信息是无任何意义的。准确的时间同步是实现传感器网络自身协议的运行、数据聚集、TDMA调度、协同休眠、定位等的基础。例如，多个传感器联合来探测一个运动目标，如车辆或者坦克的轨迹，每个传感器将它观测到的位置和时间返回到处理中心，如果这些时钟不事先同步，那么无法判断观测到的位置的时序，从而无法计算出轨迹。在数据链路层采用时隙分配的MAC协议时，节点间如果不能保持时钟同步，会造成时隙混乱，无法有效利用带宽资源。

对于无线传感器网络而言，节点的本地时钟的频率是由晶体振荡器（简称为晶振）和计数寄存器构成，每出现一定数量的振荡脉冲，寄存器值就增加1，访问该寄存器便可知当前时间。在本地时钟基础上，可构造不同类型的软件时钟。由于节点采用的晶振性能差异较大，且晶振频率受电压、温度及使用时间等多种因素的影响，使晶振的实际工作频率与出厂标定值有差异，导致节点之间时钟不同步。

（1）速率恒定模型

对于速率恒定模型，r（t）=dC（t）/dt=常数，即晶振频率为常值。当要求的时钟同步准确度远低于频率变化引起的偏差时，该模型的假设是合理的。

（2）漂移有界模型

通常情况下，时钟速率r（t）在一定范围内波动，即1-ρ≤r（t）≤1+ρ，其中，ρ为时钟漂移。对于低成本的网络节点而言，一般有ρ∈[1，100]×10^-4%。

（3）漂移变化有界模型

时钟漂移的变化ξ（t）=dρ（t）/dt是有界的，即-ξ_max≤ξ（t）≤ξ_max。对于节点i和j，用C_i（t）、C_j（t）表示它们在t时刻的时间值。若采用速率恒定模型，C_i（t）可表示为C_i（t）=a_it+b_i。由此可知，任意两个节点i和j的时钟满足如下线性关系：

C_i（t）=a_ijCj（t）+b_ij （5-11）

式中，a_ij和b_ij分别为相对漂移与相对偏移。

当两个节点的时钟保持同步，即C_i（t）=C_j（t）时，a_ij=1、b_ij=0。因此，对于采用速率恒定时钟模型的场合，时钟同步就是对（a_ij，b_ij）进行估计，这样，两个节点在新的时刻便保持时钟同步。

时钟同步算法执行周期是系统的关键之一，以此选择合适的时钟同步算法执行周期十分重要。过于频繁地执行时钟同步算法会占用一定的时间和带宽资源，特别是控制报文开销。但时钟同步算法执行的时间间隔过长时，时钟偏差不能满足相关应用对时钟同步的准确度要求，进而影响相关协议和应用的性能。重要的是当节点间时钟偏差不满足协议和应用要求时，才执行时钟同步算法。下面推导时钟同步间隔与同步误差、时钟漂移率的关系。若f为晶振工作频率（MHz），ρ为时钟漂移率，f₊、f_-分别为晶振的最大和最小工作频率，则

f₊=（1+ρ）f （5-12）

f_-=（1-ρ）f （5-13）

则节点间时钟周期偏差最大值为

累计同步误差为

t_Δ=t_syncTΔf （5-15）

式中，t_sync为两次时钟同步的时间间隔。因此

在无线传感器网络中的时钟同步算法评价指标包括定量和定性两个方面。其中，定量指标包括同步准确度、计算复杂度、协议收敛时间等；定性指标包括可扩展性、能量有效性、容错等。

在这些过程中，必须注意以下几个方面的问题：同步准确度决定了节点间以某一基准进行时间同步的偏差；计算复杂度决定了算法在选定参与转发数据帧的节点所发送的分组数的量级；协议收敛时间决定了时间同步算法在全网内完成一个轮回所用时间，即从网络时间发生变化到网络上所有的相关节点都得知这一变化，并且相应地完成同步算法所需要的时间；系统的可扩展性决定了在传感器网络应用中，节点随机分布，因此分布密度通常不均匀，时钟同步机制必须能够适应这种网络范围和节点分布密度的变化；能量保障性决定了系统的生存期，必须最小限度且均匀地使用节点能量。为了减少能量消耗，应使网络时钟同步的交换信息尽可能地少，网络通信和计算处理的能耗应可预知，时钟同步机制应该根据网络节点的能量分布，均匀地使用网络节点的能量来达到能量的高效使用。

2.传统的时钟同步

在传统网络中，已经提出了多种网络同步机制，C/S模式是主要的时钟同步模式。客户端产生时钟同步请求消息，服务器回应时钟同步应答消息，通过测试这两个消息的发送和接收时间来估计两者的时间偏差，获得相对较准确的时钟同步。采用上述思想的典型例子就是网络时间协议（NTP），被互联网用作网络时钟同步协议，NTPv4准确度已达到毫秒级。实现方案是在网络上指定若干时钟源服务器，为用户提供授时服务，并且这些服务器之间能够相互比较校正，以提高准确度。NTP采用层次型树形结构，整个体系结构中有多棵树，每棵树的父节点都是一级时间基准服务器。NTP要将时间信息从这些一级时间服务器传输到分布式系统的二级时间服务器成员和客户端，第三级时间服务器从第二级服务器获得时间信息，以此类推，服务器级数越小，越接近一级服务器，时间就越准确。由于NTP设计对象为互联网和计算机，设计重点为协议的可靠性和同步准确度。该协议要求能够始终占用CPU资源，以便它可以执行连续的操作，使时钟一直保持同步，没有考虑能耗和计算能力问题，无法直接用于无线传感器网络中。(www.xing528.com)

在无线传感器网络应用中，节点对功耗有严格的要求，并且要求尽可能保持较小的外形尺寸和低廉的成本，使其能够被大量部署，其部署环境经常是常人难以接近的恶劣环境，这使得部署后的维护通常是不可能的；显然将GPS和NTP用于无线传感器网络的时间同步是不可取的。分布式系统中对时间同步也有大量研究，但这些方法都没有考虑传感器网络的特点，需要较大的资源开销，所以不适合无线传感器网络的时间同步。鉴于时间同步在无线传感器网络应用中的基础性作用，必须研究适用于无线传感器网络的时间同步算法。

3.时钟同步方法

时钟同步方法在系统中十分重要，它决定了传感网节点的协调一致的准确度，解决这个问题依靠的是时间同步协议。通常时间同步协议可分为两类，即发送与接收的同步和接收与接收的同步。最基本的方法是发送者在报文中嵌入发送时刻，而接收者则记录下报文接收到的时刻。利用这些时间信息可估算出收发双方的时间偏差，通过对时间偏移的补偿，实现收发双方的时钟同步。

接收与接收的同步协议，与发送与接收的同步协议不同。接收与接收的同步协议是为了多个接收者的同步。节点之间为了达到同步，需要交换各种各样的消息，受信道质量、节点工作环境和节点配置等因素的影响，同步消息在传输过程中的延迟具有不确定性，这是无线传感器网络时钟同步的主要挑战之一。同步消息从发送方要依次经过发送时间延迟、发送方MAC访问时间延迟、物理层传播延迟、接收方MAC层接收延迟、接收方应用程序层延迟，最终才能到达接收方的应用程序层。

采取的主要方法有：发送时间是用来产生同步消息并向MAC层提交发送请求，该过程的持续时间取决于当前处理器的载荷和操作系统的负担，因而具有不确定性，典型值为0～100ms。访问时间用来等待信道空闲的时间，取决于网络的流量，也具有不确定性，典型值为10～500ms。传输时间是用来传输同步消息的时间，取决于消息的长度和无线电波的传输速度，具有确定性，典型值为10～20ms。传播时间是同步信息离开发送方至接收方的时间，取决于两者的距离，具有确定性，但该时间通常可忽略，典型值小于1μs（距离小于300m）。接收时间与发送方的传输时间特性相同，且在同步消息传输过程中两者重叠，典型值为10～20ms。接收处理时间是接收方用来处理同步消息的时间，与发送时间的特性相同，典型值为0～100ms。因此，一般在发送方MAC层后对同步消息添加时间戳，接收方在接收时间后添加时间戳，减少发送时间、访问时间和接收处理时间延迟的不确定性给同步准确度带来的影响。

4.硬件支持的时钟同步

在节点上安装GPS接收机，实现节点时钟与UTC（协调世界时）同步，是典型的额外硬件支持的同步方法。虽然GPS的时钟同步准确度可达纳秒级，但GPS能耗大，且某些情形下无法接收CPS信息，不适合大规模的无线传感器网络应用。

压控晶体振荡器（VCO）时钟同步机制利用参考时钟与节点本地时钟的偏差作为PI控制器的输入，控制器的输出为控制电压，用来控制VC0的输出频率。当本地时钟与参考时钟一致时，PI控制器的输出为常值，VCO的振荡频率亦为常值。

5.广播式时钟同步

“第三方广播”的方式参照节点利用物理层广播周期性地向网络中其他节点发送参照广播。在广播域中的节点，用自己的本地时钟记录各自的包接收时间，然后相互交换记录的时间信息。由于RBS（参考广播时钟同步）采用接收者之间进行同步的方法，在关键路径中排除了发送方的发送时间和访问时间对同步准确度造成的影响，使得广播同步机制得到比双向成对同步好得多的同步准确度。RBS的缺点是对网络有一定的要求，不适合点对点通信的网络。节点间交换本地时间也需要额外的消息开销，对于由n个节点构成的单跳网络，需要O（n²）的消息交换。当n很大时，消息交换开销和节点的计算开销也非常大，扩展性差。另外，RBS实现的是接收节点之间的时钟同步，未实现与参考节点的同步。DMTS算法引入时间戳（标记参考节点发送同步消息时刻）的概念，参考节点向区域内的节点广播带有时间戳的同步消息，接收节点通过准确地测量从发送节点到接收节点的单向时间延迟，结合发送节点中的时间戳计算时间调整值。这就避免了RBS算法中需要节点之间交换时钟信息，且无法与参考节点的时钟保持同步的缺点，但DMTS算法是以牺牲时间来换取较低的计算复杂度和消息复杂度。

DMTS算法没有估计时钟的频率漂移，时钟保持同步的时间较短，也没有消除时钟准确度的影响，因而其准确度不高，不适用于定位等要求高准确度同步的应用。

FTSP算法也是使用单向广播消息实现发送节点与接收节点之间的时钟同步，但是算法的具体实现与DMTS算法有所不同。FTSP算法采用参考节点多次广播带有发送时间戳的同步消息的方法，使每个节点获得多个属性对，通过集中式线性回归法对时钟的相对漂移和相对偏移进行估计。为了提高时间戳标记的准确度，FTSP算法通过对收发过程时延的分析，进一步降低了时延的不确定性。

6.双向时钟同步

双向成对同步典型代表有TPSN、Tiny-Sync/Mini-Sync，节点i在T₁时刻向节点j发送同步消息SYNC_MSG，节点j用自身的时钟记录同步消到达的时刻T₂，则T₂=T₁+D+d，其中，D是消息的传输时间；d是节点之间的时钟偏移。然后，在T₃时刻节点j向节点i返回一个包含T₂与T₃的应答消息ACK_MSG，节点i在T₄时刻收到该应答消息，则T₄=T₃+D-d。若在发送同步消息和应答消息过程中的传输时间相同，通过式（5-17）可计算时钟偏移和传输时间。

传感器网络时间同步（TPSN）算法是双向成对同步方法，分为层次发现阶段和同步阶段。

层次发现阶段的目的是在网络中产生一个分层的拓扑结构，并使每个节点都赋予一个层次号。同步阶段的核心就是节点间成对的消息交换。该阶段由根节点的time_svnc包发起，当接收到这个包，第一层的节点发起与根节点的双向消息交换。在发起消息交换之前，为最小化无线信道冲突，每个节点都要等待一个随机时间。一旦接收到根节点的应答消息，用式（5-17）计算它们之间的时钟偏移和传输时间，并调整自身时钟到根节点的时钟。第二层节点监听到第一层的一些节点与根节点的通信后，发起与第一层节点的双向消息交换，再一次需要等待一个随机时间，以确保上层节点完成同步。这个过程最终使所有节点都与根节点同步。该过程中，下层节点不可避免地会与多个上层节点同步。

TPSN算法的缺点是一旦根节点失效，就要重新选择根节点，并重新进行上述两个过程，增加了计算和能量开销。同步阶段所用时间随节点数目的增加而线性增加。协议要求网络构造层次结构，使得它不适合于高度移动的节点。用洪泛广播方式构造层次树，通信开销较大。但同步误差随着包含时间戳的消息路径跳数的增加而增加，在稀疏网络中，跳数一般较多，这明显影响了同步准确度。萤火虫同步技术对耦合延迟、耦合强度、耦合性质、初始相位、网络拓扑等隐私很敏感。虽然在两个振荡器的同步收敛性研究上取得一定进展，但无论是理论研究或模拟研究，研究者在某些结论上还不能达成一致。但有一点可以认同：在实际系统中，基于萤火虫同步技术会取得一定误差范围内的同步。

上述算法都可以扩展到多跳情形，但同步准确度与单跳情形相比略有降低，且随着跳数的增加，误差也会增加。值得注意的是，双向成对时钟同步需要两个节点间分别交换消息，这就意味着在共享信道时，由于MAC协议的不合理会导致信道冲突。

7.锁相环同步

考虑到无线传感器网络中，由于节点和链路失效等因素导致拓扑结构动态变化的特点，以及为均衡能量损耗、延长网络生存期而采用拓扑控制等系统性优化能耗的方案对网络带来的影响，沿用FTSP中根节点的选取和维护方案，着重讨论广播域内单跳同步机制与原理，在此基础上扩展到整个网络的多跳机制是较为直接和方便的。在一个广播域内，时钟参考节点（时标）周期性地广播同步分组，分组中携带了时标节点的本地时钟，为避免广播分组在发送、访问信道和接收过程中，由于系统和信道状态的不确定性因素可能引入的误差，采用在MAC层加盖时间戳的方案。收到同步分组的节点容易得到两个时钟间的差，FTSP算法和DMTS算法直接用差值进行了偏移补偿。如果能通过分析这个差值时间序列，得到两个时钟相对漂移的信息，一次完成偏移和漂移补偿，则这样的时间同步算法会更有效率。因为它不会再像FTSP算法那样，为了进行线性回归处理而维护大量的历史数据。为此，需要设计一个简单的滤波器来递推估计差值序列的变化，进行相应的校正。将这一新机制称为广播校正同步机制。

下面结合锁相环技术中的锁频原理，介绍同步算法的机理。h₁（k）、h₂（k）分别表示广播分组中携带的参考时钟和任意节点的同步时钟，它们的差值e（k）经过低通滤波器处理后，消除了高频噪声。为了方便设计，采用常用的比例积分（PI）控制器作为滤波器，控制信号v（k）作为压控晶体振荡器（VCO）的输入，k₀是VCO的基准频率。不难看出，VCO的输出频率f（k）随着误差信号e（k）动态地发生变化。f（k）经过零阶保持器和积分环节后转化为节点的同步时钟，基于锁相环的时钟同步需要压控振荡器支持，追加额外的硬件是追求低成本节点实现所不期望的。