DCA-DS: A Distributed Clustering Algorithm Based on Dominating Set for Internet of Vehicles

In this paper, we propose a new Distributed Clustering Algorithm Based on Dominating Set (DS) for Internet of Vehicles, called DCA-DS. To construct the DS, DCA-DS algorithm introduces a new parameter, called node span, which represents the number of the node neighbours that are not unclustered, including the node itself. DCA-DS algorithm is based on a simple heuristic method that uses a greedy strategy, where the node having the largest span is included in the DS, therefore it acts as new CH and all its neighbours become Cluster Members (CMs). This process repeats iteratively until there are no unclustered nodes left. Moreover, the node, which can hear two CHs or more, will act as Cluster Gateway (CG). Furthermore, DCA-DS algorithm takes care of the maintenance phase to keep clusters stability and structure. The proposed approach is implemented in NS-2 network simulator and VanetMobiSim mobility simulator to evaluate its performance.