基于膜計算和蟻群算法的融合算法在云計算資源調度中的研究

徐浙君,陳善雄

(1.浙江郵電職業技術學院,浙江 紹興 312000; 2.西南大學 計算機與信息科學學院,重慶 400715)

基于膜計算和蟻群算法的融合算法在云計算資源調度中的研究

徐浙君1,陳善雄2

(1.浙江郵電職業技術學院,浙江 紹興 312000; 2.西南大學 計算機與信息科學學院,重慶 400715)

針對云計算下的資源調度的問題,提出將蟻群算法的個體與云計算中的可行性資源調度進行對應,首先對云計算資源調度進行描述,其次針對蟻群算法的路徑選擇引入了平衡因子,對信息素進行了局部研究和全局研究,將蟻群個體引入到膜計算中,通過膜內運算和膜間運算,提高了算法的局部和全局收斂的能力,最后在云計算資源分配中,引入匹配表概念,將云計算任務和資源進行匹配,融合后的算法提高了算法的整體性能;仿真實驗說明在網絡消耗,成本消耗,能量消耗上有了明顯的降低,提高了資源分配效率。

蟻群算法;膜計算;平衡因子;信息素;匹配表

0 引言

自從云計算概念被提出來之后,有關云計算的方面的資源利用就成為了眾多系統供應商以及學者研究的對象,云計算的本質是一種集成了分布式計算,網格計算和網絡技術的互聯網概念,由于云計算中資源取決于用戶執行任務的效率,網絡的成本消耗和時間消耗等等約束條件,如何能夠更好的滿足這些約束條件進行云計算資源調度成為目前的研究方向[1-2]。國內外學者研究如下,文獻[3-4]提出了在云計算中使用粒子群算法進行云計算資源調度,仿真實驗說明改進的粒子群算法能夠有效的提高云計算下的資源分配效率,降低消耗的時間；文獻[5-7]提出了將改進的蟻群算法運用到云計算資源調度中,通過螞蟻個體的運動來描述云計算中的資源調度,仿真實驗表明該算法的總任務完成時間較短,具有較好的尋優能力,并且能夠實現負載均衡,是一種有效的資源調度算法；文獻[8]提出在云計算資源算法中引入布谷鳥算法,并對布谷鳥算法進行改進,使得改進后的算法收斂精度提高,能夠有效的提高云計算環境下的資源分配效率。

本文在云計算的資源調度中引入蟻群算法,將蟻群算法中的蟻群個體與云計算中的可行性資源調度進行對應,針對蟻群算法的不足進行改進,同時引入膜計算,使得改進后的粒子群算法和蟻群算法組成的融合算法在云計算的資源調度中節省了資源分配時間,提高了資源分配效率。

1 云計算資源調度描述

云系統中有n個任務的集合T={T1,T2,…Tn},資源節點集合G={G1,G2…Gn},前面描述了粒子群算法中一個粒子的位置就是一個可行解,因此任務Ti在資源Gj上完成,則粒子k的位置表示為Xk={x1,x2,…xi,…xn},其中xi表示任務i分配到資源為xi,因此Xk是一個可行的分配方案。本文采用文獻[11]描述的云計算資源調度模型, 綜合云計算中的各種條件,設置資源調度的約束函數表示為:

(1)

式中,Delay表示網絡延遲,Time表示執行時間,Source表示網絡消耗資源,A,B,C分別表示各自約束條件的權重。云計算分配的資源就是需要找到滿足函數最小值,從而使得云計算資源分配的成本,時間和網絡消耗都達到一個盡可能的最優值。

2 基本算法介紹

2.1 膜計算概述

膜計算是一種從生物細胞生成的啟發上得到來的算法,其概念是由歐洲科學院提出的,膜計算的本質主要模仿細胞在進行變換過程中的細胞內和細胞間之間的變換而抽象出來的一種計算模型。膜結構如圖1所示。

膜計算表示如下:

(2)

其中：V是輸入內容,T是輸出內容,μ表示膜結構,wx表示膜內對象,Rx表示膜內規則,ρx表示內部執行順序。膜算法具有的特點是:

(1)膜中的各個區域都是單獨,相互時間沒有直接聯系,膜內進行各自的計算,膜內的交流僅僅發生在相鄰的區域,這樣可以加速產生局部最優解。

(2)膜計算能夠有效的避免局部計算陷入最優,可以結合其他智能算法提高算法精度。

2.2 蟻群算法

蟻群算法是一種在模擬大自然中的螞蟻尋找食物的智能算法,螞蟻能夠尋找到食物主要依靠前面螞蟻所留下的信息素從而能夠指引前進,螞蟻個體所經歷過的路徑上的分泌的信息素越多,這樣引導后續的螞蟻走該條路徑上概率就越大,路徑概率的選擇和信息素更新選擇如下:

(3)

(4)

3 改進的蟻群算法

3.1 蟻群算法的不足

在蟻群算法的初始階段存在一定數量的隨機路徑(主要是路徑長度相對短的路徑),算法初始階段螞蟻個體會隨機的選擇的幾條路徑來進行尋找食物,通過在這些路徑上遺留下的信息素來引導后續的螞蟻前進,但是信息素的分布濃度與路徑的長度存在一定的關系,路徑越長信息素濃度越低,反之信息素濃度越高,信息素的變換效果直接影響到后續螞蟻的路徑選擇,需要注意的是螞蟻個體在每次遍歷之后,無論是最好的路徑還是最差的路徑,都會留下一定的信息素,因此,最差的路徑都會得到一定的信息素累計,這樣就會造成對后續螞蟻的影響,而出現無效的搜索,延遲了最優螞蟻個體所經過的路徑的產生。

3.2 針對選擇路徑的改進-平衡因子

蟻群算法中的螞蟻個體在前進的路徑的選擇上需要考慮信息素的濃度的大小,這樣的選擇有可能會出現最優路徑會被忽視,而陷入局部最優路徑的選擇中,其實在蟻群算法中的各個路徑上的相關信息素之間的差異并不大,為了盡可能的降低這種風險,在概率轉移規則中增加一個平衡因子來降低在搜索過程中的陷入局部最優解的影響,如果當前螞蟻尋找最短路徑的時候,就賦予該螞蟻個體高因子值,反之,則應該賦予該螞蟻個體低因子值.設置平衡因子如下:

(5)

式中,lmax和lmin分別代表螞蟻個體在當前迭代中所在路徑中長度的最大值和最小值,l(α)表示螞蟻個體所走的路徑的長度,A(i,j)表示在迭代中的路徑i→j的集合。設定螞蟻的總個數M,螞蟻選擇的其他經過點的數目為cad,本次迭代中經過路徑i→j的螞蟻個數為A(i,j),算法偽碼如表下所示。

表1 引入平衡因子算法偽碼

因此,通過上面的平衡因子的選擇得到目標的選擇的概率如下:

(6)

(7)

3.3 信息素優化

前述中已經描述了蟻群算法中的信息素是一個決定后續螞蟻是否前進選擇的重要的參考,對其信息素本身而言,本文進行2個方面的優化:

(1)局部信息素優化。

在進行選擇路徑的過程中,螞蟻個體每經過一條路徑之后,就會對路徑上的所有的信息素進行更新,這就是所謂的局部更新,在局部信息素更新中,螞蟻所走的路徑上的信息素是按照一定的比例揮發消失,因此減低了該路徑對于其他的螞蟻的吸引,從而提高了算法的迭代空間,在目前大部分的蟻群算法中,局部信息素的揮發因子是一個固定的常量,這樣的設置對于很多路徑上的信息素的揮發沒有說服力,因此本文在局部的信息素的更新上引入動態信息素揮發因子,該因子主要是可以用來動態的描述在信息素在不同情況下的揮發的變化情況。

(8)

(2)全局信息素更新。

當所有的螞蟻都進行完成第一次遍歷之后,假設有k只螞蟻通過路徑i→j,按照在迭代過程中的每只螞蟻走過的路徑對這k只螞蟻進行排序,按照從小到大的順序存儲這些螞蟻走過的路徑長度,記做list[k],因此信息素的更新如下:

(9)

在公式中,wr表示第r只螞蟻所經過的路徑上的信息量的更新程度,當list[r]值比較小的時候,第r只螞蟻走過的路徑小于其他螞蟻的路徑長度,則wr取正值,當全局更新信息素的時候,該只螞蟻會增大路徑上的信息量。當list[r]值比較大的時候,第r只螞蟻走過的路徑大于其他螞蟻的路徑長度,則wr取負值,該只螞蟻在全局信息素會降低。

4 基于膜計算和蟻群算法的融合算法在云計算資源調度

4.1 設定匹配表

為了更好的適應云計算下的資源的調度,而資源的分配對應不同的節點完成的任務,特別是在云計算中涉及的資源種類比較繁多,相同類型的任務能夠獲得相同的資源進行處理,在對應的任務和資源之間,加入一個匹配表。這樣可以更加有效的匹配云計算下的任務和資源。在匹配表中,每一個云計算的任務通過匹配表找到對應的節點序列,在節點序列中按照節點使用頻率的高低進行排列，通常優先級高的會被選中。因此螞蟻個體在尋找出發節點的時候，如果螞蟻個體對應的云計算任務對應的節點在匹配表中存在,則選擇節點強度最大的節點為初始節點, 否則選隨機節點為初始節點。當最后查找到需要的節點時候,將該節點添加到匹配表中。

4.2 基于膜計算和蟻群算法的融合算法的云計算資源調度

4.2.1 算法融合

蟻群算法的缺點是容易陷入局部最優，根據云計算中資源分配的要求，蟻群算法顯然在一定程度上無法能夠更好的分配云計算的資源，膜計算的優點在于能夠通過膜內運算和膜間運算，合理的避免產生局部最優的可能。因此兩種算法的融合可以很好的提高蟻群算法的效率，從而確定最優解。進而可以有效的獲得云計算中的資源分配效率。

4.2.2 編碼規則

4.2.3 算法內容描述

圖1描述的膜結構中情況，以其中的某一個膜為例，5當作主膜,膜6,7,8當作輔助膜。主膜是提高蟻群算法個體的全局最優能力,同時接受來自其他膜中傳遞過來的優異的螞蟻個體,從而進一步保證能夠進行全局最優，輔助膜主要是針對蟻群算法的搜索空間進行局部搜索,為主膜提供局部最優解。

步驟1:輔助膜6內在進行迭代的時候,根據螞蟻個體對應的適應度的優劣進行從小到大的排序,從中選擇優秀的螞蟻個體到主膜中。轉換規則如下:

(10)

步驟2:輔助膜7中按照公式改進的信息素和概率選擇更新蟻群個體,迭代中按照從小到大進行排序,將最差的蟻群個體重新進行初始化操作,再次進行排序。

(11)

步驟3:輔助膜8中的的螞蟻個體按照螞蟻算法的步驟進行,迭代更新的結果進行從小到大的排序,如同上面的步驟一樣送入到主膜中。

(12)

步驟4:按照公式(6),(7)計算主膜中的螞蟻個體。通過前述的步驟,將從輔助膜中傳遞的蟻群個體進行排序。按照如下的規則進行排序。

(13)

步驟5:如果達到最大迭代次數,則退出迭代,最優的螞蟻個體即是最佳云計算資源分配方案,否則繼續執行步驟2。

(14)

算法流程如圖2所示。

圖2 算法流程

5 實驗與分析

為了驗證本文算法具有的有效性和可行性,本文采用Cloudsim平臺來模擬云計算環境,在平臺中對DataCenterBroker類,Cloudlet類,CloudCoordinator類進行了重寫,初始化蟻群算法和膜計算的各個相應的參數,同時設置最大迭代次數。

