Social-aware opportunistic routing

The increased capabilities (e.g., processing, storage) of portable devices along with the constant need of users to retrieve and send information have introduced a new form of communication. Users can seamlessly exchange data by means of opportunistic contacts among them and this is what characterizes the opportunistic networks (OppNets). OppNets allow users to communicate even when an end-to-end path may not exist between them. Since 2007, there has been a trend to improve the exchange of data by considering social similarity metrics. Social relationships, shared interests, and popularity are examples of such metrics that have been employed successfully: as users interact based on relationships and interests, this information can be used to decide on the best next forwarders of information. This Thesis work combines the features of today's devices found in the regular urban environment with the current social-awareness trend in the context of opportunistic routing. To achieve this goal, this work was divided into di erent tasks that map to a set of speci c objectives, leading to the following contributions: i) an up-to-date opportunistic routing taxonomy; ii) a universal evaluation framework that aids in devising and testing new routing proposals; iii) three social-aware utility functions that consider the dynamic user behavior and can be easily incorporated to other routing proposals; iv) two opportunistic routing proposals based on the users' daily routines and on the content traversing the network and interest of users in such content; and v) a structure analysis of the social-based network formed based on the approaches devised in this work.

Multilayer optimization in radio resource allocation for the packet transmission in wireless networks

Na última década tem-se assistido a um crescimento exponencial das redes de comunicações sem fios, nomeadamente no que se refere a taxa de penetração do serviço prestado e na implementação de novas infra-estruturas em todo o globo. É ponto assente neste momento que esta tendência irá não só continuar como se fortalecer devido à convergência que é esperada entre as redes móveis sem fio e a disponibilização de serviços de banda larga para a rede Internet fixa, numa evolução para um paradigma de uma arquitectura integrada e baseada em serviços e aplicações IP. Por este motivo, as comunicações móveis sem fios irão ter um papel fundamental no desenvolvimento da sociedade de informação a médio e longo prazos. A estratégia seguida no projecto e implementação das redes móveis celulares da actual geração (2G e 3G) foi a da estratificação da sua arquitectura protocolar numa estrutura modular em camadas estanques, onde cada camada do modelo é responsável pela implementação de um conjunto de funcionalidades. Neste modelo a comunicação dá-se apenas entre camadas adjacentes através de primitivas de comunicação pré-estabelecidas. Este modelo de arquitectura resulta numa mais fácil implementação e introdução de novas funcionalidades na rede. Entretanto, o facto das camadas inferiores do modelo protocolar não utilizarem informação disponibilizada pelas camadas superiores, e vice-versa acarreta uma degradação no desempenho do sistema. Este paradigma é particularmente importante quando sistemas de antenas múltiplas são implementados (sistemas MIMO). Sistemas de antenas múltiplas introduzem um grau adicional de liberdade no que respeita a atribuição de recursos rádio: o domínio espacial. Contrariamente a atribuição de recursos no domínio do tempo e da frequência, no domínio espacial os recursos rádio mapeados no domínio espacial não podem ser assumidos como sendo completamente ortogonais, devido a interferência resultante do facto de vários terminais transmitirem no mesmo canal e/ou slots temporais mas em feixes espaciais diferentes. Sendo assim, a disponibilidade de informação relativa ao estado dos recursos rádio às camadas superiores do modelo protocolar é de fundamental importância na satisfação dos critérios de qualidade de serviço exigidos. Uma forma eficiente de gestão dos recursos rádio exige a implementação de algoritmos de agendamento de pacotes de baixo grau de complexidade, que definem os níveis de prioridade no acesso a esses recursos por base dos utilizadores com base na informação disponibilizada quer pelas camadas inferiores quer pelas camadas superiores do modelo. Este novo paradigma de comunicação, designado por cross-layer resulta na maximização da capacidade de transporte de dados por parte do canal rádio móvel, bem como a satisfação dos requisitos de qualidade de serviço derivados a partir da camada de aplicação do modelo. Na sua elaboração, procurou-se que o standard IEEE 802.16e, conhecido por Mobile WiMAX respeitasse as especificações associadas aos sistemas móveis celulares de quarta geração. A arquitectura escalonável, o baixo custo de implementação e as elevadas taxas de transmissão de dados resultam num processo de multiplexagem de dados e valores baixos no atraso decorrente da transmissão de pacotes, os quais são atributos fundamentais para a disponibilização de serviços de banda larga. Da mesma forma a comunicação orientada à comutação de pacotes, inenente na camada de acesso ao meio, é totalmente compatível com as exigências em termos da qualidade de serviço dessas aplicações. Sendo assim, o Mobile WiMAX parece satisfazer os requisitos exigentes das redes móveis de quarta geração. Nesta tese procede-se à investigação, projecto e implementação de algoritmos de encaminhamento de pacotes tendo em vista a eficiente gestão do conjunto de recursos rádio nos domínios do tempo, frequência e espacial das redes móveis celulares, tendo como caso prático as redes móveis celulares suportadas no standard IEEE802.16e. Os algoritmos propostos combinam métricas provenientes da camada física bem como os requisitos de qualidade de serviço das camadas superiores, de acordo com a arquitectura de redes baseadas no paradigma do cross-layer. O desempenho desses algoritmos é analisado a partir de simulações efectuadas por um simulador de sistema, numa plataforma que implementa as camadas física e de acesso ao meio do standard IEEE802.16e.

