На правах рекламы:
ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Авторитетность издания

ВАК - К1
RSCI, ядро РИНЦ

Добавить в закладки

Следующий номер на сайте

2
Ожидается:
16 Июня 2024

Синтез магистральных телекоммуникационных сетей

Synthesis gas telemedicine networks
Статья опубликована в выпуске журнала № 1 за 2014 год. [ на стр. 162-168 ]
Аннотация:Рассмотрена графовая модель структурно-функционального синтеза магистральной телекоммуникационной сети. Сформулирована задача синтеза структуры магистральной сети, заключающаяся в минимизации расстояний при прохождении информации до региональных узлов коммутации. По матрице расстояний между магистральными узлами с помощью функции graphshortestpath в среде MatLab получены оптимальные маршруты прохождения информации до региональных узлов магистральной сети. Сформулирована задача параметрического синтеза магистральной сети, состоящая в определении пропускной способности магистральных каналов связи по синтезированной топологической структуре и значениям входных потоков от абонентов. Показано, что задача параметрического синтеза магистральной сети относится к классу задач нелинейной оптимизации с ограничениями типа неравенств и равенств. Сформулированы ограничения типа неравенств для пропускной способности каналов и типа равенств для условий сохранения потоков в узлах сети. На основе стандартной функции fmincon в среде MatLab разработана программа, позволяющая найти оптимальные информационные потоки в магистральных каналах связи по критериям средней задержки сообщений и максимальной загруженности сети. Предложена методика расчета пропускной способности по максимальным информационным потокам, протекающим по магистральным каналам к региональным узлам коммутации. Приведены результаты расчета оптимальной пропускной способности каналов для магистральной теле-коммуникационной сети Республики Йемен. Показан пример прохождения информации для конкретных магистрального узла-источника и регионального узла-приемника.
Abstract:The article considers the graph model of structural-functional synthesis of backbone telecommunication net-work. It also describes the problem of the backbone structure synthesis. This problem is in minimizing the distances when passing information to the regional switching nodes. The optimal routes for information passing to the regional nodes of backbone network are obtained using a matrix of distances between backbone nodes and the graphshortestpath function in MatLab. The problem of parametric synthesis of backbone network is considered. It consists in determining the capacities of the main communication channels using synthetic topological structure and values of the input streams from subscribers. It is shown that the problem of parametric synthesis of backbone network belongs to a class of nonlinear optimization problems with constraints like inequality and equations. Inequality constraints are formulated for capacity of channels and the type of conservation equations for saving flows in the network nodes. The article presents a developed program that allows finding the optimal information flows in the backbone communication channels using criteria of average messages delay and maxi-mum network load. The program is developed on the basis of the standard fmincon function in MatLab. A methodology for calculating capacity for maximum information flows in the main channels to regional switching nodes. There are the results of calculation of optimal channels capacities for backbone telecommunication network backbone of the Republic of Yemen. An example of passing information to the particular backbone source node and the regional destination node is shown.
Авторы: Марголис Б.И. (borismargolis@yandex.ru) - Тверской государственный технический университет (зав. кафедрой), г. Тверь, Россия, доктор технических наук, Музанна М.М. (mohamed1984a@yahoo.com) - Тверской государственный технический университет (аспирант ), Тверь, Россия
Ключевые слова: ограничения типа неравенств и равенств, телекоммуникационная сеть, магистральная сеть, синтез структуры, узел коммутации, матрица расстояний, параметрический синтез, топология сети, информационный поток, пропускная способность, нелинейная оптимизация, к
Keywords: inequality constraints and equations, telecommunication network, backbone network, structure synthesis, switching node, distance matrix, parametrical synthesis, topology, information stream, capacity, nonlinear optimization,
Количество просмотров: 10123
Версия для печати
Выпуск в формате PDF (7.83Мб)
Скачать обложку в формате PDF (1.01Мб)

Размер шрифта:       Шрифт:

Задача синтеза топологической структуры магистральных сетей (МС) является одной из основных при проектировании магистральных телекоммуникационных сетей (ТКС) и состоит в выборе оптимальной схемы соединения узлов коммутации и концентрации, а также пропускной способности линий и оптимальных маршрутов передачи информации. Выбор топологической структуры может осуществляться по стоимостному критерию минимума суммарной годовой аренды каналов связи при наличии ограничений на время задержки и надежность передачи информации [1]. При разработке модели структурно-функ­ционального синтеза МС удобно использовать методы решения оптимизационных задач с помощью теории графов или сетей. Граф состоит из конечного множества вершин и множества ребер, соединяющих вершины (элементы системы). Для магистральных ТКС в качестве вершин графа выступают узлы коммутации, а ребрами являются соединяющие их магистральные каналы связи.

При формализованном описании элементов и структуры МС ее можно представить в виде неориентированного графа G=(Y, S), где Y={yi},  – множество узлов коммутации; S={sk},  – множество каналов связи между узлами; n – количество узлов; M – количество каналов. Вершины графа G=(Y, S) соответствуют узлам коммутации сети, ребра − каналам связи между узлами коммутации, а топология графа − топологической структуре МС. Выбор вида графа определен дуплексным режимом передачи по каналам связи между узлами коммутации. Тогда любая пара соседних вершин графа yi и yj (yiÎY, yjÎY, ) характеризуется расстоянием между ними dij, а D={dij} – это матрица расстояний графа G.

Рассмотрим общий граф МС Республики Йемен (рис. 1), на котором показаны места расположения узлов коммутации. Задача заключается в оптимальном подключении узлов коммутации для того, чтобы расстояния (пути прохождения информации) от любого узла коммутации до региональных узлов коммутации (17 и 18) были кратчайшими, то есть необходимо решить задачу топологического синтеза с выбором оптимальной схемы соединения узлов коммутации по расстоянию. Возможные магистральные каналы на рисунке 1 показаны штриховыми отрезками, числа над ними характеризуют расстояния между ма- гистральными узлами, узлы коммутации изображены темными, а региональные узлы коммутации – крупными темными кружками. Аналогичные обозначения применяются и на последующих рисунках. С учетом приведенных рассуждений и схемы МС матрица связности для рассматриваемой задачи будет состоять из узлов-источников i, узлов-адресатов j и матрицы расстояний между ними D={dij}.

Граф МС как совокупность узлов коммутации и соединяющих их каналов связи в среде Matlab можно описать с помощью функции sparse. После этого задача синтеза МС Республики Йемен в соответствии с критерием расстояния может быть решена на основе методов теории графов с использованием функции graphshortestpath. С помощью этой функции можно находить кратчайшие пути по матрице расстояний dij между любой парой вершин, а также кратчайший маршрут между заданной парой вершин. Полученные оптимальные маршруты прохождения информации от любого узла коммутации к региональным узлам коммутации 17 (Сана) и 18 (Аден) приведены на рисунке 2.

Подпись:  Рис. 1. Общая схема магистральной сети Республики ЙеменПри решении задачи с помощью graphshor­testpath получаем оптимальные маршруты прохождения информации от каждого узла коммутации до каждого регионального узла коммутации. В программе необходимо исключить повторяющиеся маршруты и учесть, что граф является неориентированным.

Подпись:  
Рис. 2. Кратчайшие пути прохождения информации 
в МС от узлов коммуникации к региональнвм узлам 
коммуникации
Результат синтеза структуры МС Республики Йемен с учетом общей схемы МС приведен на рисунке 3. На схему сплошными линиями нанесены полученные кратчайшие маршруты прохождения информации от узлов коммутации к региональным узлам коммутации, а пунктирными – исключенные линии связи. Полученная оптимальная топология МС Республики Йемен позволяет перейти к решению задачи параметрического синтеза МС, важнейшей частью которого является определение пропускной способности магистральных каналов связи.

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

С учетом возможности подключения к узлам коммутации нескольких абонентов был произведен расчет суммарных информационных потоков gj, j=1, …, n, поступающих в МС. Для полученной структуры МС (рис. 3) задача оптимального прохождения информации от абонентов к региональПодпись:  Рис. 3. Синтезированная структура МС Республики Йемен Рис. 4. Структура МС с учетом поступающих информационных потоковным узлам коммутации может быть представлена в виде, показанном на рисунке 4. Номера магистральных каналов приведены на рисунке в круглых скобках, а числа над стрелками показывают информационные потоки от абонентов к каждому узлу коммуникации.

Для решения поставленной задачи нахождения оптимальной пропускной способности магистральных каналов будем использовать рассмотренную в работе [2] модель МС с альтернативной маршрутизацией сообщений. Для МС, состоящей из n узлов коммутации и M каналов, с учетом возможности разделения каждого канала на m линий связи обозначим информационные потоки по каналам в виде jik, . Оптимизацию функционирования сети можно производить по критериям средней задержки сообщения T и максимальной загруженности T1 сети.

Сформулируем задачу оптимальной маршрутизации. По заданной топологической структуре информационной сети, значению входного потока g и матрице пропускной способности C1ik,  , необходимо найти оптимальные значения потоков ||jik||. Минимизацию можно производить по критериям T и T1:

,                              (1)

,       (2)

при выполнении следующих ограничений:

.                          (3)

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

                       (4)

где E – множество каналов связи; i – узел-источ­ник; j – узел-адресат; l=i и l=j характеризуют соответственно узел-вход и узел-выход.

Изображенная на рисунке 4 МС Республики Йемен состоит из n=18 узлов и M=26 каналов связи. При условии формирования поступающей нагрузки в виде бесприоритетного трафика входные потоки от абонентов gj, , должны быть переданы через соответствующие узлы к региональным узлам коммутации. При этом необходимо минимизировать критерий (2) при выполнении ограничений (3) и (4). Для упрощения расчетов разделение по линиям связи не производится. В этом случае m=1, а рассмотренные матрицы потоков и пропускной способности являются одномерными массивами.

Задача оптимизации критерия (2) относится к классу задач нелинейной оптимизации функции нескольких переменных с ограничениями типа неравенств (3) и равенств (4) [3], и ее решение может быть получено в среде MatLab с помощью функции fmincon. При этом ограничения типа неравенств удобно задавать с помощью нижней и верхней границ lb, ub. При синтезе значений пропускной способности магистральных каналов для оптимальной передачи информационных сообщений по МС от узлов коммутации к региональным узлам коммутации для всех имеющихся каналов нижней границей является lb=0, а в качестве верхней границы можно взять максимальное из информационных потоков от абонентов значение ub=max{gi}, .

Для приведенной на рисунке 4 МС Республики Йемен условия сохранения потоков с учетом произведенной нумерации будут выглядеть следующим образом:

(5)

Равенства (5) описывают условия сохранения потоков в узлах коммутации, причем Fi=g для узла-входа; Fi=–g для узла-выхода; Fi=0, , для промежуточных узлов. Условия сохранения потоков в узлах маршрутизации (5) являются ограничениями типа равенств и при решении оптимизационной задачи в Matlab представляют матрицы Aeq, beq. Матрица Aeq постоянна и не зависит от номеров узла-входа и узла-выхода, так как характеризует проходящие через узел информационные потоки. Матрица beq зависит от номеров узла-входа и узла-выхода, соответствует Fi в уравнениях (5), и ее элементы равны gi для узла-входа; –gi для узла-выхода и 0 для промежуточных узлов.

Для решения задачи синтеза МС разработана программа direct.m, позволяющая найти оптимальные информационные потоки в магистральных каналах связи по критериям средней задержки сообщения T и максимальной загруженности сети T1. Начальное приближение разделения потоков может быть определено с помощью функции linprog при вышеуказанных граничных условиях. При передаче информации в МС от узлов коммутации к региональным узлам коммутации необходимо многократно решать оптимизационную задачу для узлов-входов узла коммутации  и узлов-выходов региональных узлов коммутации , где n1=2 – число региональных узлов коммутации (суперцентров) по критерию максимальной загруженности сети T1. При этом в качестве пропускной способности всех магистральных каналов берется max{gi}, .

Подпись:  Рис. 5. Топология и спроектированные емкости МС Республики Йемен Рис. 6. Прохождение информации от 1-го узла коммуникации (Тайз) к 17-му региональному узлу коммуникации (Сана)Для нахождения проектируемой пропускной способности МС используются полученные оптимальные информационные потоки jijk,  от каждого j-го узла коммутации к каждому k-му региональному узлу коммутации. В качестве оптимальных значений пропускной способности магистральных каналов нужно взять максимальные из полученных информационных потоков C1i=max{jijk},  Проверку спроектированных значений пропускной способности каналов МС можно произвести и по критерию средней задержки сообщения T, находя минимальное время передачи информации. Значения спроектированной по критерию средней задержки пропускной способности каналов C1i,  для МС Республики Йемен с учетом топологии сети приведены на рисунке 5 над номерами каналов (без скобок). Пример передачи информации при прохождении сообщения от 1-го узла коммутации (Тайз) к 17-му региональному узлу коммутации (Сана) приведен на рисунке 6.

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

Литература

1.     Вишневский В.М. Теоретические основы проектирования компьютерных сетей. М.: Техносфера, 2003. 506 с.

2.     Дмитриев Г.А., Марголис Б.И., Музанна М.М. Решение задачи оптимальной маршрутизации по критерию загруженности сети // Программные продукты и системы. 2013. № 4. С. 173–176.

3.     Пантелеев А.В., Летова Т.А. Методы оптимизации в примерах и задачах. М.: Высш. школа, 2005. 544 с.

References

1.     Vishnevskiy V.M. Teoreticheskie osnovy proyektirovaniya kompyuternykh setey [Theoretical basics of computer network design]. Moscow, Tekhnosfera Publ., 2003, 506 p.

2.     Dmitriyev G.A., Margolis B.I., Muzanna M.M. Optimal routing using the network congestion criterion. Programmnye pro­dukty i sistemy [Software & Systems]. 2013, no. 4, pp. 173–176.

3.     Panteleev A.V., Letova T.A. Metody optimizatsii v prime­rakh i zadachakh [Optimization methods in examples and exercises]. Moscow, Vyssh. shkola Publ., 2005, 544 p.


Постоянный адрес статьи:
http://swsys.ru/index.php?page=article&id=3778&lang=&like=1
Версия для печати
Выпуск в формате PDF (7.83Мб)
Скачать обложку в формате PDF (1.01Мб)
Статья опубликована в выпуске журнала № 1 за 2014 год. [ на стр. 162-168 ]

Возможно, Вас заинтересуют следующие статьи схожих тематик: