基于穩(wěn)態(tài)過程的多重分形Web日志仿真生成算法

彭行雄，肖如良

(1.福建師范大學(xué) 軟件學(xué)院，福州 350117； 2.福建省公共服務(wù)大數(shù)據(jù)挖掘與應(yīng)用工程技術(shù)研究中心，福州 350117)

(*通信作者電子郵箱xiaoruliang@163.com)

基于穩(wěn)態(tài)過程的多重分形Web日志仿真生成算法

彭行雄1,2，肖如良1,2*

(1.福建師范大學(xué) 軟件學(xué)院，福州 350117； 2.福建省公共服務(wù)大數(shù)據(jù)挖掘與應(yīng)用工程技術(shù)研究中心，福州 350117)

(*通信作者電子郵箱xiaoruliang@163.com)

運(yùn)行在服務(wù)器集群的軟件系統(tǒng)需要Web日志的大規(guī)模數(shù)據(jù)集以滿足性能測(cè)試的需求，但現(xiàn)有仿真生成算法因模型單一而無法滿足要求。針對(duì)此問題，提出一種基于alpha穩(wěn)態(tài)過程的多分形Web日志的仿真生成算法。首先,在長相關(guān)尺度(LRD)下采用alpha穩(wěn)態(tài)過程來描述Web日志的自相似性；其次,在短相關(guān)尺度(RSD)下采用二項(xiàng)式b模型描述Web日志的多重分形性;最后,將長相關(guān)模型和短相關(guān)模型融合于改進(jìn)的ON/OFF框架中。與單一的模型相比，新算法的參數(shù)物理意義明確，具有良好的自相似性和多分形性。實(shí)驗(yàn)結(jié)果表明，該算法能夠較準(zhǔn)確地模擬真實(shí)Web日志，可以有效地應(yīng)用于Web日志大規(guī)模數(shù)據(jù)集的仿真生成。

穩(wěn)態(tài)過程；多重分形；自相似；時(shí)間序列；日志分析；仿真生成

0 引言

在Web服務(wù)器性能測(cè)試中，分析Web日志特征對(duì)于服務(wù)器性能評(píng)測(cè)與決策有著重要意義。然而Web日志中包含用戶隱私信息，企業(yè)及政府等機(jī)構(gòu)極少愿意公開日志供研究人員使用；現(xiàn)有已公開的Web日志數(shù)據(jù)年代久遠(yuǎn)，其特征不符合當(dāng)前大數(shù)據(jù)時(shí)代特征[1]。隨著數(shù)據(jù)規(guī)模的增大，生成有代表性卻不失一般性的大規(guī)模數(shù)據(jù)集是有困難的，而單一的傳統(tǒng)仿真模型很難表現(xiàn)出多種復(fù)雜Web日志一般性特征。如何生成仿真且一般性可控的Web日志大規(guī)模數(shù)據(jù)集，是學(xué)術(shù)界的熱點(diǎn)問題，也是本文研究的主題。

以O(shè)N/OFF模型[2]為代表的自相似模型，將自相似過程看成是無數(shù)用戶數(shù)據(jù)源采用獨(dú)立同分布形式疊加的結(jié)果，這種模型能對(duì)自相似現(xiàn)象給出明確的物理解釋，但是在構(gòu)造模型的過程中作了很多前提假設(shè)(如文件大小分布是重尾的[3]，那么訪問文件所需要的時(shí)間也是重尾的)，且這些前提假設(shè)條件常常與實(shí)際情況不相符合，這使得流疊加模型難以對(duì)實(shí)際流量進(jìn)行仿真。隨著非線性動(dòng)力學(xué)的發(fā)展，通過對(duì)Web日志序列的研究，發(fā)現(xiàn)其中含有豐富的非線性特性，因此逐漸開始采用計(jì)算智能的相關(guān)理論進(jìn)行分析，其中以多分形小波模型(Multi-fractal Wavelet Model, MWM)[4]為代表的多重分形模型，通過將Web日志分為高頻和低頻，有效地揭示了突發(fā)性流量的局部較精細(xì)的本質(zhì)特征。但是這類方法建立在重構(gòu)相空間(Web日志模型的非線性特征量的提取及分析)的基礎(chǔ)上，預(yù)測(cè)結(jié)果受相空間形狀的影響，如果參數(shù)選取不合適，就有可能產(chǎn)生較大誤差。

針對(duì)以上問題，本文提出一種模型融合算法：基于穩(wěn)態(tài)過程的多重分形Web日志仿真生成算法(Multi-Fractal Web log simulation algorithm based on Stable process, MFWS)。MFWS將alpha穩(wěn)態(tài)模型與二項(xiàng)式b模型融合，不僅能夠更加準(zhǔn)確地模擬Web日志的高斯性、非高斯性以及多分形性等特征，而且其參數(shù)的物理意義明確，能夠很好地應(yīng)用于不同Web服務(wù)器平臺(tái)。

1 相關(guān)工作

