云計(jì)算對于完工時(shí)間最小化問題的算法研究①

(滁州職業(yè)技術(shù)學(xué)院,安徽 滁州 239000)

0 引 言

對于云計(jì)算服務(wù)問題的研究，眾多學(xué)者從各個(gè)方面提出了對應(yīng)的解決方法，實(shí)現(xiàn)云計(jì)算服務(wù)的效益的最大化。吳小紅、王翠娥等人(2012)針對于響應(yīng)時(shí)間提高這一指標(biāo)，提出了DSIC機(jī)制來確保在最短的時(shí)間內(nèi)顯示資源成本信息，使得達(dá)到響應(yīng)時(shí)間最小化的目標(biāo)[1]。楊柳、唐卓等人(2012)對響應(yīng)時(shí)間與成本消耗進(jìn)行了綜合考慮，在隨機(jī)規(guī)劃理論的基礎(chǔ)上提出了虛擬分配的優(yōu)化算法，實(shí)現(xiàn)資源的有效調(diào)度與分配[2]。景維鵬，邢樂樂等人(2013)同樣采用時(shí)間與費(fèi)用的雙重約束條件，提出了一種改進(jìn)的作業(yè)調(diào)度算法來縮短響應(yīng)的時(shí)間[3]。從現(xiàn)有的研究上來看，都提出了改良算法，主要是從時(shí)間響應(yīng)上來進(jìn)行約束。但是卻很少從路由傳輸這一角度出發(fā)考慮來減少時(shí)間響應(yīng)。

1 系統(tǒng)模型建立

數(shù)據(jù)中心與鏈路集合共同組成了網(wǎng)絡(luò)圖，對此假設(shè)這三個(gè)集合分別為V={D1,D2,…,Dβ}、鏈路E與G=(V,E)。數(shù)據(jù)中心的服務(wù)器并不是單一存在的，假設(shè)服務(wù)器共計(jì)有γ個(gè)，則可記為={s1,s2,…,sγ}。每個(gè)服務(wù)器都是γ×β二元矩陣，可用其中：

(1)

Du與Dv之間的傳輸?shù)逆溌?u,v)的延時(shí)假設(shè)為luv，那么鏈路集合則為β×β的矩陣，可用ML表示，表達(dá)式如下(2)所示[4]。

ML={luv},?(u,v)∈E

(2)

2 問題模型構(gòu)建

2.1 任務(wù)映射

(3)

該約束條件指出每一個(gè)任務(wù)都需要與服務(wù)器連接，也就是說任務(wù)必須有服務(wù)器處理，則：

(4)

對于資源容量的約束來說，所分配的任務(wù)資源需求容量不能超過服務(wù)器所能提供的總?cè)萘?，故此有如下的條件(5)：

(5)

在計(jì)算時(shí)間上，其實(shí)際時(shí)間ei與任務(wù)規(guī)模Ti呈正相關(guān)，對此得到約束條件(6)，其中P0為處理速度。

(6)

(7)

滿足通用性原理，任務(wù)是通過隨機(jī)方式來實(shí)現(xiàn)公正分配，假設(shè)φ(j)為sj服務(wù)器上對接收任務(wù)的計(jì)算時(shí)間，那么我們可以得到(8)

(8)

那么，服務(wù)器sj映射下一個(gè)任務(wù)時(shí)所需要的最大的等待時(shí)間可以如下表示：

(9)

因此，服務(wù)器上的新任務(wù)Ti的預(yù)期最長周轉(zhuǎn)時(shí)間ωi可表示為：

(10)

2.2 任務(wù)路由傳輸

任務(wù)路由傳輸，首先是要確定鏈路是否起到任務(wù)傳輸?shù)淖饔?，可以通過引入(u,v)∈來進(jìn)行確認(rèn)，如(11)所示[5]：

(11)

對于任務(wù)分配來說，其分配的服務(wù)器并不是與當(dāng)前的數(shù)據(jù)中心是對應(yīng)的，但是一般來說為減少時(shí)間與消耗成本常采用同一數(shù)據(jù)中心的鏈路，對此可以得到(12)。

(12)

通過服務(wù)器的映射矩陣MTS可以得到一個(gè)α×β矩陣MTD,MTD=MTS×MSD，該矩陣反映了映射關(guān)系。對于每一個(gè)任務(wù)來說，其傳輸必須擁有一條傳輸鏈路，中間的數(shù)據(jù)中心需要保持?jǐn)?shù)據(jù)流量的均衡性，綜合考慮可以用以下(13)關(guān)系式來表達(dá)。

(13)

此外，每條鏈路上所有任務(wù)的總流量必須在其容量范圍內(nèi)，即：

(14)

根據(jù)每一個(gè)任務(wù)的傳輸延時(shí)可以得到總?cè)蝿?wù)量的傳輸延時(shí)的大小γi，即路由器傳輸?shù)难訒r(shí)，具體如下(15)所示：

(15)

考慮到云計(jì)算最重要的考核指標(biāo)，任務(wù)器傳輸延時(shí)與傳輸任務(wù)的等待時(shí)間不應(yīng)該超過其時(shí)間限制?，對此可以得到以下約束關(guān)系式：

ωi+γiζ,?i=1,2,…,α

(16)

2.3 IPQC問題

根據(jù)前面所提到的約束條件，可以將上述的建模簡化為一個(gè)IPQC問題，即具有二次約束的整數(shù)規(guī)劃問題，如(17)：

(17)

在這些約束中，式(5)和(13)是二次約束條件。IPQC問題屬于NP難題，其主要解決的辦法包括分解算法、割平面法以及外逼近法等等，但是這些算法運(yùn)用只適合于特定的IPQC，并且在算法上存在計(jì)算冗雜，計(jì)算時(shí)間長等問題，目前沒有一個(gè)有效的通用算法來進(jìn)行解決。為決絕IPQC問題最有效的途徑就是將其線性化，采用增加變量與約束條件的方式將函數(shù)問題轉(zhuǎn)化為線性函數(shù)，從而極大地簡化問題[6]。對此提出了啟發(fā)式算法，其算法在后面詳細(xì)介紹。

3 啟發(fā)式算法設(shè)計(jì)

圖1 小規(guī)模網(wǎng)絡(luò)環(huán)境下三種算法的完工時(shí)間性能比較

算法1: 最優(yōu)擬合遞增型任務(wù)映射算法

輸出：新任務(wù)的映射矩陣MTS

1：MTS←{0}

2：T′←根據(jù)任務(wù)規(guī)模對所有新的任務(wù)進(jìn)行遞增排序

3：S′←根據(jù)服務(wù)器寄存的任務(wù)數(shù)量對所有服務(wù)器遞增排序

4：for 所有Ti∈T′,?i=1,2,…,αdo

金沙江區(qū)域內(nèi)地質(zhì)構(gòu)造復(fù)雜，生態(tài)環(huán)境脆弱。為此，項(xiàng)目施工過程中，在作業(yè)場地設(shè)置了沉淀池，廢水經(jīng)過沉淀后用于灑水抑塵，不外排；對臨時(shí)施工場地以及運(yùn)輸?shù)缆范ㄆ跒⑺?，減少地面揚(yáng)塵；做好水土保持工作，最大限度保護(hù)好當(dāng)?shù)厣鷳B(tài)環(huán)境，并在工程結(jié)束后進(jìn)行植被恢復(fù)；嚴(yán)格控制炸礁、疏浚作業(yè)范圍，并在魚類繁殖季節(jié)不進(jìn)行施工，同時(shí)建立魚類臨時(shí)救護(hù)機(jī)制，若發(fā)現(xiàn)珍稀保護(hù)魚類，項(xiàng)目部在漁政部門指導(dǎo)下進(jìn)行救護(hù)，通過增殖放流，恢復(fù)魚類資源。

5：for 所有sj∈S′,?j=1,2,…,γdo

6：ifsj可滿足Ti的資源要求 then

8S′←根據(jù)寄存的任務(wù)數(shù)量對所有服務(wù)器再次遞增排序

9：break

10：end if

11：end for

12：end for

首先對其進(jìn)行初始化，再根據(jù)任務(wù)的規(guī)模進(jìn)行排序與存儲，算法1的復(fù)雜度的為O(γ·N)，當(dāng)輸入變量后就可以得到映射矩陣。在實(shí)際的云計(jì)算中，數(shù)據(jù)任務(wù)規(guī)模是非常龐大的，因此需要尋找最短的傳輸路徑來減少時(shí)間等待與傳輸延時(shí)效應(yīng)。對此最短路徑的尋找可以利用基于整數(shù)規(guī)劃的算法2來完成。將前面的映射結(jié)果作為輸入的變量，在最終結(jié)果中就可以得到最優(yōu)的傳輸路徑。

算法2: 基于IP的路徑尋找算法

輸入：網(wǎng)絡(luò)圖，任務(wù)集合及任務(wù)映射算法提供的

1：MTD←MTS×MSD

4 性能評估

4.1 小規(guī)模網(wǎng)絡(luò)的預(yù)期最大完工時(shí)間

在小規(guī)模網(wǎng)絡(luò)環(huán)境下三種算法的完工時(shí)間性能比較中，如圖1(a)中所示，隨著任務(wù)量的不斷增長，這三種方法的完工時(shí)間也同樣出現(xiàn)增長的趨勢，也就是所完工時(shí)間是與任務(wù)量的多少成正比的，同時(shí)在相同任務(wù)量的情況之下啟發(fā)式算法的完工時(shí)間明顯要低于其他兩種算法。如圖1(b)所示，鏈路容量變化情況下各算法之間的響應(yīng)時(shí)間的發(fā)展趨勢。當(dāng)容量從800增長至1600時(shí)，兩種階段啟發(fā)式算法所得到的完工時(shí)間呈現(xiàn)不斷下降趨勢但是下降幅度并不是很大，F(xiàn)FD-MEM與BFD-MEM這兩種方法同樣呈現(xiàn)遞減的趨勢，相較而言在容量一定時(shí)提出的啟發(fā)式算法性能更優(yōu)。如圖1(c)所示，隨著服務(wù)器中新舊任務(wù)概率變化時(shí)三種算法的完工時(shí)間指標(biāo)變化情況。當(dāng)新舊任務(wù)概率不斷增加時(shí)，各算法之間的完工時(shí)間均在不斷增加，造成這樣的原因在于概率越大造成任務(wù)的等待時(shí)間越長從而增加了完工時(shí)間。綜合不同情況下的三種算法得到的完工時(shí)間的長短來看，階段啟發(fā)式算法的時(shí)間性能明顯要優(yōu)于其他兩種算法。

4.2 大規(guī)模網(wǎng)絡(luò)的預(yù)期最大完工時(shí)間

在大規(guī)模網(wǎng)絡(luò)中路徑尋找是關(guān)鍵，對此與最為常用的尋找路徑的Dijkstr、 SPFA算法相結(jié)合，同樣來探尋任務(wù)量、流量以及新舊任務(wù)這種情況下的完工時(shí)間變化，最大完工時(shí)間之和與新任務(wù)數(shù)量間的關(guān)系圖2所示。其中，圖2(a)是IP-PFA的任務(wù)映射啟發(fā)式算法仿真圖，圖2(b)是Dijk.CAP的任務(wù)映射啟發(fā)式算法仿真圖，圖2(c)SPFA.CAP的任務(wù)映射啟發(fā)式算法仿真圖，圖2(d)BFI與最短路徑尋找算法相結(jié)合仿真圖。

圖2 最大完工時(shí)間之和與新任務(wù)數(shù)量間的關(guān)系

圖3 最大完工時(shí)間之和與鏈路容量間的關(guān)系

仿真結(jié)果如下圖3所示。其該三種算法的完工時(shí)間的性能變化趨勢與小規(guī)模網(wǎng)絡(luò)情況下的相一致。云計(jì)算的完工時(shí)間會隨著任務(wù)量以及新舊任務(wù)概率的增長而不斷增加，會隨著鏈路容量的增加而呈現(xiàn)出遞減的趨勢。

圖4 大規(guī)模網(wǎng)絡(luò)環(huán)境下三種算法的完工時(shí)間性能比較

但綜合這三種算法得到的最大響應(yīng)時(shí)間來看，如圖4所示。兩階段啟發(fā)式算法的完工時(shí)間最小，性能是最優(yōu)的， 也就說該算法達(dá)到了性能優(yōu)化的目的。

5 結(jié) 論

研究表明，從任務(wù)映射與路由傳輸兩個(gè)方面進(jìn)行綜合性考慮來進(jìn)一步縮小完工時(shí)間，達(dá)到快速響應(yīng)的目的。將研究的問題簡化成IPQC問題，并提出了一種多項(xiàng)式時(shí)間復(fù)雜度的啟發(fā)式算法來進(jìn)一步對問題實(shí)現(xiàn)線性簡化。通過全面的仿真實(shí)驗(yàn)，證明該算法的效率接近于最優(yōu)解，效率較高，且性能遠(yuǎn)優(yōu)于當(dāng)前其他請求響應(yīng)算法，證明了兩階段啟發(fā)算法在云計(jì)算中的有效性。