Coalitional graph game for area maximization of multi-hop clustering in vehicular ad hoc networks

Abstract

Abstract Road traffic information can be utilized in many applications of intelligent transport systems. It can be collected from vehicles and sent over a vehicular ad hoc network (VANET) to roadside units (RSUs) acting as sink nodes. Due to rapid mobility and limited channel capacity in a VANET where vehicles must compete to access the RSUs to report their data, clustering is used to create a group of vehicles to facilitate data transfer to the RSUs. Unlike previous works that focus on cluster lifetime or throughput, we formulate a coalitional graph game for multi-hop clustering (CGG-MC) model to create a multi-hop cluster with the largest possible coverage area for a given transmission delay time constraint to economize on the number of RSUs installed. Vehicles cooperatively form a proper coalition with relation directed graphs among vehicles in a multi-hop cluster to collect, aggregate, and forward data to RSUs instead of individually competing to connect directly to RSUs. Vehicles decide to join or leave the coalition based on their individual utility, which is a weighted function of the coverage area, number of members in the cluster, relative velocities, distance to sink nodes, and transmission delay toward the sink nodes. The distributed-solution approach based on probabilistic greedy merging of coalitions is used to derive the grand coalition, and the probability of grand coalition formation is analyzed by using a discrete-time Markov chain. Our results show that the proposed solution approach yields a $$95\%$$ 95 % confidence interval of the average utility between 61 and $$68\%$$ 68 % relative to the maximum utility in the centralized-solutions. Additionally, our CGG-MC model outperforms the non-cooperation model by approximately $$166\%$$ 166 % in terms of enlarging the coverage network area under a transmission delay time constraint.

Keywords

• Clustering
• Coalitional graph game
• Game theory
• Vehicular ad hoc network (VANET)