4511
правок
Алгоритмы обхода препятствий в беспроводных сетях датчиков: различия между версиями
Перейти к навигации
Перейти к поиску
Алгоритмы обхода препятствий в беспроводных сетях датчиков (посмотреть исходный код)
Версия от 20:16, 16 июля 2019
, 16 июля 2019→Формулировка задачи
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Жадная географическая маршрутизация; дыры в маршрутах == П…») |
Irina (обсуждение | вклад) |
||
| Строка 25: | Строка 25: | ||
== Формулировка задачи == | == Формулировка задачи == | ||
Несмотря на все достоинства техники жадной переадресации, у нее есть серьезный недостаток: если сообщение попадает в локальный минимум, откуда невозможно успешно перейти по направлению к точке назначения, алгоритм маршрутизации прекращает работу. Локальные минимумы появляются в силу двух основных причин: дыр в маршрутах [1] и препятствий. | |||
'''Определение 2.''' Так называемые дыры в маршрутах представляют собой области сети с малой плотностью, в которых не имеется сенсорных узлов для следующего скачка. | |||
Даже в сетях с равномерно случайным распределением узлов дыры в маршрутах возникают в результате статистического отклонения плотности узлов. По мере снижения плотности сетей количество дыр растет, однако они серьезно влияют на эффективность GF-алгоритмов даже в сетях с очень высокой плотностью [12]. | |||
'''Определение 3.''' Препятствие, блокирующее передачу, представляет собой область сети, в которой не имеется датчиков и через которую не распространяется радиосигнал. | |||
Очевидно, что при наличии крупных препятствий между сообщением и точкой его назначения алгоритм GF потерпит неудачу. | |||
Задача заключается в поиске алгоритма географической маршрутизации, который сохранил бы достоинства подхода жадной переадресации, такие как простота, малый вес, устойчивость и эффективность, и при этом не обладал присущими ему недостатками – невозможность миновать узлы локального минимума, создаваемые дырами в маршрутах и крупными препятствиями, блокирующими передачу – такими как примеры на рис. 1. | |||
'''Задача 1 (обход дыр в маршрутах).''' Первая задача заключается в выводе сообщения из множеств дыр в маршрутах, статистически неизбежно возникающих даже в плотных сетях. | |||
'''Задача 2 (картирование препятствий).''' Вторая задача заключается в разработке протокола, способного направлять сообщения в обход крупных препятствий, блокирующих передачу. | |||
Задачу 1 можно рассматривать как упрощенную версию задачи 2. Ранее были предложены облегченные решения для задачи 1, обычно использующие ограниченные функции обратной трассировки [6] или управляемого заполнения в сочетании с эвристиками жадной переадресации (GF) [4,13]. Однако, как было показано в работе [ ], в которой была предложена интегрированная модель для обхода препятствий и выполнено сравнение разных алгоритмов с точки зрения их способности к такому обходу, эти решения не способны удовлетворительно справиться с задачей 2, так как они эффективно обходят только небольшие и простые препятствия. | |||
== Основные результаты == | |||
В работе [12] был предложен новый алгоритм географической маршрутизации в обход препятствий (geographic routing around obstacles, GRIC), предназначенный для решения вышеописанных задач. | |||
'''Основная идея алгоритма''' | |||