面向成本優(yōu)化的SBS虛擬化資源調配論文
在現有關(guān)于虛擬化資源優(yōu)化分配的研究中，應用通常為單層或多層邏輯組成結構. 然而，對于由不同組件服務(wù)按照多種組合邏輯( 如順序結構、分支結構、并行結構和循環(huán)結構等) 構成的與已有研究不同，本文針對基于 SBS 的云應用的資源優(yōu)化分配問(wèn)題，提出了一種以滿(mǎn)足端到端平均響應時(shí)間為約束，以最小化資源使用成本為目標的虛擬化資源分配優(yōu)化模型及其遺傳算法的實(shí)現. 在該模型中，定義了組件服務(wù)資源配置的概念，并給出了組件服務(wù)候選資源配置的確定方法，從而將資源優(yōu)化分配問(wèn)題轉換為一個(gè)資源配置組合優(yōu)化問(wèn)題，進(jìn)而采用遺傳算法求解. 實(shí)驗驗證了本文的資源分配優(yōu)化模型的有效性，并且表明提出的遺傳算法實(shí)現收斂速度快，且與線(xiàn)性規劃算法相比，在較大問(wèn)題規模上可以快速獲得質(zhì)量更高的解.
1 基于成本的 SBS
資源分配優(yōu)化模型本節首先定義組件服務(wù)的資源配置，并給出其確定方法，進(jìn)而將 SBS 資源優(yōu)化分配建模為一個(gè)資源配置的組合優(yōu)化問(wèn)題.
1. 1 確定候選資源配置為了確定組件服務(wù)的候選資源配置，需要獲取任意資源向量與該組件服務(wù)平均響應時(shí)間之間的映射關(guān)系，本文稱(chēng)描述該映射關(guān)系的模型為組件服務(wù)的資源模型. 另外，還要確定資源使用成本的計算模型，即資源定價(jià)模型.
1. 1. 2 資源定價(jià)模型實(shí)際中，不同的資源類(lèi)型可以采用多種定價(jià)模型，如線(xiàn)性定價(jià)模型、指數型定價(jià)模型等. 本文假設資源使用成本與資源分配量、資源使用時(shí)長(cháng)呈正比，并對所有資源類(lèi)型均采用線(xiàn)性定價(jià)模
2 基于遺傳算法
求解優(yōu)化模型根據優(yōu)化模型可知，組件服務(wù)的資源配置組合優(yōu)化是個(gè) NP 難問(wèn)題，而遺傳算法是解決最優(yōu)化問(wèn)題的`有效方法之一，因此本文采用遺傳算法進(jìn)行求解. 首先，采用一維編碼方式對個(gè)體進(jìn)行二進(jìn)制編碼，基因位取值滿(mǎn)足式( 5) 和式( 6) ; 然后，采用通用的遺傳算子進(jìn)行種群的繁殖，為了減少無(wú)效解，對交叉操作和變異操作進(jìn)行了一定限制，使其滿(mǎn)足優(yōu)化模型的約束條件. 另外，在適應度函數中引入了罰函數，從而降低在解空間中無(wú)對應可行解的個(gè)體的適應度，加快收斂速度.隨機等距的方式抽取個(gè)體，從而更好地保持種群多樣性.交叉算子采用單點(diǎn)交叉. 為了使新的個(gè)體仍然滿(mǎn)足約束條件式( 5) ，將交叉點(diǎn)的取值限制為不同段基因的分割點(diǎn).變異算子采用位點(diǎn)變異，將變異基因位的值取非. 與交叉算子類(lèi)似，為滿(mǎn)足式( 5) ，如果變異后的值為1，則將該基因位所屬基因段中其他基因位的值均置為0，否則，則在變異后，隨機從該基因位所屬基因段中的其他基因位中選擇一個(gè)并取非.最后，本文通過(guò)設定遺傳代數作為終止迭代的條件，相比通過(guò)設定精度來(lái)終止迭代，可以防止由于種群過(guò)大、要求精度較高而引起的搜索時(shí)間過(guò)長(cháng)的情況.
3 實(shí)驗與分析
本節主要驗證本文的遺傳算法的收斂速度，并將其與線(xiàn)性規劃算法在 SBS 資源分配優(yōu)化模型上解的質(zhì)量和求解效率兩方面進(jìn)行比較.
3. 1 實(shí)驗設置
3. 2. 1 遺傳算法的收斂速度該組實(shí)驗考察本文提出的遺傳算法的收斂速度，這對于在合理時(shí)間內求得最優(yōu)解具有重要意義. 為了使算法能以較大概率收斂到最優(yōu)解，本文在適應度函數中引入了罰函數，以物理機個(gè)數取值15 為例，與未采用罰函數的適應度函數相比較，結果如圖3 所示.根據圖4 可知，對于不同的物理機數量，遺傳算法得到的最小資源使用成本略高于線(xiàn)性規劃算法，而且隨著(zhù)物理機數量的增加，兩種算法得到的最小資源使用成本均呈降低趨勢，這是由于解空間擴大增加了求得更優(yōu)解的可能性，同時(shí)物理機增多也會(huì )有助于減少資源配置之間的沖突，進(jìn)而產(chǎn)生更多的可行解.2) 求解優(yōu)化模型消耗的時(shí)間. 在求解優(yōu)化模型時(shí)，遺傳算法和線(xiàn)性規劃算法消耗的時(shí)間對比結果如圖5 所示.明顯要高于未引入罰函數時(shí)，這是因為在解空間中沒(méi)有可行解的個(gè)體不會(huì )遺傳到下一代，因此可在一定程度提高收斂到最優(yōu)解的概率.
3. 2. 2 與線(xiàn)性規劃比較該組實(shí)驗通過(guò)物理機數量在 10 ～50 之間的變化，與常用的求解約束優(yōu)化問(wèn)題的線(xiàn)性規劃算法在解的質(zhì)量( 以部署 SBS 的資源使用成本度量) 和求解效率( 以求解優(yōu)化模型消耗的時(shí)間度量) 兩方面進(jìn)行比較.1) 部署 SBS 的資源使用成本. 遺傳算法和線(xiàn)性規劃算法求得的最小資源使用成本對比如圖 4所示.圖4 最小資源使用成本對比Fig. 4 Comparison of the lowest resource costs根據圖4 可知，對于不同的物理機數量，遺傳算法得到的最小資源使用成本略高于線(xiàn)性規劃算法，而且隨著(zhù)物理機數量的增加，兩種算法得到的最小資源使用成本均呈降低趨勢，這是由于解空間擴大增加了求得更優(yōu)解的可能性，同時(shí)物理機增多也會(huì )有助于減少資源配置之間的沖突，進(jìn)而產(chǎn)生更多的可行解.2) 求解優(yōu)化模型消耗的時(shí)間. 在求解優(yōu)化模型時(shí)，遺傳算法和線(xiàn)性規劃算法消耗的時(shí)間對比結果如圖5 所示.圖5 消耗時(shí)間對比Fig. 5 Comparison of solving time根據圖5 可知，兩種算法的時(shí)間消耗均隨著(zhù)物理機數量的增加而呈上升趨勢. 當物理機數較小( 小于25) 時(shí)，線(xiàn)性規劃算法的時(shí)間消耗要低于遺傳算法; 而當物理機數量較大時(shí)，線(xiàn)性規劃算法的時(shí)間消耗顯著(zhù)增加，此時(shí)遺傳算法的效率要優(yōu)于線(xiàn)性規劃.
綜上實(shí)驗結果表明: 本文的遺傳算法能夠在可接受的時(shí)間內收斂到最優(yōu)解，并且適應度函數中的罰函數對于提高算法的收斂速度具有比較明顯的效果; 遺傳算法求解得到的資源分配方案的資源使用成本比較接近線(xiàn)性規劃得到的最優(yōu)解;與線(xiàn)性規劃相比，當組件服務(wù)的候選資源配置較多時(shí)，本文的遺傳算法可以在更短時(shí)間內求得最優(yōu)資源配置組合.4 結 語(yǔ)本文針對基于SBS 的應用在云環(huán)境部署時(shí)的資源優(yōu)化分配問(wèn)題，提出了一種基于資源配置的組合優(yōu)化思想、以最小化資源使用成本且滿(mǎn)足應用SLA 和物理機資源約束的資源分配優(yōu)化模型，并根據該優(yōu)化模型的特點(diǎn)給出了改進(jìn)的遺傳算法.
實(shí)驗驗證了本文提出的優(yōu)化模型的有效性，并且表明其基于遺傳算法的實(shí)現具有較快的收斂速度，同時(shí)可獲得接近線(xiàn)性規劃最優(yōu)解的資源配置組合，但在問(wèn)題規模較大時(shí)求解效率明顯優(yōu)于后者.
【面向成本優(yōu)化的SBS虛擬化資源調配論文】相關(guān)文章：
歌詞是調配語(yǔ)文大菜的佐料10-07
面向大海作文06-03
精選成本管理辦法論文11-29
關(guān)于巧用遠程教育資源優(yōu)化漢語(yǔ)拼音教學(xué)07-10
《京劇的虛擬性》閱讀答案06-21
虛擬與現實(shí)作文05-13