Некоммерческое акционерное общество
АЛМАТИНСКИЙ УНИВЕРСИТЕТ ЭНЕРГЕТИКИ И СВЯЗИ
Кафедра Автоматическая Электросвязь

 

ПРОЕКТИРОВАНИЕ ТЕЛЕКОММУНИКАЦИОННЫХ СИСТЕМ
Конспект лекций
для магистрантов специальности 6М071900  – Радиотехника, электроника и телекоммуникации

 

Алматы 2013

Составила: Мухамеджанова А.Д. Проектирование телекоммуникационных систем. Конспект лекций для магистрантов специальности 6М071900 «Радиотехника, электроника и телекоммуникации». – Алматы: АУЭС, 2013. – 50 с.

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

Ил. 10, табл. 1, библиогр. 7 назв.

 Рецензент: М.В.Башкиров

 Печатается по плану издания некоммерческого акционерного общества «Алматинский университет энергетики и связи» на 2013 г.

НАО «Алматинский университет энергетики и связи», 2013 г.

Введение

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

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

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

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

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

1 лекция. Общие принципы проектирования

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

Содержание: основные понятия; правовое обеспечение (документы); этапы и стадии проектирования; виды проектирования.

Понятие о проектировании. Уровни проектирования.

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

В настоящее время перед проектировщиками стоит большая задача – автоматизировать процесс проектирования, т.е. использовать комплекс программных, технических средств для разработки ЭС.

Проектное решение – промежуточное или конечное описание объекта проектирования, необходимое и достаточное для рассмотрения и определения дальнейшего направления или окончания проектирования.

Исходные данные для проектирования системы рассматриваемого уровня задаются системой более высокого уровня; в свою очередь внутренние параметры данной системы служат исходными (выходными) данными для системы более низкого уровня.

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

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

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

Для восходящего проектирования выполнение процедур и получение решений на более низких уровнях предшествуют получению проектных решений на более высоких уровнях (см.рисунок 1.1, а).

а) Последовательность этапов восходящего проектирования БИС;

б) Последовательность этапов нисходящего проектирования РЭС.

Рисунок 1.1

Нисходящее проектирование характеризуется последовательностью выполнения процедур от высшего уровня к низшему (см. рисунок 1.1, б).

Анализ процесса проектирования ЭС привел к рассмотрению еще одного подхода получения проектного решения (см. рисунок 1.2).

 

Рисунок 1.2 - Этапы процесса проектирования ЭС

Современная подготовка инженеров радиоэлектронного профиля осуществляется в такой же последовательности.

 

Правовое обеспечение (документы).

Техническое задание является исходным и обязательным документом для создания, приемки или сдачи проекта и должно содержать все исходные данные и требования к проектному объекту (см.рисунок1.5).

Документы должны содержать:

-    характеристику объекта проектирования, его назначение, условия применения, критерии эффективности его функционирования;

-    характеристику процесса проектирования (общее описание процесса, требования к входной и выходной информации и пр.);

-    технико-экономические показатели объекта;

-    порядок испытания и ввода в действие.

Для очень сложных объектов иногда разрабатываются «Технические предложения» и «Эскизный проект», но эти стадии не являются обязательными.

Стадии «Технический проект» и «Рабочий проект» для несложных объектов объединяются в «Технический проект».

Технический проект содержит следующие документы:

-    ведомость;

-    пояснительную записку;

-    схему процесса проектирования, подсистем, средств обеспечения;

-    смету затрат;

-    ТЗ на разработку соисполнителями отдельных компонентов;

-    расчет ожидаемой эффективности.

Рабочий проект содержит:

-    ведомость;

-    пояснительную записку;

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

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

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

 

Этапы проектирования.

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

1) Определение типа сети передачи данных.

2) Проектирование физических носителей сети.

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

4) Проектирование системы управления основной сетью.

5) Определение интерфейсов основной сети в другие сети.

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

7) Проектирование систем управления наложенными сетями.

8) Определение интерфейсов в другие наложенные сети.

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

Рассмотрим коротко предложенные выше этапы.

Первый этап – определение типа сети передачи данных.

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

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

Четвертый этап – проектирование системы управления основной сетью.

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

Шестой этап – планирование технологий, протоколов передачи данных и политик маршрутизации наложенных сетей различных уровней.

Седьмой этап – проектирование систем управления наложенными сетями.

Восьмой этап – определение интерфейсов в другие наложенные сети.

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

 

2    лекция. Большие системы и методы их анализа

 

Цель: ознакомить обучающихся с понятием «большая система», методами анализа их, блочно-итерационного подхода и показать, что телекоммуникационные системы – это «большие системы».

 

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

 

Понятие о больших системах, их свойства.

Большая система — управляемая система, рассматриваемая как совокупность взаимосвязанных управляемых подсистем, объединенных общей целью функционирования.

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

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

 

Свойства БС.

БС широко распространены в природе, технике, обществе, но, несмотря на многообразие, имеют ряд общих свойств.

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

Поведение больших систем носит вероятностный характер.

Поведение больших систем имеет единственную траекторию в прошлом и многовариантность альтернатив – в будущем.

 