為了有效地仿真生成Web日志，已經(jīng)有很多相關(guān)的研究。當(dāng)前模擬生成的方法主要是自相似方法和多重分形方法，具體如下：

1)在自相似方法中，通過模擬突發(fā)性特征來生成Web日志。其中，被不少研究者采用的ON/OFF模型[2]結(jié)構(gòu)簡(jiǎn)單，具有明確物理意義，構(gòu)造的每一個(gè)過程都能找到原型；然而在構(gòu)造過程中作了一定假設(shè)，與實(shí)際流量不符，而且還忽略了很多細(xì)節(jié)。分形布朗運(yùn)動(dòng)(Fractional Brownian Motion, FBM)[5]模型雖然易于處理，參數(shù)簡(jiǎn)單，且能在高斯條件下描述自相似性，但是只適用于高斯分布情況，而且無法同時(shí)描述長相關(guān)尺度(Long Range Dependence, LRD)和短相關(guān)尺度(Short Range Dependence, SRD)[5]。M/G/∞排隊(duì)模型[6]能夠描述短相關(guān)性，但是需要在計(jì)算量和計(jì)算精度之間進(jìn)行折中。分形自回歸滑動(dòng)平均(Fractional Auto-Regressive Integrated Moving Average, FARIMA)模型[7]雖然靈活，能夠同時(shí)描述長相關(guān)性和短相關(guān)性，但過于復(fù)雜，仿真運(yùn)算量太大，且對(duì)負(fù)載中的突發(fā)性缺乏表述。

2)在多重分形方法中，通過擴(kuò)展單分形自相似過程來模擬小時(shí)間尺度的Web日志突發(fā)性特征。二項(xiàng)式b模型[8]首先用于存儲(chǔ)系統(tǒng)的流量仿真。它通過偏差參數(shù)b來描述局部突發(fā)行為，將單位時(shí)間內(nèi)的流量二項(xiàng)式分解來達(dá)到多分形的目的，有參數(shù)少、模型簡(jiǎn)單的優(yōu)點(diǎn)。Hong等[9]推薦在一個(gè)相對(duì)較小的時(shí)間范圍用二項(xiàng)式b模型合成流量，雖然提高了模擬的精度，但是沒有在長時(shí)間范圍生成流量。MWM模型[4]基于多分形小波理論對(duì)流量信號(hào)進(jìn)行多尺度特性分析，通過設(shè)定限制方式，巧妙地避免了仿真流量出現(xiàn)負(fù)值的問題；但是在構(gòu)造小波系數(shù)和尺度系數(shù)之間的隨意乘法因子時(shí)，沒有根據(jù)實(shí)際流量的概率密度特征進(jìn)行分析，缺乏真實(shí)性，且難以調(diào)整。因此有研究者以一定規(guī)律來產(chǎn)生乘法因子，如文獻(xiàn)[10]提出一種改進(jìn)的MWM方法，提出一個(gè)β模型來初始化乘法因子提高仿真性能，但參數(shù)物理意義不足。

在以上各項(xiàng)工作中，構(gòu)造模型的過程中采用最頻繁的分布規(guī)律為重尾分布中的Pareto規(guī)律來作為分布原型。然而，無法確認(rèn)流量數(shù)據(jù)是否真的符合Pareto分布。文獻(xiàn)[11]指出隨著網(wǎng)絡(luò)媒體的多樣化、緩存技術(shù)的提升，廣延指數(shù)(StretchedExponential,SE)分布[11]能更加準(zhǔn)確地描述Web日志特征，然而其參數(shù)卻不容易確定，而且沒有考慮流量的非高斯性。文獻(xiàn)[12]在用戶行為分形建模時(shí)發(fā)現(xiàn)Web日志符合alpha穩(wěn)態(tài)[13]，此外alpha穩(wěn)態(tài)包含4個(gè)參數(shù)，每個(gè)均有相應(yīng)的物理意義，這使得研究人員可以針對(duì)不同的應(yīng)用環(huán)境很方便地轉(zhuǎn)換流量模型。由于alpha穩(wěn)態(tài)只存在特征函數(shù)，卻沒有具體的分布函數(shù)，這為仿真帶來了困難。但是文獻(xiàn)[13]中采用逼近法模擬alpha穩(wěn)態(tài)得到了近似分布函數(shù)，這為alpha穩(wěn)態(tài)的使用帶來了方便。

綜上所述，自相似方法和多重分形方法各有優(yōu)缺點(diǎn)，本文借鑒這兩類方法的優(yōu)點(diǎn)，將流量序列分為長相關(guān)過程和短相關(guān)過程，考慮到Web日志的多樣性，選擇具有物理意義的模型進(jìn)行構(gòu)造；其中長相關(guān)過程采用alpha穩(wěn)態(tài)來模擬Web日志自相似的高斯和非高斯特性，短相關(guān)過程采用二項(xiàng)式b模型來模擬Web日志的多重分形特征，在改進(jìn)的ON/OFF模型的基礎(chǔ)上提出一種模型融合算法——MFWS，以此達(dá)到提高Web日志仿真性能的目標(biāo)。

