автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Анализ вероятностно-временных характеристик высоконадёжных телекоммуникационных систем

На правах рукописи

Козырев Дмитрий Владимирович

Анализ вероятностно-временных характеристик высоконадёжных телекоммуникационных систем

05.13.17 - Теоретические основы информатики

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

2 4 О КГ 2013

Москва - 2013

005535600

005535600

Работа выполнена на кафедре теории вероятностей и математической статистики Российского университета дружбы народов.

Научный руководитель:

доктор физико-математических наук, профессор

Рыков Владимир Васильевич

Официальные оппоненты:

Ведущая организация:

Ивницкий Виктор Аронович, д.ф.-м.н.,

профессор, профессор кафедры автоматизированных систем управления Московского государственного университета путей сообщения,

Гайдамака Юлия Васильевна, к.ф.-м.н.,

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

Московский институт электроники и математики Национального исследовательского университета «Высшая школа экономики»

Защита диссертации состоится «15» ноября 2013 г. в 15 час. 30 мин. на заседании диссертационного совета Д 212.203.28 при Российском университете дружбы народов по адресу: г. Москва, ул. Орджоникидзе, д. 3, ауд. 110.

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

¿Г

Автореферат разослан

октября 2013 г.

Ученый секретарь диссертационного совета

\/!А VoAz&pf

М.Б.Фомин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы.

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

Состояние современного мирового общества характеризуется бурным развитием и внедрением информационных технологий во все сферы человеческой деятельности. Развитие телекоммуникационных и информационных технологий и их интеграция привели к появлению нового класса услуг, получивших название инфокоммуникационных. Расширение спектра услуг, быстрое и непрерывное увеличение количества их потребителей и соответствующее увеличение объемов передаваемой информации выдвигает в ряд первоочередных задач повышение производительности телекоммуникационных систем при соблюдении требований высокой надёжности, которая согласно эксперту в области надёжности сетей и систем связи В.А.Нетесу2'3 , является одним из важнейших факторов, влияющих на качество обслуживания (Quality of Service, QoS), в силу чего требования к надёжности включаются практически во все соглашения об уровне обслуживания (Service Level Agreement, SLA).

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

Во-первых, рост требований к качеству со стороны пользователей заставляет операторов все больше заботиться о качестве обслуживания (Quality of Service, QoS).

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

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

1Хуродзе P.A. Некоторые новые подходы в математической теории надёжности// Изв. HAH РА и ГИУА. Сер. ТН. 2004. Т. LVII, № 1.

гНетес В.А. Надёжность сетей связи в период перехода к NGN /,/ Вестник связи. Л'1 9. 2007.

3Нетес В. А. Надёжность сетей связи: тенденции последнего десятилетия // Электросвязь. Л"* 1. 1998.

передачи данных следующего поколения (Next Generation Networks, NGN). На то обстоятельство, что надёжность является одной из проблемных областей при переходе к NGN и на связанные с этим риски обращали внимание в своих публикациях руководители Управления связи Федерального агентства связи.4,5

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

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

Цель диссертационной работы.

1. Построение математической модели надёжности системы сложной иерархической структуры с произвольными законами распределения длительностей безотказной работы и восстановления элементов системы.

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

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

4. Разработка методов вычисления стационарных, нестационарных и квазистационарных характеристик надёжности сложных систем различной структуры и их исследование.

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

4 Лее аотэ А.К. Особенности создания н функционирования сетей связи нового поколе-ния//Фотон-Экспресс. 2006. К* 5.

5Букринский СЛ. Проблема обеспечения устойчивости, живучести и безопасности сетей связи - основная задача управления сетями следующего поколения//4-я Междун. конф. "Управление сетями электросвязи - основа надёжности функционирования телекоммуникационной инфраструктуры". М., 200fi

ния её вероятностно-временных характеристик на основании данных, близких к реальным.

Результаты, выносимые на защиту.

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

2. Для многомерного марковского альтернирующего процесса введено понятие квазистационарных вероятностей состояний и разработаны алгоритмы и программные средства вычисления основных вероятностно-временных характеристик систем различной структуры.

3. Выполнено численное исследование скорости сходимости ф.р. в.б.р. к показательному распределению для систем различной, в том числе иерархической структуры. Показана устойчивость скорости сходимости ф.р. в.б.р. к предельному распределению.

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

Научная новизна. Все основные результаты диссертации являются новыми.

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

2. Для марковских моделей надёжности впервые введено понятие квазистационарных вероятностей и предложен алгоритм их вычисления.

3. В отличие от известных работ по исследованию асимптотического поведения систем с быстрым восстановлением элементов разработаны алгоритмы и процедуры анализа скорости сходимости ф.р. в.б.р. системы к предельному распределению и показана её нечувствительность к виду ф.р. в.б.р. и восстановления элементов.

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

Методы исследования.

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

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

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

Реализация результатов работы. Результаты диссертации вошли в программу для ЭВМ "Расчет характеристик надёжности иерархических систем". 6'7

Результаты диссертации использовались в рамках гранта Министерства образования и науки РФ, Государственный контракт №14.514.11.4071.

6Дата регистрации РОСПАТЕНТом в Реестре программ для ЭВМ 13.03.2013г., патент №2013612765

7Свидетельство о регистрации в ИНИПИ РАО ОФЭРНиО №18761 от 17.02.2012г., инвентарный номер ФГАНУ "ЦИТиС": 50201251501.

Кроме того, результаты диссертации были внедрены в учебный процесс в рамках учебной дисциплины "Прикладные задачи теории вероятностей", читаемой студентам 3-го курса направлений "Прикладная математика и информатика" и "Компьютерные науки" РУДН.

Апробация работы.

Основные результаты диссертации докладывались на

1. Шестой Международной конференции "Математические методы в теории надёжности. Теория. Методы. Приложения. (MMR-2009)" (Москва, 22-27 июня 2009 г.),

2. Четырнадцатой Международной конференции "Распределенные компьютерные и телекоммуникационные сети: теория и приложения (DCCN-2010)" (Москва, 2G 28 октября 2010 г.),

3. Научной сессии НИЯУ МИФИ-2011 (Обнинск, 24-30 января 2011 г.),

4. Пятнадцатой Международной конференции "Распределенные компьютерные и телекоммуникационные сети: теория и приложения (DCCN-2011)" (Москва, 26-28 октября 2011 г.),

5. Первом Всероссийском семинаре "Прикладная теория вероятностей и теоретическая информатика" (Москва, 17-18 апреля 2012 г.),

6. Международной конференции "Теория вероятностей и ее приложения", посвященной 100-летию со дня рождения Б.В.Гнеденко (Москва, 26-30 июня 2012 г.),

7. Международной конференции "Современные вероятностные методы анализа, проектирования и оптимизации информационно-телекоммуникационных сетей" (Минск, 28-31 января 2013 г.),

8. Всероссийской конференции (с международным участием) "Информационно-телекоммуникационные технологии и математическое моделирование высокотехнологичных систем" (Москва, 22-26 апреля 2013 г.),

9. Втором Международном семинаре "Прикладная теория вероятностей и теоретическая информатика" в рамках XXXI Международного семинара по проблемам устойчивости стохастических моделей (Москва, 23-27 апреля 2013 г.).

Результаты диссертации докладывались и обсуждались на научных и научно-практических семинарах в Российском университете дружбы народов.

Публикации. Материалы диссертации опубликованы в 13 печатных работах, из них 5 — статьи в научных журналах, причём 3 из них опубликованы в рецензируемых научных журналах и изданиях, рекомендованных ВАК. Основные результаты представлены в работах, опубликованных в изданиях, рекомендованных ВАК, и получены лично соискателем. В работах, опубликованных в соавторстве, личный вклад соискателя состоит в разработке моделей и методов их исследования, доказательстве утверждений, разработке алгоритмов и программных средств для проведения численных расчетов, численном расчете и интерпретации полученных результатов.

Структура и объем диссертации. Диссертация состоит из списка сокращений, введения, 4 глав, разделенных на разделы, заключения, списка литературы и приложений. При ссылке на раздел слева добавляется номер главы. Нумерация формул, рисунков и таблиц привязана к номерам глав. Список литературы содержит 62 наименования. Текст изложен на 128 страницах, включая 20 рисунков, 6 таблиц и 3 приложения.

СОДЕРЖАНИЕ РАБОТЫ

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

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

В разделе 1.1 приведены результаты классических работ по исследованию надёжности систем с быстрым восстановлением элементов и изучению асимптотических свойств распределений их времени жизни. Приведена формулировка предельной теоремы Б.В.Гнеденко и аналогичный предельный результат А.Д.Соловьева с другой параметризацией.

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

В разделе 1.3 дан обзор работ B.C. Королюка и А.Ф. Турбина, в которых предложен близкий к работам Гиеденко и Соловьева подход к анализу сложных систем с быстрым восстановлением, опирающийся на метод фазового укрупнения состояний таких систем.

В разделе 1.4 приведены сведения о различных традиционных методах марковизации процесса, описывающего поведение системы, дан обзор работ в этой области.

Во второй главе построена модель надёжности сложной системы в виде многомерного обобщенного альтернирующего процесса, который характеризуется произвольным временем пребывания каждой компоненты в своих бинарных состояниях. Марковизация процесса, описывающего поведение системы, осуществлена путем введения дополнительной переменной с расширением пространства состояний £ = Е х Я", на котором определен многомерный процесс

Z(t) = {J(t), X(t)},

где J(i) € Е — состояние объекта; X(f) ей" - время, проведенное каждой его компонентой в своём состоянии с момента последнего попадания в него. Для марковизированного процесса Z(t) выведены дифференциальные уравнения Колмогорова для плотностей распределения (п.р.) вероятностей состояний (pj(t; x)dx = Р{ Jt(i) = jlt X^t) £ dxtl i = l,n}), доказаны существование и единственность их решения и получен общий вид их решения.

Теорема 1. Система уравнений Колмогорова для п.р. вероятностей состояний pj(t, х) в области О < Xj <t < со, j = 1, 2,... п имеет вид

01 1 <к<п °Хк

а граничные и начальное условия с помощью 5-фуикции Дирака S(t) и символа Кронекера ¿jto представимы в виде

t

Pj(i;xfc(0)) = SyoS(t) + ^p-h(t-,xk(u))~f{k,jk){u)du (j £ E). о

Здесь использованы обозначения:

• jfc = O'li • --jk-u 1 ~ ibik+ъ ■ • - in),

• Xfc(u) = (xu- ■ - xk-uu,Xk+u- ■ - xn),

• 7*A(*) = ci-*-(x)l3»(x),

• 7j(x) = E иш(хк) = E <*k(xk) + E ßk(xk).

1 <k<n k:jk= 0 k:jt=1

Теорема 2. Общее решение системы уравнений Колмогорова для п.р. вероятностей состояний имеет вид:

Pj(i;x) = hi(t-xu...,t- хп) [] i1 - - Bk(xk))h,

\<к<п

где функции /ij(x) находятся исходя из граничных и начального условий

t

ftj(t - Хк(О)) = <5j,oö(i) + | h]k(t - xt(u))c(fci i-jk)(u)du (j 6 £). 0

Здесь

• Ak(x), Bk(x) — ф.р. времени б.р. и восстановления элементов, которые предполагаются дифференцируемыми;

• ak(x), bk(x) — соответствующие п.р.;

• C(k,jt)(u) = а\~'к(и)Ь£(и) — п.р. времени, проведённого к-ой компонентой процесса в своём состоянии с момента последнего попадания в него.

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

Pj(x) = lim Pj(i;x) = Cj П (1 - Ak(xk))l^(l - Вк(хк)Г,

t—> oo

1<к<п

где константы Cj находятся, исходя из граничных условий и условия нормировки Pj = 1. и стационарных вероятностей макро-состояний (с учетом je е

условия нормировки):

Vi =

„I-Jtut

Pj(x)dx= П

хеД»

ak + h

Показана нечувствительность Pj к виду ф.р. Ак(х) и Вк(х).

Для решения задачи нахождения вероятности б.p. Rx(t), среднего в.б.р. ЕТ и построения функции надёжности системы было исследовано распределение в.б.р. Т = inf{£ : J(t) е Е\) системы, для нахождения которого следует решать систему уравнений Колмогорова, сделав множество отказовых

состояний Ei поглощающим: Fx(t) = Р{Т < i} = Е

je£i

Рассмотрен частный случай многомерного альтернирующего марковского процесса, когда ф.р. в.б.р. Ак(х), В^{х) предполагаются показательными, для которого получены более детальные результаты в явном виде. В частности, с целью исследования функционирования системы до момента ее отказа на основании доказанного факта8 о существовании пределов р-} — limpj(i) условных вероятностей пребывания системы в каждом из её состояний на её жизненном цикле: pj(t) = Р {J(f) = j \t < Т) = ^щ, получен аналитический метод расчета и разработан алгоритм и программные средства для вычисления квазистационарных вероятностей pj и связанных с ними характеристик для систем различной структуры и с разными типами резервирования.

Глава 3 посвящена численному анализу надёжности, скорости сходимости ф.р. в.б.р. к показательному распределению и расчету вероятностно-временных характеристик систем с различными распределениями времени восстановления элементов и различными типами резервирования в предположении быстрого восстановления элементов. Для проведения численных расчетов разработаны программные модули в среде MATLAB.

В разделе 3.1 рассматривается модельный пример системы облегченного дублирования с показательно распределенными в.б.р. и восстановления элементов с интенсивностями отказов основного и резервного элементов а и qi («1 < а), соответственно, и интенсивностями восстановления /3. Для данной системы найдена равномерная оценка скорости сходимости ф.р. в.б.р. системы к показательной, проведено сравнение с приближенной оценкой, полученной В.В.Калашниковым9 для аналогичного частного примера.

Теорема 3. При р = ^ —> оо имеет место равномерная сходимость вероятности б.р. системы за время t в масштабе его среднего в.б.р.: R(t) е-', причем скорость сходимости шиеет порядок е:

Скорость сходимости исследована также графически с помощью графиков функций надёжности в масштабе среднего в.б.р. системы и численно с помощью квантилей уровней высокой надёжности.

В разделах 3.2 и 3.3 для исследования влияния вида распределения времени восстановления на характеристики надёжности систем исследует-

8Hykov V. Multidimensional Alternative Processes as Reliability Models j I Proceedings of BWWQT-2013. - 2013. P.147-15G.

9Kalashnikov V. V. Geometric Sums: Bounds for Rare Events with Applications: Risk Analysis, Reliability, Queueing// Kluwer Academic Publishers, Dordrecht/Boston/London, 1997. - 285 pages.

