Моделирование работы беспроводной сети на основе протокола ZIGBEE

где обозначает минимальную длительность суперфрейма, соответствующую . Эта величина фиксирована и равна 960 символов [1] (символ равен 4 битам), что соответствует 15,36 мс, предполагая 250 кбит/с в частотном диапазоне 2,4 ГГц.

      В течении периода конкурентного доступа (CAP) узлы соперничают за получение доступа к физической среде, используя механизм слотного CSMA-CA (slotted carrier sense multiple access with collision avoidance). Этот механизм довольно сложен и его всестороннее исследование средствами имитационного моделирования в среде ns [6] представлены в [4]. В протоколе IEEE 802.15.4 также предусмотрен период неконкурентного доступа к среде (CFP), в течение которого узлам могут выделяться слоты гарантированного доступа (GTS).

      Зная  характерное энергопотребление  устройств [3], временные и другие параметры (см. Табл. 2.1) в различных режимах можно теоретически рассчитать время жизни при питании от различных батарей.

  Табл. 2.1. Известные параметры

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

  Табл. 2.2. Рассчитанные параметры для различных значений Beacon Order (

      В ИТМиВТ был проведён ряд экспериментов  связанных с измерением энергопотребления ZigBee-устройств CC2420. Полученные в результате этих экспериментов данные для силы тока хорошо согласуются с данными указанными в [3].

3. Оптимизационные алгоритмы управления работой беспроводной сенсорной сети на основе протокола ZigBee

1. Задача  минимизации энергопотребления

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

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

      В этих условиях возникает возможность  разделения устройств по ролям, энергопотребление  в которых сильно различается. Эти  роли таковы: конечное устройство, маршрутизатор  и координатор. Различия энергопотребления  устройств в этих ролях в первую очередь связано с постоянством количества устройств сети. Идея заключается в следующем. Допустим, что после включения сети координатор узнаёт о присутствии в сети всех устройств. Тогда часть устройств оказывается маршрутизаторами (router), а часть — конечными устройствами (end device) дерева топологии сети, т.е. устройствами, не имеющими дочерних узлов. На аппаратном уровне это приводит к отсутствию необходимости в передаче конечными устройствами маяка и следующего за ним суперфрейма, что снижает энергопотребление конечных устройств уже почти вдвое.

      Дальнейшая  оптимизация связана с возможностью конечного устройства засыпать сразу  же после родительского маяка, не слушая суперфрейм, при условии, что устройству не адресовано данных (устройства могут определять это по содержанию кадра маяка). Эта оптимизация позволяет снизить энергопотребление ещё в 3-4 раза. Результаты более точного расчёта приведены ниже (см. Рис. 3.1).

Рис. 3.1. Зависимость отношение средних сил токов от Beacon Order.

Здесь — сила тока с учётом первой оптимизации; — с учётом обоих; — без учёта оптимизаций (соответствует данным Табл. 2.2 и потреблению всех маршрутизаторов)

      Из  рисунка видно, что чем более быстрой является сеть, тем более эффективны оптимизации. Но при из формул (2.1) и (2.2) следует, что и   становится невозможно построить сеть с маршрутизаторами из-за проблемы скрытой станции. Поэтому имеет смысл рассматривать только сети с

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

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

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

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

где — средняя за время сила тока в узле, находящимся в роли маршрутизатора; 
— средняя за время сила тока в узле, находящимся в роли конечного устройства. Время жизни сети определяется устройством с самым коротким временем жизни

где — заряд батареи устройства . Далее для простоты предполагаем, что в начальный момент времени все устройства имеют одинаковый заряд батареи . Тогда условие (3.2) переходит в

Если наборы независимы, то , поэтому и остаётся лишь условие

      Это и есть искомое условие. Итак, для  максимизации времени жизни сети необходимо найти как можно больше независимых наборов маршрутизаторов.

2. Алгоритм  распределение ролей

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

1. Пусть вначале вершина (координатор) покрашена в красный цвет, а все остальные вершины не покрашены.
2. Покрасим в чёрный цвет всех неокрашенных соседей красных вершин.
3. Если при выполнении пункта 2 не было покрашено ни одной вершины, то набор не удалось построить — прекращаем работу алгоритма. Иначе, продолжаем.
4. Рассмотрим множество чёрных вершин. Выберем из него вершину, имеющую наибольшее число неокрашенных соседей, и перекрасим её в красный цвет.
5. Если все вершины окрашены — переходим к пункту 6. Иначе, повторяем действия, начиная с пункта 2.
6. Вершины, окрашенные в красный цвет (не считая ), являются одним из искомых наборов. Красим их в зелёный цвет, – в красный, остальные делаем неокрашенными. Повторяем действия, начиная с пункта 2.

      В результате работы алгоритма мы получаем число  и наборы . Для того чтобы получить дерево соответствующее набору пользуемся следующими правилами.