Рисунок 2.1 – Траектория поведения БС

 

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

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

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

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

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

 

Управление БС.

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

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

Характерная особенность современного направления развития техники управления большими системами — слияние систем управления технологическими процессами и систем организационного управления в объединенные системы управления, в которых обеспечивается наиболее эффективное и экономное использование информации и технических средств.

 

Блочно–иерархический подход.

Проектирование и анализ больших систем основывается на методологии блочно-иерархического подхода (БИП), представленного тремя концепциями:

-      разбиение и локальная оптимизация;

-      абстрагирование;

-      повторяемость.

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

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

Повторяемость заключается в использовании существующего опыта проектирования.

Основное достоинство блочно-иерархического подхода – упрощение процесса проектирования за счет решения более простых задач на каждом иерархическом уровне.

 

Математическое описание большой системы.

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

 

                                       y=F( x1, …, xn ),                                           ( 2.1 )

 

где y, x1, …, xn - показатели, описывающие систему;

F- реальная зависимость между показателями.

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

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

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

2.  Другая характерная особенность рассматриваемых объектов состоит в большой  изменчивости их структуры.

3.  Построение моделей систем в виде алгебраических многочленов основано на предположении независимости переменных системы.

При традиционном подходе к построению приближенных зависимостей ослабить или даже “обойти” перечисленные требования невозможно.

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

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

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

 

y=a0+a1 f1 (x)+…am fm(x),                                       ( 2.2 )

 

где     x=( x1, …, xn ) - вектор показателей системы;

a0, a1,…, am - коэффициенты модели;

f1(x),…, fm(x) - некоторые функции.

Построение приближенной зависимости в виде (2.2) имеет значительные преимущества по сравнению с построением приближенной зависимости в виде алгебраического многочлена.

лекция. Современное состояние телекоммуникационных систем

Цель: описать современное состояние телекоммуникационных систем, их особенности, основные направления совершенствования.

Содержание: основные определения; свойства ТКС; направления развития ТКС.

Основные определения.

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

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

Телекоммуникационные системы (ТКС) состоят из: технических средств, программного обеспечения, пользователей (абонентов) и системы управления. Взаимодействие этих элементов позволяет реализовать главную цель ТКС – передача, хранение и обработка информации.

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

1) Социальные задачи представлены задачами:

-      повысить качество труда, которое оценивается соотношением «производственной стоимости» к «затратам труда»;

-      расширять зону обслуживания, как по территории, так и по населению этой территории;

-      увеличить состав и качество услуг.

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

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

Все рассмотренные задачи должны учитываться еще при проектировании ТКС.

Свойства ТКС.

Назовем основные свойства телекоммуникационных систем:

1)Телекоммуникационные системы являются информационными системами. Смысл функционирования этих систем — транспортировка (перенос) информации.

2) Телекоммуникационные системы состоят из двух основных подсистем: технической и пользовательской. Взаимодействие этих различных по своей физической сущности подсистем определяет структуру и функции телекоммуникационной системы.

3) Телекоммуникационные системы являются «большими» системами, содержащими огромное количество компонентов, многие из которых — сами большие системы либо многофункциональные устройства. Компоненты телекоммуникационной системы имеют различное устройство и выполняют различные функции.

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

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

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

7) Телекоммуникационные системы являются эргатическими.

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

9) Телекоммуникационные системы нелинейны. Важно отметить следующие моменты:

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

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

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

11) Телекоммуникационные системы находятся в непрерывном развитии.

12) Телекоммуникационные системы наукоемки и базируются на перспективных технических разработках.

13) Телекоммуникационные системы являются сложными системами высокого уровня, т.е. сверхсложными.

 

Основные направления развития.

Перспективными направлениями развития сетей связи являются следующие:

1) Расширение использования дискретных сигналов.

2) Увеличение видов передаваемой информации за счет передачи документов, схем, видеоизображений.

3) Расширение функций обработки информации за счет включения в сеть связи ЭВМ.

4) Увеличения территории обслуживания различными видами связи (кабельная, радиорелейная, спутниковая, подвижная).

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

6) Использование высокоскоростных каналов связи – оптическое волокно, волноводы.

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

Учитывая сказанное выше, можно сформулировать главную цель совершенствования ТКС – глобализация связи и ее персонализация. Глобальная информационная структура может быть представлена объединением транспортной сети и распределенной сети доступа, предоставляющих любую информацию пользователям. Это может быть обеспечено высокими скоростями передачи, интеграцией видов информации, интеллектуализацией сетей, мобильностью связи.

 

4    лекция. Моделирование больших систем [5]

 

Цель: ознакомить обучающихся с кибернетическим понятием «большая система», показать возможность декомпозиции, характеристики и требования к моделям.

 

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

Уровни моделирования.

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

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

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

Принято выделять три уровня:

-      микроуровень;

-      макроуровень;

-      метауровень.

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

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

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

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

 

Формы представления моделей и требования к ним.

Принято выделять следующие формы представления моделей.

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

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

Аналитическая – совокупность выражений явной аналитической зависимости y = f(x).

Схемная – графическая – представление модели с использованием схем, чертежей, графов.

Независимо от формы представления моделей к ним предъявляются определенные требования:

1)      Адекватность – это свойство модели отражать заданные характеристики объекта с приемлемой точностью. Точность определяется как степень совпадения значений выходных параметров модели и объекта

 

,                                               (4.1)

где ỹ – параметр модели;

y_j – параметр объекта.

2)Экономичность:

а) минимум затрат вычислительных ресурсов (объем памяти ЭВМ П и время расчетов Т);

б) максимум эффекта от реализации.

3) Универсальность – широкая область использования и максимальный учет множества учитываемых факторов N. В качестве N принимают размер решаемой системы уравнений, число элементов рассматриваемой системы и т.д. При расчете экономичности используют не абсолютное значение П и Т, а их зависимость от объема модели:

 

                   ,           ,                                          (4.2)

 

где c, k, α, β– коэффициенты.

Наиболее экономичными являются модели с линейной зависимостью.

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

Перечисленные требования часто являются противоречивыми, несовместимыми. Например, увеличение точности расчетов часто требует увеличения времени расчетов, а универсальность требует повышенных объемов памяти ЭВМ, поэтому необходимо в каждом конкретном случае находить компромиссное решение.

 

Основные этапы моделирования больших систем.

1.  Построение концептуальной (описательной) модели системы и её формализация.

2.  Алгоритмизация модели и её машинная реализация.

3.  Получение и интерпретация результатов моделирования.

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

Последовательность действий:

1)  Проведение границы между системой и внешней средой. 

2)  Исследование моделируемого объекта с точки зрения выделения основных составляющих функционирования системы (по отношению к поставленной цели)

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

4)  Оставшиеся элементы модели группируются в блоки: 

-      Блоки I-ой группы представляют собой имитатор событий внешних воздействий.

-      Блоки II-ой группы являются собственно моделью процесса функционирования.

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

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

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

Исходный материал – блочная логическая схема. 

Последовательность действий:

-      Разработка схемы моделирующего алгоритма.

-      Разработка схемы программы.

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

-      Процесс программирования и отладки.

-      Проверка достоверности программы на тестовых примерах.

-      Составление технической документации.

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

Последовательность действий:

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

Главная задача – дать максимальный объем информации об объекте моделирования при минимальных затратах машинного времени.

-      Проведение собственных расчетов (контрольная калибровка модели).

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

-      Интерпретация результатов моделирования. Подведение итогов. 

-      Составление технической документации.

Различают стратегическое и тактическое планирование:

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

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

 

Рисунок 4.1 - Схема итеративной калибровки модели

 

Три основных класса ошибок:

-      Ошибки формализации. Как правило, возникают, когда модель недостаточно подробна определена.

-      Ошибки решения. Некорректный или слишком упрощенный метод построения модели.

-      Ошибки задания параметров системы.

Проверка адекватности модели некоторой системы заключается в анализе её соразмерностей, а также равнозначности системы.

 

5    лекция. Элементы, параметры и показатели системы

 

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

 

Содержание: приведена возможная классификация параметров; требования к показателям; определены целевые функции.

Классификация параметров.

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

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

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

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

Количественно любая система описывается совокупностью величин, которые могут быть разбиты на два класса:

1) параметры (П), описывающие первичные свойства системы и являющиеся исходными данными при исследовании системы;

2) характеристики (Х), описывающие вторичные свойства системы и определяемые как функции параметров системы: Х=f(П).

Параметры любой системы подразделяются на:

а) внутренние, описывающие структурно-функциональную организацию системы;

б) внешние, описывающие взаимодействие системы с внешней (по отношению к системе) средой.

К внутренним параметрам относятся:

а) структурные параметры, описывающие состав элементов системы и саму её структуру;

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

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

Характеристики системы делятся на:

а) глобальные, показывающие эффективность функционирования системы в целом;

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

К глобальным характеристикам системы относятся:

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

б) временные характеристики, описывающие временные аспекты функционирования системы;

в) надежностные характеристики, определяющие надежность функционирования системы;

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

Исходными данными для проектирования являются следующие характеристики системы ТКС:

-    варианты схем организации связи;

-    социально-экономические характеристики и расположение пунктов;

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

-    требуемые пропускные способности линий;

-    требуемые показатели надежности.

Глобальные характеристики:

-    конфигурация сети линий и каналов связи;

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

-    способ доставки сообщений (без коммутации, с коммутацией каналов, коммутаций сообщений, пакетов).

Технологические характеристики:

-    вид процедуры выбора пути;

-    дисциплина очередей;

-    технология обработки сообщений в узлах.

Конструктивно-технологические характеристики:

-    технические характеристики аппаратуры и кабелей;

-    емкость отдельных линий;

-    величина пропускной способности каналов связи;

-    необходимые показатели надежности и стоимости.

Эксплуатационные характеристики:

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

-    вероятность изоляции отдельного пункта;

-    вероятность предоставления требуемого канала и т.д.

 

Требования к показателям.

Основные показатели, которые должны определяться при проектировании, это:

-    надежность;

-    пропускная способность;

-    экономичность;

-    управляемость.

 

6    лекция. Сеть как объект анализа и синтеза

 

Цель: ознакомить обучающихся с постановками задач синтеза, их моделями и общими идеями решения.

 

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

 

Факторы, характеризующие объект синтеза, общую модель решения задач структурного синтеза.

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

«Синтез» в переводе с греческого означает «соединение, составление». 

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

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

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

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

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

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

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

Сеть как объект анализа и синтеза можно представить:

-    технической базой (линии, станции, оконечные устройства);

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

-    алгоритмикой работы – процедуры выбора путей передачи сообщений, дисциплиной очередей и т.д.

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

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

Задача состоит в том, чтобы по заданному функциональному назначению объекта или закону его функционирования получить набор параметров: X = (описывающих объект.

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

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

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

Модель задачи можно записать так: определить набор ,

удовлетворяющий условиям:

                                   (6.1)

при ограничениях

(6.2)

 

.                                                     (6.3)

 

Модель задачи (6.1 – 6.3) включает в себя задачи поиска структуры объекта и расчета его параметров, которые соответственно называются задачами структурного и параметрического синтеза. Эти задачи относятся к области математики, называемой «исследование операций» или «математическое программирование», которые в зависимости от вида функций (6.1 – 6.2) и характера переменных (6.3) подразделяются на:

-    линейное программирование;

-    нелинейное программирование;

-    динамическое программирование;

-    дискретное программирование;

-    целочисленное программирование.

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

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

а) выбор или формирование вариантов сочетаний параметров;

б) подсчет целевой функции;

в) принятие решения о дальнейших действиях.

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

Задача упрощается, если множество вариантов конечно (по постановке задачи или в силу ограничений), тогда задача становится комбинаторной.

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

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

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

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

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

-    уменьшением числа шагов поиска;

-    постановкой более скромных задач (не оптимальное, а любое приемлемое решение);

-    сокращением времени на этапе оценки варианта.

Недостатки метода – получение не оптимального, а некоторого инженерного решения, причем часто нет даже оценки близости его к оптимальному.

6)             Сведения задачи структурного синтеза к задачам дискретного математического программирования.

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

-    всем существенным элементам, характеризующим проектируемую структуру, поставить в соответствие некоторые величины  и сгруппировать их в вектор  – ;

-    установить количесвтенный критерий и выразить его в виде функции  ) и в виде ограничений , .

Большинство признаков (элементов) структуры не имеет количественных характеристик – это тип оборудование, тип канала и т.д.

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

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

 

7    лекция. Задача синтеза транспортной сети

 

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

Каждой дуге сети поставлены в соответствие три характеристики:

-    – функция стоимости;

-    – пропускная способность;

-    – величина перемещаемого потока.

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

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

,

где – себестоимость транспортирования;

– стоимость создания ребра.

Для выполнения этих условий вводится специальная функция

и функция стоимости принимает вид

.                                    (7.1)

На величины потоков накладываются ограничения:

-    поток по ребруне может превышать величину пропускной способности

;                                                 (7.2)

-    сумма исходящих из потоков должна равняться , а входящих в – равняться

                  (7.3)

 

-    сумма входящих в вершину i потоков равна сумме выходящих

 

 (7.4)

 

Задача построения сети для перемещения всего потокав  с минимальными затратами может быть представлена моделью математического программирования.

Определить , удовлетворяющие условиям

 (7.5)

,                                               (7.6)

,                        (7.7)

,                                            (7.8)

                           ,                                        (7.9)

(7.10)

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

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

Шаг 0. Произвести первоначальное распределение потока, удовлетворяющее ограничениям (7.6 – 7.9).

Шаг 1. Построить дерево графа, включая в него в первую очередь основные дуги (т.е. дуги, на которых ). Если таковых меньше, чем дуг дерева (где – число вершин графа), то включаются дуги с нулевым () или насыщенным () потоком.

Шаг 2. Для каждой хорды строится цикл из дуг дерева. Направление обхода цикла определяется из следующих условий:

1) если , то поток на дугеможно только увеличить, и направление обхода цикла совпадает с направлением дуги ;

2) если , то поток на ней можно только уменьшить, и направление обхода будет противоположно дуге.

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

,

.

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

,

а на дугах отрицательной – уменьшение потока до нуля, т.е.

.

Общее изменение потока в цикле

.

Шаг 3. Величина нового потока в цикле определяется соотношением

 .

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

,

.

Если , поток не меняется, проверяется следующий цикл (шаг 2).

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

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

После построения дерева подсчитываются потенциалы вершин.

.

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

 

,

 

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

 

8 лекция. Задача синтеза централизованной сети

 

Цель: ознакомить студентов с постановкой задачи синтеза централизованной сети, ее экономико-математической моделью и алгоритмом её решения.

 

Содержание: описание постановки задачи синтеза централизованной сети, формирование ее модели и методы ее реализации.

 

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

Централизованной называется сеть, если в ней существует два иерархических уровня:

- терминалы Т_i, i=1, 2,..., n, которые могут подключаться к удаленному концентратору К_j, , или непосредственно к ЭВМ;

- удаленные концентраторы К_j, которые соединяются с центральной ЭВМ.

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

Итак, заданными являются:

- множества терминалов Т_i и концентраторов К_j (), ЭВМ – К₀;

- стоимости линий связи

, ;

- стоимость создания концентраторов и их пропускная способность f_j, r_j.

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

Обозначим такие соединения Т_i с К_j переменной x_ij=1, при отсутствии связи – х_i=0.

Будем называть концентратор К_j открытым, если он используется, и закрытым – в противном случае. Эта ситуация отражается переменной y_j:

Очевидно, что

 (8.1)

Тогда целевая функция стоимости запишется в виде:

(8.2)

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

(8.3)

(8.4)

Каждый терминал должен быть подключен либо к ЭВМ (j=0), либо к одному из концентраторов.

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

Задача представлена целочисленной (ноль-единичной) моделью линейного программирования.

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

 

Алгоритм метода добавления.

Алгоритм основан на идее последовательного улучшения плана и представляет итерационный процесс.

Шаг 0. Первоначально план прикрепления терминалов представлен множеством

,

т.е. все терминалы прикреплены к ЭВМ. Очевидно, что это самое дорогое решение

Итерация 1.

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

Шаг 1. Откроем К₁. Эффект от изменения присоединения Т_i, к К₁ вместо К₀определим по формуле

 .                                                         (8.5)

Очевидно, что присоединить к К₁, целесообразно только те Т_i, для которых подсчитанные разности (8.5) будут положительными. Однако число таких присоединяемых Т_i ограничено . Подсчитаем эффект, учитывая затраты f₁ на создание концентратора К₁.

.

(включены только , число их меньше ).

Аналогичных шагов будет m (по числу концентраторов).

Шаг . Определяются наименьшие затраты

.

Следовательно, откроем концентратор К_j, присоединив к нему .

Итерация 2.

Считая открытым концентратор К_j, будем открывать по очереди еще по одному концентратору.

Шаг 1. Откроем К₁, при открытом К_j оценим:

,

(8.6)

Выбираются , наибольших разностей (8.6) и подсчитываются затраты

.

Шагов будет  (по числу закрытых еще концентраторов).

Шаг m. Определяется наименьшее значение функции

.

Итерация 3.

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

Последняя итерация состоит в открытии всех концентраторов одновременно.

 

Применение алгоритма метода добавления.

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

Исходные данные приведены в матрице, векторах и .

 

Таблица 1 – Матрица данных

	K0	K1	K2	K3	K4
T1	4	0	2	2	3
T2	8	5	6	4	10
T3	7	4	3	1	2
T4	4	5	11	2	0
T5	3	4	9	2	5
T6	9	7	10	4	3

 

Шаг 0. Посчитаем по формуле .

.

Итерация 1.

Шаг 1.Открываем . Подсчитаем разность стоимости подключения терминала к ЭВМ или .

,

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

.

Шаг 2.Открываем :

.

 

Шаг 3. Открываем  :

 

Шаг 4. Открываем :

,

.

 

 

Рисунок 8.1 – Прикрепление терминалов после первой итерации

 

Итерация 2.

Шаг 1. При открытом открываем :

 

Шаг 2. При открытом  открываем :

Шаг 3. При открытом открываем:

=19 ,       

Прикрепление терминалов показано на рисунке 8.2.

 

 

Рисунок 8.2 – Прикрепление терминалов после второй итерации

 

Итерация 3.

Шаг 1. При открытых  и   открываем :

;

 

 

Шаг 2. При открытых  и  открываем :

 

Уменьшение целевой функции показывает целесообразность открытия концентратора (см. рисунок 8.3).

 

 

Рисунок 8.3 – Прикрепление терминалов после третьей итерации

 

Итерация 4. Проверим целесообразность открытия при открытых,   и :

 

 

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

 

9    лекция. Задача распределения каналов на некоммутируемой сети

 

Цель: ознакомить студентов с задачей синтеза некоммутируемых вторичных сетей.

 

Содержание: постановка задачи, формирование модели.

 

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

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

Дана первичная сеть, структура которой представлена графом,  где

Задана емкость каждой линии первичной сети в виде матрицы емкостей

Иногда задается дополнительно длина или стоимость линий .

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

.

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

План – это набор путей каждой корреспондирующей пары K

и оптимальное число каналов в каждом пути .

Требования к решению:

− общее число задействованных каналов должно быть минимально (минимизироваться может длина каналов или их стоимость)

(9.1)

− каждая корреспондирующая пара обеспечена требуемым числом каналов

(9.2)

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

(9.3)

Условие (9.1) – это целевая функция задачи. Пусть – ранг пути ,  – число каналов в нем. Тогда минимизация числа каналов выразится соотношением

 (9.1′)

Минимизация стоимости

                                     (9.1″)

Полученная модель (9.1 – 9.3) – линейная целочисленная. Модель может быть дополнена ограничениями, например, на длину или ранг путей .

Реализация модели возможна методами целочисленного линейного программирования, однако, значительно проще ее можно решить эвристическим методом, описание которого приведено в методических указаниях [7].

 

10 лекция. Задача нахождения кратчайших путей

 

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

 

Содержание: алгоритм Дейкстры; алгоритм Флойда; переборные алгоритмы.

 

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

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

1) алгоритм Дейкстры;

