有噪网络断层扫描方法研究

吴辰文　朱建东　闫光辉　郑　恒　张　烨

(兰州交通大学电子与信息工程学院　甘肃 兰州 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