Введение к работе
Актуальность темы. В настоящее время одним из новых актуальных направлений в области информационных технологий является создание нового вида сетевых систем -сенсорных сетей (СС). Сенсорная сеть - это распределенная сеть необслуживаемых миниатюрных электронных устройств (узлов сети), которые осуществляют сбор данных о параметрах внешней среды и передачу их на базовую станщпо посредством ретрансляции от узла к узлу с помощью беспроводной связи. Сенсорная сеть размещается на ограниченной территории и по современным оценкам может содержать до 65000 узлов.
Сети этого класса представляют большой интерес с точки зрения их применения в таких важных областях, как автоматизация управления распределенными объектами, автоматизация систем жизнеобеспечения, выявление и предупреждение чрезвычайных ситуаций, контроль грузопотоков, мониторинг транспортных магистралей (в том числе, железных дорог, нефте- и газопроводов, сетей энерго- и теплоснабжения и др.), антитеррористическая деятельность, военные приложения и др.
Исследования и разработки в области СС интенсивно ведутся за рубежом, причем результаты этих исследований уже используются в конкретных приложениях. В России также начаты разработки таких сетей.
Проектирование и реализация сенсорных сетей требуют решения множества сложных проблем, относящихся к различным областям исследований. Одной из основных проблем является обеспечение высокой отказоустойчивости СС. Важность этой проблемы именно для сенсорных сетей определяется, с одной стороны, ответственностью их применений, а с другой - высокой вероятностью нарушения работы сети вследствие отказов узлов и каналов связи, что обусловлено большим количеством узлов, возможностью внешних неблагоприятных воздействий, а также ограничениями в энергопотреблении узлов вследствие ограниченности ресурса их источников питания (батарей).
Процесс проектирования отказоустойчивой сенсорной сети (ОУ СС) является
достаточно сложным. Он не формализован в виде жесткого набора правил, алгоритмов и
стандартов, выполнение которых гарантирует построение СС, удовлетворяющей
требованиям к ее структурной надежности, энергоэффективности и стоимости. К
настоящему времени разработан ряд методов и алгоритмов решения отдельных задач,
возникающих в процессе проектирования ОУ СС, однако эти методы обладают
существенными ограничениями, препятствующими их применению при построении
сложных структур СС. Они не учитывают некоторые важные особенности СС, такие как
возможность отказа сети как вследствие выхода из строя ее компонентов, так и вследствие
исчерпания энергоресурсов автономных источников питания узлов сети. Кроме того,
отсутствует общее представление всего процесса проектирования ОУ СС, которое
пределяло бы место в этом процессе тех или иных существующих и вновь
азрабатываемых методов и служило бы основой для построения системы проектирования
УСС.
К основным проблемам, требующим решения при построении такой системы, тносятся: разработка алгоритмов синтеза базовой и избыточной структуры СС, горитмов оценки структурной надежности СС (особенно для СС, имеющих высокую тепень связности), алгоритмов оценки общего времени работы СС до момента ее отказа. В вязи с этим представляется актуальной разработка алгоритмов построения тказоустойчивой СС и функциональной схемы процесса ее проектирования. Решению тих задач и посвящена настоящая диссертационная работа. Она базируется на результатах юдыдуших исследований отечественных и зарубежных ученых в области теории,
надежности, в особенности теории структурной надежности сетей связи (Гнеденко В.Б., Дружинин Г.В., Барлоу Р., Прошан Ф., Ушаков И.А., Литвак Е.И., Гадасин В.А., Филин Б.П., Шуман М, Тилманн Ф.А., Полесский В.П. и др.), и сенсорных сетей (Листер К., Куллер Д.Е., Стойменович И., Кучерявый А.Е., Виллинг А., Калавей Э., Санти П. и др.).
Цели работы и задачи исследования. Целью диссертационной работы является разработка и исследование алгоритмов построения отказоустойчивых сенсорных сетей и функциональной схемы процесса проектирования таких сетей, а также их практическая реализация в виде инструментального программного обеспечения. Для достижения поставленной цели в диссертационной работе решаются следующие задачи.
-
Разработка алгоритмов вычисления связности структуры СС и структурной энергоэффективности.
-
Разработка и исследование алгоритмов построения отказоустойчиво" структуры СС, отвечающей требованиям к ее связности и структурно" энергоэффективности.
-
Разработка и исследование алгоритма формирования расписания доступа беспроводную СС с целью повышения ее энергоэффективности.
-
Разработка процедуры имитационного моделирования работы СС осуществляющей периодический сбор информации, с целью получения верхней оцет общего времени работы СС до момента ее отказа с учетом как отказов компонентов узла так и разрядки батареи.
-
Разработка функциональной схемы процесса проектирования ОУ СС с учето требований к ее связности и энергоэффективности.
-
Разработка инструментального программного комплекса поддержі проектирования отказоустойчивых СС на основе предложенных алгоритмов функциональной схемы процесса проектирования.
Методы исследования. Для достижения цели диссертационной работа использованы методы теории надежности технических систем, теории графов, теорі сложности алгоритмов, теории искусственного интеллекта, теории нечетких множеств теории вычислительных систем, вычислительной математики и программирования современные методологии построения программных комплексов.
Научная новизна диссертации заключается в следующем:
-
Применение предложенных алгоритмов базового размещения транзитных узло сенсорной сети позволяет с увеличением плотности равномерного распределен функциональных узлов уменьшить число размещенных транзитных узлов по сравнению существующими алгоритмами TPRR(Trivial Placement Reusing Routers) и CRP(Cluste Router Placement). Так, в исследуемом диапазоне дальности уверенной переда радиосигнала узлами сенсорной сети 30 + 450л<, выигрыш составляет 5-35% при плотное равномерного распределения функциональных узлов р 2:1.6*10"* [Ф-узла/м2].
-
Разработаны алгоритмы размещения транзитных узлов сенсорной сети, позволяющи уменьшить на 6-25% число размещенных транзитных узлов, необходимых для достижен заданной степени связности СС, по сравнению с существующим алгоритмом NTRI (Non-trivial Redundant Router Placement). Применение предложенного алгоритма ОУ-упрощает процесс размещения транзитных узлов на реальном объекте по сравнению алгоритмом NTRRP.
-
Разработана процедура имитационного моделирования работы по расписага сенсорной сети периодического сбора информации. Процедура позволяет получа верхнюю оценку общего времени работы сенсорной сети до момента ее отказа с учетом к отказов компонентов узла, так и разрядки батареи, что дает возможность сравнивать п
этому критерию структуры СС, полученные с помощью различных алгоритмов. С помощью процедуры имитационного моделирования показано, что резервирование транзитных узлов СС с учетом интенсивности их энергопотребления позволяет повысить структурную энергоэффективность СС и тем самым увеличить общее время работы СС до момента ее отказа.
Практическая ценность и реализация результатов работы.
Разработана функциональная схема процесса построения отказоустойчивых сенсорных сетей, позволяющая во взаимодействии с проектировщиком выполнить следующие основные этапы процесса проектирования ОУ СС: выбор используемых узлов СС, сегментацию СС на кластеры, выбор используемых алгоритмов проектирования, формирование базовой и ОУ структуры СС, экспертную оценку надежности и стоимости СС, выбор и внедрение алгоритмов обеспечения энергоэффективности, имитационное моделирование, комплексную экспертную оценку СС. На базе предложенных алгоритмов и функциональной схемы построения ОУ СС разработан инструментальный программный комплекс, который может применяться для построения СС, предназначенных для ответственных применений и требующих повышенной надежности. Разработанная система зарегистрирована в отделе регистрации программ ЭВМ, баз данных и топологий ИМС Федерального института промышленной собственности РОСПАТЕНТа (свидетельство № 2009615483 от 02.10.2009).
Результаты диссертационной работы использованы в научно-производственной работе ОАО «Институт точной механики и вычислительной техники им. С. А. Лебедева РАН», в ЗАО Зонд-Холдинг, а также в учебном процессе кафедры МКиИТ МТУ СИ, что подтверждено соответствующими актами.
Апробация результатов. Основные положения диссертационной работы
бсуждались на Международной научно-технической конференции по интеллектуальным
истемам и интеллектуальным САПР AIS/CAD-08, 2-й Московской отраслевой
онференции «Технологии информационного общества» МТУСИ 2008, Международном
онгрессе по интеллектуальным системам и информационным технологиям '09, 3-й
осковской отраслевой конференции «Технологии информационного общества» МТУСИ
009, Международном конгрессе по интеллектуальным системам и информационным
ехнологиям «AIS-ІТ'Ю», 19-й научно-технической конференции «Системы
"езопасности» - СБ-2010 Международного форума информатизации, всероссийской
аучно-технической конференции «Безопасные информационные технологии»,
еждународной научно-технической конференции INTERMATIC-2010.
Публикация. Основные результаты диссертации изложены в 14 опубликованных аботах (из них 6 работ - в рецензируемых журналах, рекомендованных ВАК инобрнауки России).
Структура и объем работы. Диссертация состоит из введения, четырех глав, аключения, библиографического списка из 129 наименований и приложений. Работа одержит 160 страниц, 64 рисунка, 34 таблицы и 2 приложения. Основные положения, выносимые на защиту:
