As a promising technique for offloading computation tasks from mobile devices, Unmanned Aerial Vehicle (UAV)- assisted Mobile Edge Computing (MEC) utilizes UAVs as computational resources. A popular method for enhancing the quality of service (QoS) of UAV-assisted MEC systems is to jointly optimize UAV deployment and computation task offloading. This imposes the challenge of dynamically adjusting UAV deployment and computation offloading to accommodate the changing positions and computational requirements of mobile devices. Due to the real-time requirements of MEC computation tasks, finding an efficient joint optimization approach is imperative. This paper proposes an algorithm aimed at minimizing the average response delay in a UAV-assisted MEC system. The approach revolves around the joint optimization of UAV deployment and computation offloading through convex optimization. We break down the problem into three sub-problems: UAV deployment, Ground Device (GD) access, and computation tasks offloading, which we address using the block coordinate descent algorithm. Observing the NP-hardness nature of the original problem, we present near-optimal solutions to the decomposed sub-problems. Simulation results demonstrate that our approach can generate a joint optimization solution within seconds and diminish the average response delay compared to state-of-the-art algorithms and other advanced algorithms, with improvements ranging from 4.70% to 42.94%.

We formulate and analyze a generic coverage optimization problem arising in wireless sensor networks with sensors of limited mobility. Given a set of targets to be covered and a set of mobile sensors, we seek a sensor dispatch algorithm maximizing the covered targets under the constraint that the maximal moving distance for each sensor is upper-bounded by a given threshold. We prove that the problem is NP-hard. Given its hardness, we devise four algorithms to solve it heuristically or approximately. Among the approximate algorithms, we first develop randomized $(1-1/e)$-optimal algorithm. We then employ a derandomization technique to devise a deterministic $(1-1/e)$-approximation algorithm. We also design a deterministic approximation algorithm with nearly ${▵}^{-1}$ approximation ratio by using a colouring technique, where $▵$ denotes the maximal number of subsets covering the same target. Experiments are also conducted to validate the effectiveness of the algorithms in a variety of parameter settings.

Clouds, such as Amazon Infrastructure-as-a-Service (IaaS) clouds and EMC Hybrid Cloud, impose growing requirements of resource-efficiency scheduling. The bounded flexible scheduling (BFS) problem is one of the problems proposed to meet such requirements. In BFS, we are given a set of identical machines and a set of jobs, each of which is with a value, a workload, a deadline and a parallelism degree, i.e., the maximum number of machines on which the job can execute concurrently. The problem is to compute an assignment of the given jobs to the machines, such that the total value of the jobs successfully completed by their deadlines is maximized. This paper presents a factor C/C-k approximation algorithm for BFS, where k is the maximum parallelism degree and C is the capacity of the system (i.e., the number of machines). Since C ≫ k in BFS, our result significantly improves the known best approximation ratio of (2C-k/C-k)(1-ϵ) for tight deadlines [17], and C/C-k · s/s-1/s for loose deadlines [18] on a slackness ratios > 1 that is the maximum ratio between a job's earliest actual finish time and its deadline. We first propose feasibility condition to determine whether an instance of BFS is feasible, i.e., whether there exists a scheduling according to which all jobs can finish before their deadlines, which is the key to achieve the ratio improvement of our algorithm. To prove the correctness of the feasibility condition, we give a simple linear program (LP) for a weaker version of BFS, and show that it is with an integral polyhedron and hence the version of BFS is polynomial-time solvable. Then we present a greedy algorithm and its equivalent primal-dual algorithm for the complementary problem of BFS. Both algorithms have an approximation ratio of C/C-k, and time complexity O(n ² + nT), where n is the number of jobs and T is the number of time slots. As a by-product, we show that the BFS admits a polynomial-time approximation scheme (PTAS) when T is fixed.