基于广播Gossip算法的分布式时钟同步方法

摘要

基于广播Gossip算法的分布式时钟同步方法，涉及一种无线传感器网络的分布式时钟同步技术，解决目前所有的广播Gossip算法都面临着不能保证每个节点的时钟收敛于它们初始时钟的平均值的，致使每个节点最终达成的同步时钟会与它们初始时钟的均值有较大的偏差，不利于进行网络维护和数据分析问题。包括步骤：对包含有N个节点的无线传感器网络初始化；使每个节点获得入度信息和加扰参数值；设定节点的两个变量；判断各节点的状态：将定时期满的触发节点的变量值广播给它的外邻节点；对网络中的节点的变量值进行更新；判断无线传感器网络中N个节点的两个变量是否都收敛于同一个同步时钟值；获得时钟同步结果，完成迭代过程。本发明可广泛应用于分布式时钟同步。

说明书

技术领域

本发明涉及一种无线传感器网络的分布式时钟同步技术。

背景技术

无线传感器网络是由大量具有数据采集、数据处理和无线数据收发等功能的节点所组 成的通信网络。由于成本和体积的限制，这些节点通常都采用电池供电，因此具有有限的 数据分析和传输能力。在很多应用中，需要将各个传感器节点的时钟同步，以便进行诸如 到达时间估计的分布式定位、时分多址、分布式协同和分布式目标跟踪等领域的应用。节 点间时钟同步可以有多种方法，例如通过GPS(全球定位系统)或基站授时，但是这种 方法需要每个传感器节点装配GPS或蜂窝通信模块，不但会增加设备的成本，也会增加 它们的功耗。另外一种方法就是节点间通过交换时钟信息来进行分布式同步，但是这类方 法传统上都采用了复杂的路由协议来进行时钟信息的交换，所以通常会由于通信延时或网 络容量的问题，造成协议开销大、收敛精度低且收敛速度慢的问题。

在上述背景下，诞生了可应用于无线传感器网络分布式同步的Gossip算法。在该算 法中，每个节点被随机地唤醒，然后唤醒的节点随机地和它选定的某个(或某组)相邻节 点交换时钟信息，随后这两个(或该组)节点分别利用凸合并(Convex Combination)算 法合并这些时钟信息，并用新的时钟信息替换掉自己原有的时钟。此时称该算法完成了一 次更新或一次迭代。在数学上可以证明，通过这种算法，网络中的所有节点能够实现时钟 同步(或称为实现了共识)，并且最终每个节点的时钟恰好等于这些节点初始时钟的平均 值。因此在无线传感器网络中应用Gossip算法进行分布式时钟同步的意义在于：1)避免 热点问题。由于采用了随机行走(Random Walk)模式进行时钟信息传输，因此避免了形 成以中心节点为根的树状或网状等固定拓扑结构，因此可以使分组更好的规避热点区域。 2)减少协议开销和能量消耗。由于不需要进行路由建立和维护，所以Gossip算法有效减 少了协议开销，进而降低节点能量消耗。此外，分组在每次发送之前均进行了合并压缩， 所以分组数量大大减少，也可以有效降低节点的能量消耗。3)通信可靠性。由于不需要 通过固定的端到端路由来传输时钟信息，因此Gossip算法避免了单点失效则路由失效问 题，提高了网络的可靠性。4)提高网络可扩展性(Scalability)。由于时钟信息在传递过 程中进行了合并压缩，因而网络中增加节点只会增加算法的收敛时间，并不会显著增加网 络的业务量。因此该算法可以更好地利用网络资源，从而提高网络的扩展性。5)降低硬 件需求。传统端到端的通信模式，网络中的节点需要缓存分组直到其被正确发送为止。当 网络中的节点数较多或业务量激增时，节点需要更多的时间来处理信道竞争问题，这期间 会有大量的分组需要进行缓存，这对于存储能力十分有限的无线传感器节点是一个巨大的 挑战。而Gossip算法中的每个节点只需要保存它自己的时钟信息即可，一旦接收到新的 时钟信息，它会立刻将两个时钟信息压缩合并，所以它只会占用有限长度的数据发送队列， 而与网络的规模和业务模式无关。因此，Gossip算法可以很好的适应无线传感器网络的 体系结构和工作模式，具有很好的应用前景。

