普適計算中一種最優服務選擇算法的設計與仿真

(1.湘潭大學 信息工程學院， 湖南 湘潭 411105; 2.中國科學院 計算技術研究所 普適計算中心， 北京 100080)

摘 要:詳細分析了服務選擇問題及其求解目標，綜合服務提供方高效率低成本和終端用戶方的服務質量(QoS)等目標約束條件，提出一種多目標約束的最優服務選擇遺傳算法。該算法采用矩陣描述服務提供方、服務、終端用戶三者之間的關系，并采用矩陣編碼方式，將矩陣視為染色體個體，將矩陣的列視為染色體基因。仿真實驗結果表明，該算法具有較好的收斂性和穩定的尋優能力。

關鍵詞:服務選擇; 遺傳算法; 矩陣編碼方式; 多目標約束

中圖分類號:TP18文獻標志碼:A

文章編號:1001-3695(2010)03-0899-05

doi:10.3969/j.issn.1001-3695.2010.03.025

Design and simulation of optimum service selectionarithmetic in pervasive computing

LIU Wei1， ZHU Zhen-min2， JIANG Fa-qun2， YE Jian2， SU Xiao-li2

(1.College of Information Engineering， Xiangtan University， Xiangtan Hunan 411105， China; 2.Research Center for Pervasive Computing， Institute of Computing Technology， Chinese Academy of Sciences， Beijing 100080， China)

Abstract:After analyzing the essence of service selection，this paper proposed an optimum service selection genetic algorithm with multi-objective constraints. The algorithm included a matrix-coding scheme of chromosomes that expressed the relationship between service providers， services and end-users.Constructed special crossover and mutation operations based on matrix-co-ding， and could ensure both operations the new chromosomes were feasible. Simulation results show that this algorithm can obtain the optimal solutions of the test problem instances efficiently and steadily.

Key words:service selection; genetic algorithm; matrix-coding scheme; multi-objective constraints

普適計算[1，2]的特點是用戶能隨時隨地獲得透明的應用服務，這要求實現應用服務的無縫遷移。具體方式是通過簡化移動設備，把復雜計算通過網絡遷移到周圍強大的服務器上，使簡化的移動設備與服務器協同合作，達到用戶能隨時隨地方便接收服務的目的。服務的遷移意味著任務分工更加明確，更多的計算資源得到共享，同時節約了計算成本。因此隨著網絡和普適計算技術的迅速發展，這種應用方式將會越來越普遍。服務選擇的研究就是為了解決服務提供方與移動設備用戶之間如何協作和匹配的問題。由于普適計算環境的特殊性，需要系統能根據用戶的移動性、設備的資源受限性、服務的靈活性、網絡環境的多樣性等特點，從多個服務方提供的眾多服務中選擇最優的服務組合，形成最符合用戶需求的目標服務，實現按需計算的個性化計算環境。

 目前，對于服務選擇問題，國內外的研究者都提出了一些有效的方法和模型結構，如移動agent[3]、DIANE[4]、Jini[5]等。其中對服務選擇的目標約束也進行了廣泛的討論和分析，大多數討論集中在Web領域的服務質量約束，如文獻[6]歸納了Web領域現已提出的QoS需要包含的所有屬性。本文認為服務選擇問題的目標約束應包括兩個方面:a)服務提供方，需要達到服務提供者發布服務的高效率低成本目標;b)用戶請求方，需要最大程度滿足用戶的請求，并最大程度保證請求服務的QoS目標。本文的主要貢獻在于分析并描述服務選擇問題及其多個目標約束條件，設計實現了一種多目標約束的服務選擇遺傳算法，并對該算法進行了仿真實驗分析。

1 服務選擇問題及多目標約束分析

1.1 服務選擇問題分析

服務選擇是一個復雜的多對多的選擇問題，如圖1所示。

