{'fraction_non_alphanumeric': 0.03685376661742984, 'fraction_numerical': 0.010598227474150665, 'mean_word_length': 4.388181456426582, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Learning-Based Task Offloading for Vehicular Cloud Computing Systems

Vehicular cloud computing (VCC) is proposed to effectively utilize and share the computing and storage resources on vehicles. However, due to the mobility of vehicles, the network topology, the wireless channel states and the available computing resources vary rapidly and are difficult to predict. In this work, we develop a learning-based task offloading framework using the multi-armed bandit (MAB) theory, which enables vehicles to learn the potential task offloading performance of its neighboring vehicles with excessive computing resources, namely service vehicles (SeVs), and minimizes the average offloading delay. We propose an adaptive volatile upper confidence bound (AVUCB) algorithm and augment it with load-awareness and occurrence-awareness, by redesigning the utility function of the classic MAB algorithms. The proposed AVUCB algorithm can effectively adapt to the dynamic vehicular environment, balance the tradeoff between exploration and exploitation in the learning process, and converge fast to the optimal SeV with theoretical performance guarantee. Simulations under both synthetic scenario and a realistic highway scenario are carried out, showing that the proposed algorithm achieves close-to-optimal delay performance.


I. INTRODUCTION
Mobile devices are expected to support a vast variety of mobile applications. Many of them require a large amount of computation in a very short time, which cannot be satisfied by the devices themselves due to the limited processing power and battery capacity. Mobile cloud computing (MCC) is thus proposed [1], enabling mobile devices to offload computation tasks to powerful remote cloud servers through the Internet. However, centralized deployments of clouds introduce long latency for data transmission, which cannot meet the requirements of the emerging delay-sensitive applications, such as augmented/virtual reality, connected vehicles, Internet of things, etc. By deploying computing and storage resources at the network edge, mobile edge computing (MEC) can provide low latency computing services [2]. A major challenge in the MEC system is to perform task offloading, i.e., when and where to offload the computation tasks, and how to allocate radio and computing resources, which have been widely investigated [3]- [5]. Ad hoc cloudlet has been proposed in [6] to make use of the computing resources of mobile devices through device-to-device communications [7].
Vehicles have huge potential to enhance edge intelligence. The global number of connected vehicles is increasing rapidly, and will achieve to around 250 million by 2020 [8]. Meanwhile, vehicles are equipped with increasing amount of computing and storage resources [9]. In order to improve the utilization of vehicle resources, the concept of vehicular cloud computing (VCC) is proposed [10], in which vehicles can serve as vehicular cloud (VC) servers by sharing their surplus computing resources, and users such as other vehicles and pedestrians can offload computation tasks to them. In this case, the vehicles providing services are called service vehicles (SeVs) and the vehicles that offload their tasks are called task vehicles (TaVs). Existing architectures include softwaredefined VC [11] and VANET-Cloud [12].
Compared with the MEC system, the highly dynamic vehicular environments bring more uncertainties to the VCC system. First, the topology of vehiclar networks and the wireless channel states vary rapidly over time due to the mobility of vehicles. Second, the computing resources of SeVs are heterogeneous and fluctuate over time. These factors are typically difficult to predict, but significantly affect the delay performance of computation tasks. Furthermore, each TaV may be surrounded by multiple candidate SeVs since the density of SeVs can be much higher than that of MEC servers. It is not easy to estimate the performance of different SeVs for task offloading.
There are existing papers investigating task offloading algorithms in the VCC system. In [13], the VC and remote cloud layer are jointly considered. A centralized task offloading algorithm is proposed to minimize the average system cost related to delay, energy consumption and resource occupation. However, the centralized control requires large signaling overheads for vehicular states update, and the proposed algorithm has high complexity. A distributed task offloading algorithm is proposed in [14] based on ant colony optimization, which is of much lower complexity. However, it still requires exchanges of vehicular states. To further overcome the uncertainties in the VCC system and improve service reliability, replicated task offloading is proposed in [15], in which task replicas are assigned to multiple SeVs at the same time.
In this work, we focus on the task offloading problem of TaVs in the VCC system, and propose a learning-based task offloading algorithm to minimize the average offloading delay. Our main contributions are summarized as follows: 1) We propose a learning-based distributed task offloading framework based on the multi-armed bandit (MAB) theory [16], which enables TaVs to learn the performance of SeVs and to make task offloading decisions individually, in order to obtain low delay without exchanging vehicular states.
2) We propose an adaptive volatile upper confidence bound (AVUCB) algorithm by redesigning the utility function in the classic MAB algorithms, making it adapt to the time-varying load and action space. Both load-awareness and occurrenceawareness are augmented to the learning algorithm, so that AVUCB can effectively cope with the highly dynamic vehicular environment and balance the so-called exploration and exploitation tradeoff in the learning process. We also prove that the performance loss can be upper bounded.
3) Simulations are carried out under both synthetic scenario and a realistic highway scenario, showing that the proposed algorithm can achieve close-to-optimal delay performance.
The rest of this paper is organized as follows. The system model and problem formulation is described in Section II. The AVUCB algorithm is then proposed in Section III and the performance is analyzed in Section IV. Simulation results are provided in Section V, and finally comes the conclusion in Section VI. We consider a discrete-time VCC system in which moving vehicles are classified into two categories: SeVs and TaVs. SeVs are employed as vehicular cloud servers to provide computing services, while the on-board user equipments (UEs) of TaVs, such as smart phones and laptops, generate computation tasks that need to be offloaded for cloud execution. Note that the role of SeV or TaV is not fixed for each vehicle, which depends on whether the computing resources are sufficient and shareable. For each TaV, the surrounding SeVs in the same moving direction within its communication range C r are considered as candidate servers. Here the moving direction, together with vehicle ID, speed and location of each candidate SeV can be known to each TaV, provided by vehicular communication protocols such as beacons of dedicated short-range communication (DSRC) standards [17].

