基于信任的云服務系統多目標任務分配模型

束 柬 梁昌勇 徐 健

(合肥工業大學管理學院 合肥 230009) (優化與智能決策教育部重點實驗室(合肥工業大學) 合肥 230009) (shujian7@163.com)

在全球經濟一體化進程迅速發展的背景下，企業面臨著外部資源和環境壓力持續加大，內部也面臨著產品和服務創新乏力、資源消耗大等難題.云計算等新興信息技術和面向服務的體系框架為企業提高生產經營效率，從更大范圍內整合資源和協同價值創新，建立更加高效低碳的運營體系和服務模式等提供了契機.然而，新的云服務模式在重新整合產業鏈和協同價值鏈的過程中也帶來了新的安全隱患，虛擬化的遠程服務模式和多主體的協同服務特征等不斷拓寬以往傳統的信息安全邊界，帶來了更多的安全風險.傳統信息安全技術無法很好地解決該問題，基于信任的系統管理方法為其提供了全新的思路

云計算為企業提供的服務主要有3種模式：軟件及服務(software as a service, SaaS)、平臺即服務(platform as a service, PaaS)以及基礎設置即服務(infrastructure as a service, IaaS)[1].此外，集合企業自身系統架構，云服務也分為由企業內部信息資源虛擬化而成的私有云服務、外部云服務商提供的公有云服務，及兩者皆有的混合云服務[2].針對云服務模式已有較為廣泛的研究：Dorsch等人[3]從盈余能力的經濟影響角度討論了云服務能力，以云服務彈性的容量供應策略應對不穩定需求.Boru等人[4]以建立了一種數據復制方法解決云服務數據中心存儲海量數據的節能問題.羅軍舟等人[5]將云服務劃分為核心服務、服務管理、用戶訪問接口3層體系架構，總結了云服務的關鍵技術和熱點問題.李喬等人[6]從云服務類型和框架層次的角度綜述了不同的云計算服務.

基于云的管理系統的服務對象是包含企業生產經營等一系列活動的業務流程.業務流程對于企業而言如同經脈對于人體，是形成信息流動和資源交換的重要載體.單個業務流程可被劃分為很多個彼此存在限制關系的任務單元[7]，如何分配和調度該類任務單元以保障整個業務流程的順利完成是并行系統的熱點問題[8-9].Liu等人[10]引入流矩陣以表示待分配任務節點間約束的關系的權重.Topcuouglu等人[11]建立異構計算環境下動態高效低復雜性的任務調度算法.Wen等人[12]采用GA算法結合鄰域搜索，建立了異構多進程系統中的啟發式的任務調度算法.而現有研究對任務結構的總結多限于并行或串行結構，缺乏多樣性，本文引入6種典型任務結構到任務分配模型中，以增強模型真實性和可用性.

云計算服務在帶來高效便捷的同時，其跨組織的分布式服務模式也必將帶來新的安全問題[13].考慮不同任務對服務資源具有不同的信任安全需求，如涉及商業機密數據的任務有更高的安全需求，而服務資源根據其服務聲譽和服務模式的差異也具備不同的可信度.在信息系統領域中，對信任機制的相關理論和關鍵技術的研究日趨成熟[14-15].Krautheim等人[16]在云環境中構建了基于加密算法和可配置模塊化架構的可信虛擬環境模塊(TVEM).Manuel[17]將信任引入服務質量(QoS)參數中，以可用性、可靠性、周轉效率和數據完整性4個參數來計算服務的信任值.李勇軍等人[18]討論了信任機制與網絡安全的相關性，在信任機制的研究框架下總結了典型信任模型.徐鋒等人[19]給出了考慮憑證的存儲及授權形的信任鏈發現算法，防止有效敏感信息的泄露.可以看出，信任機制為解決云計算的分布式和遠程服務等技術特征帶來的新安全問題，提供了很好的理論依據和技術方法[20].故本文在定義了云環境中信任關系的基礎上，結合前期研究成果[21]，將信任機制引入模型中，在時間和成本目標的基礎上添加信任約束和信任目標，在保障云服務系統拓展性的同時兼顧安全可信性.

本文的主要貢獻有4個方面：

1) 結合面向服務框架(SOA)，構建了混合云環境下業務流程驅動的云服務系統體系架構，并引入信任機制以量化云服務中資源的可信程度和待執行任務的信任需求；

2) 在該架構基礎上建立了業務流程驅動的多目標任務分配模型，引入運行時間、成本和信任3個目標，在保障系統高效率低成本的同時兼顧安全可信性；

3) 從業務流程層面構建了任務結構函數范式，梳理和總結了6種典型任務結構的多目標函數關系式；

4) 提出了基于局部搜索策略的改進SPGA2(strength Pareto genetic algorithm 2)算法，在結合SPEA2和GA算法的基礎上，引入基于雙點小步距躍進的局部搜索策略以提高搜索效率，通過仿真實驗驗證了算法的有效性.

1 系統架構與優化模型

1.1 基于混合云的可信服務系統體系架構

本文在企業原有系統基礎上，結合企業內部原有可信服務資源和外部云服務商提供的云服務資源，對企業服務系統進行再造升級，構建了基于混合云的綜合服務信息系統，其系統框架如圖1所示.該框架從企業服務需求端和提供端2個方面出發，將綜合服務系統剖析為4個邏輯層：任務層、調度層、虛擬服務層和平臺及基礎設施層，并對綜合服務系統中的關鍵技術和基礎要素進行詳細分析和總結.

任務是從企業析出的業務流程分解而產生的一系列可通過服務滿足其需求的子單元.從需求角度來看，企業用戶將其所需服務的流程提交到系統中，通過流程控制器首先將接收到的流程及其基本信息進行提交注冊，然后將各流程分解為獨立的可執行任務單元，例如，一項電子商務流程可分解為以下任務單元：訂單采集、驗證、核實、購物車管理和支付單元等.隨后控制器將這些可執行的任務單元提交到任務管理器中，通過任務管理器實現對所有任務單元的統一管理.任務管理器的重要功能為對任務單元屬性特征的解析和記錄，任務單元的主要屬性包括：任務量、執行優先級和信任需求等.任務量是指任務運行完成所需要的服務資源的大小；任務優先級是為了保障業務流程內部秩序和避免死循環而設立的任務間先后執行關系；信任度需求是不同任務對服務資源可信度的需求情況表征.從服務資源的提供角度來看，企業將其內部IT資源整合私有云服務資源，并接入外部公有云服務資源.公有云資源分為2類：1)租用IaaS基礎設施服務，在其上部署自己的平臺和應用服務；2)直接租用PaaS平臺服務，并在其上部署應用服務.外部的公有云服務都是通過服務收集器進行服務注冊和服務監控的，通過服務等級協議(SLA)來保障服務質量(QoS).通過資源管理中心，將公有云資源和私有云資源抽象成具有固定屬性的服務單元，并將其信息發布到調度層的資源池中，以待分配任務.且本模型假設一個資源槽在同一時間只能運行一個任務，不同服務資源槽具有其獨立的屬性.服務單元的主要屬性有服務能力、單位時間成本、資源可信度.從服務資源的屬性上來看，私有云資源擁有更高的可信度，服務能力更強，但需要更高的成本；公有云雖面臨一定信任風險，但是成本低廉，可選擇范圍更廣.

1.2 云服務中的信任機制

信任值的引入是保障整個服務系統在任務分配和服務選擇過程中兼顧節能高效和安全可靠.模型定義不同任務單元有不同的信任需求RTn，而云服務資源的可信度STm由該資源的綜合信任值所決定.云服務資源的綜合信任值是由服務用戶對資源的直接信任值和云商間的推薦信任值融合而得，其融合方法參考前期研究成果[21]所示.推薦信任值取決于云商之間交互的歷史信息，此處不再贅述.而本文重新詳細定義了用戶對云服務資源的直接信任值：直接信任值取決于云服務資源的服務模式和供應商聲譽.從云服務模式角度，用戶對系統平臺或基礎設施所擁有的控制權限越高，則該服務資源的直接信任值就越高.如用戶使用企業內部私有云部署的軟件服務資源可信度較高；而若用戶直接租用SaaS類服務資源，其對底層系統或基礎設施沒有所有權，則該類資源的可信度就較低.需要說明的是，可信度的高低只是代表概率上的潛在的風險，并不代表資源的服務能力和狀態.從云服務供應商聲譽角度，若供應商有著良好的聲譽口碑和優質的服務能力，其必然是一個高可信度的供應商；若其在聲譽上有瑕疵或者在歷史記錄中有過服務不達標的記錄，客戶就會降低其可信度.本模型將信任需求和資源可信度分為7級，如表1所示：

Table 1 The Classification of Trust表1 信任等級分類

在混合云環境下，由本地基礎設施提供的私有云服務被定義成為高可信度7；而公有云服務根據資源類型、供應商聲譽和云商間推薦信任值等將其可信度分為1～6級.本文將信任機制引入多目標優化問題中，在時間和成本目標維度外加入了信任維度.

1.3 基于時間、成本和信任的多目標任務分配模型

企業的某項業務流程BP可分解為N個任務單元{T1,T2,…,TN}，并假設共有M個服務單元{S1,S2,…,SM}接入企業的服務系統中.該多目標優化問題可以看成：企業如何分配N個任務到M個服務單元中，使得任務執行時間最短、執行成本最低、信任度最高.本節總結了單個任務的多目標函數關系式，而對整個業務流程而言，其考慮任務結構的多目標函數關系將于第2節詳細討論.

