Методология анализа и синтеза реконфигурируемых топологий мобильных сетей связи
Рассмотрена методология реконфигурации топологии сетей WATM, исходя из надежности их функционирования. Предложен пример реализации методологии системного анализа и синтеза процессов реконфигурации топологии сети. Розглянуто методологію реконфігурації топології мереж WATM, виходячи з надійності їхньо...
Saved in:
| Published in: | Математичні машини і системи |
|---|---|
| Date: | 2006 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем математичних машин і систем НАН України
2006
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/83968 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Методология анализа и синтеза реконфигурируемых топологий мобильных сетей связи / И.Э. Горбунов // Мат. машини і системи. — 2006. — № 2. — С. 48-59. — Бібліогр.: 21 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859652997403901952 |
|---|---|
| author | Горбунов, И.Э. |
| author_facet | Горбунов, И.Э. |
| citation_txt | Методология анализа и синтеза реконфигурируемых топологий мобильных сетей связи / И.Э. Горбунов // Мат. машини і системи. — 2006. — № 2. — С. 48-59. — Бібліогр.: 21 назв. — рос. |
| collection | DSpace DC |
| container_title | Математичні машини і системи |
| description | Рассмотрена методология реконфигурации топологии сетей WATM, исходя из надежности их функционирования. Предложен пример реализации методологии системного анализа и синтеза процессов реконфигурации топологии сети.
Розглянуто методологію реконфігурації топології мереж WATM, виходячи з надійності їхнього функціонування. Запропоновано приклад реалізації методології системного аналізу і синтезу процесів реконфігурації топології мережі.
The methodology of reconfigurable topology of WATM networks is considered, proceeding from reliability of their functioning. The example of implementation of methodology of the system analysis and synthesis of network topology reconfiguration processes is offered.
|
| first_indexed | 2025-12-07T13:36:15Z |
| format | Article |
| fulltext |
ISSN 1028-9763. Математичні машини і системи, 2006, № 2 48
УДК 681.513
И.Э. ГОРБУНОВ
МЕТОДОЛОГИЯ АНАЛИЗА И СИНТЕЗА РЕКОНФИГУРИРУЕМЫХ ТОПОЛОГИЙ
МОБИЛЬНЫХ СЕТЕЙ СВЯЗИ
Abstract: The methodology of reconfigurable topology of WATM networks is considered, proceeding from reliability
of their functioning. The example of implementation of methodology of the system analysis and synthesis of network
topology reconfiguration processes is offered.
Key words: ATM, WATM, networks, mobile networks, topology reconfiguration, reliability.
Анотація: Розглянуто методологію реконфігурації топології мереж WATM, виходячи з надійності їхнього
функціонування. Запропоновано приклад реалізації методології системного аналізу і синтезу процесів
реконфігурації топології мережі.
Ключеві слова: ATM, WATM, мережі, мобільні мережі, реконфігурація топології, надійність.
Аннотация: Рассмотрена методология реконфигурации топологии сетей WATM, исходя из надежности
их функционирования. Предложен пример реализации методологии системного анализа и синтеза
процессов реконфигурации топологии сети.
Ключевые слова: ATM, WATM, сети, мобильные сети, реконфигурация топологии, надежность.
1. Введение
Сегодня начался процесс перемещения от мира многих отдельных локальных сетей передачи
мультимедийного трафика (ММТ) (голоса, видеоданных и телевидения) в мир интегральной
передачи ММТ с адаптивно регулируемой топологией широкополосных беспроводных
транспортных платформ (ШБТП) интеллектуальных сетей (ИС) с использованием технологии
беспроводного асинхронного метода передачи (WATM), что обеспечивает, в свою очередь,
создание единой широкополосной первичной сети (ШПС) страны [1, 2].
Введение технологии WATM с интеллектуальными механизмами адаптивной коррекции
протоколов передачи и топологии сети, что должно обеспечивать и контроль, и, главное,
интегральную управляемость с установлением необходимой связности между базовыми узлами
сети (так называемыми базовыми интеллектуальными узлами (БИУ) ) [3, 4].
Характерной особенностью широкополосной транспортной платформы (ШТП) ИС на базе
WATM является скоротечная динамика процессов загрузки и реконфигурации сети (неравномерный
ММТ от мобильных абонентов), с одной стороны, и поддержание заданной надежности
функционирования, с другой [5–8]. При этом первичной является проблема поддержание заданного
уровня надежности функционирования сети [9].
Таким образом, исследования, связанные с введением БИУ, адаптивно реконфигурируемых
такую топологию сети WATM, которая всегда будет обеспечивать заданную надежность ее
функционирования, в настоящее время актуальны.
Целью работы является формирование специальных алгоритмов анализа и синтеза таких
вариантов реконфигурируемой топологии сети, которые обеспечивали бы поддержку и передачу
информации с заданным уровнем надежности функционирования при минимальных затратах
средств.
2. Анализ процессов функционирования беспроводных сетей с обоснованием требований к
надежности их функционирования
До настоящего времени для технологии WATM не разработан весь комплекс необходимых стан-
дартов, которые определяли бы все предлагаемые к рассмотрению аспекты построения и эксплуа-
ISSN 1028-9763. Математичні машини і системи, 2006, № 2 49
тации сети. Спецификации требований в области WATM пока состоят из множества различных
предложений (например, введение службы с поддержкой мобильности (AMES) [8, 10, 11, 12]).
Поэтому главными первичными задачами, направленными на совершенствование технологии
WATM, которая обеспечит необходимую пользователям функциональность, являются следующие:
– необходимость прямой интеграции мобильных беспроводных терминалов в сеть ATM. Эта
интеграция является основным требованием для поддержания интегрированных служб передачи
различных типов потоков информации, подобных поддерживаемым технологией ATM в оптических
сетях;
– необходимость интеграции сетей ATM, которые хорошо масштабируются от локальных до
глобальных, а мобильность нужна как в локальных, так и глобальных сетях. Таким образом,
требуется стратегия расширения ATM на беспроводный доступ в локальной и глобальной
конфигурациях;
– необходимость обеспечения высокого качества обслуживания (quality of service – ОоS).
Технология WATM должна реализовать адекватную ATM поддержку потоков мультимедийного
трафика (ММТ). Многие другие беспроводные технологии (например, сети IEEE 802.11) предлагают
службы передачи только без обязательств поддержки качества передачи. Эти службы не
обеспечивают такое количество параметров QoS, которое дают сети ATM;
– необходимость слияния систем телекоммуникационных услуг с технологией
беспроводной мобильной связи WATM. В таком контексте одной из целей является прямая
интеграция мобильности в широкополосную цифровую сеть интегрального обслуживания (B-ISDN),
которая уже использует ATM в качестве ШТП ИС.
И самой главной причиной массового развития сетей WATM является эффективное
решение задач создания “последней мили” для глобальной сети Internet. Даже при первичном
анализе всех аспектов функционирования кабельных сетей ATM становится ясно, что WATM будет
более сложной, чем большинство других беспроводных сетей. В то время как, например, IEEE
802.11 охватывает только методы доступа к локальным областям, Bluetooth наращивает пикосети,
a Mobile IP работает только на сетевом уровне, сеть WATM должна строиться на комплексной
системе управления, охватывающей и физический уровень, и доступ к среде, с учетом
маршрутизации, и интеграцию в кабельную сеть ATM. Комплексная система, осуществляя
оптимальную реконфигурацию топологии, должна обеспечивать надежность функционирования
каналов связи сети таким образом, чтобы поддерживалась необходимая связность и
виртуальность сети [9, 13].
Таким образом, для WATM необходимо обосновать следующие дополнительные
специфицированные требования по расширению технологии ATM [7, 8], а именно ввести
следующие дополнительные функции [11,14]:
1. Управление конфигурацией топологии БИУ. Подобно другим сотовым сетям, сети WATM
должны быть в состоянии определить местоположение беспроводного терминала (БИУ как
мобильного пользователя), то есть найти текущие координаты точек доступа терминала к сети.
2. Поддержка адаптивной маршрутизации. Даже если системе управления известно
местоположение терминала, она все же еще должна маршрутизировать транспортный поток по
сети к точке доступа, в данный момент отвечающей за (мобильный) терминал. Всякий раз, когда
пользователь перемещается в новую точку доступа, система должна изменить маршрут
ISSN 1028-9763. Математичні машини і системи, 2006, № 2 50
БМТ
РР
РР
ТД
РР
ТД
КАТМ
точка анкера
КАТМ
Стационарный
сегмент
БМТ – беспроводный мобильный терминал
РР – радиоретранслятор
ТД – точка доступа
КАТМ – коммутатор АТМ
транспортируемого потока.
3. Управление изначальным назначением ресурсов радиосвязи и резервом, необходимым
для реконфигурации сети. Как и для других беспроводных сетей, в данном случае должны быть
определены основные и резервные каналы (радиочастоты, схемы модуляции БИУ с разным
числом разных типов антенн).
Последнее требование является определяющим в создании алгоритмов реконфигурации
БИУ в сети WATM с высокой надежностью функционирования.
Простая эталонная модель назначения
радиоканалов, так называемая модель
реконфигурации [8, 9, 11, 12] сети WATM,
приведена на рис. 1. Сквозной канал WATM
разделен на несколько сегментов. Стационарный
сегмент – это часть соединения, на которую не
влияет реконфигурация, чего нельзя сказать о
сегменте, который полностью внутри домена
реконфигурации. Домен управлений реконфи-
гурацией может объединять несколько БИУ:
коммутаторов, точек доступа. Он размещен
внутри одного административного базового домена центрального БИУ (ЦБИУ). Границей между
реконфигурируемым сегментом переключения и стационарным сегментом ЦБИУ является точка
анкера.
Если обе конечные системы являются беспроводными мобильными терминалами WATM,
стационарного сегмента может не быть вообще. В этом случае точка анкера соединяет два сегмен-
та реконфигураций, которые могут находиться в разных доменах реконфигурации.
В работе рассматривается сеть, состоящая из базовых (стационарных) центральных
(ЦБИУ) и мобильных базовых узлов (БИУ), обслуживающих терминалы пользователей. Для
системы назначения каналов связи установлено ряд требований, связанных с тем, что типы БИУ
различаются по числу исходящих (коммутируемых) каналов, точнее, узконаправленных антенн.
Компания NERA создала четыре типа БИУ с двумя, тремя, четырьмя и пятью разнесенными
антеннами, но и это не всегда позволяет получить (реконфигурировать) полнодоступную топологию
(каждый с каждым), и тогда БИУ выступает и в роли ретрансляторов.
Исходя из этого, требования к реконфигурации следующие [7–15]:
1. После реконфигурации топология должна обеспечивать заданное число соединений.
Поскольку ATM является технологией, ориентированной на установление соединений (коммутация
каналов), в условиях, когда конечные системы могут поддерживать множество соединений в одно и
то же время, после реконфигурации топология сети WATM должна поддерживать более одного
тракта (маршрута). Из этого требования вытекает, что после реконфигурации изменяется число
трактов передачи для каждого глобального соединения. Однако возможна ситуация, когда до-
ступные ресурсы не позволяют обеспечить тракты (маршруты) с минимальным числом соединений.
Тогда это приводит к повышенному числу ретрансляций, что ухудшает качество обслуживания. В
таком случае терминал должен принять более низкое качество или отбросить отдельные
соединения.
Рис. 1. Пример эталонной модели
реконфигурации каналов
ISSN 1028-9763. Математичні машини і системи, 2006, № 2 51
2. В процессе реконфигурации должна обеспечиваться возможность перехода от
одноточечного соединения к многоточечным. Прямая поддержка связи одноточечных соединений с
многоточечными является одним из главных преимуществ технологии ATM. Следовательно, после
реконфигурации топологии сеть WATM также должна поддерживать эти типы соединений. Однако,
вследствие сложности конфигурации топологии, может понадобиться снять некоторые ограниче-
ния. Например, если отсутствует точка расщепления внутри сегмента реконфигурируемой топо-
логии, то можно ввести дополнительную точку, чтобы избежать перемещения точки расщепления в
центр топологии.
3. После реконфигурации должны обеспечиваться заданная целостность данных и
безопасность их передачи. Реконфигурация WATM должна минимизировать потери ячеек,
избежать дублирования или переупорядочивания ячеек, и самое главное, реконфигурация должна
обеспечить заданную надежность соединения между терминалом и сетью. Высокая надежность
поддержки необходимой связности и виртуальности сети требуется для безошибочной передачи
сигналов при достаточно развитой маршрутизации. Мониторинг сети WATM для этого должен
предоставлять средства идентификации коммутаторов с поддержкой мобильности и средства
определения данных о загрузке соседних коммутаторов, а также информацию о возможности
изменения трактов, необходимую при потере отдельных соединений в реконфигурируемом домене
сети.
3. Формализация процессов функционирования сети WATM
В начале разработки алгоритмов реконфигурации топологии необходимо хотя бы кратко изложить
сущность основных сетевых параметров WATM [12–15]. На рис.2 представлены топология (рис. 2а)
и основные параметры сетевой структуры. Выделив два определяющих стохастических процесса:
поступление нагрузки (MMT) в различное время на разные БИУ и выход из строя тех или иных
каналов связи (КС) между БИУ, можно дать следующие определения сетевым параметрам [9, 13]:
1. Матрица тяготения (она определяет передачу MMT между определенными абонентами в
течение определенного интервала времени (сеанса связи (рис. 2б)).
2. Матрица связности БИУ: наличие КС между БИУ на момент сеанса связи (передачи ММТ)
(рис. 2в).
3. Маршрутно-адресные таблицы, определяющие основной и запасные маршруты передачи
ММТ (рис. 2г).
В работе [9] дано первичное определение критериев интегрального оценивания надежности
функционирования сети, зависящих как от топологии, так и от остальных сетевых параметров. Это
критерии связности и виртуальности сети:
– заданная связность сети на заданный момент времени определяется наличием заданного
числа связей БИУ с сетью;
– заданная виртуальность сети на заданный момент времени определяется наличием
заданного числа маршрутов ijm для матрицы тяготения.
Исходя из этих требований поддержания заданной надежности сети, которая оценивается
связностью и виртуальностью, ее можно представить в виде поля виртуальных каналов (ПВК) [13].
При таком подходе можно дать интегральную оценку надежности функционирования сети в целом.
ISSN 1028-9763. Математичні машини і системи, 2006, № 2 52
БИУ2
БИУ4
БИУ1
БИУ3
БИУ6
БИУ5
ММТ25
“а”
1
2
3
4
5
6
1 2 3 4 5 6
+
+
Передача-прием с БИУ2
Передача-прием с БИУ5
“б”
1
2
3
4
5
6
1 2 3 4 5 6
+
+ +
+ +
+
+ + +
+
+
+
+ +
+
+
+
+
+
+
++
“в”
1
2
3
4
5
6
1 2 3 4 5 6
основные маршруты
запасной маршрут
“г”
Рис. 2. Сетевые параметры: топология сети (а), матрица тяготения (б), матрица связности БИУ сети (в),
матрица маршрутов
При этом степень связности ijl каждого БИУ с сетью определяет связность сети, а степень
виртуальности сети определяет мощность ПВК, которая необходима для заданной
эффективности маршрутизации. Эти критерии и решают задачу интегрального оценивания
надежности сети [9]. Например, если все БИУ сети имеют не менее двух связей с сетью ( )2≥ijl , то
считается, что такая сеть находится в режиме нормального функционирования. Если же имеется
БИУ, у которого осталась только одна связь с сетью ( )1=ijl , то наступает режим критического
функционирования. Аналогично, если между БИУ (исходя из матрицы тяготения абонентов)
имеется более двух маршрутов, то необходимая производительность сети с заданной
своевременностью и верностью передачи ММТ [13, 14] обеспечивается, и наоборот.
На рис. 3 приведен пример двух вариантов конфигурации топологии сети WATM, которые
допускают для любой матрицы тяготения передачу с одной ретрансляцией (рис. 3а) и без
ретрансляций (рис. 3б). В сети все БИУ должны иметь как минимум по три, а опорные центры
ISSN 1028-9763. Математичні машини і системи, 2006, № 2 53
(ЦБИУ) по четыре КС с сетью. Для этой топологии (рис. 3а) ПВК имеет конфигурацию
неполносвязной сети (когда каждый БИУ не имеет “прямой” связи с каждым), это ячеистая
конфигурация шестерки (рис. 2). При этом у сети имеются БИУ с l ij 3 и ЦБИУ с l ij 4 .
“а”
БИУ с l ij 3 и ЦБИУ с l ij 4
“б”
БИУ с l ij 5
Рис. 3. Поле виртуальных каналов у ячеистой (а) и полнодоступной (б) конфигураций топологий
Рассматривая процессы появления отказов и восстановлений каждого КС как независимые
процессы, а деградацию всей сети как наихудший случай, возникший в процессе
функционирования, можно просмотреть все состояния работоспособности сети (события как
состояния, в которых сеть может находиться вплоть до критических режимов функционирования).
Классифицируя при этом состояния работоспособности на события нормального, критического и
ненормального функционирования, а также располагая временем нахождения в каждом из них,
можно определить коэффициенты готовности сети К гс , как вероятности застать сеть в любой
момент времени в состояниях с заданной связностью БИУ: l ij lтр . Будем рассматривать случай
ячеистой конфигурации топологии (рис. 3а).
На рис. 4 представлены ярусы процесса функционирования сети, состояние
работоспособности которой объединены в соответствующие группы по признаку наличия в каждом
БИУ определенного количества связей с сетью l ij [9, 13].
Нулевой ярус – все КС исправны (состояние работоспособности одно , l ij 3 и l ij 4 для
центрального БИУ (ЦБИУ).
Первый ярус – отказала одна любая КС, а остальные исправны (число состояний C 11
1
,
min l ij 2 ). Это режим нормального функционирования.
Второй ярус – отказали две КС (число состояний C 11
2
, min l ij 1 ). Это режим
критического функционирования (так как есть БИУ, у которых l ij 1 l т ).
Третий ярус – отказали три КС (число состояний C 11
3
, min l ij 0 ). Это срыв нормального
функционирования, т.е. режим хуже критического. Однако в третьем ярусе объединяются состоя-
ния работоспособности сети, среди которых имеются состояния с локализованными (не связанны-
ми с сетью) центральными БИУ и состояния, у которых нет локальных БИУ ( l ij 4 ).
БИУ-2 БИУ-3 БИУ-4
БИУ-1 БИУ-6 БИУ-5
Ц
Ц
БИУ-2 БИУ-3 БИУ-4
БИУ-1 БИУ-6 БИУ-5
ISSN 1028-9763. Математичні машини і системи, 2006, № 2 54
характеризуется режимами критического функционирования. Для таких ярусов вводится
коэффициент потери связности ПВК К пц как отношение числа состояний с локальными БИУ ко
всему числу состояний яруса [9]. Остальные ярусы характеризуются режимом ненормального
(ниже критического уровня) функционирования.
5. Аналитическая модель анализа надежности функционирования сетей с различной конфи-
гурацией их топологий
Для рассматриваемого примера связность сети, оцениваемая отношением числа состояний
М к М я М
'
(у которых БИУ имели mpij ll ≥ , т.к. не возникли состояния критических режимов
( )1=ijl kM ) ко всему числу состояний яруса яM , определяется коэффициентом потери
связности К ця
l 1
и К ця
l 2
[9, 16]:
К ця
l 1 М я М
'
М я
165 4
165
0,97576 ;
К ця
l 2 М я М
' '
М я
165 94
165
0,43 ;
(1)
где М я С 11
3
– число состояний яруса; М
' ,М ' '
– число состояний с локализованными
БИУ и БИУ с l ij 2 .
Рис. 4. Анализ процесса функционирования сети
WATM с ячеистой топологией
При оценке надежности
функционирования сети по критерию К гс
эта часть яруса характеризуется режимами
критического функционирования. Для таких
ярусов вводится коэффициент потери
связности ПВК К пц как отношение числа
состояний с локальными БИУ ко всему
числу состояний яруса [9]. Остальные ярусы
характеризуются режимом ненормального
(ниже критического уровня) функциони-
рования.
4. Аналитическая модель анализа
надежности функционирования сетей с
различной конфигурацией их топологий
При оценке надежности функционирования
сети по критерию К гс эта часть яруса
характеризуется режимами критического
ISSN 1028-9763. Математичні машини і системи, 2006, № 2 55
К ця
l 1 М
'
М я
4
165
0,02424 ;
К ця
l 2 М
' '
М я
94
165
0,57 ;
(2)
Виртуальность сети, как число возможных маршрутов между БИУ заданной матрицы
тяготения, оценивается отношением числа состояний с заданным числом маршрутов, оставшихся в
каждом состоянии сети яруса Rk , без учета одного «опорного» маршрута R0 , к числу всех
состояний с любым числом маршрутов:
Rня
Rk R0
Rk
. (3)
Коэффициент готовности сети как вероятность Pmk
k
нахождения сети в процессе функцио-
нирования в определенном km состоянии работоспособности любого к -го яруса определяется
моделью «гибели и размножения» – системой уравнений Колмогорова – Чепмена [16].
Вероятность застать сеть в области работоспособных состояний, когда все БИУ имеют не
менее одной связи с сетью, может быть оценена в изложенной выше трактовке выражением [9, 13,
16]:
К гс
k 0 0
m0
i 1
C11
k0
Pmi
k ця
0
k ' 0
m'
i 1
C11
k '
Pmi
k ця
'
, (4)
где m0
и m '
– количество ярусов с состояниями, удовлетворяющими и не удовлетворяющими
заданному критерию связности ( l ij lтр и l ij lтр ); k 0
, k '
, K ця
0
и K ця
'
– номера ярусов и
коэффициентов их целостности с удовлетворяющими и не удовлетворяющими состояниями
соответственно.
Предположим, что КС однотипны и обладают одинаковой безотказностью ij и
восстанавливаемостью i , вероятность нахождения сети в состояниях работоспособности Pmk
k
для
каждого mk яруса определяется в соответствии с системой уравнений Колмогорова – Чепмена
следующим образом [16]:
p0 0 p1 1 0,
p1 1 1 p0 0 p2 2 0,
p2 2 2 p1 1 p3 3 0,
p3 3 3 p2 2 p4 4 0,
p4 4 4 p3 3 p5 5 0,
p5 5 5 p4 4 p6 6 0,
p6 6 6 p5 5 p7 7 0,
p7 7 7 p6 6 p8 8 0,
p8 8 8 p7 7 p9 9 0,
p9 9 9 p8 8 p10 10 0,
p10 10 10 p9 9 p11 11 0,
p11 11 p10 10 0,
p0 p1 p2 p3 p4 p5 p6 p7 p8 p9 p10 p11 1,
(5)
ISSN 1028-9763. Математичні машини і системи, 2006, № 2 56
где ij и ij интенсивности отказов и восстановлений КС сети.
Подставляя вычисленные вероятности Pmk
k
(5) в формулу (4), получим коэффициенты
готовности сети К гс для разных критериев связности сети.
Аналогичным образом формируется модель анализа влияния безотказности и
восстанавливаемости КС на виртуальность сети, то есть оценивается влияние надежности КС на
эффективность маршрутизации, которая обеспечивает заданную производительность сети.
На рис. 5 приведены графики зависимости готовности от надежности КС для сетей с
различной степенью связности их БИУ: l ij 1 и l ij 2 для ячеистой топологии, рис. 3а (график на
рис. 5а) и l ij 3 и l ij 5 для полнодоступной , рис. 3б (график на рис. 5б).
1 2 3 4 5 6
К гс
l ij 1
l ij 2
ij 5 ij 10
1 2 3 4 5 6
К гс
l ij 3
l ij 5
ij 5
ij 10
а (ячеистая топология) б (полнодоступная топология)
Рис. 5. Графики зависимости готовности сети от различных параметров надежности каналов связи
(интенсивностей отказов и востановлений)
6. Аналитическая модель синтеза реконфигурируемых топологий
Для модели синтеза оптимальной конфигурации топологии сети лучше всего подходит
модифицированный метод ветвей и границ, который является универсальным методом дискретной
оптимизации. Он базируется на следующих процедурах [18, 19]: задание исходного множества
вариантов перебора, выбор наиболее перспективных множеств при разбиении исходного
множества, ветвление перспективных множеств на более перспективные подмножества перебора.
Эти процедуры базируются на определении нижней границы значений коэффициента готовности
К тр для каждого из образовавшихся подмножеств. В процессе ветвления идет поиск допустимого
решения в каждом из образованных подмножеств с проверкой признаков оптимальности. Основная
трудность метода ветвей и границ состоит в выборе способа ветвления (разбиения) множества на
подмножества и задании эффективной нижней границы критериев, позволяющих отбрасывать
большое число бесперспективных вариантов перебора [18].
Реализация метода ветвей и границ для задачи назначения тех или иных БИУ, исходя из
числа антенн с учетом надежности каждого КС и стоимости БИУ, позволяет реализовать синтез
оптимальной конфигурации топологии сети. Метод состоит из конечного числа однотипных
итераций, на каждой из которых строится совокупность подмножеств синтезируемых вариантов
[17, 18]:
ISSN 1028-9763. Математичні машини і системи, 2006, № 2 57
G v
k , v 1,2 ,... , k , (6)
где к – номер итерации.
Каждое из подмножеств G v
k
характеризуется следующими множествами: P v
k
–
множество координат будущих БИУ, где должны быть БИУ (без ретрансляторов); Qv
k
–
множество, где еще нужно ставить БИУ, чтобы уменьшить число ретрансляций; Rv
k
– множество,
где наложен запрет на размещение БИУ.
P v
k Q v
k Rv
k Y , (7)
где Y – исходное множество заданных координат, в которых необходимо ставить БИУ
определенного типа.
Обозначим через уХ множество подключенных всех разнотипных БИУ yi ( y i P ) по
критерию минимума затрат, т. е. x X y i , если C x yi
пер min C xy
пер hx , l xy . Тогда каждое из множеств
G v
k
будет характеризоваться величиной нижней границы критерия готовности Gv
k
для всех
структур (решений), определяемых данным множеством. Величина задается при этом
следующим соотношением:
G v
k
y Pv
k x X y
C xy
пер hx , l xy
y P v
k
C обр H y
y Qv
k x X y
C xy
пер hx , hxy C обр H ост
y Qv
k
C обр H y
, (8)
где
H ост
x X ост
hx .
Сущность модификации метода ветвей и границ [18, 19], заключается в том, что, применяя
приближенный метод (например, метод R-структур) удается построить структуру X 0 на множестве
G v
k
. При этом в решение должны войти все типы любых БИУ y i P v
k
и не должно быть ни од-
ного БИУ y R v
k
. Критерием отбора при этом будет приращение W X 0
К гс
C
. В отличие
от аддитивного критерия эффективности [18] взят мультипликативный критерий. Обозначив
величину этого критерия для структуры X 0 через W X 0 , получим следующий признак опти-
мальности: если W X 0 G v
k
, то вершина дерева решений G v
k
является конечной и даль-
нейшему разбиению не подлежит; если W X 0 min G i
k
для всех висячих вершин G i
k
,
построенных на k -й итерации, то X 0 – искомое оптимальное решение (структура).
Предположим, что уже проведено k итераций и еще не найдено оптимальное решение,
опишем процесс перебора с ветвлением, где каждая произвольная k 1 -ая итерация
характеризуется нижеследующими признаками (рис. 6):
1. Среди всех множеств Gi
k
, построенных в результате k -й итерации, выбирается
наиболее перспективное множество G v
k
, т. е. Такое, что
ISSN 1028-9763. Математичні машини і системи, 2006, № 2 58
Gv
k min Gi
k
. (9)
В нашем случае это соответствует тому, что там, где в одном и том же приращении
стоимости более существенно растет K гт .
2. Ветвление. Выбираем некоторый БИУ y G v
k
и разбиваем G v
k
на два подмножества
G v1
k
и G v2
k
так, что на подмножестве G v1
k
БИУ yr переводится в разряд действующих, а на
подмножестве G v2
k
накладывается запрет на размещение БИУ в пункте yr . Таким образом,
G v1
k P v
k y r ;Qv
k yr ; Rv
k ;
Gv2
k P v
k ;Qv
k yr ; Rv
k yr .
. (10)
Будем выбирать yr так, чтобы подмножество G v1
k
с наибольшей вероятностью
содержало искомое решение, а G v2
k
не содержало. Тогда
H yr max H y i
yi Q v
k . (11)
3. Вычисление оценок Gv1
k
и Gv2
k
. В частности, для множества Gv2
k
можно
использовать следующую рекуррентную формулу:
Gv2
k G v
k
x X y
r
min
y rr
C xy
пер C x y r
пер
. (12)
Для вычисления G v1
k
используем формулу (8).
4. На каждом из подмножеств G v1
k
и G v2
k
находим допустимое решение, которое обозна-
чим X v1
k
и X v2
k
соответственно.
5. Проверка признака оптимальности. Пусть Gv1
k G v2
k
. Если
W X v1
k min G v1
k ; G v2
k ; G i
k
, (13)
где G i
k
– множество висячих вершин на k -й итерации, то X v1
k
– искомое решение, и
конец работы алгоритма. В противном случае переходим на k 2 -ю итерацию, переобозначив
для всех висячих вершин
Gi
k 1 G i
k , i 1, k ;G
k 1
k 1 Gv1
k ;G
k 2
k 1 G v2
k
. (14)
Весь процесс решения реализуется в виде дерева вариантов (рис. 6).
Проводимые исследования показали, что метод ветвей и границ для структурного синтеза
конфигурации топологии сетей WATM не требует больших вычислительных затрат даже при числе
возможных координат размещения БИУ m 20 .
7. Заключение
В работе предложена методология системного анализа и синтеза процессов реконфигурации топо-
логии сети, исходя из обеспечения надежности ее функционирования. Эта методология может
быть положена в основу алгоритмов реконфигурации топологии БИУ для сетей WATM.
Для поддержания заданных режимов нормального функционирования, обеспечивающих
ISSN 1028-9763. Математичні машини і системи, 2006, № 2 59
заданную связность сети, необходимо ввести в систему мониторинга отслеживание допустимых
порогов безотказности и восстанавливаемости КС. Особо важен контроль допустимых порогов
безотказности ( ij доп ) для сетей ,у
которых БИУ должны иметь l ij 5 (рис
5б).
В предлагаемой методологии
синтеза отличием от известных методов
оптимизации [18, 19] является введение
мультиплексированного критерия эффек-
тивности [8], что позволяет сократить
объем вычислений при ветвлении и
нахождении границ, используя
соотношения приращений
K г
C
[20, 21].
Сравнительный анализ
различных методов синтеза:
динамического программирования,
модифицированного метода ветвей и границ – будет рассмотрен в последующих статьях.
СПИСОК ЛИТЕРАТУРЫ
1. Research Networking. The GEANT Network // www.cordis.lu, 2003.
2. Гриценко В.И., Урсатьев А.А. Распределенные информационные системы. Состояние. Перспектива разви-
тия // УСиМ. – 2003. – № 4. – С.11–21.
3. Гриценко В.И., Горбунов И.Э., Ластовченко В.М. Проблемы формализации процессов функционирования и
управления интегральной широкополосной транспортной платформой интеллектуальных сетей // УСиМ. –
2005. – № 6. – С. 87–96.
4. Ластовченко М.М., Биляк В.И. Концепция формирования базовых интеллектуальных узлов коммутации для
широкополосных сетей связи // УСиМ. – 2005. – № 6. – С. 28–36.
5. Ластовченко М.М., Медных В.В., Рашник Т.Н. Системный анализ эффективности интегрального управления
интеллектуальными сетями с асинхронным методом передачи информации // УСиМ. – 2000. – № 5, 6. – С.
113–121.
6. Гольдштейн Б.С., Ехриель И.М., Рерле Р.Д. Интеллектуальные сети // Радио и связь. – 2000. – 502 с.
7. Ranhola K. Baseline Text fro WATM specification // ATM forum RTD-WATM. – P. 32–58.
8. Bhatt R.R. WATM Requirments Specification // ATM Forum, RTD – WATM. – 1998. – P. 58–70.
9. Ластовченко М.М., Русецкий В.Е. Введение критериев интегрального оценивания в системный анализ на-
дежности функционирования широкополосной сети связи // УСиМ. – 2005. – № 2. – С. 56–68.
10. Enabling a wireless future // Nera Networks AS. Norway. – 2002. – 44 p.
11. Шиллер И. Мобильные коммуникации. – М.: Вильямс, 2002. – 375 с.
12. Горбунов И.Э. Проблемы создания беспроводной транспортной платформы интеллектуальной сети // Ма-
териалы МНК НАУ. – 2003. – С. 94–100.
13. Ластовченко М.М., Биляк В.И., Павлюк В.С, Рашник Т.Н. Анализ надежности интеллектуальных корпора-
тивных сетей, функционирующих в поле виртуальных каналов // УСиМ. – 2001. – № 5. – С. 64–72.
14. Ластовченко М.М., Ярошенко В.Н., Биляк В.И. Математические аспекты проектирования интеллектуальных
коммутационных систем передачи мультимедийных трафиков // Математические машины и системы. – 2003.
– № 4, 5. – С. 66–75.
15. Nojo S., Watanade H. Incorporating reliability specifications in the design of telecommunication networks // IEEE
Communications Mag. – 1993. – № 6. – P. 40–43.
16. Ченцов В.М. Системы распределения информации. Синтез структуры и управления.–М.:Связь,1980.–148 с.
17. Вентцель Е.С. Исследование операций. – М.: Советское радио, 1975. – 512 с.
18. Shih W. A Branch and Bound Procedure for a Class Of Discrete Resource Allocation Problems with Several Con-
straints // Operational research quarterly. – 1977. – Vol. 28, N 2. – P. 439–452.
19. Righter R., Walrand J.C. Distributed Simulation of Discrete Event Systems // IEEE Trans. Automat. Contr. – 1989.
– Vol. 77, N 1 – P. 245–262.
20. Белман Р., Дрейфус С. Прикладные задачи динамического программирования. – M.: Наука, 1965. – 460 с.
21. Ластовченко М.М, Сидоров Л.А. Техническое обслуживание сложных многоканальных систем связи
// Электросвязь. – 1969. – № 4. – C. 18–27.
Рис. 6. Дерево решений при синтезе структуры
методом ветвей и границ
|
| id | nasplib_isofts_kiev_ua-123456789-83968 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1028-9763 |
| language | Russian |
| last_indexed | 2025-12-07T13:36:15Z |
| publishDate | 2006 |
| publisher | Інститут проблем математичних машин і систем НАН України |
| record_format | dspace |
| spelling | Горбунов, И.Э. 2015-06-30T11:56:37Z 2015-06-30T11:56:37Z 2006 Методология анализа и синтеза реконфигурируемых топологий мобильных сетей связи / И.Э. Горбунов // Мат. машини і системи. — 2006. — № 2. — С. 48-59. — Бібліогр.: 21 назв. — рос. 1028-9763 https://nasplib.isofts.kiev.ua/handle/123456789/83968 681.513 Рассмотрена методология реконфигурации топологии сетей WATM, исходя из надежности их функционирования. Предложен пример реализации методологии системного анализа и синтеза процессов реконфигурации топологии сети. Розглянуто методологію реконфігурації топології мереж WATM, виходячи з надійності їхнього функціонування. Запропоновано приклад реалізації методології системного аналізу і синтезу процесів реконфігурації топології мережі. The methodology of reconfigurable topology of WATM networks is considered, proceeding from reliability of their functioning. The example of implementation of methodology of the system analysis and synthesis of network topology reconfiguration processes is offered. ru Інститут проблем математичних машин і систем НАН України Математичні машини і системи Обчислювальні системи Методология анализа и синтеза реконфигурируемых топологий мобильных сетей связи Методологія аналізу і синтезу топологій мобільних мереж зв'язку, що реконфігуруються Methodology of the analysis and synthesis of reconfigurable topologies of mobile communication networks Article published earlier |
| spellingShingle | Методология анализа и синтеза реконфигурируемых топологий мобильных сетей связи Горбунов, И.Э. Обчислювальні системи |
| title | Методология анализа и синтеза реконфигурируемых топологий мобильных сетей связи |
| title_alt | Методологія аналізу і синтезу топологій мобільних мереж зв'язку, що реконфігуруються Methodology of the analysis and synthesis of reconfigurable topologies of mobile communication networks |
| title_full | Методология анализа и синтеза реконфигурируемых топологий мобильных сетей связи |
| title_fullStr | Методология анализа и синтеза реконфигурируемых топологий мобильных сетей связи |
| title_full_unstemmed | Методология анализа и синтеза реконфигурируемых топологий мобильных сетей связи |
| title_short | Методология анализа и синтеза реконфигурируемых топологий мобильных сетей связи |
| title_sort | методология анализа и синтеза реконфигурируемых топологий мобильных сетей связи |
| topic | Обчислювальні системи |
| topic_facet | Обчислювальні системи |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/83968 |
| work_keys_str_mv | AT gorbunovié metodologiâanalizaisintezarekonfiguriruemyhtopologiimobilʹnyhseteisvâzi AT gorbunovié metodologíâanalízuísintezutopologíimobílʹnihmerežzvâzkuŝorekonfíguruûtʹsâ AT gorbunovié methodologyoftheanalysisandsynthesisofreconfigurabletopologiesofmobilecommunicationnetworks |