针对无线传感网络簇群的一种全新容错时钟同步方案

1、针对无线传感网络簇群的一种全新容错时钟同步方案（译文）Kun Sun, Peng Ning, Member, IEEE, and Cliff Wang, Member, IEEE摘要：目前无线传感网络由于其广泛的应用价值而倍受关注，如目标追踪、环境监测、危险区域的科学探测等。传感节点通常需要组成一个个簇群来保证本地的时钟同步，进而协作实现一些重要的功能，如基于时间片的MAC协议、基于睡眠模式的节能协议等。但是，所有的针对传感网络的时钟同步技术都是假设应用在良性的环境，一旦遇到有敌方恶意攻击的恶性环境中，这些时钟同步技术都不再适用。为了解决这个问题，容错时钟同步技术是潜在的解决方法。然而在许多情

2、况下，现存的一些容错时钟同步技术都显得太耗资源并遇到信息冲突问题。针对每个簇群中所有节点通过广播通信的传感网络，本文提出了一种全新的容错时钟同步方案。如果不良节点不超过簇群的三分之一，本文提出的方案可以确保簇群中任意两节点间时钟差异的在有效的上限范围之内。不像传统的容错时钟同步技术，本方案不会造成同步信息间的冲突，也不需要大量的数字特征。关键词：时钟同步，无线传感网络，容错Fault-Tolerant Cluster-Wise Clock Synchronization for Wireless Sensor NetworksKunSun, PengNing, Member, IEEE, an

3、d CliffWang, Member, IEEEAbstract: Wireless sensor networks have received a lot of attention recently due to their wide applications, such as target tracking, environment monitoring, and scientific exploration in dangerous environments. It is usually necessary to have a cluster of sensor nodes share

4、 a common view of a local clock time, so that all these nodes can coordinate in some important applications, such as time slotted MAC protocols, power-saving protocols with sleep/listen modes, etc. However, all the clock synchronization techniques proposed for sensor networks assume benign environme

5、nts; they cannot survive malicious attacks in hostile environments. Fault-tolerant clock synchronization techniques are potential candidates to address this problem. However, existing approaches are all resource consuming and suffer from message collisions in most of cases. This paper presents a nov

6、el fault-tolerant clock synchronization scheme for clusters of nodes in sensor networks, where the nodes in each cluster can communicate through broadcast. The proposed scheme guarantees an upper bound of clock difference between any nonfaulty nodes in a cluster, provided that the malicious nodes ar

7、e no more than one third of the cluster. Unlike the traditional fault-tolerant clock synchronization approaches, the proposed technique does not introduce collisions between synchronization messages, nor does it require costly digital signatures.Index Terms: Clock synchronization, wireless sensor ne

8、tworks, fault tolerance.1 引言目前无线传感网络由于其广泛的应用价值而倍受关注，例如目标追踪、环境监测、危险区域的科学探测等。传感节点的资源通常受到限制并且它们之间通过无线链接进行通信。一个准确的同步时钟对于许多传感网络来讲十分重要，尤其是因为传感网络的协作特性。例如，在目标追踪的应用中，传感节点需要知道本地和目标发送的时间，以此来正确决策出目标移动的方向和速度（如3，39）。传感节点通常包含廉价的晶振，这些晶振通常存在每秒十微秒的时钟漂移率33，而大于每天一秒的时钟漂移对于大多数传感网络应用是不容许的。因此，时钟同步对于这些应用显得十分必要。然而，由于传感节点资源受限

9、，传统的时钟同步协议（如NTP25）不能直接应用在传感网络中。另外针对传感网络提出的一些时钟同步协议（如10，13，21，26，37，29，16）实现了成对时钟同步和全局时钟同步。成对时钟同步设法获得临近节点对的高精度时钟同步，而全局时钟同步在传感网络中设法提供网络级的时钟同步。目前的成对时钟同步协议运用了接收端到接收端的同步（如RBS10，一个参考节点广播一个参考包来帮助成对接收端识别时钟差异），或者使用了发送端到接收端（如TPSN13，发送端通过与接收端通信来评估时钟差异）。而大多数全局时钟同步协议（如10，13，37）通过传感网络的多跳路径来确保所有节点在这些路径上的时钟同步。另外，扩散

10、式的全局时钟同步协议通过传播本地同步信息到整个网络来实现全局时钟同步21。无线传感网络中，传感节点通常需要组成一个个簇群来保证本地的时钟同步，从而使这些节点协同工作。例如，在基于时间片的MAC协议中，通过分配时间片给一个节点群来实现对共享通信介质的多路接入，在与其他节点没有冲突的情况下，传感节点需要一个同步时钟来访问其时间片。又例如，为了改善能耗，一个传感节点簇群可以不断地同时切换到节能睡眠模式41，这同样需要一个共同的时间基准来协调睡眠和侦听周期。在良性的环境中，这样一个本地共同的时间基准可以通过使所有节点与一个特定的节点同步来实现。但是，在一个恶性的环境中，一些节点可能被损坏，这就给簇群中

