一種稀疏度自適應(yīng)的網(wǎng)絡(luò)流量矩陣測量方法

楊京禮，崔 征，魏長安，姜守達(dá)

（哈爾濱工業(yè)大學(xué)自動化測試與控制系，150080哈爾濱）

一種稀疏度自適應(yīng)的網(wǎng)絡(luò)流量矩陣測量方法

楊京禮，崔 征，魏長安，姜守達(dá)

（哈爾濱工業(yè)大學(xué)自動化測試與控制系，150080哈爾濱）

為提高網(wǎng)絡(luò)流量矩陣測量的精度，在壓縮感知框架下提出一種稀疏度自適應(yīng)的網(wǎng)絡(luò)流量矩陣測量方法.通過對網(wǎng)絡(luò)流量矩陣的主成分分析及奇異值歸一化處理尋找信號支撐集選擇的判定閾值，利用網(wǎng)絡(luò)流量矩陣重構(gòu)過程中的殘差L2范數(shù)匹配計(jì)算各測量時(shí)間點(diǎn)上網(wǎng)絡(luò)流量矩陣的稀疏度，減小由于網(wǎng)絡(luò)流量矩陣近似稀疏表示以及稀疏度選擇不準(zhǔn)確造成的測量誤差.仿真實(shí)驗(yàn)結(jié)果表明：所提出的方法與現(xiàn)有方法相比能夠獲得更小的空間相對誤差和時(shí)間相對誤差.通過稀疏度自適應(yīng)選擇方法，能夠有效提高網(wǎng)絡(luò)流量矩陣的測量精度.

網(wǎng)絡(luò)測量；網(wǎng)絡(luò)層析成像；流量矩陣；壓縮感知；正交匹配追蹤

網(wǎng)絡(luò)流量矩陣（traffic matrix）作為描述網(wǎng)絡(luò)中源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間流量信息（origin destination flow，OD流）的參數(shù)，是互聯(lián)網(wǎng)管理和優(yōu)化的重要依據(jù)［1-2］.隨著網(wǎng)絡(luò)朝著非協(xié)作和基于邊緣控制的方向演變，傳統(tǒng)的直接測量方法不能完全滿足網(wǎng)絡(luò)流量矩陣測量的需求，亟待引進(jìn)新的測量方法.網(wǎng)絡(luò)層析成像（network tomography，NT）［3-4］將醫(yī)學(xué)上的計(jì)算機(jī)層析成像技術(shù)引入到網(wǎng)絡(luò)測量中，在沒有內(nèi)部節(jié)點(diǎn)協(xié)作的條件下進(jìn)行端到端的測量，通過網(wǎng)絡(luò)邊界的信息來推斷網(wǎng)絡(luò)鏈路級性能參數(shù).

目前，現(xiàn)有的基于網(wǎng)絡(luò)層析成像技術(shù)的網(wǎng)絡(luò)流量矩陣估計(jì)方法主要包括基于先驗(yàn)?zāi)Ｐ停?-8］和無先驗(yàn)?zāi)Ｐ偷龋?-13］兩類.基于先驗(yàn)?zāi)Ｐ偷木W(wǎng)絡(luò)流量矩陣估計(jì)方法計(jì)算簡單快捷，但該類方法采用的已知概率分布模型［5-8］難以準(zhǔn)確反映網(wǎng)絡(luò)流量矩陣的變化規(guī)律，容易造成較大的估計(jì)誤差.文獻(xiàn)［9］提出的線性規(guī)劃方法以目標(biāo)函數(shù)代替先驗(yàn)?zāi)Ｐ?，解決先驗(yàn)?zāi)Ｐ碗y以描述網(wǎng)絡(luò)流量矩陣規(guī)律的問題，但目標(biāo)函數(shù)的選擇成為影響該方法的瓶頸問題.文獻(xiàn)［10］使用主成分分析將N個(gè)流量矩陣的估計(jì)問題轉(zhuǎn)換為K（K＜＜N）個(gè)最重要特征流的計(jì)算問題.該方法在計(jì)算過程中會刪除特征值較小的特征流向量，造成后續(xù)流量矩陣計(jì)算過程中出現(xiàn)誤差.文獻(xiàn)［11］采用遞歸神經(jīng)網(wǎng)絡(luò)對網(wǎng)絡(luò)流量矩陣進(jìn)行追蹤，但該方法需要較長的時(shí)間對神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練，因此不適合互聯(lián)網(wǎng)實(shí)時(shí)流量矩陣測量的需求.

文獻(xiàn)［12-13］提出了基于壓縮感知技術(shù)的CS-OMP算法，通過矩陣奇異值分解（singular value decomposition，SVD）建立網(wǎng)絡(luò)流量矩陣的近似稀疏表示，應(yīng)用正交匹配追蹤算法（orthogonal matching pursuit，OMP）完成網(wǎng)絡(luò)流量矩陣的重構(gòu)計(jì)算.該算法的網(wǎng)絡(luò)流量矩陣計(jì)算精度與預(yù)先選擇的稀疏度有很強(qiáng)的關(guān)聯(lián)性，當(dāng)稀疏度取值過小或過大時(shí)都會造成較大的測量誤差.

為提高網(wǎng)絡(luò)層析成像技術(shù)下流量矩陣測量的精度，本文在壓縮感知框架下提出了一種稀疏度自適應(yīng)的網(wǎng)絡(luò)流量矩陣測量方法.通過對網(wǎng)絡(luò)流量矩陣數(shù)據(jù)主成分分析中奇異值的歸一化處理尋找信號支撐集選擇的判定閾值，利用正交匹配追蹤數(shù)據(jù)恢復(fù)中殘差范數(shù)匹配所有測量時(shí)間點(diǎn)上網(wǎng)絡(luò)流量矩陣的稀疏度，降低網(wǎng)絡(luò)流量矩陣近似稀疏表示造成的測量誤差.

1 模型與估計(jì)

1.1 網(wǎng)絡(luò)模型

在網(wǎng)絡(luò)層析成像框架下進(jìn)行流量矩陣估計(jì)時(shí)，鏈路流量表示相鄰兩節(jié)點(diǎn)間鏈路上傳輸?shù)臄?shù)據(jù)量大小，是各網(wǎng)絡(luò)OD流在鏈路上的聚合.設(shè)為在測量時(shí)間點(diǎn)q上的鏈路流量，M為網(wǎng)絡(luò)鏈路數(shù)量；為當(dāng)前測量時(shí)間點(diǎn)上的網(wǎng)絡(luò)流量矩陣；N為網(wǎng)絡(luò)流量矩陣中OD流對的數(shù)量；A為路由矩陣，若第i條網(wǎng)絡(luò)OD流經(jīng)過第j條鏈路，則Ai，j=1，否則Ai，j=0.鏈路流量與網(wǎng)絡(luò)流量矩陣的關(guān)系為

在網(wǎng)絡(luò)流量矩陣測量過程中，假設(shè)進(jìn)行Q次測量，各節(jié)點(diǎn)收集的鏈路流量數(shù)據(jù)為Y=（Y1，Y2，…，YQ）；對應(yīng)的網(wǎng)絡(luò)流量矩陣為X=（X1，X2，…，XQ）.

網(wǎng)絡(luò)流量矩陣估計(jì)是在已知網(wǎng)絡(luò)鏈路流量Y和路由矩陣A的情況下，獲得X的估計(jì)值.由于通常情況下M ＜N，因此式（1）為欠定方程組，在沒有額外信息的情況下上述方程組沒有唯一解.

1.2 稀疏表示

研究［10］發(fā)現(xiàn)網(wǎng)絡(luò)流量矩陣X具有低維特性：網(wǎng)絡(luò)流量矩陣分解后的特征流低維空間可以描述其主要特征，K個(gè)主要的特征流分量占據(jù)了網(wǎng)絡(luò)流量矩陣的大部分能量，特征流分量對應(yīng)的奇異值代表其能量值.通過SVD分解可以得到重建網(wǎng)絡(luò)流量矩陣的一組正交基，即

其中：si為X的奇異值；ui、vi分別為U和V的列向量.

將式（3）代入式（1），可得

其中：G為滿足漸進(jìn)正態(tài)分布N（0，O（M-1））的高斯隨機(jī)矩陣；C（γ）為元素為0或1的對角陣，其對角線上0元素?cái)?shù)量為γ；，在觀測矩陣Ψ滿足RIP原則的條件下，若已知正交基，則可以通過壓縮感知理論完成重構(gòu)Θ.

1.3 網(wǎng)絡(luò)流量矩陣重構(gòu)

在壓縮感知框架下，對于式（5）可通過l0范數(shù)優(yōu)化問題找到具有稀疏結(jié)構(gòu)的解，即

其中：wq、θq分別為W和Θ的第q列（q=1，2，…，Q）矩陣.由于式（6）的優(yōu)化問題是一個(gè)難求解的NP難問題，所以可以用l1約束取代l0約束，即

文獻(xiàn)［12］通過正交匹配追蹤算法對式（7）進(jìn)行求解，具體步驟：1）設(shè)定算法輸入觀測信號wq，稀疏度K.2）初始化各參數(shù).殘差r0=wq，信號支撐集Φ0=?.3）迭代計(jì)算.在第k（k=1，2，…，K）次循環(huán)，進(jìn)行如下計(jì)算：a）從觀測矩陣Ψ中尋找與信號相關(guān)性最強(qiáng)的信號支撐索引 I=arg將尋找到的信號支撐加入信號支撐集Φk=Φk-1∪ΦI；c）更新已選各列的稀疏系數(shù)估計(jì)值d）更新殘差重構(gòu)測量時(shí)間點(diǎn)q上的網(wǎng)絡(luò)流量矩陣

2 稀疏度自適應(yīng)的網(wǎng)絡(luò)流量矩陣估計(jì)方法

在網(wǎng)絡(luò)流量矩陣估計(jì)過程中，首先需要根據(jù)預(yù)先采集的部分網(wǎng)絡(luò)流量矩陣信息進(jìn)行SVD分解，尋找能夠建立網(wǎng)絡(luò)流量矩陣稀疏表示的稀疏基V～；隨后在每個(gè)測量時(shí)間點(diǎn)單獨(dú)應(yīng)用正交匹配追蹤算法計(jì)算該時(shí)間點(diǎn)上的網(wǎng)絡(luò)流量矩陣數(shù)據(jù).由式（3）可知，網(wǎng)絡(luò)流量矩陣SVD分解后建立的稀疏表示本身存在截?cái)嗾`差，誤差大小與稀疏度K的取值密切相關(guān).當(dāng)K值選擇過小時(shí)，通過CS-OMP算法尋找的信號支撐集不夠完備，難以完整描述網(wǎng)絡(luò)流量矩陣的主要特征.當(dāng)K值選擇過大時(shí)，由于截?cái)嗾`差的存在使得CS-OMP算法有可能選取錯誤的索引位置并添加到信號支撐集.

文獻(xiàn)［14］通過對大量實(shí)際網(wǎng)絡(luò)的流量數(shù)據(jù)分析發(fā)現(xiàn)，能夠描述網(wǎng)絡(luò)流量矩陣的主成分?jǐn)?shù)量一般在5～10個(gè)左右，且占據(jù)流量矩陣最高能量的成分所在的位置通常是固定不變的.根據(jù)上述結(jié)論，本文提出一種稀疏度自適應(yīng)策略，首先根據(jù)對預(yù)先采集部分網(wǎng)絡(luò)流量矩陣的PCA分析，計(jì)算各主成分的所占的能量值，結(jié)合初始稀疏度計(jì)算正交匹配追蹤算法選擇信號支撐集的判定閾值；隨后在網(wǎng)絡(luò)流量矩陣重構(gòu)過程中，在各測量時(shí)間點(diǎn)上以殘差衰減情況作為算法稀疏度的計(jì)算依據(jù)進(jìn)行信號支撐集的選擇，使得算法的稀疏度對于網(wǎng)絡(luò)流量矩陣當(dāng)前值具有自適應(yīng)性，減少采用統(tǒng)一初始稀疏度產(chǎn)生的網(wǎng)絡(luò)流量矩陣重構(gòu)誤差，提高網(wǎng)絡(luò)流量矩陣的估計(jì)精度.

