基于改進(jìn)的花授粉算法的虛擬機(jī)分配策略

田海梅，徐勝超

（1.金陵科技學(xué)院計(jì)算機(jī)工程學(xué)院，南京211169；2.廣州華商學(xué)院數(shù)據(jù)科學(xué)學(xué)院，廣州511300）

引 言

低能量消耗與高服務(wù)質(zhì)量是綠色云數(shù)據(jù)中心的主要性能目標(biāo)，目前國內(nèi)外的研究主要采用虛擬機(jī)遷移技術(shù)來達(dá)到這2個(gè)目標(biāo)［1-3］。虛擬機(jī)遷移的過程非常復(fù)雜，涉及物理主機(jī)負(fù)載檢測、虛擬機(jī)選擇與虛擬機(jī)重新分配及優(yōu)化等3個(gè)階段。虛擬機(jī)分配及優(yōu)化階段是最重要的一個(gè)階段，屬于多目標(biāo)優(yōu)化問題或者裝箱問題［4］，它沒有最優(yōu)解，只能在目標(biāo)函數(shù)中得到一定程度的最優(yōu)，目前針對虛擬機(jī)分配及資源優(yōu)化過程有很多智能算法對其進(jìn)行優(yōu)化，例如遺傳算法［5］、貪心算法［6］、粒子群優(yōu)化算法［7］、蟻群算法［8］、強(qiáng)化學(xué)習(xí)優(yōu)化算法［9］、螢火蟲群優(yōu)化算法［10］以及蛙跳算法［11］等。這些智能優(yōu)化方法都不同程度地存在早熟和收斂速度慢的問題，同時(shí)已有的智能虛擬機(jī)分配算法在硬件上往往都只考慮了一維的因素（處理器的溫度或者主頻，內(nèi)存利用率或者磁盤大小），其實(shí)云數(shù)據(jù)中心的能量消耗模型是一個(gè)多維的非線性數(shù)學(xué)模型，需要綜合考慮多個(gè)因素；另外云客戶端的資源訪問模型也需要重新設(shè)計(jì)。基于此，本文提出了新型的虛擬機(jī)分配及優(yōu)化策略?；ㄊ诜鬯惴ǎ‵lower pollination algorithm，F(xiàn)PA）也是近年來新提出的一種解決多目標(biāo)優(yōu)化的智能算法，它將局部最優(yōu)解搜索和全局最優(yōu)解搜索結(jié)合起來，具有良好的性能。針對上述虛擬機(jī)分配及優(yōu)化的特點(diǎn)和花授粉算法的比較，本文提出了云數(shù)據(jù)中心基于花授粉算法優(yōu)化的虛擬機(jī)分配策略（Flower pollination algorithm based virtual machine allocation，F(xiàn)PA-VMA）。

1 花授粉算法與虛擬機(jī)分配

1.1 花授粉算法

目前關(guān)于花授粉算法的文獻(xiàn)比較多［12-14］，它是一種模擬生物的交叉授粉的智能算法，具有參數(shù)少、實(shí)現(xiàn)簡單和容易調(diào)節(jié)的優(yōu)點(diǎn)，已經(jīng)廣泛應(yīng)用到NP-hard的多目標(biāo)組合優(yōu)化領(lǐng)域。某些研究者已經(jīng)實(shí)現(xiàn)了花授粉算法的離散搜索和連續(xù)搜索空間，結(jié)論表明它比其他常見的智能算法性能優(yōu)異。

花授粉算法在理想的情況下包括下面4個(gè)步驟：（1）帶花粉的傳粉者通過萊維Levy飛行進(jìn)行的全局授粉過程；（2）非生物自花授粉的局部授粉過程；（3）花的常性可以被認(rèn)為是繁衍概率，繁衍概率與參與的兩朵花的相似性成比例關(guān)系；（4）轉(zhuǎn)換概率p∈[0，1]控制全局授粉和局部授粉之間的轉(zhuǎn)換，由于物理上的鄰近性和風(fēng)等其他因素的影響，在整個(gè)授粉活動中，p是局部授粉一個(gè)非常重要的部分。

