云計算中基于服務能力與信任約束的任務調度算法

鄭 鑫，武小年，孟 川，李 豪

（1.桂林電子科技大學廣西無線寬帶通信與信號處理重點實驗室，廣西桂林 541004；2.桂林電子科技大學信息與通信學院，廣西桂林 541004）

云計算中基于服務能力與信任約束的任務調度算法

鄭 鑫1，2，武小年1，2，孟 川2，李 豪2

（1.桂林電子科技大學廣西無線寬帶通信與信號處理重點實驗室，廣西桂林 541004；2.桂林電子科技大學信息與通信學院，廣西桂林 541004）

針對云計算的可信服務選擇與多個約束目標問題，提出一種基于服務能力與信任約束的任務調度算法。該算法首先對資源進行服務能力和信任評估，然后在任務調度過程中根據用戶任務對資源的服務能力需求，篩選滿足條件的候選資源集，并構造一個以信任效益和服務費用權衡的綜合效益函數，從候選資源集為任務篩選滿足條件的資源子集，最后采用負載均衡策略進行調度。仿真結果表明，該算法能夠為用戶任務選擇滿足服務能力與信任需求的資源，具有較好的系統性能和負載均衡性。

云計算；任務調度；信任約束；綜合效益

云計算的外包服務模式引起的云平臺安全風險是云計算發展的障礙。如何構建安全可信的云服務是云計算亟需解決的問題［1］。云服務中資源與任務的分配與調度，由云計算任務調度機制完成。在云計算的任務調度中，服務提供商根據云用戶的請求，選擇滿足其需求的可信資源［2］。

云計算作為一種商業服務模式，其采用信任機制實現服務的可信評估和決策支持。文獻［3］面向信任服務提出一種云計算工作流任務調度算法，用直接信任和推薦信任度量信任關系，并以均衡策略將用戶不同的調度目標進行均衡。文獻［4］設計了一種基于安全意識與預算意識的調度策略，采用信任安全因子計算任務的優先級，并將預算費用作為約束目標進行任務與資源的映射。文獻［5］基于粒子群算法，在云工作流中修改粒子群的適應度函數，將信任服務與存儲服務作為資源選擇的約束條件，實現資源與任務的映射。文獻［6］以人際關系信任模型為基礎，提出了包含用戶對服務資源的信任需求和服務資源的可信度信任度量模型，滿足任務在信任方面的需求，提高調度成功率。Fan等［7］提出了一種基于模糊差距度量和證據推理方法的二階段評價模型來度量云服務的可信度，用戶獲得了高可信度的服務。通常用戶任務的約束目標需求并不是單一的，針對云計算的可信服務選擇與任務的多個約束目標需求問題，提出一種基于服務能力與信任約束的任務調度（TSTC）算法。

1 基于服務能力與信任約束的任務調度

資源的服務能力是云平臺商業化運作的基礎，而具有強大服務能力的可信資源能夠進一步提高用戶的滿意度。

針對云計算任務調度中的任務請求與資源分配問題，引入資源服務能力與信任評估策略對資源進行評估，從資源的服務能力和可信度篩選出滿足云用戶需求的資源集。最后從系統全局出發，進行負載均衡調整，將合適的資源提供給云用戶。任務調度結構如圖1所示。

圖1 任務調度結構Fig.1 The structure of task scheduling

1.1 資源服務能力評估

資源服務能力的評估從資源的性能屬性考慮，主要包括資源的通信帶寬Wr，存儲能力Sr以及計算能力Cr。由于Wr、Sr、Cr單位不同且數值相差較大，采用min-max標準化方式對數據進行歸一化處理，將不同類型的數據映射到區間［0，1］，使數據快速收斂。

其中：x為樣本數據；xmax為樣本數據的最大值；xmin為樣本數據的最小值；x～為x的歸一化值。

基于歸一化處理，采用線性加權的方式計算資源的服務能力，以Qj表示資源rj的服務能力，則

1.2 資源信任評估

在云計算任務調度中，資源信任缺失引發的惡意行為將降低服務質量或導致任務調度失敗［8］。因此，采用信任機制，從資源的安全性和可靠性評估云計算的資源信任［9］。

資源的安全性通過對任務的真實性、保密性和完整性進行評估，以srj表示資源rj的安全性，則

其中：Arj、Prj、Irj∈［0，1］分別為對資源rj進行歸一化后的真實性、保密性和安全性結果；權重因子ω1、ω2、ω3∈［0，1］，且ω1＋ω2＋ω3＝1。

資源通常存在失效率，隨著時間的推移，資源可靠性降低。因此，根據資源的失效率和系統的運行時間評估資源的可靠性。資源rj的可靠性

其中：frj為資源的失效率；ti為任務Ti執行前系統的運行時間［10］。

1.3 資源篩選

基于資源的服務能力和信任評估，在任務調度中，針對用戶任務對資源服務能力、信任與服務費用需求，為用戶任務篩選滿足用戶需求的資源集并選擇合適的資源進行分配。

將用戶任務對資源的服務能力需求量化處理，用戶任務Ti的服務能力需求qi，

其次，將信任效益和服務費用需求進行權衡量化，用戶對服務質量的綜合滿意度可以更好地篩選出滿足用戶綜合需求的資源。

以U（i，j）表示任務Ti對資源rj的信任和服務費用需求的綜合滿意度，則

其中：權重因子λ1、λ2∈［0，1］，且λ1＋λ2＝1；Cij為任務Ti在資源rj上的服務費用；為任務的平均預計服務費用［11］。服務費用越小，信任效益值越大，篩選出的資源更符合用戶需求。

采用任務Ti對資源rj的安全性隸屬函數Us（i，j）和可靠性隸屬度函數Uk（i，j）加權，可得信任效益：

2 仿真測試及結果分析

實驗采用云仿真器CloudSim 2.1.1［12］對TSTC算法進行仿真。計算機環境為Intel（R）Core i5-4200M2.50GHz，內存8GB，操作系統為Windows 7。在仿真中，實現TSTC算法并將其添加到DatacenterBroker類中進行任務調度，重置Cloudlet類與VM類，設置任務與虛擬機資源的參數。

1）資源參數：設置50個資源，每個資源包含一個處理器，計算能力Cr、通信帶寬Wr和存儲能力Sr的分布區間分別為［300，500］、［800，1000］和［2000，2500］。

2）資源失效率分布區間為［0.000 1，0.001 5］。

3）資源服務能力量化權值a＝b＝0.3，c＝0.4。資源安全性評估權值ω1＝ω2＝0.3，ω3＝0.4。信任效益均衡權值θ1＝θ2＝0.5。綜合效益均衡權值λ1＝λ2＝0.5。

在相同的仿真測試環境下，分別實現Min-min算法、信任驅動的Min-min（TD Min-min）算法［13］、服務質量感知的QTS算法［14］、TSTC算法，并對比了算法在總信任效益、時間跨度、用戶平均滿意度和負載均衡情況。實驗中任務數分別設置為200、500、1000、2000。

2.1 總信任效益測試

總信任效益是被調度的任務獲得的信任效益之和。總信任效益越大，說明本次調度提供的資源安全性越高。4種算法的總信任效益如圖2所示。

圖2 4種算法總信任效益Fig.2 Total trust benefit value of four algorithms

從圖2可看出，TSTC算法總信任效益優于Min-min算法與QTS算法，略低于TD Min-min算法。這是由于TSTC算法除了考慮任務的信任需求外，還考慮了服務費用，而TD Min-min算法僅追求信任效益，每次調度都選擇信任效益最大的資源進行匹配。

2.2 時間跨度測試

時間跨度是評價算法性能的重要指標，是待調度任務集中所有任務執行完畢所花費的時間。時間跨度值越小，表示任務完成越快，系統的調度性能越好。4種算法的時間跨度如圖3所示。

從圖3可看出，TSTC算法在任務數量較小時，時間跨度最小。隨著任務數量的增加，時間跨度略高于QTS算法。隨著任務數量的增加，服務能力需求低的任務數量相應增加，TSTC算法為了負載均衡，這些任務被安排到負載小但性能非最優的資源上。而TD Min-min算法僅追求高信任效益而忽略完成時間，因此時間跨度最大。

圖3 4種算法的時間跨度Fig.3 Makespan of four algorithms

2.3 用戶平均滿意度測試

用戶滿意度是用戶對任務被執行結果的滿意程度。根據任務的服務能力、信任和費用需求被滿足時進行滿意度度量。用戶任務Ti在資源rj上執行的滿意度

用戶平均滿意度

其中n為任務集合中任務的個數。4種算法用戶平均滿意度如圖4所示。

圖4 4種算法用戶平均滿意度Fig.4 Average users satisfaction of four algorithms

從圖4可看出，TSTC算法在調度中綜合考慮用戶的服務能力、服務可信度和服務費用需求，其用戶滿意度與致力于服務質量感知的QTS算法近似。TD Min-min算法與Min-min算法僅追求單一目標的優化，用戶平均滿意度較低。

2.4 負載均衡測試

負載均衡用資源負載的相對標準差（RSD）來表示，其能較好地表達一組數據的離散程度，反映了資源的負載均衡情況。RSD越小，資源負載越均衡。4種算法的負載均衡如圖5所示。

圖5 4種算法的負載均衡Fig.5 Load balance of four algorithms

從圖5可看出，TSTC算法的負載均衡性最優。因為在調度過程中，TSTC算法把對資源服務能力需求低的任務映射到滿足條件且負載最小的資源上，進行了負載均衡調整，提高了資源利用率與系統性能。

3 結束語

