用于容迟网络的路由决策方法

摘要

本发明公开了一种用于容迟网络的路由决策方法，主要解决现有技术未能充分利用网络节点运动规律及链路历史信息进行路由选择的缺陷。其具体过程为：(1)对时变链路容量函数离散化，构造描述网络拓扑变化的三维矩阵；(2)对链路容量进行二值量化，得到每条链路的齐次马尔科夫模型；(3)利用节点运动规律及链路历史信息，估计链路的连通与断开状态到达率；(4)根据得到的链路连通状与断开状态的到达率，计算任意时刻链路连通概率；(5)将容迟网络的路由决策过程定义为阶段有限的马尔科夫决策模型。(6)根据马尔科夫决策理论，定义全局最优方程，并采用后向迭代递归算法计算最优决策序列。本发明能够满足延时较大的容迟网络需求，为其选定最优路由决策序列。

主权项

1.一种用于容迟网络的路由决策方法，包括如下过程：(1)以离散化的链路连通特性描述网络拓扑状况：(1a)在观测时间段内，以给定的采样间隔Δ和平滑步长，将任意网络节点i和j间的时变链路容量函数c_ij(t)离散化，得到离散序列c_ij(t₀+aΔ)；(1b)各节点将采样所得离散序列传遍全网，使各节点整合出一个以离散的形式表征的三维矩阵：A＝{c_ij(t₀+aΔ)_|V|×|V|×K，其中，V、E分别表示所考虑网络内的节点和边，|V|、|E|分别表示节点和边的数目；i，j＝0，1，L，|V|-1；t为网络运行时间，t₀为时间统计起点，a为采样的时间序列，a＝0，1，L K，K为采样序列最大值；(2)根据已得到的三维矩阵A，采用二值量化表示链路容量，每条链路得到如下齐次马尔科夫模型为：$c_{\mathrm{ij}}(t_0+\mathrm{a\Delta })=\left\{\begin{array}{c}0\\ 1\end{array}\right.,$该模型体现了各链路容量为一个在“0”和“1”状态间转移的马尔科夫过程；式中，“0”表示链路连通，“1”表示断开；(3)根据已得到的马尔科夫模型，以网络中各节点运动规律及统计得到的链路历史信息作为参考，利用随机过程参数估计方法，估计出各链路的连通状态与断开状态的到达率μ和λ；(4)根据估计所得的连通与断开状态到达率μ、λ及Kolmogorov方程，得到如下微分方程组为：$\left\{\begin{array}{c}{P^{\prime }}_0\left(t\right)=-\lambda P_0\left(t\right)+\mu P_1\left(t\right)\\ {P^{\prime }}_1\left(t\right)=\lambda P_0\left(t\right)-\mu P_1\left(t\right)\end{array}\right.,$求解以上微分方程组得：$P_0\left(t\right)=\frac{\mu }{\lambda +\mu }+\frac{\lambda }{\lambda +\mu }{e}^{-(\lambda +\mu )t},$$P_1\left(t\right)=\frac{\lambda }{\lambda +\mu }+\frac{\mu }{\lambda +\mu }{e}^{-(\lambda +\mu )t};$上式中，P₀(t)、P₁(t)分别表示在t时刻0状态与1状态的稳态概率，P′₀(t)、P′₁(t)分别表示在t时刻0状态和1状态的转出概率；(5)根据得到的各链路马尔科夫状态模型，将容迟网络的路由决策过程定义为一个阶段有限的离散时间决策的马尔科夫决策模型：{T，S，A(i)，p(j′|i，e_ij)，r(i，e_ij)}，其中：T表示决策时刻，T＝{0，1，L，|V|-1}，|V|-1表示路由跳数的最大允许值，即最多允许跳过除源节点之外的所有其它节点；S表示可能的状态，S＝V，即一个节点表示一个状态；A(i)表示可能的行动集，A(i)＝e_ij，e_ij∈E，i，j表示网络节点，e_ij表示连接网络节点i和节点j的边；P_t(j′|i，e_ij)表示转移概率，该式表示，i节点在t时刻采用行动e_ij到达节点j′的概率，p(e_ij)表示链路e_ij的连通概率，p(e_ij)＝P₀(t)，i，j，j′∈S，e_ij∈E，t∈[0，|V|-1]；r_t(i，e_ij)表示报偿值，该式表示，i节点在t时刻采用行动e_ij所得到的，其中，c_ij(t)是链路e_ij在t时刻的链路容量，i，j∈S，e_ij∈E，t∈T，N为结束时刻，N∈[0，|V|-1]；(6)根据已建立的马尔科夫决策模型以及马尔科夫决策理论，定义全局最优方程如下：该式中，u_t(h_t)为t时刻的最优值；r_t(i，e_ij)为t时刻i状态采用行动e_ij的报偿值；p_t(j|i，e_ij)为t时刻i状态采用行动e_ij转移到j的概率；h_t为t时刻前的轨迹向量，包括之前所经历的状态及所采取的行动；(7)根据马尔科夫决策理论中，有限阶段模型的最优策略求解过程，在已知初始状态和终止状态的情况下，采用后向迭代递归算法计算所述全局优化方程，得到一组连接初始状态和终止状态的最优决策序列。