Документация Engee
Notebook

Генератор синтетических систем массового обслуживания

Введение

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

В данном примере реализован параметризованный генератор синтетических систем массового обслуживания (СМО). В отличие от ручного формирования исходных матриц, генератор позволяет в автоматическом режиме создавать множественные конфигурации СМО, варьируя количество узлов, степень связности графа, статистические распределения ёмкостей каналов и интенсивностей потоков. Полученные данные экспортируются в стандартизированном формате .xlsx, что обеспечивает прямую совместимость с последующими этапами анализа, включая оптимизацию, основанную на модели M/M/1.

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

Структура СМО

Структуру системы массового обслуживания можно представить в виде квадратной матрицы сети размером :

Где – количество узлов в сети, – суммарная пропускная способность каналов связи (ветвей графа), соединяющих узлы и направленных от узла с номером к узлу с номером .

Направление потоков в системах массового обслуживания можно так же представить в виде квадратной матрицы размером :

Где – количество узлов в сети, – величина потока, направленного от узла с номером к узлу с номером .

Как правило, в реальных системах отсутствуют петлевые потоки (потоки от узла, адресованные самому себе), соответственно диагонали матриц являются нулевыми. Однако для дополнительных экспериментов, в данном примере есть возможность сгенерировать матрицы с ненулевыми диагоналями.

Присоединение файлов и библиотек

Присоединим необходимые библиотеки. В данном примере нам понадобятся библиотеки:

  • LinearAlgebra– для матричных операций;
  • XLSX, Printf– для вывода и сохранения данных;
  • Graphs, Colors, GraphPlot, SimpleWeightedGraphs– для отображения СМО в виде графов.
In [ ]: 
#EngeePkg.purge()
#import Pkg
#Pkg.add(["XLSX", "Graphs", "Colors", "Printf", "GraphPlot", "LinearAlgebra", "SimpleWeightedGraphs"])
using XLSX, Graphs, Colors, Printf, GraphPlot, LinearAlgebra, SimpleWeightedGraphs

Также присоединим необходимые файлы с функциями:

flGplot.jl, flowGraph.jl, "netGraph.jl", nGplot.jl, sGplot.jl", simpGraph.jl – для отображения СМО в виде графов;

optiwrite.jl, "readqs.jl", qsdata.jl– для вывода и сохранения данных.

In [ ]: 
foreach(include, ("flGplot.jl", "flowGraph.jl", "netGraph.jl", "nGplot.jl", "optiwrite.jl", "readqs.jl", "sGplot.jl", "simpGraph.jl","qsdata.jl"))

Исходные параметры

Определим исходные данные.

Параметры матриц смежности:

  • Количество узлов
  • Степень разреженности матриц (параметр, задающий число итераций случайного обнуления связей между узлами, регулирующий плотность топологии сети)
  • Условие: нулевая ли диагональ (имеются ли петли)
  • Условие: симметрична ли матрица (на каждую исходящую линию связи имеется входящая);

Параметры ёмкостей линий связи:

  • Симметрична ли матрица ёмкостей (равны ли ёмкости исходящих и входящих в каждый узел линий связи)
  • Условия: одинаковы ли ёмкости (равны ли все ёмкости линий связи, если равны, то они приравниваются к значению минимальной ёмкости)
  • Минимальная ёмкость
  • Максимальная ёмкость;

Параметры потоков:

  • Условие: имеются ли петлевые потоки
  • Условие: одинаковы ли потоки (равны ли интенсивности всех потоков, если равны, то они приравниваются к значению минимального потока)
  • Минимальный поток
  • Максимальный поток
  • Степень разреженности матриц потоков;
In [ ]: 
# Параметры матриц смежности
узлов = 9  # Количество узлов
разр = 2  # Степень разреженности
диаг = true  # Нулевая ли диагональ
симм = false  # Симметрична ли матрица

# Параметры ёмкостей линий связи
симм_ёмк = false  # Симметрична ли матрица ёмкостей
равно_ёмк = false  # Одинаковы ли ёмкости
мин_ёмк = 1.0     # Минимальная ёмкость
макс_ёмк = 12.0     # Максимальныя ёмкость
диаг_поток = false # Петлевые потоки

# Параметры потоков
равно_поток = false # Одинаковы ли интенсивности потоков
мин_поток = 1.5  # Минимальный поток
макс_поток = 5.5  # Максимальный поток
разр_поток = 4   # Степень разреженности матриц потоков
Out[0]:
4

Функция генерации матриц

Определим функцию, которая принимать исходные данные, и в зависимости от них возвращает матрицу ёмкостей и смежности линий связи, а также матрицу направлений и интенсивностей потоков.

In [ ]: 
function RandQ(qN, spL, dZ, sM, syBw, smBw, minBw, maxBw, dZf, smFl, minFl, maxFl, spFl)

# Cоздание матрицы из единиц и нулей
rM = ones(qN, qN)
for n = 1:spL
    rM = rM .* rand(0:1, qN, qN)
end

# Нули по диагонали
if dZ
    for m in 1:qN
        rM[m, m] = 0
    end
end

# Симметричность матрицы смежности
    if sM
        for p in 1:qN
            for q in p:qN
                rM[q, p] = rM[p, q]
            end
        end
    end

# Ёмкости линий связи
if smBw
    nM = minBw .* rM
else
    nM = (minBw .+ (maxBw .- minBw) .* rand(qN)) .* rM
end

# Симметричность матрицы смежности
if syBw
    for p in 1:qN
        for q in p:qN
            nM[q, p] = nM[p, q]
        end
    end
end

# Матрица направлений потоков
if smFl
    flM = minFl .* rand(0:1, qN, qN)
else    
    flM = minFl .+ (maxFl .- minFl) .* rand(qN, qN)
end

#Разреженность матрицы направлений потоков
for n in 1:spFl
        flM = flM .* rand(0:1, qN, qN)
end

# Нулевая диагональ матрицы направлений потоков
if dZf
    for m in 1:qN
        flM[m, m] = 0
    end
end

return nM, flM
end
Out[0]:
RandQ (generic function with 1 method)

Создание и сохранение матриц

Обращаясь к функции генерации матриц, создадим несколько пар матриц (смежностей и потоков), в зависимости от заданного количества. Сохраним созданные матрицы в xlsx-файлы:

  • NetMatrix.xlsx – матрицы ёмкостей и смежности линий связи;

  • FlowMatrix.xlsx– матрицы интенсивностей и направлений потоков.

    Каждая новая матрица создаётся в новом листе каждого xlsx-файла. Количество листов в каждом файле соответствует количеству пар матриц.

In [ ]: 
количество = 3   # Количество создаваемых пар матриц
QS =  zeros(Float64, узлов, узлов, количество)
Flows = zeros(Float64, узлов, узлов, количество)
for q in 1:количество
    nM, flM = RandQ(узлов, разр, диаг, симм, симм_ёмк, равно_ёмк, мин_ёмк, макс_ёмк, диаг_поток, равно_поток, мин_поток, макс_поток, разр_поток)
    QS[:,:,q] = nM
    Flows[:,:,q] = flM
end
optiwrite(QS, "NetMatrix.xlsx", "Net")
optiwrite(Flows, "FlowMatrix.xlsx", "Flow")

Визуализация

Отобразим параметры СМО, а также отобразим в виде графов:

  • упрощённый вид структур;
  • полный вид структур с указанием направлений и ёмкостей линий связи;
  • интенсивности и направления потоков.
In [ ]: 
n = 1 # Номер пары матриц
СМО, Потоки = qsdata(n)
и, п = simpGraph(СМО);
Граф = sGplot(и, п)
display(Граф)
s, t, bW = netGraph(СМО);
ГрафСМО = nGplot(s, t, bW, "Структура системы массового обслуживания");
display(ГрафСМО)
nfl, nl, flG, flI = flowGraph(Потоки);
ГрафПотоков = flGplot(flG, flI, nl, "Направления потоков");
display(ГрафПотоков)

В системе  массового обслуживания

узлов: 9
потоков: 4
линий связи: 19
In [ ]: 
n = 2 # Номер пары матриц
СМО, Потоки = qsdata(n)
и, п = simpGraph(СМО);
Граф = sGplot(и, п)
display(Граф)
s, t, bW = netGraph(СМО);
ГрафСМО = nGplot(s, t, bW, "Структура системы массового обслуживания");
display(ГрафСМО)
nfl, nl, flG, flI = flowGraph(Потоки);
ГрафПотоков = flGplot(flG, flI, nl, "Направления потоков");
display(ГрафПотоков)

В системе  массового обслуживания

узлов: 9
потоков: 10
линий связи: 17
In [ ]: 
n = 3 # Номер пары матриц
СМО, Потоки = qsdata(n)
и, п = simpGraph(СМО);
Граф = sGplot(и, п)
display(Граф)
s, t, bW = netGraph(СМО);
ГрафСМО = nGplot(s, t, bW, "Структура системы массового обслуживания");
display(ГрафСМО)
nfl, nl, flG, flI = flowGraph(Потоки);
ГрафПотоков = flGplot(flG, flI, nl, "Направления потоков");
display(ГрафПотоков)

В системе  массового обслуживания

узлов: 9
потоков: 5
линий связи: 18

Таким образом, задавая собственные исходные параметры, вы можете создавать собственные пары матриц в удобном xlsx-формате, визуализировать их структуру в виде графов и использовать для дальнейших исследований.

Заключение

Генератор систем массового обслуживания предоставляет исследователям и инженерам инструмент для быстрого создания синтетических, но статистически правдоподобных конфигураций СМО с широким спектром топологических и нагрузочных характеристик. Возможность генерации множества пар матриц (ёмкости — потоки) в стандартизированном формате обеспечивает воспроизводимость экспериментов и служит основой для сравнительного анализа различных алгоритмов оптимизации.

Помимо задачи тестирования производительности и качества алгоритмов оптимизации, представленный генератор может быть применён на практике в следующих областях:

  • Проектирование телекоммуникационных сетей — для генерации множества сценариев нагрузки при выборе топологии и резервировании каналов.

  • Логистика и управление цепочками поставок — для моделирования альтернативных маршрутов доставки с различной пропускной способностью логистических узлов.

  • Образовательный процесс — для создания индивидуальных заданий по теории массового обслуживания и методам оптимизации.

  • Верификация аналитических моделей — путём сравнения результатов оптимизации на синтетических данных с известными аналитическими решениями для частных случаев.

  • Нагрузочное тестирование программных реализаций оптимизационных алгоритмов — для оценки их устойчивости при увеличении размерности задачи (количества узлов и потоков) и степени разрежённости графа.

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