加快一致性分布式算法收敛速度的网络拓扑优化方法

摘要

本发明公开了加快一致性分布式算法收敛速度的网络拓扑优化方法。现有方法不能及高效解决网络拓扑参数发生改变的问题。本发明方法不改变网络拓扑连接边数目，使用网络拓扑的局部节点信息，调整节点之间的连接优化拓扑的连通性，首先计算原始网络拓扑的信息并初始化调整次数，然后使用局部节点(邻居节点)信息计算出各个节点的删边信息，随机选择一个节点的删边信息执行一次删边操作，使用局部节点信息计算各节点的加边信息，随机选择一个节点的加边信息执行一次加边操作，最后根据网络拓扑中的最大度与最小度的差值以及调整次数的上限结束优化。本发明方法操作简单，无需网络拓扑全局信息，能够加速一致性分布式算法收敛等优点。

说明书

技术领域

本发明属于分布式信息处理技术领域，具体是分布式信息处理中的网络拓扑优化领域， 涉及一种加快一致性分布式算法收敛速度的网络拓扑优化方法。

背景技术

近年来，随着网络的普及使用，云计算和大数据等新兴领域的出现，分布式网络因其高 可靠性、可扩展性、灵活性、更快的处理速度等优势逐渐代替集中式网络。分布式网络是由 分布在不同地点且具有多个节点机互连而成的，每个节点都是独立存储和计算的，节点间就 需要网络通信算法进行协作，因此产生了各种各样的分布式算法，其中的一致性分布式算法 是分布式网络中应用较多的算法。

一致性分布式算法，不需要将信息传输到一个中央处理器，是通过与邻居节点交换信息 最终所有节点达成一致。在实际的网络环境中，有限的带宽资源使得节点之间不能进行太多 的信息交换和多次迭代计算，因此加快一致性分布式算法收敛速度具有重要应用价值。

一致性分布式算法的收敛优化是一个复杂组合优化问题，已有的加快一致性分布算法收 敛速度的优化方法主要分成两个大类。一类是对算法的优化，如分布式梯度算法、分布式交 替方向乘子法、分布式牛顿算法等。分布式梯度算法的基本思想是在每次迭代中，每个节点 都根据局部代价函数在变量梯度的反方向更新相应的参数，最终实现对目标函数的优化；分 布式交替方向乘子法的基本思想是将原始变量和目标函数进行拆分，即将原问题分解成较容 易求解的若干个子问题，其收敛速度要快于分布式梯度算法；分布式牛顿法的基本思想是利 用泰勒展开近似Hessian矩阵的逆矩阵，减少求解逆矩阵的计算量实现目标函数的快速收 敛。另一类是从网络拓扑结构入手分析一致性分布式算法的收敛问题，证明出一些拓扑结构 参数对收敛速度的上下界约束，以及提出了一些重要的网络拓扑模型，如有着小的平均路径 长度和大的集聚系数的小世界网络、符合实际网络特征的无尺度网络等，也讨论了对固定网 络拓扑模型下基于全局信息下的拓扑优化，验证了网络拓扑结构参数对收敛速度的影响，但 是获取网络全局信息是不可行的。

在实际的网络环境中，一方面网络拓扑的连接通常会发生变化，这样的变化会对网络的 一致性收敛性能产生一定的影响，对一致性分布式算法的优化并不能及时且高效应对网络拓 扑结构变化问题；另一方面，有限的通信资源使得获取网络全局信息是不可行的，因此亟需 一种方法不仅能够及时且高效应对拓扑结构变化问题，还能使用网络拓扑的局部节点信息去 实现拓扑结构的优化，进而加快一致性分布式算法的收敛速度。

发明内容

本发明的目的是针对网络拓扑结构影响着一致性分布式算法收敛性能的问题，提供一种 加快一致性分布式算法收敛速度的网络拓扑优化方法。本发明方法在不改变网络拓扑连接边 数目的情况下，以降低网络通信开销、加快收敛速度为目的，使用网络拓扑的局部节点信 息，调整节点之间的连接，优化拓扑的连通性，加快一致性分布式算法的收敛速度，进而降 低网络通信开销。

为了实现上述目的，本发明采用如下技术方案：

步骤(1)计算原始网络拓扑的信息，具体是：

