4551
правка
Географическая маршрутизация: различия между версиями
Перейти к навигации
Перейти к поиску
м
Географическая маршрутизация (посмотреть исходный код)
Версия от 11:43, 19 декабря 2017
, 19 декабря 2017нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 33: | Строка 33: | ||
Рассматриваемые алгоритмы маршрутизации работают на планарных графах, не имеющих пересекающихся ребер. Существуют строго локальные алгоритмы, которые строят подобные планарные графы из заданных графов единичных дисков. Ребра планарных графов разбивают евклидову плоскость на непрерывные области – так называемые грани. Алгоритмы, упоминающиеся в данной статье, основаны на использовании граней. | Рассматриваемые алгоритмы маршрутизации работают на планарных графах, не имеющих пересекающихся ребер. Существуют строго локальные алгоритмы, которые строят подобные планарные графы из заданных графов единичных дисков. Ребра планарных графов разбивают евклидову плоскость на непрерывные области – так называемые [[грань|грани]]. Алгоритмы, упоминающиеся в данной статье, основаны на использовании граней. | ||
== Основные результаты == | == Основные результаты == | ||
| Строка 42: | Строка 42: | ||
Однако существует алгоритм географической маршрутизации, стоимость которого ограничивается не только общим количеством вершин, но и отношением к [[кратчайший путь|кратчайшему пути]] между источником и адресатом: алгоритм GOAFR+ [15, 16, 18, 24] сочетает [[жадный алгоритм|жадную]] маршрутизацию, при которой каждая промежуточная вершина перенаправляет сообщение своему соседу, расположенному ближе всего к вершине-адресату, с маршрутизацией по граням. При использовании совместно с техникой планаризации локально вычислимых графов Гэбриэла затраты алгоритма GOAFR+ ограничены следующим образом: | Однако существует алгоритм географической маршрутизации, стоимость которого ограничивается не только общим количеством вершин, но и отношением к [[кратчайший путь|кратчайшему пути]] между источником и адресатом: алгоритм GOAFR+ [15, 16, 18, 24] сочетает [[жадный алгоритм|жадную]] маршрутизацию, при которой каждая промежуточная вершина перенаправляет сообщение своему соседу, расположенному ближе всего к вершине-адресату, с маршрутизацией по граням. При использовании совместно с техникой планаризации [[Локальные вычисления на графах|локально вычислимых]] графов Гэбриэла затраты алгоритма GOAFR+ ограничены следующим образом: | ||