用戶QoS需求導向的服務演化選擇策略

楊真諦 秦江龍,2 李 彤,2* 韓 煦 藏傳宇 陳長賡

1(云南大學軟件學院 云南 昆明 650091) 2(云南省軟件工程重點實驗室 云南 昆明 650091)

用戶QoS需求導向的服務演化選擇策略

楊真諦1秦江龍1,2李 彤1,2*韓 煦1藏傳宇1陳長賡1

1(云南大學軟件學院 云南 昆明 650091)2(云南省軟件工程重點實驗室 云南 昆明 650091)

服務型軟件以其特有的優點被廣泛應用，而面向QoS服務選擇問題的解決能更有效地推動服務的普及。組合服務的演化性要求在服務發生演化時，從具有相同功能的候選服務中選擇滿足用戶QoS需求的候選服務。為了在滿足用戶QoS需求的情況下選擇最優的服務，基于遺傳算法，提出一種用戶QoS需求導向的服務演化選擇策略。通過淘汰不滿足用戶QoS需求的候選服務，快速排除不符合需求的服務，并最終選擇符合用戶QoS需求的服務組合。實驗結果表明，用戶QoS需求導向的服務演化選擇策略能夠較優和較快地解決服務組合選擇問題，并保證用戶QoS需求，為服務選擇提供一種新的方法和思路。

QoS 服務組合 用戶QoS需求 遺傳算法 服務選擇

0 引 言

隨著互聯網的發展，以及軟件即服務模式的流行，互聯網服務在教育、商務、企業等不同的領域發揮著不可替代的作用，服務的概念深入人心。一方面，由于服務可能是以不同的方式創建、不同程序語言實現、由不同的供應商提供的，服務的請求需要根據特定的應用背景和需求進行合理的服務組合；另一方面，由于服務組件或基本服務不可能很復雜[1]，不能滿足現代企業多樣性的應用需求，因此組合服務應運而生[2]。

構造性和演化性是軟件的兩個基本特性[3]。服務軟件也是如此，組合服務也具有演化性。組合服務演化時，應該從候選服務集中選擇出滿足用戶功能性和非功能性需求的候選服務來對組合服務進行演化。服務質量QoS是描述服務非功能性屬性的主要評價標準，同時基于QoS的服務選擇在服務組合中扮演著相當重要的角色[4-5]。在互聯網中，提供相同功能的服務越來越多，但這些服務的QoS值并不相同。與此同時，用戶對服務進行演化時的服務QoS要求更為嚴格。因此，在服務演化時，根據服務的QoS屬性來選擇滿足用戶QoS需求的服務策略顯得尤為重要。

本文通過服務的QoS模型，將服務演化時面向QoS服務選擇的問題轉化為求解用戶QoS需求導向，多元非線性目標函數組合優化問題，提出了用戶QoS需求導向的遺傳算法GALUR(Genetic Algorithm Led by User Requirements)。在服務演化時，以用戶QoS需求為導向，引入用戶QoS需求向量來計算個體適應度，利用用戶QoS需求淘汰不滿足用戶需求的候選服務，從而快速地排除不符合要求的個體，并且能夠較快地跳出局部最優解，使種群朝著滿足用戶的需求方向進化，最終選擇出符合用戶QoS需求的服務組合。

1 相關研究

基于QoS的服務選擇是一個NP難問題[6]，而遺傳算法可以有效地解決這類問題[7]。解決此問題的方案有很多，例如文獻[8]中提出運用關系矩陣編碼方式，克服了一維編碼方式表示的局限性；文獻[9]描述定義了組合服務并且提出利用遺傳算法來解決服務組合問題；文獻[10]中提出了一種變異策略，在種群變異階段提出了自適應變異算子，保證了算法的收斂性；文獻[11]中提出了一種數據預處理方法，先為每個抽象服務優選出若干候選服務以減少解空間規模；文獻[12]中提出了變權QoS參數，即動態調整變權因子、交叉和變異因子來解決此問題；文獻[13]中提出一種遺傳算法和果蠅優化算法相結合的方法來解決云平臺上的服務組合問題，在選擇個體時，提出了一種新的方法，考慮個體間的多樣性來防止過早地收斂和跳出局部最優解，利用果蠅優化算法防止在進化過程中丟失具有潛力的個體；文獻[14]中提出一種遺傳算法和啟發式算法結合的方法來解決服務組合問題，引入的啟發式算法能夠有效地跳出局部最優解。但在組合服務演化時，這些方案均忽視了用戶QoS需求在服務選擇中的意義，不能夠直接在候選服務層面體現用戶QoS需求，不能夠完全地按照用戶QoS需求來選擇服務，完成服務演化。