Sistema computacional para o estudo da estrutura primária e redesenho de genes

Um dos maiores avanços científicos do século XX foi o desenvolvimento de tecnologia que permite a sequenciação de genomas em larga escala. Contudo, a informação produzida pela sequenciação não explica por si só a sua estrutura primária, evolução e seu funcionamento. Para esse fim novas áreas como a biologia molecular, a genética e a bioinformática são usadas para estudar as diversas propriedades e funcionamento dos genomas. Com este trabalho estamos particularmente interessados em perceber detalhadamente a descodificação do genoma efectuada no ribossoma e extrair as regras gerais através da análise da estrutura primária do genoma, nomeadamente o contexto de codões e a distribuição dos codões. Estas regras estão pouco estudadas e entendidas, não se sabendo se poderão ser obtidas através de estatística e ferramentas bioinfomáticas. Os métodos tradicionais para estudar a distribuição dos codões no genoma e seu contexto não providenciam as ferramentas necessárias para estudar estas propriedades à escala genómica. As tabelas de contagens com as distribuições de codões, assim como métricas absolutas, estão actualmente disponíveis em bases de dados. Diversas aplicações para caracterizar as sequências genéticas estão também disponíveis. No entanto, outros tipos de abordagens a nível estatístico e outros métodos de visualização de informação estavam claramente em falta. No presente trabalho foram desenvolvidos métodos matemáticos e computacionais para a análise do contexto de codões e também para identificar zonas onde as repetições de codões ocorrem. Novas formas de visualização de informação foram também desenvolvidas para permitir a interpretação da informação obtida. As ferramentas estatísticas inseridas no modelo, como o clustering, análise residual, índices de adaptação dos codões revelaram-se importantes para caracterizar as sequências codificantes de alguns genomas. O objectivo final é que a informação obtida permita identificar as regras gerais que governam o contexto de codões em qualquer genoma.

Caracterização molecular de cianobactérias de sistemas aquáticos portugueses

