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



МОЧАЛОВ ВЛАДИМИР АНАТОЛЬЕВИЧ

РАЗРАБОТКА И ИССЛЕДОВАНИЕ АЛГОРИТМОВ ПОСТРОЕНИЯ ОТКАЗОУСТОЙЧИВЫХ СЕНСОРНЫХ СЕТЕЙ

Специальность: 05.12.13 - Системы, сета и устройства телекоммуникаций

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата технических наук

о з 013 2311

МОСКВА 2011

4853680

Работа выполнена на кафедре Автоматизации информационных технологий и сертификации в связи Государственного образовательного учреждения высшего профессионального образования Московский технический университет связи и информатики (МТУСИ)

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

доктор технических наук, с.н.с., Турута Евгений Николаевич

Официальные оппоненты:

доктор технических наук, профессор, Кучерявый Андрей Евгеньевич

Ведущая организация:

кандидат технических наук, с.н.с., Бельфер Рувим Абрамович

Открытое акционерное общество «Институт точной механики и вычислительной техники им. С. А. Лебедева РАН»

Защита состоится «17» февраля 2011 г. в 15 часов на заседании совета по защите докторских и кандидатских диссертаций Д 219.001.03 при МТУ СИ по адресу: 111024, Москва, ул. Авиамоторная, д. 8а, ауд. А-455

С диссертацией можно ознакомиться в библиотеке МГУ СИ Автореферат разослан « » ^¿¿с^/^г^р 2011 г.

Учёный секретарь совета по защите докторских и кандидате» диссертаций

к.т.н. доцент Ерохин С. Д.

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

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

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

Исследования и разработки в области СС интенсивно ведутся за рубежом, причем результаты этих исследований уже используются в конкретных приложениях. В России также начаты разработки таких сетей.

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

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

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

надежности, в особенности теории структурной надежности сетей связи (Гнеденко В.Б., Дружинин Г.В., Барлоу Р., Прошан Ф., Ушаков И.А., Лювак Е.И., Гадасин В.А., Филин Б.П., Шуман М., Тилманн Ф.А., Полесский В.П. и др.), и сенсорных сетей (Листер К., Куллер Д.Е., Стойменович И., Кучерявый А.Е., Виллинг А., Калавей Э., Санти П. и др.).

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

1. Разработка алгоритмов вычисления связности структуры СС и структурной энергоэффективности.

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

3. Разработка и исследование алгоритма формирования расписания доступа беспроводную С С с целью повышения ее энергоэффективности.

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

5. Разработка функциональной схемы процесса проектирования ОУ СС с учето требований к ее связности и энергоэффективности.

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

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

Научная новизна диссертации заключается в следующем:

1. Применение предложенных алгоритмов базового размещения транзитных узло сенсорной сети позволяет с увеличением плотности равномерного распределен функциональных узлов уменьшить число размещенных транзитных узлов по сравнению существующими алгоритмами TPRR(Trivial Placement Reusing Routers) и CRP(Cluste Router Placement). Так, в исследуемом диапазоне дальности уверенной переда' радиосигнала узлами сенсорной сети 30 + 450л», выигрыш составляет 5-35% при плотное равномерного распределения функциональных узлов /»>1.6*10^ [Ф-узла/м2].

2. Разработаны алгоритмы размещения транзитных узлов сенсорной сети, позволяющи уменьшить на 6-25% число размещенных транзитных узлов, необходимых для достажен заданной степени связности СС, по сравнению с существующим алгоритмом NTRI (Non-trivial Redundant Router Placement). Применение предложенного алгоритма ОУ-упрощает процесс размещения транзитных узлов на реальном объекте по сравнению алгоритмом NTRRP.

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

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

Практическая ценность и реализация результатов работы.

Разработана функциональная схема процесса построения отказоустойчивых сенсорных сетей, позволяющая во взаимодействии с проектировщиком выполнить следующие основные этапы процесса проектирования ОУ СС: выбор используемых узлов СС, сегментацию СС на кластеры, выбор используемых алгоритмов проектирования, формирование базовой и ОУ структуры СС, экспертную оценку надежности и стоимости СС, выбор и внедрение алгоритмов обеспечения энергоэффективности, имитационное моделирование, комплексную экспертную оценку СС. На базе предложенных алгоритмов и функциональной схемы построения ОУ СС разработан инструментальный программный комплекс, который может применяться для построения СС, предназначенных для ответственных применений и требующих повышенной надежности. Разработанная система зарегистрирована в отделе регистрации программ ЭВМ, баз данных и топологий ИМС Федерального института промышленной собственности РОСПАТЕНТа (свидетельство № 2009615483 от 02.10.2009).

Результаты диссертационной работы использованы в научно-производственной работе ОАО «Институт точной механики и вычислительной техники им. С. А. Лебедева РАН», в ЗАО Зонд-Холдинг, а также в учебном процессе кафедры МКиИТ МТУ СИ, что подтверждено соответствующими актами.

Апробация результатов. Основные положения диссертационной работы бсуждались на Международной научно-технической конференции по интеллектуальным истемам и интеллектуальным САПР AIS/CAD-08, 2-й Московской отраслевой онференции «Технологии информационного общества» МТУСИ 2008, Международном онгрессе по интеллектуальным системам и информационным технологиям '09, 3-й осковской отраслевой конференции «Технологии информационного общества» МТУСИ 009, Международном конгрессе по интеллектуальным системам и информационным ехнологиям «AIS-IT'10», 19-й научно-технической конференции «Системы "езопасности» - СБ-2010 Международного форума информатизации, всероссийской аучно-технической конференции «Безопасные информационные технологии», еждународной научно-технической конференции INTERMATIC-2010.

Публикация. Основные результаты диссертации изложены в 14 опубликованных аботах (из них 6 работ - в рецензируемых журналах, рекомендованных ВАК инобрнауки России).

Структура и объем работы. Диссертация состоит из введения, четырех глав, аключения, библиографического списка из 129 наименований и приложений. Работа одержит 160 страниц, 64 рисунка, 34 таблицы и 2 приложения.

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

1. Разработанные алгоритмы базового размещения транзитных узлов дают ущественный выигрыш (до 35%) по числу размещенных транзитных узлов по сравнению с уществующими алгоритмами TPRR и CRP, причем этот выигрыш возрастает с величением плотности равномерного распределения функциональных узлов.

2. Предложенные алгоритмы избыточного размещения транзитных узлов даюг выигрыш а 6-25% по числу размещенных транзитных узлов по сравнению с существующим

горитмом NTRRP.

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

4. Применение предложенного алгоритма резервирования транзитных узлов с учетом интенсивности их энергопотребления позволяет повысить энергоэффективность СС и тем самым увеличить общее время работы СС до момента ее отказа.

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

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении обосновывается актуальность темы исследования, формулируют« цели и задачи диссертационной работы, основные положения, выносимые на защиту перечисляются используемые в работе методы исследования, раскрывается научна] новизна и практическая значимость результатов работы.

В первой главе диссертации «Сенсорные сети и задачи их проектирования! рассматриваются сенсорные сети как объект проектирования.

Сенсорные сети строятся на основе протоколов IEEE 802.15.4, ZigBee и DigiMesh Функционально сенсорная сеть содержит узлы трех видов: (1) функциональные узль (Ф-узлы), осуществляющие сбор информации в некоторой окрестности точки размещени данного узла; (2) транзитные узлы (Т-узлы), выполняющие только передачу информации управление маршрутизацией; (3) базовые станции (ВС), осуществляющие глобальну! координацию, организацию и установку параметров сети (рисунок 1).

Сенсорная сеть может быть организована как совокупность подсетей (кластеров связанных координаторами или шлюзами взаимодействия «сенсорная сеть - корпоративна1 сеть». Функционально к базовым станциям отнесем координатор PAN и шлза

Рисунок 1 - Сенсорная сеть как объект проектирования Основными целями, на которые ориентировано большинство предложенных до с» нор методов размещения узлов, являются: увеличение связности узлов СС, зоны покрыл и общего времени работы сети до момента ее отказа и точности собранных данных.

Задача увеличения общего времени работы СС сводится к улучшению энергоэффективности (ЭЭ) структуры СС. Энергоэффективность структуры СС при заданном множестве ее функциональных узлов {/)/}, / = /,..., к; определяется набором длительностей сбора информации БС Тр от каждого из узлов заданного множества {О/}. Время работы каждого узла СС напрямую связано с его энергопотреблением. Основными энергозатратными операциями узлов СС являются прием и передача пакетов информации.

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

Задачу обеспечения отказоустойчивости СС можно сформулировать двумя пособами.

(А). Классическая постановка задачи оптимизации: спроектировать структуру СС, оторая обеспечивает надежность (т.е. вероятность связности) > 0>' и нергоэффективность (ЭЭ) Е>Е', где значения \\ Е' заданы заказчиком, при инимизации стоимости С всей структуры СС, т.е. при С —> Опт.

