第6章无线传感器网络--时间同步

1、第第6 6章章无线传感器网络的支撑技术无线传感器网络的支撑技术1n传感器网络用户的使用目的千变万化，作为网络终端节点的功能归根结底就是传感、探测、感知，用来收集应用相关的数据信号。n为实现用户的功能，除要设计通信与组网技术以外，还要实现保证网络用户功能的正常运行所需的其它基础性技术。2无线传感器网络的支撑技术n时间同步机制n定位技术n数据融合n能量管理n安全机制3时间同步技术4分布式系统需要时间同步n不同的节点都有自己的本地时钟n即使在某个时刻所有节点都达到时间同步，它们的时间也会逐渐出现偏差n分布式系统要进行协同工作5时间同步机制是分布式系统基础框架的一个关键机制。传感器网络时间同步的作用1

2、. 构成TDMA调度机制2. 估计监测目标的运行方向和速度3. 通过测量声音的传播时间能够确定节点到声源的距离或声源的位置6时间同步n物理时间用来表示人类社会使用的绝对时间n逻辑时间表达事件发生的顺序关系，是一个相对概念n分布式系统通常需要一个表示整个系统时间的全局时间7现有的时间同步技术n网络时间协议NTP(Network Time Protocol)是Internet采用的时间同步协议。nGPS可用来提供网络的全局时间同步。8传感器网络实现时间同步的限制因素n价格和体积成为传感器网络时间同步的重要约束。n节点造价不能太高n节点的体积微小n消耗的能量9n现有网络的时间同步技术不适合传感器网络

3、n计算机性能对传感器节点而言高很多,能源也能够不断得到供给；n现有网络的时间同步机制往往关注于达到最大的同步精度方面，而较少考虑计算和通信的开销,没有考虑计算机消耗的能量。nNTP、GPS等现有时间同步机制不适用于传感器网络10时间同步技术nGPS可用来提供网络的全局时间同步。11n传感器网络中进行时间同步的设计思路：1. 少量的传感器节点携带如GPS的硬件时间同步部件2. 大多数传感器节点根据“时间同步机制”交换同步消息，与网络中的其他传感器节点保持时间同步。12n传感器网络具有应用相关的特性n在众多不同应用中很难采用统一的时间同步机制13传感器网络的时间同步机制的设计要求（1）扩展性（2）

4、稳定性（3）鲁棒性（4）收敛性（5）能量感知n进行时间同步所需的网络通量和计算量要可预知14传感器网络的时间同步机制的主要性能参数1) 最大误差n传感器节点之间的最大时间差量n相对外部标准时间的最大时间差量2) 同步期限n节点间保持时间同步的持续时间长度n瞬间同步 n永久同步3) 同步范围n要保持时间节点间同步的区域范围n地理范围 单位：米n逻辑距离 单位：跳数15传感器网络的时间同步机制的主要性能参数4) 可用性n在同步范围内的覆盖完整性5) 效率n达到同步精度所经历的时间以及消耗的能量。6) 代价和体积n硬件成本n节点体积166.2 网络时间同步机制17NTP设计思想n网络时间同步模式：C

5、/S模式n进行时间同步的2种方案：n基本方案：n时间服务器周期性地向客户端发送时间同步消息，同步消息中包含服务器的当前时间。n扩展方案 客户端主动产生时间同步请求消息，服务器回应时间同步应答消息； 测量这两个分组总的往返时间来估计单程的延迟18NTP协议n被用作Internet的时间同步协议n最新的NTP v4精确度己经达到了毫秒级19NTP协议的基准时间的实现方案n在网络上指定若干时钟源服务器，为用户提供授时服务，并且这些服务器站点之间能够相互比对以提高准确度。n时钟源服务器采用世界标准时间 (UTC)n是当前所有时钟基准的国际标准n时间服务器获取当前世界标准时间的来源：n位于科罗拉多的WW

6、V短波广播电台n卫星20NTP协议的体系结构1. NTP协议采用层次型树型结构，整个体系结构中有多棵树n每棵树的父节点都是一级时间基准服务器n一级时间基准服务器直接与UTC时间源相连接2. 将时间信息从这些一级时间服务器传输到分布式系统的二级时间服务器成员，第3层服务器从第2层服务器获取时间，以此类推21NTP协议的体系结构3. 层数表示时间服务器到外部UTC时钟源的距离。n层次数限制为154. 客户端是叶节点22NTP协议的基本原理n需要进行时间同步的客户端首先发送时间请求消息，然后服务器回应包含时间信息的应答消息。NTP协议的基本原理 T1：客户端发送时间请求消息的时间(客户端的时间) T

7、2 ：服务器收到时间请求消息的时间(服务器的时间) T3：服务器回复时间应答消息的时间(服务器的时间) T4 ：客户端收到时间应答消息的时间(客户端的时间) 1 ：时间请求消息在网上传播所需要的时间。 2 ：时间应答消息在网上传播所需要的时间。NTP协议的基本原理n设客户机与服务器时间相差：Ts = Tc+ 关系式(4-1)成立:假设时间请求消息和时间应答消息在网上传播的时间相同，即即 1=2NTP协议的基本原理n设客户机与服务器时间相差：Ts = Tc+ 假设假设 1=2n客户端根据T1、T2、T3和T4的数值计算出与服务器的时差,从而调整它的本地时间。n消息传输的非确定性延迟（1和2可能不

8、相等）是影响客户端与服务器时间同步精度的主要因素。消息传输延迟细分为四个部分1.发送时间2. 访问时间3. 传播延迟4. 接收时间27各种延时对时间同步精度的影响n局域网信道访问延迟往往变化比较大n广域网的传输延迟抖动也比较大n发送延迟和接收延迟的变化相对较小286.3传感器网络时间同步机制29NTP不适合无线传感器网络1. NTP协议应用在有线网络，链路网络失败概率小 传感器网络: 无线链路， 通信质量较差2. 网络结构的稳定性nNTP协议的网络结构相对稳定，便于为不同位置的节点手工配置时间服务器列表；n传感器网络的拓扑结构动态变化，简单的静态手工配置无法适应这种变化。30NTP不适合无线传

9、感器网络3. NTP协议中时间基准服务器间的同步需要基础设施的协助4. NTP协议需要通过频繁交换消息来不断校准时钟频率偏差带来的误差；31GPS进行时间同步的局限性1. 需配置高成本的GPS接收机2. 在室内、森林或水下等有障碍的环境中无法使用GPS系统3. 如果用于军事目的，没有主控权的GPS系统也是不可依赖的32在传感器网络中只可能为极少数节点配备GPS接收器，这些节点为传感器网络提供基准时间传感器网络的常用时间同步机制336.3.1 参考广播 同步机制RBS(Reference Broadcast Synchronization)n一种基于接收者和接收者的时间同步机制n利用了无线数据链

10、路层的广播信道特性，引入一个节点作为辅助节点n辅助节点广播一个“参考分组”n在广播域内的一组接收节点接收到这个“参考分组”n信号传播时间很短，可以认为这一组接收节点是同时收到“参考分组”n通过交换、比较各自接收到“参考分组”的本地时间，实现一组接收节点之间的时间同步34RBS机制的基本过程1. 发送节点广播一个“信标(beacon)分组”，广播域中两个节点都能够“同时”接收到这个分组。35RBS机制的基本过程2. 每个接收节点分别根据自己的本地时间记录接收到“信标分组”的时刻；n接收节点1上记录的接收时间是t1 （节点1的本地时间n 接收节点2上记录的接收时间是t2 （节点2的本地时间）n 从

11、全局时间上看， t1 和t2 所表示的时间是同一个时刻。36t1t2RBS机制的基本过程2.每个接收节点分别根据自己的本地时间记录接收到“信标分组”的时刻；n 设接收节点1上记录的接收时间是t1 （节点1的本地时间n 设接收节点2上记录的接收时间是t2 （节点2的本地时间）n 从全局时间上看， t1 和t2 所表示的时间是同一个时刻。373. 接受节点1和2，交换 t1 和t2 RBS机制的基本过程384. 两个接收时间的差值d=(t1 -t2 )相当于两个接收节点间的时间差值 n让其中一个接收节点可以根据这个时间差值d更改它的本地时间，从而达到两个接收节点之间的时间同步RBS机制nRBS机制

12、中不是通告发送节点的时间值，而是通过广播同步指示分组“信标分组”实现接收节点间的相对时间同步。n广播信道中的所有接收方“同时同时”收到信标分组，接收方之间就有了一个同步参考时间n信标分组何时发送出去不重要39RBS机制n对于传播时间，RBS机制只关心信标分组到不同接收节点的传播时间的差值nRF信号，可以忽略了传播时间的时间偏差n声音信号，不能忽略传播时间的偏差40n误差主要来源于：n信号传播时间的差值n接收节点底层硬件的接收速度41 RBS机制应用于多跳网络42 RBS机制应用于多跳网络1. 非邻居节点A和B分别发送信标分组，在相同广播域内的接收节点之间能够时间同步。nA发送信标分组后，完成同

