云計算中的基于改進的粒子群算法資源調(diào)度的研究

陳南岳

摘要：該文主要針對由于云計算動態(tài)功能而造成的不均衡資源集群情況，提出一些改善策略，主要是利用虛擬機技術(shù)，實現(xiàn)云計算資源的動態(tài)遷移。在遷移的過程中主要是利用引入窗口的相關(guān)指數(shù)來分析負載的熱點。在選擇虛擬機的時候，要充分考慮遷移效果和速度，利用退火邏輯中的粒子群算法，得到最好的虛擬機放置。然后利用輪盤思想完成平臺資源的高效優(yōu)化。之后就是利用云仿真技術(shù)CloudSim把云計算系統(tǒng)中的等級協(xié)議（SLA）有關(guān)的違背率、集群耗能、虛擬機的遷移次數(shù)、剩余資源等問題進行試驗，之后將各種算法和本文的算法進行比較。得出的結(jié)果很顯然說明了本文的算法比較有優(yōu)勢。

關(guān)鍵詞：云計算；粒子群算法；動態(tài)遷移；虛擬機

在IT領(lǐng)域中云計算是非常受歡迎的，對于當今時代各個行業(yè)對大型數(shù)據(jù)處理的需求越來越多，云計算作為一種新型計算機技術(shù)，它將網(wǎng)格式計算、并行式計算、分布式計算等實現(xiàn)了進一步的發(fā)展，充分的適應(yīng)了現(xiàn)代社會的需求。它包括的服務(wù)層次主要有三種：首先是基礎(chǔ)設(shè)施層，其次是平臺層，最后就是應(yīng)用層，這三層的功能都可以通過服務(wù)的形式表現(xiàn)出來。云計算的調(diào)度任務(wù)是指在云配置的環(huán)境中，利用相關(guān)的資源策略，根據(jù)用戶對資源的不同需求進行分析，從而是實現(xiàn)資源的合理配置，總之這些任務(wù)調(diào)配基本上都是在基礎(chǔ)設(shè)施層（IaaS）進行。目前使用的資源調(diào)度策略基本上都是在虛擬機上進行，如何在云計算環(huán)境中是實現(xiàn)更加高效的任務(wù)調(diào)度，為用戶提供更加精確的數(shù)據(jù)，是當下主要考慮的問題。

粒子群算法（PS0）是在模擬鳥群進行覓食行為試驗中逐漸發(fā)展起來的，它是一種群體協(xié)作方式的智能算法，它的優(yōu)勢在于簡單實用、容易理解，由于這些特點該算法被廣泛應(yīng)用。這種算法主要是由Eberhart等提出，之后又將群體智能算法進行完善。粒子算法的計算過程比較簡單，參數(shù)設(shè)置比較少，同時收斂速度也是非?？?，所以該算法的應(yīng)用價值比較高。但是，標準的PSO算法在實際進化中，逐漸降低了種群多樣性，從而也造成該算法出現(xiàn)收斂早熟的情況。之后Zhang等對粒子群算法的速度重新進行初始化，從而保持了該算法的種群多樣性。Riget等人利用種群多樣性繼續(xù)進行測量，在試驗中將粒子群進行交替的排斥和吸引操作。

1資源調(diào)度中初始化虛擬機的放置

首先就是建立云計算平臺并實現(xiàn)運行，把系統(tǒng)運行中原有的平臺移動到現(xiàn)在的云計算系統(tǒng)中。在實現(xiàn)這個環(huán)節(jié)之前，還有對該平臺進行虛擬化，還有對每個虛擬平臺進行初始化，然后建立云平臺。想要順利的實現(xiàn)移動原有的業(yè)務(wù)，這里可以使用動態(tài)遷移的技術(shù)進行完成，把虛擬機進行初始化之后按照物理點進行分配，這樣是為了在平臺的運行中減少虛擬機的遷移次數(shù)。

1.1資源調(diào)度中使用退火思想

