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



003490193

На правах рукописи

Алынаер Джавдат Джамиль

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

В РЕЛЯЦИОННЫХ СУБД

• / /

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

* 4 ЯН3 2Ш

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Новосибирск - 2009

003490193

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования «Новосибирский государственный технический университет»

Научный руководитель доктор технических наук, профессор

Губарев Василий Васильевич

Официальные оппоненты-, доктор технических наук, с.н.с.

Родионов Алексей Сергеевич,

доктор технических наук Ярославцев Александр Федорович

Ведущая организация Институт систем информатики имени А.П. Ершова СО РАН, г. Новосибирск

Защита состоится «21» января 2010 г. в 16-00 часов на заседани диссертационного совета Д 212.173.06 при Государственном образовательно учреждении высшего профессионального образования «Новосибирски" государственный технический университет» по адресу: 630092, Новосибирск пр. К. Маркса 20

С диссертацией можно ознакомиться в библиотеке Государственного образовательного учреждения высшего профессионального образована «Новосибирский государственный технический университет».

Автореферат разослан «18 » декабря 2009 г.

Ученый секретарь

диссертационного совета

Чубич В.М.

Общая характеристика работы

Актуальность темы. Любой существующий объект располагается где-нибудь и в какой-нибудь точке времени. За последние годы мобильность стала важным фактором человеческой жизни. Интернет, беспроводные сети, GPS технологии, мобильные телефоны и весь спектр услуг, предоставляемых с ними, совершенствуются с каждым днем. Для поддержки оказания этих услуг информация должна быть своевременно предоставлена в правильном месте.

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

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

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

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

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

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

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

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

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

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

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

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

> двухуровневого метода доступа, реализующего МПМО, отличающегося поддержкой всех типов запросов о прошлом и настоящем местонахождении МО и позволяющего уменьшить рост объема индексации путем избегания индексации повторяющихся траекторий МО и восстановления полной траектории МО. Это позволяет уменьшить объем требуемой для хранения данных об МО памяти до 30% и уменьшить время реализации запроса на 20-30 %;

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

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

4. Подсистема моделирования движения для обработки нетрадиционных запросов, включающая:

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

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

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

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

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

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

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

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

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

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

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

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

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

третьем международном форуме по стратегическим технологиям «IFOST» (Новосибирск, 23-29 июня, 2008 г.); десятом рабочем международном симпозиуме по информатике и информационным технологиям «CSIT'2008» (Турция, Анталия, 15-17 сентября, 2008г.); третьей всероссийской конференции «Винеровские чтения» (Иркутск: ГОУ ВПО ИрГТУ, 11-16 марта, 2009 г.); седьмой всероссийской научно-практической конференции студентов, аспирантов и молодых ученых с международным участием «Молодежь и современные информационные технологии» (Томск, ТПУ, 25-27 февраля, 2009 г.); пятнадцатой ежегодной международной научно-технической конференции студентов и аспирантов «Радиоэлектроника, Электротехника и Энергетика» (Москва, МЭИ, 26-27 февраля, 2009 г.); восьмой международной сибирской конференции IEEE по управлению и связи (SIBCON-2009) (Томск, ТПУ, 27-28 марта, 2009 г.); всероссийской научной конференции молодых ученых (Новосибирск, НГТУ, 4-7 декабря, 2008 г.); всероссийских научно-практических конференциях «Научная инициатива иностранных студентов и аспирантов российских вузов» II и III (Томск, ТПУ, 27-28 апреля, 2008 г. и май 2009 г.), результаты диссертации отмечены дипломами на этих конференциях; четвертом международном форуме по стратегическим технологиям «IFOST» (г. Хошимин, Вьетнам, 21-23 октября, 2009 г.).

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

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

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

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

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

Краткое содержание работы

Модель представления

Система определения местоположения МО

мобильных объектов (МПМО) в БД. Средства

Спутник

ГНС

- индексации отрезков ТПЯРКТППИЙ МО.

Мобильные Объекты (МО)

\

•ч А

Рис. 1. Система мониторинга мобильных объектов в транспортных сетях

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

Обсуждены смешанные и детализированные запросы. Смешанные - это запросы, в которых по одной из координат х, у или ? запрос является одной разновидностью, а по другой (другим) - другой разновидностью из того же класса. Например, точечный (х,,у,) по плоскости и интервальный (?,',?') по времени.

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

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

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

Во второй главе автором предложены основные модели для представления сведений о МО в БД. Структура (состав и связи) известных и предложенных средств показана на рис. 21.

Предложен алгоритм построения отрезков траекторий МО, в котором МО

посылает дискретные координаты точек (р1,р2.....р„) своего местоположения

серверу в системе координат(х,у, О, где х,у- пространственные координаты, ? -время, то есть р,-(г) = />[■*(',•), у (',•)]- точка на траектории Тв момент времени = . Траектория твыстраивается из отрезков г, = [/>,-,РмЬ Из координат местоположения объекта р,, = р(дг,-,>',-,г!)Д = 1 -Сможет быть построено различное число т = 1—( N — 1) отрезков.

Траектории Т из т отрезков записывается в виде кортежа

Т=1л.....гтМ=[Р1'Р2].....»"т=[ри,рт+1], •■•.'ЛГ-1 =(РлГ-1.Ря)-

Для индексации отрезков предлагается аппроксимировать их минимальным ограничивающим параллелепипедом (МОП). МОП является самым маленьким параллелепипедом, охватывающим отрезок траектории МО, все стороны которого параллельны осям координат (х,у,г)(см. рис. 3).

' Подсистемы, разработанные автором, выделены цветом.

8

Если В1 - МОП, охватывающий отрезок /](г\)), то МОП, охватывающий траекторию В(Т), обозначим как мажорирующий В({ Ы_1) = В1.....ВЛМ.

Рис. 2. Структура средств представления МО в БД

Каждый отрезок имеет ряд ограничительных характеристик (направление, скорость и т.д.). Отрезки должны выбираться с минимальным МОП для снижения «мертвого» (потерянного, не допускающего восстановления) пространства согласно алгоритму, приведенному на рис. 3.

Рис. 3. Алгоритм построения отрезков траекторий мобильных объектов Для индексации полученных отрезков автором предложен метод доступа, который базируется на Я+-дереве и называется РПМО-деревом. Алгоритм дерева был использован в предложенном методе индексации ввиду того, что

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

Основная идея метода заключается в разделении объемного (по координатам (х,у,0) отрезка траектории МО на линейные временные отрезки, пронумерованные с помощью 1-мерного Я+-дерева (назовем его временным) и пространственного (х,у) 2-мерного Я+-дерсва для индексации координат этих отрезков.

^ Каждый листовой узел в пространственном дереве содержит индексную запись вида: (МОП, идентификатор кортежа траекторного отрезка в БД, ссылка), где МОП - это координаты (х',у'),(х",у'),(х',у'),(х*,у") либо (/,/;*',/), при ориентации МОП вдоль координатных осей, а ссылка указывает на корень временного дерева, индексирующего моменты времени начала и конца отрезка, на котором находится интересующий нас МО.

> Не листовые узлы пространственного дерева, так же как в Я-дереве, содержат записи вида: (ссылка к дочернему узлу (потомку), МОП), где ссылка указывает на узел низшего порядка в пространственном дереве, а МОП - координаты вершин охватывающего параллелепипеда, который содержит все параллелепипеды в дочерних узлах.

> Каждый листовой узел временного дерева содержит индексную запись вида: (ссылка на траекторный отрезок, идентификатор МО в БД, временной интервал движения (/,, (2), направление движения).

> Не листовые узлы временного дерева содержат записи вида: (ссылка к дочернему узлу (потомку), временной интервал (ВИ)), где ссылка указывает на узел низшего порядка в временном дереве, а ВИ-начало и конец интервала,

охватывающего все интервалы в дочерних узлах.

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

^Начало

Рис. 4. Блок-схема алгоритма вставки объекта в РПМО-дерево

траектории, а второй - на следующий. МО добавляется в БД и индексируется РПМО-деревом с использованием алгоритма добавления Я+-дсрева (см. рис. 4).

Обработка запроса, например, вида: «Найти все объекты, находящиеся в определенной окрестности» или «Найти все объекты, содержащие в себе определенную область», реализуется с помощью операции поиска. Алгоритм поиска в РПМО-дереве проиллюстрирован на рис. 5 (предполагается, что ищется объект в РПМО-дереве с пространственно-временным окном запроса

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

Рис. 5. Блок-схема алгоритма поиска объекта в РПМО-дереве

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

определения отношения между отрезком траектории МО (который содержится в МОП) и окном запроса (например, Equals, Contains, Crosses и др.).

МПМО реализуется через двухъярусную модель запроса, на каждом из которых выполняется два типа отличных действий (пространственное и временное): 1) пространственные действия выполняются для расчёта отношения между параллелепипедами отрезка траектории МО и пространственной фигурой окна запроса; 2) временные действия выполняются для определения отношения между временными координатами движения и временным окном запроса.

Для представления местоположения МО между двумя точками предложена модель описания неопределенности, учитывающая максимальную, среднюю и минимальную скорости объекта при допустимой величине их отклонения. При помощи услуг GPS в некоторых заранее определенных точках каждый МО знает своё точное текущее положение. Мобильный объект может двигаться с максимально допустимой скоростью va=(vax,vay), которая сохранена как

характерное свойство объектов в БДМО. МО обязан посылать серверу БД по коммуникационному каналу сведения о своем местоположении по прохождении допустимого расстояния, не превышающего МО посылает также сведения о своем местоположении всякий раз, когда разница между текущей скоростью МО и последней сообщенной скоростью превышает некоторое допустимое значение разности скоростей yf = (\//x,y/y). Тогда мажоритарное представление геометрической фигуры, охватывающей неопределенность вокруг проекций траектории движения МО по осям движения х, у, можно представить как на рис. 6, на котором результаты измерений представлены точками р^ и р2 на траектории Т в моменты времени ^ и (2. Во время tl положение МО определяется точно как точка: p\={p[,pi) со скоростью движения v1=(v1',v'). После этого объект может пройти расстояние до точки р2 со скоростью по каждой из координат в пределах от наименьшей vml„ = max(\l-iy,0) до наибольшей возможной \<max = min(vl+ iff, va), где va — наибольшая максимально допустимая правилами скорость. Тогда, в случае линейного движения МО в одном направлении, минимально удаленное от точки /)[ положение объекта во время г, г, < t < г2,/>,ш„(г)по каждой из координат и максимально удаленное от точки pi положение объекта во время t, Pmaxit) вычисляются (на примере оси х), если vx и vy > 0, следующим образом:

Соотношения (1) и (2) дают фигуру, изображенную на рис 6. Заштрихованная часть рисунка отражает множество возможных положений МО между двумя точками pi и р2 за время / е [tifo]. Назовем эту область вокруг траектории Тотpt доР2 фигурой неопределенности (ФН) U для Тс допустимыми ограничениями у/). Заметим, что объект может осуществлять движение от р/ до Р2 в пределах ФН без необходимости отправки сведений об обновлениях скорости или местоположения, так как допустимые ограничения у/ и f не были превышены. Мажорирующая фигура неопределенности состоит из возможных отрезков движения {а, Ь, с, d, е, /} и следующих траекторий {abc, def}.

Разработаны различные новые операторы интервальных запросов с учётом неопределенности для определения, какие объекты (возможно или точно) находились в заданной неопределенной области в течение некоторого заданного интервала времени, например, оператор МОЖЕТ БЫТЬ-ИНОГДА-ВНУТРИ (МИВ). Запрос, реализуемый данным оператором, истинен, если существует возможный отрезок движения а и существует время / е [г,, Г2 ] такие, что МО во время t находится в области R (см. рис. 7). Логическая форма для функции оператора определена в виде [(За), а е U] л [(Bf), t е , f2)] => a s U п R, или сокращенно (За) л (3r) =>aeUr\R. Все предложенные операторы демонстрируются рис. 8.

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

Согласно модели КА, отрезок разделен на ячейки, которые могут быть пустыми либо занятыми только одним МО. Рис. 9 показывает пример КА-модели отрезка транспортной сети.

Пусть движение осуществляется только вперед. Определим местоположение (интервал перемещения х ) транспортного средства (ТС) числом

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

Рис. 7. Графическое изображение истинности оператора МИВ

ячеек позади него, т.е. от начального узла (начальная точка отрезка движения ТС) до МО, включая ячейку, где находится МО. Допустим, что каждое ТС имеет

целочисленную неотрицательную скорость V, которую условно представим отрезком пути, определяющим перемещение МО вперед за 1 такт времени (от г до г+1), т.е. числом ячеек, помещаемых впереди ТС (как бы пройденных МО в следующем временном периоде от г до ?+1). Пусть I- ТС, двигающееся по отрезку 1 длины его

скорость*,* ;(г)- его

положение (на рис. 9 уа(<) = 3,ха(1) = 2 И / = 13 ВО время /),.$,■ (г)- число пустых ячеек перед ТС до лидирующего ТС (допустимая скорость движения). На рис. 9 (0 =4 и ^(/ + 1) = 3, р-вероятность изменения

скорости транспортного

средства, утш- максимальная скорость на отрезке. Для каждого интервала времени (от г до / + 1) возможны следующие ситуации

движения для всех ТС: а) движение без изменения скорости; б) движение с изменением скорости', ускорение достижения максимальной

ПОСТОЯННО-ТОЧНО-ВНУТРИ (ПТВ)

Конец

Рис. 8. Блок-схема алгоритмов обработки всех интервальных запросов с учетом неопределенности

когда ТС намерен ускориться вплоть до скорости, или торможение, когда транспортное средство позади другого транспортного средства обязано замедлиться, поскольку если V,-(Г + 0)Дг >[(I + Дг>—л:,-(г)], ТО + = в) случайные

возмущения, связанные с заторами, пробками, авариями и т.п. Для ситуации в)

' Для упрощения полагаем скорость движения на каждом участке постоянной. В противном случае ее можно заменить на среднюю скорость.

14

необходимо ввести фактор случайности для каждого МО, задаваемый вероятностями их наступления /?,- (г), которые могут быть одинаковыми или разными для всех МО на отрезке.

¡+1 5=4 у=3

5=2 у=3

¡1

¡>3

у=4

0 1 2 3 4 5 6 7 8 9 1011 12

5=4

у=3

5=2 у=2

5>3

1+0

0 1 2 3 4 5 6 7 8 9 1011 12 5=3 5>4

у^З у=2

1+1

0 12 3

а)

Ь)

4 5 6 7

с)

8 9 1011 12

Рис. 9. Моделирование состояния дорожного движения с использованием клеточных автоматов: а) схематическое изображение дорог; Ь) моделируемый элемент изображения; с) отображение смены состояний КА - моделью

Для получения аналитического выражения функции движения мобильных объектов в диссертации предложен метод обработки запросов о предсказании местонахождения МО с применением линейной регрессией (см. рис. 10).

Дорога

i

+

- • - Траектории МО

Прямая средне® адратшеской регрессии_

С

тс

Рис. 10. Диаграмма рассеяния и прямая регрессии для точек траектории МО

Пусть последовательность точек ¡ = 1,..., N=1 -И есть выборочные

значения координат точек расположения МО в момент времени Г, на расстоянии с1,

15

от начала пути, Ти 1- их средние значения. При близкой к линейной функция, описывающая траекторию движения объекта, аппроксимируется средне-квадратической прямой регрессией <1 (/) = Д0 + Дг, где Д> и Д равны

А Р, = 1>, -г/.

Обработка запросов в МПМО иллюстрируется на рис. 11.

+

Конец 3

Рис. 11. Блок-схема алгоритма обработки непрерывных запросов и запросов предсказания с использованием имитации и регрессий

В четвертой главе рассмотрена реализация модели представления мобильных объектов в рамках Oracle и его расширения Oracle Spatial.

