Адаптивный алгоритм обработки потока навигационных данных на основе метода диагностической фильтрации

СПИСОК ЛИТЕРАТУРЫ

1. Integration Definition For Information Modeling (IDEF1X) // Federal Information Processing Standards Publication 184. - 1993. -147 p.

2. Дейт К. Введение в системы баз данных. - Киев: Диалектика, 1998. - 781 с.

3. Сибилев В.Д., Тимаков А.О. Концепции автоматизированного управления курсовым проектом по дисциплине «Базы данных» // Доклады Томского гос. ун-та систем управления и радиоэлектроники. Т. 2. Автоматизированные системы обработки информации, управления и проектирования: Сб. науч. трудов. - Томск: Изд-во Том. гос. ун-та систем управления и радиоэлектроники, 2001. - С. 29-38.

4. Красиков И.А. Автоматизированная проверка курсовых работ по дисциплине базы данных // Проблемы и перспективы образования в России: Матер. X Междунар. научно-практ. конф. - Новосибирск, 2011. - С. 97-102.

5. Романенко А.В. Контроль знаний в электронных обучающих комплексах // Доклады Томского гос. университета систем управления и радиоэлектроники. Ч. 1. Технические науки: Сб. науч. трудов. - Томск: Изд-во Том. гос. ун-та систем управления и радиоэлектроники, 2007. - С. 34-39.

6. Вендров А.М. CASE-технологии. Современные методы и средства проектирования информационных систем // ЦИТ форум. 2012. URL: http://citforum.ru/database/case/ (дата обращения:

07.12.2012).

7. Красиков И.А. Коммуникативные и методологические проблемы обучения студентов проектированию баз данных // Тестирование в сфере образования: проблемы и перспективы развития: Матер. III Всероссийской научно-практ. конф. с междунар. участием. - Красноярск, 2010. - С. 186-190.

8. Маклаков С. Проверка качества модели данных с помощью ERwin Examiner // Журнал «КомпьютерПресс». 2012. URL: http://compress.ru/Article.aspx?id=9437 (дата обращения:

07.12.2012).

9. Кузнецов С. Развитие логических моделей данных // ЦИТ форум. 2012. URL: http://citforum.ru/database/artic-

les/ref_vs_nav_models/. (дата обращения: 07.12.2012).

10. Пушников А.Ю. Введение в системы управления базами данных. Ч. 2. Нормальные формы отношений и транзакции. -Уфа: Изд-во Башкирского ун-та, 1999. - 138 с.

11. Кузнецов С. Базы данных: достижения и перспективы на пороге XIX столетия // ЦИТ форум. 2012. URL: http://citfo-rum.ru/database/classics/nfs_report/ (дата обращения:

07.12.2012).

12. Геловани В.А., Башлыков А.А., Бритков В.Б., Вязилов Е.Д. Интеллектуальные системы поддержки принятия решений в нештатных ситуациях с использованием информации о состоянии природной среды. - М.: Эдиториал УРСС, 2001. - 304 с.

13. Павлов С.Н. Системы искусственного интеллекта. В 2-х частях. Ч. 1. - Томск: Эль Контент, 2011. - 176 с.

Поступила 18.07.2012 г.

УДК 004.421

АДАПТИВНЫЙ АЛГОРИТМ ОБРАБОТКИ ПОТОКА НАВИГАЦИОННЫХ ДАННЫХ НА ОСНОВЕ МЕТОДА ДИАГНОСТИЧЕСКОЙ ФИЛЬТРАЦИИ

С.А. Хруль, Д.М. Сонькин

Томский политехнический университет E-mail: siberianodis@gmail.com

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

Ключевые слова:

Фильтрация навигационных данных, методы фильтрации данных, мобильные объекты, спутниковая навигационная система. Key words:

Filtering navigation information, data fitering methods, mobile objects, navigation system.