把虛擬機反映到物理節(jié)點上，能夠?qū)崿F(xiàn)負載的均衡和減少能耗的優(yōu)化目標，這里主要使用的是啟發(fā)式的搜索算法。因為傳統(tǒng)的粒子群算法在搜索過程中容易出現(xiàn)局部優(yōu)解的情況，所以，專業(yè)人士根據(jù)啟發(fā)式算法的優(yōu)劣進行分析，最后得出將退火思想和粒子群算法相結(jié)合實現(xiàn)對多種表目標進行計算。利用退火思想將搜索過程中的可能出現(xiàn)局部最優(yōu)解的跳出概率進行分析，從而找出整體的最優(yōu)解，這樣可以防止傳統(tǒng)粒子出現(xiàn)局部最優(yōu)的情況造成搜索的失敗，最后就可以實現(xiàn)全局搜索功能的提高，同時也能提高最有解計算的準確度和效率。

1.2粒子群相關(guān)算法的建模

首先對虛擬機相關(guān)的編號n進行隊列排序，然后根據(jù)相關(guān)的搜索算法把物理節(jié)點m與其的映射關(guān)系計算出來，之后根據(jù)物理節(jié)點合理放置虛擬機，從而實現(xiàn)優(yōu)化的目的。在群體粒子中每個粒子的速度和位置可以表示為：

在公式（1）中x表示在第k輪迭代中，參數(shù)是i的粒子在數(shù)值j個虛擬機的物理節(jié)點所放置的編號。在公式（2）中u：表示在k輪迭代中，參數(shù)為i的粒子出現(xiàn)在第j維相關(guān)的速度；D則是一個常量，它主要是對粒子飛行的范圍進行控制，避免出現(xiàn)偏移過渡的情況給算法的收斂造成影響。根據(jù)經(jīng)驗總結(jié)將設(shè)置為10%-20%的問題空間。

在每輪迭代中每個粒子的位置和速度通過公式（3）（4）進行更新。

在該公式中，i是群體中的每個粒子編號；d則是每個粒子的相關(guān)維數(shù)，它是根據(jù)虛擬機的個數(shù)來確定取值范圍；P則是迭代在個體i中最佳的位置向量；P是在整個群體中最佳的位置向量。

其中r1、r2表示0～1的隨機均勻分布數(shù)；c1、c2則是學(xué)習(xí)因子，他們會在0-4之間取相等的數(shù)值；W則是慣性的權(quán)重。

1.3慣性權(quán)重的設(shè)計和分析

對粒子群算法相關(guān)的結(jié)果和收斂速度造成影響的主要因素是粒子群的慣性權(quán)重，如果慣性權(quán)重的值比較大，那么粒子群相關(guān)算法就具有了較高性全局搜索能力，在所有的解中此時所計算出的值則是具有適應(yīng)度函數(shù)的最小解；如果慣性權(quán)重比較小的話，那么此時的粒子群算法則是局部搜索功能最好的，此時算法就能夠在一定的小范圍內(nèi)實現(xiàn)局部搜索。所以，在對粒子群迭代過程進行計算的時候，前提就是先做好粒子權(quán)重有關(guān)最大值的設(shè)置，這樣可以更加方便在全局范圍內(nèi)進行最優(yōu)值的搜索，之后在利用最小的慣性權(quán)重，在這個小范圍內(nèi)進行最優(yōu)值的搜索，如此才能在搜索算法中獲得較快的收斂性與更好的搜索結(jié)果。

通過將慣性權(quán)重的值從最大變成最小，來提高粒子群搜索的效率。其中關(guān)于慣性權(quán)值的設(shè)置可以根據(jù)公式（5）進行：

在該公式中m表示W(wǎng)值只在范圍內(nèi)變化；t表示當前的迭代相關(guān)次數(shù)；k值主要是對慣性權(quán)重進行影響以此來減少速度；num則是總迭代的次數(shù)。在迭代次數(shù)呈現(xiàn)增加的狀況時，這時候的慣性權(quán)重則是減少的，而且速度的減少也在變緩，這樣可以方便從全局搜索轉(zhuǎn)變成局部搜索，同時也能夠限制算法收斂的速度。

1.4引入模擬退火思想

根據(jù)公式（3）（4）可以看出，在進行粒子群算法時，是將每個粒子飛行的速度人為控制在一定的范圍內(nèi)，避免粒子出現(xiàn)較大的偏差，從而影響搜索的結(jié)果和收斂的速度。如果沒有對每個粒子運動位置進行限制，那么當粒子移動到一個對于局部來說是較優(yōu)值時，之后繼續(xù)的迭代都會在這個值上進行，這樣將會對搜索算法的性能造成影響。

這里可以使用退火思想和粒子群算法相結(jié)合的方式，對計算過程出現(xiàn)的局部最優(yōu)解的問題。Metropolis相關(guān)準則表明，當粒子的溫度在T時，這時它趨于平衡的概率則是exp（AE/kT），其中E表示在溫度T時有關(guān)的內(nèi)能，AE是它變化的量，k則屬于Bohzmann常數(shù)。首先把這個概率值代人到粒子群算法中，利用目標函數(shù)把內(nèi)能E模擬出來，用控制參數(shù)t來模擬溫度T。另外，在進行退火算法模擬的時候，先對i進行初始解并對參數(shù)t進行控制，之后根據(jù)當前的解通過迭代得出新的解，將其代人到目標函數(shù)中，之后計算出函數(shù)相關(guān)的變化量，然后分析這個結(jié)果是否拒絕或是接受，在每個次迭代過程結(jié)束的時候，根據(jù)相關(guān)的比例逐漸減少t的相關(guān)值，計算需要的退火公式如下：

該式中a是模擬退火中被冷卻而衰減的因子，它的取值一般是小于1.00的正常數(shù)。

在獲得每個粒子的新位置后，把適應(yīng)度的值也計算出來，假如適應(yīng)度的值比當前的位置好，那么此時的粒子就要移動到新的位置，如果是相反的，那么粒子要根據(jù)exp（AE/kT）概率進行移動。通過利用退火思想進行的模擬計算得出，每個粒子在粒子群中都會經(jīng)過退火計算，而且每個粒子會按照相應(yīng)的概率值來改變自己的位置，其中每粒子都是根據(jù)粒子群相關(guān)的優(yōu)化公式進行移動的而不是隨機的，這樣在迭代的過程中才能更好對其進行控制，避免出現(xiàn)局部最優(yōu)解。通過在粒子群算法中使用退火思想，然后對每個經(jīng)過的粒子進行退火分析，這樣可以對每個粒子更新的位置進行控制。

1.5目標物理節(jié)點使用輪盤賭思想進行選擇

一旦云計算平臺完成建設(shè)，那么在長期的運行中，總會因為用戶的不同需求進行虛擬機的移動，造成平臺中的虛擬機出現(xiàn)不定時的遷移。在給虛擬機進行物理機的選擇時，對于長期運行云平臺來說，利用退火模擬進行粒子群算法計算得出的只會是一個局部最優(yōu)解，這時如果搜索任務(wù)增多或是虛擬機出現(xiàn)遷移，那么下一刻的集群情況可能就是次優(yōu)狀態(tài)，如果頻繁進行虛擬遷移的話，則會出現(xiàn)資源被占用的情況。所以利用粒子群進行虛擬機相關(guān)的位置放置時，首先要選擇好對應(yīng)的物理機，利用輪盤賭算法進行計算，這樣集群才能長期處于優(yōu)化狀態(tài)。

在進行輪盤賭思想的計算時，是在多組解中考慮到可能解的個數(shù)，之后隨機選擇一組解進行計算。在多組可能解中使用輪盤賭的思想，可以在相對的概率范圍內(nèi)實現(xiàn)當前最有解，或是得出當前的次優(yōu)狀態(tài)。

在粒子群算法中使用輪盤賭思想是要將迭代過程中得到的N組解保存起來，以此得到虛擬機準確的放置最優(yōu)解。然后把這些解分成N組，然后組間一個Nxn的矩陣，這樣就可以獲得虛擬機遷移需要的物理節(jié)點了。之后使用概率相關(guān)算法，在根據(jù)每個解在相關(guān)解集中所占的比例，計算出每個解相關(guān)的標號，然后將虛擬機牽動需要的可能解和相關(guān)的標準差計算出來。如果出現(xiàn)的期望值和可能解的絕對值之間的差值比標準的差大，那么這個解則是不可能解，就不予考慮了。最后使用概率算法在最優(yōu)解和次優(yōu)解之間進行物理節(jié)點的選擇，這樣就可以對粒子群算法中獲得的結(jié)果進行優(yōu)化，從而實現(xiàn)長期優(yōu)化的目的。

1.6適應(yīng)度的函數(shù)

在進行云平臺資源的調(diào)度時，要充分考慮節(jié)點、能耗、負載和服務(wù)等級協(xié)議（SLA）等問題，實現(xiàn)平臺的高性能和高資源利用率，從而減少能耗。

4）服務(wù)等級協(xié)議主要受物理節(jié)點有關(guān)CPU的使用率的影響。其中在SLA評價函數(shù)中有關(guān)CPU的使用率，用公式表示為：

在該公式中Ucev是物理節(jié)點中有關(guān)CPU的使用率，P是保證SLA相關(guān)的閾值范圍。在公式（7）中選擇最小的CPU使用節(jié)點。

5）在對使用率資源進行評價的時候，可以利用剩余資源的利用率相關(guān)算法進行。把CPU、內(nèi)存、剩余資源、網(wǎng)絡(luò)、硬盤等分別與總資源比值計算出來，之后就可以得到標準的剩余資源了。在最小的標準化資源和各維之間的剩余資源中去差值，然后將計算出的最小值作為最優(yōu)解。計算剩余資源有關(guān)使用率的公式如下：

在該公式中Ri表示在第i維處的標準化剩余資源，R表示標準化剩余資源中的最小只，根據(jù)公式（6）計算出利用率約均衡f值越是小，在各維中使用該節(jié)點的幾率就越不均衡，如果值是不斷增大的，那么在各維中該節(jié)點的使用率就會越低，則該節(jié)點可以作為防止節(jié)點。

3）節(jié)點的能耗包括兩部分內(nèi)容，一是運行的能耗，而是基礎(chǔ)能耗。因為電源能耗和利用的CPU率之間是存在一定的線性關(guān)系，所以，這里可以使用通過CPU的相關(guān)使用率計算節(jié)點處的能耗。計算節(jié)點能耗的相關(guān)公式如下：

該公式中P表示滿載電能的相關(guān)消耗，P是空載電能的有關(guān)消耗，根據(jù)公式得出最低耗能的相關(guān)節(jié)點作為搜索解。

6）根據(jù)不同的目標優(yōu)化要求進行權(quán)值的設(shè)置，從而實現(xiàn)多目標的優(yōu)化。綜合的適應(yīng)度函數(shù)表示為：

2虛擬機的遷移過程

2.1利用負載預(yù)測獲得物理熱點

首先是通過窗口的思想，按照時間相關(guān)順序利用預(yù)測指數(shù)的算法來確定相應(yīng)的熱點。根據(jù)歷史數(shù)值對某一時刻的CPU使用率進行計算：

該公式中a表示平滑指數(shù)相關(guān)的預(yù)測數(shù)值（其范圍是整數(shù)且a≤1），它是對下一個時間段CPU的使用率受窗口影響的預(yù)測；a1。是正太隨機分布變量，主要是確保預(yù)測的值有一定的隨機性。

2.2選擇遷移虛擬機

將CPU使用率和虛擬機相關(guān)的內(nèi)存大小策略相結(jié)合，同時提高遷移質(zhì)量，相關(guān)函數(shù)是：

該式中R是虛擬機的相關(guān)內(nèi)存。如果CPU的使用率高而且內(nèi)存是小的時候，Q的值就是最大，虛擬機的遷移可以很快的消除熱點，如果CPU有關(guān)場景數(shù)據(jù)和內(nèi)存數(shù)據(jù)非常少，這時可以減少遷移的時間。

3結(jié)論

本文主要是對云平臺有關(guān)資源調(diào)度的SLA和能耗，以及資源利用與遷移次數(shù)等問題進行分析，通過退火思想對虛擬機進行了初始化放置，分析了虛擬機遷移相關(guān)的動態(tài)變化過程，使能耗和資源利用，以及遷移次數(shù)等問題實現(xiàn)了均衡的目的。