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