Submitted by Irvana Coutinho (irvana@ufpa.br) on 2013-01-23T15:09:34Z No. of bitstreams: 2 license_rdf: 23898 bytes, checksum: e363e809996cf46ada20da1accfcd9c7 (MD5) Dissertacao_EstrategiaReducaoConsumo.pdf: 2434652 bytes, checksum: bf2428fb8f0caeaf3737a7f0ba4cd7e5 (MD5) / Approved for entry into archive by Ana Rosa Silva(arosa@ufpa.br) on 2013-01-23T17:11:16Z (GMT) No. of bitstreams: 2 license_rdf: 23898 bytes, checksum: e363e809996cf46ada20da1accfcd9c7 (MD5) Dissertacao_EstrategiaReducaoConsumo.pdf: 2434652 bytes, checksum: bf2428fb8f0caeaf3737a7f0ba4cd7e5 (MD5) / Made available in DSpace on 2013-01-23T17:11:16Z (GMT). No. of bitstreams: 2 license_rdf: 23898 bytes, checksum: e363e809996cf46ada20da1accfcd9c7 (MD5) Dissertacao_EstrategiaReducaoConsumo.pdf: 2434652 bytes, checksum: bf2428fb8f0caeaf3737a7f0ba4cd7e5 (MD5) Previous issue date: 2012 / O avanço nas áreas de comunicação sem fio e microeletrônica permite o desenvolvimento de equipamentos micro sensores com capacidade de monitorar grandes regiões. Formadas por milhares de nós sensores, trabalhando de forma colaborativa, as Redes de Sensores sem Fio apresentam severas restrições de energia, devido à capacidade limitada das baterias dos nós que compõem a rede. O consumo de energia pode ser minimizado, permitindo que apenas alguns nós especiais, chamados de Cluster Head, sejam responsáveis por receber os dados dos nós que formam seu cluster e propagar estes dados para um ponto de coleta denominado Estação Base. A escolha do Cluster Head ideal influencia no aumento do período de estabilidade da rede, maximizando seu tempo de vida útil. A proposta, apresentada nesta dissertação, utiliza Lógica Fuzzy e algoritmo k-means com base em informações centralizadas na Estação Base para eleição do Cluster Head ideal em Redes de Sensores sem Fio heterogêneas. Os critérios usados para seleção do Cluster Head são baseados na centralidade do nó, nível de energia e proximidade para a Estação Base. Esta dissertação apresenta as desvantagens de utilização de informações locais para eleição do líder do cluster e a importância do tratamento discriminatório sobre as discrepâncias energéticas dos nós que formam a rede. Esta proposta é comparada com os algoritmos Low Energy Adaptative Clustering Hierarchy (LEACH) e Distributed energy-efficient clustering algorithm for heterogeneous Wireless sensor networks (DEEC). Esta comparação é feita, utilizando o final do período de estabilidade, como também, o tempo de vida útil da rede. / The increase in wireless communication and microelectronic devices enables the development of micro sensors with monitoring capable for large areas. Consisting of thousands of sensor nodes, working collaboratively, the Wireless sensor networks have severe energy constraints, due to the limited capacity of batteries of the nodes that compose the network. The power consumption can be minimized by allowing only a few special nodes, called Cluster Head, are responsible for receiving data from its cluster nodes that form and propagate this data to a collection point called Base Station. The choice of optimum cluster head influence on increasing the period of stability of the network, maximizing their useful life. The proposal, presented in this thesis, uses Fuzzy Logic and k-means algorithm based on centralized information on Base Station for election of ideal Cluster Head for Heterogeneous Wireless Sensors Networks. The criteria used to select the ideal Cluster Head are based on the node centrality, energy level and proximity to the Base Station. This dissertation presents the disadvantages when the local information are used to the cluster leader election and the importance of discriminatory treatment on the energy discrepancies in the network. This proposal is compared with the Low Energy Adaptive Clustering Hierarchy (LEACH) and Distributed energy-efficient clustering (DEEC) algorithms. This comparison is evaluated using the end of the stability period and the lifetime of the network.

Em Complexidade Descritiva investigamos o uso de logicas para caracterizar classes problemas pelo vies da complexidade. Desde 1974, quando Fagin provou que NP e capturado pela logica existencial de segunda-ordem, considerado o primeiro resultado da area, outras relac~oes entre logicas e classes de complexidade foram estabelecidas. Os resultados mais conhecidos normalmemte envolvem logica de primeira-ordem e suas extens~oes, e classes de complexidade polinomiais em tempo ou espaco. Alguns exemplos sÃo que a logica de primeira-ordem estendida com o operador de menor ponto xo captura a clsse P e que a logica de segunda-ordem estendida com o operador de fecho transitivo captura a classe PSPACE. Nesta dissertaÃÃo, analisaremos inicialmente a expressividade de algumas logicas modais com relacÃo ao problema de decisÃo REACH e veremos que e possvel expressa-lo com as logicas temporais CTL e CTL. Analisaremos tambem o uso combinado de logicas de ordem superior com o operador de menor ponto xo e obteremos como resultado que cada nvel dessa hierarquia captura cada nvel da hierarquia determinstica em tempo exponencial. Como corolario, provamos que a hierarquia de HOi(LFP) nÃo colapsa, ou seja, HOi(LFP) HOi+1(LFP) / In Descriptive Complexity, we investigate the use of logics to characterize computational classes os problems through complexity. Since 1974, when Fagin proved that the class NP is captured by existential second-order logic, considered the rst result in this area, other relations between logics and complexity classes have been established. Wellknown results usually involve rst-order logic and its extensions, and complexity classes in polynomial time or space. Some examples are that the rst-order logic extended by the least xed-point operator captures the class P and the second-order logic extended by the transitive closure operator captures the class PSPACE. In this dissertation, we will initially analyze the expressive power of some modal logics with respect to the decision problem REACH and see that is possible to express it with temporal logics CTL and CTL. We will also analyze the combined use of higher-order logics extended by the least xed-point operator and obtain as result that each level of this hierarchy captures each level of the deterministic exponential time hierarchy. As a corollary, we will prove that the hierarchy of HOi(LFP), for i 2, does not collapse, that is, HOi(LFP) HOi+1(LFP)

Made available in DSpace on 2016-08-17T14:53:05Z (GMT). No. of bitstreams: 1 Lucas Rego Drumond.pdf: 6150160 bytes, checksum: 27ad4ea0ffdf273a78782ada8f04da6b (MD5) Previous issue date: 2009-10-23 / Knowledge representation formalisms, such as ontologies, have proven to be a powerful tool for enhancing the effectiveness of natural language processing, information filtering and retrieval and so on. Besides these tasks, ontologies are also crucial for the Semantic Web, a new generation of the Web that aims at structuring its content in such a way that it can be more effectively processed by machines. However, knowledge systems suffer from the so called knowledge acquisition bottleneck, i.e. the difficulty in constructing knowledge bases. An approach for this problem is to provide automatic or semi-automatic support for ontology construction, a field of research known as ontology learning. This work discusses the state of the art of ontology learning techniques and proposes and approach for supporting the ontology construction process through the automatization of the concept hierarchy extraction from textual sources. The proposed process is composed by two techniques, namely PRECE (Probabilistic Relational Concept Extraction) and PREHE (Probabilistic Relational Hierarchy Extraction). The PRECE technique extracts ontology concepts from textual sources while the PREHE technique extracts taxonomic relationships between the concepts extracted by PRECE. Both techniques use Markov logic networks, an approach for statistical relational learning that combines first order logic with Markov networks. The PRECE and PREHE techniques were evaluated in the touristic domain and their results were compared with an ontology manually developed by a domain expert. / Os formalismos de representação do conhecimento como as ontologias têm se mostrado uma poderosa ferramenta para melhorar a efetividade de sistemas de processamento da linguagem natural, recuperação e filtragem de informação e muitas outras tarefas. Além disso, as ontologias são essenciais para a Web Semântica, uma nova geração da Web que visa estruturar o conteúdo da mesma de modo que este possa ser processado de forma mais efetiva pelas máquinas. Entretanto, os sistemas de conhecimento sofrem do problema conhecido como o gargalo da aquisição do conhecimento, que nada mais é do que a dificuldade de construção das bases de conhecimento. Uma abordagem para este problema é o suporte automático ou semi-automático à construção de ontologias. Este campo de pesquisa é conhecido como aprendizagem de ontologias. Este trabalho discute o estado da arte das técnicas de aprendizagem de ontologias e propõe uma abordagem para o suporte ao processo de construção de ontologias através da automatização da extração de hierarquias de conceitos a partir de fontes textuais. O processo proposto é composto por duas técnicas, a PRECE (Probabilistic Relational Concept Extraction) para a extração de conceitos e a PREHE (Probabilistic Relational Hierarchy Extraction) para a descoberta de relacionamentos taxonômicos entre os conceitos extraídos pela PRECE. As duas técnicas fazem uso das Redes Lógicas de Markov, uma abordagem da aprendizagem probabilística relacional que combina a lógica de primeira ordem com as redes de Markov. As técnicas PRECE e PREHE foram avaliadas no domínio turístico comparando os seus resultados com uma ontologia desenvolvida manualmente por especialistas neste domínio.