The MIIS Eprints Archive

Optimization of Lifetime in Sensor Networks

Bansal, N. and Bourne, D. and Firat, M. and de Graaf, M. and Kapodistria, S. and Kumar, K. and Meerman, C. and Mitici, M. and Nardi, F. R. and de Rijk, B. and Sarswat, S. and Scardia, L. (2012) Optimization of Lifetime in Sensor Networks. [Study Group Report]



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 NP-complete, 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 log n 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.

Item Type:Study Group Report
Problem Sectors:Technology/Devices
Information and communication technology
Study Groups:European Study Group with Industry > ESGI 84 (Eindhoven, Netherlands, 30 Jan-3 Feb 2012)
Company Name:Thales
ID Code:662
Deposited By: Matthew Hennessy
Deposited On:03 Jul 2014 21:55
Last Modified:29 May 2015 20:17

Repository Staff Only: item control page