无线传感器网络同步算法的研究与探讨

3 萤火虫同步算法和梯度同步算法
前面的时间同步技术都是基于时间信息交换的同步技术，然而在大规模的无线传感器网络中，存在同步误差会随着跳距而积累的问题和可拓展性需求等问题。萤火虫同步技术和协作同步技术是为了实现节点的同步性，即使节点的某些周期性动作具有相同的周期和相位，例如使一群萤火虫同步闪烁并且闪烁周期相同。1990年，Mirollo和Strogatz在Peskin模型的基础上提出了更一般的脉冲耦合振荡器模型(后简称为M＆S模型)。在此模型中，振荡器使用状态变量x来描述，x的变化服从函数f(φ)，其中f是一个[0，1]到[0，1]的光滑单渊递增上凸函数，φ是相位变量且满足(T是同步周期)。Mirollo和Strogatz从理论上证明了在M＆S模型下，多个耦合振荡器系统在几乎所有的初始情况下都能够达到同步，并在无线多跳网络测试床Gains上实现了M＆S模型的萤火虫同步算法。
麻省理工学院的Rui Fan、Nancy Lynch两位作者第一次提出了GCS梯度同步算法。在移动自组织网络中往往是邻居节点联系比较密切，而相距较远的节点很少交换消息，因此相距较远的节点可以允许较大误差。如数据融合中，具有相同父节点的子节点需要精确的同步，但是较远的节点不是同一个父节点，可以允许误差大一些。作者就是根据这一特征提出了梯度同步算法。在通常的时间同步算法的基础上，假设两任意节点i、j，f(dij)为节点i和节点j之间的最大时钟差，时钟记为。信息从节点i传到j的传播时间为0到dij，dij为节点i到节点j的距离。D=maxijdij为网络的直径。GCS提出了两要求：

计算出时钟漂移的最低边界满足f(D)=Ω(d+lgD／lg lgD)，这也就是说节点之间的时钟漂移不只与两个节点问的距离有关，还与整个网络的规模有关，越近的节点同步效果越好，反之越差。GTSP(Gradient Time Synchronization Protocol)协议中，每个节点通过接收邻居节点的时间来修正自己的时钟，整个网络无需建立一个拓扑树结构，也无需参考节点，主要是实现直接的邻居节点间直接的高精度的同步，同时考虑时间漂移和偏移补偿，漂移补偿采用式(5)。通过这种补偿机制，所有节点的逻辑漂移将趋近值Xss；时钟偏移补偿采用式(6)。协议的作者在Mica2节点上进行了仿真，通过20个节点实验，采用Mac层时间戳技术，得出邻居节点之间的平均同步精度达到4．0μs，整个网络的平均同步精度达到14．0μs。


4 分布式时隙同步算法
主从同步方法是网络中所有的节点与参考节点保持时间同步，对参考节点依赖性高，且同步的误差随着跳数而累积；分布式同步则利用网络中所有节点的彼此时间信息进行调整，不依赖任何特殊的节点，且不会有误差的累积，因此更加适合于大型的多跳自组织的无线传感器网络。分布式时隙同步算法利用了网络中邻居节点的时隙偏差值来计算时隙的调整量，实验证明该算法收敛速度快，平均每个节点的计算量小，非常适合于移动自组网的无线传感器网络终端节点的运行。采用固定的时隙调整时，根据节点间时隙基准是超前还是滞后来调整时隙基准。基于分布式一致的无线传感器网络的时间同步协议的收敛和加速问题研究中，将分布式一致的收敛和加速问题映射到马尔科夫链的状态转移过程，但是排除了连通度对收敛速度的影响，得出收敛速度与节点邻居数和网络规模有关的结论，并通过100个节点组网实验得出了可以降低25％的迭代数的结论。