基于本體的網(wǎng)格資源查找和選擇算法研究

摘 要：對現(xiàn)有的計(jì)算網(wǎng)格資源選擇算法作了總體性介紹，并在此基礎(chǔ)上詳細(xì)介紹了三種基于本體的資源查找和選擇算法。最后對各種方法作了分析、比較和總結(jié)。

關(guān)鍵詞：計(jì)算網(wǎng)格； 本體； 資源選擇； 資源匹配

中圖分類號：TP301.6文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695(2007)06-0030-04

0 引言

網(wǎng)格是在異構(gòu)、動態(tài)環(huán)境中實(shí)現(xiàn)資源共享和協(xié)作的技術(shù)［1］。網(wǎng)格中，用戶和資源是跨組織的，資源可能屬于不同的機(jī)構(gòu)，有不同的使用約束，可以動態(tài)地加入或離開，而用戶也會提出對資源的特定需求。計(jì)算網(wǎng)格中的資源選擇問題是指在滿足資源約束的條件下，將符合用戶需求的資源分配給作業(yè)。資源選擇的一般過程［2］（圖1）如下：

①資源管理器把資源的注冊信息寫到資源信息數(shù)據(jù)庫中；

②用戶需要資源時(shí)，向資源管理器提出請求；

③資源管理器從資源信息數(shù)據(jù)庫中獲得匹配資源的信息，返回給用戶，用戶即獲得了資源信息。

圖1 網(wǎng)格資源選擇過程

現(xiàn)有的網(wǎng)格資源選擇算法多是基于屬性、對稱的匹配，即資源提供方和請求方必須在屬性名和值的表示上保持一致；只支持簡單的查詢方式（如關(guān)鍵字和分類查詢）。這大大限制了資源選擇的靈活性，且不易擴(kuò)展。在網(wǎng)格這種異構(gòu)環(huán)境中，作業(yè)請求和資源約束通常在不同的應(yīng)用環(huán)境中定義，使用不同的形式和語法，要實(shí)現(xiàn)資源提供方和請求方在語法及語義上的一致是非常困難的。近年來隨著語義Web的發(fā)展，一些研究人員提出在資源描述和請求中引入本體的概念，以解決網(wǎng)格中資源描述和請求的異構(gòu)問題。

1 網(wǎng)格中現(xiàn)有資源選擇算法

1.1 ClassAd資源匹配［3］

Rajesh Raman等人提出了ClassAd資源匹配模型，用于解決在分布式環(huán)境下資源的選擇和分配問題，已用在Condor［4］的資源管理中。該模型提供的是一種雙向匹配，要求資源請求方指定對資源的要求，同時(shí)資源提供方指定對資源使用的相應(yīng)約束條件。資源提供方和請求方能以任意方式描述各自的條件或需求，但是他們必須采用相同的語法(屬性—值對的形式)。只有當(dāng)資源的提供方與請求方對資源的約束及需求的描述中均使用相同的屬性名以及相匹配的屬性值時(shí)，資源匹配才能進(jìn)行。當(dāng)有多個(gè)資源滿足作業(yè)需求時(shí)，用戶可以定義一個(gè)函數(shù)給資源排序，然后根據(jù)排序結(jié)果選擇最優(yōu)的資源。下面是一個(gè)基于ClassAd資源匹配的例子。資源提供方與請求方使用相同的屬性—值對的形式描述資源需求和使用約束。

1.2 Gang匹配［5］

為了解決ClassAd匹配模型中的二元匹配問題， Raman又提出了Gang匹配，允許資源請求方提出一個(gè)所需求資源的列表。例如，資源請求方可以同時(shí)請求多個(gè)計(jì)算資源，并分別說明對每個(gè)資源的需求。然而Gang匹配并不支持集合匹配模式［6］，如資源請求者可能會請求一個(gè)總內(nèi)存容量大于10 GB的資源集合。對于這樣的請求，Gang匹配就顯得無能為力了。

1.3 基于約束滿足的匹配［7］

Chuang Liu提出了一個(gè)應(yīng)用于網(wǎng)格中的資源選擇系統(tǒng) Redline匹配系統(tǒng)。在該系統(tǒng)中，資源選擇問題首先被轉(zhuǎn)換為約束滿足問題，然后檢查這一系列的約束是否有沖突發(fā)生，最后匹配器用已經(jīng)存在的約束解決機(jī)制來處理轉(zhuǎn)換的約束滿足問題。

與ClassAd相同，Redline匹配系統(tǒng)也是基于資源和需求的對稱描述，即用相同的語法來描述資源和需求。但與ClassAd相比，Redline匹配系統(tǒng)更富有表現(xiàn)力，而且可以支持Gang匹配和集合匹配。

1.4 對比分析

表1是對現(xiàn)有的計(jì)算網(wǎng)格資源選擇算法所作的對比。可以看出，以上所介紹的資源匹配系統(tǒng)，均要求對資源屬性和需求的對稱語法描述，因此在系統(tǒng)應(yīng)用過程中很難向其加入新概念或知識。而且在網(wǎng)格環(huán)境下，資源和用戶大多都是跨越多個(gè)不同的組織或機(jī)構(gòu)，這就很難保證資源描述和用戶請求使用相同的屬性名，表達(dá)相同的語義。隨著語義Web的發(fā)展，一些研究人員提出在資源描述和請求中引入本體，以解決網(wǎng)格中資源描述和請求的異構(gòu)問題。

表1 現(xiàn)有網(wǎng)格資源選擇算法對比

匹配方法需要資源和需求的對稱描述支持同時(shí)請求多個(gè)計(jì)算資源支持集合匹配

不足

ClassAd資源匹配YNN

Gang匹配YYN

基于約束滿足的匹配YYY

均要求對資源屬性和需求的對稱語法描述；在系統(tǒng)應(yīng)用過程中很難向其加入新概念或知識；靈活性和可擴(kuò)展性差

2 基于本體的網(wǎng)格資源選擇方法

基于本體的資源匹配是指在資源描述和用戶請求中引入本體，以解決網(wǎng)格中資源描述和請求的異構(gòu)問題，提高資源查找的靈活性。

2.1 本體概述

本體最早是一個(gè)哲學(xué)上的概念。從哲學(xué)的范疇來說，本體是客觀存在的一個(gè)系統(tǒng)的解釋或說明，關(guān)心的是客觀現(xiàn)實(shí)的抽象本質(zhì)。隨著人工智能的發(fā)展，本體被人工智能界賦予了新的定義。然而最初人們對本體的理解并不完善，對本體的定義也在不斷的發(fā)展變化中。其中最為大家普遍接受的本體定義是：本體是共享概念模型的明確的形式化規(guī)范說明。這個(gè)定義體現(xiàn)了本體的四層含義［8］：

①概念模型（Conceptualization）。

通過抽象出客觀世界中一些現(xiàn)象（Phenomenon）的相關(guān)概念而得到的模型；其表示的含義獨(dú)立于具體的環(huán)境狀態(tài)。

②明確（Explicit）。

所使用的概念及使用這些概念的約束均有明確的定義。

③形式化（Formal）。

本體是計(jì)算機(jī)可讀的。

④共享（Share）。

本體中體現(xiàn)的是共同認(rèn)可的知識，反映的是相關(guān)領(lǐng)域中公認(rèn)的概念集，它所針對的是團(tuán)體而不是個(gè)體。

領(lǐng)域本體用于表達(dá)領(lǐng)域相關(guān)的知識，提供對該領(lǐng)域知識的共同理解，確定該領(lǐng)域內(nèi)共同認(rèn)可的詞匯，并從不同層次的形式化模式上給出這些詞匯（術(shù)語）和詞匯之間相互關(guān)系的明確定義。

2.2 A.M.Pernas提出的方法［9］

A．M. Pernas等人的研究重點(diǎn)是構(gòu)建用于資源描述的本體，以更精確地描述網(wǎng)格資源，目的是為計(jì)算網(wǎng)格的研究服務(wù)。

2.2.1 構(gòu)建資源本體

資源本體的主要任務(wù)是精確地描述與網(wǎng)格資源相關(guān)的概念。在分析網(wǎng)格領(lǐng)域常用領(lǐng)域詞匯及常用資源的基礎(chǔ)上，參考NPACI［11］、ESG (Earth System Grid)［12］及NASA’s Information Power Grid［13］，初步建立相關(guān)文檔；在此基礎(chǔ)上即可建立資源本體。為構(gòu)建本體，建立的相關(guān)文檔包括以下幾部分：

（1)數(shù)據(jù)字典。描述了計(jì)算網(wǎng)格領(lǐng)域本體中所有類和實(shí)例的含義。共設(shè)計(jì)了14個(gè)類(圖2)。其中ComputationalResources是該本體的超類，其他類均是它的子類。

（2)概念分類樹。以樹的形式描述類之間的分類關(guān)系，如圖2所示。

（3)類屬性表。定義了類的屬性，包括屬性的關(guān)系邏輯、最小值、數(shù)據(jù)類型及測量單位等。

（4)實(shí)例表。描述了本體中每個(gè)實(shí)例的屬性及取值。

（5)屬性分類樹。以樹的形式描述了屬性之間的分類關(guān)系。

A．M. Pernas根據(jù)以上文檔構(gòu)建了資源本體，并使用Protégé 2000對其作了形式化的描述。

圖2 概念分類樹

為了更精確地描述資源，提高本體響應(yīng)時(shí)間，A．M. Pernas還定義了兩個(gè)組件：

①元數(shù)據(jù)，即關(guān)于數(shù)據(jù)的信息。它存儲關(guān)于資源的信息，如資源就緒時(shí)間、可被占用時(shí)間、資源地址、存儲容量、可用內(nèi)存、操作系統(tǒng)及系統(tǒng)結(jié)構(gòu)類型等。

②語義視圖，存儲資源當(dāng)前信息。當(dāng)一個(gè)請求到達(dá)語義視圖時(shí)，語義視圖返回該資源的當(dāng)前狀態(tài)，即是否可用、出故障或負(fù)載過重。

2.2.2 使用本體的網(wǎng)格架構(gòu)

A．M. Pernas提出的使用本體的網(wǎng)格架構(gòu)如圖3所示。本體直接工作在網(wǎng)格環(huán)境中，對資源的查詢使用本體中定義的詞匯，消除了查詢和讀取信息時(shí)產(chǎn)生的模糊性。這樣所有應(yīng)用中的概念（資源請求方和資源提供方）關(guān)于信息的表示和查詢均有一個(gè)確切的意義。

當(dāng)用戶提出資源請求時(shí)，首先將用戶請求轉(zhuǎn)換成資源本體中的概念，然后本體利用元數(shù)據(jù)和語義視圖獲得與資源相關(guān)的信息。其中元數(shù)據(jù)直接從資源和數(shù)據(jù)文件中獲取資源信息，語義視圖查詢MDS（元數(shù)據(jù)目錄服務(wù)）以獲取資源信息。元數(shù)據(jù)和語義視圖作為本體的輔助，可提高本體響應(yīng)時(shí)間，最后返回符合用戶要求的資源信息。

2.3 Andreas Harth的方法［10］

Andreas Harth等人開發(fā)了一個(gè)基于本體的網(wǎng)格資源選擇服務(wù)（Ontologybased Matchmaker Service，OMMS）。該服務(wù)除了支持語義上的資源匹配外，還支持動態(tài)資源發(fā)現(xiàn)及模式轉(zhuǎn)換（將不同的資源表示轉(zhuǎn)換成資源本體中的概念），以實(shí)現(xiàn)網(wǎng)格資源的自動查找與選擇。基于本體的資源匹配服務(wù)框架如圖4所示，包括三個(gè)模塊，即資源發(fā)現(xiàn)、請求處理及資源匹配模塊。

2.3.1 資源發(fā)現(xiàn)模塊

作為OMMS的關(guān)鍵組件，資源發(fā)現(xiàn)模塊動態(tài)地搜集資源信息，將其轉(zhuǎn)換為資源本體中的實(shí)例，并相應(yīng)地更新后臺知識庫。它由資源發(fā)現(xiàn)器和本體轉(zhuǎn)換器組成。資源發(fā)現(xiàn)器負(fù)責(zé)動態(tài)地搜集資源信息；本體轉(zhuǎn)換器負(fù)責(zé)將使用不同格式或語言表達(dá)的資源的屬性轉(zhuǎn)換為資源本體中的概念。

資源發(fā)現(xiàn)模塊使用網(wǎng)格中的監(jiān)控發(fā)現(xiàn)服務(wù)動態(tài)地發(fā)現(xiàn)和更新資源信息。對于支持消息訂閱/通知機(jī)制的資源信息提供者，OMMS訂閱他們的消息以獲得異步更新。只有當(dāng)資源的狀態(tài)改變時(shí)，OMMS才會被通知更新本體庫。這樣減少了OMMS與資源提供者之間的通信代價(jià)。對于不支持消息訂閱/通知機(jī)制的資源信息提供者，可以通過定期查詢以獲得最新的資源信息。 

2.3.2 請求處理模塊

該模塊中，用戶能以關(guān)鍵字的形式或自然語言形式向匹配器提交資源請求。請求處理模塊負(fù)責(zé)將接收到的資源請求轉(zhuǎn)換成資源請求本體，然后將該請求提交給資源匹配模塊。資源匹配模塊根據(jù)用戶的請求找到匹配的資源后，向用戶返回結(jié)果。

2.3.3 資源匹配模塊

