The aim of the Connected Maximum Lifetime Problem is to define a schedule for the activation intervals of the sensors deployed inside a region of interest, such that at all times the activated sensors can monitor a set of interesting target locations and route the collected information to a central base station, while maximizing the total amount of time over which the sensor network can be operational. Complete or partial coverage of the targets are taken into account. To optimally solve the problem, we propose a column generation approach which makes use of an appropriately designed genetic algorithm to overcome the difficulty of solving the subproblem to optimality in each iteration. Moreover, we also devise a heuristic by stopping the column generation procedure as soon as the columns found by the genetic algorithm do not improve the incumbent solution. Comparisons with previous approaches proposed in the literature show our algorithms to be highly competitive, both in terms of solution quality and computational time.
Accepté le :
DOI : 10.1051/ro/2017032
Mots-clés : Maximum lifetime, wireless sensor network, column generation, genetic algorithm, steiner tree, partial coverage
@article{RO_2017__51_3_607_0,
author = {Carrabs, Francesco and Cerulli, Raffaele and D{\textquoteright}Ambrosio, Ciriaco and Raiconi, Andrea},
title = {Exact and heuristic approaches for the maximum lifetime problem in sensor networks with coverage and connectivity constraints},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {607--625},
publisher = {EDP-Sciences},
volume = {51},
number = {3},
year = {2017},
doi = {10.1051/ro/2017032},
mrnumber = {3880515},
zbl = {1387.90123},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ro/2017032/}
}
TY - JOUR AU - Carrabs, Francesco AU - Cerulli, Raffaele AU - D’Ambrosio, Ciriaco AU - Raiconi, Andrea TI - Exact and heuristic approaches for the maximum lifetime problem in sensor networks with coverage and connectivity constraints JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2017 SP - 607 EP - 625 VL - 51 IS - 3 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro/2017032/ DO - 10.1051/ro/2017032 LA - en ID - RO_2017__51_3_607_0 ER -
%0 Journal Article %A Carrabs, Francesco %A Cerulli, Raffaele %A D’Ambrosio, Ciriaco %A Raiconi, Andrea %T Exact and heuristic approaches for the maximum lifetime problem in sensor networks with coverage and connectivity constraints %J RAIRO - Operations Research - Recherche Opérationnelle %D 2017 %P 607-625 %V 51 %N 3 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro/2017032/ %R 10.1051/ro/2017032 %G en %F RO_2017__51_3_607_0
Carrabs, Francesco; Cerulli, Raffaele; D’Ambrosio, Ciriaco; Raiconi, Andrea. Exact and heuristic approaches for the maximum lifetime problem in sensor networks with coverage and connectivity constraints. RAIRO - Operations Research - Recherche Opérationnelle, Tome 51 (2017) no. 3, pp. 607-625. doi : 10.1051/ro/2017032. http://www.numdam.org/articles/10.1051/ro/2017032/
and , Coverage by directional sensors in randomly deployed wireless sensor networks. J. Comb. Optim. 11 (2006) 21–41. | DOI | MR | Zbl
and , Wireless sensor networks for healthcare: a survey. Comput. Netw. 54 (2010) 2688–2710. | DOI
, , and , Maximizing system lifetime in wireless sensor networks. Eur. J. Oper. Res. 181 (2007) 390–402. | DOI | Zbl
, and , The internet of things: A survey. Comput. Netw. 54 (2010) 2787–2805. | DOI | Zbl
W. Awada and M. Cardei, Energy-efficient data gathering in heterogeneous wireless sensor networks, in Proc. of the IEEE International Conference on Wireless and Mobile Computing, Networking and Communications (2006) 53–60.
, , and , Locating sensors to observe network arc flows: Exact and heuristic approaches. Comput. Oper. Res. 46 (2014) 12–22. | DOI | MR | Zbl
, , and , Energy efficient target-oriented scheduling in directional sensor networks. IEEE Trans. Comput. 58 (2009) 1259–1274. | DOI | MR | Zbl
and , Energy-efficient connected-coverage in wireless sensor networks. Int. J. Sensor Networks 3 (2008) 201–210. | DOI
M. Cardei, M.T. Thai, Y. Li and W. Wu, Energy-efficient target coverage in wireless sensor networks. In Vol. 3 of Proc. of the 24th conference of the IEEE Communications Society (2005) 1976–1984.
, and , Improving network lifetime using sensors with adjustable sensing ranges. Int. J. Sensor Networks 1 (2006) 41–49. | DOI
, , C. D’Ambrosio, M. Gentili and A. Raiconi, Maximizing lifetime in wireless sensor networks with multiple sensor families. Comput. Oper. Res. 60 (2015) 121–137. | DOI | MR
, , C. D’Ambrosio and A. Raiconi, A hybrid exact approach for maximizing lifetime in sensor networks with complete and partial coverage constraints. J. Network Comput. Appl. 58 (2015) 12–22. | DOI
F. Carrabs, R. Cerulli, C. D’Ambrosio and A. Raiconi, An exact algorithm to extend lifetime through roles allocation in sensor networks with connectivity constraints. To published in: Optim. Lett. (2016). | DOI | MR
, , and , Extending lifetime through partial coverage and roles allocation in connectivity-constrained sensor networks. IFAC-PapersOnLine 49 (2016) 973–978. | DOI
, , and , Lower and upper bounds for the spanning tree with minimum branch vertices. Comput. Optim. Appl. 56 (2013) 405–438. | DOI | MR | Zbl
, , , and , Exact approaches for lifetime maximization in connectivity constrained wireless multi-role sensor networks. Eur. J. Oper. Res. 241 (2015) 28–38. | DOI | MR | Zbl
, , and , A column generation approach to extend lifetime in wireless sensor networks with coverage and connectivity constraints. Comput. Oper. Res. 52 (2014) 220–230. | DOI | MR | Zbl
, and , Relations, models and a memetic approach for three degree-dependent spanning tree problems. Eur. J. Oper. Res. 232 (2014) 442–453. | DOI | MR | Zbl
, and , Exact and heuristic methods to maximize network lifetime in wireless sensor networks with adjustable sensing ranges. Eur. J. Oper. Res. 220 (2012) 58–66. | DOI | MR | Zbl
, and , Maximizing lifetime and handling reliability in wireless sensor networks. Networks 64 (2014) 321–338. | DOI | MR
L. Davis, Handbook of Genetic Algorithms. Van Nostrand Reinhold, New York (1991).
G. Desaulniers, J. Desrosiers and M. Solomon, Column Generation. Springer US (2005). | MR | Zbl
K. Deschinkel, A column generation based heuristic for maximum lifetime coverage in wireless sensor networks, in Vol. 4 of SENSORCOMM 11, 5th Int. Conf. on Sensor Technologies and Applications (2011) 209–214.
A. Dhawan, C.T. Vu, A. Zelikovsky, Y. Li and S.K. Prasad, Maximum lifetime of sensor networks with adjustable sensing range, in Proc. of the Seventh ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing (2006) 285 – 289.
C. Duin and S. Voss, Steiner tree heuristics – a survey, in Operations Research Proceedings 1993. Papers of the 22nd Annual Meeting of DGOR in Cooperation with NSOR, edited by H. Dyckhoff, U. Derigs, M. Salomon and H.C. Tijms. Springer-Verlag (1994) 485–496.
and , coverage to extend network lifetime on wireless sensor networks. Optim. Lett. 7 (2013) 157–172. | DOI | MR | Zbl
Y. Gu, Y. Ji and B. Zhao, Maximize lifetime of heterogeneous wireless sensor networks with joint coverage and connectivity requirement, in EmbeddedCom-09, 8th International Conference on Embedded Computing (2009) 226–231.
F.K. Hwang, D.S. Richards and P. Winter, The Steiner Tree Problem. North-Holland, Amsterdam (1992). | MR | Zbl
C.H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Englewood Cliffs, New Jersey (1982). | MR | Zbl
A. Raiconi and M. Gentili, Exact and metaheuristic approaches to extend lifetime and maintain connectivity in wireless sensors networks, in Network Optimization, edited by J. Pahl, T. Reiners and S. Voss. Vol. 6701 of Lect. Notes Comput. Sci. Springer, Berlin/Heidelberg (2011) 607–619. | Zbl
, , and , Wireless sensor networks: a survey on recent developments and potential synergies. J. Supercomput. 68 (2014) 1–48. | DOI
, and , An exact approach for maximizing the lifetime of sensor networks with adjustable sensing ranges. Comput. Oper. Res. 39 (2012) 3166–3176. | DOI | MR | Zbl
, and , Lifetime maximization in wireless directional sensor network. Eur. J. Oper. Res. 231 (2013) 229–241. | DOI
and , An approximate solution for the steiner problem in graphs. Math. Japonica 24 (1980) 573–577. | MR | Zbl
C. Wang, M.T. Thai, Y. Li, F. Wang and W. Wu, Minimum coverage breach and maximum network lifetime in wireless sensor networks. In Proc. of the IEEE Global Telecommunications Conference (2007) 1118–1123.
and , Lifetime maximization for connected target coverage in wireless sensor networks. IEEE/ACM Trans. Netw. 16 (2008) 1378–1391. | DOI
Cité par Sources :