В первой части главы дается краткое описание используемых операторов Oracle Spatial. Например, используя модель МПМО, можно управлять пространственно-временными (ПВ) данными различными способами, чтобы приспособиться к приложению. Так для запроса «Найти объекты, которые были в пределах области 0.4-0.8 по х и 0.6-0.8 по у в течение интервала от 0.5 до 20 с», запрос SQL может иметь следующую форму:

SELECT object_id FROM moving_objects WHERE seg_id IN SELECT segment_id from road_segments

WHERE SDO_RELATE(segment_geom,SDO_GEOMETRY(2003, NULL, NULL,

SDO_ELEM_INFO_ARRAY(l,1003,3), SDO_ORDINATE_ARRAY(4,6, 8,8)), 'mask=inside1) = 'TRUE'

AND SDO_RELATE(time_period, SDO_GEOMETRY(1002, NULL, NULL, SDO_ELEM_INFO_ARRAY (1,2,1), SDO_ORDINATE_ARRAY (5,20) , 'mask=inside1) = 'TRUE'.

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

Далее в этой главе рассмотрена экспериментальная проверка алгоритмов предложенного РПМО-дерева. Было создано программное обеспечение, реализованное на Visual basic.

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

Далее описываются технологии и результаты имитационных экспериментов. Первый эксперимент - сравнение размера РПМО-дерева, которое индексирует различное количество МО для г. Oldenbourg с размером 3-мерного R и Я+-дсревьев. Второй - определить насколько увеличивается количество узлов, которые необходимо обработать при выполнении добавлений в РПМО-дереве, по сравнению с R-деревом и 3-мерным Я+-дерсвом. Третий - определить как возрастет количество узлов, которые необходимо проверить при выполнении поиска в РПМО-дереве, по сравнению с поиском в R-дереве и 3-мерном R+-дереве.

На рис. 12 представлено сравнение предложенных алгоритмов РПМО-дерева с другими алгоритмами по среднему числу г опрашиваемых узлов при различных отношениях по пространству и времени.

Для подтверждения достоверности результатов справа на рисунках приведены отношения оценки среднеквадратического отклонения (СКО) результатов к их среднему значению. Результаты экспериментов подтвердили, что при большом числе МО предложенное РПМО-дерево имеет лучшие показатели по выполнению запроса и обновлению данных, чем R и R+деревья. Например, размер индекса в рассмотренном примере составил 12Мб для РПМО-дерева против 51Мб для Я+-дерева и 38Мб для R-дерева. При этом число опрашиваемых узлов при использовании РПМО-дерева примерно на 10-15% меньше, чем при

использовании Я+-дерева, и ещё на столько же меньше, чем у И-дерева. Отметим, что некоторые типы запросов ранее были невозможны в принципе.

а)

РПМО-дерево

Отношение д/х R-depeeo (0.6-6.6)% R+-depeeo (0.5-5.7)% РПМО-дерево (1-3)% 1% площади, 10% времени.

500 750 1000 1250 1500 1750 2000 Число мобильных объектов

Ь)

-R-дерево

R+дерево —РПМО-дерево

140

1000

(7 / X

Отношение R-дерево (0.9-2.5)% R+-depeeo (1.3-4.2)% РПМО-дерево (0.4-2.4)% 1 % площади, 100% врешни. 2000

Число мобильных объектов

Рис. 12. Зависимость среднего числа опрошенных узлов от числа мобильных объектов при разных запросах: а) диапазонные запросы с 1 % от площади и с 10 % от временного интервала; Ь) диапазонные запросы с 1 % от площади и с 100 % от временного интервала

Для того, чтобы оценить насколько расширяются возможности существующих средств с введением новых запросов, проведено экспериментальное исследование отношения числа MN МО, сведения о которых мы при этом получим для каждого момента времени Г, к числу Мт объектов, сведения о которых мы получаем при традиционных запросах, т.е. у=МN / Мт.

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

Наконец, был выполнен эксперимент для эмпирического подтверждения работоспособности предложенного метода регрессионного предсказания. Результаты, полученные по 200 экспериментам, подтверждают, что использование СК-регрессионного линейного предсказания в нашей модели дает больше достоверных результатов, чем кусочно-линейная модель в TPR-дереве (см. рис. 14), на котором по оси ординат изображено в процентах отношение

5 =

-хр\/хр, где

среднее, найденное по 200 экспериментам, прогнозное значение, полученное ¡-ым (/ = 1,2) методом, а хр - среднее значение настоящей траектории МО.

м

а)

■ мив ■ МПВ

в ТИВ ■ НТВ = традиционные

■ Традиционные = ШБ

число объектов

Ь)

-^-мпв

-ж- Традиционные = ПТВ

ТИВ

ПТВ = традиционные

7

10 8 • 6 ■ 4 ■ 2 ■ 0 ■

100

200

-Ж-

300

Отношение О / У МП В (0.4-2.6)% МПВ (0.2-2.1)% ТИВ (0.4-1.3% ПТВ (0.1-1.1% Традиционный (0.2-1.5)%

400

500 Число обьектов

Рис. 13. Иллюстрация расширения возможностей поиска введением новых запросов: а) зависимость числа Мц от числа МО при традиционных и новых запросах; Ь) зависимость отношения у = М дг / Мт от числа МО при разных

запросах

В Заключении сформулированы основные результаты работы, выносимые на защиту.

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

Линейные предсказания Регрессия

16 14 12 10 8

6 4 2 О

: уА Отношение а / д

ЛГ \ т . .г-

-— Траектории МО (5-17.8)%

