面向多等級應用的氣象云資源調度方法研究

梁中軍，孫志于，韓同欣，宋雅婷，張正陽

(1.新疆氣象信息中心，新疆 烏魯木齊 830002；2.國家氣象信息中心，北京 100081)

0 引 言

隨著云計算、大數據技術的不斷發(fā)展，氣象云平臺[1]已成為支撐天氣、氣候、公共氣象服務等業(yè)務的重要平臺。其中，如何合理分配氣象云平臺中的基礎資源，已成為氣象業(yè)務穩(wěn)定運行的關鍵。

當前,研究者針對不同場景[2-4]的云平臺調度問題,從任務指派[5-9]、虛擬資源調度[10-14]和物理資源調度[15-21]等方面提出了各類啟發(fā)式方法。例如，文獻[6]提出了一種基于強化學習的多目標任務調度算法；文獻[7]提出了一種考慮時間、成本、CPU、內存和帶寬等多維約束的任務調度算法；文獻[8]從任務調度角度對其調度流程、主要算法和評測指標進行了綜述；文獻[12]提出了一種新型的面向網絡性能優(yōu)化的計算資源分配及調度機制；文獻[17]針對業(yè)務之間存在的復雜約束關系，提出了一種面向私有云的業(yè)務遷移部署方法。雖然現有研究針對公有云、私有云等場景，從負載均衡[9]、節(jié)能提升利用率[13-14,20-21]、低成本高QoS[18]等角度給出了大量的算法,然而,與上述研究場景不同,以上方法沒有針對氣象業(yè)務應用的特點設計，無法直接應用在氣象云平臺里，同時，現有算法沒有考慮部分功能組件對云平臺的物理服務器有不兼容的情況，不能滿足氣象云平臺的資源調度需求。

與傳統云平臺中的業(yè)務應用不同，氣象業(yè)務應用具有更明顯的周期性特點，在日常氣象業(yè)務應用對基礎設施資源的需求相對平穩(wěn)，氣象云平臺可以追求較高的資源利用水平。在汛期氣象業(yè)務的重要核心組件需要盡可能預留充足的基礎設施資源以應對重大天氣過程、重大氣象保障等對氣象監(jiān)測應用、氣象預報應用、災害預警應用的業(yè)務要求。為此，氣象云平臺不僅需要考慮平臺資源的集約性，同時要確保重要核心應用在平臺運行的穩(wěn)定性。

為解決上述問題，該文對氣象云平臺的資源調度問題進行建模，設計一種改進蛙跳算法的氣象云資源調度方法，并通過實驗驗證了方法的效果。主要貢獻體現在以下四個方面：

(1)根據氣象業(yè)務對基礎設施資源需求的特點，設計兩個目標函數來分別評價氣象云平臺的資源利用水平和對重要核心業(yè)務的支撐情況，基于物理服務器與功能組件之間的約束關系，將問題建模成一個多約束多目標優(yōu)化問題。

(2)根據氣象業(yè)務在日常和汛期的資源需求特點，設計適應度函數來綜合衡量模型目標，將問題轉化為多約束單目標問題。

(3)設計一種改進蛙跳算法的氣象云平臺資源調度方法。方法將資源調度方案映射成為蛙跳算法中的石頭位置，重新定義蛙跳算子，利用局部最優(yōu)交叉操作和最優(yōu)青蛙變異策略來提升方法的迭代搜索能力。

(4)通過實驗仿真驗證了方法的效果。

1 氣象云平臺資源調度場景描述

為支撐天氣、氣候、公共氣象服務等業(yè)務對基礎設施資源的需求，氣象云平臺使用虛擬機和物理服務器來承載不同業(yè)務系統的功能組件，為其提供CPU、內存、I/O、存儲等資源。由于氣象業(yè)務系統對軟硬件環(huán)境有一定要求，且部分系統的組件之間有部署要求，功能組件在部署前就需要滿足多種約束關系。主要包括：服務器的穩(wěn)定性約束和功能組件部署約束。其中，前者是為了保障氣象云平臺的承載業(yè)務不因資源搶占而導致中斷，后者主要滿足業(yè)務運行的前置條件。由于氣象業(yè)務應用在日常和汛期具有不同的特點，且業(yè)務遷移成本較高，資源調度通常在汛期前后進行開展。具體如圖1所示。

圖1 氣象云平臺資源調度場景