11、的时钟同步带来了相当大的挑战。的确，没有哪一个上述的时钟同步协议可以在节点损坏的情况下适用于恶性环境，因为一个损坏的节点会通过发送不同的时间来干扰其他未损坏的节点间的时钟同步。例如，当用RBS10来作为成对时钟同步时，一个损坏的节点会将其接收的参考包的错误时间提供给其他未损坏的节点。这就需要容错时钟同步技术来解决以上问题，这些技术已在分布式系统中得到了广泛地研究（如31，19，15，7，23，24，38，34，35，28，2，18，36，40）。但是传统的容错时钟同步技术不能直接应用在传感网络中，因为这些技术是针对分布式系统提出的，而分布式系统并不像传感网络一样会受到资源的限制。所有这些技术的

12、节点通信都是大量的，并且有时还会进行大量的运算，因为这些技术使用了数字特征（如HSSD7，CSM19）或多消息复本（如COM，CNV19）的方式，来防止在未检测的情况下恶性节点修改或破坏无错节点正常的时钟信息。通常，数字特征并不适应于资源限制的传感网络，即使使用了数字特征，如HSSD7，所有节点仍然需要在每一轮同步中发送消息给其他节点，这导致至少通信复杂度，其中是节点数目。另一些方案（如HSSD7，ST38）需要所有节点接收特定消息并立刻处理和转发给其他所有节点，在传感网络中这会导致信息冲突的概率升高。文献28所提出的方法将节点划分成重叠簇群并在每个簇群中采用了先前的一些算法（如CNV19，L

13、L23，24），这虽然减少了通信重叠，但不能避免传感网络中的消息冲突。针对每个簇群中所有节点通过广播通信的传感网络，本文提出了一种全新的容错时钟同步方案。在每一轮时钟同步中，只有一个节点作为主同步者，并只广播一个同步验证信息，这样本文提出的方案就能避免以前方案中遇到的消息冲突问题。该方案利用了最近提出的一种针对传感网络设计的本地广播验证技术，这种技术完全基于对称密码42，来避免对于消息验证中过多的数字特征。如果不良节点不超过三分之一，通过分析，本方案可以确保簇群中任意两节点间时钟差异的在有效的上限范围之内。一下内容中，第二部分将给出容错时钟同步的模型，本文的容错时钟同步方案将在第三部分介绍，第

14、四部分讨论相关的工作，最后在第五部分中将总结全文观点并展望未来研究方向。2 容错时钟同步模型本节中，本文参考文献7给出了一个容错时钟同步模型。本文首先为传感节点的时钟建立模型，然后给出容错时钟同步协议需要满足的条件。为了阅读方便，表1列出了本文所要用到的符号。本文中将区别实际时间和时钟时间两个概念。实际时间就是已规范的牛顿时间格式，它不能在传感节点的定时器中直接显示；而时钟时间能在传感节点的定时器中直接显示的时间。本文用小写字母来表示实际时间的变量和常量，用大写字母来表示时钟的变量和常量。一个时钟可以是从实际时间到时钟时间的映像，即便是在表1 本文符号一览 簇群中节点的数目簇群中冲突的不良节点

15、的数目当实际时刻时，节点的时钟正常工作时钟的最大漂移率两临近节点间最大消息传输延迟最大时钟读取错误同步间隔首个无错节点开始其第轮逻辑时钟的实际时间最后一个无错节点开始其第轮逻辑时钟的实际时间对于任意，在区间的最大时钟漂移实际时间时的时钟时间。当所有实际时间指向和时，如果时钟来自实际时间的漂移率限制在常量的范围内，则认为时钟正常工作。当时： 任意两个工作正常的时钟间的漂移率受限于值小于的。传感节点通常采用低成本的晶振，其典型的时钟漂移率为十微秒33。如果一个传感节点能正常执行一个给定时钟同步算法且时钟正常工作，则认为该传感节点是无错的。本文假设时钟按轮来同步，每轮包括次时间单元，并用（或）来表示

