As vehicles have become increasingly automated, novel vehicular applications have emerged to enhance the safety and security of the vehicles and improve user experience. This brings ever-increasing data and resource requirements for timely computation by the vehicle’s on-board computing systems. To meet these demands, prior work proposes deploying vehicular edge computing (VEC) resources in road-side units (RSUs) in the traffic infrastructure with which the vehicles can communicate and offload compute-intensive tasks. Due to the limited communication range of these RSUs, the communication link between the vehicles and the RSUs — and, therefore, the response times of the offloaded applications — are significantly impacted by vehicle mobility through road traffic. Existing task offloading strategies do not consider the influence of traffic lights on vehicular mobility while offloading workloads onto the RSUs. This causes deadline misses and quality-of-service (QoS) reduction for the offloaded tasks. In this article, we present a novel task model that captures time and location-specific requirements for vehicular applications. We then present a deadline-based strategy that incorporates traffic light data to opportunistically offload tasks. Our approach allows up to 33% more tasks to be offloaded onto RSUs compared with existing work without causing deadline misses, maximizing the resource utilization of RSUs.
1 Introduction
The presence of smart vehicles with varying levels of connectivity and autonomy is rapidly becoming prominent on today’s roads. Vehicles are now equipped with advanced sensing, communication, and computation capabilities as they transition from being human driven (Level 0) to fully autonomous (Level 5) as per vehicular automation standards [36]. These capabilities will enable advanced driving assistance (ADAS) applications that will help vehicles make precise driving maneuvers and enhance overall safety, security, and user experience in complex road traffic scenarios [42]. Examples of such ADAS applications include (but are not limited to) lane keeping assist (LKA), lane change assist (LCA) [8], and cooperative advanced cruise control (CACC) [30]. While the vehicles have dedicated on-board sensing and processing to support safety-critical driving applications, it is also necessary to support other data and computationally intensive vehicular applications that enhance passenger experience. Applications involving media-rich infotainment, augmented reality (AR)–based media streaming, collaborative data aggregation, and interactive user applications are resource intensive [16] and have timeliness and quality-of-service (QoS) requirements even though they may not be safety-critical applications.
Cloud servers provide additional storage and computational resources to satisfy these increasing demands. However, the latency of wireless channels for such long-range communications tends to be a bottleneck [23]. The upcoming vehicular edge computing (VEC) paradigm provides an attractive alternative to cloud computing solutions. Under the VEC framework, edge servers are deployed near the vehicles and provide additional compute and storage resources. Additionally, VEC relies on network technologies such as dedicated short-range communication (DSRC) and 5G-based cellular vehicle-to-everything (CV2X) connectivity that enable high-throughput short distance communication between vehicles and the edge servers deployed along the roadways [1]. Data and connectivity among the entities within the traffic ecosystem —such as roadside sensors, vehicles, and traffic lights —can now be leveraged to implement novel algorithms that enhance the overall QoS and performance of various automotive applications [15, 46]. Such localized data can be made available on an edge platform. Therefore, VEC is a promising approach to handle the data and computationally intensive vehicular tasks with soft real-time requirements.
In a typical VEC network, road-side units (RSUs; e.g., traffic lights, cameras, detectors) are equipped with additional storage and compute resources. Vehicles can communicate and offload workloads onto the edge-enabled RSUs via V2X communication with significantly reduced communication latency when they are within communication range of a nearby RSU. Recent studies are focused on finding appropriate RSU resources to opportunistically offload tasks to meet the timeliness and resource requirements as the vehicles drive in and out of RSU communication range [18, 47, 51, 52]. Figure 1 depicts a typical task-offloading scenario such that the timeliness requirements of the task are met. In Figure 1, as the vehicle travels along a road link, it communicates with the nearby RSUs to upload a task. The task is then processed at one of the RSUs and the results are downloaded back to the vehicle. As the vehicle travels, the traffic light status changes, which impacts the speed of the vehicle and, hence, the location where the task is uploaded to and downloaded from the RSUs. The timeline graph in Figure 1 depicts the total offload time, including processing time and communication delays, details of which are discussed in later sections.
Fig. 1.
Fig. 1. Offloading scenario of task \(\tau _{i}\) uploaded at \(RSU_{u}\), computed at \(RSU_{c}\) and then downloaded at \(RSU_{d}\), with completion time of the task as \(t^{ul}_{i} + \rho _{uc} + t^{c}_{i} + \rho _{cd} + t^{w}_{i} + t^{dl}_{i}\).
A vehicle can successfully communicate, exchange data and offload tasks with an RSU while it is within the communication range of the RSU. In dense traffic networks, the time during which the vehicles can maintain communication with a nearby RSU changes frequently. A vehicle cruising through a green light may spend very little time within the range of one RSU but can communicate for a significantly longer time with another RSU while waiting at a red traffic light. Therefore, traffic conditions and vehicular mobility significantly impact the communication link between vehicles and RSUs and, therefore, the choice of RSUs to offload the tasks.
In addition to influencing the communication between vehicles and RSUs, vehicular mobility and traffic conditions also affect the requirements of many novel vehicular applications [11, 14]. For example, consider a dynamic routing application on a vehicle that finds an optimized route to a preferred destination based on collaborative data from surrounding vehicles. If an optimal route for the upcoming intersection is to be calculated and the vehicle is waiting at a red traffic light, the routing task need not be completed until the light turns green and the vehicle starts moving to cross the intersection. Traditional VEC task models do not account for such tasks whose deadlines depend on traffic flow and traffic light data when the task arrives. To support emerging applications [46], we propose a comprehensive task model comprising tasks that have static deadlines, as in traditional task models, while other tasks have location- or distance-specific deadlines along with the computation requirements. Figure 2 shows an example in which light timings influence the vehicular mobility characteristics, which, in turn, affect the communication times and tasks with dynamic deadlines. As shown, consider a vehicle traveling through a road link devoid of traffic, controlled by a traffic light. If the traffic light is green, it will spend similar amounts of time within the communication range of each RSU along its way as it drives at a constant speed. However, if the traffic light is red, the same vehicle will spend a much longer time within the range of the RSUs closer to the traffic light as it slows down to come to a stop.
Fig. 2.
Fig. 2. Influence of traffic lights on dwell times: Vehicle spends significantly longer time within the range of \(RSU_{m}\) when the light is red (top) in comparison with a situation in which the light is green (bottom). \(\delta _{ij}\) is the dwell time of vehicle \(V_{i}\) in the communication range of \(RSU_{j}\).
Existing offloading strategies select RSUs based on an underlying goal of minimizing task computation [50], resource utilization [34], bandwidth usage [38], or access costs [26]. As vehicles enter a lane in a sequential manner and RSUs are only accessible once the vehicle is in communication range, greedy approaches offload the tasks for the earlier-arriving vehicles on the RSUs that are located closer to them when the tasks arrive even if they have a later deadline. This blocks the later-arriving tasks (and vehicles) from accessing these resources even if they have earlier deadlines. For example, in Figure 3, an earlier-arriving vehicle (\(V_{i}\), marked in red) ends up utilizing the first available resource (\(RSU_{1}\)) due to a greedy offloading mechanism even though its task, \(\tau _{i}\), has a later deadline. When a later-arriving vehicle (\(V_{i+1}\), marked in blue) has a more urgent task (\(\tau _{i+1}\)) to offload, the resources are blocked by \(\tau _{i}\), leading to \(\tau _{i+1}\) missing its deadline. Therefore, existing approaches fail to maximize the number of tasks that can be offloaded onto the edge.
Fig. 3.
Fig. 3. Offloading tasks without considering the traffic lights affecting vehicular mobility. Task \(\tau _{i+1}\) would miss its deadline; hence, the existing strategies would drop the task and choose not to be offloaded.
By offloading as many resource-intensive tasks with less stringent timing requirements onto RSUs, vehicles not only maximize resource utilization at RSUs, but also allow on-board processors to prioritize on time- and safety-critical applications. Since VEC tasks have soft real-time requirements, the system accrues minimal benefit in completing tasks well before the deadline. Missing the deadline, however, leads to reduced QoS. By using our deadline-based task-offloading strategy in which we offload tasks such that they complete closer to the deadline, we ensure that the offloaded tasks meet their deadlines and that more tasks can be offloaded onto the edge without blocking resources for later-arriving tasks.
To summarize, our contributions are as follows:
•
To combat the shortcomings of the existing VEC models that only consider tasks with static deadlines, we present a comprehensive model that consists of tasks with fixed time-based as well as dynamic distance-based deadlines based on traffic flow, traffic lights, and the location requirements of the task.
•
We incorporate traffic light timing data to calculate (i) the mobility characteristics and travel time for vehicles and (ii) timing requirements for tasks with dynamic distance-based deadlines.
•
We propose a task-offloading strategy that allocates RSUs to complete tasks as close to the deadlines as possible, thereby maximizing the tasks offloaded without violating the task deadlines.
•
We evaluate our proposed approach against existing offloading strategies using VISSIM [10], a microscopic traffic simulator.
1.1 Article Structure
The remainder of this article is divided into the following sections. Section 2 provides a survey of prior work in task-offloading techniques on the VEC platform. Section 3 presents our system model with details on the traffic infrastructure, task model, and assumptions in our communication framework. In Section 4, we provide details on our proposed deadline-based task offloading approach and the algorithm used to find appropriate computing resources to process the tasks. In Section 5, we evaluate the performance of our proposed approach when compared with other existing task-offloading algorithms. Section 6 contains concluding remarks and insights into future work.
2 Related Work
With increasing demands for performance, data- and compute-hungry processes on mobile devices induced breakthroughs in small-cell network, multi-antenna, and millimeter-wave communications to provide highly reliable and gigabit wireless access to next-generation systems [44]. Due to these advancements it became possible to utilize external network–based storage and compute resources to satisfy the demands. Mobile cloud computing (MCC) was a promising solution for offloading workloads from a plethora of connected devices. Many existing works have focused on tackling various connectivity, resource, mobility, and network latency constraints to optimize the utilization of MCC [4, 21, 37].
As connectivity penetrated vehicles and traffic infrastructure, vehicular cloud computing (VCC) became prevalent to enhance safety, security, and user experience for vehicular application-specific workloads [25]. Various architectures were proposed to enable cloud-based computation for vehicular applications [3, 19]. Efforts have also been made to make VCC more efficient via optimized resource allocation techniques [48], and more secure [40] and more energy-efficient [43] to allow its widespread adoption. However, many emerging vehicular applications require large amounts of data to be processed with strict response times and network bandwidth constraints. To meet these demands, the vehicular edge computing (VEC) paradigm was introduced [41], in which storage and compute nodes were brought closer to the proximity of the end user, greatly reducing the network latency [7] and energy consumption [35].
Recent studies have proposed various task-offloading mechanisms to offload more tasks from the vehicle onto the edge platform [13, 41]. In addition to offloading tasks, many researchers have also provided resource allocation mechanisms to maximize the utilization of the limited compute resources available at the edge [9, 49]. The authors of [41] propose an offloading mechanism for complex vehicular tasks with dependencies. In [26], a matching-based approach was proposed to jointly offload vehicular tasks and allocate resources on the edge. While most of these techniques focus on offloading tasks and utilizing the edge resources deployed along the RSUs of the traffic infrastructure, many researchers also propose a vehicular fog computing (VFC) architecture in which the resources available on other vehicles driving in the vicinity or parked vehicles are utilized to meet demands. Solutions proposed for utilizing the VFC framework are out of the scope of our work; interested readers can refer to existing literature [22, 27]. None of these proposed solutions, however, considers the mobility constraints in a vehicular environment.
Vehicular mobility can significantly impact resource utilization as well as task allocation onto the edge. Novel task offloading and resource allocation mechanisms have been proposed that incorporate a driving model for vehicles [2, 5, 52]. However, the driving models used in these work are simplistic and do not accurately represent vehicular mobility in urban driving conditions.
In a highly dynamic urban environment, vehicles’ mobility is heavily affected by speed limits, traffic density, traffic lights, and more. A holistic solution is required that is applicable in varying traffic conditions by incorporating mobility constraints to accurately offload tasks and allocate resources. To that end, in our proposed work, we overcome the shortcomings of existing task offloading strategies by using a robust driving model that utilizes traffic light timings to estimate a vehicle’s mobility. Additionally, we propose a task model that closely represents vehicular workloads and provide a task-offloading strategy that meets the timeliness constraints of the tasks.
3 System Model
We now look at the VEC system model and its individual components pertaining to traffic infrastructure, vehicular maneuverability, edge computing tasks, and the VEC communication framework.
3.1 Traffic Infrastructure
We represent a single road link that connects two consecutive intersections as link L. This link L has length \(d_{L}\) with a posted speed limit of \(\nu ^{lim}\) for traffic flowing along link L to approach an intersection within an urban traffic network. Link L can have one or more lanes \(\lbrace l_1, \ldots , l_k\rbrace\), where each lane \(l_{i}\) is individually controlled using a traffic light (\(s_{i}\)) located downstream of the traffic flow. The traffic lights follow a cycle of green-yellow-red lights and are enabled with edge connectivity, resembling a traffic light with a fixed cycle time or a state-of-the-art traffic controller for which timings are known for a fixed prediction horizon [31]. The traffic lights have connectivity to broadcast traffic light data to the connected infrastructure. This traffic light data consists of its current state (\(\psi _{s_{i}} = \lbrace red, green, yellow\rbrace\)), remaining time in current state (\(t^{rem}_{s_{i}}\)), maximum red (\(t^{r}_{s_{i}}\)), green (\(t^{g}_{s_{i}}\)) and yellow phase time (\(t^{y}_{s_{i}}\)), and the cycle time (\(t^{cycle}_{s_{i}} = t^{r}_{s_{i}} + t^{g}_{s_{i}}+t^{y}_{s_{i}}\)).
3.2 VEC Task Model
As introduced in Section 1, existing task models consider only those tasks with fixed time-based deadlines. In this work, in addition to tasks with static deadlines, we introduce dynamic distance-based tasks that represent novel VEC applications and workloads. Such tasks have dynamic deadlines based on distance-specific requirements specifying that the tasks need to be completed before the vehicle has travelled a certain distance from the time the task arrives. Based on traffic flow, lights status, and vehicular maneuvering characteristics, the time requirement for such tasks changes dynamically.
We therefore consider a task model in which a task can be either of the following:
(1)
Regular task: Similar to prior methodologies, such a task has a fixed deadline based on a time before which the task must be executed.
(2)
Distance-based task: Such a task has a deadline based on a distance before which the task must be executed.
Any task \(\tau _{i}\) originating from vehicle \(V_{i}\) has an arrival time (\(a_{i}\)), upload size (\(\sigma ^{ul}_{i}\) Mb), computational requirement (\(C_{i}\) clock cycles), download size (\(\sigma ^{dl}_{i}\) Mb) and a deadline (\(d_{i}\)). Note that \(d_{i} = d^{x}_{i}\) or \(d_{i} = d^{t}_{i}\) depending on whether it is a distance-based task or regular task, respectively. Therefore, \(\tau _{i}\) is represented as a 5-tuple \(\tau _{i} = (a_{i}, \sigma ^{ul}_{i}, C_{i}, \sigma ^{dl}_{i}, d_{i})\).
A distance-based deadline can be translated into a regular time-based deadline based on the vehicle’s maneuvering capabilities. When the same distance-based task is spawned from two different vehicles, the task spawned from a slower-moving vehicle that needs to go through multiple red lights will have a later time-based deadline compared with the task spawned from a faster moving vehicle that always gets a green signal at the traffic lights. Note that our model assumes that all offloaded tasks are independent tasks. In the case of tasks with dependencies, our model can be utilized by decomposing interdependent tasks into multiple independent subtasks with local deadline assignments [29]. Further, the tasks are assumed to have negligible or bounded jitter and additional buffers can be added to task execution times to account for it. However, the analysis of our model with such tasks is beyond the scope of this discussion and is left for future work.
3.3 VEC Infrastructure
A typical VEC framework consists of (i) a main base station (MBS), (ii) edge-enabled RSUs, and (iii) connected vehicles requiring edge resources.
An MBS communicates wirelessly with all vehicles via a high-throughput wired connectivity with edge-enabled RSUs, within its communication range. MBSs have a larger communication range than other edge-enabled RSUs, as they cover multiple intersections in a traffic network. RSUs comprise infrastructure (e.g., traffic lights, sensors, cameras) that are equipped with additional compute, storage, and communication resources. RSUs communicate with vehicles within their range via short-range wireless connectivity (fe.g., 5G-CV2X). All RSUs are connected via a wired backhaul network and are distributed along the roadside such that the entire road link is covered without any blind spots. Additionally, in our model, the RSUs do not share the processing resources. Therefore, tasks cannot be partially executed on different RSUs. Finally, the vehicles requiring edge resources communicate with the MBS and the RSUs to offload VEC tasks. A detailed description of such a framework can be found in [25].
Edge Infrastructure: The road link L will have RSUs deployed alongside to cover the entirety of the link L, including all of its lanes. Further, the RSUs are located such that there is no overlap in the communication radius of two contiguous RSUs. Any \(i^{th}\) RSU along the link L has a fixed communication radius (\(r_{i}\)), number of parallel processors (\(p_{i}\)), and a clock speed (\(z_{i}\)). The RSUs have strict power consumption requirements as they are deployed at remote locations due to which the transmission power is limited [20]. The communication radius is therefore determined using Friis’s equation [39] to ensure a stable link between the vehicles and the RSU. The number of processors and the clock speeds of each processor at an RSU are also chosen based on the power consumption requirements and edge resource demands. Optimal placement of RSUs and edge services is an ongoing research problem [17] and is beyond the scope of this work. In short, our system considers m RSUs (i.e., \(RSU_{1}, \ldots , RSU_{m}\)), which are deployed alongside link L of length \(d_{L}\) such that \(\sum _{i=1}^{m}2r_{i} = d_{L}\) (since no overlap in RSU range) where \(r_{i}\) is the communication range radius of RSU i.
Channel Bandwidth and Connectivity: The VEC framework consists of (i) a wired optical fiber-based backhaul network connecting all of the RSUs and the MBS, (ii) a low-latency short-range wireless network between the vehicles and RSUs, and (iii) a wireless long-range connectivity between the vehicles and MBS.
Based on the upload (\(\sigma ^{ul}_{i}\)) and download (\(\sigma ^{dl}_{i}\)) size of the task, there is a corresponding upload (\(t^{ul}_{ij}\)) and download (\(t^{dl}_{ij}\)) time based on RSU j’s channel characteristics. For simplicity, we consider that all RSUs have similar noise conditions and transmit power, and hence a fixed and equal \(\eta\). We also assume that the transmit power is adjusted such that the signal-to-noise ratio remains constant within the short range of communication of an RSU. However, in a more comprehensive setting that is significantly impacted by noise with varying channel conditions, existing formulations [33] can be used to determine the data transmission rate \(\eta\) between the communicating entities.
Alternately, the wired backhaul network is a high-throughput channel with minimal latency. Due to high bit rates, for smaller workloads, the relay time (\(\rho _{jk}\)) between two RSUs, \(RSU_{j}\) and \(RSU_{k}\), depends on the distance between the RSUs. It can be defined as
where \(c_{bh}\) is the minimum transmission relay time between two consecutive RSUs [13] and \(\eta _{bh}\) is the data rate for backhaul network.
3.4 Vehicle Maneuver Model
We consider that all vehicles within our system are fully connected and have automation capabilities of level 3 and beyond as per automation standards [36]. Such vehicles can drive and perform maneuvers in an automated manner with some (level 3) to no (level 5) intervention from the human driver. Such vehicles have already started operating on today’s roads [12] and have an increased demand for edge resources as they need the on-board processors for performing real-time driving maneuvers. These vehicles deploy an advanced driving assistance and maneuvering model to establish real-time control of the vehicle and navigate it through the traffic network. The vehicles also broadcast body safety messages (BSMs) to the MBS and other infrastructure in the vicinity. BSMs are safety messages that the connected vehicles broadcast periodically to inform the infrastructure of their driving characteristics.
We denote the \(i^{th}\) vehicle in our system by \(V_{i}\). In our system, \(V_{i}\) will enter a lane within L driving at a speed of \(\nu _{i}\) and perform one of the following driving maneuvers at any point in time:
(1)
Constant speed:\(V_{i}\) maintains a constant speed of (i) \(\nu _{i} = \nu ^{lim}\) if there is no leading vehicle in front, (ii) \(\nu _{i} = \nu _{i-1}\) in the presence of a leading vehicle \(V_{i-1}\), or (iii) \(\nu _{i} = 0\) if the \(V_{i}\) is stationary at the traffic light.
(2)
Comfortable acceleration:\(V_{i}\) may need to accelerate due to a light turning green or a leading vehicle accelerating, and it does so at a constant deceleration rate of a.
(3)
Comfortable deceleration:\(V_{i}\) may need to slow down due to a red light or a slowly moving leading vehicle and it does so at a constant deceleration rate of \(-b\).
Similar driving maneuvering mechanisms were used in closely related work [26, 52] for task assignments in urban scenarios, but without considering traffic lights.
The acceleration and deceleration rates are chosen with the comfort of the passengers within the vehicles as well as the surrounding pedestrians and vehicles in mind [6]. The vehicles also maintain a safe distance of \(x^{safe}_{i} = h\nu _{i} + x_{safe}\) from their leading vehicle using CACC techniques, where h denotes a constant time headway, \(\nu _{i}\) is the driving speed of \(V_{i}\), and \(x_{safe}\) is the minimum safety gap at standstill [45]. For consistency, we assume that all vehicles use the same maneuvering model to allow for a realistic simulation setup. However, it should be noted that our proposed offloading strategy is model agnostic.
Upon entering the link L, a vehicle communicates its location and speed via BSMs to the MBS and requests for RSU allocation to upload, compute, and download a task. In our model, we consider worst-case task-offloading demands in which every vehicle, upon entering a link, will always have a task to offload with varying timing, computation, and location requirements.
4 Deadline-based Task Offloading
This section describes our proposed task-offloading strategy for VEC systems. We first provide highlights of the VEC task-offloading process.
4.1 VEC Task Offloading
Based on the system model described so far, a typical task-offloading process from a vehicle onto the edge is as follows:
(1)
A vehicle requests the MBS to offload and compute any VEC tasks onto the RSU resources.
(2)
The offloading request also consists of the task requirements, such as the arrival time, computation requirement, deadline, and upload and download size of the data, which is communicated via the on-board cellular network capabilities.
(3)
Optionally, the MBS checks whether the task can be completed before its deadline if offloaded onto the processing units available at the RSUs, in a deadline-aware approach.
(4)
If the task requirements are feasible, the MBS deploys a task-offloading strategy to assign the requesting vehicle to RSUs where the task can be uploaded, computed, and downloaded and accordingly reserves processing units to perform the computations.
(5)
Upon entering the communication range of the assigned RSUs, the vehicle communicates with the RSUs using short-range low-latency communication channels to upload and subsequently download the task and its results back onto the vehicle.
Therefore, the total completion time of a task (as shown in Figure 1) depends on (i) task upload time (\(\tau _{i}^{ul}\)); (ii) task relay time (\(\rho _{uc}\)), that is, the time taken to relay the task data from the RSU where the task was uploaded to the RSU where the task is to be computed; (iii) task compute time (\(\tau _{i}^{c}\)); (iv) task relay time (\(\rho _{cd}\)) from RSU where the task is computed to the RSU from where the task will be downloaded; (v) wait time (\(\tau _{i}^{w}\)) for the vehicle to enter the communication radius of the RSU where the task is to be downloaded from; and, finally, (vi) task download time (\(\tau _{i}^{dl}\)). Figure 1 depicts a typical offloading scenario of task \(\tau _{i}\) with an arrival time of \(a_{i}\) and a deadline of \(d_{i}\).
Selection of RSUs and Dwell Time Estimation: The total completion time of a task must not exceed its deadline to ensure that it meets the deadline. Therefore, the MBS must select appropriate RSUs to upload (\(RSU_{u}\)), compute (\(RSU_{c}\)), and download (\(RSU_{d}\)) the task so that the total completion time meets its deadline constraint. To avoid communication interrupts and retries, the vehicle requesting the VEC resource must remain within the range of \(RSU_{u}\) and \(RSU_{d}\) for a duration that is at least equal to the upload and download time of the task. This time duration is known as dwell time, which indicates the approximate amount of time that a vehicle spends within the communication range of each RSU. Dwell time for vehicle \(V_{i}\) within the communication range of \(RSU_{j}\) is denoted by \(\delta _{ij}, \forall j = 1,\ldots ,m\). The MBS derives the dwell times based on the vehicle’s mobility characteristics.
Our deadline-based offloading strategy consists of offloading tasks such that they complete as close to the deadline as possible by using the following example.
4.2 Motivating Example
Consider a VEC system described in Section 3. m RSUs are deployed along the link L of length \(d_{L}\), of which \(RSU_{2},\ldots ,RSU_{m-1}\) are occupied by other compute-intensive tasks. The only two resources available for offloading tasks are \(RSU_{1}\), located at the entry of link L, and \(RSU_{m}\), located at the end of link L near the traffic light \(s_{L}\). Vehicle \(V_{i}\) enters link L at time \(t_{0}\) and requests to offload \(\tau _{i}\), followed by \(V_{i+1}\) entering link L at time \(t_{1}\) = \(t_{0}+1\) requesting to offload \(\tau _{i+1}\). \(\tau _{i}\) is a distance-based task such that it must complete before \(V_{i}\) crosses the traffic light \(s_{L}\) and, therefore, exits \(RSU_{m}\)’s range. Alternately, \(\tau _{i+1}\) is a time-sensitive task with a deadline of 3 seconds with reference to its arrival time. The characteristics of both tasks are as follows: \(t^{ul}_{i}\) = 0.2 s, \(t^{c}_{i}\) = 3 s, and \(t^{dl}_{i}\) = 0.2 s, and \(t^{ul}_{i+1}\) = 0.1 s, \(t^{c}_{i+1}\) = 2 s, and \(t^{dl}_{i+1}\) = 0.1 s. Both vehicles enter the link driving at the speed limit (\(\nu _{i} = \nu _{i+1} = \nu ^{lim}\)). The travel time between \(RSU_{1}\) and \(RSU_{m}\) is 25 seconds when driving at the speed limit. Dwell times for vehicles \(V_{i}\) and \(V_{i+1}\) within the range of RSUs 1 and m are \(\delta _{i1}\) = \(\delta _{im}\) = \(\delta _{(i+1)1}\) = \(\delta _{(i+1)m}\) = 3.7 seconds.
4.2.1 Offloading with Existing Approach.
As shown in Figure 3, an existing approach such as that described in [26] offloads tasks to minimize the total completion time but does not account for traffic lights. Since the total completion time for \(\tau _{i}\) if uploaded, computed, and downloaded at \(RSU_{1}\) is 3.4 seconds (as per task characteristics), which is less than \(\delta _{i1}\), \(RSU_{1}\) will be selected for upload, compute, and download. When \(\tau _{i+1}\) arrives, the only available RSU to offload is \(RSU_{m}\). Offloading \(\tau _{i+1}\) onto \(RSU_{m}\) requires \(V_{i+1}\) to travel for 25 seconds, which adds to the completion time of the task. This leads to a deadline miss for \(\tau _{i+1}\). Therefore, with an existing strategy, only \(\tau _{i}\) task will be offloaded onto the RSU.
4.2.2 Offloading with Deadline-Based Approach.
When \(\tau _{i}\) arrives at \(t_{0}\), \(\psi _{s_{i}} = red\) and has a remaining time of 45 seconds. Since the travel time from \(RSU_{1}\) to \(RSU_{m}\) is 25 seconds, the vehicle \(V_{i}\) will travel through the link and wait at the traffic light until it turns green. Since \(\tau _{i}\) is a distance-based task with the deadline coinciding to when it crosses the link and the vehicle will take 45 seconds (until the light turns green) to cross the link, the estimated deadline for the task \(\tau _{i}\) will be 45 seconds. As per our strategy, the task must be completed closer to the deadline. Therefore, \(RSU_{m}\) will be selected for offloading the task \(\tau _{i}\), even though uploading, computing, and downloading \(\tau _{i}\) onto \(RSU_{m}\) incurs a higher completion time (28.4 seconds, including travel time). Note that \(\tau _{i}\) still meets its deadline. When \(\tau _{i+1}\) arrives at \(t_{1}\), \(RSU_{1}\) will be available. Hence, \(\tau _{i+1}\) will be uploaded, computed, and downloaded on \(RSU_{1}\). Therefore, with our deadline-based, just-in-time task-offloading strategy, (i) we maximize the number of tasks that can be offloaded onto the RSUs and (ii) meet deadlines for all offloaded tasks, see Figure 4.
Fig. 4.
Fig. 4. Task offloading with mobility characteristics using traffic light data. Both tasks meet their respective deadlines.
In a typical urban traffic environment with multiple traffic intersections, traffic conditions evolve continuously. In a connected environment, real-time traffic data are made available to monitor and predict as vehicular traffic evolves. We have shown in Section 3 that in VEC applications, tasks have a strong dependency on vehicle maneuvers. By offloading tasks closer to the deadline, it allows making scheduling decisions based on real-time traffic conditions, which minimizes re-computation of tasks in case the vehicle’s state changes after uploading the task. Additionally, since most VEC tasks utilize data from vehicles and their surroundings delaying processing closer to the deadline enables utilization of the most recent data. Furthermore, prior works that utilize just-in-time scheduling in IoT applications have shown better bandwidth and resource utilization, with increased QoS [28]. When network conditions are known, approaches with just-in-time scheduling have shown reduced deadline miss ratio and packet drop ratio [24]. Network routing and vehicular traffic routing draw many similarities in their functions [47], which motivates us to explore our proposed deadline-based task-offloading approach.
4.3 Deadline-Based Approach
Elaborating on the motivation, we propose a deadline-based task-offloading strategy that (i) incorporates traffic light data to estimate the dwell time for the vehicles within each RSU’s range; (ii) ensures that all task requirements, including distance-based deadlines, are met for offloaded tasks; and (iii) offloads tasks such that they complete closer to the deadline, thereby maximizing the number of tasks being offloaded.
We break down the task offloading strategy deployed over the MBS) into three phases: (i) estimating the mobility and timing characteristics of the vehicles, (ii) calculating the dwell times based on the mobility characteristics, and (iii) finding the appropriate RSUs to meet the task deadlines and offload tasks closer to the deadline.
4.3.1 Estimating Mobility Characteristics.
We consider that link L consists of a single lane controlled by a traffic light s. However, our model can be extended to multiple lanes and traffic lights. The MBS acquires the traffic light data consisting of its current state (\(\psi _{s}\)), remaining time in current state (\(t^{rem}_{s}\)), and maximum times for green, yellow, and red phases, that is, \(t^{g}_{s}\), \(t^{y}_{s}\), and \(t^{r}_{s}\), respectively. Based on the driving model and its maneuvers — that is, (i) constant speed, (ii) accelerating at the rate of \(a\ m/s^{2}\), or (iii) decelerating at a rate of \(-b\ m/s^{2}\) — the MBS determines the trajectory of vehicle \(V_{i}\) while driving through link L of length \(d_{L}\) with a speed limit of \(\nu ^{lim}\). The rate of change in speed is denoted by \(\alpha \in \lbrace a, -b\rbrace\) based on the maneuver. To determine the distance and timings within each driving maneuver, the MBS utilizes commonly known kinematics Equations (2), (3), and (4), where \(\nu _{0}, t_{0}\), and \(x_{0}\) determine the initial speed, time, and position at the beginning of a maneuver while \(\nu _{f}, t_{f}\), and \(x_{f}\) determine the speed, time, and position at the end of a maneuver.
We then determine the safe stopping distance (\(x^{stop}_{i}\)), which denotes the distance required for vehicle \(V_{i}\) to come to a complete stop from driving at the speed limit \(\nu ^{lim}\) with a deceleration of \(-b\) (Equation (5)). \(t^{stop}_{i}\) denotes the time spent in traveling \(x^{stop}_{i}\) distance (Equation (6)).
In a typical traffic infrastructure, the yellow light time \(t^{y}_{s}\) is tuned such that \(t^{y}_{s} = t^{stop}_{i}\), which allows vehicles to safely decelerate and come to a halt upon encountering a traffic light. Any vehicle that is more than \(x^{stop}_{i}\) distance away from the traffic light will consider the yellow phase as red and would decelerate to come to a stop. Alternately, vehicles less than \(x^{stop}_{i}\) distance away from the traffic light will perceive the yellow phase as a green light and would continue driving at their current speed to avoid sudden uncomfortable deceleration and/or acceleration. Therefore, to avoid ambiguity in formulation, a yellow phase of the traffic light is considered a part of the green phase in our formulation.
A vehicle’s mobility in a single lane link will be influenced only by the traffic light or another leading vehicle in the lane. To simplify the formulation of the mobility characteristics, we first consider the case in which a vehicle enters an empty link with no vehicles in front and, therefore, its maneuvering decision is solely dependent on the traffic light timings.
Case 1: A vehicle enters an empty link controlled by a traffic light. Based on the traffic light status and timings acquired by the MBS upon the arrival of the vehicle \(V_{i}\), we define Property 1.
Property 1 (Case 1).
A vehicle \(V_{i}\) entering an empty link L of length \(d_{L}\) with no vehicles in front that has a safe stopping distance and corresponding time of \(x^{stop}_{i}\) and \(t^{stop}_{i}\), respectively, will drive at the speed limit \(\nu ^{lim}\) until the vehicle is \(x^{stop}_{i}\) distance and correspondingly \(t^{stop}_{i}\) time away from the traffic light, irrespective of the traffic light state and timings.
Based on Property 1, we calculate the distance \(x^{const}_{i}\) and the corresponding time \(t^{const}_{i}\) for which the vehicle drives at the speed limit in a link L of length \(d_{L}\) with traffic lights located at the end of the link using Equations (7) and (8).
Based on the traffic light state and timings, the vehicle will Case 1(a), drive through the entire link at the speed limit; Case 1(b), drive at the speed limit until it encounters a red traffic light when it decelerates to a halt; or Case 1(c), drive at the speed limit until it encounters a red light to decelerate and accelerate again without coming to a halt because of the light changing to green. We now define the conditions for the traffic light timings and the distance traveled based on which the vehicle will acquire one of the driving characteristics using Lemmas 4.1, 4.2, and 4.3. The proof for Lemma 4.1 and 4.2 can be derived in a similar manner as Lemma 4.3.
Lemma 4.1 (Case 1(a): The Vehicle Drives through the Link at the Speed Limit).
A vehicle \(V_{i}\) entering an empty link L of length \(d_L\) with a traffic light s and bound by the acceleration and deceleration rate of a and \(-b,\) respectively, will traverse the entire link L at the speed of \(\nu ^{lim}\) if one of the following conditions are satisfied: (i) \(\psi _{s} = red\) and \(t^{rem}_{s} \le t^{const}_{i}\) or (ii) \(\psi _{s} = green\) and \(t^{rem}_{s} \gt t^{const}_{i}\). Here, \(\psi _{s}\) and \(t^{rem}_{s}\) are the light state and remaining time in current state of traffic light s, and \(t^{const}_{i}\) is the time for which \(V_{i}\) drives at a constant speed before reaching the safe stopping distance from the traffic light.
Lemma 4.2 (Case 1(b): The Vehicle Comes to a Halt at the Traffic Light).
A vehicle \(V_{i}\) entering an empty link L of length \(d_L\) with a traffic light s and bound by the acceleration and deceleration rate of a and \(-b,\) respectively, will come to a complete stop at the traffic light if one of the following conditions are satisfied: (i) \(\psi _{s} = red\) and \(t^{rem}_{s} \gt t^{const}_{i} + t^{stop}_{i}\) or (ii) \(\psi _{s} = green\) and \(t^{rem}_{s} \le t^{const}_{i}\). Here, \(\psi _{s}\) and \(t^{rem}_{s}\) denote the light state and remaining time in current state of traffic light s, \(t^{stop}_{i}\) denotes the duration needed for \(V_{i}\) to come to a complete stop at the traffic light, and \(t^{const}_{i}\) denotes the time for which \(V_{i}\) drives at a constant speed before decelerating at the traffic light.
Lemma 4.3 (Case 1(c): Vehicle Initially Decelerates, then Accelerates without Coming to a Complete Stop).
A vehicle \(V_{i}\) entering an empty link L of length \(d_L\) with a traffic light s and bound by the acceleration and deceleration rate of a and \(-b,\) respectively, will initially decelerate for \(t^{dec}_{i}\) time and then accelerate for \(t^{acc}_{i}\) time to cross the traffic light without coming to a halt if \(\psi _{s} = red\) and \(t^{const}_{i} \lt t^{rem}_{s} \lt t^{const}_{i} + t^{stop}_{i}\). Here, \(\psi _{s}\) and \(t^{rem}_{s}\) denote the light state and remaining time in current state of traffic light s, \(t^{stop}_{i}\) denotes the duration needed for \(V_{i}\) to come to a complete stop at the traffic light, and \(t^{const}_{i}\) denotes the time for which \(V_{i}\) drives at a constant speed before decelerating at the traffic light.
Proof.
Upon \(V_{i}\)’s arrival, \(\psi _{s} = red\) and \(t^{rem}_{s}\) is the time after which the light turns green. If \(t^{rem}_{s} \gt t^{const}_{i}\), then the vehicle starts to decelerate at the red light when it is \(x^{stop}_{i}\) distance away from the traffic light. However, if \(t^{rem}_{s} \lt t^{const}_{i} + t^{stop}_{i}\), then the traffic light will turn green before the vehicle comes to a complete stop and starts accelerating. Therefore, the vehicle only decelerates for \(t^{dec}_{i} = t^{rem}_{s} - t^{const}_{i}\) time. As the light turns green, the vehicle starts accelerating at the rate of a. The speed achieved after deceleration is denoted by \(\nu ^{dec}_{i} = \nu ^{lim} - t^{dec}_{i} \cdot b\) (Equation (2)). The distance travelled during deceleration is given by \(x^{dec}_{i} = (\nu ^{dec}_{i})^2 - (\nu ^{lim})^2/(-2b)\) (Equation (4)). Now, the vehicle will continue accelerating until either it reaches maximum speed limit, that is, for \(t^{acc}_{i} = (\nu ^{lim} - \nu ^{dec}_{i})/a\) duration, or crosses the traffic light, that is, upon traveling \(x^{acc}_{i} = d_{L} - x^{const}_{i} - x^{dec}_{i}\), achieving a speed of \(\nu ^{acc}_{i} = \sqrt {(\nu ^{dec}_{i})^2 +2\cdot a\cdot x^{acc}_{i}}\) (Equation (4)) and the corresponding time will be \(t^{acc}_{i} = (\nu ^{acc}_{i} - \nu ^{dec}_{i})/a\) (Equation (2)), whichever is shorter.
Therefore, vehicle \(V_{i}\) drives at the speed limit for \(t^{const}_{i}\) time, then decelerating for \(t^{dec}_{i}=t^{rem}_{s} - t^{const}_{i}\) time followed by acceleration for \(t^{acc}_{i} = \min ((\nu ^{lim} - \nu ^{dec}_{i})/a, (\nu ^{acc}_{i} - \nu ^{dec}_{i})/a)\) time. □
Before discussing Case 2, in which the vehicle’s mobility is also influenced by the leading vehicle in front, we present the algorithm used to estimate the dwell times in a scenario such as Case 1 in which a vehicle enters an empty link. We describe the Algorithm 4.1 that the MBS will utilize to calculate the mobility characteristics of the vehicles and then assign dwell times for each RSU. The MBS also finds the time-based deadline for the traffic-dependent tasks with location requirements, based on the derived mobility characteristics of the vehicles.
4.3.2 Dwell Time Assignment Algorithm.
The MBS takes (i) traffic light data from traffic light s, that is, current state (\(\psi _{s}\)), remaining time in current state (\(t^{rem}_{s}\)), maximum red phase time (\(t^{r}_{s}\)), and maximum green phase time (\(t^{g}_{s}\)); (ii) vehicle and link data, that is, speed limit (\(\nu ^{lim}\)) and length (\(d_{L}\)) of link L, index i for vehicle \(V_{i}\), and location-based deadline \(d^{x}_{i}\) depending on the task to be offloaded by \(V_{i}\); and (iii) RSU information, including the number of RSUs (m) and the communication radii of all m RSUs (\(r_{j}, j=1,\ldots ,m\)). We consider all RSUs to have equal communication radii; therefore, \(r_{j} = r, \forall j\in 1,\ldots , m\). Using Algorithm 4.1, the MBS then calculates the dwell times \(\delta _{ij}, \forall j=1,\ldots ,m\) for vehicle \(V_{i}\) in all m RSUs. It also finds the time at which the location-based deadline will be met (\(d^{t}_{i}\)), the RSU (\(RSU_{end}\)) where the vehicle will be located when its task meets the deadline, and the time duration \(t^{end}_{i}\) within the range of \(RSU_{end}\) left before the deadline is met.
When vehicle \(V_{i}\) enters the link L and requests to offload \(\tau _{i}\), the MBS receives the relevant data from the infrastructure (Lines 1–3). The MBS is aware of the driving controller on \(V_{i}\) and hence \(t_{step}\), which determines the time granularity at which the control decisions are taken by the driving controllers (Line 4). The safe stopping distance, the distance driven at speed limit, and their corresponding times are calculated using Equations (5), (7), (6), and (8) (Line 6). Then, until the vehicle is estimated to cross the traffic light (Line 7), the MBS, using the driving maneuver model, decides whether to perform a constant speed, deceleration, or acceleration maneuver (Lines 8–15) and then calculates the corresponding acceleration, speed, and position for the next time step (Line 16). During the entire calculation process, the MBS also accumulates the time (\(T_{\delta }\)), and assigns the dwell time \(\delta _{ij}\) for \(RSU_{j}\) when the calculated position exceeds the coverage boundary of an RSU, after which \(T_{\delta }\) is reset (Lines 17–19). During the calculation process, when the MBS encounters that the estimated position equals the distance-based deadline or time duration equals the time-based deadline, the corresponding time \(T_{i}\) is assigned as the time-based deadline of the task, and the corresponding \(RSU_{end}\) and the duration within the range of \(RSU_{end}\) before the deadline is met are noted for RSU allocation (Lines 20 and 21). As the calculated driving time and distance satisfies Property 1(Line 22), it checks the traffic light state and timings to find which conditions are met as per Lemmas 4.1, 4.2, and 4.3(Lines 23–34). Based on the condition, the MBS then selects the appropriate driving maneuver (\(flag_{s}\)) influenced by the traffic light s and also sets the time check points, \(t^{stop}_{i}, t^{dec}_{i},t^{acc}_{i}\), and \(t^{w}_{i}\) when the MBS must change the maneuvering calculations (Lines 35–43). The chosen maneuver \(flag_{s}\) is then selected as an \(action\) for the next iteration. Calculations for a vehicle \(V_{i}\) end when its calculated position exceeds the length of the link. The algorithm then provides the dwell times of vehicle \(V_{i}\) in every RSU along the link as an output.
Now, let us consider a more complex situation in which the link is non-empty and there may be leading vehicles that will influence vehicle \(V_{i}\)’s mobility.
Case 2: A vehicle enters a non-empty link with existing vehicle(s) and is controlled by a traffic light. We now consider a situation in which there will be existing vehicles in the link that vehicle \(V_{i}\) enters. We refer to a vehicle immediately in front of \(V_{i}\), that is, \(V_{i-1}\) as lead vehicle, and the vehicle under consideration, that is, \(V_{i}\) as ego vehicle. Based on the location of the lead vehicle \(V_{i-1}\), it may or may not affect the mobility characteristics of the ego vehicle \(V_{i}\). We highlight that an ego vehicle maintains a safety distance of \(x^{safe}_{i} = h\nu _{i} + x_{safe}\) with its leading vehicle to enable emergency braking and safe traffic movements, where \(\nu _{i}\) is the speed of the ego vehicle, k is a safety constant and \(x_{safe}\) is the minimum distance between two vehicles at standstill. We now define the following Property 2.
Property 2 (Case 2).
An ego vehicle \(V_{i}\) entering a non-empty link L of length \(d_{L}\) has at least one vehicle \(V_{i-1}\) between itself and the traffic light s at the end of the link L. \(V_{i}\) has a safe stopping distance and time of \(x^{stop}_{i}\) and \(t^{stop}_{i}\), respectively, and a safety gap of \(x^{safe}_{i} = h\nu _{i} + x_{safe}\) from the leading vehicle. In this case, the ego vehicle will drive at a constant speed of \(\nu ^{lim}\) until either of these conditions is met: (i) the ego vehicle is \(x^{safe}_{i}\) distance behind the lead vehicle \(V_{i-1}\) or (ii) the ego vehicle is within \(x^{stop}_{i}\) distance and, correspondingly, \(t^{stop}_{i}\) time away from the traffic light irrespective of the traffic light state and timings.
While driving, if the ego vehicle satisfies condition (i), it starts following the lead vehicle such that \(x^{safe}_{i}\) distance is always maintained. While following the lead vehicle, if condition (ii) is met, and as per Lemmas 4.1, 4.2, and 4.3, the ego vehicle needs to reduce speed, then the traffic lights take precedence over following the lead vehicle. This behavior is captured in Algorithm 4.2 by extending the conditions in Algorithm 4.1.
As per Algorithm 4.2, in addition to the conditions mentioned in Algorithm 4.1 and, therefore, the \(action\) suggested as per the traffic light using \(flag_{s}\), the following conditions also need to be checked to maintain a safe distance from the lead vehicle (Line 2). The MBS first acquires the estimated positions of the lead vehicle from its previous calculations (Line 3). If the ego vehicle is \(x^{safe}_{i}\) distance away from the lead vehicle, it must continue maintaining its current speed (Lines 4 and 5). If the gap between the ego vehicle and the lead vehicle is less than \(x^{safe}_{i}\), the ego vehicle must decelerate to increase the gap (Lines 6 and 7). Alternately, if the gap between the ego vehicle and the lead vehicle is more than \(x^{safe}_{i}\), the lead vehicle does not impact the actions of the ego vehicle and the ego vehicle may accelerate to increase the gap as long as it does not violate the speed limit (Lines 8–12). \(flag_{lead}\) depicts the suggested maneuver based on the leading vehicle’s mobility. \(flag_{act}\) then decides whether the traffic light (\(flag_{s}\)) or the lead vehicle (\(flag_{lead}\)) will affect the ego vehicle’s maneuver (\(action\)) (Lines 13–18).
With the dwell times assigned and mobility estimates known, the MBS now assigns appropriate RSUs for task \(\tau _{i}\) of vehicle \(V_{i}\) based on its deadline \(d^{t}_{i}\). Note that we also determine the RSU where the vehicle will be when its task deadlines are met while estimating the mobility characteristics.
4.4 RSU Allocation for Task Offloading
We know that a task \(\tau _{i}\) needs to be completed within \(d^{t}_{i}\) time of the task’s arrival. We also determined \(d^{t}_{i}\) corresponding to the distance-based deadline (\(d^{x}_{i}\)) and the \(RSU_{end}\) where the vehicle will be when its task meets the deadline. Therefore, the task has to be uploaded, computed, and downloaded within \(RSU_{1},\ldots , RSU_{end}\). The duration \(t^{end}_{i}\) that vehicle \(V_{i}\) will spend within the range of \(RSU_{end}\) is also known.
Download RSU: As explained in the motivating example, offloading tasks such that they complete closer to the deadline improves the resource utilization at the RSUs. To complete \(\tau _{i}\) closest to the deadline, the most appropriate RSU to download would be \(RSU_{end}\) if the duration for which vehicle \(V_{i}\) remains in the range of \(RSU_{end}\) is at least equal to the download time of the task \(\tau _{i}\). The download time \(t^{dl}_{i}\) of task \(\tau _{i}\) from any \(RSU_{j}\) depends on the download size \(\sigma ^{dl}_{i}\) of the task and the communication data rate \(\eta\) such that \(t^{dl}_{i} = \eta \cdot \sigma ^{dl}_{i}\). Therefore, if \(t^{dl}_{i} \le t^{end}_{i}\), then the task can be downloaded at \(RSU_{d} = RSU_{end}\). However, if the duration is not enough to download the task at \(RSU_{end}\) (\(t^{dl}_{i} \gt t^{end}_{i}\)), any \(RSU_j\) closest to \(RSU_{end}\) whose dwell time \(\delta _{id} \ge t^{dl}_{i}\) is chosen using Equation (9) and its constraints.
\begin{align} & 1 \le d \le \text{end}. \end{align}
(9b)
Equation (9) ensures that we maximize the index d of the RSU and thereby choose an RSU closest to \(RSU_{end}\), where we download the task with the following constraints. Constraint (9b): The dwell time of the chosen \(RSU_{d}\) is at least equal to the download time \(t^{dl}_{i}\) of the task. Constraint (9c): The index d of the chosen RSU must be less than \(end\) to meet the deadline.
Compute RSU: Upon choosing \(RSU_{d}\), the MBS then finds \(RSU_{c}\), where the task can be computed. The computation time (\(t^{c}_{i}\)) of \(\tau _{i}\) depends on the compute requirement \(C_{i}\) of the task and the clock speed \(z_{c}\) of the processors at \(RSU_{c}\) such that \(t^{c}_{i} = \frac{C_{i}}{z_{c}}\) and the processor availability \(p_{c}\) at \(RSU_{c}\). Note that the RSUs are connected via a backhaul network and incur an additional delay of \(\rho _{cd}\) (Equation (1)) for relaying the data from \(RSU_{c}\) to \(RSU_{d}\). Therefore, if there is sufficient time left within the range of \(RSU_{d}\) to also compute \(\tau _{i}\), that is, \(\delta _{id} - t^{dl}_{i} \ge t^{c}_{i}\), then the task is computed at \(RSU_{d}\) without incurring any additional backhaul network delay. Otherwise, \(RSU_{c}\) can be found using Equation (10) and its constraints.
Equation (10) maximizes the index c of the RSU chosen to compute the task so that the task is computed as close as possible to where the task is to be downloaded, with the following constraints. Constraint(10b): The sum of the dwell times of all RSUs from the chosen \(RSU_{c}\) to \(RSU_{d}\) where the task is to be downloaded is at least equal to the sum of the compute time \(t^{c}_{i}\), relay time \(\rho _{cd}\) of the backhaul network between \(RSU_{c}\) and \(RSU_{d}\) and the download time of the task \(t^{dl}_{i}\). This ensures that the vehicle reaches the range of \(RSU_{d}\) when the task is ready to download and that there is no wait time incurred. Constraint(10c): If the dwell time of \(RSU_{d}\) is sufficient to compute and download the task, then it will not add any additional relay time to the task’s completion time. Constraint(10d): There has to be at least one processor available at \(RSU_{c}\) to compute task \(\tau _{i}\). Constraint(10e): the task must be computed before it is to be downloaded at \(RSU_{d}\).
Upload RSU: The MBS now determines the appropriate \(RSU_{u}\) where the task needs to be uploaded such that the task is computed and downloaded in time to meet its deadline. The upload time \(t^{ul}_{i}\) of task \(\tau _{i}\) from any \(RSU_{j}\) depends on the upload size \(\sigma ^{ul}_{i}\) of the task and the communication data rate \(\eta\) (as per the Shannon Hartley theorem [33]) such that \(t^{ul}_{i} = \eta \cdot \sigma ^{ul}_{i}\). Therefore, \(RSU_{u}\) is chosen using Equation (9) and its constraints.
Equation (11) maximizes the index u so that the RSU with the highest index is chosen to upload while constrained by the following. Constraint(11b): The dwell time in \(RSU_{u}\) is sufficient to upload the task and relay it to \(RSU_{c}\) for computation. Constraint(11c): If \(RSU_{u} = RSU_{c}\), no relay time is incurred. Constraint(11d): The task must be uploaded before it is computed.
By solving Equations (9) to (11) using linear optimization techniques, \(RSU_{u}, RSU_{c}\), and \(RSU_{d}\) can be determined. Once the RSUs are assigned, the vehicle can upload the task as soon as it is in the range of the assigned \(RSU_{u}\). The MBS then transmits the task to \(RSU_{c}\) if needed, where the task is computed and then relayed to \(RSU_{d}\). Finally, the vehicle enters the communication range of \(RSU_{d}\) and starts downloading the task. The above formulation ensures that the task is completed as close to the deadline as possible.
Complexity Analysis: The dwell time estimation algorithm (Algorithm 4.1) has a time complexity of \(O(T\times R)\), where V denotes total task-offloading requests in the queue and R denotes the total RSUs along the link. Once the dwell times are estimated, the RSU assignment is a linear optimization problem with a time complexity of \(O(R)\).
5 Evaluation
In this section, we compare our proposed approach with the state-of-the-art task-offloading strategies as baselines. Let us describe the simulation parameters used for the evaluation.
5.1 Evaluation Setup
Table 1 contains the parameters for traffic infrastructure, vehicles, task model, communication model, and the VEC framework, It also summarizes the notations used in this article. These parameters closely resemble common VEC workloads and network and traffic infrastructure configurations [26, 52]. We emulate large-scale traffic moving through a link in an urban environment using VISSIM [10], a microscopic traffic simulator. The vehicles arrive at random times as per default distribution in VISSIM. All vehicles that enter the traffic network in VISSIM follow the driving maneuver model and its parameters considered in this article. An external communication framework emulator based on Python 3 acts as an MBS that interacts with VISSIM to acquire vehicle data, calculate dwell times, generate synthetic workloads based on the chosen task parameters, and assign RSUs to the vehicles.
Table 1.
Parameter
Values
Traffic Infrastructure
Link length \(d_{L}\)
[400,800] m
Speed limit \(\nu ^{lim}\)
[25,35] mph
Number of lanes l
1
Traffic Light s
Cycle time \(t^{cycle}_{s}\)
60 s
Max. green time \(t^{g}_{s}\)
26 s
Yellow time \(t^{y}_{s}\)
4 s
Max. red time \(t^{r}_{s}\)
30 s
Vehicles
Comfortable acceleration a
1 m/s\(^2\)
Comfortable deceleration \(-b\)
\(-\)0.9 m/s\(^2\)
Time headway h
0.9 s
Standstill gap \(x_{safe}\)
1.5 m
VEC Task Model
Task type
[time-based, location-based]
Upload size \(\sigma ^{ul}\)
1–100 MB
Compute requirement C
0.24–24 \(\times\)\(10^{9}\) clock cycles
Download size \(\sigma ^{dl}\)
1\(-\)100 MB
Time-based deadline \(d^{t}\)
100 ms–5s
Distance-based deadline \(d^{x}\)
1 m–\(d_{L}\) m
VEC Communication Framework
Communication radius r
25 m
Number of processors
[2, 4, 8]
Clock speed z
2.4 GHz
Wireless data rate \(\eta\)
500 Mbps
Backhaul data rate \(\eta _{bh}\)
1 Gbps
Backhaul relay constant \(c_{bh}\)
10 ms
Table 1. Simulation Parameters
We compare our proposed deadline-based strategy that uses connected traffic lights (referred as traffic lights-aware) with a closely related work [26] (referred as wait time-aware) which considers a time-statistical model to account for the average delays over time due to a traffic light but does not consider connected traffic lights with known traffic light timings. We also compare our work with a mobility-aware task-offloading strategy [52] (referred as mobility-aware) that considers mobility without traffic lights to minimize task-offloading times. Note that the proposed approach as well as the wait time-aware [26] and mobility-aware [52] approaches offload tasks onto the RSUs only if the task is expected to be completed before its deadline.
5.2 Performance in an Ideal Setting
We evaluate all three approaches on the basis of (i) the percentage of tasks out of the entire taskset that a strategy deems feasible to offload onto the RSUs based on its estimation of the vehicular mobility and task deadlines, and (ii) the percentage of tasks that miss their deadlines out of all of the tasks offloaded onto the RSUs. In this set of experiments, we assume that the vehicles and traffic flow behave ideally and follow the maneuvers as planned by the ADAS mobility planner.
Effect of traffic flow on task offloading (Figure 5): As the traffic flow increases, the number of vehicles on the link — and, therefore, the number of tasks to be offloaded — increase as well. As shown in Figure 5, with traffic flow changing from light to heavy (400–1,000 vehicles per hour per lane [vhphpl]), the dwell times of the vehicles increase within different RSU ranges due to an increase in vehicle queues at the traffic light. Results show that under heavy traffic, the existing approaches fail to adapt to these changing traffic patterns and lead to deadline misses. The wait time-aware approach offloads 47% of all task requests and misses the deadlines for 23% of the offloaded tasks, whereas the mobility-aware approach finds 44% of the tasks feasible to offload and misses the deadlines for 22% of the offloaded tasks. Location-based tasks comprise 53% and 59% of the offloaded tasks that missed their deadlines in time delay-aware and mobility-aware approaches, respectively. Effect of processor availability on task offloading (Figure 6): As more processors become available at the RSUs, more tasks can be computed in parallel. As shown in Figure 6, with flow fixed to medium traffic, with an increase in the number of available processors at each RSU, the number of tasks offloaded for all three approaches increases. However, it is important to note that as the number of available processors increases at each RSU, the existing approaches also show an increase in deadline misses (up to 25% of deadlines missed with 8 parallel processors). As the number of available processors at each RSU increases, the existing approaches have ample available resources to offload the tasks as soon as they arrive. However, due to the lack of traffic-aware mobility, the vehicles end up leaving the RSU range before the task execution completes, leading to an increase in missed deadlines. For our proposed approach, increasing processor availability increases the number of offloaded tasks, with all of them meeting their deadlines, maximizing RSU resource utilization. We are not including a discussion on the effect of increasing link length as it also leads to an increase in the number of RSUs and processor availability, and similar results were obtained.
Fig. 5.
Fig. 5. Effect of varying traffic flow on task offloading. Increasing traffic flow leads to a reduction in the percentage of tasks offloaded out of total task requests (colored). However, the existing approaches cause a significant number of tasks to miss their deadlines (hatched).
Fig. 6.
Fig. 6. Effect of increasing processor availability on task offloading. With increase in the number of processors all approaches offload more tasks onto the RSUs (colored), however, the wait time-aware and mobility-aware strategies lead to a significant number of tasks missing their deadlines (hatched).
Effect of speed limit on task offloading (Figure 7): We choose two speed limits common for urban traffic lights: 25 mph and 35 mph. With fixed traffic flow (700 vphpl) and number of processors (2 processors per RSU), as the speed increases, the vehicles have lesser dwell time within each RSU, causing a drop in number of tasks offloaded for our proposed approach. However, with our proposed approach, we still meet the deadlines for all offloaded tasks. In contrast, the wait time-aware approach sees an increase in the number of offloaded tasks, as higher vehicle speeds causes reduced travel times and wait times at the traffic light. However, an increase in speed also causes an increase in the number of deadline misses for the wait time-aware approach due to an increase in dwell time estimation errors. Similarly, the mobility-aware offloading also leads to increased deadline misses as it relies on the average vehicle speeds. Note that with an increase in processor availability, a similar trend as in Figure 6 was observed, in which at higher speeds, more processor availability meant an increase in the number of tasks offloaded but it also led to an increase in deadline misses.
Fig. 7.
Fig. 7. Effect of changing speed limits on task offloading. Increases to the speed limit lead to a change in the percentage of tasks offloaded (colored), with a significant increase in the deadline misses (hatched) for the existing strategies.
5.3 Performance Under Uncertainty
So far, we have considered that the CAVs within our model perform known driving maneuvers and behavior as the vehicle follows predefined constrained motion such as constant speeds, reducing speeds with known deceleration rates, and increasing speed with known acceleration rates. However, in a realistic urban driving environment, the controllers in fully automated vehicles are affected by noise and disturbances that do not allow the vehicles to follow precise mobility constraints and maneuvers. To evaluate the efficacy of our model in a realistic setup with noise and uncertainty, all vehicles in our simulated evaluation show a uniform distribution ranging between \(\nu _{lim}-5\) to \(\nu _{lim}\) instead of strictly following a target speed of \(\nu _{lim}\). Instead of the vehicles following strict acceleration and deceleration rates, they are now modelled after the Weidemann 74 car-following model [32]. In this work, the Weidemann 74 model is preferred over other car-following models as it accurately captures non-ideal driving conditions in which different drivers show varying perception, reaction times, and driving behaviors in the same environment. With the car-following model in place, the vehicles show maximum acceleration, ranging from 2.5 to \(3\ m/s^{2}\), and deceleration ranging from \(-2.5\) to \(-3\ m/s^{2}\). These parameter ranges are determined based on driver reaction times and passenger comfort [32].
Now, changing traffic parameters such as traffic speeds and flow rate may lead to vehicles showing increased stop-and-go motion and thereby significantly impact the deviation in modeled vehicle speeds, acceleration and following distances. We therefore investigate the impact of (i) traffic speeds (Figure 8) and (ii) traffic flow (Figure 9) on deadline misses in our proposed approach. Speed limit and deadline misses in non-ideal conditions: As expected (from Figure 7), increasing speed limits does cause a reduction in the tasks successfully offloaded onto the edge platform. Under realistic conditions, however (Figure 8), about 5% of the offloaded tasks experience deadline misses. Traffic flow and deadline misses in non-ideal conditions: Increasing traffic flow from low to heavy traffic leads to a reduction in tasks being offloaded onto the RSUs. However, highly varying traffic (very low or very high flow rates) leads to an increase in stop-and-go motions and variations in desired speed and acceleration. Therefore, as shown in Figure 9, under non-ideal conditions, low traffic (in which vehicles can travel at higher speeds) or heavy traffic (in which vehicles are known to show increased stop-and-go motions) leads to increased (up to 10%) deadline misses. Under medium traffic, all vehicles have a more regularized traffic flow and, therefore, experience very few (2%) deadline misses.
Fig. 8.
Fig. 8. Effect of speed on deadline misses in our proposed approach.
Fig. 9.
Fig. 9. Effect of traffic flow on deadline misses in our proposed approach.
Effect of model (speed, acceleration, and car-following model) uncertainties on deadline misses (Figure 10): Finally, we investigate the impact on non-ideal conditions in existing approaches when compared with our proposed approach. The uncertainty in speed, acceleration, and following distance added in a realistic car-following model are not known a priori. Therefore, they are not considered during dwell time estimation and RSU allocation phase in our proposed approach as well as other existing state-of-the-art approaches. Because of this, deadline misses are expected due to the model being an ideal version of the system. Figure 10 shows the effect of this uncertainty on deadline misses with our proposed approach as well as the existing state-of-the-art approaches under varying traffic flow. Note that as the traffic flow increases from low to heavy traffic, the vehicles show increased stop-and-go motion with larger deviation from the ideal speeds, acceleration, and following distances. As shown, our proposed approach, while still suffering from estimation errors due to non-ideal conditions, causes up to 78% fewer deadline misses than the existing approaches, showing that our proposed dwell time estimation and RSU allocation approach, by capturing traffic flow parameters and mobility behavior of the vehicles, is more resilient to uncertainties and leads to significantly higher utilization of the edge compute platform.
Fig. 10.
Fig. 10. Effect of model uncertainties on deadline misses.
6 Conclusion
In this article, we presented a comprehensive task model to support emerging VEC applications that incorporates tasks with fixed time-based deadlines as well as traffic-dependent tasks whose deadlines depend on traffic flow, location, and traffic lights. We then incorporated the traffic light data by leveraging the connected infrastructure to accurately estimate the mobility characteristics and dwell times of the vehicles. We then used the dwell time estimates to allocate appropriate RSUs to upload, compute, and download the tasks such that they always meet their deadlines. We also show that by completing tasks closer to their deadlines, we can improve on the resource utilization of the edge resources. Finally, our evaluation using VISSIM, a traffic simulator, showed that our proposed approach outperforms the existing approaches by consistently offloading more tasks onto the RSUs and meeting 100% of the task deadlines. Extending the proposed model for a network-wide edge resource optimization is left for future work.
References
[1]
Shimaa A. Abdel Hakeem, Anar A. Hady, and HyungWon Kim. 2020. 5G-V2X: Standardization, architecture, use cases, network-slicing, and edge-computing. Wireless Networks (2020).
Yueyue Dai and Yan Zhang. 2022. Adaptive digital twin for vehicular edge computing and networks. Journal of Communications and Information Networks 7, 1 (2022), 48–59.
Stavroula Panagiota Deligianni, Mohammed Quddus, Andrew Morris, Aaron Anvuur, and Steven Reed. 2017. Analyzing and modeling drivers’ deceleration behavior from normal driving. Transportation Research Record (2017).
Jianbo Du, Liqiang Zhao, Xiaoli Chu, F. Richard Yu, Jie Feng, and I. Chih-Lin. 2018. Enabling low-latency applications in LTE-A based mixed fog/cloud computing systems. IEEE Transactions on Vehicular Technology 68, 2 (2018), 1757–1771.
Angela H. Eichelberger and Anne T. McCartt. 2016. Toyota drivers’ experiences with dynamic radar cruise control, pre-collision system, and lane-keeping assist. Journal of Safety Research (2016).
Wenhao Fan, Yi Su, Jie Liu, Shenmeng Li, Wei Huang, Fan Wu, and Yuan’an Liu. 2023. Joint task offloading and resource allocation for vehicular edge computing based on V2I and V2V modes. IEEE Transactions on Intelligent Transportation Systems (2023).
Xumin Huang, Rong Yu, Dongdong Ye, Lei Shu, and Shengli Xie. 2021. Efficient workload allocation and user-centric utility maximization for task scheduling in collaborative vehicular edge computing. IEEE Transactions on Vehicular Technology (2021).
Nathaniel Hudson, Hana Khamfroush, and Daniel E. Lucani. 2021. QoS-aware placement of deep learning services on the edge with multiple service implementations. In 2021 International Conference on Computer Communications and Networks (ICCCN’21). IEEE.
Hasan Ali Khattak, Haleem Farman, Bilal Jan, and Ikram Ud Din. 2019. Toward integrating vehicular clouds with IoT for smart city services. IEEE Network 33, 2 (2019), 65–71.
Yu-Jen Ku and Sujit Dey. 2019. Sustainable vehicular edge computing using local and solar-powered roadside unit resources. In 2019 IEEE 90th Vehicular Technology Conference (VTC2019-Fall). IEEE.
Thomas Lagkas, Dimitrios Klonidis, Panagiotis Sarigiannidis, and Ioannis Tomkos. 2021. Optimized joint allocation of radio, optical, and MEC resources for the 5G and beyond fronthaul. IEEE Transactions on Network and Service Management 18, 4 (2021), 4639–4653.
Bing Lin, Fangning Zhu, Jianshan Zhang, Jiaqing Chen, Xing Chen, Naixue N. Xiong, and Jaime Lloret Mauri. 2019. A time-driven data placement strategy for a scientific workflow combining edge computing and cloud computing. IEEE Transactions on Industrial Informatics (2019).
K. Liu, N. Abu-Ghazaleh, and K.-D. Kang. 2006. JiTS: Just-in-time scheduling for real-time sensor data dissemination. In 4th Annual IEEE International Conference on Pervasive Computing and Communications (PERCOM’06). 5 pp.–46.
Lei Liu, Chen Chen, Qingqi Pei, Sabita Maharjan, and Yan Zhang. 2021. Vehicular edge computing and networking: A survey. Mobile Networks and Applications (2021).
Wencan Mao, Ozgur Umut Akgul, Abbas Mehrabi, Byungjin Cho, Yu Xiao, and Antti Ylä-Jääski. 2022. Data-driven capacity planning for vehicular fog computing. IEEE Internet of Things Journal 9, 15 (2022), 13179–13194.
Di Natale et al. 1994. Dynamic end-to-end guarantees in distributed real time systems. In 1994 Proceedings of Real-Time Systems Symposium. IEEE, 216–227.
Gerrit J. L. Naus, Rene P. A. Vugts, Jeroen Ploeg, Marinus J. G. van De Molengraft, and Maarten Steinbuch. 2010. String-stable CACC design and experimental validation: A frequency-domain approach. IEEE Transactions on Vehicular Technology (2010).
Pratham Oza, Thidapat Chantem, and Pamela Murray-Tuite. 2020. A coordinated spillback-aware traffic optimization and recovery at multiple intersections. In 2020 IEEE 26th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA’20).
Sangjun Park and Hesham Rakha. 2010. Continuous flow intersections: A safety and environmental perspective. In 13th International IEEE Conference on Intelligent Transportation Systems. IEEE, 85–90.
Eric Price and David P. Woodruff. 2012. Applications of the Shannon-Hartley theorem to data streams and sparse recovery. In 2012 IEEE International Symposium on Information Theory Proceedings. IEEE.
Syed Danial Ali Shah, Mark A. Gregory, Shuo Li, Ramon dos Reis Fontes, and Ling Hou. 2022. SDN-based service mobility management in MEC-enabled 5G and beyond vehicular networks. IEEE Internet of Things Journal 9, 15 (2022), 13425–13442.
Muhammad Sameer Sheikh, Jun Liang, and Wensong Wang. 2020. Security and privacy in vehicular ad hoc network and vehicle cloud computing: A survey. Wireless Communications and Mobile Computing 2020 (2020), 1–25.
Jinming Shi, Jun Du, Jingjing Wang, Jian Wang, and Jian Yuan. 2020. Priority-aware task offloading in vehicular fog computing based on deep reinforcement learning. IEEE Transactions on Vehicular Technology (2020).
Yushan Siriwardhana, Pawani Porambage, Madhusanka Liyanage, and Mika Ylianttila. 2021. A survey on mobile augmented reality with 5G mobile edge computing: Architectures, applications, and technical aspects. IEEE Communications Surveys & Tutorials 23, 2 (2021), 1160–1192.
Darbha Swaroop and K. R. Rajagopal. 2001. A review of constant time headway policy for automatic vehicle following. In Proceedings of 2001 IEEE Intelligent Transportation Systems (ITSC’01) (Cat. No. 01TH8585). IEEE.
Nugroho AKim T(2024)Traffic-Aware Intelligent Association and Task Offloading for Multi-Access Edge ComputingElectronics10.3390/electronics1316313013:16(3130)Online publication date: 7-Aug-2024
Ren HLiu KYan GLiu CLi YLi CWu W(2024)Truthful Auction Mechanisms for Dependent Task Offloading in Vehicular Edge ComputingIEEE Transactions on Mobile Computing10.1109/TMC.2024.345050423:12(14987-15002)Online publication date: Dec-2024
Hassan Husain MAhmadi MMardukhi F(2024)A GWO-MFO-Based Resource Allocation in Vehicular Fog Computing With Latency Constraints and Energy ReductionIEEE Access10.1109/ACCESS.2024.347106812(176466-176484)Online publication date: 2024
Vehicular edge computing (VEC) is a promising paradigm to offload resource-intensive tasks at the network edge. Owing to time-sensitive and computation-intensive vehicular applications and high mobility scenarios, cost-efficient task offloading in ...
Vehicular fog computing (VFC) has been proposed as a promising solution to overcome the limitations of edge computing. In VFC, the idle resources of moving and parked vehicles can be used for compute-intensive applications of resource-...
Highlights
The selection of an appropriate target fog node in Vehicular Fog Computing’s (VFC) is a complex process.
With the popularity of vehicular communication systems and mobile edge vehicle networking, intelligent transportation applications arise in Internet of Vehicles (IoVs), which are latency-sensitive, computation-intensive, and requiring sufficient ...
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Nugroho AKim T(2024)Traffic-Aware Intelligent Association and Task Offloading for Multi-Access Edge ComputingElectronics10.3390/electronics1316313013:16(3130)Online publication date: 7-Aug-2024
Ren HLiu KYan GLiu CLi YLi CWu W(2024)Truthful Auction Mechanisms for Dependent Task Offloading in Vehicular Edge ComputingIEEE Transactions on Mobile Computing10.1109/TMC.2024.345050423:12(14987-15002)Online publication date: Dec-2024
Hassan Husain MAhmadi MMardukhi F(2024)A GWO-MFO-Based Resource Allocation in Vehicular Fog Computing With Latency Constraints and Energy ReductionIEEE Access10.1109/ACCESS.2024.347106812(176466-176484)Online publication date: 2024
Husain MAhmadi MMardukhi F(2024)Vehicular Fog Computing: A Survey of Architectures, Resource Management, Challenges and Emerging TrendsWireless Personal Communications: An International Journal10.1007/s11277-024-11373-z136:4(2243-2273)Online publication date: 1-Jun-2024
Sun YWu JWu YChen LSun W(2023)Efficient approaches for task offloading in point-of-interest based vehicular fog computingThe Journal of Supercomputing10.1007/s11227-023-05698-y80:5(6285-6310)Online publication date: 21-Oct-2023
