A Novel Routing Algorithm for Mobile ad-hoc Networks Based on Q-learning and its Generalization to FSR Routing Protocol

Document Type : Computer Networking-Amin Hosseini

Authors

• Mahmoud Alilou ¹
• Abdolreza Hatamlou ²

¹ Islamic Azad University

² Islamic Azad University, Khoy Branch

10.22067/cke.v1i2.63668

Abstract

This study proposes a novel routing algorithm using Q-learning. Q-learning is a machine learning (artificial intelligence) algorithm using the reinforcement learning policy which can be used to solve problems for which there are different ways to reach their goal. The proposed algorithm, the Modified Q-learning routing algorithm (MQRA), has eliminated the episodes of Q-learning required to gradually learn in different stages and this has made it a rapid routing algorithm. MQRA can be used in various types of networks. This study uses MQRA in mobile ad-hoc networks, its generalization to fisheye state routing (FSR) (a routing algorithm) and its performance results are compared with the standard FSR. Experimental results confirm the applicability and potential of the proposed algorithm.

Keywords

• Routing Algorithm
• Mobile ad-hoc Networks
• FSR Protocol
• Reinforcement learning
• Routing in MANETs

---

References

[1] R. S. Sutton and A. G. Barto, ―Reinforcement Learning: An Introduction,The MIT Press, 1998.

[2] A. F¨orster, ―Machine learning techniques applied to wireless ad-hoc networks: Guide and survey, ‖ in Proceedings of the 3rd International Conference on Intelligent Sensors, Sensor Networks and Information Processing (ISSNIP), 2007.

[3] G. Pei, M. Gerla and T.-W. Chen, “Fisheye State Routing in Mobile Ad-Hoc Networks”, In Proceedings of the 2000 ICDCS Workshops, Taipei, Taiwan, pp. D71-D78, Apr. 2000.

[4] L. Kleinrock and K. Stevens, “Fisheye: A Lenslike Computer Display Transformation”, Technical report, UCLA, Computer Science Department, 1971.

[5] T.-W. Chen and M. Gerla, “Global State Routing: A New Routing Scheme for Ad-hoc Wireless Networks”, In Proceedings of IEEE ZCC’98, Atlanta, GA, pp. 171-175, Jun. 1998.

[6] Gyanappa A. Walikar, Rajashekar C. Biradar , A survey on hybrid routing mechanisms in mobile ad hoc networks PP. 48-63. doi>10.1016/j.jnca.2016.10.014

[7] Fahimeh Dabaghi, Zeinab Movahedi, Rami Langar, A survey on green routing protocols using sleep-scheduling in wired networks, PP. 106-122. doi>10.1016/j.jnca.2016.10.005.

[8] Shafiee, Kaveh, and Victor Leung. Connectivity-aware minimum-delay geographic routing with vehicle tracking in VANETs. Ad Hoc Networks 9.2 (2011): 131-141.

[9] Ding, Zhiguo, and Kin K. Leung. Cross-layer routing using cooperative transmission in vehicular ad-hoc networks. Selected Areas in Communications, IEEE Journal on 29.3 (2011): 571-581.

[10] Sofra, Nikoletta, Athanasios Gkelias, and Kin K. Leung. Link residual-time estimation for VANET cross-layer design. Cross Layer Design, 2009. IWCLD'09. Second International Workshop on. IEEE, 2009.

[11] Al-Rabayah, Mohammad, and Robert Malaney, “A new hybrid location-based ad hoc routing protocol”, Global Telecommunications Conference (GLOBECOM 2010), 2010 IEEE. IEEE, 2010.

[12] Al-Sultan, Saif, Ali H. Al-Bayatti, and Hussein Zedan, “Context-aware driver behavior detection system in intelligent transportation systems”, Vehicular Technology, IEEE Transactions on 62.9 (2013): 4264-4275.

[13] Yang, Qing, et al. “ACAR: adaptive connectivity aware routing protocol for vehicular ad hoc networks”, Computer Communications and Networks, 2008. ICCCN'08. Proceedings of 17th International Conference on. IEEE, 2008.

[14] Schaul, T. Bayer, J. D. Weirstra, Sun, T. “PyBrain”, Journal of Machine Learning Research, vol 11, no.2, 2010.

[15] Kulkani, S., Rao, R., “Performance Optimization of Reinfrocement Learning Based Routing Algorithm Applied to Ad hoc Networks”, International Journal of Computer Networks and Communications, vol. 2, pp. 46- 60, 2010.