云計算中服務質量預測數據的信心建模

張雪潔,王志堅,張偉建

(1. 河海大學計算機與信息學院,江蘇 南京　210098; 2. 南京航空航天大學計算機科學與技術學院,江蘇 南京　210016;3. 河海大學遠程與繼續教育學院,江蘇 南京　210098)

?

云計算中服務質量預測數據的信心建模

張雪潔1, 2,王志堅1,張偉建3

(1. 河海大學計算機與信息學院,江蘇 南京210098; 2. 南京航空航天大學計算機科學與技術學院,江蘇 南京210016;3. 河海大學遠程與繼續教育學院,江蘇 南京210098)

摘要：為處理服務質量(quality of service,QoS)預測所用數據的不確定性,增加預測結果的信心值,使預測的QoS值更可信,建立了量化QoS預測中信心的概率模型。構建模型過程中,考慮了預測所用的QoS數據項數量、數據的波動情況(數據偏差)以及數據隨時間的衰減情況。數據項數量表明參與預測的數據多少對預測結果可信度的影響程度;數據偏差表明服務的實際QoS值和預期值的一致程度;數據衰減程度表明隨時間變化,數據對預測結果的影響程度。仿真試驗表明,該信心模型能夠準確有效地幫助用戶選擇滿足其需求的服務。

關鍵詞：云計算；QoS預測;信心建模;數據量;數據波動;數據衰減;服務選擇

服務質量(quality of service,QoS)預測可以廣義地描述為使用服務的歷史數據確定用戶從提供商獲得的可能的服務質量。隨著云計算的廣泛應用,網絡上功能相同的服務越來越多,想用這些服務的用戶希望用到質量最好、最符合自己需求的服務。對用戶來說,評估所有服務是不現實的,所以需要借助預測QoS的技術和工具,預測QoS的能力就顯得尤為重要。

在云計算環境中,由于受網絡擁堵、資源限制或質量管理水平等因素的影響[1-4],服務提供商的行為不總是期望的那么穩定,所以預測的性能就會有波動。這些不確定性引起的服務性能的變化會反映在收集的QoS數據中。根據變化很大的數據預測QoS很可能是不可靠的,而根據少量數據預測QoS也不可信。此外,數據收集的時間因素也會影響預測的可信度,根據新近數據預測的結果更有說服力。所以,需要對QoS預測結果附加一個信心值,這樣預測的QoS更可信,能為用戶選擇服務提供更可靠的指示。

為了量化QoS預測中的信心,筆者建立了考慮3個可靠性度量的信心模型,并展示信心模型能夠有效幫助用戶根據他們的期望選擇服務。3個可靠性度量為：(a)預測中需要用到的所有QoS數據項數量;(b)數據項中數據值的變化情況;(c)數據隨時間的衰減情況。

1信心模型相關工作

目前,許多信心模型已被提出,特別是在信任和信譽系統,這些模型的主要目標是在QoS預測時處理用戶行為的一些不確定性。Sabater 等[5]介紹了2種方法(評價的數量、評價值的偏差)用于計算信任值的可靠性,這2種方法得到了Keung等[6]、Huynh等[7]、Dossari等[8]的認同。Mui等[9]用Chernoff范圍確定獲得某一等級的信心需要的最小樣本大小,Zhang等[10]用該方法計算代理的經驗是否足夠可靠,即經驗的可靠程度,代理經驗由樣本大小度量。上述研究已表明在產生信心值時考慮數據特征的重要性,而數據特征由數據項數量和數值的偏差來度量。但上述信心模型不能直接應用到筆者的工作中,原因有2個:(a)這些模型主要是針對離散數據,而本文處理的是連續數據,即監測數據;(b)預測結果的可靠性是“靜止地”推導出來的,忽略了用戶的期望,而期望對個性化預測很重要,是選擇滿足用戶需求服務的不可少因素。

為確定一個指定服務的預測是否可信，必須根據用戶需要的質量“動態地”做出預測。為此,筆者提出一個考慮預測數據的大小、數據的波動以及數據隨時間衰減的信心模型。這樣,可以“動態地”推斷出預測結果的可信度。該模型能適當地改進已有模型的不足,有效處理QoS預測中存在的一些不確定性。

