云计算环境下基于粒子群算法的多目标优化

２０１３年７月　计算机工程与设计　Ｊｕｌｙ　２０１３　第３４卷第７期　ＣＯＭＰＵＴＥＲ　ＥＮＧＩＮＥＥＲＩＮＧ　ＡＮＤ　ＤＥＳＩＧＮ　Ｖｏ１．３４　Ｎｏ．７　云计算环境下基于粒子群算法的多目标优化　郭力争　，耿永军　，姜长源。，王军豪　，张娜。，赵曙光　（１．河南城建学院计算机科学与工程系，河南平顶山４６７０３６；　２．东华大学信息学院，上海２０１６２０）　摘要：为了优化资源的部署调度，需要考虑处理费用、传输费用，并提高云计算的性能。对云计算环境下特点进行了研　究，把云计算环境下的数据部署和任务调度问题映射为处理交互图，对处理交互图进行分析、提出了多目标优化模型，并　通过粒子群算法对多目标模型进行优化。仿真结果表明，该多目标优化模型和算法不但能优化处理时间、传输时间，也能　优化处理费用和传输费用。　关键词：云计算；粒子群算法；数据部署；任务调度；多目标优化　中图法分类号：ＴＰ３９３　文献标识号：Ａ　文章编号：１０００—７０２４（２０１３）０７—２３５８—０５　Ｍｕｌｔｉ—ｏｂｊ　ｅｃｔｉｖｅ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｂａｓｅｄ　ｏｎ　ｐａｒｔｉｃｌｅ　ｓｗａｒｍ　ｏｐｔｉｍｉｚａｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｉｎ　ｃｌｏｕｄ　ｃｏｍｐｕｔｉｎｇ　ＧＵＯ　Ｌｉ—ｚｈｅｎｇ　，ＧＥＮＧ　Ｙｏｎｇ－ｊｕｎ　，ＪＩＡＮＧ　Ｃｈａｎｇ－ｙｕａｎ。，　ＷＡＮＧ　Ｊ　ｕｎ—ｈａｏ　，ＺＨＡＮＧ　Ｎａ。，ＺＨＡＯ　Ｓｈｕ－ｇｕａｎｇ　（１．Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｈｅｎａｎ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｕｒｂａｎ　Ｃｏｎｓｔｒｕｃｔｉｏｉｎ，Ｐｉｎｇｄｉｎｇｓｈａｎ　４６７０３６，Ｃｈｉｎａ：２．Ｃｏｌｌｅｇｅ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｄｏｎｇｈｕａ　Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ　２０１６２０，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｉｎ　ｃｌｏｕｄ　ｃｏｍｐｕｔｉｎｇ，ｒｅｓｏｕｒｃｅ　ｓｃｈｅｄｕｌｉｎｇ　ｉｓ　ａ　ｈｏｔ　ｉｓｓｕｅ　ｉｎ　ｒｅｓｃｅｎｔ　ｒｅｓｅａｒｃｈ，ｉｎ　ｏｒｄｅｒ　ｔＯ　ｏｐｔｉｍｉｚｅ　ｔｈｅ　ｒｅｓｏｕｒｃｅ　ｓｃｈｅｄｕｌｉｇｎ，ｎｅｅｄ　ｔｏ　ｃｏｎｓｉｄｅｒ　ｔｈｅ　ｐｒｏｃｅｓｓｉｇｎ，ｔｈｅ　ｔｒａｎｓｆｅｒｉｎｇ　ｃｏｓｔ　ａｎｄ　ｔＯ　ｉｍｐｒｏｖｅ　ｔｈｅ　ｐｅｒｆｏｒｍａｎｃｅ．Ｔｈｅ　ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ　ｏｆ　ｃｌｏｕｄ　ｃｏｍｐｕｔｉｎｇ　ｉｓ　ｓｔｕｄｉｄｅ，ｔｈｅｎ，　ｔｈｅ　ｄａｔａ　ｐｌａｃｅｍｅｎｔ　ａｎｄ　ｔａｓｋ　ｓｃｈｅｄｕｌｉｎｇ　ｒａｅ　ｍａｐｐｅｄ　ｔＯ　ｐｒ￣ｅｓｍｒｓ　ｉｎｔｅｒａｃｔｉｏｎ　ｇｒａｐｅ　Ａ　ｍｕｌｔｉ－ｏｂｊｅｃｔｉｖｅ　ｏｐｔｉｍｉｚｉｎｇ　ｍｏｄｅｌ　ｉｓ　ｆｏｒｍｕｌａｔｄｅ　ｔ￣ｏｕｇｈ　ａｎａｌｙｚｉｇｎ　ｔｈｅ　ｐｍｃｅｓｍｒｓ　ｉｎｔｅｒａｃｔｉｏｎ　ｇｒａｐｈ．Ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｐｒｏｐｏｓｅｄ　ｍｏｄｅｌ，ａ　ｐａｒｔｉｃｌｅ　ｓｗａｒｍ　ｏｐｔｉｍｚａｔｉｏｎ　ａｌｇｏｒｉｔｈ　ｉｓ　ｕｓｅｄ　ｔｏ　ｏｐｔｉ—　ｍｉｅｚ　ｔｈｅ　ｄａｔａ　ｄｅｐｌｏｙｍｅｎｔ　ｎａｄ　ｔａｓｋ　ｓｃｈｅｄｕｌｉｎｇ．Ｔｈｅ　ｓｉｍｕｌａｔｉｏｎ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ｍｕｌｔｉ－ｏｂｊｅｃｔｉｖｅ　ｍｏｄｅｌ　ｉｓ　ｎｏｔ　ｏｎｌｙ　ｏｐｔｉｉｍｚｅ　ｔｈｅ　ｔｉｍｅ　ｏｆ　ｐｒｏｃｅｓｓｉｎｇ　ａｎｄ　ｔｒａｎｓｆｅｒｉｇｎ，ｂｕｔ　ａｌｏｓ　ｏｐｔｉｍｉｅｚ　ｔｈｅ　ｔｈｅ　ｃｏｓｔ　ｏｆ　ｐｒｏｃｅｓｓｉｇｎ　ａｎｄ　ｔｒａｎｓｆｅｒｉｎｇ．　Ｋｅｙ　ｗｏｒｄｓ：ｃｌｏｕｄ　ｃｏｍｐｕｔｉｎｇ；ｐａｒｔｉｃｌｅ　ｓｗａｒｍ　ｏｐｔｉｍｉｚａｔｉｏｎ；ｄａｔａ　ｄｅｐｌｏｙｍｅｎｔ；ｔａｓｋ　ｓｃｈｅｄｕｌｉｎｇ；ｍｕｌｔｉ－ｏｂｊｅｃｔｉｖｅ　ｏｐｔｉｍｉｚａｔｉｏｎ　０引　言　问题；文献［３］针对云计算服务集群资源调度和负载平衡　优化问题，将动态多群体协作和变异粒子逆向飞行思想引　云计算通过大规模的数据中心，向用户提供强大的计　入到粒子群优化算法中；文献ｒ４－］实现应用层服务质量到　算能力、海量数据存储能力，并且比一般的数据中心更加　资源设备层服务质量的映射，利用效用函数的管理策略实　经济和节能。文献［１］说明云计算有很多优点，但也有许　现资源的优化调度；文献［５］针对传统遗传算法易陷入早　多急需解决的问题；文献Ｅｅｌ引入学习机制等方法对非支　熟收敛等问题，提出一种改进的元胞自动机遗传算法并应　配排序遗传算法进行改进，将其应用于云计算的节能调度　用于云环境下的资源调度。以上文献主要优化的任务的执　收稿日期：２０１２—１０—２２；修订日期：２０１２—１２—２８　基金项目：国家自然科学基金项目（７０９７１０２０）；河南省科技计划重点科技攻关基金项目（１２２１０２２１０４１２）；河南省教育厅科学技术研究重　点基金项目（１２Ａ５２０００６）　作者简介：郭力争（１９７５一），男，河南开封人，博士研究生，讲师，研究方向为云计算、数据部署、任务调度、绿色计算；耿永军（１９７１一），　男，河南平顶山人，博士，副教授，研究方向为网络安全；姜长元（１９７５一），男，安徽安庆人，博士研究生，讲师，研究方向为智能计　算；张娜（１９８０一），女，河南周口人，博士研究生，讲师，研究方向为智能计算、网络；王军豪（１９８０一），男，河南平顶山人，博士研究　生，讲师，研究方向为智能计算、网络；赵曙光（１９６５一），男，陕西西安人，博士，教授，研究方向为进化计算等。　Ｅ－ｍａｉｌ：ｋｆｔｊｈ＠ｙａｈｏｏ．ｃｏｒｎ．ｃｎ　第３４卷第７期　郭力争，耿永军，姜长源，等：云计算环境下基于粒子群算法的多目标优化　・２３５９・　行时间，没有考虑任务的执行费用和数据的传输时间、传　输费用；文献Ｅ６］提出了在数据密集型应用环境下的一个　非线性规划模型，其目的是最小化数据检索，没有考虑费　用的优化问题；文献Ｅ７］探讨了云代理和多个云虚拟机管　理的体系结构，其体系结构里面描述了数据在多个云中部　之间需要进行通信，带宽为ｅ，ｇ一１０Ｍ。Ｔ１５表示任务Ｔ１产　生一个数据要任务　处理，数据大小为３５０Ｍ。　署及优化的问题，在多个云之间部署数据改善了性能、降　低了费用，但仅仅优化了处理费用；文献［８］提出了数据　密集型的应用环境下减少数据移动次数的Ｋ－ｍｅａｎｓ聚类算　法，该算法侧重如何减少数据的移动次数，而没有考虑数　据的移动时间和传输时间；文献Ｅ９—１１］对网格和云计算　环境下的数据部署策略进行了研究，但仅仅优化处理和传　输的时间。考虑到云计算中数据中心之间带宽的有限性，　使用和传输数据的费用在不同的数据中心间会有差异，因　此我们提出多目标优化部署策略。我们不但考虑传输和处　理的时间，而且考虑传输和处理的费用。数据的部署问题　已经被认为是ＮＰ－ｈａｒｄ（ｎｏｎ－ｄｅｔｅｒｍｉｎｉｓｔｉｃ　ｐｏｌｙｎｏｍｉａ１）问　题，处理这些问题一般运用启发式算法，例如遗传算法　（ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ，ＧＡ）文献［１２—１３］。文献［１４］证实在　分布式环境下基于生物群体智能的粒子群优化算法（ｐａｒｔｉｃｌｅ　ｓｗＤａ－ｒｎ　ｏｐｔｉｍｉｚａｔｉｏｎ，ＰＳＯ）的质量和收敛速度均优于ＧＡ，所　以本文采用ＰＳＯ算法对数据部署问题进行优化。　１多目标优化建模　１．１云计算环境下数据部署问题描述　在云计算中，一方面数据中心有很多的物理机，这些　物理机多达数万到数十万；另一方几个虚拟机部署到同一　个物理机上，不同的数据中心之间的带宽往往有限，不同　的数据中心之间要处理和传输大量的数据。获取高性能，　低费用的数据部署就成为一个挑战性的问题。可以把这一　问题描述为把数据部署到各个数据中心，使得处理和传输　的时间、费用最小。云计算环境下数据部署问题可以作为　一个映射来处理，把任务的数据和对数据的处理映射为处　理交互图（ｐｒｏｃｅｓｓｏｒｓ　ｉｎｔｅｒａｃｔｉｏｎ　ｇｒａｐｈ，ＰＩＧ）。在处理交　互图中，点的集合　一｛　．ｖ２，…踟｝为Ｍ个数据中心，　边的集合Ｅ代表数据中心之间的交互。每一个点　表示一　个数据中心，数据中心有一个权重ｗ，代表数据中心的处　理能力，每一个点分配一个或多个数据和任务。如果两个　数据中心之间有通信，数据中心之间有一个边ｅ，每个边有　个权重　，表示数据中心之间的带宽。为了更好的理解处　理交互图，通过一个例子来说明，如图１所示，在图１中　有５个任务被分配到３个数据中心，数据中心ＤＣ１的权重　Ｗ１—５００，表示数据中心１每秒能处理５００万条指令。任　务ｎ，有一个数据Ｄ１，数据量为５００万条指令，如果任　务Ｔ１分配到数据中心ＤＣＩ，只需１秒钟就可以处理完毕。　任务Ｔ３，有数据Ｄ３，数据量为８５０万条指令。任务ｎ，　Ｔ３分配到数据中心ＤＣ１。ＤＣ１和Ｄｃ３之间有边表示他们　图１处理交互　整个　的处理时间　为：—５０　０＋　８５０　＋　１０００　十　　。７５０　≈５．６７秒，传输时间为　…一　’　１Ｏ　一３５秒。如果数据中心Ｔ１，Ｔ２，Ｔ３的处理费用分别为每秒　０．３２０￥，０．３６０￥，０．３６８￥，不同的数据中心之间的传递　数据的收费标准为：１￥ｐｅｒ　ＧＢ，则处理费用为：　＊Ｏ．３２＋１—００＋３５—而０＋广５００＋一３５０＊０．３６８＋　８ｏ＿＿９ｏ＊０７．５０３６≈１．７３￥，传输费用为：　＊１＝ｏ．３５￥。　１．２建模　云计算中数据中心的处理费用根据处理能力、提供商、　地点等不同而收费标准也不同。传输费用由传输的数据量　的大小决定，处理费用一般是按处理时间来收费的。　为了更清晰的建立数据分配和任务调度的数学模型，　对一些概念做一说明：在处理交互图中任务　：ｉ＝｛１，　２，…，　）为　个任务，每个任务的数据量映射为百万条　指令，用来衡量一个任务的复杂程度。ＤＰ　表示任务ｔ　需　要处理的数据量，ＤＧ：尼一｛１，２，…，ｍ）为Ｍ的数据中　心，每个数据中心的性能以每秒能处理多少百万条指令来衡　量。晚：ｋｌ＝｛１，２，…，　）为两个数据中心之间的带宽，　ｍ为总的数据中心数。Ｄ　是任务ｔｉ和　之间交换的数据　量，这个数据是任务ｔｉ产生的，任务￡，需要的，并需要从任　务　分配的数据中心传输到任务　分配的数据中心。　处理时间定义为：任务的数据量除以数据中心的处理　能力，如式（１）：　定义为所有的数据分配到相应的数据　中心的整个的处理时间。∑∑ｚ　其中　表示　＋４￣ｇ－，　ｍ表示ｍ个数据中心，如果任务　分配到数据中心是，　３２　＝１，否则ｚ　＝ｏ，∑∑３２　表示把　个任务分配到ｍ　个数据中心。　表示任务ｔｉ分配到数据中心ＤＣ　的处　理时间　一　×兹　㈩　・２３６０・　计算机工程与设计　２０１３正　传输时间定义为：需要传输的数据量除以数据中心之　间的带宽，如式（２）：　表示不同的任务分配到相应的数　取值范围为ｌ或０，为１时表示某个任务分配到某个数中　心，否则为０　ｚ　一１，Ｖ　ｉ—Ｉ，２，…，　＝据中心后，任务之间由于需要其他任务的数据，这些数据　（７）　需要从其他的数据中心传过来的时间。∑∑∑∑　×　ｉ　ｌ　ｊ＝１女　１￡≠＾　１　ｚ　表示任务ｔ　分配到数据中心ＤＣ　，ｚ　一１，任务ｔｊ分配　∑∑∑∑ｚ　×Ｘｊ　一１，　一１　１　一１　Ｚ≠　Ｖｉ，　一１，２，…，，２，Ｖ忌，￡一１，２，…，ｍ　（８）　到数据中心ＤＣ　，Ｘｊ　一１，ｚ≠　表示任务ｔ　和任务ｔ　分配到　不同的数据中心，在这种情况下，如果任务　需要任务ｔ　ｒＹｒ　产生的数据，则需要的传递时间为　；如果一个任务　Ｄｋ／　ｔ　，　分配到同一个数据中心，那么他们之间就不需要进行　数据的传输。式（３）表示总的处理时间Ｔ等于处理时间　Ｔ　和传输时间Ｔ　之和　一∑∑∑∑ｚ　×　×　ｉ＝１　ｊ一１　一１　Ｚ≠　一　（２）　Ｔ＝Ｌ＋　（３）　亚马孙提供了３种类型的收费方式［１　，本文中采用按　需的收费方式（ｏｎ－ｄｅｍａｎｄ　ｉｎｓｔａｎｃｅｓ）如表１所示，按小时　购买计算能力。数据的传输费用为不同的数据中心之间传　输数据￥０。０１　ｐｅｒ　ＧＢ，操作系统采用Ｌｉｎｕｘ／ＵＮＩＸ。根据　处理数据的费用按时间计算和传输数据费用按传输量计算　的收费方式，我们来建立计算费用的公式。式（４）表示处　理费用Ｃ　，处理费用为处理时间　乘以单位数据的处理　费用　。定义　为从数据中心ＤＣ　传出的数据的收费标　准，　为数据传人到ＤＣ　的收费标准。式（５）表示的是　传输费用Ｇ为传人的收费标准Ｐ　乘以传人的数据量ＤＴ　加传出的收费标准Ｐ　乘以传出的数据量ＤＴ　之和。式　（６）为总的费用Ｃ等于传输费用Ｇ加处理费用Ｃ　之和　Ｃ　＝　×Ｐｋ　（４）　Ｇ一∑∑∑∑　×　×（ＤＴ　×　＋ＤＴ　×　）　（５）　Ｃ—　＋Ｃ，　（６）　表１按需使用的收费方式　式（７）～式（９）为约束性条件，约束条件（７）表示　一个任务必定分配到一个数据中心，约束条件（８）表示如　果两个任务分配到不同的数据中心，并且他们之间有数据　通信的需求，∑∑∑∑ｚ　×ｘｊｔ一１　ｉ＝１　ｋ＝１　ｚ≠　ｌ＝１，否则　∑∑∑∑ｚ　×　一０，约束条件（９）表示Ｘ　，ＹＪ　的　ｚ　，∞￡∈｛０，１｝，Ｖｉ，　一１，２，…，　，Ｖｋ，Ｚ一１，２，…，ｍ　（９）　２粒子群算法　粒子群优化算法于１９９５年被Ｋｅｎｎｅｄｙ和ＥｂｅｒｈａｒｔＥ“　提　出的智能进化算法。这种算法的思想是模拟动物群体的觅　食活动，通过群体之间协调配合，进而取得最优的结果。　该算法的优点是实现容易、收敛速度快、求解精度高。　ＰＳＯ随机初始化为一群随机粒子（候选解），然后通过适应　值函数计算出每个粒子的值，作为自己的最优值ｐｂｅｓｔ，从　所有粒子的最优值中再算出最优的极值作为全局极值　ｇｂｅｓｔ。计算出个体极值ｐｂｅｓｔ和全局极值ｇｂｅｓｔ后，通过式　（１Ｏ）迭代更新每个粒子速度，通过式（１１）迭代更新每个　粒子的位置，通过一次一次的迭代更新，使每个粒子都向　最优的位置靠近，从而找到最优解。在每一次迭代后都要　更新个体极值和全局极值，在更新ｐｂｅｓｔ，ｇｂｅｓｔ时，通过适　应性函数计算出最新适应值和个体极值、全局极值进行比　较，如果优于极值更新，否则不变　一ｃ田　＋Ｃｌｒａｎｄｌ×（ｐｂｅｓｔｆ—　）＋　Ｃ２ｒａｎｄ２×（ｇｂｅｓｔ一　）　（１０）　一　＋　（１１）　２．１粒子群的初始化　粒子群的初始化位置和速度都是随机产生的矢量，我　们根据文献［１７］的方法来初始化位置和速度。初始化根　据式（１２）和式（１３）来进行，其中ｚ一＝　＝４．ｏ，　＝‰—一ｏ．４来设定。由于位置为连续的变量，任务　分配为离散的组合，因此我们应当把连续的变量转变为离　散的变量来处理。根据文献［１８］，运用ｓｍａｌｌ　ｐｏｓｉｔｉｏｎ　ｖａｌ—　ｕｅ（ＳＰＶ）规则来把连续的变量转变为离散的变量，具体实　现通过式（１４）来实现　—Ｘｒ￣ｉｆ　＋（　一　丽　）×ｒａｎｄ　（１２）　＝７Ｊａｌｉ　＋（‰　一＇Ｕｒｍ　）×ｒａｎｄ　（１３）　＝　ｍｏｄｍ＋１　（１４）　２．２算法的实现　在粒子群算法中，每个粒子都是一个候选解，每个粒　子有Ｎ维，这Ｎ维依赖于特定的研究问题。在我们的研究　问题中Ｎ就是要分配的任务，把Ｎ个任务分配到Ｍ个数　据中心，使得处理时间、传输时间、处理费用、传输费用　最小。每一个粒子迭代更新直到获得理想的结果或者达到　第３４卷第７期　郭力争，耿永军，姜长源，等：云计算环境下基于粒子群算法的多目标优化　・２３６１・　迭代设定值，详细的算法如图２所示。　ＰＳＯ算法　（１）根据式（１２）和式（１３）初始化位置和速度矢量，矢量的　维数为任务的个数Ｎ。　（２）首先根据ＳＰＶ规则把连续的矢量（ｚ　ｉ，ｚ　，…，ｚ　］）　转换为离散的矢量（Ｓ；一［ｓ　，５　，…，ｓ　］），然后根据式（１４）　把离散的矢量转换为处理矢量（Ｐ　一［ｐｉ，Ｐ；，…，　］）。　（３）根据式（６）计算每个粒子的适应性函数值，把每个粒子的　适应性函数值作为ｐｂｅｓｔ，所有粒子中适应值最小的作为ｇｂｅｓｔ。　（４）所有的粒子根据式（１２）和式（１３）分别更新粒子的位置　和速度矢量。　（５）根据ＳＰＶ规则把连续的矢量（－ｚ　＝Ｅｘｉ，　，…，ｚ：］）转换　为离散的矢量（ｓ；一［ｓｌ，ｓ　，…，ｓ　］），然后根据式（１４）把离　散的矢量转换为处理矢量（Ｐ　一Ｅｐｉ，Ｐ；，…，　］）。　（６）根据式（６）计算每个粒子的适应性函数值，如果粒子的适　应性函数值小于ｐｂｅｓｔ，则用当前的适应值更新ｐｂｅｓｔ，否则　ｐｂｅｓｔ不变；从所有的粒子的适应值中选取最小的，如果其值小　于ｇｂｅｓｔ，则用其最小的适应值更新ｇｂｅｓｔ，否则ｇｂｅｓｔ不变。　（７）如果迭代达到了设定的值算法结束，否则到第（４）步继续　执行算法。　图２　ＰＳＯ算法　３仿真环境的建立与仿真结果分析　３．１仿真环境的建立　我们建立了仿真环境。测试硬件为：ＡＭＤ　Ｐｈｅｎｏｍ　Ｅｔｍ］ⅡＸ４　Ｂ９５　３．０　ＧＨｚ，２Ｇ　ＲＡＭ软件为：Ｍｉｃｒｏｓｏｆｔ　Ｗｉｎｄｏｗｓ　ＸＰ，仿真结果基于ＭＡＴＬＡＢ　Ｒ２００９ｂ实现的。　为了更加合理的测试我们的算法，我们所运用的测试数据　是随机产生的。任务的量限制在１０００到１０００００百万条指　令，每个数据中心的计算性能分别设定为｛５００，１０００，　２０００，４０００｝，数据中心之间的带宽设定为１Ｏ０～１０００ＭＢ，　任务间传输数据的大小设为１０００　１００００ＭＢ，任务间数据　传输的密度为ｄ通过式（１５）来表示，其中ｎ为总的任务　数，ｌ　Ｅ　ｌ表示所有的任务之问需要通信的次数，在本测试　中通信密度设定为：０．５。ＰＳＯ的参数设定为：根据参考文　献Ｄ７］把加速系数ｃ２，ｆ１设定为１．４９４４５，惯性权重　设定为０．７２９，这样设置有利于算法的收敛，种群取２Ｏ～　４Ｏ就可以达到很好的求解效果，设定种群为３Ｏ，随机数　ｒａｎｄ１，ｒａｎｄ２均有分布于Ｅｏ－１］之间　一　（１５）　３．２仿真结果与分析　由于ＰＳ０算法是随机的，同样的问题可能产生不同的　结果。为了更好的评测算法，对每个测试实例都运行１Ｏ次　求平均值。我们测试了一系列的数据，这些数据依据亚马　孙按需使用收费方式对３个数据中心进行模拟，仿真结果　见表２，从表２中可以看到，我们的算法不但优化了时间，　而且优化了费用。由于把时间和费用的和设定为适应性函　数，图５为任务分别为３５和１Ｏ时，分配到３个数据中心　时的费用和时间的收敛图，从图５可以看到算法的收敛速　度比较快，且能稳定的收敛。而图３费用的收敛为任务为　１Ｏ，数据中心为３时的费用收敛图，从图３中可以看到，　虽然费用也逐渐收敛，但是有些波动和不稳定，其原因为　我们把时间和费用的和设定为使用性函数，因为ＰＳＯ优化　算法中的每个粒子都趋向于最优的适应值函数，来逐步更　新每一代的速度和位置的，所以费用和时间（图４时间的　收敛）有些波动。　表２按需使用方式的仿真结果　仵备数据童　垡　堕亘　堕　垡　萱重量旦±堕　垡　堕　…　中心　前　后　前　后　前　后　ｌＯ　３　９２２　８７１．８　７６６．７　４２３．５　１５８８．６　１２４０．２　１５　３　１７５８．９　１６８８．６　６２８．８　５２７．１　２３３０．７　２１６Ｏ．５　２Ｏ　３　３５７１．１　３４５７．１　２２３４．５　１３８ｏ．４　５４８４．６　４５６５．２　２５　３　６１５５．１　６０２８．７　２６３０．５　１７１９．３　８４１１．５　７３９４．３　３０　３　８５２４．５　８４１９．３　３２１４．５　２５６８．５　１１２ｏ６　１１０６９２　３５　３　１０７４８　１０６２９　４３６８．７　３６３０．７　１４８０７　１３８４３　任务＝１ｏ与数据中心＝３　算法迭代次数　图３费用的收敛过程　任务＝１ｏ与数据中心＝３　厘　营　图４时间的收敛过程　４结束语　本文探讨了云计算环境下数据部署和任务调度问题，　把云计算环境下数据部署和任务调度问题映射为处理交换　・　２３６２　・　任务＝ＩＯ与数据中心＝３　计算机工程与设计　ｘｌ＆任务＝３５与数据中心＝３　２０１３拄　［２０１２—０９一ｏ３１．ｈｔｔｐ：／／ｉｅｅｅｘｐｌｏｒｅ．ｉｅｅｅ．ｏｒｇ／ｘｐｌ／ｍｏｓｔＲｅｃｅｎｔＩｓ—　ｓｕｅ．ｊｓｐ？ｐｕｎｕｍｂｅｒ＝５４７３８９３．　［７］Ｔｏｒｄｓｓｏｎａ　Ｊ，Ｍｏｎｔｅｒｏｂ　Ｒ　Ｓ，Ｍｏｒｅｎｏ－Ｖｏｚｍｅｄｉａｎｏｂ　Ｒ，ｅｔ　ａ１．　Ｃｌｏｕｄ　ｂｒｏｋｅｒｉｎｇ　ｍｅｃｈａｎｉｓｍｓ　ｆｏｒ　ｏｐｔｉｍｉｚｅ　ｄａｔａ　ｐｌａｃｅｍｅｎｔ　ｏｆ　ｖｉｒ—　ｔｕａｌｍａｃｈｉｎｅｓａｃｒｏｓｓ　ｍｕｌｔｉｐｌｅ　ｐｒｏｖｉｄｅｒｓ［Ｊ］．Ｆｕｔｕｒｅ　Ｇｅｎｅｒａｔｉｏｎ　ｏｍｐｕｔｅｒ　ＳｙｓｔＣｅｍｓ，２０１２，２８（２）：３５８—３６７．　［８］　Ｙｕａｎ　Ｄ，Ｙａｎｇ　Ｙ，Ｌｉｕ　Ｘ　Ａ　ｄａｔａ　ｐｌａｃｅｍｅｎｔ　ｓｔｒａｔｅｇｙ　ｉｎ　ｓｃｉｅｎ　算法迭代次数　算法迭代次数　图５费用时间和收敛过程　图。通过处理交换图建立了多目标优化的数学模型，运用　ｔｉｆｉｃ　ｃｌｏｕｄ　ｗｏｒｋｆｌｏｗｓ［Ｊ］．Ｆｕｔｕｒｅ　Ｇｅｎｅｒａｔｉｏｎ　Ｃｏｍｐｕｔｅｒ　Ｓｙｓ　ｔｅｒｎｓ，２０１０，２６（８）：１２００—１２１４．　［９］ｚｈａｎｇ　Ｌ，Ｃｈｅｎ　Ｙ　Ｈ，Ｓｕｎ　Ｒ　Ｙ，ｅｔ　ａＬ　Ａ　ｔａｓｋ　ｓｃｅｈｄｕｌｉｇ　ａｎｌｇｏ—　ＰＳＯ算法对多目标优化模型进行了优化，并通过仿真对算　法进行了验证。仿真结果显示算法不但优化了处理时间和　传输时间，而且优化了处理费用和传输费用。本文提出的　多目标优化模型能有效的减少用户使用云计算的费用，提　高任务的执行性能；但是对于云计算的服务商来说提高数　据中心的性能，满足用户的服务质量要求，降低数据中心　的能耗，达到绿色计算，对服务商来说是至关重要的，这　是我们下一步要研究的内容。　参考文献：　［１］ＡｒｍｂｒｕｓｔＭ　Ａｂｏｖｅｔｈｅ　ｃｌｏｕｄｓ：Ａｂｅｒｋｅｌｅｙｖｉｅｗｏｆ　ｃｌｏｕｄ　ｃｏｍｐｕｔｉｎｇ　［Ｒ］．Ｔｅｃｈｎｉｃａｌ　Ｒｅｐｏｒｔ．ｈｔｔｐ：／／　ｅｅｃｓ．ｂｅｒｋｅｌｅｙ．ｅｄｕ／Ｐｕｂｓ／　ＴｅｃｈＲｐｔｓ／２００９／ＥＥＣＳ－２００９－２８．ｐｄｆ，２０１１．　［２］ｘｕ　Ｘｉａｏｙｏｎｇ，ＰＡＮ　Ｙｕ，ＬＩＮＧ　Ｃｈｅｍ　Ｐｏｗｅｒ－ａｗａｒｅ　ｒｅｓｏｕｒｃｅ　ｓｃｈｅｄｕｌｉｎｇ　ｕｎｄｅｒ　ｃｌｏｕｄ　ｃｏｍｐｕｔｉｎｇ　ｅｎｖｉｒｏｎｍｅｎｔ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ａｐｐｌｉｃａｔｉｏｎｓ，２０１２，３２（７）：１９１３—１５１５（ｉｎ　Ｃｈｉ—　ｎｅｓｅ）．［徐骁勇，潘郁，凌晨．云计算环境下资源的节能调度　［Ｊ］．计算机应用，２０１２，３２（７）：１９１３—１９１５．］　［３３　ＬＩＵ　Ｗａｎｉｕｎ，ＺＨＡＮＧ　Ｍｅｎｇｈｕａ，ＧＵＯ　Ｗｅｎｙｕｅ．Ｃｌｏｕｄ　ＣＯＩＴＩ—　ｐｕｔｉｎｇ　ｒｅｓｏｕｒｃｅ　ｓｃｈｅｄｕｌｅ　ｓｔｒａｔｅｇｙ　ｂａｓｅｄ　ｏｎ　ＭＰＳＯ　ａｌｇｏｒｉｔｈｍ　［Ｊ］．Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ，２０１１，３７（１１）：４３—４４（ｉｎ　Ｃｈｉ—　ｎｅｓｅ）．［刘万军，张孟华，郭文越．基于ＭＰＳＯ算法的云计算　资源调度策略［Ｊ］．计算机工程，２０１１，３７（１１）：４３—４４．］　［４］ＱＩＡＮ　Ｑｉｏｎｇｆｅｎ，ＬＩ　Ｃｈｕｎｌｉｎ，ＺＨＡＮＧ　Ｘｉａｏｑｉｎｇ．Ｒｅｓｅａｒｃｈ　ｏｎ　ｃｌｏｕｄ　ｅｃｏｎｏｍｉｃ　ｒｅｓｏｕｒｃｅ　ｍａｎａｇｅｍｅｎｔ　ｍｏｄｅｌ　ｗｉｔｈ　ＱｏＳ　ｃｏｎｓｔｒａｉｎｓ　［Ｊ］．Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ，２０１１，２９（ｓ１）：１９５—１９７（ｉｎ　Ｃｈｉ—　ｎｅｓｅ）．［钱琼芬，李春林，张小庆．ＱｏＳ约束的云经济资源管　理模型研究ＬＪ］．计算机科学，２０１１，２９（ｓ１）：１９５—１９７．］　［５］ＺＨＡＮＧ　Ｓｈｕｉｐｉｎｇ，ｗｕ　Ｈａｉｙａｍ　Ｃｌｏｕｄ　ｒｅｓｏｕｒｃｅ　ｓｃｈｅｄｕｌｅ　ｂａｓｅｄ　ｏｎ　ｃｅｌｌｕｌａｒ　ａｕｔｏｍａｔａ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ［Ｊ］．Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ，２０１２，３８（１１）：１１—１３（ｉｎ　Ｃｈｉｎｅｓｅ）．［张水平，　邬海艳．基于元胞自动机遗传算法的云资源调度［Ｊ］．计算机　工程，２０１２，３８（１１）：ｌ１—１３．ｊ　［６］Ｐａｎｄｅｙ　Ｓ，Ｂａｒｋｅｒ　Ａ，Ｇｕｐｔａ　Ｋ　Ｋ，ｅｔ　ａ１．Ｍｉｎｉｍｉｚｉｎｇ　ｅｘｅｃｕｔｉｏｎ　ｃｏｓｔｓ　ｗｈｅｎ　ｕｓｉｎｇ　ｇｌｏｂａｌｌｙ　ｄｉｓｔｒｉｂｕｔｅ　ｄｃｌｏｕｄ　ｓｅｒｖｉｃｅｓ［ＤＢ／ＯＬ］．　ｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ＰＳＯ　ｆｒｏ　ｇｒｉｄ　ｃｏｍｐｕｔｉｎｇ［Ｊ］．Ｉｎｔｅｎｒａｔｉｏｎａｌ　Ｊｏｕｒａｎａｌ　ｏｆ　Ｃｏｍｐｕｔａｔｉｏｎａｌ　Ｉｎｔｅｌｌｉｇｅｎｃｅ　Ｒｅｓｅａｒｃｈ，２００８，４（１）：３７—４３．　［１Ｏ］Ｙｉｎ　Ｐ　Ｙ，ＹＵＳ　Ｓ，Ｗａｎｇ　Ｐ　Ｐ，ｅｔ　ａ１．Ａ　ｈｙｂｒｉｄ　ｐａｒｔｉｃｌｅ　ｓｗａｒｍ　ｏｐｔｉｍｉｚａｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｏｐｔｉｍａｌ　ｔａｓｋ　ａｓｓｉｇｎｍｅｎｔ　ｉｎ　ｄｉｓｔｒｉｂｕ—　ｔｅｄ　ｓｙｓｔｅｍｓ［Ｊ］．Ｃｏｍｐｕｔｅｒ　Ｓｔａｎｄａｒｄｓ　８Ｌ　Ｉｎｔｅｒｆａｃｅｓ，２００６，　２８（４）：４４１－４５０．　［１１］Ｇｕｏ　Ｌ　Ｚ，Ｚｈａｏ　Ｓ　Ｇ，Ｓｈｅｎ　Ｓ　Ｇ，ｅｔ　ａ１．Ｔａｓｋ　ｓｃｈｅｄｕｌｉｎｇ　ｏｐｔｉ—　ｍｉｚａｔｉｏｎ　ｉｎ　ｃｌｏｕｄ　ｃｏｍｐｕｔｉｎｇ　ｂａｓｅｄ　ｏｎ　ｈｅｕｒｉｓｔｉｃ　ａｌｇｏｒｉｔｈｍ　ＬＪ］．　Ｊｏｕｒｎａｌ　ｏｆ　Ｎｅｔｗｏｒｋｓ，２０１２，７（３）：５４７—５５３．　［１２］Ｃｈａｎｇ　Ｃ　Ｋ，Ｊｉａｎｇ　Ｈ，Ｄｉ　Ｙ，ｅｔ　ａ１．Ｔｉｍｅ－ｌｉｎｅ　ｂａｓｅｄ　ｍｏｄｅｌ　ｆｏｒ　ｓｏｆｔｗａｒｅ　ｐｒｏｊｅｃｔ　ｓｃｈｅｄｕｌｉｎｇ　ｗｉｔｈ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍｓ［Ｊ］．Ｉｎ—　ｆｏｒｍａｔｉｏｎ　ａｎｄ　Ｓｏｆｔｗａｒｅ　Ｔｅｃｈｎｏｌｏｇｙ，２００８，５０（１１）：　１１４２—１１５４．　ｒ１３］Ｇｈａｒｏｏｎｉ－ｆａｒｄ　Ｇ，Ｍｏｅｉｎ－ｄａｒｂａｒｉ　Ｆ，Ｄｅｌｄａｆｉ　Ｈ，ｅｔ　ａ１．Ｐｒｏｃｅｄｉａ　ｃｏｍｐｕｔｅｒ　ｓｄｅｎｃｅ，ｓｃｈｅｄｕｌｉｎｇ　ｏｆ　ｃｓｉｅｎｔｉｆｉｃ　ｗｏｒｋ￣ｏｗｓ　ｕｓｉｎｇ　ａ　ｃｈａｏｓ－　ｇｅｎｅｔｉｃ￣ｇｏｉｆｔｈｒｎ［ＤＢ／ＯＬ］．［２０１２～０５—１０］．ｈｔｔｐ：｜ｆ　Ｎ　．ｓｃｉｅ－　ｎｃｅｄｉｒｅｃｔ．ｃｏｍ／ｓｄｅｎｃｅ／ａｒｔｉｃｌｅ／ｐｉｉ／Ｓ１８７７Ｏ５０９１０Ｏ０１６１４．　［１４］Ｓａｌｍａｎ八Ｐａｒｔｉｃｌｅ　ｓｗａｍｒ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｆｏｒ　ｔａｓｋ　ａｓｓｉｇｎｍｅｎｔ　ｐｒｏｂｌｅｍ［Ｊ］．Ｍｉｃｒｏｐｒｏｃｅｓｓｏｒｓ　ａｎｄ　Ｍｉｃｒｏｓｙｓｔｅｍｓ，２００２，２６　（８）：３６３—３７１．　［１５］Ａｍａｚｏｎ　ＥＣ２　Ｐｒｉｃｉｎｇ［ＥＢ／ＯＬ］．［２０１２—０９—０３］．ｈｔｔｐ：／／　ａｗｓ．ａｍａｚｏｎ．ｃｏｒｎ／ｅｃ２／ｐｒｉｃｉｎｇ／．　［１６］Ｋｅｎｎｅｄｙ　Ｊ，Ｅｂｅｒｈａｒｔ　ＲＣ．Ｐａｒｔｉｃｌｅ　ｓｗａｒｍ　ｏｐｔｉｍｉｚａｔｉｏｎ［ＤＢ／　ＯＬ］．［２０１２—０５—１０］．ｈｔｔｐ：／／ｉｅｅｅｘｐｌｏｒｅ．ｉｅｅｅ．ｏｒｇ／ｘｐｌ／ｌｏｇ—　ｉｎ．ｊｓｐ？ｔｐ一￣ａｒｎｕｍｂｅｒ：４８８９６８￣ｕｒｌ—ｈｔｔｐ￣／００　３ＡＺ　２Ｆ　２Ｆｉｅｅｅｘｐｌｏｒｅ．ｉｅｅｅ．ｏｒｇ　２Ｆｘｐｌｓ￣２Ｆａｂｓ—ａｌ１．ｊｓｐ％３Ｆａｒｎｕｍｂｅｒ　％３Ｄ４８８９６８．　［１７］Ｓｈｉ　Ｙ，Ｅｂｅｒｈａｒｔ　Ｒ　Ｃ　Ｅｍｐｉｒｉｃａｌ　ｓｔｕｄｙ　ｏｆ　ｐａｒｔｉｃｌｅ　ｓｗａｒｌｎ　ｏｐｔｉｍｉｚａ—　ｔｉｏｎ［ＤＢ／ＯＬ］．［２０１２—０５—１０］．ｈｔｔｐ：／／ｉｅｅｅｘｐｌｏｒ￣ｉｅｅｅ￣ｏｒｇ／　ｘｐｌ／ｌｏｇｉｒＬｊｓｐ？ｔｐ＝￣ａｒｎｕｍｂｅｒ＝７８５５１１￣ｕｒ１＝ｈｔｔｐ￣３ＡＺ２Ｆ　２Ｆｉｅｅｅｘｐｌｏｍ　ｉｅｅｅ．ｏｒｇ　２Ｆｘｐｌｓ％２Ｆａｂｓａｌ１．ｊｓｐ％０　３Ｆａｍｕｍｂｅｒ　％３１３７８５５１１．　［１８］Ｔａｓｇｅｔｉｒｅｎ　Ｍ　Ｆ，Ｌｉａｎｇ　Ｙ　Ｃ，Ｓｅｖｋｌｉ　Ｍ，ｅｔ　ａ１．Ｐａｒｔｉｃｌｅ　ｓｗａｒｍ　ｏｐｔｉｍｉｚａｔｉｏｎ　ａｎｄ　ｄｉｆｆｅｒｅｎｔｉａｌ　ｅｖｏｌｕｔｉｏｎ　ｆｏｒ　ｓｉｎｇｌｅ　ｍａｃｈｉｎｅ　ｔｏｔａｌ　ｗｅｉｇｈｔｅｄ　ｔａｒｄｉｎｅｓｓ　ｐｒｏｂｌｅｍ口］．Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｊｏｕｒｎａｌ　ｏｆ　Ｐｒｏ—　ｄｕｃｔｉｏｎ　Ｒｅｓｅａｒｃｈ，２００６。４４（２２）：４７３７—４７５４．