對于運行在不同的服務單元中的任務單元來說，其執行時間主要取決于任務的資源需求量和資源的服務能力scm，故任務tn在服務資源Sm上的運行時間可表示為

D(tn)=Unscm.

(1)

模型假設云服務按使用時長收費，不同云服務資源有相應的單位時間成本.考慮私有云服務前期固定設備投入、場地費用、系統維護和專業人員薪酬等，故設定私有云服務的單位成本高于公有云.任務的執行成本C(tn)取決于其運行時D(tn)和服務資源的單位時間成本costm，故可得：

C(tn)=D(tn)×costm=Unscm×costm.

(2)

RTn≥STm.

(3)

綜上所述，可信混合云服務系統中的任務分配問題可以總結為一個多目標優化問題，其目標空間包括任務運行時間、運行成本和信任值3個維度.同時，將信任限制和任務結構等引入約束條件.該多目標優化問題具體表征為

minFX[D(t1),D(t2),…,D(tx)]，

(4)

minFX[C(t1),C(t2),…,C(tx)]，

(5)

maxFX[ST(t1),ST(t2),…,ST(tx)]，

(6)

s.t. {t1,t2,…,tx}?BPa，

(7)

RTx≥STy，

(8)

FX?[Fseq,Fand,For,Fxor,Fsl,Fcl]，

(9)

其中，式(4)～(6)為目標空間，式(7)表明所有任務屬于某個流程，式(8)為信任約束，式(9)是根據任務結構確定的函數關系式.

2 業務流程驅動的多目標任務結構范式

在企業日常經營活動中，提交到系統中待執行任務不是彼此割裂的孤立單元，而是涉及不同優先級結構化的任務單元組合.而這些任務組合形成不同的業務單元，本文梳理了6種業務流程的基本組成單元，建立業務流程驅動的任務結構函數范式.選用行業標準建模語言——業務流程建模符號(BPMN)[22]建立6種典型任務結構：序列、并行-且、并行-或、并行-異或、循環-簡單、循環-組合.其中對異或和循環結構通過引入概率分布并計算期望的形式總結其目標函數關系式.不同業務單元對目標的函數范式如表2所示：

Table 2 Multi-Objectives Functions of Business Process Driven Task Structure表2 業務流程驅動的多目標任務結構函數關系式

(10)

而在組合循環結構中時間函數為

(11)

Fcl[ST(t1),ST(t2)]=
p1Fseq[ST(t1,t2)]+p2Fseq[ST(t1)]=

p1min{ST(t1),ST(t2)}+p2ST(t1).

(12)

3 改進SPGA2的多目標任務分配算法

針對混合云中業務流程驅動的多目標任務分配問題，本文提出了一個改進的SPGA2算法，其結合SPEA(strength Pareto evolutionary algorithm)算法和傳統GA算法的基礎上，引入了雙點小步距定向探尋的局部搜索策略，在保證算法全局搜索效率的同時，也提高其局部收斂性.其基本流程如圖2所示：

3.1 SPEA2算子

算法執行首先需要通過編碼過程將任務空間和資源空間的分配策略映射到抽象的解空間上去，以數字編碼形式表示不同的分配策略.隨后執行初始化流程，隨機生成一個空間大小為NP的初始種群P和一個大小為Nq的外部存檔集Q，并令Q=?.SPEA2采用更詳細的適應度分配策略，同時考慮了其中個體的支配信息和被支配信息[23].支配信息由個體的強度值獲得，被支配信息由個體的準適應度r(i)獲得，再結合密度d(i)最終生成適應度f(i)：

f(i)=r(i)+d(i)，

(13)

其中各部分的組成為

S(i)=|{j|j∈P+Q∧i?j}|，

(14)

(15)

d(i)=1

(16)

環境選擇過程是SPEA2中從群體P中生成新一代存檔集Q的重要步驟.其主要過程首先復制所有適應度低于1的非支配個體，并放入外部存檔集中：

Qt+1={i|i∈P+Q∧F(i)<1}.

(17)

當所有適應度小于1的個體都放入外部存檔集后，比較存檔集中的個體數|Qt+1|與規定的規模Nq.若|Qt+1|Nq，則執行修剪操作依次從Qt+1中剔出個體i，修剪過程如式(18)所示：

(18)

其實質為依次刪除歸檔集中與個體i距離最近的個體，直至|Qt+1|=Nq.

3.2 局部搜索策略

SPEA和GA算法都具備很強的全局搜索能力，尤其針對有連續光滑邊界的多目標優化問題具備很強的收斂能力.而當最優邊界不連續、不光滑時，割裂的最優邊界嚴重制約該類算法的收斂能力.原因在于進化算法為了防止尋優過程陷入局部收斂而擴大隨機搜索范圍的過程中，往往會忽略局部優化問題，導致算法在搜索過程中直接跳過局部的最優邊界，跳到下一個最優點.為此，本文引入局部搜索策略，對歷代存檔集中的非支配個體進行鄰域搜索，以在原有非支配集合的基礎上獲得更優秀的個體，逐步逼近最優邊界.計算過程如算法1所示.

算法1. 雙點小步距躍進的局部搜索策略.

輸入：歸檔集Q、本地搜索概率p；

輸出：新的存檔集Q′.

① 通過p搜索Q中個體并存本地集local_pop；

② foriinlocal_pop

③ forpoint1 ini

④point2←i[random(0,len(i))]；

⑤point1+=1,point2+=1；

⑥ iftrust(point1)==False

⑦point1-=1;

⑧ end if

⑨ iftrust(point2)==False

⑩point2-=1;

本文采用雙點小步距躍進的局部搜索策略，在歷代存檔集中以概率p選擇出非支配個體，采用小步距定向搜索的方式擴展搜尋其周圍空間.雙點小步距躍進是選擇個體中染色體2個點的編碼信息進行增位變動，即對1次任務分配方案中的2個任務單元所分配的資源序號進行增加1位操作，需要注意的是若單點的變化過程中破壞了信任約束則不執行增位變動.

3.3 遺傳算子

在獲得經局部優化的新存檔集后，合并新存檔集Q′和群體P，并對其進行一系列GA操作以獲得新的子代.本文選用傳統GA的選擇，交叉和變異操作實現解空間的全局尋優.采用輪盤賭選擇法選出個體進行交叉變異操作，遺傳算子的基本流程如算法2所示.

算法2. 輪盤賭選擇法和交叉變異操作主要流程.

輸入：種群population、資源集合R；

輸出：新種群new_pop.

①score←total_fitness×random(0,1)；

② foriinpopulation

③sum_fitness+=fitness(i)；

④ ifsum_fitness≥score

⑤s1←i；

⑥ end if

⑦ ifrandom(0,1)

⑧p←random(0,max(s1))；

⑨ end if

⑩ 在population中隨機找s2；

s2[p:]；

交叉操作通過算法尋優過程中生成新子代的同時保留父代的一些結構特征.采用隨機單點交叉算法，隨機生成交叉點并保留其左端基因段，交換其右側基因段以形成2個后代.變異操作是通過改變1個染色體中的某段基因來擴大算法的搜索空間以防止算法過早收斂.模型同樣選用隨機點變異方法，通過隨機函數選擇染色體上任意位置的基因片段，再隨機生成1個新的基因片段.本模型采用交叉率和突變率表示算法中執行交叉操作或變異操作的概率.需要注意的是，交叉操作是交換現有子代中的基因，而現有子代中基因所攜帶的信息都是符合信任約束的，故交叉操作不會打破任務分配中的信任信息.而變異操作是非定向的隨機搜索過程，其可能破壞原有的信任規則，產生攜帶不可信調度信息的基因片段，故本文在變異操作中增加了信任約束，不符合信任約束的突變基因將不會替代原基因，算法將重復隨機生成滿足信任約束的基因片段為止.

4 仿真實驗

為了驗證混合云環境下基于信任的動態任務分配模型和算法性能，本文編程實現了一系列仿真實驗，并對實驗數據和結果進行了詳細的梳理分析和總結.實驗平臺搭建在一臺Intel Core 2 Duo-E8400@3.00 GHz CPU和4 GB RAM的PC上，操作系統為Windows Enterprise版本，采用Python 3.5.2編程實現其相應功能，用面向對象的編程語言設置任務單元和服務資源單元，并賦予相應的特征和屬性值.本文將實驗中數據都進行規范化處理，即采取從0到其極值點轉化為0-1標準化形式，以便數據間的比較和分析.

4.1 算法的可用性和有效性

本文首先采用單目標權重分配方法對模型中3個目標函數進行獨立分析.實驗對象選取包含24個任務的復雜業務流程和8個不同屬性的服務資源.通過將各目標權重從0～1以0.1為步長進行歷遍，共產生66種不同的權重組合.相應目標權重下目標函數值的得分情況如圖3所示：

Fig. 3 Variation of single objective with weight圖3 單目標隨權重變化情況

從圖3分析可得：單個目標在獲得高目標值的情況下并不意味著會遏制其他目標值得分，如成本目標和信任目標在0.3的權重分配中就可得到接近0.9的得分.該結果揭示了該任務分配問題中多個目標間并非完全沖突，可以找到在3個目標值上都有較好得分的優秀解.故啟發式算法對該類問題有很好的處理能力，其驗證了算法的可行性.此外，當決策者不考慮全局因素，側重單目標分析信息，這些解的分布情況提供了重要參考.

