651_Zelentsov_B.P._Matrichnye_modeli_funktsionirovanija_

Федеральное агентство связи

Федеральное государственное бюджетное образовательное учреждение высшего образования «Сибирский государственный университет телекоммуникаций и информатики» (СибГУТИ)

Б. П. Зеленцов

МАТРИЧНЫЕ МОДЕЛИ ФУНКЦИОНИРОВАНИЯ СИСТЕМ СВЯЗИ

Учебное пособие

Рекомендовано УМО по образованию в области Инфокоммуникационных технологий и систем связи в качестве учебного пособия для студентов высших учебных заведений, обучающихся по направлению подготовки 11.04.02 и 11.03.02 – «Инфокоммуникационные технологии и системы связи»

(уровень высшего образования – магистратура и бакалавриат)

Новосибирск

2016

УДК 487

Утверждено редакционно-издательским советом СибГУТИ

Научный редактор: д.т.н., профессор В.П. Шувалов

Рецензенты: д.т.н., профессор СПбГУТ О.С. Когновицкий д.т.н., профессор НГТУ В.Г. Китушин к.т.н., доцент НГТУ А.С. Трофимов

к.ф.-м.н., доцент СибГУТИ В.П. Максимов

Зеленцов Б. П. Матричные модели функционирования систем связи: Учебное пособие / Сибирский государственный университет телекоммуникаций и информатики. – Новосибирск, 2016. – 101 с.

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

Кафедры высшей математики и ПДСиМ

©Зеленцов Б.П., 2016

©Сибирский государственный университет телекоммуникаций и информатики, 2016

2

ОГЛАВЛЕНИЕ

2.7.ВЕРОЯТНОСТИ СОСТОЯНИЙ ОДНОРОДНОГО МАРКОВСКОГО ПРОЦЕССА ... 27

2.8.МАТРИЧНЫЕ ДИФФЕРЕНЦИАЛЬНЫЕ УРАВНЕНИЯ И ИХ РЕШЕНИЕ ……….. 29

2.9.ПРЕДЕЛЬНЫЕ ВЕРОЯТНОСТИ ЭРГОДИЧЕСКОГО МАРКОВСКОГО ПРОЦЕССА ……………………………………………………………………………… 31

2.10.ВЫЧИСЛЕНИЕ ПРЕДЕЛЬНЫХ ВЕРОЯТНОСТЕЙ …………………………………. 32

2.11.ВЫВОДЫ ……………………………………………………………………………….. 34

3.2.ФОРМИРОВНИЕ ПОЛУМАРКОВСКОГО ПРОЦЕССА НА ОСНОВЕ ЦЕПИ МАРКОВА ………………………………………………………………………. 38

3.3.ФОРМИРОВНИЕ ПОЛУМАРКОВСКОГО ПРОЦЕССА НА ОСНОВЕ ПРОЦЕССА МАРКОВА ………………………………………………………………… 39

3.4.ИСХОДНЫЕ МАТРИЧНЫЕ ХАРАКТЕРИСТИКИ ПОЛУМАРКОВСКОГО ПРОЦЕССА ………………………………………………………………………………. 40

3.5.ВЫВОДЫ ……………………………………………………………………………….. 41

3.6.ПРИМЕР ПОЛУМАРКОВСКОГО ПРОЦЕССА С ТРЕМЯ СОСТОЯНИЯМИ …….. 41

Глава 4. ВЕРОЯТНОСТНЫЕ ХАРАКТЕРИСТИКИ ПОДМНОЖЕСТВ СОСТОЯНИЙ …………………………………………………………………….. 43

3

4.6.ОТНОСИТЕЛЬНЫЕ ЧАСТОТЫ СОСТОЯНИЙ ……………………………………….

4.7.ХАРАКТЕРИСТИКИ ПОДМНОЖЕСТВА СОСТОЯНИЙ ……………………………. 50

4.8.ВЫВОДЫ ………………………………………………………………...……………….. 51

4.9.ПРИМЕР СИСТЕМЫ С ТРЕМЯ СОСТОЯНИЯМИ 51

…………………………………....

5.2.ПЕРЕХОДЫ МЕЖДУ ПОДМНОЖЕСТВАМИ ЦЕПИ МАРКОВА ………………….. 57

5.3.ПЕРЕХОДЫ МЕЖДУ ПОДМНОЖЕСТВАМИ ПРОЦЕССА МАРКОВА ………….. 58

5.4.ПЕРЕХОДЫ МЕЖДУ ЦИКЛАМИ ……………………………………………………… 58

5.5.НАЧАЛЬНЫЕ УСЛОВИЯ ЦИКЛОВ ……………………………………………………

5.7.ВЫВОДЫ ………………………………………………………………...……………….. 62

5.8.ПРИМЕР СИСТЕМЫ С ТРЕМЯ СОСТОЯНИЯМИ …………………………………...

Глава 6. ЧАСТОТНЫЙ МЕТОД ИССЛЕДОВАНИЯ СИСТЕМ ДЛИТЕЛЬНОГО

6.2.ЧАСТОТЫ СОСТОЯНИЙ ………………………………………………………………. 64

6.3.ЧАСТОТЫ ПЕРЕХОДОВ МЕЖДУ СОСТОЯНИЯМИ ………………………………. 66

6.4.ЧАСТОТЫ ПЕРЕХОДОВ МЕЖДУ ПОДМНОЖЕСТВАМИ СОСТОЯНИЙ ………. 66

6.5.ДРУГИЕ ХАРАКТЕРИСТИКУИ СИСТЕМЫ …………………………………………. 68

6.6.ВЫВОДЫ ………………………………………………………………...……………….. 68

6.7.ПРИМЕР СИСТЕМЫ С ТРЕМЯ СОСТОЯНИЯМИ 69

…………………………………....

7.5.МАТРИЧНЫЕ ХАРАКТЕРИСТИКИ ПЕРЕХОДОВ МЕЖДУ ПОДМНОЖЕСТВАМИ СОСТОЯНИЙ ………………………………………………… 73

7.6.МАТРИЧНЫЕ ХАРАКТЕРИСТИКИ ВОЗВРАЩЕНИЯ В ПОДМНОЖЕСТВА СОСТОЯНИЙ …………………………………………………………………………..… 73

7.7.УСЕЧЕНИЕ МАТРИЧНЫХ ХАРАКТЕРИСТИК ПОДМНОЖЕСТВ ………………... 75

7.8.ХАРАКТЕРИСТИКИ ЭКВИВАЛЕНТНЫХ СОСТОЯНИЙ ………………………….. 75

8.1.МОДЕЛЬ ФУНКЦИОНИРОВАНИЯ РЕЗЕРВИРОВАННОЙ СИСТЕМЫ …………... 78

8.2.МОДЕЛЬ ФУНКЦИОНИРОВАНИЯ ДУБЛИРОВАННОЙ СИСТЕМЫ …………….. 81

8.3.МОДЕЛЬ ФУНКЦИОНИРОВАНИЯ ОБОРУДОВАНИЯ

4

ВВЕДЕНИЕ

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

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

Известно, что для этих целей используют аналитические, алгоритмические и имитационные модели, в которых реализуются разные формы зависимости между исходными и обобщенными характеристиками системы [3]. К аналитическим относятся модели, основанные на логико-вероятностных методах, методах теории графов, методах, основанных на составлении и решении системы дифференциальных уравнений, методах математического программирования, марковских и полумарковских процессах, матричных методах [4]. С усложнением систем аналитические зависимости между исходными и обобщенными характеристиками системы также усложняются, что приводит к громоздким аналитическим моделям. В этом случае целесообразно применять алгоритмическое и имитационное моделирование, которые реализуется в виде машинного алгоритма, когда соответствие между исходными и обобщенными характеристиками системы устанавливаются в числовом виде [3,18]. Математические модели вероятностных систем строят как в дискретном, так и в непрерывном времени.

5

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

