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

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

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

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

Стратегия подхода GF заключается в постоянной передаче сообщения соседу, обеспечивающему максимальный прогресс на пути к точке назначения. Аналогичным образом алгоритм GRIC также максимизирует прогресс в выбранном направлении. Однако это направление не всегда ориентировано на точку назначения; это идеальное направление с точки зрения прогресса, которое может быть вычислено согласно одной из двух возможных стратегий – режима инерции или режима восстановления, описанных ниже. Наконец, было обнаружено, что эффективность оказывается выше в присутствии слегка нестабильных сетей, как демонстрирует результат 4; поэтому в случае высокой стабильности графа коммуникаций рекомендуется использовать рандомизированную версию алгоритма GRIC, в которой вершины, собирающиеся принять решение о маршрутизации, случайным образом помечают каждую исходящую беспроводную связь как пассивную или активную. Для передачи сообщения могут использоваться только активные беспроводные связи, при этом статус связи пересматривается каждый раз, когда принимается новое решение о маршрутизации. Было обнаружено, что для практических целей хорошо подходит пометка связей активными с вероятностью p = 0,95 [12].

Идея режима инерции заключается в том, что сообщению необходим мощный стимул для движения к точке назначения, но этот стимул должен быть смягчен для того, чтобы следовать по направлению текущего движения, «как небесное тело в планетной системе...» [12]. В режиме инерции сообщения движутся вблизи периметра дыр в маршрутах и препятствий, чтобы в конечном итоге обойти их и спланировать маршрут к точке назначения. Для реализации режима инерции необходимо сделать одно дополнительное предположение: сенсорные узлы должны знать положение узла, из которого они получают сообщение. Это может быть достигнуто, например, за счет фиксации односкачковой истории маршрутизации в заголовке сообщения. Зная свою собственную позицию p, точку назначения сообщения и предыдущее положение сообщения в одном скачке от себя, сенсорный узел может вычислить векторы vcur и vdst, начинающиеся в позиции p и указывающие в направлении текущего движения и в направлении точки назначения сообщения, соответственно. Режим инерции определяет идеальное направление прогресса, vidl, как вектор, начинающийся в точке p и направленный «примерно посередине» между векторами vcur и vdst. Более точно, пусть a – единственный угол в диапазоне [—ж, ж[, такой, что vdst получается в результате поворота vcur на угол a, тогда вектор vidl получается в результате поворота vcur на угол a', где a' = sign(a) • min {^, |a|}. Наконец, сообщение жадным образом переадресуется к соседнему узлу, обеспечивающему максимальный прогресс в вычисленном идеальном направлении прогресса ущ.