Qual algoritmo devo usar para geolocalização wifi?

16

Caso de uso da coleta escolar (atualização)

Pode ser útil entrar em um caso de uso mais concreto, em vez do exemplo original do quintal abaixo. As autoridades locais começaram a reprimir o uso de mensagens de texto e telefone celular nas zonas escolares. Isso representa um problema para os pais buscarem filhos depois de uma função no ensino médio. Mesmo para aqueles que ostentam a lei, a torre de celular fica sobrecarregada rapidamente quando centenas de crianças chamam seus pais ao mesmo tempo. O campus é amplo, com cobertura de wifi. Parece que deve ser possível escrever um aplicativo móvel que permita que um usuário de telefone celular envie uma mensagem de texto contendo uma lista de pontos fortes do sinal wifi a um serviço da web. O serviço da Web criaria uma correção de local e enviaria a mensagem ao dispositivo de navegação a bordo dos pais. Os pais então dirigem para o local correto no campus.

Caso de uso do quintal (original) Quando levo meu laptop ao quintal e escolho "ver redes disponíveis", vejo uma lista dos meus 4 vizinhos. Enquanto ando, os sinais relativos dos meus vizinhos mudam.

Eu gostaria de ficar com meu laptop em locais conhecidos no meu quintal, clicar no mapa e coletar pontos com 4 pontos de sinal diferentes.

Depois de coletar muitos (mas não muitos) desses pontos de calibração, eu gostaria de escrever um programa que consiga 4 níveis de força do sinal wifi e calcule um local na forma de uma elipse de erro. Os sinais podem ser medidos usando um dispositivo diferente daquele usado para coletar os pontos de calibração originais.

Qual algoritmo devo usar?

Não quero incomodar meus vizinhos perguntando se posso entrar e pesquisar a localização exata do roteador.

No entanto, posso assumir que a localização dos roteadores dos meus vizinhos não muda.

Kirk Kuykendall
fonte
4
acho que ele só quer fazer triangulações, não pegar carona ...
Marinheiro 23/10
Nada de pegar carona - apenas a força do sinal, que é legal de medir, certo? Eu não vou "pesquisar" no wifi ... blogs.discovermagazine.com/80beats/2010/10/25/…
Kirk Kuykendall

Respostas:

6

Parece que você não conhece muito bem as localizações dos sinais; portanto, é necessário primeiro estimar e, em função dessas estimativas, triangular sua posição.

Se você quiser um pouco de precisão e realismo, considere adotar um modelo de probabilidade para as forças do sinal, encontrar a probabilidade máxima e fazer um mapa em grade da probabilidade de localização calculada a partir das estimativas de probabilidade máxima. O máximo global na grade identifica a melhor estimativa do local e os contornos (relativos ao máximo) fornecem conjuntos de confiança para esse local.

Um modelo de probabilidade geral é obtido colocando uma fórmula para a atenuação do sinal e permitindo erros. Você não vai muito longe com uma fórmula completamente geral (com uma função de atenuação dependente do ângulo e da localização); portanto, você precisará simplificar. Por exemplo, você pode considerar uma função de atenuação "universal", chamada f , para que, se a força da fonte em um local WiFi x for igual a , a força esperada em outro local y é dada por

z (y; x) = af (| y - x |).

Por exemplo, você pode considerar a atenuação do quadrado inverso para a qual f (t) = 1 / t ^ 2, desde que a distância t seja maior que algum limite pequeno. Como outra simplificação, você pode usar a leitura de força z (y; x) no local y para que a fonte em x seja diferente do valor esperado por um erro normalmente distribuído; assuma que todos os erros são independentes; e assumir todos eles têm o mesmo desvio padrão ( s ). A contribuição para a probabilidade logarítmica de uma leitura de força z torna-se então

L (y, x) = - [(z (y; x) - af (| yx |) ^ 2 / s ^ 2 + ln (s)] / 2.

A probabilidade do log a ser maximizada é a soma dupla de L (y, x) em todos os locais y e todas as fontes x . É uma função dos locais desconhecidos, das intensidades desconhecidas da fonte e do desvio padrão desconhecido dos erros. É simples de encontrar o melhor desvio padrão e intensidades ótima fonte (tomar derivadas parciais, definir aqueles a zero, e resolver), mas para as funções de atenuação realistas f você tiver um problema não-linear para encontrar os locais. No entanto, no seu exemplo, ele envolve apenas 13 parâmetros, portanto, você poderá despejá-lo em, por exemplo, um otimizador multivariado de Newton-Raphson e obter rapidamente uma boa resposta. (A literatura estatística está cheia de métodos para resolver esses tipos de equações.)

Se você assumir adicionalmente que o segundo dispositivo possui sensibilidade proporcionalmente maior que o dispositivo de coleta de dados, fará pouca diferença no modelo que propus (porque os pontos fortes do sinal entram multiplicativamente). De fato, se você deixar os erros escalarem com intensidade (para que eles tenham desvio padrão a * s * em vez de s ), a diferença entre os dispositivos deve ser inconseqüente.

Para manter isso simples, pulei algumas detalhes estatísticos, como o fato de que este é um problema de intervalo de previsão multivariado, não um problema de intervalo de confiança. Se a quantidade de erro não for grande (ou seja, s for pequeno), a diferença não será de muita consequência.

whuber
fonte
Obrigado Bill, isso parece factível. Com os laptops, acabei de perceber que o sinal é sensível à orientação das antenas. Não tenho certeza se isso é verdade com telefones celulares. A correção do local seria boa o suficiente para o caso de uso da escola secundária?
26610 Kirk Kuykendall
Você pode lidar com a orientação, mas fica mais complicado e precisaria de mais leituras. Em vez disso, considere usar o sinal máximo entre todas as orientações possíveis em cada ponto. O caso de uso da escola secundária é uma variante interessante, pois sugere fazer o melhor para identificar os pontos e os pontos fortes dos remetentes de WiFi de uma vez por todas. Depois disso, é um exercício de triangulação. Uma preocupação que tenho é que os pontos fortes da fonte podem variar, geralmente imprevisivelmente. Isso pode realmente estragar a triangulação. Considere adicionar uma tela inicial para sinais externos (baixos) para que eles não estraguem a correção.
whuber
0

Se você está coletando o local com GPS, acho que está analisando dois fatores de erro diferentes. um para o GPS e outro para a força do sinal.

Brad Nesom
fonte
Nesse contexto, Kirk poderia realmente verificar os locais em seu quintal de forma independente (ou seja, basta fazer várias leituras de GPS em cada local).
Andy W
0

Você não pode aproveitar um dos sistemas de posicionamento WiFi existentes, como o Skyhook Wireless ou o Core Location no iOS da Apple? O Skyhook permite que você adicione endereços MAC Wi-Fi ao banco de dados manualmente, o iOS coleta endereços MAC Wi-Fi automaticamente usando iPhone equipados com GPS.

Ortwin Gentz
fonte
Isso pode não ser uma má idéia, se ele quiser descobrir onde está. Mas ele está tentando descobrir uma maneira de coletar os locais das redes ele mesmo. Além disso, ele está tentando triangular sua posição com base na força dos sinais de WiFi. Não tenho certeza se as soluções comerciais fazem isso.
jvangeld
@jvangeld: Até onde eu entendi, o Core Location no iOS usa a força do sinal Wi-Fi para triangular a posição. Para o caso de recolhimento da escola mencionado, seria o caminho a percorrer.
Ortwin Gentz
0

Kirk,

Embora eu esteja errado, acho que você está complicando as coisas. Embora seja justo, não sendo da sua parte do mundo, não sei com quais limitações você está trabalhando em um campus da escola.

Enquanto a maioria dos dispositivos móveis já suporta GPS e triangulação de torres celulares, para WiFi, o SkyHook é a resposta pelos seguintes motivos: 1. O banco de dados de locais WiFi é ENORME. 2. Sempre que um aplicativo usando o SkyHook é usado, ele adiciona redes WiFi recém-encontradas ao banco de dados, com posição. Portanto, quanto mais ele é usado em uma área, mais preciso ele se torna. Eu acho que em um local de alta densidade como um campus, se ainda não houver uma boa cobertura, terá em questão de dias de uso regular. 3. Alguns telefones usam o SkyHook como parte de suas APIs de localização, o que significa que mais e mais APIs de telefone normais terão isso já incorporado.

Para ser sincero, a menos que você queira que este serviço esteja disponível em laptops (a maioria dos novos navegadores possui o SkyHook embutido), a maioria dos telefones agora possui GPS, que pode ser acessado por meio das APIs nativas de telefones, seja iOS, Android, WP7 ou Amora. A outra opção seria torná-lo um aplicativo da web móvel, que usaria apenas a API de localização do navegador, com acesso a todas as ferramentas de localização no telefone de qualquer maneira.

BlinkyBill
fonte
Eu pensei que o skyhook coletou dados via wardriving. Não consigo imaginá-los dirigindo pelas estradas da escola, embora suponha que sejam públicos.
Kirk Kuykendall
Você está correto, mas como os clientes 'expandem' seu banco de dados, além de impulsionar a guerra, você provavelmente descobrirá que eles têm cobertura de qualquer maneira. Você sempre pode testar carregando o Opera no seu laptop, entrar no campus com maps.google.com e WiFi ativados e ver onde ele o coloca.
BlinkyBill