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

Методология маршрутизации для беспроводных сетей

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

Подходы

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

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

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

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

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

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

• Список протоколов маршрутизации ad hoc
• Маршрутизация обратного давления

Ссылки

1. Ruehrup, Stefan (2009). Liu; Chu; Leung (ред.). Теория и практика географической маршрутизации (PDF) . Ad Hoc и сенсорные беспроводные сети: архитектуры, алгоритмы и протоколы. Bentham Science.
2. Takagi, H.; Kleinrock, L. (март 1984). «Оптимальные диапазоны передачи для случайно распределенных пакетных радиотерминалов». IEEE Transactions on Communications . 32 (3): 246–257. CiteSeerX 10.1.1.64.9747 . doi :10.1109/TCOM.1984.1096061. 
3. Финн, Грегори Г. (март 1987 г.). «Проблемы маршрутизации и адресации в крупных городских интернет-сетях» (PDF) . Университет Южной Калифорнии, ISI/RR-87-180.
4. Стойменович, Иван (2002). «Маршрутизация на основе позиции в одноранговых сетях». Журнал коммуникаций IEEE . 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 . doi :10.1109/71.963415. 
6. Бозе, П.; Морин , П .; Стойменович, И.; Уррутия, Дж. (1999). «Маршрутизация с гарантированной доставкой в ​​беспроводных сетях ad hoc». Труды 3-го международного семинара по дискретным алгоритмам и методам для мобильных вычислений и коммуникаций (DIALM '99) . стр. 48–55. doi : 10.1145/313239.313282 .
7. Дженури, Джамель; Баласингхам, Илангко (2011). «Локализованная маршрутизация с модульным QoS на основе дифференциации трафика для беспроводных сенсорных сетей». Труды IEEE по мобильным вычислениям . 10 (6): 797–809. doi :10.1109/TMC.2010.212. S2CID  11139687.
8. Ким, Y; Рамеш Говиндан ; Карп, Брэд.; Скотт Шенкер (2005). «О подводных камнях географической маршрутизации лица». Труды совместного семинара 2005 года по основам мобильных вычислений . стр. 34–43. doi :10.1145/1080810.1080818.
9. Рао, Анант; Ратнасами, Сильвия; Пападимитриу , Христос Х.; Шенкер, Скотт ; Стоика, Ион (2003), «Географическая маршрутизация без информации о местоположении», Труды 9-й конференции ACM по мобильным вычислениям и сетям (MobiCom) , стр. 96–108.