移動網(wǎng)格中任務(wù)分組的調(diào)度算法研究

羅顯兵，吳香林

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

移動網(wǎng)格中任務(wù)分組的調(diào)度算法研究

羅顯兵1，吳香林2

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

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

移動網(wǎng)格;E-mm算法;剩余能量;任務(wù)分組;任務(wù)調(diào)度

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

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

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

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

1 移動網(wǎng)格的系統(tǒng)結(jié)構(gòu)

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

圖1 移動網(wǎng)格系統(tǒng)結(jié)構(gòu)圖

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

2 移動網(wǎng)格的任務(wù)調(diào)度

任務(wù)調(diào)度問題實質(zhì)就是一個由用戶提出的N個需要調(diào)度的任務(wù)和系統(tǒng)中M個可用的資源構(gòu)成的場景下，把N個任務(wù)以最合理的方式匹配到M個可用的資源上，目的是使得任務(wù)的總完成時間盡可能小［6］，任務(wù)執(zhí)行成功率高和資源負載均衡效果較好。

2.1 任務(wù)分組

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

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

線性函數(shù)方式為

指數(shù)函數(shù)方式為

對數(shù)函數(shù)方式為

式中:n=1∶8（分組等級號），GN為n號分組等級任務(wù)數(shù)，設(shè)定具體的a，b，k參數(shù)，可以得到對應(yīng)的優(yōu)先級分組中的任務(wù)數(shù)。通過對運用以上3種優(yōu)先級劃分后，任務(wù)執(zhí)行成功率、資源負載等性能進行分析，得出3種方式分別適合的移動網(wǎng)格調(diào)度環(huán)境。

2.2 Min-Min任務(wù)調(diào)度算法

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

圖2 Min-Min算法的調(diào)度流程

2.3 E-mm任務(wù)調(diào)度算法

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

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

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

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

式中:tj

in表示資源處于網(wǎng)絡(luò)連接狀態(tài)下接收第j個任務(wù)的原始數(shù)據(jù)所需的時間;tji表示資源i計算第j個任務(wù)需要的時間;tj

out表示資源處于網(wǎng)絡(luò)連接狀態(tài)下發(fā)送第j個任務(wù)的輸出結(jié)果數(shù)據(jù)所需的時間;Wiavai表示資源i可用剩余能量。

根據(jù)式（9）和式（10）計算移動設(shè)備的最大可持續(xù)時間和任務(wù)執(zhí)行的成功率。Pbusy，Pidle，Ncom和Nall分別表示移動終端處于執(zhí)行、空閑狀態(tài)的功率消耗、任務(wù)執(zhí)行完成數(shù)和總?cè)蝿?wù)數(shù)。

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

3 仿真與分析

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

圖3 不同任務(wù)數(shù)下任務(wù)分組策略的成功率比較

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

圖4 任務(wù)數(shù)為1 500時，各組的任務(wù)數(shù)

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

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

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

4 結(jié)論

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

:

［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］徐慧媛，袁捷.網(wǎng)格應(yīng)用中基于動態(tài)分組的調(diào)度策略［J］.計算機應(yīng)用與軟件，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］都志輝，陳渝，劉鵬.網(wǎng)格計算［M］.北京:清華大學(xué)出版社，2002.

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

［7］曹懷虎，余鎮(zhèn)危，徐壽林.網(wǎng)格環(huán)境中任務(wù)調(diào)度算法的研究［J］.計算機工程與應(yīng)用，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— ），學(xué)士，主要從事無線系統(tǒng)網(wǎng)絡(luò)咨詢規(guī)劃設(shè)計、網(wǎng)絡(luò)優(yōu)化相關(guān)工作;

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

責(zé)任編輯:任健男

2012－09－19