Volume 18, No 6, 2011, P. 17-32

UDC 519.8
A. I. Erzin, R. V. Plotnikov
On maximization of sensor network’s lifetime subject to the limited resources

Abstract:
A sensor network’s lifetime maximization problem subject to the limited resources of sensors is considered as an integer linear programming problem when the set of covers is given and it is necessary to find a lifetime of each cover. Meanwhile sensor’s resource is given as a number of time rounds during which it can be active. We proved strong NP-hardness of the problem; proposed the ways of its reduction; estimated a limit of approximability; found the special cases when the problem is polynomially solvable; proposed the heuristics for constructing approximate solutions and performed a posteriori analysis.
Tab. 1, bibliogr. 18.

Keywords: sensor network, lifetime maximization, energy consumption, integer linear programming.

Erzin Adil Il’jasovich ^1,2
Plotnikov Roman Victorovich ²
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
2. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: adilerzin@math.nsc.ru, nomad87@ngs.ru