基于NT技术中链路时延推测算法的分析研究

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于NT技术中链路时延推测算法的分析研究范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

1 引言

时延是网络性能参数的一个重要指标，准确及时地获得链路时延性能指标是有效控制、管理网络的客观要求。基于nt技术的链路时延估计方法，是将NT技术的原理应用到时延测量与估计上来，首先测得端到端链路时延参数，然后从测得数据出发，建立概率统计模型，最后分析推断链路内部时延性能特征。

NT技术中链路时延测量技术就是指通过测量直接得到网络端到端的时延数据，结合网络拓扑结构，利用统计学技术来分析推测具体的链路级时延分布。所以时延数据的测量，统计推测模型的建立，以及统计推理算法的选择是三个核心关键的研究焦点。

2 基于GMM时延的EM算法

EM算法是一种不完全数据下的参数估计算法。基本原理是：设数据Y是观测数据，数据Z是缺失数据，？兹是待估参数，？兹关于数据Y的后验分布为P（？兹 | Y）。但是P（？兹 | Y）极大化优化运算复杂，而P（？兹 | Y，Z）的优化运算比较简单，设缺失参数Z已知，利用分布P（？兹 | Y，Z）进行优化运算，再对数据Z的假设进行检验和改进，如此反复迭代直至收敛，这样就可以将一个复杂的极大化估计问题转化成一系列的简单的极大化参数估计问题，从而使得总体的计算复杂度下降。

高斯混合模型（ Gaussian Mixture Models ，GMM） 是一种基于正态分布的概率统计建模模型，对数据的处理能较好地逼近其概率密度分布函数，接近真实数据。从理论上说，高斯混合模型可以用来近似任意的概率密度函数。

假定某个信息的密度函数是由N个高斯成分来描述，而第i （i=1，2，...，N）个高斯成分的均值为？滋i，标准差为？滓i，权值为？棕i（其中■？棕i=1），则该信息的密度函数可表示为：

P（y | ？兹）=■？棕iNy（？滋i，？滓i2）

其中，？兹={？棕i，？滋i，？滓i2} ， Ny（？滋i，？滓i2） =■e

从接收端得到的测量数据Y={y1，y2，……yn}后，可以得到高斯混合模型下参数的对数极大似然函数表示为：

利用参考文献[3]的方法，可以得到EM算法的E-step和M-step两步运算的方法：

E-step：

其中，i={1，2...，N}上标（k）表示第k次迭代。

M-step：

，

重复以上两步迭代，当||Q（？兹i+1，？兹i）-Q（？兹i，？兹i-1）||足够小时，停止迭代。

用该算法对图1进行仿真，设网络拓扑结构已知，链路上的数字表示真实时延分布，根节点0负责发送探测包，叶节点负责探测包的接收及测量数据的收集。每组采样数据有七个分量，每个分量1000个抽样数据，用独立同分布的随机函数来模拟链路时延的随机分布。

图2是仿真的结果，通过仿真可知，基于高斯混合模型的EM算法具有很高的有效性，能够极其准确的模拟出链路时延的分布情况。时间复杂度为O（N2K）。在此算法的具体执行中，存在EM算法收敛较慢，需要很长时间执行迭代算法的问题。

基于高斯混合模型的链路时延推测的EM算法，在测试网络较为简单时，能够根据网络的端到端时延数据，有效的推出网络链路时延分布特性。但是算法本身具有两个不足：一是算法只能推测得到一条链路或者一条路径的时延分布，对于大规模的网络应用显然有些能力欠缺；二是算法的时间复杂度较高，当高斯成分较多，采样数据复杂时，算法的收敛速度慢，时间复杂度也较高。因此将高斯混合模型推广到有限混合模型，该算法可以同时推测多条链路的时延分布，再应用重要性抽样技术来降低算法的时间复杂度。

用有限混合模型来逼近链路时延密度函数，端到端时延密度就是链路时延密度的卷积。可以采用最大似然估计，从端到端时延测量结果中分离出各链路的各个混合成分的参数？兹，得到各链路的时延密度函数。

对某个端到端时延测量，有限混合模型的对数似然函数为：

其中有M个链路，每个链路的密度函数是由N个高斯成分和一个描述时延为零的？啄函数成分构成，T为重复进行的测量次数。s={s （i）m}，z={z （i）m ， j}，m=1，2，...，M；j=1，2，...，N；i=1，2，...，T，且满足z （i）m ， j=1，z （i）m ， k=0，k≠j，k=1，2，...，N。密度函数参数的初始值可取任意值，但初始值的选取对算法的收敛次数影响比较大。因此提出了采用辅助测量信息作为EM算法的初始值，算法复杂性为O（N2MT）。

3 基于重要性抽样时延估计方法

重要性抽样法是提高M_C（ Monte-Carlo）直接抽样法计算效率的一种方法，选择合适的重要性函数，是重要性抽样法能否成功的关键。基本原理如下：

其中p（x），g（x）是概率密度函数，则积分I 估计为：

g （ x）称为重要函数（ Importance Function ，简称IF） ，xh是根据g （ x） 分布抽取的第h 个样本，估计值■是无偏的， 其方差取决于g （ x） 的选择。