ся сначала поведение однородной системы многократного резервирования с восстановлением (М™|М|1) с показательной функцией распределения длительности восстановления, а затем аналогичное исследования для системы (Ми\Ег1апд(к)\1) с временем восстановления элементов, имеющим распределение Эрланга.

В разделе 3.4 проводится сравнение характеристик надёжности систем (М"'|М|1) и (Мп\Ег1апд(к)\1) в предположении быстрого восстановления их элементов. Подтверждается вывод о нечувствительности скорости сходимости ф.р. в.б.р. системы к показательной к виду распределения длительности восстановления элементов при быстром их восстановлении.

В разделе 3.5 проводится сравнение эффективности дублированной системы с быстрым восстановлением и п-элементной системы резервирования в терминах среднего в.б.р. Были выведены рекуррентные соотношения, которые позволяют значительно упростить вычисление ПЛ п.р. в.б.р., ПЛ функции надёжности и среднего в.б.р. для систем с большим числом элементов.

Теорема 4. Для п-элементпой системы нагруженного резервирования, отказ которой происходит при отказе т из п элементов, имеет место рекуррентная формула для нахождения ПЛ плотности распределения в. б.р. системы:

где 2ц = 1,

Ч = (п — т + 1)а + /?,

гк = {{п-т + к)а + Р)гк-\ - (п - тп + к)аРгк-2, к = 2,ш-1.

Следствие 1. В условиях теоремы 4 для нахождения среднего в.б.р. системы справедлива рекуррентная формула:

Следствие 2. В условиях теоремы 4 для нахождения ПЛ функции надёжности системы справедлива рекуррентная формула:

(п — тп + к)\а'

к '

Д(») =

1

В разделе 3.6 продолжается изучение влияния вида распределения времени восстановления на характеристики надёжности систем, для чего исследуется система (Мп\РН\1) многократного резервирования с восстановлением с ф.р. времени восстановления элементов В(х) фазового типа.

Теорема 5. Стационарное распределение вероятностей состояний {ро,Рк, к ■■ 1, п} системы надёжности (Мп\РН\1) выражается в форме усеченной мат-рично-геометрической прогрессии:

рц\Уо, если к = 1,

к

PoW^JJWj, если к = 2, п - 1, ^

»i-i

PoWÓj|W¿Wn, если к = п,

где вектор и матрицы к = 1,п выраэюаются через параметры распределений в. б.р. элементов и длительности их восстановления. Вероят-

п _

ностъ ро определяется из условия нормировки: Рк = 1, где рк = р'1 —

к=о

стационарная вероятность того, что в системе исправны к элементов.

Построение ф.р. в.б.р. системы, функции надёжности системы и нахождение среднего в.б.р. системы достигается путем исследования соответствующего процесса Х(Ь) с отказовым множеством в качестве поглощающего множества состояний. Для этого находится решение системы дифференциальных уравнений Колмогорова в терминах преобразований Лапласа (ПЛ) :

р'(а)(Ь - А) = Ь' (2)

с матрицей интенсивностей переходов А модифицированного процесса с поглощающим множеством отказовых состояний, единичной матрицей I, вектором Ь' = (1,0,..., 0) размерности (пт + 1) и квадратной невырожденной матрицей блочно-днагоналыюго вида — А размерности (пт + 1) х (пт + 1).

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

0.1 0.98 ■ 097 — 0.96-|0 95-К 094 0 930 92091 0.»^

о-1

Р"10

002 004 0 06 008

0.1 0.12 1/ЕТ

0.14 0.16 0.18

о.:

Рис 1. Сходимость нормированной функции надежности системы <Л/,|РЯ|1) к г"' с ростом ОТНОГИТГ-ЛЫюП СКОрО<ТИ КИШ1КШ1ЧП11 р. УвСЯИЧСИНыП МВСШТий.

008

0 07

006

005

й 0 041"

■г. 003

о 002

о

001

0

-0 01

4102

по в.«"*"- р-1

* * по рчо

р»100

и.»

1.3

2 9

УЕТ

33

Рис. 2. Равномерна* сходимость функции надежности системы (Л/}|Р//|1) в масштаб,- во среднего в.б.р. к нрсделыюЛ функции с"' с ростом р.

В 1>аздсле 3.7 в качестве содержательного примера применения аппарат» многомерных альтернирующих процессов для изучения надёжности неодно-|юдных телекоммуникационных систем рассмотриваеггся восстанавливаемая гибридная система беспроводной передачи мультимедийной информации, состоящая из трёх атмсс(]>ерных оптических линий связи: лазерного канала, радиоканала миллиметрового диапазона и радиоканала сантиметрового диапазона (иод управлением IEEE 802.tin). Рассматривалось два тина peiepen-

Рнс. 3. Блок-схем» гибридной системы передачи мультимедийной информпции