A. System Overview
Each computation task is offloaded to one of the candidate SeVs and processed on this single SeV according to the task offloading algorithm, without further offloaded to other SeVs, MEC servers or the remote cloud. An exemplary VCC system is shown in Fig. 1, where TaV 1 discovers 3 candidate SeVs (SeV 1-3) in its neighborhood, and the current task is offloaded to and executed on SeV 3. In this work, task offloading decisions are made in a distributed manner, i.e., each TaV makes its own task offloading decisions, in order to avoid large signaling exchange overhead. We focus on a representative TaV that moves on the road for a total of T time periods. In time period t, the TaV generates a computation task, selects an SeV n ∈ N (t), offloads the task and then receives the computing result. Here, N (t) is denoted as the candidate SeV set that can provide computing services to the TaV in time period t. We assume that N (t) = ∅ for ∀t, otherwise the TaV can offload tasks to the MEC server or the remote cloud. Note that N (t) changes across time since vehicles are moving.

B. Computation Task Offloading
The computation task generated in time period t is described by three parameters: input data size x t (in bits) that needs to be transmitted from TaV to SeV n, output data size y t (in bits) that is fed back from SeV n to TaV, and the computation intensity w t (in CPU cycles per bit) which is the required CPU cycles to compute one bit input data. Then the total required CPU cycles of the task in time period t is x t w t [3].
For each candidate SeV n, the maximum computation capability is denoted by F n (in CPU cycles per second), which is the maximum available CPU speed of its on-board server. Multiple computation tasks can be processed simultaneously using processor sharing, and the allocated computation capability to the considered TaV in time period t is denoted by f t,n . Then the computation delay of SeV n ∈ N (t) is However, in the real system, f t,n may be unknown to the TaV in advance (this will be discussed in details in Section II-C). At time period t, the uplink transmission rate between the TaV and each candidate SeV n ∈ N (t) is denoted by r (u) t,n , which mainly depends on the uplink channel state h (u) t,n between the TaV and SeV n, and the interference power I (u) t,n at SeV n. Given the channel bandwidth W , the transmission power P of the TaV and the noise power σ 2 , the uplink transmission rate can be written as ( Similarly, the downlink transmission rate is given by where h t,n is the downlink channel state between SeV n and the TaV, and I (d) t is the interference at the TaV. Therefore, the total transmission delay for uploading the task to SeV n and receiving the result feedback is Still, both r (u) t,n and r (d) t,n are unknown to the TaV in advance. Finally, the sum offloading delay to SeV n in time period t is the computation delay plus the transmission delay (5)

C. Problem Formulation
The TaV makes task offloading decisions about which SeV should serve each computation task, in order to minimize the average offloading delay. The problem is formulated as where a t ∈ N (t) is the index of the selected SeV for task offloading in time period t.
If the TaV knows the exact computation capability f t,n , uplink and downlink transmission rates r t,n of all candidate SeVs before offloading the task in time period t, it only needs to calculate the sum delay d(t, n) for ∀n ∈ N (t), and a t = arg min n d(t, n). However, in real systems, the wireless channel state and the interference change rapidly due to the movements of vehicles, and the computing resource of each SeV is shared by multiple tasks. Thus the transmission rates r t,n and the computation capability f t,n are fast varying across time, which are not easy to predict. On the other hand, if each TaV requests r t,n and f t,n of all candidate SeVs in each time period, the signaling overhead will be very high.
Without the pre-knowledge of the transmission rates r t,n and computation capability f t,n of each candidate SeV n, the TaV does not know which SeV performs the best when making the current offloading decision. Therefore, we will design learning-based task offloading algorithm in the following section, in which the TaV learns the delay performance of candidate SeVs based only on the historical delay observations. That is, the offloading decision a t at time t is based on the observed delay sequence d(1, a 1 ), d(2, a 2 ), ..., d(t − 1, a t−1 ), but not the exact value of r t,n and f t,n of any candidate SeV n in the current time period t.
III. LEARNING-BASED TASK OFFLOADING ALGORITHM In this section, we develop learning-based task offloading algorithm which enables the TaV to learn the delay performance of candidate SeVs and minimizes the average offloading delay.
We assume that tasks are of diverse input data size, but the ratio of output data size and input data size, as well as the computation intensity are identical. In fact, this is a valid assumption when the offloaded tasks are of the same kind. Let y t /x t = α 0 and w t = ω 0 for ∀t. Define the bit offloading delay as which is the sum delay of offloading one bit input data to SeV n in time period t, reflecting the comprehensive service capability of each candidate SeV. Therefore, the sum delay When making the offloading decision of the current task at time t, TaV knows the input data size x t . But for ∀n ∈ N (t), the exact value of u(t, n) and its distribution are not known to the TaV in prior, which need to learn. Our task offloading problem can be formulated as an MAB problem to solve. To be specific, the TaV is the player and each candidate SeV corresponds to an action with unknown distribution of loss. The player makes sequential decisions on which action should be taken to minimize the average loss. The main challenge of the classic MAB problem is to balance the exploration and exploitation tradeoff: explore different actions to learn good estimates of each distribution, while at the same time select the empirically best actions as many as possible. The problem has been widely studied and many algorithms have been proposed with strong performance guarantee, such as the upper confidence bound (UCB) based UCB1 and UCB2 algorithms [16]. The MAB framework has already been applied in the wireless networks to help learn the unknown environments, such as solving channel access problems [18] and mobility management issues [19].
Although our problem is similar to the classic MAB problem, we still face two new challenges. First, the candidate SeV set N (t) changes across time due to the relative movements of vehicles, rather than the fixed number of actions in the classic MAB problem. The SeVs may appear and disappear in the communication range of the TaV unexpectedly, causing a volatile action space. Existing solutions cannot exploit the empirical information of the remaining SeVs efficiently. Second, the performance loss in each time period is of equal weight in the MAB problem. However, in our model, the input data size x t of each task brings a weighting factor on the offloading delay. Intuitively, the task offloading algorithm should explore more when x t is low, and exploit more when x t is high, so that the cost of exploration can be reduced.
To overcome the aforementioned two challenges, we propose an Adaptive Volatile UCB (AVUCB) algorithm for task offloading, as shown in Algorithm 1. Parameter β is a constant factor, k t,n is the number of tasks that have been offloaded to SeV n up till time t, and t n records the occurrence time of each SeV n. Parameterx t is the normalized input data size within [0, 1], which is denoted as where x + and x − are the upper and lower thresholds for normalizing x t . Our proposed AVUCB algorithm can effectively balance the exploration and exploitation under the variation of candidate SeV set and input data size, inspired by the volatile MAB [20] and opportunistic MAB [21] frameworks. In Algorithm 1, Lines 3-5 are the initialization phase, in which the TaV will connect to the newly appeared SeV once. Lines 7-12 represent the continuous learning phase. The utility function defined in (10) is the sum of empirical delay performanceū t,n and a padding function (the latter term). Compared with existing UCB algorithms, the padding function is redesigned by jointly Algorithm 1 AVUCB Algorithm for Task Offloading 1: Input: α 0 , ω 0 and β. 2: for t = 1, ..., T do 3: if Any SeV n ∈ N (t) has not connected to TaV then 4: Connect to SeV n once. 5: Updateū t,n = d(t, n)/x t , k t,n = 1, t n = t. Observe x t . 8: Calculate the utility function of each candidate SeV n ∈ N (t): Offload the task to SeV: 10: Observe delay d(t, a t ).

13:
end if 14: end for taking into account the occurrence time t n of SeV and the input data size x t (the load), thus it can dynamically adjusts the weight of exploration and bring the occurrence-awareness and load-awareness to the algorithm. Task offloading decision is then made in Line 9, which is a minimum seeking problem with computational complexity O(|N (t)|), where |N (t)| is the number of candidate SeVs in time period t.

IV. PERFORMANCE ANALYSIS
In this section, we present the performance analysis of the proposed AVUCB algorithm. We first define an epoch as the duration in which the candidate SeV set remains the same. Let B denote the total number of epochs during T time periods, N b the candidate SeV set in the bth epoch, and t b , t ′ b the beginning and ending time period of the bth epoch with t ′ B = T . We assume that the bit offloading delay u(t, n) of each candidate SeV is i.i.d. over time and independent of each other, with expectation E t [u(t, n)] = µ n . We will prove later through simulations that without this assumption, AVUCB still works well. In each epoch, let µ * b = min n∈N b µ n and a * b = arg min n∈N b µ n . Define the total learning regret as which is the expected loss of delay performance due to lacking the service capability information of the candidate SeVs. In the following subsections, we try to upper bound the learning regret of AVUCB algorithm.

A. Regret Analysis under Identical Load
Compared to the existing UCB algorithms [16], the AVUCB algorithm adds the occurrence time t n and normalized input data sizex t to the padding function. In this subsection, we first investigate the impact of the occurrence time, by assuming that the load is not time varying, i.e., tasks are of identical input data size with x t = x 0 andx t = 0 for ∀t. Thus the padding function in (10) can be simplified as β ln(t−tn) kt−1,n , and the learning regret . Let u m = sup t,n u(t, n), and δ n,b = (µ n − µ * b )/u m . We first provide the upper bound of the learning regret within each epoch, as shown in Lemma 1.
Proof. See Appendix A.
Then we can upper bound the learning regret over T time periods in the following theorem.
Theorem 1. Let β = 2u 2 m , the total learning regret R T of AVUCB with identical load has an upper bound as follows: Proof. See Appendix B.
Theorem 1 implies that when tasks are of equal input data size, the proposed AVUCB algorithm can provide a bounded performance loss, compared to the optimal solution in which the TaV knows in prior which SeV performs the best. Specifically, the performance loss grows linearly with B and logarithmically with T .

B. Impact of the Load
In this subsection, we show the impact of the load on the learning regret, by considering that the input data size x t is random and continuous. For simplicity, we focus on a single epoch and assume B = 1. Thus there exists single best SeV with µ * = min n∈N1 µ n , a * = arg min n∈N1 µ n , and the learning regret is simplified as Recall that the normalized input data sizex t is defined in (9), in which the upper and lower thresholds x + and x − should be carefully selected for the tradeoff between exploration and exploitation. In the following theorem, x + and x − are selected such that P{x t ≤ x − } > 0 and x + ≥ x − . Particularly, when The learning regret under random and continuous input data size is shown in Theorem 2.
Theorem 2. Let β = 2u 2 m , with random continuous x t and P{x t ≤ x − } > 0, we have: (1) With x + ≥ x − , the expected number of tasks k T,n offloaded to any SeV n = a * can be upper bounded as (2) With x + = x − , the learning regret where n u(t, n), and δ n = (µ n − µ * )/u m .
Proof. See Appendix C.
Theorem 2 shows that, under single epoch, the learning regret grows logarithmically with T . This implies that when the input data size x t varies across time, our proposed AVUCB algorithm can still effectively balance the exploration and exploitation by adjusting the normalized factorx t , and provide a bounded deviation compared to the optimal solution.

V. SIMULATIONS
In this section, we evaluate the average delay and learning regret of the proposed AVUCB algorithm through simulations. We start from a synthetic scenario, and then simulate a realistic highway scenario.

A. Simulation under Synthetic Scenario
Simulations under synthetic scenario are carried out in MATLAB. We consider one TaV and 5 SeVs appear (and may also disappear) in the duration of T = 1200 time periods. The communication range C r = 200m. Within the TaV's communication range, the distance between the TaV and each SeV ranges in [10,200]m, and changes randomly by −10m to 10m every time period. According to [22], the wireless channel state is modeled by an inverse power law h (u) t,n = h (d) t,n = A 0 l −2 , where l is the distance between TaV and SeV and A 0 = −17.8dB. Other default parameters are: computation intensity ω 0 = 1000Cycles/bit, transmit power P = 0.1W, channel bandwidth W = 10MHz, noise power σ 2 = 10 −13 W and parameter β in (10) is 2.
We first evaluate the effect of occurrence time t n in the proposed AVUCB algorithm, by assuming that all the tasks are of equal input data size x 0 = 0.6Mbits, and thusx t = 0 for ∀t. The whole duration is divided into 3 epochs, each having 400 time periods. The index of candidate SeVs and their maximum computation capability F n is shown in table I. In epoch 2, there appears two SeVs indexed by 3 and 4, while in epoch 3, there appears a new SeV 5 and SeV 3 disappears. At each time period, the allocated computation capability f t,n is randomly distributed from 20%F n to 50%F n . Fig. 2(a) shows the learning regret of the proposed AVUCB algorithm and existing UCB1 algorithm under diverse occurrence time of SeVs and identical load. In the first epoch, the two algorithms perform the same since the occurence time of all SeVs are 1. From the second epoch, by taking into account of the occurrence time, AVUCB is able to learn   the performance of the newly appeared SeVs faster, while effectively making use of the information of the remaining SeVs. Compared to UCB1 algorithm, it can reduce about 50% of the learning regret. The average delay performance of each epoch is shown in Fig. 2(b), in which the average delay of AVUCB converges faster to optimal delay than UCB1.
We then focus on a single epoch with B = 1, and evaluate the effect of the normalized input data sizex t under random load. The candidate SeV set and its maximum computation capability are the same as epoch 2 in table I. The input data size x t is uniformly distributed within [0.2, 1]Mbits. The upper and lower thresholds are set to be x + = 0.8, x − = 0.4 and x + = x − = 0.6 respectively. As shown in Fig. 3, under the two sets of thresholds, AVUCB achieves similar learning regret, since both settings can effectively adjust the weight of exploration and exploitation. However, the UCB1 algorithm suffers much higher learning regret without load-awareness, since it may still explore even if the input data size is large.

B. Simulation under Realistic Highway Scenario
In this subsection, we simulate a realistic highway scenario and better emulate the traffic flow using Simulation of Urban MObility (SUMO) 1 . We use a 12km stretch of two-lane G6 Highway in Beijing with two ramps, obtained from Open Street Map (OSM) 2 . The network consists of 50% SeVs and 50% TaVs. Each vehicle is of equal probability of reaching a maximum speed of 72km/h or 90km/h. In each time period, the probability of generating a vehicle from each ramp is 0.1, and whenever a vehicle approaches a ramp, it leaves the highway with probability 0.5.
The locations of vehicles are simulated by SUMO, and then we can calculate the distance between each TaV and SeV at each time period. SeVs within its communication range C r = 200m are considered as candidate SeVs. We then focus on a single TaV, moving through the highway in T = 400 time periods. The occurrence and departure time of each candidate SeV, and its maximum computation capability F n are listed in table II. Same as above, the allocated computation capability f t,n is randomly distributed from 20%F n to 50%F n , and the input data size x t is uniformly distributed within [0.2, 1]Mbits. Let x + = x − = 0.6. We evaluate the average delay performance of the proposed AVUCB algorithm compared with 4 other algorithms: 1) UCB1 [16], which considers neither occurrence time nor input data size. 2) VUCB1 [20], which is occurrence-aware but not load-aware. 3) A naive Random Policy in which the TaV randomly select a SeV in each time period. 4) Optimal Policy, in which TaV knows the performance of each candidate SeV in advance and selects the optimal one. Fig. 4 shows the average delay of the aforementioned 5 algorithms. Our proposed AVUCB algorithm achieves closeto-optimal delay performance, while outperforms the other algorithms. This is because by introducing the occurrence time of each SeV and the normalized input data size, AVUCB is both occurrence-aware and load-aware, and can effectively balance exploration and exploitation in the learning process.

