传感器网络原理与应用

《传感器网络原理与应用》学习报告——时间同步技术学号：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中一个可以根据该差值更改它的本地时间，从而使得这两个接收节点的时间达到同步。图2RBS时间同步机制的基本过程优：RBS时间同步协议思路比较新颖，利用无线信道的广播特性来同步接收节点的时间，去除了时间同步误差中所有发送节点引入的误差，比采用往返时间的时间同步机制具有更高的精度。劣：RBS同步过程中需要第三方节点广播同步消息，随着传感器节点数量的增加，时间同步过程中的消息传递数量也会显著增长，因此也显著地消耗了节点能量。因此，RBS协议并不适用于规模较大的网络，扩展性较差，适用于构造局部时间，对于需要时间同步但不需要绝对时间的传感器网络应用非常有用。2)算法二：TPSN时间同步机制传感器网络时间同步协议TPSN是Ganeriwal等人提出的与传统网络NTP时间同步协议类似的无线传感器网络时间同步算法，它的目的是能够提供全网范围内节点间的时间同步，是基于发送者一接收者的双向时间同步算法的典型代表，属于类客户-服务器模式。TPSN协议采用层次型网络结构，假定网络中的每个传感器节点具有唯一的身份标识号ID，节点间的无线通信链路是双向的，能够通过双向的消息交换实现节点间的时间同步。在网络中有一个根节点，这个根节点可以是配备有GPS设备能够获取外界时间的节点，作为整个网络系统的时间源；也可以是一个根据某种算法规则指定的节点，不需要与外部进行时间同步，只进行传感器网络内部的时间同步。TPSN协议首先将所有节点按照层次结构进行分级，然后每个节点与上一级的某一个节点进行时间同步，以此类推上去，最终所有节点都与根节点达到时间同步。Step1：层次发现阶段(leveldiscoveryphase)。在网络部署后，根节点首先广播级别发现分组，启动层次发现阶段。级别发现分组包含发送节点的ID和级别。根节点的级别是0，在根节点广播域内的邻居节点收到根节点发送的分组后，将自己的级别设置为分组中的级别加1，即为第1级，以此建立起自己的级别。然后将自己的级别和ID作为新的发现分组广播出去。当一个未建立自己级别的节点收到第i级节点的广播分组后，记录下发送这个广播分组的节点ID，把自己的级别设置为1i，并广播自己的级别。这个过程一直持续到网络中的每个节点都有一个自己的级别。如果节点己经建立起了自己的级别，它就忽略其他的级别发现分组。Step2：同步阶段(synchronizationphase)。层次建立后，根节点(级别为0）通过广播时间同步分组(timesync)启动同步阶段。第1级节点收到分组后，各自随机等待一段时间，然后与根节点交换消息，从而同步到根节点。第2级节点侦听到第1级节点的交换消息后，后退和等待一段随机时间，然后与第1级节点交换信息，同步到第1级节点。依次类推，每个节点都与层次结构中最靠近的上一级节点进行同步，直到所有节点完成同步，都同步到根节点。图3TPSN机制中相邻级别节点间消息交换过程图3显示了邻近级别的节点对之间交换两个消息实现时间同步的过程。节点S属于第i级节点，节点C属于第1i级节点，1T和4T表示节点C的本地时钟在不同时刻测量的时间，2T和3T表示节点S本地时钟在不同时刻测量的时间，V表示两个节点之间的时间偏差，d表示消息的传播时延，并假设请求消息和应答消息的传播时延是相等的。节点C在1T时刻发送同步请求分组给节点S，分组包含S的级别和1T时间，节点S在2T时间收到分组，2T=(1T+d+V)，然后在3T时刻返回一个应答消息给C，消息中包含节点S的级别和1T、2T和3T的信息，节点C在4T记录应答消息到达的时刻，4T=(3T+d-V)，据此可以推出：2143214322TTTTTTTTdV于是，节点C在计算出于节点S的时间偏差V之后，将它的时间同步到S。优：与RBS协议相比，TPSN协议考虑了传播时间和接收时间，利用双向消息交换的平均延迟，提高了同步精度。该协议能够实现全网范围的节点同步，同步误差与跳数距离成正比，能够取得良好的精度。劣：TPSN协议协议的收敛速度相对较慢。其主要不足之处是没有考虑根节点失效问题的处理，另外，当新的传感器节点加入网络时，需要初始化层次发现阶段，这种静态的级别特性减少了算法的鲁棒性。因此，它适用于精度要求较高，需要短期间的全网节点时间的无线传感器网络应用。3)算法三：DMTS时间同步机制DMTS延迟测量时间同步机制基于同步消息在传输路径上的所有延迟进行简单的分段估计和补偿，来提高时间同步的精度，通过广播和转发同步消息的方式完成时间同步。在DMTS机制中，有一个时间主节点广播同步时间信息，称为时间参考节点(简称参考节点)，同步信息中包含此分组的发送时刻。在收到广播分组后，所有接收节点都测量和估算这个广播分组的传输延迟，在此基础上，设置本地的时间为广播分组所携带的时间加上该分组的传输延迟时间，从而同步到该参考节点。DMTS机制的同步精度完全取决于延迟测量的精度。其分组延迟的测量过程如图4所示。图4DMTS机制中广播分组延迟的测量Step1：发送节点在检测到信道空闲时，给广播分组加上时间戳0t，通过这种在MAC层添加时间戳的方法，用来去除发送端的发送时延和MAC层的访问时延这两部分对同步精度的最大影响Step2：参考节点需要在发送广播消息前发送前导码和起始字符，以便接收节点进行接收同步。根据发送消息的比特数n和发送每比特需要的时间t，可以估计出前导码和起始字符的发送时间为nt；Step3：广播分组的到达时刻，接收节点加上时标t，并在调整自己的时钟之前再加上时标2t，接收端的处理延迟就是21tt。如果忽略无线信号的传播延迟，那么接收节点从0t时刻调整时钟前所经历的时间大约为21nttt，于是，接收节点就根据这一总的延迟的估计值，调整自己的时钟到021tnttt，与发送节点时钟同步。优：DMTS机制通过使用单个广播时间分组对各个延迟进行分段估计和补偿，无需复杂的运算和操作，是一种轻量级的能量有效的时间同步机制，能够实现单跳广播范围内所有节点的同步。劣：DMTS机制在复杂度、能耗和同步精度之间进行了折中考虑，精度取决于估计的准确性，在较复杂的环境中具有较大的波动。因此，该时间同步机制比较适用于对精度要求不高的无线传感器网络应用中。三、最新的时间同步算法文章一：ExternalGradientTimeSynchronizationinWirelessSensorNetworks1)关键词：外部时间同步externaltimesynchronization梯度时间同步gradienttimesynchronization(GTSP)2)摘要说明：现有的外部时间同步算法当中，不能够很好地和周围节点同步；另一方面，仅有的目的在于优化周围节点同步误差的协议，缺乏使节点同步于参考节点的技巧。因此构造了这样一种基于应用需求的，既有外部时间同步，又有周围节点间的（紧）同步的算法叫做ExternalGradientTimeSynchronizationProtocol(EGSync)，并研究它的可行性。算法内容：每个节点通过自身的时间信息流同步于一个参考节点，同时添加一致性协议使它同步于它周围的节点。3)算法：图5EGSync通用策略图Step1：传感器节点执行EGSync算法，使得其硬件时钟速度和硬件时钟的值和预先定义的参考节点ref，也就是根节点root的相应值一致。Step2：每个节点vV通过维持一个知识库来记住周围节点的时间信息。并且通过这个知识库，节点v可以参考自己的硬件时钟，在任何时刻计算出相对硬件时钟速率。Step3：节点v需要维持额外的三个变量，refvl代表最新的比率系数，refv表示最新的硬件时钟和逻辑时钟之间的差值，vseq表示节点接收到参考节点的最大序列数目。Step4：每次节点v从它的邻节点接收到,,,,refrefuuvvvHLlseq信息帧，并且比较自己和邻节点的硬件时钟。假设两者之间的硬件时钟是线性关系，通过最小方差来拟合直线。Step5：节点v通过接受到的信息帧，可以估算出邻节点u在任意时刻的逻辑时钟值。通过同步参考节点的逻辑时钟的值，我们可以计算出参考节点的硬件时钟值。4)优：通过实验的结果我们可以看出，在直线形拓扑结构当中，本算法EGSync和GTSP的最大时钟偏移相当，明显优于FTSP算法；在环形拓扑结构当中，三种算法表现都比在直线形拓扑中要好，EGSync和GTSP的性能依旧相当，FTSP算法最大时钟偏移明显减小，与前两种算法的差距减小。5)劣：EGSync算法的不足在于，需要一个固定的参考节点，并且它需要在传感器网络部署前预先定义。当该参考节点瘫痪时，传感器网络就无法同步到外部时间。文章二：EfficientTimeSynchronizationinaWirelessSensorNetworkbyAdaptiveValueTracking1)关键词:floodingbasedtimesynchronizationy基于