周婉++王移芝

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

關鍵詞：云計算；虛擬資源調度；卡爾曼預測器

中圖分類號：TP311.12

文獻標識碼：A

DOI：10.3969/j.issn.1003-6970.2015.09.003

0 引言

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

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

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

l 調度模型

在云計算的虛擬資源調度模型中，主流的是Map-Reduce調度模型。由Google最早提出并應用到云平臺中，云用戶只需編程實現Map-Reduce接口即以實現計算的并發(fā)和分布執(zhí)行。它由“Map”和”Reduce”兩部分組成。具體結構如圖1。

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

2 相關描述

2.1 任務描述

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

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

步驟1：獲取虛擬機的資源，根據資源分別計算虛擬機的性能。

步驟2：根據卡爾曼濾波預測下一時刻虛擬機的資源。

步驟3：根據步驟1與步驟2的計算結果計算虛擬機與任務的Cost值，按性能與任務從大到小進行對應的映射與綁定，任務數按虛擬機數進行平均分配。

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

4 實驗仿真與分析

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

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

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

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

5 總結

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