As alterações climáticas favorecem a ocorrência global de episódios de precipitação e seca extremas, colocando em risco a qualidade da água em sistemas aquáticos usados consumo humano ou recreação. O fenómeno de seca, em particular, será mais frequente e severo, alterando toda a hidrodinâmica dos sistemas aquáticos e, consequentemente, a ecologia das comunidades aquáticas. A ocorrência de blooms de cianobactérias intensificarse- á sob este novo cenário climático. Em Portugal, estudos parcelares em rios e barragens têm sido realizados com enfoque em cianobactérias tóxicas e outras bactérias patogénicas, mas não há trabalhos publicados acerca da composição da comunidade bacteriana (CCB). O presente trabalho pretende colmatar esta falha, com particular atenção para a ocorrência de blooms cianobacterianos, em vários sistemas aquáticos portugueses lóticos e lênticos. Este objectivo foi alcançado utilizando metodologias moleculares, como a técnica rDNA 16S-DGGE (Denaturing Gradient Gel Electrophoresis), independente do cultivo, e a sequenciação. Dados ambientais foram também determinados para correlacionar com as variações sazonais ou espaciais da diversidade da CCB. O impacto da seca na distribuição espacial da CCB foi também investigado. A lagoa da Vela é um caso de estudo especial, devido à vasta documentação sobre a ocorrência de blooms de cianobactérias durante os últimos anos, e várias estirpes isoladas de blooms foram estudadas em mais detalhe. Os resultados mostraram, em geral, perfis de DGGE típicos de verão vs. inverno nos sistemas aquáticos estudados. Nos sistemas lênticos, os filótipos dominantes afiliaram com Cyanobacteria (formas unicelulares, coloniais e filamentosas), eucariotas fototróficos e Actinobacteria, enquanto nos rios, Bacteroidetes e Betaproteobacteria foram dominantes. Nos sistemas lênticos, os factores mais significativos para a sazonalidade da CCB incluíram a temperatura da água, a condutividade e a clorofila a, apesar da variação extrema dos níveis de precipitação, sugerindo que a BCC poderá resistir a mudanças severas causadas pela seca. Nos rios, a sazonalidade da CCB foi principalmente definida pela temperatura e os níveis de amónia. No verão seco de 2005, as barragens do Alentejo (Sul de Portugal) mostraram similaridade na CCB, com filótipos comuns de Cyanobacteria, Actinobacteria e Alphaproteobacteria. No entanto, os perfis de DGGE sugerem filótipos ubíquos em sistemas portugueses geograficamente distantes. Na Lagoa da Vela, a seca conduziu à redução drástica do nível da água e à variação na diversidade espacial da CCB (e cianobactérias dominantes) e potencial tóxico, o que pode ter impacto directo nos utilizadores da lagoa. Os resultados também mostraram a presença de estirpes tóxicas de Microcystis na lagoa e um bloom não clonal de estirpes de Aphanizomenon aphanizomenoides, com diferentes morfótipos, genótipos e ecótipos.

Macroinvertebrate traits as biomonitoring tools in agricultural scenarios

