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

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

Южно-Российский государственный политехнический университет (НПИ) им. М.И. Платова, Новочеркасск

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

А.Н. Скоба

Айеш Ахмед Нафеа Айеш (Ирак)

В.К. Михайлов

Как было отмечено в работах [1,2], одной из важных задач, без решения которой невозможна разработка распределённой информационной системы, является рациональная организация вычислительного процесса, реализованного в среде ЛВС. В процессе работы ЛВС поддерживает распределённую базу данных (РБД) [3], которая обладает несомненными преимуществам перед централизованной (меньшее время ответа для пользователей, меньшее время блокировки записей, более простое планирование заявок). Однако при проектировании таких систем будут существовать большие общие пересекающиеся массивы данных, в которых определенная информация будет присутствовать многократно. Неоптимальное обращение с информационными ресурсами может с одной стороны увеличить время реакции системы на запросы пользователей, а с другой стороны, может стать очень дорогим для пользователей [3]. Поэтому в одной из задач, возникающих при проектировании распределённой информационной системы на базе ЛВС, является задача оптимального размещения информационных ресурсов (частей РБД) по узлам ЛВС, включающая выбор топологии сети, критерия эффективности, конструирование математической модели, разработку алгоритма оптимизации и ее программную реализацию.

Исходными данными для моделирования являлись [4-7]: множество узлов сети - U={U₁,…,U_s,…,U_n}; множество пользователей - A={A₁,…,A_s,…,A_n}; множество отношений - R={R₁,…,R_j,…,R_d};множество интенсивностей формирования запросов - Л={л₁,…,л_s,…,л_n}; множество запросов на чтение - Q={Q₁,…,Q_l,…,Q_q};множество объёмов отношений - V={V₁,…,V_j,…,V_d};скорость считывания в узлах - VV={VV₁,…,VV_s,…,VV_n};скорость записи в узлах - VD={VD₁,…,VD_s,…,VD_n};скорость передачи данных по каналу связи - и; постоянная задержка при передаче данных по каналу связи - и₀; постоянная задержка при обработке в узле - б₀; производительность процессора U_z-го узла - PU_z; матрица вероятностей формирования запросов пользователями - , где элемент f_sl представляет собой вероятность того, что s-й пользователь сформировал l-й запрос; матрица объёмов считываемой информации

,

где b_lj-объём считываемой информации по l-му запросу на чтение из j-го отношения;

,

где

причём ; матрица распределения отношений по узлам ЛВС -

,

где

причём

.

Таким образом задача оптимального размещения РБД по узлам ЛВС по критерию среднего времени реакции системы сводится к задаче

,

при ограничении (1)

Подробный расчёт величины в зависимости от особенностей используемой архитектуры распределённой системы был выполнен в работах [4-7].

Как показал проведённый анализ, задача (1) является задачей нелинейной комбинаторной оптимизации с булевыми переменными. Ввиду того, что функция имеет сложный вид, а так же ввиду отсутствия в настоящее время эффективных алгоритмов решения такого класса задач (кроме как метод полного перебора) [8-10], для решения задачи (1) может быть применен разработанный авторами эвристический алгоритм, основанный на численном прогнозировании поведения целевой функции и использующий представления о базах данных, как о точках многомерного пространства, а об узлах, в которых эти базы размещаются как о кластерах. Обозначим -вероятность того, чтоi-й пользователь обратится к j-му отношению;-средний объем информации, циркулирующий между i-м пользователем и j-м отношением.

Полагаем (i=, j=),k=0.

Выбираем для j=: K_sj=max{K_ij} (i=) и отношение помещаем в s-ю ПЭВМ.

Вычисляем значения {} (r=), по формуле (7), а значение по формуле (8) работы [4]. Если k?0 - переходим на шаг 7, в противном случае - на следующий шаг.

Полагаем {}={} i= и.

Выбираем ={},i=и =max({}/{}), где : =, =1.

Если =-1 или {}/{}={},то переходим на шаг 8, иначе отношение помещаем в м-ю ПЭВМ, полагаем k=k+1и переходим на шаг 3.

Если < - переходим на шаг 4, в противном случае полагаем =-1и переходим на шаг 5.

