一種虛擬服務(wù)資源的多分配任務(wù)的選擇方法

陳為兵，王忠群

（安徽工程大學 計算機與信息學院，安徽 蕪湖 241000）

隨著服務(wù)計算技術(shù)的發(fā)展，面向服務(wù)的企業(yè)作為一種新的業(yè)務(wù)模式受到廣泛關(guān)注［1－7］.越來越多的服務(wù)需要多個組織提供的虛擬服務(wù)資源來支持完成，使得網(wǎng)絡(luò)成為一個機－機乃至人－機協(xié)同動作的平臺.虛擬服務(wù)資源的概念可以延伸到包括軟件、硬件、人力、物理設(shè)備乃至環(huán)境等各種支持服務(wù)屬性的要素［3］.服務(wù)質(zhì)量（QoS）是衡量虛擬服務(wù)資源選擇的一個重要方面，包括執(zhí)行時間、費用、可用性及可靠性等.

目前，對于服務(wù)組合方面相關(guān)研究較多.企業(yè)間的主觀信任關(guān)系對服務(wù)選擇起決定性作用，文獻［2］提出了一種基于信任關(guān)系的業(yè)務(wù)服務(wù)選擇方法.對于用戶來說個性化服務(wù)是服務(wù)需求的趨勢，文獻［3］提出一種面向個性化需求的虛擬服務(wù)資源整合方法，把服務(wù)資源以多維度分類樹的方式進行描述.文獻［4］提出了一種基于聲譽的推薦方法，給出具有高聲譽值的推薦信息源.文獻［5］提出了一個考慮資源置信度的跨企業(yè)項目伙伴選擇模型，提出了兩個優(yōu)化算法分別對速度和最優(yōu)率進行優(yōu)化.文獻［6］提出了一種支持服務(wù)應(yīng)用關(guān)聯(lián)的服務(wù)選擇方法，展現(xiàn)了關(guān)聯(lián)服務(wù)對選擇過程的影響.

然而，上述文獻都未考慮到虛擬服務(wù)資源中的資源數(shù)量受限問題，如硬件、人力資源、物理設(shè)備等資源數(shù)量有限，其可用性伴隨用戶數(shù)量而波動.服務(wù)提供商在提供虛擬服務(wù)資源時存在瓶頸問題，需要同時提供給多個用戶的多個子任務(wù)使用.資源的可用性是可信性的一個重要方面，本文對服務(wù)資源進行分類，加入置信度概念，綜合考慮項目QoS指標、信任度及費用等參數(shù)，對服務(wù)資源運用遺傳算法求解，最后驗證方法的可行性和有效性.

1 問題描述和有關(guān)符號定義

假設(shè)某企業(yè)（主企業(yè)）有一個由多子任務(wù)構(gòu)成的項目，其部分工作流程需對外招標，由其他外包企業(yè)協(xié)助完成.工作流程分為子任務(wù)1、子任務(wù)2、…、子任務(wù)i、…、子任務(wù)n，當項目進行到子任務(wù)i時，主企業(yè)要對外包企業(yè)提供的資源進行評估.對硬件、人力、物理設(shè)備等服務(wù)資源進行分類：一類是可同時向外提供多任務(wù)節(jié)點資源（M），另一類是提供單任務(wù)節(jié)點資源（N）.從信任度角度看，存在外包企業(yè)同時投標多個子任務(wù)的情況，在選擇子任務(wù)i的服務(wù)資源時，由于在同一時刻提供M資源的外包企業(yè)同時也在提供資源給其他子任務(wù)，我們對于它的信任度也會相應(yīng)有所降低，所以在考慮用戶對M資源的信任度時，有必要在原信任度上乘以一個信任因子pk，這樣更能準確地刻畫資源的隨機性.首先，我們給出3個假設(shè)：①假設(shè)項目可以獨立分為多個子任務(wù)；②假設(shè)各子任務(wù)之間的交接時間為0；③假設(shè)每個子任務(wù)只能由一個外包企業(yè)來提供服務(wù)資源.

為便于表述，給出如下符號：i為項目流程中每個子任務(wù)的序號，i＝1，2，3，…，I；j為兄弟企業(yè)提供給子任務(wù)i相對應(yīng)的資源集群里服務(wù)資源的序號，j＝1，2，3，…，Ji；Xij為0－1決策變量，當Xi，jj＝1時就表示資源集群里j資源被子任務(wù)i所征用，相反Xi，j＝0，i＝1，2，3，…，I，j＝1，2，3，…，Ji；Ci，j為資源集群i中資源j運行一次的費用成本；ti，j為資源集群i中資源j運行一次的時間成本；ai，j為資源集群i中資源j的可用性；ri，j為資源集群i中資源j在運行中的可靠性；hi，j為用戶對資源集群i中資源j的信任度；α為置信水平，α∈ ［0，1］；pk為信任因子，p∈ ［0，1］，k＝1，2，3，…，Ki；Ci為用戶對子任務(wù)i開銷費用的期望上限值；Ti為用戶對子任務(wù)i運行時間的期望上限值；Ai為用戶對子任務(wù)i的期望可用性下限值；Ri為用戶對子任務(wù)i的期望可靠性下限值；Hi為用戶對子任務(wù)i期望信任度下限值；Yi為用戶對配置后資源i的信任度下限值；C0為用戶對整個工作流程運行一次所產(chǎn)生總費用的上限值；T0為用戶對整個工作流程運行一次所需總時間的上限值；Y0為用戶對整個工作流程運行一次配置后資源信任度的下限值.

2 基于多任務(wù)服務(wù)資源選擇模型的建立

本文綜合考慮QoS指標、信任度、費用3個參數(shù)作為決策因數(shù)，對有關(guān)硬件、人力、物理設(shè)備等服務(wù)資源進行選擇，將流程總執(zhí)行時間、總執(zhí)行費用作為規(guī)劃目標.此處QoS指標包括：任務(wù)執(zhí)行時間、費用、可用性和可靠性，pk為因外包企業(yè)提供給其他子任務(wù)資源而降低目前子任務(wù)資源信任度的一個懲罰因數(shù).假設(shè)某外包企業(yè)能同時提供給k（k＝1，2，3，…，Ki）個子任務(wù)的資源l，那么用戶對此l資源的信任度就會在原有基礎(chǔ)上有所降低.設(shè)，k＝1，2，3，…，Ki，x1∈ ［0，1］，x1為用戶對資源l劃分后第一個起點.不難理解當k＝1時，x1＝0；當k≠1時，x1≠0，x1的取值如表1所示.

表1 x1取值與k之間的對應(yīng)關(guān)系

資源服務(wù)選擇模型定義如下：

在上述式子中，式（1）表示所有工作流程總運行費用和總運行時間分別與用戶期望的總運行費用和總運行時間的差值依字典序達最??；式（2）表示所有工作流程總運行費用、總運行時間和配置后資源信任度與用戶期望值的差值；式（3）表示用戶對每個子任務(wù)所需資源的信任度在置信水平a上不低于用戶的期望值；式（4）、（5）表示完成每個子任務(wù)時，對所選資源的費用和時間都不高于用戶的期望值；式（6）、（7）表示完成每個子任務(wù)時，對所選資源的可用性、可靠性都不低于用戶的期望值；式（8）為0－1決策變量，表示每個子任務(wù)只能由一個外包企業(yè)來承擔；式（9）為數(shù)據(jù)關(guān)系表達式.

在業(yè)務(wù)流程中除了順序結(jié)構(gòu)外，還有并行、選擇和循環(huán)結(jié)構(gòu)，下面給出各結(jié)構(gòu)的時間和費用計算方法.

③選擇結(jié)構(gòu)中，假設(shè)業(yè)務(wù)流程由I個子任務(wù)組成，每個子任務(wù)i被選擇的概率為，總時間

④循環(huán)結(jié)構(gòu)中，假設(shè)業(yè)務(wù)流程由I個子任務(wù)順序組成，此流程的循環(huán)概率為γ，總時間T＝

3 模型求解

由于此問題不是線性問題，我們采用遺傳算法對上述模型進行求解.其算法思想是將每一個配置后的業(yè)務(wù)流程編碼為一個染色體，通過染色體之間的選擇、交叉和變異產(chǎn)生出具有更高適應(yīng)度值的染色體，重復上述步驟直到滿足具體要求，最終得到一個染色體集，此染色體集是在解空間尋求的解集.具體步驟：①編碼.對流程涉及到的每個資源進行編號，每個資源是一個基因，一個染色體是一串基因的組合.②產(chǎn)生初始種群.隨機產(chǎn)生N個個體組成初始種群，每個染色體稱為一個個體，N個個體構(gòu)成了一個種群.假設(shè)現(xiàn)在的代數(shù)g1＝0，假設(shè)種群規(guī)模為W，開始時染色體上面的基因在［1，W］隨機選取隨機排列而成.③計算適應(yīng)度值.評估種群中所有個體的目標值，再評估每個個體的適應(yīng)度值，此處適應(yīng)度值函數(shù)f＝100D＋c＋10D＋t＋D＋y.④種群進化.對于選擇算子，采用輪盤賭的方式進行；對于交叉算子，采用雙點交叉進行；對于變異算子，以一定概率丟失某個基因，再在［1，W］隨機產(chǎn)生一個基因來代替它.⑤終止檢驗.滿足條件停止運算，最終種群解是我們需要的解集，代數(shù)g1＝g1＋1，否則繼續(xù)執(zhí)行.

4 仿真實驗與分析

實驗以摩托車裝配流水線過程來示例.摩托車裝配過程分為發(fā)動機裝配（子任務(wù)S1），部件裝配（子任務(wù)S2），車架裝配（子任務(wù)S3），成車裝配（子任務(wù)S4），產(chǎn)品測試（子任務(wù)S5）和包裝下線（子任務(wù)S6），前3個節(jié)點是并行結(jié)構(gòu)，后3個節(jié)點是順序結(jié)構(gòu)，總體形成一個順序結(jié)構(gòu)，制造流程結(jié)構(gòu)如圖1所示.

假設(shè)6個服務(wù)提供商ABCDEF，其提供資源與子任務(wù)Si間的對應(yīng)關(guān)系如表2所示.

圖1 摩托車制造流程結(jié)構(gòu)圖

表2 提供資源與子任務(wù)Si對應(yīng)關(guān)系

參數(shù)設(shè)置：A ＝22，B＝18，C＝10，D ＝20，E＝14，F(xiàn)＝6.

用VC＋＋6.0變成實現(xiàn)遺傳算法，交叉概率設(shè)為0.6，變異概率設(shè)為0.2，種群規(guī)模設(shè)為90.實驗的硬件平臺由Intel（R）Core（TM）i3－3220 3.30GHz和4.00GB內(nèi)存組成的PC機.實驗設(shè)置2組用戶的資源需求來說明多分配方式在資源選擇中的作用，服務(wù)資源參數(shù)設(shè)置如表3所示.

第1組表示不考慮資源的多分配任務(wù)作業(yè)，服務(wù)提供商在提供資源時按照S1S2S3S4S5S6的序列順序提供，第2組表示服務(wù)提供商可以多分配資源任務(wù)，不同用戶資源需求的選擇方案如表4所示.從表4可看出，配置信任因子之后的選擇方案不同于之前的選擇方案，這是由于服務(wù)提供商在多分配任務(wù)之后造成給用戶的信任度降低的結(jié)果，分配方式越多pk值的平均值就越小，給用戶的信任度就越低，被后續(xù)子任務(wù)選擇的概率也就越小.上述結(jié)果說明虛擬服務(wù)資源多分配任務(wù)算法的可行性和有效性.

表3 服務(wù)資源參數(shù)設(shè)置

表4 不同用戶資源需求的選擇方案

5 結(jié)束語

隨著企業(yè)運營業(yè)務(wù)的全球化，基于Web環(huán)境的虛擬服務(wù)資源選擇已成為企業(yè)外包過程中必不可少的一個環(huán)節(jié).多層次多角度的分析資源，對于資源選擇的研究有著十分重要的意義.本文將服務(wù)提供商分為兩類，對提供多任務(wù)的服務(wù)資源設(shè)置了信任因子，運用遺傳算法對模型進行了求解，并用實例驗證該算法的可行性和有效性.但在上述過程中未考慮到資源釋放問題，在占用資源一定時間后，子任務(wù)會釋放資源，下一步工作將對此進行研究.

［1］ 張建良，范玉順.面向服務(wù)的企業(yè)與業(yè)務(wù)生態(tài)系統(tǒng)［J］.計算機集成制造系統(tǒng)，2010，16（8）：1 751－1 759.

［2］ 李素粉，范玉順.基于信任關(guān)系的業(yè)務(wù)服務(wù)選擇方法［J］.計算機集成制造系統(tǒng)，2011，17（10）：2 278－2 285.

［3］ 初佃輝，王顯志，王忠杰，等.面向個性化需求的服務(wù)資源整合方法［J］.計算機學報，2011，34（12）：2 370－2 380.

［4］ 潘靜，徐鋒，呂建.面向可信服務(wù)選取的基于聲譽的推薦者發(fā)現(xiàn)方法［J］.軟件學報，2010，21（2）：388－400.

［5］ 徐漢川，徐曉飛，何霆，等.考慮資源置信度的跨企業(yè)項目伙伴選擇方法［J］.計算機集成制造系統(tǒng)，2010，16（7）：1 480－1 486.

［6］ 李素粉，范玉順，李秀.支持服務(wù)應(yīng)用關(guān)聯(lián)的服務(wù)選擇方法［J］.計算機集成制造系統(tǒng)，2012，18（3）：645－653.

［7］ Skopik F，Schall D，Dustdar S.Modeling and mining of dynamic trust in complex service－oriented systems［J］.information system，2010，35：735－757.