朱建宇

1 引言

隨著計算機的快速發(fā)展和廣泛使用，計算機數(shù)據(jù)變得越來越復雜，規(guī)模越來越龐大。

為了處理大規(guī)模的數(shù)據(jù)和應用，計算機數(shù)據(jù)做出各種正確的行為指導，云計算應運而生。云計算是一種在分布式計算，并行計算，網(wǎng)格計算的基礎上發(fā)展形成的一種計算模式。目前，從國內(nèi)國外的研究現(xiàn)狀來看，谷歌、微軟、亞馬遜、IBM等巨型IT公司紛紛在全球建立數(shù)據(jù)中心，研發(fā)和應用云計算，并形成了相對成熟穩(wěn)定的云計算平臺。同時，均將云計算作為發(fā)展的重要戰(zhàn)略之一[1]。同樣，諸如Facebook，蘋果等其他大型公司及部分中小型企業(yè)也開始加大對云計算的投資力度，實現(xiàn)云計算的各領(lǐng)域的落地服務。在國內(nèi)，以阿里云為首，騰訊云，華為云，百度云等幾十家互聯(lián)網(wǎng)企業(yè)。都對云計算進行了巨額投資和研發(fā)，并實現(xiàn)了初步的商用目的。國內(nèi)的大型央企，國企，政府機構(gòu)，都已經(jīng)建立了各自的云計算平臺，為自己的單位建立了相對完善的私有云平臺。

云計算利用了虛擬化技術(shù)將物理資源虛擬成為軟件資源，形成了多種資源池，這樣可以提供按需交付、靈活彈性、集中規(guī)模、自由調(diào)度、安全管理等多種功能。適應了當代企業(yè)和用戶對大規(guī)模數(shù)據(jù)計算，復雜邏輯處理的迫切要求。由于很多科學研究、項目需求對云計算的資源有各種各樣的要求，包括計算資源，網(wǎng)絡資源，存儲資源。研究高效靈活的云計算相關(guān)技術(shù)任重道遠，滿足各種使用需求具有非常重要的價值和意義。

OpenStack是IaaS的重要組件，OpenStack的作用是創(chuàng)建虛擬機需要各種服務的交互和配合工作。OpenStack支持幾乎所有類型的云環(huán)境，項目目標是提供實施簡單、可大規(guī)模擴展、豐富、標準統(tǒng)一的云計算管理平臺。OpenStack通過各種互補的服務提供了基礎設施即服務的解決方案，每個服務提供API以進行集成。目前OpenStack開發(fā)速度非?？欤鐓^(qū)也很活躍，國內(nèi)外的很多企業(yè)、研究機構(gòu)、學校、組織都踴躍參與和貢獻OpenStack的開發(fā)和修復工作，發(fā)展非常順利。

用戶在使用云計算服務的過程中，更為關(guān)注可靠性、效率、成本。基于上述指標提出QoS(quality of service)服務質(zhì)量。為了最大程度滿足QoS的需求，提高用戶滿意度，云計算需要在資源分配環(huán)節(jié)從用戶角度考慮，實現(xiàn)資源調(diào)度的合理化、自由化、準確化。因此，資源調(diào)度和資源方向是云計算的重要研究方向。

為了保障QoS，提高資源利用率，必須解決好云計算中的資源調(diào)度問題，隨著仿生學的發(fā)展，人們開始關(guān)注遺傳算法，并將遺傳算法應用到云計算當中，提高了資源調(diào)度的智能性。

但是，傳統(tǒng)的遺傳算法具有局部收斂的問題。只能得到局部最優(yōu)解，因此，針對上述問題，本文提出基于OpenStack云計算的資源調(diào)度改進遺傳算法，提高了可靠性，滿足了資源利用最大化，更好的發(fā)揮了遺傳算法的智能性作用。

2 OpenStack云計算理論基礎及傳統(tǒng)調(diào)度算法

2.1 云計算

云計算是一種可以提供按需收費，能夠彈性伸縮的一種新型的計算模式。正所謂彈性可伸縮，即資源分配和部署可以根據(jù)用戶的需求時時的改動。云計算的這種資源使用模式，為用戶通過網(wǎng)絡提供訪問計算資源的可能。比如存儲，應用服務，軟件程序等。從用戶角度來講，云計算有以下特征：（1）按需服務，云計算可以為用戶快速提供可用資源可用服務，并且能夠根據(jù)用戶的需求對資源進行使用，釋放，這樣，云服務商可以根據(jù)用戶需求調(diào)度各種云資源；（2）資源池，云計算通過虛擬化技術(shù)將存入資源進行虛擬并組成資源池，讓多個用戶根據(jù)需求共同利用資源池中的資源[2]；（3）彈性伸縮，云服務商可以根據(jù)用戶的需求,快速的，彈性的分配，釋放，回收資源，這對于用戶而言，代表資源是無限的，任何需求都能夠及時得到滿足；（4）按需付費，按需服務的基本眼球要求按需付費，云計算商按照用戶是使用的資源進行按量計費，滿足了用戶的需求，當然，這些資源也是虛擬抽象出來的資源，比如CPU，內(nèi)存，硬盤，帶寬等。

2.2 虛擬化技術(shù)

虛擬化技術(shù)是云計算IaaS層核心組成部分，虛擬化也可以理解為對物理資源的抽象化。其本質(zhì)是隔離了軟件和硬件的一種中間件技術(shù)，將物理底層進行屏蔽，并為上層提供統(tǒng)一的接口服務。虛擬化的對象可以劃分為服務器的虛擬化，網(wǎng)絡的虛擬化，存儲的虛擬化等多種不同形式。本文的資源調(diào)度主要針對的是服務器的虛擬化。服務器虛擬化是把一臺服務器抽象成為多臺服務器，這樣一臺物理主機就可以變成多臺虛擬機，并且多臺虛擬機是互相獨立的，是完全隔離的。這樣保證了虛擬機的安全性與可靠性。服務器虛擬化主要是將物理的CPU，內(nèi)存，硬盤，網(wǎng)絡設備，I/O接口等資源進行抽象。其中CPU虛擬化會將物理的CPU虛化成多個虛擬的CPU。這樣，多個虛擬的CPU可以提高物理CPU的利用率。內(nèi)存虛擬化將物理內(nèi)存抽象成多個虛擬內(nèi)存，內(nèi)存空間完全隔離;網(wǎng)絡設備和I/O接口虛擬化，就是將真實的物理設備抽象為多個虛擬設備，為多臺虛擬機進行I/O請求，提供服務[3]。

目前，較為流行的虛擬化管理軟件有KVM，Xen，vSphere，本文研究的OpenStack云計算對KVM提供很好的支持。KVM是基于Linux內(nèi)核對虛擬機進行管理的，所以它要求底層硬件必須都支持虛擬化。

2.3 傳統(tǒng)遺傳算法

遺傳算法按照自然界的生存法則，將具體問題抽象化，把需要解決的問題虛擬成為染色體，接著把這些染色體進行選擇，交叉和變異，直到得到目標最優(yōu)解[4]。具體的算法過程按照以下描述，隨機產(chǎn)生初始化種群后，通過不斷地的選擇，交叉，變異來優(yōu)化，調(diào)度，擴大下一代種群搜索空間。并利用適應度函數(shù)對已經(jīng)編碼的種群進行優(yōu)勝劣汰，留下適應度較高的個體，淘汰掉適應度較低的個體。篩選完個體之后，由新的個體產(chǎn)生新的種群。

3 改進資源調(diào)度遺傳算法

3.1 改進資源調(diào)度遺傳算法

