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