周偉強(qiáng), 湯春香, 王麗娟

(1.河南農(nóng)業(yè)大學(xué)信息與管理科學(xué)學(xué)院，河南 鄭州 450002； 2.河南牧業(yè)經(jīng)濟(jì)學(xué)院，河南 鄭州 450002)

基于主屬性網(wǎng)格資源分類組織模式

周偉強(qiáng)1, 湯春香2, 王麗娟1

(1.河南農(nóng)業(yè)大學(xué)信息與管理科學(xué)學(xué)院，河南 鄭州 450002； 2.河南牧業(yè)經(jīng)濟(jì)學(xué)院，河南 鄭州 450002)

在深入研究已有的網(wǎng)格資源組織方式的基礎(chǔ)上，通過(guò)引入主屬性的概念，提出了基于主屬性網(wǎng)格資源分類樹(Resource Category Tree，RCT)的組織模式，并對(duì)基于主屬性RCT的初始化、自主演化、動(dòng)態(tài)性維護(hù)和容錯(cuò)機(jī)制進(jìn)行了分析和研究.通過(guò)模擬性能測(cè)試，基于主屬性RCT的網(wǎng)格資源組織方式有很高的資源查找能力和容錯(cuò)性.

網(wǎng)格；主屬性；RCT；資源管理

網(wǎng)格計(jì)算興起于20世紀(jì)90年代，從主要研究元計(jì)算和千兆位網(wǎng)，到后來(lái)網(wǎng)格計(jì)算被廣泛用于高能物理、航空航天、故障檢測(cè)、遙感數(shù)據(jù)處理、地震監(jiān)測(cè)、商業(yè)計(jì)算、大型游戲、仿真等領(lǐng)域.短短20多年，美國(guó)、日本、歐洲主要國(guó)家等都啟動(dòng)了大型網(wǎng)格研究項(xiàng)目，并獲得了快速發(fā)展.網(wǎng)格技術(shù)是面向因特網(wǎng)的，被稱為下一代因特網(wǎng).網(wǎng)格計(jì)算的目的是把基于網(wǎng)絡(luò)的跨越多個(gè)自治域的計(jì)算資源、存儲(chǔ)資源、高端儀器設(shè)備、數(shù)據(jù)、軟件、因特網(wǎng)等網(wǎng)格資源組織起來(lái)，實(shí)現(xiàn)這些網(wǎng)格資源的高度共享和資源協(xié)同問(wèn)題求解[1].在網(wǎng)格系統(tǒng)中，網(wǎng)格資源是支撐網(wǎng)格系統(tǒng)和網(wǎng)格運(yùn)行服務(wù)的關(guān)鍵資源.由于網(wǎng)格計(jì)算中，所有的作業(yè)都要分配到網(wǎng)格計(jì)算資源上才能進(jìn)行處理，因此，網(wǎng)格資源的組織和管理直接影響到網(wǎng)格整體的性能.由于網(wǎng)格資源種類、數(shù)量繁多，網(wǎng)格資源的管理和發(fā)現(xiàn)面臨很多挑戰(zhàn)，因此，人們提出了用專門的網(wǎng)格信息服務(wù)(GIS)[2]系統(tǒng)來(lái)解決網(wǎng)格資源的發(fā)現(xiàn)問(wèn)題.目前，較為常見的網(wǎng)格資源發(fā)現(xiàn)是基于Globus MDS[3]的，采用分布式的拓?fù)浣Y(jié)構(gòu)，避免采用集中式的結(jié)構(gòu)，從而減少了單點(diǎn)失效帶來(lái)的損失，出現(xiàn)性能瓶頸的情況大大減少.這些算法都提供了資源搜索算法處理用戶的查詢請(qǐng)求[4～11].這些網(wǎng)格資源管理系統(tǒng)不區(qū)分資源的特點(diǎn)，把資源的元信息隨機(jī)的分配到不同GIS節(jié)點(diǎn)上，當(dāng)用戶對(duì)資源進(jìn)行查找時(shí)就必須對(duì)所有的GIS節(jié)點(diǎn)進(jìn)行遍歷，降低了資源的發(fā)現(xiàn)效率.如果能對(duì)資源按照某些特性進(jìn)行有效的分類組織和管理，就可以快速的縮小資源的搜索范圍，減少資源發(fā)現(xiàn)的代價(jià)，提高資源發(fā)現(xiàn)效率.本研究提出了基于主屬性聚類的網(wǎng)格資源分類樹組織方式，通過(guò)對(duì)網(wǎng)格資源的主屬性各個(gè)分量進(jìn)行聚類后組成網(wǎng)格資源分類樹，可以快速的查找任務(wù)所需要的網(wǎng)格資源，并把任務(wù)分配到資源上進(jìn)行處理，減少了網(wǎng)格任務(wù)分配時(shí)對(duì)網(wǎng)格資源查找的開銷.

