RADAR/EKAHAU
Um sistema para localização e posicionamento de dispositivos móveis
usando rádio-frequência
Peter Kreslins Junior
Novembro/2004
Agenda


Tecnologias para localização e posicionamento de
dispositivos móveis
RADAR




Descrição
Diferenças com relação às outras tecnologias
Metodologia de Pesquisa
Métodos para inferir a localização e o posicionamento de dispositivos
móveis
• Método empírico
• Método teórico


Conclusões
EKAHAU



Descrição
Produtos
Screenshots
Tecnologias para localização e
posicionamento de dispositivos móveis

Em ambientes abertos




Time Difference of Arrival (TDoA)
Angle of Arrival (AoA)
GPS
Em ambientes fechados


Infra-vermelho
Rádio-frequência
TDoA e AoA


Utilizam técnicas para inferir a posição do
dispositivo em termos da diferença de
tempo de chegada do sinal entre as
diversas bases e em termos do ângulo de
chegada do sinal
Funcionam bem em ambientes abertos,
mas exibem problemas em ambientes
fechados como:


reflexão do sinal
dificuldade na sincronização do tempo
entre antena e dispositivo
GPS




Utiliza o sistema de
posicionamento global via satélite
para determinar a posição do
dispositivo
Em ambientes abertos é um dos
mais precisos métodos para
determinar a posição do dispositivo
Requer que o dispositivo móvel
seja capaz de receber sinais do
satélite (custo elevado)
Pode não funcionar em ambientes
fechados pois o sinal pode ser
bloqueado
Infra-vermelho




Localização e posicionamento de dispositivos móveis usando sinais
infra-vermelhos
Requer muitos sensores uma vez que essa tecnologia possui
alcanço limitado
Necessita de equipamentos específicos que em geral são usados
somente para localização e não oferecem serviço de transmissão
de dados
Manutenção pode se tornar um problema devido ao elevado
número de sensores
Rádio-frequência




Utiliza sinais de rádio para detectar a posição e localização de
dispositivos
Utiliza a infraestrutura WiFi (802.11a/b/g) para inferir o
posicionamento: mais barato e largamente utilizado
Além de localização, a infraestrutura WiFi provê serviço de
transmissão de dados (10mbps+)
Abrangência do sinal muito maior do que infra-vermelho
RADAR
Descrição






Sistema para localização e posicionamento de dispositivos usando
rádio-frequência
Pesquisa feita por Paramvir Bahl e Venkata Padmanabhan e
patrocinada pela Microsoft
Tem como objetivo demonstrar que o uso de tecnologia WiFi,
largamente adotada, pode ser usada para localização e
posicionamento de dispositivos
Utiliza dados sobre a força do sinal de rádio, coletados em diversos
pontos de acesso, para inferir a posição do dispositivo (através de
triangulação)
A triangulação pode ser feita de um modo empírico ou teórico
EKAHAU é o produto comercial que se baseia indiretamente nessa
pesquisa
Diferenças com relação às outras
tecnologias



Utiliza a rede Wireless para obter dados que são usados para inferir
posicionamento e localização
Não está associado a nenhuma tecnologia proprietária (nem
hardware e nem software)
Pode utilizar um modelo empírico ou um modelo teórico de
propagação de sinal
Metodologia de Pesquisa (1)





Experiência executada no segundo andar de um
prédio
O andar possui as seguintes dimensões: 43.5m
x 22.5m (980 m2)
Além disso o andar possui mais de 50 salas
Foram usadas 3 estações-base
O dispositivo móvel (laptop) recebeu uma placa
de rede com suporte WireLess (tecnologia
wireless antiga – WaveLAN RF LAN da Lucent)
Metodologia de Pesquisa (2)




Mapa do andar onde os
experimentos foram
conduzidos.
Pontos pretos indicam os
locais onde informação sobre
a intensidade do sinal foi
coletada.
As estrelas grandes indicam
a localização de cada uma
das 3 bases.
A orientação desse mapa é
Norte acima e Leste à direita.
Coletando dados






Coletar informações sobre o sinal de rádio como uma função da
posição do dispositivo (num modo offline e num modo realtime)
Os relógios das bases e do dispositivo móvel são sincronizados
O dispositivo móvel é programado para enviar pacotes UDP (4
pacotes por segundo)
Cada estação base grava a intensidade do sinal registrado em
conjunto com o timestamp
No modo offline, o usuário do dispositivo móvel indica sua posição
(X,Y) clicando no mapa – o timestamp e a posição também são
gravados
A direção para onde o usuário está apontando faz o sinal variar em
aproximadamente 5 dBm – assim, além da posição e timestamp, é
interessante gravar a direção também
Algoritmos e Análise Experimental (1)



Uma premissa dessa pesquisa é que a intensidade do sinal é uma maneira
de se inferir a posição do dispositivo
Isso é razoável pois, conforme o gráfico abaixo, a intensidade do sinal
varia conforme o dispositivo se aproxima ou se afasta de cada base
O gráfico abaixo retrata o dispositivo móvel sendo levado em sentido antihorário, começando perto da base 1 e terminando nela (vide slide Layout
do Andar)
Algoritmos e Análise Experimental (2)

A forma de inferir a posição do dispositivo proposta por esta pesquisa é a
triangulação. Para que funcione, algumas etapas devem ser levadas em
conta:


Uma maneira de sumarizar os dados sobre intensidade do sinal
Uma maneira de determinar a posição e direção que mais se aproxima de um
conjunto de valores de intensidade do sinal registrados – duas alternativas são
discutidas nessa pesquisa:
• o método empírico
• o método baseado num modelo de propagação de sinal

Uma maneira de decidir, entre vários possíveis candidatos para uma posição do
dispositivo móvel, qual é o melhor:
• A idéia geral é utilizar a técnica chamada NNSS (Nearest Neighbor(s) in Signal Space)
– calcular a distância entre as intensidades de sinal medidas e as intensidades de
sinal gravadas e escolher a que minimiza essa distância
Método Empírico


Nesse método os dados coletados durante a fase off-line são usados para
estimar a posição do dispositivo
Nos próximos slides, apresentamos alguns testes que ajudam a analisar
esse método:







Análise Básica (NNSS simples)
NNSS com múltiplos vizinhos
Desconsiderando a orientação
Impacto do número de pontos
Impacto do número de amostras
Impacto da orientação do dispositivo
A métrica usada para analisar a precisão do método, é a distância de erro
(distância euclidiana entre a posição real do dispositivo e a posição
estimada)
Análise Básica

Validar a técnica NNSS-simples (somente um vizinho) comparando-a com:



Um método aleatório de escolha de posições
Um método que considera a posição do dispositivo como sendo a mesma posição da base
que registrou o maior sinal
Mostrar que a técnica NNSS apresenta precisão satisfatória
NNSS com múltiplos vizinhos


Utiliza a técnica NNSS considerando os k vizinhos mais próximos (e
não somente o mais próximo)
Nos experimentos, mostrou-se que o uso de k-vizinhos melhora um
pouco a precisão




para k=5: melhoria de 22% (25% de prob.) e uma melhoria de 9%
(50% de prob.)
No entanto, para valores grandes de k, percebe-se uma
degradação na precisão pois posições distantes da real corrompem
a estimativa
A razão pela qual o ganho não é tão significativo diz respeito ao
fato de que k-NNSS, em geral, não são k diferentes pontos – eles
podem ser o mesmo ponto registrado em diferentes orientações
Conclusão: k-NNSS não melhora a estimativa de forma
considerável
Desconsiderando a orientação

Como pudemos ver, o fator orientação pode
prejudicar a precisão da técnica k-NNSS.
Assim, vejamos o que acontece quando a
orientação não é levada em conta:



Para o conjunto de dados obtidos no modo offline, escolhemos somente os pontos com
intensidade de sinal máxima, dentro de uma
mesma orientação
O objetivo é simular a situação onde o sinal
gerado não é obstruído pelo corpo do usuário,
por exemplo
Nas observações percebeu-se que há uma
melhora considerável (percentuais
comparados com a análise básica)


Para k=1: 6% de ganho (25% de prob.) e 9%
de ganho (50% de prob.)
Para k={2..4}: 48% de ganho (25% de prob.) e
28% de ganho (50% de prob.)
Impacto do número de pontos

Todos os testes até o momento foram feitos
usando-se 70 pontos distintos – vejamos o
impacto de utilizar menos de 70 pontos:





Para cada valor de n (variando de 2 a 70),
conduziu-se 20 execuções da análise
A cada execução, n pontos aleatórios foram
escolhidos do conjunto coletado no modo
offline e estes pontos foram usados no
algoritmo NNSS
Para n pequeno (menor ou igual a 5),
percebeu-se que a distância de erro é de 2 a 4
vezes pior que quando utiliza-se n=70.
A distância de erro diminui rapidamente
conforme o n aumenta. Ex.: para n=20 a
distância de erro é 33% pior e para n=40 é
menos de 10% pior.
Percebe-se que existe um limite de número de
pontos onde a melhora não é mais significativa
(em particular para o caso analisado, 40 pontos
distintos são suficientes)
Impacto do número de amostras




Nos testes até o momento utilizou-se a média de todas as
amostras coletadas, para cada combinação de posição+orientação.
Isso pode ser razoável para o modo offline, que é feito uma só vez,
no entanto, para o modo real, podem existir limitações no número
de amostras que se consegue coletar
A análise mostra que apenas uma pequena quantidade de
amostras no modo real é necessária para atingir uma precisão
razoável
Comparando com a análise básica:


Com somente 1 amostra, a distância de erro é 30% pior (50% de
prob.)
Com 2 amostras ela é 11% pior e com 3 amostras é 4% pior
Impacto da orientação do dispositivo

Como pudemos ver, a orientação do dispositivo impacta na
precisão. Para verificar o quanto esse impacto é significativo, o
seguinte teste foi feito:




A análise mostra que (em comparação com a análise básica):


Considera-se, para o conjunto de dados obtido no modo offline,
somente uma orientação específica (norte, por exemplo)
Para o conjunto de dados obtido em modo real, considera-se a direção
oposta (ex.: sul)
Calcula-se a distância de erro para cada uma das orientações que se
opõe (norte-sul, sul-norte, leste-oeste e oeste-leste)
A distância de erro é 54% pior (25% de prob.) e 67% pior (50% de
prob.)
Portanto é muito importante obter amostras para todas as
possíveis direções.
Localizando usuários móveis

Até agora, todos os experimentos feitos levavam em
conta um usuário/dispositivo estacionário. Vejamos as
particularidades para localização de usuários móveis:




O problema de localizar um usuário móvel pode ser definido
como uma sequência de problemas de localizar um usuário
“quase-estacionário”
Assim, usa-se uma janela deslizante de 10 amostras para
computar a média de intensidade de sinal
Esse valor é usado no método descrito anteriormente para
usuários estacionários
A distância de erro nesse caso é 19% pior que para o
caso estacionário
Método baseado no modelo de
propagação de sinal



Utiliza um modelo teórico de propagação do sinal para gerar o conjunto de
dados que serve de base para o NNSS
Não depende de dados empiricamente coletados durante uma fase off-line
Três modelos foram estudados:

Rayleigh fading model
• É largamente utilizado para descrever um fenômeno denominado multipath fading
mas não é completo pois assume que todos os sinais que chegam ao receptor têm a
mesma intensidade.

Rician distribution model
• É um modelo mais abrangente (o modelo Rayleigh é um caso especial deste) que
descreve a ocorrência de um sinal mais forte imerso em muitos sinais fracos e
dispersos. É bastante completo, no entanto é difícil determinar os parâmetros do
modelo como intensidade da componente dominante, por exemplo.

Wall Attenuation Factor (WAF) model
Wall Attenuation Factor model

Adaptação do modelo Floor Attenuation Factor (FAF) onde o fator de
atenuação dos andares foi trocado pelo fator de atenuação dos obstáculos
(paredes).
É descrito pela seguinte fórmula:

Onde:







n indica a taxa com a qual a intensidade do sinal cai com a distância
P(d0) indica a intensidade do sinal a uma distância de referência d0
d é a distância que separa o transmissor do receptor
C é o número máximo de paredes que fazem diferença sobre o fator de
atenuação
nW é o número de paredes entre o transmissor e o receptor
WAF é o fator de atenuação das paredes
Determinando o fator WAF





Primeiramente a intensidade do sinal é medida entre o receptor e o
emissor quando eles têm linha de visão (sem obstáculos)
Depois uma série de medições são feitas com um número conhecido de
paredes entre o emissor e o receptor
A média da diferença entre os sinais medidos é usada para determinar o
fator WAF
A atenuação começa a ficar cada vez menor conforme o número de
paredes entre o receptor e o emissor aumenta (isso indica que a perda por
distância domina a perda por obstáculos quando o receptor e o emissor
estão distantes e existem muitos obstáculos entre eles)
Os testes empíricos mostram que o fator WAF é de aproximadamente 3.1
dBm e o parâmetro C é de 4 paredes (número máximo de paredes que
fazem diferença na atenuação)
Variação do Sinal



Acima podemos ver a diferença entre a intensidade dos sinais registrados
sem (à esquerda) e com (à direita) o fator WAF.
No gráfico à esquerda, percebe-se uma diferença de 10 dBm entre duas
localidades afastadas aproximadamente 36m do receptor – isso se deve ao
fato de que, provavelmente, uma das localidades possui linha de visão
com o receptor e a outra encontra-se atrás de algumas paredes.
No gráfico à direita, já podemos perceber uma distribuição mais
homogênea devido à correção proporcionada pelo fator WAF – esse
gráfico muito se assemelha ao de perda de sinal por distância em
ambientes abertos.
Determinando os parâmetros n e P(d )
0