由于氣象云平臺中的基礎設施資源有限，為滿足業(yè)務的有序發(fā)展，氣象應用被劃分成若干等級，分級提供基礎資源支撐。根據氣象業(yè)務的重要程度將功能組件劃分成若干等級(如：重要核心、關鍵和一般)。根據功能組件對氣象云平臺的資源需求(CPU、內存、I/O、存儲等)，以及上述兩種約束關系對功能組件進行動態(tài)部署。其中，在日常資源需求穩(wěn)定時，側重提升資源利用率，以提升氣象業(yè)務的集約化水平。在汛期重要核心功能組件的峰值很難估計，側重于保障重要核心功能組件的穩(wěn)定運行(即，為高等級應用提供更多基礎設施資源)。

2 氣象云平臺資源調度的問題建模

該文將面向多等級應用的氣象云資源調度問題建模如下：

基于以上描述，該問題模型的主要參數及數據符號標識如表1所示。

表1 模型的主要參數及數據符號標識

氣象云平臺資源調度問題模型如下:

目標一：最大化氣象云平臺的資源利用率，具體如公式(1)所示。

(1)

目標二：最大化氣象云平臺對重要核心功能組件的支撐保障，即對重要核心業(yè)務預留最大基礎設施資源，具體如公式(2)所示。

(2)

式中，

G為重要核心功能組件的標識，xik表示功能組件i與物理服務器k之間的調度關系。

約束條件一：服務器的穩(wěn)定性約束。

(3)

式中，Bk是物理服務器k上承載功能組件的最高等級。即物理服務器要滿足其承載的最高等級功能組件的資源預留要求。

約束條件二：功能組件部署約束。

據統計，1998年，中國參與綠色食品開發(fā)的企業(yè)有619個，綠色食品產品銷售額為285億元，實現利潤17億元。

由于氣象業(yè)務系統對軟硬件環(huán)境有一定要求，部分功能組件之間存在依賴關系，資源調度需要滿足一定前置條件。假設功能組件部署有o條依賴約束D={d1,d2,…,do}和h條沖突約束C={c1,c2,…,ch},則約束可由下列公式表示。

?ch∈C∧ch=∧k∈F,xek=0

(4)

?do∈D∧do=,xak×xbk=1

(5)

其中，任意沖突約束ch=表示物理服務器F不滿足功能組件e的部署條件；任意依賴約束do=表示功能組件a和b需要部署在同一臺物理服務器上。

3 基于改進蛙跳算法的氣象云平臺資源調度方法

為解決氣象云平臺資源調度問題，該文設計改進蛙跳算法來求解模型。由于面向多等級應用的氣象云平臺資源調度問題考慮因素較多，同時傳統資源調度問題本身屬于NP-Hard問題，因此難以精確求解問題。由于蛙跳算法在求解多約束問題上具有搜索能力強、與本問題求解更易映射的特點，該文以蛙跳算法框架為基礎，將問題求解與蛙跳算法進行映射，重新定義蛙跳算子，設計適應度函數，利用局部最優(yōu)交叉操作和最優(yōu)青蛙變異策略來迭代搜索最優(yōu)方案。

3.1 氣象云平臺資源調度方案映射

3.2 適應度函數設計

為指導算法迭代搜索，以公式(6)為適應度函數綜合評價方案的優(yōu)劣。

(6)

其中，調度方案Z(p)的適應度函數由Fitness(Z(p))計算，取值越高越好；β為目標一的重要程度，日常和汛期會有不同取值；|Gp|為調度方案Z(p)中重要核心功能組件占有物理服務器的數量。

3.3 初始調度方案生成

為迭代搜索最優(yōu)資源調度方案，算法首先生成若干初始方案作為迭代搜索的基礎。方案生成的主要思想是隨機產生所有功能組件的部署順序,優(yōu)先采用貪婪策略部署重要核心功能組件,然后按照順序部署其余功能組件。具體步驟如下：

步驟1：生成重要核心功能組件的部署方案。按照重要核心功能組件的生成順序，根據貪婪策略依次生成部署方案。策略以問題目標二最大化為指標，依次判斷當前物理服務器是否能夠滿足約束條件，若滿足則選擇取值最大的物理服務器為部署方案。若存在重要核心功能組件在部署時無法滿足約束，則重新生成部署順序，依照步驟1生成可行方案。

步驟2：部署其余功能組件生成方案。根據生成的部署順序，對其余功能組件，以適應度函數值最大為目標，采用貪婪策略依次生成部署位置。生成過程中無法滿足約束，則重新生成部署順序，執(zhí)行步驟1和步驟2，完成初始方案生成。

3.4 蛙跳算子定義

為迭代搜索方案，重新定義蛙跳算子如下：

定義1 差異算子⊙：用于分析兩個資源調度方案在相應物理服務器上的差異。局部最優(yōu)資源調度方案Z(pb)與局部最差資源調度方案Z(pw)在物理服務器上的差異可由公式(7)計算獲得。

(7)

(8)

定義2 隨機選擇算子rand()：用于從資源調度方案間存在差異的物理服務器集合中隨機選擇若干物理服務器的操作。被選擇的物理服務器由n維向量Di表示，滿足|Di|∈[0,n]。

定義3 重新部署算子⊕：重新部署資源調度方案Z(pw)在Di上功能組件。具體步驟包括：清除被選擇物理服務器上的部署方案，生成待部署功能組件集合。采用初始調度方案的生成策略，分別對集合中的重要核心功能組件和其他功能組件進行重新部署。

基于以上定義，局部最優(yōu)資源調度方案Z(pb)對局部最差資源調度方案更新，生成新方案Z(new)的過程可由公式(9)和公式(10)表示。

Di=rand()*Z(pb)⊙Z(pw)

(9)

Z(new)=Z(pw)⊕Di

(10)

3.5 局部最優(yōu)交叉操作

為快速搜索最優(yōu)資源調度方案，算法將加強族群之間的交流，提升全局搜索能力。采用文獻[17]的交叉框架，設計局部最優(yōu)交叉策略，提升算法的搜索能力。具體如下：

步驟1：構建局部最優(yōu)交叉操作集合。選擇每個種群中的最優(yōu)方案，根據其適應度取值從大到小排序，選擇順序相鄰的方案，兩兩配對構成局部最優(yōu)交叉操作集合。

步驟2：隨機選擇交叉點，調換交叉點前的功能組件。針對任意配對的局部最優(yōu)調度方案，從n臺物理服務器里選擇除第一臺以外的任意機器作為交叉點，將二者在交叉點前部署功能組件進行對調，生成兩個新部署方案。

步驟3：調整新部署方案，生成新資源調度方案。判斷新部署方案是否存在重復和未部署功能組件，若存在，則選擇新部署方案中重復功能組件對應的物理服務器，清除被選擇物理服務器上的部署方案，同時加入未部署功能組件，生成待部署功能組件集合。利用重新部署算子生成新資源調度方案。

步驟4：對比新資源調度方案與原局部最優(yōu)調度方案的適應度取值，選擇值大的方案參與下次迭代搜索。

3.6 最優(yōu)青蛙變異操作

為進一步提升算法的迭代搜索能力，每次迭代都將對種群中的當前全局最優(yōu)青蛙實施變異操作。即，隨機選擇當前全局最優(yōu)資源調度方案中承載功能組件的一臺物理服務器，清除被選擇物理服務器上的部署方案，生成待部署功能組件集合，利用重新部署算子對其進行重新部署，生成新資源調度方案。對比新資源調度方案與原全局最優(yōu)調度方案的適應度取值，選擇值大的方案作為新的全局最優(yōu)方案。

3.7 算法的執(zhí)行過程

基于改進蛙跳算法的氣象云平臺資源調度方法執(zhí)行過程如下：

步驟1：算法初始化設置。輸入氣象云平臺的物理服務器情況(物理服務器的總數n、氣象云平臺的資源情況{T1,…,Tn})、功能組件的情況(功能組件的總數w、功能組件的等級{L1,…,Lw}、功能組件的資源需求{Q1,…,Qw}、重要核心功能組件的標識G)、服務器穩(wěn)定性約束(不同等級功能組件對資源的預留要求{S1,…,Sl})、氣象業(yè)務部署約束(功能組件之間的依賴關系D，功能組件與服務器之間沖突關系C)、資源利用率的重要程度β等信息。設置方法的種群規(guī)模gp、最大迭代次數IT、子群的規(guī)模tp。

步驟2：生成初始資源調度方案集合，劃分若干青蛙子群。根據種群規(guī)模設置，利用3.3節(jié)的方法生成初始資源調度方案集合{Z(1),Z(2),…,Z(gp)}。利用公式(6)計算每個方案的適應度，根據子群規(guī)模設置，結合適應度取值大小依次將生成方案劃分到相應子群中，生成m個子群{SP1,…,SPm}。將子群中適應度最高和最低的方案設置為局部最優(yōu)資源調度方案和局部最差調度方案。