16、首个（或最后一个）无错节点开始其第轮逻辑时钟的实际时间点。对于任意，在区间上，存在两个工作正常的时钟之间的最大时钟漂移，即：假设某个节点在时刻进行一次时钟调整，则用和来对应表示在时钟调整前和时钟调整后的时钟时间。假设对于一个节点发送的消息存在一个上限，并且该节点传送和处理接收到的该消息。假设节点在时发送一个消息，节点在时接收到该消息，且节点调整其时钟为，那么：其中为时钟读取错误的上限，包含了最大传输延迟以及在该延迟中的时钟漂移。假设在起始时刻，两无错节点和之间的时钟差异小于，即：在下一节中，将针传感网络提出一种全新的容错时钟同步方案。假设个节点能够相互通信并组成了一个簇群，其中存在个的不良节点

17、。设和本文的算法满足一下两个条件：条件1：对于任意两无错节点和在任意实际时间点上，存在两节点间的一个时钟差异的上限值，即当所有的并且时，条件2：如果一个节点在时刻进行一次时钟调整，存在一个时钟调整的上限值，即。3 簇群的容错时钟同步3.1 概述本文集中讨论针对节点簇群给出的容错时钟同步方案，其中由一个节点广播的消息到达簇群中所有的其他节点。假设每个节点都有自己唯一的ID，且簇中每两个节点共享唯一的对键值（该对键值可由目前的一些键值预分配方案给出22，4，9）。一个节点可以通过手工分配来获得ID，或者通过其物理特性得到ID。一个节点使用与另一个节点共享的唯一的对键值来识别对方。针对该假设的一个潜

18、在的危险是“女巫攻击”8，即一个恶意节点通过采用多个ID来假扮多个节点。幸运的是，最近的研究27表明这些早期的键值预分配方案能够将攻击者假冒新ID的概率减少到接近为零，即使在一定数量的节点出现故障的情况下。一个攻击者可以通过损坏大量节点来提高假冒成功的概率，不过在这种情况下，所有的键值预分配方案也就被破坏了，进而导致这些网络没有安全可言。本文的容错时钟同步方案在每个次时间单元内都执行一次，为了方便，本文将这样一个次时间单元称为一轮。每一轮中，簇群的一个节点作为主同步者，它负责广播一个时钟同步消息给所有其他节点，从而使所有其他节点得到时钟同步。假设传感节点在一开始已得到了同步，而且，假设簇群中的

19、节点都能服从成为主同步者的顺序规则。本文将该顺序规则称为主同步者顺序规则。可以有几种方式来满足以上两个假设，例如可以用文献24的方法来实现起始的时钟同步，并采用OM算法20来决定一个的簇群中的主同步者顺序规则。实际中为了满足上述假设采用的方法是在传感网络的开发过程中添加一个引导程序阶段。我们可以用一个或多个能维持良好同步时钟的委托外部设备（如通过GPS接收端），来实现传感网络的引导阶段。假设传感节点在网络的开发阶段不会损坏，这在通常情况下是合理的。这样，外部设备可以分配同步起始时钟值给所有的传感节点。同时，这些外部设备可以收集来自周围传感节点和簇群的信息，并在每个簇群中分配主同步者顺序规则。如

20、果要在引导阶段考虑安全问题，那么在每个节点以及受托设备之间可以使用一个对称密钥。当布置到一个传感网络后，整个引导阶段可以完全自动执行。当然， 还有其他一些可行的方法来满足以上假设。在本文提出的算法中，每个节点包含一个计数器，从1开始每轮递增1。假设一个传感节点到达了次时间单元，其中为每轮中时间单元的个数。如果一个节点是主同步者，它可以立即广播验证信息到所有其他节点。当一个非主同步者节点接收到这样一个验证信息时便会检查该信息，如果该消息无效或者发送端不是制定的主同步者，接收端就会丢弃该消息。否则，接收端按照接收到的同步消息中的时间来调整其自身当前的时间，并且接收端可以判断该主同步者的时钟是否是在

21、其实同步时钟后的第次时间单元。本文提出的方案可以工作在“任意攻击模式12”下，该模式中恶意节点可以任意从协议规则中摆脱出来（如用方向天线发送干扰消息到其他节点）并危害拉拢其他节点。由于通信错误可以被视为发送节点错误，所以本文并不将其单独考虑。假设攻击者可以用一个资源充足的节点（如带有方向天线的膝上电脑）来取代一个受损的传感节点，并超越正常节点夺取有利位置。由于本文仅考虑无错节点间的时钟差异问题，为了简便，本文将“最大时钟差异”来表示“两无错节点间的最大时钟差异”。下文中，将首先讨论如何进行广播同步消息的验证，接着描述和分析本文提出的方案，再与一些传统的容错时钟同步方案进行比较。3.2 广播验证

