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

Введение

Глава I. Основы теории неполнодоступных схем.

1.1. Основные понятия неполнодоступных схем.

1.1.1. Понятие о неполнодоступной схеме.

1.1.2. Функционирование неполнодоступной схемы.

1.1.3. Описание неполнодоступных схем.

1.1.4. Изоморфность неполнодоступных схем.

1.1.5. Цилиндры.

1.2. Связь между теориями неполнодоступных схем и блок-схем.

1.3. Равномерные неполнодоступные схемы.

1.3.1. Мера равномерности неполнодоступных схем.

1.3.2. Определение равномерных неполнодоступных схем.

1.3.3. Другие определения равномерных неполнодоступ- . ных схем.

1.3.4. Числовые характеристики равномерных неполно-доступных схем.

1.4. Выводы к главе 1.

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

2.1. Решение системы уравнений равновесия.

2.2. Приближенная оценка вероятностей потерь аналитическим путем.'.

2.3. Статистическое моделирование неполнодоступных схем.

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

2.5. Выводы к главе 2.

Глава 3. Синтез равномерных неполнодостулных схем.

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

3.2. Известные алгоритмы синтеза РНС.

3.2.1. Алгоритм Монте-Карло.

3.2.2. Алгоритм Педерсена.

3.2.3. Таблицы цилиндров.

3.2.4. Алгоритм Пиоро.

3.3. Новый алгоритм синтеза РНС в стандартном виде.

3.3.1. Построение равномерной цилиндрической части.

3.3.2. Построение подходящего остатка.

3.3.3. Усовершенствование остатка.

3.4. Выводы к главе 3.

Глава 4. Формализация проектирования кроссировочных таблиц.

4.1. Кроссировочные таблицы.

4.2. Описание кроссируемого оборудования.

4.3. Описание включения.П

4.4. Описание промщитов.П

4.5. Описание расшивки.П

4.6. Описание кроссировки.П

4.6.1. Последовательная нумерация.

4.6.2. Послойная нумерация.

4.6.3. Клеточная нумерация.

4.6.4. Нумерация подмножеств для неполнодоступной кроссировки.

Глава 5. Применение ЭВМ при проектировании АТС.

5.1. Исходные данные для проектирования кроссировочных таблиц.

5.2. Технология проектирования кроссировочных таблиц с помощью ЭВМ.

• 5.3. Программное обеспечение автоматизированного проектирования кроссировочных таблиц.

5.4. Применение пакета прикладных программ проектирования кроссировочных таблиц.

Актуальность проблемы. Развитие Цциной автоматизированной сети связи страны требует большого вложения капитальных средств по проектированию и строительству новых телефонных и телеграфных станций. Поэтому вопросы, связанные с ускорением и улучшением проектных работ и уменьшением их стоимости, имеют большое народнохозяйственное значение. Основным средством для решения vэтиx вопросов является автоматизация проектирования сооружений связи на ЭВМ. Широкое применение автоматизированного проектирования сооружений связи затрудняется сложностью и разнообразностью проектируемых объектов и отсутствием универсальных алгоритмов, методики и соответствующего программного обеспечения на ЭВМ. Следовательно, разработка таких средств имеет большую актуальность .

Значительную часть (до 20%) £ю] от общего объема проектной документации телефонных и телеграфных станций составляют крос-сировочные таблицы. Составление . кроссировочных таблиц является трудоемкой работой, требующей постоянного внимания, к тому же, проверить качество составленных кроссировочных таблиц затруднительно. Поэтому ошибки выявляются только в процессе монтажа станции или остаются необнаруженными, что значительно замедляет выполнение работ и ввод станций в эксплуатацию и ухудшает качество обслуживания абонентов.

