6) 及时性 :对于一些紧急事件的检测等传感器网络应用 的场合 ,需要将发生的事件立即发送给汇聚点 ( sink) ,这种特 性称之为“及时性 ”。若在事件发生后再进行同步就没有意 义了 ,因此节点之间需要经常进行“预同步 ”。 1. 3 成对节点间的同步
全网的时间同步是建立在成对节点间的同步基础之上 的 。节点 i和节点 j通过交换两个数据包就能够实现二者本地 时钟的同步 。
ห้องสมุดไป่ตู้
也就是 0. 1m s。 1. 5 基于层次的全网时间同步
算法的第一步是建立一个具有层次的拓扑结构 ,这是在
网络部署的初期建立的 。首先汇聚点 ( sink)点被赋值为级别 0,广播一个“建立级别 ”数据分组 ,从而开始一个级别建立过 程。
“建立级别 ”分组包含了发送节点的 ID 和发送节点的级 别 。当其他节点收到该分组后 ,就将级别加 1,并将发送节点
的时钟漂移率将不会超过 ρ, 则对于任意的真实时刻 t, 用 H ( t) 表示的一个节点的时钟定义为“ρ有界 ”的含义如下 :
1
节点 i在本地时钟 T1时刻发送一个同步脉冲分组 , 当节 点 j接收到该分组时 ,记录该分组到达的时间 T2, 则 T2等于 T1加上从节点 i到节点 j的传输时间 D,再加上节点 i和节点 j 的时钟偏差 d。即 : T2 = T1 + D + d。通常传输时间 D 是未知 的 ,它与节点间的距离和无线传播特性有关 。
关键词 :无线传感器网络 ;时间同步 ;成对同步 中图分类号 : TP393. 04 文献标识码 : A
T im e synchron iza tion protocol for w ireless sen sor networks
PEN G Gang1 , CAO Yuan2da1 , SUN L i2m in2 (1. D epa rtm en t of Com pu ter S cience and Eng ineering, B eijing Institu te of Technology, B eijing 100081, Ch ina;
布 [10 ] ,均值为 0,方差为 σ,实验测得 σ的值为 11μs。 访问时间 指分组到达 MAC层之后 ,等待得到访问信道
的时间 ,当然也包括载波侦听的时间 。和接收时间一样 ,因为 分组通过的是同一个无线信道和 MAC层 ,因此在节点间的访 问时间也是以 0为均值的高斯分布 。
由此可见 ,误差主要是接收时间和访问时间的组合 ,根据 二者的相关度可知 ,其方差最多增加 4倍 ,因此对于两个节点 的时间同步 ,基于 99%的可信度 ,其精确度可达 2. 3 ×4 ×σ,
远程时钟估计部件是用于决定网络中另外一个节点的本 地时钟 。它有两种实现方法 ,一是远程节点的时钟在一个消 息中进行“时间传输 ”,一个是在未知延迟上界时的“远程时 钟读取 ”。
时钟校准部件是指重新同步事件产生后估计出远程节点 时钟的信息并更新本地时钟 。 1. 2 传感器网络时间同步的考虑
应用十分 广 泛 的 同 步 机 制 是 GPS[8 ] 和 网 络 时 间 协 议 NTP[9 ] ,但这两个机制算法复杂 ,成本昂贵 ,因此不适合于传 感器网络 。
第 6期
彭刚等 :无线传感器网络时间同步协议
1 23 1
常有限的 ,而且不能补充或更换电能 。 2) 精确度 :针对不同的应用 ,精确度的要求具有很大的
差别 ,对某些应用可能只需分辨一些事件的前后顺序就足够 了 ,但是对于有些应用需要时间精确到毫秒级 。
3) 可扩充性 :传感器网络的应用都需要部署大量的传感 器节点 ,因此同步策略需要能够适应数量多和密度高的特点 。
作为其父节点 ,然后用新的级别形成新的“建立级别 ”分组继 续向其邻居节点广播 。每个节点继续该过程 ,直到所有的传 感器节点都收到了“建立级别 ”分组 ,并获得了其级别和父节
点。
若一个节点收到大于自己级别的数据分组 ,就丢弃 ,而收 到一个级别小的分组就更新其级别 。
算法的第二步是沿着这个建立的层次结构 ,在每对节点 之间使用成对的同步过程 。首先是汇聚点广播一个“时间同
4) 健壮性 :传感器网络往往是处于无人值守工作状态 , 工作在恶劣的环境下 ,因而要做到即使在部分节点失效的情 况下 ,网络的剩余部分也能保持协议的有效性 。
5) 成本和大小 :由于传感器节点的尺寸很小 ,且成本低 廉 ,若要附带很大而且很贵的 GPS设备是不可能的 。因此同 步算法要建立在十分有限的成本和尺寸基础上 。
Key words: wireless sensor networks; time synchronization; pair2w ise synchronization
0 引言
无线传感器网络是由大量的微传感器节点采用无线自组 织方式构成的网络 [1, 2 ] ,它的应用非常广泛 ,如车辆跟踪 、抗 震救灾 、动 植 物 栖 息 地 的 监 控 、病 人 身 体 状 况 的 监 测 等 等 。 [ 3, 4 ]
传统时钟同步技术的主要目的是如何获得高精度的时间 同步 。但是传感器网络时钟同步的目的是在满足一定精度的 情况下如何减少算法复杂性 ,从而减少电能的消耗 ,需要在精 确性和电能高效之间进行权衡和折衷 。主要说来 ,应该考虑 以下几个方面的问题 :
1) 电能的高效性 :这是由于传感器网络节点的电能是非
步 ”分组 ,然后属于层次 1 的节点就开始和汇聚点进行成对
的信息交换 。为了避免媒体访问的冲突 ,需要等待一个随机 的时间段后才开始进行成对的同步 。这些节点接收到一个响
应分组后 ,就调整本地的时钟和汇聚点进行同步 。
属于第 2级的节点会偷听到级别 1的消息交换 ,这是因 为第 2级的节点的邻居节点集合中至少有一个 1级节点 。当 第 2级节点偷听到该消息后 ,就等待一个随机的时间段后启
第 25卷第 6期 2005年 6月
计算机应用 Computer App lications
Vol. 25 No. 6 June 2005
文章编号 : 1001 - 9081 (2005) 06 - 1230 - 03
无线传感器网络时间同步协议
彭 刚 1 ,曹元大 1 ,孙利民 2 (1. 北京理工大学 计算机科学工程系 ,北京 100081;
下一步 ,节点 j发送第二个分组给 i, 该分组包含了时间 T1和 T2,还包含了 j发送该分组的时刻 T3。节点 i在 T4时刻接 收到该分组 ,则有 T4 = T3 + D - d。
两个节点交换分组的过程如图 1所示 。
图 1 成对同步的分组交换 于是在节点 i即可计算出两个节点时钟之间的偏差 d。 d = ( ( T1 - T2) - ( T4 - T3) ) /2 D = ( ( T2 - T1) + ( T4 - T3) ) /2 节点 i计算出二者的偏差后就可进行同步 , 然后还需再 发送一个分组将计算出的 d传输给节点 j。 上面的计算是基于一个假设 :从节点 i到 j和节点 j到 i的 传输时间相同 ,即 D1 = D2。当然 D1和 D2并不是完全相等的 , 这会导致一些同步的误差 。 1. 4 成对的同步误差分析 传输时间可细分为以下四个部分 : 发送时间 发送者装配消息的时间 ,包含消息处理时间 和缓冲时间 。在发送时间完成后分组才加上时间戳 ,因此发 送时间对传输时间没有影响 。 传播时间 信号在两个节点之间通过物理介质传播的时 间 ,该时间与节点间的距离有关 。传感器节点并不会快速移 动 ,因此双向的传播时间应该是相同的 。 接收时间 接收者从通道接收到一个消息并将此信息 告知主机的处理时间 。经实验 证 明 , 接 收 时 间 呈 现 高 斯 分
动和第 1级节点的同步过程 。 这个过程继续进行 ,直到全网的所有节点都和汇聚点的
时间同步起来 。由于传感器网络的冲突非常频繁 ,在等待响
应分组的同时要启动一个定时器 ,一旦定时器时间到 ,就会重 新发送一个“同步请求 ”分组 ,重新启动成对的时间同步 ,直 到同步成功完成 。
1. 6 全网时间同步误差 由于存在时钟漂移 ,假设时钟的漂移是以 ρ为界的 ,期望
本文提出的同步算法是一种基于层次式的时间同步算 法 ,充分考虑了传感器网络的特点 ,开销较小 ,还具有较好健 壮性和自组织性 。
1 时间同步协议
1. 1 通用的时间同步问题 同步可以通过硬件实现 ,也可以通过软件来实现 。一般
时间同步都由三个主要部件组成 :重新同步事件检测 、远程时
钟估计和时钟校准 。 重新同步事件检测表示节点在某个时刻必须重新同步它
2. 中国科学院 软件所 ,北京 100080) (penggang@126. com )
摘 要 :提出了基于层次结构的无线传感器网络时间同步协议 。首先以汇聚点为根节点建立一 个具有层次结构的树 ,然后采用成对同步法沿着该树建立一个全网统一的时钟 。仿真结果显示该协 议能满足无线传感器网络的时间同步要求 。
2. Institu te of S oftw a re, The Ch inese A cadem y of S ciences, B eijing 100080, Ch ina)
Abstract: A time synchronization p rotocol based on hierarchical structure was designed. In this p rotocol, at first a hierarchical structure tree was established w ith sink node as root node, then a pair w ise synchronization was performed along the tree to establish a global timescale throughout the sensor network. The simulation results show that the time synchronization p rotocol can be used for w ireless sensor network app lications.
正如所有的分布式系统一样 ,传感器网络的一个重要功 能是所有节点的时间同步问题 。传感所获得的数据必须具有 准确的时间和位置信息 ,否则采集的信息就是不完整的 。此 外 ,传感器节点的数据融合 、TDMA 定时 、休眠周期的同步等 等这些都要求传感器节点具有统一的时钟 。
以往提出了许多针对分布式系统的时间同步技术 [5～7 ] , 但是传感器网络对时间同步的要求和其他系统而言有很大不 同 ,它的规模很大 ,节点密集 。因此要求同步协议应能适应节 点数目的改变 ,而且传感器节点的电能十分有限 ,因此能量的 高效利用也是要考虑的主要问题 。
们的时钟 , 它有两种方式实现 。一是采用初始化的同步时钟 数 ,它以一个固定的速率 kR 进行同步 , R 表示单轮时间同步 周期 。k是大于 1的实数 ,以避免两轮同步过程出现重叠 。第二 个技术是当过了 kR时间之后 ,用一个特殊的节点发送一个初 始化消息给系统中其他的每一个节点 j。一旦节点 j收到该消 息 ,就启动自己的同步过程 ,同步的精度取决于消息的时延 。
收稿日期 : 2004 - 12 - 06;修订日期 : 2005 - 02 - 18 基金项目 :国家自然科学基金资助项目 (60272078) ;国家 863计划项目 (2001AA112051) 作者简介 :彭刚 (1968 - ) ,男 ,湖南衡阳人 ,副教授 ,博士研究生 ,主要研究方向 :无线网络协议 ; 曹元大 ( 1944 - ) ,男 ,江苏常州人 ,教授 , 博士生导师 ,主要研究方向 :人工智能 、网络安全 ; 孙利民 (1966 - ) ,男 ,河南郑州人 ,研究员 ,博士 ,主要研究方向 :无线移动网络 、宽带接入网.