И методы оптимального синтеза связывающих сетей

Математические модели

Лекция 7

Общее понятие о задачах синтеза и анализа

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

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

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

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

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

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

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

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

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

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

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

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

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

Однако точные алгоритмы, как правило, довольно трудоемки с вычислительной точки зрения. Поэтому на практике часто используют более простые алгоритмы, обеспечивающие быстрое получение решения с приемлемой для практики точностью. Такие алгоритмы строятся с использованием рациональных, с точки зрения логики человека, правил выполнения вычислений. Эти правила называются эвристикамии, как показывает практика, позволяют получить решение, близкое к оптимальному. Например, задача определения замкнутого контура наименьшей длины, обеспечивающего обход всех пунктов сети, может быть решена путем полного перебора всех возможных контуров с выбором среди них контура наименьшей длины, т. е. точным алгоритмом. Известно, что для сети, содержащей n пунктов, количество возможных контуров составляет порядка n!, получение которых для сети, размером n>30, представляет значительные трудности. Однако использование эвристики: "на каждом шаге движемся только к ближайшему пункту" обеспечивает получение приемлемого решения за время, необходимое для построения всего лишь одного контура.

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