[發明專利]一種云環境下收益驅動的大規模處理任務調度方法

無效

• 申請號: 201210525859.5
• 申請日: 2012-12-07
• 公開（公告）號: CN103019822A
• 公開（公告）日: 2013-04-03
• 發明（設計）人: 蘇森;雙鍇;李健;徐鵬;王玉龍
• 申請（專利權）人: 北京郵電大學
• 主分類號: G06F9/46
• 分類號: G06F9/46;G06F9/455
• 代理公司: 北京思創畢升專利事務所 11218
• 代理人: 郭韞

1.一種云環境下收益驅動的大規模處理任務調度方法，其特征在于：所述方法包括以下步驟：

步驟1：讀入大規模圖狀數據處理任務圖，按照圖狀結構任務的層次關系對所述大規模圖狀數據處理任務圖進行遍歷，按照層次進行任務序號標記，并計算任務的總數n；

步驟2：讀入當前云計算環境的虛擬機的性能和計價模式；

步驟3：初始化m個粒子的編碼以及各個粒子的位置X_i和飛行速度V_i，設最大迭代次數設為T；

步驟4：根據粒子的當前的編碼利用下面的適應度函數計算所有粒子的適應度函數值f(X_i)：

minα·T′-TminTmax-Tmin+(1-α)·C′-CminCmax-Cmin]]>

其中T’表示當前策略的任務調度長度，C’表示當前策略的資源租賃成本，T_min和T_max分別表示當前解集中最小和最大的任務調度長度，C_min和C_max分別表示當前解集中最小和最大的資源租賃成本，系數α用以反應調度長度和資源租賃成本之間均衡關系，α∈[0，1]；α值變小將得到資源租賃成本較小但調度長度延長的調度方案；

通過迭代式搜索不同的α值構造Pareto最優解集；

在上述迭代過程中，將當前值和上一次結果進行比較獲得個體極值X_pb，選取個體極值中最小的作為全局極值X_gb；

步驟5：根據粒子的適應度函數值f(X_i)進行速度更新和位置更新；

步驟6：對每個粒子，將其適應度函數值f(X_i)與步驟4得到的個體極值X_pb進行比較，然后將兩者中較小的值作為新的個體極值；將其適應度函數值f(X_i)與步驟4得到的全局極值X_gb進行比較，然后將兩者中較小的值作為新的全局極值，則更新當前的全局極值；

步驟7：判斷是否達到最大迭代次數T，如果是，則停止計算，轉入步驟8；如果否，則返回步驟5；

步驟8：輸出大規模圖狀數據處理任務調度方案。

2.根據權利要求1所述的云環境下收益驅動的大規模處理任務調度方法，其特征在于：所述步驟3中所述粒子的位置對應于待解決問題的一個潛在解，粒子的速度指導其在迭代過程中向最優解運動的方向。

3.根據權利要求1所述的云環境下收益驅動的大規模處理任務調度方法，其特征在于：所述步驟5具體如下：

利用下式進行速度更新：

Vi(t+1)=P1Vi(t)⊕P2(XpbΘXi(t))⊕P3(XgbΘXi(t))]]>

其中，t表示迭代次數，X_i(t)表示粒子第t次迭代時所處的位置，V_i(t)為對應第t次迭代時所處的位置的飛行速度，P₁是粒子取當前速度的概率，P₂是粒子取局部最優速度的概率，P₃是粒子取全局最優速度的概率，且P₁+P₂+P₃＝1；

利用下式進行位置更新，位置更新中隨機選取云計算中候選虛擬機列表：

Xi(t+1)=Xi(t)⊗Vi(t+1)]]>

其中，Θ用于計算兩種映射方案的差異性，如果映射方案X_i和X_j在同一維上具有相同的值，則差值的結果為1，否則為0；

用于粒子更新過程中，通過跟蹤自身最優位置和全局最優位置來更新自身的速度，即在粒子的對應維度上以P_i的概率按照V_i各維度的值更新和以P_j的概率按照V_j各維度的值更新；

用于粒子根據當前速度更新位置，即當前位置X_i按照V_j的策略對當前大規模圖狀數據處理任務調度策略進行調整。