无线传感网络中时间同步技术综述.docx

无线传感网络中时间同步技术综述Sami M. Lasassmeh and James M. ConradElectrical and Computer Engineering Department, University of North Carolina at Charlotte, NC, USA摘要：无线传感网络是由分散在全球各区域的小设备组成，这些小设备都具有感知，计算和通信功能，当网络中需要partial time sy和full time sy时，无线传感网络就会被应用。时间同步技术的目的在于在必要的时候将全网的所有节点与当地时间整合一致，因为无线传感网络在能源，计算容量，存储量和带宽方面很有限，所以传统的算法如NTP和GPS在同步全网的时候就显得不实用。这篇文章将介绍无线传感网络中时间同步存在的问题以及在这一领域中提出的一些基本算法。1 引言无线网络由空间上离散分布在不同地域的自动装置组成，这些装置通常用来监控温度，声音，振动，压力，运动和污染等数据2，10。这种装置通常都有感应部件，无线通信收发器，计算回路，数据网以及电源（通常是电池）4。传感器网络是一种特殊的ad-hoc网络，在传感器网络中，无线设备（通常指的是网络中的节点）可以在没有基础的网络构造的情况下自发地一起工作形成网络12。节点可以收发数据，或者作为数据传输的路径。网络节点通常是静态的，并且是资源受限的，它们把数据搜集起来并且形成一个叫做sink的中心单元，用于后续运算。整个传感器网络的运行时间（常常通过耗尽电量的无线节点的百分比来定义，而不是指的一个设备的运行时间）是评估网络性能的主要参数之一。传感器必须要设计的能够经得住恶劣的环境和地质条件。通常配备多余的后备设备或者传感器以应对设备无法工作的情形（如硬件故障，电池电量耗尽等）。时间同步的目的是在网络中建立一个时标，它在很多应用中都是必要的技术。介质访问控制技术，如TDMA就需要时间同步技术来实现精确的没有冲突的介质访问的规划。另外，无线传感网络的电源有限，因此为降低整个网络的能耗就要用到节电技术。为了使节点能在准确的时间开关收发设备，就要用到网络节点之间的精确的时间调整技术。在很多应用中还引入了数据融合。在不同节点搜集的数据将被会聚然后发送到sink节点，以便做出决断。这些节点相互之间合作协调来完成这一任务。项目表探测这样的应用技术，需要精确的时间整合来对事件进行准确的估计。在有线网络中已经得到应用的传统的时间同步技术并不适用于无线网络。在互联网中得到广泛应用的NTP技术8的开始过程过于复杂，并且能耗较大。另一方面，因为安装在网络节点上的设备过于庞大和接近所以GPS技术也不适，而且，因为传感器通常被安装在恶劣的环境下，GPS信号还常常无法到达。下面的论述将以如下方式展开：第二部分我们将论述计算机时钟是如何工作的，并且解释时间同步的资源和需求，第三部分详细介绍时间同步的方法，TTS,RBS,TPSN,Tiny-Sync,Mini-Sync,以及基于树时间同步的算法。2 同步问题A.计算机时钟计算机时钟回路由振荡器和计时器组成，计时器将基于为振荡器的角频率来增加代表当地时钟的网络节点的C（t）的数值。在理想情况下，角频率是恒定的。因此时钟的变化率A等于1.计算机时钟随诸如温度，振动，压力和角频率的变化而摆动节点i的本地时钟将随实时数据t作如下变化： Cit=ait+bi (1)这里a表示时钟的变化绿，b是关于节点i的时钟的设定。变化率表示了时钟频率的变化比率，设定值表示了数值与实时数据的差异。从方程（1）我们比较在一个网络中的两个节点，可以向文献11中称它们为节点1和节点2。 C1t=a12.C2t+b12 (2)我们称a为节点1时钟和节点2时钟的相对漂移，b为节点1时钟和节点2时钟的相对设定。如果两个始终能够完全同步，那么它们的相对漂移就为1，表示这两个时钟拥有相同的变化率。它们的相对设定值为0，表示他们在这一时刻具有相同的数值12。基于前面的等式，网络节点的时钟变化率和始终设定可以用来调整当地时间，很多方案都设计成不断重复调整节点设定值，或者是调整节点设定值和变化率到一个共同的时标。B.同步错误的原因信息交换在很多时间同步算法中都得到了应用，如果一个节点发送了一个带有时间戳的信息包，不确定的像访问或广播时间这样的延时接收节点很难与发送节点准确地同步。总体上，产生同步错误的因素主要包括:精确度：同步技术的准确性高度依赖于设备鲁棒性：网络节点可能会被破坏或者退出运行，因为它们运行的环境很恶劣。任何同步技术的设计都应该适应这种变化，并且能在各种情形下运行。可扩展性：很多实际应用中，可能会有成千上万的传感器，任何同步技术都应该保证无论多少节点，都能很好地运行。寿命：假设同步可能是瞬间发生的，与具体应用有关，比如确定的某事件发生时，或者一旦网络开始运行就同步。电源效率：网络节点的能源有限，包括同步技术在内的所有的网络协议都要考虑到这一点。费用：由于技术的进步，网络节点变得小而便宜，任何同步算法都不能增加费用或者增大网络规模。范围：时间同步算法为所有节点提供了一个共同的时间，但这种方法将耗费更多的能源和时间，另一种方法是可以只为在空间上靠得近的节点提供共同的时间。延时：很多设备，像漏气监测，需要即时反应。这样的设备，同步所需的时间要尽量低。3 无线传感网络的同步方法同步任务的目的在于调整网络中的所有节点的时间与参考值一致，最严格有力的同步方法要求所有节点在所有时间同步，而其它要求宽松一点的方法则要求某些节点一段时间同步。A.传统的时间同步（TTS）传统的网络节点时间同步的方案（如网络时间协议）是基于收发信息而实现的，最简单的形式就是发送方向接收方发送带有实时当地时间的信息，然后接收方根据收到的信息调整自己的时钟。在相对于本地时间所要求的精度下收发信息的延时可以忽略不及的情况下，这种方案可以很好地实现同步，如果收发的延时很长，发送方就要求接收方立即回复，节点就可以计算信息在一个来回所需的时间，并且将这一时间应用在与其它节点同步的时候。B.广播参考同步(RBS)在文献1中，介绍了接收器与接收器而非接收器与发送器的同步，在这种情况下，介绍了RBS。节点通过广播方式发送信标，其他节点应用这些到达的信标作为参考来重新设定它们的时间。这一算法主要是去改变不确定的传送来的时间。这一方案的主要误差来源在于不确定的接受和发送的次数，如果假设射频距离很短，并且是表示向所有的节点同时广播，那么发送误差可以忽略。所以这一误差的唯一来源就在与接收时间。典型的通信方案是一个节点向相邻节点发送时标，接收方通过自己的时间与时标差异的交换寻找相关的时间设定，然后相互之间进行时间同步。发送的时标越多，同步就越精确。用这项技术可以达到微秒的精确度，在流行的平台Berkley上可以达到11微秒的精确度。而这种算法也被应用在Linux上来通过802.11协议通信，而精确度也能达到6.296.45微秒。 C.无线传感网络的时间同步协议（TPSN）TPSN在文献6中被提出。这种同步技术有两个阶段，在发现阶段（第一阶段），每个节点都会被设定一个层次编号。只有一个节点被编号为0，称为根节点。在第二阶段，层次编号为n的节点依次与层次编号为n-1的节点同步，这样下去，最终整个网络将达到同步。节点发现阶段：这一阶段的第一步是选根节点，网络中的节点可以定期地选出一个节点，然后将层次编号为0.这一节点可以与外部的时间参考（如GPS）相连。然后向其它节点发送发现数据包，接收到数据包的节点将自己层次编号为1，然后再向剩下的节点发送包括它们层次编号的数据包，直到所有节点都完成层次编号。同步阶段：根节点通过再一次发送时间同步数据包开始时间同步阶段。层次编号为n的节点A通过双向数据交换与层次编号为n-1的节点B完成同步。节点A发送一个带有当地时间T1的数据包，节点B在时间T2收到这一数据包，T2可以通过如下方式计算：T2=T1+Td+ (3)上式Td是广播延时，是节点与假设恒定情况下信息交换的相关时钟漂移。节点B在一个随机时刻T3向节点A发送一个包含T1,T2,T3和它的层次编号的确认数据包。节点A在时间T4收到数据包的时候，可以通过文献6的方法计算计算和Td，然后与节点B同步。=T2-T1-T4-T32;Td=T2-T1+(T4-T3)2(4)这种在层次编号n的节点到层次编号n-1的节点之间的同步方法在每一个节点上持续进行，整个网络就会实现同步。将TPSN和RBS作比较，这两种算法都应用在Mica平台。数据显示在相同的实验设定下RBS达到了29.13微秒的精度，而TPSN达到了16.9微秒的精度。这些结果显示，利用MAC层面上的时间标记（time stamp）传统的发送方-接收方算法可以克服发送时间的误差，并且精确度比接收方-接收方算法高。再电能方面，TPSN比RBS消耗得多。在发现阶段用来选根节点的数据包就算是一种消耗，这种消耗有损于网络的寿命，特别是当根节点总是失效时，整个同步方法总是要被重复。D.小同步和迷你同步在文献11中，作者提出了两种用于一对无线节点的同步的算法，然后这些算法被扩展到所有网络节点的情形。传统的双向信息被用来收集数据点，这些数据点用来使两个节点的相关漂移和相关设定更加紧密。用两个节点创造数据点,：1和2，节点1向节点2发送带有时间标记t的探索信息，节点2再马上或者在某一时刻（标记为t），在这一信息上做上记号t，然后传回节点1以作确认。图三就描述了上述顺序。基于上述等式2并且考虑到信息发送的顺序，可以得到下面的关系：t0ta12tbt+b12 (6)算法开始收集数据点，用线性程序估计a和b，然后使节点相互同步。当网络中的普通数据和确认数据包能够用来收集数据点的时候，这样可以减小消耗，估计a和b所需要的大存储量以及大的计算量。E基于树的同步算法很多无线网络传感器都需要微秒级的精度，有的需要毫秒级精度。文献7提出的算法，在假定需要达到的精度，以及基于这一给定数据得出的复杂程度和计算时间已知的情况下，解决这一现实问题。第一个算法包括两个阶段，在第一阶段线形成生成树协议，然后在第二阶段，在生成树协议n-1边一个发送方-接收方同步将会完成。在这种集中算法中，所有的节点的时间将会同步为一个中心点，称作sink或者根节点。根节点的作用是在必要的时候重新开始同步。同样，它也将网络所有的节点都同步为一个时间。为了能够进行那些运算和做出其它的决策，根据生成树协议的深度不断调整更新根节点是很有必要的。在第二种算法中，节点根据与参考节点的远近，时钟漂移，以及所需的精度来决定什么时候同步。因此任何节点都能再有参考节点的时候开始同步阶段，而通向参考节点路径上的所有节点必须先被同步。因为并非所有节点都需要在所有时间被同步，所以这种算法允许节点自己决定是否要同步，这样就减少了消耗。同步要求的整合的应用使得算法更有效，在节点发出同步请求时，会先看临近节点是否还有没有经过处理的请求，如果有的话，就把自己的请求整合在上面，这样就可以保证同步只有一次。在文献11中，提出了将整个网络分成子树的方法。在每一个子树上，子节点向它们的母节点或者根节点同步，然后所有的母节点同步。4 结论我们发现在精确度上TPSN和RBS做得很好。它们可以将精确度控制在微秒级。因为收发数据包是整个同步过程中耗能最大的过程，所以同步一对节点所需要的数据包数常被用来评估节能效率。RBS算法是一个接收方-接收方算法，在同步两个节点时会发送4个数据包，接收3数据包。在TPSN中，在同步两个节点的时候会发送2个数据包，接收两个数据包。尽管听上去TPSN更加节能，但是事实上，TPSN需要额外发送数据包来进行层次的编号，并且在RBS中一次脉冲不止同步一个接收点。基于树的同步算法更加灵活，并且根据给定的精度和复杂度耗能的高低可能不确定。根节点在这些算法中起到了很大的作用，并且还可以连上外部节点以获得实时时间。参考文献1 J. Elson, L. Girod, and D. Estrin, “Fine-Grained Time Synchronization using Reference Broadcasts, Proceedings of the Fifth Symposium on Operating Systems Design and Implementation (OSDI 2002), Boston, MA, December 2002. 2 T. Haenselmann. “Sensornetworks,” Wireless Sensor Network textbook, 2006. 3 L. He and G.S. Kuo, “A Novel Time Synchronization Scheme in Wireless Sensor Networks,” Vehicular Technology Conference, 2006. VTC 2006-Spring. IEEE 63rd Volume 2, 7-10 May 2006 pps. 568 572. 4 J. Hill and D. Culler, “A Wireless Embedded Sensor Architecture for System-Level Optimization, Technical Report, U.C. Berkeley, 2001. 5B.Hofmann-Wellenhof,H. Lichtenegger, and J. Collins. “Global Positioning System: Theory and Practice,” Text Book, Fifth edition, 2001. 6S. Ganeriwal, R. Kumar, and M. Srivastava, “Timing Sync Protocol for Sensor Networks, ACM SenSys, Los Angeles, November 2003. 7 J.V. Greunen, and J. Rabaey, “Lightweight Time Synchronization for Sensor Networks, Proceedings of the 2nd ACM International Conference on Wireless Sensor Networks and Applications (WSNA), San Diego, CA, September 2003. 8 D. Mills, “Network Time Protocol (Version 3) Specification, Implementation and Analysis,” Technical