基于價(jià)格時(shí)延Petri網(wǎng)的超級(jí)節(jié)點(diǎn)網(wǎng)格調(diào)度*

潘善亮 ，黃 希 ，茅琴嬌

（1.寧波大學(xué)計(jì)算機(jī)科學(xué)技術(shù)研究所 寧波 315211；2.西安交通大學(xué)電子與信息工程學(xué)院 西安 710049）

1 引言

近幾年提出的超級(jí)節(jié)點(diǎn)模式網(wǎng)格資源管理[1,2]很好地在高效的集中式搜索與擴(kuò)展性強(qiáng)的分布式搜索之間實(shí)現(xiàn)了平衡。超級(jí)節(jié)點(diǎn)模式網(wǎng)格按資源注冊(cè)方式主要分為兩種[3]：一種是資源節(jié)點(diǎn)按地域界限劃分的超級(jí)節(jié)點(diǎn)模式網(wǎng)格；另一種是資源節(jié)點(diǎn)基于語(yǔ)義相似度聚類的超級(jí)節(jié)點(diǎn)模式網(wǎng)格。其中，在第二種超級(jí)節(jié)點(diǎn)模式網(wǎng)格中，資源節(jié)點(diǎn)基于語(yǔ)義相似度聚類，同一超級(jí)節(jié)點(diǎn)域內(nèi)的資源類型相同。這種類型的網(wǎng)格至少具有以下優(yōu)點(diǎn)：資源的描述包含本體語(yǔ)義特征，資源發(fā)現(xiàn)具有更高的查全率與查準(zhǔn)率[4]；具有相同類型的資源預(yù)先分組聚類，能降低查找空間，資源發(fā)現(xiàn)具有更高的效率[5,6]。因此，資源節(jié)點(diǎn)基于語(yǔ)義相似度聚類的超級(jí)節(jié)點(diǎn)模式網(wǎng)格受到了廣泛的關(guān)注。

[7～9]提出了利用超級(jí)節(jié)點(diǎn)網(wǎng)絡(luò)來(lái)管理文件共享系統(tǒng)，資源節(jié)點(diǎn)依據(jù)其共享文件的語(yǔ)義相似性進(jìn)行分組。參考文獻(xiàn)[10]將Web服務(wù)按照語(yǔ)義定義進(jìn)行分組聚類，由超級(jí)節(jié)點(diǎn)進(jìn)行管理。參考文獻(xiàn)[11]構(gòu)建了一個(gè)網(wǎng)格資源節(jié)點(diǎn)身份可靠性度量函數(shù)和行為表現(xiàn)信譽(yù)度評(píng)估策略，建立了一個(gè)網(wǎng)格任務(wù)調(diào)度的安全融合模型，以此為基礎(chǔ)，提出一個(gè)時(shí)間—安全驅(qū)動(dòng)的雙目標(biāo)優(yōu)化網(wǎng)格依賴任務(wù)調(diào)度模型。參考文獻(xiàn)[12]將節(jié)點(diǎn)的興趣進(jìn)行分組聚類，每個(gè)分組內(nèi)的節(jié)點(diǎn)構(gòu)成一個(gè)語(yǔ)義樹(shù)，根節(jié)點(diǎn)之間互聯(lián)形成一個(gè)覆蓋網(wǎng)絡(luò)。參考文獻(xiàn)[13]提出語(yǔ)義覆蓋簇的概念，討論了資源節(jié)點(diǎn)如何加入對(duì)應(yīng)的超級(jí)節(jié)點(diǎn)。參考文獻(xiàn)[14]提出了基于超級(jí)節(jié)點(diǎn)模式網(wǎng)格的資源語(yǔ)義描述與注冊(cè)框架。參考文獻(xiàn)[15]在參考文獻(xiàn)[14]的基礎(chǔ)上提出了資源分類的處理過(guò)程以及超級(jí)節(jié)點(diǎn)的選擇方法。以上學(xué)者雖然將本體以及資源分類聚集的思想引入網(wǎng)格中，但是他們的討論局限于網(wǎng)格體系結(jié)構(gòu)，資源的描述與注冊(cè)框架以及資源分類的處理過(guò)程等方面，而沒(méi)有具體討論對(duì)于一個(gè)需要協(xié)同不同類型的資源以完成網(wǎng)格協(xié)作型任務(wù)的具體調(diào)度方法及其形式化建模和理論分析。參考文獻(xiàn)[16]針對(duì)資源節(jié)點(diǎn)按地域界限劃分的超級(jí)節(jié)點(diǎn)模式網(wǎng)格提出了一種兩階段網(wǎng)格任務(wù)調(diào)度方法，并用時(shí)延Petri網(wǎng)對(duì)調(diào)度過(guò)程進(jìn)行了建模、分析。但是其討論的對(duì)象是簡(jiǎn)單的元任務(wù)且只考慮了調(diào)度的時(shí)間特性。

不同于以上參考文獻(xiàn)的研究，本文針對(duì)資源節(jié)點(diǎn)基于語(yǔ)義相似度聚類的超級(jí)節(jié)點(diǎn)模式網(wǎng)格，提出網(wǎng)格協(xié)作型任務(wù)的面向用戶時(shí)間、費(fèi)用及二者偏好參數(shù)等多QoS約束的調(diào)度算法且考慮了重調(diào)度機(jī)制。鑒于復(fù)雜的調(diào)度過(guò)程具有并行、分布式的特點(diǎn)，筆者利用價(jià)格時(shí)延Petri網(wǎng)對(duì)調(diào)度過(guò)程進(jìn)行建模，圖形化調(diào)度過(guò)程，構(gòu)造并分析可達(dá)任務(wù)圖，通過(guò)實(shí)例驗(yàn)證算法的有效性。

2 網(wǎng)格協(xié)作型任務(wù)調(diào)度算法

2.1 資源管理模型

圖1顯示了資源節(jié)點(diǎn)基于語(yǔ)義相似度聚類的超級(jí)節(jié)點(diǎn)模式網(wǎng)格體系結(jié)構(gòu)[14,15]。

圖1 網(wǎng)格體系結(jié)構(gòu)

在圖1中，網(wǎng)格資源節(jié)點(diǎn)基于語(yǔ)義相似度分組聚類，每個(gè)聚類對(duì)應(yīng)的網(wǎng)格社區(qū)有一個(gè)超級(jí)節(jié)點(diǎn)負(fù)責(zé)管理。規(guī)定一個(gè)節(jié)點(diǎn)只提供一種類型的資源且資源的分類體系不考慮各類型之間的層次關(guān)系[17]。

“Class”為一組語(yǔ)義相似的網(wǎng)格資源節(jié)點(diǎn)集合。每個(gè)Class包含兩種類型的節(jié)點(diǎn)：資源節(jié)點(diǎn)（node）和超級(jí)節(jié)點(diǎn)（SP）。超級(jí)節(jié)點(diǎn)是性能評(píng)估參數(shù)較高的節(jié)點(diǎn)，為本聚類中的節(jié)點(diǎn)作為服務(wù)器運(yùn)作，代表對(duì)應(yīng)的資源分類。不同類型的SP之間采用P2P模式互連。每個(gè)node都在對(duì)應(yīng)的SP處進(jìn)行注冊(cè)。

有關(guān)資源節(jié)點(diǎn)基于語(yǔ)義相似度的聚類技術(shù)、資源與任務(wù)的匹配方法等在參考文獻(xiàn)[6]中有詳細(xì)介紹，本文不再贅述。

2.2 調(diào)度算法

先定義如下的參數(shù)：ti，j為任務(wù)i在資源節(jié)點(diǎn)j上的估計(jì)執(zhí)行時(shí)間。T為任務(wù)的截止期限與到達(dá)時(shí)間之差。ci，j為任務(wù)i在其他用戶資源節(jié)點(diǎn)j上的估計(jì)執(zhí)行費(fèi)用。C為任務(wù)的費(fèi)用上限。α+β=1；α≥0，β≥0。其中，α，β為用戶定義的時(shí)間和費(fèi)用偏好參數(shù)。

定義1 在語(yǔ)義匹配且截止期限和費(fèi)用上限均能滿足的情況下，資源j對(duì)于任務(wù)i的評(píng)價(jià)函數(shù)為：

超級(jí)節(jié)點(diǎn)將從符合要求的多個(gè)資源中選擇使目標(biāo)函數(shù)I最小的資源j作為任務(wù)i的調(diào)度目標(biāo)。

在本文的調(diào)度模型中，超級(jí)節(jié)點(diǎn)具有一定的智能，用戶向系統(tǒng)提交任務(wù)，如果任務(wù)能在該用戶所在社區(qū)執(zhí)行完成，就直接由該社區(qū)的超級(jí)節(jié)點(diǎn)調(diào)度完成任務(wù)的執(zhí)行。如果任務(wù)不能在該社區(qū)內(nèi)完成，就需要由該用戶所在的社區(qū)的超級(jí)節(jié)點(diǎn)與其他社區(qū)的超級(jí)節(jié)點(diǎn)協(xié)調(diào)，找到合適的社區(qū)完成任務(wù)的執(zhí)行。調(diào)度算法簡(jiǎn)要描述如下。

步驟1 用戶將網(wǎng)格任務(wù)提交給本地超級(jí)節(jié)點(diǎn)（SP），SP接收后，判斷其是否可以根據(jù)資源類型分解為子任務(wù)。

步驟 2 對(duì)于任一任務(wù)（元任務(wù)或者子任務(wù)），SP首先考慮其所需的資源類型是否對(duì)應(yīng)于本地類型，若是，則轉(zhuǎn)步驟3；否則，轉(zhuǎn)步驟 4。

步驟3 SP進(jìn)行本地集中式調(diào)度。對(duì)于語(yǔ)義匹配的資源節(jié)點(diǎn)，以定義1中的評(píng)價(jià)函數(shù)作為衡量目標(biāo)，擇優(yōu)調(diào)度，執(zhí)行交易，返回執(zhí)行結(jié)果給SP。

步驟4 SP進(jìn)行分布式遠(yuǎn)程調(diào)度。根據(jù)所需資源類型查找并發(fā)送任務(wù)至目標(biāo)SP，由其在對(duì)應(yīng)分組內(nèi)作集中式調(diào)度。對(duì)于匹配的資源節(jié)點(diǎn)，以定義1中的評(píng)價(jià)函數(shù)作為衡量目標(biāo)，擇優(yōu)調(diào)度，執(zhí)行交易，返回執(zhí)行結(jié)果至源SP。

步驟5不斷重復(fù)步驟2，直至協(xié)作型任務(wù)的所有子任務(wù)都執(zhí)行完畢。

一個(gè)超級(jí)節(jié)點(diǎn)的網(wǎng)格任務(wù)調(diào)度算法用偽代碼表示如下。

Super-peer scheduling algorithm

INPUT:grid task GT

OUTPUT:execution result of GT

Begin

While GT comes from local grid community do

If GT can decompose

Then according to resource classification,decompose it to subtasks with the QoS parameters;establish a dispatch list;

Else GT is called meta-task;

For every grid task GTi(GTiis a sub-task or meta-task)

If the local resource type can satisfy GTi,Super-peer.s search for the semantic matching node.k which also meets the following two requirements:

ArrivalTime(GTi)+ExecutedTime(GTi,Super-peer.s,node.k)DeadlineTime(GTi);//時(shí)間屬性要求

ExecutedCost(GTi,Super-peer.s,node.k)CostLimt(GTi);//費(fèi)用屬性要求

Then for allnode.k calculate the function I;

Seek for the smallest I and the corresponding node.k′;Allocate(GTi,Super-peer.s,node.k′);

If an error occurs to node.k′

Then SendResult0(GTi,Super-peer.s);//錯(cuò)誤報(bào)告，重調(diào)度

Else SendResult1(GTi,Super-peer.s);

Else Queuing(GTi,Peer-to-Peer Grid);

Search some Super-peer.t(t≠s)according to the resource type//超級(jí)節(jié)點(diǎn)之間分布式資源類型查詢

Send(GTi,Super-peer.t);

Endwhile

While GT comes from remote Super-peer.r

For every semantic matching node.l in Super-peer.s which also meets the following two requirements:

ArrivalTime(GT)+ExecutedTime(GT,Super-peer.s,node.l)DeadlineTime(GT);

ExecutedCost(GT,Super-peer.s,node.l)

CostLimt(GT);

Calculate the function I;Seek for the smallest I and the corresponding node.l′;

Allocate(GT,Super-peer.s,node.l′);

If an error occurs to node.l′

Then SendResult0 (GT,Super-peer.s,Super-peer.r);//重調(diào)度

Else SendResult1(GT,Super-peer.s,Super-peer.r);

Endwhile

End

設(shè)任務(wù)T被分解為n個(gè)子任務(wù)t1,t2,…,tn執(zhí)行，整個(gè)系統(tǒng)有m個(gè)網(wǎng)格社區(qū)。任務(wù)ti的執(zhí)行時(shí)間是由任務(wù)在網(wǎng)格社區(qū)里的某個(gè)節(jié)點(diǎn)的最大執(zhí)行時(shí)間決定的，設(shè)為max{ti}，則整個(gè)調(diào)度算法的時(shí)間復(fù)雜度為O(m·max{ti})。

3 網(wǎng)格調(diào)度的價(jià)格時(shí)延Petri網(wǎng)模型

有關(guān)Petri網(wǎng)、顏色Petri網(wǎng)的基本概念與性質(zhì)可以參考文獻(xiàn)[18,19]給出的價(jià)格時(shí)延Petri網(wǎng)的定義。

定義2 資源節(jié)點(diǎn)基于語(yǔ)義相似度聚類的超級(jí)節(jié)點(diǎn)模式網(wǎng)格任務(wù)調(diào)度對(duì)應(yīng)的全局Petri網(wǎng)模型是一個(gè)層次顏色 Petri網(wǎng)：HCPN=（P，S，T；F，C，W，M0，I）。具體解釋如下。

