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

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

ЖЕВАК Алексей Владимирович

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

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

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

Уфа 2008

003457295

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

Научный руководитель д-р. техн. наук, ст. науч. сотр.

АРЬКОВ Валентин Юльевич

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

д-р. физ.-мат. наук, проф. ЖИТНИКОВ Владимир Павлович

канд. техн. наук, доц. ГИНИЯТУЛЛИН Вахит Мансурович

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

ОАО «Нефтеавтоматика»

Защита диссертации состоится «2£» декабря 2008 г. в ¡4ой на заседании диссертационного совета Д-212.288.03 при Уфимском государственном авиационном техническом университете по адресу: 450000, Уфа, ул. К. Маркса 12

С диссертацией можно ознакомиться в библиотеке университета

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

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

Актуальность темы

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

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

Проблема организации и оптимизации сбора данных в беспроводных сенсорных сетях активно изучается учёными из разных стран мира. Среди российских учёных можно отметить труды Е.А. Кучерявого и Д.А. Молчанова в области самоорганизующихся сенсорных сетей.

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

Цель работы

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

Задачи исследования:

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

2. Разработать алгоритм оптимизации сбора данных в беспроводной сенсорной сети на основе разработанной модели.

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

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

Основные научные результаты, выносимые иа защиту:

1. Математическая модель сбора данных в беспроводной сенсорной сети.

2. Алгоритм оптимизации сбора данных в беспроводной сенсорной сети, основанный на разработанной модели.

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

4. Комплекс программ для проведения вычислительного эксперимента.

Научная новизна

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

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

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

4. Комплекс программ для проведения вычислительного эксперимента, реализованный на языке программирования С++ с использованием принципов объектно-ориентированного программирования, реализует новую модель сбора

данных и новые алгоритмы оптимизации сбора данных и генерации графов беспроводных сенсорных сетей.

Практическая значимость

1. Разработана математическая модель сбора данных в беспроводной сенсорной сети, позволяющая избежать радио-коллизий и дублирования данных, обеспечивающая сбор данных со всех сенсорных узлов за фиксированное время (менее 2 мин для сети из 100 улов) и не требующая изменения расписания сбора данных до тех пор, пока не изменится топология сети. Данная модель также позволяет осуществить прогноз срока службы каждого сенсорного узла без замены источника питания с точностью 6%. Такая погрешность является незначительной на фоне вариации ёмкости источника питания в зависимости от температурного режима (более 50%).

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

3. Новый алгоритм генерации графов беспроводных сенсорных сетей является единственным в своём роде алгоритмом, позволяющим генерировать входные данные для нового алгоритма оптимизации сбора данных, и позволяет протестировать последний на более чем Ю|0° различных графах, не прибегая к их реальному построению (что потребовало бы серьёзных временных и материальных затрат).

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

Внедрение результатов работы

Результаты работы применимы для беспроводных сенсорных сетей независимо от сферы их применения. Они внедрены в НЛП «Знание» (г. Уфа), где используются в автономной беспроводной информационно-измерительной системе мониторинга трубопровода, основанной на беспроводной сенсорной сети.

Апробация работы

Основные результаты диссертации докладывались на следующих конференциях и семинарах:

1. Зимняя школа аспирантов и молодых ученых (Уфа, 2006).

2. Вторая научно-техническая конференция молодых специалистов, посвященная годовщине образования объединения ОАО «УМПО» (Уфа, 2006).

3. XXIII Гагаринские чтения (Москва, 2007).

4. Зимняя школа аспирантов и молодых ученых (Уфа, 2007).

5. Зимняя школа аспирантов и молодых ученых (Уфа, 2008).

6. 9-я международная научно-практическая конференция «Компьютерные науки и информационные технологии» (Красноусольск, 2007)

Список публикаций по теме диссертации содержит 10 работ, в том числе 2 статьи в рецензируемых журналах из списка ВАК и 3 свидетельства о регистрации программ для ЭВМ.

Структура и объём работы

Диссертация состоит из 4 глав. Объем работы составляет 111 страниц машинописного текста, включая 36 рисунков, 7 таблиц и библиографию, содержащую 94 названия.

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

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

Для решения рассматриваемой задачи необходимо создание адекватных моделей и разработка эффективных численных методов для её решения.

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

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

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

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

Требования:

1. Не реже чем 1 раз в 2 - 10 минут информация об измерениях с каждого сенсорного узла должна поступать в центральный узел.

2. Множество узлов постоянно.

3. Все узлы статичны.

4. Количество узлов п< 100.

5. Используется следующее оборудование: микроконтроллер АОиС 848, радиомодуль Хегшсз ХЕ1203.

Все модели сбора данных в беспроводных сенсорных сетях можно разбить на 2 основных класса: модели сбора данных по расписанию и адаптивные модели. Важно отметить, что нельзя рассматривать алгоритм сбора данных отдельно от модели сбора данных и наоборот. Основной идеей алгоритмов сбора данных по расписанию является создание некоторого расписания сбора данных для узлов сети. Расписание жёстко прописывает для каждого узла, что он должен делать в каждый момент времени. При этом время может быть разбито на интервалы. Как правило, расписание строится таким образом, чтобы исключить дублирование данных. Адаптивные модели реализуют идею так называемых самоорганизующихся беспроводных сенсорных сетей. Основной смысл заключается в том, что в сети не существует никакого заданного извне расписания. Узлы сети некоторым образом самостоятельно организуются в сеть. В таблице I приведена сводка основных характеристик существующих моделей сбора данных.

Таблица 1 - Характеристики моделей сбора данных в беспроводной сенсорной сети ____

Класс моделей Время сбора данных Энергопотребление Поддержка мобильности Отказоустойчивость

Основанные на расписании малое, фиксированное низкое, постоянное нет низкая

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

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

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

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

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

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

Беспроводная сенсорная сеть, состоящая из п узлов (я-1 сенсорного и 1 центрального), есть связный неориентированный граф С{УД), где

у= {уь у2,..., у„} - множество вершин графа 6, причём: VI, Уг, у„„1 - сенсорные узлы; у„ - центральный узел;

Е={е]ге2, •.., е„} - множество рёбер графа £?, причём:

{и, у} е Е если между к и V возможна прямая радиосвязь;

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

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

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

тральный узел, называется циклом сбора данных. Цикл сбора данных состоит из Ь единичных временных интервалов. Каждый узел в течение 1 единичного временного интервала выполняет 1 из 3 возможных действий:

3) Принимает данные от другого узла.

2) Передаёт данные другому узлу.

3) Не осуществляет приём/передачу данных.

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

Расписание сбора данных описывается математически как упорядоченное множество {5"ь ¿о, ..., б/.}, где описывает сбор данных в /-й единичный временной интервал и представляет собой множество упорядоченных пар вершин: & = {(«ь Ь\), (а2, Ьг), (ат, Ь„,)}, где д,- - узел, передающий информацию в течение /-го единичного временного интервала узлу Ьь а А,, соответственно, -узел, принимающий информацию от узла а,-, в течение ¡-го временного интервала.

Для определения длительности единичного временного интервала и энергопотребления узлов сети, построена схема сеанса связи между 2 узлами. Благодаря данной схеме, определена максимальная длительность цикла сбора данных для сети, состоящей из 100 узлов (максимальное число узлов, определённое в постановке задачи создания модели сбора данных). Для оборудования, используемого в сенсорной сети мониторинга трубопровода, она составляет 99,16 с, что меньше ограничения максимального срока поступления данных от каждого сенсорного узла в центральный узел (составляющего 120 с). Это позволяет пренебречь длительностью цикла сбора данных как критерием оптимизации сбора данных. Таким образом единственным критерием сбора данных становится расход энергии сенсорными узлами сети.

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

+ (>} + 1>„ к ~ ) •+ к + ег - е,) + +

В

- +

+

+

КК + г.+У,)

0)

5

