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

Размещено на http://www.allbest.ru/

Федеральное государственное автономное образовательное учреждение высшего профессионального образования

"Национальный исследовательский университет "Высшая школа экономики"

Пермский филиал

Факультет бизнес-информатики

Выпускная квалификационная работа

АНАЛИЗ ИНЖНЕРНЫХ СЕТЕЙ. ПОИСК ОПТИМАЛЬНОГО ПУТИ

Работу выполнил

А.В. Сибиряков

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

В.В. Морозенко

Пермь 2015



Оглавление

Введение

Глава 1. Анализ возможностей информационной системы для поиска оптимального маршрута в инженерных сетях

1.1 Анализ способов представления инженерных сетей в информационных системах

1.2 Моделирование инженерной сети и помещения

1.3 Анализ существующих алгоритмов поиска кратчайшего пути. Выбор оптимального алгоритма

1.4 Моделирование и анализ бизнес-процессов поиска, локализации и устранения неисправности

1.5 Моделирование классов предметной области

1.6 Описание модели базы данных информационной системы

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

2.1 Проектирование информационной системы поиска оптимального маршрута в инженерных сетях

2.2 Реализация компонентов системы поиска оптимального маршрута в инженерных сетях

2.3 Тестирование

Заключение

Библиографический список

Приложения



Введение

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

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

Сегодня тема indoor-навигации очень перспективна, востребована в мире. В ней работают как стартапы, так и крупные технологические компании, такие как Google, Apple, Qualcomm, Broadcom, CSR, Sony, Nokia и др. Игроки мирового рынка уже вкладывают в indoor-навигацию сотни миллионов долларов.Среди российских компаний данной проблемой занимается компания «2ГИС».С другой стороны, приложения indoor-навигации принесут много новых возможностей для людей. В частности, например, они облегчат жизнь путешественникам и командировочным, оказавшимся в чужом городе или стране, с незнакомыми языком и символикой; помогут не заблудиться или найти нужный объект в таких больших зданиях, как аэропорты, торговые центры, деловые здания, вокзалы. Вместе с тем, количество indoor-локаций в мире пока исчисляется десятками или, наибольшее, сотнями. Например, на данный момент в "Этажах" доступны только шесть столичных торговых центров. Эксперты аналитической компании ABI Research в своем исследовании «Indoor Location Technology: Wi-Fi, Bluetooth, Audio, Small Cell, DAS, NFC, MEMS» отмечают, что «рынок все еще находится на стадии зарождения». Кроме того, если брать только применение indoor-навигации к инженерным сетям, то подобных решений на данный момент нет вообще. Поэтому создание системы indoor-навигации для инженерных сетей является очень перспективным делом, в которое будут охотно инвестировать деньги.

Кроме того, потребителям системы indoor-навигации в инженерных сетях она позволит гораздо быстрее находить место повреждения, следовательно, производство/работа будет меньше простаивать, а владелец терять деньги.

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

Что касается степени изученности вопроса анализа инженерных сетей, то по данной тематике было проведено уже много исследований. Так, ещё в 2002 году в статье [1] авторы отметили, что «в различное время ... выполнялись многочисленные проекты по тематике инженерных сетей, включая разработку кадастров и имитационных моделей инженерных коммуникаций (электрических, водопроводных, тепловых, газовых, телефонных сетей, сетей водоотведения), расчеты режимов функционирования инженерных сетей, расчет транспортных сетей и другие». Кроме того, уже были сформулированы задачи анализа (задача проверки связности, задача выделения компонент связности, задача упрощения графа сети и другие). В частности, была рассмотрена и задача, установленная в теме данного исследования (поиск оптимального пути). Более того, на основании проведённых исследований были созданы информационные системы, решающие перечисленные выше задачи. Например, геоинформационная система ГрафИн, ГИС Zulu, ИГС "CityCom" и др. Недостатком существующих систем является то, что они не касаются компьютерных сетей, они рассматривают инженерные сети вне помещений, они не оптимизируют процесс устранения неисправности (не проводят навигацию персонала, обслуживающего сети). В то же время система, рассматриваемая в данном исследовании, будет лишена упомянутых недостатков: она предназначена для компьютерных сетей помещения и строит оптимальный маршрут для обслуживающих лиц до места неисправности (решает задачу indoor-навигации).

Проблема

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

Объект

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

Предмет

Программное средство для информационной поддержки процесса локализации и устранения неисправности в инженерной сети.

Цель

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

Задачи

1. Исследовать предметную область.

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

b. Создать диаграмму бизнес-процесса и классов в предметной области.

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

2. Выбрать подходящий способ представления данных о модели сети и помещения в компьютере.

a. Рассмотреть существующие способы представления инженерных сетей и помещений.

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

c. На основе анализа предметной области и рассмотрения существующих способов представления инженерных сетей и помещений выбрать наиболее подходящий для данной ситуации способ.

d. Оптимизировать способ представления для данной предметной области.

3. Выбрать алгоритм поиска оптимального маршрута.

a. Рассмотреть существующие алгоритмы, осуществляющие поиск оптимального маршрута.

b. Исходя из выбранного способа представления данных об инженерной сети и помещении определить наиболее подходящий алгоритм.

c. Определить входные и выходные данные, необходимые для выбранного алгоритма.

4. Спроектировать и создать информационную систему, осуществляющую поиск оптимального маршрута.

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

b. Определить требования к системе.

c. Создать спецификацию информационной системы и её составных частей.

d. Создать информационную систему. Создать базу данных, хранящую сведения о помещении и сети. Создать приложение ввода информации в БД. Реализовать web-приложение, осуществляющее поиск оптимального маршрута до места неисправности и отображающего его и помещение визуально (в рамках данной работы создаётся не всё web-приложение, а только его серверная часть. Клиентская часть рассматривается в других работах).

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

Методы исследования

Моделирование - для моделирования бизнес-процесса и инженерных сетей; для тестирования средства (информационной системы).

Абстрагирование - для выбора способа представления данных о модели сети и помещения в компьютере.

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

Результат работы

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



Глава 1. Анализ возможностей информационной системы для поиска оптимального маршрута в инженерных сетях

1.1 Анализ способов представления инженерных сетей в информационных системах

Начнём исследование с того, что определим, что же такое инженерные сети. Инженерные сети - это такие сети, которые осуществляют централизованное снабжение рассредоточенных потребителей электрической и тепловой энергией, топливом, водой или другими транспортируемыми продуктами [1].

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

1. Кабельные сети: электрические воздушные, электрические кабельные подземные, низкого/высокого напряжения, контактные сети, телефонные сети; сети передачи данных (электрические, оптоволоконные), телерадиосети.

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

3. Дорожные сети: автомобильные и рельсовые дороги, метрополитен, фуникулер и т. д.

В результате для исследования были взяты электрические сети передачи данных, конкретнее - компьютерные сети. Компьютерная сеть - система связи компьютеров или вычислительного оборудования (серверы, маршрутизаторы и другое оборудование). Синонимом понятия «компьютерная сеть» является понятие «вычислительная сеть», поэтому далее они будут использоваться для обозначения одной и той же сущности. Одним из преимуществ таких сетей в контексте нахождения оптимального пути до места неисправности является сравнительно лёгкое определение наличия неисправности и его логического места в сети (например, в сравнении с водопроводной сетью).

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

Очевидно, что для решения задач моделирования инженерных сетей удобно использовать представление сети в виде графа. В ходе решения задач моделирования граф может использоваться либо непосредственно как основа для решения, либо как промежуточное представление, по которому строятся системы уравнений или иные математические модели. В данном исследовании граф будет использоваться непосредственно как основа для решения. Использование представления в виде графа позволяет учитывать такое важное свойство сети, как топология [1]. Топология (в контексте инженерных сетей) - способ описания конфигурации сети, схема расположения и соединения сетевых устройств. Кроме того, такое представление сети позволяет анализировать её методами теории графов [2], такими как алгоритм Дейкстры, жадные алгоритмы и т.п.

Также для моделирования инженерных сетей можно использовать сети Петри [3]. Такой способ представления является частным случаем способа представления с помощью графа, так как сеть Петри является двудольным ориентированным мультиграфом. Для моделирования используются иерархические раскрашенные Сети Петри (СП) с временным механизмом, где цвет (тип меток) соответствует типу трафика. Метки могут быть двух типов - «сообщения» и «служебные маркеры», означающие факт занятости ресурса (какого-либо устройства) обработкой меток-«сообщений». Количество меток в позициях соответствует состоянию сети, переходы изменяют это состояние, перемещая метки в другие позиции. Каждый сетевой объект (рабочая станция, канал передачи, коммуникационное устройство) моделируется как подсеть Петри.

