WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 | 2 || 4 |

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

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

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

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

3. Выбор из оставшихся вариантов оптимального пути по заданному критерию.

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

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

Архитектура справочной системы должна обеспечивать высокую производительность при большом количестве пользовательских запросов.

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

Предполагается, что запросы к данным, распределены по закону Пуассона со средней интенсивностью Считается, что все документы I,i.

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

.

, где константа определяет, насколько пологим будет Zipf распределение и определяется как:

Общая задержка T при получении документа состоит из задержки времени соединения и времени передачи где – математическое ожидание времени полной передачи документа.

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

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

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

где – вероятность того, что нет запросов к документу i в поддереве с корнем в в интервале времени [0,.

В результате получаем вероятность:

Чтобы вычислить времена передачи, сначала определяется суммарная частота запросов на каждом сетевом уровне. Суммарная частота к глобальной внешней системе определяется выражением:

Вероятность обработки на каждом сетевом уровне.

Суммарная частота запросов к локальной системе определяется выражением для, и, для.

Время передачи данных из различных систем рассматривается в параграфе 2.4.

Время передачи из глобальной информационной системы :

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

где – время передачи через соответствующий сетевой уровень из локальной информационной системы.

Пусть – средний размер документов. Теория очередей M/D/1 дает для запросов к глобальным системам выражение:

.

Аналогично для запросов к локальным системам:

.

Время полной обработки запроса выводится в параграфе 2.4 и определяется наибольшим из времен взаимодействия с информационными системами. Время установления соединения с удаленной локальной системой оказывается больше этого времени для глобальной системы:

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

Программный комплекс включает в себя следующие компоненты:

1. Специализированная база данных геоинформации и расписаний.

2. Средства подготовки данных для геоинформационной системы и БД.

3. Средства импорта данных из промежуточного формата XML.

4. Реализация алгоритмов поиска маршрута на транспорте.

5. Службы интеграции с другими информационными системами, включающие:

a. интеграционный сервис, функционирующий в режиме on-line;

b. эмулятор терминала системы ЭКСПРЕСС.

6. Справочный интернет-портал для доступа к информационной системе.

Специализированная база данных оптимизирована для хранения и анализа информации по транспорту. Она содержит несколько десятков таблиц и реализацию базовых алгоритмов работы с данными, которые запрограммированы в хранимых процедурах на языке T-SQL. Каждый объект в базе данных имеет как координатную привязку, так и привязку к совокупному графу вершин и соединений.

Средства подготовки данных для системы описаны в параграфе 3.3.

Особенности информационной системы потребовали создания специального программного инструментария – среды визуального описания транспортного графа. Программа представляет собой Windows-приложение, написанное на языке C++. С ее помощью можно описать фрагменты единого графа. Результаты работы программы сохраняются в файлы формата XML. Для каждого региона создается отдельный XML файл, где указывается расположение региональных транспортных узлов. Таким способом можно последовательно описать все фрагменты железнодорожной и автобусной сети. С помощью разработанной программы было описано большинство железнодорожных станций, вокзалов, платформ на территории всего бывшего СССР и некоторых прилегающих стран, а также основные автобусные станции нескольких регионов России.

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

Процесс загрузки состоит из следующих шагов: считывание данных из файла, анализ данных, устранение неоднозначностей, формирование объектной структуры, сохранение данных. Программа импорта состоит из двух функциональных модулей: (i) загрузчик географических данных, (ii) загрузчик расписаний. Загрузчик географических данных обрабатывает подготовленные оператором файлы данных. Алгоритм импорта географических объектов запрограммирован следующим образом: 1) распознавание названия и типа объекта; 2) поиск объектов в базе данных с похожим названием; 3) добавление объекта в базу данных; 4) обновление топологических связей.

Реализация алгоритма поиска и модуль ядра описаны в параграфе 3.7.

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

Взаимодействие с внешними системами представляет отдельную подсистему, в которую входят: модуль интеграции в составе модуля поиска пути; сервис интеграции с внешними системами; эмулятор терминала ЭКСПРЕСС; программа контроля взаимодействия с внешними системами.

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

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

Если используется асинхронный способ взаимодействия, например, с системой ЭКСПРЕСС, то запрос ставится в очередь. Когда в очереди появляются запросы на обслуживание, к работе подключается программа-сервис взаимодействия.

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

Сервисы могут специализироваться на обслуживании запросов к определенным внешним системам. Взаимодействие с системой ЭКСПРЕСС осуществляется через специальный сервис-эмулятор терминала. При получении запроса, для которого необходимо получить информацию из системы ЭКСПРЕСС, эмулятор терминала преобразует запросы системы в пакеты BSC-3 сети ЭКСПРЕСС, инкапсулирует их в пакеты TCP/IP и передает на шлюз доступа в ЭКСПРЕСС.

Далее шлюз обменивается информацией с ХОСТ-ЭВМ и возвращает ответ эмулятору. Процесс протекает асинхронно: один запрос системы может отображаться в серию запросов-ответов между эмулятором и ХОСТ-ЭВМ.

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

- поиск пунктов пересадки, когда нет прямого пути проезда;

- поиск путей только на указанном виде транспорта (автобусы, поезда);

- поиск пути проезда между двумя пунктами с пересадкой в третьем явно указанном пункте;

- поиск интермодального пути проезда (на разных видах транспорта);

- поиск пути проезда в заданную дату (маршруты транспорта, которые не удовлетворяют указанной дате, не отображаются в результатах);

- поиск пути проезда со всех вокзалов города, или явное указание с какого вокзала искать путь;

- отображение найденных путей проезда на интерактивной карте;

- отображение схемы всех прямых маршрутов транспортного узла.

Рисунок 1. Результат поиска пути проезда Бобруйск-Дальнегорск В главе 4 продемонстрированы результаты использования информационносправочной системы, и проведено исследование ее работы. В параграфе 4.приводятся примеры результатов поиска по различным видам запросов:

- поиск маршрута с пересадкой на одном виде транспорта;

- поиск маршрута с одной пересадкой на нескольких видах транспорта;

- поиск маршрута с одной пересадкой в крупном транспортном узле;

- поиска маршрута с несколькими пересадками на одном виде транспорта.

В параграфе 4.2 проводится статистический анализ транспортного графа. Проводится три серии вычислений по исследованию плотности графа вокруг Москвы, Калининграда и Владивостока.

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

Например, на расстоянии 500 км от Москвы расположено более 3000 станций, а на таком же расстоянии от Владивостока - только 195 станций. Аналогичный статистический анализ проводится для Рисунок 2. Результат поиска пути пересадочного графа. Вид графиков и проезда по Московской области данные таблиц показывают аналогичную картину неоднородности для пересадочного графа. Далее в главе исследуются транспортные маршруты поездов дальнего следования.

Далее находится зависимость количества достижимых пунктов назначения от минимального числа необходимых пересадок. Проводится серия вычислений для пунктов Москва, Калининград и Владивосток. Как и следовало ожидать, для проезда из Москвы в другие пункты в среднем требуется меньше пересадок, чем для проезда из Владивостока. Приводится анализ зависимости количества пунктов назначения от расстояния и заданного количества пересадок. Из графиков видно, что наиболее вероятное расстояние до пункта назначения, до которого можно добраться из Москвы минимум с одной пересадкой, составляет 800 км. Для Калининграда это расстояние составляет уже 1200 км, а для Владивостока - 6500 км.

Pages:     | 1 | 2 || 4 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»