2 理論基礎(chǔ)

2.1 alpha穩(wěn)態(tài)

文獻(xiàn)[14]研究表明：對(duì)于不同的Web服務(wù)器，Web日志到達(dá)模型分為獨(dú)立同分布和自相似性兩種；而且，即使同樣具有自相似性，有的Web日志具有高斯性，而有的Web日志體現(xiàn)出非高斯性。于是文獻(xiàn)[14]發(fā)現(xiàn)用alpha穩(wěn)態(tài)來描述Web日志特征更加合理。之所以alpha穩(wěn)態(tài)具有準(zhǔn)確的仿真性能，是因?yàn)橄鄬?duì)于傳統(tǒng)方法使用的冪律分布，alpha穩(wěn)態(tài)更適合于描述Web日志。隨著對(duì)大量數(shù)據(jù)的調(diào)查[11]發(fā)現(xiàn)，所謂的冪律僅僅適用于分布曲線的尾端部分(x軸遠(yuǎn)離原點(diǎn)位置)。另外文獻(xiàn)[15]中利用美國真實(shí)稅收情況估計(jì)出的收入分布曲線也表明：當(dāng)取雙對(duì)數(shù)坐標(biāo)時(shí)，曲線尾端是直線，即冪律分布；當(dāng)取半對(duì)數(shù)(y軸為對(duì)數(shù))時(shí)，曲線頂端為直線，即指數(shù)分布。數(shù)學(xué)家Nolan[13]指出alpha穩(wěn)態(tài)分布正好具備這種尾端趨近于冪律分布，而在頭端(x軸靠近原點(diǎn)位置)偏離冪律、趨向于指數(shù)分布的性質(zhì)。即：一個(gè)隨機(jī)變量X被稱為具有穩(wěn)定分布，若存在參數(shù)0<α≤2，σ>0，-1≤β≤1，μ∈R，使得其特征函數(shù)E的形式如式(1)所示：

E[exp(iθX)]=

(1)

式中:sign(·)為符號(hào)函數(shù)。文獻(xiàn)[14]發(fā)現(xiàn)：α表示分布中的突發(fā)程度，β表示分布的尾部變化情況。如果β≠0，說明alpha穩(wěn)態(tài)的波峰是偏斜的：取負(fù)值表示alpha穩(wěn)態(tài)的波峰偏向左尾部(left-tail)；反之，取正值則表示alpha穩(wěn)態(tài)的波峰偏向右尾部(right-tail)。因此參數(shù)α和β決定了alpha穩(wěn)態(tài)的基本形狀。σ表示分布的方差，μ表示分布的均值，j表示X的第j個(gè)特征。由式(1)可知，當(dāng)α=2時(shí)，得式(2)：

E[exp(iθX)]=exp(-σ2θ2+jμθ)

(2)

此時(shí)，alpha穩(wěn)態(tài)的特征函數(shù)E退化為高斯特征函數(shù)。因此隨著α取值的不同，alpha穩(wěn)定過程可以表示高斯和非高斯情況下的隨機(jī)過程。此外，alpha穩(wěn)態(tài)包含4個(gè)參數(shù)，每個(gè)均具有相應(yīng)的物理意義，這使得研究人員可以針對(duì)不同的應(yīng)用環(huán)境很方便地轉(zhuǎn)換仿真模型。雖然alpha穩(wěn)態(tài)沒有分布函數(shù)，但是可以使用Matlab軟件中的stbl工具來進(jìn)行模擬，這為模擬Web日志的到達(dá)模型提供了方便。

2.2 二項(xiàng)式b模型

(3)

(4)

二項(xiàng)式b模型近似于“二八定律”：20%的操作中包含80%的數(shù)據(jù)。在二項(xiàng)式b模型中，如偏置參數(shù)b=0.8意味著在一個(gè)給定的時(shí)間間隔內(nèi)，80%的流量只占時(shí)間間隔的一半(剩余20%占時(shí)間間隔的另一半)。然后這個(gè)過程反復(fù)遞歸，通過偏置參數(shù)b反映流量的局部突發(fā)行為，因此偏置參數(shù)b具有一定的物理意義。在實(shí)際中使偏置參數(shù)b為0.5到1之間的隨機(jī)數(shù)，這樣能增加分形的復(fù)雜性。

3 基于alpha穩(wěn)態(tài)過程的用戶到達(dá)模型