Определение СП при этом можно представить в следующем виде:

,

где P - множество позиций; T - множество переходов; D - множество дуг; TR - множество типов трафика; TR(p) - множество типов меток, которые могут находиться в позиции р; m(tr, p) - метка типа tr, находящаяся в позиции р.

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

В данном исследовании для представления инженерной, а именно - компьютерной сети, был выбран неориентированный граф. Более сложные типы графа (те же сети Петри) использовать не имеет смысла, так как они позволяют проводить моделирование сети не только в пространстве, но и во времени, а это в данном случае не требуется. Цель представления системы в виде сети Петри и последующего анализа этой сети состоит в получении важной информации о структуре и динамическом поведении моделируемой системы и возможности моделирования работы программного обеспечения для рассматриваемой системы [6]. Те же сети Петри предназначены больше для имитационного моделирования. Для решения поставленной цели нужно смоделировать сеть исключительно в пространственном измерении, а динамическое поведение системы неважно. Существующие или вновь добавляемые сетевые устройства рассматриваются как вершины, а соединяющие их линии связи - как рёбра.

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

1.2 Моделирование инженерной сети и помещения

В пункте 1.1 настоящей работы было решено, что средством моделирования ИС был выбран неориентированный граф G. Далее объясним граф подробней. Вершинами в нём могут являться любые объекты сети, кроме сетевого кабеля. Рёбра графа означают, что вершины электрически соединены между собой.

Также в пункте 1.1 неориентированный граф H был выбран для моделирования путей прохода в помещениях. Поскольку будущая информационная система предназначена для поиска кратчайшего пути, то, очевидно, нужно хранить информацию обо всех возможных путях прохода между объектами сети. Вершинами графа H являются маркеры, обозначающие либо объекты сети, либо объекты помещения, встречающиеся на пути. Рёбра графа обозначают, что человек может пройти между двумя инцидентными вершинами-маркерами напрямую, без препятствий на пути. Атрибутами ребра являются длина, начальный и конечный маркер, инцидентные ребру. Важно отметить, что все рёбра данного графа являются прямыми; в ином случае задача бы сильно усложнилась, так как пришлось бы хранить не только начало и конец ребра, а также его длину, но и координаты всех его точек. Такая прямолинейность достигается тем, что при необходимости моделирования криволинейного пути он просто разбивается на несколько более коротких путей, для чего добавляется несколько маркеров. Получившаяся в результате цепь прямолинейных небольших путей примерно совпадает с исходным криволинейным путём.

Также очевидно то, что множество вершин графа G инженерной сети является подмножеством вершин графа H путей прохода. Следовательно, можно объединить эти два графа в один граф F. В итоге получилось, что данные о компьютерной сети и о переходах представляются одним графом F с двумя типами рёбер. Пример графа F показан на рисунке 1.1. Первый тип - рёбра, обозначающие электрическое соединение между маркерами-объектами сети (основная линия). Второй тип - рёбра, показывающие, что возможно пройти между двумя инцидентными вершинами-маркерами напрямую, без препятствий на пути (штриховая основная линия).

Рисунок 1.1. Пример помещения с графом F путей и компьютерной сети

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

1.3 Анализ существующих алгоритмов поиска кратчайшего пути. Выбор оптимального алгоритма

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

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

1. Алгоритм Дейкстры.

2. Алгоритм Беллмана-Форда.

3. Алгоритм Флойда-Уоршелла.

4. Алгоритм Левита.

5. Алгоритм Джонсона.

Кратко рассмотрим эти алгоритмы, чтобы выбрать оптимальный.

Алгоритм Дейкстры изобретен нидерландским ученым Э. Дейкстрой в 1959 году. Цель алгоритма - нахождение кратчайшего расстояния от одной вершины графа до всех остальных. Алгоритм работает только для графов с ребрами неотрицательного веса [5].

