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