Research On Dynamic Coalition Formation Of Roadside Units Algorithm In Vehicular Networks

Recent vehicular networks constitutes the main building block of ITS and has attracted much significant attention. A diversity of applications are provided by vehicular networks. In order to support different applications, both vehicle-to-roadside (V2V) communications and Vehicle-to-roadside (V2R) communications need to be supported in vehicular networks, meanwhile the roadside units connected with each other by wired links or wireless networks constitute the backbone network. In V2R communications, due to the limited radio range of the RSU and high speed of traveling vehicles, a vehicle can keep a short period at a RSU and download a little of packets. To solve this problem, Walid, et al propose a novel cooperative V2R (CV2R) communications and a coalition formation game scheme, so that the backbone network is partitioned into several coalitions. On one hand, the proposed scheme can improve the diversity of information circulating in the network and exploit the data exchange capabilities of the underlying V2V networks with the CV2R communication in the same coalition; On the other hand, the proposed scheme can decrease the CV2R communication costs with the non-cooperative V2R communication(NCV2R) among different coalitions.In this paper, by analyzing the coalition formation game scheme, there are two problems: local optimum and long partition time. So, the paper proposes the modified Kernighan-Lin algorithm scheme(MKLs) and the modified Fiduccia-Mattheyses algorithm scheme(MFMs) to reduce the probability of local optimum. Meanwhile, the paper proposes the multilevel hyper-graph partitioning based on heavy edge matching scheme(MHEMs) to reduce the switch times and shorten the partition time. Finally, simulation results show that compare to noncooperation scheme, globe cooperation scheme and coalition game scheme, the MKLs can improves the performance (in terms of the average payoff per roadside unit) up to31.5%,14.3%,8.4%, and the MFMs can improves the performance up to33.9%,17.2%,10.4%; compare to coalition game scheme, the switch times of the MHEMs can be reduce to85.7%.