云平臺下任務調度的克隆選擇范文

本站小編為你精心準備了云平臺下任務調度的克隆選擇參考范文，愿這些范文能點燃您思維的火花，激發您的寫作靈感。歡迎深入閱讀并收藏。

《計算機應用研究雜志》2015年第五期

1問題建模和相關定義

1.1工作流任務模型工作流任務由存在相互依賴關系的子任務構成，這些子任務構成有向無環圖(DirectedAcyclicGraph，DAG)，用二元組表示為G=(N,E)，其中N代表一組節點，E代表連接節點的邊，邊上的數字代表邊的權重。典型的DAG工作流任務模型如圖1所示。

1.2相關定義用T表示DAG中的節點集合，用來描述任務集T={t1,t2,…,tn}，n表示任務總數。用E表示有向邊的集合，用來描述任務之間的依賴關系，E={eij|eij=(ti,tj),eij∈T×T}，任務tj必須在其前驅任務執行完成后才能開始處理。任務的完成時間、執行費用定義和計算方法如下，其中相關符號說明如表1所示。假定任務ti分配在資源Rk上執行，tr(Rk)表示資源Rk的通信能力，data(ti,tj)表示任務ti和tj之間數據傳輸的通信量，本文采用式1來計算任務ti到tj數據傳輸的通信時間。cp(Rk)表示資源Rk的計算性能，load(ti)表示任務ti的計算量，本文采用式2來計算任務ti在資源Rk上的執行時間.

2TCCS任務調度算法

受生物克隆選擇機理的啟發，DeCastro[12]等人提出克隆選擇算法，其本質是一種高效、并行的全局搜索方法。本文基于CSA思想，提出一種TCCS改進算法。

2.1染色體編碼本文采用字符編碼方式，將任務占用的資源序列編碼為染色體。假定工作流任務包含10個任務，云平臺提供5個可用資源，則染色體長度為10，每個基因取值為1~5之間的隨機數。染色體的編碼如圖2所示，任務1資源1上面執行，任務2在資源3上面執行，以此類推。

2.2種群初始化在GSA中，初始化種群對算法性能有重要的影響。隨機種群可能導致算法收斂過慢，或者最終結果不夠理想。本文認為DAG中任務所處層級越高，則任務優先級越高，如圖1中任務t1級別高于任務t4。本文采用前驅任務優先調度策略快速生成可用初始種群.

2.3親和度函數親和度函數的選取至關重要，直接影響到算法的收斂速度和最優解的查找。本文將工作流任務完成所需要的時間和經濟成本的加權值作為親和度函數，因此需要對這兩種屬性的數據進行無量綱化處理。對于每一批進化的種群，用minFinish表示該批種群中任務完成時間最小值，maxFinish表示任務完成時間最大值，用minCost表示該批種群中經濟成本最小值，maxCost表示經濟成本最大值。則親和度函數可表示為公式10，其中ω1和ω2為任務完成時間和經濟成本的加權因子，且ω1+ω2=1.

2.4免疫基因操作本文采取交叉變異和基因變異兩步對抗體進行免疫基因操作，以增加抗體種群的多樣性，避免種群過早收斂。交叉變異將兩個抗體交換基因片段，形成兩個新的個體。它可以促進不同抗體之間的基因交流，有利于豐富種群的多樣性。交叉變異可以表示為公式11，每次隨機選取抗體中相同位置的連續兩位基因片段進行交換，其中n表示工作流任務的個數。基因變異將是在基因編碼的層面對抗體進行變異。本文選取交換突變的方式進行基因變異。在抗體基因編碼中，隨機選擇兩個位置，并交換其取值。例如抗體基因編碼為：1423542351，隨機選取第3位與第9位基因編碼進行交換突變，則突變的結果為1453542321。

2.5克隆選擇算法步驟n表示任務總數，m表示資源節點數，N表示迭代代數最大值。步驟一：抗體初始化。本文根據4.2介紹的初始種群生成方式生成一組可行的調度方案，采用實數編碼方式對任務所分配的資源序號進行編碼。步驟二：親和度計算。按照公式8計算抗體親和度f(ti)，本文選取ω1=ω2=0.5，表示任務完成時間和任務執行成本權重相同。f(ti)的值越小，表示解越優，若f(ti)達到理想值f*，或迭代次數達到最大值N，則停止計算，否則繼續。步驟三：抗體選擇。按一定的概率ρr選擇親和度高的抗體形成一個臨時抗體群tmp{r}。步驟四：抗體克隆。tmp{r}中的抗體獨立進行克隆，親和度越高的抗體，抗體克隆的數量越多，抗體t的克隆數目Ci如式12所示，其中α為克隆調節系數，fmax為當前抗體中的最大親和度，M為群體規模。