рования третьего канала (Wi-Fi) холодный и горячий резерв, которые, как следует из результатов численного анализа, практически не нлияют на пропускную способность гибридной системы, однако с[>еднео в.б.р. в случае холодного резерва в 12,5 раз больше. Для вычислений использовались данные, полученные в результате продолжительного натурного эксперимента.10

В четвертой главе в разделах 4.1 и 4.2 построена общая модель надежности сложной иерархической многокомпонентной системы. Эта система составлена из блоков нескольких уровней. Каждый блок и следующие за ним блоки образуют иерархическую структуру того же типа, что и основная система. Блоки самых нижних уровней (элементы) подвержены постепенным отказам своего типа, те. распределения длительностей б.р. элементов зависят от их типов.

В силу быстрого «установления элементов системы, произвольные рас-п|>еделения времени восстановления элементов и подсистем асимптотически показательны с параметрами, обратными к соответствующим средним в.б.р.

10П М ВнШИСВСКИЯ, О.В.СоШМН. Об ainoft МОКЛИ ОПТИКИ П|Ю« IMVWTÍ.'n.WXT» ППЧХЖОЛО.'КХ«ОГО П1-б|»1Лиого кллдля сию» и« оспм* люсрпоЛ и рАлпотгогатогяЛ /' Проблемы млформвпгкп 2010. Т 6. .V" 2. С. 4J-S8.

элементов. Элементы с несколькими состояниями могут быть модифицированы в соответствующие бинарные подсистемы. Поэтому, для простоты ограничиваемся случаем систем с бинарными элементами и подсистемами.

Отдельно рассмотрены случаи однородных и неоднородных систем. Для исследования надёжности всей системы разработан и программно реализован итерационный метод: сначала исследуется надёжность ее подсистем, начиная с нижних уровней, а затем вычисленные характеристики надёжности подсистем становятся исходными данными для подсистем следующего уровня иерархии и т.д. Расчет вероятностно-временных характеристик подсистем производится на основании результатов, полученных в рамках моделей одноуровневых систем, исследованных в главах 2 и 3, в зависимости от типа системы и вида ф.р. времени восстановления элементов.

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

1) относительная скорость восстановления постоянна для любого уровня иерархии, т.е. Рк = ^ = Р = const; в этом случае среднее в.б.р. подсистемы к-го уровня определяется рекуррентно следующим образом:

ВТЬ = =... = (^l^-V, =

2) относительная скорость восстановления возрастает с каждым уровнем, т.е. рк = = в этом случае среднее в.б.р. подсистемы к-го уровня определяется через среднее в.б.р. (к — 1)-ого уровня:

ЕТк = |ЕГ*_, + ^ETl, = ^Е Т*_х.

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

В Заключении сформулированы основные результаты диссертационного исследования.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Козырев Д.В. Методика анализа дерева отказов как общепринятый инструмент описания сложных технологических систем и универсальное средство общения для специалистов в области исследования надёжности и анализа риска // Информационные технологии и научно-технический перевод: Сборник статей. - М.: РУДН, 2008, 4 с.

2. Kozyrev D., Rykov V. Reliability model for hierarchical systems //VI Международная конференция Mathematical Methods in Reliability (MMR-2009): Расширенные тезисы докладов (Москва, 22-29 июня 2009г.) - Москва, изд-во РУДН, 2009. - С. 207-213, 7 с.

3. Козырев Д.В., Рыков В.В. Анализ надёжности иерархических систем: регенеративный подход// М.: Автоматика и телемеханика, №7, 2010, 14 с.

4. V. V. Rykov, D. V. Kozyrev. Reliability model for hierarchical systems: Regenerative approach// Automation and Remote Control, July 2010, Volume 71, Issue 7 , pp 1325-1336

5. Козырев Д.В. К анализу скорости сходимости характеристик надёжности систем с быстрым восстановлением// 14-я Международная конференция Distributed Computer and Communication Networks (DCCN-2010): Тезисы докладов (Москва, 26-28 октября 2010г.) - С.232-238, 7 с.

6. Kozyrev D., Rykov V. On the Reliability Modeling of Hierarchical Systems// Mathematical and Statistical Models and Methods in Reliability. Applications to Medicine, Finance, and Quality Control, изд-во «Birkhauser», серия «Statistics for Industry and Technology», 2010. - 14 c.

7. Козырев Д.В. Анализ асимптотического поведения характеристик надёжности дублированных систем при «быстром восстановлении»// Вестник Российского университета дружбы народов, серия «Математика. Информатика. Физика.» - №3. М: Изд-во РУДН, 2011 - С. 49-57, 9 с.

8. Козырев Д.В. Численный анализ систем надёжности при быстром восстановлении и многократном резервировании// 15-я Международная конференция Distributed Computer and Communication Networks (DCCN-2011): Тезисы докладов (Москва, 26-28 октября 2011г.) С. 122 129, 8 с.

9. Козырев Д.В., Рыков В.В. Многомерные альтернирующие процессы и их применение в моделях надёжности// Всероссийская конференция «Прикладная теория вероятностей и теоретическая информатика» (Москва, 17-18 апреля 2012 г.) - М.: Институт проблем информатики, РАН, С. 44-45, 2 с.

10. Козырев Д.В., Рыков В.В. Многомерный обобщенный альтернирующий процесс как модель надёжности// Международная конференция «Тео-

рия вероятностей и ее приложения» (Москва, 26-30 июня 2012 г.) - Москва: ЛЕНАНД, С. 254-255, 2 с.

11. Вишневский В.М., Козырев Д.В., Рыков D.B. К оценке надёжности гибридной системы передачи мультимедийной информации// Международная научная конференция «Современные вероятностные методы анализа, проектирования и оптимизации информационно-телекоммуникационных сетей» (Минск, 28 31 января 2013 г.) Минск: Издат. центр БГУ, С. 192 203, 12 с.

12. Вишневский В.М., Козырев Д.В., Рыков В.В. О нестационарных характеристиках надёжности телекомуникационных систем связи гибридной структуры// Всероссийская научная конференция с международным участием «Информационно-телекоммуникационные технологии и математическое моделирование высокотехнологичных систем» (Москва, 22-26 апреля 2013 г.) - М: Изд-во РУДН, С. 83-85, 3 с.

13. Kozyrev D. Analysis of a repairable redundant system with PH distribution of restoration times of its elements// XXXI International Seminar on Stability Problems for Stochastic Models (23 - 27 April 2013, Moscow) - Moscow: Institute of Informatics Problems, RAS, Pp.43-44.

ДРУГИЕ НАУЧНЫЕ ТРУДЫ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Козырев Д.В. Расчет характеристик надёжности иерархических систем (электронный ресурс)// ИНИПИ РАО ОФЭРНиО (свидетельство о регистрации №18761 от 17 декабря 2012г.), ФГАНУ «ЦИТиС» (инвентарный номер 50201251501)

2. Козырев Д.В. Расчет характеристик надёжности иерархических систем (программа для ЭВМ)// Бюллетень Роспатента №2, патент №2013612765.

Козырев Дмитрий Владимирович Анализ вероятностно-временных характеристик высоконадежных телекоммуникационных систем

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

Kozyrev Dmitry Vladimirovich

Analysis of probability-time characteristics of high-reliability telecommunication systems

In this thesis multivariate alternating process is applied to the development of the reliability model of complex systems with generally distributed failure-free times and recovery times of their elements. For the Markovized process the equations for the state probabilities density functions are derived, the unique existence of their solution is proved and the general form of their solution is obtained. The stationary distribution of state probabilities is worked out and its insensitivity to the distributions is proved. In Markov case the existence of quasi-stationary state probabilities is proved and efficient numerical algorithms and programs are developed for calculation of main probability-time characteristics for systems of different structure. Numerical analysis of the convergence rate of the system's lifetime distribution to the exponential distribution is held and its insensitivity is demonstrated. The obtained theoretical results were applied to modeling and analysis of the hybrid multimedia data transmission system with the use of experimental data.

Подписано в печать:

07.10.2013

Заказ № 8825 Тираж - 100 экз. Печать трафаретная. Объем: 1 усл.п.л. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 wvvw.autoreferat.ru

Российский Университет Дружбы Народов

На правах рукописи

04201363533

Козырев Дмитрий Владимирович

Анализ вероятностно-временных характеристик высоконадежных телекоммуникационных систем

05.13.17 - Теоретические основы информатики

ДИССЕРТАЦИЯ на соискание ученой степени кандидата физико-математических наук

Научный руководитель

д. ф.-м. н., проф.

Рыков Владимир Васильевич

Москва - 2013

Содержание

Список сокращений........................................................5

Введение ......................................................................6

Глава 1. Предварительные сведения.................22

1.1. Методы марковизации моделей надёжности...........22

1.2. Надежность систем с быстрым восстановлением.........22

1.3. Равномерные оценки вероятности редких событий в теории надежности ...............................24

1.4. Фазовое укрупнение состояний сложных систем.........25

Глава 2. Многомерный альтернирующий процесс как модель

надежности сложных систем........................................27

2.1. Общая модель надежности.....................27

2.1.1. Примеры...........................28

2.2. Многомерный обобщенный альтернирующий процесс как модель надежности...........................31

2.2.1. Определение. Уравнения Колмогорова..........31

2.2.2. Распределение времени безотказной работы.......37

2.3. Многомерный альтернирующий марковский процесс......38

2.3.1. Определение. Уравнения Колмогорова..........38

2.3.2. Обращения блочно-диагональных матриц........41

2.3.3. Стационарные вероятности ................45

2.3.4. Распределение времени безотказной работы.......46

2.3.5. Квазистационарные вероятности .............48

Глава 3. Численный анализ. Примеры................53

3.1. Система облегченного дублирования с восстановлением .... 53

3.2. Система многократного резервирования с восстановлением (М™|М|1) ...........................61

3.3. Система многократного резервирования с восстановлением (Мп\Ег1апд{к)\\).......................63

3.4. Сравнение характеристик надежности систем (М™\М\\)

и (Мп\Ег1апд(к)\1).........................65

3.5. Сравнение эффективности дублированной системы с быстрым восстановлением и п-элементной системы резервирования в терминах среднего в.б.р.........................68

