留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于强化学习的光传送网路由波长优化

孔英会 杨佳治 高会生 胡正伟

孔英会, 杨佳治, 高会生, 胡正伟. 基于强化学习的光传送网路由波长优化[J]. 红外与激光工程, 2022, 51(11): 20220084. doi: 10.3788/IRLA20220084
引用本文: 孔英会, 杨佳治, 高会生, 胡正伟. 基于强化学习的光传送网路由波长优化[J]. 红外与激光工程, 2022, 51(11): 20220084. doi: 10.3788/IRLA20220084
Kong Yinghui, Yang Jiazhi, Gao Huisheng, Hu Zhengwei. Optimization of routing and wavelength optimization algorithm for optical transport network based on reinforcement learning[J]. Infrared and Laser Engineering, 2022, 51(11): 20220084. doi: 10.3788/IRLA20220084
Citation: Kong Yinghui, Yang Jiazhi, Gao Huisheng, Hu Zhengwei. Optimization of routing and wavelength optimization algorithm for optical transport network based on reinforcement learning[J]. Infrared and Laser Engineering, 2022, 51(11): 20220084. doi: 10.3788/IRLA20220084

基于强化学习的光传送网路由波长优化

doi: 10.3788/IRLA20220084
基金项目: 国家自然科学基金 (52177083);河北省省级科技计划(SZX2020034);国网山西省电力公司科学技术项目(SGSXXT00JFJS2100106)
详细信息
    作者简介:

    孔英会,女,教授,博士,主要从事机器学习、通信系统与通信网技术方面的教学和研究工作

    通讯作者: 杨佳治,男,硕士生,主要从事光网络方面的研究。
  • 中图分类号: TN929.1

