Social clustering of vehicles based on semi-Markov processes

Abstract

Vehicle clustering is a crucial network management task for vehicular networks to address the broadcast storm problem and to cope with the rapidly changing network topology. Developing algorithms that create stable clusters is a very challenging procedure because of the highly dynamic moving patterns of vehicles and the dense topology. Previous approaches to vehicle clustering have been based on either topology-agnostic features, such as vehicle IDs or hard-to-set parameters, or have exploited very limited knowledge of vehicle trajectories. This paper develops a pair of algorithms, namely, sociological pattern clustering (SPC) and route stability clustering (RSC), the latter being a specialization of the former that exploits, for the 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 vehicles gathered by roadside units located in each subnetwork of a city and use the recently introduced clustering primitive of virtual forces. The mobility, i.e., mobile patterns of each vehicle, is modeled as semi-Markov processes. To assess the performance of the proposed clustering algorithms, we performed a detailed experimentation by simulation to compare its behavior with that of high-performance state-of-the-art algorithms, namely, the Low-Id, DDVC, and MPBC protocols. The comparison involved the investigation of the impact of a range of parameters on the performance of the protocols, including vehicle speed and transmission range, as well as the existence and strength of social patterns, for both urban and highway-like environments. All of the received results attested to the superiority of the proposed algorithms for creating stable and meaningful clusters. © 2015 IEEE.