一種基于改進(jìn)隱馬爾可夫的多媒體業(yè)務(wù)分類算法

王再見董育寧張 暉馮友宏

①(南京郵電大學(xué)通信與信息工程學(xué)院 南京 210003)

②(安徽師范大學(xué)物理與電子信息學(xué)院 蕪湖 241000)

一種基于改進(jìn)隱馬爾可夫的多媒體業(yè)務(wù)分類算法

王再見*①②董育寧①張 暉①馮友宏②

①(南京郵電大學(xué)通信與信息工程學(xué)院 南京 210003)

②(安徽師范大學(xué)物理與電子信息學(xué)院 蕪湖 241000)

該文提出一種基于改進(jìn)隱馬爾可夫(Hidden Markov Model, HMM)的多媒體業(yè)務(wù)分類算法。改進(jìn)后的算法保持典型HMM模型結(jié)構(gòu)不變，通過區(qū)分包大小的位置信息，改變發(fā)射概率取值，提高了多媒體業(yè)務(wù)區(qū)分性能。理論分析表明，該文模型在計(jì)算量上低于高階HMM；實(shí)驗(yàn)結(jié)果表明，改進(jìn)的HMM多媒體業(yè)務(wù)分類算法的區(qū)分效果優(yōu)于現(xiàn)有的HMM多媒體業(yè)務(wù)分類方法。

多媒體業(yè)務(wù)流識(shí)別；隱馬爾可夫；發(fā)射概率；包大小

1 引言

端到端QoS(Quality of Service)保證領(lǐng)域的網(wǎng)絡(luò)多媒體業(yè)務(wù)的分類，關(guān)注的是QoS特征而不是業(yè)務(wù)具體內(nèi)容，希望用較少的QoS特征區(qū)分業(yè)務(wù)所歸屬的QoS/業(yè)務(wù)類。典型的基于端口或深度包檢測(cè)的業(yè)務(wù)分類方法在效率、安全等方面存在不足。一些機(jī)器學(xué)習(xí)方法由于分類的復(fù)雜度較高，影響了分類實(shí)時(shí)性。因此，近年來有大量工作，研究如何基于可觀察的QoS特征狀態(tài)，準(zhǔn)確、高效地識(shí)別被隱藏的QoS/業(yè)務(wù)類別[1]。

HMM(Hidden Markov Model)近年來取得較多的研究成果。文獻(xiàn)[2-5]都基于典型HMM分類方法識(shí)別網(wǎng)絡(luò)業(yè)務(wù)流，規(guī)避了傳統(tǒng)識(shí)別/分類方法存在的法律問題等不足，但識(shí)別效果有待進(jìn)一步提高，部分原因是由于HMM中對(duì)隱式序列的一階假定有很大的局限性，發(fā)射概率是隨機(jī)的。但事實(shí)上，網(wǎng)絡(luò)多媒體業(yè)務(wù)中用于區(qū)分的特征，其所構(gòu)成的觀測(cè)序列不僅依賴于隱藏序列現(xiàn)在的狀態(tài)，與過去的狀態(tài)也有關(guān)，且常常存在高階依賴關(guān)系。業(yè)務(wù)區(qū)分的重要特征包大小被很多研究人員用于業(yè)務(wù)識(shí)別和分類，但其取值并不是隨機(jī)的，有一定的規(guī)律可循。如果放寬HMM的經(jīng)典假設(shè)，將HMM直接拓展為高階HMM則會(huì)引入相當(dāng)大的計(jì)算量。因此，如何在不改變典型HMM結(jié)構(gòu)的前提下，結(jié)合多媒體業(yè)務(wù)QoS特征，既不降低實(shí)時(shí)性要求，又提高識(shí)別準(zhǔn)確性，是HMM模型在多媒體業(yè)務(wù)識(shí)別應(yīng)用中面臨的挑戰(zhàn)。

本文的主要貢獻(xiàn)如下：(1)通過分析典型網(wǎng)絡(luò)多媒體業(yè)務(wù)包大小特征，得出了與前人不同的新發(fā)現(xiàn)，發(fā)現(xiàn)了一組易于提取、計(jì)算復(fù)雜度低、處理速度快、可有效區(qū)分業(yè)務(wù)所屬Q(mào)oS/業(yè)務(wù)類別的QoS特征；(2)根據(jù)這些新發(fā)現(xiàn)，通過融合特征上下文信息，調(diào)整發(fā)射概率，改進(jìn)典型HMM模型，設(shè)計(jì)了一種基于改進(jìn)HMM的多媒體業(yè)務(wù)分類算法。

論文具體安排如下：第2節(jié)分析典型網(wǎng)絡(luò)多媒體業(yè)務(wù)的包大小特征，第3節(jié)介紹改進(jìn)的模型，第4節(jié)描述了基于改進(jìn)HMM的分類算法，第5節(jié)給出仿真結(jié)果，最后是結(jié)論。

2 典型網(wǎng)絡(luò)多媒體業(yè)務(wù)的包大小特征分析

圖1是實(shí)時(shí)捕獲的土豆視頻業(yè)務(wù)抓包截圖，由圖可見，當(dāng)前包大小值與其在序列中位置有以下特點(diǎn)：(1)當(dāng)某個(gè)包大小值首次出現(xiàn)時(shí)，其后包大小值以較大的概率與之相等或相近；(2)傳輸過程中，在一定時(shí)間內(nèi)，包大小取值相同或相近；(3)當(dāng)前包大小值與相鄰的前一個(gè)包大小有一定的聯(lián)系。這是由于協(xié)議、擁塞、丟包、排序、優(yōu)先級(jí)、重傳等因素的存在，使得包大小值具有階段性的特點(diǎn)。

本文使用Wireshark[6]在實(shí)驗(yàn)室公用網(wǎng)絡(luò)收集即時(shí)通信、標(biāo)清流媒體(592×252)、高清流媒體(768×326)和游戲4種較流行的多媒體業(yè)務(wù)。依據(jù)標(biāo)清流媒體業(yè)務(wù)包大小累積分布曲線，本文將包大小值劃為如下4個(gè)等級(jí)。4種業(yè)務(wù)包大小值在4個(gè)等級(jí)之間的轉(zhuǎn)化頻率并不一致(見表1)。與標(biāo)清流媒體類似，其它3種業(yè)務(wù)包大小值轉(zhuǎn)換頻率也有變化，即當(dāng)前包大小值和前一個(gè)包大小值有內(nèi)在聯(lián)系。限于篇幅，此處不再一一列出。

3 改進(jìn)的HMM模型

3.1 改進(jìn)的模型

定義1 Q={q1,q2,…,qN}代表網(wǎng)絡(luò)操作的有限狀態(tài)集合，其中的狀態(tài)數(shù)為N,Qt表示在t時(shí)刻的狀態(tài)。

表1 標(biāo)清流媒體業(yè)務(wù)包大小值轉(zhuǎn)化頻率(%)

定義2 V={v1,v2,…,vM}代表離散化情況下QoS特征取值的集合，其中M為QoS特征值總數(shù)。

將網(wǎng)絡(luò)操作狀態(tài)的集合Q看作HMM模型的隱藏狀態(tài)集合，O=(O1=o1,…,OM=oM)是輸出的可觀測(cè)狀態(tài)，M是序列中觀測(cè)值數(shù)目。網(wǎng)絡(luò)操作狀態(tài)相互轉(zhuǎn)移的概率矩陣為A={αij},1≤i,j≤N (N為狀態(tài)數(shù)目)，αij=p(qj/qi)表示從狀態(tài)qi轉(zhuǎn)移到狀態(tài)qj的概率，αij=1,1≤i≤N 。B={}表示某個(gè)時(shí)刻因網(wǎng)絡(luò)操作狀態(tài)而得到相應(yīng)QoS特征輸出值的概率，bim=P(vm/qi)描述在給定狀態(tài)qi輸出QoS特征取值vm的概率。隨機(jī)產(chǎn)生的π={πi,i =1,…,N}, ∑Ni=1πi=1為網(wǎng)絡(luò)操作狀態(tài)初始概率分布，那么由網(wǎng)絡(luò)操作狀態(tài)和QoS特征狀態(tài)所構(gòu)建的模型，形成HMM模型。

本文通過一個(gè)修改后的發(fā)射概率函數(shù)將包大小取值概率與其相鄰的前一個(gè)包大小取值結(jié)合起來，調(diào)整發(fā)射概率，將混淆矩陣修改為B={bim(ot-1)}, 1≤i≤N,1≤m≤M ，其中ot-1表示上一時(shí)刻輸出的觀察狀態(tài)，bim(ot-1)=P(vm/qi,ot-1)描述在t時(shí)刻時(shí)，給定的上一個(gè)觀察特征狀態(tài)為ot-1和隱藏狀態(tài)為qi情況下，觀察特征取值為vm的概率。依據(jù)特征前后狀態(tài)間依賴關(guān)系，通過設(shè)計(jì)的發(fā)射概率函數(shù)確定當(dāng)前狀態(tài)的發(fā)射概率bim(ot-1)，之后利用轉(zhuǎn)移概率矩陣計(jì)算下一時(shí)刻的系統(tǒng)隱式狀態(tài)的取值，轉(zhuǎn)移概率矩陣和時(shí)間無關(guān)，保證了典型HMM模型的結(jié)構(gòu)不變，提高識(shí)別準(zhǔn)確度。相比其它模型，本文模型既簡(jiǎn)化了QoS/業(yè)務(wù)類區(qū)分隱式過程存在的高階依賴關(guān)系，又由于發(fā)射概率源于歷史信息，確保了準(zhǔn)確性。此外，本文模型保留了更多訓(xùn)練數(shù)據(jù)的統(tǒng)計(jì)信息，有利于解決訓(xùn)練和分類上的困難。

