王帥+馬景奕

摘要：為解決多資源文件共享和語(yǔ)義網(wǎng)格環(huán)境下異構(gòu)資源共享管理問題，提出了一種新的分布式調(diào)度算法。該算法采用語(yǔ)義網(wǎng)格的分布式技術(shù)，充分利用資源共享模型實(shí)現(xiàn)高效的資源調(diào)度。仿真實(shí)驗(yàn)表明，該算法具有較好的執(zhí)行效率。與其它算法相比，在相同任務(wù)數(shù)量時(shí)響應(yīng)更快。

關(guān)鍵詞：語(yǔ)義網(wǎng)格；輕量級(jí)目錄訪問協(xié)議；資源共享模型；分布式調(diào)度算法；資源發(fā)現(xiàn)

DOIDOI：10.11907/rjdk.172030

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2017）012-0064-03

Abstract：rid is a hot technology for sharing， managing information resources and providing information services. In the current situation of increasingly serious environmental pollution， green cloud computing has become an important issue in the field of green communications.

In order to solve the problems in the management of heterogeneous resources in multi resource file sharing and semantic sharing in grid， this paper proposes a new distributed scheduling algorithm， the algorithm adopts the distributed semantic grid technology， and make full use of the resource sharing model， to achieve efficient resource scheduling， the simulation results show that the proposed algorithm has good execution efficiency， at the same time the number of tasks in response， faster response， and prove the effectiveness of the algorithm.

Key Words：semantic grid； lightweight directory access protocol； resources sharing model； distributed scheduling algorithm； resource discovery

0 引言

網(wǎng)格技術(shù)是新興的互聯(lián)網(wǎng)技術(shù)，是下一代互聯(lián)網(wǎng)技術(shù)研究和應(yīng)用的重要領(lǐng)域 [1]。近年來(lái)，物聯(lián)網(wǎng)、車聯(lián)網(wǎng)、云計(jì)算、大數(shù)據(jù)、綠色通信、量子通信、智慧城市、智能家居、深度學(xué)習(xí)等新概念和新技術(shù)層出不窮，語(yǔ)義網(wǎng)格逐漸引起人們的關(guān)注。網(wǎng)格是協(xié)調(diào)管理各種地理分布資源的手段，為用戶提供透明、一致的訪問接口，實(shí)現(xiàn)資源共享 [2]。

互聯(lián)網(wǎng)頁(yè)面大多數(shù)基于Web頁(yè)面技術(shù)，它的缺點(diǎn)是用HTML編寫，這種語(yǔ)言主要用于文本格式化，而不是識(shí)別和標(biāo)記內(nèi)容。同時(shí)，受限于用戶端，加載效率、兼容性不高。新的HTML標(biāo)準(zhǔn)已經(jīng)擴(kuò)展（元標(biāo)簽），可向頁(yè)面添加更多信息，用于標(biāo)記整個(gè)頁(yè)面，而不是在給定頁(yè)面上的內(nèi)容描述[3]。HTML頁(yè)面的另一個(gè)目標(biāo)是提供到其它頁(yè)面和信息源鏈接。語(yǔ)義Web應(yīng)用于網(wǎng)格環(huán)境，形成語(yǔ)義網(wǎng)格，用于描述網(wǎng)格中信息的語(yǔ)義網(wǎng)格元數(shù)據(jù)。語(yǔ)義網(wǎng)格是網(wǎng)格相關(guān)技術(shù)的延伸，包括信息和服務(wù)，可使計(jì)算機(jī)系統(tǒng)與人更好地協(xié)同工作。語(yǔ)義網(wǎng)格通常是網(wǎng)格和語(yǔ)義Web技術(shù)的多重組合，通過不同組合提高計(jì)算能力和數(shù)據(jù)集成能力。

為解決多資源文件共享和語(yǔ)義網(wǎng)格環(huán)境下的管理問題，本文提出了一種基于語(yǔ)義網(wǎng)格環(huán)境的文件資源共享模型和分布式調(diào)度算法。該模型將注冊(cè)通知機(jī)制、確定性算法與非確定性算法消息傳遞機(jī)制互相組合，從而對(duì)網(wǎng)格中的各節(jié)點(diǎn)進(jìn)行有效管理調(diào)度。本文提出一種新的分布式調(diào)度算法（NDSA），用于解決語(yǔ)義網(wǎng)格中的異構(gòu)資源共享問題。圖1 描述的是語(yǔ)義網(wǎng)格的文檔結(jié)構(gòu)。

通過應(yīng)用語(yǔ)義網(wǎng)格的分布式技術(shù)，將兩者有機(jī)結(jié)合，可極大提高資源調(diào)度的利用率。

1 語(yǔ)義網(wǎng)格資源共享模型

資源信息表現(xiàn)在兩個(gè)方面：①存儲(chǔ)在數(shù)據(jù)庫(kù)或其它介質(zhì)中的信息通過可視化呈現(xiàn)給用戶；②針對(duì)存儲(chǔ)介質(zhì)中的信息 [4]創(chuàng)建多個(gè)中間層信息，中間層在應(yīng)用邏輯層中用相應(yīng)的數(shù)據(jù)表示。

元數(shù)據(jù)是描述數(shù)據(jù)的數(shù)據(jù)，是對(duì)數(shù)據(jù)對(duì)象的抽象描述，使各種信息體現(xiàn)在屬性和值之間的關(guān)系上[5]。資源目錄服務(wù)功能模塊為分布式資源共享模型提供Grid信息服務(wù)[6]。資源目錄由元數(shù)據(jù)描述的所有資源構(gòu)成。資源目錄服務(wù)的主要任務(wù)是管理網(wǎng)格中的各種資源，包括資源發(fā)現(xiàn)、注冊(cè)、修改和取消。系統(tǒng)使用LDAP（輕量級(jí)目錄訪問協(xié)議）目錄服務(wù)器存儲(chǔ)資源目錄信息[7]。LDAP目錄樹結(jié)構(gòu)以樹級(jí)結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)，以條目的形式存儲(chǔ)一組屬性，每條記錄包括屬性類型和屬性值，一個(gè)屬性可以存儲(chǔ)多個(gè)值。LDAP數(shù)據(jù)庫(kù)的靈活性和可擴(kuò)展性，非常適用于廣域分布式資源共享系統(tǒng)。每個(gè)網(wǎng)格節(jié)點(diǎn)都要注冊(cè)本地資源來(lái)查找和收集監(jiān)控，并且每個(gè)節(jié)點(diǎn)維護(hù)本地LDAP服務(wù)器和本地存儲(chǔ)的資源信息。圖2描述的是語(yǔ)義網(wǎng)格之間的數(shù)據(jù)共享過程。

2 網(wǎng)格任務(wù)調(diào)度算法

通過互聯(lián)網(wǎng)將不同地理位置的分布式計(jì)算資源、存儲(chǔ)資源、通信資源、軟件資源、信息資源和知識(shí)資源集成為一個(gè)巨大的超級(jí)計(jì)算機(jī)，各種資源實(shí)現(xiàn)共享，這是網(wǎng)格作業(yè)調(diào)度的主要任務(wù)[8]。用戶向網(wǎng)格系統(tǒng)提交計(jì)算任務(wù)，為了共享網(wǎng)格資源和網(wǎng)格調(diào)度器，這些任務(wù)被分配到適當(dāng)?shù)恼{(diào)度資源上。高效的調(diào)度策略或算法可以利用網(wǎng)格系統(tǒng)的處理能力，提高面向?qū)ο蟮膽?yīng)用性能。在網(wǎng)格調(diào)度算法中，策略的主要目的是提高圖2 語(yǔ)義網(wǎng)格之間的數(shù)據(jù)共享過程

系統(tǒng)吞吐量和利用率，通過經(jīng)濟(jì)系統(tǒng)和用戶約束，使整個(gè)系統(tǒng)任務(wù)中的網(wǎng)格最小化。遺傳算法創(chuàng)建一個(gè)調(diào)度集合，從中找到最佳調(diào)度，這種繼承特性可以遺傳到下一代，遺傳算法通過適應(yīng)度函數(shù)交叉和重組實(shí)現(xiàn)最優(yōu)調(diào)度[9]。這是一種迭代算法，它具有吸收系統(tǒng)在演變過程中的變化差異優(yōu)勢(shì)，并能夠適應(yīng)網(wǎng)格系統(tǒng)的動(dòng)態(tài)變化。

在網(wǎng)格技術(shù)的許多問題中，網(wǎng)格計(jì)算、任務(wù)調(diào)度是一般形式的NP問題，沒有最優(yōu)解。有效的調(diào)度算法，如并行資源分配決策和分布式調(diào)度算法，并不能很好地適應(yīng)資源異構(gòu)性網(wǎng)格的各種特性。因此，如何合理地分配和管理網(wǎng)格資源以滿足廣泛的服務(wù)需求，實(shí)現(xiàn)資源的最佳利用，成為該領(lǐng)域研究的關(guān)鍵。

網(wǎng)格任務(wù)調(diào)度可分為通信間任務(wù)、任務(wù)組調(diào)度和獨(dú)立任務(wù)組調(diào)度。集中式調(diào)度是系統(tǒng)中的中央調(diào)度員，負(fù)責(zé)收集狀態(tài)信息并作出所有調(diào)度決策。機(jī)器周期性地將分組更新到其發(fā)送狀態(tài)，報(bào)告其負(fù)載信息；中央調(diào)度服務(wù)建立一個(gè)主機(jī)候選者序列表，以響應(yīng)客戶請(qǐng)求的遠(yuǎn)程執(zhí)行。解決容錯(cuò)集中調(diào)度問題的典型方法是提供多個(gè)備用服務(wù)員[10]。

3 實(shí)驗(yàn)與結(jié)果分析

在Matlab環(huán)境下設(shè)計(jì)網(wǎng)格任務(wù)調(diào)度系統(tǒng)仿真程序。該程序根據(jù)主機(jī)處理能力、主機(jī)數(shù)量、任務(wù)數(shù)量、每個(gè)任務(wù)的預(yù)測(cè)執(zhí)行時(shí)間、通信開銷和時(shí)間的仿真等需求，生成任務(wù)開銷和其它參數(shù)。

圖3顯示的是在語(yǔ)義網(wǎng)格環(huán)境中3種算法的負(fù)載均衡度比較。負(fù)載均衡度越高，表明該算法執(zhí)行的效果越理想，資源利用的公平性越好。隨著系統(tǒng)任務(wù)數(shù)量的不斷增加，NDSA算法性能始終優(yōu)于其它兩種算法。

圖4顯示的是3種調(diào)度算法的響應(yīng)時(shí)間比較。圖5和圖6分別顯示在不同進(jìn)化代數(shù)和不同任務(wù)規(guī)模時(shí)，3種調(diào)度算法的執(zhí)行時(shí)間情況。

4 結(jié)語(yǔ)

網(wǎng)格技術(shù)作為一種高性能的廣域分布式計(jì)算模型，是許多機(jī)構(gòu)的研究熱點(diǎn)。Matlab仿真實(shí)驗(yàn)結(jié)果表明，本文提出的分布式調(diào)度算法（NDSA）具有較好的執(zhí)行效率，在相同任務(wù)數(shù)量時(shí)響應(yīng)速度更快，可在網(wǎng)格資源中實(shí)現(xiàn)公平有效的任務(wù)調(diào)度；在負(fù)載均衡度、系統(tǒng)響應(yīng)時(shí)間、系統(tǒng)執(zhí)行時(shí)間等方面，NDSA算法都比傳統(tǒng)的Max-min算法和GA算法表現(xiàn)出更佳的性能，該算法能有效應(yīng)用到語(yǔ)義網(wǎng)格各領(lǐng)域。

參考文獻(xiàn)：

[1] I FOSTER， C KESSELMAN，S TUECKE.The anatomy of the grid： enabling scalable virtual organizations[J]. International Journal Supercomputing Application， 2001，15（3）：200-222.

[2] M KAYA.Multi-objective genetic algorithm based approaches for mining optimized fuzzy association rules[J]. Soft Comput，2006，10（7）：578-586.

[3] L C JIAO， L WANG. A novel genetic algorithm based on immunity [J].IEEE Transaction on Systems， Man， and Cybernetics-Part A，Systems and Humans， 2000，30（5）：552-561.

[4] ZHONG WEI CAI， LIU JING， XUE MING ZHI， et al. A multi-agent genetic algorithm for global numerical optimization[J]. IEEE Trans.System，Man and Cybernetics—Part B，2004，34（2）：1128-1141.

[5] T HONG， C CHEN， Y WU， et al.A GA-based fuzzy mining approach to achieve a trade-off between number of rules and suitability of membership functions[J].Soft Comput，2006，10（11）：1091-1101.

[6] WANNENG SHU， SHIJUE ZHENG.A Real-course-based load balanced algorithm of VOD cluster[C].2005 International Symposium on Computer Science and Technology （ISCST 2005），Ningbo，2005.

[7] ZHANG JIANG SHE， XU ZONG BEN， LIANG YI. Global Annealing genetic algorithm and its convergence well necessary condition [J].science in China（Series E），1997，27（2）：154-164.

[8] WANG XIA， ZHOU GUO BIAO. Strong convergence of global annealing genetic algorithm[J]. mathematica applicata，2003，16（3）：1-7.

[9] RAJKUMAR BUYYA， DAVID ABRAMSON， JONATHAN GIDDY. Grid resource management， scheduling， and computational economy [C].WGCC，Japan， 2000.

[10] 孫清超，孫偉，郭鋼.多項(xiàng)目環(huán)境下復(fù)雜產(chǎn)品開發(fā)資源動(dòng)態(tài)分配技術(shù)[J].中國(guó)機(jī)械工程，2011，22（23）：2844-2848.

[11] 熊張悅，姜俊穎，舒萬(wàn)能.綠色云計(jì)算的任務(wù)調(diào)度與能耗優(yōu)化機(jī)制研究[J].軟件導(dǎo)刊，2016，15（4）：38-40.

（責(zé)任編輯：杜能鋼）