Алгоритмы обхода препятствий в беспроводных сетях датчиков: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 55: | Строка 55: | ||
'''Основная идея алгоритма''' | '''Основная идея алгоритма''' | ||
Стратегия подхода 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|}. Наконец, сообщение жадным образом переадресуется к соседнему узлу, обеспечивающему максимальный прогресс в вычисленном идеальном направлении прогресса ущ. | |||
'''Режим восстановления''' | |||
[[Файл:OAA_WSN.png]] | [[Файл:OAA_WSN.png]] | ||