基于RBS的无线传感器网络时间同步算法.doc

第6期李文锋等：基于RBS的无线传感器网络时间同步算法87基于RBS的无线传感器网络时间同步算法李文锋1，王汝传1,2，孙力娟1(1. 南京邮电大学 计算机科学与技术系，江苏 南京 210003；2. 南京大学 计算机软件新技术国家重点实验室，江苏 南京 210093)摘 要：提出了一种改进的时间同步算法IRBS(improved references broadcast synchronization)，它是在RBS算法的基础上，根据接收节点的时间值，估算出实际时间值，并利用估计时间来实现时间的同步。仿真结果表明，IRBS算法能够缩小时间误差，有效提高时间同步的精度。关键词：无线传感器网络；时间同步；误差估计；改进的参考广播同步中图分类号：TP391 文献标识码：B 文章编号：1000-436X(2008)06-0082-05Proved wireless sensor networks time synchronization algorithm based on RBSLI Wen-feng 1, WANG Ru-chuan1, 2, SUN Li-juan1(1. Department of Computer Science and Technology, Nanjing University of Posts and Telecommunications, Nanjing 210003,China; 2. State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210093,China)Abstract: IRBS algorithm was proposed on RBS. According to receiver node time, IRBS estimate its real time. During its calculation of two nodes time difference, it realizea time synchronization by the estimating time. Simulation result shows IRBS algorithm can reduce time error and improve time synchronization precision.Key words: wireless sensor network; time synchronization; error estimation; improved reference broadcast synchronization1 引言收稿日期：2007-06-19；修回日期：2008-04-22基金项目：国家自然科学基金资助项目（60573141，60773041）；国家高资助技术研究发展计划（“863”计划）基金资助项目（2006AA01Z201，2006AA01Z219，2007AA01Z404，2007AA01Z478）；江苏省高技术研究计划基金资助项目（BG2006001）；2006江苏省软件专项；南京市高科技基金资助项目（2007软资106，2007软资127）；现代通信国家重点实验室基金资助项目（9140C1105040805）；江苏省计算机信息处理技术重点实验室基金资助项目（kjs06006）Foundation Items: The National Natural Science Foundation of China (60573141, 60773041); The National High Technology Research and Development Program of China (863 Program)(2006AA01Z201, 2006AA01Z219, 2007AA01Z404, 2007AA01Z478); The Provincial Jiangsu High Technology Research Program(BG2006001); The Special Fund for Software Technology of Jiangsu Province; The High Technology Research Program of Nanjing (2007RZ106, 2007RZ127); The National Key Laboratory Foundation for Modern Communications (9140C1105040805); The Key Laboratory Foundation of Information Technology Processing of Jiangsu Province (kjs06006)无线传感器网络是由大量的微传感器节点采用无线自组织方式构成的网络1，应用于国防、环保、交通、医疗及制造业等领域2。时间同步是无线传感器网络的一项重要支撑技术，影响传感器网络自身协议的运行及应用，如标记数据采集时间、协同休眠、定位、数据融合等都要求网络中节点的时钟保持同步。J.Elson和K.Romer在2002年8月的HotNets-I的国际会议上首次提出和阐述了传感器网络中时间同步机制的研究成果，在传感器网络研究领域引起了关注。从同步算法来看，主要包括3类：一是基于发送者的同步算法，如DMTS3、TFSP4，这类算法的优点是灵活、轻量和能量高效，能够实现全部网络节点的同步，但是实现复杂、同步精度不高；二是基于发送者接收者交互的同步算法，如TPSN5、Tiny-sync和Mini-sync6，这类算法需要较大的带宽及存储空间，且当真实时间发生变化时，时间同步会出现较大的偏差；三是基于接收者接收者的时间同步算法，如RBS7和Adaptive RBS8。RBS算法是经典的时间同步算法，实现不复杂，也不需要耗费大的存储空间，能够满足大多数时间同步精度要求不太高的需求。虽然adaptive RBS算法使用概率方法对RBS的广播数量及广播频率方面进行了改善，但是该算法并没有对RBS算法的参数估计的精度进行分析。本文提出的改进参考广播同步算法，即IRBS(improved reference broadcast synchronization)算法，对每个接收节点的时间值做进一步的估计，以达到最接近原始时间的值，然后，根据每个节点在接收不同数据时的时钟误差，得出系统的时钟误差。仿真表明，该改进算法能够有效地提高时间同步的精度。2 IRBS算法IRBS算法的基本原理是：以一个节点作为发送节点，多个节点作为接收节点，将不同的接收节点收到同一消息的时间差值用于标记节点间的接收时间误差，然后根据不同的接收时间，利用最小平方线性回归方法，分析出同一节点的系统时钟误差。2.1 RBS算法误差分析RBS算法的时间估计分为节点接收时间估计和系统时钟误差估计2个部分。节点间接收时间误差的估计是利用统计多个接收消息包的时间的差，再取平均值，得到2个节点收到不同消息包时它们之间的接收时间误差可用式（1）表示，其中n表示第n号节点，而m表示第m个消息。而节点的系统时钟误差，可以用最小平方线性回归方法求出，如式(2)所示。(1)(2)通过上述分析，起决定作用的是每个节点接收到第k个消息的时间。现假设节点1正确接收到第k个消息的时间为，而是在某种误差产生后节点1收到第k个消息的时间，且和总是以常量相差；同时，假设节点2接收到第k个消息的时间为，而是在某种误差产生后节点2收到第k个消息的时间，同理和总是以常量相差。根据式(1)，可以计算出有误差和无误差2种情况下的2节点的接收时间误差值，见式(3)。(3)由式(3)可以得出2个节点的接收时间误差取决于接收到第k个消息时的时间值的准确性。因此，必须减少的误差，换言之，如果能够取得的最相近的值，则也会变得很小。因此，本文试图从获得与最相近的值的角度来提高时钟同步精度。2.2 IRBS算法描述为了更好地描述IRBS算法，这里先做如下假设：1) 为经典RBS算法计算出来的当前节点i的时钟时间；2) 为通过贝叶斯方法估算的实际时间t的值；3) 为上一节点通过贝叶斯方法估计出来的估算值，服从方差为正态分布；4) 观察本节点时钟的随机误差服从。根据文献9，可以得出如下关系式(4)和式(5) (4)(5)IRBS算法描述如下：1) 令第一个发送消息节点的时间及时钟决定因子；2) 上一跳节点发送其接收第k个消息包时的估计时间和估计误差的标准方差到下一跳节点；3) 下一跳节点利用接收消息时间记录计算出接收时间,和,，再利用式（4）和式（5）计算出、和、 ；4) 2个节点之间交换接收时间，并利用式（1）、式（2）计算出接收时间误差及时钟误差；5) 依次按以上步骤执行，直到到达最后一跳节点。3 IRBS算法参数分析影响无线传感器网络时间同步的因素很多，包括算法运行所耗费的时间、空间、能量以及节点接收时间误差、系统时钟误差等。针对本文提出的方法，这里仅对关系到系统时间同步的接收时间误差、系统时钟误差、估计误差的标准方差的计算、平均系统时钟误差分析及误差概率分析几个参数进行分析。3.1 接收时间误差和系统时钟误差在IRBS算法中，上一跳节点将估计时间传输到下一跳节点，下一跳节点间通过交换他们的估计时间确定2个节点时间的误差平均值。即利用，对于，且根据式（6）及式（7）计算得到时间误差及。(6)(7)其中，。3.2 估计误差的标准方差的计算由于是未知的参数，所以需要利用样本去估计，为了估计，先引入下述残差平方和Qe，记,则Qe可以表示为式(8)(8)另外，记,则。由于，于是，即的无偏估计公式表示为式（9）(9)3.3 平均系统时钟误差分析由于每个节点的系统时钟误差di可以算出，且，则对于接收了m个信息包的无线传感器网络，整个网络的平均系统时钟误差可通过式（10）计算得出。(10)也就是说，是关于m个随机变量的算术平均值，其每个变量都服从。因此，根据正态分布总体与样本的性质，可以知道。3.4 误差概率分析误差概率可以用来衡量整个网络的时间同步效率。一个给定的无线传感器网络，如果给定平均系统时钟误差，则可以计算出误差概率。由式(10)可以得到平均时钟误差，假定期望的系统误差概率为，错误最大的误差数为，则全网的误差密度函数可由式（11）表示，其误差概率可由式(12)计算出来。(11)(12)4 仿真结果分析在无线传感器网络仿真工具TOSSIM上，选择了200个节点进行仿真(如图1所示)。仿真条件如下：仿真时间800s，发射距离为80m，测试28组数据。对RBS和IRBS两种算法的误差进行分析，其中RBS算法误差较大，误差范围在014 000之间，而用改进后的算法IRBS的误差范围相对较小，可以控制在02 000之间。虽然在波动性能上还没有达到完全平衡，但在稳定性方面优于经典RBS算法。仿真结果还表明，实验数据量越大，则经典RBS算法误差就越大。当测试次数超过17次后，经典RBS算法的结果波动范围非常大，而改进后的IRBS算法仍然显得相对的稳定，结果如图2所示。图1 节点拓扑图图2 2种算法误差结果本文还针对多跳网络中的节点个数与节点的误差关系进行了仿真。仿真结果如图3所示。在该图中，当节点个数小于60时，节点的误差相对稳定；而当节点个数在60和90之间时，节点的误差不稳定；而当节点个数大于90之后，同步时间误差达到一个相对稳定值，误差随节点个数增加的影响不大。图3 改进后的IRBS算法中节点数与误差的关系同时，本文还对系统误差性能进行了分析。根据系统期望的最大允许误差值，得出在这个误差内所有误差的分布情况。这里根据56组数据得出的=24.31。当最大允许误差期望=10和20时的分布情况，分别如图4和图5中阴影部分所示。从图4和图5可以看出，误差主要集中在0附近。而随着误差范围的扩大，误差的数据呈现下降趋势，即出现误差越大的数据越少。图4 =10时的误差分布情况图5 =20时的误差分布情况5 结束语在RBS算法的基础上，对接收时间进行估计，使整个网络的平均误差变小，达到无线传感器网络时间同步的精度要求；同时，依据几个影响时间同步的参数指标，对改进后的IRBS算法的接收时间误差、系统时钟误差、估计误差的标准方差的计算、平均系统时钟误差及误差概率进行了分析，并在仿真平台上进行实验，仿真结果表明，改进后的IRBS算法将误差控制在02 000之间，有效地缩小误差。在后续的研究中，将在IRBS算法基础上研究分析误差产生的原因，进一步缩小时间同步误差，提出适合大规模无线传感器网络应用的IRBS算法。参考文献：1STANKOVIO J A, ABDELZAHER T F, CHEN Y L, et al. Real-time communication and coordination in embedded sensor networksA.Proceedings of the IEEEC. 2003.1002-1022.2HILL J L, CULLER D E. Mica: a wireless platform for deeply embedded networksJ. IEEE Micro,2002,22(6):12-24.3PING S. Delay Measurement Time Synchronization for Wireless Sensor NetworksR. Intel Research Cente, IR-TR-2003-64, 2003.4MAROTIM, KUSYB, SMON G, et al. The flooding time synchronization protocolA. Proceedings of the 2nd Intermational Conference on Embedded Networked Sensor Systems(Sensys04)C. 2004.39-49.5GANERIWAL S, KUMAR R, SRIVASTAVA M B. Timing-sync protocol for sensor networksA. Proceedings of the 1st International Conference on Embedded Networked Sensor Systems(IPSN04)C. 2003.138-149.6SICHITIU M L, VEERARITTIPHAN C C. Simple: accurate time synchronization for wireless sensor networksA. Proceedings of the IEEE Wireless Communications and Networking Conference(WCNC 2003)C. 2003.1266-1273.7ELSON J, GIROD L, ESTRIN D. Fine-grained network time s