區(qū)間型服務(wù)響應(yīng)時間變化趨勢預(yù)測機(jī)制

景偉娜，陳秋紅，薛 冰

（河南城建學(xué)院 計算機(jī)科學(xué)與工程系，河南 平頂山467036）

0 引 言

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

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

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

雖然區(qū)間型數(shù)據(jù)類型對描述服務(wù)響應(yīng)時間保留了更多的信息，但由于其具備區(qū)間不確定性，傳統(tǒng)的預(yù)測方法如線性回歸、神經(jīng)網(wǎng)絡(luò)等方法需將區(qū)間數(shù)據(jù)轉(zhuǎn)換為確定實數(shù)再進(jìn)行預(yù)測。難以在不損失信息的情況下進(jìn)行預(yù)測。

本文引入?yún)^(qū)間灰數(shù)預(yù)測［8］機(jī)制，在不損失信息的前提下，從區(qū)間型服務(wù)響應(yīng)時間的區(qū)間穩(wěn)定性和區(qū)間上下界值兩方面進(jìn)行預(yù)測，并分析在這兩方面的服務(wù)響應(yīng)時間變化趨勢，為用戶提供更豐富準(zhǔn)確的決策信息。

1 區(qū)間型服務(wù)響應(yīng)時間特性分析

區(qū)間型服務(wù)響應(yīng)時間是某一時間段內(nèi)服務(wù)響應(yīng)時間變化范圍的統(tǒng)計值。比某一時間點服務(wù)響應(yīng)時間的具體值包含了更豐富的信息。為了更好的利用這些信息，不損失有用信息，需首先對區(qū)間型數(shù)據(jù)的特性進(jìn)行分析，判斷在服務(wù)響應(yīng)時間的區(qū)間型數(shù)據(jù)中有哪些有用信息。

為了對區(qū)間型服務(wù)響應(yīng)時間的特性進(jìn)行分析，將連續(xù)時段內(nèi)區(qū)間型服務(wù)響應(yīng)時間的上下界在圖中標(biāo)注出來。如圖1所示，用表示區(qū)間型服務(wù)響應(yīng)時間，同一時間段內(nèi)服務(wù)響應(yīng)時間的上界為bn，下界為an，連續(xù)n段時間段內(nèi)服務(wù)響應(yīng)時間分別為 ［a1，b1］， ［a2，b2］， ［a3，b3］，……，［an－1，bn－1］，［an，bn］。

圖1 區(qū)間型服務(wù)響應(yīng)時間分布

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

設(shè)定服務(wù)響應(yīng)時間的區(qū)間型數(shù)據(jù)A的穩(wěn)定性為Aw，區(qū)間型數(shù)據(jù)的相對大小值為Ad。則對于服務(wù)響應(yīng)時間的區(qū)間型數(shù)據(jù)A和B，

如果Aw＞Bw，且Ad＜Bd，則A優(yōu)于B；

如果Aw＜Bw，且Ad＞Bd，則B優(yōu)于A；

如果Aw＞Bw，且Ad＞Bd則B較優(yōu)于A；

如果Aw＜Bw，且Ad＜Bd則A較優(yōu)于B；

如果Aw＝Bw，且Ad＜Bd則A優(yōu)于B；

如果Aw＝Bw，且Ad＞Bd則B優(yōu)于A；

如果Aw＜Bw，且Ad＝Bd則A優(yōu)于B；

如果Aw＞Bw，且Ad＝Bd則B優(yōu)于A；

穩(wěn)定性與相對大小都是通過區(qū)間型數(shù)據(jù)的上下界值分析得出的，說明區(qū)間型服務(wù)響應(yīng)時間包含的信息不僅僅是邊界值，由一系列區(qū)間型服務(wù)響應(yīng)時間的變化趨勢還包含了服務(wù)響應(yīng)時間波動在一定范圍內(nèi)的分布信息，這種波動分布信息常在現(xiàn)有的數(shù)據(jù)分析過程中進(jìn)行降維時，而損失掉，造成分析的結(jié)果不夠準(zhǔn)確。

用戶期望下一時段的服務(wù)響應(yīng)時間區(qū)間型數(shù)據(jù)更優(yōu)，通過預(yù)測下一時段服務(wù)響應(yīng)時間區(qū)間數(shù)據(jù)的 “穩(wěn)定性”和“相對大小”，則可分析下一時段的服務(wù)響應(yīng)時間是否優(yōu)于上一時段，并可根據(jù)比較結(jié)果選擇服務(wù)響應(yīng)時間更優(yōu)的服務(wù)，或采取相應(yīng)措施以提高服務(wù)的服務(wù)質(zhì)量。更好地滿足用戶的需求。

2 區(qū)間服務(wù)響應(yīng)時間變化趨勢預(yù)測機(jī)制

2.1 區(qū)間型數(shù)據(jù)的信息保留

為了不遺失區(qū)間型服務(wù)響應(yīng)時間的有效信息，從區(qū)間穩(wěn)定性和區(qū)間上下界值兩方面進(jìn)行預(yù)測，以分析其變化趨勢。

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

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

2.2 “穩(wěn)定性”預(yù)測分析

步驟1 將相鄰區(qū)間數(shù)據(jù)間構(gòu)建的四邊形面積作為原始預(yù)測序列

原始預(yù)測序列為

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

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

步驟4 分析區(qū)間數(shù)據(jù) “穩(wěn)定性”與構(gòu)建四邊形面積之間的關(guān)系

當(dāng)p＝1時

當(dāng)p＝2時

由此可推出：

當(dāng)P＝n－1時

步驟5 將式（4）的預(yù)測結(jié)果代入到式（6），

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

步驟6 為了進(jìn)行動態(tài)循環(huán)預(yù)測新樣本，將第K＋1次的實際服務(wù)響應(yīng)時間統(tǒng)計為區(qū)間型數(shù)據(jù)，然后在原預(yù)測樣本S（0）中去掉第一個預(yù)測樣本值S（0）（1），將第K＋1次的樣本值S（0）（K＋1）加入到預(yù)測序列中，構(gòu)成新的預(yù)測樣本：用于下次預(yù)測，重復(fù)步驟1－5，如此動態(tài)更新預(yù)測樣本。

2.3 區(qū)間上下界值預(yù)測

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

步驟2 預(yù)測第K＋1個中心點序列的縱坐標(biāo)，對預(yù)測序列作累減生成得

步驟3 分析中心點序列與區(qū)間數(shù)據(jù)上下界值之間的關(guān)系

當(dāng)P＝1時

當(dāng)P＝2時

由此可推出：

當(dāng)p＝n－1時

步驟4 將式（9）的預(yù)測結(jié)果代入到式（11）

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

步驟5 聯(lián)合式（7）和（12），通過解方程組的形式可得到下一時間段的區(qū)間型服務(wù)響應(yīng)時間上界和下界值

其中

步驟6 獲得K＋1次的實際服務(wù)響應(yīng)時間區(qū)間型數(shù)據(jù)后，求得新的四邊形中心點Ok＋1的縱坐標(biāo)，在原序列W（0）中去掉W（0）（1），加入W（0）（K＋1），構(gòu)成新的動態(tài)序列：

2.4 變化趨勢分析

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

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

3 仿真實驗

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

3.1 區(qū)間服務(wù)響應(yīng)時間預(yù)測誤差評估

在獲取的單位時間段區(qū)間型服務(wù)響應(yīng)時間200組作為預(yù)測原始序列進(jìn)行預(yù)測，按照第2節(jié)中所提算法共預(yù)測300組時段的區(qū)間型服務(wù)響應(yīng)時間。對每相鄰5個區(qū)間型服務(wù)響應(yīng)時間與實際統(tǒng)計的單位時間段內(nèi)區(qū)間型服務(wù)響應(yīng)時間對比，分別求上界和下界殘差，將這相鄰5組的殘差平均值作為1組殘差率。共統(tǒng)計60組預(yù)測殘差率。

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

圖2 服務(wù)響應(yīng)時間預(yù)測值殘差率

3.2 服務(wù)調(diào)用實際響應(yīng)時間比較

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

圖3 服務(wù)響應(yīng)時間比較

從圖3中可以看出，應(yīng)用兩種方法調(diào)用服務(wù)，根據(jù)平均值法和本文預(yù)測機(jī)制預(yù)測結(jié)果所調(diào)用服務(wù)的實際響應(yīng)時間平均值均約為200s，但根據(jù)平均值法所調(diào)用服務(wù)的響應(yīng)時間波動較大，約在區(qū)間 ［100，300］內(nèi)波動，波動跨度為200s。而本文方法所選擇服務(wù)的響應(yīng)時間波動性較小，約在區(qū)間 ［170，230］內(nèi)波動，波動跨度為60s，因而具有更強(qiáng)的穩(wěn)定性，更能有效提高用戶的滿意度。

3.3 預(yù)測樣本數(shù)對預(yù)測效果的影響。

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

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

圖4 預(yù)測樣本數(shù)分析

4 結(jié)束語

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

［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服務(wù)組合策略 ［J］.中國科學(xué)E輯：信息科學(xué)，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服務(wù)組合算法.軟件學(xué)報，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服務(wù)選擇方法 ［J］.計算機(jī)應(yīng)用研究，2010，27（6）：2147－2149.］

［7］LI Na，F(xiàn)ENG 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）.［李娜，馮百明，武小龍.動態(tài)Web服務(wù)合成中的服務(wù)選擇算法研究 ［J］.計算機(jī)工程與設(shè)計，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）.［方志耕，劉思峰，陸芳，等.區(qū)間灰數(shù)表征與算法改進(jìn)及其GM（1，1）模型應(yīng)用研究 ［J］.中國工程科學(xué)，2005，7（2）：58－61.］

［9］LIU Sifen，F(xiàn)ANG Zhigeng，F(xiàn)orrest 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.