Географическая маршрутизация - Geographic routing

Географическая маршрутизация (также называемый георутинг[1] или же позиционная маршрутизация) это маршрутизация принцип, который опирается на географическое положение Информация. В основном предлагается для беспроводные сети и основан на идее, что источник отправляет сообщение в географическое положение пункта назначения вместо использования сетевой адрес. В районе пакетное радио сетей, идея использования информации о местоположении для маршрутизации была впервые предложена в 1980-х годах.[2] для межсетевых соединений.[3] Географическая маршрутизация требует, чтобы каждый узел может определить свое собственное местоположение и что источнику известно местоположение пункта назначения. С этой информацией сообщение может быть направлено к месту назначения без знания топология сети или предыдущее открытие маршрута.

Подходы

Существуют различные подходы, такие как однонаправленный, многопутевой и наводнение -основанные стратегии (см.[4] для опроса). Большинство однонаправленных стратегий основаны на двух методах: жадная пересылка и маршрутизация лица. Жадная пересылка пытается приблизить сообщение к месту назначения на каждом этапе, используя только локальную информацию. Таким образом, каждый узел пересылает сообщение соседу, наиболее подходящему с локальной точки зрения. Наиболее подходящим соседом может быть тот, кто минимизирует расстояние до пункта назначения на каждом шаге (Жадный). В качестве альтернативы можно рассмотреть другое понятие прогресса, а именно прогнозируемое расстояние на линии исходный пункт назначения (MFR, NFP) или минимальный угол между соседом и пунктом назначения (маршрутизация по компасу). Не все эти стратегии работают без петель, т.е. сообщение может циркулировать между узлами в определенной совокупности. Известно, что базовая жадная стратегия и MFR работают без петель, а NFP и Compass Routing - нет.[5]

Варианты жадной пересылки: у исходного узла (S) есть разные варианты поиска ретрансляционного узла для дальнейшей пересылки сообщения в пункт назначения (D). A = Ближайший с прогрессом пересылки (NFP), B = Максимальный прогресс пересылки в пределах радиуса (MFR), C = Маршрутизация по компасу, E = Жадный
Маршрутизация лиц: сообщение направляется по внутренней стороне граней коммуникационного графа, с изменениями лиц на краях, пересекающих S-D-линию (красный). Окончательный путь маршрутизации показан синим цветом.

Жадная пересылка может завести в тупик, где нет соседа ближе к месту назначения. Затем маршрутизация лиц помогает выйти из этой ситуации и найти путь к другому узлу, где жадная пересылка может быть возобновлена. Стратегия восстановления, такая как маршрутизация лица, необходима, чтобы гарантировать, что сообщение может быть доставлено адресату. Комбинация жадной переадресации и прямой маршрутизации была впервые предложена в 1999 году под названием GFG (Greedy-Face-Greedy).[6] Это гарантирует доставку в так называемой сетевой модели с единичным дисковым графом. Различные варианты, которые предлагались позже[7], также для графов неединичного диска, основаны на принципах GFG.[1]

Маршрутизация граней в целом зависит от плоского подграфа; однако распределенная планаризация затруднительна для реальных беспроводных сенсорных сетей и плохо масштабируется в трехмерных средах. [8]

Жадное вложение

Хотя изначально они были разработаны как схема маршрутизации, в которой используются физические позиции каждого узла, алгоритмы географической маршрутизации также применялись к сетям, в которых каждый узел связан с точкой в ​​виртуальном пространстве, независимо от его физического положения. Процесс поиска набора виртуальных позиций для узлов сети, при котором географическая маршрутизация с использованием этих позиций гарантированно будет успешной, называется жадное вложение.[9]

Смотрите также

Рекомендации

  1. ^ а б Рюхруп, Стефан (2009). Лю; Чу; Люн (ред.). Теория и практика географической маршрутизации (PDF). Одноранговые и сенсорные беспроводные сети: архитектуры, алгоритмы и протоколы. Bentham Science.
  2. ^ Takagi, H .; Клейнрок, Л. (март 1984 г.). «Оптимальные диапазоны передачи для случайно распределенных пакетных радиотерминалов». Транзакции IEEE по коммуникациям. 32 (3): 246–257. CiteSeerX  10.1.1.64.9747. Дои:10.1109 / TCOM.1984.1096061.
  3. ^ Финн, Грегори Г. (март 1987 г.). «Проблемы маршрутизации и адресации в крупных межсетевых сетях городского масштаба» (PDF). Университет Южной Калифорнии, ISI / RR-87-180. Цитировать журнал требует | журнал = (помощь)
  4. ^ Стойменович, Иван (2002). «Маршрутизация на основе позиции в специальных сетях». Журнал IEEE Communications. 40 (7): 128–134. CiteSeerX  10.1.1.6.6012. Дои:10.1109 / MCOM.2002.1018018.
  5. ^ Стойменович, Иван; Линь, Сюй (2001). «Беспетлевые гибридные алгоритмы однонаправленной маршрутизации / лавинной маршрутизации с гарантированной доставкой для беспроводных сетей». Транзакции IEEE в параллельных и распределенных системах. 12 (10): 1023–1032. CiteSeerX  10.1.1.67.7527. Дои:10.1109/71.963415.
  6. ^ Бозе, П.; Морен, П.; Стойменович, И .; Уррутия, Дж. (1999). «Маршрутизация с гарантированной доставкой в ​​одноранговых беспроводных сетях». Proc. 3-го международного семинара по дискретным алгоритмам и методам мобильных вычислений и коммуникаций (DIALM '99). С. 48–55. Дои:10.1145/313239.313282.
  7. ^ Дженури, Джамель; Баласингем, Илангко (2011). «Модульная локализованная маршрутизация QoS на основе дифференциации трафика для беспроводных сенсорных сетей». IEEE Transactions по мобильным вычислениям. 10 (6): 797–809. Дои:10.1109 / TMC.2010.212. S2CID  11139687.
  8. ^ Ким, Y; Рамеш Говиндан; Карп, Брэд .; Скотт Шенкер (2005). «О ловушках географической разводки поверхностей». Труды совместного семинара 2005 г. по основам мобильных вычислений. С. 34–43. Дои:10.1145/1080810.1080818.
  9. ^ Рао, Анант; Ратнасами, Сильвия; Пападимитриу, Христос Х.; Шенкер, Скотт; Стойка, Ион (2003), «Географическая маршрутизация без информации о местоположении», Proc. Девятый ACM по мобильным вычислениям и сетям (MobiCom), стр. 96–108.