基于隐马尔科夫的Internet网络时延预测方法

摘要

本发明公开了网络时延预测技术领域中的一种基于隐马尔科夫的Internet网络时延预测方法。包括根据历史时延数据集和设定的时延预测精度，获得可观测状态和可观测状态序列；采用K-Means聚类方法对历史时延数据集进行聚类，计算不同k值下历史时延数据集的误差，根据不同k值下历史时延数据集的误差确定初始值；估计不同k值下的隐马尔科夫参数，并根据不同k值下的隐马尔科夫参数计算不同k值下的隐马尔科夫贝叶斯信息准则值，选择最小的隐马尔科夫贝叶斯信息准则值对应的k值作为最佳隐状态个数k_best；根据可观测状态和最佳隐状态个数k_best，预测未来时延。本发明准确表示时延数据集的规律以及Internet网络的特性，对于未来的可观测状态的预测有较高的准确性。

说明书

技术领域

本发明属于网络时延预测技术领域，尤其涉及一种基于隐马尔科夫的 Internet网络时延预测方法。

背景技术

基于Internet网络的应用中，有些应用对Internet的网络时延并不敏感，但 有很多应用对Internet的网络时延要求较高。对时延要求较高的应用，一般有两 种预测时延的方法：一种是根据时延数据之间的关系，进行拟合，预测未来的 时延；另一种通过构建Internet的网络模型，实现对时延的预测。后一种方法相 对于前一种方法有着更好的预测效果，这是因为后者不但能够包含时延数据之 间的规律，而且能够更好的反映出当前的网络状况以及未来时刻网络的状况和 时延情况。

本文提出基于隐马尔科夫的Internet网络时延预测方法，即采用隐马尔科夫 (HMM，Hidden Markov Model)的方法构建Internet网络模型，预测Internet网络 时延。该方法通过预测未来时刻的可观测状态值，准确表示时延数据集的规律 以及Internet网络的特性；同时，该方法对于未来的可观测状态的预测有较高的 准确性，能够更好地对Internet时延敏感的应用作出决策。

发明内容

本发明的目的在于，提供一种基于隐马尔科夫的Internet网络时延预测方法， 用于解决现有技术在预测Internet网络时延时存在的不足。

为了实现上述目的，本发明提出的技术方案是，一种基于隐马尔科夫的 Internet网络时延预测方法，其特征是所述方法包括：

步骤1：根据历史时延数据集和设定的时延预测精度，获得可观测状态和可 观测状态序列；

步骤2：设定参数K的值，采用K-Means聚类方法对历史时延数据集进行聚 类，计算不同k值下历史时延数据集的误差，根据不同k值下历史时延数据集的 误差确定初始值k_start；

步骤3：估计不同k值下的隐马尔科夫参数，并根据不同k值下的隐马尔科 夫参数计算不同k值下的隐马尔科夫贝叶斯信息准则值，选择最小的隐马尔科夫 贝叶斯信息准则值对应的k值作为最佳隐状态个数k_best；其中，k_start≤k≤K；

步骤4：根据可观测状态和最佳隐状态个数k_best，预测未来时延。

所述步骤1包括如下子步骤：

子步骤101：确定历史时延数据集中的最大时延t_max和最小时延t_min；

子步骤102：根据公式计算可观测状态的数量；其中，N为 可观测状态的数量，I为设定的时延预测精度，[·]为取整运算；

子步骤103：建立N个时延区间I_j=((j-1)I,jI]，其中j为时延区间的序号， j=1,2,...,N；

子步骤104：将历史时延数据集中的每一个时延映射为一个整数；映射规则 为，如果t_i∈I_j，则将t_i映射为时延区间I_j的序号j；其中，i=1,2,...,n，n为历史 时延数据集中的时延个数；

子步骤105：将每一个时延区间的序号作为一个可观测状态，则由历史时延 数据集中的每一个时延映射为一个时延区间的序号后得到的所有时延区间的序 号组成的序列为可观测状态序列。

所述步骤2包括如下子步骤：

子步骤201：根据公式计算不同k值下历史时延数据集的 误差；

