如今, 人们对互联网服务日益增长的需求大大增加了互联网以及云计算数据中心的能源消耗. 2014年, 美国数据中心的用电量估计为700亿千瓦时, 约占美国总用电量的1.8 %[1].而我国近年来随着各行业对数据服务的需求不断增加, 数据中心市场逐年扩大, 投资规模也快速增长. 2015年, 我国数据中心总耗电量从2009年的413.7亿千瓦时增长到近1 000亿千瓦时, 约占当年全国电力消耗总量的2%[2].数据中心巨大的用电量带来的主要问题是高额的电费以及大量的碳排放[3].因此, 如何减少数据中心的用电, 进而减少其面临的高额电费和大量碳排放, 成为了国内外研究的热点.这些研究中除了使用绿色能源减少电费和碳排放外, 还包括一些能更高效运行数据中心的资源管理方法.其中一种是利用功耗管理减少数据中心的能耗, 例如动态电压频率调整技术[4]根据服务器的工作负载调整其CPU时钟频率以达到降低用电量的目的; 通过在系统未得到充分利用的低工作负载期间, 仅在一部分机器上分配负载并关闭其余机器降低总功耗[5].另一种方式是利用电力市场中的价格差异, 在多个地点的数据中心之间分配工作量以最大限度地降低电力总成本[6].一些研究还考虑到数据中心能源费用最小化与云计算服务收入最大化之间的平衡[7].此外, 也有研究指出[8], 最小化能耗和最大化系统提供的服务质量是能源性能管理中的重要平衡, 其中对数据中心的服务质量可以通过各种度量进行定义, 并根据服务等级协议(SLA)中的内容具体化.
目前, 针对数据中心能源与性能管理的优化主要是单目标优化, 如用电量、运营收入等.在很多研究中, 将用电量和运营收入作为同一个目标讨论, 但实际上, 虽然数据中心的用电量直接影响着运营收入, 但由于服务等级协议的影响, 电费的减少未必意味着数据中心总收入的提高.另一方面, 用电量能够直接反映数据中心的碳排放量.同时, 目前的研究很少将服务质量作为优化目标, 而仅是作为约束条件考虑.在合理量化服务质量的前提下, 将服务质量作为优化的目标之一, 可以有效地改善用户体验.鉴于此, 本文建立了数据中心运营收入、碳排放和服务质量的三目标优化模型, 并根据问题特征设计了改进的多目标优化算法ICDA-NSGA-Ⅱ.通过与经典的NSGA-Ⅱ算法[9]和基于分解的多目标进化算法[10]对比, 所提出的算法无论在Benchmarks测试函数还是实际问题求解中, 都要优于经典的多目标优化算法.
1 分布式数据中心能源与性能建模 1.1 问题描述考虑n个地理位置分散的数据中心, 负载调度服务器接收到服务请求后, 根据各数据中心的实时情况将服务请求发往不同的数据中心, 服务请求达到数据中心后都首先放在一个队列中, 直到任何有可用的服务器可以处理它们为止.每个数据中心按照规定的服务等级协议(SLA)运营, 数据中心的最大开机数量为Mmax, 该因素限制了其处理数据的最大能力, 要求在各个数据中心不超出其最大服务能力的情况下, 尽量增加运营收入, 减少碳排放并提高服务质量.分布式数据中心系统架构如图 1所示.
在不考虑数据中心维护成本等因素的情况下, 数据中心的利润计算主要由服务收入和电费两部分构成, 其中电费的多少与数据中心的用电量即碳排放是正相关的, 因此这里只考虑数据中心的收入最大化.本文使用一种带不耐烦客户的m/m/1队列模型对数据中心中的每个服务器进行建模, 可以理解为服务请求队列有一定的长度限制, 当服务队列达到一定长度后, 新到达的服务请求将会被丢弃, 即使它们能被得到处理也将会超时.根据一般SLA的规定[11], 若服务商在规定时间D内满足服务请求, 则可收取一定的服务费用; 若没有在规定的时间内完成服务, 则需要缴纳一定的罚金, 这是计算数据中心收入的主要依据.数据中心在某时段T的总收入为
(1) |
每经过一段时间间隔T, 负载调度服务器重新分配所有n个分布式数据中心服务请求的到达速率λi和处理速率μi是模型中的决策变量. α和β分别表示根据SLA在规定的时间D内完成服务请求收取的费用以及超时未完成服务请求的罚款费用. l(μ)表示服务请求的丢失概率, 即由于服务队列被占满而导致服务请求被丢弃的概率.根据排队理论, 带有不耐烦客户m/m/1排队模型中丢失概率l(μ)的计算方式[12]如下:
(2) |
其中
(3) |
数据中心的碳排放量与用电量之间的换算可以通过碳排放因子计算.数据中心的用电量通过将计算机服务器的总功耗与设备的总功耗(如冷却、照明等)相加得到.由文献[7, 13]中的计算方法, 数据中心的总功率为
(4) |
其中
(5) |
(6) |
Ppeak和Pidle分别为服务器的平均空闲功耗和处理服务请求时的平均峰值功耗, ε为每个服务器平均处理一条服务请求所需要的时间.参数在不同数据中心的取值也不尽相同, 根据服务器总功耗, 求得数据中心在某时间段T内的碳排放量为
(7) |
其中: EF为碳排放因子, 可以通过各区域电网的发电情况计算得到, 以华中区域电网为例[14], 计算得到的碳排放因子为0.901 4 tCO2/MWh.
1.2.3 数据中心服务质量一个数据中心的服务质量(quality of service, QoS)主要根据平均客户等待时间和服务请求的丢失率进行评价.文献[12]介绍了带有不耐烦客户m/m/1排队模型的客户等待时间分布为
(8) |
由式(8)求得客户等待时间的期望为
(9) |
考虑到服务请求丢失对服务质量的影响, 将丢失概率考虑到数据中心服务质量的模型中, 有
(10) |
其中: [1-li(μ)] Ei(W)为接受了服务的客户等待时间, li(μ) D为未接受服务的客户等待时间, 由于最终该客户没有得到服务, 可以考虑加大这一项的权值.
1.2.4 数学模型综上分析, 分布式数据中心能源与性能管理多目标优化模型如下:
(11) |
(12) |
(13) |
其中μi和λi(i=1, 2, …, n)为决策变量, 分别代表各个数据中心的服务请求到达速率.式(12)代表所有服务请求被分配到各个数据中心进行处理, 式(13)中εMmax为数据中心的最大处理速率, max为数据中心最大收入, 显然μ应小于该值, 而为了防止服务请求的不断堆积, 服务请求的处理速率μ应大于到达速率λ.在该模型中, 由于各个数据中心的相关参数可能不同, 某些数据中心可能很容易被分配绝大部分的工作负载, 需要得到一组多样性丰富的解, 从而能更好地选择负载较为均衡的方案, 这对优化算法的分布性能而言是一个挑战.
2 改进后的NSGA-Ⅱ多目标优化算法带精英策略非支配排序的遗传算法(NSGA-Ⅱ)是目前解决多目标优化问题中应用最广泛、效果最优秀的方法之一. Deb等[9]在原NSGA算法的基础上对排序方法和搜索机制进行改进, 提出了更高效的快速非支配排序方法, 并引入了以拥挤距离算子为基础的精英保留策略, 使得NSGA-Ⅱ算法具有更好的收敛性和分布性.
随着多目标优化理论的发展, 出现越来越多复杂的多目标优化问题, 在大量实践中发现, 传统的NSGA-Ⅱ算法虽然通过拥挤距离机制增加了种群多样性, 但仍然存在分布性不佳、局部最优的问题.在本文模型中, 如何保持种群多样性的同时加快算法的收敛速度是算法设计中所面临的主要困难.一方面, 为了更容易得到均衡的负载分配方案, 有需要得到分布性更好的解决方案的需求; 另一方面, 数据中心相关参数的差异可能导致优化结果有较强的偏向性.同时, 较快的收敛速度有助于负载分配服务器更加及时地为各个数据中心分配负载, 在设计算法时有必要对这一方面加以考虑.针对该问题, 本文在NSGA-Ⅱ算法的基础上进行了一些改进, 以提高算法的收敛速度和优化结果的分布性.
2.1 改进的拥挤距离计算方法拥挤距离的计算是NSGA-Ⅱ算法中排挤机制的基础, 个体拥挤距离是指在同一Pareto层级中, 某一个体与其前后相邻的两个个体在各个方向上的距离之和.对于第i个层级的某个个体j, 其拥挤距离disj的计算方法如下.
Step 1:将拥挤距离disj初始化为0.
Step 2:依次对各个目标函数k进行如下计算: 1)根据第k个目标函数的大小对第i层级中的各个个体进行排序; 2)对于边界上的个体(目标函数最大或最小), 定义disj=inf (无穷大); 3)对于其他个体, 假设其排序为n, 则有
(14) |
这种拥挤距离的计算方式在某些状况下有一定局限性, 可以通过两个例子说明.在图 2中, 如果按照原先的计算方式, 个体在C点或D点时的拥挤距离是一样的, 但实际上, 当个体在D点时更能体现种群的均匀分布, 应该有更佳的拥挤距离.同样在图 2中, 若按照原先的计算方式, 个体在E点或F点时的拥挤距离是一样的, 但实际上, 当个体在E点时能加快种群的收敛速度, 应该有更佳的拥挤距离.
为了更好地体现种群中个体分布的均匀性, 加强种群的收敛性, 对拥挤距离的计算方法作一些改进, 新的拥挤距离disj定义如下:
(15) |
其中
(16) |
(17) |
由图 2和图 3可见:当个体越靠近原点时, c的取值越大; 当个体分布得越均匀时, d的取值越大.因此, c越大代表个体的目标函数越优, 收敛得越快, d越大代表个体有着越好的分布性.在综合考虑这两个参数后, 将它们整合进新的拥挤距离计算方法中.
在NSGA-Ⅱ算法中, 交叉与变异往往是通过遗传算法实现, 其中存在一些缺陷影响了算法的收敛性和搜索能力.一方面, NSGA-Ⅱ算法中的交叉过程采用了SBX算子(模拟二进制交叉算子), 而SBX算子的大多数子代解决方案位于父代解决方案的相邻区域, 因此这种变异方式往往收敛速度较慢; 另一方面, 传统的NSGA-Ⅱ算法采取多项式变异方式, 这种方式不能根据种群中个体的变化调整变异方式, 收敛速度缓慢.
一般而言, SBX算子专注于搜索父代个体周围的一小部分区域, 若优化问题比较庞大, 则产生的子代个体只能覆盖总搜索空间很小一部分.由于它们都靠近父代个体, 找到非支配解的可能性很低, 相比之下, 正态分布交叉算子(NBX)算子具有更强的全局搜索能力[15].本文引入NBX算子以增强算法的空间搜索能力, 假定父代为p1和p2, 产生了子代x1和x2, 其中第i个变量的交叉过程为
(18) |
(19) |
其中: u为区间(0, 1)中一个随机数, N(0, 1)为正态分布随机变量.同时, 为了提高种群的收敛速度, 引入一种自适应调整的变异方式, 种群中某一个体Xi的变异概率为
(20) |
其中: N为个体数量; F(Xi)为个体Xi的适应度评价函数;
改进后的算法流程如下.
step 1:随机产生有N个个体的初始种群P0, 对种群进行快速非支配排序, 并采用改进后的拥挤距离计算个体的拥挤度.
step 2:采用二进制锦标赛选择操作, 从Pn中随机选择个体进行遗传操作后产生子代Qn, 交叉和变异分别采用正态分布交叉方式和改进的自适应调整变异方式.
step 3:将种群Pn和Qn合并后进行快速非支配排序, 并计算改进后的拥挤距离, 优选出N个个体组成新一代种群, 形成新一代种群Pn+1.
step 4:若达到最大迭代次数, 则满足终止条件, 循环结束, 否则转至step 2.
3 实验与分析为了显示改进算法的有效性, 本文首先对基准测试函数进行计算, 然后利用该改进算法求解多数据中心负载调度优化问题.
3.1 实验环境和参数设置本文所提出的ICDA- NSGA-Ⅱ算法由Matlab实现, 运行在PlatEMO平台[16], 运行实验的电脑CPU为Intel Core i5-7500, 内存8.0 GB.所有算法的相关参数设置如下:初始种群大小N= 100;期望变异概率p=m/d, 即优化的目标数量除以决策变量的数量; 当达到最大迭代次数Gmax=10 000时, 算法终止.
3.2 测试函数及性能评价指标本文采用经典的基准测试问题ZDT系列[17]和DTLZ系列[18]进行对比实验.同时选用IGD[19]、SP[20]以及运行时间作为算法的性能评价指标. IGD和SP能够分别评价算法的收敛性和分散性.其中: IGD值越小表明算法的收敛性能越好, SP值越大表明算法有越好的分散性.实验采用每种算法对各个测试问题独立运行30次后, 对统计结果进行评价.
3.3 对比实验在对比实验中, 选用NSGA-Ⅱ[9]和MOEA/D[10]与所提出的ICDA-NSGA-Ⅱ进行对比. 表 1为各算法对所有测试问题的运行时间.基于实验结果, 使用置信水平为95 %的秩和检验来评价不同算法间的性能差异.基于性能指标IGD和SP的实验结果分别如表 2和表 3所示.其中“+ ”和“- ”分别表示其他算法显著优于或劣于ICDA-NSGA-Ⅱ, “= ”表示差距不明显, 各算法中表现最好的性能评价指数用加粗字体显示.由表 1~表 3的测试结果可以看出:针对15个测试问题, ICDA-NSGA-Ⅱ不仅在运行时间上显著优于其他两个算法, 而且在其中10个测试问题上有着最优的IGD值, 在其中7个测试问题上有着最优的SP值, 这表明所提出的算法在收敛性和分散性上总体表现都更好.
实验结果表明, 相较传统的两种多目标优化算法, 本文提出的ICDA-NSGA-Ⅱ收敛性和分散性更好, 由于收敛性的改善, 算法的求解速度也明显更快.在实际问题中, 这对于负载分配服务器及时分配负载是有利的.性能改善的原因在于:首先, 改进后的拥挤距离能兼顾算法的收敛性和分散性; 然后, NDX算子的引入增强了算法的空间搜索能力, 能够在保证种群多样性的同时能更快地找到非支配解; 最后, 改进后的变异方式基本不改变总体的期望变异概率, 在加快收敛速度的同时没有对种群的多样性造成太大影响, 提高了算法的总体性能.
3.4 实例模拟与分析本实验对NSGA-Ⅱ和ICDA-NSGA-Ⅱ进行对比分析.实验数据来自文献[21], 包括分布式数据中心在一天中某几个时间段的实际运行数据, 对3个位于不同地区、提供相同服务的数据中心的运行进行管理与优化.实验中采用的SLA数据在文献[22]的基础上根据实际情况作出调整, 客户的最大等待时间D=100 ms, 最大开机数量Mmax=50 000, 按时完成服务收费α=7×10-5美元/条, 未按时完成服务罚款β=3.5×10-5美元/条.负载调度服务器根据收到的服务请求总到达率λ, 每经过一个时间间隔T=15 min后, 对负载重新进行分配, 数据中心服务器参数的上下限见表 4.
实验中, 首先比较ICDA-NSGA-Ⅱ和NSGA-Ⅱ分别在4种不同的数据中心及电价模型下, 对分布式数据中心能源与性能管理的算法性能. 表 5给出了两个算法在优化模型上求得的SP平均值以及结果的标准差, 表中符号“+ ” “- ”的含义同表 1.由表 5可见, 所提出的ICDA-NSGA-Ⅱ在4种情形下的种群分散性结果均优于NSGA-Ⅱ.
在实际情况中, 对数据中心运行管理优化目标的选择与权衡可以根据实际情况调整, 在保证服务质量的前提下选择收入更高、碳排放更低的运行模式, 也可以根据某种权重进行选择. 表 6给出的优化结果根据ICDA-NSGA-Ⅱ求得的Pareto前沿, 采用前一种偏好进行选择.与文献[21]方法对比的结果显示, 除了在问题1中ICDA-NSGA-Ⅱ的优化结果能耗较高以外, 在其他问题上优化后的各项目标都更优.可以看出, 采用本文提出的多目标优化模型与算法求得的参数设定值可以获得更好的结果.
针对分布式数据中心运行负载调度过程中经常出现的能耗优化问题, 本文进一步考虑了数据中心收入与服务质量的优化, 建立了问题的多目标能源与性能管理优化模型, 从而保证了在数据中心能耗降低的同时优化收入和服务质量.同时, 针对所建立的模型提出了一种改进拥挤距离及交叉算子的自适应调整变异NSGA-Ⅱ算法.基于15个基准测试问题的实验结果表明, 该算法的性能优于传统的多目标算法.数据中心管理的优化问题的测试结果表明, 所提出的算法显著优于传统多目标优化算法NSGA-Ⅱ, 且优化结果能够在保证服务质量的同时进一步降低能耗, 增加收入.
[1] |
Shehabi A, Smith S, Sartor D, et al. United states data center energy usage report[R]. Berkeley: Lawrence Berkeley National Lab, 2016.
|
[2] |
Xu M M, Zhai X Q, Li G Z, et al. Research progress in cooling technology of data centers[J]. Building Science, 2018, 34(8): 124-132. |
[3] |
Qureshi A, Weber R, Balakrishnan H, et al. Cutting the electric bill for internet-scale systems[J]. ACM Sigcomm Computer Communication Review, 2009, 39(4): 123-134. DOI:10.1145/1594977.1592584 |
[4] |
Chen Y, Das A, Qin W, et al. Managing server energy and operational costs in hosting centers[J]. ACM Sigmetrics Performance Evaluation Review, 2005, 33(1): 303-314. DOI:10.1145/1071690.1064253 |
[5] |
Heo J, Henriksson D, Liu X, et al. Integrating adaptive components: An emerging challenge in performance-adaptive systems and a server farm case-study[C]. The 28th IEEE International Real-time Systems Symposium. Tucson: IEEE, 2007: 227-238.
|
[6] |
Li J Y, Li Z Y, Ren K, et al. Towards optimal electric demand management for internet data centers[J]. IEEE Transactions on Smart Grid, 2012, 3(1): 183-192. DOI:10.1109/TSG.2011.2165567 |
[7] |
Ghamkhari M, Mohsenian-Rad H. Energy and performance management of green data centers: A profit maximization approach[J]. IEEE Transactions on Smart Grid, 2013, 4(2): 1017-1025. DOI:10.1109/TSG.2013.2237929 |
[8] |
Beloglazov A, Buyya R. Managing overloaded hosts for dynamic consolidation of virtual machines in cloud data centers under quality of service constraints[J]. IEEE Transactions on Parallel and Distributed Systems, 2013, 24(7): 1366-1379. DOI:10.1109/TPDS.2012.240 |
[9] |
Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197. DOI:10.1109/4235.996017 |
[10] |
Zhang Q, Li H. MOEA/D: A multiobjective evolutionary algorithm based on decomposition[J]. IEEE Transactions on Evolutionary Computation, 2007, 11(6): 712-731. DOI:10.1109/TEVC.2007.892759 |
[11] |
Macías M, Guitart J. SLA negotiation and enforcement policies for revenue maximization and client classification in cloud providers[J]. Future Generation Computer Systems, 2014, 41: 19-31. DOI:10.1016/j.future.2014.03.004 |
[12] |
Choi B D, Kim B, Chung J. M/M/1 queue with impatient customers of higher priority[J]. Queueing Systems, 2001, 38(1): 49-66. DOI:10.1023/A:1010820112080 |
[13] |
Fan X B, Weber W D, Barroso L A. Power provisioning for a warehouse-sized computer[J]. ACM SIGARCH Computer Architecture News, 2007, 35(2): 13-23. DOI:10.1145/1273440.1250665 |
[14] |
Baseline Emission Factor of China Regional Power Grid for 2017 Emission Reduction Project[R]. Beijing: Ministry of Ecology and Environment of China, 2018.
|
[15] |
Zheng F F, Qi Z X, Bi W W, et al. Improved understanding on the searching behavior of NSGA-Ⅱ operators using run-time measure metrics with application to water distribution system design problems[J]. Water Resources Management, 2017, 31(4): 1121-1138. DOI:10.1007/s11269-016-1564-7 |
[16] |
Tian Y, Cheng R, Zhang X Y, et al. PlatEMO: A Matlab platform for evolutionary multi-objective optimization[educational forum][J]. IEEE Computational Intelligence Magazine, 2017, 12(4): 73-87. DOI:10.1109/MCI.2017.2742868 |
[17] |
Zitzler E, Deb K, Thiele L. Comparison of multiobjective evolutionary algorithms: Empirical results[J]. Evolutionary Computation, 2000, 8(2): 173-195. DOI:10.1162/106365600568202 |
[18] |
Deb K, Thiele L, Laumanns M, et al. Scalable test problems for evolutionary multiobjective optimization[C]. Evolutionary Multiobjective Optimization. London: Springer, 2005: 105-145.
|
[19] |
Coello C A C, Cortés N C. Solving multiobjective optimization problems using an artificial immune system[J]. Genetic Programming and Evolvable Machines, 2005, 6(2): 163-190. DOI:10.1007/s10710-005-6164-x |
[20] |
Schott J R. Fault tolerant design using single and multicriteria genetic algorithm optimization[D]. Master: Department of Aeronautics and Astronautics, Massachusetts Institute of Technology, 1995.
|
[21] |
Ghamkhari M, Mohsenian-Rad H. Optimal integration of renewable energy resources in data centers with behindthe-meter renewable generator[C]. IEEE International Conference on Communications. Ottawa: IEEE, 2012: 3340-3344.
|
[22] |
Kusic D, Kephart J O, Hanson J E, et al. Power and performance management of virtualized computing environments via lookahead control[J]. Cluster Computing, 2009, 12(1): 1-15. DOI:10.1007/s10586-008-0070-y |