多QoS約束下的PSO 云存儲任務調度算法

李 飛，易傅瀟，王 浩

（成都信息工程學院 信息安全工程學院，四川 成都610225）

0 引 言

云存儲的核心是對大量數據的存儲和管理。在數據的存儲方面：存儲系統數據的有效性和完整性是最受關注的性能指標，因此云存儲系統的冗余機制提供了數據在不同節點上的備份功能，也就是其冗余的副本［1］。在數據的管理方面：當用戶向服務器發出數據請求時，系統會根據相應的調度策略為用戶提供相對最優的數據副本以及路徑的選取，調度策略的優劣很大程度上決定了系統的運行處理效率［2］。在云計算中的調度算法相對較為豐富，但云存儲在任務調度方面有區別于傳統云計算的特點，在已有的對云存儲的任務調度算法的研究中，引入了存在矩陣以適應云存儲的特點，提出了針對云存儲環境的特殊要求，相對于云計算任務來說，由于云計算任務可由云中任意節點提供，但云存儲中的節點會出現節點沒有任務所需要的數據的情況，引入了存在矩陣 （exist matix，EM）的概念來指示任務和資源節點的對應關系，資源節點通過存在矩陣限制其初始解和解空間，從而使得初始解以及解空間有意義。然而，網絡環境是動態變化的，因此，引入網絡服務質量QoS （quality of service）參數，動態實時地反映出當前網絡的狀態，使得在計算的迭代過程中可以根據QoS參數以及相對應的適應度函數來動態調整其影響參數，從而達到了優化算法的作用。同時，可以根據用戶對網絡QoS的不同需求，使得產生解更趨向于用戶的QoS需求。例如部分用戶的應用需求僅僅是關注于吞吐量的大小，而其他用戶的應用需求可能不一定是追求其最大的吞吐量，而是對其延遲有很高的敏感度，由此可根據不同用戶不同應用場景調整其對QoS參數的需求，從而使用戶直觀地感受到以服務質量為中心的調度策略。

1 云存儲任務調度抽象

本文研究的模型前提為 “批調度”模型，即在單位時間內，等待調度的任務數為n，而調度是按照這n 個任務來啟動一次調度任務，相類似QoS需求的用戶可歸集為一組任務集合作為一次調度任務。本文使用以下定義［3，4］：

定義1 用T ＝｛t1，t2，…，tn｝表示一個任務集合，單位時間內該任務集合中等待被調度的任務數為n。

定義2 用N ＝｛n1，n2，…，nm｝表示云存儲系統中的節點集合，角標代表節點數量。Ni代表ni節點上的數據資源，特別要指出的是相對于云計算中節點一定能執行計算任務，而云存儲系統的節點有可能不能提供用戶所請求的數據。

定義3 用V ＝｛v1，v2，…，vn｝表示任務調度向量，即云存儲調度方案。角標代表任務長度，n表示任務總數為n，vi表示第i個任務的數據在vi節點上取得。

定義4 用Fv 代表任務調度方案的調度向量函數。它是調度算法的數學模型，不同調度算法的根本區別就在于調度向量函數的不同。

2 多QoS約束下的限制解空間PSO 云存儲任務調度算法

2.1 標準PSO 算法及限制PSO 解空間的云存儲調度算法

粒子群優化 （particle swarm optimization，PSO），又稱微粒群算法，PSO 算法模擬了一個簡化的社會模型，而該社會模型是基于群體的，群體中的個體可根據自己以及群體中的最優值來判斷進而調整自己或者全局的最優值，實現自適應的優化。PSO 算法中群體被抽象為D 維空間中沒有體積及質量的粒子集合［4］。個體粒子中第i個粒子表示為Xi＝（xi1，xi2，…，xiD），通過適應度函數得到該粒子的適應值 （fitness value），粒子在飛行過程中得到的最優位置記為Pi＝（pi1，pi2，…，piD），也稱為個體極值pbest，作為個體粒子的飛行經驗。群體中所有粒子共同發現的最好位置用符號g 表示，即Pg，也稱為全局極值gbest。個體粒子通過自己的飛行經驗極值pbest以及全局的飛行經驗gbest來更新自己的飛行速度以及位置。粒子i的速度用Vi＝（vi1，vi2，…，viD）表示，對于每一次迭代，它的第d維（1≤d ≤D）以式 （1）、式 （2）更新

其中：w 為慣性權重（inertia weight），代表粒子的慣性行為，w 越大全局尋優能力越強，但局部尋優能力降低，w 越小則相反。c1和c2為加速常量（acceleration constants），分別代表粒子個體自己的認知和對群體經驗的學習能力。Rand（）和Rand（）為兩個隨機值，其取值范圍在［0，1］中變化［5］。

標準PSO 算法在應用到云存儲環境中時，由于云計算任務可由云中任意節點提供但云存儲中的節點會出現節點沒有任務所需要的數據的情況，并且在云存儲中這種情況應該作為常態處理，而PSO 算法初始化參數的隨機產生和每一輪的更新都沒有考慮到云存儲的這一特性，所以標準PSO 算法會出現對云存儲任務無效的解，且這種無效解的隨機性較大。

限制PSO 解空間的云存儲調度算法引入了存在矩陣的概念［6］。EM 是一個n＊m 的矩陣，n表示調度任務，m 表示云存儲系統中的節點數目。矩陣中的元素代表了該任務是否存在，例如元素eij代表任務i 所需的數據節點是否在j上，0和1分別代表無和有。云存儲中的資源列表用于生成該存在矩陣。資源列表是云存儲節點與數據塊的映射表。由于云系統中對數據安全以及冗余的需求，同樣的一塊數據會存在于多個而并非全部的云存儲節點上，所以矩陣中的調度任務向量ni的行中會出現多個1的情況。

其改進在于：

（1）PSO 的初始化的解是由存在矩陣產生，而非傳統PSO 算法的隨機產生，這樣保證了初始化解的有效性。

（2）PSO 算法會根據式 （1）、式 （2）進行迭代，每次迭代的結果會根據存在矩陣進行對迭代解的檢測，判斷其是否符合存在矩陣，如果不符合則產生一個新的解，并且滿足存在矩陣的限制條件。

（3）如果算法陷入了局部的最優解時，傳統算法會隨機產生新的解，但這個解的有效性是未知的，而該算法會在存在矩陣中產生新的解，保證其解的有效性。

2.2 多QoS約束下的限制解空間PSO 云存儲任務調度算法

存在矩陣解決了PSO 的初始化解不再隨機產生，而是根據資源列表生成存在矩陣。同時在迭代的過程中也會在存在矩陣中進行驗證，防止了無效解的產生。但是由于其未考慮到網絡狀態的變化，所以其不能通過網絡狀態的實時更新從而根據當前網絡狀態得到最優值。

通過多QoS參數作為當前網絡狀態的度量定義QN 是一個n＊n 的矩陣，n 表示云存儲系統中的節點數目，Qij代表節點i到節點j 的QoS狀態信息，包括帶寬、時延、抖動的信息。

2.2.1 QoS參數的應用

本文研究的重點放在多QoS約束下的根據不同用戶或應用場景對多QoS敏感度不同，符合用戶或應用場景需求的最小代價選路問題［8，9］。云存儲網絡節點的集合可以建模為一個無向加權圖G（V，E），其中V 是代表所有云存儲的節點。E是物理上或者邏輯上代表鏈接節點的所有的邊。每一組鏈路有三組權重BandWith、Delay、Jetter分別對應可用帶寬，延遲和抖動。

路徑P（s，d）為任務節點以及數據節點之間的鏈路，且節點之間有多條鏈路可以到達，M ∈V 代表云存儲節點與任務節點間最短路徑的節點集合，一條鏈路上的總時延取P（s，d）鏈路上所有經過路徑的鏈路時延之和［10，11］

在QoS向量中鏈路P（s，d）上的總時延定義為從路徑上起點到終點上的最小值

樹的抖動定義為從源節點到終節點路徑上延遲的平均值差值

式中：delay＿avg——從源節點到終節點的延遲的平均值。

鏈路的瓶頸帶寬被定義為T 中鏈路的最小帶寬

鏈路的開銷被定義為該鏈路上邊的開銷之和。CostT（s，M）引用參考STP協議中1Gbit／s的寬帶鏈路的STP開銷與bandwidth之間的關系進行設定。

帶延遲帶寬約束的QoS選路問題可以被描述如下：已給定的網絡圖G，一個源任務節點s，云存儲節點到任務節點鏈路節點集合M，延遲，抖動延遲和帶寬約束分別為Dmax，Dj和Dmin。 并通過 DelayP（s，d）、JitterP（s，M）、BandwidthP（s，M）并且符合以下條件：

（1）鏈路P（s，d）為任務節點到數據節點的最短路徑；

（2）云存儲任務的請求源節點是S；

（3）所有的數據節點都在云存儲節點V 中，且受存在矩陣約束；

（4）數據源樹必須滿足以下的多QoS約束：

端到端的延遲要求

抖動延遲約束

給QoS保證的帶寬

2.2.2 適應度函數

PSO 的每一次迭代都會被評估計算。在QoS調度問題上每一次迭代被一個適應度函數所驅動，這個適應度函數根據粒子對減少鏈路的花費來評估粒子進化的質量［11］。適應度函數的定義如下

式中：k1和k2——懲罰系數，懲罰系數的值決定了懲罰程度。

多QoS約束下的存在矩陣的PSO 調度算法如下：

（1）設置迭代的次數Li＝0，由存在矩陣代替隨機的初始解生成V0；

（2）While Li≤MaxLi；

（4）由適應度函數f（P（s，M））得到fi；

（5）當適應度函數fi未到達閥值時，break，輸出Vi；

（6）Li＝Li＋1；

（7）根據PSO 算法得到迭代一輪后的Vnew；

（8）將Vnew與存在矩陣做匹配，如果不匹配則重新生成Vnew；

（9）將得到的數據節點與多QoS矩陣做對比，對要求的Dmax，Dj和Dmin做匹配，如果不滿足用戶所提出的QoS限制則按重新生成Vnew，如果連續10次沒有生成滿足條件的Vnew，則使用第十次生成的Vnew；

（10）End While

3 實驗和分析

3.1 實驗環境和實驗參數

由于網絡環境的不同對實驗結果的影響比較大，而又要兼顧與現有調度算法的比較，所以采取了將網絡拓撲的節點分別設置為10，20，40，80，160.存在矩陣實時的分配產生。網絡環境的設置如下：各鏈路的帶寬在 ［100，1000］之間隨機分布，單位為兆 （M）。延遲在 ［0，5］之間隨機分布，單位為毫秒 （ms）。

實驗默認的最大迭代次數為100 次，調度向量中含有10個任務。為得到一般性實驗結果，對于以上每種網絡大小環境的測試數為10次，所需記錄的實驗數據有 “運行時間”與 “QoS滿足率”，“運行時間”能夠直觀表達算法之間的性能差異， “多QoS滿足率”表示了算法在多QoS約束下的優化程度，以上數據均取得10次測試的平均值。

3.2 實驗結果分析

圖1分別代表了限制PSO 解空間的云存儲調度算法、多QoS約束下的限制解空間PSO 云存儲任務調度算法在相同實驗環境下的實驗結果。表1、表2為運行參數。從表中實驗數據可以看到多QoS約束下的限制解空間PSO 云存儲任務調度算法，在運行時間上與前者算法近似，這是因為雖然后者算法在QoS保障上較優，但在迭代過程中，當得不到滿足多QoS 約束的條件時，會重新計算得到新的Vnew，雖然不能超過10次重新計算的限制，但仍然增加了算法在運行時間上的開銷，從而使得算法在運行時間上沒有特別大的優勢。而在QoS的滿足率方面，其優勢就較為明顯。在多QoS約束條件Dmax＝20，Dj＝10，Costmax＝40下，限制解空間PSO 算法在迭代過程中隨著節點數目的增多，網絡情況復雜程度增加，多QoS滿足率下降的較為明顯，當節點數目增至160 時，僅有26%符合QoS的要求，QoS平均滿足率為33%。而在多QoS約束下的迭代由于考慮到了每一輪迭代的結果均要滿足多QoS的需求，所以結果相對于需求值不會有太大的偏離，當節點數目到達160時多QoS 的滿足率能夠達到38%，QoS 平均滿足率為45.6%。通過圖1對兩組數據的對比，直觀展現了二者之間QoS滿足率之間的對比。因此，雖然在運行時間和執行次數上兩者之間差距不大，但是多QoS優化算法在試行中有更好的滿足率，更能夠體現網絡的實際狀況，從而滿足不同用戶及應用對于網絡的不同需求，提高用戶直觀的網絡服務質量。

圖1 QoS滿足率的比較

表1 限制解空間PSO 算法

表2 多QoS約束下的限制解空間PSO 云存儲任務調度算法

4 結束語

本文對云存儲任務調度算法進行了研究，探討了PSO調度算法在云存儲系統調度中的問題，同時引入了前人針對云存儲系統的改進，即任務和資源節點的關系矩陣：存在矩陣。通過存在矩陣的引入，排除了對于云存儲任務無效的解，PSO 算法的迭代次數以及運行時間效率有了極大的提高，但這種提高是在理想的網絡環境中所得到的值，在真實網絡環境中，用戶對于所需的云存儲資源有不同的需求，通過QoS的約束，使得算法所產生的解更趨向于用戶對于資源的QoS需求，仿真結果表明，在本文所提出的QoS需求下，QoS滿足率有了明顯的提高。

下一步研究方向在于抽象出云存儲節點資源分布的特性，結合多QoS的特性進行更進一步的改進，使得算法在達到最優解的收斂時間以及QoS的滿足率上有更進一步的提高。

［1］FENG Guofu，LI Wenzhong，ZHANG Jincheng，et al.Replica distribution for search size minimization in unstructured overlay ［J］.Chinese Journal of Computers，2011，34 （4）：628－635 （in Chinese）.［馮國富，李文忠，張金城，等.無結構覆蓋網絡中面向搜索范圍最小化的副本分布 ［J］.計算機學報，2011，34 （4）：628－635.］

［2］Lin G，Dasmalchi G，Zhu J.Cloud computing and IT as a service：Opportunities and challenges ［C］／／IEEE International Conference on Web Services.IEEE，2008.

［3］JIN J，Rothrock L，Mcdermott PL.Using the analytic hierarchy process to examine judgment consistency in a complex multiattribute task ［J］.IEEE Transactions on Systems，Man and Cybernetics，Part A：Systems and Humans，2010，40 （5）：1105－1115.

［4］LEI Binghan，HE Jun，HE Xiang，et al.Grid load schedule algorithm based on QoS［J］.Computer Engineering，2009，35 （24）：96－98（in Chinese）.［雷炳翰，何軍，何翔，等.基于QoS的網格負載調度算法［J］.計算機工程，2009，35 （24）：96－98.］

［5］Pedersen MEH，Chipperfield AJ.Simplifying particle swarm optimization ［J］.Applied Soft Computing，2010，10 （2）：618－628.

［6］WANG Juan，LI Fei，ZHANG Luqiao.Task scheduling algorithm in cloud storage system using PSO with limited solution domain ［J］.Application Research of Computers，2013，30（1）：127－129 （in Chinese）.［王娟，李飛，張路橋.限制解空間的PSO 云存儲任務調度算法 ［J］.計算機應用研究，2013，30 （1）：127－129.］

［7］Wang H，Meng X，Li S.A tree－based particle swarm optimization for multicast routing ［J］.Computer Networks，2010，54 （15）：2775－2786.

［8］Lin N，Yang T，Song L.A new QoS multicast routing algorithm for MPLS－TE ［C］／／International Conference on Measuring Technology and Mechatronics Automation.IEEE，2010：192－195.

［9］Yang P，Huang B.GA based QoS multicast routing algorithm in mobile ad hoc network［C］／／International Seminar on Future Bio－Medical Information Engineering.IEEE，2008：247－250.

［10］Li X，Ning Q，Jun－Ya Z.An improved GA for QoS multicast routing algorithm ［C］／／Control and Decision Conferenc.IEEE，2008：393－396.

［11］Xi－hong C，Shao－wei L，Jiao G.Study on QoS multicast routing based on ACO－PSO algorithm ［C］／／International Conference on Intelligent Computation Technology and Automation.IEEE，2010：534－537.