— Регрессия (8-19.5)%

Линейные предсказания (7.5Л ¡3.7)%

10 20 30 40 50 60 70 80 90 100 »'ч

Рис 14. Реальные и предсказанные траектории МО

Основные результаты работы

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

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

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

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

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

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

Список публикаций по теме диссертации Публикации в изданиях, рекомендованных ВАК РФ

1. Альшаер Д.Д. Обработка запросов в базе данных мобильных объектов / Д.Д. Альшаер, Губарев В.В. // Известия Томского политехнического университета. -Томск : Изд-во ТПУ, 2009,- Т. 314.-№ 5. - С. 166-170.

2. Альшаер Д.Д. Применение дискретных баз данных для хранения и поиска сведений о непрерывном движении мобильных объектов / Д.Д. Альшаер, В.В. Губарев // Научный вестник НГТУ -Новосибирск : Изд-во НГТУ, 2009 - № 2(35).-С. 61-73.

Научные статьи в сборниках и конференциях

3. Альшаер Д.Д. Модель представления траекторий мобильных объектов в базах данных / Д.Д. Альшаер, В.В. Губарев // Доклады Академии наук высшей школы России .-Новосибирск : Изд-во НГТУ, 2009.-№ 2(13). - С. 66-75.

4. Альшаер Д.Д. Пространственно-временные базы данных: проблемы и решения. 4.1 / Д.Д. Альшаер, В.В. Губарев // Сборник научных трудов НГТУ-Новосибирск : Изд-во НГТУ, 2007.- № 2(48). - С. 33-38.

5. Альшаер Д.Д. Пространственно-временные базы данных: проблемы и решения. 4.2 / Д.Д. Альшаер, В.В. Губарев // Сборник научных трудов НГТУ. -Новосибирск: Изд-во НГТУ, 2007.-№3(49). - С. 129-132.

6. Альшаер Д.Д. Обработка запросов в базе данных мобильных объектов (БДМО) / Д.Д. Альшаер, В.В. Губарев // Радиоэлектроника, Электротехника и Энергетика: материалы XV ежегодной международной научно-технической конференции студентов и аспирантов. -Москва : Изд-во МЭИ, 2009. -Т. 1. - С. 323-324.

7. Альшаер Д. Д. Проблема неточности в базе данных мобильных объектов / Д.Д. Альшаер, В.В. Губарев // Наука. Технологии. Инновации : материалы всероссийской научной конференции молодых ученых в 7 частях. -Новосибирск : Изд-во НГТУ, 2008. - Ч. 1. - С. 183-185.

8. Альшаер Д.Д. Построение и индексирование траекторий мобильных объектов / Д.Д. Альшаер, В.В. Губарев // Винеровские чтения : материалы 3-й Всероссийской конференции, Иркутск, 2009 г. [Электронный ресурс]. - ГОУ ВПО ИрГТУ, 2009. - № 4. - 1 электрон, опт. Диск (CD-ROM, RR035).

9. Альшаер Д.Д. Индексация траекторий мобильных объектов с использованием R-дерева / Д.Д. Альшаер, Т.А. Сливка, В.В. Губарев // Молодежь и современные информационные технологии : материалы 7 всероссийской научно-практическая конференции студентов, аспирантов и молодых ученых с международным участием. - Томск : Изд-во ТПУ, 2009. - 4.1. - С. 11-12.

10. Альшаер Д.Д. Обработка непрерывных запросов о мобильных объектах с использованием имитаций / Д.Д. Альшаер, В.В. Губарев // Научная инициатива иностранных студентов и аспирантов российских вузов : материалы II Всероссийской научно-практической конференции. - Томск : Изд-во ТПУ, 2009,- С. 34-38.

11.Alshaer J. J. Indexing moving objects on transportation networks / J. J. Alshaer, V. V. Gubarev // The 3-rd International forum on strategic technologies (IFOST),

Novosibirsk, Russia : proceeding. - NSTU, 2008,- P. 249-252.[Индексация мобильных объектов в транспортных сетях ]

12.A]shaer J. J. Intelligent Traffic Management System / Jawdat J. Alshaer, Vasily V. Gubarev // International Siberian Conference on Control and Communications (SIBCON-2009), The Tomsk IEEE Chapter & Student Branch, Tomsk, Russia: proceeding. - TPU, 2009. - P. 15—20. [ Интеллектуальная Система мониторинга мовильнных объектов]

13. Alshaer J. J. Storing, Indexing and Simulating movements on transportation networks / J. J. Alshaer, V. V. Gubarev // Proceedings of the 10th International Workshop on Computer Science and Information Technologies (CSIT'2008), Antalya, Turkey, State Aviation Technical University : UFA, 2008. -Vol. 1. - P. 169-174.[Сохранение, индексации и имитации движения в транспортных сетях]

14.Alshaer J. J. Managing moving objects on transportation networks / J. J. Alshaer, V. V. Gubarev // The 3rd International forum on strategic technologies IFOST , Novosibirsk, Russia : proceeding. - NSTU, 2008. - P. 253-257.[Управление мобильными объектами в транспортных сетях]

15. Alshaer J. J. Model for Indexing and Processing Moving Objects Information / J. J. Alshaer, V. I. Guzhov, К. H. Jo // The 4th International forum on strategic technologies (IFOST), Ho Chi Minh, Vietnam, Ho Chi Minh University of Technology: proceeding. - Ho Chi Minh : City Publishing House, 2009. - P. 154— 156. [Модель для индексации и обработки информации о мобильных объектах]

Зарегистрированные программы

16. Альшаер Д.Д. Комплекс вычислительных программ для обработки данных о мобильных объектах (КВПМО) / Д.Д. Альшаер // федеральный институт промышленной собственности (ФИПС), свидетельство об официальной регистрации программы для ЭВМ №. 2009616597 от 27.11.09 г.

Отпечатано в типографии Новосибирского государственного Технического университета 630092, г. Новосибирск, пр. К. Маркса, 20, тел./факс: (383) 346-08-57 формат 60x84 1\16, объем 1.5 п.л., тираж 100 экз. заказ № 135 подписано в печать 18.12.09 г.

ВВЕДЕНИЕ.

ГЛАВА 1. ОСОБЕННОСТИ ПРОСТРАНСТВЕННО-ВРЕМЕННЫХ СИСТЕМ.

1.1 Вводные замечания.

1.2. Система определения местоположения мобильных объектов

1.2.1. Принцип работы ГНС.

1.2.2. Точность определения координат.

1.3. Базы данных и системы управления ими.

1.4. Краткая характеристика мобильных объектов.

1.5. Поддержка пространственных объектов в современных РСУБД.

1.5.1. Хранение пространс твенных данных в БД и манипулирование ими.

1.5.2. Логическая структура БД, таблицы и индексы.

1.5.3. Физическая структура БД, файлы данных и индексов.

1.5.4. Обработка запросов, содержащих условия поиска записей, и методы ее оптимизации.

1.5.5. Индексирование пространственных данных для оптимизации операций над ними.

1.6. Анализ особенностей и проблем пространственно-временных систем.

1.6.1. Новые типы пространственно-временных запросов.

1.6.2. Нетрадиционные методы доступа и обработки: непрерывные запросы.

1.6.3. Неопределенности при обработке «неточных» данных.

1.7. Обзор существующих исследований об определении координат мобильных объектов.

3 1.7.1. Обзор существующих методов доступа к данным о мобильном объекте.

1.7.2. Существующая теоретическая модель представления мобильных объектов в БД.

1.7.3. Обзор существующих исследований по проблеме неточности определения координат МО.

1.8. Постановка задачи исследования.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Он может применяться для предсказания будущих местоположений объектов с использованием регрессии. Комплекс зарегистрирован в федеральном институте промышленной собственности (ФИПС), № 2009616597 от 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. Создан программный комплекс обработки данных о мобильных объектах (КВПМО) и специальные программные средства имитационного моделирования, с помощью которых проведена проверка работоспособности и оценена эффективность предложенных алгоритмов.

1. Андрианов В. Ю. Англо-русский толковый словарь по геоинформатике / В. Ю. Андрианов -М.: ДАТА+, 2001.-122 с.

2. Берлянт A.M. Геоинформационное картографирование. / А. М. Берлянт -М.: Астрея, 1997. 64 с.

3. Борисенков Д. В. Специальное математическое и программное обеспечение манипулирования распределенными объектами в реляционной СУБД на основе полигамических представлений : дис. . канд. тех. наук : 05.13.11 / Д.

4. В. Борисенков ; Воронежская государственная лесотехническая академия; науч. рук. В. Н. Харин. Воронеж, 2007. - 136 с.

5. Борисенков Д. В. Краткий обзор стандартов поддержки ГИС в реляционных СУБД и вариантов их реализации / Д. В. Борисенков, В. Н. Харин // Технология клиент-сервер. 2005. - №3. - С. 40^-5.

6. Боуман Дж., Эмерсон С., Дарновски М. Практическое руководство по SQL / Дж. Боуман, С. Эмерсон, М. Дарновски. М. : Издательский дом "Вильяме", 2001.-336 с.

7. Вахрамеева JI. А. Математическая картография : учебник / JI. А. Вахрамее-ва, JI. М. Бугаевский, 3. JI. Казакова. М. : Недра, 1986. - 285 с.

8. Геоинформатика : Толковый словарь основных терминов / Под ред. А. М. Берлянта, А. В. Кошкаревой. М. : ГИС-Ассоциация, 1999. - 204 с.

9. Грабер М. Справочное руководство по SQL / М. Грабер / Пер. с англ. М. : Лори, 1998.-291 с.

10. Дейт К.Дж. Введение в системы баз данных / К.Дж Дейт . 8-е изд. - М. : Вильяме, 2006. - 1328 с.

11. ДеМерс М. Географические информационные системы. Основы / М. Де-Мерс / Пер. с англ. М. : Дата+, 1999. - 491 с.

12. Дюбуа П. MySQL / П. Дюбуа / Пер. с англ. М. : Издательский дом "Вильяме", 2004.-1088 с.

13. Зикопулос П. DB2 версии 8: официальное руководство / П. Зикопулос, Дж. Бакларц, Д. Де Рус, Р. Мельник / Пер. с англ. М. : КУДИЦ -Образ, 2004. -380 с.

14. Кайт Т. Oracle для профессионалов. Архитектура, методики программирования и основные особенности версий 9i и 10g / Т. Кайт / Пер. с англ. М.: Издательский дом Вильяме, 2007. - 848 с.

15. Кимельман М. JI. Исследование и разработка языковой подсистемы SQL сервера : дис. .канд. физ.-мат. наук : 05.13.11 / М. J1. Киммельман ; Российская Академия Наук. Институт Системного Программирования; науч. рук. С С. Гайсарян. М., 1996. - 210 с.

