基于Dijkstra算法的Q-learning光片上网络自适应路由规划方法转让专利
申请号 : CN202010403396.X
文献号 : CN111770019B
文献日 : 2021-06-15
发明人 : 李慧 , 陈燕怡 , 顾华玺 , 杨银堂 , 王琨
申请人 : 西安电子科技大学
摘要 :
权利要求 :
1.一种基于Dijkstra算法的Q‑learning光片上网络自适应路由规划方法,其特征在于,包括:
S1:构建网络模型,并定义网络模型参数;
S2:根据Dijkstra算法和所述网络模型,构建每个节点到其他节点的最短路径树,同时按照预设值在各节点存储若干条该节点到目标节点vd的最短路径,并获取源节点vs到目标节点vd的最短路径的路由跳数h(vs,vd);
S3:根据Q‑learning算法,采用基于ε‑贪婪策略的链路选择机制进行路径规划,得到所述源节点vs到所述目标节点vd的若干条规划路径,获取所述规划路径的奖励值,所述规划路径的路由跳数不超过所述最短路径的路由跳数h(vs,vd);
S4:根据所述规划路径的奖励值,得到最佳路径;
其中,根据Dijkstra算法和所述网络模型,构建每个节点到其他节点的最短路径树,包括:
步骤a:获取当前网络拓扑信息;
步骤b:初始化已确定最短路径的顶点集合N和权重De(v),N={vs},
其中,h(vs,v)表示源节点vs和节点v之间的路由跳数;
步骤c:选取De(w)=min(De(v)),其中节点v和节点w不属于所述已确定最短路径的顶点集合N,则更新所述已确定最短路径的顶点集合N和所述权重De(v),其中,N={N,w},
步骤d:重复步骤c,直到所有节点都在所述已确定最短路径的顶点集合N中;
根据Q‑learning算法,采用基于ε‑贪婪策略的链路选择机制进行路径规划,得到源节点vs到所述目标节点vd的若干条规划路径,包括:步骤1:初始化Q‑learning学习参数以及Q值,所述Q值为Q(vt,linkt),表示第t时刻节点vt的输出数据链路linkt;
步骤2:根据所述Q值,基于所述ε‑贪婪策略选择下一节点vt+1,并获取选择该节点的奖励函数rt+1;
步骤3:根据选择的节点vt+1,更新所述Q值,判断节点vt+1是否为所述目标节点vd,若是则结束本轮学习,得到一条所述规划路径;
若不是,则令计数变量Count=Count+1,判断计数变量Count是否小于所述最短路径的路由跳数h(vs,vd),若是,则重复步骤2‑步骤3;若不是,则结束本轮学习;
步骤4:根据预设的学习轮次得到若干条所述规划路径。
2.根据权利要求1所述的基于Dijkstra算法的Q‑learning光片上网络自适应路由规划方法,其特征在于,所述网络模型参数包括链路使用次数、排队时延和插入损耗。
3.根据权利要求1所述的基于Dijkstra算法的Q‑learning光片上网络自适应路由规划方法,其特征在于,源节点vs到目标节点vd的最短路径的路由跳数h(vs,vd)=De(vd),vd表示目标节点。
4.根据权利要求1所述的基于Dijkstra算法的Q‑learning光片上网络自适应路由规划方法,其特征在于,所述步骤a包括:根据所述网络模型,获取每个节点的链路连接信息分组,每个节点将其链路连接信息分组发送至其他节点,同时存储其他节点发送的所述链路连接信息分组,组成所述当前网络拓扑信息,其中,所述链路连接信息分组包括:节点的网络地址、相邻节点的网络地址以及节点与相邻节点之间的连接信息。
5.根据权利要求1所述的基于Dijkstra算法的Q‑learning光片上网络自适应路由规划方法,其特征在于,所述Q‑learning学习参数包括:学习轮次q_n、学习步长α、折扣系数γ和ε‑贪婪策略概率。
6.根据权利要求1所述的基于Dijkstra算法的Q‑learning光片上网络自适应路由规划方法,其特征在于,初始化Q值包括:根据存储的所述若干条最短路径,设置所述最短路径中节点对应链路的Q值为正数,其余未在所述最短路径中节点对应链路的Q值为零。
7.根据权利要求1所述的基于Dijkstra算法的Q‑learning光片上网络自适应路由规划方法,其特征在于,所述S4包括:判断若干条所述规划路径的奖励值的大小,最大奖励值对应的所述规划路径为最佳路径。
8.根据权利要求7所述的基于Dijkstra算法的Q‑learning光片上网络自适应路由规划方法,其特征在于,所述规划路径的奖励值为路径规划过程中选择节点对应的奖励函数rt+1的总和。
说明书 :
基于Dijkstra算法的Q‑learning光片上网络自适应路由规划
方法
技术领域
背景技术
能力不断增强,片上通信效率对整体性能至关重要。在整个信息的传送过程中,中间的路由
器需要根据当前的状态来选择下一跳的路由器。然而,从整体和长期来看,全局信息的缺乏
使得所选择的下一跳转发节点往往未必是最佳的,所以人们更关注使用强化学习来解决实
时性、动态性的路由问题。
每个目标点提供一条最短路径,不能提供其他可替代的最短路径,而且它只适用于非负权
重的规划。相比Dijkstra算法,Bellman‑Ford算法支持存在负权重的情况,并且代码实现相
对简单,但是Bellman‑Ford算法的时间复杂度较高,收敛速度低于Dijkstra算法,而且
Bellman‑Ford算法要求大量的信息传递,尤其是在遇到负权重时,需要多次迭代。
发明内容
现:
目标节点vd的最短路径的路由跳数h(vs,vd);
划路径的路由跳数不超过所述最短路径的路由跳数h(vs,vd);
前网络拓扑信息,其中,所述链路连接信息分组包括:节点的网络地址、相邻节点的网络地
址以及节点与相邻节点之间的连接信息。
短路径的路由跳数h(vs,vd),其次使用Dijkstra算法计算的最短路径的路由跳数h(vs,vd)
限制Q‑learning算法设计,采用基于ε‑贪婪策略的链路选择机制,生成规划路径,最后从若
干条规划路径中得到最佳路径。该方法克服了缺乏未知网络环境的先验知识的缺点,基于
强化学习Q‑learning算法,扩大算法的适用范围,也克服了Dijkstra算法每个目标点只能
产生一条最短路径的缺点,使用Q‑learning算法寻找其他替代最短路径,使自动规划路径
更可控。
最佳路径,不必在乎ε‑贪婪策略造成的收敛结果不稳定现象。
更明显易懂,以下特举较佳实施例,并配合附图,详细说明如下。
附图说明
具体实施方式
络自适应路由规划方法进行详细说明。
采取的技术手段及功效进行更加深入且具体地了解,然而所附附图仅是提供参考与说明之
用,并非用来对本发明的技术方案加以限制。
2
它基于马尔科夫链,可以实现自主学习,在t时刻,其总的反馈定义为Gt=rt+1+γrt+2+γrt+3
+.......,并且未来反馈rt+n随着时间间隔n的增加对Gt的影响越来越小。
索,即使过程中不断优化结果,直至最后寻到全局最优解仍然存在多余的探索,结果无法稳
定在最优解;二是时间复杂度较高,收敛速度慢。
提供的一种基于Dijkstra算法的Q‑learning光片上网络自适应路由规划方法的流程图。如
图所示,本发明的方法包括:
Cygnus路由器,每个节点可以使用坐标(x,y)标识。路径定义为有序点集R(v0,vn)={v0,
v1,...,vn}。其中对任意R中的元素vi,i<=n,vi∈V,vi在全局路径上,位于数据流前方。需要
考虑的因素包括最短路径,路径均衡,排队时延,通信路径的插入损耗,使用权重的方法衡
量各个考虑因素对选取数据链路的影响,可以给出规划路径时考虑因素的优先级,设各考
虑因素优先级为:最先考虑最短路径,其次路径均衡,最后排队时延、通信路径的插入损耗
处于同一优先级。网络模型参数包括链路使用次数、排队时延和插入损耗。其中,
vt+1之间的链路使用次数H(vt,vt+1)=min(H(vt,:))。
选择节点vt的下一节点vt+1,节点vt与节点vt+1之间的排队时延D(vt,vt+1)=min(D(vt,:))。
n,C_n,D_n,T_n分别代表通信路径中节点vi的内部传输路径波导转弯,波导交叉,处于ON状
态的微环谐振器,处于OFF状态的微环谐振器的数目。
目标节点vd的最短路径的路由跳数h(vs,vd);
Dijkstra算法和所述网络模型,构建每个节点到其他节点的最短路径树,包括:
所述当前网络拓扑信息。其中,所述链路连接信息分组包括:节点的网络地址、相邻节点的
网络地址以及节点与相邻节点之间的连接信息,节点与相邻节点之间的连接信息也就是两
个节点是否直连。
点vd的最短路径的路由跳数h(vs,vd),其中,h(vs,vd)=De(vd),vd表示目标节点。
果网络拓扑发生变化,增加或改变相应的链路连接信息分组,再发送给其他节点,重新更新
节点存储的网络拓扑信息,使用Dijkstra算法再次规划路径即可。
划路径的路由跳数不超过所述最短路径的路由跳数h(vs,vd);
learning算法,采用基于ε‑贪婪策略的链路选择机制进行路径规划,得到源节点vs到所述
目标节点vd的若干条规划路径,包括:
应链路的Q值为零。
可以得出不同程度的选取意向。链路选择的机制采用基于ε‑贪婪策略,也就是,以1‑ε的概
率基于贪婪策略选取,以ε的概率随机选取,公式如下:
均衡,排队时延以及通信路径的插入损耗。在本实施例中,根据考虑因素,执行当前节点选
择的奖励函数rt+1如下:
径均衡、排队时延、插入损耗和到达目标节点vd的奖励系数。根据优先级,a1>a2=a3。
(vs,vd)限制Q‑learning算法,能够加快收敛速度。根据网络的变化情况,Q‑learning算法通
过网络节点之间的交互,能够实时地调整路由规划。
的总和。
采取该迭代方法可以避免基于ε‑贪婪策略的链路选择机制带来的收敛不稳定问题。
也就是,最大奖励值对应的规划路径为最佳路径,第二大奖励值对应的规划路径为第一最
佳替代路径,第三大奖励值对应的规划路径为第二最佳替代路径,依次类推。
路径,并获得该最短路径的路由跳数h(vs,vd),其次使用Dijkstra算法计算的最短路径的路
由跳数h(vs,vd)限制条件限制Q‑learning算法设计,采用基于ε‑贪婪策略的链路选择机制,
生成规划路径,最后从若干条规划路径中得到最佳路径。该方法克服了缺乏未知网络环境
的先验知识的缺点,基于强化学习Q‑learning算法,扩大算法的适用范围,也克服了
Dijkstra算法每个目标点只能产生一条最短路径的缺点,使用Q‑learning算法寻找其他替
代最短路径,使自动规划路径更可控。相较于单一的Q‑learning算法,寻找最短路径的速度
更快,此外,采用迭代的方法,可以找到最佳路径,不必在乎ε‑贪婪策略造成的收敛结果不
稳定现象。
标识网络路由器的方法,和探测网络中各个路由器内部不同传输路径对应的插入损耗,以
及路由器与其他路由器的连接情况。对于网格、带环网格(torus)、超立方等网络拓扑结构,
建立XY轴或XYZ轴,以坐标作为标识方法;对于环形网络,可以建立球坐标系,以坐标为标
识;对于不规则的网络拓扑,使用不同的数值标识不同的路由器。对于不同类型的路由器,
例如Crossbar、Cygnus、Crux路由器,只需探测网络中各个路由器内部不同传输路径对应的
插入损耗,以及路由器与其他路由器的连接情况。
不脱离本发明构思的前提下,还可以做出若干简单推演或替换,都应当视为属于本发明的
保护范围。