带流量约束的星型图背包问题

发布时间：2017-05-23 23:02

  本文关键词：带流量约束的星型图背包问题，由笔耕文化传播整理发布。

【摘要】：高速发展的互联网技术,企业对提高资源利用率和降低能耗的不断上升的需求,以及用户追求方便获取软硬件资源的愿望,共同促使了云计算的快速兴起。云计算结合6T技术和互联网思想实现强大的计算和存储能力,其关键技术虚拟化使得资源分配的粒度更加细化,从而提高资源利用率。承载客户服务的虚拟机放置到云平台上运行,申请计算、存储以及网络资源,并付给云平台费用。对于特定的云平台来说,物理资源总是有限的,而用户资源的请求总是无限的。但有限的物理资源满足不了无限的用户请求,因此最大化收益便成了云平台资源分配的重要目标。本文将该资源优化问题建模为图上的背包问题,考虑物理资源组织成星型图网络结构,使用确定型和启发式两种算法求解。确定型方法给出问题的整数规划形式,使用lpsolve工具计算最优解。针对星型图背包问题的特殊子问题,给出了最优值表达式以及最优解求解过程。由于求解整数规划的时间复杂度较高,较大规模的问题很难用该方法在较短时间内得到解,因此本文还考虑了启发式算法,使用的是贪心算法,并设计了几种贪心策略。实验结果表明,该算法较好地适用于小规模问题,对于规模较大的场景也可以快速地求解,虽然结果稍差一些。当虚拟机请求资源相对网络中物理资源和带宽资源较小时结果更好,而实际应用场景往往是符合该情况的。对比虚拟机放置的两种背包选择策略,worst-fit比best-fit实验结果更好。
【关键词】：背包问题 星型图 整数规划 贪心算法
【学位授予单位】：浙江大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP393.02
【目录】：

• 摘要4-5
• Abstract5-10
• 1 绪论10-13
• 1.1 课题背景10-11
• 1.2 研究意义11
• 1.3 主要工作11
• 1.4 本文结构11-12
• 1.5 本章小结12-13
• 2 云计算13-21
• 2.1 计算的服务模型13-14
• 2.2 云平台的部署方式14-16
• 2.3 云计算的应用和优缺点16-17
• 2.4 云计算的关键技术17-19
• 2.4.1 虚拟化技术17-18
• 2.4.2 编程模式18
• 2.4.3 数据存储和管理18-19
• 2.5 虚拟机19-20
• 2.6 本章小结20-21
• 3 背包问题概述及研究现状21-28
• 3.1 背包问题的概述21-22
• 3.2 背包问题的分类及其应用22-25
• 3.2.1 多背包问题22-23
• 3.2.2 多维度背包问题23
• 3.2.3 优先约束背包问题23-24
• 3.2.4 多选择背包问题24
• 3.2.5 多目标背包问题24-25
• 3.3 背包问题的算法分类25-27
• 3.3.1 动态规划算法25
• 3.3.2 分支定界算法25-26
• 3.3.3 禁忌搜索26
• 3.3.4 混合算法26-27
• 3.4 本章小结27-28
• 4 星型图背包问题的精确求解28-42
• 4.1 图上的背包问题28-34
• 4.1.1 问题的描述28-29
• 4.1.2 网络拓扑结构29-34
• 4.2 星型图背包问题34-41
• 4.2.1 问题描述和模型建立34-35
• 4.2.2 lpsolve求解整数规划35-37
• 4.2.3 特殊情况求解和理论分析37-41
• 4.3 本章小结41-42
• 5 贪心算法在星型图背包问题中的应用42-55
• 5.1 贪心算法概述42-43
• 5.2 星型图背包问题的贪心算法设计43-44
• 5.3 实验数据设计44-45
• 5.4 实验及其结果分析45-54
• 5.4.1 规模大小的比较45-47
• 5.4.2 物品排序方式的比较47-49
• 5.4.3 背包选择顺序的比较49-53
• 5.4.4 应用场景的比较53-54
• 5.5 本章小结54-55
• 6 总结和展望55-57
• 6.1 总结55
• 6.2 展望55-57
• 参考文献57-59
• 致谢59

【相似文献】

中国期刊全文数据库 前10条

1 何文明,朱起定;背包问题的循环及并行解[J];湘潭师范学院学报(社会科学版);2000年03期

2 任瑞征,严蔚敏;整数背包问题的应用及其算法研究[J];小型微型计算机系统;2001年02期

3 叶俊,刘贤德,韩露;基于博弈论的背包问题优化算法[J];华中科技大学学报(自然科学版);2003年09期

4 罗小虎,赵雷;一个解决0/1背包问题的蚁群方法[J];苏州大学学报(工科版);2004年01期

5 宋翔,聂义勇,储诚斌;无限制背包问题的爬山算法[J];小型微型计算机系统;2004年07期

6 谢涛,陈火旺,康立山;二次背包问题的一种快速解法[J];计算机学报;2004年09期

7 王喜凤;浅析0/1背包问题[J];电脑知识与技术;2004年29期

8 华中生,张斌;求解可分离连续凸二次背包问题的直接算法[J];系统工程与电子技术;2005年02期

9 宋海洲;魏旭真;;求解0-1背包问题的混合遗传算法[J];华侨大学学报(自然科学版);2006年01期

10 熊伟清;魏平;王小权;;蚁群算法求解多维0/1背包问题[J];计算机工程与科学;2006年10期

中国重要会议论文全文数据库 前6条

1 乔善平;朱波;赵玲;;基于移动Agent的0-1背包问题分布式求解[A];2008'中国信息技术与应用学术论坛论文集（一）[C];2008年

2 高尚;;背包问题的分布估计算法[A];2013年中国智能自动化学术会议论文集（第五分册）[C];2013年

3 徐俊杰;忻展红;;粒子群优化在0/1背包问题中的应用[A];中国运筹学会第七届学术交流会论文集（上卷）[C];2004年

4 姜宇;苏中滨;郑萍;;求解O/1背包问题的算法综述[A];黑龙江省计算机学会2009年学术交流年会论文集[C];2010年

5 刘裴寰;姜青山;王备战;史亮;;基于K均值聚类求解多维背包问题的算法[A];第二十三届中国数据库学术会议论文集（技术报告篇）[C];2006年

6 李伟;吕克伟;;类背包DH问题的比特安全性研究[A];第28次全国计算机安全学术交流会论文集[C];2013年

中国博士学位论文全文数据库 前1条

1 TRUONG KHAC TUNG;[D];湖南大学;2013年

中国硕士学位论文全文数据库 前10条

1 史如意;带流量约束的星型图背包问题[D];浙江大学;2015年

2 潘夏福;混合蚁群算法求解0-1背包问题[D];厦门大学;2008年

3 朱阅岸;解0-1背包问题的算法比较和改进[D];暨南大学;2011年

4 史今驰;背包问题的实用求解算法研究[D];山东大学;2005年

5 郑杨凡;基于属性论的0-1背包问题算法研究[D];上海海事大学;2005年

6 李其;有偿在线背包问题的研究[D];大连理工大学;2012年

7 孟晓笑;并行环境下0-1背包问题的解决策略[D];湖北大学;2011年

8 钟海林;背包问题的一种新算法：降维递归算法[D];江西师范大学;2008年

9 赵培怡;改进群体智能算法及其在背包问题中的应用[D];山东大学;2007年

10 周钱;多选择多约束背包问题的进化求解策略[D];中国科学技术大学;2011年

  本文关键词：带流量约束的星型图背包问题，由笔耕文化传播整理发布。

，

本文编号：389264