赵廷磊, 乔建忠, 林树宽, 王彦华
东北大学 计算机科学与工程学院, 辽宁 沈阳 110169
收稿日期：2017-10-27
基金项目：国家自然科学基金资助项目(61402442)；辽宁省软件系统开发与应用重点实验室项目。
作者简介：赵廷磊(1983-), 男, 甘肃白银人, 东北大学博士研究生;
乔建忠(1964-), 男, 辽宁兴城人, 东北大学教授，博士生导师。

摘要：为了改善分布式系统中负载分布不平衡对性能的影响, 提出并实现了一个基于控制理论的时滞脉冲切换负载平衡模型.该模型根据节点资源的动态性建立了相关子系统.当节点状态发生改变时触发子系统的切换, 并根据负载迁移规则对过量负载进行迁移, 迁移比例根据节点的实时运行状态进行计算.节点仅在此时才进行信息广播, 降低了通信开销, 提升了动态负载平衡的效率.给出了相应的负载平衡算法, 并在实际平台上进行了验证.实验结果表明, 与其他负载平衡算法相比, 本模型算法使负载平衡时间平均减少29.82%.
关键词：负载迁移节点状态脉冲切换系统动态负载平衡分布式系统
An Adaptive Dynamic Load Balancing Model
ZHAO Ting-lei, QIAO Jian-zhong, LIN Shu-kuan, WANG Yan-hua
School of Computer Science & Engineering, Northeastern University, Shenyang 110169, China
Corresponding author: ZHAO Ting-lei, E-mail:zhaotinglei_0928@163.com
Abstract: The grasp of the moving capability of a robot is crucial to the motion planning and control of the robot. The moving capability of a hexapod robot which is used over rugged terrains is thus analyzed. First, the hexapod robot platform as well as the system design is introduced. Then, the kinematic models of the hexapod robot leg and the parallel mechanism consisting of the robot torso and each support leg are built respectively. Their workspaces are also analyzed. Finally, the hexapod robot simulation platform with a rugged terrain is built based on Adams and Matlab, and the motion simulation with the hexapod robot is performed. Results show that, through reasonable motion planning that takes account of both the moving capability and terrain profiles, it is possible to effectively enhance the mobility of a hexapod robot over rugged terrains.
Key words: load migrationnode stateimpulsive and switching systemdynamic load balancingdistributed system
负载平衡是分布式系统的一个重要研究领域, 节点间负载的不平衡会严重影响工作效率.在分布式系统中, 每个节点可多次提交不同类型的新任务并动态地加入和退出^[1].处理大规模任务时, 将任务划分为多个子任务并分配到各个节点处理, 返回的结果由系统重新融合.若某些节点繁忙不能及时返回结果, 将严重影响系统性能.现有的负载平衡研究分为以下几个方面:1)通过使用典型的控制模型进行负载平衡^[2].分布式控制模型的主要特征是节点之间可以自主地相互协调以进行任务分配.通过模型控制可以适应不同的系统规模, 并允许一些节点出现故障, 因此鲁棒性很高.但由于每个节点只能知道相邻节点的信息, 结果可能只是局部最优的.节点之间的协商会产生额外的计算成本.2)负载平衡中的一些典型的资源优化方法.其中, 自主资源优化方法^[3]只考虑节点本身的资源, 忽略节点之间资源的协调, 该方法仅在大多数节点可以自主完成分配的任务的情况下才能很好地执行.基于资源的上下文优化方法^[4]考虑了节点之间的协调, 适用于协作分布式系统, 但是这些优化方法需要大量的计算, 在大规模系统中会产生高成本.3)实现负载平衡可靠性有基于冗余的方法^[5]和基于非冗余的方法^[6].针对某些特殊情况, 使用启发式方法以最低的成本实现理论上可靠的性能.4)利用典型协调机制对异构节点之间进行协调以便实现负载平衡.异构节点之间的协调机制常用博弈论^[7]和图论^[8].节点的角色总是假定在任务分配和执行期间保持固定.节点可以动态地改变在系统中的角色, 根据自己的策略进行单独决策.5)根据网络结构的特征在不同的网络拓扑结构中实现负载平衡.网络结构影响了节点之间的协调以及执行任务.通常有两种网络结构:节点通过物理通信网络结构互连^[9], 在任务分配中应考虑节点的资源和位置；节点通过虚拟交互网络结构互连^[10].
本文结合脉冲切换系统模型和时滞系统模型的特点针对分布式动态负载平衡过程提出了一个时滞脉冲切换负载平衡模型.该模型是由4个连续的子系统构成的一个连续-离散系统.在进行负载迁移时, 根据本节点和其他所有节点的处理能力计算迁移比例, 只有空载和轻载节点接收迁移的负载, 同时兼顾了各状态的节点.节点状态改变时通过脉冲信号切换系统, 并在此时广播节点信息, 降低通信开销, 提高负载平衡的效率.
1 时滞脉冲切换负载平衡模型本系统包含多个连续的子系统, 子系统之间是离散的, 属于连续-离散系统.每个节点在不同时刻根据自身状态对应不同的子系统, 各个子系统在状态改变时触发切换.不同的子系统交替发生、相互作用, 最终使系统达到平衡状态, 并使性能得到改善.
1.1 时滞脉冲切换负载平衡过程描述分布式系统中一个典型的时滞脉冲切换负载均衡过程可由图 1来描述.节点2为重载节点, 它将过量负载迁移到轻载节点3和空载节点4上执行.最终各节点均处于适载状态, 系统达到平衡.
图 1(Fig. 1)

