張云勇，李素粉，吳俊，房秉毅

（1. 中國聯(lián)通研究院，北京 100048；2. 北京郵電大學 經(jīng)濟管理學院，北京 100876）

1 引言

云計算作為信息通信技術（ICT, information and communication technology）轉(zhuǎn)型機遇的發(fā)展趨勢，已經(jīng)得到了國內(nèi)外業(yè)界的廣泛認同，很多市場調(diào)研機構紛紛預測云服務將成為全球增長速度最快的市場，我國政府在國家戰(zhàn)略高度也積極推進國家云計劃。

云計算環(huán)境下，一些大型企業(yè)紛紛將傳統(tǒng)業(yè)務向云服務轉(zhuǎn)型，組建企業(yè)云，形成云服務資源池。例如，亞馬遜建立專門的數(shù)據(jù)中心，以云服務的形式向用戶和開發(fā)者提供存儲和計算資源。云計算發(fā)展趨勢下，企業(yè)的業(yè)務以云服務形式進行共享和集成。隨著云計算在企業(yè)的廣泛應用，必將催生大量服務。以電信行業(yè)為例，國內(nèi)外電信運營企業(yè)紛紛開展云計算相關研究和應用，逐漸形成基礎設施即服務（IaaS, infrastructure as a service）、平臺即服務（PaaS, platform as a service）和軟件即服務（SaaS,software as a service）3個層次的服務資源池，服務資源將呈現(xiàn)規(guī)模化和商業(yè)化特點。這種情況下，對于企業(yè)內(nèi)部或外部用戶需求，有效的服務選擇方法，對于提高服務選擇結果的有效性和服務資源的整體利用率具有重要意義。

隨著服務計算思想在企業(yè)界和學術界的擴展與滲透，服務選擇相關研究近幾年得到國內(nèi)外學者重視，取得了豐富的研究成果。服務計算環(huán)境下的服務選擇是指根據(jù)用戶需求，包括功能性需求和非功能性需求，從服務資源池中選擇出滿足用戶需求的服務。

基于功能需求的服務匹配是指根據(jù)用戶對服務的功能性需求描述，例如服務的輸入輸出接口描述，從服務資源池內(nèi)選擇出與功能需求相匹配的服務流程，服務流程由一個或者多個抽象服務節(jié)點依一定的流程結構組合而成，每個抽象服務對應服務資源池內(nèi)一個或者多個功能相同的具體服務。相關研究主要是針對Web服務選擇展開，采用基于關鍵詞[1]和基于語義的服務[2～4]匹配方法等。查全率和查準率是關鍵詞匹配方法面臨的兩大研究難點，基于語義的方法可以改善這一問題。語義Web服務的語義信息是以本體為基礎實現(xiàn)，而現(xiàn)實應用系統(tǒng)中難以構建完善的本體庫，且語義異構等現(xiàn)象普遍存在，信息描述不能對語義邏輯提供充分的支持。文獻[4]通過定義良好的語義信息，提高服務選擇方法的效率。

基于非功能性需求的服務選擇是指基于特定的抽象服務流程，根據(jù)用戶對服務的非功能性需求以及服務資源池內(nèi)服務的運行狀態(tài)等信息，為抽象服務流程中的每個節(jié)點選擇出一個或者一組具體服務。相關研究主要集中在基于QoS需求的服務選擇方法研究，包括服務質(zhì)量模型[5,6]、QoS局部最優(yōu)服務選擇[7]、QoS全局最優(yōu)服務選擇[8～10]以及基于信任[11,12]和服務關聯(lián)[13,14]等因素的服務選擇。

上述研究主要是針對服務計算環(huán)境下服務選擇的特點展開。服務計算環(huán)境下，服務資源具有海量特點，同時服務類型多種多樣，也具有海量特點，各服務提供商通過公共注冊中心進行服務注冊，由服務中介或者服務選擇平臺根據(jù)用戶需求進行服務選擇。因此，服務計算環(huán)境下服務選擇具有2個特點：面向海量服務資源和面向用戶。基于這2個特點，現(xiàn)有相關研究主要集中在：基于用戶需求（包括對服務的功能需求和非功能需求），在海量服務資源中選擇出最優(yōu)[8]或者滿足用戶需求[15]的服務。

云計算環(huán)境下服務選擇在一定程度上與服務計算環(huán)境下的服務選擇類似，但同時具有自身的特點。隨著云計算在企業(yè)的廣泛應用，必將催生大量云服務，這一點與服務計算環(huán)境類似，可以借鑒相關的服務選擇方法和研究成果。然而，在同一朵云中，服務的類型一般不會出現(xiàn)海量特點，例如，亞馬遜云，提供的服務類型包括存儲、計算、數(shù)據(jù)庫和網(wǎng)絡等 11類[16]，其中以計算和存儲服務為主。云計算環(huán)境下，政府或者大型集團企業(yè)（在本文中統(tǒng)稱為服務提供商）構建“政府云”或“企業(yè)云”，服務提供商根據(jù)用戶需求進行服務選擇。服務選擇過程不僅考慮用戶需求，同時關注提供商服務資源池的資源調(diào)度問題。因此，與服務計算環(huán)境下服務選擇相比，云計算環(huán)境下服務資源選擇具有2個特點：一方面，服務資源類型有限；另一方面，在考慮用戶需求的同時兼顧服務資源調(diào)度。目前，服務選擇相關研究主要集中在基于功能和非功能需求的服務選擇方法，兼顧服務資源調(diào)度的服務選擇相關研究鮮有提及。

本文基于服務選擇現(xiàn)有研究基礎，針對云計算環(huán)境下的服務選擇特點，從服務提供商角度出發(fā)，研究云計算環(huán)境下的服務選擇問題。首先，分析云服務提供商的服務資源特點，對服務資源池進行形式化描述。進而，提出一種兼顧用戶需求和服務資源調(diào)度的服務選擇方法，重點分析3種服務資源調(diào)度原則，分別構建計算規(guī)則，并將其引入到服務選擇模型，建立基于用戶需求和服務資源調(diào)度的服務選擇數(shù)學模型。設計智能算法進行求解。最后進行算例分析。

2 面向云服務提供商的服務選擇流程

為清楚地描述服務選擇流程，首先對云服務資源池進行形式化描述。然后，從云服務提供商角度出發(fā)，給出服務選擇總體思路，并設計具體服務選擇流程。

2.1 云服務資源池形式化描述

云服務資源池由多個云服務構成，每個云服務具有一定的業(yè)務類型。為便于描述，首先對云服務資源池的劃分進行假設并對相關概念進行形式化定義。

假設 1 假設云服務提供商的服務資源能夠按照功能進行分組，將所有服務資源分為若干個服務組，記為 ServiceSet，形成服務組集合，記為ServiceSetS，可以描述為式（1）。

其中，N為自然數(shù)。

根據(jù)假設1，同一個服務組中的服務具有相同或相似的業(yè)務功能，不同服務組中的服務具有不同的業(yè)務功能。每個服務組由一個抽象服務標識，描述為

其中，GroupID是服務組的唯一性標識；FuncSet是服務組ServiceSet內(nèi)云服務的業(yè)務功能描述，本文用三元組進行描述，如式(3)。

其中，F(xiàn)unction是服務的業(yè)務功能描述；Input和Output分別是輸入和輸出接口描述。

定義 1 云服務指云服務資源池內(nèi)具有特定業(yè)務功能和非功能描述的具體服務，本文用六元組對云服務進行形式化描述，如式（4）。

其中，S表示云服務；GroupID指服務S所屬的服務組編號；ID是服務S在服務組GroupID中的編號，GroupID與ID一起形成云服務S的唯一性標識；FuncSet是服務S的功能描述，定義同式（3）；QoSSet是服務S的質(zhì)量描述，QoSSet是一個復合參數(shù)，用參數(shù)向量表示 QoSSet=(QoS1, QoS2,QoS3, … )，一般包括服務的執(zhí)行時間、費用和可靠性等指標，不同類型服務需要的QoS指標可能不同,隨應用場景變化，服務的QoSSet參數(shù)值會發(fā)生變化；Provider指服務S的提供單位；Site指服務所在的物理位置。

對于云服務資源池內(nèi)的云服務，提供模式一般分為 2種：1）單一服務提供，根據(jù)用戶需求，選擇資源池內(nèi)的一個服務提供給用戶；2）組合服務提供，根據(jù)用戶需求，選擇資源池內(nèi)的多個服務形成服務流程，提供給用戶，例如亞馬遜多個云服務的結合使用[16]，如圖1所示。

圖1 亞馬遜多個云服務的結合使用

鑒于云服務提供商的云服務類型有限，例如亞馬遜目前提供 11類云服務[16]，容易挖掘出潛在組合服務流程。可以依據(jù)歷史應用信息和服務之間的業(yè)務關聯(lián)進行服務流程挖掘。服務流程挖掘不是本文研究的重點，這里不再詳細討論。在實例化之前，組合服務流程是一類抽象服務，本文用二元組對其進行描述，如式(5)所示。

所有的云服務流程形成云服務流程集合，記為ServiceFlowS。

抽象云服務集合ServiceSetS和抽象云服務流程集合ServiceFlowS一起描述了服務資源池能夠提供的所有服務類型。本文采用五元組對服務資源池進行形式化描述，如式(6)。

其中，PoolID、PoolName和 PoolOwner分別描述服務資源池的唯一標識、名稱和所屬企業(yè)等基本信息；ServiceSetS和ServiceFlowS的含義分別見式（1）和式（5）。

2.2 面向提供商的云服務選擇流程

面向云服務提供商的服務選擇總體思路可以描述為：面對用戶的服務請求，首先分析用戶的服務需求，將其抽象為功能需求集合和非功能需求集合，作為服務選擇的依據(jù)，這里的非功能需求用服務質(zhì)量（QoS）描述。然后根據(jù)功能需求集合依次在服務組集合ServiceSetS和服務流程集合ServiceFlowS中進行功能匹配，找到滿足功能需求的服務，形成抽象服務描述 ServiceSet或抽象服務流程描述ServiceFlow，每個抽象服務對應多個功能相同或相似的具體服務S。進而，綜合考慮用戶的QoS需求和服務資源調(diào)度，為每一個抽象服務選擇一個具體服務。最后形成服務選擇結果，提供給用戶。

基于上述思路，面向云服務提供商的服務選擇具體流程如圖2所示，具體描述如下。

步驟 1 根據(jù)給定的用戶需求，用戶需求包括對服務的功能需求描述和非功能需求描述，云服務選擇系統(tǒng)根據(jù)需求描述，將用戶需求抽象為用戶功能需求集合和非功能需求集合，分別用符號UserFuncSet和UserQoSSet描述。

步驟 2 服務選擇系統(tǒng)根據(jù) UserFuncSet中的參數(shù)需求，在服務資源池中查找功能匹配的服務組。匹配方法如下。

圖2 面向云服務提供商的服務選擇流程

步驟 2.1 進行單一服務匹配，根據(jù)用戶需求UserFuncSet參數(shù)在服務組集合ServiceSetS中對抽象服務ServiceSet進行匹配，查找FuncSet各參數(shù)均與用戶需求相應參數(shù)匹配的服務組ServiceSet。

根據(jù)假設1，匹配結果有2種：0或1。若返回結果為 1，則表明服務資源池中存在滿足用戶功能需求的單一服務，將該服務所在的服務組ServiceSet稱作候選服務集合，記為ServiceSetAim，轉(zhuǎn)步驟3；若返回結果為 0，則表明服務資源池中的任一服務均不能單獨實現(xiàn)用戶的功能需求，轉(zhuǎn)步驟2.2。

步驟 2.2 進行服務流程匹配，根據(jù)用戶需求UserFuncSet參數(shù)在抽象云服務流程集合 Service FlowS中對ServiceFlow進行匹配，查找FlowFuncSet各參數(shù)均與用戶需求相應參數(shù)匹配的服務流程ServiceFlow。匹配結果有 3種情況：1)0；2)1；3)大于1。對于情況1)，轉(zhuǎn)步驟6。對于情況2)，將匹配的服務流程 ServiceFlow稱作目標服務流程，記為ServiceFlowAim，轉(zhuǎn)步驟3。對于情況3)，將匹配的多個服務流程 ServiceFlow稱作目標服務流程集合，記為ServiceFlowAimS，轉(zhuǎn)步驟4。

步驟 3 對于步驟 2.1生成的候選服務集合ServiceSetAim，或者步驟 2.2生成的目標服務流程ServiceFlowAim，分析用戶的 QoS需求參數(shù)UserQoSSet，采用基于QoS需求偏好和服務資源調(diào)度的服務選擇方法（見本文第 3節(jié)），進行具體服務選擇。服務選擇結果有2種：成功或失敗。成功則輸出選擇結果，記為SelectedService，轉(zhuǎn)步驟5。失敗則轉(zhuǎn)步驟6。

步驟 4 對于步驟 2.2生成的目標服務流程集合 ServiceFlowAimS，對其中的每一個元素ServiceFlow用基于QoS需求偏好和服務資源調(diào)度的服務選擇方法（見本文第3節(jié)），進行服務選擇。同樣，服務選擇結果有2種：成功或失敗。對于成功服務流程ServiceFlow，進行標記和統(tǒng)計，數(shù)量記為SFN。若SFN=0，轉(zhuǎn)步驟6；若SFN=1，則輸出服務選擇結果，轉(zhuǎn)步驟5；若SFN＞1，說明存在具體服務流程滿足用戶需求，則從促進服務資源的均衡利用角度出發(fā)，以最優(yōu)資源調(diào)度為原則，選擇其中一個具體服務流程，作為服務選擇結果，記為SelectedServiceFlow。轉(zhuǎn)步驟5。

步驟5 找到滿足用戶需求的服務資源，選擇的服務資源為SelectedService或者SelectedServiceFlow，服務選擇過程結束。

步驟6 沒有找到滿足用戶需求的服務，服務選擇過程結束。

3 基于QoS需求偏好和服務資源調(diào)度的服務選擇方法

針對第2節(jié)服務選擇流程中步驟3和步驟4，本節(jié)給出一種基于 QoS需求偏好和服務資源調(diào)度的服務選擇方法。

3.1 符號定義

為便于建立基于數(shù)學模型，首先給出表1所示符號定義。

3.2 模型要素分析

基于 QoS需求偏好和服務資源調(diào)度的服務選擇模型的要素可以分為2類：QoS指標和服務資源調(diào)度相關指標。本節(jié)對這2類指標進行分析，并給出各指標的計算規(guī)則。

表1 基于QoS需求偏好和服務資源調(diào)度的服務選擇模型基本符號

