СПОСОБ МАРШРУТИЗАЦИИ В БЕСПРОВОДНЫХ СЕТЯХ ZIGBEE
METHOD OF ROUTING IN WIRELESS ZigBee NETWORKS

Изобретение относится к беспроводным сетям связи. В частности, к способу маршрутизации в беспроводных сенсорных сетях ZigBee. Указанные сети представляют альтернативу проводным соединениям в распределенных системах управления и мониторинга.
В рассматриваемых сетях объединенные в сеть сенсоры образуют территориально-распределенную самоорганизующуюся систему сбора, обработки и передачи информации. Синхронизация для данных сетей является сложной и важной задачей, поскольку она требует взаимной пространственно-временной координации между узлами. Решение данной задачи возможно благодаря использованию суперфреймовой структуры в сетях ZigBee [1]. Суперфрейм ограничивается периодически передаваемыми кадрами маячков, которые позволяют узлам синхронизироваться с сетью. Активная часть суперфрейма разделяется на 16 последовательных временных слотов и включает три части: маячок, период конкурентного доступа (САР) и период неконкурентного доступа (CFP). Конец суперфрейма является неактивным периодом, в котором узлы могут входить в режим пониженного потребления энергии. В сети могут происходить коллизии маячков, что, безусловно, может приводить к нарушению синхронизации сети. Указанные коллизии устраняются тремя способами:
- выделение временного окна в начале каждого суперфрейма, зарезервированного для передачи кадра-маячка [2];
- временное планирование, при котором кадры маячков передающих маршрутизаторов (ZigBee Routers, ZRs) отправляются в течение неактивных периодов длительности суперфреймов принимающих ZRs [2];
- временное планирование, при котором выбор времени передачи кадров маячков осуществляется в произвольном периоде времени CFP цикла маячкового сигнала координатора сети (ZigBee Coordinator, ZC) [3].
Однако ни один из перечисленных способов не позволяет, используя суперфреймовую структуру, совместить функции синхронизации и маршрутизации сети. Существующие способы маршрутизации, не использующие суперфреймовую структуру, приводят к значительному увеличению потребления энергии узлами, что достаточно критично для рассматриваемых сетей [1].
Разработано достаточно большое количество алгоритмов маршрутизации для сетей ZigBee, из которых наибольшую известность приобрели DSR (Dynamic source routing) и AODV (Ad hoc On-demand Distance Vector routing) [4].
В протоколе DSR маршрут до требуемого узла находится путем рассылки из каждого узла специального пакета запроса маршрута во все узлы окружения, т.е. используется маршрутизация от источника, не полагаясь на таблицы маршрутизации на каждом промежуточном устройстве. Недостатком протокола DSR является нерациональное увеличение как стоимости пути до узла назначения, так и увеличение энергопотребления узлами.
Особенностью протокола AODV является неявное предположение, что любой узел сети может участвовать в процессе маршрутизации. Однако сети ZigBee являются гетерогенными сетями, так как для устройств предусмотрены различные роли и функции. К недостаткам данного протокола следует отнести значительный объем памяти устройств для хранения таблиц маршрутов, а также значительный сетевой трафик, который необходим для поиска маршрутов в разветвленных сетях [4].
Наиболее близким по технической сущности является способ маршрутизации в проводных сетях, основанный на построении минимального связующего дерева (протокол STP (Spanning Tree Protocol)) [5]. Однако данный способ не может быть применен напрямую в сетях ZigBee, т.к. в них отсутствует возможность блокировки портов, как это происходит в проводных сетях, работающих по протоколу STP.
С целью устранения этого недостатка предлагается связи между ZRs устанавливать в течение определенных временных слотов.
Сущность предлагаемого изобретения заключается в том, что ZC закрепляет за каждым из ZRs определенные временные слоты суперфрейма, в течение которых данный ZR осуществляет прием предназначенной ему информации, а каждый узел, передающий суперфрейм, осуществляет передачу данному ZR только в течение закрепленного за данным ZR слота.
Техническим результатом предлагаемого изобретения является возможность осуществления полноценной маршрутизации при двухадресных пакетах, содержащих адрес начального отправителя (НО) и конечного получателя (КП), по аналогии с тем, как это реализуется в проводных сетях протокола STP.
В рамках данного изобретения рассматривается кластерная древовидная сеть ZigBee, тем не менее, предлагаемый способ может быть использован применительно и к другим топологиям ZigBee («звезда», «mesh»), т.к. он соблюдает общие принципы функционирования рассматриваемых сетей.
Реализация предлагаемого способа предусматривает процесс формирования топологии сети, в результате которого будет построено минимальное связующее дерево (аналогично проводным сетям, работающим на основе протокола STP) [5], в котором корнем выступает ZC, а вершинами дерева являются ZRs. При этом вся сеть разделяется на подсети, называемые кластерами. Каждый кластер содержит ZR, через которые кластеры общаются между собой, и конечные узлы (ZigBee End Device, ZED), связанные только с ZR своего кластера.
i
Каждый ZR независимо от других периодически по сигналу таймера рассылает широковещательные пакеты BPDU (Bridge Protocol Data Units) со своим МАС-адресом, а все ZR, имеющие с ним непосредственную связь (узлы его окружения в «дереве»), принимают указанные BPDU. В результате широковещательной рассылки в каждом из ZRs сформируется таблица МАС-адресов, содержащая МАС-адреса узлов окружения, входящих в «дерево», и соответствующие им номера слотов, которые по специальному алгоритму распределяет ZC. При распределении слотов используется алгоритм, минимизирующий число слотов, т.к. допускается повторное использование слотов, но на разных уровнях (невзаимодействующих) иерархии сети.
Рассмотрим принцип работы предлагаемого способа на примере, представленном на рис. 1, где имеются следующие обозначения:
1 - маячки;
2 - слот суперфрейма, в который помещаются принятые пакеты (с адресами НО и КП) для последующей передачи;
3 - принимаемый суперфрейм;
4
4 - рабочая область ZR;
5
5 - рабочая область ZR;
5
6 - таблица МАС-адресов ZR;
7 - передаваемый суперфрейм;
8
8 - рабочая область ZR;
9
9 - рабочая область ZR.
i
i
i
В приведенном фрагменте показаны рабочие области четырех маршрутизаторов, которые взаимодействуют между собой посредством радиосвязи, в частности ZR (4) взаимодействует с ZR (5), a ZR (5) с ZR (8), ZR (9). За каждым из представленных ZRs предварительно ZC закрепил слоты (из формата суперфрейма). Допустим, что в представленном фрагменте сети номер закрепленного слота соответствует номеру ZR. Каждый ZR настраивается на работу в соответствующих слотах таким образом, что для каждого слота в каждом из ZR отводится буферная память для приемо-передачи информации в течение данного слота.
Согласно рис. 1 ZR (4) получает пакет, в адресной части которого имеются МАС-адреса НО и КП. ZR (4) анализирует полученный пакет (в слоте с номером 4), определяет, что адреса КП отличаются от его собственного, т.е. в данном случае ZR (4) является промежуточным узлом при маршрутизации пакетов в сети ZigBee. ZR (4) анализирует собственную таблицу МАС-адресов и определяет, что для доставки пакета по адресу данного КП нужно отправить пакет в слоте с номером 5. ZR (4), формирующий свой собственный суперфрейм, помещает принятый пакет в ячейку с номером 5 (2) и по истечении времени таймера отправляет сформированный суперфрейм соседним ZRs (в данном случае ZR (5)).
8
9
ZR (5), получив пакет в слоте с номером 5, аналогично ZR (4) производит анализ МАС-адресов КП, а затем обращается к собственной таблице МАС-адресов и, в случае если в ней не было ранее таких МАС-адресов НО, вносит в нее адреса НО и номера слотов, в которых ZR (5) должен будет направить пакет для достижения указанных адресов НО (в данном случае это слот с номером 4). Одновременно с этим ZR(5) находит в своей таблице МАС-адресов (6) строчку, содержащую МАС-адреса КП и номера слотов, в течение которых необходимо отравить предназначенную для них информацию. В данном случае адресу КП соответствует МАС-адрес ZR (8) и слот с номером 8, а адресу КП соответствует МАС-адрес ZR (9) и слот с номером 9. ZR (5), формирующий собственный суперфрейм, помещает информацию для каждого из ZR в соответствующий ему слот и по истечении времени таймера отправляет указанный суперфрейм (7) соседним ZRs (в данном случае ZR(8), ZR(9)).
ZR (8) и ZR (9) принимают указанные пакеты, передаваемые в течение соответствующих им слотов.
Рассмотренные выше процессы происходят независимо в каждом из маршрутизаторов сети ZigBee. Из вышеизложенного следует, что в предлагаемом способе временные слоты суперфреймовой структуры как бы выполняют функции портов (аналогично портам в проводных сетях протоколов STP), через которые осуществляется связь между ZRs в сети ZigBee.
Достоинством предлагаемого способа является то, что в результате закрепления за каждым из узлов определенного временного слота (из формата суперфрейма), в течение которого он может принимать данные, становится возможным осуществить полноценную маршрутизацию при двухадресных пакетах по аналогии с тем, как это происходит в проводных сетях, работающих на основе протокола STP. Каждый ZRs производит активную передачу только в тех слотах, которые закреплены за узлами окружения. Это позволяет существенно уменьшить энергопотребление ZRs, что немаловажно для рассматриваемых сетей.
Литература
1. Rao V.P., Marandin D. Adaptive Channel Access Mechanism for Zigbee (IEEE 802.15.4) // Proceedings of the 6th international conference on Next Generation Teletraffic and Wired/Wireless Advanced Networking, 2006. - pp. 501-516.
2. Koubaa A., Cunha A., Alves M., Tovar E. TDBS: A time division beacon scheduling mechanism for Zigbee cluster-tree wireless sensor networks // Real-Time Systems Journal, 2008. - Vol. 40. - №3. - P. 321-354.
3. Beacon scheduling method in wireless sensor network system: pat. US 20060104251 A1; Filed: 14.11.2005; Publ.: 18.05.2006.
4. Влияние гетерогенности на процесс маршрутизации в сетях ZigBee [Электронный ресурс] - Режим доступа: http://tm.ifmo.ru/tm2009/src/244bs.pdf
5. Алгоритм покрывающего дерева Spanning Tree [Электронный ресурс] - Режим доступа: http://life-prog.ru/1_10569_algoritm-pokrivayushchego-dereva-Spanning-Tree.html