автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Обобщенные GERT-сети для моделирования протоколов, алгоритмов и программ телекоммуникационных систем

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

Шибанов Александр Петрович

ОБОБЩЕННЫЕ ОБЯТ-СЕТИ ДЛЯ МОДЕЛИРОВАНИЯ ПРОТОКОЛОВ, АЛГОРИТМОВ И ПРОГРАММ ТЕЛЕКОММУНИКАЦИОННЫХ СИСТЕМ

05.13.13 - Телекоммуникационные системы и компьютерные сети

АВТОРЕФЕРАТ

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

Рязань 2004

Работа выполнена на кафедре систем автоматизированного проектирования вычислительных средств ГОУВПО Рязанской государственной радиотехнической академии

Научный консультант: доктор технических наук, профессор

Корячко Вячеслав Петрович Официальные оппоненты: доктор технических наук, профессор

Брехов Олег Михайлович доктор технических наук Куракин Дмитрий Владимирович доктор технических наук, профессор Чураков Евгений Павлович Ведущая организация: Институт проблем передачи информации

Российской академии наук

Защита состоится " 2 " апреля 2004 г. в 11 часов на заседании диссертационного совета Д212.211.02 в ГОУВПО Рязанской государственной радиотехнической академии по адресу: 390005, г. Рязань, ул. Гагарина, 59/1.

С диссертацией можно ознакомиться в библиотеке ГОУВПО РГРТА.

Автореферат разослан "_"_2004 г.

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

2004-4 27412

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

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

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

1) задавать входные спецификации имитационной модели телекоммуникационной системы как случайные величины. Если орграф G является инструментом, "порождающим" некий закон распределения, характеризующий входную спецификацию, то, меняя параметры и структуру графа, мы можем обеспечить вероятностное управление ходом моделирования. Наиболее важными задачами такого рода являются: а) моделирование трафика сложной структуры, б) стохастическое управление изменением структуры модели, в) стохастическое задание спецификаций элементов модели.

РОС. НАЦИОНАЛЬНАЯ БИБЛИОТЕКА

осз

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

В настоящее время появилось большое число работ отечественных и зарубежных ученых (Бочарова П.П., Вишневского В.М., Альбореса Ф.Х., Ge-lenbe E., СЬао X., Pinedo M, Artalejo J. R. и многих других), в которых рассматриваются вопросы разработки принципиально новых моделей систем массового обслуживания с отрицательными заявками и триггерами (G-сстей). Они могут быть использованы для исследования новых телекоммуникационных сетей, в частности систем беспроводной связи (Бочаров П.П., Богуславский Л.Б., Брехов О.М., Вишневский В.М., Корячко B.II, Ляхов А., Баканов А.С., Шевчик КС). При имитации G-сетей необходимо иметь инструментальные средства, обеспечивающие задание большого числа дискретных и непрерывных случайных величин.

Известны методы получения случайных выборок распределений определенного типа, например, экспоненциального, Эрланга, Пуассона и т.д. Но распределение времени прохождения полумарковской модели от источника до стока при известных характеристиках случайных величин задержки в вершинах модели и вероятностях переходов для получения случайной выборки не используется, так как до настоящего времени не были найдены методы нахождения самого распределения;

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

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

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

5) использовать логические и функциональные операции над несколькими выходными случайными величинами графов. Например, находить закон распределения максимальной или минимальной из нескольких случайных величин. Задачи такого рода часто возникают при моделировании режима рассылки широковещательной информации группе пользователей телекоммуникационной сети или режима установления связи в системах с маршрутизацией от источника информации;

6) формулировать и решать задачи оптимизации технических характеристик телекоммуникационных систем. Спецификации (параметры) отдельных операций могут изменяться с целью получения лучшего проектного варианта. Часто встречаются задачи сведения многомодового распределения к одномодовому, решение которых необходимо при синтезе параллельно работающих телекоммуникационных систем. Улучшаемыми параметрами могут быть, например, показатели качества отдельных подканалов из множества 'параллел>Н9Г^а]бо^ающих Решение оптимизационных задач чаще всего

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

В настоящее время решение задач 1 - 5 не получено. Разработка методов решения этих задач позволяет найти более эффективные процедуры проектирования и исследования телекоммуникационных систем различного назначения. Знание распределений случайных величин при решении задачи 6 позволяет более эффективно решать задачи синтеза телекоммуникационных систем. Из вышесказанного можно сделать вывод об актуальности проводимых исследований.

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

Должно быть создано математическое и программное обеспечение для решения следующих проблем:

• оценки вероятностно-временных характеристик телекоммуникационных систем на основе графов алгоритмов большой сложности;

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

• комплексной оценки быстродействия и надежности технических и программных средств телекоммуникационных систем на основе их графов алгоритмов;

• комплексной оценки быстродействия телекоммуникационных систем с учетом старения информации на основе их графов алгоритмов;

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

Задачи исследований. Главными задачами диссертационной работы являются:

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

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

3. Нахождение распределений времени прохождения неоднородных GERT-сетей для решения задач анализа и синтеза компонент телекоммуникационных систем, отличающихся друг от друга методами исследования или разрабатываемых разными научными коллективами.

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

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

5. Разработка GERT-моделей со старением заявок для оценки вероятностно-временных характеристик телекоммуникационных систем, в которых поступившие во входные буфера коммуникационных устройств информационные пакеты с просроченными метками времени уничтожаются.

6. Разработка GERT-моделей с вероятностью отказов узлов (случайных GERT-сетей) для оценки вероятностно-временных характеристик телекоммуникационных систем с учетом надежности их элементов.

7. Разработка обобщенных сетевых моделей GERT с использованием логических связей и функциональных преобразований выходных величин сетей GERT нижнего уровня иерархии: логического пересечения "И", разъединительного "ИЛИ", вероятностного ветвления, преобразования законов распределения для анализа широковещательных режимов работы телекоммуникаций и режимов маршрутизации от источника информации.

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

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

Публикации. По теме диссертации опубликована 71 работа, в том числе 16 статей в ведущих научных журналах и изданиях, выпускаемых в Российской Федерации и утвержденных ВАК РФ для изложения основных научных результатов диссертаций на соискание ученой степени доктора наук. В Российском агентстве по патентам и товарным знакам зарегистрированы 4 программы для электронно-вычислительных машин.

Апробация работы. Результаты настоящей работы докладывались и обсуждались на 39 всероссийских, всесоюзных и международных конференциях и семинарах, в том числе на: конференции ученых социалистических стран "Локальные вычислительные сети", Рига, 1986; третьей всесоюзной конференции "Локальные вычислительные сети", Рига, 1988; второй международной конференции "Дистанционное образование в России", Москва, 1996; конференциях "Научная сессия МИФИ" 1999,2000,2001,2003; всероссийских научно-методических конференциях "Телематика", С-Петербург, 1995, 1997, 1998, 2003; международной научно-технической конференции "Гибридные системы. MODEL VISION STUDIUM", С-Петербург, 2001; международных научно-технических конференциях "Компьютерное моделирование", С-Петербург, 2002, 2003; международной школе-семинаре "БИКАМП", С-Петербург, 2001, 2003; VI международной школе-семинаре "Современные информационные технологии", Минск, 2003.

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

При решении задач, поставленных в диссертации, получены следующие новые научные результаты.

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

2. Разработаны метод и алгоритмы нахождения плотности распределения времени прохождения однородной GERT-сети большой размерности на основе эквивалентных упрощающих преобразований.

3. Разработаны метод и алгоритмы решения задачи нахождения плотности распределения времени прохождения неоднородной GERT-сети большой размерности путем выполнения упрощающих преобразований с выделением последовательности вложенных зон.

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

5. Создан новый класс сетевых стохастических моделей - GERT-сети со старением заявок и предложены методы нахождения их выходных характеристик.

6. Создан новый класс сетевых стохастических моделей - случайные GERT-сети и предложены методы нахождения их выходных характеристик.

7. На основе сетей GERT создан новый класс моделей - обобщенные стохастические графовые модели (ОСГМ).

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

9. Создана компьютерная программа моделирования обобщенных стохастических сетей GERT.

10. Создана система имитационного моделирования протоколов, алгоритмов и программ телекоммуникаций с использованием ОСГМ.

11. На основе обобщенных стохастических моделей GERT и компьютерной программы разработана не имеющая аналогов методика оценки вероятностно-временных характеристик протоколов связи и алгоритмов защиты информации сетей сбора, передачи и обработки траекторией информации.

12. На основе системы имитации с применением ОСГМ разработана не имеющая аналогов методика оценки вероятностно-временных характеристик автоматизированных комплексов обработки телеметрической информации.

Достоверность научных положений определяется: доказательством корректности полученных математических результатов; сравнением точности законов распределения, полученных разными методами, например численны-

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

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

• для анализа систем, описываемых стохастическими моделями с большим числом циклов и вероятностных ветвлений;

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

• при решении задач планирования проектов;

• при проектировании вычислительных комплексов и систем;

• для анализа криптографической стойкости алгоритмов защиты информации и т.д.

Реализация и внедрение результатов работы. Результаты исследований внедрены в Федеральном государственном унитарном предприятии ОКБ "Спектр", г. Рязань при разработке аппаратуры и систем сбора, передачи и обработки траекторной и телеметрической информации; в научно-производственном объединении ООО "Нейрон", г. Рязань при проектировании систем дистанционного управления лифтовым оборудованием; в рамках межвузовской научно-технической программы Минобразования РФ "Информационные технологии" в ГНИЙ ИТТ, г. Москва для повышения показателей качества Федеральной университетской компьютерной сети России RUNNet; при разработке программы развития единой информационной среды сферы образования Рязанской области на 2002 - 2003 г.г.; в учебный процесс Рязанской государственной радиотехнической академии.

Структура работы. Диссертация содержит 220 страниц основного текста и состоит из введения, шести глав, заключения, библиографического списка из 209 наименовании и пяти приложений на 42 страницах. В диссертацию включено 74 рисунка и 11 таблиц.

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

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

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

мины и определения, намечены направления исследований, сформулированы цели и задачи, решаемые в диссертационной работе.

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

При анализе технических систем нередко наиболее гибкими и полезными оказываются сетевые стохастические модели. Частным случаем стохастической модели является GERT-сеть (GERT: Graphical Evaluation and Review Technique - метод графического отображения). Разработка графоаналитических моделей GERT связана с именем американского математика Алана Прицкера. Ему же принадлежит и заслуга дальнейшего развития и обобщения этого метода, в результате чего появились широко известные системы имитационного моделирования Q-GERT и SLAM II. В последние годы опубликовано большое число работ отечественных ученых Воропаева В.И., Любкина СМ., Резера B.C., Ицковича Э.Л. и зарубежных - Голенко-Гинзбурга Д., Ласло 3., Ситняковского С, Каца В. и др. в которых освещаются проблемы создания новых альтернативно-сетевых стохастических моделей (SATM) на основе методов сетевого планирования. Сети GERT рассматриваются авторами как частный случай SATM. Однако потенциальные возможности математического аппарата сетей GERT в настоящее время не использованы в достаточной мере. Не разработаны методы нахождения закона распределения выходной величины GERT-сети и методы, обеспечивающие применение на практике моделей достаточно большой размерности.

Сети GERT могут быть использованы для моделирования системы, если она последовательно переходит из одного состояния в другое:

Каждому из них приписана вероятность вероятности последовательности

прохождения состояний определяются по правилу умножения:

ность Р1 ь ; если состояние Су достигнуто на некотором шаге, то вероятность перехода в состояние на следующем шаге равна В общем

вероятность попадания в состояние Cj^ в начальном испытании. Переход системы из состояния в состояние связывается с выполнением некоторой операции (чаще всего с временем выполнения), описываемой случайной величиной с известным законом распределения. В моделях GERT состояниям систе-

соответствует условная вероят-

случае

РИСУо.....Cj.fcaJiPjoJi-Pj^J^Pj^J..- Здесь

есть

мы соответствуют узлы (вершины) графа, а выполняемым в системе операциям - ветви (дуги) графа. Случайные величины, приписанные дугам GERT-сети, должны обладать аддитивностью по дугам любого пути. Используется преобразование GERT-сети в эквивалентную сеть, состоящую из одной ветви, с эквивалентной W-функцией W£(s) = p£Mg(s), где р£ - вероятность выполнения стока, Mß(s) - производящая функция моментов сети.

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

• операция логического пересечения "И" - событие свершится, если будут выполнены все операции, отображаемые входящими дугами. Функции или плотности распределения времени исполнения GERT-сетей используются для нахождения закона распределения: а) максимальной из нескольких случайных величин, б) минимальной из нескольких случайных величин;

• операция разъединительное "ИЛИ" - если выполнение одной из операций исключает выполнение всех остальных;

• операция ветвления выполняется над множеством выходящих из нее ветвей с заданными вероятностями их выбора. Выбранная ветвь может входить в узел (вершину) любого из выше определенных типов;

• операции преобразования законов распределения, выполняемые в узлах ОСГМ. По исходной функции или плотности распределения находятся: а) условные функции или плотности; б) законы распределения функций случайных величин;

• операции перенаправления заявок, получивших отказ в обслуживании в узле GERT-cem

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

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

петель г-го порядка (г = 1,л) возрастает по экспоненциальному закону, что делает невозможным решение задачи. Поэтому одним из наиболее важных направлений исследований является получение произвольного закона распределения выходной величины GERT-сети, содержащей большое число циклов. В работах Гадасина В.А., Гадасина Д.В., Голенко Д.И., Зоркальцева А.В., Кес-лера С.Ш., Колоскова В.А., Лившица СЕ. и др. рассматриваются задачи, описываемые решетчатыми многоразмерными стохастическими графами, содержащими экспоненциально большое число циклов. Возможны постановка и решение этих задач с использованием системы GERT при условии модернизации ее математического аппарата. При этом ценность полученных результатов во многих случаях возрастает.

При моделировании стохастического поведения программ наиболее часто используются марковские или полумарковские модели с любыми циклами и условными ветвлениями (Бейзер Б., Головкин Б.А., Довженок Т.С., Евстигнеев В.А., Касьянов В.П., Кемени Дж. Дж., Снелл Дж. Л., Феллер В. и др.). Алгоритмы или программы представляются в виде конечной поглощающей однородной цепи Маркова и характеризуются матрицей переходных вероятностей. При использовании методов линейной алгебры предполагается, что каждый оператор модели выполняется в течение одной условной единицы времени, а для нахождения закона распределения выходной величины используется итерационная рекурсивная процедура умножения матриц. В методе упрощающих преобразований графовой модели используются три базовые процедуры, в каждой из которых находится эквивалентная дуга: 1) для двух последовательно соединенных дуг, 2) для параллельно соединенных дуг, 3) для фрагмента программы, состоящего из дуги и петли. При использовании обоих методов число значений вероятностей и число циклов ограничиваются. Это принципиально приводит к потере точности за счет усечения распределений.

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

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

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

Рассматриваются используемые в настоящее время инструментальные средства моделирования телекоммуникаций. Системы COMNET III, BON De-

signer, OPNET Modeler, NS2 предназначены не для разработчиков новых сетевых технологий, а, главным образом, для администраторов и пользователей сети. Средства моделирования, как правило, жестко привязаны к конкретным сетевым схемам и технологиям. Библиотеки устройств часто приходится дописывать, используя язык (для COMNET III - SIMSCRIPT), что достаточно сложно для непрофессионального программиста. Определенный интерес представляет отечественная система СИДМ-2, разработанная Родионовым А.С. С помощью средств логического программирования и интерфейса с базами знаний реализована концепция интеллектуальных деятелей (объектов принятия решений), в которой поведение модели определяется заданными целями объектов.

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

В последние годы интенсивно развивается новое направление сетей массового обслуживания — G-сети, в которых помимо потоков обычных заявок рассматриваются также дополнительные пуассоновские потоки сигналов -отрицательных заявок или/и триггеров. При поступлении в узел сети отрицательная заявка уничтожает одну или несколько положительных заявок, если они имеются в данном узле. Триггер мгновенно перемещает положительную заявку или группу заявок с заданной вероятностью из данного узла в некоторый другой узел сети. Случайная величина, определяющая размер уничтожаемой или перемещаемой группы заявок, подчиняется произвольному дискретному закону распределения. Поступивший в узел сети сигнал может обслуживаться следующим образом: 1) активизироваться через случайное время; 2) максимальное время пребывания любого сигнала в узле ограничено величиной, имеющей случайное распределение. Сигнал, для которого это время закончилось, немедленно покидает узел.

В работах Бочарова П.П., Вишневского В.М., Atencia I., Aguillera G., Chao X., Gelenbe E., Manzo R., Pincdo M., Salerno S., Schassberger R. используются аналитические методы исследования G-сетей с характерными для них ограничениями: стационарности случайного процесса, пуассоновских входящих потоков, экспоненциального времени обслуживания прибора и т.п. Поэтому для расширения возможностей исследования новых сетей и систем массового обслуживания, в частности G-сетей, необходимо создать объектно-ориентированную систему имитации с возможностями стохастического управления процессом моделирования. Для реализации такой системы необходимо разработать: методы генерации заявок с произвольными интервалами следования и с внешним стохастическим управлением имитационными блоками-генераторами; методы динамического изменения структуры моделируемой системы на основе внешнего стохастического управления; методы и алгоритмы реализации значений случайных параметров (в частности, случайных задержек) в имитационных блоках-активностях; методы анализа состояния и управления потоками заявок в модели с применением условных функций распределения времени прохождения сетей GERT; алгоритмы реализации основ-

ных функций G-сетей. При этом в механизме стохастического управления должны использоваться ОСГМ.

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

Во второй главе рассматриваются численный метод нахождения непрерывной плотности распределения времени прохождения GERT-сети и обобщенные стохастические графовые модели.

Плотность распределения вероятностей времени прохождения GERT-сети находится из формулы обращения

¿ж

где

а характеристическая функция

определяется на основе топологического уравнения Мейсона заменой в эквивалентной производящей функции моментов переменной на С — действительная переменная. После нахождения плотности $>(х) должна быть найдена искомая плотность распределения £>(*). Это достигается использованием тривиального численного метода трансформации законов распределений на основе решения системы линейных уравнений.

При х = 0 получаем $>(о) = . Выполняется

2я

интерполяция

функции на отрезках [¿^—е, к = \,р, многочленом Ла-

гранжа второй степени с равноотстоящими узлами в пределах от

[—£,!,]. Если случайная величина имеет плотность то -►О

при ¿"->±оо. В целом же скорость стремления к нулю функции при тем выше, чем выше гладкость В результате интерполя-

ции и интегрирования имеем

■ £-1

и0к+ихк(]к+и2к

М1+62

где 17ок , и^ь, С/2* — значения действительных частей коэффициентов при степенях многочлена Лагранжа функции на отрезке

1У

Для последовательного вычисления значений функции 9>(хт) при различных значениях аргумента полагаем На каждом шаге

плотность смещается по оси X на некоторую заранее заданную величину. Наиболее трудоемкая часть вычислений, связанная с нахождением действительных и мнимых значений характеристических функций отдельных ветвей, проделывается однократно при нахождении плотности $>(*) в точке Х = 0. Все остальные значения плотности распределения находятся посредством рекуррентного умножения значений характеристической функции = вычисленных на предыдущем шаге, на величину

ехр (<<Т)= cos CT + isinCT ,где Т — шаг изменения X.

Вычислительные затраты нахождения плотности распределения вероятностей времени прохождения GERT-сети могут быть оценены как 0\р\П 2} +0(q)+0\n4}, где И| - число дуг GERT-сети, »2 " число узлов интерполяции, q - число определяемых значений плотности вероятности, - суммарное число петель порядков

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

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

многочленами нулевой степени с равноотстоящими узлами

Reх(С) 85 -^sin Ce^LojCos Cpj,]mx{C) ~ ^-sin Ce^Z-oysin QPj

Вычислительная трудоемкость задачи определения значений ;f(C) характеризуется как 0(<jN), где q- число определяемых значений 4".

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

1) последовательных ветвей с характеристическими функциями Х\> Х2-Эквивалентная дуга имеет характеристическую функцию

ХЕ12=*£Х г-Ъпх№Х2 + ' [КсдпЬп^г+ЬплКедгг ];

2) параллельных дуг с вероятностями выбора р\ и р 2:

3) дуги и петли первого порядка, соединяющей выход и вход узла (с вероятностями выбора Р2 И р 1 соответственно):

[1-Л Яедг,]2 + ^ 1)2

Структура ОБЯТ-сети G отображается в матрице весов Я(О) С п вершинами. Элемент матрицы Гу содержит: вероятность ру выбора дуги и значения действите Иед;у(С)и мнимых (¿") частей характеристической функции дуги (/,_/) в /узлах интерполяции. В произвольный узел ОЕКГ-сети Уд входят дуги из узлов У1,...,Уд_1 и выходят дуги в узлы ... ,\>/,, Кроме того, имеется дуга (уд > Уд ) • У ЗЛЫ У[,... ,Уд_1, Уд, и соединяющие их дуги составляют фрагмент G\. Выделим фрагмент, состоящий из узлов

Эквивалентные ^-функции ... , длядуг (уд,уд+1),

... ,(уьуа) равны: 1ГЕкА+\ =^1/(1 - . ^Ек.к ^.аД1"®*.*)-

Петля первого порядка (уд,Уд) исключается из сети, а \¥-функции дуг (уд,Уд+1), ... , заменяются эквивалентными функциями

Так как в ОБЯТ-сети выполняется условие аддитивности по дугам любого пути, то любой узел можно дублировать, порождая число его копий, равное числу дуг, входящих в узел. Каждая копия Уд ^...,Уд к | узла Уд имеет то же

множество выходных дуг (уд,Уд+1), ... »(уд.^) и соответствующих им вероятностей исполнения что и узел . В каждую копию узла Уд из множества У1,...,Уд_1 входит одна дуга. Назовем такое дублирование дублированием узла Уд с сохранением выходных дуг.

Полученный после дублирования фрагмент обозначим через С2 с матрицей смежности

П % -Ч

Столбцы у^.-.-.у^, матрицы смежности Аз^з) содержат по одной единице. Из фрагмента (?2 выделяются подграфы , состоящие из узлов: {у1,у*,,у*+ь ...,УА|, ... ,(у*_1,у*ы,у*+1.....УА}. Их структура одинакова, поэтому рассматриваются преобразования только подграфа Узел ^к копируется так, чтобы из каждой его копии У^ 1 1,...,Уд1 ^

в каждый из узлов Уа+1,"чуЛ входила бы одна дуга. Узел V! соединяется дугами с узлами У*и,...Л^, 4 • Назовем такое дублирование дублированием

узла V£ 1 с копированием входных дуг, после чего подграф преобразуется

в подграф с матрицей смежности

ч % % - % -

АкЛак

1 1

1 О О

0 0 . . 0 1 0 . . 0

0 0 . . 0 0 1 . . 0

0 0 . . 0 0 0 . . 1

0 0 . . 0 0 0 . . 0

0 0 . . 0 0 0 . . 0

0 0 . . 0 0 0 . . 0

у* •

4+2

Каждый из множества узлов vAu»"->vilt подграфа G^ имеет одну входящую и одну выходящую дуги. Аналогично каждый узел из множеств (%.!» — >%,*}' ... , (^.....v^ } подграфов Gki.....Gkh также имеет

одну входящую и одну выходящую дуги. Последовательные дуги заменяются эквивалентными, и узел Vj исключается из GERT-сети. При этом размерность матрицы A (G) уменьшается на единицу.

Любая GERT-модель приводится к единственной эквивалентной дуге по следующему алгоритму:

1) произвольно выбирается узел Vjj , отличный от источника и стока. Если имеется дуга (vi,vt)> то значения характеристических функций дуг (vjfc>v£+t)» *•• >(v*>va)» выходящих из узла vj, пересчитываются и дуга (V*»vi) исключается;

2) узел Vj дублируется с сохранением выходных дуг;

3) каждый продублированный в пункте 3 узел дублируется с копированием входных дуг;

4) последовательные дуги заменяются эквивалентными, и узел vk исключается из GERT-сети;

5) если в процессе преобразований в GERT-сети образуются последовательные или параллельные дуги, то они заменяются эквивалентными дугами;

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

Плотность вероятности находится по формуле обращения с ин-

терполяцией подынтегрального выражения многочленом Лагранжа. Временная сложность алгоритма О (п4) , где я - число узлов сети.

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

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

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

Теорема 2. Любая GERT-сеть может быть преобразована в ациклическую GERT-сеть и приведена к единственной эквивалентной дуге.

Выделение и преобразование зон выполняется следующим образом. Удаляем из замкнутого потокового графа ОЕКГ-сети дугу Если не рассматривать тривиальный случай ациклической ОЕКГ-сети, то мы получаем граф, содержащий хотя бы одну зону. Выделяем в графе ОЕКГ-сети множество зон, каждая из которых должна быть преобразована к ОЕКГ-сети, в которой множество источников 5 истоков Т соединены эквивалентными дугами.

Определение. Назовем зоной с базовой вершиной V j такую зону, которую образуют все простые контуры, состоящие из дуг (вместе с инцидентными им вершинами) и содержащие вершину Vу. Здесь ¡^ — предельно допустимое число дуг, входящих в простой контур.

Найдем последовательно все зоны с базовыми вершинами Vу, _/ = 1,<5,

в порядке их нумерации. Обозначим через I число ветвей, составляющих

*

петлю первого порядка, включающую в себя вершину V j . Алгоритм поиска

зоны состоит из следующих шагов:

1. Полагаем ] = \. Просматривая список вершин в порядке нумерации,

находим вершину входящую хотя бы в одну петлю первого порядка.

2. Зададим значение / = 1. Если через вершину Vj проходит петля первого порядка, то вершина порождает наименьшую из возможных вложенных зон Ы(1).

4. Если имеются петли первого порядка, содержащие вершину Vj и

состоящие из ветвей, то зона дополняется за счет включения в нее

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

5. Если 1 = 1доп> то зона с базовой вершиной Vj построена, иначе-пе-реход к шагу 3.

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

7. Если в GERT-сети еще имеются вершины V , ТО = ] + \ и выполняется переход на шаг 2, иначе - конец алгоритма.

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

означает, что данная вершина имеет петлю первого порядка, состоящую из одной ветви. Это наименьшая из возможных зон. По матрице смежности А формируется вспомогательная матрица П. Элементы матрицйимеют такую же структуру, что и элементы матрицы А. Для V/,./ <1 ¡у. = а ц.

Далее на шаге / преобразования выполняется возведение матрицы А в степень Для каждого шага преобразований составляется матрица

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

чисел , имеющих одинаковые индексы и . Элемент

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

Это означает что вершина впервые

достигается из вершины г за I шагов. Предельное число шагов преобразований I ¿ж задается пользователем и может быть различным для каждой зоны.

Оно ограничивается максимально допустимым числом петель первого порядка, не имеющих общих вершин. Проверка выполнения условия (в 1 + {1 = /1 позволяет обнаружить все петли первого порядка,

проходящие через вершину из вершины за шагов, Вер-

шины, входящие в эти петли, порождают искомую зону.

*

После определения зон с базовыми вершинами выполняются упрощающие преобразования сети. Каждая зона заменяется одной или несколькими эквивалентными дугами, соединяющими источники У со стоками (

Если в преобразованном графе GERT-сети число петель порядка Г является допустимым, то выполняется интерполяция эквивалентной характеристической функции GERT-сети многочленом Лагранжа и находится плотность распределения вероятностей выходной величины GERT-сети по

формуле обращения. Если число петель порядка г все еще неприемлемо велико, то упрощающие преобразования графа повторяются.

Рассматриваются ОЕКГ-сети со сложными распределениями. Пусть £ 1 > £2» ... — независимые случайные величины с одним и тем же распределением и характеристической функцией Если N - целочисленная случайная величина с производящей функцией Рк^ , не зависящая от всех , то случайная сумма £1+ ...+ ¿¡¡у имеет характеристическую функцию е?(С) = А (я (£"))• Функции Ксю(С) и 1т й>(С) используются как характеристики ветвей ОЕКГ-сети.

Предлагается новый класс стохастических моделей - GERT-cemu со старением заявок. Если определено время £ прохождения заявки из некоторого начального узла f в заданный конечный узел ] , то необходимо определить вероятность ,Р|£<а]| того, что оно не превысит з н ач е н . Условная

[ характеристическая функция случайной величин1$равна

/

рМ

-а, Л

(Ьс =

Я 1-е-" Л-/С 1-е-в'А

-и 1-е

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

Предлагается новый класс новый класс стохастических моделей - случайные ОЕКТ-модели. Определено три типа случайных GERT-сетей ё , различающихся между собой по выполняемым действиям в случае получения заявкой отказа в обслуживании из-за неготовности узла: 1) модель типа , в

которой заявка отправляется на выход сети t ; 2) модель типа ё3 , в которой

заявка с задержкой Т3 отправляется на вход сети 5 ; 3) модель типа ёи , в

которой заявка повторно с задержкой отправляется на вход узла и .

Коэффициент пропускания ветви (/,./) случайной ОЕКГ-сети типа С^ определяется как = ? где р,у - вероятность выбора ветви,

- вероятность потери заявки в узле /. Дуга (/,./) отражает элементарную случайную разомкнутую ОЕКТ-сеть, а соответствующая замкнутая случайная ОЕКГ-сеть будет выглядеть так, как это представлено на рис. 1. Вводится дополнительный фиктивный узел »', в котором для узла / проверяется условие "включен"-"выключен", а производящие функции моментов дуг (/',')

и (j'yj) взяты равными единице, что соответствует нулевому времени выполнения логических условий. Функция

W,E(s)='liPtjMtj(.:s)+l-'li> где

= (s) • Слагаемое (s) в неявном виде отражает потери потока заявок в узле í, когда тот находится в состоянии "выключен". Случайная GERT-сеть типа Gt определяется тремя базовыми эквивалентными характеристиками: вероятностью потери заявки 1—рщ, вероятностью достижения данного стока и найденной по производящей функции моментов для заданного стока Mg(s) функцией распределения F(x).

При использовании логической функции "И" в случайных ОСГМ/ необходимо учитывать, что возможны случайные события, состоящие в том, что на входы элементов "И" и "ИЛИ" заявки не проходят. Появление в модели таких состояний говорит о том, что отдельные части технической системы могут стать неработоспособными.

Случайные GERT-сети типа G¡ имеют множество петель 1-го порядка

, включающих в себя источник сети. В сочетании с петлями

первого порядка не включающими источник сети, они

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

В сети типа Gu для каждого узла дополнительно появляется фрагмент "дуга-петля". Если каждый из п узлов может попасть в состояние "выключен", то в сети обязательно есть петли всех порядков до 2" включительно. Распределение времени прохождения сети Gu находится методом эквивалентных упрощающих преобразований.

Использование GERT-сетей со старением заявок, а также случайных GERT-сетей и основанных на них ОСГМ открывает принципиально новые возможности для исследования ВВХ телекоммуникационных систем при изменении характеристик их надежности и потере определенной доли информационных пакетов.

! = {/,}, í = l,»

Дается определение модели ОСГМ. В ОСГМ используются логические связи и функциональные преобразования над выходными величинами двух или более ОЕКТ-сетей с циклами. Используются операции логического пересечения "И", разъединительного "ИЛИ" и вероятностного выбора одной из множества выходящих ветвей. В узлах ОСГМ могут выполняться операции преобразования законов распределения.

Моменты времени наступления событий определяются не на основе средних значений, а посредством нахождения закона распределения максимальной из нескольких случайных величин при известных законах распределения каждой из эквивалентных ветвей ОЕКТ-сети; резервы времени эквивалентных ветвей ОСГМ находятся с использованием распределений вероятностей. Использование ОСГМ позволяет получать более глубокие результаты при анализе режимов функционирования телекоммуникаций, по сравнению с известными аналогичными методами.

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

Выполняется переход от характеристической функции ОЕКГ-сети к функции Ф£(г) с заменой п е р е м е Жны'С. Искомая плотность

распределения

Ш *

при условии,

-1т 4=12=2*

что все особые точки функции ФЕ(г) лежат в левой части комплексной плоскости.

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

Рис.2

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

Ф£(г) = (мг3+уг2+И'г+А)/{(А1+г)(А4 + 7)|г3 + гг2 + 52 + г|}.

Когда функция Ф (г) имеет только простые полюсы

ХФ (г) =-

е (г u + z v+zw+h

fW - i

k'V

_m «rM

п(ч) _ V e*tX(zlu + z2kv + zkw + h)

Szk+4g4zik+3g3zi+2g2zk+gl

В приведенных выражениях коэффициенты при степенях z зависят от параметров ветвей модели.

Доказывается, что многочлен может иметь или три

разных отрицательных действительных нуля, или один отрицательный действительный нуль и пару комплексных сопряженных нулей. Когда функция ф(г) кроме простых полюсов имеет и полюсы второго или третьего порядка, плотность 0>(х) находится по формуле нахождения вычетов е-1 от полюсов

1

lim

.»-1

Zt порядка п : С_1 =

dz"

В четвертой главе рассматриваются не имеющая аналогов компьютерная программа и методика оценки вероятностно-временных характеристик (ВВХ) протоколов связи и алгоритмов защиты информации сетей сбора, передачи и обработки траекторной информации на основе обобщенных стохастических моделей GERT.

Рис.3

- Ититискм

Плотность ■ероятностм j Т"— ..—.-—... f \ ожидание

0.03 /

0,02 /\У

0,01 / Время

S0 10 20 SO 40 60 ео 70

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

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

Рис. 5, 6 иллюстрируют выявление некорректной работы протокола установления связи посредством применения программы на основе обобщенной модели GERT. Функция распределения на интервале времени от 27,5 до 34,5 возрастает от 0 до значения 0,9675. До момента времени 85,5 она не изменяется, но потом снова возрастает и в момент времени 90,3 достигает значения, близкого к 1. В интервале времени [85,5; 90,3] имеется второй пик плотности вероятности. Это говорит о том, что в 3,25 % случаев время установления начальной связи резко увеличивается. Ясно, что

Рис.4

1

0.75 0,5 0,25 О

Функция распределения

©

Время

20 30 40 50 60 70 80 90 100

Рис.5

0,4 0,3 0,2 0.1 0

Плотность распределения

Время CD

20

30 40 50 60 70 80 90 100

Рис. 6

модельные характеристики такого протокола установления начальной связи неудовлетворительны. Метод нахождения законов распределения времени прохождения GERT-сети и основанный на нем пакет прикладных программ использовались в ФГУП ОКБ "Спектр" и при выполнении работ по темам "Резеда" и "СБОР-Р".

Рассматривается применение ОСГМ для оценки ВВХ алгоритмов защиты траекторной информации в системах типа "Крона" при условии реализации вариантов кодирования, основанных на нелинейных теоретико-числовых методах: китайской теореме об остатках (система Д ¡) и возведении в степень в кольце целых чисел (система /?2 ).

При кодировании по модулям взаимно простых чисел т^, ... ,/Я^:

отображение осущест-

вляется на основе китайской теоремы об остатках. Если

то

/ е /о (тех! /И}... т д). Путем машинного эксперимента показано, что если решение сравнений первой степени выполняется по формуле Ад е (-^'"^^(тойт^), где Рч_1 - числитель предпоследней подходящей дроби -Р/б 17-1 в алгоритме Евклида; Г]- число неполных

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

При кодировании на основе степенных вычетов выполняются преобразования: Л2 = {/: Сш1 е(тоёА/); /Ысу(тоАМ)};у■ ев 1(тсх1 <р(м));

Здесь <р(м) - значение функции Эйлера от модуля М. Применяется предложенная Риселом процедура вычисления степенных вычетов. Полагается г^Ьп(р.оЛМ), л = <*02*+</+ ...+<}„, ¿у = 0; 1 (/2:1). Тогда, если 5о =с/0 =1 и 5у+1 =25у, то л = 5„. Если

Гу э65'(июс1Л/),то г0=Ь ; Гу+1 =(то<1Л/) и г гг„(тосШ). В дие-

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

Стохастические ОЕКГ-модели базовых преобразований и /?2 ис~ пользуются для построения модели более высокого уровня иерархии - алгоритма кодирования на основе сетей Файстеля. Найдено выражение для эквивалентной W-функции времени работы алгоритма расшифрования

постоянные коэффициенты определяются относительным временем выполнения основных машинных команд.

По этому выражению находятся среднее время и дисперсия времени расшифрования файла. Полученная машинным способом плотность распределения времени расшифрования при числе раундов J =12 приведена на рис. 7. Распределение времени выполнения расшифрования является многомодальным, и для целей имитационного моделирования приближенные распределения, полученные на основе исключи-

где

Рис.7

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

В пятой главе рассматривается применение обобщенной системы GERT для проектирования автоматизированных комплексов обработки телеметрической информации (АКОТ) типа "Лагуна". При определении максимальной производительности АКОТ целесообразно использовать графовые модели алгоритмов и программ для получения возможно более точных сведений о случайном времени выполнения сервером заданий клиентских программ. Полученные функции распределения используются в системе имитационного моделирования. Поток телеметрической информации от приемно-регистрирующей станции (ПРС) (рис. 8) поступает на адаптер, который преобразует аналоговую информацию в цифровой код и передает ее через ОЗУ на формирователь кадров. Формирователь потоков обрабатывает задания клиентов: кодовые значения отдельных параметров преобразуются в физические величины с помощью обработчиков параметров. Программный сервер по запросу программного клиента формирует ответ, содержащий набор требуемых параметров. Нагрузка на сервер заданий существенно зависит от числа и спецификаций параметров, запрашиваемых в одном наборе данных, числа наборов данных и интервалов следования между ними. Число наборов, число параметров в наборе и время обработки параметров являются случайными величинами. При увеличении числа клиентских программ увеличивается длина буфера в ОЗУ и возрастает время обработки кадра. Одной из наиболее важных задач проектирования данной системы является определение максимально возможной производительности АКОТ.

Пусть N - целочисленная случайная величина с производящей функцией и не зависящая от всех . Тогда случайная сумма независимых случайных величин имеет распределение, описываемое производящей функцией моментов ш($)=./4(м($)), где Л($) — производящая функция, описывающая случайное число запрашиваемых программой-клиентом параметров, а - производящая функция моментов времени

Рис.8

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

[Н^Г

Из этого выражения найдены среднее время выполнения задания и его дисперсия . Получены ана-

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

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

ден на рис. 9.

Число параметров в задании характеризуется равномерным распределением с целочисленными значениями от 9 до 14, а время обработки одного параметра - равномерным непрерывным распределением с параметрами а = 3, Ь=9.

Имитационная модель системы изображена на рис. 10.

Выполнение щаят Выполнен к« гадания

клиента! клиента г

ным сервером ю($)=р

(м Л*\Ь („аз

е —к е —е

[ («-*)' )

36 40 50 00 70 «0 М 100

Рис. 9

Рис.10

Здесь 01 - генератор заявок, <31 — -блоки-очереди, — Б4 -блоки-селекторы, выполняющие ветвления заявок по различным условиям, 811 - блок сбора статистики, Т - терминатор заявок, " - W6 — дуги, которые характеризуют случайную задержку в обслуживающих приборах.

При числе клиентских заданий г = 7 число кадров во входном буфере системы (очередь (}1) не превышало 4, и отсутствовала тенденция к росту очереди (рис. 11). При обслуживании сервером 8 клиентских программ наблюдается заметный рост входной очереди (}1 (рис. 12), что говорит о перегрузке системы.

Применение разработанных методов и моделей позволяет оценить производительность, выбрать наилучший вариант структуры системы обработки ТМИ и возможности ее масштабирования при увеличении объема и сложности решаемых задач. При этом сокращаются сроки проектирования на 10 -15 %.

Рассматриваются методы исследования и модели высокоскоростного агрегированного канала сети обработки телеметрической информации с использованием коммутаторов Ethernet Тракт передачи информации между сервером и компьютерами-клиентами с использованием агрегированного канала показан на рис. 13.

Рис. 13

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

кие, чем для каждого канала в отдельности. Невыполнение этих требований может отрицательно сказаться на качестве передачи речи, аудио- и видеоинформации в реальном времени. Алгоритмы управления сети должны гарантировать заданные показатели качества: среднюю скорость передачи CIR. (Committed Information Rate); объем пульсации Вс , соответствующий средней скорости CIR и периоду контроля Т: Д» = СЖ-Г ; допустимое превышение объема пульсации В.

Расчет ВВХ проводится для случая передачи файла достаточно большой длины I, причем 1>п, где п - размер окна. Передаваемый файл делится на некоторое целое число m кадров равной длины. Каждый из R каналов тран-ка передает множество кадров с суммарными объемами

. Кадры помещаются в выходных буферах передающего

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

Наиболее сложным является режим передачи в соответствии с алгоритмом GBN (с возвратом на N шагов назад). В начале каждого цикла передатчик канала а посылает п кадров, не дожидаясь квитанций от приемника. По окончании приема всех п кадров определяется номер первого искаженного кадра из числа переданных. Этот номер сообщается передатчику. Передатчик начинает новый цикл работы, направляя в канал все кадры, начиная с первого ошибочного.

С учетом независимости циклов друг от друга находится производящая функция моментов числа переданных за циклов кадров

Так как 1а>п, то начиная о ж н ы события, заключаю-

щиеся в том, что все кадры файла, следующие по данному каналу, будут пере-

даны успешно. При увеличении числа членов ряда Г/,, f"/,+i, ... ,Гу, '"ü увеличивается доля исходов, при которых файл передается полностью. Найдя сумму вероятностей таких исходов для всех Гу, получаем сумму вероятностей Рг, составляющих ряд: Pf,,Pf,+i, ••• ,Ру, ••• > Рк*1г Р/1 . Ограничиваем этот ряд таким значением к , при котором величина Р^ достаточно близка к единице. В результате нормировки получаем новый ряд

Pht^h* 1> -•• >Ру* ••■ > лС^У = ^ При экспоненциальном распре-

делении времени передачи файла с параметром производящая функция моментов равна

Правая часть вьдзажения определяет смесь распределений Эрланга порядков hn, (й + 1)л,... , кп , поэтому функция распределения вероятностей времени передачи файла

Функция распределения G(y) времени передачи файла по транку, состоящему из логических каналов, определяется как произведение функций

распределения отдельных каналов

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

Рассматривается типовая формулировка задачи оптимизации с использованием сетей GERT. Выражение для среднего времени передачи графовой модели вводится в целевую функцию, а варьируемыми параметрами являются параметры распределений, характеризующие отдельные операции процесса. Решена задача оптимизации процесса передачи зашифрованной информации по критерию минимума Ф(с) = ß\C + ß2 tcy где с - величина затрат, tc —

среднее время передачи файла при наличии ограничения с ä Ст . Здесь /?j и /?2 - коэффициенты, задаваемые разработчиком задачи. Считается известной зависимость между качеством канала и параметром стоимости

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

в файле случайное и задается дискретным распределением с вероятностями Я], а 2, ... ,а„. С использованием стохастической ОЕКГ-модели получены

плотность распределения времени передачи файла для стартстопного режима

и среднее время передачи

Хр . Задача оптимизации сводится к нахождению

Имеем экстремум в точке Ср = —

р0 =1-^(2^ + 1-^/4^+1 )/(2К),

с вероят-

ностью правильной передачи

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

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

1) в реализации стохастического управления работой имитационных блоков-генераторов основе использования ОСГМ, а именно: включения и выключения блока; задания случайного числа вырабатываемых транзактов; задания интервалов следования транзактов произвольными непрерывными и дискретными распределениями;

2) в реализации стохастического управления изменением структуры модели из внешней управляющей среды, построенной на использовании ОСГМ;

3) в возможности задания случайных величин в имитационных блоках через ОСГМ, например числа выбранных входов и выходов блока; распределения вероятностей при случайном выборе выхода, задании временных интервалов, используемых в алгоритме работы блока, и т.д.

При моделировании дисциплины работы очередей в соответствии с концепцией О-сетей задание случайных величин производится на основе ОСГМ.

Рис. 14

Укрупненная структура комплекса средств моделирования приведена на рис. 14. Сеть ОСГМ, выполняющая функции генератора произвольных распределений, создается с использованием компьютерной программы с современным графическим интерфейсом. Модель ОСГМ "порождает" неизвестное заранее распределение, сохраняемое в файле. Пользователю достаточно задать спецификации элементов (ветвей) сети ОСГМ: тип распределения и его параметры, а также последовательность прохождения ветвей с указанием вероятностей переходов. При этом сеть ОСГМ может иметь в своем составе ветви, характеризующиеся любыми непрерывными и дискретными распределениями, содержать любое число вероятностных ветвлений и циклов, учитывать старение заявок и вероятность отказа их обслуживания в узлах.

Объектно-ориентированная система моделирования реализует концепцию О-сетей. Размер группы уничтожаемых или перемещаемых заявок определяется дискретными распределениями на основе ОСГМ. Произвольное время ожидания "нетерпеливой" заявки в очереди может быть задано непрерывной или дискретной ОСГМ.

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

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

Создана система моделирования со стохастическим управлением процессом имитации на основе ОЕКГ-сетей. Она позволяет воссоздавать и исследовать экстремальные условия, которые могут возникнуть в процессе функционирования телекоммуникационной системы при изменении ее состава, структуры, способов управления и рабочей нагрузки.

В приложениях приводятся примеры практической реализации разработанных методов, алгоритмов и программ для проектирования телекоммуникаций: рассматриваются фрагменты моделей ОСГМ для генерации трафика произвольной структуры; моделирование процесса передачи полномочий в сетях с маркерным доступом; анализ дисциплин обслуживания трафика сложного профиля в очередях коммутаторов сети Ethernet; модель коммутатора телекоммуникационной системы управления лифтовым оборудованием, расчет сети Fast Ethernet Прилагаются акты о внедрении результатов работы.

ВАЖНЕЙШИЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Автоматизированный комплекс обработки телеметрической информации / В.А. Кузин, Н.В. Кравчук, А.П. Шибанов и др. // Вестник Самарского аэрокосмического университета. 2003. № 1. С. 146 - 153.

2. Корячко В.П., Шибанов А.П., Шибанов В.А. Численный метод нахождения закона распределения выходных величин GERT-сети // Информационные технологии. № 7.2001. С. 16 - 21.

3. Корячко В.П., Шибанов А.П. Шибанов ВА., Чернышев А.С. Имитационная система моделирования телекоммуникационных сетей // Телекоммуникации. № 10.2001. С. 28-32.

4. Корячко В.П., Курдюмов В.В., Морев СВ., Шибанов А.П., Шибанов ВА. Моделирование лифтовых телекоммуникаций // Известия Белорусской инженерной академии. № 1.2003. С. 274-280.

5. Малышга В.В., Шибанов А.П. Программная реализация расчета тепловых режимов электронно-вычислительной аппаратуры // Вестник Ряз. гос. радиотехн. акад. Вып. 2. 1997. С. 79 - 84.

6. Программное обеспечение моделирования работы группы лифтов / А.П. Шибанов, ВА. Шибанов, В.В. Курдюмов и др. // Промышленные АСУ и контроллеры. 2003. № 8. С. 42 - 44.

7. Шибанов А.П., Корячко В.П., Чернышев СВ., Кириллов С.Н., Корне-ев В.А. Развитие новых информационных технологий в образовании на основе расширения сети RUNNet // Вестник Ряз. госуд. радиотехн. акад. Вып. 1. 1996. С.10-15.

8. Шибанов А.П. Минимизация ресурсов в моделях стохастической структуры // Межвуз. сб. науч. трудов "Новые информационные технологии", Рязань. 2001. С. 121 - 126.

9. Шибанов А.П. Нахождение закона распределения выходной величины GERT-сети // Вестник Ряз. гос. радиотехн. акад. Вып. 8. 2001. С. 81 -85.

10. Шибанов А.П. Разработка программного обеспечения для моделирования локальных сетей Ethernet // Программирование. 2002. № 6. С. 62 - 71.

11. Шибанов А. П. Нахождение закона распределения выходной величины GERT-сети большой размерности // Информационные технологии. 2002. № 1.С. 42 -45.

12. Шибанов А.П. Применение моделей стохастической структуры для анализа вероятностно-временных характеристик алгоритмов преобразования информации в специализированных сетях // Телекоммуникации. № 3. 2002. С. 35-39.

13. Шибанов А.П. Моделирование работы коммутатора в полнодуплексном режиме // Вестник Самарского аэрокосмического университета. 2002. № 1. С. 143 -150.

14. Шибанов А.П. Нахождение дискретного закона распределения выходной величины GERT-сети // Вестник РГРТА. 2002. Вып. 9. С. 43 - 48.

15. Шибанов А.П. Нахождение плотности распределения времени исполнения GERT-сети на основе эквивалентных упрощающих преобразований // Автоматика и телемеханика. № 2.2003. С. 117 -126.

16. Шибанов А.П. Стохастическая модель канала связи // Вычислительные технологии. Т. 8.2003. № 1. С. 111 -116.

17. Шибанов А.П., Шибанов В.А., Курдюмов В.В., Морев СВ. Система моделирования лифтовых телекоммуникаций // Приборы и системы. Управление, контроль, диагностика. 2003. № 7. С. 11 - 16.

18. Шибанов А.П. Передача файлов по агрегированному каналу с гарантией качества обслуживания // Вестник РГРТА. 2003. Вып. 11. С. 67 — 70.

19. Шибанов А.П., Шибанов В.А. Система имитационного моделирования телекоммуникаций / Свидетельство об официальной регистрации программы для ЭВМ в РОСПАТЕНТ. № 2003611086 от 7.05.2003.

20. Шибанов А.П., Шибанов В.А. Система моделирования стохастического поведения алгоритмов и программ / Свидетельство об официальной регистрации программы для ЭВМ в РОСПАТЕНТ. № 2003611087 от 7.05.2003.

21. Шибанов А.П., Шибанов В А. Редактор графов / Свидетельство об официальной регистрации программы для ЭВМ в РОСПАТЕНТ. № 2003611088 от 7.05.2003.

22. Шибанов В.А., Шибанов А.П., Курдюмов В.В., Сусарин Н.И. Система имитационного моделирования работы группы лифтов / Свидетельство об официальной регистрации программы для ЭВМ в РОСПАТЕНТ. № 2003611250 от 27.05.2003.

ШИБАНОВ Александр Петрович

ОБОБЩЕННЫЕ GERT-СЕТИ ДЛЯ МОДЕЛИРОВАНИЯ ПРОТОКОЛОВ, АЛГОРИТМОВ И ПРОГРАММ ТЕЛЕКОММУНИКАЦИОННЫХ СИСТЕМ

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора технических наук

Подписано в печать 12.01.2004. Формат бумаги 60x84 1/16. Бумага офсетная. Печать трафаретная Усл. печ. л. 2,0 Уч.-изд. л. 2,0 Тираж 100 экз. Заказ iOfti. ГОУВПО Рязанская государственная радиотехническая академия. 390005, Рязань, ул. Гагарина, 59/1 Редакционно-издательский центр ГОУВПО РГРТА

2 061

РНБ Русский фонд

2004-4 27412

Введение.

Глава 1. Определение целей и задач исследований.

1.1. Сетевые стохастические модели и системы имитации.

1.1.1. Введение.

1.1.2. Стохастические GERT-модели.

1.2. Возможности расширения области использования системы GERT.

1.2.1. Применение моделей GERT для решения задач с использованием графов большой размерности.

1.2.2. Комбинированные системы, основанные на стохастических моделях и программах имитации очередей.

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

1.3.1. Марковские модели алгоритмов и программ с дискретным временем.

1.3.2. Марковские модели с непрерывным временем.

1.3.3. Статистическое моделирование алгоритмов и программ.

1.3.4. Аналитические методы расчета, используемые в сетевых проектах.

1.4. Инструментальные средства исследования протоколов, алгоритмов и программ.

1.5. Анализ возможностей применения стохастических моделей GERT в системах и сетях массового обслуживания.

1.5.1. Возможности использования моделей GERT в сетях массового обслуживания.

1.5.2. Сети массового обслуживания с отрицательными заявками и триггерами (G-сети).

1.6. Области применения моделей GERT и определение целей исследований.

1.6.1. Области применения системы GERT.

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

1.6.3. Структуризация модели телекоммуникационной системы.

1.6.4. Задачи исследований.

1.7. Выводы.

Глава 2. Численные методы исследования сетей GERT и обобщенных стохастических графовых моделей.

2.1. Численный метод нахождения распределения времени прохождения GERT-сети.

2.1.1. Введение.

2.1.2. Вычисление значения плотности распределения вероятностей <р{х) в точке л: = 0.

2.1.3. Интерполяция характеристической функции ХЕ(С)

GERT-сети.

2.1.4. Вычисление значений плотности распределения вероятностей ф(хт} в точках хт, г = \,q.

2.1.5. Табличное представление эквивалентных характеристических функций.

2.2. Эквивалентные преобразования однородной

GERT-сети.

2.2.1. Введение.

2.2.2. Эквивалентные характеристические функции, полущ чающиеся в результате типовых преобразований GERT-сети.

2.2.3. Преобразование GERT-сети к эквивалентной дуге.

2.2.4. Трудоемкость и емкостная сложность алгоритма.

2.2.5. Пример.

2.3.2. Приведение GERT-сети к эквивалентной дуге.93

2.3.3. Выделение и преобразование зон.96

2.3.4. Пример выполнения упрощающих преобразований.99

2.3.5. Заключение.101

2.4. GERT-сети со сложными распределениями и старением заявок.103

2.4.1. GERT-сети со сложными распределениями.103

2.4.2. Использование w-функций вида Wn(s).107

2.4.3. GERT-сети со старением заявок.108

2.5. Случайные стохастические GERT-модели.115

2.5.1. Введение.115

Ф 2.5.2. Случайные GERT-сети типа G,.117

2.5.3. Случайные GERT-сети типа Gs.121

2.5.4. Случайные GERT-сети типа Gu.121

2.5.5. Пример.122

2.5.6. Заключение.125

2.6. Обобщенные стохастические графовые модели.126

2.6.1. Введение.126

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

ОСГМ.130

2.7. Основные результаты. 133

Глава 3. Исследование сетей GERT и обобщенных стохастических графовых моделей на основе теории вычетов. 134

3.1. Общие положения. 134

3.2. Анализ телекоммуникационных каналов с использованием теории вычетов. 137

3.2.1. Введение. 137

3.2.2. Экспоненциальные GERT-модели

Ф телекоммуникационных каналов.138

3.2.4. Пример 1.142

3.2.5. Пример 2.145

3.2.9. Выводы.147

3.5. Основные результаты.148

Глава 4. Моделирование протоколов, алгоритмов и программ систем передачи траекторией информации.150

4.1. Анализ корректности протоколов сети передачи траекторией информации. 150

4.1.1. Компьютерная программа моделирования обобщенных сетей GERT. 150

4.1.2. Анализ корректности работы протоколов телекоммуникационной сети передачи траекторной информации. 152

4.2. Применение обобщенной системы GERT для оценки вероятностно-временных характеристик алгоритмов кодирования траекторной информации. 158

4.2.1. Введение. 158

4.2.2. Модели алгоритмов преобразования данных, основанных на китайской теореме об остатках. 159

4.2.3. Модели алгоритмов преобразования информации, основанные на степенных вычетах. 163

4.2.4. Анализ вероятностно-временных характеристик алгоритмов защиты информации, основанных на прямых алгебраических преобразованиях систем Rx и R2. 166

4.2.5. Модель прямого преобразования информации с использованием систем Rl и R2. 166

4.2.6. Вероятностно-временные характеристики систем шифрования, основанные на теоретико-числовых преобразованиях и стохастических моделях. 170

4.2.7. Вероятностно-временные характеристики алгоритмов защиты информации на основе сетей Файстеля. 174

4.2.8. Заключение. 180

4.3. Основные результаты. 181

Глава 5. Применение обобщенной системы GERT для проектирования автоматизированных комплексов обработки телеметрической информации. 183

5.1. Исследование вероятностно-временных характеристик алгоритмов и программ комплексов обработки телеметрической информации. 183

5.1.1. Введение. 183

5.1.2. Описание автоматизированного комплекса обработки

ТМИ.183

5.1.3. Аналитические методы оценки времени выполнения заданий программ-клиентов.187

5.1.4. Имитационное моделирование системы.190

5.2. Модели группового канала специализированной сети обработки телеметрической информации.195

5.2.1. Введение. 195

5.2.2. Модель передачи кадров по агрегированному каналу в соответствии с алгоритмом SAW.198

5.2.3. Модель передачи кадров по агрегированному каналу в соответствии с алгоритмом GBN.199

5.2.4. Модель передачи кадров по агрегированному каналу в соответствии с алгоритмом SR.201

5.2.5. Нахождение времени передачи файла по агрегированному каналу.201

5.2.6. Модели агрегированного соединения.202

5.2.7. Модель агрегированного соединения в режиме SAW. 203 # 5.2.8. Модель агрегированного соединения в режимах GBN и SW.206

5.3. Оптимизация процесса передачи зашифрованной информации.207

5.3.1. Введение.207

5.3.2. Постановка и решение задачи.209

5.4. Основные результаты.216

Глава 6. Система моделирования протоколов, алгоритмов и программ телекоммуникационных систем.218

6.1. Функциональные характеристики системы моделирова ния.218

6.2. Описание основных имитационных блоков.224

6.3. Моделирование G-сетей.229

6.3.1. Реализация G-сетей в объектно-ориентированной системе моделирования.229

6.3.2. Пример.232

6.4. Выводы.235

6.5. Основные результаты.236

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

Библиографический список.245

Приложение 1. Моделирование трафика пользователей и изменения состояния системы.266

П.1.1. Управление генерацией трафика.266

П. 1.2. Имитация передачи полномочий в сетях с маркерным доступом.272

Приложение 2. Анализ дисциплин обслуживания очередей коммутаторов в сети Ethernet.277

П.2.1. Введение.277

П.2.2. Реализация метода.278

Ф Приложение 3. Модель коммутатора телекоммуникационной системы управления лифтовым оборудованием.286

Приложение 4. Моделирование сети Fast Ethernet.290

Приложение 5.295

ВВЕДЕНИЕ

Актуальность темы. В настоящее время в связи с развитием микропроцессоров и микроконтроллеров телекоммуникационные системы постоянно усложняются. Отдельные части технических систем становятся все более интеллектуальными, число и сложность выполняемых функций постоянно увеличиваются. Разные части технической системы функционируют параллельно и в процессе решения задач постоянно обмениваются между собой информацией. Ведется обмен не только данными, но и во все большей мере звуковой и видеоинформацией, часто в реальном времени. Примерами таких систем являются технические комплексы, обеспечивающие взаимодействие групп самолетов-истребителей между собой и с наземными средствами управления, аппаратура для обеспечения согласованной работы нескольких систем обработки траекторной информации при испытаниях летательных аппаратов, телекоммуникационная аппаратура для обеспечения функций дистанционного контроля и управления промышленным оборудованием и т.д. Для обеспечения обмена информацией между удаленными объектами технической системы в условиях сильного воздействия отрицательных факторов, ухудшающих качество передачи информации, например, электромагнитных помех, а также возможного преднамеренного воздействия противника (злоумышленника) необходима разработка новых протоколов функций взаимодействия объектов. Для этой цели применяются более совершенные алгоритмы помехоустойчивого кодирования, криптографической защиты и сжатия информации. Разрабатываются повышенные требования по обеспечению параметров качества передачи данных, видео- и аудио- информации. Многие задачи, возникающие при оптимизации, тестировании, оценке вероятностно-временных характеристик, параметров надежности и отказоустойчивости телекоммуникаций значительно упрощаются, если их рассматривать на теоретико-графовых моделях. При выборе структуры телекоммуникационного комплекса важнейшую роль играют сведения о множестве задач, решаемых системой. Типичной формой задания такого множества является совокупность алгоритмов, увязанных в единое целое по перерабатываемой информации для решения главной задачи системы. Наиболее удобная, наглядная и многосторонняя форма описания телекоммуникационной системы — граф алгоритмов телекоммуникационной системы. Под этим понимается орграф G = (X,U) вершины х{ которого отображают частные реализации / -х алгоритмов системы. Вершинам графа приписывается вес в форме некоторых физических величин, связанных с реализацией алгоритмов, например, времени реализации алгоритма, требующейся для его выполнения памяти, вероятности попадания на тот или иной его выход, ошибок определения тех или иных величин, связанных с реализацией алгоритма и т.п. Соотношения следования между алгоритмами обычно соответствуют направлениям потоков информации. Граф алгоритмов телекоммуникационной системы может быть представлен и в такой форме, в которой частные реализации алгоритмов связываются с дугами графа.

Для получения характеристик графа алгоритмов телекоммуникационной системы часто используется метод статистических испытаний, основанный на использовании датчиков случайных чисел. Но время счета растет экспоненциально относительно числа ветвлений и циклов графа, и трудно добиться погрешности менее 1 %. Наибольшими возможностями обладают полумарковские модели, при использовании которых время исполнения операторов задается случайной величиной. Чаще всего время исполнения операторов характеризуется средним значением и дисперсией. Если дисперсия равна нулю, модель становится марковской. Для марковских и полумарковских моделей разработаны быстродействующие алгоритмы нахождения математического ожидания и дисперсии выходной случайной величины. Но задача нахождения закона распределения для марковских моделей большой размерности решается с погрешностью примерно в 10 - 15 %, а итоговое распределение является дискретным. Такая погрешность считается небольшой, например, для планирования работ на вычислительных центрах, но для решения задач, требующих точного знания функции или плотности распределения, нужны иные методы. Известны результаты, полученные на основе интегральных уравнений, связывающих условные вероятности достижения соседних вершин графа через распределения сверток случайных величин времени выполнения операций. Система решается с использованием преобразований Лапласа. Однако результаты в виде аналитических выражений получены только для простейших моделей.

Разработка графо-аналитических моделей GERT связана с именем американского математика Алана Прицкера. Ему же принадлежит и заслуга дальнейшего развития и обобщения этого метода, в результате чего появились широко известные системы имитационного моделирования Q-GERT и SLAM И. В последние годы опубликовано большое число работ отечественных ученых Воропаева В. И., Любкина С. М., Резера В. С., Ицковича Э. Л. и зарубежных - Голенко-Гинзбурга Д., Ласло 3., Ситняковского С., Каца В. и др. в которых освещаются проблемы создания новых альтернативно-сетевых стохастических моделей (SATM) на основе методов сетевого планирования. Сети GERT рассматриваются вышеуказанными авторами как ча стный случай SATM. Однако потенциальные возможности математического аппарата сетей GERT в настоящее время не использованы в достаточной мере. Не разработаны методы нахождения закона распределения выходной величины GERT-сети и методы, обеспечивающие применение на практике моделей достаточно большой размерности. Модели GERT, по сути, не отличаются от полумарковских, но их анализ выполняется на основе комплексных характеристик случайных величин, характеризующих операции — производящих функций моментов. На практике это позволяет получить несколько первых моментов распределения. Однако эффективных методов и алгоритмов нахождения закона распределения выходной величины до настоящего времени не было получено.

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

1) задавать входные спецификации имитационной модели телекоммуникационной системы как случайные величины. Если система только проектируется, то о ее свойствах можно судить по соответствующей модели. Чаще всего известна статистика на множество независимо выполняемых операций; но проблемой является нахождение закона распределения, характеризующего выход системы. Если орграф G является инструментом, "порождающим" некий закон распределения, характеризующий входную спецификацию, то, меняя параметры и структуру графа, мы можем обеспечить вероятностное управление ходом моделирования. Наиболее важными задачами такого рода являются: а) моделирование трафика сложной структуры в телекоммуникационной сети, б) стохастическое управление изменением структуры модели, в) стохастическое задание спецификаций элементов модели.

В настоящее время появилось большое число работ отечественных и зарубежных ученых (Бочарова П. П., Вишневского В. М., Альбореса Ф. X., Gelenbe Е., Chao X., Pinedo М, Artalejo J. R. и многих других), в которых рассматриваются вопросы разработки принципиально новых моделей систем массового обслуживания с отрицательными заявками и триггерами (G-сетей). Они могут быть использованы для исследования новых телекоммуникационных сетей, в частности систем беспроводной связи (Бочаров П. П., Богуславский Л. Б., Брехов О. М., Вишневский В. М., Ко-рячко В. П., Ляхов А., Баканов А. С., Шевчик К.С.). При реализации и использовании имитационных систем с использованием G-сетей необходимо иметь инструментальные средства, обеспечивающие задание множества дискретных и непрерывных случайных величин.

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

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

Задачи, связанные с использованием условных распределений, на основе известных методов статистических испытаний и марковских моделей не решаются в виду недостаточной точности этих методов. Решения подобных задач на основе полумарковских моделей не получены;

3) использовать сложные распределения, в частности распределение суммы случайного числа случайных слагаемых, которое характеризует элементарную логически неделимую операцию. Например известно, что число передаваемых кадров звуковой информации в режиме диалога относительно невелико. Оно может быть охарактеризовано целочисленной случайной величиной N, время передачи кадра также случайно и задается непрерывной величиной Тогда время передачи всего множества кадров а> имеет распределение суммы случайного числа случайных слагаемых. При обработке телеметрической информации компьютеры, на которых реализованы автоматизированные рабочие места испытателей, обращаются к компьютеру-серверу, обрабатывающему входной поток телеметрической информации, с запросом случайного числа параметров одного типа, причем время обработки одного параметра также случайное. При проектировании и исследовании работы телекоммуникационных систем встречается множество задач такого рода.

Метод статистических испытаний и полумарковские модели со сложными распределениями используются только в простейших случаях;

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

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

5) использовать логические и функциональные операции над несколькими выходными случайными величинами графов. Например, находить закон распределения максимальной или минимальной из нескольких случайных величин. Задачи такого рода часто возникают при моделировании режима рассылки широковещательной информации группе пользователей телекоммуникационной сети или режима установления связи в системах с маршрутизацией от источника информации.

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

6) формулировать и решать задачи оптимизации технических характеристик телекоммуникационных систем. Спецификации (параметры) отдельных операций могут изменяться с целью получения лучшего проектного варианта. Часто встречаются задачи сведения многомодового распределения к одномодовому, решение которых необходимо при синтезе параллельно работающих телекоммуникационных систем. Улучшаемыми параметрами могут быть, например, показатели качества отдельных подканалов из множества параллельно работающих. Решение оптимизационных задач чаще всего носит итерационный характер. Если есть возможность просмотра получающейся плотности распределения после каждой итерации, то выполнение оптимизационных процедур на следующем шаге может быть более эффективным.

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

Подводя итог, можно отметить, что в настоящее время решение задач 1 — 5 не получено. Решение этих задач позволяет найти более эффективные методы исследования и проектирования систем телекоммуникаций различного назначения. Знание распределений случайных величин при решении задачи 6 позволяет более эффективно решать задачи синтеза телекоммуникационных систем. Из вышесказанного можно сделать вывод об актуальности проводимых исследований.

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