Алгоритм Беллмана-Форда - алгоритм поиска кратчайшего пути во взвешенном графе. Отличительной особенностью является то, что он может работать с ребрами, имеющими отрицательный вес. Кроме того, особенностью алгоритма является то, что в одну и ту же вершину мы можем попасть несколько раз [4].

Алгоритм Флойда-Уоршелла более общий, чем алгоритм Дейкстры. Это динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа [5]. Тем не менее, алгоритм определяет только кратчайшие расстояния между всеми парами вершин, но не сохраняет информации о кратчайших путях [5], что является существенным недостатком применительно к задачам данной работы.

Алгоритм Левита позволяет найти кратчайшие пути от заданной вершины до всех остальных вершин [5]. В сравнении с методом Дейкстры метод Левита проигрывает в том, что некоторые вершины приходится обрабатывать повторно, а выигрывает на более простых алгоритмах включения и исключения вершин из множества М1 (М1 - вершины, расстояние до которых вычисляется на текущем шаге алгоритма). Экспериментально установлено, что для графов с «геометрическим» происхождением, т.е. для графов, построенных на основе транспортных сетей и реальных расстояний, метод Левита оказывается наиболее быстрым. Он выигрывает и по размеру программы.

Алгоритм Джонсона позволяет найти кратчайшие пути между любыми двумя вершинами графа за O(n2*log(n)+n*m), где n - количество вершин, а m - количество рёбер. Следовательно, для достаточно разреженных графов, он эффективнее альтернативных алгоритмов возведения в квадрат матрицы весов и алгоритма Флойда-Уоршелла [5].

В таблице 1.1. представлено сравнение алгоритмов поиска кратчайшего пути в графе:

Таблица 1.1. Сравнение алгоритмов поиска кратчайшего пути в графе

Алгоритм	Сложность	Количество начальных вершин	Работа с рёбрами отрицательного веса
Дейкстры	O(n2+ m)	1	нет
Беллмана-Форда	O(n*m)	1	да
Флойда-Уоршелла	O(n3)	все	да (без отрицательных циклов)
Левита	O(n*m)	1	да
Джонсона	O(n2*log(n)+n*m)	все	да (без отрицательных циклов)



В результате анализа был выбран алгоритм Дейкстры. Во-первых, он работает только с ребрами, имеющими неотрицательный вес, а в нашей системе только такие ребра и существуют. Во-вторых, в случае нашего графа путей сложность алгоритма Дейкстры является наименьшей среди всех приведённых алгоритмов, так как граф путей H связный, но не является деревом (иначе алгоритмы Беллмана-Форда и Левита были бы выгоднее). В-третьих, во время его выполнения пройденные вершины помечаются. Это может пригодиться при создании маршрута к точке разрыва, в нашем случае необходимо знать, не только «длину» кратчайшего пути до вершины, но список вершин, через которые он проходит.

1.4 Моделирование и анализ бизнес-процессов поиска, локализации и устранения неисправности

Перед тем, как начинать применять поиск кратчайшего пути в инженерных сетях, нужно узнать, когда это необходимо сделать. А точнее, нужно проанализировать процесс устранения неисправности в инженерных сетях. Для анализа необходимо смоделировать этот бизнес-процесс. Процесс может быть смоделирован с помощью различных средств, таких как сеть Петри, блок-схема, а также диаграммы в других нотациях структурного и объектного моделирования (такие как DFD, IDEF0). Проанализируем кратко некоторые из них.

Изначально сети Петри были предложены для моделирования асинхронных параллельных процессов в дискретных системах, но затем получили значительное развитие и применение в разнообразных областях [6]. Данный теоретический аппарат удачно сочетает в себе наглядность представления процессов, мощность моделирования и мощность разрешения. При этом сеть Петри удачно представляет структуру управления <...> и поэтому является эффективной при моделировании упорядочения инструкций и потока информаций [6]. Цель представления системы в виде сети Петри и последующего анализа этой сети состоит в получении важной информации о структуре и динамическом поведении моделируемой системы и возможности моделирования программного обеспечения для рассматриваемой системы [6].

Также процесс устранения неисправности можно смоделировать в виде блок-схемы. Данный подход имеет много общего с графическими языками описания алгоритмов программного обеспечения [7]. Описание процессов при помощи блок-схем имеет одно существенное преимущество: простота и доступность восприятия. Затраты на обучение исполнителей чтению блок-схем минимальны. Кроме того, для их формирования не требуются специализированные, дорогостоящие программные продукты [7].

