Recent studies in collaborative edge computing fail to take advantage of shareable structures in multi-task learning (MTL) models and the potential of MTL models sharing at the edge. This leads to resource under-utilization at the edge. Thus, this paper focuses on shareable-structure-aware model deployment and task scheduling in collaborative multi-task inference, so as to fully utilize the low-latency potential of edge computing. Specifically, we formally define the problem with an objective to maximize edge throughput under multiple constraints (e.g., resource constraint, model integrity, etc.), and prove that it is NP-hard. To solve the problem, we first propose an approximation algorithm based on randomized rounding to generate sub-optimal solutions. We then present an adjustment strategy that generates a feasible solution when the approximation algorithm violates any of the given constraints. To evaluate the proposed algorithms, we conduct comprehensive simulations based on state-of-the-art MTL models, Google cluster-usage trace, and four kinds of computing units. Extensive experiments show that the proposed approximation algorithm coupled with the adjustment strategy, outperforms state-of-the-art methods for all cases, in terms of edge throughput.

In vehicular edge computing (VEC), two-level scheduling both at intra-vehicle and inter-vehicle offers great potential to improve quality of services for deep neural network (DNN) inference. However, existing works on two-level scheduling failed to jointly consider load balance among vehicles and the selfishness of vehicles, which results in the absence of guarantee in quality of services. This paper seeks to fill this gap by formulating an incentive problem associated with two-level scheduling aimed at load balance for DNN inference in VEC, with the objective of maximize the system utility in VEC under the constraints of per task response time, per vehicle energy consumption, per vehicle utility guarantee, etc. Then, we prove the problem is NP-complete. A coalition based incentive algorithm, called CBA, is proposed. CBA makes intra-vehicle scheduling decisions by a heuristic strategy and it makes inter-vehicle scheduling decisions by a coalition game based strategy. The Nash-stable and convergence for CBA are proved. In addition, a deep reinforcement learning based algorithm, called DRL, is proposed to solve the formulated problem. DRL introduces a heuristic strategy to generate the intra-vehicle scheduling decisions, and it exploits deep reinforcement learning method to generate the inter-vehicle scheduling decisions. The proposed algorithms are evaluated on a platform with CPUs, SCALE-Sim, OSM and SUMO. Simulation results show that two proposed algorithms outperform the state-of-the-art methods for all cases, in terms of system utility. Compared with two baseline algorithms, CBA and DRL improve system utility by an average of 0.56× and 1.24×, respectively, for different numbers of vehicles.

Abstract Ridesharing is an effective approach to alleviate traffic congestion. In most existing works, drivers and passengers are assigned prices without considering the constraints of desired benefits. This paper investigates ridesharing by formulating a matching and pricing problem to maximize the total payoff of drivers, with the constraints of desired benefit and quality of experience. An efficient algorithm is proposed to solve the formulated problem based on coalitional double auction. Secondary pricing based strategy and sacrificed minimum bid based strategy are proposed to support the algorithm. This paper also proves that the proposed algorithm can achieve a Nash-stable coalition partition in finite steps, and the proposed two strategies guarantee truthfulness, individually rational and budget balance. Extensive simulation results on the real-world dataset of taxi trajectory in Beijing city show that the proposed algorithm outperforms the existing ones, in terms of average total payoff of drivers while meeting the benefits of passengers.

In Internet of Vehicles (IoV), it is critical to collect sufficient data for model training, to support vehicular intelligent applications. However, the environment of IoV is highly dynamic due to the mobility of vehicles, making it challenging to efficiently allocate resources for data collection. Additionally, timely training of machine learning models with collected data is important for accurate representation in a constantly changing environment. This article aims to improve the performance of model training by collecting sufficient data from vehicles in IoV. A system throughput maximization problem is formulated under the limited bandwidth, storage, and computing resources, which is an NP-hard problem. To solve the problem, an iterative algorithm, namely, the iterative algorithm based on approaching minimum bandwidth (IAMB), is proposed to preferentially collect data from the vehicles with sufficient data and reliable communication quality. Besides, a genetic algorithm, namely, the genetic algorithm based on approaching minimum bandwidth (GAMB), is proposed to further improve the probability of superior individual by replacing operation. We also customize three greedy strategy-based algorithms as the baselines. Extensive experimental results show that our proposed algorithms outperform the baseline algorithms for all cases. Specifically, IAMB and GAMB can improve the throughput by up to 5% and 8%, respectively, compared with baseline algorithms. In addition, the customized genetic algorithm is also superior to the iterative algorithm on performance of system throughput. Moreover, the customized genetic algorithm is more stable than the proposed iterative algorithm in terms of system throughput for model training in the dynamic network environment.

Private car-based carpooling (PCC) has become an important transportation mode in our daily life. Unlike ride-hailing or taxi-based carpooling, PCC has two unique features that have yet to be fully explored: (i) A private-car driver has more bargaining space than a non-private car driver; (ii) There exists unfriendly congestion in private car-based carpooling if not handled well. Existing carpooling schemes are not tailored for PCC services with an oversimplified assumption that passengers pay detour fees and there is no guarantee on the passenger’s travel time. Consequently, such limitations not only harm the passenger’s carpooling incentive but also hurt the passenger’s quality of experience as well as the driver’s utility. We propose a novel framework for the double-sided preference-aware carpooling (D-SPAC) problem, after comprehensively addressing the above two unique features. We formulate the D-SPAC problem as a mixed-integer non-linear programming problem, which is proved to be NP-hard, to maximize the total utility of passengers while meeting the driver’s buyout asking price, traversal radius, passenger’s waiting time, budget and both sides’ detour length constraints. We design a coalitional double auction-based scheme that can better motivate both sides with guaranteed economic properties. We further design a deep reinforcement learning algorithm to cope with the position dynamics and the changing user requests. Extensive experimental results based on real-world data sets demonstrate the effectiveness of proposed algorithms over three benchmark algorithms.

In vehicular edge computing, efficient strategies for model deployment and task offloading offer tremendous potential to reduce response time for machine learning inference. However, existing works do not pay much attention to that there are shared structures among different types of inference tasks. This limits the improvement in response time. This paper aims to fill this gap by investigating a share-aware joint model deployment and task offloading problem for multi-task inference in vehicular edge computing. We formulate the problem with an objective to minimize the total response time of all inference requests, under constraints of per task response time, per roadside unit storage capacity, etc. We prove that the formulated problem is NP-hard. To solve the problem, a time period aware algorithm, called TPA, is proposed with guaranteed approximation ratio. In TPA, an iterative approach is designed to solve the problem of maximizing system throughput during a certain time period. Then, the certain time period approximates to the minimum time period of completing all requests. The algorithms are evaluated in the environment comprising two CPUs, two GPUs, state-of-the-art multi-task learning models and the dataset of Google cluster-usage trace. Simulation results derived from this environment show that, the proposed TPA outperforms the state-of-the-art methods for all cases, in terms of the total response time of all requests. For example, TPA can significantly reduce the total response time by at least$73.72\%$for different numbers of RSUs considered, compared with state-of-the-art methods.

The intrinsic nature of non-independent and identically distributed datasets on heterogeneous devices slows down the distributed model training process and reduces the training accuracy. To settle this problem, we propose a dataset reconstruction scheme to transform the data distribution of training device’s dataset into independent and identically distributed dataset via data exchange among trusted devices. For energy efficiency, we further consider power control for the devices. We then formulate an optimization problem, which is a mixed integer non-linear programming problem, to minimize the total energy consumption for each round of distributed training. Due to the NP-hardness and coupling property of the optimization problem, we decompose it into two subproblems for dataset reconstruction and power control, respectively. An approximation algorithm is designed to obtain a near-optimal auxiliary devices set for dataset reconstruction with minimum energy consumption, while meeting the variance constraint of the optimization problem. We prove that approximation algorithm has a worst-case approximation ratio of$1+\ln |\boldsymbol{\Omega }_{i}(t)|$, where$|\boldsymbol{\Omega }_{i}(t)|$is the required data samples for dataset reconstruction of each training device. For power control, we design a dynamic programming algorithm to further reduce the energy consumption. For comparison, we propose three benchmark schemes that adopt either one of the algorithms or neither. We also customize three baseline algorithms based on the state-of-the-arts to compare with our proposed algorithm. Numerical results show that, our proposed algorithm outperforms three benchmarks on the average energy consumption for one round for different cases. When varying the labels that each device owns, our proposed algorithm outperforms the other three baseline algorithms on training accuracy. Besides, when setting a target accuracy, our proposed algorithm always has the lowest energy consumption.