Os ecossistemas de água doce – responsáveis por funções ambientais importantes e pelo fornecimento de bens e serviços insubstituíveis – têm vindo a ser severamente afectados por perturbações antropogénicas. A conversão de floresta em terreno agrícola afecta os sistemas aquáticos através de uma série de mecanismos: sedimentação; excesso de nutrientes; contaminação; alterações hidrológicas; e remoção de vegetação ripícola. As comunidades de macroinvertebrados de água doce – devido à sua diversidade, ubiquidade e sensibilidade às perturbações ambientais – revelam-se como particularmente adequadas para estudos de avaliação da integridade ecológica destes sistemas expostos simultaneamente a múltiplos factores de impacto. O uso sistemático de respostas biológicas para avaliação de mudanças ambientais – ou biomonitorização – pode ser levado a cabo através de diversas metodologias, que, de uma forma geral, não consideram aspectos funcionais das comunidades biológicas e têm aplicabilidade geograficamente restrita. A biomonitorização através de atributos biológicos (características que reflectem a adaptação das espécies ao seu meio ambiente) revela-se como uma ferramenta promissora na resolução dos problemas referidos, apresentando vantagens adicionais: relações causa-efeito directas; melhoria na diferenciação de impactos; e integração da variabilidade natural. O presente estudo apresenta uma revisão critica do estado-da-arte actual na área do uso de atributos biológicos em biomonitorização. Até à data de publicação, não estava disponível nenhum outro trabalho com a base conceptual do uso de atributos de macroinvertebrados enquanto descritores de comunidades e para efeitos de biomonitorização e gestão de sistemas de água doce. Descrevem-se as teorias ecológicas de suporte destas metodologias (conceitos de habitat-molde e de filtros paisagísticos) e os estudos que aplicaram estas teorias em cenários reais, tendo-se chamado a atenção para questões técnicas e possíveis soluções. As necessidades futuras nesta área englobam: o desenvolvimento de uma só ferramenta de biomonitorização de aplicação alargada; uma maior compreensão da variabilidade natural nas comunidades biológicas; diminuição dos efeitos de soluções de compromisso biológico e sindromas; realização de estudos autoecológicos adicionais; e detecção de impactos específicos em cenários de impacto complexos. Um dos objectivos deste estudo foi contribuir para a melhoria das técnicas de biomonitorização através de atributos, focalizando em comunidades de macroinvertebrados ribeirinhas em diferentes regiões biogeográficas (as bacias hidrográficas dos rios: Little e Salmon em New Brunswick, Canadá; Anllóns na Galiza, Espanha; Reventazón em Cartago, Costa Rica). Em cada região, foram estudados gradientes de uso agrícola de solo, incluindo desde bacias hidrográficas quase exclusivamente cobertas por floresta até bacias sob a influência maioritária de actividades agrícolas intensivas. Em cada gradiente de uso de solo, a caracterização da comunidade biológica (por amostragem de macroinvertebrados em troços de rápidos) foi acompanhada pela caracterização do habitat circundante (incluindo propriedades da bacia hidrográfica, análise química das águas e outras propriedades à escala local). A comunidade de macroinvertebrados foi caracterizada através de informação taxonómica, métricas estruturais, índices de diversidade, métricas de tolerância, índices bióticos e através da compilação de atributos biológicos e fisiológicos gerais, de história de vida e de resistência a perturbações. Análises estatísticas univariadas e multivariadas foram usadas para evidenciar os gradientes biológicos e físico-químicos, confirmar a sua co-variação, testar a significância da discriminação de níveis de impacto e estabelecer comparações inter-regionais. A estrutura de comunidades revelou os complexos gradientes de impacto, que por sua vez co-variaram significativamente com os gradientes de uso de solo. Os gradientes de impacto relacionaram-se sobretudo com entrada de nutrientes e sedimentação. Os gradientes biológicos definidos pelas medidas estruturais seleccionadas co-variaram com os gradientes de impacto estudados, muito embora apenas algumas variáveis estruturais tenham individualmente discriminado as categorias de uso de solo definidas a priori. Não foi detectada consistência nas respostas das medidas estruturais entre regiões biogeográficas, tendo-se confirmadado que as interpretações puramente taxonómicas de impactos são difíceis de extrapolar entre regiões. Os gradientes biológicos definidos através dos atributos seleccionados também co-variaram com os gradientes de perturbação, tendo sido possível obter uma melhor discriminação de categorias de uso de solo. Nas diferentes regiões, a discriminação de locais mais impactados foi feita com base num conjunto similar de atributos, que inclui tamanho, voltinismo, técnicas reproductivas, microhabitat, preferências de corrente e substrato, hábitos alimentares e formas de resistência. Este conjunto poderá vir a ser usado para avaliar de forma predictiva os efeitos das modificações severas de uso de solo impostas pela actividade agrícola. Quando analisadas simultaneamente através dos atributos, as comunidades das três regiões permitiram uma moderada mas significativa discriminação de níveis de impacto. Estas análises corroboram as evidências de que as mudanças nas comunidades de macroinvertebrados aquáticos em locais sob a influência de agricultura intensiva podem seguir uma trajectória convergente no espaço multidimensional, independentemente de factores geográficos. Foram fornecidas pistas para a identificação de parâmetros específicos que deverão ser tidos em conta no planeamento de novos programas de biomonitorização com comunidades de macroinvertebrados bentónicos, para aplicação numa gestão fluvial verdadeiramente ecológica, nestas e noutras regiões. Foram ainda sugeridas possíveis linhas futuras de investigação.

Morphological and ecological studies on the phylum Cycliophora

