網(wǎng)格資源模糊格模型及其算法研究

摘要:在研究總結(jié)了現(xiàn)有成果的基礎(chǔ)上，首次提出了模糊概念格和模糊概念trie樹(shù)的網(wǎng)格資源管理策略，將形式概念分析理論和網(wǎng)格資源管理技術(shù)進(jìn)行了有機(jī)結(jié)合#65377;給出了網(wǎng)格#65380;資源的形式概念定義，建立了網(wǎng)格資源閾值模糊概念格模型#65377;在閾值模糊概念格模型基礎(chǔ)上，利用形式概念分析方法構(gòu)造了網(wǎng)格資源模糊概念的外延trie樹(shù)和內(nèi)涵trie樹(shù)，并給出了樹(shù)的生成和資源與服務(wù)檢索算法#65377;實(shí)驗(yàn)和應(yīng)用實(shí)例表明，這種資源組織方式是可行的和有效的#65377;

關(guān)鍵詞:網(wǎng)格;形式概念分析;資源模糊格;模糊外延trie樹(shù);模糊內(nèi)涵trie樹(shù)

中圖分類號(hào):TP18文獻(xiàn)標(biāo)志碼:A

文章編號(hào):1001-3695(2007)10-0070-05

自從網(wǎng)格[1]被提出以來(lái)，科學(xué)家和工程技術(shù)專家為了各自領(lǐng)域的需求，按照網(wǎng)格規(guī)范建立了許多資源組織與管理模型[2]，并實(shí)現(xiàn)了一系列網(wǎng)格系統(tǒng)原型(如Globus[3]#65380;Legion[4]#65380;Unicore[5]等)，同時(shí)也出現(xiàn)了一些與網(wǎng)格計(jì)算緊密相關(guān)的理論與技術(shù)(如語(yǔ)義Web[6]#65380;Web服務(wù)[7]等)#65377;網(wǎng)格的動(dòng)態(tài)#65380;分布特性和密集型計(jì)算能力[5]與語(yǔ)義#65380;服務(wù)能力的融合，涌現(xiàn)了許多網(wǎng)格的概念(如語(yǔ)義網(wǎng)格[8]#65380;計(jì)算網(wǎng)格#65380;數(shù)據(jù)網(wǎng)格#65380;信息網(wǎng)格#65380;知識(shí)網(wǎng)格[9]等)和網(wǎng)格提供的服務(wù)概念(如計(jì)算服務(wù)#65380;數(shù)據(jù)服務(wù)#65380;信息服務(wù)#65380;知識(shí)服務(wù)#65380;語(yǔ)義服務(wù)等[10])#65377;

在這些網(wǎng)格的研究與應(yīng)用問(wèn)題中，如何對(duì)各自的資源進(jìn)行組織與管理，是構(gòu)成各種網(wǎng)格#65380;提供單一或多樣服務(wù)的關(guān)鍵問(wèn)題#65377;文獻(xiàn)[2]中從計(jì)算服務(wù)#65380;數(shù)據(jù)服務(wù)角度給出了網(wǎng)格的許多資源管理模型及其特點(diǎn);文獻(xiàn)[11，13]中從信息服務(wù)#65380;知識(shí)服務(wù)角度給出了網(wǎng)格的資源空間模型及其特點(diǎn);文獻(xiàn)[10，14]中從計(jì)算服務(wù)#65380;數(shù)據(jù)服務(wù)#65380;信息服務(wù)#65380;知識(shí)服務(wù)角度給出了資源的語(yǔ)義模型及其特點(diǎn)#65377;

本文從形式概念分析[12]和模糊概念分析理論[19]角度，對(duì)這些網(wǎng)格和網(wǎng)格提供的服務(wù)概念與關(guān)系以及資源管理策略進(jìn)行了分析#65380;歸納#65380;研究，提出了模糊概念格和模糊形式概念trie樹(shù)的網(wǎng)格資源組織與管理方式;并用形式概念分析理論研究了網(wǎng)格資源閾值模糊概念格的構(gòu)造算法#65380;網(wǎng)格資源模糊概念外延trie樹(shù)和內(nèi)涵trie樹(shù)的生成算法#65380;資源與服務(wù)檢索算法#65377;為有效地解決網(wǎng)格資源組織與管理問(wèn)題提供了一個(gè)理論和技術(shù)手段，為進(jìn)一步進(jìn)行網(wǎng)格資源其他相關(guān)問(wèn)題的研究奠定了基礎(chǔ)#65377;

1網(wǎng)格資源閾值模糊格模型

Zadeh[17]和Ganter等人[12]分別提出了模糊集理論和形式概念分析理論;在此基礎(chǔ)上Burusco等人[18]#65380;Belohlavek[19]#65380;Elloumi等人[20]分別提出了結(jié)合模糊集和概念格的模糊概念分析理論，從各自研究領(lǐng)域角度給出了一些模糊格和模糊概念的理論研究和應(yīng)用成果#65377;在網(wǎng)格的研究與應(yīng)用中，根據(jù)需求可將跨組織#65380;異構(gòu)#65380;靜態(tài)#65380;動(dòng)態(tài)#65380;群集#65380;通信#65380;互操作等網(wǎng)格資源的特性作為屬性集元素，各種資源作為對(duì)象集元素#65377;資源具有的某些特性的強(qiáng)度往往是模糊的，并非是確定性的，這樣網(wǎng)格資源的分類既要考慮形式概念問(wèn)題又需考慮模糊特性#65377;下面就從這兩個(gè)角度給出網(wǎng)格#65380;資源#65380;δ閾值模糊概念格等概念的相關(guān)定義#65377;

1.1基本定義

定義1資源是具有三個(gè)屬性集合的對(duì)象，這三個(gè)屬性集分別是資源的標(biāo)記集#65380;資源的信息特征集以及對(duì)資源的操作參數(shù)集#65377;

標(biāo)記可以與資源所處的節(jié)點(diǎn)號(hào)#65380;資源所處的虛擬組織號(hào)，以及使用資源的應(yīng)用序號(hào)關(guān)聯(lián);操作參數(shù)是使用資源的輸入#65380;輸出參數(shù)等;信息特征可以是資源的靜態(tài)#65380;動(dòng)態(tài)信息等#65377;資源可具有計(jì)算能力#65380;數(shù)據(jù)存儲(chǔ)能力#65380;信息服務(wù)能力#65380;知識(shí)服務(wù)能力以及語(yǔ)義服務(wù)能力等#65377;

定義2網(wǎng)格是由不同組織的#65380;異構(gòu)的#65380;地理分布的#65380;動(dòng)態(tài)的各種資源按照一定關(guān)系群集在一起的對(duì)象#65377;這個(gè)群集對(duì)象也具有標(biāo)記#65380;信息特征#65380;操作參數(shù)三個(gè)屬性集#65377;

4結(jié)束語(yǔ)

在研究了相關(guān)的網(wǎng)格模型和應(yīng)用原型的基礎(chǔ)上，提出了網(wǎng)格資源δ閾值模糊格和模糊概念trie樹(shù)的資源組織與管理模型，將模糊形式概念分析理論與網(wǎng)格資源管理技術(shù)進(jìn)行了有機(jī)結(jié)合;給出了網(wǎng)格#65380;資源δ#65380;閾值模糊Galois連接的定義，建立了網(wǎng)格資源δ閾值模糊格模型#65377;在分析了trie樹(shù)這種數(shù)據(jù)結(jié)構(gòu)特點(diǎn)的基礎(chǔ)上，利用形式概念分析方法構(gòu)造了網(wǎng)格資源模糊概念的外延trie樹(shù)和內(nèi)涵trie樹(shù)，并給出了樹(shù)的生成和檢索算法#65377;實(shí)驗(yàn)和實(shí)例表明:資源和服務(wù)檢索算法是有效的，資源組織與管理策略是可行的，這項(xiàng)有意義的工作為下一步研究奠定了基礎(chǔ)#65377;進(jìn)一步的工作是對(duì)資源閾值模糊格的更新算法#65380;trie樹(shù)的壓縮算法#65380;基于資源閾值模糊格和trie樹(shù)的網(wǎng)格資源管理與調(diào)度系統(tǒng)等進(jìn)行研究#65377;上述討論表明，本文提出的方法不局限于計(jì)算網(wǎng)格#65380;服務(wù)網(wǎng)格#65380;語(yǔ)義網(wǎng)格等，對(duì)各種網(wǎng)格的研究與應(yīng)用都有借鑒之處#65377;

參考文獻(xiàn):

[1]FOSTER I，KESSELMAN C.The grid:blueprint for a new computing infrastructure[M].San Francisco:Morgan Kaufman Publishers，1998.

[2]KRAUTER K，BUYYA R，MAHESWARAN M.A taxonomy and survey of grid resource management systems for distributed computing[J].Software Practice Expercence，2002，32(2):135164.

[3]Globus[EB/OL].http://www.globus.org.

[4]CHAPIN S J，KATRAMATOS D，KARPOVICH J，et al.Resource management in Legion[J].Future Generation Computer Systems，1999，15(5/6):583-594.

[5]Unicore[EB/OL].http://www.unicore.de/.

[6]HENDLER J.Agents and the semantic Web[J].IEEE Intelligent Systems，2001，16(2):30-37.

[7]SARMENTA L F G.Bayanihan computing net:grid computing with XML Web services[C]//Proc of the 2nd IEEE/ACM Int’l Conf on Cluster Computing and the Grid.Berlin:IEEE Computer Society Press，2002.

[8]Semantic grid[EB/OL].http://www.semanticgrid.org.

[9]ZHUGE Hai.Semantics，resource and grid[J].Future Generation Computer Systems，2004，20(1):1-5.

[10]LI Maozhen，SANTEN P van，WALKER D W.SGrid:a serviceoriented model for the semantic grid[J].Future Generation Computer Systems，2004，20(1):718.

[11]ZHUGE Hai.Resource space model，its design method and applications[J].Journal of Systems Software，2004，72(1):71-81.

[12]GANTER B，WILLER R.Formal concept analysis:mathematical foundations[M].Berlin:SpringerVerlag，1999.

[13]ZHUGE Hai.A knowledge grid model and platform for global knowledge sharing[J].Expert Syst Appl，2002，22(4):313-320.

[14]ZHUGE Hai.Clustering softdevices in semantic grid[J].IEEE Computational Science Engineering，2002，4(6):60-62.

[15]GODIN R，MISSAOUI K，ALAOUI H.Incremental concept formation algorithms based on Galois(concept) lattices[J].Computational Intelligence，1995，11(2):246-267.

[16]KUZNETSOV S，OBIEDKOV S.Comparing performance of algorithms for generating concept lattices[J].Journal of Experimental and Theoretical Artificial Intelligence，2002，14(23):189-216. 

[17]ZADEH L A.Fuzzy sets[J].Information and Control Journal，1965，8(3):338-353.

[18]BURUSCO A，F(xiàn)UENTES R.The study of Lfuzzy concept lattices[J].Mathware Soft Computing，1994，1(3):209-218.

[19]BELOHLAVEK R.Fuzzy Galois connections[J].Math Logic Quarterly，1999，45(4):497-504.

[20]ELLOUMI S，JAOUA A.Automatic classification using fuzzy concepts[C]//Proc of the JCIS2000.Atlantic City:[s.n.]，2000:276-279.

[21]FREDKIN E.Trie memory[J].Communication ofACM，1960，3(9):490-500.

[22]KNUTH D.The art of computer programming[M].New York:AddisonWesley，1973: 481-505.

[23]STANDISH T.Data structure techniques[M].New York:AddisonWesley，1980. 

[24]AOE J.A compact representation of hierarchical relations using decimal notations[J].Int J Computer Math，1990，33(1): 37-54. 

[25]DUNDAS J.Implementing dynamic minimal prefix tries[J].Software Practice Expercence，1991，21(10):10271040.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”