Abstract Parameter servers (PSs) placement is one of the most important factors for global model training on distributed deep learning. This paper formulates a novel problem for placement strategy of PSs in the dynamic available storage capacity, with the objective of minimizing the training time of the distributed deep learning under the constraints of storage capacity and the number of local PSs. Then, we provide the proof for the NP-hardness of the proposed problem. The whole training epochs are divided into two parts, i.e. the first epoch and the other epochs. For the first epoch, an approximation algorithm and a rounding algorithm are proposed in this paper, to solve the proposed problem. For the other epochs, an adjustment algorithm is proposed, by continuously adjusting the decisions for placement strategy of PSs to decrease the training time of the global model. Simulation results show that the proposed approximation algorithm and rounding algorithm perform better than existing works for all cases, in terms of the training time of global model. Meanwhile, the training time of global model for the proposed approximation algorithm is very close to that for optimal solution generated by the brute-force approach for all cases. Besides, the integrated algorithm outperforms the existing works when the available storage capacity varies during the training.

Abstract Existing works on caching in multi-access edge computing focus on service caching and request routing. However, loading cost and execution time influenced by resource sharing have not been well exploited. To fill this gap, we investigate the joint optimization problem over deep neural network (DNN) model caching and DNN request routing with edge collaboration in edge-enabled wireless sensor networks. A problem is formulated, with the objective of maximizing throughput, under constraints of budget, accuracy and latency etc. The proof of NP-hardness for the formulated problem is provided. To solve the problem, an approximation algorithm based on randomized rounding is presented. In addition, the approximation ratio for the presented algorithm is proved to be $1/(1-\sqrt{4\ln S/\xi^\dagger})$, where $S$ is the number of edge servers and $\xi^\dagger$ is the objective value from linear relaxation. Extensive experiments demonstrate that the system throughput for the presented algorithm can be improved by 58.8% on average, compared with that of the baseline algorithm.

Abstract In wireless sensor networks (WSNs), wireless sensor nodes can be equipped with deep neural network accelerators to deal with the computation challenges in distributed training. However, the communication overhead of distributed training and the limited battery capacity of sensor nodes still impedes the broad deployment of distributed training applications. This article investigates the distributed training in WSNs by formulating an aggregation‐aware routing problem into a non‐linear integer programming problem. The objective of the formulated problem is to reduce the training time using data aggregation‐aware routing under the constraints of memory size and energy cost. Meanwhile, the NP‐Hardness of the formulated problem is proved in this article. Then, an intra‐cluster aggregation‐aware routing algorithm is proposed. The proposed algorithm accelerates the transmission of the data packet by integrating the K‐Means clustering and shortest path routing to choose the aggregators and the route paths. Extensive experiments demonstrate that the proposed algorithm outperforms two classical clustering routing algorithms UC‐LEACH and K‐Means by 29% and 37% in terms of average training time, and reducing the energy consumption by 21% and 15%, respectively.

In vehicular networks, task scheduling at the microarchitecture-level and network-level offers tremendous potential to improve the quality of computing services for deep neural network (DNN) inference. However, existing task scheduling works only focus on either one of the two levels, which results in inefficient utilization of computing resources. This paper aims to fill this gap by formulating a two-level scheduling problem for DNN inference tasks in a vehicular network, with an objective of minimizing total weighted sum of response time and energy consumption for all tasks under the following constraints: per task response time, per vehicle energy consumption, per vehicle storage capacity. We first formulate the problem and prove that it is NP-hard. A group transformation based algorithm, called GTA, is proposed. GTA makes scheduling decisions at the network-level using the group transformation based approach, and at the microarchitecture-level using a greedy strategy. In addition, an algorithm, denoted as DRL, is proposed to decrease total weighted sum of response time and energy consumption for all tasks. DRL trains two models with deep reinforcement learning to achieve two-level scheduling. The proposed algorithms are evaluated on a platform consisting of a desktop, Raspberry Pi, Eyeriss, OSM, SUMO, NS-3. Simulation results show that DRL outperforms the state-of-the-art methods for all cases, while the proposed GTA outperforms the state-of-the-art methods for most cases, in terms of total weighted sum of response time and energy consumption. Compared with four baseline algorithms, GTA and DRL reduce the total weighted sum of response time and energy consumption by 41.49% and 62.38%, on average respectively, for different numbers of tasks.

Convolutional neural networks (CNNs) (including 2D and 3D convolutions) are popular in video analysis tasks such as action recognition and activity understanding. Fast algorithms such as fast Fourier transforms (FFTs) are promising in significantly reducing computation complexity by transforming convolution into frequency domain. In frequency space, conventional spatial convolutions are replaced with simpler element-wise complex multiplications. Conventional application-specific-integrated-circuit (ASIC) based frequency-domain accelerators can achieve effective performance boost but come at the cost of significant energy consumption, owing to the hierarchical memory organization. We propose a frequency-domain resistive random access memory (ReRAM) based inference accelerator called FDA that can process element-wise complex multiplication in memory for both 2D and 3D CNNs. Each ReRAM-based frequency-domain process element (PE) with two ReRAM cells can perform an element-wise complex multiplication in two continuous execution cycles. We then provide a flexible dataflow to alleviate the redundant data movements by frequency-domain data reuse and inherent symmetrical characteristic for both 2D and 3D convolutions. Evaluation results based on representative both 2D and 3D CNN benchmarks demonstrate that FDA outperforms state-of-the-art baselines with better performance and energy efficiency.

Summary Blockchain has been applied in wide range of fields to guarantee security. However, it has been very challenging for blockchain to flourish in mobile environment with limited resources. Existing studies mainly assume that single mobile user can buy the whole resources from edge servers in mobile blockchain. This paper formulates the problem of maximizing the social welfare for computation offloading in mobile blockchain. A three‐stage auction scheme with approximation ratio of based on group‐buying mechanism is proposed to allocate edge server resources for mobile blockchain applications. In the first stage, the miners are divided into groups, and a Vickrey–Clarke–Groves based auction is proposed to determine the bid of each group for each edge server. In the second stage, a matching algorithm is proposed to match edge servers and Access Points for maximizing the profit of edge servers. In the third stage, the edge server resources are allocated to mobile users for mining base on the results in the above stages. We prove that our auction scheme guarantees truthfulness, individual rationality and budget balance. Simulation results show that, the social welfare of our scheme is improved by 33.78%, 21.84%, 19.69%, and 6.69% for 1000 miners, compared with the existing works.

Load balance in vehicular ad hoc networks (VANETs) is a challenge in vehicle-to-vehicle computation offloading, due to stochastic requests of users, heterogeneous service capabilities and high mobility of vehicles, etc. This paper aims to fill this gap by formulating a problem for load balance in a VANET, with the objective of minimizing the maximum load under transmit power, storage capacity, per task completion time and energy consumption constraints. The formulated problem is proved to be NP-hard, then it is investigated by decomposing it into two subproblems, i.e., how to offload tasks for the case of fixed transmit power and how to adjust transmit power for the given offloading decision. For the first subproblem, an approximation algorithm is proposed by offloading the tasks in the vehicle with the maximum load to the vehicle with minimum load. Meanwhile, a deep reinforcement learning algorithm is proposed, in order to focus on the network dynamics. A coalition based algorithm, a distributed coalition based algorithm, as well as an incentive algorithm based on deep reinforcement learning, are proposed to maximize the total payoff for the selfishness of vehicles. 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 open street map, SUMO, NS-3 and dataset of Google cluster-usage traces. Simulation results show that, the proposed algorithms outperform three state-of-the-art works for most cases, in terms of the maximum load. The proposed distributed algorithm can significantly accelerate the proposed centralized algorithm with acceptable increase in maximum load. Besides, the load can be further reduced by the proposed adjustment strategy.

