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

Географическая маршрутизация особенно интересна по той причине, что не требует использования каких-либо таблиц маршрутизации. Кроме того, как только положение вершины-адресата становится известно, все операции оказываются строго локальными, то есть каждая вершина должна отслеживать только своих непосредственных соседей. Эти два фактора – отсутствие необходимости в поддержке актуальных таблиц маршрутизации и независимость от происходящих на большом расстоянии изменений топологии – делают географическую маршрутизацию исключительно удобным инструментом для работы в децентрализованных сетях. Кроме того, географическую маршрутизацию можно в некотором смысле рассматривать как «урезанную» версию маршрутизации от источника, подходящей для динамических сетей: Если при маршрутизации от источника весь маршрут сообщения от одной вершины к другой (hop-by-hop) задается вершиной-источником, то в случае географической маршрутизации источник просто прикрепляет к сообщению положение вершины-адресата. Поскольку положение вершины-адресата в общем случае меняется медленно в сравнении с частотой изменений топологии между источником и адресатом, рационально было бы отслеживать положение адресата вместо поддержки информации о топологии сети в актуальном состоянии; если вершина-адресат не перемещается слишком быстро, сообщение будет доставлено вне зависимости от возможных изменений топологии промежуточных вершин.

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