[發明專利]基于可靠性和非合作博弈的計算網格任務調度方法

有效

• 申請號: 201210158071.5
• 申請日: 2012-05-21
• 公開（公告）號: CN102736955A
• 公開（公告）日: 2012-10-17
• 發明（設計）人: 王勇;李凱;劉美林
• 申請（專利權）人: 北京工業大學
• 主分類號: G06F9/50
• 分類號: G06F9/50
• 代理公司: 北京思海天達知識產權代理有限公司 11203
• 代理人: 樓艮基

1.基于可靠性和非合作博弈的計算網格任務調度方法，其特征在于含有以下步驟：

步驟（1），構造一個基于可靠性和非合作博弈的計算網格系統：

所述基于可靠性和非合作博弈的計算網格系統由用戶、面向各用戶的各調度器i以及面向各調度器i的網格計算節點j以及調度方案計算器組成，其中i=1,2，..,n，n為所述系統中所有調度器的數目，j=1,2，...,m，m為所述系統中所有網格計算節點的數目；

在忽略調度器內部處理代價、任務傳輸時間下，所述調度器在進行任務分片時的可靠性條件如下：

各個調度器從各用戶接受任務，各個調度器發出任務的平均速率λ_i的加和應該小于所述系統所有網格計算節點對任務的平均執行速率u_j的加和，速率的單位是單位時間內的任務數，下同：

Σi=1nλi<Σj=1muj---(1)]]>

；

各個所述調度器發到第j個所述網格計算節點上任務分片的速率的加和應該小于第j個所述網格計算節點對所述任務分片的執行速率u_j，即計算能力：

Σi=1nλiaij<uj---(2)]]>

；

步驟（2），網格計算節點j的穩定狀態的提供能力A_j,0<A_j<1：

A_j=1-δ_jβ_1j(1+u′_jγ_j)???????????????????????（3）

其中A_j針對的是網格計算節點j的提供能力，其中j＝1,2,...,m，δ_j為網格計算節點j的平均任務到達速率，到達網格計算節點j的任務滿足以δ_j為均值的泊松分布，β_1j為網格計算節點j任務服務時間的均值，u′_j為網格計算節點j忙時失敗的平均速率，γ_j為網格計算節點j的重試時間的均值；

根據網格計算節點的數量，調度器i將用戶的請求分解為所述m個任務分片，a_ij為第i個調度器的任務分配到第j個網格計算節點的比例，滿足以下的約束：

a_ij≥0且Σj=1maij=1---(4)]]>

；

步驟（3），調度方案計算器按下式計算所述所有調度器將任務分片到所述網格計算節點j上后，第j個網格計算節點的提供能力：

Aj=1-Σi=1n(λiaij)β1j(1+uj′γj)---(5)]]>

其中，j=1,2，..,n；

步驟（4），調度方案計算器以該系統中所述網格計算節點提供的計算能力倒數之和作為目標函數確定任務分片方案：

D=Σj=1m11-Σi=1n(λiaij)β1j(1+uj′γj)---(6)]]>

；

步驟（5），調度方案計算器按照以下步驟計算所述調度器的任務分片方案：

為了便于算法步驟的說明，定義u_ji為網格計算節點j為調度器i提供

的計算能力，u_j為網格計算節點j的計算能力，代入（6）式可得式（7）：

D=Σj=1m11-(λiaij+uj-uji)β1j(1+uj′γj)---(7)]]>

；

步驟（5.1），系統參數初始化：

設網格系統中調度器的個數為n，網格計算節點個數為m，調度器i發出任務的平均速率為λ_i(0)，網格計算節點j的任務平均處理速率u_j(0)，其中i＝1,2,...,n，j=1,2,...,m；系統中各個調度器和網格計算節點將上述初始值發送給調度方案計算器，以下步驟均由調度方案計算器完成；將調度器i的任務分片方案初始化為：

ai(0)={ai1(0),ai2(0),...,aim(0)}={1m,1m,...,1m},]]>設uj′(0)=uj(0)10,]]>γj(0)=5uj(0),]]>目標函數值誤差精度ε(0)=1；

步驟（5.2），利用步驟（4）中的公式計算初始條件下的目標函數值latterD；

步驟（5.3），判斷ε是否滿足指定的誤差要求ε≤10^-6，不滿足，循環執行以下步驟（5.4）~（5.15），否則得到調度方案a，結束循環；

步驟（5.4），令formerD=latterD，formerD用于暫存前一次調度方案下的目標函數值；

步驟（5.5），根據程序中的初值，利用公式求取u_ji；

步驟（5.6），利用式θij=(1+uj′γj)β1jλi(1-(1+uj′γj)β1j(uj-uji))2]]>求取θ_ij，并將θ_ij從小到大排序，

排序的結果保存到變量index中；

步驟（5.7），對i從1到n，依次執行步驟（5.8）~（5.14）：

步驟（5.8），令d_i從m到1，依次執行步驟（5.9）~（5.11）：

步驟（5.9），利用下述式（8）求取α；

步驟（5.10），利用下述式(9)求取j從1到d_i的a_i,index(i,j)，j從(d_i+1)到m的剩余網格節點的a_i,index(i,j)賦值為0，其中d_i≤m；

步驟（5.11），若存在a_ij不滿足0≤a_ij≤1則d_i減1，返回到步驟（5.9），否則往下執行；

步驟（5.12），利用求得的a_ij修改u_ji；

步驟（5.13），利用θij=(1+uj′γj)β1jλi(1-(1+uj′γj)β1j(uj-uji))2]]>求取θ_ij，并對θ_ij從小到大排序，

排序的結果保存到變量index中；

步驟（5.14），令i＝i+1,返回到步驟（5.8），其中i≤n；

步驟（5.15），利用公式D=Σj=1m11-Σi=1n(λiaij)β1j(1+uj′γj)]]>求得a修改后的目標函數值latterD，ε=|formerD-latterD|，返回到步驟（5.3）；

上述算法中的式（8）為：

α=(Σj=1di1Windex(i,j)Σj=1di1-Windex(i,j)(μindex(i,j)-μindex(i,j),i)Windex(i,j)λi-1)21λi---(8)]]>

其中，W_index(i,j)=(1+μ′_index(i，j)γ_index(i,j))β_{1,inedex(i,j)}）；

式中α為分配臨界因子，是調度器i判斷是否向某個網格計算節點分配任務的界限值，index(i,j)代表第i個調度器向系統中網格計算節點分配任務時，以θ_ij對網格計算節點從小到大排序后排在第j個位置的節點；

上述算法中的式（9）為：

aij=1-(1+uj′γj)β1j(uj-uji)-(1+uj′γj)β1jλiα(1+uj′γj)β1jλi---(9)]]>

其中式（9）中的j=index(i,j)，為在該調度算法中用于調度器i確定任務分向第index(i,j)個網格計算節點的比例；

上述公式θ_ij為任務可分配調節因子，是第i個調度器判斷是否向網格計算節點j分配任務的依據，若θ_ij>α，調度器i不會向網格計算節點j分配任務，即a_ij=0。