虚拟时钟指数逼近的无线传感器网络时钟同步协议

　　提出了一个基于虚拟时钟指数逼近的无线传感器网络时钟同步协议，采用一个虚拟时钟作为全网同步的基础，从而实现全网同步。由于采用虚拟时钟，使得各节点进入网络时有了统一的标准，对时钟扭曲和偏移采用指数逼近的方法，在相差较大时调整快，提高了同步效率。仿真数据证明，本协议能有效地提高同步效率，并适应于不同的网络拓扑。

　　引言

　　WSN时钟同步［1］关键问题主要有两个方面：一是标准的确立，即有一个时钟作为全网基准，不管是事实上存在的时钟，还是虚拟的时钟；二是标准的共享，即各节点都按照标准来调整自己的工作状态。目前WSN时钟同步主要集中于两个方面：集中式和分布式。集中式如TPSN［2］、RBS［3］、 FTSP［4］。分布式同步如ATS［5］、CCS［6］、GCS［7］。

　　本文采用一个虚拟的时钟作为全网同步的基准，所有节点在进入网络后逐次逼近一个统一的虚拟时钟，逼近过程采用基于本地时钟的指数逼近方式，最终实现同步。

　　1 近期工作

　　WSN中时钟同步的主要方法如下，前三者为集中式同步，后三者为分布式同步方法：

　　TPSN（TimingSync Protocol for Sensor Networks）［2］是用于WSN中时钟同步的技术，主要包括标准发现阶段和同步阶段。发现阶段将整个网络划分为树状层次拓朴，根结点是首要结点，然后采用普通的握手协议实现全网同步。TPSN利用MAC层时间戳减少信息传输的延时和提高同步准确性，收敛速度随着网络规模的扩大线性增长。该算法的限制是，当根结点或者父结点失效时，需要有相应的策略去选择新的根结点或父结点。同时由于地理上相近的节点，并不一定能够在实际中成为树状网络中的邻近节点，因此降低了同步性能。

　　RBS（Reference Broadcast Synchronization）［3］着眼于提供基于信标信号单跳范围内的节点同步方案，其最大的贡献在于去除了信息传输过程中的两个影响因素——传输时间和接入时间，即消息花在非时钟同步上的时间最少。RBS采用最小方差线性回归的方法补偿时钟扭曲，收敛速度随着网络规模也呈线性增长趋势，使用信标节点使得传输易受到干扰，同时也会因为节点移动而导致时钟同步失败。

　　FTSP（Flooding Time Synchronization Protocol ）［4］是一个自治、多跳的同步协议，通过无线栈中低层无线消息中的时间戳，完全消除了CSMA协议中的接入时间，从而提供了较高的准确性。FTSP通过线性回归补偿部分节点的时钟扭曲能够得到更高的准确性。FTSP还采用了几种机制来提高节点和链路失败后的鲁棒性，比如周期性地采用洪泛同步方式同步节点时钟，由于FTSP对动态拓扑的适应性和对不同时钟扭曲的修正能力，成为事实上的WSN时钟同步标准，但和TPSN一样，FTSP也无法消除本身收敛速度慢等限制。

　　GCS（Global clock synchronization）［5］中，每个节点依次向邻居广播自己的同步申请，邻居依次回答并包含自己的本地消息，处于本次接收中心的节点从时间戳中计算一个平均值并向邻居广播，从而得到一个基准，一直重复，直到全网同步，这种分布式的策略无法补偿时钟扭曲，不能从根本上解决时钟同步的效率问题。

　　ATS（Average Time Synchronization）［6］使用两种一致算法以调整补偿参数，聚集所有节点于一个稳定的虚拟时钟。ATS分为两个阶段，第一阶段网络中各节点广播一个本地时间戳，用以估计相互间的时钟扭曲率，然后广播节点自身相对一个虚拟（实际存在）时钟扭曲率的当前估计，并接收别的节点的扭曲估计，从而调整它们实际的时钟。在消除偏移错误时也采用同样的原则，这种分布式协议，收敛速度较慢，且与网络拓朴结构有关，还需要进行算法改进，以提高收敛速度和对网络结构的自适应能力。

