Содержание к диссертации
Введение
1 Постановка задачи оптимизации распределения надежности и оптимального резервирования в территориально-распределённых сетях 12
1.1 Разработка логической модели территориально-распределённои сетей 12
1.2 Существующие постановки задачи оптимизации надёжности 16
1.3 Постановка задачи оптимизации надежности и эффективности работы территориально-распределённои сети 21
1.4 Выводы 36
2 Математические модели надёжности территориально-распределённои сети 37
2.1 Введение 37
2.2 Математическая модель надёжности подсистемы СПД-ЦВК-ЦУ территориально-распределённои сети 39
2.3 Математическая модель оценки надёжности территориально-распределённои сети с резервированием ЦВК, ЦУ, и СПД 50
2.4 Применение математических моделей к расчёту надёжности территориально-распределённои сети 65
2.5 Математическая модель надёжности полностью восстанавливаемой в процессе эксплуатации сложной сети 68
2.6 Выводы 79
3 Разработка алгоритма оптимизации надёжности территориально-распределённых сетей 80
3.1 Введение 80
3.2 Исследование функции качества работы сети 81
3.3 Численные результаты сравнения алгоритмов решения нелинейных задач математического программирования 96
3.4 Разработка алгоритма оптимизации надёжности территориально-распределённои сети 102
3.5 Исследование модифицированного алгоритма дифференциальной эволюции для оптимизации надёжности сети 108
3.6 Выводы 115
4 Методика поиска оптимального варианта построения сети 116
4.1 Введение 116
4.2 Разработка методики моделирования и оптимизации надёжности территориально-распределённых сетей 117
4.3 Разработка аналитической модели и оптимизация территориально-распределённой сети 129
4.4 Автоматизация методики оптимизации надёжности территориально-распределённых сетей 147
4.5 Выводы 150
Заключение. Теоретические и практические результаты диссертационной работы 151
- Постановка задачи оптимизации надежности и эффективности работы территориально-распределённои сети
- Математическая модель оценки надёжности территориально-распределённои сети с резервированием ЦВК, ЦУ, и СПД
- Численные результаты сравнения алгоритмов решения нелинейных задач математического программирования
- Разработка методики моделирования и оптимизации надёжности территориально-распределённых сетей
Введение к работе
Актуальность работы. Современный этап развития территориально-распределённых сетей характеризуется ростом сложности и масштабов инфраструктуры, непрерывным повышением требований к качеству предоставляемых услуг, рассмотрением сетей как экономических объектов [19, 50, 51, 63, 69, 113]. При этом проблема надёжности компьютерных сетей остаётся одной из важнейших. Рост надежности элементной базы не успевает за ростом требований к надёжности и сложности систем. Низкая надежность сети приводит к потере клиентов, недополучению прибыли, к штрафным санкциям. Чрезмерные затраты на повышение надёжности могут превысить прибыль, получаемую от предоставления инфокоммуникационных услуг. Международным Союзом Электросвязи разработана рекомендация Е.862 "Планирование сетей связи по общей надёжности". В ней отмечается, что при планировании, проектировании, эксплуатации и техническом обслуживании сетей необходимо учитывать экономические потери вследствие ненадежности, которые несут как владельцы территориально-распределённых сетей, так и их пользователи [63, 69]. Данный документ носит чисто рекомендательный характер и не содержит чётких процедур и моделей, необходимых для решения задачи. В связи с этим требуются новые подходы и разработка новых математических моделей расчёта и оптимизации надежности компьютерных сетей как экономических объектов.
Большой вклад в развитие современных методов теории надёжности, теоретических и практических основ построения надёжных компьютерных сетей внесли многие отечественные и иностранные учёные и инженеры, среди которых следует выделить [1, 2, 8, 9, 17, 18, 24, 42, 48, 54, 55, 62, 63, 71, 79, 82, 84, 96, 114, 121, 126, 127, 130, 146, 151, 152, 153, 158]: Вишневского В.М., Чуканова В.О, Алексеева Е. Б, Герцбаха И.Б., Каштанова В.А., Гнеденко В.Б., Соловьёва А.Д., Ивлева В.В, Ушакова И.А., Полесского В.П., Нетеса В.А, Половко A.M., Рябинина И.А., Филина Б.П., Черкесова Г.Н., Койта Д.В., Зуо М.Дж., Корена Из., Энрико Зио, Шумана М., Тил-манна Ф.А., Кванга С.Л., Куо В.; а также группы учёных и инженеров компаний "ReliaSofl" и "Relex" [150, 163], активно развивающих направление разработки программного обеспечения для задач проектирования высоконадёжных сетей. Основными методами, используемыми при анализе надёжности в вычислительных сетях, являются методы имитационного и аналитического моделирования [138]. Первый метод, несмотря на многие его достоинства, к числу которых, прежде всего, относится достаточно высокая точность, отличает большая трудоемкость создания модели и большое время, необходимое для получения результатов [23, 73, 155, 160, 163]. Основными аналитическими методами, используемыми для анализа вероятностно-временных и надёжностных характеристик вычислительных сетей, являются методы теории массового обслуживания [22, 24, 57, 58]. Проблема оптимизации надёжности компьютерных сетей рассматривалась в работах Дружинина Г.В., Ушакова И.А., Левина Б.Р., Филина Б.П., Черкесова Г.Н., Зуо М.Дж., Корена Из., Шумана М., Тилманна Ф.А., Куо В. [22, 57, 80, 82, 84, 121, 146, 151, 152, 153,]. Однако в существующих работах решение задачи оптимизации надёжности осуществлялось по критерию надёжности и сводилось к задаче оптимального резервирования. Не учитывались доходы от сети, капиталовложения, необходимые для достижения определённого уровня надёжности, затраты на техническое обслуживание сети, потери вследствие простоев сети из-за отказов. Кроме того, большинство существующих моделей надёжности сетей основано на предположении о независимости отказов, экспоненциальном характере распределения времени восстановления [1], идентичности элементов в модели надёжности. Для этих случаев получены точные решения. Реальные потоки восстановления не являются простейшими [17, 84, 45, 85, 93], сети являются экономическими объектами, элементы моделей являются зависимыми, резервные элементы имеют различные надёжностные характеристики. Для этих случаев модели надёжности отсутствуют.
В связи с изложенным, актуальность исследования обусловлена тем, что разработка методики оптимизации надёжности территориально-распределённых сетей, учитывающей неэкс-поненциальность потоков отказов и восстановлений, смешанные сценарии повышения надёжности, зависимость элементов модели надёжности, экономические целевые функции, численные процедуры автоматизации расчётов, позволит существенно повысить эффективность современных территориально-распределённых сетей как экономических объектов.
Целью диссертационной работы является разработка и исследование математических моделей и методики оптимизации надёжности территориально-распределённых сетей.
Для достижения поставленной цели решены следующие научно-практические задачи:
- разработана математическая модель надёжности сети, учитывающая зависимость между состояниями подсистем, и получено выражение для коэффициента готовности в случае простейших потоков отказов и произвольных распределений времени восстановления;
- исследована зависимость коэффициента готовности сети от закона распределения времени восстановления центра управления сетью, что позволило оценить эффективность применения централизованной схемы управления распределённой сетью;
- разработана математическая модель надёжности сети при использовании нагруженного и ненагруженного резерва из п восстанавливаемых подсистем с разной надёжностью, получено выражение для коэффициента готовности и средней наработки на отказ в случае простейших потоков отказов и произвольных распределений времени восстановления;
- разработана модель надёжности сети на основании полученных моделей подсистем, что позволило найти математические выражения для коэффициента готовности сети; - получено явное аналитическое выражение для оптимизации территориально распределённой сети по критерию прибыли, учитывающее полученные ранее аналитические формулы для расчёта надёжности подсистем, что позволило свести задачу оптимизации к задаче нелинейного смешанного программирования, предложен и исследован модифицированный алгоритм дифференциальной эволюции для её решения;
- разработана методика поиска оптимального в смысле надёжности варианта построения сети, включающая модели надёжности подсистем, алгоритм оптимизации и программные средства автоматизации расчётов. На основании данной методики проведён расчёт примера оптимизации надёжности сети.
Объектом исследования являются модели и методики оптимизации надёжности, применяемые при проектировании территориально-распределенных сетей, методы и алгоритмы решения задачи оптимизации надёжности.
Методы исследования. Для решения поставленных задач использованы методы теории вероятностей, теории случайных процессов, математической теории надёжности, математического программирования, аналитического и имитационного моделирования. В процессе исследований использованы работы отечественных и зарубежных ученых, научные обзоры, общегосударственные и отраслевые методические материалы.
Научная новизна работы состоит в разработанной методике оптимизации надёжности сложных систем и её применении к оптимизации надёжности территориально-распределенных сетей, включающей в себя:
1. Математические модели расчёта надёжности восстанавливаемых систем, которые в отличие от известных моделей учитывают зависимость отказов элементов в системе: транспортная сеть - центрально-вычислительный комплекс — центр управления сетью.
2. Аналитические выражения для расчёта коэффициента готовности, вероятности безотказной работы, среднего времени безотказной работы и интенсивности отказов параллельных систем с резервированием, которые в отличие от существующих справедливы для систем большой размерности при произвольном распределении времени восстановления подсистем. Результаты обобщены на сложные структурные модели надёжности и смешанные схемы резервирования, применяемые в территориально-распределенных сетях.
3. Функционал качества работы сети, который в отличие от существующих целевых функций позволяет учесть параметры надёжности подсистем, различные схемы резервирования, стоимости подсистем, экономическую эффективность работы компании-собственника террито риально-распределённой сети. 4. Модифицированный алгоритм дифференциальной эволюции для оптимизации надёжности сети в случае нелинейной целевой функции и целочисленных, непрерывных и дискретных значениях переменных, ускоряющий поиск оптимума по сравнению с известными алгоритмами.
Объём и структура диссертации. Работа включает: введение, четыре главы, заключение, список использованных источников и семь приложений. Основной текст работы изложен на 165 страницах и включает 69 рисунков и 15 таблиц. Список использованных источников включает 163 наименования.
В первой главе описываются известные методы планирования надёжности технических систем с учётом экономических факторов, предлагается новая обобщённая логическая модель надёжности сети, предлагаются новые модели оптимизации; рассматриваются показатели надёжности и экономические показатели, применяемые для оценки качества работы территори-алыю-распределённых сетей [3,4,11,12,39], и, исходя из конкретных условий и целей эксплуатации сети, описывается принцип вывода на основе данных показателей одного интегрированного функционала качества, по которому и предлагается оптимизировать систему. Приводится несколько примеров подобных функционалов с учётом штрафов за простои сети, с учётом среднего времени простоя сети. Среди важнейших направлений надёжностного планирования выделяется задача определения оптимального резервирования, которая неоднократно рассматривалась в литературе [2,66,80,82]. Ввиду некоторых технических особенностей функционирования тер-риториально-распределённых сетей, известные постановки задачи оптимального резервирования требуют некоторой модификации и обобщения. Разработанные ранее постановки применялись для определения оптимальной структуры резерва в задачах радиотехники, где основной и резервные элементы имели одинаковые характеристики надёжности [24], и рассматривались для невосстанавливаемых или частично восстанавливаемых систем при экспоненциальном распределении времени восстановления [128]. Поскольку территориально-распределённые сети являются системами с длительным сроком эксплуатации, и подсистемы, входящие в сосіав сетей, являются сложными программно-аппаратными комплексами, подлежащими ремонту после отказов и сбоев, то возникает необходимость в разработке новых моделей надёжности, отвечающих условиям функционирования современных сетей.
Во второй главе рассматриваются соответствующие модели и выведены формулы для расчёта показателей надёжности [29, 118]. Причем, во многих работах, посвященных анализу компьютерных сетей, отмечается, что законы функционирования большинства из них отличаются от экспоненциальных законов [9,84,93]. Так, например, законы восстановления большинства систем не являются экспоненциальными. Во второй главе для различных сценариев работы подсистем территориально-распределённой сети будут рассмотрены как марковские, так и полумарковские модели надёжности [35, 123,147]. Для части подсистем в территориально-распределённых сетях надежность не может быть улучшена за счёт резервирования. В этом случае необходимо оптимизировать другие параметры надёжности системы, например, среднюю наработку до отказа, интенсивность отказов, среднее время восстановления, и задача планирования и оптимизации надёжности сводится к задаче распределения оптимальных значений надёжности по элементам логической модели [86,100,130,131,148,154]. С каждым элементом модели связывается ещё и некоторая функция, аппроксимирующая стоимость элемента как функцию от параметра надёжности, подлежащего оптимизации [87,154]. Как правило, сеть состоит из большого числа подсистем, надёжность части из них повышается за счёт резервирования, надёжность остальных - за счёт оптимизации других параметров. При этом часть параметров надёжности системы изменяется непрерывно, часть принадлежит множеству целых чисел, часть некоторому дискретному множеству. Таким образом, получается, что для современных сетей задача оптимизации надёжности формулируется как нелинейная дискретно-непрерывно-целочисленная задача математического программирования [30,33].
В третей главе приводится несколько примеров задач в такой постанове и проводится их анализ на предмет наличия решения. Естественно, нахождение решения нелинейной задачи смешанного программирования для большого числа переменных классическими методами вызывает определённые трудности, связанные со сложностью вычисления частных производных и большими объемами производимых вычислений. Проводится сравнительный анализ различных методов оптимизации, из которых выбирается наилучший [68, 77, 78, 106, 140]. Наиболее эффективным для решения подобных классов задач является алгоритм дифференциальной эволюции [26, 34, 40, 103, 126]. В заключительных разделах главы приводится алгоритм дифференциальной эволюции, адаптированный для решения задачи смешанной оптимизации надёжности сложной системы, и описывается структура компьютерной программы, реализующей данный алгоритм [37].
В четвертой главе рассматривается общая методика оптимизации и её применение для расчёта и оптимизации надёжности примера сети [27]. Из расчётов видно, что предлагаемый подход полностью отвечает современным требованиям и особенностями развития территориально-распределённых сетей, позволяет максимально сократить время проектирования сети и уже на этапе проектирования повысить эффективность её использования. Разработано программное обеспечение оптимизации надёжности сложной системы, позволяющее автоматизировать все этапы разработанной методики оптимизации надёжности и сократить время расчётов [28, 38].
Приложение А содержит материалы по внедрению результатов диссертационной работы.
Приложение Б содержит материалы по анализу моделей с зависимыми отказами. Приложение В включает материалы по анализу моделей надёжности для частного случая - для простейших потоков восстановлений.
Приложение Г содержит формулы для расчётов надёжности параллельных систем.
Приложение Д содержит описание программы для расчёта надёжности сложных систем по точным и приближённым формулам.
Приложение Е включает краткий обзор и сравнение численных алгоритмов оптимизации.
Приложение Ж включает описание программы оптимизации параметров надёжности.
Реализация результатов работы. Результаты диссертационной работы используются в учебном процессе кафедры ИТЭУ факультета экономики и управления МТУСИ. Методика оптимизации надёжности территориально-распределенных сетей была использованы при проектировании сетей связи в проектах компаний ОАО «Центральный телеграф» и ЗАО «ТрансТеле-Ком», что подтверждается соответствующими актами.
Практическая ценность и реализация результатов работы:
1. Разработана эффективная методика расчётов и оптимизации показателей надёжности как проектируемых, так и действующих территориально-распределенных сетей, позволяющая найти такое число резервных элементов и такие характеристики надёжности нерезервируемых элементов сети, при которых доход, получаемый за счёт эксплуатации сети и предоставления услуг, будет максимальным, а надёжность заданной.
2. Программно реализованы процедуры расчётов характеристик моделей надёжности и сети в целом, позволяющие в 1.5 раза сократить время поиска оптимального решения по сравнению с существующими методами и программами.
3. Усовершенствован алгоритм дифференциальной эволюции, позволяющий находить сети оптимальной структуры с точки зрения надёжности в случае нелинейной целевой функции и целочисленных, непрерывных и дискретных значениях переменных.
4. Исследованы предложенные процедуры, алгоритмы и методика при различных распределениях потоков восстановления, схемах резервирования, структурах сети, что позволяет принимать обоснованные и экономически целесообразные решения по внедрению новой техники и технологии с целью повышения надёжности функционирования сетей, повысить качество предоставляемых услуг. ,
Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на следующих российских и международных конференциях:
1. Международный форум информатизации "Телекоммуникационные и вычислительные системы" (Москва, 2006г.).
2. Научно-техническая конференция профессорско-преподавательского, научного и инженерно-технического состава МТУСИ (Москва, 2006 г.). 3. 6-ая международная научно-практическая конференция "Исследование, разработка и применение высоких технологий в промышленности" (Санкт-Петербург, 2008).
4. 5-ая всероссийская школа-семинар молодых ученых «Управление большими системами» (Липецк, ЛГТУ, 2008).
5. Всероссийская научно-технической конференции "Новые материалы и технологии -НМТ-2008" (Москва, 2008).
6. 7-ая всероссийская научно-практическая конференция с международным участием "Информационные технологии и математическое моделирование" (Томск, 2008).
7. 9-ая международная конференция молодых учёных «Актуальные проблемы современной науки - 2008» (Самара, 2008).
8. Международная конференция "Перспективы развития телекоммуникационных систем и информационные технологии" (Санкт-Петербург, 2008).
Основные положения диссертационной работы докладывались и обсуждались на научном семинаре кафедры "Информационные технологии в экономике и управлении" МТУСИ (июнь, 2008г.).
Публикации. По теме диссертации опубликовано в периодических научных, научно-технических и производственно-технических изданиях 20 печатных работ, из них 5 статей опубликовано в ведущих рецензируемых научных журналах.
Достоверность научных результатов и выводов подтверждается использованием научных методов исследования, современного математического аппарата и практическим внедрением моделей расчёта и оптимизации надёжности сетей.
Основные положения, выносимые на защиту:
1. Логическая модель надёжности сети может быть представлена совокупностью резервируемых элементов (нагруженный и ненагруженный резерв) и нерезервируемых элементов (характеристики которых подлежат определению), что обеспечивает возможность оптимизации параметров надёжности с учётом стоимости подсистем и экономической эффективности функционирования сети для общего случая постановки задачи.
2. Математические модели надёжности (для восстанавливаемых параллельных систем для случая полумарковских моделей надёжности, подсистем с зависимой архитектурой: транспортная сеть — центрально-вычислительный комплекс — центр управления); аналитические выражения для расчёта показателей надёжности (коэффициентов готовности, вероятностей безотказной работы, среднего времени безотказной работы и интенсивности отказов систем с резервированием), модель надёжности сложной восстанавливаемой системы большой размерности и соответствующие выражения для расчёта показателей надёжности таких систем обеспечивают определение характеристик надёжности при произвольном распределении времени восстановления подсистем.
3. Модификация алгоритма оптимизации надёжности сети на базе метода дифференциальной эволюции позволяет найти решение задачи оптимизации для случая нелинейной целевой функции при целочисленных, непрерывных и дискретных значениях переменных и сокращает время решения задачи.
4. Методика оптимизации надёжности территориально-распределённых сетей (включая разработанное программное обеспечение) позволяет найти такое количество резервных элементов (нагруженный и ненагруженный резерв) и такие характеристики надёжности нерезервируе-мых элементов, которые обеспечивают максимальное значение дохода сети при заданной надёжности.
Постановка задачи оптимизации надежности и эффективности работы территориально-распределённои сети
Приведённые в разделе 1.2 постановки задач оптимизации надёжности требуют модификации и обобщения на случай применения к современным сетей по следующим причинам:
1) не рассмотрена задача повышения надёжности одной части подсистем за счет нена-груженного резервирования, другой - за счет нагруженного резервирования, третьей - за счёт улучшения характеристик надёжности элементов (установки более надёжного оборудования);
2) результаты решений применимы только для случая однородного резервирования (элементы с одинаковыми интенсивностями отказов и восстановлений);
3) рассмотренные задачи решены для невосстанавливаемых элементов;
4) капитальные затраты на резервирование рассматриваются в отрыве от прибыли, которую приносит действующая сеть, когда стоимость повышения надёжности сети (стоимость сети порядка нескольких миллионов долларов, элементы сети — дорогостоящие подсистемы), может превысить прирост доходов, получаемый за счет резервирования.
В диссертации решается общая задача оптимизации надёжности территориально-распределённых сетей. Работа посвящена исследованию и разработке математических моделей и методик оптимизации надёжности территориально-распределённых сетей. Рассматриваются восстанавливаемые неоднородные элементы, различные варианты повышения надёжности (нагруженное и ненагруженное резервирование, уменьшение среднего времени восстановления) и доход в качестве экономического критерия, учитывающий разность между денежными поступлениями от работы сети и затратами на повышение надёжности сети.
Рассмотрим численный пример, который показывает необходимость учёта различных сценариев резервирования, восстанавливаемости элементов, прибыли от работы сети для оптимизации надёжности системы [44]. Пусть укрупнённая модель надёжности сети имеет вид: оконечное оборудование - сеть доступа — транспортная сеть - сервис центр - центр ресурсов (рисунок 1.1). Решим для данной модели задачу оптимизации надёжности для частного случая. Рассмотрим модель надёжности из двух элементов: транспортная сеть - ЦВК (рисунок 1.6).
Найдём решение для случая с разными сценариями повышения надёжности. Для первого блока необходимо подобрать оптимальные параметры надёжности элементов, надёжность второго блока повышается за счёт применения нагруженного резервирования. Сделаем следующие предположения:
1) времена безотказной работы элементов независимы и распределены по экспоненциальному закону с параметрами: Х\ и Хг\
2) времена восстановлений являются независимыми (в совокупности) и распределёнными по экспоненциальному закону с параметрами: ц\ и цг\
3) каналы передачи данных восстанавливаются в процессе эксплуатации, в качестве показателя надёжности систем применяется нестационарный коэффициент готовности:
4) время работы / системы задано, для второй подсистемы заданы jU2 и Яг; для первой системы задано/г ь
5) стоимость первой системы как функция от надёжности задаётся формулой (1.13), где, в качестве показателя надёжности применяется нестационарный коэффициент готовности: I — R С,(g,) = а, 1п[ — ] и полагается, что Л,-т1п=0, т.е. система проектируется «с нуля».
6) стоимость второй системы ?2 известна;
7) блоки работают независимо.
Найти: для первой подсистемы интенсивность отказов Х\, для второй подсистемы - количество параллельных элементов в системе пг.
В качестве критерия оптимизации будем использовать чистый приведённый доход [32, 33, 47].
Формальная постановка задачи: найти число параллельных элементов для второй подсистемы «2 и интенсивность отказов первого элемента Х\, такие, чтобы чистый приведённый доход был максимальным:
Общая постановка задачи оптимизации надёжности. Эксплуатация системы с невысокими показателями надёжности может привести к значительным экономическим потерям и, как результат, снизить эффективность работы сети. Сеть имеет определённую структуру и состоит из конечного числа подсистем к (блоков, элементов). Цель настоящей работы заключается в определении значения надёжности для сети Р, которую в общем можно определить как функционал от функций надёжности каждой подсистемы: P=f[Pi, Ръ—, Рк), /=1,2,..., к. В общем случае Р, - показатель надёжности работы подсистемы, функция от некоторых параметров подсистемы, которые подлежат определению в процессе решения задачи оптимизации. Р, может быть вероятность безотказной работы /-ой подсистемы: Pt= P{T{ t}; нестационарный или стационарный коэффициент. Определение Pt уточняется при решении задачи. С каждой подсистемой можно связать функцию стоимости от надёжности C,(Pj):
Математическая модель оценки надёжности территориально-распределённои сети с резервированием ЦВК, ЦУ, и СПД
Повышение надёжности системы, представленной на рисунке 2.1, возможно путём резервирования. Для повышения надёжности системы может применяться резервирование одной или нескольких подсистем. Пример приведен на рисунке 2.8. С точки зрения математической модели каждый блок представляет собой не отдельную подсистему, а несколько подсистем, соединённых параллельно в смысле надёжности.
Для нахождения коэффициента готовности системы, представленной на рисунке 2.8, можно воспользоваться формулой (2.6) для Кг. Для применения формулы (2.6) надо заменить интенсивности отказов элементов Л А Я, на интенсивности.отказов блоков Л,,Л2,Л3 и най тиFe](t),Fe2(t),Fg3(t) - функции распределения времени восстановления блоков 1, 2 и 3, соответственно. Модель надёжности всех блоков показана на рисунке 2.9.
Также учтём, что за счёт резервирования может повышаться надёжность других подсистем, входящих в модель надёжности сети, но работающих независимо от ЦВК, СП, ЦУ. Например, за счёт резервирования (как нагруженного, так и ненагруженного) может повышаться надёжность сети доступа или среды передачи данных в ЦВК (рисунок 2.10). Поэтому также необходимо найти формулы для расчётов коэффициентов готовности систем с резервированием, работающих независимо.
Логические модели надёжности сети доступа и среды передачи ЛВС
В настоящее время широко известны аналитические формулы для расчета вероятности безотказной работы и средней наработки на отказ систем с однократным нагруженным резервом и однократным ненагруженным резервом. Данные формулы получены для случая невосстанав-ливаемых систем. В публикациях и монографиях [22, 57] приводятся формулы для расчётов надёжности и результаты исследования таких систем. Также известны формулы для коэффициента готовности систем, включающих (и-1) одинаковых резервных элементов, работающих в нагруженном режиме для случая простейших потоков отказов и восстановлений [110, 112].
В диссертации рассматривается задача оценки показателей надёжности систем с восстановлением (систем многократного использования), поскольку сеть представляет собой систему многократного использования, где все подсистемы восстанавливаются в процессе эксплуатации. Рассматриваются полумарковские модели надёжности, т.е. потоки восстановлений в подсистемах сети считаются ординарными с ограниченным последействием, для нагруженного и нсна груженного резерва и применение этих моделей для расчёта надёжности территориально-распределённой сети. Математические модели надёжности и вывод формул для частного случая - марковской модели надёжности — приведены в приложение Г. В данной диссертации рассматриваются модели надёжности систем из п параллельных элементов с разными характеристиками надёжности. Для каждой модели находятся математические выражения для расчёта коэффициента готовности и средней наработки на отказ.
Рассмотрим возможность повышения надежности сети путем введения избыточных элементов: в логической модели надежности к основному блоку добавляется п резервных блоков в Сначала решим задачу определения надежности системы с восстановлением, состоящей из двух параллельно соединённых восстанавливаемых элементов: основного и резервного (« 2). Модель надёжности системы, состоящей из двух параллельно соединенных элементов, находящихся в нагруженном режиме, представлена на рисунке.2.12.
Численные результаты сравнения алгоритмов решения нелинейных задач математического программирования
В настоящее время для решения задачи нелинейного программирования существует достаточно большое число алгоритмов [68, 81, 83, 115, 116, 129]. В диссертации исследуется их эффективность для решения задач большой размерности. В работе используется следующий подход: сначала выбирается наиболее эффективный метод для непрерывной оптимизации, затем разрабатывается его модификация для задачи оптимизации надёжности сети с учётом того, что часть переменных в модели являются дискретными. В данном разделе проводится сравнительный анализ нескольких алгоритмов непрерывной оптимизации.
В разделе 3.1 было показано, что функция NPV(X) имеет максимум во внутренней точке множества допустимых значений переменных. С ростом числа подсистем в сети (при увеличении числа переменных) и изменении структуры сети, возрастает сложность целевой функции за счёт увеличения размерности задачи. Поэтому из рассмотрения исключаются аналитические методы оптимизации, использующие дифференциальное и вариационное исчисление. Также исключаются численные методы, использующие производные, т.к. они могут привести к возникновению ошибок вблизи областей, где функция неограниченно убывает (например, в окрестности нуля, когда//— 0 (рисунки 3.12 и 3.15)) и требуют большого объёма времени на подготовку к решению задачи [83].
Будем использовать численные методы нелинейного программирования, не требующие регулярности и непрерывности целевой функции и существования производных. Большинство алгоритмов такого класса дают локальные оптимальные решения [83, 121]. Глобальность может быть доказана только анализом целевой функции или полным перебором. В общем случае, сходимость к глобальному оптимуму не может быть гарантирована. Задача проектирования сети накладывает ряд естественных ограничений на переменные. В общем случае целевая функция вида (1.14) с учётом ограничений вида (2.60) обладает единственным экстремумом. Поэтому достаточно использования алгоритмов, дающих локальное решение [83]. Эффективными в условиях, когда точный вид функции неизвестен и число переменных достаточно велико, могут оказаться методы случайного поиска [77, 78], -которые хорошо работают при оптимизации надёжности сети при поиске с разных начальных точек [40].
Эффективность работы локальных алгоритмов оптимизации зависит от выбора начальных значений [106]. Из рисунка.3.18 видно, что при значениях //І5 близких к 0, функция неограниченно возрастает. При задании начальных значений среднего времени восстановления, близ ких или при попадании на очередной итерации в данную область, алгоритм может не привести к решению.
Поэтому, наряду с локальными методами оптимизации, рассмотрим методы глобального поиска экстремума, которые обычно требуют больше времени, но обеспечивают более точное решение и гарантируют глобальность оптимума без введения дополнительных ограничений [120].
Таким образом, рассмотрим следующие алгоритмы оптимизации двух классов: прямого поиска и случайного поиска:
1) алгоритм М. Дж. Бокса,
2) алгоритм Розенброка.
3) метод Хука-Дживса,
4) алгоритм последовательного улучшения модели (Simulated annealing),
5) метод Нелдера-Мида,
6) метод случайного поиска,
7) алгоритм дифференциальной эволюции.
Результат обзора численных алгоритмов (1)-(7) поиска экстремума задачи нелинейного смешанного программирования приводится в приложении Е.
Критерии оценки алгоритмов. При теоретическом сравнении алгоритмов оптимизации большое внимание уделяется вопросам сходимости алгоритмов для некоторых классов задач [83]. Однако, математическое доказательство сходимости алгоритмов нелинейного программирования применимо к весьма узкому классу задач, и в ряде работ отмечается, что алгоритмы нелинейного программирования могут быть весьма эффективны в случаях, когда сходимость вообще не удаётся доказать [81, 83]. В большинстве работ оценивание алгоритмов осуществлялось на ограниченном множестве тестовых функций и для исследования брались наиболее известные задачи с небольшим числом переменных. Одной из главных особенностей задачи оптимизации надёжности является большая размерность задачи. Также к числу важных критериев при оценке качества алгоритма относят: число операций и время их выполнения, точность решения, затраты машинного времени, количество вычислений целевой функции, число итераций, максимальное число переменных и ограничений, время подготовки задачи к решению [83,106, 115, 121]. При оптимизации надёжности в качестве критериев оценки работы алгоритма в работе использовались [121]:
1) максимальное число переменных, для которых алгоритм находит решение;
2) машинное время; 3) количество вычислений целевой функции;
4) точность работы алгоритма.
Примеры функций для тестов. Для тестов использовались функции вида (1.14). Всего было взято 14 различных функций с различным числом блоков в модели надёжности п: 100, 200, 500, 700, 1000, далее с шагом 1000 до «=10000. При выводе функций было сделано предположение, что времена восстановления и отказов блоков имеют экспоненциальные распределения, при этом переменные модели выбирались случайно: с равной вероятностью для блока неизвестным параметром могло быть выбрано число элементов в резервной группе или среднее время восстановления подсистемы. Для автоматизации вывода целевой функции для тестовых задач была написана небольшая программа Tests.java, описание которой приведено в приложении Е. Входным параметром для программы являлось максимальное число переменных модели. На выходе программа генерировала текстовый файл в формате: число переменных: це-левая_функцня. На следующем шаге данные из файла tests.out считывались программами для каждого алгоритма оптимизации, результаты записывались в выходные файлы в формате: число переменных: число итераций: число подсчётовцелевойфунщии: время_решения_задачи. Для каждой функции каждый из алгоритмов запускался 100 раз для разных начальных точек, затем результат усреднялся для получения более устойчивых оценок. При тестировании программ учитывался тот факт, что программа может оказаться слишком неэффективной при решении задачи, поэтому вводился дополнительный показатель - максимально возможное время решения задачи, если в установленное время не удавалось получить решение, то происходил останов, и программа считалась неэффективной. Были заданы следующие значения: не более 10 минут для 1000 переменных, не более 100 - для 4000. Схема процедуры тестирования алгоритмов приведена на рисунке 3.19.
Разработка методики моделирования и оптимизации надёжности территориально-распределённых сетей
Для практического применения и проведения исследования предлагается следующая методика оптимизации. Методика решения задачи включает следующие этапы (рисунок 4.1):
Этап 1: проектирование структуры сети и построение логической модели надёжности сети; задание исходных данных для модели надёжности сети, т.е. фактическое определение того, какие параметры в модели сети являются известными, а для каких необходимо определить оптимальные значения.
Этап 2: аналитическое моделирование надёжности сети - вывод формулы для функции готовности или коэффициента готовности системы.
Этап 3: построение финансовой модели работы сети, определение чистого денежного потока, получаемого за счёт работы сети, и затрат на построение сети.
Этап 4: построение аналитической модели стоимости сети - оценка затрат на повышение надёжности сети - вывод формулы для функции затрат на повышение надёжности.
Этап 5: построение задачи оптимизации: вывод аналитических выражений для целевых функций с учётом исходных данных этапов 1-4; выбор критерия оптимизации и ограничений.
Этап 6: собственно процедуру оптимизации - нахождение оптимальных значений параметров модели.
Эгап 7: выработку рекомендаций по построение конкретной модели сети с учётом полученных результатов оптимизации.
Рассмотрим более подробно каждый из этапов. Построение целевой функции и ограничений и решение задачи оптимизации надёжности сети решается в несколько этапов.
I. На первом этапе строится финансовая модель системы. На основании модели рассчитывается чистый денежный поток CF, , получаемый за счёт работы сети. На данном этапе рас чётов предполагается, что сеть является абсолютно надёжной, т.е. кГ = 1 (g(t) = 1). Таким обра 118
1. Сначала определяется последовательная исходная модель надёжности. При этом учитывается, какие подсистемы работают независимо (могут быть представлены последовательной моделью надёжности из независимых подсистем), а для каких подсистем необходимо применять модель надёжности с зависимыми отказами.
2. Определяются подсистемы, надёжность которых может быть улучшена за счёт резервирования. Для таких подсистем в модели к основному блоку добавляются резервные в нагруженном и ненагруженном режиме. Количество резервных элементов есть подлежащие определению переменные в задаче оптимизации. Затем определяются подсистемы, надёжность которых не может быть улучшена за счёт резервирования. Значения интенсивностей отказов таких подсистем есть подлежащие определению переменные в задаче оптимизации.
3. На основе построенной модели надёжности выводиться формула для расчёта нестационарного коэффициента готовности #(/,//,,//2,...,//и,,..,«,,п2,...,пт) (стационарного коэффициента готовности для тех случаев, когда из-за сложности расчётов не получается вывести выражение для нестационарного коэффициента готовности в явном виде:
Investments в формуле NPV — CFt - Investments в зависимости от переменных оптимизации.
Инвестиции на повышение надёжности складываются из затрат на резервирование (для тех подсистем где применяется резервирование), и затрат на повышение надёжности за счёт установки более надёжного (и более дорогого оборудования). Величина Investments определяется как функция от переменных //,,//2,..., и,,я2,...: Investments = С!І(ЛІІЛ2,..., пх,п2,...).
CS(JUX,/J2,..., «j,«2,...), полученные соответственно на этапах I, II, III. Влияние надёжности на целевую функцию учитывается путём умножения потока наличных денежных средств на коэффициент готовности. Таким образом, первое слагаемое в формуле для расчёта NPV принимает надёжности сети вычитаются из чистого денежного потока и получается выражение для чистого приведённого дохода с учётом переменных надёжности и затрат на повышение надёжности:
