Algoritmos para controle de densidade em redes de sensores sem fio

• Ano de defesa: 2010
• Autor(a) principal: Fabiola Pereira da Silva Guerra
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Minas Gerais; UFMG
• Palavras-chave em Português: Controle de Densidade; Redes de Sensores sem Fio; Programação Linear Inteira; Relaxação Lagrangeana; Computação
• Link de acesso: http://hdl.handle.net/1843/ESBF-AAYNSS

Density Control is an effective way towards the efficient resource usage and lifetime extension in wireless sensor networks. In this work, the models and algorithms proposed for density control aims at guaranteeing coverage and connectivity, while minimizing the overall energy consumption and takes into account the battery capacity of the nodes. The Density Control Problem (DCP) is addressed by using two different approaches: Multiperiod and Periodic. The Multiperiod Approach is a density control scheme that primarily divides the expected network lifetime in time periods, which may or may not have the same duration.The approach calculates, in a global way, a solution for the density control problem at each period, respecting the battery capacity of the node. Given the global aspect of the approach regarding the available nodes and the network lifetime, the optimal solution provides a network configuration that has the best coverage possible with the minimum overall energy consumption. Hence, a multiperiod solution could provide a lower bound for periodic density control schemes. TheMultiperiod Density Control Problem (MDCP) is modeled as a Integer Linear Programming (ILP) Problem and is solved by a commercial optimization package. However, the MDCP is a combinatorial problem which means large instances may not be solved at reasonable time. Then, we use different optimization techniques, such as Lagrangian Relaxation and Lagrangian Heuristics to address the problem. Results show that the Lagrangian Relaxationderives good lower bounds. The Lagrangian Heuristics is a good choice to generates aviable solution, that in some cases is very close the optimal solution, regarding the objectivefunction. The Periodic Approach is proposed as an alternative to the MDCP and consists infinding the optimal solution for the DCP in a given time and to repeat this procedure periodically.We model the Periodic Density Control Problem (PDCP) as a ILP problem withtwo objective functions, one that minimizes the energy consumption and other that minimizesthe ratio between the energy consumption and the residual energy of the nodes. Giventhe combinatorial nature of the model, for small instances, we generate the solutions witha commercial optimization package and for large instances we propose a Hybrid Algorithm(HA), that combines global and local strategies, to derive the solutions. Results show that,compared to the optimal solution of the model, the HA generates good solutions, consideringboth the quality of the solution and the execution time. Additional results include analysisof the sink node position into the network lifetime, advantages and disadvantages of eachobjective function, and compare the two density control approaches.