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

Идея режима инерции заключается в том, что сообщение должно иметь твердое намерение двигаться к точке назначения, но это намерение должно быть смягчено для того, чтобы следовать по направлению текущего движения, «как небесное тело в планетной системе...» [12]. В режиме инерции сообщения движутся вблизи периметра дыр в маршрутах и препятствий, чтобы в конечном итоге обойти их и спланировать маршрут к точке назначения. Для реализации режима инерции необходимо сделать одно дополнительное предположение: сенсорные узлы должны знать положение узла, из которого они получают сообщение. Это может быть достигнуто, например, за счет фиксации односкачковой истории маршрутизации в заголовке сообщения. Зная свою собственную позицию p, точку назначения сообщения и предыдущее положение сообщения в одном скачке от себя, сенсорный узел может вычислить векторы <math>v_{cur}</math> и <math>v_{dst}</math>, начинающиеся в позиции p и указывающие в направлении текущего движения и в направлении точки назначения сообщения, соответственно. Режим инерции определяет идеальное направление прогресса, <math>v_{idl}</math>, как вектор, начинающийся в точке p и направленный «примерно посередине» между векторами <math>v_{cur}</math> и <math>v_{dst}</math>. Более точно, пусть <math>\alpha</math> – единственный угол в диапазоне <math>[ - \pi, \pi [</math>, такой, что <math>v_{dst}</math> получается в результате поворота <math>v_{cur}</math> на угол <math>\alpha</math>, тогда вектор <math>v_{idl}</math> получается в результате поворота <math>v_{cur}</math> на угол <math>\alpha'</math>, где <math>\alpha' = sign(\alpha) \cdot min \Big\{ \frac{\pi}{6}, |\alpha| \Big\} </math>. Наконец, сообщение жадным образом переадресуется к соседнему узлу, обеспечивающему максимальный прогресс в вычисленном идеальном направлении прогресса <math>v_{idl}</math>.

Для повышения эффективности работы алгоритма в целом и для обхода сложных препятствий режим восстановления имитирует правило правой руки (right-hand rule, RHR) – хорошо известную технику следования вдоль стены для выхода из лабиринта. Схематичное описание RHR-компонента алгоритма GRIC приведено ниже, полное изложение можно найти в работе [12]. В контексте GRIC компонент RHR использует виртуальный компас и флаг. Виртуальный компас присваивает вектору <math>v_{cur}</math> значение кардинальной точки, считая точку назначения сообщения находящейся на севере. Рассматривая угол <math>\alpha</math>, определенный выше, компас возвращает строку x-y, где x соответствует северу или югу, если <math>| \alpha |</math> меньше или больше <math>\pi / 2</math>, соответственно, а y соответствует востоку или западу, если <math>\alpha</math> является отрицательным или положительным, соответственно. В первый раз, когда компас возвращает значение «юг», флаг поднимается и помечается значением (x, y) компаса. Поднятие флага обозначает направление сообщения в обход препятствия по правилу RHR, если компас указывает на юго-восток. Симметричный случай, когда компас указывает на юго-запад, здесь не рассматривается; в этом случае взамен RHR будет использоваться аналогичное правило левой руки (left-hand rule, LHR). После поднятия флага он остается поднятым, а его пометка неизменной до тех пор, пока компас не укажет на север, что говорит о том, что обход препятствия завершен. Можно слегка оптимизировать процесс, опуская флаг только тогда, когда компас указывает на северо-восток (при использовании RHR), а не на северо-запад; подробнее об этом – в [12]. Согласно правилу RHR, следует двигаться в тесной близости к периметру препятствия и держаться правой стороны относительно текущего направления движения сообщения. В случае расхождения пометок компаса и флага, например, если флаг помечен значением «юго-восток», а компас выдает значение «юго-запад», считается, что сообщение слишком сильно ушло влево, рискуя уйти от препятствия и нарушить правило правой руки (симметричный подход применим к правилу левой руки). В этом случае алгоритм GRIC переходит в режим восстановления, в котором изменяется принятый по умолчанию способ вычисления vidl: в режиме восстановления сообщение принудительно поворачивается направо (налево в случае применения правила LHR) путем определения <math>v_{idl}</math> как вектора, полученного поворотом <math>v_{cur}</math> на угол <math>\alpha ''</math> (вместо применяемого в режиме инерции <math>\alpha '</math>), где <math> \alpha '' = - sign(\alpha)(2 \pi - | \alpha |)/6</math>.