黄 晓，罗树浩

(中山大学信息科学与技术学院，广东 广州 510006)

在无线传感器网络(Wireless Sensor Networks, WSNs)[1]中，节点搭载各种传感器，通过无线传输将监测的数据传输到汇聚点(sinks)。无线传感器网络的节点具有体积小、低能耗、低成本和自组织等特点，在环境监测、工业自动化以及人员监控管理等领域得到广泛应用[2]。

时间同步(Time Synchronization)在无线传感器网络的应用中有关键的作用[3]。当观测到事件发生时，多个节点需要将事件的时间以及空间信息进行数据融合(Data Fusioning)，必须维护一个与全网一致的时钟。另一方面，精确的时间同步可降低网络的能耗，例如在周期性工作的网络中，所有节点在空闲周期同时关闭接收机进入休眠状态，等待工作周期到来后唤醒，进行数据的传输。此外，在应用信标(Beacon)机制的传感器网络中，以及采用TDMA(Time Division Multiple Access)等协议避免碰撞，都需要精确的时间同步。

无线传感器网络时间同步的首要目标是最小化同步误差。但是由于节点存在能量、运算以及通信能力方面的局限性，时间同步必须能量高效(Energy Efficient)。实际上，消息传输所需要的能量开销远大于运算所需开销，所以时间同步过程中应尽量减少同步消息的传递，同时可保证其他数据的有效传输。

1 研究现状

时间同步问题早年在分布式系统已有相关研究[4]。随着无线传感器网络的发展，针对其所进行的同步研究也有丰富的成果。根据同步过程的差异，将现有无线传感器网络时间同步算法划分为集中式和分布式两类。

集中式同步算法，是指在网络中存在一个根节点(root)，向全网提供一个标准的时钟，并发起同步流程。RBS(Referenced Broadcast Synchronization)是经典的集中式同步算法[5]，通过同层节点交换时间戳的方法抵消发送时延，达到较高同步精度，但难以在多跳网络中应用。TPSN(Timing-sync Protocol for Sensor Networks)将同步分为两个阶段[6]，层次发现阶段每个节点获取层次属性，同步阶段每个节点都与父节点进行双向的消息交互从而同步，因此消息开销大。为解决开销问题，Kyoung-Lae等[7]提出了成对广播同步，一对节点双向交换消息同步，而其共同邻居能监听到这些消息并完成同步。King-Yip等[8]将成对广播同步应用到多跳网络中，采用分布式的方法并结合贪婪算法动态选择同步对，大大减少了同步过程中消息开销。为提高鲁棒性，RTSP(Recursive Time Synchronization Protocol)算法实现根节点的动态选举[9]，通过下层节点迭代式向上层请求同步，但延长了同步过程从而增加了误差。

相反地，分布式同步算法不存在根节点，同步在各个节点间异步进行，整个网络收敛于虚拟全局时钟。萤火虫同步算法结合了生物现象中的激发模型[10]，节点通过观测脉冲信号以及调整脉冲信号发射间隔，与周围节点保持同步。ATS(Average TimeSync)算法用随机矩阵方程的角度来解决同步问题[11]，但仅适用于网络规模较小的情况。一致时钟同步算法(Consensus Clock Synchronization)使用置信赋权平均方法对邻居时钟戳赋权重从而补偿本地时钟[12]，算法的收敛速度较快。RGCS(Robust Gradient Clock Synchronization)算法通过滑动平均赋权的方法[13]，更新本地的时钟，算法的鲁棒性较好。

分布式算法普遍存在着收敛时间长、适用网络规模受限等缺点，集中式算法虽然在应对网络动态变化(如根节点失效)方面稍显不足，但同步精度高、收敛快速。本文研究了集中式同步算法，在层次发现阶段，采用基于最大互邻集合的分布式策略获取精简的同步集，降低节点能耗和网络开销。在硬件平台和软件仿真平台进行的实验，证明了算法的有效性。