Gossip算法在1984年由Tsitsiklis等人首次提出，该算法仅利用网络节点的本地 信息与它的邻居节点的信息进行数据交换，解决了分布条件下的平均共识问题。Gossip 算法可以被广泛的用于源定位问题、参数估计问题、卡尔曼滤波等，近年来更是受到了学 术界的广泛关注。本发明涉及一种无线传感器网络中的分布式平均共识算法，该算法能够 使得无线传感器网络中所有的节点达到平均共识状态，与传统的算法相比，该算法具有更 快的收敛速度，并且在数学上被证明是收敛的并且收敛于均值，同时，该算法对实际应用 过程中的丢包问题、拓扑结构变化问题有很好的适应性。

尽管国内外已经有很多关于无线传感器网络Gossip算法方面的研究成果，但是以前 的研究主要侧重于成对Gossip算法(Pair-wise Gossip Algorithm)和地理Gossip算法 (Geographic Gossip Algorithm)的研究。这两类算法由于在每次更新时只有选定的节点 进行数据交换，因此尽管可以使节点时钟收敛于它们初始时钟的均值，但是却只能用于双 向链路，没有很好的利用无线信道的广播特性。直到最近几年，国际上才出现了对于广播 Gossip算法(Broadcast Gossip Algorithm)的研究。这类算法中当一个节点广播它的时钟 信息时，所有能接收到该时钟信息的节点均可以更新它们的数据。由于不需要反向数据交 换，所以这类算法更适合于非对称的无线信道。同时，由于每次时钟更新有更多的节点参 与，因此这类算法的收敛速度更快。此外，由于广播Gossip算法不再需要随机选择相邻 节点，从而使算法更加简单并易于实现。然而遗憾的是，目前国际上所有的广播Gossip 算法都面临着两个问题：或者它们不能保证每个节点的时钟收敛于它们初始时钟的平均值 (即平均共识)；或者能收敛到平均值，但是无法从数学上证明其收敛性。对于前者，那 么每个节点最终达成的同步时钟会与它们初始时钟的均值有较大的偏差，不利于进行网络 维护和数据分析。而后者由于不能从数学上证明其收敛性，因此算法的可靠性无法得到保 证，并且该算法从仿真分析结果来看收敛速度也极慢。

发明内容

本发明为了解决目前所有的广播Gossip算法都面临着不能保证每个节点的时钟收敛 于它们初始时钟的平均值的，致使每个节点最终达成的同步时钟会与它们初始时钟的均值 有较大的偏差，不利于进行网络维护和数据分析问题，从而提供一种基于广播Gossip算 法的分布式时钟同步方法。

基于广播Gossip算法的分布式时钟同步方法，它包括如下步骤：

步骤一：对包含有N个节点的无线传感器网络初始化，并初始化入度信息和加扰参 数；其中N为正整数，为节点i的入度信息，ε为加扰参数；

步骤二：设定节点的两个变量，x_i(t)为节点i的当前时钟变量，y_i(t)为节点i的伴随 变量，其中x_i(0)为节点i的初始时钟值，且y_i(0)＝0，即初始时间为t＝0；并设定定时器， 所述定时器的计数值满足任意随机分布；

步骤三：判断各节点的状态：当节点为定时期满的触发节点k时则进入步骤五，当节 点为接收到本地广播的外邻节点j时则进入步骤六；否则继续监听；

步骤四：将定时期满的触发节点k的两个变量值，即触发节点k的当前时钟变量值 x_k(t)和伴随变量值y_k(t)，利用本地广播分别广播给它的外邻节点j；

步骤五：对无线传感器网络中的节点的时钟变量值和状态变量值进行更新，并将触发 节点k的定时器清除；

步骤六：判断无线传感器网络中N个节点的两个变量是否都收敛于同一个同步时钟 值，即无线传感器网络中N个节点的时钟变量均相同，且N个节点的伴随变量均相同； 如果是则进入步骤八，否则重新设定定时器并返回步骤四；

步骤七：获得时钟同步结果，完成迭代过程。

步骤一所述对包含有N个节点的无线传感器网络初始化的过程为：

对包含有N个节点的无线传感器网络建立有向简单图G＝(V，E)，其中V＝{1，2，…，N} 为节点集合，E为边集合；当且仅当节点i能够直接从节点j处接收分组时，称边(i，j)∈E 存在，此时称节点i为节点j的外邻，而节点j为节点i的内邻，且

令和分别代表节点i的内邻集合和外邻集 合，和分别为节点i的入度和出度，符号|X|_c代表取集合X的势。

所述步骤五：对无线传感器网络中的节点的时钟变量值和状态变量值进行更新的过程 中：

对于触发节点k，将该节点的状态值、伴随变量值发送给外邻节点j，然后将触发触 发节点k的伴随变量设置为0；

$\left(\begin{array}{c}{x}_k(t+1)=x_k\left(t\right)\\ y_k(t+1)=0\end{array}\right)$

式中：x_k(t)表示触发节点k在t时刻的时钟变量，y_k(t)表示触发节点k在t时刻的伴 随变量。

对于外邻节点j，根据收到的信息进行更新：

$\left(\begin{array}{c}{x}_j(t+1)=(1-\frac{1}{{\delta }_j^{+}})x_j\left(t\right)+\frac{1}{{\delta }_j^{+}}{x}_k\left(t\right)+ϵ\frac{1}{{\delta }_j^{+}}{y}_j\left(t\right)\\ y_j(t+1)=\frac{1}{{\delta }_j^{+}}{x}_j\left(t\right)-\frac{1}{{\delta }_j^{+}}{x}_k\left(t\right)+(1-ϵ\frac{1}{{\delta }_j^{+}})y_j\left(t\right)+\frac{1}{{\delta }_j^{+}}{y}_k\left(t\right)\end{array}\right)$

式中：x_j(t)表示外邻节点j在t时刻的伴随变量，y_j(t)表示外邻节点j在t时刻的伴 随变量，为外邻节点j的入度。

所述加扰参数ε的取值为Re(ξ₂)/2，其中ξ₂为矩阵L的第二小特征值；

所述L为其中θ为满足：如果j＝k并且那么否则

本发明基于广播Gossip算法实现保证每个节点的时钟收敛于它们初始时钟的平均值 的，使每个节点最终达成的同步始终会与他们初始时钟的均值没有较大偏差问题。本发明 提出一种基于广播Gossip算法的具有低收敛误差的分布式时钟同步技术，并且该算法可 以从数学上证明其收敛性。当给定迭代次数时，本发明的方法具有最低的收敛误差，当给 定收敛误差时，本发明的方法具有最快的收敛速度，因此本发明基于广播Gossip算法的 分布式时钟同步方法在所有广播Gossip算法中具有最佳的性能。

附图说明

图1为本发明基于广播Gossip算法的分布式时钟同步方法的流程图；

图2为具体实施方式一中的100个节点的网络收敛方差的仿真结果；

图3为具体实施方式一中的100个节点的网络收敛偏差的仿真结果；

图4为具体实施方式一中的500个节点的网络收敛方差的仿真结果；

图5为具体实施方式一中的500个节点的网络收敛偏差的仿真结果。

具体实施方式

具体实施方式一、结合图1说明本具体实施方式。

基于广播Gossip算法的分布式时钟同步方法，它包括如下步骤：

步骤一：对包含有N个节点的无线传感器网络初始化，并初始化入度信息和加扰参 数；其中N为正整数，为节点i的入度信息，ε为加扰参数；

步骤二：设定节点的两个变量，x_i(t)为节点i的当前时钟变量，y_i(t)为节点i的伴随 变量，其中x_i(0)为节点i的初始时钟值，且y_i(0)＝0，即初始时间为t＝0；并设定定时器， 所述定时器的计数值满足任意随机分布；

