close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
УДК 681.3
АЛГОРИТМ ИНФОРМАЦИОННОГО ПРОЦЕССА РАСЧЕТА КРАТЧАЙШЕГО ПУТИ
ПРОНИКНОВЕНИЯ ЧЕРЕЗ СИСТЕМУ ОХРАНЫ ОБЪЕКТА
А.С. Кравченко, В.И. Сумин
Рассматривается алгоритм работы информационной системы определения надежности системы охраны
объекта, основанный на использовании аппарата теории графов. Расчет кратчайшего пути основан на алгоритме
метода «ближайшего соседа»
Ключевые слова: граф, метод «ближайшего соседа», путь в графе
Для определения количественной оценки
надежности системы охраны необходимо провести
подробный анализ всех возможных способов
проникновения злоумышленника не территорию
объекта охраны к месту расположения материальных
ценностей
[5].
Выбор
пути
проникновения
осуществляется злоумышленником в зависимости от
множества факторов. Такими факторами могут быть:
степень оснащенности злоумышленника, а так же
состав СОО. Время проникновения в большой
степени
зависит
отдельных
строительных
конструкций, входящих в состав объекта охраны.
Отыскание оптимального пути проникновения
злоумышленника решает задачу поиска уязвимости в
проектируемой системе охраны объекта. Критерием
качества СОО может быть минимальное время
проникновения
через
нее,
таким
образом
минимальная длина пути проникновения принимается
за показатель качества системы в целом.
Для решения задачи отыскания кратчайшего
пути между двумя точками используется аппарат
теории графов. Путь злоумышленника представим в
виде цепочек элементов охраны (вершины графов) и
путей возможного передвижения злоумышленника
(дуги графа). Существуют различные комбинаторные
алгоритмы, реализующие поисковые задачи в
планарном графе, которые анализируют все
возможные сочетания цепочек проникновения, для
отыскания кратчайшей из них. Длина дуг графа
отражает
время
проникновения
через
соответствующий элемент укрепленности, длина
минимальной цепочки дуг графа, между заданными
его вершинами позволяет численно оценить общую
надежность
всей
СОО
при
осуществлении
проникновении через нее.
Рассмотрим алгоритмы поиска кратчайшего пути
в планарном орграфе с неотрицательными весами, что
относительно
СОО
решает
задачу
поиска
кратчайшего расстояния от заданной точки, до
охраняемой материальной ценности [4]. Выбор
именно простого планарного графа обусловлен
возможностью представления любого вида графа в
простой форме так, если граф не является простым, то
Кравченко Андрей Сергеевич – ВГПУ, аспирант, e-mail:
kr_and@inbox.ru
Сумин Виктор Иванович – ВГПУ,
д-р техн. наук,
профессор, e-mail: viktorsumin51@yandex.ru
без ущерба для предмета рассмотрения можно
отбросить все его петли, и заменив все параллельные
ребра одним из них (ребром с наименьшим весом).
Сложнее обстоит дело с представлением
неориентированных дуг графа [1]. Возможно
представление каждой неориентированной дуги в виде
пары дуг, которые противоположно направленны и
имеют равный вес, равный весу неориентированного
ребра,
т.е.
неориентированное
ребро
(i, j )
представляется как пара ориентированных ребер (i, j )
и ( j, i) .
Задача
отыскания
кратчайшего
пути
к
охраняемым
материальным
ценностям
с
использованием аппарата теории графов состоит из
двух подзадач:
1. Нахождение длины кратчайшего пути
между двумя выделенными вершинами.
2. Нахождение длин кратчайших путей между
выделенной вершиной и всеми остальными
вершинами графа.
Для решения задачи воспользуемся рядом
соглашений:
• выполнение условия равенства весовых
коэффициентов ωi , j = ω j ,i не требуется;
• выполнение
неравенства
ωi , k + ωk , j < ωi , j необязательно;
треугольника
• несуществующие ребра будем считать
ребрами с бесконечным весом;
• сумма весов ребер в пути будет называться
весом или длиной этого пути.
Первая задача, отыскание длины кратчайшего пути
между двумя вершинами S (начало) и F (конец) и
отыскание самого пути, может быть решена методом
«ближайшего соседа» для отыскания минимума
деревьев графа [2]. Начинаем из вершины S и
просматриваем граф в ширину, помечая вершины
значениями их расстояний от
S . Процесс
заканчивается, когда вершина F помечена значением
ее расстояния от S .
До
окончательной
пометки
вершине
присваивается временная метка: присвоенное вершине
число будет расстоянием от начала S , когда множество
рассмотренных путей не состоит из всех возможных
путей. Алгоритм прекращает работу только тогда, когда
метка, присвоенная вершине F , далее не меняется.
Таким образом, в каждый момент времени работы
алгоритма некоторые вершины будут иметь
окончательные метки, а остальная часть нет.
Вначале
вершине
S
присваивается
окончательная метка 0 (нулевое расстояние до самой
себя), а каждой из остальных V − 1 вершин
присваивается временная метка ∞ ( V - общее
количество вершин графа). На каждом шаге одной
вершине
с
временной
меткой
присваивается
окончательная и поиск продолжается дальше. Таким
образом, на каждом шаге метки меняются
следующим образом.
j,
1. Каждой
вершине
не
имеющей
окончательной метки, присваивается новая временная
метка - наименьшая из ее временной метки и чисел ωij окончательная метка i , где i — вершина, которой
присвоена окончательная метка на предыдущем шаге.
2. Находится наименьшая из всех временных
меток, которая и становится окончательной меткой
своей вершины. В случае равенства выбирается любая
из них.
Процесс продолжается до тех пор, пока вершине
F не присваивается окончательная метка.
Первой помеченной окончательной вершиной
будет S , которая находится на нулевом расстоянии от
себя. Следующей, получившей окончательную метку,
будет вершина, ближайшая к S . Третьей вершиной,
получившей окончательную метку, будет вторая по
близости к S и т. д.. Окончательная метка каждой
вершины — это кратчайшее расстояние от этой
вершины до начала S .
Исходные данные для алгоритма нахождения
кратчайшего пути от точки S к точке F в графе
G = (V , E ) , представлены в виде матрицы весов
W = (ωi , j ), i ∈1..m, j ∈1.. p и массива f, который
состоит из логических элементов для определения
вида метки: если метка окончательная, то
соответствующий элемент массива принимает
значение 1, 0 в противоположном случае.
Алгоритм допускает не более чем V − 1 итераций,
и число операций каждой итерации равно V . Поэтому,
для реализации алгоритма требуется не более чем V 2
операций.
Алгоритм позволяет найти время проникновения
через проектируемую СОО.
Получение всех дуг показывающих кратчайшие
пути до всех точек объекта осуществляется с
помощью алгоритма:
1. Расстановка значений защищенности на
координатной плоскости. Формируется матрица
A = ( xi , y j ), i ∈ 1..m, j ∈ 1.. p из времен проникновения
через элемент укрепленности СОО.
2. Определяется точка A( x1 , y1 ) истока (начало
пути проникновения).
3. Методом перебора рассчитаем время,
являющееся минимальным для каждой кочки
координатной плоскости с истоком в точке
A( x1 , y1 ) (рис. 1.).
Рис. 1 Подпроцесс
времени слева направо
расчета
минимального
4. В результате выполнения части алгоритма
получаем значения времени, просуммированные
цепным методом, т.е. к каждой последующей
добавляется значение из каждой предыдущей точки.
Точки складываются слева направо.
5. Для суммирования времен проникновения
снизу вверх необходимо повторить пункт 3 поменяв
местами индексы i и j (рис. 2.).
Рис. 2 Подпроцесс
времени снизу вверх
расчета
минимального
6. Рассмотренные части алгоритма учитывают
две цепочки слева – направо, направо – вверх. Для
учета остальных возможных цепочек проведем
суммирование сверху вниз и справа налево, изменив
направление изменения параметра цикла на
противоположное. Полученная в результате расчета
цепочка учитывает перемещение: слева – направо –
вверх – налево – вниз.
7. В случае если точка начала проникновения
имеет координаты A( xr , y q ) , то алгоритм обретает
вид, представленный на рис. 3.
8. Повторение части алгоритма 1 - 7 z раз (z –
количество спиральных перемещений), обеспечит
полную проверку плоскости в первой, второй, третьей
и четвертой четвертях. Таблица B(i, j ) содержит
наименьшие времена проникновения для всех точек
координатной плоскости.
9. Нахождение возможных маршрутов движения
злоумышленника при проникновении заключается в
обратном движении по точкам с наименьшим
временем. Структурная схема информационного
процесса,
соответствующего
алгоритму представлена на рис. 4)
рассмотренному
Рис. 3. Подпроцесс расчета минимального
времени проникновения от точки A( xr , y q )
Рис. 4. Подпроцесс нахождения возможных
маршрутов
движения
злоумышленника
при
проникновении.
Литература
1. Абалмазов Э.И. Декомпозиция и композиция
систем безопасности // Системы безопасности, связи и
телекоммуникаций. - 1995. №5. - С. 68-72.
2. Балабошко
Н.Г.
Автоматизированные
комплексные
системы
безопасности
//
Системы
безопасности, связи и телекоммуникаций. -1996. -№ 4. - С.
84 - 85.
3. Гнеденко Б.В. Математические методы в теории
надежности. / Б.В. Гнеденко, Ю.К. Беляев, А.Д. Соловьев
// М.: Наука., 1965. – 524 с.
4. Волхонский В. Термины и определения систем
безопасности // Журнал «Безопасность Достоверность
Информация» № 6 (34), 2000 г. С. 24-27.
5. Дубровин А.С. Методика оценки программ
систем защиты информации и ее функций / А.В.
Мельников, Е.А. Рогозин, В.И.Сумин // Х Международная
научная
конференция
«Информатизация
правоохранительных систем»: Сборник трудов. – Москва,
2001.- С 376-378.
Воронежский государственный педагогический университет
ALGORITHM OF INFORMATIONAL PROCESS OF CALCULATION OF THE SHORTEST WAY
OF PENETRATION THROUGH PROJECTED SYSTEM OF PROTECTION
A.S. Kravchenko, V.I. Sumin
The algorithm of work of an intelligence system of definition of reliability of system of protection of the plant, based on
use of a means of the graph theory is considered. Calculation of the shortest way is based on algorithm of a method of "
Neighbor-Joining»
Key words: the graph, a method of "the nearest neighbour», a way to the graph
Документ
Категория
Без категории
Просмотров
8
Размер файла
444 Кб
Теги
алгоритм, информационные, пути, система, процесс, проникновения, расчет, кратчайшего, охране, через, объекты
1/--страниц
Пожаловаться на содержимое документа