文獻[9]和文獻[10]是關于云計算資源調度中較新的研究算法,將本文的算法與這兩種算法進行云計算的資源比較,從節點能量消耗,時間消耗和帶寬消耗上進行比較,設定虛擬任務為1 000個,虛擬資源為100個,從圖3～5中發現,本文算法在能量消耗,完成時間方面和成本消耗方面低于其他的云計算調度算法,在能量消耗方面,時間消耗和帶寬消耗相比于其他兩種算法平均降低了7.12%,10.18%和6.21%,本文算法能夠有效的降低了能量消耗,能夠有效的降低云計算中的資源調度所帶來的能量消耗的問題。

圖3 3種算法的能量消耗比較

圖4 3種算法的時間消耗比較

圖5 3種算法的網絡消耗帶寬比較

6 結束語

針對云計算的資源調度的問題,本文引入了膜計算和蟻群算法,首先對蟻群算法中的路徑與信息素的匹配進行改進,其次針對信息素所處狀態的不同進行局部更新和全局更新,最后將蟻群個體融入到膜計算中,融合后的算法提高了算法效率,CloudSim實驗說明本文算法能夠有效的提高云計算的資源分配效率,節省時間和降低能量消耗.

[1] 李 喬.云計算研究現狀綜述[J].計算機科學,2011,38(4):32-36.

[2] 葛 新.基于云計算集群擴展中的調度問題研究[D].合肥:中國科學技術大學,2011.

[3] 蔡 琪,單冬紅,趙偉艇.改進粒子群算法的云計算環境資源優化調度[J].遼寧工程技術大學學報(自然科學版),2015,35(1):93-96.

[4] 周麗娟,王春影.基于粒子群優化算法的云計算資源調度策略研究[J].計算機科學,2015,42(6):279-283.

[5] 張煥青,張學平,王海濤,等.基于負載均衡蟻群優化算法的云計算任務調度[J].微電子學與計算機,2015,32(5):31-35.

[6] 王常芳,徐文忠.一種用于云計算資源調度的雙向蟻群優化算法[J].計算機測量與控制,2015,23(8):2861-2863.

[7] 蔣 華,張樂乾,王 鑫.基于多維評價模型及改進蟻群優化算法的云計算資源調度策略[J].計算機測量與控制,2015,23(7):2559-2562.

[8] 葉華喬,丁善婷.基于改進的布谷鳥算法在云計算資源的研究[J],計算機測量與控制,2014,22(12):4150-4154.

[9] 趙宏偉,李圣普.基于粒子群算法和RBF神經網絡的云計算資源調度方法研究[J].計算機科學,2016,43(3):113-116.

[10] 嵇可可.基于動態趨勢預測蟻群算法的云計算資源調度優化研究[J].科技通報,2016,32(1):187-190.

[11] 寧 彬,谷 瓊,吳 釗.基于膜計算的蝙蝠算法在云計算資源調度的研究[J].計算機應用研究,2015,32(3):830-83.

Research of Fusion Algorithm Based on Membrane Computing and Ant Colony Algorithm in Cloud Computing Resource Scheduling

Xu Zhejun1, Chen Shanxiong2

(1.Zhejiang Technical College of Posts&telecom,Shaoxing 312000,China; 2.College of Computer and Information Science,Southwest Universtiy,Chongqing 400715,China)

Aiming at the issue of resource scheduling in cloud computing, this paper proposes to correspond individuals in ant colony algorithm with feasibility resource scheduling in cloud computing. Firstly, it describes resource scheduling in cloud computing and then aiming at the path choice of ant colony, balancing factor is introduced for global research into pheromone, and individual ants are introduced into the calculation of membrane. The membrane computing and membrane operations have improved the ability of local and global convergence. Finally, in resource allocation of cloud computing, the concept of matching table is introduced to match tasks and resources in cloud computing. The integrated algorithm has improved the entire performance of the algorithm, and simulation platform experiment shows that it has reduce the network consumption, cost consumption and energy consumption as well as the resource allocation efficiency.

ant colony algorithm; membrane computing; balancing factor; pheromone; matching table

2016-06-29；

2016-08-17。

國家自然基金項目(61303227)。

徐浙君(1980-),男,講師，碩士,主要從事數據挖掘和云計算方向的研究。

1671-4598(2017)01-0127-04

10.16526/j.cnki.11-4762/tp.2017.01.036

TP3

A