因此，本文將提出一種新的選擇服務思路，充分重視用戶QoS需求在服務演化選擇時的作用，在候選服務的適應度和選擇上體現用戶的QoS需求，提出了一種在服務演化時，以用戶QoS需求為導向的服務選擇策略。

2 服務QoS模型

2.1 服務QoS模型

文獻[9]對服務QoS的描述如下：

設一個組合服務S需要完成n個功能F，如式(1)所示。若每個功能由一個子服務完成，即S由n個子服務ss組合完成，其中，每個子服務ss具有m個QoS屬性。

S= (F1,F2,…,Fn)T=(ss1,ss2,…,ssn)T=

(1)

其中：qij表示第i個子服務的第j個QoS屬性值。

本文將涉及到5個QoS屬性，故m取值為5。

2.2 QoS屬性

本文借鑒文獻[15]中的QoS模型，從執行價格、執行期間、聲望、成功率和可用性五個方面對服務的QoS屬性進行評價，五個QoS屬性定義如下：

執行價格：服務每次執行時需要的成本，成本記為qpr；

執行期間：表示請求服務至收到服務結果的時間段，由服務處理請求時間Tprocess和請求與結果傳輸時間Ttrans組成，執行期間記為qdu，則qdu=Tprocess+Ttrans；

2.3 QoS屬性組合

表1 服務組合QoS屬性組合函數表

2.4 QoS屬性歸一化

通過表1計算得出的QoS屬性值具有不同的量綱和取值范圍，不能有效地統一評價服務，因此，需要對不同的QoS屬性進行歸一化處理，將取值范圍不同的QoS屬性值轉化成無量綱并且范圍都在[0,1]之間的值。有些QoS屬性取值越小，表示服務性能越高，屬于成本型屬性，例如執行價格和執行期間；有些QoS屬性取值越大，表示服務評價越高，屬于效益型屬性，例如聲望、成功率和可用性。因此，將兩種屬性分為兩個公式對其歸一化，成本型屬性用式(2)歸一化，效益型屬性用式(3)歸一化。

(2)

(3)

2.5 QoS屬性權重

2.6 用戶QoS需求

不同用戶對服務有不同的非功能性需求，即QoS需求。為了使組合服務演化后得到的結果嚴格地符合用戶QoS需求，演化向著用戶QoS需求的方向進行。定義用戶需求向量R=(r1,r2,…,rm)，其中rj∈[0,1]，rj根據用戶提出的需求，進行歸一化處理得出。

3 用戶QoS需求導向的服務選擇策略

通過對組合服務候選服務的QoS屬性評估與建立模型，將候選服務進行順序、選擇和并行組合。在服務演化時，以用戶QoS需求為導向，引入用戶QoS需求向量來計算個體適應度，利用用戶QoS需求淘汰不滿足用戶需求的候選服務，從而快速地排除不符合要求的個體，并且能夠較快地跳出局部最優解，使種群朝著滿足用戶的需求方向進化，最終選擇出符合用戶QoS需求的服務組合。

3.1 適應度函數設計

陳小華：小的個體戶活起來還可以，只要對客戶要求不大就永遠踩不死。一些垂直的領域也有機會，比如綠植全國第一、沙發保養全國第一，然后和一些平臺進行合作，但如果說在平臺層面，已經基本沒有創業機會了。

一般適應度函數只能夠單一體現個體在環境中的適應度值，不能夠體現用戶QoS需求與個體的關系。遺傳算法是根據生物進化理論和遺傳變異理論提出的一種算法，其主要思想是通過不斷地進化，淘汰適應度低的個體，使適應度高的個體存活。根據遺傳算法的思想，引入用戶QoS需求向量設計適應度函數。

