![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
1. Построим модель вычислительной сети в виде графа со взвешенными рёбрами. Для компьютерного анализа графа
представим его в виде матрицы смежности размерности
(
– количество центров обработки информации (вершин графа)). Элементы матрицы смежности
Для идентификации модели вычислительной сети (граф ) формализуем процессы функционирования центров обработки информации
с использование аппарата теории массового облуживания. В соответствии с постановкой задачи, представим центр обработки информации
в виде системы массового обслуживания с отказами, которая характеризуется основным показателем эффективности – оценка вероятности отказов
,
где – приведённая интенсивность потока задач в центре
. Здесь
– интенсивность потока решений задач.
Рассмотрим канал между двумя центрами обработки информации
. Пусть
,
– соответственно оценки вероятностей отказов в обслуживании задач в центрах
. Тогда возможность прохождения заявки на получение информации по каналу
определяется
. Обозначим его значение через
. С этих позиций проведём идентификацию модели вычислительной сети.
2. Определение наиболее перспективного центра обработки информации для размещения баз данных. Выберем центр обработки информации и построим относительно его кратчайший остовный граф
. Известно, что кратчайший остовный граф типа «дерева» характеризуется минимальной суммой весов при рёбрах. Таким образом, вероятность прохождения заявок на получение информации для решения задач в вычислительной сети будет максимальной.
Для определения наиболее перспективного центра проведём вычислительный эксперимент относительно центров , используя метод оптимизации на графах – алгоритм «Прима».
Алгоритм «Прима» предполагает выполнение следующих действий:
2.1. Выбрать корневую вершину и присвоить всем остальным вершинам из
большие веса
, например
.
2.2. Определить соответствие относительно вершины
, которое составляет множество вершин
соединённых с
ребром. Множеству вершин
соответствует
-я строка матрицы смежности.
2.3. Обновить веса вершин по правилу
2.4. Присоединить вершину к формируемому кратчайшему остовному графу
, если
.
Здесь – множество вершин, присоединённых к данному
этапу строящемуся графу.
Принять , а ребро
,
включить в множество
. На первом этапе работы алгоритма вершина
соответствует минимальному значению веса при рёбрах
. Пусть это будет ребро
. При этом в
включается ребро
.
2.5. Перейти к этапу 2.2 заменив на
и используя вместо
множество
.
Данный процесс продолжается до тех пор пока на некотором этапе не будет сформировано множество
и множество
кратчайшего остовного графа
с корневой вершиной
.
Обозначим через – сумму весов при рёбрах
. Проведём в соответствии с алгоритмом «Прима» анализ кратчайших остовных графов
для корневых вершин
и выберем наиболее перспективный центр обработки информации для размещения баз данных из условия
.
Пусть этому условию соответствует корневая вершина .
Алгоритм выбора второго центра. Для определения второго перспективного центра обработки информации для размещения баз данных будем строить два кратчайших остовных графа и
относительно корневых вершин
и
.
Графы и
строятся поэтапно. Сначала право на принятие решений на этапах 2.2 – 2.4 предоставляется алгоритму «Прима»
относительно корневой вершины
, а затем алгоритму
относительно вершины
.
Данный процесс продолжается до тех пор пока между алгоритмами и
не наступит конфликт. Например, по логике алгоритма
вершина
и ребро
, ранее включены алгоритмом
в строящийся граф
, относится к графу
. Пусть к данному
– этапу работы алгоритмов
,
сумма весов при рёбрах построенных фрагментов графов
,
составляют значения
,
. Обозначим их сумму через
.
Если вершина будет присоединена к фрагменту графа
, то
,
где – вес при ребре
, которое включается в фрагмент графа
;
- вес при ребре
, которое исключается из другого фрагмента кратчайшего остовного графа.
Тогда конфликт между алгоритмами ,
разрешается в пользу
, т.е. вершина
и ребро
включается в фрагмент графа
, если
либо
.
Предложенная методика разрешения конфликтов позволяет на некотором этапе построить фрагменты
,
графов
,
,
при которых значение критерия достигает своего минимума.
Это значит, что для обеспечения эффективности обработки информации множество центров должны получать данные из центра
, а
- из
.
Выбор второго наиболее перспективного центра обработки информации для размещения баз данных осуществляется путём решения последовательности задач
.
По аналогии находится третий перспективный центр обработки информации. В этом случае строятся три фрагмента кратчайших остовных графов относительной ,
и
. В процессе вычислительного эксперимента определяется новый центр обработки информации
, который обеспечивает условие
.
В соответствии с постановкой задачи (5.17) отбор центров множества заканчивается, если выполняется требование
.
Дата публикования: 2015-01-23; Прочитано: 205 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!