{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:31:18Z","timestamp":1761611478253,"version":"build-2065373602"},"reference-count":33,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2019,5,12]],"date-time":"2019-05-12T00:00:00Z","timestamp":1557619200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>\u201cVehicular Ad-hoc Networks\u201d (VANETs): As an active research area in the field of wireless sensor networks, they ensure road safety by exchanging alert messages about unexpected events in a decentralized manner. One of the significant challenges in the design of an efficient dissemination protocol for VANETs is the broadcast storm problem, owing to the large number of rebroadcasts. A generic solution to prevent the broadcast storm problem is to cluster the vehicles based on topology, density, distance, speed, or location in such a manner that only a fewer number of vehicles will rebroadcast the alert message to the next group. However, the selection of cluster heads and gateways of the clusters are the key factors that need to be optimized in order to limit the number of rebroadcasts. Hence, to address the aforementioned issues, this paper presents a novel distributed algorithm CDS_SC: Connected Dominating Set and Set Cover for cluster formation that employs a dominating set to choose cluster heads and set covering to select cluster gateways. The CDS_SC is unique among state-of-the-art algorithms, as it relies on local neighborhood information and constructs clusters incrementally. Hence, the proposed method can be implemented in a distributed manner as an event-triggered protocol. Also, the stability of cluster formation is increased along with a reduction in rebroadcasting by allowing a cluster head to be passive when all its cluster members can receive the message from the gateway vehicles. The simulation was carried out in dense, average, and sparse traffic scenarios by varying the number of vehicles injected per second per lane. Besides, the speed of each individual vehicle in each scenario was varied to test the degree of cohesion between vehicles with different speeds. The simulation results confirmed that the proposed algorithm achieved 99% to 100% reachability of alert messages with only 6% to 10% of rebroadcasting vehicles in average and dense traffic scenarios.<\/jats:p>","DOI":"10.3390\/s19092191","type":"journal-article","created":{"date-parts":[[2019,5,13]],"date-time":"2019-05-13T05:35:39Z","timestamp":1557725739000},"page":"2191","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Plummeting Broadcast Storm Problem in Highways by Clustering Vehicles Using Dominating Set and Set Cover"],"prefix":"10.3390","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8671-4300","authenticated-orcid":false,"given":"S.","family":"Kamakshi","sequence":"first","affiliation":[{"name":"Centre for Information Super Highway (CISH), School of Computing, SASTRA Deemed University, Thanjavur, Tamil Nadu 613401, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7870-7944","authenticated-orcid":false,"given":"V. S.","family":"Shankar Sriram","sequence":"additional","affiliation":[{"name":"Centre for Information Super Highway (CISH), School of Computing, SASTRA Deemed University, Thanjavur, Tamil Nadu 613401, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,5,12]]},"reference":[{"key":"ref_1","unstructured":"(2018, April 21). World Health Organisation Road Traffic Injuries. Available online: http:\/\/www.who.int\/mediacentre\/factsheets\/fs358\/en\/."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Khaliq, K., Chughtai, O., Shahwani, A., Qayyum, A., Pannek, J., Khaliq, K.A., Chughtai, O., Shahwani, A., Qayyum, A., and Pannek, J. (2019). An Emergency Response System: Construction, Validation, and Experiments for Disaster Management in a Vehicular Environment. Sensors, 19.","DOI":"10.3390\/s19051150"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Ni, S.-Y., Tseng, Y.-C., Chen, Y.-S., and Sheu, J.-P. (1999, January 15\u201319). The Broadcast Storm Problem in a Mobile Ad hoc Network. Proceedings of the 5th Annual ACM\/IEEE International Conference on Mobile Computing and Networking\u2014MobiCom \u201999, Seattle, WA, USA.","DOI":"10.1145\/313451.313525"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Jakubiak, J., and Koucheryavy, Y. (2008, January 10\u201312). State of the Art and Research Challenges for VANETs. Proceedings of the 2008 5th IEEE Consumer Communications and Networking Conference, Las Vegas, NV, USA.","DOI":"10.1109\/ccnc08.2007.212"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Yousefi, S., Mousavi, M., and Fathy, M. (2006, January 21\u201323). Vehicular Ad Hoc Networks (VANETs): Challenges and Perspectives. Proceedings of the 2006 6th International Conference on ITS Telecommunications, Chengdu, China.","DOI":"10.1109\/ITST.2006.289012"},{"key":"ref_6","first-page":"134","article-title":"Clustering in Vehicular Ad hoc Networks: Taxonomy, Challenges and Solutions","volume":"1","author":"Bali","year":"2014","journal-title":"Veh. Commun."},{"key":"ref_7","unstructured":"Wang, X., Shroff, N., and Pitsillides, A. (2008, January 17\u201319). Speed Adaptive Probabilistic Flooding in Cooperative Emergency Warning. Proceedings of the 4th Annual International Conference on Wireless Internet, Maui, HI, USA."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1145\/263876.263885","article-title":"A Cluster-based Approach for Routing in Dynamic Networks","volume":"27","author":"Krishna","year":"1997","journal-title":"ACM SIGCOMM Comput. Commun. Rev."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1265","DOI":"10.1109\/49.622910","article-title":"Adaptive Clustering for Mobile Wireless Networks","volume":"15","author":"Lin","year":"2006","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Hu, M., Zhong, Z., Ni, M., Baiocchi, A., Hu, M., Zhong, Z., Ni, M., and Baiocchi, A. (2016). Design and Analysis of A Beacon-Less Routing Protocol for Large Volume Content Dissemination in Vehicular Ad Hoc Networks. Sensors, 16.","DOI":"10.3390\/s16111834"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/j.jnca.2014.08.009","article-title":"Forwarder smart selection protocol for limitation of broadcast storm problem","volume":"47","author":"Vegni","year":"2015","journal-title":"J. Netw. Comput. Appl."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"2621","DOI":"10.1109\/TVT.2015.2421277","article-title":"Multihop-Cluster-Based IEEE 802.11p and LTE Hybrid Architecture for VANET Safety Message Dissemination","volume":"65","author":"Ucar","year":"2016","journal-title":"IEEE Trans. Veh. Technol."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Dong, W., Lin, F., Zhang, H., and Yin, Y. (2017, January 6\u20138). A cluster-based recursive broadcast routing algorithm to propagate emergency messages in city VANETs. Proceedings of the 2017 IEEE 9th International Conference on Communication Software and Networks (ICCSN), Guangzhou, China.","DOI":"10.1109\/ICCSN.2017.8230103"},{"key":"ref_14","unstructured":"Ruiz, P., Dorronsoro, B., Khadraoui, D., Bouvry, P., and Tard\u00f3n, L. (2008, January 3\u20136). BODYF-A Parameterless Broadcasting Protocol Over Dynamic Forest. Proceedings of the Special Session on Parallel and Grid Computing for Optimization as Part of the 2008 International Conference High Performance Computing & Simulation (HPCS\u201908) and in Conjunction with the 22nd European Conference on Modeling and Simulation (ECMS 2008), Nicosia, Cyprus."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/j.adhoc.2011.06.005","article-title":"Information dissemination in VANETs based upon a tree topology","volume":"10","author":"Ruiz","year":"2012","journal-title":"Ad Hoc Netw."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"685","DOI":"10.1016\/j.jnca.2012.12.023","article-title":"Position-based Routing in Vehicular Networks: A Survey","volume":"36","author":"Bilal","year":"2013","journal-title":"J. Netw. Comput. Appl."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1155","DOI":"10.1007\/s11277-017-4913-9","article-title":"Adaptive Mobility and Range Based Clustering Dependent MAC Protocol for Vehicular Ad Hoc Networks","volume":"98","author":"Pal","year":"2018","journal-title":"Wirel. Pers. Commun."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/j.adhoc.2014.09.007","article-title":"Traffic Density Estimation in Vehicular Ad hoc Networks: A Review","volume":"24","author":"Darwish","year":"2015","journal-title":"Ad Hoc Netw."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Benkerdagh, S., and Duvallet, C. (2019). Cluster-based Emergency Message Dissemination Strategy for VANET using V2V Communication. Int. J. Commun. Syst., e3897.","DOI":"10.1002\/dac.3897"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1212","DOI":"10.1002\/dac.1226","article-title":"Analysis and Simulation of a Message Dissemination Algorithm for VANET","volume":"24","author":"Busson","year":"2011","journal-title":"Int. J. Commun. Syst."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Mohammed Nasr, M., Abdelgader, A., Wang, Z.-G., Shen, L.-F., Mohammed Nasr, M.M., Abdelgader, A.M.S., Wang, Z.-G., and Shen, L.-F. (2016). VANET Clustering Based Routing Protocol Suitable for Deserts. Sensors, 16.","DOI":"10.3390\/s16040478"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"906084","DOI":"10.1155\/2014\/906084","article-title":"Non-GPS Data Dissemination for VANET","volume":"10","author":"Rojviboonchai","year":"2014","journal-title":"Int. J. Distrib. Sens. Netw."},{"key":"ref_23","first-page":"1661","article-title":"Distributed and Weighted Clustering based on d-Hop Dominating Set for Vehicular Networks","volume":"10","author":"Shi","year":"2016","journal-title":"KSII Trans. Internet Inf. Syst."},{"key":"ref_24","unstructured":"Sun, M.T., Feng, W.C., Lai, T.H., Yamada, K., Okada, H., and Fujimura, K. (2000, January 21\u201324). GPS-based message broadcasting for inter-vehicle communication. Proceedings of the 2000 International Conference on Parallel Processing, Toronto, ON, Canada."},{"key":"ref_25","first-page":"3257","article-title":"An Optimal ODAM-Based Broadcast Algorithm for Vehicular Ad-Hoc Networks","volume":"6","author":"Sun","year":"2012","journal-title":"KSII Trans. Internet Inf. Syst."},{"key":"ref_26","unstructured":"Casteigts, A., and Chaumette, S. (2005, January 15\u201317). Dynamicity Aware Graph Relabeling Systems (DA-GRS), A Local Computation based Model to Describe Manet Algorithms. Proceedings of the Parallel and Distributed Computing and Systems, Innsbruck, Austria."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1109\/TMC.2010.253","article-title":"Acknowledgment-Based Broadcast Protocol for Reliable and Efficient Data Dissemination in Vehicular Ad Hoc Networks","volume":"11","author":"Ros","year":"2012","journal-title":"IEEE Trans. Mob. Comput."},{"key":"ref_28","first-page":"1223","article-title":"Beacon-Less Broadcast Protocol for Vehicular Ad Hoc Networks","volume":"8","author":"Khan","year":"2014","journal-title":"KSII Trans. Internet Inf. Syst."},{"key":"ref_29","first-page":"3512","article-title":"Intelligent Clustering in Vehicular ad hoc Networks","volume":"10","author":"Bajwa","year":"2016","journal-title":"KSII Trans. INTERNET Inf. Syst."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1016\/j.adhoc.2017.05.002","article-title":"Reliable Data Dissemination Protocol for VANET Traffic Safety Applications","volume":"63","author":"Carlos","year":"2017","journal-title":"Ad Hoc Netw."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/j.icte.2017.11.009","article-title":"Novel Store\u2013Carry\u2013Forward Scheme for Message Dissemination in Vehicular Ad-hoc Networks","volume":"3","author":"Nguyen","year":"2017","journal-title":"ICT Express"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/S0167-5060(08)71047-1","article-title":"Unit Disk Graphs","volume":"48","author":"Clark","year":"1991","journal-title":"Ann. Discret. Math."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Karp, R.M. (1972). Reducibility among Combinatorial Problems. Complexity of Computer Computations, Springer.","DOI":"10.1007\/978-1-4684-2001-2_9"}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/19\/9\/2191\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T12:51:14Z","timestamp":1760187074000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/19\/9\/2191"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,12]]},"references-count":33,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2019,5]]}},"alternative-id":["s19092191"],"URL":"https:\/\/doi.org\/10.3390\/s19092191","relation":{},"ISSN":["1424-8220"],"issn-type":[{"type":"electronic","value":"1424-8220"}],"subject":[],"published":{"date-parts":[[2019,5,12]]}}}