Влияние коэффициента «скорость распространения эхо» на эффективность маршрутизации алгоритма ADAPTIVE RATE FULL ECHO
DOI:
https://doi.org/10.22213/2413-1172-2019-2-65-72Ключевые слова:
сеть ad-hoc, время доставки, обучение с подкреплением, моделирование, q-маршрутизацияАннотация
В предыдущих статьях авторами был предложен алгоритм маршрутизации Adaptive Q-routing Full Echo, в котором каждый узел использует два типа коэффициентов обучения – основной и дополнительный – и дополнительные коэффициенты обучения для каждого узла в зависимости от оценок среднего времени задержки изменяются динамически. Дополнительный коэффициент обучения обновляется на каждом шаге моделирования для каждого узла в отдельности.
В основе расчета дополнительных коэффициентов лежит параметр «скорость распространения эхо», поэтому исследование влияния данного коэффициента на эффективность работоспособности алгоритма является важной частью достижения наибольшей эффективности маршрутизации. Результаты влияния коэффициента «скорость распространения эхо» на эффективность маршрутизации приведены для двух структур сетей – сети Литтмана и академической сети NASK – и проанализированы по трем параметрам: длительность обучения, максимальное значение средней задержки и установившееся значение средней задержки. Для дополнительного параметра обучения коэффициент подбирался в порядке убывания целочисленных степеней числа 10 в сторону отрицательной оси, начиная со степени 0 и заканчивая степенью 6, с дополнительными промежуточными значениями, равными половине интервала между двумя ближайшими степенями. При сравнении полученных результатов для двух структур сетей были получены как сходные закономерности для критерия установившегося среднего значения, так и отличающиеся для остальных двух критериев.
Дальнейшее направление исследования заключается в формировании структур сетей и их характеристик, для которых определенные значения коэффициентов «скорость распространения эхо» будут давать схожие результаты.Библиографические ссылки
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.
