автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Пространственное размещение коммуникационных систем с использованием модернизированного кластерного и градиентного методов

Введение.

Глава 1. Направления и проблемы системного анализа в области оценки эффективности и прогнозирования развития структур систем.

1.1. Обзор методов системного анализа физического пространства.

1.2. Классификация и выбор коммуникационных систем.

1.3. Обзор методов системного анализа коммуникационных систем.

1.4. Обоснование актуальности разработки универсальных методов системного анализа физического пространства для размещения технических систем.;.

1.5. Обоснование актуальности разработки универсальных методов размещения технических систем.

1.6. Выводы. h

Глава 2. Модернизированный метод кластерного анализа пространства,.

2.1. Влияние физического пространства на размещение технических систем.

2.1.2. Использование различных функций распределения/матриц.

2.2. Формализация физического пространства.

2.2.1 Формирование исходной матрицы пространства,.

2.2.1. Формирование стоимостной матрицы пространства.

2.2.2. Формирование сокращенной матрицы пространства.

2.3. Модернизация кластерного метода.

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

2.3.2. Формирование матрицы локальных областей.

2.3.3. Выделение специализированных областей Выводы,.

Глава 3. Модернизированный градиентный метод размещения технических систем.

3.1. Первичное размещение оконечных элементов коммуникационной системы.

3.2. Коррекция расположения элементов коммуникационной системы.

3.3. Модернизация градиентного метода для размещения центрального элемента коммуникационной системы.

3.4. Алгоритм трассировки функциональных связей коммуникационной системы.

3.5. Выводы.

Глава 4. Практическая реализация модернизированного кластерного метода анализа пространства.

4.1. Генератор случайных областей.

4.2. Развертка границ областей.

4.3. Анализ развертки границ областей.

4.4 Выводы.

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

5.1. Функциональная схема взаимосвязей блоков программного обеспечения.

5.2. Блок ввода исходных данных.

5.3. Блок построения физического пространства на основе модифицированного кластерного метода.

5.4. Блок визуального отображения физического пространства и кабельных трасс.

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

5.6. Блок формирования технической документации структурированной кабельной системы.

5.7. Блок анализа построенной структурированной кабельной системы и поиска компонентов.

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

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

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

5.11. Формализованное описание структурированной кабельной системы как коммуникационной системы с централизованной структурой.

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

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

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

5.15. Выводы.

За последние десятилетия технические коммуникационные системы быстро развиваются и усложняются. Анализ их структуры и функционирования предполагает применение системного подхода. В настоящее время одной из проблем является узкая специализация по прикладным областям методов, позволяющих анализировать и оценивать эффективность размещения коммуникационных систем в физическом пространстве по выбранным критериям, например, по экономическому. Это объясняется отсутствием универсальных методов выделения, идентификации и классификации областей физической среды (физического пространства) в которой размещается техническая система. Для конструктивного решения этой проблемы необходимо разработать: способ классификации областей физического пространства, в котором размещается коммуникационная система и метод анализа и идентификации таких областей; метод, позволяющий эффективно размещать в физическом пространстве элементы коммуникационной системы и допускающий при этом его применения для широкого круга прикладных задач.

Эффективный анализ физического пространства, направленный на распознавание и выделение объектов, проводят кластерные методы. Наиболее интересная и полная работа была представлена Губерманом Ш. Предложенные им алгоритм нелокального выделения объектов и кластерный метод [1] используются как основополагающие в этом направлении. Эти методы позволяют эффективно выделять в пространстве области по признаку однородности, но они лишь обозначают их границы и не дают им качественной оценки. Поэтому невозможно оценить эффективность использования выделенной области пространства для размещения в них элементов коммуникационных систем, обладающих различным структурным строением - централизованным, сетевым, скелетным [2].

Использование кластерного метода для идентификации областей пространства в соответствии с некоторой классификацией возможно после его модернизации. Следует провести дополнительный анализ выделенной области и на основе результатов соотнести исследуемую область с классифицированными областями. Это первая наиболее актуальная задача, решение которой необходимо для эффективного размещения коммуникационных систем в пространстве. В этом направлении проведено много работ, и, в частности, О.Н. Родзиной[3]. Однако предлагаемые методы, как и другие, близкие по решаемой задаче методы распознавания текстов (метод масок, метод нейронных сетей) в данном случае не применимы. Количество обрабатываемых ими образов строго конечно. Задача анализа пространства при размещении коммуникационных систем не накладывает таких ограничений. Системный анализ в данном случае применяется для получения приближенного общего описания свойств объекта (области пространства).

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

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

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

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

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

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

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

Модернизированный градиентный метод поиска локального экстремума нелинейной функции

Технология пространственного размещения элементов коммуникационной системы на основе модернизированного градиентного метода.

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

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

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

Разработанный ПМК прошел успешную апробацию в практической задачи проектирования СКС в департаменте проектирования компании Advanced Electronic Support Products, Inc.

Основные положения диссертации опубликованы в работах:

1. Чернышов М.А., Дарчиашвили В.В., «Оптимизация структуры СКС». Материалы научно-технической конференции «Новые информационные технологии», МГАПИ, Москва, 2000., Стр.123.

2. Чернышов М.А., «Простейший метод анализа пространства, предназначенного для размещения инженерных систем». Объединенный научный журнал N26. Издательство "ТЕЗАРУС", Москва, 2002., Стр. 38-39.

3. Чернышов М.А., «Поиск тупиковых направлений в пространстве, предназначенном для размещения инженерных систем». Объединенный научный журнал N26. Издательство "ТЕЗАРУС", Москва, 2002., Стр. 40-41.

4. Чернышов М.А., «Автоматизированное проектирование структурированных кабельных систем». Объединенный научный журнал N11. Издательство "ТЕЗАРУС", Москва, 2002., Стр. 44-46

5. Чернышов М.А., «Исследование функционала методами нелинейного программирования». Объединенный научный журнал N11. Издательство "ТЕЗАРУС", Москва, 2002., Стр. 46-49.

6. Чернышов М.А., «Локализация пространства, предназначенного для размещения инженерных систем». Объединенный научный журнал N26. Издательство "ТЕЗАРУС", Москва, 2002., Стр. 41-43.

7. Чернышов М.А. N26, «Оптимизация экономического анализа пространства, предназначенного для размещения коммуникационных систем», Москва, 2002., Стр. 39-40

В качестве теста для проверки производительности предложенной технологии пространственного размещения коммуникационных систем, было проведено сравнение быстродействия и корректности работы двух программных пакетов. Первый реализовывал предложенные в диссертационной работе методы. Второй - уже известный ранее волновой метод трассировки. Оба пакета решали идентичные задачи трассировки печатных плат. Структура печатной платы формализуется в соответствии с технологией пространственного размещения коммуникационных систем аналогично СКС и представляется в виде множества независимых централизованных проводниковых коммуникационных систем. На вход программам подавались 10 карт БИС, генерированных случайным образом. Временные затраты на решение задач и суммарные длины предложенных проводниковых соединений приведены в таблице 1:

Волновой метод Пространственное размещение на базе модернизированного градиентного метода

Время Длина соединений Время без кластерного анализа Время с кластерным анализом Длина Соединений

Задача 1 0.2 с(+ 0.2 с) 1009 0.3 с(+ 0.3 с) 0.3 с(+ 0.3 с) 1040

Задача 2 0.3 с(+ 0.1 с) 302 0.4 с(+- 0.1 с) 0.4 с(+ 0.1 с) 305

Задача 3 0.4 с(+ 0.1 с) 565 0.6 с(+ 0.2 с) 0.7 с(+ 0.3 с) 541

Задача 4 0.6 с(+ 0.2 с) 918 0.9 с(+ 0.3 с) 1.0 с(+ 0.3 с) 932

Задача 5 0.8 с(+ 0.2 с) 1142 1.2 с(+ 0.3 с) 1.3 с(+ 0.3 с) 1103

Задача 6 1.1 с(+ 0.3 с) 1490 1.7 с(+ 0.5 с) 1.9 с(+ 0.6 с) 1522

Задача 7 1.2 с(+ 0.1 с) 499 1.9 с(+ 0.2 с) 2.1 с(+ 0.2 с) 478

Задача 8 1.3 с(+ 0.1 с) 411 2.1 с(+ 0.2 с) 2.3 с(+ 0.2 с) 404

Задача 9 1.5 с(+ 0.2 с) 873 2.4 с(+ 0.3 с) 2.7 с(+ 0.4 с) 834

Задача 10 1.7 с(+ 0.2 с) 984 2.7 с(+ 0.3 с) 3.0 с(+ 0.3 с) 1036

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

1. Губерман Ш. А. Неформальный анализ данных в геологии и геофизике. М.: Недра, 1987.

2. Ольга Н. Родзина. Методы, модели и технология рзработки нечетких кластерных анализаторов для классификации и распознавания графических образов. Отечественный теоретический и научно-методический журнал N3, 2002.

3. Уидроу Б., Стирнз С. "Адаптивная обработка сигналов" М.: Радио и связь, 1998.

4. Фомин В.Н. "Математическая теория обучаемых опознающих систем" Л.: Изд-во ЛГУ, 1976.

5. Мандель И.Д. Кластерный анализ. М.: Финансы и статистика, 1988.

6. Функционально-стоимостный анализ в электротехнике/ Под ред. М.Г. Карпунина. М.: Энергоатомиздат, 1984.

7. Проблемы построения и обучения нейронных сетей / под ред. А.И.Галушкина и В.А.Шахнова. М. Изд-во Машиностроение. 1999.

8. А. А.Н.Горбань, Д.А.Россиев Нейронные сети на персональном компьютере. Новосибирск: Наука. Сибирская издательская фирма РАН, 1996.

9. Дуда Р., Харт П. "Распознование образов и анализ сцен" М., Мир, 1976.

10. Лиховидов В.Н. "Практический курс распознавания образов" -Владивосток, Изд-во ДВГУ, 1983.

11. Ильин В.Н. Основы автоматизации схемотехнического проектирования. М.: Энергия, 1979.

12. Норенков И. П. Введение в автоматизированное проектирование технических устройств и систем. М., 1986.13