首页> 中国专利> 移动云计算中一种基于鲁棒优化的联合资源预留配置算法

移动云计算中一种基于鲁棒优化的联合资源预留配置算法

页面导航

摘要
著录项
法律信息
说明书
相似文献

摘要

本发明公开了一种移动云计算中的联合资源预留配置方法。针对移动云计算环境下无线通信资源与虚拟计算资源对移动应用服务的双重影响，已有的资源预留配置算法没有考虑未知用户需求概率分布信息时算法的适用性等问题，本发明提出一种基于鲁棒优化的联合资源预留配置算法，在最坏情况下将资源预留配置的不确定性问题转化为带有约束保护水平的易于求解的鲁棒优化模型，同时将无线通信资源和虚拟计算资源的预留配置结合在一起，对二者的分配量进行匹配，从而既降低了问题复杂度，实现了云服务提供商的最小预留配置成本，又实现了无线资源与虚拟资源的联合优化配置，有效提升了资源利用率和用户服务质量。

著录项

公开/公告号CN105446817A

专利类型发明专利
公开/公告日2016-03-30

原文格式PDF
申请/专利权人重庆邮电大学;
展开▼

申请/专利号CN201510814941.3
发明设计人李云;刘杰;吴广福;刘期烈;
展开▼

申请日2015-11-23
分类号G06F9/50(20060101);G06F9/48(20060101);
代理机构50102 重庆市恒信知识产权代理有限公司;
代理人刘小红
地址 400065 重庆市南岸区黄桷垭崇文路2号
入库时间 2023-12-18 15:07:46

法律信息

法律状态公告日

法律状态信息

法律状态
2019-01-22

授权

授权
2016-04-27

实质审查的生效 IPC(主分类):G06F9/50 申请日:20151123

实质审查的生效
2016-03-30

公开

公开

说明书

技术领域

本发明涉及云计算技术领域，尤其是移动云计算环境中的资源预留和配置方法。特别涉及移动用户对接入端无线资源和云端虚拟资源分配的整体服务满意度，以及用户需求不确定情况下联合资源预留配置的鲁棒优化模型。

背景技术

移动云计算是云计算和移动互联网相融合的产物，是近年来快速发展的一种新型应用模式。移动云计算使人们可以随时使用各种移动设备来方便快捷地获取云计算提供的按需服务，使云计算的优势得以全面体现，同时大大增强了移动互联网数据的高效传输和处理能力，降低了移动终端的能量消耗。移动云计算资源配置是指云服务提供商将有用资源通过网络分配给用户以运行移动应用的过程，主要包括数据处理所需的云端虚拟资源和移动终端接入网络所需的无线资源。资源配置一方面要满足移动用户的资源需求，另一方面要尽可能提高资源的有效利用率，因此，云服务提供商的资源配置问题是关系到移动云业务是否能成功完成、云资源能否有效利用及运营成本的关键问题。

目前比较经典的资源配置方法主要是资源按需配置和资源预留配置两种方案。资源按需配置(参见文献：YingS.,YuzhongS.,andWeisongS.,ATwo-TieredOn-Demand ResourceAllocationMechanismforVM-BasedDataCenters.IEEETransactionson ServicesComputing,6(1),2013:116-129)是指云服务提供商通过虚拟化技术，实时且动态的为用户调度所需的各种资源，以随时满足用户的波动需求。资源预留配置(参见文献： Chaisiri,S.,Lee.B.-S.,andNiyato.D.RobustCloudResourceProvisioningfor CloudComputingEnvironments.IEEEInternationalConferenceonService- OrientedComputingandApplications(SOCA),2010:1-8)是指云服务提供商以较低的定期价格提前一段时间预留资源，当应用请求到来时，优先利用预留资源满足用户需求，此时的资源利用成本低于按需资源配置方案的直接利用成本，从而有效减少云服务提供商的整体资源配置成本，提升用户的服务质量。在资源预留配置方案中，用户需求的无法预知和不确定性会造成资源预留量过少或过多，预留资源过少可能无法满足用户的应用需求，承担较高的过需资源调度成本，反之会造成资源的浪费。

以往资源预留配置方面的研究在建立模型时大多假设已知用户需求或其概率分布信息，而实际应用最坏情况下即未知用户需求概率信息下的资源配置问题研究较少。鲁棒优化(参见文献：D.BertsimasandM.Sim,“Thepriceofrobustness”,Operations Research,2004,52(1):35-53)是研究不确定优化问题的一个重要分支，对不确定环境下可能发生的变化进行预测，并采取一定的防范措施，使优化方案具有一定的抗干扰性，即鲁棒性。鲁棒优化下不确定性参数的概率分布函数是未知的，用区间、椭球集等描述不确定参数的变动范围，主要围绕优化方案的可行性与最优性，找到近似最优解，使其对一定范围内任意的不确定性参数的观测值都不敏感。因此鲁棒优化方法可以有效提高不确定需求下资源预留配置的效率。同时，移动云计算资源配置与传统的云计算资源配置的最大区别在于前者需要同时考虑移动终端接入网络的无线资源(如频谱带宽等)和云端数据中心的虚拟资源(如CPU计算资源、存储资源等)，移动用户所分配的无线资源量和虚拟计算资源量同时影响用户的整体服务满意度，上述现有技术的资源预留配置往往忽略了无线资源和虚拟资源对移动应用的双重影响，大多只单独关注一方面的配置问题，很少将二者联合起来考虑。因此有必要研究移动云计算中联合资源预留配置问题，从而有效提高资源利用率。

发明内容

本发明所要解决的问题是：针对现有技术未充分考虑实际应用中未知用户需求具体信息或概率分布信息，造成资源预留配置方案的不准确，以及在移动云计算环境下，忽略了无线资源和虚拟资源对移动应用的双重影响，配置过多的无线资源不仅无法有效的提升用户的整体满意度，还会造成无线资源的浪费，反之亦然。为此，本发明提出一种基于鲁棒优化理论的联合资源配置算法，既能解决用户需求不确定性带来的影响，又能对无线资源和云端虚拟资源进行联合优化，实现无线通信资源和虚拟计算资源的全局最优配置。

本发明解决上述问题的技术方案是：在移动云计算场景下分析无线通信资源和虚拟计算资源对用户业务满意度的整体影响，建立两种资源分配量之间的函数关系；进而在用户需求具体信息未知的情况下，确定资源预留配置的鲁棒优化模型，并建立基于该预留策略的联合资源分配算法。具体为：一种移动云计算环境下联合资源预留配置方法，根据用户无线资源和云端虚拟资源满意度之间的匹配关系，确定两种资源配置量之间的匹配值；以运营成本最小化建立鲁棒优化模型，根据模型计算获得全局最优无线资源预留量和虚拟机资源预留量用户请求到来时，优先以较低的价格利用预留量对用户需求进行虚拟资源分配，并按照无线资源和虚拟资源分配量的匹配量进行分配，(匹配量可由无线资源和虚拟资源满意度之间的匹配关系求解得到)，在预留资源可用量不足时，以较高价格调度未预留资源进行补偿。

所述资源满意度之间的匹配关系为：获得实际配置的无线资源量X_ir和虚拟机资源量Y_ipj，满足等式成立，其中，α和β分别表示用户愿意为所获取的无线资源和虚拟资源的最大支付意愿参数，db_i和dv_ij分别表示用户i对无线带宽资源需求和第j类虚拟机资源的需求，X_ir和Y_ipj分别表示实际配置的无线资源量和虚拟机资源量，在一定范围内分配的资源量越多，则满意度越大。求解上式可得匹配关系成立成立时X_ir和Y_ipj的匹配值。

所述建立的鲁棒优化模型具体包括：根据公式

$\underset{X_{r}^{(r e)}, Y_{p j}^{(r e)}}{m i n} \underset{r \in R}{Σ} \underset{p \in P}{Σ} \underset{j \in J}{Σ} (C_{r}^{(r e)} X_{r}^{(r e)} + C_{p j}^{(r e)} Y_{p j}^{(r e)}) + μ$

$\begin{matrix} s . t . & \underset{i \in I}{Σ} \underset{r \in R}{Σ} \underset{p \in P}{Σ} \underset{j \in J}{Σ} γ_{i r p j} = 1 \end{matrix},$ 其中γ_irpj取0或1

$\forall {db}_{i} \in [\overline{d} b_{i} - \hat{d} b_{i}, \overline{d} b_{i} + \hat{d} b_{i}], {dv}_{i j} \in [\overline{d} v_{i j} - \hat{d} v_{i j}, \overline{d} v_{i j} + \hat{d} v_{i j}],$

$\underset{i \in I}{Σ} \underset{r \in R}{Σ} \underset{p \in P}{Σ} \underset{j \in J}{Σ} γ_{i r p j} {{db}_{i} (C_{r}^{(u)} x_{i r}^{(u)} + C_{r}^{(o)} x_{i r}^{(o)}) + {dv}_{i j} (C_{p j}^{(u)} y_{i p j}^{(u)} + C_{p j}^{(o)} y_{i p j}^{(o)})} \leq μ$

