Содержание к диссертации
Введение
1. Глава 1. Обзор технологий и проблем беспроводных сенсорных сетей 17
1.1 Технологии беспроводных сенсорных сетей 17
1.1.1 Стандарт ШЕЕ 802.15.4 20
1.1.2 Альянс ZigBee. Стек протоколов ZigBee 24
1.1.3 Альтернативные технологии создания БСС 27
1.1.4 Операционные системы и программные средства 29
1.1.5 Ведущие производители оборудования и программного обеспечения для БСС 34
1.2 Существующие проблемы БСС 38
1.3 Задача проектирования топологии БСС 40
1.4 Факторы, учитываемые при проектировании топологии БСС 42
1.5 Подходы к решению задачи проектирования топологии беспроводных сетей 43
1.6 Выводы 45
2. Глава 2. Формализация подхода к решению задачи проектирования рациональной топологии БСС 47
2.1 Описание подхода к решению 47
2.2 Математические модели 55
2.2.1 Математическая модель топологии БСС 55
2.2.2 Математическая модель узла БСС 60
2.2.3 Математическая модель канала информационного взаимодействия узлов БСС 64
2.2.4 Математическая модель механизма доступа узлов к среде передачи данных 71
2.2.5 Математическая модель распределения плотностей входящих и исходящих потоков на узле 73
2.2.6 Критерий оптимальности топологии 76
2.3 Алгоритмы 80
2.3.1 Алгоритм построения начального приближения к решению 80
2.3.2 Игровой алгоритм 84
2.3.3 Игровой алгоритм с участием Природы 94
2.3.4 Алгоритм расчета критерия сравнения топологий 99
2.4 Выводы 107
3. Глава 3 . Программное обеспечение 108
ЗЛ Функциональные возможности приложения 109
3.2 Архитектура программного обеспечения 114
3.3 Тестирование программного обеспечения 119
3.3.1 Достижение минимума количества ретрансляций 120
3.3.2 Объединение нескольких маршрутов 121
3.3.3 Разнесение нагруженных маршрутов 122
3.3.4 Построение начального приближения к решению 123
3.3.5 Сравнение топологий 124
3.4 Оценка быстродействия программного обеспечения 126
3.5 Выводы 127
4. Глава 4. Вычислительные эксперименты 128
4.1 Целесообразность построения начального приближения к решению 128
4.2 Построение топологии простой БСС 130
4.3 Построение топологии БСС производственного помещения 131
4.4 Сравнение критериальных функций ZigBee-маршрутизации 135
4.5 Исследование влияния отклонения топологии от оптимальной на качество решения 139
4.6 Исследование влияния алгоритма CSMA/CA на снижение пропускной способности сети 143
4.7 Выводы 146
Заключение 148
Список использованных источников 151
- Ведущие производители оборудования и программного обеспечения для БСС
- Критерий оптимальности топологии
- Тестирование программного обеспечения
- Целесообразность построения начального приближения к решению
Введение к работе
Актуальность темы исследования
В настоящее время беспроводные сенсорные сети (БСС) находят все более широкое применение в качестве распределенных систем мониторинга различных объектов и физических процессов. Специфика данной задачи определяет общую структуру БСС, которые, как правило, представляют собой распределенные на большой территории информационно-измерительные комплексы. В состав таких сетей входит множество миниатюрных устройств – узлов, среди которых выделяют несколько различных типов в соответствии с их функциональностью:
конечные устройства (КУ), оснащаемые сенсорами и осуществляющие измерения;
ретрансляторы или маршрутизаторы, передающие сообщения c результатами измерений от КУ;
шлюзы, собирающие сообщения от КУ и осуществляющие коммутацию БСС с высокоскоростными магистралями передачи данных, посредством которых эти сообщения доставляются в вычислительный центр;
мосты, связывающие разные БСС друг с другом;
PAN-координатор (PAN – Personal Area Network), осуществляющий управление БСС и также выполняющий роль шлюза данных.
Узлы могут полностью или частично объединять в себе функциональность нескольких типов (например, PAN-координатор может также являться шлюзом и мостом, а КУ – маршрутизатором).
Сфера возможного применения таких систем очень широка. БСС могут быть использованы в строительстве и архитектуре, промышленности, сельском хозяйстве, сейсмологии, на транспорте, в медицине и других отраслях человеческой деятельности.
Отсутствие проводных коммуникаций существенно облегчает процесс развертывания и реконфигурирования сети, снижает стоимость системы; автономность и миниатюрность устройств обеспечивает возможность их размещения в труднодоступных местах и на больших территориях. Беспроводные решения незаменимы, когда необходимо связать в сеть постоянно движущиеся или часто перемещаемые узлы. Очевидным же недостатком беспроводных решений оказывается их меньшая надежность, как в смысле гарантированности доставки данных за ограниченное время, так и в смысле защиты передаваемой информации от несанкционированного доступа.
Для конечного потребителя услуг, предоставляемых информационно-измерительным комплексом на основе использования БСС, важно минимизировать затраты на его приобретение и дальнейшее техническое обслуживание при выполнении ограничений на решение целевой задачи с заданной надежностью. Реализация данного требования потребителя приводит, с одной стороны, к сокращению количества используемых узлов-ретрансляторов, а, с другой стороны, не позволяет вытянуть их в цепь по кратчайшему расстоянию между КУ и шлюзами с учетом требуемого уровня надежности доставки данных. Вместе с тем, при увеличении количества КУ и ретрансляторов остро встают проблемы ограниченной пропускной способности узлов и взаимного влияния потоков данных друг на друга. Перечисленные условия определяют необходимость решения задачи выбора рационального геометрического расположения ретрансляторов, а также оптимальной маршрутизации потоков данных между ними, что и составляет понятие «рациональная топология беспроводной сенсорной сети». Такая топология позволит сократить трафик и снизить энергопотребление на узлах, что, в свою очередь, увеличит время безотказной работы сети и снизит общие затраты на её обслуживание, заключающиеся в замене оборудования и/или элементов питания.
В настоящее время при построении беспроводной сенсорной сети выбор расположения ретрансляторов обычно производится на основе результатов натурного моделирования, связанного с проведением многочисленных экспериментов, замеров напряженности электромагнитного поля, что существенно повышает трудоемкость и стоимость процесса развертывания БСС.
Наличие приведенных проблем обусловливает актуальность задачи оптимизации топологии БСС. Решение этой задачи на практическом уровне позволит в значительной степени снизить трудозатраты и финансовые расходы при внедрении систем мониторинга.
Цель работы
Целью работы является снижение ресурсозатрат при проектировании, развертывании и эксплуатации БСС посредством алгоритмической и программной реализации расчёта рациональной топологии сети с учетом возможности её практического воспроизведения, а также создания программного продукта, обеспечивающего получение этого решения.
Объект исследования
Объектом настоящего исследования являются беспроводные сенсорные сети, а предметом – разработка эффективных методов и средств их проектирования, включающих оптимизацию, сравнение и анализ топологий БСС и их качественных характеристик (надежность и стоимость обслуживания).
Методы исследования
В работе использованы методы теории игр и динамического программирования, а также методы имитационного моделирования и статистических испытаний. Перечисленные методы реализованы в программно-математическом обеспечении (ПМО), с помощью которого проведены вычислительные эксперименты.
Основные задачи исследования
-
Анализ и формализация особенностей и ограничений задачи проектирования рациональной топологии БСС;
-
Разработка математической модели БСС, её компонентов и аспектов функционирования;
-
Разработка алгоритма проектирования рациональной топологии БСС, обеспечивающего учет проанализированных особенностей и ограничений;
-
Разработка алгоритма сравнения топологий и использование его для анализа возможности практического воспроизведения рационального решения;
-
Разработка ПМО, реализующего алгоритмы проектирования и сравнения топологий;
-
Создание программного продукта, обеспечивающего комплексное решение задачи проектирования рациональной топологии.
Научная новизна работы
-
Поставлена задача оптимизации топологии БСС, предполагающая выбор рационального расположения ретрансляторов сети и маршрутизации потоков данных между ними.
-
Задача проектирования топологии БСС рассматривается как игровая, в которой игроками выступают КУ, оснащенные сенсорами и генерирующие сообщения с результатами измерений. Конкуренция между ними обусловлена их совместным использованием ретрансляторов сети для доставки потоков данных на шлюз. Такой подход обеспечивает учет их взаимного влияния при оптимизации топологии.
-
Предложен трехэтапный алгоритм оптимизации топологии: построение начального приближения, оптимизирующего достижимое в игровой ситуации равновесие Нэша; уточнение решения с использованием игрового метода итераций; обеспечение надежности сети путем включения в состав игроков Природы.
-
Формализованы следующие ограничения задачи оптимизации топологии: на допустимые области размещения узлов, на трафик через узел, на надежность доставки сообщений, на количество соединений узла, а также особенности задачи, связанные с влиянием внешних источников ЭМИ на вероятность успешного приема пакетов, совместным использованием ресурсов сети для транспортировки различных потоков данных, использованием более одного типа ретрансляторов, движением КУ, проблемой реализации рациональной топологии в БСС.
-
Разработаны математические модели:
-
топологии БСС с учетом распределения входящих и исходящих потоков данных на узлах сети;
-
узла БСС с учетом показателей его надежности;
-
зависимости вероятности успешного приема символа от соотношения сигнал/шум на приемной антенне;
-
механизма конкурентного доступа узлов к среде передачи данных.
-
-
Предложена физическая интерпретация результатов, полученных с использованием численных методов теории игр: оптимальная стратегия игрока, цена игры, решение в смешанных стратегиях.
-
Предложен алгоритм количественного измерения сходства сетевых топологий, предназначенный для анализа степени соответствия топологии, построенной с использованием критериальной функции оптимальности маршрутизации ZigBee, и рациональной топологии.
-
Разработано ПМО, реализующее алгоритмы оптимизации топологии, моделирование построения ZigBee-оптимальной топологии, сравнения топологий.
-
Проведен анализ изменения качественных характеристик БСС (надежности и стоимости обслуживания) в связи с отличием её топологии от рациональной.
-
Предложена модифицированная критериальная функция оптимальности маршрутизации в сетях ZigBee, основанная на максимизации качества сигнала с расширенной градацией его уровня и обеспечивающая уменьшение отличий ZigBee-топологии от рациональной.
-
Проведены вычислительные эксперименты, подтвердившие работоспособность алгоритма оптимизации топологии и обоснованность его структуры. По результатам вычислительных экспериментов также установлены средние показатели степени соответствия рациональной и ZigBee-оптимальных топологий, получены данные о зависимости степени соответствия от изменения условий коммуникации узлов.
-
Разработан программный продукт, предназначенный для решения задачи оптимизации топологии БСС и обладающий возможностью её 3D-визуализации.
Практическая значимость работы
Практическая значимость полученных в работе результатов состоит в возможности использования предложенного подхода к оптимизации топологии БСС, математических моделей и алгоритмов, а также разработанного программного продукта при решении задач, связанных с проектированием топологии беспроводных сенсорных сетей.
Основные положения, выносимые на защиту
-
Математическая модель беспроводной сенсорной сети и её топологии.
-
Коррективы к алгоритмам оптимизации топологии БСС в следующем составе:
-
Учет влияния совместного несинхронизированного доступа узлов к сети на снижение её пропускной способности.
-
Моделирование процесса эксплуатации БСС на заключительном этапе проектирования топологии с целью предварительной проверки работоспособности сети и оценки качественных характеристик (надежности и стоимости обслуживания).
-
-
Алгоритм сравнения сетевых топологий.
-
Обоснование выбора критериальной функции оптимальной маршрутизации в сетях ZigBee.
-
Программная реализация алгоритмического обеспечения задачи оптимизации топологии БСС
-
Результаты вычислительных экспериментов.
-
Программный продукт, предназначенный для решения задачи оптимизации топологии БСС.
Публикации
Основные результаты работы изложены в 6 публикациях, приведенных в списке литературы, в т.ч. 2 статьи в изданиях, рекомендованных ВАК.
Апробация работы
Результаты исследований докладывались и обсуждались на всероссийских и международных конференциях в 2008-2010 годах, а также научно-технических конференциях и семинарах в Московском авиационном институте, Институте проблем передачи информации им. А.А. Харкевича РАН, Институте программных систем им. А.К. Айламазяна РАН.
Достоверность результатов
Достоверность результатов, полученных в работе, подтверждается:
Корректным использованием математических методов теории игр, динамического программирования и статистических испытаний, а также проведенным тестированием разработанного ПМО и результатами вычислительных экспериментов.
фактом использования полученных результатов в научно-исследовательских разработках по гранту Федерального агентства по науке и инновациям ООО «MeshNetics».
Структура диссертационной работы
Диссертация состоит из введения, 4 глав с 5 таблицами и 42 иллюстрациями, заключения и библиографического списка, состоящего из 53 наименований. Общий объем работы составляет 155 страниц.
Ведущие производители оборудования и программного обеспечения для БСС
Сегодня ведущие мировые производители электронных компонентов и ПО для создания БСС представляют широкий спектр технических решений, позволяющих в короткие сроки разворачивать сети, предназначенные для решения различных прикладных задач. Большинство производимых устройств собрано по классической схеме — отдельные чипы сенсоров, микроконтроллера и приемопередатчика. Для связи этих устройств между собой часто используется интерфейс обмена данными SPI (поддерживаемый ведущими производителями специализированных микросхем — СЫрсоп, Atmel и др.) Существуют и другие решения, например от компании Intel, в которых все устройства размещены в одном чипе. Во всех случаях производители стремятся упростить протоколы взаимодействия и обеспечить наименьшую потребляемую мощность микросхем. Рассмотрим несколько известных продуктов.
Одним из первых производителей узлов БСС и готовых решений на их базе стала компания Crossbow Technologies [21]. Наиболее известными её продуктами являются миниатюрные модули MICA2, MICAz, объединяющие в себе приемопередатчик и микроконтроллер, а также узлы TELOS (показаны на рисунке 5.
Компания Crossbow предлагает также законченные платформы для быстрого развертывания БСС различного прикладного назначения. К таким платформам относится MeshWorks, в состав которой входят следующие средства: узлы БСС на базе модулей MICAz, XMesh (стек протоколов ZigBee и операционная система на базе TinyOS, позволяющая удаленно конфигурировать программное обеспечение на узлах), XServe (средства для передачи данных в ПК) и пользовательское приложение MoteView для удобного удаленного анализа, управления и конфигурации БСС. На базе продукции Crossbow реализовано много решений, одно из которых описано в разделе 1.1.4.
Среди решений, нашедших применение в биомедицинской практике, можно отметить продукцию, разрабатываемую в рамках проекта CodeBlue, в котором участвуют такие компании, как Intel Corp., Sun Microsystems, a также университет Беркли и Бостонский медицинский центр [22]. На рисунке 6 представлено устройство с торговым названием Pluto - наручный детектор двигательной активности человека, снабжённый трёхосным акселерометром. Устройство обладает также Bluetooth и USB интерфейсами. Рисунок 6. Наручный детектор двигательной активности Pluto, снабжённый трехосным акселерометром.
Компания Intel, являющаяся одним из ведущих производителей оборудования и программного обеспечения для БСС, также предлагает различные практические решения. Одним из известных реализованных ею проектов стала система мониторинга состояния оборудования на основе БСС, развернутая в Орегоне на одном из своих заводов по производству микросхем. Сеть отслеживает уровень вибрации оборудования для очистки воды, предоставляя данные о потребности в профилактическом обслуживании. Точно так же, как по вибрации двигателя автомобиля можно определить его состояние, вибрация оборудования свидетельствует о том, соответствуют ли условия его эксплуатации нормальным. По оценкам специалистов Intel развертывание такой системы мониторинга позволяет сократить время простоя оборудования без ручного контроля, что существенно снижает затраты на производство.
Другим примером успешного применения БСС Intel является экспериментальная система поддержки профилактического обслуживания нефтеналивного танкера, принадлежащего компании British Petroleum. Проводимое тестирование должно было ответить на вопрос, может ли сенсорная сеть работать на борту судна, в условиях экстремальных температур, высокой вибрации и значительного уровня радиочастотных помех в некоторых помещениях судна. Сенсорная сеть была установлена на борту танкера и работала более четырех месяцев. В процессе этой опытной эксплуатации система обеспечивала надежный сбор данных и самовосстанавливалась в случае возникновения ошибок. Журнал Info World включил этот проект в число 100 лучших проектов 2004 г. и удостоил его награды как «инновационный новый проект, позволяющий подчеркнуть возможности ИТ-сообщества». Компания ВР теперь планирует использование сенсорных сетей в масштабах всей компании - на судах, в производстве и нефтеперегонных процессах [23].
Среди реализованных проектов развёртывания БСС, осуществляющих мониторинг параметров окружающей среды в промышленных и офисных зданиях, можно отметить систему контроля освещения (компания Philips, бизнес-центр в Чикаго), систему оплаты товаров с помощью мобильного телефона (компания Telecom Italia, проект Zsim), систему автоматического считывания показаний счетчиков (компания Amron), интегрированную систему управления мультимедиа-устройствами, безопасностью, освещением и кондиционированием (компания Control 4) [24].
Среди наиболее, известных производителей законченных решений, позволяющих реализовывать различные прикладные системы, можно отметить также компании Freescale Semiconductor, Ember, Jennie. Многие из фирм, специализирующихся производстве узлов БСС, используют в своих решениях продукты фирм Chipcon (маломощные приемопередатчики), Atmel (экономичные и функциональные контроллеры ATmega), и Microchip (микроконтроллеры семейства РІС). Известны 8- и 16-битные решения, целесообразность применения каждого из них обусловлена конкретной прикладной задачей.
Все компании, предлагающие сегодня на рынке решения для быстрого развертывания БСС, включают в свои комплекты устройства, предназначенные для отладки и тестирования работы сети. Основой таких устройств является узел ZigBee, к которому подключено различное периферийное оборудование (датчики, индикаторы, панель управления режимами) и дополнительные коммуникационные интерфейсы для связи с ПК (RS-232, USB, Bluetooth). Такие узлы предоставляют возможность натурного моделирования работы БСС и исследования её в различных аспектах, например: отслеживание потоков данных, проверка мощности и качества сигнала, тестирование работы приложений и т.д. Журнал наблюдаемых событий формируется в ПК и может быть проанализирован разработчиком.
На рисунке 7 показан отладочный узел БСС, предлагаемый компанией Meshnetics [9]. Узел имеет модульную конструкцию, что позволяет легко изменять его конфигурацию оборудования.
Критерий оптимальности топологии
К основным показателям качества БСС можно отнести её стоимость и надёжность. Как правило, стремление снизить стоимость какой-либо технической системы приводит к уменьшению её надёжности, что может оказаться недопустимым по условиям ее эксплуатации, что, в конечном итоге, приведет к увеличению ее стоимости за счет замены вышедших из строя компонентов. Поэтому в данном случае при проектировании оптимальной топологии сети предлагается задаться требуемым уровнем надёжности БСС и сформировать структуру сети, обладающую минимальной стоимостью при данном ограничении. Под надёжностью БСС будем понимать вероятность доставки информационных сообщений от каждого КУ до шлюза. С учётом сделанных ограничений на учитываемые факторы определим надёжность доставки как вероятность безошибочной передачи информационного сообщения по выбранному маршруту с учетом вероятности выхода из строя узлов, участвующих в цепочке ретрансляций, и вероятности безошибочной передачи сообщения между каждой парой узлов на маршруте.
Стоимость же БСС в общем случае определяется стоимостью ее узлов, а также стоимостью их технического обслуживания (периодическая замена вышедших из строя узлов или замена израсходованных источников тока узлов). Известно, что продолжительность жизни узла БСС в нулевом приближении пропорциональна совокупной продолжительности периодов приёма и/или передачи сообщений. Таким образом, логично определить стоимость одной ретрансляции как линейную функцию суммарной плотности информационного потока, проходящего между двумя узлами. Будем считать, что достижение максимальной плотности информационного потока на узле эквивалентно введению в состав сети нового узла.
Наложение ограничения, связанного с введение величины uwa" , вызвано следующими соображениями. В соответствии с предложенной моделью канала информационного взаимодействия каждый узел обладает определенным радиусом радиовидимости, в пределах которого уровень излучаемого узлом сигнала достаточно велик. При осуществлении адресной трансляции одним из узлов, все узлы, находящиеся в зоне его радиовидимости, не могут начать передачу, чтобы не вызвать коллизии. Режим приема возможен только для адресата, остальные узлы должны перейти в режим ожидания конца передачи.
Предложенная методика расчета величин Cmote и Сг, определяющих стоимостные показатели БСС, позволяет учесть в начальном приближении факторы совместного использования ретрансляторов несколькими информационными потоками и их взаимного влияния. В процессе построения топологии необходимо минимизировать стоимость БСС, для чего должен быть сформирован некий обобщенный критерий оптимальности по стоимости.
Введём понятие элементарной функции потерь W, равной сумме условных стоимостей одной ретрансляции и узла, её осуществляющего: w = c +с
Будем называть суммарной функцией потерь (или просто функцией потерь) W величину, равную сумме затрат, необходимых для доставки сообщения от одного из КУ до шлюза. Суммарная функция потерь определяется как сумма элементарных функций потерь для каждого из узлов, участвующих в доставке сообщения: где R — множество узлов маршрута доставки сообщений от данного КУ до шлюза.
Таким образом, для игрового алгоритма величина суммарной функции потерь будет определять проигрыш игрока в результате каждого его хода (по сути, являясь ценой игры для данного игрока). Выбор оптимальной стратегии (маршрута с наименьшей стоимостью) будет в этом случае состоять в последовательном переборе всех возможных вариантов с целью поиска маршрута, характеризующегося наименьшим значением функции потерь (минимальной стоимостью).
Методики расчета величины We рассматриваются применительно к каждому этапу алгоритма оптимизации топологии в соответствующих разделах.
В данном разделе рассматриваются вычислительные алгоритмы, обеспечивающие практическое проектирование оптимальной топологии БСС с использованием ЭВМ. Z3.1 Алгоритм построения начального приближения к решению
Как уже было отмечено, целью построения начального приближения к решению является предварительное определение состава сети, т.е. выбор из множества ретрансляторов, размещенных в допустимой области, определенной группы, обеспечивающей решение целевой задачи (доставку сообщений от КУ до PAN-координатора) без учета плотностей информационных потоков, принимаемых и передаваемых узлами.
В основе предлагаемого алгоритма лежит метод динамического программирования, известный также как метод Форда-Беллмана [30, 32]. Практически, здесь решается задача прокладки совокупности маршрутов от каждого из КУ до шлюза на множестве ретрансляторов (фазовом пространстве), обладающей наименьшей стоимостью в смысле определенного критерия, представляемого суммарной функцией будущих потерь. Предлагаемый алгоритм базируется на решении классической задачи поиска оптимального маршрута.
Подход к решению задачи состоит в следующем. Для каждого узла, претендующего на включение в состав будущей сети, составляется таблица маршрутизации, в которой указываются стоимости оптимальных маршрутов, проходящих через каждый из соседних узлов до каждого из КУ. Стоимости маршрутов рассчитываются как значения суммарных функций потерь на доставке сообщений от данного узла до конкретного КУ. Общий вид таблицы маршрутизации представлен в таблице 3.
Тестирование программного обеспечения
С целью подтверждения работоспособности алгоритмов оптимизации и сравнения топологий, а также проверки корректности разработанного программного обеспечения был проведен ряд тестов. Тестовые сценарии были направлены на исследование работы описываемых алгоритмов в следующих аспектах:
Достижение возможного минимума количества ретрансляций.
Объединение нескольких маршрутов в один.
Разнесение в пространстве маршрутов, по которым осуществляется передача информационных потоков большой плотности.
Построение начального приближения к решению
Сравнение топологий БСС
Тесты заключались в моделировании некоторой достаточно простой структуры БСС и процесса построения (сравнения) топологий. Общими для большинства тестовых сценариев (если иное специально не оговаривается) являются следующие исходные данные:
Область развертывания БСС представляет собой плоский квадрат размером 100x100 м (такие параметры области развертывания упрощают отображение и контроль результатов, одновременно не оказывая влияния на работу алгоритма и функционирование ПО).
Уровень надежности доставки сообщений у= 0,999.
Максимальное количество дополнительных ретрансляций итах = 4.
Радиус зоны радиовидимости rmax, одинаковый для всех узлов, рассчитан для сообщений длиной 37 байт (минимальная длина генерируемых КУ сообщений в соответствии со спецификацией IEEE 802.15.4 [4]). Величина гтах составила 29,6 м.
Сценарии тестов предполагают вариации параметров областей допустимого размещения узлов, взаимного расположения КУ и PAN-координатора, а также величин плотностей информационных потоков, генерируемых КУ.
Все тесты проводились на ЭВМ со следующей конфигурацией: процессор - Intel Core Duo Т2130 (тактовая частота 1800 МГц), объем ОЗУ -2 ГБ, операционная система - Windows ХР SP2.
В результате проведения этого теста должна быть установлена способность алгоритма оптимизации топологии и реализующего его ПО минимизировать количество ретрансляторов, включаемых в топологию БСС.
PAN-координатор расположен в центре допустимой области развертывания БСС и выполняет функции шлюза. Вокруг него на расстоянии 20 м размещены 60 КУ, каждый из которых генерирует информационный поток плотностью 0,13(3) бит/сек. (1 байт в минуту). Ретрансляторы размещены в узлах регулярной сетки (вокруг PAN-координатора с шагом 7 м, в остальной части допустимой области - с шагом 10 м).
Общий вид смоделированной БСС с изображением маршрутов передачи информационных потоков показан на рисунке 27.
Построенная в результате БСС не включает в себя ни одного ретранслятора, что может служить достаточным условием оптимальности решения и свидетельствует об успешном выполнении теста.
Этот тест направлен на проверку способности алгоритма и реализующего его ПО минимизировать количество ретрансляторов, включаемых в БСС, посредством объединения маршрутов от нескольких КУ до шлюза. На рисунке 28 представлены два случая возможного размещения КУ и шлюза - PAN-координатора, а также маршрутов передачи информационных потоков, соответствующих выбранным размещениям. Плотность информационного потока, генерируемого каждым КУ, составляет ОДЗ(З) бит/сек. (1 байт в минуту). Шаг регулярной сетки, в узлах которой размещены ретрансляторы -5 м. Корректным результатом будет считаться такой, при котором в состав БСС будет включены ретрансляторы, используемые более чем одним информационным потоком. Рисунок 28. Объединение нескольких маршрутов в один. В результате проведения теста получены рациональные решения, свидетельствующие об эффективности объединения маршрутов и подтверждающие работоспособность направленных на это элементов алгоритма. Разнесение нагруженных маршрутов Тест направлен на проверку способности алгоритма и реализующего его ПО выполнять ограничение на допустимую плотность информационных потоков. На рисунке 29 показаны для сравнения две модели БСС, отличающихся только плотностью генерируемых КУ информационных потоков. На схеме, изображенной слева, эта величина для каждого КУ составила 0,13(3) бит/сек., а на схеме справа - 10 кбит/сек.
Целесообразность построения начального приближения к решению
Целью этого вычислительного эксперимента является исследование целесообразности использования начального приближения к решению, призванного компенсировать недостаток игрового алгоритма оптимизации топологий, связанный с наличием нескольких состояний равновесий Нэша и возможностью получения квазиоптимального решения.
Сценарий эксперимента состоит в моделировании построения топологии как с использованием начального приближения, выполненного в соответствии с описанным в разделе 2.3.1 алгоритмом, так и без него при помощи лишь второго этапа алгоритма оптимизации (см. раздел 2.3.2). Результат эксперимента, таким образом, должен позволить установить факт наличия или отсутствия преимуществ решения, построенного с учетом начального приближения.
Исходные данные для моделирования построения топологии БСС в обоих случаях были аналогичны указанным в разделе 3.3. При этом ретрансляторы располагались в узлах регулярной сетки с шагом 10 м, а плотности информационных потоков С/, генерируемых пятью КУ, размещенными как показано на рисунке 32, были одинаковыми и составляли 8 бит/сек. На схеме, изображенной слева на этом рисунке, представлена топология БСС, построенная без выполнения начального приближения к решению, а справа - с его выполнением.
Решение, показанное на правой схеме, демонстрирует целесообразность применения алгоритма начального приближения в качестве первого этапа построения оптимальной топологии, так как конфигурация сети при этом улучшается (за счет нахождения глобального оптимума решений в классе рациональных в смысле применяемой критериальной функции), что проявляется в уменьшении количества задействованных в сети узлов.
Цель данного эксперимента — установить способность решения задачи проектирования топологии БСС с учетом пространственного размещения большого количества узлов при помощи разработанного приложения Topology Builder; продемонстрировать возможность ЗО-отображения полученного решения, визуально оценить его рациональность. Модель исследуемой БСС состоит из 225 потенциальных ретрансляторов, 6 КУ, плотность информационных потоков которых составляет 1 кбит/сек. и координатора (являющегося и шлюзом данных). Потенциальные ретрансляторы размещены регулярно с шагом 5 м на двух вертикальных перегородках, имеющих размеры 60 х 20 м и 100 х 20 м и ориентированных под прямым углом друг к другу, и с шагом 10 м на горизонтальном перекрытии размером 60 х 100 м, соединяющим эти перегородки. Для построения решения использовались первые два этапа алгоритма оптимизации топологии (т.е. без применения механизма обеспечения надежности - игры с Природой). Изображение модели сети с обозначенными рассчитанными направлениями информационных потоков между узлами, полученное в результате обработки приложением Topology Builder описанного сценария, показано на рисунке 33.
. Построение топологии БСС с большим количеством узлов. 3D модель
Из рисунка видно, что построенная БСС включает в себя 7 узлов-ретрансляторов, выбранных из числа потенциальных рациональным образом. Время расчета такой топологии составило 2,5 мин.
Цель данного эксперимента - исследовать возможность и целесообразность применения разработанного приложения для решения задач проектирования топологии БСС, приближенных к практическим.
Как уже было отмечено, БСС представляет собой распределенный информационно-измерительный комплекс, который может осуществлять контроль параметров окружающей среды (например, температуры, влажности, освещенности) и наблюдение за состоянием оборудования производственного помещения (например, контроль вибраций с целью прогнозирования износа и предупреждения разрушений). Актуальность создания таких комплексов обусловлена увеличением технологичности и повышением требований к точности современных производств.
Смоделируем производственное помещение с расположенными в нем конвейерными линиями, станками и другим оборудованием. Зафиксируем расположение 45-ти конечных устройств БСС, оснащенных различными сенсорами, координатора сети и двух шлюзов данных. План-схема такого помещения изображена на рисунке 34. Данные от каждого из КУ должны представлять собой краткие сообщения длиной 128 байт с информацией об измерениях сенсоров, поступающие раз в 5 секунд.
Ретрансляторы, необходимые для доставки данных от КУ допустимо размещать на стенах помещения, конвейерных линиях и собственно технологическом оборудовании. На рисунке 35 показано размещение потенциальных ретрансляторов, претендующих на включение в сеть и необходимых для построения решения с использованием алгоритма оптимизации топологии, в одной из половин помещения.