3.2.1 QoS指標

QoS指標一般包括服務的執(zhí)行時間、費用、可用性、可靠性和處理能力等。云服務分為3個層次SaaS、PaaS和IaaS，對于不同層次的服務。本文用向量Q=(Q1，Q2，Q3，…，Qk，…，QK)描述用戶對服務的QoS指標需求，Q1描述用戶最關心的指標，Q2次之，以此類推。服務的QoS參數(shù)值會出現(xiàn)在服務描述中。因此，各個服務的QoS指標相關參數(shù)值可以從服務描述中獲取。

3.2.2 服務資源調(diào)度相關指標

云服務資源調(diào)度是指基于調(diào)度規(guī)則對云服務資源池中的云服務進行合理有效的調(diào)節(jié)和利用。本文主要考慮3種調(diào)度原則：資源集約利用原則、資源均衡利用原則和物理距離最短原則。本文第2.2節(jié)的服務選擇流程，基于功能的服務匹配結果有2種：單服務和服務流程。為簡化描述計算過程，將第1種結果（單服務）看作僅包含一個服務節(jié)點的服務流程。

1) 資源集約利用原則

該調(diào)度原則主要針對物理服務器的資源利用效率問題。目前，服務器資源是云服務的一個主要內(nèi)容，一般通過虛擬化技術將物理服務器虛擬為多個獨立虛擬服務器（簡稱為虛機），將虛機作為獨立的云服務器資源向用戶提供。為提高物理服務器資源的利用率，本文設計了資源集約利用原則，核心思想是優(yōu)先選擇處于開啟狀態(tài)的物理服務器上的虛擬服務器資源。這一原則在服務選擇模型中將以資源集約利用函數(shù)F1體現(xiàn)，F(xiàn)1是物理服務器開啟狀態(tài)的函數(shù)。

F1計算思路為：判斷服務Si,j所在物理服務器狀態(tài)參數(shù)ServerStatusi,j，ServerStatusi,j=0表示處于開啟狀態(tài)；ServerStatusi,j=1表示處于關閉狀態(tài)。F1的具體計算規(guī)則可以描述為式(7)。

其中，Xi,j∈{0,1},i=1,2,3,…,I, j=1,2,3,…,Ji，當服務Si,j是虛機資源時，Xi,j=1；否則Xi,j=0。

2) 資源均衡利用原則

本文從2個方面考慮資源均衡利用原則：不飽和運行狀態(tài)下的云服務資源均衡利用原則和飽和狀態(tài)下云服務資源均衡利用原則。

不飽和運行狀態(tài)下的云服務資源均衡利用原則，主要針對虛機（一類云服務資源）的選擇問題進行分析，對于已開啟的物理服務器資源，如何均衡利用其上的虛機資源。也就是說，當存在多個同類虛機可供選擇，這些虛機均處于空閑狀態(tài)且所在物理服務器為開啟狀態(tài)時，怎樣選擇其中一個虛機需要遵循一定的原則。本文采用的實現(xiàn)規(guī)則是優(yōu)先選擇當前負荷較小的物理服務器上的虛機資源。這一原則在服務選擇模型中將以函數(shù)F21體現(xiàn)，F(xiàn)21是物理服務器的虛機利用率函數(shù)。F21的計算思路是：獲取候選服務Si,j所在物理服務器當前時刻的虛機利用率ServerUtilizRatioi,j（已使用的虛機數(shù)/總虛機數(shù)），選擇利用率最小的物理服務器上的虛機資源。F21的具體計算規(guī)則可以描述為式（8）。

其中，Xi,j和ServerStatusi,j的含義同式（7）。

飽和狀態(tài)下云服務資源均衡利用原則，主要針對候選服務資源均處于忙碌狀態(tài)時的服務選擇問題進行分析。本文采用的實現(xiàn)規(guī)則是優(yōu)先選擇等待時間最短的服務資源。這一原則在服務選擇模型中將函數(shù)F22體現(xiàn)，F(xiàn)22是服務資源的實際等待時間函數(shù)。

在給出F22的計算規(guī)則之前，首先分析各候選服務的等待時間計算方法。

不失一般性，對服務等待進行假設，如假設2。

假設2 對于服務Si,j，如果當前運行實例數(shù)pni,j等于最大并行實例數(shù)pNi,j，則新的實例請求需要排隊等待。

服務的運行狀態(tài)包括：不飽和運行狀態(tài)（運行實例數(shù)小于pNi,j）、飽和運行狀態(tài)（運行實例數(shù)等于pNi,j）和排隊等待個數(shù)，由系統(tǒng)動態(tài)獲取。如果服務的運行實例數(shù)小于pNi,j，則等待時間為零；若運行實例數(shù)等于pNi,j，則根據(jù)服務的執(zhí)行時間和執(zhí)行進度計算等待時間；若服務有排隊，則根據(jù)其當前執(zhí)行進度、執(zhí)行時間、最大并行實例數(shù)pNi,j和排隊數(shù)量計算等待時間。基于此，服務Si,j等待時間的計算規(guī)則可以描述為式（9）。

其中，int()表示取整函數(shù)，這里采用上取整規(guī)則。其他各參數(shù)定義見表1。

對于一個組合服務流程，選擇具體服務之后，一般不會立刻使用所有服務。例如對于流程中任一服務（開始服務節(jié)點除外），只有等前一個串聯(lián)服務執(zhí)行結束后，即任務到達后，才會調(diào)用其選擇的具體服務資源。也就是說，一方面服務資源被釋放后才可進行實例化，另一方面任務到達后才會使用服務資源。因此，本文綜合考慮服務等待時間和任務到達時間，采用如下迭代計算過程計算流程中各個服務的實際等待時間：

其中，TotalTf()是服務流程總體時間類參數(shù)的計算函數(shù)，具體計算公式參見文獻[15]，TotalTf(wtk′,j+tk,j,k=1,2,3,…,i-1)表 示 服 務 流 程 中 前i-1個服務的執(zhí)行時間與實際等待時間之和，也就是第i個服務Si,j的任務到達時間。

整個服務流程總的實際等待時間即為流程中每個服務的實際等待時間之和，F(xiàn)22的計算規(guī)則如式（14）。

其中，函數(shù)TotalTf()的含義與式（12）相同。

3) 物理距離最短原則

云中的服務資源分布在不同的物理位置。服務選擇中，優(yōu)先選擇距離用戶較近的服務資源。這一原則在服務選擇模型中將以函數(shù)F3體現(xiàn)，F(xiàn)3是物理距離的函數(shù)。服務流程的物理距離包括2個方面，一方面是每個服務與用戶之間的物理距離，另一方面是兩兩服務之間的物理距離，這里主要考慮具有串聯(lián)關系的兩兩服務。本文基于這2種距離構造函數(shù)F3。

從服務Si,j描述中提取地理位置參數(shù)Sitei,j，從用戶需求中獲取用戶的位置參數(shù)，記為UserSite。F3的計算規(guī)則如式（15）。

其中，j =2,3,4,…,Ji；Distf( a, b)是距離函數(shù)，用于計算a, b兩點之間的距離；Zi,j∈{0,1}，Zi,j=1表示服務Si,j與Si+1,j之間是串聯(lián)關系，否則Zi,j=0。

3.2.3 總體指標的計算規(guī)則

對于需要選擇組合服務流程的情況，需要計算組合服務的總體QoS指標。在不同的流程實例中，需要根據(jù)局部流程的結構特點來計算。流程的基本結構主要有4種：順序、并行、選擇和循環(huán)。本文第2節(jié)描述的服務選擇流程，得到的服務組合流程將呈現(xiàn)上述4種或部分結構。關于4種不同流程結構下的總體指標計算方法，相關文獻研究較多[8,15]。本文中，總體指標的計算參見文獻[15]的計算方法。

由于不同的指標具有不同的量綱，因此在將多個指標進行綜合計算時，首先需要對各種指標進行無量綱歸一化處理。本文采用極差規(guī)格化變換[17,18]對每一指標值進行無量綱歸一化處理。無量綱歸一化處理后，服務個體每一質(zhì)量指標的取值都是[0, 1]區(qū)間上的無量綱點。本文所建模型中的參數(shù)均為歸一化處理后的參數(shù)。

3.3 基于QoS需求偏好和服務資源調(diào)度的服務選擇數(shù)學模型

基于QoS指標和服務的運行狀態(tài)建立基于用戶QoS需求偏好和服務資源調(diào)度的服務選擇數(shù)學模型。基于QoS指標的服務選擇是一個多目標數(shù)學規(guī)劃問題，鑒于目標規(guī)劃能較好的解決多目標決策問題，其目標函數(shù)不是尋求最大值或最小值，而是尋求這些目標與預計成果的最小差距，差距越小，目標實現(xiàn)的可能性越大。利用目標規(guī)劃的這一特點，服務選擇并不是以選擇最優(yōu)的服務為目標，而是找到滿足用戶需求的服務，在一定程度上可以避免優(yōu)質(zhì)服務排隊現(xiàn)象，利于服務的均勻利用。

本文采用目標規(guī)劃對基于QoS需求偏好和服務資源調(diào)度的服務選擇問題進行建模。用戶的QoS指標一般包括服務的執(zhí)行時間、費用、可用性、可靠性和處理能力等。將所選服務或組合服務流程的實際QoS指標值與用戶期望值的差值作為模型的目標項，差值越小表示越接近用戶需求，當差值為0時，表示所選服務或組合服務流程完全滿足用戶需求?；谟脩舻腝oS指標需求和服務的使用狀態(tài)，目標規(guī)劃的目標向量可以定義為：

目標向量是一個由多個目標項構成的一維向量，描述為式（16）。

其中，Objo表示目標因子，o=1,2,3,…,O，O是自然數(shù)，Objo≥0。

