Математическое и программное обеспечение представления и обработки данных о мобильных объектах в реляционных СУБД

Актуальность темы

Любой существующий объект располагается где-нибудь и в какой-нибудь точке времени. В динамично развивающемся мире пространство является особенностью, которая изменяется с течением времени. За последние годы мобильность стала важным фактором человеческой жизни. Интернет, беспроводные сети, GPS технологии, мобильные телефоны и весь спектр услуг, предоставляемых с ними, совершенствуются с каждым днем. Все эти технологии стали доступны для разных слоев населения. Общей целью технологий и услуг является удовлетворение растущих ожиданий потребителей. Для достижения этой цели информация должна быть своевременно предоставлена в правильном месте. Сейчас предоставление услуг, соответствующих времени, стало очень важным и зависит от местонахождения потребителей мобильных устройств. Предоставление такого рода информации позволит потребителям устройств лучше ориентироваться в пространстве, чтобы получить необходимые услуги и определить возможные проблемы (например, дорожные пробки). Основной аспект в мобильности — объект, местоположение которого изменяется, т. е. мобильный объект (МО). В реальной жизни существует много приложений, которые используют этот аспект (городское движение, наблюдения миграций животных, анализ поведения покупателей (в торговых и городских центрах), местонахождение пациента в больнице, расположение таких услуг как туристические, рекламные, скорой помощи и т. д.). Несмотря на некоторый прорыв в удовлетворении спроса потребителей на информационное сопровождение таких услуг, при их создании все еще остается много нерешенных аспектов. Одним из таких аспектов является отсутствие стандартной базы данных (БД) для мобильных объектов и услуг. Универсальным средством для хранения структурированной информации являются базы данных, работающие под управлением систем управления базами данных (СУБД). Из них наибольшее распространение получили реляционные СУБД (РСУБД), которые обладают мощным декларативным языком описания запросов для поиска информации (SQL) и способны выполнять запросы, не предусмотренные изначально при создании структуры базы данных.

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

Но РСУБД традиционно ориентированы на работу с элементами числовых, символьных и временных типов данных, имеющими простую внутреннюю структуру, занимающими небольшой объем памяти и позволяющими эффективно выполнять над этими данными поисковые и вычислительные операции. Информационные же системы, работающие с данными о местонахождении МО, должны иметь особую форму хранения по сравнению с обычными базами данных, так как должны оперировать с данными в форме многообразных, непрерывных, быстро изменяющихся во времени потоков. Однако, хотя подобные системы уже нашли практическое применение, теория их построения еще не разработана в должной степени.

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

Цель и задачи исследования

Целью диссертационной работы является разработка и исследование модельного, алгоритмического и программного обеспечения для хранения и обработки данных о МО в реляционных СУБД.

Для достижения поставленной цели исследования необходимо решить следующие задачи:

1. Проведение сравнительного анализа существующих методов представления сведений о мобильных объектах и манипулирования ими в реляционных БД.

2. Разработка и исследование методов, алгоритмов и моделей для представления данных и обработки запросов о непрерывных траекториях движения МО и нахождении объектов в заданных областях с помощью традиционных БД.

3. Разработка и исследование методов и средств для решения прогнозных задач вида: «Найти МО, которые возможно пересекут заданную область через определенный интервал времени».

4. Создание средств для имитационного исследования разработанного модельного и алгоритмического обеспечения и проведение такого исследования.

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

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

1. Алгоритм представления непрерывной траектории МО по дискретным точкам съёма координат, отличающийся минимизацией «мертвого (потерянного, не допускающего восстановления) пространства» путем уменьшения размеров параллелепипедов, аппроксимирующих отрезки траекторий МО, позволяющий с большей эффективностью осуществлять запись сведений о МО в БД.

2. Модель представления МО (МПМО) в БД, отличающаяся сочетанием векторного, статического, пространственного и динамического временного подходов. Оригинальность модели заключается в специальном разбиении координатного пространства на пространственную и временную составляющие, когда каждый МО имеет статическое и динамическое временное представление. МПМО состоит из: двухуровневого метода доступа, реализующего МПМО, отличающегося поддержкой всех типов запросов о прошлом и настоящем местонахождении МО и позволяющего уменьшить рост объема индексации путем избегания индексации повторяющихся траекторий МО и восстановления полной траектории МО. Это позволяет уменьшить объем требуемой для хранения данных об МО памяти до 30% и уменьшить время реализации запроса на 20−30%- способа организации хранения сведений о мобильных объектах в БД, отличающегося использованием аппарата таблиц и индексов СУБД, элементами иерархической организации данных, существующими типами и операциями, и двухъярусной моделью обработки запроса в СУБД, что делает модель применимой с любыми СУБД.

3. Математическая модель представления фигуры неопределенности, содержащей возможные траектории объектов, движущихся в ограниченных сетях, и разработанные алгоритмы обработки пространственно-временных диапазонных запросов с учетом неопределенности. Это позволяет отыскивать не только те МО, которые точно пересекают область запроса, но и объекты, которые возможно пересекают эту область. Тем самым подтверждается факт расширения возможностей существующих средств.

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

5. Комплекс вычислительных программ для обработки данных о мобильных объектах (КВПМО) и специальное программное обеспечение, с помощью которых проведена проверка работоспособности предложенных алгоритмов, их имитационное исследование, и результаты этого исследования.

Практическая значимость результатов работы. Практическая значимость диссертационной работы заключается в обеспечении возможности использования дискретных реляционных СУБД для хранения и обработки информации о непрерывных траекториях мобильных объектов. Предложенная надстройка в типовых СУБД позволяет использовать их для решения разнообразных задач управления движением транспорта, отслеживать передвижения МО различного вида, контролировать состояние территорий. В предложенном подходе к построению индексов (И±дерево для мобильных объектов, РПМО) достигнута более высокая эффективность реализации по сравнению с ранее применяемыми (Я±дерево и Я-дерево). Например, размер индекса в рассмотренном примере составил 12Мб для РПМО-дерева против 51Мб для Я±дерева и 38Мб для Я-дерева. При этом число опрашиваемых узлов при использовании предложенного РПМО-дерева примерно на 10−15% меньше чем при использовании К±дерева и на 20−30% чем у Я-дерева. Отметим, что некоторые типы запросов ранее были невозможны в принципе. Предложенные алгоритмы реализованы в программном обеспечении «Система мониторинга мобильных объектов в транспортных сетях», переданном на госрегистрацию в Федеральный институт промышленной собственности (ФИПС).

Особенность предложенной модели представления МО в БД состоит в использовании уже имеющихся типов данных и операций. С практической точки зрения это является несомненным достоинством, поскольку предоставляет возможность применения существующих реляционных СУБД, что упрощает реализацию и внедрение предложенных методов.

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

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

Использование разработанного среднеквадратического регрессионного предсказания (СК-предсказания) дает больше достоверных результатов, чем кусочно-линейная модель в ТРБ1-дереве.

Разработанный автором комплекс вычислительных программ для обработки данных о мобильных объектах (КВПМО) является удобным инструментом при использовании поверх СУБД для обработки непрерывных запросов о МО и позволяет получать ответы на запросы в переносных устройствах пользователей.

Он может применяться для предсказания будущих местоположений объектов с использованием регрессии. Комплекс зарегистрирован в федеральном институте промышленной собственности (ФИПС), № 2 009 616 597 от 27.11.09 г.

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

Реализация и результаты внедрения. Основные теоретические и практические результаты работы приняты к использованию в управлении пассажирских перевозок мэрии г. Новосибирска, сервисном центре Samsung г. Новосибирска, Jordan Telecom Group (Orange) г. Амман, Иордания, в учебном и научном процессе Новосибирского государственного технического университета (НГТУ) и Новосибирского государственного университета (НГУ).

Апробация результатов. Результаты, полученные в диссертационной работе, докладывались на научных конференциях:

Третьем международном форуме по стратегическим технологиям «IFOST» (Новосибирск, 23−29 июня, 2008 г.);

Десятом рабочем международном симпозиуме по информатике и информационным технологиям «CSIT2008» (Турция, Анталия, 15−17 сентября, 2008 г.);

Третьей всероссийской конференции «Винеровские чтения» (Иркутск: ГОУ ВПО ИрГТУ, 11−16 марта, 2009 г.);

Седьмой всероссийской научно-практической конференции студентов, аспирантов и молодых ученых с международным участием «Молодежь и современные информационные технологии» (Томск, ТПУ, 25−27 февраля, 2009 г.);

Пятнадцатой ежегодной международной научно-технической конференции студентов и аспирантов «Радиоэлектроника, Электротехника и Энергетика» (Москва, МЭИ, 26−27 февраля, 2009 г.);

Восьмой международной сибирской конференции ШЕЕ по управлению и связи (81ВС01Ч-2009) (Томск, ТПУ, 27−28 марта, 2009 г.);

Всероссийской научной конференции молодых ученых (Новосибирск, НГТУ, 4−7 декабря, 2008 г.);

Всероссийских научно-практических конференциях «Научная инициатива иностранных студентов и аспирантов российских вузов» II и Ш (Томск, ТПУ, 27−28 апреля, 2008 г. и май 2009 г.), результаты диссертации отмечены дипломами на этих конференциях;

Четвертом международном форуме по стратегическим технологиям «ШОБТ» (г. Хошимин, Вьетнам, 21−23 октября, 2009 г.).

Публикации. По теме диссертации опубликовано 16 научных работ, в том числе: 2 — в изданиях, входящих в перечень рекомендуемый ВАК РФ, 3 — в рецензируемых журналах, 10 — в сборниках трудов конференций и зарегистрирована 1 программа.

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

Список использованных источников

содержит 85 наименований. Кратко изложим основное содержание работы.

4.4.2. Результаты исследования по размеру дерева и стоимости добавления.

Чтобы решить первую задачу: сравнение размера РПМО-дерева, которое индексирует различные числа МО для г. Oldenbourg с размером 3-мерного R и Я±деревьев, были генерированы различные размеры МО (0−2000) на основе цифрового представления реальной дорожной сети Oldenbourg. При этом использовался генератор мобильного объекта, как уже упоминалось в пункте 4.2.1. С использованием программного обеспечения имитации основных алгоритмов РПМО-дерева, R-дерева и R+дерева реализованного на Visual Basic, как уже упоминалось в пункте 4.21., были проиндексированы все траектории сети, затем каждая из трех созданных индексных структур сохранялась в файле в упакованном виде, и после чего вычислялся размер каждой структуры для различного числа МО.

Размер созданных индексных структур показан в табл. 4.2.

Заключение

.

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

1. Разработан новый алгоритм представления непрерывной траектории МО по дискретным точкам съёма координат.

2. Предложена модель представления МО (МПМО) в БД, обеспечивающая при ее реализации уменьшение объема требуемой для хранения данных об МО памяти до 30% и времени реализации запросов на 20−30% по сравнению с ранее используемыми средствами.

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

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

5. Создан программный комплекс обработки данных о мобильных объектах (КВПМО) и специальные программные средства имитационного моделирования, с помощью которых проведена проверка работоспособности и оценена эффективность предложенных алгоритмов.