Размещено на http://www.Allbest.ru/

Размещено на http://www.Allbest.ru/

05.25.05 - Информационные системы и процессы, правовые аспекты информатики

Автореферат

диссертации на соискание ученой степени доктора технических наук

Тема:

Мобильные распределенные базы данных автоматизированных информационно-управляющих систем МЧС России

Иванов Александр Юрьевич

Санкт-Петербург - 2009

Работа выполнена в Санкт-Петербургском университете Государственной противопожарной службы МЧС России

Научный консультант:

доктор технических наук, доктор военных наук, профессор, заслуженный работник высшей школы РФ Артамонов Владимир Сергеевич

Официальные оппоненты:

доктор технических наук, профессор, заслуженный деятель науки РФ Яшин Александр Иванович;

доктор технических наук, профессор Осадчий Александр Иванович;

доктор технических наук, старший научный сотрудник Одоевский Сергей Михайлович.

Ведущая организация:

Санкт-Петербургский институт информатики и автоматизации Российской академии наук

С диссертацией можно ознакомиться в библиотеке Санкт-Петербургского университета Государственной противопожарной службы МЧС России.

Ученый секретарь диссертационного совета Д205.003.02 доктор технических наук, профессор И.Г. Малыгин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы. За последние десятилетия произошли кардинальные изменения в управлении силами и средствами МЧС. Информатизация мероприятий повседневной деятельности и операций при ликвидации чрезвычайных ситуаций приобрела статус решающего фактора.

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

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

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

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

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

Во-вторых, преимущественным использованием промышленно выпускаемых систем управления распределенными базами данных (СУРБД), для которых вопросы оперативности обработки информации не всегда являются доминирующими.

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

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

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

Таким образом, проблема организации МРБД является одной из основополагающих проблем, решаемых при комплексной информатизации МЧС России.

В настоящее время уместно вести речь о прочном становлении технологии БД, которая имеет под собой солидный теоретический фундамент. Значительный вклад в развитие общей теории баз данных, внесли зарубежные исследователи Дж. Мартин (Martin J.), К. Дейт (Date C.), Э. Кодд (Codd E.), Дж. Ульман (Ullman J.), Д. Цикритзис (Tsichritzis D.), С. Чери (Ceri S.) и др. Среди отечественных специалистов в области БД следует отметить Мамиконова А.Г., Калиниченко Б.О., Цегелика Г.Г., Галатенко В.А., Ладыженского Г.М., Кузнецова С.Д., Сахарова С.С. Представителями Санкт-Петербургской научной школы информационных систем и БД по праву считают Артамонова В.С., Яшина А.И., Саенко И.Б., Котенко И.В., Лычагина Н.И., Ломако С.Г. и других. Несмотря на внушительный научный задел в указанной области исследований, методологические основы решения проблемы реструктуризации РБД в настоящее время не разработаны и находятся в стадии становления. Тем не менее, для создания таких основ сложились объективные предпосылки, к числу которых следует отнести:

формирование общей концепции единого информационно-функционального пространства органов управления МЧС России;

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

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

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

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

Объектом исследования являются распределенные базы данных автоматизированных информационно-управляющих систем МЧС России.

Предмет исследования составляют эмпирические факты, закономерности, модели и методы построения МРБД и управления ими в АИУС МЧС России.

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

1) исследование необходимости и возможности реализации структурных изменений РБД в интересах повышения эффективности функционирования АИУС МЧС;

2) разработка основ теории МРБД;

3) разработка моделей и методов анализа и синтеза МРБД;

4) разработка модели, методов и алгоритмов динамического управления МРБД;

5) разработка метода и алгоритмов обеспечения целостности МРБД;

6) разработка методики оценки эффективности МРБД;

7) формирование научно-обоснованных рекомендаций по применению МРБД.

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

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

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

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

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

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

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

Научная новизна работы определяется следующим.

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

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

3. При разработке моделей и методов построения МРБД применены и получили развитие методы теории массового обслуживания, теории распределений, математического программирования, теории принятия решений. Задача синтеза структуры МРБД приведена в новой постановке и для ее решения предложен оригинальный метод, который ранее в области разработки структуры распределенных баз данных не применялся.

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

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

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

7. При разработке методики оценки эффективности МРБД использован подход к определению критерия эффективности на основе зависимых по полезности показателей эффективности,

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

формированием экспериментально проверенных на моделях предложений по использованию полученных результатов в распределенных базах данных существующих и перспективных АИУС;

возможностью постановки и решения практических задач построения МРБД на основе разработанных методологических основ;

доведением полученных результатов до практических алгоритмов, и возможностью их реализации в существующих и перспективных АИУС.

Достоверность результатов диссертационной работы обеспечена:

использованием системного подхода при изучении объекта исследования;

корректностью постановок задач и применением математических методов их решения;

полнотой учета совокупности и характера факторов, влияющих на информационный процесс и АИУС;

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

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

Публикации. Результаты диссертационного исследования опубликованы в монографии, 19 статьях в журналах и научно-технических сборниках, 14 сборниках докладов международных, всероссийских и ведомственных научно-технических конференций. Список 40 основных работ приведен в конце автореферата.

Реализация. По результатам работы получены акты реализации от следующих организаций: Северо-Западный региональный центр МЧС России, ГУП НИИ «Рубин», ОАО «Институт сетевых технологий»,

Научные результаты и разработанные в рамках диссертационного исследования модели, методы и алгоритмы реструктуризации МРБД внедрены в учебный процесс Санкт-Петербургского университета Государственной противопожарной службы МЧС России и Военной академии связи.

Апробация. Результаты диссертационной работы докладывались и обсуждались на II Международной научно-практической конференции «Исследование, разработка и применение высоких технологий в промышленности» (Санкт-Петербург, 2006 г.), Международной конференции по мягким вычислениям и измерениям SCM-2005 (Санкт-Петербург, 2005 г.), I Научно-практической конференции Военной академии связи (Санкт-Петербург, 2005 г.), Международной конференции по мягким вычислениям и измерениям SCM-2003 (Санкт-Петербург, 2003 г.), Международной научно-практической конференции «Проблемы обеспечения безопасности при чрезвычайных ситуациях» (Санкт-Петербург, 2003 г.), II Международной научно-практической конференции «Экономика и инфокоммуникации в XXI веке» (Санкт-Петербург, 2003 г.), 2-ой Всероссийской научной конференции «Проблемы развития информационно-телекоммуникационных систем специального назначения» (Орел, 1999 г.), а также ряде других конференций и семинаров.

Структура и объем работы. Диссертационная работа состоит из введения, шести разделов, заключения, списка литературы и шести приложений. Диссертация изложена на 326 страницах основного текста, содержит 67 рисунков, 15 таблиц и список литературы из 219 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

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

В состав системы управления МЧС в Северо-Западном Федеральном округе входят Северо-Западный региональный центр и Главные управления по субъектам Федерации: Республике Карелия, Республике Коми, Ненецкому Автономному округу, Архангельской, Вологодской, Калининградской, Ленинградской, Мурманской, Новгородской, Псковской областям и Санкт-Петербургу.

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

Рис. 1. Типовая структура технического комплекса АИУС регионального уровня

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

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

Требования к информационному процессу в системе управления МЧС, к АИУС и РБД формулируются на качественном или количественном уровнях. В первом случае требования выражаются в виде совокупности существенных свойств, характеризующих процесс и/или систему. Предъявление требований на количественном уровне дополнительно предполагает определение ПЭ и задание их предельных или интервальных значений. Система свойств показана на рис. 2.

Доминирующим свойством информационного процесса является своевременность. Это свойство в значительной мере определяется оперативностью АИУС, которая в основном зависит от реактивности БД. Названные свойства объединены в категорию «темпоральных».

С позиций теории эффективности удовлетворение требований к информационному процессу рассматривается как цель, достигаемая при построении и использовании АИУС и ее РБД, в частности.

Рис. 2. Субординация свойств информационного процесса и средств его реализации

Существуют факторы, определяемые спецификой условий функционирования системы управления МЧС, которые могут приводить к изменению значений ПЭ информационного процесса. К ним относятся:

перемещение пользователей в плановом или оперативном порядке;

изменение структуры сети, например, ее наращивание или деформация, обусловленная перемещением центров (пунктов) управления;

выход или угроза выхода из строя центров (пунктов) управления, узлов или линий связи по причинам разрушений, вызванных техногенными и природными катастрофами, террористическими актами;

отказы и сбои аппаратно-программных средств АИУС;

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

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

В этом случае, начиная с некоторого момента времени t₀, значение выбранного показателя может выходить за нормативные пределы (см. рис. 3, поз. 2). В подобной ситуации вполне естественным является стремление к стабилизации значений ПЭ за счет изменения характеристик БД. Изменения могут быть параметрическими или структурными.

Рис. 3. Характер изменения значений показателей эффективности информационного процесса

К параметрическим изменениям относятся:

увеличение производительности и объема внешней памяти серверов базы данных (СБД) в узлах сети;

повышение скорости передачи данных между узлами сети;

оптимизация маршрутов выполнения запросов в плане уменьшения времени их исполнения.

Параметрическая модификация РБД имеет ограниченные возможности в динамике функционирования АИУС, т.к. требует модернизации аппаратно-программных средств и значительных затрат времени.

Структурные изменения возможны по следующим направлениям:

наращивание количества СБД в сети за счет их установки в свободных узлах сети;

изменение топологии связей между СБД и рабочими местами пользователей за счет организации дополнительных каналов передачи данных (КПД);

трансформация физической структуры РБД за счет перераспределения ФД между функционирующими СБД.

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

Традиционно полагается, что структура РБД формируется в процессе проектирования и не подлежит изменению на этапе эксплуатации. Такое положение характерно для большинства коммерческих информационных систем. Тем не менее, потребность в изменении структуры РБД наблюдается и в этих системах, что повлекло внедрение в СУРБД механизма репликации данных. Однако эффективное использование репликации предполагает наличие высокоскоростных КПД. Кроме того, репликация не является адекватным ответом на проявление таких факторов риска как выход (угроза выхода) из строя узлов сети, программные атаки и др.

Таким образом, анализ условий функционирования АИУС показывает необходимость наличия РБД с изменяемой структурой. Придание гибкости структуре РБД позволит обеспечить выполнение требования по реактивности и, тем самым, повысить оперативность АИУС и своевременность информационного процесса в различных условиях обстановки. Реструктуризация способна сбалансировать загрузку СБД, снизить интенсивность сетевого трафика, уменьшить время доступа к данным и, следовательно, повысить эффективность использования РБД.

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

Существующее и требуемое положение в области реструктуризации РБД характеризуются следующими факторами (табл. 1).

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

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

Таблица 1

Сравнение положения в области реструктуризации РБД

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

Схематично возникновение проблемы организации МРБД показано на рис. 4.

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

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

Рис. 4. Возникновение проблемы организации МРБД

Составляющими процесса организации МРБД, требующими реализации в рамках разрабатываемой методологии, являются:

1) построение МРБД;

2) управление функционированием МРБД;

3) обеспечение функционирования МРБД;

4) оценка эффективности применения МРБД.

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

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

Теория МРБД относится к классу гипотетико-дедуктивных теорий. Ее структура представлена на рис. 5.

Система понятий теории объединяет известные термины смежных областей знаний - систем связи, баз данных, вычислительных систем, а также новые понятия в области МРБД (рис. 6).

К наиболее важным понятиям относятся следующие:

мобильность - свойство объекта, характеризующее его способность к перемещению, изменению характера своих действий в зависимости от смены обстановки;

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

Рис. 5. Структура теории МРБД

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

