This paper addresses theJoint deployment ofUnmanned aerial vehicles (UAVs) and surveillance caMeras withPath planning (JUMP), aiming to deploy a fixed number of UAVs and budget-limited surveillance cameras, to achieve continuous omnidirectional monitoring. Specifically, the objective is to maximize the monitoring durations of target objects in each of all horizontal directions within a given task duration. We propose an approach for JUMP, which is proved to be NP-hard. Our approach achieves a$\frac{1}{6}-\varepsilon _{1}$approximation ratio in general and$\frac{1}{4}-\varepsilon _{1}$when camera costs are uniform. Firstly, we introduce spatio-temporal discretization to approximate JUMP. Secondly, we partition the solution space of JUMP from spatial perspective and refine the space by addressing a variant of obstacle-avoiding shortest path problem spatio-temporal perspective. Thirdly, we reformulate the problem as a classical problem of Monotone Submodular set function Maximization with one partition Matroid and two Knapsack constraints (MSMMK). To address MSMMK, we propose a$\frac{1}{6(1+\varepsilon )}$approximation algorithm, which outperforms the state-of-the-art with the same time complexity in general. Specifically, our algorithm achieves a$\frac{1}{4(1+\varepsilon )}$approximation ratio for special cases. Simulation results demonstrate our proposed approach outperforms five benchmark algorithms, yielding enhancements 13%-1446%. Moreover, field experiment results indicate that our approach surpasses comparison algorithms, achieving enhancements 23%-265%.

High-definition (HD) cameras for surveillance and road traffic have experienced tremendous growth, demanding intensive computation resources for real-time analytics. Recently, offloading frames from the front-end device to the back-end edge server has shown great promise. In multi-stream competitive environments, efficient bandwidth management and proper scheduling are crucial to ensure both high inference accuracy and high throughput. To achieve this goal, we propose BiSwift, a bi-level framework that scales the concurrent real-time video analytics by a novel adaptive hybrid codec integrated with multi-level pipelines, and a global bandwidth controller for multiple video streams. The lower-level front-back-end collaborative mechanism (called adaptive hybrid codec) locally optimizes the accuracy and accelerates end-to-end video analytics for a single stream. The upper-level scheduler aims to accuracy fairness among multiple streams via the global bandwidth controller. The evaluation of BiSwift shows that BiSwift is able to real-time object detection on 9 streams with an edge device only equipped with an NVIDIA RTX3070 (8G) GPU. BiSwift improves 10%~21% accuracy and presents$1.2\sim 9\times $throughput compared with the state-of-the-art video analytics pipelines.

Edge-end collaborative learning trains models with exchanged knowledge through distributed interaction, alleviating the cloud's burden. Edge-end heterogeneous collaborative learning further enables edge servers and end devices to train models of different scales in parallel based on their computational capabilities. This technology supports various applications in different resource conditions and improves server resource utilization. However, implementing it is challenging due to heavy communication costs and high global costs (time and energy). To this end, this paper proposes a novel prototype-based edge-end heterogeneous collaborative learning method and an optimization algorithm, which improves model performance and reduces training costs. We first use prototypes to perform collaborative learning and analyze the convergence. Prototypes are computed as mean feature vectors from different classes. The aggregated prototypes help capture class information on end devices and generate data on edge servers. Then, we study how to determine prototype selection and edge association to minimize training time, energy consumption, and prototype approximation error under a limited reward budget, which is proven to be NP-hard. We split the original problem into two subproblems. The first is solved in the closed form. Through approximation and reformulation, the second is transformed into a submodular maximization problem with knapsack and matroid constraints. On this basis, we propose an approximation algorithm with a theoretical guarantee. Finally, by simulation and field experiments, our method takes 3.61% of communication costs to improve heterogeneous edge and end models' accuracy by at least 5.16% and 2.77% compared with five baselines. The proposed algorithm outperforms others by at least 9.78% in terms of global cost.

Deep learning-based intelligent perception has become pivotal in enhancing the effectiveness of UAV monitoring systems. However, deploying complex models on resource-constrained UAV swarms presents significant shortcomings: existing approaches either compromise model accuracy to enable lightweight deployment or introduce communication delays through cloud offloading. More critically, they generally overlook the fundamental prerequisite of monitoring tasks: maintaining stable coverage of the target area. To address this issue, we proposes AirInfer, an innovative collaborative UAV inference framework with critical zones coverage. We formulate a joint optimization problem of deep learning model partitioning and UAV swarm deployment, to minimize end-to-end inference latency. This complex problem can be decomposed into two sub-problems: model partitioning and UAV deployment, which can be solved efficiently using dynamic programming and successive convex approximation, respectively. On this basis, an iterative algorithm is devised to provide guarantees of$\epsilon$-local convergence. Theoretical analysis and experimental results demonstrate that AirInfer not only guarantees blind spot-free monitoring but also reduces inference latency by at least 37 % compared to existing solutions, achieving a balance between perception performance and mission reliability.

Edge-end collaborative learning greatly reduces latency by eliminating the need for processing on the cloud side, showing promising results in machine learning applications due to collaborating on training tasks through the computational resources of edge servers and end devices. However, current edge-end collaborative learning methods suffer from unbearable latency which result from heavy transmission burden and long synchronization time. We propose a new Prototype-based Semi-Asynchronous Edge-end Collaborative Learning approach (ProSACL) that carefully integrates prototype-based end-side training and edge clustering, allowing any end device to synchronize knowledge, significantly reducing the time spent on training latency. Our approach includes (1) prototype training and asynchronous prototype transfer on end devices: Unlike traditional training methods, we use the average of the same class of feature vectors, i.e., the prototype, as the knowledge transfer means, which significantly reduces the transfer burden and eliminates the need for end devices to wait for other devices to finish. (2) prototype-based clustering and asynchronous aggregation on the edge server: The end devices are segmented by prototype-based clustering to obtain unbiased prototypes for performance enhancement, and prototypes from different rounds are aggregated for fine-grained knowledge transfer. We evaluate the proposed approach by training on three datasets, which show substantial performance improvement compared to previous work.

Unmanned aerial vehicle (UAV) air-to-air (A2A) communications are emerging as a vital component of future low-attitude wireless networks. This paper introduces a novel A2A channel model and evaluates its statistical properties through analysis and experimental validation. The proposed model adopts a quasi-deterministic approach that incorporates rooftop specular reflection (RSR), distinguishing it from traditional ground reflection. Airframe occlusion (AO) is represented using a diffraction-based segmented function to accurately characterize its impact on the line-of-sight path. Key statistical indicators are derived based on the proposed model, and numerical results show that the presence of RSR reduces both the level crossing rate and average fade duration. Enhanced Rician factor improves spatial-temporal correlation, while higher transmission power and lower UAV mobility reduce outage probability. Compared to standardized models, the proposed model demonstrates improved capability in capturing the effects of RSR and AO while maintaining compatibility. Additionally, an A2A channel measurement platform leveraging the high autocorrelation properties of Zadoff-Chu sequences is developed to extract channel impulse response. Experimental measurements of channel capacity, outage probability, and root mean square delay spread closely align with simulated results, validating the model’s accuracy and reliability.

Federated learning (FL), as an innovative paradigm of distributed learning, provides reliable support for the growing edge intelligence (EI). The limitations of traditional FL’s reliance on ground base stations (BSs) make the development of aerial server unmanned aerial vehicles (UAVs) inevitable, thereby developing the air-ground integrated FL (AGIFL). However, current efforts predominately focus on static offline training based on existing datasets and some efforts consider online training in dynamic sample environments, where new samples need to be fully pre-trained to determine sample quality. To this end, we study how to realize high-performance of FL in dynamic environment without training all samples. Specifically, we formulate a joint optimization problem for sample selection, UAV deployment, and resource distribution aiming to minimize the trade-off between the user energy consumption and FL performance. To address the optimization problem without explicit expression, we employ meta-learning to derive an upper bound on the gradient norm of the loss function to evaluate learning performance, and describe how time-varying small-batch ratios affect this bound. Then, we propose an optimization algorithm that ensures convergence, capitalizing on the block coordinate descent techniques. To demonstrate the efficacy of our algorithm, we conduct both extensive simulations and proof-of-concept field experiments. The findings indicate an average improvement of approximately 39% in reducing the objective value when compared to the benchmarks.

Deep Neural Networks (DNNs) are now widely used in Low Earth Orbit (LEO) satellites, such as in remote sensing and environmental monitoring. DNN tasks are generally resource-intensive, while the resources of LEO satellites including computation and storage resources are usually limited, which implies directly running high-precision and complex DNNs on them is extremely challenging. A promising way is leveraging the layered structure of DNNs and executing DNN tasks collaboratively between satellites and ground, i.e., satellite-terrestrial collaborative inference. However, most existing works about satellite- terrestrial collaborative inference mainly focus on the optimization of DNN offloading strategy in terms of latency and energy minimization, without considering how to minimize the highly precious satellite communication resources in the collaboration. In this paper, we study how to jointly optimize the offloading decision and satellites' communication bandwidth, to achieve the minimization of weighted sum of latency, energy consumption, and communication bandwidth consumption. The aforementioned problem is a Mixed Integer Nonlinear Programming (MINLP) problem and hard to resolve. We design an alternating optimization algorithm combining branch-and-bound and gradient descent methods (AO-SA) to obtain an efficient solution. Extensive simulations validate the efficiency of the proposed algorithm: compared to existing satellite-terrestrial offloading algorithms, it improves the performance in terms of latency and energy consumption by up to 31 %, while saving the bandwidth resource of satellites by 28 % on average.

Recent advancements in unmanned aerial vehicle (UAV) technology have propelled the popularity of edge intelligence (EI) applications with deep learning in UAV swarm. Nevertheless, the high computational demands of deep neural networks (DNNs) conflict with the limited computing power and battery capacity of UAV. Furthermore, many UAV applications require real-time performance such as object detection and recognition. In this paper, we study how to achieve fast DNN inference in UAV swarm by the collaboration of multiple UAVs, and formulate the problem of minimizing the completion time of a series of arriving DNN inference tasks, under memory and energy constraints. To solve the aforementioned challenging problem with combinatorial explosion, we propose an efficient solution exploiting deep reinforcement learning (DRL) with action space simplification to find the allocation strategy of each DNN inference task within a resource-constrained UAV swarm. Simulation results validate the effectiveness of the proposed solution compared to five benchmark algorithms.

Federated learning (FL) as an emerging distributed machine learning (ML) paradigm enables participants to train their on-device data locally and share model parameters with others by the parameter server. Differing from the centralized ML, FL splits the high requirements of training data and computing power from the server to clients, which is well adapted to unmanned aerial vehicle (UAV) swarms with scattered nodes, heterogeneous data, and limited computing power. However, pre-trained models are unsatisfactory in unfamiliar scenes and most existing approaches fail to concentrate on the communication-sensitivity and real-time requirements in UAV-enabled FL scenarios. To address this problem, this paper proposes participant and sample selection for efficient online federated learning in UAV swarms (FedOL). Through the combination of online learning and FL, UAVs can supplement real-time samples and quickly improve the model accuracy in unfamiliar scenes. Meanwhile, to reduce the training latency with expected model accuracy, FedOL allows the server UAV to select participants with high training utility, while the client UAVs select more important samples. We implement FedOL and deploy it on UAV embedded devices. Experimental results show that compared with existing FL approaches, FedOL speeds up by about 2.61× and reaches the final accuracy about 1.02× higher.

