陳為兵，王忠群

（安徽工程大學(xué) 計(jì)算機(jī)與信息學(xué)院，安徽 蕪湖 241000）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 模型求解

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

4 仿真實(shí)驗(yàn)與分析

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

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

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

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

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

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

［6］ 李素粉，范玉順，李秀.支持服務(wù)應(yīng)用關(guān)聯(lián)的服務(wù)選擇方法［J］.計(jì)算機(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.