Algorithms For Task Offloading In Vehicular Networks

Network communication among vehicles and infrastructures has been successfully implemented in vehicular network,which becomes a critical component of the future transportation systems.Vehicular network can provide high quality of computing services for transportation system,by exploiting edge computing techniques to integrate computing resources on vehicles and on roadside units(RSUs).However,there exist several challenges in terms of task offloading for supporting high quality of computing services in vehicular network,due to high mobility of vehicles,uneven distribution of vehicles in geography,stochastic requests,heterogeneous service capabilities.These characteristics lead to high response time of tasks,high energy consumption of vehicles or RSUs,weak stability of network,etc.To meet these challenges,this thesis focuses on efficient algorithms for task offloading on different vehicular network models,to provide high quality of computing services.The main contributions of this thesis are as follows.(1)A novel computing model,together with three algorithms,is proposed on the vehicular network with vehicle-to-infrastructure(V2I)computation offloading,in which the states of RSUs can dynamically switch between work and sleep.Specifically,the task requests of vehicles are modeled as an independent Poisson stream,and the computing service is modeled as a simple M/M/1 queuing system for each edge server in RSU.Meanwhile,an optimization problem of minimizing the total delay of tasks is formulated,and its NP-hardness is proved.For solving this problem,a greedy algorithm is proposed,by carefully selecting RSU to minimize the response time of the task arrived at the current time.Meanwhile,a tabu search algorithm is customized to refine the solution generated by the proposed greedy algorithm.Moreover,a deep Q-network based algorithm is proposed,by exploiting deep reinforcement learning approach,to decrease the response time of tasks.Simulation results show that the proposed deep Q-network algorithm performs better than the random algorithm also proposed in this thesis,in terms of total delay of tasks.Meanwhile,all proposed algorithms outperform the random algorithm,in terms of total delay of tasks.(2)Load balance is a challenge problem on the vehicular network model with vehicle-to-vehicle(V2V)computation offloading,due to high mobility of vehicles,uneven distribution of vehicles in geography,stochastic requests,heterogeneous service capabilities.A novel problem for load balance,together with the related V2V computation offloading algorithms and adjustment algorithm for transmit power,is proposed.Specifically,a NP-hard problem is modeled to minimize the maximum load under the constraints of transmit power,storage capacity,per task completion time and energy consumption.The modeled problem is investigated by decomposing it into two subproblems,i.e.,1)how to offload tasks for the case of fixed transmit power and 2)how to adjust transmit power for the given offloading decision.For the first subproblem,a series of algorithms are proposed to decrease the maximum computing load,they are an approximation algorithm,a deep reinforcement learning algorithm,a coalition based algorithm,a distributed coalition based algorithm,and an incentive algorithm based on deep reinforcement learning.For the second subproblem,an adjustment strategy for transmit power is customized to further reduce the computing load.The algorithms are evaluated on an integrated simulation platform with OSM,SUMO,NS-3 and dataset of Google cluster-usage traces.Simulation results show that,the proposed algorithms outperform three state-of-the-arts for most cases,in terms of the maximum computing load.Besides,the computing load can be further reduced by the proposed adjustment strategy.(3)A vehicular network model for directional vehicle mobility and three task offloading algorithms are proposed,where both V2I computation offloading and V2V computation offloading are considered,to provide the stable and efficient computing services for users.Specifically,a network model for directional vehicle mobility is proposed,where vehicles are configured into three vehicular subnetworks based on their turning directions at the crossing.For each subnetwork,vehicles communicate with each other in the manner of V2V,and they communicate with RSUs in the manner of V2I.To minimize the average response time of tasks generated from vehicles,a greedy algorithm is proposed,by carefully choosing neighboring vehicles as task processing helpers.In addition,two bipartite matching based algorithms are presented,by exploiting Kuhn-Munkras approach and minimum-cost maximum-flow approach,respectively.The proposed model and the performance of offloading algorithms are evaluated on the combined simulation platform by OSM,SUMO and NS-3.Simulation results show that,the proposed model outperforms four existing models in terms of average response time,when the mentioned five models have similar number of unsuccessful tasks.Moreover,the proposed two bipartite matching based algorithms are superior to the existing algorithm in terms of the average response time of tasks.Meanwhile,the proposed greedy algorithm significantly accelerates the generation of offloading decisions,compared with two bipartite matching based algorithms and the existing algorithm.