[發(fā)明專利]一種基于能量優(yōu)化的網(wǎng)格調度方法

無效

• 申請?zhí)枺?/td>: 200810047692.X
• 申請日: 2008-05-13
• 公開（公告）號: CN101271407A
• 公開（公告）日: 2008-09-24
• 發(fā)明（設計）人: 李春林;施步青;鐘景秀;張小慶;蔡英華
• 申請（專利權）人: 武漢理工大學
• 主分類號: G06F9/50
• 分類號: G06F9/50
• 代理公司: 武漢開元專利代理有限責任公司
• 代理人: 潘杰

技術領域

本發(fā)明屬于一種網(wǎng)格調度方法，特別是一種基于能量優(yōu)化的網(wǎng)格調度方法。

背景技術

網(wǎng)格計算是近年來逐漸興起的一種Internet計算模式，其目的是為了在分布、異構、自治的網(wǎng)絡資源環(huán)境上構造動態(tài)的虛擬組織，并在其內部實現(xiàn)跨自治域的資源共享和資源協(xié)作，有效的滿足面向互聯(lián)網(wǎng)的復雜應用對大規(guī)模計算能力和海量數(shù)據(jù)處理的需求。因此，網(wǎng)格資源具有分布性和異構性這一特點，常見的網(wǎng)格資源有：計算資源、存儲資源、網(wǎng)絡資源、能量資源等。近年來隨著Ad?Hoc網(wǎng)絡以及無線傳感器網(wǎng)絡(WSN)的快速發(fā)展和其在網(wǎng)格中的應用，能量資源在網(wǎng)格異構環(huán)境中越來越普遍。比如，在Ad?Hoc網(wǎng)格中，各資源節(jié)點的能量儲量都是有限的，在實現(xiàn)資源調度過程中，能量約束是一個不可忽視的因素。另外，近年來數(shù)據(jù)密集型網(wǎng)格應用不斷增多，比如高性能物理研究、天體研究、天氣預報等，這些應用都是建立在高性能數(shù)據(jù)網(wǎng)格之上的。高性能數(shù)據(jù)網(wǎng)格具有計算時間長，能量消耗大等特點，能量因素是在進行高性能計算中不得不考慮的一個問題。當前，隨著人們對環(huán)境問題關注力度的不斷增大，能量優(yōu)化問題已經(jīng)成為了各種領域內急需解決的一個問題。因此，在網(wǎng)格調度研究中考慮能量約束，實現(xiàn)調度的能量最優(yōu)也將成為網(wǎng)格計算研究領域內的一個熱點。

網(wǎng)格計算的資源調度是個NP完全問題。由于NP問題目前還找不到有效的解決方案，人們提出了一些啟發(fā)式方法來尋求它的次優(yōu)解，如遺傳算法，蟻群算法，Min-Min，禁忌搜索，神經(jīng)網(wǎng)絡，模擬退火等算法。現(xiàn)階段，對啟發(fā)式調度算法的研究主要分為兩個方面：靜態(tài)調度算法和動態(tài)調度算法。靜態(tài)算法是指所有的任務-資源映射策略在調度前已經(jīng)確定，而動態(tài)調度算法是指部分任務-資源映射策略是在調度期間根據(jù)實際情況確定。因此靜態(tài)調度算法相對比較簡單，運行開銷小，對數(shù)據(jù)依賴小，但靜態(tài)調度算法對于網(wǎng)格環(huán)境中資源的分布性以及異構性支持力度不夠。而動態(tài)調度算法很好的解決異構性分布性帶來的負載平衡問題、效應測定問題、任務遷徙問題。動態(tài)調度算法可分為聯(lián)機模式(onlinemodel)和批模式(batch?model)。這兩種方法各有優(yōu)缺點，對于聯(lián)機在線模式，由于當任務到達時就考慮分配，盡可能及時地將任務進行調度，因此反應快、任務的延遲時間短，但是可能導致資源的分配不夠優(yōu)化，因為沒有考慮前后任務的特點，可能導致要求低的任務占用處理能力強的節(jié)點，而要求高的任務分配到處理弱的節(jié)點或者處于等待狀態(tài)。而批處理方式則能夠考慮更多的請求和資源狀況，潛在地能得到更有效的網(wǎng)格資源利用率，但對于單個任務來說，延遲時間可能較長，對于某些服務質量沒有辦法實施。

網(wǎng)格應用的不斷發(fā)展，尤其是服務網(wǎng)格的出現(xiàn)，促進和加速了對于網(wǎng)格服務質量(QoS)的研究。各種基于QoS的調度算法也逐漸出現(xiàn)，這些調度算法都是在原有經(jīng)典調度算法的基礎上加入各種QoS約束條件演化而成。一般研究的QoS約束主要集中在：網(wǎng)絡帶寬、網(wǎng)絡延時、代價、時間、生存性、信任度等方面。相應的改進算法也能很好的解決很多調度過程中的核心問題：完成時間優(yōu)化、調度效率優(yōu)化、經(jīng)濟開銷優(yōu)化等。但由于涉及的網(wǎng)格資源類型比較單一和QoS約束條件本身的局限性，對于調度過程中的能量優(yōu)化問題很少有涉及。

發(fā)明內容

本發(fā)明的目的是提供一種將能量資源引入到網(wǎng)格資源調度中，綜合考慮能量約束以及時間約束的基于能量優(yōu)化的網(wǎng)格調度方法。

為了實現(xiàn)上述目的，本發(fā)明的技術方案如下：

1、將能量資源作為調度的研究重點，引入能量初始值，網(wǎng)絡帶寬等因素。

2、實現(xiàn)能量優(yōu)化，使資源調度中的能量消耗值最小，網(wǎng)格資源調度中的能量消耗主要分為計算消耗和網(wǎng)絡通信消耗。

3、考慮時間跨度優(yōu)化(Makespan)，達到能量優(yōu)化過程中的資源負載均衡。

4、提出一個綜合考慮能量約束以及時間約束的基于能量優(yōu)化的網(wǎng)格調度方法。

考慮到網(wǎng)格資源調度過程中網(wǎng)格任務以及網(wǎng)格資源都具有分布性以及異構性，本發(fā)明的網(wǎng)格調度模型不能對真實的網(wǎng)格環(huán)境進行完全模擬，因此做出如下設定：

(1)各網(wǎng)格任務都是獨立存在的，任務之間無數(shù)據(jù)依賴或通信。

(2)在調度模型中的能量資源能實現(xiàn)任務計算，任務執(zhí)行等功能，與狹義上的只提供能源供應的能量資源有區(qū)別。

(3)每個資源只能同時執(zhí)行一個網(wǎng)格任務。

(4)網(wǎng)格調度中的能量消耗只限于任務執(zhí)行消耗和網(wǎng)絡通信消耗，而網(wǎng)絡通信消耗主要指任務與資源數(shù)據(jù)通信時的能量消耗，資源間通信的能量消耗忽略。

(5)網(wǎng)絡通信時間為網(wǎng)絡帶寬的倒數(shù)，忽略網(wǎng)絡延時等其他網(wǎng)絡因素。