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

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

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

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

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