Cycliophora é um filo animal descrito recentemente que acomoda, apenas, duas espécies: Symbion pandora Funch e Kristensen, 1995 e S. americanus Obst, Funch e Kristensen, 2006. Este filo é caracterizado por um ciclo de vida assaz complexo, cuja posição filogenética tem sido debatida desde a sua descoberta. Esta dissertação visa aprofundar o conhecimento geral existente acerca destes enigmáticos e pouco explorados metazoários. Assim, vários aspectos da morfologia e ecologia de ciclióforos foram estudados através de observações in vivo, técnicas de microscopia e reconstrução tridimensional. A mioanatomia de várias fases do ciclo de vida é descrita para S. pandora e S. americanus. Os nossos resultados revelam uma similaridade contundente entre a musculatura das duas espécies. A mioanatomia geral de Symbion é, ainda, comparada à de outros metazoários. A expressão de algumas substâncias imunorreactivas, como são exemplo a serotonina e as sinapsinas, é investigada em várias formas do ciclo de vida. Quando comparados com outros representantes de Spiralia, conclui-se que a neuroanatomia geral dos ciclióforos se assemelha mais às formas larvares do que aos adultos. Apesar de possuírem um plano corporal sofisticado, com extensas áreas ciliadas e uma mioanatomia complexa, descobrimos que o macho de ambas as espécies Symbion é composto por apenas algumas dezenas de células. Baseando-nos nestas observações, inferimos que a complexidade dos metazoários não se relaciona com o tamanho corporal nem com o número de células de um organismo. Estudos sobre a ultra-estrutura da fêmea revelaram, entre outras estruturas, um putativo poro genital, extensões citoplasmáticas do oócito e glândulas posteriores. Morfologia e implicações funcionais destas estruturas são aqui discutidas. A anatomia do protonefrídeo da larva cordóide é descrita. A arquitectura deste órgão diverge daquela presente noutros representantes de Nephrozoa, particularmente ao nível da área de filtração da célula terminal. As nossas observações são discutidas em termos filogenéticos. A maturação sexual em ciclióforos é investigada. Os nossos resultados sugerem que a transição de reprodução assexual a sexual se relacione com a idade da forma séssil, a “feeding stage”. A presença da larva Prometeus assente no tronco desta também poderá influenciar o processo, embora mais estudos sejam desejáveis para o comprovar. Os nossos resultados são discutidos integrativa e comparativamente com o conhecimento prévio sobre Cycliophora. A cumulação deste conhecimento será essencial para a compreensão da evolução e filogenia deste enigmático filo.

Left ventricle functional analysis from coronary CT angiography

Coronary CT angiography is widely used in clinical practice for the assessment of coronary artery disease. Several studies have shown that the same exam can also be used to assess left ventricle (LV) function. LV function is usually evaluated using just the data from end-systolic and end-diastolic phases even though coronary CT angiography (CTA) provides data concerning multiple cardiac phases, along the cardiac cycle. This unused wealth of data, mostly due to its complexity and the lack of proper tools, has still to be explored in order to assess if further insight is possible regarding regional LV functional analysis. Furthermore, different parameters can be computed to characterize LV function and while some are well known by clinicians others still need to be evaluated concerning their value in clinical scenarios. The work presented in this thesis covers two steps towards extended use of CTA data: LV segmentation and functional analysis. A new semi-automatic segmentation method is presented to obtain LV data for all cardiac phases available in a CTA exam and a 3D editing tool was designed to allow users to fine tune the segmentations. Regarding segmentation evaluation, a methodology is proposed in order to help choose the similarity metrics to be used to compare segmentations. This methodology allows the detection of redundant measures that can be discarded. The evaluation was performed with the help of three experienced radiographers yielding low intraand inter-observer variability. In order to allow exploring the segmented data, several parameters characterizing global and regional LV function are computed for the available cardiac phases. The data thus obtained is shown using a set of visualizations allowing synchronized visual exploration. The main purpose is to provide means for clinicians to explore the data and gather insight over their meaning, as well as their correlation with each other and with diagnosis outcomes. Finally, an interactive method is proposed to help clinicians assess myocardial perfusion by providing automatic assignment of lesions, detected by clinicians, to a myocardial segment. This new approach has obtained positive feedback from clinicians and is not only an improvement over their current assessment method but also an important first step towards systematic validation of automatic myocardial perfusion assessment measures.

Cooperative communications in multi-rate IEEE 802.11 networks