мобильная распределенная база данных - распределенная база данных, фрагменты которой могут перемещаться (копироваться) с одного узла сети на другой; при этом сохраняется логическая интеграция данных и их доступность пользователям;

реструктуризация - процесс изменения физической структуры МРБД за счет миграции мобильных фрагментов данных;

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

Рис. 6. Система понятий теории МРБД

Концептуальная модель МРБД фиксирует множество возможных априорных и апостериорных знаний о структуре и характере функционирования базы данных в условиях изменения ее применения и внешних воздействий и выступает в качестве их слабоструктурированной модели.

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

(1)

где - вектор характеристик потока запросов к МРБД,

- вектор характеристик среды, - вектор описания структуры МРБД,

- вектор управляющих воздействий на изменение структуры МРБД,

- вектор управляющих воздействий, направленных на обеспечение целостности данных,

- вектор внутренних характеристик АИУС,

- вектор требований к процессам функционирования МРБД и АИУС в целом,

- вектор показателей эффективности МРБД и АИУС,

F - функционал, определяющий порядок перехода от указанных векторов к вектору .

Рис. 7. Модель процесса реструктуризации МРБД

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

Анализ процесса и условий функционирования МРБД позволяет сформулировать следующие гипотезы:

1) о существовании возможности поддержания параметров АИУС и ее базы данных в требуемых пределах и о ее реализации на основе структурных изменений;

2) о существовании компромисса между ресурсными и временными издержками на реструктуризацию базы данных и снижением эффективности ее применения.

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

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

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

1) нахождения множества значений показателей реактивности РБД (показателей оперативности обработки запросов);

2) определения множества значений показателей оперативности решения задач в АИУС;

3) вычисления обобщенного показателя своевременности информационного процесса.

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

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

Такими элементами являются (рис. 8):

сети передачи данных (моноканалы - МК) локальных вычислительных сетей, входящих в состав общей сети АИУС;

СБД, на которых размещены ФД;

коммутационные устройства (КУ), обеспечивающие обмен данными между удаленными узлами;

каналы передачи данных (КПД).

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

Структура модели приведена на рис. 8.

Рис. 8. Структура модели для оценки реактивности МРБД

Модель решения задач в АИУС. В модели верхнего уровня процесс решения задачи в АИУС представляется ориентированным графом, узлы которого отображают операции по обработке запросов к МРБД, а дуги - связи между операциями (рис. 9).

Рис. 9. Граф процесса решения задачи

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

Плотность распределения времени пребывания заявки в сети определяется равенством

,

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

L - число путей.

Интегрируя обе части этого равенства в пределах от 0 до t_доп, и учитывая, что интеграл суммы равен сумме интегралов, получим

, (2)

где

Использование взвешенного суммирования требует существенных затрат вычислительных ресурсов для многократного нахождения величины .

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

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

Синтез МРБД предполагает последовательное принятие решений по размещению ФД в сети. Цель этого процесса - добиться такого размещения, при котором база данных соответствует требованиям.

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

1. Определение исходных данных. На основе анализа характера АИУС и условий ее функционирования исследуются сильные и слабые стороны каждой стратегии относительно выявленных факторов. Результат этапа - матрица оценки факторов, в которой столбцы соответствуют видам стратегий-претендентов, а строки - анализируемым факторам. Элементы матрицы обозначаются «1» в случае отнесения фактора к достоинствам стратегии, и «0» - в противном случае.

2. Оценка стратегий. Базируется на использовании экспертных методов, таких как парные сравнения или ранжирование. Результатом этапа является матрица балльных оценок стратегий относительно факторов.

3. Формирование отношения предпочтительности стратегий. Предполагает переход от векторных оценок стратегий к скалярным. Основу такого перехода составляет алгоритмический метод нахождения весовых коэффициентов на основе ряда приоритета. Результатом этапа и применения метода выбора стратегии в целом является ряд предпочтения стратегий, построенный по убыванию интегрированных оценок каждой.

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

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

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