Кроме того, возможно описание процесса устранения неисправности в нотации структурного моделирования DFD. При этом полученная схема -- это описание процесса, схожее с его описанием в нотации IDEF3 [7]. В первую очередь диаграмма DFD нужна для описания реально существующих в системе потоков данных. Созданные модели потоков данных организации могут быть использованы при решении таких задач, как: определение существующих хранилищ данных; определение и анализ данных, необходимых для выполнения каждой функции процесса; подготовка к созданию модели структуры данных системы; выделение основных и вспомогательных бизнес-процессов системы [7].

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

В итоге для моделирования процесса устранения неисправности была выбрана блок-схема по причине своей простоты и наглядности. Также было проведено моделирование с помощью DFD, так как эта нотация позволяет наглядно отобразить последовательность операций процесса, а при необходимости провести их декомпозицию. При этом в отличие от IDEF0, где во главу угла поставлено управление, DFD в первую очередь позволяет проследить потоки данных. А это как раз то, что нужно в контексте определения спецификаций алгоритма и модулей будущей ИС. Что касается сетей Петри, то они не были выбраны по причине своей сравнительно меньшей наглядности.

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

Далее представлены модели бизнес-процесса устранения неисправности сначала в виде блок-схемы (рисунок 1.2), а затем и в виде DFD (рисунок1.3, рисунок 1.4). При этом на этапах процесса, выделенных красным цветом, происходит поиск оптимального пути. Следовательно, эти этапы можно автоматизировать с помощью информационной системы, реализующей алгоритм поиска кратчайшего пути.

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

1.5 Моделирование классов предметной области

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

Во-первых, так как объект и предмет исследования связаны с инженерными, а именно - компьютерными, сетями, необходим класс Device, который представляет устройство сети. Атрибутами класса будут являться Id (тип - счётчик) - идентификатор, Type (тип - строка) - показывает тип устройства (коммутатор, модем, маршрутизатор и т.д.), Description (тип - строка) - описание устройства (необязательное поле), PortQuantity (тип - целое число) - показывает количество портов устройства, Neighbours (тип - массив устройств) - показывает список соседних устройств. Метод класса - FillNeighbours() (тип результата - не возвращает) - предназначен для заполнения свойства Neighbours.

Также все устройства являются маркерами, следовательно, нужен класс Marker, который описывает маркер. Атрибутами класса будут являться Id (тип - счётчик) - идентификатор, X,Y,Z (тип - целое число) - показывают координаты маркера, Description (тип - строка) - описание маркера, Image (тип - массив байт) - предназначен для хранения фотографии маркера, Neighbours (тип - словарь, где тип ключа - маркер, а тип значения - целое число) - показывает список соседних маркеров и расстояние до них, Device (тип - устройство) - описывает устройство, если маркер является сетевым устройством (необязательное поле). Метод класса - FillDictionary() (тип результата - не возвращает) - предназначен для заполнения свойства Neighbours.

Так как темой данной работы является поиск оптимального пути, то очевидно, что необходим класс ShortestPath. Его свойствами являются BeginPoint и EndPoint (тип - маркер) - начальная и конечная точки кратчайшего пути, Path (тип - массив маркеров) - последовательность маркеров на кратчайшем пути, Markers (тип - массив маркеров) - множество всех маркеров помещения. Методом класса является метод BuildingPath (BeginPoint, EndPoint, Markers) (тип результата - массив маркеров) - строит кратчайший путь для заданных начального и конечного маркеров.

Наконец, для визуализации кратчайшего пути информационной системе необходимо работать с данными о помещении. Чтобы их представить, нужно создать класс Point, который будет отражать вершину графа помещения. Его свойствами являются Id (тип - счётчик) - идентификатор, X,Y,Z (тип - целое число) - показывают координаты маркера, Description (тип - строка) - описание точки (вершины), Neighbours (тип - массив точек) - показывает список соседних точек. Метод класса - FillNeighbours() (тип результата - не возвращает) - предназначен для заполнения свойства Neighbours.

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

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

Рисунок 1.5. Диаграмма классов предметной области



1.6 Описание модели базы данных информационной системы

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

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

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



