Comunicações e Coordenação de Rede de Veículos Aquáticos

FACULDADE DE ENGENHARIA DA UNIVERSIDADE DO PORTO Comunicação e Coordenação em Rede de Veículos Aquáticos André Filipe de Castro Reis Mestrado Integrado em Engenharia Eletrotécnica e de Computadores Orientador: Professor Aníbal Matos 27 de Outubro de 2013 c André Reis, 2013 Resumo À medida que a tecnologia vai avançando, o Homem fica cada vez mais dependente que as máquinas consigam desempenhar tarefas de forma autónoma. Esta necessidade implica, no caso de várias máquinas envolvidas, que estas tenham sempre a capacidade de comunicação umas com as outras. Este trabalho está inserido no âmbito do grupo da Faculdade de Engenharia da Universidade do Porto, OceanSys, que tem, como objectivo o desenvolvimento de sistemas avançadas com a capacidade de, automaticamente, recolher e processar dados em ambientes aquáticos, e pretende desenvolver um meio de assegurar que estas comunicações se realizam, através de algoritmos e simulações. i ii Abstract As technology advances, Man develops a need of machinery that can perform tasks in an autonomous way. This need implies, in the case of multiple machines involved, that they have the ability to communicate with one another. This work is inserted in the context of the working group from Faculdade de Engenharia da Universidade do PortoOceanSys, which has the purpose of developing advanced systems with the ability to, automatically, collect and process data in aquatic environments, and pretends to assure that these communications take place, through the use of algorithms and simulations. iii iv Agradecimentos Agradeço, primeiramente, aos meus pais pelo apoio dado durante todos os anos que estudei. Agradeço, também à Joana pela paciência demonstrada quando as coisas corriam menos bem e precisava de alguém para desabafar. Um agradecimento especial ao Professor Aníbal Matos pela orientação prestada no decorrer deste trabalho e, também, aos elementos pertencentes ao OceanSys pela disponibilidade demonstrada para ajudar a compreender o funcionamento dos ASV. Por fim, agradeço a Matt Fig e a Paulo Silva pelo código que disponibilizaram online e que auxiliou à execução do trabalho. André Reis v vi “An example I often use to illustrate the reality of vanity, is this: look at the peacock; it’s beautiful if you look at it from the front. But if you look at it from behind, you discover the truth... Whoever gives in to such self-absorbed vanity has huge misery hiding inside them.” Pope Francis vii xiv LISTA DE TABELAS Abreviaturas e Símbolos ASV Autonomous Surface Vehicle AUV Autonomous Underwater Vehicle GPS Global Positioning System MARES Modular Autonomous Robot for Environmental Sampling SSH Secure SHell UTM Universe Transverse Mercator WSN Wireless Sensor Network (Rede de Sensores sem Fios) xv Capítulo 1 Introdução 1.1 Motivação Quando em missão, é, de todo, importante que não haja quaisquer falhas na comunicação entre os vários intervenientes. Ao falar em veículos autónomos, tem-se, como preocupação, não só a detecção destas falhas, mas também a sua correcção. Uma maneira de minimizar estas falhas, é usar veículos secundários para preencher lacunas, realizando pontes entre o veículo emissor e o recetor. 1.2 Caracterização do Problema O problema a tratar é o desenvolvimento de estratégias de controlo coordenado e de localização distribuída para uma rede de veículos aquáticos, entrando em consideração com as restrições da rede de comunicação. Este problema divide-se em 3 sub-problemas: •A formação adotada pelos veículos, uns com os outros; •Otimização da comunicação entre eles de modo a que esta seja o mais eficiente possível; •Junção de localização subaquática cooperativa com recurso a uma mistura de redes acústicas com redes sem fios. As restrições impostas pela rede de comunicação são as seguintes: •Intermitências inerentes a comunicações sem fios, sendo mais frequentes com o tipo de plataforma a ser usada, pois a ondulação da água pode limitar o alcance da comunicação; •O próprio alcance referido no ponto anterior é um dos desafios a enfrentar, uma vez que é possível haver casos em que o alcance necessário seja relativamente grande; •O atraso das comunicações que influenciam a instabilidade o sistema, como será referido no capítulo 2. 1 2Introdução Para além dos desenvolvimentos conceptuais, os algoritmos estudados serão aplicados nos veículos aquáticos presentes na FEUP. Os veículos de superfície autónomos (ASV), Zarco e Gama, fig 1.1, têm a forma de um catamarã, são altamente modulares e foram desenhados para operar em águas calmas. Contém um computador a bordo de modo a executar as missões de forma completamente autónoma ou controlada remotamente e onde pode armazenar os dados internos e da carga. Também possui uma ligação wifi com a qual pode comunicar com uma estação em terra. Tem 1,5m de comprimento, 1m de largura e pesa cerca de 50kg, podendo aguentar cargas de até 20kg e consegue atingir 3nós de velocidade, o que corresponde a 5,556 km/h. Figura 1.1: ASV Zarco O MARES, fig 1.2, é um Veículo subaquático autónomo (AUV), também altamente modular, foi desenhado para operações a baixas profundidades. A sua configuração permite que lhe sejam acoplados uma grande variedade de sensores oceanográficos e tem um de sensores de navegação para garantir que se mantém na trajetória planeada. Tem forma cilíndrica com 20cm de diâmetro e 1,5m de comprimento e pesa cerca de 32kg, podendo atingir profundidades na ordem dos 100m e velocidades de cerca de 2m/s. Figura 1.2: AUV MARES O TriMARES, fig 1.3 é um AUV composto por 3 partes baseadas no MARES montadas em forma de triângulo. Foi desenhado para ter uma maior capacidade de carga, de modo a poder transportar, por exemplo, câmaras de alta qualidade e sonares. Os seus sensores de navegação incluem um IMU, um sensor de pressão e um sistema de posicionamento acústico. Mede 1,5m de 1.3 Estrutura da Dissertação 3 comprimento, 80cm de largura composta e 50 cm de altura composta e pesa 75kg. Pode atingir os 100m de profundidade e uma velocidade de 2m/s. Figura 1.3: AUV TRIMARES 1.3 Estrutura da Dissertação Este documento está dividido em seis partes: No capitulo 2é revisto o estado da arte que refere o movimento coordenado de veículos autónomos com restrições de comunicações. É, também, introduzido o conceito de redes de sensores sem fios e o controlo de sistemas em rede, assim como filtros de Kalman como ferramenta de controlo. No capítulo 3são estudados modelos probabilísticos de comunicação, nomeadamente, um modelo uniforme, um modelo linear e um modelo exponencial. No capítulo 4são estudadas 4 topologias distintas para a comunicação entre dois veículos. Por fim, no capítulo 6são comparados quatro algoritmos diferentes em termos de tempo médio usado para estabelecer uma comunicação, desde que, estando os veículos em repouso, partem para estabelecer a comunicação e retornam à posição original. 4Introdução Capítulo 2 Estado da Arte 2.1 Introdução Neste capitulo é apresentado o estado da arte. É, primeiramente, apresentado o movimento coordenado de veículos em rede, seguido da modelização de redes sem fios e dos problemas levantados pelo controlo em rede e uma possível solução através da utilização de filtros de kalman. 2.2 Movimento coordenado de veículos autónomos, tendo restrições de comunicações Uma rede de comunicações pode ser modelada recorrendo ao uso de grafo onde os vértices são os nodos de comunicação e as arestas ligam os nodos que conseguem comunicar. Um grafo diz-se conectado quando dois vértices quaisquer podem ser unidos por um caminho de tamanho arbitrário. [1] Matematicamente, um grafo pode ser representado pela matriz de incidência M de dimensão nxε, sendo n o número de vértices e εo número de arestas. Esta matriz é preenchida da seguinte forma: mkl=         +1 se o vértice k for o início da aresta l −1 se o vértice k for o fim da aresta l 0 nos outros casos (2.1) O laplaciano de um grafo, L, é definido como sendo L=MMTe tem ordem n×n. Por construção, Lé independente da orientação dada a cada aresta na matriz M, os seus valores próprios são não negativos e o vetor 1npertence ao seu núcleo, isto é, L1n=0n. No caso de grafos conectados, Ltem um valor próprio em zero e vetor próprio 1n. De seguida, são apresentadas considerações sobre redes de comunicações, supondo topologias fixa, onde o grafo é fixo ao longo do tempo, e topologias variáveis, onde a conectividade do grafo pode variar. 5 6Estado da Arte No primeiro caso, podem-se considerar restrições nas comunicações bidirecionais e unidirecionais. Nas comunicações bidirecionais, assumem-se duas condições: •Se o nodo icomunicar com o nodo j, o nodo jtambém consegue comunicar com o nodo i, isto é, se Nkfor o conjunto de nodos com os quais o nodo kconsegue comunicar, então, i∈Nj⇔j∈Ni; •O grafo está conectado. Caso contrário, haveria dois ou mais conjuntos de nodos incapazes de comunicar uns com os outros. Nas comunicações unidirecionais, a primeira condição das comunicações bidirecionais, já não se aplica. Apesar deste tipo de comunicações ser mais restritivo, é possível, na mesma, possível a execução de coordenação entre veículos e de seguimento de trajetórias lineares, circulares ou trajetórias paralelas de caminhos arbitrários. Quanto às topologias de comunicação variáveis, tem-se breves perdas de conectividade e topologia "conectado em média". Na primeira, considera-se que o grafo está alternadamente conectado e desconectado. Para isto, considera-se um conjunto com 2ngrafos, correspondentes às possibilidades de conectividade do grafo, onde n=n×(n−1) 2é o número de vértices e n é o número de nós do grafo. Deste conjunto, em cada interação, seleciona-se aleatoriamente um grafo e, daí, determina-se, de forma probabilística se o grafo está conectado ou não. Na segunda topologia, considera-se a hipótese de o grafo nunca estar conectado, qualquer que seja o instante de tempo. No entanto, assume-se que, num intervalo de tempo finito, a união das várias posições do grafo, origina um grafo conectado. Isto é um grafo está conectado em média se, para todos os instantes de tempo t≥0 existir um T>0 finito, tal que, a união dos grafos no intervalo [t,t+T]seja um grafo conectado. Neste caso, a soma dos laplacianos dos grafos do intervalo, terá um valor próprio na origem, e vetor próprio 1n. 2.3 Redes de Sensores sem Fios (WSN) Uma WSN pode ser modelada como um conjunto de nodos numerados de 1 até Ne uma matriz de conectividade Conde cada elemento ci j ∈[0,1]é a probabilidade do nodo jcomunicar com o nodo i. Como a rede é aproximadamente simétrica, pode-se assumir que C=CTecii =1,∀i. [2] O grafo de conectividade-c Gc = (N,Ec)está associado à matriz Ccomo sendo o grafo onde (i,j)pertence ao conjunto das arestas se cij≥c. Existem três tipos de comunicação mais frequentemente usados: •Broadcast – Um nó transmite uma mensagem para toda a vizinhança; •Assymetric Gossip – Um nó transmite uma mensagem para um nó específico, pertencente à sua vizinhança; 2.4 Controlo de Sistemas em Rede 7 •Symetric Gossip – Igual ao assymetric gossip, mas o nó que transmite fica à espera de resposta por parte do recetor. 2.4 Controlo de Sistemas em Rede Num sistema de controlo em rede, os atuadores e os sensores comunicam com o controlador com recurso a uma rede de comunicação. O tempo que a informação demora entre as partes depende da topologia da rede e pode ser constante, tendo, no entanto, na maioria das vezes, variações aleatórias. [3] Nestes sistemas, os atrasos advêm de três acções: •Atraso de comunicação entre os sensores e o controlador; •Atraso na computação dos dados no controlador; •Atraso na comunicação entre o controlador e os sensores. Sendo estes atrasos estocásticos, o sistema passa a ser variante no tempo, pelo que as técnicas usadas para sistemas invariantes no tempo não o possam ser diretamente utilizadas na análise deste sistema. Uma possível solução para este problema, será a utilização de buffers na realimentação, tornando, assim, os atrasos determinísticos e o sistema invariante no tempo. Esta resolução levanta, no entanto, um outro problema: a informação a que o controlador, por vezes, tem acesso, é informação que já não é válida e isso leva a uma degradação da estabilidade e da eficiência do sistema. Assim sendo, torna-se, por vezes, mais comportável o cálculo de um controlador para o sistema invariante no tempo. De seguida, são apresentados três possíveis modelos para a rede de comunicação: •Rede modelada com atrasos constantes – Este é o modelo mais simples para a rede e é admissível até com redes com atrasos variáveis se a escala temporal do processo for muito superior ao atraso das comunicações. Neste caso, é usual usar o valor médio ou o pior caso. Nos casos em que isso não acontece, podem ser tiradas conclusões erradas quanto à estabilidade e eficiência do sistema. •Rede modelada com atrasos independentes – Neste caso, os atrasos podem tomar várias formas como, por exemplo, o tempo de espera para que outras mensagens de maior prioridade sejam enviadas ou tempos de retransmissões. Como as ações do sistema não estão sincronizados, estes atrasos são estocásticos, e podem ser modelados com recurso a distribuições probabilísticas. •Rede modelada com recurso a cadeias de Markov – Apesar de, com o modelo anterior, se assumir que os atrasos são independentes dos atrasos anteriores, isto nem sempre é verdade, pelo que é necessário que o sistema tenha memória, de modo a ser possível, correlacionar o atraso com os anteriores. Isto é possível usando cadeias de Markov que efetuam uma transição a cada comunicação feita. 14 Comunicação em rede Capítulo 4 Topologias de Rede 4.1 Introdução Neste capítulo serão apresentados 4 topologias da rede as quais serão comparadas no capítulo 5. Estas topologias, assim como os algorítmos a elas associados, foram estudadas no decorrer desta dissertação. 4.1.1 Sistema UTM A primeira consideração a realizar, quando se fala em comunicação, é a distância entre os intervenientes. O sistema GPS, contendo medidas angulares torna este trabalho complicado. Nesse caso, tendo em consideração, que os veículos se encontram sempre numa distância muito inferior ao do raio da Terra, pode-se usar um outro sistema, o UTM. Este sistema consiste na divisão da superfície da Terra numa grelha com 20x60 campos com 6ode largura, permitindo aproximar as coordenadas GPS dentro de cada campo a um plano cartesiano, permitindo medir distâncias entre dois pontos, assumindo-os num mesmo plano. A conversão de GPS para UTM é feita através das fórmulas presentes em [11]. 4.2 Comunicação direta A primeira topologia consiste no emissor e no recetor deslocarem-se em direção um do outro, efectuarem a comunicação e voltarem ao local original. A função que dá o tempo total da comunicação em função da distância a que se encontram os dois veículos é ttot =d−min(remissor,rrecetor) v+ttr p(4.1) 15 16 Topologias de Rede , onde ttot é o tempo total da comunicação, dé a distância entre os veículos, remissor errecetor são os raios do emissor e do recetor , respetivamente, vé a velocidade dos veículos, ttr é o tempo de transmissão da mensagem e pé a probabilidade de sucesso de uma dada tentativa de transmissão. 4.3 Comunicação Fixa Na segunda topologia, é estudada a possibilidade de estarem Nveículos entre o emissor e o recetor , de emodo a diminuir o tempo total de comunicação. Estes veículos estão, em repouso, distribuídos uniformemente entre o emissor e o recetor , de acordo com a figura 4.1. Cada veículo desloca-se em direção ao seu emissor, seguindo para o seu recetor , voltando, por fim, ao local de repouso. Na figura 4.1, a variável x, corresponde ao deslocamento do recetor de um dado veículo, enquanto este se desloca até ao emissor. É fácil deduzir que a função que relaciona o tempo total de transmissão e o número de veículos é independente desta varíavel, uma vez que, o tempo será sempre o mesmo para um dado número de veiculos interemedios, qualquer que seja o valor tomado por x. Figura 4.1: Disposição de N veiculos entre o emissor e o recetor no estado de repouso. O emissor encontra-se representado por um ponto verde e o recetor por um ponto vermelho. Os veículos encontram-se igualmente espaçados entre eles de modo a minimizar o caminho a percorrer. Na iteração em causa, o veículo je o seu emissor (o veículo j−1) deslocam-se em direção um do outro para estabelecer a comunicação. Enquanto isso acontece, o seu recetor (o veículo j+1) desloca-se na direção do veículo jpor uma distância x. 4.4 Uso de Um Veículo Bridge 17 Assim, a função que relaciona o tempo total de comunicação e o número de veículos é a seguinte. ttot =N+2 N+1×d v+ttr ×(N+1) p(4.2) sendo No número de veículos entre o emissor e o recetor . Sendo esta a função a minimizar, basta determinar-se a sua derivada e igualá-la a zero, obtendose a seguinte função: N=rd×p ttr ×v−1 (4.3) Sendo esta uma função f:R→Re sendo Num número inteiro, torna-se necessário calcular o valor da equação 4.3 para bNce para dNe, escolhendo o valor de i que dê o menor resultado. 4.4 Uso de Um Veículo Bridge Nesta topologia, assume-se uma rede distribuída de veículos onde o emissor e o recetor podem não estar dentro do alcance um do outro. Nesse caso, é escolhido um veículo livre para efectuar a ponte entre estes dois de modo a minimizar o tempo total de comunicação. Estando os N veículos em missão, considera-se, em cada iteração com comunicação, 3 casos diferentes para os 2 veículos envolvidos: 1. estão ambos dentro do raio de comunicação; 2. os raios de comunicação intersectam-se; 3. os raios de comunicação não se intersectam. No primeiro caso, ambos os veículos, estão automaticamente aptos para iniciar a comunicação. No segundo e terceiro casos, esta condição já não se verifica, sendo necessário um terceiro veículo para fazer a ponte, em diante denominado bridge . No segundo caso, o veículo bridge deve-se colocar, na linha que une os 2 veículos no ponto médio da intersecção dos raios de comunicação, que representa o centro da intersecção, seleccionandose para bridge , o veiculo que se encontrar mais próximo desse ponto. No terceiro caso, é necessário que o veículo bridge se desloque, primeiro em direcção à área de cobertura do veículo emissor e, após receber a mensagem a transmitir, deslocar se para o recetor . Neste caso, é seleccionado para bridge que percorra o menor caminho neste processo. Para determinar este caminho, existem 2 casos, dependendo do posicionamento entre os 3 veiculos, isto é, se a linha que une o veículo bridge e o recetor intersecta, ou não o raio de comunicação do veículo emissor. Para se determinar esta situação, verifica-se se a distância entre o emissor e essa linha é igual ou inferior ao raio de comunicação. Em caso afirmativo, verifica-se que a intersecção ocorre. 18 Topologias de Rede Se intersectar, essa linha representa o caminho mais curto a percorrer pelo veículo. Nesse caso, ele desloca-se até ao ponto de intersecção do caminho com a sua perpendicular que passa pelo ponto onde o emissor se localiza para receber a mensagem e depois, deslocar-se até conseguir transmitir a mensagem para o recetor , como se pode verificar na figura 4.2. Figura 4.2: Exemplo em que a linha que une o veículo bridge e o recetor intersecta o raio do emissor Em caso negativo, o veículo bridge terá de se deslocar até um ponto dentro do raio de comunicação do emissor e, após receber a mensagem, até ao recetor para a transmitir de tal modo que minimize o camino percorrido, como visto na figura 4.3. Neste caso, o caminho a percorrer será obtido da seguinte forma: 4.4 Uso de Um Veículo Bridge 19 Figura 4.3: Exemplo em que a linha que une o veículo bridge e o recetor não intersecta o raio do emissor d=   (1,0)se xrecetor <xbridge (−1,0)nos outros casos (4.4) D= (xemissor −xrecetor,yemissor −yrecetor)(4.5) α=arctanD(1) D(0)(4.6) β=arccosd·D ||d||||D||−θ−α(4.7) P1=   (xbridge ,ybridge )no primeiro caso (xemissor,yemissor)+(R1cos(Beta),R1sin(Beta)) no segundo caso (4.8) T=P1−(xrecetor,yrecetor)(4.9) γ=arctanT(1) T(0)(4.10) P2= (xrecetor,yrecetor)+(R1cos(γ),R1sin(γ)) (4.11) L1=q(xbridge −P1(0))2+(ybridge −P1(1))2(4.12) L2=q(P2(0)−P1(0))2+(P2(1)−P1(1))2(4.13) L=L1+L2(4.14) Sendo todos os valores, excepto θeβconstantes e βdependente de θatravés da equação (4.7), este torna-se num problema de optimização, tendo, como variável, o ângulo θ. 20 Topologias de Rede 4.5 A quarta topologia é uma mistura entre a primeira e a terceira topologias de modo a otimizálas. Em cada situação, é comparado o tempo total de comunicação em cada um desses algoritmos e é escolhida a ação em conformidade com o resultado. 4.6 Conclusão Neste capítulo foram apresentadas 4 topologias distintas para a comunicação dentro de uma rede. No capítulo 5será validado o terceiro algoritmo e no capítulo ?? as 4 topologias serão comparadas através de um ambiente de simulação que foi desenvolvido para o efeito. Capítulo 5 Validação de algoritmo 5.1 Introdução Neste capítulo será validado o algoritmo relativo à terceira topologia apresentada no capítulo 4; Relembrando, quando dois veiculos pretendem comunicar, caso não estejam dentro do raio de comunicação, é necessária a utilização de um veículo bridge . Nesse caso, dependendo da distância entre o emissor e o recetor , o veículo bridge terá de se deslocar para um ponto, se os raios de comunicação dos dois primeiros se interesectarem, ou dois, se não. Caso se interesectem, o veículo bridge deve-se deslocar para o centro da intersecção. Se não, dois casos sao possíveis de considerar. •A linha que une o veículo bridge e o recetor intersectam o raio de comunicação do emissor •A linha que une o veículo bridge e o recetor não intersectam o raio de comunicação do emissor Os dois pontos pelos quais o veículo bridge deve passar são dados pelas equações (4.4) a (4.11). Em qualquer dos casos, é selecionado, de entre os outros N-2 veículos, o que minimize a distância percorrida. No caso de intersecção entre os raios de comunicação do emissor e do recetor , esta distância percorrida é a distância entre o veículo bridge e o ponto para onde se deve deslocar. No outro caso, é calculada pelas equações (4.12)a(4.14). 5.2 Inicialização Para efeitos de simulação, os veículos foram modelizados pela sua posição (x,y) e pelo seu raio de comunicação. Existe, também uma área onde os barcos se podem movimentar que tem a 21 22 Validação de algoritmo forma quadrada e que é modelizada pelo tamanho do lado. O último modelo usado, é a ordem de comunicações que consiste numa matriz de tamanho NxN onde, na posição (i,j) contém o número de iterações que faltam ate o veiculo i comunicar com o veículo j. A inicialização da simulação é efectuada uma colocação aleatória dos N veículos dentro da área e da matriz de comunicações. Esta coloccação segue um modelo probabilístio uniforme entre os limites do mundo. O raio de comunicação também segue um modelo uniforme entre 25m e 50m. Durante esta inicialização é garantido, por motivos de simplificar, que dois barcos não tentam comunicar em simultâneo. Isto é alcançado através de uma matriz cujo índice ij é único e representa o número de iterações restantes para o veículo i comunicar com o veículo j. 5.3 Simulação Em cada iteração, é executada uma deslocação aleatória dos N veículos, garantindo que se mantém dentro da área disponível, seguido da determinação da comunicação a ser executada nessa iteração. Caso, não exista, passa-se à iteração seguinte. Determinando-se qual o emissor e o recetor da comunicação, armazenam-se os dados relativos a cada, nomeadamente, posição e raio de comunicação, e determina-se a intersecção dos mesmos, caso exista. Após esta acção, determina-se qual dos 3 casos enumerados no início da secção ?? e aplica-se o algoritmo descrito na mesma secção dependendo do caso. Por fim, é mostrado o resultado da iteração num gráfico com as seguintes características: •O emissor é apresentado com um ponto verde; •O recetor é apresentado com um ponto vermelho; •Todos os outros veículos são apresentados com pontos pretos; •O recetor é apresentado com um ponto vermelho; •Os raios de comunicação do emissor e do recetor são apresentados por circunferências azuis; •No casos de intersecção dos raios, esta é apresentada a vermelho sobre as circunferências azuis; •Caso seja necessário um veículo bridge , o caminho percorrido é apresentado com uma linha azul e o ponto onde termina é apresentado por um ponto azul. 5.4 Resultados Da simulação obtiveram-se os resultados pretendidos, sendo que, quando necessario, era seleccionado um veiculo para bridge , o qual se dirigia ao emissor, se não estivesse dentro do range e, posteriormente, ao recetor . 5.5 Conclusão 23 Para os resultados ilustrados, seguidamente nas figura 5.1, foi simulada a situação de 10 veículos numa área quadrada de 1000 pontos de lado. Figura 5.1: Resultado da simulação para os diferentes casos: a) Ambos os veículos encontram-se dentro do raio de comunicação, b) os raios de comunicação intersectam-se, sendo necessário um veículo bridge para efectuar a ponte, c) os raios de comunicação não se intersectam, estando, no entanto, o veículo bridge ao alcance do emissor, d) os raios de comunicação não se cruzam e é necessário o veículo bridge deslocar-se para o emissor antes de receber a mensagem 5.5 Conclusão Neste capítulo, foi apresentada a simulação da aplicação do algoritmo descrito no capítulo 4. Para a elaboração da simulação, foi usada uma função adaptada do código por Matt Fig, para desenhar a intersecção entre as circunferências e uma função escrita por Paulo Silva para determinar a intersecção entre dois segmentos de recta. 30 Algoritmos A.2 Aquisiçao de dados client = SSHClient() client.connect(router’s ip, username, password) ip = listener vehicle’s ip while not KeyboardInterrupt { value = client.exec_command(command to read power and noise in wireless connection) pos = Pos(port listener) pos.updateGPSCoord() lat, lon, alt = getPosOther(ip) other = Pos(lat = lat, lon = lon, alt = alt) distance = pos.getDistance(other) t = timestamp() writeToFile(timestamp, distance, power and noise) delay(1 sec) } A.3 Line Intersect lineintersect(l1,l2){ //l1 and l2 are segments of line of the form [P1X, P1Y, P2X, P2Y] m1 = slope of line 1 m2 = slope of line 2 b1 = y-intercept of line 1 b2 = y-intercept of line 2 b = [b1, b2] a = [1 -ml1; 1 -ml2] Pint = transpose of b * inverse of a //find maximum and minimum values for the final test l1minX=min([l1(1) l1(3)]) l2minX=min([l2(1) l2(3)]) l1minY=min([l1(2) l1(4)]) l2minY=min([l2(2) l2(4)]) l1maxX=max([l1(1) l1(3)]) l2maxX=max([l2(1) l2(3)]) l1maxY=max([l1(2) l1(4)]) l2maxY=max([l2(2) l2(4)]) //Test if the intersection is a point from the two lines because A.4 Plot Arc 31 //all the performed calculations were for infinite lines if ((x<l1minX) | (x>l1maxX) | (y<l1minY) | (y>l1maxY) | (x<l2minX) | (x>l2maxX) | (y<l2minY) | (y>l2maxY) ) return None else Return Pint } A.4 Plot Arc plot_arc(th1,th2,xc,yc,r){ //th1 and th2 are the start and end of the arc in radians //xc and yc are the center of the arc //r is the radius of the arc t = a row vector of 100 linearly equally spaced points between 0 and 2π x = r*cos(t) + xc; y = r*sin(t) + yc; P = draw(x,y,’r’); } 32 Algoritmos Referências [1] Reza Ghabcheloo. Coordinated Path Following of Multiple Autonomous Vehicles. Tese de doutoramento, Instituto Superior Tecnico de Lisboa, April 2007. [2] Gianluigi Pillonetto e Sandro Zampieri. Cooperative control and estimation algorithms. Relatório técnico, University of Padova, August 2008. [3] Johan Nilsson. Real-time control systems with delays. Tese de mestrado, Lund Institute of Technology, 1998. [4] Nuno A. Cruz et al. Implementation of an underwater acoustic network using multiple heterogeneous vehicles. 2012. [5] Paul L. Meyer. Probabilidade - Aplicacoes a Estatistica. Livros Tecnicos e Cientificos Editora, 2.a edição, 1987. [6] Andre Sa. Modelacao e controlo dinamico de uma embarcacao autonoma. Tese de mestrado, Faculdade de Engenharia da Universidade do Porto, Julho 2009. [7] Antonio Santos. Modelo de comunicacao OceanSys. OceanSys. [8] TRIMARES Software de bor do. [9] OceanSys. Tecnology – S y s t e m s and Prototypes. [Online]. [2011?] [ C i t a do 2013 Fev 13]; Disponível em: U R L : h tt p : // o c e a n s y s . f e . up . p t / t e c hno l o g y . php [10] B ur e a u I n t e rn a t i on a l des Poids et Mesures. T h e I n t e rn a t i on a l S y s t e m of Units (SI). [ O n li n e ] . 2006 [ c i t a do 2013 Fev 13]; Disponível e m : U R L : h tt p : // www . b i pm . or g / u t il s / c ommon / pd f / s i _ bro c hur e _ 8 _ e n . pd f [11]Universal Transverse Mercator coordinate system. [Online]. [ C i t a do 2013 Jun 17]; D i s pon í v e l em: U R L : h tt p : // e n . w i k i p e d i a . or g / w i k i / U n i v e r s a l _ T r a n s v e r s e _ M e r c a t or _ c oord i n a t e _ s y s t e m 33