3實驗結果與分析

3.1實驗目的為驗證TCCS算法的正確性和有效性，本文設計了云平臺工作流任務調度的仿真實驗，并在相同實驗條件下與遺傳算法進行對比。實驗主要在算法收斂時間、任務完成時間—經濟成本加權值兩個方面進行比較。

3.2實驗環境實驗采用開源云仿真平臺CloudSim[13]，它是澳大利亞墨爾本大學網格實驗室和Gridbus項目組推出的云計算仿真軟件。在該試驗平臺上分別測試了上述兩種算法的調度時間、任務完成時間和經濟成本。對圖1所示的工作流任務，實驗的相關參數取值如下：1)任務：每個任務的計算量隨機產生，取值范圍為[100,500]，本次實驗中任務的計算量取值如下，單位是MI:Load={120,472,255,398,161,340,263,117,382,453}。前驅任務與后繼任務之間的數據傳輸量如圖1所示。2)虛擬機：計算資源中虛擬機的個數為5，計算能力取值為cp={2,4,6,8,10}，單位是MIPS。虛擬機之間的通信能力矩陣如下Tr所示，單位是ms(millisecond).3)參考SinaAppEnginge[14]的服務價格，設置資源任務計算的服務單價為0.03，通信帶寬的服務單價為0.2。4)加權因子：設置任務完成時間和經濟成本的加權因子ω1=0.5，ω2=0.5。

3.3實驗結果分析本文選擇遺傳算法GA與TCCS算法進行對比試驗。TCCS算法的相關參數設置為：種群規模為20，交叉變異與突變概率均為0.5，抗體記憶的比例為0.05。GA的相關參數為：種群規模為20，交叉變異與突變概率均為0.5。兩個算法終止條件均為迭代500次后終止。實驗中，兩個算法的種群規模均為20，則算法的收斂速度取決于種群對問題空間的搜索能力。圖3、圖4為兩種算法分別重復運行10次的實驗結果。實驗1：算法收斂時間對比測試算法收斂時間是指算法從執行開始到算法收斂的時間，值越小，算法的執行時間越短，可以更快的得到任務調度的結果。兩種算法的收斂時間測試結果如圖3所示。從圖3中可以看出，TCCS算法收斂時間在4S以下的實驗占60%，10次實驗的平均收斂時間為4.21S，GA收斂時間在4S以下的實驗占僅為10%，10次實驗的平均收斂時間為5.64S。可見TCCS算法收斂速度相對GA較快，這是因為TCCS算法在種群初始階段，采用簡單策略生成一批可用的初始種群，避免了隨機種群引起算法收斂速度慢的問題。實驗2：任務完成時間與經濟成本加權值對比測試任務完成時間與經濟成本加權值通過公式10進行計算，該值越小，表明算法探索任務完成時間與經濟成本多目標優化問題最優解的性能越好。兩種算法的工作流任務調度測試結果如圖4所示。從圖4中可以看出，TCCS算法10次實驗的任務完成時間與經濟成本平均加權值為0.51，最小值為0.29，加權值在0.6以下的實驗占70%，GA10次實驗的任務完成時間與經濟成本平均值為0.63，加權值在0.6以下的僅為40%。可見TCCS算法探索任務完成時間與經濟成本最優解方面性能更優，這是因為TCCS算法在傳統克隆選擇算法的基礎上增加了交叉變異算子，在抗體種群多樣性方面進行了優化。

4結束語

本文結合云計算的特點，提出了一種對任務完成時間，經濟成本多目標優化的克隆選擇改進算法。在CloudSim仿真平臺下，把TCCS算法與解決任務調度問題常用的GA進行了對比實驗。實驗表明，TCCS算法是有效的。需要注意的是，本文只考慮了任務完成時間和任務執行的經濟成本的多目標優化，沒有考慮云平臺下資源的負載均衡問題，這也是本文下一步的研究重點。

作者：徐立 梁意文 單位：武漢大學 計算機學院