(Б). Постановка задачи в терминах нечетких множеств: спроектировать структуру С, которая обеспечивает: "высокую надежность" (или "очень высокую надежность", 'приемлемую надежность" и т.д.); "высокую ЭЭ" (или "очень высокую ЭЭ", "среднюю Э" и т.д.); "низкую стоимость" (или "очень низкую стоимость", "приемлемую стоимость" I т.д.). В отличие от классической оптимизационной задачи проектирования использование еханизма нечеткой экспертной оценки дает результат в виде процента удовлетворения ебований к проектируемой СС, что обеспечивает мягкость в выборе структуры СС. тсутствие мягкости в принятии решения может выразиться, в частности, в том, что труктура СС не будет выбрана (или предложена проектировщику как одно из решений) з-за невыполнения одного из требований на малый процент от желаемой величины при еликолепных показателях, характеризующих выполнение других требований. Следует одчеркнуть, что постановка задачи (А) является частным случаем задачи (Б), так как «четкие множества требований в задаче (Б) могут быть заданы жестко.

В работе рассматривается задача обеспечения отказоустойчивости СС в постановке

Б).

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

По результатам главы сформулированы задачи исследования диссертационной аботы.

Во второй главе диссертации «Исследование и разработка алгоритмов величения структурной надежности сенсорной сети» предлагаются алгоритмы оценки обеспечения структурной надежности СС по критерию ее связности.

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

В качестве показателя надежности как узла, так и канала связи принята вероятность их безотказной работы в течение интервала времени Т (заданной наработки) при условии, что узлы и каналы являются невосстанавливаемыми, а их отказы независимы. Вероятность р„,(Т) безотказной работы узла в течение времени Т определяется вероятностью безотказной работы структуры узла р,(Т) и вероятностью не разрядки в течение этого времени батареи питания узла рь(Т). Считаем, что вероятности безотказной работы узлов и каналов СС заданы; известны также дальности уверенной радиосвязи и стоимости узлов СС.

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

Надежность структуры СС при заданном множестве ее функциональных узлов

{О/}, / = 1..... к, определяется набором значений вероятностей связности Рр каждого из

узлов ' заданного множества {И/} с базовой станцией. В качестве показателя надежности структуры СС принято минимальное из этих значений Ррб = пип {Р/ь},/ = !>■••. к, где Я/, вычисляется для заданной наработки Т, т.е. Рр= Р//Т), а для получения оценки Р'ь? этого показателя предлагается использовать нижние оценки вероятностей связности узлов множества {О/} с базовой станцией, т.е. Ррз = тт{/^},/ = 1 ,...к.

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

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

Нижняя оценка вероятности связности некоторого Ф-узла ^ с БС вычисляется как: /',-(7-£у,где <2р - вероятность того, что все НП от данного Ф-узла ^ к БС н работоспособны:

ГК> (О

где дкр - вероятность того, что данный НП цкр между Ф-узлом Рс и БС неработоспособен с/'р — 1 - рк/3, где ркр% - вероятность того, что к-й независимый путь ¡хр между Ф-узлом

БС работоспособен, определяемая как вероятность работоспособного состояния всех каналов и всех Т-узлов, образующих этот путь, т.е.

р> П Р,, ПР.. (2)

где рт и ptj - вероятности работоспособного состояния (т.е. отсутствия отказа), соответственно, Т-узла Ът и канала c,j (между некоторшш узлами bt и bj); С*/3 - множество всех каналов, входящих в путь цifß - множество всех узлов, входящих в путь fikp.

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

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

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

требуемой связностью (что достигается введением в базовую структуру СС избыточных I-узлов с целью формирования требуемого числа путей от каждого Ф-узла к БС).

В работе предлагаются модификации существующих алгоритмов TPRR (алгоритм АЗ-1) и CRP (алгоритм БАЗ-2). В алгоритмах БАЗ-1 и CRP перед выполнением основных агов предложено осуществить сортировку Ф-узлов следующим образом: в случае низкой ютности распределения Ф-узлов - сортировать узлы по критерию близости их азмещения к БС; в случае высокой плотности распределения Ф-узлов - сортировать узлы о критерию дальности их размещения от БС. Отличия алгоритма БАЗ-2 от CRP аключаются: (1) в способе объединения Ф-узлов в группы (предлагается алгоритм 'УПП-!); (2) в способе установки центрального Т-узла в группу (предлагается станавливать центральный Т-узел в центр масс Ф-узлов группы); (3) в изменении оследовательности построения базовой структуры СС таким образом, что первоначально ентралыше Т-узлы связываются с БС по алгоритму БАЗ-1, после чего Ф-узлы вязываются с ближайшим Т-узлом или БС с помощью алгоритма БАЗ-1. В алгоритме АЗ-2 предлагается формировать группы таким образом, чтобы расстояние между любыми -умя Ф-узлами одной и той же группы не превышало величины D и количество Ф-узлов уппы превышало значение к.

Решения, полученные с помощью алгоритмов базового размещения Т-узлов, могут ьпъ не оптимальными. Так, некоторые Т-узлы могут быть удалены, при этом Ф-узлы станутся связанными с БС. Для определения Т-узлов, которые могут быть удалены, . едоожено выполнить следующую процедуру: (1) создать отсортированный по критерию лизости к БС массив Ф-узлов Mf, (2) создать пустое множество задействованных узлов Oy добавить в него БС; (3) в цикле для каждого Ф-узла FcgMf осуществить поиск одного атчайшего по числу ретрансляций маршрута от данного узла Fc до узлов Tzs £Ту, после его добавить Т-узлы найденного маршрута в множество Oy, (4) удалить из структуры СС -узлы, не принадлежащие множеству Oy. Поскольку кратчайших (по числу ретрансляций) утей от данного Ф-узла до узлов множества Oy может быть несколько и выбор одного из их является случайным, процедуру оптимизации базовой структуры СС целесообразно оводить рекурсивно к раз, на каждой итерации оптимизируя получившуюся на едыдущем шаге структуру СС. Если за m итераций (т < к) не было удалено ни одного

Т-узла, то процедуру оптимизации следует остановить. Параметры т и к устанавливаются проектировщиком.

Результаты экспериментального исследования алгоритмов базового размещения (БАЗ-1, БАЗ-2 и описанный ниже алгоритм ОУ-3 с количеством НП к=\) показаны на рисунках 2 и 3 (при дальности уверенной радиосвязи узлов СС £>=50м). Результаты получены для следующей тестовой задачи: Ф-узлы случайным образом размещаются на объекте прямоугольной формы (2000м х 1100м), исследуемый диапазон: 30 < £) < 450л<. Базовая станция установлена в точке с координатами (496м, 1009м). Результаты полного экспериментального исследования приведены в выводах второй главы.

Рисунок 2 - Зависимость количества Рисунок 3 - Зависимость времени работы размещенных Т-узлов от исходного алгоритмов базового размещения от

количества Ф-узлов (для различных исходного количества Ф-узлов

алгоритмов базового размещения)

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

Алгоритм ОУ-1 разработан в результате исследования и модификации существующего алгоритма NTRRP (Non-trivial Redundant Router Placement) обеспечения k-связности структуры сенсорной сети. Этот алгоритм позволяет сократить количество Т-узлов, необходимых для обеспечения k-связности, и уменьшить время выполнения алгоритма по сравнению с NTRRP.

Алгоритм ОУ-2, основанный на применении генетических алгоритмов (ГА), позволяет осуществить построение избыточной структуры СС при учете требований к вероятности связности ее Ф-узлов с БС и стоимости внедрения. Сенсорная сеть представляется в виде двумерной сетки [Ы х М], "покрывающей" объект ее размещения, где N - число рядов (строк), а М - число столбцов. На пространстве, соответствующем каждой ячейке сетки, может быть либо размещен какой-либо узел СС (функциональный или транзитный), либо не размещен никакой узел. Интерпретируя нашу задачу в терминах ГА, введем следующие определения. Популяция - множество возможных структур СС. Хромосома - структура СС. Каждая хромосома состоит из N генов. Ген соответствует строке сетки, покрывающей СС, и состоит из М ячеек, соответствующих ячейкам сетки. Значением каждой ячейки гена является число к элементарных узлов, размещенных на пространстве, соответствующем одноименной ячейке сетки. Структура СС, соответствующая требованиям проектировщика, находится с помощью выполнения процедуры ГА (последовательности генетических операторов).

Структуры СС, полученные с помощью вышеописанных алгоритмов ОУ-размещения -узлов, могут быть не оптимальными: удаление из них некоторых Т-узлов может не инвеста к уменьшению достигнутой степени связности Ф-узлов с БС. Для определения -узлов, которые могут бьгть удалены, выполняется следующий алгоритм оптимизации: 1) создать массив Т-узлов Мт, отсортированный по критерию наибольшего расстояния до С; (2) в цикле каждый Т-узел Тс<=Мт временно изъять из структуры СС, после чего существить оценку структуры СС по какому-либо из критериев (вероятность связности, оличество НП от каждого из Ф-узлов к БС, энергоэффекгивность структуры СС). Если без ременно изъятого узла Тс оценка структуры СС удовлетворяет проектировщика, то Тс даляется из сети навсегда. Для уменьшения времени работы алгоритма ОУ-оптимизации в аботе предлагается сохранять в хэш-таблицах и повторно использовать на последующих ерациях независимые пути от Ф-узлов к БС.

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

Результаты экспериментального исследования алгоритмов ОУ-размещения (МПШР, У-1, ОУ-3 и ОУ-1 совместно с процедурой ОУ-оптимизации) показаны на рисунках 4 и 5 при дальности уверенной радиосвязи В=60и). Результаты получены для следующей стовой задачи: 400 Ф-узлов случайным образом размещаются на о&ьекте квадратной

независимые маршруты

исунок 4 - Зависимость количества Рисунок 5 - Зависимость времени работы

размещенных Т-узлов от степени алгоритмов ОУ-размещения от степени

связности при 0=60м связности при Б=60м

В таблицах 1-3 приведены результаты экспериментального исследования зисимосги количества размещенных Т-узлов от степени связности (числа НП) при спользовании рассматриваемых алгоритмов ОУ-размещения при £>=100м и различной отностир равномерного распределения Ф-узлов.

Результаты полного экспериментального исследования приведены в выводах второй

авы.

Таблица 1. Зависимость количества размещенных Т-узлов от степени связности при

£>=100м и р = 4.08 * 10"

Ф-узла/м ]

Алгоритмы ОУ-размещения п=2 п=3 п=4 п=5 п=6 п=7 п=8

NTRRP 33 51 63 78 91 107 125

ОУ-1 33 47 58 74 86 97 112

ОУ-1 (Опт) 29 47 55 69 82 91 107

ОУ-3 25 41 47 61 81 88 104

Таблица 2. Зависимость количества размещенных Т-узлов от степени связности при £>=100м и р = 2.04 * 10~4 [Ф-узла/м2] _

Алгоритмы ОУ-размещения п=2 п=3 11=4 п=5 п=6 п=7 п=8

NTRRP 52 82 111 131 158 184 212

ОУ-1 52 71 96 119 131 157 188

ОУ-1 (Опт) 42 65 89 100 119 140 169

ОУ-3 41 63 78 97 122 135 158

Таблица 3. Зависимость количества размещенных Т-узлов от степени связности при Д=100м и /> = 8,16*10"" [Ф-узла/м2] __

Алгоритмы ОУ-размещения п=2 п=3 п=4 п=5 п=6 п=7 п=8

NTRRP 78 129 163 205 243 252 275

ОУ-1 78 110 140 160 195 231 257

ОУ-1 (Опт) 54 82 110 130 165 185 213

ОУ-3 50 74 92 116 144 157 184

В заключении к главе делаются следующие выводы:

1. Предложенный алгоритм вычисления нижней оценки вероятности связности Ф-узлов СС с БС позволяет оценивать и сравнивать различные структуры СС большой размерности и высокой степени связности.

2. Разработанные алгоритмы базового размещения транзитных узлов с увеличением плотности равномерного распределения функциональных узлов дают выигрыш по числу размещенных транзитных, узлов по сравнению с существующими алгоритмами TPRR и CRP. Так, в исследуемом диапазоне дальности уверенной передачи радиосигнала узлами сенсорной сети 30 -г- 450л/, выигрыш составляет 5-35% при плотности равномерного распределения функциональных узлов р > 1.6* 10" [Ф-узла/м2].

3. В алгоритмах БАЗ-1 и CRP способ сортировки Ф-узлов относительно БС существенно влияет на количество размещенных Т-узлов.

4. Разработанный алгоритм БАЗ-2 не уступает алгоритму CRP по количеству размещенных Т-узлов при плотности равномерного распределения функциональных узлов р< 4.55*10"' [Ф-узла/м2] и превосходит алгоритм CRP на 5-42% при р 2; 4.55 *10~' [Ф-узла/м2].

5. Разработанные алгоритмы избыточного размещения транзитных узлов дают выигрыш на 6-25% по числу размещенных транзитных узлов по сравнению с существующим алгоритмом NTRRP.

6. Применение предложенного алгоритма ОУ-3 упрощает процесс размещения транзитных узлов на реальном объекте по сравнению с алгоритмом NTRRP.

В третьей главе диссертации «Разработка алгоритмов увеличения общего ремени работы сенсорной сети до момента ее отказа» предлагаются: алгоритм ормироваиия расписания доступа в беспроводную СС, обеспечивающий увеличение бщего времени работы СС и минимизацию конфликтов при передаче сообщений; горим увеличения структурной энергоэффективности СС; процедура имитационного оделирования работы по расписанию сенсорной сети периодического сбора информации, озволяющая получить верхнюю оценку общего времени работы до момента отказа СС с етом как отказов компонентов узла, так и разрядки батареи.

Алгоритм ЭЭ-1 - алгоритм резервирования Т-узлов с учетом интенсивности их нергопотребления. Под интенсивностью энергопотребления (ИЭ) Т-узла понимается ело ретрансляций, осуществляемых этим узлом за один период сбора информации со сех Ф-узлов и ее передачи на БС. Очевидно, величина ИЭ зависит от числа маршрутов ередачи информации от Ф-узлов к БС, проходящих через данный Т-узел в течение анного периода сбора информации. Указанное число маршрутов, в свою очередь, зависит т числа независимых путей от различных Ф-узлов к БС, проходящих через данный Т-узел.

В работе предложены два алгоритма оценки ИЭ Т-узлов (алгоритмы ОЭ-1 и ОЭ-2), озволяющие получать численные оценки структурной ИЭ Т-узлов и сравнивать азличные структуры СС по этому показателю, не проводя при этом процедуру литационного моделирования работы СС. Оценка ИЭ 1Ес некоторого Т-узла Тс на первом 1апе алгоритма ОЭ-1 определяется как:

1

1=1 «(

е Мгс - множество Ф-узлов, независимые пути от которых к БС проходят через Т-узел с, к, - количество НП от Ф-узлаМге/'У к БС.

На втором этапе алгоритма ОЭ-1 формируются группы Т-узлов таким образом, чтобы бой Т-узел группы имел равное множество смежных узлов (не являющихся членами уппы) с другими Т-узлами группы. Оценки ИЭ Т-узлов каждой сформированной группы редняются.

В алгоритме ОЭ-2 осуществляется учет различных комбинаций НП от Ф-узлов к БС, зволяющий получить более точную оценку ИЭ Т-узлов. В качестве структурной оценки Э всей СС может быть использовано максимальное значение оценки ИЭ из всех Т-узлов.

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

Алгоритм ЭЭ-1 осуществляет добавление в структуру СС нового Т-узла в точку мещения Т-узла с наивысшей вычисленной оценкой ИЭ. Алгоритм ЭЭ-1 повторяется курсквно, т.е. на каждой итерации используется полученная на предыдущем шаге уктура СС. Алгоритм ЭЭ-1 завершается при достижении требуемой структурной оценки всейСС.

Алгоритм ЭЭ-2 - алгоритм формирования расписания доступа в беспроводную СС, еспечивающий увеличение общего времени работы СС до момента ее отказа и шмизацшо конфликтов, возникающих в общей беспроводной среде во время ювремешюй передачи сообщений двумя узлами. Этот алгоритм разработан на основе ализа существующих алгоритмов доступа к радиоканалу. Предлагаемый алгоритм ЭЭ-2

может быть применен в качестве программной надстройки над IEEE 802.15.4 в сенсорных сетях периодического сбора информации.

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

Установка и переконфигурирование расписания

Использование расписания

Выбранные маршруты

Выбор

маршрутов

Загрузка маршрутов н расписания

Использование расписания узлами СС

Построение расписания

^Нельзя построить расписание Этказ узла-

Рисунок 6 - Диаграмма состояний СС при ее работе на основе расписаний Входными данными для этого алгоритма являются: количественные параметр узлов СС; Ор- множество всех Ф-узлов; От- множество всех транзитных ЕГО-узлов; В( у) - координаты БС; Д. - множество выбранных координатором маршрутов от Ф-узлов БС (каждый элемент е£\ - это последовательный список узлов маршрута переда сообщения от Ф-узла I к БС); <3(У,Е) - структура СС, представленная в виде графа, где V множество узлов СС, а Е - множество ребер между узлами СС, которые находятся в зон радиовидимости друг друга. Данный алгоритм последовательно для каждого Ф-уз Р, естроит расписание работы как самого ^, так и узлов множества!^, составляющ маршрут от узла к БС. В процессе последовательного формирования расписаний д узлов СС алгоритм устанавливает запреты на передачу сообщений по ребрам графа й определенные моменты времени. Эти запреты устанавливаются с целью устранен конфликтов, возникающих в общей беспроводной среде. Правила установки запретов пр передаче узлом / сообщения узлу у в момент времени /и длительностью передачи Дг (т.е. интервал времени [1; I + Дг]) следующие: установить запрет на передачу по всем ребрам инцидентным узлу у, установить запрет на передачу по всем ребрам, инцидентным узлу / установить запрет на передачу сообщений по всем исходящим ребрам узлов, смежных узлом у, установить запрет на передачу сообщений по всем входящим ребрам узло смежных с узлом

На каждом шаге формирования расписаний работы узлов маршрута Ьг (от Ф-узла к БС) строится такое расписание передачи сообщений через узлы этого маршрута, которо

я

минимизирует текущее значение функции энергопотребления узлов СС: ^Гя. (где и

ело узлов СС, a E¡ — суммарная энергия, потребляемая узлом i за один период сбора формации с СС) с учетом ограничений на время доставки сообщения от Fc на БС. начение Е, определяется как:

(4)

/=О

де I¡j - ток, потребляемый узлом / в состоянии, соответствующем дискретному моменту ремени t/, Ду - интервал времени нахождения узла i в состоянии, соответствующем скретному моменту времени I/, U- напряжение питания узла СС.

Узел СС переходит в сон, если непрерывный временной интервал Д^в расписании аботы узла между двумя его активными состояниями (приема или передачи) превышает аксимум следующих двух величин:

> max(ABU + Ад,Im,Amj +/дАд ) (5)

^ RX "IlDLB

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

ромосома состоит из N генов, где N - это количество Ф-узлов (|QF|). Ген содержит еловой индекс, связанный с Ф-узлом.

Важным параметром, характеризующим СС, является время работы СС до момента отказа. Для оценки значения этого параметра предлагается применять разработанную в аботе процедуру имитационного моделирования (ИМ) работы беспроводной СС, существляющей периодический сбор информации по расписанию. Процедура ИМ снована на применении алгоритма ЭЭ-2 и учитывает отказы узлов, возникающие как ледствие отказов их компонентов, так и вследствие разрядки их батарей. Для аппаратных азов компонентов узлов СС справедлив экспоненциальный закон надежности ггенсивность аппаратных отказов компонентов X=const).

