In their EWSN`07 paper [1], Giusti et al. proposed a decentralized wake-up scattering algorithm for temporally spreading the intervals in which the nodes of a wireless sensor network (WSN) are active, and showed that the resulting schedules significantly improve over the commonly-used random ones, e.g., by providing greater area coverage at less energy costs. However, an open question remained about whether further improvements are possible. Here, we complete the work in [1] by providing a (centralized) optimal solution that constitutes a theoretical upper bound for wake-up scattering protocols. Simulation results shows that the decentralized algorithm proposed in [1] comes within 4% to 11% of the optimum. Moreover, we show that the modeling framework we use to derive the solution, based on integer programming techniques, allows for a particularly efficient solution. The latter result discloses important opportunities for the practical utilization of the model. The model is also general enough to encompass alternative formulations of the problem.

Solving the Wake-Up Scattering Problem Optimally

Murphy, Amy Lynn;Picco, Gian Pietro;
2009

Abstract

In their EWSN`07 paper [1], Giusti et al. proposed a decentralized wake-up scattering algorithm for temporally spreading the intervals in which the nodes of a wireless sensor network (WSN) are active, and showed that the resulting schedules significantly improve over the commonly-used random ones, e.g., by providing greater area coverage at less energy costs. However, an open question remained about whether further improvements are possible. Here, we complete the work in [1] by providing a (centralized) optimal solution that constitutes a theoretical upper bound for wake-up scattering protocols. Simulation results shows that the decentralized algorithm proposed in [1] comes within 4% to 11% of the optimum. Moreover, we show that the modeling framework we use to derive the solution, based on integer programming techniques, allows for a particularly efficient solution. The latter result discloses important opportunities for the practical utilization of the model. The model is also general enough to encompass alternative formulations of the problem.
9783642002236
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11582/4626
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
social impact