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

• Управляющая информация, которая может храниться в пакете, ограничена O(log n) – таким образом, он может содержать данные только о константном количестве вершин.

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

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

Однако существует алгоритм географической маршрутизации, стоимость которого зависит не только от общего количества вершин, но и от отношения к кратчайшему пути между источником и адресатом: алгоритм GOAFR+ [15, 16, 18, 24] сочетает жадную маршрутизацию , при которой каждая промежуточная вершина перенаправляет сообщение своему соседу, расположенному ближе всего к вершине-адресату, с маршрутизацией по граням. При использовании совместно с техникой планаризации локально вычислимых графов Гэбриэла затраты алгоритма GOAFR+ ограничены следующим образом: