×

An exact approach to extend network lifetime in a general class of wireless sensor networks. (English) Zbl 1436.68054

Summary: This paper provides a general framework to model and optimize lifetime maximization problems in wireless sensor networks with sensors having specialized capabilities like the ability to adjust their sensing range, change their directions, etc. In order to identify the set of tasks that a sensor carries out, the concept of role is introduced. These roles include sensor direction, sensing range, communication mode and combinations of these. The purpose is to identify schedules, represented as the allocation of roles to the sensors and a time interval for assuming such roles, while covering targets and transmitting signals to the base station. To do so, a large scale linear programming model is proposed and solved through an exact approach based on column generation, which is complemented with a branch-and-cut procedure used to address the pricing subproblem. The proposed approach is tested on an extensive set of randomly generated instances used to evaluate its performance. Computational results show the potential of the proposed approach for medium-large size instances for which it is possible to compute either the optimal or good quality solutions in short computational times.

MSC:

68M18 Wireless sensor networks as related to computer science
90B18 Communication networks in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abdulla, A. E.; Nishiyama, H.; Kato, N., Extending the lifetime of wireless sensor networks: a hybrid routing algorithm, Comput. Commun., 35, 9, 1056-1063 (2012)
[2] Ai, J.; Abouzeid, A. A., Coverage by directional sensors in randomly deployed wireless sensor networks, J. Comb. Optim., 11, 1, 21-41 (2006) · Zbl 1132.90004
[3] Alam, K. M.; Kamruzzaman, J.; Karmakar, G.; Murshed, M., Dynamic adjustment of sensing range for event coverage in wireless sensor networks, J. Netw. Comput. Appl., 46, 139-153 (2014)
[4] Amac Guvensan, M.; Gokhan Yavuz, A., On coverage issues in directional sensor networks: a survey, Ad Hoc Netw., 9, 7, 1238-1255 (2011)
[5] Amor, H.; Desrosiers, J.; Frangioni, A., On the choice of explicit stabilizing terms in column generation., Discrete Appl. Math., 157, 6, 1167-1184 (2009) · Zbl 1169.90395
[6] Cai, Y.; Lou, W.; Li, M.; Li, X.-Y., Energy efficient target-oriented scheduling in directional sensor networks, IEEE Trans. Comput., 58, 9, 1259-1274 (2009) · Zbl 1368.68110
[7] Cardei, M.; Wu, J.; Lu, M., Improving network lifetime using sensors with adjustable sensing ranges, Int. J. Sens. Netw., 1, 1/2, 41 (2006)
[8] Carrabs, F.; Cerulli, R.; D’Ambrosio, C.; Raiconi, A., A hybrid exact approach for maximizing lifetime in sensor networks with complete and partial coverage constraints, J. Netw. Comput. Appl., 58, 12-22 (2015)
[9] Castaño, F.; Bourreau, E.; Rossi, A.; Sevaux, M.; Velasco, N., Partial target coverage to extend the lifetime in wireless multi-role sensor networks, Networks, 68, 1, 34-53 (2016)
[10] Castaño, F.; Rossi, A.; Sevaux, M.; Velasco, N., A column generation approach to extend lifetime in wireless sensor networks with coverage and connectivity constraints, Comput. Oper. Res., 52, 220-230 (2014) · Zbl 1348.90170
[11] Castaño, F.; Sevaux, M., Combining metaheuristics with column generation: Successful approaches to enhance column generation algorithms performance, Proceedings of the Sixth International Workshop on Model-based Metaheuristic (Matheuristics 2016), 95-100 (2016)
[12] Cerulli, R.; De Donato, R.; Raiconi, A., Exact and heuristic methods to maximize network lifetime in wireless sensor networks with adjustable sensing ranges, Eur. J. Oper. Res., 220, 1, 58-66 (2012) · Zbl 1253.90057
[13] Chaudhary, M.; Pujari, A. K., Q-Coverage Problem in Wireless Sensor Networks, 325-330 (2009)
[14] Chvátal, V., Linear Programming. A Series of Books in the Mathematical Ssciences (1983) · Zbl 0537.90067
[15] Curry, R. M.; Smith, J. C., A survey of optimization algorithms for wireless sensor network lifetime maximization, Comput. Ind. Eng., 101, 145-166 (2016)
[16] Dhawan, A.; Vu, C. T.; Zelikovsky, A.; Li, Y.; Prasad, S. K., Maximum lifetime of sensor networks with adjustable sensing range, Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing, 2006. SNPD 2006. Seventh ACIS International Conference on, 285-289 (2006), IEEE
[17] Gil, J.; Han, Y., A target coverage scheduling scheme based on genetic algorithms in directional sensor networks, Sensors, 11, 2, 1888-1906 (2011)
[18] Gilmore, P. C.; Gomory, R. E., A linear programming approach to the cutting-stock problem, Oper. Res., 9, 6, 849-859 (1961) · Zbl 0096.35501
[19] Gu, Y.; Liu, H.; Zhao, B., Target coverage with QoS requirements in wireless sensor networks, Proceedings The 2007 International Conference on Intelligent Pervasive Computing, IPC 2007, 35-38 (2007)
[20] Gu, Y.; Zhao, B.-H.; Ji, Y.-S.; Li, J., Theoretical treatment of target coverage in wireless sensor networks, J. Comput. Sci. Technol., 26, 1, 117-129 (2011) · Zbl 1280.68053
[21] Han, C.; Sun, L.; Guo, J.; Chen, C., Rotatable sensor scheduling for multi-demands of coverage in directional sensor networks, 25th International Conference on Computer Communications and Networks, ICCCN 2016 (2016)
[22] Hooshmand, M.; Soroushmehr, S. M.R.; Khadivi, P.; Samavi, S.; Shirani, S., Visual sensor network lifetime maximization by prioritized scheduling of nodes, J. Netw. Comput. Appl., 36, 1, 409-419 (2013)
[23] Kandoth, C.; Chellappan, S., Angular mobility assisted coverage in directional sensor networks, Network-Based Information Systems, 2009. NBIS’09. International Conference on, 376-379 (2009), IEEE
[24] Liu, H.; Chen, W.; Ma, H.; Li, D., Energy-efficient algorithm for the target Q-coverage problem in wireless sensor networks, (Pandurangan, G.; Kumar, V. S.A.; Ming, G.; Liu, Y.; Li, Y., WASA. WASA, Lecture Notes in Computer Science, 6221 (2010), Springer), 21-25
[25] Marsten, R.; Hogan, W. W.; Blankenship, J., The boxstep method for large-scale optimization, Oper. Res., 23, 3, 389-405 (1975) · Zbl 0372.90078
[26] Mini, S.; Udgata, S. K.; Sabat, S. L., K-connected coverage problem in wireless sensor networks, ISRN Sens. Netw., 2012, 1-9 (2012)
[27] Mohamadi, H.; Salleh, S.; Norsyarizad Razali, M., Heuristic methods to maximize network lifetime in directional sensor networks with adjustable sensing ranges, J. Netw. Comput. Appl., 46, 26-35 (2014)
[28] Mostafaei, H.; Shojafar, M., A new meta-heuristic algorithm for maximizing lifetime of wireless sensor networks, Wirel. Person. Commun., 82, 2, 723-742 (2015)
[29] Nguyen, N. D.; Zalyubovskiy, V.; Ha, M. T.; Le, T. D.; Choo, H., Energy-efficient models for coverage problem in sensor networks with adjustable ranges, Ad Hoc Sens. Wirel. Netw., 16, 1-3, 1-28 (2012)
[30] Othman, M. F.; Shazali, K., Wireless sensor network applications: a study in environment monitoring system, Procedia Eng., 41, 1204-1210 (2012)
[31] Rault, T.; Bouabdallah, A.; Challal, Y., Energy efficiency in wireless sensor networks: a top-down survey, Comput. Netw., 67, 104-122 (2014)
[32] Rossi, A.; Singh, A.; Sevaux, M., An exact approach for maximizing the lifetime of sensor networks with adjustable sensing ranges, Comput. Oper. Res., 39, 12, 3166-3176 (2012) · Zbl 1349.90573
[33] Rossi, A.; Singh, A.; Sevaux, M., Lifetime maximization in wireless directional sensor network, Eur. J. Oper. Res., 231, 1, 229-241 (2013)
[34] Sarkar, A.; Murugan, T. S., Routing protocols for wireless sensor networks: what the literature says?, Alexandria Eng. J., 55, 4, 3173-3183 (2016)
[35] Schurgers, C.; Srivastava, M. B., Energy efficient routing in wireless sensor networks, Military communications conference, 2001. MILCOM 2001. Communications for Network-centric Operations: Creating the Information Force. IEEE, 1, 357-361 (2001), IEEE
[36] Singh, A.; Rossi, A.; Sevaux, M., Matheuristic approaches for Q-coverage problem versions in wireless sensor networks, Eng. Optim., 45, 5, 609-626 (2013)
[37] Wang, A.; Gao, Y.; Wu, J.; Sun, G.; Jia, W., A novel multi-objective coverage optimization memetic algorithm for directional sensor networks, Int. J. Distrib. Sens. Netw., 12, 7, 1-9 (2016)
[38] Wang, B., Coverage problems in sensor networks, ACM Comput. Surv., 43, 4, 1-53 (2011) · Zbl 1293.68042
[39] Westerlund, A.; Göthe-Lundgren, M.; Larsson, T., A stabilized column generation scheme for the traveling salesman subtour problem, Discrete Appl. Math., 154, 15, 2212-2238 (2006) · Zbl 1111.90097
[40] Wu, J.; Yang, S., Energy-efficient node scheduling models in sensor networks with adjustable ranges, Int. J. Found. Comput. Sci., 16, 01, 3-17 (2005) · Zbl 1096.68012
[41] Younis, O.; Ramasubramanian, S.; Krunz, M., Location-unaware sensing range assignment in sensor networks, International Conference on Research in Networking, 120-131 (2007), Springer
[42] Zhou, Z.; Das, S. R.; Gupta, H., Variable radii connected sensor cover in sensor networks, ACM Trans. Sens. Netw., 5, 1, 1-36 (2009)
[43] Zhu, Y.; Song, J.; Dong, F., Applications of wireless sensor network in the agriculture environment monitoring, Procedia Eng., 16, 608-614 (2011)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.