移動網格中任務分組的調度算法研究

羅顯兵，吳香林

（1.廣州杰賽科技股份有限公司通信規劃設計院，重慶 400042;2.重慶郵電大學移動通信技術重慶市重點實驗室，重慶 400065）

移動網格中任務分組的調度算法研究

羅顯兵1，吳香林2

（1.廣州杰賽科技股份有限公司通信規劃設計院，重慶 400042;2.重慶郵電大學移動通信技術重慶市重點實驗室，重慶 400065）

針對移動網格中任務量大的調度問題，考慮到同一網格域中有限的網格資源且資源的能量受限因素，提高移動網格的任務執行成功率和資源利用率就尤為重要。改進Min-Min算法，首先對大量任務分別按照指數、線性、對數方式進行分組，確定各組任務數，然后再利用移動終端能量受限和Min-Min算法結合的Energy Min-Min算法（即E-mm算法）進行調度。通過仿真驗證分析，該改進算法相對于Min-Min算法，提高了任務執行成功率，并且系統負載均衡效果也得到明顯改善。

移動網格;E-mm算法;剩余能量;任務分組;任務調度

【本文獻信息】羅顯兵，吳香林.移動網格中任務分組的調度算法研究［J］.電視技術，2013，37（3）.

隨著無線移動通信系統的快速發展，用戶可以隨時隨地訪問全球網絡資源。它以無縫、透明、安全、有效的方式支持移動用戶和共用網格資源，實現了無線技術與網格計算的融合。因此，移動設備被納入到網格系統中成為網格系統的組成部分，形成移動網格［1］（Mobile Grid）。移動網格最大優勢是引入了移動設備。因為移動設備與普通大眾有著最直接的聯系，因此移動網格更加貼近人們的生活，帶來了很多便利，在日常生活中有著廣泛的應用。目前將移動設備作為移動網格中的一種資源使用已成為研究熱點。

在移動網格中，便攜式設備數量顯著增長，當大量移動用戶發起任務請求時，如何快速有效地調度可用資源，既保證任務執行成功率，又提高可用資源的利用率和平衡系統資源負載，已成為研究過程中的一個非常核心的問題。較好的調度策略需要考慮以下三點［2］:1）每個任務的處理需求;2）根據資源的處理能力設計合理的任務分組機制;3）將分組任務傳送到恰當的資源。

盡管移動終端的能量是有限的，但是在執行某一任務期間必須保證能量充足。否則，移動設備就沒有足夠能量保證任務繼續執行完畢，導致任務需要重新被調度。由于計算任務到達的隨機性，使得單位時間內到達的任務量時而稀疏，時而密集，而現有的網格計算系統通常是資源長時間處于開啟狀態，等待計算任務到達，資源處于空閑狀態時，其空閑能耗占總能耗的50%～60%［3-4］，這種情況會過度浪費能量，使整個調度系統的吞吐量下降。因此，有必要提供一種移動網格任務調度方法來克服上述缺陷?；谌蝿辗纸M的E-mm算法。首先，將大量任務進行分組，針對各組任務采用Min-Min算法選取合適“任務—資源”對。其次，判斷匹配的最小期望完成時間與對應資源的能量極限時間的關系，選取合適的調度策略進行任務調度。該E-mm調度策略與傳統的Min-Min算法相比具有較好的資源負載性和較高的任務執行成功率等優點，與已有的調度算法相比在某些方面具有更優的性能。

1 移動網格的系統結構

隨著移動互聯網應用的逐漸普及以及移動搜索應用的不斷完善，當用戶需要查詢一些急需信息（如電話號碼、地圖、公交路線等）時，會越來越傾向于使用移動搜索。移動網格系統結構［5］如圖1所示，主要由3個模塊組成:固定網格站點，移動終端群，中間件移動網關。

圖1 移動網格系統結構圖

移動網格中，移動終端有兩個用途:一是作為被調度的資源;二是作為提供服務的資源。前者是移動設備去訪問網格資源，而后者是把移動設備作為網格資源，從而為其他網格用戶提供服務。移動終端，是指不包括筆記本在內的具備有限計算資源的設備。移動終端的體型不斷縮小，變得更為小巧和易于攜帶，而功能卻日益強大，服務不斷延伸，集通信、視頻、閱讀等多種功能為一身。但移動終端存在缺陷，具體表現在以下幾點:有限的內存和存儲資源，通常在2～64 Mbyte之間;計算資源、電池壽命、網絡帶寬、顯示和輸入能力是有限的，有多種多樣的處理器、操作系統。

2 移動網格的任務調度

任務調度問題實質就是一個由用戶提出的N個需要調度的任務和系統中M個可用的資源構成的場景下，把N個任務以最合理的方式匹配到M個可用的資源上，目的是使得任務的總完成時間盡可能?。?］，任務執行成功率高和資源負載均衡效果較好。

2.1 任務分組

若移動網格有N個相互獨立的任務可以表示為任務集T={t1，t2，…，tN}。為了便于分析問題，假設移動網格環境下提交的任務為元任務［7］。當大量任務中若有多個任務同時搶占相同的網格資源時，就會發生沖突，引起阻塞，阻塞會影響網絡的調度性能。針對上述問題，采用任務分組策略，分組后不同優先級任務發生沖突時，為了盡量保證網絡的QoS，則需要盡量保證高優先級任務的調度的成功率，而阻塞低優先級任務的調度。

移動網格系統在不同應用場景中，各優先級任務的數量分配都是不確定的，因此需要用不同的數學模型為其分配每個優先級組別的任務，并進行相應分析。本文對優先級的劃分使用了3種不同數學函數分析研究，對3種方式分組后系統的性能進行了比較，分析了在不同的移動網格環境下，使用哪種優先級劃分方式對系統的QoS較好，并進行了仿真說明。

線性函數方式為

指數函數方式為

對數函數方式為

式中:n=1∶8（分組等級號），GN為n號分組等級任務數，設定具體的a，b，k參數，可以得到對應的優先級分組中的任務數。通過對運用以上3種優先級劃分后，任務執行成功率、資源負載等性能進行分析，得出3種方式分別適合的移動網格調度環境。

2.2 Min-Min任務調度算法

Min-Min調度算法是一種簡單快速、高效的算法。該算法調度流程如圖2所示。首先，輸入任務數和資源數，由未執行的任務構成集合T，可用資源構成集合M，對于集合T中的每個任務計算其在所有可用資源集M上的期望完成時間，得到期望矩陣為ECT。然后，選擇每個任務的最小期望完成時間構成集合ECT={Min0＜j＜k（ct（ti，mj），ti∈T）};從ECT中選擇最小完成時間的任務和相應資源進行匹配。最后，從T中刪除該任務重復上述操作直到集合T為空。該算法最大的缺點是資源的負載嚴重不均衡。

圖2 Min-Min算法的調度流程

2.3 E-mm任務調度算法

任務分配給資源之前，首先確定該資源是否有足夠的能量來執行此任務。只有當移動資源能量充足時，才把任務分配給該移動資源執行。假設資源與網格系統斷開連接時消耗很少的能量，可以忽略不計，那么移動資源通常處于空閑和任務執行狀態。電池可用剩余能量是決定電池運行時間的主要因素。電源法是國家信息產業部為通信行業電池容量選擇而規定的方法。

式中:Q為電池組容量;I為電池組電流;K為電池保險系數（取1.25）;T為電池放電時間（單位為h）;H為電池放電系數;A為電池溫度系數（1/c）;P為電源的標稱容量（單位為V·A）;Umin為電池組最低電壓;Pf為電源的功率因子;q為放電容量系數。

電池的能量是指電池在一定條件下，對外做功所能輸出的電能，通常用W表示。實際能量是指電池放電過程中實際放出的能量，在數值上等于實際容量與平均輸出電壓的乘積，即

式中:Umax為終端充電滿是的最大電壓值;Umin為終端放電至某一極限的最小電壓值。

式中:tj

in表示資源處于網絡連接狀態下接收第j個任務的原始數據所需的時間;tji表示資源i計算第j個任務需要的時間;tj

out表示資源處于網絡連接狀態下發送第j個任務的輸出結果數據所需的時間;Wiavai表示資源i可用剩余能量。

根據式（9）和式（10）計算移動設備的最大可持續時間和任務執行的成功率。Pbusy，Pidle，Ncom和Nall分別表示移動終端處于執行、空閑狀態的功率消耗、任務執行完成數和總任務數。

根據上式（11）判斷資源的持續時間是否滿足該任務執行不受能量的影響。反之，則導致任務執行失敗。本文研究根據調查統計移動終端的電池容量一般是3 000～4 500 mAh，當終端處于空閑狀態時電流為50～80 mA，處于忙時的電流為120～150 mA。

3 仿真與分析

假設場景是同一網格域中的資源數選取為350，任務數從500以步長為200遞增到2 500。根據以上3種分組策略將任務數分組后和未分組時，分別采用Min-Min算法和E-mm算法進行仿真，對任務執行成功率進行比較，得到4種情況的任務執行成功率，如圖3所示。

圖3 不同任務數下任務分組策略的成功率比較

