基于量化无偏广播Gossip算法的分布式负载均衡方法

摘要

基于量化无偏广播Gossip算法的分布式负载均衡方法，本发明涉及分布式负载均衡方法。本发明是要解决分布式共识，具体为分布式负载均衡问题从而提出了经过量化的无偏广播Gossip算法。一、对节点状态值进行初始化并设置无线传感器网络的同步时钟和最大迭代次数；二、无偏广播Gossip算法的迭代和量化过程；三、当迭代次数达到预设最大迭代次数时，结束迭代；此时无线传感器网络中所有节点负载达到均衡，即完成基于量化无偏广播Gossip算法的分布式负载均衡方法。本发明应用于通信领域。

权利要求

1.基于量化无偏广播Gossip算法的分布式负载均衡方法，其特征在于基于量化无偏广播Gossip算法的分布式负载均衡方法包括以下步骤：一、对节点状态值进行初始化并设置无线传感器网络的同步时钟和最大迭代次数；

二、无偏广播Gossip算法的迭代和量化过程；

三、当迭代次数达到预设最大迭代次数时，结束迭代；此时无线传感器网络中所有节点负载达到均衡，即完成基于量化无偏广播Gossip算法的分布式负载均衡方法；

所述步骤一具体为：

(一)将无线传感器网络作为一个随机的几何图模型G(N,R)，N代表传感器节点个数，R为连通半径，N个传感器节点均匀地分布在网络中；这N个传感器节点的拓扑结构用N×N的相邻矩阵A表示，如果两个节点i和j间的欧氏距离小于传输半径R，则认为两个节点是彼此相邻的，可以直接通信，则令Aij＝1；否则，两个节点是不相邻的，不能直接进行通信，则令Aij＝0；当i＝j时，i和j代表同一个节点，则令Aij＝0；令Ni＝{j∈{1,2,…,N}:Aij≠0}表示节点i的所有相邻节点；

(二)无线传感器网络中的每个节点i保存有两个变量，一个是当前网络状态平均值的估计值xi(t)，另一个为伴随变量yi(t)；由传感器测得的每个节点的初始状态值xi(0)为初始时刻每个节点i的负载数量，并设置伴随变量yi(0)＝0；同时采用量化算法Q(·)对xi(0)进行量化得到量化后的初始值(三)在无线传感器网络中设置统一定时器，所述定时器的计数值满足指数分布，同时设置最大迭代次数；

所述步骤二中无偏广播Gossip算法的迭代和量化过程具体为：

1)启动定时器，开始计时：当开始本轮迭代时，判断当前迭代次数是否已达到最大值，若未达到最大值，则进入本轮迭代过程；若已达到最大值，则退出迭代过程；

2)在本轮迭代过程中，判断节点的定时器计数值是否已满：若在时刻t节点k的计时期满则该节点被随机唤醒，否则节点不会被唤醒并进入等待接收状态；被唤醒的节点k向全网广播它的当前量化状态值 和量化伴随变量值 同时节点k更新t+1时刻自己的最终状态值为

3)判断其他未被唤醒的节点是否会在t时刻接收到节点k的广播信息：若未接收到节点k的广播信息，令这些节点为 则进入步骤4)；若接收到节点k的广播信息，令这些节点为 则这些节点按照以下方法更新自己t+1时刻的状态信息xj(t+1)和yj(t+1)：其中 和 分别代表节点i的内邻集合和外邻

集合，这里V＝{1,2,…,N}为节点集合，E为边集合；并且定义 为节点k的出度，为节点j的入度，符号|X|c代表取集合X的势；

随后， 节点按照量化算法Q(·)对xj(t+1)和yj(t+1)经行量化，得到t+1时刻的量化值 和Q(·)代表量化运算，具体的量化过程为， 使 映射到它的最近整数值，这种量化规则使得对于所有的 成立；

之后， 节点按照以下方法消除 和 的累计量化误差，作为本次迭代

的最终状态更新值；

4)未在时刻t接收到k节点的广播信息的那些 节点保持其当前量化状态值不变，即

5)当所有节点完成本轮的量化无偏广播Gossip算法的迭代更新和量化过程后，迭代次数加一，重复步骤1)～步骤4)，进入下一轮迭代。

说明书

基于量化无偏广播Gossip算法的分布式负载均衡方法

技术领域

[0001] 本发明涉及分布式负载均衡方法。

背景技术

[0002] Gossip算法在1984年由Tsitsiklis等人首次提出，该算法仅利用网络节点的本地信息和其邻居节点信息进行数据交换，解决了分布式条件下的平均共识问题。在实际的数字通信链路中，由于测量值的精度和通信信道容量的限制，以及有限的节点存储容量使得对节点信息进行量化成为必要。

