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

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

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

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

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

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

Решению таких задач посвящены работы Анисимова Б. В., Калниболотского Ю. М., Петренко А. И., Сигорского В. П., Пухова Г. Е.Дро-хименко Я.К., Белова Б. И., Норенкова И. П., Нагорного Л. Я., tonна В.Н., Гуревича И. В., Ланнэ A.A., Бондаренко В. М., Хасайова П. Ф., Королева Ю. В., Юрина О. Н., Баталова Б. В., Казеннова Г. Г., Абрайтиса Л. Б., Мелихова А. Н., Матюхина H.a., Кабулова В. К., Глу-шковаВ.М., Брюнина В. Н., Лазарева В. Г., Поспелова Д. А., Сифорова В. И., Толчан А. Й., Рогинского В. Н., Давыдова Г. Б., Харкевича А. Д., Бусленко М. П., Журавлева Ю. П., Ченцова В. М. и многих других авторов.

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

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

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

В диссертации ставятся и решаются следующие задачи:

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

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

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

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

Научные положения и результаты, выносимые на защиту:

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

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

3. Предложены методы и алгоритмы топологического анализа информационных сетей, цепей и РЭС, оперирующие непосредственно массивами данных об объекте.

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

5. Составлены алгоритмы определения всевозможных маршрутов между оконечными узлами ИС, множества маршрутов, проходящих через заданную линию связи, и построения минимальной по стоимости линий связи структуры ИС типа «дерева» .

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

Практическая значимость работы проявляется в возможности совершенствования известных и разработки новых инженерных методов анализа, цреобразования цепей РЭС и ИД, моделирования ИС и надежности Функционирования РЭС с неисправностями.

Научные результаты диссертационной работы наши црактическое применение в научно-исследовательских работах, проводимых в ТашПИ им. Абу Райхана Берунй, й внедрены в «лектромеханическом заводе г. Ташкента.

Результаты диссертации доложены на: Республиканской научно-технической конференции «Автоматизация с применением электротехнических устройств и автоматизированное управление производственными процессами в отраслях народного хозяйства» (г.Ташкент, 1978) — Республиканской конференции молодых ученых и специалистов (г.Самарканд, 1978) — Республиканской научно-технической конференции молодых ученых и специалистов, посвященной 50-летию ТашПИ (г.Ташкент, 1980) — П Всесоюзной межвузовской научно-технической конференции «Математическое, алгоритмическое и техническое обеспечение АСУ ТП» — П Всесоюзном семинаре «Методы синтеза и планирования развития структур сложных систем» (г.Ташкент, 1981) — Ш Всесоюзном совещании «Методы и программы решения оптимизационных задач на графах и сетях» (гг.Ташкент, Новосибирск, 1984) — ежегодных научно-технических конференциях профессорско-преподавательского состава ТашПИ (г.Ташкент, 1977;1984).

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

Выводы По четвертой главе.

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

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

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

4. Моделирование функциональной надежности РЭС реализован на основе методики определения всевозможных путей с помощью Г-обра-зований. Использованная система аналогий между параметрами, понятиями и законов информационных цепей и цепей РЭС позволяет применять разработанную алгебру и аппарат Д-определителей для анализа, преобразования информационных цепей.

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

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

— 168 -ЗАКЛЮЧЕНИЕ.

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

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

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

2. 1У! бдель информационных сетей и цепей, их элементов — радиоэлектронных схем и структур, графов в виде структурных образований содержит в себе необходимую инфэрмацию одновременно как о топологии их, так и о параметрах, режимах (или состояниях) их в виде упорядоченных структур данных. Такая модель вместе с полной системой операций над ней (операциями алгебры структурных образований), алгоритмами и методами может служить удобным аппаратом в арсенале исследователей — разработчиков теоретических и практических вопросов ИС, ИЦ и цепей РЭС, графов других систем. Предло женные алгоритмы выполнения операций алгебры структурных образований, алгоритмы вычисления Д-определителей их являются ориентированными на ЭВМ.

3. Структурные образования в зависимости от типа моделируемого объекта и решаемых топологических задач условно делятся на два вида: Д-образования и Г-образования. Аппарат Д-образова-ния более ориентирован для решения задач, связанных с поиском деревьев, а аппарат Г-образований — для решений топологических задач, сводящихся к поиску путей.

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

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

6. Предложенные алгоритмы выделения всевозможных маршрутов между оконечными узлами ИС, алгоритм определения множества всех маршрутов, проходящих через заданную линию связи ИС, реализованы на основе <|ункционаяьно-условной записи ГО. Они отличаются от известных матричных методов тем, что не требуется применение упорядочения процедур поиска путей для исключения поглощаемых елагаемых. Алгоритм построения оптимальной структуры ИС использует критерий минимальной стоимости линий связи. Моделирование функциональной надежности РЭС реализован на основе методики определения всевозможных путей с помощью Г-образований и позволяет уменьшить время моделирования.

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

Годовой экономический эффект от внедрения результатов исследований составил 17,3 тысяч рублей.

— 171.