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

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 indi- vidually 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% confidence interval of the average utility between 61 and 68% relative to the maximum utility in the centralized solutions. Additionally, our CGG-MC model outperforms the non-cooperation model by approximately 166% in terms of enlarging the coverage network area under a transmission delay time constraint.