13、步节点、和的时间；nB发送信标分组后，完成同步节点、和的时间；43 RBS机制应用于多跳网络2. 节点4处于两个广播域的交集处，使得根据节点4的时间能够同步两个广播域内节点间的时间44如何得到网络中事件间的全局时间关系1. 假设发生在节点1和节点7附近的两个事件n设节点1监测到事件的时间为：tE1 （节点1的本地时间）； n设节点7监测到事件的时间为：tE7 （节点7的本地时间）；45如何得到网络中事件间的全局时间关系2.假设节点A和节点B分别在Pa和Pb时间点发送信标分组;n设节点1是在收到节点A发送的信标分组之前的d1秒观察到事件E1 , tE1=Pa d1n设节点7是在收到节点B发送的信

14、标分组之前的d2秒观察到事件E7 ， tE7=Pb d23. 其他节点从节点4知道节点A发送分组比节点B晚d秒Pa =Pb+d4. 可知：可知： tE1 =tE7+d d1 + d2 46RBS时间同步的优点nRBS机制利用信道的广播特性来同步接收节点时间，去除了时间同步误差中所有发送节点引入的部分n比采用往返时间的时间同步机制NTP具有较高的精度47nRBS的缺点nRBS机制的时间同步精度受“接收节点间接收时间差”的影响较大n改进方法：n通过多次广播信标分组获得平均值，能够提高RBS机制的时间同步精度48后同步思想n通常情况下节点的时间不必同步n当监测到一个事件发生时，节点才采用RBS机制进

15、行时间同步n优点：n节省传感器节点的能量n缺点：n不适应于需进行长距离或长时间通信的时间同步的应用496.3.2 TPSN时间同步协议n传感器网络时间同步协议TPSN(Timing-sync Protocol for Sensor Networks),提供传感器网络全网范围内节点间的时间同步。50TPSN时间同步协议基本思想nTPSN是基于发送者和接收者的双向时间同步机制n基于客户机/服务器架构n待同步节点向基准节点发送同步请求包，基准节点回馈包含当前时间的同步包，待同步节点估算时延并校准时钟。51TPSN时间同步协议基本思想n在网络中有一个与外界通信获取外界时间的节点称为根节点nGPS接收机

16、n整个网络系统的时钟源n采用层次型网络结构n首先将所有节点按照层次结构进行分级n每个节点与上一级与上一级的一个节点进行时间同步52TPSN协议包括2个阶段n第1个阶段：生成层次结构n每个节点赋予一个级别n根节点赋予最高级别第0级n第i级的节点至少能够与一个第(i-1)级的节点通信n第2个阶段：实现所有节点的时间同步n第1级节点同步到根节点，n第i级的节点同步到第(i-1)级的一个节点53TPSN协议的主要思想分为两个阶段:n第一阶段是层次发现阶段n给每一个节点赋予一个级别，第i级的节点至少要能够和一个第(i-1 ) 级的节点通信;n第二阶段是时间同步阶段n实现所有树节点的时间同步，第i 级的节

17、点同步第(i-1) 级的一个节点54生成层次结构阶段1. 根节点通过广播“级别发现(level-discovery)分组”启动层次发现阶段n“级别发现分组”包含发送节点的ID和级别2. 根节点的邻居节点收到“级别发现分组”n将自己的级别设置为发送“级别发现分组”中根节点的级别加1 ，（设为级别1）n广播新的“级别发现分组”，”级别字段”值为155生成层次结构阶段3. 节点收到第i级节点的广播的“级别发现分组” n记录发送这个广播分组的节点IDn设置自己的级别为(i+1)n广播级别设置为(i+1)的“级别发现分组”分组4. 重复步骤3，直到网络内的每个节点都被赋予一个级别56节点一旦建立自己的级

18、别，就忽略任何 “级别发现分组”同步阶段1. 层次结构建立以后，根节点通过广播“时间同步分组”启动同步阶段2. 第1级节点收到这个分组后，通过与根节点交换消息同步到根节点3. 第2级节点侦听到 第1级节点的交换消息后，等待等待一一段随机段随机时间时间后，与它的父节点交换消息进行同步4. 每个节点与层次结构中最靠近的上一级节点进行同步，最终所有节点都同步到根节点。57相邻级别节点间的时间同步机制n相邻级别的两个节点对间通过交换两个消息实现时间同步58相邻级别节点间的时间同步机制nT1和T4: 节点S的本地时钟测量的时间；nT2和T3: 节点R的本地时钟测量的时间；59相邻级别节点间的时间同步机制

