常兴华，陈春鹏

(中国人民解放军91404部队，河北秦皇岛066000)

0 引言

随着信息时代的到来，战争手段不断更新，传感器网络在战争中发挥了越来越重要的作用，例如美国的“狼群”系统即是针对电子战的传感器网络。因此，传感器网络的研究方兴未艾［1，2］，为满足节点间的协调和信息共享，传感器网络的时间同步成为当前一个新的研究热点［3－7］。传感器网络是一种分布式自组织网络，特别是在无基站或者利用动态基站收集数据的网络中，节点与节点之间组成对等(P2P)网络，节点之间进行对等数据传输。P2P网络是基于Internet之上构建的一个完全位于应用层的对等网络，节点间具有很强的对等性、匿名性、开放性和松耦合性等特点。P2P的技术优势有助于解决传感器网络中的关键技术问题［8］。通过研究对等网络中的时钟管理方法，解决传感器网络中传输消息的因果关系问题。

1 相关研究

因果性问题作为分布式系统中的重要问题被广泛关注。在分布式系统的时间同步研究中，Lamport首先提出了逻辑时间的思想［9］，但不能捕获所有并发;Fidge和 Mattern分别提出了向量时钟的概念［10，11］，但存储、通信和处理时间的额外耗费随着系统大小N线性增长;Medal等提出一种降低额外消耗的时钟策略［12］，但是它仅仅用于判断消息之间的因果关系。目前，在许多应用中采用了改良的向量时钟，例如:为了降低额外消耗，Lee等提出增量向量时钟的技术，仅仅对消息附加改变的向量时钟［13］;Anh提出了懒向量时钟协议，提供向量时钟的覆盖范围和可扩展性之间的折中［14］。同时，在分布式虚拟环境应用中也对时间同步进行了深入研究。

2 模型描述

在P2P结构中，每个节点具有完全的自治性，只能通过网络传输信息而相互通信。为了使研究简化，假定通信协议是面向连接的，并且节点的拓扑结构图包含所有可能传输信息的连接，是静态的和已知的。对P2P网络进行如下建模:对等网络G=(V，E，M)是一个互连的有向图，其中V是通信节点的集合，E是边的集合，表示节点对之间可能的互连，M是节点间传输的消息的集合。

2.1 基本定义

定义1:在对等网络中，有从节点u到节点v的边，称为直接连接，记作:(u，v)。如果从节点u到节点v存在一条长度大于1的路径，则称间接连接，记作:［u，v］。

在对等网络中，如果没有消息发出，一个节点中的事件对于其他节点来说是不可知的。消息的发送和接收意味着节点之间的信息流动，并且建立了发送节点和接收节点之间的因果依赖关系。

定义2:节点i接收消息m表示消息m被送达到节点i。节点i提交消息m表示消息m被节点i处理。

在任何节点，对消息的接收没有任何限制，但必须保证消息按照因果关系提交。

定义3:对于消息m1和m2，若它们从同一个节点发出m2是m1的下一个消息，若它们从不同的节点发出m2是m1提交后的下一个消息，称m1和m2之间存在直接因果关系，记作:m1→m2。如果m1→m2，m2→m3，…，mn－1→mn(n＞1，n∈Nat)，则称m1和mn之间存在因果关系，记作:m1mn。

可以说，m2是m1的结果消息，m1是m2的原因消息。很明显，因果关系是反自反、反对称和传递的。

定义4:如果m1m2且m2先于m1提交，称为因果异常发生，记作:A(m2，m1，v)。

2.2 结构分析

这里，用抽象的观点研究为什么因果异常可能发生的问题，如图1所示。在对等网络G=(V，E，M)中，u，v，w∈V，m1，m2∈M，m1→m2，因为边(w，v)和边(u，v)不同而网络中的消息延迟是可变的和不可预测的，所以A(m2，m1，v)有可能发生。

图1 对等网络中因果异常结构分析

在解决问题前，声明一些有用的假定，这些假定表示使用理论所应满足的条件。

假定1:任一连接都是可靠、有序的，消息的接收顺序与发送顺序一致。

网络系统首要考虑的是节点间消息通道的属性，这样的通信协议随处可见，例如:广泛使用的TCP/IP。

假定2:从同一节点发出的消息必须遵循时间进化的递增顺序。

该假定保持同一节点发送消息的相对顺序，是防止系统运行中发生因果异常的基本要求。该假定保证了消息有序发出，是逻辑时钟推进过程中通用的假定［9－11］。

定理1:源自同一节点的因果消息不会在系统中引发因果异常。

基于假定1和假定2，该定理明显成立。

定理 2:对等网络G=(V，E，M)，u，v∈V，m1从u发出，如果因果异常A(m2，m1，v)发生，则(u，v)∈E且∃［u，v］。

定理2描述了因果异常可能发生的基本结构，即在对等网络中，原因消息发送节点和因果异常发生节点之间同时存在1个直接连接与1个或多个间接连接。

3 向量时钟管理算法

3.1 基本思想

向量时钟管理(VCM)算法需要在正常的系统运行前维护各节点的初始时钟信息，并且需要针对各节点确定可能向其发送原因消息的节点集合和可能向其发送结果消息的节点集合。在VCM算法中的每个节点都维护着2个队列，一个是FIFO队列，该队列中的消息保持先入先出(FIFO)原则，其中的消息可以直接提交节点，因此将消息放在FIFO队列中就意味着将该消息提交节点了;另一个是Waiting队列，用于存储先接收的结果消息，这些消息在该队列中等待其后到达的原因消息。

该算法的基本思想如图2所示。节点接收消息后，根据消息的来源节点和时标，判断该消息能否立刻提交。当从结果路径收到消息时，节点判断消息的时标与其本身向量时钟之间的关系，确定是否存在带有更小时标的原因消息仍在传送过程中。如果是，确定该消息是先于原因消息收到的结果消息，则将该结果消息放在Waiting队列中延迟提交。否则，该消息不可能在该节点引发因果异常，可以立即放入FIFO队列中。如果有消息被放入到FIFO队列中，则节点的向量时钟推进，然后根据新的向量时钟检测Waiting队列中的消息。

图2 VCM算法的基本思想

3.2 数据结构

在VCM算法中，每个消息m带有时标VTm，而每个节点i维护如下数据结构:

①VTi:节点i的向量时钟。节点i提交消息m的更新规则为:VTi=sup(VTi，VTm)，sup(u，v)=w:w［i］=max(u［i］，v［i］)，∀i;

②Joined(i):有边到节点i的节点的集合;

③EffectSet(i):可能发送结果消息给i的节点的集合;

④CauseSet(i):可能发送原因消息给i的节点的集合;

⑤d:逻辑时钟可能推进的步长，d＞0。

3.3 算法

定理3:假定分布式系统G=(V，E，M)，当发送自节点j的消息m在节点i接收时，若VTm［j］≤VTi［j］，则∃m1已经被i接收并提交，且mm1。

由于VTi［j］表示节点i对节点j进展的了解，根据向量时钟的更新规则，该定理明显成立。

定理4:假定分布式系统G=(V，E，M)，对于m∈M是从节点j发送由节点i接收并提交的消息，m1∈M是从节点k发送由节点i接收并提交的消息，如果因果异常A(m，m1，i)发生，则j∈EffectSet(i)且当m被提交时VTi［k］＜VTm［k］。

定理4表明，如果消息m不是来自结果节点，或者对于所有k∈Joined(i)且k≠j VTm［k］≤VTi［k］，则不会引发因果异常。所以在向量时钟管理算法中首先判断消息的发送节点，然后在消息被接收后通过比较向量时间来避免因果异常。

向量时钟管理算法如下:

①当节点i发送消息m时:

VTi［i］∶ =VTi［i］+d;i的当前时钟附加到m，即，VTm∶ =VTi.

②当节点i接收来自节点j发送的消息m时:

If(j∉EffectSet(i)∧j∉CauseSet(i))

{VTi［i］∶ =VTi［i］+d;VTi∶ =sup(VTi，VTm);将m放入FIFO队列}

Else

{If(j∉EffectSet(i)∨for all(k∈Joined(i)∧k≠j)VTm［k］≤VTi［k］)

{VTi［i］∶ =VTi［i］+d;

VTi∶ =sup(VTi，VTm);

将m放入FIFO队列;

Detect Waiting Queue.}

Else将(m，j)放入Waiting队列.

}

Detect Waiting Queue是一个递归函数，用来判断Waiting队列中的消息是否可以转移到FIFO队列中。

4 属性分析

首先，对一些简单的网络拓扑下进行算法性能分析，例如:线型、星型树型和层次三角型。对于这些拓扑网络，在初始化阶段，可以得到任何节点i的EffectSet(i)都是空集。所以在整个系统运行过程中，只要消息到达就可以提交。在这些简单拓扑的网络中，VCM的性能与没有使用时钟的系统性能相差不多。然后，讨论VCM算法的通用属性。