22、在每轮时钟同步中，仅有一个节点担当主同步者并广播同步消息。为了防止恶意节点假冒无错的主同步者，每个同步消息必须得到验证。本文提出的方案并不需要在同步消息中含有一个时钟值。在从主同步者接收到一个同步消息后，该节点知道如何调整其时钟。这样，接收节点只需确定消息是否来自正确的主同步者以及消息是否没被恶意节点替换。针对传感网络，本文采用最近提出的一个本地广播验证方案42来验证广播的同步消息。首先，每个节点按的方式生成一个一维的密钥链，其中，而是一个随机数，是一个一维函数。每个节点发送至其他节点来作为其密钥链的“委托消息”，节点通过相互之间共享的成对密钥来验证。密钥链中的密钥在其这一轮的反序规则中是公开

23、的。当一个节点作为主同步者时，它将下一个未公开的密钥添加到广播消息的密钥链中。当其他节点接收到该消息时，就会验证该消息是否来自使用“委托消息”的指定节点，或者是否是最近公开的该节点密钥。当时，注意有。这样，即使一个节点从指定的主同步者没有接收到任何在和之间的密钥，该节点仍然可以通过来密钥确定密钥。由于一维函数的特性，一个恶意节点无法得到一个无错节点未公开的密钥。每个节点只接收第一份广播消息，而会将以后的消息复本丢弃。因此，一个恶意节点无法伪造或重用无错节点的广播消息。攻击者可以在一定程度上屏蔽受害节点而不接收第一份同步消息，或者在无错节点间建立一个虫洞17，这样受害节点可以接收延迟的同步消息。

24、这种攻击等同于将一个恶意节点冒充为主同步者，当恶意节点或屏蔽的无错主同步者的总数满足，这种攻击就能得到防范。这个广播验证方案在初始化阶段需要个单播消息来转换所有节点密钥链的“委托消息”。3.3 容错时钟同步算法本方案在每一个次时间单元执行一轮时钟同步。为了简便，假设“其实时间”为。对于任意两无错节点和，有。每个节点包含一个计数器，在每轮时钟同步时递增1，起始时。假设每个节点产生了一个一维密钥链并与其他节点交换“委托消息”。该算法包含两个在无错节点连续运行的任务。第一个任务，如果节点作为第轮同步的主同步者，当其时钟时间为时，立刻向所有其他节点广播一个同步消息“”，其中为节点的ID，为节点在第轮用

25、于验证的密钥链。第二个任务，当一个节点在第轮时钟同步的时钟时间时接收到一个同步消息，如果或者，则该节点会将此消息丢弃。本文的算法中，为任一无错节点与无错主同步者之间的最大时钟差异，其中为恶意节点数目，若节点都是无错的，则为任意两节点之间的最大时钟差异。否则该算法验证节点是否为正确的主同步者，并且验证该节点是否是第一次接收到，从而，其中为一个一维函数，为第轮节点接收到的密钥或者“委托消息”。一旦该消息无法通过这些验证，节点就会丢弃该消息。否则，节点会计算时钟差异并执行以下时钟调整：如果，节点通过增加来调整其时钟时间；如果，节点通过来增加其时钟时间；如果，节点通过来减小其时钟时间。同时该节点的计数

26、器按1递增。如果该节点不能按时间在本轮中接收到同步验证消息，就会让计数器增1并进入下一轮。本算法保证在每轮时钟同步后所有同步节点保持相同的计数器值。一个节点可能会从簇群中失去与其他节点的同步，比如由于长期的通信错误。如果该错误节点能够与同个簇群中的其他节点重新建立直接和可靠的通信，那么该节点可以试图从这种错误中恢复过来。一个可能的办法是向其他所有节点那里请求当前最图1 算法1，同步环算法新的时钟值，并采用中值来决定本地时钟值。然后该节点可以通过恢复的时钟值以及同步间隔来计算出计数器的值。如果这些节点中的大多数是无错的且维持着时钟同步，那么存在两节点和，对应的时钟值为和，这样以上提到的时钟中值就

27、介于和之间。换句话说，错误节点可以在一定可接受的范围内成功重置其本地时钟。然而在其他情况中错误节点无法保证得到恢复。图1 中的算法1给出了伪代码。由于在一轮罗宾方式中，所有节点都会轮流担当主同步者，所以本文将该方案称为同步环（SR）算法。为了确保时钟不被回置，我们必须进一步采用文献19中提出的技术，该技术将同步调整延长到下一个周期。由于篇幅所限，本文略去细节介绍。下面首先在没有恶意节点参与时检查该技术，然后在有针对损坏节点进行拉拢攻击时的情况进行研究。 恶性主同步者 无错主同步者 图2 时钟差异的变化引理1：当一个无错节点在时刻将其时钟调整为无错主同步者的时钟时，且，则对任意，有：。定理1：假