为了减小估计的误差和实现方便， 重要函数应该近似于原概率分布，并且易于从其中抽取样本. 把IS 方法应用于期望最大化方法，可以把从难以抽取样本的概率密度转换为从重要函数进行抽样。由于重要性抽样有效与否的关键在于重要性函数的选取，在把重要性抽样和EM算法相结合的算法中重点研究的是重要性抽样函数的选取。重要性抽样函数的选取要满足两个条件：（1）必须确保采用的重要性抽样函数g（x）与原模型的概率密度分布函数f（x）是同类型的函数；（2）引入重要性抽样技术的目的是把原密度函数f（x）向其“感兴趣的区域”移动，从而增加其在“感兴趣区域”的抽样概率，加速预期结果的出现。

在有限混合模型中端到端链路时延的联合密度函数函数式中，令：

则确定重要性抽样函数的方法如下：

（1）通过下面的两步操作找到对概率分布函数Pf贡献最大的点：

①使用JC方法求出的初始点作为x*

②用下列方程求出x*

Gi（x）=0为f（x）的极限状态方程。

（2）确定重要抽样函数g（x）的均值，重要性抽样函数g（x）和原概率密度分布函数具有相同的结构，服从同样的分布。因此设定重要性抽样函数的均值？滋g=x*。

（3）确定重要性抽样函数的标准差？滓g，具体方法如下：

任意确定一实数b，使得实数b满足关系：b>x*，将区间[x*，b]划分为m等分，分别从这m等分中，按照一次取出一个值的规则得到m个值。v1

当 时？滓g为：

g（x）与f（x）是同类型的概率密度函数，因此b可以取为f（x）标准差？滓的3～5倍。

由于重要性函数g（x）服从正态分布：

，

根据得到的g（x）的两个参数期望（均值）？滋g=x*和方差？滓g2，就可得出重要性函数g（x）。根据文献[9]中介绍的方法，由g（x）产生所需H样本（为了确保估计的准确性，H应该满足H≥■），将产生的样本向量代入EM算法的E-Step中进行迭代得到链路的时延估计。将重要性抽样技术应用其中，能有效的降低算法的复杂度，加速收敛。

4 仿真

在Matlab平台上仿真，设在测试网络内一条测量路径上包含两段链路，每一段链路的端到端时延密度分布函数都是由两个高斯成分和一个delta函数叠加而成。

第一条链路的参数包括：

第二条链路的参数包括：

要生成T个时延值，首先，确定两个链路的参数值；然后，按照概率？棕1，j，使时延为0或落在两个高斯成分的任意一个里，随机生成链路1的时延值。设T=10000。链路1的初始值为：

链路2的初值可以随便设定。表1、图3、图4显示了真实值与估计值的比较。

从仿真结果可看出在模型的基础上提出采用重要性抽样技术来提高抽样效率，降低运算复杂的的方法，能够较为精确的从端一端时延的测量结果推测出多条测量路径上的链路时延分布。算法复杂性为O（N×L×H）， N为各链路的高斯成分个数，L为测量路径上的链路数，H为采样样本个数（H≥■）。算法能有效地逼近真实的源信号。能够在基本保持估计算法准确性的基础上，提高算法的收敛速度，降低运算时间复杂度。

5 结束语

有限混合模型的算法解决了基于高斯混合模型的链路时延EM算法中存在的收敛速度慢和每次只能计算一条链路的不足，利用链路数据的卷积可以同时计算多条链路的问题，并且降低算法的时间复杂度，加速算法的收敛。但在此算法中，各链路时延密度函数的高斯成分个数是事先确定的，这不符合实际应用的情况，后续的工作将采用非监督学习技术估计出高斯成分个数，这样就能够进行自适应参数估计。

参考文献

[1] LAWRENCE E， MICHAILIDIS G， NAIR V N. Maximum Likelihood Estimation of Internal Network Link Delay Distributions Using Multicast Measurements[C] //Conference on Information Sciences and Systems. [S. .l ]： the Johns Hopkins University， 2003： 1123-1128.

[2] 李东， 张乃， 孙怡. 网络透视中延迟推理算法的研究和改进[J]. 哈尔滨工业大学学报， 2009， （01） ：89-92.

[3] 李勇军，蔡皖东，王伟.网络断层扫描技术综述[J]. 计算机工程，2006，32（13）：91-93.

[4] 刘瑞芳.网络性能测量和推测技术的研究[D]. 北京邮电大学 2006.

[5] PADMANABHAN V， QIU L， WANG H. Server-base inference of Internet link lossiness[C] //Proc of IEEINFOCOM '03. San Francisco， CA， USA： [ s. n. ]， 2003： 2017-2031.

[6] 金光.重要性抽样法研究[J].系统仿真学报， 2002， （09）.

[7] 王伟，蔡皖东，李勇军.网络断层扫描中推断分析理论与方法的研究[J]. 计算机应用研究，2007.

[8] 李雄，黄建国，张群飞.基于重要性抽样的最大似然方位估计方法[J]. 电子学报， 2005， （08）.

[9] SHIHM F， HERO IIIO. Topology Discovery on Unicast Networks： A Hierarchical Approach Based on End-to-End Measurements. CSPL Technical Report TR -357： Dep.t of EECS， University of Michigan， 2005（8）：3852-3855.

[10] S M Kay ，Supratim Saha.Maximum likelihood parameter estimation of superimposed chirps using Monte Carlo Importance sampling[J ] . IEEE Transactions on Signal Processing ，2002 ，50.

作者简介：

马宏艳（1978-），女，汉族，甘肃庆阳人，讲师，硕士；主研方向：计算机网络。

吴辰文（1964-），男，汉族，甘肃兰州人，教授；主研方向：无线传感器网络、下一代网络。