Результаты экспериментального исследования алгоритмов повышения ергоэффективности показаны на рисунке 7 (при D=60м).

|-МО 1/час -»- Л=0.0000а881/час - - - А=0.0800Ш 1/час — - Л=О.ООООМЭ 1/час]

° '5 5000 2 5 4500

5 О 4000

О 3500

о. Я 3000

^ 5 2500

о 2000 m я 1500

<U -Т-

Ш 5 1000 М 2 500

<о о

О 2 0

О 50 100 150 200 250 300 350 400 450

Кол-во зарезервированных Т-узлов

Рисунок 7 - Зависимость общего времени работы СС до момента отказа от количества зарезервированных Т-узлов при различных X. Результаты получены для следующей тестовой задачи: 30 Ф-узлов случайным разом размещаются на объекте квадратной формы(700м х 700м). С помощью алгоритма

ОУ-3 осуществляется построение трехсвязной структуры СС. Цель эксперимента заключалась в поиске зависимости общего времени работы СС до момента ее отказа от количества Т-узлов, зарезервированных с помощью алгоритма ЭЭ-1. Принятое значение критерия отказа СС: I = 12 (информация с / Ф-узлов не может быть доставлена на БС). Результаты имитационного моделирования показали, что алгоритм ЭЭ-1 позволяет с учетом ограничений существенно увеличить показатель общего времени работы к-связной сенсорной сети на единицу стоимости по сравнению с алгоритмами увеличения количества независимых путей к базовой станции.

В заключении к главе делаются следующие выводы:

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

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

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

В четвертой главе диссертации «Разработка функциональной схемы процесса проектирования отказоустойчивых сенсорных сетей и ее реализация инструментальном комплексе поддержки проектировщика» предлагаете функциональная схема процесса проектирования ОУ СС (рисунок 8), являющаяся вместе разработанными алгоритмами построения ОУ СС основой интеллектуальной системь поддержки проектирования (ИСПП) отказоустойчивых СС. Разработанный программны" комплекс реализует предложенные принципы построения ИСПП ОУ СС и позволяет в взаимодействии с проектировщиком выполнить основные этапы процесса проектирован! ОУ СС и сократить время расчетов. Проведен анализ применимости и эффективное« разработанной системы на примере сквозного проектирования СС.

Наиболее общие исходные данные для процесса проектирования СС: масы координат функциональных узлов СС; координата размещения базовой станции; описани объекта, на котором должна быть размещена сенсорная сеть (его размеры, схем размещения); Т - период сбора информации Ф-узлами с СС; Дтр - допустимое отклонени

периода сбора информации; критерий отказа СС.

Функциональный блок выбора компонентов СС осуществляет (согласно требования проектировщика) подбор компонентов для проектируемой СС из базы данных, содержаще1 набор совместимых друг с другом типов узлов. Используемая в расчетах дальность уверенной передачи радиосигнала узла (км) определяется как:

D = 10 20 20 , (6

где FSL (free space lose) - потери в свободном пространстве (дБ); F — центральная частот канала, на котором работает узел (МГц).

Рисунок 8 - Функциональная схема процесса проектирования ОУ СС

Функциональный блок сегментации СС на кластеры формирует кластеры на основе данного размещения Ф-узлов и требований к сети, а также осуществляет размещение БС утри каждого кластера. Кластеры формируются с помощью выбранного оектировщиком алгоритма кластеризации (ГРУПП-1, к-теапв, алгоритма иерархической астеризации, алгоритма кластеризации методами теории графов).

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

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

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

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

В работе предлагается использовать механизм нечеткого логического вывода для осуществления оценок различных параметров СС, таких как надежность, стоимость, общее время работы, а также для комплексной оценки структуры СС. Реализация данного механизма основывается на применении коэффициентов достоверности (КД) в экспертно" системе (ЭС) Drools, что позволяет получать результаты экспертных оценок в вид процента удовлетворения требований проектировщика. В языке ЭС Drool непосредственно не предусмотрена возможность работы с КД, поэтому в работе разработа механизм учета КД параметров СС, основанный на реализации программной надстройки н языке Java.

Основными реализованными компонентами ИСПП являются: модул взаимодействия с проектировщиком (пользовательский интерфейс); модуль вычислен] дальности уверенной передачи радиосигнала по характеристикам узла; модуль сохранеш и загрузки рабочего проекта; модуль осуществления кластеризации СС (алгоритмь ГРУПП-1, k-means, иерархической кластеризации); модуль построения базовой структурь СС (алгоритмы TRC, БАЗ-1, БАЗ-2); модуль вычисления вероятности связности меж; Ф-узлами и БС; модуль оптимизации базовой структуры СС; модуль построеш избыточной и энергоэффективной структуры СС (алгоритмы ОУ-1, ОУ-3, ЭЭ-1); модул демонстрации интенсивности энергопотребления узлов СС; модуль оптимизащ отказоустойчивой структуры СС; модуль формирования расписания доступа беспроводную СС (алгоритм ЭЭ-2); модуль имитационного моделирования работы СС п расписанию; модуль интеграции с ЭС Drools; модуль осуществления нечеткой экспертно оценки параметров СС; модуль тестирования и сравнения результатов работы алгоритмов.

В рассматриваемой прикладной задаче требуется разработать ОУ СС предназначенную для мониторинга лесного массива на предмет появления возгорания

определенной области с целью предотвращения пожара. В качестве объекта размещения СС рассмотрен российский национальный парк Лосиный остров (прикладная задача и исходные данные для сквозного проектирования ОУ СС были предоставлены Институтом точной механики и вычислительной техники им. Лебедева РАН). Под отказом структуры СС понимаем событие, приводящее СС в состояние, при котором достоверная информация с 40% Ф-узлов не может быть доставлена на базовую станцию.

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

Спроектированная с помощью ИСПП структура ОУ СС показан на рисунке 1. Эта СС состоит из 20 кластеров, в каждом кластере внедрены стратегии ОУ и ОЭЭ. Общее количество размещенных Т-узлов во всех кластерах равно 1110. Общее количество БС кластеров равно 38. Общая стоимость всех узлов СС равна 16830$. При проведении имитационного моделирования СС проработала до момента отказа 47112 часов. Коэффициент достоверности того, что спроектированная ОУ СС является высоконадежной, знергоэффективной и имеет "низкую стоимость" был вычислен с помощью нечеткой комплексной экспертной системы и оказался равным 0.985.

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

В заключении представлены основные результаты работы.

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

