Please use this identifier to cite or link to this item:
http://hdl.handle.net/11612/3199| Authors: | Vilarino, Matheus Machado |
| metadata.dc.contributor.advisor: | Carvalho, Rafael Lima de |
| Title: | Modelo de posicionamento de nos sensores através da utilização de um algoritmo genético satisfazendo as restrições de k-cobertura e m-conectividade |
| Keywords: | k-Cobertura;m-Conectividade;Algoritmo genético;Redes de sensores sem fio |
| Issue Date: | 2018 |
| Publisher: | Universidade Federal do Tocantins |
| Citation: | VILARINO, Matheus Machado. Modelo de posicionamento de nos sensores através da utilização de um algoritmo genético satisfazendo as restrições de k-cobertura e m-conectividade. 59f. Monografia Graduação, Curso de Ciências da Computação, Universidade Federal do Tocantins, Palmas, 2018. |
| metadata.dc.description.resumo: | O problema de cobertura em redes de sensores sem fio consiste em: dados n alvos (ou pontos de observação) encontrar um esquema de cobertura de forma a contemplar os n pontos, utilizando-se o menor número de nós sensores possível. Alguns critérios de redundância podem ser incorporados neste problema, tais como o grau de conectividade de cada n´o sensor (m - conectividade) e o grau de cobertura de cada alvo (k - cobertura), dentre outros. Neste trabalho, são abordados os problemas da cobertura de n´os sensores com as restrições de k-cobertura e m-conectividade, simultaneamente. Por ser um problema NP Completo, ´e proposto a utilização de um algoritmo genético específico para o problema de posicionamento de sensores, com a aplicação de uma modificação da função de crossover baseado no Algoritmo Genético Flexível, utilização do Diagrama de Voronin e uma função de perturbação dos n´os sensores para realizar um pré-processamento no posicionamento dos nós. Os resultados experimentais mostram que o algoritmo proposto obteve um bom desempenho com relação ao número de sensores selecionados, escolhendo a menor quantidade de nós sensores e mantendo a k - cobertura e m - conectividade da rede, após aplicadas as modificações descritas. |
| Abstract: | The coverage problem in wireless sensor networks consists of: given n targets (or observa tion points) find a coverage scheme in order to contemplate the n points, using the least number of sensor nodes. Some redundancy criteria can be incorporated in this problem, such as the degree of connectivity of each sensor node (m - connectivity) and the degree of coverage of each target (k - coverage), among others. In this work, the problems of covering sensor nodes with the k-coverage and m-connectivity constraints are addressed simultaneously. Because it is a NP-Complete problem, it is proposed to use a specific ge netic algorithm for the sensor positioning problem, with the application of a modification of the crossover function based on the Flexible Genetic Algorithm and use of the Voronoi Diagram and a function of perturbation of the sensor nodes to perform a preprocessing in the positioning of the nodes. The experimental results show that the proposed algorithm obtained a good performance in relation to the number of selected sensor nodes, choosing the least amount of sensor nodes and maintaining the k - coverage and m - connectivity of the network, after applying the modifications described. |
| URI: | http://hdl.handle.net/11612/3199 |
| Appears in Collections: | Ciência da Computação |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Matheus Machado Vilarino- TCC.pdf | 1.43 MB | Adobe PDF |  View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.