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

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

?

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

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

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

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

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

0　引　言

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

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

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

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

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

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

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

Yt=AXt+ε

(1)

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

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

(2)

其中，W測(cè)量中隨機(jī)變量噪音的有界方差，其均值為零。Z是取值范圍為[m]的隨機(jī)變量,對(duì)于?i∈[m],λi>0表示Pr{Z=i}{Xk},{Zk},{Wk},k≥1是X,Z,W的IID副本，它們是完全獨(dú)立的并且Yk表示AXk+Wk。假設(shè)在每一個(gè)時(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)是一個(gè)滿(mǎn)足∑ηk=∞和∑(ηk)2<∞的一個(gè)正值步長(zhǎng)序列，ξk+1表示噪聲干擾。當(dāng)ηk→0時(shí),式(3)可被看作噪聲離散化的常微分方程。

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

(4)

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

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

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

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

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

2.2Kaczmarz算法

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

(5)

通過(guò)基本的計(jì)算，顯示其解為:

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

(6)

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

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

(7)

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

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

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

2.3SAK算法

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

EY=AEX

(8)

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

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

(9)

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

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

(10)

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

我們現(xiàn)在再來(lái)分析它的行為。顯然，所述迭代式(9)的{xk}總是保持局限于Α0，在式(6)下定義了仿射空間。由于A行滿(mǎn)秩，對(duì)于每個(gè)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算法會(huì)收斂于式(9)的x*，x*也是對(duì)應(yīng)的經(jīng)典卡茨馬爾茲收斂的點(diǎn)。

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

圖1　仿真實(shí)驗(yàn)所用的網(wǎng)絡(luò)

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

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

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

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

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

(a) 鏈路1

(b) 鏈路3圖2　用SAK算法對(duì)候選鏈路1和3預(yù)期時(shí)延的在線(xiàn)估計(jì)

4　結(jié)　語(yǔ)

本文提出的基于隨機(jī)逼近算法和Kaczmarz算法的SAK算法，對(duì)驅(qū)除鏈路噪聲有一定效果，可用于樹(shù)狀拓?fù)浜筒糠志W(wǎng)狀拓?fù)涞耐茢唷＿€存在許多問(wèn)題需要進(jìn)一步研究：(1)目前的測(cè)量方法和分析算法都只能用于小規(guī)模網(wǎng)絡(luò)，如何把這類(lèi)方法運(yùn)用于大規(guī)模網(wǎng)絡(luò)是面臨的一大難題；(2)現(xiàn)有的NT技術(shù)大都只能用于簡(jiǎn)單樹(shù)狀拓?fù)涞耐茢啵鯓影袾T技術(shù)用于復(fù)雜網(wǎng)狀拓?fù)涫墙窈竺媾R的挑戰(zhàn)；(3)迄今為止的研究都是假定路由矩陣已知或者容易確定的情況下進(jìn)行的，因而尋求針對(duì)動(dòng)態(tài)隨機(jī)路由的推測(cè)方法也是一大挑戰(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é)報(bào)，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] 張潤(rùn)生,康一丁,張冠杰,等.基于非參數(shù)假設(shè)檢驗(yàn)的拓?fù)渫茢嗨惴╗J].電子科技大學(xué)學(xué)報(bào):自然科學(xué)版，2014，43(5)：764-768.

[6] 張潤(rùn)生,李艷斌,李嘯天.基于合并分層聚類(lèi)的網(wǎng)絡(luò)拓?fù)渫茢嗨惴╗J].電子學(xué)報(bào)，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è)計(jì)指南[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] 徐恪,張賽,陳昊.在線(xiàn)社會(huì)網(wǎng)絡(luò)的測(cè)量與分析[J].計(jì)算機(jī)學(xué)報(bào)，2014，37(1):165-188.

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

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

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

TP393

A

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