16. Когаловский М. Р. Энциклопедия технологий баз данных / М. Р. Когалов ский. М. : Финансы и статистика, 2002. - 800 с.

17. Кодд Э. Ф. Реляционная модель для больших совместно используемых банков данных / Э. Ф. Кодд // Журнал СУБД. 1995 - №1. - С. 145-160.

18. Костенко Б. Б. История и актуальные проблемы темпоральных баз данных / Б. Б. Костенко, С. Д. Кузнецов // Труды Института системного программирования. М.: ИСП РАН, 2007. - Т.13, 4.2. - С. 77-114.

19. Мартин Дж. Организация баз данных в вычислительных системах / Дж. Мартин М.: Мир, 1980. - 211с.

20. Мобильная реляционная СУБД Линтер. Версия 6.1.: Справочник по SQL. -Воронеж : НПП Релэкс, 2007.- 190 с.

21. Нейл М. PostgreSQL. Основы / М. Нейл, Р. Стоунз / Пер. с англ. М. : Символ-плюс, 2003. - 400 с.

22. Норенков И. П. Основы автоматизированного проектирования / И.П. Но-ренков. М.: Изд-во МГТУ им. Н.Э.Баумана, 2002. - 336 с.

23. Селко Дж. SQL для профессионалов: программирование / Дж. Селко / Пер. англ. М. : Лори, 2004. - 456 с.

24. Цикритзис Д. Модели данных / Д. Цикритзис , Ф. Лоховски / Пер. с англ. -М.: Финансы и статистика, 1985. 344 с.

25. Шекхар Ш. Основы пространственных баз данных / Ш. Шекхар, С. Чаула / Пер. с англ. М.: КУДИЦ-Образ, 2004. - 336 с.

26. Adler D. W. IBM DB2 Spatial Extender Spatial Data within the RDBMS/ D. W. Adler // Proceedings of the 27th VLDB Conference, Roma, Italy : Morgan Kaufmann, 2001.- P.- 687-690.

27. Pagel B. U. Towards an analysis of range query performance in spatial datastructures / B. U. Pagel, H. W. Siax, H. Toben, P. Widmayer // The twelfth ACM

28. SIGACT-SIGMOD-SIGART symposium on Principles of database systems,

29. Washington, US : proceeding. ACM, 1993. - P. 214-221.

30. Basch J. Algorithms for reporting and counting geometric intersections / J.

31. Basch, L. J. Guibas, G. D. Ramkumar // IEEE Transactions on Computing.

32. Redwood City : CA, 1979. Vol. 28. - P. 643-647.

33. Bentley J. L. Data structures for range searching / J. L. Bentley , J. H. Friedman

34. Computing Surveys (CSUR).- US, New York : ACM, 1979. P. 397^09.

35. Brinkoff T. Generating Network-Based Moving Objects / T. Brinkoff // The12th Int'l Conference on Scientific and Statistical Database Management, Washington, USA, DC : IEEE Computer Society, 2000. P. 253-255.

36. Chen J. Modeling and Predicting Future Trajectories of Moving Objects in a

37. Constrained Network / J. Chen, X. Meng, Y. Guo, S. Grumbach, H. Sun // Proceedings of the 7th International Conference on Mobile Data Management

38. MDM 2006), Nara, Japan : IEEE Computer Society, 2006. P. 156.

39. Draper A. Applied Regression Analysis /A. Draper, R. Norman, V. Smith .

40. New York : John Wiley and Sons, Inc., 1998. P. 7-20.

41. Environmental Systems Research Institute, Inc. ESRI Shapefile Technical Description, 1997.

42. Erwig M. Spatio-temporal data types / M. Erwig, R. H. Guting, M. Schneider,

43. M. Vazirgiannis // An approach to modeling and querying moving objects in databases. Lisbon, Portugal : Geolnformatica, 1999. - Vol. 14. - P. 269-296.

44. Frentzos E. Indexing objects moving on fixed networks / E. Frentzos // Proc.8th Scientific and Statistical Database Management (SSDBM'00), Berlin, Germany : ACM, 2003. P. 289-305.128

45. Gaede V., Gunther О. Multidimensional access methods. Computing Surveys /

46. V. Gaede, 0. Gunther. New York : ACM, 1998. - P. 170-231.

47. Gruber M. SQL Instant Reference / M. Gruber. Alameda, Sybex: CA, 1993.352 p.

48. Guttman A. R-Trees: a Dynamic Index Structure for Spatial Searching / A.

49. Guttman // The ACM-SIGMOD Conference on the Management of Data, Boston, Massachusetts, US : proceeding. ACM Press, 1984. - P. 47-57.

50. Hadjieleftheriou M. Efficient indexing of spatiotemporal objects / M. G. Hadjieleftheriou, V. J. Kollios, D. Gunopulos // The 8th International Conference on

51. Extending Database Technology, London, UK : proceeding. Springer-Verlag,2002.-P. 251-268.59. http: // msdn.microsoft.com/library/(flaTa обращения: 20.10.2008).60. http://www.cnord.ru/0wa обращения: 20.08.2008).

52. International Business Machines Corp., Armonk, NY, USA. IBM DB2 Spatial

53. Extender and Geodetic Extender User's Guide and Reference, Version 8.2,2004.

54. International Business Machines, Corp. DB2 Spatial Extender. User's Guide and

55. Reference, Version 8.1, 2002.

