Содержание к диссертации
Введение
Глава 1 Анализ программ контроля и управления распределёнными объектами 11
1.1 Функциональные возможности информационных систем 11
1.2 Сравнительный анализ геоинформационных систем 14
1.3 Организация моделирования в геоинформационных системах 19
1.4 Региональные геоинформационные системы 22
1.5 Анализ свойств объекта исследования 26
1.6 Надёжность энергетических сетей 33
1.7 Выводы 37
Глава 2 Разработка и анализ алгоритмов планирования восстановления территориально распределённых систем 39
2.1 Организация моделирования территориально протяжённых объектов 39
2.2 Разработка модели энергетической сети 47
2.3 Разработка алгоритмов определения порядка восстановления ЛЭП 50
2.4 Адаптация алгоритма разложения графа в ширину применительно к модели энергосистемы 62
2.5 Алгоритм определения порядка восстановления некритических неисправностей 65
2.6 Выводы 69
Глава 3 Разработка модуля принятия решений для геоинформационных систем с учётом требований по надёжности 70
3.1 Анализ различных топологических вариантов распределённых сетей 71
3.1.1 Последовательные системы 72
3.1.2 Параллельные системы 75
3.2 Количественные оценки структурных характеристик сетей 77
3.3 Особенности построения сетевых структур повышенной надёжности 79
3.4 Разработка алгоритмов для организации модуля анализа сетевых структур 80
3.5 Выводы 102
Глава 4 Программное расширение Arcgraf 104
4.1 Состав программы 106
4.2 Модуль активации всех тем (active) 108
4.3 Модуль обнуления неисправностей таблиц (obnul) 109
4.4 Модуль ввода неисправностей помеченных вершин в активной теме (neispr) 110
4.5 Модуль номеров опор на текущей теме (graf) 110
4.6 Модуль программы расчёта (glav ras graf) 111
4.7 Порядок работы с расширением ARCGRAF 118
4.8 Оценка сложности и быстродействия алгоритмов поиска кратчайших путей 127
4.9 Выводы 134
Заключение 136
Литература 138
- Организация моделирования в геоинформационных системах
- Адаптация алгоритма разложения графа в ширину применительно к модели энергосистемы
- Разработка алгоритмов для организации модуля анализа сетевых структур
- Оценка сложности и быстродействия алгоритмов поиска кратчайших путей
Введение к работе
В экономически развитых странах существует разветвлённая инфраструктура коммуникаций, которая включает в себя линии электропередач (ЛЭП), газопроводы, нефтепроводы, линии телефонной и телеграфной связи и т.д. Такие территориально протяжённые системы практически никогда не находятся в состоянии полной работоспособности. Например, на работу энергетических сетей оказывают влияние различные факторы: нагрузка потребителей, износ оборудования, метеоусловия (температура, повышенная влажность, ветер, обледенение, дым), сейсмология (подвижка грунтов, землетрясения), биологические (растительность и животные), человеческие и др.
При проведении работ по устранению локальных аварий используются информационно-управляющие системы и системы моделирования отдельных узлов и агрегатов.
В настоящее время всё больше внимания уделяется проблемам защиты и прогнозирования восстановления объектов после катастроф и стихийных бедствий. Однако в катастрофических и посткатастрофических ситуациях существующие информационно-управляющие системы не обеспечивают эффективного анализа и управления территориально распределёнными объектами. Существующие системы ориентированы на решение задач восстановления в одной узкоспециализированной области техники и не удовлетворяют требованиям наглядности и полноты управления.
В научно-технической литературе не достаточно полно рассмотрены проблемы обеспечения устойчивого (надёжного) функционирования и восстановления территориально протяжённых систем после множественных аварий. В то же время, следует
6 отметить появление публикаций, посвященных решению этих проблем с использованием геоинформационных систем (ГИС). ГИС позволяют получать и анализировать информацию как о системе в целом, так и об отдельных её компонентах с учётом природных, погодных, географических и других факторов. Кроме того, они обладают большими потенциальными возможностями при планировании порядка восстановления систем после множественных аварий в посткатастрофических ситуациях. Однако при проведении восстановительных работ в территориально распределённых системах, геоинформационные технологии не используются в должной мере для координации и управления. ГИС служат для удобного представления хранимой информации. В то же время проведённый анализ показывает, что интеграция в ГИС сведений о рельефе местности и параметрах распределённых объектов может быть эффективно использована при создании программных модулей поддержки принятия решений в посткатастрофических ситуациях. При этом должны быть решены задачи разработки способа взаимодействия ГИС с модулем поддержки принятия решений и создания универсального интерфейса, позволяющего использовать функции модуля в различных предметных областях.
Целью работы является совершенствование математического и программного обеспечения систем поддержки принятия решений в посткатастрофических ситуациях по организации восстановления сложно структурированных территориально протяжённых систем на основе геоинформационных технологий.
Для достижения поставленной цели решаются следующие задачи: разработка способа формализованного описания территориально распределённых систем для решения задач управления восстановлением с учётом форматов представления информации в базах данных геоинформационных систем; разработка и анализ алгоритмов планирования восстановления территориально распределённых систем для реализации процедур поддержки принятия решений с применением геоинформационных технологий; разработка математического обеспечения модуля анализа территориально распределённых систем, находящихся в состоянии частичной работоспособности, с учётом характеристик надёжности; разработка способа расширения функциональных возможностей геоинформационных систем на основе современных технологий проектирования программ.
Методологической основой работы является использование методов теории графов, математического и имитационного моделирования, дискретной математики, теории надёжности и проектирования информационных систем, искусственного интеллекта и методов анализа алгоритмов.
Научная новизна диссертационной работы состоит в следующем:
Предложены классификация и способ построения моделей территориально распределённых систем. В отличие от известных, способ позволяет осуществлять построение и эквивалентные преобразования моделей с учётом организации баз данных геоинформационных систем.
Разработан метод планирования восстановления сетевых структур, который, в отличие от известных, позволяет на основе геоинформационных технологий сократить время принятия решений и повысить качество управления процессом устранения множественной аварии.
Разработаны алгоритмы планирования восстановления сетевой структуры, которые в отличие от известных позволяют учесть как весовые коэффициенты неисправностей, так и приоритеты восстановления сети.
Предложены новые количественные оценки состояния сетевых структур с учётом характеристик надёжности, предназначенные для использования в системах поддержки принятия решений.
Достоверность полученных результатов подтверждена использованием предложенных алгоритмов при разработке и тестировании программы получения маршрутных карт восстановления территориально протяжённых систем. Для предлагаемых в работе алгоритмов приводится обоснование их сходимости и сравнительная оценка вычислительной сложности.
На защиту выносятся результаты разработки систем анализа и управления восстановлением протяженных сетевых структур, в том числе: способ формализованного описания территориально протяженных систем с учётом форматов представления данных в геоинформационной системе Arc View; алгоритмы решения задачи определения приоритетного порядка восстановления территориально протяжённых систем на основе предложенной модели с использованием геоинформационных технологий; способ количественной оценки структурных характеристик территориально протяжённых систем, позволяющий выбрать структуру, отличающуюся лучшими характеристиками надёжности в состоянии частичной неработоспособности; математическое, алгоритмическое и программное обеспечение функциональных подсистем, реализуемых в составе геоинформационной системы на основе технологии динамически подключаемых библиотек (dll).
Публикации. По теме диссертации опубликовано 12 печатных работ, в том числе 9 статей и 3 тезиса докладов.
Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на I Всероссийской научно-технической конференции «Компьютерные технологии в науке, проектировании и производстве» (г. Нижний Новгород, 1999 г.); II Всероссийской научно-технической конференции «Компьютерные технологии в науке, проектировании и производстве» (г. Нижний Новгород, 2000 г.); IV Международной научно-технической конференции «Новые информационные технологии и системы» (г. Пенза, 2000 г.); Всероссийской научно-практической конференции «Электромагнитная совместимость (ЭМС) и безопасность при эксплуатации мобильных средств связи, телекоммуникаций и компьютерной техники» (г. Пенза, 2001 г.); Всероссийской научно-технической конференции «Методы и средства измерения в системах контроля и управления» (г. Пенза, 2001 г.); Межрегиональном постоянно действующем научно-техническом семинаре «Экологическая безопасность регионов России и риск от техногенных аварий и катастроф» (г. Пенза, 2001 г.); Международной научно-технической конференции «Новые информационные технологии и системы» (г. Пенза, 2002 г.)-
Практическую ценность работы состоит в создании новых, более эффективных методов и программных средств управления процессом восстановления энергетических сетей и других территориально протяжённых сетевых структур, таких как телефонные сети, железнодорожные и автомобильные дороги,
10 нефтепроводы, газопроводы, объекты муниципального хозяйства на основе геоинформационных технологий.
Реализация и внедрение результатов работы. Разработанное программное расширение ArcGraf внедрено в составе геоинформационной системы NilesVl, разработанной ФГУП «НІШ Рубин» г. Пенза и эксплуатируется филиалом ОАО «ПензаЭнерго» «Нижнеломовские электрические сети». (Приложение А).
Структура и объём работы. Диссертационная работа состоит из введения, четырёх глав, заключения, списка литературы и приложения. Работа содержит 144 страницы основного текста, 43 рисунка и 9 таблиц, 126 страниц приложений. Список литературы включает 55 наименований.
Автор считает своим долгом выразить благодарность научному руководителю, д.т.н., профессору П.П. Макарычеву; заведующему кафедрой вычислительной техники ПГУ, д.т.н., заслуженному деятелю науки РСФСР, профессору Н.П. Вашкевичу; заведующему кафедрой автоматизированных электроэнергетических систем ПГУ, д.т.н., профессору В.И. Чернецову за ценные советы и поддержку при выполнении работы.
Организация моделирования в геоинформационных системах
По сфере использования ГИС занимает довольно широкую нишу в системах автоматизированного контроля и управления, в системах документооборота и информационно-управляющих системах. Подробный обзор решаемых с помощью ГИС задач представлен в Приложении В данной диссертации. Это обусловлено тем, что многие ГИС-системы создавались с возможностью использования внутреннего или внешнего языка программирования. Например, для ArcView, это внутренний язык Avenue. Кроме того, ArcView может взаимодействовать с программами, написанными с использованием практически любых языков программирования. КОМБИНАЦИЯ внутреннего языка Avenue с внешним языком обработки и моделирования данных делает возможным совместное использование средств пространственного анализа и моделирования. Работы по совместному использованию ведёт институт сейсмологии Объединённого института физики Земли по сейсмическому районированию Северной Евразии (территория России и стран СНГ). В 90-х годах институтом был создан комплекс программ оценки сейсмического риска, рассчитьшающий возможную сотрясаемость территории на основе данных о различных сейсмологических зонах, потенциально опасных землетрясений и сейсмически однородных территорий, называемых доменами. Средствами ГИС осуществляется подготовка данных для этого комплекса, имеющих сложную структуру. На основе этих данных рассчитывается график повторяемости землетрясений, диапазон глубин, на которых могут произойти землетрясения, информация о затухании энергии и т.д. С использованием ГИС проводится пространственный анализ взаимного расположения рассматриваемых очагов землетрясений. Выходные данные комплекса обрабатываются в ГИС программами построения изолиний. На основе параметров изолиний в Arc View строятся конечные карты сотрясаемости. Без применения ГИС, решать задачи, аналогичные рассмотренной, было достаточно трудоёмко и приводило к вынужденному упрощению многих моделей, и сказывалось на качестве получаемых результатов. [6]. Подобные исследования ведутся как в России объединённым институтом физики Земли имени О.Ю. Шмидта РАН по общему сейсмическому районированию территории Российской Федерации, так и в Евразии и США [7]. Примером эффективного использования ГИС является моделирование процессов на рерритории Семипалатинского испытательного ядерного полигона. Система ориентирована на решение следующих задач: - изучения процессов поступления и переноса радионуклидов в различных средах и оценкой их воздействия на здоровье человека; - оценки уровня радиоактивного загрязнения территории и идентификацией районов повышенного радиационного риска; - прогноза развития радиационной и экологической ситуации на загрязнённой территории во времени; - экспертного анализа реализации природоохранных мероприятий. База данных ГИС ядерного полигона используется не только для информационно-справочного обслуживания пользователей, но и для поддержки различных процедур моделирования. В связи с этим, учтены требования к информационному обеспечению по полноте и времени доступа к данным [8]. Ещё одна область применения ГИС в процедурах моделирования — это работа с инженерными сетями. В 1996 году, крупнейшая в Дании кампания NESA — поставщик электроэнергии, начала работать с системой Giselle. Это ГИС-система, поставляемая дистрибьютором ESRI в Дании. Система Giselle основана на ARC/INFO и модуле расширения Arc Storm и ORACLE в качестве базы данных. Система реализована на технических средствах Digital Alpha, которые включают 5 серверов баз данных и 29 рабочих станций [9]. Таким образом, на сегодняшний день существуют различные варианты использования технологий ГИС для моделирования сложных систем с территориально распределёнными объектами. Организация таких систем вьшолнена с использованием как внутренних, так и внешних модулей.
В настоящее время в России и, в том числе, в Пензенской области, большое распространение получили территориально распределенные отраслевые геоинформационные системы [10]. Задание на разработку геоинформационной системы филиала ОАО Пензэнерго Нижнеломовских электрических сетей — ГИС «НиЛЭС» было выдано организации ГНПП «Рубин». Текст технического задания приведён в Приложении С.
Адаптация алгоритма разложения графа в ширину применительно к модели энергосистемы
Результат выполнения алгоритма — одномерный массив result — имеет процедуру чтения FIFO и содержит упорядоченный список обхода рёбер повреждённого графа энергосети.
В алгоритме введены временные переменные ds, ps, ns, nt, к и одномерный массив стекового типа result, в котором хранятся номера линий электропередач в порядке их восстановления. Элементы rezult а Е, заполнение и чтение массива происходит по процедуре FIFO. В одномерном массиве ver хранится список отождествляемых вершин. Процедура работы с массивом — FIFO.
Окончательное планирование завершилось после получения массива порядка восстановления, но в системе остаются ЛЭП, представленные в модели в виде хорд графа, восстановление которых не имеет решающего значения для функционирования сети. В понятие надёжности входит непрерывное и качественное обеспечение электроэнергией потребителей [13].
Для дальнейшего исследования графа энергетической сети необходимо упорядочить оставшиеся рёбра с коэффициентами неисправностей отличным от нуля. Такие рёбра графа представляют собой хорды [17]. Исходя из этого, для более удобного решения поставленной задачи восстановления качественного энергоснабжения произведём оценку и классификацию имеющихся хорд ЛЭП по топологическим признакам: хорды, связывающие две смежные и не смежные вершины (рисунок 2.8 а) и в) — хорды у и z); хорды, связывающие периферийную вершину с остальным графом (рисунок 2.8 б) — хорда х). Необходимо расположить хорды в последовательности увеличивающей связность графа. Исходя из этого предположения, хорды подлежат упорядочиванию в следующей последовательности: топологическим признакам На первом этапе, без восстановления хорд, можно предположить, что полученный ранее граф неисправностей состоит из объединённых в вершины сильносвязных компонент. Под сильносвязными компонентами будем понимать подграф исходного графа, удаление рёбер которого с точки зрения повторного воздействия менее вероятно, чем удаление других рёбер графа, или с числом -связности большим, чем у других компонент графа. Это предположение тем более верно, что при повторном воздействии факторов, приведших к множественной аварии возможно частичное, или полное повторение явлений, приведших к катастрофе и разрыву тех же самых ЛЭП, которые были выведены из строя. Можно считать вершины, отождествлённые при выполнении обобщённого планирования, сильно связными. Для дальнейшего анализа на восстановление графа неисправностей был предложен алгоритм разложения графа в ширину. Этот алгоритм часто использует для поиска циклов в графе (рисунок 2.9), но его ещё предлагается использовать и для поиска порядка восстановления хорд, соединяющих вершины графа [27].
В результате выполнения разработанных алгоритмов получен список восстановления всех критических неисправностей рассматриваемой сети. Для дальнейшего использования предложена классификация хорд графа энергетической сети, позволяющая продолжить процедуру получения упорядоченного списка восстановления.
Для решения задачи получения полного списка восстановления, следует упорядочить имеющиеся хорды по топологическим признакам. Для разработки алгоритма получения списка восстанавливаемых хорд графа энергетических сетей предлагается разложить этот граф в ширину. Классический алгоритм разложения графа в ширину рассмотрен в [27, 20]. На основе классического алгоритма была разработана граф-схема алгоритма разложения графа в ширину для нахождения порядка восстановления линий электропередач. Пример разложения в ширину графа представлен в Приложении D.
Предположим, что алгоритм начинает выполняться после операции отождествления источников, описанной ранее. В переменной / хранится информация об уровне вложенности вершин графа. В процессе работы алгоритма вводится матрица TS3 и одномерный массив D, где s — размер массива N. В первом столбце матрицы будем хранить значение переменной t для соответствующего ребра, а во втором и третьем столбце — номера инцидентных ей рёбер. Размер массива D равен размеру массива /. В нём будем хранить значения переменной t для соответствующей вершины. Каждый столбец D соответствует вершинам графа, в порядке нахождения их в массиве /. В массиве result разместим номера вершин графа, в соответствии с разложением в ширину. Количество элементов result и / равно.
Разработка алгоритмов для организации модуля анализа сетевых структур
Структурный параметр /л характеризует уровень недогрузки заданной структуры в достижении максимальной связности. Будем использовать этот показатель при оценке живучести сетей энергетики, представленных в виде графа.
Чем ближе этот показатель к нулю, тем более равномерной является структура графа и тем меньше у структуры точек сочленения и мостов. Отсутствие в энергетической сети узких мест делает не напрасными капиталовложения на создание «компонент сильной связности», то есть делает менее вероятным выход их из строя.
При исследовании влияния внешних возмущений на функционирование энергетической сети, представим сеть графом G(u,v), где и- множество вершин, a v- множество дуг. Известно также, что сеть имеет множество источников и стоков. Все вершины-источники могут быть сведены к одному, путем удаления вершин источников, кроме одной, и введения дополнительных дуг (отождествлением вершин источников см. главу 2). К стокам будем относить все остальные вершины сети. Для описания возмущения сети будем использовать неотрицательный вектор X = (xv...,xm), где х(- возмущение для дуги vt, принимает значение [0,1]. При возмущении я:,. =1, элемент v, выходит из строя. Совокупность возмущений может характеризоваться числом и местом возникновения возмущений. Предположим, что для фиксированного числа возмущений, они воздействуют на различные участки сети. Анализ живучести энергетических сетей приведён в Приложении Е. Из проведённого анализа следует, что рассмотренные критерии могут быть положены в основу оценки состояния сети для характеристики её надёжности и живучести. Наиболее надёжным вариантом взаимного расположения потребителя и производителя является их совместное размещение [48]. В этом случае система передачи практически отсутствует. Это возможно в системах теплоснабжения, энергоснабжения, водоснабжения и т.д. Например, в качестве индивидуальных генераторов электроэнергии используются различного вида механические генераторы (с использованием двигателей внутреннего сгорания, газотурбинных двигателей, паровых двигателей и турбин, энергии ветра, падающей и приливной воды), солнечные генераторы (с фотоэлементами, термопарами, либо с использованием термодинамических генераторов), электрохимические источники тока (гальванические элементы и аккумуляторы), кинетические генераторы (маховики) и т.п. Удобство использования индивидуальных источников электроэнергии кажущееся. Большинство из них требуют обеспечения снабжения первичными источниками энергии (например топливом), либо зависимы от погоды и времени года. Но основной недостаток индивидуальных электрогенераторов — невысокая надёжность. Любой техосмотр или мелкий ремонт заставляет отключать индивидуальные генераторы и тем самым лишать потребителя энергопитания. Таким образом резервирование одно или многократное оправдано только для важных объектов энергопотребления, поскольку требует увеличения затрат пропорционально степени резервирования. Повышение надёжности структуры также возможно за счёт использования в качестве резерва генераторов электроэнергии ближайших потребителей. При разработке модуля анализа сетевых структур возникла необходимость оценки устойчивоспособности структуры в виде количества отключаемых от сети элементов от числа выведенных из строя связей. Для простых структур такая оценка может быть произведена аналитически. Для анализа более сложных структур необходима автоматизация процесса получения таблиц зависимости максимального количества отключённых от сети элементов от числа выведенных из строя связей. Рассмотрим разработку «таблиц отказов» для различных вариантов энергетической сети. Технически целесообразно производство электроэнергии сосредоточить в крупных центрах с наличием нескольких генераторов, обученного обслуживающего персонала и эксплуатационной базы. Но в этом случае возникает проблема передачи энергии. Можно предположить, что энергоснабжение потребителей будет осуществляться по звёздной схеме, когда к каждому потребителю от производителя электроэнергии протянута своя линия электропередачи (рисунок 3.5). В этом случае надёжность энергообеспечения каждого потребителя будет определяться надёжностью генератора производителя электроэнергии и надёжностью линий электропередач. Показатели надёжности и того и другого можно улучшить, используя тот же метод резервирования. Ничто не мешает иметь запас по мощности генераторов. Величина этого запаса должна позволять останавливать отдельные генераторы для профилактики и ремонта. Характеристика уровня недогрузки структуры для схемы звезда определяется по формуле (3.4) и будет равна:
Оценка сложности и быстродействия алгоритмов поиска кратчайших путей
Геоинформационные системы нового поколения отличает ориентация на пользовательские модели данных с учётом предметной области и особенностей приложений. Разрабатываемые модули являются приложениями для ГИС NilesVl для построения маршрутных карт движения ремонтных бригад в порядке ликвидации неисправностей.
При написании многомодульной программы с использованием как внутреннего, так и внешнего языков программирования, появилась задача выбора способа взаимодействия модулей программы. Наряду с решением задачи поиска порядка восстановления территориально протяжённых объектов, решается задача организации интерфейсной части модуля расчёта и создания более универсальной программы с возможностью максимального использования результатов разработки в других смежных областях.
Кроме того, проводится сравнительный анализ алгоритмов поиска кратчайших путей с алгоритмом, разработанным и использованным в работе, по вычислительной сложности. Результаты такого анализа позволяют сделать вывод о эффективности практического применения разработанного алгоритма поиска кратчайших путей для решения задач на тех или иных территориально протяжённых системах.
Используя возможности обработки данных, геоинформационная система, построенная на платформе ArcView, позволяет реализовать поиск последовательности восстановления повреждённых участков ЛЭП и получения маршрутной карты восстановления для проекта NilesVl (Нижнеломовские энергетические сети). Программа моделирует работу энергетической системы с использованием механизма неориентированных графов. При анализе данных и вводе информации об авариях используются как внешние наблюдения о сети, проводимые с наземных и воздушных наблюдательных пунктов, так и существующая информационная сеть, включающая систему передач высокочастотного сигнала по ЛЭП, других информационных каналов, систем определения места разрыва на линии электропередач. Для хранения географической информации о месте расположения энергетических объектов используются файлы точек (shape файлы), а для представления информации о структуре энергетической сети — атрибутивные таблицы данных. Для хранения информации о месте и степени повреждения, в атрибутивные таблицы было добавлено поле Neispr, в котором хранится коэффициент неисправности соответствующего объекта энергосистемы. Разработанный модуль производит расчёт, вывод на экран и печать маршрутных карт для аварийных бригад восстановления энергосистемы. Для принятия решений при получении маршрутных карт, используется модуль Network Analyst, который обрабатывает информацию о местоположении аварии и информацию о сети дорог. С использованием этого модуля выполняется другой вид моделирования — геометрический анализ. С появлением баз данных дорог и линий электропередач появилась возможность нахождения кратчайших маршрутов к аварийным участкам сети, а также определения порядка, в котором целесообразно проводить восстановление топологии сети. Такая задача возникает при множественных авариях, когда важно за короткое время ввести в строй наибольшее количество подстанций. ГИС ArcView делает возможным использования следующих инструментов работы с различными типами данных: - добавление данных, собранных в таблицы (формат dbf); - отображение пространственных данных; - сетевые возможности обработки табличных данных; - управления крупными базами пространственных данных, Spatial Database Engine (sde); - работа с динамически подключаемыми библиотеками (dll) и динамическим обменом данными (dde); - возможности пространственной выборки информации на основе использования электронной карты; - возможности проведения расчётов, используя табличные и географические данные проекта; написание внутренних программ, с использованием внутреннего языка программирования Avenue.