2) алгоритм Флойда;

3) переборные алгоритмы.

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

 

Алгоритм Дейкстры.

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

Каждой вершине приписывается вес – это вес пути от начальной вершины до данной. Также каждая вершина может быть выделена. Если вершина выделена, то путь от нее до начальной вершины кратчайший, если – нет, то временный. Обходя граф, алгоритм считает для каждой вершины маршрут, и, если он оказывается кратчайшим, выделяет вершину. Весом данной вершины становится веc пути. Для всех соседей данной вершины алгоритм также рассчитывает вес, при этом ни при каких условиях не выделяя их. Алгоритм заканчивает свою работу, дойдя до конечной вершины, и весом кратчайшего пути становится вес конечной вершины.

Алгоритм Дейкстры

Шаг1. Всем вершинам, за исключением первой, присваивается вес равный бесконечности, а первой вершине – 0.

Шаг 2. Все вершины не выделены.

Шаг 3. Первая вершина объявляется текущей.

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

Шаг 5. Среди невыделенных вершин ищется вершина с минимальным весом. Если таковая не найдена, то есть вес всех вершин равен бесконечности, то маршрут не существует. Следовательно, выход. Иначе, текущей становится найденная вершина. Она же выделяется.

Шаг 6. Если текущей вершиной оказывается конечная, то путь найден, и его вес есть вес конечной вершины.

Шаг 7. Переход на шаг 4.

Для определения самого кратчайшего пути введем массив P вершин, где P[v] будет содержать вершину, непосредственно предшествующую вершине v в кратчайшем пути (см. рисунок 10.1).

 

 

Рисунок 10.1-Демонстрация алгоритма Дейкстры

 

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

 

Алгоритм Флойда.

Рассматриваемый алгоритм иногда называют алгоритмом Флойда-Уоршелла. Алгоритм Флойда-Уоршелла является алгоритмом на графах, который разработан в 1962 году Робертом Флойдом и Стивеном Уоршеллом. Он служит для нахождения кратчайших путей между всеми парами вершин графа.

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

Основная идея алгоритма. Пусть есть три вершины i, j, k и заданы расстояния между ними. Если выполняется неравенство A[i,k]+A[k,j]<A[i,j], то целесообразно заменить путь i->j путем i->k->j. Такая замена выполняется систематически в процессе выполнения данного алгоритма.

Шаг 0. Определяем начальную матрицу расстояния A₀ и матрицу последовательности вершин S₀. Каждый диагональный элемент обеих матриц равен 0, таким образом, показывая, что эти элементы в вычислениях не участвуют. Полагаем k = 1.

Основной шаг k. Задаем строку k и столбец k как ведущую строку и ведущий столбец. Рассматриваем возможность применения замены описанной выше, ко всем элементам A[i,j] матрицы A_k-1. Если выполняется неравенство , тогда выполняем следующие действия:

-    создаем матрицу A_k путем замены в матрице A_k-1 элемента A[i,j] на сумму A[i,k]+A[k,j];

-    создаем матрицу S_k путем замены в матрице S_k-1 элемента S[i,j] на k. Полагаем k = k + 1 и повторяем шаг k.

Таким образом, алгоритм Флойда делает n итераций, после I -й итерации матрица А будет содержать длины кратчайших путей между любыми двумя парами вершин при условии, что эти пути проходят через вершины от первой до I -й. На каждой итерации перебираются все пары вершин, и путь между ними сокращается при помощи I-й вершины (см. рисунок 10.2).

 

 

Рисунок 10.2 -Демонстрация алгоритма Флойда

 

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

 

Переборные алгоритмы.

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

Лабиринт, состоящий из проходимых и непроходимых клеток, задан матрицей A размером mxn. Элемент матрицы A[i,j]=0, если клетка (i, j) проходима. В противном случае .

Требуется найти длину кратчайшего пути из клетки (1, 1) в клетку (m, n).

Фактически дана матрица смежности (только в ней нули заменены бесконечностями, а единицы – нулями). Лабиринт представляет собой граф.

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

 

11    лекция. САПР, причины и цели создания. Виды САПР

 

Цель: ознакомить студентов с понятием автоматизированного проектирования, причинами и целями его создания и применения, видами систем.

 

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

 

Виды САПР.

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

Статистика утверждает, что с 1900 по 1960 гг. производительность труда на производстве возросла на 1000%, а в информационной сфере – только на 20%, в 70-х годах эти показатели составляли 80% и 4% соответственно. Решение этих проблем пытались осуществить экстенсивным путем,  увеличивая количество проектировщиков.

К середине ХХ века научно-техническая революция привела к следующим показателям:

-    число различных классов технических систем удваивалось каждые 10 лет;

-    сложность изделий по числу деталей удваивалось каждые 15 лет;

-    объем научно-технической информации удваивался через 8 лет;

-    время создания новых изделий уменьшалось вдвое через 25 лет.

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

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

В рамках жизненного цикла промышленных изделий САПР решает задачи автоматизации работ на стадиях проектирования и подготовки производства.

Основная цель создания САПР — повышение эффективности труда инженеров, включая:

-    сокращения трудоёмкости проектирования и планирования;