假設(shè)每顆顯花植物只開一朵花，且每朵花僅產(chǎn)生一個(gè)花粉配子。因此一朵花或一個(gè)配子就對應(yīng)于優(yōu)化問題中的一個(gè)解，類似于虛擬機(jī)到物理主機(jī)的映射與分配?；谝陨详U述，文獻(xiàn)［15］描述了基本的花朵授粉算法實(shí)現(xiàn)步驟。

1.2 FPA?VMA工作環(huán)境

云計(jì)算環(huán)境下分配可用的資源給云客戶端具有各種不同的模式，這些模式都可以被認(rèn)為是針對云數(shù)據(jù)中心資源池的一種基于服務(wù)的訪問，虛擬機(jī)技術(shù)是將云客戶端的請求封裝成虛擬機(jī)的形式來分配與訪問。圖1顯示了FPA-VMA分配優(yōu)化策略所運(yùn)行的資源分配模型，它由3個(gè)主要步驟組成：（1）云客戶端提交請求；（2）服務(wù)提供者處理請求；（3）云數(shù)據(jù)中心資源分配與管理。

圖1 FPA-VMA優(yōu)化的綠色云計(jì)算框架Fig.1 Optimized green cloud computing framework of FPA-VMA

圖1 中，首先云客戶端提交請求到云服務(wù)提供者，代理將返回該結(jié)果到右邊的云數(shù)據(jù)中心資源管理模塊。云資源管理將查詢該請求，與可用資源池的資源進(jìn)行比較，并作出決策。云資源管理對云客戶端請求的接受都是基于系統(tǒng)的資源可用性，如果超過了資源的可用能力，云資源管理將會把該請求傳遞到資源分配模式，尋找全局可用資源，該資源分配方法被傳遞到資源管理模塊，里面包含了FPA-VMA等虛擬機(jī)分配與優(yōu)化的相關(guān)操作。

1.3 FPA?VMA數(shù)學(xué)建模

1.3.1 云客戶端請求模型

云客戶端請求資源通過代理或者云服務(wù)提供者來請求各種應(yīng)用。云客戶端的請求可以定義為VMs，定義用戶的請求為UR。UR按照先來先服務(wù)的方式來訪問云數(shù)據(jù)中心的物理資源。Ai表示虛擬機(jī)VMs的組成部分。虛擬機(jī)的組成部分包括：處理器需求內(nèi)存需求；磁盤空間需求其中i和s表示資源的數(shù)量和它們各自的資源提供能力。因此，可以把資源請求表示為Ai?UR并且故有

所以當(dāng)云客戶端只發(fā)送1個(gè)請求到1個(gè)資源之上時(shí)，可以表示為

當(dāng)i=1時(shí)，UR1則表示了資源的需求只有1個(gè)，即

如果客戶端的請求超過1個(gè)時(shí)，可以表示為

1.3.2 云數(shù)據(jù)中心能量消耗模型

假設(shè)云數(shù)據(jù)中心中所有虛擬機(jī)集合為VM={VMi，i=1，2，3，…，n}，它們將被分配到多個(gè)物理主機(jī)PMj之 上，PM={PMj，j=1，2，3，…，m}。每 個(gè) 虛 擬 機(jī) 的 多 維 資 源 需 求 都按 照d維 的 向 量 來 表示［16］，VMi=(Ai，1，Ai，2，…，Ai，d)，其中Ai，s為虛擬機(jī)VMi的資源請求向量。類似地，每個(gè)物理主機(jī)的多維資源提供能力也可以按照d維的向量來表示［17］，PMj=(Bj，1，Bj，2，…，Bj，d)，其中Bj，s為物理主機(jī)PMj的資源能力提供向量。本文描述的FPA-VMA策略中各種物理主機(jī)資源主要包括CPU資源、內(nèi)存資源和磁盤空間，因此這里d=3。

虛擬機(jī)分配與優(yōu)化都有開始時(shí)間和結(jié)束時(shí)間，每個(gè)虛擬機(jī)VMi在一個(gè)固定的時(shí)間Sti開始，需要一個(gè)執(zhí)行時(shí)間Eti，因此整個(gè)虛擬機(jī)分配的時(shí)間跨越可表示為Sti+Eti。整體來講云數(shù)據(jù)中心的資源分配問題有下列約束條件：（1）所有資源必須有能力提供給云客戶端的請求；（2）所有的虛擬機(jī)的資源請求必須小于等于整個(gè)物理主機(jī)的資源提供能力；（3）假設(shè)aj(t)是被分配到PMj上的一個(gè)虛擬機(jī)，則每個(gè)虛擬機(jī)只能分配到一個(gè)具體的物理主機(jī)上；（4）對于?s=1，2，…，d，有

