Adapting Multi-Stage Distributed Real-Time Systems Design to Vehicular Edge Computing

Adapting Multi-Stage Distributed Real-Time Systems Design to Vehicular Edge Computing Niraj Kumar, Anant Gautam

arXiv:2611.12370v1 [cs.DC] 9 Nov 2026

Indian Institute Of Technology Goa, India Email: {niraj, anant2413101}@iitgoa.ac.in

Abstract—Vehicular Edge Computing (VEC) aims to support computation-intensive applications in intelligent transportation systems while meeting stringent latency requirements. When processed remotely, applications require access to different resource types in a specific sequence, forming a multi-stage processing pipeline. This structure closely resembles multistage distributed applications executing across heterogeneous resources, making established multi-stage distributed real-time scheduling techniques well suited for modeling VEC systems. The resulting model accommodates diverse resource configurations and access patterns. Building on this model, we propose a joint mapping and scheduling approach that accounts for vehicle mobility and real-time constraints. The proposed heuristic extends optimal priority assignment for multi-stage systems to the VEC setting, to construct feasible schedules while minimizing local-device energy consumption and ensuring that offloaded jobs meet their deadlines. Extensive simulations show that the proposed approach consistently outperforms both a baseline based on the same delay-composition framework and a deadline decomposition-based approach. Index Terms—Real-Time Systems, Vehicular Edge Computing, Scheduling, Mapping

I. Introduction Vehicular Edge Computing (VEC) extends edge computing to intelligent transportation systems by enabling vehicles to offload computation-intensive applications to edge servers [1]–[3]. It has emerged as a promising paradigm for supporting low-latency, computationintensive applications. Since onboard computational resources are limited, jobs may be processed locally or offloaded to edge infrastructure. Effective mapping of jobs to VEC resources and scheduling their access to these resources are crucial for fully exploiting the benefits of vehicular edge computing. In addition to resource constraints, vehicle mobility introduces time-varying resource availability. Scheduling decisions must therefore jointly decide whether to execute locally or offload a job, resource mapping, and execution order, while explicitly considering vehicle mobility and end-toend deadlines. Existing approaches often consider resource contention in isolation: some works ignore contention altogether [4], [5], while others consider only computation [6]–[10] or communication resources [11], [12]. A smaller body of work considers contention across both communication and

computation resources [3], [13]–[15]. However, their models are restricted to two resource types, limiting their ability to capture more general and heterogeneous VEC systems. Furthermore, existing approaches often rely on ILP and other computationally expensive optimization techniques [16], [17]. Such approaches are less suitable for VEC environments, where job arrivals are determined at runtime and resource availability can change dynamically, requiring scheduling decisions to be made with low overhead. These limitations motivate a lightweight, holistic resource mapping and scheduling approach that supports diverse resource types and configurations while preserving the end-to-end delay structure. Emerging VEC applications may involve multiple stages spanning wireless and wired networks as well as heterogeneous computing resources, such as CPUs, GPUs, and other accelerators. Existing works also rarely consider the download of results back to the vehicle, despite it being part of the end-to-end processing path. Furthermore, different applications may follow different resource access patterns. This motivates modeling a VEC application as an end-to-end multi-stage pipeline, where each stage represents communication or computation over a potentially heterogeneous resource. The resulting model provides a generic framework that can accommodate diverse resource configurations and access patterns without being tied to a specific system configuration. Furthermore, this model also support both preemptive and non-preemptive stages seamlessly. Mobility has also been considered in recent VEC scheduling and resource allocation studies [9], [12], [18], [19]. Our goal, however, is to develop a generic framework for VEC applications. The model should capture arbitrary numbers and types of heterogeneous resources, resource contention across different stages, end-to-end timing constraints, and mobility, while supporting joint resource mapping and scheduling. Specifically, we ask the following fundamental research question: How can multi-stage real-time scheduling and resource allocation approaches be adapted to Vehicular Edge Computing systems to jointly optimize resource mapping and task offloading under mobility and end-to-end timing constraints? From Prior Work to Our Design: Recently, [20] studied fixed-priority (FP) scheduling of real-time jobs

II. System Model and Problem Statement A. System Architecture Figure 1 illustrates the Vehicular Edge Computing (VEC) architecture considered in this work. The system consists of a set of vehicles V = {Vk }, roadside units

Information/Control Flow

Backhaul link

Wireless link

VEC Controller Resource Mapping and Scheduling

Mobility and Network Monitoring

System State (Network conditions, mobility, resource status)

Mapping and Scheduling Decisions

Edge Servers

Fo rw Jo ard b

with end-to-end deadlines in distributed systems, focusing on multi-stage pipelines where each stage corresponds to a resource type and may consists of multiple heterogeneous resources. Their approach combines optimal priority assignment (OPA) [21] with a schedulability test based on delay-composition algebra (DCA) [22], [23] to compute an optimal schedule. While the work also evaluates a VEC setting, it assumes that the mapping of jobs to resources is given. Building on this framework, we address the joint resource mapping and scheduling problem while explicitly incorporating vehicle mobility into these decisions. Prior work [24], [25] addresses real-time scheduling with end-to-end deadline constraints by decomposing an endto-end deadline into per-stage deadlines and then applying single-stage scheduling techniques. While these techniques can be applied in a VEC setting too, however, deadline decomposition is non-trivial and may turn an otherwise schedulable workload into an unschedulable one [20]. The key contributions of this work are summarized in the following. • In line with [20], we model a VEC system as a multistage multi-resource distributed real-time system, enabling the use of established results from this area. Building on [20], we additionally address the mapping of jobs to heterogeneous resources and explicitly account for vehicle mobility. • We propose a mobility-aware heuristic MJMP that jointly performs mapping and scheduling by utilizing optimal priority assignment and delay-composition algebra while accounting for mobility and end-to-end delay to minimize energy consumption. • We conduct an extensive evaluation across a diverse range of system and workload configurations against two baselines. The first uses the same delaycomposition algebra, isolating the impact of our mapping strategy, while the second uses a decompositionbased approach, highlighting the benefits of directly optimizing end-to-end delay. Extensions to [20]: This work builds on the multistage multi-resource distributed scheduling framework developed in [20], which proposes an optimal scheduling approach and uses a VEC setting for evaluation. However, [20] does not explicitly model vehicle mobility and assumes that resource mapping is given. In contrast, this work jointly addresses resource mapping and scheduling while explicitly accounting for mobility and its impact on resource availability. Furthermore, unlike [20], we also consider the energy consumption of vehicles as an optimization objective.

For Re ward sult Coverage Range of RSU3

d

loa

Up

b Jo RSU1

D

RSU3 Roewnloa

RSU2

su

lt d

Direction of movement

Vehicles moving on a road

Fig. 1: Vehicular Edge Computing System Architecture (RSUs) R = {Ri }, and servers S = {Sj }. Vehicles communicate with RSUs over a wireless network, while RSUs connect to servers through a wired backhaul network. We assume that vehicles move in the same direction. For simplicity, we assume that each RSU is connected to every server. More generally, RSU↔server connectivity can be represented by a connectivity set C ⊆ R × S, where (Ri , Sj ) ∈ C indicates that RSU Ri can communicate with server Sj . The proposed approach does not require full connectivity and can directly accommodate arbitrary RSU↔server connectivity. Following common practice in the literature, we assume that the wireless network supports simultaneous uploading and downloading for vehicles within the coverage range of an RSU, with uplink and downlink transmissions using orthogonal channels [3]. Since vehicles are mobile, the RSU used for downloading may differ from the one used for uploading. Each server Sj provides a processing capacity of cj cycles per unit time. Vehicle mobility and network conditions are monitored by the control plane, and the resulting information is made available to the VEC controller for resource mapping and scheduling decisions. B. Job Model We assume that the offloading algorithm runs periodically on the VEC controller, with each invocation receiving a snapshot of the system representing its current state. For simplicity, each vehicle Vk generates one job Jk . Let J denote the set of N job jobs. Each job Jk ∈ J is charlocal acterized by ⟨pk , ak , θkinp , θkres , creq ⟩ as explained k , dk , Ek in the following. Let pk be the current absolute position of the corresponding vehicle Vk , ak ≥ 0 is its arrival time, θkinp and θkres are the input and result sizes (in MB), respectively, and dk is its deadline. Jobs may arrive in the future, for example, due to periodic tasks running on vehicles or event-triggered applications. Given the vehicle speed sk , we can determine the time entry exit window [Tk,i , Tk,i ] during which vehicle Vk remains entry within the coverage range of RSU Ri . Here, Tk,i and

exit Tk,i denote the entry and exit times, respectively. The corresponding sojourn time is sojourn entry exit Tk,i = Tk,i − Tk,i .

(1)

Thus, any upload or download through an RSU must be completed within the corresponding coverage window. Moreover, let creq denotes the number of CPU cycles k required to complete Jk . A job can either be executed locally or offloaded to a server through an RSU. For local execution, we assume that the onboard processor can complete the job before its deadline at an energy cost of Eklocal . For offloaded execution, the vehicle consumes energy for uploading the job and downloading the result. For simplicity, we assume that every server provides the resource types required to process any job, allowing a job to be assigned to any server. This assumption can be relaxed trivially by restricting the set of feasible mappings. C. Delay and Energy Model Following common practice, the transmission rate between vehicle Vk and RSU Ri is given by   ρk |ℏ|2 , (2) αk,i = B log2 1 + υ w0 (δk,i ) where B is the bandwidth, ρk is the transmit power of Vk , ℏ is the channel fading coefficient, w0 is the white Gaussian noise power, δk,i is the distance between vehicle Vk and RSU Ri , and υ is the path-loss exponent. Thus, the time required to upload the job Jk to RSU Ri is f tof k,i =

θkinp αk,i

(3)

while downloading the result takes tres k,i =

θkres αk,i

(4)

We assume a high-speed backhaul network which provides a constant transmission rate σ, resulting in an input θ inp transfer delay of kσ from the RSU to the server and a θ res result transfer delay of kσ from the server to the RSU. The processing time of job Jk on server Sj is tproc k,j =

creq k cj

(5)

We allow preemptive execution at servers, while wireless as well as backhaul transmissions are non-preemptive. The end-to-end delay ∆k therefore depends not only on its upload, processing, and download times, but also on interference from higher-priority jobs at preemptive stages and from both higher- and lower-priority jobs at nonpreemptive stages. The energy consumed by vehicle Vk for local execution of job Jk is Eklocal . If the job is offloaded through RSU Ri and its result is downloaded through  RSU Rq, the f res corresponding energy consumption is ρk tof k,i + tk,q .

Let Xk,i be a binary variable that is 1 if job Jk is uploaded through RSU Ri , and 0 otherwise. Similarly, Zk,i indicates whether the result is downloaded through RSU Ri , and Yk,j indicates whether the job is processed on server Sj . Let Lk indicate whether the job is executed locally (Lk = 1) or remotely (Lk = 0). The total vehicle energy consumption is then # job " N  X X of f local res Φ= Lk Ek + ρk Xk,i tk,i + Zk,i tk,i k=1

i

(6) For a locally executed job, Lk = 1, and all upload, processing, and download variables are zero. For an offloaded job, Lk = 0, with exactly one upload RSU, one processing server, and one download RSU selected. Let Mk,x denote the resource assigned to job Jk in stage Sx . For example, Xk,i = 1 if Mk,x = Ri for the corresponding upload stage. D. Problem Formulation Given the vehicles V = {Vk }, RSUs R = {Ri }, servers S = {Sj }, and available jobs J = {Jk }, the mobility aware mapping and scheduling in VEC problem, henceforth referred to as MMSV, is to determine, for each job Jk : 1) whether the job is executed locally or offloaded, as indicated by Lk ; 2) if offloaded, the RSU used for uploading, the server used for processing, and the RSU used for downloading, represented by Xk,i , Yk,j , and Zk,i , respectively; 3) a unique global priority πk for each job, which determines its execution order across the pipeline. The resulting schedule must account for the set of higher-priority jobs at preemptive stages and both higher- and lower-priority jobs at non-preemptive stages. The resulting schedule must ensure that every offloaded job completes within its end-to-end deadline: (1 − Lk )∆k ≤ dk

(7)

where ∆k is the end-to-end deadline of Jk in the pipeline with both preemptive and non-preemptive stages. The objective is to minimize the total energy consumption of the vehicles Φ in Eq. (6). Problem Complexity: Even a restricted version of MMSV reduces to the flow-shop scheduling problem with job deadlines, which is NP-hard [3], [26]. Specifically, by fixing vehicle mobility, resource mappings, and energy considerations, and assuming a fixed sequence of resource stages, MMSV reduces to scheduling jobs with end-to-end deadlines on a flow-shop system. Therefore, MMSV is NP-hard. The full problem is further complicated by vehicle mobility and the resulting dynamic resource availability, which must be jointly considered with resource mapping, end-to-end deadline constraints, and priority assignment. Moreover, the scheduler must optimize vehicle energy consumption while maintaining deadline feasibility.

III. Proposed Approach In the following, we present our Mobility-Aware Joint Mapping and Priority Assignment (MJMP) approach for solving MMSV. The problem can be viewed as three closely related subproblems: [SP1], end-to-end delay computation; [SP2], priority assignment; and [SP3], mobilityaware resource mapping for each stage. We address SP1 using the Delay-Composition Algebra (DCA) described in Section III-B and SP2 using the Optimal Priority Assignment (OPA) described in Section III-A. Finally, since MMSV is NP-hard, we develop an efficient mobilityaware heuristic, MJMP, to jointly address resource mapping and priority assignment, as described in Section III-C. Notably, the formulation in Section II can be extended to an ILP; however, such a solution has limited utility due to scalability and the low runtime requirement in a VEC setting. A. Optimal Priority Assignment (OPA) OPA assigns fixed priorities to a set of n tasks by constructing a linear ordering (permutation) of the tasks in O(n2 ) time [21]. The priorities are assigned incrementally, starting from the lowest and proceeding toward the highest. At each priority level, OPA considers the tasks that have not yet been assigned a priority and identifies one that can feasibly take the current priority. Feasibility is checked using an OPA-compatible feasibility test [20], [27], [28]. Once a feasible task is found, OPA assigns it the current priority and removes it from further consideration. If no remaining task passes the feasibility test, OPA declares the task set unschedulable. The procedure continues until all tasks have been assigned priorities. As shown in [20], an OPA-compatible feasibility test can be constructed using DCA. In our setting, OPA assigns each offloaded job Jk a unique global fixed priority πk . These priorities define the ordering of jobs when accessing shared resources throughout the processing pipeline. In Section III-C, we use OPA for joint priority assignment and job-to-resource mapping.

⟨Jb , Jc , J1 ⟩ Ja

Jb

S1 0

S2 S3 S4 S5 S6

↓

Ja Jb Jc

2 3 Pb,1 + Pa,1

4

J1 5

Jb

Delay 4 in S2 : δ2 = Pb,2

Jb J1 Ja Jc Priority:Ja > Jb > Jc > J1

job’s arrival

Ja preempts Jb in S1 7

J1 Ja is not mapped with J1 in S2

Jc 5

Ja

Jb

7

8

Ja

5 6 8 Ja ’s segment δ3 ≤ Pb,3 + Pa,3 ends in S4 −→ 8

Jb Jc 9

Ja

J1

10

←− Ja ’s new segment begins in S3 12

Jb Jc

10 11 12 Jb ’s segment ends in S5 −→ Pa,4 + Pb,4

J1 14

Jb Jc J1

If relative priority is not known δ2 ≤ max{Pb,2 , Pc,2 , P1,2 }

11 12 13 14 Pb,5 + Pc,5

Jc

J1

13 15 16 Pc,6 + P1,6

Fig. 2: End-to-End Delay in a Preemptive Pipeline

As illustrated in Figure 2, if the relative priority among jobs and their arrival times at the first stage are known, the exact end-to-end delay can be computed incrementally. Specifically, the arrival and finish times of jobs are determined at each stage, traversing the pipeline from the first to the last stage and considering jobs in decreasing priority order. However, OPA compatibility requires only the sets of higher- and lower-priority jobs to be known; their relative ordering within each set is not yet determined. DCA avoids this requirement by deriving a delay bound based on the overlap of job execution across stages.

B. Delay Composition Algebra (DCA)

The DCA bound consists of a stage-additive component for each stage except the last and a job-additive component for higher-priority jobs. To formulate these components, we define a segment with respect to job Jk as a sequence of consecutive stages such that (i) Jk shares every stage in the segment with J1 , and (ii) the first (last) stage of the segment is either the first (last) stage of the pipeline or Jk does not share the stage immediately before (after) the segment with J1 . For example, ⟨S3 , S4 ⟩ forms a twostage segment of job Ja . Let Nkseg denote the number of segments of job Jk .

DCA provides an upper bound on the end-to-end delay of a job executing in a multi-stage pipeline by accounting for the overlap in job execution across stages. We briefly describe the delay-bound computation below to make the paper self-contained; additional details can be found in [20], [22], [23]. Let J1 be the target job for which we want to comub pute a delay bound ∆ub 1 such that ∆1 ≥ ∆1 . The job executes alongside a set of higher-priority jobs H1job and lower-priority jobs Ljob in a pipeline with N stg stages, as 1 illustrated in Figure 2. We exclude from H1job and Ljob 1 any jobs whose activation windows do not overlap with that of J1 . We further define H1+ = H1job ∪ J1 . Let Pk,x denote the processing time of job Jk at stage Sx .

The end-to-end delay bound is composed of the following terms: (1). for each stage except the last, the maximum processing time among jobs in H1+ that share the stage with J1 ; (2). for each one-stage segment, the processing time of the corresponding higher-priority job; (3). for each segment spanning two or more stages, the highest and second-highest processing times of the corresponding higher-priority jobs within the segment under preemptive scheduling, and only the highest processing time under non-preemptive scheduling; and (4). under non-preemptive scheduling, a blocking term for each stage, given by the maximum processing time among all jobs that share that stage. These rules summarize the DCA formulation presented in [22], [23]. We define the effective processing time

of job Jk at stage Sx as ( Pk,x , if Jk and J1 share stage Sx , tk,x = 0, otherwise. and an indicator variable Ix which is 1 for a nonpreemptive stage and 0 for a preemptive stage. Using these definitions, the end-to-end delay bound ∆ub 1 for a pipeline containing both preemptive and non-preemptive stages is given below. ∆ub 1 =

stg NX −1

x=1

max tk,x +

Jk ∈H+ 1

X Jk ∈H+ 1

ξk +

stg N X

x=1

Ix max tk,x Jk ∈J \J1

(8) where ξk denotes the interference terms due to higher priority jobs computed as per the rules discussed above. Note that Eq. (8) builds upon the delay bounds for preemptive and non-preemptive scheduling given in Eqs. (5) and (6) of [20]. Therefore, the OPA-compatibility proofs established in Section IV.A [20] can likewise be extended to Eq. (8). Adapting DCA to Our VEC Setting. The generic delay bound in Eq. (8) consists of three components: a stage-additive component capturing the execution time across stages, a job-additive component capturing interference from higher-priority jobs, and a blocking component capturing interference from lower-priority jobs at non-preemptive stages. Our VEC model consists of five stages. Each processing term is accounted exactly once, either as a stage-additive term, a job-additive term due to higher-priority jobs, or a job-blocking term due to a non-preemptive stage. C. Mobility aware Joint Mapping and Priority Assignment Since mapping is NP-hard, combinatorial approaches such as ILP, despite providing optimal solutions, are not well suited to our online setting, where the complete set of jobs is not known in advance. We therefore propose a lightweight mapping and priority-assignment approach, MJMP, that can be applied online to obtain a near-optimal solution. MJMP jointly determines resource mappings and global priorities while explicitly accounting for vehicle mobility to optimize the energy consumption of vehicles. The key insight behind MJMP is to decouple mobility from the mapping of intermediate stages. Specifically, processing at the intermediate stages is independent of vehicle mobility, which affects only the first and last stages of the pipeline. A job can be uploaded to an RSU, or its result downloaded from an RSU, only while the vehicle is within the corresponding coverage range. The fundamental idea behind the mapping strategy is to distribute jobs across available resources so that jobs with similar deadlines are not concentrated on the same resource. This helps reduce contention and improves the likelihood of meeting end-toend deadlines, while RSU mappings additionally account for the mobility and sojourn time. Priority assignment

Algorithm 1: MJMP – Mobility aware Joint Mapping and Priority Assignment C ← ∅; π cand ← N job RU 2 M ← RSUUploadMapping() S 3 M ← ServerMapping() 4 Sort J in the increasing order of energy density 5 Qk ← GetCandRSUDownload(), ∀k 6 foreach Jk ∈ J \ C do 7 Rearrange(Qk ) 8 status ← False 9 foreach Ri ∈ Qk do 10 if Ri is feasible with π cand then 11 πk ← π cand ; Mk,5 ← Ri 12 π cand ← π cand − 1; status ← True; Break 1

13 14

if !status then C ← C ∪ Jk ; Update MRU and MS

MRD ← {Mk,5 }
RS ← RSUServerLinkMapping MRU , MS
16 M SR 17 M ← ServerRSULinkMapping MS , MRD 18 return ⟨{π}, M, C⟩ 15

follows OPA. The overall procedure is summarized in Algorithm 1 and discussed below. MJMP first computes the upload mapping MRU = Mk,1 using RSUUploadMapping(), given in Algorithm 2. Specifically, RSUUploadMapping() first orders jobs by their absolute deadlines, ak + dk . For each job, it selects the RSU with the smallest deadline assigned so far among those for which the vehicle’s sojourn time is sufficient to complete the upload (Step 9). Thus, an RSU is excluded if the vehicle has already left its coverage range or if the remaining sojourn time is insufficient for the upload. Since uploading is non-preemptive, once an upload begins, it must complete before another upload can use the same transmission resource. Thus, if no feasible RSU is found, then in Step 11 the job is migrated for local execution. The server mapping is then determined in Algorithm 1 using ServerMapping(), which follows the same basic principle of spreading jobs across resources according to their deadlines. Unlike the upload stage, server mapping is not directly constrained by mobility; under our assumption that every server can process every job, all servers are feasible and no additional feasibility test is required. Next, the set of locally executed jobs C is initialized to ∅, and the candidate priority π cand used by OPA is initialized to N job in Step 1. Jobs are then considered in increasing order of energy density, defined as energy consumption per unit of processing time. This ordering allows the heuristic to favor local execution for jobs that are relatively expensive to execute locally when selecting between local and offloaded execution. The priority assignment and download mapping are determined in Steps 7–14. For each job, a set of feasi-

Algorithm 2: RSUUploadMapping() Sort J = {Jk } in increasing order of absolute deadline ak + dk 2 ωi ← 0, ∀i|Ri ∈ R 3 foreach Jk ∈ J do 4 Qk ← ∅ 5 foreach Ri ∈ R do of f 6 if ak ≤ texit k,i − tk,i then 7 Qk ← Qk ∪ Ri 1

8 9 10 11 12

if Qk ̸= ∅ then Mk,1 ← arg min ωi ; ωi ← ak + dk Ri ∈Qk

else C ← C ∪ Jk return {Mk,1 }

ble RSUs is first computed in Step 5, initially assuming no interference from other jobs. The feasible set Qk is then reordered using Rearrange(Qk ) so that RSUs are considered from right to left according to their absolute positions. This ordering allows the heuristic to select an RSU that is feasible under the current candidate priority π cand while delaying the job as much as possible. If no feasible combination of priority and download RSU is found, the job is migrated to local execution. The backhaul mappings are straightforward under the assumed full RSU↔server connectivity. Given the upload and server mappings ⟨MRU , MS ⟩, the RSU-to-server mapping MRS can be directly determined. Similarly, given ⟨MS , MRD ⟩, the server-to-RSU mapping MSR follows directly. No additional mapping decisions are therefore required for these stages. Finally, MJMP imposes a release restriction on the download stage. Although the execution of the intermediate stages is determined solely by priority, downloading cannot begin until the preceding stage has completed and the vehicle is within the coverage range of the selected RSU. Since the download mapping is determined using the upper-bound delay1 provided by DCA, the download must begin at this delay bound to guarantee that the vehicle remains within range of the respective RSU. Thus, the download stage is governed by both global priority and release time, with the latter determined by the completion of the preceding stage. D. Discussion Release Restrictions: The release restriction is introduced solely to ensure that the DCA-based upper-bound delay remains valid in the presence of mobility. It does not constitute an additional scheduling decision; rather, it constrains when the final transmission may start so 1 The actual completion time of the previous stage may be earlier, allowing the download to begin before the delay bound.

that the delay bound remains consistent with the vehicle’s movement. The restriction is needed only when mobility introduces uncertainty that must be captured by the upper-bound delay and therefore need not be enforced throughout the entire execution. Why OPA? OPA can produce EDF- or RM-like priority orderings as special cases, but its main advantage in our distributed setting is its flexibility to assign priorities based on actual schedulability. Jobs need not be mapped to the same resources at every stage. For example, consider two jobs J1 and J2 with D1 < D2 . An EDF-like policy would always assign J1 higher priority than J2 on every resource. However, given their different resource mappings, this ordering may make J2 infeasible on one or more of its mapped resources, whereas reversing their priorities may allow both jobs to meet their deadlines. OPA therefore avoids imposing a globally deadline-ordered priority and instead determines priorities based on the schedulability of the mapped jobs. This flexibility is particularly important when jobs follow different resource paths through the system. Notably, for a given mapping and a schedulability test, OPA is optimal [20], [29]. Why DCA? DCA is needed to compute delay bounds during the joint mapping and priority-assignment process. Under OPA, the complete priority ordering is not known until the priority-assignment procedure is completed. DCA provides the required delay bounds as priorities and mappings are progressively determined, allowing their feasibility to be evaluated during the procedure. IV. Experimental Results We evaluate the performance of MJMP2 against two baselines across a wide range of system and workload configurations. The first baseline EFF uses the same DCAbased delay-computation framework as MJMP, while the second DCMP adopts a decomposition-based approach that assigns per-stage deadlines to satisfy an end-to-end deadline constraint. We assume that the backhaul is a high-speed network, such as an optical-fiber network, with sufficient bandwidth to provide near-contention-free communication. Accordingly, we model the backhaul using a constant transmission rate and negligible queuing delay [3], [16]. In our experiments, we therefore assume a fixed backhaul delay determined by the corresponding transmission rate. We also assume that all RSUs are available for offloading. The remaining system parameters are selected based on VEC configurations commonly used in the literature including [3], [16], [20]. Baselines: We consider two baselines. The first, EFF, is an end-to-end-based configuration that uses EDF for priority assignment. Its mapping strategy operates as follows. For each RSU, jobs are ordered according to their arrival times. The first job in each RSU queue is considered in 2 Upon acceptance, the source code will be made publicly available.

TABLE I: Simulation Parameter Configurations cfg2

cfg3

40

cfg4

[0.6, 0.7] [0.7, 0.8] [0.8, 0.9] [0.9, 1] {5, 3, 5} {10, 5, 10} {15, 7, 15} – {0.2, 0.3, 0.1} {0.2, 0.4, 0.1} {0.2, 0.5, 0.1} {0.3, 0.6, 0.1} 80 100 120 –

each iteration and assigned to the corresponding resource, after which the selected job is removed from all queues. A job that cannot satisfy its end-to-end deadline is migrated to local execution. The second baseline, DCMP, uses a decomposition-based approach. Each job is decomposed into a set of per-stage tasks with corresponding offsets and deadlines derived from its end-to-end deadline. The end-to-end deadline is distributed across the stages in proportion to their processing times, where the minimum processing time of each stage is used for the decomposition. DCMP then selects the first available resource for each decomposed task. Feasibility is determined using the Demand Bound Function (DBF). If a job is found to be infeasible, it is migrated to local execution and its corresponding decomposed tasks are removed from all stages. Experimental Setup: We vary the number of jobs N job , the number of resources in each stage Nxres , the average resource utilization in each stage ustg x , and β which determines the deadline. Specifically, the deadline of each job is set to β × ξ, where ξ denotes the maximum time for which the corresponding vehicle remains on the road. Table I shows the values of simulation parameters. Unless otherwise stated, the bold-faced values represent the default configuration. β is sampled uniformly from the specified range for each configuration in Table I; for the default configuration, it is sampled uniformly from [0.8, 1]. For each configuration we generate 1000 test cases. We evaluate the approaches in terms of energy consumption at the vehicles. In particular, we focus on the energy saved through offloading relative to executing all jobs locally. Since the energy consumed for wireless transmission is negligible compared with the energy required for local processing in the considered setting, we ignore the energy cost of uploading jobs and downloading results in the experiments. Results: For consistency across experiments, we report energy improvement relative to executing all jobs locally. Specifically, for each approach, the reported value is the saving in energy consumption compared to executing all jobs locally. Thus, a larger improvement indicates greater energy savings. Figure 3 shows the impact of the deadline ratio β on energy savings. Since stage utilization remains constant, increasing β primarily allows jobs to be assigned longer processing times, and therefore has only a limited impact on energy savings. This trend is reflected in our results. For β ∈ [0.6, 0.7], DCMP, EFF, and MJMP achieve average

Improvement (%)

β Nxres ustg x N job

cfg1

EFF DCMP MJMP

30

20

10

cfg1

cfg2

cfg3

cfg4

Fig. 3: Varying Deadline 40

Improvement (%)

Parameter

EFF DCMP MJMP

30

20

10

cfg1

cfg2

cfg3

cfg4

Fig. 4: Varying Utilization

improvements of 9%, 6.7%, and 14.1%, respectively, relative to executing all jobs locally. For β ∈ [0.9, 1], the corresponding improvements are 9.8%, 6.8%, and 15.5%. Thus, varying β results in minor savings in average energy consumption. In contrast, varying stage utilization leads to a noticeable relative improvement for MJMP, as discussed next. Overall, although the minimum energy savings of MJMP are only slightly higher than those of the baselines or lower β values, both its average and maximum savings consistently increase with β. Figure 4 shows the impact of resource utilization on energy savings. To isolate the effect of the first two stages, we keep the utilization of the final stage fixed while increasing the utilization of the first and second stages. Note, this assumptions reflect a realistic system. As utilization increases, jobs require a larger share of the available processing capacity, making fewer jobs feasible for offloading when the other parameters remain unchanged. Consequently, the energy savings generally decrease for all approaches. MJMP, however, consistently maintains higher energy savings than both baselines. DCMP performs slightly better than or comparably to EFF across the considered configurations, but the gap between the baselines and MJMP remains evident. Figure 5 illustrates the impact of the number of resources on energy savings. Increasing the number of re-

2000

EFF DCMP MJMP

1600

30

Time (ms)

Improvement (%)

40

20

10

1200 800

EFF DCMP MJMP

EFF: 10x scaled; DCMP: 100x scaled for presentation

400

cfg1

cfg2

cfg3

Fig. 5: Varying Number of Resources

0

80

100

120

Number of Jobs

Fig. 7: Runtime with Number of Jobs

Improvement (%)

40

EFF DCMP MJMP

30

20

10

cfg1

cfg2

cfg3

Fig. 6: Varying Number of Jobs

sources provides greater flexibility for mapping jobs and reduces resource contention, allowing more jobs to be offloaded successfully. For example, when the number of resources increases from {5, 3, 5} to {15, 7, 15}, the energy savings of DCMP increase from 3.6% to 10.4% compared to executing all jobs locally. The performance of EFF also increase from 6.1% to 11% compared to executing all jobs locally. In comparison, MJMP improves considerably from 12.9% to 18.2% compared to executing all jobs locally. The improvement achieved by MJMP reflects its ability to exploit the additional mapping flexibility when more resources are available. Moreover, the maximum achieved saving also increases as expected. Note that adding more resources also tends to increase the utilization assigned to each job, since the stage utilization and number of jobs remain constant. This explains the consistent but proportional improvement. Figure 6 examines the effect of increasing the number of jobs while keeping the other parameters, including resource utilization, fixed. As the number of jobs increases, the same utilization is distributed among a larger number of jobs, resulting in smaller and more similar jobs. Although the fraction of jobs executed locally may remain relatively stable, the energy benefit of offloading each individual job decreases because the difference between local and remote execution becomes smaller. Consequently, the overall energy savings decrease as the number of jobs increases. The results show a consistent downward trend across the considered configurations, as expected.

Finally, Figure 7 shows the average execution time of the algorithms as the number of jobs increases, providing an indication of their scalability. For presentation clarity, the runtime of DCMP is scaled by 100× and that of EFF by 10×. As expected, the runtime increases with the number of jobs because the algorithms must process a larger set of jobs and perform more feasibility checks. Nevertheless, the runtime of MJMP remains practical for the considered VEC configurations, demonstrating that the proposed approach can scale to large workloads while providing substantially higher energy savings. V. Conclusion In this work, we studied joint resource mapping and scheduling for Vehicular Edge Computing (VEC) systems under vehicle mobility and end-to-end real-time constraints. We modeled VEC applications as multi-stage multi-resource distributed real-time systems. This formulation provides a flexible framework for representing a range of VEC applications with different resource configurations and access patterns. Building on this model, we proposed MJMP, a mobilityaware heuristic that jointly determines resource mappings and global job priorities. Mobility is incorporated through feasibility checks for the RSU mappings, allowing the approach to account for the limited time vehicles remain within RSU coverage. Extensive simulation across a wide range of system and workload configurations demonstrated the effectiveness of the proposed approach. MJMP consistently achieved higher energy savings than both the DCAbased baseline and the decomposition-based approach. Overall, the results demonstrate that explicitly accounting for mobility, resource mapping, and end-to-end scheduling together can provide substantial benefits for real-time VEC systems. Future work will investigate varying network conditions, multi-cell offloading and downloading, and multiple jobs per vehicle. Furthermore, the heuristic will also be improved to compute a schedule in a distributed setting, as there is no need to assign a priority to jobs that do not meet in the pipeline, this will also reduce the runtime.

References [1] L. Liu, C. Chen, Q. Pei, S. Maharjan, and Y. Zhang, “Vehicular edge computing and networking: A survey,” Mobile networks and applications, vol. 26, no. 3, pp. 1145–1168, 2021. [2] R. Meneguette, R. De Grande, J. Ueyama, G. P. R. Filho, and E. Madeira, “Vehicular edge computing: Architecture, resource management, security, and challenges,” ACM Computing Surveys (CSUR), vol. 55, no. 1, pp. 1–46, 2021. [3] C. Gao, N. Kumar, and A. Easwaran, “Energy-efficient real-time job mapping and resource management in mobile-edge computing,” in 2024 IEEE Real-Time Systems Symposium (RTSS). IEEE, 2024, pp. 15–28. [4] B. Ma, Z. Ren, W. Cheng, J. Wang, and W. Zhang, “Latencyconstrained multi-user efficient task scheduling in large-scale internet of vehicles,” IEEE Transactions on Mobile Computing, 2024. [5] X. Zhang, T. Lin, C.-K. Lin, Z. Chen, and H. Cheng, “Computational task offloading algorithm based on deep reinforcement learning and multi-task dependency,” Theoretical Computer Science, p. 114462, 2024. [6] Y. Xu, L. Chen, Z. Lu, X. Du, J. Wu, and P. C. K. Hung, “An adaptive mechanism for dynamically collaborative computing power and task scheduling in edge environment,” IEEE Internet of Things Journal, vol. 10, no. 4, pp. 3118–3129, 2023. [7] Y. Gao, J. Tao, H. Wang, Z. Wang, W. Sun, and C. Song, “Joint server deployment and task scheduling for the maximal profit in mobile edge computing,” IEEE Internet of Things Journal, 2023. [8] S. Abdi, M. Ashjaei, and S. Mubeen, “Task offloading in edgecloud computing using a q-learning algorithm,” in The International Conference on Cloud Computing and Services Science, CLOSER (2024), 2024. [9] Y. Sang, J. Wei, Z. Zhang, and B. Wang, “A mobility-aware task scheduling by hybrid pso and ga for mobile edge computing,” Cluster Computing, pp. 1–16, 2024. [10] M. Tiwari, I. Maity, and S. Misra, “Rate: Reliability-aware task service in fog-enabled iov environments,” IEEE Transactions on Cognitive Communications and Networking, 2024. [11] X. Huang and G. Huang, “Joint optimization of energy and task scheduling in wireless-powered irs-assisted mobile-edge computing systems,” IEEE Internet of Things Journal, vol. 10, no. 12, pp. 10 997–11 013, 2023. [12] L. Huang and Q. Yu, “Mobility-aware and energy-efficient offloading for mobile edge computing in cellular networks,” Ad Hoc Networks, vol. 158, p. 103472, 2024. [13] S. Pradhan, S. Tripathy, and R. Matam, “Towards optimal edge resource utilization: Predictive analytics and reinforcement learning for task offloading,” Internet of Things, p. 101147, 2024. [14] N. Chauhan and R. Agrawal, “A probabilistic deadline-aware application offloading in a multi-queueing fog system: A max entropy framework,” Journal of Grid Computing, vol. 22, no. 1, pp. 1–22, 2024. [15] W. Li, S. Li, H. Shi, W. Yan, and Y. Zhou, “Uav-enabled fair offloading for mec networks: a drl approach based on actor-critic parallel architecture,” Applied Intelligence, pp. 1–18, 2024. [16] H. A. Alameddine, S. Sharafeddine, S. Sebbah, S. Ayoubi, and C. Assi, “Dynamic task offloading and scheduling for lowlatency iot services in multi-access edge computing,” IEEE Journal on Selected Areas in Communications, vol. 37, no. 3, pp. 668–682, 2019. [17] X. Lai, T. Wu, C. Pan, L. Mai, and A. Nallanathan, “Shortpacket edge computing networks with execution uncertainty,” IEEE Transactions on Green Communications and Networking, 2024. [18] T. Zhu, T. Shi, J. Li, Z. Cai, and X. Zhou, “Task scheduling in deadline-aware mobile edge computing systems,” IEEE Internet of Things Journal, vol. 6, no. 3, pp. 4854–4866, 2019. [19] I. Sorkhoh, D. Ebrahimi, R. Atallah, and C. Assi, “Workload scheduling in vehicular networks with edge cloud capabilities,” IEEE Transactions on Vehicular Technology, vol. 68, no. 9, pp. 8472–8486, 2019.

[20] N. Kumar, C. Gao, and A. Easwaran, “Optimal fixed priority scheduling in multi-stage multi-resource distributed real-time systems,” in 2024 Design, Automation & Test in Europe Conference & Exhibition (DATE). IEEE, 2024, pp. 1–6. [21] N. C. Audsley, “Optimal priority assignment and feasibility of static priority tasks with arbitrary start times,” 1991. [22] P. Jayachandran and T. Abdelzaher, “Delay composition in preemptive and non-preemptive real-time pipelines,” Real-Time Systems, vol. 40, no. 3, pp. 290–320, 2008. [23] ——, “Transforming distributed acyclic systems into equivalent uniprocessors under preemptive and non-preemptive scheduling,” in 2008 Euromicro Conference on Real-Time Systems. IEEE, 2008, pp. 233–242. [24] J. C. Palencia and M. G. Harbour, “Offset-based response time analysis of distributed systems scheduled under edf,” in 15th Euromicro Conference on Real-Time Systems, 2003. Proceedings. IEEE, 2003, pp. 3–12. [25] S. Hong, T. Chantem, and X. S. Hu, “Meeting end-to-end deadlines through distributed local deadline assignments,” in 2011 IEEE 32nd Real-Time Systems Symposium. IEEE, 2011, pp. 183–192. [26] R. Bettati and J. W.-S. Liu, “End-to-end scheduling to meet deadlines in distributed systems.” in ICDCS. Citeseer, 1992, pp. 452–459. [27] R. I. Davis and A. Burns, “Priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems,” in 2009 30th IEEE Real-Time Systems Symposium. IEEE, 2009, pp. 398–409. [28] R. I. Davis, L. Cucu-Grosjean, M. Bertogna, and A. Burns, “A review of priority assignment in real-time systems,” Journal of systems architecture, vol. 65, pp. 64–82, 2016. [29] R. I. Davis and A. Burns, “A survey of hard real-time scheduling for multiprocessor systems,” ACM computing surveys (CSUR), vol. 43, no. 4, pp. 1–44, 2011.

Related documents

• Teknik DEVELOPMENT OF A SEMI-AUTONOMOUS HYBRID NAVIGATION SYSTEM FOR MILITARY RECONNAISSANCE OPERATIONS USING MULTI-CONSTELLATION GNSS AND EDGE COMPUTING: Multi-Constellation Implementation Study of GNSS and Raspberry Pi 5-Based Edge Computing#235435
• Internet of Things future in Edge Computing#761991
• GenioSim: A Novel Simulation Platform for Edge Computing over Optical Networks#175166
• EdgeDAE: Acceleration of Diffusion Action Experts for Real-Time Physical AI with Tiny VLAs on Edge FPGA-GPU Systems#1154934
• Entwine: Coordinating Tiled Computation and Fine-Grained Communication across GPUs#673468