Автореферат квалификационной работы магистра

Вступление

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

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

Таким образом, появляется новый класс беспроводных сетей малой дальности. Эти сети обладают рядом особенностей. Устройства, входящие в эту сеть, имеют небольшие размеры и питаются в основном от батарей. Эти сети являются Ad-Hoc сетями – высокоспециализированными сетями, с динамическим изменением количественного состава сети. В связи с этим возникают задачи создания и функционирования данных сетей – организация добавления и удаления устройств, аутентификация устройств, эффективная маршрутизация, безопасность передаваемых данных, «живучесть» сети, продление времени автономной работы конечных устройств. [2]

Актуальность работы определяется актуальностью использования беспроводных технологий. Одним из главных направлений внедрения беспроводной связи являются беспроводные сети датчиков, применяемые в промышленных системах управления и контроля SCADA, а также в быту в виде систем автоматизации типа «Умный дом». Рынок подобных систем ежегодно растет, а это означает высокую актуальность исследования проблемы маршрутизации для улучшения взаимодействия подобных систем.

Цели и задачи

Объектом исследования научной работы являются беспроводные сети малой дальности, в том числе беспроводные сети датчиков.

Предметом исследования являются алгоритмы маршрутизации в сетях стандарта 802.11.4.

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

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

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

Научная новизна и практическая новизна

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

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

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

Основные результаты докладывались и обосновывались на международных научно-технических конференциях студентов, аспирантов и молодых ученых "Информатика и компьютерные технологии – 2009" (секция "Проектирование ЭВМ и цифровых устройств, FPGA-технологии") и "Информационные управляющие системы и компьютерный мониторинг - 2010" (секция "Компьютерная инженерия").

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

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

Общая информация о технологии ZigBee

Беспроводные сети малой дальности созданные для взаимодействия микроконтроллерных устройств получили название WPAN (Wireless Personal Area Network), стандарт которых разработан рабочей группой IEEE 802.15. Этот стандарт включает в себя спецификацию беспроводной связи для портативных устройств Bluetooth (стандарт IEEE 802.15.1) и набор протоколов высокого сетевого уровня использующий маломощные радиопередатчики ZigBee (стандарт IEEE 802.15.4). Стандарты ZigBee и Bluetooth работают на нелицензируемом диапазоне частот 2,4 ГГц, однако имеют существенные отличия характеристик, которые представлены в таблице. [3]

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

Сети ZigBee являются самообразующимися и самовосстанавливающимися. Технология Zigbee может быть использована не только для реализации простых соединений типа "точка-точка" и "звезда", но также и для образования сложных сетей с топологиями "дерево" и "ячеистая сеть". [4]

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

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

За последние годы разработано достаточно большое количество алгоритмов маршрутизации, из которых наибольшую известность приобрели DSR (Dynamic source routing) и AODV (Ad-hoc on-demand Distance Vector routing). Именно AODV, как основной протокол маршрутизации, был реализован в устройствах Zigbee/Zigbee PRO. Особенностью протокола AODV является неявное предположение, что любой узел сети может участвовать в процессе маршрутизации. Однако сети Zigbee являются гетерогенными сетями, так как для устройств предусмотрены различные роли и функции: координатор, роутер, спящее устройство и мобильное устройство.

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

Маршрутизация в сетях ZigBee

В ZigBee применяются следующие способы маршрутизации пакетов:

• широковещание (broadcasting)
• явная маршрутизация (source routing)
• ячеистая сеть (mesh routing)
• маршрутизация по дереву (tree routing)

Каждый из этих методов имеет свои преимущества и недостатки, указанные в таблице 2.

Широковещание

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

Когда узел инициирует широковещание, сообщение ретранслируется всеми соседними маршрутизаторами до определенного предела, как показано на рисунке 1. Область охвата широковещания расширяется подобно кругам на воде. Каждый узел, который получает широковещательное сообщение, добавляет запись в специальную таблицу Broadcast Transaction Table (BTT) и уменьшает значение поля радиуса. Если поле радиуса достигает единицы, дальнейшая ретрансляция пакета не производится. Таблица BTT также предотвращает повторное получение ретранслированного сообщения. Для каждой записи в таблице BTT указывается значение таймаута, что в совокупности с ограниченным размером таблицы вводит ограничение на количество широковещательных сообщений в единицу времени. Если таблица заполнена, широковещательное сообщение не будет принято.

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