属性1:没有因果异常

很明显，P2P网络使用VCM算法维护时钟推进，能够满足避免因果异常的需求。

定理5:假定分布式系统G=(V，E，M)，对于同一节点i接收的消息m1，m2∈M，使用向量时钟管理算法维护时钟推进，若m1→m2，则VTm1＜VTm2。

定理6:假定分布式系统G=(V，E，M)，对于同一节点i接收的消息m1，m2∈M，使用向量时钟管理算法维护时钟推进，则m1m2iff VTm1＜VTm2。

定理6的结果与标准向量时钟协议正确地捕获分布式系统事件间的因果关系的结论一致［13，14］。

属性2:没有死锁

假定在节点i发生死锁，那么i必然处于无限等待状态。但是在VCM算法中如果i处于等待状态，它必然是首先接收到结果消息m2，而需要等待原因消息m1。并且m1m2，则m1必然已经被发送而且正处在向i传送的过程中。所以基于通信通道可靠的假定，消息m1必定在将来某时刻被接收，这样节点i的等待状态截至。所以在节点i不可能发生死锁。

属性3:并行

VCM算法通过开拓消息间的“发生在先”关系，没有因果相关的消息可以在各个节点按任意顺序提交，在保证消息按因果序提交的前提下最大化了节点间的并行性。

5 结束语

在确定P2P网络中拓扑结构的基础上，对网络中可能引发因果异常的条件进行了深入分析，基于爱因斯坦—闵可夫斯基的相对论时空观，利用向量描述表示消息间因果关系的时间，将严格的时序关系弱化，提出了向量时钟管理算法。该算法采用预测—延迟技术，并给每个消息标记时标，消息间潜在的因果关系通过比较消息的时标与接收节点的时钟确定，节点对其中可能发生因果异常的消息进行监控，并对先收到的结果消息进行缓存，直到其所有原因消息都被提交给节点后才提交该结果消息。经分析验证，该算法既可以避免因果异常，又可以增加并发、提高性能。该向量时钟管理算法的应用推广将是下一步的工作。

［1］闫会芹，何加铭，郑紫微，等.无线传感器网络模糊逻辑分簇路由协议［J］.无线电通信技术，2013，39(6):18－21.

［2］张绪昌，何加铭，谢志军，等.无线传感网络移动分簇路由策略［J］.无线电通信技术，2012，38(5):6 －8.

［3］杨逊豪，何加铭，董义旺，等.基于无线传感器网络时间同步MAC协议研究［J］.无线电通信技术，2012，38(6):15－19.

［4］戴亚文，李小强，邱 航.结构健康监测无线传感网络同步采集研究［J］.无线电工程，2010，40(9):1 －4.

［5］常光强，樊晓平，刘少强.基于时间同步的无线传感器网络覆盖控制优化算法［J］.计算机应用研究，2012(1):35－37.

［6］李 立.无线传感器网络时间同步算法研究［D］.北京:清华大学博士学位论文，2010.

［7］王义君.面向物联网的无线传感器网络时间同步与寻址策略研究［D］.长春:吉林大学博士学位论文，2012.

［8］罗 樵，陈 靖，郭一辰，等.大规模无线传感器网络中基于P2P的路由模型研究［J］.计算机科学，2012(2):122－125.

［9］周航军，张红雷.一种DVE中通用的因果消息序时间管理分布式中间件［J］.计算机工程与科学，2012(3):80－85.

［10］周航军.分布式大规模虚拟环境消息序一致性时间管理技术研究［D］.长沙:国防科学技术大学博士学位论文，2011.

［11］付 沙，周航军.广域网分布式虚拟环境中的动态因果消息序控制方法［J］.计算机应用，2012(4):1 013－1 016.

［12］LAMPORTL.Time，Clocks，and the Ordering of Events in a Distributed System ［J］.Communications of the ACM，1978，21(7):558 －565.

［13］FIDGEC J.Timestamps in Message-passing Systems that Preserve the Partial Ordering［C］∥ in Proc.11th Australian Comp.Sci.Conf.，1988:56 － 66.

［14］MATTERNF.Virtual Time and Global States of Distributed Systems［C］∥in Proceedings of the International Workshop on Parallel and Distributed Algorithms，M.Cosnard et al.Eds.，Amsterdam，Elsevier Science Publishers，1989:215－226.