WWW.DISSERS.RU

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

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

Pages:     | 1 || 3 |

Концепция «мобильных роботов». Эта концепция, по своей сути, является гибридом предыдущих концепций. Её основу составляет предложение модернизировать программное обеспечение Web-сервера и оснастить его специальной средой («distributed crawler runtime environment»). В задачи среды входит «принятие» от центрального узла системы мониторинга к себе некоторого «мобильного» кода («мобильный робот») и последующее его выполнение. Используемые в мобильном роботе алгоритмы повторяют идей из концепции «роботов». Результатом работы кода является представление (или т.н. расширенная форма мета-описания) о состоянии ИР, которые найдены на данном Web-сервере. Полученное представление полностью передаётся на головной узел системы мониторинга, а мобильный робот «переходит» к обработке другого Web -сервера.

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

.

где FP(S;t) – свежесть, измеряемая в процентах; N – общее количество ИР; ei (i = 1,…, N) обозначает ИР, которые уже хранятся в базе данных системы мониторинга; S = {e1,…, eN} – база данных системы мониторинга; FN(ei;t) обозначает свежесть элемента ei в момент времени t, которая вычисляется следующим образом:

.

Во-вторых, суммарный объём V(t) (в байтах) всех ИР, которые система мониторинга перекачала со стороны информационных источников на сторону головного узла мониторинга с начала работы до момента наблюдения t.

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

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

В первом параграфе главы проведён анализ ситуации с моделированием систем мониторинга. Найденные работы, в которых с помощью имитационного моделирования исследовались различные аспекты функционирования системы мониторинга «роботов» невозможно использовать (из-за акцентов и принятых в них допущений) в качестве единообразного подхода к рассмотрению эффективности любых систем мониторинга. Также было сказано о том, что использование теории систем массового обслуживания неприемлемо в силу необходимости принятия допущений о характере потоков заявок.

Математическая модель. Информационное поле состоит из N различных информационных ресурсов. Процесс мониторинга - это меняющийся в дискретном времени набор состояний. Состояние в момент времени t – это тройка <R,R', >, где

  • R = (r1,r2,..., rN), ri - матрица числовых характеристик информационного ресурса с номером i;
  • R' = (r'1,r'2,..., r'N), r'i - матрица числовых значений критериев эффективности Freshness и Sumsize информационного ресурса с номером i;
  • =(1,..., N), i - текст программы записанной на языке высокого уровня, которая преобразует согласно некоторого алгоритма матрицу ri в матрицу r'i:

r'i=i ri

или

R' = R

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

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

  • пропускная способность каналов подключения к Internet имеет максимально возможный размер, чтобы минимизировать время передачи любого, отдельно взятого ИР;
  • продолжительность «посылки» любого GET-запроса можно не учитывать;
  • законы распределения значений параметров в явном виде указывать не нужно;
  • не рассматриваются функции поиска новых ИР.

Одинаковым для обеих моделей является, во-первых, то, что основные объекты в них – объекты типа «информационный ресурс», которые характеризуются значениями следующих свойств:

  • размер содержимого (количество байт);
  • идентификатор текущего состояния (рассматривается конечный набор допустимых значений, каждое из которых относится к группе «ИР доступен» или «ИР недоступен»);
  • признак того, что серия последних изменений стала известна системе мониторинга (истина – ложь).

Второй одинаковой чертой моделей является наличие объектов типа источник изменений (ИИ) и источник запросов (ИЗ), каждый из которых описывается потоком изменений (ПИ) или потоком запросов (ПЗ) соответственно. В свою очередь, поток изменений характеризуется законом распределения Hc(x) времени (Тизм) появления следующего изменения (смены состояния ИР или смены содержимого ИР) и законом распределения G() относительной частоты появления определённого (одного из возможных вариантов) «изменения» (Инов), а поток запросов характеризуется законом распределения Hq(x) времени (Тзапр) появления следующего запроса. Каждому ИР сопоставляется собственная пара ИИ и ИЗ.

Различие моделей проявляется в объектах, которые воспроизводят элементы системы мониторинга:

  • В модели «робота» систему мониторинга воспроизводят два объекта: «робот» и «репозиторий». Причём в модели описан робот, который реализует стратегию последовательного скачивания всех известных ИР.
  • В модели «сенсоров» систему мониторинга воспроизводят объекты типа «сенсор», «робот» и «репозиторий». Причём в модели реализуется робот, который немедленно начинает скачивание ИР сразу после поступления от соответствующего «сенсора» уведомления о найденном изменении состояния ИР или изменении содержимого ИР. Для простоты рассмотрения считалось, что каждому экземпляру объекта ИР соответствует один экземпляр объекта «сенсор».

