Авторефераты по всем темам >>
Авторефераты по техническим специальностям
На правах рукописи
Тараканов Евгений Владимирович
АГРЕГИРОВАНИЕ ДАННЫХ МУЛЬТИСЕНСОРОВ В БЕСПРОВОДНЫХ СЕНСОРНЫХ СЕТЯХ
Специальность: 05.11.13 - Приборы и методы контроля природной среды, веществ, материалов и изделий
АВТОРЕФЕРАТ
диссертации на соискание ученой степени кандидата технических наук
Томск - 2012
Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования Национальный исследовательский Томский политехнический университет
Научный консультант: Муравьев Сергей Васильевич доктор технических наук, профессор
Официальные оппоненты: Шидловский Станислав Викторович, доктор технических наук, заведующий лабораторией реконфигурируемых высокопроизводительных систем Национального исследовательского Томского государственного университета Майстренко Андрей Васильевич, кандидат технических наук, доцент кафедры электронных устройств автоматизации и управления Томского государственного университета систем управления и радиоэлектроники
Ведущая организация: Институт проблем управления им. В.А.
Трапезникова РАН, г. Москва
Защита состоится 25 декабря 2012 г. в 17.00 часов на заседании диссертационного совета Д 212.269.09 при Федеральном государственном бюджетном образовательном учреждении ВПО Национальный исследовательский Томский политехнический университет по адресу: Россия, 634028, г. Томск, ул. Савиных, 7, ауд. 215 (актовый зал).
С диссертационной работой можно ознакомиться в научно-технической библиотеке Федерального государственного бюджетного образовательного учреждения высшего профессионального образования Национальный исследовательский Томский политехнический университет по адресу: г. Томск, ул. Белинского, 55.
Автореферат разослан 21 ноября 2012 г.
Ученый секретарь диссертационного совета докторских и кандидатских диссертаций, кандидат технических наук, доцент Б.Б. Винокуров
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность работы. Сенсорная сеть представляет собой распределенную, самоорганизующуюся, устойчивую к отказам отдельных элементов сеть из необслуживаемых и не требующих специальной установки устройств. В таких системах разнородные измерительные данные собираются мультисенсорами, входящими в состав узлов, расположенных в подлежащих мониторингу точках определенной географической области, и передаются по беспроводной сети в центральный узел для обработки и принятия решений.
Мультисенсор представляет собой набор датчиков (первичных измерительных преобразователей) измеряющих одновременно несколько физических величин.
Обычно сеть имеет иерархическую (древовидную) структуру, в которой на каждом уровне данные могут передаваться от узлов-источников к одному или нескольким узлам-приемникам. Благодаря быстрому развитию технологий беспроводной связи, миниатюризации и снижения энергопотребления электронных устройств, все большее развитие получают беспроводные сенсорные сети (БСС). Основными преимуществами беспроводных (БСС) являются простота развертывания, высокая надежность сети в целом и стойкость к электромагнитным помехам. Благодаря этому БСС все чаще используются для организации различных видов мониторинга: параметров окружающей среды, состояния конструкций, зданий и сооружений, в системах безопасности (пожарной, сейсмической, экологической и др.), для отслеживания целей в процессе ведения боевых действий и т.п.
При передаче данных в беспроводных сенсорных сетях возникают существенные проблемы, связанные с ограниченной полосой пропускания используемых в качестве линий связи радиоканалов. В частности, в ситуациях, когда много узлов-источников одновременно инициируют передачу данных, может возникать перегрузка или даже коллапс сети, в результате чего ее пропускная способность, выражаемая в количестве проходящих от источника к центральному узлу пакетов данных в единицу времени, падает практически до нуля. Кроме того, отдельные сенсорные узлы могут как добавляться в сеть, так и, по разным причинам, выходить из состава сети. Изменение в конфигурации сети, как правило, приводит к необходимости изменять маршруты пакетов данных, что также снижает пропускную способность сети.
Одним из возможных подходов к решению проблемы является назначение приоритетов передаваемым по сети пакетам и организация первоочередной доставки пакетов с более высоким приоритетом. Перспективным является способ назначения приоритетов узлам беспроводной сенсорной сети с использованием некоторого бинарного отношения консенсуса, получаемого в результате процедуры агрегирования предпочтений. Предпочтения в форме m ранжирований n узлов формируются на основе показаний мультисенсоров. Он позволяет динамически назначать приоритеты узлам сети (и, следовательно, передаваемым ими пакетам), формировать очередь передачи пакетов и распределять пропускную способность сети в зависимости от смыслового содержания (семантики) передаваемых данных. Таким образом, решение о приоритетной передаче данных принимается на основе агрегирования разнородных данных мультисенсоров.
Этот подход согласуется с концепцией качества обслуживания (Quality of Service, QoS), являющейся общепринятой для сенсорных сетей, основанных на обнаружении событий. Основными показателями QoS являются малая задержка передачи данных от источника к центральному узлу и низкие потери данных о событиях.
Целью диссертационной работы является исследование подходов к агрегированию измерительных данных мультисенсоров в беспроводной сенсорной сети на основе теории голосования и разработка, программная реализация и экспериментальная апробация метода управления передачей пакетов данных в беспроводной сенсорной сети с учетом приоритета передаваемых данных.
В соответствии с поставленной целью были сформулированы следующие задачи исследования:
Х анализ методов агрегирования данных мультисенсоров;
Х разработка метода назначения приоритетов пакетам данных мультисенсоров с использованием агрегирования разнородных данных на основе отношения консенсуса;
Х разработка протокола передачи пакетов данных мультисенсоров в беспроводной сенсорной сети на основе разработанного метода назначения приоритетов;
Х программная реализация и экспериментальная проверка метода передачи пакетов данных мультисенсоров в беспроводной сенсорной сети.
Методы исследования. При разработке метода агрегирования измерительных данных использованы методы теории бинарных отношений и теории голосования, теории измерений, теории вероятностей и математической статистики. Для экспериментальной апробации протоколов передачи данных в сенсорной сети использовалась среда моделирования TOSSIM (эмулятор сенсорной сети на основе операционной системы TinyOS).
Достоверность полученных результатов диссертационной работы подтверждается совпадением с достаточной точностью расчетных данных и результатов моделирования и эксперимента.
Научная новизна работы.
1. Предложен метод использования агрегирования предпочтений для организации передачи данных в беспроводной сенсорной сети, позволяющий решить проблему ограниченной пропускной способности радиоканалов и обеспечивающий минимальную задержку при передаче пакетов данных, несущих информацию о событиях.
2. Предложен метод обеспечения максимальной пропускной способности беспроводной сенсорной на основе функции расстояния Кемени с учетом вероятности потери пакетов.
3. Разработан и экспериментально апробирован программный комплекс передачи пакетов данных в беспроводной сенсорной сети, управляющий интервалами передачи пакетов данных и очередью передачи пакетов данных на основании приоритетов узлов БСС.
Практическая ценность работы. Разработанный в ходе диссертационных исследований программный пакет передачи данных в беспроводной сенсорной сети, благодаря первоочередной передачи более приоритетных данных и назначению интервалов передачи пакетов данных узлам сети, может найти широкое применение в распределенных системах экологического мониторинга, контроля состояния промышленных и гражданских объектов.
Реализация и внедрение результатов работы. Результаты работы использованы Х на Новоиркутской ТЭ - ОАО Иркутскэнерго при организации сбора данных для экологического мониторинга окружающей среды на территории ТЭ - (акт внедрения приложен к диссертации);
Х при выполнении проекта "In-network importance ranking in wireless sensor network data collection (Внутрисетевое ранжирование при организации сбора данных в сенсорной сети)", грант Национального университета Сингапура по программе EERSS, 2007-2009 гг.).
Положения, выносимые на защиту:
1. Предложенный метод агрегирования предпочтений, сформированных на основе передаваемых по беспроводной сенсорной сети данных измерений мультисенсоров, позволяет избавиться от перегрузок сети и обеспечить минимальную задержку при передаче пакетов данных (заявка на патент № 2011154473).
2. Использование функции расстояния Кемени с учетом вероятности потери пакетов позволяет обеспечить максимальную пропускную способность беспроводной сенсорной сети.
3. Разработанный на базе агрегирования предпочтений протокол передачи пакетов данных в беспроводной сенсорной сети протестирован в системе TOSSIM и показал достаточное совпадение значений показателей эффективности сети с предсказанными теоретическими исследованиями.
Апробация результатов работы. Основные результаты диссертационной работы докладывались и обсуждались на следующих конференциях:
Х XV Международная научно-практическая конференция студентов, аспирантов и молодых ученых Современные техника и технологии СТТТ2009, г. Томск, 2009 г.;
Х Региональная научно-методическая конференция Электронные дидактические материалы в инженерном образовании, г. Томск, 2009 г.;
Х XVI Международная научно-практическая конференция студентов, аспирантов и молодых ученых Современные техника и технологии СТТТ2010, г. Томск, 2010 г.;
Х Университетская научно-методическая конференция Совершенствование содержания и технологии учебного процесса, г.
Томск, 2010 г.;
Х IEEE Sensors Applications Symposium (SAS-2010), г. Лимерик, Ирландия, 2010 г.;
Х XVII Международная научно-практическая конференция студентов, аспирантов и молодых ученых Современные техника и технологии СТТТ2011, г. Томск, 2011 г. (доклад отмечен дипломом II степени);
Х International Conference on Instrumentation, Measurement, Circuits and Systems, ICIMCS 2011, Гонконг, 2011 г.
Публикации. Основные результаты исследований отражены в публикациях: две статьи в ведущем рецензируемом научном журнале, рекомендуемом ВАК; одна статья в рецензируемом журнале; две статьи в трудах зарубежных конференций, шесть статей в сборниках трудов российских конференций.
Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и электронных ресурсов из 103 библиографических ссылок и приложения. Работа содержит 94 страницы основного текста, включая 26 рисунков и 5 таблиц.
ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении: обоснована актуальность исследуемой проблемы;
сформулированы цель исследований и основные положения, выносимые на защиту; определены решаемые задачи; указаны научная новизна и практическая ценность работы.
В первой главе Агрегирование данных мультисенсоров дана постановка проблемы агрегирования измерительных данных и представлен аналитический обзор соответствующих подходов к решению проблемы: байесовская сеть, теория Демпстера-Шефера и др.
Задача агрегирования (слияния, интеграции) данных мультисенсоров (multisensor data fusion problem) состоит в формировании суждений о состоянии объекта на основе результатов измерений разнородных физических величин. При этом полученное в результате процедуры агрегирования суждение обладает большей достоверностью по сравнению с суждениями, сформированными на основе индивидуальных измерений. То есть агрегирование обладает синергетическим эффектом.
Пусть имеется множество n мультисенсоров (узлов) A = {a1, a2,..., an}, состоящих из m датчиков (сенсоров) каждый.
Байесовская сеть представляет собой направленный ациклический граф, каждой вершине которого может соответствовать показание мультисенсора или суждение, а дуги графа кодируют отношения правдоподобия между вершинами.
Отношение правдоподобия соответствует вероятности Pi (cij ) события V на i-ом узле при некотором значении измеряемой величины cij; i = 1, Е, m; j = 1, Е, n. В данном подходе измеренное значение величины переводится в отношение правдоподобия с помощью некоторой функции преобразования fi (cij ), задаваемой для каждой из m измеряемых величин. Если измеряемые переменные являются независимыми случайными величинами, то вероятность события Pi(V ) на узле i n вычисляется по формуле полной вероятности Pi(V ) = (cij ). Если измеряемые Pi j=переменные являются зависимыми, вероятность Pi(V ) вычисляется с использованием условных вероятностей. Тогда для каждого мультисенсора с помощью байесовской сети может быть вычислена вероятность некоторого события в системе мониторинга (например, пожара для системы пожарной безопасности), на основе которых может быть выработано общее суждение.
Подход Демпстера-Шефера представляет собой математическую теорию свидетельств, основанную на двух функциях преобразования измеряемых величин - доверия fi (cij ) и правдоподобия fi (cij ) - использующихся для вычисления возможности события. Для каждой измеряемой переменной назначаются три ( ( меры: мера того, что событие произошло mV ); что событие не произошло mV ) и мера неопределенности mV V ). Вероятность Pi (cij ) того, что событие ( произошло, лежит в интервале mV ) < Pi(V ) <1- mV ). Таким образом, в отличие ( ( от байесовской сети, в подходе Демпстера-Шефера каждый параметр описывается не одной, а тремя мерами. Преимуществом этого подхода является получение диапазона вероятности события Pi(V ) и учет неопределенности каждого сенсора.
В теории голосования для каждой из m измеряемых величин строится ранжирование = a1 a2 as at an, которое может включать как { } строгое отношение предпочтения , так и отношение безразличия ~. Множество полученных таким образом ранжирований = 1,2,,m будем называть { } профилем предпочтения для данных m свойств и n узлов. Задача агрегирования предпочтений заданного профиля заключается в нахождении единственного строгого ранжирования (отношения консенсуса), одинаково близкого ко всем исходным ранжированиям.
Применительно к проблеме агрегирования измерительных данных мультисенсоров в беспроводных сенсорных сетях следует отметить, что корректность результатов традиционно применяемых подходов, включая байесовские сети, теорию Демпстера-Шефера, фильтра Калмана и др., зависит от выбора той или иной функции преобразования измеряемых величин в суждения.
Поскольку данная функция, как правило, выбирается из субъективных предположений или на основе весьма приближенных вычислений, указанные подходы уступают в корректности методам теории голосования, в которых ранжирования формируются на основе непосредственных показаний мультисенсоров, а суждения выносятся без использования каких-либо функций преобразования показаний.
Таким образом, для назначения приоритетов узлам сенсорной сети был выбран подход к агрегированию данных мультисенсоров на основе теории голосования.
Во второй главе Агрегирование данных мультисенсоров на основе отношения консенсуса рассматриваются методы построения отношения консенсуса на основе измерительной информации и обсуждается использование ранжирования Кемени для построения отношения консенсуса.
Для примера рассмотрим систему пожарной сигнализации, состоящую из распределенных по некоторой контролируемой площади узлов, мультисенсоры которых измеряют 6 величин каждый - температуру, скорость изменения температуры, задымленность, уровень СО, срабатывание датчика пламени и присутствие персонала (таблица 1).
Таблица 1. Данные с узлов системы пожарной сигнализации.
Результаты измерений 1 2 3 4 5 Узел Скорость Уровень Срабатывание Температура, изменения Задымленность, Наличие СО, датчика С температуры, дБ/м людей мг/м3 пламени С/с a1 42 8 0,03 0,31 - - a2 270 15 0,08 0,86 + - a3 80 35 0,13 0,83 + + a4 50 12 0,03 0,58 + - a5 300 38 0,10 0,90 - - a6 62 10 0,11 0,70 + + a7 62 7 0,04 0,18 - - Профиль предпочтения, построенный для представленных в таблице результатов измерений, имеет следующий вид:
1 : a5 a2 a3 a6 a7 a4 a2 : a5 a3 a2 a4 a6 a1 a3 : a3 a6 a5 a2 a7 a4 a. (1) 4 : a5 a2 a3 a6 a4 a1 a5 : a2 a3 a4 a6 a1 a5 a6 : a3 a6 a1 a2 a4 a5 a Ранжирование представим матрицей отношения R =, строки и столбцы rij которой соответствуют узлам a, и rij =1 если ai aj rij = 0 если ai aj rij = -; ;
если ai aj. Тогда расстояние Кемени d(k,l ) между любыми двумя ранжированиями k и l определяется формулой k l d(k,l ) = rij - rij | |. (2) i< j Расстояние между произвольным ранжированием и профилем можно теперь определить следующим образом:
m mm kk D(,) = d(, ) = | rij - rij | = d. (3) k ij k =1 i< j k=1 i< j k =Из (3), с учетом rij = 1 для всех i < j, что соответствует естественному линейному порядку a1 a2 ... an, следует, что для любого k = 1, Е, m имеем:
k k k dij =|1-1|= 0 если aik ak ; dij =| 0 -1|=1 если aik ~ ak и dij =| -1-1|= 2 если j j aik ak.
j Тогда можно определить матрицу профиля P = [pij], где m k pij =, i, j =1,...,n, (4) d ij k =и отношение консенсуса определяется как такое ранжирование узлов из A, что расстояние D(,) от до профиля минимально, то есть = arg min D(,) = arg min pij, (5) i< j где - множество всех n! строгих предпочтений на A.
Для нахождения отношения консенсуса для профиля , описываемого матрицей P известно простое естественное правило Кондорсе: в каждом сравнении альтернатив предпочтительной является альтернатива, предпочитаемая большинством избирателей, т.е. ai a если и только если pij > pji. Однако, j ранжирование Кондорсе не обязательно транзитивно, т.е. может быть, что ai aj и aj ak, тогда как ak ai. Единственным корректным способом преодоления указанной трудности является нахождение отношения консенсуса по правилу Кемени (5).
К сожалению, задача о ранжировании Кемени является NP-полной, то есть время нахождения ее точного решения экспоненциально зависит от n. Для построения отношения консенсуса в беспроводных сенсорных сетях предпочтительнее использовать правило Борда, которое представляет собой приближенное решение задачи Кемени. По правилу Борда каждому узлу присваивается количество баллов в зависимости от его места в ранжировании: баллов за последнее место, 1 балл за предпоследнее место и т.д. до n - 1 баллов за первое место. Баллы каждого узла суммируются по всем ранжированиям, и его место в отношении консенсуса определяется полученной суммой. Решение по правилу Борда в большом количестве практических случаев может служить хорошей заменой ранжирования Кемени.
Для профиля (1) итоговое отношение консенсуса по Борда имеет следующий вид:
= a3 a2 a5 a4 a1 a7. (5) { } Оно позволяет выстроить n узлов в порядке важности измеряемых ими физических величин.
В работе предложено использовать этот порядок для назначения приоритетов узлам сети, так как ранжирования исходного профиля формируются исходя из актуальных данных измерений, характеризующих обстановку в окружении каждого конкретного сенсорного узла. Высший приоритет получает узел a3, а низший - a7.
В третьей главе Разработка протокола передачи измерительных данных мультисенсоров в беспроводных сенсорных сетях рассматриваются характеристики качества обслуживания в беспроводных сенсорных сетях, описывается применение отношения консенсуса для обеспечения нормального функционирования сенсорной сети путем формирования очередей передачи данных сенсорных узлов и назначения интервалов ожидания передачи.
Приводится статистическое обоснование предложенной схемы организации передачи данных в сенсорной сети.
Беспроводная сенсорная сеть, как правило, имеет древовидную топологию (рис. 1), в которой только определенные узлы (будем называть их узламипредками) могут взаимодействовать с другими узлами (потомками). Кластером будем называть узел-предок со всеми его ближайшими потомками.
Для обеспечения бесперебойной работы сенсорной сети требуются специальные методы передачи данных, позволяющие решать проблему перегрузки сети и повысить надежность доставки пакетов данных до центрального узла. Для этой цели используются различные способы, такие как алгоритм ART, протоколы VPCR, RCRT и др. Например, протокол RCRT реализует способ организации передачи пакетов путем назначения интервала ожидания на основе динамического вычисления соотношения текущей и максимальной пропускной способности сети.
В этом способе каждый узел сообщает требуемый ему интервал ожидания центральному узлу, после чего центральный узел назначает интервалы ожидания узлу пропорционально затребованному. Назначенные интервалы ожидания сообщаются узлам сети с помощью пакетов обратной связи. При переполнении очереди передачи вновь поступающие пакеты отбрасываются. Недостатком этого способа является необходимость принятия каждым узлом решения о требуемом ему интервале ожидания. Вообще, существующие протоколы рассматривают все передаваемые пакеты как равноправные и не управляют очередностью их передачи.
Центральный узел Кластер...
(i - 1)-го уровня h Узел-...
Кластеры предок i-го уровня Узлы-...
...
...
1 nih потомки 1 1 niniРис. 1. Топология древовидной сети В диссертационной работе предложен способ организации передачи пакетов данных в беспроводной сенсорной сети с учетом приоритетов узлов, состоящий из очереди передачи пакетов данных в порядке приоритетов пакетов данных и алгоритма распределения пропускной способности сети.
Блок-схема способа приведена на рис. 2. Его суть состоит в следующем: на каждом узле БСС, пересылающем пакеты данных с узлов-потомков на родительский узел, формируется и поддерживается ранжирование узловпотомков. На основании извлеченной из пересылаемых пакетов данных измерительной информации методом Борда формируется ранжирование узлов в порядке важности измеряемых им проявлений свойств. Поскольку формирующий ранжирование узел сам генерирует пакеты данных, то он также включен в ранжирование и тоже имеет некоторый приоритет. Данное ранжирование пересчитывается при каждом поступающем пакете данных. Все отправляемые сообщения хранятся в единой очереди передачи. При добавлении нового пакета его приоритет сравнивается с приоритетами пакетов в очереди и добавление происходит перед пакетом, имеющим более низкий приоритет. В случае переполнения очереди сообщений пакет с наименьшим приоритетом отбрасывается.
Алгоритм распределения пропускной способности сети использует для работы уже сформированные приоритеты узлов-источников данных и задает интервалы передачи пакетов данных узлам-потомкам обратно пропорционально приоритету узла. Формирование интервалов передачи пакетов данных производится по формуле:
от узла-потомка к узлу-предку Приемный буфер Буфер передачи Блок накопления Блок назначения пакетов данных интервалов ожидания Блок построения Блок нахождения профиля предпочтений итогового ранжирования Рис. 2. Предложенная блок-схема протокола передачи данных узла R TN = T (6) rmax - ri +, где Т - интервал передачи пакетов данных, назначенный текущему узлу его узломпредком; rmax - максимальный приоритет узлов-потомков; ri - приоритет узла потомка; R определяется по формуле:
ni R = ni(rmax +1) -, (7) r i где ni - число узлов-потомков.
Периодически обновленные интервалы передачи пакетов данных рассылаются узлам-потомкам через пакеты обратной связи.
Для проверки, не теряется ли существенная информация при отбрасывании пакетов, в диссертационной работе предложено теоретическое обоснование предложенной схемы управления очередью передачи. Для этого был использовано выражение для основанного на статистических соображениях коэффициента ранговой корреляции Кендалла , который принимает значения в диапазоне от -(абсолютно несовместимые ранжирования) до +1 (полное совпадение ранжирований).
Совместимость двух ранжирований 1 и 2 по Кендаллу определяется по формуле:
1 = r rij, (8) ij n(n -1) i< j 1 где rij и rij - элементы матрицы отношений для отношений 1 и соответственно.
Как коэффициент ранговой корреляции Кендалла (8), так и расстояние Кемени (3) являются мерами совместимости ранжирований. Между ними существует известная связь:
d 1,( ) 1,2 =1-. (9) ( ) n n -( ) Рассмотрим два ранжирования 1 и 2 для n узлов некоторого кластера.
Естественным требованием для них является то, что они должны быть согласованы между собой. Соответствующий уровень согласованности обозначим через 1. Для n - k узлов, где k - число отброшенных пакетов, получатся два ' других отношения консенсуса 1 и ', с уровнем согласованности 2. Стремясь сохранять согласованность при любом k, примем, что 2 = 1.
Обозначив d1 = d 1,2 для случая n узлов и d2 = d 1,2 для случая n - k ( ) ( ) узлов, получаем выражения для соответствующих коэффициентов ранговой корреляции:
d1 d1 =1- и 2 =1-.
n n -1 n ( ) ( - k n - k -)( ) d1 dТогда =, откуда n n - k n - k n - k -( ) ( )( ) n d2 ( - k n - k -)( ) =. (10) d1 n n - k ( ) Введем параметр (n, k), где n - число узлов в сети, k - количество отбрасываемых пакетов, названный относительной несогласованностью приоритетов при удалении k из n пакетов:
d1 - d2 d(n,k) = =1-. (11) d1 dС учетом выражения (10) получаем:
(n - k)(n - k -1) (n,k) =1-. (12) n(n -1) Ясно, что 0 (n,k) 1.
Задаваясь значением параметра (n, k), можно выбирать обоснованное количество k отбрасываемых пакетов для известных значений n (см. рис. 3).
Например, при числе узлов n = 30 удаление четырех пакетов соответствует относительной несогласованности 0,25, а удаление восьми пакетов увеличивает несогласованность до 0,47.
В диссертационной работе проведена оценка вероятности потери пакета данных в зависимости от приоритета узла-источника пакета.
Пакет, отправленный узлом с приоритетом j в общем ранжировании, не попадет в итоговое ранжирование в том случае, если в частном ранжировании на кластере i будет ni - ki пакетов с более высоким приоритетом.
Вероятность того, что первый пакет в частном ранжировании i будет иметь в ранжировании приоритет выше, чем j, определяется следующим образом:
0,n = 0,0,0,0,0,0,0,0,0 2 4 6 8 Число отброшенных пакетов k Рис. 3. Зависимость параметра от n и k j - Pj =, n - ki -Для всех пакетов с номерами от 1 до ni - ki в ранжировании i вероятность получить в ранжировании приоритет выше, чем j, определяется как ni -ki j - l Pj =. (13) n - ki - l l=что и представляет собой вероятность потери пакета при передаче данных в сети.
В факториальной форме эта вероятность имеет вид:
j!(n - ni)! Pj =. (14) ( j - ni + k )!(n - ki)! i График изменения вероятности потери пакета с приоритетом j в зависимости от значения приоритета для случая n = 30, ni =15, ki = 8 представлен на рис. 4.
Pj 0,0,0,0,0,0,0,0,0,j 0 5 10 15 20 25 Рис. 4. Вероятность потери j-го пакета при n = 30, ni =15, ki = расстояния Изменение относительного Из формулы (14) и рис. 4 ясно, что вероятность потери мала при приоритете j < ni. Выражение (14) позволяет выбирать параметры сети таким образом, чтобы гарантировать доставку критичных пакетов.
В четвертой главе Экспериментальная проверка метода передачи пакетов данных мультисенсоров в беспроводной сенсорной сети приведены результаты экспериментальных исследований разработанного протокола передачи данных.
В распоряжении разработчиков современных сенсорных сетей имеются находящиеся в открытом доступе средства разработки программного обеспечения узлов, такие как операционная система TinyOS. Проверка работоспособности таких сетей, содержащих большое количество узлов, обычно осуществляется с помощью специальных программ-эмуляторов.
В составе TinyOS 2.1 имеется эмулятор TOSSIM, позволяющий имитировать происходящие в узлах сети события, такие как получение показаний сенсоров, передача/получение пакета и т.д. Характеристики TOSSIM: масштабируемость, полнота, точность, достоверность - обеспечивают возможность всесторонней проверки функционирования сенсорной сети без ее фактического развертывания.
В процессе эмулирования полагалось, что разработанный программный комплекс передачи пакетов данных в беспроводной сенсорной сети, управляющий интервалами передачи пакетов данных и очередью передачи пакетов данных на основании приоритетов узлов, реализован на аппаратной платформе MICAz, состоящей из Рис. 5. Аппаратная платформа микроконтроллера Atmel AVR и микросхемы MICAz радиосвязи Chipcon CC2420 (рис. 5).
Предполагалось, что экспериментальная беспроводная сенсорная сеть пожарной сигнализации состоит из 241 узла, организованного в 15 кластеров по узлов в каждом. Каждый узел имеет в своем составе тот же набор сенсоров, что приведен в таблице 1. Радиомодуль CC2420 обеспечивает скорость передачи данных до 256 кБ/с и имеет буфер в 10 пакетов по 60 байт.
Были организованы два эксперимента: в первом эксперименте проверялись управление интервалом ожидания передачи пакетов и задержка доставки пакетов до центрального узла сети; во втором эксперименте определялась доля потерянных пакетов в общем количестве отправленных к центральному узлу пакетов.
В первом эксперименте узлы располагались вдоль прямой линии. Пожар начался в районе 26 узла и распространялся вдоль линии со скоростью 1 узел/с. За счет использования разработанного протокола передачи измерительных данных задержка при передаче пакетов данных на центральный узлел с узлов, получающих информацию о пожаре (пакетов с высоким приоритетом), уменьшилась с 900 до 500 мс. При этом задержка при передаче данных для узлов, не получающих информации о пожаре (пакетов с низким приоритетом), выросла до 1800 мс.
Проведенное измерение количества пакетов, получаемых центральным узлом от узлов сети в секунду, показало, что при использовании разработанного программного комплекса передачи данных центральный узел получает в среднем 0,21 пакета данных с высоким приоритетом и 0,061 пакета данных с низким приоритетом в секунду. Без использования разработанного программного комплекса центральный узел получает 0,068 пакета данных в секунду (рис. 6).
Рис 6. Скорость получения пакетов центральным узлом при использовании (слева) и без использования (справа) разработанного протокола передачи данных За счет использования алгоритма управления интервалами ожидания передачи пакетов данных скорость отправки пакетов (количество отправленных к центральному узлу пакетов данных в секунду), например, с узла 129 при достижении пожаром района его расположения увеличивается с 0,26 пакетов/с до 0,86 пакетов/с (рис. 7).
Рис. 7. Скорость отправки пакетов с узла 1Во втором эксперименте для определения доли потерянных пакетов в общем количестве отправленных к центральному узлу пакетов, которая зависит от приоритета узла сети, см. формулу (14), генерировались случайные значения показаний сенсоров, с каждого узла отправлялись 140 пакетов. Фиксировалось количество пакетов, полученных центральным узлом, по которому судили о доле потерь. Результаты исследований показали, что зависимость доли потерянных пакетов и числа пакетов, полученных центральным узлом, от приоритета узлаисточника данных имеет характер, предсказанный выражением (14), см. рис. 8 и рис. 4. Для узлов с приоритетами от 1 до 7 потери составили около 10% всех пакетов, а для узлов с приоритетами от 8 до 16 потери составили около 90% отправленных узлами пакетов.
Рис. 8 Доля потерь пакетов в зависимости от приоритета узла сети В приложении диссертации приведен акт внедрения результатов кандидатской диссертации на Новоиркутской ТЭ - ОАО Иркутскэнерго при создании информационно-измерительной системы экологического мониторинга окружающей среды.
ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ 1. Разработан метод назначения приоритетов узлам беспроводной сенсорной сети с использованием агрегирования разнородных данных на основе вычисления отношения консенсуса по правилу Борда.
2. Разработан способ организации передачи пакетов данных в беспроводных сенсорных сетях на основе назначения приоритетов узлам беспроводной сенсорной сети, формирования очереди передачи и назначения интервала передачи пакетов данных с учетом приоритетов узлов.
3. Разработан и экспериментально апробирован программный комплекс, обеспечивающий реализацию предложенного способа организации передачи пакетов данных в беспроводных сенсорных сетях, повышение надежности и снижение задержки доставки пакетов данных с более приоритетных узлов.
4. Результаты работы применены в построении программно-аппаратного измерительного комплекса для экологического мониторинга окружающей среды на территории ТЭЦ-9 и при выполнении проекта "In-network importance ranking in wireless sensor network data collection (Внутрисетевое ранжирование при организации сбора данных в сенсорной сети)", грант Национального университета Сингапура по программе EERSS, 2007-2009 гг.) ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ 1. Muravyov S.V., Tarakanov E.V. Multiple solutions of an exact algorithm for determination of all Kemeny rankings: preliminary experimental results // Proceedings of the 2011 International Conference on Instrumentation, Measurement, Circuits and Systems (ICIMCS 2011), December 12-13, 2011, Hong Kong, vol. 1, New York: ASME Press, 2011, pp. 17-20.
2. Муравьев С.В., Тараканов Е. В. Передача данных в беспроводных сенсорных сетях с приоритетами на основе агрегирования предпочтений // Известия Томского политехнического университета. - 2012. - Т. 320. - № 5. - C. 111116.
3. Shao Tao, Chan M. Ch., Muravyov S.V., Tarakanov E.V. A Prioritized Convergecast Scheme using Consensus Ranking in Wireless Sensor Networks // Proceedings of the IEEE Sensors Applications Symposium (SAS-2010), Limerick, Ireland, 2325 February 2010. - Limerick: IEEE, 2010. - P. 251-256.
4. Тараканов Е.В. Повышение надежности доставки приоритетных пакетов данных в сенсорных сетях // Проблемы информатики. - 2011. - Вып.
Специальный. - C. 102-107.
5. Тараканов Е.В. Особенности передачи данных в беспроводных сенсорных сетях // Современные техника и технологии: сборник трудов XVII Международной научно-практической конференции студентов, аспирантов и молодых ученых в 3-х томах - Томск, ТПУ, 12Ц16 апреля 2011. - Томск: Изд.
ТПУ, 2011. - С. 392-393.
6. Муравьев С.В., Тараканов Е.В. Cпособ передачи пакетов в беспроводных сенсорных сетях / Патент на изобретение, заявка № 2011154473 от 29.12.20г.
7. Тараканов Е.В. Использование отношений консенсуса для назначения приоритетов передачи данных в беспроводных сенсорных сетях // Современные техника и технологии: сборник трудов XVI Международной научно-практической конференции студентов, аспирантов и молодых ученых, Томск, 12Ц16 апреля 2010. - Томск: Изд. ТПУ, 2010. - С. 392-393.
8. Баранов П.Ф., Горисев С.А., Жилкин П.Н., Кириченко Е.М., Ряшенцев И.В., Тараканов Е.В. Создание среды компьютерно-сетевых лабораторных практикумов удаленного доступа на основе интеграции системы управления интернет-обучение MOODLE и программно-аппаратных комплексов на базе LabVIEW // Совершенствование содержания и технологии учебного процесса: Материалы университетской научно-методической конференции [Электронный ресурс] - Томск, ТПУ, 12-13 февраля 2010. - Томск: ТПУ, 2010.
9. Баранов П.Ф., Тараканов Е.В. Применение технологий Labview для разработки лабораторных практикумов удалённого доступа // Электронные дидактические материалы в инженерном образовании: Материалы региональной научно-методической конференции [Электронный ресурс] - Томск, 11-12 октября 2009. - Томск: ИДНО ТПУ, 2009.
10. Khomyakova M.S., Tarakanov E.V., Baranov P.F. Сonsensus relation for data fusion in wireless sensor network // Modern Technique and Technologies (MTT2009): Proceedings of the 15th International Scientific and Practical Conference of Students, Post-graduates and Young Scientists, Tomsk, May 4-8, 2009. - Tomsk:
TPU Press, 2009. - С. 44-46.
11. Тараканов Е.В. Экспериментальные исследования протокола передачи данных с приоритетами в беспроводной сенсорной сети в системе TOSSIM // Известия Томского политехнического университета. - 2012. - Т. 321. - № 5 - C. 98-106.
Авторефераты по всем темам >>
Авторефераты по техническим специальностям