19、n设表示两个节点之间的时间偏差n设d表示消息的传播时延，假设d1=d260TR TS=d=d1=d2相邻级别节点间的时间同步机制n节点S在T1时间发送同步请求分组给节点R，分组中包含S的级别和T1值 n 节点R在T2时间收到分组： T2=T1+d+ -(1)61TR TS=d=d1=d2相邻级别节点间的时间同步机制n节点R在T3时间发送应答分组给节点Sn分组中包含节点R的级别和T1、T2和T3的值n节点S在T4时间收到应答：T3=T4d+ -(2)62TR TS=d=d1=d2相邻级别节点间的时间同步机制n节点S可计算出：632143() ()2TTTT2143() ()2TTTTdTR TS

20、=d=d1=d2消除访问时间对误差的影响n在发送时间、访问时间、传播时间和接收时间四个消息延迟组成部分中，“访问时间”往往是无线传输消息时延中最具不确定性的因素。n解决方法：n为了提高两个节点间的时间同步精度,TPSN协议在MAC层消息开始发送到无线信道的时刻，才给同步消息加上时标，消除了访问时间的不确定性带来的时间同步误差。64与RBS机制相比的优点：nTPSN利用双向消息交换计算消息的平均延迟，提高了时间同步的精度。n在时钟频率为4MHz的Mica节点平台：n TPSN 平均误差是16. 95sn RBS 平均误差是29. 135s65TPSN的缺点：1）开销比较大n生成层次结构的消息：“

21、级别发现分组”n节点间时间同步消息：“同步请求分组”、“应答分组”2）实现全网范围内节点间的时间同步时，同步误差与跳数距离成正比增长。3）没有考虑根节点失效问题4）层次级别的建立是静态n新的传感器节点加入网络时，需要初始化层次发现阶段666.3.3 DMTS 同步机制n延迟测量时间同步DMTS (delay measurement time synchronization) 67n延迟测量时间同步(DMTS) 机制是基于发送者和接收者的单向时间同步机制。68DMTS 机制的基本原理1. 选择一个节点作为时间主节点广播“同步时间分组”，含有时间值t0 ； 2. 所有接收节点测量这个时间广播分组的

22、延迟Td 3. 接收节点把本地时间设置为: t0+Td 69DMTS 机制的广播“时间同步分组”的传输过程1. 主节点在检测到信道空闲时，给广播分组加上时间戳t070DMTS 机制的广播“时间同步分组”的传输过程2. 在发送广播分组前，主节点需要发送“前导码起始字符”，以便接收节点进行接收同步n设“前导码起始字符”的比特数为n；n设发送每比特位需要的时间t ;n “前导码起始字符”的发送时间为: n*t 71n*tDMTS 机制的广播“时间同步分组”的传输过程3. 接收节点记录“广播分组到达时刻值t1” ，并记录“在调整自己的时钟之前时刻值t2” n 接收端的接收和处理延迟： (t2-t1 )

23、72n*t(t2-t1) DMTS 机制的广播“时间同步分组”的传输过程 4. 接收节点从t0时刻到调整时钟前的时间长度约为: n*t+(t2-t1) 。n接收节点调整其时钟为：t0 +n*t +(t2 -t1) 73n*t(t2-t1) DMTS 机制的广播“时间同步分组”的传输过程1. 主节点在检测到信道空闲时，给广播分组加上时间戳t074DMTS 机制的广播“时间同步分组”的传输过程2. 在发送广播分组前，主节点需要发送“前导码起始字符”，以便接收节点进行接收同步n设“前导码起始字符”的比特数为n；n设发送每比特位需要的时间t ;n “前导码起始字符”的发送时间为: n*t 75n*tD

24、MTS 机制的广播“时间同步分组”的传输过程3. 接收节点在广播分组到达时刻记录时间t1 ，并在调整自己的时钟之前时刻再记录时间t2 n 接收端的接收处理延迟就是(t2-t1 )76进行时钟调整n*t(t2-t1) DMTS 机制的广播“时间同步分组”的传输过程 4. 接收节点从t0时刻到调整时钟前的时间长度约为: n*t+(t2-t1) 。n接收节点调整其时钟为：t0 +n*t +(t2 -t1) 77调整时钟n*t(t2-t1) DMTS 机制机制特点特点nDMTS 机制通过使用单个“广播时间分组”，能够同步单跳广播域内的所有节点，同时无需复杂的运算和操作，是一种能量有效的时间同步机制。78DMTS 机制在多跳网络