區間型服務響應時間變化趨勢預測機制

景偉娜，陳秋紅，薛 冰

（河南城建學院 計算機科學與工程系，河南 平頂山467036）

0 引 言

在服務計算領域，當用戶訪問服務時，將面對不同的服務提供者提供的數量可觀的功能相同或相似的服務，需根據服務質量選擇用戶滿意度較高的服務進行訪問。在眾多的服務質量屬性中，由于服務響應時間能被用戶直觀感知，因此預測并分析服務響應時間的變化趨勢，對于提高用戶滿意度具有重要意義。

服務響應時間指用戶開始請求服務和收到響應之間的時間間隔。包括服務時間和傳輸時間。其中，服務時間指服務收到用戶請求以及服務完成處理的時間區間。服務時間一般由服務提供者的SLA提供。傳輸時間由網絡狀態決定。根據對服務響應時間的定義可知，服務響應時間具有在一定取值范圍內動態性較強的特性。在不同的時間點和不同的網絡狀況下訪問同一個服務時，服務響應時間的值往往會在一定范圍內有較大的波動。在這樣的情況下，以往的處理方法常以一定時間段內服務響應時間的平均值進行計算［1－3］，這將遺失掉很多信息，使得響應時間有差別的服務被判定為無差別服務。

因而，近年來已有眾多研究將區間型數據類型引入到Web服務的QOS屬性描述中，通過記錄存在波動的QOS屬性值的上下邊界，以增加QOS屬性描述的準確性和表達更為豐富的QOS信息［4－7］。采用區間型數據描述服務響應時間，例如，服務S1和S2的響應時間分別為：RTS1［100s，200s］，RTS2 ［50s，250s］。響應時間平均值都是150s，如果按照平均值方法進行定義，服務S1和S2的響應時間無差別。但是，按照區間型數據類型描述方法可以明顯看出，在以往的歷史活動中，服務S1的響應時間表現比服務S2更加穩定（服務S1的響應時間在100s的范圍內波動，服務S2的響應時間在200s內波動），所以可以得出在某種程度上，服務S1的響應時間要優于服務S2。

雖然區間型數據類型對描述服務響應時間保留了更多的信息，但由于其具備區間不確定性，傳統的預測方法如線性回歸、神經網絡等方法需將區間數據轉換為確定實數再進行預測。難以在不損失信息的情況下進行預測。

本文引入區間灰數預測［8］機制，在不損失信息的前提下，從區間型服務響應時間的區間穩定性和區間上下界值兩方面進行預測，并分析在這兩方面的服務響應時間變化趨勢，為用戶提供更豐富準確的決策信息。

1 區間型服務響應時間特性分析

區間型服務響應時間是某一時間段內服務響應時間變化范圍的統計值。比某一時間點服務響應時間的具體值包含了更豐富的信息。為了更好的利用這些信息，不損失有用信息，需首先對區間型數據的特性進行分析，判斷在服務響應時間的區間型數據中有哪些有用信息。

為了對區間型服務響應時間的特性進行分析，將連續時段內區間型服務響應時間的上下界在圖中標注出來。如圖1所示，用表示區間型服務響應時間，同一時間段內服務響應時間的上界為bn，下界為an，連續n段時間段內服務響應時間分別為 ［a1，b1］， ［a2，b2］， ［a3，b3］，……，［an－1，bn－1］，［an，bn］。

圖1 區間型服務響應時間分布

區間型服務響應時間包含了豐富的信息，主要有用的信息包含以下幾個方面，一是 “穩定性”信息。上下界之間范圍大小，表征了數據波動的穩定性。當區間數據上下界的差值越小，則表明在該時間段內服務響應時間的波動范圍越小，即 “穩定性”越好，如 ［50，100］比 ［50，200］的 “穩定性”好。如果服務響應時間比上一個時間段趨于 “穩定”，則說明服務所受到的干擾因素減少，這種變化趨勢是用戶所期望的結果。二是區間數據上下界值的相對大小。對于服務響應時間，小的上下界值更有意義，如［50，100］＜ ［100，200］。現有方法一般采用區間數據白化值［8］來比較區間數據的相對大小，即1/2（ai＋bi）。區間數據的相對大小并不能完全表征哪個區間數據更優。需將區間型數據的 “穩定性”和區間型數據的相對大小結合起來判定和分析。

設定服務響應時間的區間型數據A的穩定性為Aw，區間型數據的相對大小值為Ad。則對于服務響應時間的區間型數據A和B，