在模型和算法可行性的基礎上，通過仿真實驗實現了改進的SPGA2算法，并用于到多目標任務分配的模型上.建立了一個三維立體散點圖，從全局視角展示了算法所得的最終解集，三維視圖的X軸、Y軸和Z軸分別表示時間、成本和信任3個目標維度，采用標準化取0-1為單位范圍.為了便于比較，取進化算法的種群數量也為66，故生成的66個解展示如圖4所示：

Fig. 4 Non-dominated solutions by the proposed algorithm圖4 多目標任務分配算法所得非支配解

通過圖4中點的分布，可看出其形成了一個多目標優化問題的帕列托邊界，該邊界上的所有解都是非支配的，即對一個非支配解無法找到更好的解在3個目標上都優于該解.在實際生產中，需要根據管理者的偏好和具體環境的限制約束，在所有非支配解中選出最適合的解作為任務分配問題的最優解方案.如追求低成本的公司可能更多側重成本目標，而對任務內容保密性要求較高的企業可能對成本并不敏感，更側重于信任目標.

4.2 多目標優化算法對比分析

為了更好地展現算法性能，本節選取4個經典多目標優化算法(NSGA,VEGA,MOGA和原SPEA2)作為參照，與所提出的改進SPGA2算法進行對比試驗.NSGA以帕累托解的支配關系為搜索策略，具備很強的非支配解全局搜索能力[25]；VEGA是通過分配多個向量組評估優化多個目標，其生成的解多聚攏在單目標極值點處，局部優化能力較強；MOGA通過權重將多目標聚合成單個目標，再通過遺傳算法對單目標優化，其具備較強的收斂能力，然而固定的目標權重會影響算法的全局搜索能力[26];原SPEA2是未經改進的強帕列托支配進化算法，其個體的支配信息和被支配信息由強度值體現，具備較強的解空間定向尋優搜索能力[23].本文所提出的改進SPGA2算法在結合SPEA2和GA算法的基礎上，引入局部搜索策略，以彌補面對割裂不連續的最優邊界制約算法收斂能力的情況，在保障SPEA2全局搜索能力的同時，增強對局部最優邊界的搜索效率.

Fig. 5 Performance comparison of multi-objective algorithms圖5 多目標算法性能對比

本文選取非支配解比例和算法收斂距離2個指標來衡量和對比多目標算法的性能.非支配解比例是通過多次迭代后產生的最終解集中非支配解的數量占初始解集中解數量的百分比，體現了整體尋優能力.如圖5(a)所示，改進SPGA2雖在尋優過程初期非支配解數量增長較慢，然而經過多次迭代最終生成的支配解比率最高；VEGA初期支配解比率增長對比NSGA較快，而后者最終支配解比率穩定值卻高于前者；VEGA和MOGA只考慮不同目標空間的權重問題，不關注解的支配關系，故其最終的非支配解比率較低；原SPEA2初期支配解比率增長較快，而其最終支配解比率穩定值同NSGA相似，顯著低于改進SPGA2的值.

本文將算法迭代過程中歷代最優解集的并集中非支配解的合集定義為參考集，理想的帕列托最優解集應是向該參考集無限逼近.通過計算每代種群中所有個體解到參考集的歐氏距離之和，將其記為該代種群的收斂距離，并對其標準化.如圖5(b)所示，MOGA和VEGA關注不同目標權重下的最優解，忽略解的支配關系，故搜索質量不佳，最終收斂距離較遠；原SPEA2和NSGA強調全局搜索能力，忽略部分的局部最優解，導致收斂速度較慢.而改進SPGA2算法在收斂性能上有了較大程度的提高，一方面收斂的速度更快，另一方面最終收斂距離也距最優邊界最近.收斂速度的加快是算法中引入了局部優化搜索策略的影響，大大增加了解空間的探索效率，減少無意義的迭代，使得進化過程更有針對性；最終收斂距離縮短是改進算法整體優化的結果，體現了算法在全局搜索能力和最終解集有效性上的優異表現，在減少了計算負擔的同時也提高了收斂能力.

4.3 任務結構和資源數量對分配模型的影響分析

此節討論不同任務程結構和不同服務資源數量對任務分配模型的影響，選取4種不同的業務流程，其結構分別包含8,12,20,25個任務單元；并設置服務資源數量n(S)分別為4,8,12,15，以探究不同任務結構和不同服務資源數量對該多目標分配模型的影響.

多目標任務分配問題以帕列托非支配解為主要參考基準，在所有非支配解集中通過管理者對不同目標的偏好來選擇出優秀解.而帕列托解集中除了支配關系，難以比較2個解的優劣之分.本文尋找特定解空間中的最優解點，通過比較最優解在3個目標函數中的得分情況，驗證不同任務結構和服務數量對任務分配模型的影響.特定解空間的最優解是通過設定每個目標維度的限制范圍，從符合要求的解集中找出最優解點.本文設置4種任務結構和4種服務資源數目形成16組任務分配問題，限定每個目標值需大于0.55，通過特定解空間限制{x,y,z|x>0.55,y>0.55,z>0.55}找出最優解，不同流程和服務資源中任務分配方案最優解的目標值對比情況如圖6所示：

Fig. 6 Comparison under different task and resource schemes圖6 不同任務和資源方案下最優解目標值對比情況

從圖6中可以看出，任務結構和資源數對時間目標影響較大，簡單和普通結構的流程分配到8個服務資源的場景可以獲得最高時間目標值，而對于大型復雜流程，8,12,15個不同服務資源數量對時間目標值的影響不顯著，故對待大型復雜流程增加服務資源數目所起作用不明顯.對于成本目標，本文假設云服務按使用時間收費，且服務能力跟資源的單位時間成本正相關，即越貴的服務速度越快，任務運行完成耗時越短.可看出不同任務結構復雜程度和資源數量情況下任務運行成本變化較為平穩，對成本影響較低.信任目標值中，隨著服務資源數量增加，信任目標值呈顯著增長趨勢，是因為引入更多的服務資源擴展了任務分配過程中的可信資源范圍；而不同任務規模的流程影響其信任目標值的變動并不大，顯示了任務結構復雜度變化對信任目標值變化的影響較低.

4.4 任務分配模型中的可信度分布及變化情況

Fig. 7 Trust situation in multi-objective task assignment model圖7 多目標任務分配模型中的信任情況

考慮到云服務系統中任務分配問題是基于可信服務的，故此節將模型中的信任問題單獨提取出做獨立分析.選取包含12個任務的普通業務流程和4個不同屬性的服務資源作為實驗對象.首先驗證了50次算法迭代中，每代群體中所有非支配解的信任目標平均值，并表示在圖7(a)中.圖7(a)中除了展示非支配解集的平均信任情況，還標識出任務對可信服務所要求的最低信任閾值，即流程中所有任務最低信任需求值的和.由圖7(a)可以看出，一方面由于信任約束的限制，使得算法進化過程中所有任務的信任需求都得到滿足，保證每次分配都符合信任約束；另一方面，算法迭代中整個帕列托解集的信任目標均值保持穩定增加，且最終生成解集的信任均值穩定在0.6左右，體現了任務分配方案最終解是基于高可信度的.

進化中的信任目標均值體現了算法迭代過程中整體的信任變化情況，而針對某次任務分配方案中的信任分布情況就需要選取具體的解進行分析.本文提出基于理想點的最優解確認方案，以選出合適的最優解點來分析其信任分布情況.先通過算法迭代得出最終的帕列托解集，在解集中設置理想點，并選擇與理想點歐氏距離最短的解點作為最優解.本文設置理想點為(0.6,0.6,0.6)，通過搜索帕列托解空間中與理想點歐氏距離最小的非支配解點作為最優解.以該最優解為例，對其任務分配方案的信任分布情況進行分析.如圖7(b)所示，每根柱狀圖代表該任務單元所分配的信任情況，柱狀圖下半部分為每個任務單元的信任約束值，上半部分為任務所分配的服務資源的可信度超過信任閾值部分.由圖7可見，在信任約束下所有任務單元的最小信任值需求都得到滿足，且在信任目標推動下，高可信需求的任務分配到了更可信的服務資源，大大保障了整個服務系統的可信性.

4.5 時間復雜度分析

算法的時間復雜度將直接影響其運行質量和效率，現對本文所提出的改進SPGA2算法中各算子的時間復雜度進行分析，取最大值為算法的時間復雜度.假設多目標任務分配模型是將n個任務分配到m個資源上.

1) 種群初始化.對種群P和存檔集Q進行初始化操作，其空間大小分別為常數Np和Nq.根據初始化原則，隨機生成Np×n×m個數據，并令存檔集為空集.故種群初始化復雜度為O(m×n).

2) 遺傳算子.群體交叉操作的復雜度為Np×O(m2×n)=O(m2×n)；變異操作的復雜度為Np×O(m×n)=O(m×n).故遺傳算子的復雜度為O(m2×n)+O(m×n)=O(m2×n).

3) SPEA2算子.該算子中個體的強度值表示其支配和被支配的信息，在計算個體的強度值時，需要計算個體間歐氏距離，其時間復雜度為O(m2×n2).而在環境選擇過程中，復雜度為(Nq+1)2×Nq×O(m2×n2).故SPEA2算子的復雜度為O(m2×n2)+(Nq+1)2×Nq×O(m2×n2)=O(m2×n2).

4) 局部搜索算子.對歷代存檔集中的非支配個體進行鄰域搜索，其種群最大交換次數為Np×n×m×m，故局部搜索算子的復雜度為O(m2×n).

在改進SPGA2算法中，SPEA2算子時間復雜度較高，為O(m2×n2)；遺傳算子和局部搜索算子復雜度其次，為O(m2×n)；種群初始化復雜度最低，為O(m×n).故改進SPGA2算法的時間復雜度為O(m2×n2).算法中復雜度最高為通過歐氏距離計算個體的強度值，由于強度值的計算為SPEA2算子的必要流程，故本文所引入的算子并未增加算法的時間復雜度.

5 總結與展望

云計算等新興信息技術帶來了產業鏈重新整合和商業模式創新等一系列重大變革，面對日益增長的業務需求和復雜變化的商業環境，企業如何改造并升級業務流程、合理分配和使用云服務資源、在安全可信服務的基礎上提高效率并降低成本，成為其保持旺盛生命力的重要保障.本文在面向服務的框架基礎上，結合混合云服務模式和信任機制，構建了一種基于混合云的可信云服務系統體系架構，并在該框架下建立了基于時間、成本和信任的多目標任務分配模型；引入信任值的度量以刻畫任務的信任需求和服務資源可信度，并于任務分配中結合信任機制選擇云服務資源，以保證服務的安全可靠性；在此基礎上，梳理了6種典型任務結構關于多目標的函數范式；采用基于局部搜索策略的改進SPGA2算法提高了混合云環境下多目標任務分配問題解空間的搜索效率，并最終通過仿真實驗驗證了模型和算法切實有效可行.

在未來的工作中，我們將收集并使用企業實際的業務流程數據，并結合市場上現有的典型云服務資源定價策略和服務能力，通過實際數據進一步驗證模型的有效性.現模型中引入的信任是融合直接信任值和推薦信任值的云服務綜合信任情況，今后我們擬結合不同云環境下的跨地域和跨結構的多域信任屬性特征，研究云環境下信任的跨域傳播和更新等問題，建立一種動態的綜合跨域信任網絡，以更好地刻畫服務系統中的信任關系，進一步增強系統的安全可信性.

[1]Zhan Zhihui, Liu Xiaofang, Gong Yuejiao, et al. Cloud computing resource scheduling and a survey of its evolutionary approaches[J]. ACM Computing Surveys, 2015, 47(4): 1-33

[2]Lin Chuang, Su Wenbo, Meng Kun, et al. Cloud computing security: Architecture, mechanism and modeling[J]. Chinese Journal of Computers, 2013, 36(9): 1765-1784 (in Chinese)(林闖, 蘇文博, 孟坤, 等. 云計算安全: 架構、機制與模型評價[J]. 計算機學報, 2013, 36(9): 1765-1784)

[3]Dorsch C, H?ckel B. Combining models of capacity supply to handle volatile demand: The economic impact of surplus capacity in cloud service environments[J]. Decision Support Systems, 2014, 58(1): 3-14

[4]Boru D, Kliazovich D, Granelli F, et al. Energy-efficient data replication in cloud computing datacenters[J]. Cluster Computing, 2015, 18(1): 385-402

[5]Luo Junzhou, Jin Jiahui, Song Aibo, et al. Cloud computing: Architecture and key technologies[J]. Journal on Communications, 2011, 32(7): 3-21 (in Chinese)(羅軍舟, 金嘉暉, 宋愛波, 等. 云計算: 體系架構與關鍵技術[J]. 通信學報, 2011, 32(7): 3-21)

[6]Li Qiao, Zhen Xiao. Research survey of cloud computing[J]. Computer Science, 2011, 38(4): 32-37 (in Chinese)(李喬, 鄭嘯. 云計算研究現狀綜述[J]. 計算機科學, 2011, 38(4): 32-37)

[7]Ahmed W, Wu Yongwei, Zheng Weimin. Response time based optimal Web service selection[J]. IEEE Trans on Parallel & Distributed Systems, 2013, 26(2): 551-561

[8]Wei Wei, Liu Yang, Yang Weidong. A fast approximation algorithm for the general resource placement problem in cloud computing platform[J]. Journal of Computer Research and Development, 2016, 53(3): 697-703 (in Chinese)(魏蔚, 劉揚, 楊衛東. 一種通用云計算資源調度問題的快速近似算法[J]. 計算機研究與發展, 2016, 53(3): 697-703)

[9]Mao Chengying, Chen Jifu, Towey D, et al. Search-based QoS ranking prediction for Web services in cloud environments[J]. Future Generation Computer Systems, 2015, 50(C): 111-126

[10]Liu Hongbo, Abraham A, Mcloone S. Swarm scheduling approaches for work-flow applications with security constraints in distributed data-intensive computing environments[J]. Information Sciences, 2012, 192(6): 228-243

[11]Topcuouglu H, Hariri S, Wu Minyou. Performance-effective and low-complexity task scheduling for heterogeneous computing[J]. IEEE Trans on Parallel & Distributed Systems, 2002, 13(3): 260-274

[12]Wen Yun, XuHua, Yang Jiadong. A heuristic-based hybrid genetic-variable neighborhood search algorithm for task scheduling in heterogeneous multiprocessor system[J]. Information Sciences, 2011, 181(3): 567-581

[13]Feng Dengguo, Zhang Min, Zhang Yan, et al. Study on cloud computing security[J]. Journal of Software, 2011, 22(1): 71-83 (in Chinese)(馮登國, 張敏, 張妍, 等. 云計算安全研究[J]. 軟件學報, 2011, 22(1): 71-83)

[14]Fang Yulin, Qureshi I, Sun Heshan, et al. Trust, satisfaction, and online repurchase intention: The moderating role of perceived effectiveness of E-commerce institutional mechanisms[J]. Mis Quarterly, 2014, 38(2): 407-427

[15]Yu Nenghai, Hao Zhuo, Xu Jiajia, et al. Review of cloud computing security[J]. Acta Electronic Sinica, 2013, 41(2): 371-381 (in Chinese)(俞能海, 郝卓, 徐甲甲, 等. 云安全研究進展綜述[J]. 電子學報, 2013, 41(2): 371-381)

[16]Krautheim F J, Phatak D S, Sherman A T. Introducing the trusted virtual environment module: A new mechanism for rooting trust in cloud computing[G]Trust and Trustworthy Computing. Berlin: Springer, 2010: 211-227

[17]Manuel P. A trust model of cloud computing based on quality of service[J]. Annals of Operations Research, 2015, 233(1): 281-292

[18]Li Yongjun, Dai Yafei. Research on trust mechanism for peer-to-peer network[J]. Chinese Journal of Computers, 2010, 33(3): 390-405 (in Chinese)(李勇軍, 代亞非. 對等網絡信任機制研究[J]. 計算機學報, 2010, 33(3): 390-405)

[19]Xu Feng, Wang Yuan, Zhang Lin, et al. A trust chain discovery algorithm for open environment[J]. Journal of Computer Research and Development, 2006, 43(Suppl2): 72-77 (in Chinese)(徐鋒, 王遠, 張林, 等. 一個開放環境中信任鏈發現算法的設計與分析[J]. 計算機研究與發展, 2006, 43(增刊2): 72-77)

[20]Ko R, Jagadpramana P, Mowbray M, et al. TrustCloud: A framework for accountability and trust in cloud computing[C]Proc of the 2011 IEEE World Congress on Services. Los Alamitos, CA: IEEE Computer Society, 2011: 584-588

[21]Shu Jian, Liang Changyong. Dynamic trust model based on DS evidence theory under cloud computing environment[J]. Computer Science, 2016, 43(8): 105-109 (in Chinese)(束柬, 梁昌勇. 基于DS理論的多源證據融合云安全信任模型[J]. 計算機科學, 2016, 43(8): 105-109)

[22]Chinosi M, Trombetta A. BPMN: An introduction to the standard[J]. Computer Standards & Interfaces, 2012, 34(1): 124-134

[23]Kim M, Hiroyasu T, Miki M, et al. SPEA2: Improving the performance of the strength pareto evolutionary algorithm 2[G]LNCS 3242: Proc of Int Conf on Parallel Problem Solving from Nature. Berlin: Springer, 2004: 742-751

[24]Silverman B W. Density Estimation for Statistics and Data Analysis[M]. London: Chapman &Hall, 1986

[25]Deb K, Pratap A, Agarwal S, et al. A fast and elitist multi-objective genetic algorithm: NSGA-Ⅱ[J]. IEEE Trans on Evolutionary Computation, 2002, 6(2): 182-197

[26]Gen M, Lin Lin. Multi-objective evolutionary algorithm for manufacturing scheduling problems: State-of-the-art survey[J]. Journal of Intelligent Manufacturing, 2014, 25(5): 849-866

ShuJian, born in 1989. PhD. His main research interests include cloud computing, information management, information security, and trust theory.

LiangChangyong, born in 1965. PhD, professor, PhD supervisor. His main research interests include information system & information management, cloud service, and decision science.

XuJian, born in 1982. PhD candidate. His main research interests include big data, data mining, game theory, and machine learning.