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

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

Ефремов Сергей Геннадьевич

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

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

программ

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

-1 АВГ 2013

Москва - 2013

005531876

Работа выполнена в Национальном исследовательском университете «Высшая школа экономики»

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

Восков Леонид Сергеевич.

Официальные Петренко Александр Константинович,

оппоненты: д.ф.-м.н., проф., Институт системного про-

граммирования РАН, заведующий отделом Технологий программирования; Кузьмин Лев Викторович, д.ф.-м.н., Институт радиотехники и электроники им. В.А. Котельникова РАН, старший научный сотрудник.

Ведущая организация: Федеральное государственное унитарное

предприятие «Межотраслевой научно-исследовательский институт «Интеграл».

Защита состоится 26 сентября 2013 г. в 16 часов на заседании диссертационного совета Д 212.048.09 в Национальном исследовательском университете «Высшая школа экономики» (НИУ ВШЭ) по адресу: 105187, Москва, ул. Кирпичная, д. 33/5, ауд. 505.

С диссертацией можно ознакомиться в библиотеке НИУ ВШЭ. Автореферат разослан «2^.» ¿^¿^W— 2013 г.

Ученый секретарь диссертационного совета, доктор технических наук, профессор

Назаров С. В.

Общая характеристика работы

Актуальность работы

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

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

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

Одной из проблем, препятствующих повышению энергоэффективности

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

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

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

Объектом исследования являются модели и методы динамической реконфигурации сенсорных сетей.

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

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

Для достижения поставленной цели были решены следующие задачи:

4

1. Проведен обзор и анализ подходов к определению понятия времени жизни сенсорных сетей, дано новое определение.

2. Разработана математическая модель динамически реконфигурируемой сенсорной сети с мобильным стоком.

3. Разработан численный метод решения задачи планирования движения стока.

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

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

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

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

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

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

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

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

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

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

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

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

1. Определение времени жизни самовосстанавливающейся сенсорной сети.

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

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

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

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на научно-технических конференциях студен-

6

тов, аспирантов и молодых специалистов МЙЭМ НИУ ВШЭ (2008 - 2013гг.), научно-практическом семинаре ВШЭ "Системный анализ, управление и информационные системы" (19.03.2013), XVI и XVII Международной студенческой конференции-школе-семинаре «Новые информационные технологии» (2008-2009гг.), на международных исследовательских семинарах в Университете Шеффилда и Университете Бирмингема (Великобритания, 2011 г.). Результаты работы вошли в научно-технические отчеты по НИОКР «Разработка программных средств в целях внедрения информационных технологий в промышленность» (номер государственной регистрации НИОКР 01201056220), «Разработка системы активного беспроводного сбора данных в интралогисти-ке» (номер государственной регистрации НИОКР 01200961253).

Результаты работы были применены при проектировании динамически реконфигурируемой сети в рамках совместного Российско-Германского научно-исследовательского проекта.

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

Получены патент на полезную модель № 87259 от 11.06.2009, патент на полезную модель № 98623 от 30.06.2010, патент на полезную модель № 121947 от 10.11.2012, патент на изобретение № 2429549 от 30.06.2010.

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

Структура и объем диссертации Диссертация состоит из введения, 4 глав, заключения, библиографии, включающей 95 наименований, и 4 приложений. Общий объем диссертации без учета приложений составляет 128 страниц.

Содержание работы

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

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

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

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

У исследователей в области БСС нет общего подхода к определению вре-

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

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

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

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

Динамическая реконфигурация БСС с помощью мобильного стока требует описания последовательности его перемещения между узлами сети. В существующих моделях такой возможности нет: в них каждая возможная

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

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

Результаты первой главы опубликованы в следующих работах: [1, 5, 7, 8].

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

Реконфигурируемая сеть N задается в виде следующей тройки:

ЛГ=(а,Г„,П),

где ва = Е3) - граф конфигураций сети,

Гп = {вп(к), к € У,} - множество сетевых графов, каждый элемент которого связан с конфигурацией сети к,

П = (< тт"1, ¿1 >, < л"2, ¿2 >,...,< 7Гд, ¿д >) - последовательность смены конфигураций.

Граф конфигураций С?., состоит из множества вершин = {1,2 ,...,тп} и множества ребер Еа : Ея С Уа х У3. В общем случае У3 задает возможные состояния, в которых может находиться сеть. Применительно к рассматриваемым далее в диссертации методам состояние определяется положением

мобильного стока. Например, на рис. 1 граф С8 организован в виде решетки 4x4, переходы стока возможны только по горизонтали и вертикали между соседними вершинами.

КЗ О)

О I

о

1 о

I

! г,

о

о

I о

I I

! О

о

о То

I I I

о] о

о

0 - узел сенсорной С81И

Рис. 1. Управляемая мобильность стока

Каждый из графов, входящих во множество Гп задает беспроводную сеть: = (уп,Еп),к е К, где Уп - множество вершин, Еп С Уп х Уп -

множество ребер. Вершины соответствуют узлам сети, ребра - установленным беспроводным каналам передачи данных.

Уп = Уи1/ является множеством узлов сети, состоящим в общем случае из сенсорных узлов V = {г>1, -щ, ■ ■ ■, г>п} и узлов-стоков и = {гдх, щ,..., гг5}.

Каждый сенсорный узел Vi = (Р1*, Р;, Ег) характеризуется своей начальной энергией Ег, набором Р, = (р[,р\, ■ ■ ■ ,р'т), где р\ представляет собой мощность, потребляемую г-м узлом, при использовании к-й конфигурации сети, и матрицей = \е^_к\т><т, где ег-_к - дополнительная энергия, затрачиваемая г-м узлом при переходе сети от j-й конфигурации к к-й. Таким образом, особенностью предлагаемой модели является то, что работа любого сетевого узла выражается интегральной характеристикой потребляемой им мощности.

Сток представляет собой специальный тип идеального узла, для которого начальная энергия принимается неограниченной: щ — (Е{ —оо). В диссертации рассматривается случай с одним стоком.

Последним элементом модели является последовательность смены конфигураций П, состоящая из пар < щ, и >, где щ € Ц, - номер конфигурации, и - время ее использования.

Во-втором разделе главы приводится методика расчета времени автономной работы оконечных узлов и маршрутизаторов БСС.

В третьем разделе главы приводится описание предлагаемого автором определения времени жизни БСС. Разобьем сеть на отдельные зоны обслуживания и введем показатель качества работы сети для каждой зоны, зависящий от времени £. Для этого рассмотрим некоторый интервал (£ — Д£ь £). Пусть Ык{€) - общее количество событий, возникших в зоне к в данный интервал времени, а - количество событий из общего числа доставленных до стока за допустимое время. Допустимое время может задаваться как в целом для области к, так и для каждого типа события, возникающего в ней. Значение параметра Atk выбирается исходя из интенсивности событий в конкретной зоне и требований приложения по обеспечению качества обслуживания. Тогда показателем качества работы сети в зоне к в момент времени £ можно считать:

если ВД ^ о 1, если = О Пусть Ск - пограничное значение показателя фк, выше которого сеть считается работоспособной. Зададим через ©^ множество точек во времени, в которых фк переходит через границу Ск сверху вниз и обратно:

М*) =

Рис. 2. Изменение показателя качества работы сети фк со временем

ек = {и, ¿ = 1,2,...: фк(и) >скА {MU + *)< CjfcV VVfc(£i - е) < Cfc), ii < ii+ь е 0}

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

= iUi), ¿ = 1,2,...: тг(») 6 [1..|9а| - 1] : Vi 6 {t<()-M)+1) i>kit) <Ck А Ьщ+i - t,(i) > imaI} U {i|0jt|}

Тогда моментом времени, после которого сеть выходит из строя для отдельной зоны к, будет тк = inf Q'k, а временем жизни Т всей сети:

Т = min Tfc к

Результаты второй главы опубликованы в работе [1].

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

Пусть задана динамически реконфигурируемая сеть в соответствии с описанной во второй главе моделью N = (<33, ГП,П). Необходимо найти оптимальный маршрут движения стока П по критерию максимизации времени жизни сети.

