Лекция: Методика оптимизации распределения баз данных

1. Построим модель вычислительной сети в виде графа со взвешенными рёбрами. Для компьютерного анализа графа представим его в виде матрицы смежности размерности ( – количество центров обработки информации (вершин графа)). Элементы матрицы смежности

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

,

где – приведённая интенсивность потока задач в центре. Здесь – интенсивность потока решений задач.

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

2. Определение наиболее перспективного центра обработки информации для размещения баз данных. Выберем центр обработки информации и построим относительно его кратчайший остовный граф. Известно, что кратчайший остовный граф типа «дерева» характеризуется минимальной суммой весов при рёбрах. Таким образом, вероятность прохождения заявок на получение информации для решения задач в вычислительной сети будет максимальной.

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

Алгоритм «Прима» предполагает выполнение следующих действий:

2.1. Выбрать корневую вершину и присвоить всем остальным вершинам из большие веса, например .

2.2. Определить соответствие относительно вершины, которое составляет множество вершин соединённых с ребром. Множеству вершин соответствует -я строка матрицы смежности.

2.3. Обновить веса вершин по правилу

2.4. Присоединить вершину к формируемому кратчайшему остовному графу, если

.

Здесь – множество вершин, присоединённых к данному этапу строящемуся графу.

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

2.5. Перейти к этапу 2.2 заменив на и используя вместо множество .

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

Обозначим через – сумму весов при рёбрах. Проведём в соответствии с алгоритмом «Прима» анализ кратчайших остовных графов для корневых вершин и выберем наиболее перспективный центр обработки информации для размещения баз данных из условия

.

Пусть этому условию соответствует корневая вершина .

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

Графы и строятся поэтапно. Сначала право на принятие решений на этапах 2.2 – 2.4 предоставляется алгоритму «Прима» относительно корневой вершины, а затем алгоритму относительно вершины .

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

Если вершина будет присоединена к фрагменту графа, то

,

где – вес при ребре, которое включается в фрагмент графа; — вес при ребре, которое исключается из другого фрагмента кратчайшего остовного графа.

Тогда конфликт между алгоритмами, разрешается в пользу, т.е. вершина и ребро включается в фрагмент графа, если

либо

.

Предложенная методика разрешения конфликтов позволяет на некотором этапе построить фрагменты, графов

, ,

при которых значение критерия достигает своего минимума.

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

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

.

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

.

В соответствии с постановкой задачи (5.17) отбор центров множества заканчивается, если выполняется требование .