Intelligent Routing Algorithm for Wireless Networks Based on Deep Reinforcement Learning

doi:10.19678/j.issn.1000-3428.0066301

Abstract

Abstract:

Intelligent routing algorithm based on Deep Reinforcement Learning(DRL) has become an important development direction for intelligent routing algorithms due to its combination of deep learning perception ability and reinforcement learning decision-making ability.However, existing DRL-based intelligent routing algorithms cannot adapt to the dynamically changing network topology in wireless networks, making it difficult to make appropriate routing decisions.To address this issue, this paper proposes an intelligent routing algorithm called MPNN-DQN, which combines the Message Passing Neural Network (MPNN) and DRL.MPNN-DQN uses MPNN to learn irregular network topology, enabling it to make effective decisions even when the network topology changes dynamically.Moreover, a hop-by-hop routing generation method based on k-order neighbor information aggregation is designed to improve the scalability of the algorithm while ensuring decision-making effectiveness; thus, the algorithm can be better applied to medium- to large-sized network topologies.Experimental results show that compared to routing algorithms such as GCN, DRSIR, and DQN, MPNN-DQN has superior average latency, packet loss rate, and network throughput indicators.In three different network scenarios, Germany, GBN, and synth50, the throughput of the proposed algorithm has been improved by 3.27%-23.03%, and has strong adaptability to dynamic network topologies.

Key words: Deep Reinforcement Learning(DRL), Message Passing Neural Network(MPNN), neighbor information aggregation, intelligent routing, dynamically changing network topology

摘要：

基于深度强化学习(DRL)的智能路由算法因兼具深度学习的感知能力和强化学习的决策能力，成为路由决策的重要发展方向。然而，现有基于深度强化学习的智能路由算法无法适应无线网络中动态变化的网络拓扑结构，难以在网络拓扑动态变化时做出恰当的路由决策。针对该问题，提出一种结合消息传递神经网络(MPNN)和DRL的智能路由算法MPNN-DQN。利用MPNN对不规则的网络拓扑进行学习，使其在网络拓扑动态变化时仍然能够做出有效的决策。设计基于k阶邻居信息聚合的逐跳路由生成方法，使得模型在保证决策效果的同时提升算法的可扩展性，能够更广泛地适用于中大型网络拓扑。实验结果表明，相比GCN、DRSIR、DQN等路由算法，该算法具有较优的平均时延、丢包率和网络吞吐量指标，在Germany、GBN和synth50这3种不同的网络场景下，该算法的吞吐量提升3.27%~23.03%，具有较强适应动态网络拓扑的能力。

关键词: 深度强化学习, 消息传递神经网络, 邻居信息聚合, 智能路由, 动态变化的网络拓扑

Linghui KONG, Zheheng RAO, Yanyan XU, Shaoming PAN. Intelligent Routing Algorithm for Wireless Networks Based on Deep Reinforcement Learning[J]. Computer Engineering, 2023, 49(9): 199-207, 216.

孔凌辉, 饶哲恒, 徐彦彦, 潘少明. 基于深度强化学习的无线网络智能路由算法[J]. 计算机工程, 2023, 49(9): 199-207, 216.

/ / Recommend / Download Citations

URL: http://www.ecice06.com/EN/10.19678/j.issn.1000-3428.0066301

http://www.ecice06.com/EN/Y2023/V49/I9/199

Figures/Tables 14

Fig.1 Architecture of intelligent routing scheme

Fig.2 Schematic diagram of node-link transformation

Fig.3 Message update process for node one within two time steps

Fig.4 Procedure of feature extraction

Fig.5 Architecture of DQN model

Fig.6 Structure of network topology used in this paper

Fig.7 Ablation experimental results

Fig.8 Performance comparison among different methods on original topology GEANT2

Fig.9 Schematic diagram of scenario where some links in the original topology fail

Fig.10 Performance comparison among different methods in the scenario of link failure in the original topology section

Fig.11 Performance comparison among different methods on new topology

References 25

