Two-phase routing algorithm in the time-dependent networks.pdf В современных телекоммуникационных сетях приходится иметь дело с расширением задачи о кратчайшем пути, когда время прибытия в конечную вершину y дуги e = (x,y) ориентированного графа G зависит не только от веса дуги e, но и времени выхода из начальной вершины x этой дуги. Функции, заданные на дугах графа G подобным образом, называют функциями прибытия, а сам граф G - нестационарной сетью. Задача поиска кратчайшего пути в нестационарной сети носит название Time-Dependent Shortest-Path problem, или коротко TDSP [1]. Известно, что TDSP для нестационарной сети общего вида без каких-либо ограничений на топологию сети и функции прибытия является NP-трудной задачей [2]. Когда функции прибытия удовлетворяют условию FIFO (First-In First-Out), задача TDSP полиномиально разрешима [1]. В этом случае задача TDSP традиционно решается алгоритмом Дейкстры. Предлагается решать задачу TDSP двухфазным алгоритмом маршрутизации по ориентирам, известным в литературе как алгоритм ALT (A* with Landmarks & Triangle). При этом под ориентиром понимается выделенная вершина исходного графа. Пусть задан ориентированный граф G = (V, E) без кратных дуг и петель (далее просто граф), в котором для всякой дуги e = (x,y) G E определена весовая функция wxy(t) ^ 0 следующим образом: w"(t) = vxXw. Здесь величина /xy - расстояние между вершинами x,y G V, а vxy(t) -скорость движения по дуге (x, y) G E при условии, что старт из x осуществлён в момент времени t. Считаем, что выполнены естественные для сетей условия: vxy(t) > 0 и /xy ^ 0. Сопоставим дуге (x,y) G E функцию прибытия Fxy(t) = t + wxy(t), где t - время отправления из вершины x при движении в вершину y по дуге (x,y). Если для каждой дуги (x,y) G E и любых моментов времени 0 < t1 ^ t2 выполняется неравенство Fxy(t1) ^ Fxy(t2), то говорят, что функция прибытия является монотонной, или удовлетворяет условию FIFO. Для всякой дуги e = (x, y) G E всегда верны отношения x = y, t > 0, wxy(t) ^ 0. Отсюда следует, что Fxy(t) ^ t > 0. (1) Неравенство (1) отражает непосредственный ход времени: «отправляясь из вершины x в момент времени t, невозможно прибыть в вершину y раньше времени t вне зависимости от значений /xy и vxy (t)». Граф G с учётом всех указанных предположений будем называть нестационарной сетью с условием FIFO. Последовательность вершин P = (x0, x1,... , xk), в которой s = x0, d = xk, (xi-1,xi) G E для i = 1, 2,...,k, задаёт путь из вершины s в вершину d в графе G, старт которого осуществляется в момент времени ts. Такой путь обозначается (P, ts). Если в G существует (s, d)-путь P, то вершина d достижима из s по пути P, что записывается как s ^ d. Полагаем, что вес (s, d)-пути в сети G вычисляется традиционным для задач маршрутизации способом [3] fc-1 w(P,ts) = ts + WxiXi+1 (ti), где to = ts,ti+1 = (ti), i=0 а вес кратчайшего (s, d, ^)-пути определяется следующим образом: dist(s, d, ts) = min{w(P, ts): s ^ d}. Тройку величин (s, d, ts), где s и d - стартовая и целевая вершина соответственно, ts - стартовое время, будем называть запросом на поиск в нестационарной сети G = (V, E) кратчайшего (s, d, ^)-пути, или кратко (s, d, ^-запросом. С использованием введённых понятий и обозначений задача TDSP формулируется следующим образом: Time-Dependent Shortest-Path problem Заданы: нестационарная сеть G = (V, E) с условием FIFO, (s, d, ^)-запрос. Требуется: найти значение dist(s,d,ts) и последовательность вершин, образующих кратчайший (s, d, ^)-путь. Задача TDSP всегда имеет решение, возможно, не единственное, если вершина d достижима из вершины s в графе G. Условие FIFO гарантирует справедливость неравенства (1), которое требуется для корректной работы алгоритма Дейкстры, а также его различных версий, включая алгоритмы A* и ALT [1]. В данной работе предполагается, что сеть является метрической, т. е. выполнено неравенство треугольника для весов дуг. Доказано, что неравенство треугольника, определённое через оптимистичные значения весов дуг, обеспечивает выполнимость свойств допустимости и преемственности потенциальных функций, необходимых для корректной работы алгоритма ALT. Расстановка ориентиров в вершинах графа - фактор, существенно влияющий на значение потенциальных функций, а значит, и на быстродействие алгоритма A*, выполняющегося на второй фазе алгоритма ALT [2]. Задача оптимального выбора ориентиров в графе G заключается в определении числа ориентиров и мест их расстановки в вершинах этого графа. Данная задача носит комбинаторный характер и является труднорешаемой. Доказано, что даже в частном случае, когда число ориентиров фиксировано, эта задача NP-трудная [2]. Поэтому расстановку ориентиров обычно осуществляют с помощью эвристических алгоритмов. Экспериментально установлено разумное число ориентиров, которое обеспечивает эффективность алгоритма A* на больших графах,-от 9 до 16. С учётом данного факта задача выбора ориентиров сводится к более простой, но по-прежнему труднорешаемой задаче расстановки заданного числа K ориентиров в графе G = (V, E) [2]. Предложена эвристика AdaHeuris по расстановке заданного числа ориентиров в вершинах графа, которая отличается от существующих и применяемых в ALT эвристик тем, что в ней текущий набор ориентиров корректируется на основе истории обработки запросов. Эвристика AdaHeuris позволяет значительно уменьшить время работы второй фазы алгоритма ALT и решать задачу TDSP для последовательности запросов, поступающих в режиме онлайн. Показано, что разработанный алгоритм ALT находит точное решение задачи TDSP за время O(|V|2). Алгоритм проверен на реальных сетях, представленных в базе данных DIMACS http://www.dis.uniroma1.it/challenge9/. Результаты сравнения разработанного алгоритма с алгоритмом Дейкстры приведены в таблице, где С - коэффициент ускорения, определяемый как отношение времени работы сравниваемых между собой алгоритмов; T - среднее время выполнения одного запроса алгоритмом ALT. Достигнутые значения коэффициента ускорения оказались сопоставимы со значениями подобных коэффициентов, полученных в работе [4], в которой задача TDSP решается с помощью иерархического алгоритма. Иерархические алгоритмы - альтернативный подход ускорения алгоритма Дейкстры (по отношению к алгоритму ALT), в котором ускорение достигается за счёт разложения исходной сети на несколько уровней. Результаты экспериментов показали, что разработанный алгоритм ALT может быть использован для эффективного решения задачи TDSP на последовательности запросов, поступающих в режиме онлайн, наряду с другими подходами. Результаты сравнения алгоритмов Название графа Параметры графа C T, с |V | |E| Rome99 3353 8870 1,2 0,03622 AK 69082 156200 4,01 8,04443 VT 97975 215116 5,32 17,8026

Скачать электронную версию публикации