Topology Control. Coverage. Localization. Time Synchronization. Садков Александр Аспирант РФ axel@wl.unn.ru Сайт курса: - презентация

1 Topology Control. Coverage. Localization. Time Synchronization. Садков Александр Аспирант РФ Сайт курса:

2 План Введение Контроль топологии сети (Topology Control) Зона покрытия (Sensing Coverage) Локализация (Localization) Временная синхронизация (Time Synchronization) Заключение

3 Topology Control Вопросы размещения узлов Вариант 1: Случайное расположение Какие свойства связности и зоны покрытия в случайном графе? Вариант 2: Структурированное размещение Как и где расположить узлы, чтобы обеспечить необходимую связность и зону покрытия при этом сделать энергетические затраты минимальными?

4 Topology Control Вопросы контроля топологии сети Использование плотности размещения. При данной плотности размещения, когда не все узлы требуются для создания связанной топологии, каким сделать duty-cycle узлов для сохранения энергии. Методология Эмпирическая адаптация (ничего не известно о первоначальном разположении узлов) Аналитическая адаптация (подразумевается что известна плотность/расположение)

5 Случайное размещение узлов

6 Topology Control Связность сети Идеализированная геометрическая модель для беспроводных каналов: полная слышимость в пределах радиуса R Граф сети G формируется узлами как вершинами графа и каналами между узлами как гранями графа. Основное понятие связности: если существует хоть один multi-hop пусть между парой любых узлов, то сеть является связанной.

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

8 Topology Control Случайные графы Случайный граф Бернулли G(n,p): грань между любой парой из n узлов существует независимо с вероятностью p. Геометрический случайный граф G(n,R): n узлов расположены с равномерным случайным распределением на конечной территории, грань между любой парой узлов существует в пределах радиуса R.

9 Topology Control Фазовый переход в связности

10 Guest Speaker Константин Мишагин

11 Topology Control Если цель – построить связанную сеть при плотном размещении узлов, доастаточно использовать только небольшое их количество (остальные могут находиться в спящем состоянии). Необходимо гарантировать достаточную плотность узлов в активном состоянии в данный момент времени, чтобы сеть была полностью связанной.

12 Topology Control Почему мы должны делать сети с высокой плотностью? Позволяет повысить надежность сети и добиться устойчивости к отказам. Не всегда возможно провести дополнительное размещение узлов. Слишком дорого размещать узлы по требованию (когда другие узлы умирают) Может быть необходимо для достижения достаточной зоны покрытия измеряемого явления. Сенсоры более эффективны, когда они близко расположены к измеряемому явлению. Измерение из нескольких точек дает больше возможностей.

13 Topology Control Основная идея. Найти набор узлов из k узлов, который обеспечит необходимую зону покрытия. Менять узлы, чтобы хотя бы k из них были в активном состоянии, а остальные в спящем. Minimal Connected Dominating Set (MCDS) Находится доминирующий набор, затем находится подмножество узлов, которые соединяют все узлы в доминирующий набор. AFECA, GAF, CEC, Span Оценка плотности Поиск подмножества узлов, которые обеспечивают определенный порог плотности. ASCENT, PEAS. Гибридные STEM

14 ASCENT: Adaptive Self-Configuring sEnsor Networks Topologies. Alberto Cerpa and Deborah Estrin UCLA

15 ASCENT: Adaptive Self-Configuring sEnsor Networks Topologies Различные приложения могут требовать, чтобы топология сети имела различные характеристики. Минимальная. Гомогенная с определенной степенью связности. Гетерогенная с различной связностью в разных районах. Примерами таких районов могут быть: На пути информационных потоков. Избегая путей информационных потоков. На границе наблюдаемого явления. Цель – использовать избыточность в системе (высокую плотность), чтобы сохранить энергию предоставляя топологии адаптироваться для нужд конкретных приложений.

16 ASCENT: Adaptive Self-Configuring sEnsor Networks Topologies Связность – очень сложная вещь в реальном мире. Многолучевые эффекты, ассиметричность каналов и пр. не позволяют создать точную радио модель. ASCENT использует эмпирическую адаптацию. Каждый узел оценивает связность и подстраивает свое участие в топологии сети. ASCENT только нужно выключить радио (sleep state) и иметь возможность перевести NIC/MAC в смешанный режим (passive state) ASCENT работает между MAC уровнем и уровнем маршрутизации. Он не зависит от использоваемого протокола маршрутизации и не использует информацию собранную на сетевом уровне.

17 ASCENT: Adaptive Self-Configuring sEnsor Networks Topologies Узел может находится либо в активном либо в пассивном состоянии. В активном состоянии узел принимает участие в маршрутизации пакетов. Узел в пассивном состоянии может «спать» или проводить измерение параметров сети. Не маршрутизирует сообщения. Каждый узел знает количество своих соседей и локально измеряет потери пакетов. Каждый узел принимает решение включиться в топологию сети или произвести некоторую адаптацию (уменьшить duty-cycle для сохранения энергии)

18 ASCENT: Adaptive Self-Configuring sEnsor Networks Topologies

19 Каждый узел добавляет порядковый номер (sequence number) в каждый пакет, что позволяет определить потери пакетов. Оценка количества соседей: neighbor loss threshold (NLT) = 1- 1/N (N- число соседей в предыдущем цикле. Значение neighbor threshold (NT) определяет средний уровень связности сети. The loss threshold определяет максимальное количество потерь данных, которое зависит от конкретного приложения. Отношение Tp/Ts (passive/sleep timers) определяет затраты энергии и отклик системы на динамические изменения.

20 ASCENT: Adaptive Self-Configuring sEnsor Networks Topologies

21 Достоинства. Эмпирическая подстройка повышает надежность работы сети. Недостатки. Высокие накладные расходы (справедливо для всех адаптивных схем управления топологией). Много параметров настройки сети, влияние которых на поведение системы не совсем ясно. Neighbor threshold, loss threshold, neighbor loss threshold, итд.

22 Структурное размещение и зона покрытия

23 Модели покрытия сети. Круговая модель Сенсоры с угловым покрытием Поиск наиболее оптимального расположения узлов в условиях следующих ограничений: Зона покрытия. Зона радиокорытия (связность) Стратегия сбора данных.

24 Структурное размещение и зона покрытия Ограничения Зона покрытия. Область измерения должна быть покрыта сенсорами. Определенные точки покрытия. Постоянный мониторинг. Радиопокрытие. Необходимо создать связанную топологию. Характеристики области размещения.

25 Структурное размещение и зона покрытия Круговая модель Событие может быть зарегистрировано только в пределах радиуса R от сенсора. Подобно круговой модели радиопокрытия. SNR падает с расстоние, на некотором расстояние он становится ниже границы обнаружения. Акустические, вибрационные (сейсмические) события. Проблема покрытия: Как расположить узлы, чтобы каждая точка была покрыта хотя бы одним сенсором (кругом).

26 Структурное размещение и зона покрытия Угловая модель Каждый сенсор имеет ограниченную зону видимости по углу. Камера, радар. Проблема покрытия: Как расположить и ориентировать разные узлы, чтобы покрыть определенный район.

27 Структурное размещение и зона покрытия В каких случая круговая/угловая модель применима? Источник точечный и SNR затухает с расстоянием. Когда сенсор не может зарегистрировать сигнал если расстояние больше R (SNR слишком мало): Камера, Радар. 1/0 модель: Либо детектирует, либо нет. В каких случая круговая/угловая модель не применима? При измерении пространственно меняющихся явлений (температура, погода). Зависит от приложения. Что делать, чтобы определить зону покрытия для непрерывно меняющихся явлений.

28 Структурное размещение и зона покрытия Voronoi Diagram Вход: Набор точек на плоскости. Выход: Плоскость разделенная на ячейки. Каждая ячейка содержит все наиближайшие точки к определенному узлу.. Построение Проводятся средние линии, отделяющие узел от всех других. Voronoi Diagram – это пересечение всех полуплоскостей.

29 Структурное размещение и зона покрытия Maximal breach path: путь, который максимизирует наилучшее приближение к любому узлу. Maximal support path: путь, который минимизирует максимальное расстояние к любому узлу. S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M.B. Srivastava, Coverage problems in wireless ad-hoc sensor networks, INFOCOM 2001.

30 Структурное размещение и зона покрытия

31 Localization

32 Что такое локализация? Механизм для определения пространственного соотношения между объектами. Почему локализация важна? Фундаментальное требование для многих сервисов (географический роутинг и пр.) Локализация придает данным с сенсоров физический смысл. Температурные данные – температурная карта области. Трекинг цели

33 Localization Базовые принципы Проблемы локализации: Технологии: RSSI / Акустические / Ультразвуковые Оценка ориентации при использовании акустических методов. Эффект Beacon Geometry на ошибки Распределенная multi-hop локализация

34 Localization Базовые станции рассылают свои координаты и посылают опорный сигнал. PDA по опорному сигналу оценивает расстояние до каждой базовой станции. Расстояние оценивается с ошибкой.

35 Localization Определение расстояния и Локализация Как точно оценить расстояние? Можно ли локализовать, без точнойй оценки расстояния? Ориентация Как оценить направление? Топология Влияние расположения маяка (beacon). Multi-hop Расширение простой триангуляции на multi-hop случай.

36 Localization RSSI Сигнал затухает линейно с логарифмом расстояния S=S 0 + n*log (d) d i =sqrt ((x i – x 0 ) 2 + (y i – y 0 ) 2 ) Используя триангуляцию, находим координаты точки. Но в реальной жизни все гораздо сложнее! шум, многолучевой распространение, отражения и пр.

37 Localization Acoustic / UltraSound Acoustic Mote UCB/UCLA MIT Cricket Project Ultrasound Localization UCLA NESL MK-II Ultrasound Localization

38 Localization Acoustic / UltraSound Достоинства. Невысокая скорость распространения сигнала – легкое измерение времени распространения (ToF) Точная синхронизация достигается посылкой Радио сигнала. Недостатки Датчики потребляют много энергии Необходима прямая видимость. Звуковой диапазон имеет ряд преимуществ, но не всегда подходит. Обвчно используется ультразвук.

39 Localization Acoustic / UltraSound Радио сигнал используется для синхронизации приемника и передатчика. Акустический сигнал посылается передатчиков и принимается микрофоном. Расстояние определяется по разнице времени приема Радио и Акустивеского сигналов.

40 Localization Acoustic / UltraSound Ошибка определения зависит от расстояния и угла приема.

41 Localization Определение направления Система с несколькими акустическими каналами приема. Разница времен прихода сигнала по разным каналам определяет угол приема сигнала.

42 Localization Расположение маяков Какие три маяка дадут наименьшую ошибку ?

43 Хорошое расположение маяков Localization Расположение маяков

44 Плохое расположение маяков Localization Расположение маяков

45 Важно не расстояние, а угол под которыми расположены маяки.

46 Временная синхронизация

47 Временная синхронизация в Беспроводных Сенсорных Сетях Обнаружение событий (event) Как много транспорта прошло по шоссе за время t. Необходимая точность 1 сек. Совместная обработка данных Определение цели с точностью 1см использую разницу прихода акустического сигнала. Необходимая точность 1мс. Duty-Cycling Точная информация о времени перехода соседних узлов в спящий режим и обратно. Необходимая точность 1 мкс.

48 Временная синхронизация

49 NTP (Network Time Protocol): Используется в Интеренете GPS: микросекундная синхронизация. WWVB и другие системы передачи сигналов точного времени. Высоко стабильные осцилляторы ( Рубидий, Цезий).

50 Временная синхронизация NTP: Золотой стандарт используемый миллионами. Особенности: Синхронизирует часы на компьютерах и роутерах в сети Интернет. Обеспечивает субмиллисекундную синхронизацию в LAN, и десятки миллисекундр в Wi-Fi. Разработан чтобы уменьшить джиттер, влияние множества источников и избежать некоректной работы серверов. Более NTP точек синхронизации распределенных по всему Интернету.

51 Временная синхронизация Необходимая точность. Интернет приложения: 1 мс Сенсорные сети: 1 сек – 1 мкс Ограниченные ресурсы: Интернет: Ресурсы не ограничены. Можно усреднять ошибку используя передачу множества пакетов. Сенсорные сети: Энергия. Нужно использовать небольшое количество пакетов. Источники неопределенности. Интернет: Высокие. Очереди в роутерах, загрузка сети, различные скорости обработки на хостах и пр. Сенсорные сети: Низкие. В основном синхронизация в пределах одного hop.

52 Временная синхронизация Использование GPS Достоинства. Высокая точность: нс. Надежность. Недостатки: Не работает в помещениях, под водой и т.д. Если что-то произошло, восстановление занимает долгое время (30 мин). Дорого. Энергетически затратно.

53 Временная синхронизация Использование Сигналов Точного времени Периодически посылает время используя мощные передатчики. Недостатки: Специальный приемник. Невысокая точность (типичное значение 0.5 сек). Частые сбои.

54 Временная синхронизация

55 Временная синхронизация Ошибки измерения

56

57 Временная синхронизация Синхронизация приемник-приемник Основная идея: Использование стороннего передатчика, для синхронизации приемников.

58 Временная синхронизация Синхронизация приемник-передатчик

59 Временная синхронизация Временная рассинхронизация

60 Временная синхронизация Multi-hop synchronization Задача может быть разделена на несколько подзадач R-R и S-R синхронизации. Комбинируя разные источники информации может дать лучшую синхронизацию точка- точка.

61 Временная синхронизация Multi-hop synchronization

62 Заключение Контроль топологии сети (Topology Control) Зона покрытия (Sensing Coverage) Локализация (Localization) Временная синхронизация (Time Synchronization)

63 Литература Localization in Sensor Networks A. Savvides, L. Girod, M. Srivastava, and D. Estrin, Book Chapter, Wireless Sensor Networks, Edited by Znati, Radhavendra and Sivalingam.Localization in Sensor Networks Power-Efficient Sensor Placement and Transmission Structure for Data Gathering under Distortion Constraints D. Ganesan, R. Cristescu and B. Berefull-LozanoPower-Efficient Sensor Placement and Transmission Structure for Data Gathering under Distortion Constraints Coverage in wireless ad hoc sensor networks X. Li, P. Wan, and O. FriederCoverage in wireless ad hoc sensor networks Impact of Heterogeneous Deployment on Lifetime Sensing Coverage in Sensor Networks, Jae-Joon Lee, Bhaskar Krishnamachari, C.C. Jay KuoImpact of Heterogeneous Deployment on Lifetime Sensing Coverage in Sensor Networks, Topology Control for Wireless Sensor Networks J. Pan, Y.T. Hou, L. Cai, Y. Shi, and S.X. ShenTopology Control for Wireless Sensor Networks

64 The End