1	DUTRA E A, ALMANÇA GONÇALVES DA COSTA OLIVEIRA D, KEDOR-HACKMANN E R M, et al. Determination of Sun Protection Factor (SPF) of sunscreens by ultraviolet spectrophotometry. Revista Brasileira De Ciências Farmacêuticas, 2004, 40 (3): 381- 385. doi: 10.1590/S1516-93322004000300014
2	ZHANG C Y, PATRAS P, HADDADI H. Deep learning in mobile and wireless networking: a survey. IEEE Communications Surveys & Tutorials, 2019, 21 (3): 2224- 2287.
3	AL-SAADI A, SETCHI R, HICKS Y, et al. Routing protocol for heterogeneous wireless mesh networks. IEEE Transactions on Vehicular Technology, 2016, 65 (12): 9773- 9786. doi: 10.1109/TVT.2016.2518931
4	LUONG N C, HOANG D T, GONG S M, et al. Applications of deep reinforcement learning in communications and networking: a survey. IEEE Communications Surveys & Tutorials, 2019, 21 (4): 3133- 3174.
5	韩向敏, 鲍泓, 梁军, 等. 一种基于深度强化学习的自适应巡航控制算法. 计算机工程, 2018, 44 (7): 32-35, 41. URL
	HAN X M, BAO H, LIANG J, et al. An adaptive cruise control algorithm based on deep reinforcement learning. Computer Engineering, 2018, 44 (7): 32-35, 41. URL
6	LIU W X. Intelligent routing based on deep reinforcement learning in software-defined data-center networks[C]//Proceedings of Symposium on Computers and Communications. Washington D. C., USA: IEEE Press, 2020: 1-6.
7	LIU Q Z, CHENG L, JIA A L, et al. Deep reinforcement learning for communication flow control in wireless mesh networks. IEEE Network, 2021, 35 (2): 112- 119. doi: 10.1109/MNET.011.2000303
8	SCARSELLI F, GORI M, TSOI A C, et al. The graph neural network model. IEEE Transactions on Neural Networks, 2009, 20 (1): 61- 80. doi: 10.1109/TNN.2008.2005605
9	潘少明, 王玉杰, 种衍文. 基于图卷积神经网络的跨域行人再识别. 华中科技大学学报(自然科学版), 2020, 48 (9): 44- 49. URL
	PAN S M, WANG Y J, CHONG Y W. Cross-domain person re-identification using graph convolutional networks. Journal of Huazhong University of Science and Technology (Nature Science Edition), 2020, 48 (9): 44- 49. URL
10	RUSEK K, SUÁREZ-VARELA J, MESTRES A, et al. Unveiling the potential of graph neural networks for network modeling and optimization in SDN[C]//Proceedings of Symposium on SDN Research. New York, USA: ACM Press, 2019: 140-151.
11	SUÁREZ-VARELA J, CAROL-BOSCH S, RUSEK K, et al. Challenging the generalization capabilities of graph neural networks for network modeling[C]//Proceedings of the Conference on Posters and Demos. Washington D. C., USA: IEEE Press, 2019: 114-115.
12	GILMER J, SCHOENHOLZ S S, RILEY P F, et al. Neural message passing for quantum chemistry[EB/OL]. [2022-10-15]. https://arxiv.org/pdf/1704.01212.pdf.
13	刘辰屹, 徐明伟, 耿男, 等. 基于机器学习的智能路由算法综述. 计算机研究与发展, 2020, 57 (4): 671- 687.
	LIU C Y, XU M W, GENG N, et al. A survey on machine learning based routing algorithms. Journal of Computer Research and Development, 2020, 57 (4): 671- 687.
14	XU Q, ZHANG Y F, WU K, et al. Evaluating and boosting reinforcement learning for intra-domain routing[C]//Proceedings of the 16th International Conference on Mobile Ad Hoc and Sensor Systems. Washington D. C., USA: IEEE Press, 2020: 265-273.
15	CASAS-VELASCO D M, RENDON O M C, DA FONSECA N L S. DRSIR: a deep reinforcement learning approach for routing in software-defined networking. IEEE Transactions on Network and Service Management, 2022, 19 (4): 4807- 4820. doi: 10.1109/TNSM.2021.3132491
16	ZHU H, GUPTA V, AHUJA S S, et al. Network planning with deep reinforcement learning[C]//Proceedings of the ACM SIGCOMM 2021 Conference. New York, USA: ACM Press, 2021: 258-271.
17	KATO N, FADLULLAH Z, MAO B, et al. The deep learning vision for heterogeneous network traffic control: proposal, challenges, and future perspective. IEEE Wireless Communications, 2017, 24 (3): 146- 153. doi: 10.1109/MWC.2016.1600317WC
18	HASSELT H V, GUEZ A, SILVER D. Deep rein- forcement learning with double Q-learning[C]//Proceedings of the 28th AAAI Conference on Artificial Intelligence. [S. l. ]: AAAI Press, 2016: 1-10.
19	GAWLOWICZ P, ZUBOW A. NS3-Gym: extending OpenAI Gym for networking research[EB/OL]. [2022-10-15]. https://arxiv.org/pdf/1810.03943.pdf.
20	BARRETO F, WILLE E C G, NACAMURA J L. Fast emergency paths schema to overcome transient link failures in ospf routing[EB/OL]. [2022-10-15]. https://www.airccse.org/journal/cnc/0312cnc02.pdf.
21	CÂRPA R, DIAS DE ASSUNÇÃO M, GLÜCK O, et al. Responsive algorithms for handling load surges and switching links on in green networks[C]//Proceedings of International Conference on Communications. Washington D. C., USA: IEEE Press, 2016: 1-7.
22	PEDRO J, SANTOS J, PIRES J. Performance evaluation of integrated OTN/DWDM networks with single-stage multiplexing of optical channel data units[C]//Proceedings of the 13th International Conference on Transparent Optical Networks. Washington D. C., USA: IEEE Press, 2011: 1-4.
23	JIA J C, ZHANG Q. MMC01-3: shared tree for application-layer multi-source multicast[C]//Proceedings of Globecom. Washington D. C., USA: IEEE Press, 2007: 1-5.
24	唐鑫, 徐彦彦, 潘少明. 基于图卷积神经网络的智能路由算法. 计算机工程, 2022, 48 (3): 38- 45. URL
	TANG X, XU Y Y, PAN S M. Intelligent routing algorithm based on the graph convolutional neural network framework. Computer Engineering, 2022, 48 (3): 38- 45. URL
25	ZHAO L, WANG J D, LIU J J, et al. Routing for crowd management in smart cities: a deep reinforcement learning perspective. IEEE Communications Magazine, 2019, 57 (4): 88- 93.

[1]	Guanying ZHANG, Peng YI, Dan LI, Di ZHU, Ming MAO. Service Function Chain Deployment Method for Large-Scale Network [J]. Computer Engineering, 2023, 49(8): 122-129.
[2]	Jing MEI, Longbao DAI, Zhao TONG, Xin DENG, Jiake WANG. Adaptive Offloading Algorithm Based on Lyapunov Optimization Under Resource Constraints [J]. Computer Engineering, 2023, 49(7): 34-46.
[3]	LI Qiang, YI Jinhui, DU Tingting, WANG Shengchun. Dependent Task Offloading and Resource Allocation Based on A3C in Mobile Edge Computing [J]. Computer Engineering, 2023, 49(6): 42-52.
[4]	LI Zifan, WANG Hao, FANG Baofu. A Method for Multi-Agent Cooperation Based on Multi-Step Dueling Network [J]. Computer Engineering, 2022, 48(5): 74-81.
[5]	TANG Xin, XU Yanyan, PAN Shaoming. Intelligent Routing Algorithm Based on the Graph Convolutional Neural Network Framework [J]. Computer Engineering, 2022, 48(3): 38-45.
[6]	YU Jing, LU Lingyun, LI Xiang. Edge-Cloud Collaborative Task Offloading Mechanism Based on DDQN in Vehicular Networks [J]. Computer Engineering, 2022, 48(12): 156-164.
[7]	LIU Xianfeng, LIANG Sai, LI Qiang, ZHANG Jin. Cloud-Edge Collaborative DNN Inference Based on Deep Reinforcement Learning [J]. Computer Engineering, 2022, 48(11): 30-38.
[8]	YANG Wenqi, ZHANG Yang, NIE Jiangtian, YANG Helin, KANG Jiawen, XIONG Zehui. Energy and Information Management Strategy Based on Federated Learning for Wireless Network Nodes [J]. Computer Engineering, 2022, 48(1): 188-196,203.
[9]	YANG Tian, YANG Jun. Deep Reinforcement Learning Method of Offloading Decision and Resource Allocation in MEC [J]. Computer Engineering, 2021, 47(8): 37-44.
[10]	YANG Siming, SHAN Zheng, DING Yu, LI Gangwei. Survey of Research on Deep Reinforcement Learning [J]. Computer Engineering, 2021, 47(12): 19-29.
[11]	YAN Jiaojie, ZHANG Qieshi, HU Xiping. Review of Path Planning Techniques Based on Reinforcement Learning [J]. Computer Engineering, 2021, 47(10): 16-25.
[12]	JIN Jiuyi, QIU Gongan. Joint Optimization of Resource Allocation and Power Control in C-V2X Communications [J]. Computer Engineering, 2021, 47(10): 147-152.
[13]	CHEN Jianping, ZHOU Xin, FU Qiming, GAO Zhen, FU Baochuan, WU Hongjie. Dual Network DQN Algorithm Based on Second-order Temporal Difference Error [J]. Computer Engineering, 2020, 46(5): 78-85,93.

Please choose a citation manager

Content to export