2信心模型的建立

基于Huynh等[7]、 Zhang等[10]的研究,本文信心模型用3個度量(數據大小、數據偏差和數據衰減程度)計算對某個QoS屬性預測的信心。數據大小表明用于預測的數據集支持QoS預測方法進行預測的強度,即參與預測的數據多少對預測結果可信度的影響程度。數據偏差表明服務的實際QoS值和預期值的一致程度。數據衰減程度表明隨時間變化,數據對預測結果的影響程度。

2.1　數據大小度量

數據大小度量是基于預測時所用數據項數量進行的。預測時所用的每個數據項都是一個服務過去服務質量的證據。擁有證據越多,對評估的信心越高,即隨著數據項數量的增加,可信度增加。本文采用式(1)形式化表示度量方法,根據數據項數量計算得到可信度,式(1)表明隨著數據項數量n的增加,可靠程度增加,直到達到定義的閾值(需要的最小數據項數量)m:

(1)

其中

式中:Cω——數據規模的度量值(當n從0增加到m時其從0增加到1,當n超過m時其值保持1，m根據邊界定理[9]計算得到);ε——用戶可以接受的最大誤差等級;λ——需要的信心等級。

λ越大,ε越小,m值越大,說明需要的數據項數量越多。例如,如果設λ=0.99、ε=0.1,則需要的最小數據項數m=1 060,這意味著要對預測結果有信心,就要盡可能多地使用QoS數據項記錄。

2.2　數據偏差度量

數據偏差度量是基于預測中所用數據的變化進行的。服務選擇是根據歷史性能數據預測出的QoS值來決定的,選擇用于預測的數據時考慮數據的偏差很重要。因為分布不同的數據可能計算得到同樣的平均值,但它們變化不同,如,一個服務的某個QoS屬性值(如,響應時間)變化比較大,另一個服務的響應時間相對穩定,但二者的平均值可能相同。而數據變化越大,計算出的平均值越不可靠,也就是說,根據波動大的數據預測出的結果可靠性低。

為計算可靠性,筆者把服務提供的QoS值看作伯努利(Bernoulli)試驗集合,交付結果分為:成功的交付(交付的服務滿足用戶需求的質量)或不成功的交付(不能交付滿足用戶需求質量的服務),然后用Beta分布建模[11-12]:

(2)

其中

α=s+1β=f+1

式中:Cθ——數據偏差的度量值;s——監測的成功交付的服務數量;f——不成功的服務數量。

根據拉普拉斯繼承規則[13],α和β的比率可以確定[0,1]區間的分布峰值,α越大分布模式越接近1。

采用式(3)來判斷一個服務對一個QoS屬性的歷史交付是否成功:

(3)

式中:S(Ai)——記錄一個服務提供的服務質量是否滿足用戶需求的參數；d(Ai)——QoS數據集D中服務屬性Ai的質量值,是監測到的服務實際提供的質量值;pi——對QoS屬性Ai預測的結果,根據用戶需求計算得到;θ——用戶可接受的質量等級波動值。

如果d(Ai)在pi指定范圍內,則認為是成功的交付,記S(Ai)=1；否則,認為不成功,記S(Ai)=0。范圍[pi-θ,pi+θ]稱為信心范圍?；谑?3)可得

(4)

選擇不同的θ對Cθ有直接影響,同樣的數據大小,θ值越大,則會產生更多認為是成功的交付,因此對QoS預測結果的信心越大、Cθ值越大。所以,用戶接受服務提供商提供的服務QoS值波動大時要選擇大的ε值。

與已有方法[9-12]相比,筆者提出的信心模型中一個服務是否交付成功是動態確定的,因為pi是根據用戶需求計算的,所以d(Ai)是否在信心范圍內受用戶需求的影響,也就是說,判斷一個服務是否成功是由用戶的需求影響的。例如,設θ=0.1,假設服務的交付值和需求的質量等級足夠近才算滿足用戶需求,即[pi-θ,pi+θ]是一個小范圍。如果一個服務S對屬性Ai的交付質量是0.5,那么對于對Ai的期望是0.5的用戶是成功的,但對于需求是0.9的用戶就是不成功的。

