动态网格计算的理论与算法研究

２００７年１月　第３１卷第１期　安徽大学学报（自然科学版）　Ｊｏｕｒｎａｌ　ｏｆ　Ａｎｈｕｉ　Ｕｎｉｖｅｒｓｉｔｙ　Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｅｄｉｔｉｏｎ　Ｊａｎｕａｒｙ　２００７　Ｖｏｌ｜３１　Ｎｏ．１　

一种基于密度的网格动态聚类算法的研究　

焦誉　，赖建章　，柯佳　

（１．安徽行政学院信息管理系，安徽合肥２３００５９；　２．合肥工业大学管理学院，安徽合肥２３０００９；３．安徽中医学院计算机系，安徽合肥２３００３７）　

摘要：聚类算法是数据挖掘领域中一个非常重要的研究方向．至今为止人们已经提出了许多适　用于大规模的、高维的数据库的聚类算法．基于密度的聚类算法是其中一个比较典型的研究方向，文中　以ＤＢＳＣＡＮ为基础，提出一种基于密度的网格动态聚类算法．新算法将网格的原理运用到基于密度的聚　类算法中，并采用了动态的参数法，能自动根据数据的分布情况进行必要的参数更改，有效减少ＤＢＳＣＡＮ　对初始参数的敏感度，从而提高了聚类的效率和效果，降低了算法Ｉ／Ｏ的开销．算法不仅能挖掘出各种　形状的聚类，并能准确的挖掘出数据集中突出的聚类．　关键词：聚类算法；密度；网格；动态　中图分类号：ＴＰ１８　文献标识码：Ａ　文章编号：１０００—２１６２（２００７）０１—００３１—０４　

近１０多年来，数据挖掘逐渐成为数据库研究领域的一个热点¨　，其中，聚类分析就是数据挖掘领域　

广为研究的问题之一．所谓聚类，就是将数据库中的数据进行分组，使得每一组内的数据尽可能相似而　不同组内的数据尽可能不同．聚类技术在统计数据分析、模式识别、图像处理等领域都有广泛应用前景．　

迄今为止，人们已经提出了许多聚类算法　Ｉ４　．而当今的研究领域有关聚类的算法大体可以归结为以下　几种情况：分割法、层次法、基于密度法、基于网格法和基于模型法等，所有这些算法都试图解决大规模　

或高维数据的聚类问题．　

１　相关研究　

基于网格的聚类算法由于易于增量实现和高维数据挖掘而被广泛应用于聚类算法当中，迄今为止，　

２００７年５月　第２２卷第３期　西安石油大学学报（自然科学版）　Ｊｏｕｒｎａｌ　ｏｆ　Ｘｉ　ａｎ　Ｓｈｉｙｏｕ　Ｕｎｉｖｅｒｓｉｔｙ（Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｅｄｉｔｉｏｎ）　Ｍａｙ　２００７　Ｖｌ０１．２２Ｎｏ．３　

文章编号：１６７３—０６４Ｘ（２００７）０３—０１１５—０４　

基于服务网格的动态负载平衡调度算法研究　

Ｒｅｓｅａｒｃｈ　ａｎｄ　ｉｍｐｌｅｍｅｎｔａｔｉｏｎ　ｏｆ　ｔｈｅ　ｄｙｎａｍｉｃ　ｌｏａｄ　ｂａ￣ｎｃｉｎｇ　ａ￣ｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ｓｅｒｖｉｃｅ　

任长林　，王家华２　

（１．西安石油大学信息中心，陕西西安７１００６５；２．西安石油大学计算机学院，陕西西安７１００６５）　

摘要：为了提高资源利用率和系统的吞吐率，需要实现服务网格系统内负载的均衡分布．提出了层　

次式动态负载平衡调度模式，详细介绍了负载平衡系统的系统结构．作业分配是负载平衡系统中的　

核心机制．设计并实现了一种综合考虑各局部代理作业数和各个局部代理性能以及当前负载情况　的动态双阀值作业分配算法．试验数据表明，该作业分配算法较传统调度算法综合性能有较大提　

高．在作业数较多时，该作业分配算法性能更好．　关键词：网格；服务网格；Ｗｅｂ服务；动态负载平衡　

中图分类号：ＴＰ３９３　文献标识码：Ａ　

随着高性能应用需求的迅猛发展，单台高性能　计算机已经不能胜任一些超大规模应用问题的解　决．在异地分布的许多空闲资源可以用来进行计算　

处理、数据存储等资源，要利用好这些资源就需要将　异地分布、系统异构的多种计算资源通过高速网络　

连接起来，共同解决大型应用问题，即广域高性能的　元计算技术（Ｍｅｔａ　ｃｏｍｐｕｔｉｎｇ），也称为网格（Ｇｒｉｄ）　技术．　将通用的网格服务与专用的网格服务相整合，　

构建成面向领域的服务网格（Ｓｅｒｖｉｃｅ　Ｇｒｉｄ）．服务网　格系统中，许多业务将通过使用支持网格计算架构　

的网格服务在因特网上进行集成，因此需要协调使　用分布的网格资源，由多个局部代理透明地自动进　

第３２卷　

１１ｏ１．３２　第１１期　

№ｌｌ　计算机工程　

Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　２００６年６月　

ｊｕｎｅ　２００６　

・软件技术与数据库・　文章缠号，１００　＿３４２８ｔ２００６）ｌ１—　ｏ６　＿＿０２　文献标识码ｔ　Ａ　中田分类号。ＴＰ３１　

一个面向服务的网格动态调度算法　

田意民　，赵御　，杨扬　，陈冬娥　．疆正利　

（１，北京科技大学信息学院，北京１０／）／）８３；２．天津大学管理学院，天津３０００７２）　

摘要：随着基于ＯＧＳＡ的网格模型的提出，作业匹配和调度问题显得尤为重要。该文提出了一个面向服务的网格调度框架，引入了随机　

过程理论，给出了匹配和调度的动态算法，从而使网格计算的动态性问题得到了很好的解决。　关翻：网格服务；泊松随机过程；调度；匹配；排队　

Ａ　Ｄｙｎａｍｉｃ　Ｓｃｈｅｄｕｌｉｎｇ　Ａｌｇｏｒｉｔｈｍ　ｆｏｒ　Ｓｅｒｖｉｃｅ－ｏｒｉｅｎｔｅｄ　

Ｇｒｉｄ　Ｃｏｍｐｕｔｉｎｇ　

ＴＩＡＮ　Ｚｈｉｍｉｎ　，ＺＨＡＯ　Ｊｉａｎ　，ＹＡＮＧ　Ｙａｎｇ　，ＣＨＥＮ　Ｄｏｎｇｅ　，ＺＨＡＩ　Ｚｈｅｎｇｌｉ　

（１．Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｃｈｏｏｌ，Ｂｅｉｊｉａｇ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｓｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ，Ｂｅｉｊｉｎｇ　１０００８３；　

２．Ｓｃｈｏｏｌ　ｏｆ　Ｍａｎａｇｅｍｅｎｔ，Ｔｉａｎｊｉｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｔｉａｎｊｉｎ　３０００７２）　

［Ａｂｓｔｒａｃｔｌ　Ｗｉｔｈ　ｔｈｅ　ａｄｖｅｎｔ　ｏｆ　ｇｒｉｄ　ｍｏｄｅｌ　ｂａｓｅｄ　Ｏｎ　ｏｐｅｎ　ｇｒｉｄ　ｓｅｒｖｉｃｅ　ａｒｃｈｉｔｅｃｔｕｒｅ，ｔｈｅ　ｐｒｏｂｌｅｍ　ａｂｏｕｔｊｏｂ　ｍａｔｃｈｉｎｇ　ａｎｄ　ｓｃｈｅｄｕｌｉｎｇ　ｈａｓ　ｉｎｃｒｅａｓｉｎｇｌｙ　

ｂｅｃｏｍｅ　ｉｍｐｏｒｔａｎｔ．Ｔｈｉｓ　ｐａｐｅｒ　ｐｒｏｐｏｓｅｓ　ａ　ｓｅｒｖｉｃｅ—ｏｒｉｅｎｔｅｄ　ｇｒｉｄ　ｓｃｈｅｄｕｌｉｎｇ　ｆｒａｍｅｗｏｒｋ．ｉｎｔｒｏｄｕｃｅｓ　ｓｔｏｃｈａｓｔｉｃ　ｐｒｏｃｅｓｓ　ｔｈｅｏｒｙ，ａｎｄ　ｇｉｖｅｓ　ａ　ｄｙｎａｍｉｃ　ａｌｇｏｒｉｔｈｍ　ａｂｏｕｔ　ｊｏｂ　ｍａｔｃｈｉｎｇ　ａｎｄ　ｓｃｈｅｄｕｌｉｎｇ．Ｔｈｉｓ　ｓｏｌｖｅｓ　ｔｈｅ　ｄｙｎａｍｉｃ　ｐｒｏｂｌｅｍ　ｉｎ　ｇｒｉｄ　ｃｏｍｐｕｔｉｎｇ　ｅｆｆｉｃｉｅｎｔｌｙ．　［Ｋｅｙ　ｗｏｒｄｓ　Ｉ　Ｇｒｉｄ　ｓｅｒｖｉｃｅ；Ｐｏｉｓｓｏｎ　ｓｔｏｃｈａｓｔｉｃ　ｐｒｏｃｅｓｓ；Ｓｃｈｅｄｕｌｉｎｇ；Ｍａｔｃｈｉｎｇ；Ｑｕｅｕｉｎｇ　

第７卷第ｌ２期　２００８年ｌ２月　软件导刊　Ｓｏｆｔｗａｒｅ　Ｇｕｉｄｅ　ＶＯ１．７　ＮＯ．１２　Ｄｅｃ．２０ｏ８　网格计算中任务调度策略研究　许光男　（东西大学校计算机信．ｇ－学院，韩国６１７—７１６）　摘要：首先概述了网格计算中的任务调度算法，然后着重讨论了比较经典的Ｍｉｎ—ｍｉｎ算法：２￣ＱｏＳ　ｇｕｉｄｅｄ　Ｍｉｎ—ｍｉｎ　算法。在此基础上考虑到任务对服务质量要求的差异、对调度算法的影响，提出了一个较为合理的改进算法来有效　地均衡负载、提高系统吞吐量。最后对提出的算法进行了实验仿真，表明改进后的调度算法更加高效。　关键词：网格计算；任务调度；ＱｏＳ；Ｍｉｎ—ｍｉｎ　中图分类号：ＴＰ３９３．０７　文献标识码：Ａ　文章编号：１６７２—７８００（２００８）１２—０１３７—０２　０引言　简单地讲．网格就是把整个因特网整合成一台巨大的超级　计算机。实现计算资源、存储资源、数据资源、信息资源、知识资　源和专家资源的全面共享。这种计算模式是利用互联网将分散　在不同地理位置的计算机组织成一个“虚拟的超级计算机”，其　中每一台参与计算的计算机就是一个“节点”。而整个计算机系　统由成千上万个“节点”组成“一张网格”。所以这种计算模式叫　做网格计算。　在网格系统中，有大量的应用程序要运行．这些应用程序　共享网格的各种资源，如何才能够合理利用这些资源，获得最　大的网格性能是网格环境研究需要解决的主要问题；同时，资　源管理和作业调度是连接网格底层与高层功能的纽带，是协调　整个网格系统有效运转的中枢，是网格的核心技术问题，所以　对这部分网格技术的研究具有重要的意义。　１　网格计算中任务调度策略概述　在网格系统中，任务调度系统是其重要的组成部分，它要　根据任务信息采用适当的策略把不同的任务分配到相应的资　源节点上去运行。由于网格系统的异构性和动态性，以及运行　于网格系统之中的应用程序对于资源的不同需求，使得任务调　度变得极其复杂。不好的任务分配策略。将会增加任务的执行　时间，降低整个网格系统的吞吐量。　网格任务调度通常由３个部分组成，分别是资源发现、资源　匹配和任务执行。其中资源发现部分是在所有可用的资源中找　出满足任务要求的资源；资源匹配部分是从发现的资源中找到　一个最合适的资源分配给任务；任务执行部分是把任务传送到　资源匹配部分找到的资源上去执行。由于网格系统具有动态、　异构、广域的特点，在网格计算系统下，任务调度需要考虑任务　特性、机器特性，为不同任务匹配不同的资源，从而提高系统资　源的利用率和任务的执行效率。由于网格计算中任务调度是一　个ＮＰ完全问题，它引起了众多学者的关注．成为目前网格计算　研究领域的一个焦点。　２　ＱｏＳ　ｇｕｉｄｅｄ　Ｍｉｎ－ｍｉｎ算法分析　服务质量ＱｏＳ（Ｑｕａｌｉｔｙ　ｏｆ　Ｓｅｒｖｉｃｅ）是一个很广泛的概念，对　于不同类型的资源代表不同的含义。根据任务的ＱｏＳ要求的不　同，可以把任务分为两类：高ＱｏＳ的任务和低ＱｏＳ的任务。我们　也可以把主机根据提供的ＱｏＳ的不同划分为两类：高ＱｏＳ主机　和低ＱｏＳ主机。通常高ＱｏＳ的任务只能在高ＱｏＳ的主机上执行，　而低ＱｏＳ的任务则可以在所有的主机上执行。　２．１　ＱｏＳ　ｇｕｉｄｅｄ　Ｍｉｎ—ｍｉｌｌ算法思想　对Ｍｉｎ—ｍｉｎ算法来说，由于在调度时没有考虑任务的ＱｏＳ　要求，这可能会使得低ＱｏＳ任务占用了高ＱｏＳ￣Ｅ机，而高ＱｏＳ任　务只能排在低ＱｏＳ任务后面，等待其完成后才能被执行；与此　同时．有的低ＱｏＳ资源却保持没有任务执行的空闲状态。从而　使得负载不均衡更加严重。这样就造成了资源的浪费。降低了　执行效率。　为了改进Ｍｉｎ—ｍｉｎ算法的调度性能，文献［５］提出了一种考　虑任务ＱｏＳ￣－求的调度算法。在该调度算法中将高ＱｏＳ任务按　照Ｍｉｎ—ｍｉｎ算法先进行调度，然后再将低ＱｏＳ任务按照Ｍｉｎ—ｍｉｎ　算法调度，直到把所有的任务分配完成为止。　２．２　ＱｏＳ　ｇｕｉｄｅｄ　Ｍｉｎ—ｍｉｎ算法与Ｍｉｎ－ｍｉｎ算法的性能比较　表１给出了一个对Ｍｉｎ—ｍｉｎ算法和改进后的ＱｏＳ　ｇｕｉｄｅｄ　Ｍｉｎ—ｍｉｎ算法进行性能分析的ＥＴ矩阵。　作者简介：许光男（１９４４一），男，辽宁沈阳人，博士，东西大学校教授，研究方向为网格计算。