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

Ключевые слова и синонимы

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

Постановка задачи

Модель сети / протокол коммуникаций

В геометрических сетях точки встроены в евклидову плоскость. Каждая вершина осведомлена о своем географическом положении, т. е. знает свои координаты (x, y) на плоскости.

У каждой вершины один и тот же диапазон передачи; если вершина v находится в пределах диапазона передачи некоторой другой вершины u, то вершина u может непосредственно передавать данные вершине v, и наоборот. Таким образом, сеть может быть смоделирована при помощи неориентированного графа G = (V, E), в котором две вершины u, v 2 V соединены ребром (u, v) 2 E в том случае, если они находятся в пределах диапазона передачи друг друга. Такие две вершины называются соседними вершинами или просто соседями. Если две вершины находятся за пределами диапазона передачи друг друга, потребуется многоскачковая передача, иными словами, эти вершины должны будут связываться друг с другом через промежуточные вершины.

Стоимость c(e) отправки сообщения соседней вершине через ребро e 2 E можно моделировать различными способами. Среди наиболее распространенных можно упомянуть следующие: метрика прыжков (или каналов) (c(e) = 1), евклидова метрика (c(e) = |e|), где |e| – евклидова длина ребра e и метрика энергии (c(e) = \e\a для a > 2).

В геометрических сетях не предполагается фиксированной инфраструктуры для центрального сервера. Иначе говоря, все вершины выступают и как ячейки сети, и как маршрутизаторы. Топология сети неизвестна вершинам за исключением их непосредственного окружения, т. е. каждая вершина знает свое местоположение и координаты своих соседей. Вершины должны вычислить и поддерживать маршруты для многоскачковых передач самостоятельным и распределенным образом. В большинстве случаев предполагается (если речь идет о сетях датчиков), что память и мощность каждой вершины ограничены.