传感器网络原理与应用.

《传感器网络原理与应用》学习报告

——时间同步技术

学号：6141905039 姓名：唐波 专业：控制科学与工程

一、时间同步基本概述

1) 时间同步概念

时间同步是传感器网络技术研究领域里的一个新热点，它是无线传感器网络应用的重要组成部分，很多无线传感器网络的应用都要求传感器网络节点的时钟保持同步。

在集中式管理的系统中，事件发生的顺序和时间都比较明确，没有必要进行时间同步。但在分布式系统中，不同节点都有自己的本地时钟。由于不同节点的晶振频率存在偏差，以及温度变化和电磁干扰等，即使在某个时刻所有节点都达到时间同步，他们的时间也会逐渐出现偏差。

2) 时间同步的意义

在无线传感器网络的应用中，传感器节点将感知到的目标位置、时间等信息发送到传感器网络中的首领节点，首领节点在对不同传感器发送来的数据进行处理后便可获得目标的移动方向、速度等信息。为了能够正确地监测事件发生的次序，就要求传感器节点之间实现时间同步。在一些事件监测的应用中，事件自身的发生时间是相当重要的参数，这就要求每个传感器节点维持唯一的全局时间以实现整个网络的时间同步。

文档

实用标准

3) 时间同步算法优劣性判别标准

无线传感器网络时间同步算法设计的目的是为网络中节点的本地时钟提供共同的时间戳。我们评价一个无线传感器网络时间同步算法的性能，主要包括了网络能量效率、可扩展性、精确度、健壮性、寿命、有效范围、成本和尺寸、及时性等指标。

① 能量效率。无线传感器网络的主要特点就是节点的能量受限问题，涉及的时间同步算法需以考虑节点有效的能量资源为前提。

② 可扩展性。无线传感器网络需要部署大量的传感器节点，时间同步方案应该有效扩展网络中节点的数目或者密度。

③ 精确度。精确度的需要依赖于特殊的应用和时间同步的目的而有所不同，对某些应用，知道时间和消息的先后顺序就够了，而对某些其他的，则要求同步精度到微秒级。

④ 健壮性。无线传感器网络可能在敌对区域长期无人管理，一旦某些节点失效，在余下的网络中，时间同步方案应该继续保持有效并且功能健全。

⑤ 略。

二、传统时间同步算法

1) 算法一：RBS时间同步机制

RBS参考广播时间同步协议是2002年由J.Elson等人提出的基于接收者一接收者的时间同步。该协议利用了无线数据链路层信道的广播特性，一个节点发送广播消息，在无线

文档

实用标准

传输范围内的一组节点可以认为是几乎同时接收到该广播消息，这就把消息延迟中非确定因素的最主要部分一发送时延和访问时延消除在外，如图1所示。然后接收到广播消息的这组节点通过交换各自接收到消息的本地时刻，计算时间差值，从而实现它们之间的时间同步。

图1 时间同步机制关键路径

参考广播时间同步协议最简单的情形是两个节点单跳范围内的时间同步，其基本过程如图2所示。

Step1：第三方节点广播一个信标分组，在其广播范围内的节点A和B都能够接收到这个分组；

Step2：节点A和B根据自己的本地时钟记录收到该消息的时刻；

Step3：节点A和B交换它们记录的信标分组的接收时间，节点A和节点B记录的接收时间的差值就是这两个节点之间的时间偏差；

Step4：节点A和B中一个可以根据该差值更改它的本地时间，从而使得这两个接收

文档

实用标准

节点的时间达到同步。

图2 RBS时间同步机制的基本过程

优：

RBS时间同步协议思路比较新颖，利用无线信道的广播特性来同步接收节点的时间，去除了时间同步误差中所有发送节点引入的误差，比采用往返时间的时间同步机制具有更高的精度。

劣：

RBS同步过程中需要第三方节点广播同步消息，随着传感器节点数量的增加，时间同步过程中的消息传递数量也会显著增长，因此也显著地消耗了节点能量。

因此，RBS协议并不适用于规模较大的网络，扩展性较差，适用于构造局部时间，对于需要时间同步但不需要绝对时间的传感器网络应用非常有用。

2) 算法二：TPSN时间同步机制

文档

实用标准

传感器网络时间同步协议TPSN是Ganeriwal等人提出的与传统网络NTP时间同步协议类似的无线传感器网络时间同步算法，它的目的是能够提供全网范围内节点间的时间同步，是基于发送者一接收者的双向时间同步算法的典型代表，属于类客户-服务器模式。

TPSN协议采用层次型网络结构，假定网络中的每个传感器节点具有唯一的身份标识号ID，节点间的无线通信链路是双向的，能够通过双向的消息交换实现节点间的时间同步。在网络中有一个根节点，这个根节点可以是配备有GPS设备能够获取外界时间的节点，作为整个网络系统的时间源；也可以是一个根据某种算法规则指定的节点，不需要与外部进行时间同步，只进行传感器网络内部的时间同步。TPSN协议首先将所有节点按照层次结构进行分级，然后每个节点与上一级的某一个节点进行时间同步，以此类推上去，最终所有节点都与根节点达到时间同步。

Step1：层次发现阶段(level discovery phase)。在网络部署后，根节点首先广播级别发现分组，启动层次发现阶段。级别发现分组包含发送节点的ID和级别。根节点的级别是0，在根节点广播域内的邻居节点收到根节点发送的分组后，将自己的级别设置为分组中的级别加1，即为第1级，以此建立起自己的级别。然后将自己的级别和ID作为新的发现分组广播出去。当一个未建立自己级别的节点收到第i级节点的广播分组后，记录下发送这个广播分组的节点ID，把自己的级别设置为i1，并广播自己的级别。这个过程一直持续到网络中的每个节点都有一个自己的级别。如果节点己经建立起了自己的级别，它就忽略其他的级别发现分组。

Step2：同步阶段(synchronization phase)。层次建立后，根节点(级别为0）通过广播时间同步分组(time sync)启动同步阶段。第1级节点收到分组后，各自随机等待一段时间，然后与根节点交换消息，从而同步到根节点。第2级节点侦听到第1级节点的交换消息后，后退和等待一段随机时间，然后与第1级节点交换信息，同步到第1级节点。依次

文档

实用标准

类推，每个节点都与层次结构中最靠近的上一级节点进行同步，直到所有节点完成同步，都同步到根节点。

图3 TPSN机制中相邻级别节点间消息交换过程

图3显示了邻近级别的节点对之间交换两个消息实现时间同步的过程。节点S属于第i级节点，节点C属于第i1级节点，T1和T4表示节点C的本地时钟在不同时刻测量的时

T2和T3表示节点S本地时钟在不同时刻测量的时间，表示两个节点之间的时间偏差，间，

d表示消息的传播时延，并假设请求消息和应答消息的传播时延是相等的。节点C在T1时

刻发送同步请求分组给节点S，分组包含S的级别和T1时间，节点S在T2时间收到分组，

T2=(T1+d+)，然后在T3时刻返回一个应答消息给C，消息中包含节点S的级别和T1、T2和T3的信息，节点C在T4记录应答消息到达的时刻，T4=(T3+d-)，据此可以推出：

T2T1T4T32dT2T1T4T32

于是，节点C在计算出于节点S的时间偏差之后，将它的时间同步到S。

文档

实用标准

优：

与RBS协议相比，TPSN协议考虑了传播时间和接收时间，利用双向消息交换的平均延迟，提高了同步精度。该协议能够实现全网范围的节点同步，同步误差与跳数距离成正比，能够取得良好的精度。

劣：

TPSN协议协议的收敛速度相对较慢。其主要不足之处是没有考虑根节点失效问题的处理，另外，当新的传感器节点加入网络时，需要初始化层次发现阶段，这种静态的级别特性减少了算法的鲁棒性。

因此，它适用于精度要求较高，需要短期间的全网节点时间的无线传感器网络应用。

3) 算法三：DMTS时间同步机制

DMTS延迟测量时间同步机制基于同步消息在传输路径上的所有延迟进行简单的分段估计和补偿，来提高时间同步的精度，通过广播和转发同步消息的方式完成时间同步。

在DMTS机制中，有一个时间主节点广播同步时间信息，称为时间参考节点(简称参考节点)，同步信息中包含此分组的发送时刻。在收到广播分组后，所有接收节点都测量和估算这个广播分组的传输延迟，在此基础上，设置本地的时间为广播分组所携带的时间加上该分组的传输延迟时间，从而同步到该参考节点。DMTS机制的同步精度完全取决于延迟测量的精度。其分组延迟的测量过程如图4所示。

文档

实用标准

图4 DMTS机制中广播分组延迟的测量