Airlines commonly need to take into consideration maximizing their profit while designing the hub-and-spoke network to obtain more market share and promote healthy development of aviation industry. Hence, in this article, we study the problem of multiple-allocation HUb and spoke network design for ROuting flight flows to maximize airline profit utility (HURO). That is, given a set of airport nodes, a set of flight flows with known origin positions and destination positions, finding a limited number of hub edges to transfer flows and determining routing allocation mode considering customer preference such that the overall transportation profit utility is maximized. To address HURO problem, we first consider a relaxed version of HURO (HURO-R for short). We prove that HURO-R falls into the realm of maximizing a submodular set function subject to a cardinality constraint, and propose an algorithm with a constant approximation ratio. Next, we design a two-level algorithm framework with a constant approximation ratio to address HURO. Besides, we consider variants of HURO, HURO-C and HURO-RU, and design approximation algorithms to address them. We conduct simulation experiments on standard dataset and field experiments to verify our theoretical findings. The results shows that our proposed algorithm can outperform other comparison algorithms by 75.28 percent.

Charger placement is an important problem in improving the quality of service in wireless rechargeable sensor networks. This paper studies the problem ofWireless ChArger PlacemeNt with Multiple (Directional) Antennas (WANDA). The problem is described as follows: given a set of wireless chargers equipped with multiple directional antennas and a set of wireless rechargeable sensors, determine the chargers' positions and orientations to maximize the overall charging utility. According to the relative positional relationship between the antennas, the problem is classified into Relative Orientation Fixed (WANDA-ROF) and Relative Orientation Unfixed (WANDA-ROU) situations. To address WANDA, we present a piecewise constant function to approximate the nonlinearity of charging power and propose an area discretization technique to reduce the infinite solution space to a limited one without performance loss. Then, we prove the monotonic submodularity of WANDA, and present a$\frac{1}{2}-\epsilon$approximation algorithm for the ROF situation and a$\frac{1}{2}-\epsilon$approximation algorithm for the ROU situation, all run in polynomial time. Finally, we conduct extensive simulation and experiments to show that our algorithms outperform comparison algorithms by at least 16% for ROF situation and 12% for ROU situation.

Unmanned aerial vehicles (UAVs) play an essential role in emergency cases and adverse environments for applications like disaster detection and mine exploration. To process the massive volume of sensing data generated by various sensory payloads in these applications, existing works either compress deep learning (DL) models to conduct onboard computing, or offload raw data back to the resourceful ground station with the help of relay UAVs due to base station damage. However, the former sacrifices the inference accuracy of DL models (up to 10% accuracy loss), while the latter achieves high accuracy at the cost of significant latency, due to limited wireless communication resources in the multi-hop transmission. To address the problem, exploiting the resources of the UAV swarm including both task UAVs and relay UAVs, we build up anall-skyautonomous computing (ASAP) system to autonomously conduct collaborative computing in the swarm, to achieve both high accuracy and low latency of sensing data processing. In detail, we first propose a novel UAV swarm-native collaborative computing architecture, considering the general hierarchy and clustering structure of UAV swarms, as well as the characteristic of DL model execution. We then design an elastic efficient task scheduler to allocate computing tasks for UAVs, and update the scheduling scheme online when some UAVs are unavailable, with the aid of a lightweight and accurate DL inference performance predictor. Finally, we design an adaptive inter-UAV data compressor, to adapt to the limited and dynamic communication resources between UAVs. Experiment results on 24 airborne computers and five real-world UAVs show that, the proposed system can perform collaborative computing in a timely manner and effectively deal with situations when some UAVs become unavailable.

Truck-drone systems, wherein trucks carrying drones drive to pre-planned positions and then free drones equipped with cameras to monitor a known number of objects with reported positions, have been used for various scenarios. An object's quality of monitoring (QoM) by a camera is defined as a function of camera focal length and monitoring distance. Improving the QoM would help downstream tasks, including object detection and recognition. The monitoring utility is the fusion of all the QoMs of an object from multiple cameras. This paper optimizes theDeploymentOfTrucksAndDrones forObject monitoring (DOTADO) problem,i.e., deploying a truck-drone system, where each drone is equipped with a varifocal camera, to maximize the overall monitoring utility for all objects. Firstly, we model the hybrid system and define monitoring quality and utility. Then, we discretize the solution space into deployment strategies with performance bound. To select deployment strategies, we prove the submodularity of the problem and propose a two-level greedy algorithm with a bounded approximation ratio. Finally, we devise an optimal method to adjust the strategy for energy saving and communication improvement without losing monitoring utility. We perform both simulations and field experiments to verify the proposed framework.