28、设对于任意两节点和，有。如果所有节点都是无错的，执行同步环（SR）算法且没有通信错误，则对于所有，有：。在期间，两非同步的节点和仅能达到的最大时钟差异为，而在节点（或节点）与主同步者之间的时钟差异至多为，这个值是当所有节点无错时所允许的最大时钟调整值。下面考虑有恶性主同步者的情况。引理2：如果第个主同步者是恶性的，在期间，它可以提高最大时钟差异到至多的程度。引理3：假设两无错节点和在时刻和对应地与主同步者进行同步，且。如果满足且，则有：。引理4：假设在期间，两节点和之间的最大时钟差异为，如果且第轮主同步者是无错的，那么对于任意，有。引理5：当，算法1满足以下条件：1）对于所有且，若指定两无错节

29、点和，有。2）如果一个节点在时刻调整其时钟，那么。最大时钟差异（单位：秒）恶性节点的个数图3 仿真中达到的平均（Average）最大时钟差异值与理论值的比较引理6：同步间隔是被界定的，因为，对于所有，有以及，其中。引理7：对于所有，在时间间隔上，有。定理2：当，算法1为一个无错时钟同步算法，并将时钟差异的上限值定为，把作为时钟调整的上限值，其中以及。图2中显示了一个最大时钟差异变化的例子。第一个主同步者是无错的。在期间，最大时钟差异小于。第二和第三主同步者都是恶性的，它们把最大时钟差异增加到。第四个主同步者是无错的，并把最大时钟差异增加到。可以看到所有的恶性主同步者都能将相同量的最大时钟错误引

30、入到最大时钟差异中，它们担当主同步者的顺序没有改变。3.4 讨论3.4.1 最大时钟差异的理论与平均的比较当受损或恶性节点的数目满足时，定理2给出了最大时钟差异的上限值。但是仅当个恶性节点连续担当起主同步者时才能达到最大时钟差异的上限值，并且该情况发生的概率仅为每轮消息的数目恶性节点的数目（节点总数为n50）图4 在相同条件下最大时钟差异的通讯开销。为了理解在实际中一般达到的最大时钟差异，本文进行了一系列仿真实验。图3 显示了理论上（Theoretical）的最大时钟差异以及在仿真中达到的平均（Average）最大时钟差异，分别为10、20和50。对于每个数据节点，担当主同步者的顺序为个不同的

31、随机顺序。每2分钟节点同步一次，时钟漂移率为，以及为0.0001秒。图中的结果显示，当大于5时，仿真得到的最大时钟差异平均小于理论界限的一半。3.4.2 与MAC协议的结合在一个基于时间片的传感网络中，划分传感节点为一个个簇群。在任意时刻，每个簇群中仅有一个节点允许访问无线通信介质。基于时间片的MAC协议在每个簇群中需要一个本地时钟同步来给节点安排时间片，本文提出的方案就提供了这样的一个时钟同步。例如，当时间片大小为秒且每个簇群含有个节点时，设同步时钟间隔为，其中为一个整数且。假设每个时间片中给节点第个时间片，那么节点会在而不是原来的时广播发送一个同步信息。本算法可以通过简单的一点修改来适应这

32、种变化。在基于CSMA的传感网络中，由于所有传感节点争用无线通信介质，传输延迟被限制的假设并不成立。传输延迟主要包括发送时间、接入时间、传播时间和接收时间13。由于可以根据消息长度了来估算出发送时间和接收时间，并且传播时间非常短以至于可以被忽略，我们实际上只需要解决未定的接入时间。因此，可以在很短的时间间隔内，通过预设广播同步消息的主同步者的无线信道，来限定接入时间，这可以通过使所有其他节点在时间间隔内侦听信道来得到实现，其中为轮数，为同步间隔，为最大时钟差异。为了改善传感网络的能耗，一些方法提出可以将传感节点频繁地切换到省电睡眠模式（如41）。该方法中，节点按簇划分并保证在同一个簇中节点同时

33、睡眠（或侦听）。为了将本文提出的方案与该省电睡眠方法结合，需要做到两点：1）在活跃期内节点与其他节点进行传输和侦听；2）在无错节点的活跃期内完成每轮同步。所有无错节点在省电模式中满足第一个要求。如果本文提出的方案中的最大时钟差异小于在省电方法中定义的侦听时间的一半，则能满足第二个要求。假设所有无错节点在内激活，当一个无错主同步者在时广播一个消息，从而让其他节点激活，在任意时刻两无错节点和间有。例如，在文献41中，侦听时间设为300毫秒，睡眠时间设为1秒。根据图4中的仿真结果，表2 性能比较算法容错度通信开销（每轮消息数目）最大时钟差异CNV19（单播）COM19（单播）CSM19（单播）HSS