其中:P代表服務提供者;S代表服務提供者發布的服務;U代表終端用戶;A代表終端用戶發出的服務請求。假定有n個服務提供者和h個用戶，每個服務提供者發布1～m個服務程序，每個用戶向服務提供者請求1～k個應用服務程序，服務選擇問題變成如何從n×m個服務中選擇h×k個服務，要求每個用戶選擇的服務序列都是滿足目標約束的最優序列，且每個序列中不能有重復的服務。其中，每個服務提供者發布的服務類型和服務個數可能不相同，用戶請求的服務類型和服務個數也可能不相同。

本文提出采用矩陣來表示服務提供方、服務與終端用戶三者之間的關系。假定n個服務提供者{P1，P2，P3，…，Pn｝共發布m個不同類型的應用服務{S1，S2，S3，…，Sm｝。其中每個服務提供者可以發布多個應用服務Si(1≤i≤m)，每個應用服務Si(1≤i≤m)也可以由多個服務提供者提供。服務提供方與服務之間的關系可以用n×m的P矩陣表示如下:

P=-1-10…000-1…0

0-10…0 -10-1…-1

(1)

其中:P矩陣的值由{-1，0｝組成。Pij的值為“0”表示對應行的服務提供者Pi發布了對應列的應用服務Sj，值為“-1”則表示對應行的服務提供者Pi未發布對應列的應用服務Sj。

 假定h個用戶{U1，U2，U3，…，Uh｝共提出k個不同類型的服務請求{A1，A2，A3，…，Ak｝。其中每個用戶可以請求多個應用服務Ai(1≤i≤k)，多個用戶也可以提出同一類型的請求Ai(1≤i≤k)。用戶與請求服務之間的關系可以用h×k的U矩陣表示如下:

U=

111…1001…0

110…1 101…1

(2)

其中:U矩陣的值由{0，1｝組成。Uij的值為“1”表示對應行用戶Ui請求對應列的應用服務Aj，值為“0”則表示對應行的Ui未請求對應列的應用服務Aj。

 U矩陣中的服務請求{A1，A2，A3，…，Ak｝和P矩陣中的應用程序{S1，S2，S3，…，Sm｝應屬于如下包含關系:

{A1，A2，A3，…，Ak}{S1，S2，S3，…，Sm}(3)

結合P矩陣和U矩陣，本文用一個n×m的R矩陣表示服務提供者與響應用戶請求服務之間的關系如下:

R=

-1-11…113-1…3

2-12…0 -11-1…-1

(4)

其中:R矩陣的值由整數{-1，0，1，…，x｝組成。Rij的值為“-1”表示對應行的服務提供者Pi未發布對應列的應用服務Sj，值為“0”~“x”表示對應行的服務提供者Pi發布了對應列的應用服務Sj，值的大小表示Pi發布的Sj服務響應用戶請求的個數，并且Sj響應用戶請求的總個數應等于各用戶對Sj請求次數的總和，即該列的所有正整數之和應等于矩陣中對應服務所在列的值之和。

 從上面對服務選擇問題的分析可以看出，求解服務選擇的最優解即求解一定目標條件下的最優R矩陣。其中，P矩陣、U矩陣和關系式(3)為約束條件。

1.2 服務選擇的目標約束分析

本文認為服務選擇的目標約束應從兩個方面考慮:a)服務提供方，需要達到多服務提供者發布服務的高效率低成本目標;b)用戶請求方，需要最大程度滿足用戶的請求，并最大程度保證請求服務的QoS目標。

 1)高效率低成本目標約束

服務提供方的目標主要是保證高運行效率和低運行代價等。本文將服務提供方的負載均衡作為衡量高效率低成本的目標參數。關于負載均衡的研究已經有很多，可借鑒已有的負載均衡研究成果和技術方案。

 本文采用系統資源利用率作為負載指標，最常使用的資源利用率負載指標有CPU、內存等。本文根據CPU和內存的負載，設計服務節點負載公式如下:

load=1loadc≥1orloadm≥1

wc×loadc+wm×loadm其他(5)

其中:loadc表示服務節點在t0時間內的平均CPU負載;loadm表示服務節點在t0時間內的平均內存負載;wc和wm分別為CPU和內存的權值(0≤wc，wm≤1且wc+wm=1)。由于CPU和內存是動態變化的，在某一時刻的值并不能客觀地反映CPU和內存的負載狀態，取它們在一段時間t0內的平均值，如取t0=15 s。Load的數值越小，表示服務提供者的負載越小，當loadc和loadm任意一個值大于或等于1時，load的值為1，表示服務提供者已經滿負荷運行，或者進程阻塞故障，導致系統無法再運行其他應用程序。

多服務器負載均衡的目標要求每臺服務器的負載盡量接近平均負載，本文引入平均差的計算方法。平均差也稱為平均離差，是各個數據值與其平均值的離差絕對值的平均數，用A.D.表示。平均差反映的是各標志值對其平均數的平均差異程度。因此，求解負載平衡的目標即求解負載平均差的最小值，設計求解公式如下:

loadbal=min{A.D.}=min∑ni=1|load(i)-loadave|/n(6)

2)QoS目標約束

不同的用戶對請求服務的QoS要求可能不一樣，有的用戶希望服務能有較快的執行速度，有的用戶希望能有較便宜的價格等。目前，不同的標準和研究組織對服務質量的認識有一定的差別，文獻[6]歸納了Web領域現已提出的QoS需要包含的所有屬性。參考國際標準ISO 8402[7]對QoS的定義，本文認為QoS應由下面一些屬性組成:服務的價格(cost)、服務的執行時間(time)、服務的可用性(availability)、服務的健壯性(robustness)和安全性(security)。通過這些QoS屬性反映用戶的需求和對服務的滿意度。

 在服務選擇過程中，用戶同時請求的多個服務構成了一個服務組合，該組合的總體QoS參數應由單個服務的QoS來計算。其中，總價格和總執行時間應是各單個因子的總和，服務越多，總價格和總執行時間就越多，如式(7)所示。

C(s)=∑niC(i)，T(s)=∑ni=1T(i)(7)

可用性、健壯性和安全性應是各因子系數比例的乘積，總可用性、總健壯性和總安全性則隨著服務的增多系數反而降低，如式(8)所示。

A(s)=∏ni=1A(i)，R(s)=∏ni=1R(i)，S(s)=∏ni=1S(i)(8)

2 多目標約束的最優服務選擇遺傳算法

服務選擇算法的好壞直接影響到服務匹配和調度的優劣，文獻[8]對目前各種調度算法進行了詳細的分析和研究，并對各算法進行了仿真比較。在靜態調度算法中，遺傳算法[9](genetic algorithm，GA)具有非常好的表現。服務選擇的難點在于多服務提供者提供的多個服務與多個用戶同時提出多個服務請求之間的選擇與匹配，要求同時滿足服務提供方的高效率低成本要求及用戶方的QoS最優等多個目標約束條件。本文設計了一種多目標約束的最優服務選擇遺傳算法，下面將詳細介紹設計方案。

2.1 染色體編碼

本文設計的遺傳算法采用矩陣編碼方式，將矩陣視為一個染色體個體，將矩陣的列視為染色體的一個遺傳基因。設計矩陣染色體個體如下:

g11g12g13…g1mg21g22g23…g2mg31g32g33…g3m gn1gn2gn3…gnm(9)

矩陣的值由整數{-1，0，1，…，x｝組成。編碼確定后，初始群體根據約束條件在一定范圍內隨機產生。

2.2 適應度函數設計

適應度函數是遺傳算法求解的關鍵，個體的選擇是根據染色體適應度值的優劣程度，因此染色體的適應度值越大，個體被選擇的幾率就會越大。

 由于服務選擇的目標約束從兩個方面考慮，本文使用兩個適應度函數f1，f2。其中: f1從服務提供方計算染色體個體是否滿足服務提供方高效率低成本的目標要求，即求解服務提供方的負載均衡參數; f2則從用戶方計算染色體個體是否滿足服務的QoS要求。假定服務的QoS由r個QoS屬性來刻畫，即{Q1，Q2，…，Qr｝，設計f1和f2求解公式如下:

f1=Loadbal(10)

f2=∑ri=1(wi×Qi)(11)

其中:0≤wi≤1，∑ri=1wi=1。在f1中，求最大的適應度函數即為求函數的最小值，本文將該適應度函數作一個轉換:f′1=1-f1，轉換為求函數f′1的最大值。綜合這兩個適應度函數的求解，本文設計一個求解多目標約束的總適應度函數公式如下:

f=wL×f′1+wQ×f2(12)

其中:0≤wL，wQ≤1，wL+wQ=1;wL為適應度函數f′1的權值;wQ為適應度函數f2的權值。

2.3 進化操作

進化操作算子主要有三個，即選擇(selection)、交叉(crossover)和變異(mutation)。

選擇操作是根據個體適應度值的優劣程度決定它在下一代是被淘汰還是被遺傳。一般來說，選擇將使適應度較大(優良)個體有較大的存在機會，而適應度較小(低劣)的個體繼續存在的機會也較小，最通常的實現方法是輪盤賭(roulette wheel)模型。假設群體中有n個染色體，f(xi)表示種群中第i個染色體xi的適應度值，則f(xi)產生后代的能力為其適應度值所占份額如下:

f(xi)/∑ni=1f(xi)(13)

交叉操作是將被選擇出的兩個個體P1和P2作為父母個體，將兩者的部分碼值按概率pc進行交換，生成兩個新的個體。本文的遺傳算法以矩陣的列作為一個基因，因此交叉操作將矩陣的列作為單元進行交換，如下所示。

變異操作是改變群體中個體串的某些基因位置的基因值。在本文中，變異操作和交叉操作一樣，是以矩陣的一個列為單位進行變異，如下所示。其中，選擇和變異都需要滿足矩陣的約束條件。

2.4 算法流程

綜合2.1～2.3節的內容，算法的染色體群體進化流程如圖2所示。首先產生初始染色體群體并對該群體計算每個個體的適應度值，然后通過判定條件進入循環。每一次循環都依次進行一次選擇、交叉、變異操作，從而產生新的群體，計算新群體的個體適應度函數，查找最優個體，循環終止直至滿足終止條件。

3 仿真實驗

3.1 仿真設計與結果

筆者對算法進行了尋優能力的仿真對比和尋優穩定性的仿真對比，所有仿真實驗均在相同的軟硬件環境下進行。CPU為Intel Pentium 4 1.60 GHz，內存為512 MB，操作系統為Windows XP，程序編碼為標準C，在Visual Studio

.NET 2003編譯器下通過。

3.1.1 尋優能力仿真分析

1)離線特征比較

DeJong提出離線特性用于說明算法的收斂性，是目前遺傳算法中比較公認的性能指標之一。其計算公式如下:

x(t)=1t∑ti=1fe(i)(14)

其中:fe(i)是第i代最好個體的目標函數值;x(t)表示至第t代每次最好目標函數值的平均。離線特性考慮最優點的進化趨勢，用于說明算法的收斂性。

本文對比1、3、10、20個用戶同時進行服務選擇的離線特性，運行條件為交叉率0.55，變異率0.1，服務提供者與提供的服務關系P矩陣的值如下:

P=0-100-100-10-1-100-10000-100-1-100-10000(15)

1、3、10、20個用戶與服務請求關系的U矩陣由系統隨機產生，每個用戶請求0～5個不定服務。表1給出了多次運行情況下最佳適應度與離線特性的對比結果。

表1 最佳適應度與離線特性對比數據表

1個用戶(群體=30)

迭代數1020406080100

最佳適應度0.62550.62550.62550.62550.62550.6255

離線特性0.62150.62350.62450.62480.62500.6251

3個用戶(群體=50)

迭代數200400800120016002000

最佳適應度0.46980.47530.47530.47530.47530.4753

離線特性0.46820.47040.47290.47370.47410.4744

10個用戶(群體=100)

迭代數50010002000300040005000

最佳適應度0.73940.73940.73940.73940.73940.7394

離線特性0.73410.73680.73810.73850.73870.7389

20個用戶(群體=150)

迭代數200040008000120001600020000

最佳適應度0.55210.55350.55350.55350.55350.5535

離線特性0.54350.54800.55070.55160.55210.5524

圖3給出了1、3、10、20個用戶在迭代數增加的情況下最佳適應度和離線特性的對比效果。

從表1和圖3可以看出，隨著迭代數的增加，1、3、10、20個用戶的離線特征曲線斜率由大到小變化，曲線漸漸趨向與最佳適應度曲線平衡，并逐步接近最佳適應度的值。這說明隨著迭代數的增加，該算法具有很好的收斂性。從1個用戶增加到20個用戶，離線特征的曲線變化趨勢接近，這說明在用戶數量增多的情況下，該算法依然具有很好的收斂性。

2)算法結果比較

在本文中，算法的適應度考慮服務提供方和終端用戶兩個方面，可通過算法執行結果來評價該算法獲得最優解的能力。本文仿真資源在不釋放的情況下服務提供方的負載情況，通過服務選擇算法的多次運行，看是否能使服務提供方達到負載平衡的目標。在此將系統資源利用率作為負載平衡的評價標準。

將f1的權值wL設置為0.9，f2的權值wQ設置為0.1。運行條件為交叉率0.55，變異率0.1，服務提供者與提供的服務關系的P矩陣的值與式(15)一致，用戶與請求的服務關系的U矩陣由系統隨機產生。仿真6個服務提供者的CPU、內存的情況，每個服務提供者提供0～5個服務，每次由1個用戶登錄選擇并訪問服務。30個用戶通過30次登錄選擇的過程中，CPU占用率、內存使用率的變化情況如表2、3所示。其中，列表示登錄次數，行表示服務提供者。

表2 CPU占用率變化數據表%

36912151821241730

P12279161621262631

P227712152020253030

P325.89.112.113.718.418.424.226.729.1

P42.87.58.313.314.916.621.624.629.629.6

P544.813.814.616.623.628.628.633.633.6

P625.78.713.116.118.124.730.735.541.5

表3 內存使用率變化數據表%

36912151821241730

P15516.718.231.431.443.154.854.866.5

P2516.716.725.232.2444455.767.467.4

P3512.617.724.728.639.639.651.956.460.9

P45.616.517.128.832.736.648.455.467.167.1

P56.57.121.722.323.836.948.748.760.460.4

P6510.417.423.430.431.941.545.949.453.8

圖4給出了各服務提供者的CPU占用率和內存使用率的變化曲線。

從表2、3的數據和圖4的曲線可以看出，隨著用戶的增加和請求服務的增多，各服務器的負載呈現平滑增長的趨勢，無較大抖動出現。各服務器的負載值近似相等，曲線斜率大小也近似相等，無兩個服務器負載相差很大的現象出現。這說明該算法能很好地滿足負載平衡的要求，具有很好的尋優能力。

3.1.2 穩定性仿真分析

本文將遺傳算法和隨機負載均衡算法進行比較，驗證算法尋優的穩定性。采用相同的仿真軟硬件環境，服務提供者與提供的服務關系的P矩陣的值與式(15)一致，用戶與請求關系的U矩陣由系統隨機產生。6個服務提供者，統計每次由1個用戶登錄選擇并訪問服務，30個用戶通過30次登錄選擇服務后對服務提供方的負載影響，將f1的權值wL設置為0.9，f2的權值wQ設置為0.1。算法連續運行10次，計算每次服務提供者的負載平均差。

平均差計算公式如下:

A.D.=∑ni=1|Xi-X|n(16)

圖5給出了本文設計的遺傳算法與隨機選擇算法的CPU占用率平均差和內存使用率平均差的對比情況。

從圖5的對比曲線可以看出，隨機負載算法的負載平均差抖動較大，而遺傳算法的曲線趨近與x軸平衡，并且曲線較平滑，說明與隨機負載算法相比，遺傳算法求解的值趨向于穩定，并且，遺傳算法的負載平均差要遠遠小于隨機負載平衡算法的負載平均差，這說明遺傳算法的解更趨向于最優解。因此，與隨機負載平衡算法相比，本文設計的遺傳算法具有非常穩定的尋優能力。

3.2 結論分析

本節分別給出了算法的尋優能力仿真分析以及尋優穩定性的仿真分析。在評價過程中，本文采用了離線指標分析、算法結果仿真分析以及與其他算法對比的分析方法，從實驗數據及結果可以發現:

a)本算法具有較好的收斂性。收斂性的好壞決定算法的優劣，本文用離線指標評價遺傳算法的收斂性。從表1的數據及圖3的對比曲線可以看出，在用戶數量逐漸增多的情況下，本算法依然具有較好的收斂性。

b)本算法能獲得近似最優解。本文通過算法的執行結果評價算法是否能獲得最優解。本文仿真在資源不釋放的情況下服務提供方的負載情況，從表2、3的數據和圖4的曲線可以看出，隨著用戶的增加和請求的增多，各服務器的負載呈現平滑增長的趨勢。這說明該算法的執行結果能很好地滿足負載平衡的要求，該算法具有獲得最優解或近似最優解的能力。

c)本算法具有穩定的尋優能力。本文將該算法與其他算法進行對比，從圖5的對比曲線可以看出，與隨機負載平衡算法相比，本文設計的遺傳算法具有穩定的尋優能力。

總的來說，本文提出的矩陣編碼方式的遺傳算法能很好地解決服務選擇問題中服務提供者與用戶服務請求的匹配問題。通過上面的仿真實驗可以證明，本文設計的遺傳算法具有很好的收斂性和穩定的尋優能力。

4 結束語

本文采用矩陣表示服務選擇問題中服務提供方、服務、用戶三者之間的關系，根據服務選擇的多個目標約束，設計并實現了一種最優服務選擇遺傳算法。該算法采用矩陣編碼設計，克服了一維編碼的局限性，有效地解決了復雜的多對多選擇關系的表示問題，并通過一次算法搜索就可以找出滿足用戶QoS要求和服務提供方效率成本要求的最優服務序列。最后通過大量的仿真數據證明，本文設計的多目標約束的遺傳算法能有效地解決服務選擇問題。通過離線特性、算法執行效果和與其他算法進行對比等方法，證明該算法具有很好的收斂性和穩定的尋優能力。

參考文獻:

[1]WEISER M. The computer for the 21st century[J]. Scientific American，1991，265(3):66-75.

[2]朱珍民， 史紅周. 網格終端與普適計算的發展趨勢[J]. 信息技術快報， 2004，2(4):14-24.

[3]CAMPO C. Service discovery in pervasive multi-agent systems[C]//Proc of AAMAS Workshop on Ubiquitous Agents on Embedded， Wearable， and Mobile Agents. 2002.

[4]KUSTER U， KONIG-RIES BIRGITTA， STERN M， et al. DIANE: an integrated approach to automated service discovery， matchmaking and composition[C]//Proc of the 16th International World Wide Web Conference. New York:ACM Press， 2007:1033-1042.

[5]SUN. Jini architecture specification[EB/OL].(2006). http://www.jini.org/wiki/Jini_Architecture_Specification.

[6]KALEPU S， KRISHNASWAMY S，LOKE S. Verity: a QoS metric for selecting Web services and providers[C]//Proc of the 4th Web Information Systems Engineering Workshop. 2003:131-139.

[7]ISO 8402， Quality management and quality assurance vocabulary[S]. Geneva:International Organization for Standardization， 1994.

[8]黃寶邊， 曾文華. 網格環境中任務調度算法的分析與比較[C]//2005年中國計算機大會論文集. 北京: 清華大學出版社， 2005.

[9]米凱利維茨 Z. 演化程序—遺傳算法和數據編碼的結合[M]. 周家駒， 何險峰，譯. 北京: 科學出版社， 2000.