步骤三：判断各节点的状态：当节点为定时期满的触发节点k时则进入步骤五，当节 点为接收到本地广播的外邻节点j时则进入步骤六；否则继续监听；

步骤四：将定时期满的触发节点k的两个变量值，即触发节点k的当前时钟变量值 x_k(t)和伴随变量值y_k(t)，利用本地广播分别广播给它的外邻节点j；

步骤五：对无线传感器网络中的节点的时钟变量值和状态变量值进行更新，并将触发 节点k的定时器清除；

步骤六：判断无线传感器网络中N个节点的两个变量是否都收敛于同一个同步时钟 值，即无线传感器网络中N个节点的时钟变量均相同，且N个节点的伴随变量均相同； 如果是则进入步骤八，否则重新设定定时器并返回步骤四；

步骤七：获得时钟同步结果，完成迭代过程。

工作原理：本发明利用广播Gossip算法获取无线传感器网络的时钟同步，本算法中 每个节点的时钟值不但收敛，而且收敛于它们初始时钟的均值。数学上还可以证明，如果 加扰参数ε取值为Re(ξ₂)/2，那么所提出的算法具有最快的收敛速度。

本专利的方法比所有其他广播Gossip算法具有更快的收敛速度或更好的收敛精度。 在给定迭代次数时，本方法在所有广播Gossip算法中收敛误差最小；在给定收敛误差时， 本方法收敛速度最快。在实际应用时，分布式时钟同步就是通过这两个参数来衡量性能指 标的。或者限制网络中节点的迭代次数，或者给定收敛的误差。满足这两个条件之一，算 法就认为收敛了。

本发明的具体步骤详细为：

步骤一：对包含有N个节点的无线传感器网络初始化，并初始化入度信息和加扰参 数；其中N为正整数，为节点i的入度信息，ε为加扰参数；

对于有N个节点的无线传感器网络，可以将其建模为一个有向单图G＝(V，E)，这里 V＝{1，2，…，N}为节点集合，而E为边集合。当且仅当节点i能够直接从节点j处接收分组 时，才称边(i，j)∈E存在，此时称节点i为节点j的外邻(Out-neighbor)，而节点j为节点 i的内邻(In-neighbor)。在本发明中，将不允许自环的存在，即这样，即使当 一个节点发送分组时，它自己能够通过无线信道接收到它所发送的分组，也将会直接丢弃。 定义和分别代表节点i的内邻集合和外邻集合， 并且定义和为节点i的入度(In-degree，图论术语，代表一个节点内邻 的数量)和出度(Out-degree，图论术语，代表一个节点外邻的数量)，这里符号|X|_c代表 取集合X的势(即集合中元素的数量)。

入度信息根据无线传感网络拓扑结构分为两种方式获得：(1)自行获得的方式获得入 度信息过程如下：每个节点侦听它周围节点发送的分组，从而可以知道它周围的相邻节点 信息。这样节点就可以通过侦听的方式获得它相邻节点的数量，从而获得入度信息；(2) 直接设定方式获得入度信息。如果网络拓扑结构比较简单，节点数较少的时候，也可以直 接设定每个节点的入度信息。如果网络是随机分布的，那么最好就采用自行获取入度信息 的方式。

步骤二：设定节点的两个变量，x_i(t)为节点i的当前时钟变量，y_i(t)为节点i的伴随 变量，其中x_i(0)为节点i的初始时钟值，且y_i(0)＝0，即初始时间为t＝0；并设定定时器， 所述定时器的计数值满足任意随机分布；

网络中的每个节点i均保存有两个变量，一个是其当前时钟变量x_i(t)，另一个为伴随 变量y_i(t)。其中x_i(0)为每个节点的初始时钟值，并指定y_i(0)＝0。

步骤三：判断各节点的状态：当节点为定时期满的触发节点k时则进入步骤五，当节 点为接收到本地广播的外邻节点j时则进入步骤六；否则继续监听；