在對網(wǎng)絡(luò)流量矩陣進(jìn)行PCA分析時(shí)，由于網(wǎng)絡(luò)流量矩陣數(shù)據(jù)本身是多維度數(shù)據(jù)，為減小不同維度數(shù)據(jù)幅值不同對PCA分析造成的誤差，需要對網(wǎng)絡(luò)流量矩陣數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理，即

式中：μq為第q次測量時(shí)獲得的各網(wǎng)絡(luò)OD流的均值；σq為第q次測量時(shí)獲得的各網(wǎng)絡(luò)OD流的協(xié)方差.

由于占據(jù)流量矩陣能量最高的成分的位置通常不變，因此考慮按照該成分所占的能量值對各主成分能量進(jìn)行歸一化處理，即

在2.3節(jié)所示網(wǎng)絡(luò)流量矩陣重構(gòu)過程中，重構(gòu)誤差主要來源于在每個(gè)測量時(shí)間點(diǎn)q上均要按照預(yù)先設(shè)置的初始稀疏度值進(jìn)行K0次計(jì)算.但是由于受到稀疏表示本身誤差及網(wǎng)絡(luò)流量矩陣動態(tài)變化的影響，預(yù)先選擇的K0不能準(zhǔn)確地描述當(dāng)前測量點(diǎn)上網(wǎng)絡(luò)流量矩陣數(shù)據(jù)的稀疏度，容易導(dǎo)致選擇錯誤的信號支撐集進(jìn)行網(wǎng)絡(luò)流量矩陣的重構(gòu).在正交匹配追蹤算法進(jìn)行信號重構(gòu)過程中，信號支撐集中各分量所占的能量值大小可通過其當(dāng)前殘差的L2范數(shù)進(jìn)行表征，而占據(jù)流量矩陣能量最高的成分所在的位置通常是不變的.因此本文采用歸一化后的殘差L2范數(shù)作為依據(jù)近似求解當(dāng)前測量點(diǎn)上網(wǎng)絡(luò)流量矩陣數(shù)據(jù)的稀疏度，在網(wǎng)絡(luò)流量矩陣重構(gòu)過程中按照下式尋找滿足判定閾值的主成分中的最低能量所處的位置，即

在滿足‖rK‖2／‖r0‖2≤δ后，認(rèn)為已找到當(dāng)前測量點(diǎn)上網(wǎng)絡(luò)流量矩陣的稀疏度.如圖1所示（圖中橫軸i為按能量值降序排列后的主成份序號，縱軸為歸一化后的奇異值與殘差l2范數(shù)的比值），初始稀疏度值取值為K0=10，經(jīng)過PCA分析并對主成分能量進(jìn)行歸一化處理排序后，通過式（10）計(jì)算得到選擇信號支撐集的判定閾值δ=0.21.在信號重構(gòu)過程中，1. 3節(jié)步驟3經(jīng)過5次迭代計(jì)算后的p5=0.21（見圖中方框），因此當(dāng)前時(shí)間點(diǎn)網(wǎng)絡(luò)流量矩陣的稀疏度為5.

圖1 自適應(yīng)策略下的稀疏度計(jì)算過程

3 性能評估

本文采用Abilene骨干網(wǎng)的真實(shí)網(wǎng)絡(luò)流量數(shù)據(jù)驗(yàn)證所提出算法 （adaptive orthogonal matching pursuit，AOMP）的各項(xiàng)指標(biāo).Abilene骨干網(wǎng)由12個(gè)節(jié)點(diǎn)路由器，30條內(nèi)部鏈路和24條外部鏈路組成，主要用于教育與研究工作，其數(shù)據(jù)已廣泛應(yīng)用于網(wǎng)絡(luò)測量的各個(gè)領(lǐng)域［15］.在本文中，可開展流量測量的鏈路數(shù)量M=54，待測量的網(wǎng)絡(luò)OD流對數(shù)量為N=12×12=144，網(wǎng)絡(luò)流量數(shù)據(jù)由NetFlow軟件采集，采樣間隔為5 min，連續(xù)采集1周時(shí)間得到的樣本數(shù)為Q=2 016.為評價(jià)AOMP算法的性能，將與目前效果較好的CS-OMP算法［12］進(jìn)行比較.