圖1 實(shí)時(shí)捕獲的抓包截圖

3.2 改進(jìn)的發(fā)射概率

由于HMM的參數(shù)主要包括轉(zhuǎn)移概率和發(fā)射概率，包大小在狀態(tài)中的位置信息只能通過參數(shù)體現(xiàn)出來，由于與包大小有關(guān)，因此只能通過包大小發(fā)射概率體現(xiàn)出來。為此，本文參考文獻(xiàn)[7]根據(jù)包大小所處位置的不同，采用不同的發(fā)射概率計(jì)算方法。具體說來，就是根據(jù)包大小在狀態(tài)中的位置的不同以及前一個(gè)包大小的不同，選擇不同的發(fā)射概率，公式為式中σ-1表示σ的前一個(gè)包大小特征。c(x)表示事件x在訓(xùn)練集中出現(xiàn)的次數(shù)，為了計(jì)算c(x)，需要在模型合并過程中保存狀態(tài)的一些必要信息，包括狀態(tài)中各個(gè)特征值出現(xiàn)的頻率以及順序關(guān)系。

4 基于改進(jìn)HMM的分類算法

基于易獲取、區(qū)分效果好、復(fù)雜度低的考慮，本文選取包大小作為區(qū)分特征，針對(duì)不同類型的QoS/業(yè)務(wù)類網(wǎng)絡(luò)多媒體業(yè)務(wù)，訓(xùn)練相應(yīng)的基于改進(jìn)HMM的分類器?；讷@得的新分類器，對(duì)未知網(wǎng)絡(luò)多媒體業(yè)務(wù)流進(jìn)行分類，區(qū)分依據(jù)是相應(yīng)分類器產(chǎn)生的概率。這樣只需調(diào)整發(fā)射概率，就可通過一個(gè)HMM模型，簡(jiǎn)單地表述、解決復(fù)雜的網(wǎng)絡(luò)多媒體業(yè)務(wù)流分類問題。上述過程的詳細(xì)描述如下：

(1)數(shù)據(jù)預(yù)處理：獲取包大小特征及位置信息，采用K-means聚類算法聚類。依據(jù)聚類中心，生成訓(xùn)練和識(shí)別的特征序列；

(2)改進(jìn)的HMM：根據(jù)數(shù)據(jù)庫中包含的業(yè)務(wù)類型數(shù)目設(shè)置N，觀測(cè)值數(shù)目為M；隨機(jī)產(chǎn)生初始概率向量π,A中的每個(gè)元素用業(yè)務(wù)在數(shù)據(jù)庫中分布概率代表各個(gè)狀態(tài)轉(zhuǎn)移出現(xiàn)的概率，B采用改進(jìn)的觀測(cè)值發(fā)生概率(見式(1))，初始化該類型業(yè)務(wù)的HMM為λ；

(3)采用Baum-Welch算法[8]求解HMM參數(shù)λ；

(4)判決輸出：計(jì)算各業(yè)務(wù)在每個(gè)模型下的產(chǎn)生概率，由最優(yōu)判決輸出結(jié)果。

不同于基于典型HMM模型的多媒體業(yè)務(wù)分類方法，本文通過改進(jìn)發(fā)射概率，簡(jiǎn)化高階依賴關(guān)系降低實(shí)現(xiàn)難度，基于歷史信息提高準(zhǔn)確性，同時(shí)實(shí)現(xiàn)保持典型HMM模型結(jié)構(gòu)不變，不增加訓(xùn)練和識(shí)別階段的計(jì)算復(fù)雜度，這是由于本文不涉及聯(lián)合概率、條件概率等概率公式的求解，也不涉及特征高階量的計(jì)算，其計(jì)算復(fù)雜度遠(yuǎn)小于高階HMM。此外，與典型HMM模型相比，本文模型通過改進(jìn)發(fā)射概率隨機(jī)取值的不足，較好地考慮了多媒體業(yè)務(wù)QoS特征的內(nèi)在規(guī)律，有利于提高區(qū)分效果。

5 實(shí)驗(yàn)仿真

本文使用Wireshark從實(shí)際網(wǎng)絡(luò)中捕獲4類流行的多媒體業(yè)務(wù)，作為樣本流，通過人工識(shí)別，將流分為訓(xùn)練樣本和測(cè)試樣本(表2)，用于評(píng)估算法性能，通過與文獻(xiàn)[2-5]中相關(guān)算法比較，驗(yàn)證本文方法的有效性。

表2 樣本統(tǒng)計(jì)信息

通過多次實(shí)驗(yàn)，使用記錄完整的分組信息，并保存在流文件中，下面取2組不同時(shí)間段進(jìn)行的典型實(shí)驗(yàn)數(shù)據(jù)進(jìn)行分析，其中“其它”包括HTTP等業(yè)務(wù)和未知流量，作為干擾數(shù)據(jù)，其中HTTP為主，約占“其它”流量的75%以上。然后基于HMM工具箱[9]，將本文方法與典型方法[2-5]進(jìn)行對(duì)比，結(jié)果如表3和表4所示。

由表3可見，本文方法對(duì)4種業(yè)務(wù)的區(qū)分準(zhǔn)確度較高，而基于典型HMM多媒體業(yè)務(wù)分類方法區(qū)分業(yè)務(wù)效果欠佳。文獻(xiàn)[2-5]方法同時(shí)忽略了業(yè)務(wù)內(nèi)在QoS需求對(duì)區(qū)分特征的影響，將發(fā)射概率設(shè)為隨機(jī)值，且演化過程中保持不變，違背了業(yè)務(wù)內(nèi)在結(jié)構(gòu)穩(wěn)定性特點(diǎn)，導(dǎo)致區(qū)分效果欠佳。由于重傳、網(wǎng)絡(luò)資源限制、業(yè)務(wù)類型特點(diǎn)等因素的存在，相近的特征取值之間有較緊密的聯(lián)系，輸出觀察值概率與多個(gè)狀態(tài)有關(guān)。因此，似乎應(yīng)該基于特征取值的上下文信息對(duì)業(yè)務(wù)區(qū)分，這體現(xiàn)業(yè)務(wù)自身內(nèi)在規(guī)律性的要求。

本文方法依據(jù)位置信息改變發(fā)射概率，反映了特征取值的位置信息，一定程度上體現(xiàn)了特征值位置間的上下文信息，較好地反映了其內(nèi)在規(guī)律，取得較好的區(qū)分效果。由于包大小等多媒體業(yè)務(wù)特征受網(wǎng)絡(luò)協(xié)議、業(yè)務(wù)類型等因素影響較大，其出現(xiàn)的位置具有內(nèi)在的規(guī)律性。這是由于典型HMM多媒體業(yè)務(wù)分類方法中隱式序列為一階馬爾可夫鏈的約束條件具有內(nèi)在局限性，側(cè)重于反映區(qū)分特征的某個(gè)側(cè)面，不能反映業(yè)務(wù)區(qū)分特征全部信息，特征考慮的全面程度不足，決定不利于提高區(qū)分效果，因此，有必要更深入研究區(qū)分特征的上下文信息。

表3 不同方法測(cè)試樣本集的區(qū)分結(jié)果

表4 不同方法的計(jì)算時(shí)間

表4的數(shù)據(jù)在MATLAB R2008a環(huán)境下獲得，由表4可見，本文方法耗時(shí)較少，這是由于本文方法選擇的區(qū)分特征最少，而計(jì)算復(fù)雜度隨著狀態(tài)個(gè)數(shù)的增加而增長(zhǎng)。文獻(xiàn)[2]方法選擇兩個(gè)區(qū)分特征，通過加權(quán)將兩個(gè)特征聯(lián)系起來，有較高的計(jì)算復(fù)雜度。文獻(xiàn)[3]方法僅適合區(qū)分基于TCP協(xié)議的業(yè)務(wù)，不適合多媒體業(yè)務(wù)流的區(qū)分。文獻(xiàn)[4]方法使用的區(qū)分特征需要較高的預(yù)處理成本，計(jì)算時(shí)間依然較大。文獻(xiàn)[5]針對(duì)無線業(yè)務(wù)識(shí)別，計(jì)算復(fù)雜度較高且聯(lián)合分布獲取很困難。

6 結(jié)論

本文針對(duì)典型HMM多媒體業(yè)務(wù)分類方法使用包大小特征區(qū)分業(yè)務(wù)的不足，分析了典型多媒體業(yè)務(wù)包大小分布特點(diǎn)，通過引入包大小位置信息，改進(jìn)典型HMM發(fā)射概率的取值，提高識(shí)別效果。仿真結(jié)果驗(yàn)證了本文方法的有效性。由于多媒體業(yè)務(wù)識(shí)別相關(guān)研究處于不斷發(fā)展的階段，一些其它關(guān)鍵問題還亟待解決。此外，發(fā)射函數(shù)的引入也改變了HMM中馬爾可夫過程的性質(zhì)，是否有負(fù)面效果的存在，也尚待深入展開研究。

[1] Michael F, Chris R, Eduardo R, et al.. A survey of

payload-based traffic classification approaches[J]. IEEE Communications Surveys & Tutorials, 2014, 16(2):1135-1156.

[2] Mu Xue-feng and Wu Wen-jun. A parallelized network traffic classification based on hidden Markov model[C]. IEEE International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery, Beijing, 2011: 107-112.

[3] El Khadimi A, Lmater M A, Eddabbah M, et al.. Packet classification using the hidden Markov model[C]. IEEE International Conference on Multimedia Computing and Systems, Ouarzazate, Morocco, 2011: 1-5.

[4] 許博, 陳鳴, 魏祥麟. 基于HMM模型的P2P流識(shí)別技術(shù)[J].通信學(xué)報(bào), 2012, 33(6): 55-63. Xu Bo, Chen Ming, and Wei Xiang-lin. Hidden Markov model based P2P flow identification technique[J]. Journal on Communications, 2012, 33(6): 55-63.

[5] Maheshwari S, Mahapatra S, Kumar C S, et al.. A joint parametric prediction model for wireless internet traffic using Hidden Markov Model[J]. Wireless Networks, 2013, 19(6): 1171-1185.

[6] Gold S. Hacking on the hoof[J]. Engineering and Technology, 2012, 7(3): 80-83.

[7] 張銘, 銀平, 鄧志鴻, 等. SVM+BiHMM:基于統(tǒng)計(jì)方法的元數(shù)據(jù)抽取混合模型[J]. 軟件學(xué)報(bào), 2008, 19(2): 358-368. Zhang Ming, Yin Ping, Deng Zhi-hong, et al.. SVM + BiHMM: a hybrid statistic model for metadata extraction[J]. Journal of Software, 2008, 19(2): 358-368.

[8] Baggenstoss P M. A modified Baum-Welch algorithm for hidden Markov models with multiple observation spaces[J]. IEEE Transactions on Speech and Audio Processing, 2001, 9(4): 411-416.

[9] Kevin Murphy. HMM Toolbox. http://www.cs.ubc.ca/～murphyk/Software/HMM/hmm_download.html,2014.

王再見： 男，1980年生，博士生，副教授，研究方向?yàn)槎说蕉薗oS保證技術(shù)、業(yè)務(wù)流識(shí)別.

董育寧： 男，1955年生，博士生導(dǎo)師，教授，研究方向?yàn)槎嗝襟w通信與信息處理、綠色通信.

張 暉： 男，1982年生，博士，副教授，研究方向?yàn)闊o線網(wǎng)絡(luò)、云計(jì)算.

A Multimedia Traffic Classification Method Based on Improved Hidden Markov Model

Wang Zai-jian①②Dong Yu-ning①Zhang Hui①Feng You-hong②

①(College of Communications and Information Engineering, Nanjing University of Posts and Telecommunications, Nanjing 210003, China)
②(The College of Physics and Electronic Information, Anhui Normal University, Wuhu 241000, China)

This paper proposes an improved Hidden Markov Model (HMM) based multimedia traffic classification method. This method preserves the classical HMM model structure, and improves the performance of multimedia traffic classification by changing the emitting probability value with the position information of packet size. Theoretical analysis indicates that the new model can reduce the computational complexity of the classical HMM model. Simulation results show that the proposed method can improve the classification performance compared with the existing HMM based classification method.

Multimedia traffic classification; Hidden Markov Model (HMM); Emitting probability; Packet size

TP393

A

1009-5896(2015)02-0499-05

10.11999/JEIT140340

2014-03-13收到，2014-09-15改回

國(guó)家自然科學(xué)基金(61401004, 61271233, 60972038, 61101105)，教育部高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金(20103223110001, 20113223120001)，工業(yè)與信息化部通信軟科學(xué)課題(2011-R-70), 2011年度江蘇省研究生培養(yǎng)創(chuàng)新工程(CXZZ11_0396)和安徽師范大學(xué)科研培育基金(2013xmpy10)資助課題

*通信作者：王再見 wangzaijian@ustc.edu