– 逐层在相邻两层节点间同步 • 网络内两个节点的同步 – “后同步”查找两个节点间的路径 – 在路径的相邻两个节点间进行TPSN同步
HRTS（Hierarchy Referencing Time Synchronization Protocol）
• TPSN基于双向报文交换，因此同步精度高
• TPSN本质上是对同步，因此全网同步的同步 能耗高
FTSP（Flooding Time Synchronization Protocol）
• 同步精度高 • 工程实用性强 • 强调实现细节
FTSP（Flooding Time Synchronization Protocol）
• MAC层时间戳技术
– 和平台直接相关，书中给出了在Mica2平台下的实 现
健壮性
• • • •
外部环境复杂，搞毁能力 需要应对安全性挑战 无线传感器网络拓扑动态性较强 网络规模变化、需求变化
内容提要
1.
基本概念
2.
3.
传统与挑战
典型时间同步协议
4.
5.
新型同步机制
总结
典型时间同步协议
• NTP（Network Time Protocol）
• DMTS （Delay Measurement Time Synchronization）
• 节点遍历模式 • 聚类分层模式 • 扩散模式
GCS：节点遍历模式
• 游走阶段：记录游走的出发和到达时间 • 时间校正阶段：根据节点在游走环的位置和游 走时间对节点时间进行校正 • 理论假设：每段游走的时间花费相同
GCS：聚类分层模式
• 单纯的节点遍历方式导致遍历环过长， 同步功耗大 • 通过分簇协议，把网络组织成簇结构
• 簇头节点间以节点遍历方式同步
• 簇内节点可以节点遍历或RBS等方式进 行同步
GCS：扩散模式
• 越简单的方法往往是越有效的
• 同步过程：对接收到的时间进行平均操 作，并对自己的时间进行扩散 • 理论证明：当把所有节点的时间当成一 张快照时，经过若干轮扩散过程，所有 节点时间最终将收敛到所有节点时间的 平均值上
传感器网络的挑战
• • • • • •
室内、矿井、森林，有遮挡 低功耗、低成本和小体积 传输延迟的不确定性 可扩展性、移动性 健壮性、安全性 网络规模大、多点协作
传输延迟的不确定性
Sender
Send time Access time Transmission time
Receiver
Propagation time Reception time Receive time
传输延迟的进一步细化(在Mica2上)
时间 Send time & Receive time Access time Transmission time & Reception time Propagation time Interrupt waiting time Encoding time & Decoding time Byte alignment time 典型值 0~100ms 10~500ms 10~20ms <1μs（距离<300米） 在大多数情况下<5μs，在重 负载下，可达30μs 100~200μs，<2μs的抖动 0~400μs 特性 不确定，依赖处理器负载、操 作系统系统调用开销 不确定，依赖信道负载。 确定，依赖报文长度和发送速 率。 确定，依赖收发方物理距离和 传播媒质特性。 不确定，依赖处理器类型和处 理器负载。 确定，依赖射频芯片的种类和 设置。 确定，依赖发送速率和收发字 节偏移。
• 发送时间：发送节点构造和发送时间同步消息所用时间。e.g., 系 统调用时间；内核调度时间；消息从主机发送到网络接口时间。 • 访问时间：发送节点等待访问网络传输信道的时间。 • 传播延迟：发送节点传输到接收节点所经历的时间。 • 接收时间：从接收节点的网络接口接收到消息到通知主机消息达 到事件所经历的时间间隔。
BS
n1 n4
(c)
n3
(d)
HRTS（Hierarchy Referencing Time Synchronization Protocol）
• 根节点和应答者节点本质上是采用TPSN 同步 • 根节点和非应答者节点本质上是双向报 文交换同步（但非TPSN） • 应答者节点和非应答者节点本质上是接 收者--接收者同步
时间同步技术的分类
• 排序、相对同步与绝对同步
– 递进关系 – 各自具有典型的协议代表
• 外同步与内同步
– 参考源不同
• 局部同步与全网同步
– 同步对象的范围不同
时间同步技术的应用场合
• • • • • •
多传感器数据压缩与融合 低功耗MAC协议、路由协议 测距、定位（位置相关报务，LBS） 分布式系统的传统要求 协作传输、处理的要求 ... ...
时间同步技术
内容提要
1.
基本概念
2.
3.
传统与挑战
典型时间同步协议
4.
5.
新型同步机制
总结
内容提要
1.
基本概念
2.
3.
传统与挑战
典型时间同步协议
4.
5.
新型同步机制
总结
基本概念
• • • •
WSN时间同步技术背景 时间同步技术的分类 时间同步技术的应用场合 关键点：时钟模型
WSN时间同步技术背景
RBS （Reference Broadcast Synchronization）
• 接收者接收者同步的基本依据：接收者时 间相移均值为0
单跳RBS
• 用最小二乘法估计clock skew提高同步精度
多跳RBS
• 时间路由技术：基于最短路径查找
TPSN（Timing-sync Protocol for Sensor Networks）
简单，高效，可扩展性强
M&S模型
• • • • • 研究由初始不同步状态如何达到同步状态 个体性质相同,因此一旦达到同步则永远同步 萤火虫之间的交互被建模成电量耦合 耦合延迟规定为0 最终结论为:系统的同步收敛性取决于个体在 自由状态下的动力学特性 • 同步的实质：不同步产生了耦合，耦合改变 了状态量，而状态量又改变了相位量 ,相位差 通过同步过程不断缩小，最终达到完全相同, 即同步状态
• 由DMTS发现，广播能降低全网同步能耗 • 结合广播和节点间的双向报文交换同步 HRTS协议
HRTS（Hierarchy Referencing Time Synchronization Protocol）
n2 BS n1 n3 BS
n2
n1
n3
(a)
n2 BS n1 n3 n4 n2
(b)
• 体系结构（单机）
NTP（Network Time Protocol）
• • • •
NTP不适合于WSN 体积、计算能力和存储空间存在限制 传输方式不同：无线而非有线 目标不同：局部最优而非全局最优
GPS（Global Position System）
• 从根本上解决了人类在地球上的导航与 定位问题。 • 每颗卫星上配备有高精度的铷、铯原子 钟，并不断发射其时间信息 • 地面接收装置同时接收4颗卫星的时间 信息，采用伪距测量定位方法可计算出 时间和位置信息 • 缺点（室内、功耗、安全性、分布式）
TPSN（Timing-sync Protocol for Sensor Networks）
• 对同步误差的分析
– 很重要，是一种基本的分析方法
– 理论分析和实验证明：TPSN同步误差是 RBS的一半 – 结合对clock skew的估计，可以提高TPSN 的精度
多跳TPSN
• 全网周期性同步
– “层发现”把网络组织成最短生成树
2.
3.
传统与挑战
典型时间同步协议
4.
5.
新型同步机制
总结
传统与挑战
• 传统同步方法 • 传感器网络的挑战
传统同步：NTP与GPS
• NTP：网络时间协议 • GPS：全球定位系统
NTP（Network Time Protocol）
• 体系结构（网络）
NTP（Network Time Protocol）
• 否定：DMTSRBS • 否定之否定：RBSTPSN • TPSN：双报文交换的发送者接收者同 步
TPSN（Timing-sync Protocol for Sensor Networks）
节点A
T2
T3
Request
Reply
节点B
同步点
T1
T4
(T 2 T 1) (T 4 T 3) 2
接收者接收者：RBS （Reference Broadcast Synchronization
NIC NIC Sender
Sender
Receiver
Receiver1
Critical Path Receiver2
Time
Critical Path
•通过广播同步指示分组实现接收点间的相对时间同步 •RF信号的传播时间差值非常小 •可以消除接收节点的接收协议处理、上下文切换、网络接口向主机传 送 •影响RBS机制性能的因素：时钟偏差、接收点飞确定性因素以及接收 点的个数
• 基本同步原理
– 发送者--接收者同步 – 单个报文中包括多个时间戳（在报文的不同位置） – 根据单个报文中的多个时间戳，可对中断等待时 间进行补偿 – 对clock skew的补偿仍采用最小二乘法
多跳FTSP
• 洪泛方式广播时间基准节点的时间 • 协议健壮 • 实际做了工程化的实现
GCS（Global Clock Synchronization）