3.6. Система {Мп\РН\\) многократного резервирования с восстановлением при РН-распределении времени восстановления элементов ................................73

3.6.1. . Процесс ...........................74

3.6.2. Стационарное распределение ...............75

3.6.3. Распределение в.б.р. системы...............81

3.6.4. Численный пример: система (М2\РН\1)........83

3.7. Пример: гибридная система передачи данных..........87

3.7.1. Модель............................88

3.7.2. Исходные данные......................92

3.7.3. Горячий резерв широкополосного радиоканала.....93

3.7.4. Холодный резерв широкополосного радиоканала .... 95

Глава 4. Анализ надёжности иерархических систем ......98

4.1. Постановка задачи..........................98

4.2. Общая модель............................100

4.2.1. Алгоритм исследования надежности системы в целом . 103

4.3. Расчет вероятностно-временных характеристик однородных иерархических систем...........................105

4.4. Расчет вероятностно-временных характеристик неоднородных иерархических систем........................108

Заключение..................................116

Литература..................................117

Приложение А. Алгоритм обращения блочно-диагональных матриц .....................................125

Приложение Б. Свидетельство о регистрации электронного ресурса ....................................127

Приложение В. Свидетельство о государственной регистрации программы для ЭВМ .........................128

АОЛС в.б.p. вер. б.р м.о. МП

мип

OAK

пл

ПРГ п.р. п.ф. с.в.

СУ СУР ф.р. NGN

QoS

RF

SLA

Список сокращений

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

Next Generation Networks (сети передачи данных следующего поколения)

Quality of Service (качество обслуживания) Radio Frequency (радиочастота)

Service Level Agreement (соглашение об уровне обслуживания)

Введение

Актуальность темы.

Создание надежных систем является стратегической целью любого индустриального общества. С момента становления надёжности как отдельной научно-технической дисциплины в задачах обеспечения надёжности сложных технических систем плодотворно применялись математические методы, которые в настоящее время составляют важную часть общей теории надёжности. При этом математическая теория надёжности развивается в соответствии с теми тенденциями [1], которые проявляются в ведущих областях техники и технологий.

Состояние современного мирового технологического общества характеризуется бурным развитием и внедрением информационных технологий во все сферы человеческой деятельности. Развитие телекоммуникационных и информационных технологий и их интеграция привели к появлению нового класса услуг, получивших название инфокоммуникационных. Расширение спектра услуг, быстрое и непрерывное увеличение количества их потребителей и соответствующее увеличение объемов передаваемой информации выдвигает в ряд первоочередных задач повышение производительности телекоммуникационных систем при соблюдении требований высокой надёжности, которая согласно эксперту в области надёжности сетей и систем связи В.А.Нетесу [2, 3], является одним из важнейших факторов, влияющих на качество обслуживания (Quality of Service, QoS), в силу чего требования к надёжности включаются практически во все соглашения об уровне обслуживания (Service Level Agreement, SLA).

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

Во-первых, рост требований к качеству со стороны пользователей застав-

ляет операторов все больше заботиться о качестве обслуживания (Quality of Service, QoS).

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

Наконец, свои специфические проблемы в обеспечении надёжности выдвигает идущий в настоящее время активный переход к построению сетей передачи данных следующего поколения (Next Generation Networks, NGN). На то обстоятельство, что надёжность является одной из проблемных'областей при переходе к NGN и на связанные с этим риски обращали внимание в своих публикациях руководители Управления связи Федерального агентства связи [4, 5].

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

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

Цель диссертационной работы.

1. Построение математической модели надёжности системы сложной иерархической структуры с произвольными законами распределения длительностей безотказной работы и восстановления элементов системы.

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

ния элементов.

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

4. Разработка методов вычисления стационарных, нестационарных и квазистационарных характеристик надёжности сложных систем различной структуры и их исследование;

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

Научная новизна. Все основные результаты диссертации являются новыми.

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

2. Для марковских моделей надёжности впервые введено понятие квазистационарных вероятностей и предложен алгоритм их вычисления.

3. В отличие от известных работ по исследованию асимптотического поведения систем с быстрым восстановлением элементов разработаны алго-

ритмы и процедуры анализа скорости сходимости ф.р. в.б.р. системы к предельному распределению и показана её нечувствительность к виду ф.р. в.б.р. и восстановления элементов.

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

Методы исследования.

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

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

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

Результаты, выносимые на защиту.

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

2. Для многомерного марковского альтернирующего процесса введено понятие квазистационарных вероятностей состояний и разработаны алгоритмы и программные средства вычисления основных вероятностно-временных характеристик систем различной структуры.

3. Выполнено численное исследование скорости сходимости ф.р. в.б.р. к показательному распределению для систем различной, в том числе иерархической структуры. Показана устойчивость скорости сходимости ф.р. в.б.р. к предельному распределению.

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

Реализация результатов работы. Результаты диссертации вошли в программу для ЭВМ "Расчет характеристик надёжности иерархических си-

)) 1 2 стем .