[0003] 随着无线技术的发展，无线传感器网络应运而生。无线传感器网络就是由大量具有无线通信、数据采集和处理、协同合作等功能的传感器节点协同组织起来的简单传感器网络。它是一个通过无线通信方式形成的一个多跳的自组织的网络系统，其作用是协作和感知、采集和处理网络覆盖区域中感知对象的信息，并将该信息发送给观察者。因此无线传感器网络为人们提供最直接、最有效、最真实的信息，具有快速部署、抗毁性强、实时性等特点，有着越来越广泛的应用前景。

[0004] 在无线传感器网络中，分布式平均共识问题是一个具有挑战性的基础性问题。平均共识指的是网络根据各个节点的初始状态通过信息的交换使各个节点最终达到一致状态的过程。在工程应用中，很多实际问题最终都能够转化成平均共识问题，例如源定位问题、同步问题，以及在并行计算机或分布式网络中存在的负载均衡问题。负载均衡是指将负载(工作任务)进行平衡、分摊到多个网络节点或设备上进行执行，从而共同完成工作任务。由于现有网络的各个核心部分随着业务量的提高，访问量和数据流量的快速增长，其处理能力和计算强度也相应地增大，使得单一的服务器或网络节点设备根本无法承担。在此情况下，如果扔掉现有设备去做大量的硬件升级，这样将造成现有资源的浪费，而且如果再面临下一次业务量的提升时，这又将导致再一次硬件升级的高额成本投入，甚至性能再卓越的设备也不能满足当前业务量增长的需求，因此网络节点间的负载均衡过程很有必要。

[0005] 由此可以看出，如何有效的解决分布式平均共识问题具有重要的实际应用价值。随着通信基础理论研究的不断深入，平均共识问题在国际学术界得到了广泛的关注，对于平均共识问题的研究取得了许多成果。其中，基于Gossip算法的平均共识问题在无线传感器网络中的应用更是研究的热点。该算法通过相邻节点间的信息交换，可以最终使网络中的所有节点获得它们信息的平均值。尽管国内外已经有很多关于无线传感器网络Gossip算法方面的研究成果，但是以前的研究主要侧重于成对Gossip算法(Pairwise Gossip Algorithm)和地理Gossip算法(Geographic Gossip Algorithm)的研究。这两类算法由于在每次更新时只有选定的节点进行数据交换，因此尽管可以使共识收敛于均值，但是却只能用于双向链路，没有很好的利用无线信道的广播特性。直到最近几年，国际上才出现了对于广播Gossip算法(Broadcast Gossip Algorithm BGA)的研究。这类算法中当一个节点广播它的数据时，所有能接收到该数据的节点均可以更新它们的数据。由于不需要反向数据交换，所以这类算法更适合于非对称的无线信道。同时，由于每次数据更新有更多的节点参与，因此这类算法的收敛速度更快。此外，由于广播Gossip算法不再需要随机选择相邻节点，从而使算法更加简单并易于实现。

[0006] 具体到负载均衡问题，由于数字通信链路的信道容量限制以及传感器节点有限的存储能力，需要在共识过程中引入量化步骤，称为量化共识。

发明内容

[0007] 本发明是要解决分布式共识，具体为分布式负载均衡问题从而提出了经过量化的无偏广播Gossip算法。

[0008] 基于量化无偏广播Gossip算法的分布式负载均衡方法包括以下步骤：

[0009] 一、对节点状态值进行初始化并设置无线传感器网络的同步时钟和最大迭代次数；

[0010] 二、无偏广播Gossip算法的迭代和量化过程；

[0011] 三、当迭代次数达到预设最大迭代次数时，结束迭代；此时无线传感器网络中所有节点负载达到均衡，即完成基于量化无偏广播Gossip算法的分布式负载均衡方法。

[0012] 发明效果：

[0013] 本发明涉及一种分布式负载均衡技术，具体利用量化的广播Gossip算法，通过网络节点的本地信息和其邻近节点信息重新分配网络中排队等候需要处理的任务，使得最终需要每个节点处理任务的数量几乎相同，从而达到分布式负载均衡的目的。该技术能够保证网络中所有节点最终达到共识状态。

[0014] 因此本发明提出一种基于量化广播Gossip算法的负载均衡技术。通过性能仿真证明量化广播Gossip算法可以达到共识状态，能够达到负载均衡的目的。

[0015] 在无偏广播Gossip算法(Unbiased broadcast gossip algorithms UBGAs)中，网络中的一个节点随机地被激活，并将自己的状态值进行本地广播。所有该节点的相邻节点都可以接收到该状态值，并和自己的本地状态值进行加权平均。计算后的结果替换掉自己原来的状态信息，就完成了一次更新或一次迭代。在这种方式下，每进行一次迭代就可以使多个节点进行状态值的更新，并且不需要发送自己的状态值给广播节点。这能够克服成对Gossip算法收敛缓慢的缺点，对无线通信的应用更有意义。

