[發明專利]一種移動網格任務調度方法

無效

• 申請號: 200910272555.0
• 申請日: 2009-10-27
• 公開（公告）號: CN101702833A
• 公開（公告）日: 2010-05-05
• 發明（設計）人: 李春林;李方云;李輝;申智勇
• 申請（專利權）人: 武漢理工大學
• 主分類號: H04W80/12
• 分類號: H04W80/12;H04W84/12
• 代理公司: 武漢開元知識產權代理有限公司 42104
• 代理人: 潘杰

技術領域

本發明涉及網格的任務調度方法，更具體地涉及一種移動網格任務調度方 法。

背景技術

現今，移動設備例如便攜式計算機、個人數字助理(PDA，Personal?Digital Assistant)、移動手機等已經大眾化，逐漸影響了人們日常生活和商務活動的各 個方面。同時，無線網絡的蓬勃發展，包括無線局域網(WLAN，Wire-less Local-Area?Network)、GPRS/CDMA1?X(General?Packet?Radio?Service/Code Division?Multiple?Access?1x，通用分組無線業務/碼分多址接入技術)移動通信網 絡移動通信網絡、即將得到應用的第三代移動通信網絡(3G)、以及近來成為研究 熱點的無線傳感器網絡等，為人們隨時隨地進行溝通提供了網絡平臺。隨著技 術的不斷發展，可以預見移動設備將由移動互聯網、WAP應用逐步走向網格應 用。如果將現有的網格稱為固定網格，那么在移動設備上部署網格中間件，可 以構成一個動態的、多制度的移動設備的虛擬組織-移動網格(Mobile?Grid)。與 固定網格相比，移動網格更加貼近每一個普通人的實際應用。具體來講，移動 網格不僅能為用戶提供音樂、醫療、保險等服務，而且可以用于日常的交通事 故處理以及酒店點菜系統。

隨著移動設備性能的不斷增強以及移動網格應用范圍的不斷擴大，將移動 設備作為移動網格中的一種資源使用成為了研究熱點。然而，當若干用戶發出 請求時，如何快速有效地協同調度可用的資源，從而一方面實現整體調度時間 最短，另一方面提高可用資源的利用率，已成為研究過程中的一個非常核心的 問題。

目前現有的資源調度方法針對的是固定網格，其資源是靜止的，并且是在 關于資源和任務的狀態信息已知的情況下，基于一些規則函數(如最小化執行時 間、最大化資源利用率)作出的最優任務分配，因此執行時間達到最小化時，基 本實現任務調度時間的最小化。

然而，移動網格中的資源是移動的，并且資源的通信范圍及移動性會引起 連接時斷時續問題，同時資源的移動使資源與調度機之間的距離產生變化，進 而延遲返回的任務處理結果并影響傳送結果所消耗能量。由上可以看出，資源 的移動性對任務調度完成時間和任務調度所消耗的能量有很大影響，僅僅考慮 最小執行時間是遠遠不夠的。綜上所述，現有的資源調度方法不適用于資源移 動的移動網格。

因此，有必要提供一種移動網格任務調度方法來克服上述現有技術存在的 問題。

發明內容

本發明的目的是提供一種移動網格任務調度方法，充分考慮移動網格環境 下資源的移動性。

為了實現上述目的，本發明提供了一種移動網格任務調度方法，所述移動網 格任務調度方法包括如下步驟：(1)根據任務的服務請求類型對任務隊列中的 所有任務進行分組；(2)根據所述任務的服務類型請求對資源集中的所有資源 進行分組；(3)在同種服務請求類型的任務組和資源組中查找每個任務在各個 資源上執行時消耗的時間，并根據所述每個任務和所述查找的對應資源獲取所 述每個任務在所述查找的對應資源上執行的最小執行時間、所述每個任務提交 給所述查找的對應資源的預期提交通信時間、以及所述查找的資源將對應任務 的處理結果返回給任務調度者的預期結果返回通信時間；(4)獲取所述最小執 行時間、所述預期提交通信時間和所述預期結果返回通信時間之和的最小值對 應的資源和任務；(5)將所述資源分配給所述任務；(6)所述任務調度完成后 取消所述任務，更新所述資源集。

較佳地，所述步驟(3)中的最小執行時間獲取的步驟具體為：(31)在同 種服務請求類型的任務組和資源組中獲取預期執行時間矩陣，其中所述預期執 行時間矩陣的每個元素表示每個資源在沒有負載時執行每個任務需要的時間； (32)根據所述預期執行時間矩陣獲取最小執行時間向量，所述最小執行時間 向量的每個元素為所述預期執行時間矩陣中每個任務行的最小值。

優選地，所述步驟(31)中預期執行時間矩陣是通過網絡氣象服務獲取的。

在本發明的一個實施例中，所述步驟(32)具體包括：如果所述預期執行 時間矩陣中不同任務行的最小值出現在相同資源上，則與所述不同任務行的下 一任務對應的最小執行時間向量的元素為所述下一任務所在行的次最小值。