Coalition Formation Games for Distributed Cooperation Among Roadside Units in Vehicular Networks

I. INTRODUCTION

• Prior research covered scheduling, protocols, testbeds, data distribution, antennas, safety, congestion control, and other V2R/V2V topics.The cited work includes a non-cooperative Bit Torrent-based RSU-to-vehicle data distribution approach and a Nash bargaining solution for V2V exchange.Source: §I · p. 1
• RSUs can coordinate the data classes sent to vehicles to exploit V2V sharing, diversify circulating information, and increase revenue.Vehicles often have time to download only a limited number of packets at each RSU, so sharing data received from different RSUs can broaden the classes they obtain.Source: §I · pp. 1–2
• Existing work studied V2R/V2V communications and non-cooperative RSU data delivery, but the paper identifies cooperative RSU strategies for improving data diversity as unexplored.The authors specifically note that they know of no prior study of this RSU-cooperation problem from a game-theoretic perspective.Source: §I · pp. 1–2
• The paper models RSU cooperation as a coalition formation game and proposes a distributed algorithm in which RSUs join or leave coalitions based on revenue gains and coordination costs.The algorithm is described as enabling Nash-stable partitions and adaptation to changes such as average vehicle traffic.Source: §I · p. 2

II. SYSTEM MODEL

• Each RSU serves vehicles traveling toward other RSUs, transmits one data class per direction at a time, and each vehicle downloads an average amount of data while at the RSU.The available data classes are ordered by priority weight.Source: §II · p. 2
• The payment operator charges vehicles in proportion to the data they carry after their first RSU and distributes revenue to the RSUs that supplied it.Higher-priority data classes have greater weights, while RSU network fees are treated as one-time payments that do not affect continuous revenue.Source: §II · p. 2
• Without cooperation, RSUs are assumed unaware of V2V sharing and therefore transmit the highest-priority class to maximize revenue.The non-cooperative utility counts the effective worth of downloaded data, weighted by the operator's price per unit.Source: §II · pp. 2–3
• The model treats potential V2V meetings as pairwise exchanges between vehicles traveling in opposite directions, with the number of possible pairs limited by traffic and decreasing with RSU distance.The proposed protocol uses this sharing opportunity to increase coalition revenue; the number of pairs is modeled using δ and distance.Source: §II · p. 3
• Cooperating RSUs exchange directional traffic and distance information, estimate vehicle pairs that may meet, and coordinate data classes to maximize the amount and diversity received through V2R and V2V.Coordination covers traffic between RSUs in the same coalition; traffic toward an RSU outside the coalition still receives the highest-priority class.Source: §II · p. 3
• In the two-RSU example, cooperation raises each RSU's payoff from 1.2β to 2.2β when one RSU sends class c1, the other sends c2, and cooperation has no cost.The example assumes two vehicles in each direction, two meeting pairs, and equal division of the resulting revenue.Source: §II · p. 4

III. COALITIONAL GAME FOR COOPERATION AMONG RSUS

• The coalition’s revenue includes gains from V2V content-sharing, alongside revenue from external traffic and internal traffic without sharing.The V2V-sharing component reflects vehicles exchanging data across RSUs in the same coalition.Source: §III · p. 5
• The model assumes successful receipt of transmitted data chunks; accounting for fading would reduce received packets but, the authors state, leave the cooperation advantage intact.The proposed cost function is linear in coalition size, while the analysis can apply to other cost functions.Source: §III · p. 5
• Coalition value is transferable: its utility can be apportioned among members, and a singleton coalition retains the non-cooperative utility.The game is modeled with RSUs as players and the value function as coalition utility.Source: §III · pp. 4–5
• The adopted individually rational egalitarian rule divides extra coalition benefits equally while preserving each RSU’s non-cooperative payoff.Other payoff-division rules, including the Shapley value or nucleolus, could also be used.Source: §III · pp. 5–6
• Coordination costs rise with coalition size, limiting cooperation gains and making disjoint coalitions generally more suitable than the grand coalition.The grand coalition may still form when cooperation costs are low relative to its benefits.Source: §III · pp. 5–6

IV. COALITION FORMATION ALGORITHM

• The section introduces coalition-formation concepts and an algorithm for forming RSU coalitions in a vehicular network.Source: §IV · p. 6

A. Coalition Formation Concepts

• The algorithm uses preference-based coalition formation, where RSUs compare possible coalitions containing them.The preference relation is defined as complete, reflexive, and transitive.Source: A. Coalition Formation Concepts · p. 6
• A coalition partition divides all RSUs into disjoint coalitions, and each RSU belongs to exactly one coalition in that partition.The section also denotes the coalition containing a given RSU within a partition.Source: A. Coalition Formation Concepts · p. 6
• An RSU’s move is acceptable only when its preference improves and the existing members of the destination coalition are not worse off.The move rule also uses a history set of coalitions the RSU previously visited and left.Source: A. Coalition Formation Concepts · p. 6

