云計(jì)算對(duì)完工時(shí)間最小化算法研究范文

本站小編為你精心準(zhǔn)備了云計(jì)算對(duì)完工時(shí)間最小化算法研究參考范文，愿這些范文能點(diǎn)燃您思維的火花，激發(fā)您的寫作靈感。歡迎深入閱讀并收藏。

摘要:目前對(duì)云服務(wù)供應(yīng)進(jìn)行的研究主要圍繞任務(wù)映射展開，其中如何將面向服務(wù)的任務(wù)分布給服務(wù)器以實(shí)現(xiàn)完工時(shí)間最小化成為該領(lǐng)域內(nèi)的難點(diǎn)?？偨Y(jié)后發(fā)現(xiàn)，未能實(shí)現(xiàn)完工時(shí)間最小化的重要原因是沒有考慮到任務(wù)路由器傳輸所造成的影響，鑒于此提出一種多項(xiàng)式時(shí)間復(fù)雜度的啟發(fā)式算法。實(shí)驗(yàn)結(jié)果表明，該算法的效率接近于最優(yōu)解，效率較高且性能遠(yuǎn)優(yōu)于當(dāng)前其他算法。

關(guān)鍵詞:云服務(wù);映射;時(shí)間;啟發(fā)式算法;最優(yōu)解

引言

對(duì)于云計(jì)算服務(wù)問題的研究，眾多學(xué)者從各個(gè)方面提出了對(duì)應(yīng)的解決方法，實(shí)現(xiàn)云計(jì)算服務(wù)的效益的最大化。吳小紅、王翠娥等人(2012)針對(duì)于響應(yīng)時(shí)間提高這一指標(biāo)，提出了DSIC機(jī)制來確保在最短的時(shí)間內(nèi)顯示資源成本信息，使得達(dá)到響應(yīng)時(shí)間最小化的目標(biāo)［1］。楊柳、唐卓等人(2012)對(duì)響應(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ò)圖，對(duì)此假設(shè)這三個(gè)集合分別為V=D1，D2{，…，D}β、鏈路E與G=(V，E)。數(shù)據(jù)中心的服務(wù)器并不是單一存在的，假設(shè)服務(wù)器共計(jì)有γ個(gè)，則可記為S=s1，s2{，…，s}γ。每個(gè)服務(wù)器都是γ×β二元矩陣，可用MSD=MSD{}ij，i=1，2，…，γj=1，2，…，β，其中：Du與Dv之間的傳輸?shù)逆溌?u，v)的延時(shí)假設(shè)為luv，那么鏈路E集合則為β×β的矩陣，可用ML表示，表達(dá)式如下(2)所示［4］。ML={l}uv，(u，v)∈E(2)在云計(jì)算服務(wù)中，當(dāng)收到數(shù)據(jù)請(qǐng)求時(shí)，會(huì)形成任務(wù)T=T1，T2{，…，T}α，并根據(jù)任務(wù)來對(duì)資源需求規(guī)模T進(jìn)行估算。鑒于時(shí)間ζ約束的云計(jì)算服務(wù)，任務(wù)資源可以用θ×α的矩陣QRT=QRT{}ki，k=1，2，…，θ，i=1，2，…，α表示，其中QRTki是Ti對(duì)資源Rk的需求量。對(duì)此，可以在數(shù)據(jù)控制室直接確定某一時(shí)間區(qū)間內(nèi)的ARS與QRT的容量。

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

2．1任務(wù)映射任務(wù)完成的約束條件:假若任務(wù)—服務(wù)器映射關(guān)系為一個(gè)α×γ的矩陣MTSij，其具體表達(dá)式如下(3)所示:該約束條件指出每一個(gè)任務(wù)都需要與服務(wù)器連接，也就是說任務(wù)必須有服務(wù)器處理，則:對(duì)于資源容量的約束來說，所分配的任務(wù)資源需求容量不能超過服務(wù)器所能提供的總?cè)萘?，故此有如下的條件(5):在計(jì)算時(shí)間上，其實(shí)際時(shí)間ei與任務(wù)規(guī)模Ti呈正相關(guān)，對(duì)此得到約束條件(6)，其中P0為處理速度。對(duì)于等待時(shí)間來說，這是在工作周期內(nèi)因任務(wù)未完成從而造成等待時(shí)間。若未完成任務(wù)有N0個(gè)，那服務(wù)器是初始的任務(wù)狀態(tài)可以用N0×γ矩陣M～T^S=M～T^S{}ij，i=1，2，…，N0，j=1，2，…，γ表示，其表示公式如下(7)所示:滿足通用性原理，任務(wù)是通過隨機(jī)方式來實(shí)現(xiàn)公正分配，假設(shè)φ(j)為sj服務(wù)器上對(duì)接收任務(wù)的計(jì)算時(shí)間，那么我們可以得到(8)那么，服務(wù)器sj映射下一個(gè)任務(wù)時(shí)所需要的最大的等待時(shí)間可以如下表示:因此，服務(wù)器上的新任務(wù)Ti的預(yù)期最長周轉(zhuǎn)時(shí)間ωi可表示為:

2．2任務(wù)路由傳輸任務(wù)路由傳輸，首先是要確定鏈路是否起到任務(wù)傳輸?shù)淖饔?，可以通過引入(u，v)∈E來進(jìn)行確認(rèn)，如(11)所示［5］:對(duì)于任務(wù)分配來說，其分配的服務(wù)器并不是與當(dāng)前的數(shù)據(jù)中心是對(duì)應(yīng)的，但是一般來說為減少時(shí)間與消耗成本常采用同一數(shù)據(jù)中心的鏈路，對(duì)此可以得到(12)。通過服務(wù)器的映射矩陣MTS可以得到一個(gè)α×β矩陣MTD，MTD=MTS×MSD，該矩陣反映了映射關(guān)系。對(duì)于每一個(gè)任務(wù)來說，其傳輸必須擁有一條傳輸鏈路，中間的數(shù)據(jù)中心需要保持?jǐn)?shù)據(jù)流量的均衡性，綜合考慮可以用以下(13)關(guān)系式來表達(dá)。此外，每條鏈路上所有任務(wù)的總流量必須在其容量范圍內(nèi)，即:根據(jù)每一個(gè)任務(wù)的傳輸延時(shí)可以得到總?cè)蝿?wù)量的傳輸延時(shí)的大小γi，即路由器傳輸?shù)难訒r(shí)，具體如下(15)所示:考慮到云計(jì)算最重要的考核指標(biāo)，任務(wù)器傳輸延時(shí)與傳輸任務(wù)的等待時(shí)間不應(yīng)該超過其時(shí)間限制，對(duì)此可以得到以下約束關(guān)系式:2．3IPQC問題根據(jù)前面所提到的約束條件，可以將上述的建模簡化為一個(gè)IPQC問題，即具有二次約束的整數(shù)規(guī)劃問題，如(17):在這些約束中，式(5)和(13)是二次約束條件。IPQC問題屬于NP難題，其主要解決的辦法包括分解算法、割平面法以及外逼近法等等，但是這些算法運(yùn)用只適合于特定的IPQC，并且在算法上存在計(jì)算冗雜，計(jì)算時(shí)間長等問題，目前沒有一個(gè)有效的通用算法來進(jìn)行解決。為決絕IPQC問題最有效的途徑就是將其線性化，采用增加變量與約束條件的方式將函數(shù)問題轉(zhuǎn)化為線性函數(shù)，從而極大地簡化問題［6］。對(duì)此提出了啟發(fā)式算法，其算法在后面詳細(xì)介紹。

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

根據(jù)前面闡述的約束問題，可以歸結(jié)于兩點(diǎn)，一個(gè)服務(wù)器裝箱問題與數(shù)據(jù)流量傳輸管理問題，對(duì)此，根據(jù)云計(jì)算的時(shí)限指標(biāo)以及其約束條件設(shè)計(jì)了兩個(gè)階段的啟發(fā)式算法1與算法2，具體如下:算法1:最優(yōu)擬合遞增型任務(wù)映射算法輸入:網(wǎng)絡(luò)圖G=(V，E)，新的任務(wù)集合T，ARS，QRT，M～T^S;輸出:新任務(wù)的映射矩陣MTS1:MTS←{}02:T'←根據(jù)任務(wù)規(guī)模對(duì)所有新的任務(wù)進(jìn)行遞增排序3:S'←根據(jù)服務(wù)器寄存的任務(wù)數(shù)量對(duì)所有服務(wù)器遞增排序4:for所有Ti∈T'，i=1，2，…，αdo5:for所有sj∈S'，j=1，2，…，γdo6:ifsj可滿足Ti的資源要求then7:MTSij←18S'←根據(jù)寄存的任務(wù)數(shù)量對(duì)所有服務(wù)器再次遞增排序9:break10:endif11:endfor12:endfor13:ωi←∑γj=1MTSij(•φ())j，i=1，2，…，α;約束為(8)，(9)．首先對(duì)其進(jìn)行初始化，再根據(jù)任務(wù)的規(guī)模進(jìn)行排序與存儲(chǔ)，算法1的復(fù)雜度的為O(γ•N)，當(dāng)輸入變量后就可以得到映射矩陣。在實(shí)際的云計(jì)算中，數(shù)據(jù)任務(wù)規(guī)模是非常龐大的，因此需要尋找最短的傳輸路徑來減少時(shí)間等待與傳輸延時(shí)效應(yīng)。對(duì)此最短路徑的尋找可以利用基于整數(shù)規(guī)劃的算法2來完成。將前面的映射結(jié)果作為輸入的變量，在最終結(jié)果中就可以得到最優(yōu)的傳輸路徑。算法2:基于IP的路徑尋找算法輸入:網(wǎng)絡(luò)圖，任務(wù)集合及任務(wù)映射算法提供的1:MTD←MTS×MSD2:λiuv←{}03:λiuv←argmin∑αi=1∑(u，v)∈ETi•luv•λiu()v，約束條件為式(12)，(13)，(14)，(16)。

4性能評(píng)估

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)鍵，對(duì)此與最為常用的尋找路徑的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é)合仿真圖。任務(wù)概率的增長而不斷增加，會(huì)隨著鏈路容量的增加而呈現(xiàn)出遞減的趨勢。仿真結(jié)果如下圖3所示。其該三種算法的完工時(shí)間的性能變化趨勢與小規(guī)模網(wǎng)絡(luò)情況下的相一致。云計(jì)算的完工時(shí)間會(huì)隨著任務(wù)量以及新舊但綜合這三種算法得到的最大響應(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)一步對(duì)問題實(shí)現(xiàn)線性簡化。通過全面的仿真實(shí)驗(yàn)，證明該算法的效率接近于最優(yōu)解，效率較高，且性能遠(yuǎn)優(yōu)于當(dāng)前其他請(qǐng)求響應(yīng)算法，證明了兩階段啟發(fā)算法在云計(jì)算中的有效性。

參考文獻(xiàn):

［1］張燕，顧才東．一種求解云計(jì)算資源優(yōu)化的改進(jìn)蝙蝠算法［J］．科技通報(bào)，2014(11):117－121．

［2］劉美林，王勇，李凱，等．云計(jì)算中基于序貫博弈的任務(wù)調(diào)度策略［J］．計(jì)算機(jī)科學(xué)，2015，42(s1)．

［3］楊喆曦，薛華成．基于系統(tǒng)響應(yīng)時(shí)間的云服務(wù)質(zhì)量評(píng)估模型［J］．計(jì)算機(jī)應(yīng)用與軟件，2017，34(10):40－45．

［4］王翠娥，顧永跟，吳小紅，等．基于機(jī)制設(shè)計(jì)理論的云計(jì)算SLA響應(yīng)時(shí)間優(yōu)化［J］．電信科學(xué)，2012，28(1):42－46．

［5］謝文靜，唐卓，楊柳，等．基于隨機(jī)規(guī)劃的云計(jì)算中虛擬機(jī)分配優(yōu)化研究［J］．計(jì)算機(jī)工程與科學(xué)，2012，34(5):95－100．

［6］劉亞秋，邢樂樂，景維鵬．云計(jì)算環(huán)境下基于時(shí)間期限和預(yù)算的調(diào)度算法［J］．計(jì)算機(jī)工程，2013，39(6):56－59．

作者：劉會(huì)珍 單位：滁州職業(yè)技術(shù)學(xué)院