автореферат диссертации по радиотехнике и связи, 05.12.13, диссертация на тему:Определение координат в беспроводных сенсорных сетях

На правах рукописи

Иванов Евгений Владимирович

ОПРЕДЕЛЕНИЕ КООРДИНАТ В БЕСПРОВОДНЫХ СЕНСОРНЫХ СЕТЯХ

Специальность 05.12.13 - Системы, сети и устройства телекоммуникаций

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

003453058

Москва, 2008

003453058

Работа выполнена в Московском Физико-Техническом Институте (Государственном Университете) на кафедре прикладной электродинамики и информационных систем реального времени в ОАО "Радиофизика"

Защита состоится 9 декабря 2008 г. в 17 часов на заседании диссертационного совета Д 212.156.04 при Московском физико-техническом институте (ГУ) по адресу: 141700, г. Долгопрудный, Московской обл., Институтский пер., д. 9, Новый корпус, ауд. 204.

С диссертацией можно ознакомиться в библиотеке Московского физико-технического института (ГУ). Автореферат разослан 7 ноября 2008 г.

Ученый секретарь

диссертационного совета Д 212.156.04

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

кандидат технических наук Курикша Вадим Александрович доктор технических наук, профессор Шевырев Александр Владимирович Московский научно-исследовательский радиотехнический институт кандидат технических наук Колесников Игорь Игоревич Научно-исследовательская часть московского технического университета связи и информатики Российский научно-исследовательский институт космического приборостроения

Официальные оппоненты:

Ведущая организация:

кандидат технических наук, доцент

Куклев Л. П.

Общая характеристика работы

Актуальность темы. В последние годы во всем мире все более пристальное внимание привлекают к себе "беспроводные сенсорные сети" ("Sensor Networks", далее просто сенсорные сети). Основным их отличием от классических радиосетей является использование в качестве объектов сети большого числа сверхминиатюрных и дешевых устройств. Данный подход к формированию сети позволяет адаптировать сенсорные сети к решению чрезвычайно широкого спектра задач. В частности одним из основных применений сенсорных сетей является создание разнообразных систем мониторинга и контроля. Следует ожидать что в недалеком будущем сенсорные сети займут свою весьма обширную нишу среди имеющихся телекоммуникационных технологий использующих беспроводную радиосвязь.

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

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

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

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

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

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

2. Разработка математической модели алгоритма определения координат.

3. Получение соотношений для вычисления месторасположения объекта на основе информации о взаимном месторасположении объектов сети и для оценки точности вычислений.

4. Изучение влияния ошибок измерений на работу алгоритмов определения координат.

5. Оценка применимости алгоритма в существующих беспроводных сетях

стандарта IEEE 802.15.4.

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

Научная новизна диссертационной работы заключается в следующем:

1. Разработан распределенный алгоритм определения координат для применения в условиях беспроводных сенсорных сетей при наличии ошибок в измерениях расстояний.

2. Предложен новый механизм итерационной оценки координат на основе калмановской фильтрации.

3. При оценке координат аналитически учитывается точность проводимых измерений.

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

5. Разработана методика оценки эффективности работы алгоритмов определения координат в сенсорных сетях.

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

Апробация результатов работы. Основные результаты работы были обсуждены на научно-технических конференциях и семинарах:

• Международная конференция "Цифровая обработка сигналов и ее

применение", Москва, 2007 г.

• Научные семинары проводимые IEEE совместно с ЦП РНТОРЭС им. А. С. Попова "Системы синхронизации, формирования и обработки сигналов для связи и вещания" в 2007, 2008 гг.

• 63-я Научная сессия РНТОРЭС им. А. С. Попова в 2008 г.

• Московская отраслевая научно-технической конференция "Технологии информационного общества", Москва, 2005, 2007 гг.

• XLVII научная конференция МФТИ в 2005г.

• Научно-техническая конференция "Радиолокация и связь -перспективные технологии", Москва, 2007г.

Публикации. Основное содержание диссертационной работы опубликовано в 10 печатных работах (в том числе 2 статьи в журнале «Радиотехника» и 3 публикации в трудах международных конференций).

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

Объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы, включающего 96 наименований. Работа изложена на 152 страницах и содержит 54 рисунка. Основные положения, выносимые на защиту.

1. Математическая модель взаимодействия объектов сенсорной сети и ее использование для оценки координат;

2. Распределенный алгоритм определения координат на основе калмановской фильтрации;

3. Результаты исследования работы алгоритма определения координат при наличии ошибок в оценках расстояний;

