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

- - 004610157

Московским авиационным институт (государственный технический университет)

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

Акимов Евгений Вячеславович

Проектирование рациональной топологии беспроводных

сенсорных сетей

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

АВТОРЕФЕРАТ

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

Научный руководитель: к.т.н. доцент С.В. Кудряшов

Москва 2010

- 7 окт 2010

004610157

Работа выполнена на кафедре 704 «Информационно-управляющие комплексы» Московского авиационного института (государственного технического университета).

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

Официальные оппоненты: доктор технических наук, профессор Ляхов Андрей Игоревич, заведующий лабораторией методов анализа и синтеза сетевых протоколов ИППИ РАН им. А.А. Харкевича кандидат технических наук, доцент Гришин Вячеслав Михайлович, доцент кафедры 604 Московского авиационного института (государственного технического университета)

Ведущая организация: Институт программных систем им. А.К. Айламазяна РАН, г. Переславль-Залесский

Защита диссертации состоится « 12» октября 2010 г. в аудитории 302 на заседании диссертационного совета Д 212.125.02 при Московском авиационном институте (техническом университете) по адресу 125993, г. Москва, Волоколамское шоссе д. 4.

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

Дата рассылки автореферата:

«/О» сентября 2010 г.

Ученый секретарь диссертационного совета Д 212.125.02 к.т.н., доц.

Петраков А.М.

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

Актуальность темы исследования

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

• конечные устройства (КУ), оснащаемые сенсорами и осуществляющие измерения;

• ретрансляторы или маршрутизаторы, передающие сообщения с результатами измерений от КУ;

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

• мосты, связывающие разные БСС друг с другом;

• PAN-координатор (PAN - Personal Area Network), осуществляющий управление БСС и также выполняющий роль шлюза данных.

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

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

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

Для конечного потребителя услуг, предоставляемых информационно-измерительным комплексом на основе использования БСС, важно минимизировать затраты на его приобретение и дальнейшее техническое обслуживание при выполнении ограничений на решение целевой задачи с заданной надежностью. Реализация данного требования потребителя приводит, с одной стороны, к сокращению количества используемых узлов-ретрансляторов, а, с другой стороны, не позволяет вытянуть их в цепь по кратчайшему расстоянию между КУ и шлюзами с учетом требуемого уровня надежности доставки данных. Вместе с тем, при увеличении количества КУ и ретрансляторов остро встают проблемы ограниченной пропускной способности узлов и взаимного влияния потоков данных друг на друга. Перечисленные условия определяют необходимость решения задачи выбора рационального геометрического расположения ретрансляторов, а также оптимальной маршрутизации потоков данных между ними, что и составляет понятие «рациональная топология беспроводной сенсорной сети». Такая топология позволит сократить трафик и снизить энергопотребление на узлах, что, в свою очередь, увеличит время безотказной работы сети и снизит общие затраты на её обслуживание, заключающиеся в замене оборудования и/или элементов питания.

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

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

Цель работы

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

Объект исследования

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

Методы исследования

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

Основные задачи исследования

1. Анализ и формализация особенностей и ограничений задачи проектирования рациональной топологии БСС;

2. Разработка математической модели БСС, её компонентов и аспектов функционирования;

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

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

5. Разработка ПМО, реализующего алгоритмы проектирования и сравнения топологий;

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

Научная повнзна работы

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

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

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

4. Формализованы следующие ограничения задачи оптимизации топологии: на допустимые области размещения узлов, на трафик через узел, на надежность доставки сообщений, на количество соединений узла, а также особенности задачи, связанные с влиянием внешних источников ЭМИ на вероятность успешного приема пакетов, совместным использованием ресурсов сети для транспортировки различных потоков данных, использованием более одного типа ретрансляторов, движением КУ, проблемой реализации рациональной топологии в БСС.

5. Разработаны математические модели:

• топологии БСС с учетом распределения входящих и исходящих потоков данных на узлах сети;

• узла БСС с учетом показателей его надежности;

• зависимости вероятности успешного приема символа от соотношения сигнал/шум на приемной антенне;

• механизма конкурентного доступа узлов к среде передачи данных.

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

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

8. Разработано ПМО, реализующее алгоритмы оптимизации топологии, моделирование построения ZigBee-oптимaльнoй топологии, сравнения топологий.

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

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

11. Проведены вычислительные эксперименты, подтвердившие работоспособность алгоритма оптимизации топологии и обоснованность его структуры. По результатам вычислительных экспериментов также установлены средние показатели степени соответствия рациональной и 2!§Вее-оптимальных топологий, получены данные о зависимости степени соответствия от изменения условий коммуникации узлов.

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

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

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

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

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

2. Коррективы к алгоритмам оптимизации топологии БСС в следующем составе:

• Учет влияния совместного несинхронизированного доступа узлов к сети на снижение её пропускной способности.

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

3. Алгоритм сравнения сетевых топологий.

4. Обоснование выбора критериальной функции оптимальной маршрутизации в сетях ZigBee.

5. Программная реализация алгоритмического обеспечения задачи оптимизации топологии БСС

6. Результаты вычислительных экспериментов.

7. Программный продукт, предназначенный для решения задачи оптимизации топологии БСС.

Публикации

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

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

Результаты исследований докладывались и обсуждались на всероссийских и международных конференциях в 2008-2010 годах, а также научно-технических конференциях и семинарах в Московском авиационном институте, Институте проблем передачи информации им. A.A. Харкевича РАН, Институте программных систем им. А.К. Айламазяна РАН.

Достоверность результатов

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

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

• фактом использования полученных результатов в научно-исследовательских разработках по гранту Федерального агентства по науке и инновациям ООО «MeshNetics».

Структура диссертационной работы

Диссертация состоит из введения, 4 глав с 5 таблицами и 42 иллюстрациями, заключения и библиографического списка, состоящего из 53 наименований. Общий объем работы составляет 155 страниц.

2. Основное содержание работы

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

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

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

Под топологией БСС в работе понимается совокупность геометрического расположения её узлов и вероятностей использования коммуникаций между ними для доставки сообщений:

ИМ'

где ||/г,|| - множество узлов БСС мощностью N; Ц/^Ц - множество вероятностей

использования коммуникаций между узлами.

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

где Р, Р* - надежность и ограничение надежности сети.

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

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

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

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

Известные сегодня подходы к проектированию топологической структуры беспроводных сетей с использованием математического моделирования основаны на применении аппарата комбинаторного анализа и обладают существенной ресурсоемкостью (экспоненциально увеличивающейся при росте числа узлов сети), что затрудняет их использование для проектирования сетей большой размерности. Среди реализованных можно отметить решения, разработанные в Институте проблем передачи информации РАН им. A.A. Харкевича (семейство алгоритмов подсистемы топологического проектирования, входящей в состав Системы автоматизации проектирования компьютерных сетей), а также разработку коллектива сотрудников каф.704 МАИ, выполненную по заказу компании ООО «MeshNetics».

В настоящем исследовании развивается альтернативный подход к проектированию рациональной топологии БСС, предусматривающий учет перечисленных особенностей и ограничений. Данный подход впервые был сформулирован доцентом кафедры 704 МАИ С.В.Кудряшовым в 2005 г. и основан на сведении задачи оптимизации топологии к игровой. Это позволяет учесть взаимное влияние потоков данных в сети, а также показатели надежности узлов и коммуникаций между ними посредством формализации этих ограничений как проявления действий игрока-Природы.

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

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

Для каждого из узлов сети существует непустое множество соседних с ним узлов (находящихся в зоне его радиовидимости)1, определяющих его возможные коммуникации:

А, = {./'}, j = \,n„ я, >0, где п - мощность этого множества для /-го узла. Последовательность ретрансляций сообщения от отправителя до адресата образует маршрут

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

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

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

Я = П >

tel

где рг - вероятность (частота) использования маршрута;

Nm - количество узлов в маршруте;

р1М - вероятность использования для передачи сообщения коммуникации между /ым и (/+1) -ым узлами маршрута.

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

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

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

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

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

Построение маршрутов от КУ до шлюза осуществляется с помощью алгоритма динамического программирования - метода Форда-Беллмана. Критериальная функция этого алгоритма (функция Беллмана) определяет условную стоимость транспортировки потока данных между соседними узлами маршрута:

г = •< У«' ,

Ст - условная стоимость узла БСС, принимающая нулевое значение при повторном использовании узла в топологии (чем достигается минимизация количества ретрансляторов), СТ - условная номинальная стоимость узла, Сг - условная стоимость ретрансляции, и'тх, и'м - фактический трафик через узел с учетом повторных ретрансляций, {/тах -максимальный трафик через узел, 1/'г - эквивалентная плотность потока данных, излучаемого соседними узлами с учетом конкуренции за доступ к среде передачи.

и'г =Т,ги^, где Т1Г - случайная величина, составляющая время ожидания узлом начала передачи. Вычислительные эксперименты позволили установить, что в первом приближении данная величина зависит от вероятности нахождения среды передачи данных в

2Х,,

незанятом состоянии Ра = 1 - —-и имеет экспоненциальное распределение с параметром

ц№. По результатам экспериментов зависимость Ця-{Ра) была аппроксимирована кубическим полиномом.

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

где С =

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

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

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

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

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

Рис. 1. Алгоритм моделирования процесса эксплуатации БСС

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

N

рты _ [=|

' ~ N >

&

¡=1

где Тг - продолжительность регламентного периода;

N - количество моделируемых регламентных периодов;

- время неполной работоспособности БСС в течение г -го регламентного периода.

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

где кг - среднее оцененное количество узлов, нуждающихся в замене по окончании регламентного периода;

к' - количество узлов, вышедших из строя к моменту окончания /-го регламентного периода.

Критерий сравнения топологий. Для сравнения топологий предлагается использовать следующий критерий:

1 Кпп К

ED t 1=1 J'I

где Ст - степень сходства двух топологий (величина критерия сравнения), представляющая собой среднее сходство маршрутов на пару «источник-адресат» обеих топологий, Ned - общее количество КУ в БСС, N, - общее количество шлюзов, Cs -

суммарная степень совпадения маршрутов для /'-го КУ и j -го шлюза.

Для вычисления величины предлагается выбирать пары маршрутов,

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

где п,т - количество маршрутов, определенных для данной пары «источник-адресат» в сравниваемых топологиях, С^^ - степень совпадения /'-го маршрута одной топологии и ] -го маршрута другой.

Величину критерия Сг можно определить как среднее сходство на сегмент (участок маршрута) для сравниваемой пары маршрутов. Расчетное соотношение для Сг выглядит

следующим образом:

1 - ,

с=-

к+1-2{

где к ,1 - количество узлов в каждом из сравниваемых маршрутов; С ((- величина критерия сходства сегментов маршрутов, заключенных между г-

ыми (/+1)-ым узлами одного маршрута и у'-ыми (у+1)-ым узлами другого.

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

При этом C„g = 0 будет достигаться только в тех случаях, когда сравниваемые участки маршрутов будут иметь противоположные направления. Несмотря на достижимость нулевого значения для критерия сравнения отдельных сегментов маршрута С , критерий

сравнения маршрутов Сг при этом будет иметь область значений (0;1], исключающую

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

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

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

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

При создании ПМО был использован язык программирования С++ и интегрированная среда разработки C++Builder 6.0.

Разработанное приложение Topology Builder способно функционировать в среде MS Windows и обладает следующими основными функциональными возможностями:

• проектирование плана помещения, в котором развертывается БСС;

• формирование областей возможного размещения узлов БСС в помещении;

• проектирование рациональной топологии БСС (3 этапа);

• формирование ZigBee-оптималыюй (3 критерия) топологии БСС на рациональном множестве узлов;

• сравнение топологий БСС;

• создание и использование шаблонов узлов для проектирования БСС;

• сохранение и восстановление сохраненных исходных данных и топологий в XML-формате;

• ЗО-визуализация помещений, узлов БСС, топологий БСС.

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

топологий, ЗО-визуализации, общего интерфейса пользователя и обеспечения функционирования. Исходный код размещен в 44 файлах, суммарное количество строк в которых превышает 14000. Общее количество декларированных классов (в т.ч. унаследованных от представленных библиотекой OWL) составляет 54.

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

• достижение возможного минимума количества ретрансляций;

• объединение нескольких маршрутов в один;

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

• построение начального приближения к решению;

• сравнение топологий БСС;

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

t~NBDNUnk

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

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

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

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

Первый метод основан на минимизации количества ретрансляций сообщений при прокладке оптимального маршрута, элементарная функция потерь для него определяется как W = 1, Второй метод максимизирует вероятность успешной передачи и основан на использовании информации о качестве сигнала - значении LQI, предоставляемой приемником узла, что регламентировано стандартом IEEE 802.15.4. Спецификация ZigBee предполагает расчет этого критерия с помощью соотношения:

W =

1

mini 7,

1 | LQI>75 3| 50 < LQI<75, 71 LQI<50

где Р1 - вероятность успешной передачи сообщения.

Ещё один подход к расчету критериальной функции оптимальности г!§Вее-маршрутизации состоит в модификации второго метода, заключающейся в расширении градации уровней качества сигнала, и, с учетом возможного диапазона значений И31=0..255, предполагает вычисление элементарной функции потерь }¥ из соотношения: ^ = 16-^1 (НУ 16),

По результатам экспериментов, в которых варьировались начальные условия (количество и расположение узлов, плотности потоков данных, генерируемых КУ), а также моделировалось случайное отклонение значений соотношения сигнал/шум на приемных антеннах узлов, что влияло на изменение зон радиовидимости узлов и перераспределение оптимальных маршрутов при использовании перечисленных критериев ZigBee-маршрутизации, была построена сводная таблица 1.

Таблица 1 - Сравнение величин критерия сходства топологий Ст

Критерий Отклонение соотношения сигнал/шум Ст о[ст] Кол-во экспериментов

Минимум ретрансляций - 0,49 0,012 100

±25% 0,4 0,031 100

Максимум качества сигнала - 0,58 0,019 100

±25% 0,4 0,032 100

Максимум качества сигнала (расширенная градация) - 0,62 0,018 100

±25% 0,4 0,032 100

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

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

Вместе с тем степень сходства рациональной и ZigBee-oптимaлы^oй топологий при случайных отклонениях значений сигнал/шум в диапазоне ±25% для всех методов расчета критериальной функции получается одинаковой, что показывает независимость характеристик решения от применяемого алгоритма маршрутизации при существенных вариациях условий коммуникации.

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

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

• Надежность БСС />'га") получаемая в результате моделирования процесса её эксплуатации;

• Среднее количество узлов к", вышедших из строя и нуждающихся в замене на момент окончания регламентного периода для каждой построенной топологии;

• Величина критерия совпадения рациональной и 21§Вее-оптимальной топологии.

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

Увеличение количества заменяемых узлов Уменьшение надежности

Рис. 2. Влияние уменьшения степени сходства топологий на ухудшение качества

решения

Из графиков видно, что при величине коэффициента совпадения топологий Ст >0,7 отличие их качественных характеристик не превышает 4%, что является пренебрежимо малой величиной.

При уменьшении степени совпадения топологий ухудшение качественных характеристик 2igBee-oптимaльнoй топологии по сравнению с рациональной более существенно - до 35% увеличения количества нуждающихся в замене узлов и до 10% уменьшения надежности. Эти показатели являются граничными, так как практически не

удается построить различные топологии на одном наборе узлов со степенью соответствия Сг < 0,4.

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

Учитывая результаты предыдущего вычислительного эксперимента, можно заключить, что при практической реализации БСС допустимо использование критерия ZigBee-oптимaлыюcти, основанного на максимизации качества сигнала с расширенной градацией его уровня. Возможный проигрыш в надежности сети составит в этом случае около 2%, а в стоимости обслуживания - 17%. Практически при отклонении условий коммуникации от расчетных более чем на 25%, ухудшение качественных характеристик БСС может достигать граничных значений при использовании любого критерия ZigBee-оптимальности.

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

3. Основные результаты работы

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

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

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

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

• На основе ПМО разработан программный продукт. Функциональное системное тестирование показало его работоспособность и соответствие заявленным требованиям.

• Поставлена, формализована и решена проблема сравнения топологий БСС.

• На основе использования алгоритма сравнения топологий разработано ПМО. На множестве тестовых задач показана его работоспособность.

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

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

1. Акимов Е.В. Сравнение топологий беспроводных сенсорных сетей (БСС). — «Вестник компьютерных и информационных технологий» №8, 2008 г. — М.: Машиностроение, 2008.

2. Акимов Е.В., Кузнецов М.Н. Вероятностные математические модели для оценки надежности беспроводных сенсорных сетей (БСС). — «Труды МАИ», №40, 2010 г.

3. Акимов Е.В. Сравнение топологий беспроводных сенсорных сетей. — 13-ая Международная конференция «Системный анализ, управление и навигация», Евпатория, 29 июня - 6 июля 2008 г. — М.: Изд-во МАИ-ПРИНТ, 2008. — 288 с. -сс. 144-147.

4. Акимов Е.В. Оптимизация топологии беспроводной сенсорной сети (БСС), осуществляющей мониторинг производственного помещения. — 7-ая Международная конференция «Авиация и космонавтика - 2008», МАИ, Москва, 20 - 23 октября 2008 г. — М.: Изд-во МАИ-ПРИНТ, 2008. — 236 с. - с. 113.

5. Акимов Е.В. Обоснование работоспособности алгоритма оптимизации топологии беспроводных сенсорных сетей. — Международная конференция «Distributed computer and communication networks. Theory and applications» (DCCN-2008), София, Болгария, 20 - 23 октября 2008 г. — М.: ИППИ РАН, 2008. — 204 с. - сс. 166- 170.

6. Акимов Е.В. Оценка надежности беспроводных сенсорных сетей (БСС). — 8-ая Международная конференция «Авиация и космонавтика - 2009», МАИ, Москва, 26 - 29 октября 2009 г. — М.: Изд-во МАИ-ПРИНТ, 2009. — 240 с. - с. 210

Заказ Jfe 48-а/09/10 Подписано в печать 08.09.2010 Тираж 100 экз. Усл. п.л. 1

ООО "Цифровичок", тел. (495) 649-83-30 www.cfr.ru; e-mail:info@cfr.ru

Содержание.

Введение.

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

1.1 Технологии беспроводных сенсорных сетей.

1.1.1 Стандарт IEEE 802.15.4.

1.1.2 Альянс ZigBee. Стек протоколов ZigBee.

1.1.3 Альтернативные технологии создания БСС.

1.1.4 Операционные системы и программные средства.

1.1.5 Ведущие производители оборудования и программного обеспечения для БСС.

1.2 Существующие проблемы БСС.

1.3 Задача проектирования топологии БСС.

1.4 Факторы, учитываемые при проектировании топологии БСС

1.5 Подходы к решению задачи проектирования топологии беспроводных сетей.

1.6 Выводы.

2. Глава 2. Формализация подхода к решению задачи проектирования рациональной топологии БСС.

2.1 Описание подхода к решению.

2.2 Математические модели.

2.2.1 Математическая модель топологии БСС.

2.2.2 Математическая модель узла БСС.

2.2.3 Математическая модель канала информационного взаимодействия узлов БСС.

2.2.4 Математическая модель механизма доступа узлов к среде передачи данных.

2.2.5 Математическая модель распределения плотностей входящих и исходящих потоков на узле.

2.2.6 Критерий оптимальности топологии.

2.3 Алгоритмы.

2.3.1 Алгоритм построения начального приближения к решению

2.3.2 Игровой алгоритм.

2.3.3 Игровой алгоритм с участием Природы.

2.3.4 Алгоритм расчета критерия сравнения топологий.

2.4 Выводы.

3. Глава 3. Программное обеспечение.

3.1 Функциональные возможности приложения.

3.2 Архитектура программного обеспечения.

3.3 Тестирование программного обеспечения.

3.3.1 Достижение минимума количества ретрансляций.

3.3.2 Объединение нескольких маршрутов.

3.3.3 Разнесение нагруженных маршрутов.

3.3.4 Построение начального приближения к решению.

3.3.5 Сравнение топологий.

3.4 Оценка быстродействия программного обеспечения.

3.5 Выводы.

4. Глава 4. Вычислительные эксперименты.

4.1 Целесообразность построения начального приближения к решению

4.2 Построение топологии простой БСС.

4.3 Построение топологии БСС производственного помещения

4.4 Сравнение критериальных функций ZigBee-маршрутизации

4.5 Исследование влияния отклонения топологии от оптимальной на качество решения.

4.6 Исследование влияния алгоритма CSMA/CA на снижение пропускной способности сети.

4.7 Выводы.

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

В настоящее время БСС находят все более широкое применение в качестве распределенных систем мониторинга различных объектов и физических процессов. Специфика данной задачи определяет общую структуру беспроводных сенсорных сетей, которые, как правило, представляют собой распределенные на большой территории информационно-измерительные комплексы [1—3].

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

Выделяют несколько различных типов узлов, которые могут входить в состав БСС [4]. К ним относятся:

• конечные устройства (КУ), оснащаемые сенсорами и осуществляющие измерения;

• ретрансляторы или маршрутизаторы, передающие информационные сообщения от КУ;

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

• мосты, связывающие разные БСС друг с другом;

• PAN-координатор (PAN - Personal Area Network), осуществляющий управление БСС и также выполняющий роль шлюза данных.

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

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

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

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

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

Перечисленные требования регламентирует стандарт беспроводной связи IEEE 802.15.4 [4, 5]. Данный стандарт, так же, как и IEEE 802.11 для технологии Wi-Fi, определяет два нижних уровня взаимодействия открытых систем (ISO-OSI) - физического (PHY) и управления доступом к среде (MAC) - нижнего подуровня канального уровня OSI. Действующий сегодня базовый вариант стандарта был принят в 2006 году, но продолжаются разработки его расширений IEEE 802.15.4х [5]. Особенностями стандарта являются низкое энергопотребление, короткое время подключения к сети, поддержка большого количества клиентов, возможность реализации требований стандарта в недорогих устройствах.

Для обеспечения совместимости беспроводных устройств, выпущенных различными производителями, осенью 2002-го года, ещё до выхода окончательной спецификации на IEEE 802.15.4, по инициативе компании Philips Semiconductor был образован ZigBee Alliance [6-8]. Целью образованного консорциума является выработка единого стандарта, регламентирующего взаимодействие беспроводных устройств на всех семи уровнях базовой модели OSI. Совокупность протоколов, реализованных на различных уровнях этой модели, называют стеком протоколов ZigBee. Альянс также занимается сертификацией решений, образовательными программами и развитием рынка БСС.

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

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

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

Цель работы

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

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

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

К основным задачам исследования относятся:

• Анализ и формализация особенностей и ограничений задачи проектирования рациональной топологии БСС;

• Разработка математической модели БСС, её компонентов и аспектов функционирования;

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

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

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

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

Объект исследования

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

Актуальность исследования

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

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

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

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

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

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

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

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

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

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

5. Разработаны математические модели, адаптированные для использования в алгоритме оптимизации топологии БСС:

• топологии БСС с учетом распределения входящих и исходящих информационных потоков на узлах сети;

• узла БСС с учетом показателей его надежности;

• зависимости вероятности успешного приема символа от соотношения сигнал/шум на приемной антенне;

• механизма конкурентного доступа узлов к среде передачи данных с предотвращением коллизий (CSMA/CA).

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

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

8. Разработано программно-математическое обеспечение (ПМО), реализующее алгоритмы оптимизации топологии, моделирование построения ZigBee-оптимальной топологии, сравнения топологий. ПМО разработано в среде C++Builder и обладает открытой объектной архитектурой.

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

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

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

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

Внедрения и апробация работы

Результаты исследований докладывались и обсуждались на всероссийских и международных конференциях в 2008-2009 годах, а также научно-технических конференциях и семинарах в Московском авиационном институте, Институте проблем передачи информации им. А.А. Харкевича РАН, Институте программных систем им. А.К. Айламазяна РАН.

Разработанный программный продукт был использован компанией ООО «MeshNetics» [9] в научно-исследовательских разработках по гранту Федерального агентства по науке и инновациям.

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

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

2. Коррективы к алгоритмам оптимизации топологии БСС в следующем составе:

• Учет влияния совместного несинхронизированного доступа узлов к сети на снижение её пропускной способности.

• Моделирование процесса эксплуатации БСС на заключительном этапе проектирования топологии с целью предварительной проверки работоспособности сети.

3. Алгоритм сравнения сетевых топологий.

4. Обоснование выбора критериальной функции оптимальной маршрутизации в сетях ZigBee.

5. Программная реализация алгоритмического обеспечения задачи проектирования и оптимизации топологии БСС

6. Результаты вычислительных экспериментов.

7. Программный продукт, предназначенный для решения задачи проектирования и оптимизации топологии БСС.

Структура диссертации

Диссертация состоит из введения, 4 глав, заключения и библиографического списка.

4.7 Выводы

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

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

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

• Установлены средние показатели степени соответствия рациональной и ZigBee-оптимальных топологий в смысле критерия, описанного в разделе 2.3.4.

• Получены данные о зависимости степени соответствия от изменений условий коммуникации узлов.

• Построены зависимости ухудшения качественных показателей БСС с ZigBee-оптимальной топологией от степени её соответствия рациональной топологии.

• Обоснованы рекомендации использования при маршрутизации в ZigBee-сетях критерия оптимальности, основанного на максимизации качества сигнала с расширенной градацией его уровня.

Исследование, связанное с имитационным моделированием механизма конкурентного доступа узлов к среде передачи данных (CSMA/CA), позволило описать характеристики существенных параметров математической модели этого механизма с целью использования их в алгоритме оптимизации топологии.

Заключение

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

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

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

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

• На основе ПМО разработан программный продукт. Функциональное системное тестирование показало его работоспособность и соответствие заявленным требованиям.

• Поставлена, формализована и решена проблема сравнения топологий БСС.

• На основе использования алгоритма сравнения топологий разработано ПМО. На множестве тестовых задач показана его работоспособность.

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

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

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

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

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

Кроме того, результаты исследований докладывались и обсуждались на всероссийских и международных конференциях в 2008 - 2010 годах, а также научно-технических конференциях и семинарах в Московском авиационном институте, Институте проблем передачи информации им. А.А. Харкевича РАН, Институте программных систем им. А.К. Айламазяна РАН.

Разработанный программный продукт был использован компанией ООО «MeshNetics» в научно-исследовательских разработках по гранту Федерального агентства по науке и инновациям.

1. Терентьев М.Н. Беспроводные сенсорные сети. Учебное пособие. — М.: Издательство МАИ, 2007.

2. Culler D., Estrin D., Srivastava M. Overview of Sensor Networks. — University of California, Berkeley, University of California, Los Angeles, 2004.

3. Lewis F. L., Wireless Sensor Networks. — Smart Environments: Technologies, Protocols, and Applications, New York, 2004.

4. IEEE Standards 802.15.4. Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications for Low-Rate Wireless Personal Area Networks (LR-WPANs). — IEEE Computer Society, 2006.

5. IEEE 802.15.4 WPAN-LR Task Group. IEEE 802.15 WPAN™ Task Group 4 (TG4), 2010. http://www.ieee802.org/15.

6. ZigBee Alliance, http://www.zigbee.org.

7. Sinem C.E. ZigBee/IEEE 802.15.4 Summary. — Berkeley, 09/2004.

8. Palo Wireless. ZigBee Resource Center, http://www.palowireless.com.

9. MeshNetics ZigBee products, http://www.meshnetics.com/zigbee-products/

10. Баскаков C.C. Стандарт ZigBee и платформа MeshLogic: эффективность маршрутизации в режиме «многие к одному». —

11. Первая миля (приложение к журналу «ЭЛЕКТРОНИКА: Наука, Технология, Бизнес»), 2008 г., №2-3.

12. Баскаков С.С., Оганов В.И. Беспроводные сенсорные сети на базе платформы MeshLogic. М.: Электронные компоненты, 2006 г., №8.

13. Micrium Embedded RTOS and Software Stacks. http://www.micrium.devicetools.com

14. TinyOS An open-source OS for sensor networks. http://www.tinyos.net/scoop.

15. Munk-Stander J., Scovgaard M., Nielsen T. Bachelor's Thesis. Implementing a ZigBee Protocol Stack and Light Sensor in TinyOS. — Department of Computer Science University of Copenhagen, October 2005.

16. Mascolo C., Musolesi M., Pasztor B. Demo Abstract: Data Collection in Delay Tolerant Mobile Sensor Networks using SCAR (Sensor Context-aware Adaptive Routing).

17. MANTIS Project, http://mantis.cs.colorado.edu.

18. Han C., Kumar R., Shea R., Kohler E., Srivastava M. A Dynamic Operating System for Sensor Nodes. — University of California, Los Angeles.

19. Inc. Crossbow Technology. Motes, smart dust sensors, wireless sensor networks. http://www.xbow.com/Products/productsdetails.aspx?sid=3.

20. CodeBlue: Wireless Sensor Networks for Medical Care. http://www.eecs.harvard.edu/~mdw/proi/codeblue.

21. Intel Inc. http://intel.com.

22. The Industrial Wireless Book. http://wireless.industrial-networking-com/articles/articleproduct.asp?id:::::9

23. Вишневский B.M., Ляхов А.И., Портной C.JL, Шахнович И.В. Широкополосные беспроводные сети передачи информации. — М. Техносфера, 2005, 592 с.

24. Вишневский В.М. Теоретические основы проектирования компьютерных сетей, — М.: Техносфера, 2003, 512 с.

25. Ермолаев С.Ю. Методы оптимизации размещения базовых станций для сетей стандарта WIMAX. — М.: «Инфокоммуникационные технологии», том 5, №2, 2007.

26. Шварц М. Сети ЭВМ. Анализ и проектирование. Пер. с англ. — М.: Радио и связь, 1981, 336 с.

27. Жожикашвили В.А., Вишневский В.М., Гинсбург Б.Н. Об адаптивном управлении потоками в сетях ЭВМ. — Доклад VIII Всесоюзного совещания по проблемам управления, Институт проблем управления, М., 1980, с. 637 - 639.

28. Вентцель Е.С. Исследование операций. — М.: «Советское радио», 1972.

29. Оуэн Г. Теория игр. — М.: «Вузовская книга», 2004.

30. Таха X. Введение в исследование операций. — М.-СПб.-К.: Издательский дом «Вильяме», 2005.

31. Мулен Э. Теория игр. — М.: «Мир»,1985.

32. Скляр Б. Цифровая связь. Теоретические основы и практическое применение. М.-СПб.-К.: Издательский дом «Вильяме», 2004.

33. Кочерчневский Г.Н. Антенно-фидерные устройства. — М.:, «Связь», 1972

34. Тихонов В.И. Статистическая радиотехника. — М.: «Советское радио», 1966.

35. Кудряшов С.В. Оптимальная маршрутизация информационных потоков в беспроводных сенсорных сетях. — М.: Известия РАН, ТиСУ, №1,2008.

36. Абрамович М., Стиган И. Справочник по специальным функциям с формулами, графиками и математическими таблицами. — М.: «Наука», 1979.

37. Березин И.С., Жидков Н.П. Методы вычислений. Учебное пособие для ВУЗов. — М.: «Физматлит», 1960.

38. Ray S, Starobinski D., Carruthers J.B. Performance of Wireless Networks with Hidden Nodes: A Queuing-Theoretic Analysis. — Department of Electrical and Computer Engineering, Boston University, Boston, MA 02215, USA.

39. Yue W, Matsumoto Y. Performance Analysis of CSMA/CA DFT Wireless LAN Systems with Pulse Signal Transmission for Multi-traffic. — 35th Hawaii International Conference on System Sciences

40. Ramachandran I., Das A.K., Roy S. Analysis of the contention access period of IEEE 802.15.4 MAC. — ACM Transactions on Sensor Networks, vol.3, 2007.

41. Takagi H., Kleinrock L. Optimal transmission ranges for randomly distributed packet radio terminals. — IEEE Transactions on Communications 32 (3): 246-257, March 1984.

42. Wu L., Varshney K. Performance analysis of CSMA and BTMA protocols in multihop networks: (I). Single channel case. — Informatics and Computer Science: An International Journal (120): 159 177, November 1999.

43. Элджер Дж. С++: Библиотека программиста. — С.-Пб.: «Питер», 2005.

44. Компиляторы С++. Ьир://ги^^реё1а.ощ/ш1к1/Категория:КомпиляторыС++

45. Сравнение IDE. http://ru.wikipedia.org/wiki/CpaBHemieIDE

46. Архангельский А.Я. Программирование в C++Builder 6. М.: Издательство «Бином», 2003.

47. Хантер Д., Рафтер Дж. и др. XML. Базовый курс. — М.: Вильяме, 2009, 1344 с.

48. Гамма Э., Хелм Р., Джонсон Р. и др. Приемы объектно-ориентированного проектирования. Паттерны проектирования. — С.-Пб.: «Питер», 2001, 368 с.

49. Херн Д., Паулин Бейкер М. Компьютерная графика и стандарт OpenGL. — М: Вильяме, 2005, 1168 с.

50. Гмурман В.Е. Теория вероятностей и математическая статистика,1. М.: «Высшая школа», 2003.

51. Вентцель Е.С. Теория вероятностей и её инженерные приложения.

52. М.: «Высшая школа», 2000 г., 480 с.