針對云服務信任缺失與用戶任務約束目標需求問題，提出一種基于服務能力與信任約束的任務調度算法。該算法通過資源服務能力評估與信任評估，為用戶的服務質量需求提供選擇依據。在資源篩選中，將信任效益與服務費用加權作為綜合目標，均衡了用戶多方面約束目標需求。算法將低服務能力需求的任務調度到負載小的資源上，獲得了良好的負載均衡性。仿真結果表明，TSTC算法能夠滿足用戶對資源服務的性能、可信度和服務費用的需求，提高了用戶滿意度，具有較好的負載均衡性。

［1］ 丁滟，王懷民，史佩昌，等.可信云服務［J］.計算機學報.2015，38（1）：133-149.

［2］ LIN Weiwei，LIANG Chen，WANG J Z，et al.Band-width-aware divisible task scheduling for cloud computing［J］.Software：Practice and Experience，2014，44（2）：163-174.

［3］ TAN Wenan，SUN Yong，LI L X，et al.A trust serviceoriented scheduling model for workflow applications in cloud computing［J］.IEEE Systems Journal，2014，8（3）：868-878.

［4］ ZENG Lingfang，VEERAVALLI B，LI Xiaorong.SABA：a security-aware and budget-aware workflow scheduling strategy in clouds［J］.Journal of Parallel and Distributed Computing，2015，75：141-151.

［5］ YANG Yuli，PENG Xinguang，CAO Jianfang.Trustbased scheduling strategy for cloud workflow applications［J］.Informatica，2015，26（1），159-180.

［6］ 曹潔，曾國蓀，姜火文，等.云環境下服務信任感知的可信動態級調度方法［J］.通信學報，2014，35（11）：39-49.

［7］ FAN Wenjuan，YANG Shanlin，PEI Jun.A novel twostage model for cloud service trustworthiness evaluation［J］.Expert Systems，2014，31（2）：136-153.

［8］ LI Wenjuan，WU Jiyi，ZHANG Qifei，et al.Trust-driven and qos demand clustering analysis based cloud workflow scheduling strategies［J］.Cluster Computing：the Journal of Networks Software Tools and Applications，2014，17（3）：1013-1030.

［9］ WANG Wei，ZENG Guosun，TANG Daizhong，et al.Cloud-DLS：dynamic trusted scheduling for cloud computing［J］.Expert Systems with Applications，2012，39（3）：2321-2329.

［10］ POOLA D，GARG S K，BUYYA R，et al.Robust scheduling of scientific workflows with deadline and budget constraints in clouds［C］／／28th International Conference on Advance Information Networking and Applications，2014：858-865.

［11］ SU Sen，LI Ji，HUANG Qi，et al.Cost-efficient task scheduling for executing large programs in the cloud［J］.Parallel Computing，2013，39（4／5）：177-188.

［12］ CALHEIROS R N，RANJAN R，BELOGLAZOV A，et al.CloudSim：a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms［J］.Software Practice ＆Experience，2011，41（1）：23-50.

［13］ AZZEDIN F，MAHESWARAN M.Integrating trust into grid resource management systems［C］／／Proceedings of the International Conference on Parallel Processing，2002：1-8.

［14］ 周發超，王志堅，葉楓.一種新型的云任務調度算法研究［J］.中國科學技術大學學報，2014，44（7）：590-598.

編輯：曹壽平

A task scheduling algorithm based on service ability and trust constraint in cloud computing

ZHENG Xin1，2，WU Xiaonian1，2，MENG Chuan2，LI Hao2
（1.Key Laboratory of Guangxi Wireless Broadband Communication and Signal Processing，Guilin University of Electronic Technology，Guilin 541004，China；2.School of Information and Communication Engineering，Guilin University of Electronic Technology，Guilin 541004，China）

In view of selecting trusted service and multiple constraint objects in cloud computing，a task scheduling algorithm based on service ability and trust constraint is proposed.Firstly the service ability and creditability of resources are assessed.And then during the process of task scheduling，the candidate resources are selected if their service ability meets the requirements of users.Furthermore a comprehensive benefit function is designed by the weight of the trust benefit and cost，resource with the biggest comprehensive benefit is selected from the candidate resources.Finally the task is assigned to a resource according to load balancing strategy.Simulation results show that the algorithm can satisfy service ability and the trust requirements of users.And the performance and load balance of the system is good.

cloud computing；task scheduling；trust constraint；comprehensive benefit

TP393

：A

：1673-808X（2016）05-0382-05

2016-03-12

國家自然科學基金（61572148）；廣西自然科學基金（2015GXNSFGA139007）；廣西無線寬帶通信與信號處理重點實驗室基金（GXKL061510，GXKL0614110）；桂林電子科技大學研究生教育創新計劃（YJCXS201524）

武小年（1972-），男，湖北監利人，副教授，碩士，研究方向為分布式計算、信息安全。E-mail：xnwu＠guet.edu.cn

鄭鑫，武小年，孟川，等.云計算中基于服務能力與信任約束的任務調度算法［J］.桂林電子科技大學學報，2016，36（5）：382-386.