无线传感网络时间同步.pdf

发布时间：2022-06-10 发布人：admin 分类：说明书资料大小：0.20M 资料格式：pdf 举报版权申诉

x5762210-3089327-4744302543286794544.pdf-第1页.png

第1页 / 共7页

x5762210-3089327-4744302543286794544.pdf-第2页.png

第2页 / 共7页

x5762210-3089327-4744302543286794544.pdf-第3页.png

第3页 / 共7页

x5762210-3089327-4744302543286794544.pdf-第4页.png

第4页 / 共7页

x5762210-3089327-4744302543286794544.pdf-第5页.png

第5页 / 共7页

x5762210-3089327-4744302543286794544.pdf-第6页.png

第6页 / 共7页

x5762210-3089327-4744302543286794544.pdf-第7页.png

第7页 / 共7页

文本预览

一种基于双向消息交换的传感网时间同步算法1 http://www.paper.edu.cn 李顺辉，杨科华湖南大学计算机与通信学院，长沙 (410082) E-mail：sunfastlee@gmail.com 摘要：作为传感器网络应用的一项重要支撑技术，时间同步方法受到国内外传感器网络研究人员的广泛关注。由于传感器节点受到成本、能量和体积的限制，传感器网络的时间同步面临一些新的挑战。本文提出一种基于双向消息交换的低开销时间同步算法(Low-cost Time Synchronization Protocol, LTSP)，该算法通过两次同步操作实现全网的时间同步。实验结果表明：该算法在低开销设计的基础上，同步精度满足我们的预期目标。关键词：传感器网络；时间同步；时间信标中图分类号：TP312 1．引言传感器网络是由具备感应、无线通信及信息处理能力的微型传感器节点组成的网络，具有易部署、节点数目多、多跳自组织等特性。同时，节点本身具有能量缺乏、短距离通信、计算和存储能力有限等局限性。与以地址为中心的多跳寻址IP网络不同，传感器网络是一种以数据为中心的网络[1] [2]。时间同步作为分布式系统的一个重要基础，也是传感器网络的一项基本支撑技术，也是传感器网络实现数据融合、TDMA调度、协同睡眠等的基础。相关学者已经提出许多时间同步算法，这些算法主要有以下几类：基于接收者-接收者交互的时间同步、基于发送者-接收者的时间同步、单向时间传播和基于参数拟合的时间同步。各自的典型算法分别有：RBS[3]、 TPSN[4]、FTSP[5]和DMTS[6]、Tiny-Sync和Mini-Sync[7]协议。此外，新提出的两种同步技术分别是：萤火虫同步技术[8]和协作同步技术[9]，因其存在较多假设，故仍停留在理论探索和仿真阶段。本文在FTSP和TPSN的基础上，提出一种改进后的低开销时间同步算法LTSP，算法目标是使全网的时间同步精度与TPSN大致相当，同时对其进行了程序实现和性能比较，结果表明，LTSP算法在有效降低系统开销的同时，基本满足我们的预期精度目标。 2．经典时间同步算法 2.1 参考广播时间同步协议(Reference Broadcast Synchronization, RBS) RBS 协议是由 J.Elson 等人提出的一种接收者-接收者类型协议，在 RBS 协议中，一节点发送广播消息，其他接收到该广播消息的节点接收到消息时记录自身本地时间，然后各节点交换彼此记录的接收时间，并通过计算，来实现节点间的时间同步。 2.2 传感器网络时间同步协议(Timing-sync Protocol for Sensor Networks, TPSN) TPSN 算法是由加州大学网络和嵌入式系统实验室的 Saurabh Ganeriwal 等于 2003 年提出，该算法采用双向成对同步方法，其同步思想借鉴了传统网络时间同步协议的分层思想，在传感器网络中以自配置方式构建分层架构。TPSN 协议先确定每个节点在网络中的级别， 1本课题得到国家自然科学基金（No.60673061）的资助。 -1-

