Оптимизационные задачи проектирования

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

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

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

Как отмечалось в работе [1], создание такой методике опирается на решение следующих задач:

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

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

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

1. Основные понятия

Определение первичной сети электросвязи.

Рекомендуемые материалы

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

Определение вторичной сети электросвязи.

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

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

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

2. Сети электросвязи и модели структур сетей

Описанию сетей связи и их элементов посвящен ряд работ [4,8,10], поэтому здесь зафиксируем те особенности, которые возникают в связи с формальным описанием структур первичной и вторичной сети как единого объекта исследования.

Морфологическое описание сетей электросвязи.

1.      Элементы сетей.

-         пункты связи: сетевой узел, сетевая станция, узел связи, оконечная станция (пункт), узел коммутации и т.п.;

-         линии сетей связи: линия передачи, соединительная линия, канал электросвязи , канал вторичной сети и т.п.

2.      Структуры сетей.

-         структура первичной сети – конфигурация сетки линий передачи или соединительных линий;

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

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

3.      Технология обслуживания.

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

4.      Внешние воздействия.

-         поток заявок между корреспондирующими парами;

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

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

-         поток восстановлений элементов - восстановление отказавших элементов и создание новых;

-         передвижение элементов, то есть перемещение станций и узлов вслед за абонентами.

5.      Критерий эффективности.

В качестве критериев эффективности рассматривается экономические критерии, критерии качества и надежности передачи, критерии живучести.

6.      Требования и ограничения.

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

3 Формальное описание структур сетей электросвязи

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

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

1.      Первичные сети.

Структура первичной сети может быть задана графом G=(V,E), где

V=(v1 , …, vn) – множество вершин, а E= (e1 ,…, ek) - множество ветвей. Каждому сетевому узлу первичной сети будет соответствовать вершина графа G, а каждой соединительной линии – ветвь графа G. Характеристики элементов первичной сети в этом случае соответствует параметрам (весам) соответствующих вершин и ветвей графа G.

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

2.      Вторичные сети.

Структура вторичной сети, если не рассматривать ее реализацию на первичной сети, также моделируется графом  L = (W,R), где W = (w1 ,…,wm) – множество вершин, а R=(r1,…,rp) – множество ребер графа L.

Каждому узлу связи вторичной сети (коммутируемому или некоммутируемому), соответствует вершина графа L, а каждому каналу (или пучку каналов) вторичной сети соответствует ребро (мультиребро) графа L. Характеристики элементов вторичной сети при этом соответствует параметрам (весам) вершин и ребер графа L.

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

3.      Сеть электросвязи

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

Узлы связи вторичной сетей обычно не относится к первичным сетям.

Граф G =(V,E) соответствует первичной сети электросвязи PS =(V,E), а граф L=(W,R) – вторичной сети WS = (W,R). В соответствии с определением простой гиперсети, связь WS и PS определяется гиперграфом FS = (E,R), где ветвь eE инцидентна  ребру rR тогда и только тогда, когда соответствующий r канал вторичной сети реализован по линии передачи первичной сети соответствующей ветви e. Таким образом, структура  сети электросвязи задается гиперсетью S = (PS,WS;FS).

4.      Основные формальные модели структур.

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

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

4. Сети электросвязи и их формальные (теоретические) модели.

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

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

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

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

Классификация теоретических моделей сетей связи.

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

1. Двухполюсная – сеть независимой связи, осуществляющая соединение одной   корреспондирующей пары.

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

2. Стохастическая -  сеть из ненадежных элементов.

    Детерминированная – сеть из абсолютно надежных элементов.

3. Неориентированная – сеть, состоящая из дуплексных каналов.

    Ориентированная – сеть, состоящая из симплексных каналов.

4. Избыточная – сеть, содержащая резервные не включенные элементы.

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

5. Подвижная – сеть с подвижными абонентами (оконечными пунктами и узлами связи).

Стационарная – сеть с зафиксированными пунктами связи.

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

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

7. Кроссируемая – сеть, в узлах которой может осуществляться кроссировка каналов, трактов и т.д.

    Сеть без кроссировки – кроссировка в узлах отсутствует.

8. Потоковая – сеть, в которой учитывается потоки сообщений.

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

9. Коммутируемая – сеть, в узлах которой осуществляется оперативная коммутация каналов или сообщений.

    Некоммутируемая – сеть, в которой отсутствует узлы коммутации.

10. Сеть с коммутацией каналов.

      Сеть с коммутацией пакетов и сообщений.

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

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

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

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

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

5 Критерии эффективности сетей связи.

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

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

Рассмотрим перечисленные типы критериев более подробно.

1. Критерии качества и надежности.

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

Приведенные ниже критерии качества и надежности функционирования в основном взяты из работы [4]:

1.      Существование заданного числа кондиционных путей, то есть путей, в которых число транзитов ограничено или ограничена длина пути.

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

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

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

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

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

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

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

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

10.  Вероятность своевременной доставки сообщений входящего потока сообщений при заданной норме времени доставки.

11.   Вероятность ожидания для любого поступившего вызова.

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

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

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

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

2. Экономические критерии.

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

Приведем наиболее употребительные экономические критерии :

1.      Стоимость линии связи первичной сети

2.      Число каналов в линии связи.

3.      Суммарная длина каналов в одной линии связи.

4.      Длина линии связи.

5.       Арендная плата за канал вторичной сети.

3.  Критерий живучести

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

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

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

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

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

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

6. Основные задачи исследования и проектирования структур сетей связи

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

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

Классификация задач проектирования сетей связи.  

А) Основные классы сетей связи:

1.    Первичные сети.

2.    Вторичные сети.

3.    Сети электросвязи.

Б) Типы сетей связи (включая первичные и вторичные сети):

1.      Магистральные сети.

2.      Зоновые. Состоят из внутризоновых и местных сетей.

3.      Внутризоновые сети.

4.      Городские сети.

5.      Сельские сети.

6.      Абонентские сети.

7.      Ведомственные сети.

В) Типы вторичных сетей связи:

1.      Телефонные.

2.      Передачи данных.

3.      Телеграфные.

4.      Радиовещание.

5.      Телевидение.

6.     Другие возможные типы.

Г) Виды проектной деятельности:

1.      Анализ сети связи.

2.      Перспективное проектирование сетей связи.

3.      Планирование развития сети связи.

4.      Текущее проектирование сетей связи.

5.     Построение вторичных сетей связи на базе первичной.

Д) Требования и ограничения в задачах проектирования.

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

1.      Длина канала заданного физического типа не превосходит некоторой наперед заданной величины;

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

3.      Конфигурация структуры сети имеет определенный вид;

4.      Связность сети не менее заданного числа;

5.      Семейство ограничений, соответствующих критериям качества и надёжности, а   также экономическим критериям;

6.      Семейство ограничений относительно живучести сети;

7.      Ограничения на характер внешних воздействий;

8.      Некоторая сеть связи уже существует;

9.      Другие ограничения.

Е) Методические приемы оптимизации целевой функции экономической эффективности:

1.      Определение адекватности матрицы потоков;

2.      Оптимальное размещение пунктов связи;

3.      Объединение нагрузки во вторичных сетях;

4.      Объединение соединительных линий в одну линию передачи;

5.      Объединение трасс реализации линий передачи;

6.      Оптимальное распределение каналов вторичных сетей в первичной сети;

7.      Реализация линий передачи по кратчайшим маршрутам;

8. другие способы снижения затрат, которые учитывают специфику конкретной задачи проектирования.

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

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

Анализ сетей электросвязи.

А) Анализ метрических характеристик:

1.       Вычисление кратчайшего расстояния между заданными вершинам.

2.      Вычисление наименьшего ранга между заданными вершинами.

3.      Проверка наличия кондиционного между парой вершин.

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

Б) Анализ   пропускной способности сети:

1.      Поиск максимального потока между  парой вершин.

2.      Поиск максимального потока минимальной стоимости.

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

В) Анализ показателей живучести:

1.      Вычисление вершинной или реберной связности графа и множества элементов из минимального разреза.

2.      Вычисление характеристик связности гиперсети   и множества элементов минимального разреза.

3.      Вычисление специальных характеристик связности (устойчивость, к-степень, тотальная и компактная связность).

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

Г) Анализ экономических показателей:

1.      Вычисление капитальных затрат.

2.      Вычисление приведенных затрат.

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

Д) Анализ показателей качества и надёжности:

1.      Вычисление чувствительности сети связи и управлению.

2.      Вычисление комплексных показателей живучести.

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

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

2. Синтез сети связи.

А) Поиск узловой основы:

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

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

3.      Определить границы станционных районов (для абонентских сетей).

4.      Найти границы узловых районов (подсетей  заданного уровня  иерархии).

Б) Вычисление нагрузки и потоков:

1.      Определить матрицу нагрузки между оконечными пунктами.

2.      Определить матрицу потоков между оконечными пунктами.

3.      Определить число каналов по каждому направлению вторичной сети.

4.      Определить емкость линий передачи для первичной сети.

В) Поиск структуры сети:

1.  Найти максимальную (или с заданным числом линий и узлов) сетку линий для   реализации в ней сети.

2.  Найти оптимальную структуру сети.

3.  Найти оптимальное вложение одной сети в другую.

Г) Выбор эффективного оборудования:

1.      Определить номенклатуру пунктов связи.

2.      Определить номенклатуру линий передачи.

Д) Распределение потоков и каналов:

1.      Распределить потоки по пучкам каналов вторичной сети.

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

3.      Распределить соединительные линии по максимальной сетке линий.

Е) Поиск множества элементов:

1.      Найти линии связи, предназначенные для удаления.

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

Если Вам понравилась эта лекция, то понравится и эта - 58 Возникновение Крымского ханства.

3.      Найти добавочное число пунктов связи и подсоединить к сети.

Ж) Выбор алгоритмов управления:

1.      Разработка алгоритм управления коммутацией (соединением).

2.      Разработать алгоритм управления кроссировкой (структурой).

3.      Разработать алгоритм управления нагрузкой (потоками).

4.      Разработать алгоритм управления ресурсами.