一种基于移动云计算且有预算约束的多任务分配机制.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN106815081A(43)申请公布日2017.06.09(21)申请号201710058590.7(22)申请日2017.01.23(71)申请人武汉万般上品信息技术有限公司地址430070湖北省武汉市东湖新技术开发区光谷大道303号光谷芯中心2-07栋201-03室(72)发明人李宗鹏黄浩(74)专利代理机构武汉科皓知识产权代理事务所(特殊普通合伙)42222代理人鲁力(51)Int.Cl.G06F9/50(2006.01)权利要求书2页说明书5页附图2页(54)发明名称一种基于移动云计算且有预算约束的多任务分配机制(57)摘要本发明公开了一种基于移动云服务且有预算约束的多任务分配机制；利用新型移动云cloudlet作为服务，将移动设备用户提出的资源请求分配到各个cloudlet上。针对用户到达的随机性以及实际中每个用户的预算约束，定义一个在线的多任务分配机制，同时引入round-by-round算法将在线的处理分为以时隙为单位的单轮分配机制，有效的解决了在线算法的困难。在处理单轮分配时，利用tailoreddependentrounding算法将分式解变成整数解，并取得一个很好地近似比。从而设计出一个同时具有计算可行以及经济有效的多任务分配机制。CN106815081ACN106815081A权利要求书1/2页1.一种基于移动云服务且有预算约束的多任务分配机制，其特征在于，包括以下步骤：步骤1：将收益最大化的多任务分配写成整数线性规划；由于条件的复杂度较大，利用round-by-round算法将online分解为多轮分配，每一轮之间都依靠用户的budget相互连接，任务分配机制将一个时隙作为一轮分配；步骤2：初始化缩减因子为第一轮分配时用户对每个任务的估价用户估价与预算的最大比值参数步骤3：第t轮分配开始，开始时：t＝1，将所有缩减因子的用户进行任务分配，并将已分配的用户的任务放入集合ψ中，用户每轮至多被分配一个任务；具体包括：步骤3.1：解线性规划得到分式解θ′inm；步骤3.2：计算并根据以下步骤构建二分图，二分图左边的点(ain)代表每个用户的任务，右边Lm个点bml代表对应的cloudlet：步骤3.3：如果就将这条边放入匹配集合中并从边集合W中删除；步骤3.4：当二分图中存在一个环或是一个最长路径时，将这个环或是最长路径分为两2CN106815081A权利要求书2/2页个匹配集合(S1,S2)，找到η与ζ，使得然后以概率******在集合S1中更新θ＝θ-η，在集合S2中更新θ＝θ+η；以概率在集合S1中更新θ＝θ+ζ，**在集合S2中更新θ＝θ-ζ；步骤3.5：如果就将这条边放入匹配集合中并从边集合W中删除；如果从边集合W中删除；如果仍然存在一个环或者最长路径，返回步骤3.4继续执行，直到找不出一个环或是最长路径；步骤3.6：如果边集合W中仍有剩余边，令该边的权重为1，即步骤3.7：更新整数解步骤4：如果用户i的一个任务被分配，就更新该用户的递减因子并且更新每一轮新的任务价格这里更新每一轮用户的任务价格是因为设计在线的多任务分配机制时，每一轮拍卖是依靠预算相互联系的，为了使用户在后期的分配过程中仍然可以提出申请，需要对用户任务的价格进行修改，即逐轮减小每个任务的价格；如果某个用户的缩减因子则停止申请资源，不能进入后续的任务分配；步骤5：返回步骤3，直到完成T轮分配。2.根据权利要求1所述的一种基于移动云服务且有预算约束的多任务分配机制，其特征在于，所述步骤3.2的具体方法包括：步骤3.2.1、将所有的任务点按照价格的大小排序；*步骤3.2.2、如果∑i∑nθ′inm≤1，将(ain,bml)放入边的集合W，并将边的权重设为θ(ain,bml)＝θ′inm；步骤3.2.3、如果∑i∑nθ′inm>1，对所有l＝2,...,Lm，将nil作为一个分割点，下标在这个*之前的边放入集合W，并将边的权重设为θ(ain,bml)＝θ′inm，下标在这个之后的边权重更新*为θ(ain,bml)＝1-∑i∑nθi′nm；步骤3.2.4、重复步骤3.21至步骤3.23直到二分图建立完成。3CN106815081A说明书1/5页一种基于移动云计算且有预算约束的多任务分配机制技术领域[0001]本发明属于计算机网络的移动云计算领域，尤其是一种基于移动云计算且有预算约束的多任务分配机制。背景技术[0002]目前移动设备已经成为生活中必不可少的一部分，例如手机，平板电脑等无地域时间限制的通信工具。但是移动设备的内存，电池容量或带宽是有限的，不利于多任务的处理。云计算的出现为用户提供了快速的按需资源分配，例如CPU,RAM,内存和带宽等的资源分配。所以移动云计