Адаптивный энергосберегающий алгоритм классификации состояний в беспроводных сенсорных сетях

Во введении содержится обоснование актуальности и научной новизны выбранной темы, а также практической значимости и достоверности результатов работы с точки зрения решения практических задач. Также во введении указана формулировка научной проблемы, решаемой в диссертации, цель работы и решаемые задачи. В заключении представлены научные положения, выносимые на защиту.
В первой главе проанализированы принципы реализации БСС. БСС является сложной технической системой, где элементы системы – сенсоры и модуль управления, связи между элементами – беспроводное взаимодействие, входные данные – параметры контролируемого объекта, выходные данные – результат обработки информации с сенсоров, в том числе сформированные управляющие команды (см. Рисунок 1). БСС предназначены для автоматизированного сбора информации о контролируемом объекте с последующей обработкой информации и выработкой управляющего воздействия. При исследованиях в области БСС приходится решать такие задачи системного анализа, как анализ проблемы и выявление ее причин, выработка вариантов ее разрешения, декомпозиция и формализация БСС, использование имитационных моделей БСС для исследования предлагаемых решений.
Основная задача эффективного функционирования БСС – это снижение энергопотребления узла БСС. Анализ одного рабочего цикла узла сети показал, что около 70% энергии источника питания расходуется на коммуникацию (прием и передача данных по сети). Обобщенный график энергопотребления узла БСС представлен на Рисунке 2.
Рисунок 1. Структурная схема БСС
Рисунок 2. Осциллограмма работы сенсорного узла в зависимости от фазы обработки информации
Представлен анализ существующих методов и средств, обеспечивающих увеличение времени автономной работы узла сети за счет использования эффективных алгоритмов передачи данных. Для этого предлагается использовать метод Geographical Adaptive Fidelity, энергетическую
балансировку при построении маршрута передачи данных, дискретный режим работы узла сети, расписание для передачи данных, агрегацию данных и другое. Проведен анализ существующих применений БСС, на основе которого была разработана классификация функций БСС: сбор данных, мониторинг, контроль, слежение, формирование управляющих команд. Определено, что для функций мониторинга, контроля, слежения и формирования управляющих команд
требуется на основе данных с узлов БСС классифицировать состояние сети. При классификации состояний в БСС важным этапом является сбор текущих показаний сети. Данные представлены в структурированном виде с указанием временных меток, идентификатора сенсора и самих показаний. Главный модуль получает данные со всех сенсоров и принимает решение по заранее определенному алгоритму. Данные алгоритмы оперируют с информацией, поступившей в текущий момент времени, и представляют собой поведенческое описание системы. Подобные алгоритмы принятия решения
имеют низкую гибкость и адаптацию ко внешним факторам.
При обеспечении взаимодействия элементов беспроводной сенсорной сети
возникает вопрос о том, с какой частотой должны передаваться показания по сети к главному модулю. С увеличением числа сеансов связи растут энергозатраты, что ведет к сокращению времени автономной работы узла сети, с уменьшением – повышается вероятность пропуска важных событий, что может привести к неверному принятию решения (Рисунке 3).
Повышение достоверности принятых решений
ПЭ
Принятие ошибочного решения
НЭ
У величение энергозатрат
ПЭ
У величение автономного срока работы узла
Увеличение частоты передачи данных
Достоверность принятого решения
Энергозатраты, срок автономной работы узла
Частота передачи данных
НЭ
Уменьшение частоты передачи данных
ПЭ – положительный эффект, положительное влияние; НЭ – нежелательный эффект, нежелательное влияние.
Рисунок 3. Предметное противоречие частоты передачи данных
Разрешение противоречия достигается за счет использования «принципа вынесения», предложенного Г. С. Альтшуллером. В данном случае объектом вынесения является частота передачи данных, которая обязывает периодически передавать данные по сети. Если отказаться от периодической передачи данных, то требуется обеспечить альтернативную методику взаимодействия. Для этого предлагается использовать «принцип динамичности», то есть, когда
характеристика объекта или внешней среды должна меняться так, чтобы быть оптимальной на каждом этапе работы системы. В данном случае принцип динамичности можно характеризовать как передачу данных только тогда, когда в этом есть необходимость.
Таким образом, для решения технического противоречия предлагается разработать алгоритм обработки информации в беспроводных сенсорных сетях, который с одной стороны сократит количество сеансов связи, тем самым повысит энергоэффективность узла БСС, а с другой стороны будет гарантировать, чтобы главный модуль всегда обладал необходимой информацией о параметрах окружающей среды.
Для динамического определения частоты передачи данных предлагается использовать информацию из базы знаний, чтобы сенсоры самостоятельно принимали решение, когда необходимо передавать данные. Для реализации данного алгоритма эффективно использовать методы машинного обучения. Они ориентированы на построение математической модели поведения внешней среды, где параметры данной системы определяются путем обучения на выборке данных с сенсоров и результатов принятия решения главным модулем или оператором.
Во второй главе для формализации задачи классификации состояний в БСС представлена математическая модель, описывающая в общем виде набор параметров, с которым в дальнейшем следует оперировать предлагаемому алгоритму. Преимуществом данной модели является то, что происходит абстрагирование от технической реализации сенсорной сети, тем самым упрощается применение методов управления и обработки информации из смежных дисциплин.
Для математического описания задачи классификации введем несколько параметров входных данных:
N – количество сенсоров в БСС,
K – количество уникальных параметров внешней среды, контролируемых датчиками (температура, влажность, и т.п.), – множество показаний со всех сенсоров сети.
Каждый сенсор в определенный момент времени ∈ представлен вектором ‘ ”’⃗ ∈ , где n = 1..N. Данный вектор принадлежит K-мерному
!
пространству значений, при этом элемент x!” может быть выражен бинарным
(срабатывание триггера) или количественным (значения температуры, влажности) признаком. Таким образом, значение x!” характеризует показание датчика в составе n-го сенсора, который контролирует k-й параметр окружающей среды.
Таким образом, показания сенсорной сети описываются матрицей объектов- признаков:
## $# … %#
=+ #$ $$ … %$/. (1) ⋮⋮⋱⋮
#& $& … %&

Также введем параметры для задачи классификации:
S – количество состояний, которое может быть детектировано с
помощью БСС (например, повышенная влажность, возгорание, утечка газа),
Y – множество состояний в беспроводной сенсорной сети, которое
можно представить в виде:
#
= 2 $4. (2) ⋮
‘
В определенный момент времени БСС находится в состоянии ∈Y,
которое может быть выражено бинарным или номинальным признаком.
Задача классификации состояний в беспроводной сенсорной сети
заключается в установлении зависимости (отображения):
∗: → . (3)
В ходе анализа методов классификации в области машинного обучения было принято решение, что наиболее подходящей моделью при классификации состояний в БСС является решающее дерево. Во-первых, данная модель полностью решает задачу многоклассовой классификации. Во-вторых, модель легко интерпретировать, и процесс принятия решения похож на алгоритм работы оператора. В-третьих, модель позволяет классифицировать при наличии пропусков в данных. В-четвертых, модель решающего дерева позволяет выделить компоненты, дающие возможность выстроить дополнительную модель для локального принятия решения о необходимости передачи данных на базовую станцию.
Для того чтобы определить к какому классу относится входной объект, необходимо ответить на вопросы, стоящие в узлах решающего дерева, начиная с его корня. Вопросы имеют вид «значение параметра !” больше значения …». Если ответ положительный, то осуществляется переход к правому узлу, если отрицательный – к левому, затем снова необходимо ответить на вопрос следующего узла. Так, в конце концов, достигается один из конечных узлов, где стоит указание, к какому классу следует отнести рассматриваемый объект. За счет прозрачной интерпретации работы алгоритма данный метод имеет высокую наглядность.
Расчет энергоэффективности алгоритма классификации состояний в БСС. Рассмотрим расчет энергопотребления по параметрам решающего дерева. Обозначим основные параметры модели обученного решающего дерева: – количество узлов сети (в решающем дереве – предикаты), – количество листьев дерева (в решающем дереве – состояние в сети). Определим граничные случаи при построении решающего дерева.
Минимальное дерево. Под минимальным деревом будем считать такое дерево, где каждому состоянию сети соответствует ровно один лист. В результате полученное дерево будет иметь минимальные значения и , то есть:
= , = −1. )*! )*!
В простейшем случае в сети из одного сенсора, который контролирует один параметр окружающей среды (N = 1, K = 1), чтобы сформировать узлов,
достаточно для данного сенсора определить S – 1 непересекающихся точек на области определения контролируемого параметра. В таком случае получим набор предикатов:
=[ ∶ ∈R, =1.. −1]. )*! *
Предикаты разбивают зону определения параметра на S )*!
промежутков, которые будем называть числовыми диапазонами. Каждый числовой диапазон будет соответствовать одному из состояний сети. Таким образом, нахождения параметра в рамках одного числового диапазона означает, что БСС не изменяет своего состояния, следовательно, передавать данные на базовую станцию нет необходимости. Пример минимального решающего дерева и его соответствующих числовых диапазонов, сформированных на базе предикатов, представлены на Рисунке 4.
а)
б)
Рисунок 4. Минимальное дерево: a) пример минимального дерева и б) его числовые диапазоны на базе предикатов дерева
Полное дерево: ситуация, когда каждое показание !” (при с!” = 1) имеет S разделений, таким образом, содержит S – 1 предикат. В результате количество узлов (предикатов) можно вычислить по формуле:
=[ : ∈R, =1.. ∙( −1)], )+, *
где – количество действительных показаний сети.
В результате получаем, что размер дерева варьируется в диапазоне:
=[| |,| |]=[ −1, ∙( −1)]. (4) )*! )+,
Количество показаний, участвующих в процессе классификации: = [1, ],
причем ситуация < означает, что не все показания сенсорной сети -.// участвуют в принятии решения, следовательно, такие показания можно исключить из сети без влияния на процесс классификации. Расчет количества сеансов связи при энергоэффективном методе передачи данных. Рассмотрим функцию изменения параметра окружающей среды = -.// (t),атакженаборпредикатов = [ ∶ * ∈R, =1.. ],где –количество предикатов обученного дерева. Зададим функцию состояния сенсора S(t), которая определяет принадлежность точки (t) к промежутку *: ( )={ * ∶ * ≤ ( ) < *0#}. На промежутке времени ∈ [ , ] количество передач данных по сети промежутками #,..., 1: =∑2 T h, ( )≠ ( +1) 0, ( )= ( +1) !"# . (5) -32 ! , ,0# можно вычислить через количество переходов переменной x(t) между В выражении используется h – среднее количество передач при маршрутизации в топологиях «дерево» и «ячеистая», для топологии «звезда» h = 1. Вычислим энергоэффективность алгоритма на основе числовых диапазонов. Для этого определим вероятность локального изменения состояния сенсора, то есть вероятность, когда значение x(t) сменило числовой диапазон в промежуток времени [t, t+1]: ' -=Z [ -0# - ], вычислена по формуле: ' =Z - ∙ ( - ). *3# !"* !"5 !"* 53#, 57* где !"* – условие, когда показание k-го параметра (k=1..K) n-го сенсора (n=1..N) является i-м числовым диапазоном (i=1..P). Таким образом, вероятность смены состояния БСС при изменении k-го параметра n-го сенсора может быть !" !"* !"* Другими словами, KS89 – это вероятность того, что n-му сенсору необходимо передать показания k-го параметра на базовую станцию. Таким образом, вероятность того, что n-й сенсор выполнит передачу данных, можно вычислить по формуле: =1−∏& [1− ( )]. (6) ! "3# !" Выражение (6) получено из соображения того, что мы можем определить вероятность отсутствия передачи по сети как ситуацию, когда каждый из параметров сети не изменил своего числового диапазона. В результате при использовании предлагаемого энергосберегающего алгоритма, n-й сенсор сокращает количество передач по сети на (1 − !)%. В третьей главе представлены результаты разработки программной реализации адаптивного энергосберегающего алгоритма классификации состояний в БСС. Алгоритм основывается на модели классификации – решающее дерево, что позволяет использовать базу знаний для энергоэффективного принятия решения. Процесс вычисления состояния сети при помощи дерева решений является идемпотентным, то есть, при условии одинаковых входных данных, гарантируется идентичность итогового результата. Таким образом, если новые показания с сенсоров не изменились, то и состояние сети остается прежним. При использовании предлагаемого алгоритма предполагается, что базовая станция будет получать показания с сенсоров в тот момент, когда БСС должна сменить свое состояние. В свою очередь базовая станция принимает решение о состоянии сенсорной сети на основе множества переданных данных от сенсоров. Таким образом, алгоритм энергоэффективной классификации состояний БСС состоит из двух этапов: 1. локальное принятие решения о смене состояния подсистемы (узла сети) и необходимости передачи данных на главный модуль; 2. принятие решения о текущем состоянии системы с учетом предыдущего состояния и новых показаний, полученных от сенсоров. На Рисунке 5 представлена контекстная диаграмма работы адаптивного энергосберегающего алгоритма классификации состояний в беспроводной сети, которая отображает взаимодействие с внешней системой. Рисунок 5. Контекстная диаграмма работы адаптивного энергосберегающего алгоритма классификации состояний в БСС Также в третьей главе представлен первый уровень декомпозиции контекстной диаграммы, анализ функциональных требований к разрабатываемому алгоритму, блок-схема алгоритма и основные элементы программного кода с описанием логики классификации состояний в БСС. В четвертой главе проведено экспериментальное исследование разработанного адаптивного энергосберегающего алгоритма обработки информации в БСС. Исследование состоит из трех частей: в первой части проводится модульное тестирование функциональных блоков алгоритма, во второй – исследование способа расчета вероятности передачи данных при стандартных распределениях контролируемой величины, в третьей – исследование энергоэффективности работы БСС при использовании разработанного алгоритма классификации состояний на полунатурной модели БСС. Модульное тестирование функциональных блоков выполнено для функции определения числовых предикатов и функции локального принятия решения о необходимости передачи данных по сети. Модульное тестирование подтвердило, что разработанные функции производят вычисления корректно. Для проверки достоверности расчетов энергоэффективности разработанного алгоритма были проведены исследования на различных моделях динамики параметров окружающей среды. Рассмотрено равномерное и нормальное распределения случайной входной величины. Результаты представлены на Рисунке 6. На рисунке слева представлено поведение случайной величины, справа – закрашенная область получена при помощи программной реализации алгоритма, пунктирная – при использовании разработанного способа расчета вероятности передачи данных по сети. Совпадение графиков доказывает достоверность полученных расчетов. При этом визуально можно выделить, что максимальное количество изменений состояния сети приходится на значение 0. Это объясняется тем, что вероятность попадания в положительную ось и отрицательную равновероятны. a) б) Рисунок 6. Графики моделирования случайных процессов и оценка вероятности передачи данных по сети: а) равномерное распределение, б) нормально распределение 13 В состав полунатурной модели БСС входило переменное количество сенсоров, параметров окружающей среды, состояний сети, а также различные топологии. Каждый сенсор предоставлял информацию об определенных параметрах окружающей среды (например: влажность, температура, давление, освещенность). Динамика параметров окружающей среды была сгенерирована при помощи гауссовских процессов. Для генерации состояний сети на основе входных данных был использован алгоритм кластеризации k-means. На первом этапе случайным образом было выбрано 40% данных, на которых было построено решающее дерево по алгоритму ID3. На втором этапе оставшиеся 60% данных были классифицированы с помощью полученной модели. Для оценки достоверности построенной модели была рассчитана точность классификации, равная (T) / (T + F), где T – количество верных ответов, F – количество ошибочных ответов. Результаты исследования разработанного алгоритма: – тестирование при различном количестве сенсоров, N: точность классификации более 99.6%, c ростом N количество предикатов уменьшается, а энергоэффективность алгоритма растет с 73% до 96%; – тестирование при различном количестве параметров окружающей среды, K: точность классификации более 99.3%, с ростом K уменьшается количество предикатов, а энергоэффективность растет с 88% до 97%; – тестирование при различном количестве состояний сети, S: точность классификации более 99.4%, c ростом S увеличивается количество предикатов, падает энергоэффективность с 97% до 77%; – тестирование при различном количестве связей в сети, h: точность классификации более 99%, остальные параметры без существенных изменений. Из результатов исследования видно, что построенная модель решающего дерева дает точность классификации состояний в сенсорной сети более 99%. Таким образом доказано, что алгоритм удовлетворяет своим функциональным требованиям. Энергоэффективность алгоритма (KS) зависит как от параметров БСС, так и от динамики входных данных. Для всех проведенных испытаний разработанного алгоритма установлено, что энергоэффективность работы БСС превышает 70%. Тестирование при различном количестве сенсоров N показало следующую зависимость: чем больше сенсоров контролируют параметры окружающей среды, тем выше энергоэффективность алгоритма. Это можно обосновать тем, что при большем количестве сенсоров модели решающего дерева удается найти наиболее показательные входные данные. Тестирование при различном количестве состояний сети S показало следующую зависимость: чем больше состояний сети, тем ниже энергоэффективность алгоритма. Также установлено, что энергоэффективность сети при использовании предлагаемого алгоритма не зависит от топологии сети. В заключении диссертационной работы представлены общие результаты исследования, которые были получены при выполнении работы. ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ Для достижения поставленных целей в диссертационной работе решены актуальные научно-технические задачи и получены следующие результаты: 1. Проведен системный анализ способов энергопотребления в беспроводных сенсорных сетях, который определил, что 70% электроэнергии узла сети расходуется на коммуникацию по беспроводной сети; 2. Проведен системный анализ функций беспроводных сенсорных сетей в различных отраслях, который позволил сформировать классификацию функций БСС: сбор данных, мониторинг, контроль, слежение и формирование управляющих команд, и сформулировать общую задачу для разрабатываемого алгоритма – принятие решения о состоянии в БСС; 3. Разработан адаптивный энергосберегающий алгоритм обработки информации в БСС, реализующий принятие решения о классификации состояния сети на основе набора прецедентов; 4. Разработана программная реализация алгоритма классификации в БСС на программном языке Python; 5. Проведено экспериментальное исследование способа расчета вероятности передачи данных, которое подтвердило достоверность теоретических расчетов с погрешностью менее 1%; 6. Проведен сравнительный анализ предлагаемого алгоритма классификации состояний в БСС на математической модели и при исследовании на полунатурной модели, который показал, что при использовании алгоритма точность классификации составляет более 99%, а количество сеансов связи сокращается более чем на 70%.