傳統(tǒng)的遺傳算法，采用0，1的編碼方式對染色體完成編碼，但是資源調(diào)度的問題是有不同的分配方案的，需要明確每一個任務在每一個資源節(jié)點執(zhí)行，傳統(tǒng)的編碼方式不能覆蓋全部信息。本文采用一種間接編碼方式，規(guī)定任務的數(shù)量就是染色體的長度。染色體的每一位表示一個任務，對應一個資源。比如染色體（3，5，2，6，8，7）表示染色體長度是6，需要執(zhí)行6個任務，第一個任務被分配到節(jié)點3，第二個任務被分配到節(jié)點5，以此類推。

3.2 適應度函數(shù)

適應度函數(shù)表示個體被度量的函數(shù)，用來計算個體被選中的概率。適應度越大，個體越好，被選中概率越大，保證特性得到遺傳。適應度函數(shù)的選擇能夠決定是否可以得到最優(yōu)解，所以選擇合適的是適應度函數(shù)非常重要。

滿足用戶QoS的需求有四個指標，分別是時間、可用性、成本、安全性。這四項指標能夠滿足用戶的需求，決定最優(yōu)解。目標函數(shù)值越大，代表優(yōu)化效果越好，也代表算法性能高。因此本文選用目標函數(shù)的平方當做適應度函數(shù)。QoS四項指標按照權(quán)重系數(shù)來影響適應度函數(shù)。權(quán)重系數(shù)由資源的剛性和彈性偏好決定。也可以根據(jù)用戶自身需求進行調(diào)節(jié)。

3.3 改進遺傳算法操作過程

遺傳算法主要有三部分組成，選擇，交叉，變異。這三個部分直接影響到遺傳操作的效果。

（1）選擇

選擇是為了通過對當代種群的篩選，利用適應度函數(shù)對個體進行評價，完成對種群的不斷優(yōu)化。因為適應度函數(shù)的大小決定了個體被篩選的概率，所以可以將優(yōu)良的個體通過評價篩選后遺傳到下一代。本文采用的選擇方法是賭輪選擇法。當個體的適應度值比較大的時候，被選擇的可能性也越大。

（2）交叉

交叉算子可以使我們的搜索空間擴大，是遺傳算法中的基因重組，具有核心作用[5]。交叉是指兩個父體結(jié)構(gòu)進行替換，重新生成兩個新個體。交叉概率的選取非常重要，取值偏大會導致良好的結(jié)構(gòu)被破壞，取值偏小會影響個體的產(chǎn)生速度。本文設施了一種自適應方式，避免交叉概率偏大或者偏小。調(diào)整公式1如下：

favg代表種群的品均適應度，fmax代表種群最大的適應度，f代表交叉雙方適應值比較大的一方。k1和k2在（0，1）之間取值，從公式中可以看出，個體適應度值接近最大適應度值的時候，交叉概率就小，而當適應度值和最大適應讀值相等的時候，交叉概率等于0。

（3）變異

變異可以為算法找到最優(yōu)解提供條件，可以豐富種群的多樣性。變異操作可以使算法向著最優(yōu)解的方向收斂。并且保持多樣性，變異概率設置太大，不會加速尋找最優(yōu)解，反而會破壞變異基因位。本文設計了一種自適應的方式選取變異概率。調(diào)整公式2如下：

其中，favg代表種群的品均適應，fmax代表種群最大的適應度，代表變異雙方適應值比較大的一方。k3和k4在（0，1）之間取值。從公式中可以看出，當變異個體的適應值接近最大的適應值的時候，變異概率就小，而適應度值與最大適應讀值相同的時候，變異概率等于0。

綜上所述，本文的交叉算法有更強的全局搜索能力，而本文的變異算法可以提高局部的搜索能力。通過選擇交叉變異三種操作，遺傳算法可以擴大全局搜索范圍，提高局部搜索能力，使得問題可以加速并保證精準的尋求和接近最優(yōu)解。

4 總結(jié)

本文研究了云計算，OpenStack的基本原理和核心技術(shù)，對傳統(tǒng)的遺傳算法進行了深入學習和實驗。提出了一套可以改進資源調(diào)度效果的遺傳算法，能夠?qū)崿F(xiàn)在滿足QoS的情況下，降低成本，提高資源利用率。