Материал пособия содержит как общеизвестные положения из учебной литературы, так и некоторые разработки автора. Сущность матричного метода заключается в описании процесса функционирования системы с дискретным множеством состояний в дискретном или непрерывном времени, при этом производятся преобразования числовых и/или функциональных матриц. Интерес к матричным методам обусловлен их преимуществами: компактностью и простотой преобразований исходных характеристик в обобщенные, наличием стандартного математического обеспечения. Следует отметить, что матричные методы относятся к численно-аналитическим методам, то есть могут быть применены как для численных расчетов, так и для аналитических исследований. С помощью матричного метода могут быть получены обобщенные характеристики разного вида: вероятностные, например, коэффициенты готовности и простоя, временные, например, средняя наработка на отказ, частотные, например, среднее число проверок технического состояния в единицу времени, экономические, например, ожидаемый доход от использования системы, и другие характеристики, связанные со спецификой исследуемой системы [5].

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

Состояние элементов системы образуется некоторой комбинацией параметров. При формировании состояний элементов учитываются специфические внутренние процессы, отражающие особенности исследования. Состояние системы определяется состояниями ее элементов. Переходы системы и ее элементов от состояния к состоянию обусловлено событиями как случайными, так и детерминированными.

6

Состояния и события связаны между собой во времени причинноследственными отношениями. Новое состояние объекта (элемента системы или самой системы) является следствием определенного события, а любое событие является следствием предшествовавшего состояния. Итак, каждому состоянию соответствуют два события: начало состояния и его завершение. В математических моделях, как правило, принимается, что события (переходы между состояниями) происходят мгновенно.

В теории надежности одним из основных случайных событий, приводящих к смене состояния, является отказ объекта. Это событие приводит к смене работоспособного состояния (объект выполняет свои функции) на неработоспособное (объект не выполняет свои функции), а событие «завершение восстановления» – к смене неработоспособного состояния на работоспособное.

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

ИСТОРИЧЕСКАЯ СПРАВКА

Андрей Андреевич Марков (1856–1922) – известный русский математик, выдающийся специалист по теории чисел, математическому анализу и теории вероятностей. Его именем назван широкий класс случайных процессов, описывающих многие явления в разных областях науки и техники. А.А.Марков исследовал случайный процесс с дискретным временем и конечным числом состояний. Впоследствии именем А.А.Маркова названы и другие, более общие классы случайных процессов.

Первоначально А.А.Марков ввел понятие цепи; после его смерти эти процессы стали называть его именем. Цепь Маркова – это математическое понятие, ассоциативно связанное по сходству с механической цепью, которая состоит из дискретных звеньев, и каждое звено непосредственно связано с соседними звеньями. Различие между механическим и математическим понятиями состоит в том, что связи между состояниями цепи Маркова являются не механическими,

авероятностными.

Сразвитием математики понятие цепи Маркова было расширено: появилась теория процессов Маркова (процессов в непрерывном времени) и полумарковских процессов. Зачастую под марковскими процессами понимают все эти виды процессов. Тогда говорят о марковских процессах в широком смысле.

В данном пособии мы будем использовать термины “случайный процесс”, “процесс” и “система” как синонимы.

7

Глава 1. ОДНОРОДНЫЕ МАРКОВСКИЕ ЦЕПИ

1.1.ПОНЯТИЕ ДИСКРЕТНОГО СЛУЧАЙНОГО ПРОЦЕССА В ДИСКРЕТНОМ ВРЕМЕНИ

Пусть имеется некоторая система, множество состояний которой является

дискретным (конечным или счетным): W = {w1, w2, …}. Случайные события, приводящие к переходу системы от состояния к состоянию, происходят в дис-

кретные моменты времени t0, t1, t2,…, которые будем называть шагами и обозначать их в дальнейшем номером шага: n = 0, 1, 2, 3, …

Обозначим через S(n) состояние системы на n-м шаге. Запись S(n) = wj озна-

чает, что на n-м шаге система находится в состоянии wj. Непосредственный пе-

реход из состояния wi в состояние wj будем обозначать через wi wj. На каждом шаге система может находиться только в одном состоянии.

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

мени.

Марковская цепь относится к классу случайных процессов с дискретными состояниями и дискретным временем.

1.2. ПЕРЕХОДНЫЕ ВЕРОЯТНОСТИ МЕЖДУ СОСТОЯНИЯМИ

Из любого состояния wi на n-м шаге система может с некоторыми вероятностями перейти в другие состояния или с определенной вероятностью остаться в нем. Здесь могут быть два основных случая.