Multi-access edge computing (MEC) is emerging to improve the quality of experience of mobile devices including internet of things sensors by offloading computing intensive tasks to MEC servers. Existing MEC-enabled cooperative computation offloading works focus on the optimization of total energy consumption but fail to exploit multi-relay diversity and min-max fairness of energy consumption on participated sensors. We explore a typical wireless sensor network with multi-source, multi-relay, and one edge server, where relay nodes can provide both cooperative communication and computation services. We divide the energy efficiency optimization problem into two sub-problems: One is to minimize the weighted average total energy consumption per time slot, and the other is to minimize the maximum weighted energy consumption. For the first sub-problem, we propose an optimal algorithm named as optimal weighted average total energy consumption algorithm (OTCA) based on bipartite matching. For the second sub-problem, greedy algorithm for fairness guarantee (GAF) is proposed with an approximation ratio of (1 + ε), where ε is a small positive constant. Extensive numerical results show that OTCA outperforms the baseline algorithms by 26.7–77.4% on the average total weighted energy consumption while GAF outperforms benchmark algorithms by 30.7–84.4%. NS-3 simulation experiments comply with numerical results.

Fog computing has become an emerging distributed computing paradigm to provide services with low latency and high throughput. However, load unbalance is serious due to the difference in geography, which results in performance deterioration and low utilization of resources in the fog network. In this paper, the load is the tradeoff between the delay and energy consumption for fog nodes. Meanwhile, the problem of minimizing the maximum load in the homogeneous fog network is formulated and its NP-hardness is proved. Then, a greedy algorithm is proposed for solving the problem by giving the preference to offloading the task in the fog node with the maximum load to the fog node with the minimum load in the network. Moreover, for solving the problem with consideration of selfishness of fog nodes, a coalition based algorithm is proposed to encourage the fog nodes with a light load to share their resources to reduce the maximum load. We evaluate the performance of the proposed algorithms on NS-3 and simulation results show that the proposed algorithms outperform the existing algorithm about 40% in terms of the maximum load.

Vehicular fog computing (VFC) has become an appealing paradigm to provide services for vehicles and traffic systems. However, high mobility is one of the great challenges to the communication and computation service qualities in VFC. A network model for directional vehicle mobility is proposed in this paper to guarantee the service qualities of vehicles in VFC. In the model, vehicles are configured into three vehicular subnetworks according to their turning directions at the next crossing. For each subnetwork, vehicles communicate with each other via vehicle-to-vehicle communication, and with roadside units via vehicle-to-infrastructure communication. The aim is to minimize the average response time of the tasks originated from vehicles. By carefully choosing neighboring vehicles as task processing helpers, a greedy algorithm is proposed to solve the mentioned optimization problem. Besides, two bipartite matching based algorithms, named BMA1and BMA2, are proposed by exploiting Kuhn-Munkras approach and minimum-cost maximum-flow approach, respectively. Performance of the proposed model and the offloading algorithms are evaluated on the combined simulation platform by open street map, SUMO and NS-3. Simulation results show that, the proposed model outperforms four existing models in terms of average response time, when the five models have similar number of unsuccessful tasks. Moreover, the proposed BMA1and BMA2are superior to the existing greedy algorithm in terms of the average response time of tasks, and the proposed greedy algorithm significantly accelerates the generation of offloading decisions in comparison to BMA1, BMA2and the existing greedy algorithm.

Mobile edge computing enables the execution of compute-intensive applications, e.g. deep learning applications, on the end devices with limited computation resources. However, the deep learning applications bring the performance bottleneck in mobile edge computing, due to the movements of a large amount of data incurred by the large number of layers and millions of weights. In this paper, the computing model for parallel deep learning applications in mobile edge computing is proposed, by considering the occupancy allocation of processors, cost of context switch, and multi-processors in edge server and remote cloud. The problem of minimizing the completion time for deep learning applications is formulated, and the NP-hardness of the problem is proved. To solve the problem, an integrated algorithm by merging and scheduling is proposed. Moreover, a real-world distributed platform is developed for evaluating the proposed algorithm. Experimental results show that, the completion time of deep learning application for the proposed algorithm is decreased by 63% and 75%, respectively, without extra control costs, compared with the existing algorithms.