2 单向时间同步模型

2.1 单向时间同步和双向时间同步

节点同步时，由作为主节点的某个邻居提供所需的时间戳信息。单向同步是相对于双向同步而言的，节点不必进行双向的消息交互，只需接收主节点的时间戳即完成同步，消息单向传播。一般的同步算法(如TSPN)采用双向同步策略[6]，节点A发送同步消息S1给B，而B回复S2给A，同步消息中携带相关时间戳，过程如图1(a)所示。节点A获取四个时间戳，通过(1)式可补偿相位偏移Δ，利用线性回归等方法补偿速率漂移。

图1 双向同步(a)和单向同步(b)

Δ=[(T2-T1)-(T4-T3)]/2

(1)

文献[14]提出了一种新的时间戳标记方法，如图2所示。B生成同步消息并打开发射机，在发送帧首定界符SFD完毕的瞬间，硬件系统捕捉硬件时钟的值T1并保存在寄存器中，此时消息其他字段正在传输。B立即将T1嵌入消息末端，通过当前消息发送出去。A在收到消息的SFD时，也捕捉到本地时间戳T2，并嵌入到消息的末端，交给上层处理。A由(2)式即可完成相位偏移补偿，过程见图1(b)。

Δ=T2-T1

(2)

图2 单向同步原理

这种时间戳标记方法脱离了协议栈的层次结构，由硬件系统独立完成，因此比MAC层标记方法的精度更高。单向同步过程引入了消息在空气中的传播时延d，由此带来的误差可忽略[6]，故认为可取得与双向同步相同的精度。另外，节点只需广播单个时间戳即可实现多个邻节点的同步，显著降低了同步通信开销。

2.2 单向时间同步数学模型

由于单向同步可达到双向同步的精度，而且具有降低消息开销、节省同步节点能耗的优势，故本文选择单向同步作为研究对象。同时由于无线传感器网络的能量资源少，运算能力弱，故本文算法的目标为降低能量开销，降低算法复杂度，提高同步成功率。

同步分成两个阶段。第一阶段为层次发现阶段，寻找包括根节点在内的所有广播节点组成的同步集，同时控制同步集节点数量以降低同步消息开销。第二阶段为同步阶段，同步消息自根节点起经同步集节点向外传播，其余节点监听，实现全网同步。本文使用单向同步技术实现全网同步，建立寻找最小同步集的数学模型。

设节点集合为Ψ，其元素数量为‖Ψ‖=N。对于任意两个节点∀ψi,ψj∈Ψ，定义其连通性cψiψj

(3)

设同步集为Ω⊆Ψ，根节点属于Ω。Ω中每个节点都有一个层次属性，表示与根节点的最短拓扑距离，根节点的层次规定为0。对于任意两个节点∀φp,φq∈Ω，定义变量λφpφq表示两者的层次关系

(4)

对于非根节点的∀φq∈Ω，Ω至少存在一个节点与其互为邻居且是其上层节点，从而同步消息可由根节点开始沿广播节点向外传播

∀φq∈Ω,φq≠0,p≠q

(5)

为确保网络中所有节点可监听到同步消息，须保证每个节点至少与一个广播节点互为邻居，即

∀ψi∈Ψ,ψi≠φp

(6)

目标是求取符合上述条件的具有最小元素数量的同步集Ω

argminΩ‖Ω‖

(7)

将网络看作一个无向连通图，寻找最小同步集的问题等价于构造一个以根节点为树根的非叶子节点最少的生成树，即最多叶子生成树(MLST, Maximum Leaf Spanning Tree)[15]，是一个NP-HARD问题，可利用集中式优化算法求解。集中式算法通过节点把拓扑连接信息传输到汇聚节点，求取最优解，再将结果分发给每个节点。这种方法对网络链路造成较大负荷，当传输过程发生消息丢失时会造成结果错误。本文研究了更具实用意义的分布式算法，节点通过有限数量的消息交互，判断自身是否广播节点。

