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

Для повышения эффективности работы алгоритма в целом и для обхода сложных препятствий режим восстановления имитирует правило правой руки (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>.

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

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