Geodesic
On maximization of sensor network's lifetime subject to the limited resources
Diskretnyj analiz i issledovanie operacij, Tome 18 (2011) no. 6, pp. 17-32.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DA_2011_18_6_a1,
     author = {A. I. Erzin and R. V. Plotnikov},
     title = {On maximization of sensor network's lifetime subject to the limited resources},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {17--32},
     publisher = {mathdoc},
     volume = {18},
     number = {6},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2011_18_6_a1/}
}
TY  - JOUR
AU  - A. I. Erzin
AU  - R. V. Plotnikov
TI  - On maximization of sensor network's lifetime subject to the limited resources
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2011
SP  - 17
EP  - 32
VL  - 18
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2011_18_6_a1/
LA  - ru
ID  - DA_2011_18_6_a1
ER  - 
%0 Journal Article
%A A. I. Erzin
%A R. V. Plotnikov
%T On maximization of sensor network's lifetime subject to the limited resources
%J Diskretnyj analiz i issledovanie operacij
%D 2011
%P 17-32
%V 18
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2011_18_6_a1/
%G ru
%F DA_2011_18_6_a1
A. I. Erzin; R. V. Plotnikov. On maximization of sensor network's lifetime subject to the limited resources. Diskretnyj analiz i issledovanie operacij, Tome 18 (2011) no. 6, pp. 17-32. http://geodesic.mathdoc.fr/item/DA_2011_18_6_a1/

[1] Astrakov S. N., Erzin A. I., Zalyubovskii V. V., “Sensornye seti i pokrytie ploskosti krugami”, Diskret. analiz i issled. operatsii, 16:3 (2009), 3–19 | MR

[2] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982, 416 pp. | MR

[3] Kharari F., Teoriya grafov, Mir, M., 1973, 296 pp. | MR

[4] Berman P., Fujito T., “Approximating independent sets in degree 3 graphs”, Proc. 4th Workshop Algorithms Data Structures, Lect. Notes Comput. Sci., 955, Springer-Verl., Berlin, 1995, 449–460 | MR

[5] Berman P., Calinescu G., Shan C., Zelikovsky A., “Power efficient monitoring management in sensor networks”, Proc. IEEE Wireless Communications Networking Conf. (Atlanta, USA, March 21–25, 2004), IEEE Comp. Soc., Los Alamitos, CA, 2006, 2329–2334

[6] Berman P., Karpinski M., On some tighter inapproximability results, Tech. Rep. TR98–065, ECCC, 1998

[7] Cardei M., Ding-Zhu D., “Improving wireless sensor network lifetime through power aware organization”, Wireless Networks, 11:3 (2005), 333–340 | DOI

[8] Cardei M., Thai M. T., Li Y., Wu W., “Energy-efficient target coverage in wireless sensor networks”, IEEE Infocom, v. 3, 2005, 1976–1984

[9] Dhawan A., Vu C. T., Zelikovsky A., Li Y., Prasad S. K., “Maximum lifetime of sensor networks with adjustable sensing range”, Proc. 7th ACIS Int. Conf. Software Engineering (Las Vegas, Nevada, USA, June 19–20, 2006), IEEE Comp. Soc., Los Alamitos, 2006, 285–289

[10] Garg N., Konemann J., “Faster and simpler algorithms for multicommodity flow and other fractional packing problems”, Proc. FOCS (Palo Alto, CA, USA, November 8–10, 1998), IEEE Comp. Soc., Washington, 1998, 300–309

[11] Gavril F., “Algorithms on circular-arc graphs”, Networks, 4 (1974), 357–369 | DOI | MR | Zbl

[12] Ghouila-Houri A., “Caractérisation des matrices totalement unimodulaires”, CR hebdomadaires des séances de l'Académie des sciences Paris, 254 (1962), 1192–1194 | MR | Zbl

[13] Hastad G., Clique is hard to approximate within $n^{1-\varepsilon}$, Tech. Rep. TR97–038, ECCC, 1997

[14] Hopcroft J., Karp R., “An $n^{5/2}$ algorithm for maximum matchings in bipartite graphs”, SIAM J. Comput., 2 (1973), 225–231 | DOI | MR | Zbl

[15] Inanc M., Magdon-Ismail M., Yener B., Power optimal connectivity and coverage in wireless sensor networks, Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY, 2003

[16] Kim Y., Lee H., Han Y. Jeonge Y., “A branch and bound algorithm for extending the lifetime of wireless sensor networks”, Proc. Vehicular Tech. Conf. (Anchorage, AK, September 20–23, 2009), IEEE Comp. Soc., Washington, 2009, 1–5

[17] Mucha M., Sankowski P., “Maximum matchings via Gaussian elimination”, Proc. 45th IEEE Symp. Foundations Comput. Sci. 2004 (Washington, DC, USA, October 17–19, 2004), IEEE Comp. Soc., Washington, 2004, 248–255

[18] Segal M., “Improving lifetime of wireless sensor networks”, Netw. Protocols Algorithms, 1:2 (2009), 48–60