定義式(4)為適應度函數。在計算候選服務的QoS屬性值之前，定義式(5)，利用示性函數表示候選服務的QoS屬性是否滿足用戶的需求，只有當候選服務的每一個QoS屬性滿足用戶QoS需求時，示性函數為1，其他情況則為0。對滿足需求的候選服務計算其加權后的QoS屬性值，再將每個候選服務的QoS屬性值按照順序、選擇和并行結構的相應計算公式計算，得到組合服務S的適應度函數值。這樣就能夠將用戶QoS需求體現到每一個候選服務的適應度計算中，不符合用戶QoS需求的個體則會表現出低適應度，在選擇時被淘汰，滿足需求的個體繼續存活，使種群朝著滿足用戶QoS需求方向進化。

(4)

(5)

3.2 選擇函數設計

一般的選擇函數只是負責從群體中選擇出具有最高適應度的個體，沒有將用戶QoS需求引入選擇過程，不能夠在選擇中體現用戶QoS需求。為改進這一問題，在選擇函數中將用戶需求與輪盤賭選擇法相結合，采用用戶QoS需求導向的輪盤賭選擇法，即每個個體被選擇概率由個體的適應度與當代所有滿足用戶QoS需求個體的適應度共同決定。定義式(6)為個體被選擇概率函數。

(6)

由于引入了用戶的QoS需求，因此在選擇的時候，能夠快速地將不滿足用戶QoS需求的個體淘汰，滿足需求的個體繼續存活到下一代，使種群朝著滿足用戶QoS需求方向進化。

3.3 編碼方式

采用二進制編碼方式，將能夠完成相同功能F對應的具有不同QoS屬性的子服務ss的唯一標識用二進制的方式進行編碼。功能Fn的候選子服務集合記為Fn_CS={ss1,ss2,…,ssn}，其中，ss1的唯一標識為1，故可編碼為0000 0001；ss2的唯一標識為2，故可編碼為0000 0010；以此類推。因此，如果服務S需要完成兩個功能，并且每個功能選擇了標識為1的候選子服務進行組合，則S對應的二進制編碼為：0000 0001, 0000 0001。

3.4 變異與交叉

變異和交叉能夠增大種群的隨機多樣性，使種群能夠向更多方向進化，從而得到不同適應度的解。變異方法選擇隨機位置變異，利用變異率與種群大小來決定變異個體的數量，確定變異個體后，隨機選擇基因位來進行變異。交叉方法選擇兩點交叉，交叉率與種群大小決定通過交叉取代種群個體的數量，然后隨機選擇兩個位置進行交叉。

4 實驗結果及分析

為了檢驗用戶需求導向的服務演化選擇策略的有效性，將該方法(GALUR)與傳統的沒有用戶需求導向的遺傳算法在不同結構組合的情況下分別進行實驗，對解集的適應度和算法執行時間進行對比和分析。無論哪種仿真對比，都采用相同的軟硬件環境，即中央處理器為酷睿 I7-2.4 GHz，內存8 GB，操作系統為Windows 10，開發語言為Java，IDE為IntelliJ IDEA2016.2的實驗環境；所有實驗的運行數據采用相同數據，并且多次測量取平均值。由于本文只涉及了5種QoS屬性值，因此，為每個候選子服務隨機生成在一定范圍內取值的五個不同的屬性值；為了消除不同權重對結果的影響，取每個QoS屬性權重相同，即W=(0.2,0.2,0.2,0.2,0.2)；為了消除不同用戶QoS需求對結果的影響，取每個用戶QoS需求相同，即R=(0.5,0.5,0.5,0.5,0.5)；初始種群數為10；變異率和交叉率為0.5。

4.1 順序結構組合下的適應度和執行時間對比

當子服務順序結構組合時，可以從圖1中看出，GALUR策略選擇的解均優于傳統策略選擇出的解，并且隨著進化代數的增長，兩者選出解的適應度也在增長。但傳統策略在10 000代的時候收斂于一個比較低的適應度，并且不能夠跳出局部最優解，而采用GALUR策略得到適應度隨著進化代數的增長呈遞增趨勢，能夠得到一個較優的解。由圖2可知，GALUR策略執行時間一直低于傳統的選擇策略。

圖1 順序結構適應度比較圖

圖2 順序結構執行時間比較圖

4.2 選擇結構組合下的適應度和執行時間對比

當子服務選擇結構組合時，可以從圖3中看出，GALUR策略在第1 000代時選擇出的解劣于傳統策略的解，但是隨著進化代數的增加，適應度的增長比傳統策略更加迅速，在第4 000代到第6 000代的時候，GALUR收斂到一個適應度，過了第6 000代后，傳統策略也開始收斂。而GALUR策略經過2 000代的進化，成功地跳出了之前收斂到的局部最優解并繼續增長，9 000代后收斂到一個比傳統策略更優的解，傳統策略經過4 000代進化并沒有跳出局部最優解。并且由圖4可知，GALUR策略執行時間一直低于傳統的選擇策略。

圖3 選擇結構適應度比較圖

圖4 選擇結構執行時間比較圖

4.3 并行結構組合下的適應度和執行時間對比

當子服務并行結構組合時，可以從圖5中得出GALUR策略在第1 000代的時候得到的解比傳統策略得到的適應度低。但隨后逐漸上升，從第2 000代開始，適應度相近，傳統策略在4 000代開始平穩，經過3 000代進化以后跳出局部最優解，適應度有小幅度提升，然后開始收斂。而GALUR策略第6 000代進入平穩階段，經過1 000代的進化，適應度開始提升，在第8 000代開始收斂。由此看來GALUR策略得到的解要優于傳統策略得到的解，同時由圖6可知，GALUR策略執行時間一直低于傳統的選擇策略。

圖5 并行結構適應度比較圖

圖6 并行結構執行時間比較圖

4.4 實驗結果分析

通過三組實驗，我們將從兩個方面來分析這兩種選擇策略。

在適應度方面來看，GALUR策略在子服務順序組合時得到的適應度一直高于傳統的策略。在選擇和并行組合時得到的適應度，雖然前期與傳統策略得到的適應度相近，但最后GALUR策略能夠收斂到優于傳統策略的解。從圖中可以看出，傳統策略低于GALUR策略是因為傳統策略不能迅速地跳出局部最優解，而GALUR策略在計算個體適應度時，引入了用戶QoS需求作為導向，淘汰不滿足需求的候選服務，能夠快速地跳出局部最優解，得到更好的個體。

在執行時間方面來看，GALUR策略引入用戶QoS需求作為導向，逐代快速地淘汰不滿足需求的子服務，減少了每代需要考慮的候選服務數量，有效地降低算法執行的時間。

通過三組實驗得到結論，GALUR選擇策略在順序、選擇和并行結構組合中得到的適應度較高，同時花費的時間較短，因此，GALUR選擇策略能夠較優和較快地解決服務組合選擇問題。

5 結 語

隨著軟件即服務模式的流行，服務型軟件以其特有的優點被廣泛應用，而面向QoS服務選擇問題的有效解決能更有效推動服務的普及，使服務由一種技術轉化為真正可以為人們使用的工具。人們提出許多方案來解決基于QoS的服務選擇問題，其中基于遺傳算法的解決方案是一種新穎的全局優化解決方案[6,17]。在組合服務演化時，這些策略幾乎都忽視了用戶QoS需求，只能選擇出適應度最高的候選服務，并不能夠得到滿足用戶QoS需求的候選服務。還有一些策略，雖然考慮了用戶需求，但只是在最終組合以后考慮到用戶的需求，并沒有將用戶需求滲入到候選服務層面，不能夠完全體現用戶的QoS需求。在深入研究服務組合和遺傳算法的基礎上，本文提出了一種用戶QoS需求導向的服務演化選擇策略，為服務選擇策略提供了一種新的方法和思路。該算法采用二進制編碼方式，并在個體適應度的計算和選擇中，引入用戶需求向量，在進化的過程中，能夠快速地淘汰不滿足需求的候選服務。在組合服務演化時，考慮了用戶的非功能性需求，使服務選擇能充分的反映用戶QoS需求，提高了服務在演化時選擇的質量和效率，為服務選擇提供了一種新的方法和思路。

[1] 岳昆,王曉玲,周傲英.Web服務核心支撐技術:研究綜述[J].軟件學報,2004,15(3):428-442.