-    сокращения сроков проектирования;

-    сокращения себестоимости проектирования и изготовления, уменьшение затрат на эксплуатацию;

-    повышения качества и технико-экономического уровня результатов проектирования;

-    сокращения затрат на натурное моделирование и испытания.

Достижение этих целей обеспечивается путем:

-    автоматизации оформления документации;

-    информационной поддержки и автоматизации процесса принятия решений;

-    использования технологий параллельного проектирования;

-    унификации проектных решений и процессов проектирования;

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

-    стратегического проектирования;

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

-    повышения качества управления проектированием;

- применения методов вариантного проектирования и оптимизации.

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

Различают 4 вида САПР:

1) Уникальные САПР, имеющие межотраслевой характер, создаваемые для решения крупнейших хозяйственных и научно-технических задач.

2) Универсальные САПР отраслевого назначения с системой коллективного пользования, обеспечивающие проектирование всей номенклатуры технических изделий отрасли. Такие САПР обычно строятся на 2-х уровнях: на первом – мощная ЭВМ с большим объемом памяти и высоким быстродействием, а на втором – периферийные персональные компьютеры, обслуживающие абонентские пункты. Годовой объем проектной продукции – до 100 тысяч документов.

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

4) Индивидуальные САПР, работающие на ПЭВМ, предназначенные для выполнения отдельных видов инженерных расчетов (инженерно-графические работы, сметные расчеты, трассировка печатных плат и т.д.).

 

Классификация САПР.

Классификация САПР производится:

-    по типу объектов проектирования (изделия машиностроения, приборостроения, объекты строительства, организационные системы и т.д.);

-    по уровню комплексности автоматизации (автоматизации подлежит <25%, 25…50%, >50% работ);

-    по сложности (наличию подсистем) (простые – 10² подсистем, сложные – 10⁴ подсистем; очень сложные – 10⁶ подсистем);

-    по числу уровней технического обеспечения (одно-, двух- и трехуровневые).

ГОСТ 23501.108-85 устанавливает следующие признаки классификации САПР:

-    тип/разновидность и сложность объекта проектирования;

-    уровень и комплексность автоматизации проектирования;

-    характер и количество выпускаемых документов;

-    количество уровней в структуре технического обеспечения.

Целью создания САПР являются:

-    повышение качества и технико-экономического уровня проектируемых объектов, в том числе при их создании и применении;

-    повышение производительности труда проектировщиков, сокращение сроков и уменьшение стоимости проектирования.

Для достижения цели необходимо:

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

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

-    унифицировать и стандартизировать методы проектирования;

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

-    произвести подготовку и переподготовку специалистов.

 

Эффективность САПР.

Эффективность использования САПР проявляется на протяжении всего жизненного цикла объекта, т.е. на стадии проектирования, строительства (создания) и эксплуатации.

В процессе проектирования эффект получается за счет сокращения сроков и снижения стоимости проектирования:

В процессе строительства и эксплуатации объекта эффект получается за счет реализации проекта с оптимальными параметрами:  – снижение капитальных и эксплуатационных затрат.

Критерием эффективности САПР принимается годовой экономический эффект

 ,

где    – стоимость создания САПР.

Срок окупаемости капитальных вложений

, год.

 

12    лекция. Структура САПР

 

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

 

Содержание: подсистемы объектно-ориентированные и инвариантные, схема соединения подсистем, построенных по типу выполняемых работ.

 

САПР, созданная для проектирования большой системы, сама является большой системой, состоящей из отдельных взаимосвязанных блоков – подсистем.

Как и любая сложная система, САПР состоит из подсистем. Различают подсистемы проектирующие и обслуживающие.

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

Обслуживающие подсистемы обеспечивают функционирование проектирующих подсистем, их совокупность часто называют системной средой (или оболочкой) САПР. Типичными обслуживающими подсистемами являются подсистемы управления проектными данными, подсистемы разработки и сопровождения программного обеспечения CASE(Computer Aided Software Engineering), обучающие подсистемы для освоения пользователями технологий, реализованных в САПР.

 

Схема САПР по виду выполняемых работ.

Подсистемой называют выделенную по некоторому признаку часть САПР, обеспечивающую получение законченных проектных решений. Выделение подсистем неоднозначно.

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

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

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

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

1) монитор;         

2) подсистема поиска решений технической задачи;

3) подсистема инженерного анализа;

4) подсистема ведение и изготовления документации;

5) подсистема информационная.

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

В общем случае она включает:

− собственно управляющую программу;

− программу связи с пользователем;

− программу диагностики ошибок;

− обслуживающие и вспомогательные подпрограммы;

− БД мониторной подсистемы.

 

Подсистема поиска решений инженерной задачи.

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

− сокращение времени разработки конструктивных решений;

− возможность генерации решения, близкого к глобально-оптимальному, что повышает качество на 20-30%.

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

 

Подсистема инженерного анализа (моделирования объекта и оптимизация его характеристик).

Основное назначение – выполнение всех вычислительных работ. Арсенал применяемых методов очень широк:

− аналитические (детерминированные и стохастические);

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

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

− экспертные подсистемы.

 