Optimization of routing and wavelength optimization algorithm for optical transport network based on reinforcement learning

  • 摘要: 针对光传送网中动态业务的路由和波长问题,提出一种基于强化学习的深度路由波长分配算法DeepRWA。算法基于软件定义网络架构,通过强化学习灵活地调整控制光传送网,实现光网络路由波长分配策略优化。针对路由选择问题,结合链路上的波长使用情况,使用A3C算法选择合适的路由,使得阻塞率最小;针对波长分配问题,使用首次命中算法选择波长。考虑阻塞率、资源利用率、策略熵、价值损失、运行时间及收敛速度等多个指标,利用14节点NSFNET网络拓扑仿真实验。结果表明:当信道中包含18个波长时,与传统KSP-FF算法相比,所提出的路由波长分配算法的阻塞率降低了0.06,资源利用率提高了0.02,但运行时间有增加;在波长数超过45以后,与传统KSP-FF算法相比,所提算法保持阻塞率和资源利用率的同时,运行时间开始降低;当信道中包含波长数为58时,与传统KSP-FF算法相比,所提算法运行时间减少了0.07 ms。由此可见,提出的算法使路由选择和波长分配得到了优化。
  • 图  1  光传送网模型

    Figure  1.  Optical transport network model

    图  2  DeepRWA结构图

    Figure  2.  Structure of DeepRWA

    图  3  状态示意图

    Figure  3.  Example of state

    图  4  14节点¬NSFNET拓扑

    Figure  4.  14-node ¬NSFNET topology

    图  5  阻塞率变化曲线

    Figure  5.  Curve of blocking rate

    图  6  资源占用率曲线

    Figure  6.  Curve of resource occupancy

    图  7  资源利用率随信道波长变化关系

    Figure  7.  Curve of resource utilization rate vs. channel wavelength

    图  8  策略熵变化曲线图

    Figure  8.  Curve of policy entropy

    图  9  价值损失曲线

    Figure  9.  Curve of value Loss

    图  10  算法的运行时间及收敛速度

    Figure  10.  Algorithm’s execution time and converage speed

    表  1  仿真实验业务参数

    Table  1.   Serve parameters of simulation experiment

    ParametersValue
    Average arrival time of dynamic service/s1/12
    Continuing times of dynamic service/s13
    Available wavelength of channel18
    下载: 导出CSV
  • [1] Nath P K, Venkatesh T. Lightpath routing and wavelength assignment for static demand in translucent optical networks [J]. Photonic Network Communications, 2020, 39(7): 103-119.
    [2] Yang Xiuqing, Chen Haiyan. Application of optical communication technique in the internet of things [J]. Chinese Optics, 2014, 7(6): 889-896. (in Chinese)
    [3] Li Haitao. Technical approach analysis and development prospects of optical communication technology in China deep space TT&C network [J]. Infrared and Laser Engineering, 2020, 49(5): 20201003. (in Chinese) doi:  10.3788/IRLA20201003
    [4] Yang Junbo, Yang Jiankun, Li Xiujian, et al. Choice and control of routes in crossover optical interconnection network [J]. Optics and Precision Engineering, 2010, 18(6): 1249-1257. (in Chinese)
    [5] Sun Zhaowei, Liu Xuekui, Wu Xiande, et al. Path planning based on ant colony and genetic fusion algorithm for communication supporting spacecraft [J]. Optics and Precision Engineering, 2013, 21(12): 3308-3316. (in Chinese) doi:  10.3788/OPE.20132112.3308
    [6] Guo Xiuzhen, Hou Lixin, Yin Zhaotai, et al. All-optical routing control based on coherently induced high reflection band and high transmission band in a medium of cold atoms [J]. Chinese Optics, 2011, 4(4): 355-362. (in Chinese)
    [7] Zhang Min, Xu Bo, Cai Yi, et al. Routing and wavelength assignment based on genetic algorithm in large scale WDM network [J]. Optical Communication Technology, 2018, 42(11): 1-4. (in Chinese)
    [8] Wang Weilong, Li Yongjun, Zhao Shanghong, et al. Routing and wavelength assignment based on load balance for optical satellite network [J]. Laser & Optoelectronics Progress, 2021, 58(7): 0706004. (in Chinese)
    [9] Shi Xiaodong, Li Yongjun, Zhao Shanghong, et al. Ant colony optimization routing and wavelength technology for software-defined satellite optical networks [J]. Infrared and Laser Engineering, 2021, 51(7): 20200125. (in Chinese) doi:  10.3788/IRLA20200125
    [10] Martín I, Troia S, Hernández J A, et al. Machine learning based routing -and wavelength assignment in software-defined optical networks [J]. IEEE Transactions on Network and Service Management, 2019, 16(3): 871-883. doi:  10.1109/TNSM.2019.2927867
    [11] Mnih V, Kavukcuoglu K, Silver D, et al. Human level control through deep reinforcement learning. [J]. Nature, 2015, 518(7540): 529-533. doi:  10.1038/nature14236
    [12] Li Zhongtao. Wireless communication node coverage optimization based double deep Q-learning [J]. Electronic Technology & Software Engineering, 2021(14): 1-3. (in Chinese)
    [13] Rao Ning, Xu Hua, Qi Zisen, et al. Communication interference resource allocation method of deep reinforcement learning based on maximum policy entropy [J]. Journal of Northwestern Polytechnical University, 2021, 39(5): 1077-1086. (in Chinese) doi:  10.1051/jnwpu/20213951077
    [14] Zhao Zipiao, Zhao Yongli, Ma Haoli, et al. Cost-efficient routing, modulation, wavelength and port assignment using reinforcement learning in optical transport networks [J]. Optical Fiber Technology, 2021, 64: 102571.
    [15] Li Xin, Zhao Yongli, Li Yajie, et al. Multi-objective routing and resource allocation based on reinforcement learning in optical transport networks[C]//2020 Asia Communications and Photonics Conference (ACP) and International Conference on Information Photonics and Optical Communications (IPOC), 2020: 1-3.
    [16] Chen Xiaoliang, Li Baojia, Proietti Roberto, et al. DeepRMSA: A deep reinforcement learning framework for routing, modulation and spectrum assignment in elastic optical networks [J]. Journal of Lightwave Technology, 2019, 37(16): 4155-4163. doi:  10.1109/JLT.2019.2923615
  • [1] 辛文辉, 毕元硕, 李仕春, 李耀飞, 华灯鑫.  甲醛气体探测的DIAL波长选择及探测性能 . 红外与激光工程, 2022, 51(9): 20210925-1-20210925-9. doi: 10.3788/IRLA20210925
    [2] 孙红胜, 梁新刚, 马维刚, 邱超, 杨旺林.  无扫描宽范围多波长成像测温技术 . 红外与激光工程, 2021, 50(5): 20200394-1-20200394-7. doi: 10.3788/IRLA20200394
    [3] 杨双月, 谷一英, 胡晶晶, 李晓洲, 赵明山, 韩秀友, 武震林.  基于亚波长超窄带滤波器设计 . 红外与激光工程, 2020, 49(S1): 20200134-20200134. doi: 10.3788/IRLA20200134
    [4] 邓华荣, 龙明亮, 张海峰, 吴志波, 汤凯, 张忠萍.  1 064 nm波长白天卫星激光测距试验 . 红外与激光工程, 2020, 49(10): 20200021-1-20200021-6. doi: 10.3788/IRLA20200021
    [5] 陈明, 赵连飞, 苑立民, 徐峰, 韩默.  基于特征选择YOLOv3网络的红外图像绝缘子检测方法 . 红外与激光工程, 2020, 49(S2): 20200401-20200401. doi: 10.3788/IRLA20200401
    [6] 石晓东, 李勇军, 赵尚弘, 王蔚龙.  软件定义卫星光网络蚁群优化波长路由技术 . 红外与激光工程, 2020, 49(10): 20200125-1-20200125-8. doi: 10.3788/IRLA20200125
    [7] 李斌, 吴建, 谢锋云.  双波长共相检测方法研究 . 红外与激光工程, 2019, 48(8): 813004-0813004(7). doi: 10.3788/IRLA201948.0813004
    [8] 张福才, 孙博君, 孙晓刚.  单目标极小值优化法的多波长真温反演研究 . 红外与激光工程, 2019, 48(2): 226002-0226002(6). doi: 10.3788/IRLA201948.0226002
    [9] 丁煜, 陈磊, 王志华, 朱文华, 刘致远.  电调谐波长移相干涉术 . 红外与激光工程, 2018, 47(5): 506003-0506003(7). doi: 10.3788/IRLA201847.0506003
    [10] 范灏然, 于永吉, 朱贺, 邢爽, 王宇恒, 金光勇.  500 kHz波长锁定878.6 nm LD双端泵浦Nd:YVO4声光调Q激光器 . 红外与激光工程, 2018, 47(6): 606001-0606001(7). doi: 10.3788/IRLA201847.0606001
    [11] 余光其, 王鹏, 宋伟, 刘奎永.  光纤激光泵浦的多波长中红外光参量振荡器 . 红外与激光工程, 2018, 47(4): 404003-0404003(7). doi: 10.3788/IRLA201847.0404003
    [12] 徐玲, 卜令兵, 蔡镐泽, 萨日娜, 杨彬, 周军.  中红外差分吸收激光雷达NO2测量波长选择及探测能力模拟 . 红外与激光工程, 2018, 47(10): 1030002-1030002(8). doi: 10.3788/IRLA201847.1030002
    [13] 杨洋, 刘兵, 赵勇, 王辉, 赵亚丽, 杜瑶.  DWDM技术在新型波长解调方法中的应用 . 红外与激光工程, 2016, 45(8): 822007-0822007(7). doi: 10.3788/IRLA201645.0822007
    [14] 刘旭, 魏靖松, 谭朝勇, 朱孟真, 程勇.  激光器免温控泵浦源的多波长选择理论 . 红外与激光工程, 2016, 45(5): 505004-0505004(5). doi: 10.3788/IRLA201645.0505004
    [15] 朱长军, 张国青, 翟学军, 薛兵.  基于六波混频的双波长红外光信号研究 . 红外与激光工程, 2015, 44(5): 1462-1466.
    [16] 丛日进, 汪井源, 徐智勇, 王荣, 王喆.  长波长红外光大气信道传输 . 红外与激光工程, 2014, 43(3): 927-932.
    [17] 冷雁冰, 董连和, 孙艳军.  1×11亚波长结构Dammann光栅的研制 . 红外与激光工程, 2014, 43(3): 812-817.
    [18] 谢杨易, 刘继桥, 姜佳欣, 陈卫标.  使CO2浓度测量误差减小的星载激光雷达波长优化 . 红外与激光工程, 2014, 43(1): 88-93.
    [19] 李晨龙, 冯丽爽, 周震, 隋佳伟, 殷博昊.  基于亚波长金属孔阵列的光控太赫兹强度调制器 . 红外与激光工程, 2014, 43(12): 4013-4016.
    [20] 刘群.  偏振无关的电光多波长滤波器设计 . 红外与激光工程, 2013, 42(3): 723-726.
  • 加载中
