Unmanned Aerial Vehicle (UAV) technology is a promising solution for providing high-quality mobile services (e.g., edge computing and local caching) to ground users. How to dynamically determine a UAV swarm's cooperative path planning to best meet many users' spatio-temporally distributed demands is an important question but unaddressed in the literature. Regarding a single UAV's path planning design, we manage to substantially simplify the traditional dynamic program and propose an optimal algorithm of low computation complexity. After coordinating a large number K of UAVs, this simplified dynamic optimization problem becomes intractable and we alternatively present a fast iterative cooperation algorithm with provable approximation ratio$1-(1-\frac{1}{K})^{K}$in the worst case. To relax UAVs' battery capacity limit for sustainable service provisioning, we further allow UAVs to travel to charging stations in the mean time and thus jointly design UAVs' path planning over users' locations and charging stations. We successfully transform the problem to an integer linear program by creating novel directed acyclic graph of the UAV-state transition diagram, and propose an iterative algorithm with constant approximation ratio.

Recent years have witnessed an emerging class of real-time applications, e.g., autonomous driving, in which resource-constrained edge platforms need to execute a set of real-time mixed Deep Learning (DL) tasks concurrently. Such an application paradigm poses major challenges due to the huge compute workload of deep neural network models, diverse performance requirements of different tasks, and the lack of real-time support from existing DL frameworks. In this paper, we present RT-mDL, a novel framework to support mixed real-time DL tasks on edge platform with heterogeneous CPU and GPU resource. RT-mDL aims to optimize the mixed DL task execution to meet their diverse real-time/accuracy requirements by exploiting unique compute characteristics of DL tasks. RT-mDL employs a novel storage-bounded model scaling method to generate a series of model variants, and systematically optimizes the DL task execution by joint model variants selection and task priority assignment. To improve the CPU/GPU utilization of mixed DL tasks, RT-mDL also includes a new priority-based scheduler which employs a GPU packing mechanism and executes the CPU/GPU tasks independently. Our implementation on an F1/10 autonomous driving testbed shows that, RT-mDL can enable multiple concurrent DL tasks to achieve satisfactory real-time performance in traffic light detection and sign recognition. Moreover, compared to state-of-the-art baselines, RT-mDL can reduce deadline missing rate by 40.12% while only sacrificing 1.7% model accuracy.

Unmanned Aerial Vehicle (UAV) technology is a promising solution for providing high-quality mobile services (e.g., edge computing, fast Internet connection, and local caching) to ground users, where a UAV with limited service coverage travels among multiple geographical user locations (e.g., hotspots) for servicing demands locally. It is necessary for different UAVs to cooperate with each other for servicing many users, and how to determine their cooperative path planning to best meet many users' spatio-temporally distributed demands is an important question. This paper is the first to design and analyze cooperative path-planning algorithms of a UAV swarm for optimally servicing many spatial locations with dynamic user arrivals and waiting deadlines in the time horizon. For each UAV, it needs to decide whether to wait at the current location or chase a newly released demand in another location, under upper coordination with the other UAVs in the swarm. For each UAV's routing problem even without coordinating with the rest UAVs, it follows dynamic programming structure and is difficult to solve directly given many user demands. We manage to simplify and propose an optimal algorithm of fast computation time (only polynomial with respect to both the numbers of user locations and user demands) for returning the UAV's optimal path-planning. When a large number |K| of UAVs are coordinating, the dynamic programming simplification becomes intractable. Alternatively, we present an iterative cooperation algorithm with approximation ratio 1 - (1 - 1/|K| )|K|in the worst case, which is proved to obviously outperform the traditional idea of partitioning UAVs to serve different user/location clusters separately. Finally, we conduct simulation experiments to show that our algorithm's average performance is close to the optimum.

We study the scheduling problem with calibrations. In 2013, Bender et al. (SPAA '13) proposed a theoretical framework for the problem. Jobs of unit processing time with release times and deadlines are to be scheduled on parallel identical machines. The machines need to be calibrated to run jobs while a single calibration remains valid on a machine only for a time period of length T. The objective is to find a schedule that completes all jobs within their timing constraints and minimizes the total number of calibrations. In this paper, we aim to design an approximation algorithm to solve the problem. We propose a dynamic programming algorithm with polynomial running time when the number of machines is constant. In addition, we give a PTAS when the number of machines is input.

The rapid development of the Real-Time and Embedded System (RTES) has increased the requirement on the processing capabilities of sensors, mobiles and smart devices, etc. Meanwhile, energy efficiency techniques are in desperate need as most devices in RTES are battery powered. Following the above trends, this work explores the memory system energy efficiency for a general multi-core architecture. This architecture integrates a local memory in each processing core, with a large off-chip memory shared among multiple cores. Decisions need to be made on whether tasks will be executed with the shared memory or the local memory to minimize the total energy consumption within real-time constraints. This paper proposes optimal schemes as well as a polynomial-time approximation algorithm with constant ratio. The problem complexity analysis for different task and system models is also presented. Experimental results show that the proposed approximation scheme performs close to the optimal solution in average.

In this paper we study the classical scheduling problem of minimizing the total weighted completion time on a single machine with the constraint that one specific job must be scheduled at a specified position. We give dynamic programs with pseudo-polynomial running time, and a fully polynomial-time approximation scheme (FPTAS).

In sensitive applications, machines need to be periodically calibrated to ensure that they run to high standards. Creating an efficient schedule on these machines requires attention to two metrics: ensuring good throughput of the jobs, and ensuring that not too much cost is spent on machine calibration. In this paper we examine flow time as a metric for scheduling with calibrations. While previous papers guaranteed that jobs would meet a certain deadline, we relax that constraint to a tradeoff: we want to balance how long the average job waits with how many costly calibrations we need to perform.

In this paper, we propose the optional preference model for the facility location game with two heterogeneous facilities on a line. Agents in this new model are allowed to have optional preference, which gives more flexibility for agents to report. Aiming at minimizing maximum cost or sum cost of agents, we propose different deterministic strategy-proof mechanisms without monetary transfers. Depending on which facility the agent with optional preference cares for, we consider two variants of the optional preference model: Min (caring for the closer one) and Max (caring for the further one). For the Min variant, we propose a 2-approximation mechanism for the maximum cost objective, as well as a lower bound of 4/3, and a (n/2+1)-approximation mechanism for the sum cost objective, as well as a lower bound of 2. For Max variant, we propose an optimal mechanism for the maximum cost objective and a 2-approximation mechanism for the sum cost objective.

The rapid development of the Internet of Things (IoT) has increased the requirement on the processing capabilities of sensors, mobile phones and smart devices. Meanwhile, energy efficiency techniques are in desperate need as most devices in the IoT systems are battery powered. Following the above two trends, this work explores the memory system energy efficiency for a general multi-core architecture. This architecture integrates a local memory in each processing core, with a large off-chip memory shared among multiple cores. Decisions need to be made on whether tasks will be executed with the shared memory or the local memory to minimize the total energy consumption within real-time constraints. This paper proposes optimal schemes as well as a polynomial-time approximation algorithm with constant ratio. The complexity analysis of the problem for different task and system models is also presented. Experimental results show that the proposed approximation algorithm performs close to the optimal solution in average.