Com os valores de intensidade do sinal medidos em diversas posições e corrigidos
com o fator WAF, basta fazer uma regressão linear e obter os parâmetros restantes.
Os dados obtidos por regressão linear foram:
Podemos ver que os valores n e P(d0) não são muito discrepantes entre as bases, o
que sugere que eles não estão associados a um local fixo.
Além disso, o valor final combinado para as três bases é útil pois permite a inclusão
de novas bases no sistema sem necessidade de recálculo.
Os coeficientes R² e MSE são respectivamente o coeficiente de determinação e o
erro quadrado médio que indicam a precisão da regressão linear.
Resultados do modelo de propagação
de sinal



Para determinar a precisão desse modelo, uma série de medidas foram
feitas utilizando a fórmula descrita anteriormente. Esses valores foram
usados como base para o algoritmo NNSS.
O modelo de propagação de sinal apresentou distância de erro de 4,3m
(50% de prob.) e 1,86m (???) (25% de prob.).
Abaixo, mostramos um gráfico comparando os valores previstos pelo
modelo e os valores reais medidos:
Conclusões finais sobre os dois
modelos





Como visto através dos dados, o modelo empírico é muito mais
preciso do que o modelo teórico.
No entanto, o modelo empírico é mais caro na preparação pois a
base para o algoritmo NNSS precisa ser construída manualmente.
Já o modelo teórico apresenta uma maneira direta através da
fórmula apresentada.
Além disso, numa realocação das bases (ou inclusão de novas), o
modelo empírico requer todo o trabalho de setup novamente. Isso
não acontece no modelo teórico.
Além de coletar dados sobre a intensidade do sinal, parece ser
interessante combinar dados sobre o perfil do usuário como
padrões de movimento, horários, etc.
O objetivo dessa pesquisa era mostrar que, mesmo sucetível a
interferência, reflexão, atenuação, etc, o sinal de rádio pode ser
usado como base para as técnicas de localização de dispositivos
móveis.
EKAHAU
Descrição



EKAHAU é uma empresa que desenvolve ferramentas para
localização e posicionamento de dispositivos móveis usando a
infraestrutura Wireless (802.11abg).
Apesar de pertencer a uma vertente diferente de pesquisa,
Complex Systems Computation Group da Universidade de Helsinki,
o EKAHAU muito se assemelha ao modelo empírico descrito pela
pesquisa RADAR.
Os produtos pertencentes à suíte EKAHAU são:




EKAHAU
EKAHAU
EKAHAU
EKAHAU
Positioning Engine
T101 Wi-Fi Tag
Site Survey
Client
Positioning Engine




É o software que gerencia o posicionamento de dispositivos.
Trabalha com diversos tipos de dispositivos como WiFi Tags,
laptops, PDAs e outros dispositivos 802.11a/b/g.
Possui precisão média de 1m, usando técnicas para calibrar o local
em que será usado.
Apresenta dois tipos de interface para que outros programas se
comuniquem com o engine:


Uma API em Java que permite obter informações como posição x,y do
dispositivo, velocidade, andar em que se encontra, direção, etc.
Um protocolo denominado YAX que permite a comunicação via sockets
com o engine
T101 Wi-Fi Tag



São dispositivos pertencentes ao padrão 802.11 que podem ser
usados como etiquetas para localização de pessoas, equipamentos,
containers, etc.
Funcionam de forma transparente no sistema de posicionamento
EKAHAU.
Não necessitam de infraestrutura de hardware proprietária.
EKAHAU Site Survey



Essa é uma poderosa ferramenta para gravar, visualizar,
analisar, otimizar e verificar a performance de sua rede
sem fio.
Possui basicamente um visualizador e editor do mapa
da região onde a rede sem fio está instalada.
Com essa ferramenta, um administrador de rede sem
fio pode ter as seguintes informações da rede:
intensidade do sinal em diversos pontos, taxa de
transmissão de dados, localização dos APs, utilitário
para melhor posicionamento de APs, interferência, AP
mais forte, entre outras.
EKAHAU Client


Software que deve ser instalado nos dispositivos móveis
como laptops e PDAs para que eles se tornem passíveis
de localização e posicionamento através do Positioning
Engine.
Além disso, com esse software instalado, laptops e
PDAs tornam-se capazes de gerar dados para o Site
Survey, ajudando na obtenção de estatísticas sobre o
local onde a rede sem fio será instalada.
Screenshots – Positioning Engine
Screenshots – Client
Screenshots – Site Survey
Screenshots – Site Survey
Screenshots – Site Planner
Q&A