基于平均场的分布式多跳无线网络时钟同步方法

技术领域

本发明涉及一种分布式时钟同步方法，特别涉及一种基于平均场的分布式多跳无 线网络时钟同步方法。

背景技术

分布式多跳无线网络，是一种特殊的无线移动通信网络，分布式多跳无线网络包 括无线传感器网络(WSN)、移动自组织网络(MANET)、车载网(VANET)、MESH 网以及分布式无线网络控制系统等。它不依赖于任何网络基础设施，具有很强的自组 织性、鲁棒性和抗毁性等特点，在军事、抢险、救灾及应急通信领域有着广泛的应用 前景。分布式多跳无线网络作为一种新型的无线网络，其应用领域越来越广泛。精确 的时钟同步是分布式多跳无线网络自身协议运行、节能管理、数据融合的必要前提条 件，分布式多跳无线网络中的节点只有保持时钟同步，才能协作完成相应的任务。因 此，时钟同步是分布式多跳无线网络的重要支撑技术，是网络运行和应用的必要基础， 它是执行大量应用程序的关键。如何设计时钟同步方案，使得全网中的节点具有一个 公共的时钟基准，即为分布式多跳无线网络中的时钟同步问题。

在分布式多跳无线网络中，如何实现时钟同步是一个难题。由于分布式多跳无线 网络有自身的局限性，比如：节点内部的硬件时钟受环境因素影响较大、能量受限、 节点运算能力有限、要求可扩展性、动态网络拓扑结构、不对称链路、无固定中心节 点等等，这些局限使得在分布式多跳无线网络中难以获得全网时钟基准、难以准确测 量节点之间的时钟偏差。这使得在分布式多跳无线网络中实现时钟同步有着很大的困 难，也使得传统的时钟同步方案不适合分布式多跳无线网络，必须研究分布式多跳无 线网络专有的时钟同步方法。

广泛用于传统网络的同步技术主要有GPS、NTP和IEEE1588。现有的分布式多 跳无线网络时钟同步研究主要从如何准确测量节点之间的时钟差和如何实现全网同步 这两个方面展开。

文献1“申请公开号是CN104122789A的中国发明专利”公开了一种高精度分布 式时钟同步时钟系统及方法，采用GPS与恒温晶振相结合的分布式同步方式，通过 GPS接收机模块解算出时间信息、定位信息并产生信号去校正恒温晶振模块所产生的 本地秒脉冲信号使得本地秒脉冲信号与信号同步，此方法需要的对硬件有较高要求， 成本较大，且不适合大规模分布式多跳无线网络，无法适用于动态拓扑。

文献1“申请公开号是CN104092528A的中国发明专利”公开了一种时钟同步方 法和装置，其基于PTP时钟节点设备，首先通过收发报文构建网络拓扑表，其中包括 发送各报文的各端口的优先级向量，根据各端口的优先级向量确定本设备是否为最优 时钟节点设备。此方法的缺陷在于当主节点损失时，重新指定或选举主节点会造成算 法性能急剧下降，影响协议正常工作，而且其需要维护节点的优先结构，开销较大。

发明内容

为了克服现有分布式时钟同步方法时钟基准难以确定的不足，本发明提供一种基 于平均场的分布式多跳无线网络时钟同步方法。该方法首先采用广播方式实现双向时 间戳交换，再将节点之间的时钟差的总体效果等价于一个平均场，基于空间马尔可夫 随机场建立网络的时钟同步模型，根据马尔可夫随机场与吉布斯随机场的等价性，通 过引入邻居系统和团势能，得到基于平均场伊辛模型的时钟同步能量函数，并在此基 础上给出采用能量最小化寻优的时钟同步算法，基于平均场模型的全网时钟分布式同 步算法。由于采用了基于平均场模型的全网时钟同步方法，基于平均场理论，通过节 点间的平均作用确定了全网虚拟时钟基准，解决了背景技术分布式时钟同步方法时钟 基准难以确定的技术问题，采用并行能量最小化的方法实现全网时钟分布式同步，具 有快速收敛、收敛时间稳定，成本开销低，对拓扑规模变化不敏感和适用大规模分布 式多跳无线网络的优点。

本发明解决其技术问题所采用的技术方案：一种基于平均场的分布式多跳无线网 络时钟同步方法，其特点是包括以下步骤：

节点j首先将包含本次发送时间戳报文发送至节点i。节点i在时刻接收到该 报文，并回复响应报文给节点j。响应报文中包含着本次响应报文的发送时间戳和 接收请求报文的时间戳点j在时刻接收到该响应报文。节点j根据获得的时间戳，构建如下时钟偏差计算方程：

$t_2^k-t_1^k=d_F^k+{\theta }^k---\left(1\right)$

$t_4^k-t_3^k=d_B^k+{\theta }^k---\left(2\right)$

根据公式(1)和(2)，计算节点i和节点j之间的时钟偏差为：

${\theta }^k=\frac{(t_2^k-t_1^k)-(t_4^k-t_3^k)}{2}-\frac{d_F^k-d_B^k}{2}---\left(3\right)$

式中，k为第k轮双向时间戳交换；θ^k为第k轮双向时间戳交换过程中节点i和j之 间的相对时钟偏差，为第k轮双向时间戳交换过程中从节点j到节点i到的消息传输 时延，为第k轮双向时间戳交换过程中从节点i到节点j的消息传输时延。

在一个包含M个节点的分布式多跳无线网络，基于平均场理论的分布式多跳无线 网络时钟同方法MFSP描述如下：

1)相邻节点加入本地节点的一跳邻居列表进行初始化，节点的时钟偏差初始化 为0。

2)设置同步采样定时器。同步采样定时器的作用是，本地节点周期性的向邻居 节点广播时间戳报文。

3)第k次采样。

4)M个节点在每个同步周期内都以广播时间戳报文的方式与邻居进行双向时间 戳交换。

5)第k次采样中，节点将本地第k-1次的发送时间戳以及第k-1次采样后收到 所有邻居报文的接收时间戳打包成同步数据包。

6)节点广播同步数据包到一跳邻居，并记录发送时间戳。

7)接收到一跳邻居的时钟广播报文，并记录接收件事戳。

8)根据接收获得的时间戳数据，基于卡尔曼滤波算法计算与单个一跳邻居之间 的时钟偏差。

9)判断同步采样定时器是否超时，若超时则执行第10)步，否则回到第7)步 操作。

10)同步采样定时器超时，节点i基于平均场理论计算虚拟参考时钟，同步采样 定时器复位，虚拟参考时钟计算公式如下：

$<f_R{>}_i={\Sigma }_{\left\{i^{\prime }\right\}\in N_i}{f}_{i^{\prime }}P\left(f_{i^{\prime }}\right)---\left(4\right)$

11)基于虚拟参考时钟计算能量函数，计算公式为：

$U\left(f\right)={\Sigma }_{\left\{i\right\}\in V}{(f_i-<f_R{>}_i)}^2+{\Sigma }_{\left\{i\right\}\in V}{\Sigma }_{\left\{i^{\prime }\right\}\in N_i}min\{{\sigma }^2,{(f_i-f_{i^{\prime }})}^2\}----\left(5\right)$

12)计算本地时钟偏差调整量，使能量函数逐渐最小化，从而修正节点本地时钟， 并修正本地保存的一个发送时间戳和两个接收时间戳。计算公式为：

$f_i^{k+1}=f_i^k-2\mu \times [(f_i^k-<f_R{>}_i^k)+{\Sigma }_{\left\{i^{\prime }\right\}\in N_i}(f_i^k-f_{i^{\prime }}^k)]---\left(6\right)$

13)检查同步采样定时器是否超时，如果超时，则进行新一轮的设置同步采样定 时器，然后继续循环时钟同步过程，否则本地循环等待直到定时器超时。

上式中，f_i为节点i的本地时钟，〈f_R〉_i为由平均场定义的虚拟时钟基准；f_i'为节 点i的一跳邻居的时钟,P(f_i')表示节点i的一跳邻居节点i'的时钟取值为的f概率，由 平均场的吉布斯分布确定，U(f)为能量函数，(f_i-〈f_R〉_i)²为邻居系统的单节点团C₁的 团势能；(f_i-f_i′)²为双邻居节点团C₂的团势能,μ为较小的常数。

此外，考虑节点间的时钟关系，t时刻节点i的时钟为：

C_i(t)＝α_i·t+β_i(7)

其中,α_i为时钟频偏，β_i为时钟偏差。

对时钟频偏进行调整，使其同步到虚拟参考时钟频偏，对时钟的频偏和偏差都进 行同步。一个包含M个节点的分布式多跳无线网络时钟同步过程如下：

1)相邻节点加入本地节点的一跳邻居列表进行初始化，初始化节点的时钟频偏 为1，时钟偏差为0。

2)设置同步采样定时器,。同步采样定时器的作用是，本地节点周期性的向邻居节 点广播时间戳报文。

3)第k次采样。

4)M个节点在每个同步周期内都以广播时间戳报文的方式与邻居进行双向时间戳 交换。

5)第k次采样中，节点将本地第k-1次的发送时间戳以及第k-1次采样后收到所有邻 居报文的接收时间戳打包成同步数据包。

6)节点广播同步数据包到一跳邻居，并记录发送时间戳。

7)接收到一跳邻居的时钟广播报文，并记录接收件事戳。

8)根据接收获得的时间戳数据，基于卡尔曼滤波算法计算与单个一跳邻居之间的 时钟偏差。

9)判断同步采样定时器是否超时，若超时则执行第10)步，否则回到第7)步操作。

10)同步采样定时器超时，节点i基于平均场理论计算虚拟参考时钟，同步采样定 时器复位，虚拟参考时钟计算公式如下：

$<{\hat{\alpha }}_R^k{>}_i={\Sigma }_{\left\{j\right\}\in N_i}{\hat{\alpha }}_j^{k}P\left({\hat{\alpha }}_j^k\right)---\left(8\right)$

$<{\hat{\beta }}_R^k{>}_i={\Sigma }_{\left\{j\right\}\in N_i}{\hat{\beta }}_j^{k}P\left({\hat{\beta }}_j^k\right)---\left(9\right)$

11)计算本地时钟频偏和时钟偏差调整量，使能量函数逐渐最小化，从而修正节 点本地时钟，并修正本地保存的一个发送时间戳和两个接收时间戳。计算公式为：

${\hat{\alpha }}_i^{k+1}={\hat{\alpha }}_i^k-2\times \mu \times [({\hat{\alpha }}_i^k-<{\hat{\alpha }}_R^k{>}_i)+{\Sigma }_{\left\{j\right\}\in N_i}({\hat{\alpha }}_i^k-{\hat{\alpha }}_j^k)]---\left(10\right)$

${\hat{\beta }}_i^{k+1}+{\hat{\beta }}_i^k-2\times \mu \times [({\hat{\beta }}_i^k-<{\hat{\beta }}_R^k{>}_i)+{\Sigma }_{\left\{j\right\}\in N_i}({\hat{\beta }}_i^k-{\hat{\beta }}_j^k)]\sqrt{b^2-4ac}---\left(11\right)$

12)检查同步采样定时器是否超时，如果超时，则进行新一轮的设置同步采样定 时器，然后继续循环时钟同步过程，否则本地循环等待直到定时器超时。

式中，为节点j的时钟频偏，为节点i的时钟频偏，为虚拟参考时钟频 偏，为节点i的时钟偏差，为节点j的时钟偏差，为虚拟参考时钟偏差，表示节点j的时钟频偏取值为的概率，表示节点j的时钟偏差取值为的概率， μ为较小的常数。

本发明的有益效果是：该方法首先采用广播方式实现双向时间戳交换，再将节 点之间的时钟差的总体效果等价于一个平均场，基于空间马尔可夫随机场建立网络 的时钟同步模型，根据马尔可夫随机场与吉布斯随机场的等价性，通过引入邻居系 统和团势能，得到基于平均场伊辛模型的时钟同步能量函数，并在此基础上给出采 用能量最小化寻优的时钟同步算法，基于平均场模型的全网时钟分布式同步算法。 由于采用了基于平均场模型的全网时钟同步方法，基于平均场理论，通过节点间的 平均作用确定了全网虚拟时钟基准，解决了背景技术分布式时钟同步方法时钟基准 难以确定的技术问题，采用并行能量最小化的方法实现全网时钟分布式同步，具有 快速收敛、收敛时间稳定，成本开销低，对拓扑规模变化不敏感和适用大规模分布 式多跳无线网络的优点。