56. Jensen D. Indexing of network constrained moving objects / D. Jensen, C. S.

57. Pfoser // Proceedings of the 11th ACM international symposium on Advances ingeographic information systems, Louisiana, New Orleans, USA : ACM, 2003. 1. P. 25-32.

58. Kollios G. On indexing mobile objects / G. Kollios , D. Gunopulos // Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, Pennsylvania, Philadelphia, USA : ACM, 1999. P.261.272.

59. MySQL AB, Uppsala, Sweden. MySQL 5.0 Reference Manual, 2005.129

60. Nagel K. A cellular automaton model for freeway traffic / K. Nagel, M.

61. Schreckenberg // Journal Physique. 1992. -1 2.- P. 2221-2229.

62. Open Geospatial Consortium. Open GIS Geography Markup Language (GML)

63. Encoding Specification Implementation Specification, Revision 3.1.1, 2004.

64. Open Geospatial Consortium. OpenGIS Simple Features Specification for SQL,1. Revision 1.1,1999.

65. Oracle Spatial User's Guide and Reference: Oracle Corp., Redwood City :

66. CA, 2005. lOg Release 2 (10.2).

67. Oracle Spatial User's Guide and Reference: Oracle Corp., Redwood City : CA,2001.-Release 9.0.1.

68. Pfoser D. Novel approaches to the indexing of moving object trajectories / D.

69. Pfoser, C. S. Jensen, Y. Theodoridis // The 26th International Conference on

70. Very Large Databases, Egypt, Cairo : proceeding.- Morgan Kaufmann, 2000.1. P. 395^106.

71. Prasad S. Modeling and Querying Moving Objects / S. Prasad, W. Ouri, D. Son

72. Proc. of the 11th ACM international symposium on Advances in geographicinformation systems, New Orleans, Louisiana, USA: ACM, 2003. -P 118 125.

73. Saltenis S. Indexing the Positions of Continuously Moving Objects / S. Saltenis,

74. C. S. Jensen, S. T. Leutenegger, M. A. Lopez // Proc. 2000 ACM SIGMOD International Conference on Management of Data, Dallas, Texas, USA :

75. SIGMOND, 2000. P. 331-342.

76. Sellis T. The R+ Tree: A Dynamic Index for Multi- Dimensional Objects / T.

77. Sellis, N. Roussopoulos, C. Faloutsos // Proc. 13rd International Conference on

78. Very Large Data Bases, Brighton, England: Morgsn Kaufmann, 1987. P.507518.130

79. Sistla A. P. Querying the uncertain position of moving objects / A. P. Sistla, O.

80. Wolfson, S. Chamberlain, S. Dao // In Temporal Databases: Research and Practice = LNCS, Redwood City : CA, 1998. Vol. 1399. - P. 310-337.

81. Slobodan R. A Trajectory Splitting Model for Efficient Spatio-temporal Indexing / R. Slobodan, S. Jarg, J. Elding, A. Nascimento // Proceedings of the 31st

82. VLDB Conference, Norway : VLDB Endowment, 2005. P. 934-945.

83. Szalay, A., Kunszt P., Thakar A., Gray J., Slutz D., and Brunner R. Designingand Mining Multi-terabyte Astronomy Archives : The Sloan Digital Sky Survey

84. Proceedings of the 2000 ACM SIGMOD international conference on Management of data, Dallas TX : ACM, 2000. P. 451-462.

85. Tao Y. The TPR*-tree: An optimized spatial-temporal access method for predictive queries / Y. Tao, D. S. Papadia, J. Sun // Proc. Int. Conf. on Very Large

86. Data Bases, Berlin, Germany: Morgan Kaufmann, 2003. P. 790-801.

87. The PostgreSQL Global Development Group. PostgreSQL 8.1.0 Documentation, 2005.

88. Theodoridis Y. Spatial Temporal Indexing for Large Multimedia Applications

89. Y. Theodoridis, M. Vazirgiannis, T. Sellis // The 3rd IEEE Int'l Conference on

90. Multimedia Computing and Systems, Hiroshima, Japan: IEEE Computer Society, 1996. P. 441^48.

91. Trajcevski G. Managing uncertainty in moving objects databases / G. Trajcevski, O. Wolfson, K. Hinrichs, S. Chamberlain // Database Syst., New York, USA :

92. ACM, 2004. Vol. 3. - P. 463-507.

93. Trajcevski G. The Geometry of Uncertaintyin Moving Objects Databases / G.

94. Trajcevski, O. Wolfson, F. Zhang, S. Chamberlain // London, UK : Springer1. Verlag, 2002. P. 233-250.

95. Tzouramanis T. Overlapping Linear Quad Trees for Spatio-temporal Data / T.

96. Tzouramanis, M. Vassilakopoulos, Y. Manolopoulos // In Proc. 4th East

97. European Conf. on Advanced Databases and Information Systems(ADBIS-DASFAA2000), Prague, Czech Republic : Springer-Verlag, 2000. P.279-292.

98. Teixeira D. A. Supporting Uncertainty in Moving Objects in Network Databases / D. A. Teixeira, R.H. Guting // International Workshop on Geographie Information Systems, Bremen, Germany : ACM, 2005. P. 31-40.

99. Wolfson O. Updating and querying databases that track mobile units / O. Wolf-son , A. P. Sistla, S. Chamberlain, Y. Yesha // Distributed and Parallel Databases, Netherlands : Kluwer Academic Publishers, 1999. Vol. 3. - P. 257-387.