4551
правка
Маршрутизация в геометрических сетях: различия между версиями
Перейти к навигации
Перейти к поиску
Маршрутизация в геометрических сетях (посмотреть исходный код)
Версия от 21:55, 31 мая 2019
, 31 мая 2019→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 69: | Строка 69: | ||
== Применение == | == Применение == | ||
'''Онлайновая геометрическая маршрутизация''' | '''Онлайновая геометрическая маршрутизация''' | ||
Онлайновая геометрическая маршрутизация основывается на крайне скудном объеме информации, содержащейся в передаваемом сообщении, и локальной информации, доступной в узлах сети. Это приводит к естественной масштабируемости геометрической маршрутизации. Кроме того, предполагается, что сеть статична, то есть узлы не перемещаются, а ребра не пропадают и не появляются. | |||
Маршрутизация по циркулю, тип I (Compass Routing I, CR-I) [ ] представляет собой жадную процедуру на основе триангуляции Делоне и наблюдения из леммы 2, в ходе которой на каждом шагу сообщение сегда направляется соседнему узлу, находящемуся ближе к точке назначения t. К сожалению, сообщение может попасть в локальный минимум (тупик) в случае, когда все соседи находятся дальше от t. Процедура CR-I очен проста. Вычисление триангуляции Делоне является локальным и недорогим (см. лемму 1). Ооднако алгоритм не гарантирует успешной доставки. | |||
Маршрутизация по циркулю, тип II (Compass Routing II, CR-II) [1 , 4] – первый алгоритм геометрической маршрутизации, основанный на принципе правой руки и наблюдении из леммы 3, который гарантирует успешную доставку в любом графе, вложенном в R2. Алгоритм также носит название маршрутизации по граням (Face Routing), поскольку пересылаемое сообщение движется вдоль периметров граней, постепенно приближаясь к точке назначения. В выпуклом графе сегмент st пересекается с периметром любой грани не более двух раз. Таким образом, когда пересылаемое сообщение попадает в первое ребро e, пересекающее st, оно немедленно оказывается на грани по другую сторону e. Следовательно, каждое ребро на каждой грани проходит не более чем дважды. Однако в графе общего вида сообщение должно пройти по всем ребрам, инцидентным грани. Это необходимо для поиска точки пересечения xi, ближайшей к точке назначения t. В этом случае каждое ребро может проходиться целых четыре раза. Однако, если после обхода всех ребер пересылаемое сообщение выбирает более короткий путь к xi (вместо того чтобы воспользоваться принципом пракой руки), амортизированная стоимость прохода каждого ребра оказывается равной 3 [1]. Доказательство корректности следует из леммы 3. | |||
Теорема 7 [1]. Алгоритм Compass Routing II гарантирует успешную доставку сообщений в планарных графах за время O(n) шагов, где n – количество узлов в сети. | |||