本文采用文獻(xiàn)［10］給出的實(shí)驗(yàn)條件，選擇采集1 d時(shí)間得到的OD流樣本作為先驗(yàn)信息，樣本數(shù)量為288.根據(jù)文獻(xiàn)［14］的研究結(jié)論，能夠描述網(wǎng)絡(luò)流量矩陣的主成分?jǐn)?shù)量一般在5～10個(gè)左右.為在相同條件下綜合比較兩種算法的性能，本文首先在文獻(xiàn)［12］的初始稀疏度值（K0=10）下比較網(wǎng)絡(luò)流量矩陣重構(gòu)的精度，然后比較算法對初始稀疏度值（K0∈［5，6，7，8，9，10］）的自適應(yīng)能力.

3.1 性能評價(jià)指標(biāo)

空間相對誤差eSRE：指某個(gè)OD流在各時(shí)間點(diǎn)上的測量值與真實(shí)值的相對誤差，即

時(shí)間相對誤差eTRE：指某個(gè)時(shí)間點(diǎn)上各OD流的測量值與真實(shí)值的相對誤差，即

絕對誤差均值eAE：指某個(gè)OD流在各時(shí)間點(diǎn)上的測量值與真實(shí)值偏差的均值，即

絕對誤差標(biāo)準(zhǔn)差eSD：指某個(gè)OD流在各時(shí)間點(diǎn)上絕對誤差的分布情況，即

空間相對誤差均值eASRE：指各OD流的空間相對誤差的均值，即

時(shí)間相對誤差均值eATRE：指各時(shí)間點(diǎn)上的時(shí)間相對誤差的均值，即

3.2 實(shí)驗(yàn)結(jié)果及分析

首先，考察兩種算法對網(wǎng)絡(luò)OD流的追蹤能力.限于篇幅原因，本文僅通過圖2、3列出其中兩條OD流（編號為72和116）的估計(jì)值與真實(shí)值隨時(shí)間點(diǎn)序號的變化情況，以展示兩種算法對不同的OD流追蹤性能.從圖中可以看出，從整體上看兩種算法都能跟蹤網(wǎng)絡(luò)OD流的變化趨勢，但CS-OMP算法在每個(gè)時(shí)間點(diǎn)上都會引入相對較大的測量誤差，其主要原因在于由于CS-OMP算法稀疏度是固定不變的，隨著時(shí)間點(diǎn)的變化，預(yù)先設(shè)定的初始稀疏度逐漸不能很好地描述當(dāng)前時(shí)間點(diǎn)上的網(wǎng)絡(luò)OD流的稀疏情況，導(dǎo)致網(wǎng)絡(luò)OD流重構(gòu)時(shí)的誤差增大.與之相比，AOMP算法在每個(gè)時(shí)間點(diǎn)上估計(jì)當(dāng)前網(wǎng)絡(luò)OD流的稀疏度，因此可以有效減小重構(gòu)誤差.

圖2 第72條OD流真實(shí)值與估計(jì)值

圖3 第116條OD流真實(shí)值與估計(jì)值

然后，比較兩種算法對整個(gè)網(wǎng)絡(luò)流量矩陣的估計(jì)能力.圖4描述了空間相對誤差隨網(wǎng)絡(luò)OD流編號（按照OD流均值升序排列）的變化情況和時(shí)間相對誤差隨時(shí)間點(diǎn)序號的變化情況.從圖4可以看出，AOMP算法估計(jì)的網(wǎng)絡(luò)流量矩陣空間相對誤差與時(shí)間相對誤差明顯小于CS-OMP算法.

圖4 空間相對誤差與時(shí)間相對誤差變化情況

圖5描述了空間相對誤差與時(shí)間相對誤差的累積分布函數(shù).從圖5（a）可見，當(dāng)空間相對誤差為0.5時(shí)，AOMP算法估計(jì)出的網(wǎng)絡(luò)流量矩陣的空間相對誤差累積分布函數(shù)值為0.72；對于CS-OMP算法，對應(yīng)的空間相對誤差累積分布函數(shù)值為0.47.從圖5（b）可見，在AOMP算法下，90%的網(wǎng)絡(luò)流量矩陣中OD流的時(shí)間相對誤差小于0.18；對于CS-OMP算法，達(dá)到該比例時(shí)的時(shí)間相對誤差為0.27.