Mobile Edge Computing (MEC) technology can be implemented at cellular base stations, enabling flexible and configurable provisions of services for mobile users to access. Nevertheless, the conventional solutions mainly focus onstaticalservice provisioning, which ignores the dynamic nature of the arriving service requests. In this work, we first conduct comprehensive data-driven observations on over 4 million service requests throughout 9,800 base stations. Our key findings suggest that users’ demands intrinsically exhibit spatial and temporal patterns, which inevitably lead to performance degradation in statical service provisioning. Motivated by that, we design and implement MobiEdge, a predictive service provisioning system with online learning in wireless edge networks. We propose a graph embedding learning-based model for representation learning, thus to achieve accurate request prediction at different base stations. Then, based on the prediction of incoming service requests, we study the service provisioning reconfiguration problem, i.e., how to jointly optimize service placement and corresponding request scheduling across dual timescales, under constraints of network resources and the total budget. By leveraging the submodular technique, we transform the research issue into a submodular function maximization problem under the$q$-independence system constraint, where$q$is a positive constant related to the ratio of coefficients in constraint conditions. On this basis, we propose a$1/(1+q)$approximation algorithm with rigorous theoretical analysis on the bounded maximum utility. Extensive trace-driven evaluations are conducted over networks of different scales, and MobiEdge shows remarkable performance enhancements by achieving the accuracy of up to 98% in service prediction and an average utility of 92.9% to the optimal solution in service provisioning.

Optimizing deep neural network (DNN) models to meet quality of service (QoS) requirements in terms of accuracy and computation is of crucial importance for realizing efficient on-device inference in resource-constrained artificial intelligence of things (AIoT). However, most existing works can hardly satisfy the aforementioned QoS requirements since the intrinsic multi-scale characteristic of DNN structures has been seldom considered. In this paper, we formulate a QoS-ensured DNN model structure optimization problem as a novel multi-scale Markov decision process (MSMDP), which can collaboratively decide the DNN structures from different scales. To efficiently solve the above problem, we propose a multi-scale reinforcement learning (MSRL) algorithm, which jointly optimizes block and channel number by interactive multi-scale decision, while ensuring QoS by QoS-based decision evaluation and policy update. Extensive experiments are conducted in both the actual AIoT scenarios and public datasets for different tasks by using different AIoT devices. The results confirm that our proposed MSRL outperforms the baseline schemes in terms of QoS satisfaction, convergence performance, and complexity. Specifically, our algorithm respectively reduces 98.6% computation and 95.7% model size at most while ensuring the QoS compared with the state-of-the-art methods.

The proliferation of various mobile devices with massive data and improving computing capacity have prompted the rise of edge artificial intelligence (Edge AI). Without revealing the raw data, federated learning (FL) becomes a promising distributed learning paradigm that caters to the above trend. Nevertheless, due to periodical communication for model aggregation, it would incur inevitable costs in terms of training latency and energy consumption, especially in multi-cell edge networks. Thus motivated, we study the joint edge aggregation and association problem to achieve the cost-efficient FL performance, where the model aggregation over multiple cells just happens at the network edge. After analyzing the NP-hardness with complex coupled variables, we transform it into a set function optimization problem and prove the objective function shows neither submodular nor supermodular property. By decomposing the complex objective function, we reconstruct a substitute function with the supermodularity and the bounded gap. On this basis, we design a two-stage search-based algorithm with theoretical performance guarantee. We further extend to the case of flexible bandwidth allocation and design the decoupled resource allocation algorithm with reduced computation size. Finally, extensive simulations and field experiments based on the testbed are conducted to validate both the effectiveness and near-optimality of our proposed solution.

IEEE INFOCOM 2023 - IEEE Conference on Computer Communications, New York City, NY, USA, 17-20 May 2023

We study the problem of resilient service provisioning for edge computing (RSPE), i.e., how to determine a service placement strategy to maximize the expected overall utility by service provisioning, in the presence of uncertain service failures. RSPE is extremely challenging to tackle, because the explicit expression of its objective function is difficult to obtain, and it is a resilient max–min problem subject to knapsack constraints, which is unexplored so far and cannot be addressed by existing resilient optimization techniques. We first explore the potential properties of the implicit objective function, and reveal that it is monotone submodular under certain conditions. We further prove that the knapsack constraints form a$q$-independence system constraint, where$q>0$is a constant related to the constraints. We propose two novel solutions for the general RSPE and homogeneous case, respectively. First, for the general problem, we propose a “two-step greedy” algorithm achieving a constant approximation ratio within polynomial time. Second, for the homogeneous case where one of the knapsack constraints reduces to a matroid constraint, we propose an improved “first-greedy-then-local search” polynomial time algorithm achieving better approximation ratio than the previous one. Both extensive simulations and field experiments validate the effectiveness of our proposed algorithms.

Unmanned aerial vehicles (UAVs) have been widely used to perform search and tracking tasks in military and civil fields. To perform these tasks autonomously, a swarm of multiple UAVs need to be endowed with intelligence through machine learning (ML). However, the traditional centralized ML cannot be directly applied in UAV networks, since it is challenging to transmit raw data with limited bandwidth and energy budget. As a distributed manner, federated learning (FL) is more suitable for UAV networks than traditional ML schemes in order to boost edge intelligence for UAVs. Considering the limited energy supply of UAVs, we study how to minimize UAVs’ overall training energy consumption by jointly optimizing the local convergence threshold, local iterations, computation resource allocation, and bandwidth allocation, subject to the FL global accuracy guarantee and maximum training latency constraint. The formulated nonconvex mixed-integer programming problem is solved by a joint training and resource allocation optimization algorithm. In addition, we also study how to solve the problem considering fairness among different UAVs by changing the objective to minimizing the maximum energy consumption of UAVs, and extend the aforementioned approach to this problem. Our simulation results show that while satisfying both the training accuracy and latency constraints, the proposed algorithm can reduce more UAVs’ overall training energy consumption and the maximum energy consumption in the UAV swarm than four baseline schemes.

In this work, we study the problem ofRobustServerPlacement (RSP) for edge computing, i.e., in the presence of uncertain edge server failures, how to determine a server placement strategy to maximize the expected overall workload that can be served by edge servers. We mathematically formulate the RSP problem in the form of robust max-min optimization, derived from two consequentially equivalent transformations of the problem that does not consider robustness and followed by a robust conversion. RSP is challenging to solve, because the explicit expression of the objective function in RSP is hard to obtain, and it is a robust max-min problem with knapsack constraints, which is still an unexplored problem in the literature. We reveal that the objective function is monotone submodular, and propose two solutions to RSP. First, after proving that the involved constraints form a$p$-independence system constraint, where$p$is a parameter determined by the coefficients in the knapsack constraints, we propose an algorithm that achieves a provable approximation ratio in polynomial time. Second, we prove that one of the knapsack constraints is a matroid contraint, and propose another polynomial time algorithm with a better approximation ratio. Furthermore, we discuss the applicability of the aforementioned algorithms to the case with an additional server number constraint. Both synthetic and trace-driven simulation results show that, given any maximum number of server failures, our proposed algorithms outperform four state-of-the-art algorithms and approaches the optimal solution, which applies exhaustive exponential searches, while the proposed latter algorithm brings extra performance gains compared with the former one.

Thanks to the increasing number and massive coverage, delivery drones, equipped with various sensors, have demonstrated significant but unexplored potentials for large-scale and low-cost urban sensing during package delivery. In this paper, we propose novel studies on the reutilization of such delivery drone resources to fill this void in urban crowdsensing. Accounting for interdependency between flying/sensing and drone delivery weight, we jointly optimize route selection, sensing time, and delivery weight allocation, to maximize delivery and sensing utility under drones’ energy constraints. This problem is formulated as a non-convex mixed-integer non-Linear programming problem, which is proved to be NP-hard. To address this intricate problem, we propose near-optimal algorithms that leverage the equivalent objective function construction, the local search scheme, and the alternating iteration technique. Theoretical analysis indicates that our algorithms can achieve$\frac{1}{4+\varepsilon }$-approximation ratio (where$\varepsilon$is an arbitrarily small positive parameter) and the convergence guarantee in polynomial time, for the scenarios of fixed and adjustable delivery weights, respectively. Extensive trace-based simulations, field experiments, and the real-world application demonstrate that ours can significantly improve the delivery & sensing utility by$124.7\%$and the energy utilization rate by$72.2\%$on average, compared with the drone delivery without reusing.

As a way of providing users flexible computing services, networks exist that can make full use of air and ground computing resources. Such networks are called air-ground collaborative mobile edge computing (AGC-MEC) networks. AGC-MEC supports numerous emerging real-time applications for which timely computed results are critical. Researchers have developed a novel metric “age of information (AoI)” that can capture the freshness of computed results. This is the first paper to study the problem of AoI-aware scheduling forAir-groundCollaborative mobileEdge computing (i.e., IACE). So as to minimize the weighted AoI of all the terrestrial user equipments (UEs), we have jointly optimized task scheduling, computing resource allocation, and unmanned aerial vehicle (UAV) trajectory taking into account the constraints on the computing resources and the available energy of the UAV. The formulated problem, which is a challenge to solve, is a mixed-integer nonlinear programming (MINLP) problem. To obtain an effective solution, we propose an iterative algorithm based on the alternating optimization approach, which entails dividing the considered problem into three subproblems. Extensive simulations show that the proposed algorithm can achieve lower weighted AoI than five benchmark algorithms, while satisfying the resource constraints. Furthermore, simulation results demonstrate two interesting insights. First, the introduction of an aerial MEC server facilitates a flexible offloading design of the UEs which is critical to guaranteeing the freshness of computed results. Second, by optimizing the scheduling, the proposed design can unlock performance gains, especially in the resource-limited regime.

With the popularity of Mobility-on-Demand (MOD) vehicles, a new market called MOD-Vehicular-Crowdsensing (MOVE-CS) was introduced for drivers to earn more by collecting road data. Unfortunately, MOVE-CS failed after two years of operation. To identify the root cause, we survey 581 drivers and reveal its simple operation model based on blindly competitive rewards. This model brings most drivers few yields, resulting in their withdrawals. In contrast, a similar market termed MOD-Human-Crowdsensing (MOMAN-CS) remains successful thanks to a complex model based on exclusively customized rewards. Hence, we wonder whether MOVE-CS can be resurrected by learning from MOMAN-CS. Despite considerable similarity, we can hardly apply the operation model of MOMAN-CS to MOVE-CS, since drivers are also concerned with passenger missions that dominate their earnings. To this end, we analyze a large-scale dataset of 12,493 MOD vehicles, finding that drivers have explicit preference for short-term, immediate gains as well as implicit rationality in pursuit of long-term, stable profits. Therefore, we design a novel operation model for MOVE-CS, at the heart of which lies a spatial-temporal differentiation-aware task recommendation scheme empowered by submodular optimization. Applied to the dataset, our design would essentially benefit both the drivers and platform, thus possessing the potential to resurrect MOVE-CS.

This demonstration shows a working prototype of IDEA, Intelligent Divine Eye on Air through multi-UAV collaborative inference, to improve the throughput and accuracy of onboard object detection. Different from most existing UAV airborne object detection systems relying single UAV to run the convolutional neural networks (CNN)-based inference independently, IDEA leverages the abundant resources of multiple UAVs in a swarm, and collaboratively executes the inference task. Specifically, IDEA divides the CNN model into multiple submodels (each consisting of several successive layers), and distributes each submodel to a UAV, where the execution sequence of the submodels is coordinated to output the final prediction. The prominent advantage of IDEA lies in that, it can not only run highly accurate complex CNN models, but also perform the object detection tasks in a pipeline manner, which thus boosts high detection accuracy and frame rate. IDEA prototype with three self-constructed real-world UAVs shows ~2.6× frame rate improvement over that with one single UAV, while achieving higher detection accuracy.