VI. CONCLUSIONS
In this work, we have studied the task offloading problem in the VCC system and proposed a learning-based AVUCB algorithm that minimizes the average offloading delay based only on the historical delay observations. The proposed algorithm is of low complexity and easy to implement with low signaling overhead. We have extended the classic MAB algorithms to be both load-aware and occurrence-aware, by taking into account the input data size of tasks and the occurrence time of SeVs in the utility function. Therefore, AVUCB can effectively adapt to the highly dynamic vehicular environment and balance the tradeoff between exploration and exploitation in the learning process with performance guarantees. Simulations under both synthetic scenario and a realistic highway scenario have shown that our proposed algorithm can achieve close-to-optimal delay performance. Future research directions include considering the heterogeneous cloud architecture with VCC, MEC and remote cloud, as well as the cooperation of SeVs. The learning regret in the bth epoch can be written as where k n,b is the number of tasks offloaded to SeV n in epoch b. Following the proof of Lemma 1 in [20] and Theorem 1 in [16], when β = 2u 2 m , the expectation of k n,b can be upper bounded by Substituting (18) into (17), we prove Lemma 1: APPENDIX B PROOF OF THEOREM 1 According to Lemma 1, the learning regret of the bth epoch: By summing over b = 1, 2, ..., B, the total learning regret: APPENDIX C PROOF OF THEOREM 2 When β = 2u 2 m and B = 1, the utility function in (10) iŝ u t,n =ū t−1,n − u m 2(1 −x t ) ln t k t−1,n .
The offloading decision in (11) can be written as: a t = arg min The learning regret can be written as Since 1 −ū t−1,n um ∈ [0, 1], and 1 − u(t,n) um ∈ [0, 1], our problem is equivalent to the problem defined in Section II in our previous work [21]. By leveraging Lemma 7, Theorem 3 and Appendix C.2 in [21], we can get Theorem 2.