如果Aw＞Bw，且Ad＜Bd，則A優于B；

如果Aw＜Bw，且Ad＞Bd，則B優于A；

如果Aw＞Bw，且Ad＞Bd則B較優于A；

如果Aw＜Bw，且Ad＜Bd則A較優于B；

如果Aw＝Bw，且Ad＜Bd則A優于B；

如果Aw＝Bw，且Ad＞Bd則B優于A；

如果Aw＜Bw，且Ad＝Bd則A優于B；

如果Aw＞Bw，且Ad＝Bd則B優于A；

穩定性與相對大小都是通過區間型數據的上下界值分析得出的，說明區間型服務響應時間包含的信息不僅僅是邊界值，由一系列區間型服務響應時間的變化趨勢還包含了服務響應時間波動在一定范圍內的分布信息，這種波動分布信息常在現有的數據分析過程中進行降維時，而損失掉，造成分析的結果不夠準確。

用戶期望下一時段的服務響應時間區間型數據更優，通過預測下一時段服務響應時間區間數據的 “穩定性”和“相對大小”，則可分析下一時段的服務響應時間是否優于上一時段，并可根據比較結果選擇服務響應時間更優的服務，或采取相應措施以提高服務的服務質量。更好地滿足用戶的需求。

2 區間服務響應時間變化趨勢預測機制

2.1 區間型數據的信息保留

為了不遺失區間型服務響應時間的有效信息，從區間穩定性和區間上下界值兩方面進行預測，以分析其變化趨勢。

在一個區間或某個一般的數集內取值的不確定數也被稱為區間灰數，區間型服務響應時間滿足在一定范圍內取值不確定的特點，故區間型服務響應時間屬于區間灰數，區間服務響應時間的預測可采用區間灰數預測機制。區間灰數預測的實質是對區間灰數上界和下界的預測。區間灰數的上界和下界在形式上表現為實數，但灰數的取值分布信息缺乏。假如直接分別對灰數的上下界進行建模，則只保留了邊界信息，損失了服務響應時間在此邊界波動范圍內的分布信息，預測出的邊界值將會出現較大偏差，會對模型的正確構造帶來一定的影響。因此，將 ［ai－1，bi－1］，［ai，bi］連起來，形成若干個封閉四邊形，該四邊形的面積充分反應了服務響應時間在不同范圍內波動性變化的情況，采用該四邊形的面積作為預測序列，保留了 ［ai－1，bi－1］向 ［ai，bi］變化的分布信息，并可根據四邊形面積作為原始預測序列所求得的預測結果，分析區間數據“穩定性”。

選取四邊形的中心點（如圖1所示，O1，O2，O3，O4，…，On）作為預測序列分析上下界值相對大小變化趨勢。四邊形的中心點能充分反應區間性數據 ［an－1，bn－1］向 ［an，bn］變化的過程中的信息分布，根據該項值的預測結果，求解出的服務響應時間上下界值，保留了波動分布信息，預測效果更能獲得較高的用戶滿意度。

2.2 “穩定性”預測分析

步驟1 將相鄰區間數據間構建的四邊形面積作為原始預測序列

原始預測序列為

步驟2 對該原始序列作一次累加生成（1－AGO），建立GM（1，1）灰預測模型，并采用最小二乘法求解后得生成序列

步驟3 預測第K＋1個四邊形面積，對預測序列作累減生成得

步驟4 分析區間數據 “穩定性”與構建四邊形面積之間的關系

當p＝1時

當p＝2時

由此可推出：

當P＝n－1時

步驟5 將式（4）的預測結果代入到式（6），

從代入的結果來看，式（6）的前（n－2）項構成了等比數列，其公比為q＝－eas，根據這一分析結果，對前n－2項求和，即可求解出 “穩定性”為

步驟6 為了進行動態循環預測新樣本，將第K＋1次的實際服務響應時間統計為區間型數據，然后在原預測樣本S（0）中去掉第一個預測樣本值S（0）（1），將第K＋1次的樣本值S（0）（K＋1）加入到預測序列中，構成新的預測樣本：用于下次預測，重復步驟1－5，如此動態更新預測樣本。

2.3 區間上下界值預測

步驟1 將四邊形中心點序列O1，O2，…，On的縱坐標W＝（w（1），w（2），…，w（n－1））作為預測序列構建GM（1，1）灰預測模型，其中w（p）＝（ap＋ap＋1＋bp＋bp＋1）/4。采用最小二乘法求解后得生成序列

