The Echo Ratio Effect on the Routing Efficiency of Full Rate Echo Algorithm
DOI:
https://doi.org/10.22213/2413-1172-2019-2-65-72Keywords:
ad-hoc network, delivery time, reinforcement training, simulation, q-routingAbstract
In previous papers the authors proposed a routing algorithm called Adaptive Q-routing Full Echo. The algorithm in each node uses two types of learning coefficients: primary and secondary, and the additional learning factors change dynamically for each node depending on the estimated average delay time.
The additional learning factor is updated at each modeling step for each node separately. The additional coefficient calculation is based on the parameter called echo ratio. To study the influence of the coefficients on the algorithm performance is an important step for achieving the greater routing efficiency. The influence of the echo ratio on the routing efficiency are given for two network structures, the Littman network and the NASK academic network. The influence of three parameters has been analyzed: the duration of learning, the maximum value of the average delay, and the steady value of the average delay. For the additional training parameter, the coefficient was chosen in descending order of integer powers of the number 10 towards the negative axis, starting with power 0 and ending with power 6, with additional intermediate values equal to half the interval between two nearest powers. When comparing the results obtained for two network structures, the similar patterns for the steady-state average criterion and different patterns for the other two criteria were obtained.
A further research implies the formation of network structures and their characteristics, for which certain values of the coefficients called echo ratio will give similar results.References
Sutton R.S. and Barto A.G. Reinforcement learning: An introduction. Cambridge, MIT press, 1998, 328 p.
Watkins C., Dayan P. Q-learning. Machine learning, 1992, vol. 8, no. 3, pp. 279-292.
Boyan J., Littman M. Packet Routing In Dynamically Changing Networks: A Reinforcement Learning Approach. Advances in Neural Information Processing Systems, 1994, pp. 671-678.
Kaelbling L.P., Littman M.L., Moore A.W. Reinforcement learning. A survey Journal of artificial intelligence research, 1996, vol. 4, pp. 237-285.
Kumar S., Miikkulainen R. Dual Reinforcement
Q-Routing: An On-Line Adaptive Routing Algorithm. Artificial neural networks in engineering, 1997, pp. 231-238.
Choi S. and Yeung Dit-Yan. Predictive Q-routing: A memory-based reinforcement learning approach to adaptive traffic control. Advances in Neural Information Processing Systems, 1996, vol. 8, pp. 945-951.
Subramanian D., Druschel P., Chen J. Ants and re-inforcement learning: A case study in routing in dynamic networks. IJCAI, 1997, 2, pp. 832-839.
Tao N., Baxter J., Weaver L. A Multi-Agent Policy-Gradient Approach to Network Routing. ICML, 2001, vol. 1, pp. 553-560.
Peshkin L., Savova V. Reinforcement learning for adaptive routing. Proc. of the 2002 International Joint Conference on Neural Networks, 2002, vol. 2, pp. 234-244.
Hoceini S., Mellouk A., Amirat Y. K-shortest paths Q-routing: a new QoS routing algorithm in tele-communication networks. Networking-ICN 2005. Springer Berlin Heidelberg, 2005, pp. 164-172.
Lopez A.M. and Heisterkamp D.R. Simulated Annealing Based Hierarchical Q-Routing: A Dynamic Routing Protocol. IEEE Eighth International Conference on Information Technology. New Generations, 2011, pp. 791-796.
Chetret D., Tham C.K., Wong L.W.C. Rein-forcement learning and CMAC-based adaptive routing for manets. IEEE International Conference on Networks, 2004, vol. 2, pp. 540-544.
Arroyo-Valles R., Alaiz-Rodríguez R., Guerrero-Curieses A., Cid-Sueiro J. Q-Probabilistic Routing In Wireless Sensor Networks. IEEE 3rd International Con-ference on Intelligent Sensors. Sensor Networks and Information, 2007, pp. 1-6.
Desai R., Patil B.P. Enhanced Confidence Based Q-Routing for an Ad Hoc Network. American Journal of Educational Science 1.3, 2015, pp. 60-68.
Shilova Y., Kavalerov M. and Bezukladnikov I. Full Echo Q-routing with adaptive learning rates: a rein-forcement learning approach to network routing. IEEE NW Russia Young Researchers in Electrical and Elec-tronic Engineering Conference (EIConRusNW), 2016, pp. 341-344.
Шилова Ю. А. Алгоритм маршрутизации семейства Q-routing, основанный на динамическом изменении коэффициентов обучения за счет оценки средней задержки в сети // Вестник Пермского научного центра. 2015. №. 2. C. 79–93.
Kavalerov M., Shilova Y., Likhacheva Y. Adap-tive Q-Routing with random echo and route memory. 20th Conference of Open Innovations Association (FRUCT). St. Petersburg, 2017, pp. 138-145.
Кавалеров М. В. Сетевая маршрутизация на основе обучения с подкреплением в виде адаптивного Q-routing, использующего схему Random Echo, память маршрутов и оценки времени ожидания в очереди соседнего узла // Нейрокомпьютеры: разработка, применение. 2017. № 6. C. 20–26.
Pacut A., Gadomska M., Igielski A. Ant-routing vs. q-routing in telecommunication networks. Proc. of the 20th ECMS Conference, May 28th - 31st, 2006, Bonn, Germany, pp. 67-72.