　　CCS（Consensus Clock Synchronization）［7］利用平均一致算法补偿时钟偏移，通过在每次偏移补偿中消除累积偏移错误，节点能够从一致时间中获得自己的时钟扭曲，这一信息可以用于自身的纠正，从这一意义上说CCS是一种增强型的ATS，提供了一种分布式的解决方案，其缺点仍然是收敛速度不快。

　　本文的方法和CCS相近，是一种分布式的利用节点本地信息修正时钟参数的算法，不同之处在于采用了指数方式逐次逼近的方式补偿时钟扭曲和偏移参数，这样能像集中式那样收敛速度快，同时随着网络规模的增长收敛时间呈线性变化，且在消息丢失和节点失效时具有较高的可靠性。

　　2 数学准备

　　为实现最终结果全网各节点逼近一个统一的值，合理的策略是找到一个基准时钟，对于相差较大的节点调整大，相差较小的节点调整小，保证向一个统一的时钟逼近，最终实现同步。

　　为实现节点时钟与基准时钟相差越大，所需的修正参数就越大。本算法采用修正参数与平均值的差值大小指数对应关系，即越接近平均值的节点偏移，调整的修正参数越小。指数方式的调整方式能够优化节点调整的效率和可靠性，从而得到更佳的收敛速度和可靠性，设第某节点本身的偏移值为β，所需要逼近的值为 β-，λ=β-β-，设调整因子为γ=min（β，β-）max（β，β-），显然0≤γ＜1，则某节点所需调整的参数为：

　　

　　调整因子和修正值关系如图1所示，当调整因子越大，表明与标准值越接近，所调整的比例便越小，即节点与标准值差值λ为0时，节点不需要对自己的值作任何改动，而节点自身值与平均值相差越大时，节点所需调整的参数越大。在实际执行时，可以设置λ′的一个阈值RT，使得需要调整的数值在某一范围内时，即 λ′小于某一规定值时，节点可在一定时间内不调整，这样可以在很大程度上避免由于某个新的节点参数与别的节点参数相差太大时，导致整个网络节点调整的情况。RT值的设置与网络规模对同步收敛速度的要求有关。

　　

　　图1 调整因子和修正值关系图

　　3 算法实现

　　3.1 时钟模型

　　WSN中各节点的时钟主要包括一个统一的基准时钟，一个相对于基准时钟的偏移，和由于时钟频率不一致而导致的扭曲。定义c（t）为一个参考时钟，是一个统一稳定的基准值。每个节点有自己的时钟，是一个关于t的函数ci（t），每个节点的本地时钟相对基准时钟的偏移是指由于长期累积而导致的时钟不一致，扭曲是指由于石英晶体振荡器振荡频率不一致，从而导致了时钟与基准时钟之间存在差别。

　　设两个节点的时钟分别为ci（t）和cj（t），如果时钟在时间t完全正确，则ci（t）＝cj（t）＝c（t），但是在实际中两个时钟往往是不相等的。这是由于晶体振荡器本身技术原因和外部工作环境（如温度、压力）等因素引起的，因此，t时刻每个节点的时钟模型为：ci（t）=αit+βi，其中αi为晶体振荡器自身频率的不一致而带来的扭曲，βi为时钟长期积累的偏移。

　　为达到时钟一致，最关键的问题是使得任何节点的ci（t）＝c（t），即补偿时钟的扭曲αi和时钟偏移βi，在任何时刻各节点的时钟不再偏移，且振荡频率也完全一致。

　　3.2 算法实现

　　TSMA要达到的目标是内部一致。在每个同步循环，算法更新每个节点的补偿参数，通过这样的方式使时钟达到一致：limt→∞ci（t）=cv（t）。其中cv（t）是本算法的虚拟时钟，虚拟时钟并不是一个现实中存在的时钟，而是所有节点以之为基准的一个时钟，是由本算法在运行过程中产生的。虚拟时钟有相对于实际时钟的扭曲率和相对偏移。各节点对本节点扭曲和偏移进行补偿，从而同步于虚拟时钟，实现全网同步。

