一種基于改進隱馬爾可夫的多媒體業務分類算法

王再見董育寧張 暉馮友宏

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

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

一種基于改進隱馬爾可夫的多媒體業務分類算法

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

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

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

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

多媒體業務流識別；隱馬爾可夫；發射概率；包大小

1 引言

端到端QoS(Quality of Service)保證領域的網絡多媒體業務的分類，關注的是QoS特征而不是業務具體內容，希望用較少的QoS特征區分業務所歸屬的QoS/業務類。典型的基于端口或深度包檢測的業務分類方法在效率、安全等方面存在不足。一些機器學習方法由于分類的復雜度較高，影響了分類實時性。因此，近年來有大量工作，研究如何基于可觀察的QoS特征狀態，準確、高效地識別被隱藏的QoS/業務類別[1]。

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

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

論文具體安排如下：第2節分析典型網絡多媒體業務的包大小特征，第3節介紹改進的模型，第4節描述了基于改進HMM的分類算法，第5節給出仿真結果，最后是結論。

2 典型網絡多媒體業務的包大小特征分析

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

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

3 改進的HMM模型

3.1 改進的模型

定義1 Q={q1,q2,…,qN}代表網絡操作的有限狀態集合，其中的狀態數為N,Qt表示在t時刻的狀態。

表1 標清流媒體業務包大小值轉化頻率(%)

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

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

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

圖1 實時捕獲的抓包截圖

3.2 改進的發射概率

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

4 基于改進HMM的分類算法

基于易獲取、區分效果好、復雜度低的考慮，本文選取包大小作為區分特征，針對不同類型的QoS/業務類網絡多媒體業務，訓練相應的基于改進HMM的分類器。基于獲得的新分類器，對未知網絡多媒體業務流進行分類，區分依據是相應分類器產生的概率。這樣只需調整發射概率，就可通過一個HMM模型，簡單地表述、解決復雜的網絡多媒體業務流分類問題。上述過程的詳細描述如下：

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

(2)改進的HMM：根據數據庫中包含的業務類型數目設置N，觀測值數目為M；隨機產生初始概率向量π,A中的每個元素用業務在數據庫中分布概率代表各個狀態轉移出現的概率，B采用改進的觀測值發生概率(見式(1))，初始化該類型業務的HMM為λ；

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

(4)判決輸出：計算各業務在每個模型下的產生概率，由最優判決輸出結果。

不同于基于典型HMM模型的多媒體業務分類方法，本文通過改進發射概率，簡化高階依賴關系降低實現難度，基于歷史信息提高準確性，同時實現保持典型HMM模型結構不變，不增加訓練和識別階段的計算復雜度，這是由于本文不涉及聯合概率、條件概率等概率公式的求解，也不涉及特征高階量的計算，其計算復雜度遠小于高階HMM。此外，與典型HMM模型相比，本文模型通過改進發射概率隨機取值的不足，較好地考慮了多媒體業務QoS特征的內在規律，有利于提高區分效果。

5 實驗仿真

本文使用Wireshark從實際網絡中捕獲4類流行的多媒體業務，作為樣本流，通過人工識別，將流分為訓練樣本和測試樣本(表2)，用于評估算法性能，通過與文獻[2-5]中相關算法比較，驗證本文方法的有效性。

表2 樣本統計信息

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

由表3可見，本文方法對4種業務的區分準確度較高，而基于典型HMM多媒體業務分類方法區分業務效果欠佳。文獻[2-5]方法同時忽略了業務內在QoS需求對區分特征的影響，將發射概率設為隨機值，且演化過程中保持不變，違背了業務內在結構穩定性特點，導致區分效果欠佳。由于重傳、網絡資源限制、業務類型特點等因素的存在，相近的特征取值之間有較緊密的聯系，輸出觀察值概率與多個狀態有關。因此，似乎應該基于特征取值的上下文信息對業務區分，這體現業務自身內在規律性的要求。

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

表3 不同方法測試樣本集的區分結果

表4 不同方法的計算時間

表4的數據在MATLAB R2008a環境下獲得，由表4可見，本文方法耗時較少，這是由于本文方法選擇的區分特征最少，而計算復雜度隨著狀態個數的增加而增長。文獻[2]方法選擇兩個區分特征，通過加權將兩個特征聯系起來，有較高的計算復雜度。文獻[3]方法僅適合區分基于TCP協議的業務，不適合多媒體業務流的區分。文獻[4]方法使用的區分特征需要較高的預處理成本，計算時間依然較大。文獻[5]針對無線業務識別，計算復雜度較高且聯合分布獲取很困難。

6 結論

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

[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流識別技術[J].通信學報, 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:基于統計方法的元數據抽取混合模型[J]. 軟件學報, 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年生，博士生，副教授，研究方向為端到端QoS保證技術、業務流識別.

董育寧： 男，1955年生，博士生導師，教授，研究方向為多媒體通信與信息處理、綠色通信.

張 暉： 男，1982年生，博士，副教授，研究方向為無線網絡、云計算.

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改回

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

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