Основные трудозатраты при составлении кроссировочных таблиц относятся к проектированию так называемых неполнодоступных кроссировочных таблиц, проектирование которых основывается на задачах анализа и синтеза равномерных неполнодоступных схем (РНС). При ручном способе построения равномерных неполнодоступных схем используются специальные таблицы заготовок. Эти таблицы дают готовый ответ только в относительно небольшой части случаев, когда РНС состоит только из цилиндров и не содержит остатка. Построение остатка производится интуитивно и в большой мере зависит от изобретательности технолога. Автоматизацию проектирования кроссировочных таблиц в значительной мере затруднило отсутствие эффективного алгоритма синтеза РНС по заданным параметрам /I, Р (где И - число нагрузочных групп, ¿1 - доступность, д' - число линий) и отсутствие формализации процесса составления кроссировочных таблиц.

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

Диссертационная работа связана с тематикой научных исследований, выполняемых в Вычислительном центре Латвийского госуниверситета им. П.Стучки, являющихся компонентой проблемы 0.80.15 (пункт 04.19): "Создать в ведущих отраслях промышленности и строительства системы автоматизированного проектирования и технологической подготовки производства (САПР) на основе применения математических методов и средств вычислительной техники координационного плана Государственного комитета Совета Министров СССР по науке и технике". Работа проводилась на основе хоздоговоров между Гипросвязью г. Москва и ВЦ ЛГУ им. П.Стучки.

Состояние вопроса. К проблемам, рассмотренным в диссертации, имеют отношение работы, посвященные следующим основным вопросам:

1) синтез PHC,

2) оценка вероятности потерь неполнодоступных схем,

3) формализация и автоматизированное проектирование кросси-ровочных таблиц.

Хотя первый патент на неполнодоступные схемы выдан уже в 1907 г. [35] , систематического математического изложения теории НС нет. Имеется только целое множество различных методов для решения отдельных задач, связанных с применением НС на практике.

Как отмечает М.А.Шнепс в [35^ , с тех пор, когда выдан первый патент на НС "не прекращаются споры о том, какие же неполнодоступные схемы являются оптимальными". Вопрос действительно является непростым, так как на практике понятие "оптимальный" совмещает противоположные требования. Согласно монографии Ю.Н. Корнышева [12^ "при построении схем неполнодоступных включений необходимо обеспечить:

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

- минимальные затраты времени при составлении и следующем практическом выполнении схемы;

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

- высокое переходное затухание между подключаемыми соединительными устройствами".

Из этих требований первое и четвертое вызывают усложнение структуры НС, а второе и третее - ее упрощение.

В целом с применением НС связаны две задачи - синтез НС и анализ НС. Под синтезом НС в общем случае понимается следующая задача: найти структуру НС с заданными параметрами: П, - число групп, d - доступность, V" - число линий, обеспечивающую выполнение поставленных требований. Нахождение оптимальных НС является основной задачей синтеза НС. Анализ НС представляет собой определение вероятностных характеристик (обычно, среднее значение пропускной способности) НС с заданной структурой при заданных условиях работы.

В начале инженерной практики синтеза НС, когда в основном применялся упорядоченный поиск свободной линии,и нагрузки были небольшими, строились так называемые оделловские НС. В оделлов- v ских НС на первых шагах поиска размещаются индивидуальные линии, потом сдвоенные и т.д., на последних шагах поиска размещаются линии, общие для всех групп нагрузки. Методика синтеза таких НС изложена, например, в монографии Берклея [з] .

Однако уже в конце 50-х и в начале 60-х годов, когда шире стал применяться случайный выбор свободной линии и нагрузки стали более значительными, в качестве оптимальных стали выступать равномерные НС. Основные принципы структуры равномерных НС были выдвинуты Н.Зллдином [39], Гельмсом и Кунтце [4l] и М.А.Шнепсом [32]. К середине 60-х годов в работах Седола и Шнепса [19] и Валенцушпш [54] определение равномерных схем приняло вид, который, в основном,стал общепринятым.

Несмотря на внешнюю простоту и ясность формулировки, задача синтеза равномерных НС оказалась весьма сложной. Только в начале 70-х годов появились первые публикации по синтезу равномерных схем. Независимо Педерсеном [49] и Смилгайсом [43] задача построения равномерной НС ставилась как некоторая задача математического программирования. Они предлагали также эвристические алгоритмы для решения этой задачи. На основе идей, изложенных в монографии Г.П.Башарина, А.Д.Харкевича и М.А.Шнепса [i] , Ю.Н.Кор-нышевым [il] и А.А.Фроловой [28] были опубликованы методы построения цилиндрической части равномерных НС с применением таблиц цилиндров. Разработкой каталогов цилиндров занимались также за границей, например, в ФРГ [Зб], М.Ферет [40] и М.Пиоро [я] • в Польше и др. М.Пиоро предложил также алгоритм построения равномерных НС из заготовок цилиндров [51] и разработал соответствующее программное обеспечение [52] . Общая задача построения равномерных НС, состоящих из цилиндров и остатка, в виде задачи математического программирования поставлена А.А.Смилгайсом [24]. Автором были разработаны также эвристические алгоритмы для решения этой задачи и соответствующее программное обеспечение [2&\ .

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

1) точное решение системы уравнений равновесия,

2) приближенные формулы,

3) статистическое моделирование.

