一种等级化分布式时间同步算法.docVIP

一种等级化分布式时间同步算法 　　摘 要： 为了满足无线自组网中采用分布式TDMA组网所需的时间同步要求，提出了一种等级化分布式时间同步算法。该方法采用时间参考节点推选制度，实时更新参考节点，同时采用分层的时间等级和时间质量相结合使得在网的每个节点都能和自己周围最靠近时间参考点的节点进行对时同步，仿真实验结果表明，该方法能够提高同步精度，完全满足分布式TDMA无线自组网的时间同步要求。 　　关键词： 无线自组网； 时分多址； 分布式时间同步； 时间参考节 　　中图分类号： TN929.5?34 文献标识码： A 文章编号： 1004?373X（2013）17?0037?04 　　0 引 言 　　无线自组网（Ad Hoc Network）也称多跳无线网，是由一组带有无线通信收发装置的移动终端节点组成的一个多跳的临时性无中心网络，可以在任何时刻、任何地点快速构建起一个移动通信网络，并且不需要现有信息基础网络设施的支持，网中的每个终端可以自由移动，地位相等[1]。 　　时分多址（TDMA）是目前在无线自组网络中普遍采用的一种信道接入方法。TDMA信道访问需要维护一个公共的时间参考基准来实现无冲突TDMA通信，网络时间同步为一个基本要求[2]。因而网络同步技术是实现TDMA的关键技术之一。对于分布式网络而言，节点之间没有统一的时钟。而TDMA是要求统一时钟的，因此设计一种切实可行的同步策略非常重要。 　　本文针对分布式TDMA提出了一种基于质量的等级化分布式时间同步算法，采用时间参考节点推选制度，实时更新参考节点，同时采用分层的时间等级和时间质量相结合使得在网的每个节点都能和自己周围最靠近时间参考点的节点进行对时同步，提高了同步的精确性。 　　1 时间同步技术 　　定时同步技术的主要作用是使各节点的时间基准保持一致，各个节点保持同步，从而能以TDMA的方式使用公共的无线媒介。 　　目前，常用的TDMA定时同步技术主要有： 　　（1）高精度时钟法 　　各节点采用高精度的时钟如原子钟、铷钟等产生自己的时间基准。 　　高精度时钟法的优点是：精度很高，如原子钟1 μs/天，故几乎没有同步误差；没有网络的分裂和合并问题，协议简单，而缺点则是成本、体积和功耗较大。 　　（2）外时间基准法 　　利用GPS或北斗时标作为时间基准。GPS的时间精度已经达到了20 ns，因而在Ad Hoc网中可以利用GPS同步时钟来为每个终端提供同步[3]。 　　外时间基准法的优点是：精度高，实现简单；没有网络的分裂和合并问题，协议简单。其缺点则是网络的运行必须依赖于GPS或北斗时标信号，一旦时标信号不可用时，网络便无法运行[4]。 　　（3）分布式同步法 　　分布式同步有两个方式：一种是中心式的，即以某节点为中心，其他节点与它同步；另一种是互同步技术[4?5]。节点之间相互计算同步误差，利用数学迭代方法逐步收敛到同步位置上[6?9]。 　　分布式同步法的优点是：不依赖外部时钟源，抗毁顽存能力强；成本、体积和功耗较小。其缺点则是：由于传输时延、噪声干扰等因素，网络中存在较大的同步误差；网络存在分裂和合并问题，故协议较复杂。 　　比较上面三种同步方式，各种方式各有优缺点。但在追求低成本、不依赖外部信号支持的应用场合，为了支持多跳中继路由情况下的自组网TDMA接入，分布式同步法是最有效的同步方法。 　　2 基于质量的等级化分布式时间同步算法 　　2.1 算法描述 　　首先，对每个节点同步信息增加相应的时间参考点ID信息、时间等级信息和时间质量信息； 　　其次，根据各节点ID值的大小推选时间参考节点，以时间参考节点为中心向外扩散，构成逐级扩散的同步网络，并确定各节点的时间等级和时间参考点ID值，修改对应节点信息中的时间等级信息和时间参考点ID信息； 　　然后，时间参考节点定时广播对时和路由信息，路由信息包含有节点同步信息，各级节点分别与时间等级靠前的节点进行对时，并修改本节点的时间等级信息和时间参考点ID信息，同时开始本节点的对时间隔的计时，即时修改时间质量信息，完成时隙同步。 　　2.2 逐级扩散同步 　　逐级扩散同步的基本思想是以参考站为基准，逐级向下建立同步。同一同步组内组员按节点序号大小的顺序，采用不同起始时刻进行下一级同步组构建及维护。 　　如图1所示为分布式时间同步自组网拓扑示例。 　　0节点相当于同步基准站，它发送同步信息给它周围的邻节点1，4，5。1，4，5称为一级节点，也就是同一同步组的组员。按照以上思想，它们按序号大小用不同起始时刻构建相应的下一级同步组。于是1先向它的下一级节点发送同步信息，也就是向2节点发送同步信息，2成为二级节点。之后，4向它的下一级节点发送同步信息，也就是10，14和