移動網(wǎng)格環(huán)境下的資源調(diào)度研究

摘 要：本文結(jié)合移動網(wǎng)格自身的特點，構(gòu)建與其相適應(yīng)的網(wǎng)絡(luò)模型。同時，對資源決策過程中具體采用的調(diào)度優(yōu)化算法進行研究，將基本微粒群算法進行離散化編碼，在迭代的過程中引入變異算子以及遺傳算子。經(jīng)仿真，該算法不僅能提高微粒群整體向最優(yōu)解逼進的速度，更可協(xié)助避免陷入局部收斂，對大規(guī)模求解的計算效果優(yōu)越。

關(guān)鍵詞：移動網(wǎng)格 資源調(diào)度 微粒群算法（PSO）

中圖分類號：TN929.5文獻標識碼：A文章編號：1003-9082（2019）08-000-02

引言

目前，移動網(wǎng)格系統(tǒng)中重點會對移動設(shè)備進行通信接口和通信資源本身進行研究[1]。在移動網(wǎng)格中，用戶與網(wǎng)絡(luò)資源需要保持實時的、動態(tài)的連接，每個移動設(shè)備可看作為一個網(wǎng)格節(jié)點，又要解決它自身的缺陷：如頻繁移動，帶寬小，電池容量不足等問題?？梢姡绾胃咝У亟M織這些移動資源成為網(wǎng)格資源管理的關(guān)鍵問題之一。

一、移動網(wǎng)格的網(wǎng)絡(luò)模型

移動網(wǎng)格建立在有線網(wǎng)格的框架之上，由無線網(wǎng)格、網(wǎng)關(guān)、有線網(wǎng)格這三部分構(gòu)成。其內(nèi)部的資源管理服務(wù)機制是基于移動代理的分層模型，用移動資源代理實時地對資源進行監(jiān)測和分配這樣可增強系統(tǒng)的可擴展性，提高執(zhí)行效率。

此外，在移動網(wǎng)格的網(wǎng)關(guān)中需要對資源代理執(zhí)行監(jiān)控，同時還要根據(jù)執(zhí)行策略進行任務(wù)策略的選擇，具體功能包括通信接口、信息采集、任務(wù)劃分以及調(diào)度決策。信息采集作為關(guān)鍵的一個部分，用于收集和發(fā)布網(wǎng)格系統(tǒng)各節(jié)點的狀態(tài)信息;NWS是一個分布式監(jiān)控系統(tǒng)，主要用于實時跟蹤網(wǎng)絡(luò)資源和狀況，提供網(wǎng)絡(luò)性能預(yù)判功能。收集到的網(wǎng)格資源相關(guān)信息會定期反饋到調(diào)度決策模塊，以供調(diào)度決策模塊執(zhí)行相應(yīng)調(diào)度策略。

在移動網(wǎng)格運行的過程中，其中一個重要環(huán)節(jié)就是資源調(diào)度，具體地，根據(jù)系統(tǒng)吞吐量、資源利用率、用戶需求等多種因素來選擇最佳的任務(wù)分配方案。傳統(tǒng)的資源調(diào)度常常只著重考慮任務(wù)在資源上的執(zhí)行時間，而移動網(wǎng)格中更多的約束限制決定了其任務(wù)調(diào)度將更加復(fù)雜化，在選擇調(diào)度算法時，要實時地從網(wǎng)格系統(tǒng)中監(jiān)測最新的移動節(jié)點資源狀況和位置變動等信息，更新路由表，把通信因素對性能的影響作為分析的重點。

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

1.問題假定

在移動網(wǎng)格中，資源調(diào)度是把移動網(wǎng)格中提交的作業(yè)分割成許多子任務(wù)，根據(jù)子任務(wù)在不同移動節(jié)點上的執(zhí)行的吞吐量和資源利用率不同，來選擇最佳的作業(yè)分配方案，使任務(wù)完成時間最小。不同的作業(yè)調(diào)度算法可能擁有不同的調(diào)度目標，比如考慮服務(wù)質(zhì)量優(yōu)先、網(wǎng)絡(luò)跨度優(yōu)先、資源負載優(yōu)先 [2]等，這里對移動網(wǎng)格中的資源調(diào)度問題作以下幾個假定：

1.1同一時刻下，一臺節(jié)點設(shè)備僅能執(zhí)行一個任務(wù)，該任務(wù)不會被其他設(shè)備搶占。

1.2一個用戶提交的任務(wù)被劃分為許多任務(wù)，任務(wù)相互之間不具備必然的依賴關(guān)系，并且不會發(fā)生數(shù)據(jù)交互。

1.3實時獲得未來一段時間內(nèi)系統(tǒng)的預(yù)測信息，在資源節(jié)點故障或其所有者離開了網(wǎng)格系統(tǒng)的情況下，原來分配到該資源節(jié)點上的任務(wù)會被重新進行資源調(diào)度和分配。

資源調(diào)度采用以下數(shù)學(xué)模型進行搭建：

任務(wù)集合表示為，資源集合表示為，其中N小于等于M。獲取資源和任務(wù)的屬性信息矩陣：

任務(wù)在資源上的預(yù)期執(zhí)行時間：

任務(wù)到資源上執(zhí)行所需的通信時間、數(shù)據(jù)傳輸時間以及結(jié)果返回所用的時間之和，統(tǒng)稱為通信時延：

尋求優(yōu)化調(diào)度的目標就是求得這樣一種映射方案，使總的時間損耗T最小，以獲得最高效的系統(tǒng)性能。

2.基本微粒群算法

微粒群算法具有公認的諸多優(yōu)點，比如計算簡單、所需個體數(shù)目少等，尤其是在求解復(fù)雜問題時，其優(yōu)越性表現(xiàn)地更為突顯 [3-4]。其中，一個可行解可看作成“微?！?，每一個微粒會通過跟蹤多個最優(yōu)解來對自己進行更新，包括每個微粒自身尋找的個體最優(yōu)解、種群整體當(dāng)前尋找到的全局最優(yōu)解。微粒采用以下方式來更新速度和位置：

3.改進的PSO資源調(diào)度算法

本文對PSO算法進行優(yōu)化，改進的算法流程圖如下所示：

3.1初始微粒種群，計算各微粒的適應(yīng)度

設(shè)置基本參數(shù)，隨機離散編碼生成微粒群，每個微粒包含以下參數(shù)：

位置向量：，表示為把第個資源節(jié)點分配用為執(zhí)行第個任務(wù)，的范圍小于搜索空間N。

飛行速度：，表示第個任務(wù)下一次迭代所選擇的資源節(jié)點與當(dāng)前分配的資源節(jié)點之間存在的偏離，初始時的速度取值范圍可以界于（-N+1）與（N-1）之間，并且取整。

適應(yīng)值：將第個微粒當(dāng)前的位置表示為，將微粒群中適應(yīng)值最優(yōu)的那個微粒所處的位置定義為，計算適應(yīng)值。

以上參數(shù)按序存放用于表征一個微粒，主要是便于執(zhí)行迭代和參數(shù)的更新，如下表所示：

假設(shè)初始化產(chǎn)生的微粒群的微粒數(shù)目表示為D，則微粒群可用二維數(shù)組表示，大小相應(yīng)地就是D*（3*M+1），在迭代中不斷更新該數(shù)組，慢慢逼進全局的最優(yōu)解。

3.2采用遺傳選擇、隨機交叉、線性衰減的慣性因子進行迭代

將適應(yīng)度較低的部分微粒進入下一代，將其他適應(yīng)度較大的微粒執(zhí)行遺傳選擇以及隨機的交叉，然后更新微粒：當(dāng)交叉后微粒的適應(yīng)度低于之前，則不改變原始位置，如果對之前更優(yōu)，則對個人最優(yōu)解進行更新。

此外，考慮到慣性因子具有以下特點：w值越大，越對局部最小點的跳出有利;w值越小，則可以加快算法進行收斂。為此，采用線性衰減的w進行改進：

（3）對微粒的速度、位移，不斷更新個體最優(yōu)解以及全局最優(yōu)解

（4）判定收斂條件

設(shè)置迭代的總次數(shù)，達到此次數(shù)時算法終止，輸出最優(yōu)方案;否則重新回到步驟（2），繼續(xù)執(zhí)行迭代。

三、實驗分析

采用該帶有遺傳因子和交叉因子的PSO算法與基本PSO算法進行比較進行仿真，模擬了在8個移動網(wǎng)格節(jié)點上來執(zhí)行10-50個服務(wù)任務(wù)。設(shè)置初始種群為40，迭代次數(shù)為100，c1=c2=1.8，false=0.9， false=0.2。兩種算法下分配效率隨任務(wù)數(shù)增加所產(chǎn)生的影響，如圖所示：

由仿真圖可以直觀地發(fā)現(xiàn)，改進的PSO調(diào)度算法在任務(wù)數(shù)量變大的情況下調(diào)度效率更優(yōu)越。分析其原因，任務(wù)數(shù)量越大，基本PSO算法容易陷入局部最優(yōu)，使得向全局最優(yōu)執(zhí)行搜索的進度變得較慢。改進的算法則因為使用了遺傳因子、隨機交叉以及變化的慣性因子，會更加明顯可以擴大搜索范圍。此外，由于每一次迭代交叉具有隨機性，任務(wù)調(diào)度的完成時間整體上具有隨著任務(wù)量的增大而增加的趨勢，但同時也呈現(xiàn)有一定幅度的波動。

結(jié)語

本文重點是分析了移動網(wǎng)格系統(tǒng)的特征，把傳統(tǒng)網(wǎng)格資源調(diào)度模型應(yīng)用其中。為了滿足移動節(jié)點資源調(diào)度的復(fù)雜性，這里全面地考慮了影響分配方案的因素，然后采用改進的PSO算法來加快搜索的收斂速度，在更短的時間內(nèi)獲得更優(yōu)的分配方案，在應(yīng)對大規(guī)模移動網(wǎng)格中的動態(tài)資源管理問題上效果顯著。

參考文獻

[1]PHAN T，HUANG L，DULAN C. Challenge： integrating mobile wireless devices into the computational grid[C] //Proc of the 8thACM International Conference on Mobile Computing and Networking. New York ：ACM Press， 2002： 271-278.

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

[3]Kennedy J，EberhartR C. Particle swarm optimization[C]//Proc. IEEE International Conference on Neural Networks.Pis-cataway，NJ，1995

[4]曾建潮，介婧，崔志華.微粒群算法[M].北京：科學(xué)出版社， 2004： 10-15.

作者簡介;朱丹丹，（1987.5-）女，安徽省亳州市人，研究方向：通信與信息系統(tǒng)。