周偉強, 湯春香, 王麗娟

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

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

周偉強1, 湯春香2, 王麗娟1

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

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

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

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

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

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

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

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

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

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

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

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

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

當(dāng)S是不可聚類單主屬性網(wǎng)格資源集時，對S中的資源按照主屬性A的大小組成一個資源分類樹(RCT)，S的主屬性的值域為R=[L，H]，L，H分別為R的下界和上界，Ri=[Li，Hi]，Rj=[Lj，Hj]為R的2個子區(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個互不相交的子區(qū)間Ri(i=1…n)，每個區(qū)間的節(jié)點數(shù)大致相同，且Ri由節(jié)點Ni進(jìn)行管理，將Ni按照Ri的大小組織為一個平衡的二叉樹(AVL樹)，稱該平衡二叉樹為資源分類樹，如圖4所示.Ni為從Ri中選出的計算能力和存儲能力較強的節(jié)點，稱Ni為Ri上的管理節(jié)點HR.對于任意一個網(wǎng)格資源Si，若Si的主屬性A的取值為V，V在Ni所管理的區(qū)間上，則將網(wǎng)格資源Si注冊到Ni所管理的區(qū)間上.每個普通網(wǎng)格資源僅需要維護(hù)好其自身與所在的區(qū)間HR的連接，而每個資源分類樹的節(jié)點HR除需要維護(hù)好注冊到其自身上的網(wǎng)格資源節(jié)點的連接外，還需要維護(hù)好其自身與資源分類樹的父節(jié)點和直接子節(jié)點的聯(lián)系，以及父節(jié)點和直接子節(jié)點所管理的區(qū)間.

當(dāng)S是可聚類單主屬性網(wǎng)格資源集時，首先對S中的網(wǎng)格資源根據(jù)主屬性A的大小進(jìn)行聚類，聚類完成之后，將R劃分為n個互不相交的子區(qū)間Ri(i=1…n)，其中每個聚類就是一個子區(qū)間，其余每個子區(qū)間的節(jié)點數(shù)大致相同，從每個子區(qū)間選取一個節(jié)點Ni管理其所在子區(qū)間，根據(jù)區(qū)間大小將Ni組織成一個資源分類樹，Ni也是從Ri中選出的計算能力和存儲能力較強的節(jié)點，如圖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負(fù)責(zé)管理本區(qū)間內(nèi)的所有網(wǎng)格資源的加入、退出和轉(zhuǎn)移，因此，必須確保HR具有很強的網(wǎng)格資源管理功能和可用性.通過計算能力來衡量HR對網(wǎng)格資源的能力，當(dāng)HR擁有較強計算能力時就降低了HR由于負(fù)載過高而引起的性能瓶頸風(fēng)險，并能更好完成HR作為網(wǎng)格資源的任務(wù).用Ton/Tall來衡量網(wǎng)格資源的可用性，Ton表示網(wǎng)格資源的平均在線時長，Tall表示網(wǎng)格資源平均在線時長和平均離線時長的總和.

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

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

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

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

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

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

2.3計算資源的動態(tài)性維護(hù)

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

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

2.4容錯機制

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

3 性能模擬與測試

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

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

4 結(jié)語

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

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

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

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

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

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

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

[11] 牛 琨,張舒博,陳俊亮.采用屬性聚類的高維子空間聚類算法[J].北京郵電大學(xué)學(xué)報, 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)項目(121PPTGG465)

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

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

1000-2340(2014)05-0658-05