Modelirovanie, optimizaciâ i informacionnye tehnologii.
Применение алгоритмов элитарной муравьиной системы и Max-Min муравьиной системы для оптимизации маршрутов в сетях квантового распределения ключей
Evgeniy S. Razdyakonov, Sergey Alekseevich Korchagin, А.В. Тимошенко, М.Ф. Булатов
Abstract
Данное исследование посвящено оптимизации маршрутов в сетях квантового распределения ключей (КРК), особенностями которых является ряд физических ограничений и сильная зависимость от топологии. В работе рассматривается применение двух вариаций алгоритма муравьиных колоний, алгоритмов элитарной муравьиной системы (EAS) и Max-Min муравьиной системы (MMAS), для построения оптимальных маршрутов в сетях КРК. Была представлена метрика коммуникационной эффективности маршрута сети КРК, позволяющая оценивать качество маршрута в соответствии с заданными требованиями к пропускной способности и безопасности. Особенностью данной метрики является ее неаддитивная составляющая пропускной способности, зависящая от минимальной эффективности соединения в маршруте. Была проведена серия экспериментов на случайно сгенерированном планарном графе для длинных и коротких маршрутов с алгоритмами EAS и MMAS, в результате которых MMAS оказался значительно более эффективным для длинных маршрутов, но в случае коротких маршрутов EAS находил маршрут быстрее без значительной потери в качестве решения. Результаты, полученные в данном исследовании, могут быть применены в решении задач динамической маршрутизации, а также оптимизации топологии сетей квантового распределения ключей. This study focuses on route optimization in quantum key distribution (QKD) networks, whose features are a number of physical constraints and strong topology dependence. This paper examines the application of two variations of the ant colony algorithm, the elitist ant system (EAS) and Max-Min ant system (MMAS) algorithms, to construct optimal routes in QKD networks. A metric for the communication efficiency of a route in QKD networks has been presented to evaluate the quality of a route according to given capacity and security requirements. The peculiarity of this metric is its non-additive capacity component, which depends on the minimum link efficiency in the route. A series of experiments were conducted on a randomly generated planar graph for long and short routes with EAS and MMAS algorithms, which resulted in MMAS being significantly more efficient for long routes, but in the case of short routes, EAS found the route faster without significant loss in solution quality. The results obtained in this study can be applied in solving problems of dynamic routing, as well as optimization of the topology of quantum key distribution networks.