Постановка задачи размещения ФД в сети формулируется следующим образом. Сеть состоит из n узлов, в которых размещены СБД. Известно первоначальное размещение ФД по узлам, полученное при проектировании БД. Доля данных, получаемая i-м пользователем от ФД j-го узла - f_ij (i = 1...m, j = 1...n). Среднее время исполнения запроса i-го пользователя j-м узлом определяется как t_ij. При изменении пространственного положения пользователей и/или структуры сети необходимо перераспределить ФД по узлам. Среднее время передачи j-го ФД по сети при изменении его местоположения _j.

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

Метод решения задачи заключается в следующем. Основными временными характеристиками АИУС являются время реализации запросов на получение данных и время выполнения запросов на корректировку, которые в сумме определяют «рабочую нагрузку» T.

Введем такие булевы переменные x_j, что

Задача размещения формулируется следующим образом:

найти

(3)

при ограничениях

(4)

(5)

(6)

Целевая функция определяет затраты на размещение фрагментов в узлах, соответствующих значениям x_j = 1. Первое ограничение означает, что общая доля данных, получаемая i-м абонентом от j-го узла, либо равна нулю, если x_j = 0, либо не может превосходить числа абонентов в противном случае. Из второго ограничения следует, что все потребности i-го пользователя должны быть удовлетворены некоторым набором фрагментов.

В такой постановке задача относится к задаче смешанного целочисленного программирования, и впервые была сформулирована как задача размещения одного предприятия с дискретным пространством решений. Подобный подход учитывает в качестве основного параметра только транспортные расходы. Тогда в случае предельно малых затрат на передачу фрагментов (_j 0) оптимальное решение состояло бы в том, чтобы разместить любой фрагмент в каждом из доступных мест (дублирование базы данных). Напротив, если бы время доступа к данным по всей сети различалось несущественно (t_ij const), любое размещение фрагментов по узлам сети было бы оптимальным. Таким образом, задача в приведенной постановке призвана найти решение, обеспечивающее определенное соотношение между временем на реструктуризацию базы и временем исполнения рабочей нагрузки.

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

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

Шаг 1. Проводится ранжирование ФД по очередности изменения их положения.

Шаг 2. Решается задача размещения каждого ФД в соответствии с его приоритетом. Если при размещении очередного ФД происходит наложение на занятый узел, то на данном этапе задача решается повторно. Для занятого узла принудительно устанавливается значение переменной x_j = 0.

Шаг 3. Оценивается величина рабочей нагрузки T. При превышении установленных значений происходит изменение порядка ранжирования и возврат к шагу 2. В случае удовлетворения требований принимается полученный план размещения.

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

На шаге 2 после размещения очередного ФД в j-м узле осуществляется оценка суммарного объема его фрагментов и проверка

где s - номера уже размещенных ФД в j-м узле.

Если требование не удовлетворяется, то как и в предыдущем случае, задача решается повторно, но для занятого узла принудительно устанавливается значение переменной x_j = 0.

Такой подход справедлив, если число копий ФД невелико и временем их актуализации можно пренебречь. В противном случае следует учесть среднее время актуализации копии, размещаемой в j-м узле

Задача размещения ФД формулируется в уточненной постановке:

найти

(7)

при тех же ограничениях

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

В подобной ситуации целесообразно отыскание компромисса между стремлением к выполнению требований по эффективности реализации запросов к МРБД и имеющимися временными ресурсами на реструктуризацию базы данных.

Предлагается следующая модель решения данной задачи на основе применения рассмотренного метода (рис. 10).

мобильный распределенный информационный база данный



Рис. 10. Структура модели синтеза МРБД

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

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

Блок оценки эффективности (БОЭ) служит для определения соответствия процесса информационного обслуживания пользователей требованиям.

Блок синтеза структуры МРБД (БСС) решает задачу отыскания варианта структуры, оптимизирующего значение критерия эффективности МРБД.

Блок анализа целесообразности реструктуризации (БАЦР). При обнаружении существенных расхождений текущих и требуемых значений показателей эффективности в этом блоке вырабатывается рекомендация на изменение структуры МРБД. В противном случае принимается решение оставить существующую структуру.

Кроме того, последний названный блок предназначен для определения ФД, подлежащих передаче или копированию на другие узлы сети. Это осуществляется путем сравнения существующей на данный момент и предлагаемой структур МРБД. Затем формируются маршруты передачи ФД. Исходя из объемов передаваемых (копируемых) фрагментов и скоростных характеристик КПД, рассчитывается ожидаемое время перегруппировки фрагментов. Если расчетное время не превышает некоторой допустимой величины, то выработанный вариант структуры подлежит реализации. В противном случае требуется проведение дополнительного анализа. Следует оценить и сравнить потери эффективности (ущерб):

1) от снижения уровня выполнения требований, предъявляемых к информационному сервису;

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

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

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

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

1) использование в качестве исходных данных для решения оптимизационной задачи накопленной статистики о характеристиках потоков запросов;

2) оптимизацию размещения ФД по СБД в соответствии с локальными критериями для каждого СБД в отдельности;

3) децентрализованное управление процессом реструктуризации;

4) проведение реструктуризации параллельно с обработкой запросов.

Цель динамического управления состоит в модификации физической структуры МРБД без прерывания процесса обработки запросов. При этом решаются следующие задачи:

сбор статистических данных о нагрузке на СБД, потоках циркулирующих запросов и эффективности их обработки;

проверка соответствия текущего размещения ФД принятым критериям;

непосредственное управление размещением ФД;

определение моментов проведения реструктуризации.

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

Метод динамического планирования локального представления структуры МРБД. В качестве основного критерия оптимальности размещения ФД принят минимум затрат на информационный обмен между СБД:

 (8)

где - показатель информационного обмена i-го и j-го СБД, имеющий физический смысл суммарного объема передаваемых данных между серверами.

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

Необходимым условием оптимальности размещения фрагмента данных является превышение объема локально обрабатываемых данных над данными, обрабатываемыми удаленно:

(9)

Достаточным условием оптимальности размещения l-го ФД является выполнение следующих ограничений:

1) на минимально возможное число копий l-го ФД, , где - текущее число копий l-го ФД, а - минимально допустимое количество копий;

2) на возможное место размещения l-го ФД.

Предполагаемый эффект V^эф от размещения копии l-го ФД на j-м сервере равен разности текущего и оценки будущего объема :

(10)

Метод децентрализованного управления размещением ФД на СБД. Операция удаления копии l-го ФД на i-м СБД характеризуется минимальным объемом передаваемых данных между СБД, поскольку она предполагает лишь оповещение всех серверов об удалении данной копии и получение ответных квитанций о внесении соответствующих изменений в их схемы размещения ФД. Суммарные затраты на ее реализацию имеют вид:

(11)

где и - объем запроса на оповещение всех серверов и квитанции на него, как правило, не превышающие установленного размера пакета, S - число серверов.

Затраты на копирование l-го ФД на j-й СБД складываются из объема передаваемого фрагмента данных от СБД-инициатора к СБД-получателю и дополнения в виде запроса на обновление переданной копии, устаревшей за время передачи:

, (12)

где - объем l-го ФД,

- размер запроса на обновление переданной копии ФД.

Каждому из решений на удаление или копирование l-го ФД ставятся в соответствие достигаемый в результате его реализации эффект и прогнозируемые затраты. Очевидно, что через некоторое время будет сформировано новое локальное представление структуры, которое в общем случае не будет совпадать с текущим. Реализация всех решений по трансформации может потребовать значительно больше времени, чем . Поэтому за отведенный интервал времени необходимо реализовать наиболее эффективные решения из множества P, которые бы максимизировали суммарный эффект от проведения реструктуризации МРБД при минимальных затратах.

Такая формулировка цели оптимизации и ограничений позволяет свести исходную задачу к известной задаче о ранце (рюкзаке) с ограничением на максимальный «вес» каждого предмета:

целевая функция:

...