3 基于最大互邻集合的单向同步

可相互传输消息的两个节点之间存在无线通信链路，而距离对链路通信质量存在影响。节点接收消息时，采样到对应无线链路的LQI(Link Quality Indicator)参数，例如ZigBee采用接收信号强度指示值(Receive Signal Strength Indicator, RSSI)作为LQI。在理想情况下，当两个节点之间没有障碍物时，LQI值随距离的增大而减小；当障碍物存在时，以节点为中心向障碍物延伸的方向上，LQI值虽呈规律性变化，但距离越远LQI值越小的趋势依然成立。因此，在实际环境中节点可通过消息的LQI值来获知邻居节的大概空间信息。

单向同步算法分为两个阶段，本文主要详述层次发现阶段，流程如图3所示。

图3 单向同步算法流程图

Step 1 根节点启动同步流程，广播一跳层次发现帧P_DISCOVERY。在层次发现过程中的所有控制和数据帧都包括以下几个公共域：

MsgTpyeSeqSourceIDSourceLevel

其中，MsgTpye为帧类型；Seq为层次发现帧序列号，根节点可增大Seq发起新一轮层次发现；SourceID为源节点的ID号，网络中每个节点都有唯一的ID，根节点为0；SourceLevel是源节点的层次，根节点为0，子节点的层次为父节点加1。此外，节点保存一个状态参数来指示工作状态，初始时为S_INIT。

根节点置状态为S_FINISH，表示层次发现阶段结束。

Step 2 节点接收到i-1层节点的P_DISCOVERY帧，若状态为S_INIT则接收该帧。节点收到多个帧时，选择最小的ID作为父节点并记录其ID，并把自身的层次修改为i。节点根据帧的LQI值判断：

1)LQI>阈值L1，表明节点离其父节点较接近，则置状态为S_FINISH，完成层次发现并退出；

2)LQI<=L1，表明节点处于父节点广播范围的边缘处，则置节点状态为S_EXCH_NEIGHBOR，成为第i层候选广播节点，广播P_EXCH_NEIGHBOR帧，帧中携带一跳邻居信息。节点的邻居信息在网络层周期性的邻居扫描可获取，不需要额外的同步消息开销。

候选广播节点同时接收同层邻居节点的P_EXCH_NEIGHBOR帧，等待一段时间确保接收完毕。通过准确的时序控制，可确保同一层次的所有节点在同一时间段内进行同步。候选广播节点保存同层邻居集合Ns的邻居表及LQI值。

Step 3 第i层候选广播节点在同层邻居集合Ns中计算其最大互邻集合Gmax和最近邻集合Imax。

定义节点互邻集合G，G中任意节点np和nq互为邻居；则节点的最大互邻集合Gmax为其所在K个互邻集合中元素数量最多的一个，即

Gmax=argminGk‖Gk‖,1≤k≤K

(8)

定义节点最近邻集合Imax，表示同层邻居集合Ns中LQI值大于阈值L2的所有节点的集合，即

(9)

Gmax和Imax由候选广播节点遍历搜索Ns的邻居表获得。为降低搜索过程的运算量，可将Ns按其ID号的大小排序后存储。对排序后的Ns搜索Gmax，运算复杂度为O(nlogn)，其中n为Ns的元素数量且值较小，故运算可在资源受限的传感器节点上进行。获取Imax只需搜索Ns的LQI值即可，运算复杂度为O(n)。另外初始化计数值CG=0和CI=0。

Step 4 候选广播节点退避等待随机时间trand，节点状态修改为S_BACKOFF，在此期间接收Ns中节点发送的P_ABANDON帧。这些邻居节点称作放弃节点，说明该节点放弃成为广播节点，在同步阶段只作监听，不发送同步消息。候选广播节点将放弃节点ID写入集合Sabandon，并判断：