圖5 空間相對誤差與時(shí)間相對誤差的累積分布函數(shù)

圖6給出了上述兩種算法的網(wǎng)絡(luò)流量矩陣絕對誤差均值隨OD流編號（按照OD流均值降序排列）的變化情況.由圖中可見AOMP算法估計(jì)出的網(wǎng)絡(luò)流量矩陣絕對誤差均值小于CS-OMP算法的估計(jì)結(jié)果，因此AOMP算法具有更高的網(wǎng)絡(luò)流量矩陣測量正確度.

圖6 各OD流的絕對誤差均值分布情況

為比較兩種算法對網(wǎng)絡(luò)OD流估計(jì)的穩(wěn)定性，本文采用網(wǎng)絡(luò)流量矩陣絕對誤差的標(biāo)準(zhǔn)差對其進(jìn)行比較.圖7描述了AOMP算法和CS-OMP算法估計(jì)出的網(wǎng)絡(luò)流量矩陣絕對誤差的標(biāo)準(zhǔn)差隨絕對誤差均值的變化情況，由圖中可見AOMP算法絕對誤差的標(biāo)準(zhǔn)差比CS-OMP算法更小，即AOMP算法估計(jì)出的結(jié)果具有更高的精密度.最后，驗(yàn)證AOMP算法對初始稀疏度的自適應(yīng)性。圖8和圖9分別描述了網(wǎng)絡(luò)流量矩陣空間相對誤差均值和時(shí)間相對誤差均值隨初始稀疏度K0的變化情況，從圖中可見AOMP算法的網(wǎng)絡(luò)流量矩陣空間相對誤差均值和時(shí)間相對誤差均值都小于CS-OMP算法。隨著初始稀疏度增大，CS-OMP算法的空間相對誤差均值和時(shí)間相對誤差均值逐漸增大，而AOMP算法則對初始稀疏度有良好的自適應(yīng)性。

圖7 絕對誤差的標(biāo)準(zhǔn)差隨絕對誤差均值變化情況

圖9 時(shí)間相對誤差隨初始稀疏度變化情況

4 結(jié) 論

1）以網(wǎng)絡(luò)層析成像技術(shù)為應(yīng)用背景，在壓縮感知框架下提出一種稀疏度自適應(yīng)的網(wǎng)絡(luò)流量矩陣測量方法.通過對基于壓縮感知的網(wǎng)絡(luò)流量矩陣測量方法重構(gòu)算法分析，得出信號支撐集不夠完備導(dǎo)致難以完整描述網(wǎng)絡(luò)流量矩陣的主要特征是造成現(xiàn)有算法測量誤差較大的主要原因的結(jié)論.

2）通過主成分分析方法計(jì)算網(wǎng)絡(luò)流量各主成分所占的能量值，結(jié)合初始稀疏度計(jì)算正交匹配追蹤算法選擇信號支撐集的判定閾值.

3）在網(wǎng)絡(luò)流量矩陣重構(gòu)過程中，以殘差衰減情況作為算法稀疏度的計(jì)算依據(jù)進(jìn)行信號支撐集的選擇，使得算法的稀疏度對于網(wǎng)絡(luò)流量矩陣當(dāng)前值具有自適應(yīng)性.

4）對比CS-OMP算法，當(dāng)初始稀疏度取值為10時(shí)，AOMP算法的時(shí)間相對誤差降低50%左右；當(dāng)初始稀疏度在5～10之間變化時(shí)，AOMP算法的空間相對誤差均值和時(shí)間相對誤差均值基本保持不變，表明其對于初始稀疏度選擇具有良好的自適應(yīng)性.

［1］周愛平，程光，郭曉軍.高速網(wǎng)絡(luò)流量測量方法［J］.軟件學(xué)報(bào)，2014，25（1）：135-153.

［2］TOLEDO T，KOLECHKINA T.Estimation of dynamic origin-destination matrices using linear assignment matrix approximations［J］.IEEE Transactions on Intelligent Transportation Systems，2013，14（2）：618-626.

