We consider the problem of optimizing the area coverage of a wireless sensor network under energy consumption constraints. Following existing approaches, we use a mixed integer linear program formulation. We then show how to use partitioning techniques, developed in the context of VLSI place and route, to decompose the problem into separate sub-problems, overcoming the exponential complexity typical of integer linear programming, while minimizing the loss in optimality. In addition, we are able to evaluate the achieved degree of optimality by computing relatively tight bounds with respect to the optimal solution. Finally, we employ simple but effective heuristics to further improve our solution. The results show that our procedure is very efficient and is able to find solutions that are very close to optimal.

Efficient Coverage Optimization in Energy-Constrained Wireless Sensor Networks / Palopoli, Luigi; Passerone, Roberto; Toldo, Paolo. - ELETTRONICO. - (2009), pp. 1-6.

Efficient Coverage Optimization in Energy-Constrained Wireless Sensor Networks

Palopoli, Luigi;Passerone, Roberto;
2009-01-01

Abstract

We consider the problem of optimizing the area coverage of a wireless sensor network under energy consumption constraints. Following existing approaches, we use a mixed integer linear program formulation. We then show how to use partitioning techniques, developed in the context of VLSI place and route, to decompose the problem into separate sub-problems, overcoming the exponential complexity typical of integer linear programming, while minimizing the loss in optimality. In addition, we are able to evaluate the achieved degree of optimality by computing relatively tight bounds with respect to the optimal solution. Finally, we employ simple but effective heuristics to further improve our solution. The results show that our procedure is very efficient and is able to find solutions that are very close to optimal.
2009
Trento
University of Trento - Dipartimento di Ingegneria e Scienza dell'Informazione
Efficient Coverage Optimization in Energy-Constrained Wireless Sensor Networks / Palopoli, Luigi; Passerone, Roberto; Toldo, Paolo. - ELETTRONICO. - (2009), pp. 1-6.
Palopoli, Luigi; Passerone, Roberto; Toldo, Paolo
File in questo prodotto:
File Dimensione Formato  
PalopoliPasseroneToldo09DISI.pdf

accesso aperto

Tipologia: Versione editoriale (Publisher’s layout)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 258.61 kB
Formato Adobe PDF
258.61 kB Adobe PDF Visualizza/Apri

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/11572/358683
 Attenzione

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

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