Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/SLSC-BBKJDV
Type: | Tese de Doutorado |
Title: | Topological design of Wireless sensor network: Formulations and exact algorithms |
Authors: | Vinicius Wellington Coelho de Morais |
First Advisor: | Geraldo Robson Mateus |
First Referee: | Alexandre Salles da Cunha |
Second Referee: | Vinicius Fernandes dos Santos |
Third Referee: | Dilson Lucas Pereira |
metadata.dc.contributor.referee4: | Marcus Vinícius Soledade Poggi de Aragão |
Abstract: | The subject of this thesis is the design of Wireless Sensor Networks (WSN). Given a limited set of sensors and a single sinks, we are particularly interested in the topological WSN design problem. This problem consists in clustering the sensors and defining a communication topology to gather the sensed information throughout the network. Natural connectivity and coverage requirements are satisfied assuming an imposition on the number of clusters. Two variants of the problem are studied: p-arborescence star problem (P-ASP) and p-cycle star problem (P-CSP). P-ASP organizes the network into p clusters and defines the communication topology as rooted directed tree, i.e., an arborescence rooted at the sink. In P-CSP, mobile-sink based networks are designed replacing the core arborescence by a directed cycle. We introduce Mixed Integer Programming formulations and exact solution approaches. To validate our approaches, experiments are performed on instance sets extended from the literature. |
Abstract: | The subject of this thesis is the design of Wireless Sensor Networks (WSN). Given a limited set of sensors and a single sinks, we are particularly interested in the topological WSN design problem. This problem consists in clustering the sensors and defining a communication topology to gather the sensed information throughout the network. Natural connectivity and coverage requirements are satisfied assuming an imposition on the number of clusters. Two variants of the problem are studied: p-arborescence star problem (P-ASP) and p-cycle star problem (P-CSP). P-ASP organizes the network into p clusters and defines the communication topology as rooted directed tree, i.e., an arborescence rooted at the sink. In P-CSP, mobile-sink based networks are designed replacing the core arborescence by a directed cycle. We introduce Mixed Integer Programming formulations and exact solution approaches. To validate our approaches, experiments are performed on instance sets extended from the literature. |
Subject: | simple directed cycles Wireless sensor networks cardinality constraints Computação backbone arborescence |
language: | Português |
Publisher: | Universidade Federal de Minas Gerais |
Publisher Initials: | UFMG |
Rights: | Acesso Aberto |
URI: | http://hdl.handle.net/1843/SLSC-BBKJDV |
Issue Date: | 31-Aug-2018 |
Appears in Collections: | Teses de Doutorado |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
viniciuswellingtoncoelhodemorais.pdf | 936.02 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.