автореферат диссертации по радиотехнике и связи, 05.12.14, диссертация на тему:Исследование и разработка метода узлообразования на ГТС

Государственный комитет Российской Федерации но связи н пнформнщ ¡¡шин ¡Московским технический университет связи и ни форм;! гики

На правах рукописи

УДК 621.395

НГУЕНЛЫОНГНЬЯТ

ИССЛЕДОВАНИЕ И РАЗРАБОТКА МЕТОДА УЗЛООБРАЗОВАНИЯ НА ГТС

Специальность 05.12.14 - Сети, узлы связи и распределение информации

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Москва 1997

Работа выполнена на кафедре "Автоматическая электросвязь" Московского технического университета связи и информатики.

Научный руководитель: кандидат технических наук,

доцент Нестерова А.В Официальные оппоненты: доктор технических наук,

профессор Нейман В.И., кандидат технических наук, старший научный сотрудник Сергеева Т.П.

Ведущая организация: Научно - технический центр "Комсет"

Зашита диссертации состоится "Дбй.Л.Д...." 1997 г. в ..АЛ. часов на заседании диссертационного совета К. 118.06.02 Московского технического университета связи и информатики по адресу: Москва - 24, ул. Авиамоторная, д.8а.

С диссертацией можно ознакомиться в библиотеке МТУСИ.

Автореферат разослан 997г.

Ученый секретарь диссертационного совета К 118.06.02

кандидат технических наук, профессор

¿О

Демина Е В.

ОБЩАЯ ХАРАКТЕРИСТИКА ГМ.ОТЫ

Актуальность проблемы. Предлагаемая работа посвящена проблеме перспективного проектирования городских телефонных сетей (ГТГ).

В условиях широкого внедрения цифровых систем коммутации и передами, интеграции сетей связи особенно актуальным является совершенствование теории и практики перспективного проектирования ГТС.

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

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

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

Развитие современных математических методов моделирования на базе применения вычислительной техники значительно сокращает трудности решения динамических задач.

Учитывая большое количество ГТС, а также объемы капиталовложений на их построение и развитие, даже незначительный процент экономии (2% + 5%) от внедрения принятых решений может дать снижение затрат в миллиарды рублей на построение сетей.

Цель работы и 1:1.1:1411 исследования. Целью диссертационной рабоп.1 является исследование методов узлообразовання на ГТС, разработка алюршмои построения динамических моделей узлообразовання и оптимизации динамнчс-. скп\ схем. Данная цель достигается в результате решения следующих основных задач:

математической постановки динамической задачи узлообразовання ГТС; разработки алгоритмов построения динамических моделей узлообразовання на графе развития сети, анализа основных переменных, допущений и ограничений, принятых в модели;

разработки статических схем узлообразовання, входящих в состав динамической модели и процедур их оптимизации;

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

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

Мстолы исследования. Теоретические разработки и экспериментальные исследования основаны на теории исследования операций, теории сетей связи, теории графов, теории автоматической коммутации. Научная новизна работы.

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

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

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

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

простая логика перебора вариантов, разработанная Раппом при решении задачи районирования ГТС.

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

Практическая ценность и реализация результатов работы. Алгоритмы построения динамических моделей и оптимизации динамических схем непосредственно предназначены для использования при разработке генеральных схем развития ГТС. Анализ эффективности данных алгоритмов по сравнению со статическими показал возможность сокращения затрат на построение сети до 7%.

Разработанные алгоритмы узлообразования и выбора кабельных трасс реализованы в виде программ для ПЭВМ и позволяют получить все необходимые параметры для проектируемых объектов.

Результаты работы внедрены в учебный процесс кафедры " Автоматическая электросвязь" МТУСИ и института связи г. Ханоя Вьетнам в форме программ на ПЭВМ для проведения практических занятий по дисциплине "Сети связи''.

Апробация работы. Результаты диссертационной работы докладывались, обсуждались и получили одобрение на научно-технической конференции НТО-РЭС имени A.C. Попова в 1995г. (Москва), на научно-технических конференциях профессорско - преподавательского состава МТУСИ (1996,1997), а также на заседаниях кафедры АЭС МТУСИ.

Публикации. Основные результаты диссертационной работы опубликованы в б печатных работах и включены в отчет о госбюджетной НИР Гос. per. № 01.9.20.01.4727.

Основные положения, выносимые на защиту.

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

2. Разработанные эвристические алгоритмы построения динамических моделей на графе развития сети для решения динамической задачи узлообразования пошоляют учитывать прямые и обратные временные и пространственные связи, включать в модель лишь конкурентоспособные схемы. Определяя затраты на ка-

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

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

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

5. Представленные примеры динамических моделей позволяют определить влияние различного числа переменных на размерность модели и следовательно, оценить сложность ее расчета.

Объем и структура диссертации. Диссертационная работа состоит из введения, пяти глав, заключения, списка литературы и двух приложений. Работа изложена на страницах машинописного текста, содержит 23 рисунка. Список литературы включает 66 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе диссертации дается математическая постановка динамической задачи узлообразования ГТС.

На каждом этапе развития сети V = , где N - число этапов рассматриваемого периода, математическая модель ГТС представляется в виде графа (!(у), в котором вершинами являются места расположения АТС А(у) = {ч,(у)}, / -\,п(у), где п(у)- число АТС., а ребрами - трассы кабельной канализации - Н(у)~ (у)^ (г))} ; /,./= 1,'!(1')- Каждая вершина графа имеет вес, соответствующий емкости станции - ш, (V); / = 1,лг(V). Каждому ребру присваивается вес, соответствующий протяженности в км - с/,у (у),'/,./' = 1,я(у). Кроме того, на графе задано множество станций, в которых могут располагаться узлы - > = {</„('')}

, // = \,к(у)~, 0(у) с: А(у), где к(у) - число транзитных узлов на этапе V. Будем понимать под узловым районом (УР) множество АТС, подключенных к одному узлу. Емкость УР представляет собой суммарную емкость АТС, входящих в мот УР.

Проблема узлообразования ГТС с учетом динамики ее развития заключается в следующем. На заданном множестве АТС А (у) и множестве возможных мест расположения узлов С>(\') на каждом этапе развития сети г= I, А/ следует определить такое количество узлов, их местоположение и емкости узловых районов, при • которых ¡атрлты на построение линейных сооружений и узлового оборудования ¡а весь период развития были бы минимальными.

Оптимизация динамической задачи узлообразования ГТС сводится к минимизации целевой функции затрат на построение сети межстанционных свя!ей:

2= I

г=0

»<>')*(>•) г ' 1

I I

1-1 //»1

кц-) Гя(и) , , ,

+1 1йр,(1')]у'')к(1')

кц-) Гя(и)

щ

I '=1

<(>')*( г)

+ I

,гА к = 1

(П

п(г) , п{у) ,

I У, ( у)А„ ((у). I У, (V)А Л у)х17 (V) ; = 1 ; = 1

»(I') , 1 = 1

Чг).

где У, (I') - исходящая на сеть нагрузка АТС;, равная поступающей нагрузке У,.(у) на АТС, за исключением внутристанционной нагрузки У„(у): и <1 щ - протяженности соответственно между АТС, - ТУ,, и ТУ,,-ТУ, ;

$(у) - коэффициент приведения затрат на этапе V к началу расчетного периода;

х1/1 ('•')• х!у (у)< " Ау (г)-двоичные функции, которые принимают

значения;

Г], если узел /I на этапе \> установлен, [О, в противном случае. [1, если узел у на этапе V установлен, [О, в противном случае. При Д„(^) =1:

П, если от АТС; организуется пучок каналов к ТУ^

на э т апе V,

О, в противном случае. При Д„(г) =0 .г,„(|')=0. При А., (г) = I:

+

II. если от АТС; организуется пучок каналов к ТУ^

па этапе г, 0. в противном случае.

При ДгО') = 0 Л',/(|-) = 0.

В выражении (I) функционал (р^ представляет собой соответственно затраты па пучки внутриузловой связи между АТС, и ТУ Коэффициент 2 учитывает два пучка - исходящий и входящий.

Функционал <Р2 представляет собой затраты на организацию транзитных узлов, включая здание, земельный участок и коммутационное оборудование, а -затраты на пучки межузловой связи.

Минимизация целевой функции должна производится с учетом следующих ограничений:

к{ V) ___

5>,,.,(1') = 1 : '.М ;\,п(у), (2)

;/=|

; (3)

/=1

*(>•) _

У>„(г)< 1Лу/(у); к = 1, N -1, (4)

/'=1 /'=1 ___

А,,(у)<Ам(У + 1) ; = 1 (5)

11<1>) _

>Л/,шпун;1;/' = (б)

/-1

Ограничение (2) означает, что каждая станция может быть подключена только к одному из узлов. Ограничение (3) означает, что нагрузка на узел не должна превышать максимальной. Ограничение (4) гарантирует, что при переходе от этапа у к этапу (у-Н) количество ТУ не может уменьшаться, а должно либо сохраняться, либо увеличиваться. Ограничение (5) гарантирует, что узел //. установленный на предыдущем этапе, не будет исключен на последующих этапах. Ограничение (6) означает, что емкость узлового района (УР) не должна быть меньше минимальной.

Как видно из приведенных выражений (1-^6), динамическая задача узлооб-рдзования ГТС относится к классу целочисленных задач нелинейного программирования высокой размерности, что затрудняет использование математических методов. Наиболее приемлемым для решения данной задачи является разработка эвристических алгоритмов на графовой модели развития сети.

Во второй главе разработаны динамические модели узлообразования на зрафе развития сети, вершинами которого являются состояния сети в момент

времени 1:1= О, У, где Т - период развития сети, а ребрами - действия по достижению этого состояния - х, . Действия Д'( представляют собой различные мероприятия по узлообразованню, такие как установка узлов, выбор их местоположения и емкости У Р. Состояние сети - et представляет собой совокупность действии по развитию сети, совершившихся за период времени до данного момента I включительно :

с, = Ü*, (5)

1=0

Введем следующие обозначения:

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

2. Связный переход из исходной схемы узлообразовання е0 в конечную et назовем динамической схемой узлообразовання за рассматриваемый период развития сети - Р(е: ).

3 Набор динамических схем узлообразовання за рассматриваемый период развития, образующих область оптимизации, назовем динамической системой узлообразовання или динамической моделью узлообразовання ГТС. Общая формулировка задачи состоит в следующем:

найти F = min F]i'(T,e)], (6)

И*»} 1 v п

где ¡'(Т,е) - динамическая схема узлообразовання за период Т от начальной схемы е0 до схемы ет; {/'(¿Г,с)} - множество динамических схем узлообразовання за период Т от

начальной схемы е0 до схемы ет ; F/l'fT.c)/ - значение целевой функции для динамической схемы 1'П.с). Интегральным критерием качества динамической схемы являются суммарные годовые затраты, приведенные к начальному периоду развития сети:

F\P{T,c)\ = Y.Z, .s„ (7)

t

где Z, - приведенные затраты на организацию схемы в момент времени / для динамической схемы /'(Г,с)\ •V, - коэффициент приведения затрат к началу расчетного периода.

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

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

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

Были разработаны три алгоритма моделирования динамической системы узлообразовання.

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

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

В основу третьего алгоритма положена известная идея узлообразовання, заложенная в генеральных схемах развития ГТС. В качестве оптимального варианта узлообразовання принят вариант по числу узлов и их местоположению, полученный на статической модели третьего этапа развития сети. В предложенном алгоритме решается лишь задача очередности ввода выбранного на третьем этапе числа узлов при сохранении их местоположения. Таким образом, переменной в алгоритме величиной является число УР.

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

Исходные данные и обозначения:

1. Количество градаций емкостей УР - ¿>"; $ = 1,е , где е - число градаций У Р.

2. Емкость УР в каждой градации - Нд\ 8 = 1,е.

3. Число градации по местоположению ТУ в зависимости от числа этапов развития сети, на которых производится расширение емкости УР

р\ р = 1,/"; г < N - у+ 1 . Число этапов р отсчитывается от момента г , на котором произведена установка ТУ.

4. Схема узлообразования на этапе ц построенную с Н^ емкостями УР, местоположение которых выбрано по состоянию сети на />ый этап развития -Л'ф(у). Для схемы с расширением, т.е. без установки ТУ воспользуемся обозначением Л'о^(/), в котором 8 =0, а р соответствует местоположению ТУ на этапе их установки.

5. Общее количество статических схем построения сети на одном этапе развития -$(у), а количество динамических схем за весь период развития Т- 5(Ы).

Шаг 1.

1. Для каждой градации емкости УР 8(5= \,е ) определяется количество УР на первом этапе развития - Для этого емкость сети на первом этапе делится

на емкость УР каждой из градаций8:

~л(1)

2>,0)

М1) =

Ял-

(8)

где £¿(1) - количество УР емкостью Н6 на 1-ом этапе:

- знак округления до целого числа в большую сторону.

Для некоторых градаций емкостей УР - Н6(5- \,е ) число УР ¿¿(I) может оказаться одинаковым, если емкости УР превышают потребность на данном этапе, а их полное заполнение предлагается на последующих этапах.

2. Для одного и того же числа УР £¿(1) находится количество схем с различным местоположением ТУ. Для этого определяется суммарная емкость всех УР максимальной градации и сравнивается с потребностью в связи на данном этапе. Если

л(2) л(!)

1я1,(2)>ЯЛ(1)*,(1)а: 2>,(1), (9)

/=1 /=1 то будет один вариант местоположения ТУ - ¿>¿(1)= I, который определяется состоянием развития сети на данном этапе.

Если суммарная емкость УР максимальной градации для рассматриваемого числа УР перекрывает потребность в связи последующих этапов V— ,

т.е.

Н3( 1)^(1) >1>,(у), (10)

1=1

то количество вариантов с различным местоположение ТУ будет определяться числом этапов, на которых заполняются емкости УР, т.е.

Рб( 1) = 17; г < N - У+1

3. Для каждого варианта I) по разработанным процедурам [гл.З] уточняются местоположение ТУ и границы действия УР .Таким образом, общее количество схем узлообразования на данном этапе расчета будет составлять:

X 5*0)- (II)

Я>(1)

4. Для каждой статической схемы узлообразования / (/ = 1,Л'(1)) определяются : ' затраты на ее организацию 2, (1).

• Шаг 2...Ж

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

П(У)

2 Н£{у-\)к6(у-\)> ЕщМ, (12)

<5(1-1) <=1

где 0 - суммарная емкость УР на (у- 1)-ом этапе развития.

Если условие (12) выполняется, то новых УР не организуется, а производится расширение существующих. При этом <5>( у) = 0; р$ (у) = 1. Если условие (12) не выполняется, то организуются новые УР, расчет которых, связанный с определением числа УР, их емкости и местоположения ТУ ведется в соответствии с п. 1*т-5.

6. Для каждой статической схемы узлообразования / (/' = 1, Л'( у)) определяются затраты на ее построение - ¿¡{у}.

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

Для каждой динамической схемы узлообразования / (¿ = 1, Л"( /V) ) определи

ляются затраты на ее построение Ъ^ - , где (и) - затраты на

построение статической схемы узлообразования ; на этапе V, входящей в динамическую схему узлообразования /.

8 Из всех динамических схем узлообразовання в качестве оптимальной выбирается схема с минимальными затратами на ее организацию:

г„л„,(л/) = тт{г7}; ./ = 1,Л'(Л') . (П)

В третьей главе предлагается развитие метода Раппа для решения статической задачи узлообразовання ГТС.

Разработаны следующие процедуры решения частных задач узлообразовання:

- размещение ТУ в отдельном УР при заданных границах обслуживания;

- определение границ между двумя УР при заданном местоположении ТУ;

- определение места размещения двух ТУ при известной границе между ними.

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

Расчеты процедуры размещения ТУ и определения границ между УР производятся в два этапа: без учета затрат на межузловые связи (МУС) и с учетом затрат на МУС.

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

участках АТС, - ТУ;, ,ТУ/; - ТУ^, и затраты на кан-км - ,

7-)1у \и,'/ = \,к, где к - число УР, а также радиусы действия УР, которые определяют нагрузки У^с .У ■

