摘要：
TPSN时间同步算法研究,TPSN时间同步算法研究CONTENTS目录WSN时间同步概述TPSN时间同步算法一种基于优化拓扑的时间同步算法N-... TPSN时间同步算法研究CONTENTS目录WSN时间同步概述TPSN时间同步算法一种基于优化拓扑的时间同步算法N-TPSN01WSN时间同步概述WSN时间同步概述23概念：各个节点定期或不定期与其他节点交换本地时钟信息，并在协议或算法控制下调整本地时钟，实现全局时间一致的过程。WSN为何需要时间同步：不同节点晶体振荡不同，存在累计误差；受能量、存储、带宽限制；分布式系统，要求节点必须实现同步，不同系统要求程度不同。时间同步要解决的问题：保证同步的精度；尽量小的功耗；保证网络的可扩展性。WSN时间同步概述——时间同步的误差来源晶体振荡不同节点的晶体振荡器间存在误差，并且也会受到环境影响，这一误差会随时间累积。成本、资源由于WSN资源受限，通信信道质量不佳时；节点密度大时，易造成延迟和出错，导致时间误差。同步协议需在性能和开销间取得平衡，即用较小的通信代价取得较好的同步效果。协议执行信道出错，导致部分节点不能被同步，影响网络的整体时间同步情况。WSN时间同步概述——时间同步算法的分类（1）（1）基于接收者——接收者（Receiver--Receiver）的时间同步基于接收者——接收者的时间同步算法，主要利用了无线信道的广播属性。
主要原理是引入一个节点作为辅助节点，由该节点广播一个参考分组，在广播域内的一组接收节点接收到这个参考分组，通过比较各自接收到消息的的本地时间，实现它们之间的时间同步。由于其他节点只需要监听信息而不需要同步到参考节点，该类型算法的优点在于可以避免发送节点时延的影响，但缺点在于信息交换次数较多，能耗较大。该种类型的代表性算法是RBS算法。WSN时间同步概述——时间同步算法的分类（2）（2）基于发送者——接收者（Sender--Receiver）的双向时间同步基于发送者——接收者的双向时间同步算法，类似于传统Internet中的NTP协议，即基于客户机——服务器架构。待同步节点发送时间同步请包，基准节点接收到这一同步请求后反馈自身当前时间，待同步节点接收到反馈的信息后计算时间偏差并予以调整，完成时间同步。该类型算法优点在于同步的高精度，而缺点就是节点分层的维护和多次两点间信息交换，大大增加了能耗。该种类型的代表性算法是TPSN算法、LTS算法。WSN时间同步概述——时间同步算法的分类（3）（3）基于发送者——接收者（Sender--Receiver）的单向时间同步基于发送者——接收者的单向时间同步算法，相对于双向的时间同步算法，只需要基准节点向待同步节点进行单向数据包传递。
主要原理是基准节点广播包含自己节点时间信息的时间同步数据包，待同步节点在接受到这一数据包后，根据时间戳信息，开始计算数据通信过程中数据包延迟的各个组成部分，得到时间差值的待同步节点将对这些时延进行补偿，并完成了自己向参考节点的同步。该类型算法优点在于算法复杂度低、能耗小，缺点在于同步精度较低。该种类型的代表性算法是DMTS算法和FTSP算法。02TPSN时间同步算法TPSN时间同步算法主要思想层次发现时间同步采用层次型网络结构，分为层次发现和时间同步两个阶段。实现所有树节点的时间同步，第i层的节点与第(i-1)层的一个节点同步，最终所有节点都能在时间上与根节点同步，从而实现整个网络的时间同步。每一个节点赋予一个层次，第i层的节点至少要能够与第(i-1)层的节点通信；——主要思想TPSN时间同步算法——层次发现阶段该阶段主要工作是把整个网络进行分层。时钟源节点作为根节点，广播级别发现数据包来启动分层过程。数据包中包含着节点自身的ID和所属层次。每个初次接收到级别发现数据包的节点需要将层次加1并继续广播，直到完成整个网络的分层工作。当根节点的邻居收到这一数据包，便把自己的层次置为1，并向下继续广播新的级别发现数据包。
01040203TPSN时间同步算法——时间同步阶段ddA：i层节点B：i+1层节点TPSN时间同步算法——时间同步阶段B节点根据与A节点的时间偏差Δ同步到A节点的时间结论：缺点优点在MAC层消息开始发送到无线信道时才添加时间信标，消除了访问时间带来的误差；利用双向交换信息计算消息的平均时延，精度相对较高。节点失效（尤其是靠近根节点的节点失效）会导致同步错误，并在网络扩散；新节点加入时，需初始化层次发现步骤，扩展性差；不适合移动节点或多跳同步等情况。TPSN时间同步算法——优、缺点03一种基于优化拓扑的时间同步算法N-TPSNN-TPSN时间同步算法——问题描述无线传感器网络各项技术具有一项共同的性能指标，即能量消耗。传感器节点除了待机耗能外，几乎所有能量都用来通过无线信道发送和接收数据包。问题：研究方向：对于无线传感器网络时间同步算法，也希望降低算法能量损耗降低在时间同步过程中的数据包交换次数。N-TPSN时间同步算法——算法思想（1）本次算法设计的应用背景是大规模、多跳、弱动态的无线传感器网络，其单跳拓扑图如图所示，其中，实线表示1跳节点向参考节点发送的时间同步请求，虚线表示参考节点回馈的数据包。
根据TPSN算法流程，在网络分层结束同步过程开始后，每个1跳节点需要向参考节点发送同步请求数据包，等待参考节点回馈后完成时间差值计算，同步到参考节点；随着节点数量的增加，节点密度增大，单跳范围内节点数量变大到n，在TPSN协议中，此单跳范围内的数据包交换次数为2n。由于节点密度增大后，某个1跳节点（假设为A节点）和参考节点的通信范围内很可能覆盖其他的1跳节点，由于无线信道广播特性，A节点和参考节点的数据包交换过程可以被其他被覆盖的1跳节点监听到。利用这些信息，这些被覆盖的1跳节点便能发现自己与参考节点的时间差值进而同步到参考节点。以此思路为基础进行单跳层次内的算法优化设计。N-TPSN时间同步算法——算法思想（2）上图示意了2跳内的TPSN算法，节点的编号0-1表示该节点是第0层的1号节点，1-9表示该节点是第1层的9号节点，依此类推。TPSN的分层思想是多跳无线传感器网络时间同步算法中比较科学、先进的解决思想。TPSN协议在多跳情况下，下层节点需要向邻近的每个上层节点进行时间同步请求。比如图中的17号节点，需要向8号节点和9号节点分别进行同步请求。但这两个节点的反馈包被17号节点接受并进行数据综合处理后，并不能保证17号节点的同步精度比单独与一个节点进行时间同步精度更高。
如果17号节点只与9号节点同步，16号节点只与7号节点同步，8号节点便不需要进行时间同步数据包的接收和回馈工作。以此进行层次间的算法优化。N-TPSN时间同步算法——层次内开销优化设计（1）TPSN算法的数据包交换流程如图3-4所示，O为上层节点，A、B、C均为下层节点。图中节点按A、B、C顺序依次与O节点进行时间同步，实现表示下层节点发送时间同步请求，虚线表示上层节点回馈。N-TPSN算法数据包交换流程如图3-5所示，B、C节点均在A和O节点的单跳范围内，由于无线信道具有广播特性，A与O节点间的数据包交换可以被B、C两个节点监听到。以单跳内四个节点为例，N-TPSN时间同步算法——层次内开销优化设计（2）1.同步请求2.上层回馈3.偏差计算4.时间修正上图可以完成1跳范围内某节点与上层节点通信范围覆盖的所有节点的时间同步工作，这些被覆盖的节点只需要监听无线信道并对接收到的数据包进行分析计算即可，大大降低了TPSN的算法开销。N-TPSN时间同步算法——层次间开销优化设计（1）网络拓扑简化，采用选择最佳邻居的拓扑优化思路，该算法被命名为best-NeighborTPSN，即N-TPSN。
N-TPSN时间同步算法——层次间开销优化设计（2）检测1跳邻居计算2跳邻居计算最佳邻居保存选中名单1号节点的1跳节点中只有2、4、6、8号节点需要向1号节点发送时间同步请求数据包，3、5、7、9号节点只需要进行无线信道的监听。在1跳范围内的节点被同步到1号节点之后，2跳节点只需要向之前进行了同步数据交换的节点发送请求，即10、11节点只需要向2号节点发送时间同步请求数据包。相对于TPSN协议，一方面3、5、7、9四个节点节省了1跳范围内时间同步时主动发起的一次数据请求，另一方面节省了下层节点时间同步时与他们的一次完整的数据交换。THANKYOU