Взаимодействие объектов моделей можно представить в виде схем (Рис.1 и Рис.2). По поводу Рис. 1 стоит сделать два замечания. Во-первых, в модели «робота» потоки запросов никоим образом не используются и не описываются, но всё же изображаются на рисунке, чтобы отобразить наличие формально равных условий функционирования вариантов системы мониторинга. Во-вторых, литерой «N» обозначено общее количество ИР.

Рис. 1. Схема взаимодействия объектов модели «робота»

Рис. 2. Схема взаимодействия объектов модели «сенсоров»

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

Для моделирования процесса скачивания в обеих моделях используется закон распределения Hg(x) времени скачивания ИР, с помощью которого определяется момент завершения процесса скачивания этого ИР - Тскач. Для имитации процесса посылки уведомления сенсором определяется время Тувед когда сигнал уведомления «дойдёт» до робота (время Тувед имеет свой закон распределения Ha(x) чтобы в последствии можно было учитывать такие случаи как, например, отложенное уведомление или загруженность Web-сервера).

Отдельный параграф главы посвящён обсуждению проблемы самостоятельного (исследователем относительной эффективности систем мониторинга) задания конкретных законов распределения для Hc(x), Hg(x), Hq(x), Ha(x).

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

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

  1. Среда разработки программ Borland Delphi 6 (от неё отказались по причине недоступности качественной библиотеки организации модельной среды).
  2. Среда GPSS World student от фирмы Minuteman (не могла справиться с большим объёмом вычислений, пределом оказалось моделирование «жизни» около 40000 ИР).
  3. Язык программирования Python 2.2 + средства баз данных MySQL 4.0.13 + python-модуль SimPy 1.3 (среда удовлетворила всем сформулированным требованиям).

Python-модуль SimPy представляет собой библиотеку классов для программирования моделей, которые основаны на дискретных событиях (классы реализуют ведение календаря событий).

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

  • SimPages.py – задача модуля заключается в генерации (равномерный закон распределения задаёт начальный размер каждого ИР) набора ИР.
  • SimChanges.py – задача модуля заключается в генерации (интервал времени между последовательными событиями определяет экспоненциальный закон распределения) истории изменений ИР определённого набора. Тип нового изменения определяется с помощью заданных относительных частот появления шести предопределённых типов изменений.
  • SimQueries.py – задача модуля заключается в генерации (интервал времени между последовательными событиями определяет экспоненциальный закон распределения) истории запросов ИР определённого набора.
  • SimRobRoute.py – модуль занимается тем, что «привязывает» каждый конкретный ИР к одному из роботов. Используемый алгоритм «привязки» априори подразумевает наличие упорядоченной нумерации у ИР, которые созданы модулем SimPages.py.
  • SimRobot.py – модуль позволяет осуществлять имитацию функционирования вариантов системы мониторинга, которые построены с использованием «обычных роботов».
  • SimRobotM.py – имитация работы варианта системы мониторинга, которая использует «модифицированных роботов». За основу модуля был взят код модуля SimRobot.py и соответствующим образом модифицирован.
  • SimSensor.py – модуль позволяет осуществлять имитацию функционирования варианта системы мониторинга, которая использует «сенсоры».

Рис. 3. Структура комплекса SimCOSAR

Также имеются два модуля, которые предназначены для извлечения из баз данных значений статистических переменных и их последующей записи в файлы формата CSV:

  • SimReport.py – извлекает из баз данных значения, которые накоплены в ходе одного опыта.
  • SimMergeReports.py – извлекает статистику нескольких опытов (вместо нескольких CSV-файлов получаем один файл - первый столбец содержит время замера, а в остальные столбцы попадают результаты замеров одной переменной в нескольких опытах).

В работе представлено детальное описание «настроечной» информации (параметров моделирования), как всего комплекса, так и каждого модуля по отдельности. Например, для SimRobot.py описаны параметры: RobotQuantity, ModelTime, PageCount, MinPageLoadTime, MaxPageLoadTime, StepLogCycles и т.д. Также представлена подробная информация о выходной (статистические переменные, журналы функционирования) информации каждого модуля. Принципы функционирования основных модулей пояснены с помощью блок-схем обобщённых алгоритмов.

В заключении третьей главы отмечено, что программный комплекс SimCOSAR может быть легко модернизирован под цели исследования непредусмотренных вариантов системы мониторинга или для проведения исследований вариантов на основе данных о реальном (для этого достаточно в таблицы pages, changes, queries внести соответствующие данные) сегменте информационного поля.

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

Планирование эксперимента. Проведён анализ имеющихся в моделях переменных, в результате которого выделены основные, второстепенные, третьестепенные переменные отклика и основные, второстепенные, третьестепенные влияющие факторы. К основным переменным отклика отнесены переменные:

  • Количество «устаревших» ресурсов (Needfresh, шт.).
  • Свежесть (Freshness, %).
  • Объём скачанной информации (Sumsize, байт).

Для основных влияющих факторов выбраны уровни изменения:

Pages:     | 1 || 3 |






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