Способ маршрутизации в беспроводных сетях zigbee
Владельцы патента RU 2640349:
Федеральное государственное бюджетное образовательное учреждение высшего образования "Поволжский государственный университет телекоммуникаций и информатики" (ФГБОУ ВО ПГУТИ) (RU)
Изобретение относится к области беспроводной связи и может быть использовано в беспроводных сенсорных сетях ZigBee.Технический результат состоит в повышении точности маршрутизации при двухадресных пакетах, содержащих адрес начального отправителя и конечного получателя. Для этого функции портов, соединяющих маршрутизаторы в проводных сетях, в сетях ZigBee выполняют временные слоты, в течение которых осуществляется связь между маршрутизаторами сети. Временные слоты суперфреймовой структуры ZigBee как бы выполняют функции портов, через которые осуществляется связь между маршрутизаторами в сети ZigBee. Перед передачей маячка в выходном буфере каждого маршрутизатора формируется суперфрейм в виде набора ячеек памяти. В каждой из ячеек, за которыми закреплены соответствующие маршрутизаторам слоты, размещаются пакеты, получаемые от маршрутизаторов для последующей передачи. Каждый маршрутизатор независимо от других периодически по сигналу таймера рассылает широковещательно суперфреймы, ограниченные маячками. Все соседние маршрутизаторы, принявшие начальный маячок, запускают механизмы синхронизации, генерирующие последовательность временных слотов, и производят последовательный (послотовый) прием всех пакетов, содержащихся в соответствующей им ячейке. В течение тех слотов, в которых отсутствует информация, передача не происходит, а осуществляются только механизмы синхронизации, во время которых затрачивается малое количество энергии по сравнению с режимом передачи. 1 ил.
Изобретение относится к беспроводным сетям связи. В частности, к способу маршрутизации в беспроводных сенсорных сетях 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 своего кластера.
Каждый ZR независимо от других периодически по сигналу таймера рассылает широковещательные пакеты BPDU (Bridge Protocol Data Units) со своим МАС-адресом, а все ZRi, имеющие с ним непосредственную связь (узлы его окружения в «дереве»), принимают указанные BPDU. В результате широковещательной рассылки в каждом из ZRs сформируется таблица МАС-адресов, содержащая МАС-адреса узлов окружения, входящих в «дерево», и соответствующие им номера слотов, которые по специальному алгоритму распределяет ZC. При распределении слотов используется алгоритм, минимизирующий число слотов, т.к. допускается повторное использование слотов, но на разных уровнях (невзаимодействующих) иерархии сети.
Рассмотрим принцип работы предлагаемого способа на примере, представленном на рис. 1, где имеются следующие обозначения:
1 - маячки;
2 - слот суперфрейма, в который помещаются принятые пакеты (с адресами НО и КП) для последующей передачи;
3 - принимаемый суперфрейм;
4 - рабочая область ZR4;
5 - рабочая область ZR5;
6 - таблица МАС-адресов ZR5;
7 - передаваемый суперфрейм;
8 - рабочая область ZR8;
9 - рабочая область ZR9.
В приведенном фрагменте показаны рабочие области четырех маршрутизаторов, которые взаимодействуют между собой посредством радиосвязи, в частности ZR (4) взаимодействует с ZR (5), a ZR (5) с ZR (8), ZR (9). За каждым из представленных ZRs предварительно ZC закрепил слоты (из формата суперфрейма). Допустим, что в представленном фрагменте сети номер закрепленного слота соответствует номеру ZRi. Каждый ZRi настраивается на работу в соответствующих слотах таким образом, что для каждого слота в каждом из ZRi отводится буферная память для приемо-передачи информации в течение данного слота.
Согласно рис. 1 ZR (4) получает пакет, в адресной части которого имеются МАС-адреса НО и КП. ZR (4) анализирует полученный пакет (в слоте с номером 4), определяет, что адреса КП отличаются от его собственного, т.е. в данном случае ZR (4) является промежуточным узлом при маршрутизации пакетов в сети ZigBee. ZR (4) анализирует собственную таблицу МАС-адресов и определяет, что для доставки пакета по адресу данного КП нужно отправить пакет в слоте с номером 5. ZR (4), формирующий свой собственный суперфрейм, помещает принятый пакет в ячейку с номером 5 (2) и по истечении времени таймера отправляет сформированный суперфрейм соседним ZRs (в данном случае ZR (5)).
ZR (5), получив пакет в слоте с номером 5, аналогично ZR (4) производит анализ МАС-адресов КП, а затем обращается к собственной таблице МАС-адресов и, в случае если в ней не было ранее таких МАС-адресов НО, вносит в нее адреса НО и номера слотов, в которых ZR (5) должен будет направить пакет для достижения указанных адресов НО (в данном случае это слот с номером 4). Одновременно с этим ZR(5) находит в своей таблице МАС-адресов (6) строчку, содержащую МАС-адреса КП и номера слотов, в течение которых необходимо отравить предназначенную для них информацию. В данном случае адресу КП8 соответствует МАС-адрес ZR (8) и слот с номером 8, а адресу КП9 соответствует МАС-адрес 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
Способ слотовой маршрутизации в беспроводных сетях ZigBee, имеющих суперфреймовую временную синхронизацию, отличающийся тем, что за каждым маршрутизатором закрепляются временные слоты суперфрейма, в течение которых он может принимать предназначенные ему пакеты, а каждый передающий маршрутизатор рассылает пакеты, предназначенные принимающему маршрутизатору, только в течение слотов, закрепленных за указанным принимающим маршрутизатором.
