МОДЕЛЬ ОЦЕНКИ ОПЕРАТИВНОЙ ДОСТУПНОСТИ К РЕСУРСАМ ЕДИНОГО ИНФОРМАЦИОННОГО ПРОСТРАНСТВА

MODEL OF THE ASSESSMENT OF OPERATIONAL ACCESSIBILITY TO RESOURCES OF THE COMMON INFORMATION SPACE

Valery Kuvaev

ph.D., doctoral student of the Military Academy of communications,

Russia, St. Petersburg

Igor Saenko

ph.D., professor of Military Telecommunication Academy,

Russia, St. Petersburg

Sergey Bushuev

ph.D., professor of Military Telecommunication Academy,

Russia, St. Petersburg

АННОТАЦИЯ

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

ABSTRACT

The paper considers the analytical model of an assessment of operational accessibility to resources of a common information space. Settings of optimization tasks for different modes of functioning of the system are given. The technique for solving these tasks based on using genetic algorithms is discussed.

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

Keywords: common information space, information resource, operational accessibility, genetic algorithm.

Единое информационное пространство (ЕИП) является неотъемлемым компонентом построения современных крупномасштабных автоматизированных систем. Одной из важнейших задач, решаемых при создании ЕИП, является задача обеспечения оперативного доступа к информационным ресурсам со стороны пользователей ЕИП. Для достижения этой цели в настоящей статье предлагается аналитическая модель оценки оперативной доступности к ресурсам ЕИП. При этом в модели используются различные критерии в зависимости от режимов работы с ЕИП, под которыми понимаются on-line и off-line режимы.

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

Постановка задачи заключается в следующем. Исходными данными являются:

1. множество узлов ЕИП A = {A₀, A₁, …, A_N}, где A₀ – центральный узел ЕИП (центр обработки данных), A₁, …, A_N – узлы, соответствующие локальным автоматизированным системам (АС), N – количество АС, интегрируемых в ЕИП;
2. каждый узел A_i характеризуется допустимым объемом памяти B_i, i = 1, …, N, отводимым для хранения информационных ресурсов (для центрального узла A₀ отсутствуют ограничения на допустимый объем памяти узла);
3. множество информационных ресурсов, распределяемых по узлам сети ЕИП, R = {R₁, …, R_M}, M – количество ресурсов;
4. каждый ресурс R_j характеризуется своим объемом V_j, j = 1, …, M;
5. матрица частот обращений к ресурсам ||f_ij|| с запросами z_ij, где z_ij – запрос со стороны пользователя, находящегося на узле A_i на получение из ЕИП ресурса R_j;
6. матрица пропускных способностей сети ЕИП ||w_ik||, где w_ik ­– пропускная способность между узлами A_j и A_k (i, k = 1, …, N).

Требуется: распределить множество ресурсов {R_j} по узлам {A_i} таким образом, чтобы, с одной стороны, максимизировать показатели оперативной доступности ресурсов T_ОД, а с другой – удовлетворять требованиям по допустимому объему памяти на узлах сети ЕИП.

Показатели оперативной доступности ресурсов введем для двух случаев функционирования ЕИП: режима реального времени (on-line) и режима произвольного времени (off-line).

Введем переменные задачи. Положим, что переменная x_ij равна 1, если ресурс R_j располагается на узле A_i, и x_ij равна 0 – в противном случае. Тогда матрица булевых переменных ||x_ij|| полностью определяет решение по распределению ресурсов.

Матрица переменных обладает следующим свойством:

 i = 1, …, N; j = 1, …, M).                                      1)

Иными словами, в каждой j-ой строке матрицы может присутствовать только одна единица.

Определим с учетом (1), чему равно время обработки запроса z_ij, т. е. запроса на получение ресурса R_j пользователем с узла A_i:

                                               2)

Тогда с учетом (2) показатель T_ОД для режима off-line может быть выражен в виде среднего времени, рассчитываемого по всем пользовательским запросам, осуществляемым в заданный период времени:

                           3)

Суммарный объем ресурсов, размещенный на i-ом узле, определяется следующим выражением:

                                                                              4)

Тогда ограничения задачи выражаются в виде совокупности неравенств вида

, j = 1, …, M.                                                     5)

Выражения (3) и (5) определяют критерий задачи для режима off-line (т. е. задачи оценки оперативной доступности ресурсов ЕИП)

В случае on-line режима дополнительно в состав исходных данных включается требования по своевременности получения ресурсов по запросам. Эти требования задаются вектором D = {D_j}, где D_j ­– максимально допустимое время получения ресурса R_j. С учетом D можно следующим образом записать требование по своевременности получения ресурсов по запросам:

, j = 1, …, M,                        6)

где: – максимальное время получения ресурса R_j среди всех пользователей.

Тогда для T_ОД в режиме on-line предложим следующей вид:

                     7)

Выражения (5), (6) и (7) определяют постановку задачи для режима on-line, которую можно рассматривать как задачу обеспечения оперативной доступности к ресурсам ЕИП.

Рассмотрим теперь методику решения этих задач.

Как видно из (3), (5), (6) и (7), задача оценки оперативной доступности ресурсов относится к классу задач линейного целочисленного (точнее – булевого) программирования, а задача обеспечения – к классу нелинейного булевого программирования. В этой связи для решения задачи оценки можно предложить известные традиционные методы, например, алгоритм Гомори, метод ветвей и границ и т. д. [1, с. 43]. Однако для решения задачи обеспечения оперативной доступности ресурсов, особенно в условиях большой размерности этой задачи, классические методы являются неэффективными. Необходимы разработка и применение эвристических методов решения этой задачи [2, с. 8]. Поэтому предложим единую методику решения обеих задач, основанную на применении эвристического алгоритма. В качестве последнего выберем генетический алгоритм (ГА). Генетические алгоритмы достаточно хорошо себя зарекомендовали для решения оптимизационных задач, относящихся к целочисленному и булеву программированию [3, с. 647].

Основные решения по реализации ГА всегда связываются с формированием хромосомы и функции пригодности (ФП). Хромосома выполняет строковое кодирование потенциальных решений. ФП позволяет оценивать эти решения.

В качестве хромосомы предлагается использовать строку вида Chr = <y₁, …, y_M>, где y_j – номер узла сети ЕИП, на котором размещен ресурс Rj. В качестве ФП предлагается функция следующего вида:

                                                 8)

где: V_j (Chr) и T_ОД (Chr) – суммарный объем ресурсов на узле A_i и показатель оперативной доступности, соответственно, определяемые алгоритмически в зависимости от хромосомы Chr; d(u) – индикаторная функция, которая равна 1, если u0, и равна 0 – в противном случае.

Список литературы:

1. Бодров В.И., Лазарева Т.Я., Мартемьянов Ю.Ф. Математические методы принятия решений. – Учеб. пособие. Тамбов: Изд-во Тамб. гос. тех. ун-та, 2004 г. – 124 с.
2. Латыпов Н.Н., Ёлкин С.В., Гаврилов Д.А. Инженерная эвристика / под.ред. А.А. Вассермана. – М.: Астрель, 2012. – 320 с.
3. Saenko I., Kotenko I. Genetic Algorithm for Role Mining Problem // Proceedings of the 19th International Euromicro Conference on Parallel, Distributed, and Network-Based Processing, PDP 2011. Ayia Napa, 2011, Р. 646–650.