Конец. (Полученное распределение и будет оптимальным).

Целессообразно пункты алгоритма 1-3 выполнять уже на этапе конструирования исходных данных, что совершенно очевидно приведёт к уменьшению количества итераций алгоритма и соответственно, к уменьшению временных затрат на его работу.

Данный алгоритм был программно реализован на языке C# при следующих исходных данных: скорость считывания в s-м узле КБ/сек, ; скорость записи в оперативную память s-го узла КБ/сек, ; производительность процессора s-го узла операций/сек, ; скорость передачи данных по каналу связи КБ/с; постоянная задержка при передаче по каналу ; постоянная задержка при обработке в узле ; объём j-го отношения КБ, ; объём считываемой информации КБ , по l-му запросу на чтение из j-го отношения, по l-му запросу на чтение из j-го отношения; КБ - объем информации, получаемый после процессорной обработки по запросу на чтение из отношения. Расчет проводился на компьютере на базе процессора фирмы Intel, с тактовой частотой 3,0 ГГц. В таблицах 1-3 приведены некоторые результаты машинных экспериментов, полученных для решения задачи оптимального размещения информационных ресурсов по узлам распределённой информационной системы: в таблице№ 1-на базе файл-серверной архитектуры при отсутствии блокировок , в таблице№ 2-на базе файл-серверной архитектуры с учётом влияния блокировок на уровне всей базы данных , в таблице№ 3-без учёта влияния блокировок на базе двухуровневой архитектуры «клиент-сервер», в таблице №4- с учётом влияния блокировок на базе двухуровневой архитектуры «клиент-сервер».

Таблица 1

Таблица 2

Таблица 3

Таблица 4

Здесь МПП - метод полного перебора; ЭА - эвристический алгоритм; - среднее время реакции системы для оптимального размещения РБД, полученного МПП; - среднее время реакции системы для оптимального размещения РБД, полученного ЭА.

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

Литература

эвристический запрос пользователь

1. Бойко В.В., Савенков В.М. Проектирование баз даных информационных систем. М.: Финансы и статистика, 1989. 351 с.

2. Кузнецов Н.А., Кульба В.В., Косяченко С.А. Методы анализа и синтеза модульных информационно-управляющих систем. М.: ФИЗМАТЛИТ, 2002. 880с.

3. Цегелик Г.Г. Системы распределённых баз данных. Львов: СВИТ,1990. 167 с.

4. Скоба А.Н., Состина Е.В. Математическая модель оптимального размещения распределенной базы данных по узлам ЛВС на базе файл-серверной архитектуры. // Инженерный вестник Дона. 2015. № 2. URL: ivdon.ru/ru/ magazine/archive/n2y2015/2881.

5. Скоба А.Н., Логанчук М.Л. Математическая модель функционирования распределённой информационной системы на базе архитектуры «файл-сервер» с учётом влияния блокировок // Инженерный вестник Дона.2015. № 3. URL:ivdon.ru/ru/magazine/archive/n3y2015/3276.

6. Скоба А.Н., Состина Е.В. Математическая модель оптимального размещения распределенной базы данных по узлам ЛВС на базе двухуровневой клиент-серверной архитектуры. // Инженерный вестник Дона. 2015. № 2. URL: ivdon.ru/ru/ magazine/archive/n2y2015/2882.

7. Скоба А.Н., Панфилов А.Н. Модель оптимального размещения информационных ресурсов по узлам распределенной информационной системы предприятия на базе двухуровневой архитектуры “клиент-сервер” с учетом влияния блокировок // Изв. вузов. Электромеханика. 2017. Т. 60, № 2. С. 77-84.

8. Antunes C.H. et al. A Multiple Objective Routing Algorithm for Integrated Communication Network // Proc. ITC-16.-1999.V. 3b. pp. 1291-1300.

9. Chakka R., Harrison P.G. A Markov modulated multi-server queue with negative customers. Ihe MM CPP/GE/c/LG-queue // Acta Informatika/-2001.-v. 37. pp. 785-799.

10. Круглый З.Л. Алгоритмы расчёта моделей структур вычислительных систем с различными классами заданий // Управляющие системы и машины. 1989. № 4. С. 22-24.

Размещено на Allbest.ru