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

Географическая маршрутизация – это тип маршрутизации, особенно подходящий для динамических децентрализованных сетей. Иногда ее называют направленной или геометрической маршрутизацией, а также маршрутизация на основе географического местоположения или на основе положения. Она основывается на двух принципиальных предположениях. Во-первых, предполагается, что каждая вершина знает свое положение и положение своих соседей по сети. Во-вторых, предполагается, что вершине-источнику сообщения известно положение вершины-адресата. Географическая маршрутизация определяется на евклидовом графе – то есть графе, вершины которого встроены в евклидову плоскость. Формально алгоритмы географической децентрализованной маршрутизации можно определить следующим образом:

Определение 1 (алгоритм географической децентрализованной маршрутизации)

Пусть G = (V, E) – евклидов граф. Задача алгоритма географической децентрализованной маршрутизации A заключается в передаче сообщения от вершины-источника s 2 V вершине-адресату t 2 V при помощи отправки пакетов по ребрам графа G с соблюдением следующих условий:

• Всем вершинам v 2 V известно их собственное географическое положение, а также географическое положение всех их соседей в графе G.

Стоимостные границы, приводимые в данной статье, достигаются на графах единичных дисков, которые определяются следующим образом.

Определение 2 (граф единичных дисков). Пусть V С R2 – множество точек на двумерной плоскости. Граф, ребра которого соединяют все вершины, находящиеся на расстоянии не более 1, называется графом единичных дисков для V.