在選用alpha穩(wěn)態(tài)過程作為Web日志建模依據(jù)之前，需要對(duì)實(shí)際的Web日志數(shù)據(jù)進(jìn)行測(cè)量分析，以驗(yàn)證采用alpha穩(wěn)態(tài)過程的合理性。對(duì)1995年美國國家航天航空局(NationalAeronauticsandSpaceAdministration，NASA)網(wǎng)站的八月份1 569 898條請(qǐng)求序列和MovieLens-1M的1 000 209條電影評(píng)分日志進(jìn)行統(tǒng)計(jì)，圖1表示用戶到達(dá)數(shù)量與時(shí)間間隔關(guān)系Rel，橫坐標(biāo)為兩個(gè)用戶之間的時(shí)間間隔(100ms)，縱坐標(biāo)為時(shí)間間隔內(nèi)到達(dá)的用戶數(shù)量?？梢钥闯龃蟛糠钟脩粼诤芏虝r(shí)間間隔內(nèi)到達(dá)，而少部分用戶是相隔很長一段時(shí)間才能到達(dá)。對(duì)圖1的橫縱坐標(biāo)取對(duì)數(shù)，這兩個(gè)數(shù)據(jù)集的雙對(duì)數(shù)曲線如圖2所示，可以看出在雙對(duì)數(shù)坐標(biāo)下，Rel曲線頭部(靠近坐標(biāo)原點(diǎn))為曲線，尾部(遠(yuǎn)離坐標(biāo)原點(diǎn))大致為直線；對(duì)圖1的縱坐標(biāo)取對(duì)數(shù)，其半對(duì)數(shù)曲線如圖3所示，可以看出在半對(duì)數(shù)坐標(biāo)下，Rel曲線頭部大致為直線，尾部為曲線(當(dāng)出現(xiàn)大量縱坐標(biāo)值相等時(shí)，取其中點(diǎn)的橫坐標(biāo)值)。因此Rel是一種頭部為指數(shù)分布，尾部為冪律分布的曲線，這是符合alpha穩(wěn)態(tài)過程的[13]。

可以使用stbl工具的stblfit函數(shù)擬合此數(shù)據(jù)集參數(shù)，接著生成符合這兩個(gè)參數(shù)模型的alpha穩(wěn)態(tài)隨機(jī)數(shù)集合，將此隨機(jī)數(shù)集合與兩個(gè)數(shù)據(jù)集用戶到達(dá)模式累積概率分布進(jìn)行比較，結(jié)果如圖4所示。由圖4可以發(fā)現(xiàn)alpha穩(wěn)態(tài)與兩個(gè)源數(shù)據(jù)集的累積概率分布差異不大，因此可以模擬基于alpha穩(wěn)態(tài)過程的用戶到達(dá)(UserArrivebasedonalphaStableprocess，UAS)模型獲得alpha穩(wěn)態(tài)過程的4個(gè)參數(shù)，如表1所示。

為了體現(xiàn)出參數(shù)的物理意義，圖5(a)中NASA數(shù)據(jù)集的突發(fā)性更為均勻，圖形平緩，而圖5(b)中MovieLens-1M數(shù)據(jù)集的突發(fā)性更為集中，圖形陡峭，因此NASA的α更大；其次兩個(gè)數(shù)據(jù)集的概率密度分布曲線都向右偏，因此β>0。從圖5的數(shù)據(jù)分布情況來看也不難解釋兩個(gè)數(shù)據(jù)集的方差σ和均值μ的差異性。

圖1 不同數(shù)據(jù)集用戶到達(dá)數(shù)量與時(shí)間間隔關(guān)系分布

圖2 不同數(shù)據(jù)集用戶到達(dá)數(shù)量與時(shí)間間隔關(guān)系雙對(duì)數(shù)分布

圖3 不同數(shù)據(jù)集用戶到達(dá)數(shù)量與時(shí)間間隔關(guān)系半對(duì)數(shù)分布

圖4 原始數(shù)據(jù)集與alpha模擬數(shù)據(jù)集累積概率分布對(duì)比

表1alpha穩(wěn)態(tài)過程的擬合參數(shù)

Tab.1Fittingparametersofthealphasteadystateprocess

數(shù)據(jù)集αβσμN(yùn)ASA1．790．9310．8328．40MovieLens?1M1．060．900．9311．49

圖5 不同數(shù)據(jù)集用戶到達(dá)模式分布情況

然后使用stbl工具的stblinv函數(shù)隨機(jī)獲取用戶到達(dá)時(shí)間間隔序列ΔT={ΔT1, ΔT2,…, ΔTu,…, ΔTm}，其中m表示有m個(gè)用戶，用戶u距離用戶u-1的到達(dá)時(shí)間間隔為ΔTu。為了使ΔT更真實(shí)，改進(jìn)ΔT如式(5)所示：

ΔT=ΔT/ln (1+Actu)

(5)

對(duì)于活躍度高的用戶u，其ΔTu通常很小，這樣會(huì)造成短時(shí)間內(nèi)同一個(gè)用戶頻繁訪問，因此給出對(duì)ΔT的懲罰因子1/ln(1+Actu),其中Actu表示用戶u的流行度。

4 基于UAS的算法——MFWS

在單分形模型中，ON/OFF模型因其構(gòu)造簡(jiǎn)單而受到廣泛使用，然而其假設(shè)存在與真實(shí)流量不符合的現(xiàn)象，因此本文提出一種基于UAS的多重分形Web日志仿真算法——MFWS，改進(jìn)ON/OFF模型如圖6所示。

