СПОСОБ НЕЙРОСЕТЕВОЙ КЛАСТЕРИЗАЦИИ БЕСПРОВОДНОЙ СЕНСОРНОЙ СЕТИ Российский патент 2015 года по МПК H04W40/24 H04W84/18 G06N3/08 

Изобретение относится к области сетей и телекоммуникаций, предпочтительно беспроводных сенсорных сетей (БСС), и может быть использовано в иерархических протоколах БСС.

Из предшествующего уровня техники известен способ кластеризации, лежащий в основе протокола маршрутизации беспроводных сенсорных сетей HEED. Используется итеративный алгоритм образования кластеров, где каждый узел имеет следующие параметры: вероятность стать ГКУ - это функция от остаточной энергии и внутрикластерная коммуникационная стоимость - это функция от близости соседей (плотности кластера) или же используется уровень узла (то есть число соседей). Каждый узел на основании вероятности стать ГКУ принимает решение - посылать сообщения другим узлам о том, что он может стать ГКУ на этой итерации или нет. Основываясь на этих сообщениях, каждый узел выбирает ГКУ с самой низкой стоимостью передачи данных (ГКУ мог бы быть он сам). На каждой итерации узлы увеличивают свою вероятность стать ГКУ.

Недостатком первого способа является большое количество пакетов, которые пересылаются в течение множества итераций, пока не будут избраны окончательные ГКУ для каждого кластера.

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

Недостатком второго способа является большое количество пакетов, которые пересылаются множество итераций, пока не будут избраны окончательные ГКУ для каждого кластера.

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

Также известен третий способ, лежащий в основе протокола маршрутизации беспроводных сенсорных сетей LEACH. Согласно этому способу случайным образом выбирается несколько узлов, которые будут центрами кластеров - главными кластерными узлами (ГКУ). Каждый узел может стать ГКУ с вероятностью 1/р, где р - количество раундов, в которых выбираются ГКУ. Каждый узел, не являющийся ГКУ, выбирает ближайший к нему ГКУ и присоединяется к его кластеру. Иерархия сети получается следующая: подчиненные узлы передают данные ГКУ, далее ГКУ передает данные напрямую на базовую станцию (БС). Этот аналог является прототипом для заявленного изобретения.

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

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

Задача, на решение которой направлено заявленное изобретение, заключается в реализации беспроводной сенсорной сети, построение и поддержание работоспособной структуры которой производится автоматически.

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

Матрица мощностей Р (матрица энергетической видимости) - это квадратная матрица, где каждому узлу ставится в соответствие другие узлы сети. Матрица имеет порядок n, где n - это количество узлов сети. В качестве элементов матрицы используются значения энергетической видимости узлов относительно друг друга в процентах (фиг. 1).

В качестве примера приведем матрицу мощностей, состоящую из 7 узлов фиг. 2.

Условно примем за бесконечность 100% видимость узла, тогда получим матрицу, представленную на фиг. 3.

Каждая строка матрицы Р является входным вектором для нейронной сети и несет информацию о каждом из узлов сети - о его видимости относительно других узлов сети. С помощью данной матрицы можно описать следующий граф (фиг. 4).

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

Понижающий коэффициент запаса γ_S необходим для получения данных об энергетической видимости узлов с избыточностью. Поскольку узлы сети, как правило, питаются от автономных источников энергии, то со временем мощность сигнала каждого узла уменьшается вследствие истощения этого источника. Следовательно, для продления времени актуальности результатов кластеризации, целесообразно производить расчет с некоторым запасом. Для этого уменьшаем значения уровней видимости всех узлов, умножив матрицу мощностей Р на коэффициент γ_S. В качестве примера можно сделать запас 10%, тогда значение коэффициента будет равно 0,9. Получим: Р·0.9 (фиг. 5).

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

Важно заметить, что использование матрицы инцидентности позволяет нормализовать входные данные и жестко задать диапазон допустимых нормализованных значений, где I∈[0∨1].

Алгоритм обучения нейронной сети Кохонена

Обучение сети Кохонена необходимо производить со следующими параметрами:

- Количество входных нейронов N будет равняться количеству узлов БСС;

- Количество нейронов слоя Кохонена (выходных нейронов) будет равняться согласно конструктивному методу обучения только лишь одному нейрону;

- Начальное значение скорости обучения α₀ и постоянную времени обучения τ зададим согласно [Баталов А.С. Методы повышения эффективности обучения нейронной сети Кохонена. Вестник Пермского университета. Сер.: Математика. Механика] равными 0.7 и 1000 соответственно;

- Радиус чувствительности R зададим в пределах от 0.22 до 0.36;

- Точность обучения ε=0,01;

- Обучающей выборкой являются все узлы БСС.

