Geometric optimization on visibility problems: metaheuristic and exact solutions

Os problemas de visibilidade têm diversas aplicações a situações reais. Entre os mais conhecidos, e exaustivamente estudados, estão os que envolvem os conceitos de vigilância e ocultação em estruturas geométricas (problemas de vigilância e ocultação). Neste trabalho são estudados problemas de visibilidade em estruturas geométricas conhecidas como polígonos, uma vez que estes podem representar, de forma apropriada, muitos dos objectos reais e são de fácil manipulação computacional. O objectivo dos problemas de vigilância é a determinação do número mínimo de posições para a colocação de dispositivos num dado polígono, de modo a que estes dispositivos consigam “ver” a totalidade do polígono. Por outro lado, o objectivo dos problemas de ocultação é a determinação do número máximo de posições num dado polígono, de modo a que quaisquer duas posições não se consigam “ver”. Infelizmente, a maior parte dos problemas de visibilidade em polígonos são NP-difíceis, o que dá origem a duas linhas de investigação: o desenvolvimento de algoritmos que estabelecem soluções aproximadas e a determinação de soluções exactas para classes especiais de polígonos. Atendendo a estas duas linhas de investigação, o trabalho é dividido em duas partes. Na primeira parte são propostos algoritmos aproximados, baseados essencialmente em metaheurísticas e metaheurísticas híbridas, para resolver alguns problemas de visibilidade, tanto em polígonos arbitrários como ortogonais. Os problemas estudados são os seguintes: “Maximum Hidden Vertex Set problem”, “Minimum Vertex Guard Set problem”, “Minimum Vertex Floodlight Set problem” e “Minimum Vertex k-Modem Set problem”. São também desenvolvidos métodos que permitem determinar a razão de aproximação dos algoritmos propostos. Para cada problema são implementados os algoritmos apresentados e é realizado um estudo estatístico para estabelecer qual o algoritmo que obtém as melhores soluções num tempo razoável. Este estudo permite concluir que as metaheurísticas híbridas são, em geral, as melhores estratégias para resolver os problemas de visibilidade estudados. Na segunda parte desta dissertação são abordados os problemas “Minimum Vertex Guard Set”, “Maximum Hidden Set” e “Maximum Hidden Vertex Set”, onde são identificadas e estudadas algumas classes de polígonos para as quais são determinadas soluções exactas e/ou limites combinatórios.

Majorantes para a ordem de subgrafos induzidos k-regulares

Muitos dos problemas de otimização em grafos reduzem-se à determinação de um subconjunto de vértices de cardinalidade máxima que induza um subgrafo k-regular. Uma vez que a determinação da ordem de um subgrafo induzido k-regular de maior ordem é, em geral, um problema NP-difícil, são deduzidos novos majorantes, a determinar em tempo polinomial, que em muitos casos constituam boas aproximações das respetivas soluções ótimas. Introduzem-se majorantes espetrais usando uma abordagem baseada em técnicas de programação convexa e estabelecem-se condições necessárias e suficientes para que sejam atingidos. Adicionalmente, introduzem-se majorantes baseados no espetro das matrizes de adjacência, laplaciana e laplaciana sem sinal. É ainda apresentado um algoritmo não polinomial para a determinação de umsubconjunto de vértices de umgrafo que induz umsubgrafo k-regular de ordem máxima para uma classe particular de grafos. Finalmente, faz-se um estudo computacional comparativo com vários majorantes e apresentam-se algumas conclusões.

Network virtualisation from an operator perspective

Network virtualisation is seen as a promising approach to overcome the so-called “Internet impasse” and bring innovation back into the Internet, by allowing easier migration towards novel networking approaches as well as the coexistence of complementary network architectures on a shared infrastructure in a commercial context. Recently, the interest from the operators and mainstream industry in network virtualisation has grown quite significantly, as the potential benefits of virtualisation became clearer, both from an economical and an operational point of view. In the beginning, the concept has been mainly a research topic and has been materialized in small-scale testbeds and research network environments. This PhD Thesis aims to provide the network operator with a set of mechanisms and algorithms capable of managing and controlling virtual networks. To this end, we propose a framework that aims to allocate, monitor and control virtual resources in a centralized and efficient manner. In order to analyse the performance of the framework, we performed the implementation and evaluation on a small-scale testbed. To enable the operator to make an efficient allocation, in real-time, and on-demand, of virtual networks onto the substrate network, it is proposed a heuristic algorithm to perform the virtual network mapping. For the network operator to obtain the highest profit of the physical network, it is also proposed a mathematical formulation that aims to maximize the number of allocated virtual networks onto the physical network. Since the power consumption of the physical network is very significant in the operating costs, it is important to make the allocation of virtual networks in fewer physical resources and onto physical resources already active. To address this challenge, we propose a mathematical formulation that aims to minimize the energy consumption of the physical network without affecting the efficiency of the allocation of virtual networks. To minimize fragmentation of the physical network while increasing the revenue of the operator, it is extended the initial formulation to contemplate the re-optimization of previously mapped virtual networks, so that the operator has a better use of its physical infrastructure. It is also necessary to address the migration of virtual networks, either for reasons of load balancing or for reasons of imminent failure of physical resources, without affecting the proper functioning of the virtual network. To this end, we propose a method based on cloning techniques to perform the migration of virtual networks across the physical infrastructure, transparently, and without affecting the virtual network. In order to assess the resilience of virtual networks to physical network failures, while obtaining the optimal solution for the migration of virtual networks in case of imminent failure of physical resources, the mathematical formulation is extended to minimize the number of nodes migrated and the relocation of virtual links. In comparison with our optimization proposals, we found out that existing heuristics for mapping virtual networks have a poor performance. We also found that it is possible to minimize the energy consumption without penalizing the efficient allocation. By applying the re-optimization on the virtual networks, it has been shown that it is possible to obtain more free resources as well as having the physical resources better balanced. Finally, it was shown that virtual networks are quite resilient to failures on the physical network.

O problema da árvore de suporte de custo mínimo com restrições de peso

Nesta tese abordam-se várias formulações e diferentes métodos para resolver o Problema da Árvore de Suporte de Custo Mínimo com Restrições de Peso (WMST – Weight-constrained Minimum Spanning Tree Problem). Este problema, com aplicações no desenho de redes de comunicações e telecomunicações, é um problema de Otimização Combinatória NP-difícil. O Problema WMST consiste em determinar, numa rede com custos e pesos associados às arestas, uma árvore de suporte de custo mínimo de tal forma que o seu peso total não exceda um dado limite especificado. Apresentam-se e comparam-se várias formulações para o problema. Uma delas é usada para desenvolver um procedimento com introdução de cortes baseado em separação e que se tornou bastante útil na obtenção de soluções para o problema. Tendo como propósito fortalecer as formulações apresentadas, introduzem-se novas classes de desigualdades válidas que foram adaptadas das conhecidas desigualdades de cobertura, desigualdades de cobertura estendida e desigualdades de cobertura levantada. As novas desigualdades incorporam a informação de dois conjuntos de soluções: o conjunto das árvores de suporte e o conjunto saco-mochila. Apresentam-se diversos algoritmos heurísticos de separação que nos permitem usar as desigualdades válidas propostas de forma eficiente. Com base na decomposição Lagrangeana, apresentam-se e comparam-se algoritmos simples, mas eficientes, que podem ser usados para calcular limites inferiores e superiores para o valor ótimo do WMST. Entre eles encontram-se dois novos algoritmos: um baseado na convexidade da função Lagrangeana e outro que faz uso da inclusão de desigualdades válidas. Com o objetivo de obter soluções aproximadas para o Problema WMST usam-se métodos heurísticos para encontrar uma solução inteira admissível. Os métodos heurísticos apresentados são baseados nas estratégias Feasibility Pump e Local Branching. Apresentam-se resultados computacionais usando todos os métodos apresentados. Os resultados mostram que os diferentes métodos apresentados são bastante eficientes para encontrar soluções para o Problema WMST.

Enhanced ethernet switching technology for adaptive hard real-time applications: Tecnologia de comutação ethernet melhorada para aplicações adaptativas e críticas de tempo-real

Os Sistemas Embarcados Distribuídos (SEDs) estão, hoje em dia, muito difundidos em vastas áreas, desde a automação industrial, a automóveis, aviões, até à distribuição de energia e protecção do meio ambiente. Estes sistemas são, essencialmente, caracterizados pela integração distribuída de aplicações embarcadas, autónomas mas cooperantes, explorando potenciais vantagens em termos de modularidade, facilidade de manutenção, custos de instalação, tolerância a falhas, entre outros. Contudo, o ambiente operacional onde se inserem estes tipos de sistemas pode impor restrições temporais rigorosas, exigindo que o sistema de comunicação subjacente consiga transmitir mensagens com garantias temporais. Contudo, os SEDs apresentam uma crescente complexidade, uma vez que integram subsistemas cada vez mais heterogéneos, quer ao nível do tráfego gerado, quer dos seus requisitos temporais. Em particular, estes subsistemas operam de forma esporádica, isto é, suportam mudanças operacionais de acordo com estímulos exteriores. Estes subsistemas também se reconfiguram dinamicamente de acordo com a actualização dos seus requisitos e, ainda, têm lidar com um número variável de solicitações de outros subsistemas. Assim sendo, o nível de utilização de recursos pode variar e, desta forma, as políticas de alocação estática tornam-se muito ineficientes. Consequentemente, é necessário um sistema de comunicação capaz de suportar com eficácia reconfigurações e adaptações dinâmicas. A tecnologia Ethernet comutada tem vindo a emergir como uma solução sólida para fornecer comunicações de tempo-real no âmbito dos SEDs, como comprovado pelo número de protocolos de tempo-real que foram desenvolvidos na última década. No entanto, nenhum dos protocolos existentes reúne as características necessárias para fornecer uma eficiente utilização da largura de banda e, simultaneamente, para respeitar os requisitos impostos pelos SEDs. Nomeadamente, a capacidade para controlar e policiar tráfego de forma robusta, conjugada com suporte à reconfiguração e adaptação dinâmica, não comprometendo as garantias de tempo-real. Esta dissertação defende a tese de que, pelo melhoramento dos comutadores Ethernet para disponibilizarem mecanismos de reconfiguração e isolamento de tráfego, é possível suportar aplicações de tempo-real críticas, que são adaptáveis ao ambiente onde estão inseridas.Em particular, é mostrado que as técnicas de projecto, baseadas em componentes e apoiadas no escalonamento hierárquico de servidores de tráfego, podem ser integradas nos comutadores Ethernet para alcançar as propriedades desejadas. Como suporte, é fornecida, também, uma solução para instanciar uma hierarquia reconfigurável de servidores de tráfego dentro do comutador, bem como a análise adequada ao modelo de escalonamento. Esta última fornece um limite superior para o tempo de resposta que os pacotes podem sofrer dentro dos servidores de tráfego, com base unicamente no conhecimento de um dado servidor e na hierarquia actual, isto é, sem o conhecimento das especifidades do tráfego dentro dos outros servidores. Finalmente, no âmbito do projecto HaRTES foi construído um protótipo do comutador Ethernet, o qual é baseado no paradigma “Flexible Time-Triggered”, que permite uma junção flexível de uma fase síncrona para o tráfego controlado pelo comutador e uma fase assíncrona que implementa a estrutura hierárquica de servidores referidos anteriormente. Além disso, as várias experiências práticas realizadas permitiram validar as propriedades desejadas e, consequentemente, a tese que fundamenta esta dissertação.

Synthesis and functionalization of hydroxyapatite nanoparticles