1 基于主屬性RCT的網(wǎng)格資源組織

1.1網(wǎng)格資源的主屬性表示法

在網(wǎng)格系統(tǒng)中，通常用基于屬性的方法來(lái)描述網(wǎng)格的資源，這種方法簡(jiǎn)單、有效.本研究通過(guò)<屬性名，屬性值>來(lái)表示網(wǎng)格的資源.當(dāng)一個(gè)網(wǎng)格資源包含多種屬性時(shí)，可以通過(guò)(<屬性名1，屬性值1>、<屬性名2，屬性值2>……)的組合來(lái)表示.由于網(wǎng)格中的資源是動(dòng)態(tài)變化的，因此，人們更關(guān)心的是網(wǎng)格資源的動(dòng)態(tài)屬性.

設(shè)RS是包含N個(gè)網(wǎng)格節(jié)點(diǎn)的n維資源集，A={A1,A2…An}為RS屬性域的集合，稱所有的子集S?A為子空間.本算法首先對(duì)網(wǎng)格資源的所有屬性進(jìn)行處理，找出最能體現(xiàn)網(wǎng)格資源特征和重要性的屬性，并標(biāo)記為網(wǎng)格資源的主屬性.有時(shí)對(duì)網(wǎng)格資源的各個(gè)屬性進(jìn)行處理以后，每個(gè)屬性的重要性基本相同，如果只找出一個(gè)主屬性，那么網(wǎng)格資源其他的屬性的重要性就無(wú)法表現(xiàn)出來(lái)，因此，對(duì)它所有的比較重要的屬性都定義為主屬性，這時(shí)一個(gè)網(wǎng)格資源的主屬性就不止一個(gè)，可能有多個(gè)屬性是網(wǎng)格資源的主屬性.

根據(jù)網(wǎng)格資源主屬性的概念，對(duì)網(wǎng)格資源進(jìn)行分類.主屬性完全相同的網(wǎng)格資源歸為一類.主屬性完全相同是指主屬性的數(shù)量和類別完全相同.

由于網(wǎng)格資源的動(dòng)態(tài)性，網(wǎng)格資源的屬性值由于負(fù)載的不同會(huì)動(dòng)態(tài)的變化，這樣就會(huì)出現(xiàn)網(wǎng)格主屬性的類別和個(gè)數(shù)不穩(wěn)定而快速變化的情況，為了解決這類問(wèn)題，提出了在主屬性之間設(shè)置緩沖區(qū)的概念，避免了網(wǎng)格資源由于動(dòng)態(tài)變化而向多個(gè)網(wǎng)格資源分類樹不停的注冊(cè)和退出的問(wèn)題，如圖1所示.

圖1 主屬性之間關(guān)系Fig.1 The relationship between the main attributes

由圖1可以看到,當(dāng)網(wǎng)格資源的主屬性為A時(shí)，即使網(wǎng)格資源的B屬性值變大到了主屬性A和主屬性為A,B之間的實(shí)線部分，仍然判定資源的主屬性為A；只有當(dāng)B屬性繼續(xù)增大到主屬性為A,B的一側(cè)的虛線部分，才會(huì)判定為主屬性為A,B.同樣當(dāng)主屬性為A，B的網(wǎng)格資源主屬性A的值不斷減小到主屬性B的界限時(shí)，仍然判定資源的主屬性為A,B；只有當(dāng)A屬性繼續(xù)減小到主屬性為B的一側(cè)的虛線部分時(shí)，再判定網(wǎng)格資源的主屬性為B.

1.2網(wǎng)格資源的主屬性組成RCT

當(dāng)S是不可聚類單主屬性網(wǎng)格資源集時(shí)，對(duì)S中的資源按照主屬性A的大小組成一個(gè)資源分類樹(RCT)，S的主屬性的值域?yàn)镽=[L，H]，L，H分別為R的下界和上界，Ri=[Li，Hi]，Rj=[Lj，Hj]為R的2個(gè)子區(qū)間，且Ri∩Rj=φ.如果Hi≤Lj，則定義RiRi.

圖2 網(wǎng)格資源的不可聚類屬性Fig.2 The non-clustering property of grid resources

圖3 網(wǎng)格資源的可聚類屬性Fig.3 The clustering property of grid resource

將R劃分為n個(gè)互不相交的子區(qū)間Ri(i=1…n)，每個(gè)區(qū)間的節(jié)點(diǎn)數(shù)大致相同，且Ri由節(jié)點(diǎn)Ni進(jìn)行管理，將Ni按照Ri的大小組織為一個(gè)平衡的二叉樹(AVL樹)，稱該平衡二叉樹為資源分類樹，如圖4所示.Ni為從Ri中選出的計(jì)算能力和存儲(chǔ)能力較強(qiáng)的節(jié)點(diǎn)，稱Ni為Ri上的管理節(jié)點(diǎn)HR.對(duì)于任意一個(gè)網(wǎng)格資源Si，若Si的主屬性A的取值為V，V在Ni所管理的區(qū)間上，則將網(wǎng)格資源Si注冊(cè)到Ni所管理的區(qū)間上.每個(gè)普通網(wǎng)格資源僅需要維護(hù)好其自身與所在的區(qū)間HR的連接，而每個(gè)資源分類樹的節(jié)點(diǎn)HR除需要維護(hù)好注冊(cè)到其自身上的網(wǎng)格資源節(jié)點(diǎn)的連接外，還需要維護(hù)好其自身與資源分類樹的父節(jié)點(diǎn)和直接子節(jié)點(diǎn)的聯(lián)系，以及父節(jié)點(diǎn)和直接子節(jié)點(diǎn)所管理的區(qū)間.

當(dāng)S是可聚類單主屬性網(wǎng)格資源集時(shí)，首先對(duì)S中的網(wǎng)格資源根據(jù)主屬性A的大小進(jìn)行聚類，聚類完成之后，將R劃分為n個(gè)互不相交的子區(qū)間Ri(i=1…n)，其中每個(gè)聚類就是一個(gè)子區(qū)間，其余每個(gè)子區(qū)間的節(jié)點(diǎn)數(shù)大致相同，從每個(gè)子區(qū)間選取一個(gè)節(jié)點(diǎn)Ni管理其所在子區(qū)間，根據(jù)區(qū)間大小將Ni組織成一個(gè)資源分類樹，Ni也是從Ri中選出的計(jì)算能力和存儲(chǔ)能力較強(qiáng)的節(jié)點(diǎn)，如圖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的自組織機(jī)制

2.1基于主屬性RCT的初始化

RCT包含有若干個(gè)HR，其初始化過(guò)程是生成的每一個(gè)主屬性RCT的第一個(gè)HR的過(guò)程.每個(gè)HR負(fù)責(zé)管理本區(qū)間內(nèi)的所有網(wǎng)格資源的加入、退出和轉(zhuǎn)移，因此，必須確保HR具有很強(qiáng)的網(wǎng)格資源管理功能和可用性.通過(guò)計(jì)算能力來(lái)衡量HR對(duì)網(wǎng)格資源的能力，當(dāng)HR擁有較強(qiáng)計(jì)算能力時(shí)就降低了HR由于負(fù)載過(guò)高而引起的性能瓶頸風(fēng)險(xiǎn)，并能更好完成HR作為網(wǎng)格資源的任務(wù).用Ton/Tall來(lái)衡量網(wǎng)格資源的可用性，Ton表示網(wǎng)格資源的平均在線時(shí)長(zhǎng)，Tall表示網(wǎng)格資源平均在線時(shí)長(zhǎng)和平均離線時(shí)長(zhǎng)的總和.

每一個(gè)VO中都有一個(gè)RCT索引服務(wù)(RIS)，RIS包含有本VO內(nèi)的所有RCT的主屬性和值域信息等多種信息.當(dāng)網(wǎng)格資源R加入網(wǎng)格時(shí)，首先計(jì)算網(wǎng)格資源的主屬性，根據(jù)網(wǎng)格資源R的主屬性向RIS查詢相應(yīng)RCT的配置信息.當(dāng)VO中不存在相應(yīng)主屬性的RCT時(shí)，資源R向RIS提交自身的可用性和處理能力，申請(qǐng)成為HR.RIS存儲(chǔ)網(wǎng)格資源R所提交的相關(guān)信息.當(dāng)VO中存在相應(yīng)主屬性的RCT時(shí)，R通過(guò)GIS找到相應(yīng)的RCT的HR訪問(wèn)入口點(diǎn)，并注冊(cè)到相應(yīng)的RCT上.當(dāng)向RIS提交申請(qǐng)成為一個(gè)主屬性RCT的 HR節(jié)點(diǎn)的網(wǎng)格資源達(dá)到一定數(shù)量時(shí)，RIS將比較這些網(wǎng)格資源的可用性和處理能力，選擇其中一個(gè)最合適的網(wǎng)格節(jié)點(diǎn)成為HR，然后，RIS向其他候選HR發(fā)出通知，候選HR向選定的HR注冊(cè)，至此RCT完成初始化.

2.2負(fù)載感知的自主演化

在RCT初始化之后，RCT只有一個(gè)HR節(jié)點(diǎn)，所有的網(wǎng)格資源都向該HR注冊(cè).隨著加入到本RCT上的網(wǎng)格資源越來(lái)越多，該HR負(fù)責(zé)管理的節(jié)點(diǎn)越來(lái)越多，容易使HR超負(fù)荷負(fù)載而成為RCT的性能瓶頸.因此，RCT必須能夠選出更多的HR來(lái)管理所有的主屬性空間，并把所有的HR節(jié)點(diǎn)組成一顆平衡的RCT.

當(dāng)重載的HR節(jié)點(diǎn)是非聚類節(jié)點(diǎn)時(shí)，則該HR先查詢相鄰區(qū)間的HR的負(fù)載，如果相鄰區(qū)間的HR的負(fù)載沒有達(dá)到警戒值可以接受負(fù)載時(shí)，則重載HR向相鄰區(qū)間轉(zhuǎn)移負(fù)載.如果相鄰區(qū)間的HR達(dá)到警戒值不能接受負(fù)載時(shí)，則重載HR采取分裂的方式減輕負(fù)載.當(dāng)重載HR節(jié)點(diǎn)是聚類節(jié)點(diǎn)時(shí)，則該HR節(jié)點(diǎn)先查詢相鄰區(qū)間是否和本區(qū)間屬于同一個(gè)聚類和能否接受負(fù)載.如果相鄰區(qū)間和本HR所管理的區(qū)間屬于同一個(gè)聚類并且可以接受負(fù)載則向該區(qū)間轉(zhuǎn)移負(fù)載，否則采取分裂的方式減輕負(fù)載.

由于網(wǎng)格系統(tǒng)允許網(wǎng)格資源動(dòng)態(tài)的加入和退出，以及網(wǎng)格資源的動(dòng)態(tài)變化性，有可能會(huì)出現(xiàn)一個(gè)HR節(jié)點(diǎn)上所管理的網(wǎng)格資源大量退出或轉(zhuǎn)移到其他HR上，造成HR負(fù)載較小，增加整個(gè)RCT樹的深度，從而增加搜索長(zhǎng)度.

如果把輕載HR負(fù)責(zé)管理的值域區(qū)間與相鄰HR節(jié)點(diǎn)所管理的區(qū)間合并，可以解決輕載問(wèn)題.當(dāng)一個(gè)HR節(jié)點(diǎn)處于輕載時(shí)，它就會(huì)向相鄰的能接受負(fù)載的同屬于非聚類或者屬于同一個(gè)聚類的區(qū)間HR節(jié)點(diǎn)轉(zhuǎn)移負(fù)載，同時(shí)刪除本節(jié)點(diǎn)HR.否則,不采取任何措施，而是定時(shí)檢查自身負(fù)載和相鄰區(qū)間負(fù)載，以便隨時(shí)轉(zhuǎn)移負(fù)載.

2.3計(jì)算資源的動(dòng)態(tài)性維護(hù)

由于網(wǎng)格系統(tǒng)允許網(wǎng)格資源動(dòng)態(tài)的加入和退出，并且網(wǎng)格資源會(huì)隨著任務(wù)的處理動(dòng)態(tài)的變化，這就需要相應(yīng)的管理機(jī)制.

當(dāng)網(wǎng)格資源加入網(wǎng)格系統(tǒng)之后，它就會(huì)周期性的向HR發(fā)送狀態(tài)信息，當(dāng)網(wǎng)格資源沒有變化時(shí)，狀態(tài)變化信息為空.當(dāng)網(wǎng)格資源的由于變化超過(guò)了本HR所負(fù)責(zé)的區(qū)間時(shí)，本HR就會(huì)將其轉(zhuǎn)移到相應(yīng)的HR進(jìn)行管理.當(dāng)HR長(zhǎng)時(shí)間沒有收到相應(yīng)的更新信息時(shí)，就默認(rèn)網(wǎng)格資源已動(dòng)態(tài)的退出網(wǎng)格系統(tǒng).

2.4容錯(cuò)機(jī)制

在RCT中，每個(gè)HR節(jié)點(diǎn)負(fù)責(zé)管理主屬性值域上一段區(qū)間的網(wǎng)格資源，HR是從其所管理的區(qū)間上選取的處理能力和有效性都比較高的網(wǎng)格節(jié)點(diǎn)，但是仍然無(wú)法保證由于特殊原因?qū)е缕涫У那闆r.針對(duì)這一問(wèn)題，本研究提出了HR節(jié)點(diǎn)備份的容錯(cuò)解決方案，即為RCT的每個(gè)HR節(jié)點(diǎn)在其所管理的區(qū)間上選出一個(gè)備份節(jié)點(diǎn)，保持與HR的同步.當(dāng)HR失效時(shí)，備份節(jié)點(diǎn)就會(huì)成為新的HR節(jié)點(diǎn)，同時(shí)在選取一個(gè)新的備份節(jié)點(diǎn)，提高RCT的容錯(cuò)性.

3 性能模擬與測(cè)試

通過(guò)程序，隨機(jī)生成了15萬(wàn)個(gè)具有6個(gè)主屬性網(wǎng)格資源，并將其組成RCT，每個(gè)HR平均注冊(cè)20個(gè)網(wǎng)格資源的主屬性，通過(guò)客戶端查詢所需的資源，并計(jì)算從查詢到獲得所需資源所經(jīng)歷的網(wǎng)格HR數(shù)，計(jì)算平均搜索長(zhǎng)度，對(duì)查詢時(shí)間進(jìn)行定性分析來(lái)評(píng)估資源的發(fā)現(xiàn)效率.

由和基于跳圖的DPTree比較，結(jié)果如圖6所示.由圖6可以看出，采用基于主屬性RCT的網(wǎng)格資源組織對(duì)網(wǎng)格資源進(jìn)行查找時(shí)經(jīng)歷的HR更少，可以快速找到所需的網(wǎng)格資源，提高網(wǎng)格資源的發(fā)現(xiàn)效率，對(duì)網(wǎng)格資源的管理有一定的研究意義.

4 結(jié)語(yǔ)

作為網(wǎng)格系統(tǒng)的底層資源，網(wǎng)格資源的組織和發(fā)現(xiàn)機(jī)制顯得尤為重要.本研究根據(jù)網(wǎng)格資源的特征和網(wǎng)格系統(tǒng)對(duì)網(wǎng)格資源需求特點(diǎn)進(jìn)行分析，提出了基于主屬性RCT的網(wǎng)格資源組織機(jī)制.與傳統(tǒng)的平衡二叉樹不同，本研究提出的RCT節(jié)點(diǎn)之間是對(duì)等的關(guān)系，可以對(duì)資源從任何一個(gè)網(wǎng)格節(jié)點(diǎn)進(jìn)行搜索.由于結(jié)構(gòu)化的網(wǎng)格資源組織，RCT提高了網(wǎng)格資源的發(fā)現(xiàn)效率，同時(shí)具有較好的自組織機(jī)制.

本研究提出的基于主屬性RCT的網(wǎng)格資源組織為網(wǎng)格系統(tǒng)增加了一種有效的解決方案，在模擬環(huán)境下有快速的資源發(fā)現(xiàn)優(yōu)勢(shì)，但在實(shí)際的網(wǎng)格環(huán)境部署中可能會(huì)遇到其他的各種問(wèn)題，今后將結(jié)合其他的網(wǎng)格資源發(fā)現(xiàn)算法，改進(jìn)基于主屬性RCT網(wǎng)格資源發(fā)現(xiàn)算法.

[1] 萬(wàn) 虎,余明暉,楊 慶,等.基于網(wǎng)格的分布式仿真綜述[J].計(jì)算機(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] 張仙偉,張 璟.基于網(wǎng)格計(jì)算平臺(tái)的并行計(jì)算系統(tǒng)研究與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用,2012,48 (7):5-11.

[5] 房向明,楊壽保,郭磊濤,等.網(wǎng)格計(jì)算系統(tǒng)安全體系結(jié)構(gòu)模型研究[J].計(jì)算機(jī)科學(xué),2004, 31 (7): 63-65.

[6] 王 燕.分布式動(dòng)態(tài)異構(gòu)網(wǎng)格中間件比較研究[J].計(jì)算機(jī)光盤軟件與應(yīng), 2012 (13): 108-109.

[7] 時(shí) 晨,馬秀芳,趙洪鋼.分布式仿真網(wǎng)格技術(shù)簡(jiǎn)析[J].電信快報(bào), 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動(dòng)態(tài)反饋負(fù)載均衡算法[J]. 價(jià)值工程, 2012, 31 (04)：149-152.

[10] 孫海龍,懷進(jìn)鵬,富公為.一種自適應(yīng)的網(wǎng)格計(jì)算資源組織與發(fā)現(xiàn)機(jī)制[J].軟件學(xué)報(bào), 2009, 20 (1):152-163.

[11] 牛 琨,張舒博,陳俊亮.采用屬性聚類的高維子空間聚類算法[J].北京郵電大學(xué)學(xué)報(bào), 2007, 30 (3):1-5.

(責(zé)任編輯：梁保松)

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

鄭州市科技攻關(guān)項(xiàng)目(121PPTGG465)

周偉強(qiáng)，1989年生，男，河南周口人，碩士研究生，主要從事網(wǎng)格方面的研究.

王麗娟，1966年生，女，河南周口人，教授，博士，碩士研究生導(dǎo)師.

1000-2340(2014)05-0658-05