步驟2 預測第K＋1個中心點序列的縱坐標，對預測序列作累減生成得

步驟3 分析中心點序列與區間數據上下界值之間的關系

當P＝1時

當P＝2時

由此可推出：

當p＝n－1時

步驟4 將式（9）的預測結果代入到式（11）

從代入的結果來看，式（11）的前（n－2）項構成了等比數列，其公比為q＝－eas，根據這一分析結果，對前n－2項求和，得

步驟5 聯合式（7）和（12），通過解方程組的形式可得到下一時間段的區間型服務響應時間上界和下界值

其中

步驟6 獲得K＋1次的實際服務響應時間區間型數據后，求得新的四邊形中心點Ok＋1的縱坐標，在原序列W（0）中去掉W（0）（1），加入W（0）（K＋1），構成新的動態序列：

2.4 變化趨勢分析

通過將相鄰兩個區間型服務響應時間上下界值分別相連構建四邊形，然后用四邊形的面積預測分析 “穩定性”，用四邊形的中心點值預測分析 “相對大小”，這種方法包含了波動分布信息。在此基礎上獲得的區間上下界值沒有損失區間數據所包含的信息。得到區間數據在下一時間段的預測值后，還需要進行變化趨勢分析，以確定是否需要采取必要的措施，增強服務質量，改善網絡環境，以便于取得更高的用戶滿意度。

用戶除了期望得到平均服務響應時間更短的服務以外，還期望所訪問服務的穩定性較好，在較短的時間段內服務響應時間變化范圍較小。因此，服務響應時間的變化趨勢也應分為兩個方面進行。通過預測值與當前時間段的區間型服務響應時間的對比，分析 “穩定性”與 “相對大小”的變化方向，如果 “穩定性”與 “相對大小”均變差，則可通過冗余策略等方法，提高服務的可用性和可靠性，從而改善服務的服務質量。

3 仿真實驗

在實驗室環境下，采用6臺PC機搭建實驗平臺，PC機配置均為 Pentium Dual－Core 2.60－GHz，內存4G。首先部署了10個具有相同功能的服務在AXIS服務器中，并在JUDDI中注冊。訪問這些服務若干次，在單位時間段內（t＝30s），隨機產生服務請求，并將單位時間段內的服務響應時間進行記錄，獲得在此單位時間段的區間型服務響應時間。按此方法，采樣區間型服務響應時間作為預測的原始序列，從兩方面分析本文預測機制的有效性。一是評估預測誤差，判定預測準確度。二是對比本文預測機制與傳統區間平均值法，在調用服務的實際響應時間。

3.1 區間服務響應時間預測誤差評估

在獲取的單位時間段區間型服務響應時間200組作為預測原始序列進行預測，按照第2節中所提算法共預測300組時段的區間型服務響應時間。對每相鄰5個區間型服務響應時間與實際統計的單位時間段內區間型服務響應時間對比，分別求上界和下界殘差，將這相鄰5組的殘差平均值作為1組殘差率。共統計60組預測殘差率。

如圖2所示，本文提出的區間灰數預測機制預測不確定性區間型服務響應時間。統計的殘差率均在5%以下，平均約為3%。根據灰色系統預測精度檢驗等級參照表［9－10］中對精度等級的劃分，本文方法的預測精度等級為1級，完全可用于區間型服務響應時間的預測，表明本文預測機制是有效、可行的。

圖2 服務響應時間預測值殘差率

3.2 服務調用實際響應時間比較

如前所述實驗室環境條件下，將相同功能的服務增加為30個，統計服務響應時間在單位時間段內的上下界值，對每個服務，共記錄200個時間段作為預測原始序列。分別采用平均值法［2］和本文預測機制進行預測，根據預測結果，選擇訪問請求預測值中響應時間最短的服務。再統計下一單位時間段內調用服務的實際響應時間。然后將兩種方法所求得的預測值與實際響應時間進行對比，以分析兩種方法在應用中的實際效果。

圖3 服務響應時間比較

從圖3中可以看出，應用兩種方法調用服務，根據平均值法和本文預測機制預測結果所調用服務的實際響應時間平均值均約為200s，但根據平均值法所調用服務的響應時間波動較大，約在區間 ［100，300］內波動，波動跨度為200s。而本文方法所選擇服務的響應時間波動性較小，約在區間 ［170，230］內波動，波動跨度為60s，因而具有更強的穩定性，更能有效提高用戶的滿意度。

