<figure><img src="image_1.png" /></figure>

HAL
open science

# A Game Theoretical Priority-Aware R2V Task Offloading Framework For Vehicular Fog Networks

Kinda Khawam, Maurice Khabbaz, Joe Saad

► To cite this version:

Kinda Khawam, Maurice Khabbaz, Joe Saad. A Game Theoretical Priority-Aware R2V Task Offloading Framework For Vehicular Fog Networks. IEEE Open Journal of the Communications Society, 2025, pp.1-1. 10.1109/ojcoms.2025.3553787. hal-05059740

HAL Id: hal-05059740

https://hal.science/hal-05059740v1

Submitted on 27 Jun 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Received 27 February 2025; accepted 19 March 2025. Date of publication 21 March 2025; date of current version 4 April 2025.

Digital Object Identifier 10.1109/OJCOMS.2025.3553787

# A Game Theoretical Priority-Aware R2V Task Offloading Framework for Vehicular Fog Networks

KINDA KHAWAM<fnref n="1" />, MAURICE KHABBAZ<fnref n="1" />,<fnref n="2" /> (Senior Member, IEEE), AND JOE SAAD<fnref n="1" />,<fnref n="3" />

CORRESPONDING AUTHOR: M. KHABBAZ (e-mail: mk321@aub.edu.lb).

This work was supported by the Research Projects and Creative Works fund offered by the Faculty of Arts and Science's Dean's Office at the American University of Beirut.

**ABSTRACT** Modern vehicles, equipped with advanced digital infrastructure, are transforming from mere transportation units to powerful mobile servers. This trend, coupled with the rise of mobile edge computing (MEC), presents a unique opportunity to leverage vehicles as temporary computing resources. Roadside Units (RSUs) can then offload urgent tasks to passing vehicles, enabling ubiquitous connectivity and low-latency services. However, efficient task offloading remains a challenge. This paper proposes a two-level resource management framework for Priority-Aware RSU-to-Vehicle (PA-R2V) Task Offloading (PA-R2VTO) to address this issue. The first level utilizes a two-stage Stackelberg game to incentivize vehicles within RSU coverage to allocate a portion of their computing resources. The second level focuses on task assignment to participating vehicles. Two computation modes are considered: serial and parallel. Serial computation leverages a Multiple Knapsack Problem (MKP) formulation to prioritize tasks based on deadlines, while parallel computation employs a non-cooperative congestion game model. Both approaches are compared against the traditional Earliest Deadline First (EDF) scheduling algorithm. Extensive simulations validate the framework's effectiveness, paving the way for a more tangible realization of the Vehicle-as-a-Resource (VaaSR) concept.

**INDEX TERMS** Priority scheduling, task offloading, RSU, vehicular networks, serial and parallel computing, knapsack problem, non-cooperative game.

# I. INTRODUCTION

## A. PRELIMINARIES

TODAY'S manufactured vehicles, owing to their embedded paramount electronic, computing and wireless communication technology, parade a peculiar role that transcends their typical transportation utility. Indeed, with ubiquitous digital broadband connectivity, now, brought to the wheels, these vehicles are being sought by operators and service providers as cost-effective powerful server-grade computing and storage nodes that contribute to the rise of a novel mobile edge cloud/fog networking/computing paradigm, [1], [2]. These networks, in turn, support the proper functionality of multifarious emerging applications/services that necessitate handling data in the vicinity of their generating sources (e.g., autonomous driving [3], user-centric 5G applications [4], Internet-of-Things [5],

augmented reality [6], etc). Indeed, parallel to the deployment of roadway edge computing hot spots (e.g. RoadSide Units (RSUs) connected to edge servers) that cover specific areas, an importuning call for the formation of ultra-large-scale metro-fog networks (i.e., overlaying an entire metropolitan area and/or interconnecting separate cities) has been trending over the past years, [7]. Vehicular networks catalyze the realization of this objective given the widespread vehicles navigating along the metro-wide road networks together with the innate platooning characteristics of vehicular traffic allowing for the formation of vehicle-based computing clusters (e.g., [8]) that may satisfy the pressing data sharing, storage and processing requirements of the aforementioned applications, [9]. Various are the related example scenarios that may be enumerated. For instance, vehicles may store digital content within their

<footnote n="1">¹DAVID Laboratory, Versailles St-Quentin University, 78035 Versailles, France</footnote>

<footnote n="2">²CMPS Department, American University of Beirut, Beirut 1107-2020, Lebanon</footnote>

<footnote n="3">³PAC and PES Departments, Murex, 75782 Paris, France</footnote>
OnBoard Units' (OBUs) buffers, then, physically carry such content and share it with surrounding nodes they encounter throughout their navigation along the roads. Alternatively, stationary vehicles located in a parking area may offer regional micro-cloud storage and/or caching services for region-specific content and, thus, enable proximity users (e.g., pedestrians, passing by vehicles) to have anytime access to such content without resorting to, for example, cellular communications. Even mobile vehicles can, for example, provision users as well as other proximity vehicles roaming within secluded areas with temporary though precious computing resources that typically are very scarce and often unavailable in such areas. Even RoadSide Units (RSUs) that may either be completely isolated or connected to edge computing servers with low processing capabilities or probably happen to be overloaded, can also opportunistically exploit the computing capacities of passing by vehicles for the purpose of completing some urgent deadline constrained tasks; these tasks can pertain to either other vehicles or also possibly other users roaming within the RSU's range. This latter scenario, although subject to notably limiting constraints, has rarely been addressed in the literature. Indeed, the all-time-anywhere connectivity and low latency edge service availability targeted by the next generation carrier grade networks is still contingent to the resolution of numerous persisting challenges one of which, namely Priority-Aware RSU-to-Vehicle (R2V) Task Offloading (PA-R2VTO) is investigated herein.

## B. LITERATURE SURVEY AND MOTIVATION

In addition to the feasibility, design principles, communication, clustering, security/privacy (e.g., [10]) and data management (e.g., [11]), the problem of computational task offloading in the context of Mobile Edge Computing (MEC) scenarios has been recently receiving significant momentum. A prime selection of existing work (e.g., [12], [13], [14], [15], [16] and references thereof) have addressed this problem in contexts of mostly metropolitan scenarios where RSUs were deployed along roadways with networking and power supply infrastructure availability; hence, allowing these RSUs to remain continuously operational over time. In such contexts, vehicles passing by an RSU opportunistically offloaded complex computational tasks to that RSU, which, in turn routed these tasks towards any of the above-mentioned computational facilities; typically, those deemed most suitable to execute and complete a given task or batch of tasks with the objective of achieving optimal trade-offs between resource availability, consumption, round trip time and computational efficiency.

Despite their appeal and embraced performance superiority (e.g., [16]), those ingeniously architected multi-tier MEC solutions, soon enough, were found to experience new challenges imposed by the rapid proliferation and market penetration of MEC technology; this speeding the induction of an unparalleled evolution of novel but resource exhaustive services such as augmented-reality-enhanced and

artificial-intelligence-assisted autonomous driving, which requires continuous smart sensing of vehicles' surroundings, prediction of driving conditions via thorough image scanning and processing, early hazard forecasting, real-time safety-aware event detection and vehicle maneuverability for collision/accident prevention, among many other computationally intensive tasks. It has been justifiably argued (e.g., [22]) that routing such tasks to upper tiers and, possibly, towards computationally out-powered mega-centers, then back, after completion, to their intended originating nodes/users, incurred excessive bandwidth consumption and so, link congestion, losses and remarkable round trip delays. Such undesirable consequences constituted a dominant subset of reasons behind the poor functionality of cutting-edge services.

Furthermore, it has been continuously observed (e.g., [18]) that, especially during rush hours, edge servers connected to RSUs have been experiencing a crucial over-utilization and often were driven into operational instability manifested in the form of excessive response delays; hence, uselessly wasting precious computational resources in completing tasks, which end up being discarded.

The above-presented challenges have triggered the mobilization of both academic and industrial efforts towards the opportunistic exploitation of the processing capabilities of vehicles nearby RSUs (i.e., mobile vehicles passing by or stationary vehicles in parking lots) for the purpose of cost-minimal, low-latency and efficient task processing and results delivery; a concept that was dubbed as Vehicle-as-a-Resource (VaaSR). Indeed, todays' manufactured vehicles being equipped with powerful server-grade computerized modules and avant-garde wireless communication technologies allow them to process tasks assigned/offloaded to them and timely deliver back their results (e.g., [19], [20], [21], [22], [23], [24], [25], [26]). For instance, the work of [20] aimed at reducing the overall cost of distributing tasks among multiple vehicles with heterogeneous computational capacities. Therein, the formulated multiple-choice Knapsack problem was solved offline with the assumption of a priori network dynamics' knowledge.

In the context of a micro-cloud sub-networking scenario, the authors of [21], aimed at reducing the task completion time through the scheduling and assignment of these tasks to multiple vehicles with random computational resource availability. Therein, vehicles were assumed to arrive at random times to a certain intersection; thus, revealing an inevitable computational capacity variability.

The work of [21] was founded on top of highly restrictive assumptions, like assuming that all arriving vehicles have equal constant computing capacity and considering a per-vehicle single task allocation at a time. The authors of [22] considered a quasi-similar system to that of [21] but with an RSU that was deployed along the side of a straight roadway segment. The optimal results generated by the excessively time consuming resolution of the formulated MILP therein, were quite different from those generated by the proposed
heuristics. The latter produced notably over-pessimistic and, hence, misleading. This is not to mention that the RSU was scheduling task batches. Consequently, it might have been possible that an entire batch could not be scheduled if some of its tasks could not be scheduled to meet all the constraints.

The work of [23] considered a task offloading scenario similar to that in [22] but on a much larger scale involving a certain area covered by a Base Station (BS) and with also the following differences. First, tasks were classified into only two categories, namely, high and low priority tasks. Second, the authors assumed that the BS was only responsible for assigning tasks to vehicles. Third, a pricing scheme was introduced with the objective of providing incentive for vehicles to share their computing resources. Last but not least, owing to the complexity of the problem, a Deep Reinforcement Learning (DRL) framework was developed to optimize the system's task offloading utility and provide insights into the achieved delays.

In [24], a task is divided in multiple subtasks and allocated to multiple vehicles (forming a so called virtual edge) in the vicinity of the offloading node. Hence, every vehicle processes only a subtask. The task scheduling is modeled again as a Knapsack problem. In [26], [27], multiple tasks from different vehicles are processed concurrently on different servers (and vehicles in [27], but each task can only be offloaded to a single server/vehicle.

In [25], similar to our work, users are offloading tasks to the edge but are incentivized to exploit fog servers. However, in reality, the cited work scenario and ours are quite different. First, the authors of [25] consider a two-layer computing environment consisting of an edge service layer and a fog service layer. Architecturally, these layers differ by the location where their computation power is placed. Precisely, for the edge layer, such power is deployed at the local edge while, for the fog service layer, the computing power is offered at different locations between the network edge and the core cloud network. Yet, in both cases, once the computing power is deployed, it remains fixed at the same location and is always present to serve and execute incoming offloaded tasks regardless of the offloading incentive. In contrast, in our work, the edge service layer is assumed to be overloaded with marginal computing capability left for it to serve newly incoming tasks. Also, the fog network is deployed over a mobile vehicular infrastructure, which means that is not fixed and its computing power is highly variable depending on the presence of vehicles which the edge RSU's range and the available capacities of these vehicles and how much capacity each vehicle is willing to share/allocate for the purpose of computing tasks. Moreover, in our work, the fog network itself is completely hidden from the users. As a matter of fact, users always offload their tasks to the in-proximity RSU, which, in turn, resorts to in-range vehicles to exploit them as opportunistic computationally capable nodes able to serve as adjuvants in task computing.

In this paper, different from [25], instead of giving users the incentives to bypass the edge and offload to the fog, it is

the RSU that is attempting to give incentives to fog nodes to collaborate and dedicate some of their capacities to compute the user tasks it holds. Our scenario is totally different as the Stackelberg game we devise consists of providing enough motive for vehicular nodes to maximize their shared computing resources in such a way to offload as many tasks from the RSU to these vehicles and, hence, reduce the overall perceived delay at the RSU through a clear attempt of re-stabilizing its buffer and reducing its load. In addition, opposite to the work of [25], which aimed at reducing end-to-end energy consumption and improving resource utilization over resource-scarce uplinks, our work aims at reducing the overall user-perceived end-to-end delay. This is achieved through re-stabilization of the RSU's queue and reduction of its load by clearing out tasks over R2V downlinks with maximized per-vehicle resource sharing/allocation, which indirectly contributes to the reduction of the RSU's energy utilization and better resource utilization. Further to that, our work goes beyond that of [23] in extending the capacity provisioning problem with the onboard task scheduling constraints. Precisely, two variants of this joint provisioning and scheduling problem are presented herein, one with serial task processing (e.g., [30], [31]) and another with parallel task processing (e.g., [28], [29]).

All in all, with the objective of filling a gap overlooked by the above-surveyed prime selection of existing work among many others, this present work addresses the PA-R2VTO problem in the context of a scenario where RSUs are completely isolated and operating in secluded areas. Deprived from both continuous electrical power supplies as well as connectivity to networking infrastructure, such RSUs are powered with batteries rechargeable through renewable energy sources (e.g., solar power, [32], [33]) and mostly opportunistically exploit passing by vehicles (e.g., [34]) for possible data communication in a Disruption-Tolerant Networking (DTN) substructure. An RSU operating under such limited energy and connectivity circumstances, is surely unable to locally process computationally exhaustive tasks it receives. Instead, it will opportunistically exploit the computational resources shared by vehicles passing by for this purpose. Depending on their rate of arrival, Task Processing Requests (TPRs) may be buffered at the RSU shall they not be timely cleared out. With a subset of these TPRs possibly having higher urgency than others, extending their waiting time as they queue at the RSU's buffer will undesirably lead to prematurely dropping them upon the expiry of their deadlines. Furthermore, the RSU's buffer has a finite amount of space; a major role-playing aspect that exerts the utmost impact on the RSU's jointly crucial Quality-of-Service (QoS) performance indicators (i.e., TPR blocking, system's response time (SRT) and deadline expiry). This is especially true since these parameters concurrently account for multiple dynamic and stochastic requirements (i.e., vehicular traffic, vehicular computing resource availability and task deadlines), the non-satisfaction of at least one of which, leads to further extending a TPR's retention, possible
buffer exhaustion and, thus, deadline expiry, drop of newly
incoming requests and increased SRT; all following in a
likely domino effect. To the best of our knowledge, all
of the above elaborated aspects have not yet been given
adequate attention in the literature. Inspired by this fact,
the main objective of this present work is to develop a
two-level game theoretical resource management framework
that accounts for traffic load, resource and priority-aware
R2V task offloading with the objective of quantifying and
improving the aforementioned user QoS metrics; hence
filling up an important literature gap. To this end, this paper's
novel contributions are presented next.

C. NOVEL CONTRIBUTIONS

This paper aims at presenting novel insights into the game
theoretical modeling and performance analysis of R2V task
offloading in Vehicular Fog Networks (VFNs). Nonetheless,
it is worthwhile noting that the presented game-theoretical
framework herein is highly generic and, thus, after adequate
fine tuning, can be easily utilized to capture the dynamics and
evaluate the performance of any next generation carrier grade
Mobile-Edge-Computing-enhanced wireless sub-network. To
this end, without any further ado, the novel contributions of
the work presented herein are listed as follows:

1) The development of a two-level resource management framework coined PA-R2VTO for VFNs. Under PA-R2VTO, an RSU buffering deadline-constrained and computationally intensive tasks is granted the luxury of opportunistically exploiting the idle computational resources of vehicles navigating through their respective communication ranges; this having the objective of reducing the average SRT as well as the long-term TPR deadline expiry and blocking probabilities. Precisely, at a first level, the RSU steers a Stackelberg game with the aim of tapping into the computing resources of in-range vehicles. To this end, vehicles may partially or fully contribute their available computing resources/capacities to the RSU in exchange of some rewards (e.g., reduced toll fees, priority lane access, energy refueling credits/discounts, cryptocurrency incentives, improved traffic flow, early access to new applications, etc). Here, by offering appealing-enough rewards, the RSU seeks to incentivize vehicles to maximize their offered capacity. In turn, vehicles act as followers and try to strike a balance between lost capacity and resulting rewards. Once this is done, the RSU, at the second level, dispatches tasks (if any) to be computed by their designated vehicles chosen based on: i) The vehicles' dedicated computing resources (i.e., the per-vehicle computing capacity), ii) the per-vehicle sojourn time within the RSU's coverage range, iii) the tasks' sizes and deadlines. Finally, two computational modes are considered, namely: i) vehicles process their assigned tasks serially (i.e., task assignment is modeled as a Multiple Knapsack problem, [41]), and, ii) vehicles process multiple tasks in parallel (i.e., task assignment is modeled as a non-cooperative congestion game with player specific payoff functions [43]).

2) The establishment of a thorough simulation and numerical analysis framework to, first, assert the validity and accuracy of the proposed model and, second, evaluate the performance of the newly proposed PA-R2VTO in terms of the above-mentioned QoS metrics as well as, third, compare PA-R2VTO's performance to that of other existing counterparts (e.g., in [46]) in order to gauge its merits.

D. PAPER’S ORGANIZATION

The remaining of this paper is organized as follows.
Section II lays out an elaborate description of the considered
RSU-to-Vehicle task offloading scenario, followed by a
theoretical framework pertaining to the proposed PA-R2VTO
scheme, which is presented in Section III. Numerical
analyses and simulations are conducted in Section IV and,
finally, concluding remarks are presented in Section V.

II. SYSTEM MODEL

Consider the vehicular fog sub-network illustrated in Figure 1. This figure shows a unidirectional uninterrupted road segment that could either represent a rural roadway or a large inter-city highway. Along this highway are deployed a certain number of RoadSide Units (RSUs). In this context, knowing that the setup and maintenance of networking and power infrastructure is highly costly, due efforts have been recently invested towards the opportunistic exploitation of the processing capabilities of vehicles navigating in proximity of the RSUs for the purpose of cost-minimal, low-latency and efficient task processing and results delivery.