2.3　數據衰減度量

監測的QoS數據在時間上是連續的,數據中包含的用于預測的信息會隨著時間的推移而發生變化。在實際應用中,距離預測時間點最近的數據所蘊含的信息往往要比歷史數據有價值。因此,根據不同時間段的數據預測出的結果其可靠性不同。為此,對預測所用數據在預測中的權重進行度量,為預測的可信度做出指示。

應用時間衰減函數 (time decay function,TDF)來度量逐步衰減的數據對預測的支持程度[14-15]。監測的QoS數據對預測的支持度隨時間t逐步衰減,衰減函數為

(5)

式中:t——預測時間點與數據監測時間點的時間差;μ——數據在一個時間單元內的衰減比率,即衰減因子。

μ是算法中的重要參數,它反映了歷史數據對預測結果的影響程度,有助于提高預測結果的可信度。當μ減小時,衰減速度變慢,同一時間點的QoS數據對預測結果的影響程度也相應提高。如果μ太小,數據衰減不明顯,數據衰減對預測的影響就很小,即久遠的數據和新近的數據效果差不多,所以μ太小不會影響預測結果的可信度。μ太大,數據對預測的影響迅速衰減,同樣會影響預測結果的可靠性。所以,應該在取值范圍內盡可能大地設置μ。

設用戶預測所用的最少數據項數量為m,第m個數據的記錄時間和預測時間差記為tm,用戶所能接受的最小衰減值為fmin,理想狀態這個值出現在第m個數據,那么fmin=2-μtm,即fmin≤f(t)≤1。所以,μ的取值范圍為

(6)

總的數據衰減度量值為

(7)

式中:N(ti)——預測數據中距離預測時間點ti時間的數據項數量。

2.4　總體信心值

數據規模度量Cω表示QoS預測值受數據集支持的程度,數據偏差度量Cθ表示監測的服務QoS值和平均值的一致程度,數據衰減度量Cf表示服務的QoS值隨時間的衰減程度。根據這3個度量,計算總的信心值為

(8)

3仿 真 試 驗

試驗的目的是驗證信心模型是否有助于提高服務選擇的準確性。

3.1　試驗數據

試驗模擬6個服務:S1、S2、S3、S4、S5和S6,6個服務的測試數據見表1,數據分布如圖1所示。6個服務的QoS值的模擬值為正態分布,平均值相同,都為0.5,但數據的大小、數據的波動(受標準偏差σ控制)和數據收集的時間跨度不同。創建的6個服務模擬了服務的不同行為。

表1　6個服務的測試數據Table 1　Test data of six services

圖1　服務數據分布Fig. 1　Distribution of services data

3.2　信心在服務選擇中的作用

QoS預測的目的是幫助用戶選擇滿足他們需求的服務。利用信心模型情況下的服務選擇情況來驗證本文提出的信心模型是否能提高服務選擇的準確性。本文提出的信心模型可以和任意QoS預測方法結合,幫助提高預測的可靠度。

圖2為不考慮信心模型情況下的服務選擇。由于6個服務的歷史QoS數據的平均相似,預測的QoS值也相似,所以對服務做出隨機選擇。雖然S1偏離服務的需求等級很多,但被選擇了3次,有33.3%的時間選擇它,大于平均時間。而和用戶需求最一致的服務S2只被選擇1次。

圖2　有無信心模型的服務選擇比較Fig. 2　Comparison between service selections with and without confidence model

考慮信心模型的方法剛開始數據量小的時候在服務S4和S6之間隨機選擇,之后一直穩定地選擇服務S2。由式(8)分別計算6個服務的信心值, 6個服務信心值隨時間/QoS數據量的變化情況如圖3所示。從圖3可知服務的行為表現可以分為2個階段,第一階段(時間在0～500 s之間),S2、S4、S5和S6的行為一直很接近,它們的預測信心值也比較接近,所以QoS預測方法選擇有更高信心值的服務。第二階段(時間在500 ～1 000 s之間), S4、S5和S6的預測信心值開始下降或保持不變。S5和S6用于預測的數據量比較少,沒有更多的數據用于預測,所以預測信心值不會增加。S5的數據跨度比較大,所以數據衰減比較大,其預測的信心值開始下降。S4在這個階段用于預測的數據波動比較大,所以預測的信心值較上一個階段急速下降,之后穩定在0.25左右。只有S2的預測信心值一直穩步上升,所以將選擇S2。

圖3　6個服務的信心值Fig. 3　Confidence values of six services

與不考慮信心的試驗相比,這里一直沒有選擇S1、S3和S5。因為S1的QoS值一直比較波動,意味著S1的QoS平均值不太可靠。S3在第一階段的波動比較大,S5的數據衰減一直比較大,所以都沒有被選擇。試驗表明，在云計算環境中把信心作為QoS預測的一部分,能更好地幫助用戶選擇滿足其需求的服務。

4結語

為量化QoS預測中的信心,提出了一個概率模型,該模型集成了3個可靠性度量:預測中所用QoS數據項的數量、數據偏差和數據衰減。該模型中,數據大小度量表明數據集或過去的證據對QoS預測方法推導出預測的支持程度,數據偏差度量表明監測的服務QoS值和平均值的一致程度,數據衰減度量表明服務的QoS值隨時間的衰減程度。最后,通過試驗驗證了在預測過程增加信心模型能夠更準確地選擇滿足用戶需求的服務,增加用戶的總體效用。目前的信心模型中只考慮了監測的QoS數據,接下來可以進一步擴展模型,加入預測服務時考慮的其他因素,如服務提供商的信譽等。此外,還可以利用衰減函數去度量隨時間推移服務提供商的行為變化。

參考文獻：

[1] SAHAI A, OUYANG J, MACHIRAJU V, et al. Specifying and guaranteeing quality of service for web services through real time measurement and adaptive control [R]. Palo-Alto: EServices. Software Research Department, HP Laboratories, 2001.

[2] KIM D, LEE S, HAN S, et al. Improving web services performance using priority allocation method[C]//Anonymous. Proceedings of International Conference on Next Generation Web Services Practices. Los Alamitos: IEEE Computer Society, 2005: 201-206.

[3] JURETA I J, HERSSENS C, Stéphane F, et al. A comprehensive quality model for service-oriented systems [J]. Software Quality Journal, 2009, 17: 65-98.

[4] WOHLSTA E, TAI S, Mikalsen T,et al. Glueqos: middleware to sweeten quality-of-service policy interactions[C]//Anonymous. Proceedings of the 26th International Conference on Software Engineering. Washington DC: IEEE Computer Society, 2004:189-199.

[5] SABATER J, SIERRA C. REGRET: reputation in gregarious societies[C]//Anonymous. 5th International Conference on Autonomous Agents and Multiagent systems. Hakodate: ACM Press, 2006: 194-195.

[6] KEUNG S N L C, GRIFFITHS N. Using recency and relevance to assess trust and reputation[C]//Anonymous. Proceedings of AISB 2008 Symposium on Behaviour Regulation in Multi-agent Systems. Aberdeen: The Society for the Study of Artificial Intelligence, 2008:13-18.

[7] HUYNH T D, JENNINGS N R, SHADBOLT N. R fire: an integrated trust and reputation model for open multi-agent systems [C]//Anonymous.16th European Conference on Artificial Intelligence, Valencia: IOS Press, 2004: 18-22.

[8] DOSSARI A H, SHAO, J H. Modelling confidence for quality of service assessment in cloud computing [C]//Anonymous. Proceedings of CONF-IRM. Natal: Berkeley Electronic Press, 2013: 48-59.

[9] MUI L, MOHTASHEMI M, HALBERSTADT A. A Computational model of trust and reputation[C]//Anonymous.35th Annual Hawaii International Conference on System Sciences. Hawaii: IEEE Computer Society, 2002: 2431-2439.

[10] ZHANG J, COHEN R. A personalized approach to address unfair ratings in multiagent reputation systems[C]//Anonymous. AAMAS Workshop on Trust in Agent Societies. Hakodate:Springer. 2006: 89-98.

[11] TEACY W T L, PATEL J, JENNINGS N R, et.al. Coping with inaccurate reputation sources: experimental analysis of a probabilistic trust model[C]//Anonymous. 4th International Joint Conference on Autonomous Agents and Multiagent Systems. Utrecht: Association for Computing Machinery, 2005: 25-32.

[12] SANG A J, ISMAIL R. The Beta Reputation System[R]. Brisbane: Queensland University of Technology, 2002.

[13] RISTAD E S. A natural law of succession: Research Report CS-TR-495-95[R]. Princeton: Princeton University, 1995.

[14] 李國徽,陳輝. 挖掘數據流任意滑動時間窗口內頻繁模式[J]. 軟件學報,2008, 19(10): 2585-2596. (LI Guohui, CHEN Hui. Mining the frequent patterns in an arbitrary sliding window over online data streams[J]. Journal of Software, 2008, 19(10): 2585-2596. (in Chinese))

[15] 吳楓, 仲研, 吳泉源. 基于時間衰減模型的數據流頻繁模式挖掘[J]. 自動化學報, 2010, 36(5): 674-684. (WU Feng, ZHONG Yan, WU Quanyuan. Mining frequent patterns over data stream under the time decaying model[J]. Acta Automatica Sinica, 2010, 36(5): 674-684. (in Chinese))

·簡訊·

河海大學杰出校友陸佑楣院士獲世界工程組織聯合會優秀工程獎獎章

近日，在世界工程組織聯合會(WFEO)舉辦的2015年世界工程師大會(WEC 2015)上，河海大學杰出校友、我國著名的水利水電工程專家、中國大壩協會榮譽理事長、河海大學博士生導師陸佑楣院士被授予優秀工程獎(Medal of Engineering Excellence)獎章。這是中國專家首次獲此殊榮。

優秀工程獎又稱工程成就獎(the Engineering Achievement Award)，由世界工程組織聯合會設置于1989年，每兩年頒發一次，旨在增強全球公眾對工程的實踐、理論和社會貢獻的關注。該獎項主要頒發給具備豐富職業經驗，在實踐、理論和社會地位方面有突出成就、并具有較強國際影響力的工程師。

(本刊編輯部供稿)

Confidence model of QoS prediction data in cloud computing

ZHANG Xuejie1,2, WANG Zhijian1, ZHANG Weijiang3

(1.CollegeofComputerandInformation,HohaiUniversity,Nanjing210098,China;

2.CollegeofComputerScienceandTechnology,NanjingUniversityofAeronauticsandAstronautics,

Nanjing210016,China;

3.CollegeofDistanceLearningandContinuingEducation,HohaiUniversity,Nanjing210098,China)

Abstract:In order to handle the uncertainty of data used in quality of service (QoS) prediction, increase the confidence value of prediction results, and make the QoS prediction more reliable, a probability model for quantifying the confidence in QoS prediction was built. In the process of building the model, the number of QoS data items used in prediction, the data fluctuation (data deviation), and the data decay over time were considered. The results show that the number of data reflects the impact of the number of QoS data used in prediction on the reliability of the prediction result, the data deviation reflects the consistency degree of the actual value and predicted value of QoS in service, and the data decay reflects the impact of data on the prediction result over time. The simulated test indicates that the confidence model can help consumers effectively select services based on their requirements.

Key words:QoS prediction; confidence modeling; number of data; data fluctuation; data decay; services selection

中圖分類號：TP391

文獻標志碼：A

文章編號：1000-1980(2015)06-0588-06

作者簡介：張雪潔(1979—),女,遼寧鐵嶺人,博士研究生,工程師,主要從事服務計算、Web服務質量評估與推薦研究。E-mail: xuejiezh@hhu.edu.cn

基金項目：“十二五”國家科技支撐計劃(2013BAB05B00,2013BAB06B04);江蘇水利科技項目(2013025);河海大學淮安研究院開放基金(2014502512)

收稿日期：2014-12-10

DOI：10.3876/j.issn.1000-1980.2015.06.014