在一次服務選擇中，用戶對于不同指標的偏好程度可能不同，例如：用戶需求“在滿足服務執(zhí)行時間的條件下費用越低越好”，表明“執(zhí)行時間”的優(yōu)先等級高于“執(zhí)行費用”。針對這一情況，提供一種靈活的目標項權重設置方法。該方法通過采用權重向量實現(xiàn)，目標權重向量定義如下：

目標權重向量是一個由多個權重因子構成的一維向量，描述為

其中，αw表示權重因子，w=1,2,3,…,W，W是自然數(shù)；0≤αw≤1且

對于目標規(guī)劃問題，將目標權重向量與目標向量的點乘乘積函數(shù)作為目標規(guī)劃模型的目標函數(shù)，對于同一個目標函數(shù)，權重數(shù)量W與目標數(shù)量O相等，目標函數(shù)可以描述為

本文模型考慮4個等級的目標，前3個目標分別根據(jù)用戶的QoS需求生成，QoS指標需求一般可以分為2類，一類指標值越大越好，例如可用性、可靠性和處理能力等，在模型中用符號,k=1,2,3表示，另一類指標值越小越好，例如服務的執(zhí)行時間和費用等，在模型中用符號,k=1,2,3表示；第4個目標是服務資源調(diào)度函數(shù)，根據(jù)這4個目標，形成目標向量Obj=(V0,V0,V0,P1×F1 V 0+P21×F21V 0+P22×F22V 0+P3×F3 V 0)，其中4個目標因子分別表示所選服務或組合服務流程的實際QoS指標值與用戶期望值的差。根據(jù)用戶需求偏好決定目標權重向量ObjWeight?；谀繕讼蛄亢蜋嘀叵蛄浚瑯嬙炷繕撕瘮?shù)。模型的約束函數(shù)主要是目標約束和決策變量約束。

基于上述分析，建立基于QoS需求偏好和服務資源調(diào)度的服務選擇數(shù)學模型，模型描述如式(19)～式(22)。

其中，I=1表示單服務選擇，I＞1表示組合服務流程選擇。式(18)為目標函數(shù)，表示服務或組合服務的3個QoS指標分別與用戶期望值的差，依字典序分別達到最小，目標函數(shù)中的V表示“取大”操作，例如“V0”表示“”的值與“0”取大。式（20）、式（21）為模型的目標約束，表示3個QoS指標分別與用戶期望值的差。式（22）是決策變量約束，表示為每個抽象服務選擇一個具體服務，各參數(shù)的總體指標是Yi,j的函數(shù)。

3.4 模型求解

組合服務QoS局部和全局優(yōu)化計算問題都是NP問題，算法具有指數(shù)復雜度，隨著問題規(guī)模的增大，難以在多項式時間內(nèi)找到問題的最優(yōu)解[8,19]。遺傳算法（GA, genetic algorithm）作為一種智能優(yōu)化方法，具有并行計算、群體尋優(yōu)的特點，已廣泛應用于各種NP-Complete 問題的求解[8]。鑒于此，本文基于遺傳算法對所提服務選擇方法進行仿真計算。

算法的基本思想為：基于第2節(jié)服務選擇流程步驟2，在服務資源池中找到目標服務組，形成組合服務流程（可以包含一個或多個服務節(jié)點）。將每一個配置后的組合服務流程編碼為一個染色體，通過染色體之間的選擇、交叉和變異等遺傳操作，產(chǎn)生具有更高適應函數(shù)值的新染色體。這一過程不斷重復進行，實現(xiàn)在解空間的并行全局搜索。算法停止時，得到一個染色體集合，對應模型的解集，也就是服務選擇的方案集。

在遺傳算法中，適應值是對染色體進行評價的重要指標，適應值函數(shù)的構造非常重要。染色體對應問題的解，因此可以基于所求解問題的目標對染色體的適應值函數(shù)進行定義。

1) 適應值函數(shù)構建

根據(jù)模型的目標函數(shù)構建遺傳算法的適應值函數(shù) f′。

用戶對不同 QoS指標的需求偏好通過αk(k = 1 ,2,3)的取值來體現(xiàn)。

2) 適應值歸一化處理

直觀認識方面，適應值越高表示染色體性能越好，反之越差。因此便于直觀理解，對適應值f′采用負指數(shù)方法進行歸一化處理[15]，可以描述為

其中，μ＞0，是歸一化參數(shù)。

歸一化之后的適應值f是介于0和1之間的實數(shù)，f=1表示適應值最高，f=0表示適應值最低。

4 算例分析

4.1 參數(shù)初始化

本文基于云服務提供商的服務選擇方法，服務選擇結果可以是一個服務，也可以是由多個服務形成的組合服務流程。對于選擇結果是一個服務的情況，本節(jié)算例分析中把其看作包含一個服務節(jié)點的服務流程，對本文第3.3節(jié)所建模型進行算例分析。服務流程包含I個服務節(jié)點，這里令I=6，不失一般性，假設 I個服務組的規(guī)模相同且規(guī)模Ji= 2 0,i = 1 ,2,3,…, I 。