從圖3分析，可得出隨著任務數的遞增，兩種算法的成功率都有所下降。隨著任務成功執行，消耗了移動資源的能量。因為移動資源的能量有限，無法承擔過大的任務量，所以任務數越多，執行成功率越低。針對分組策略詳細分析如下，如選取資源數為350，任務數為1 500。按照上述3種分組方式，將任務分為8個組，得到各組的任務數如圖4所示。

圖4 任務數為1 500時，各組的任務數

本文ps1，ps2分別代表Min-Min算法和E-mm算法的任務執行成功率。分別針對不同的分組策略采用Min-Min算法和E-mm算法，分別仿真分析得到不同分組模式下，任務執行的總時間跨度如圖5～圖8所示。

針對上述對數分組，任務數為1 500，資源數為350，ps1=0.81，ps2=0.99時，仿真驗證該系統中兩種算法下的各個資源上的負載情況如圖9所示。綜合上述分析，當任務數較少時，任務不分組和分組的優越性不是很明顯。隨著任務數的增加，將任務數進行分組調度的優越性就很明顯，使得系統的高優先級任務調度成功率大幅提高和執行時間縮短，但是犧牲了低優先級任務大量的等待時間，來提高高優先級的任務執行成功率。其中在任務量較大的環境下，對數分組策略是最佳選擇。

圖9 對數分組時，兩種算法的資源負載

4 結論

通過對移動網格中任務量大時的調度算法進行研究，考慮移動網格中移動終端能量約束的任務調度方式，結合移動網格中移動終端的特點改進經典的Min-Min調度算法。根據任務量大小，先對任務進行分組和分別計算移動終端可用剩余能量的持續時間。通過能量與電流間的轉化關系計算出各個資源的可用時間，優先選擇高優先級的任務匹配可用資源參與調度，盡量減少由于資源能量受限對系統任務調度所產生的影響。通過仿真驗證總執行時間、資源利用率、任務執行成功率等評價指標，說明在此環境下E-mm算法優于傳統的Min-Min算法。采用E-mm算法后系統能夠獲得較好的負載均衡性能，任務執行成功率也得到提高。

:

［1］LITKE A，SKOUTAS D，VARVARIGOU T.Mobile grid computing:changes and challenges of resource management in a mobile grid environment［EB/OL］.［2012-06-15］.http://www.akogrimo.org/modulesfe0a.pdf?name=UpDownload&req=getit&lid=28.

［2］徐慧媛，袁捷.網格應用中基于動態分組的調度策略［J］.計算機應用與軟件，2006，11（23）:58-59.

［3］KANSAL A，ZHAO F.Fine-grained energy profiling for power-aware application design［J］.Sigmetrics Performance Evaluation Review，2008，36（2）:26-31.

［4］COSTA G D，GELAS J P，GEORGIOU Y，et al.The green-net framework:energy efficiency in large scale distributed systems［C］//Proc.IEEE International Symposium on Parallel and Distributed Processing，2009.Rome:IEEE Computer Society，2009:1-8.

［5］都志輝，陳渝，劉鵬.網格計算［M］.北京:清華大學出版社，2002.

［6］吳高峰，蔣玉明.基于QoS改進的Min-Min網格調度算法［J］.微計算機信息，2009，25（9）:110-112.

［7］曹懷虎，余鎮危，徐壽林.網格環境中任務調度算法的研究［J］.計算機工程與應用，2004（5）:87-88.

Study of Grouping Tasks Scheduling Algorithm in Mobile Grid

LUO Xianbing1，WU Xianglin2

（1.Institute of Communication Planning and Design，GCI Science＆Technology Co.，Ltd.，Chongqing 400042，China;2.Chongqing Key Lab of Mobile Communications Technology，Chongqing University of Post and Communications（CUPT），Chongqing 400065，China）

Aiming at the large amount of the mobile terminals task scheduling problem in mobile grid，considering the limited mobile resource and its energy limited（the small-capacity battery）factors at the same grid domain，it’s important to improve the task execution success ratio and the utilization rate of resources particularly.To improve Min-Min algorithm，first according to the exp，linear，log function，it divides a large number of tasks into groups to determine the respective number of tasks，and then proposes Energy Min-Min algorithm（E-mm algorithm），which is combined the mobile terminal energy restriction with Min-Min algorithm for task scheduling.Through the simulation analysis，the modified algorithm is much better than the Min-Min algorithm，which improves the success rate of task execution，and the system load balancing effect is improved obviously.

mobile grid;E-mm algorithm;remaining energy;task grouping;task scheduling

TN949.6

A

羅顯兵（1979— ），學士，主要從事無線系統網絡咨詢規劃設計、網絡優化相關工作;

吳香林（1987— ），女，碩士，主要研究移動通信及移動網格。

責任編輯:任健男

2012－09－19