We consider the problem proposed by Thales Nederland at the SWI 2012 meeting. Thales Nederland is the Dutch branch of the international Thales Group. The company specializes in designing and producing professional electronics for defence and security applications, such as radar and communication systems. Moreover, Thales Nederland acts as a local point of contact for the complete portfolio of the Thales Group. During the SWI 2012 meeting, on behalf of Thales Nederland, Dr. Maurits de Graaf posed several questions regarding the maximization of the lifetime of a wireless sensor network. We addressed these questions during the workshop and our most significant results are summarized as follows: We have proven that this lifetime maximization problem, even under the most simple constraints, is NPcomplete, so it is not possible to find an algorithm that gives the optimal solution within polynomial time. Furthermore, we have constructed a counterexample to illustrate that the heuristic currently used by Thales can be asymptotically at least logn times worse than the optimal solution. Moreover, we have developed a new heuristic and have illustrated with several numerical examples that it performs better than the heuristic currently used by Thales. Finally, we have formulated the problem as a linear programming problem and used this to quantify how far the heuristic used by Thales is from being optimal.

Optimization of Lifetime in Sensor Networks / Nikhil Bansal, David Bourne, Murat Firat, Maurits de Graaf, Stella Kapodistria , Kundan Kumar, Corine Meerman, Mihaela Mitici , Francesca R. Nardi, Björn de Rijk, Suneel Sarswat, Lucia Scardia.. - STAMPA. - Proocedings of the 84th European Study group:(2012), pp. 39-69. (Intervento presentato al convegno Mathematics with Industry tenutosi a Eindhoven nel 30/01/2012-3/02/2012).

Optimization of Lifetime in Sensor Networks

NARDI, FRANCESCA ROMANA;
2012

Abstract

We consider the problem proposed by Thales Nederland at the SWI 2012 meeting. Thales Nederland is the Dutch branch of the international Thales Group. The company specializes in designing and producing professional electronics for defence and security applications, such as radar and communication systems. Moreover, Thales Nederland acts as a local point of contact for the complete portfolio of the Thales Group. During the SWI 2012 meeting, on behalf of Thales Nederland, Dr. Maurits de Graaf posed several questions regarding the maximization of the lifetime of a wireless sensor network. We addressed these questions during the workshop and our most significant results are summarized as follows: We have proven that this lifetime maximization problem, even under the most simple constraints, is NPcomplete, so it is not possible to find an algorithm that gives the optimal solution within polynomial time. Furthermore, we have constructed a counterexample to illustrate that the heuristic currently used by Thales can be asymptotically at least logn times worse than the optimal solution. Moreover, we have developed a new heuristic and have illustrated with several numerical examples that it performs better than the heuristic currently used by Thales. Finally, we have formulated the problem as a linear programming problem and used this to quantify how far the heuristic used by Thales is from being optimal.
2012
Proceedings of the 84th European Study Group with Industry SWI2012
Mathematics with Industry
Eindhoven
30/01/2012-3/02/2012
Nikhil Bansal, David Bourne, Murat Firat, Maurits de Graaf, Stella Kapodistria , Kundan Kumar, Corine Meerman, Mihaela Mitici , Francesca R. Nardi, Björn de Rijk, Suneel Sarswat, Lucia Scardia.
File in questo prodotto:
File Dimensione Formato  
SWI2012.pdf

Accesso chiuso

Descrizione: tabelle dati sperimentali
Tipologia: Pdf editoriale (Version of record)
Licenza: Tutti i diritti riservati
Dimensione 585.63 kB
Formato Adobe PDF
585.63 kB Adobe PDF   Richiedi una copia

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

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/1092070
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact