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

羅顯兵，吳香林

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

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

羅顯兵1，吳香林2

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 任務(wù)分組

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

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

線性函數(shù)方式為

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

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

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

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

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

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

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

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

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

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

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

式中:tj

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

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

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

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

3 仿真與分析

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

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

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

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

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

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

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

4 結(jié)論

通過對(duì)移動(dòng)網(wǎng)格中任務(wù)量大時(shí)的調(diào)度算法進(jìn)行研究，考慮移動(dòng)網(wǎng)格中移動(dòng)終端能量約束的任務(wù)調(diào)度方式，結(jié)合移動(dòng)網(wǎng)格中移動(dòng)終端的特點(diǎn)改進(jìn)經(jīng)典的Min-Min調(diào)度算法。根據(jù)任務(wù)量大小，先對(duì)任務(wù)進(jìn)行分組和分別計(jì)算移動(dòng)終端可用剩余能量的持續(xù)時(shí)間。通過能量與電流間的轉(zhuǎn)化關(guān)系計(jì)算出各個(gè)資源的可用時(shí)間，優(yōu)先選擇高優(yōu)先級(jí)的任務(wù)匹配可用資源參與調(diào)度，盡量減少由于資源能量受限對(duì)系統(tǒng)任務(wù)調(diào)度所產(chǎn)生的影響。通過仿真驗(yàn)證總執(zhí)行時(shí)間、資源利用率、任務(wù)執(zhí)行成功率等評(píng)價(jià)指標(biāo)，說明在此環(huán)境下E-mm算法優(yōu)于傳統(tǒng)的Min-Min算法。采用E-mm算法后系統(tǒng)能夠獲得較好的負(fù)載均衡性能，任務(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)用中基于動(dòng)態(tài)分組的調(diào)度策略［J］.計(jì)算機(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)格計(jì)算［M］.北京:清華大學(xué)出版社，2002.

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

［7］曹懷虎，余鎮(zhèn)危，徐壽林.網(wǎng)格環(huán)境中任務(wù)調(diào)度算法的研究［J］.計(jì)算機(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è)計(jì)、網(wǎng)絡(luò)優(yōu)化相關(guān)工作;

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

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

2012－09－19