移動網格環境下的資源調度研究

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

關鍵詞：移動網格 資源調度 微粒群算法（PSO）

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

引言

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

一、移動網格的網絡模型

移動網格建立在有線網格的框架之上，由無線網格、網關、有線網格這三部分構成。其內部的資源管理服務機制是基于移動代理的分層模型，用移動資源代理實時地對資源進行監測和分配這樣可增強系統的可擴展性，提高執行效率。

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

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

二、移動網格資源調度算法

1.問題假定

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

1.1同一時刻下，一臺節點設備僅能執行一個任務，該任務不會被其他設備搶占。

1.2一個用戶提交的任務被劃分為許多任務，任務相互之間不具備必然的依賴關系，并且不會發生數據交互。

1.3實時獲得未來一段時間內系統的預測信息，在資源節點故障或其所有者離開了網格系統的情況下，原來分配到該資源節點上的任務會被重新進行資源調度和分配。

資源調度采用以下數學模型進行搭建：

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

任務在資源上的預期執行時間：

任務到資源上執行所需的通信時間、數據傳輸時間以及結果返回所用的時間之和，統稱為通信時延：

尋求優化調度的目標就是求得這樣一種映射方案，使總的時間損耗T最小，以獲得最高效的系統性能。

2.基本微粒群算法

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

3.改進的PSO資源調度算法

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

3.1初始微粒種群，計算各微粒的適應度

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

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

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

適應值：將第個微粒當前的位置表示為，將微粒群中適應值最優的那個微粒所處的位置定義為，計算適應值。

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

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

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

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

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

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

（4）判定收斂條件

設置迭代的總次數，達到此次數時算法終止，輸出最優方案;否則重新回到步驟（2），繼續執行迭代。

三、實驗分析

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

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

結語

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

參考文獻

[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]都志輝，陳渝，劉鵬.網格計算[M].北京：清華大學出版社，2002.

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

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

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