Рассмотрим алгоритм обучения сети Кохонена по конструктивному методу с настроенными коэффициентами функций для кластеризации узлов БСС согласно [Кохонен Т. Самоорганизующиеся карты. Пер. 3-го англ. изд. - М.: БИНОМ. Лаборатория знаний. 2008. - 655 с.: с ид. ISBN 978-5-94774-352-4], [Горбаченко В.И. Сети и карты Кохонена: [Электронный ресурс] // Научно-исследовательский центр самоорганизации и развития систем. М., 2010-2014. URL: http://gorbachenko.self-organization.ru/index.html (Дата обращения: 01.02.2014] и [Баталов А.С. Методы повышения эффективности обучения нейронной сети Кохонена. Вестник Пермского университета. Сер.: Математика. Механика].

Последовательно подаем на вход сети обучающие вектора E₁…E_N:

1) Если это первый входной вектор E₁ и первый внешний цикл обучения, то единственный существующий изначально в сети нейрон принимает значения этого вектора. Иначе, переходим к шагу 2.

2) Определяем нейрон-победитель для рассматриваемого на текущей операции обучающего вектора. Нейроном-победителем будет тот нейрон, вектор весов которого в наименьшей степени отличается от вектора весов обучающего вектора. То есть расстояние между их векторами весов должно быть минимально. В качестве метрики используем Евклидово расстояние, которое вычисляем по формуле (1):

3) Если d(x,w_i) не удовлетворяет условию , то в сеть добавляется новый нейрон, который принимает значение этого входного вектора и переходим к шагу 1, где подаем на вход нейросети следующий входной вектор. В противном случае происходит обучение нейрона согласно следующему шагу.

4) Подстраиваем веса (компоненты вектора) нейрона-победителя и близлежащих нейронов по формуле (2):

где $$w_i^t$$ - вектор весов i-го нейрона, t - номер итерации обучения, х - входной вектор, α(t) - коэффициент скорости обучения.

На данном этапе происходит подстройка весов всех нейронов Кохонена. Величина изменения весов $$w_i^k$$ каждого нейрона зависит от произведения разности каждого веса $$w_i^k$$ и компонента входного вектора х на коэффициент скорости обучения α(t)

5) Если текущий вектор - последний вектор обучения E_N, то проверяем, изменились ли веса каждого нейрона больше, чем на ε по отношению к предыдущему состоянию, после предыдущего прохождения последнего обучающего вектора. Если нет, то завершаем обучение сети. Если да, то переходим на первый шаг и начинаем обучение снова с первого обучающего вектора.

После обучения, назначаем в качестве ГКУ центроиды (центральные узлы) каждого кластера.

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

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

На фиг. 1 - матрица энергетической видимости для БСС из n узлов.

На фиг. 2 - матрица энергетической видимости для БСС из 7 узлов.

На фиг. 3 - практическое представление матрицы энергетических уровней для БСС из 7 узлов

На фиг. 4 - граф мощностей для БСС из 7 узлов.

На фиг. 5 - произведение матрицы мощностей БСС из 7 узлов на понижающий коэффициент.

На фиг. 6 - матрица инцидентности для БСС из 7 узлов.

Изобретение относится к области сетей и телекоммуникаций и может быть использовано в иерархических протоколах беспроводной сенсорной сети (БСС). Техническим результатом является автоматическое построение и поддержание работоспособности структуры сети. Способ включает иерархическое деление узлов на головные кластерные узлы (ГКУ) и на «ведомые» и использование данных о радиовидимости узлов. Структура всей БСС описывается с помощью графа энергетической видимости узлов БСС, на основании которого строится матрица энергетической видимости, которую умножают на понижающий коэффициент, задаваемый в процентах, преобразуют к матрице инцидентности. Кластеризацию производят с помощью нейронной сети Кохонена, обучающейся по конструктивному методу обучения, где в качестве входных обучающих данных выступает полученная ранее матрица инцидентности, количество нейронов сети Кохонена задается автоматически на основании отличия и подобия входных данных об узлах БСС, радиус чувствительности нейронов слоя Кохонена задается в пределах от 0,22 до 0,36. Матрица энергетической видимости узлов БСС используется для маршрутизации и позволяет производить межкластерную связь между ГКУ и внутрикластерную связь в рамках ведомых каждому ГКУ узлов. 6 ил.

Способ нейросетевой кластеризации беспроводной сенсорной сети (БСС), включающий иерархическое деление узлов на «центры кластеров» (головные кластерные узлы, ГКУ) и на «ведомые» и использование данных о радиовидимости узлов, отличающийся тем, что структура всей БСС описывается с помощью графа энергетической видимости узлов БСС, на основании которого строится матрица энергетической видимости узлов БСС, затем матрицу умножают на понижающий коэффициент, задаваемый в процентах, после чего полученную матрицу преобразуют к матрице инцидентности, кластеризацию производят с помощью нейронной сети Кохонена, обучающейся по конструктивному методу обучения, где в качестве входных обучающих данных выступает полученная ранее матрица инцидентности, количество нейронов сети Кохонена задается автоматически на основании отличия и подобия входных данных об узлах БСС, причем радиус чувствительности нейронов слоя Кохонена задается в пределах от 0,22 до 0,36, при этом автоматическая генерация нейронов не приводит к бесконечному росту их числа (числа классов), матрица энергетической видимости узлов БСС используется для маршрутизации и позволяет производить межкластерную связь между ГКУ и внутрикластерную связь в рамках ведомых каждому ГКУ узлов, введения в беспроводную сеть дополнительных функциональных модулей не требуется.