3)学习问题。 给定一个观察序列O＝1，2，,T,如何调整优化模型参数=（，A，B），使得P（O |）最大。目前普遍使用的方法是Baum.Welch估计算法［9］。 2.2HMM可用带宽模型 在一条端对端路径上可用带宽可以被抽象成N个
3)学习问题。
给定一个观察序列O＝ξ1，ξ2，…,ξT,如何调整优化模型参数λ=（π，A，B），使得P（O |λ）最大。目前普遍使用的方法是Baum.Welch估计算法［9］。
2.2HMM可用带宽模型
在一条端对端路径上可用带宽可以被抽象成N个状态，每一个状态代表一定程度的利用率。例如在图2的五个状态中，可用带宽的状态从低到高分别为L，ML，M，MH，H。也就是说，它可以位于范围从［0，0.2），［0.2，0.4），［0.4，0.6），［0.6，0.8），或［0.8，1］内的任何利用率。如果能观察到时间T内的连续状态，那么每个状态范围中间点的平均值就可以认为是时间T内的可用带宽的一个估计。状态定义得越多，每个状态所呈现的可用带宽的范围就会越小，所估计的结果就会越准确。
图片
图2可用带宽模型
然而可用带宽的状态不能直接观察到，但可以通过HMM模型来估计这些未知的状态。这种模型能够用于找出在一定时间段内的与包分布有关的状态序列。它是由X个代表不同可用带宽水平的不相关联的隐藏状态以及所观察到的探测包对的分布变量ξ所组成。B代表在一个特定的状态下所观察到的状态概率。可用带宽状态之间的过渡用矩阵A来表示。这个模型在每一次新的观察出现之后就会被优化一次，用于决定在时间T内所产生的状态序列。最终，时间T内估测到的状态序列的平均值即为可用带宽的平均值。模型如图3所示。图片
图3可用带宽的HMM
2.3HMM的可用带宽模型的组成
1)模型中的状态数目N。
定义状态集合为S＝｛S1，S2，…,Sn｝，代表可用带宽的水平依次从低到高排列。再定义t时刻的状态为Xt。
2)每一个状态所产生的观察符号的数目（M）。
每一个状态会产生很多可能的结果，也就是说，这些符号的集合是和观察到的探测样本的方法相关联的。
ξ=「M*|1-ε|(5)
3)状态之间的过渡矩阵A。
在HMM中，假设状态之间的过渡只发生在相邻的状态，于是就可以设定好初始的状态矩阵。这个假设有利于初始的计算以便找到模型参数。因为矩阵中的未知元素已被减少到只剩三条斜线。这对于夹杂着背景流量的探测包对来说是一个很好的假设。然而实际情况并不总是这样的，由于一个探测包对夹杂着背景流量，而它随后的一个却找到了空闲的通道，这样会导致状态不是在相邻的状态之间过渡。但随着时间的推移，HMM会了解这种过渡并对过渡概率做出相应的调整。
5)初始状态概率π。
这是初始状态概率分布的一个矢量,于是可以把模型记为λ=（π，A，B）。
2.4 参数估计
给定一个时间T内的观察序列O＝ξ1，ξ2，…,ξT，要估算出最有可能产生此序列的模型λ=（π，A，B），并且使得P(O|λ)最大,可以通过Baum.Welch算法来解决。这个算法的目的就是对于每一个新观察到状态序列来更新可用带宽模型。这个算法有两处主要的修改，第一个就是初始转移概率矩阵A是随机生成的是一个一步到位的过渡矩阵。因此，在矩阵中只有三条斜线上有非零数值。第二个就是观察概率矩阵B是固定的。以便状态所产生的观察概率不会改变。这是因为，高度拥挤的链接将增加数据包之间的分散性，反之亦然。事实上，一条链路上没有背景流量的话数据包对之间的分散将为零（或接近零）。整个算法的时间复杂度为O（N2T），运行的步骤如下：
1)设定初始模型λ0 ，A0，π0；
2)通过λ0和观察到的状态序列O算出一个新的λ=(A,B0, π)；
3)如果log P(O| λ)-log P(O|λ0 )<0.001 就停止，否则λ0 ←λ回到第2)步。
在这个算法中要注意到B0已经初始化好了，并且固定不变，在前文已经解释过。
2.5状态序列估计
对于给定观察序列O以及模型λ,下一个问题就是如何选择一个对应的状态序列S ，使得S能够最为合理地解释观察序列O，这个状态序列用于计算时间T内的平均可用带宽，通过Viterbi算法可以解决这个问题。这个算法的时间复杂度也为O（N2T）。该算法从一个特定状态到所有可能的路径中选择最有可能的路径，并对每个状态重复这样做，最终最有可能的路径就代表了可用带宽的等级。因此，可用带宽是通过这个状态序列的平均值得出来的。3改进后的带宽测量算法
针对Spruce［10］带宽测量，这个算法的时间复杂度为O(2NT)。本文提出了改进后的基于HMM的算法（Wspruce），该算法能够提供快速、连续、准确的可用带宽估计。客户端每10个估计为一个循环周期。在初始估计中，这个工具发送50个UDP包对1498个字节长度。剩下的9个估计每一个发30个包对。基于HMM，这种减少方案是可行的，它能从初始样本中了解可用带宽的变化，并从减少规模的样本中更新模型。从实验中可以发现，重新学习10个估计足以保证好的准确性和低的负载。使用50个包对也能训练这个模型，并能得到最好的估计结果。未来研究的主要工作是当探测包的数量变化时，这个工具的准确性。
Wspruce对包间隔以及包对之间的间隔使用了不同的变量，包间隔也就是每个包对中两个数据包之间的间隔，在发送端进行设定好，用Δin表示，和在紧致链路的一个单独的探测包传输时间是一致的。数据包对在队列中传输会夹杂着背景流量。包对之间的时间间隔通过gettimeofday()函数功能来实现，这个值会发送到接收端。
它通过使用指数方式分布的包间隔时间来执行路径上的可用带宽的泊松样本进程。为了使负载便于控制和比较低，包间隔时间平均值已被计算出，这样这个工具的最大负载就会是紧致链路容量的5%甚至更低。
在接收端，Wspruce的服务器应用程序在内核层为每一个接收到的数据包建立时间戳。这是通过在接口的SO_TIMESTAMP［11］选项来实现的。数据包被编号以便决定哪些数据包在同一对中并且计算出它们之间正确的相对时间分布ε。通过代入式(5)，对于每一个数据包对来说，HMM中相应的观察符号也就确定了，改进后算法的时间复杂度为O（N2T）。
Wspruce中的HMM模块从一个文件中读取N，M，B并通过接收端的已经计算出的50个或者更少的观察结果来计算出模型λ，这个模型用于决定最有可能产生观察序列的状态序列。初始模型λ0是上一次估计的输出。最终，状态序列的平均值乘以紧致链路的容量也就得出了一个最终的可用带宽估值。这个工具的核心算法流程如下： (责任编辑：南粤论文中心)转贴于南粤论文中心: http://www.nylw.net(南粤论文中心__代写代发论文_毕业论文带写_广州职称论文代发_广州论文网）
顶一下
(0)
0%
踩一下
(0)
0%
版权声明：因本文均来自于网络，如果有版权方面侵犯,请及时联系本站删除.
