有噪網(wǎng)絡(luò)斷層掃描方法研究

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

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

?

有噪網(wǎng)絡(luò)斷層掃描方法研究

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

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

噪聲數(shù)據(jù)在一定程度上影響了網(wǎng)絡(luò)斷層掃描的準(zhǔn)確性。針對之前網(wǎng)絡(luò)斷層掃描方法大都忽略噪聲影響的不足，提出SAK算法?；诳ù鸟R爾茲算法和SA算法的SAK算法更具有一般性和實時性，SAK算法模仿了原始Kaczmarz算法的特性。實驗結(jié)果顯示，通過用SAK算法處理估計的初始值，使其估計值能夠收斂到真實值，在很大程度上能達(dá)到去除噪聲的目的。

網(wǎng)絡(luò)斷層掃描隨機(jī)逼近算法Kaczmarz算法SAK算法網(wǎng)絡(luò)測量

0　引　言

網(wǎng)絡(luò)層析成像技術(shù)是近年來新興的一種網(wǎng)絡(luò)測量技術(shù)，用網(wǎng)絡(luò)測量的結(jié)果，計算出節(jié)點間相關(guān)性后進(jìn)而可以推斷出網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。該技術(shù)的特點是能夠在不需要內(nèi)部節(jié)點協(xié)作的前提下用基于端到端的測量技術(shù)獲取網(wǎng)絡(luò)內(nèi)部的特性。

隨機(jī)逼近(SA)算法[1]是一個在存在測量噪聲的情況下尋找回歸方程根的回歸算法。直接利用測量數(shù)據(jù)，建立逼近算法尋找函數(shù)極值，不需要對系統(tǒng)模型有先驗知識，對測量噪聲有比較好的處理效果?？梢岳斫鉃槭抢糜^測值估計未知函數(shù)的極值或者未知方程解的自適應(yīng)問題求解技術(shù)。

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

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

本文證明了對相同的初始點用經(jīng)典的卡茨馬爾茲算法和隨機(jī)逼近卡茨馬爾茲算法收斂于同一點。基于這種特性，我們提出來一種在線估計從測量序列中得到向量X元素的新算法，該算法有一般性和實時性。這種算法的優(yōu)點是它可以實時地觀測和輸入數(shù)據(jù)，并且能夠進(jìn)行增量調(diào)整。跟之前方案不同的是，我們的設(shè)計方案考慮到了X的元素是相互有關(guān)聯(lián)的。對于鏈路時延斷層掃描，該算法摒棄了組播探測包測量的需要，不僅能夠用于樹狀拓?fù)浣Y(jié)構(gòu)，還能用于網(wǎng)狀拓?fù)浣Y(jié)構(gòu)。

1　 數(shù)學(xué)模型

網(wǎng)絡(luò)層析成像問題可用下面的數(shù)學(xué)模型表示[3]：

Yt=AXt+ε

(1)

其中：Yt是在時間t上的可觀測到的測量向量；A是節(jié)點矩陣；Xt是時間t上的數(shù)據(jù)分組的相關(guān)參數(shù)向量；ε是噪聲向量。

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

(2)

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

2　算法描述

2.1隨機(jī)逼近(SA)算法

經(jīng)典隨機(jī)逼近算法公式是：

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

(3)

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

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

(4)

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

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

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

進(jìn)而，我們得出如下引理：

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

2.2Kaczmarz算法

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

(5)

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

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

(6)

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

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

(7)

定理1如果0<κ<2，當(dāng)k→∞時，xk→x*。

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

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

2.3SAK算法

我們?yōu)楣烙嬍?1)EX值制定了一個SAK算法。給定x0為一個EX的近似值。從式(1)中觀察得出:

EY=AEX

(8)

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

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

(9)

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

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

(10)

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

我們現(xiàn)在再來分析它的行為。顯然，所述迭代式(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*也是對應(yīng)的經(jīng)典卡茨馬爾茲收斂的點。

3　仿真實驗

圖1　仿真實驗所用的網(wǎng)絡(luò)

本文表述了SAK算法在圖1網(wǎng)絡(luò)的實時時延診斷方面的應(yīng)用。其目標(biāo)是使用探測數(shù)據(jù)包在遍歷網(wǎng)絡(luò)中不同路徑時所經(jīng)歷的端到端所得到的時延測量值，從而實時獲得鏈路時延統(tǒng)計的估計值。

本次仿真所用的實驗設(shè)置如下，我們選擇在網(wǎng)絡(luò)中六個途徑的先驗。

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

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

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

(a) 鏈路1

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

4　結(jié)　語

本文提出的基于隨機(jī)逼近算法和Kaczmarz算法的SAK算法，對驅(qū)除鏈路噪聲有一定效果，可用于樹狀拓?fù)浜筒糠志W(wǎng)狀拓?fù)涞耐茢?。還存在許多問題需要進(jìn)一步研究：(1)目前的測量方法和分析算法都只能用于小規(guī)模網(wǎng)絡(luò)，如何把這類方法運用于大規(guī)模網(wǎng)絡(luò)是面臨的一大難題；(2)現(xiàn)有的NT技術(shù)大都只能用于簡單樹狀拓?fù)涞耐茢?，怎樣把NT技術(shù)用于復(fù)雜網(wǎng)狀拓?fù)涫墙窈竺媾R的挑戰(zhàn)；(3)迄今為止的研究都是假定路由矩陣已知或者容易確定的情況下進(jìn)行的，因而尋求針對動態(tài)隨機(jī)路由的推測方法也是一大挑戰(zhàn)。

[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] 趙洪華,陳鳴.基于網(wǎng)絡(luò)層析成像技術(shù)的拓?fù)渫茢郲J].軟件學(xué)報，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] 張潤生,康一丁,張冠杰,等.基于非參數(shù)假設(shè)檢驗的拓?fù)渫茢嗨惴╗J].電子科技大學(xué)學(xué)報:自然科學(xué)版，2014，43(5)：764-768.

[6] 張潤生,李艷斌,李嘯天.基于合并分層聚類的網(wǎng)絡(luò)拓?fù)渫茢嗨惴╗J].電子學(xué)報，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] 朱三元,楊明,薛鈁.網(wǎng)絡(luò)通信軟件設(shè)計指南[M].北京：清華大學(xué)出版社，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] 徐恪,張賽,陳昊.在線社會網(wǎng)絡(luò)的測量與分析[J].計算機(jī)學(xué)報，2014，37(1):165-188.

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

[13] 羅瑞龍.SDN網(wǎng)絡(luò)的測量和檢測子系統(tǒng)的設(shè)計與實現(xiàn)[D].北京：北京郵電大學(xué),2014.

[14] 鄧建球,郝翠,鞠傳文,等.網(wǎng)絡(luò)測量及參數(shù)對網(wǎng)絡(luò)控制系統(tǒng)的影響[J].中南大學(xué)學(xué)報：自然科學(xué)版，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。國家自然科學(xué)基金項目(61163010);蘭州市科技計劃基金項目(2009-1-5);甘肅省自然科學(xué)基金項目(1308RJZA111)。吳辰文，教授，主研領(lǐng)域：網(wǎng)絡(luò)層析成像技術(shù)。朱建東，碩士生。閆光輝，教授。鄭恒，碩士生。張燁，碩士生。

TP393

A

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