步骤四：将定时期满的触发节点k的两个变量值，即触发节点k的当前时钟变量值 x_k(t)和伴随变量值y_k(t)，利用本地广播分别广播给它的外邻节点j；

步骤五：对无线传感器网络中的节点的时钟变量值和状态变量值进行更新，并将触发 节点k的定时器清除；

这些节点更新其变量的具体过程如下：

对于触发节点k，将该节点的状态值、伴随变量值发送给外邻节点j，然后将触发触 发节点k的伴随变量设置为0；

$\left(\begin{array}{c}{x}_k(t+1)=x_k\left(t\right)\\ y_k(t+1)=0\end{array}\right)$

式中：x_k(t)表示触发节点k在t时刻的时钟变量，y_k(t)表示触发节点k在t时刻的伴 随变量。

对于外邻节点j，根据收到的信息进行更新：

$\left(\begin{array}{c}{x}_j(t+1)=(1-\frac{1}{{\delta }_j^{+}})x_j\left(t\right)+\frac{1}{{\delta }_j^{+}}{x}_k\left(t\right)+ϵ\frac{1}{{\delta }_j^{+}}{y}_j\left(t\right)\\ y_j(t+1)=\frac{1}{{\delta }_j^{+}}{x}_j\left(t\right)-\frac{1}{{\delta }_j^{+}}{x}_k\left(t\right)+(1-ϵ\frac{1}{{\delta }_j^{+}})y_j\left(t\right)+\frac{1}{{\delta }_j^{+}}{y}_k\left(t\right)\end{array}\right)$

式中：x_j(t)表示外邻节点j在t时刻的伴随变量，y_j(t)表示外邻节点j在t时刻的伴 随变量，为外邻节点j的入度。

对于其它节点有：

$\left(\begin{array}{c}{x}_l(t+1)=x_l\left(t\right)\\ y_l(t+1)=y_l\left(t\right)\end{array}\right),$

即其他节点l只进行自己的时钟更新。

在上述迭代算法中，x(t+1)主要用来储存每次迭代过程中节点所储存的同步时钟估计 值；y(t+1)用来储存每次迭代过程中节点同步时钟估计值与真实值之间的偏差；ε为加扰 参数，通过改变该参数，算法将会有不同的收敛速度，后面会详细讨论它的取值。由于上 述算法是典型的线性迭代算法，因此可以用矩阵的形式来进行表述，即

$\left(\begin{array}{c}x(t+1)\\ y(t+1)\end{array}\right)=W_k\left(t\right)\left(\begin{array}{c}x\left(t\right)\\ y\left(t\right)\end{array}\right)---\left(1\right)$

这里线性变换矩阵W_k(t)的下脚标k代表这次时钟更新由节点k发起。

步骤六：判断无线传感器网络中N个节点的两个变量是否都收敛于同一个同步时钟 值，即无线传感器网络中N个节点的时钟变量均相同，且N个节点的伴随变量均相同； 如果是则进入步骤八，否则重新设定定时器并返回步骤四；

对于广播Gossip算法，在任意t时刻的更新时，只有该次更新所激活的某个节点k 广播它的状态值，而只有节点k的外邻节点才能接收到该状态值并进行状态更新。 因此，网络中只有节点和边(j，k)∈E参与了这次状态值更新。基于这个原因，可以 将图G中的节点全部保留但是将除(j，k)∈E以外的边全部删除，并构造出一个新的图G_k。 然后为这个新的图G_k生成相应的本地广播加权邻接矩阵本地广播加权入度矩阵 和本地广播加权拉普拉斯矩阵为便于描述，下面给出这三种矩阵的具体定 义。

本地广播加权邻接矩阵该矩阵中的每个元素满足：如果j＝k并且 那么否则

本地广播加权入度矩阵该矩阵中的每个元素满足：如果那么否则

本地广播加权拉普拉斯矩阵这里代表全1向量而 Diag(v)代表一个对角阵并且它的对角元素为向量v的对应元素。

这三种加权矩阵分别是：

${\hat{A}}_2\left(\theta \right)=\left(\begin{array}{cccc}0& 0& 0& 0\\ 0& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0.5& 0& 0\end{array}\right),$${\hat{D}}_2\left(\beta \right)=\left(\begin{array}{cccc}0& 0& 0& 0\\ 0& 0& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 0.5\end{array}\right),$${\hat{L}}_2\left(\theta \right)=\left(\begin{array}{cccc}0& 0& 0& 0\\ 0& 0& 0& 0\\ 0& -1& 1& 0\\ 0& 0.5& 0& 0.5\end{array}\right)$

利用这三种矩阵，可以将变换矩阵W_k(t)用以下的公式来描述。

$W_k\left(t\right)=\left(\begin{array}{cc}I-{\hat{L}}_k\left(\theta \right),& ϵ{\hat{D}}_k\left(\beta \right)\\ {\hat{L}}_k\left(\theta \right),& I-e_k{e}_k^T-{ϵ\hat{D}}_k\left(\beta \right)+{\hat{A}}_k\left(\theta \right)\end{array}\right)---\left(2\right)$

这里I为单位矩阵，而e_k为标准的基向量，即它除了第k个元素为1外，其余元素都 为0。可以验证这里和分别为全1列向量和全0列向量。因 此如果向量x(t)和y(t)分别收敛于和(这里c为一个常数)，那么整个迭代算法就进 入了一个不动点，此后向量x(t)和y(t)的状态值将不会改变，从而进入收敛状态。并且此 时所有节点取得了共识，即对于任意的两个节点i和j，lim_t→∞x_i(t)＝lim_t→∞x_j(t)。需要指 出，如果网络中所有的链路都是双向对称的，那么对任意的节点有此时可以证明， 本算法中每个节点的时钟值不但收敛，而且收敛于它们初始时钟的均值。

步骤七：获得时钟同步结果，完成迭代过程。

从数学理论上论述：

如果加扰参数ε取值为Re(ξ₂)/2，那么所提出的算法具有最快的收敛速度，这里ξ₂为 矩阵L的第二小特征值。利用矩阵扰动理论和马尔科夫矩阵理论，可以得到以下两个结 论。

结论1.所提出算法可以保证每个节点能够依数学期望达成时钟同步，即

$\underset{t\to \infty }{\lim }E\left(\left(\begin{array}{c}x\left(t\right)\\ y\left(t\right)\end{array}\right)\right)=\underset{t\to \infty }{\lim }E\left(\underset{j=0}{\overset{t}{\Pi }}W\left(j\right)\right)\left(\begin{array}{c}x\left(0\right)\\ y\left(0\right)\end{array}\right)$

$=\underset{t\to \infty }{\lim }{\bar{W}}^t\left(\begin{array}{c}x\left(0\right)\\ y\left(0\right)\end{array}\right)$

$=\left(\begin{array}{c}\overrightarrow{1}\\ \overrightarrow{0}\end{array}\right)\left(\begin{array}{cc}{\omega }_1^T& {\omega }_2^T\end{array}\right)\left(\begin{array}{c}x\left(0\right)\\ y\left(0\right)\end{array}\right)---\left(3\right)$

$=\left({\omega }_1^{T}x\left(0\right)\right)\left(\begin{array}{c}\overrightarrow{1}\\ \overrightarrow{0}\end{array}\right)$

这里，该公式成立是因为每个矩阵W_k(t)为独立同分布 的随机矩阵。利用马尔科夫矩阵的性质和矩阵扰动理论，可以证明矩阵的最大特征值 为1，并且是一个单根；而它的其余特征值的模均小于1，所以该矩阵的幂积收敛，收敛 结果如公式(3)所示，其中向量${\left(\begin{array}{cc}{\omega }_1^T& {\omega }_2^T\end{array}\right)}^T$和${\left(\begin{array}{cc}{\overrightarrow{1}}^T& {\overrightarrow{0}}^T\end{array}\right)}^T$分别为矩阵对应于特征值1的左特 征向量和右特征向量，并且满足归一化条件$\left(\begin{array}{cc}{\omega }_1^T& {\omega }_2^T\end{array}\right){\left(\begin{array}{cc}{\overrightarrow{1}}^T& {\overrightarrow{0}}^T\end{array}\right)}^T=1.$从公式(3)不难看出， 所有节点的时钟最终收敛于值