B. Distributed Coalition Formation Algorithm

• An RSU switches coalitions only when it strictly prefers the new membership, with destination members’ payoffs protected and its history set consulted.A switch changes the current partition by removing the RSU from its former coalition and adding it to the destination coalition.Source: B. Distributed Coalition Formation… · pp. 6–7
• The algorithm has three stages: neighbor discovery, distributed coalition formation, and cooperative V2R communication.During coalition formation, RSUs investigate switch operations in random order.Source: B. Distributed Coalition Formation… · pp. 7–8
• From any initial partition, the algorithm converges to disjoint coalitions; its final partition is Nash-stable and hence individually stable.The convergence argument relies on the finite number of partitions and limits revisits involving non-cooperative RSUs.Source: B. Distributed Coalition Formation… · pp. 7–8

C. Adaptation to Environmental Changes and Implementation

• Traffic changes modify vehicle-meeting possibilities between RSUs, creating a need for the network to reorganize.The coalition-formation algorithm is repeated periodically to adapt to environmental changes.Source: C. Adaptation to Environmental Changes… · p. 8
• Regardless of its starting position, the algorithm self-organizes RSUs into a Nash-stable partition after environmental changes.The period Ψ is chosen according to how quickly the environment changes, and the history set is reset each period.Source: C. Adaptation to Environmental Changes… · p. 8
• RSUs can individually perform switch operations without a centralized entity, with each switch search costing O(|Π|), or O(N) in the worst case.The algorithm’s complexity in changing environments is comparable to that in static environments, but it runs more often.Source: C. Adaptation to Environmental Changes… · p. 8

Simulation setup

• Simulations average over random RSU positions and traffic patterns; unless stated otherwise, they use L = 3 data classes and δ = 0.8.RSUs are randomly deployed in a 3 km × 3 km area, and each RSU’s vehicle count is selected uniformly from integers up to 25.Source: §V · pp. 8–9

Example coalition structure

• Nearby RSUs with comparable traffic form coalitions; the example partition is Nash-stable, and admitting RSU 9 to S2 would reduce existing members’ payoffs.RSU 9’s payoff would rise in S2, but the coalition members’ payoffs would fall because of cooperation cost, distance, and limited V2V-sharing prospects.Source: §V · p. 9

Average payoff as network size varies

• 20.5%–33.2% improvement in average payoff per RSU over the non-cooperative case occurs across tested network sizes; at N = 10, the gap from optimal is at most 2.3%.The comparison uses L = 3 data classes and δ = 0.8; the optimal partition is found by centralized exhaustive search.Source: Figure 3 · p. 9, §V · pp. 9–10

Coalition size as network size varies

• Average and average maximum coalition sizes rise with N, from around 1.9 for both at N = 2 to around 5.25 and 9.9 at N = 15.The authors conclude that the resulting network generally consists of a small number of relatively large coalitions.Source: Figure 4 · p. 10, §V · p. 10

Average payoff as V2V sharing varies

• Up to around 25% improvement in average payoff per RSU over non-cooperation occurs at δ = 1, while the gap from optimal is at most 2.8%.At δ = 0, the coalition scheme reduces to the non-cooperative approach.Source: Figure 5 · p. 10, §V · p. 10

Coalition size as V2V sharing varies

• At δ = 0.4, average and average maximum coalition sizes do not exceed 3 and 5.6; at δ = 1, they reach 4.9 and 7.8, respectively.Both coalition-size measures increase as the fraction of vehicles able to share V2V content increases.Source: §V · pp. 10–11, Figure 6 · p. 11

Convergence operations

• At N = 15, convergence averages 27.6 switch operations at δ = 0.4 and 43.2 at δ = 0.8; the latter is about 3 operations per RSU.At all tested network sizes, the δ = 0.4 operation count is approximately two-thirds of the count at δ = 0.8.Source: Figure 7 · p. 11, §V · p. 11

Adaptation over time

• Over five minutes, the N = 10 network adapts to traffic changes, ending with two coalitions after 41 switch operations.The algorithm was repeated every minute; the structure changed from three coalitions at t = 0 to four at t = 1, and remained unchanged between t = 2 and t = 3.Source: Figure 8 · p. 11, §V · p. 11

• Average payoff per RSU improves by 20.5%–33.2% relative to the non-cooperative scheme, depending on the scenario.Source: §VI · p. 12
• Cooperating RSUs coordinate transmitted data classes to diversify circulating information and exploit the underlying V2V content-sharing network to improve revenue.Source: §VI · p. 12
• The transferable-utility coalition-formation game lets RSUs individually join or leave coalitions based on payoffs accounting for increased revenue and coordination costs.Source: §VI · p. 12
• The algorithm always converges to a Nash-stable partition, and periodic repetition lets RSUs adapt network structure to environmental changes such as changing vehicle traffic.Source: §VI · p. 12