1) 服務資源池中服務的 QoS參數(shù)和資源調(diào)度相關參數(shù)

服務Si,j的相關參數(shù)值從服務描述中獲取，例如：對于云計算IaaS層面的某存儲服務Si,j，根據(jù)式（4）的云服務定義，有i=GroupID，j=ID且FuncSet和 QoSSet分別描述該服務的功能和質(zhì)量指標，Provider和Site分別描述該服務的提供者信息和所處的物理位置信息。

這里QoS指標分別取服務執(zhí)行費用、時間和可靠性。對于QoS指標參數(shù)和服務服務資源調(diào)度相關參數(shù)初始化，采用隨機方法，在一定范圍內(nèi)自動生成，每個參數(shù)的取值范圍設定如表2和表3所示，其中， j =1,2,3,… ,Ji, i = 1,2,3,… , I 。

表2 QoS參數(shù)相關參數(shù)取值范圍

表3 服務資源調(diào)度相關參數(shù)取值范圍

其中，參數(shù) q ueuei,j和pNi,j的取值是整數(shù)，參數(shù)queuei,j和pNi,j初始化方法分別是：在區(qū)間(0,60]和[1,20]上分別隨機產(chǎn)生一個實數(shù)，然后取整分別作為參數(shù) q ueuei,j和pNi,j的值；參數(shù)pni,j初始化方法是在區(qū)間[0,pNi,j]上隨機產(chǎn)生一個實數(shù)，然后取整作為該參數(shù)的值。

2) 用戶需求相關參數(shù)設置

不同的用戶需求一般體現(xiàn)在對各項指標的限值要求不同，本節(jié)實驗假設了3種不同的用戶需求情況，如表4所示。

表4 用戶需求相關參數(shù)設置

3) 目標權重參數(shù)

本文目標規(guī)劃模型考慮了4個目標，對應的目標權重向量包含4個權重因子。為比較不同用戶需求偏好情況下的服務選擇結果，本算例對4種不同的目標權重向量取值下的服務選擇進行計算分析，目標權重向量參數(shù)設置如表5所示。

表5 目標權重參數(shù)設置

其中，ObjWeightA的4個權重取值相同，表示4個目標優(yōu)先等級相同；ObjWeightB和ObjWeightC的權重設置表示3個QoS指標具有從高到低不同的優(yōu)先等級，未考慮資源調(diào)度問題；ObjWeightD的權重設置表示只考慮資源調(diào)度目標而不考慮用戶的QoS需求。

4) 遺傳算法參數(shù)

遺傳算法參數(shù)取交叉概率設為 0.6，變異概率設為0.1，染色體種群規(guī)模取25。

4.2 計算結果與分析

用VC++6.0編程實現(xiàn)求解算法。分別針對3種不同的用戶QoS需求和4種不同的目標權重情況進行具體服務選擇。通過設置不同的目標權重，決定在服務選擇模型中是否引入資源調(diào)度規(guī)則，其中，ObjWeightA和ObjWeightD權重設置下，在不同程度上考慮資源調(diào)度原則，ObjWeightA和ObjWeightD權重設置下，不考慮資源調(diào)度原則。服務選擇結果如表6和表7所示。

表6 不同用戶需求情況下的服務選擇方案(ObjWeightA)

表7 不同目標權重參數(shù)情況下的服務選擇方案(Case2)

表6表明，3種不同QoS需求情況下，前2種不同的用戶需求情況下，模型的適應值都等于 1，意味著用戶的需求都達到滿意，但并一定是系統(tǒng)內(nèi)服務選擇的最優(yōu)解或者最優(yōu)方案。因此本文所提服務選擇方法一方面能夠滿足用戶的需求，另一方面在一定程度上能夠減少優(yōu)質(zhì)服務排長隊的問題。對于用戶需求 Case3，算法運行結束時沒有找到適應值等于1的服務流程，即完全滿足需求的服務組合方案，這種情況下可以進而采用其他方法與用戶達成協(xié)定，例如服務協(xié)商。

表7表明，4種不同的目標權重參數(shù)下，都找到了滿足需求的具體服務選擇方案，而每種情況下的服務選擇方案不盡相同。目標權重反映了用戶對服務的QoS需求偏好和資源調(diào)度目標，表6的數(shù)據(jù)反映出不同的目標權重設置導致了不同的服務選擇結果。其中，對于目標權重 ObjWeightB和ObjWeightC，參數(shù)設置為(0.75, 0.2, 0.05, 0)和(0.5,0.5, 0, 0)，α4=0表示服務選擇計算過程中沒有考慮資源調(diào)度因素，這種情況下的服務選擇結果明顯區(qū)別于其他2組，同時，由于ObjWeightB和ObjWeightC具有不同 QoS權重，對應的服務選擇結果也不相同。因此，將用戶需求偏好和資源調(diào)度因素考慮到服務選擇過程具有重要意義。

5 結束語

服務選擇是云服務提供商進行服務提供時面臨的一個首要問題。本文從云服務提供商角度，分析影響服務選擇的主要因素，梳理服務選擇流程，給出服務選擇的具體實現(xiàn)步驟。進而建立基于用戶需求偏好和服務資源調(diào)度的服務選擇數(shù)學模型，設計智能算法進行求解。算例分析表明了方法的可行性和有效性。本文所提服務選擇流程和模型對于提高云服務提供商的服務運營效率具有一定指導意義。

[1] 鄧岳. 基于個性化服務匹配度的服務發(fā)現(xiàn)機制研究[D]. 西安：西安電子科技大學2007.DENG Y. Research on Service Discovery Based on Personalized Service Matchmaking Degree[D]. Xi’an: Xidian University, 2007.

[2] YANG F C, SU S, LI Z. Hybrid QoS-aware semantic Web service composition strategies[J]. Science in China Series F: Information Sciences, Science in China Press, Co-published with Springer-Verlag GmbH, 2008, 51(11): 1822-1840.

[3] 白東偉. 基于語義的 Web服務匹配與發(fā)現(xiàn)技術研究[D]. 北京: 北京郵電大學, 2008.BAI D W. Research on Web Services Semantic Matchmaking and Discovery[D]. Beijing: Beijing University of Posts and Telecommunications, 2008.

[4] 狄小峰. 基于分布式本體的服務選擇技術研究[D]. 北京: 清華大學, 2012.DI X F. Research on Service Selection Method based on Distributed Ontology[D]. Beijing: Tsinghua University, 2012.

[5] MENASCE D A. QoS issues in web services[J]. IEEE Internet Computing, 2002, 6: 72-75.

[6] RAN S. A model for web services discovery with QoS[J]. ACM, 2003,4(1): 1-10.

[7] YU T, LIN K J. The design of QoS broker algorithms for QoS-capable web services[J]. International Journal of Web Service Research,2004,1(4): 33-50.

[8] 劉書雷, 劉云翔, 張帆等. 一種服務聚合中 QoS 全局最優(yōu)服務動態(tài)選擇算法[J]. 軟件學報, 2007. 18(3): 646-656.LIU S L, LIU Y X, ZHANG F, et al. A dynamic Web services selection algorithm with QoS global optimal in Web services composition[J]. Journal of Software, 2007, 18 (3): 646-656.

[9] FUDZEE M F M, ABAWAJY J H. QoS-based adaptation service selection broker[J]. Future Generation Computer Systems, 2011, 27:256-264.

[10] GUO F, ZHAO L, WANG Y, et al. Research on the Web services selection problem[A]. Proceedings of the 2010 Second International Workshop on Education Technology and Computer Science(ETCS)[C]. Wuhan, China, 2010. 284 - 287.

[11] 潘靜, 徐鋒, 呂建. 面向可信服務選取的基于聲譽的推薦者發(fā)現(xiàn)方法[J]. 軟件學報, 2010, 21(2): 388-400.PAN J, XU F, LV J. Reputation-based recommender discovery approach for service selection[J]. Journal of Software, 2010, 21(2):388-400.

[12] DAI G, WANG Y. Trust-aware component service selection algorithm in service composition[A]. 2009 International Conference on Frontier of Computer Science and Technology[C]. 2009.613-618.

[13] 徐萌. 基于服務關系的服務組合相關技術研究[D].北京：北京郵電大學, 2007.XU M. Research on Service Relationship based Web Services Composition and Related Technology[D]. Beijing: Beijing University of Posts and Telecommunications, 2007.

[14] 葉世陽, 魏峻, 李磊等. 支持服務關聯(lián)的組合服務選擇方法研究[J].計算機學報. 2008, 31(8): 1383-1397.YE S Y, WEI J, LI L, et al. Service correlation aware service selection for composite service[J]. Chinese Journal of Computers, 2008, 31(8):1383-1397.

[15] 李素粉. SOBE環(huán)境下支持信任和服務關聯(lián)的服務選擇方法[D]. 北京: 清華大學, 2011.LI S F. A Trust and Service Relation Aware Approach to Services Selection under SOBE Environments[D]. Beijing: Tsinghua University,2010.

[16] [EB/OL]. http://aws.amazon.com.

[17] 張躍, 鄒壽平, 宿分. 模糊數(shù)學方法及其應用[M]. 北京: 煤炭工業(yè)出版社, 1992.ZHANG Y, ZOU S P, SU F. Fuzzy Mathematics and its Application[M]. Beijing: Ching Coal Industry Publishing House, 1992.

[18] 姜峰.基于關系的服務資源管理關鍵技術研究[D]. 北京: 清華大學,2009.JIANG F. Research on Key Technologies of Relation-Based Service Resource Management[D]. Beijing: Tsinghua University, 2009.

[19] GAREY M, JOHNSON D. Computers and Intractability: A Guide to the Theory of NP-Completeness[M]. New York: W.H.Freeman and Company, 1979.