附图说明

[0016] 图1是本发明流程图；

[0017] 图2是仿真实验中本发明在100个节点场景下的收敛误差r(t)仿真结果图；

[0018] 图3是仿真实验中本发明在100个节点场景下的收敛速度q(t)仿真结果图；

[0019] 图4是仿真实验中本发明在500个节点场景下的收敛误差r(t)仿真结果图；

[0020] 图5是仿真实验中本发明在500个节点场景下的收敛速度q(t)仿真结果图。

具体实施方式

[0021] 具体实施方式一：本实施方式的基于量化无偏广播Gossip算法的分布式负载均衡方法包括以下步骤：

[0022] 一、对节点状态值进行初始化并设置无线传感器网络的同步时钟和最大迭代次数；

[0023] 二、无偏广播Gossip算法的迭代和量化过程；

[0024] 三、当迭代次数达到预设最大迭代次数时，结束迭代；此时无线传感器网络中所有节点负载达到均衡，即完成基于量化无偏广播Gossip算法的分布式负载均衡方法。

[0025] 具体实施方式二：本实施方式与具体实施方式一不同的是：所述步骤一具体为：

[0026] (一)将无线传感器网络作为一个随机的几何图模型G(N,R)，N代表传感器节点个数，R为连通半径，N个传感器节点均匀地分布在网络中；这N个传感器节点的拓扑结构用N×N的相邻矩阵A表示，如果两个节点i和j间的欧氏距离小于传输半径R，则认为两个节点是彼此相邻的，可以直接通信，则令Aij＝1；否则，两个节点是不相邻的，不能直接进行通信，则令Aij＝0；当i＝j时，i和j代表同一个节点，则令Aij＝0；令Ni＝{j∈{1,2,…,N}:Aij≠0}表示节点i的所有相邻节点；

[0027] (二)无线传感器网络中的每个节点i保存有两个变量，一个是当前网络状态平均值的估计值xi(t)，另一个为伴随变量yi(t)；由传感器测得的每个节点的初始状态值xi(0)为初始时刻每个节点i的负载数量，并设置伴随变量yi(0)＝0；同时采用量化算法Q(·)对xi(0)进行量化得到量化后的初始值

[0028] (三)在无线传感器网络中设置统一定时器，所述定时器的计数值满足指数分布，同时设置最大迭代次数。

[0029] 其它步骤及参数与具体实施方式一相同。

[0030] 具体实施方式三：本实施方式与具体实施方式一或二不同的是：所述步骤二中无偏广播Gossip算法的迭代和量化过程具体为：

[0031] 1)启动定时器，开始计时：当开始本轮迭代时，判断当前迭代次数是否已达到最大值，若未达到最大值，则进入本轮迭代过程；若已达到最大值，则退出迭代过程；

[0032] 2)在本轮迭代过程中，判断节点的定时器计数值是否已满：若在时刻t节点k的计时期满则该节点被随机唤醒，否则节点不会被唤醒并进入等待接收状态；被唤醒的节点k向全网广播它的当前量化状态值 和量化伴随变量值 同时节点k更新t+1时刻自己的最终状态值为

[0033] 3)判断其他未被唤醒的节点是否会在t时刻接收到节点k的广播信息：若未接收到节点k的广播信息，令这些节点为 则进入步骤4)；若接收到节点k的广播信息，令这些节点为 则这些节点按照以下方法更新自己t+1时刻的状态信息xj(t+1)和yj(t+1)：

[0034]

[0035] 其中 和 分别代表节点i的内邻集合和外邻集合，这里V＝{1,2,…,N}为节点集合，E为边集合；并且定义 为节点k的出度，为节点j的入度，符号|X|c代表取集合X的势；

[0036] 随后， 节点按照量化算法Q(·)对xj(t+1)和yj(t+1)经行量化，得到t+1时刻的量化值 和

[0037] 这种量化规则使得对于所有的 成立；

[0038] 之后， 节点按照以下方法消除 和 的累计量化误差，作为本次迭代的最终状态更新值；

[0039]

[0040]

[0041] 4)未在时刻t接收到k节点的广播信息的那些 节点保持其当前量化状态值不变，即

[0042] 5)当所有节点完成本轮的量化无偏广播Gossip算法的迭代更新和量化过程后，迭代次数加一，重复步骤1)～步骤4)，进入下一轮迭代。

[0043] 其它步骤及参数与具体实施方式一或二相同。

[0044] 具体实施方式四：本实施方式与具体实施方式一至三之一不同的是：所述无偏广播Gossip算法的量化过程具体为：

[0045] (一)无偏广播Gossip算法

[0046] 当某节点k在t时刻被激活时，它将会把它的这两个变量xk(t)和yk(t)同时广播给它的相邻节点 所有 节点收到这两个状态值并按如下规则更新自己的状态信息

[0047]

[0048]

[0049] 其中 和 分别代表节点i的内邻集合和外邻集合，这里V＝{1,2,…,N}为节点集合，E为边集合；并且定义 为节点k的出度， 为节点j的入度，符号|X|c代表取集合X的势；

[0050] 发送节点k更新自己的状态值为

[0051] xk(t+1)＝xk(t)  (3)

[0052] yk(t+1)＝0  (4)

[0053] 所有其他 保持当前节点信息不变，即

[0054] xi(t+1)＝xi(t)  (5)

[0055] yi(t+1)＝yi(t)  (6)

[0056] 上述(1)-(6)广播Gossip更新过程可以写成如下向量形式

[0057]

[0058] 当节点k在时刻t广播信息时，W(t)是一个随机矩阵，即

[0059]

[0060] (二)对无偏广播Gossip算法进行量化

[0061] 在t＝0时刻，每个节点初始化各自的状态值xi(0)和伴随变量yi(0)＝0，量化其状态值得到 当节点k在时刻t被唤醒时，k广播它的当前量化状态值 和量化伴随变量值 所有 的节点接受到k的广播信息后按如下规则更新自己的状态信息

[0062]

[0063]

[0064] 之后xj(t+1)和yj(t+1)被量化为

[0065]

[0066]

[0067] 发送节点k更新自己的状态值为

[0068]

[0069]

[0070] 所有其他 的节点保持其量化状态值不变，即

[0071]

[0072]

[0073] 至此，第t次迭代更新过程完成，量化无偏广播Gossip算法(QUBGA)的更新过程(9)-(16)写成如下矩阵形式

[0074]

[0075]

[0076] 这里Q(·)代表量化运算，具体的量化过程为， 使 映射到它的最近整数值，这种量化规则使得对于所有的 成立；

[0077] (三)消除量化误差

[0078] 量化共识的每一轮迭代过程中都存在量化误差 即表示第i个节点在第t次迭代更新过程中实值与量化值的差值；将每次迭代产生的量化误差累计，得到累计量化误差 消除累积量化误差的过程为：首先， 节点
完成t时刻的量化共识后同时更新本轮的累计量化误差；之后，节点j查询自己当前t+1时刻的累计量化误差值xj,sum_error(t+1)；最后， 节点利用该值按照如下规则修正本轮的量化共识值

[0079] 如果

[0080] 如果以此消除量化过程带来的误差。

[0081] 其它步骤及参数与具体实施方式一至三之一相同。

[0082] 仿真实验：

[0083] 为了更好的对本专利所提算法进行性能分析和比较，现与国际上已有的经典广播Gossip算法BGA经行比较，并将其量化算法命名为QBGA。在下面的性能分析中，网络中分别有100和500个节点，并由它们生成随机几何图，迭代次数为80000次。下面分别从收敛误差和收敛速度两个方面来分析算法的性能。

[0084] 首先定义两个衡量指标：

[0085] (1)量化广播Gossip算法的标准偏差，代表收敛误差。表达式如下：

[0086]

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

[0088] (2)量化广播Gossip算法的方差，代表收敛速度。表达式如下：

[0089]

[0090] 从公式(23)不难看出，q(t)度量了每次迭代时每个节点当前负载数的方差。当节点形成共识时，q(t)将收敛于0。因此，q(t)收敛于0的速度可以衡量算法的收敛速度。

[0091] 图2和图3分别代表算法在100个节点场景下的收敛误差和收敛速度仿真结果，图4和图5分别代表算法在500个节点场景下的收敛误差和收敛速度仿真结果。从仿真结果可以看出，1)QUBGA的收敛误差小于QBGA的收敛误差。具体的，QUBGA最终可以收敛于初始均值，收敛误差小。QBGA也可以达到共识状态，但无法保证最终收敛于所有节点的初始均值，收敛误差大；2)QBGA的收敛速度较快，但这是以较大的收敛误差为代价的。QUBGA的收敛速度与QBGA相当，但其收敛误差明显小于QBGA的收敛误差。综合以上因素可以看出，在高精度场合要求下，QUBGA算法具有明显的优势。

[0092] 综上，对于分布式负载均衡应用，需要保证最终每个节点的任务数量几乎一致，以此达到共同分担任务的目，因此需要最终的共识状态以较高精度收敛于所有节点初始值的均值。从以上仿真分析不难看出，本专利提出的QUBGA算法收敛误差最小，而且收敛速度较快，符合分布式负载均衡的应用要求，因此具有最优的工程实践价值。