有噪網絡斷層掃描方法研究

吳辰文　朱建東　閆光輝　鄭　恒　張　燁

(蘭州交通大學電子與信息工程學院　甘肅 蘭州 730070)

?

有噪網絡斷層掃描方法研究

吳辰文朱建東閆光輝鄭恒張燁

(蘭州交通大學電子與信息工程學院甘肅 蘭州 730070)

噪聲數據在一定程度上影響了網絡斷層掃描的準確性。針對之前網絡斷層掃描方法大都忽略噪聲影響的不足，提出SAK算法。基于卡茨馬爾茲算法和SA算法的SAK算法更具有一般性和實時性，SAK算法模仿了原始Kaczmarz算法的特性。實驗結果顯示，通過用SAK算法處理估計的初始值，使其估計值能夠收斂到真實值，在很大程度上能達到去除噪聲的目的。

網絡斷層掃描隨機逼近算法Kaczmarz算法SAK算法網絡測量

0　引　言

網絡層析成像技術是近年來新興的一種網絡測量技術，用網絡測量的結果，計算出節點間相關性后進而可以推斷出網絡的拓撲結構。該技術的特點是能夠在不需要內部節點協作的前提下用基于端到端的測量技術獲取網絡內部的特性。

隨機逼近(SA)算法[1]是一個在存在測量噪聲的情況下尋找回歸方程根的回歸算法。直接利用測量數據，建立逼近算法尋找函數極值，不需要對系統模型有先驗知識，對測量噪聲有比較好的處理效果。可以理解為是利用觀測值估計未知函數的極值或者未知方程解的自適應問題求解技術。

卡茨馬爾茲算法[2]由數學家Kaczmarz于1937年提出，目的是用迭代的方法解決方程組的不適定線性問題。2004年，Galántai對此算法的收斂性進行了廣泛分析，并將其用于不同的領域，比如斷層掃描、納米測量、自身學習與自適應控制。

網絡斷層掃描中需要的卡茨馬爾茲算法不同于其他領域，這里需要一種隨機的卡茨馬爾茲算法。本文介紹和分析了一種近似版本的隨機卡茨馬爾茲算法，并證明了隨機卡茨馬爾茲算法具有強收斂性。我們用常微分方程的方法去分析算法，結果顯示這種算法和傳統算法有幾乎相同的漸進行為。本文跟之前研究的不同在于：這里提出的部分隨機性跟噪聲有關，不受人為因素的控制。

本文證明了對相同的初始點用經典的卡茨馬爾茲算法和隨機逼近卡茨馬爾茲算法收斂于同一點。基于這種特性，我們提出來一種在線估計從測量序列中得到向量X元素的新算法，該算法有一般性和實時性。這種算法的優點是它可以實時地觀測和輸入數據，并且能夠進行增量調整。跟之前方案不同的是，我們的設計方案考慮到了X的元素是相互有關聯的。對于鏈路時延斷層掃描，該算法摒棄了組播探測包測量的需要，不僅能夠用于樹狀拓撲結構，還能用于網狀拓撲結構。

1　 數學模型

網絡層析成像問題可用下面的數學模型表示[3]：

Yt=AXt+ε

(1)

其中：Yt是在時間t上的可觀測到的測量向量；A是節點矩陣；Xt是時間t上的數據分組的相關參數向量；ε是噪聲向量。

Y≡(Y(1),Y(2),…,Y(m))′=AX+W

(2)

其中，W測量中隨機變量噪音的有界方差，其均值為零。Z是取值范圍為[m]的隨機變量,對于?i∈[m],λi>0表示Pr{Z=i}{Xk},{Zk},{Wk},k≥1是X,Z,W的IID副本，它們是完全獨立的并且Yk表示AXk+Wk。假設在每一個時間間隔k，我們僅僅知道Zk+1的值和Yk+1中第Zk+1元素的值，即用yk+1表示Yk+1(Zk+1)。

2　算法描述

2.1隨機逼近(SA)算法

經典隨機逼近算法公式是：

xk+1=xk+ηk[h(xk)+ξk+1]

(3)

其中h:Rn→Rn是利普席茨(Lipschitz)函數,{ηk}(k≥0)是一個滿足∑ηk=∞和∑(ηk)2<∞的一個正值步長序列，ξk+1表示噪聲干擾。當ηk→0時,式(3)可被看作噪聲離散化的常微分方程。

x′(t)=h(x(t))

(4)

式(4)為 “常微分方程逼近”的表達式。具體來說，可以假設下面的設定均成立。

(A2) ?u,存在h∞(u)表示limh(cu)/c(c→∞)(h∞ 將必然是利普席茨函數)，由于具備全局漸近穩定性，常微分方程x′(t)=h∞(x(t))具有起始點。

(A3) H表示{x∈Rn:h(x)=0}≠φ，同時,?a連續可微李亞普諾夫函數L:Rn→R，這里對于x?H,[▽L(x),h(x)]<0。

進而，我們得出如下引理：

引理1式(3)中的迭代{xk}幾乎必然可以收斂到H。

2.2Kaczmarz算法

Kaczmarz算法最初的目的是用迭代的方法解決方程組的不適定線性問題問題。考慮到從Av*中找到一個固定的v*∈RN的反演問題。在不失一般性的情況下，令A中的行具有單位范數。給定一個v*的近似值x0，一個需要考慮的自然的優化問題是：

(5)

通過基本的計算，顯示其解為:

x*=x0+A′(AA′)-1(Av*-Ax0)

(6)

顯然地，x*∈Α0=x0+RA。當A行滿秩時，x*是在符合Au=Av*的A0中唯一的點。利用規定的起始點x0、步長κ以及rk≡(kmodm)+1，它的更新規則為:

xk+1=xk+κ[[ark,v*]-[ark,xk]〗ark

(7)

定理1如果0<κ<2，當k→∞時，xk→x*。

設定Α*表示v*+RA，由于Α0,Α*是RA的解，dist(x0,Α*)=dist(Α0,v*)。當A(x*-v*)=0時,(x*-v*)⊥RA。因此(x*-v*)⊥Α0,Α*。因此，‖v*-x*‖=dist(Α0,v*)=dist(x0,Α*)。于是我們得出了如下引理。

引理2對于任意δ>0,當且僅當dist(x0,Α*)<δ時，‖x*-v*‖<δ。

2.3SAK算法

我們為估計式(1)EX值制定了一個SAK算法。給定x0為一個EX的近似值。從式(1)中觀察得出:

EY=AEX

(8)

通過重新調整公式，我們假設在不失一般性的情況下，A的行具有單位范數。鑒于Y未被確切知道，可以對它進行離線估算，并使用經典的卡茨馬爾茲算法來確定EX。在式(5)中，經典的卡茨馬爾茲會收斂到:

x*=x0+A′(AA′)-1(E(Y)-Ax0)

(9)

相對這種離線方案，更好的選擇是使用在線算法。根據式(7)，用一個SAK算法估計出對應的EX值為：

xk+1=xk+ηk[Υk+1-]aZk+1

(10)

其中{ηk}如式(3)下的定義。記下式(10)中EY的元素的噪聲測量值{Υk}以及EX的實時估計值{xk}。

我們現在再來分析它的行為。顯然，所述迭代式(9)的{xk}總是保持局限于Α0，在式(6)下定義了仿射空間。由于A行滿秩，對于每個k≥0 ，都存在唯一的αk∈Rm，于是有：

xk=x0+A′αk

(11)

因此，可以等效地分析該算法:

(12)

αk+1=αk+ηk[Λ(EY-A(x0+A′αk))+ξk+1]

(13)

如果h(u)表示Λ(EY-A(x0+A′u))，那么，很顯然，式(13)的形式即是式(3)給定的。因此它的限制常微分方程是:

α′(t)=Λ(EY-A(x0+A′α(t)))

(14)

由于式(10)、式(11)的SAK算法會收斂于式(9)的x*，x*也是對應的經典卡茨馬爾茲收斂的點。

3　仿真實驗

圖1　仿真實驗所用的網絡

本文表述了SAK算法在圖1網絡的實時時延診斷方面的應用。其目標是使用探測數據包在遍歷網絡中不同路徑時所經歷的端到端所得到的時延測量值，從而實時獲得鏈路時延統計的估計值。

本次仿真所用的實驗設置如下，我們選擇在網絡中六個途徑的先驗。

如果鏈路j在路徑i上，則aij=1，否則為0。如第三行表示連接節點1-6-9-10-7-3的路徑。探測數據包在遍歷鏈路j時經歷的延遲是一個服從二進制非負值分布的隨機變量X(j)。穿越路徑i的延遲為Y(i)=+W(i)，其中W1,W2,…,W6是表示測量誤差值的IID標準高斯隨機變量。本次仿真生成了一百萬個探測包，其中對于第k個數據包的發送路徑的索引，是由Zk表示的，Zk是從{1,2,…,6}中隨機而又均勻地選出。因此，每一個路徑得到大約167 000個樣本。我們使用Yk來記錄遍歷路徑Zk時探測包k經歷的延遲。我們同樣對式(1)用一百萬個迭代也運行了式(9)的SAK算法。所選擇的開始點、實際值和最終矩的估計值在表1中給出。在表1預選鏈路時延真實值和最終估計值。

表1　預選鏈路時延真實值和最終估計值

這兩種情況下，給定的初始點都滿足引理2的假設，所以最終的估計值接近實際值。圖2比較了候選鏈路1和3期望延遲的實時估計值，該估計值是使用SAK算法和平均SAK算法獲得。平均SAK算法的迭代是SAK算法迭代的樣本平均值。觀察結果表明，雖然我們運行了一百萬個數據包的模擬，但在大約300次迭代后，估計值就已經非常接近真實值。還要注意的是，估計值中的誤差不會單調減少。這是因為我們直接使用了噪音測量值。然而，隨著迭代步長的減少，波動也因此得到了抑制。

(a) 鏈路1

(b) 鏈路3圖2　用SAK算法對候選鏈路1和3預期時延的在線估計

4　結　語

本文提出的基于隨機逼近算法和Kaczmarz算法的SAK算法，對驅除鏈路噪聲有一定效果，可用于樹狀拓撲和部分網狀拓撲的推斷。還存在許多問題需要進一步研究：(1)目前的測量方法和分析算法都只能用于小規模網絡，如何把這類方法運用于大規模網絡是面臨的一大難題；(2)現有的NT技術大都只能用于簡單樹狀拓撲的推斷，怎樣把NT技術用于復雜網狀拓撲是今后面臨的挑戰；(3)迄今為止的研究都是假定路由矩陣已知或者容易確定的情況下進行的，因而尋求針對動態隨機路由的推測方法也是一大挑戰。

[1] Bianchi P,Fort G,Hachem W.Performanceof a distributed stochastic approximation algorithm[J].Information Theory,IEEE Transactions on,2013,59(11):7405-7418.

[2] Liang Dai,Mojtaba Soltanalian.Kristiaan pelckmans.On the randomized Kaczmarz algorithm[J].Signal Processing LettersIEEE,2014,21(3):300-333.

[3] 趙洪華,陳鳴.基于網絡層析成像技術的拓撲推斷[J].軟件學報，2010,21(1):133-146.

[4] GuGan Thoppe,Vivek Borlar,Manjunath D.A stochastic Kaczmarz algorithm for network tomography[J].Automatica,2014,50(3):910-914.

[5] 張潤生,康一丁,張冠杰,等.基于非參數假設檢驗的拓撲推斷算法[J].電子科技大學學報:自然科學版，2014，43(5)：764-768.

[6] 張潤生,李艷斌,李嘯天.基于合并分層聚類的網絡拓撲推斷算法[J].電子學報，2013，41(12)：2346-2352.

[7] Wojciech Czaja,James H Tanis.Kaczmarz algorithm and frames[J].International Journal of Wavelets,Multiresolution and Information Processing,2013,11(5)：1-13.

[8] 朱三元,楊明,薛鈁.網絡通信軟件設計指南[M].北京：清華大學出版社，1994.

[9] Anastasios Zouzias,Nikolaos M Freris.Randomized extended Kaczmarz for solving least squares[J].SIAM Journal on Matrix Analysis and Applications,2013,34(2):773-793.

[10] Mansour H,Yilmaz O.A Sparse randomized Kaczmarz algorithm[C]//IEEE Global Conference on Signal and Information Processing,2013:621.

[11] 徐恪,張賽,陳昊.在線社會網絡的測量與分析[J].計算機學報，2014，37(1):165-188.

[12] 曹爭,何建斌.基于虛擬化的網絡測量平臺[J].通信學報，2013，34(S2)：84-89.

[13] 羅瑞龍.SDN網絡的測量和檢測子系統的設計與實現[D].北京：北京郵電大學,2014.

[14] 鄧建球,郝翠,鞠傳文,等.網絡測量及參數對網絡控制系統的影響[J].中南大學學報：自然科學版，2013(S1)：128-132.

[15] Federico Battiston,Vincenzo Nicosia,Vito Latora.Structural measures for multiplex networks[J].Physical Review.E:Statistical,nonlinear and soft matter physics,2014,89(3.1):032804-032819.

[16] Thomas Strohmer,Roman Vershynin.A randomized Kaczmarz algorithm with exponential convergence[J].Journal of Fourier Analysis and Applications,2009,15(2):262-278.

RESEARCH ON NOISY NETWORK TOMOGRAPHY METHOD

Wu ChenwenZhu JiandongYan GuanghuiZheng HengZhang Ye

(SchoolofElectronicandInformationEngineering，LanzhouJiaotiongUniversity，Lanzhou730070，Gansu，China)

Noisy data affects the accuracy of network tomography to some extent.In light of the insufficiency of previous network tomography methods that they mostly ignore the influence of noise,we proposed SAK algorithm.The SAK algorithm is based on Kaczmarz algorithm and SA algorithm,and is of more universal and real-time; SAK algorithm simulates the characteristics of original Kaczmarz algorithm.Experimental results showed that by using SAK algorithm to deal with the estimated initial values,they could converge to the real one; to a great extent it was able to achieve the purpose of noise removal.

Network tomographyStochastic approximation (SA) algorithmKaczmarz algorithmSAK algorithmNetwork measurement

2015-04-22。國家自然科學基金項目(61163010);蘭州市科技計劃基金項目(2009-1-5);甘肅省自然科學基金項目(1308RJZA111)。吳辰文，教授，主研領域：網絡層析成像技術。朱建東，碩士生。閆光輝，教授。鄭恒，碩士生。張燁，碩士生。

TP393

A

10.3969/j.issn.1000-386x.2016.08.033