A Stable Clustering Algorithm for VANETs

Abstract

Despite the clear advantages offered by Vehicular Ad-hoc Networks (VANETs) over Mobile Ad-hoc Networks (MANETs), which stem from their ability to regulate vehicular movement according to traffic laws, including actions like stopping, slowing down, and changing lanes, VANETs still grapple with instability issues. These issues result from various factors such as high-speed vehicle behaviors, frequent vehicle joinings and departures, link failures, and alterations in network topology. Numerous algorithms have been developed to enhance network stability in terms of maintaining vehicles within a cluster for extended periods, whether they serve as cluster heads or cluster members, minimizing packet loss rates, and achieving this stability with minimal message and packet exchanges to avoid network bottlenecks. Most of these algorithms focus on organizing and clustering vehicles based on their mobility patterns. Stability means the continuity of communication between vehicles on the one hand and the base station on the other hand, thus delivering packets close to real time, and thus an almost non-existent rate of data loss. In the proposed algorithm, this means a group of vehicles that travel together at close distances and in the same direction along the distance traveled. This thesis primarily investigates two well-known clustering algorithms: the Center-Based Secure and Stable Clustering algorithm (CBSC) and the Scalable Clustering algorithm (SCalE). CBSC determines clustering centers based on vehicle density to maximize cluster size, while also considering vehicle speed, acceleration, and distance between vehicles for cluster head selection. However, CBSC overlooks vehicle behaviors that could lead to link disruptions when vehicles make turns or exit highways. On the other hand, SCalE aims to address these issues by using vehicle behavior as a criterion for cluster head selection, focusing on stable vehicles that are less likely to leave the road. It employs differences in speeds and positions to choose cluster heads, ultimately extending the cluster members' lifetimes. However, the authors of SCalE did not account for scenarios where vehicles travel in opposite directions, briefly coming close to each other and the cluster head before moving away, which affects cluster duration. To address this, the proposed Hybrid Stable Clustering Algorithm (HSCA) was introduced. HSCA strives to create clusters where vehicles travel closely together for longer distances and durations. It uses vehicle density to determine cluster centers and adopts the cluster head selection method from SCalE, focusing on vehicle behavior while disregarding vehicles traveling in different directions. HSCA has demonstrated its effectiveness across various simulation scenarios, including changes in the number of vehicles, their speeds, and cluster ranges. Despite resulting in more cluster compared to the previous algorithms, HSCA maintains consistent result quality due to its focus on selecting cluster elements based on behavior and movement direction. Additionally,

XIV changes in vehicle speeds and locations are accommodated within the cluster head election process, ensuring adaptability to different simulation scenarios. We did not mention the security aspects. Although we meant to talk about Wi-Fi, we mentioned it because communication between vehicles is based on this technology. Based on the experiments that were conducted, it was found that the proposed algorithm (HSCA) was able to outperform its counterparts (SCalE and CBSC) in the improvement rate. It was able to outperform SCALE in all cases that were tested with a high percentage, and it was also able to outperform the CBSC algorithm in most scenarios, and we clarified Reasons why it is not superior in some scenarios. The proposed algorithm achieved an improvement rate of 45% in terms of CH life time compared to CBSC when changing the number of nodes, and 196% compared to SCALE. Likewise, in CM life time, HSCA achieved an improvement of 89% compared to CBSC and 230% improvement compared to SCALE. When implementing the scenario of changing the number of nodes and knowing the impact of this on the time required to form a cluster, the HSCA algorithm achieved a better improvement compared to CBSC and SCALE by 22% and 46.46.85%, respectively. The proposed algorithm was able to outperform SCALE in terms of CH and CM life time under the cluster range change, while the results were close to CBSC, where the improvement rate was 117% and 19%, respectively. The same was true for CM life time, where the percentage was 57% and 2.9%, respectively. While the effect of mobility speed was remarkable, the proposed algorithm achieved an improvement of 187% compared to SCale in terms of CH life time and 116% in terms of CH life time. Keywords: VANET, CM, CH, SCalE, CBSC, HSCA.