Явная маршрутизация

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

Явная маршрутизация имеет высокие издержки для беспроводной передачи. Размер пакета физического уровня стандарта 802.15.4 ограничен 127 байтами. С учетом накладных расходов на протокол ZigBee полезная нагрузка составляет около 100 байт. В случае явной маршрутизации с большой длиной маршрута, полезная нагрузка может быть снижена вплоть до 60 байт. Тем не менее, явная маршрутизация присутствует в ZigBee, но длина маршрута ограничена пятью узлами, чтобы минимизировать накладные расходы.

Ячеистая сеть

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

Алгоритм маршрутизации основан на публично доступном алгоритме динамической маршрутизации Advanced Ad-hoc On-Demand Distance Vectoring (AODV). Данный алгоритм не предъявляет жестких требований к оперативной памяти устройства (устройства ZigBee обычно имеют не более 4кб оперативной памяти). В алгоритме AODV информация о маршруте распределена – каждый узел сети содержит таблицу маршрутизации, в которой хранятся записи о соседних узлах по нужным маршрутам. Таблица маршрутизации может содержать несколько десятков значений. Маршруты обычно однонаправленные и существуют, пока могут использоваться. О сбое маршрута сообщается узлу-отправителю, указывая ему найти новый маршрут. Следует отметить, что в данном алгоритме сеть представляет собой взвешенный граф. В качестве весов ребер графа выступает качество сигнала между узлами, а в теле пакета хранится сумма весов пройденных ребер.

Изначально ячеистая сеть не содержит никакой информации о маршрутах. Определение маршрута начинается с широковещательного сообщения от узла-отправителя. К примеру, на рисунке 2, узел 1 отправляет пакет узлу 10. Узел 10 не является соседом узла 1, и маршрут к нему неизвестен, поэтому начинается определение маршрута. Сообщение ретранслируется по всем направлениям и на каждом узле в тело пакета добавляется вес пройденного ребра графа. Необходимо заметить, что длинный маршрут с более качественной связью предпочтительнее, так как на повторную передачу пропавшего пакета уйдет больше времени, чем на прохождение лишнего узла в маршруте. [6]

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

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

Маршрутизация по дереву

Данный вид маршрутизации используется совместно со специальным методом адресации узлов сети. Следует отметить, что узлы сети ZigBee имеют несколько адресов – адрес MAC, присваиваемый изготовителем устройства (64 бита), а также короткий адрес сети (16 бит). Использование короткого адреса позволяет сократить служебный заголовок пакета, так как в пакете нужно передать адрес получателя и адрес отправителя.

В случае использования адресации Cskip (child skip) координатор сети имеет адрес 0 по умолчанию. Каждый новый узел, подсоединившийся к сети, получит адрес от родительского узла, который будет зависеть от того, является ли новый узел роутером либо конечным устройством. Cskip использует три параметра, чтобы определить адресацию – maxDepth (максимальная глубина дерева), maxChildren (максимальное количество детей у узла) и maxRouters (максимальное количество роутеров).

Образуется симметричное дерево, корнем (нулевым уровнем) которого является координатор с адресом 0. Все роутеры подключенные к координатору составляют первый уровень дерева, а роутеры, подключенные к ним – второй, и т.д. Первый роутер подключенный к координатору получает номер 0x0001, а второй роутер – номер достаточно большой, чтобы в дереве, образованном первым роутером все возможные дети могли быть пронумерованы. Таким образом, создается запас по номерам. Пример нумерации с заданными параметрами сети показан на рисунке 3.

Из недостатков организации подобной топологии и способа маршрутизации следует отметить ненадежность сети. При разрушении связи, ветка дерева станет изолированной и целостность сети нарушитcя. [7]

Аппаратная реализация элемента сети

В качестве аппаратной реализации элемента сети, рассмотрим связку микроконтроллера AVR ATmega32 фирмы Atmel и трансивера СС2500 фирмы Chipcon, структурная схема которой изображена на рисунке 4. Данные интегральные схемы достаточно распространены и имеют низкую стоимость, что позволяет использовать их в недорогих встраиваемых системах. [8]

Контроллеры AVR построены по скалярной RISC архитектуре, что обеспечивает производительность примерно 20MIPS на частоте 20MHz. Данной вычислительной мощности должно быть достаточно для организации координаторов и маршрутизаторов. Развитая периферия Atmel AVR (ШИМ, UART, АЦП) будет использована для подключения элементов управления и датчиков на конечных устройствах, а наличие функций энергосбережения позволит использовать контроллер в энергонезависимых модулях. Таким образом, использование внешнего контроллера позволяет реализовать все элементы гетерогенной сети ZigBee используя одну и ту же аппаратную часть, что сокращает время разработки и удешевляет конечное устройство. [10]

Микросхема Chipcon СС2500 разработана для маломощных беспроводных устройств в полосе частот на 2,4 ГГц и отличается дешевизной и технологичностью. Этот трансивер требует минимум внешних компонент, что существенно облегчает разработку. Тактируется чип кварцевым резонатором Q2 с частотой в диапазоне 26-27 MHz. Точность кварцевого резонатора имеет существенное влияние на частоту приемопередачи. Необходимо использовать прецизионные кварцевые резонаторы либо изменять частоту резонатора при помощи встроенных механизмов коррекции.

Также нужно учитывать, что СС2500 является весьма чувствительной к качеству питания, поскольку изменение напряжения питание в процессе приема или передачи приводит к уходу частоты передачи. Для стабилизации использованы микросхемы LF33 и KA7805 с конденсаторами емкостью рекомендованной производителем.

Для связи модуля с ПК используется UART контроллера, подключенный к COM-порту через микросхему MAX232. Связь контроллера с ZigBee трансивером СС2500 происходит по последовательному периферийному интерфейсу SPI, реализованному в контроллере программно. Данные между модулями ZigBee передаются пакетами по 64 байта с контролем четности.

Заключение

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

Список литературы

1. Материалы альянса ZigBee / Интернет ресурс. — Режим доступа: www.zigbee.org
2. Patrick Kinney. ZigBee Technology: Wireless Control that Simply Works / Kinney Consulting LLC, Chair of IEEE 802.15.4 Task Group, 2003 / Интернет ресурс. — Режим доступа: http://intranet.daiict.ac.in/~ranjan/sn/papers/Zigbee.pdf
3. F. L. Lewis. Wireless Sensor Networks / Automation and Robotics Research Institute, The University of Texas at Arlington / Интернет ресурс. — Режим доступа: http://arri.uta.edu/acs/networks/WirelessSensorNetChap04.pdf
4. Kemal Akkaya and Mohamed Younis. A Survey on Routing Protocols for Wireless Sensor Networks / Department of Computer Science and Electrical Engineering, University of Maryland, Baltimore County / Интернет ресурс. — Режим доступа: http://www.cs.umbc.edu/~kemal1/mypapers/Akkaya_Younis_JoAdHocRevised.pdf
5. Curt Schurgers,Mani B. Srivastava. Energy Efficient Routing in Wireless Sensor Networks / Networked & Embedded Systems Lab (NESL), University of California at Los Angeles / Интернет ресурс. — Режим доступа: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.11.4476
6. Ian D. Chakeres, Elizabeth M. Belding-Royer. AODV Routing Protocol Implementation Design / Dept. of Electrical & Computer Engineering, University of California, Santa Barbara / Интернет ресурс. — Режим доступа: http://moment.cs.ucsb.edu/pub/wwan_chakeres_i.pdf
7. Drew Gislason. ZigBee Wireless Networking. — Newnes, 2008
8. Shahin Farahani. ZigBee Wireless Networks and Transceivers. — Newnes, 2008
9. Панфилов Д., Соколов М. Введение в беспроводную технологию ZigBee стандарта 802.15.4
   Электронные компоненты. — Киев, 2004. — №12(73). — С.73-79
10. Шатунов М. Штрапенин Г. Интеграция технологии ZigBee в электронные устройства:
    Компоненты и технологии. — Минск, 2005. — №10(130). — С.130-134