Esta tese apresenta um estudo sobre alguns dos protocolos de cooperação MAC para redes sem fios utilizando o sistema IEEE 802.11 multi-débito. É proposto um novo modelo de arquitetura para a categorização e análise da cooperação em redes sem fios, tendo este modelo sido aplicado a protocolos cooperativos existentes para camada MAC. É investigado como as características do meio físico, assim como os requisitos de níveis superiores podem ser aplicados ao processo de cooperação, com vista a melhorar as características de funcionamento da rede de comunicações. Para este propósito são exploradas as métricas mais relevantes para o processo de cooperação. São igualmente estudados os limites impostos pelos protocolos da camada MAC e as limitações práticas impostas por protocolos da família de normas que compõem o IEEE 802.11. Neste trabalho foi criada uma métrica multicamada, que permite considerar os requisitos aplicacionais de performance e o tipo de tráfego, assim como a mobilidade dos dispositivos, no funcionamento dos mecanismos de cooperação. Como forma de validação, e para corretamente avaliar o impacto da métrica, um novo protocolo de cooperação foi desenvolvido e implementado. O seu funcionamento é descrito de forma analítica assim como validado através de a um ambiente de simulação. Os resultados obtidos mostram que a utilização de uma métrica multicamada é uma técnica robusta, fornecendo melhorias consistentes no contexto de redes IEEE 802.11. São igualmente demonstradas várias outras características de funcionamento com impacto para as comunicações. Estes dados fornecem uma visão real e encorajadora para a realização de mais pesquisas para a melhoria da performance dos protocolos cooperativos, assim como a sua utilização num variado número de aplicações futuras. No final do documento são apresentados alguns desafios para a continuação da investigação deste tópico.

Cooperative positioning for heterogeneous wireless systems

Future emerging market trends head towards positioning based services placing a new perspective on the way we obtain and exploit positioning information. On one hand, innovations in information technology and wireless communication systems enabled the development of numerous location based applications such as vehicle navigation and tracking, sensor networks applications, home automation, asset management, security and context aware location services. On the other hand, wireless networks themselves may bene t from localization information to improve the performances of di erent network layers. Location based routing, synchronization, interference cancellation are prime examples of applications where location information can be useful. Typical positioning solutions rely on measurements and exploitation of distance dependent signal metrics, such as the received signal strength, time of arrival or angle of arrival. They are cheaper and easier to implement than the dedicated positioning systems based on ngerprinting, but at the cost of accuracy. Therefore intelligent localization algorithms and signal processing techniques have to be applied to mitigate the lack of accuracy in distance estimates. Cooperation between nodes is used in cases where conventional positioning techniques do not perform well due to lack of existing infrastructure, or obstructed indoor environment. The objective is to concentrate on hybrid architecture where some nodes have points of attachment to an infrastructure, and simultaneously are interconnected via short-range ad hoc links. The availability of more capable handsets enables more innovative scenarios that take advantage of multiple radio access networks as well as peer-to-peer links for positioning. Link selection is used to optimize the tradeo between the power consumption of participating nodes and the quality of target localization. The Geometric Dilution of Precision and the Cramer-Rao Lower Bound can be used as criteria for choosing the appropriate set of anchor nodes and corresponding measurements before attempting location estimation itself. This work analyzes the existing solutions for node selection in order to improve localization performance, and proposes a novel method based on utility functions. The proposed method is then extended to mobile and heterogeneous environments. Simulations have been carried out, as well as evaluation with real measurement data. In addition, some speci c cases have been considered, such as localization in ill-conditioned scenarios and the use of negative information. The proposed approaches have shown to enhance estimation accuracy, whilst signi cantly reducing complexity, power consumption and signalling overhead.

Contributos para a eficácia do clustering usando o tagging social

Nos últimos anos temos vindo a assistir a uma mudança na forma como a informação é disponibilizada online. O surgimento da web para todos possibilitou a fácil edição, disponibilização e partilha da informação gerando um considerável aumento da mesma. Rapidamente surgiram sistemas que permitem a coleção e partilha dessa informação, que para além de possibilitarem a coleção dos recursos também permitem que os utilizadores a descrevam utilizando tags ou comentários. A organização automática dessa informação é um dos maiores desafios no contexto da web atual. Apesar de existirem vários algoritmos de clustering, o compromisso entre a eficácia (formação de grupos que fazem sentido) e a eficiência (execução em tempo aceitável) é difícil de encontrar. Neste sentido, esta investigação tem por problemática aferir se um sistema de agrupamento automático de documentos, melhora a sua eficácia quando se integra um sistema de classificação social. Analisámos e discutimos dois métodos baseados no algoritmo k-means para o clustering de documentos e que possibilitam a integração do tagging social nesse processo. O primeiro permite a integração das tags diretamente no Vector Space Model e o segundo propõe a integração das tags para a seleção das sementes iniciais. O primeiro método permite que as tags sejam pesadas em função da sua ocorrência no documento através do parâmetro Social Slider. Este método foi criado tendo por base um modelo de predição que sugere que, quando se utiliza a similaridade dos cossenos, documentos que partilham tags ficam mais próximos enquanto que, no caso de não partilharem, ficam mais distantes. O segundo método deu origem a um algoritmo que denominamos k-C. Este para além de permitir a seleção inicial das sementes através de uma rede de tags também altera a forma como os novos centróides em cada iteração são calculados. A alteração ao cálculo dos centróides teve em consideração uma reflexão sobre a utilização da distância euclidiana e similaridade dos cossenos no algoritmo de clustering k-means. No contexto da avaliação dos algoritmos foram propostos dois algoritmos, o algoritmo da “Ground truth automática” e o algoritmo MCI. O primeiro permite a deteção da estrutura dos dados, caso seja desconhecida, e o segundo é uma medida de avaliação interna baseada na similaridade dos cossenos entre o documento mais próximo de cada documento. A análise de resultados preliminares sugere que a utilização do primeiro método de integração das tags no VSM tem mais impacto no algoritmo k-means do que no algoritmo k-C. Além disso, os resultados obtidos evidenciam que não existe correlação entre a escolha do parâmetro SS e a qualidade dos clusters. Neste sentido, os restantes testes foram conduzidos utilizando apenas o algoritmo k-C (sem integração de tags no VSM), sendo que os resultados obtidos indicam que a utilização deste algoritmo tende a gerar clusters mais eficazes.

Perception and software architecture for mobile robotics

When developing software for autonomous mobile robots, one has to inevitably tackle some kind of perception. Moreover, when dealing with agents that possess some level of reasoning for executing their actions, there is the need to model the environment and the robot internal state in a way that it represents the scenario in which the robot operates. Inserted in the ATRI group, part of the IEETA research unit at Aveiro University, this work uses two of the projects of the group as test bed, particularly in the scenario of robotic soccer with real robots. With the main objective of developing algorithms for sensor and information fusion that could be used e ectively on these teams, several state of the art approaches were studied, implemented and adapted to each of the robot types. Within the MSL RoboCup team CAMBADA, the main focus was the perception of ball and obstacles, with the creation of models capable of providing extended information so that the reasoning of the robot can be ever more e ective. To achieve it, several methodologies were analyzed, implemented, compared and improved. Concerning the ball, an analysis of ltering methodologies for stabilization of its position and estimation of its velocity was performed. Also, with the goal keeper in mind, work has been done to provide it with information of aerial balls. As for obstacles, a new de nition of the way they are perceived by the vision and the type of information provided was created, as well as a methodology for identifying which of the obstacles are team mates. Also, a tracking algorithm was developed, which ultimately assigned each of the obstacles a unique identi er. Associated with the improvement of the obstacles perception, a new algorithm of estimating reactive obstacle avoidance was created. In the context of the SPL RoboCup team Portuguese Team, besides the inevitable adaptation of many of the algorithms already developed for sensor and information fusion and considering that it was recently created, the objective was to create a sustainable software architecture that could be the base for future modular development. The software architecture created is based on a series of di erent processes and the means of communication among them. All processes were created or adapted for the new architecture and a base set of roles and behaviors was de ned during this work to achieve a base functional framework. In terms of perception, the main focus was to de ne a projection model and camera pose extraction that could provide information in metric coordinates. The second main objective was to adapt the CAMBADA localization algorithm to work on the NAO robots, considering all the limitations it presents when comparing to the MSL team, especially in terms of computational resources. A set of support tools were developed or improved in order to support the test and development in both teams. In general, the work developed during this thesis improved the performance of the teams during play and also the e ectiveness of the developers team when in development and test phases.