Рисунок 1.6. Первоначальный возможный вариант базы данных

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

Кроме того, для сохранения в базе данных объектов класса Point, рассмотренных в предыдущем пункте, и связей между ними были добавлены таблицы Point и LinksP соответственно. Ещё раз отмечу, что эти классы нужны для хранения в базе данных графа R помещения.

Также, в таблицу Markers были добавлены поля типа int, которые хранят координаты маркеров. Это нужно, чтобы была возможность построить графическую модель помещения с маркерами. Ещё было добавлено поле ImageData типа byte[] для хранения фотографии маркера.



Рисунок 1.7. Диаграмма базы данных



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

2.1 Проектирование информационной системы поиска оптимального маршрута в инженерных сетях

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

Выбор шаблона для информационной системы «Инженерная indoor-навигация»

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

Для начала нужно выбрать тип приложения, в виде которого будет реализовываться система «Инженерная indoor-навигация». На наш взгляд, оптимальным решением будет веб-приложение. Веб-приложение - клиент-серверное приложение, в котором клиентом выступает браузер, а сервером - веб-сервер. Логика веб-приложения распределена между сервером и клиентом, хранение данных осуществляется, преимущественно, на сервере, обмен информацией происходит по сети. Такой тип приложения соответствует выдвинутым требованиям к разрабатываемой системе.

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

После того, как был определён тип приложения, можно было приступать к выбору конкретных способов реализации. Как и другие приложения, веб-приложение можно разрабатывать полностью самостоятельно, либо используя определённый шаблон (паттерн) проектирования. Использование шаблона даёт массу преимуществ, а недостатки этого подхода в нашем случае незначительно влияют на конечный результат, поэтому было принято использовать паттерн. Во-первых, использование паттернов снижает сложность разработки из-за использования готовых абстракций для решения целого класса проблем. Во-вторых, применение шаблона упрощает коммуникацию между разработчиками, позволяя ссылаться на известные шаблоны. В-третьих, использование многих шаблонов проектирования зачастую позволяет также создавать более модифицируемые и изменяемые приложения. Причиной служит то, что эти решения уже прошли проверку временем. Следовательно, их использование позволяет создавать структуры, допускающие модификацию в большей степени, чем это возможно в случае полностью самостоятельного решения «с нуля». В-четвёртых, возможность многократного использования решений из уже завершенных успешных проектов позволяет быстро приступить к разработке новых продуктов и избежать типичных ошибок. По сути, разработчик с помощью шаблона пользуется опытом других разработчиков. Кроме того, паттерны проектирования предоставляют абстрактный высокоуровневый взгляд как на проблему, так и на весь процесс объектно-ориентированной разработки. С помощью этого мы можем избежать ненужной детализации на начальных стадиях проектирования[10].

В нашем случае для разработки веб-приложения было принято решение использовать шаблон (паттерн) проектирования MVC (Model-View-Controller).Такой шаблон «особенно хорошо подходит для веб-приложений»[9], так как «взаимодействие с MVC-приложением следует естественному циклу действий пользователя и обновлений представлений, где представление считается не сохраняющим состояние. Это хорошо согласуется с HTTP-запросами и ответами, лежащими в основе веб-приложений». По сути, шаблон MVC обозначает, что MVC приложение будет разделено как минимум на три части [9]:

· Модель. Она содержит или представляет данные предметной области, с которыми работают пользователи. Является наиболее важной частью приложения. Это может быть простая модель представления, которые только представляет данные, которые передаются от контроллера представлению, или доменная модель, содержащая данные домена, а также методы и правила работы с этими данными.

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

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

На рисунке 2.1 показано взаимодействие между компонентами MVC-приложения.



Рисунок 2.1. Взаимодействие компонентов MVC-приложения

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

Во-первых, на роль фреймворка, использующего шаблон MVC, нужно в первую очередь рассмотреть Ruby on Rails, так как в этой среде разработки в одной из первых был применён паттерн MVC. Как следует из названия, он написан на языке Ruby. Это инструмент разработки с открытым кодом, оптимизированный для удобства программирования и устойчивой производительности. Специализирован для веб-приложений, использующих базы данных[11].

Ещё один фреймворк с открытым кодом, использующий шаблон MVC - это ZendFramework. Предназначен для разработки приложений с помощью языка PHP5. Поддерживает множество различных систем управления базами данных (далее - СУБД). Поставляется с Javascript-фреймворком Dojo.

Другой фреймворк, написанный на языке PHP - CakePHP. В отличие от предыдущего средства, он совместим как с РНР4, так и с РНР 5. Является открытым ПО, многие идеи заимствованы от Ruby on Rails.

Что касается языка Java, то для него тоже разработано множество фреймворков, реализующих паттерн MVC. Один из них - это фреймворк с отрытым кодом Apache Struts.

Кроме того, существуют MVC-фреймворки и для других популярных языков программирования. Например, для языка Python разработан фреймворк Django. Этот фреймворк также является открытым ПО. Ориентирован на разработку сайтов информационного характера. Использует собственную ORM (object-relational mapping) технологию.

Что касается компании Microsoft, то она тоже не могла остаться в стороне от развития технологий веб-разработки. Поэтому ею также был изготовлен фреймворк, использующий шаблон MVC - ASP.NETMVC, выпущенный как альтернатива ASP.NET WebForms. В отличие от предыдущих платформ веб-разработки от Microsoft, эта имеет открытый исходный код[9].

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

Таблица 2.1. Сравнение различных MVC-фреймворков

Критерий	Ruby on Rails	Zend	CakePHP	Struts	Django	ASP.NET MVC 4
Язык	Ruby	PHP 5.3	PHP 4, PHP 5	Java	Python	языки ASP.NET
Применение ORM	+	+	+	+	+	+
Использование Ajax	+	+	+	+	+	+
Модульное тестирование	+	+	+	+	+	+
СУБД	многие СУБД	различные СУБД	многие СУБД	многие СУБД	многие СУБД	многие СУБД

Как видно из таблицы, большинство фреймворков, реализующих шаблон MVC, имеют схожий функционал. Основным различием между ними является используемый язык программирования. Поскольку у нас имеется большой опыт программирования на языке С#, то для разработки системы «Инженерная indoor-навигация» был выбран фреймворк ASP.NET MVC 4. К тому же все предыдущие наши наработки по данной системе также были написаны с помощью этого языка и для платформы .NET, а база данных была создана в «родной» СУБД MS SQL Server.

Проектирование системы

Далее нужно было спроектировать базу данных для системы. Процесс проектирования схемы базы данных был затронут выпускной квалификационной работе. Здесь же вкратце распишем, с помощью какой технологии база данных будет реализована. Для этого будет использоваться версия LocalDB из СУБД SQL Server 2012. Эта версия автоматически устанавливается вместе с VisualStudio 2012, следовательно, не нужно устанавливать дополнительные средства для её разработки. SQL Server Express LocalDB - это упрощенная версия SQL Server, обладающая множеством возможностей по программированию баз данных, аналогичных SQL Server. LocalDB выполняется в пользовательском режиме, и его можно установить быстрее, с меньшим числом требований и без конфигурации[12]. Эта версия как раз специально предназначена для разработчиков приложений[9], поэтому в ней доступны только локальные подключения.

После этого необходимо переходить к проектированию непосредственно веб-приложения. Начинать нужно с проектирования модели как главной части MVC-приложения. Для взаимодействия объектов модели с базой данных будет использоваться шаблон «Репозиторий». Он позволяет абстрагироваться от конкретных подключений к источникам данных и является промежуточным звеном между классами, непосредственно взаимодействующими с данными, и остальной программой[13]. С помощью него можно легко менять подключение к одной базе данных на другое или использовать несколько подключений в процессе работы приложения. Например, если мы имеем подключение к базе данных MS SQL Serverи вдруг захотим сменить его на подключение к базе данных MySQL, то нужно будет изменить всего лишь одну строку кода в приложении.

Для непосредственного доступа к базе данных будет использоваться платформа EntityFramework, которая является ORM-системой для платформы .NET. ORM (Object-relational mapping) - это технология, которая позволяет связать таблицы базы данных с классами ООП, то есть позволяет работать с таблицами, столбцами и строками реляционной базы данных с помощью обычных объектов. Кроме того, EntityFramework позволяет использовать технологию LINQ для работы с объектами модели вместо языка SQL. Также EntityFramework поддерживает возможность reverse engineer code first, при которой по созданной базе данных с помощью этого фреймворка генерируются классы модели, классы, описывающие связи между свойствами классов модели и столбцами базы данных и класс контекста базы данных.

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

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

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

Рисунок 2.2 Схема представлений

Согласно схеме представлений, необходимо реализовать 8 методов действий для контроллера HomeController, который отвечает за отображение данных модели в представлениях. При этом для одного представления Search1 нужно 2 метода действия с одинаковым именем Search1: первый метод с атрибутом HttpGet обрабатывает http-запрос Get по адресу http://localhost:9598/Home/Search1,а второй метод с атрибутом HttpPost обрабатывает http-запрос Post по этому же адресу. Этот метод применяется, когда пользователь вводит данные о начальной и конечной точке маршрута и отправляет её на сервер. Get-запрос является тем, что браузер генерирует после клика по гиперссылке. Этот вариант действий будет отвечать за отображение начальной пустой формы. Метод действия с атрибутом HttpPost будет отвечать за получение отправленных данных и решать, что с ними делать. Аналогичная ситуация и с представлением Search2.

Вроде бы этот вариант хорош и должен работать. Но всё дело в том, что визуализация помещения и оптимального пути на стороне клиента идёт с помощью функций библиотеки WebGL для языка JavaScript, позволяющей создавать на нём интерактивную 3D-графику. А с помощью средств этого языка нельзя обрабатывать объекты С#, передаваемые в представление с помощью метода View(объект_С#). Решить проблему можно с помощью формата JSON (JavaScriptObjectNotation), который является независимым от языка способом выражения данных[9]. Для этого применим методы действия, которые возвращают не представление ViewResult, а данные JsonResult. Эти методы будут вызываться из представления по виртуальному клику по Ajax-ссылке. Для обработки полученных данных в представлении должна быть создана специальная функция на языке JavaScript. В результате получается, что вместо методов действия ViewResult [HttpPost]Search1 и ViewResult [HttpPost]Search2 нужно создать, соответственно, методы JsonResultGetRoute(int start, int finish) и JsonResult Search2Json(int finish, int port).При этом все данные будут визуализироваться в одном представлении Search1, поэтому представление Search2 и, следовательно, метод ViewResult [HttpGet]Search2 будут не нужны.

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

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

2.2 Реализация компонентов системы поиска оптимального маршрута в инженерных сетях

Реализация базы данных

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

На данном этапе рассчитано, что данные о помещении, компьютерной сети и путях прохода будут вручную заноситься в базу данных. Причиной для этого является то, что визуальный конструктор в приложении пока не создан, тем более не создано приложение, которое будет распознавать объекты помещения или сети по фотографиям. Данная работа требует больших усилий и временных затрат и не входит непосредственно в список задач данной работы. Единственными данными, которые будут автоматически заноситься в базу, являются фотографии маркеров и путей прохода от них. Зачем так сделано? Известно, что изображение хранится в базе данных в виде бинарного кода. Следовательно, пользователь не может вручную получить бинарный код изображения и внести его в базу данных, поэтому необходимо специальное средство. Для этого было написано специальное нативное приложение. Оно имеет две вкладки. На первой вкладке (см. рисунок 2.3) пользователь, заполняющий базу данных, должен сначала выбрать изображение, которое он хочет загрузить в качестве фотографии маркера, а затем указать необходимый маркер, выбрав его из выпадающего списка. После чего, после нажатия кнопки «Загрузить», изображение будет загружено в необходимое поле базы данных. При этом кнопка становится доступной только тогда, когда выбрано изображение для загрузки. Чтобы загрузить изображения переходов от текущего маркера к следующему, пользователь должен перейти на вторую вкладку приложения (см. рисунок 2.4). Аналогично с предыдущим случаем, сначала необходимо выбрать изображение, нажав на кнопку «Выбрать». Затем нужно из выпадающего списка выбрать текущий маркер, от которого начинается переход (и сделана фотография). После этого из выпадающего списка выбрать маркер, в сторону которого проходит переход. При этом в списке будут доступны только те маркеры, которые соединяются с текущим маркером в графе путей. После этих манипуляций становится доступной кнопка «Загрузить», при нажатии по которой происходит загрузка фотографии в базу данных.

...