基于本體的網格資源查找和選擇算法研究
2007-01-01 00:00:00王莉劉宗田黃美麗竇旻陳鋒
計算機應用研究 2007年6期
摘 要：對現有的計算網格資源選擇算法作了總體性介紹，并在此基礎上詳細介紹了三種基于本體的資源查找和選擇算法。最后對各種方法作了分析、比較和總結。
關鍵詞：計算網格； 本體； 資源選擇； 資源匹配
中圖分類號：TP301.6文獻標志碼：A
文章編號：1001-3695(2007)06-0030-04
0 引言
網格是在異構、動態環境中實現資源共享和協作的技術［1］。網格中，用戶和資源是跨組織的，資源可能屬于不同的機構，有不同的使用約束，可以動態地加入或離開，而用戶也會提出對資源的特定需求。計算網格中的資源選擇問題是指在滿足資源約束的條件下，將符合用戶需求的資源分配給作業。資源選擇的一般過程［2］（圖1）如下：
①資源管理器把資源的注冊信息寫到資源信息數據庫中；
②用戶需要資源時，向資源管理器提出請求；
③資源管理器從資源信息數據庫中獲得匹配資源的信息，返回給用戶，用戶即獲得了資源信息。
圖1 網格資源選擇過程
現有的網格資源選擇算法多是基于屬性、對稱的匹配，即資源提供方和請求方必須在屬性名和值的表示上保持一致；只支持簡單的查詢方式（如關鍵字和分類查詢）。這大大限制了資源選擇的靈活性，且不易擴展。在網格這種異構環境中，作業請求和資源約束通常在不同的應用環境中定義，使用不同的形式和語法，要實現資源提供方和請求方在語法及語義上的一致是非常困難的。近年來隨著語義Web的發展，一些研究人員提出在資源描述和請求中引入本體的概念，以解決網格中資源描述和請求的異構問題。
1 網格中現有資源選擇算法
1.1 ClassAd資源匹配［3］
Rajesh Raman等人提出了ClassAd資源匹配模型，用于解決在分布式環境下資源的選擇和分配問題，已用在Condor［4］的資源管理中。該模型提供的是一種雙向匹配，要求資源請求方指定對資源的要求，同時資源提供方指定對資源使用的相應約束條件。資源提供方和請求方能以任意方式描述各自的條件或需求，但是他們必須采用相同的語法(屬性—值對的形式)。只有當資源的提供方與請求方對資源的約束及需求的描述中均使用相同的屬性名以及相匹配的屬性值時，資源匹配才能進行。當有多個資源滿足作業需求時，用戶可以定義一個函數給資源排序，然后根據排序結果選擇最優的資源。下面是一個基于ClassAd資源匹配的例子。資源提供方與請求方使用相同的屬性—值對的形式描述資源需求和使用約束。
1.2 Gang匹配［5］
為了解決ClassAd匹配模型中的二元匹配問題， Raman又提出了Gang匹配，允許資源請求方提出一個所需求資源的列表。例如，資源請求方可以同時請求多個計算資源，并分別說明對每個資源的需求。然而Gang匹配并不支持集合匹配模式［6］，如資源請求者可能會請求一個總內存容量大于10 GB的資源集合。對于這樣的請求，Gang匹配就顯得無能為力了。
1.3 基于約束滿足的匹配［7］
Chuang Liu提出了一個應用于網格中的資源選擇系統 Redline匹配系統。在該系統中，資源選擇問題首先被轉換為約束滿足問題，然后檢查這一系列的約束是否有沖突發生，最后匹配器用已經存在的約束解決機制來處理轉換的約束滿足問題。
與ClassAd相同，Redline匹配系統也是基于資源和需求的對稱描述，即用相同的語法來描述資源和需求。但與ClassAd相比，Redline匹配系統更富有表現力，而且可以支持Gang匹配和集合匹配。
1.4 對比分析
表1是對現有的計算網格資源選擇算法所作的對比。可以看出，以上所介紹的資源匹配系統，均要求對資源屬性和需求的對稱語法描述，因此在系統應用過程中很難向其加入新概念或知識。而且在網格環境下，資源和用戶大多都是跨越多個不同的組織或機構，這就很難保證資源描述和用戶請求使用相同的屬性名，表達相同的語義。隨著語義Web的發展，一些研究人員提出在資源描述和請求中引入本體，以解決網格中資源描述和請求的異構問題。
表1 現有網格資源選擇算法對比
匹配方法需要資源和需求的對稱描述支持同時請求多個計算資源支持集合匹配
不足
ClassAd資源匹配YNN
Gang匹配YYN
基于約束滿足的匹配YYY
均要求對資源屬性和需求的對稱語法描述；在系統應用過程中很難向其加入新概念或知識；靈活性和可擴展性差
2 基于本體的網格資源選擇方法
基于本體的資源匹配是指在資源描述和用戶請求中引入本體，以解決網格中資源描述和請求的異構問題，提高資源查找的靈活性。
2.1 本體概述
本體最早是一個哲學上的概念。從哲學的范疇來說，本體是客觀存在的一個系統的解釋或說明，關心的是客觀現實的抽象本質。隨著人工智能的發展，本體被人工智能界賦予了新的定義。然而最初人們對本體的理解并不完善，對本體的定義也在不斷的發展變化中。其中最為大家普遍接受的本體定義是：本體是共享概念模型的明確的形式化規范說明。這個定義體現了本體的四層含義［8］：
①概念模型（Conceptualization）。
通過抽象出客觀世界中一些現象（Phenomenon）的相關概念而得到的模型；其表示的含義獨立于具體的環境狀態。
②明確（Explicit）。
所使用的概念及使用這些概念的約束均有明確的定義。
③形式化（Formal）。
本體是計算機可讀的。
④共享（Share）。
本體中體現的是共同認可的知識，反映的是相關領域中公認的概念集，它所針對的是團體而不是個體。
領域本體用于表達領域相關的知識，提供對該領域知識的共同理解，確定該領域內共同認可的詞匯，并從不同層次的形式化模式上給出這些詞匯（術語）和詞匯之間相互關系的明確定義。
2.2 A.M.Pernas提出的方法［9］
A．M. Pernas等人的研究重點是構建用于資源描述的本體，以更精確地描述網格資源，目的是為計算網格的研究服務。
2.2.1 構建資源本體
資源本體的主要任務是精確地描述與網格資源相關的概念。在分析網格領域常用領域詞匯及常用資源的基礎上，參考NPACI［11］、ESG (Earth System Grid)［12］及NASA’s Information Power Grid［13］，初步建立相關文檔；在此基礎上即可建立資源本體。為構建本體，建立的相關文檔包括以下幾部分：
（1)數據字典。描述了計算網格領域本體中所有類和實例的含義。共設計了14個類(圖2)。其中ComputationalResources是該本體的超類，其他類均是它的子類。
（2)概念分類樹。以樹的形式描述類之間的分類關系，如圖2所示。
（3)類屬性表。定義了類的屬性，包括屬性的關系邏輯、最小值、數據類型及測量單位等。
（4)實例表。描述了本體中每個實例的屬性及取值。
（5)屬性分類樹。以樹的形式描述了屬性之間的分類關系。
A．M. Pernas根據以上文檔構建了資源本體，并使用Protégé 2000對其作了形式化的描述。
圖2 概念分類樹
為了更精確地描述資源，提高本體響應時間，A．M. Pernas還定義了兩個組件：
①元數據，即關于數據的信息。它存儲關于資源的信息，如資源就緒時間、可被占用時間、資源地址、存儲容量、可用內存、操作系統及系統結構類型等。
②語義視圖，存儲資源當前信息。當一個請求到達語義視圖時，語義視圖返回該資源的當前狀態，即是否可用、出故障或負載過重。
2.2.2 使用本體的網格架構
A．M. Pernas提出的使用本體的網格架構如圖3所示。本體直接工作在網格環境中，對資源的查詢使用本體中定義的詞匯，消除了查詢和讀取信息時產生的模糊性。這樣所有應用中的概念（資源請求方和資源提供方）關于信息的表示和查詢均有一個確切的意義。
當用戶提出資源請求時，首先將用戶請求轉換成資源本體中的概念，然后本體利用元數據和語義視圖獲得與資源相關的信息。其中元數據直接從資源和數據文件中獲取資源信息，語義視圖查詢MDS（元數據目錄服務）以獲取資源信息。元數據和語義視圖作為本體的輔助，可提高本體響應時間，最后返回符合用戶要求的資源信息。
2.3 Andreas Harth的方法［10］
Andreas Harth等人開發了一個基于本體的網格資源選擇服務（Ontologybased Matchmaker Service，OMMS）。該服務除了支持語義上的資源匹配外，還支持動態資源發現及模式轉換（將不同的資源表示轉換成資源本體中的概念），以實現網格資源的自動查找與選擇。基于本體的資源匹配服務框架如圖4所示，包括三個模塊，即資源發現、請求處理及資源匹配模塊。
2.3.1 資源發現模塊
作為OMMS的關鍵組件，資源發現模塊動態地搜集資源信息，將其轉換為資源本體中的實例，并相應地更新后臺知識庫。它由資源發現器和本體轉換器組成。資源發現器負責動態地搜集資源信息；本體轉換器負責將使用不同格式或語言表達的資源的屬性轉換為資源本體中的概念。
資源發現模塊使用網格中的監控發現服務動態地發現和更新資源信息。對于支持消息訂閱/通知機制的資源信息提供者，OMMS訂閱他們的消息以獲得異步更新。只有當資源的狀態改變時，OMMS才會被通知更新本體庫。這樣減少了OMMS與資源提供者之間的通信代價。對于不支持消息訂閱/通知機制的資源信息提供者，可以通過定期查詢以獲得最新的資源信息。
2.3.2 請求處理模塊
該模塊中，用戶能以關鍵字的形式或自然語言形式向匹配器提交資源請求。請求處理模塊負責將接收到的資源請求轉換成資源請求本體，然后將該請求提交給資源匹配模塊。資源匹配模塊根據用戶的請求找到匹配的資源后，向用戶返回結果。
2.3.3 資源匹配模塊
基于本體的匹配模塊由領域本體、領域背景知識及匹配規則組成。背景知識使用本體中的概念獲取背景信息；匹配規則使用本體和背景知識匹配資源及作業需求。基于本體的匹配器建立在TRIPLE/XSB［14］推理數據庫系統之上。（1)領域本體：用來獲取描述資源特性和任務需求的領域知識及概念。Andreas Harth使用RDFS定義了三個本體：①資源本體。提供了描述資源的一個抽象模型，包括資源(如 ComputerSystem， OperatingSystem)、資源性能(OperatingSystem.TotalPhysicalMemory=5 000 MB)及其關系(如Running￣OS(ComputerSystemX， OperatingSystemY))。
②資源請求本體。描述了請求(如 Request.Owner)、請求特性(JobType=MPI)及資源需求(MinPhysicalMemory=1 G， NumberOfCPUs=16)；可支持對多個獨立資源的請求。
③Policy本體。描述了資源授權及使用Policy。例如AuthorizedAccounts=(ComputerSystem X{ user1，user2})列出了可訪問ComputerSystem X的用戶。
（2)領域背景知識：捕獲該領域不能為本體表達的附加知識（通常是實例級）。這些知識通常在匹配過程中會用到。知識是基于規則獲取的。這些規則使用本體中定義的詞匯增加不能為本體表述的定理，并且指導與實例相關的推理。
（3)匹配規則：定義了請求和資源之間的匹配條件。規則是使用TRIPLE語言實現的。除了支持基于屬性匹配的語法、數值的推理外，TRIPLE還支持基于對象屬性、關系以及背景知識的推理。下面是一個匹配規則的例子。規則需要以下輸入：屬性集Data、背景知識Background及領域本體Ontology。
資源匹配模塊根據用戶的請求、領域背景知識及匹配規則找到匹配的資源后，向用戶返回結果。當有多個資源符合用戶的請求時，用戶可以定義一個RANK函數（定義為與資源屬性相關的數學表達式，如10*CPUClockSpeed+PhysicalMemory）給查找到的資源排序，從而選擇符合要求的最優資源；用戶也可以指定以RANK值排序返回的資源數目。
2.4 Mumtaz Siddiqui的方法［15］
Andreas Harth提出的OMMS存在以下問題：使用RDFS表示本體，其描述及推理能力很有限；OMMS是基于規則匹配的，隨著新概念的加入，需要領域專家顯式地定義相關規則。
針對以上問題，Mumtaz Siddiqui等人使用OWL表示資源本體，利用概念和角色的包含與被包含關系來匹配資源描述和用戶請求， 并借助于Protégé平臺結合Racer［16］推理器來執行推理工作；由已經宣告的顯性知識，利用邏輯推理及計算來獲得隱性知識，從而實現了基于本體的資源描述、發現和匹配。
Mumtaz Siddiqui提出的資源匹配框架如圖5所示。
圖5 Mumtaz Siddiqui提出的網格資源匹配框架
（1)資源本體：包括物理資源本體、邏輯資源請求本體和Policy本體。可利用相關本體對資源及請求進行標注，并基于此進行相關的匹配和推理。
（2)資源信息收集器Collector：直接與網格資源和網格信息服務（如MDS）交互，動態地搜集資源信息，轉換為資源本體中的概念或實例，并相應地更新后臺知識庫。
（3)推理器：使用Racer作為推理器。主要執行概念有效性和本體完整性檢查、概念的分類以及約束檢查，并接收由用戶查詢條件轉換得到的OWLQL，結合領域本體進行推理。
（4)匹配器：資源匹配的核心。接收用戶請求，并將收到的資源請求轉換成資源本體中的概念；檢查請求中是否有沖突，然后利用概念的包含關系，執行資源匹配。概念的包含關系有以下四種情況：
①RequestResource | Request≡Resource。請求是資源的子概念，或請求與資源是相等的概念，表示得到了一個滿足所有需求和約束的精確或最佳匹配。
②RequestResource。請求是資源的父概念，即資源不能完全滿足所有需求，但可作為一個相近的匹配或選擇。③Request∩Resource≠NULL。請求與資源有交集，可作為一個候選資源。
④Request∩Resource=NULL。請求與資源交集為空，即沒有匹配的資源。
Mumtaz Siddiqui提出的方法省去了領域專家顯式定義匹配規則的煩瑣工作；同時，Racer推理機制的引入，提高了隱性知識的發現，實現了基于本體的網格資源描述、發現和匹配。
2.5 對比分析
根據以上對各種方法的詳細描述，對三種方法作了分析比較（表2），并得出基于本體的資源匹配有以下優點：
（1）資源和需求描述的非對稱性。資源描述和需求描述可以獨立建立，然后在兩者之間進行語義匹配。由于這種非對稱性，除非有新的概念或屬性加入，資源提供者與用戶之間無須協同工作。
（2）共享性和可維護性。因為本體體現的是共同認可的知識，反映的是相關領域中公認的概念集，是可共享、易于維護及可理解的。
（3）可執行一致性檢查。當一個新資源加入時，匹配器可使用領域知識檢測資源描述中的沖突；當有一個新的資源請求到達時，匹配器也可檢測資源請求中是否存在沖突。例如，資源描述OS=“Windows 2000”與CPUfamily=“Sparc”是沖突的。
（4）靈活性和可擴展性。新的概念和詞匯可以容易地加入本體。
（5）可為應用提供豐富的表達方式。由于資源和需求描述的非對稱性，資源請求可在應用領域內獨立建模。用戶可以加入高層應用特性，由資源匹配器將這些高層特性轉換為本體中的概念或詞匯。
表2 基于本體的網格資源選擇方法對比
方法本體描述語言推理方式特點
A．M. PernasOWL FULL無專門的推理機制
具體描述了網格資源本體的構建，為網格用戶提供了一個共享的概念模型；并定義了元數據和語義視圖兩個組件以提高本體響應時間
Andreas HarthRDFS基于規則使用RDFS定義了領域本體、領域背景知識及匹配規則；請求和資源之間是基于領域規則進行匹配；除了支持語義上的資源匹配外，還支持動態資源發現及模式轉換，實現了網格資源的自動查找與選擇
Mumtaz SiddiquiOWL DL基于概念的包含關系
使用OWL定義了領域本體， Racer作為推理器， 利用概念的包含關系進行資源匹配，無須顯式地定義相關規則
3 結束語
本體的引入為屏蔽網格資源的異構性和動態性，提高資源查找的靈活性提供了新的解決思路。目前關于基于本體的網格資源選擇的研究雖有一定進展，但在實際應用過程中還存在許多問題，如用戶接口不夠友好、對用戶的要求過高及資源選擇還不夠靈活等。隨著本體及語義Web技術的發展，且更好地與自然語言理解等相關領域方法的結合，網格資源管理將更完善，并為網格用戶提供更好的服務。
本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。
