Sistemas de Localização
baseados em 802.11
Fernando Ney da Costa Nascimento
[email protected]
Roteiro
Motivação
 Aplicações
 Alternativas e Problemas
 Localização baseada em 802.11

Metodologia
 Algoritmos


Conclusões
Motivação
Crescente aumento de comunicação sem fio
 Pré-requisito para serviços baseados em
localização
 Soluções tradicionais não funcionam

Aplicações

Location-Awareness




Segurança


Localização de Pessoas
Dispositivos Inteligentes
Roteamento Wireless
Localização de intrusos
Robôs Móveis



Exploração
Construção automática de mapas
Navegação
Propriedades de Sistemas de
Localização








Posição Física x Simbólica
Localização Absoluta x Relativa
Localização Remota ou Auto-Localização
Exatidão e Precisão
Escala
Reconhecimento de dispostivos
Custo
Limitações
Alternativas

Outdoor


GPS
Indoor
Infrared (IR)
 Radio Frequency (RF)

GPS
Altamente disseminado
 Cada vez mais baratos
 Não funcionam em ambientes indoor

Infra-Vermelho
Grande precisão (curtas distâncias, linha
reta entre emissor e receptor)
 Baixa escalabilidade
 Requer hardware especializado
 Ex: Active Badge

Rádio Frequência
Granularidade a nível de célula
 Alta Escalabilidade
 Não requer hardware especializado

Problemas com propagação de
sinais Indoor







Propagação não linear
Ruído
Propagação Multi-Caminho
Interferência
Absorção
Temperatura do ar
Absorção por pessoas (freqüência resonante da
água)
Localização baseada em 802.11
Hardware já presente no ambiente
 Custo reduzido
 Complexidade reduzida

Ideía

Usar medidas de força do sinal para
determinar a localização.
Categorias
Técnicas Determinísticas
 Técnicas Probabilísticas

Algoritmos para Localização

Fase 1: Geração dos dados – Construção de
um espaço de busca.
Geração por modelos de propagação
 Geração empírica


Fase 2: Recepção de um dado real e busca
da posição nos dados gerados na fase 1.
Busca probabilística
 Busca por diferença/semelhança

Técnicas de Localização
Representação do Espaço
 Representação do Sinal
 Algorimtos de Inferência de Localização

Representação do Espaço
Representação da localização e direção
Representação do Sinal
Ponto de Acesso
Valor do sinal medido
Algoritmos de Inferência
Nearest Neighbor
 Multiple Nearest Neighbor
 Modelo de Propagação de ondas de rádio
 Kernel Method
 Histogram Method
 Inferência Probabilística

Nearest Neighbor (CHOICE,
RADAR)
A localização é determinada usando um
função de distância.
 Ex.: Distância Euclidiana


Resolução de 3.20 metros em média
Multiple Nearest Neighbor
(RADAR)

São considerados as k amostras mais
“perto”.

Resolução de 2.75 (k=5)metros em média
Multiple Nearest Neighbor
(cont.)

Escolha de k
k pequeno melhora, mas não significativamente
 k grande piora,pois pontos distantes são levados
em consideração
 k não melhora significativamente porque são os
mesmos pontos com diferentes orientações

Modelo de propagação de ondas
de rádio
Usado para determinar as amostras
 Teórico x Empírico
 Diversos modelos de propagação
 Resultados variáveis devido a propagação
de sinais em ambientes indoor
 Reduz a dependência de dados empirícos

Modelo de propagação de ondas
de rádio
• Resolução de 4.3 metros em média
Regra de Bayes
• Função de Probabilidade
• Probabilidade Anterior
• Distribuição Posterior
Kernel Method (Ekahau)
Regra de Bayes
 Distribuição posterior
 Uso de distribuição Gaussiana

Kernel Method
• Função de Probabilidade
Kernel Method
Histogram Method (Ekahau,
Rover, Nibble)
• Função de Probabilidade
• Determinada através de caixas
• Caixas com tamanhos diferentes ou
iguais
Histogram Method
Inferência Probabilística

Resolução de 1.5 metros em média
Sistemas de Localização
Algoritmos
Precisão
Sistemas
Nearest Neighbor
~ 3.20
RADAR,
CHOICE
Kernel
~ 2.30
Ekahau
Histogram
~ 2.30
Inferência
Probabilística
~ 1.50
Ekahau, Rover,
Nibble
Rice University
Variações
Número de pontos amostrados
 Número de amostras por pontos
 Orientação do usuário
 Número vetores de observação utilizados
 Número de Pontos de Acesso

Vantagens

Orientação


Custo


Não tão preciso como posição
Infraestrutura já existente
Escalável

Limitação por custo computacional
Desvantagens

Dependência do Ambiente
Movimentação de pessoas e objetos
 Outros dispositivos 2.4 GHz


Geração de dados

Tempo necessário para geração
Conclusões
A inferência varia com fatores externos
 Os melhores resultados têm sido obtidos
com estratégias probabilísticas
 É possível a construção de diversas
aplicações com a precisão descrita
