基于时间聚合图的延迟容忍网络最大流路由方法

摘要

本发明公开了一种基于时间聚合图的延迟容忍网络最大流路由方法，主要解决现有的时间聚合图模型中，由于同一链路不同时段之间缺乏联系而引起不同选路顺序导致求解出不同最大流的问题。其实现步骤为：(1)标记时间聚合图；(2)在时间聚合图中寻找增广路径L；(3)计算增广路径L的最大流,获得剩余路径；(4)累加每条增广路径L的最大流Lf_max(T)，以此作为网络当前的最大流，循环找路,当时间聚合图中不存在增广路径时，得到网络的最大流。本发明增加了链路中不同时段之间的联系，解决了时间聚合图中的最大流问题，可用于互联网、物联网、移动通信、卫星通信和深空通信中提高传输吞吐量。

主权项

一种基于时间聚合图的延迟容忍网络最大流路由方法，包括：(1)标记时间聚合图时间聚合图是由若干节点和多条有向的边所构成的一种图形，每条边标记一个容量时间序列C(T)＝(c₁,...,c_t,...,c_m)，每个节点设置一个存储传递序列N(T)＝(n₁,...,n_t,...,n_m)，其中T是指给定的时间范围，c_t是指与该边相对应的网络链路在第t个时间段内的网络链路总容量，n_t是指该节点从第t‑1个时间段向第t个时间段储存的数据量，1≤t≤m，m是指在给定的时间范围T内以单位时间为间隔分割的时间段；(2)在时间聚合图中寻找增广路径L：(2a)设定时间聚合图所描述的延迟容忍网络的当前最大流为Wf_max(T)，并初始化为0；(2b)将源点s设为增广路径L的当前找路节点并将该节点的找路出发时间t_s设定在第1个时段内即t_s＝1；(2c)利用当前找路节点的存储传递序列对当前节点的找路出发时间进行更新，得到当前节点新的出发时间t_s；(2d)依据当前节点的邻接关系，找到以当前节点为起始节点的所有邻接链路，并在这些邻接链路中找出所有有效的邻接链路:若链路连通的时间段t满足t≥t_s，且链路容量c_t＞0则该链路是有效的邻接链路，否则，该链路是无效的邻接链路；(2e)判断当前节点是否有邻接链路或是否有有效的邻接链路，若有，则执行步骤(2f)，否则，从所有有效的邻接链路中选择具有最早连通时段t'＝min(t)的一条有效邻接链路，将此链路的终止节点作为增广路径L的下一跳节点，并将此链路的终止节点设置为新的当前找路节点，设定当前节点的找路出发时间为t_s＝t'，执行步骤(2g)；(2f)若当前节点为源点s，则不存在增广路径，执行步骤(6)，否则将当前节点的上一跳邻接链路设为无效，在增广路径L中删除该节点，同时把当前节点的上一跳节点设为增广路径L新的当前找路节点，返回步骤(2c)；(2g)若当前节点为终点d，则执行步骤(3)，否则，返回步骤(2c)；(3)计算增广路径L的最大流：(3a)设定增广路径L的当前最大流为Tf_max(T)，并初始化为无穷大，选取增广路径L的最后一跳链路作为当前链路；(3b)根据当前链路终止节点的存储传递序列，计算当前链路的容量时间序列C_u,v(T)与增广路径L的当前最大流Tf_max(T)之间所允许的最大流Pf_max(T)，更新增广路径L的当前最大流Tf_max(T)＝Pf_max(T)；(3c)判断当前链路是否为增广路径L的第一跳链路：若是，则得到增广路径L的最大流Lf_max(T)＝Tf_max(T)，执行步骤(4)，否则，选择此链路的前一跳链路作为当前链路，返回步骤(3b)；(4)获得剩余路径：(4a)设定增广路径L的暂时最大流为Zf_max(T)＝Lf_max(T)，选取增广路径L的第一跳链路作为当前链路；(4b)根据当前链路起始节点的存储传递序列，计算增广路径L的暂时最大流Zf_max(T)与当前链路的容量时间序列C_u,v(T)之间所允许的可行流f_u,v(T)；(4c)更新增广路径L的暂时最大流Zf_max(T)＝f_u,v(T)，依据可行流f_u,v(T)计算当前链路(u,v)以及与当前链路反方向的链路(v,u)的剩余链路容量时间序列；(4d)判断当前链路是否为增广路径L的最后一跳链路：若是，则执行步骤(5)，否则，选择此链路的后一跳链路作为当前链路，返回步骤(4b)；(5)将每次计算出的增广路径L最大流Lf_max(T)进行累加，累加的结果作为网络当前的最大流Wf_max(T)，返回步骤(2b)；(6)结束循环，输出网络的最大流f_max(T)＝Wf_max(T)。