基于主属性网格资源分类组织模式

周伟强, 汤春香, 王丽娟

(1.河南农业大学信息与管理科学学院，河南 郑州 450002； 2.河南牧业经济学院，河南 郑州 450002)

基于主属性网格资源分类组织模式

周伟强1, 汤春香2, 王丽娟1

(1.河南农业大学信息与管理科学学院，河南 郑州 450002； 2.河南牧业经济学院，河南 郑州 450002)

在深入研究已有的网格资源组织方式的基础上，通过引入主属性的概念，提出了基于主属性网格资源分类树(Resource Category Tree，RCT)的组织模式，并对基于主属性RCT的初始化、自主演化、动态性维护和容错机制进行了分析和研究.通过模拟性能测试，基于主属性RCT的网格资源组织方式有很高的资源查找能力和容错性.

网格；主属性；RCT；资源管理

网格计算兴起于20世纪90年代，从主要研究元计算和千兆位网，到后来网格计算被广泛用于高能物理、航空航天、故障检测、遥感数据处理、地震监测、商业计算、大型游戏、仿真等领域.短短20多年，美国、日本、欧洲主要国家等都启动了大型网格研究项目，并获得了快速发展.网格技术是面向因特网的，被称为下一代因特网.网格计算的目的是把基于网络的跨越多个自治域的计算资源、存储资源、高端仪器设备、数据、软件、因特网等网格资源组织起来，实现这些网格资源的高度共享和资源协同问题求解[1].在网格系统中，网格资源是支撑网格系统和网格运行服务的关键资源.由于网格计算中，所有的作业都要分配到网格计算资源上才能进行处理，因此，网格资源的组织和管理直接影响到网格整体的性能.由于网格资源种类、数量繁多，网格资源的管理和发现面临很多挑战，因此，人们提出了用专门的网格信息服务(GIS)[2]系统来解决网格资源的发现问题.目前，较为常见的网格资源发现是基于Globus MDS[3]的，采用分布式的拓扑结构，避免采用集中式的结构，从而减少了单点失效带来的损失，出现性能瓶颈的情况大大减少.这些算法都提供了资源搜索算法处理用户的查询请求[4～11].这些网格资源管理系统不区分资源的特点，把资源的元信息随机的分配到不同GIS节点上，当用户对资源进行查找时就必须对所有的GIS节点进行遍历，降低了资源的发现效率.如果能对资源按照某些特性进行有效的分类组织和管理，就可以快速的缩小资源的搜索范围，减少资源发现的代价，提高资源发现效率.本研究提出了基于主属性聚类的网格资源分类树组织方式，通过对网格资源的主属性各个分量进行聚类后组成网格资源分类树，可以快速的查找任务所需要的网格资源，并把任务分配到资源上进行处理，减少了网格任务分配时对网格资源查找的开销.

1 基于主属性RCT的网格资源组织

1.1网格资源的主属性表示法

在网格系统中，通常用基于属性的方法来描述网格的资源，这种方法简单、有效.本研究通过<属性名，属性值>来表示网格的资源.当一个网格资源包含多种属性时，可以通过(<属性名1，属性值1>、<属性名2，属性值2>……)的组合来表示.由于网格中的资源是动态变化的，因此，人们更关心的是网格资源的动态属性.

设RS是包含N个网格节点的n维资源集，A={A1,A2…An}为RS属性域的集合，称所有的子集S⊂A为子空间.本算法首先对网格资源的所有属性进行处理，找出最能体现网格资源特征和重要性的属性，并标记为网格资源的主属性.有时对网格资源的各个属性进行处理以后，每个属性的重要性基本相同，如果只找出一个主属性，那么网格资源其他的属性的重要性就无法表现出来，因此，对它所有的比较重要的属性都定义为主属性，这时一个网格资源的主属性就不止一个，可能有多个属性是网格资源的主属性.

根据网格资源主属性的概念，对网格资源进行分类.主属性完全相同的网格资源归为一类.主属性完全相同是指主属性的数量和类别完全相同.

由于网格资源的动态性，网格资源的属性值由于负载的不同会动态的变化，这样就会出现网格主属性的类别和个数不稳定而快速变化的情况，为了解决这类问题，提出了在主属性之间设置缓冲区的概念，避免了网格资源由于动态变化而向多个网格资源分类树不停的注册和退出的问题，如图1所示.

图1 主属性之间关系Fig.1 The relationship between the main attributes

由图1可以看到,当网格资源的主属性为A时，即使网格资源的B属性值变大到了主属性A和主属性为A,B之间的实线部分，仍然判定资源的主属性为A；只有当B属性继续增大到主属性为A,B的一侧的虚线部分，才会判定为主属性为A,B.同样当主属性为A，B的网格资源主属性A的值不断减小到主属性B的界限时，仍然判定资源的主属性为A,B；只有当A属性继续减小到主属性为B的一侧的虚线部分时，再判定网格资源的主属性为B.

1.2网格资源的主属性组成RCT

当S是不可聚类单主属性网格资源集时，对S中的资源按照主属性A的大小组成一个资源分类树(RCT)，S的主属性的值域为R=[L，H]，L，H分别为R的下界和上界，Ri=[Li，Hi]，Rj=[Lj，Hj]为R的2个子区间，且Ri∩Rj=φ.如果Hi≤Lj，则定义RiRi.

图2 网格资源的不可聚类属性Fig.2 The non-clustering property of grid resources

图3 网格资源的可聚类属性Fig.3 The clustering property of grid resource

将R划分为n个互不相交的子区间Ri(i=1…n)，每个区间的节点数大致相同，且Ri由节点Ni进行管理，将Ni按照Ri的大小组织为一个平衡的二叉树(AVL树)，称该平衡二叉树为资源分类树，如图4所示.Ni为从Ri中选出的计算能力和存储能力较强的节点，称Ni为Ri上的管理节点HR.对于任意一个网格资源Si，若Si的主属性A的取值为V，V在Ni所管理的区间上，则将网格资源Si注册到Ni所管理的区间上.每个普通网格资源仅需要维护好其自身与所在的区间HR的连接，而每个资源分类树的节点HR除需要维护好注册到其自身上的网格资源节点的连接外，还需要维护好其自身与资源分类树的父节点和直接子节点的联系，以及父节点和直接子节点所管理的区间.

当S是可聚类单主属性网格资源集时，首先对S中的网格资源根据主属性A的大小进行聚类，聚类完成之后，将R划分为n个互不相交的子区间Ri(i=1…n)，其中每个聚类就是一个子区间，其余每个子区间的节点数大致相同，从每个子区间选取一个节点Ni管理其所在子区间，根据区间大小将Ni组织成一个资源分类树，Ni也是从Ri中选出的计算能力和存储能力较强的节点，如图5所示.

图4 不可聚类属性组成的RCTFig.4 The RCT of grid resources whoseproperty can not cluster

图5 可聚类属性组成的RCTFig.5 The RCT of grid resources whoseproperty can cluster

2 基于主属性RCT的自组织机制

2.1基于主属性RCT的初始化

RCT包含有若干个HR，其初始化过程是生成的每一个主属性RCT的第一个HR的过程.每个HR负责管理本区间内的所有网格资源的加入、退出和转移，因此，必须确保HR具有很强的网格资源管理功能和可用性.通过计算能力来衡量HR对网格资源的能力，当HR拥有较强计算能力时就降低了HR由于负载过高而引起的性能瓶颈风险，并能更好完成HR作为网格资源的任务.用Ton/Tall来衡量网格资源的可用性，Ton表示网格资源的平均在线时长，Tall表示网格资源平均在线时长和平均离线时长的总和.

每一个VO中都有一个RCT索引服务(RIS)，RIS包含有本VO内的所有RCT的主属性和值域信息等多种信息.当网格资源R加入网格时，首先计算网格资源的主属性，根据网格资源R的主属性向RIS查询相应RCT的配置信息.当VO中不存在相应主属性的RCT时，资源R向RIS提交自身的可用性和处理能力，申请成为HR.RIS存储网格资源R所提交的相关信息.当VO中存在相应主属性的RCT时，R通过GIS找到相应的RCT的HR访问入口点，并注册到相应的RCT上.当向RIS提交申请成为一个主属性RCT的 HR节点的网格资源达到一定数量时，RIS将比较这些网格资源的可用性和处理能力，选择其中一个最合适的网格节点成为HR，然后，RIS向其他候选HR发出通知，候选HR向选定的HR注册，至此RCT完成初始化.

2.2负载感知的自主演化

在RCT初始化之后，RCT只有一个HR节点，所有的网格资源都向该HR注册.随着加入到本RCT上的网格资源越来越多，该HR负责管理的节点越来越多，容易使HR超负荷负载而成为RCT的性能瓶颈.因此，RCT必须能够选出更多的HR来管理所有的主属性空间，并把所有的HR节点组成一颗平衡的RCT.

当重载的HR节点是非聚类节点时，则该HR先查询相邻区间的HR的负载，如果相邻区间的HR的负载没有达到警戒值可以接受负载时，则重载HR向相邻区间转移负载.如果相邻区间的HR达到警戒值不能接受负载时，则重载HR采取分裂的方式减轻负载.当重载HR节点是聚类节点时，则该HR节点先查询相邻区间是否和本区间属于同一个聚类和能否接受负载.如果相邻区间和本HR所管理的区间属于同一个聚类并且可以接受负载则向该区间转移负载，否则采取分裂的方式减轻负载.

由于网格系统允许网格资源动态的加入和退出，以及网格资源的动态变化性，有可能会出现一个HR节点上所管理的网格资源大量退出或转移到其他HR上，造成HR负载较小，增加整个RCT树的深度，从而增加搜索长度.

如果把轻载HR负责管理的值域区间与相邻HR节点所管理的区间合并，可以解决轻载问题.当一个HR节点处于轻载时，它就会向相邻的能接受负载的同属于非聚类或者属于同一个聚类的区间HR节点转移负载，同时删除本节点HR.否则,不采取任何措施，而是定时检查自身负载和相邻区间负载，以便随时转移负载.

2.3计算资源的动态性维护

由于网格系统允许网格资源动态的加入和退出，并且网格资源会随着任务的处理动态的变化，这就需要相应的管理机制.

当网格资源加入网格系统之后，它就会周期性的向HR发送状态信息，当网格资源没有变化时，状态变化信息为空.当网格资源的由于变化超过了本HR所负责的区间时，本HR就会将其转移到相应的HR进行管理.当HR长时间没有收到相应的更新信息时，就默认网格资源已动态的退出网格系统.

2.4容错机制

在RCT中，每个HR节点负责管理主属性值域上一段区间的网格资源，HR是从其所管理的区间上选取的处理能力和有效性都比较高的网格节点，但是仍然无法保证由于特殊原因导致其失效的情况.针对这一问题，本研究提出了HR节点备份的容错解决方案，即为RCT的每个HR节点在其所管理的区间上选出一个备份节点，保持与HR的同步.当HR失效时，备份节点就会成为新的HR节点，同时在选取一个新的备份节点，提高RCT的容错性.

3 性能模拟与测试

通过程序，随机生成了15万个具有6个主属性网格资源，并将其组成RCT，每个HR平均注册20个网格资源的主属性，通过客户端查询所需的资源，并计算从查询到获得所需资源所经历的网格HR数，计算平均搜索长度，对查询时间进行定性分析来评估资源的发现效率.