http://www.paper.edu.cn 然后每个节点与它上一级的某个节点通过消息交换进行时间同步，最后实现所有节点都与根节点 Sink 同步。协议的实现由两个阶段构成：节点的层次发现阶段(Level Discovery Phase) 和同步阶段(Synchronization Phase)。 2.2.1 层次发现阶段此阶段内生成分层的节点拓扑结构，每个节点被赋予一个级别，根节点级别为最高 0 级，第 i 层级别为 i-1，第 i 级的节点应至少能与一个第(i-1)级的节点通信。 2.2.1 同步阶段第二个阶段实现所有树节点的时间同步，第一级节点同步到 Sink，第 i 级节点同步到第 (i-1)级的一个节点，最终所有节点都同步到 Sink，进而实现全网的时间同步。该协议的不足之处是： (1) 消息交换开销太大； (2) 当有新节点加入网络时，需要初始化层次发现阶段，增加了算法的复杂度。 2.3 洪泛广播时间同步协议(Flooding Time Synchronization Protocol, FTSP) FTSP 算法由 Vanderbilt 大学的 Branislav 等人于 2004 年提出，采用单向传输时间消息的方法，并通过消息互换来消除误差并利用线性拟合分析进行时间漂移补偿。在达到较高同步精度的同时减少消息发送次数，其缺点是收敛时间长且协议比较复杂。 3. LTSP时间同步算法 3.1 传感器节点的时间模型传感器节点计时是通过节点的硬件晶体振荡器中断计数实现的，而晶体振荡器的频率并非固定不变，因此传感器节点在某个物理时刻 t 的本地时间可表示为[10]： tC )( i = 1 f 0 t ∫ t 0 tCdtf )( i i )( 0 + t （1）其中， 0f 为节点晶振的标称频率， )(tfi 是晶振在 t 时刻的实际频率， 0t 表示节点开始计时的物理时间， )( 0tCi 表示节点在 0t 时刻的时钟读数。 3.2 LTSP时间同步算法 LTSP 结合了 TPSN 的双向成对同步机制和 FTSP 的单向传递时间消息，通过两次同步操作实现全网的时间同步。首次同步时，Sink 下发全网自身本地时间，普通节点收到该同步分组后修改本地时间为 Sink 时间，并向其他节点转发该同步分组，同时向 Sink 发送反馈分组，以此实现全网粗同步，此时各跳之间的误差主要来自不确定的跳延迟，Sink 通过双向消息交换来计算平均每跳延迟。第二次同步时，Sink 根据各普通节点的反馈分组计算出的延迟作为调整量包含在同步分组内，普通节点收到该同步分组后取出调整量对自身时间做调整，进而可以实现全网的时间同步。 3.2.1 首次时间同步 Sink 可以通过泛洪、消息捎带或者其他分发协议如采用 Trickle 算法的 DIP 协议[11]把自身的本地时间下发到传感器网络中。普通节点在收到该时间同步调整分组后首先读取分组 -2-

http://www.paper.edu.cn 序列号以判断过去是否已经接收，若是新分组则调整时间相位并继续下发本次下行时间同步调整分组，逐层深入直至覆盖全网，否则不做任何处理直接转发；同时，普通节点生成一个随机数，若该随机数小于事先设定的一个阈值 K 时，构造上行反馈分组并按照下行路径的反方向向上一跳节点发送该上行反馈分组，节点在收到该上行反馈分组后继续向更上行普通节点转发上行反馈分组，逐层往上直至汇聚节点，若该随机数大于阈值 K，则不进行反馈操作，减少网络开销；汇聚节点根据其收到的上行反馈分组计算逐跳调整量，并开始第二轮次的时间调整。同步分组的逻辑顺序如图 1 所示，其中 H1 表示 Sink 的下一跳普通节点，H2 为 H1 的下一跳节点。在 T1 时刻，Sink 下发同步分组，H1 节点在 T2 时刻收到该分组进行相应处理后并于 T3 时刻向 H2 下发同步分组，同样地，H2 在 T4 时刻收到来自 H1 的同步分组进行处理后于 T5 时刻发送上行反馈分组，H1 在 T6 时刻收到后于 T7 时刻向 Sink 转发该上行反馈分组，Sink 节点在 T8 时刻收到该分组。图 1 双向消息交换计算跳延迟 Fig1 Calculating hop delay through bidirectional message exchanges 从上图可知，逐跳延时调整量 d 可以表示为： TT ( 2 − ) 1 + TT ( 4 − d = TT ) ( + 3 6 − N 2 × ) 5 + TT ( 8 − ) 7 （2）对分子进行变形，即： TT ( 5 − N TT ( 3 − ) 2 2 − × TT ( 8 − ) 1 − d = ) 4 − TT ( 7 − ) 6 （3）其中，N 为同步分组所经历的跳数；由公式(3)可以得出，各个普通节点只需计算出同步分组到达时间以及自身转发时间之间的间隔，再汇总到 Sink 节点，即可算出逐跳调整量 d。 3.2.2 再次时间同步 Sink 节点下发第二轮同步分组时，分组内包含在 Sink 端计算出的逐跳调整量 d，收到分组的普通网络节点将依据分组中携带的时间信息和调整量 d 对自身的时间进行调整，同时修改同步分组中携带的时间信息并转发，供下一跳节点进行调整。 -3-