3.3 預測樣本數對預測效果的影響。

預測精度很大程度上依賴于樣本規模，我們將樣本數從20一直調整到500，計算預測值與真實值之間的誤差率。

如圖4所示，隨著樣本數的增加，預測誤差率減小，預測精度提高。但樣本數增加到200后，曲線走勢變得較為平坦，表明從200再增加樣本數對預測精度的貢獻較小。

圖4 預測樣本數分析

4 結束語

本文采用區間灰數預測機制來解決不確定性區間型服務響應時間的預測問題，能夠在不損失信息的前提下，從“穩定性”和 “區間上下界值”兩方面進行預測分析，并通過預測結果分析得出區間型服務響應時間的變化趨勢。最后，仿真實驗表明預測機制的預測精度為1級，平均誤差約為3%，且根據本文預測機制所調用的服務響應時間穩定性較高，能夠有效提高用戶滿意度。另外，根據預測分析結果，也能為服務提供者提供豐富的信息，以便于進行服務的管理和維護，提高服務的服務質量水平。

［1］NIE Weiran，ZHANG Jing，LIN Kweijay.Estimating real－time service process response time using server utilizations ［C］.IEEE International Conference on Service－Oriented Computing and Applications.Perth WA Australia：IEEE Computer Society，2010：1－8.

［2］Gorbenko Anatoliy，Kharchenko Vyacheslav，Mamutov Seyran，et al.Real distribution of response time instability in service－oriented architecture ［C］.Proceedings of the IEEE Symposium on Reliable Distributed Systems.New Delhi，India：IEEE Computer Society，2010：92－99.

［3］FENG Xingzhi，REN Yi，HU Jianqiang，et al.ZebraX：A model for service composition with multiple QoS constraints［G］.LNCS 4459：Proceedings of the 2nd International Conference on Advances in Grid and Pervasive Computing，2007：614－626.

［4］YANG Fangchun，SU Shen，LI Zhen.The semantics web service composition strategy of mixed QoS model perceptive［J］.China science E：information science，2008，38（10）：1697－1716（in Chinese）.［楊放春，蘇森，李禎.混合QoS模型感知的語義Web服務組合策略 ［J］.中國科學E輯：信息科學，2008，38（10）：1697－1716.］

［5］LI Zhen，YANG Fangchun，SU Sen.Fuzzy multi－attribute decision making－based algorithm for semantic web service composition ［J］.Journal of Software，2009，20（3）：583－596（in Chinese）.［李禎，楊放春，蘇森.基于模糊多屬性決策理論的語義 Web服務組合算法.軟件學報，2009，20（3）：583－596.］

［6］WEN Junhaoa，QIN Jiaa，LIU Lingb.Approach to web services selection under uncertain user preferences ［J］. Application Research of Computers，2010，27（6）：2147－2149（in Chinese）.［文俊浩，秦佳，柳玲.一種在用戶偏好不確定情況下的Web服務選擇方法 ［J］.計算機應用研究，2010，27（6）：2147－2149.］

［7］LI Na，FENG Baiming，WU Xiaolong.Research on service selection algorithm for dynamic web services composition ［J］.Computer Engineering and Design，2011，32（2）：413－415（in Chinese）.［李娜，馮百明，武小龍.動態Web服務合成中的服務選擇算法研究 ［J］.計算機工程與設計，2011，32（2）：413－415.］

［8］FANG Zhigeng，LIU Sifeng，LU Fang，et al.Study on improvement of token and arithmetic of interval grey numbers and its GM（1，1）model［J］.Engineering Science，2005，7（2）：58－61（in Chinese）.［方志耕，劉思峰，陸芳，等.區間灰數表征與算法改進及其GM（1，1）模型應用研究 ［J］.中國工程科學，2005，7（2）：58－61.］

［9］LIU Sifen，FANG Zhigeng，Forrest Jeffrey.On algorithm rules of interval grey numbers based on the"kernel"and the degree of greyness of grey numbers ［C］.IEEE International Conference on Systems，Man and Cybernetics，Man and Cybernetics，Istanbul Turkey：IEEE Computer Society，2010：756－760.

［10］MI Chuanmin，LIU Sifeng，XU Yangzi.Study on GSOM model based on interval grey number ［C］.IEEE International Conference on Grey Systems and Intelligent Services.Nanjing China：IEEE Computer Society，2007：1280－1283.