4. Структурная схема малогабаритного объекта беспроводной сети с реализацией возможности определения координат.

Краткое содержание работы

Во введении рассмотрена и обоснована актуальность работы, сформулирована основная цель, научная новизна и практическая значимость результатов, приведено краткое описание структуры диссертации.

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

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

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

Учитывая потребность в радиосвязи, ориентированной на устройства с низким энергопотреблением в 2003 году организацией IEEE был принят стандарт ШЕЕ 802.15.4, в котором определены физический и канальный уровни

стека сетевых протоколов в беспроводных сетях отвечающих данным запросам. В данном документе на физическом уровне определены три диапазона частот: 868 МГц, 910 МГц, 2.4 ГГц, из которых на территории Российской Федерации доступен к использованию только диапазон 2.4 ГГц. В данном диапазоне определены 16 каналов шириной 5 МГц с несущими частотами, определяемыми из соотношения

Fc = 2405 + 5(к-1) МГц, 1,... 16. (1)

Скорость передачи в каждом канале составляет 250 кбит/с. Кроме того на

физическом уровне определены возможности включения/выключения

приемопередатчика, оценка уровня помех в канале, прием/передача данных,

оценка уровня принимаемого сигнала.

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

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

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

из указанных документов никоим образом не рассматривается, хотя в процессе работы объекта сети ему по стандарту теоретически доступна информация, указывающая на его месторасположение:

1. Содержимое таблиц маршрутизации (список близлежащих объектов сети - "соседей");

2. Оценки уровня принимаемого сигнала (по которым можно оценить расстояния до близлежащих "соседей");

3. Информация о координатах "соседей" (если таковые известны).

По этой информации можно попытаться оценить географические координаты объекта сети.

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

Применительно к сенсорным сетям следует отметить следующую специфику определения координат:

• Более высокие ошибки в оценках расстояний;

• Большая плотность сети (не 1-3, а до 10 соседей и более).

Для решения задачи поиска координат в сенсорной сети предложен ряд алгоритмов, наиболее известные из которых (APS, MDS, ABC, AFL, оснащение датчиками GPS) рассмотрены и проанализированы в первой главе диссертационной работы. Ни один из имеющихся алгоритмов не использует в чистом виде только приведенную выше информацию (см. (1)-(3)), но требует также дополнительную информацию от объектов которые не являются непосредственными соседями, что в конечном итоге создает дополнительную нагрузку на сеть. По результатам рассмотрения утверждается следующее: существующие алгоритмы не дают однозначного и универсального решения задачи определения координат в сенсорных сетях, а значит данная область

представляет интерес для проведения дальнейших научных исследований.

Вторая глава посвящена всестороннему исследованию вопросов связанных с оценкой координат по измерениям расстояний до близлежащих объектов сети.

Математическая постановка задачи определения координат в сенсорной обычно выглядит следующим образом. Допустим в некоторой области пространства £ размером 5 = АхВ случайным образом однородно распределены объекты беспроводной сенсорной сети {г}, где ¡еМ=[ 1,... М] :

в

• » ф

<3 % • • • @ в** • •

• •

♦ • • «

• •

© « * « ® Л. # * э

• © 9

в в • • •

• • « в • • —в- •

-а-

О Л

Рис. 1. Сенсорная сеть

Эти объекты имеют радиосредства, благодаря которым каждый объект может общаться и определять расстояния с! до ближайших "соседей" (объекты с которыми есть связь в радиусе Ь), при этом (исходя из способа определения расстояний) известна точность проводимых измерений. Каждый объект / собирает информацию о расстояниях до всех доступных "соседей" у и заносит ее в таблицу Т, = {/', с^}. Исходя из этих данных требуется определить координаты объектов г, . Другими словами требуется решить систему уравнений следующего вида:

к>г,М, (2)

где с/,, - измеренное расстояние от г до у, как правило содержащее погрешность

измерения описываемую распределением Е(с1у, от,), где /,у = [1, ..., М\, Щ. Как

правило, в качестве функции распределения F используется нормальное распределение N(0, а,]), при этом дисперсия ошибки измерения d определяется способом оценки расстояния, и может быть оценена априори теоретически, на основе имитационного моделирования или из эксперимента. Для удобства выкладок в данной работе предполагается двумерный случай ( г= |х, у/ , сеть развернута на плоской поверхности) - это допущение не влияет на общность приводимых рассуждений, но упрощает теоретическое рассмотрение и последующую практическую реализацию алгоритмов определения координат.

Результат решения поставленной задачи вне зависимости от алгоритма определения координат зависит от ряда начальных условий: наличия базиса СК (объектов с априори известными координатами), точности производимых измерений расстояний а, равномерности и плотности распределения объектов сети ieM .

Базис СК обычно задается набором объектов i&Q , которые могут определить свои координаты самостоятельно, например с помощью GPS. Экономически целесообразно, чтобы доля таких объектов была невелика, Q « М. Обычно предполагается 0.1 М< Q < 0.3М

Точность измерений расстояний <т зависит от способа оценки расстояния. Наиболее часто упоминаемы в литературе следующие способы:

1. Измерение расстояний на основе измерения времени распространения

сигнала от передатчика до приемника - ToA (Time-of-Arrival).

2. Измерение расстояний на основе измерения мощности принимаемого

сигнала RSSI - (Received-Signal-Strength-Indicator).

В работе исследуется возможность измерения расстояний в сети стандарта IEEE 802.15.4, поэтому для определения расстояний используется уровень принимаемого сигнала, так как все имеющиеся передатчики по стандарту аппаратно поддерживают такую возможность. Оценка расстояния

происходит из соотношения

Р(йО[дБм] = Р(Л)[дБм] - 10«logl0(flU),

(3)

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

Для оценки равномерности и плотности распределения объектов сети предлагается использовать усредненное число "соседей" для всей сети т, которое несложно определить на основе информации из таблиц маршрутизации

где М, - число соседей объекта /'. Теоретически минимально возможное значение т при фиксированных параметрах Б, М, Ь получается при максимально однородном распределении и может быть вычислено из соотношения

где 5, - область "видимости" объекта / (круг радиуса Ь с центром в точке г, ). В случае топологии сети Б^АхА при А»Ь значение тт,„ очевидно определяется по формуле

(4)

(5)

(6)

При А ~ L при взятии интеграла (5) получается выражение

_ _МттЬ2{, , т \2 , (А—£)£3 ( 5 \ 72/зтт 17\\ ,„

При этом вполне очевидно что — А/¿-»со .

Таким образом по отклонению величины т, рассчитанной на основе соотношения (4) от минимально возможного при фиксированных Б, М, Ь значения, полученного из (5)-(7) можно судить о равномерности распределения объектов сети. В данной работе рассматриваются топологии с тт„ <т< 1.6 т„,„. Дополнительно следует отметить что сама величина т в таком случае также является мерой плотности распределения объектов сети.

После того как поставлена задача поиска координат, выполнены начальные условия, требуется алгоритм, позволяющий на основе исходных данных произвести преобразование {г^}—>{?,}, «\./е[1,...М] . В данной работе предлагается такой алгоритм, обладающий следующими отличительными свойствами:

1. Каждый объект оценивает свои координаты самостоятельно, в качестве входных данных используются расстояния и координаты непосредственных близлежащих "соседей";

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

{7„Р] , (8)

где ?,=\х, У,Г . ,=|соV г,| - ковариационная матрица,

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

Для получения начальной оценки координат используется процедура триангуляции: при наличии 3-5 измерений составляется система уравнений вида , которая может быть сведена к избыточной линейной

системе уравнений вида (здесь и далее индекс текущего объекта i опущен)

Аг=В , (9)

из которой можно найти начальную оценку координат, удовлетворяющую

критерию минимума величины (Аг-В)т(Аг-В) в виде

7°=(АГА'')АТВ . (10)

После этого по мере поступления информации строится

последовательность оценок

{?VU?V}...{?",, (11)

из которой можно получить одну общую интегральную оценку координат {?", р"\ ■ Для получения такой оценки предлагается использовать процедуру калмановской фильтрации. Такой подход позволяет не хранить в условиях ограниченности ресурсов всю последовательность оценок (11), а только обновлять по мере поступления информации последнюю оценку координат.

При условии отсутствия передвижений объектов сенсорной сети соответствующие соотношения будут выглядеть следующим образом:

-«-1 г

п— 1

(12)

Р =Р

На этапе обновления при получении очередного "измерения" г" с ошибкой Г=И{г,рп) :

р"=Р"{Р"-+Р"ГР"- (13)

к=Р"-(Р"-+р"Г1

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

Третья глава посвящена всестороннему исследованию работы алгоритма определения координат на основе имитационного моделирования. При этом

исследовалась возможность оценки расстояний в беспроводной сети стандарта ШЕЕ 802.15.4 с использованием модели распространения сигнала SMRCIM (Simulation of Mobile Radio Channel Impulse-Response Models), а также была создана компьютерная модель беспроводной сенсорной сети, состоящая из следующий частей:

1. Сенсорная сеть, состоящая из набора М объектов, распределенных в прямоугольной области двумерного пространства размером АхВ;

• Объекты сети, каждый из которых через случайные промежутки времени передает и в остальное время принимает пакеты от всех близлежащих "соседей", находящихся на расстоянии не более L от него и при получении приходящих сообщений оценивает расстояние;

• Отдельные компоненты физического и канального уровня стека протоколов ШЕЕ 802.15.4 и ZigBee (ослабление сигнала, механизм доступа к общей среде).

В результате моделирования распространения сигнала были получены кривые ослабления сигнала при распространении между передатчиком и приемником в зависимости от расстояния при развертывании сети вне и внутри

Рис. 2. Ослабление сигнала Рис. 3. Ослабление сигнала

(вне помещения) (внутри помещения)

Распределение ошибок при оценке расстояний получалось при многократном

(200) повторении передачи пакета и оценке уровня принимаемого сигнала при рассматриваемом расстоянии между передатчиком и приемником. Полученные зависимости представлены на рис. 4 и рис. 5:

Рис. 4. Число битовых ошибок Рис. 5. Число битовых ошибок

(вне помещения) (внутри помещения)

По результатам моделирования дисперсия относительной ошибки измерения расстояния составляет 10 и 15 процентов при оценке расстояний вне и внутри помещения соответственно. Усредненные оценки мощности принимаемого

сигнала, полученные при увеличении расстояния показаны на рис. 6 и рис. 7:

Расстояние, ы Расстояние, ы

Рис. 6. Мощность сигнала в приемнике Рис. 7. Мощность сигнала в приемнике (вне помещения) (внутри помещения)

Таким образом при увеличении дальности все больший вклад в оценку уровня

принимаемого сигнала начинают вкладывать шумы, присутствующие в канале

передачи. Соответствующий коэффициент битовых ошибок (BER) при

(вне помещения) (внутри помещения)

Таким образом дальность связи в сетях IEEE 802.15.4 по стандарту оказывается в пределах 20 метров (при уровне передаваемого сигнала -ЗдБм).

С учетом полученных данных на основе созданной модели сети производилось имитационное моделирование работы предлагаемого алгоритма определения координат. Исследовалась беспроводная сеть, состоящая из М~ 200 объектов, развернутая внутри области S= 100x100, дальность действия каждого объекта L = 25 (соответствует уровню передаваемого сигнала ОдБм), доля объектов с известными координатами Q = 0.25М. Из соотношения (7) получается среднее число соседей ттт= 16, при распределении объектов исследовались топологии с т < 1.6тш„.

Отмечено, что при работе алгоритма средняя ошибка оценки координат при увеличении номера итерации к фильтра Калмана стремится к постоянной величине

— 1 „г _

5г=—У \r —r,\—>const, и-+со П4Ч

Mi'' ' К '

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

от номера итерации фильтра Калмана В данном случае скорость сходимости составляет порядка 30 итераций. При этом показано что величина 6 г линейно зависит от разброса ошибок измерений расстояний с/. Другой метрикой эффективности работы алгоритма определения координат является процентное соотношение числа объектов, координаты которых удалось определить за определенный интервал времени.

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

1. Размеры и топология сети (5, М, т, 0;

2. Индивидуальные характеристики отдельных объектов сети, зависящие от применяемого стандарта радиосвязи (Ь, оа).

Для этого в первую очередь варьировались величины /«(посредством изменения числа объектов сети М), ц = ()/М, о^. Результаты работы алгоритма определения координат по истечении заданного интервала времени (достаточного для прохождения к > 30 итераций фильтра Калмана у всех объектов сети) при изменении т, а при фиксированном значении 0= 0.2М

показаны на рис. 11 ирис. 12:

оценки координат в зависимости от т, а свои координаты в зависимости от т, а Результаты работы алгоритма определения координат при изменении д, а

при фиксированном значении т = 15 показаны на рис. 13 и рис. 14:

оценки координат в зависимости от д, а свои координаты в зависимости от д, а Результаты моделирования демонстрируют работоспособность предлагаемого алгоритма при выполнении начальных условий задачи, в частности более 90% объектов сети могут оценить свои координаты на основе собранной информации при от >10 и д>0.2. Полученные в результате калмановской фильтрации оценки координат сходятся к значениям координат в пределах 8г < 1 метра от реальных координат объектов сети по истечении к~30

итераций ФК. При увеличении точности измерения расстояний пропорционально увеличивается точность получаемых координат, таким образом при а^ < 5% получается 8г < 0.3.

Четвертая глава диссертационной работы посвящена аспектам практической реализации алгоритма определения координат в беспроводной сенсорной сети.

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

В результате сравнительного анализа доступных на данный момент на территории Российской Федерации приемопередатчиков стандарта ШЕЕ 802.15.4 на основе соотношений цены/харакгеристик/удобства использования для проведения экспериментальной части работы выбираются приемопередатчики ХВее-Рго производства компании (МахБйеат). Для управления приемопередатчиком выбрана плата Н5003 от фирмы ОНтех на основе процессора АЯМ7ТОМ1, который обладает достаточно высокой производительностью (до 60 МГц) при сравнительно скромном энергопотреблении (~0.1мВт/ МГц). Соединение платы с приемопередатчиком происходит через интерфейс БЮ по протоколу иАКГ. Для микроконтроллера написано программное, реализующее предлагаемый алгоритм определения координат.

При проведении эксперимента оценивалась возможность оценки расстояний по уровню принимаемого сигнала. Эксперимент производился в

течение 1 рабочего дня (3745 отсчетов) в условиях обычного офисного помещения при наличии прямой видимости. Распределение отсчетов уровня принимаемого сигнала показано на рис. 15

1400 |-1-1-1-1-1-1-1-1-

1200 -

1000 --1

й;

800 - -

600 -

400 - _

200 -

?70 -69 -68 -67 -66 -65 -64 -63 -62 -61 Р [дБм]

Рис. 15. Гистограмма распределения отсчетов уровня принимаемого сигнала

Среднеквадратическое отклонение относительной ошибки оценки расстояния (при условии п= 4) составляет 22%, что превышает данные полученные на этапе имитационного моделирования (15%). Увеличение ал обусловлено в первую очередь наличием большого числа предметов и перемещением людей, что увеличивает роль эффекта многолучевости в канале распространения. Вследствие интерференции многолучевых компонент увеличивается разброс отсчетов уровня принимаемого сигнала при фиксированном расстоянии между передатчиком и приемником.

Применительно к работе алгоритма определения координат данный результат означает (по результатам работы компьютерной модели), что для оценки координат более 90% объектов со средней точностью в пределах одного метра требуется большая плотность сети (т > 40), для оценки координат требуется от 40 до 60 итераций фильтра Калмана.

При проведении аналогичного эксперимента в условиях окружающей среды (вне помещения) разброс составляет 12%. График линейной

аппроксимации усреднённой зависимости (3) показан на рис. 16:

-48 -50 -52 -54

КС

(Л -56 ^-58 -60 -62 -64

10 11 12 13 14 15 16 17 18 10

Рис. 16. Линейная аппроксимация отсчетов ослабления сигнала в зависимости от расстояния

-По

Показатель ослабления п в данном случае составил 2.24. Следует отметить, что при слабом уровне сигнала (ниже -85 дБм) сильное влияние на количество ошибок оказывает взаимное расположение модулей и окружающих предметов. Таким образом несмотря на заявленную дальность связи более одного километра, адекватные оценки расстояния по уровню принимаемого сигнала возможны на расстояниях до 80 метров (при уровне передаваемого сигнала 0 дБм).

В данном случае предлагаемый алгоритм определения координат является работоспособным при развертывании сети вне помещения при условии т~ 15,

В заключении приводятся основные результаты и выводы диссертационной работы.

2 > 0.2М

Основные результаты работы

1. Предложен алгоритм определения координат в беспроводных сенсорных сетях, который может использоваться в сетях стандарта IEEE 802.15.4 при условии развертывания сети вне помещения.

2. Исследованы критерии оценки работоспособности и применимости алгоритмов определения координат в сенсорных сетях.

3. Разработан комплекс специализированных программ для отработки и оценки поведения алгоритмов определения координат в сенсорных сетях на основе имитационного моделирования. На базе данного программного комплекса реализован предлагаемый алгоритм определения координат.

4. Получены качественные показатели работы предлагаемого алгоритма при изменении плотности сети и при возможном улучшении точности измерений расстояний.

5. Предложен опытный образец малогабаритного устройства с реализацией функции определения координат в сети подобных устройств.

Список работ, опубликованных по теме диссертации

1. Иванов Е.В., Козлов В.Н., Курикша В.А. "Оценка точности измерения расстояний между узлами в распределенной сенсорной радиосети стандарта IEEE 802.15.4" // "Радиотехника" (журнал в журнале), №10, 2006, стр. 13-16 ("Радиолокация и связь")

2. Иванов Е.В., Козлов В.Н., Курикша В.А. "Экспериментальное определение ошибки измерения расстояний между устройствами стандарта IEEE 802.15.4/ZigBee" // "Радиотехника" (журнал в журнале), №10, 2008 ("Радиолокация и связь")

3. Иванов Е.В., Козлов В.Н., Курикша В.А. "Алгоритм определения координат в беспроводной сенсорной сети" // Труды 8-й Международной научно-технической Конференции "Цифровая обработка сигналов и ее применение", Москва, 2007

4. Иванов Е.В., Козлов В.Н., Курикша В.А. "Экспериментальное определение координат в сетях стандарта ШЕЕ 802.15.4" // Труды 63-й научной сессии РНТОРЭС им. A.C. Попова, Москва, 2008, стр. 471-473

5. Иванов Е.В., Козлов В.Н., Курикша В.А. "Определение координат в сенсорной сети с помощью фильтра Калмана" // Труды семинара "Системы синхронизации, формирования и обработки сигналов для связи и вещания", Одесса, 2007, стр. 116-120

6. Иванов Е.В., Козлов В.Н., Курикша В.А. "Алгоритм определения координат в беспроводной сенсорной сети" // Межотраслевая конференция "Технологии информационного общества", Москва, 2007, стр. 79

7. Иванов Е.В., Козлов В.Н., Курикша В.А. "Задача определения координат в беспроводных сетях стандарта IEEE 802.15.4/ZigBee" // Труды семинара "Системы синхронизации, формирования и обработки сигналов для связи и вещания", Ярославль, 2008, стр. 88-90

8. Козлов В.Н., Филимонов H.H., Иванов Е.В. "Методы определения

месторасположения распределенных объектов в беспроводной сети" // Научная конференция профессорско-преподавательского, научного и инженерного состава МТУСИ, Москва, 2005 9. Иванов Е.В., Козлов В.Н., Курикша В.А. "Методы определения координат распределенных объектов в беспроводной сети" // Труды 47-й научной конференции МФТИ, Долгопрудный, 2005 Ю.Иванов Е.В., Козлов В.Н., Курикша В.А. "Сравнительный анализ алгоритмов позиционирования объектов в сенсорных сетях" // Научно-техническая конференция "Радиолокация и связь - перспективные технологии", Москва 2007

Заказ Л» 279/10/08 Подписано в печать 30.10.2008 Тираж 70 экз. Усл. п л. 1,5

ООО "Цифровнчок", тел. (495) 797-75-76; (495) 778-22-20 www.cfr.ru; e-mail:info@cfr.rn

Введение.

Глава 1. Определение координат.

1.1. Беспроводные сенсорные сети.

1.2. Организация беспроводной связи.

1.2.1. Сверхширокополосные сигналы (UWB).

1.2.2. Стандарт IEEE 802.15.4/ZigBee.

1.2.2.1. Топологии сети IEEE 802.15.4/ZigBee.

1.3. Определение координат в сенсорных сетях.

1.3.1. Постановка задачи.

1.3.2. Обзор наиболее популярных вариантов решения.

1.3.2.1. Использование внешней радионавигационной системы.

1.3.2.2. Система "APS" [19].

1.3.2.3. Алгоритм "MDS-MAP" [16].

1.3.2.4. Алгоритм "ABC" [18].

1.3.2.5. Алгоритм "AFL" [13].

1.4. Выводы.

Глава 2. Определение координат в сенсорной сети.

2.1. Начальные условия.

2.1.1. Базис СК в сенсорной сети.

2.1.2. Топология сети.

2.1.3. Точность оценки расстояний в сети IEEE 802.15.4/ZigBee.

2.1.3.1. Передатчик.

2.1.3.2. Канал.

2.1.3.3. Приемник.

2.2. Алгоритм определения координат.

2.2.1. Сбор исходных данных.

2.2.2. Оценка координат.

2.2.3. Уточнение координат.

2.2.3.1. Применение фильтра Калмана.

2.2.4. Оценка координат по двум измерениям.

2.2.4.1. Выбор решения.

2.3. Выводы.

Глава 3. Имитационная модель.

3.1. Модель сенсорной сети.

3.2. Модель объекта сети.

3.2.1. Физический уровень.

3.2.2. Канальный уровень.

3.2.3. Сетевой уровень.

3.3. Результаты моделирования.

3.3.1. Оценка расстояний.

3.3.2. Оценка координат.

3.4. Выводы.

Глава 4. Экспериментальная часть.

4.1. Построение миниатюрного объекта беспроводной сенсорной сети.

4.1.1. Приемопередатчики стандарта IEEE 802.15.4/ZigBee.

4.1.2. Приемопередатчики XBee-Pro (MaxStream) [27].

4.1.3. Плата Olimex Н5003.

4.1.4. Датчики физических параметров окружающей среды.

4.2. Физический эксперимент.

4.3. Выводы.

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

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

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

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

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

1. вопросы связанные с организацией работы сети;

2. разработка программного обеспечения;

3. учёт ограничений по электропитанию при работе сети;

4. привязка месторасположения объектов к географическим координатам;

5. синхронизация внутренних часов отдельных объектов и др.

Кроме того, помимо сугубо научного теоретического интереса уже имеют место быть и конкретные практические шаги направленные к созданию и продвижению данной концепции. Здесь следует отметить факт стандартизации нижних уровней стека сетевых протоколов для использования в беспроводных сетях с малым энергопотреблением: принятие в 2003 году международного стандарта IEEE 802.15.4 [1] (физический и канальный уровни), а также набор спецификаций ZigBee [2] (сетевой уровень). Благодаря этому к настоящему времени уже целый ряд фирм выпускает готовые устройства, на основе которых уже можно создавать прототипы беспроводных сенсорных сетей.

Кроме документов [1] и [2] также следует отметить возможность организации беспроводной сенсорной сети на основе сверхширокополосных (Ultra-Wide Band, UWB) приёмопередатчиков. Данная возможность доступна только теоретически, т.к. соответствующий документ IEEE 802.15.4а так и не был принят в качестве стандарта. Тем не менее вне зависимости от формального статуса данная технология представляет интерес с точки зрения организации беспроводной радиосвязи в сенсорной сети. Поэтому технологии UWB также уделяется внимание в данной работе.

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

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

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

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

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

Для достижения поставленной цели должны быть решены следующие задачи:

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

2. Разработка математической модели алгоритма определения координат.

3. Получение соотношений для вычисления месторасположения объекта на основе информации о взаимном месторасположении объектов сети и для оценки точности вычислений.

4. Изучение влияния ошибок измерений на работу алгоритмов определения координат.

5. Оценка применимости алгоритма в существующих беспроводных сетях стандарта IEEE 802.15.4.

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

Научная новизна диссертационной работы заключается в следующем:

1. Разработан распределённый алгоритм определения координат для применения в условиях беспроводных сенсорных сетей при наличии ошибок в измерениях расстояний.

2. Предложен новый механизм итерационной оценки координат на основе калмановской фильтрации.

3. При оценке координат аналитически учитывается точность проводимых измерений.

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

5. Разработана методика оценки эффективности работы алгоритмов определения координат в сенсорных сетях.

Практическая ценность. Создан комплекс компьютерных программ для моделирования поведения беспроводной сенсорной сети, а также для моделирования работы алгоритмов определения координат. В составе комплекса реализована методика оценки эффективности работы алгоритмов определения координат. Создан малогабаритный макет мобильного беспроводного устройства на базе приёмопередатчика стандарта IEEE 802.15.4. В процессе работы использовалось только ПО с открытым исходным кодом.

Апробация результатов работы. Основные результаты работы были обсуждены на научно-технических конференциях и семинарах:

• Международная конференция "Цифровая обработка сигналов и ее применение" в 2007 г.

• Научные семинары проводимые IEEE совместно с ЦП РНТОРЭС им. А. С. Попова "Системы синхронизации, формирования и обработки сигналов для связи и вещания" в 2007, 2008 гг.

• 63я Научная сессия РНТОРЭС им. А. С. Попова в 2008 г.

• Московская отраслевая научно-технической конференция "Технологии информационного общества" в 2005, 2007 гг.

• XLVII научная конференция МФТИ в 2005г.

• Научно-техническая конференция "Радиолокация и связь — перспективные технологии" в 2007г.

Публикации. Основное содержание диссертационной работы опубликовано в 10 печатных работах (в том числе 2 статьи в журнале «Радиолокация и связь» и 3 публикации в трудах международных конференций).

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

Объем работы. Работа состоит из введения, четырех глав, заключения, списка литературы, включающего 97 наименований. Объем работы составляет 148 страниц текста, работа содержит 54 рисунка.

Основные положения, выносимые на защиту.

1. Математическая модель взаимодействия объектов сенсорной сети и её использование для оценки координат;

2. Распределённый алгоритм определения координат на основе калмановской фильтрации;

3. Результаты исследования работы алгоритма определения координат при наличии ошибок в оценках расстояний;

4. Структурная схема малогабаритного объекта беспроводной сети с реализацией возможности определения координат.

Краткое содержание работы Во введении рассмотрена и обоснована актуальность работы, сформулирована основная цель, научная новизна и практическая значимость результатов, приведено краткое описание структуры диссертации.

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

Вторая глава посвящена всестороннему исследованию вопросов связанных с оценкой координат на основе измерений расстояний до близлежащих объектов сети применительно к беспроводным сенсорным сетям.

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

В третьей главе на основе разработанного комплекса программ, проводится исследование точности измерений расстояний по уровню принимаемого сигнала в сетях стандарта IEEE 802.15.4, а также моделируется работа целой сенсорной сети и исследуется поведение предлагаемого алгоритма в зависимости от плотности сети, доли объектов с известными координатами, точности производимых оценок расстояний. Дается качественная и количественная интерпретация получаемых результатов, на основе которых делаются выводы о возможности использования предлагаемого алгоритма определения координат в беспроводных сенсорных сетях с радиочастью стандарта IEEE 802.15.4.

Четвертая глава посвящена аспектам технической реализации малогабаритного объекта беспроводной сети со встроенной возможностью определения координат, представляющую собой программную реализацию предлагаемого в данной работе алгоритма. Для создания объекта используется приёмопередатчик стандарта IEEE 802.15.4 и управляющая плата на основе микроконтроллера ARM7TDMI.

В заключении приводятся основные результаты и выводы диссертационной работы.

Основные результаты работы заключаются в следующем:

1. Предложен алгоритм определения координат в беспроводных сенсорных сетях, который может использоваться в сетях стандарта IEEE 802.15.4 при условии развертывания сети вне помещения.

2. Исследованы критерии оценки работоспособности и применимости алгоритмов определения координат в сенсорных сетях.

3. Разработан комплекс специализированных программ для отработки и оценки поведения алгоритмов определения координат в сенсорных сетях на основе имитационного моделирования. На базе данного программного комплекса реализован предлагаемый алгоритм определения координат.

4. Получены качественные показатели работы предлагаемого алгоритма при изменении плотности сети и при возможном улучшении точности измерений расстояний.

5. Предложен опытный образец малогабаритного устройства с реализацией функции определения координат в сети подобных устройств.

6. При проведении диссертационной работы использовалось только программное обеспечение с открытым исходным кодом.

Заключение

1. : IEEE, "Wireless Medium Access Control (MAC) and Physical Layer (PHY)

2. Networking", Изд-во "John Wiley & Sons", 20046.: B.C. Шебшаевич, "Сетевые спутниковые радионавигационные системы", Издво "Радио и связь", 1993 7.: Mohinder S. Grewall, Lawrence R. Weill, Angus R. Andrews, "Global Positioning

3. Distributed Localization in Sensor Networks", 200314.: Archana Bharathidasan, Vijay Anand Sai Ponduru, "Sensor Networks: An 1. Overview", 2003 15.: Ivan Stojmenovic, "Handbook of Sensor Netowks: Algorithms and Architectures",

4. Power as Distance Estimation forPrecise Localization in Sensor Networks", 200640.: J. Benedicto, S.E.Dinwiddy, G. Gatti, R. Lucas, M. Lugert, "GALILEO: Satellite

5. Synchronization Scheme", 200647.: SHI Qin-Qin, HUO Hong, FANG Tao, LI De-Ren, "Using Linear Intersection for

6. Bound for Localization Algorithms", 200853.: Neal Patwari, Alfred O. Hero, Josh Ash, Randolph L. Moses, Spyros Kyperountas,

7. Usingan UWB Radio Link", 200256.: Farid Benbadis, Timur Friedman, Marcelo Dias de Amorim, Serge Fdida, "GPS

8. Tracking a Maneuvering Target Using a Network of Wireless Dynamic Sensors", 200869.: Konrad Lorincz, David J. Malan,Thaddeus R.F. Fulford-Jones, Alan Nawoj, Antony

9. Clavel, Victor Shnayder, Geoffrey Mainland, Matt Welsh, Steve Moulton, "Sensor

10. Environmental Sensing-System", 200793.: Steven M. Kay, "Fundamentals of Statistical Signal Processing: Estimation

11. Architecture for Exploring Distributed Sensor Network Applications", 200497.: "Музей сенсорных сетей", http://www.btnode.ethz.ch/Projects/SensorNetworkMuseum