下面结合附图和具体实施方式对本发明作详细说明。

附图说明

图1是本发明基于平均场的分布式多跳无线网络时钟同步方法的流程图。

图2是图1中节点间的双向时间戳交换示意图。

具体实施方式

参照图1-2。本发明基于平均场的分布式多跳无线网络时钟同步方法具体步骤如下：

节点j首先将包含本次发送时间戳报文发送至节点i。节点i在时刻接收到该 报文，并回复响应报文给节点j。响应报文中包含着本次响应报文的发送时间戳和 接收请求报文的时间戳点j在时刻接收到该响应报文。节点j根据获得的时间戳，可构建如下时钟偏差计算方程：

$t_2^k-t_1^k=d_F^k+{\theta }^k---\left(1\right)$

$t_4^k-t_3^k=d_B^k+{\theta }^k---\left(2\right)$

根据公式(1)和(2)，计算节点i和节点j之间的时钟偏差为：

${\theta }^k=\frac{(t_2^k-t_1^k)-(t_4^k-t_3^k)}{2}-\frac{d_F^k-d_B^k}{2}---\left(3\right)$

式中，k为第k轮双向时间戳交换；θ^k为第k轮双向时间戳交换过程中节点i和 j之间的相对时钟偏差，为第k轮双向时间戳交换过程中从节点j到节点i到的消息 传输时延(前向时延)，为第k轮双向时间戳交换过程中从节点i到节点j的消息传 输时延(后向时延)。

在一个包含M个节点的分布式多跳无线网络，基于平均场理论的分布式多跳无线 网络时钟同方法MFSP可描述如下：

1)相邻节点加入本地节点的一跳邻居列表进行初始化，节点的时钟偏差初始化 为0。

2)设置同步采样定时器。同步采样定时器的作用是，本地节点周期性的向邻居 节点广播时间戳报文。

3)第k次采样。

4)M个节点在每个同步周期内都以广播时间戳报文的方式与邻居进行双向时间 戳交换。

5)第k次采样中，节点将本地第k-1次的发送时间戳以及第k-1次采样后收到 所有邻居报文的接收时间戳打包成同步数据包。

6)节点广播同步数据包到一跳邻居，并记录发送时间戳。

7)接收到一跳邻居的时钟广播报文，并记录接收件事戳。

8)根据接收获得的时间戳数据，基于卡尔曼滤波算法计算与单个一跳邻居之间 的时钟偏差。

9)判断同步采样定时器是否超时，若超时则执行第10)步，否则回到第7)步 操作。

10)同步采样定时器超时，节点i基于平均场理论计算虚拟参考时钟，同步采样 定时器复位，虚拟参考时钟计算公式如下：

$<f_R{>}_i={\Sigma }_{\left\{i^{\prime }\right\}\in N_i}{f}_{i^{\prime }}P\left(f_{i^{\prime }}\right)---\left(4\right)$

11)基于虚拟参考时钟计算能量函数，计算公式为：

$U\left(f\right)={\Sigma }_{\left\{i\right\}\in V}{(f_i-<f_R{>}_i)}^2+{\Sigma }_{\left\{i\right\}\in V}{\Sigma }_{\left\{i^{\prime }\right\}\in N_i}min\{{\sigma }^2,{(f_i-f_{i^{\prime }})}^2\}---\left(5\right)$

12)计算本地时钟偏差调整量，使能量函数逐渐最小化，从而修正节点本地时钟， 并修正本地保存的一个发送时间戳和两个接收时间戳。计算公式为：

$f_i^{k+1}=f_i^k-2\mu \times [(f_i^k-<f_R{>}_i^k)+{\Sigma }_{\left\{i^{\prime }\right\}\in N_i}(f_i^k-f_{i^{\prime }}^k)]---\left(6\right)$

13)检查同步采样定时器是否超时，如果超时，则进行新一轮的设置同步采样定 时器，然后继续循环时钟同步过程，否则本地循环等待直到定时器超时。

上式中，f_i为节点i的本地时钟，〈f_R〉_i为由平均场定义的虚拟时钟基准；f_i'为节 点i的一跳邻居的时钟,P(f_i')表示节点i的一跳邻居节点i'的时钟取值为的f概率，由 平均场的吉布斯分布确定，U(f)为能量函数，(f_i-〈f_R〉_i)²为邻居系统的单节点团C₁的 团势能；(f_i-f_i′)²为双邻居节点团C₂的团势能,μ为较小的常数。

此外，考虑节点间的时钟关系，t时刻节点i的时钟为：

C_i(t)＝α_i·t+β_i(7)

其中α_i为时钟频偏，β_i为时钟偏差。

由于时钟频偏受温度、湿度、设备老化等环境因素影响，节点间的时钟频偏并不 相等，且难以计算，为了达到更好的同步效果，本方法对时钟频偏也进行调整，使其 同步到虚拟参考时钟频偏，对时钟的频偏和偏差都进行同步。以一个包含M个节点的 分布式多跳无线网络为例，时钟同步过程如下：

11)相邻节点加入本地节点的一跳邻居列表进行初始化，初始化节点的时钟频偏 为1，时钟偏差为0。

12)设置同步采样定时器,。同步采样定时器的作用是，本地节点周期性的向邻居 节点广播时间戳报文。

13)第k次采样。

14)M个节点在每个同步周期内都以广播时间戳报文的方式与邻居进行双向时间 戳交换。

15)第k次采样中，节点将本地第k-1次的发送时间戳以及第k-1次采样后收到所有 邻居报文的接收时间戳打包成同步数据包。

16)节点广播同步数据包到一跳邻居，并记录发送时间戳。

17)接收到一跳邻居的时钟广播报文，并记录接收件事戳。

18)根据接收获得的时间戳数据，基于卡尔曼滤波算法计算与单个一跳邻居之间 的时钟偏差。

19)判断同步采样定时器是否超时，若超时则执行第10)步，否则回到第7)步操作。

20)同步采样定时器超时，节点i基于平均场理论计算虚拟参考时钟，同步采样定 时器复位，虚拟参考时钟计算公式如下：

$<{\hat{\alpha }}_R^k{>}_i={\Sigma }_{\left\{j\right\}\in N_i}{\hat{\alpha }}_j^{k}P\left({\hat{\alpha }}_j^k\right)---\left(8\right)$

$<{\hat{\beta }}_R^k{>}_i={\Sigma }_{\left\{j\right\}\in N_i}{\hat{\beta }}_j^{k}P\left({\hat{\beta }}_j^k\right)---\left(9\right)$

11)计算本地时钟频偏和时钟偏差调整量，使能量函数逐渐最小化，从而修正节 点本地时钟，并修正本地保存的一个发送时间戳和两个接收时间戳。计算公式为：

${\hat{\alpha }}_i^{k+1}={\hat{\alpha }}_i^k-2\times \mu \times [({\hat{\alpha }}_i^k-<{\hat{\alpha }}_R^k{>}_i)+{\Sigma }_{\left\{j\right\}\in N_i}({\hat{\alpha }}_i^k-{\hat{\alpha }}_j^k)]---\left(10\right)$

${\hat{\beta }}_i^{k+1}+{\hat{\beta }}_i^k-2\times \mu \times [({\hat{\beta }}_i^k-<{\hat{\beta }}_R^k{>}_i)+{\Sigma }_{\left\{j\right\}\in N_i}({\hat{\beta }}_i^k-{\hat{\beta }}_j^k)]\sqrt{b^2-4ac}---\left(11\right)$

12)检查同步采样定时器是否超时，如果超时，则进行新一轮的设置同步采样定 时器，然后继续循环时钟同步过程，否则本地循环等待直到定时器超时。

式中，为节点j的时钟频偏，为节点i的时钟频偏，为虚拟参考时钟频 偏，为节点i的时钟偏差，为节点j的时钟偏差，为虚拟参考时钟偏差，表示节点j的时钟频偏取值为的概率，表示节点j的时钟偏差取值为的概率， μ为较小的常数。