基于KDT的人体运动数据行为分割.pdf

该【基于KDT的人体运动数据行为分割 】是由【珍珠夸克】上传分享，文档一共【10】页，该文档可以免费在线阅读，需要了解更多关于【基于KDT的人体运动数据行为分割 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。中国科技论文在线
基于马尔可夫模型的端到端流量预测方法
研究#
蒋定德,聂来森,秦文达*
5(东北大学信息科学与工程学院,沈阳110819)
摘要:针对当前通信网络中端端流量预测问题,研究端到端流量的准确预测方法,通过将端
到端流量建模为马尔可夫模型来描述其时间相关性和动态变化特性,并利用测量样本建立马
尔科夫模型的转移概率矩阵,考虑到端到端流量所满足的约束条件,首先预测获得单条端到
10端流量流的预测值,然后获得所有端到端流量流的预测,最后通过约束调整获得最终的预测
结果。仿真结果表明所提出的预测方法能精确预测端到端流量并能准确捕获它的动态变化,
与以前的方法相比,具有更好的预测性能和更低的预测误差,并具有明显的性能改善。
关键词:网络流量;马尔可夫模型;流量预测;加权平均;预测误差
中图分类号:TP393
15
OnPredictionApproachofEnd-to-EndTrafficBasedon
MarkovModel
JiangDingde,NieLaisen,QinWenda
(CollegeofInformationScienceandEngineering,NortheasternUniversiy,Shenyang110819)
20Abstract:Forthepredictionproblemofend-to-endtrafficincurrentcommunicationnetworks,
thispaperstudiesthepredictionmethodaboutend-to--to-endtrafficismodeledas

samplesaboutend-to-endtrafficareusedtobuildthetransitionprobabilitymatrixoftheMarkov
-to-endtraffic,end-to-endtrafficiseach
-to-

approachcanaccuratelypredictend-to-endtrafficandcaptureitsdynamicchange,andincontrast
topreviousmethods,itholdsthebetterpredictionperformanceandlowerpredictionerrorsandhas
thelargerperformanceimprovement.
30Keywords:networktraffic;Markovmodel;trafficprediction;weightedaverage;predictionerrors
0引言
端到端流量反映了通信网络中网络级流量的变化情况,其作为网络管理的重要输入参
数,是网络设计、规划和优化的重要参考依据。但由于端到端网络流量隐藏在链路流量中,
35要直接获得非常困难[1-3]。端到端流量预测是获取端到端流量的有效手段,已成为当前的研
究热点[4-6]。然而,由于其动态变化和随机突发性,要进行准确预测是困难的,端到端流量
预测引起了研究人员的广泛关注[5-9].
Pascal[6]利用自适应贝叶斯网络来预测流量流;Zhang等人[7]利用重力模型来建模和预测
端到端流量;Lakhina等人[8]研究了大尺度IP骨干网络端到端流量矩阵,分析了端到端流量
40流的结构,利用主成分分析方法来建模和分析网络级流量的特征和属性,并提出相应的预测
基金项目:国家自然科学基金项目();高等学校博士学科点专项科研基金资助课题(No.
20100042120035);新世纪优秀人才支持计划项目(-11-0075);中央高校基本科研业务专项资金资
助课题(,N110404001)。
作者简介:蒋定德,男,副教授,主要研究方向:网络测量、网络体系结构和协议分析
-1-
中国科技论文在线
方法;Filho[9]通过主成分分析和K-meas方法进行流量预测;Adelani等人[10]结合迭代比例拟
合算法、fan-out算法、EM(Expectation-Maximization)算法和神经网络来提出一种混合
预测方法对端到端流量进行预测和估计。由于网络流量的动态变化[11]和自相似性[12],要建
立精确的网络级流量模型是困难的。Federico等人[13]利用统计反演和alpha稳定模型来建模
45网络流量;Stolojescu等人[14]研究了WiMAX网络中流量的长相关特性;Zhang等人[15]利用压
缩感知(compressivesensing)来对网络流量进行分析和预测。然而由于网络级流量的高
动态变化和波动特性,所有这些方法都存在一定的预测误差,要精确预测网络级流量仍然具
有诸多困难。
本文研究了通信网络中端端流量的预测问题,基于马尔可夫过程提出了一种新的预测方
50法来获得网络级的端到端流量。马尔可夫过程被用来描述端到端流量的时间相关性和动态变
化,通过端到端流量的测量样本,利用聚类算法来准确构建其转移概率矩阵,并考虑端到端
流量的非负性来构建每一条端到端流量,从而进一步获得所有的端到端流量预测值,然后基
于网络级流量在路由矩阵下进行数据转发和疏导而在汇聚到链路上的约束条件,通过约束调
整获得最终的预测结果。
551问题阐述
端到端流量描述网络中所有源-目的节点间的流量随时间的变化情况,本文研究骨干网
络的端到端网络流量预测问题。假设对于一个具有N个节点,R条链路的网络,其共有N2
条端到端流量流,所有的端到端流量构成端到端流量矩阵,可表示为
X(t)[x(t),x(t),...,x(t)]',它是一个2的矩阵,随着时间的变化而变化,其中xt()
12N21Ni
2
60表示端到端流量(iN1,2,...,)。端到端流量xti()更加网络路由矩阵将数据包沿着指定路
径通过链路传输,所有的端到端流量在不同的链路上汇集成链路流量,因此链路流量、路由
矩阵和流量矩阵间满足如下的约束关系:
Y(t)AX(t)(1)
其中,Y(t)[y(t),y(t),...,y(t)]'表示链路流量,为网络中链路数目,Aa()为
12RRijRN2
2
65一RN的路由矩阵,当端到端流量j经由链路i传输时,aij为1,否则为0。本文要解决
的问题是如何对所有的端到端流量xti()进行建模和预测,并让其预测结果满足等式(1)的
约束条件,或者说通过对所有的端到端流量进行建模分析,由路由矩阵和链路流量来预测隐
含在链路流量中的端到端流量信息。由于路径矩阵A是非满秩矩阵,其秩非常小,要由等
式(1)直接获得端到端流量是困难的,下面将讨论本文提出的预测方法。
702网络流量建模
在本文中,马尔可夫模型[16-18]用来描述端到端网络流量的动态变化,并对网络流量进行
建模描述。端到端网络流量描述网络中的从源节点到目的节点的网络流量的动态变化,其与
网络设备、网络用户的活动情况紧密相关,是网络设备和网络用户访问网络的外在体现,这
种流量行为可以表示为某一随机过程。某一条端到端流量随着时间而动态变化,就要波动性、
75突发性和随机性,但其在时间上具有某种相关性,即当前时刻的端到端网络流量与前一时刻
或前几个时刻的网络流量相关性。为了准确描述网络流量的这些动态行为,我们考虑使用一
阶、二阶和三阶马尔可夫模型来描述端到端网络流量。
对于网络中每一条端到端流量xi(t),定义其状态空间为i{i12,i,...,iz},其中
2
iN1,2,...,,z为整数表示状态数目,ii1min(xt()),izmax(xti()),则xi(t)可
-2-
中国科技论文在线
80用一阶马尔可夫建模为[16-17]:
P{x(t1)|x(t),...,x(2),x(1)}
iiiitii21ii(2)
P{xi(t1)i|xi(t)it}
其一阶转移概率矩阵是一个二维矩阵,记为11i{Pi(i,it)}zz,其中P1i(i,it)表
示一阶转移概率矩阵1i的元素,i,iti。
可用二阶马尔可夫建模为[16-17]:
P{xi(t1)i|xi(t)it,...,xi(2)i21,xi(1)i}
85(3)
P{xi(t1)i|xi(t)it,xi(t1)i(t1)}
其二阶转移概率矩阵是一个三维矩阵,记为2i{P2i(i,it,i(t1))}zzz,其中
P2i(i,it,i(t1))表示二阶转移概率矩阵2i的元素,i,,iti(t1)i。
可用三阶马尔可夫建模为[16-17]:
P{xi(t1)i|xi(t)it,...,xi(2)i21,xi(1)i}
(4)
P{xi(t1)i|xi(t)it,xi(t1)i(t1),xi(t2)i(t2)}
90其三阶转移概率矩阵是一个四维矩阵,记为3i{P3i(i,it,i(t1),i(t2))}zzzz,其
中P3i(i,it,i(t1),i(t2))表示三阶转移概率矩阵3i的元素,i,it,i(t1),i(t2)i。
对具有N个节点和R条链路的网络中的所有端到端网络流量,只要其一阶、二阶和三
阶转移概率矩阵确定,就可以根据等式(2)、(3)和(4)描述其动态变化。下面进一步
讨论基于该模型进行端到端网络流量的预测方法。
953端到端流量预测
本文利用马尔可夫模型来预测端到端网络流量,首先通过端到端网络流量的先验测量值
来建模等式(2)、(3)和(4)所描述的端到端流量模型,然后构造相应的预测方法。由
于端到端流量动态变化,不同时刻的流量值随机变化,要建立关于端到端流量的马尔科模型,
需要将流量样本数据划分到不同的状态空间中,本文采用模糊聚类的方法来解决这一问题。
100为了建立等式(2)、(3)和(4)所描述的端到端流量模型,利用聚类方法[18]对先验端到
端流量测量值进行聚类,并获取各聚类中心及对应的隶属度矩阵,然后根据隶属度矩阵来生
成转移概率矩阵,从而建立端到端网络流量的马尔可夫模型[16]。
T
对于端到端流量xi(t),T个时刻的观测样本数据集Xi=[xi(1),xi(2),...,xi(T)](其中
2T
iN1,2,...,),根据模糊C均值聚类算法将Xi划分为z个聚类,且其z个聚类的聚类中
105心表示为vi{vi12,vi,...,viz}。在模糊聚类中,每一个数据并不严格地划分到某一类中,而
i
是以一定的隶属度归属于各个聚类。定义隶属度为kcs,其表示第s数据点属于第c类的隶
iiii
属度,其中sT{1,2,...,}和cz{1,2,...,},kcs[0,1],且k12sks...kcs1。隶属
度矩阵可表示为[18]:
iii
k11,k12,...,k1T