(уп+{к,+\Ут + Уе) , , V ч

5

Здесь

- время, необходимое АЦП для измерения всех необходимых параметров;

- время, необходимое микропроцессору для обработки значений, полученных от АЦП;

tv, - время перехода микропроцессора в рабочий режим (из спящего режима);

¿р - максимальное время ожидания сигнала приёмником (интервал времени между включением узла-приёмника на приём и началом передачи данных узлом-передатчиком);

/> - время перехода радио-модуля в режим приёмника; I, - время перехода радио-модуля в режим передатчика; вз — ток потребляемый микропроцессором в спящем режиме; ет - ток потребляемый АЦП во время измерения; е„ - ток потребляемый микропроцессором в рабочем режиме; ег - ток потребляемый радио-модулем в режиме приёмника; е, - ток потребляемый радио-модулем в режиме передатчика; В - скорость обмена данными по радиоканалу;

Ур - объём служебной информации, передаваемой при каждой передаче данных по радиоканалу (кроме передачи отклика); Ус - размер пакета отклика; V, - размер 1 пакета синхронизации времени; Ут - размер 1 пакета измерений 1; Ьг - реальная длительность цикла сбора данных; г - ожидаемое среднее количество попыток связи; П - количество узлов, у которых узел принимает данные в течение 1 цикла сбора данных;

А/ - количество пакетов измерений, принимаемых узлом 1 в течение 1 цикла сбора данных;

к, — сумма значений энергопотребления радиопередатчика г-го узла при передаче откликов во все узлы, передающие данные напрямую узлу г" (с учётом необходимых уровней мощности);

г, - энергопотребление радиопередатчика /-го узла при передаче пакетов измерений (с учётом требуемого уровня мощности).

На основании формулы (1) определена формула расчёта общего расхода энергии (т.е. суммарного расхода энергии всеми сенсорными узлами сети за 1 цикл сбора данных)

Е = (п- 1)Ьгег + (и - 1>и {ея + е„-е,) +

+ (и ~!>,(*„ -«,)+ (2п-Я- 1>А ~ + (л ~ чУРк + - 0 + (и - 1X2' -Я + )+

Я-]

+ (п -1)2;/, (ег + е„ - в,) + 2Й( +

Ur/ß

+

+

(и-i);

в

-k+ew-es)+

^Vp + Vc+{ki + \)Va( .

+ r2L,-5-(^ + e„-ef) +

i-i

(2)

В

f \ + -R-~ 2>/+(*~<?X*w~<Ü

\iey/Q

Общий расход энергии £ является критерием оптимизации в задаче оптимизации сбора данных в беспроводной сенсорной сети, постановка которой приведена ниже:

Дано:

G(V,E) — граф, описывающий беспроводную сенсорную сеть;

В, Vm, Ve, Vp, V„ tw, t„, tc, tP, tr, t„ es, ew e„„ er, С - характеристики беспроводной сенсорной сети.

Найти:

S - расписание сбора данных для заданной беспроводной сенсорной сети, такое, что Е -> min (общий расход энергии минимален).

Здесь

С = {с|, с2, ..., ст) - множество, описывающее уровни мощности радиопередатчика;

е, — ток, потребляемый РМ в режиме передачи при /-м уровне мощности;

т - количество уровней мощности.

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

Задача оптимизации сбора данных, посредством определённых манипуляций, сводится к задаче поиска максимального потока минимальной стоимости в транспортной сети. Таким образом, разработанный алгоритм состоит из 3 основных шагов:

1. Построение транспортной сети по заданному графу беспроводной сенсорной сети.

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

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

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

На первом шаге алгоритма по исходному графу БСС Е) строится транспортная сеть (?'(VЕ') таким образом, что

V—Vи з и (, где 5 - исток, сток;

Е' = Е и(5,1)и($, 2 ... и (у, л -1) и (я, г) - множество дуг;

р^, V) = 1, для всех V, таких что (у, V) е Е';

р(и, у) = оо, для всех и, у, таких что (к, у) е Е' и и Ф з;

а(и, у) = 0, для всех к, у, таких что (и, у) е Е'/Е;

а(м, у) = Сф? + ег + 2е№ - 2е„ для всех и,у, таких что (и,у) е Е, и Ф п, у ф к;

а(и, п) = си.(„_ + для всех и, таких что (и, п) е Е.

Здесь

р(м,у) - пропускная способность дуги (и,у);

а(и,у) - цена прохождения потока по дуге (к,у).

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

Теорема об объединении потоков: если в транспортной сети, построенной по графу беспроводной сенсорной сети, для некоторого узла и существует несколько узлов V], у2, ..., Уь таких что из и в каждый из них проистекают потоки ненулевой величины, то объединение этих потоков в единый поток из и в у, (для любого /е[1,£]) не изменит ни суммарной величины потока в графе, ни его стоимости.

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

риментов по оценке эффективности работы разработанного эвристического алгоритма.

Сложность проведения натурного эксперимента приводит к необходимости создания комплекса компьютерных программ для имитационного моделирования. Для проведения последнего спроектирован (с помощью унифицированного языка моделирования UML (Unified Modeling Language)) и реализован (на языке программирования С++) комплекс программ для ЭВМ.

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

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

Дано:

п - количество узлов сети;

D = [di, d2,..., dm), где dt - количество связей между узлами с минимальным уровнем мощности передатчика равным /;

Требуется сгенерировать граф G(V,E), такой что:

1. G(V,E) — связный неориентированный граф;

2. |F| = n;

3. w(u,v) е {1,2,...,«} V {u,v} е Е;

4. Количество {w,v} еЕ и w(m,v) = i, равно 4 для всех ¡" е {1,2,..., т].

Алгоритм генерации графов беспроводных сенсорных сетей, решающий

поставленную задачу, приведён ниже:

1. Задать V=0,E=0.

2. Задать V' = {vb v2,..., v„} - множество всех допустимых вершин.

3. Задать & ~ 1М - множество всех допустимых ребер.

«eE',ve£'

4. Построить случайное остовое дерево:

a. Задать и = случайная вершина из У".

b. Задать F= Кии.

c. Задать и = случайная вершина из V.

d. Задать v = случайная вершина из V.

e. Задать V=Vuu,V'=V'/u.

f. Задать Е = Е u (m,v), Е' = ЕЧ (u,v).

g. Задать w(u,v) = случайный элемент из {1,2,т}.

Ь. ¿Cfu.v) = — 1 •

i. Если | V\ < и, перейти на шаг 4с.

5. Дополнить граф случайным образом до достижения заданного числа рёбер:

Пока YAi> выполнять:

a. Задать (w,v) = случайное ребро из Е'.

b. Задать£ = £и(h,v),Е' = Е'/(m,v).

с. Задать = случайный элемент из {1, 2,..т}. & ¿/»»(и^) = ¿4(я,у) — 1.

Примечание к шагам 4g и 5с:

4

вероятность генерации элемента г равна *

IX

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

Также в данной главе приводится описание и результаты натурного эксперимента, поставленного с целью определения точности формулы частного расхода энергии (1). По результатам эксперимента было выявлено, что теоретический расход энергии превысил практический на 5,61%.

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

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

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

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

4. Комплекс программ для проведения вычислительного эксперимента, реализованный на языке программирования С++, реализует новую модель сбо-

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

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ В рецензируемых журналах из списка БАК

1. Оптимизация сбора данных в беспроводных сенсорных сетях с использованием нейронной сети с градиентным алгоритмом обучения / В.Ю. Арьков, A.M. Фридлянд, A.B. Жевак И Нейрокомпьютеры: разработка, применение. 2007. №10. С. 47-49.

2. Построение кратчайшего расписания сбора данных в беспроводной сенсорной сети с ограниченным критическим энергопотреблением / A.B. Жевак, В. Ю. Арьков // Вопросы современной науки и практики . Университет им. В.И. Вернадского: науч. журн. Тамбовск. гос. ун-та. 2008. Т. 2, № 4(10). С. 147— 156.

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

3. Распределённая автономная информационная измерительная система мониторинга состояния трубопроводов / A.B. Жевак // Интеллектуальные системы обработки информации и управления : сб. ст. per. зимн. шк.-сем. аспирантов и молодых учёных. Уфа: Технология, 2006. Т. 1. С. 271-272.

4. Минимизация длительности цикла сбора данных в беспроводной сенсорной сети для мониторинга трубопровода / A.B. Жевак // ХХХШ Гагаринские чтения: матер, междунар. молодёжи, науч. конф. М.: МАТИ, 2007.

5. Алгоритм динамического программирования для нахождения минимальной длительности цикла сбора данных беспроводной сенсорной сети / A.B. Жевак, В. Ю. Арьков // Интеллектуальные системы обработки информации и управления : сб. ст. per. зимн. шк.-сем. аспирантов и молодых учёных. Уфа : Технология, 2007. Т. 1. С. 97-102.

6. Распределённая автономная информационно-измерительная система мониторинга состояния трубопровода / A.B. Жевак // Материалы 2-й науч.-техн. конф. молодых специалистов. Уфа: УМПО, 2006. С. 70—71.

7. Нахождение оптимального цикла сбора данных в беспроводной сенсорной сети / A.B. Жевак, В.Ю. Арьков // Компьютерные науки и информационные технологии : сб. матер. 9-й междунар. науч.-практ. конф. Уфа : УГАТУ, 2007. Т. 3. С. 220-223. (статья на англ. яз.).

8. Свид. о гос. per. программы для ЭВМ №2008615005. Программа имитационного моделирования сбора данных в беспроводных сенсорных сетях / A.B. Жевак, В.Ю. Арьков. Зарег. 17.10.2008. Роспатент.

9. Свид. о гос. per. программы для ЭВМ №2008615006. Программа оптимизации сбора данных для беспроводной сенсорной сети / A.B. Жевак, В.Ю. Арьков. Зарег. 17.10.2008. Роспатент.

Ю.Свид. о гос. per. программы для ЭВМ №2008615007. Генератор 1рафов беспроводных сенсорных сетей / A.B. Жевак, В.Ю. Арьков. Зарег. 17.10.2008. Роспатент.

Диссертант

Жевак A.B.

ЖЕВАК Алексей Владимирович

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

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

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

Подписано в печать 21.11.08. Формат 60x84 1/16. Бумага офсетная. Печать плоская. Гарнитура Times New Roman Cyr. Усл. печ. л. 1,0. Усл. кр.-отт. 1,0. Уч.-изд. л. 0,9. Тираж 100 экз. Заказ № 557.

ГОУ ВПО Уфимский государственный авиационный технический университет Центр оперативной полиграфии 450000, Уфа-центр, ул. К.Маркса, 12