2.2 Описание математической модели реализации задачи
Для расчета входного потока заявок для каждой системы массового обслуживания используем условие стационарности: среднее число заявок, поступающих в систему, равно среднему числу заявок, покидающих ее.
Вероятности перехода заявок (пакетов данных) из одной СМО в другую берутся по условию одинаковыми для СМО с общей начальной вершиной. При этом источник заявок выступает в виде отдельной оконечной вершины, соединенной с каждой из остальных двумя дугами. Расчет характеристик этих дуг не ведется.
Естественным требованием является выполнение условия достоверности события – перехода заявки в некоторую СМО. Математически это выражается в равенстве единице суммы вероятностей перехода во все инцидентные ребра (в том числе и ребро, соединяющее вершину с источником – оконечной вершиной) для всех вершин графа.
Если всего вершин графа исходных данных N, то можно составить систему из N линейных уравнений вида:
,
(1)
где Ri – собственная интенсивность генерации пакетов i-м городом;
λi – общая интенсивность прихода пакетов в i-й город;
– вероятность
перехода сообщения из вершины i
в вершину j.
После преобразования формулы (1) получается формула:
.
(2)
Полученную систему можно решить, используя формулы Крамера. Дополнительная конечная вершина в расчетах не учитывается.
,
(3)
где det
Ai
– определитель матрицы, составленной
из коэффициентов при
,
в которой i-й
столбец заменен на столбец свободных
членов.
det Ai – определитель матрицы, составленной из коэффициентов при .
Искомая интенсивность поступления заявки в СМО будет определяться по формуле:
(4)
Для сети будет существовать установившейся режим, если каждая СМО в сети будет стационарной. Таким образом, для каждой СМО в сети (то есть для каждого ребра графа) должно выполняться условие стационарности для одноканальной СМО по формуле:
, (5)
где
– пропускная способность соответствующего
ребра.
В случае не выполнения данного условия для некоторой СМО необходимо увеличить пропускную способность канала ij либо уменьшить число пакетов, поступающих в вершину i.
Для определения весов ребер графа исходных данных необходимо рассчитать среднее время нахождения заявки (пакета) в данном ребре.
В случае если ребро между двумя вершинами отсутствует, его вес предполагается равным бесконечности и определяется по формуле Литтла:
.
Для поиска оптимального (кратчайшего) пути на графе можно использовать алгоритм Дейкстры. Данный алгоритм работает для случая, когда веса ребер графа положительны (это условие выполняется в сетях передачи данных).
Алгоритм ищет оптимальный путь из начальной (нулевой) вершины графа в конечную (последнюю).
Для работы алгоритма всем вершинам присваивается метка и создается множество окончательно помеченных вершин P. Начальные значения меток у всех вершин, кроме первой, равны бесконечности. Метка первой вершины равна 0. Значение метки некоторой вершины после окончания работы алгоритма будет показывать длину кратчайшего пути от начальной вершины до данной. Начальное множество P содержит только первую вершину.
Шаг 1. Выбрать все непомеченные вершины, смежные с хотя бы одной из помеченных.
Шаг 2. Изменить метки выбранных на шаге первом вершин по следующему правилу: новой метке присваивается минимальное значение сумм старой метки и веса ребра для каждого узла. Здесь минимум берется по всем помеченным вершинам. Индекс минимизации обозначен как i.
Шаг 3. Из всех непомеченных вершин выбрать вершину с минимальной меткой и добавить ее в P. Если множество P содержит все вершины – работа алгоритма заканчивается. Иначе – переход на шаг 1.
Фрагмент программы, реализующей алгоритм Дейкстры, приведен в приложении Б.