　　设虚拟时钟为cv（t）=α·t+β，为使得各节点时钟最后同步于虚拟时钟，需要采用修正参数，设对于扭曲的修正参数为α′，对于偏移的修正参数为β′，则运行过程中，通过修正参数使得时钟保持一致的条件为：limt→∞（α′ci（t）+β′）=cv（t）=α·t+β，即limt→∞（α′ αit+α′βi+β′）=α·t+β，由此可得到修正参数为：

　　

　　为得到补偿各节点的时钟扭曲和偏移，每个节点在算法执行周期内完成对两种参数的修正。修正主要包括两个过程：第一个过程为扭曲修正，通过修正扭曲值使得节点与虚拟时钟频率一致；第二个过程为偏移修正，通过修正偏移值确保全网时钟同步。

　　3.2.1 扭曲修正

　　扭曲修正的目的是确保时钟在相同的振荡频率下工作，即limt→∞α′αi=α。对扭曲参数的修正采用指数逼近的方式，以将所有的时钟扭曲趋近于α，每个节点执行的算法如下：

　　① 运行同步算法前，节点设置扭曲估计αi为１，同时准备搜索邻居节点的时钟扭曲信息。

　　② 由于各节点并不一定知道邻居节点的存在，在节点广播自己的时钟信息时，有可能别的节点也在广播时钟信息，从而导致广播失败，因此在MAC层需要一个类似CSMA/CD的协议，以确保各节点能正确广播自己的时钟信息。

　　③ 设共有n个节点，第i（1≤i≤n）个节点存储并广播自己的时间信息（αi，Ti），其中Ti为本节点当前时间值，由于节点距离和传输速度是已知的，所以接收到广播的节点根据Ti确定接收时的时间是可行的。

　　④ 节点i收到第j（1≤j≤n）个节点的广播包，包含了节点j的时间信息（αi，Tj），如果第j个节点是第１次出现，则节点i只存储节点j的时间信息，直到收到节点j的下一个时间信息（αj+1，Tj+1）。

　　⑤ 此时比较节点i和节点j的扭曲，计算R1=αi（Tj+1-Tj）和R2=αj（Ti+1-Ti），若R1》R2，则需要对节点i的扭曲率进行修正，设两者的差值为λi=αi-αj，调整因子为σ=min（αi，αj）max（αi，αj），设置扭曲率和校正值为λ′i=λi（e-eσ）（e- 1），设置修正值调整的阈值RT，当节点i首次出现λ′i低于阈值要求时不作调整，以避免部分失效节点重新进入网络时对邻居节点造成影响。则节点i新的扭曲值为

　　

　　则αi=α，同时保留最新的节点i和节点j的时间信息T，即Ti=Ti+1，Tj=Tj+1。

　　⑥ 节点重复步骤②～⑤，直到R1＝R2，两节点扭曲率一致，此时节点已经更新了自己的时钟扭曲率，只需要保持偏移一致，即可达到时钟同步。

　　3.2.2 偏移修正

　　修正完扭曲率后，需要对偏移进行修正，以达到节点时钟同步。修正偏移值的关键是找到合适的偏移值，使得各节点能够同步到一个统一的偏移值，从而统一于一个虚拟的时钟。设每个节点的偏移值为βi，1≤i≤n，则节点i在接收到邻居节点的偏移值后，很容易得到一个平均值β-1n∑ni=1βi，显然这一平均值即为要找的虚拟时钟的偏移值，当各节点同步于这一偏移值，便实现了全网时钟同步。由于部分节点的时钟偏移值较大，同时每次更新的节点为一跳内的节点，采用一次调整偏移值至平均值的方法并不能以最快的速度使得全网节点偏移同步，而采用逐次指数逼近的方式，对偏移相差较大的节点修正参数较大，偏移相差较小的节点修正参数较小，使得全网所有节点逼近统一的偏移值。本算法采用了如下步骤：

　　① 节点i首先估计自己的偏移值βi，1≤i≤n，并开始收听广播，和扭曲修正一样，广播已经考虑了冲突避免。

　　② 节点收集一跳内的邻居偏移值，得到偏移平均值β-1n∑ni=1βi。

　　③ 节点i计算与平均偏移值的差值λi=βi-β-，设调整因子为γi=min（βi，β-）max（βi，β-），显然0≤γi≤1，则某节点所需调整的参数为λ′i=λi（e-eγi）（e-1）。设置修正值调整的阈值RT，当节点i首次出现λ′i低于阈值要求时不作调整，以避免部分失效节点重新进入网络时对邻居节点的影响。新的偏移值为

　　

　　则βi=β，节点i采用指数逼近的方法，逐次向平均值逼近。

　　④ 节点i再次收听邻居节点广播，重复步骤②③，直到λi=βi-β-低于设定值，实现了全网同步。

　　由于指数逼近的方式在节点偏移相差较大时调整较大，节点偏移相差较小时调整较小，适用于网络中有新节点出现时导致偏移相差较大的情况。采用指数逼近方式后，与平均值误差较大的节点调整大，加快了收敛速度，与平均值相差小的节点调整小，控制了向邻居节点扩散偏移调整的范围。同时，在全网节点偏移一致后，指数逼近的方式使得节点调整幅度小，避免了由于某一个时钟节点失误而带来的大范围时钟偏移调整，保证了全网时钟同步的稳定性。

　　4 仿真

　　本文采用指数逼近的方式调整各节点时钟扭曲和偏移参数，使得各节点修正时钟扭曲和偏移，最终同步于一个统一的时钟，为显示算法有效性和可靠性，用 Matlab进行了仿真。仿真环境为在8×8的格状网络里放置64个节点，每个格子包含一个节点，节点处于每个格子的中央区域，设每个节点用于校准的晶振参考值是32 768 Hz，即一个振荡周期为30.5 μs，小于一个周期的时钟误差是无法识别的，因此用1 tick =30.5 μs来表示时钟误差的最小单位。每个节点的扭曲率服从平均值为１、方差为10-5的正态分布，节点的初始偏移在0～1000随机分布。具体得到：节点扭曲 ——平均值为1，方差为10-5的正态分布，即N（1，10-5）；初始偏移——在0～1000 tick间随机分布。

　　在运行过程中，每个节点运行扭曲和偏移的修正协议，网络中没有一个实际的基准时钟，而是在运行过程中逐渐收敛到一个统一的时钟，从而实现节点同步。

　　设同步每个循环周期为30 s，节点在每个循环期间随机广播自己的同步帧，节点的传输距离为2个单位，即节点距离相差不超过2时可以收到对方消息。为避免网络稳定运行时部分偏差较大的节点导致网络中大部分节点同时调整参数，仿真中对首次出现的调整参数低于10%的修正参数不作调整。为验证本算法的对多种网络拓扑的适应性，设置了不同的网络状况，以检验算法的有效性和可靠性。

　　图2演示了节点使用本算法在网络运行初期、稳定工作状态、部分节点忽然失效或主动停止工作时的性能。每个同步周期设置为30 s。仿真持续时间为30 min，分为A、B、C、D四个不同区域。区域A所有节点均工作，由于各节点运行本算法前时钟偏差较大，前3个同步阶段，节点根据收到的偏移值调整参数，偏移校正效果不明显，从第３个周期开始，节点开始补偿时钟偏移和扭曲，经过9个循环周期的补偿，所有节点到达同步状态，即任意两节点间的时钟偏差在10个节拍以内。在区域B的开始阶段，50％的节点选择随机关闭，又随机工作，一但一个节点打开，即开始运用本算法，因为采用指数逼近的方式，节点一但开始工作时即开始执行本算法，由于大部分节点已经同步，新加入的节点的时钟调整不会对已经同步的节点造成影响，由图中可以看出节点能够在开始工作后迅速进入同步状态。在区域C中，30％的节点停止工作。在区域D，这30%的节点开始工作，由于没有时钟调整，刚开始工作时与别的节点时钟无法同步，此时能够看到，各节点开始工作后时钟很快收敛，实现了全网时钟同步。

　　

　　图2 动态网络下时钟同步的性能

　　结语

　　从WSN时钟同步的发展趋势来看，随着WSN节点数量的增加，采用基于本地信息的分布式同步策略，能够提高WSN节点工作效率和稳定性。本算法在动态网络结构下实现了较快的收敛速度，未来的工作集中在网络稳定运行后如何减少由于时钟同步带来的非必要消耗，从而提高节点生存时间和网络生命周期。