1. Вероятности состояний на n-м шаге не зависят от состояния на (n 1)-м шаге. В этом случае говорят, что испытания независимы, так как в каждом испытании событие происходит с одной и той же вероятностью, которая не зависит от исхода на предыдущем шаге.

Пример независимых испытаний. При бросании игральной кости состояние (выпадение числа от 1 до 6) при n-м бросании не зависит от того, какое состояние было при предыдущем, (n 1)-м бросании.

2. Вероятности состояний на n-м шаге зависят от состояния на предыдущем, (n 1)-м шаге.

Марковская цепь относится к классу случайных процессов, вероятности состояний которых на n-м шаге зависят от состояния на предыдущем шаге.

8

Непосредственные переходы между состояниями описываются переходными вероятностями.

Переходной вероятностью (вероятностью перехода) на n-м шаге называется

условная вероятность непосредственного перехода wi wj на n-м шаге при ус-

ловии, что на (n 1)-м шаге система находилась в состоянии wi: pij(n)= p[S(n) = wj / S(n 1) = wi], i, j = 1, 2, 3, …,

где S(n) и S(n 1) обозначение случайного состояния на n-м и (n 1)-м шаге соответственно.

1.3. ПОНЯТИЕ ОДНОРОДНОЙ ЦЕПИ МАРКОВА. ГРАФ СОСТОЯНИЙ

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

pij(n)= pij, i, j = 1, 2, 3, …

Смысл свойства однородности заключается в том, что переходные вероятности не зависят ни от номера шага, ни от состояний на предшествовавших шагах. А это означает, что условия протекания процесса не изменяются с течением времени.

Таким образом, вероятности pi1, pi2, pi3, … образуют распределение вероят-

ностей попадания из состояния wi в состояния w1, w2, w3, … за один шаг. Это распределение не зависит от номера шага, на котором происходит переход.

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

В случайном процессе с дискретными состояниями и с дискретным временем можно выделить три части: прошлое, настоящее и будущее относительно

некоторого шага n0 (рис. 1.1).

Рис.1.1. Разбиение случайного процесса на три части

Однородная марковская цепь обладает свойством независимости будущего от прошлого при фиксированном настоящем. Будущее процесса (системы) зависит только от настоящего и не зависит от прошлого, то есть не зависит от того, каким путем система попала в настоящее. Таким образом, можно сказать, что при фиксированном настоящем будущее и прошлое однородной цепи Маркова независимы.

Это свойство принято называть отсутствием последействия или марковским свойством.

9

Марковское свойство может быть определено также следующим образом:

для любого шага n0 вероятность любого состояния системы в будущем (то есть при n n0) зависит только от ее состояния в настоящем (то есть при n = n0) и не зависит от того, когда и каким образом система пришла в это состояние.

Для наглядности и лучшего восприятия цепь Маркова изображают в виде ориентированного графа, вершинами которого являются состояния, а ребрами – события, обуславливающие непосредственные переходы между состояниями. Каждому ребру приписывается переходная вероятность. Если ребро отсутствует, то переходная вероятность равна нулю. Возможные задержки в прежнем состоянии изображают стрелкой-петлей.

Пример. На рис. 1.2 приведен граф из трех состояний. Множество состояний

системы W = {w1, w2, w3}. Переходные вероятности: p11 = 1/2, p12 = 1/2, p21 = 1/4, p22 = 1/2, p23 = 1/4, p31 = 2/3, p33 = 1/3.

Рис. 1.2. Пример графа из трех состояний

1.4. СРЕДНЕЕ ЧИСЛО ШАГОВ НАХОЖДЕНИЯ В СОСТОЯНИИ

На рисунке 1.3 приведена часть графа состояний, относящаяся к состоянию

wi. Указаны две вероятности: вероятность pii того, что состояние не изменится за один шаг, и вероятность 1 pii того, что состояние изменится за один шаг (pii

< 1).

pii

wi 1 – pii

Рис.1.3. Часть графа состояний, относящаяся к состоянию wi

После попадания в состояние wi система будет находиться в нем случайное число шагов. Найдем среднее число шагов (или математическое ожидание чис-

ла шагов) нахождения в состоянии wi., которое будем обозначать θii(n).

Обозначим через qii(n) вероятность того, что на n-м шаге система будет в состоянии wi при условии, что до n-го шага система не покидала это состояние.

10