1) 若放弃节点nA∈Gmax，则使计数值CG=CG+1，即更新记录最大互邻集合中放弃节点的数量；

2) 若放弃节点nA∈Imax，则使计数值CI=CI+1，更新记录最近邻集合中放弃节点的数量。

Step 5 候选广播节点随机等待时间trand到达，分析是否成为广播节点。

在最大互邻集合Gmax中，任意节点广播消息集合内其余节点都能监听到，因此Gmax中的所有节点处于一个相对较小的空间范围内。若Gmax中均为广播节点，则同步时广播的同步消息覆盖范围有较大面积的重叠，造成不必要的能量和网络开销。实际上，只需在Gmax中选取部分广播节点，并使其分布合理，那么同步覆盖范围约等于Gmax中所有节点的同步覆盖范围。

候选广播节点作以下判断：

1)在trand内收到Gmax中所计数的放弃节点数量为CG，若CG<‖Gmax‖-B1，在Gmax中搜索，若存在未放弃的节点，且该节点为最近邻集合Imax中节点，即：

(Gmax-Sabandon)∩Imax≠φ

(10)

则放弃成为广播节点，广播P_ABANDON帧通知邻居节点；若上述条件不满足，则进入2)。

2)在trand内收到Imax中放弃节点数量为CI，若CI<‖Imax‖-B2，即Imax中存在过多候选节点，则放弃成为广播节点，同样广播P_ABANDON帧；否则，进入3)。这个条件保证了Imax中保留不多于B2个同步节点，因为集合内的节点进行同步广播所覆盖的有效面积会有大部分重叠，这是不必要的。

3)若CG<‖Gmax‖-B3，说明Gmax中潜在的广播节点数量超过最大值B3，强制放弃成为广播节点，广播P_ABANDON帧。否则，成为同步集中的广播节点。为了控制同层节点在同一时间段内进行层次发现，保证算法流程准确，加入一个时序控制策略。广播节点在此前退避了随机的周期trand监听同层邻居节点的P_ABANDON帧，变量trand由其本地保存；同时节点希望与同层的广播节点在尽量接近的时刻广播P_DISCOVERY帧告知下层节点。因此，设定每层的层次发现过程的执行周期为T，则广播节点在分析完毕后应该等待时间(T-trand)后，再广播P_DISCOVERY帧，进入Step 6。

同层候选广播节点邻居收到P_ABANDON帧，按Step 4处理。上述的B1,B2,B3为可变参数，根据实际网络情况调整其值大小使同步达到最佳状况。

Step 6 第i层候选广播节点广播P_DISCOVERY帧，置状态为S_WAIT_REGISTER，此时并未最终成为广播节点。节点开启定时器，在设定时间内等待子节点注册。状态若为S_INIT的邻居节点可能收到多个P_DISCOVERY帧，选择ID最小的父节点，进入层次发现流程Step 2，并立即单播一个注册帧P_REGISTER给父节点。当父节点收到了该帧，正式成为广播节点。这个策略防止了子节点有多个潜在的父节点时，造成某些广播节点“悬空”，即实际上没有子节点的情况。

另外，第i层放弃节点A广播P_ABANDON帧，状态为S_INIT的邻居B收到后，将A的ID存储起来，并开启定时器等待tabandon时间。若在此期间，B没有收到任何的P_DISCOVERY帧，说明了自身在层次发现阶段被遗漏了。此时B发送P_INFORM帧告知该放弃节点A，A重新成为广播节点，发送P_DISCOVERY帧。

在实际场景中，网络边缘可能存在少量的节点，其仅有的邻居在Step 2的LQI阈值判断时放弃成为广播节点，导致这些节点被遗漏从而同步失败。这种极端的情况，可应用简单的策略解决。具体在同步阶段，被遗漏节点经过长时间没有监听到同步消息，确认同步失败，向邻居节点提出同步请求，等待其回复同步消息即可。