Для точного определения пропускной способности НС решается система алгебраических уравнений равновесия, содержащая 2 уравнений. Составление системы зависит от способа поиска свободной линии. Для НС со случайным поиском свободной линии систему уравнений равновесия составил А. Эллдин [39] . Ввиду большого объема вычислений практическое применение этого метода стало возможным только после появления быстродействующих ЭВМ. Первая, автору известная публикация, в которой сообщается о возможности решения систем уравнений равновесия (для НС с принадлежит Г.Бретшнейдеру ¡53] и относится к 1965 г. Р.Шерер сообщил [бЗ] , что к 1969 г. в Штуттгартском университете имеется возможность подсчета НС для . Однако, дяя оценки пропускной способности НС в большинстве практических случаев, когда 20тг^ОО, возможностей даже современных ЭВМ, недостаточно.

Для практических целей чаще всего применяются различные приближенные формулы. Таких формул разработано очень много. Так, например, только обзорная работа А.Лотце [48] в списке литературы содержит 59 источников, предлагающих различные способы расчета НС. Дяя оценки пропускной способности равномерных НС несколько работ (А.Эллдин [39] , М.А.Шнепс [зб] и др.) предлагают использовать формулу Е1Г. Другим более известным методом является метод, предложенный А.Лотце [47] , который в нашей стране известен также под названием метода Бабицкого. В основном, методы предложены для расчета НС в узких, специальных случаях. Так, например, для НС, построенной из цилиндров, со случайным поиском, метод расчета предложил И.Г.Валенцуела [54] . Серьезных исследований по анализу НС с применением методов алгебры и математического анализа мало. Здесь следует отметить работы Я.Я.Седола и М.А.Шнепса [19, 17, 18, 34^.

Статистическое моделирование является общепринятым средством для анализа НС в более сложных случаях и для проверки новых аналитических методов. Для статистического моделирования основной проблемой является разработка удобных программных средств [7, 14].

По разработке математической теории НС автору известны работы М.Пиоро £50] и П.Доната [зв] . М.Пиоро использует средства теории множеств и комбинаторного анализа, а П.Донат - средства теории графов. Однако, много вопросов, связанных с построением РНС стандартного вида (т.е. состоящих из цилиндрической части и остатка), в этих работах не рассмотрено.

Хотя работы по созданию программного обеспечения автоматизированного проектирования кроссировочных таблиц ведутся (например, в Гипросвязь - 2, г. Ленинград), завершенных результатов по формализации и автоматизированному проектированию кроссировочных таблиц нет.

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

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

Научная новизна диссертации заключается в следующем:

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

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

• 3) разработан новый алгоритм синтеза равномерных неполно-доступных схем для произвольных значений структурных параметров /г , с!, где П, - число групп, ¿1 - доступность, у -число линий;

4) предложен и исследован новый приближенный метод расчета вероятности потерь неполнодоступных схем с потерями при случайном поиске свободной линии, учитывающий структуру НС и позволяющий сравнивать качество НС с одинаковыми значениями структурных параметров.

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

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

Реализация результатов работы. Полученные в диссертации результаты, в основном, в виде пакета прикладных программ проектирования кроссировочных таблиц, внедрены и регулярно эксплуатируются в работе ведущих проектных институтов ("Гипросвязь" г. Москва, "Гипросвязь - 2 г. Ленинград, "Гипросвязь - 3" г. Киев, "Гипросвязь - 4 г. Новосибирск) Главсвязьпроекта Министерства связи СССР. Пакет постановлением Главсвязьпроекта рекомендован для широкого внедрения во всех институтах Главсвязь-проекта при проектировании вновь строящихся АТС. Подтвержденный экономический эффект до 1983 г. составил 36 тыс. рублей.

Реализованные средства статистического моделирования систем массового обслуживания с неполнодоступными включениями включены в состав программного обеспечения системы языков программирования и моделирования СПАЛМ, разработанной в Вычислительном центре ЛГУ им. П.Стучки.

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

Основные -результаты диссертации следующие:

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

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

3. Разработан новый, удобно программируемый алгоритм синтеза равномерных неполнодоступных схем по заданным параметрам. По своим возможностям и качеству построенных схем этот алгоритм превосходит другие известные алгоритмы. С помощью этого алгоритма созданы наибольшие в мировой практике равномерные неполнодоступные схемы с параметрами 1Ъ-^8, о! =60,

П=£/8 , </= 60 , 1Г=828, для синтеза которых требуется ориентировочно 5' процессорного времени на ЕС-1055.

4. Создан пакет прикладных программ проектирования кроссировочных таблиц, позволяющий в виде готовой технологической документации получить на ЭВМ прямые (последовательные, послойные и клеточные) и неполнодоступные кроссировочные таблицы при проектировании АМТС-3, АМТС-4, АТ-ПС-ПД, различных типов городских АТС и др. Разработаны удобные дан щювкшрзвщика формы по подготовке исходных данных и технологическая схема к проектированию кроссировочных таблиц.

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

6. Реализованы макросредства статистического моделирования систем массового обслуживания с неполнодоступными схемами, включенные в программное обеспечение системы языков программирования и моделирования (СПАЛЮ, разработанное в Вычислительном центре ЛГУ им. П.Стучки.

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

Теория неполнодоступных схем излагается с единой точки зрения. В основе теории поставлено понятие матрицы инциденций неполнодоступной схемы. Так как матрицы являются удобным средством для работы на ЭВМ, такое изложение является теоретической основой для реализации на ЭВМ алгоритмов с применением НС. На основе, матрицы инциденций£ вводятся двойственные, дополнительные и симметричные НС. Рассматриваются два вида матриц связности: матрица связности групп С= (с^) ) и матрица связности линий £= С^) ¿¿Вводятся характеристики п. Л г V V- & определяющие равномерность матриц связи. Доказывается, что для одной и той же НС 0.с= .

Вводится понятие изоморфности НС. Изоморфными называются НС, отличающиеся не более чем нумерацией групп, линий и шагов поиска и перестановкой элементов в пределах абонентной группы. Доказывается, что если С/ - матрица связности групп однородной • НС /\1, а Ег - матрица связности линий двойственной неполнодос-тупной схемы Д2 , то Cf изоморфна Ег.

Вводятся понятия циклических матриц и неполнодоступные схемы специального вида - цилиндров. Цилиндром называется НС с параметрами П,, С?, &=/1 с заданной первой линией где &п (ап = /,2,.,с[) - номера групп, доступных линии , причем матрица соединения Д— (¿ = /1> П<Л) определяется соотношением: а1т = а-ат + /1 + 0(Ш/П).

Символом (/710(?П.) обозначается действие - остаток по модулю 1Ъ, в котором вместо остатка 0 принимается остаток И . Доказываются следующие свойства цилиндров:

1. Матрица инциденций цилиндра является циклической.

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

3. Для цилиндров матрицы связности групп и связности линий равны между собой.

Из рассмотренных свойств следует, что цилиндр являатся симметричной НС и что задание матриц связности цилиндров сводится к заданию вектора связи с + координатами.

Вводится понятие НС в стандартной форме. НС имеет стандартную форму, если матрица соединения А=А,: I? , где /¡^ (г = в) - цилиндры, а./? - неполнодоступная схема, в которой 7%</1 и , где - количество линий с числом доступных групп [П-о1/1Р] , 1?2 - количество линий с числом доступных групп ~]/1-о1/1Х\ .

Излагаются некоторые основные понятия одного из разделов комбинаторного анализа (теории блок-схем) и определяются их связи с понятиями неполнодоступных схем.

Выведены формулы, позволяющие на основе значений параметров И, о( и V для равномерных НС определить другие структурные характеристики РНС (в том числе для РНС, тлеющих стандартную форму).

Проведен анализ применимости существующих мер равномерности для НС: 27 (по Шнепсу) и (по Педерсену). Предлагается новая, более уточненная мера равномерности НС где: С1г - мера, учитывающая перекос,

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

Приведены примеры расчета 0. для весьма подобных неполно-доступных схем. Во всех этих примерах "более хорошие" НС имеют меньшие значения меры й .

На основе меры равномерности 0, предлагается более строгое, по сравнению с существующими, определение равномерных неполно-доступных схем (РНС). Неполнодоступная схема А с параметрами /I , с[, г? называется равномерной, если мера принимает минимальное значение.

На практике при определении равномерности НС можно пользоваться следующими необходимыми условиями равномерности:

1) число доступных групп для любых двух линий и ^ (К=2?; /,., V) отличаются не больше чем на единицу;

2) связность любых двух пар групп и

1}2Г.,П-^ 2,.,И; г^/,2,.„,-/}2Г.,п) по возможности одинакова; п п

3) суммы элементов С^ = £ С^ и = £ С.к по возможности одинаковы;

Вместо условия 2) можно пользоваться эквивалентным условием :

2а) связность любых двух пар линий и к-6. - 6 « г^-ч^ по возможности одинакова.

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

При поиске равномерной НС с заданными параметрами необходимы средства для сравнения вероятности потерь НС с одинаковыми значениями параметров /г, с/} г?, но с различной структурой. Существующие методы для этой цели мало пригодны решение системы уравнений равновесия на ЭВМ возможно лишь для числа линий г^ • известные аналитические приближенные формулы структуру НС не учитывают вообще; статистическое моделирование не обеспечивает необходимое различие НС с похожей структурой).

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

В основе метода лежит известная формула Башарина-Лонглея-Бенеша, в которой предлагается при определении условных вероятностей потерь (г = О, f,.t1r) при £ занятых линиях использовать модель размножения - гибели с состоянием, приблизительно отображающей функционирование НС. В ¿-ое "макросостояние" модели объединяются все состояния НС с ъ занятыми линиями. Чтобы избежать экспоненциальную сложность такого объединения, некоторые состояния НС считаются эквивалентными и рассматриваются как одно состояние. Два состояния НС предлагается считать эквивалентными, если выполняются следующие условия:

1) число занятых по всем встречаемым числам доступных групп линий для обоих состояний совпадают;

2) совпадают (с точностью до порядка координат) векторы занятия групп.

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

I) предложенный метод позволяет более точно подсчитать вероятности потерь для НС при случайном поиске свободной линии и позволяет сравнивать по качеству НС различной структуры, но с одинаковыми значениями параметров;

2) подтверждается предположение М.А.Шнепса, что потери дяя РНС можно рассчитывать по

Третья глава посвящена вопросам синтеза равномерных непол-нодоступных схем. Задача синтеза равномерных НС ставится в виде " следующей задачи целочисленного нелинейного программирования: пусть заданы значения параметров И, с/, 2У и пусть /¿^ (г=/,2,.,/г; /с= независимые булевые переменные. Необходимо минимизировать значение целевой функции @ , при 'условии, что

Сг = л).

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

Проведено описание и анализ существующих методов синтеза равномерных НС. Рассмотрены следующие алгоритмы: построение равномерных НС методом Монте-Карло (предложенный О.Я.Строевым и В.И.Якименко [27]), алгоритм Педереена [49]), составление цилиндрической части по заготовкам цилиндров из специального альбома цилиндров (развитые Ю.Н.Корнышевым [I, 4, б] и алгоритм Пиоро [50] .

Предлагается новый алгоритм синтеза равномерных НС в стандартной форме. Алгоритм состоит из трех частей: сначала несколько модифицированным методом ветвей и границ строится цилиндрическая часть, потом к цилиндрической части присоединяется некоторый остаток и в конце происходит (в случае необходимости) попытка усовершенствования остатка.

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

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

Так как построение равномерной цилиндрической части является задачей целочисленного программирования с квадратичной целевой функцией, то для нахождения глобального экстремума необходимо, по возможности, скорее попасть в достаточно небольшую окрестность этого экстремума. С этой целью основное условие устанавливающее признать ли частичное решение пригодным для продолжения поиска, сделано переменным. В начальном этапе построения цилиндрической части условие является жестким, сразу отбрасывающим подозрительные ветви. На этом этапе условие требует, чтобы частичное решение порождало равномерную НС. Как показала практика применения, в большинстве случаев равномерная цилиндрическая часть строится (в 90% случаев)без единого возврата. Если РНС построить сразу не удается, устанавливается Р=Д , где Р> - условие, которое исключает пропуск решения, выдающего равномерную цилиндрическую часть.

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

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

Формализация процесса проектирования кроссировочных таблиц состоит из трех разделов - описания кроссируемого оборудования и промщитов, описания закона кроссировки и описания расшивки оборудования на цромщитах.

Для описания кроссируемого оборудования вводится некоторое множество точек а е А , где множество А называется множеством оборудования, если на нем определены три функции р)координаты элемента ^ (сс) —р — название элемента ос, а.) = /К - номер элемента сс, где ос , ^ , Ж - натуральные числа,р - слово ограниченной длины в некотором фиксированном алфавите. Функции £ (сс) 'И £ (а) используются для описания кроссируемого оборудования в исходных данных, ^ (сс) используется для установления взаимного соответствия между кроссируемыми комплектами.

Основными понятиями, с помощью которых технолог описывает кроссируемое оборудование, являются понятия звена и прямоугольника. Звеном /Р Р / называется такое подмножество // сс1г я} с к, для которого £ (а.<) = Р, £ = и где 1 =/, ; К-1', Р'ъ Р" - два допустимых значения для ^ («у. Прямоугольником //Р 'Р "Ц называется множество элементов а — (ос,у.) е А такое, что сс е //р'р"// тогда и только тогда, когда ^ ^ ОС и 7 ^ ^ ^ ^ где ¿г и <2 - два элемента из /I , для которых

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

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

Л* А"

Пусть заданы два множества А ил кроссировочных комплектов. Собственно под кроссировкой понимается установление взаимнооднозначного соответствия между элементами ¿¿¿е А' и подмножествами А^ £ А где V - заданный параметр. Если тах1А'11=1, кроссировка является прямой, если же /пссх/А'^/ крос-сировка является неполнодоступной. При прямой кроссировке в соответствие ставятся комплекты а/еА' и ос "е- Адля которых ее) = / '(а"). Вводятся часто употребляемые функции нумерации ' 3 '3 для основных видов прямой кроссировки: последовательной, послойной и клеточной. Для неполнодоступных кроссировок необходимо представить список -подмножеств лг". Представление этого списка и разбиение множества А " на подмножества А ^ происходит с помощью алгоритма синтеза равномерных неполнодоступных схем, описание которого содержится в главе 3.

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

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

I. ОСНОВЫ ТЕОРИИ НШОЛНОДОСТУПНЫХ СХЕМ.

Заключение

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

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

Исследованы существующие алгоритмы синтеза равномерных неполнодоступных схем и показана необходимость создания алгоритма синтеза равномерных неполнодоступных схем в стандартной форме (т.е., состоящих из цилиндрической части и остатка) для произвольных значений параметров ^ гг (где^-число нагрузочных групп, сС - доступность,чГ- число линий). Такой алгоритм разработан и реализован на ЭШ. Цилиндрическая часть неполнодоступной схемы строится на основе модифицированного метода ветвей и границ. Остаток строится с помощью специального, эвристического алгоритма.

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

Формализован процесс проектирования кроссировочных таблиц и создано программное обеспечение в виде пакета прикладных программ для автоматизированного проектирования кроссировочных таблиц. Пакет выдает прямые (последовательные, послойные и клеточные) и неполнодоступные кроссировочные таблицы в виде готовой технологической документации. Пакет широко применяется в проектных институтах Главсвязьпроекта.

1. Башарин Г.П., Харкевич Л.Д., Шнепс М.А. Массовое обслуживание в телефонии.- М.: -Наука,"1968. 246 с.

2. Бенеш В.Е. Математические основы теории телефонных сообщений.-М.: Связь, 1968. .

3. Берклей Г.С. Основы группообразования и расчета оборудования АТС английских систем.- М.: Связьиздат, 1952.

4. Инструкция по расчету нагрузок и объема оборудования сельских координатных АТС.- М.: Радио и связь, 1983. 88 с.