其中，e_k是k值下历史时延数据集的误差；

t_i是历史时延数据集中的第i个时延；

c_k是采用K-Means聚类方法对历史时延数据集进行聚类后得到的聚类C_k的 聚类中心，k=2,3,...,K；

n为历史时延数据集中的时延个数；

子步骤202：选择满足|e_k-e_k+1|/e_k<θ的第一个k值作为初始值并记为k_start，θ 为设定值。

所述估计不同k值下的隐马尔科夫参数采用Baum-Welch算法，包括估计不 同k值下的所有隐状态之间的转移概率矩阵A_k×k、任意隐状态到可观测状态之间 的概率矩阵B_k×N和初始隐状态概率向量π_1×k；

其中，矩阵A_k×k中的元素a_ij表示第i个隐状态到第j个隐状态的转移概率；

矩阵B_k×N中的元素b_i(o_l)表示当前隐状态为第i个隐状态，且从第i个隐状态观 测到第l个可观测状态o_l的概率；

向量π_1×k中的元素π_i表示隐马尔科夫初始隐状态为第i个隐状态的概率；

i=1,2,...,k，j=1,2,...,k，l=1,2,...,N，N为可观测状态的数量。

所述根据不同k值下的隐马尔科夫参数计算不同k值下的隐马尔科夫贝叶 斯信息准则值采用公式BIC_k=[-2lnP(O|λ_k)+u_kln(n)]；

其中，BIC_k是k值下的隐马尔科夫贝叶斯信息准则值；

lnP(O|λ_k)是k值下的隐马尔科夫模型的最大似然估计；

O是可观测状态序列；

λ_k是由k值下的隐马尔科夫参数确定的隐马尔科夫模型；

u_k是k值下的隐马尔科夫模型中需要求解的参数个数且u_k=k²+k×N+k；

n是历史时延数据集中的时延个数；

N为可观测状态的数量。

所述步骤4包括如下子步骤：

子步骤401：初始化公式采用Viterbi算法估计当前可观 测状态的最大概率隐状态q_l；

其中，p是当前隐状态；

是当前隐状态到第i个隐状态的转移概率，1≤i≤k_best；

b_i(o_l)是当前隐状态为第i个隐状态，且从第i个隐状态观测到第l个可观测状 态的概率，1≤l≤N；

子步骤402：根据公式计算下一时刻最优隐状态为第i个 隐状态且观测到最大可观测状态的概率；

其中，是第q_l个隐状态到第i个隐状态的转移概率；

b_i(o_l)是当前隐状态为第i个隐状态，且从第i个隐状态观测到第l个可观测状 态的概率，1≤l≤N；

子步骤403：根据公式${\delta }_t\left(j\right)=\underset{1\le i\le k\_\mathrm{best}}{\max }[{\delta }_{t-1}\left(i\right)·a_{\mathrm{ij}}]·\underset{t}{\max }{b}_j\left(o\left(t\right)\right)$计算时刻t的概率 δ_t(j)；

其中，a_i,j是第i个隐状态到第j个隐状态的转移概率；

b_j(o(t))是当前隐状态为第j个隐状态，且从第j个隐状态观测到时刻t的可观 测状态的概率；

o(t)是时刻t的可观测状态；

1≤j≤k_best，2≤t≤T，T为设定值；

子步骤404：计算时刻T的最佳隐状态，并根据时刻T的最佳隐状态计算时 刻T的最佳可观测状态；

时刻T的最佳隐状态的计算公式为

时刻T的最佳可观测状态的计算公式为

子步骤405：时刻T的最佳可观测状态对应的延时区间即为时刻T时延的预 测区间。

本发明采用隐马尔科夫模型预测Internet网络时延，通过预测未来时刻的可 观测状态值，准确表示时延数据集的规律以及Internet网络的特性；同时，本发 明对于未来的可观测状态的预测有较高的准确性，能够更好地对Internet时延敏 感的应用作出决策。

附图说明

图1是基于隐马尔科夫的Internet网络时延预测方法流程图；

图2是实施例2提供的基于隐马尔科夫的Internet网络时延预测方法流程图。

具体实施方式

