[發(fā)明專利]基于量子被囊群搜索機(jī)制的云計(jì)算任務(wù)調(diào)度方法

有效

• 申請(qǐng)?zhí)枺?/td>: 202210091586.1
• 申請(qǐng)日: 2022-01-26
• 公開（公告）號(hào): CN114510330B
• 公開（公告）日: 2023-06-02
• 發(fā)明（設(shè)計(jì)）人: 高洪元;狄妍岐;程建華;陳夢晗;趙英琪;劉亞鵬;趙立帥;郭瑞晨;劉凱龍
• 申請(qǐng)（專利權(quán)）人: 哈爾濱工程大學(xué)
• 主分類號(hào): G06F9/48
• 分類號(hào): G06F9/48;G06F9/455;G06F9/50;G06N3/006;G06N10/60
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發(fā)明提供基于量子被囊群搜索機(jī)制的云計(jì)算任務(wù)調(diào)度方法，包括：根據(jù)任務(wù)與虛擬機(jī)的分配矩陣，構(gòu)建任務(wù)在虛擬機(jī)上的執(zhí)行時(shí)間矩陣和執(zhí)行成本矩陣并構(gòu)建數(shù)學(xué)模型；初始化被囊群搜索機(jī)制的量子位置并設(shè)定參數(shù)；計(jì)算每只被囊的適應(yīng)度值，根據(jù)每只被囊的適應(yīng)度值將全部被囊進(jìn)行排序；根據(jù)被囊群搜索機(jī)制產(chǎn)生量子旋轉(zhuǎn)角，使用模擬的簡化量子旋轉(zhuǎn)門更新被囊的量子位置；應(yīng)用貪心策略，確定新一代被囊群的量子位置，根據(jù)適應(yīng)度值將全部被囊進(jìn)行排序；判斷是否達(dá)到最大迭代次數(shù)G，若未達(dá)到，令g＝g+1，返回步驟四；若達(dá)到，則終止迭代循環(huán)，根據(jù)最后一代中的最優(yōu)量子位置的映射位置所對(duì)應(yīng)的任務(wù)與虛擬機(jī)的分配矩陣得到最終的任務(wù)調(diào)度策略。

技術(shù)領(lǐng)域

本發(fā)明涉及一種云計(jì)算應(yīng)用環(huán)境中基于量子被囊群搜索機(jī)制的有約束任務(wù)調(diào)度方法，屬于云計(jì)算領(lǐng)域。

背景技術(shù)

任務(wù)調(diào)度問題是云計(jì)算領(lǐng)域中的研究熱點(diǎn)。云計(jì)算為用戶提供了基礎(chǔ)設(shè)施、平臺(tái)、軟件三類服務(wù)。隨著云計(jì)算的發(fā)展和普及，云計(jì)算的用戶數(shù)量逐步增多，任務(wù)的數(shù)量越來越多，如何兼顧各種性能的需求，對(duì)任務(wù)進(jìn)行合理的調(diào)度，提高任務(wù)分配的效率和資源的利用率，是云計(jì)算研究的重點(diǎn)。

常見的云計(jì)算調(diào)度算法有Min-Min、Max-Min算法等，這些算法使用相對(duì)簡單的策略進(jìn)行任務(wù)調(diào)度的工作，但隨著云計(jì)算技術(shù)的發(fā)展，云計(jì)算不僅要滿足用戶的多個(gè)目標(biāo)需求，如低成本，較小的任務(wù)完成時(shí)間等，保障用戶服務(wù)質(zhì)量，還要兼顧數(shù)據(jù)中心的整體能耗、資源利用率、經(jīng)濟(jì)效益等，保障資源提供者的利益。因此云計(jì)算需要同時(shí)兼顧各種性能的需求，云計(jì)算調(diào)度問題具有離散優(yōu)化和多目標(biāo)優(yōu)化的共同特征，適合采用優(yōu)化算法來求解。現(xiàn)有一些國內(nèi)外學(xué)者已經(jīng)將遺傳算法、粒子群算法、蟻群算法等優(yōu)化算法應(yīng)用在云計(jì)算任務(wù)調(diào)度上，但很多基于智能算法的任務(wù)調(diào)度方法存在不同程度的缺陷，如收斂速度慢，易陷入局部最優(yōu)值等，且大多數(shù)算法都只考慮一個(gè)指標(biāo)，如最小化任務(wù)的總完成時(shí)間，但忽視了最小化任務(wù)總完成時(shí)間的同時(shí)，任務(wù)的執(zhí)行成本也會(huì)增加。

通過對(duì)現(xiàn)有文獻(xiàn)的檢索發(fā)現(xiàn)，周靜等在《計(jì)算機(jī)學(xué)報(bào)》上發(fā)表的“基于入侵腫瘤生長優(yōu)化的云計(jì)算調(diào)度算法”中，對(duì)入侵腫瘤生長優(yōu)化算法進(jìn)行了一定的改進(jìn)和提高，并把它應(yīng)用到云計(jì)算任務(wù)調(diào)度問題中，此算法在縮短任務(wù)完成時(shí)間上有一定的效果，但只考慮了時(shí)間這一個(gè)優(yōu)化目標(biāo)，沒有考慮其他約束條件。魏赟等在《計(jì)算機(jī)工程》上發(fā)表的“基于改進(jìn)蟻群算法的云計(jì)算任務(wù)調(diào)度模型”中，采用改進(jìn)的蟻群算法，在效率和公平性的前提下，一定程度的縮短了任務(wù)的延遲時(shí)間，但忽視了成本這一關(guān)鍵指標(biāo)。

綜上所述，現(xiàn)有的云計(jì)算任務(wù)調(diào)度方法大多只考慮時(shí)間這一個(gè)關(guān)鍵指標(biāo)，沒有全面考慮云計(jì)算應(yīng)用環(huán)境中任務(wù)調(diào)度復(fù)雜多變的應(yīng)用需求，在最小化任務(wù)總完成時(shí)間的同時(shí)，任務(wù)的執(zhí)行成本會(huì)增加，只考慮時(shí)間這一指標(biāo)不能合理反映云服務(wù)的服務(wù)質(zhì)量。且現(xiàn)有智能優(yōu)化算法大多存在計(jì)算復(fù)雜度高，收斂速度較慢，容易陷入局部最優(yōu)值等問題。因此提出了基于量子被囊群搜索機(jī)制的云計(jì)算任務(wù)調(diào)度方法，保證了成本在一個(gè)要求的預(yù)算范圍內(nèi)，達(dá)到了較小的任務(wù)總完成時(shí)間。解決了現(xiàn)有的云計(jì)算任務(wù)調(diào)度方法只考慮時(shí)間這一指標(biāo)，沒有兼顧時(shí)間與成本的問題。

發(fā)明內(nèi)容

針對(duì)現(xiàn)有云計(jì)算任務(wù)調(diào)度方法的缺點(diǎn)和不足，本發(fā)明設(shè)計(jì)了具有懲罰機(jī)制的目標(biāo)函數(shù)和單鏈編碼的量子被囊群搜索機(jī)制去實(shí)現(xiàn)有約束的云計(jì)算任務(wù)調(diào)度方法，保證了成本在一個(gè)要求的預(yù)算范圍內(nèi)，最小化任務(wù)的總完成時(shí)間，算法收斂性較好，在要求的成本約束下，實(shí)現(xiàn)了較小的任務(wù)的總完成時(shí)間，提高了云計(jì)算資源的利用率，突破了現(xiàn)有方法的局限。

本發(fā)明的目的是這樣實(shí)現(xiàn)的：步驟如下：

步驟一：根據(jù)任務(wù)與虛擬機(jī)的分配矩陣，構(gòu)建任務(wù)在虛擬機(jī)上的執(zhí)行時(shí)間矩陣和執(zhí)行成本矩陣并構(gòu)建數(shù)學(xué)模型；

步驟二：初始化被囊群搜索機(jī)制的量子位置并設(shè)定參數(shù)；

步驟三：計(jì)算每只被囊的適應(yīng)度值，根據(jù)每只被囊的適應(yīng)度值將全部被囊進(jìn)行排序；

步驟四：根據(jù)被囊群搜索機(jī)制產(chǎn)生量子旋轉(zhuǎn)角，使用模擬的簡化量子旋轉(zhuǎn)門更新被囊的量子位置；