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

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

Результат 1. В отсутствие препятствий дыры в маршрутах обходятся при любой плотности сети: процент успеха близок к 100% в случаях, когда исходная точка и точка назначения тесто связаны друг с другом. Маршрутизация является эффективной с точки зрения длины маршрутов.

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

Существуют мощные альтернативы алгоритму GRIC, такие как широко известные протоколы гарантированной доставки GFG [ ], GPSR [ ] и GOAFR [ ]. Эти протоколы основываются на этапе планаризации, выполняемом, например, при помощи протокола обнаружения перекрестных ссылок (CLDP) [9]. LCR подразумевает значительные издержки на поддержку топологии сети, которые со временем могут быть амортизированы в случае достаточно высокой стабильности сети. Напротив, при высокой динамичности сети необходимость частых обновлений делает затраты на поддержку топологии неприемлемо высокими. Таким образом, GRIC может быть самым практичным вариантом для динамических сетей с нестабильной структурой графа коммуникаций.

(1) Сложные вогнутые объекты, наподобие представленного на рис. 1d, по-прежнему представляют серьезную проблему для облегченных протоколов, поскольку в этой конфигурации эффективность GRIC напрямую зависит от плотности сети. (2) Низкая и очень низкая плотность сети порождает проблемы в присутствии крупных препятствий, даже если они оказываются «простыми» и выпуклыми, как на рис. 1b. (3) Задача, относящаяся к случаю трехмерных сетей, остается открытой. Инерция отчасти помогает делу, однако виртуальный компас и правило правой руки жестко привязаны к двумерной плоскости. (4) GRIC не свободен от циклов. Для практических задач очень нужен механизм выявления циклов или слишком длинных маршрутов. (5) Работа GRIC недостаточно изучена. Не имеется аналитических результатов, можно также рассмотреть такие новые метрики, как срок жизни сети, потребление энергии или перегрузка по трафику.