(1-1)由N个节点组成的网络拓扑表示为G＝(V,E)；其中，节点集合V＝{s

(1-2)根据连接情况计算相应的邻接矩阵A，其中a

(1-3)根据邻接矩阵A，得到节点s

(1-4)计算拉普拉斯矩阵L＝D-A，L的第i行、第j列元素

(1-5)计算节点s

步骤(2)初始化调整次数k，令k＝0；

步骤(3)计算各个节点的初始删边信息，具体是：

(3-1)从各个节点的邻居节点集合中找到有着各自局部最大节点度和的节点对集合

(3-2)从节点对集合

(3-3)将节点对集合

步骤(4)与邻居节点交换初始删边信息，确定各个节点的删边信息，具体是：

(4-1)节点s

(4-2)从各个节点和它的邻居节点集合的初始删边信息中找到有着各自局部最大节点度 和的节点对集合

(4-3)从节点对集合

(4-4)将节点对集合

步骤(5)执行一次删边操作，并更新相应的信息，具体是：

(5-1)从节点集合V＝{s

(5-2)更新节点s

步骤(6)计算各个节点的初始加边信息，具体是：

考虑到加边时节点s

(6-1)从各个节点的非邻居节点集合中找到有着各自局部最小节点度和的节点对集合

(6-2)从节点对集合

(6-3)将节点对集合

步骤(7)与邻居节点交换初始加边信息，确定各个节点的加边信息，具体如下：

(7-1)节点s

(7-2)从各个节点和它的邻居节点集合的加边信息中找到有着各自局部最小节点度和的 节点对集合

(7-3)从节点对集合

(7-4)将节点对集合

步骤(8)执行一次加边操作并更新相应的信息，具体是：

(8-1)从节点集合V＝{s

(8-2)更新节点s

步骤(9)更新调整次数k，判断是否结束优化，具体是：

(9-1)更新调整次数k＝k+1；

(9-2)判断是否结束优化。计算当前网络拓扑中最大节点度d

本发明依据网络拓扑结构影响着一致性分布式算法的收敛性能，在不改变网络拓扑连接 边数目的情况下，使用网络拓扑的局部节点信息，调整节点之间的连接(即删边、加边)优 化拓扑的连通性。本发明具有以下优点：

(1)现有的优化方法的对象是一致性分布式算法本身，而本发明所提方法是从网络拓扑 结构出发，提高收敛速度的同时又能够优化拓扑连通性。

(2)本发明所提方法是基于网络拓扑的局部节点信息，减少节点之间交换信息的次数， 可以有效节省网络节点之间的通信资源，降低网络通信开销。

附图说明

图1为本发明方法的流程图；

图2为本发明实施例中的原始拓扑；

图3为本发明实时例中的具体优化调整图；

图4为本发明实施例中的优化拓扑。

具体实施方式

以下结合附图并举例对本发明做进一步详细说明，方法的流程图如图1所示。

如图2所示，节点i如图中的圆形所示，连接边如图中的直线所示。一致性模型可以表 示为X(t+1)＝W·X(t),其中X(t)为各节点t时刻的状态值，W∈R

将拉普拉斯矩阵的次小特征值λ

本实例具体通过以下步骤实现：

步骤(1)计算原始网络拓扑的信息。如图2所示，在节点数量N＝10的原始网络拓扑中，连接边数量K＝25，计算相应的邻接矩阵A、度矩阵D、拉普拉斯矩阵L，得到拉普 拉斯矩阵的次小特征值λ

步骤(2)初始化调整次数k＝0。

步骤(3)计算各个节点的初始删边信息。从各个节点的邻居节点集合中找到有着各自局 部最大节点度和的节点对集合

步骤(4)与邻居节点交换初始删边信息，确定各个节点的删边信息。节点s

步骤(5)执行1次删边操作并更新相应的信息。从节点集合V＝{s

步骤(6)计算各个节点的初始加边信息。从各个节点的非邻居节点集合中找到有着各自 局部最小节点度和的节点对集合

步骤(7)与邻居节点交换初始加边信息，确定各个节点的加边信息。节点s

步骤(8)执行1次加边操作并更新相应的信息。从节点集合V＝{s

步骤(9)更新调整次数k，判断是否结束优化。更新调整次数k＝k+1，计算当前网络拓 扑中最大节点度d