下面结合附图，对优选实施例作详细说明。应该强调的是，下述说明仅仅 是示例性的，而不是为了限制本发明的范围及其应用。

实施例1

图1是基于隐马尔科夫的Internet网络时延预测方法流程图。下面结合图 1对本发明提供的方法的原理进行说明。如图1所示，本发明提供的基于隐马 尔科夫的Internet网络时延预测方法包括：

步骤1：根据历史时延数据集和设定的时延预测精度，获得可观测状态和可 观测状态序列。

这一过程包括如下子步骤：

子步骤101：确定历史时延数据集中的最大时延t_max和最小时延t_min。

子步骤102：根据公式计算可观测状态的数量；其中，N为 可观测状态的数量，I为设定的时延预测精度，[·]为取整运算。

子步骤103：建立N个时延区间I_j=((j-1)I,jI]，其中j为时延区间的序号， j=1,2,...,N。

子步骤104：将历史时延数据集中的每一个时延映射为一个整数。映射规则 为，如果t_i∈I_j，则将t_i映射为时延区间I_j的序号j；其中，i=1,2,...,n，n为历史 时延数据集中的时延个数。

子步骤105：将每一个时延区间的序号作为一个可观测状态，则由历史时延 数据集中的每一个时延映射为一个时延区间的序号后得到的所有时延区间的序 号组成的序列为可观测状态序列。

步骤2：设定参数K的值，采用K-Means聚类方法对历史时延数据集进行聚 类，计算不同k值下历史时延数据集的误差，根据不同k值下历史时延数据集的 误差确定初始值k_start。通常。参数K的值取50。

步骤2包括如下子步骤：

子步骤201：根据公式计算不同k值下历史时延数据集的 误差。其中，e_k是k值下历史时延数据集的误差，t_i是历史时延数据集中的第i个 时延，c_k是采用K-Means聚类方法对历史时延数据集进行聚类后得到的聚类C_k的聚类中心，k=2,3,...,K，n为历史时延数据集中的时延个数。

子步骤202：选择满足|e_k-e_k+1|/e_k<θ的第一个k值作为初始值并记为k_start，θ 为设定值。通常，θ取值为0.05。

在发明中，需要得到最佳的隐状态个数，而最佳的隐状态个数需要根据不 同取值的隐马尔科夫贝叶斯信息准则值BIC值比较得到。但是，对于每一个隐 马尔科夫贝叶斯信息准则值BIC值，如果其隐状态个数为m个，则需要训练具 有m个隐状态个数的隐马尔科夫模型，其训练时间较长。采用K-Means算法可 以直接从K-Means算法得到的初始值k_start，即从具有k_start个隐状态的隐马尔科夫 模型开始训练计算BIC值，不需要从隐状态个数为1开始计算，这样可以大大 减少运算时间。

步骤3：估计不同k值下的隐马尔科夫参数，并根据不同k值下的隐马尔科 夫参数计算不同k值下的隐马尔科夫贝叶斯信息准则值，选择最小的隐马尔科夫 贝叶斯信息准则值对应的k值作为最佳隐状态个数k_best；其中，k_start≤k≤K。

估计不同k值下的隐马尔科夫参数采用Baum-Welch算法，包括估计不同k 值下的所有隐状态之间的转移概率矩阵A_k×k、任意隐状态到可观测状态之间的概 率矩阵B_k×N和初始隐状态概率向量π_1×k。Baum-Welch算法是现有的经典算法，一 般的数学计算软件（如MATLAB）中都提供该算法。在上述K-Means聚类的基 础上，结合可观测状态，利用MATLAB中的Baum-Welch算法，即可估计不同k 值下的隐马尔科夫参数。

其中，矩阵A_k×k中的元素a_ij表示第i个隐状态到第j个隐状态的转移概率，矩 阵B_k×N中的元素b_i(o_l)表示当前隐状态为第i个隐状态，且从第i个隐状态观测到第 l个可观测状态o_l的概率，向量π_1×k中的元素π_i表示隐马尔科夫初始隐状态为第i 个隐状态的概率，i=1,2,...,k，j=1,2,...,k，l=1,2,...,N，N为可观测状态的数量。

由于隐马尔科夫模型是一个五元组λ=(Ω_π,Ω₀,A,B,π)，λ表示隐马尔科夫模 型，Ω_π是隐马尔科夫隐含状态集，Ω₀是隐马尔科夫可观测状态集，A是所有隐 状态之间的转移概率矩阵，B是任意隐状态到可观测状态之间的概率矩阵，π是 初始隐状态概率向量。因此，在确定了不同k值下的隐马尔科夫参数后，即可确 定不同k值下的隐马尔科夫模型λ_k。

根据不同k值下的隐马尔科夫参数计算不同k值下的隐马尔科夫贝叶斯信 息准则值采用公式BIC_k=[-2lnP(O|λ_k)+u_kln(n)]。其中，BIC_k是k值下的隐马尔科 夫贝叶斯信息准则值，lnP(O|λ_k)是k值下的隐马尔科夫模型的最大似然估计，O 是可观测状态序列，λ_k是由k值下的隐马尔科夫参数确定的隐马尔科夫模型，u_k是k值下的隐马尔科夫模型中需要求解的参数个数且u_k=k²+k×N+k，n是历史 时延数据集中的时延个数，N是可观测状态的数量。

步骤4：根据可观测状态和最佳隐状态个数k_best，预测未来时延。该步骤 包括如下子步骤：

子步骤401：初始化公式采用Viterbi算法估计当前可观 测状态的最大概率隐状态q_l，其中，p是当前可观测状态，a_p,i是第p个隐状态 到第i个隐状态的转移概率，b_i(o_l)是当前隐状态为第i个隐状态，且从第i个隐状 态观测到第l个可观测状态的概率，1≤l≤N。

Viterbi算法是隐马尔科夫模型中经典的算法，由于已经知道当前可观测状 态，因此利用公式和MATLAB计算工具，采用Viterbi算法可 估计当前可观测状态的最大概率隐状态q_l。

子步骤402：根据公式计算下一时刻最优隐状态为第i个 隐状态且观测到最大可观测状态的概率。其中，是第q_l个隐状态到第i个隐状 态的转移概率，b_i(o_l)是当前隐状态为第i个隐状态，且从第i个隐状态观测到第l 个可观测状态的概率，1≤l≤N。

子步骤403：根据公式${\delta }_t\left(j\right)=\underset{1\le i\le k\_\mathrm{best}}{\max }[{\delta }_{t-1}\left(i\right)·a_{\mathrm{ij}}]·\underset{t}{\max }{b}_j\left(o\left(t\right)\right)$计算时刻t的概率 δ_t(j)。其中，a_i,j是第i个隐状态到第j个隐状态的转移概率，b_j(o(t))是当前隐状 态为第j个隐状态，且从第j个隐状态观测到时刻t的可观测状态的概率，o(t)是 时刻t的可观测状态，1≤j≤k_best，2≤t≤T，T为设定值。时刻t的可观测状态 可以根据时刻t的时延所处的子步骤103划分的时延区间确定，当时刻t的可观 测状态处于子步骤103划分的某个时延区间时，该时延区间的序号即为时刻t的 可观测状态。

子步骤404：计算时刻T的最佳隐状态，并根据时刻T的最佳隐状态计算时 刻T的最佳可观测状态。时刻T的最佳隐状态的计算公式为时 刻T的最佳可观测状态的计算公式为

子步骤405：由于为可观测状态，因此该可观测状态对应的延时区间即为 时刻T时延的预测区间。

实施例2

下面以实际的时延数据为例，说明本发明的实施过程。本实施例采用历史 时延数据集为：21.7867，16.8299，27.0571，20.2741，40.5288，……，共有70 万条数据，单位为毫秒。设定的时延预测精度I=10毫秒。

步骤1：根据历史时延数据集和设定的时延预测精度，获得可观测状态和 可观测状态序列。

子步骤101：确定历史时延数据集中的最大时延t_max=491.2745和最小时延 t_min=0.0569。

子步骤102：根据公式$N=\left[\frac{491.2745-0.0569}{10}\right]+1=50$计算可观测状态的数量， 则可观测状态的数量N=50。