图 1 4节点分布式系统的时滞脉冲切换负载均衡过程Fig.1 Process of time delay impulsive switching load balancing model for distributed system with 4 nodes

1.2 时滞脉冲切换负载平衡模型系统由n个节点P_i(0≤i≤n-1)组成.定义P_i的处理能力a_i是P_i的核心数Nc_i, 频率F_i, 内存M_i和当前利用率U_i(t)的综合指标：

(1)

其中:Ξ_i=Nc_i(F_i+εM_i), ε=0.2;α=0.2;β=0.55.
定义1(节点状态判断依据):当节点P_i的负载分别满足条件w_i < w^inf, w^inf < w_i < w^sup, w_i>w^sup或w_i=0时, P_i为轻载、适载、重载或空载节点.其中, w^sup=w′_i(1+ξ), w^inf=w′_i(1-ξ), ξ=0.05.
节点P_i的负载为w_i(0≤i≤n-1), 在子系统的第k个驻留时间段[t_k, t_k+1)内所能处理的负载为理想负载w′_i.系统启动时, 节点P_i将其状态和负载信息进行广播, 并收集其他节点的信息.节点P_i使用式(2)计算系统当前状态.

(2)

当state=1时, 系统超载, 使用w′_i=ωw′_i对w′_i进行处理, 则state转换为0.当state=0时, 使用时滞脉冲切换负载均衡模型(3)处理.

(3)

其中:w_i(t)∈Rⁿ是系统的状态变量, 表示节点P_i的负载队列长度；σ_i(k)为节点P_i在第k个时间段[t_k, t_k+1)内被激活的子系统, t_k+1-t_k是子系统的驻留时间；Γ_OLN, Γ_MLN, Γ_LLN和Γ_ELN表示重载、适载、轻载和空载状态分别对应的子系统σ₁, σ₂, σ₃和σ₄；σ_l(l=1, 2, …, 4)在[t₀, t]内驻留的总时间为T_l；切换时刻序列满足0≤t₀ < t₁ < …t_k < t_k+1 < …；系统时滞τ_i>0；f是一个分段连续向量值函数, f(t, 0, 0)≡0, t∈R⁺；Δw_i(t_k+1)表示状态跃变；初值条件为w_i(θ)=w_i(t₀)；w_i:[t₀-τ_i, t₀]→Rⁿ除了有限个点t外是连续的, 而在t处满足w_i(t⁺)和w_i(t^-)存在并相等；w_i(t₀)表示节点P_i在初始时刻负载队列的长度.
定义2(负载迁移规则):对于处于状态σ_i(k)和σ_j(k)的任意两个节点P_i和P_j, 负载按{|σ_i(k)=Γ_OLN, σ_j(k)∈{Γ_LLN, Γ_ELN}}进行迁移.其中u_i表示单位时间内从节点P_i上迁移到节点P_j上的过量负载.
节点的a_i不同, 每次迁移的负载量各不相同, 对节点性能的影响也各不相同.若按固定划分, 会使节点的状态发生频繁的转换. a_i较小的节点应该比a_i较大的节点每次接收的负载量要少, 因为其w′_i较小，当超过w′_i时, 系统的状态将发生变化.为了保证系统的稳定性, a_i较大的节点每次迁移出的负载量不宜过大.因此, 使用式(4)计算适合的负载迁移比例p_i.

(4)

根据定义1判断节点的状态, 当节点P_i处于重载状态时, 除了处理自身任务和生成新任务外, 只将自身过量负载迁移给轻载和空载节点P_j，而不再接收其他节点迁移的负载.迁移过程按照负载迁移规则进行, 负载迁移比例根据式(4)计算.针对该过程使用控制理论建立子系统模型, 其状态空间具体描述如下:

(5)

当节点P_j处于轻载状态时, 除了处理自身任务和生成新任务外, 只接收其他重载节点P_i迁移的负载, 而不再对自身的负载进行迁移.若接收到了迁移负载, 其状态空间具体描述为式(6).若没有接收到迁移负载, 则根据式(7)进行状态转换.

(6)

当节点P_i处于适载状态时, 只处理自身任务和生成新任务, 既不接收其他节点迁移的负载, 也不对自身的负载进行迁移.其状态空间具体描述为

(7)

当节点P_j处于空载状态时, 只接收其他重载节点P_i迁移的负载, 而自身没有可处理的任务, 也没有新任务生成, 也不迁移负载.若接收到了迁移负载, 其状态空间具体描述为式(8).若没有接收到迁移负载, 节点状态不改变.

(8)

式(5)~(8)中:状态变量w_i表示节点P_i的负载队列长度；输入变量u_i表示单位时间内从节点P_i上迁移到其他节点上的过量负载；输出变量y_i表示节点P_i上的过量负载；w′_i表示节点P_i的理想负载队列长度；k_i表示单位时间内负载平衡系统的闭环增益；p_i表示节点P_i的负载迁移比例；η_ij表示节点P_i到节点P_j的传输时延；ν_i, μ_i分别表示节点P_i的任务生成率和处理率, 使用式(9)和式(10)计算:

(9)

(10)

其中，r_i∈R⁺, 其值由负载的固有属性确定.
2 时滞脉冲切换负载平衡算法1) 根据式(1)计算系统中节点P_i的处理能力a_i.
2) 依据定义1判断节点P_i所处的状态, 并计算节点P_i的理想负载w′_i.
3) 依据式(2)判断系统当前状态.当系统超载时, 对理想负载w′_i进行处理.
4) 根据定义2对系统中处于Γ_OLN状态的重载节点进行负载迁移.使用式(4)计算适合的负载迁移比例p_i.根据式(11)计算单位时间内从节点P_i上迁移到节点P_j上的过量负载.

(11)

5) 根据定义1判断节点P_i所处的状态, 如果系统中还存在重载节点, 返回步骤4).否则, 负载平衡过程结束.
动态负载平衡算法如下.
初始化:定义系统规模, 计算每个节点的理想负载和状态, 定义负载均衡的起始条件和结束条件.
当(重载节点数z >0)
{如果(重载节点P_i中包含的u_ij的数量u大于空载节点数k和轻载节点数q之和)
在传输时延η下, 节点P_i将每个大小为u_ij的负载传输给空载节点和轻载节点.
否则, 如果(重载节点P_i中包含的u_ij的数量u小于等于空载节点数k)
????在传输时延η下, 节点P_i随机选择u个空载节点, 并将每个大小为u_ij的负载传输给这u个空载节点.
????否则
????在传输时延η下, 节点P_i随机选择u-k个轻载节点, 并将每个大小为u_ij的负载传输给这u-k个轻载节点和所有空载节点.
}
更新节点的信息, 输出结果.
3 实验结果与分析在Intel Core i7平台上对CloudSim仿真框架做出扩展并进行实验. CloudSim是墨尔本大学Rajkumar Buyya教授团队开发的云计算仿真器, 是一个通用、可扩展的新型仿真框架, 支持无缝建模和模拟, 对不同应用和服务模型的调度和分配策略的性能进行量化的比较, 达到控制使用云计算资源的目的^[11].
实验环境:Win8操作系统, JDK1.8版本, CloudSim3.0.3版本, Eclipse 4.7.1a.根据实验要求, 对主机和VM相关参数进行配置, 如表 1所示.
表 1(Table 1)

表 1 主机和VM参数描述Table 1 Host and VM parameters 参数 描述 hostId 主机ID, 分别为1, 2, 3, 4. CPU Intel Core i7-4712MQ hostram 主机内存, 8 GB hostmips 主机每秒执行百万条指令数, 在2.66 GHz下对应49000 DMIPS. Vmid 虚拟机ID, 分别为1, 2, 3, 4. vmmips 根据式(1)计算每个虚拟机的处理能力, 再转化为其对应的MIPS. vmram 虚拟机内存, 分别为4, 2, 4, 2 GB. bw 带宽为1000 Mb/s

表 1 主机和VM参数描述 Table 1 Host and VM parameters

按照CloudSim的实验步骤, 在创建DataCenter和PowerDataCenter时对其进行扩展, 实现所需的任务调度算法.
为了便于分析系统中各节点状态及队列长度的变化, 以4个节点为例进行分析说明. 4个节点的初始队列分别为w₁=420, w₂=980, w₃=1500, w₄=0.图 2描述了各个节点的状态及队列长度的变化.
图 2(Fig. 2)

图 2 负载平衡过程中节点的队列长度和状态变化Fig.2 State and queue length change of nodes in the process of load balancing

从图 2中可以看到, 各节点状态及队列长度变化发生在T1=17.723 ms, T2=22.366 ms, T3=25.001 ms, T4=27.431 ms和T5=29.057 ms时刻.在初始时刻T0, 统计每个节点的瞬时负载信息和节点状态, 并判断系统状态, 根据式(2)对理想负载进行处理; 各节点线程计算本节点处理能力a_i和理想负载w′_i.初始时刻各节点分别处于适载、重载、轻载和空载状态.节点2分别给节点3和节点4迁移一个单位的负载u₂(T1).迁移后在T1时刻节点4转变为轻载状态.但是由于节点3的处理能力远强于节点2, 所以接收到的一个单位的负载u₂(T1)后不会对其状态产生影响.节点2继续给节点3和节点4迁移一个单位的负载u₂(T2).由于节点2迁出单位变小, 因此在T2时刻的w₂落差明显低于T1时刻, 此时没有轻载和空载节点.所以重载节点2不迁移负载.所有节点均处理自己的负载.到T3时刻, 节点1和4转变为轻载状态.节点2开始分别给这2个节点迁移一个单位的负载u₂(T4).在T4时刻, 4个节点变为重载、适载、适载和适载状态.由于u₁(T4)升高导致处理能力a₁降低, 从而使w′降低, 因此节点1成为了重载节点.各节点均处理本节点的负载不迁移也不接收.到T5时刻, 系统中不存在重载节点, 达到平衡状态.
为了证明本模型和算法的有效性, 不仅与传统算法中的均分负载算法和二分负载算法进行比较, 还与使用典型的控制模型实现负载平衡的DDLB算法^[1]进行比较, 系统的负载平衡时间如图 3所示.
图 3(Fig. 3)

图 3 几种负载平衡算法比较Fig.3 Comparison of different load balancing algorithms

从图 3中可以看出, 在不同规模下, 本模型算法所需的负载平衡时间均比其他算法少.二分负载算法中, 因为每次按网络中的节点数将网络划分为两个子网络, 然后按照两个子网络的处理速度之比将负载进行迁移, 递归上述过程, 直到系统达到平衡状态, 该过程对负载多次重复迁移, 产生较大的数据传输代价.与其比较, 本模型负载平衡时间减少了62.21%.均分负载算法和DDLB算法均没有考虑负载迁移节点与其他节点的处理能力, 也没有考虑负载接收节点的状态, 导致过量负载被多次迁移, 但是与二分负载算法相比迁移次数减少很多.与均分负载算法和DDLB算法相比, 本模型负载平衡时间分别减少了18.11%和9.14%.
负载平衡过程中, 在负载进行迁移时所产生的数据传输开销对系统最终达到负载平衡所需的时间影响较大.图 4为几种负载平衡算法的数据传输代价的比较图.
图 4(Fig. 4)