[2] Chen M,Wang Z.An Approach for Web Services Composition Based on QoS and Discrete Particle Swarm Optimization[C]//Eighth Acis International Conference on Software Engineering,Artificial Intelligence,Networking,and Parallel/distributed Computing,2007:37-41.

[3] 楊芙清.軟件工程技術發展思索[J].軟件學報,2005,16(1):1-7.

[4] Menasce D A.QoS issues in Web services[J].Internet Computing IEEE,2002,6(6):72-75.

[5] Menasce D A.Composing Web services:a QoS view [J].IEEE Internet Computing,2004,8(6):88-90.

[6] Canfora G,Dipenta M,Esposito R,et al.A lightweight approach for QoS-aware service composition[C]//Proceedings of the 2nd International Conference on Service Oriented Computing.New York,2004:232-239.

[7] Rojas I,Gonzalez J,Pomares H,et al.Statistical analysis of the main parameters involved in the design of a genetic algorithm[J].IEEE Transactions on Systems Man & Cybernetics Part C,2002,32(1):31-37.

[8] 張成文,蘇森,陳俊亮.基于遺傳算法的QoS感知的Web服務選擇[J].計算機學報,2006,29(7):1029-1037.

[9] 毛一梅,樂嘉錦.基于遺傳算法的Web服務組合優化[J].計算機應用與軟件,2008,25(11):199-201.

[10] 董元元,倪宏,鄧浩江,等.QoS全局最優化的服務選擇策略[J].小型微型計算機系統,2011,32(3):455-459.

[11] 葉恒舟,關云慧.基于局部選擇和遺傳算法的QoS感知的服務組合方法[J].小型微型計算機系統,2016,37(7):1389-1392.

[12] 吳青林,周天宏.基于服務質量的動態Web服務組合方法研究[J].計算機應用與軟件,2016,33(5):20-23.

[13] Seghir F,Khababa A.A hybrid approach using genetic and fruit fly optimization algorithms for QoS-aware cloud service composition[J].Journal of Intelligent Manufacturing,2016:1-20.

[14] Shahrokh P,Safi-Esfahani F.QoS-based web service composition applying an improved genetic algorithm (IGA) method[J].International Journal of Enterprise Information Systems,2016,12(3):60-77.

[15] Zeng L,Benatallah B,Ngu A H H,et al.QoS-aware middleware for Web services composition[J].IEEE Transactions on Software Engineering,2004,30(5):311-327.

[16] Saaty T L.Analytic hierarchy process[M]//Encyclopedia of Biostatistics,2001:19-28.

[17] Zhang L J,Li B,Chao T,et al.On demand Web services-based business process composition[C]//IEEE International Conference on Systems,Man and Cybernetics.IEEE,2003,4:4057-4064.

ASTRATEGYFORSERVICESELECTIONINTHEEVOLUTIONOFSERVICESBASEDONQOSUSERREQUIREMENT

Yang Zhendi1Qin Jianglong1,2Li Tong1,2*Han Xü1Zang Chuanyu1Chen Changgeng1

1(CollegeofSoftware,YunnanUniversity,Kunming650091,Yunnan,China)2(KeyLaboratoryforSoftwareEngineeringofYunnanProvince,Kunming650091,Yunnan,China)

The widely use of service software with its unique advantages has promoted through the effective solution of QoS service selection problem. The evolution of composition services requires that select the candidate services which meet the user QoS requirement from the set of the same functional services during the evolution. In order to satisfy the user’s QoS requirement and select the optimal services, we propose a user QoS requirement oriented service evolution selection strategy based on genetic algorithm. By eliminating candidate services that do not meet user QoS requirements and quickly excluding services that do not meet requirements, a service portfolio that meets the user’s QoS needs is ultimately selected. The experimental results show that the user QoS demand oriented service evolution selection strategy can solve the problem of service composition selection better and faster, and guarantee the user’s QoS requirement. It provides a new method and thinking for service selection.

QoS Services composition User QoS requirement Genetic algorithm Service selection

2016-12-21。國家自然科學基金項目(61379032)。楊真諦，碩士，主研領域：軟件工程，軟件演化，軟件過程。秦江龍，教授。李彤，教授。韓煦，碩士。藏傳宇，碩士。陳長賡，碩士。

TP3

A

10.3969/j.issn.1000-386x.2017.12.016