基于多QoS約束條件的廣域信息管理系統任務調度算法

李罡，吳志軍

（1. 天津大學電氣自動化與信息工程學院，天津 300072；2. 白城師范學院機械工程學院，吉林 白城137000；3. 中國民航大學電子信息與自動化學院，天津 300300）

1 引言

1997年，歐洲航空安全組織向美國聯邦航空局提出廣域信息管理系統（SWIM, system-wide information management）概念[1]，國際民航組織（ICAO, International Civil Aviation Organization）于2002年接受了這個概念[2]。SWIM是一個集成度很高的大規模網絡系統，它可以對內部資源進行整合和管理，從而提高系統信息的利用率和資源的共享率。SWIM作為一個信息共享平臺，為不同的民航業務子系統提供統一的數據傳輸和交換機制，并以提高子系統業務處理效率為目的，實現民航各相關單位之間的信息共享性和互通性[3]。在空管、航空公司、機場等空中交通運輸參與者之間實現一體化、標準化、靈活的通信、導航、監視、運行、氣象、情報數據的發布與共享，滿足未來民航高效協同運行的需求。

為了提高廣域信息管理系統的資源利用與共享率，需要解決系統任務調度問題，對用戶提出的需求找到合適節點進行任務處理，并且應在SWIM任務調度過程中綜合考慮用戶的服務質量（QoS,quality of service）需求。蟻群算法具有并行性和頑健性的特點，可以很快取得高質量的解，已經成功解決了很多不同類型的調度問題。本文在總結現有的網絡任務調度技術并結合 SWIM 自身特點的基礎上，以多QoS約束條件為立足點，利用蟻群優化（ACO, ant colony optimization）算法提出了一種改進傳統蟻群算法的SWIM任務調度算法QoS-ACO，保證用戶任務調度QoS要求盡可能地得到滿足，提高SWIM整體性能。

2 相關工作

目前，國內外專家學者在大型網絡系統的任務調度方面進行了很多研究，如針對現在比較流行的云計算、網格等網絡系統的研究。Min-Min算法[4]、Max-Min算法[5]、Max-Int算法[6]和遺傳算法（GA,genetic algorithm）[7]等任務調度算法都是經典的研究成果，在網絡系統任務調度中得到應用并取得了比較好的效果。此外，Buyya等[8]還提出一種基于經濟模型的優化調度模型，為研究任務調度算法提供了新的思路。但這些算法也存在一些局限性和不足，它們都是基于最小化調度目標的思想提出的，而在任務調度算法的設計和改進中很少考慮到用戶對服務質量的需求。

現在也有一些針對服務質量方面的任務調度方法研究。Castillo等[9]在解決資源調度過程中所產生的碎片問題和服務質量研究中，應用了數學幾何方法建立資源預留調度機制。劉宴兵等[10]提出的S-GTSA（grid task scheduling algorithm based on QoS similarity）在任務調度過程中應用了服務質量相似度，在一定程度上滿足了用戶的QoS需求，但在任務完成時間跨度方面的考慮不夠全面。鄧見光等[11]針對云計算中的 QoS任務調度問題進行了研究，對任務調度的多QoS目標約束條件進行形式化建模，提出了一種多QoS目標約束的云計算任務調度策略。文獻[12]研究了一種基于離散粒子群優化的可重構系統任務調度方法，在任務調度過程中配置閾值，有效隱藏了任務的配置時間，提高了系統執行性能，但其目標單一，缺少對其他QoS參數的考慮。文獻[13]設計的任務調度策略較合理，在任務調度過程中考慮的服務質量參數也比較全面，提高了系統任務調度效率，避免了系統負載不均衡現象的發生。

網絡應用的廣泛普及和網絡技術的更新發展對任務調度的研究提出了新的要求，也對任務調度的服務質量提出了更高標準。本文分析、參考了大量分布和異構環境下的網絡任務調度算法，在前人研究工作的基礎上，結合廣域信息管理系統自身的特點，針對SWIM中任務調度服務質量在任務完成時間、安全性和可靠性方面需求的特殊性進行了研究。通過采用并改進傳統蟻群算法，提出了基于多QoS約束條件的廣域信息管理系統任務調度算法QoS-ACO。仿真實驗結果表明，所提出的QoS-ACO任務調度算法具有很好的綜合QoS性能，在任務調度完成效率和滿足客戶服務質量需求方面的效果都比較好。

3 多QoS約束條件SWIM任務調度模型

3.1 SWIM任務調度模型

服務質量的約束條件有很多，在本文SWIM任務調度模型和QoS-ACO算法中，主要從以下3個方面進行考慮。

1) 時間。完成用戶提交任務所需要的時間。

2) 安全性。在 SWIM 節點上可以獲得的安全等級。

3) 可靠性。任務被成功執行的概率。

SWIM分為以下三層。

1) SWIM共享數據應用層（SDA, shared data application）。實現空管、機場和航空公司等客戶端發出服務請求。

2) SWIM公共信息管理層（CIM, common information management）。負責系統中資源配置、負載均衡監控和隊列管理等內容。

3) SWIM公共數據傳輸層（CDT, common data transport）。實現對分布的共享航空飛行等資源數據的采集。

在CIM中，SWIM任務調度中心能完成請求服務的任務調度、任務解析、任務分配以及建立服務虛擬機等功能。用戶通過任務調度中心可以完全透明化地接入SWIM資源環境中。任務調度中心對系統資源和用戶的需求進行統一分配和管理，針對不同任務的各自特點和資源需求，在任務調度模塊中執行相應的任務調度算法。任務解析模塊解析任務特點、獲取特性，把任務調度分配到合適的服務資源上進行執行，保證QoS需求得到滿足。由于服務節點在整個SWIM中的分布異構性，分配調度模塊結合采集到的共享資源數據，按照任務解析模塊對任務的分配要求來匹配資源，把最終的資源節點信息發送到虛擬機模塊上，由其對用戶提供所需的服務。多QoS約束條件SWIM任務調度模型架構如圖1所示。

3.2 相關定義

為更好地描述QoS-ACO算法，首先進行如下一般性定義。

2) SWIM總調度任務集T= {t1,t2,t3,… ,ti,… ,tn}，包括n個調度任務，ti為系統中第i個調度任務。

3) 預期執行時間矩陣（ETC, expected time to compute），為調度任務ti在資源節點sj上的預期完成時間。

4) 搜索表Tabu記錄螞蟻任務完成信息。

3.3 多QoS約束條件參數

為實現系統任務調度的QoS目標，采用隸屬度函數思想將任務完成時間、安全性和可靠性進行目標約束化處理，具體過程如下。

1) 任務調度完成時間目標約束化處理

系統中參與任務調度的所有的調度任務完成時間為任務調度總完成時間。任務在不同節點上的執行時間會因系統的網絡異構性和資源節點的性能差異性而不同，所以任務的調度策略會直接影響系統任務的總完成時間。用資源節點上最后一個任務的完成時間來表示該節點的任務完成時間Ti，如式(1)所示。

其中，tig為資源節點i上最后一個任務的完成時間。NTG{Ti}為系統中所有的資源節點任務完成時間的集合，以該集合中的最大值表示系統調度任務的總完成時間TIM，如式(2)所示。

所以，實現TIM值的最小化就可以達到優化系統總完成時間的目的。

圖1 多QoS約束條件SWIM任務調度模型架構

2) 任務調度安全性目標約束化處理

安全性定義為

其中，n為安全參數個數；li為第i個安全數的權重；當滿足系統任務調度第i個安全參數時，seci=1，否則seci=0。

3) 任務調度可靠性目標約束化處理

任務調度的可靠性可以等效為在系統任務完成時間最小化的前提下，完成所有任務調度的成功率。系統中節點i完成全部任務過程中的任務調度成功率用指數率來表示，其表達式為

假設所有任務調度成功率互不影響，則系統全部資源節點完成所有任務的成功率為

3.4 多QoS約束條件求解

SWIM多 QoS約束條件求解分為以下幾種情況。

1) 把任務ti調度到資源節點sj上進行處理時獲得的服務質量時間參數效用等效為時間評價函數，如航空飛行計劃任務在航行情報信息資源中進行分配時獲得的 QoS時間性效用。假設Tmaxti為任務ti的最長完成時間，T(ti,sj)為任務ti調度到資源節點sj上需要的完成時間，λ為常數，則時間評價函數為

2) 把某個任務ti調度到資源節點sj上進行處理時獲得的服務質量安全性參數效用等效為安全性評價函數，如航空飛行計劃任務在航行情報信息資源中進行分配時獲得的 QoS安全性效用。假設為任務ti應具有安全等級的最小值，為資源節點sj具有的安全等級，Smax是系統資源節點具有的最高安全等級，則安全性評價函數為

3) 把任務ti調度到資源節點sj上進行處理時獲得的服務質量可靠性參數效用等效為可靠性評價函數，如航空飛行計劃任務在航行情報信息資源中進行分配時獲得的QoS可靠性效用。本文用調度任務完成的成功率來表征其可靠性，假設Rminti為任務ti完成成功率的最小概論值，為把任務ti調度到資源節點sj上進行處理所獲得的可靠性，則可靠性評價函數為

假設系統資源節點sj的固有非成功率為Fsj，任務ti在資源節點sj上進行處理所需要的完成時間為T(ti,sj)，則

用戶滿意度評價標準的計算式為

其中，E(ti,sj)為調度任務ti的服務質量總體效用評價函數，作為用戶滿意度的評價標準，用此函數值對蟻群優化算法中的信息素進行更新；時間、安全性和可靠性評價函數對應的權值分別用常數?1、?2和?3來表示，且?1+?2+?3= 1。

對總體效用評價函數E(ti,sj)進行線性加權處理，最終得到用戶對任務完成服務質量的總效用評價函數，其計算式為

系統資源調度的目標就是確保總效用評價函數E值最大，以提高任務完成的服務質量，也用此函數來評價任務調度算法的性能。

4 基于多 QoS約束條件的蟻群優化任務調度算法

本文根據 SWIM 核心服務的特點對蟻群算法進行改進，使用SWIM中業務調度QoS總效用評價函數來更新蟻群算法中的信息素，提出了面向SWIM的多QoS約束條件蟻群優化任務調度算法QoS-ACO，在保障完成SWIM業務調度的同時，能夠最大化用戶滿意度，提高SWIM核心服務的質量。

4.1 QoS-ACO算法優化規則

Dorigo等[14]通過觀察自然界中的螞蟻覓食行為產生了任務調度靈感，并于 1991年首次提出了蟻群算法，模擬螞蟻覓食行為來達到全局尋優目的。假設t時刻螞蟻k從資源節點i轉移到資源節點j的概率值為利用該值來選擇要調度的下一個任務。的計算式為

通過式(12)可知，影響資源節點選擇的 2個關鍵因子是τij(t)和ηij(t)，對這2個因子的改進是算法優化研究的重點。本文提出的面向SWIM任務調度的多QoS約束條件蟻群優化任務調度算法，就是在傳統蟻群算法基礎上對τij(t)做出相應改進，使用SWIM中業務調度QoS總效用評價函數E來更新蟻群算法中的信息素。

蟻群算法中更新信息素τij的計算式為

本文使用SWIM中業務調度QoS總效用評價函數E來更新信息素ijτ，其計算式為

為保障完成所有任務的時間最小，利用預期完成時間獲得啟發函數。從式(16)可知，預期完成時間的值與ηij(t)成反比關系。成正比關系，因此通過降低預期完成時間可以提高轉移概率[15]。

把改進后的信息素濃度函數式(13)和啟發函數式(16)代入任務轉移概率式(12)中，得到優化蟻群算法 QoS-ACO后的任務ti被調度到資源節點sj的概率值本文提出的QoS-ACO算法計算復雜度為O( NCmaxn3)，其中， N Cmax為循環次數，n為任務總數。本節涉及的函數及參數描述如表1所示。

4.2 QoS-ACO算法優化流程

QoS-ACO算法主要利用蟻群算法優化任務調度安排，依據任務在資源節點上的總效用值來選擇節點處理調度任務。本文設計的QoS-ACO算法需要在完成調度任務的同時最大化用戶的滿意度，盡量獲得比較高的總體評價。因此使用QoS總效用評價函數來更新蟻群算法中信息素，并且期望完成所有任務的時間最小，使用預期完成時間來計算蟻群算法的啟發函數。最終依據任務轉移概率的值，選擇一個信息素濃度函數值高的資源節點來處理分配的任務。

SWIM 任務調度的關鍵是保證總體效用評價函數E(ti,sj)值最大，并將所有調度任務合理分配到相應的資源節點上進行處理。假設給定一個由n個任務組成的SWIM任務調度，其算法流程如圖2所示，具體步驟如下。

1) 參數初始化。任務數量為n，資源數量為m，螞蟻數量為q，最大的循環次數為tmax，初始時間t設置為0，在SWIM中假設有n個航空飛行計劃任務，m個航行情報信息資源。

2) 初始化搜索表Tabu。

3) 利用Pijk(t)的值來確定接下來的調度任務，并選擇具有最大效用的資源節點進行任務處理。

4) 把新的調度任務添加到搜索表中進行更新。

5) 根據式(13)，使用總效用評價函數E來進行蟻群算法的信息素更新，并把篩選出具有最佳調度結果的螞蟻信息進行保存。

6) 重復以上步驟直至t＞tmax，算法結束[16]。

5 仿真實驗及結果分析

為驗證本文所提出算法的可行性和性能，在參考了民航某空中交通管理局已經部署的廣域信息管理系統結構基礎上，利用網絡仿真軟件NS-2搭建仿真實驗環境。SWIM局部任務調度結構如圖3所示。

5.1 實驗環境及參數設置

在 NS-2網絡仿真平臺搭建的實驗環境主要由調度器模塊、服務器模塊、客戶端模塊和路由器模塊構成。調度器模塊扮演調度者的角色，路由器模塊負責路由轉發，客戶端模塊和調度器模塊通過路由器模塊完成交互，調度器的功能是發現客戶可以訪問的資源，把任務映射到資源上后執行任務，最后收集結果。服務器模塊為具有不同處理能力的服務節點，接收調度器模塊分配的任務并執行，同時定期向調度器模塊匯報自己的運行狀態。網絡測試拓撲如圖4所示。

圖4 仿真實驗網絡拓撲結構

仿真實驗設計了具有一個調度器模塊、2個路由器模塊、10個服務器模塊和4個客戶端模塊的拓撲結構模型。在模型中，節點1為系統調度器；節點2和節點3為路由器；節點4～節點7為客戶端；節點8～節點17為服務器。

本實驗選取了任務完成時間、安全性和可靠性作為三維QoS約束，在NS-2環境的仿真平臺上對改進的蟻群優化算法進行仿真實驗，并進行如下參數設置。

1) 任務完成時間。在任務調度過程中，任務的完成時間一定要小于用戶定義的最大時間，任務的執行期限計算式為

其中，iγ為1～6的隨機值，eti是任務ti的平均完成時間，kti是任務的到達時間。任務完成時間評價函數如式(6)所示。

2) 安全性。安全性級別設置為{poor, low, medium, high}4個等級，安全性評價函數如式(7)所示。

3) 可靠性。每個服務節點可以成功完成任務的概率。可靠性評價函數如式(8)所示。

4) QoS總效用評價函數的權值參數設置為：1?=0.4，2?=0.3，3?=0.3。

5) 參考文獻[17]中的ACO算法設置：α=1.0，β=2.0，μ=0.5。

6) 設置節點之間的鏈路帶寬為200 Mbit/s，單向時延為20 ms。

7) 通過NS-2編譯器創建調度服務器、調度路由器、用戶和資源節點服務器對象。

8) 運用NS-2的解釋器連接調度服務器，將調度路由器加載到其相鄰節點。

仿真實驗測試參數如表2所示。

表2 仿真實驗測試參數

5.2 實驗結果及分析

仿真實驗通過任務完成時間、安全性、可靠性和 QoS總效用值 4個評價指標對本文提出的QoS-ACO算法進行綜合評價，并在相同條件下將QoS-ACO算法與經典的Min-Min算法[4]、啟發式粒子群優化（PSO, particle swarm optimization）算法[18]進行比較分析，驗證QoS-ACO算法的有效性。采用在 SWIM 資源節點數目m和任務數n不同情況下進行2種實驗。

1) 資源節點數量m固定，任務數量n變化。在構建的SWIM仿真系統中，資源節點個數m=10，任務數量為n，1≤n≤400，比較3種算法在任務完成時間、安全性和可靠性值方面的性能，并通過總效用值來驗證QoS-ACO算法的優越性。

2) 任務數量n固定，資源節點數量m變化。在構建的SWIM仿真系統中，任務數量n=200，資源節點個數為m，1≤m≤40，比較3種算法在任務完成時間、安全性和可靠性值方面的性能，并通過總效用值來驗證QoS-ACO算法的優越性。

為使驗證結果更加準確，每種實驗進行 1 000次，取實驗結果的平均值，并利用Matlab進行處理對比分析。

5.2.1 任務完成時間

任務完成時間可以反映出算法的高效性。在NS-2上運行QoS-ACO算法、PSO算法和Min-Min算法，經過路由選擇操作后確定最終路徑完成任務調度。通過Wireshark統計分析工具對得到的trace文件進行統計和分析，并利用Matlab對結果進行處理，得到3種算法的任務完成時間，如圖5和圖6所示。

圖5 任務完成時間隨任務數變化

圖6 任務完成時間隨資源節點數變化

從圖 5可以看出，在蟻群尋徑的初期，QoS-ACO算法、PSO算法和Min-Min算法在任務數量不多的情況下，任務完成時間相差不大。但隨著任務數量的增多，QoS-ACO算法的任務完成時間明顯小于PSO算法和Min-Min算法。從圖6可以看出，在資源節點數量增加的情況下，QoS-ACO算法的執行調度任務時間始終小于PSO算法和Min-Min算法。這是由于在QoS-ACO算法中采用了預期完成時間來計算啟發函數，調度路徑空間得到擴展并分布均勻。雖然擴展路徑空間在初期會帶來總時延問題，但在之后的路徑尋找過程中，螞蟻會傾向于信息素濃度高并且完成時間最小的路徑。由此可以得出結論，QoS-ACO算法可以提高任務的執行效率，使螞蟻具有更強的任務調度能力。

5.2.2 安全性

安全性是任務調度的前提和保障。通過在NS-2上運行測量QoS-ACO算法、PSO算法和Min-Min算法的任務安全性數據得到 trace文件，通過Wireshark統計分析工具對得到的trace文件進行統計和分析，并利用Matlab對結果進行處理，結果如圖7和圖8所示。

圖7 任務安全性隨任務數變化

圖8 任務安全性隨資源節點數變化

從圖7和圖8可以看出，隨著任務數量和資源節點數量的增加，QoS-ACO算法的任務安全性值始終高于 PSO算法和 Min-Min算法。這是因為QoS-ACO算法中的蟻群信息素更新是通過QoS總效用評價函數，而安全性評價函數為總效用評價函數的一部分，為保證總效用評價函數最大，就需要在任務調度過程中對其安全性進行考慮。由此可以得出結論，QoS-ACO算法可以保障蟻群在任務調度過程中資源的安全性。

5.2.3 可靠性

可靠性反映整個系統完成所有任務調度的成功性。在NS-2上運行得到QoS-ACO算法、PSO算法和Min-Min算法任務可靠性數據的trace文件。運用Wireshark統計分析工具對得到的trace文件進行統計和分析，并利用 Matlab工具對結果進行處理，結果如圖9和圖10所示。

圖9 任務可靠性隨任務數變化

圖10 任務可靠性隨資源節點數變化

從圖9和圖10可以看出，隨著任務數量和資源節點數量的增加，QoS-ACO算法的任務可靠性值始終高于PSO算法和Min-Min算法。這是因為QoS-ACO算法中的蟻群信息素更新是用QoS總效用評價函數，而可靠性評價函數為總效用評價函數的一部分，為保證總效用評價函數最大，就需要在任務調度過程中對其可靠性進行考慮。由此可以得出結論，QoS-ACO算法可以提高任務調度完成的成功率，提升系統的任務調度性能。

5.2.4 總效用值

為提高用戶對任務處理的滿意度，需要保證服務質量總效用評價值最大，本文通過式(11)對任務調度算法的QoS總效用進行評價。在NS-2仿真平臺中進行對比實驗，并把每個任務依次提交至仿真系統中進行調度處理，實驗結果如圖 11和圖 12所示。

圖11 不同任務數下總效用值

圖12 不同資源節點數下總效用值

從圖11和圖12可以看出，在任務數量增加和資源節點數量增加這 2種情況下，QoS-ACO算法所獲得的總效用值都明顯優于PSO算法和Min-Min算法。這主要是因為QoS-ACO算法考慮了用戶對任務完成時間、安全性和可靠性3個服務質量方面的要求，并從這3個方面建立各自的約束條件，根據式(10)得到任務調度的QoS總效用評價函數，并使用該值對QoS-ACO算法中的蟻群信息素進行全局更新。由此可以得出結論，QoS-ACO算法在保障系統調度任務完成的前提下，可以提高系統對用戶的服務質量。

5.3 比較分析

目前，在SWIM任務調度方面的研究及成果不是很多，針對SWIM任務調度算法的研究也很少。而在其他大型網絡系統應用領域關于任務調度算法的研究已經取得了一定的成果，例如Min-Min算法[4]和啟發式任務調度PSO算法[18]等。因此，將本文提出的 QoS-ACO算法與上述算法進行性能比較，結果如表3所示。

表3 部分任務調度算法任務調度性能比較

表3中性能比較結果數據中3組數值分別表示各自檢測項目的最優值、平均值及兩者差的絕對值，一般用最優值和平均值之差的絕對值來總體衡量檢測項目的性能，其值越小則性能越好。從表3可以看出，本文提出的QoS-ACO算法在完成時間、安全性和可靠性方面的性能指標都優于 Min-Min算法和啟發式任務調度PSO算法，且算法總效用值最高。

6 結束語

服務質量是衡量 SWIM 任務調度策略好壞的重要指標，本文以多QoS約束條件為立足點，實現SWIM任務最優調度目標；提出的基于多QoS約束條件 SWIM 任務調度蟻群優化算法，綜合考慮了SWIM中用戶的QoS需求；通過對蟻群算法的改進，使用SWIM中業務調度QoS總效用評價函數來更新蟻群算法中的信息素，保證在有效完成調度任務的同時，最大化滿足用戶的QoS需求。仿真實驗表明，在多約束條件QoS任務調度模型中，QoS-ACO算法在任務完成時間、安全性、可靠性和總效用值方面比PSO算法和Min-Min算法有一定的優勢，可以獲得較好的任務調度結果，能夠解決SWIM資源共享問題，滿足用戶對服務質量需求，提高了航空運營質量和效率。但QoS-ACO算法在以下方面需要進一步研究和完善。

1) 由于蟻群算法普遍存在過早收斂的現象，尤其是當任務數達到一定數量時，總效用值會過早收斂。因此本文提出的QoS-ACO算法也存在不足，在后續的算法改進中，會借鑒其他啟發式算法優點，如模擬退火算法和遺傳算法等。根據這些算法的不同特點進行綜合應用，優劣互補，提高算法整體任務調度性能。

2) 本文提出的QoS-ACO算法，只考慮了服務質量中的任務完成時間、安全性、可靠性和總效用值這幾個方面，還需要更全面地考慮SWIM中的其他QoS需求，以及系統負載均衡等因素，不斷地改進和完善任務調度策略。

3) 蟻群算法中參數設置很重要，如果設置不當會導致求解速度變慢，影響結果質量。在下一步的SWIM任務調度研究工作中，還將考慮任務的動態性，動態調整算法中的相應參數。

4) 本文提出的 QoS-ACO算法只是在模擬的SWIM環境下，利用網絡仿真工具進行仿真實驗，而沒有在實際SWIM應用環境下測試。后續工作應在真實的SWIM環境下進行實驗測試，進一步驗證所提QoS-ACO算法的有效性。