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.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