We introduce a framework that operates in two levels
in order to solve the R2V task offloading problem and
shown in Figure 2. In the first level, the vehicles allocate
to the RSU a part of their capacity for the offloaded tasks
in exchange of some gratification bestowed by the RSU.
This level is portrayed as one leader multiple followers
Stackelberg game. In the second level, the RSU assigns
to the computational tasks to the participating vehicles
according to various parameters, such as the task size,
task delay, vehicles allocated capacity and vehicles sojourn
time in the RSU coverage area. Two processing models are
considered for task computation, serial processing modeled
as a knapsack problem and parallel processing modeled as
a non-cooperative congestion game.

Accordingly, we consider a set of vehicles $v_i$ ($i \in I = \{1, \dots, I\}$), dotted with a maximum capacity $C_i$ and a sojourn time $s_i$ within the coverage zone of the target RSU. Incoming tasks at the RSU are such that a task $T_j$ ($j \in J = \{1, \dots, J\}$) has a size $V_j$ and is assorted with a deadline $d_j$.

At this level, it is worthwhile noting that in the context
of our scenario, any existing classical multi-point-to-point
and point-to-multi-point protocols can respectively be used
to govern the R2V and V2R (i.e., uplink and downlink)
communication taking place between vehicles and the RSU.
This communication aspect has been widely tackled in
the literature and is outside the scope of our present
work. However, to better clarify, the RSU is directly
<figure><img src="image_3.png" /><figcaption>FIGURE 1. RSU-to-vehicle task offloading scenario.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>FIGURE 2. Two-level RSU-to-Vehicle Task Offloading Framework.</figcaption></figure>

communicating with vehicles that are within its range. When executing the game, in-range vehicles shall return to the RSU their share of computing resources using very small messages that are very unlikely to collide and, also, are

very quickly transmitted in almost a negligible amount of time. This is not to mention that TDMA can actually be used to lead to absolutely zero collision. Now, in the reverse direction (i.e., from the RSU to the vehicles), it is the RSU
<table><caption>TABLE 1. Model variables.</caption><thead><tr><td>Variable</td><td>Description</td></tr></thead><tbody><tr><td>v<sub>i</sub></td><td>Vehicle i</td></tr><tr><td>R<sub>i</sub></td><td>Contributed capacity of v<sub>i</sub></td></tr><tr><td>C<sub>i</sub></td><td>Total capacity of v<sub>i</sub></td></tr><tr><td>g</td><td>Total gratification given by the RSU</td></tr><tr><td>g<sub>i</sub></td><td>Gratification received by v<sub>i</sub></td></tr><tr><td>T<sub>j</sub></td><td>Task j</td></tr><tr><td>V<sub>j</sub></td><td>Size of T<sub>j</sub></td></tr><tr><td>g</td><td>Total gratification given by the RSU</td></tr><tr><td>g<sub>max</sub></td><td>Maximum gratification given by the RSU</td></tr><tr><td>g<sub>i</sub></td><td>Gratification received by v<sub>i</sub></td></tr></tbody></table>

that is transmitting tasks to each and every vehicle separately. Hence, the RSU here is regarded as the sole centralized arbitrator of the communication-related resources with no interference or collision among the transmissions performed to each and every one of the vehicles. Finally, with regard to user-to-RSU task transmissions (i.e., user wireless access to the RSU), this can take place on a totally different frequency that is fully orthogonal to that used for R2V and V2R.

### III. LEVEL 1: THE STACKELBERG GAME

We aim to model the interaction between the vehicles' provisioned capacities to the RSU and the RSU's offered reward for the allotted capacity. The RSU seeks to motivate passing by vehicles to allow part of their capacity to be used for processing tasks that the RSU can not handle in exchange of some gratification. To that aim, we propose a two-stage Stackelberg game (refer to [39]), according to which the RSU (the leader) derives the optimal gratification to bestow to each participating vehicle, while at the same time, the vehicles (the followers) autonomously determine the optimal capacity that they intend to yield to the RSU.

Throughout the first stage, the RSU announces the gratification $g$ for harvested resources, followed by the second stage where each vehicle determines its offered share of resources to strike a balance between a satisfactory gratification and a tolerable amount of renounced resources. Therefore, the RSU is the leader while the vehicles are naturally the followers. Note that the second stage is a non-cooperative game played for a given instance of gratification announced by the RSU.

Each vehicle $v_i$ within the RSU's range chooses to contribute a part, $R_i$ (or all) of its capacity (i.e., $0 < R_i \le C_i$) to that RSU. The latter rewards $v_i$ with a gratification, $g_i$, proportional to its allocated resources. That is:

$$g_i = g \cdot \frac{R_i C_i^{-1}}{R_i C_i^{-1} + \sum_{k \neq i} R_k C_k^{-1}} \quad (1)$$

where $0 < g \le g_{max}$ is the total reward that the RSU is capable of provisioning to participating vehicles.

Accordingly, without loss of generality (w.l.o.g.), the utility function pertaining to any target vehicle, say vehicle $v_i$ is:

$$U_i = g_i - \alpha R_i \quad (2)$$

where $\alpha$ is a normalizing factor. Hence, $v_i$ will strive to increase its gratification while minding the amount of capacity offered to the RSU.

#### A. STAGE 1: THE LEADER STAGE

Here, the RSU's aim is to strike a balance between harvested resources and incurred gratification paid for the participating vehicles. Thus, the RSU's utility function is formulated as:

$$U_{RSU} = \sum_{i \in \mathcal{I}} R_i - \beta g, \quad (3)$$

where $\beta$ is a normalizing factor. As such, the leader's optimization problem is formulated as:

$$\begin{array}{ll} \max_{g} & U_{RSU} \\ \text{s.t.} & 0 \le g \le g_{max} \end{array} \quad (4)$$

#### B. STAGE 2: THE FOLLOWERS STAGE

Here, recall the utility function defined in (2). Each vehicle tries to maximize its utility function; hence, the follower's optimization problem is given by:

$$\begin{array}{ll} \max_{R_i} & U_i \\ \text{s.t.} & 0 \le R_i \le C_i \end{array} \quad (5)$$

**Proposition 1:** The utility function $U_i$ is strictly concave.

**Proof:** The first derivative of the utility function is:

$$\frac{\partial U_i}{\partial R_i} = \frac{g}{C_i} \cdot \frac{\sum_{k \neq i} R_k C_k^{-1}}{(R_i C_i^{-1} + \sum_{k \neq i} R_k C_k^{-1})^2} - \alpha \quad (6)$$

The second derivative of the utility function is:

$$\frac{\partial^2 U_i}{\partial R_i^2} = \frac{g}{C_i^2} \cdot \frac{-2 \sum_{j \neq i} R_j C_j^{-1}}{(R_i C_i^{-1} + \sum_{j \neq i} R_j C_j^{-1})^3} \quad (7)$$

Clearly, from (7) the second derivative is strictly negative; meaning that the utility function is strictly concave. ■

Since the optimization problem (5) is convex (concave utility and linear constraints), the Karush-Kuhn-Tucker (KKT) conditions allow for determining the optimum for each vehicle, $v_i$. That is:

$$\frac{\partial U_i}{\partial R_i} - \gamma = \frac{g}{C_i} \cdot \frac{\sum_{k \neq i} R_k C_k^{-1}}{(R_i C_i^{-1} + \sum_{k \neq i} R_k C_k^{-1})^2} - \alpha - \gamma = 0 \quad (8)$$

$$\gamma \cdot (R_i - C_i) = 0 \quad (9)$$

$$R_i \le C_i \quad (10)$$
Whether $\gamma$ is null or not, it follows from (8), (9), (10) that:

$$R_i = \min \left( \sqrt{\frac{gC_i}{\alpha} \sum_{k \neq i} \frac{R_k}{C_k}} - \sum_{k \neq i} \frac{R_k}{C_k}, C_i \right) \quad (11)$$

### C. STACKELBERG EQUILIBRIUM

In a Stackelberg Game, the Stackelberg Equilibrium (SE) is always sought. This is a Nash Equilibrium (NE) between the leader and the followers. Hence, when the SE is reached, no player has profit in deviating unilaterally. Accordingly, an SE is an equilibrium point ($R_i^*$, $g^*$) defined as follows:

$$U_{RSU}(R_i^*, g^*) \geq U_{RSU}(R_i^*, g), \forall g \in [0, g_{max}] \quad (12)$$

$$U_i(R_i^*, g^*) \geq U_i(R_i, g^*), \forall R_i \in [0, C_i] \quad (13)$$

The SE of the devised Stackelberg game is derived by using the backward induction method. Consequently, the followers' best responses can be obtained with the fixed value of $g$ given by the leader, and then the optimal strategy of the leader can be achieved according to the followers' best responses. Accordingly, first solve for the followers' optimization problem in (5). Then, by using the obtained solution, solve the leader's optimization problem in (4). For that aim, first derive the optimal capacity share ($R_i^*$) relinquished by any vehicle $i \in \mathcal{I}$ in Stage 1, obtained from equation (11) and inject it in equation (3) to obtain the optimal solution of Stage 1 (i.e., $g^*$).

### D. OPTIMAL SOLUTION FOR STAGE 1

As previously stated, substitute (11) in equation (3). Accordingly, the following RSU utility function is obtained:

$$U_{RSU} = \min \left( \sqrt{\frac{gC_i}{\alpha} \sum_{k \neq i} \frac{R_k}{C_k}} - \sum_{k \neq i} \frac{R_k}{C_k}, C_i \right) - \beta \cdot g \quad (14)$$

**Proposition 2:** The utility function is strictly concave.

**Proof:** The first derivative of the RSU's utility function is:

$$\frac{\partial U_{RSU}}{\partial g} = \frac{1}{2\sqrt{g}} \sum_{i \in \mathcal{I}'} \sqrt{\frac{C_i}{\alpha} \sum_{k \neq i} \frac{R_k}{C_k}} - \beta \quad (15)$$

where $\mathcal{I}' \subset \mathcal{I}$ is the set of vehicles $v_i$ for which $R_i < C_i$.

The second derivative of the RSU's utility function is:

$$\frac{\partial^2 U_{RSU}}{\partial g^2} = \frac{-1}{4} g^{-3/2} \sum_{i \in \mathcal{I}'} \sqrt{\frac{C_i}{\alpha} \sum_{k \neq i} \frac{R_k}{C_k}} \quad (16)$$

Equation (16) indicates that the second derivative is strictly negative; meaning that $U_{RSU}$ is strictly concave. ■

In that case, as (4) is a convex optimization problem, the KKT conditions enable determining a global optimum which is the Stackelberg Equilibrium. The KKT conditions are:

$$\frac{\partial U_{RSU}}{\partial g} - \theta = \frac{1}{2\sqrt{g}} \sum_{i \in \mathcal{I}'} \sqrt{\frac{C_i}{\alpha} \sum_{k \neq i} \frac{R_k}{C_k}} - \beta - \theta = 0 \quad (17)$$

### Algorithm 1 Stackelberg Equilibrium Algorithm

Initialize $g$ and $R_i$, $\forall i \in \mathcal{I}$

repeat

repeat

The vehicles calculate $U_i$ based on (11) with the set value of $g$

until Convergence of $R_i$;

The RSU updates $g$ based on (20)

until Convergence of $g$;

$$\theta \cdot (g - g_{max}) = 0 \quad (18)$$

$$0 < g \leq g_{max} \quad (19)$$

From (17), (18), (19)), $g$ is obtained as:

$$g = \min \left[ \frac{1}{4\beta^2} \cdot \left( \sum_{i \in \mathcal{I}'} \sqrt{\frac{C_i}{\alpha} \sum_{k \neq i} \frac{R_k}{C_k}} \right)^2, g_{max} \right] \quad (20)$$

### E. SE ALGORITHM

The Stackelberg game is formed through a two-layer iteration. In the inner iteration, the vehicles compete with each other, and the amount of capacity they hand over to the RSU is updated iteratively based on the RSU gratification, as shown in (5). In the outer iteration, the RSU updates its gratification based on the resources gained from the vehicles, as shown in (4). Algorithm 1 is used to obtain the SE.

First, initialize the weights $g$ and $R_i$ ($i \in \mathcal{I}$) to random values obeying the constraints in $W$. Then, repeat the costs/weights computation based on the leader and follower optimization problems until convergence (i.e., constant costs and weights).

**Proposition 3:** Algorithm 1 converges to a unique fixed point which is the unique SE.

**Proof:** Generally, the SE for the proposed Stackelberg game can be obtained by finding the NE of its subgame. The best response of the unique leader is obtained straightforwardly by solving the optimization problem in (4), which has a unique optimum. At the followers' side, the best response can be achieved by solving the optimization problem in (5). Therefore, to prove this theorem, it is only needed to prove that a unique NE exists for the subgame at the followers' side. Since the utility function of any vehicle $v_i$ is strictly concave and continuous in $R_i$ and the set of strategies $[0, C_i]$ is convex and compact, the NE exists and is unique, [40]. ■

### IV. LEVEL 2: VEHICLE SELECTION AND PROCESSING

Once the available capacities are known to the RSU, the system delves in its second level where tasks get assigned to the various vehicles for computation. The two computational modes mentioned in Section I-C are detailed hereafter.

#### A. VEHICLE SELECTION AND SERIAL PROCESSING

In this model, each vehicle is considered as a knapsack and each task is an item whose profit is the opposite of
its deadline $d_j, j \in \mathcal{J}$ and weight is its processing time (that depends on its size and the chosen vehicle/knapsack). The goal of the Multiple Knapsack Problem (MKP) is to select disjoint subsets of items so that the total profit of the selected items is a maximum, and each subset is assigned to a knapsack whose capacity $R_i, i \in \mathcal{I}$ is no less than the total weight of the items in the subset. Further, let $x_{ij}$ be a binary variable that takes the value one if item/task $j$ is assigned to knapsack/vehicle $i$. Hence, the MKP can be modeled as:

$$ 
\begin{aligned}
\min_{x_{ij}} & \sum_{i \in \mathcal{I}} \sum_{i \in \mathcal{J}} d_j x_{ij} \\
\text{s.t.} & \sum_{j \in \mathcal{J}} \frac{V_j}{R_i} \cdot x_{ij} \leq s_i, \forall i \in \mathcal{I} \\
& \sum_{i \in \mathcal{I}} x_{ij} \leq 1, \forall j \in \mathcal{J}
\end{aligned} 
\quad (21) $$

The value of an item decreases with its deadline as there is need to service the items with the lowest deadline. The latter incentive explains the objective function of the MKP problem in (21). The first constraint ensures that assigned tasks are serviced before the selected vehicle $i$ leaves the RSU vicinity and hence in a time lower than the vehicle sojourn time $s_i$. The second constraint ensures a task is assigned to a single vehicle as the variables are binary.

Note that (21) does not account for the transmission time of task $j$'s results by vehicle $i$, say $\tau_{i,j}$, back to the RSU since, according to [47], [48], this time is negligible compared to tasks queueing and computing times. Yet, (21) is easily amendable to account for it by simply adding $\tau_{i,j}$ to the left-hand-side of this constraint.

The MKP in (21) is NP-hard in the strong sense. The method proposed [42] with improved Branch-and-Bound algorithms comes to the rescue in resolving that MKP using the dominance criteria and symmetry breaking strategies. To avoid redundancy, the reader is referred to [42] for all the details pertaining to their proposed resolution technique.

Now, the time has come to evaluate the per-task waiting time under the serial task processing scheme. Obviously here, considering an arbitrary vehicle $v_i$ a task queue is forming at that vehicle with tasks being buffered very similarly to a first come first serve service policy. For simplicity of the explanation, let's assume that the set of $N$ tasks dispatched for processing at $v_i$ is $\mathcal{T}_i = \{T_r, T_w, T_x, T_y, T_j, T_z, \dots\}$ where $r, w, x, y, j, z, \dots$, are the ascending order integer indices of these tasks all in $[1; J]$. When serial processing is adopted, each task is processed at full capacity $R_i$ dedicated by $v_i$ for processing offloaded tasks. Therefore, the processing time, $\rho_k$, of any arbitrary task $T_k$ is equivalent to the ratio of its size, $V_k$, to $v_i$'s dedicated processing capacity $R_i$; that is, $\rho_{ik} = V_k R_i^{-1}$. Once task $T_k$ is complete, its results are returned to the RSU and then, immediately, $v_i$ starts processing the next subsequent task, $T_{k+1}$. Regardless of its position in $v_i$'s queue, $T_j$ must wait for $v_i$ to process all of the $j-1$ tasks queueing ahead of it until it becomes due for

processing. So, the overall waiting time, $W_{j,i}^S$, of task $T_j$ at $v_i$ (i.e., queueing at $v_i$ plus processing time) is:

$$ W_{ij}^S = \sum_{k=1, k \leq j}^{J} x_{ik} \rho_{ik} = \sum_{k=1, k \leq j}^{J} x_{ik} \cdot V_k R_i^{-1}, \forall i \in \mathcal{I} \quad (22) $$

## B. VEHICLE SELECTION AND PARALLEL PROCESSING

In this model, tasks are considered as self-interested players whose strategies are the set of vehicles. Accordingly, w.l.o.g. each arbitrary task, $T_j$ ($j \in \mathcal{J}$), seeks to select the best vehicle that reduces its cost function, which is given by:

$$ C_j(x_j, x_{-j}) = \sum_{i \in \mathcal{I}} x_{ij} \left( \frac{1}{d_j} \cdot \frac{V_j}{R_i} \sum_{j \in \mathcal{J}} x_{ij} - \gamma \cdot s_i \right) \quad (23) $$

Furthermore, $C_j^i(x_j, x_{-j}) = \frac{1}{d_j} \cdot \frac{V_j}{R_i} \sum_{j \in \mathcal{J}} x_{ij} - \gamma \cdot s_i$ denotes the cost of task $T_j$ for selecting vehicle $v_i$.

The cost function is devised in a way to account for the processing time endured by task $T_j$ when processed by vehicle $v_i$: $\sum_{j \in \mathcal{J}} \frac{V_j}{R_i} x_{ij}$. As parallel processing is considered, the vehicle's capacity is equally shared among tasks that selected that same vehicle (through the congestion factor $\sum_{j \in \mathcal{J}} x_{ij}$), making the game a congestion type game. The processing time is normalized by the task deadline that serves as a reference for the task strategy selection. Finally, $\gamma$ is a normalization factor that multiplies the selected vehicle sojourn time. The goal is to favor the vehicle that resides the longest within the RSU's coverage range.

The formulation of the Vehicle Selection non-cooperative game $G = (\mathcal{J}, \mathcal{I}, C)$ can be described as follows:

* A set of players $\mathcal{J} = (1, \dots, J)$, which is the set of tasks buffered by the RSU.

* A set of strategies for any player $T_j$ is $S_j = \mathcal{I} = (1, \dots, I)$, which is the set of vehicles.

* The space of pure strategies $S$ formed by the Cartesian product of each set of pure strategies $S = S_1 \times \dots \times S_J$.

* A set of cost functions $\{C_1, C_2, \dots, C_J\}$ that quantify the players' preferences over the possible outcomes of the game. Outcomes are determined by the particular action $x_j$ chosen by task $j$ and actions chosen by all other tasks $x_{-j}$. Action $x_j$ corresponds to selecting a particular vehicle, hence it is a vector such that $x_j = (x_{ij}, i = 1, \dots, I)$ where the binary variable $x_{ij} = 1$ if task $j$ selects vehicle $i$. Otherwise, $x_{ij} = 0$. Thus, Task $j$'s cost is $C_j(x_j, x_{-j})$ as in (23).

### 1) NASH EQUILIBRIUM

In a non-cooperative game, an efficient solution is reached when all players adhere to an NE being a profile of strategies, in which no player will take advantage by deviating its strategy unilaterally. Hence, it is a strategy profile where each player's strategy appears as an optimal response to the other players' strategies:

$$ C_j(x_j, x_{-j}) \leq C_j(x'_j, x_{-j}), \forall j \in \mathcal{J}, \forall x'_j \in S_j \quad (24) $$
The presented game G herein is a finite game which is guaranteed to possess a mixed NE but no pure NEs. The former leads to a continuous change of strategy according to a probability distribution which can be cumbersome. Nonetheless, G has specific properties which prove the existence of a pure NE as explained in Section IV-B.2 below.

## 2) GAME PROPERTIES

As per [44], it is necessary and sufficient that, for every strategy and for every pair of players, the corresponding cost functions are affine transformations of each other in order to guarantee a pure NE. In other words, the cost functions are of the form $C_j^i(x) = a_j^i \cdot x + b$ where $x = \sum_{j \in \mathcal{J}} x_{ij}$ is the congestion factor (a.k.a., the number of players that chose the same strategy $i$), $b \in \mathbb{R}$ an arbitrary constant and $a_j^i$ a positive constant such that $a_j^i/a_j^i$ is independent of the strategy $i$ for any two players $j$ and $j'$. It can be easily asserted through (23) that these properties are verified; particularly, $a_j^i/a_j^i = \frac{V_j}{d_j \cdot R_i} \cdot \frac{d_j^i \cdot R_i}{V_j} = \frac{V_j d_j^i}{V_j d_j}$. Hence, a Pure NE exists for the vehicle selection with parallel computation game.

Following the resolution of the above-formulated parallel task processing model, it is now of interest to compute the per-task waiting time. For this purpose, w.l.o.g., considering an arbitrary task $T_j$, the computation of its waiting time under parallel processing is explained as follows. Under parallel processing, the capacity of vehicle $v_i$, namely $R_i$ is fairly shared among all tasks dispatched to it, among which is task $T_j$. Let $\mathcal{T}_i = \{T_r, T_w, \dots, T_j, \dots\}$ be a subset of tasks in set $\mathcal{J}$, which are dispatched to $v_i$ where $\mathcal{N}_i = \{r, w, j, \dots\}$ is the set of these tasks' distinct numerical indices. Hence, the allocated per-task capacity shall be $R_t = R_i(\sum_{k \in \mathcal{N}_i} x_{ik})^{-1}$. Thus, the waiting time pertaining to an arbitrary task $T_j$ computed by vehicle $v_i$ is nothing else but its processing time equivalent to the ratio of $T_j$'s size, $V_j$, to $v_i$'s fractional fair capacity share, $R_t$; that is:

$$W_{ij}^P = V_j R_t^{-1} = V_j \cdot R_i^{-1} \sum_{\forall k \in \mathcal{N}_i} x_{ik}, \forall i \in \mathcal{I} \quad (25)$$

## C. FUNDAMENTAL QOS PERFORMANCE METRICS

The fundamental QoS performance indicators are:

* The system-wide average task waiting time: being the average waiting time experienced by all dispatched tasks to all vehicles. It is computed as:

$$\overline{W} = \sum_{\forall i \in \mathcal{I}} \sum_{\forall j \in \mathcal{J}} x_{ij} W_{ij}^{\chi} \quad (26)$$

where $\chi = \{S, P\}$ depending on the adopted processing scheme (i.e., whether serial or parallel processing). Obviously, $\overline{W}$ manifests itself as the average of the waiting times of tasks as expressed in equations (22) and (25) respectively.

* The task blocking probability: defined as the ratio of, $n_r$, being the number of retained tasks (i.e., not dispatched by the RSU to any vehicle given that none of the vehicles

is capable of processing it) to, $n_t$, being the total number of tasks buffered by the RSU. Mathematically:

$$P_b = n_r n_t^{-1} \quad (27)$$

* The deadline mismatch probability: defined as the ratio of the number of tasks $n_{dm}$ that were dispatched for processing but failed to be processed by their deadlines, to $n_t$:

$$P_{dm} = n_{dm} n_t^{-1} \quad (28)$$

## V. COMPLEXITY ANALYSIS

We analyse the complexity of our devised framework. For the first level, after the convergence of the non-cooperative game among vehicles, the vehicles' optimal allocated capacity are sent back to the RSU and the next iteration of the Stackelberg game is established. This procedure is repeated until convergence of the overall Stackelberg game and reached at the Stackelberg equilibrium point $(R^*, g^*)$ where neither the RSU nor the vehicles have incentive to deviate. As both embedded problems (the followers stage and the leader stage) correspond to convex optimization problems with closed form formulas, they have $O(1)$ complexity. We denote by $x$ the number of iterations for the non-cooperative game among followers and $y$ the number of iterations of the Stackelberg game. Hence, the complexity of the first level is in $O(I \cdot x \cdot y)$, where $I$ is the number of vehicles as the non-cooperative game is played out through best response dynamics where vehicles play in turn.

As for the devised framework second level, the sequential processing is modeled as a multiple knapsack problem that is NP-hard. We resorted to branch-and-bound algorithm which is known to be extremely difficult to analyse. We can take the full-enumeration bound, which is simple to calculate is also extremely loose. Finally, for the parallel processing model, the Nash Equilibrium of the corresponding congestion game is reached using best response dynamics. We denote by $z$ the number of iterations till convergence and as the algorithm is applied in an iterative fashion, the complexity is in $O(z \cdot I)$.

Also, as per our vehicular traffic model, the number of vehicles within the range of the RSU is limited and does not grow infinitely.

## VI. SIMULATIONS AND NUMERICAL ANALYSIS

### A. SIMULATION SETUP

A custom-built PYTHON-based simulation environment was developed using standard libraries to code basic functions allowing for evaluating PA-R2VTO's performance and compare it to the performances of existing benchmarks (e.g., [46]). The simulator was executed on a machine with a Core i7 CPU at 1.8 GHz, 8GB RAM.

Now, following the guidelines of [45], the RSU's coverage range spans a road segment of length $L$ experiencing free-flow traffic conditions whereby vehicle arrivals follow a Poisson process with parameters $\lambda_v$ veh./s. The per-vehicle speeds, $s_i$ ($i \in \mathcal{I}$), constitute a sequence of independent and identically distributed random variables drawn from a
<table><caption>TABLE 2. Simulation parameters.</caption><thead><tr><td>Parameter</td><td>Description</td><td>Value</td></tr></thead><tbody><tr><td>L</td><td>Road segment length</td><td>200 m</td></tr><tr><td>λ<sub>v</sub></td><td>Vehicle arrival rate</td><td>[0.1; 0.277] veh./s</td></tr><tr><td>S<sub>min</sub></td><td>Minimum vehicle speed</td><td>10 m/s</td></tr><tr><td>S<sub>max</sub></td><td>Maximum vehicle speed</td><td>50 m/s</td></tr><tr><td>f<sub>min</sub></td><td>Minimum clock frequency</td><td>500 MHz</td></tr><tr><td>f<sub>max</sub></td><td>Maximum clock frequency</td><td>4 GHz</td></tr><tr><td>Σ<sub>min</sub></td><td>Minimum cycle/instruction</td><td>1</td></tr><tr><td>Σ<sub>max</sub></td><td>Maximum cycle/instruction</td><td>5</td></tr><tr><td>λ<sub>t</sub></td><td>Task arrival rate</td><td>0.75 task/s</td></tr><tr><td>V<sub>t</sub></td><td>Mean task size</td><td>3 × 10<sup>6</sup> instructions</td></tr><tr><td>d<sub>m</sub></td><td>Mean task deadline</td><td>[0.5; 10000] ms</td></tr><tr><td>g<sub>max</sub></td><td>RSU maximum gratification</td><td>[1; 1000]</td></tr><tr><td>α</td><td>Normalizing factor</td><td>10<sup>-5</sup></td></tr><tr><td>β</td><td>Normalizing factor</td><td>10<sup>6</sup></td></tr><tr><td>γ</td><td>Normalizing factor</td><td>1</td></tr></tbody></table>

truncated Normal distribution, which, in turn, is defined over a range [$S_{min}$; $S_{max}$] m/s with a mean $\mu_s$ and a standard deviation $\sigma_s$. Under free-flow traffic conditions, a vehicle's speed is assumed to remain constant during the entire navigation period of the vehicle along the considered road (i.e., RSU's range). Reference [45] along with Traffic Engineering references therein dictate that for each value of $\lambda_v$ corresponds a value of $\mu_s$ and $\sigma_s$. These values are borrowed and used herein to compute the per-vehicle speed (and eventually the vehicle's sojourn times) in the context of vehicular mobility scenarios differentiated by a range of $\lambda_v$ values.

Moreover, each vehicle, $v_i$, also has a processing capacity $C_i = f_i \Sigma_i^{-1}$ ($\forall i \in \mathcal{I}$) instructions/second, where $f_i$ is $v_i$'s clock frequency uniformly chosen from the range [$f_{min}$; $f_{max}$] and $\Sigma_i$ is Cycle Per Instruction, which is also a random integer drawn from the range [$\Sigma_{min}$; $\Sigma_{max}$].

Next, regarding the tasks, they are generated following a Poisson process with a mean $\lambda_t$ task/s. Each task, $T_j$ ($j \in \mathcal{J}$), has a size $V_j$ that is geometrically distributed with a mean of $V_t$. Additionally, $T_j$ also has a deadline, $d_j$, that is drawn from an exponential distribution with a mean $d_m$. These simulation parameters and their values together with other model-related parameters are presented in Table 2.

## B. STUDIED ALGORITHMS AND BENCHMARKS

Thorough simulations are conducted to evaluate the performance of the proposed schemes in terms of the earlier mentioned performance metrics (i.e., $\bar{W}$, $P_b$ and $P_{dm}$). The results pertaining to the proposed PA-R2VTO scheme herein with Serial and Parallel processing at the vehicles (hereafter labelled Serial and Parallel respectively) are obtained through the use of the Multiple-choice Knapsack Problem resolution heuristics (i.e., [42]) and the Best Response Algorithm (i.e., [43]). These results are benchmarked against two

### Algorithm 2 EDF Assignment Heuristic Algorithm

Sort tasks in ascending order of their deadlines

Sort vehicles in ascending order of their sojourn time

repeat

In order, each vehicle, will take a number of tasks $N_T$ based on (29) and (30)

until All vehicles' capacity is full;

variants of the Earliest Deadline First (EDF) R2V task offloading scheme, namely:

* EDF task dispatching by the RSU with Serial (EDF-S) task processing by vehicles, which was developed in [46].

* EDF task dispatching by the RSU with Parallel (EDF-P) task processing by vehicles; an extension to EDF-S developed herein.

The EDF-based algorithm is presented in Algorithm 2 where, first, tasks arriving to the RSU's buffer are sorted in ascending order of their deadlines; that is, tasks with the shorter deadlines are placed first followed by those with larger deadlines. Vehicles navigating through the RSU's coverage range are also sorted in ascending order of their sojourn times; that is, vehicles with the shortest residual residence time within the RSU's range are placed first followed by those with longer sojourn times. Subsequently, the RSU will assign to each in-range vehicle $v_i$ ($i \in \mathcal{I}$), in order, a number of tasks that $v_i$ can complete and return the tasks' results back to the RSU both before it leaves the RSU's range. To this end, under serial processing, the mean number of tasks assigned to vehicle $v_i$, $N_{T,i}^S$, is:

$$N_{T,i}^S = \frac{R_i \cdot s_i}{V_t} \qquad (29)$$

where $R_i$ is $v_i$'s dedicated capacity for task processing and $s_i$ is $v_i$'s sojourn time within the RSU's range; hence, $R_i \cdot s_i$ represents the total number of instructions that $v_i$ is capable of successfully completing before leaving the RSU's range.

Similarly, for parallel processing, with the processing time equally divided among served tasks, the mean number of tasks dispatched by the RSU to vehicle $v_i$, $N_{T,i}^P$, is:

$$N_{T,i}^P = \frac{R_i \times s_i}{V_t \cdot N_{T,i}^P} \implies N_{T,i}^P = \sqrt{\frac{R_i \times s_i}{V_t}} \qquad (30)$$

## C. PERFORMANCE EVALUATION

At this level, it is important to mention that, to ensure at least 95% confidence interval (dotted curves in all result figures), reported results herein are averaged out over 1000 runs of each simulation scenario. The Stackelberg game reached its SE within only $y = 2$ iterations, similar to the inner loop corresponding to the non-cooperative game, which converges in no more than $x = 2$ iterations. The congestion game converged within $z = 3$ iterations. At equilibrium, all
<figure><img src="image_5.png" /><figcaption>FIGURE 3. Level 1: Percentage of assigned capacity vs. RSU gratification.</figcaption></figure>

vehicles' dedicated processing capacities for RSU-dispatched tasks are equal and depend only on the RSU's offered gratification $g$, which converges to $g_{max}$.

Figure 3 plots the per-vehicle contributed percentage computing capacity (i.e., $R_i C_i^{-1} \times 100$) as a function of the RSU's maximum gratification $g_{max}$ for three vehicular traffic scenarios where the vehicular arrival rate was calibrated in such a way to have a mean number of 10, 20 and 30 vehicles within the RSU's range. The figure indicates that vehicles increase their contributed capacity proportionally to the RSU's gratification. Truly, the more the RSU's rewards are appealing, the more vehicles are willing to contribute additional computing capacity up until they contribute their full capacities at a certain maximum gratification offered by the RSU. Clearly, vehicles cannot contribute more than their 100% computing power; hence, the constantly horizontal trend beyond the $g_{max}$ corresponding to each scenario. One very interesting insight that can be provided here is that vehicles are aware of the worth of their computing resources. This is why, when the number of in-range vehicles is small, computing resources are more and more scarce and so vehicles will demand much higher rewards to renounce them to the RSU rather than keeping such resources for themselves. This explains the gaps between the red, blue and green curves where a certain per-vehicle capacity threshold is shared at a much higher gratification when the number of vehicles is low than it is shared under denser vehicular traffic. It is quite interesting to see this quasi-business-oriented demand-supply resource pricing behavior here.

Figure 4 plots $\bar{W}$ as a function of $\lambda_v$ for both of the PA-R2VTO and EDF schemes with serial and parallel processing modes. The mean task size here is $V_t$. Notice that whenever the vehicular traffic intensity is very low (i.e., $\lambda_v < 0.1$), the number of vehicles within the RSU's range is extremely low; almost zero vehicles in range on average. Whenever a vehicle $v_i$ enters the RSU's range, the RSU operating under EDF-S, will keep on serially clearing out from its queue the tasks sorted in ascending order of their deadlines until $N_{T,i}^S$ or, otherwise, the queue becomes completely empty. However,

<figure><img src="image_6.png" /><figcaption>FIGURE 4. Level 2: $\bar{W}$ v.s. $\lambda_v$.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>FIGURE 5. Level 2: $P_{dm}$ v.s. $\lambda_v$.</figcaption></figure>

under PA-R2VTO, the RSU will only clear out a subset of the ordered tasks (not necessarily as they are sorted) from the queue if the in-range vehicle is able to process and complete these tasks before they expire and before the vehicle leaves the RSU's range. Hence, PA-R2VTO is obviously more selective than EDF-S and will lead, not only to a higher queue size, which, by Little's Theorem (refer to [?]), clearly leads to a higher waiting time, but it will also lead to a higher mismatch probability $P_{dm}$ as illustrated in Figure 5 (plotting $P_{dm}$ versus $\lambda_v$). This is especially the case since some tasks with shorter deadlines may be skipped by PA-R2VTO only to dispatch other higher-deadline tasks that may better fit the vehicle's capacity and avoid capacity underutilization. In contrast, whenever $\lambda_v$ increases, the number of in-range vehicles increases and, therefore, the likelihood that PA-R2VTO finds suitable vehicles for processing tasks will increase. Indeed, as $\lambda_v \ge 0.1$, PA-R2VTO appears to be clearing out tasks from the RSU's queue equally rapidly as EDF-S and so the only additional delay these tasks experience is at the vehicle's queue as they wait to be serially processed there. Here, with tasks being fully dispatched from the RSU's queue, may, under PA-R2VTO with serial
<figure><img src="image_8.png" /><figcaption>FIGURE 6. Level 2: $\bar{W}$ vs. $V_t$.</figcaption></figure>

processing, not be sorted in order of their deadlines at the vehicles' respective queues while, under EDF-S, it is found that all vehicle queues have tasks sorted in ascending order of their deadlines. Hence, EDF-S achieves a quasi-zero $P_{dm}$.

Now, when parallel processing is involved, PA-R2VTO with parallel processing, exhibits a much lower waiting time than EDF-P. This is the case since PA-R2VTO optimally distributes tasks to vehicles in such a way that all of them will be timely computed. In contrast, EDF-P dispatches tasks to vehicles in order and so might not be able to fit as many tasks in vehicles as PA-R2VTO does. As a matter of fact, it has been observed through simulations that EDF-P often leaves vehicles with non-utilized residual capacities with left over tasks at the RSU queue, whereas PA-R2VTO rarely does so causing the RSU's queue size to be much smaller than it is under EDF-P; hence, the lower queueing delay (the deadline mismatch $P_{dm} \approx 0$ in Figure 5). At this level, one can truly observe the superiority of PA-R2VTO with parallel processing when compared to EDF-P.

Figure 6 plots $\bar{W}$ as a function of $V_t$ for PA-R2VTO with serial and parallel processing as well as EDF-S and EDF-P. To gauge the effect of $V_t$ over $\bar{W}$, the vehicle arrival rate has been set to its maximum $\lambda_v = 0.277$ veh./s. Aside of the fact that $\bar{W}$ increases as a function of $V_t$ for all the considered schemes, it should now be clear to the reader that the selectivity PA-R2VTO with serial processing forces this latter to organize sorted tasks into groups (not necessarily sorted in ascending order of deadlines) that best fit the majority of the in-range vehicles in such a way that these vehicles will complete these tasks before leaving the RSU's range. Under such conditions, the serial variant of PA-R2VTO is found to clear out less tasks from the queue due to the difficulty of finding suitable vehicles to process the tasks as their sizes increase. Instead, EDF-S, regardless of the task size, aims at clearing as many tasks as possible to reduce the deadline mismatch (as proven in Figure 7) and, so, achieves a much lower waiting time on average and lower $P_{dm}$. Under parallel processing, PA-R2VTO outperforms EDF-P due to its ability to dispatch the vast majority of the tasks to in-range

<figure><img src="image_9.png" /><figcaption>FIGURE 7. Level 2: $P_{dm}$ vs. $V_t$.</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>FIGURE 8. Level 2: $\bar{W}$ vs. $d_m$.</figcaption></figure>

vehicles in a very well organized manner to asymptotically approach the 100% utilization of the in-range vehicles. EDF-P fails to do so because it lacks the luxury of organizing tasks into best fit groups. Instead, it blindly assigns these tasks one after the other to the vehicles only taking into account the task deadlines and vehicle sojourn times. With such ill-dispatching, EDF-P is often found not to be able to fully empty the RSU's queue and hence left over tasks suffer from deadline expiries. Obviously, considering task sizes and available vehicle capacities adds up one additional degree of flexibility allowing for more optimal R2V task offloading and, hence, promoting the outperformance of the parallel variant of PA-R2VTO over the EDF-P in terms of both $\bar{W}$ and $P_{dm}$ (as shown in Figures 6 and 7).

Figure 8 concurrently plots $\bar{W}$ versus $d_m$ for both serial and parallel variants of PA-R2VTO as well as EDF-S/P. To gauge the impact of $d_m$ over $\bar{W}$, $\lambda_v = 0.277$ veh./s and the mean task size has been fixed to as low as $V_t = 3 \times 10^6$ instructions. Clearly, the high vehicular traffic intensity puts at the RSU's disposal a large number of vehicles; hence, maximizing the likelihood of task dispatching. With low
<figure><img src="image_11.png" /><figcaption>FIGURE 9. Level 2: $P_{dm}$ vs. $d_m$.</figcaption></figure>

task sizes, the RSU finds itself always capable of entirely depleting its queue regardless under which offloading scheme it operates. So here, under serial processing mode, the delay that tasks experience is due to their waiting at the vehicles' queues until they are due for service (mainly as dictated by Eq. (22)). Obviously, serial processing shall incur delays that are much higher than parallel processing; hence, the big difference between the parallel and serial variants of PA-R2VTO and EDF in terms of $\bar{W}$. Here, the reason behind the identical results pertaining to the serial variants of PA-R2VTO and EDF in terms of both $\bar{W}$ (and so in terms of $P_{dm}$ as shown in Figure 9) should be quite clear to the reader. Also, the fact that PA-R2VTO with parallel processing outperforms EDF-P should also be obvious from the above-elaborated modus operandi of both schemes. Yet, as $d_m > 1.5$, the parallel variant of PA-R2VTO is showing a slight increase in waiting time. This is due to the additional degree of tolerance that tasks can endure (hence, waiting further in the RSU's queue) to be assigned to better-fit vehicles.

## VII. CONCLUSION

Modern vehicles, equipped with advanced computational resources and wireless capabilities, offer a promising platform for executing and offloading tasks to meet the stringent latency and connectivity demands of future networks. This paper introduces a two-tier resource management framework for efficient Priority-Aware RSU-to-Vehicle Task Offloading (PA-R2VTO). A Stackelberg game models resource allocation among passing vehicles, while task assignment is optimized considering deadlines and coverage area, employing multiple knapsack and non-cooperative congestion game formulations for serial and parallel computation modes, respectively. Extensive simulations demonstrate the superiority of the proposed PA-R2VTO framework over traditional Earliest Deadline First scheduling, providing valuable insights for leveraging vehicle-based computing to realize low-latency, always-connected services.

## REFERENCES

[1] X. Hou, Y. Li, M. Chen, D. Wu, D. Jin, and S. Chen, "Vehicular fog computing: A viewpoint of vehicles as the infrastructures," *IEEE Trans. Veh. Technol.*, vol. 65, no. 6, pp. 3860-3873, Jun. 2016.

[2] Z. Zhou, H. Liao, X. Zhao, B. Ai, and M. Guizani, "Reliable task offloading for vehicular fog computing under information asymmetry and information uncertainty," *IEEE Trans. Veh. Technol.*, vol. 68, no. 9, pp. 8322-8335, Sep. 2019.

[3] K. Zheng, Q. Zheng, H. Yang, L. Zhao, L. Hou, and P. Chatzimisios, "Reliable and efficient autonomous driving: The need for heterogeneous vehicular networks," *IEEE Commun. Mag.*, vol. 53, no. 12, pp. 72-79, Dec. 2015.

[4] I. Farris, T. Taleb, H. Flinck, and A. Iera, "Providing ultra-short latency to user-centric 5G applications at the mobile edge," *Trans. Emerg. Telecommun. Technol.*, vol. 29, no. 4, 2018, Art. no. e3169.

[5] Y. Yao, X. Chang, J. Mišic, and V. Mišic, "Reliable and secure vehicular fog service provision," *IEEE Internet Things J.*, vol. 6, no. 1, pp. 734-743, Feb. 2019.

[6] M. Ferreira, P. Gomes, M. K. Silvéria, and F. Vieira, "Augmented reality driving supported by vehicular ad hoc networking," in *Proc. IEEE ISMAR*, 2013, pp. 253-254.

[7] O. Altintas, F. Dressler, F. Hagenauer, M. Matsumoto, M. Sepulcre, and C. Sommery, "Making cars a main ICT resource in smart cities," in *Proc. IEEE INFOCOM*, 2015, pp. 582-587.

[8] F. H. Rahman, A. T. Wan, S. H. S. Newaz, and W. S. Suhaili, "Vehicular clustering: Fog paradigm and recent advances," in *Proc. IEEE 18th Int. Conf. Commun. Technol.*, 2018, pp. 468-472.

[9] E. Lee, E.-K. Lee, M. Gerla, and S. Y. Oh, "Vehicular cloud networking: Architecture and design principles," *IEEE Commun. Mag.*, vol. 52, no. 2, pp. 148-155, Feb. 2014.

[10] Q. Kong, R. Lu, H. Zhu, and M. Ma, "Achieving secure and privacy-preserving incentive in vehicular cloud advertisement dissemination," *IEEE Access*, vol. 6, pp. 25040-25050, 2018.

[11] G. Singh Pannu, T. Higuchi, O. Altintas, and F. Dressler, "Efficient uplink from vehicular micro cloud solutions to data centers," in *Proc. IEEE WoWMoM*, 2018, pp. 1-7.

[12] A. A. Al-Habob, A. Ibrahim, O. A. Dobre, and A. G. Armada, "Collision-free sequential task offloading for mobile edge computing," *IEEE Commun. Lett.*, vol. 24, no. 1, pp. 71-75, Jan. 2020.

[13] W. Z. Khan, E. Ahmed, S. Hakak, I. Yaqoob, and A. Ahmed, "Edge computing: A survey," *Future Gener. Comput. Syst.*, vol. 97, Aug. 2019, pp. 219-235.

[14] X. Zhao, J. Zhang, J. Zhang, P. Yuan, H. Jin, and X. Li, "CooCo: A collaborative offloading and resource configuration algorithm in edge networks," *IEEE Internet Things J.*, vol. 11, no. 6, pp. 10709-10721, Mar. 2024.

[15] W. Fan, Y. Zhang, G. Zhou, and Y. Liu, "Deep reinforcement learning-based task offloading for vehicular edge computing with flexible RSU-RSU cooperation," *IEEE Trans. Intell. Transp. Syst.*, vol. 25, no. 7, pp. 7712-7725, Jul. 2024.

[16] J. Zhang, Z. Ning, R. H. Ali, M. Waqas, S. Tu, and I. Ahmad, "A many-objective ensemble optimization algorithm for the edge cloud resource scheduling problem," *IEEE Trans. Mobile Comput.*, vol. 23, no. 2, pp. 1330-1346, Feb. 2024.

[17] M. Tao, K. Ota, and M. Dong, "Foud: Integrating fog and cloud For 5G-enabled V2G networks," *IEEE Netw.*, vol. 31, no. 2, pp. 8-13, Mar./Apr. 2017.

[18] M. Y. Akhlaqi and Z. B. M. Hanapi, "Task offloading paradigm in mobile edge computing-current issues, adopted approaches, and future directions," *J. Netw. Comput. Appl.*, vol. 212, Mar. 2023, Art. no. 103568.

[19] A. M. A. Hamdi, F. K. Hussain, and O. K. Hussain, "Task offloading in vehicular fog computing: State-of-the-art and open issues," *Future Gener. Comput. Syst.*, vol. 133, Aug. 2022, pp. 201-212.

[20] M. Nabi, R. Benkoczi, S. Abdelhamid, and H. S. Hassanein, "Resource assignment in vehicular clouds," in *Proc. IEEE ICC*, 2017, pp. 1-6.

[21] G. Hattab, S. Ucar, T. Higuchi, O. Altintas, F. Dressler, and D. Cabric, "Optimized assignment of computational tasks in vehicular micro clouds," *ACM EdgeSys*, 2019, pp. 1-6.

[22] I. Sorkhoh, D. Ebrahimi, C. Assi, S. Sharafeddine, and M. Khabbaz, "An infrastructure-assisted workload scheduling for computational resources exploitation in the fog-enabled vehicular network," *IEEE Internet Things J.*, vol. 7, no. 6, pp. 5021-5032, Jun. 2020.
[23] J. Shi, J. Du, J. Wang, J. Wang, and J. Yuan, "Priority-aware task offloading in vehicular fog computing based on deep reinforcement learning," *IEEE Trans. Veh. Technol.*, vol. 69, no. 12, pp. 16067-16081, Dec. 2020.

[24] N. Cha, C. Wu, T. Yoshinaga, Y. Ji, and K.-L. A. Yau, "Virtual edge: Exploring computation offloading in collaborative vehicular edge computing," *IEEE Access*, vol. 9, pp. 37739-37751, 2021.

[25] M. Diamanti, P. Charatsaris, E. E. Tsiropoulou, and S. Papavassiliou, "Incentive mechanism and resource allocation for edge-fog networks driven by multi-dimensional contract and game theories," *IEEE Open J. Commun. Soc.*, vol. 3, pp. 435-452, 2022, doi: 10.1109/OJCOMS.2022.3154536.

[26] Z. Xiao et al., "Multi-objective parallel task offloading and content caching in D2D-Aided MEC networks," *IEEE Trans. Mobile Comput.*, vol. 22, no. 11, pp. 6599-6615, Nov. 2023.

[27] R. Men, X. Fan, K. L. A. Yau, A. Shan, and Y. Xiao, "Mobility-aware parallel offloading and resource allocation scheme for vehicular edge computing," *Ad Hoc Netw.*, vol. 164, Nov. 2024, Art. no. 103639.

[28] T. Deng, Y. Chen, G. Chen, M. Yang, and L. Du, "Task offloading based on edge collaboration in MEC-enabled IoT networks," *J. Commun. Netw.*, vol. 25, no. 2, pp. 197-207, Apr. 2023.

[29] M. Z. Alam and A. Jamalipour, "Multi-agent DRL-based Hungarian algorithm (MADRLHA) for task offloading in multi-access edge computing Internet of Vehicles," *IEEE Trans. Wireless Commun.*, vol. 21, no. 9, pp. 7641-7652, Sep. 2022.

[30] H. Tang, H. Wu, G. Qu, and R. Li, "Double deep Q-network based dynamic framing offloading in vehicular edge computing," *IEEE Trans. Netw. Sci. Eng.*, vol. 10, no. 3, pp. 1297-1310, May/Jun. 2023.

[31] D. Cao et al., "A relay-assisted parallel offloading strategy for multi-source tasks in Internet of Vehicles," *Sustain. Energy Technol. Assess.*, vol. 62, Feb. 2024, Art. no. 103619.

[32] F. Busacca, C. Grasso, S. Palazzo, and G. Schembra, "A smart road side unit in a microeolic box to provide edge computing for vehicular applications," *IEEE Trans. Green Commun. Netw.*, vol. 7, no. 1, pp. 194-210, Mar. 2023.

[33] F. Azam, N. Priyadarshi, H. Nagar, S. Kumar, and A. K. Bhoi, "An overview of solar-powered electric vehicle charging in vehicular Adhoc network," *Electric Vehicles: Modern Technologies and Trends. Singapore: Springer*, 2021.

[34] M. Khabbaz, "Modelling and delay analysis of intermittently connected roadside communication networks," Ph.D. dissertation, Dept. Electr. Comput. Eng., Concordia Univ., Montreal, QC, Canada, 2012.

[35] M. Khabbaz, J. Antoun, S. Sharafeddine, and C. Assi, "Modelling and delay analysis of intermittent V2U communication in secluded areas," *IEEE Trans. Wireless Commun.*, vol. 19, no. 5, pp. 3228-3240, May 2020.

[36] M. Khabbaz, C. Assi, and S. Sharafeddine, "Multihop V2U path availability analysis in UAV-assisted vehicular networks," *IEEE Internet Things J.*, vol. 8, no. 13, pp. 10745-10754, Jul. 2021.

[37] J. R. Jackson, *Scheduling a Production Line to Minimize Maximum Tardiness*. Office Techn. Serv., 1955.

[38] J. Hong, X. Tan, and D. Towsley, "A performance analysis of minimum laxity and earliest deadline scheduling in a real-time system," *IEEE Trans. Comput.*, vol. 38, no. 12, pp. 1736-1744, Dec. 1989.

[39] Z. Han, D. Niyato, W. Saad, T. Basar, and A. Hjørungnes, *Game Theory in Wireless and Communication Networks: Theory, Models, and Applications*. Cambridge, U.K.: Cambridge Univ., 2011.

[40] J. B. Rosen, "Existence and uniqueness of equilibrium points for concave n-person games," *Econometrica*, vol. 33, no. 3, pp. 520-534, 1965.

[41] V. Cacchiani, M. Iori, A. Locatelli, and S. Martello, "Knapsack problems—An overview of recent advances. Part II: Multiple, multidimensional, and quadratic knapsack problems," *Comput. Oper. Res.*, vol. 143, Jul. 2022, Art. no. 105693.

[42] A. Fukunaga, "A branch-and-bound algorithm for hard multiple knapsack problems," *Ann. Oper. Res.*, vol. 184, pp. 97-119, Apr. 2011.

[43] I. Milchaica, "Congestion games with player-specific payoff functions," *Games Econ. Behav.*, vol. 13, no. 1, 1996, pp. 111-124.

[44] M. Gairing and M. Klimm, "Congestion games with player-specific costs revisited," in *Proc. Int. Symp. Algorithmic Game Theory*, 2013, pp. 98-109.

[45] M. J. Khabbaz, W. F. Fawaz, and C. M. Assi, "A simple free-flow traffic model for vehicular intermittently connected networks," *IEEE Trans. Intell. Transp. Syst.*, vol. 13, no. 3, pp. 1312-1326, Sep. 2012.

[46] M. Khabbaz, "Deadline-constrained RSU-to-vehicle task offloading scheme for vehicular fog networks," *IEEE Trans. Veh. Technol.*, vol. 72, no. 11, pp. 14955-14961, Nov. 2023.

[47] B. Shabir, A. U. Rahman, A. W. Malik, and M. A. Khan, "On collective intellect for task offloading in vehicular fog paradigm," *IEEE Access*, vol. 10, pp. 101445-101457, 2022.

[48] H. Guo and J. Liu, "Collaborative computation offloading for multiaccess edge computing over fiber-wireless networks," *IEEE Trans. Veh. Technol.*, vol. 67, no. 5, pp. 4514-4526, May 2018.

<figure><img src="image_12.png" /></figure>

**KINDA KHAWAM** received the B.E. degree in telecommunications and networking engineering from the Saint Joseph University of Beirut in 2001, and the M.E. and Ph.D. degrees in computer science from Telecom Paristech in 2003 and 2006, respectively. She is currently an Associate Professor with the University of Versailles. Her research interests include distributed and centralized radio resource management, green networking and IoT, 5G wireless networks, game theory, machine learning, and optimization.

<figure><img src="image_13.png" /></figure>

**MAURICE KHABBAZ** (Senior Member, IEEE) received the Ph.D. degree in electrical engineering from Concordia University, Montreal, Canada, in 2012. He is currently a Tenured Associate Professor with the Computer Science Department, American University of Beirut. His research interests are in the areas of the next generation carrier grade networks, Internet of Things, cloud/datacenter networking, intelligent transportation systems, vehicular networks, wireless networking, dynamic spectrum access, delay-/disruption-tolerant networking, modeling and performance analysis, network optimization, and queueing theory. He serves as an Executive Editor for the IEEE COMMUNICATIONS LETTERS as well as an Associate Editor-in-Chief for IEEE INTERNET OF THINGS MAGAZINE. He is currently an Associate Editor of the IEEE TRANSACTIONS ON COMMUNICATIONS, the IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT and IEEE ACCESS.

<figure><img src="image_14.png" /></figure>

**JOE SAAD** received the B.E. degree in computer and communications engineering from Saint Joseph University, Beirut, in 2017 and the Ph.D. degree from the Orange Labs, University of Versailles, France, in 2024. He is currently a Technical Consultant with Murex, France. His research interests include 5G mobile networks, resource allocation optimization, IoT, software-defined networks, and open-RAN architecture.