автореферат диссертации по радиотехнике и связи, 05.12.13, диссертация на тему:Повышение эффективности мониторинга эксплуатационного состояния средств навигационного оборудования в прибрежной зоне

На правах рукописи

Шсйкнп Трифон Юрьевич

ПОВЫШЕНИЕ ЭФФЕКТИВНОСТИ МОНИТОРИНГА ЭКСПЛУАТАЦИОННОГО СОСТОЯНИЯ СРЕДСТВ НАВИГАЦИОННОГО ОБОРУДОВАНИЯ В ПРИБРЕЖНОЙ ЗОНЕ

Специальность 05.12.13 — Системы, сети и устройства телекоммуникаций (технические науки)

Автореферат диссертация на соискание ученой степени кандидата технических наук

005557970

Санкт-Петербург - 2014

005557970

Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего образования «Государственный университет морского и речного флота имени адмирала С.О. Макарова» на кафедре «Автоматика и вычислительная техника»

Научный руководитель: доктор технических наук, профессор, Смолсицсв Сергей Викторович

Официальные оппоненты: Привалов Андрей Андреевич,

доктор военных паук, профессор,

ФГБОУ ВПО «Петербургский государственный университет путей сообщения Императора Александра I»

Сепчепко Виктор Григорьевич,

кандидат технических наук, профессор,

ФГБОУ ВПО «Г"МУ имени адмирала Ф.Ф. Ушакова»

Ведущая организация: ЗАО «Центральный научно-нсслсдопатсльскин и нроектно-конструкторский институт морского флота» (ЗАО «ЦНИИМФ»), г. Санкт-Нстсрбург

Защита состоится «9» декабря 2014 г. в 14-00 часов па заседании диссертационного совета Д 223.009.06 при ФГБОУ ВО «Государственный университет морского и речного флота имени адмирала С.О. Макарова» по адресу: г. Санкт-Петербург, ул. Двинская, д.5/7, зал заседаний диссертационного совета (ауд. 257)

С диссертацией можно ознакомиться в библиотеке ГУМРФ имени адмирала С.О. Макарова: http://gumrf.ru/naudejat_dissov_zd22300906.html

Автореферат разослан «_»_2014 г.

Ученый секретарь _

диссертационного совета Д 223.009.06

д.т.н., профессор __—Каретников В.В.

. - ... ..

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

В настоящее время технология беспроводных сенсорных сетей (СС) на основе реактивного протокола маршрутизации Ad-hoc On-demand Distance Vector (AODV) достаточно широко распространена в различных системах мониторинга. Сенсорной сетью называют множество датчиков (сенсоров), объединенных между собой радиоканалом. В работе рассматривается возможность применения сенсорных сетей, а именно эффективная реализация их потенциала в коммуникационной инфраструктуре системы мониторинга СНО, что требует глубокого понимания достоинств и недостатков функциональных характеристик данной технологии.

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

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

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

В настоящее время известны работы таких исследователей в области технологии беспроводных СС, как С.С. Баскаков, В.А. Мочалов, М.М. Комаров, М. Дарги. Также следует отметить работы М. Дориго, Д. Голдберга, Дж. Холланда, Ю.А. Кочетова, В.М. Курейчика, Т.В. Левановой в области применения биологических механизмов поиска при решении оптимизационных задач. В то же время до сих пор не разработаны алгоритмы, позволяющие найти оптимальное размещение шлюзов для СС на основе реактивного протокола АОБУ для системы мониторинга навигационных знаков с учетом обеспечения требуемой степени надежности и энергоэффективности сети за приемлемое время. Таким образом, разработка полиномиального алгоритма для предлагаемой задачи является актуальной. Цель работы. Повышение эффективности коммуникационной инфраструктуры системы мониторинга СНО, основанной на технологии беспроводных сенсорных сетей с применением шлюзов путем разработки алгоритмов оптимального размещения шлюзов в сети. Задачи работы:

— проанализировать технологии передачи данных, используемые в системах мониторинга СНО;

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

— разработать методику проектирования коммуникационной инфраструктуры системы мониторинга СНО, основанной на технологии беспроводных сенсорных сетей с использованием шлюзов;

— разработать математическую модель задачи оптимального размещения шлюзов;

— разработать алгоритмы для задачи оптимального размещения шлюзов;

— разработать программное обеспечение для реализации исследуемых алгоритмов;

— провести вычислительный эксперимент для анализа производительности разработанных алгоритмов.

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

— разработана методика проектирования коммуникационной инфраструктуры системы мониторинга СНО на базе технологии беспроводных сенсорных сетей с применение шлюзов;

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

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

— предложена реализация концепций генетического алгоритма для решения задачи оптимального размещения шлюзов;

— предложена реализация концепций алгоритма муравьиной колонии для решения задачи оптимального размещения шлюзов.

Основные положения, выпоенмые на защиту:

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

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

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

Внеярсннс результатов работы. Теоретические и практические результаты диссертационного исследования были использованы при реализации ряда проектов в ЗАО «Техпомарип», что подтверждено соответствующим актом.

Апробация результатов исследования. Основные результаты диссертационной работы докладывались на научно-технических конференциях профессорско-преподавательского состава, научных сотрудников и курсантов ГМА им. адм. С.О. Макарова в 2012 г. и 2013 г., на международной научно-практической конференции «Наука и образование в современной конкурентной среде», г. Уфа, 2014 г.

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

Структура н объем работы. Диссертация состоит из введения, четырех разделов, заключения, списка сокращений и условных обозначений, списка литературы, включающего 99 наименований. Работа изложена на 124 страницах, содержит 38 рисунков и 8 таблиц.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

Перечислены типы данных, передаваемых в системах мониторинга СПО и способы организации удаленного мониторинга. Приведены примеры различных устройств, применяемых в системах мониторинга СНО для передачи данных, а именно передатчики спутниковой и сотовой связи, передатчики автоматической идентификационной системы (АИС), радиомодемы UHF и VHF диапазонов, передатчики сенсорных сетей. В результате проведенного сравнительного анализа были выявлены характерные достоинства и недостатки каждой технологии передачи данных для задач мониторинга СНО. Показана целесообразность использования технологии СС в основе эффективной системы мониторинга СНО.

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

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

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

Сеть навигационных знаков моделируется в виде графа б = (V, £), где V — множество вершин, представляющее множество навигационных знаков, Е — множество ребер графа, характеризующее множество радиоканалов между СНО. Мощность множества |Г| определяется количеством навигационных знаков п, т.е. — п. Вершины графа будем обозначать как и или V, а количество ребер вершины V — как <3е§ V. Через К, будем обозначать множество шлюзов сети. В качестве синонимов приняты следующие пары терминов: «граф» — «сеть», «вершина» — «узел». При использовании шлюза в составе аппаратуры навигационного знака следует предусмотреть существенное увеличение объема потребляемой энергии, поэтому количество шлюзов в сети должно быть сведено к минимуму для уменьшения затрат на развертывание коммуникационной сети системы мониторинга. В данной работе рассматривается зависимость структурной надежности сети от ее топологии и схемы размещения шлюзов. Под отказом понимается случай, когда при выходе из строя любого одного узла или шлюза сети теряется связь с исправными узлами, т.е. исправные узлы не имеют маршрутов к шлюзам сети. Таким образом, на этапе проектирования при размещении шлюзов для повышения отказоустойчивости системы мониторинга СНО необходимо исключить существование узлов, выход из строя которых может нарушить целостность сети, путем обеспечения резервных маршрутов доставки данных в центр мониторинга для каждого узла. Эпергоэффективность сети определяется временем функционирования всех ее узлов. В исследовании рассматривается энергия, потребляемая приемопередающей аппаратурой СНО, и необходимая узлу для формирования и передачи собственного отчета и ретрансляции отчетов от других знаков в центр мониторинга СНО. Таким образом, поднимается вопрос зависимости энергопотребления узлов от структуры сети и схемы размещения шлюзов, определяющих их положение в цепочке ретрансляции сообщений.

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

**„„>*„, (и)+ 1, иеУ\Ур, (1)

где пт («) — количество узлов, для которых узел и является ретранслятором;

— максимальное количество сообщений, которое может передаваться (в т.ч. ретранслироваться) узлом за один цикл сбора информации (значение Гхти задается проектировщиком).

Пусть X — множество вариантов размещений шлюзов в сети. Схему размещения шлюзов хе X в сети будем кодировать в виде /г-мерного вектора бинарных элементов. Для всех элементов вектора выполняется условие

\1 если и еУ ,

*'Нп ' /={1...и}. (2)

1 [0 если Ур; 1 ' у '

Введем бинарную переменную, указывающую па принадлежность узла к множеству шлюзов

[1 если узел уб V ,

к={ р И)

10 если узел V« У

Простая цепь — это последовательность неповторяющихся вершин в графе, где каждая вершина в цепи соединена с последующей вершиной ребром из Е. Пусть Лг,,„ — множество узлов, составляющих 1-ю простую цепь узлов из У\Ур от узла иеУ\Ур до шлюза уе Ур при 1в £„,(£„„— множество простых цепей между вершинами и и V) . На множестве простых цепей между узлом и и шлюзом V можно найти множество кратчайших маршрутов. Тогда

= (4)

гДе — множество узлов, составляющих ^-й кратчайший маршрут от узла и до шлюза V при

(— множество кратчайших маршрутов от узла и до шлюза V). В случае существования нескольких ближайших шлюзов целесообразно учитывать кратчайшие маршруты до всех ближайших шлюзов. Тогда

где Л'у„— множество узлов, составляющих _/'-й кратчайший маршрут от узла и до ближайших шлюзов уе Ур при у'е ^ ( Ju — множество кратчайших маршрутов до ближайших шлюзов). Обозначим через Уи множество узлов, которые могут быть задействованы при передаче данных узлом и е V \ Ур до шлюзов из Ур, тогда

^=иЛГу. (6)

Соответственно множество ближайших шлюзов V", на которые узел и е У\Ур может передавать данные в процессе эксплуатации можно выделить следующим образом

не У\Ур. ' (7)

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

{1 если и■£ У ;

и,\\>еУ\У„. (8)

О если и>еУи, р

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

= (9)

уеГр

Тогда через обозначим множество узлов, представляющее 1-ю простую цепь узлов из У\Ур от узла и до шлюзов из Ур при I е /„. Далее введем бинарную переменную, отражающую наличие простых цепей от узла и до двух разных шлюзов из У

1 если N. П Аг,„ = {«) при г, / е / ,

" '* (10) и в противиом случае',

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

тш^А„=р (11)

уеГ

при ограничениях:

£/г„>1, иеУ\Ур; (12)

->7

5>„,, <&:„„, »вУ\Ур- (13)

£2Х„>1, (14)

1:1 >=¿+1

О-1}' уеУ, и,кеУ\Ур, г,./е/„. (15)

Целевая функция (11) определяет количество шлюзов. Условие (12) гарантирует подключение каждого узла к ближайшему шлюзу. Неравенство (13) исключает избыточную энергетическую нагрузку в процессе эксплуатации, когда все узлы исправны. Условие (14) обеспечивает двусвязность узлов относительно шлюзов.

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

/фп М = И+ X(«)-}Г = {иеГ\Ур I«„,(«)■+1 >} , (16)

иеУ

где У — множество узлов, для которых не выполняется требование (13).

В алгоритме определения пригодности схемы размещения шлюзов требованию энергоэффективности в виде л'"' будем представлять матрицу наличия кратчайшего пути длины т между вершинами, т.е. если элемент матрицы а^ — 1, то между вершинами и и V

существует путь длины т. Все элементы матрицы Л""> являются бинарными. Через IV будем обозначать матрицу кратчайших путей между вершинами. Множество содержит все узлы всех кратчайших путей между и и V, включая сами узлы и и V. Параметр с/, представляет длину минимального пути от узла и до ближайшего шлюза. С учетом введенных обозначений алгоритм проверки схемы размещения шлюзов па соответствие заданному требованию энергоэффективпости приведен на рисунках 1 и 2.

В блоке 1 выполняется присваивание исходных значений всем переменным алгоритма. В блоках 2 — 6 выполняется вычисление вспомогательных данных, необходимых для проверки пригодности схемы размещения шлюзов. Помимо длины кратчайшего пути между парой вершин, выясняются номера узлов, из которых состоит этот путь. Суть операции выполняемой в блоке 3 сводится к поиску кратчайших путей длины т +1 между всеми парами вершин путем умножения матрицы смежности графа и матрицы Л'™'. Все элементы главной диагонали матриц Л'"' при т = {1...и-1} равны 0, а также все элементы матриц являются булевыми, поэтому при «произведении» и-й строки матрицы А''' и у-го столбца матрицы Л'"' элемент '' принимает значение 0 или 1. Единица в результате перемножения элементов аЦ и а!"1 сигнализирует о наличии кратчайшего пути длины т + 1 от узла и до V. Тогда в блоке 4 соответствующее значение заносится в И7 — матрицу кратчайших путей между вершинами. Также в блоке 4 создается множество узлов составляющих кратчайшие пути между

данными вершинами. Если такое множество уже существует, то оно пополняется новыми элементами.

Рисунок 1 — Алгоритм проверки схемы размещения шлюзов на соответствие требованию энергоэффективности

Рисунок 2 — Алгоритм проверки схемы размещения шлюзов на соответствие требованию энергоэффективности (продолжение)

В блоке 6 на основе значения расстояния до ближайшего шлюза (1и для каждого узла сети и выясняются все ближайшие шлюзы, через которые узел и может передавать отчеты в центр мониторинга СНО. По этой информации определяется множество узлов К,„ которые могут быть задействованы для ретрансляции данных в случае передачи узлом и своему ближайшему шлюзу сообщения. В блоках 7 и 8 выполняется основная процедура алгоритма — выяснение соответствия предлагаемой схемы размещения шлюзов требованию (13) .

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

Предлагаемая методика проектирования коммуникационной инфраструктуры системы мониторинга СНО состоит из последовательности действий, представленных на рисунке 3.

Начало

1 г

Формирование топологи' навигационных знаков. 1еской структуры сети

2

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

3

Рисунок 3 — Методика проектирования коммуникационной инфраструктуры системы

мониторинга СНО

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

Предварительный анализ структуры сети позволит не применять алгоритм Форда-Фалкерсона для каждого хе X и сократит общее количество возможных вариантов размещения шлюзов. Анализ структуры сети подразумевает выявление компонент связности графа и выявление в каждом подграфе блоков и точек сочленения. Блоком в графе называется максимальный двусвязный подграф, не содержащийся в другом таком подграфе. Точкой сочленения называется вершина, удаление которой нарушает связность графа. Если подграф является двусвязным, то для него выполняется требование (14), поэтому следует найти

граничные значения р:, которые обеспечивали бы сокращение количества вариантов размещений шлюзов следующим образом

1</),""п< д. </>""<«,, (17)

где рГ'\рГ — минимально и максимально возможное количество шлюзов, которое может покрывать компоненту связности г;

Граница //"'" определяется из предположения, что каждый шлюз будет передавать сообщения от максимально возможпого количества узлов сети. Пусть V? — упорядоченный массив, содержащий степени вершин v 6 Vi, которые отсортированы по убыванию, т.е. deg v, > deg v2 >... > deg vn . Через V будем обозначать вспомогательную переменную, содержащую количество покрытых шлюзом узлов. Тогда с использованием псевдокода процедура поиска р"™ может быть записана следующим образом. PminKompSv(txmlix, и , V') 1

2 F'<—О

3 while V' < и

4 do <— р™ш +1

5 У'<-0

6 for f/ <— 1 to р'"'п

7 do V <^V'+V'[q\txm%

8 return

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

В четвертом разделе предложены различные алгоритмы для решения задачи оптимального размещения шлюзов в сети навигационных знаков. Показана NP-полнота задачи и предложен точный алгоритм (ТА) для поиска оптимального варианта размещения. Точный

(п\

алгоритм на основе метода последовательного переоора, вычисляет /ФП{х) для всех

Ы

возможных вариантов размещения р шлюзов, начиная с минимального значения р. Инкремент р выполняется до тех пор, пока не найдется вариант с fa,,, (х) == 0. Данный алгоритм позволяет получать точные значения целевых функций для рассматриваемых задач. Время работы точного алгоритма является экспоненциальным. Существование точного алгоритма с полипомиалъпьтм временем работы для решения jVP-полных задач маловероятно. Таким образом, целесообразно сосредоточить усилия па разработке эвристических алгоритмов, позволяющих получать решения близкие к оптимальным за приемлемое время. Эвристический алгоритм может не иметь доказательства корректности получаемых результатов и при этом возвращать достаточно «хорошие» решения в большинстве случаев. Представлены результаты вычислительного эксперимента, позволяющие сравнить точность и скорость работы полученных алгоритмов.

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

Пусть С, — множество хромосом поколения г. Тогда каждую хромосому будем

кодировать в виде п-мерного вектора бинарных элементов с.еС,,где / = {1...|С,|} и каждый ген

принимает значения из множества {0, 1}. Блок-схема генетического алгоритма для решения задачи размещения шлюзов приведена па рисунке 4.

Рисунок 4 — Генетический алгоритм оптимального размещения шлюзов в сети

В блоке 1 целесообразно воспользоваться процедурой PminKompSv, с помощью которой можно вычислить минимально возможное количество шлюзов ртт в сети. Далее каждая хромосома исходной популяции создается путем случайного размещения pmin шлюзов. Функция Cross в блоке 2 обеспечивает создание хромосом потомков С' путем обмена генетического материала между родителями из С,. В данной реализации оператора скрещивания при одноточечном разрезе хромосом точка определяется случайным образом. Выбор особей, участвующих в формировании потомства, производится с использованием модели «колеса рулетки», в которой каждой хромосоме выделяется сектор, по размеру пропорциональный значению ее приспособленности. Одно «колесо рулетки» используется для выбора родителя 1 по значению /иФ(с:) и другое «колесо рулетки» для выбора родителя 2 по

значению /ФП(с:) при / = [l...|C,|}. Подобный подход обеспечивает разнообразие генетического

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

Функция Mut в блоке 3 выполняет частичное скачкообразное преобразование хромосомы случайным образом. Особь подвергается мутации с вероятностью q. В данном алгоритме происходит случайный выбор позиции гена, подвергаемого мутации, и инвертируется его значение. Преждевременная сходимость алгоритма может бьгть исключена повышением вероятности мутации q. После выполнения оператора скрещивания существует вероятность появления недопустимых решений в числе новых хромосом, поэтому если для хромосомы ; выполняется неравенство /да(с;)< р^, то происходит ее корректировка путем добавления Ртп ~/цф (с<) шлюзов на случайные позиции.

Функция Recomb в блоке 4 выполняет формирование нового поколения из числа хромосом текущей популяции и хромосом потомков. В данном алгоритме применяется элитарный механизм отбора. Для каждой хромосомы из С, и С' вычисляется суммарное значение (с,.) = fm (с,.) + /ФП (с. ). В повое поколение / + 1 переходят |С,| хромосом с минимальным значением /¿(с,). В результате «хорошие» особи из текущей популяции и

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

Работа алгоритма продолжатся до по луче пня некоторого оптимального решения (глобального или локального), поэтому в качестве критерия останова в блоке 5 выбрано условие, при котором в поколении / +1 все хромосомы имеют одинаковые значения /j. (с. ), т.е. алгоритм не может улучшить получаемые решения.

Алгоритм муравьиной колонии (АМК) является вероятностной реализацией приближенного «жадного» алгоритма с использованием глобального информационного поля, содержащего статистические данные. Взаимодействие муравьев осуществляется с помощью феромона — специального химического вещества, откладываемого ими в процессе перемещения для того, чтобы пометить пройденный путь. Как правило, каждый муравей делает выбор в пользу пути, на котором концентрация феромона более высокая, чем на других возможных направлениях. Чем короче путь, тем больше муравьев успевает по этому пути пройти и, соответственно, оставить больше феромона. Чем больше феромона на пути, тем больше муравьев будет включать фрагменты этого пути в свой маршрут в процессе поиска. В результате, со временем, все муравьи начинают передвигаться по кратчайшему пути.

Решение, получаемое муравьем г будем представлять в виде пройденного пути и кодировать в виде вектора бинарных элементов а , характеризующего схему размещетгая шлюзов в сети, при этом через V' будем обозначать множество шлюзов, выбраттых муравьем /. С каждым шагом муравья г в векторе я. будет происходить инвертирование одного элемента со значением 0. Качество решения, полученного муравьем, будем оценивать по количеству шлюзов = р,. Через г„(/) будем обозначать количество феромона на узле у в момент интерации I. На рисунке 5 приведена блок-схема АМК.

При инициализации переменных в блоке 1 установка начального количества феромона Т„(0 на узлах необходима для корректного выполнения процедуры при / — 1.

Количество муравьев в алгоритме равно количеству узлов в сети я, поэтому каждый муравей устанавливается на отдельный узел, который служит отправной точкой в маршруте. Искусственный муравей двигается от начата до конца своего пути, который считается пройденным, если выполняется условие/<рп(а|) = 0. Каждый шаг муравья выполняется путем добавления одного шлюза в сеть. Шаг могут выполнять только те муравьи, у которых полученное решение еще не соответствует требованию (13) или функция пригодности не может быть рассчитана.

Функция Аш81ер в блоке 2 выполняет один шаг муравья, путем модификации вектора а. инвертированием одного элемента со значением 0. Для выбора преобразуемого узла используется механизм вероятностно-пропорционального выбора на основе модели «колеса рулетки», где размеры секторов пропорциональны значению вероятности преобразования q[ каждой вершины. Значение д[ для каждого узла вычисляется по формуле

я',=-

1

Е к")Г

1

Г, (18)

гДе /фп(а,у) — функция пригодности для вектора а. в случае выбора вершины V в качестве шлюза;

от,/?— константы, определяющие «вес» соответствующих параметров.

После запуска рулетки определяется преобразуемый узел V и выполняются следующие операции: /фп(а.) <— /ФП(а1г); Ур <-и {у}. Таким образом, в решение каждого муравья, не дошедшего до конца своего маршрута, добавляется один шлюз.

Функция РИегирс1ше в блоке 3 обеспечивает адаптивное поведение алгоритма, изменяя информацию о количестве феромонов на вершинах по формуле

гу(г + 1) = ^гД0 + Е—' уеК- С9)

где /„ — множество муравьев i, для которых у е Ур ; у/ — коэффициент испарения феромона;

О — количество феромона, откладываемого муравьем при прохождении своего пути от начала до конца.

Со временем всем муравьям требуется одинаковое количество шагов по наиболее обогащенным феромоном узлам для прохождения своего пути, что сигнализирует о схождешш алгоритма. Данное условие выбрано в качестве критерия останова в блоке 4 для рассматриваемого АМК.

Значения параметров подбираются экспериментальным путем, что является

одним из недостатков алгоритма. При а = 0 атгоритм становится «жадным», а при /? = 0

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

Рисунок 5 — Алгоритм муравьиной колонии для задачи оптимального размещения

шлюзов в сети

Оценка разработанных алгоритмов была проведена на основе эмпирических данных. Поскольку разработанные эвристические алгоритмы являются вероятностными и получают приближенные решения, цель проводимого эксперимента заключается в выяснении скорости их работы и оценки погрешности их решений. Для проведения вычислительного эксперимента автором была разработана программа в среде Borland С++ Builder 6. Эксперимент проводился па ПК с процессором Intel Atom с тактовой частотой 1,67 ГГц. Серия запусков алгоритмов проводилась на связных графах, сгенерированных случайным образом. В эксперименте рассматривался точный алгоритм (ТА), ГА и АМК. Результаты экспериментов для ГА получены при следующих значениях параметров: q = 0,6 ; [ С, |= 150. Результаты экспериментов для АМК получены при следующих значениях параметров: а = 2; ß = 1; Q = 2; цг = 0,6 . Для каждого значения параметров п и tcmax было выполнено 100 запусков ГА и АМК. В таблице 1 приведено минимальное время /тш, потраченное каждым алгоритмом на нахождение оптимального решения по значению /,1Ф(х). Оптимальные значения целевой функции получены в результате работы ТА. Следует заметить, что сложность задачи размещения шлюзов зависит не только от количества узлов в сети, но и от значения параметра tx . Чем меньше значение данного параметра, тем больше шлюзов следует разместить в сети и больше схем размещения следует рассмотреть в процессе поиска.

Таблица 1 — Экспериментальная оценка скорости работы алгоритмов

п /да. О), усл. ед. ¿min-. С

ТА ГА АМК

40 4 4 1,279 0,468 1,903

40 3 6 106,268 0,765 5,179

40 2 7 2481,165 0,593 8,424

60 5 4 7,941 0,780 13,603

60 4 5 489,266 1,467 27,565

60 3 7 12292,630 1,575 34,008

80 7 4 45,911 1,591 32,183

80 6 4 181,538 2,059 39,827

80 5 5 1820,142 1,638 49,531

80 4 6 10613,793 2.013 76,549

100 12 4 67,845 2,169 70,809

100 11 4 307,696 2,528 79,966

100 10 5 1677,307 2,652 108,827

100 9 5 1726,510 2,808 116,190

100 8 6 33440,483 3,416 153,365

100 7 6 311591,358 — 170,025

Как видно из таблицы 1 задачи могут быть разделены на четыре группы по значению п. В каждой группе наблюдается рост времени получения решения с уменьшением значения 1хтт в подавляющем большинстве случаев для всех алгоритмов. Подобное явление можно объяснить ростом пространства решений с увеличением п и уменьшением количества допустимых решений с уменьшением £хшах- В таблице 2 приведены данные, позволяющие получить представление о точности разработанных эвристических алгоритмов. Параметр Ы* используется для обозначения доли оптималышх решений в процентном соотношении из общего числа решений, полученных алгоритмом при 100 запусках. Через и стах обозначаются средняя и максимальная относительная погрешность соответственно.

Таблица 2 — Экспериментальная оценка точности алгоритмов

п Р ГА АМК

1ч[*,% £„, % е„4., % Етах^

80 7 4 69 7,75 25 94 1,5 25

80 6 4 28 18,8 50 64 9 25

80 5 5 16 17,2 40 38 12,4 20

80 4 6 42 10,3 33,3 65 5,8 16,7

100 12 4 59 10,3 25 100 0 0

100 11 4 25 18,8 25 38 15,5 25

100 10 5 76 4,8 20 99 0,2 20

100 9 5 26 15,6 40 86 2,8 20

100 8 6 29 12,5 33,3 42 9,7 16,7

100 7 6 0 25 50 5 18 33,3

Задача с входными параметрами и = 100,Ьстах =7 оказалась достаточно сложной для решения. Алгоритму муравьиной колонии удалось найти оптимальное решение только на 5 запусках из 100, а генетическому алгоритму не удалось найти оптимального решения на всех запусках. Подобный результат можно объяснить недостаточным размером популяции для данной задачи. Для некоторых задач значение £тах достаточно высоко. Данное явление можно объяснить тем, что оптимальные значения целевой функции относительно малы и могут быть только целочисленными. По результатам экспериментов видно, что разработанные алгоритмы способны найти оптимальное решение за приемлемое время для большинства предлагаемых параметров задач. Ключевым достоинством ГА по сравнению с АМК можно назвать более высокую скорость получения решений. Однако, в большинстве случаев, АМК вырабатывает больше оптимальных решений, чем ГА, о чем свидетельствуют значения И* и еау алгоритмов. С ростом количества узлов в сети общая скорость получения решений в АМК падает быстрее, чем в ГЛ. Подобное явление объясняется тем, что для модификации значения /фп{а() на одном шаге одного муравья требуется выполнить п — р. вычислений значения т.е.

трудоемкость каждого шага муравья растет пропорционально значению п. В генетическом алгоритме для модификации /фп(с,)требуется выполнить 2 вычисления /фп{с-)'. для хромосомы текущей популяции С, и хромосомы потомка из С",.

Для ГА значения параметров, при которых проведен эксперимент являются достаточными для получения оптимальных решений в большинстве случаев, при этом увеличение значения параметра | С, | обеспечивает рост точности алгоритма. Для АМК!, представленного в данной работе, значения настраиваемых параметров, при которых проводился эксперимент, являются оптимальными. Разработанные алгоритмы позволяют получать оптимальные решения задачи размещения шлюзов за приемлемое время, что свидетельствует о перспективности их изучения и применения.

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

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

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕР ТАЦИИ

Работы, опубликованные автором в перечне ведущих рецензируемых научных журналов и изданий, рекомендованных ВАК:

1. Шейкин Т.Ю. Современные проблемы проектирования систем удаленного мониторинга СНО // Эксплуатация морского транспорта. — 2012. — №4 (70). — С. 24-28.

2. Шейкин Т.Ю. Применение технологии сенсорных сетей в системе мониторинга судоного навигационного оборудования // Журнал университета водных коммуникаций. — 2013. — №3 (19). — С. 122-130.

3. Шейкин Т.Ю. Генетический и муравьиный алгоритмы для задачи размещения шлюзов в сети навигационных знаков // Вестник государственного университета морского и речного флота имени адмирала С.О. Макарова. — 2013. — №3 (22). — С. 14-19.

В других изданиях:

4. Шейкин Т.Ю. Проблемы развития дистанционного мониторинга и управления СПО // Научно-техническая конференция профессорско-преподавательского состава, научных сотрудникон и курсантов: тезисы докладов. — Ч. 1. — СПб.: Изд-во ГМА им. адм. С.О. Макарона, 2012. — С. 293-294.

5. Шейкин Т.Ю. Генетический и муравьиный алгоритмы для задачи размещения шлюзов в сенсорной сети системы мониторинга навигационных знаков // Наука и образование в современной конкурентной среде: материалы Международной научно-практической конференции: в 3-х ч. Часть II. —Уфа: РИО ИЦИПТ, 2014. — С. 170-177.

Подписано в печать с оригинал-макета автора 29.09.14 Сдано в производство 29.09.14 Формат 60x84 1/16 Усл.-печ. л. 1,16. Уч.-изд. л. 1. _Тираж 65 экз._Заказ № 92_

Государственный университет морского и речного флота имспн адмирала С. О. Макарова 19X035, Санкт-Петербург, ул. Двинская, 5/7

Отпечатано в типографии ФГБОУ ШЮ ГУМРФ имени адмирала С. О. Макарова 198035, Санкт-Петербург, Межевой канал, 2