close

Вход

Забыли?

вход по аккаунту

?

knotted flowlines

код для вставкиСкачать
Хомологични методи за
сензорни мрежи
Роберт Грист
Department of mathematics
University of Illinois
Urbana-Champaign, USA
joint work with V. de Silva [Pomona College]
сензори & сензорни възприятия
цел: да усетиш средата
днес:
един/малко скъпи,
силни, глобални
сензори
утре:
Множество
евтини,слаби,
локални сензори
задача: Да се интегрират данните от локалните сензори в
обща глобална картина?
Теза: топологията е точното сердство за локално → глобално
Една аналогия
хомологията превръща локалните комбинаторни данни
в глобални данни за алгебричната
топология на пространствата
Какво е хомологията?
Симплициален комплекс X
хомология
Hk(X) k=0,1,2...
хомологията превръща локалните комбинаторни данни
в глобални данни за алгебричната
топология на пространствата
Проблем за покритията
Възли с радиално симетрично възприемане / комуникация
приложение:
Комуникация
Сигурност и наблюдение
Роботика и
Навигация в
корабоплаването
цел: да се реши проблема с невидимите полета
Предположения относно мрежата
A1 : възлите излъчват единствено id към всеки в радиус radius rb
A2 : симетрични области на покритие с радиус rc> rb /√3
A3 : компактна полигонална област D в R2
A4 : специални възли от оградата
дефинират ∂D
rc
rb
Какво е известно на мрежата...
Аз съм възел #11
Свързан съм с възли
6,7,13,22
Аз съм възел #8
Свързан съм с възли
1,6,11,18,22
Аз съм възел #6
Свързан съм с възли
2,7,8,11,13
Не съм от оградата
Не съм от оградата
Аз съм от оградата
Аз съм възел #18
Свързан съм с възли
1,5,7,8
Аз съм възел #1
Свързан съм с възли
8,18
Аз съм възел #22
Свързан съм с възли
2,3,11,17,21,23
Не съм от оградата
Аз съм от оградата
Не съм от оградата
За геометрията на областта не знаем нищо освен
размерността (=2)
Сензори и симплекси
Класически инструмент: комплекса на Чех на покритието (нерва)
k-симплексите съответстват на k припокриванията
Теорема на Чех: Комплекса на Чех има хомотопиченния тип
на покритието
Как да извлечем инфо за построяване на комплекса на Чех?
За съжаление, комплекса на Чех зависи от точните
Растояния между възлите...
rb
Какво можем да забележим в данните на сензорите?
Очевидната част...
графа на комуникацията
ръбовете съответстват на комуникационните връзки
Изчислими са
на хардуерно ниво...
...но не знаем как са разположени в равнината
Не толкова очевидната част...
Комплекса на Рипс-Виеторис R
Допълваме графа до максимален симплициален комплекс
Конструкцията идва
от геометричната
теория на групите...
Подкомплекса на оградата F съответства на ∂D
Критерий за хомологично накритие
теорема: При условия A1-A4, кръговете с радиус rc покриват областта
ако съществува генератор на H2(R ,F) с неизчезваща граница
интуиция:
Генераторът изглежда като
покривка от триъгълници,
които попълват
границата на областта
Да внимаваме за фалшиви генератори
Числата на Бети [ранговете на хомологичните групи]
не са достатъчни за покриване...
Тези образуват октаедър и
Рийбс граф
Генератор е за H2 но има
изчезваща граница
Хипотеза за релативното накритие
Възли в компактна област D в Rd
Възлите имат уникални id номера които те излъчват
Възлите могат да разпознават сигнали и да ги различават
Силен сигнал
|xi - xj| ≤ rs
Слаб сигнал rs < |xi - xj| ≤ rw
Възлите имат накриваща област с радиус rc
rw ≥ rs√10
rc ≥ rs√2
Хипотеза за релативното накритие
Възлите могат да разпознаят оградата ∂D на растояние rf
Възли на оградата
Подкомплекс на
оградата
Rs
Rw
Fs
Fw
Хипотеза за релативното накритие
Предполагаме, че D не е много “накъдрена”
Предполагаме, че D не е “продупчена”: D-C е свързано
C = яка с радиус rf + rs√2
В резюме
Хомологичния критерий за накритие
Дава свидетелство
Изчислим е
Приложим е за широк кръг от проблеми
топологията като кутия с инструменти
“превръщане на безпорядъчен облак в хубав облак от данни”
Документ
Категория
Презентации
Просмотров
2
Размер файла
785 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа