基于双目标优化的服务器负载均衡方法

    专利查询2023-09-11  114



    1.本发明属于服务器集群负载均衡领域,具体涉及基于双目标优化的服务器负载均衡方法。


    背景技术:

    2.近年来,网络智能化快速发展,主要表现在互联网的用户访问量和网络流量的迅速增长,据有关调查结果显示,截止2020年6月,我国网络用户已达9.4 亿人。网络的发展与人们的生活息息相关,尤其体现在逐渐兴起的智能家居、智能企业、智能高速等其它物联网产业,另外手机、ipad和电脑等终端设备的普及也是造成网络迅速发展的原因。那么随之而来的问题是,当过多用户请求在同一时间访问同一资源时,如果服务器端不能够对请求进行及时的处理,会导致服务器出现过载和宕机崩溃等问题,严重影响用户的上网体验,因此单一服务器已经不再能够满足用户的复杂需求,则需要服务器集群系统来替代单一服务器统一对外进行工作。怎样将网络请求合理的分配到各个服务器上,是集群领域的研究学者们一直不断思考的问题。
    3.负载均衡技术是集群工作中重要的技术之一,目的是能够将任务请求合理地分发到集群中各个服务器,使得各个服务器的性能能够充分发挥,实现任务请求完成时间最小和集群更高的吞吐量。随着集群技术的不断发展,传统的负载均衡算法已经不能满足用户对于服务器端负载均衡的需求,越来越多的学者将其与优化组合、神经网络、元启发式算法等结合起来进行研究,用以实现更加复杂的负载均衡效果。
    4.本发明中所涉及的布谷鸟搜索算法是元启发式算法中的一种,它依赖于布谷鸟自身的繁衍规律,将优化模型中的问题原型比拟成布谷鸟群体行为,构建目标函数,通过迭代寻优的方式进行问题的求解。因布谷鸟搜索算法具有收敛速度较快、体量轻、不易陷入局部最优等特点,自出现以来,一直被研究学者所喜爱。


    技术实现要素:

    5.本发明要克服现有技术的上述缺点,提供一种基于双目标优化的服务器负载均衡方法。
    6.本发明为了减少任务请求的完成时间,缩小集群中各服务器之间的处理时间差异,提高集群中负载均衡性能,满足用户多样性需求,将集群中负载请求分配优化问题转化成与任务请求处理时间有关的两个目标函数,并添加约束条件;然后采用元启发式布谷鸟搜索算法对集群负载均衡问题进行优化求解,并通过改进步长的方式对算法进行改进,最终找到一组合适的请求分配编码方案。
    7.本发明采用的技术方案如下:
    8.本发明提出的基于双目标优化的服务器负载均衡方法,包括以下步骤:
    9.s1.确定一次请求分配过程中处理服务器的个数,根据时间节点中并发请求的数量采用滑动窗口获取任务请求的个数。
    10.s2.获取服务器的实时状态信息包括量化集群中节点服务器的综合处理能力和任务请求到来时刻各服务器的资源使用量;服务器的综合处理能力与cpu频率、内存容量、网络带宽和磁盘读写速度有着直接的关系,表示成:
    11.p=α1*p
    cpu
    +α2*p
    memory
    +α3*p
    band
    +α4*p
    i/o (1)
    12.式中,αi表示各参数对服务器处理能力的影响权重,满足于与服务器的配置信息有着直接的联系,权重越大说明该参数对服务器性能的影响更显著。
    13.服务器的资源使用量与cpu频率、内存容量、网络带宽和磁盘读写速度也是密切相关的,线性表示成:
    14.c=β1*c
    cpu
    +β2*c
    memory
    +β3*c
    band
    +β4*c
    i/o (2)
    15.式中,βi表示各参数对服务器处理能力的影响权重,满足于参数大小与αi一致。
    16.s3.采用0-1矩阵对任务请求与处理服务器之间的关系进行编码,通过一个矩阵来表示:
    17.在一组分配任务中,编码矩阵中的一行代表一个任务,所在元素为1的位置表示服务器的所在序号。例如,矩阵本组分配是将5个任务合理地分配到3台节点服务器。例如,001表示第3个任务被划分到第3台节点服务器进行处理,每次任务分配目的就是找到一个最优的编码矩阵,将这个编码矩阵用d来表示。
    18.s4.构造集群负载请求分配优化问题的目标函数,表示成:
    [0019][0020]
    式中,t(sj)表示每台处理服务器完成该组任务分配所耗费的时间,其中j∈ (0,n),表示集群中处理服务器的标号。σ表示一组分配任务请求中服务器的处理时间差异,可以通过以下表示:
    [0021][0022]
    上述公式中,表示的是集群中每台服务器的平均任务完成时间;σ表示集群中各服务器处理时间的方差,σ数值越小越好。约束条件可以表示成:
    [0023][0024]
    式中,表示编码矩阵d中的每一行元素之和,d
    i*j
    取值只能为0 或1,当d
    i*j
    为1时表示任务请求在所选的节点服务器进行被处理;又因同一组任务中,每个任务有且仅能选择一台处理服务器,所以在编码矩阵中的行向量中,至多存在一个元素为1。表示任务请求到来时选择处理服务器的限制条件。表示节点服务器的资源剩余量。监控节
    点服务器的资源信息,当资源使用率小于某个阈值c时能够说明该节点服务器能够接受更多的任务请求。
    [0025]
    s5.使用布谷鸟搜索算法对提出的问题进行迭代优化求解,输出编码解集。将集群中的任务调度问题转化成鸟群迭代寻找最优鸟巢位置进行孵卵的过程,包括以下几个部分:
    [0026]

    设置鸟巢寻优的初始参数,包括鸟巢的个数、最优迭代次数、以及布谷鸟发现外来鸟蛋的概率pa,确定适应度函数为目标函数。
    [0027]

    初始化鸟群。
    [0028]
    采用随机的方式生成数量为n的初始鸟群d
    _cell
    ,表示成:d
    _cell
    = [d1,d2,d3,

    ,d
    n-1
    ,dn],其中每一个编码矩阵都代表一个调度方案。
    [0029]

    计算适应度值。
    [0030]
    通过采集到服务器的参数进行量化处理服务器的综合处理能力和负载信息,计算适应度函数值,更新初始鸟群,。
    [0031]

    鸟群迭代。当未满足最大迭代次数时便开始进行种群的迭代以找到较优的鸟巢位置。
    [0032]

    采用改进莱维飞行的方式更新鸟巢的位置。
    [0033]
    在布谷鸟群体生活中,布谷鸟寻找合适产卵鸟巢的方式是随机的,但服从一种特殊的移动轨迹,即在一定短时间移动距离较短,长时间内出现一次移动距离较长的情况,服从莱维分布,表达式为:
    [0034][0035]
    式中,l(λ)~u=t-λ
    ,λ为移动步长,取值为1《λ≤3。
    [0036]

    进一步的,为了更好进行快速搜索和局部精准搜索,引入参数动态参数β对步长进行适度调整,β可表示成:
    [0037]
    β=θ(iter
    max-t)+β
    0 (7)
    [0038]
    式中,iter
    max
    表示算法设置的最大迭代次数,t表示当前的迭代次数,θ表示的是变化幅度。β0控制步长不为0。其中θ和β0是由求解问题规模的大小决定的。继而得到新的表达式为:
    [0039][0040]

    对比当代鸟巢与上一代鸟巢的位置,得到较优的鸟巢d
    best

    [0041]

    通过发现概率pa进行筛选鸟群。若满足(0,1)的随机数r》pa,则对d
    best
    进行再一次的随机寻优,得到较优的鸟巢。
    [0042]

    循环迭代终止。当达到迭代次数时,停止迭代,输出较优全局最优的鸟巢位置,否则从步骤

    开始,继续迭代。
    [0043]
    s6.输出合适的编码方案。严格意义上来讲优化结果中最优适应度函数值可能是一个或多个fit
    best
    ,即存在一个pareto解集,每一个fit
    best
    会对应一个编码方案。
    [0044]
    s7.对方案进行解码,找到最终的任务请求与处理服务器之间的关系,调度机制会随机选择一个编码方案进行任务调度。
    [0045]
    优选地,步骤s2中设α1~α4取值分别0.5,0.2,0.2和0.1。
    [0046]
    本发明的有益效果是:
    [0047]
    在解决集群负载均衡问题上,本发明能够结合布谷鸟搜索算法的特性与集群中节点服务器的处理性能,更快速地为网络请求规划到合理的服务器资源,减少资源的浪费,并能够大大缩短网络请求响应时间,减少任务失败率,使得资源分配更加合理。最为有效的是对布谷鸟搜索算法中莱维飞行的移动步长进行合理改进,使其更适用于解决集群中负载均衡分配的问题,使整个解决方案更高效和准确。
    附图说明
    [0048]
    图1本发明方法的流程图。
    [0049]
    图2是本发明的实施例的编码图。
    [0050]
    图3是本发明的实施例的pareto解集图。
    具体实施方式
    [0051]
    为了更清晰地讲解本发明技术方案,下面通过结合附图和实施例的方式介绍本发明的具体实施过程,注意的是,本发明所提出的实施例仅仅为了更好的解释本发明,并不限定于本发明。
    [0052]
    本发明提出一种基于双目标优化的服务器负载均衡方法,实施例流程如图1 所示,具体的实施步骤如下:
    [0053]
    (1)确定一次请求分配中处理服务器和任务请求的数量,在实际的集群系统中,并发请求大量出现时,为了防止集群因短时间内流量聚集引起的系统崩溃问题,采用流量控制方式进行控流。本发明当中,大量任务请求出现时,将所有请求存入队列,并采取滑动窗口技术进行获取即将分配的任务请求数量为12个。处理服务器数量设置为7个。
    [0054]
    (2)利用服务器监控系统获取服务器实时的初始状态信息。集群中处理服务器的初始状态信息决定服务器现阶段的处理能力和当前时刻接收新的任务请求的能力,是新的任务请求进行选择处理服务器的主要衡量标准。
    [0055]
    服务器的综合处理能力主要与cpu频率、内存容量、网络带宽和磁盘读写速度有着直接的关系,表示成公式(1):
    [0056]
    p=α1*p
    cpu
    +α2*p
    memory
    +α3*p
    band
    +α4*p
    i/o (1)
    [0057]
    式中,αi表示各参数对服务器处理能力的影响权重,满足于与服务器的配置信息有着直接的联系,设α1~α4取值分别0.5,0.2,0.2和0.1,权重越大说明该参数对服务器性能的影响更显著,7个服务器的处理能力分别表示成p(s1) 、p(s2)、p(s3)、p(s4)、p(s5)、p(s6)、p(s7)。
    [0058]
    服务器的实际设置参数决定了各个服务器的实际处理能力。同时服务器的资源使用率与cpu频率、内存容量、网络带宽和磁盘读写速度也是密切相关的,线性表示成公式(2):
    [0059]
    c=β1*c
    cpu
    +β2*c
    memory
    +β3*c
    band
    +β4*c
    i/o (2)
    [0060]
    式中,βi表示各参数对服务器处理能力的影响权重,满足于参数大小与αi一致。7个服务器的资源使用率分别表示成c(s1)、c(s2)、c(s3)、c(s4) 、c(s5)、c(s6)、c(β7)。
    [0061]
    任务请求到来时,选择哪台服务器是通过集群中处理服务器的资源剩余量来衡定的。在本发明中,当前处理服务器的资源剩余量可以表示成:
    [0062][0063]
    式中:c(sj)表示第j台处理服务器当前的资源使用量,表示第j台处理服务器占整个集群中资源使用量的比例。综合集群中各处理服务器的整体性能,确定一个资源使用阈值常量c,只有满足的处理服务器才能成为候选服务器,存入候选服务器集。并且越小,该候选服务器的地位越稳定,任务请求在进行分配任务时优先选择候选服务器集中较小的那一个。
    [0064]
    (3)采用0-1矩阵对任务请求与处理服务器之间的关系进行编码,用编码矩阵d来表示。
    [0065]
    编码的唯一目的是将系统中的任务请求与处理服务器之间的关系联系起来。本发明实施例中,系统调度中仅有12个任务请求,集群中处理服务器的个数为 7个,那么两者的编码关系图如图2编码部分所示。
    [0066]
    编码矩阵中每行代表一个到来的任务请求,0-1表示该任务请求是否在所属服务器编号上被处理,每次调度中每个任务请求仅能选择一台服务器进行交互。任务请求到来时,监控服务器统计负载信息,筛选能够进入候选集的服务器序号,具体的任务请求分配是发生在候选服务器集上的。
    [0067]
    (4)通过负载均衡的方式来处理集群问题,主要的目的是合理利用空闲资源,提高集群系统的吞吐量,减少任务的处理时间。在本发明中,将任务完成时间和集群中各服务器之间的处理时间差异看作两个相互竞争系统资源的目标,在保证集群处理时间最小的情况下,服务器的资源利用率未必是最高的,因此,构建目标函数为公式(3):
    [0068][0069]
    式中,t(sj)表示每台处理服务器完成该组任务分配所耗费的时间,其中j∈ (0,n),表示集群中处理服务器的标号。σ表示一组分配任务请求中服务器的处理时间差异,可以通过公式(4)表示:
    [0070][0071]
    式中,表示的是集群中每台服务器的平均任务完成时间;σ表示集群中各服务器处理时间的方差,σ数值越小说明各服务器之间处理时间差异越小。
    [0072]
    约束条件可表示为公式(5):
    [0073][0074]
    约束条件只是限定了一个任务只能选择一台服务器进行处理,同时在选择服务器时根据请求时刻服务器资源剩余量构建候选服务器集,任务请求在候选服务器集中选则所
    要进行交互的服务器。
    [0075]
    (5)使用布谷鸟搜索算法对提出的优化问题进行迭代优化求解:
    [0076]

    设置任务个数、服务器集群中的节点个数、鸟群个数n、迭代次数以及布谷鸟发现外来鸟蛋的概率pa。
    [0077]

    初始化鸟群。采用随机的方式生成数量为n的初始鸟群d
    _cell
    ,表示成:
    [0078]d_cell
    =[d1,d2,d3,

    ,d
    n-1
    ,dn],其中每一个di都代表一个调度方案如图2 中的编码方式部分,di中的行向量代表系统中进行分配的每一个任务,每个di可以分解为12个行向量,每个行向量中的1表示候选服务器的标号。
    [0079]

    计算适应度值
    [0080]
    本发明的适应度值函数是由目标函数转变而来,通过采集到服务器的参数进行量化处理服务器的综合处理能力p(sj)和负载信息c(sj),计算适应度值函数。
    [0081]

    鸟群迭代。当未满足最大迭代次数时便开始进行种群的迭代。
    [0082]

    采用莱维飞行的方式更新鸟巢的位置。
    [0083]
    在布谷鸟群体生活中,布谷鸟寻找合适产卵鸟巢的方式是随机的,但服从一种特殊的移动轨迹,即在一定短时间移动距离较短,长时间内出现一次移动距离较长的情况,服从莱维分布,表示成公式(6):
    [0084][0085]
    式中,l(λ)~u=t-λ
    ,λ为移动步长,取值为1《λ≤3。
    [0086]
    采用发明1中的改进步长的方式,引入参数动态参数β对步长进行适度调整,β可表示成公式(7):
    [0087]
    β=θ(iter
    max-t)+β
    0 (7)
    [0088]
    式中,iter
    max
    表示算法设置的最大迭代次数,t表示当前的迭代次数,θ表示的是变化幅度。β0控制步长不为0。其中θ和β0是由求解问题规模的大小决定的。继而得到新的表示为公式(8):
    [0089][0090]
    之所以改进步长,是便于根据实际的问题特点进行提高鸟群寻优的速度和精度。每一代都会使用适应度函数进行选择。
    [0091]

    对比当代鸟巢与上一代鸟巢的位置,得到较优的鸟巢d
    bes
    t。
    [0092]

    通过发现概率pa进行筛选鸟群。若满足(0,1)的随机数r》pa,则对d
    bes
    t进行再一次的随机寻优,得到较优的鸟巢,并输出较优的适应度函数值。
    [0093]

    循环迭代终止。当达到迭代次数时,停止迭代,输出较优全局最优的适应度函数值fit
    best
    和相应的编码矩阵d,否则从步骤

    开始,继续迭代。
    [0094]
    (6)输出合适的编码方案。
    [0095]
    严格意义上来讲最优适应度值fit
    best
    可能是一个或多个,即存在一个pareto 解集,每一个fit
    best
    会对应一个编码方案,解集中的每个解都是无差别解,如图 3所示,在一次任务分配,即迭代优化过程中,会出现4个适应度函数值fit
    best
    ,每个适应度函数值会分别对应一个编码方案,调度机制会随机选择一个编码方案 0和1所在的序号对任务进行调度。
    [0096]
    (7)对方案进行解码,找到最终的任务请求与处理服务器之间的关系,调度机制会随机选择一个编码方案进行任务调度。
    [0097]
    实施例中具体的任务请求与候选服务器之间的关系结合图2中的编码矩阵可以得出右侧解码后的任务请求与候选服务器之间的关系,并能够达到是任务时间最小化和提高集群负载均衡的双目的。
    [0098]
    本说明书实施例所述的内容仅仅是对发明构思的实现形式的列举,本发明的保护范围不应当被视为仅限于实施例所陈述的具体形式,本发明的保护范围也及于本领域技术人员根据本发明构思所能够想到的等同技术手段。

    技术特征:
    1.基于双目标优化的服务器负载均衡方法,包括以下步骤:s1.确定一次请求分配过程中处理服务器的个数,根据时间节点中并发请求的数量采用滑动窗口获取任务请求的个数;s2.获取服务器的实时状态信息包括量化集群中节点服务器的综合处理能力和任务请求到来时刻各服务器的资源使用量;服务器的综合处理能力与cpu频率、内存容量、网络带宽和磁盘读写速度有着直接的关系,表示成:p=α1*p
    cpu
    +α2*p
    memory
    +α3*p
    band
    +α4*p
    i/o
    ꢀꢀꢀꢀꢀꢀ
    (1)式中,α
    i
    表示各参数对服务器处理能力的影响权重,满足于与服务器的配置信息有着直接的联系,权重越大说明该参数对服务器性能的影响更显著;服务器的资源使用量与cpu频率、内存容量、网络带宽和磁盘读写速度也是密切相关的,线性表示成:c=β1*c
    cpu
    +β2*c
    memory
    +β3*c
    band
    +β4*c
    i/o
    ꢀꢀꢀꢀꢀꢀꢀꢀ
    (2)式中,β
    i
    表示各参数对服务器处理能力的影响权重,满足于参数大小与α
    i
    一致;s3.采用0-1矩阵对任务请求与处理服务器之间的关系进行编码,通过一个矩阵来表示:在一组分配任务中,编码矩阵中的一行代表一个任务,所在元素为1的位置表示服务器的所在序号;s4.构造集群负载请求分配优化问题的目标函数,表示成:式中,t(s
    j
    )表示每台处理服务器完成该组任务分配所耗费的时间,其中j∈(0,n),表示集群中处理服务器的标号;σ表示一组分配任务请求中服务器的处理时间差异,可以通过以下表示:上述公式中,表示的是集群中每台服务器的平均任务完成时间;σ表示集群中各服务器处理时间的方差,σ数值越小越好;约束条件可以表示成:式中,表示编码矩阵d中的每一行元素之和,d
    i*j
    取值只能为0或1,当d
    i*j
    为1时表示任务请求在所选的节点服务器进行被处理;又因同一组任务中,每个任务有且仅能选择一台处理服务器,所以在编码矩阵中的行向量中,至多存在一个元素为1;表示任务请求到来时选择处理服务器的限制条件;表示节点服务器的资源剩余量;监控节点服务器的资源信息,当资源使用率小于某个阈值c时能够说明该节点服务器能够接受更多的任务请求;s5.使用布谷鸟搜索算法对提出的问题进行迭代优化求解,输出编码解集;将集群中的
    任务调度问题转化成鸟群迭代寻找最优鸟巢位置进行孵卵的过程,包括以下几个部分:

    设置鸟巢寻优的初始参数,包括鸟巢的个数、最优迭代次数、以及布谷鸟发现外来鸟蛋的概率pa,确定适应度函数为目标函数;

    初始化鸟群;采用随机的方式生成数量为n的初始鸟群d
    _cell
    ,表示成:d
    _cell
    =[d1,d2,d3,

    ,d
    n-1
    ,d
    n
    ],其中每一个编码矩阵都代表一个调度方案;

    计算适应度值;通过采集到服务器的参数进行量化处理服务器的综合处理能力和负载信息,计算适应度函数值,更新初始鸟群,;

    鸟群迭代;当未满足最大迭代次数时便开始进行种群的迭代以找到较优的鸟巢位置;

    采用改进莱维飞行的方式更新鸟巢的位置;在布谷鸟群体生活中,布谷鸟寻找合适产卵鸟巢的方式是随机的,但服从一种特殊的移动轨迹,即在一定短时间移动距离较短,长时间内出现一次移动距离较长的情况,服从莱维分布,表达式为:式中,l(λ)~u=t-λ
    ,λ为移动步长,取值为1<λ≤3;

    进一步的,为了更好进行快速搜索和局部精准搜索,引入参数动态参数β对步长进行适度调整,β可表示成:β=θ(iter
    max-t)+β0ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
    (7)式中,iter
    max
    表示算法设置的最大迭代次数,t表示当前的迭代次数,θ表示的是变化幅度;β0控制步长不为0;其中θ和β0是由求解问题规模的大小决定的;继而得到新的表达式为:

    对比当代鸟巢与上一代鸟巢的位置,得到较优的鸟巢d
    best


    通过发现概率pa进行筛选鸟群;若满足(0,1)的随机数r>pa,则对d
    best
    进行再一次的随机寻优,得到较优的鸟巢;

    循环迭代终止;当达到迭代次数时,停止迭代,输出较优全局最优的鸟巢位置,否则从步骤

    开始,继续迭代;s6.输出合适的编码方案;严格意义上来讲优化结果中最优适应度函数值可能是一个或多个fit
    best
    ,即存在一个pareto解集,每一个fit
    best
    会对应一个编码方案;s7.对方案进行解码,找到最终的任务请求与处理服务器之间的关系,调度机制会随机选择一个编码方案进行任务调度。2.如权利要求1所述的基于双目标优化的服务器负载均衡方法,其特征在于:步骤s2中设α1~α4取值分别0.5,0.2,0.2和0.1。

    技术总结
    基于双目标优化的服务器负载均衡方法,包括:S1.确定一次请求分配过程中处理服务器的个数,根据时间节点中并发请求的数量采用滑动窗口获取任务请求的个数;S2.获取服务器的实时状态信息包括量化集群中节点服务器的综合处理能力和任务请求到来时刻各服务器的资源使用量;S3.采用0-1矩阵对任务请求与处理服务器之间的关系进行编码;S4.构造集群负载请求分配优化问题的目标函数;S5.使用布谷鸟搜索算法对提出的问题进行迭代优化求解,输出编码解集;S6.输出合适的编码方案;S7.对方案进行解码,找到最终的任务请求与处理服务器之间的关系,调度机制会随机选择一个编码方案进行任务调度。本发明能够解决服务器的集群中负载均衡分配的问题,使整个解决方案更高效和准确。使整个解决方案更高效和准确。使整个解决方案更高效和准确。


    技术研发人员:孟利民 田真真 蒋维 林梦嫚 应颂翔
    受保护的技术使用者:浙江工业大学
    技术研发日:2022.02.11
    技术公布日:2022/5/25
    转载请注明原文地址:https://tc.8miu.com/read-18560.html

    最新回复(0)