Modelos e heurísticas para o problema de controle de densidade em redes de sensores sem fio planas

Abstract

Wireless Sensor Networks (WSNs) are composed of a large number of sensor nodes. These networks require density control to ensure a better functioning because the high concentration of sensor nodes generates collision data, interference, and retransmittions. In addition, sensor nodes have limited energy, processing, and communication, therefore is interesting to optimize the energy consumption of the network in order to extend its lifetime. Density control schemes have been used to prolong the network lifetime. The Density Control Problem in Wireless Sensor Networks (DCP-WSNs) minimizes the energy consumed by the sensor nodes active, choosing a subset of sensor nodes that meets the application requirements and maximize the use of network resources. This paper presents two approaches to treat DCP-WSN: Periodic and Multiperiod. The Periodic Approach always chooses the best solution for a given period, having a local view of the network lifetime and repeats this proceduce periodically. The Multiperiod Approach defines an expected life time of the network and divide it into periods. For each period the solution is chosen taking into consideration the other periods, thus with an global view of the network lifetime and periods. Both approaches are modeled with Integer Linear Programming and solved by an optimization software. For the Periodic Approach model is proposed a Lagrangean Relaxation with a Lagrangean Heuristic which relax difficults constraints in order to make the problem easier to be solved. We also present a Genetic Algorithm Hybrid (GA) which uses the Periodic Approach to generate the solution of each period and execute a refinement stage based on concepts of the Multiperiod Approach. The proposed heuristics are compared with algorithms of the literature and results show that the Lagrangean Relaxation and Heuristic reach better energy consumption and solution time. Furthermore the Lagrangean relaxation generates lower bounds for the DCP-WSN that may be used to evaluate other algorithms Density Control.