http://www.paper.edu.cn 3.3 提高时间同步精度的关键技术 3.3.1 延时消除为了详细分析时间同步误差，从发送节点到接收节点之间的关键路径上，消息传输延时可以分成五个部分：发送处理时间、信道空闲检测时间、传输时间、传播时间和接收处理时间[12]。其中传播时间可以忽略不计，发送和接收处理时间会因操作系统所引入的延迟而存在变化，波动较大的是不确定的信道空闲检测时间，随网络应用环境的不同而不同。基于此，在具备硬件支持的条件下，通过在 MAC 层进行消息发送和接收的时候记录时间信标，可以直接消除发送延时、信道检测延时和接收延时的影响；另外，可以根据数据传输速率和待传输数据位数目对物理层传输延迟进行估计并进行补偿，假如待传输数据位个数为 n，发送一个比特位所需时间为 t，则可估算出应补偿的传输时间为 nt。 3.3.2 漂移矫正由于制造工艺等因素的影响，节点晶振的实际频率与标称频率之间会有微小的差异，有如下关系： ρ≤−1 （4） fi 0f 如公式(1)所定义， 0f 为节点的标称时钟频率， if 为节点的实际频率，ρ称为绝对频差上限，通常ρ的值在 1-100ppm 之间，一般来说，大部分节点的绝对频差上限在 40-50ppm 之间，也就是说，节点时钟每秒最多时会产生 40-50us 的时间漂移。统计表明，各节点时钟漂移的概率分布符合均值为 0 的正态分布，该现象将会使得节点的本地时钟相对全局时间之间存在一个时间偏差，并且随着网络的运行，该时间偏差很可能被不断地放大，导致各节点间的时间同步精度不断降低。所以很有必要对节点进行漂移矫正。FTSP 协议中采用线性回归的方法拟合回归曲线，在消耗硬件资源的同时增加了协议的复杂度。这里我们通过一个简单的方法来计算节点相对 Sink 的漂移系数：假设网络处于稳定的工作环境，并以 Sink 节点为时钟频率基准，在 T0 和 T1 时刻 Sink 的时间分别为 0,ST 和 1,ST ，节点 N 的时间分别为 0,NT 和 1,NT ，可计算出该节点的漂移系数为： S kew = T N T S 1, 1, − − T T N 0, S 0, (5) 之后，节点在收到第二轮同步分组可对自身进行带漂移系数的调整，延长网络保持同步时间。 4. 算法的程序实现基于 TinyOS 2.0 操作系统，我们独立编写了 Sink 与普通节点的 LTSP 同步算法的程序代码，烧写到 30 个采用 CC2420 无线通信芯片的 telosb 传感器网络节点上，并进行了小规模的无线传感器网络的时间同步相关测试。 4.1 Sink节点程序伪代码 Sink 节点主要负责处理转发应用程序的时间同步命令、接收反馈数据分组、计算每条延迟，以及下发逐跳调整量： -4-

http://www.paper.edu.cn //接收到用户发送的时间同步命令； command void RecCMD.received(); //更新命令序列号； ucSerialNum++; //构造下行分组并发送； void Packet_Trans_Down(); … //接收到普通节点反馈的上行分组； event message_t* UpReceive.receive () //计算每跳调整量； CountHopDelay(); 4.2 普通节点程序伪代码普通节点除需要进行自身时间的调整外，还负责转发下行数据分组和上行反馈分组： //计算节点漂移 CountSkew(); //判断是否需要向上反馈； if ( ucFeedBackNum > usRandomNum) //收到下行同步分组 event message_t* DownReceive.receive(); //命令序列号判断； if (ucSerialNum 不是最新) { return bufPtr; } else { Packet_Trans_Up(); //接收到普通节点反馈的上行分组； event message_t* UpReceive.receive () CountHopDelay(); } //修改下行分组并转发； void Packet_Trans_Down(); 5．实验测试和性能对比 4.3 时间同步的精度对比在 telosb 平台上对各协议分别进行实现并做了进一步的对比，各算法的同步精度如下图：同步精度对比 30 25 20 15 10 5 0 ) s n ( ：位单度精步同间时 FTSP LTSP RBS TPSN 图 2 几种算法的同步精度 Fig.2 The synchronization accuracy between several algorithms -5-