Unmanned aerial vehicle (UAV) has attracted much attention due to its excellent ability to collect visual information of surroundings. In this paper, we investigate a new monitoring model to focus on sizes and shapes of objects, and occlusion between objects, and then study the placement of a set of UAVs to monitor polygonal sizable objects. Our aim is to maximize the overall monitoring utility of all objects by determining the positions and orientations of UAVs, given a set of polygonal sizable objects with fixed coordinates and shapes on a$2\mathbf{D}$plane. We study two typical scenarios of the problem: the former stipulates that a line segment is effectively monitored only when it is completely monitored by a single UAV, and the latter allows multiple UAVs to cooperatively monitor a line segment and then integrate their image information. The problem is proved to be NP-hard with infinite continuous solution space. For the first scenario, we propose a$(1-1/e)$-approximation algorithm. For the second one, we first propose a 1/2-approximation algorithm to address its simple version, and then propose a heuristic solution. Numerical evaluations validate the effectiveness of our proposed algorithms.

This paper studies the problem of Wireless ChArger PlacemeNt with Multiple (Directional) Antennas (WANDA). Given a set of wireless chargers wherein each charger is equipped with multiple directional antennas and a set of wireless rechargeable sensors, determining the chargers' positions and the antennas' orientations, such that the overall charging utility is maximized. To address WANDA, we first present a piecewise constant function to approximate the nonlinear relationship between charging power and charging distance. Then, we propose an area discretization technique to reduce the infinite solution space to a limited one without performance loss. Next, we present approximation algorithms for both Relative Orientation Fixed (WANDA-ROF) and Relative Orientation Unfixed (WANDA-ROU) situations. For WANDA-ROF, we propose a Maximum Coverage Set extraction method that transforms WANDA-ROF into the problem of maximizing a monotone submodular function subject to a partition matroid constraint and then present a$1/2 -\epsilon$approximation algorithm. For WANDA-ROU, we construct a candidate position set for each charger to limit the searching space. Then, we propose a novel two-level submodular optimization scheme to address it, which achieves an approx-imation ratio of 1/6 - ∊. Simulation and experimental results show that our algorithms outperform comparison algorithms by at least 22%.

In this paper, we study the problem ofRobust offloading schEduling for mobIle edge computiNg (REIN), i.e., in the presence of uncertain offloading failures, how to determine an offloading schedule to minimize the overall latency of all computation-intensive tasks. We mathematically formulate the problem in the form of min-max robust optimization, based on the twice equivalent transformations of the scheduling problem that originally does not consider robustness. REIN is challenging to solve because the min-max robust objective is computationally intractable with existing approaches, and the monotonicity of the objective function is uncertain, even if we transform the objective into the popular max-min form by introducing an appropriate constant upper bound. To solve the above challenges, we first construct a constant upper bound and a monotone modular function to approximate the transformed max-min objective function, and then propose a computationally feasible solution with provable performance bound. Moreover, given the fact of the weak computation ability of users in practical, we construct a tighter constant upper bound and a monotone submodular approximation function, and propose a feasible solution with possibly improved performance bound. Extensive results show that, given a maximum number of offloading failures, our proposed algorithms outperform three benchmark algorithms, and approach the optimum at small time costs.

With the envision of sixth generation (6G) network technology, varied artificial intelligence (AI) services gradually develop from the network center to the edge, which makes unmanned aerial vehicle (UAV) a hot spot to provide auxiliary services of machine learning (ML) to empower terrestrial users intelligence. However, due to the sensitive privacy and limited resources, traditional centralized ML may not be used directly in such networks. As a promising distributed collaborative ML, fed-erated learning (FL) could be more suitable. Meanwhile, unlike conventional FL working on terrestrial networks, applying FL in UAV-assisted networks should strictly consider the impact of air-ground wireless channel caused by the maneuverability of UAVs, as well as the allocation of various network resources, including frequency and latency. To address these challenges, we propose to jointly optimize the UAV location and resource allocation, subject to the constraints of learning accuracy and training latency to minimize the energy consumption of terrestrial users. The for-mulated complicated non-convex problem is efficiently solved by an alternating optimization algorithm based on successive convex approximation (SCA) approaches after problem decomposition. Simulations results show that our proposed algorithm can reduce more overall users' energy consumption than three benchmarks while guaranteeing the learning accuracy within the maximum training latency.

With the proliferation of mobile and Internet of Things (IoT) devices, there has been an unprecedented growth of data consumption and computation requests at the network edge. To support latency-sensitive and resource-intensive mobile services, cellular base stations can be integrated with Mobile Edge Computing (MEC) technologies for service provisioning. MEC prompts flexible and configurable provisions of applications or services to make more efficient responses to mobile users' demands. Nevertheless, the time-varying nature of service demands inevitably becomes a vital challenge for existing service provisioning solutions. In this work, we propose MobiEdge, a multi-frame service provisioning scheme across two distinct timescales for MEC networks under various constraints of computation, communication and storage resources. We show that the large timescale indicated by ‘frame’ is more suitable for adjusting edge server activation and service placement, while the small timescale indicated by ‘time slot’ is more feasible to schedule users' requests. By leveraging the submodular techniques, we formulate a joint optimization problem and further propose an approximation algorithm with theoretical analysis and proofs. Synthetic and trace-driven evaluation results validate that MobiEdge can benefit both service providers and mobile users in MEC with high profits (e.g., 94% of the optimal) and a relatively low complexity.

In this article, we study the problem of task selection and scheduling in unmanned aerial vehicle (UAV)-enabled multiaccess edge computing for reconnaissance (ASSUMER). Specifically, taking into account the time-varying priorities of reconnaissance tasks, we investigate how to maximize the overall reconnaissance utility by selecting an appropriate set of tasks and scheduling their execution sequence in the multiaccess edge computing server of the UAV. The ASSUMER problem is a mixed-integer nonlinear programming (MINLP) problem, which includes both integer and continuous variables and is proved to be NP-hard. To address this challenging problem, we first model the task scheduling subproblem as a single machine scheduling problem with the deterioration effect. We find out that the optimal task scheduling can be solved efficiently given any task selection variables and propose an optimal scheduling algorithm. Second, using the proposed scheduling algorithm, the ASSUMER problem is equivalent to a binary integer programming problem with respect to the task selection variable only. We prove that the objective function falls into the category of the submodular function and transform the original problem into the problem of maximizing submodular function with the energy constraint. Third, combining the proposed scheduling algorithm with submodularity, we design an effective approximation algorithm for the ASSUMER problem and prove that the algorithm has$(1 - {e^{ - 1}})/2$bicriterion approximation guarantee. Finally, simulation results show that the proposed algorithm can improve the overall reconnaissance utility and energy efficiency compared to five benchmark algorithms.

For effective crowdsensing, it is essential to incentivize the interactions of participants and platforms. Existing approaches do not tailor users’ bidding to their preferences, i.e., personalized bidding (PB). To meet this need, we design an incentive mechanism, called Picasso, that achieves not only the expressiveness and description efficiency of PB for users, but also minimal social cost, computational efficiency, and strategy proof for platform owners. This design is, however, challenging due to the intrinsic conflicting goals of the platform owner and users. To handle these conflicts, Picasso represents bids in a novel 3-D expression space by orchestrating three logical operations to balance among expressiveness, computational complexity, and description efficiency. Moreover, we equivalently decompose and recombine the complex task dependencies of bids originated from the expressiveness of PB, thus achieving a constant-factor approximation of optimal task allocation with strategy proof in polynomial time. These properties of Picasso are proven theoretically. In addition to a detailed simulation study, our trace-driven evaluations show that, compared to existing approaches, Picasso can enable each user to bid$9.7\times $more tasks, on average, and decrease the description length by 74%, thus encouraging more users’ participation. Picasso also reduces the platform owner’s payment by more than 61%, hence yielding a win–win solution for incentivizing platform–user interactions.

Unmanned aerial vehicle (UAV)-enabled mobile edge computing has been recognized as a promising technology to flexibly and efficiently handle computation-intensive and latency-sensitive tasks in the era of fifth generation (5G) and beyond. In this paper, we study the problem of Service Provisioning for UAV-enabled mobile edge computiNg (SPUN). Specifically, under task latency requirements and various resource constraints, we jointly optimize the service placement, UAV movement trajectory, task scheduling, and computation resource allocation, to minimize the overall energy consumption of all terrestrial user equipments (UEs). Due to the non-convexity of the SPUN problem as well as complex coupling among mixed integer variables, it is a non-convex mixed integer nonlinear programming (MINLP) problem. To solve this challenging problem, we propose two alternating optimization-based suboptimal solutions with different time complexities. In the first solution with relatively high complexity in the worst case, the joint service placement and task scheduling subproblem, and UAV trajectory subproblem are iteratively solved by the Branch and Bound (BnB) method and successive convex approximation (SCA), respectively, while the optimal solution to the computation resource allocation subproblem is efficiently obtained in the closed form. To avoid the high complexity caused by BnB, in the second solution, we propose a novel approximation algorithm based on relaxation and randomized rounding techniques for the joint service placement and task scheduling subproblem, while the other two subproblems are solved in the same way as that of the first solution. Extensive simulations demonstrate that the proposed solutions achieve significantly lower energy consumption of UEs compared to three benchmarks.

In this work, we study the problem of Robust Server Placement (RSP) for edge computing, i.e., in the presence of uncertain edge server failures, how to determine a server placement strategy to maximize the expected overall workload that can be served by edge servers. We mathematically formulate the RSP problem in the form of robust max-min optimization, derived from two consequentially equivalent transformations of the problem that does not consider robustness and followed by a robust conversion. RSP is challenging to solve, because the explicit expression of the objective function in RSP is hard to obtain, and RSP is a robust max-min problem with a matroid constraint and a knapsack constraint, which is still an unexplored problem in the literature. To address the above challenges, we first investigate the special properties of the problem, and reveal that the objective function is monotone submodular. We then prove that the involved constraints form a p-independence system constraint, where p is a constant value related to the ratio of the coefficients in the knapsack constraint. Finally, we propose an algorithm that achieves a provable constant approximation ratio in polynomial time. Both synthetic and trace-driven simulation results show that, given any maximum number of server failures, our proposed algorithm outperforms three state-of-the-art algorithms and approaches the optimal solution, which applies exhaustive exponential searches.

Crowdsensing has been well recognized as a promising approach to enable large scale urban data collection. In a typical crowdsensing system, the task owner usually needs to provide incentives to the users (say participants) to encourage their participation. Among existing incentive mechanisms, posted pricing has been widely adopted because it is easy to implement while ensuring truthfulness and fairness. One critical challenge to the task owner is to set the right posted price to recruit a crowd with small total payment and reasonable sensing quality, i.e., posted pricing problem for robust crowdsensing. However, this fundamental problem remains largely open so far. In this paper, we model the robustness requirement over sensing data quality as chance constraints in an elegant manner, and study a series of chance constrained posted pricing problems in crowdsensing systems. Although some chance-constrained optimization techniques have been applied in the literature, they cannot provide any performance guarantees for their solutions. In this work, we propose a binary search based algorithm, and show that using this algorithm allows us to establish theoretical guarantees on its performance. Extensive numerical simulations demonstrate the effectiveness of our proposed algorithm.

