Алгоритмы обхода препятствий в беспроводных сетях датчиков

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

Жадная географическая маршрутизация; дыры в маршрутах

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

Беспроводные сети датчиков состоят из множества небольших устройств, называемых сенсорными узлами и обладающих возможностями вычисления и радиосвязи. Сенсорные узлы обычно развертываются децентрализованным образом и используют свои датчики для сбора данных о состоянии окружающей среды. Получившаяся сеть коллективно обрабатывает, собирает и распространяет данные по исследуемой области – например, из региона, где было зарегистрировано событие, на базовую станцию или мобильному пользователю. Далее будет рассматриваться функция распространения данных по сети датчиков при наличии препятствий.

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

Определение 1 (граф коммуникаций). Беспроводная сеть датчиков рассматривается как граф G = (V, E), вершины которого соответствуют сенсорным узлам, а ребра представляют беспроводные связи между вершинами.

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

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

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

Возможности простой географической маршрутизации

Ранние алгоритмы «пересылки наиболее продвинутому узлу в пределах диапазона» (most forward within range, MFR) или жадной географической маршрутизации [ ] направляли сообщения, исходя из соображений максимизации в процессе каждого скачка продвижения по спроецированной линии на пути к точке назначения – или, напротив, минимизации оставшегося расстояния до точки назначения сообщения. Обе эти жадные эвристики объединяются по общим названием «жадная переадресация» (greedy forwarding, GF). Эта техника маршрутизации выглядит весьма многообещающей для применения в беспроводных сетях датчиков. Этому есть немало причин. (1) Жадная переадресация, как это почти повсеместно требуется, является полностью децентрализованной. (2) Это недорогая техника в том смысле, что она не добавляет расходов на управление топологией. (3) Она обеспечивает коммуникацию типа «все со всеми», а не «все с одним». (4) Благодаря отсутствию предположений о структуре коммуникационного графа, который может быть ориентированным, неориентированным, стабильным или динамическим (например, вершины могут быть мобильными, а беспроводные связи могут появляться и исчезать – скажем, в силу изменений окружающей обстановки или в результате работы более низкий уровней стека протоколов, таких как схемы перехода в спящий режим и выхода из него с целью экономии энергии), техника оказывается весьма надежной. (5) Она работает по запросу: до распространения сообщения не строится таблицы маршрутизации или градиента. (6) Ее эффективность связана с тем, что сообщения находят короткие пути к точкам назначения (в терминах количества скачков). (7) Техника проста и в силу этого удобна для внедрения. (8) Она эффективно использует память в том смысле, что (8а) в заголовке сообщения храниится только информация о точке назначения и (8б) является «экологичной», поскольку в посещаемых сообщением сенсорных узлах не остается «мусорной» информации.

Формулировка задачи

Несмотря на все достоинства техники жадной переадресации, у нее есть серьезный недостаток: если сообщение попадает в локальный минимум, откуда невозможно успешно перейти по направлению к точке назначения, алгоритм маршрутизации прекращает работу. Локальные минимумы появляются в силу двух основных причин: дыр в маршрутах [1] и препятствий.

Определение 2. Так называемые дыры в маршрутах представляют собой области сети с малой плотностью, в которых не имеется сенсорных узлов для следующего скачка.

Даже в сетях с равномерно случайным распределением узлов дыры в маршрутах возникают в результате статистического отклонения плотности узлов. По мере снижения плотности сетей количество дыр растет, однако они серьезно влияют на эффективность GF-алгоритмов даже в сетях с очень высокой плотностью [12].

Определение 3. Препятствие, блокирующее передачу, представляет собой область сети, в которой не имеется датчиков и через которую не распространяется радиосигнал.

Очевидно, что при наличии крупных препятствий между сообщением и точкой его назначения алгоритм GF потерпит неудачу.

Задача заключается в поиске алгоритма географической маршрутизации, который сохранил бы достоинства подхода жадной переадресации, такие как простота, малый вес, устойчивость и эффективность, и при этом не обладал присущими ему недостатками – невозможность миновать узлы локального минимума, создаваемые дырами в маршрутах и крупными препятствиями, блокирующими передачу – такими как примеры на рис. 1.

Задача 1 (обход дыр в маршрутах). Первая задача заключается в выводе сообщения из множеств дыр в маршрутах, статистически неизбежно возникающих даже в плотных сетях.

Задача 2 (картирование препятствий). Вторая задача заключается в разработке протокола, способного направлять сообщения в обход крупных препятствий, блокирующих передачу.

Задачу 1 можно рассматривать как упрощенную версию задачи 2. Ранее были предложены облегченные решения для задачи 1, обычно использующие ограниченные функции обратной трассировки [6] или управляемого заполнения в сочетании с эвристиками жадной переадресации (GF) [4,13]. Однако, как было показано в работе [ ], в которой была предложена интегрированная модель для обхода препятствий и выполнено сравнение разных алгоритмов с точки зрения их способности к такому обходу, эти решения не способны удовлетворительно справиться с задачей 2, так как они эффективно обходят только небольшие и простые препятствия.

Основные результаты

В работе [12] был предложен новый алгоритм географической маршрутизации в обход препятствий (geographic routing around obstacles, GRIC), предназначенный для решения вышеописанных задач.

Основная идея алгоритма