可以看出，LTSP 协议的同步精度大致与 TPSN 相当，这基本满足我们的协议设计目标。 4.4 其他性能参数比较 http://www.paper.edu.cn 表 1 其他性能比较 Tab.1 Others performance comparisons 收敛时间拓展性鲁棒性能耗 RBS 较短较差较差较大 TPSN 较长差差一般 LTSP 较短好一般小 FTSP 较长一般一般小在其他方面，LTSP 具有较短的收敛时间，良好的扩展性，且能耗较小，这对于能量受限的传感器节点而言是很有意义的。 5. 总结本文介绍了几种常见的传感器网络时间同步算法，并基于 FTSP 和 TPSN 算法的基础上提出一种改进的时间同步算法，相对其他算法而言，该算法实现简单，无需过多计算资源，并且进行了精简的延迟消除和时钟漂移矫正，实验结果对比显示：该算法开销较低，且性能满足预期的同步精度目标。 -6-

http://www.paper.edu.cn 参考文献 [1] 孙利民, 刘俊涛, 何庆伟.无线传感器网络的通信协议. 中国计算机学会通讯[J]. 2006, 2(5):43-51. [2] 任丰原, 黄海宁, 林闯. 无线传感器网络[J]. 软件学报, 2003, 14(2): 1148-1157. [3] Elson J, Griod L, Esrein D. Fine-grained network time synchronization using reference broadcasts. In Proc 5th Symp Operating Systems Design and Implementation (OSDI2002). December2002. [4] Ganeriwal S, Kumar R, Srivastava MB. Timing-sync protocol for sensor networks. In: Proc 1st Int'1 Conf on Embedded Networked Sensor Systems(SenSys 2003). November, 2003.pp138~149. [5] Maroti M, Simon G, Ledecze A, etc. Shooter Localization in Urban Terrain. IEEE Computer 37, No.8.August, 2004.pp60-61. IR-TR-2003-64,2003. [6] Ping S.Delay measurement time synchronization for wireless sensor networks. Intel Researeh Center: [7] Sichitiu M, Veerarittiphan C. Simple accurate time synchronization for wireless sensor networks. Proc IEEE Wireless Communications and Networking Conference(WCNC’2003). March 2003. [8] Y Hong, A Scaglione. A scalable synchronization protocol for large scale sensor networks and its applications [J]. IEEE Journal of Selected Areas in Communications, 2005, 23(5):1085-1099 [9] A Hu, S D Servetto. On the scalability of cooperative time synchronization in pulse-connected networks [J]. IEEE Trans on Information Theory, 2006, 52(6):2725-2748 [10] Romer K, Blum P, Meier L. Time Synchronization and Calibration in Wireless Sensor Networks. Wireless [11] Jonathan W.Hui, David Culler. The Dynamic Behavior of a Data Dissemination Protocol for Network [12] Maroti M, Kusy B, Simon G, et al. Flooding time synchronization in wireless sensor networks. ACM Sensor Networks, Ivan Stojmenovic, ed., 2005. Programming at Scale. SenSys'04, USA. SenSys’04. November, 2004, Baltinore, Maryland. A Time Synchronization Approach Based on Bidirectional Message Exchanges for Wireless Sensor Networks School of Computer and Communications, Hunan University, Changsha (410082) Li Shunhui, Yang Kehua Abstract As a fundamental service for both design and application of sensor networks, time synchronization has attracted wide attention. Because of the cost, power and size constraints of the individual nodes, time synchronization always encounter some new challenges. This paper present a novel and low-cost time synchronization approach named LTSP (LTSP: Low-cost Time Synchronization Protocol), which achieves time synchronization through bidirectional messages exchange operations. A pair of synchronization phases was performed in LTSP. The experiment result shows that: the synchronization accuracy of the approach based on low-cost design principles could meet our expectation well. Keywords: Sensor Networks; Time Synchronization; Time Stamping 作者简介：李顺辉，男，硕士研究生，主要研究方向为嵌入式计算、传感器网络。杨科华，男，博士，副教授，主要研究方向为嵌入式数据库。 -7-

分享到：

赞收藏

资料库

无线传感网络时间同步.pdf

相关推荐

网络技术

热门标签

最新资料