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

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

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