图 4 数据传输代价Fig.4 Data transmission cost

从图 4中可以看出, 本模型所采用的算法在各种规模下的数据传输开销都是最小的, 这是因为在负载迁移过程中, 以每个节点的处理能力和节点当前所处的状态为依据, 将重载节点的负载按照合适的比例迁移到相应的节点上, 既不会将负载迁移到其他重载节点上, 同时尽量避免了负载的重复迁移, 降低了系统的数据传输代价.DDLB算法中每个重载节点以增益k将过量负载按固定划分比例平均迁移给其他所有节点, 同时接收其他节点迁移出的过量负载, 导致系统中每个节点频繁迁出迁进负载, 使重载节点负担加重, 但是它重复迁移的负载比均分负载和二分负载算法少.
4 结论本文采用控制理论思想对分布式动态负载均衡过程提出了一个基于状态空间描述的时滞脉冲切换负载平衡模型.对系统中每个节点的不同状态建立对应的子系统.在进行负载迁移时, 综合考虑本节点和其他所有节点的处理能力, 不会导致迁移后出现更多的重载节点, 有效平衡节点负载, 提高了负载均衡的效率.通过实验分析, 本模型算法使负载平衡时间平均减少29.82%.今后将采用Lyapunov泛函方法对本系统进行稳定性分析, 分析其对负载平衡的影响.
参考文献

[1]	Meng Q Y, Qiao J Z, Lin S K, et al.A delay-based dynamic load balancing method and its stability analysis and simulation[C]//Proceedings of European Conference on Parallel Computing.Ischia, 2010: 192-203.
[2]	Shah R, Veeravalli B, Misra M. On the design of adaptive and decentralized load-balancing algorithms with load estimation for computational grid environments[J].IEEE Transactions on Parallel and Distributed Systems, 2007, 18(12): 1675–1686.DOI:10.1109/TPDS.2007.1115
[3]	Xu J, Lam A, Li V. Chemical reaction optimization for task scheduling in grid computing[J]. IEEE Transactions on Parallel and Distributed Systems, 2011, 22(10): 1624–1631.DOI:10.1109/TPDS.2011.35
[4]	Jiang Y C, Zhou Y F, Li Y P. Reliable task allocation with load balancing in multiplex networks[J]. ACM Transactions on Autonomous and Adaptive Systems, 2015, 10(1): 1–32.
[5]	Kang Q M, He H, We J. An effective iterated greedy algorithm for reliability-oriented task allocation in distributed computing systems[J].Journal of Parallel and Distributed Computing, 2013, 73(8): 1106–1115.DOI:10.1016/j.jpdc.2013.03.008
[6]	Faragardi H R, Shojaee R, Keshtkar M A, et al.Optimal task allocation for maximizing reliability in distributed real-time systems[C]//Proceedings of the IEEE/ACIS 12th International Conference on Computer and Information Science.Niigata, 2013: 513-519.
[7]	Subrata R, Zomaya A, Landfeldt B. Game-theoretic approach for load balancing in computational grids[J].IEEE Transactions on Parallel and Distributed Systems, 2008, 19(1): 66–76.DOI:10.1109/TPDS.2007.70710
[8]	Bajaj R, Agrawal D. Improving scheduling of tasks in a heterogeneous environment[J].IEEE Transactions on Parallel and Distributed Systems, 2004, 15(2): 107–118.DOI:10.1109/TPDS.2004.1264795
[9]	Jiang Y C, Li Z F. Locality-sensitive task allocation and load balancing in networked multiagent systems:talent versus centrality[J].Journal of Parallel and Distributed Computing, 2011, 71(6): 822–836.DOI:10.1016/j.jpdc.2011.01.006
[10]	Jiang Y C, Zhou Y F, Wang W Y. Task allocation for undependable multiagent systems in social networks[J].IEEE Transactions on Parallel and Distributed Systems, 2013, 24(8): 1671–1681.DOI:10.1109/TPDS.2012.249
[11]	Kumar R, Sahoo G. Cloud computing simulation using CloudSim[J].International Journal of Engineering Trends and Technology, 2014, 8(2): 82–86.DOI:10.14445/22315381/IJETT-V8P216