Подсистема ведения и изготовления документации.

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

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

Многие САПР ориентированы на сквозную автоматизацию:

проектирование → подготовка производства → изготовление.

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

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

 

Информационная подсистема.

Основная задача этой полсистемы состоит в сборе, хранении, упорядочении и выдаче по запросу всей необходимой информации. Система состоит из базы данных и системы управления базой – СУБД.

База данных + СУБД = Банк данных.

База содержит:

− полные сведения о проектируемом объекте и требования к нему;

− сведения о мировом научно-техническом уровне, фиксируемом в виде публикаций патентов, изобретений;

− методы генерации проектных решений;

− методика проектирования;

− архив;

− руководящие и справочные материалы, ГОСТы.

Рассмотренная система САПР является инвариантной по отношению к объекту проектирования. Используемая технология предполагает диалоговый характер проектирования.

 

13    лекция. Обеспечения САПР [4]

 

Цель: изучить структуру и содержание обеспечений САПР.

 

Содержание: описано обеспечение: методического, математического, технического, лингвистического, информационного, программного и организационного характера.

 

Структурирование САПР по различным аспектам обусловливает появление видов обеспечения.

Принято выделять семь видов обеспечения:

1) Комплекс средств автоматизации проектирования – это совокупность различных видов обеспечения автоматизированного проектирования, необходимых для выполнения автоматизации.

2) Математическое обеспечение (МО) – это совокупность математических методов, математических моделей и алгоритмов проектирования.

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

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

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

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

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

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

7)         Информационное обеспечение – совокупность сведений, необходимых для выполнения проектирования, представленных в заданной форме. Основа – автоматизированные банки данных (БД), которые состоят из баз данных и систем управления базами данных (СУБД). В информационное обеспечение входят нормативно-справочные документы, прогнозы технического развития, типовые проектные решения, системы классификации кодирования технико-экономической информации, файлы и блоки данных на машинных носителях, нормативные, плановые, типовые решения и т.д.

База данных должна отвечать определенным требованиям, основными из них являются:

− принцип информационного единства;

− полнота сведений;

− гибкость;

− надежность;

− адаптивность;

− наращиваемость;

− неизбыточность.

Лингвистическое обеспечение (ЛО) – это совокупность языков проектирования, включая термины и определения, правила формализации естественного языка и методы сжатия и развертывания текстов.

Методическое обеспечение (МТО) – совокупность документов, устанавливающих состав и правила отбора средств обеспечения САПР. В некоторых публикациях в методическое обеспечение включается МО и ЛО.

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

 

Заключение

 

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

 

 

Список литературы

 

1 Крухмалев В.В., Гордиенко В.Н. и др. Основы построения телекоммуникационных систем и сетей. – М.: Горячая линия – Телеком, 2004.

2 Берж К. Теория графов и ее применение. – М.: Иностранная литература, 1962.

3 Алексеев Е.Б., Гордиенко В.Н., Крухмалев В.В. Проектирование и техническая эксплуатация цифровых телекоммуникационных систем и сетей. – М.: Горячая линия – Телеком, 2008.

4 Корячко В.Г., Курейчик В.М., Норенков И.П. – Теоретические основы САПР. – М.: Энергоатомиздат, 1987.

5 Шварц М. Сети ЭВМ. Анализ и проектирование. – М.: Радио и связь, 1981.

6 Норенков И.П. Основы автоматизированного проектирования – М.: Из-во МГТУ им. Н.Э. Баумана, 2000.

7 Данилина Г.П. МУ по дисциплине Основы построения сетей и систем телекоммуникаций – А., АИЭС, 2007.

 

 

Содержание

 

Введение	4
1 лекция. Общие принципы проектирования	5
2 лекция. Большие системы и методы их анализа	8
3 лекция. Современное состояние телекоммуникационных систем	13
4 лекция. Моделирование больших систем	15
5 лекция. Элементы, параметры и показатели системы	19
6 лекция. Сеть как объект анализа и синтеза	22
7 лекция. Задача синтеза транспортной сети	26
8 лекция. Задача синтеза централизованной сети	28
9 лекция. Задача распределения каналов на некоммутируемой сети	35
10 лекция. Задача нахождения кратчайших путей	36
11 лекция. САПР, причины и цели создания. Виды САПР	40
12 лекция. Структура САПР	43
13 лекция. Обеспечения САПР	46
Заключение	48
Список литературы	48

Сводный план 2013 г., поз 267

Альмира Далелханкызы Мухамеджанова

ПРОЕКТИРОВАНИЕ ТЕЛЕКОММУНИКАЦИОННЫХ СИСТЕМ
Конспект лекций
для магистрантов специальности 6М071900  – Радиотехника, электроника и телекоммуникации

Редактор  Л.Т.Сластихина
Специалист по стандартизации Н.К. Молдабекова

 

Подписано в печать 
Формат 60х84 1/16
Тираж 50 экз.
Бумага типографская №1
Объём 3,1 уч.-изд.л. 
Заказ___Цена 310 тенге

Копировально-множительное бюро
Некоммерческого акционерного общества
"Алматинский универсиет энергетики и связи"
050013, Алматы, Байтурсынова, 126