模糊集下ＱｏＳ感知的網格服務優選算法
2008-12-31 00:00:00王璿孔令富
計算機應用研究 2008年7期
摘 要：在面向服務的網格應用中，支持服務質量（QoS）的服務選擇成為確保用戶QoS需求的有效方法，QoS感知的服務選擇以多個QoS參數為評價指標。考慮到服務需求描述中QoS參數的約束條件往往具有模糊性，定義了模糊目標的隸屬函數，將服務選擇問題轉換為模糊集下的多目標規劃問題，通過求解QoS參數之間的重要關系來緩解QoS需求間存在的矛盾性問題。最后提出了QoS感知的服務優選算法，對每個候選服務的整體服務質量進行排序，為用戶選擇合適的服務提供依據。
關鍵詞：網格; 服務選擇; 服務質量; 模糊集; 多目標規劃
中圖分類號：TP393．07 文獻標志碼：A
文章編號：1001-3695(2008)07-2007-03
QoSaware selection algorithm of grid services on fuzzy set
WANG Xuana，KONG Lingfua，b
(a.School of Information Science Engineering，b.Office of President， Yanshan University， Qinhuangdao Hebei 066004， China)
Abstract:The QoSaware service selection is an available method to ensure quality of service for users in serviceoriented grid application. It adopts several QoS parameters to evaluate the performance of service. During the process of service selection， the restrictive conditions of QoS usually are fuzzy. A subjection function of fuzzy targets was defined to solute this problem. The problem of service selection was translated into the multitargets programming problem on the fuzzy set. In order to release the contradictory between several QoS parameters， the weight relationship of them were calculated. According to the above parameters， a QoSaware service selection algorithm was proposed that took response time， cost， service global capability and service credit as performance metrics， and chosen the best service as target.
Key words:grid; service selection; quality of service(QoS); fuzzy set; multitargets programming
隨著網格應用的變化和對服務共享理解的深入，網格服務的功能性不再是用戶的惟一需求。用戶更關注服務所能保證的性能、服務實例完成任務的能力和效率等問題[1~3]。要在網格中找到最適合用戶需求的服務，其基本方法是從一個特定應用的角度對服務的好壞進行度量。對于一次服務發現過程中所有滿足需求約束的服務而言，存在相應的能力指標計算方法，使用戶可以根據服務能力的強弱進行排序，從而選擇等級最高的服務或服務子集。在網格應用中，服務能力主要體現在對QoS參數的度量上。在采用多個QoS參數為評價指標計算服務整體質量時，主要存在不可公度性和矛盾性的問題。一方面，網格服務的多樣性使得如何計量具體的QoS參數還沒有統一的方法，因此需要一個能反映服務整體質量的度量概念[4，5]；另一方面，用戶提出的QoS需求往往具有矛盾性。例如，用戶在提出服務請求的時候，既期望獲得最快的響應時間，又期望花費的成本最少。在這種情況下，服務選擇過程還需要考慮各QoS參數間的均衡問題。
針對以上問題，本文采用多目標規劃求解方法實現QoS感知的服務選擇。然而在服務需求描述中，QoS參數的約束條件往往具有模糊性，這給多目標規劃問題轉換成單一目標規劃問題進行問題求解帶來了一定的難度。本文提出了模糊集下QoS感知的服務優選算法并進行了實例分析。通過對QoS參數的無量綱處理和求解QoS參數的重要關系來解決多個QoS目標之間的不可公度性和矛盾性問題，通過定義模糊目標的隸屬函數求解模糊集下的多目標規劃問
題。
1 QoS參數的定義
在面向服務的網格應用中，為滿足用戶多角度的需求及優化共享，服務選擇要盡可能滿足四化原則，即成本最小化、響應時間最短化、服務性能最優化及服務存在最大化。這四方面性能的保證必須由相應的QoS參數來衡量[6，7]。服務應當具有的QoS參數是由該服務所屬領域的領域本體決定的。以網格計算應用為例，終端用戶主要關心計算服務的運行成本、計算服務的響應時間、計算服務是否達到預期效果及計算服務是否能夠有效執行等性能指標。因此，可定義四個與網格計算應用相關的基本QoS參數來描述用戶對應用的需求，它們是服務價格、服務響應時間、服務綜合性能及服務信用度。為體現一定的語義特征，在服務需求描述中采用閾值約束的形式描述QoS參數。質量閾值約束包括上限約束(maximum)和下限約束(minimum)，一個QoS參數可以兩個閾值約束都制定，也可以只定義其中一個。
1．1 服務價格和服務響應時間
服務價格QP是用來描述使用某個網格服務需支付或收取費用的QoS參數，它由服務提供者提供。隨著計算服務商業化的發展，傳統的服務交易從無償形式向付費形式轉變，因此用戶請求調用網格服務時需要考慮價格因素。QP在整個網格服務市場中遵循市場的價格規律，供求雙方均可定出自己期望的QP。
服務響應時間QT是描述服務計算能力的基本參數，指服務從開始執行到結束時所需要的時間，包括服務期望計算時間Tcom和傳輸延遲Ttran兩個部分，即QT＝Tcom＋Ttran。QT可以通過預測機制[8]獲得一個期望的參考值。在服務注冊時，將其作為基本參數記錄在服務描述文檔中，若需改變，可以定期觸發預測機制修改服務的相關注冊信息。通常，QT和QP之間不是獨立的，而是相關的。
1．2 服務綜合能力
服務綜合能力QG反映了服務對于底層各類資源的需求。通常，網格中存在多個計算節點可以提供同一類型的服務。服務發現系統根據所需服務的性能約束指派到相應的計算節點上進行計算，使其獲得令人滿意的運行性能。傳統資源性能評估機制根據節點的CPU個數、主頻、內存等硬件指標通過Benchmark測試[9]等評價方法評價其計算性能，然而在網格計算應用中，不同類型的計算對計算節點的計算性能、存儲容量、I/O速度、通信能力的需求是不一樣的。若在處理服務選擇問題時只考慮服務的計算能力需求，很容易導致所選計算節點在通信能力等其他方面的差異性很大，從而影響重建速度。
為綜合度量計算節點的處理能力，定義了一個服務綜合能力QoS參數QG，采用四個特征對其進行刻畫QG={RC，RL，RI/O，RM}。計算性能RC表示處理單位計算量所需的時間，通過計算節點的CPU個數、主頻等硬件指標通過Benchmark測試進行評價；平均通信性能RL為與節點相連的鏈路通信能力的均值;I/O傳輸速度RI/O為與該網格節點相連的傳輸速度最快的鏈路;存儲容量RM表示服務所在節點存儲磁盤空間的大小。QG中的各特征指標有不同的需求權重，特征指標權重集記為
W={w1，w2，w3，w4}(wi>0，且4i=1wi=1)(1)
QG屬于值隨服務運行動態改變的QoS參數，需要進行即時監控以獲得最新的參數信息。在監控時，對于數值變化較快的特征參數，采取計算最近一段時間之內的平均值作為特征參數值的方式。
1．3 服務信用度
網格的動態性決定了用戶對所使用服務的未知性。為了使任務能夠分配到可信任的服務上執行，降低任務執行失敗率，服務發現過程中需要使用一個評價機制對服務的信用度進行評價。服務的信用度QC針對網格服務在某一時間段內發生的交易行為所形成的全局評價，由獨立的第三方通過審計歷史數據獲得。影響服務信用度的核心因素是違約。違約是指服務代理和任務之間達成服務使用協議后，網格服務沒能按照約定提供服務的行為，如服務調用失敗、超服務響應時間、超服務成本等。
設x為服務標志，則服務信用度QC(x)為
其中:0≤QC(x)≤1;0≤α≤1;i=1，2，3，…。QC，old(x)為網格服務信用度的當前值，即上次評估的結果；QC，new(x)表示在上次評估后，產生調用記錄的信用度計算值，包括響應時間和費用兩個因子；ti0為任務的期望響應時間，ti為實際響應時間；ci0為獲取服務的預算費用值，ci為實際支付費用值。QC(x)=1表示最好的信用度，QC(x)=0表示最差的信用度。QC(x)初值由服務提供者設定，通常是服務提供者擁有服務中最小的服務信用度作為新加入服務的初值。若擁有服務的服務提供者首次加入網格系統，則通常認為新加入的服務提供者是半誠實的，因此其提供服務的信用度初值設為50%。這種假設是合理的，因為初值不能過小，以防初次欲提供計算服務的服務提供節點因信用度太低而永遠得不到計算任務，最終導致該計算節點被餓死；同時初值也不能過大，因為如果初值過大，一個節點就可能以欺騙的方式騙得一個計算任務后，再重新以一個新的身份再次騙得一個計算任務。
QC是一個隨時間變化的量。服務提供者的兩種行為可能導致其擁有服務的信用度下降，即違約行為和不作為行為。若服務調用過程中有違約行為發生，如服務響應時間超過用戶期望的響應時間，則服務信用度將會降低；或者在評價周期T內，某一服務沒有產生新的使用記錄即存在服務不作為行為，則信用度發生衰減。
其中：φ作為違約懲罰因子或衰減因子，根據其發生的違約行為或不作為行為對網格服務的當前信用度進行調整。這種調整機制使得原先信用低的服務在經歷一段時間后重新獲得執行任務的機會，使那些信用高的服務由于長時間沒有為網格提供服務而喪失其積累的信用值。通過服務信用度的評價，系統盡量選擇誠實良好和可靠的服務，從而克服了動態網格環境下服務存在的非法性和不確定性的缺點。
2 模糊集下QoS感知的服務優選模型
2．1 QoS目標的模糊隸屬度
在服務需求描述中，QoS參數給出的約束條件往往帶有模糊性，這給求解多目標規劃問題帶來了難度。若將QoS參數描述的候選服務看做模糊集，則需要實現模糊集下的多目標規劃問題。一般多個目標函數不可能同時達到最優解，因此只能求使各個目標都較滿意的模糊最優解，即模糊妥協解。模糊集合通過隸屬函數進行描述，將模糊妥協解隸屬度定義為1，其他解根據情況確定隸屬度。由于QoS參數通常有極大化或極小化兩方面的需求，將QoS參數劃分為成本型指標和效益型指標兩種形式。成本型指標期望指標值越小越好，效益型指標則期望指標值越大越好，對兩種指標形式分別采用兩種方法計算隸屬函數。相應地，為了區分QoS參數屬于效益型還是成本型，需要在服務需求描述中加入服務質量方向direction的描述。
設應用P劃分成i個子任務，每個子任務ti的候選服務集合為Sj={s1，s2，…，sk}。子任務ti的服務需求中對響應時間QT和服務信用度QC的描述為
……
〈quality〉
〈name〉responsetime〈/name〉
〈direction〉min〈/direction〉
〈maximum〉140〈/maximum〉
〈/quality〉
〈quality〉
〈name〉credit〈/name〉
〈direction〉max〈/direction〉
〈minimum〉0.8〈/minimum〉
〈maximum〉1/maximum〉
〈/quality〉
……
不難看出，對于能夠執行ti的候選服務來說，期望其響應時間不超過140 ms。響應時間的direction為min，說明響應時間越小越好，則該參數為成本型指標；期望其服務信用度至少要大于0.8，且最大值不超過1。服務信用度的direction為max，說明信用度越大越好，則該參數為效益型指標。
子任務ti的服務需求描述中對候選服務的QoS參數的上限值定義為Qmax，下限值定義為Qmin，每個候選服務中QoS參數定義為Q，成本型指標的隸屬函數為
μ:F→[0，1]
μ=(Qmax-Q)/(Qmax-Qmin)Qmin≤Q≤Qmax
0其他(4)
在式（4）中，當Q＝Qmin時，μ(T)=1；當Q=Qmax，μ(T)=0；當Qmin<Q Q 根據隸屬函數的定義，可以求解出候選服務對每個QoS參數的隸屬函數矩陣Ak×m。其中：μjl為QoS參數的隸屬函數；j為候選服務個數(1≤j≤k)；l為QoS參數個數(1≤l≤m)。 2．2 QoS參數的重要性度量 除了對QoS參數的閾值限制，用戶還要考慮不同QoS參數之間的重要度關系。QoS參數間重要度關系標志著在進行服務選擇時將優先考慮哪個質量參數的取值，它能有效地緩解參數間的矛盾性。在服務選擇時，表現為計算每個QoS參數的權重值，其求解過程為 a)設定QoS重要度矩陣Q=(qjl)k×m。其中：qjl表示第j個候選服務的第l個QoS屬性；k表示子任務ti中候選服務的個數；m表示QoS參數的個數。將Q泛化為R=(rjl)k×m。 b)對矩陣R進行歸一化處理，得到歸一化矩陣R=(rjl)k×m。其中：rjl=qjl/kj=1qjl，j∈k，l∈m。 c)計算每個QoS參數輸出的信息熵El。 El=(-1/ln k)kj=1rjlln rjl；j∈k(7) d)計算每個QoS參數的權重向量ω=(ω1，ω2，…，ωm)。 ωl =(1-El)/ml=1(1-El)(8) 3 模糊集下QoS感知的服務優選算法及實例分析 3．1 算法描述 根據上述服務優選思想，服務是否配置給任務通過用戶獲得的服務質量多少來衡量，子任務選擇服務質量高的服務。對于整個任務來說，用戶獲得的服務質量是各子任務獲得服務質量的和。模糊集下QoS感知的服務優選算法描述如下： a)接收滿足子任務ti所需QoS約束的服務列表。設候選服務集合為Sj={s1，s2，…，sk}。 b)構造無QoS參數模糊隸屬矩陣Ak×m。 c)通過歸一化處理獲得無量綱的QoS參數重要度矩陣，并計算獲得QoS參數的權重向量ω。 d)計算各候選服務的綜合服務質量Gj(ω)。 e)S1=decreasesort(Gj(ω)); /*根據Gj(ω)對候選服務進行降序排列*/ Ribid=S1[1];/*選擇Gj(ω)最大的候選服務為配置給子任務ti的服務*/ 3．2 實例說明 設某應用P，其子任務t的候選服務集合中有四個元素。比較服務需求中QoS參數閾值和各候選服務中QoS參數的值，獲得四個候選服務對于各QoS參數的隸屬度，構成隸屬函數矩陣： 根據QoS參數重要性度量方法，求出QoS權重向量為Q＝{0.315， 0.295， 0.175， 0.215}。計算各候選服務的綜合服務質量，如表1所示。 根據四個候選服務的綜合服務質量值，從大到小排列為s3>s1>s2>s4，即選擇服務s3完成子任務t。同理，采用該模型可以為其他子任務選擇合適的服務。 4 結束語 從用戶多方面需求的角度出發，采用多個QoS作為網格服務能力的評價指標，旨在選擇綜合能力最優的服務提供給用戶。針對網格QoS參數的約束條件具有模糊性的特點，提出了模糊集下的QoS感知的服務優選算法，并通過對QoS參數的歸一化處理和權值計算，解決了QoS參數的不可公度性問題和多個QoS參數之間的矛盾性問題。實例分析表明了算法的有效性。 參考文獻： ［1］FOSTER I， ROY A， SANDER V. A quality of service architecture that combines resource reservation and application adaptation[C]//Proc of the 8th International Workshop on Quality of Service.Pittsburgh: Kluwer Academic Press，2000:181188. ［2］胡春明，懷進鵬，沃天宇，等. 一種支持端到端QoS服務質量的網格體系結構[J].軟件學報，2006，17(6):14481458. ［3］SINGHERA Z U.Extended Web services framework to meet nonfunctional requirements[C]//Proc of the International Symposium on Applications and the Internet Workshops.Los Alamitos: IEEE Computer Society，2004:26-30. ［4］金海，陳漢文，呂志鵬，等.CGSP作業管理器合成服務的QoS優化模型及其求解[J].計算機學報，2005，28(4):578-588. ［5］ALALI R J， RANA O F， WALKER D W，et al.GQoSM:grid service discovery using QoS properties[J].Computing and Informatics Journal，2002，21(4):363-382. ［6］BUYYA R，GIDDY J，ABRAMSON D.An evaluation of economybased resource trading and scheduling on computational power grids for parameter sweep applications[C]//Proc of the 2nd International Workshop on Active Middleware Services.Pittsburgh: Kluwer Academic Press，2000:221-230. ［7］馬滿福，吳健，陳丁劍，等.網格經濟模型中基于信譽度的資源選擇[J].計算機工程，2006，32(17):175177. ［8］WOLSKI R，SPRING N， HAYES J.The network weather service: a distributed resource performance forecasting service for metacomputing[J].Journal of Future Generation Computing Systems，1999，15(5-6):757768. ［9］NAS parallel benchmarks compare performance[EB/OL].[2006-05-20].http://www.nas.nasa.gov/software/npb. 注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”