2.Разработаны и реализованы алгоритмы базового размещения транзитных узлов сенсорной сети, позволяющие с увеличением плотности равномерного распределения функциональных узлов уменьшить число размещенных транзитных узлов по сравнению с существующими алгоритмами TPRR и CRP. Так, в исследуемом диапазоне дальности уверенной передачи радиосигнала узлами сенсорной сети 30 + 450л(, выигрыш составляет 5-35% при плотности равномерного распределения функциональных узлов р>1.6*10~* [Ф-узла/м2].

3.Разработаны и реализованы алгоритмы избыточного размещения транзитных узлов сенсорной сети, позволяющие уменьшить на 6-25% число размещенных транзитных узлов, необходимых для достижения заданной степени связности СС, по сравнению с существующим алгоритмом NTRRP.

4.Разработан и реализован алгоритм формирования расписания доступа в беспроводную СС, обеспечивающий увеличение общего времени работы СС до момента ее

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

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

етом как отказов компонентов узла, так и разрядки его батареи.

6.Разработан и реализован алгоритм резервирования транзитных узлов СС с учетом ггенсивности их энергопотребления. Алгоритм позволяет повысить структурную

энергоэффективность СС и тем самым увеличить общее время работы СС до момента ее отказа.

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

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

9.Разработана интеллектуальная система поддержки проектирован отказоустойчивых сенсорных сетей (ИСПП ОУ СС), реализующая разработанные диссертации алгоритмы и функциональную схему построения ОУ СС. Инструментальны программный комплекс может быть применен при разработке сложных сенсорных сете ответственного назначения. Проведен анализ применимости этого комплекса на пример сквозного проектирования СС. Разработанная ИСПП ОУ СС зарегистрирована в отдел регистрации программ ЭВМ, баз данных и топологий ИМС Федерального институ промышленной собственности РОСПАТЕНТа (свидетельство № 2009615483 от 02.10.2009)

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации в изданиях, рекомендованных ВАК

1.Мочалов В.А. Построение расписания доступа в беспроводную сенсорную сеть / Электросвязь. — 2009. —№10. — С.36-40.

2.Мочалов В. А. Алгоритмы размещения транзитных узлов в сенсорной сети / Информационные технологии. —2009 — №10. — С. 18-23.

3.Мочалов В. А. Алгоритмы оценки надежности структуры сенсорной сети Информационно-управляющие системы. — 2009. — №5. — С. 61-66.

4.Мочалов В.А. Алгоритмы увеличения общего времени работы сенсорной сети д момента ее отказа // Приборы и системы. Управление, контроль, диагностика. — М. "НАУЧТЕХЛИТИЗДАТ", 2010. — №7. — С. 12-19

5.Мочалов В.А., Турута E.H. Функциональная схема процесса проектирован беспроводных сетей мониторинга // Датчики и системы. — 2010. — №2. — С.40-44.

6. Мочалов В.А, Турута E.H. Сквозное проектирование отказоустойчивой сенсорной сети помощью интеллектуальной СППР // T-Comm, 2010, — № 10. — С. 24-28.

Прочие публикации

1.Мочалов В.А., Турута E.H. Метод построения отказоустойчивой структуры сенсорно сети, основанный на применении генетического алгоритма // T-Comm. Спецвыпус Часть 1.Технологии информационного общества. — июнь 2009. — С.63-66.

2.Мочалов В.А., Турута E.H.. Интеллектуальная САПР сенсорных сетей // Труды конгресс по интеллектуальным системам и информационным технологиям «AIS-IT'09». Научно издание в 4-х томах. — М.: Физматлит, 2009. — Т. 3. — С. 268-276.

3.Мочалов В.А., Турута E.H. Интеллектуальная процедура выбора отказоустойчиво топологии и компонентов сенсорной сети // Труды Международных научно-техничесм

конференций «Интеллектуальные системы» (AIS'08) и «Интеллектуальные САПР (CAD'2008). — М.: Физматлит, 2008. — Т. 1. — С. 385-392.

4.Турута E.H., Мочалов В.А. Проблемы проектирования отказоустойчивых сенсорных сетей // Труды Московского технического университета связи и информатики: М.: "ИД Медиа Паблишер", 2008. — Т.1 — С. 128-132.

5.Мочалов В.А, Турута E.H. Нечеткая экспертная оценка параметров сенсорной сети // , уды Конгресса по интеллектуальным системам и информационным технологиям «AIS-Т'10». Научное издание в 4-х томах. - М.: Физматлит, 2010. — Т. 3. — С. 185-193.

. Мочалов В.А, Турута E.H. Стратегии размещения узлов сенсорной сети // труды VII еждународной тучно-технической конференции INTERMATIC-2010. — 2010.— часть 3. С. 211-216.

. Мочалов В.А. Обеспечение энергетической безопасности сенсорных сетей // сборник зисов докладов всероссийской научно-технической конференции "Безопасные формационные технологии". — М.: НИИ PJIМГТУ им. Н.Э.Баумана, 2010. — С. 57-59. .Мочалов В.А. Свидетельство о государственной регистрации программы для ЭВМ 'Интеллектуальная система поддержки проектирования отказоустойчивых сенсорных етей" № 2009615483 от 02.10.2009.

Подписано в печать 23.12.10. Формат 60x84 1/16. Объем 1,5 усл.п.л. Тираж 100 экз. Заказ 255.

ООО «Брис-М». Москва, Варшавское шоссе, д. 37А. 21

Введение.

ГЛАВА 1. Сенсорные сети и задачи их проектирования.

1.1 Структура и функционирование сенсорных сетей.

1.2 Стратегии размещения узлов в сенсорной сети.'.:.

1.3 Задача построения отказоустойчивой сенсорной сети.

1.4 Обзоринтеллектуальных технологий, применяемых для проектирования сенсорных связи.:.

1.5 Основные существующие подходы к обеспечению отказоустойчивости сенсорных сетей.:.

1.6 Выводы.

ГЛАВА 2. Исследование н разработка алгоритмов увеличения структурной надежности сенсорной сети.43?

2.1 Разработанный алгоритм оценки структурной надежности сенсорной сети.

2.2 Исследование и разработка алгоритмов базового размещения транзитных узлов сенсорной сети.

2.3 Исследование и разработка алгоритмов избыточного размещения транзитных узлов сенсорной1 сети.

2.4 Выводы.:.

ГЛАВА 3. Разработка алгоритмов увеличения общего времени работы сенсорной сети до момента ее отказа.;.

3.1 Алгоритм увеличения.структурной энергоэффективности сенсорной сети.

3.2 . Алгоритмгформирования расписания доступа в беспроводную сенсорную; сеть

3.3 Оценка общего времени работы сенсорной сети до»момента ее отказах помощью процедуры имитационного моделирования.102:

3.4 Выводы1 .;.108'

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

4.1 Функциональная схема процесса проектирования отказоустойчивых сенсорных сетей.

4.2 Экспертная оценка структурной надежности, энергоэффективности и стоимости сенсорной сети.

4.3 Применение разработанных алгоритмов и инструментального программного комплекса при проектировании отказоустойчивой сенсорной сети.

Выводы.

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

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

Исследования и разработки в области СС интенсивно* ведутся за рубежом, причем результаты этих исследований уже используются в конкретных приложениях. В,России также начаты разработки таких сетей.

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

Процесс проектирования отказоустойчивой сенсорной сети (ОУ СС) является достаточно сложным. Он не формализован в виде жесткого набора правил, алгоритмов и стандартов, выполнение которых гарантирует построение СС, удовлетворяющей требованиям к ее структурной надежности, энергоэффективности и стоимости. К настоящему времени разработан ряд методов и алгоритмов решения отдельных задач, возникающих в процессе, проектирования ©У СС,. однако- эти? методы обладают существенными ограничениями, препятствующими? их применению при построении сложных структур СС. Они не учитывают некоторые, важные особенности СС, такие как возможность отказа сети как.вследствие выхода', из строя ее компонентов, так и вследствие исчерпания» энергоресурсов автономных источников питания узлов сети: Кроме того, отсутствует общее представление всего процесса проектирования ОУ СС, которое определяло бы место; в этом; процессе тех или иных существующих и вновь разрабатываемых методов и служило бы основой: для построения«системы, проектирования ©У ОС.

К основным проблемам, требующим решения- при построении такой системы, относятся: разработка алгоритмов; синтеза базовой и отказоустойчивой структуры СС, алгоритмов оценки структурной надежности: СС (особенно, для: СС, имеющих высокую степень, связности),, алгоритмов оценки общего времени работы, СС. до момента ее отказа. В связи с этим 1 федставляется актуальной разработка алгоритмов1 построения отказоустойчивой СС и функциональной, схемы процесса« ее проектирования. Решению: этих задач: и посвящена настоящая; диссертационная? работа. Она базируется« на результатах предыдущих исследований отечественных и зарубежных ученых в области теории надежности, в особенности; теории, структурной надежности сетей связи (Гнеденко В.Б., Дружинин Г.В., Барлоу Р., Прошан Ф., Ушаков И.А., Литвак- Е.И., Гадасин В .А., Филин Б.П., Шуман М:, Тилманн. Ф.А., Полесский В1П. и др.), и сенсорных сетей (Пистер К., Куллер Д.Е., Стойменович И., Кучерявый А.Е., Виллинг А., Калавей Э., Санти II. и др.).

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

1. Разработка алгоритмов вычисления связности структуры СС и структурной энергоэффективности.

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

3. Разработка и исследование алгоритма формирования расписания доступа в беспроводную СС с целью повышения ее энергоэффективности.

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

5. Разработка функциональной схемы процесса проектирования ОУ СС с учетом требований к ее связности и энергоэффективности.

6. Разработка инструментального программного комплекса поддержки' проектирования отказоустойчивых СС на основе предложенных алгоритмов и функциональной схемы процесса проектирования.

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

Научная новизна диссертации заключается в следующем: 1. Применение предложенных алгоритмов базового размещения- транзитных узлов сенсорной сети позволяет с увеличением плотности равномерного распределения'функциональных узлов уменьшить число размещенных транзитных узлов по сравнению с существующими алгоритмами TPRR(Trivial Placement Reusing 6

Routers) и CRP(Cluster Router Placement). Так, в исследуемом диапазоне дальности уверенной передачи радиосигнала узлами сенсорной сети 30-*- 450л/, выигрыш составляет 5-35% при плотности равномерного распределения функциональных узлов р> 1.6*10^ [Ф-узла/м2].

2. Разработаны алгоритмы размещения транзитных узлов сенсорной сети, позволяющие уменьшить на 6-25% число размещенных транзитных узлов, необходимых для достижения заданной степени связности СС, по сравнению- с существующим алгоритмом NTRRP(Non-trivial Redundant' Router Placement). Применение предложенного алгоритма ОУ-3 упрощает процесс размещения, транзитных узлов на реальном объекте по сравнению с алгоритмом NTRRP.

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

Практическая ценностью реализация результатов работы.

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

Разработанная интеллектуальная система поддержки проектирования ОУ СС зарегистрирована в отделе регистрации программ ЭВМ, баз данных и топологий ИМС Федерального института промышленной собственности РОСПАТЕНТа (свидетельство № 2009615483 от 02.10.2009).

Результаты диссертационной работы использованы в научно-производственной работе ОАО «Институт точной механики и вычислительной техники им. С. А. Лебедева РАН», в ЗАО Зонд-Холдинг, а также в учебном процессе кафедры МКиИТ МТУ СИ, что подтверждено соответствующими актами.

Апробация результатов. Основные положения диссертационной работы обсуждались на Международной научно-технической конференции по интеллектуальным системам и интеллектуальным САПР AIS/CAD-08, 2-й Московской отраслевой конференции «Технологии информационного общества» МТУСИ 2008, Международном конгрессе по интеллектуальным системам и информационным технологиям '09, 3-й Московской отраслевой конференции «Технологии информационного общества» МТУСИ 2009, Международном конгрессе по интеллектуальным системам и информационным технологиям «AIS-IT'10», 19-й научно-технической конференции «Системы безопасности» - СБ-2010 Международного форума информатизации, всероссийской научно-технической конференции «Безопасные информационные технологии», Международной научно-технической конференции INTERMATIC-2010.

Публикация. Основные результаты диссертации изложены в 14 опубликованных работах (из них 6 работ - в рецензируемых журналах, рекомендованных ВАК Минобрнауки России).

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, библиографического списка из 129 наименований и приложений* Работа содержит 160 страниц; 64 рисунка, 34 таблицы и 2 приложения.

Основные результаты диссертационной работы:

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

2. Разработаны и реализованы алгоритмы базового* размещения, транзитных узлов, сенсорной сети, позволяющие с увеличением плотности равномерного распределения функциональных узлов уменьшить число размещенных транзитных узлов по сравнению с существующими алгоритмами TPRR' и CRP. Так,, в исследуемом диапазоне дальности уверенной передачи» радиосигнала узлами сенсорной сети 30 + 450л*, выигрыш составляет 5-35% при плотности равномерного распределения функциональных узлов р > 1.6 * 10~* [Ф-узла/м2].

3. Разработаны, и реализованы алгоритмы избыточного размещения транзитных узлов сенсорной- сети, позволяющие уменьшить на 6-25% число размещенных транзитных узлов, необходимых для достижения заданной степени связности СС, по сравнению с существующим алгоритмом NTRRP.

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

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

6. Разработан» и реализован алгоритм резервирования транзитных узлов СС с учетом интенсивности их энергопотребления. Алгоритм позволяет повысить структурную

131 энергоэффективность СС и тем самым увеличить общее время работы СС до момента ее отказа.

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

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

9. Разработана интеллектуальная система поддержки проектирования отказоустойчивых сенсорных сетей (ИСПП ОУ СС), реализующая разработанные в диссертации алгоритмы и функциональную схему построения ОУ СС. Инструментальный программный комплекс может быть применен при разработке сложных сенсорных сетей ответственного назначения. Проведен анализ применимости этого комплекса на примере сквозного проектирования СС. Разработанная ИСПП ОУ СС зарегистрирована в отделе регистрации программ ЭВМ, баз данных и топологий ИМС Федерального института промышленной собственности РОСПАТЕНТа (свидетельство № 2009615483 от 02.10.2009).

10. Результаты диссертационной работы использованы в научно-производственной работе ОАО «Институт точной механики и вычислительной техники им. С. А. Лебедева РАН», в ЗАО Зонд-Холдинг, а также в учебном процессе кафедры МКиИТ МТУСИ, что подтверждено соответствующими актами.

ЗАКЛЮЧЕНИЕ

1. Nitaigour, P.M. (Editor) Sensor networks and configuration fundamentals, standards, platforms, and applications / P.M. Nitaigour // Springer. — 2007. — 510 p.

2. Кучерявый, E.A. Принципы построения сенсоров и сенсорных сетей / Е.А. Кучерявый, С.А. Молчан, В.В. Кондратьев // Электросвязь, 2006. — №6 — С.10-15.

3. Молчанов, Д.А. Приложения беспроводных сенсорных сетей / Д.А. Молчанов, Е.А. Кучерявый // Электросвязь, 2006. — №6 — С.20-23.

4. Майская, В. Беспроводные сенсорные сети, малые системы — большие баксы / В. Майская // Электроника: Наука, Технология, Бизнес. — 2005. — №10. — С. 18-22.

5. Таненбаум, Э. Компьютерные сети / Э. Таненбаум — Спб. : Питер, 2003 — 992 с.

6. Варгаузин, В.А. Сетевая технология ZigBee / В.А. Варгаузин // ТелеМультиМедиа. — 2005. — №6. — С. 29-32.

7. Сергиевский, М. Беспроводные сенсорные сети / М. Сергиевский // КомпьютерПресс. — 2007. — №10.

8. Прокопьев, A.B. Перспективы использования протокола 6L0WPAN в сетях IEEE 802.15.4 / A.B. Прокопьев // Электросвязь, 2009. — №1 — С.33-36.

9. Семенов, Ю.А. Телекоммуникационные технологии. URL: http://book.itep.ru/ (дата обращения: 22.02.2010).

10. Gutierrez, J., Callaway, Е., Barrett, R. Low-Rate Personal Area Networks: Enabling Wireless Sensors with IEEE 802.15.4 — IEEE — ISBN 0-7381-3557-7 — 2003.

11. Стандарт беспроводной связи ZigBee / URL: http://www.zigbee.org (дата обращения: 17.07.2009).

12. Сетевой протокол DigiMesh / URL: http://www.digi.com/technology/digimesh/ (дата обращения: 07.07.2010).

13. Технология ZigBee / URL: http://www.spectronvideo.ru/zigbee.html (дата обращения: 07.08.2009).

14. Варгаузин, В.А. Радиосети для сбора данных от сенсоров, мониторинга и управления на основе стандарта ШЕЕ 802.15.4 / В.А. Варгаузин // ТелеМультиМедиа. — 2005. — №6.

15. Кучерявый, А.Е. Самоорганизующиеся сети и новые услуги / А.Е. Кучерявый // Электросвязь, 2009. — №1 С. 19-23.

16. Сергиевский, М. Беспроводные сенсорные сети. Часть 2. // КомпьютерПресс,2008. — №4 / URL: http://www.compress.ru/article.aspx?id=18943&iid=877 (дата обращения: 17.03.2010).

17. Пушкарев, О. ZigBee-модули ХВее: новые возможности / О. Пушкарев // Беспроводные технологии. — 2008. — №4. — С. 22-25.

18. Беспроводные системы на базе сенсорных сетей для автоматизации объектов нефтяной промышленности / URL: http://www.ipmce.ru/img/release/oil.pdf (дата обращения: 07.08.2009).

19. Турута, E.H. Проблемы проектирования отказоустойчивых сенсорных сетей / E.H. Турута, В.А. Мочалов // Труды Московского технического университета связи и информатики. — М. : "ИД Медиа Паблишер", 2008. — Т. 1. — С. 128132.

20. Гургенидзе, А. u-общество: вездесущая связность или тотальная слежка? / А. Гургенидзе // ИКС. — 2005. — №12.

21. Мочалов В.А, Турута E.H. Стратегии размещения узлов сенсорной сети / В.А. Мочалов // труды VII Международной научно-технической конференции INTERMATIC-2010. — 2010. — часть 3. — С. 211-216.

22. Мочалов, В.А. Алгоритмы размещения транзитных узлов в сенсорной сети / В.А. Мочалов // Информационные технологии. — М.: "Новые технологии",2009. —№10. —С. 18-23.

23. Нао, В. Fault-Tolerant Relay Node Placement in Wireless Sensor Networks: Formulation and Approximation / Нао В., Tang J., Guoliang X. // Proceedings of the Workshop on High Performance Switching and Routing (HPSR'04). — Phoenix, Arizona, 2004.

24. Tang, J. Relay Node Placement in Large Scale Wireless Sensor Networks / Tang J., Нао В., Sen A. // Computer Communications, special issue on wireless sensor networks. — 2006. — Vol. 29. — P. 490-501.

25. Ishizuka, M. Performance Study of Node Placement in Sensor Networks / Ishizuka M., Aida M. // Proceedings of the 24th International Conference on Distributed Computing Systems Workshops. — W7: EC (Icdcsw'04). — Hachioji, Tokyo, Japan, 2004. —Vol. 7.

26. Райншке, К. Оценка надежности систем с использованием графов / К. Райншке, И.А. Ушаков // М. : Радио и связь, 1988. — С. 15-39.

27. Надежность технических систем : Справочник // под ред. И.А. Ушакова. — М. : Радио и связь, 1985. — 608 с.

28. Берж, К. Теория графов и ее приложения. / К. Берж // М. : ИЛ, 1962. — 320 с.

29. Кристофидес, Н. Теория графов. Алгоритмический подход. // Н. Кристофидес //М. :Мир, 1978. —429 с.

30. Diestel, R. Graph Theory / R. Diestel // Springer-Verlag, Heidelberg, 2005. — P. 55-80.

31. Горский, Л.К. Статистические алгоритмы исследования надежности. / Л.К. Горский//М. : Наука, 1970.

32. Ломоносов, М.В. Нижняя оценка надежности сетей / М.В. Ломоносов, В.П. Полесский // Пробл. передачи информации. — 8:2 — 1972. — С. 47-53.

33. Кутузов, О.И. Статистическое оценивание связности сети / О.И. Кутузов, Ф. Матарнех // Автоматизация, информатизация, инновация в транспортных системах : сб. науч.-техн. статей. — СПб. : СПГУВК, 2006. — Вып. 1. — С. 2732.

34. Кривулец, В.Г. Квазиупаковочные оценки характеристик надежности сетей / В.Г. Кривулец, В.П. Полесский // Информационные процессы. — 2001.— №2.1. Т. 1. —С. 126-146.

35. Мочалов, В.А. Алгоритмы оценки надежности структуры сенсорной сети / В.А. Мочалов // Информационно-управляющие системы. — 2009. — №5. — С. 61-66.

36. Santi, P. Topology Control in Wireless Ad Hoc and Sensor Networks / P. Santi // John Wiley & Sons Ltd — The Atrium, Southern Gate, Chichester, West Sussex P019 8SQ — England, 2005. — P. 52-62.

37. Fowler, RJ. Optimal packing and covering in the plane are NP-complete / R.J. Fowler, M.S. Paterson, S.L. Tanimoto // Inf. Process. Lett., 1981. — 12(3) — P. 133-137.

38. Wu, Q. On efficient deployment of sensors on planar grid / Q. Wu, S.S. Iyengar, N.S.V. Rao, J. Barten // Computer Communications. — 2007. — Vol. 30 — No. 1415 —P. 2721-2734.

39. Xiang-Yang, Li. Coverage in wireless ad hoc sensor networks / Li Xiang-Yang, Wan Peng-Jun, O. Frieder // Computers, IEEE Transactions. — June 2003. — Vol. 52. — Issue 6. —P. 753-763.

40. Younis, M. Energy-Aware management in Cluster-Based Sensor Networks / M. Younis, M. Youssef, K. Arisha // Computer Networks. —2003. — Vol. 43 — No. 51. P. 649-668.

41. Chen, Y. Sensor Placement for Maximizing Lifetime per Unit Cost in Wireless Sensor Networks / Y. Chen, C. Chuan, Q. Zhao // in the Proceedings of the IEEE Military Communication Conference (MILCOM'05), October 2005. — Atlantic City, NJ.

42. Мочалов, В.А. Интеллектуальная САПР сенсорных сетей / В.А. Мочалов, Е.Н. Турута // Труды конгресса по интеллектуальным системам и информационным технологиям «AIS-IT'09». Научное издание в 4-х томах. — М.: Физматлит, 2009. —Т. 3. —С. 268-276.

43. Zhang, X. How to distribute sensors in a random field? / X. Zhang, S.B. Wicker // in the Proceedings of the 3rd International Symposium on Information Processing in Sensor Networks (IPSN '04), April 2004. — Berkeley, CA.

44. Волик, Б.Г. Эффективность, надежность и живучесть управляющих систем / Б.Г. Волик, И.А. Рябинин // Автоматика и телемеханика. — 1984. — №12.

45. Mulazzani, M. Reliability versus safety / M. Mulazzani // in the Proceedings of the 4th IFAC Workshop SAFECOMP'85, Como, Italy, 1-3 October, 1985.

46. Avizienis, A. Design of fault-tolerant computers / A. Avizienis // in the Proceedings of AFIPS Conference, 1967. — Vol. 31. — FJCC —P. 733-743.

47. Турута, Е.Н. Конспект лекций по дисциплине: "Распределенные вычислительные системы и сетевые технологии" — раздел "ОТКАЗОУСТОЙЧИВОСТЬ РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ" / Е.Н. Турута. — М. : МТУСИ, 2001.

48. Трахтенгерц, Э:А. Компьютерная поддержка решений / Э.А. Трахтенгерц // Научно-практическое издание. Серия «Информатизация России на пороге XXI века». — М. : Синтег, 1998. — 376 с.

49. Виссема, X. Менеджмент в подразделениях фирмы / X. Виссема — Пер., с англ.1. М. : Инфра-М, 1996.

50. Ларичев, О.И. Качественные методы принятия решений / О.И. Ларичев, Е.М. Мошкович — М. : Наука. Физматлит, 1996.

51. Eom, S.B. Decision support systems research: Reference disciplines and a. cumulative tradition / S.B. Eom// The International Journal of Management Science.1995. — P. 511-523.

52. Klein, M. Expert Systems —- A Decision Support Approach with Application in Management and Finance / Mi Klein, L.B. Methlie // Addison Wesley, 1990.

53. Трахтенгерц, Э.А. Компьютерная поддержка принятия решений в САПР / Э.А. Трахтенгерц // Автоматизация проектирования. — 1997. — №5.

54. Моисеев, Н.Н. Предисловие к книге Орловского Ç.A. «Проблемы принятия решений при нечеткой исходной информации» / Н.Н. Моисеев—М. : Наука, 1981.

55. Реферат "Информатика. Структура предметной области. Объекты изучения информатики". URL:. http://revoliition.allbest.ru/programming/000903732.htnil (дата обращения: 05.09.2009).

56. Юрченко, И.Ф. Принципы разработки системы поддержки решений по технической эксплуатации гидромелиоративных систем / И.Ф. Юрченко // сборник научных трудов Всероссийской научно-технической^ конференции, Москва, 15-19 марта 2004 г. — ISBN 5-89231-140-6.

57. Turban, Е. Decision support and expert systems: management support systems / E. Turban // Englewood Cliffs, N.J.: Prentice Hall, 1995.

58. Кун, Т. Структура научных революций / Т. Кун — М. : Прогресс, 1977.

59. Балдищ К.Б. Управленческие решения: учебник. —1 3-е изд. /К.Б. Балдин, С.Н. Воробьев; В.Б. Уткин // М. : Издательско-торговая корпорация "Дашков и К", 2007. — 496 с.

60. Статья «Система поддержки принятия решений». URL: http://ш.wikipedia.org/wiki/Cиcтeмaпoддepжкипpинятияpeшeний (дата обращения: 05.09.2009).

61. Абдикеев, Н.М. Проектирование интеллектуальных систем в экономике: ■ учебник / Н.М. Абдикеев // под ред. Н.П. Тихомирова. — М. : Издательство "Экзамен", 2004. — 528 с.

62. Marakas, G. М. Decision support systems in the twenty-first century / G.M. Marakas // Upper Saddle River — N.J.: Prentice Hall, 1999.

63. Абдикеев, Н.М. Интеллектуальные информационные системы / Н.М. Абдикеев // М.: КОС — ИНФ, Рос. экон. акад., 2003. — 118 с.

64. Джексон, П. Введение в экспертные системы / П. Джексон // М. : Вильяме, 2001. — ISBN 5-8459-0150-2, 0-201-87686-8 — 624 с.

65. Джарратано, Д. Экспертные системы: принципы разработки и программирование, 4-е издание.: Пер. с англ. / Д. Джарратано, Г. Райли // М. : ООО "И.Д. Вильяме", 2007. — 1152 с.

66. Попов, Э.В. Экспертные системы. Решение неформализованных задач в диалоге с ЭВМ / Э.В. Попов // "Наука" — Главная редакция физико-математической литературы — М., 1987. — 288 с.

67. Таунсенд, К. Проектирование и программная реализация экспертных систем на персональных ЭВМ / К. Таунсенд, Д. Фохт // М. : "Финансы и статистика", 1990. — ISBN 5-279-00255-0 — С. 7-8.

68. Малышев, Н.Г. Нечеткие модели для экспертных систем в САПР / Н.Г. Малышев, Л.С. Берштейн, A.B. Боженюк // М. : Энергоатомиздат, 1991. — 136 с.

69. Рутковская, Д. Нейронные сети, генетические алгоритмы и нечеткие системы / Д. Рутковская, М. Пилиньский, JL Рутковский; пер. И.Д. Рудинского. — М. : Горячая линия-Телеком, 2006. — 452 с.

70. Вороновский, Г.К. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности / Г.К. Вороновский, К.В. Маотило, С.Н. Петрашев, С.А. Сергеев //X.: Основа, 1997. — С. 11. — 112 с.

71. Емельянов, В.В. Теория и практика эволюционного моделирования / В.В. Емельянов, В.В. Курейчик, В.М. Курейчик // М.: ФИЗМАТЛИТ, 2003. — 432 с.

72. Czogala, Е. Elementy i metody teorii zbiorow rozmytych / E. Czogala, W. Pedrycz. — Warszawa : PWN, 1985.

73. Kacprzyk, J. Zbiory rozmyte w analizie systemowej / J. Kacprzyk. — Warszawa : PWN, 1986.

74. Cox, E. The Fuzzy Systems Handbook / E. Cox. — London : Academic Press, 1994.

75. Dubois, D. Fuzzy Sets and Systems: Theory and Applications /D. Dubois, H. Prade // San Diego : Academic Press, 1980.

76. Klir, G. J. Fuzzy Sets, uncertainty and Information / G.J. Klir, T.A. Folger // Englewood Cliffs : Prentice Hall, 1988.

77. Kruse, R. Foundations of Fuzzy Systems / R. Kruse, J. Gebhardt, R. Klawonn // Chichester : John Wiley, 1994.

78. Terano, T. Fuzzy Systems Theory and its Applications to Modeling and Control / T. Terano, K. Asai, M. Sugeno // IEEE Transactions on Systems, Man and Cybernetics, 1885. —No. 15.—P. 16-132.

79. Yan, J. Using Fuzzy Logic / J. Yan, M. Ryan, J. Power // London : Pentice Hall, 1994.

80. Zimmermann, H.J. Fuzzy Set Theory / H.J. Zimmermann // Boston, Dordrecht, London : Kluwer Academic Publishers, 1994.

81. Круглов, В.В. Нечеткая логика и искусственные нейронные сети / В.В. Круглов. — М.: Физматлит, 2001. — С. 29-31 — 221 с.

82. Лаврентьев, B.C. Методические указания к лабораторному практикуму "Структуры данных и обработка информационных массивов в экспертных140системах" / B.C. Лаврентьев, Д.О. Сергиенко, В.И. Овсянников // М. : МИФИ, 1992. — 88 с.

83. Марандин, Д.А. Открытые проблемы по беспроводным сенсорным технологиям / Д.А. Марандин // Электросвязь, 2009. — №1 — С.29-32.

84. Кучерявый, А.Е. Выбор головного узла кластера в однородной беспроводной сенсорной сети / А.Е. Кучерявый, А. Салим // Электросвязь, 2009. — №8 — С.32-36.

85. Фомин, А.Д. Разработка и исследование надежных методов агрегации данных в сенсорных сетях : дисс. канд. техн. наук. — СПб., 2007. — 122 с.

86. Линский, Е. М. Управление передачей пакетов в сенсорных сетях : дисс. канд. техн. наук. — СПб., 2007. — 104 с.

87. Cardei, М. Algorithms for Fault-Tolerant Topology in Heterogeneous Wireless Sensor Networks / M. Cardei, S. Yang, J. Wu // IEEE Transactions on Parallel and* Distributed Systems, April 2008. — Vol. 19. — No. 4. — P. 545-558.

88. Goodrich, M.T. Algorithm Design: Foundations, Analysis, and' Internet Examples / M.T. Goodrich, R. Tamassia // John Wiley & Sons, 2002. — Section 8.2.2.

89. Форд, Л. Потоки в сетях. Пер. с англ. / Л. Форд, Д. Фалкерсон — М. : Мир, 1966. —276 с.

90. Кормен, Т. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн — М.: Издательский дом "Вильяме", 2007. — 1296 с.

91. Ahlberg, М. Router Placement in Wireless Sensor Networks / M." Ahlberg, V. Vlassov, Y. Terumasa // IEEE International Conference on Mobile Adhoc and Sensor Systems (MASS), 2006. — P. 538-541'.

92. Леденев, A.H. Физика: Учебное пособие: Для вузов. В 5 кн. Кн. 1. Механика. — М.: ФИЗМАТЛИТ, 2005. — С. 79-81. — 240 е.— ISBN 5-9221-0461-6.141

93. Мочалов, В. А. Метод построения отказоустойчивой структуры сенсорной сети, основанный на применении генетического алгоритма / В.А. Мочалов, Е.Н. Турута // T-Comm, июнь 2009. — Спецвыпуск. Часть 1. Технологии информационного общества — С. 63-66.

94. Мочалов, В. А. Алгоритмы увеличения общего времени работы сенсорной сети до момента ее отказа / В.А. Мочалов // Приборы и системы. Управление, контроль, диагностика. — М.: "НАУЧТЕХЛИТИЗДАТ", 2010. — №7. —С. 12-19.

95. Мочалов В.А. Обеспечение энергетической безопасности сенсорных сетей / В.А. Мочалов // сборник тезисов докладов всероссийской научно-технической конференции "Безопасные информационные технологии". — М.: НИИ РЛ МГТУ им.Н.Э.Баумана, 2010. — С. 57-59.

96. Мочалов, В.А. Построение расписания доступа в беспроводную сенсорную сеть / В.А. Мочалов // Электросвязь, 2009. — №10 — С.36-40.

97. Elson, J. Time Synchronization for Wireless Sensor Networks / J. Elson; D. Estrin // Proceedings of the 15th International Parallel & Distributed Processing Symposium, 2001. — IEEE Computer Society, Washington, DC — USA — P. 186.

98. Elson, J. Fine-grained network time synchronization using reference broadcasts / J. Elson, L. Girod, D. Estrin // OSDI '02: Proceedings of the 5th symposium on Operating systems design and implementation, 2002. — Vol. 36. — P. 147-163.

99. Simeone, O. Distributed* Time Synchronization in Wireless Sensor Networkswith Coupled. Discrete-Time Oscillators / O. Simeone, U. Spagnolini // EURASIPi

100. Journal on Wireless Communications and Networking. — 2007. — Vol. 2007 — Article ID 57054 — 13 p.

101. Van Greunen, J. Lightweight time synchronization for sensor networks / J. van Greunen, J. Rabaey // Proceedings of the 2nd ACM international conference on Wireless sensor networks, 2003. — San-Diego, CA — USA — P. 11-19.

102. Romer, K. Time synchronization; in- ad hoc networks / K. Romer // Proceedings of the-2nd ACM international symposium on Mobile ad-hoc networking & computing table.of contents, 2001. — Long Beach, CA,— USA — P. 173-182.

103. Sichitiu, M.L. Simple, accurate time synchronization for wireless sensor networks / M:L. Sichitiu, C. Veerarittiphan // IEEE Wireless. Communications and Networking Conference (WCNC 2003), March 2003. — New Orleans, LA.

104. Culler, D;E. A network-centric approach to embedded software for tiny devices / D.E. Culler, J. Hill, P. Buonadonna, R. Szewczyk, A. Woo // in Proceedings of the First International Workshop on Embedded Software (EMSOFT), October 2001.

105. Herman, Т. Oriented Edge Colorings and Link Scheduling in Sensor Networks. Communication System Software* and Middleware / T. Herman, I. Pirwani, S. Pemmaraju. — New Delhi: Corns ware, 2006.

106. Grable, D.A. Nearly optimal distributed1 edge coloring in O(loglogn) rounds / D.A. Grable, A. Panconesi // in the Proceedings of the Eighth Annual« ACM-SIAM Symposium on Discrete Algorithms, 1997.

107. Гладков, JI.А. Генетические алгоритмы : учеб. пособие / Л.А. Гладков, В.В. Курейчик, В.М. Курейчик. — 2 изд. — М.: Физматлит, 2006.

108. Мочалов, В.А. Функциональная- схема процесса проектирования беспроводных сетей мониторинга / В.А. Мочалов, E.Hi Турута // Датчики и системы, 2010. — №2 — С.40-44.

109. Пролетарский, А.В. Беспроводные сети Wi-Fi / А.В. Пролетарский, И.В. Баскаков, Д.Н. Чирков // Интернет-университет информационных технологий, 2007. —С. 137-145.

110. Теодоридис, С. Распознавание образов, пер. с англ. / С. Теодоридис, К. Коутрумбас — М.: Издательский Дом «Интеллект», 2009.

111. Николенко, С. Слайды лекций по алгоритмам' кластеризации. URL: http://logic.pdmi.ras.rU/~sergey/teaching/ml/l l'-cluster.pdf (дата обращения: 19.08.2009) — Машинное обучение — ИТМО, 2006.

112. Статья в Википедии "K-means". URL: http://ru.wikipedia.org/wiki/K-means (дата обращения: 05.09.2009).

113. Асанов, М.О. Дискретная математика: графы, матроиды, алгоритмы / М.О. Асанов, В.А. Баранский, В.В. Расин // Ижевск : НИЦ "РХД", 2001. — 288; с.

114. Scellato, S. Wireless network clustering-with genetic algorithms / S. Scellato // Univercity of Catania, Italy.

115. Официальный < сайт экспертной системы Drools. URL: http://jboss.org/drools/ (дата обращения: 30.08.2009).

116. Apache License, Version 2.0. URL: http://www.apache.Org/licenses/LICENSE-2.0.html (дата обращения: 30.08.2009).144

117. Мочалов, В.А. Свидетельство о государственной регистрации программы для ЭВМ "Интеллектуальная система поддержки проектирования отказоустойчивых сенсорных сетей" № 2009615483 от 02.10.2009.

118. Мочалов В.А, Турута E.H. Сквозное проектирование отказоустойчивой сенсорной сети с помощью интеллектуальной СППР // T-Comm, 2010, — № 10. — С. 24-28.