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

УДК 621.396

СИНТЕЗ СТРУКТУРЫ АБОНЕНТСКИХ ТЕЛЕКОММУНИКАЦИОННЫХ СЕТЕЙ

Г.А. Дмитриев, д.т.н.., зав. кафедрой; Б.И. Марголис, д.т.н.., профессор;

М.М. Музанна, аспирант

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

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

SYNTHESIS OF THE SUBSCRIBER TELECOMMUNICATION NETWORKS STRUCTURE Dmitriev G.A., Dr. Tech. Sc., Head of Chair; Margolis B.I., Dr. Tech. Sc., Professor;

Muzanna M.M., Postgraduate Student (Tver State Technical University, Quay Nikitin, 22, Tver, 170026, Russian Federation, kirsanich@mail.ru, borismargolis@yandex.ru, mohammed12@yandex.ru) Abstract. The need to separate the telecommunication network in terms of topological structure on the terminal (subscriber) and a core (backbone) network is described. The problem of synthesis of a subscriber network is stated. It represents minimizing the sum of the distances from the subscribers to the main switching nodes with limitations of the ability to connect each subscriber to a single site. A complete matrix of distances from the subscribers to the switching nodes is presented. It is shown that the problem of subscribers' optimal connection to sites switching refers to the class of linear integer programming problems with equality constraints. The equality constraints for each subscriber's connection conditions to one node switching is formulated. Based on the MatLab bintprog standard function, the authors have developed the program that allows synthesizing the topological structure of a user's network using a plurality of users, multiple nodes and switching matrix of distances between them. The paper shows the results of calculating the optimal connection of subscribers with the criterion of minimum sum of distances to the switching nodes for the telemedicine network of the Republic of Yemen. The article presents a method for calculating capacity of subscriber communication channels based on the supposed information flow for the received structure of subscriber network and its maximum load. Results of bandwidth calculation for the resulting structure of subscribers network of the Republic of Yemen that is received from synthesis.

Keywords: telecommunication network, subscriber network, backbone network, switching node, distance matrix, linear optimization, equality constraints, network topology, optimal connectivity, communication channel, the maximum load, bandwidth, structure synthesis.

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

С точки зрения топологической структуры, параметров и принципов обмена информацией в ТКС можно выделить две подсети: терминальную (абонентскую) и базовую (магистральную) сети [1]. Терминальная сеть включает терминалы, концентраторы и каналы связи, соединяющие терминалы с концентраторами; терминалы и концентраторы узлов коммутации, а также систему управления терминальной сетью. Базовая сеть включает узлы коммутации и каналы связи, их соединяющие, а также систему управления базовой сетью.

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

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

Пусть X={xk}, к = 1, г - множество абонентов; Y={yi}, г = 1,п - множество узлов коммутации; dki, к = 1, г, г = 1, п - матрица расстояний от ^го абонента до /'-го узла рассматриваемой сети, где г -количество абонентов, п - количество узлов. Основным ограничением рассматриваемой задачи синтеза структуры абонентской сети является то, что каждый абонент хкеХ может быть подключен только к одному узлу коммутации y/eY.

Введем переменную

(1, если абонент хк подсоединен к узлу у,,

=1„ _ _

10 в противном случае.

Тогда ограничения рассматриваемой задачи примут следующий вид:

I 2Ы= 1, к = 1, Г ,

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

Р = И2ы  ¿к, ^т^п-

к=1 ,=1

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

Для минимизации критерия (3) необходимо иметь всю матрицу расстояний от абонентов до

узлов dki, к = 1, г, г = 1, п, а обычно известны расстояния от малонаселенных районов - абонентов (удаленных пунктов) до районных центров - городов (узлов коммутации) dk/, к = 1, г , у = 1, п (г -

количество удаленных районов для ]-го узла) и между магистральными узлами связи dij,

г = 1, п, у = 1, п. Тогда полная матрица расстояний

dki, к = 1, г, г = 1, п , может быть найдена по выражению

dk/= dkj+dij,

к = 1, г, г = 1, п.

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

Задача оптимизации критерия (3) является задачей линейного целочисленного программирования с ограничениями типа равенств (2) [2]. Решение таких задач может эффективно осуществляться в среде Ма1ЬаЬ с помощью функции Ып1р1^. Для этого необходимо перейти от набора к = 1, г, г = 1, п, к одномерному массиву неизвестных j=1, г-п. То же самое относится к расстояниям: от матрицы \\dfoW переходим к одномерному массиву dlj, j=1, г-п.

Стандартное обращение к функции при отсутствии ограничений типа неравенств будет следующим: [г1, /га/]=Ып1р1^ ^1, [], [], Лед, Ъед), где/та/ - минимальное значение критерия Е в (3); 21 - булевый вектор решения, то есть его компоненты принимают значение 0 (абонент не подключен к узлу) или 1 (подключен).

Матрицы ограничений типа равенств Лед, Ъед формируются в соответствии с (2), а их размерности равныЛед[гхп], Ъед [гх1].

Для примера рассмотрим состав ТКС Республики Йемен. Сеть имеет две степени иерархии: абонентскую часть (г=72 абонента) и магистральную часть (п=18 узлов коммутации). Каждый из абонентов в зависимости от расстояния должен быть подсоединен к единственному ближайшему к нему узлу сети через каналы связи.

На рисунке 1 возможные магистральные каналы показаны штриховыми отрезками, абоненты обозначены маленькими светлыми, а узлы коммутации большими темными кружками. Аналогичные обозначения используются и на последующих рисунках. Таким образом, решение задачи синтеза структуры абонентской сети Республики Йемен в соответствии с критерием (3) может быть произведено на основе вышеизложенных методов целочисленного программирования в среде МаЙаЬ с использованием матриц расстояний dki в формуле (4). Результатом расчета является подключение каждого абонента к единственному узлу коммутации. Полученная структура абонентской сети Республики Йемен приведена на рисунке 2.

1=1

Аден

Рис. 1. Исходная структура ТКС Республики Йемен

Аден

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

Решение задачи синтеза структуры абонентской сети Республики Йемен в среде МайаЬ пред-

ставляет собой массив подключений абонентов к узлам к=1, ..., г, /=1, ..., п (см. табл. 1).

Таблица 1

Фрагмент матрицы подключений удаленных пунктов к узлам коммуникации

кд 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

3 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

4 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

5 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

6 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

7 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

8 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

9 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

10 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

11 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

12 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

13 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

14 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

15 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

16 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

17 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

18 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

19 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

20 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

21 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

22 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0

23 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0

24 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0

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

предполагаемые информационные потоки по данным каналам ф— к=1, ..., г, -=1, ..., п. Для полученной структуры абонентской сети Республики Йемен матрица информационных потоков ||ф— приведена в таблице 2. Пропускную способность

каналов ||Су| необходимо проектировать с учетом |ф|| и максимальной загруженности сети T [3]. В этом случае для получения запаса по нагрузке нужно использовать соотношение

ckj = сей [ф^/Т^, k = 1, Vj ,j = 1, п,

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

Таблица 2

Предполагаемые информационные потоки в абонентской сети

Результаты расчетов пропускной способности каналов ||Су| для 7,1=0,8 приведены на графе абонентской сети Республики Йемен, изображенном на рисунке 3. Таким образом, решена задача синтеза оптимальной структуры абонентской сети по критерию минимума суммы расстояний от абонентов до узлов коммутации с учетом того, что

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

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

Литература

1. Осипов Л.А., Яковлев С.А. Информационно-сетевые технологии. СПб: Изд-во ГУАП, 2008. 296 с.

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

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

References

1. Osipov L.A., Yakovlev S.A. Informatsionno-setevye tekh-nologii [Information and network technologies]. St. Petersburg, GUAP Publ., 2008, 296 p.

2. Panteleev A.V., Letova T.A. Metody optimizatsii vprime-rakh i zadachakh [Optimization methods in examples and exercises]. Moscow, Vyssh. shkola Publ., 2005, 544 p.

3. 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.

Щ

1 2,5 2,7 2,6 2,9 3 2,5

2 1,5 3,6 3 2 0,6

3 0,5 1,2 0,6 0,6 2

4 0,5 3 1,3 2 0,4

5 3 0,6 1,2

6 0,5 2,8 0,25 3,3 3,5

7 3,6 1,2 1,2 0,5

8 0,6 1,2 0,5 0,6 0,7

9 3,1 0,3 2,2 0,4 1,2

10 0,3 0,6 0,5

11 0,25 0,3 0,4 0,5 0,4

12 0,6 0,5 0,5 0,4

13 0,5 0,6 1,2 2,2

14 0,6 0,5 0,25 0,5

15 0,6 0,4 0,3 1,2

16 1,3 0,3 0,4 0,5 1,3