Software & Systems

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

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

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

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

Пусть X={xk},  – множество абонентов; Y={yi},  – множество узлов коммутации; dki,  – матрица расстояний от k-го абонента до i-го узла рассматриваемой сети, где r – количество абонентов, n – количество узлов. Основным ограничением рассматриваемой задачи синтеза структуры абонентской сети является то, что каждый абонент xkÎX может быть подключен только к одному узлу коммутации yiÎY.

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

(1)

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

,                                                   (2)

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

                                     (3)

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

Для минимизации критерия (3) необходимо иметь всю матрицу расстояний от абонентов до узлов dki, , а обычно известны расстояния от малонаселенных районов – абонентов (удаленных пунктов) до районных центров – городов (узлов коммутации) dki, (rj – количество удаленных районов для j-го узла) и между магистральными узлами связи dij, . Тогда полная матрица расстояний dki, , может быть найдена по выражению

dki= dkj+dij,

.                                                     (4)

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

Задача оптимизации критерия (3) является задачей линейного целочисленного программирования с ограничениями типа равенств (2) [2]. Решение таких задач может эффективно осуществляться в среде MatLab с помощью функции bintprog. Для этого необходимо перейти от набора zki, , к одномерному массиву неизвестных z1j, j=1, r×n. То же самое относится к расстояниям: от матрицы ||dki|| переходим к одномерному массиву d1j,  j=1, r×n.

Стандартное обращение к функции при отсутствии ограничений типа неравенств будет следующим: [z1, fval]=bintprog (d1, [], [], Aeq, beq), где fval – минимальное значение критерия F в (3); z1 – булевый вектор решения, то есть его компоненты принимают значение 0 (абонент не подключен к узлу) или 1 (подключен).

Матрицы ограничений типа равенств Aeq, beq формируются в соответствии с (2), а их размерности равны Aeq[r´n], beq [r´1].

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

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

Решение задачи синтеза структуры абонентской сети Республики Йемен в среде Matlab представляет собой массив подключений абонентов к узлам zki, k=1, …, r, i=1, …, n (см. табл. 1).

После того как получена структура абонентской сети, обеспечивающая оптимальное подключение абонентов к магистральным узлам сети, необходимо определить пропускную способность абонентских каналов связи. Для этого нужно знать предполагаемые информационные потоки по данным каналам jkj, k=1, …, r, j=1, …, n. Для полученной структуры абонентской сети Республики Йемен матрица информационных потоков ||jkj|| приведена в таблице 2. Пропускную способность каналов ||Ckj|| необходимо проектировать с учетом ||jkj|| и максимальной загруженности сети T1 [3]. В этом случае для получения запаса по нагрузке нужно использовать соотношение

,                 (5)

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

Таблица 2

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

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

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

Литература

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

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 v prime­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.