2. Teoretisk rammeverk
2.2 Stadiene i staveutviklingen
16 v ar i an c e = r e f i n a m e n t o ( pico ) ; 17 if( var > l i m i a r F i n o ) { 18 printf (" \ n Sa t ´e li t e e n c o n t r a d o !! ") ; 19 total ++; 20 }else{ 21 // S a t´e l it e n~ao e n c o n t r a d o .
22 // C o nt i nu a a busca com adi¸c~ao de novas a m os t ra s .
23 } 24 } 25 } 26 }
4.2
Detec¸c˜ao Fria em Paralelo
Al´em das estrat´egias mencionadas na se¸c˜ao anterior, foi utilizada uma estrat´egia paralela para o caso de busca por m´ultiplos sat´elites. Existem 32 (apenas 24 est˜ao ativos) poss´ıveis sat´elites dispon´ıveis para aquisi¸c˜ao e no m´ınimo quatro s˜ao necess´a- rios para fazer o c´alculo de posi¸c˜ao. Em adi¸c˜ao `as estrat´egias anteriormente citadas, foi utilizado paralelismo visando otimizar a busca fria, que ´e a busca realizada em todos os sat´elites poss´ıveis. Com isso, tanto a busca direcionada quando a busca fria est˜ao cobertas pelo algoritmo. As mesmas estrat´egias do algoritmo anterior foram mantidas, mas agora elas s˜ao aplicadas a v´arios sat´elites simultaneamente.
A Figura 4.9 mostra a replica¸c˜ao de diversos correlacionadores em paralelo. Em cada um deles s˜ao implementadas as estrat´egias na se¸c˜ao anterior. No nossos expe- rimentos foram utilizados 32 correlacionadores em paralelo, cada um buscando por um sat´elite diferente.
Foi utilizada a biblioteca Open-MP para fazer a implementa¸c˜ao paralela do al- goritmo. No momento que quatro sat´elites s˜ao encontrados, o algoritmo para. Esse valor ´e configur´avel e pode ser modificado para quantos sat´elites forem necess´arios. A busca em paralelo executa 32 buscas simultaneamente. A vari´avel total ´e compartilhada e informa o n´umero de sat´elites encontrados. Cada thread que executa em paralelo pode ler e escrever em total. A diretiva critical foi utilizada para proteger o acesso `a total, de modo que apenas uma thread escreva por vez.
Quando a quantidade chegar a quatro sat´elites detectados, o algoritmo para. Existem dois crit´erios de parada, quando o sat´elite ´e encontrado ou quando o total
36 CAP´ITULO 4. DETEC ¸C ˜AO DE SINAIS DE GPS EM DOIS PASSOS
for maior ou igual a quatro. Quando o sat´elite ´e encontrado, apenas a thread que encontrou para, mas quando quatro s˜ao encontrados, todos param.
O algoritmo paralelo ´e basicamente o mesmo que foi citado anteriormente, apenas algumas diretivas ligadas ao paralelismo foram utilizadas, mas todas as estrat´egias anteriores foram mantidas. O pseudo-c´odigo do algoritmo paralelo ´e listado abaixo:
1 # pragma omp p ar a ll e l n u m _ t h r e a d s (32) 2 { 3 s at e li t e = o m p _ g e t _ t h r e a d _ n u m () +1; 4 for ( d = 0; d < passo ; d ++) { 5 for ( z = d ; z < n ; z = z + passo ) { 6 for ( x = 0; x < doppler ; x ++) 7 { 8 for( y =0; y < phases ; y ++) { 9 // calcula o pico de c o r r e l a ¸c ~a o 10 } 11 } 12 13 // fun¸c~ao r e p o n s ´a v e l por c a lc u la r a v a r i ^a n c i a
14 // dos 5 maiores picos e n c o n t r a d o s
15 v a r i a n c i a = c a l c u l a V a r i a n c i a ( peaks ) ; 16 if( variancia > l i m i a r G r o s s e i r o ) { 17 v a r i a n c i a = re f in i n g ( peaks ) ; 18 if( variancia > l i m i a r F i n o ) { 19 printf (" \ n S at ´e li t e e n c o n t r a d o ") ; 20 # pragma opm c ri t ic a l 21 total ++; 22 }else{ 23 // S a t´e l it e n~ao e n c o n t r a d o
24 // C o nt i nu a a busca com adi¸c~ao de novas a m os t ra s .
25 } 26 }
27 if( total ==4) {
28 // Neste ponto foram d e t e c t a d o s o m´ınimo de quatro
s a t ´e l i t e s
29 break;
30 } 31 } 32 }
4.2. DETEC ¸C ˜AO FRIA EM PARALELO 37
38 CAP´ITULO 4. DETEC ¸C ˜AO DE SINAIS DE GPS EM DOIS PASSOS
(a) Correla¸c˜ao com Sinal de 100 amostras (b) Correla¸c˜ao com Sinal de 200 amostras
(c) Correla¸c˜ao com Sinal de 300 amostras (d) Correla¸c˜ao com Sinal de 400 amostras
Figura 4.3: Compara¸c˜ao entre a correla¸c˜ao baseada no incremento progressivo das mostras do sinal. Esta figura mostra que `a medida que se utiliza mais amostras, o valor do pico de correla¸c˜ao tem um aumento. O algoritmo explora essa propriedade para utilizar um sinal menor. O total de amostras para o sinal desta figura ´e de 11999, mas com 200 j´a se pode detectar um poss´ıvel pico.
4.2. DETEC ¸C ˜AO FRIA EM PARALELO 39
1 1 1 ... 1
1 1 1 1 ... 1
Visita 1 Visita 2 Visita 1023 O sinal pode ser detectado antes de terminar todas as visitas.
Se o sinal não for detectado com 1 amostra por sub-vetor o processo continua adicionando outra amostra por sub-vetor.
1 1 1 1 ... 1 1 1 1 ... 1 1 1 1 1 1 1 ... 1 1 n-1 0 ... ... 1 ... 1
1 Amostra já utilizada. 1 Amostra a ser utilizada.
Foram realizadas todas as visitas possíveis nesse caso.
1
1
Figura 4.4: Itera¸c˜oes do algoritmo.
Figura 4.5: Regi˜ao de refinamento identificada pelo algoritmo grosseiro. Apenas uma ilustra¸c˜ao de que ´e preciso cobrir outros componentes de frequˆencia al´em da coordenada buscada. Os valores da imagem n˜ao representa informa¸c˜ao ´util.
40 CAP´ITULO 4. DETEC ¸C ˜AO DE SINAIS DE GPS EM DOIS PASSOS
Figura 4.6: Com o m´etodo proposto h´a a possibilidade de detec¸c˜ao de falsos picos e que aumenta o processamento pois v´arias chamadas `a busca fina ser´a feita. Se aumentarmos o limiar o processamento tamb´em aumenta, pois ser´a preciso fazer mais processamento para se atingir o pico.
Figura 4.7: Poss´ıveis valores de variˆancia para dois picos de correla¸c˜ao normalizados. O valor m´aximo de variˆancia ´e 0.5
4.2. DETEC ¸C ˜AO FRIA EM PARALELO 41
42 CAP´ITULO 4. DETEC ¸C ˜AO DE SINAIS DE GPS EM DOIS PASSOS
Cap´ıtulo 5
Resultados
O trabalho descrito neste texto faz parte de um esfor¸co inicial para desenvol- vimento de um receptor de GPS completo. Nesse sentido, foi implementado um algoritmo que trata da aquisi¸c˜ao dos sinais, que ´e uma importante etapa no pro- cesso de localiza¸c˜ao por GPS.
O algoritmo foi implementado utilizando a linguagem C e os experimentos foram realizados num computador com 24 n´ucleos e frequˆencia de 2.0 GHz em cada n´ucleo. O sinal utilizado para a busca foi adiquirido no site da Universidade de Aalborg, no Danish GPS Center [Danish GPS Center n.d.].
Foi amplamente descrito no texto que, para fazer a detec¸c˜ao do sat´elite, ´e preciso gerar uma r´eplica do c´odigo CA no receptor. No entanto, foi adotada a estrat´egia de gravar estes sinais em arquivo. S˜ao 32 poss´ıveis sinais que demandam processamento para serem gerados. Se armazenados em mem´oria, o tempo de execu¸c˜ao gasto para ger´a-los pode ser economizado. O algoritmo de gera¸c˜ao do c´odigo CA est´a dispon´ıvel no Apˆendice A.1.
A escolha dos experimentos que ser˜ao apresentados, foi realizada com o objetivo de verificar o desempenho do algoritmo em rela¸c˜ao a busca fria e a busca direcionada. Cada tipo de busca ´e apropriada para situa¸c˜oes espec´ıficas.
Inicialmente ´e mostrado na Tabela 5 o Time to First Fix (TTFF), que representa o tempo para se fazer a primeira localiza¸c˜ao, ou seja, obter a primeira coordenada. Alguns receptores comerciais est˜ao listados juntamente com o seu TTFF para uma busca fria. Vale lembrar que para cada tipo de estrat´egia de busca o tempo varia, mas a busca fria ´e a mais demorada. O processo de c´alculo de posi¸c˜ao possui v´arias etapas e n˜ao ´e foco deste trabalho fazer um receptor completo, mas a tabela ´e apresentada para dar uma vis˜ao geral para o leitor sobre os tempos de alguns receptores.
Segundo Zhu et al. (2011), o tempo gasto no processo de aquisi¸c˜ao ´e o principal 43
44 CAP´ITULO 5. RESULTADOS
fator que contribui para o aumento do TTFF. Nesse sentido, baseado no TTFF de alguns receptores comerciais listados na Tabela 5, ´e poss´ıvel fazer uma estimativa a respeito da viabilidade do algoritmo proposto baseando-se nos resultados do processo de aquisi¸c˜ao que ser˜ao apresentados a seguir.
Receptor TTFF em segundos WondeX BT760Y 30 Globaltop G33 36 Nokia LD-3W 45 Emtac/Socket BT GPS 43.2 Garmin eTrex 41.4 Garmin eTrex Summit 41
Garmin eTrex Vista 39.8 Garmin GPSMap76 37.4 Garmin GPSMap76S 38.4 Garmin Geko 101 53 Garmin Geko 201 40 HaiCom 302 CF 57.8 HaiCom 303 MMF 57.6
Tabela 5.1: Rela¸c˜ao de tempo para fazer a primeira localiza¸c˜ao para alguns recep- tores comerciais.
5.1
Estat´ısticas da Busca
Para os primeiros testes, foram utilizadas 40 sequˆencias de 1 ms selecionadas aleatoriamente no sinal de entrada. Para cada uma das 40 sequˆencias foi utilizado o algoritmo convencional e o proposto para procurar quatro sat´elites.
Para as duas abordagens foi utilizado um deslocamento de frequˆencia de 20 kHz em passos de 1 kHz. A abordagem proposta pode refinar ainda mais essa freq¨uˆencia com passos de 500Hz. O m´etodo convencional foi testado em 3 configura¸c˜oes diferen- tes, ou seja, utilizando limiares de detec¸c˜ao de 3x105
, 5x105
, 8x105
. Na abordagem proposta foram utilizados limiares fixos, sendo 1.8x10−1 para a etapa grosseira e
4x10−2 para a etapa de fina.
A partir dos resultados apresentados nas Tabelas [5.2-5.5], pode-se observar duas importantes vantagens do m´etodo proposto. Em primeiro lugar, quando se compara a precis˜ao entre o m´etodo proposto e as duas primeiras defini¸c˜oes da abordagem convencional, ´e poss´ıvel perceber um grau de equivalˆencia, enquanto o desempenho da terceira configura¸c˜ao do m´etodo convencional se degrada consideravelmente.
5.2. BUSCA POR SAT ´ELITES VIS´IVEIS 45
Neste sentido, a abordagem proposta ´e vantajosa porque o n´ıvel de limiar ´e independente da intensidade de sinal. Em segundo lugar, o tempo de execu¸c˜ao da abordagem proposta foi muito menor do que o convencional. ´E poss´ıvel observar que o tempo de execu¸c˜ao m´edio ´e 90% melhor.
Sat´elite
Precis˜ao
Falsos Positivos
Falsos Negativos
Tempo
1
95%
5%
1.15s
2
85%
0%
3.18s
16
95%
5%
1.18s
19
60%
40%
2.46s
TOTAL
84%
28%
5%
1.99s
Tabela 5.2: Algoritmo proposto com limiar Grosseiro de 4x10−2 e limiar fino de
1.8x10−1
Sat´elite
Precis˜ao
Falsos Positivos
Falsos Negativos
Tempo
1
80%
20%
38.21s
2
100%
0%
38.22s
16
96%
4%
38.22s
19
76%
24%
38.22s
TOTAL
88%
12%
12%
38.22s
Tabela 5.3: Algoritmo convencional com limiar de detec¸c˜ao de 3x105
.
Sat´elite
Precis˜ao
Falsos Positivos
Falsos Negativos
Tempo
1
50%
50%
38.21s
2
100%
0%
38.22s
16
93%
7%
38.22s
19
100%
0%
38.22s
TOTAL
86%
0%
29%
38.22s
Tabela 5.4: Algoritmo convencional com limiar de detec¸c˜ao de 5x105
.