基于本體的匹配模塊由領(lǐng)域本體、領(lǐng)域背景知識及匹配規(guī)則組成。背景知識使用本體中的概念獲取背景信息；匹配規(guī)則使用本體和背景知識匹配資源及作業(yè)需求。基于本體的匹配器建立在TRIPLE/XSB［14］推理數(shù)據(jù)庫系統(tǒng)之上。（1)領(lǐng)域本體：用來獲取描述資源特性和任務(wù)需求的領(lǐng)域知識及概念。Andreas Harth使用RDFS定義了三個(gè)本體：①資源本體。提供了描述資源的一個(gè)抽象模型，包括資源(如 ComputerSystem， OperatingSystem)、資源性能(OperatingSystem.TotalPhysicalMemory=5 000 MB)及其關(guān)系(如Running￣OS(ComputerSystemX， OperatingSystemY))。

②資源請求本體。描述了請求(如 Request.Owner)、請求特性(JobType=MPI)及資源需求(MinPhysicalMemory=1 G， NumberOfCPUs=16)；可支持對多個(gè)獨(dú)立資源的請求。

③Policy本體。描述了資源授權(quán)及使用Policy。例如AuthorizedAccounts=(ComputerSystem X{ user1，user2})列出了可訪問ComputerSystem X的用戶。

（2)領(lǐng)域背景知識：捕獲該領(lǐng)域不能為本體表達(dá)的附加知識（通常是實(shí)例級）。這些知識通常在匹配過程中會用到。知識是基于規(guī)則獲取的。這些規(guī)則使用本體中定義的詞匯增加不能為本體表述的定理，并且指導(dǎo)與實(shí)例相關(guān)的推理。

（3)匹配規(guī)則：定義了請求和資源之間的匹配條件。規(guī)則是使用TRIPLE語言實(shí)現(xiàn)的。除了支持基于屬性匹配的語法、數(shù)值的推理外，TRIPLE還支持基于對象屬性、關(guān)系以及背景知識的推理。下面是一個(gè)匹配規(guī)則的例子。規(guī)則需要以下輸入：屬性集Data、背景知識Background及領(lǐng)域本體Ontology。

資源匹配模塊根據(jù)用戶的請求、領(lǐng)域背景知識及匹配規(guī)則找到匹配的資源后，向用戶返回結(jié)果。當(dāng)有多個(gè)資源符合用戶的請求時(shí)，用戶可以定義一個(gè)RANK函數(shù)（定義為與資源屬性相關(guān)的數(shù)學(xué)表達(dá)式，如10*CPUClockSpeed+PhysicalMemory）給查找到的資源排序，從而選擇符合要求的最優(yōu)資源；用戶也可以指定以RANK值排序返回的資源數(shù)目。

2.4 Mumtaz Siddiqui的方法［15］

Andreas Harth提出的OMMS存在以下問題：使用RDFS表示本體，其描述及推理能力很有限；OMMS是基于規(guī)則匹配的，隨著新概念的加入，需要領(lǐng)域?qū)＜绎@式地定義相關(guān)規(guī)則。

針對以上問題，Mumtaz Siddiqui等人使用OWL表示資源本體，利用概念和角色的包含與被包含關(guān)系來匹配資源描述和用戶請求， 并借助于Protégé平臺結(jié)合Racer［16］推理器來執(zhí)行推理工作；由已經(jīng)宣告的顯性知識，利用邏輯推理及計(jì)算來獲得隱性知識，從而實(shí)現(xiàn)了基于本體的資源描述、發(fā)現(xiàn)和匹配。

Mumtaz Siddiqui提出的資源匹配框架如圖5所示。

圖5 Mumtaz Siddiqui提出的網(wǎng)格資源匹配框架

（1)資源本體：包括物理資源本體、邏輯資源請求本體和Policy本體。可利用相關(guān)本體對資源及請求進(jìn)行標(biāo)注，并基于此進(jìn)行相關(guān)的匹配和推理。

（2)資源信息收集器Collector：直接與網(wǎng)格資源和網(wǎng)格信息服務(wù)（如MDS）交互，動態(tài)地搜集資源信息，轉(zhuǎn)換為資源本體中的概念或?qū)嵗⑾鄳?yīng)地更新后臺知識庫。

（3)推理器：使用Racer作為推理器。主要執(zhí)行概念有效性和本體完整性檢查、概念的分類以及約束檢查，并接收由用戶查詢條件轉(zhuǎn)換得到的OWLQL，結(jié)合領(lǐng)域本體進(jìn)行推理。

（4)匹配器：資源匹配的核心。接收用戶請求，并將收到的資源請求轉(zhuǎn)換成資源本體中的概念；檢查請求中是否有沖突，然后利用概念的包含關(guān)系，執(zhí)行資源匹配。概念的包含關(guān)系有以下四種情況：

①RequestResource | Request≡Resource。請求是資源的子概念，或請求與資源是相等的概念，表示得到了一個(gè)滿足所有需求和約束的精確或最佳匹配。

②RequestResource。請求是資源的父概念，即資源不能完全滿足所有需求，但可作為一個(gè)相近的匹配或選擇。③Request∩Resource≠NULL。請求與資源有交集，可作為一個(gè)候選資源。

④Request∩Resource=NULL。請求與資源交集為空，即沒有匹配的資源。

Mumtaz Siddiqui提出的方法省去了領(lǐng)域?qū)＜绎@式定義匹配規(guī)則的煩瑣工作；同時(shí)，Racer推理機(jī)制的引入，提高了隱性知識的發(fā)現(xiàn)，實(shí)現(xiàn)了基于本體的網(wǎng)格資源描述、發(fā)現(xiàn)和匹配。

2.5 對比分析

根據(jù)以上對各種方法的詳細(xì)描述，對三種方法作了分析比較（表2），并得出基于本體的資源匹配有以下優(yōu)點(diǎn)：

（1）資源和需求描述的非對稱性。資源描述和需求描述可以獨(dú)立建立，然后在兩者之間進(jìn)行語義匹配。由于這種非對稱性，除非有新的概念或?qū)傩约尤耄Y源提供者與用戶之間無須協(xié)同工作。

（2）共享性和可維護(hù)性。因?yàn)楸倔w體現(xiàn)的是共同認(rèn)可的知識，反映的是相關(guān)領(lǐng)域中公認(rèn)的概念集，是可共享、易于維護(hù)及可理解的。

（3）可執(zhí)行一致性檢查。當(dāng)一個(gè)新資源加入時(shí)，匹配器可使用領(lǐng)域知識檢測資源描述中的沖突；當(dāng)有一個(gè)新的資源請求到達(dá)時(shí)，匹配器也可檢測資源請求中是否存在沖突。例如，資源描述OS=“Windows 2000”與CPUfamily=“Sparc”是沖突的。

（4）靈活性和可擴(kuò)展性。新的概念和詞匯可以容易地加入本體。

（5）可為應(yīng)用提供豐富的表達(dá)方式。由于資源和需求描述的非對稱性，資源請求可在應(yīng)用領(lǐng)域內(nèi)獨(dú)立建模。用戶可以加入高層應(yīng)用特性，由資源匹配器將這些高層特性轉(zhuǎn)換為本體中的概念或詞匯。

表2 基于本體的網(wǎng)格資源選擇方法對比

方法本體描述語言推理方式特點(diǎn)

A．M. PernasOWL FULL無專門的推理機(jī)制

具體描述了網(wǎng)格資源本體的構(gòu)建，為網(wǎng)格用戶提供了一個(gè)共享的概念模型；并定義了元數(shù)據(jù)和語義視圖兩個(gè)組件以提高本體響應(yīng)時(shí)間

Andreas HarthRDFS基于規(guī)則使用RDFS定義了領(lǐng)域本體、領(lǐng)域背景知識及匹配規(guī)則；請求和資源之間是基于領(lǐng)域規(guī)則進(jìn)行匹配；除了支持語義上的資源匹配外，還支持動態(tài)資源發(fā)現(xiàn)及模式轉(zhuǎn)換，實(shí)現(xiàn)了網(wǎng)格資源的自動查找與選擇

Mumtaz SiddiquiOWL DL基于概念的包含關(guān)系

使用OWL定義了領(lǐng)域本體， Racer作為推理器， 利用概念的包含關(guān)系進(jìn)行資源匹配，無須顯式地定義相關(guān)規(guī)則

3 結(jié)束語

本體的引入為屏蔽網(wǎng)格資源的異構(gòu)性和動態(tài)性，提高資源查找的靈活性提供了新的解決思路。目前關(guān)于基于本體的網(wǎng)格資源選擇的研究雖有一定進(jìn)展，但在實(shí)際應(yīng)用過程中還存在許多問題，如用戶接口不夠友好、對用戶的要求過高及資源選擇還不夠靈活等。隨著本體及語義Web技術(shù)的發(fā)展，且更好地與自然語言理解等相關(guān)領(lǐng)域方法的結(jié)合，網(wǎng)格資源管理將更完善，并為網(wǎng)格用戶提供更好的服務(wù)。

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