5. Инструкция "Расчет оборудования АТС-54А и построение кросси-ровочных схем для декадно-шаговых и координатных АТС И-028-71".- М.: Гипросвязь, 1971. 121 с.

6. Ионин Г.Л. Теория телетрафика.- Рига: Издательство Рижского политехнического института, 1975. 182 с.

7. Ионин Г.Л., Седол Я.Я. Статистическое моделирование систем телетрафика. М.: Радио и связь, 1982. — 184 с.

8. Йодан Э. Структурное программирование и конструирование программ.- М.: Мир, 1979.- 415 с.

9. Копп М.Ф., Корнышев Ю.Н., Шилов О.С. Проектирование координатных АТС.- Одесса: Одесский электротехнический институт связи им. А.С.Попова, 1971. 91 с.

10. Корнышев Ю.Н. Оптимизация проектных решений для сельских телефонных сетей. М. Радио и связь, 1983. - 135 с.- i^B

11. Корнышев Ю.Н. Построение схем равномерных неполнодоступных включений.- Электросвязь, 1971, № 7, с. 35 45.

12. Корнышев Ю.Н., Коханова З.С. Проектирование городских координатных автоматических телефонных станций.- М. : Связь, 1975.182 с.

13. Линтер Р., Миллс X., Уитт Б. Теория и практика структурного программирования.- М. : Мир, 1979.- 406с.

14. Метод статистических испытаний (Метод Монте-Карло)/ Буслен-ко Н.П., Голенко Д.И., Соболь И.М. и др.- М. : Физматгиз, 1962.

15. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика.- М.: Мир, 1982. 476 с.

16. Седол Я.Я. Алгебраические методы расчета неполнодоступных схем.- В кн.: Латвийский математический ежегодник № 2. Рига: Зинатне, 1966, с. 299 319.

17. Седол Я.Я. Исследования неполнодоступных схем при больших нагрузках.- В кн. : Латвийский математический ежегодник № 6. Рига: Зинатне, 1969, с. 165 185.

18. Седол Я.Я., Шнепс М.А. Некоторые качественные исследования неполнодоступных схем.- Проблемы передачи информации, 1965,том I, вып. 2, с. 87 94.

19. Смилгайс A.A. О возможности построения оптимальных неполно-доступных схем методом целочисленного программирования с параболическими ограничениями,- В кн.: Латвийский математический ежегодник № 24. Рига: Зинатне, 1980, с. 247 249.

20. Смилгайс A.A. Проектирование и распечатка кроссировочных таблиц с помощью ЭВМ.- В кн.: ХНУ Всесоюзная научная сессия, посвященная Дню радио, М.: НТОРЭС им. А.С.Попова, 1980, с.109.

21. Смилгайс A.A. Составление прямых кроссировочных таблиц с помощью ЭВМ.- В кн.: Методы и структуры систем телетрафика, М.: Наука, 1979, с. 176 183.

22. Смилгайс A.A. О пропускной способности неполнодоступных схем.- В кн.: Информационные сети и автоматическая коммутация (ВСИС-4), М.: Наука, 1981, с. 97 98.

23. Смилгайс A.A. Приближенный метод оценки потерь неполнодоступных схем.- В кн.: IX Научно-техническая конференция, посвященная Дню радио, М.: НТОРЭС им. А.С.Попова, Московское городское правление, 1983, с. 91 92.

24. Смилгайс A.A. Пакет прикладных программ проектирования кроссировочных таблиц. Программная документация.- Рига: Государственный фонд алгоритмов и программ, 1983, 259 с.

25. Строев О.Я., Якименко В.И. Синтез равномерных неполнодоступ-яых схем на ЭВМ.- В кн.: Всесоюзное совещание по информационным сетям "Информационные сети и автоматическая коммутация", М.: Наука, 1981, с. 72 73.

26. Фролова A.A. К вопросу о построении неполнодоступных включений.- В кн.: Сборник научных трудов Центрального научно-исследовательского института связи, вып.4, М.: ЦНИИС, 1971,с. 19 30.

27. Холл М. Комбинаторика.- М.: Мир, 1970

28. Ху Т. Целочисленное программирование и потоки в сетях.- М.: Мир, 1974. 519 с.

29. Широкова С.А. Еяок-схемы.- Успехи математических наук, том XXIII, вып. 5 (143), 1968, с. 51 98.