·P 是子網(wǎng)的集合，P={Super-peeri(SPi)/i=1，2，…，n}，n是超級(jí)節(jié)點(diǎn)的個(gè)數(shù)，Super-peeri(SPi)是第i個(gè)超級(jí)節(jié)點(diǎn)所對(duì)應(yīng)的局部子網(wǎng)。

·S 是庫(kù)所的集合，S={Si1，Si2/i=1，2，…，n}，n 是超級(jí)節(jié)點(diǎn)的個(gè)數(shù)，Si1是接收從遠(yuǎn)程超級(jí)節(jié)點(diǎn)發(fā)送來(lái)的信息的單元，Si2是向遠(yuǎn)程超級(jí)節(jié)點(diǎn)發(fā)送信息的單元。

·T 是變遷的集合，T={Tij/i，j=1，2，…，n，i≠j}，n 是超級(jí)節(jié)點(diǎn)的個(gè)數(shù)，Tij表示第i個(gè)超級(jí)節(jié)點(diǎn)的發(fā)送單元向第j個(gè)超級(jí)節(jié)點(diǎn)的接收單元發(fā)送消息。其中，每個(gè)變遷的時(shí)延、價(jià)格屬性均為0。

·F 是弧的集合，F(xiàn)哿（P×S，S×P，S×T，T×S）。

·C={（rt，dt，dc，α，β）}∪{τ，et，ct}∪{（gt，gs）}∪R 是顏色的集合，rt、dt、dc 分別是任務(wù)（子任務(wù)）的到達(dá)時(shí)間、截止期限、費(fèi)用上限。α、β分別是用戶規(guī)定的時(shí)間及費(fèi)用偏好參數(shù)。τ是變遷實(shí)施的時(shí)刻，et、ct是任務(wù)（元任務(wù)或者子任務(wù)）在各資源節(jié)點(diǎn)上執(zhí)行時(shí)所花費(fèi)的時(shí)間和費(fèi)用估計(jì)值。gt、gs分別是超級(jí)節(jié)點(diǎn)之間發(fā)送的任務(wù)信息及其執(zhí)行結(jié)果信息。R為資源類型集合。

·W為弧函數(shù)；M0是初始標(biāo)識(shí)；I是哨崗函數(shù)。

假設(shè)圖1中有代表4種不同類型資源的超級(jí)節(jié)點(diǎn)互連，則全局Petri網(wǎng)模型如圖2所示。

定義3 第i個(gè)超級(jí)節(jié)點(diǎn)Super-peeri(SPi)所對(duì)應(yīng)的局部子網(wǎng)包括兩個(gè)相互聯(lián)系的顏色、價(jià)格時(shí)延Petri網(wǎng)：集中式調(diào)度Petri網(wǎng)和分布式調(diào)度Petri網(wǎng)。

定義 4 集中式調(diào)度 Petri網(wǎng)：Super-peeriC={S，T；F，C，W，M0，I，Γ，D，E}。

·S 是庫(kù)所的集合，S={si/i=1，2，…，17}∪{（CIN，COUT）}，CIN為集中式調(diào)度子網(wǎng)接收來(lái)自分布式調(diào)度子網(wǎng)信息的單元，COUT為集中式調(diào)度子網(wǎng)向分布式調(diào)度子網(wǎng)發(fā)送信息的單元。

·T是變遷的集合；F是弧的集合；C是顏色的集合；W為弧的加權(quán)函數(shù)集合；M0是庫(kù)所的初始標(biāo)識(shí)集合；I是變遷的哨崗函數(shù)集合；T是變遷實(shí)施時(shí)刻的集合。

·D是定義在變遷集T上的時(shí)延函數(shù)，D（t）=a表示變遷的發(fā)生需要a單位時(shí)間來(lái)完成。

·E是定義在變遷集T上的價(jià)格函數(shù)，E（t）=b表示變遷的發(fā)生需要b單位費(fèi)用來(lái)完成。

圖3顯示了Super-peeri子網(wǎng)包含的集中式調(diào)度Petri網(wǎng)Super-peeriC。

圖2 網(wǎng)格調(diào)度全局層次Petri網(wǎng)HCPN模型

圖3 集中式調(diào)度Petri網(wǎng)Super-peer iC

為了簡(jiǎn)便，以下僅介紹圖3中變遷的含義，見(jiàn)表1。

表1 圖3中變遷的含義

定義 5 分布式調(diào)度 Petri網(wǎng)：Super-peeriD=（S，T；F，C，W，M0，I，Γ，D，E）。

其中，各元素的含義與定義4中類似。圖4顯示了Super-peeri子網(wǎng)包含的分布式調(diào)度Petri網(wǎng)Super-peeriD。圖中每個(gè)變遷的時(shí)延、費(fèi)用屬性均為0。為了簡(jiǎn)便，僅介紹圖4中庫(kù)所的含義，見(jiàn)表2。

圖4 分布式調(diào)度Petri網(wǎng)Super-peer iD

4 可達(dá)任務(wù)圖

定義6 網(wǎng)格調(diào)度全局Petri網(wǎng)HCPN模型的可達(dá)任務(wù)圖是一個(gè)有向圖 RTG（HCPN）=（V，E），其中 V 是由帶標(biāo)記的標(biāo)識(shí)組成的頂點(diǎn)集合，E是由帶標(biāo)記的連接頂點(diǎn)的有向邊所組成的邊集合。有向圖的構(gòu)造算法類似于參考文獻(xiàn)[16]中提出的算法。基于RTG(HCPN)，可以進(jìn)行時(shí)間和價(jià)格特性分析，根據(jù)每個(gè)任務(wù)上到達(dá)時(shí)間、截止期限、費(fèi)用上限等，得出整個(gè)調(diào)度的總時(shí)間和總價(jià)格成本。這樣，可在總體預(yù)算和時(shí)間的限度下進(jìn)行調(diào)度。根據(jù)有向圖RTG（HCPN）=（V，E）的時(shí)間和價(jià)格信息，分別可以得到對(duì)應(yīng)的AOE網(wǎng)Nt和Np，Nt和Np是一個(gè)帶權(quán)的有向無(wú)環(huán)圖，其中頂點(diǎn)表示事件，弧表示任務(wù)，權(quán)表示任務(wù)持續(xù)的時(shí)間或價(jià)格。以下算法給出了計(jì)算調(diào)度最長(zhǎng)時(shí)間或最大費(fèi)用的過(guò)程。

表2 圖4中庫(kù)所的含義

算法 根據(jù)AOE網(wǎng)計(jì)算調(diào)度的總時(shí)間和成本。

步驟1 根據(jù)AOE網(wǎng)求得各個(gè)頂點(diǎn)的最大入度。

步驟 2初始化堆棧S。

步驟 3將入度為零頂點(diǎn)入堆棧S，置這些入度為零的頂點(diǎn)的最長(zhǎng)時(shí)間ve(m)=0；//或最費(fèi)用為零。

步驟 4 While堆棧S不為空

從堆棧中彈出頂點(diǎn)i

其中，T為所有以i為頭的弧的集合，dut（）表示與弧對(duì)應(yīng)的活動(dòng)的持續(xù)時(shí)間頂點(diǎn)k的入度減1；

若頂點(diǎn)k的入度為零，則將頂點(diǎn)k入堆棧；步驟5 最后返回各頂點(diǎn)的最長(zhǎng)時(shí)間。

計(jì)算出的最長(zhǎng)實(shí)施時(shí)間和最大成本，可作為調(diào)度算法的依據(jù)之一。

命題1 設(shè) ne是 RTG(HCPN)中“端點(diǎn)”的個(gè)數(shù)，則系統(tǒng)的吞吐量為ne。

命題2 設(shè)etj為 RTG(HCPN)的第k個(gè)資源節(jié)點(diǎn)區(qū)域中標(biāo)注在執(zhí)行變遷tj邊上的時(shí)延分量，sek=∑etj，μ與s分別是序列{sek}的平均值與標(biāo)準(zhǔn)差，則離散系數(shù)v=s/μ可以用來(lái)判斷系統(tǒng)的負(fù)載平衡狀態(tài)。

命題3設(shè) Mk是RTG（HCPN）中的“端點(diǎn)”，ak、bk分別為Mk的時(shí)間、費(fèi)用標(biāo)識(shí)，則整個(gè)系統(tǒng)目前完成所有任務(wù)后所處的時(shí)刻為max{ak}，所消耗的總費(fèi)用為∑bk。

5 實(shí)例分析

假設(shè)在如圖5所示的網(wǎng)格計(jì)算環(huán)境中，節(jié)點(diǎn)a1和a2屬于SP1所代表的資源分組A類型網(wǎng)格社區(qū)；節(jié)點(diǎn)b1、b2、b3屬于SP2所代表的資源分組B類型網(wǎng)格社區(qū)；節(jié)點(diǎn)c1屬于SP3所代表的資源分組C類型網(wǎng)格社區(qū)；節(jié)點(diǎn)d1、d2屬于SP4所代表的資源分組D類型網(wǎng)格社區(qū)。有兩個(gè)相互之間獨(dú)立的協(xié)作型任務(wù) GT1、GT2分別在節(jié)點(diǎn) a1、c1提交，它們的子任務(wù)結(jié)構(gòu)如圖6所示。圓圈內(nèi)的數(shù)字表示第幾個(gè)子任務(wù)，字母表示所需的資源類型。