Предлагаемый метод основан на сведении задачи нахождения маршрута к оптимизационной задаче частично-целочисленного линейного программирования (ЧЦЛП). Постановка задачи в терминах ЧЦЛП выглядит следующим образом:

T(ti,t2,..., tm) = У^ tk -» max (1)

»=i

при следующих ограничениях:

т mm

+ Л xjke)_k<Ei, i = TJi (2)

fc=l j=1 к=1,кфз

X>.* = 1 (3)

k=\ m

Xk,m+1 = 1 (4)

k=1

rn+1

xik= xkj,k = l..m (5)

j=0,j?k 3=1,зфк

m

У! Xjk = Ук,к = 1..ТП (6)

3=0

tmmVk <tk< tmaxVk, к = 1..ТП (7)

uj — Uk + m • Xjk < m — 1, 1 < j,k <m,j ф к (8)

Xjk < djk, 1 <j,k< mij ф к (9)

^€{0,1}, yk,ukeN (10) где D = |c!y| - матрица смежности графа Gs,

14

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

Для построения маршрута в структуру задачи вводится искусственное дополнение. Так как движение может начинаться с любой точки, в граф позиций стока добавляются дополнительные виртуальные вершины - 0 и т + 1, чтобы зафиксировать начало и конец маршрута. Генерация маршрута обеспечивается ограничениями (3) - (5). Для выполнения равенства (3) происходит установка в 1 одной из переменных Аналогично окончание маршрута фиксируется установкой в 1 одной из переменных Хк,т+1- Чтобы в каждую вершину входила только одна дуга, используется ограничение (6). Выражение (5) выравнивает входящий и исходящий потоки для каждой посещаемой вершины, что автоматически обеспечивает построение маршрута.

Однако при этом не исключаются возможности образования циклов, не связанных с основным маршрутом. Для решения данной проблемы в модель вводится дополнительное ограничение (8). Вспомогательные переменные и служат для присвоения посещенным вершинам индексов в соответствии с порядком прохода стока через них: если х3к = 1, то и^ < ик. Таким образом, становится невозможным повторное посещение одной и той же вершины графа.

Ограничения (7) оставляют в маршруте только те позиции к, для которых Ьк > 0. ¿т,-п и £та1 представляют собой соответственно минимальное и максимальное время нахождения стока на каждой из позиций.

В результате решения задачи (1), например, одним из стандартных методов, получается набор величин 6 [1 ..т]. Маршрут однозначно восстанавливается по значениям переменных ик и имеет вид: (я"(1), тг(2),..., 7г(д)), где < ип{1+1), V» е [М - !]•

Описанная выше задача ЧЦЛП является ИР-трудной. Поэтому в диссер- •

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

1. Современные алгоритмы маршрутизации в сенсорных сетях позволяют существенно сократить величины e*¡_k, в результате второй суммой в каждом из неравенств (2) можно пренебречь.

2. Учитывая неограниченность стока в ресурсах, необязательно строить кратчайший путь по найденному множеству позиций, для которых íjt > 0.

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

К ним относятся алгоритм случайного перемещения стока (RANDOM), обход сети по периметру, а также эвристический алгоритм GMRE (Greedy Maximal Residual Energy). Последний использует информацию о текущей энергии узлов соседних кластеров и направляет сток в кластер с большей остаточной энергией.

В диссертации предложен новый алгоритм, названный по аналогии с предыдущим GML (Greedy Maximal Lifetime), согласно которому сток направляется в ту из соседних позиций, которая обеспечила бы наибольшее время жизни БСС.

Опишем формально процесс выбора вершины на каждом шаге. Для этого введем дополнительные обозначения: S(k) - подмножество вершин в графе Gs, включающее к и смежные с к вершины, т.е. S(k) = {/c}U{j : (k,j) £ Es}. Обозначим также через D{k) множество узлов, окружающих к-ю позицию стока или, другими словами, множество узлов, которые подключаются напрямую к стоку, когда тот находится на позиции к.

16

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

. Ei(ri)

Рп+1 = argmax min —— keS(pn) Pi

где Ei(n) - остаточная энергия г-го узла после п итераций алгоритма.

Результаты третьей главы опубликованы в работе [2].

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

1. Метод динамической реконфигурации сети с поиском маршрута стока (ОРТ).

2. Метод приближенного решения задачи поиска маршрута стока (ITER).

3. Эвристический алгоритм GMRE движения к максимальной остаточной энергии.

4. Эвристический алгоритм GML стремления к точке максимального времени жизни сети.

5. Метод случайного перемещения стока (RANDOM).

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

St = - 1) * 100%, (11)