34、D7（单播）SR1（广播）本方案可以保证最大时钟差异小于150毫秒。因此本方案可以结合文献41的方法来提供时钟同步。3.4.3 组群与全局时钟同步在大型传感网络中，由于物理限制如通信范围，通常无法把所有节点分到一个簇群中去，这就需要划分一定数量的簇群来解决。簇群的个数以及其大小都取决于网络节点的密度、节点的通信范围以及特定应用的要求。当节点划分好簇群且保证节点能在自己的簇群中与其他节点广播通信后，本方案就能在每个簇群中使用基于簇群的容错时钟同步技术。很容易在每个簇群中布置一个簇头，该簇群中的节点与该簇头保持同步，从而实现基于簇群的时钟同步技术。然而，一旦簇头损坏，整个簇群就无法正确同步了。而本

35、方案提供了容错特性，并通过主同步者（簇头）的轮换来保持簇群的稳定。本文提出的基于簇群的容错时钟同步方案虽然不能在需要全局时钟同步的簇群中反复使用，不过作为目前许多全局时钟同步方案的基础还是很有前景的。例如Olson和 Shin两人提出了一种容错时钟同步技术28，该技术将节点划分为一些重叠的同步组，并在每个同步组内采用交互收敛算法19。此外，我们也可以利用簇群算法开发一个簇群结构。一个简单的解决办法就是在每个簇群中选出簇头并用一个外部时钟资源来同步这些簇头。当簇头完好的情况下，簇群中的每个节点就能通过簇头来得到全局时钟时间。为了提高容错度，每个簇群可以选出不止一个簇头，并且节点可以采用这些簇头的

36、中间值来决定全局时钟值。即使所有簇头损坏，簇群中剩下的节点只要没用大于三分之一的损坏，该簇群还是能维持本地时钟同步。显然，有必要进行进一步的研究来将本算法拓展为具体的全局时钟同步技术，我们会在后期研究中考虑这点。3.5 与先前技术的比较本文提出的算法中，每轮时钟同步只有一个节点担当主同步者且其他节点不许回应主同步者发送来的消息。因此，当没有恶意攻击时，时钟同步过程中不会出现消息冲突。相比之下，几乎所有目前的其他容错时钟同步方案（如CNV19，HSSD7）都需要参与节点同时发送或转发同步消息，这就很可能在应用到无线传感网络时产生消息冲突。而且本文提出的方案利用了广播介质以及针对传感网络最新提出的

37、验证技术42，因此对广播验证不需耗费过多的数字特征。相比之下，一些传统的容错技术（如CSM19，HSSD7）却需要数字特征，而无法适用在资源受限的传感网络中。值得注意的是，这些方案没有采用最新提出的验证技术42。原因之一是这些方案需要转发接收到的消息，而一个恶意节点可以在节点转发该消息之前复制该消息。另一个原因是消息冲突。在基于CSMA的传感网络中，所有节点共享无线通信信道。在CSM和HSSD中，为了减少同步错误，节点在接收到消息后将尽快向其他节点转发消息。因此，在节点广播消息之后，由于传输时间很短，其临近的所有其他节点可以几乎同时接收到该消息。假设所有节点有相同的内部结构，则它们更有可能同时

38、广播消息而造成消息冲突。在一个簇群中个节点同步的情况下，表2将本文提出的方案与其他容错时钟同步算法进行了比较。我们将一种算法所能容忍的最大恶性节点数目视为容错度。在一个有个节点的簇群中，本方案的容错度为，这与算法CNV及算法COM的容错度相同。但是，算法CSM及算法HSSD针对干扰攻击能提供更好的容错度。下面将本方案的通信开销与目前其他的容错方案进行比较。假设表2中列出的这些方案可以用广播的方式代替单播方式来发送同步消息。对CNV和HSSD来讲，这将每轮的消息数目由减少到了，而COM和CSM由减少到了。接着本文对最大时钟差异设置同样的界限来在比较所有这些方案的通信开销。为了把差异解释清楚，本文

39、用以及与在3.4节中仿真实验相同的参数来计算出这些方案的通信开销。在保守假设（但是不切实际）HSSD和CNV也能用验证广播来发送同步消息的情况下，图4显示了CNV、HSSD以及本方案各自不同的容忍干扰恶性节点的最大数目。该图显示了本文提出的方案始终比CNV（也包括CSM及COM，它们也有相当大的通信开销，但在图4中未表示出来）的通信开销来的小。另外，当能容忍的干扰节点数目变小时，本方案的通信开销就变少；而当能容忍的干扰节点数目变大时，本方案的通信开销也就增大。但是由于在HSSD中使用了广播通信，HSSD不得不被修改来达到这性能，但这样会造成HSSD存在相当大的消息冲突。而且HSSD对传感网络所

