Источник: Інформаційні управляючі системи та комп'ютерний моніторинг (ІУС та КМ-2011)./ Матеріали II всеукраїнської науково-технічної конференції студентів, аспірантів та молодих вчених. — Донецьк, ДонНТУ — 2011, II Том, с. 117-121.

Постановка задачи Беспроводные сенсорные сети (WSN) — перспективная технология, имеет ряд преимуществ перед обычными вычислительными сетями. В частности это полное отсутствие каких бы то ни было кабелей, возможность компактного размещения и интеграции мотов в объекты окружающей среды и надежность всей системы в целом. WSN могут быть использованы для решения широкого спектра задач от контроля окружающей среды до использования в системах обороны и обеспечения безопасности. В целях экономии средств на доработку и исправления уже внедренных беспроводных сенсорных сетей их прорабатываю с использованием эмулятора, для определения проблем, узких мест. Для значительного облегчения анализа будущей системы информацию эмуляции работы сети необходимо визуализировать. Задачей работы является создание программы, которая на базе эмулятора TOSSIM смоделирует беспроводную сенсорную сеть, отобразила граф сети и ее работу в реальном времени с соблюдением норм и критериев. Структурная схема визуализатора изображена на рисунке 1.

Беспроводные сенсорные сети (wireless sensor networks) состоят из миниатюрных вычислительно-коммуникационных устройств — мотов (от англ. motes — пылинки), или сенсоров. Мот представляет собой плату размером обычно не более одного кубического дюйма. На плате размещаются процессор, память — флэш и оперативная, цифроаналоговые и аналого-цифровые преобразователи, радиочастотный приемопередатчик, источник питания используются датчики температуры, давления, влажности, освещенности, вибрации). Набор применяемых датчиков зависит от функций, выполняемых беспроводными сенсорными сетями. Питание мота осуществляется от небольшой батареи. Моты используются только для сбора, первичной обработки и передачи сенсорных данных. Основная функциональная обработка данных, собираемых мотами, осуществляется на узле, или шлюзе, который представляет собой мощный компьютер.

Для получения данные узел оснащается антенной. Но доступными для узла оказываются только моты, находящиеся достаточно близко от него; другими словами, узел не получает информацию непосредственно от каждого мота. Проблема получения сенсорной информации, собираемой мотами, решается следующим образом. Моты могут обмениваться между собой информацией с помощью приемопередатчиков, работающих в радиодиапазоне. Это, во-первых, сенсорная информация, считываемая с датчиков, а во-вторых, информация о состоянии устройств и результатах процесса передачи данных. Информация передается от одних мотов другим по цепочке, и в итоге ближайшие к шлюзу моты сбрасывают ему всю аккумулированную информацию. Если часть мотов выходит из строя, работа сенсорной сети после реконфигурации должна продолжаться. Но в этом случае, естественно, уменьшается число источников информации. Для выполнения функций на каждый мот устанавливается специализированная операционная система. В настоящее время в используется ОС TinyOS, разработанная в Университете Беркли.

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

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

Для разработки и тестирования работы сетей используется эмулятор TOSSIM. Эмулятор позволяет выполнять тот же код, что и реальные сенсорные узлы. TOSSIM использует очень простую, но невероятно мощную модель беспроводной сети. Сеть представляется в виде графа, в котором каждая вершина — беспроводной узел и каждой дуге между узлами поставлено в соответствие некоторое значение — вероятность ошибки. Каждый узел имеет локальную переменную, куда заносится то, что принимается им по радиоканалу.

Структура сети можно представить в виде ненаправленного графа, к тому же расположение мотов таково, что сеть имеет минимально количество пересечений. Его можно визуализировать с помощью алгоритма рисования графов на основе физических аналогий. Главным преимуществом такого метода рисования графа то, что он дает в итоге хорошее отображение графа. В большинстве случаев он строит симметричные изображения графов. Метод заключается в том, что граф рассматривается как система тел с силами взаимодействия между ними. Вершины графа считают телами, а ребра пружинами. В таком случае алгоритм находит конфигурацию тел с локальной минимальной энергией – так называемую конфигурацию равновесия сил, в которой каждое тело занимает такую позицию, что сумма всех сил, приложенных к телу, равна нулю. Идея схематически изображена на рисунке 2.

Рисунок 2

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

Где fu- сила растяжения, действующая на вершину p из-за пружины (p,q), а g(p,q) - это сила отталкивания, существующая между частицами p и q. По закону Гука fu пропорциональна разности расстояний от p до q и длинной пружины с минимальной Энергией; а сила g(p,q) следует обратному квадратному закону.

Пусть d (p,q) обозначает расстояние на плоскости между p и q. Тогда для x-й координаты F(p) можно использовать формулу

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

lu- это естественна (с нулевой энергией) длина пружины между p и q. Если пружина имеет длину l_(u ) (т.е.d(p,q)=l_(u )), то не возникает сил растяжения между p и q.

ku(1) – коэффициент жесткости (упругости) пружины между p и q. Чем больше он, тем сильнее пружина стремится установить расстояние между p и q, равным lu

k(p,q)(2) - коэфициент силы отталкивания между p и q

Данная модель нацелена на удовлетворение двух эстетических требований:

1. Силы пружины между соседними вершинами нацелены на то, чтобы расстояние между ними приблизительно равнялось l_u
2. Электронные силы должны гарантировать, чтобы вершины не приближались близко друг к другу.

Алгоритм работы метода. На первом этапе вершины размещаются на плоскости случайным образом. Второй этап – это последовательность итераций для стабилизации, на каждой из которых вычисляются для всех вершин p силы F(p) и для тех их них, для которых F(p) 0, происходит перемещение вершины в направлении этой силы на расстояние пропорциональное модулю силы. Пропорция сдвига всех вершин и является еще одним параметром алгоритма.

Для визуализации работы алгоритма была разработана программа с использованием открытой библиотеки protovis, которую разрабатывают в Стендфордском университете. В protovis используется JavaScript и SVG, что позволяет ей работать в любом браузере без дополнительных плагинов. Для задания вершин используется структура, каждая запись которой имеет вид {nodeName:"%Node_name", group: %Color} где %Node_name – имя вершины, а %color его цвет. Связи между вершинами задаются тоже структурой: {source: %source, target: %target} где %source номер первого узла, а %target – второго. Остальные параметры задаются программно. Визуализированный граф показан на рисунке 3.

В связи с тем, что структура WSN имеет малое количество пересечений, то метод физических аналогий в рисовании графов будет давать хороший результат. К тому же данный метод позволяет довольно быстро отрисовывать графы и имеет ряд параметров, с помощью которых легко можно влиять на конечный результат

1. Michael Kaufmann, Dorothea Wagner. Drawing Graphs. Methods and Models. Springer-Verlag Berlin Heidelberg, 2001 – 325 c.
2. Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка визуализация, применение. С-П. 2003 – 1104 с.
3. Philip Levis. TOSSIM: Accurate and Scalable Simulation of Entire TinyOS Applications. 2009 – 23 с.
4. Maneesh Varshney. Detailed Models for Sensor Network Simulations and their Impact on Network Performance. 2006