移動網(wǎng)格資源調(diào)度算法

摘要:移動網(wǎng)格是近年來興起的新技術(shù)研究熱點，由于移動設(shè)備本身資源有限(計算速度慢和內(nèi)存小)，電池容量小等問題，移動網(wǎng)格的資源調(diào)度算法顯得尤為重要，綜合各種傳統(tǒng)的資源預(yù)言模型，該文提出了一種一般的機動性資源調(diào)度預(yù)言模型，此模型通過利用有限的移動設(shè)備資源，發(fā)揮其最大性能，以此來降低移動設(shè)備的響應(yīng)時間。預(yù)言模型在固定資源模式情況下改進了移動網(wǎng)格資源的調(diào)度算法，并進行了模擬試驗。

關(guān)鍵詞:移動網(wǎng)格;預(yù)言模型;資源調(diào)度

中圖分類號:TP311文獻標識碼:A文章編號:1009-3044(2009)26-7406-03

The Algorithm of Resource Scheduling of Mobile Grid

YANG Wei1， LV Hong-wei2

(1.Graduate Student's Group， CAPF Project institute， Xi'an 710086， China; 2.Network Management Centre， CAPF Project Institute ，Xi'an 710086， China)

Abstract: It is the new technical research focus in recent years to Mobile Grid， because resources of mobile devices are limited (calculate slowly and the small memory)， the question such as being small of the capacity of the battery， the algorithm of scheduling of resource which Mobile Grid seems particularly important， comprehensive resource prophecy models of different tradition， this text has put forward a kind of general prophecy model of scheduling of resource of mobility， this model gives play to its greatest performance through utilizing limited mobile device resources， so as to reduce the response time of mobile devices. The prophecy model has improved dispatcher's algorithm who Mobile Grid in case of regular resource mode，and has carried on the simulated test.

Key words: Mobile grid; prophecy model; resource scheduling

網(wǎng)格是分布式技術(shù)的新發(fā)展，其目的是利用網(wǎng)絡(luò)把分散在不同地理位置的資源組織成為一臺虛擬的超級計算機，實現(xiàn)計算資源、存儲資源、數(shù)據(jù)資源、信息資源、知識資源、設(shè)備資源等各種動態(tài)的、異構(gòu)的、自治的、分布廣泛的資源的全面共享和協(xié)同解決問題，從而充分利用網(wǎng)絡(luò)上的閑置資源，提高資源的利用率。

隨著移動無線網(wǎng)絡(luò)系統(tǒng)的快速發(fā)展，用戶在任何地點、任何時間都可以訪問全球網(wǎng)絡(luò)資源。這意味著除了靜態(tài)結(jié)點外，網(wǎng)格系統(tǒng)也應(yīng)考慮把移動結(jié)點包含在內(nèi)，這種結(jié)合所產(chǎn)生的技術(shù)就稱為“移動網(wǎng)格計算”。它以無縫、透明、安全、有效的方式支持移動用戶和資源，是無線技術(shù)與網(wǎng)格計算這兩種新技術(shù)的融合。

在移動網(wǎng)格體系結(jié)構(gòu)(如圖1)中定位移動設(shè)備的角色，可以考慮兩種，一是可作為同網(wǎng)格系統(tǒng)交互的接口，使用者可通過移動設(shè)備向網(wǎng)格要求服務(wù)，利用網(wǎng)格資源來完成任務(wù)，可遠程監(jiān)控任務(wù)的執(zhí)行，并從網(wǎng)格中獲得所要求的結(jié)果;另一種是把移動設(shè)備也作為網(wǎng)格的計算資源，可參與到網(wǎng)格的計算任務(wù)中，而不僅僅是網(wǎng)格服務(wù)的接收者。因此，移動設(shè)備要有效地嵌入到網(wǎng)格中，既可以作為要求網(wǎng)格服務(wù)的接收者，也可以作為網(wǎng)格服務(wù)的提供者。

目前移動網(wǎng)格資源的選擇和分配方法的模型主要有以下六種:

1) 基于距離的選擇。當有多個網(wǎng)格資源可用時，根據(jù)客戶端距網(wǎng)格資源的遠近，選擇較近的資源。必須根據(jù)經(jīng)驗數(shù)據(jù)建立初始值，放入規(guī)則庫;在運行時記錄相關(guān)的參數(shù)，更新規(guī)則庫。

2) 基于資源的貪心選擇算法。根據(jù)資源的豐富程度，選擇對應(yīng)用一次性盡量充足可用的資源。

3) 基于優(yōu)先隊列的選擇算法。將不同的應(yīng)用請求根據(jù)客戶的信譽度、應(yīng)用的類型、緊急程度等進行分類，建立多個優(yōu)先級隊列。調(diào)度隊列時，分配不同的權(quán)重給不同的隊列，同一隊列采用輪轉(zhuǎn)(round trip)算法，對請求分配資源。

4) 根據(jù)網(wǎng)格經(jīng)濟的原則，選擇代價(網(wǎng)絡(luò)跳數(shù)、時間或金錢等)最小的資源。當有多個因素要綜合考慮時，使用加權(quán)求和的方式，選擇決策值最優(yōu)的資源。

5) 基于協(xié)議的選擇算法。由于不同的協(xié)議對數(shù)據(jù)的緩沖和交付策略不同，將應(yīng)用請求按協(xié)議劃分，比如TCP和UDP，按協(xié)議的時間敏感性優(yōu)先的原則進行調(diào)度，對同一協(xié)議的請求隊列按先來先服務(wù)(FIFO)的原則進行處理。

6) 基于響應(yīng)性能的選擇算法。根據(jù)距離、計算能力、網(wǎng)絡(luò)帶寬等因素進行綜合計算，得出預(yù)測的響應(yīng)時間，選擇響應(yīng)性能最好的網(wǎng)格資源。

1 機動模型

一般講用戶的行為或移動設(shè)備是很難預(yù)言的，該文在移動網(wǎng)格環(huán)境中為資源調(diào)度提出了一種一般的機動性模型。對于一種移動的資源來說，其狀態(tài)有兩種可能性:一種是移動資源正反向分開，另一種是資源正相向接近。帶有其它參數(shù)并且參加計算的資源，其移動性要在資源選擇過程中重點被考慮。移動性參數(shù)用來表示一種資源保持的時間預(yù)言。任務(wù)分派基于預(yù)言的時間。為了區(qū)別不同的參數(shù)變量的影響，可以使用相似的信號或者資源的位置意識。本文對資源位置意識進行了解釋，每種資源在任何瞬間都知道它的單元信息。機動模型假設(shè)移動末端設(shè)備以平均速度改變它的位置。移動性須假設(shè)為一個移動的終端改變位置的平均速度。機動模型(如圖2)有兩種形式:靜止與移動(static-mobile)和移動與移動(mobile-mobile)。第一種形式靜止與移動(static-mobile)即靜止的一個核心資源和遍布其周圍的移動的移動設(shè)備。第二種形式是核心資源和移動資源設(shè)備都是移動的。這種形式通常討論的全部是分散的基礎(chǔ)設(shè)施而沒有靜止的基礎(chǔ)設(shè)施。

基于應(yīng)用領(lǐng)域，在任務(wù)分配時傳統(tǒng)的調(diào)度程序通常考慮不同的參數(shù)，例如計算能力和貯存工作任務(wù)的能力等，移動資源被認為有能力單獨地處理一個被分配的工作。

這個機動性模型與移動網(wǎng)格環(huán)境中的資源調(diào)度程序結(jié)合起來改進資源調(diào)度的性能，提高了資源的利用率，縮短了移動資源的響應(yīng)時間。機動性模型的用戶及移動設(shè)備使用最基本的可計算的參數(shù)。模型使用的參數(shù)如“用戶范圍”，“平均機動性”和“在范圍內(nèi)的時間”等。“用戶范圍”是指用戶能夠覆蓋的范圍，并且在這個范圍內(nèi)用戶能與移動設(shè)備進行通信。“平均機動性”，一個可計算的參數(shù)，是指一種資源或用戶(基于用戶和資源的移動性)的平均機動性。它主要是通過在用戶和移動資源之間最近發(fā)生的通信量進行計算。“在范圍內(nèi)的時間”參數(shù)指在用戶范圍內(nèi)為顯示資源可用性被預(yù)言的時間。下面給出用于計算“平均機動性”和“在范圍內(nèi)的時間”兩個參數(shù)的方程式如下:

平均機動性=abs(第一次方位 — 第二次方位) (1)

方位可以簡化為用戶和資源之間的距離。方位通過找到兩個最近相互發(fā)生作用的用戶或移動設(shè)備之間的差別來計算。“在范圍內(nèi)的時間”這個參數(shù)通過方程式(2)計算。“距離”是指在用戶和資源(新位置)的位置之間的網(wǎng)差別。

在范圍內(nèi)的時間=(用戶范圍-距離)/平均機動性(2)

在單一的迭代里被分配到一種資源的工作數(shù)量通過方程式(3)計算。參數(shù)\"放棄任務(wù)\"是通過參數(shù)“在范圍內(nèi)的時間”和“工作完成時間”進行計算。 參數(shù)“放棄任務(wù)”的價值是為一種資源分派任務(wù)。

放棄任務(wù)=在范圍內(nèi)的時間/ 工作完成時間 (3)

基于\"放棄任務(wù)\"參數(shù)的價值，在對移動資源進行任務(wù)分派時，下列規(guī)則被使用:

If Value (放棄任務(wù)) > 0 Then

Assign job(s) based the value of “放棄任務(wù)” parameter

Else

Reject assignment

End If

上述模型是一個靜止用戶與移動設(shè)備資源進行資源調(diào)度時的機動性模型。模型需要擴展成為一個移動用戶和移動的設(shè)備之間進行資源調(diào)度時的機動性模型。通過計算基于兩個移動性因素的\"平均機動性\"參數(shù)對此機動性模型進行擴展。一個移動性因素考慮用戶和另一個移動性考慮資源。用戶平均機動性簡化為通過從新位置中減去老位置而獲得。用戶維持了資源的兩次方位。移動-移動模型的\"平均機動性\"通過方程式(4)計算

平均機動性=abs(第一次方位—第二次方位—用戶平均機動性)(4)

其它參數(shù)是通過上述靜止-移動模型得到“在范圍內(nèi)的時間”和“放棄任務(wù)”參數(shù)方法的方程式得到，“距離”參數(shù)的計算現(xiàn)在是新用戶位置和資源的新位置之間的網(wǎng)差別。

2 模型的試驗

我們通過簡單的實驗證明被提議的機動性模型和資源預(yù)言。實驗假設(shè)用戶和資源在任何規(guī)定的時間都知道它們的具體位置。這個方位的確定通過GPS (全球衛(wèi)星定位系統(tǒng))很容易被實現(xiàn)與協(xié)調(diào)。當GPS為簡單協(xié)調(diào)時，實施考慮XY兩個參數(shù)。當與用戶通信的移動資源改變它們的位置時，用戶被認為是靜止的。XY的變化范圍在0 和500之間考慮。用戶的范圍設(shè)為200米。用戶的位置是(200，200)，移動資源的第一個位置是(250，200)，第二個位置是(300，200)。為了計算方位，兩段距離從用戶到資源被基于兩個位置測量。第一個方位為50 ，第二個方位為100。根據(jù)測量的方位利用\"平均機動性\"方程式1求出平均機動性。計算\"平均機動性\"參數(shù)時使用的移動資源第一個方位為50。絕對價值被考慮在全部情況里，正的機動性價值顯示資源正離開用戶，負的機動性價值表明資源將移動向用戶。參數(shù)“在范圍內(nèi)的時間”通過計算參數(shù)\"在用戶里的范圍\"和\"平均機動性\"獲得的價值是2個單位時間。假定單位時間內(nèi)能夠完成被分配到一種資源的任務(wù)。基于這個預(yù)言模型，兩個子任務(wù)將被分配到移動資源，并且移動資源在離開用戶范圍之前，提供結(jié)果。

為了延伸為一種用戶和移動資源兩個都是移動的模型環(huán)境中進行實驗驗證，實驗進行如下，參照靜止-移動模型提及的預(yù)測模型，用戶的最初位置是(200，200)和資源的位置是(225，200)。第一個方位被給25的最初位置計算。用戶和資源移到新位置。 用戶的新位置是(175，200)和資源的新位置是(250，200)。 新距離從用戶到資源為75。 關(guān)于用戶和資源的“平均機動性”是125。參數(shù)“在范圍內(nèi)的時間”的值是1個單位時間，這表示僅僅只有一個工作任務(wù)可能被分配到移動資源。

3 結(jié)論

該文在移動網(wǎng)格環(huán)境中為資源預(yù)言提出了一個一般的機動性模型，提出了一種簡單的實驗機制，并且證明了在兩種機動性模型的基礎(chǔ)上資源調(diào)度選擇的機制，即靜止-移動模型和移動-移動模型。第一種機動性模型是基于靜止的用戶和移動的資源。另一種則是機動性模型考慮移動用戶和移動資源設(shè)備。在這個機動性模型上資源選擇和任務(wù)分配被簡單的實驗所證明。在基于響應(yīng)時間的基礎(chǔ)上，資源被預(yù)言，它在用戶范圍內(nèi)保持通信，未來的工作是為一般的機動性模型提出資源預(yù)言模型，并進行實驗驗證。

參考文獻:

[1] 徐志偉，李偉.織女星網(wǎng)格的體系結(jié)構(gòu)研究[D].中科院計算所，2002.

[2] 都志輝，陳渝，劉鵬.網(wǎng)格計算[M].北京:清華大學出版社，2002.

[3] Weiser M.Ubiquitousc omputing[J].Computer，1993，26(10):1-72.

[4] Satyanarayanan M.Pervasive computing:Vision and challenges[M].IEEE Personal Communications，2001:10-1.

[5] 移動網(wǎng)格變革服務(wù)[EB/OL].http://www.ccu.com.cn/houtai1/content.asp?newsid=1892.

[6] 李璽，胡志剛.計算網(wǎng)格中的資源選擇與調(diào)度算法[J].計算機工程與應(yīng)，2005(11).

[7] 都志輝，陳渝，劉鵬.網(wǎng)格計算[M].北京:清華大學出版社，2002.

[8] Park S M，Kim J H.Chameleon: A Resource Scheduler in a Data Grid Environment[C].Tokyo，Japan:2003 IEEE/ACM International Symposium on Cluster Computing and the Grid (CCGRID'2003)，2003.

[9] Farooq U，Khalil W.A Generic Mobility Model for Resource Prediction in Mobile Grids[C].IEEE，International Symposium on Collaborative Technologies and Systems (CTS 2006)，2006.