Алгоритмы устранения ложных и избыточных данных в GPS-потоке
Разработка электроники на базе GPS/ГЛОНАСС-технологий — одна из наших любимых тем на Хабре. Мы уже писали обзорную статью на эту тему, рассказывали про систему «ЭРА-ГЛОНАСС» и даже определяли своё местоположение по сетям сотовой связи.
В этот раз наш пост призван дать ответ на конкретный практический вопрос: «Как уменьшить объем потока данных с навигационно-связных терминалов без потери информативности?». Эта тема весьма актуальна, ведь услуги беспроводной связи составляют значительную часть финансовых затрат на обслуживание систем мониторинга транспорта.
Для начала давайте посмотрим, что представляет собой тракт подготовки и сбора информации на терминалах перед отправкой данных на сервер.На рисунке ниже представлена блок-схема данного процесса:
Этап формирования точки, от момента получения координат с GPS-приемника до момента передачи на сервер, можно разделить на три подготовительных части: стабилизация, фильтрация и прореживание.
Стабилизация и фильтрация — это опциональные этапы, они нужны для исправления несовершенства качества приема GPS-сигнала. Зачастую задачу стабилизации позволяет решить установленный на устройстве акселерометр, а также алгоритм усреднения точек. Таким образом мы избавляемся от так называемых «звезд» на стоянках транспортных средств и можем привязаться к статичной позиции, когда транспортное средство покоится.
Фильтрация предназначена для отслеживания физически невозможных бросков координат. Такая ситуация возникает в кратковременных критических условиях приёма (например под линиями электропередач).
И, наконец, прореживание точек или децимация — самый распространённый и логичный этап в задаче уменьшения объема передаваемых данных, его мы рассмотрим в данной статье.
1. Прореживание точек или децимация в навигационных системахДопустим, что каждая навигационная точка содержит информацию о местоположении транспортного средства, информацию, полученную от датчиков, установленных на борту и какие-либо статусы, характеризующие состояние системы. Обычно информация от GPS-приёмника поступает каждую секунду, т.е. каждую секунду мы имеем сформированный набор данных, который без алгоритма децимации пришлось бы передавать полностью. Эта информация по большей части является избыточной.Если транспортное средство двигалось относительно равномерно по какому-то участку дороги, то мы не потеряем важных данных, если выбросим промежуточные точки. При этом мы сохраним точки на участках, где были резкие изменения навигационных параметров. Ниже приведен пример прореживания точек по такому принципу:
В рамках этого примера мы сэкономили 72% данных в случае со средней степенью прореживания и целых 96% в случае с жесткими условиями прореживания! Как видно, этот простой метод дает колоссальное преимущество в экономии объема памяти.
Но в реальных условиях, когда навигационные данные дополнены информацией от бортовых датчиков, алгоритм немного усложняется, так как возникает необходимость передавать данные ещё и по системным событиям. Поэтому все критерии прореживания можно разделить на группы по приоритетам: системные события («прерывания») и информация о навигационных характеристиках транспортного средства.
К системным можно отнести такие события: включение / выключение питания, установление / потеря соединения со спутниками и т. д. Очевидно, что системные прерывания являются более приоритетными, чем общая информация. Отношения между приоритетностью и важностью информации можно представить следующей блок-схемой:
При выполнении одного из условий, пакет передается дальше на проверку остальных условий либо отправляется в нелинейный буфер. Если ни одно из условий не выполнено, то пакет выбрасывается из потока.
Примерная реализация алгоритма прореживания на языке си может быть следующей:
#define TIME_LIMIT 60 //sec #define HDOP_LIMIT 400 #define DISTANCE_LIMIT 300 //m #define SPEED_LIMIT 4000//km/h #define COURSE_LIMIT 9000 //deg GPS_DATA previous_sample; int GPS_decimator (GPS_DATA * sample) { if (sample→time.sec + sample→time.min*60 + sample→time.hour*3600 — previous_sample.time.sec — previous_sample.time.min*60 — previous_sample.time.hour*3600 > TIME_LIMIT) { return 1; } if (sample→hdop > HDOP_LIMIT) { return 0; } double UTMNorthing; double UTMEasting; double GPS_passed_northing; double GPS_passed_easting; char UTMZone[4]; double la; modf (sample→la/100,&la); la += ((sample→la)-la*100)/60; double lo; modf (sample→lo/100,&lo); lo += ((sample→lo)-lo*100)/60; //convert coordinates to UTM LLtoUTM (la, lo, &UTMNorthing, &UTMEasting, UTMZone); double pla; modf (previous_sample.la/100,&pla); pla += ((previous_sample.la)-pla*100)/60; double plo; modf (previous_sample.lo/100,&plo); plo += ((previous_sample.lo)-plo*100)/60; //convert coordinates to UTM LLtoUTM (pla, plo, &GPS_passed_northing, &GPS_passed_easting, UTMZone); if (sqrt (pow (UTMNorthing-GPS_passed_northing,2)+pow (UTMEasting-GPS_passed_easting,2)) >= DISTANCE_LIMIT) { return 1; } if ((previous_sample.speed — sample→speed)*(previous_sample.speed — sample→speed) >= SPEED_LIMIT*SPEED_LIMIT) { return 1; } if ((previous_sample.course — sample→course)*(previous_sample.course — sample→course) >= COURSE_LIMIT*COURSE_LIMIT) { return 1; } return 0; } В приложении находится полный листинг программы (cpp-файл, 17 КБ). Пример программы носит сугубо демонстрационный характер и в реальных проектах не использовался.2. Использование оптимального протокола передачи данных Второй путь уменьшения объема передаваемых данных — это использование оптимального протокола передачи данных. Для начала выделим два основных типа протоколов: текстовый и двоичный или бинарный.Текстовым протоколом, например, является NMEA, который используется в GPS-приемниках. Для передачи навигационной информации в простейшем случае может быть достаточно передачи RMC-строки данного протокола.
Основные черты текстового протокола:
удобен для визуального восприятия;
один пакет содержит одну путевую точку;
целостность гарантируется контрольной суммой;
имеет фиксированное количество полей в пакете;
данные передаются в открытом виде;
все численные данные необходимо переводить в текстовый вид и обратно;
протокол не предполагает экономии количества байт в пакете.
Пример использования текстового протокола: 
На фото: персональный GPS-навигатор с электронным компасом — давний проект команды инженеров Promwad, один из первых опытов в сфере навигации. Это простое устройство возвращает пользователя в точку старта или заранее отмеченное место на системе координат.
В рамках проекта использовался текстовый протокол NMEA. Аппаратная платформа навигатора была построена на базе электронных компонентов с оптимальными параметрами, чтобы обеспечить низкую себестоимость устройства (на уровне 30 USD при партии от 10 000 шт.). В результате нам пришлось решать интересные задачи по оптимизации алгоритмов расчёта расстояния и направления.
GPS-модуль навигатора отправлял координаты в формате NMEA на микроконтроллер Freescale MC9S08QE8, по ним определялось расстояние и вектор движения до заданной точки. Т.к. объём памяти микроконтроллера был крайне ограничен, мы реализовали преобразование координат в целочисленную форму, при этом погрешность вычислений осталась в допустимых пределах. Подробнее об этой разработке можно прочитать в PDF-файле с техническим описанием проекта.
Второй тип — бинарный протокол, имеет только один недостаток — он неудобен для визуального восприятия без применения специальных средств. Его использование с тем же количеством параметров, что и в текстовом варианте, позволяет сэкономить на объеме данных более чем в два раза с одного пакета.
По бинарному протоколу можно передавать сразу несколько путевых точек и таким образом мы ускоряем процесс передачи данных из буферной памяти и дополнительно экономим байты, идущие на заголовки транспортных пакетов.
Бинарный протокол также позволяет производить аутентификацию устройств на сервере сбора данных и передавать различную сервисную информацию в двухстороннем порядке. Конечно же, некоторые из этих вещей можно передавать и с использованием текстового протокола, но это нецелесообразно.
Ещё одной прекрасной возможностью, которую дает бинарный протокол, является переменная длина пакетов. Благодаря этому устройства с различной конфигурацией периферийных датчиков могут работать в одной системе. Каждый пакет имеет неделимую часть, состоящую из заголовка и навигационной информации — часть, которая является идентификационной, и дополнительные поля с информацией, полученной от датчиков. Причём в каждый момент времени могут быть добавлены только необходимые данные.
На первый взгляд может показаться, что при таком подходе могут возникнуть проблемы со способом хранения этих пакетов в энергонезависимом буфере, но это легко решается алгоритмом хранения информации, точнее выбором структуры хранимых данных. Так различные модели прибора могут работать в одной системе, не нарушая общей концепции.
Итого Полевые испытания и годы эксплуатации систем мониторинга транспорта показали, что метод прореживания является очень успешным подходом к уменьшению объемов трафика и не вносит искажений в исходный трек при грамотном подборе параметров прореживания.Касательно протоколов, в разработке систем мониторинга широко применяются как текстовые, так и бинарные. Как правило, текстовые протоколы используются на более простых устройствах мониторинга с минимальным фиксированным набором интерфейсных датчиков. Эти протоколы легко узнать и распознать их данные.
Более профессиональные модели снабжаются бинарными протоколами, что позволяет повысить безопасность и достоверность данных, а главное — уменьшить объем передачи данных и сэкономить средства на техническом обслуживании системы. Также использование бинарного протокола передачи данных предоставляет бо̀льшие возможности для взаимодействия мобильных навигационно-мобильных терминалов с центром мониторинга (например, можно организовать интерактивную удалённую работу с прибором).
Мы продолжим публиковать статьи про навигацию, так что присоединяйтесь к подписчикам блога Promwad.