ki,ki,...,ki
K21222T(5)
i...

iii
kz1,kz2,...,kzT
110另外,由于端到端网络流量描述真实值,则聚类中心满足如下约束关系:
-3-
中国科技论文在线
vi{vi12,vi,...,viz},vij0,j1,2,...,z(6)
[18]
根据模糊C均值聚类算法,对于端到端流量xi(t),获取各聚类中心及对应的隶属度
矩阵的具体步骤如下算法1所示:
算法1:
115步骤1:初始化端到端流量xi(t)的聚类数目z、迭代误差门限、模糊系数m和最大迭代次
0
数L。初始化初始隶属度矩阵Ki[1,1,...,1],迭代变量l1。
步骤2:由端到端流量xi(t)的T个数据集中随机等概率抽取z个样本作为端到端流量xi(t)
lllll
第l次迭代的聚类中心vi,即vi{vi12,vi,...,viC}。
l
步骤3:计算第l次迭代隶属度矩阵Ki。定义
120Is{c|1cz,dcs0}(7)
Iss{1,2,...,z}I(8)
il
其中,dcsxsvc表示第s个数据到第c个类中心的距离。当Is时,kcs为:
2
1
zdm
ilcs(9)
kcs1
j1dis
il
其中,kcs表示在第l次迭代中,第s个数据与第c个类的隶属度。当Is时,
il[18]
125cIs,0kcs,且满足如下约束条件:
ililil
k12sks...kzs1(10)
ll
步骤4:根据Ki计算vic如下:
TT
lilmilm
vic(kcs)xi(s)(kcs)(11)
ss11
lll
步骤5:如果vic0,则令vvicic,并转入步骤3。
ll1
130步骤6:判断KKii是否成立。如果成立,则转入Step7;否则令ll1。
步骤7:如果lL,转入Step3。
ll
步骤8:保存聚类中心vvii及对应的隶属度矩阵KKii到文件,并退出。
通过以上算法步骤,可获得所有端到端流量的聚类中心和隶属度矩阵,从构建相应的端
到端流量马尔可夫模型。现在讨论基于马尔可夫模型的端到端流量预测方法。对端到端流量
TT
135xi(t),观测样本数据集Xi=[xi(1),xi(2),...,xi(T)]。在Xi中随机抽取z个数据,并记为
0000
vi{vi12,vi,...,viz}。利用算法1获取聚类中心vi及其隶属度矩阵Ki。根据概率论,一阶马
尔可夫过程的状态转移概率计算为:
1Tkkii
P(,)q(j1)rj(12)
1iiriqi
Tkj2qj(1)
其中,ir,iqi;q,r1,2,..,z;P1i(ir,iq)表示已知当前时刻状态为iq,下一个时刻
140状态为ir的概率。通过等式(12)获得一阶转移概率矩阵1i,从而确定端到端流量的一
阶马尔科夫模型。
二阶马尔可夫过程的状态转移概率计算为:
-4-
中国科技论文在线
1Tkikiki
P(,,)p(j2)q(j1)rj(13)
2iiriqipii
Tj3kp(j2)kq(j1)
其中,ir,,iqipi;p,q,r1,2,..,z;P2i(ir,iq,ip)表示已知当前时刻和前一时刻状态
145为iq和ip,下一个时刻状态为ir的概率。通过等式(13)获得二阶转移概率矩阵2i,
从而确定端到端流量的二阶马尔科夫模型。
三阶马尔可夫过程的状态转移概率计算为:
1Tkikikiki
P(,,,)p(j3)p(j2)q(j1)rj(14)
3iiriqipioiii
Tj4kp(j3)kp(j2)kq(j1)
其中,ir,,,iqipioi;o,p,q,r1,2,..,z;P3i(ir,iq,ip,io)表示已知当前时刻和前两
150个时刻状态为iq、ip和io,下一个时刻状态为ir的概率。通过等式(14)获得三阶转
移概率矩阵3i,从而确定端到端流量的三阶马尔科夫模型。
根据等式(12)、(13)和(14)确定的一阶、二阶和三阶马尔可夫模型的转移概率矩
阵,根据当前和前两个时刻的端到端流量值,选择最大转移概率对应的值为t1时刻端到
端网络流量最可能的取值,则分别获得一阶、二阶和三阶马尔可夫模型的预测值为

155x1i(t1)、x2i(t1)和x3i(t1)。通过加权平均可以获得网络流量的预测值为:

xˆi(t1)1x1i(t1)12x2i(t1)13x3i(t1)(15)
其中,为加权系统且为0到1之间的常数。但由于端到端流量是真实数据,所以其应该满
足非负约束条件,则等式(15)应该变为下面等式:

xˆi(t1)xi(t1)(1)xi(t1),xˆi(t1)0(16)
160根据等式(16)可以获得所以的端到端流量,即:
Xˆ(t)=[xˆ(t1),xˆ(t1),...,xˆ(t1)]'(17)
12N2
等式(17)满足等式(1)的约束条件,则根据等式(1)、(16)和(17),得到最后的预测等式如下:

xˆ1(t1)x1(t1)(1)x1(t1)

xˆ(t1)x(t1)(1)x(t1)
222
...

xˆ(t1)x(t1)(1)x(t1)(18)
N2N2N2
xˆ(t1)0,i1,2,...,N2
i
ˆ
Y(t)AX(t)
但由于网络是动态变化的,在不同时刻的网络流量差别很大,下一时刻的网络流量只与
165当前时刻及前几个时刻的网络流量具有较强的相关性,而与其他时刻的流量信息也许没有多
少关联,从而根据以上建立的流量模型将不能很好捕获经过多个时刻后流量的变化特性。本
文提出利用滑动时窗来解决这一问题,通过建模时窗hm和预测时窗he,首先利用在建模时
窗hm内建立关于网络流量的各阶马尔可夫模型,然后利用该模型在预测时窗he内进行预测
并获得相应时刻的流量值;当对预测时窗内所有时间点预测结束后,滑动he个时间点,在
170新的建模时窗hm和预测时窗he重复上述过程。根据以上分析,可以得到端到端网络流预测
-5-
中国科技论文在线
的具体算法步骤如下算法2所示:
算法2:
T
步骤1:给出建模时窗长hm和预测时窗长he;并给出建模时窗hm内端到端流量样本Xi。
步骤2:初始化一阶、二阶和三阶模型的状态空间i{i12,i,...,iz}。
175步骤3:根据算法1和等式(5)-(11),计算聚类中心vi及其隶属度矩阵Ki。
步骤4:根据等式(12)-(14),计算t1时刻端到端网络流量的一阶、二阶和三阶的状态
转移概率P1i(ir,iq),P1i(ir,iq,ip)和P1i(ir,iq,ip,io)。
步骤5:根据等式(15)-(16)获得t1时刻端到端网络流量的预测值xˆi(t1)。
步骤6:根据等式(16)-(18)获得t1时刻所有端到端网络流量的预测值Xtˆ(),并根据
180等式(19)进行调整,使其满足等式(1)的约束条件。
步骤7:如果预测时窗he内流量预测没有结束,则转步骤5。
步骤8:判断预测是否结束,如果没有,则滑动he个时间点,,转入步骤1重复执行。否则保
存结果并退出。
根据算法2,可获得网络中所有端到端流量的预测值,并准确获得网络级的流量信息。
1854仿真分析
仿真实验使用来自Abilene网络上的真实数据来验证本文提出的方法。本文提出的方法
基于二阶马尔科夫来进行端到端流量预测,简称为SMTP(Second-orderMarkov-based
end-to-endTrafficPrediction)。图1表示了用于仿真的网络拓扑结构,其中圆圈中数字表示路
由器编号,箭头旁边数字表示网络内部链路序号。Abilene网络有12个节点,144条端到端流
190量流。文献[7]的TomoGravity方法(为了方便表示,在仿真图中简写为TomoG)、文献[8]PCA
方法和文献[15]的SRSVD方法被报道为能对端到端流量进行准确预测。本文将SMTP和这三
种方法进行比较,分析他们的端到端流量预测、空间相对误差和时间相对误差,以及性能改
善。Abilene网络上连续1周数据被用来仿真四种方法,其中前1000个数据用来建立端到端流
量模型,其余500个数据用于性能分析。
195
图1仿真拓扑.
.

200图2和图3表示了四种方法在Abilene网络上的端到端网络流量预测结果。图2表明,在
Abilene网络上,端到端网络流量具有明显的动态变化,而且具有突变和周期性变化特征。
从图2可以看到,四种预测方法都能准确预测端到端流量的变化趋势,但是,TomoGravity
产生了过预测(如端到端流36),PCA预测结果有较大的波动(如端到端流36和78),SRSVD
-6-
中国科技论文在线
77
x10x10

Real3Real
2
SMTPSMTP

SRSVDSRSVD
1
TomoG1TomoG

00
100011001200130014001500100011001200130014001500
(a)OD36(a)OD92
77
x10x10

Real3Real
2
SMTPSMTP
PCA

SRSVDSRSVD
1TomoG
1TomoG

00
100011001200130014001500100011001200130014001500
(b)OD78(b)OD132
.
-to--to-endflows92and132.
210能获得较好的预测结果,但和真实的端到端流量相比,SMTP获得了最准确的预测值并能准
确预测端到端流量的变化和波动。图3表明,在Abilene网络上,当端到端网络流量缓慢变化或
者拘役类似周期性特征时,四种方法也跟踪流量的动态变化趋势,但相比之下,TomoGravity
和SRSVD出现了过预测(如端到端流92),尽管PCA能获得更好的预测结果,但也发生了
过预测并且预测结果和真实之间总是有较大的波动而不能很好的预测端到端流量(如端到端
215流92),SMTP的预测结果更接近真实值。图3也表明,尽管PCA、SRSVD和TomoGravity能
获得相当准确的预测值,但与SMTP相比,他们的预测结果仍具有较大的误差(如端到端流
132)。而且,图2和图3也表明,PCA、SRSVD和TomoGravity预测结果不稳定,其有时能
比较准确预测端到端流量,而有时又产生较大预测误差,相比之下,SMTP却能更准确的预
测端到端流量。这表明SMTP具有更好的预测性能。

端到端流量的时间和空间相对预测误差表示了预测方法的预测性能,其中空间相对预测
误差表示预测误差随端到端流量变化的空间关系,反映了预测方法在空间上的预测精度;其
时间相对预测误差表示预测误差随时间变化而变化的情况,反映了预测方法在时间上的预测
精度[5,19]。端到端流量的空间和时间相对预测误差分别定义如下[5,19]:
||xˆM(n)xM(n)||22||xˆP(t)xP(t)||
225errsp(n),t1,2,...,M;errtm(t),n1,2,...,P(19)
||xMP(n)||22||x(t)||
其中,P、M分别为端到端流量流的总数和总的测量时刻;errsp()n表示相对于所有测量时刻,
第n条端到端流量流的空间相对误差;xnM()和xnˆM()分别表示相对于所有测量时刻,第n
条端到端流量流的真实值和估计值;errtm()t表示时刻t时,所有端到端流量流的时间相对
[5,20]
误差;xtP()和xtˆP()分别表示时刻t时所有端到端流量流的真实值和估计值。
230图4表示了四种预测方法在Abilene网络上的时间和空间相对预测误差。图4(a)表明,在
Abilene网络上,TomoGravity和PCA具有较大的空间相对误差,尽管SRSVD相对于
TomoGRavity和PCA具有较小的空间相对误差,但相对于SMTP,SRSVD仍然具有较大的空
间相对误差,SMTP具有最小的空间相对误差。从图4(a)可以看到,SMTP不能准确预测较大
端到端流量流,而且其也能准确预测较小的端到端流量流,相比之下,尽管PCA、TomoGravity
235和SRSVD具有对较大的端到端流量流具有较大的预测误差,但对较小的端到端流量具有较
-7-
中国科技论文在线
8
SMTP1SMTP

SRSVDSRSVD

4TomoGTomoG
CDF

2

(a)Spatialrelativeerror00
020406080**********.
FlowIDfromsmallesttolargestinmean(a)Spatialrelativeerror

SMTP1SMTP

SRSVDSRSVD


CDF



(b)Temporalrelativeerror00

time(b)Temporalrelativeerror
.
.
大的预测误差。这表明SMTP能准确预测所有的端到端流量流。图4(b)表明,在所有的预测
时刻上,SMTP都具有小得多的时间相对误差,它的时间相对误差曲线大部分在PCA、
TomoGravity和SRSVD的时间相对误差曲线的下面,这表明SMTP对不同时刻的端到端流量
245流量能进行准确预测,具有较好的预测能力。
为进一步分析四种方法的预测能力,下面将讨论他们的空间和时间相对误差的累积分布
CDFs(cumulativedistributionfunctions)。图5表示了Abilene网络上四种方法的空间和时间相对
误差的累积分布。图5(a)表明,SMTP的空间相对误差累积曲线远在其他三种方法的上面,
这进一步表明SMTP具有更小的空间相对误差。而且从图5(a)可以看到,当空间相对误差大
,%的端到端流量流,而对其他三种方法,最大
只能准确预测约60%以上的端到端流量流,与SMTP相差22%,这表明SMTP对不同端到端流
量流具有较准确的预测能力。图5(b)表明,SMTP的时间相对误差曲线在其他三种方法上面,
这表明SMTP比其他三种方法能更准确预测不同时间的端到端流量。而且图5(b)也表明,当
,SMTP能对大约99%时刻的端到端流量进行准确预测,而其他三种算
255法仅仅最