Plummeting Broadcast Storm Problem in Highways by Clustering Vehicles Using Dominating Set and Set Cover

Area of Science:

• Computer Science
• Network Engineering
• Wireless Communication

Background:

• Vehicular Ad-hoc Networks (VANETs) are crucial for road safety, enabling decentralized alert message exchange.
• The broadcast storm problem, caused by excessive rebroadcasts, hinders efficient message dissemination in VANETs.
• Clustering vehicles is a common solution, but optimizing cluster head and gateway selection is key to reducing rebroadcasts.

Purpose of the Study:

• To propose a novel distributed algorithm, CDS_SC, for efficient cluster formation in VANETs.
• To address the broadcast storm problem by minimizing rebroadcasting vehicles through optimized cluster head and gateway selection.
• To enhance the stability and efficiency of alert message dissemination in VANETs.

Main Methods:

• Developed the Connected Dominating Set and Set Cover (CDS_SC) algorithm for distributed, event-triggered cluster formation.
• Utilized a dominating set to select cluster heads and set covering to select cluster gateways.
• Implemented an incremental cluster construction approach based on local neighborhood information.

Main Results:

• The CDS_SC algorithm achieved 99% to 100% reachability of alert messages in simulations.
• Significantly reduced rebroadcasting vehicles to only 6% to 10% in average and dense traffic scenarios.
• Demonstrated increased cluster formation stability and reduced rebroadcasting by allowing passive cluster heads.

Conclusions:

• The CDS_SC algorithm effectively mitigates the broadcast storm problem in VANETs.
• The proposed method offers a stable and efficient solution for alert message dissemination in diverse traffic conditions.
• CDS_SC's distributed and event-triggered nature makes it suitable for real-world VANET implementations.