基于卡爾曼預(yù)測(cè)器的云計(jì)算資源調(diào)度研究

周婉++王移芝

摘要：資源調(diào)度是云計(jì)算的一個(gè)主要研究方向，本文在研究現(xiàn)有云計(jì)算資源調(diào)度算法的基礎(chǔ)上，為了提高云計(jì)算資源的利用率，保持負(fù)載平衡，設(shè)計(jì)了基于卡爾曼預(yù)測(cè)器的云計(jì)算資源調(diào)度算法，采用卡爾曼預(yù)測(cè)器預(yù)測(cè)虛擬資源下一時(shí)刻的狀態(tài)，由此得到虛擬資源的向量，然后計(jì)算任務(wù)的代價(jià)，建立任務(wù)與資源的映射模型，將任務(wù)分配到合適的虛擬資源進(jìn)行調(diào)度，避免了盲目調(diào)度，提出了基于卡爾曼預(yù)測(cè)器的云計(jì)算資源動(dòng)態(tài)調(diào)度的具體算法，最后在云計(jì)算仿真平臺(tái)CloudSim上進(jìn)行仿真實(shí)驗(yàn)與分析。仿真實(shí)驗(yàn)的結(jié)果證明，本文提出的算法在任務(wù)執(zhí)行的跨度和負(fù)載均衡離差方面具有一定的優(yōu)勢(shì)。

關(guān)鍵詞：云計(jì)算；虛擬資源調(diào)度；卡爾曼預(yù)測(cè)器

中圖分類號(hào)：TP311.12

文獻(xiàn)標(biāo)識(shí)碼：A

DOI：10.3969/j.issn.1003-6970.2015.09.003

0 引言

隨著計(jì)算機(jī)性能的不斷提高和互聯(lián)網(wǎng)規(guī)模的不斷擴(kuò)大，人們的計(jì)算需求和海量數(shù)據(jù)處理需求日益增長，出現(xiàn)了云計(jì)算這種新興的計(jì)算方式。云計(jì)算是在并行計(jì)算、分布式計(jì)算、網(wǎng)格計(jì)算的基礎(chǔ)上發(fā)展起來的一種商業(yè)模型，是虛擬化技術(shù)、效用計(jì)算、基礎(chǔ)設(shè)施即服務(wù)、平臺(tái)即服務(wù)和軟件即服務(wù)等概念優(yōu)化整合的結(jié)果。云平臺(tái)采用虛擬化技術(shù)將集群中的各種資源構(gòu)成資源池，接收用戶任務(wù)請(qǐng)求，并將任務(wù)調(diào)度到合適的資源上執(zhí)行。云環(huán)境下的任務(wù)數(shù)量以海量形式存在，而云計(jì)算資源具有動(dòng)態(tài)、異構(gòu)特性，這就使得云計(jì)算環(huán)境下的虛擬資源調(diào)度成為了云計(jì)算研究的一個(gè)熱點(diǎn)問題。

師雪霖等借鑒網(wǎng)絡(luò)效用最大化模型，提出了一種資源調(diào)度模型——云效用最大化模型，以達(dá)到效用最大為調(diào)度目標(biāo)，可以充分提高用戶的滿意程度。徐文忠等提出了一種基于遺傳算法的關(guān)于虛擬機(jī)負(fù)載均衡的調(diào)度策略，算法在很大程度上能夠解決負(fù)載不均衡和高遷移成本問題。王艷平等設(shè)計(jì)了一種基于改進(jìn)蟻群的云計(jì)算資源調(diào)度算法。在算法中添加了查找表，存儲(chǔ)其他螞蟻推薦的節(jié)點(diǎn)，縮短了搜尋資源節(jié)點(diǎn)的時(shí)間，從而使任務(wù)可以更快地獲得資源并執(zhí)行，保證了任務(wù)能夠按時(shí)完成。

本文設(shè)計(jì)了一種基于卡爾曼預(yù)測(cè)器的云計(jì)算資源調(diào)度算法，采用卡爾曼預(yù)測(cè)器預(yù)測(cè)虛擬資源下一時(shí)刻的狀態(tài)，得到可用資源向量，然后建立任務(wù)與資源的映射模型，將任務(wù)分配給合適的虛擬資源進(jìn)行調(diào)度，避免了盲目調(diào)度，并提出了具體的基于卡爾曼預(yù)測(cè)器的云計(jì)算資源動(dòng)態(tài)調(diào)度算法。

l 調(diào)度模型

在云計(jì)算的虛擬資源調(diào)度模型中，主流的是Map-Reduce調(diào)度模型。由Google最早提出并應(yīng)用到云平臺(tái)中，云用戶只需編程實(shí)現(xiàn)Map-Reduce接口即以實(shí)現(xiàn)計(jì)算的并發(fā)和分布執(zhí)行。它由“Map”和”Reduce”兩部分組成。具體結(jié)構(gòu)如圖1。

Map-Reduce調(diào)度模型中，首先根據(jù)文件的大小，將其分割。在集群中分為主控制模塊和普通模塊，主控制模塊的主要職責(zé)是將工作分配給普通模塊。主控制模塊的主要工作流程是首先選取空閑狀態(tài)的服務(wù)器，然后將映射或者簡化的任務(wù)分配到這些空閑的服務(wù)器上，分配到映射任務(wù)的服務(wù)器根據(jù)主控制模塊傳達(dá)的指令讀取輸入文件的分片，之后執(zhí)行映射操作，將執(zhí)行結(jié)果保存在緩存中。映射階段的任務(wù)完成之后，將中間結(jié)果寫入硬盤，同時(shí)進(jìn)行分區(qū)，將分區(qū)信息傳遞給主控制模塊。主控制模塊將中間結(jié)果保存的分區(qū)信息通知分配了簡化任務(wù)的服務(wù)器，這些服務(wù)器讀取中間結(jié)果，同時(shí)執(zhí)行用戶定義的簡化操作，最后將結(jié)果保存在輸出文件中，同時(shí)將結(jié)果通知主控制模塊。最終由主控制模塊綜合所有的輸出模塊，輸出最終的結(jié)果。

2 相關(guān)描述

2.1 任務(wù)描述

Kalman于1960年提出了卡爾曼濾波，采用由狀態(tài)方程和觀測(cè)方程組成的線性隨機(jī)系統(tǒng)的狀態(tài)空間模型來描述濾波器，并利用狀態(tài)方程的遞推性，按線性無偏最小均方誤差估計(jì)準(zhǔn)則，用遞推算法對(duì)該濾波器的狀態(tài)變量作最佳估計(jì)，從而求得濾掉噪聲的有用信號(hào)的最佳估計(jì)。

卡爾曼濾波器使用遞推的方式來進(jìn)行預(yù)測(cè)。濾波器先通過上一時(shí)刻系統(tǒng)的狀態(tài)預(yù)測(cè)下一時(shí)刻系統(tǒng)的狀態(tài)，然后再通過觀測(cè)的到的系統(tǒng)運(yùn)行時(shí)表現(xiàn)進(jìn)行反饋修正，如此反復(fù)。

步驟1：獲取虛擬機(jī)的資源，根據(jù)資源分別計(jì)算虛擬機(jī)的性能。

步驟2：根據(jù)卡爾曼濾波預(yù)測(cè)下一時(shí)刻虛擬機(jī)的資源。

步驟3：根據(jù)步驟1與步驟2的計(jì)算結(jié)果計(jì)算虛擬機(jī)與任務(wù)的Cost值，按性能與任務(wù)從大到小進(jìn)行對(duì)應(yīng)的映射與綁定，任務(wù)數(shù)按虛擬機(jī)數(shù)進(jìn)行平均分配。

步驟4：迭代次數(shù)i是否達(dá)到最大值迭代次數(shù)n，若達(dá)到最大迭代次數(shù)，則虛擬資源調(diào)度結(jié)束；否則i=i+l，并返回步驟2繼續(xù)運(yùn)行。

4 實(shí)驗(yàn)仿真與分析

為了驗(yàn)證算法，本實(shí)驗(yàn)在云仿真平臺(tái)CloudSim上進(jìn)行仿真。CloudSim是澳大利亞墨爾本大學(xué)開發(fā)的云計(jì)算仿真器，是一個(gè)通用的和可擴(kuò)展的模擬框架，支持模擬云計(jì)算基礎(chǔ)設(shè)施和管理服務(wù)，具有對(duì)不同應(yīng)用和服務(wù)模型的調(diào)度和分配策略的性能進(jìn)行量化和比較等優(yōu)點(diǎn)。CloudSim是在離散事件模擬包Simjava上開發(fā)的函數(shù)庫，CloudSim繼承了GridSim的編程模型，并具有以下特點(diǎn)：一個(gè)自足的支持?jǐn)?shù)據(jù)中心、服務(wù)代理人、調(diào)度和分配策略的平臺(tái).CloudSim的軟件結(jié)構(gòu)框架和體系結(jié)構(gòu)組件包括Simjava、GridSim、CloudSim、UserCode4個(gè)層次，CloudSim的CIS（CloudInformation Service）和DataCenterBroker實(shí)現(xiàn)資源發(fā)現(xiàn)和信息交互，是模擬調(diào)度的核心，提出的算法主要在DataCenterBroker中實(shí)現(xiàn)。

本實(shí)驗(yàn)的仿真環(huán)境同李園園等，采用李園園等的方法對(duì)實(shí)例進(jìn)行仿真，將得到的任務(wù)跨度和負(fù)載均衡離差進(jìn)行比較，得出的仿真曲線如圖2和圖3所示。

從圖2中可以看出，本文所研究的方法的任務(wù)跨度與李園園等的方法和魏銳等的方法相比，任務(wù)跨度比較低，平均任務(wù)跨度與李園園等的方法相比，降低了19.87%，與魏銳等的方法相比，降低了29.75%。

從圖3中可以看出，負(fù)載均衡離差的值隨著任務(wù)數(shù)的增加而增加，隨著任務(wù)數(shù)的增加負(fù)載均衡離差呈增加趨勢(shì)，本文所研究的方法得到的負(fù)載均衡離差值較李園園等的方法和魏銳等的方法偏低，說明了該方法較好地實(shí)現(xiàn)了資源負(fù)載平衡。

5 總結(jié)

云計(jì)算的資源調(diào)度技術(shù)是云計(jì)算中的關(guān)鍵技術(shù)，一個(gè)好的調(diào)度算法對(duì)提高整個(gè)云計(jì)算系統(tǒng)的性能起著重要作用。本文研究并設(shè)計(jì)了一種基于卡爾曼預(yù)測(cè)器的云計(jì)算資源調(diào)度算法，建立了云資源調(diào)度模型，采用卡爾曼預(yù)測(cè)器預(yù)測(cè)虛擬資源下一時(shí)刻的狀態(tài)，得到可用資源向量，然后建立任務(wù)與資源的映射模型，將任務(wù)分配給合適的虛擬資源進(jìn)行調(diào)度，避免了盲目調(diào)度，使用cloudsim工具進(jìn)行仿真，實(shí)驗(yàn)結(jié)果表明，本研究方法有效地實(shí)現(xiàn)云環(huán)境下虛擬資源調(diào)度，具有較小的負(fù)載均衡離差，有效地提高了資源利用率。