Social Clustering of Vehicles Based on Semi-Markov Processes

Vehicle clustering is a crucial network managementtask for vehicular networks in order to address the broadcaststorm problem, and also to cope with rapidly changing networktopology. Developing algorithms that createstable clustersis avery challenging procedure because of the highly dynamic movingpatterns of vehicles and the dense topology. Previous approachesto vehicle clustering have been based on either topology-agnosticfeatures, such as vehicle IDs, on hard to set parameters, orhave exploited very limited knowledge of vehicle trajectories.This article develops a pair of algorithms, namelySociologicalPattern Clustering (SPC), andRoute Stability Clustering (RSC),the latter being a specialization of the former that exploit, forthe first time in the relevant literature, the “social behavior”of vehicles, i.e. their tendency to share the same/similar routes.Both methods exploit the historic trajectories of vehiclesgatheredby road-side units located in each subnetwork of a city, anduse the recently introduced clustering primitive ofvirtual forces.The mobility, i.e. mobile patterns of each vehicle are modeledas semi-Markov processes. In order to assess the performanceof the proposed clustering algorithms, we performed a detailedexperimentation by simulation to compare its behavior withthat of high-performance state-of-the-art algorithms, namely, theLow-Id,DDVCandMPBCprotocols. The comparison involvedthe investigation of the impact of a range of parameters onthe performance of the protocols, including vehicle speed andtransmission range as well as the existence and strength of socialpatterns, for both urban and highway-like environments. Allthe received results attested to the superiority of the proposedalgorithms for creating stable and meaningful clusters.