Graças aos desenvolvimentos na área da síntese de nanomaterais e às potentes técnicas de caracterização à nanoescala conseguimos hoje visualizar uma nanopartícula (NP) como um dispositivo de elevado potencial terapêutico. A melhoria da sua efectividade terapêutica requer no entanto o aprofundamento e sistematização de conhecimentos, ainda muito incipientes, sobre toxicidade, selectividade, efeitos colaterais e sua dependência das próprias características físico-químicas da NP em análise. O presente trabalho, elegendo como alvo de estudo uma substância considerada biocompatível e não tóxica, a hidroxiapatite (Hap), pretende dar um contributo para esta área do conhecimento. Definiram-se como metas orientadoras deste trabalho (i) estudar a síntese de nanoparticulas de Hap (Hap NP), e a modificação das características físico-químicas e morfológicas das mesmas através da manipulação das condições de síntese; (ii) estudar a funcionalização das Hap NP com nanoestruturas de ouro e com ácido fólico, para lhes conferir capacidades acrescidas de imagiologia e terapêuticas, particularmente interessantes em aplicações como o tratamento do cancro (iii) estudar a resposta celular a materiais nanométricos, com propriedades físico-químicas diversificadas. No que se refere à síntese de Hap NP, comparam-se dois métodos de síntese química distintos, a precipitação química a temperatura fisiológica (WCS) e a síntese hidrotérmica (HS), em meios aditivados com ião citrato. A síntese WCS originou partículas de tamanho nanométrico, com uma morfologia de agulha, pouco cristalinas e elevada área superficial especifica. A síntese HS à temperatura de 180ºC permitiu obter partículas de dimensões também nanométricas mas com área específica inferior, com morfologia de bastonete prismático com secção recta hexagonal e elevada cristalinidade. Com o objectivo de aprofundar o papel de algumas variáveis experimentais na definição das características finais das partículas de hidroxiapatite, designadamente o papel do ião citrato (Cit), variou-se a razão molar [Cit/Ca] da solução reagente e o tempo de síntese. Demonstrou-se que o ião citrato e outras espécies químicas resultantes da sua decomposição nas condições térmicas (180ºC) de síntese tem um papel preponderante na velocidade de nucleação e de crescimento dessas mesmas partículas e por conseguinte nas características físico-químicas das mesmas. Elevadas razões [Cit/Ca] originam partículas de dimensão micrométrica cuja morfologia é discutida no contexto do crescimento com agregação. Com o objectivo de avaliar a citotoxicidade in vitro das nanopartículas sintetizadas procedeu-se à esterilização das mesmas. O método de esterilização escolhido foi a autoclavagem a 121º C. Avaliou-se o impacto do processo de esterilização nas características das partículas, verificando-se contrariamente às partículas WCS, que as partículas HS não sofrem alterações significativas de morfologia, o que se coaduna com as condições de síntese das mesmas, que são mais severas do que as de esterilização. As partículas WCS sofrem processos de dissolução e recristalização que se reflectem em alterações significativas de morfologia. Este estudo demonstrou que a etapa de esterilização de nanopartículas para aplicações biomédicas, por autoclavagem, pode alterar substancialmente as propriedades das mesmas, sendo pois criticamente importante caracterizar os materiais após esterilização. Os estudos citotoxicológicos para dois tipos de partículas esterilizadas (HSster e WCSster) revelaram que ambas apresentam baixa toxicidade e possuem potencial para a modelação do comportamento de células osteoblásticas. Tendo em vista a funcionalização da superfície das Hap NP para multifunções de diagnóstico e terapia exploraram-se condições experimentais que viabilizassem o acoplamento de nanopartículas de ouro à superfície das nanopartículas de Hidroxiapatite (Hap-AuNP). Tirando partido da presença de grupos carboxílicos adsorvidos na superfície das nanopartículas de Hap foi possível precipitar partículas nanométricas de ouro (1,5 a 2,5 nm) na superfície das mesmas adaptando o método descrito por Turkevich. No presente trabalho as nanopartículas de Hap funcionaram assim como um template redutor do ouro iónico de solução, propiciando localmente, na superfície das próprias nanopartículas de Hap, a sua redução a ouro metálico. A nucleação do ouro é assim contextualizada pelo papel redutor das espécies químicas adsorvidas, designadamente os grupos carboxílicos derivados de grupos citratos que presidiram à síntese das próprias nanopartículas de Hap. Estudou-se também a funcionalização das Hap NP com ácido fólico (FA), uma molécula biologicamente interessante por ser de fácil reconhecimento pelos receptores existentes em células cancerígenas. Os resultados confirmaram a ligação do ácido fólico à superfície das diferentes partículas produzidas HS e Hap-AuNPs. Graças às propriedades ópticas do ouro nanométrico (efeito plasmão) avaliadas por espectroscopia vis-UV e às potencialidades de hipertermia local por conversão fototérmica, as nanoestruturas Hap-AuNPs produzidas apresentam-se com elevado interesse enquanto nanodispositivos capazes de integrar funções de quimio e terapia térmica do cancro e imagiologia. O estudo da resposta celular aos diversos materiais sintetizados no presente trabalho foi alvo de análise na tentativa de se caracterizar a toxicidade dos mesmos bem como avaliar o seu desempenho em aplicações terapêuticas. Demonstrou-se que as Hap NP não afectam a proliferação das células para concentrações até 500 g/ml, observando-se um aumento na expressão genética da BMP-2 e da fosfatase alcalina. Verificou-se também que as Hap NP são susceptíveis de internalização por células osteoblásticas MG63, apresentando uma velocidade de dissolução intracelular relativamente reduzida. A resposta celular às Hap-AuNP confirmou a não citotoxicidade destas partículas e revelou que a presença do ouro na superfície das Hap NP aumenta a taxa proliferação celular, bem como a expressão de parâmetros osteogénicos. No seu conjunto os resultados sugerem que os vários tipos de partículas sintetizadas no presente estudo apresentam também comportamentos interessantes para aplicações em engenharia de tecido ósseo.