tst

где tst - время жизни сети с неподвижным стоком

t - время автономной работы той же самой сети, в которой сток перемещается согласно некоторому алгоритму.

Для сохранения структуры задачи выбор позиции стока kst при его стационарном размещении осуществляется следующим образом:

kst = argmax min —7-*e[i..ml ..n]pk

Было проведено имитационное моделирование, позволившее:

1. Оценить разброс результатов величины 5t при различных размещениях одного и того же количества маршрутизаторов сети.

2. Получить зависимость <5( от радиуса зоны покрытия приемопередатчика.

3. Исследовать зависимость 5t от мощностных характеристик устройств в различных режимах.

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

Из графика видно, что методы динамической реконфигурации сенсорной сети с мобильным стоком дают заметное увеличение времени жизни сети среднего и большого размера (более 50 узлов). Предложенные в диссертации методы приближенного решения задачи планирования стока показывают результаты, близкие к оптимальным, при условии что значение параметра im;n достаточно мало (tmin « 6 [l..n],fc € [l..m])

Результаты четвертой главы опубликованы в работах [3, 5, 10, 11]

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

200

150

100

50 100 150 200 250 Количество узлов сети

300

Рис. 3. Зависимость <5( от размера сети

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

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

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

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

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

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

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

Список публикаций

1. Ефремов С. Г., Воеков JI. С. К вопросу о времени автономной работы сенсорных сетей // Качество, Инновации, Образование. 2012. Т. 7. С. 61-67.

- 0,8 п.л. (вклад автора 0,7 п.л.).

2. Ефремов С. Г., Восков JI. С. Задача увеличения времени автономной работы беспроводных сенсорных сетей в системах сбора данных и способ ее решения // Датчики и системы. 2013. № 4 (167). С. 2-6. - 0,6 п.л. (вклад автора 0,5 п.л.).

3. Ефремов С. Г., Восков JI. С. Использование мобильных стоков для энергетической балансировки сенсорных сетей // Научные труды (Вестник МАТИ). 2012. № 19 (91). С. 220-230. - 1,3 п.л. (вклад автора 1,1 п.л.).

4. Ефремов С. Г. Задача планирования движения мобильного стока в беспроводных сетях сбора данных и метод ее решения // Научно-техническая конференция студентов, аспирантов и молодых специалистов МИ-ЭМ НИУ ВШЭ. Тезисы докладов. М.: МИЭМ НИУ ВШЭ, 2013. С. 91-92.

- 0,2 п.л.

5. Ефремов С. Г. Применение энергетической балансировки в беспроводных сенсорных сетях // Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ, посвященная 50-летию МИЭМ. Тезисы докладов. М.: МИЭМ, 2012. С. 78-79. - 0,2 п.л.

6. Восков JI. С., Комаров М. М., Ефремов С. Г. Выбор платформы для системы мониторинга контейнеров // Журнал "Автоматизация&1Т в энергетике". 2011. № 4 (21). С. 13-18. - 0,7 п.л. (вклад автора 0,3 п.л.).

7. Ефремов С. Г. Управляемая мобильность в беспроводных сенсорных сетях // Тезисы докладов научно-технической конференции студентов,

21

аспирантов и молодых специалистов МИЭМ 2011. М.: МИЭМ, 2011. С. 172-173. - 0,2 п.л.

8. Ефремов С. Г. Общий подход к изучению мобильных беспроводных се- . тей // Тезисы докладов научно-технической конференции студентов, аспирантов и молодых специалистов МИЭМ 2010. М.: МИЭМ, 2010.

С. 174-176. - 0,3 п.л.

9. Voskov L., Panfilov P., Efremov S. et al. Universal wireless sensor networks technology platform and its applications // Proceedings of the 1st International Workshop on Networked embedded and control system technologies: European and Russian R&D cooperation - NESTER. 2009. P. 127-131.

10. Восков JI. С., Комаров M. M., Ефремов С. Г. Универсальная платформа для мониторинга эффективности использования ресурсов на основе технологии беспроводных сенсорных сетей // Журнал "Автоматизация&1Т в энергетике". 2009. № 1 (1). С. 41-43. - 0,3 п.л. (вклад автора 0,1 п.л.).

11. Комаров M. М., Ефремов С. Г. Мобильные платформы для беспроводной сенсорной сети // "Новые информационные технологии". Тезисы докладов XII международной студенческой конференции-школы-семинара. М.: МИЭМ, 2009. С. 190-191. - 0,2 п.л. (вклад автора 0,1 п.л.).

12. Патент на полезную модель № 87259 от 11.06.2009 «Устройство для дистанционного мониторинга окружающей среды на основе технологии беспроводных сенсорных сетей». Восков Л.С., Ефремов С.Г., Комаров М.М.

13. Патент на полезную модель № 121947 от 10.11.2012 «Система захвата движения». Вабищевич А.Н., Восков Л.С., Ефремов С.Г., Комаров М.М., Панфилов П.Б.

14. Патент на полезную модель № 98623 от 30.06.2010 «Система многопользовательского дистанционного управления компьютером для графических приложений» Восков Л.С., Ефремов С.Г., Комаров М.М.

15. Патент на изобретение № 2429549 от 30.06.2010. «Способ многопользовательского дистанционного управления компьютером для графических приложений» Восков JI.C., Ефремов С.Г., Комаров М.М.

Лицензия ЛР № 020832 от «15» октября 1993 г. Подписано в печать % го/З г. формат 60x84/16

Бумага офсетная. Печать офсетная. Усл. печ. л. 1.

Тираж 100 экз. Заказ № ^^ Типография издательства НИУ ВШЭ, 125319, г. Москва, Кочновский пр-д., д. 3.

ПРАВИТЕЛЬСТВО РОССИЙСКОЙ ФЕДЕРАЦИИ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ «ВЫСШАЯ ШКОЛА ЭКОНОМИКИ»

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

04201361244

Ефремов Сергей Геннадьевич

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

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

программ

ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук

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

Восков Леонид Сергеевич

Москва - 2013

Содержание

Введение ......................................................................4

Глава 1. Проблема увеличения времени жизни беспроводных сенсорных сетей.............................11

1.1. Понятие беспроводной сенсорной сети...............11

1.2. Понятие времени жизни сети....................20

1.3. Методы увеличения времени жизни БСС.............23

1.4. Реконфигурируемые БСС с мобильным стоком.........27

1.5. Выводы к главе 1..........................35

Глава 2. Математическая модель реконфигурируемых БСС . 37

2.1. Введение...............................37

2.2. Модель реконфигурируемой сенсорной сети...........37

2.3. Расчет потребляемой мощности и времени жизни узлов БСС . 41

2.4. Показатели времени жизни сети..................54

2.5. Оценка времени жизни динамически реконфигурируемых сетей 59

2.6. Выводы к главе 2..........................63

Глава 3. Метод динамической реконфигурации сенсорной сети с мобильным стоком..........................65

3.1. Введение...............................65

3.2. Общая задача планирования движения стока..........66

3.3. Метод решения задачи планирования движения стока.....72

3.4. Эвристические алгоритмы динамического управления движением стока..............................77

3.5. Выводы к главе 3..........................81

Глава 4. Моделирование БСС с мобильным стоком.......83

4.1. Введение...............................83

4.2. Исследование возможности проведения натурного эксперимента 83

4.3. Имитационное моделирование...................92

4.4. Выводы к главе 4..........................113

Заключение..................................114

Литература..................................116

Приложение А. Акты внедрения результатов диссертационной работы...................................129

Приложение Б. Примеры расчета потребляемой мощности и времени жизни устройств БСС...................132

Приложение В. Аппаратная платформа для беспроводных сенсорных сетей...............................135

В.1. Принципиальная схема.......................135

В.2. Внешний вид макета ........................136

В.З. Характеристики...........................136

В.4. Патент на полезную модель ....................138

Приложение Г. Комплекс программ для моделирования динамически реконфигурируемых БСС.................139

Г.1. Решение задач линейной оптимизации с помощью 1р_Бо1уе . . . 139 Г. 2. Интерфейс программы.......................143

Введение

Актуальность работы

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

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

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

Одной из проблем, препятствующих повышению энергоэффективности

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

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

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

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

Для достижения поставленной цели были решены следующие задачи:

1. Проведен обзор и анализ подходов к определению понятия времени жизни сенсорных сетей, дано новое определение.

2. Разработана математическая модель динамически реконфигурируемой сенсорной сети с мобильным стоком.

3. Разработан численный метод решения задачи планирования движения стока.

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

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

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

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

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

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

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

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

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

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

1. Определение времени жизни самовосстанавливающейся сенсорной сети.

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

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

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

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на научно-технических конференциях студентов, аспирантов и молодых специалистов МИЭМ НИУ ВШЭ (2008 - 2013гг.), научно-практическом семинаре ВШЭ "Системный анализ, управление и информационные системы" (19.03.2013), XVI и XVII Международной студенческой конференции-школе-семинаре «Новые информационные технологии» (2008-2009гг.), на международных исследовательских семинарах в Университете Шеффилда и Университете Бирмингема (Великобритания, 2011 г.). Результаты работы вошли в научно-технические отчеты по НИОКР «Разработка программных средств в целях внедрения информационных технологий в промышленность» (номер государственной регистрации НИОКР 01201056220), «Разработка системы активного беспроводного сбора данных в интралогисти-ке» (номер государственной регистрации НИОКР 01200961253).

Результаты работы были применены при проектировании динамически реконфигурируемой сети в рамках совместного Российско-Германского научно-исследовательского проекта.

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

Получены патент на полезную модель № 87259 от 11.06.2009, патент на полезную модель № 98623 от 30.06.2010, патент на полезную модель № 121947 от 10.11.2012, патент на изобретение № 2429549 от 30.06.2010.

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

Структура и объем диссертации Диссертация состоит из введения, 4 глав, заключения, библиографии, включающей 95 наименований, и 4 приложений. Общий объем диссертации без учета приложений составляет 128 страниц.

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

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

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

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

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

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

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

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

2. Условия функционирования сети могут изменяться, как следствие, мощность, потребляемая узлами, также меняется со временем.

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

Для второго сценария рассматривается несколько эвристических алгоритмов, включая новый алгоритм GML (Greedy Maximal Lifetime).

Четвертая глава посвящена комплексному моделированию беспроводной сенсорной сети с мобильным стоком.

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

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

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

Глава 1

Проблема увеличения времени жизни беспроводных сенсорных сетей

1.1. Понятие беспроводной сенсорной сети

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

Сенсорные сети являются частным случаем ситуационных (в англоязычной литературе - ad hoc) сетей [9], представляющих собой распределенные системы равноправных узлов, в которых каждый узел может обмениваться данными с любым из своих соседей. Отличие сенсорных сетей в том, что в них элементы можно четко разделить по набору выполняемых функций. Исходя из этого выделяют три основных типа сетевых узлов:

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

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

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

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

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

• RISC-процессор с частотой от 8 до 32 МГц

• объем оперативной памяти от 8 до 192 Кбайт

• объем внешней флеш-памяти от 0,5 до 8 МБайт

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

Режим работы Обозначение мощности Типовое значение, мВт

Прием р 1 Г X 52

Передача Ргх 45

Обработка Ра 20

Режим сна Р8 0,03

Таблица 1.1. Режимы работы беспроводных модулей БСС

1.1.1. Практическое применение БСС

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

Существует и ряд нестандартных приложений, изначально несвойственных БСС, но, тем не менее, активно изучаемых - передача мультимедиа данных [19], данных инерциальных датчиков в системах слежения или захвата движения [3].

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

• Сети подводного мониторинга. В последние годы были изучены возможности развертывания подводных сенсорных сетей для мониторинга состояния мирового океана в отдельных его областях. Но, как было показано в одной из работ [32], использование традиционных БСС под водой сталкивается с целым рядом трудностей. Во-первых, это на несколько порядков больший коэффициент затухан