Должно быть создано математическое и программное обеспечение дня решения следующих проблем:

• оценки вероятностно-временных характеристик телекоммуникационных систем на основе графов алгоритмов большой сложности;

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

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

• комплексной оценки быстродействия и надежности технических и программных средств телекоммуникационных систем на основе их графов алгоритмов;

• комплексной оценки быстродействия телекоммуникационных систем с учетом старения информации на основе их графов алгоритмов;

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

Задачи исследований. Главными задачами диссертационной работы являются:

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

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

3. Нахождение распределений времени прохождения неоднородных GERT-сетей для решения задач анализа и синтеза компонент телекоммуникационных систем, отличающихся друг от друга методами исследования или разрабатываемых разными научно-производственными коллективами.

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

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

5. Разработка GERT-моделей со старением заявок для оценки вероятностно-временных характеристик телекоммуникационных систем, в которых поступившие во входные буфера коммуникационных устройств информационные пакеты с просроченными метками времени уничтожаются.

6. Разработка GERT-моделей с вероятностью отказов узлов (случайных GERT-сетей) для комплексной оценки вероятностно-временных характеристик телекоммуникационных систем с учетом надежности их элементов.

7. Разработка обобщенных сетевых моделей GERT с использованием логических связей и функциональных преобразований выходных величин сетей GERT нижнего уровня иерархии: логического пересечения "И", разъединительного "ИЛИ", вероятностного ветвления, преобразования законов распределения для анализа широковещательных режимов работы телекоммуникаций и режимов маршрутизации от источника информации.

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

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

Публикации. По итогам исследований опубликована 71 работа, в том числе 16 статей в ведущих научных журналах и изданиях, выпускаемых в Российской Федерации и утвержденных ВАК РФ для изложения основных научных результатов диссертаций на соискание ученой степени доктора наук. Опубликованы статьи в журналах, входящих в Перечень ВАК: "Автоматика и телемеханика", "Вычислительные технологии", "Информационные технологии", "Программирование", "Приборы и системы. Управление, контроль, диагностика", "Промышленные АСУ и контроллеры", "Телекоммуникации", "Вестник Самарского аэрокосмического университета", "Вестник Рязанской государственной радиотехнической академии".

Кроме этого опубликованы 2 статьи во всероссийских журналах "Вопросы радиоэлектроники", 19 материалов докладов всесоюзных, всероссийских и международных конференций; опубликовано 12 статей в межвузовских сборниках Рязанской государственной радиотехнической академии, 1 статья депонирована в Информприборе.

В Российском агентстве по патентам и товарным знакам зарегистрированы 4 программы для электронно-вычислительных машин.

Личное участие автора в проведении исследований. В работах, выполненных по теме диссертации, автору полностью принадлежат постанов

• ка целей и задач, разработка основных теоретических положений, методов и алгоритмов исследований. Система моделирования телекоммуникаций выполнена в соавторстве с В. А. Шибановым. Автору принадлежит разработка принципов стохастического управления процессом моделирования на основе новых моделей GERT. Соавтору принадлежит разработка системы моделирования в комплексе.

Апробация работы. Результаты настоящей работы докладывались и обсуждались на 39 всероссийских, всесоюзных и международных конференциях и семинарах, в том числе на: II всесоюзном семинаре "Синтез ф управляющих устройств на основе микропроцессоров и однородных сред",

Рязань, 1980; всесоюзном научно-техническом семинаре "Интерактивные диалоговые системы в вычислительных комплексах и сетях ЭВМ", Москва, 1986; конференции ученых социалистических стран "Локальные вычислительные сети", Рига, 1986; третьей всесоюзной конференции "Локальные вычислительные сети", Рига, 1988; второй международной конференции "Дистанционное образование в России", Москва, 1996; конференциях "Научная сессия МИФИ" 1999, 2000, 2001, 2003; всероссийских научно-методических конференциях "Телематика", С-Петербург, 1995, 1997, 1998,

2003; международной научно-технической конференции "Гибридные сист темы. MODEL VISION STUDIUM", С-Петербург, 2001; международной научно-технической конференции "Проблемы передачи и обработки информации в сетях и системах телекоммуникаций", Рязань, 2001; международных научно-технических конференциях "Компьютерное моделирование", С-Петербург, 2002, 2003; международной школе-семинаре "БИКАМП", С-Петербург, 2001, 2003; всероссийских научно-технических конференциях "Новые информационные технологии", Москва, 1998, 2001, 2003; VI международной ппсоле-семинаре "Современные информационные технологии", Минск, 2003. w Научная новизна. В диссертации произведено теоретическое обобщение и представлено решение крупной научной проблемы сокращения сроков проектирования и улучшения качества функционирования телекоммуникационных систем посредством разработки обобщенных GERT-сетей для моделирования протоколов, алгоритмов и программ передачи информации.

При решении задач, поставленных в диссертации, получены следующие новые научные результаты.

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

2. Разработаны метод и алгоритмы нахождения плотности распределения времени прохождения однородной GERT-сети большой размерности на основе эквивалентных упрощающих преобразований.

3. Разработаны метод и алгоритмы решения задачи нахождения плотности распределения времени прохождения неоднородной GERT-сети большой размерности путем выполнения упрощающих преобразований с выделением последовательности вложенных зон.

4. Предложена экспоненциальная GERT-модель для оценки вероятно

• современны* характеристик хелекоммуншсационных каналов. Разработаны теоретические положения, обеспечивающие решение задачи нахождения распределения времени прохождения GERT-сети такого типа через вычеты.

5. Создан новый класс сетевых стохастических моделей — GERT-сети со старением заявок и предложены методы нахождения их выходных характеристик.

6. Создан новый класс сетевых стохастических моделей — случайные GERT-сети и предложены методы нахождения их выходных характеристик.

7. На основе сетей GERT создан новый класс моделей — обобщенные стохастические графовые модели (ОСГМ).

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

9. Создана компьютерная программа моделирования обобщенных стохастических сетей GERT.

10. Создана система имитационного моделирования протоколов, алгоритмов и программ телекоммуникаций с использованием ОСГМ.

11. На основе обобщенных стохастических моделей GERT и компьютерной программы разработана не имеющая аналогов методика оценки вероятностно-временных характеристик протоколов связи и алгоритмов защиты информации сетей сбора, передачи и обработки траекторной информации.

12. На основе системы имитации с применением ОСГМ разработана не имеющая аналогов методика оценки вероятностно-временных характеристик автоматизированных комплексов обработки телеметрической информации.

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

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

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

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

• для исследования систем, функционирование которых отражается графами с большим числом циклов и вероятностных ветвлений, например, решетчатыми графами;

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

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

• при решении задач планирования проектов;

• для решения задач анализа надежности, живучести и отказоустойчивости технических систем;

• при проектировании вычислительных комплексов и систем;

• для решения задач анализа характеристик параллельных алгоритмов и программ и их оптимизации;

• для анализа криптографической стойкости алгоритмов защиты информации.

Практическая значимость диссертационной работы подтверждается награждением дипломом П Московского международного салона инноваций и инвестиций, Москва, ВВЦ, 6 — 9 февраля 2002 г. разработки "Имитационная система моделирования корпоративных сетей для построения информационной образовательной среды Рязанской области", в основу которой легли полученные автором основные результаты диссертации. Копия диплома приведена в Приложении 5.

Реализация и внедрение результатов работы. Результаты исследований внедрены в Федеральном унитарном государственном предприятии ОКБ "Спектр", г. Рязань при создании систем сбора, передачи и обработки траекторной и телеметрической информации.

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

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

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

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

На основании результатов, полученных автором, созданы компьютерные программы и получены свидетельства об официальной регистрации программ для ЭВМ: "Система имитационного моделирования телекоммуникаций", № 2003611086, 7.05.2003 г.; "Система моделирования стохастического поведения алгоритмов и программ", № 2003611087, 7.05.2003 г.; "Редактор графов", № 2003611088, 7.05.2003 г.; "Система имитационного моделирования работы группы лифтов", № 2003611250, 27.05.2003 г., зарегистрированные в Российском агентстве по патентам и товарным знакам.

Копии актов о внедрении результатов диссертационной работы и свидетельств о регистрации программ приведены в Приложении 5.

Структура работы. Диссертация содержит 220 страниц основного текста и состоит из введения, шести глав, заключения, библиографического списка из 209 наименований и пяти приложений на 42 страницах. В диссертацию включено 74 рисунка и 11 таблиц

Основные результаты диссертации опубликованы в следующих работах: [2, 51, 52, 79,95, 128, 130 - 132, 134, 135, 137 - 140, 142, 143, 203 - 206].

ЗАКЛЮЧЕНИЕ

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

Создано математическое и программное обеспечение для решения следующих проблем:

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

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

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

• комплексной оценки быстродействия и надежности технических и программных средств проектируемых телекоммуникационных систем на основе их графов алгоритмов; Ф

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

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

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

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

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

• в системе GERT можно проследить зависимость между параметрами распределений, характеризующих отдельные ветви, и выходными характеристиками сети. Это, в принципе, дает возможность постановки и решения задач оптимизации. Параметры распределений ветвей (и соответствующих им операций) можно связать с показателями качества, стоимостью и т.д. Однако использование в процессе оптимизации только характеристик, полученных на основе первых моментов распределения т - и выходной величины в ряде случаев недостаточно. В частности, если время передачи информации по телекоммуникационному каналу описывается распределением с двумя или более модами, то технические характеристики такого канала могут быть расценены как неудовлетворительные из-за большого разброса значений времени передачи. Задача проведения оптимизации в таких случаях может состоять в уменьшении разброса случайного времени передачи и получении его распределения с одной модой. Процесс оптимизации носит, как правило, итерационный характер. На каждом шаге должна оцениваться степень приближения к поставленной цели. Если промежуточные распределения неизвестны, то решить такую задачу проблематично.

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

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

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

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

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

Еще одним направлением исследований является разработка типовой GERT-модели телекоммуникационного канала с получением распределений выходной величины сети в виде математических выражений. Это позволило сформулировать и решить задачу анализа вероятностно-временных характеристик группового канала сети передачи и обработки телеметрической информации и задачу параметрической оптимизации процесса передачи зашифрованной информации. Нахождение выходных распределений GERT-сети на основе теории вычетов создает благоприятные предпосылки для проведения дальнейших исследований, например для получения более глубоких результатов при исследовании телекоммуникационных систем со старением заявок. Некоторые новые результаты уже получены, в том числе и другими авторами [145,146].

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

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

Применение на практике полученных научных результатов выразилось в следующем:

• разработана не имеющая аналогов компьютерная программа моделирования обобщенных стохастических сетей GERT;

• создана система имитационного моделирования протоколов, алгоритмов и программ телекоммуникаций с использованием ОСГМ;

• на основе обобщенных стохастических моделей GERT и компьютерной программы разработана не имеющая аналогов методика оценки вероятностно-временных характеристик протоколов связи и алгоритмов защиты информации сетей сбора, передачи и обработки траекторной информации;

• на основе системы имитации с применением ОСГМ разработана не имеющая аналогов методика оценки вероятностно-временных характеристик автоматизированных комплексов обработки телеметрической информации.

Разработанные инструментальные средства многократно применялись при проектировании систем передачи траекторной и телеметрической информации; систем дистанционного управления лифтовым оборудованием; разработке телекоммуникаций для целей открытого образования в России; при разработке телекоммуникационных проектов по заказу администрации Рязанской области; при проведении учебного процесса на кафедре САПР ВС в РГРТА.

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

1. Абдуллаев Д. А., Амирсаидов У. Б. Моделирование локальных вычислительных сетей с учетом вероятностно-временных характеристик // Автоматика и телемеханика, 1994. № 3. С. 151 160.

2. Автоматизированный комплекс обработки телеметрической информации / Кузин В. А., Кравчук Н. В., Шибанов А. П. и др. // Вестник Самарского аэрокосмического университета, 2003. № 1. С. 146 — 153.

3. Айерленд К., Роузен М. Классическое введение в современную ф теорию чисел. М.: Мир, 1987.

4. Бабенко К. И. Основы численного анализа. М.: Наука, 1986.

5. Баканов А. С., Вишневский В. М., Ляхов А.И. Метод оценки показателей производительности беспроводных сетей с централизованнымуправлением // Автоматика и телемеханика, 2000. № 4. С. 97 — 105.

6. Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. Численные методы. М.: Наука, 1987.

7. Башарин Г. П., Бочаров П. П., Коган Я. А. Анализ очередей в вычислительных сетях. Теория и методы расчета. М.: Наука, 1989.

8. Башарин Г. П., Толмачев А. Л. Теория сетей массового обслуживания и ее приложения к анализу информационно-вычислительных систем / Итоги науки и техники. Теория вероятностей. Мат. статистика. Теорет. кибернетика. Т. 21. М.: ВИНИТИ, 1983. С. 3 119.

9. Бессонов JI. А. Основы теории графов / Всесоюзный заочный энергетический институт, М.: 1964.

10. Богуславский Л. Б., Ляхов А. И., Шевчик К. С. Моделирование стратегий доступа с обратной связью к общей памяти многопроцессорных систем // Автоматика и телемеханика, 1996. № 4. С. 172 -184.

11. Богуславский Л. Б., Ляхов А. И., Шевчик К. С. Сравнительный анализ стратегий доступа с обратной связью в многопроцессорных системах //Автоматика и телемеханика, 1996. № 5. С. 160— 177.

12. Богуславский Л. Б., Ляхов А. И. Методы оценки производительности многопроцессорных систем. М.: Наука, 1992.

13. Богуславский Л. Б., Ляхов А. И. Моделирование многосерверных локальных сетей // Автоматика и телемеханика, 1998. № 8. С. 109 — 123.

14. Богуславский Л. Б., Ляхов А. И. Оценка производительности распределенных информационно-вычислительных систем архитектуры "КЛИЕНТ-СЕРВЕР" // Автоматика и телемеханика, 1995. № 9. С. 160 175.

15. Боровков А. А. Теория вероятностей. М.: Наука, 1986.

16. Бочаров П. П., Вишневский В. М. G-сети: развитие теории мультипликативных сетей // Автоматика и телемеханика, 2003. № 5. С. 46 — 74.

17. Бочаров П. П. Сеть массового обслуживания с сигналами со случайной задержкой // Автоматика и телемеханика, 2002. № 9. С. 90 — 101.

18. Бусленко Н. П., Голенко Д. И. Метод статистических испытаний (Монте-Карло). М.: Физматтиз., 1962.

19. Везенов В. И., Светников О. Г., Таганов А. И. Основы процессно-ориентированного управления проектами информационных систем. Под ред. В. П. Корячко. М.: Энергоатомиздат, 2002.

20. Вентцель Е. С., Овчаров JI. А. Теория вероятностей и ее инженерные приложения. М.: Наука, 1988.

21. Вероятностные методы в вычислительной технике / А. В. Крайни-ков, Б. А. Курдиков, А. Н. Лебедев и др. М.: Высш. шк. 1986.

22. Виленкин С. Я. Определение закона распределения максимального времени. Автоматика и телемеханика, т. XXII. № 7. 1965.

23. Виноградов И. М. Основы теории чисел. М.: Наука, 1981.

24. Вишневский В. М., Ляхов А. И., Терещенко Б. Н. Моделирование беспроводных сетей с децентрализованным управлением // Автоматика и телемеханика, 1999. № 6. С. 88 99.

25. Вишневский В. М. Состояние и перспективы развития информационно-вычислительных сетей в России // Электросвязь, 1988. № 7. С. 20 — 23.

26. Вишневский В. М., Ляхов А. И. Беспроводные сети передачи данных: состояние, проблемы, моделирование // Межд. конф. по проблемам управления. М.: Фонд "Проблемы управления 1999. С. 154 171.

27. Вишневский В. М., Ляхов А. И. Оценка производительности беспроводной сети в условиях помех // Автоматика и телемеханика, 2000. № 12. С. 87-103.

28. Вишневский В. М., Ляхов А. И. Оценка пропускной способности локальной беспроводной сети при высокой нагрузке и помехах // Автоматика и телемеханика, 2001. № 8.

29. Волгина М. А. Моделирование производственных систем средствами математических пакетов // Компьютерное моделирование 2003: Труды межд. науч.-техн. конф. СПб.: "Нестор", 2003.

30. Воропаев В. И., Любкин С. М., Голенко-Гинзбург Д. Модели принятия решений для обобщенных альтернативных стохастических сетей // Автоматика и телемеханика, 1999. № 10. С. 144 — 152.

31. Воропаев В. И., Любкин С. М., Резер В. С., Голенко-Гинзбург Д. И. Построение оптимальной организационной структуры проекта // Автоматика и телемеханика, 2000. № 6. С. 133 —142.

32. Гадасин В. А., Гадасин Д. В. Надежность двухполюсных сетей с аддитивной структурой II. Финальная вероятность связи // Автоматика и телемеханика, 1999. № 10. С. 164 179.

33. Гадасин В. А., Гадасин Д. В. Надежность крупномасштабных сетей связи с аддитивной структурой // Автоматика и телемеханика, 1997. № 1.С. 160-173.

34. Гадасин В. А., Гадасин Д. В. Надежность двухполюсных сетей с аддитивной структурой. I // Автоматика и телемеханика, 1997. № 10 С. 78 — 90.

35. Голенко Д. И., Лившиц С. Е., Кеслер С. Ш. Статистическое моделирование в технико-экономических системах. Л.: Изд-во Ленингр. ун-та, 1977.

36. Голенко Д. И. Статистические методы планирования и управления. Наука, М.: 1968.

37. Голенко-Гинзбург Д. И, Кац В., Ситняковский С., Ицкович Э. JI. Управление трехуровневой производственной системой типа "человек-машина" // Автоматика и телемеханика, 2000. № 5. С. 166 184.