结论2.所提算法的二阶矩收敛，即极限存在，其中 $m\left(t\right)={\left(\begin{array}{cc}{x\left(t\right)}^T& {y\left(t\right)}^T\end{array}\right)}^T-(1/N){\left(\begin{array}{cc}{\overrightarrow{1}}^T& {\overrightarrow{0}}^T\end{array}\right)}^T\left(\begin{array}{cc}{\overrightarrow{1}}^T& {\overrightarrow{1}}^T\end{array}\right){\left(\begin{array}{cc}{x\left(0\right)}^T& {y\left(0\right)}^T\end{array}\right)}^T$代表了每次时钟更新时每个节 点的两个变量值与所有节点初始变量平均值的差值。

综合结论1和结论2可知，所提时钟同步算法不但依概率能够收敛，并且收敛误差有 界，因此算法在数学上可以证明其收敛性。

为了便于比较，现将国际上已有的两种广播Gossip算法分别命名为BGA-1和BGA-2， 并将它们与本发明提出的算法(命名为BBGA)进行性能比较。其中BGA-1是能够证明 算法收敛，但是算法不能收敛于初始时钟均值的广播Gossip算法；而BGA-2是不能通过 数学手段证明其收敛性的广播Gossip算法。在下面的性能分析中，网络中存在100或500 个节点，并由它们生成随机几何图。仿真中采用了两种不同的加扰参数配置，其中 BBGA-opt代表加扰参数ε取最优值Re(ξ₂)/2；而BBGA-0.5代表加扰参数ε取值0.5。下 面分别从收敛速度和收敛误差两个方面来分析算法的性能。

1)收敛速度

为了分析收敛速度，首先定义收敛速度的评价标准，即方差

从公式(4)不难看出，q(t)度量了每次迭代时每个节点所保持的时钟变量的方差。当节 点形成共识时，q(t)将收敛为0。因此，q(t)收敛于0的速度快慢可以用来衡量算法的收敛 速度。

2)收敛误差

为了分析收敛误差，可以定义偏差函数

如果一个算法能够保证收敛于所有节点初始时钟的均值，那么r(t)将收敛于0；否则， r(t)收敛值的大小就决定了收敛误差的大小。因此偏差函数r(t)可以用来衡量算法的收敛误 差。

图2和图4是算法间在100个节点和500个节点网络收敛方差的仿真结果，该仿真结 果同时表明了算法的收敛速度。图2和图5是算法间在100个节点和500个节点网络收敛 偏差的仿真结果，该仿真结果同时表明了算法的收敛误差。从仿真结果可以看出，BGA-1 收敛速度最快，但这是以收敛误差最大为代价的。BGA-2收敛速度最慢，但是收敛精度 最高。本发明所提出的BBGA算法，无论加扰参数取最优值还是0.5，它们的性能都介于 BGA-1和BGA-2之间。显然，BBGA-opt的性能要优于BBGA-0.5，但是加扰参数的最优 化需要事先知道网络的拓扑结构，所以仅适合于小规模的应用。

综上，对于分布式时钟同步，由于并不需要每个节点的时钟最终严格收敛于它们初始 时钟的均值，只要该收敛值满足一定的精度要求即可。从以上的仿真分析不难看出，本发 明所提出的算法在收敛精度方面要优于BGA-1，在收敛速度方面要优于BGA-2，因此是 在收敛速度和收敛精度间的均衡，更符合分布式时钟同步算法的应用要求。同时，由于 BBGA-0.5具有简便易行和适用于大规模网络应用的特点，因此具有最优的工程实践价值。