一種移動網格任務調度方法
2023-06-07 03:23:31 2
專利名稱：一種移動網格任務調度方法
技術領域：
本發明涉及網格的任務調度方法，更具體地涉及一種移動網格任務調度方法。
背景技術：
現今，行動裝置例如可攜式計算機、個人數字助理(PDA, Personal DigitalAssistant)、移動手機等已經大眾化，逐漸影響了人們日常生活和商務活動的 各個方面。同時，無線網絡的蓬勃發展，包括無線區域網(WLAN， Wire-lessLocal-Area Network) 、 GPRS/CDMA1 X(General Packet Radio Service/CodeDivision Multiple Access lx，通用分組無線業務/碼分多址接入技術)移動通信網絡移動通信網絡、即將得 到應用的第三代移動通信網絡(3G)、以及近來成為研究熱點的無線傳感器網絡等，為人們 隨時隨地進行溝通提供了網絡平臺。隨著技術的不斷發展，可以預見行動裝置將由移動互 聯網、WAP應用逐步走向網格應用。如果將現有的網格稱為固定網格，那麼在行動裝置上 部署網格中間件，可以構成一個動態的、多制度的行動裝置的虛擬組織-移動網格(Mobile Grid)。與固定網格相比，移動網格更加貼近每一個普通人的實際應用。具體來講，移動網 格不僅能為用戶提供音樂、醫療、保險等服務，而且可以用於日常的交通事故處理以及酒店 點菜系統。 隨著行動裝置性能的不斷增強以及移動網格應用範圍的不斷擴大，將行動裝置作 為移動網格中的一種資源使用成為了研究熱點。然而，當若干用戶發出請求時，如何快速有 效地協同調度可用的資源，從而一方面實現整體調度時間最短，另一方面提高可用資源的 利用率，已成為研究過程中的一個非常核心的問題。 目前現有的資源調度方法針對的是固定網格，其資源是靜止的，並且是在關於資 源和任務的狀態信息已知的情況下，基於一些規則函數(如最小化執行時間、最大化資源 利用率)作出的最優任務分配，因此執行時間達到最小化時，基本實現任務調度時間的最 小化。 然而，移動網格中的資源是移動的，並且資源的通信範圍及移動性會引起連接時 斷時續問題，同時資源的移動使資源與調度機之間的距離產生變化，進而延遲返回的任務 處理結果並影響傳送結果所消耗能量。由上可以看出，資源的移動性對任務調度完成時間 和任務調度所消耗的能量有很大影響，僅僅考慮最小執行時間是遠遠不夠的。綜上所述，現 有的資源調度方法不適用於資源移動的移動網格。 因此，有必要提供一種移動網格任務調度方法來克服上述現有技術存在的問題。
發明內容
本發明的目的是提供一種移動網格任務調度方法，充分考慮移動網格環境下資源 的移動性。 為了實現上述目的，本發明提供了一種移動網格任務調度方法，所述移動網格任 務調度方法包括如下步驟(l)根據任務的服務請求類型對任務隊列中的所有任務進行分組；(2)根據所述任務的服務類型請求對資源集中的所有資源進行分組；(3)在同種服務請 求類型的任務組和資源組中查找每個任務在各個資源上執行時消耗的時間，並根據所述每 個任務和所述查找的對應資源獲取所述每個任務在所述查找的對應資源上執行的最小執 行時間、所述每個任務提交給所述查找的對應資源的預期提交通信時間、以及所述查找的 資源將對應任務的處理結果返回給任務調度者的預期結果返回通信時間；(4)獲取所述最 小執行時間、所述預期提交通信時間和所述預期結果返回通信時間之和的最小值對應的資 源和任務；(5)將所述資源分配給所述任務；(6)所述任務調度完成後取消所述任務，更新 所述資源集。 較佳地，所述步驟(3)中的最小執行時間獲取的步驟具體為(31)在同種服務請 求類型的任務組和資源組中獲取預期執行時間矩陣，其中所述預期執行時間矩陣的每個元 素表示每個資源在沒有負載時執行每個任務需要的時間；(32)根據所述預期執行時間矩 陣獲取最小執行時間向量，所述最小執行時間向量的每個元素為所述預期執行時間矩陣中 每個任務行的最小值。 優選地，所述步驟(31)中預期執行時間矩陣是通過網絡氣象服務獲取的。
在本發明的一個實施例中，所述步驟(32)具體包括如果所述預期執行時間矩陣 中不同任務行的最小值出現在相同資源上，則與所述不同任務行的下一任務對應的最小執 行時間向量的元素為所述下一任務所在行的次最小值。 在本發明的另一實施例中，所述移動網格任務調度方法還包括如下步驟(33)根 據所述最小執行時間向量獲取最小執行時間數組，所述最小執行時間數組的每個元素表示 與所述最小執行時間向量的每個元素對應的任務和資源組成的數對。 較佳地，所述步驟(3)中的預期提交通信時間獲取的步驟具體為(34)根據所述
最小執行時間數組獲取預期提交通信時間向量，所述預期提交通信時間向量的每個元素表
示所述最小執行時間數組的每個元素的對應任務傳送到對應資源的通信時間。 在本發明的再一實施例中，所述步驟(3)中的預期結果返回通信時間獲取的步驟
具體為(35)根據所述最小執行時間數組獲取預期結果返回通信時間向量，所述預期結果
返回通信時間向量的每個元素表示所述最小執行時間數組的每個元素的對應資源在對應
任務完成時將所述對應任務的處理結果返回給任務調度者的通信時間。 在本發明的又一實施例中，所述步驟(35)具體為(351)根據所述最小執行時間
數組獲取預期結果返程數組，所述預期結果返程數組的每個元素表示所述最小執行時間數
組的每個元素的對應資源在所述對應任務完成時與所述任務調度者之間的距離；(352)根
據所述預期結果返程數組獲取預期結果返回通信時間向量，所述預期結果返回通信時間向
量的每個元素為所述最小執行時間數組的每個元素與結果返回傳輸速度的商。 在本發明的另一實施例中，所述步驟(351)具體為利用極坐標建立移動預測模
型，所述移動預測模型預測所述最小執行時間數組的每個元素的對應資源在所述最小執行
時間內完成所述對應任務時的位置，根據所述預測的位置以及所述任務調度者的位置獲取
所述最小執行時間數組的每個元素的對應資源在所述對應任務完成時與所述任務調度者
之間的距離，所述獲取的每個距離為所述預期結果返程數組的元素。 在本發明的再一實施例中，所述步驟(4)具體包括如果所述最小執行時間、所述 預期提交通信時間和所述預期結果返回通信時間之和的最小值出現多個，則獲取所述多個最小值中較小的最小執行時間對應的資源和任務。 與現有技術相比，本發明移動網格任務調度方法從資源的移動性出發考慮移動網 格中資源的復移動性，資源和任務根據任務的服務請求類型分組，任務調度是面向服務類 型的。 另外，所述移動網格任務調度方法實現調度目標時考慮了任務的最小執行時間、 預期提交通信時間和預期結果返回通信時間，調度的目標是整個任務的調度時間最小，而 以往的調度方法都沒有考慮資源的移動帶來的傳送延遲。 此外，任務調度在所有分組中並行進行，因而縮短了調度時間，進而減輕了移動網 格資源管理的複雜度。如果採用現有的網格中面向域的資源調度機制，資源的移動性會使
管理非常複雜。 再者，所述移動網格任務調度方法中只要有一組完成一個子任務就更新所有資源 組，因而不影響其它組中任務的執行，這樣在保證最優跨度的同時提高了資源的利用率。當 有新資源出現時，根據任務的服務請求類型將所述新資源歸屬到相應組中，因而不影響其 它組中任務的調度，這樣能提高資源的利用率。 通過以下的描述並結合附圖，本發明將變得更加清晰，這些附圖用於解釋本發明 的實施例。
圖1為本發明移動網格任務調度方法的流程圖。
具體實施例方式
現在參考附圖描述本發明的實施例，附圖中類似的元件標號代表類似的元件。如 上所述，本發明提供了一種移動網格任務調度方法，所述方法充分考慮移動網格環境下資 源的移動性，任務調度採取整個任務的調度時間最小的策略，並且任務調度在所有分組中 並行進行，縮短了調度時間，同時在組內子任務完成後更新所有資源組，保證最優跨度的同 時提高了資源的利用率。下面詳細說明。 在對本實施例移動網格任務調度方法進行詳細說明之前，先對移動網格環境中的
任務、資源以及本實施例調度方法中的假設、參數定義和移動預測模型進行說明。 移動網格環境中任務描述 本實施例移動網格中的任務調度是面向服務的，假設一個任務序列T具有n個任 務，這裡可以表示為任務序列T = {tn t2， . . . ， tn}。所述任務序列T根據任務的服務請求 類型劃分為P組，其中每組中的任務滿足以下條件 (1)每個任務都是粗粒度的子任務，即任務之間沒有通訊和數據依賴，減少通信開 銷； (2)每個機器是共享的，提供的服務是獨佔的，即當一個任務分配了 一個服務時， 該任務佔有該服務直到運行完畢； (3) —個任務只需要單個服務，即一個任務只可能在一個任務組中出現； (4)具有靜態運行時間，即在分配之前任務在每個資源上的期望運行時間都是預
先可知的。
綜上所述，經過分組後n個任務滿足l] A^A)="，其中N(p》表示第i組任務組中 任務的個數。 移動網格環境中資源描述 移動網格中的任意移動終端都可以提供資源共享，共享的資源稱之為服務。本實 施例中提到的服務和資源是同一概念，由機器提供。任務以描述其請求的服務方式提交，資 源以描述其可提供的服務的方式發布。 —個機器可以提供多種服務。假設若干個機器提供m個服務，這裡可以表示資源 集M = {ri， r2，. . . ， rm}，將這m個服務根據任務的服務請求類型劃分為p組，經過分組後的
m個服務滿足l]M(A):m ，其中M(p》表示第i組服務組中服務的數目。
本實施例調度方法中的假設 本實施例考慮到移動網格的資源調度過程中任務和資源都具有分布性、異構性、 移動性特點，做出如下假設 (1)資源在任務提交和結果返回過程中設為靜止狀態(只考慮資源在任務執行過
程中的移動性)，任務調度者是靜止的，任務調度者的位置表示為(x。，y。)； (2)每個移動資源都有位置識別功能，即每隔AT時間就自身定位一次並記有兩
個歷史位置信息，其中歷史位置信息的歷史記錄隊列項格式為(t(定位時刻)，X(橫坐
標)，y(縱坐標)，v(初速度大小)，a(加速度大小)，e (移動方向))。移動方向是以前一
次的定位位置為參考點的； (3)只考慮一個作業的n個子任務的調度，任意任務至少有一個服務能滿足要求；
(4)同一任務提交時的數據的傳送速度和結果返回的傳輸速度是一樣的，用Vi表 示，傳送數據量是一樣的，單位時間內傳送單位數據量消耗的能量是一樣的。
本實施例調度方法中用到的參數定義 預期執行時間矩陣EET(Expected Execution Time):每個元素EETij表示資源j在 沒有負載的情況下，執行任務i所需要的時間。若任務不能在機器上執行，則值為無窮大。
最小執行時間向量MET (Minimum Execution Time):每個元素MET^.是矩陣EET中 每個任務行的最小值，表示任務i執行時的最小執行時間。如果所述預期執行時間矩陣EET 中不同任務行的最小值出現在相同資源上，則與所述不同任務行的下一任務對應的最小執 行時間向量的元素為所述下一任務所在行的次最小值，以保證每個資源同時只為一個任務 服務。 最小執行時間數組A[n]:每個元素為一個數對(i， j)，表示最小執行時間向量MET 中每個元素對應的任務和資源。 預期提交通信時間向量ETHT(Expected Task Hand in Time):每個元素ETHTij表 示最小執行數組A[n]中任務i傳送到資源j的通信時間。 預期結果返程數組B[n]:每個元素表示數組A[n]中資源j在任務完成時與任務 調度者之間的距離。 預期結果返回通信時間向量ERBT(Expected Result Back Time):每個元素ETHTi」 是指數組A[n]中資源j將任務i的處理結果返回給任務調度者的通信時間。
預期任務調度時間向量EST (Expected Schedule Time):每個元素EST".是最小執 行時間向量MET、預期提交通信時間向量ETHT和預期結果返回通信時間向量ERBT的對應元 素之和，即EST" = METij+ETHTij+ERBTij。 預期結果到達時間矩陣ERAT (Expected Result Arrive Time):每個元素ERATij 是指資源j將任務i的處理結果返回給任務調度者的到達時間。假設任務i在資源j上的 提交起始時間為I,則ERATij = ESTij+Tij。
需要提出的是，以上參數都是在一個組中的定義。 注本實施例中的總完成時間Makespan定義為最後一個任務的處理結果返回給 任務調度者的到達時間與第一個任務的提交起始時間的差值。本實施例移動網格任務調度 的目標是使上述總完成時間Makespan達到最小值。 假設第一個任務提交起始時間為零，那麼本實施例移動網格任務調度的目標轉變 為求mint(^7;),由於每個任務都是獨立的，故mint(^7;卜tmin(ES7;)移動預測模
型的建立 本實施例利用極坐標建立了移動預測模型。基於假設(2)，資源j記錄了兩個歷史 位置信息。假設資源在t(i)時刻的位置是(Xt(i)，yt(i))，那麼在一個AT時間間隔後，移動 預測模型可以預測資源的位置是
formula see original document page 8formula see original document page 8 所述任務i在所述資源j上執行時，所述移動預測模型在數組A[n]中的資源j上 要運行kj次，其中kj滿足 min (METj + t > A T > min (METj - t ， t為估計誤差
所述移動預測模型每運行一次，就更新資源的歷史記錄。 通過上述移動預測模型，能預測出數組A[n]中每個任務i對應的資源j在最小執 行時間METij內完成任務時的位置(x，y)，通過兩點間的距離公式可以求出資源j在任務完 成時與任務調度者(位置表示為(x。，y。))之間的距離 formula see original document page 8 因此，預期結果返程數組B[n] = (dij)，其維數與數組A[n]的維數相同。 基於假設(4)，根據公式ERBTij = 可得資源j返回任務i的處理結果的預期
結果返回通信時間向量ERBT。 下面具體說明本實施例移動網格任務調度方法的流程 步驟S110，根據任務的服務請求類型將n個任務形成的任務隊列T二 {tp^,...， tn}分成p組;
步驟S120，根據任務的服務請求類型將m個資源形成的資源集M = {巧，r2，...，
rj同樣分成p組； 步驟S130，通過網絡氣象服務(麗S，Network Weather Services)並在同種服務請求類型的任務組和資源組中獲取預期執行時間矩陣EET，根據所述預期執行時間矩陣EET獲得最小執行時間向量MET和最小執行時間數組A[n]，如果最小執行時間向量MET中的元素METu等於無窮大，則將任務i掛起；(假設同種任務的服務請求類型的第一任務組和資源組中有3個子任務映射到4個服務上，它們的預期執行時間矩陣EET為々5 五五r =
oo
8
5 2 oo
6 3 7
那麼，最小執行時間數組A[n]為:A[3]對應的最小執行時間向量MET為MET=;2 其中，數組A[3]中元素(1，3)表示任務1在編號為3的資源上的預期執行時間最短。類似地，可以得到P個這樣的數組。) 步驟S140，根據所述最小執行時間數組A[n]獲取預期提交通信時間向量ETHT ;
(假設上述數組A[3]各數對中的任務到對應資源的距離分別為9，16，3，傳送數據的速度分別為3，4，3，那麼提交任務的通信時間向量ETHT為 3— ETHT= 步驟S150，利用所述移動預測模型並根據所述最小執行時間數組A[n]獲取預期結果返程數組B[n]，如果大於所述任務提交者的通信範圍的半徑，則將任務i掛起；
(這裡假設所述移動預測模型對數組A[3]中的資源進行預測，得到預期結果返程數組為B[3] = (4， 6， 4)。) 步驟S160，根據所述預期結果返程數組B[n]獲取預期結果返回通信時間向量ERBT ;(假設處理結果返回的傳輸速度分別為2，3，4，基於假設(4)且根據公式ERBTij =dij/Vi，得到資源j返回任務i的處理結果的通信時間向量ERBT為—2— ERBT- 步驟S170，根據所述最小執行時間向量MET、預期提交通信時間向量ETHT和預期結果返回通信時間向量ERBT獲取數組A[n]中各個任務的預期任務調度時間向量EST ;
(這樣，數組A[3]各個數對中任務i從提交到執行到收到處理結果整個最小任務調度時間EST為
9
formula see original document page 10
由上式可知，執行時間或完成時間最短並不能保證任務的整個調度時間最短，所
以在移動網格中，考慮任務處理結果返回所消耗的時間是非常必要的。) 步驟S180，根據所述預期任務調度時間向量EST獲取最小元素min (ESTj ，如果出
現多個最小元素，則獲取所述多個最小元素中具有較小的最小執行時間的元素；
(這樣，任務調度的最後選擇是min (ESTij) = 7。) 步驟S190，獲取與所述最小元素min (ESTj或所述多個最小元素中具有較小的最小執行時間的元素對應的資源和任務；(結合數組A[3]知min(ESTij)對應的任務為編號3，對應的資源為編號4。)
步驟S200，將所述資源分配給所述任務(即將編號3的任務分配給編號4的資源執行)； 步驟S210，所述任務調度完成後取消該任務，喚醒掛起的任務，並更新資源組，將新註冊的資源加入到相應組中，轉步驟S300。 由上可以看出，本實施例移動網格任務調度方法從資源的移動性出發考慮移動網格中資源的複雜性，不像以往的網格調度只考慮固定的網格資源。本實施例資源和任務根據任務的服務請求類型分組，任務調度是面向服務類型的，任務調度在所有分組中並行進行，縮短了調度時間，這種管理方式減輕了移動網格資源管理的複雜度，如果採用現有的網格中面向域的資源調度機制，資源的移動會使管理非常複雜。 此外，只要有一組中完成一個子任務就更新所有資源組，因而不影響其它組中的任務執行，這樣在保證最優跨度的同時提高了資源的利用率。當有新資源出現時，根據任務的服務請求類型將所述新資源歸屬到相應組中，因而不影響其它組中的任務調度，這樣能提高資源的利用率， 再者，本實施例移動網格調度方法能通過移動預測模型對資源在執行任務過程中的位置進行估計，並且該在實現調度目標時考慮了任務的最小執行時間、預期提交通信時間和預期結果返回通信時間，調度的目標是整個任務的調度時間最小，而以往的調度方法都沒有考慮資源的移動帶來的傳送延遲。 以上結合最佳實施例對本發明進行了描述，但本發明並不局限於以上揭示的實施例，而應當涵蓋各種根據本發明的本質進行的修改、等效組合。
權利要求
一種移動網格任務調度方法，其特徵在於，包括如下步驟(1)根據任務的服務請求類型對任務隊列中的所有任務進行分組；(2)根據所述任務的服務類型請求對資源集中的所有資源進行分組；(3)在同種服務請求類型的任務組和資源組中查找每個任務在各個資源上執行時消耗的時間，並根據所述每個任務和所述查找的對應資源獲取所述每個任務在所述查找的對應資源上執行的最小執行時間、所述每個任務提交給所述查找的對應資源的預期提交通信時間、以及所述查找的資源將對應任務的處理結果返回給任務調度者的預期結果返回通信時間；(4)獲取所述最小執行時間、所述預期提交通信時間和所述預期結果返回通信時間之和的最小值對應的資源和任務；(5)將所述資源分配給所述任務；以及(6)所述任務調度完成後取消所述任務，更新所述資源集。
2. 如權利要求1所述的移動網格任務調度方法，其特徵在於，所述步驟(3)中的最小執 行時間獲取的步驟具體為(31) 在同種服務請求類型的任務組和資源組中獲取預期執行時間矩陣，其中所述預期 執行時間矩陣的每個元素表示每個資源在沒有負載時執行每個任務需要的時間；以及(32) 根據所述預期執行時間矩陣獲取最小執行時間向量，所述最小執行時間向量的每 個元素為所述預期執行時間矩陣中每個任務行的最小值。
3. 如權利要求2所述的移動網格任務調度方法，其特徵在於，所述步驟(31)中預期執 行時間矩陣是通過網絡氣象服務獲取的。
4. 如權利要求2所述的移動網格任務調度方法，其特徵在於，所述步驟(32)具體包括如果所述預期執行時間矩陣中不同任務行的最小值出現在相同資源上，則與所述不同 任務行的下一任務對應的最小執行時間向量的元素為所述下一任務所在行的次最小值。
5. 如權利要求2所述的移動網格任務調度方法，其特徵在於，還包括如下步驟(33) 根據所述最小執行時間向量獲取最小執行時間數組，所述最小執行時間數組的每 個元素表示與所述最小執行時間向量的每個元素對應的任務和資源組成的數對。
6. 如權利要求5所述的移動網格任務調度方法，其特徵在於，所述步驟(3)中的預期提 交通信時間獲取的步驟具體為(34) 根據所述最小執行時間數組獲取預期提交通信時間向量，所述預期提交通信時間 向量的每個元素表示所述最小執行時間數組的每個元素的對應任務傳送到對應資源的通 信時間。
7. 如權利要求5所述的移動網格任務調度方法，其特徵在於，所述步驟(3)中的預期結 果返回通信時間獲取的步驟具體為(35) 根據所述最小執行時間數組獲取預期結果返回通信時間向量，所述預期結果返回 通信時間向量的每個元素表示所述最小執行時間數組的每個元素的對應資源在對應任務 完成時將所述對應任務的處理結果返回給任務調度者的通信時間。
8. 如權利要求7所述的移動網格任務調度方法，其特徵在於，所述步驟(35)具體為 (351)根據所述最小執行時間數組獲取預期結果返程數組，所述預期結果返程數組的每個元素表示所述最小執行時間數組的每個元素的對應資源在所述對應任務完成時與所 述任務調度者之間的距離；(352)根據所述預期結果返程數組獲取預期結果返回通信時間向量，所述預期結果返 回通信時間向量的每個元素為所述最小執行時間數組的每個元素與結果返回傳輸速度的 商。
9. 如權利要求8所述的移動網格任務調度方法，其特徵在於，所述步驟(351)具體為 利用極坐標建立移動預測模型，所述移動預測模型預測所述最小執行時間數組的每個元素的對應資源在所述最小執行時間內完成所述對應任務時的位置，根據所述預測的位置 以及所述任務調度者的位置獲取所述最小執行時間數組的每個元素的對應資源在所述對 應任務完成時與所述任務調度者之間的距離，所述獲取的每個距離為所述預期結果返程數 組的元素。
10. 如權利要求l所述的移動網格任務調度方法，其特徵在於，所述步驟(4)具體包括如果所述最小執行時間、所述預期提交通信時間和所述預期結果返回通信時間之和的 最小值出現多個，則獲取所述多個最小值中較小的最小執行時間對應的資源和任務。
全文摘要
本發明公開了一種移動網格任務調度方法，其通過對任務隊列中的所有任務以及資源集中的所有資源進行分組，然後在同類任務組和資源組中查找每個任務在執行時消耗時間最小的資源，並根據每個任務和查找的對應資源獲取最小執行時間、預期提交通信時間和預期結果返回通信時間之和的最小值對應的資源和任務，然後將所述資源分配給所述任務，在所述任務調度完成後取消所述任務，並更新所述資源集，進而完成移動網格任務調度。本發明移動網格任務調度方法充分考慮移動網格環境下資源的移動性，任務調度採取整個任務的調度時間最小的策略，並且任務調度在所有分組中並行進行，縮短了調度時間。
文檔編號H04W80/12GK101702833SQ20091027255
公開日2010年5月5日 申請日期2009年10月27日 優先權日2009年10月27日
發明者李方雲, 李春林, 李輝, 申智勇 申請人:武漢理工大學