[發(fā)明專利]一種移動云環(huán)境下的工作流優(yōu)化方法

有效

• 申請?zhí)枺?/td>: 201810095728.5
• 申請日: 2018-01-31
• 公開（公告）號: CN108416465B
• 公開（公告）日: 2021-08-31
• 發(fā)明（設計）人: 袁友偉;劉恒初;俞東進;鄢臘梅;李萬清
• 申請（專利權）人: 杭州電子科技大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/06;G06Q50/06;G06N3/12
• 代理公司: 浙江永鼎律師事務所 33233
• 代理人: 雷仕榮

1.一種移動云環(huán)境下的工作流優(yōu)化方法，其特征在于，包括以下步驟：

步驟S1：對用戶提交的工作流進行預處理；

步驟S2：構建移動云環(huán)境下的工作流模型；

步驟S3：基于改進遺傳算法生成工作流最優(yōu)調度方案；

步驟S4：根據(jù)調度結果分配任務至移動云中的設備；

其中，所述步驟S1進一步包括以下步驟：

步驟S11：根據(jù)工作流傳輸代價權值對工作流傳輸代價過大節(jié)點進行合并；

步驟S12：移動云環(huán)境設備調用電壓調整技術調節(jié)設備最合適電壓頻率；

所述步驟S11進一步包括以下步驟：

(1)根據(jù)Trans_P矩陣計算權值τ；

(2)根據(jù)任務存在先后順序，且其傳輸能力高于權值τ，則將任務分配到同一個處理器上；

其中，工作流中節(jié)點合并參考權值計算公式為：

上式中，m表示移動設備的個數(shù)，Trans_P[i][j]表示處理器p_i到p_j的數(shù)據(jù)傳輸能力；

所述步驟S12中，電壓頻率的計算公式如下：

其中f表示移動云端設備的電壓頻率，V_dd表示系統(tǒng)所支持的電壓，V_ts表示系統(tǒng)電壓閾值，L_d表示工作流執(zhí)行的最短時間，Z和β表示一個常量；

所述步驟S2進一步包括以下步驟：

移動云環(huán)境下工作流的任務集合通過一個邊帶權重的有向無環(huán)圖表示G＝{T，E，P}，其中T＝{t₁，t₂...，t_n}是包含N個任務的集合，E＝{(i，j)|t_it_j}是各任務間的先序約束，即t_j不能在t_i完成之前開始,P＝{p₁,p₂,...,p_mc}表示在移動云端部署的設備；優(yōu)化條件中包括{Tim，Ene，R}，其中Tim，Ene，R分別表示用戶對時間、能量消耗和可靠性的用戶需求值；

上述模型中的mc和n分別代表集群中所使用的處理器個數(shù)和任務集中的任務個數(shù)，其中每個設備都支持動態(tài)電壓頻率調整技術，i，j均表示任務編號，因此1≤i，j≤n；

所述步驟S3進一步包括以下步驟：

步驟S31：在對工作流進行編碼后需要計算新種群各個體的適應值，其適應值的計算公式為：

其中，f(n,mr)表示在該調度方案的適應值，R_n,mr表示該任務n在設備mr上的可靠性，R_high表示調度方案中最大可靠性，R_low表示調度方案中最小可靠性，E_n,mr表示該任務n在設備mr上的能源消耗，E_normal表示設備在不采用動態(tài)電壓頻率調整技術時產生的能源消耗,ψ₁和ψ₂表示兩個常量，且ψ₁+ψ₂＝1；

步驟S32：劃分種群，其劃分依據(jù)為：

計算所得各個體的適應值，適應值越大則視為該個體越優(yōu)秀，因此將調度方案按照適應度降序的劃分歸入精英組和普通組；

步驟S33：對種群進行交叉、變異操作，其具體操作如下：

在交叉操作中，對種群中的兩兩個體節(jié)點依次進行單節(jié)點交換，得到新的個體，根據(jù)適應值選擇其中適應值較高的個體，作為新解；

在變異操作中，首先依據(jù)概率在種群中分離出需要變異的集合，依次對集合中的個體上的單節(jié)點進行變異操作，得到新的個體，根據(jù)適應值選擇其中適應值較高的個體，作為新解。

2.根據(jù)權利要求1所述的移動云環(huán)境下的工作流優(yōu)化方法，其特征在于，

所述步驟S4進一步包括：

在預先設定的迭代次數(shù)范圍內，連續(xù)迭代后，產生的新種群中可靠性、完成時間、能源消耗符合用戶預期，依據(jù)得到的調度方案對任務與設備進行映射并分配移動云設備合適的電壓頻率。

3.根據(jù)權利要求1或2所述的移動云環(huán)境下的工作流優(yōu)化方法，其特征在于，

所述步驟S1中，本地設備電壓頻率由設備電壓及設備制作工藝決定，通過合理分配電壓頻率至移動端設備以減少設備能源消耗。