{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,30]],"date-time":"2026-03-30T02:44:59Z","timestamp":1774838699151,"version":"3.50.1"},"reference-count":27,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2021,5,31]],"date-time":"2021-05-31T00:00:00Z","timestamp":1622419200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100004837","name":"Ministerio de Ciencia e Innovaci\u00f3n","doi-asserted-by":"publisher","award":["PID2019-104156GB-I00"],"award-info":[{"award-number":["PID2019-104156GB-I00"]}],"id":[{"id":"10.13039\/501100004837","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Dominating sets are among the most well-studied concepts in graph theory, with many real-world applications especially in the area of wireless sensor networks. One way to increase network lifetime in wireless sensor networks consists of assigning sensors to disjoint dominating node sets, which are then sequentially used by a sleep\u2013wake cycling mechanism. This paper presents a greedy heuristic for solving a weighted version of the maximum disjoint dominating sets problem for energy conservation purposes in wireless sensor networks. Moreover, an integer linear programming model is presented. Experimental results based on a large set of 640 problem instances show, first, that the integer linear programming model is only useful for small problem instances. Moreover, they show that our algorithm outperforms recent local search algorithms from the literature with respect to both solution quality and computation time.<\/jats:p>","DOI":"10.3390\/a14060170","type":"journal-article","created":{"date-parts":[[2021,5,31]],"date-time":"2021-05-31T21:42:06Z","timestamp":1622497326000},"page":"170","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["A Greedy Heuristic for Maximizing the Lifetime of Wireless Sensor Networks Based on Disjoint Weighted Dominating Sets"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9980-0758","authenticated-orcid":false,"given":"Samir","family":"Balbal","sequence":"first","affiliation":[{"name":"Department of Computer Science, Ferhat Abbas University S\u00e9tif 1, S\u00e9tif 19000, Algeria"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5842-2850","authenticated-orcid":false,"given":"Salim","family":"Bouamama","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Mechatronics Laboratory (LMETR)\u2014E1764200, Ferhat Abbas University S\u00e9tif 1, S\u00e9tif 19000, Algeria"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1736-3559","authenticated-orcid":false,"given":"Christian","family":"Blum","sequence":"additional","affiliation":[{"name":"Artificial Intelligence Research Institute (IIIA-CSIC), Campus of the UAB, 08193 Bellaterra, Spain"}]}],"member":"1968","published-online":{"date-parts":[[2021,5,31]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"828","DOI":"10.1109\/COMST.2017.2650979","article-title":"A survey of network lifetime maximization techniques in wireless sensor networks","volume":"19","author":"Yetgin","year":"2017","journal-title":"IEEE Commun. Surv. Tutor."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Rodrigues, L.M., Montez, C., Budke, G., Vasques, F., and Portugal, P. (2017). Estimating the lifetime of wireless sensor network nodes through the use of embedded analytical battery models. J. Sens. Actuator Netw., 6.","DOI":"10.3390\/jsan6020008"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Lewandowski, M., P\u0142aczek, B., and Bernas, M. (2021). Classifier-Based Data Transmission Reduction in Wearable Sensor Network for Human Activity Monitoring. Sensors, 21.","DOI":"10.3390\/s21010085"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"101966","DOI":"10.1016\/j.adhoc.2019.101966","article-title":"Maximization of wireless sensor network lifetime using solar energy harvesting for smart agriculture monitoring","volume":"94","author":"Sharma","year":"2019","journal-title":"Ad Hoc Netw."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Lewandowski, M., Bernas, M., Loska, P., Szyma\u0142a, P., and P\u0142aczek, B. (2019). Extending Lifetime of Wireless Sensor Network in Application to Road Traffic Monitoring. International Conference on Computer Networks, Springer.","DOI":"10.1007\/978-3-030-21952-9_9"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"2383","DOI":"10.1109\/ACCESS.2017.2669020","article-title":"Maximizing lifetime in wireless sensor network for structural health monitoring with and without energy harvesting","volume":"5","author":"Mansourkiaie","year":"2017","journal-title":"IEEE Access"},{"key":"ref_7","unstructured":"Cardei, M., Thai, M.T., Li, Y., and Wu, W. (2005, January 13\u201317). Energy-efficient target coverage in wireless sensor networks. Proceedings of the IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies, Miami, FL, USA."},{"key":"ref_8","unstructured":"Slijepcevic, S., and Potkonjak, M. (2001, January 11\u201314). Power efficient organization of wireless sensor networks. Proceedings of the ICC 2001\u2014IEEE International Conference on Communications, Helsinki, Finland."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Wang, H., Li, Y., Chang, T., and Chang, S. (2018). An effective scheduling algorithm for coverage control in underwater acoustic sensor network. Sensors, 18.","DOI":"10.3390\/s18082512"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"2245","DOI":"10.1109\/TCYB.2017.2731598","article-title":"A novel integer-coded memetic algorithm for the set k-cover problem in wireless sensor networks","volume":"48","author":"Liao","year":"2017","journal-title":"IEEE Trans. Cybern."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"20500","DOI":"10.3390\/s141120500","article-title":"Memetic algorithm-based multi-objective coverage optimization for wireless sensor networks","volume":"14","author":"Chen","year":"2014","journal-title":"Sensors"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"108167","DOI":"10.1016\/j.measurement.2020.108167","article-title":"Energy efficient target coverage for a wireless sensor network","volume":"165","author":"Balaji","year":"2020","journal-title":"Measurement"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"D\u2019Ambrosio, C., Iossa, A., Laureana, F., and Palmieri, F. (2020). A genetic approach for the maximum network lifetime problem with additional operating time slot constraints. Soft Comput., 1\u20137.","DOI":"10.1007\/s00500-020-04821-y"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Li, J., Potru, R., and Shahrokhi, F. (2020). A Performance Study of Some Approximation Algorithms for Computing a Small Dominating Set in a Graph. Algorithms, 13.","DOI":"10.3390\/a13120339"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Li, R., Hu, S., Liu, H., Li, R., Ouyang, D., and Yin, M. (2019). Multi-Start Local Search Algorithm for the Minimum Connected Dominating Set Problems. Mathematics, 7.","DOI":"10.3390\/math7121173"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Bouamama, S., and Blum, C. (2021). An Improved Greedy Heuristic for the Minimum Positive Influence Dominating Set Problem in Social Networks. Algorithms, 14.","DOI":"10.3390\/a14030079"},{"key":"ref_17","unstructured":"Garey, M., and Johnson, D. (1979). Computers and Intractability. A Guide to the Theory of NP-Completeness, W. H. Freeman."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1142\/S021926590200063X","article-title":"Wireless sensor networks with energy efficient organization","volume":"3","author":"Cardei","year":"2002","journal-title":"J. Interconnect. Netw."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1137\/S0097539700380754","article-title":"Approximating the domatic number","volume":"32","author":"Feige","year":"2002","journal-title":"SIAM J. Comput."},{"key":"ref_20","unstructured":"Moscibroda, T., and Wattenhofer, R. (2005, January 4\u20138). Maximizing the lifetime of dominating sets. Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium, Denver, CO, USA."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Nguyen, T.N., and Huynh, D.T. (2007, January 1\u20133). Extending sensor networks lifetime through energy efficient organization. Proceedings of the International Conference on Wireless Algorithms, Systems and Applications (WASA 2007), Chicago, IL, USA.","DOI":"10.1109\/WASA.2007.7"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Islam, K., Akl, S.G., and Meijer, H. (2009, January 20\u201323). Maximizing the lifetime of wireless sensor networks through domatic partition. Proceedings of the 2009 IEEE 34th Conference on Local Computer Networks, Zurich, Switzerland.","DOI":"10.1109\/LCN.2009.5355161"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"17527","DOI":"10.1109\/ACCESS.2018.2819083","article-title":"Dominating set algorithms for wireless sensor networks survivability","volume":"6","author":"Pino","year":"2018","journal-title":"IEEE Access"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Haynes, T.W., Hedetniemi, S.T., and Henning, M.A. (2020). Topics in Domination in Graphs, Springer.","DOI":"10.1007\/978-3-030-51117-3"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/j.simpat.2015.11.001","article-title":"A hybrid algorithmic model for the minimum weight dominating set problem","volume":"64","author":"Bouamama","year":"2016","journal-title":"Simul. Model. Pract. Theory"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"3647","DOI":"10.1016\/j.ins.2010.06.009","article-title":"Dominating sets in directed graphs","volume":"180","author":"Pang","year":"2010","journal-title":"Inf. Sci."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.cor.2015.10.014","article-title":"Construct, Merge, Solve & Adapt: A new general algorithm for combinatorial optimization","volume":"68","author":"Blum","year":"2016","journal-title":"Comput. Oper. Res."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/6\/170\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T06:09:29Z","timestamp":1760162969000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/6\/170"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,31]]},"references-count":27,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2021,6]]}},"alternative-id":["a14060170"],"URL":"https:\/\/doi.org\/10.3390\/a14060170","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,5,31]]}}}