Результаты диссертации использовались в рамках гранта Министерства образования и науки РФ, Государственный контракт №14.514.11.4071.

Кроме того, результаты диссертации были внедрены в учебный процесс в рамках учебной дисциплины "Прикладные задачи теории вероятностей", читаемой студентам 3-го курса направлений "Прикладная математика и информатика" и "Компьютерные науки" РУДН.

Содержание работы

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

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

В разделе 1.1 приведены результаты классических работ по исследованию надёжности систем с быстрым восстановлением элементов и изучению асимптотических свойств распределений их времени жизни. Приведена формулировка предельной теоремы Б.В.Гнеденко и аналогичный предельный результат А.Д.Соловьева с другой параметризацией.

В разделе 1.2 приведены сведения о развитом В.В.Калашниковым методе исследования систем надёжности, опирающимся на теорию регенерирующих процессов. Приведен полученный им для одного частного примера результата регистрации РОСПАТЕНТом в Реестре программ для ЭВМ 13.03.2013г., патент №2013612765 2Свидетельство о регистрации в ИНИПИ РАО ОФЭРНиО №18761 от 17.02.2012г., инвентарный номер ФГАНУ "ЦИТиС": 50201251501.

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

В разделе 1.3 дан обзор работ B.C. Королюка и А.Ф. Турбина, в которых предложен близкий к работам Гнеденко и Соловьева подход к анализу сложных систем с быстрым восстановлением, опирающийся на метод фазового укрупнения состояний таких систем.

В разделе 1.4 приведены сведения о различных традиционных методах марковизации процесса, описывающего поведение системы, дан обзор работ в этой области.

Во второй главе построена модель надёжности сложной системы в виде многомерного обобщенного альтернирующего процесса, который характеризуется произвольным временем пребывания каждой компоненты в своих бинарных состояниях. Марковизация процесса, описывающего поведение системы, осуществлена путем введения дополнительной переменной с расширением пространства состояний £ = Е х , на котором определен многомерный процесс

где Л(£) Е Е — состояние объекта; Х(£) £ Щ. — время, проведенное каждой его компонентой в своём состоянии с момента последнего попадания в него. Для марковизированного процесса Z(t) выведены дифференциальные уравнения Колмогорова для плотностей распределения (п.р.) вероятностей состояний х)с!х = = ji, Х^) € г = 1,п}), доказаны суще-

ствование и единственность их решения и получен общий вид их решения.

Теорема 1. Система уравнений Колмогорова для п.р. вероятностей состояний х) в области 0 < х3 < £ < оо, ] = 1, 2,... п имеет вид

Z(t) = {J(t), X(t)}

а граничные и начальное условия с помощью 6-функции Дирака 5(Ь) и символа Кронекера ¿^о представимы в виде

щк(ЪхкЫЬ{ык)(и)<1и 0 е Е).

Здесь использованы обозначения:

• Зк = Оь • • -Зк-1, 1 - 3к,3к+1, • • • Зп),

• Кк{и) = {х1,... хк-1,и, Хк+и ■ ■ ■ хп),

• 7*^0*0 = а~3к{х)153кк{х))

•7](х) = Е 7(ш{хк)= Е Е РкЫ.

1 <к<п к\]к = 1

Теорема 2. Общее решение системы уравнений Колмогорова для п.р.„вероятностей состояний имеет вид:

ф\х) = Щ{Ь-хъ...,г-хп) П {1-Ак{хк))1~^{1-Вк{хк)У\

1 <к<п

где функции /^(х) находятся исходя из граничных и начального условий

Здесь

- ХкЫ)с(к,1-к)(и)(1и О е Е).

Ак(х), Вк(х) — ф.р. времени б.р. и восстановления элементов, которые предполагаются дифференцируемыми;

ак(х), Ьк(х) — соответствующие п.р.;

с(к^к)(и) = {и) — П-Р- времени, проведённого к-ой компонен-

той процесса в своём состоянии с момента последнего попадания в него.

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

^(х) = Итр^х) = <3 П {1-Ак{хк))1-^{1-Вк(хк)У\ '

г—>оо -1- ■*-

1 <к<п

где константы С-} находятся, исходя из граничных условий и условия нормировки Р] = 1 > и стационарных вероятностей макро-состояний (с учетом

зеЕ

условия нормировки):

хбД™ 1<к<п

акЧ%к ак + Ьк

Показана нечувствительность р-3 к виду ф.р. Ак(х) и Вк{х).

Для решения задачи нахождения вероятности б.р. Ят(£), среднего в.б.р. ЕТ и построения функции надёжности системы было исследовано распределение в.б.р. Т = т£{£ : ,/(£) Е Е\} системы, для нахождения которого следует решать систему уравнений Колмогорова, сделав множество отказовых состояний Е\ поглощающим: = Р{Т < £} = ^

Рассмотрен частный случай многомерного альтернирующего марковского процесса, когда ф.р. в.б.р. Лк(х), Вк{х) предполагаются пок