建立的联合资源预留配置鲁棒优化目标函数，求解云服务提供商的资源预留成本、资源使用成本和过需时资源调度成本的最小值，获取总配置成本最小时的无线资源预留量和虚拟机资源预留量其中，r∈R表示覆盖该区域的基站集R中第r个基站，p∈P 表示为该区域提供服务的远程云数据中心集P中的第p个云数据中心，i∈I表示该区域的移动应用集I中的第i个移动应用请求,云数据中心以虚拟机资源的形式为用户提供虚拟计算资源，包含运行应用所需的CPU计算资源、存储资源及网络内部带宽资源等，且根据组成虚拟机所需的各种资源数量的多少分为不同的类型，j∈J表示云端所提供的虚拟机资源类型集J中第j类虚拟机资源。和为云服务提供商联盟在基站r处和云数据中心p处的无线资源预留量和虚拟机资源预留量，γ_irpj表示第i个移动应用经基站r无线接入第p个云数据中心分配第j类虚拟机资源，和分别表示第i个移动应用的无线资源需求的标称值及最大波动值，可由该应用类型的历史需求统计信息来预测得到，同理和表示第i个移动应用对第j类虚拟机资源需求的标称值和最大波动值。则db_i和dv_ij表示移动应用的无线资源需求和虚拟资源需求的可能取值。和分别表示在基站r处的无线带宽资源的单位时间预留成本、单位预留资源利用成本和单位资源过需使用成本，和分别为云数据中心p处第j类虚拟机资源在资源预留、预留资源使用和过需时调度未预留资源的单位成本。和代表实际分配给移动应用的无线资源和虚拟资源量系数。μ为中间变量。目标函数的目的在于求解出总配置成本最小时的无线资源预留量和虚拟机资源预留量

所述模型计算进一步包括：通过约束保护水平参数Γ控制鲁棒优化模型中解的保护程度，使得每个含用户i对无线带宽资源需求db_i和第j类虚拟机资源需求dv_ij的约束条件中至多有个系数可以改变；并根据公式X_ir＝x_irdb和Y_ipj＝y_ipjdv_ij将鲁棒优化模型的最大扰动线性化。构建T＝{1,2,…t,…,T}，其中T＝2I，设置约束条件，使得约束条件包含用户的无线资源需求和虚拟资源需求同时不确定的情况。

在移动云计算中，移动业务的整体服务质量水平同时受无线通信状况和虚拟计算资源状况的影响，利用移动用户对所获取的无线资源和虚拟资源的服务满意度之间的等价关系，确定无线资源配置量和虚拟资源配置量之间的匹配关系；在用户需求不确定且未知概率分布信息的情况下，以云服务提供商的成本最小化为目标，同时考虑无线资源和虚拟资源配置的匹配关系，根据Bertsimas和Sim提出的带有约束保护水平参数的鲁棒优化理论，建立资源预留配置决策的鲁棒优化模型。求解鲁棒优化模型得云服务提供商对无线资源和虚拟计算资源的预留决策，在基站处和云端公用资源池提前一段时间预留资源；请求到来时，云资源管理者观测当前时刻可用预留资源量，根据无线资源和虚拟资源的匹配分配量为用户分配资源，移动应用开始运行。

本发明一方面对无线通信资源和虚拟计算资源进行联合优化配置，更能适应移动云计算的应用场景；另一方面采用带有约束保护水平的鲁棒优化模型，将原不确定性问题转化为易于求解的形式，且能灵活应对用户需求的不确定性带来的波动影响。该方法在有效提高用户整体满意度的基础上，实现无线资源和虚拟计算资源的全局最优配置，同时实现云服务提供商的最小预留成本，提升资源利用率。

附图说明

图1为本发明移动云计算中资源配置系统框架；

图2为本发明系统资源预留状态及转移图；

图3为本发明资源预留配置的三个阶段；

图4为本发明联合资源预留配置算法流程图。

具体实施方式

以下结合附图和具体实例对本发明的实施作具体描述。

图1是移动云计算环境下资源配置的系统架构，由移动用户端、系统中央控制器、基站和云端服务器构成，在基站无线覆盖小区移动用户可接入不同的云端数据中心获取服务。假设系统中云服务提供商采用联盟的形式分别在基站和云端数据中心预留资源；基站提供移动应用接入网络所需要的无线带宽资源，云端服务器通过虚拟化技术，将服务器物理资源以虚拟机资源的形式提供给用户，为移动应用提供数据处理所需要的计算资源，假设基站和云端数据中心所提供的资源均归云服务提供商所有；中央控制器在云服务提供商与移动云用户之间承担代理和决策的角色，是用户和资源之间的接口，并决策带宽资源量和虚拟资源量的配置，在中央控制器中设置一个用户满意度计算和反馈模块，以在制定资源预留策略及分配资源时均考虑无线资源和虚拟资源的匹配问题。

图2是系统资源预留状态及转移图，系统的资源预留配置过程主要包括：资源预留申请提交；系统中央控制器根据当前资源状况接受申请进入已调度状态；系统对需要预留的资源按照一定的开始时刻进行调度和分配；当用户请求到来时，利用预留资源为预留申请用户分配资源；预留周期结束后，资源回收；如果现有系统资源不足，则直接转入异常终止。

图3展示了一个资源预留周期内三个阶段的资源状态。

1)资源预留阶段，在一个资源预留周期开始时，云服务提供商以较低的定期预留价格提前在基站处和云端数据中心处预留一定量的带宽资源和虚拟机资源；

2)资源利用阶段，当移动用户请求到来时，根据资源分配决策，云服务提供商以较低的利用价格为用户应用分配相匹配的无线带宽资源和虚拟机资源；

3)资源过需阶段，当中央控制器检测到当前预留资源无法满足用户应用需求时，云服务提供商按照用户的实际需求以较高的过需价格为用户配置额外的非预留资源。

以下举例说明无线资源与虚拟资源分配之间的关系。

以多媒体应用如音频视频点播为例，用户从云端获取的多媒体服务质量越高，音质和画面越清晰，所需要的流媒体数据传输和处理速率也越大。当云端资源较充足时，可为用户配置较多的虚拟计算资源进行数据处理，基站相应的为该应用分配更多的无线资源，使用户以更高的数据传输速率来获取更高质量的多媒体服务；反之，当云端虚拟资源紧缺，而无线通信环境良好时，即使分配更多的无线资源也无法有效提升多媒体服务的质量，还会造成资源浪费。

可见，移动云用户的服务质量水平受无线资源和云端虚拟计算资源的双重影响，只有两种资源的分配量相匹配，才能有效提升资源利用率和用户服务质量。将用户对资源分配的服务满意度作为衡量服务质量水平的标准，当用户对无线带宽资源的服务满意度与对虚拟计算资源的服务满意度相等时，可以实现对用户无线资源分配量和虚拟资源分配量的匹配。选取对数函数作为服务满意度函数，则用户无线资源分配量和虚拟资源分配量之间的关系如下：

$α l o g (1 + \frac{X_{i r}}{{db}_{i}}) = β l o g (1 + \frac{Y_{i p j}}{{dv}_{i j}}) - - - (1)$

其中，α和β是与用户业务体验有关的大于0的常数，分别代表用户愿意为所获取的无线资源和虚拟资源的最大支付意愿参数，是已知的。db_i和dv_ij分别表示用户i对无线带宽资源和第j类虚拟机资源的需求，代表正常运行时至少需要的资源量，X_ir和Y_ipj表示云服务提供商对该应用实例所实际配置的无线资源量和虚拟机资源量，在一定范围内分配的资源量越多，则满意度越大。

建立联合资源预留配置鲁棒优化模型与约束条件

在一个资源预留配置周期中，第一阶段的资源预留决策是在未知用户需求的情况下进行的，后两阶段的资源分配决策是在已接收到用户的确切需求信息后进行的。在实际应用中最坏情况下，云服务提供商无法提前预知提交预留申请的用户需求的确切信息，而仅可根据历史观测信息确定其需求值范围。即：用户i的无线带宽资源需求量：对第j类虚拟机资源需求量：其中，和分别表示第i个移动应用的无线资源需求的标称值及最大波动值，可由该应用类型的历史需求统计信息来预测得到，同理和表示第i个移动应用对第j类虚拟机资源需求的标称值和最大波动值。则db_i和dv_ij表示移动应用的无线资源需求和虚拟资源需求的可能取值。

以云服务提供商运行成本最小化为目标，建立联合资源预留配置鲁棒优化目标函数，以获取云服务提供商的资源预留成本、资源使用成本和过需时资源调度成本之和的最小值：

$\underset{X_{r}^{(r e)}, Y_{p j}^{(r e)}}{m i n} \underset{r \in R}{Σ} \underset{p \in P}{Σ} \underset{j \in J}{Σ} (C_{r}^{(r e)} X_{r}^{(r e)} + C_{p j}^{(r e)} Y_{p j}^{(r e)}) + μ$

(2)

$\begin{matrix} s . t . & \underset{i \in I}{Σ} \underset{r \in R}{Σ} \underset{p \in P}{Σ} \underset{j \in J}{Σ} γ_{i r p j} = 1 \end{matrix},$ 其中γ_irpj取0或1

$\forall {db}_{i} \in [\overline{d} b_{i} - \hat{d} b_{i}, \overline{d} b_{i} + \hat{d} b_{i}], {dv}_{i j} \in [\overline{d} v_{i j} - \hat{d} v_{i j}, \overline{d} v_{i j} + \hat{d} v_{i j}],$

(3)

这里μ是不可调的中间变量，通过μ将后两阶段的成本表达式转移到了约束条件中，这是一种鲁棒表示方式，是原问题的逼近形式。其中，r∈R表示覆盖该区域的基站集R中第r个基站，p∈P表示为该区域提供服务的远程云数据中心集P中的第p个云数据中心，i∈I 表示该区域的移动应用集I中的第i个移动应用请求,云数据中心以虚拟机资源的形式为用户提供虚拟计算资源，包含运行应用所需的CPU计算资源、存储资源及网络内部带宽资源等，且根据组成虚拟机所需的各种资源数量的多少分为不同的类型，j∈J表示云端所提供的虚拟机资源类型集J中第j类虚拟机资源。和为云服务提供商联盟在基站r处和云数据中心p处的无线资源预留量和虚拟机资源预留量，即预留决策，目标函数的目的在于求解出最终的预留决策和γ_irpj是接入控制参数，表示第i个移动应用经基站r无线接入第p个云数据中心分配第j类虚拟机资源，

和分别表示第i个移动应用的无线资源需求的标称值及最大波动值，可由该应用类型的历史需求统计信息来预测得到，同理和表示第i个移动应用对第j类虚拟机资源需求的标称值和最大波动值。则db_i和dv_ij表示移动应用的无线资源需求和虚拟资源需求的可能取值。和分别表示在基站r处的无线带宽资源的单位时间预留成本、单位预留资源利用成本和单位资源过需使用成本，和分别为云数据中心p处第 j类虚拟机资源在资源预留、预留资源使用和过需时调度未预留资源的单位成本(单位成本已知)。和代表实际分配给移动应用的无线资源和虚拟资源量系数。μ为中间变量。目标函数的目的在于求解出总配置成本最小时的无线资源预留量和虚拟机资源预留量

这里利用鲁棒优化理论，限制系统在资源利用阶段和资源过需阶段对用户i的无线资源和虚拟机资源配置量和分别表示为需求的函数，将最大扰动线性化，即

$X_{i r}^{(u)} = x_{i r}^{(u)} {db}_{i}, X_{i r}^{(o)} = x_{i r}^{(o)} {db}_{i};$

$Y_{i p j}^{(u)} = y_{i p j}^{(u)} {dv}_{i j}, Y_{i p j}^{(o)} = y_{i p j}^{(o)} {dv}_{i j} - - - (4)$

因此，和作为系数代表了实际分配给移动应用的无线资源和虚拟资源量大小。

上述鲁棒优化目标函数模型(2)需要满足的约束条件有：

约束条件S1：即如(3)式所示，要求资源利用阶段和资源过需阶段的总配置成本最低时，才能使目标函数(2)的总配置成本最小化。

约束条件S2：联合资源预留配置应当保证无线资源配置量与虚拟计算资源配置量的匹配，根据无线资源与虚拟资源分配的函数匹配关系，由于 $X_{i r} = X_{i r}^{(u)} + X_{i r}^{(o)}, Y_{i p j} = Y_{i p j}^{(u)} + Y_{i p j}^{(o)},$ 将式(4)代入转化，需满足

$α l o g (1 + x_{i r}^{(u)} + x_{i r}^{(o)}) = β l o g (1 + y_{i p j}^{(u)} + y_{i p j}^{(o)}), \forall i \in I, r \in R, p \in P, j \in J . - - - (5)$

约束条件S3：系统给用户配置的资源应当大于等于用户的资源需求，即

$\begin{matrix} \underset{r \in R}{Σ} γ_{i r p j} (X_{i r}^{(u)} + X_{i r}^{(o)}) \geq {db}_{i} & \underset{p \in P}{Σ} γ_{i r p j} (Y_{i p j}^{(u)} + Y_{i p j}^{(o)}) \geq {dv}_{i j} \end{matrix} - - - (6)$

将式(4)代入转化，需满足

$\begin{matrix} \underset{r \in R}{Σ} γ_{i r p j} (x_{i r}^{(u)} + x_{i r}^{(o)}) \geq 1 & \underset{p \in P}{Σ} γ_{i r p j} (y_{i p j}^{(u)} + y_{i p j}^{(o)}) \geq 1 \end{matrix} - - - (7)$

约束条件S4：当应用请求到来时，系统在资源利用阶段分配给用户的资源不能超过资源预留阶段所预留的资源量，否则进入资源过需阶段，即

$\begin{matrix} \underset{i \in I}{Σ} γ_{i r p j} X_{i r}^{(u)} \leq X_{i r}^{(r e)} & \underset{i \in I}{Σ} γ_{i r p j} Y_{i p j}^{(u)} \leq Y_{i p j}^{(r e)} \end{matrix} - - - (8)$

将式(4)代入转化，需满足

$\begin{matrix} \underset{i \in I}{Σ} γ_{i r p j} x_{i r}^{(u)} {db}_{i} \leq X_{i r}^{(r e)} & \underset{i \in I}{Σ} γ_{i r p j} y_{i p j}^{(u)} {dv}_{i j} \leq Y_{i p j}^{(r e)} \end{matrix} - - - (9)$

约束条件S5：由于系统中可提供的无线资源和虚拟计算资源有限，用于预留和配置的资源应当不大于系统资源容量，对基站r处的无线带宽资源来说，为

$\underset{i \in I}{Σ} γ_{i r p j} (X_{i r}^{(u)} + X_{i r}^{(o)}) \leq t_{r} - - - (10)$

其中t_r为基站r处当前可用的无线资源量最大值。将式(4)代入转化，需满足

$\underset{i \in I}{Σ} γ_{i r p j} (x_{i r}^{(u)} {db}_{i} + x_{i r}^{(o)} {db}_{i}) \leq t_{r} - - - (11)$

约束条件S6：云数据中心以虚拟机资源的形式为用户提供资源，用分别表示第j类虚拟机资源的CPU处理功率、存储容量及网络内部带宽资源，分别表示数据中心p处的三种资源的最大可用容量，即为

