МЕТОД КЛАСТЕРИЗАЦИИ В БЕСПРОВОДНОЙ СЕНСОРНОЙ СЕТИ НА ОСНОВЕ ПРИНЦИПОВ САМООРГАНИЗАЦИИ

Беспроводная сенсорная сеть (БСС) – это распределенная, самоорганизующаяся и устойчивая к отказу сеть большого числа автономных узлов, способных обмениваться сообщениями и ретранслировать их по беспроводному каналу связи.

Существует большое множество различных протоколов маршрутизации БСС. Иерархические протоколы (например, LEACH, PEGASIS, TEEN and APTEEN, SOP) объединяют узлы в кластеры, с определенной иерархией. Они направлены на увеличение энергосбережения сети в сочетании с оптимальной доставкой данных до базовой станции, путем объединения узлов в кластеры (области).

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

Известным коммуникационным протоколом беспроводной сенсорной сети является ZigBee. Одним из вариантов топологий сетей ZigBee является топология «Кластерное дерево». При формировании сети координатор посылает всем соседним устройствам широковещательную команду. Затем узлы запрашивают разрешение на присоединение к кластеру. Если сетевой координатор разрешает, то устанавливается связь с узлом, который начинает периодически посылать команды, для присоединения других устройств.

К недостаткам процедуры формирования кластеров в ZigBee можно отнести следующее:

- формирование сети производит узел-координатор. Координатор принимает решение о принятии узла в кластер и назначает узлы главами кластеров. В результате возрастает время образования сети;

- формируемая структура сети может быть не оптимальной.

Рассмотрим семейство энергосберегающих алгоритмов Low-Energy Adaptive Clustering Hierarchy (LEACH).

По алгоритму LEACH часть узлов сети создают вокруг себя кластеры (при этом становятся их головными узлами), остальные узлы сети присоединяются к ближайшему из кластеров. Узел принимает решение на создание кластера с вероятностью, определяемой из требуемого количества кластеров, количества узлов в сети, от запаса энергии узла. [1]

В алгоритме LEACH-C каждый из узлов передает напрямую на базовую станцию информацию о своем расположении, затем на базовой станции выполняется кластеризация узлов. После чего базовая станция рассылает узлам информацию о принадлежности узлов к кластерам. [1]

Преимуществом алгоритмов LEACH является учет уровня питания узлов при формировании кластеров и как следствие увеличение времени жизни сети.

К недостаткам семейства алгоритмов LEACH можно отнести:

- вероятностный характер распределения кластеров, что не всегда может быть оптимальным;

- использование базовой станции для определения конфигурации сети (LEACH-C, LEACH-F), что увеличивает время образования сети при сборе информации об узлах и конфигурировании.

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

Какие принципы самоорганизации можно выделить?

Общая теория самоорганизации получила название – «Синергетика» (synergeia (греч.) – совместное действие, сотрудничество), которое было предложено в начале 70-х годов немецким физиком Г. Хакеном. [2, с. 6]

"Самоорганизующейся является система, способная без специфического воздействия извне формировать пространственную, временную или функциональную структуру, т.е. самостоятельно изменяющая свои структуру и организацию на основе принципа структурно-функционального единства.
Специфическим называется воздействие, навязывающее системе ее структуру и функционирование" – Г. Хакен "Синергетика" [3].

Таким образом, можно выделить следующие принципы самоорганизации:

1) Отсутствие навязывающего, диктующего внешнего воздействия на систему;

2) Самостоятельный выбор действий из возможных вариантов элементами системы.

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

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

Разработанный алгоритм кластеризации БСС состоит из трех этапов:

1) Образование кластера;

2) Выбор оптимального головного узла кластера;

3) Оптимизация кластеров.

Для исследования работы алгоритма кластеризации на модели БСС была разработана прикладная программа «Метод кластеризации в беспроводной сенсорной сети на основе принципов самоорганизации». [4]

Схема алгоритма программы представлена на рисунке 1.

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

Рисунок 1. Схема алгоритма прикладной программы

В блоках 2, 3 происходит вызов соответственно процедур кластеризации узлов и затем выбора оптимального головного узла кластера.

На месте 4 блока алгоритм заходит в цикл, условием выхода из которого является отсутствие изменений в кластерах.

Блоком 5 обозначено приглашение доступного узла в кластер и переход в состояние ожидания подтверждения – «WaitAsk».

(а) Начальные условия состояния сенсорной сети

(б) Результат кластеризации

Рисунок 2. Пример работы алгоритма программы

На рисунке 2 показан пример результата кластеризации беспроводной сенсорной сети на основе принципов самоорганизации по критериям минимального числа переходов до головного узла кластера и минимального расстояния между узлами.

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

Список использованных источников

1. Наградов Е.А. Проблемы применения существующих алгоритмов маршрутизации в сенсорных сетях реального времени / Методы и средства обработки информации. Труды третьей Всерос. научн. конф. – М.: Издательский отдел факультета вычислительной математики и кибернетики МГУ имени М.В. Ломоносова, 2009. – 481 с.

2. Лоскутов А.Ю., Михайлов А.С. Введение в синергетику: Учеб. Руководство. М.: Наука. Гл. ред. физ.-мат. лит., 1990. – 271 с.

3. Г. Хакен Синергетика. – М.: Мир, 1980. – 406 с.

4. Свид. о рег. прогр. ср-ва № 729 «Метод кластеризации в беспроводной сенсорной сети на основе принципов самоорганизации» / А.А. Муталлапов, Т.З. Аралбаев; заявитель и обладатель Оренбургский государственный университет. – зарег. 26.04.2012. – 696 Кбайт.

Научный руководитель:

Т.З. Аралбаев, д.т.н., зав. каф. ВТФГБОУ ВПО «Оренбургский государственный университет»