Процедура размещения ТУ и определения границ между УР без учета затрат на МУС состоит в следующем.

1. С помощью программы на ЭВМ определяется линия раздела между УР путем отнесения АТС, к тому ТУ ^= 1,к , к которому затраты будут ми-

нимальными:

г*,г=т (14)

где - затраты на кан-км кабеля внутриузловой связи при подключении

АТС, соответственно к 7У/( ; <7(с/(, с/„) - протяженность кабеля (в км) от АТС, к ТУ,, ;

- внутриуповая (шрузка АТС,, подключенной соответственно к ТУ ■

</ - коэффициент пропорциональности, определяющий требуемое число каналов на каждый Эрланг нагрузки и который обратно пропорционален ¡¡-использованию линий (каналов) в пучке — 1 ///.

2. В результате расчетов по п.1 определяется емкость У!'^ - М ^;= 1Д-.

3. В пределах найденных по п.1 границ УР производится смещение ТУ в медиану графа соответствующего УР:

где /•(//) - количество АТС в узловом районом .

4. Вычисления повторяются по п. 1-гЗ до тех пор, пока не будет возникать изменений'в конфигурации сети, т.е. размещении ТУ и границах У Р.

5. В результате расчетов по 1-му этапу будут получены данные:

- местоположение ТУ;

- границы действия УР; -емкости

- средняя протяженность линий внутриузловой связи ¿/(а, ) каждого УР,/,

- затраты на линейные и станционные сооружения сети. Аналогичным образом была разработана процедура расчета для второго этапа с учетом затрат на межузловые связи.

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

Проблема возникает при включении новых узлов, а также при изменении емкости существующих УР, что приводит к необходимости перераспределения каналов между всеми узлами сети.

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

Использование различных приемов и методов анализа сетей связи позволило разработать процедуру решения данной задачи, которая требует значительно меньше времени на проведение вычислений. Обозначения исходных параметров: IV - множество корреспондирующих пар узлов и а, е/1", в каждой паре которых узел ал. является источником, а узел а, - стоком;

1'(аяа,)- потребность в числе каналов между корреспондирующими узлами ауа, е /(•';

1! - максимальная конфигурация сетки линии, в которой представлены все ребра рассматриваемой сети < а, а; > б (7;

с|у - емкость ребра <и,а] > в каналах; < а, с^ > еЧ ;

(1ц - протяженность ребра <> в км; <</,</у > е I! .

Процедура распределения каналов между узлами на ГТС состоит в следующем.

Все ж корреспондирующих пар узлов из И' = { аха, } пронумеровываются в порядке уменьшения потребности в числе каналов, а затем просматриваются в порядке номеров {<3^*7,; ( = 1,«}где ¡/(а1.Я|)>...>У(ахап).

Процедура локальной шаговой оптимизации состоит из основного цикла д = 1 с числом шагов ж, равных числу корреспондирующих пар узлов IV и дополнительных циклов д =2,3,..., организуемых по мере необходимости, если для какой -либо пары узлов не будет решена задача в основном цикле.

В основном цикле на первом шаге £ =1 {£ =1,2,..., ге ) выбирается первая : пара узлов и строится текущая сетка линий М{д ). Для этого из максимальной '" сетки линий V исключаются те ребра, емкость которых ниже требуемого числа ' каналов для первой пары узлов На полученной сетке строится оДннм из

способов, например, методом Флойда кратчайший путь из узла а1 в узел Ес-0

ли кратчаишии путь найден , то строится текущая сетка линии для второго шага А'(1,2). Для этого из емкостей ребер максимальной сетки <7 исключаются израсходованные каналы для первой пары узлов У(а^сц), а также то ребра, емкости которых меньше требуемого числа каналов для второй пары узлов - У(аха?).

На текущей сетке линий А'(1,2) определяется аналогично первой паре узлов возможность удовлетворения связи для второй пары. Описанная процедура повторяется для остальных пар до тех пор, пока не будет удовлетворена потребность в связи для всех пар узлов, либо пока для какой-нибудь пары не найдется пути для реализации требуемого числа каналов.

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

1Г>

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

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

Если решение найдено, то оно еще не гарантирует реализацию требований по единственному пути для каждой из предыдущих пар узлов.

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

Описанная процедура продолжается до тех пор, пока не будет сделан выбор для всех пар узлов ( положительный или отрицательный).

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

В пятой главе приводится три примера построения динамических моделей по трем алгоритмам, разработанным во второй главе. Для наглядности представления динамических моделей была использована абстрактная модель ГТС с равномерной телефонной плотностью и правильной геометрической формой территории сети. Для каждого примера были использованы одинаковые исходные данные для того, чтобы иметь возможность сравнить размерности полученных динамических моделей. Анализ динамических моделей показал, что с увеличением числа переменных, вводимых в модель, количество статических схем, а следовательно и динамических увеличивается. Возрастает также и вычислительная сложность задачи. Однако, чем больше размерность динамической модели, тем точнее может быть получен результат.

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

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

2. Математическая постановка динамической задачи узлообразования показала, что данная задача относится к классу дискретных, детерминированных, нелинейных динамических задач высокой размерности.

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

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

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

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

7. Разработаны программы для автоматизированного проектирования схем развития ГТС, связанные с выбором кратчайших трасс кабельной канализации заданной пропускной способности.

В приложении разработаны на персональном компьютере две программы на языке Borland С":

1. Программа выбора местоположения ТУ и определения границ между УР.

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

способностей кабельных участков сети.

По материалам диссертации опубликованы работы: 1. Нестерова A.B. Нгуен Лыонг Ньят. Выбор кабельных участков межузловой связи на ГТС при проектировании нового узла. Деп. статья в ЦНТИ "Информ-связь" -№ 2021- св 94, с. 49-59.

2. Нестерова A.B., Нгуен Лыонг Ньят. Динамика построения сети между станциями ГТС. Тезисы доклада на 50-ой научной сессии НТОРЭС имени A.C. Попова, посвященной Дню радио. М, 1995.

3. Нестерова А.В, Нгуен Лыонг Ньят. Динамическая модель системы узлообра-зования на ГТС. Деп. статья в ЦНТИ "Информсвязь". -№ 2060-св95, с. 2-10.

- 4. Нгуен Лыонг Ньят, Нестерова A.B. Анализ динамических моделей развития ГТС. Тезисы доклада на научно-технической конференции профессорско-преподавательского , научного и инженерно-технического состава, посвященной 75-летнему юбилею МТУСИ. М, 1996.

5. Нестерова А.В, Нгуен Лыонг Ньят. Алгоритм размещения узловых станции с двухуровневым построением ГТС и определение границ между узловым районами. Деп. статья в ЦНТИ "Информсвязь". - № 2080-св96, с. 78-84.

6. Нгуен Лыонг Ньят. Автоматизация процесса узлообразования на ГТС. Тезисы доклада на научно-технической конференции профессорско - преподавательского , научного и инженерно-технического состава, посвященной 850-летию Москвы. М, 1997.