Asymptotic stationary probability distribution of the physical experiment data total volume.pdf Введение Кибер-физическая система (Cyber-Physical System (CPS)) представляет собой сложную распределенную систему, управляемую или контролируемую компьютерными алгоритмами, основанную на технологии интернет-вещей (Internet of Things (IoT)) [1]. Основным отличием является очень плотное взаимодействие между вычислительными процессами и процессами физическими, поэтому можно сказать, что CPS - это комплексная система из вычислительных и физических элементов, которая постоянно получает данные из окружающей среды и использует их для дальнейшей оптимизации процессов управления. К CPS можно отнести «умные» сети электроснабжения, системы управления «умным» транспортом, «умные» города. Кибер-физические системы управляют значительными объемами данных, получаемых от датчиков. Вычислительная обработка должна быть эффективной и своевременной, поскольку физические процессы продолжаются независимо от результатов вычислений. Для удовлетворения этого требования CPS должны обладать пропускной способностью или мощностью, необходимой для поддержки немедленной обработки, то есть обладать необходимым для обработки данных объемом ресурсов. В качестве математических моделей широкого спектра технических устройств и инфокоммуникационных и кибер-физических систем наиболее логично рассматривать ресурсные системы массового обслуживания (СМО). Методы теории массового обслуживания широко используются для описания процесса передачи информации. В классических СМО приборы играют роль необходимых для обслуживания ресурсов, но кроме приборов и/или мест ожидания заявкам могут потребоваться различные дополнительные ресурсы случайного объема, занимаемого на время обработки, передачи и хранения требований. Кроме того, из-за неоднородности предоставляемых услуг (телефонные звонки, отправка текстовых сообщений, видео- и аудиосообщений, использование интернет) необходимо учитывать объем передаваемой информации [2-4]. В связи с этим актуальна разработка новых ресурсных моделей, сформулированных в терминах СМО, которые позволили бы оценить объем используемого ресурса. Моделированию беспроводных систем связи с помощью ресурсных СМО посвящено большое число публикаций, наиболее полный обзор которых дан в работах [5-9]. Однако в основном в них делается анализ различных схем распределения ресурсов в системах c детерминированными или дискретными требованиями заявок к ресурсам [10, 11]. В настоящей статье проводится исследование характеристик систем массового обслуживания со случайными требованиями к объему занимаемого ресурса беспроводной сети с расщеплением (копированием) заявок. В отличие от известных ранее, рассматриваемые модели позволят сделать оценку необходимых объемов резервируемых ресурсов для трафика интернета вещей и выработать стратегию распределения ресурсов с конкурирующим трафиком. 1. Постановка задачи Рассмотрим систему массового обслуживания MMPP(ν)|GI|∞ с копированием заявки на второй фазе, на вход которой поступает MMPP-поток заявок, управляемый цепью Маркова k(t) = 1, 2, …, K, задаваемой матрицей инфинитезимальных характеристик Q = ||qνk||, ν, k = 1, …, K и диагональной матрицей условных интенсивностей Λ = diag{λ1, …, λK}. Дисциплина обслуживания определяется следующим образом. Заявка, поступившая в систему, занимает любой свободный прибор на первой фазе и требует для обслуживания случайное количество некоторого ресурса G0(ν) и обслуживается в течение случайного времени, имеющего функцию распределения B0(x). После обслуживания на первой фазе заявка переходит на вторую и обслуживается на первом блоке в течение случайного времени с функцией распределения B1(x), а также копируется на второй блок, где обслуживается с функцией распределения B2(x). Также заявка требует случайное количество некоторого ресурса на первом блоке с функцией распределения G1(ν) и на втором с G2(ν). По окончании обслуживания заявка покидает систему, освобождая все занятые приборы и ресурсы. Количество занимаемых ресурсов и время обслуживания не зависят друг от друга. Пусть Vi(t) - суммарный объем занятого ресурса в системе в момент времени t, где i = 0, 1, 2. Поставим задачу нахождения характеристик многомерного случайного процесса . Отметим, что исследуемый процесс не является марковским. Для его исследования применим метод многомерного динамического просеивания [12, 13]. Изобразим четыре параллельных оси времени. Ось «MMPP» будет отображать события входящего потока, ось под номером 0 будет соответствовать первому просеянному потоку, ось под номером 1 - второму, ось под номером 2 - соответственно третьему просеянному потоку. Зафиксируем произвольный момент времени T. Пусть имеется набор функций , значения которых лежат в диапазоне [0,1] и обладают свойством , для любых t. Событие входящего потока может просеяться только на одну из трех осей 0, 1, 2, либо ни на одну. Вероятность того, что заявка входящего потока, поступившая в систему в момент времени : - сформирует событие потока на оси 0, т.е. к моменту времени T не закончит обслуживание на первой фазе, равна ; - сформирует событие потока на оси 1, т.е. к моменту времени T закончит обслуживание на первой фазе, на втором блоке второй фазы и не закончит на первом блоке второй фазы, равна ; - сформирует событие потока на оси 2, т.е. к моменту времени T закончит обслуживание на первой фазе, на первом блоке второй фазы и не закончит на втором блоке второй фазы, равна ; - сформирует события потока на осях 1 и 2, т.е. к моменту времени T закончит обслуживание на первой фазе и будет находиться на двух блоках второй фазы одновременно, равна . Обозначим Wi(t) - суммарный объем занятого ресурса просеянными заявками на i-й оси (i = 0, 1, 2). Нетрудно показать, что (1) для любых . Будем использовать равенство (1) для исследования процесса с помощью процесса W(t). 2. Система дифференциальных уравнений Колмогорова Добавим компоненту k(t) - состояние управляющей цепи Маркова в момент времени t. Тогда полученный четырехмерный процесс k(t) будет марковским. Введем обозначение для его распределения вероятностей: . Для этого распределения составим Δt-методом прямую систему дифференциальных уравнений Колмогорова для k = 1, …, K; : . (2) Начальное условие для решения в момент времени t0 определим в виде где r(k) - стационарное распределение вероятностей состояний цепи Маркова k(t). Введем частичные характеристические функции вида , где - мнимая единица. Тогда (2) можем переписать в виде следующих дифференциальных уравнений: , k = 1, …, K, где . Перепишем эту систему в матричном виде + (3) с начальным условием , (4) где ; r = [r(1), …, r(K)] - вектор стационарного распределения вероятностей состояний управляющей цепи Маркова k(t), удовлетворяющий системе e - единичный вектор-столбец. 3. Метод асимптотического анализа Так как прямое решение уравнения (3) не представляется возможным, то для решения задачи (3), (4) воспользуемся методом асимптотического анализа [9] в условии неограниченно растущей интенсивности входящего потока и предельно частых изменений состояний цепи Маркова. Подставим в уравнение (3) и , где N → ∞ - некоторый параметр, который используется для асимптотического анализа. Тогда с начальным условием (4) можно записать + . (5) Теорема 1. Асимптотическая характеристическая функция первого порядка трехмерного случайного процесса имеет вид + , где - средняя интенсивность входящего потока; a1(i) - математическое ожидание занимаемого ресурса на i-м блоке системы. Теорема 2. Асимптотическая характеристическая функция второго порядка многомерного случайного процесса имеет следующий вид: + . Здесь ; a1(i) и a2(i) - первый и второй начальные моменты случайных величин с функцией распределения вероятностей Gi(y). Доказательство. Представив функцию в виде , (6) получим уравнение относительно функции : + . (7) Выполним здесь следующие замены: . (8) С использованием обозначений (8) уравнение (7) перепишется в виде . (9) Найдем асимптотическое, при , решение этой задачи, то есть . Этап 1. Выполнив предельный переход при в (9), получим . Представим в виде , (10) где - некоторая скалярная дифференцируемая функция, удовлетворяющая условию . Этап 2. Решение уравнения (9) запишем в виде разложения , (11) где - некоторая вектор-строка. Подставив разложение (11) в (9), получим матричное уравнение для вектора g: . Этап 3. Домножим (9) на вектор e, используя (11) и разложение , в результате несложных преобразований получаем , где . Решение этого уравнения с учетом начального условия имеет вид (12) + . Подставив (12) в (10) и выполнив замены, обратные к (6) и (8), запишем приближенное равенство для характеристической функции , которое совпадает с равенством, записанном в формулировке теоремы 2. Теорема 2 доказана. Следствие. Полагая t = T, t0 → - ∞ и учитывая (1), получаем выражения для асимптотической характеристической функции стационарного трехмерного распределения вероятностей суммарного объема занятых ресурсов на каждой фазе системы, которая имеет вид гауссова распределения с вектором математического ожидания и ковариационной матрицей: , где , , , , , , . 4. Численный анализ точности асимптотических результатов Пусть входящий MMPP-поток задан следующими матрицами: , (при получаем асимптотическое условие растущей интенсивности входящего потока). Время обслуживания имеет -распределение вероятностей с параметрами ; ; . Ресурсы равномерно распределены в следующих диапазонах: [0;3] - для первой фазы, [0;2] - для первого блока второй фазы, [0;1] - для второго блока второй фазы. Проведем серию экспериментов, увеличивая значения N, и сравним асимптотические распределения с эмпирическими, используя расстояние Колмогорова: , где F(x) - асимптотическая гауссова функция распределения, а G(x) - эмпирическая. В таблице приведены значения расстояний Колмогорова между асимптотическими и эмпирическими функциями распределения суммарных объемов занятых ресурсов на трех блоках системы (Δ0, Δ1, Δ2). Точность аппроксимации увеличивается с ростом интенсивности входящего потока N, а рис. 1 демонстрирует это. Аналогичный вывод можно сделать и для совместного распределения, как показано в таблице (Δ12) и на рис. 2. Расстояния Колмогорова N 1 3 5 7 10 20 50 100 Δ0 0.372 0.118 0.065 0.044 0.031 0.019 0.012 0.008 Δ1 0.374 0.102 0.056 0.040 0.030 0.020 0.013 0.009 Δ2 0.367 0.115 0.062 0.042 0.028 0.018 0.011 0.008 Δ12 0.374 0.118 0.068 0.046 0.031 0.019 0.012 0.008 Рис. 1. Распределение вероятностей суммарного объема занятого ресурса на каждом блоке (0, 1, 2) системы: а - N = 10; б - N = 100 Рис. 2. Совместное распределение вероятностей суммарного объема занятого ресурса для первого и второго блоков второй фазы системы: а - N = 10; б - N = 100 Заключение Была исследована бесконечнолинейная ресурсная СМО с неограниченным числом приборов, с копированием заявки на второй фазе системы и с входящим MMPP-потоком. С помощью метода асимптотического анализа показано, что совместное асимптотическое распределение вероятности суммарного объема занятого ресурса на каждой фазе системы сходится к трехмерному гауссовскому распределению в асимптотическом условии растущей интенсивности входящего потока. Авторы выражают благодарность профессору Пизанского университета Микеле Пагано за совместную работу в рамках разработки комплекса программ имитационного моделирования и численного анализа рассматриваемой математической модели.

Скачать электронную версию публикации