［3］楊京禮，孫超，姜守達(dá)，等.基于層次分解的網(wǎng)絡(luò)鏈路時(shí)延分布快速推測算法［J］.電子與信息學(xué)報(bào)，2013，35（8）：2005-2012.

［4］ERIKSSON B，DASARATHY G，BARFORD P，et al. Efficient network tomography for internet topology discovery［J］.IEEE／ACM Transactions on Networking，2012，20（3）：931-943.

［5］ZHANG Y，ROUGHAN M，DUFFIELD N，et al.Fast accurate computation of large-scale IP traffic matrices from link loads［J］.ACM SIGMETRICS Performance Evaluation Review，2003，31（1）：206-217.

［6］ VARDIY.Network tomography： estimatingsourcedestination traffic intensities from link data［J］.Journal of American Statistical Association，1996，91（4）：365-377.

［7］ LIANG Gang， YU Bin.Maximum pseudo likelihood estimation in network tomography［J］.IEEE Transactions on Signal Processing，2003，51（8）：2043-2053.

［8］VATON S，BEDO J.Network traffic matrix：how can one learn the prior distributions from the link counts only？［C］／／Proceeding of IEEE Conference on Communications 2006.Paris：IEEE，2006：2138-2142.

［9］EUM S，MURPHY J，HARRIS R.A fast accurate LP approach for traffic matrix estimation［C］／／Proceeding of ITC19.Beijing：IEEE，2005：243-252.

［10］SOULE A，LAKHINA A，TAFT N，et al.Traffic matrices：balancing measurements，inference and modeling［C］／／Proceeding of SIGMETRICS Conference on Measurement and Modeling of Computer Systems 2005.Banff：ACM，2005：362-373.

［11］QIAN Feng，HU Guangmin，XIE Jijun.A recurrent neural network approach to traffic matrix tracking using partial measurements ［C］／／Proceeding of the 3rd IEEE Conference on Industrial Electronics and Applications. Singapore：IEEE，2008：1640-1643.

［12］NIE Laisen，JIANG Dingde.A compressive sensing-based network tomography approach to estimating origindestination flow traffic in large-scale backbone networks［J］.International Journal of Communication Systems，2014，27（4）：1-12.

［13］NIE Laisen， JIANG Dingde， XU Zhengzheng.A compressive sensing-based reconstruction approach to network traffic［J］.Computers and Electrical Engineering，2013，39（5）：1422-1432.

［14］LAKHINA A，PAGIANNAKI K，CROVELLA M，et al. Structuralanalysis ofnetwork traffic flows ［C］／／Proceeding of SIGMETRICS Conference on Measurement and Modeling of Computer Systems 2004.New York：ACM，2004：61-72.

［15］YIN Z，MATTHEW R，WALTER W，et al.Spatiotemporal compressive sensing and internet traffic matrices［J］.IEEE／ACM Transactions on Networking，2012，20（3）：662-676.

（編輯 魏希柱）

A sparsity adaptive measurement algorithm for network traffic matrix

YANG Jingli，CUI Zheng，WEI Chang’an，JIANG Shouda

（Department of Automatic Test and Control，Harbin Institute of Technology，150080 Harbin，China）

In order to improve the accuracy of the measurement algorithm for traffic matrix，a novel traffic matrix measurement algorithm with compressive sensing is proposed.This algorithm gets the judge gate by the principal components analysis and normalization of singular value.To reduce the measurement error created by approximation of sparse express and inaccurate choice of sparsity，we use L2 formulation of residual error to match the sparsity in the process of reconstitution of the traffic matrix on each time of measurement.Simulation results show that，this algorithm can obtain less spatial relative error and temporal relative error compared with the existing algorithm.With the help of adaptive selection for initial value of sparsity，this algorithm can obtain a higher accuracy.

network measurement；network tomography；traffic matrix；compressive sensing；orthogonal matching pursuit

TP393

A

0367-6234（2015）09-0013-06

10.11918／j.issn.0367-6234.2015.09.003

2014-07-03.

國家自然科學(xué)基金（61501135）；黑龍江省博士后基金（LBH-Z11171）.

楊京禮（1984—），男，博士，助理研究員.

楊京禮，jinglidg＠hit.edu.cn.