$\begin{matrix} \underset{i \in I}{Σ} \underset{j \in J}{Σ} γ_{i r p j} v_{j}^{(c)} (Y_{i p j}^{(u)} + Y_{i p j}^{(o)}) \leq t_{p}^{(c)} \\ \underset{i \in I}{Σ} \underset{j \in J}{Σ} γ_{i r p j} v_{j}^{(s)} (Y_{i p j}^{(u)} + Y_{i p j}^{(o)}) \leq t_{p}^{(s)} \\ \underset{i \in I}{Σ} \underset{j \in J}{Σ} γ_{i r p j} v_{j}^{(h)} (Y_{i p j}^{(u)} + Y_{i p j}^{(o)}) \leq t_{p}^{(h)} \end{matrix} - - - (12)$

将式(4)代入转化，需满足

$\begin{matrix} \underset{i \in I}{Σ} \underset{j \in J}{Σ} γ_{i r p j} v_{j}^{(c)} (y_{i p j}^{(u)} {dv}_{i j} + y_{i p j}^{(o)} {dv}_{i j}) \leq t_{p}^{(c)} \\ \underset{i \in I}{Σ} \underset{j \in J}{Σ} γ_{i r p j} v_{j}^{(s)} (y_{i p j}^{(u)} {dv}_{i j} + y_{i p j}^{(o)} {dv}_{i j}) \leq t_{p}^{(s)} \\ \underset{i \in I}{Σ} \underset{j \in J}{Σ} γ_{i r p j} v_{j}^{(h)} (y_{i p j}^{(u)} {dv}_{i j} + y_{i p j}^{(o)} {dv}_{i j}) \leq t_{p}^{(h)} \end{matrix} - - - (13)$

联合资源预留配置鲁棒优化模型的求解

上述鲁棒优化目标函数式(2)及其约束条件S1-S6中，对每个包含不确定参数db_i和dv_ij的约束条件，引入参数Γ来控制解的保护程度，约束中至多有个系数可以改变，并通过对偶变化等，将不确定性鲁棒优化问题转化为确定性随机规划问题求解。具体方法如下

对包含不确定参数db_i和dv_ij的约束条件S1的式(2)，引入不确定需求参数集合其中，集合T＝{1,2,…t,…,T}，T＝2I，当且t≤I时，表示第t个用户应用实例的带宽需求db_t不确定，当且I<t≤T时，表示该应用实例的虚拟资源需求不确定；约束参数表明该约束条件中至多有个应用实例的需求参数(db_i或dv_ij)不确定，可能是第i个应用实例的带宽需求db_i不确定，也可能是第i个用户应用实例对第j类虚拟机资源的需求dv_ij不确定，或二者均不确定。调整Γ₀的大小，可以调整需求不确定的应用实例比例数，使该优化模型有一定的可适应性。

将(2)式写成向量形式为：

$\begin{matrix} \underset{r \in R}{Σ} \underset{p \in P}{Σ} \underset{j \in J}{Σ} \vec{d} & {\vec{z}}_{r p j} = \underset{i \in I}{Σ} \underset{r \in R}{Σ} \underset{p \in P}{Σ} \underset{j \in J}{Σ} \end{matrix}, d_{t} z_{t r p j} \leq μ - - - (14)$

其中，当1≤t≤I时， $d_{t} = {db}_{t} \in {\hat{D}}_{b}, z_{t r p} = γ_{t r p j} (x_{t r}^{(u)} C_{r}^{(u)} + x_{t r}^{(o)} C_{r}^{(o)});$

当I≤t≤T时， $d_{t} = {dv}_{(t - I) j} \in {\hat{D}}_{d}, z_{t r p j} = γ_{(t - I) r p j} (y_{(t - I) p j}^{(u)} C_{p j}^{(u)} + y_{(t - I) p j}^{(o)} C_{p j}^{(o)} .$

对上述向量形式进行对偶转化，得到约束条件S1的带约束保护水平的线性的鲁棒逼近形式为：

$(\begin{matrix} \underset{t \in T}{Σ} \underset{r \in R}{Σ} \underset{p \in P}{Σ} \underset{j \in J}{Σ} {\overline{d}}_{t} z_{t r p j} + s_{0} Γ_{0} + \underset{t \in {\hat{T}}_{0}}{Σ} \underset{r \in R}{Σ} \underset{p \in P}{Σ} \underset{j \in J}{Σ} q_{t r p j} \leq μ; \\ \begin{matrix} s_{0} + q_{t r p j} \geq {\hat{d}}_{t} k_{t r p j}, & \forall t \in {\hat{T}}_{0}, r \in R, p \in P, j \in J; \end{matrix} \\ \begin{matrix} 0 \leq z_{t r p j} \leq k_{t r p j}, & \forall t \in T, r \in R, p \in P, j \in J . \end{matrix} \end{matrix}) - - - (15)$

约束条件S2和S3不含不确定参数db_i或dv_ij，因此不做转换。

对包含不确定参数db_i和dv_ij的约束条件S4中的式(9)，分别引入表示带宽需求不确定和虚拟资源需求不确定的应用实例集合，对每个含带宽需求不确定系数db_i的约束条件引入来调整解的鲁棒性和最优性，的物理意义是在接入基站r的应用实例中至多有个应用实例的带宽需求是不确定的，约束条件中不确定系数至多有个可以变化，还有一个系数改变为同理对含虚拟资源需求不确定系数 dv_ij的约束条件引入经过对偶变换，将约束条件S2转化为线性的鲁棒逼近形式为：

$(\begin{matrix} \underset{i \in I}{Σ} γ_{i r p j} x_{i r}^{(u)} \overline{d} b_{i} + s_{r} Γ_{r}^{b} + \underset{i \in {\hat{I}}_{b}}{Σ} w_{i r} \leq X_{r}^{(r e)}, & \forall r \in R; \\ s_{r} + w_{i r} \geq γ_{i r p j} k_{i r} \hat{d} b_{i}, & \forall i \in {\hat{I}}_{b}, r \in R, p \in P, j \in J; \\ 0 \leq x_{i r}^{(u)} \leq k_{i r}, & \forall i \in I, r \in R, p \in P, j \in J . \end{matrix}) - - - (16)$

$(\begin{matrix} \underset{i \in I}{Σ} γ_{i r p j} y_{i p j}^{(u)} \overline{d} v_{i j} + u_{p j} Γ_{p j}^{d} + \underset{i \in {\hat{I}}_{v}}{Σ} v_{i p j} \leq Y_{p j}^{(r e)}, & \forall p \in P, j \in J; \\ u_{p j} + v_{i p j} \geq γ_{i r p j} h_{i p j} \hat{d} v_{i j}, & \forall i \in {\hat{I}}_{v}, p \in P; \\ 0 \leq y_{i p j}^{(u)} \leq h_{i p j}, & \forall i \in I, p \in P . \end{matrix}) - - - (17)$

同理，对包含不确定参数db_i的约束条件S5中的式(11)，引入经过对偶变换，将约束条件S5转化为线性的鲁棒逼近形式为

$(\begin{matrix} \underset{i \in I}{Σ} γ_{i r p j} \overline{d} b_{i} (x_{i r}^{(u)} + x_{i r}^{(o)}) + s_{r}^{'} Γ_{r}^{b} + \underset{i \in {\hat{I}}_{b}}{Σ} w_{i r}^{'} \leq t_{r}, & \forall r \in R; \\ s_{r}^{'} + w_{i r}^{'} \geq γ_{i r p} k_{i r}^{'} \hat{d} b_{i}, & \forall i \in {\hat{I}}_{b}, r \in R; \\ 0 \leq (x_{i r}^{(u)} + x_{i r}^{(o)}) \leq k_{i r}^{'}, & \forall i \in I, r \in R . \end{matrix}) - - - (18)$

同理，对包含不确定参数db_i的约束条件S6中的式(13)，引入经过对偶变换，将约束条件S6转化为线性的鲁棒逼近形式为

$(\begin{matrix} \underset{i \in I}{Σ} γ_{i r p j} v_{j}^{(c)} \overline{d} v_{i j} (y_{i p j}^{(u)} + y_{i p j}^{(o)}) + u_{p j}^{'} Γ_{p j}^{b} + \underset{i \in {\hat{I}}_{v}}{Σ} v_{i p j}^{'} \leq t_{p}^{(c)}, & \forall p \in P, j \in J; \\ u_{p j}^{'} + v_{i p j}^{'} \geq γ_{i r p j} h_{i p j}^{'} \hat{d} v_{i j}, & \forall i \in {\hat{I}}_{v}, p \in P, j \in J; \\ 0 \leq v_{j}^{(c)} (y_{i p j}^{(u)} + y_{i p j}^{(o)}) \leq h_{i p j}^{'}, & \forall i \in I, p \in P, j \in J . \end{matrix}) - - - (19)$

$(\begin{matrix} \underset{i \in I}{Σ} γ_{i r p j} v_{j}^{(s)} \overline{d} v_{i j} (y_{i p j}^{(u)} + y_{i p j}^{(o)}) + u_{p j}^{''} Γ_{p j}^{d} + \underset{i \in {\hat{I}}_{v}}{Σ} v_{i p j}^{''} \leq t_{p}^{(s)}, & \forall p \in P, j \in J; \\ u_{p j}^{''} + v_{i p j}^{''} \geq γ_{i r p j} h_{i p j}^{''} \hat{d} v_{i j}, & \forall i \in {\hat{I}}_{v}, p \in P, j \in J; \\ 0 \leq v_{j}^{(s)} (y_{i p j}^{(u)} + y_{i p j}^{(o)}) \leq h_{i p j}^{''}, & \forall i \in I, p \in P, j \in J . \end{matrix}) - - - (20)$

$(\begin{matrix} \underset{i \in I}{Σ} γ_{i r p j} v_{j}^{(n)} \overline{d} v_{i j} (y_{i p j}^{(u)} + y_{i p j}^{(o)}) + u_{p j}^{'''} Γ_{p j}^{d} + \underset{i \in {\hat{I}}_{v}}{Σ} v_{i p j}^{'''} \leq t_{p}^{(n)}, & \forall p \in P, j \in J; \\ u_{p j}^{'''} + v_{i p j}^{'''} \geq γ_{i r p j} h_{i p j}^{'''} \hat{d} v_{i j}, & \forall i \in {\hat{I}}_{v}, p \in P, j \in J; \\ 0 \leq v_{j}^{(n)} (y_{i p j}^{(u)} + y_{i p j}^{(o)}) \leq h_{i p j}^{'''}, & \forall i \in I, p \in P, j \in J . \end{matrix}) - - - (21)$

综上，经过鲁棒转换之后，目标函数式(2)联合转换后的约束条件S1-S6，是一个易于求解的普通的非线性规划问题，为联合资源预留配置的鲁棒优化模型提供了求解途径，利用非线性规划问题的经典求解方法(如遗传算法等)可求解全局最优无线资源预留量和虚拟机资源预留量和对用户需求取值范围内所有值，即 $\forall {db}_{i} \in [\overline{d} b_{i} - \hat{d} b_{i}, \overline{d} b_{i} + \hat{d} b_{i}], {dv}_{i j} \in [\overline{d} v_{i j} - \hat{d} v_{i j}, \overline{d} v_{i j} + \hat{d} v_{i j}]$ 该鲁棒模型所求得的资源预留量和都是近似最优的，即对一定范围内不确定参数的摄动不敏感，具有一定的鲁棒可适应性。

图4是基于鲁棒优化的联合资源预留配置算法的流程图。以下举例说明在移动云计算中基于本发明进行资源预留配置的方法。

根据历史观测信息设定不同应用实例类型对无线资源和虚拟计算资源的需求值范围 ${db}_{i} \in [\overline{d} b_{i} - \hat{d} b_{i}, \overline{d} b_{i} + \hat{d} b_{i}]$ 和 ${dv}_{i j} \in [\overline{d} v_{i j} - \hat{d} v_{i j}, \overline{d} v_{i j} + \hat{d} v_{i j}],$ 并设定预留周期时间等相关初始值；

对目标函数(2)结合约束条件S1-S6进行求解，中央控制器获取该预留周期的资源预留量和并根据资源预留量在基站和云端数据中心进行资源调预留；

当移动用户应用请求到来时，中央控制器获取确切的用户需求相关信息，并观测当前时刻系统可用的无线资源和虚拟计算资源容量，若充足，则受理用户请求；

结合当前的无线通信环境和云端服务器的工作情况，选取系统所能提供的无线带宽资源配置满意度和虚拟计算满意度中较小的值作为标准，根据计算两种资源分配量之间的匹配值X_ir和Y_ipj。

判别当前可用预留资源是否满足两种资源分配量的匹配值，若满足，则按匹配量为用户分配无线资源和虚拟资源，若不足，则优先调度预留资源分配，未满足的过需部分由系统调度未预留的资源部分以较高的价格进行补偿分配。

资源分配完成后，移动应用开始运行，预留周期结束后回收资源。

去获取专利，查看全文>

相似文献

专利
中文文献
外文文献

1. 移动云计算中一种基于鲁棒优化的联合资源预留配置算法 [P] . 中国专利： CN105446817B . 2019.01.22
2. 移动云计算中一种基于鲁棒优化的联合资源预留配置算法 [P] . 中国专利： CN105446817A . 2016-03-30
3. The ‘Property Identification Method’ (“PIM”) is a novel algorithm through which a Real Estate Authority and/or Conveyancing data is created through image-processing a document such as a Council/Shire Rates Notice. This invention establishes a unique algorithm incorporating techniques such deep learning segmentation and computer vision to decode property information. This application utilises computer-implemented technology configured in such manner as to enable conveyancers and real estate agents to automate the creation of client files. [P] . AU2020102233A4 . 2020-10-29

机译： “财产识别方法”（“ PIM”）是一种新颖的算法，通过该算法，可以通过对文件（如市议会/房屋价格通知）进行图像处理来创建房地产管理局和/或产权转让数据。本发明建立了一种独特的算法，该算法结合了诸如深度学习分段和计算机视觉之类的技术来解码属性信息。该应用程序利用以某种方式配置的计算机实现的技术，以使运输商和房地产经纪人能够自动创建客户端文件。
4. 1. A binder is used to combine two substrates, one containing a base and one water binder, which is based on the scattering of chlorinated polyolefins and additives, and one of the substrates is treated with an active agent. [P] . CL2012000460A1 . 2012-08-31

机译： 1.粘合剂用于结合两种基材，其中一种包含碱和一种水粘合剂，这是基于氯化聚烯烃和添加剂的散射，并且其中一种基材用活性剂处理。
5. Mapping and distributing parallel algorithms to compute nodes in a parallel computer based on temperatures of the compute nodes in a hardware profile and a hardware independent application profile describing thermal characteristics of each parallel algorithm [P] . 美国专利： US7953957B2 . 2011-05-31

机译：基于描述每个并行算法的热特性的硬件配置文件和独立于硬件的应用程序配置文件中计算节点的温度，将并行算法映射和分配到并行计算机中的计算节点