30. Шнепс М.А. Новые принципы выбора оптимальной неполнодоступ-ной схемы.- Электросвязь, 1963, № 7, с. 40 46.

31. Шнепс М.А. Численные методы теории телетрафика.- М.: Связь, 1974.- 232 с.

32. Шнепс М.А. Теорема об оптимальных неполнодоступных схемах при предельно малой интенсивности нагрузки.- Проблемы передачи информации, 1975, том XI, вып. 3, с. 73-80.

33. Шнепс М.А. Системы распределения информации. Методы расчета.-М.: Связь, 1979.- 342 с.

34. Bazlen D. The Dimensioning of Trunk Groups for Standard Gradings of the German GPO in Case of Finite Number of Traffic Sources.- Nachrichtentechnisehe Zeitschrift, 1972 Heft 1 p. 50-52.

35. Benes v.b. Markov Processes Representing Traffic in Connecting Networks. Bell System. Techn.Y., 1963 42.6., p.2765-2838.

36. Donath P. A New Graph and Matrix Method for Designing Graded Switsching Stages.- Telecommunication Review Budavox, Budapest, 1979, N 4 p.1-12.

37. Elldin A. Further Studies on Gradings with Random Hunting.-Ericsson Technics, Stockholm, 1957. N 2, p.175-257.

38. Feret M. Catalog of homogeneous cyclic gradings of availability 10.- Informator projektanta lacznosci dodatek, Warszawa, 1975, N 2-3, p.1-34.

39. Helms, Kuntze Erhöhung der Leistungsfähigkeit unvollkommenen Bündel durch homogene Mischungen.- Mitteilung aus dem Post und Fernmeldewesungen, I960 Ii 2.

40. Herzog U., Lotze A., Schehrer R. Calculation of Trunk Groups for simplified gradings.- Nachrichtentechnisehe Zeitung, 1969. N 12, p.684-689.

41. Jonin G.L., Sedol J.J., Smilgais A.A. Design of Optimal Gradings:- Symposium on Computer Communications Networks and Teletraffic, New-York, 1972 p.295-299.

42. Jacobäus C. A Study an Congestion in Link Systems.- Ericsson Technics N 48, Stockholm, 1950.

43. Kindler E. Classification of Simulation Programming Languages.- Elektronische Informations-Verarbeitung und Kybernetik, 1978 N 11.

44. Longley K. The Efficiency of Gradings.- Post off Elect. Engrs Journal. 1948.

45. Lotze A. Verluste und Gütemerkmale einstufiger Mischungen.-Nachrichtentechnische Zeitung, 1961 Ii 8, p.449-453«

46. Lotze A. History and Development of Gradings Theory. Archiv; für Elektronik und Übertragungstechnik, Band 25, Heft 9/10, Stuttgart, 1971, p.402-410.

47. Pedersen C.A. Algorithms for Constructing Ideal Gradings for Nonhoming Selectors (An Application of the Theory of Block Designs)IEEE Transactions on Communication Technology vol.com.- 19, N 2, 1971 April, p.101-112.

48. Pioro M.P. Combinatorial foundations of the theory of optimal homogeneous gradings.- Archiv/um Elektrotechniki torn 5rXY zeszut 95, Warszawa, 1976 Ii 1, p.53-64.

49. Pioro M.P. Konfiguracje cykliczne i ich zastosov/anie do projektowania pol homogenicznych.- Referaty Instytutat elekomunikacji politechniki Warszav/skiej , 1976, zeszyt 15-36 p.

50. Pioro M.P. Zastosowanie konfiguracji cyklicznych do projek-towania pol homogenicznych. Referaty Instytuta telekomu-nikacji politechniki Warszawskiej. 1978, zeszyt 55-20 p.M

51. Schehrer R. Uber die exakte Berechnung von Uberlaufsystemen der Wählvermittlungstechnik.- Institut für Nachrichtenvermittlung und Datenverarbeitung, Universität Stuttgart.,

52. Bericht über verkehrstheoretische Arbeiten, 1969 -122 p.

53. Valenzuela J.G. Study of Certain Tupes of Cyclic Gradings for Random Hunting.- Reprint from Ericsson technics N 1, 1965, p.111-184.