Современным системам спутникового мониторинга подвижных объектов, использующим терминальное оборудование на мобильных объектах, необходима высокая достоверность принимаемых навигационных данных, достигнуть которой без использования различных алгоритмов обработки принимаемой информации не представляется возможным. Одним из решений, позволяющим повысить достоверность и уменьшить объем навигационной информации, передаваемой пользователю, является фильтрация ложных и избыточных данных, полученных от ГЛОНАСС^Р8 модуля,

входящего в состав аппаратуры мобильного терминала [1].

GPS/ГЛОНАСС модуль принимает сигналы со спутников и после их обработки формирует сообщение, включающее ряд параметров о состоянии мобильного объекта, а также навигационную информацию. Производители GPS/ ГЛОНАСС-приемников используют различные алгоритмы окончательной обработки спутниковых сигналов, а также различные протоколы и форматы передачи навигационных сообщений терминалу. Наиболее распространённым форматом является NMEA-

протокол, который включает следующую информацию: Т - время по Гринвичу; р - широта в градусах; Я - долгота в градусах; h - эллипсоидная высота; PDOP, VDOP, HDOP - факторы потери точности в пространстве, по высоте, по горизонтали соответственно; A - статус достоверности (1 - достоверны; 0 - не достоверны); M- режим позиционирования (0 - сигнал отсутствует; 1 - доступно только время; 2 - двухмерный режим позиционирования; 3 - трехмерный режим позиционирования).

Необходимость предварительной обработки и фильтрации данных, полученных непосредственно с навигационных приемников, обусловлена множеством причин, среди которых наиболее значимы:

• проблемы, связанные с питанием навигационного устройства (например, временное обесточивание терминала или сильные электростатические помехи на аппаратуру терминала);

• «холодный старт» приемника движущегося мобильного объекта;

• помехи отраженного сигнала на антенну ГЛО-НАСС^РБ модуля;

• изменение условий приема сигналов со спутников (проезд в условиях плотной городской застройки, въезд в туннель или лесистую/горную местность, сложные метеорологические условия).

Использование фильтрации в системах мониторинга мобильных объектов позволяет значительно уменьшить объёмы обрабатываемой информации с сохранением ее достоверности. Фильтрация заключается в исключении избыточных данных, не приносящих значимых изменений о положении объекта, а также отсеве выбросов, которые приводят к искажениям данных и ошибкам в определении местоположения [6].

Под выбросами понимаются ошибочные данные не отражающие реальную ситуацию, которые были получены в результате технической ошибки аппаратуры, входящей в состав мобильного терминала или алгоритмической ошибки ГЛО-НАСС^РБ модуля.

Можно выделить несколько типов выбросов:

• Хаотичный. Наблюдается при движении на малых скоростях или при стоянке на одном месте в течение непродолжительного времени. Появление таких ошибок объясняется помехами отраженных сигналов спутников от высотных зданий или других объектов. На карте данная ситуация отображается как дрейф (неравномерный разброс) предполагаемого местонахождения.

• Грубый (неконтролируемый сдвиг). Возникает в случае длительной стоянки автотранспортного средства на одном месте. Представляет собой движение в некотором направлении с постоянным ускорением в течение продолжительного интервала времени. Распознать такие выбросы на карте можно по характерному мгновенному (резкому) скачку из последней предполагаемой

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

• Систематический. Обусловлен изменением условий приема сигналов со спутников. Систематические выбросы заключаются в некотором отклонении по одному или нескольким параметрам, в том числе координат местонахождения. В отличие от хаотичных выбросов, ошибка в определении координат сопровождается снижением встроенных показателей точности в получаемых навигационных данных.

Наличие любого типа выброса в полученных навигационных данных отрицательно влияет на точность и своевременность отображения объекта на карте, а также отрицательно сказывается на расчете контрольных показателей (пройденного пути, средней скорости движения и продолжительности стоянки, расхода топлива и т. д.) [7].

Например: мобильный терминал неподвижного объекта выдает координаты местонахождения, беспорядочно разбросанные в радиусе 20...30 м (рис. 1). При этом система рассматривает их как движение, и постепенно происходит увеличение пробега. В результате складывается ситуация, что пробег за несколько часов стоянки увеличивается на 200.800 м.

Рис. 1. Пример навигационных выбросов от неподвижного объекта

Фильтрацию навигационных данных можно разделять на аппаратную, выполняемую ГЛО-НАСС^Р8 модулем, и программную, выполняемую программным обеспечением терминала [1]. Аппаратная фильтрация заключается в анализе шумов и искажений сигналов со спутников и последующую их обработку с помощью цифровых математических фильтров, уникальных для каждой модели приемника. Программная фильтрация выполняется на терминале или диспетчерском центре и заключается в окончательном отсеве навигационных данных, полученных с навигационного модуля, с применением статистических алгоритмов сглаживания, учете показаний установленных на мобильном объекте датчиков, встроенных фак-

торов потери точности позиционирования и других аналитических методов. В случае транспортных средств такими датчиками могут быть: реле зажигания, датчик работы двигателя, датчик вращения колеса и другие. Благодаря их использованию мобильный терминал обрабатывает навигационную информацию от ГЛОБАСС^РБ модуля только после срабатывания датчиков, тем самым, исключая грубые выбросы.

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

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

Существующие методы фильтрации данных, используемые в системах спутникового мониторинга, основаны на значениях встроенных факторов точности позиционирования (HDOP, VDOP, PDOP), а также срабатывания датчиков, установленных на мобильном объекте.

Для решения задачи фильтрации навигационных данных известны статистические методы фильтрации, включающие математические алгоритмы сглаживания (фильтр Калмана, метод наименьших квадратов, правило 3-х сигм, медианный фильтр), а также критерии для отброса выбросов данных (критерий Грабса, критерий Шовене, критерий Пирса, Q-тест Диксона) [2-4].

В случае, когда количество последовательных выбросов не велико, применение различных алгоритмов сглаживания позволяет добиться высокой точности навигационных данных о местоположении объекта. В ситуации, когда последовательные выбросы образуют целую «пачку» алгоритмы сглаживания не справляются (низкая точность), поэтому необходимо применение методов, способных отбрасывать ошибочную информацию (рис. 2) [3, 5].

Как видно из рисунка, рассмотренные алгоритмы сглаживания плохо реагирует на наличие выбросов и не справляются с выбросами в конце исследуемого промежутка.

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

Рис. 2. Фильтрация данных с помощью алгоритмов сглаживания

Также для методов сглаживания необходимо хранение данных, полученных на предыдущих периодах. Чем больше хранимой информации, тем точнее окажутся сглаженные данные (точнее известна модель поведения). Стоит заметить, что объем хранимой выборки ограничен встроенной в терминальное оборудование памятью, поэтому сохранение большого количества навигационных данных не возможно. Также отметим, что сам процесс сглаживания достаточно трудоемкий и выполняется на мобильном терминале в течение относительно длительного времени, что приводит к ситуации, когда невозможно своевременно обрабатывать вновь поступающую информацию.

Проанализировав существующие подходы к решению задач фильтрации, было принято решение объединить их и дополнить диагностическими методами.

Предлагаемое решение можно разделить на 3 этапа:

1. Этап. Предварительный отсев:

На данном этапе осуществляется фильтрация данных, которые с большой долей вероятности являются ошибочными. Отсев осуществляется по следующим критериям:

• количество видимых спутников меньше допустимого значения;

• режим позиционирования не соответствует выбранному режиму;

• данные по показаниям статуса достоверности не валидны;

• значения встроенных факторов точности позиционирования больше допустимых значений;

• скорость движения превышает максимально допустимую для данного типа мобильных объектов (например: для транспортных средств - 300 км/ч, для морского судна - 100 км/ч);