38. Голенко-Гинзбург Д. И., Любкин С. М., Резер В. С. Анализ устойчивы законов распределения продолжительности операций в стохастических сетевых проектах. // Автоматика и телемеханика, 2000. № 12. С. 147 -161.

39. Голенко-Гинзбург Д. И, Любкин С. М., Резер В. С., Ситняковский С. Л. Алгоритмы оптимальной поставки ресурсов для группы проектов (стохастические сети) // Автоматика и телемеханика, 2001. № 8. С. 157 — 167.

40. Голенко-Гинзбург Д. И, Любкин С. М., Резер В. С., Ситняковский С. Л. Использование метрических пространств в оптимальном календарном планировании // Автоматика и телемеханика, 2002. № 9. С. 164 173.

41. Голенко-Гинзбург Д. И., Ласло 3., Любкин С. М., Резер В. С. Вероятностная модель многомаршрутной задачи календарного планирования со стоимостными параметрами // Автоматика и телемеханика, 2002. № 10. С. 177-186.

42. Головкин Б. А. Построение вероятностной модели и анализ параллельных вычислительных процессов // Изв. АН СССР. Техническая кибернетика, 1973. № 3. С. 86 96.

43. Головкин Б. А. Расчет распределения вероятностей времени выполнения машинных программ // Управляющие системы и машины, 1974. №3. С. 23-28.

44. Головкин Б. А. Расчет характеристик и планирование параллельных вычислительных процессов. М.: Радио и связь, 1983.

45. Довженок Т. С. Инвариантность стационарного распределения сетей с обходами и "отрицательными" заявками // Автоматика и телемеханика, 2002. № 9. С. 97-111.

46. Евстигнеев В. А. Применение теории графов в программировании / Под ред. А.П. Ершова. М: Наука, 1985.

47. Егорова Ю. В. Родионов А. С., Чемисова Н. С. Средства интеллектуального моделирования в пакете СИДМ-2 // Тр. ИВМиМГ СО РАН. Новосибирск. 1997. С. 3-11.

48. Ермолаев Б. И., Корячко В. П., Григоренко В. Ф., Шибанов А. П. Минимизация ресурсов локальной сети САПР // Вопросы радиоэлектроники, серия ЭВМ. Вып. 3. 1988. С. 164-169.

49. Ермолаев Б. И., Корячко В. П., Григоренко В. Ф., Шибанов А. П. Определение ресурсов локальной сети интегрированной САПР // Вопросы радиоэлектроники. Серия ЭВМ. Вып. 5, 1988. С. 19-28.

50. Жожикашвили В. А., Вишневский В. М. Сети массового обслуживания. Теория и применение к сетям ЭВМ. М.: Радио и связь, 1988.

51. Захаров Г. П. Методы исследования сетей передачи данных. М.: Радио и связь, 1982.

52. Зоркальцев А. В. Назаров А. А. Об адаптивном распределении буферной памяти узла коммутации пакетов // Автоматика и телемеханика, 1997. №9. С. 176-184.

53. Иванов А. П. Оценка времени выполнения структурированных программ // Механизация и автоматизация производства, 1981. № 3. С. 29 — 31.

54. Игнатущенко В. В., Подшивалова И. Ю. Динамическое управление вычислительными процессами на основе статического прогнозирования // Автоматика и телемеханика, 1997. № 5. С. 160-173.

55. Игнатущенко В. В., Клушин Ю. С. Прогнозирование выполнения сложных программных комплексов на параллельных компьютерах: прямое стохастическое моделирование // Автоматика и телемеханика, 1994. №11. С. 142-157.

56. Игнатущенко В. В. Тепляков А. В. Об эффективности временного резервирования параллельных вычислительных процессов // Автоматика и телемеханика, 1994. № 6. С. 154 169.

57. Игнатущенко В. В. Организация структур управляющих многопроцессорных вычислительных систем. М.: Энергоатомиздат, 1984.

58. Интернет // http://wail.tms.ru/nets/optimise/locnop 09.html

59. Интернет // http ://wwwns2. chat.ru/whatis-w.html

60. Интернет // http://www.caciasl.com

61. Интернет // http ://wwwmakesvstems. com

62. Интернет // http ://www.mi!3. com

63. Интернет // http://www.ses.com

64. Интернет // http://www.iosotech.com

65. Карибский В. В. Лубков Н. В. Построение модели и анализ надежности многопроцессорной вычислительной системы // Автоматика и телемеханика, 1990. № 10. С. 171 182.

66. Касьянов В. П. Оптимизирующие преобразования программ. М.: Наука. Гл. ред. физ.-мат. лит., 1988.

67. Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. СПб.: БХВ-Петербург, 2003.

68. Кемени Дж. Дж., Снелл Дж. Л. Конечные цепи Маркова. М.: Наука, 1970.

69. Колесов Ю. Б. Сениченков Ю. Б. Визуальное моделирование сложных динамических систем. СПб.: Мир и семья и Интерлайн. 2000.

70. Колосков В. А., Титов В. С. Метод самоорганизации отказоустойчивой мультимикроконтроллерной сети // Автоматика и телемеханика, 1998. № 3. С. 173-183.

71. Колосков В. А., Медведева М. В., Медведев А. В. Клеточная самоорганизация отказоустойчивого мультимикроконтроллера // Автоматика и вычислительная техника, 2000. № 2. С. 64 — 73.

72. Корячко В. П., Шибанов А. П. Анализ и оптимизация временныххарактеристик ЛВС сложной технической системы // Локальные вычислительные сети / Тез. докл. третьей всесоюзной конференции. Рига: ИЭВТ, 1988. С. 165 -168.

73. Корячко В. П., Скворцов С. В., Телков И. А. Архитектура многопроцессорных систем и параллельные вычисления. М.: Высшая школа, 1999.

74. Корячко В. П., Шибанов А. П., Шибанов В. А. Численный метод нахождения закона распределения выходных величин GERT-сети // Информационные технологии, № 7. 2001. С. 16-21.ф

75. Корячко В. П., Шибанов А. П. Шибанов В. А., Чернышев А. С. Имитационная система моделирования телекоммуникационных сетей // Телекоммуникации, № 10. 2001. С. 28 32.

76. Корячко В. П., Курдюмов В. В., Морев С. В., Шибанов А. П., Шибанов В. А. Моделирование лифтовых телекоммуникаций // Известия Белорусской инженерной академии, № 1. 2003. С. 274 — 280.

77. Кукушкин С.С. Теория конечных полей и информатика, том 1 // Методы и алгоритмы, классические и нетрадиционные, основанные на использовании конструктивной теоремы об остатках — М.: МО РФ, 2000.

78. Кукушкин С.С. Повышение эффективности передачи телеметрической информации на основе представления результатов телеизмерений в системе остаточных классов // Измерительная техника. М.: "Стандарты", №7. 1995.

79. Лаврентьев М. А., Шабат Б. В. Методы теории функций комплексного переменного. М.: Наука, 1987.

80. Лазарев И. А. Композиционное проектирование сложных агрегативных систем. -М.: Радио и связь, 1986.• 92. Левин Б. Р. Теоретические основы статистической радиотехники.1. М.: Радио и связь, 1989.

81. Ляхов А. И. Асимптотический анализ моделей иерархических локальных сетей с многопроцессорными серверами // Автоматика и телемеханика, 1998. № 12. С. 82-93.

82. Максимов Н. А., Осипчук О. К. GERT-сети и моделирование систем обработки изображений // Компьютерное моделирование 2003: Труды Междунар. науч.-техн. конф. СПб.: "Нестор", 2003. С. 168-169.

83. Малинковский Ю. В. Сети массового обслуживания с обходами узлов заявками // Автоматика и телемеханика, 1991. № 2. С. 102 — 110.

84. Малыпин В. В., Шибанов А. П. Программная реализация расчета тепловых режимов электронно-вычислительной аппаратуры // Вестник Ряз. госуд. радиотехн. акад. вып. 2, 1997. С. 79 84.

85. Маркова В. П., Пискунов С. В., Погудин Ю. М. Формальные методы, языковые и инструментальные средства синтеза клеточных алгоритмов и архитектур // Программирование, 1996. № 3. С. 24 — 36.

86. Михотин В. Д. Синергические свойства пакета Simulink // Exponenta Pro. Математика в приложениях. М.: Softlane, 2003. № 1. С. 38 — 42.

87. Мэзон С., Циммерман Г. Электронные цепи, сигналы и системы. М.: Изд-во иностр. лит., 1969.

88. Олифер В. Г., Олифер Н. А. Компьютерные сети. Принципы, технологии, протоколы. СПб.: "Питер", 2000.

89. Олифер В. Г., Олифер Н. А. Новые технологии и оборудование IP-сетей. СПб.: БХВ-Петербург, 2001.

90. Полляк Ю. Г. Вероятностное моделирование на электронных вычислительных машинах. М.: Советское радио, 1971.ф 106. Привалов И. И. Введение в теорию функций комплексного переменного. М.: Наука, 1984.

91. Прицкер А. Введение в имитационное моделирование и язык С ЛАМ II: Пер. с англ. М: Мир, 1987.

92. Программные системы: Пер. с нем. / Под ред. Бахманна П. М.: Мир, 1988.

93. Пчелин Б. К. Специальные разделы высшей математики. М.: Высшая школа, 1973.

94. Родионов А. С. Разработка систем дискретного имитационного моделирования информационных сетей: Докт. диссертация. Новосибирск:1. Л ИВМиМГ СО РАН, 2002.

95. Родионов А. С. Имитационное моделирование СПД ВККП СО АН СССР средствами языка СИМУЛА // Эффективность и структурная надежность информационных систем (СМ-7). Новосибирск. 1982. С. 73 — 89.

96. Родионов А. С. Интеллектуальное моделирование новое направление в системах имитации // Экспертные системы и базы данных: Новосибирск. 1988. С. 75 - 82.

97. ИЗ. Родионов А. С., Чемисова Н. С. Пакет моделирования распределенных дискретных систем на Модула-2. Новосибирск. 1991.

98. Родионов А. С. Объектная ориентация в интеллектуальных системах моделирования // Тр. ВЦ СО РАН. Сер. Системное моделирование. Новосибирск. 1994.

99. Родионов А. С. Распределенное моделирование цифровых систем связи // Матер, межд. семинара "Перспективы развития современных средств и систем телекоммуникаций-99". Хабаровск-Новосибирск. 1999. С. 105-109.

100. Родионов А. С., Меленцова Н. А. Использование пакета СИДМ-2 для моделирования цифровых сетей с коммутацией каналов // Матер. IV Межд. конф. "Современные информационные технологии". Новосибирск. 2000. С. 41-45.

101. Сетевое планирование и управление / Под ред. Голенко Д. И. и Кириллова В. В. М.: Экономика, 1967.

102. Суэтин П. К. Классические ортогональные многочлены. М.: Наука, 1979.

103. Томашевский В. Н., Жданова Е. Г. Имитационное моделирование в среде GPSS. М.: Бестселлер, 2003.

104. Турчак JI. И. Основы численных методов. М.: Наука, 1987.

105. Уорланд Дж. Введение в теорию сетей массового обслуживания. М.: Мир, 1993.

106. Феллер В. Введение в теорию вероятностей и ее приложения. В 2-х томах. Т.1. Пер. с англ. М.: Мир, 1984.

107. Феллер В. Введение в теорию вероятностей и ее приложения. В 2-х томах. Т.2. Пер. с англ. М.: Мир, 1984.

108. Филлипс Д., Гарсиа-Диас А. Методы анализа сетей. М.: Мир,

109. Форд Л., Фалкерсон Д. Потоки в сетях. М.: Мир, 1966.

110. Харламов Б. П. Оптимальный режим обслуживания системы с наблюдаемой опасностью отказа // Автоматика и телемеханика, 1998. № 4. С. 117-134.

111. Харченко В. С. Модели и алгоритмы реконфигурации отказоустойчивых цифровых систем с адаптивной многоярусной мажоритарной структурой // Автоматика и телемеханика, 2000. № 12. С. 162 175.

112. Харченко В. С. Выбор технологии проектирования и базовых архитектур дефектоустойчивых цифровых управляющих и вычислительных систем реального времени // Космическая наука и технология, 1997. № 5. С. 37-39.

113. Харченко В. С. Литвиненко В. Г. Применение концепции многоальтернативного проектирования для построения высоконадежных и безопасных систем // Приборы и системы управления. 1993. № 6. С. 8 — 11.

114. Шибанов А. П. Моделирование стохастического поведения программ канального уровня специализированной сети передачи данных: Канд. диссертация. Рязань: РРТИ, 1993.

115. Шибанов А. П., Малыпин В. В. Моделирование стохастического поведения программ с большим числом вероятностных ветвлений // Информационные технологии: Межвуз. сб. науч. тр. Рязань: РГРТА, 1998. С. 100-108.

116. Шибанов А. П. Разработка программного обеспечения для моделирования локальных сетей Ethernet // Программирование, 2002. № 6. С. 62-71.

117. Шибанов А. П. Нахождение закона распределения выходной величины GERT-сети // Вестник Ряз. госуд. радиотехн. акад. вып. 8, 2001. С. 81-85.

118. Шибанов А. П. Минимизация ресурсов в моделях стохастической структуры // Межвуз. сб. науч. трудов "Новые информационные технологии", Рязань. 2001. С. 121 -126.

119. Шибанов А. П. Система моделирования компьютерных сетей // Сб. науч. трудов "Математическое моделирование и управление в сложных системах". М.: МГАПИ, 2001. С. 209 214.

120. Шибанов А. П. Нахождение закона распределения выходной величины GERT-сети большой размерности, статья // Информационные технологии, 2002. № 1. С. 42 45.

121. Шибанов А. П. Применение моделей стохастической структуры для анализа вероятностно-временных характеристик алгоритмов преобразования информации в специализированных сетях // Телекоммуникации, № 3. 2002. С. 35-39.

122. Шибанов А. П. Моделирование работы коммутатора в полнодуплексном режиме // Вестник Самарского аэрокосмического университета, 2002. № 1.С. 143-150.

123. Шибанов А. П. Нахождение дискретного закона распределения выходной величины GERT-сети // Вестник РГРТА, 2002. вып. 9. С. 43 48.

124. Шибанов А. П., Корячко В. П., Чернышев С. В., Кириллов С. Н., Корнеев В. А. Развитие новых информационных технологий в образовании на основе расширения сети RUNNet // Вестник Ряз. госуд. радиотехн. акад., вып. 1. 1996. С. 10-15.

125. Шибанов А. П. Нахождение плотности распределения времени исполнения GERT-сети на основе эквивалентных упрощающих преобразований // Автоматика и телемеханика, № 2. 2003. С. 117 126.

126. Шибанов А. П. Стохастическая модель канала связи // Вычислительные технологии, Т. 8. 2003. № 1. С. 111-116.

127. Шибанов А. П., Шибанов В. А., Курдюмов В. В., Морев С. В. Система моделирования лифтовых телекоммуникаций // Приборы и системы. Управление, контроль диагностика, 2003. № 7. С. 11 — 16.

128. Шибанов А. П., Курдюмов В. В., Морев С. В., Шибанов А. П. Метод анализа дисциплин обслуживания очередей коммутаторов в сетиш Ethernet // Труды четвертой межд. школы-семинара "БИКАМП-ОЗ". С

129. Петербург, 2003. С. 255 259.

130. Шибанов А. П. Передача файлов по агрегированному каналу с гарантией качества обслуживания // Вестник РГРТА, 2003. Вып. 11. С. 67 — 70.

131. Шибанов А. П., Шибанов В. А., Курдюмов В. В., Морев С. В., Наянов В. В. Программное обеспечение моделирования работы группы лифтов // Промышленные АСУ контроллеры, 2003. № 8. С. 42 44.

132. Шибанов В.А. Нахождение вероятностно-временных характере ристик телекоммуникационных систем со старением заявок // Новые информационные технологии: Межвуз. сб. науч. тр. Рязань: РГРТА, 2003. С. 128-135.

133. Шибанов В.А., Шибанов А.П. Модель телекоммуникационного канала со старением кадров // Сб. науч. трудов "Новые информационные технологии". М.: МГАПИ, 2003. С. 181 185.

134. Шорников Ю. В., Жданов Т. С., Ландовский В. В. Компьютерное моделирование динамических систем // Компьютерное моделирование 2003: Труды межд. науч.-техн. конф. СПб.: "Нестор", 2003.

135. Artalejo J. R., Gomez-Corral A. Stochastic analysis of the departureф)and quasi input processes ma versatile single server queue // J. Appl. Math. Stoch. Anal. 1996. V. 9. P. 171-183.

136. Artalejo J. R., Gomez-Corral A. Generalized birth and death processes with applications to queues with repeated attempts and negative arrivals // OR Spectrum. 1998. V. 20. P. 5 14.

137. Artalejo J. R., Gomez-Corral A. Analysis of a stochastic clearing system with repeated attempts // Stochastic Models. 1998. V. 4. P. 623 — 645.

138. Artalejo J. R., Gomez-Corral A. On a single server queue with negative arrivals and request repeated // J.Appl. Prob. 1999. V. 36. P. 907 918.

139. Artalejo J. R., Gomez-Corral A. Performance analysis of a single server queue with repeated attempts // Math. Comput. Model. 1999. V. 30. P. 79 -88.

140. Artalejo J. R., Gomez-Corral A. Computation of the limiting distribution in queueing systems with repeated attempts and disasters // RO-Recherche Operationelle/Oper. Res. (RAIRO). 1999. V. 33. P. 371-382.

141. Artalejo J. R. G-networks: a versatile approach for Work removal in queueing networks // Europ. J. Oper. Res. 2000. V. 126. P. 233 249.

142. Atencia I., Aguillera G., Bocharov P. P. On the M/G/1/0 queueing system under LCFS PR discipline with repeated and negative customers with batch arrivals // Proc. Oper. Res. 42 Annual Conf. University of Swamsea. 2000. P. 30-34.

143. Atencia I., Bocharov P. P. On the M/G/1/0 queueing system under LCFS PR discipline with repeated and negative customers // Proc. 3-rd Europ. Cong. Math. Barcelona, 2000.

144. Atencia I., D'Apice C., Manzo R., Salerno S. Retrial queueing system with several input flows negative customers and LCFS PR discipline // Proc. Fourth Int. Workshop on Queueing Networks with Finite Capacity. Ilkley, U.K. 2000.

145. Atencia I., Aguillera G., Bocharov P. P. On the M/G/1/0 queueing system under LCFS PR discipline with repeated and negative customers with batch arrivals // Proc. Oper. Res. 42 Annual Conf. University of Swamsea. 2000. P. 30-34.

146. Atencia I., Bocharov P. P. On the M/G/1/0 queueing system under LCFS PR discipline with repeated and negative customers // Proc. 3-rd Europ. Cong. Math. Barcelona, 2000.

147. Beizer B. Analytical techniques for statistical evaluation of program running time //AFIPS Conf. Proc. 1970. v. 37. C. 519 524.

148. Bianchi G. IEEE 802.11 saturation throughput analysis // IEEE Comm. Letters. 1998. V. 2. № 12. P. 318 - 320.

149. Bocharov P.P. On queueing networks with signals // Proc. Int. Conf. "Appl. Stochastic Models and Inform. Proc." Petrozavodsk, 2002. P. 27 30.

150. Chao X., Pinedo M. On generalized networks of queues with positive and negative arrivals // Prob. Eng. Inf. Sci. 1993. V. 7. P. 301-334.

151. Chao X., Pinedo M. Networks of queues with batch services, signals and product form solutions // Oper. Res. Lett. 1995. V. 17. P. 237 242.

152. Chao X. A note on queueing networks with signals and random triggering time // Prob. Eng. Inf. Sd. 1994. V. 8. P. 213 219.

153. Chao X. Networks of queues with customers, signals and arbitrary service times distributions // Oper. Res. 1995. V. 43. № 3. P. 537 544.

154. Chhaya H.S., Gupta S. Performance modeling of asynchronous data transfer methods of IEEE 802.11 MAC protocol // Wireless Networks. 1997. V. 3. № 3. P. 217 234.

155. Clingen G. T. A Modification of Fulkerson's PERT algoritm. "Operation Res", 1964. V. 12. № 4.

156. Drakopoulos E., Merges M. J. Performance analysis of client-server storage systems // IEEE Trans. Comput, 1992. V. 41 No 11. P. 1442 1452.ф)

157. Foumeau J. N., Hernandez M. Modelling defective parts in a flow system using G-networks // Proc. Second Int. Workshop on Performability Modelling of Comput. and Commun. Syst. Le Mont Saint-Michel, June. 1993.

158. Gelenbe E., Pujolle G. Introduction to queueing networks. N.Y.: John Wiley, 1998.

159. Gelenbe E. Reseaux stochastiques ouverts avec clients negatifs and positifs, et reseaux neuronaux // Comptes-Rendus de l'Academie des Sci. 1989. V. 309. SeriellP. 972-982.

160. Gelenbe E. Random neural networks with negative and positive signals and product formsolution // Neural Comput. 1989. V. 1. № 1. P. 502 510.

161. Gelenbe E. Product form queueing networks with negative and positive customers //J. Appl. Prob. 1991. V. 28. P. 656 663.

162. Gelenbe E., Schassberger R. Stability of G-networks // Prob. Eng. Inf. Sci. 1992. V. 6. P. 271-276.

163. Gelenbe E. Learning in the recurrent random neural network // Neural Comput. 1993. V. 5. № 1. P. 154 164.

164. Gelenbe E. G-networks with signals and batch removal // Prob. Eng. Inf. Sci. 1993. V. 7. P. 335-342.

165. Gelenbe E. G-networks with triggered customer movement // J. Appl. Prob. 1993. V. 3. P. 742-748.

166. Gomes-Corral .A. Retrial queues with negative customers / Ph. D. Thesis. Statist, and Oper. Res. University Complutense Madrid, 1996.

167. Gopinath P., Schwan K. Chaos. Why One Cannot Have Only an Operating System for Real-Time Applications // Operating System Rev. 1989. № 7. P. 106-125.

168. Harteley H. O., Wortham A. W. A statistical theory for PERT critical path analysis. Manag. Sci, 1966. vol. 12 № 10.

169. Henderson W. Queueing networks with negative customers and negative queue lengths // J. Appl. Prob. 1993. V. 30. P. 931 942.

170. Ho T. S., Chen К. C. Performance analysis of IEEE 802.11 CSMA/CA medium access control protocol // Proc. 7th IEEE Int. Symp. on Personal, Indoor and Mobile Radio Communications (PIMRC'96), Taipei, Taiwan. 1996. P. 407-411.

171. Kelly F. P. Reversibility and stochastic networks. N.Y.: John Wiley,1979.

172. Jackson J.R. Jobshop like queueing systems // Management Sci. 1963. V. 10. P. 131-142.

173. Liu J.W.S. et al. Algorithms for Scheduling Imprecise Computations // Computer. 1991. № 5. P. 58 68.

174. Mason S. I. Feedback theory Some properties of signal flow-graphs // Proc. of the Institute of Radio Engineers. 1953. P. 1144 - 1156.

175. Martin C., Ransom K., Zhao W. An Integrated Environment for the Development and Analysis of Hard Real-Time Systems // Real-Time Programming. Oxford: Pergamon Press, 1992. P. 27 32.

176. Natarajan S., Zhao W. Issues in Building Dinamic Real-Time Systems // IEEE Software. 1992. № 9. P. 16 21.

177. Pitel E. Queues with negative customers // Ph. D. Thesis. Imperial College, London. 1994.

178. Pritsker А. А. В., Happ W. W. GERT: Graphical Evaluation and Review Technique. Part I. Fundamentals // The Journal of Industrial Engineering (May 1966).

179. Pritsker А. А. В., Whitehouse G. E. GERT: Graphical Evaluation and Review Technique. Part I // The Journal of Industrial Engineering (May 1966).

180. Pritsker А. А. В., Whitehouse G. E. GERT: Graphical Evaluation and Review Technique. Part II // Journal of Industrial Engineering (June 1966).

181. Pritsker A. Modeling and Analysis Using Q-GERT Networks. New York: Wiley, 1977.

182. Pritsker & Associates, AID: Fitting Distributions to Observations / by Musselman K. J., Penick W. R. and Grant M. E. P&A, West Lafayette. IN. 1981.

183. Pritsker A. Introduction to simulation and SLAM II. Systems Publishing Corporation: West Lafayette, Indiana. 1984.

184. Risel H. Prime numbers and computer methods for factorization. Birkhauser: Boston. Basel. Stuttgart. 1985.

185. Stankovic J., Ramamritham K. The Spring Kernel: A New Paradigm for Real-Time Operating Systems // Operating System Rev. 1989. № 7. P. 54 -71.

186. Van Dijk N. M. Queueing networks and product forms. N.Y.: John Wiley & Sons, 1993.

187. Vishnevsky V. M., Lyakhov A.I. IEEE 802.11 wireless LAN: Saturation Throughput Analysis wiht Seizing Effect Consideration // J. Appear Cluster Comput. 2001.

188. Weinmiller J., Schlager M., Festag A. et al. Performance Study of Access Control in Wireless LANs IEEE 802.11 DFWMAC and ETSI RES 10 HIPERLAN // Mobil Networks Appl., 1997. V. 2 № 1. P. 55 - 76.

189. Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications. IEEE Standard 802.11 IEEE Press, 1997.

190. Шибанов А. П., Шибанов В. А. Система имитационного моделирования телекоммуникаций / Свидетельство об официальной регистрации программы для ЭВМ в РОСПАТЕНТ, № 2003611086 от 7.05.2003.

191. Шибанов А. П., Шибанов В. А. Система моделирования стохастического поведения алгоритмов и программ / Свидетельство об официальной регистрации программы для ЭВМ в РОСПАТЕНТ, № 2003611087 от 7.05.2003.

192. Шибанов А. П., Шибанов В. А. Редактор графов / Свидетельство об официальной регистрации программы для ЭВМ в РОСПАТЕНТ, № 2003611088 от 7.05.2003.

193. Шибанов В. А., Шибанов А. П., Курдюмов В. В., Сусарин Н. И. Система имитационного моделирования работы группы лифтов / Свиде

194. Ф тельство об официальной регистрации программы для ЭВМ в

195. РОСПАТЕНТ, № 2003611250 от 27.05.2003.

196. МОДЕЛИРОВАНИЕ ТРАФИКА ПОЛЬЗОВАТЕЛЕЙ И ИЗМЕНЕНИЯ СОСТОЯНИЯ СИСТЕМЫ

197. Рис. ПЛ.1 Л. Модель генерации трафика

198. Рис. ПЛ. 1.2. Диаграмма числа кадров, выработанных генератором G11.! Пос траение график ои МШЩЙОЙЮД ipi xf

199. В & i & : fe j L* & vsk 1 .?'- -50 -45-40-35 -зо- -25-20-15-10- --- * i i i t i 1 1 1 1 I i i i \ i r I

200. Описание графиков 1 1 i I

201. А 1 1 1 ' » 1 1 i J 1 I t * i 1 I I i ■ t I i i ■t Г 10 20 30 40 50 GO 70 80 90 1 00 110 1 20 130 140 1 50 ISO 170 1 00 1Э0 200

202. Рис. П. 1.1.3. Диаграмма числа кадров, выработанных генератором G2

203. Рис. П. 1 1.4. Гистограмма моментов времени поступления кадров в блок ST1

204. Блок-очередь Q1 имитирует входную буферную память некоторого моделируемого устройства с экспоненциальным временем обслуживания с математическим ожиданием 1,25 (задержку обеспечивает дуга W3).

205. Диаграмма текущей длины очереди блока Q3 приведена на рис. П.1.1.7.itShKpi ii- ■}'•■0,2:1. Описание графиков0,1751.10.151.I0,125а:- •1.I0,0751 10,051.I0.0251.Ifl—i---ш1. I I ягаv1. ШН1«1Ммм1в

206. О 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100 105 110 115 120-----------.,., . -----.-,■■,.■!--------. ■ ■ ■ г, .у —--У.-.-—V.

207. Рис. П. 1.1.5. Гистограмма моментов времени поступления кадров в блок ST2--0,15 -0,14 -0.13---0,12 --0,11---0/I ---0,09 -0.09 --0,07- 0.06 - -005---0LO4---0.03-0.02 --0.011. Описание I рафиковйШйШмммАнимяЁ1. Л---- L1. JU