由和基于跳图的DPTree比较，结果如图6所示.由图6可以看出，采用基于主属性RCT的网格资源组织对网格资源进行查找时经历的HR更少，可以快速找到所需的网格资源，提高网格资源的发现效率，对网格资源的管理有一定的研究意义.

4 结语

作为网格系统的底层资源，网格资源的组织和发现机制显得尤为重要.本研究根据网格资源的特征和网格系统对网格资源需求特点进行分析，提出了基于主属性RCT的网格资源组织机制.与传统的平衡二叉树不同，本研究提出的RCT节点之间是对等的关系，可以对资源从任何一个网格节点进行搜索.由于结构化的网格资源组织，RCT提高了网格资源的发现效率，同时具有较好的自组织机制.

本研究提出的基于主属性RCT的网格资源组织为网格系统增加了一种有效的解决方案，在模拟环境下有快速的资源发现优势，但在实际的网格环境部署中可能会遇到其他的各种问题，今后将结合其他的网格资源发现算法，改进基于主属性RCT网格资源发现算法.

[1] 万 虎,余明晖,杨 庆,等.基于网格的分布式仿真综述[J].计算机仿真,2008, 25 (1): 6-10.

[2] PLALE B, P DINDA, GVLASZEWSKI. Key concepts and services of a Grid information service[J].Proceedings of the 15th International Conference on Parallel and Distributed Computing Systems ,2002(3)：437-442.

[3] RANGANATHAN K, I FOSTER. Simulation studies of computation and data scheduling algorithms for data grids[J]. Journal of Grid Computing, 2003, 52(1)：53-62.

[4] 张仙伟,张 璟.基于网格计算平台的并行计算系统研究与实现[J].计算机工程与应用,2012,48 (7):5-11.

[5] 房向明,杨寿保,郭磊涛,等.网格计算系统安全体系结构模型研究[J].计算机科学,2004, 31 (7): 63-65.

[6] 王 燕.分布式动态异构网格中间件比较研究[J].计算机光盘软件与应, 2012 (13): 108-109.

[7] 时 晨,马秀芳,赵洪钢.分布式仿真网格技术简析[J].电信快报, 2013 (2)：26-28.

[8] EPEMA D, A IOSUP. Grid computing workloads[J].IEEE Transactions on Internet Computng,2011, 15(2): 19-26.

[9] 李 宁,陈 丙. 一种INSS动态反馈负载均衡算法[J]. 价值工程, 2012, 31 (04)：149-152.

[10] 孙海龙,怀进鹏,富公为.一种自适应的网格计算资源组织与发现机制[J].软件学报, 2009, 20 (1):152-163.

[11] 牛 琨,张舒博,陈俊亮.采用属性聚类的高维子空间聚类算法[J].北京邮电大学学报, 2007, 30 (3):1-5.

(责任编辑：梁保松)

Theorganizationmodeofgridresourcesbasedonthemainattributes

ZHOU Wei-qiang1, TANG Chun-xiang2, WANG Li-juan1

(1.College of Information and Management Science, Henan Agricultural University, Zhengzhou 450002,China; 2.Henan University of Animal Husbandry and Economy,Zhengzhou 450002,China)

Based on in-depth study of the existing grid resource organization and by introducing the concept of the main attributes to propose the organization of the Resource Category Tree of the main attributes. We also have analyzed and studied the initialization, self-evolution dynamic maintenance and fault tolerance mechanisms of the main attributes RCT. Through the simulating and performance tests, we find that the organization of grid resources based on the main attributes RCT has a high ability to find resources and fault tolerance.

grid; main attributes;RCT; resource management

TP 393

：A

2014-05-23

郑州市科技攻关项目(121PPTGG465)

周伟强，1989年生，男，河南周口人，硕士研究生，主要从事网格方面的研究.

王丽娟，1966年生，女，河南周口人，教授，博士，硕士研究生导师.

1000-2340(2014)05-0658-05