圖5 一個(gè)調(diào)度實(shí)例

圖6 協(xié)作型任務(wù)的子任務(wù)結(jié)構(gòu)

表3給出了這些任務(wù)（子任務(wù)）的達(dá)到時(shí)間、截止期限、費(fèi)用上限、時(shí)間/費(fèi)用權(quán)重；表4和表5分別給出了任務(wù)（子任務(wù)）在各資源節(jié)點(diǎn)上的估計(jì)執(zhí)行時(shí)間和估計(jì)執(zhí)行費(fèi)用。為了討論方便，假設(shè)與每個(gè)子任務(wù)對(duì)應(yīng)資源類型的網(wǎng)格節(jié)點(diǎn)均能滿足其語(yǔ)義匹配要求。根據(jù)這些參數(shù)和調(diào)度算法、Petri網(wǎng)模型、定義6，可以構(gòu)造出該系統(tǒng)網(wǎng)格調(diào)度對(duì)應(yīng)的Petri網(wǎng)可達(dá)任務(wù)圖RTG（HCPN），如圖7所示。

與參考文獻(xiàn)[16]對(duì)比，本文作了以下較大改進(jìn)。

·資源節(jié)點(diǎn)基于語(yǔ)義相似度預(yù)先分組聚類，能提高資源發(fā)現(xiàn)準(zhǔn)確率與效率。

·將網(wǎng)格調(diào)度的目標(biāo)由簡(jiǎn)單的元任務(wù)改為常見(jiàn)的協(xié)作型任務(wù)，協(xié)作型任務(wù)調(diào)度機(jī)制復(fù)雜。

·調(diào)度算法面向用戶時(shí)間、費(fèi)用及二者之間權(quán)重參數(shù)等多QoS約束，而不只是考慮單一的時(shí)間參數(shù)；引入市場(chǎng)機(jī)制，調(diào)度算法更能夠表征實(shí)際網(wǎng)格資源供需雙方的自私性，實(shí)現(xiàn)資源的優(yōu)化分配。

·建模工具價(jià)格時(shí)延Petri網(wǎng)相比于時(shí)延Petri網(wǎng)，功能更強(qiáng)大，能同時(shí)反映調(diào)度過(guò)程中產(chǎn)生的時(shí)延、價(jià)格問(wèn)題。

總之，本文的研究更加全面、系統(tǒng)和科學(xué)。

下面結(jié)合表3～表5及可達(dá)任務(wù)圖進(jìn)行詳細(xì)的調(diào)度分析。

（1）網(wǎng)格任務(wù)GT1、GT2均為協(xié)作型任務(wù)，都需要多種類型的資源協(xié)同配合才能完成。對(duì)于任務(wù)GT1，需要3種類型的資源：A、B、D。SP1接收到任務(wù)后，按照資源類型將其分解為 GT1-1、GT1-2、GT1-33個(gè)子任務(wù)。對(duì)于子任務(wù) GT1-1，其需求的資源類型為A，屬于SP1所管理的網(wǎng)格社區(qū)。由于a1是GT1的提交節(jié)點(diǎn)，故a1對(duì)應(yīng)于GT1-1的執(zhí)行費(fèi)用為0。SP1進(jìn)行集中式查詢發(fā)現(xiàn)，a1、a2均能滿足GT1-1的時(shí)間、費(fèi)用等QoS參數(shù)的要求，計(jì)算a1、a2相對(duì)于子任務(wù)GT1-1的資源評(píng)價(jià)函數(shù)，發(fā)現(xiàn)a1優(yōu)于a2，故a1是GT1-1的調(diào)度目標(biāo)。其執(zhí)行完成后所處的時(shí)刻為25，也是GT1-2的開(kāi)始調(diào)度時(shí)刻；對(duì)于GT1-2，需要資源類型為B的資源，SP1將其發(fā)送給SP2進(jìn)行分布式調(diào)度。由于其3次循環(huán)后的時(shí)刻不能超過(guò)120，故每次執(zhí)行時(shí)間不能超過(guò)在網(wǎng)格社區(qū)B中，同時(shí)滿足其時(shí)間、費(fèi)用QoS參數(shù)要求的只有b2一個(gè)節(jié)點(diǎn)，SP2調(diào)度GT1-2到b2上執(zhí)行。GT1-2執(zhí)行完成后，所處的時(shí)刻為115，累積費(fèi)用消耗為 72；對(duì)于 GT1-3，將被發(fā)送到 SP4進(jìn)行分布式調(diào)度。其執(zhí)行時(shí)間不能超過(guò)160-115=45，d1、d2均能滿足其QoS參數(shù)要求。SP4計(jì)算它們的資源評(píng)價(jià)函數(shù)，Id1=為GT1-3的調(diào)度目標(biāo)。當(dāng)GT1-3執(zhí)行完成后，GT1便執(zhí)行完畢。GT1執(zhí)行完畢后，所處的時(shí)刻為155，消耗的總執(zhí)行時(shí)間為155，總費(fèi)用為112。

圖7 網(wǎng)格調(diào)度Petri網(wǎng)模型的可達(dá)任務(wù)圖

表3 網(wǎng)格任務(wù)（子任務(wù)）的QoS約束

表4 網(wǎng)格任務(wù)（子任務(wù)）的執(zhí)行時(shí)間估計(jì)值

表5 網(wǎng)格任務(wù)（子任務(wù)）的執(zhí)行費(fèi)用估計(jì)值

對(duì)于GT2，因其費(fèi)用權(quán)重為0.7，用戶更看重執(zhí)行費(fèi)用。SP3接收GT2后，按照其對(duì)資源類型的要求將其分解為4個(gè)具有相互依賴關(guān)系的子任務(wù)：GT2-1、GT2-2、GT2-3、GT2-4。對(duì)于GT2-1，需要A類型的資源，SP3將其發(fā)送給SP1，其開(kāi)始時(shí)刻為60，截止期限為100，故執(zhí)行時(shí)間不能超過(guò)40。SP1進(jìn)行集中式查詢發(fā)現(xiàn)，a1、a2均能滿足GT2-1的時(shí)間、費(fèi)用等QoS參數(shù)要求，計(jì)算a1、a2相對(duì)于子任務(wù)GT2-1的資源評(píng)價(jià)函數(shù)，發(fā)現(xiàn)a2優(yōu)于a1，故a2是GT2-1的調(diào)度目標(biāo)。GT2-1執(zhí)行完成后所處的時(shí)刻為 60+38=98；此后，因 GT2-2、GT2-3是并行任務(wù)且分別需要B類型和C類型的資源，故可以在SP2、SP3處進(jìn)行并行調(diào)度。對(duì)于GT2-2，SP2進(jìn)行集中式查詢發(fā)現(xiàn)b1、b2能滿足其QoS參數(shù)要求且b1的資源評(píng)價(jià)函數(shù)優(yōu)于b2，GT2-2被調(diào)度到b1上執(zhí)行；對(duì)于GT2-3，SP3管理的社區(qū)中只有c1一個(gè)節(jié)點(diǎn)且它是GT2的提交節(jié)點(diǎn)，對(duì)應(yīng)于GT2-3的執(zhí)行費(fèi)用為0。它能在截止期限內(nèi)完成子任務(wù)GT2-3、GT2-3被調(diào)度到c1上執(zhí)行；只有當(dāng)GT2-2、GT2-3都順利執(zhí)行完成后，GT2-4才能獲得調(diào)度機(jī)會(huì)，此時(shí)刻為60+38+92=190。由于其截止期限為240，故其執(zhí)行時(shí)間限制為240-190=50，它需要D類型的資源，SP4管理的社區(qū)中只有d2能滿足其QoS參數(shù)要求，GT2-4被調(diào)度到d2節(jié)點(diǎn)上執(zhí)行。當(dāng)GT2-4執(zhí)行完成后，GT2便執(zhí)行完畢。GT2執(zhí)行完畢后，所處的時(shí)刻為238，消耗的總執(zhí)行時(shí)間為178，總費(fèi)用為94。

（2）資源節(jié)點(diǎn) a1、a2、b1、b2、b3、c1、d1、d1執(zhí)行所有任務(wù)（子任務(wù)）所用的時(shí)間分別為：se1=25，se2=38，se3=28，se4=90，se5=0，se6=92，se7=40，se8=48。它們的平均數(shù)為 μ=45.1，標(biāo)準(zhǔn)差S=29.6，離散系數(shù)v==0.66。由命題5知，系統(tǒng)目前的負(fù)載平衡狀態(tài)較差，主要是因?yàn)槟壳敖y(tǒng)計(jì)的時(shí)間段短，子任務(wù)數(shù)量比較少，以致資源節(jié)點(diǎn)忙閑程度不同。相信在長(zhǎng)時(shí)間的觀察統(tǒng)計(jì)中，系統(tǒng)的負(fù)載平衡特性會(huì)處于良好狀態(tài)。

（3）可達(dá)任務(wù)圖有 2 個(gè)端點(diǎn)：M112、M213。系統(tǒng)的吞吐量為2。目前整個(gè)系統(tǒng)執(zhí)行完所有任務(wù)后所處的時(shí)刻為max{155，238}=238，所消耗的總費(fèi)用為：112+94=206。

6 結(jié)束語(yǔ)

本文針對(duì)資源節(jié)點(diǎn)基于語(yǔ)義相似度聚類的超級(jí)節(jié)點(diǎn)模式網(wǎng)格，提出網(wǎng)格協(xié)作型任務(wù)的面向用戶時(shí)間、費(fèi)用及二者偏好參數(shù)等多QoS約束的調(diào)度算法，并運(yùn)用價(jià)格時(shí)延Petri網(wǎng)對(duì)調(diào)度過(guò)程進(jìn)行建模，構(gòu)造并分析可達(dá)任務(wù)圖，實(shí)例驗(yàn)證算法的有效性。將子任務(wù)的傳輸過(guò)程、資源分配狀況以及每一步產(chǎn)生的時(shí)延、費(fèi)用等信息通過(guò)標(biāo)識(shí)的形式反映在可達(dá)任務(wù)圖中，便于觀察、統(tǒng)計(jì)及分析任務(wù)的詳細(xì)調(diào)度過(guò)程。下一步的工作重點(diǎn)是進(jìn)一步優(yōu)化調(diào)度算法。

參考文獻(xiàn)

1 Kurve A,Griffin C,Miller D J,et al.Optimizing cluster formation in super-peer networks via local incentive design.Peer-to-Peer Networking and Applications,2013(4)

2 Liu M R,Koskela T,Ou Z H,et al.Super-peer-based coordinated service provision.Journal of Network and Computer Applications,2011,34(4):1210～1224

3 Hassan M I,Abdullah A.Semantic-based grid resource discovery systems a literature review and taxonomy.Proceedings of International Symposium in Information Technology(ITSim),Kuala Lumpur,June 2010

4 吳健，吳朝暉，李瑩等.基于本體論和詞匯語(yǔ)義相似度的Web服務(wù)發(fā)現(xiàn).計(jì)算機(jī)學(xué)報(bào)，2005，28(4):595～602

5 曹潔，曾國(guó)蓀，鈕俊等.云環(huán)境下可用性感知的并行任務(wù)調(diào)度方法.計(jì)算機(jī)研究與發(fā)展，2013，50(7):1563～1572

6 倪晚成，劉連臣，吳澄等.基于概念關(guān)聯(lián)程度的網(wǎng)格服務(wù)組合方法.清華大學(xué)學(xué)報(bào)，2007，7(40):1581～1585

7 Tan Y H,LüK,Lin Y P.Organisation and management of shared documents in super-peer networks based semantic hierarchical cluster trees. Peer-to-Peer Networking and Applications,2012,5(3):292～308

8 Garbacki P,Epema D H J,Steen M.The design and evaluation of a self-organizing superpeer network.IEEE Transactions on Computers,2010,59(3):317～331

9 Doulkeridis C,Vlachou A,Norvag K,et al.Efficient search based on content similarity over self-organizing P2P networks.Peer-to-Peer Networking and Applications,2009,3(1):67～79

10 Ayorak E,Bener A B.Super peer web service discovery architecture.Proceedings of IEEE the 23rd International Conference on Data Engineering,Istanbul,Turkey,2007:1360～1364

11 朱海，王宇平.融合安全的網(wǎng)格依賴任務(wù)調(diào)度雙目標(biāo)優(yōu)化模型及算法.軟件學(xué)報(bào)，2011，22(11)

12 Li J,Vuong S.A scalable semantic routing architecture for grid resource discovery.Proceedingsofthe 11th InternationalConference on Paralleland Distributed Systems,Fukuoka,Japan,2005:29～35

13 Lser A,Naumann F,Siberski W,et al.Semantic overlay clusters within super-peer networks.Databases,Information Systems and Peer-to-Peer Computing,2004(2944):35～38

14 Hassan M I,Abdullah A.A semantic description and registration framework for large grid resource discovery systems.Computer Science Letters,2009,1(1)

15 Hassan M I,Abdullah A.A new grid resource discovery framework.The International Arab Journal of Information Technology,2011,8(1):99～107

16 熊曾剛，楊揚(yáng)，曾明.基于Petri網(wǎng)的兩階段網(wǎng)格任務(wù)調(diào)度模型與分析.通信學(xué)報(bào)，2009，30(8):69～77

17 孫瑞志，楊璐，歐陽(yáng)婭.基于改進(jìn)遺傳算法的網(wǎng)格任務(wù)調(diào)度.解放軍理工大學(xué)學(xué)報(bào)（自然科學(xué)版），2012，13(4)

18 Jensen K.Colored Petri Nets:Basic Concepts,Analysis Methods and Practical Use.Berlin:Springer,1996

19 劉衛(wèi)東，宋佳興，林闖.基于價(jià)格時(shí)間Petri網(wǎng)的網(wǎng)格計(jì)算應(yīng)用模型及分析.電子學(xué)報(bào)，2005，33（8）： 1416～1420