云计算中负载均衡优化模型及算法研究(2)
2.基于任务调度的负载均衡优化模型
2.1云计算中负载均衡优化问题描述
云计算中处于重要和关键地位的是虚拟资源池，而虚拟资源的调度和分配策略更成为核心问题[10]，本文研究的重点是把任务调度到虚拟机上之后，再把虚拟机均衡的分配到物理机上。
云计算中任务和虚拟机的调度与分配（如图2-1）可分为四个层次：任务接收层、虚拟机创建层、负载均衡策略层、物理机层[11]。任务接收层处于最上面，面向云计算中的所有用户，接收用户提交的请求任务，并进行任务的分批归类处理，同时把归类好的任务按照某种策略成批映射到虚拟机创建层。虚拟机创建层根据任务的种类和数量创建相应的虚拟机，把任务部署到虚拟机上。负载均衡策略层首先收集每个虚拟机上任务的负载量和物理机上的计算资源量，并将收集的信息进行量化，然后根据负载均衡策略再将虚拟机分配到物理机上。物理机层提供虚拟机所需的资源，并运行部署在物理机上的虚拟机，以完成分配到的任务。本文不考虑服务质量（QoS）和用户等级协议(SLA)等问题，只考虑将调度了任务的虚拟机均衡的分配到物理机上。
图1 任务的调度过程
2.2云计算中任务调度的负载均衡优化模型
基于任务调度的计算资源均衡在负载均衡中占据很重要的地位，有不少负载均衡策略对于计算资源的均衡有很好的效果，比如Yiqiu Fang、Fei Wang和Junwei Ge提出了云计算下基于负载均衡的任务调度算法[12]。而我建立的模型是基于任务调度的计算资源均衡，首先衡量出任务的负载量和计算资源的能力大小，然后根据负载量和计算资源能力的大小抽象成组合优化的数学模型，即把负载均衡的分配到计算资源上，使得每台物理机上计算资源的资源占用率相差不大、相对均衡。这里任务负载量的衡量依据预计执行时间和任务量的大小来确定，而物理机计算能力的大小综合考虑CPU型号、频率、核心数、CPU数量等等因素。
物理机j上的计算资源占用率 计算公式如下：
（1）
其中 为任务i的负载量大小， 为物理机j上的计算能力大小， 为物理机j上的计算资源占用率。
云计算中所有物理机上计算资源占用率的均值AOR的计算公式如下：
（2）
云计算中计算资源占用率的方差VOR的计算公式如下：
（3）
其中n代表的是云计算环境中物理机的数量。
由公式（3）可知， 越小，负载均衡效果越好，反之效果越差。所以，该负载均衡模型的目标函数即为：min{OVR}。
3.基于GA的计算能力负载均衡优化算法
3.1算法介绍
遗传算法（Genetic Algorithms，GA）是基于达尔文的生物进化机制和孟德尔的遗传原理设计出来的全局随机优化算法。算法的思想是通过模拟自然界生物群体由低级、简单到高级、复杂的生物进化过程，使所求解问题从初始解逐步求精向最优解逼近。
遗传算法执行过程：首先要将现实问题中的解编码成对应的染色体，因为遗传算法并不直接对问题的解处理而是要对于编码后的参数集处理，同时随机产生出初始群体，并根据适应度函数对每个染色体进行适应度评价，依据计算的适应度值进行染色体的选择、交叉和变异等遗传操作，从而使染色体不断进化求优，经过遗传群体的多次迭代过程，最终得到问题的最优解或者准最优解。