假設(shè)一個(gè)最優(yōu)的虛擬機(jī)分配方式RA為二元組(VMi，PMj)，?i∈{1，2，…，n}，?j∈{1，2，…，m}，RA目標(biāo)函數(shù)是盡量地提高整體物理資源的利用效率（RUDC），同時(shí)降低整體云數(shù)據(jù)中心的能量消耗首先必須試圖最大化單臺物理主機(jī)的資源利用效率有

則整個(gè)云數(shù)據(jù)中心物理主機(jī)的資源利用效率為

假設(shè)每個(gè)PMj都可以容納任何虛擬機(jī)，而且物理主機(jī)的能量消耗模型變量P(t)具有線性關(guān)系［18］，云數(shù)據(jù)中心的能量消耗模型的部分參數(shù)可描述為

式中：U(t)j表示在給定時(shí)刻t的物理資源利用效率；ECj為物理主機(jī)PMj在[t1，t2]內(nèi)的能量消耗，i∈{1，2，…，n}，j∈{1，2，…，m}，t∈[0，T]。整個(gè)云數(shù)據(jù)中心的能量消耗模型可以描述為

綜上所述，整個(gè)云數(shù)據(jù)中心的資源利用效率UR的最大值RA和整個(gè)云數(shù)據(jù)中心的能量消耗利用效率可以描述為

2 FPA?VMA策略描述

2.1 FPA?VMA簡介

IAAS云平臺的異構(gòu)性導(dǎo)致虛擬機(jī)規(guī)模越來越大，因此虛擬機(jī)資源分配算法需要的時(shí)間也越來越長。本文提出一種基于問題特征的搜索操作來重新設(shè)計(jì)花授粉算法中的動態(tài)切換概率（Dynamic switching probability，DSP）過程，以便適應(yīng)云數(shù)據(jù)中心的能量消耗模型，同時(shí)改善整個(gè)物理資源的利用效率。

本文的FPA-VMA在局部搜索辦法中也需要授粉者，其目的是為了在算法規(guī)定的搜索空間內(nèi)快速搜索和尋找到局部最優(yōu)解。第一步主要是對目標(biāo)函數(shù)的當(dāng)前解進(jìn)行改進(jìn)，只要滿足約束條件的問題解都可以算是一個(gè)當(dāng)前解，對每一個(gè)生成的當(dāng)前解而言，它們之間必須有一個(gè)差異值，用來體現(xiàn)這些當(dāng)前解是如何滿足全局的目標(biāo)函數(shù)需求。云數(shù)據(jù)中心的資源分配的總體目標(biāo)是把客戶端的n個(gè)虛擬機(jī)請求分配到m個(gè)可用的物理主機(jī)資源之上，以便在采用最小的物理資源條件下完成用戶的需求。

2.2 初始化階段

FPA-VMA的第一階段是初始化，根據(jù)目標(biāo)函數(shù)的當(dāng)前解，發(fā)現(xiàn)一個(gè)可能的局部解，只要滿足目標(biāo)函數(shù)約束條件的資源分配辦法，都可以認(rèn)為是一個(gè)局部最優(yōu)解。云客戶端使用能量感知的目標(biāo)函數(shù)來代替隨機(jī)的資源分配辦法，這樣可以盡量地提高物理資源的利用效率。如果當(dāng)前的需求不能滿足，F(xiàn)PA-VMA優(yōu)化算法將繼續(xù)進(jìn)行下一步。整個(gè)過程反復(fù)迭代，直到指定的時(shí)間到達(dá)或者尋找到全局最優(yōu)的資源分配辦法，此時(shí)的資源分配辦法是在最后種群中最好的花。算法1為FPA-VMA優(yōu)化算法中目標(biāo)函數(shù)RA的初始化過程，按照1.3節(jié)所描述的云數(shù)據(jù)中心的能量消耗模型來完成資源的分配［19］。