40、需的数字特征也变得相当可观，这在之前已经讨论过。4 相关工作学术界研究时钟同步问题已许多年了。早期的技术（如NTP25）主要针对有线网络的时钟同步，但是这些技术通常假设有无限的运算资源以及网络带宽，因此这些技术不适用于资源有限的传感网络。正如在第一节中提到的，目前已经提出了一些针对传感网络的时钟同步技术（如10，11，6，14，13，21，26，37，29，16，32）。Elson等人针对成对和多畴的时钟同步开发了参考广播同步（RBS）方案10，该方案用一个参考的广播节点来从时钟读取错误中估算出未知的发送时间和接入时间。Dai和Han通过在每个广播域内减少通信开销将RBS改良为双广播方式6。P

41、alChaudhuri等人基于RBS提出了概率性的时钟同步29，它通过减少通信开销将有线网络中的概率性的时钟同步（1，5）扩展到了传感网络。Generiwal等人针对传感网络提出了一种分层时钟同步方案并称为TPSN13，该方案假设时钟同步消息为MAC层的时间信息。Sichitiu和Veerarittiphan通过确定地评估两传感节点之间相对时钟漂移及偏置的界限，提出了一种小型的方案来实现时钟同步37。Li和Rus基于本地时钟信息扩散，提出了全局时钟同步技术21。但是所有这些技术都假设在良好的应用环境下，却不能适用于恶性攻击及节点损坏的情况。本文提出的技术就是来解决基于簇群时钟同步中损坏节点遭到

42、的地址攻击的问题。本文提出的同步技术与早已得到实质研究的传统的针对分布式系统的容错时钟同步密切强关（如31，19，15，7，23，24，38，34，35，28，2，18，36，40），这些技术采用了软件或硬件的方法31。基于硬件的技术需要一个同步电路连续地监控所有时钟，但这不能用于传感网络。基于软件的技术则能被进一步分类为平均收敛（如CNV19，LL23，24）、非平均收敛（如HSSD7，ST38）或一致性算法（如COM，CSM19）。一些基于软件（或硬件辅助，或混合）的技术30用软件来产生时间信息，这样可以减少在时钟同步中包含的未知因素。这些技术的普遍特点是采用冗余消息来解决恶性参与者的攻击

43、行为。这些容错方案通常有很高的通信开销（特别是像COM和CSM这样的基于一致性的算法）。而且，为了防止恶性参与者的伪造消息，这些方案使用了数字特征（如CSM19，HSSD7）或需要让多节点同时广播的广播源，这就导致了在无线传感网络中的消息冲突。而文献28中的方法将节点分为重叠的簇群，并在每个簇群中运行早期的一些算法（如CNV19，LL23，24），该方法减少了通信开销，却也不能避免在无线传感网络中的消息冲突问题。本文提出的技术正是为解决此类问题，采用了一些传感网络簇群时钟同步的唯一特性以及最新本地广播验证的一些成果。5 结论本文针对传感网络的节点簇群提出了一种容错时钟同步方案。该方案保证了在一

44、个簇群中的任意无错节点间有一个时钟差异的上限值，但是前提是簇群中的恶性节点不超过三分之一。相比于目前其他的容错时钟同步技术，本方案可以避免其他技术遇到的消息冲突的问题，并且不需要大量的数字特征。当然，本方案也存在一些局限。首先本方案需要簇群节点在起始就保持同步，这就不得不要采用一些其他手段，例如在启动阶段采用委托的外部设备（见3.1节）或者采用一个容错的初始时钟同步方法（如24）。其次，本方案需要簇群中的每个节点都能通信到其他所有节点，这就缩小了每个簇群的传播范围。我们以后的工作将针对传感网络着眼于研究小型容错的全局时钟同步技术。参考文献1 K. Arvind, “Probabilistic

45、Clock Synchronization in Distributed Systems,” IEEE Trans. Parallel and Distributed Systems, vol. 5, no. 5, pp. 474-487, 1994.2 B. Barak, S. Halevi, A. Herzberg, and D. Naor, “Clock Synchronization with Faults and Recoveries,” Proc. 19th Ann. ACM Symp. Principles of Distributed Computing, pp. 133-14

46、2, 2000.3 K. Chakrabarty, S.S. Iyengar, H. Qi, and E. Cho, “Grid Coverage for Surveillance and Target Location in Distributed Sensor Networks,” IEEE Trans. Computers, vol. 51, pp. 1448-1453, 2002.4 H. Chan, A. Perrig, and D. Song, “Random Key Predistribution Schemes for Sensor Networks,” IEEE Symp.