• Также скоростной характеристикой может яв-

ляться максимальное моментальное ускорение движения (например: для транспортных

средств - 6 м2/с, для морского судна - 3 м2/с).

Таблица 1. Значения характеристик исследуемых мобильных объектов

Тип объекта ^сутки ^ср. Vmax Тф.стоян Тдвиж. ^стоянок <3 ср. amax аср.торм. amax торм.

СМП 1 118,8 29 75,2 13,6 6,46 25 0,207 1,305 0,2 1,1

СМП 2 146,7 27,7 95,6 15,2 7,06 8 0,233 1,31 0,18 0,7

ГПТ 1 204,7 25,6 70 3,06 12,2 9 0,16 1,19 0,17 1,21

ГПТ 2 241,4 23,6 65,1 1,34 13,09 7 0,118 0,91 0,116 1,17

СЛА 1 35,28 51,1 88,1 44 2,3 10 0,3 1,57 0,26 2,75

СЛА 2 27 41,5 95 150 2,01 5 0,331 1,95 0,29 2,48

2. Этап. Диагностическая фильтрация:

В качестве критерия фильтрации используется расстояние между двумя точками, которое должно быть не меньше порогового значения Dlmit. Графически это представлено на рис. 3.

\ / ч /

Рис. 3. Иллюстрация к алгоритму диагностической фильтрации

Радиус окружности (сферы в случае использования высоты) соответствует пороговому значению Dlimit и вычисляется на основе точности позиционирования, которая зависит от значений факторов потери точности в текущий момент:

Dlimit = HDOP*HFactor+VDOP*VFactor, где HFactorи VFactorсоответствующие коэффициенты для DOP в метрах, далее просто коэффициенты.

Рекомендовать строго определенные коэффициенты нельзя, поскольку точность позиционирования зависит не только от качества сигналов со спутников, но и от типа приемника. В общем виде, диапазон рекомендуемых значений можно определить как 5...15 м для HDOP, 10.29 м для VDOP.

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

Рассмотрим более подробно характеристики исследуемых мобильных объектов (табл. 1) на примере различных транспортных средств, где СМП 1, 2 - автомобили скорой медицинской помощи; ГПТ 1, 2 - автобусы городского пассажирского транспорта; СЛА 1, 2 - служебные легковые авто-

мобили; 5су1хи - пройденный путь за сутки, км; Кср. -средняя скорость движения, км/ч; ¥шк - максимальная скорость движения, км/ч; Гсрс1оян. - средняя продолжительность стоянки, мин.; 7^™. - продолжительность движения в сутки, час; 0стоянок - количество стоянок продолжительностью более 5 мин.; -ср. - среднее значение ускорения, м/с2; -

максимальное значение ускорения, м/с2; аср.торм. -среднее значение ускорения торможения, м/с2; -шхторм. - максимальное значение ускорения торможения, м/с2.

Таким образом, исходя из табл. 1, можно сделать вывод, что при фильтрации данных для различного класса мобильных объектов требуется индивидуальный подбор значений параметров алгоритма (табл. 2).

Таблица 2. Результаты экспериментов за сутки для различных объектов и индивидуальные значения критериев

Тип объекта Значения критерия Период исследования, сутки Частота сообщений, в минуту Число точек Изменение количества точек, %

SpeedLimit HFactor VFactor до фильтрации после фильтрации

СМП 1 12 20 15 1 6 2422 744 69,3

СМП 2 12 20 15 14 6 62577 14758 76,4

ГПТ 1 8 15 12 5 6 28248 19203 32,1

ГПТ 2 8 15 12 7 6 42101 20134 52,3

СЛА 1 15 20 15 1 60 21037 790 96,3

СЛА 2 15 20 15 3 6 3761 1790 52,4

3. Этап. Сглаживание данных:

Необходимость сглаживания объясняется тем, что мобильный объект движется плавно, с постепенным изменением направления движения. Благодаря сглаживанию можно добиться реалистичного отображения пути передвижения, а также получить более точные значения пройденного расстояния (рис. 4).

Таким образом, разработан адаптивный алгоритм обработки навигационного потока данных, позволяющий уменьшить объем передаваемых данных и повысить их достоверность (рис. 5).

Основными достоинствами разработанного метода обработки данных являются:

• возможность работы в режиме реального времени (возможность применения алгоритма

в программном обеспечении мобильного терминала);

Рис. 4. Пример использования сглаживания

• простота исполнения (с точки зрения времени и трудозатрат оборудования на выполнение) алгоритма, а значит возможность использования маломощных и недорогих микроконтроллеров в составе аппаратуры мобильного терминала;

• значительное уменьшение потока данных для любого типа наблюдаемого объекта и его характера движения, вследствие чего снижение нагрузки на канал передачи между диспетчерским центром и мобильным объектом;

• улучшение точности производных параметров (путь, скорость, время движения и др.) вследствие отсева выбросов.

Пример работы адаптивного алгоритма обработки навигационных данных в системе мониторинга транспорта приведен на рис. 6.

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

Выводы

1. Предложен адаптивный алгоритм обработки навигационных данных на основе метода диагностической фильтрации.

2. Отличительной особенностью алгоритма является динамическое вычисление порогового значения Dlmit (расстояние для определения смещения объекта) на основе данных о точности позиционирования (значений факторов потери точности в текущий момент времени) и типа объекта.

3. Разработанный адаптивный алгоритм обработки потока навигационных данных на основе метода диагностической фильтрации позволяет исключать недостоверные и избыточные данные для передачи в диспетчерский центр. В зависимости от типа объекта (характеристик его движения) поток данных уменьшается на

Рис. 5. Схема адаптивного алгоритма обработки потока навигационных данных

Рис. 6. Пример использования адаптивного алгоритма фильтрации навигационных данных в системе мониторинга транспорта: а) до применения алгоритма; б) после применения алгоритма фильтрации

30.50 % для городского пассажирского транспорта, служебных легковых автомобилей и на 50.70 % для выездных бригад скорой медицинской помощи.

4. В отличие от известных подходов предложенный алгоритм подходит для работы в режиме реального времени, обеспечивая заданную точность.

СПИСОК ЛИТЕРАТУРЫ

1. Владимиров В.М., Гречкосеев А.К., Толстиков А.С. Имитатор измерительной информации для отработки эфемеридно-вре-менного обеспечения космической навигационной системы ГЛОНАСС // Измерительная техника. - 2004. - № 8. -С. 12-14.

2. Кошаев Д.А. Многоальтернативный метод обнаружения и оценки нарушений на основе расширенного фильтра Калма-на // Автоматика и телемеханика. - 2010. - № 5. - С. 70-83.

3. Hang Guo, Min Yu, Chengwu Zou, Wenwen Huang. Kalman filtering for GPS/magnetometer integrated navigation system // Advances in Space Research. - 2010. - № 45. - P. 1350-1357.

4. Brilingaite A., Jensen C. Online Route Prediction for Automotive Applications // Proc. of the XIIIth World Congress and Exhibition on

Intelligent Transport Systems and Services. - London, October 2006. - P. 168-175.

5. Шестаков Н.А. Позиционирование объектов в дорожной сети в системах мониторинга городского транспорта // Проблемы информатики. - 2011. - № 5. - С. 159-166.

6. Глобальная спутниковая радионавигационная система ГЛО-НАСС // под ред. В.Н. Харисова, А.И. Перова, В.А. Болдина. -М.: ИПРЖР, 1998. - 400 с.

7. Харисов В.Н., Яковлев А.И., Глущнко А.Г. Оптимальная фильтрация координат подвижного объекта // Радиотехника и электроника. - 1984. - Т. 23. - № 7. - С. 1441-1452.

Поступила 09.10.2012 г.