算法1目標(biāo)函數(shù)初始化

（1）For each PM∈collection of PMs do

（2）Utilization of PM：=PM.getUtilization of PM（CPU；Memory；Storage）

（3）Power of PM：=getPower（PM.getUtilization of CPU）

（4）Power of PM：=getPower（PM.getUtilization of Memory）

（5）Power of PM：=getPower（PM.getUtilization of Storage）

（6）Energy of datacenter：=Energy of datacenter+power of PMs（CPU；Memory；Storage）

（7）End for

（8）Evaluation value（Pollen）：=1.0/power of datacenter

2.3 全局搜索策略階段

在全局搜索階段，資源分配辦法Xi相當(dāng)于是一個(gè)花針對花粉配子的映射。傳粉者需要查找整個(gè)搜索空間，發(fā)現(xiàn)最優(yōu)的的當(dāng)前位置。因此全局最優(yōu)解適應(yīng)于生物和交叉?zhèn)鞣壅?，因?yàn)樗鼈冏裱氖荓evy萊茵飛行規(guī)則，可以更加有效地飛行很遠(yuǎn)的距離。在大規(guī)模的空間搜索過程中，Levy萊茵飛行規(guī)則比Brownian布朗運(yùn)動更加高效，該過程可以表示為［19］

式中Γ(λ)為標(biāo)準(zhǔn)的Gamma函數(shù)。

2.4 局部搜索策略階段

在獲得了全局最優(yōu)解之后，局部搜索階段是基于FPA花授粉算法的組成部分。FPA-VMA算法進(jìn)行更高強(qiáng)度的尋找，以便在相鄰的結(jié)構(gòu)中尋找到更加優(yōu)秀的問題解。FPA需要局部的花粉來搜索，以更好地探索周邊的區(qū)域，這樣可以增加尋找最優(yōu)解的機(jī)會。因?yàn)檫@個(gè)階段可以從當(dāng)前解中發(fā)現(xiàn)改進(jìn)的問題解，局部搜索可以描述為

2.5 動態(tài)切換概率階段

FPA-VMA中，切換概率p用來在全局傳粉和局部傳粉之間切換，這里p是一個(gè)常量。一般來講，一個(gè)智能優(yōu)化算法在剛開始執(zhí)行時(shí)，應(yīng)該多做一些全局搜索，而在最后快結(jié)束時(shí)盡量少做［17］。因此結(jié)合花授粉算法的實(shí)際情況，本文提出了DSP方法調(diào)整兩個(gè)不同的傳粉過程的比例，平衡全局搜索和局部搜索過程。這里增強(qiáng)的切換概率p可以修改為

式中：Maxiteration為FPA-VMA優(yōu)化算法的最大迭代次數(shù)；t為當(dāng)前的迭代次數(shù)。算法2為FPA-VMA優(yōu)化算法步驟。

2.6 FPA?VMA時(shí)間消耗分析

FPA-VMA首先以文獻(xiàn)［16-17］中的數(shù)據(jù)作為比較對象，即常見的普通花授粉算法FPA和蟻群虛擬機(jī)優(yōu)化策略ACO的結(jié)果。FPA-VMA、FPA和ACO算法都在類似的參數(shù)條件下進(jìn)行測試，調(diào)整循環(huán)迭代的次數(shù)為（100，200，1 000），改變種群的尺寸為（10，20，50）。對于普通的花授粉算法FPA而言，切換概率p=0.8，迭代的次數(shù)為1 000。對于蟻群優(yōu)化算法ACO中，交叉概率為0.95，學(xué)習(xí)參數(shù)為2［20］。

圖2 顯示了FPA-VMA優(yōu)化算法運(yùn)行時(shí)間隨著迭代次數(shù)變化的實(shí)驗(yàn)結(jié)果。從結(jié)果可以看出，隨迭代次數(shù)的增加，F(xiàn)PA-VMA相對其他兩種算法運(yùn)行時(shí)間較少，基本保持了線性的緩慢增加。在FPA-VMA中，每個(gè)花都被描述為M維的向量，花的搜索空間被限制在I，I在種群個(gè)數(shù)中已經(jīng)指定?？梢钥闯鯢PA-VMA優(yōu)化明顯優(yōu)于普通的FPA算法和ACO優(yōu)化算法，主要原因是FPA-VMA采用了動態(tài)的切換概率策略，提高了算法尋優(yōu)的效率。

圖2 FPA-VMA優(yōu)化算法時(shí)間分析Fig.2 Time cost results of FPA-VMA

ACO優(yōu)化算法在尋最優(yōu)解上也具有收斂性，盡管如此，出現(xiàn)收斂的時(shí)間還是不確定，因?yàn)閿?shù)據(jù)都是隨機(jī)的。綜合比較，F(xiàn)PA-VMA策略在所有函數(shù)的測試中具有比較好的性能，其主要原因是FPA-VMA在第4階段采用動態(tài)切換概率策略，它可以在局部搜索過程和全局搜索過程中調(diào)整，很容易發(fā)現(xiàn)滿足目標(biāo)函數(shù)的局部最優(yōu)解，而且它還可以加快發(fā)現(xiàn)全局最優(yōu)解的速度。

3 FPA?VMA實(shí)驗(yàn)與性能分析

3.1 實(shí)驗(yàn)環(huán)境

因?yàn)镕PA-VMA基于花授粉算法優(yōu)化的虛擬機(jī)分配是在虛擬機(jī)遷移過程中運(yùn)用的，所以進(jìn)行FPA-VMA實(shí)驗(yàn)分析必須構(gòu)造云數(shù)據(jù)中心的虛擬機(jī)遷移場景。本文參考了Cloudsim 3.0工具包，同時(shí)依據(jù)圖1中的功能模塊，實(shí)現(xiàn)了基于Java語言的云資源管理方法，根據(jù)算法2在該模塊中實(shí)現(xiàn)了花授粉算法的優(yōu)化的代碼。表1給出了云數(shù)據(jù)中心的物理主機(jī)和虛擬機(jī)的參數(shù)配置情況，為了描述簡單，這些物理主機(jī)都是相同的配置。表2給出了FPA-VMA算法與其他常見的Benchmark智能算法的參數(shù)設(shè)置。

表1 云數(shù)據(jù)中心的物理主機(jī)和虛擬機(jī)的參數(shù)設(shè)置Table 1 Parameters of physical host and virtual machine in cloud data centers

表2 FPA?VMA性能分析相關(guān)的算法參數(shù)設(shè)置Table 2 Parameters setup of FPA?VMA performance analysis

3.2 工作負(fù)載類型

實(shí)驗(yàn)的虛擬機(jī)的相關(guān)參數(shù)都來最常見的CoMon project，它是由Planetlab實(shí)驗(yàn)室開發(fā)的一個(gè)項(xiàng)目。虛擬機(jī)遷移周期設(shè)置為10 min一次，一共運(yùn)行24 h，每次統(tǒng)計(jì)1天內(nèi)的能量消耗，在1周內(nèi)重復(fù)運(yùn)行5次取平均值，1周內(nèi)每天虛擬機(jī)請求的個(gè)數(shù)如表3所示，不同的虛擬機(jī)尺寸如表4所示。

表3 Planet項(xiàng)目的1周工作負(fù)載Table 3 Workloads of a week in Planet projects

表4 CoMon項(xiàng)目不同虛擬機(jī)粒度的參數(shù)Table 4 Parameter setup of different virtual machine grains in CoMon projects

3.3 物理資源利用率分析

圖3 顯示了各個(gè)智能算法優(yōu)化針對云數(shù)據(jù)中心的所有物理主機(jī)的處理器資源，內(nèi)存資源和存儲資源的平均利用效率情況，包括云數(shù)據(jù)中心的所有活躍物理主機(jī)情況也進(jìn)行了分析。圖4顯示了隨著虛擬機(jī)請求個(gè)數(shù)的增加，物理資源利用效率的變化情況。這些實(shí)驗(yàn)結(jié)果表明，F(xiàn)PA-VMA策略可以使得云數(shù)據(jù)中心的物理主機(jī)資源平均利用率達(dá)到95.4%以上。

圖3 FPA-VMA多維物理資源利用效率分析Fig.3 Multi-demensional physical resource utilization results of FPA-VMA

圖4 FPA-VMA資源利用效率隨請求個(gè)數(shù)的變化Fig.4 Physical resource utilization results of different virtual machine numbers

在相同的軟硬配置和虛擬機(jī)請求的條件下，GA、ACO、螢火蟲優(yōu)化算法GSO［10］等虛擬機(jī)分配優(yōu)化策略只能使得云數(shù)據(jù)中心的物理資源達(dá)到72%的利用效率，F(xiàn)PA-VMA策略能夠高效地利用物理資源主要是得益于在花授粉時(shí)采用的DSP策略，它在具體的搜索最優(yōu)解的過程中停止了局部搜索，選擇利用搜索相鄰的資源分配方案，提高了效率。

另外一個(gè)原因是DSP策略可以改善FPA-VMA資源分配的全局收斂能力。FPA-VMA可以很好地分配虛擬機(jī)到目標(biāo)物理主機(jī)。整體來講，上述實(shí)驗(yàn)結(jié)果均可證明FPA-VMA是一個(gè)可操作的、高效的大規(guī)模云資源分配和優(yōu)化策略。

3.4 能量消耗分析

圖5 和圖6顯示了FPA-VMA、GA、ACO和GSO等虛擬機(jī)分配策略在不同的虛擬機(jī)請求下的云數(shù)據(jù)中心的能量消耗情況?？傮w來說，隨著云客戶端的虛擬機(jī)個(gè)數(shù)的增加，能量消耗都在增長。與GA、ACO和GSO策略比較起來，F(xiàn)PA-VMA策略的能量消耗最小。

圖5 FPA-VMA隨請求個(gè)數(shù)的能量消耗情況Fig.5 Energy consumption results of different virtual machine numbers

圖6 FPA-VMA隨主機(jī)個(gè)數(shù)的能量消耗情況Fig.6 Energy consumption results of different physical host numbers

因?yàn)榭蛻舳说奶摂M機(jī)請求個(gè)數(shù)的增加，越來越多的物理主機(jī)將被分配虛擬機(jī)，當(dāng)活動主機(jī)數(shù)目不夠時(shí)，云數(shù)據(jù)中心還會啟動處于睡眠狀態(tài)的物理主機(jī)。FPA-VMA能夠獲得良好性能也是因?yàn)榛ㄊ诜鬯惴ǖ奶摂M機(jī)分配優(yōu)化及該算法在動態(tài)切換概率階段的改進(jìn)策略。

表5 顯示了隨著物理主機(jī)數(shù)量變化，整個(gè)云數(shù)據(jù)中心總體能量消耗和資源利用率的比較情況。從表5中可以看出，在相同的虛擬機(jī)請求個(gè)數(shù)條件下，F(xiàn)PA-VMA策略的最大能量消耗只有104.6 kW·h，GA策略是125 kW·h，ACO策略是129 kW·h，GSO策略是135.2 kW·h，因此FPA-VMA虛擬機(jī)資源分配策略比其他優(yōu)化策略可以節(jié)省20%的能量消耗。

表5 云數(shù)據(jù)中心的總體能量消耗與資源利用情況Table 5 Total energy consumption and resource utilization in cloud data centers

4 結(jié)束語

針對目前綠色云數(shù)據(jù)中心的提高物理資源利用效率和降低能量消耗的需求，本文提出了基于花授粉算法優(yōu)化的虛擬機(jī)分配策略FPA-VMA。本文提出一種云數(shù)據(jù)中心環(huán)境下的綠色云計(jì)算框架，并設(shè)計(jì)了云數(shù)據(jù)中心的多維物理資源的能量消耗模型和客戶端的資源請求模型，將智能計(jì)算的花授粉算法應(yīng)用到虛擬機(jī)分配及其優(yōu)化過程中。真實(shí)條件下的實(shí)驗(yàn)數(shù)據(jù)表明，F(xiàn)PA-VMA在物理資源利用效率和整體能量消耗方面比常見的遺傳算法、蟻群算法和螢火蟲群算法等虛擬機(jī)分配策略性優(yōu)越，可以為企業(yè)節(jié)能云數(shù)據(jù)中心的構(gòu)造提供參考。