4 实验与仿真

4.1 单双向同步对比

为验证单向同步策略的同步精度，本文进行了相关的实验，并与双向同步技术对比。实验在CC2530为核心的ZigBee平台上进行，协议栈为TI的Z-Stack2.5，利用两个节点进行单跳的时间同步。单双向同步各进行8次实验，并使用双踪示波器测量同步误差，结果见表1。硬件实验数据表明，单向同步的平均同步误差约为12.5 μs，双向同步约为11 μs。由此可知利用时间戳捕捉技术进行单向同步，可达到与双向同步一致的精度，而结果的差异来源于同步时引入的系统随机误差，并非同步方法所导致。

表1 单向与双向同步误差对比

4.2 大规模网络实验

在单向同步的基础上，本文提出了基于最大互邻集合的同步算法。为验证算法的有效性，在NS2(Network Simulator 2)软件平台上进行大规模网络下的仿真，同时使用文献[8]中的算法进行对比。文献[8]提出了基于双向同步的成对广播时间同步算法，控制同步消息开销，与本文算法目标一致，新颖且具权威性。本文实验中，参数取值分别为B1=1,B2=2,B3=3，实验结果见图4至图7。

图4 网络规模100～400，同步集节点数量和同步消息开销

图5 网络规模250，同步集节点数量和同步消息开销

图6 网络规模250，执行算法的消息开销

图7 网络规模250，成功同步节点比例

图4是网络节点数从100至400范围变化的实验结果，平均节点邻居数大约保持在10个，即节点密度不变。在不同网络规模下，本文的算法得到的广播节点的数量均比文献中算法结果少。在同步阶段，本文算法的广播节点只需发送一个同步消息，同步消息数量与广播节点数量一致；而成对同步需要消息交换，因此消息开销是同步集节点数量的两倍。本文算法在同步阶段平均消息开销比单向同步算法低61.43%，在降低能耗方面更有效。

图5中是网络节点数固定为250个、节点密度变化时的实验结果。本文算法的广播节点数比文献中方法同步集节点数量平均少20.74%，消息开销节约60.37%。与网络规模变化时相似，在不同网络密度下本文的方法在节省网络开销和节点能耗方面更优秀。

图6是节点密度变化时，在层次发现阶段算法执行所需要传递的消息数量对比情况。表明本文方法所产生的平均消息开销为文献中算法的46.8%，远小于后者。文献中算法在层次发现流程中，节点选择下层同步子节点需要多次的消息交互，而本文算法中节点只需固定数量的消息开销。

图7是节点密度变化时成功同步节点数量占网络节点数量的比例。由于消息碰撞等原因，消息传递时可能会丢失少量帧，节点获取邻居信息不准确，从而造成少量节点被遗漏的情况。由于在本文中加入了遗漏节点处理、时序控制、放弃节点重新同步等策略，故同步算法更有效，成功同步节点的比例为99.07%，额文献中方法缺乏相关处理，比例为96.76%。

在运算时间复杂度方面，本文算法在搜索最大互邻集合时的运算复杂度为O(nlogn)，同层邻居获取最近邻集合为O(n)，n为节点的平均同层邻居数，而其余的步骤均为O(1)。在文献中的算法中，获取并排序所有低层邻节点的邻居表过程的复杂度为O(mlogm)，其后搜索最大共同邻居集合和sync_num则为O(n2)，筛选最大的sync_num为O(m)，且需多次迭代，最后根据not_MAX消息作出的处理的复杂度为O(n*m)或O(1)，其中m和n分别为同层和上层邻居数。对比可知，本文算法的运算复杂度更低，流程更简单。

5 结 语