47、Research in Security and Privacy, pp. 197-213, 2003.5 F. Cristian, “Probabilistic Clock Synchronization,” Distributed Computing, vol. 3, no. 3, pp. 146-158, 1989.6 H. Dai and R. Han, “TSYNC: A Lightweight Bidirectional Time Synchronization Service for Wireless Sensor Networks,” ACM SIGMOBILE Mobile

48、Computing and Comm. Rev., vol. 8, no. 1, pp. 125-139, 2004.7 D. Dolev, J.Y. Halpern, B. Simons, and R. Strong, “Dynamic Fault-Tolerant Clock Synchronization,” J. ACM, vol. 42, no. 1, pp. 143-185, 1995.8 J.R. Douceur, “The Sybil Attack,” Proc. First Intl Workshop Peer-to-Peer Systems (IPTPS 02), Mar.

49、 2002.9 W. Du, J. Deng, Y.S. Han, and P. Varshney, “A Pairwise Key Pre-Distribution Scheme for Wireless Sensor Networks,” Proc. 10th ACM Conf. Computer and Comm. Security (CCS 03), pp. 42-51, Oct. 2003.10 J. Elson, L. Girod, and D. Estrin, “Fine-Grained Network Time Synchronization Using Reference B

50、roadcasts,” ACM SIGOPS Operating Systems Rev., vol. 36, pp. 147-163, 2002.11 J. Elson and K. Romer, “Wireless Sensor Networks: A New Regime for Time Synchronization,” Proc. First Workshop Hot Topics in Networks (HotNets-I), Oct. 2002.12 A. Galleni and D. Powell, “Consensus and Membership in Synchron

51、ous and Asynchronous Distributed Systems,” Technical Report 96104, LAAS, Apr. 1996.13 S. Ganeriwal, R. Kumar, and M.B. Srivastava, “Timing-Sync Protocol for Sensor Networks,” Proc. First Intl Conf. Embedded Networked Sensor Systems (SenSys), 2003.14 J. Greunen and J. Rabaey, “Lightweight Time Synchr

52、onization for Sensor Networks,” Proc. Second ACM Intl Workshop Wireless Sensor Networks and Applications (WSNA), Sept. 2003.15 J.Y. Halpern, B.B. Simons, H.R. Strong, and D. Dolev, “Fault-Tolerant Clock Synchronization,” Proc. Third Ann. ACM Symp. Principles of Distributed Computing, pp. 89-102, 198

53、4.16 A. Hu and S.D. Servetto, “Asymptotically Optimal Time Synchronization in Dense Sensor Networks,” Proc. Second ACM Intl Workshop Wireless Sensor Networks and Applications (WSNA), Sept. 2003.17 Y.C. Hu, A. Perrig, and D.B. Johnson, “Packet Leashes: A Defense against Wormhole Attacks In Wireless A

54、d Hoc Networks,” Proc. INFOCOM 2003 Conf., Apr. 2003.18 C.M. Krishna, K.G. Shin, and R.W. Butler, “Ensuring Fault Tolerance of Phase-Locked Clocks,” IEEE Trans. Computers, vol. 34, no. 8, pp. 752-756, Aug. 1985.19 L. Lamport and P.M. Melliar-Smith, “Synchronizing Clocks in the Presence of Faults,” J

55、. ACM, vol. 32, no. 1, pp. 52-78, 1985.20 L. Lamport, R. Shostak, and M. Pease, “The Byzantine Generals Problem,” ACM Trans. Programming Languages and Systems (TOPLAS), vol. 4, no. 3, pp. 382-401, 1982.21 Q. Li and D. Rus, “Global Clock Synchronization in Sensor Networks,” Proc. IEEE INFOCOM 2004 Co

56、nf., Mar. 2004.22 D. Liu and P. Ning, “Establishing Pairwise Keys in Distributed Sensor Networks,” Proc. 10th ACM Conf. Computer and Comm. Security (CCS 03), pp. 52-61, Oct. 2003.23 J. Lundelius and N. Lynch, “A New Fault-Tolerant Algorithm for Clock Synchronization,” Proc. Third Ann. ACM Symp. Prin

57、ciples of Distributed Computing, pp. 75-88, 1984.24 J. Lundelius-Welch and N. Lynch, “A New Fault-Tolerant Algorithm for Clock Synchronization,” Information and Computation, vol. 77, no. 1, pp. 1-36, 1988.25 D.L. Mills, “Internet Time Synchronization: The Network Time Protocol,” IEEE Trans. Comm., vol. 39, no. 10, pp. 1482-1493, 1991.26 M. Mock, R. Frings, E. Nett, and S. Trikaliotis, “Clock Synchronization for