﻿ 采用随机规划模型的云资源分配算法
 计算机系统应用  2019, Vol. 28 Issue (2): 140-145 PDF

Cloud Resource Allocation Algorithm Using Stochastic Programming
CHEN Jun-Jie
School of Electronics and Information, Nantong University, Nantong 226019, China
Foundation item: Natural Science Fund for Colleges and Universities in Jiangsu Province (15KJD520002)
Abstract: Aiming at the cloud resource provisioning problem, a stochastic programming based cloud resource allocation algorithm is proposed to reduce the total resource provisioning cost of the service provider. Combining the reservation plan and the on-demand plan, the cloud resource provisioning problem can be formulated as a two-stage stochastic programming problem using the probability distribution of the workload demand. Then the sample average approximation approach and a stage decomposition based hybrid evolutionary algorithm are applied to solve the cloud resource provisioning problem. The simulation results show that the proposed cloud resource allocation algorithm can obtain near optimal resource reservation scheme within a short time, reducing the total resource provisioning cost of the service provider significantly.
Key words: cloud resource allocation     reservation     stochastic programming     sample average approximation     hybrid evolutionary algorithm

1 云资源提供问题 1.1 云计算环境

1.2 基于随机规划的云资源提供问题

 $\left\{\begin{gathered} Q(\{ {n_i}\} , {d_t}) = \mathop {\min }\limits_{{x_i}} \sum\nolimits_{i = 1}^N {{x_i}p_i^o} \\ {\rm{ s.t.}}\sum\nolimits_{i = 1}^N {{x_i}{C_i}} \geqslant {d_t} - \sum\nolimits_{i = 1}^N {{n_i}{C_i}} \\ {x_i} \in {N_0} \\ \end{gathered} \right.$ (1)

 \left\{\begin{aligned} &\mathop {\min }\limits_{{n_i}} \sum\nolimits_{i = 1}^N {{n_i}P_i^R} + \sum\nolimits_{i = 1}^N {{n_i}p_i^rT} + \sum\nolimits_{t = 1}^T {Q(\{ {n_i}\} , {d_t})} \\ &{\rm{ s.t.}}\;\;{n_i} \in {N_0} \end{aligned} \right. (2)

 \left\{\begin{aligned} &\mathop {\min }\limits_{{n_i}} \sum\nolimits_{i = 1}^N {{n_i}p_i^R} + \sum\nolimits_{i = 1}^N {{n_i}p_i^r} + \sum\nolimits_{k = 1}^K {{p_D}({D_k})Q(\{ {n_i}\} , {D_k})} \\ &{\rm{ s.t.}}\;\;{n_i} \in {N_0} \\ \end{aligned}\right. (3)

 \left\{\begin{aligned} & \mathop {\min }\limits_{{n_i}} \sum\nolimits_{i = 1}^N {{n_i}p_i^R} + \sum\nolimits_{i = 1}^N {{n_i}p_i^r} + \sum\nolimits_{k = 1}^K {[p({D_k})\sum\nolimits_{i = 1}^N {{x_{ki}}p_i^o} ]} \\ & {\rm{s.t.}}\;\;\sum\nolimits_{i = 1}^N {{n_i}{C_i}} + \sum\nolimits_{i = 1}^N {{x_{ki}}{C_i}} \geqslant {D_k},\; {n_i} \in {N_0}, {x_{ki}} \in {N_0} \end{aligned}\right. (4)

2 云资源分配算法 2.1 抽样平均近似问题

 \left\{\begin{aligned} &\mathop {\min }\limits_{{n_i}} \sum\nolimits_{i = 1}^N {{n_i}p_i^R} + \sum\nolimits_{i = 1}^N {{n_i}p_i^r} + \frac{1}{{{N_S}}}\sum\nolimits_{j = 1}^{{N_S}} {Q(\{ {n_i}\} , {D_{{k_j}}})} \\ &{\rm{ s.t.}}\;\;{n_i} \in {N_0} \end{aligned} \right. (5)

2.2 混合进化算法

 \left\{\begin{aligned} & \mathop {\min }\limits_{{n_i}} \sum\nolimits_{i = 1}^N {{n_i}p_i^R} + \sum\nolimits_{i = 1}^N {{n_i}p_i^r} + \frac{1}{{{N_S}}}\sum\nolimits_{j = 1}^{{N_S}} {Q(\{ {n_i}\} , {D_{{k_j}}})} \\ &{\rm{ s.t.}}\;\;{n_i} \in {N_0} \\ \end{aligned}\right. (6)

 \left\{\begin{aligned} & Q(\{ {n_i}\} , {D_{{k_j}}}) = \mathop {\min }\limits_{{x_i}} \sum\nolimits_{i = 1}^N {{x_i}p_i^o} \\ &{\rm{ s.t.}}\sum\nolimits_{i = 1}^N {{x_i}{C_i}} \geqslant {D_{{k_j}}} - \sum\nolimits_{i = 1}^N {{n_i}{C_i}}, {x_i} \in {N_0} \\ \end{aligned} \right. (7)

(1) 染色体编码

(2) 适应度函数

 $f({n_1}, \cdots, {n_N}) = \frac{1}{{1 + T({n_1}, \cdots, {n_N}) - {T_{\min }}}}$ (8)

(3) 选择

 ${p_i} = \frac{{c - 1}}{{{c^N} - 1}}{c^{N - i}}$ (9)

(4) 交叉

 $\left\{\begin{gathered} {{\beta '}_{ik}} = \frac{1}{2}[(1 + {B_k}){\beta _{ik}} + (1 - {B_k}){\beta _{jk}}] \\ {{\beta '}_{jk}} = \frac{1}{2}[(1 - {B_k}){\beta _{ik}} + (1 + {B_k}){\beta _{jk}}] \\ \end{gathered} \right.$ (10)

 ${B_k} = \left\{ {\begin{array}{*{20}{l}} {{{(2 \cdot u)}^{\frac{1}{{\eta +1}}}},\;\;u \leqslant \frac{1}{2}} \\ {{{\left( {\frac{1}{{2 \cdot (1 - u)}}} \right)}^{\frac{1}{{\eta + 1}}}},\;\;u > \frac{1}{2}} \end{array}} \right.$

(5) 变异

 ${n'_i} = {n_i} \pm (0.5 \cdot rang{e_i} \cdot \theta )$ (11)

 $\theta = \sum\limits_{m = 1}^M {a(m) \cdot {2^{ - (m-1)}}}$

3 仿真实验

 图 1 工作负载

 图 2 工作负载的概率分布

3.1 资源预留方案对运营成本的影响

 图 3 资源预留方案对运营成本的影响

3.2 抽样平均近似方法

 图 4 抽样平均近似方法的性能

3.3 混合进化算法

 图 5 混合进化算法的进化过程

4 总结

 [1] 师雪霖, 徐恪. 云虚拟机资源分配的效用最大化模型. 计算机学报, 2013, 36(2): 252-262. [2] 赵君, 马中, 刘驰, 等. 一种多目标蚁群优化的虚拟机放置算法. 西安电子科技大学学报(自然科学版), 2015, 42(3): 173-178, 185. [3] Xiao Z, Song WJ, Chen Q. Dynamic resource allocation using virtual machines for cloud computing environment. IEEE Transactions on Parallel and Distributed Systems, 2013, 24(6): 1107-1117. DOI:10.1109/TPDS.2012.283 [4] Zhang Q, Zhani MF, Boutaba R, et al. Dynamic heterogeneity-aware resource provisioning in the cloud. IEEE Transactions on Cloud Computing, 2014, 2(1): 14-28. DOI:10.1109/TCC.2014.2306427 [5] Chaisiri S, Lee BS, Niyato D. Optimization of resource provisioning cost in cloud computing. IEEE Transactions on Services Computing, 2012, 5(2): 164-177. DOI:10.1109/TSC.2011.7 [6] Ran YY, Yang J, Zhang SB, et al. Dynamic IaaS computing resource provisioning strategy with QoS constraint. IEEE Transactions on Services Computing, 2017, 10(2): 190-202. DOI:10.1109/TSC.2015.2464212 [7] Hwang RH, Lee CN, Chen YR, et al. Cost optimization of elasticity cloud resource subscription policy. IEEE Transactions on Services Computing, 2014, 7(4): 561-574. DOI:10.1109/TSC.2013.35 [8] 陈俊杰, 周晖, 王伟. 一种低成本的云资源提供算法. 西安交通大学学报, 2017, 51(10): 135-141. [9] Shapiro A, Dentcheva D, Ruszczynski A. Lectures on stochastic programming: Modeling and theory. Philadelphia: Society for Industrial and Applied Mathematics, 2009. [10] Shopova EG, Vaklieva-Bancheva NG. BASIC–A genetic algorithm for engineering problems solution. Computers & Chemical Engineering, 2006, 30(8): 1293-1309. [11] Blickle T, Thiele L. A comparison of selection schemes used in evolutionary algorithms. Evolutionary Computation, 1996, 4(4): 361-394. DOI:10.1162/evco.1996.4.4.361 [12] Picek S, Jakobovic D. From fitness landscape to crossover operator choice. Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation. Vancouver, Canada. 2014. 815–822.