云計算對完工時間最小化算法研究范文

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

摘要:目前對云服務供應進行的研究主要圍繞任務映射展開，其中如何將面向服務的任務分布給服務器以實現完工時間最小化成為該領域內的難點。總結后發現，未能實現完工時間最小化的重要原因是沒有考慮到任務路由器傳輸所造成的影響，鑒于此提出一種多項式時間復雜度的啟發式算法。實驗結果表明，該算法的效率接近于最優解，效率較高且性能遠優于當前其他算法。

關鍵詞:云服務;映射;時間;啟發式算法;最優解

引言

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

1系統模型建立

數據中心與鏈路集合共同組成了網絡圖，對此假設這三個集合分別為V=D1，D2{，…，D}β、鏈路E與G=(V，E)。數據中心的服務器并不是單一存在的，假設服務器共計有γ個，則可記為S=s1，s2{，…，s}γ。每個服務器都是γ×β二元矩陣，可用MSD=MSD{}ij，i=1，2，…，γj=1，2，…，β，其中：Du與Dv之間的傳輸的鏈路(u，v)的延時假設為luv，那么鏈路E集合則為β×β的矩陣，可用ML表示，表達式如下(2)所示［4］。ML={l}uv，(u，v)∈E(2)在云計算服務中，當收到數據請求時，會形成任務T=T1，T2{，…，T}α，并根據任務來對資源需求規模T進行估算。鑒于時間ζ約束的云計算服務，任務資源可以用θ×α的矩陣QRT=QRT{}ki，k=1，2，…，θ，i=1，2，…，α表示，其中QRTki是Ti對資源Rk的需求量。對此，可以在數據控制室直接確定某一時間區間內的ARS與QRT的容量。

2問題模型構建

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

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

3啟發式算法設計

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

4性能評估

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

4．2大規模網絡的預期最大完工時間在大規模網絡中路徑尋找是關鍵，對此與最為常用的尋找路徑的Dijkstr、SPFA算法相結合，同樣來探尋任務量、流量以及新舊任務這種情況下的完工時間變化，最大完工時間之和與新任務數量間的關系圖2所示。其中，圖2(a)是IP－PFA的任務映射啟發式算法仿真圖，圖2(b)是Dijk．CAP的任務映射啟發式算法仿真圖，圖2(c)SPFA．CAP的任務映射啟發式算法仿真圖，圖2(d)BFI與最短路徑尋找算法相結合仿真圖。任務概率的增長而不斷增加，會隨著鏈路容量的增加而呈現出遞減的趨勢。仿真結果如下圖3所示。其該三種算法的完工時間的性能變化趨勢與小規模網絡情況下的相一致。云計算的完工時間會隨著任務量以及新舊但綜合這三種算法得到的最大響應時間來看，如圖4所示。兩階段啟發式算法的完工時間最小，性能是最優的，也就說該算法達到了性能優化的目的。

5結論

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

參考文獻:

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

［2］劉美林，王勇，李凱，等．云計算中基于序貫博弈的任務調度策略［J］．計算機科學，2015，42(s1)．

［3］楊喆曦，薛華成．基于系統響應時間的云服務質量評估模型［J］．計算機應用與軟件，2017，34(10):40－45．

［4］王翠娥，顧永跟，吳小紅，等．基于機制設計理論的云計算SLA響應時間優化［J］．電信科學，2012，28(1):42－46．

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

［6］劉亞秋，邢樂樂，景維鵬．云計算環境下基于時間期限和預算的調度算法［J］．計算機工程，2013，39(6):56－59．

作者：劉會珍 單位：滁州職業技術學院