步驟3：更新青蛙子群內部的最差資源調度方案。首先利用差異算子分析局部優(yōu)資源調度方案與局部最差調度方案的差異，使用隨機選擇算子獲取局部最差調度方案需要調整的物理服務器，利用重新部署算子生成新的部署方案，判斷其與原局部最差調度方案的適應度取值大小，若大于則利用新部署方案更新局部最差調度方案。

步驟4：更新青蛙子群的局部最優(yōu)資源調度方案。首先依據適應度對局部最優(yōu)方案Z(pb1),…,Z(pwm)逆序排列生成Z(pb1),…,Z(pwm)和二者之間的映射關系RE={re1,re2,…,rem}。然后利用3.5節(jié)中的局部最優(yōu)交叉操作更新各個子群中的局部最優(yōu)資源調度方案。

步驟5：更新青蛙種群的全局最優(yōu)資源調度方案。利用3.6節(jié)最優(yōu)青蛙變異操作更新全局最優(yōu)青蛙的資源調度方案Z(gbest)。

步驟6：迭代搜索最優(yōu)資源調度方案，輸出最終結果。判斷算法是否小于最大迭代次數，若是則跳轉至步驟2繼續(xù)搜索，否則輸出全局最優(yōu)資源調度方案作為最終結果。具體如下所示:

算法：基于改進蛙跳算法的氣象云平臺資源調度方法。

輸入：n,w,C,D,{T1,…,Tn},{L1,…,Lw},{S1,…,Sl},

{Q1,…,Qw},G,β,gp,IT,tp

1.初始化方案劃分子群

{Z(1),Z(2),…,Z(gp)}=Initial() #根據輸入生成初始調度方

{SP1,…,SPm}=Group(Z(1),Z(2),…,Z(gp),tp)#劃分成m個子群

2.迭代搜索方案

Fori=1:IT do

Forj=1:mdo #更新子群最差調度方案

Z(pbj),Z(pwj)∈SPj#子群的最優(yōu)最差方案

Di=rand()*Z(pbj)⊙Z(pwj)

Z(new)=Z(pwj)⊕Di

If Fitness(Z(pwj))

Z(pwj)=Z(new)

End for

#依據適應度逆序排列局部最優(yōu)方案

{[Z(pb1),...,Z(pbm)],RE}=SortByFitness(Z(pb1),…,Z(pbm))

Fork=1:?m/2」 do #進行局部最優(yōu)交叉操作

{Z(new2k),Z(new2k-1)}=Cross(Z(pb2k)，Z(pb2k-1))

If Fitness(Z(pb2k))

Z(pb2k)=Z(new2k)

If Fitness(Z(pb2k-1))

Z(pb2k)=Z(new2k)

End for

#更新子群的局部最優(yōu)方案

Z(pb1),…,Z(pbm)=Update([Z(pb1),…,Z(pbm)],RE)

Z(gbest)=FindGBest(Z(pb1),…,Z(pwm)) #找到種群最優(yōu)方案

Z(gnew)= Mutation(Z(gbest))#全局最優(yōu)變異操作

If Fitness(Z(gbest))

Z(gbest)=Z(gnew)

End for

輸出：種群最優(yōu)調度方案Z(gbest)

4 實驗仿真

實驗以氣象云平臺的資源利用率和對重要核心業(yè)務的支撐情況為評價指標，綜合分析方法的效果。氣象云平臺的資源利用率包含CPU、內存、I/O、存儲等指標，其對重要核心功能組件的支撐情況通過預留資源的多少來衡量?？傮w調度效果可由公式(6)來計算?？紤]氣象業(yè)務具有周期性特點，仿真將設計汛期和日常兩種狀態(tài)進行調度，其中氣象云平臺在日常將側重于提升資源利用水平，汛期將側重于對重要核心功能組件的支撐保障，方法評價的優(yōu)劣主要體現在氣象云平臺汛期和日常的業(yè)務目標上。重要核心功能組件的資源需求可根據數據量和計算復雜度采用類比法預估。在日常天氣過程較少，氣象應用對基礎設施資源的需求相對穩(wěn)定，雖然，不同功能組件在一天中的負載略微起伏，但是由于模型為每臺物理服務器都預留了一定的基礎資源，算法基本可以保證氣象云平臺的資源不會超額分配，從而應對負載有一些變化的場景。在汛期由于重大天氣過程和氣象保障需求的增多，重要核心功能組件將需要更多資源以應對業(yè)務的需要。為此，氣象云平臺需要針對其預留更多的資源以確保平臺盡全力支撐重要核心功能組件的需求。

為驗證方法的有效性，實驗對比貪婪方法進行分析。貪婪方法首先利用3.3節(jié)的方法生成初始資源調度方案，然后再選擇最優(yōu)調度方案作為問題的解。該文在一臺物理機中搭建仿真環(huán)境模擬資源調度平臺，它能根據氣象應用的資源需求和氣象云平臺的資源情況生成最終的調度方案。在仿真環(huán)境中，氣象云平臺的資源情況參考新疆氣象云平臺的能力生成，氣象功能組件對氣象云平臺的資源需求及約束條件將結合氣象應用在日常和汛期的情況隨機生成，仿真主要參數如表2所示。

表2 實驗參數設置

基于以上實驗數據，基于改進蛙跳算法的氣象云平臺資源調度方法和貪婪方法在汛期和日常，根據不同數量的功能組件的需求，對氣象云中資源調度獲得的效果如圖2～圖6所示。其中，圖2是兩種方法在汛期和日常，根據不同數量的功能組件的需求獲得的調度效果，圖3和圖4展示了基于改進蛙跳算法的氣象云平臺資源調度方法對氣象云平臺資源調度后的資源利用率情況。圖5和圖6展示了基于改進蛙跳算法的氣象云平臺資源調度方法對重要核心功能組件的平均資源預留比例。

圖2 兩種方法在汛期和日常對氣象云平臺

從圖2可以看出，基于改進蛙跳算法的氣象云平臺資源調度方法在汛期和日常，針對不同功能組件的需求，與貪婪方法相比，均能取得較好的總體調度效果。由于貪婪方法初始時采用隨機方式生成部署順序，因此有一定概率獲得較好的調度方案，但方法并不穩(wěn)定。該方法在60個功能組件時取得了較為良好的效果，但在70個功能組件時效果并不理想?；诟倪M蛙跳算法的氣象云平臺資源調度方法是在貪婪方法的基礎上不斷迭代改進，因此其效果總體優(yōu)于貪婪方法。

從圖3和圖4可以看出，文中方法能夠根據汛期和日常要求，動態(tài)調整氣象云平臺的資源以支撐不同數量功能組件的需求。在日常本方法能使氣象云平臺保持較高資源利用水平。

圖3 文中方法在汛期和日常對氣象云平臺資源調度后的資源利用率(60個功能組件)

圖4 文中方法在汛期和日常對氣象云平臺資源調度后的資源利用率(70個功能組件)

從圖5和圖6可以看出，文中方法能夠根據汛期和日常要求，動態(tài)調整氣象云平臺對重要核心功能組件的平均預留資源比例，在汛期本方法能使氣象云平臺預留較多的基礎資源，保證重要核心業(yè)務安全穩(wěn)定運行。

圖5 文中方法在汛期和日常對重要核心功能組件平均預留的資源比例(60個功能組件)

圖6 文中方法在汛期和日常對重要核心功能組件平均預留的資源比例(70個功能組件)

綜上所示，基于改進蛙跳算法的氣象云平臺資源調度方法針對不同數量的功能組件需求，總能夠獲得較好的總體調度效果，與貪婪方法相比該方法的搜索能力更強。

5 結束語

氣象云平臺是集約支撐氣象業(yè)務發(fā)展基礎資源平臺，合理調度氣象云中的基礎資源是氣象業(yè)務穩(wěn)定運行的關鍵。該文根據氣象業(yè)務在日常和汛期對基礎設施資源需求的特點，設計了兩個目標函數來分別評價氣象云平臺的資源利用水平和其對重要核心業(yè)務的支撐保障，并在約束中考慮了功能組件與物理服務器的沖突關系等因素，將問題建模成一個多目標優(yōu)化問題。然后，通過適應度函數來綜合評價模型目標，設計一種改進蛙跳算法的氣象云資源調度方法。方法通過重新定義蛙跳算子，利用局部最優(yōu)交叉操作和最優(yōu)青蛙變異策略來迭代搜索問題的資源調度方案。最后，通過實驗仿真驗證了方法的效果。