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

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

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

,

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

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

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

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

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

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

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

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

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

.

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

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

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

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

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

.

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

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

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

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

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

,

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

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

либо

.

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

, ,

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

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

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

.

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

.

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