子步骤103：建立N个时延区间I₁=(0,I]，I₂=(I,2I]， I₃=(2I,3I]，…I₅₀=(49I,50I]。

子步骤104：对时延数据集中的每一个时延t_i∈I_j进行映射。比如 21.7867∈(20,30]，则根据规则将21.7867映射成整数3，即可观测状态为3，依此 类推。

子步骤105：上述时延数据集被映射为{3,2,3,3,5，…}，该序列即为可观测 状态序列。

步骤2：设定参数K=50，采用K-Means聚类方法对历史时延数据集进行聚 类，计算不同k值下历史时延数据集的误差，k=2,3,...,50。根据不同k值下历史 时延数据集的误差确定初始迭代值k_start。本实施例得到初始迭代值k_start=20。

步骤3：采用Baum-Welch算法估计不同k值下的隐马尔科夫参数，并根据 不同k值下的隐马尔科夫参数计算不同k值下的隐马尔科夫贝叶斯信息准则值， 选择最小的隐马尔科夫贝叶斯信息准则值对应的k值作为最佳隐状态个数 k_best；其中，k_start≤k≤K。

结果表明k=30时BIC值最小，确定最佳隐状态个数k_best=30。其中，计 算隐马尔科夫的参数估计值为：

矩阵A(30×30)中第3隐状态与第4隐状态之间的转移概率为$\left(\begin{array}{cc}0.744& 0.134\\ 0.129& 0.730\end{array}\right),$其 中a₃₃=0.744表示第3隐状态到第3隐状态的转移概率为0.744，其余的描述方法 与此类似；矩阵B(30×50)，第1隐状态和第4隐状态到第4可观测状态和第5可 观测状态之间的概率为$\left(\begin{array}{cc}0.030& 0.145\\ 0.299& 0.191\end{array}\right),$其中b₁(o₄)=0.030表示在第1隐状态下观测 到第4可观测状态的概率为0.030，其余的描述方法与此类似；初始隐状态概率 π(1×30)一般是一均匀概率向量，本实施例

根据N=50个可观测状态和k_best=30个隐状态的隐马尔科夫参数，使用 状态预测算法对未来状态进行预测，预测T时刻后最佳可观测状态预测的具体 过程为：

子步骤401：当前时刻的可观测状态为17，初始化公式 采用Viterbi算法估计当前可观测状态的最大概率隐 状态q_l=10。

子步骤402：根据公式计算下一时刻最优隐状态为第i 个隐状态且观测到最大可观测状态的概率，得到δ₁(1)=0.0362，即下一时刻的最 佳隐状态为第1隐状态，且观测到最大可观测状态概率为0.0362；同法可得， δ₁(2)=0.0325，依此类推。

子步骤403：根据公式${\delta }_t\left(j\right)=\underset{1\le i\le k\_\mathrm{best}}{\max }[{\delta }_{t-1}\left(i\right)·a_{\mathrm{ij}}]·\underset{t}{\max }{b}_j\left(o\left(t\right)\right)$进行迭代计算。

子步骤404：计算时刻T的最佳隐状态，并根据时刻T的最佳隐状态计算时 刻T的最佳可观测状态。

当k=1时，${\hat{Q}}_T=\underset{1\le i\le k\_\mathrm{best}}{\arg \max }\left[{\delta }_T\left(i\right)\right]={\delta }_1\left(17\right)=0.244,$${\hat{O}}_T=\underset{1\le i\le N}{\arg \max }\left[b_{17}\left(i\right)\right]=17,$即当前可 观测状态为17，下一时刻预测值为可观测状态17，下一时刻真实值为可观测状 态17。

本发明提出的一种基于隐马尔科夫的Internet网络模型构建方法能够描述时 延数据的规律以及Internet网络的特性，为对时延敏感的Internet应用提供决策。

以上所述，仅为本发明较佳的具体实施方式，但本发明的保护范围并不局 限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，可轻易 想到的变化或替换，都应涵盖在本发明的保护范围之内。因此，本发明的保护 范围应该以权利要求的保护范围为准。