圖6中Tu時(shí)刻表示某Web日志中某用戶u到達(dá)(發(fā)生點(diǎn)擊事件)的時(shí)刻,T(u+1)時(shí)刻表示用戶u訪問結(jié)束，下一個(gè)用戶u+1到達(dá)的時(shí)刻，將兩次用戶到達(dá)時(shí)刻之間的時(shí)間間隔ΔTu稱為用戶間隔，也稱為Web對(duì)象被動(dòng)OFF時(shí)間。用戶的一次點(diǎn)擊行為引發(fā)服務(wù)器發(fā)送多個(gè)Web文件，第i個(gè)文件和第i+1個(gè)文件在傳輸?shù)倪^程中由于網(wǎng)絡(luò)延遲等[11]造成訪問時(shí)間間隔Δti，也稱為主動(dòng)OFF時(shí)間。

圖6 改進(jìn)后的ON/OFF模型

根據(jù)第3章的方法可以使用alpha穩(wěn)態(tài)分布生成用戶間隔ΔT,對(duì)于文件間隔Δt,傳統(tǒng)的做法是采用冪律分布來建立數(shù)學(xué)模型[16]，然而在Web服務(wù)器端收集到的用戶訪問Web文件時(shí)間僅為Web服務(wù)器發(fā)送Web文件時(shí)間，卻沒有用戶訪問Web時(shí)間。不同的Web服務(wù)器性能也會(huì)導(dǎo)致這種數(shù)學(xué)模型缺乏一般性，同時(shí)也無法表現(xiàn)出Web日志的多重分形特性。在實(shí)際中，主動(dòng)OFF時(shí)間比被動(dòng)OFF時(shí)間小很多，屬于小時(shí)間尺度，根據(jù)Hong等[9]的研究，本文認(rèn)為同樣也可以將二項(xiàng)式b模型用在小時(shí)間尺度的Web日志中。改進(jìn)方法為在ON/OFF模型模擬文件間隔Δt時(shí)采用二項(xiàng)式b模型，具體做法如下：

對(duì)NASA網(wǎng)站數(shù)據(jù)進(jìn)行分析發(fā)現(xiàn)，用戶發(fā)出連續(xù)動(dòng)作次數(shù)概率近似服從Zipf定律[16]。假設(shè)用戶u的總請(qǐng)求序列是Sequ={sequ1,sequ2,…，sequi}，其中rui為用戶u訪問的第i個(gè)Web文件，則第i個(gè)Web文件被訪問的概率為p(rui)=iω，利用最小二乘法擬合可得ω=-0.924。這個(gè)結(jié)果與ω=-1 的Zipf 定律非常接近。由此可知在Web對(duì)象中，用戶連續(xù)訪問2個(gè)以上Web文件的概率低于60%，而用戶連續(xù)訪問16個(gè)以上Web文件的概率已經(jīng)非常接近于0。文獻(xiàn)[8]指出將時(shí)間ΔTu內(nèi)的流量進(jìn)行n次分離即是二項(xiàng)式分形，但實(shí)際中的n存在限制。根據(jù)二項(xiàng)式b模型的偏置參數(shù)b∈(0.5,1)，不可能存在用戶連續(xù)訪問的16個(gè)文件都能獨(dú)占一個(gè)時(shí)間區(qū)間，從而二項(xiàng)式分離次數(shù)0≤n≤4。

當(dāng)確定用戶u的連續(xù)訪問序列長度s后，從Sequ中取出前s個(gè)Web文件，組成用戶u當(dāng)前連續(xù)訪問序列Yu，隨機(jī)選擇二項(xiàng)式分離次數(shù)n，對(duì)每個(gè)用戶到達(dá)時(shí)間間隔ΔTu以及連續(xù)訪問的文件序列Yu，建立一棵高度為n+1的滿二叉樹Treeu,將ΔTu分為z=2n個(gè)相等區(qū)間，根據(jù)式(3)和(4)計(jì)算每個(gè)區(qū)間內(nèi)的Web文件數(shù)量，先序遍歷Treeu的葉子節(jié)點(diǎn)組成的時(shí)間序列Yu′={yu1′,yu2′,…,yut′,…,yuz′}，其中yut′表示第t個(gè)時(shí)間區(qū)間內(nèi)用戶訪問的Web文件數(shù)量,用戶訪問Web文件時(shí)間為ΔTu+t*ΔTu/z，則Yu′是用戶u的一個(gè)含有多分形特性的Web對(duì)象。

基于以上分析，本文提出一種基于UAS的多重分形Web日志仿真算法——MFWS。該算法通過改進(jìn)ON/OFF模型，利用alpha穩(wěn)態(tài)過程模擬用戶到達(dá)時(shí)間間隔ΔT，利用二項(xiàng)式b模型模擬用戶連續(xù)訪問Web文件時(shí)間間隔Δt，算法流程如下：

1)生成每個(gè)用戶u的屬性并形成集合U。

2)生成每個(gè)文件i的屬性并形成集合I。

3)關(guān)聯(lián)用戶和文件形成原始請(qǐng)求序列Seq。

4)以alpha穩(wěn)態(tài)擬合源數(shù)據(jù)集的用戶到達(dá)模式,計(jì)算用戶u的到達(dá)時(shí)間ΔT作為改進(jìn)的ON/OFF模型的被動(dòng)OFF時(shí)間。

5)將Seq變成用戶請(qǐng)求序列Sequ,遍歷u,記錄算法開始時(shí)間currentTime。

6)判斷是否收斂，是則算法結(jié)束；否則判斷Sequ是否為空，為空轉(zhuǎn)5)，不為空則轉(zhuǎn)7)。

7)找到連續(xù)訪問個(gè)數(shù)s=1。

8)取出Sequ的前s個(gè)文件構(gòu)成連續(xù)訪問序列Y。

9)以二項(xiàng)式b模型分離Y為連續(xù)訪問時(shí)間序列Y′，并以Y′的每個(gè)元素的Δt作為改進(jìn)ON/OFF模型的主動(dòng)OFF時(shí)間。

10)將序列Y′加入到用戶的新訪問序列Sequ′中。

11)從Sequ中刪除前s個(gè)文件序列，轉(zhuǎn)6)。

5 實(shí)驗(yàn)與結(jié)果分析

5.1 數(shù)據(jù)集

在生成Web日志之后需要觀察模擬Web日志的仿真性能，采用真實(shí)數(shù)據(jù)集作為參照比對(duì)。實(shí)驗(yàn)采用NASA數(shù)據(jù)集以及MovieLens-1M電影評(píng)分?jǐn)?shù)據(jù)集,其中NASA為31天采集的1 569 898條日志數(shù)據(jù)；MovieLens-1M為6 040個(gè)用戶對(duì)3 952個(gè)電影的1 000 209條評(píng)分記錄。

5.2 結(jié)果分析

5.2.1Hurst指數(shù)分析

由自相似性的定義[3]知，要驗(yàn)證生成的Web日志是否滿足自相似過程，必須滿足自相關(guān)函數(shù)r(m)(k)=r(k)～αk-β，0<β<1,H=2-2β且H∈(0.5,1)。其中α和β為自相關(guān)函數(shù)參數(shù)，H為Hurst指數(shù)。Hurst指數(shù)值越接近于1，說明Web日志具有較強(qiáng)的自相似性?？疾煺鎸?shí)數(shù)據(jù)集與模擬數(shù)據(jù)集的Hurst指數(shù)對(duì)比情況，按照不同時(shí)間間隔來獲取不同時(shí)間尺度下的請(qǐng)求序列，最后用Hurst指數(shù)來估計(jì)各個(gè)不同時(shí)間尺度序列的自相似特性。將真實(shí)數(shù)據(jù)集的Hurst指數(shù)記為real_Hurst，將MFWS模擬數(shù)據(jù)集的Hurst指數(shù)記為MFWS_Hurst，將Web代理緩存生成器(WorkloadGenerationtoolforWebProxycaches,PWG)算法[16]模擬數(shù)據(jù)集的Hurst指數(shù)記為PWG_Hurst。如表2所示，可以發(fā)現(xiàn)對(duì)于每個(gè)真實(shí)數(shù)據(jù)集，隨著時(shí)間尺度增大，real_Hurst在減小。這是因?yàn)殡S著時(shí)間尺度的增大，自相似系數(shù)r(k)的取值變少，在擬合的過程中，也就造成擬合效果不佳。

通過表2還可以看出，算法MFWS和PWG都有較好的自相似性(Hurst指數(shù)大于0.5)，但是通過將這兩個(gè)算法的Hurst指數(shù)值與真實(shí)數(shù)據(jù)的Hurst指數(shù)值對(duì)比，可以發(fā)現(xiàn)MFWS的Hurst指數(shù)與真實(shí)數(shù)據(jù)集更加接近，這是因?yàn)镻WG算法采用的是冪律分布，在模擬不同類型數(shù)據(jù)集時(shí)不如alpha穩(wěn)態(tài)分布合適，這說明MFWS具有更加良好的自相似性。

表2 不同時(shí)間尺度下的Hurst指數(shù)比較

5.2.2 分形譜評(píng)估

分形譜是Web日志模型在多重分形尺度上的本質(zhì)體現(xiàn)，因而分形譜是衡量多重分形模型好壞的一項(xiàng)重要標(biāo)準(zhǔn)[17]。將兩個(gè)真實(shí)數(shù)據(jù)集(real)和利用MWFS算法模擬產(chǎn)生的數(shù)據(jù)集(MWFS)的分形譜進(jìn)行對(duì)比分析；另外，為了使實(shí)驗(yàn)更有說服力，將多分形小波算法的模擬數(shù)據(jù)集(MWM)也作為實(shí)驗(yàn)對(duì)比參照。α表示holder指數(shù)，f(α)表示奇異譜，以隨機(jī)抽樣的方式任意抽取這三個(gè)數(shù)據(jù)集中1 s內(nèi)的Web日志，分形譜實(shí)驗(yàn)對(duì)比結(jié)果如圖7所示。

圖7 真實(shí)數(shù)據(jù)集與模擬數(shù)據(jù)集分型譜對(duì)比

由圖7可以看出，在α=1.1時(shí)，源數(shù)據(jù)集以及兩種算法模擬的數(shù)據(jù)集的奇異譜非常相似，但是在α=1.1的兩邊，只有MWFS算法的模擬數(shù)據(jù)集更加接近于源數(shù)據(jù)集，說明MWFS算法在多分形譜描述上要優(yōu)于MWM模型[16]，與實(shí)際流量分形譜更為接近，能更準(zhǔn)確地描述真實(shí)流量的多分形特性。

5.2.3 概率密度曲線的評(píng)估

分析數(shù)據(jù)集的用戶到達(dá)模式概率密度分布，是為了驗(yàn)證仿真生成的數(shù)據(jù)集的用戶到達(dá)模型是否符合實(shí)際數(shù)據(jù)集用戶到達(dá)模式概率密度分布，體現(xiàn)MWFS算法的真實(shí)性。由圖8可知，兩個(gè)不同數(shù)據(jù)集的概率密度分布與仿真數(shù)據(jù)集的概率密度分布非常相似，說明仿真效果良好；其次，仿真數(shù)據(jù)具有很明顯的重尾特征，這與真實(shí)情況相符。因此，MWFS算法仿真數(shù)據(jù)集符合原始數(shù)據(jù)集的用戶到達(dá)模式特征。

通過對(duì)比真實(shí)數(shù)據(jù)集和模擬數(shù)據(jù)集的自相似特征、多分形特征和用戶到達(dá)模式特征，可以發(fā)現(xiàn)MWFS算法具有較好的仿真性能，并且第3章中給出的各項(xiàng)參數(shù)物理意義明確，能夠反映真實(shí)數(shù)據(jù)集特征。雖然MWFS算法仿真性能良好，但是由于采用的ON/OFF模型是一種流疊加模型，其時(shí)間復(fù)雜度也隨著要生成的模擬數(shù)據(jù)集量級(jí)呈線性增長；另外，二項(xiàng)式b模型在創(chuàng)建和遍歷二叉樹時(shí)也會(huì)消耗大量時(shí)間。然而，MWFS得到的ΔT屬于每個(gè)用戶的固有屬性，對(duì)每個(gè)用戶的ΔT的多分形過程作為一次ON/OFF源，這為多個(gè)ON/OFF源的并發(fā)執(zhí)行提供了可能，在運(yùn)行時(shí)間上勢(shì)必會(huì)有所減少。

圖8 不同數(shù)據(jù)集用戶到達(dá)模式的概率密度分布

6 結(jié)語

自相似性和多分形性是Web日志仿真的關(guān)鍵，本文提出一種基于穩(wěn)態(tài)過程的多分形Web日志仿真生成算法MWFS，它以alpha穩(wěn)態(tài)模型代替冪律模型在大時(shí)間尺度下建立Web日志中的用戶到達(dá)模型，同時(shí)以二項(xiàng)式b模型在小時(shí)間尺度下進(jìn)行二項(xiàng)式分形，將這兩個(gè)模型通過改進(jìn)的ON/OFF模型進(jìn)行融合。實(shí)驗(yàn)表明，MWFS算法同時(shí)具備良好的自相似性和多分形性；同時(shí)MWFS的各項(xiàng)參數(shù)物理意義明確，能夠方便研究人員應(yīng)用于不同的Web服務(wù)器上。如何實(shí)現(xiàn)并行化仿真生成是下一步要做的工作。

References)

[1] CALZAROSSA M C, MASSARI L, TESSERA D.Workload characterization: a survey revisited [J].ACM Computing Surveys, 2016, 48(3): Article No.48.

[2] CROVELLA M E, BESTAVROS A.Self-similarity in World Wide Web traffic: evidence and possible causes [J].IEEE/ACM Transactions on Networking, 1997, 5(6): 835-846.

[3] SARLA P, DOODIPALA M R, DINGARI M.Self-similarity analysis of Web users arrival pattern at selected Web centers [J].American Journal of Computational Mathematics, 2016, 6(1): 17-22.

[4] RIEDI R H, CROUSE M S, RIBEIRO V J, et al.A multifractal wavelet model with application to network traffic [J].IEEE Transactions on Information Theory, 1999, 45(3): 992-1018.

[5] 張雪媛,王永剛,張瓊.基于分?jǐn)?shù)布朗運(yùn)動(dòng)的自相似流量判別及生成方法[J].計(jì)算機(jī)應(yīng)用,2013,33(4):947-949,963.(ZHANG X Y, WANG Y G, ZHANG Q.Self-similar traffic discrimination and generating methods based on fractal Brown motion [J].Journal of Computer Applications, 2013, 33(4): 947-949, 963.)

[6] GOMEZ M E, SANTONJA V.Analysis of self-similarity in I/O workload using structural modeling [C]// Proceedings of the 1999 7th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems.Piscataway, NJ: IEEE, 1999: 234.

[7] LELAND W E, TAQQU M S, WILLINGER W, et al.On the self-similar nature of Ethernet traffic [C]// SIGCOMM’93: Proceedings of the 1993 Conference proceedings on Communications Architectures, Protocols and Applications.New York: ACM, 1993: 183-193.

[8] WANG M Z, MADHYASTHA T, CHAN N H, et al.Data mining meets performance evaluation: fast algorithms for modeling bursty traffic [C]// ICDE’02: Proceedings of the 18th International Conference on Data Engineering.Washington, DC: IEEE Computer Society, 2002: 507.

[9] HONG B, MADHYASTHA T M.The relevance of long-range dependence in disk traffic and implications for trace synthesis [C]// Proceedings of the 22nd IEEE / 13th NASA Goddard Conference on Mass Storage Systems and Technologies.Piscataway, NJ: IEEE, 2005: 316-326.

[10] WEN J, MA Y, LIU P, et al.Distributed multipliers in MWM for analyzing job arrival processes in massive HPC workload datasets [J].Future Generation Computer Systems, 2014, 37(7): 335-344.

[11] GUO L, TAN E, CHEN S, et al.The stretched exponential distribution of Internet media access patterns [C]// PODC’08: Proceedings of the Twenty-Seventh ACM Symposium on Principles of Distributed Computing.New York: ACM, 2008: 283-294.

[12] CHEN S, GHORBANI M, WANG Y Z, et al.Trace-based analysis and prediction of cloud computing user behavior using the fractal modeling technique [C]// Proceedings of the 2014 IEEE International Congress on Big Data (BigData Congress).Piscataway, NJ: IEEE, 2014: 733-739.

[13] NOLAN J P.Stable distributions: models for heavy tailed data [EB/OL].[2016- 01- 30].https://www.researchgate.net/publication/247635151_Stable_Distribution_Models_for_Heavy-Tailed_data.

[14] 鄒強(qiáng),程強(qiáng).存儲(chǔ)系統(tǒng)負(fù)載自相似性研究綜述[J].計(jì)算機(jī)科學(xué),2013,40(3):24-30.(ZOU Q, CHENG Q.Survey of studies on self-similarity in storage system workload [J].Computer Science, 2013, 40(3): 24-30.)

[16] BUSARI M, WILLIAMSON C.ProWGen: a synthetic workload generation tool for simulation evaluation of Web proxy caches [J].Computer Networks, 2002, 38(6): 779-794.

[17] THOMPSON J R, WILSON J R.Multifractal detrended fluctuation analysis: practical applications to financial time series [J].Mathematics and Computers in Simulation, 2016, 126(C): 63-88.

This work is partially supported by the Fujian Provincial Great Plan Project (2016H6007).

PENG Xingxiong, born in 1991, M.S.candidate.His research interests include machine learning.

XIAO Ruliang, born in 1966, Ph.D., professor.His research interests include software engineering, new technology of big data software.

Multi-fractal Web log simulation generation algorithm based on stable process

PENG Xingxiong1,2, XIAO Ruliang1,2*

(1.FacultyofSoftware，F(xiàn)ujianNormalUniversity,FuzhouFujian350117,China; 2.FujianProvincialEngineeringResearchCenterofPublicServiceBigDataAnalysisandApplication,FuzhouFujian350117,China)

The software system running on the server cluster needs large-scale data sets of Web log to meet the performance test requirement, but the existing simulation generation algorithm cannot meet the requirements due to the single model.Aiming at this problem, a new multi-fractal Web log simulation generation algorithm based on alpha stable process was proposed.Firstly, the self-similarity of Web log was described by alpha stable process in Long Range Dependence (LRD).Secondly, the multi-fractal of Web log was described by binomial-bmodel in Short Range Dependence (SRD).Finally, the model of long range dependence and the model of short range dependence were integrated into the improved ON/OFF framework.Compared with the single model, the parameters of the proposed algorithm has clear physical meaning equipped with good performance of self-similarity and multi-fractal.The experimental results show that the proposed algorithm can accurately simulate the real Web log and be effectively applied in Web log simulation generation with large-scale data sets.

stable process; multi-fractal; self-similarity; time series; log analysis; simulation generation

2016- 06- 14;

2016- 08- 18。 基金項(xiàng)目:福建省高校產(chǎn)學(xué)合作項(xiàng)目(2016H6007)。

彭行雄(1991—)，男，湖北孝感人，碩士研究生，主要研究方向：機(jī)器學(xué)習(xí)； 肖如良(1966—)，男，湖南婁底人，教授，博士，CCF高級(jí)會(huì)員，主要研究方向：軟件工程、大數(shù)據(jù)軟件新技術(shù)。

1001- 9081(2017)02- 0587- 06

10.11772/j.issn.1001- 9081.2017.02.0587

TP

A