 |
Лекция. Сеть как объект анализа и синтеза
|
|
|
|
Цель: ознакомить обучающихся с постановками задач синтеза, их моделями и общими идеями решения.
Содержание: приведены множества факторов, которые характеризуют объект синтеза, общую модель решения задач структурного синтеза.
Факторы, характеризующие объект синтеза, общую модель решения задач структурного синтеза.
Все задачи, возникающие при построении и эксплуатации телекоммуникационных сетей, можно разделить на два класса: задачи синтеза и задачи анализа.
«Синтез» в переводе с греческого означает «соединение, составление».
Задача синтеза сети возникает как при построении новой сети, так и при реконструкции и развитии существующих сетей. Эта задача носит технико – экономический характер, так как чаще всего отыскивается решение, оптимальное по ряду экономических показателей, например, по минимуму капиталовложений.
При синтезе сети обычно считается заданным расположение пунктов сети. Конфигурация (топология) же линий связи может меняться при оптимизации экономических показателей. Это позволяет использовать затраты на линии связи в качестве целевого критерия оптимального синтеза сети. На конфигурацию линий могут быть наложены ограничения в виде исключения отдельных географических трасс при организации связи между пунктами, например, если они пересекают водные или горные преграды. К частным задачам синтеза можно отнести задачи выбора оптимальной топологии сети, выбор оптимального количества и места расположения узлов коммутации и т. д.
Задачи анализа актуальны для существующей (синтезированной сети). К ним относятся задачи нахождения оптимальных путей передачи информационных сообщений, определения совокупности путей заданной транзитности, оценки пропускной способности сети, вероятности установления соединения между пунктами и т. д.
|
|
|
В классе задач анализа рассматриваются также вопросы расчета характеристик и параметров как сети в целом, так и отдельных ее элементов. К таким характеристикам относят качество обслуживания на сети, параметры надежности и живучести.
Для того чтобы решить конкретную задачу синтеза или анализа телекоммуникационной сети, ее необходимо формализовать, т. е.записать в виде схемы: что дано, что необходимо определить и при каких ограничениях.
Формализацию можно выполнить в словесной форме (такая форма называется вербальной моделью задачи) либо в виде математической модели, описывающей задачу в терминах той или иной теории (например, теории графов, теории оптимальных решений и т. п.). Осуществление формализации требует не только понимания стоящей проблемы, но и выбора соответствующей модели самого объекта (сети связи).
Модельное (упрощенное) представление объекта синтеза или анализа позволяет выявить и отразить наиболее существенные, с точки зрения стоящей проблемы, элементы объекта и связи между ними, не отвлекаясь на детали.
Сеть как объект анализа и синтеза можно представить:
- технической базой (линии, станции, оконечные устройства);
- технологией обслуживания, т.е. системой операций, связанных с обслуживанием пользователей;
- алгоритмикой работы – процедуры выбора путей передачи сообщений, дисциплиной очередей и т.д.
Условимся, что вход сообщений в сеть и выход из сети осуществляется только в пунктах.
Два упорядоченных пункта называются корреспондирующей парой, если существует ненулевая потребность в связи между этими пунктами с целью доставки сообщений, входящих через первый пункт и выходящих через второй. В сети одновременной двусторонней связи направление передачи определяются вызовом.
|
|
|
Задача состоит в том, чтобы по заданному функциональному назначению объекта или закону его функционирования получить набор параметров: X = (
описывающих объект.
При этом под параметрами 
понимаются не только количественные величины, но и качественные понятия – технологические решения, технические элементы, математические алгоритмы и методы и т.д.
В качестве критерия оптимальности может быть принят любой количественный показатель, зависящий от 
, в общем случае 
.
Очевидно, что говорить об оптимальности решения можно только в том случае, когда можно построить некоторое множество (набор) технологически допустимых вариантов решений, каждому из которых соответствует определенное значение функции критерия.
Модель задачи можно записать так: определить набор 
,
удовлетворяющий условиям:
(6.1)
при ограничениях
(6.2)
. (6.3)
Модель задачи (6.1 – 6.3) включает в себя задачи поиска структуры объекта и расчета его параметров, которые соответственно называются задачами структурного и параметрического синтеза. Эти задачи относятся к области математики, называемой «исследование операций» или «математическое программирование», которые в зависимости от вида функций (6.1 – 6.2) и характера переменных (6.3) подразделяются на:
- линейное программирование;
- нелинейное программирование;
- динамическое программирование;
- дискретное программирование;
- целочисленное программирование.
Существует большое количество специальных методов решения, некоторые из них рассмотрим ниже.
1. Перебор возможных вариантов решения задачи. Это самый универсальный, но и самый трудоемкий метод. Алгоритм его представлен тремя шагами:
а) выбор или формирование вариантов сочетаний параметров;
б) подсчет целевой функции;
в) принятие решения о дальнейших действиях.
Этот метод очень трудоемок, к тому же не всегда можно говорить о том, что известно полное множество допустимых вариантов.
Задача упрощается, если множество вариантов конечно (по постановке задачи или в силу ограничений), тогда задача становится комбинаторной.
Поиск способов сокращения множества вариантов – задача актуальная, которая часто решается эвристическими методами. При этом наиболее часто встречаются следующие приемы.
|
|
|
2. Перебор вариантов, генерируемых из библиотеки элементов, использование библиотеки элементов вместо библиотеки готовых структур усложняет алгоритм генерации вариантов, но сокращает объем хранимой информации.
3. Последовательный синтез вариантов. Рассмотренные выше методы основаны на оценке законченной структуры. Последовательный синтез отличается от них постепенным наращиванием структуры с оценкой получаемых промежуточных решений. Наращивание осуществляется путем включения в предыдущую частичную структуру новых элементов. Такой подход в ряде случаев позволяет получить алгоритмы синтеза, эффективные по затратам машинного времени. Однако необходимым условием применения этого метода является возможность оценки частичных структур, что не всегда допустимо.
4. Выделение варианта из обобщенной структуры. В этом методе синтез осуществляется постепенным исключением элементов из некоторой обобщенной избыточной структуры, которая должна быть получена предварительно путем анализа и обобщения инженерного опыта. Применение этого метода целесообразно в тех случаях, когда сруктура проектируемых объектов содержит одинаковые фрагменты.
5. Эвристические приемы – это используемые человеком неформальные процедуры, основанные на его знаниях, интуиции, опыте. Преимущества этого подхода представлены:
- уменьшением числа шагов поиска;
- постановкой более скромных задач (не оптимальное, а любое приемлемое решение);
- сокращением времени на этапе оценки варианта.
Недостатки метода – получение не оптимального, а некоторого инженерного решения, причем часто нет даже оценки близости его к оптимальному.
6) Сведения задачи структурного синтеза к задачам дискретного математического программирования.
Для того чтобы задачу структурного синтеза представить моделью дискретного программирования неоходимо:
- всем существенным элементам, характеризующим проектируемую структуру, поставить в соответствие некоторые величины и сгруппировать их в вектор 
– 
;
|
|
|
- установить количесвтенный критерий и выразить его в виде функции 
) и в виде ограничений, 
.
Большинство признаков (элементов) структуры не имеет количественных характеристик – это тип оборудование, тип канала и т.д.
Эти признаки можно сделать количественными, присвоив каждому определенный номер – код. Тогда любому варианту структуры можно поставить в соответствие значение функции критерия. Это искусственный прием, который позволяет надеяться на успешное решение задачи далеко не всегда.
Однако существуют определенные типы задач синтеза, которые успешно решаются, это, прежде всего, так называемые транспортные задачи.
|
|
|