Step1：发送节点在检测到信道空闲时，给广播分组加上时间戳t0，通过这种在MAC层添加时间戳的方法，用来去除发送端的发送时延和MAC层的访问时延这两部分对同步精度的最大影响

Step2：参考节点需要在发送广播消息前发送前导码和起始字符，以便接收节点进行接收同步。根据发送消息的比特数n和发送每比特需要的时间t，可以估计出前导码和起始字符的发送时间为nt；

Step3：广播分组的到达时刻，接收节点加上时标t，并在调整自己的时钟之前再加上时标t2，接收端的处理延迟就是t2t1。如果忽略无线信号的传播延迟，那么接收节点从t0时刻调整时钟前所经历的时间大约为ntt2t1，于是，接收节点就根据这一总的延迟的估计值，调整自己的时钟到t0ntt2t1，与发送节点时钟同步。

优：

DMTS机制通过使用单个广播时间分组对各个延迟进行分段估计和补偿，无需复杂的

文档

实用标准

运算和操作，是一种轻量级的能量有效的时间同步机制，能够实现单跳广播范围内所有节点的同步。

劣：

DMTS机制在复杂度、能耗和同步精度之间进行了折中考虑，精度取决于估计的准确性，在较复杂的环境中具有较大的波动。

因此，该时间同步机制比较适用于对精度要求不高的无线传感器网络应用中。

三、最新的时间同步算法

文章一：External Gradient Time Synchronization in Wireless Sensor

Networks

1) 关键词：外部时间同步external time synchronization

梯度时间同步gradient time synchronization(GTSP)

2) 摘要说明：

现有的外部时间同步算法当中，不能够很好地和周围节点同步；另一方面，仅有的目的在于优化周围节点同步误差的协议，缺乏使节点同步于参考节点的技巧。

因此构造了这样一种基于应用需求的，既有外部时间同步，又有周围节点间的（紧）同步的算法叫做External Gradient Time Synchronization Protocol (EGSync)，并研究

文档

实用标准

它的可行性。

算法内容：每个节点通过自身的时间信息流同步于一个参考节点，同时添加一致性协议使它同步于它周围的节点。

3) 算法：

图5 EGSync通用策略图

Step1：传感器节点执行EGSync算法，使得其硬件时钟速度和硬件时钟的值和预先定义的参考节点ref，也就是根节点root的相应值一致。

Step2：每个节点vV通过维持一个知识库来记住周围节点的时间信息。并且通过这个知识库，节点v可以参考自己的硬件时钟，在任何时刻计算出相对硬件时钟速率。

refreflStep3：节点v需要维持额外的三个变量，v代表最新的比率系数，v表示最新的

硬件时钟和逻辑时钟之间的差值，seqv表示节点接收到参考节点的最大序列数目。

文档

实用标准

refrefHu,Lu,l,vv,seqv信息帧，Step4：每次节点v从它的邻节点接收到并且比较自己和

邻节点的硬件时钟。假设两者之间的硬件时钟是线性关系，通过最小方差来拟合直线。

Step5：节点v通过接受到的信息帧，可以估算出邻节点u在任意时刻的逻辑时钟值。通过同步参考节点的逻辑时钟的值，我们可以计算出参考节点的硬件时钟值。

4) 优：

通过实验的结果我们可以看出，在直线形拓扑结构当中，本算法EGSync和GTSP的最大时钟偏移相当，明显优于FTSP算法；在环形拓扑结构当中，三种算法表现都比在直线形拓扑中要好，EGSync和GTSP的性能依旧相当，FTSP算法最大时钟偏移明显减小，与前两种算法的差距减小。

5) 劣：

EGSync算法的不足在于，需要一个固定的参考节点，并且它需要在传感器网络部署前预先定义。当该参考节点瘫痪时，传感器网络就无法同步到外部时间。

文章二：Efficient Time Synchronization in a Wireless Sensor Network by

Adaptive Value Tracking

1) 关键词: flooding based time synchronizationy基于流的时间同步

adaptive value tracking (AVT)提出的算法

2) 摘要说明：

文档

实用标准

一种理想的基于流的时间同步协议既不需要快速的实时时间信息传播又不需要一直跟踪他们的邻节点。另外，这样一个协议对于低计算量、通讯和小的内存是严格需要的。由此提出了一种时间同步算法，核心在于自适应值追踪（adaptive-value tracking）。通过调整比率同步时钟的时间偏移，将会获得整个网络内时间同步。

3) 算法：

AVTS算法的目标是使传感器节点同步于参考节点的时钟，该算法动态地选择参考节点并且将它的时间信息广播到网络中。每个传感器根据收到的时间信息，调整自己的时间偏移，在并不知道参考时钟实际值的情况下，尝试找到和参考时钟之间的比率关系。

Step1：每个节点u都是一个adaptive value tracker，avtu提供了逻辑时钟的比率信息，sequ存储了从参考节点接收到的最大序列数目。

Step2：启动u，初始化avtu，调整初始值，使得逻辑时钟和硬件时钟同比率变化。最后初始化sequ，启动周期定时器。

Step3：u为了调整自己的逻辑时钟比率，u减去从自己的逻辑时钟值当中估计到的接收到的参考时钟。如果误差大于，u反馈给逻辑时钟需要减小变化率；如果误差大于，

u反馈给逻辑时钟需要增大变化率；误差在容许范围内，逻辑时钟avtu保持不变。最终u从

接收到的逻辑时钟值中更新自己的逻辑时钟。

4) 优：

通过实验结果可知，AVTS在小型实时网络中能够提供很好的紧的同步性，并且能够

文档

实用标准

保证网络长时间的时间同步性质量。该算法明显优于FCSA算法。

5) 劣：

在AVTS中，节点的的逻辑时钟的更新是突入其来的，由于这种更新策略的缺陷，使得该算法的逻辑时钟对于大的信息延迟是比较敏感的。

文章三：Time Synchronization in WSNs: A Maximum-Value-Based Consensus Approach

1) 关键词：Convergence收敛性

Maximum consensus最大值一致性

2) 摘要说明：

在不考虑通信时延时，提出了MTS协议，通过这种算法每个节点的斜率和偏移都可以被同时同步。在具有通信时延，并且节点间的时延都是正的随机信号，提出一种WMTS（加权MTS协议），这种算法可以抵消通信时延的影响，可以根据预期完全同步时钟斜率，并且可以获得良好的精度，但是始终偏移不能够被同步。

4) 算法：

MTS：

Step1：设置节点初始值，斜率为1，偏移为0，设置全局广播间隔T。

文档

实用标准

itStep2：如果某个节点的硬件时钟满足T和偏移广播给他的邻节点。

N，则该节点把他的硬件时钟值、斜率

itStep3：i节点在t1时刻收到j的数据包，则i记录本地的硬件时钟和收到的信息包

[jt1,(aj(t1),bj(t1))]。

[it0,jt0]，计算aij和qij并且删除[it0,jt0]。

Step4：如果i有历史记录

iStep5：判断qij与1之间的关系，更新(ai,b)，存储

[it1,jt1]。

WMTS：

Step1：设置节点初始值，斜率为1，偏移为0，wi0,rii，设置全局广播间隔T。

Step2：如果有的邻节点。

itlT,lN，节点i广播信息包包括it，wi，ri，(ai,bi)给他

itk,jtk。 Step3：i收到第k1次节点j的信息包在tk时刻，记录Step4：计算aij(k),qij(k)，判断qij(k)值，并且更新wi，ri，(ai,bi)。

Step5：存储aij(k)和

[itk,jtk]。

文档

实用标准

5) 优：

MTS和WMTS算法都提供了更快的收敛速度，使得同步可以在有限时间内达到；MTS协议可以使时钟斜率和时钟偏移同时达到同步；WMTS协议可以有效地解决随机通信延时。

6) 劣：

缺乏对复杂网络模型的研究，同时没有做理论结果的实验验证。

四、未来的发展方向

方向一：3篇新文献有待研究的问题

文章一中EGSync算法使用了一个固定的参考节点，当这个节点出现故障的时候EGSync算法就无法被实现。可以多加入几个参考节点或者使用动态参考节点来改进EGSync算法的稳定性。

文章二中AVTS算法还有待研究的问题是，当需要微秒级的时间同步精度时AVTS算法的部署和效果。

文章三中对提出的MTS和WMTS两种协议做了严格分析和一致性证明，并且通过仿真比较了和现有算法ATS的优劣。接下来可以研究一下这两个算法在实际应用中的具体效果，或者将这两种算法应用在大型复杂的模型上。

方向二：时间同步的发展方向

文档

实用标准

1. 节点间的紧时间同步算法和具有参考的节点的外部时间同步之间的相互结合；

2. 对于时间同步精度提出了更高的要求；

3. 越来越重视算法在实际当中的应用效果；

4. 针对的越来越复杂的系统模型；

文档