Маршрутизация в геометрических сетях: различия между версиями

Маршрутизация по циркулю, тип 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.