本文对无线传感器网络的时间同步问题进行了研究。利用单向同步的时间戳标记技术，将时间同步转化为构造最小同步集问题，并建立数学模型，提出分布式的算法求解。算法通过在层次发现阶段节点生成最大互邻集合和最近邻集合，减少同步集节点数量。加入子节点向父节点注册、层节点监听放弃帧以及时序控制等策略提高了算法性能。ZigBee硬件平台的实验证明了单向同步可达到较高精度；NS2平台的仿真表明本文方法在不同网络规模、不同网络密度下可降低同步消息开销，提高成功同步节点比例，能更有效地解决时间同步问题。

参考文献：

[1]AKYILDIZ I F, SU W, SANKARASUBRAMANIAM Y, et al. Wireless sensor networks: a survey[J]. Computer Networks, 2002, 38(4): 393-422.

[2]ARAMPATZIS T H, LYGEROS J. A survey of applications of wireless sensors and wireless sensor networks [C]∥ Proceedings of the 13th Mediterranean Conference on Control and Automation, Limassol, 2005: 719-724

[3]SOMMER P, WATTENHOFER R. Gradient clock synchronization in wireless sensor networks[C]∥ Information Processing in Sensor Networks, San Francisco, 2009: 37-48.

[4]LISKOV B. Practical uses of synchronized clocks in distributed systems[J]. Distributed Computing, 1993, 6(4): 1-9.

[5]ELSON J, GIROD L, ESTRIN D. Fine-grained network time synchronization using reference broadcasts[C]. Proceedings of the 5th Symposium on Operating Systems Design and Implementation, New York, 2002, 36: 147-163.

[6]GANERIWAL S, KUMAR R, SRIVASTAVA M B. Timing-sync protocol for sensor networks[C]∥1st International Conference on Embedded Networked Sensor Systems, New York, 2003: 138-149.

[7]KYOUNG-LAE N, ERCHIN S, KHALID Q. A new approach for time synchronization in wireless sensor networks: pairwise nroadcast synchronization[J]. IEEE Transactions on Wireless Communications, 2008, 7(9): 3318-3322.

[8]KING-YIP C, KING-SHAN L, YIK-CHUNG W, et al. A distributed multihop time synchronization protocol for wireless sensor networks using pairwise broadcast synchronization[J]. IEEE Transactions on Wireless Communications, 2009,8(4): 1764-1772.

[9]MUHAMMAD A, TAREK R S. RTSP: an accurate and energy-efficient protocol for clock synchronization in WSNs[J].IEEE Transactions on Instrumentation and Measurement, 2013, 62(3): 578-589.

[10]GEOFFREY Werner-Allen, GEETIKA Tewari, ANKIT Patel, et al. Firefly-inspired sensor network synchronicity with realistic radio effects[C]∥ Proceedings of the 3rd International Conference on Embedded Networked Sensor Ssystems, New York, 2005: 142-153.

[11]LUCA Schenato, GIOVANNI Gamba. A distributed consensus protocol for clock synchronization in wireless sensor network[C]∥ Proceedings of the 46th IEEE Conference on Decision and Control, New Orleans, 2007: 2289-2294.

[12]MAGGS M K, O’KEEFE S G , THIEL D V. Consensus clock synchronization for wireless sensor networks[J]. IEEE Sensors Journal, 2012, 12(6): 2269-2277.

[13]PINHO A C, FIGUEIREDO D R , FRANCA F M G. A robust gradient clock synchronization algorithm for wireless sensor networks[C]∥ Communication Systems and Networks (COMSNETS), 4th International Conference on, Bangalore, 2012: 1-10.

[14]COX D, JOVANOV E, MILENKOVIC A. Time synchronization for ZigBee networks[C]∥Proceedings of the 37th Annual Southeastern Symposium on System Theory (SSST ’05), 2005:135-138.

[15]BONSMA S PAUL , TOBIAS B, GERHARD J. A faster FPT algorithm for finding spanning trees with many leaves[C]∥Mathematical Foundations of Computer Science, 28th International Symposium, Bratislava, 2003: 259-268.