图(10) / 表(1)
计量
  • 文章访问数:  153
  • HTML全文浏览量:  37
  • PDF下载量:  43
  • 被引次数: 0
出版历程
  • 收稿日期:  2022-02-07
  • 修回日期:  2022-07-23
  • 刊出日期:  2022-11-30

基于强化学习的光传送网路由波长优化

doi: 10.3788/IRLA20220084
    作者简介:

    孔英会,女,教授,博士,主要从事机器学习、通信系统与通信网技术方面的教学和研究工作

    通讯作者: 杨佳治,男,硕士生,主要从事光网络方面的研究。
基金项目:  国家自然科学基金 (52177083);河北省省级科技计划(SZX2020034);国网山西省电力公司科学技术项目(SGSXXT00JFJS2100106)
  • 中图分类号: TN929.1

摘要: 针对光传送网中动态业务的路由和波长问题,提出一种基于强化学习的深度路由波长分配算法DeepRWA。算法基于软件定义网络架构,通过强化学习灵活地调整控制光传送网,实现光网络路由波长分配策略优化。针对路由选择问题,结合链路上的波长使用情况,使用A3C算法选择合适的路由,使得阻塞率最小;针对波长分配问题,使用首次命中算法选择波长。考虑阻塞率、资源利用率、策略熵、价值损失、运行时间及收敛速度等多个指标,利用14节点NSFNET网络拓扑仿真实验。结果表明:当信道中包含18个波长时,与传统KSP-FF算法相比,所提出的路由波长分配算法的阻塞率降低了0.06,资源利用率提高了0.02,但运行时间有增加;在波长数超过45以后,与传统KSP-FF算法相比,所提算法保持阻塞率和资源利用率的同时,运行时间开始降低;当信道中包含波长数为58时,与传统KSP-FF算法相比,所提算法运行时间减少了0.07 ms。由此可见,提出的算法使路由选择和波长分配得到了优化。

English Abstract

    • 网络业务的激增对骨干网传输带宽提出了更高的要求。如何在有限资源网络中为业务选择合适的路由和分配优化的波长对于提升网络资源的利用效果、优化管理和灵活控制都有较大的影响。所以路由与波长分配(Routing and Wavelength Assignment,RWA)成为光传送网中的核心问题之一[1-3]

      RWA问题一般被分为路由问题和波长两个方面,首先选取合适的路由作为链路,然后为链路分配波长[4-6]。常用的路由算法有最短路径算法(Shortest Pathes,SP)、K条最短路径算法(K Shortest Pathes,KSP);其中SP根据源节点-目的节点计算最短路径,当业务请求到来选择最短路径路由。这种方法计算复杂度低,但会导致网络阻塞率高。KSP是在SP的基础上,在源节点-目的节点计算K条路径并且按照距离排序。当业务到达时,可按照优先级顺序选择可用路由。常用波长分配算法有随机分配 (Random Assignment, RA)、首次命中 (First Fit, FF)等。其中RA是在可用波长的集合随机选择一个波长传输资源,该算法实现简单,被使用波长的随机性较大。而FF按照优先级搜索可用波长,使用首次找到可用的波长传输信息。FF计算开销较小、阻塞率较低。参考文献[7]对解决RWA问题波长分配的常用方法做了对比实验,仿真表明波长分配算法对RWA问题的解决影响较小,因此FF是光网络中目前应用较多的典型算法。

      由于目前的云计算、数据互联等新业务呈现动态特性,上述路由方法由于缺乏灵活性不再适用,需要根据业务特性快速按需部署网络资源,并借助智能算法为光网络的路由选择提供灵活的优化管理与控制方案,软件定义网络(Software Defined Network,SDN)与深度强化学习的思想可以为上述方案实施提供支持。

      近几年,基于机器学习的光网络路由和波长智能分配算法引起了学者的广泛关注。参考文献[7]提出一种遗传算法解决光网络中RWA问题,较传统算法具有更低的的网络阻塞率。参考文献[8]提出一种蚁群RWA算法,实现了卫星光网络的负载均衡,但是所提出的蚁群算法易陷入局部最优,收敛速度较慢。参考文献[9]考虑卫星光网络传输延迟和波长连续性限制,提出改进蚁群算法的RWA方法,降低了计算复杂度,但是也增加了阻塞率。参考文献[10]使用监督学习的机器学习方法解决RWA问题,将RWA问题映射为分类问题,该算法大大减少了生成RWA策略的计算时间,但训练数据集难以得到。

      自2015年开始,深度强化学习已用于解决通信网络的优化问题[11]。参考文献[12]中,作者针对空中移动无线通信节点与水面通信节点信息交互的应用场景,提出基于深度强化学习的方法引导空中无线通信节点移动路径,实现最小代价水面通信节点覆盖。参考文献[13]中,作者针对通信组网对抗中干扰资源分配的优化问题,提出了一种基于最大策略熵深度强化学习的干扰资源分配方法。参考文献[14]中,作者提出一种基于深度强化学习算法用于解决光传送网中路由、调制、波长和端口分配问题,目的是降低成本。但是该算法处理复杂的拓扑时,由于可用的路由路径较多,将导致模型训练时间较长。在参考文献[15]中,作者提出一种基于深度强化学习的路由和资源分配算法,该算法可以选择跳数最小的路径和数量最少的波长转换器,降低光网络运维成本,简单实验拓扑验证算法可以达到预期目标,但实验所需的网络拓扑及评价指标需要进一步扩展。在参考文献[16]中,作者针对弹性光网络提出一种基于深度强化学习的路由-模式-频谱分配算法,根据业务需求动态分配带宽,进而提高频谱利用率,有效降低弹性光网络中业务请求的阻塞概率,对光传送网中RWA问题的解决有一定借鉴意义。

      针对光网络中的路由选择和波长分配问题,借鉴弹性光网络中频谱优化的思想,提出一种深度路由波长分配算法(Deep Routing and Wavelength Assignment, DeepRWA),该算法采用SDN框架灵活控制光传送网络的路由选择和波长分配,基于深度强化学习策略实现RWA的智能化处理。深度强化学习使用异步优势行动-评论算法(Asynchronous Advantage Actor-Critic, A3C)算法并考虑波长使用情况选择路由;在此基础上使用FF实现波长分配,使路由阻塞率最小,提升资源利用率。

    • 光传送网由光分叉复用器(Optical Add/Drop Multiplexers,OADM)和链路构成。光传送网连接模型可使用图结构G(V, E, F)表示,如图1所示,其中VE表示拓扑的节点(主要是光分插复用器OADM)和链路,F={Fe, f | e, f}表示某条光纤链路e中的波长f使用情况。空闲波长分布情况用$f=\left\{z_{\,\,\,\,\,\,\, k}^{1, j}, z_{\,\,\,\,\,\,\, k}^{2, j}\right\}$表示,$z_{\,\,\,\,\,\,\, k}^{1, j}$表示第k条路由第j段波长可用波长的数量;$z_{\,\,\,\,\,\,\, k}^{2, j}$表示第k条路由第j段波长第一个可用波长的索引。当光网络处于工作状态时,业务由主机发出,服务器对服务做出响应。把一个从源节点到目的节点的光路请求设为Rt(o, d, τ), 其中od表示光路请求的源节点和目的节点,τ表示光路业务请求的持续时间。

      图  1  光传送网模型

      Figure 1.  Optical transport network model

      RWA包含路由选择和波长分配两个子问题,路由选择是在业务的源节点、目的节点之间选择一条合适的物理路径进行数据传输,以最小化阻塞率为目标;波长分配就是路由选择结果确定之后为业务请求分配波长,主要以提高波长利用率为目标,即提高已用波长数在总波长数的比例。在波长分配阶段,需要遵循两个原则:(1)波长一致性限制, 连接源-目的节点的光通道必须分配相同的波长。(2)不同波长限制,所有使用同一条光纤链路的光通道都必须分配不同的波长。

      根据应用场景的不同,RWA工作方式主要分为两种:静态RWA与动态RWA。静态RWA主要解决固定的业务请求下如何最小化网络成本和网络资源使用(例如所需波长数最少)的问题,即提高资源利用率。动态RWA主要解决在业务请求随机到达的情况下如何最小化业务的阻塞率,并提高网络资源利用率的问题。目前光传送网中动态业务较多,文中针对动态RWA问题进行研究。假设光网络拓扑的节点不具备把光信号的波长转换为一个不同的波长,即波长转换功能,因此光路请求需要服从波长一致性限制。

    • 文中提出的基于强化学习的深度路由波长分配算法DeepRWA总体结构如图2所示,算法采用SDN架构,由光网络模块、 控制器、强化学习模块三部分组成。SDN本地控制器作为核心,首先根据数据平面获得网络状态和光路请求,利用深度强化学习算法生成RWA策略然后下发至数据平面。光网络模块主要由光分叉复用器作为节点,节点间相互连接形成拓扑;SDN控制器是光网络模块和强化学习模块的桥梁,可以感知光网络信息、波长使用情况、业务请求信息,为光网络提供高效的路由与波长分配策略;强化学习模块利用控制器收集的信息进行训练,把生成包括路由路径和选用波长的动作发送至控制器模块。DeepRWA工作过程是通过SDN智能控制光传送网的数据平面, DeepRWA具体实现步骤如下:

      图  2  DeepRWA结构图

      Figure 2.  Structure of DeepRWA

      (1) SDN本地代理首先收到主机发出的光路请求Rt

      (2) SDN控制器获得网络拓扑信息和光路请求信息,调用特征处理模型产生DeepRWA的状态信息,其中包括可选路由和每条路由的波长使用信息;

      (3) DeepRWA强化学习模块通过神经网络读取状态st ,利用A3C算法迭代训练,将神经网络的输出作为RWA策略发送至SDN控制器;

      (4)控制器将RWA策略下发至本地代理,由本地代理执行相应的路由和波长分配策略,即DeepRWA的动作;

      (5)奖励系统将获得以往的历史奖励作为反馈和生成DeepRWA的即时奖励rt

      (6)存储即时奖励、动作和状态三个元素数据至经验池;

      (7)利用经验池的数据训练策略神经网络和价值神经网络,更新神经网络的参数,利用策略神经网络获取RWA策略。RWA策略是选择策略神经网络中概率最大的动作。

    • 文中提出DeepRWA的核心是基于强化学习的路由波长优化算法,而强化学习关键是设计状态、动作和奖励,文中具体设计如下:

      (1)状态:针对拓扑中的单业务请求,使用特定的矩阵表示状态st信息和候选路径的波长使用情况,文中状态设定如图3所示,其中图3(a)为光网络拓扑;图3(b)为光网络链路的波长使用示意图,定义状态为1×(2 |V|+1+2JK)大小的矩阵,如公式(1)所示:

      图  3  状态示意图

      Figure 3.  Example of state

      $$ s_{t}=\left\{o, d, \tau,\left\{z^{1, j}_{\,\,\,\,\,\,\, k}, z_{\,\,\,\,\,\,\,k}^{2, j}\right\}\right\} $$

      式中:odτ表示业务请求的源节点、目的节点和服务时长;k∈[1, 2, ··· , K],j∈[1, 2, ··· , J],K为业务请求的所有候选路由数(如图3(a)虚线部分),J表示某条路由所有可用波长段(单个可用波长段至少包含一个可用波长且波长段内的所有波长位置连续,如图3(b)中白色部分),V表示拓扑的节点数。候选路由数目的不同会导致状态的不同,因此需采用一个固定的候选路由数目。强化学习可以通过探索多条候选路由获得更大的收益,然而收敛时间也会更长。候选路由数太少,强化学习的收益较小;候选路由数太多,算法收敛速度慢,文中参考文献[15]的设置,即K=5。$\left\{z_{\,\,\,\,\,\,\, k}^{1, j}, z_{\,\,\,\,\,\,\, k}^{2, j}\right\}$表示业务请求某条候选路由的未占用波长分布情况,$z^{1, j}_{\,\,\,\,\,\,\, k},$表示第k条路由第j段波长可用波长的数量,$z^{2, j}_{\,\,\,\,\,\,\, k},$表示第k条路由第j段波长第一个可用波长的索引。具体实例见图3(a)中,假设业务有两条路由可选,1-2-4为路由1 (k=1),1-3-5-4为路由2 (k=2)。图3(b)中两条路由1、2的波长使用情形分上下两部分,上方路由1的第1段波长可用波长数量$z_{\,\,\,\,1}^{1,1}= 3$,路由1的第1段波长可用波长集合的起始索引$z_{\,\,\,\,1}^{2,1}=0 $;路由1的第2段波长可用波长数量$z_{\,\,\,\,1}^{1,2} =3$,路由1的第2段波长可用波长集合的起始索引$z_{\,\,\,\,1}^{2,2}=9 $;下方路由2第1段波长的可用波长数量$z_{\,\,\,\,2}^{1,1}=4$,路由2第1段波长的可用波长集合的起始索引$z_{\,\,\,\,2 }^{2,1}=2$;路由2第2段波长的可用波长数量$z_{\,\,\,\,2}^{1,2}=4$,路由2第2段波长的可用波长集合的起始索引$z_{\,\,\,\,2}^{2,2}=8 $。因此图3的状态表示为:$S_{t}= \left\{o, d, \tau , z_{\,\,\,\,1}^{1,1} \sim z_{\,\,\,\,1}^{2,2}, \quad z_{\,\,\,\,2}^{1,1} \sim z_{\,\,\,\,2}^{2,2}\right\}$

      (2)动作:动作空间需要对光网络中业务的路由和波长进行部署,每一个动作就是代表一种路由与波长分配方案。对于一个业务请求,DeepRWA算法从光网路拓扑的K条候选路径选择一个路由路径,根据状态计算可选波长数I,从I个可选波长选择一个可用波长传输数据,因此动作空间包含K*I个动作。

      (3)奖励:奖励的设定对算法的收敛速度和动作决策都有很大影响。由于动态RWA问题的优化目标是最小化阻塞率,所以用业务的成功率衡量该动作的价值。即时奖励作为一个标记,记录当前业务请求是否成功。DeepRWA算法如果成功地使一个业务通过光网络传输,即路由与波长分配成功,此时即时奖励rt=1,否则rt=−1。即时奖励为1时,表明代理在状态S下执行动作a策略会更好,有助于策略的收敛;即时奖励为−1时,表明代理在状态S下执行动作a策略比较差,不利于策略的收敛。DeepRWA中神经网络不断迭代使累积收益Γ最大化,累积收益如公式(2)所示:

      $$ {\varGamma _t} = {\displaystyle \sum\limits_{t' \in [t,\infty ]} \gamma ^{t' - t}} \cdot {r_{t'}} $$ (2)

      式中:γ∈[0,1]是未来收益的折扣因子;t'表示未来某个时刻;t表示当前时刻。

    • 文中从阻塞率、资源利用率、策略熵、价值损失和运行时间及收敛速度五个方面评价DeepRWA算法的性能。并与现有的算法KSP-FF对比,验证所提出算法的有效性,借鉴参考文献[16]的参数设置,KSP-FF算法的备选路径设为5条,即K=5,下面实验中KSP-FF参数均采用上述设置。

    • 仿真实验采用如图4所示的14节点NSFNET拓扑,链路间的数字代表节点间的距离(单位:km)。实验采用动态的业务模型,业务服从泊松分布,服务时间遵循指数分布,具体参数如表1所示,软件配置操作系统选用Ubuntu16.04,GPU为NVIDIAGeforce1080 Ti,CPU为i7-6700 k,程序设计采用python3.7,tensorflow版本为1.14.0。

      图  4  14节点¬NSFNET拓扑

      Figure 4.  14-node ¬NSFNET topology

      表 1  仿真实验业务参数

      Table 1.  Serve parameters of simulation experiment

      ParametersValue
      Average arrival time of dynamic service/s1/12
      Continuing times of dynamic service/s13
      Available wavelength of channel18
    • (1)阻塞率

      动态RWA问题的目标是最小化阻塞率,对比了DeepRWA算法和KSP-FF算法阻塞率指标随业务数变化情况。图5给出了上述两种算法随着业务数增加的变化曲线。从图5可以看出,业务请求数较小时DeepRWA阻塞率较大,为0.16左右。这是因为业务请求数较少时,DeepRWA训练次数较少,没有学习到理想的路由与波长分配策略。当业务请求数达到370000个后,经训练的DeepRWA路由和波长分配方案的阻塞率降到0.01,比KSP-FF算法的阻塞概率近似低0.06。原因是KSP-FF寻找路由只考虑最短路径,遇到无可用波长的链路就会发生阻塞;而DeepRWA在选路过程中考虑路径的跳数及波长占用情况,综合考虑选择一条路径,尽可能避开了拥塞链路。因此,DeepRWA较KSP-FF算法具有更低的(业务)阻塞率。

      图  5  阻塞率变化曲线

      Figure 5.  Curve of blocking rate

      (2)资源利用率

      资源利用率表示被业务利用的资源占总资源的比例,资源利用率越大,代表网络中被充分利用,算法性能会更好。图6比较了DeepRWA算法和KSP-FF算法资源利用率随业务数变化的性能曲线。从图6可以看出,DeepRWA算法资源利用率在训练过程中逐步提高最后趋于稳定。起初资源利用率较低且波动较大,因为随着业务请求数增多,要想服务这些业务,就要不断地分配波长,网络的资源利用率必然呈上升趋势。在训练过程中,业务数较小时资源利用率为0.51,当业务数达到150000后,DeepRWA资源利用率上升至0.59,表1中设定的18个波长平均有10.6个波长被利用;而在KSP-FF算法下,设定的18个波长中平均有10.1个波长被利用。可见DeepRWA的路由和波长策略使光网络中资源利用率超过了KSP-FF算法。图7表示实验环境的其它参数不变,资源利用率随着信道波长数变化关系曲线图。随着信道波长数增加,资源利用率逐渐降低。由于业务强度一定,当信道波长数增加时,链路间空闲信道明显增加。根据资源利用率的定义,它会逐渐降低,使网络拥塞问题有所改善。

      图  6  资源占用率曲线

      Figure 6.  Curve of resource occupancy

      图  7  资源利用率随信道波长变化关系

      Figure 7.  Curve of resource utilization rate vs. channel wavelength

      (3)策略熵

      图8描绘了DeepRWA算法随着业务强度增加策略熵的变化曲线,熵值的变化可以反映所提出的算法是否进行了有效的学习。熵值越大说明算法得到的路由和波长策略不确定性越强;策略熵收敛表明算法的随机性降到最低,模型已经训练完成。当业务强度较小时,熵值较大,生成的路由与波长决策随机性较大;随着业务请求数量的增加,当该算法通过3000000个业务请求后,策略熵收敛,熵值从1.5下降至0.15,说明DeepRWA已经学习到一些规则并可以做出随机性相对较小的路由与波长决策。

      图  8  策略熵变化曲线图

      Figure 8.  Curve of policy entropy

      (4)价值损失

      价值损失函数用于计算价值神经网络预估值和真实值的差距,从而指导下一步的训练向正确的方向进行。价值损失描述的是累积收益与价值函数预测值的接近程度,用于评价算法的优劣。图9描述了价值损失随着训练过程的变化曲线,训练过程中价值损失逐渐降低,训练逐渐稳定。当业务数较少时,选择的路由与波长策略的预测值与累积收益差距较大。随着业务数的增加,训练后算法的预测值逐渐接近于累积收益,当通过450000个业务请求后训练算法的价值损失减少至2.5左右,预测值和累积收益比较接近,表明采取的路由与波长策略比较合适。

      图  9  价值损失曲线

      Figure 9.  Curve of value Loss

      (5)运行时间及收敛速度

      运行时间是衡量算法时间复杂度的评价指标,运行时间越短表明算法的时间复杂度越小、适应性越好。针对单个业务请求,在业务服从泊松分布、到达率和服务时长的设置同表1时,对比了DeepRWA算法和KSP-FF算法运行时间随波长数变化情况,如图10(a)所示。由图10(a)可知,当信道波长数增加时,两种算法运行时间均明显增加。因为当信道波长数增加时,路由与波长分配策略复杂度增加。但是,随波长数增加,DeepRWA算法运行时间增长的速度明显慢于KSP-FF。当信道中包含18个波长时,与KSP-FF算法相比,DeepRWA算法运行时间增加了0.12 ms;当信道中包含的波长数增加至45时,两种算法的运行时间大致相同;之后,DeepRWA算法运时间优势逐渐明显,当信道中包含的波长数增加至58时,与KSP-FF算法相比,DeepRWA算法运行时间减少了0.07 ms。因此,DeepRWA较KSP-FF算法更适应于波长数较多的光网络。

      图  10  算法的运行时间及收敛速度

      Figure 10.  Algorithm’s execution time and converage speed

      算法的收敛速度反应了智能体使网络达到最低阻塞率需要的训练时长,也即算法收敛需要的业务数量。使用多线程训练神经网络,线程数的不同也会影响网络收敛速度。文中采用A3C算法,业务服从泊松分布,到达率、服务时长和信道波长数的设置同表1,仿真得到算法收敛所需业务数随线程数变化曲线如图10(b)所示,可以看出当线程数增加时,算法训练至收敛需要的业务数呈指数式减少。当线程数为2时,算法需要690000个业务进行训练;当线程数增加至8时,算法收敛所需的业务数已减少至190000。由此可知,在CPU/GPU支持的最大线程范围内,增加线程数可以明显减少算法的训练时间。

    • 为了适应大量动态业务的需求,针对光网络中的RWA问题进行研究,考虑阻塞率、资源利用率两个目标提出一种基于强化学习的路由波长分配算法DeepRWA,采用SDN网络架构实现光网络灵活控制,通过强化学习实现路由选择和波长分配的优化。针对路由选择问题,结合链路上的波长使用情况,使用A3C算法选择合适的路由,使得阻塞率最小;针对波长分配问题,使用首次选中算法选择波长。利用NSFNET网络拓扑下进行了仿真实验,结果表明文中所提的DeepRWA算法阻塞率更低,改善了资源利用率,提升了网络的性能;当链路波长数较多时,与KSP-FF算法相比,文中所提DeepRWA算法运行时间更短,适应性更好。后续结合实际网络和业务进行进一步的研究和测试,为实际应用提供有力的支持。

参考文献 (16)

目录

    /

    返回文章
    返回