The benefits of network coding on multicast in traditional multihop wireless networks have already been extensively demonstrated in previous works. However, most existing approaches cannot be directly applied to multihop cognitive radio networks (CRNs), given the unpredictable primary user occupancy on licensed channels. Specifically, due to the unpredictable occupancy, the channel's available bandwidth is time-varying and uncertain. Accordingly, the capacity of the link using that channel is also uncertain, which can significantly affect the network coding subgraph optimization and may result in severe throughput loss if not properly handled. In this paper, we study the problem of network coding-based multicast in multihop CRNs while considering the uncertain spectrum availability. To capture the uncertainty of spectrum availability, we first formulate our problem as a chance-constrained program. Given the computational intractability of the above-mentioned program, we then transform the original problem into a tractable convex optimization problem, through appropriate Bernstein approximation with relaxation on link scheduling. We further leverage Lagrangian relaxation-based optimization techniques to propose an efficient distributed algorithm for the original problem. Extensive simulation results show that the proposed algorithm achieves higher multicast rates, compared with a state-of-the-art non-network coding algorithm in multihop CRNs, and a conservative robust network coding algorithm that treats the link capacity as a constant value in the optimization.

Abstract Network coding (NC) can greatly improve the performance of wireless mesh networks (WMNs) in terms of throughput and reliability, and so on. However, NC generally performs a batch‐based transmission scheme, the main drawback of this scheme is the inevitable increase in average packet delay, that is, a large batch size may achieve higher throughput but also induce larger average packet delay. In this work, we put our focus on the tradeoff between the average throughput and packet delay; in particular, our ultimate goal is to maximize the throughput for real‐time traffic under the premise of diversified and time‐varying delay requirements. To tackle this problem, we propose DCNC, a delay controlled network coding protocol, which can improve the throughput for real‐time traffic by dynamically controlling the delay in WMNs. To define an appropriate control foundation, we first build up a delay prediction model to capture the relationship between the average packet delay and the encoding batch size. Then, we design a novel freedom‐based feedback scheme to efficiently reflect the reception of receivers in a reliable way. Based on the predicted delay and current reception status, DCNC utilizes the continuous encoding batch size adjustment to control delay and further improve the throughput. Extensive simulations show that, when faced with the diversified and time‐varying delay requirements, DCNC can constantly fulfill the delay requirements, for example, achieving over 95% efficient packet delivery ratio (EPDR) in all instances under good channel quality, and also obtains higher throughput than the state‐of‐art protocol. Copyright © 2014 John Wiley & Sons, Ltd.

The benefits of network coding on multicast in traditional multi-hop wireless networks have already been demonstrated in previous works. However, most existing approaches cannot be directly applied to multi-hop cognitive radio networks (CRNs), given the unpredictable primary user occupancy on licensed channels. Specifically, due to the unpredictable occupancy, the channel's bandwidth is uncertain and thus the capacity of the link using this channel is also uncertain, which may result in severe throughput loss. In this paper, we study the problem of network coding-based multicast in multi-hop CRNs considering the uncertain spectrum availability. To capture the uncertainty of spectrum availability, we first formulate our problem as a chance-constrained program. Given the computationally intractability of the above program, we transform the original problem into a tractable convex optimization problem, through appropriate Bernstein approximation together with relaxation on link scheduling. We further leverage Lagrangian relaxation-based optimization techniques to propose an efficient distributed algorithm for the original problem. Extensive simulation results show that, the proposed algorithm achieves higher multicast rates, compared to a state-of-the-art non-network coding algorithm in multi-hop CRNs, and a conservative robust algorithm that treats the link capacity as a constant value in the optimization.

In cognitive radio networks (CRNs), secondary users (SUs) may employ network coding to pursue higher throughput. However, because SUs should not interfere with high-priority primary users (PUs), the available transmission time of SUs is usually uncertain, i.e., SUs do not know how long the idle state can last. Meanwhile, existing network coding strategies generally adopt a block-based transmission scheme, implying that all packets in the same block can be decoded simultaneously only with enough coded packets collected. Therefore, the gain induced by network coding may be dramatically decreased once a block cannot be decoded due to the arrival of PUs. In this paper, for the first time, we develop an efficient network coding strategy for SUs while considering the uncertain idle durations in CRNs. To handle the uncertainty of SUs' available transmission time, we first consider how to estimate the length of idle duration. For the case where the length of idle duration is stochastic, we employ confidential interval estimation (CIE) method to estimate the expected length of the idle duration. For the non-stochastic case, we utilize multi-armed bandit (MAB) to determine the idle durations sequentially. After obtaining the estimated length, we further adopt systematic network coding (SNC) in the data transmission of SUs. We find that SNC is more suitable for SUs' transmission than the general block-based network coding in the sense that it can reduce average perpacket delay without decreasing the throughput gain. However, the block size (also the proportion of uncoded packets to be sent) of SNC is hard to determine, due to the complicated correlation among the receptions at different receivers. To solve this problem, we propose an optimal block size selection algorithm for SNC (OSNC) to determine the transmission proportion of uncoded packets, under a given idle duration length. Due to its low computational complexity, OSNC can be used to make an online decision on the optimal block size with small delay. Simulation results show that, compared to traditional block-based network coding and plain retransmission schemes, our proposed scheme achieves highest performance for both stochastic and non-stochastic idle durations.