In this paper, by integrating the advantages of synchronous federated learning (SFL) and asynchronous federated learning (AFL), an efficient federated learning (FL) framework with hybrid aggregation is proposed for the connected and autonomous vehicles (CAVs) over multiple base stations (BSs). Specifically, to cope with the stragglers caused by traffic accidents, extreme weather or other uncontrollable factors, the AFL with periodic aggregation is proposed to perform edge model aggregation within a single BS. Furtherly, taking the freshness of local model updates and the training data distribution into account, a novel weighting strategy is designed correspondingly. Moreover, to reconcile the contradiction between the scarce wireless communication resources and the enormous communication overhead caused by frequent exchanges of model parameters, an effective model compression mechanism is constructed based on the inherent statistical property of FL. In addition, considering a relatively small number of autonomous vehicles (AVs) within the limited coverage of a single BS and the instant guidance required for the CAVs, the SFL based on FedAvg is introduced to aggregate edge models trained from multiple BSs at network edge instead of remote cloud. The superior performance of the proposed method is verified by various simulations on real dataset.

Relation Classification (RC) is a fundamental task in knowledge discovery. Prototypical networks are commonly used for few-shot RC tasks to tackle labeled data scarcity and long-tail relations, but they always overlook classification reliability and outlier features, potentially leading to sub-optimal similarity measurement. In a dynamic world with emerging novel semantic relations, incremental few-shot learning of relations gains attention, involving learning of both base and novel relations in new tasks while retaining base relation knowledge. However, this becomes challenging with increasing novel relations, requiring that models should reduce reliance on learning base relations for the new task. Therefore, this article explores Class-Incremental Few-Shot Relation Classification (CIFRC) using a Gaussian-Augmented Prototypical Network (GA-Proto). GA-Proto refines the similarity measurement by incorporating discrepancies between ideal and actual classifications via Gaussian Mixture Model and analyzing Gaussian outlier features of query instances. It also employs reliability learning and knowledge distillation to mitigate encoding space distortion and base relation forgetting by enhancing classification reliability and transferring base relation knowledge, respectively. Additionally, GA-Proto uses label smoothing to alleviate novel relation overfitting. Experimental results on three public datasets demonstrate that GA-Proto outperforms existing methods on CIFRC, achieving up to 19.64% improvement in accuracy. The datasets and source code for GA-Proto are released at https://github.com/GTZN2/GA-Proto .

In modern datacenters, the effectiveness of end-to-end congestion control (CC) is quickly diminishing with the rapid bandwidth evolution. Per-hop flow control (FC) can react to congestion more promptly. However, a coarse-grained FC can result in Head-Of-Line (HOL) blocking. A fine-grained, per-flow FC can eliminate HOL blocking caused by flow control, however, it does not scale well. This paper presents Pyrrha, a scalable flow control approach that provably eliminates HOL blocking while using a minimum number of queues. In Pyrrha, flow control first takes effect on the root of the congestion, i.e., the port where congestion occurs. And then flows are controlled according to their contributed congestion roots. A prototype of Pyrrha is implemented on Tofino2 switches. Compared with state-of-the-art approaches, the average FCT of uncongested flows is reduced by 42%-98%, and 99th-tail latency can be$1.6\times $-$215\times $lower, without compromising the performance of congested flows.

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.

Federated learning (FL), as an emerging distributed machine learning paradigm, allows multiple participants to collaboratively train machine learning models without disclosing raw data. The high mobility and flexibility of Unmanned Aerial Vehicles (UAVs) can be effectively integrated with FL for distributed intelligent sensing, such as disaster response and agricultural monitoring. However, existing UAV-assisted federated learning approaches rarely take into account the unique characteristics of large-scale UAV swarms, which often encounter two critical challenges: biased model convergence resulting from statistical heterogeneity and inefficient training due to resource constraints. To address these issues, we propose FedUD, a novel federated learning framework for UAV networks that integrates adaptive UAV sampling and device-to-device (D2D) communications. FedUD employs a two-tier optimization strategy: (1) a set of leader UAVs is sampled by the base station to maximize statistical representativeness in each communication round, thereby mitigating bias from non-IID data; (2) A set of follower UAVs is selected for each leader UAV to form D2D clusters, which helps reduce communication overhead. Follower UAVs conduct local training and transmit their model updates to leader UAVs through D2D communications. The leader UAVs then aggregate these updates and forward them to the base station for global aggregation. Based on theoretical convergence analysis, we formulate a joint optimization problem for UAV sampling and D2D communications. This problem can be effectively solved using a submodular maximization-based iterative algorithm. Extensive experiments conducted on physical testbeds and simulations demonstrate that FedUD significantly enhances the stability of model performance and reduces system latency during the training process compared to benchmark methods.

Federated learning (FL) with differential privacy (DP) is a promising distributed learning framework for protecting user privacy. However, the introduction of DP noise leads to a decrease in the accuracy of the FL model and may even hinder convergence. Improving model performance while maintaining privacy is a significant challenge in FL with DP. Existing works primarily focus on the fine-grained allocation of the same privacy budget in each global iteration of FL, without considering the impact of varying privacy budget per round on model performance. Preliminary experiments with manual allocation of non-uniform privacy budget suggest that FL model performance with variable privacy budget outperforms those with uniform privacy budget, providing a potential basis for dynamically adjusting privacy budget per round to enhance model performance. Additionally, client data heterogeneity and device heterogeneity are also crucial factors affecting FL model performance. In this paper, we investigate the joint optimization problem of client selection and overall privacy budget allocation. To address the significant challenges posed by the coupling of optimization variables and the inability to express the objective function of the optimization problem explicitly in terms of the optimization variables, we propose a Coarse-Grained Dynamic Differential Privacy (CGDDP) scheme based on the Dueling Double Deep Q Network (D3QN), modeling the optimization task as a Markov Decision Process. We carefully design a reward function that encourages higher model accuracy while penalizing excessive privacy budget allocation. By introducing the sequential composition theorem, we prove that CGDDP provides (ε, δ)-DΡ for the entire local model. Theoretical analysis confirms that the security of CGDDP is no less than that achieved by allocating the same privacy budget per round. Extensive experiments under various configurations validate the effectiveness of CGDDP. The results show that, compared to traditional methods, the proposed scheme improves global model prediction accuracy by 5.78% and 4.8% for non-IID MNIST and FashionMNIST datasets, respectively, and by 17.78% and 7.53% for IID data distributions.

Federated learning (FL) has emerged as the most promising distributed machine learning training framework due to its advantages in efficiency, privacy preservation, and scalability. In the practical deployment, FL usually faces the system heterogeneity, data heterogeneity, and limited communication resources. Many works attempt to address the above challenges by client selection, but seldom consider the issues of missing classes in training samples and communication resource allocation, which leads to poor training performance. In this paper, we propose an efficient FL framework with clustering-based client selection and bandwidth allocation, called FedCCS. Specifically, FedCCS first clusters clients based on the local label distribution. By ensuring clients from each cluster participate in training, a wider range of sample classes are covered to mitigate data heterogeneity effects. Furthermore, considering system heterogeneity and limited communication resources, we develop an iterative-based joint optimization algorithm for client selection and bandwidth allocation to minimize latency. Experimental results on both simulations and real-world prototypes show that, compared to other methods, FedCCS can significantly reduce latency and improve the stability of model performance during the training process.

The existing Discrete Event Simulators (DES) cannot meet the demands of modern networks for efficient, accurate, and flexible simulation. Recent m achine l earning models have demonstrated exceptional capabilities for e stimating n etwork p erformance (MLENP). However, the quality and quantity of available data greatly limit the accuracy and generalizability of ML models. After analyzing the data requirements of MLENP over the past decade and the shortcomings of existing DES, we propose a low-threshold and powerful n etwork p erformance data gen erator (GenNP), and generate a network performance dataset consisting of 10K samples. GenNP, with OMNeT＋＋ and INET at its simulation core, integrates the configuration generation layer, simulation transformation layer, result extraction layer, and result output layer, achieving massive random generation of simulation configurations (networks, traffic, routing protocols, faults) and multi-granularity extraction of network performance data (throughput, drop, delay, jitter, routing table). We validate the robust capabilities of GenNP through a series of simulation experiments across multi-granularity (spatial, temporal), diversity (traffic models, network load, fault types, routing protocols), and efficiency (parallelism).

Abstract Temporal Scoping of Facts is crucial for completing the temporal dimension of knowledge graphs. Current mainstream methods rely heavily on external resources for mining temporal information. However, the presence of noise in external resources, coupled with limitations in adaptively inferring non-continuous temporal dimensions with multiple temporal ranges, leads to low accuracy in predicting temporal ranges. To address these challenges, a model named JammyTS is proposed, which J oins an a ttention m echanism and a m emor y network for T emporal S coping of facts. Specifically, JammyTS leverages attention to adjust the distribution of weights dynamically in memory networks and builds attention capsule-based networks to reduce the impact of noise in external resources. Furthermore, two linear classifiers are separately trained to infer the end and beginning timestamps of facts for inference of non-continuous temporal ranges. Extensive experiments on three datasets show that JammyTS improves the accuracy by up to 12.29% compared to the state-of-the-art.

Abstract Named Entity Recognition (NER) in cybersecurity is crucial for mining information during cybersecurity incidents. Current methods rely on pre-trained models for rich semantic text embeddings, but the challenge of anisotropy may affect subsequent encoding quality. Additionally, existing models may struggle with noise detection. To address these issues, we propose JCLB, a novel model that J oins C ontrastive L earning and B elief rule base for NER in cybersecurity. JCLB utilizes contrastive learning to enhance similarity in the vector space between token sequence representations of entities in the same category. A Belief Rule Base (BRB) is developed using regexes to ensure accurate entity identification, particularly for fixed-format phrases lacking semantics. Moreover, a Distributed Constraint Covariance Matrix Adaptation Evolution Strategy (D-CMA-ES) algorithm is introduced for BRB parameter optimization. Experimental results demonstrate that JCLB, with the D-CMA-ES algorithm, significantly improves NER accuracy in cybersecurity.

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.

With the booming development of fifth-generation network technology and Internet of Things, the number of end-user devices (EDs) and diverse applications is surging, resulting in massive data generated at the edge of networks. To process these data efficiently, the innovative mobile edge computing (MEC) framework has emerged to guarantee low latency and enable efficient computing close to the user traffic. Recently, federated learning (FL) has demonstrated its empirical success in edge computing due to its privacy-preserving advantages. Thus, it becomes a promising solution for analyzing and processing distributed data on EDs in various machine learning tasks, which are the major workloads in MEC. Unfortunately, EDs are typically powered by batteries with limited capacity, which brings challenges when performing energy-intensive FL tasks. To address these challenges, many strategies have been proposed to save energy in FL. Considering the absence of a survey that thoroughly summarizes and classifies these strategies, in this paper, we provide a comprehensive survey of recent advances in energy-efficient strategies for FL in MEC. Specifically, we first introduce the system model and energy consumption models in FL, in terms of computation and communication. Then we analyze the challenges regarding improving energy efficiency and summarize the energy-efficient strategies from three perspectives: learning-based, resource allocation, and client selection. We conduct a detailed analysis of these strategies, comparing their advantages and disadvantages. Additionally, we visually illustrate the impact of these strategies on the performance of FL by showcasing experimental results. Finally, several potential future research directions for energy-efficient FL are discussed.

To realize the benefits expected and ensure user privacy and data security simultaneously, a cost-efficient edge federated learning (FL) architecture over multiple base stations (BSs) is proposed for the intelligent transportation system (ITS) based on connected and autonomous vehicles (CAVs). Firstly, in the proposed FL architecture, the road side units (RSUs) are designed to train the machine learning (ML) model with the BSs equipped with edge servers collaboratively. In this way, since the autonomous vehicles do not participate in model training, the negative impact of unreliable communication caused by vehicle mobility can be eliminated. Then, considering that the limited amount of data involved within the coverage of a single base station (BS), the FL architecture over multiple BSs at network edge is proposed for better learning performance. Along this line, the joint edge aggregation and association problem is studied, and a set function optimization problem is formulated with the objective of minimizing the costs considering latency and energy consumption comprehensively. Finally, after analyzing the complexity, monotonicity, and modularity of the problem formulated, the NP-hardness optimization problem is further decomposed and transformed, and an innovative solution is proposed. The abundant simulation results demonstrate the superior performance of the cost-efficient FL architecture proposed.

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.

RDMA over Converged Ethernet (RoCEv2) has been widely deployed to data centers (DCs) for its better compatibility with Ethernet/IP than Infiniband (IB). As cross-DC applications emerge, they also demand high throughput, low latency, and lossless network for cross-DC data transmission. However, RoCEv2’s underlying lossless mechanism Priority-based Flow Control (PFC) cannot fit into the long-haul transmission scenario and degrades the performance of RoCEv2. PFC is myopic and only considers queue length to pause upstream senders, which leads to large queueing delay. This paper proposes Bifrost, a downstream-driven lossless flow control that supports long distance cross-DC data transmission. Bifrost uses virtual incoming packets, which indicates the upper bound of in-flight packets, together with buffered packets to control the flow rate. It minimizes the buffer space requirement to one-hop bandwidth delay product (BDP) and achieves low one-way latency. Moreover, we extend Bifrost and propose BifrostX, to accommodate the multi-priority queue of the current switch implementation. BifrostX enables flow control for each queue separately while maintaining low buffer reservation, no throughput loss, and no packet loss. Real-world experiments are conducted with prototype switches and 80 kilometers cables. Evaluations demonstrate that compared to PFC, Bifrost reduces average/tail flow completion time (FCT) of inter-DC flows by up to 22.5%/42.0%, respectively. Bifrost is compatible with existing infrastructure and can support distance of thousands of kilometers.

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.

RDMA over Converged Ethernet (RoCEv2) has been widely deployed to data centers (DCs) for its better compatibility with Ethernet/IP than Infiniband (IB). As cross-DC applications emerge, they also demand high throughput, low latency, and lossless network for cross-DC data transmission. However, RoCEv2's underlying lossless mechanism Priority-based Flow Control (PFC) cannot fit into the long-haul transmission scenario and degrades the performance of RoCEv2. PFC is myopic and only considers queue length to pause upstream senders, which leads to large queueing delay. This paper proposes Bifrost, a downstream-driven lossless flow control that supports long distance cross-DC data transmission. Bifrost uses virtual incoming packets, which indicates the upper bound of in-flight packets, together with buffered packets to control the flow rate. It minimizes the buffer space requirement to one-hop bandwidth delay product (BDP) and achieves low one-way latency. Real-world experiments are conducted with prototype switches and 80 kilometers cables. Evaluations demonstrate that compared to PFC, Bifrost reduces average/tail flow completion time (FCT) of inter-DC flows by up to 22.5%/42.0%, respectively. Bifrost is compatible with existing infrastructure and can support distance of thousands of kilometers.

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

Recent works have shown that inaudible signals (at ultrasound frequencies) can become audible to the microphone by exploiting the nonlinear effects. With a well-designed inaudible signal, an adversary can control Amazon Echo and Google Homelike devices in people’s rooms silently and remotely. A voice command like “Alexa, open the door“ can be a serious treat. Although recent works design various methods against such inaudible attacks, one important issue remains open: there is no clear solution to locate the attack source accurately. Obviously, the only way to completely eliminate such inaudible threats is to locate and remove the attack source. This paper is an attempt to close this gap. We propose Arrow, an effective method to help users locate the ultrasound attack source in 3D space indoors. Arrow establishes the relationship between inaudible signals and the recorded sounds of the microphone, and then explores the architecture of the embedded microphone array on smart speaker for extracting a 3D direction-specific signature. By learning such directional signature, Arrow can accurately estimate the spatial orientation of the inaudible attack source and help users to locate and remove it. We implement a prototype of Arrow and conduct comprehensive experiments to validate its performance. The results show Arrow can achieve 2.5° and 7° error in DoA(Direction of Arrival) estimation for horizontal and vertical angles, respectively.

Reliable data measurement is considered to be one of the critical ingredients for variant Internet of Things (IoT) applications. Gaining full knowledge of measurement data is becoming increasingly crucial to ensure a satisfactory user experience. However, data missing and corruption are inevitable in practical applications, which motivates us to study how to accurately recover the missing IoT measurement data in the presence of outliers. The data recovery problem can be formulated as a tensor completion (TC) problem. Existing TC methods are built on the assumption that the rank of the underlying tensor is fixed, which is not suitable for long data sequences in practice. Consequently, based on the characteristics of IoT streaming data, we assume that the data tensor lies in time-varying subspace, and an accurate estimate of the rank is a prerequisite for filling the missing entries and achieving robustness of the variations in both rank and noise. We built up an updatable framework based on dynamic CANDECOMP/PARAFAC (CP) decomposition. In addition, an efficient algorithm, called temporal multi-aspect streaming (T-MUST), is introduced to solve the optimization problem that originates in our developed model. It is worth noting that the proposed algorithm allows time-varying tensor rank and enables the rank changes could be detected and tracked automatically. Theoretical analysis indicates that T-MUST enjoys a geometric convergence rate. Numerical experiments conducted on various synthetic and real-world datasets empirically validate the superiority of the proposed T-MUST in both efficiency and effectiveness.

The recent breakthroughs in Wireless Power Transfer (WPT) facilitate supporting rechargeable sensors to enrich a series of energy-consuming applications. However, most charging scheduling schemes in rechargeable wireless sensor networks (WSNs) focus on sensing tasks instead of charging utility, which leaves a considerably high performance gap in the optimal result. Moreover, the charging scheduling is usually non-flexible, in which a full or nothing charging policy suffers from relatively low charging coverage as well as low efficiency. In this article, we focus on how to efficiently improve charging utility when introducing charging-oriented sensor placement and flexible scheduling policy. We formulate a general maximization optimization problem under a general routing constraint, which generates great difficulty. We utilize area partition and charging discretization methods to transform into the scope of maximizing a submodular function problem. Thus, a constant approximation algorithm is delivered to construct a near optimal charging tour. We analyze the performance loss from the discretization to guarantee that the output of the proposed algorithm has more than (1-ɛ)(1-1/ e )/4 of the optimal solution, where ɛ is an arbitrarily small positive parameter (0 < ɛ < 1). Both simulations and field experiments are conducted to evaluate the performance of our proposed algorithm.

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.

With the popularity and development of the Internet of things (IoT), human life has been deeply affected. Because of the limitations of computation capability and battery capacity, it is difficult for IoT devices to support frequent and complex computing. Motivated by this challenge, many works attempt to upload tasks of IoT devices to the cloud center for computation. However, because of the limitation of distance and bandwidth, cloud computing is difficult to guarantee low latency. As a feasible solution, Mobile Edge Computing (MEC) has attracted more and more attention. Most existing works focus on the computation offloading strategy, while the task scheduling on edge servers is not studied in depth. The tasks uploaded by IoT devices are dynamic and random, and there are dependencies between these tasks. Therefore, it is difficult for edge servers to find a task scheduling scheme to minimize the task execution delay. In this paper, to solve the task scheduling problem of edge server in multi-server and multi-user MEC system, we propose a heuristic algorithm based on the following three scenarios: 1) Tasks uploaded by IoT devices is dynamic and uncertain. 2) There are dependencies between tasks. 3) The computation capability of the edge server is limited. Experimental results show that the proposed algorithm can significantly reduce the overall completion time of tasks and the average task execution delay in the edge server.

Wireless power transfer (WPT) has emerged as a promising paradigm to charge devices due to the high reliability and efficiency of continuous power supply. Recent studies usually focus on relatively general charging patterns and metrics but neglect the collaborated task execution of nodes that incur charging inefficiency. In this article, we respect the energy requirement diversity among nodes to investigate the collaborated and tasks-driven mobile charging problem. Our goal is to maximize the overall task utility that concerns sensor selection and task cooperation. To address this problem, we propose a$(1-1/e)/4$-approximation algorithm. First, we propose a novel energy allocation scheme with a specific theoretical analysis of the submodularity and gap property for the surrogate function. Then, we approximate the traveling cost to transform the formulated problem into an essentially monotone submodular function optimization subject to a general routing constraint and propose a greedy algorithm to address this problem. We conduct extensive simulations to validate our theoretical results and the results show our algorithm can achieve a near-optimal solution covering at least 84.9% of the optimal result achieved by the OPT algorithm. Furthermore, field experiments in an office room and a soccer field environment are implemented, respectively, to validate our proposed algorithm.

Due to the merit without requiring charging cable, wireless power transfer technology has drawn rising attention as a new method to replenish energy for Wireless Rechargeable Sensor Networks. In this article, we study the mobile charger scheduling problem for multi-node recharging with deadline constraints. Our target is to maximize the overall effective charging utility and minimize the traveling time for moving as well. Instead of charging only once over a scheduling cycle, we incorporate the multi-node charging strategy with deadline constraints, where charging spots and tour are jointly optimized. Specifically, we formulate the effective charging utility maximization problem as a monotone submodular function optimization subject to a partition matroid constraint, and we propose a simple but effective ½-approximation greedy algorithm. After that, we derive the result of global scheduling and present the grid-based skip-substitute operation to further save the traveling time, which can increase the charging utility. Finally, we conduct the evaluation for the performance of our scheduling scheme. The simulation and field experiment results show that our algorithm excels in terms of effective charging utility.

The recent breakthrough in Wireless Power Transfer (WPT) provides a promising way to support rechargeable sensors to enrich a series of energy-consuming applications. Unfortunately, two major design restrictions hinder the applicability of rechargeable sensor networks. First, most of the sensor placement schemes are focusing on the sensing tasks instead of the charging utility, which leaves a considerably high performance gap towards the optimal result. Second, the charging scheduling is non-flexible, where full or nothing charging policy suffers from the relatively low charging coverage as well as efficiency. In this paper, we focus on how to efficiently improve the charging utility when introducing charging oriented sensor placement and flexible scheduling policy. To this end, we jointly consider optimizing node positions and charging allocations. In particular, we formulate a general convex optimization problem under a general routing constraint, which generates great difficulty. We utilize area partition and charging discretization methods to reformulate a submodular function maximization problem. Thus a constant approximation algorithm is delivered to construct a near optimal charging tour. To this end, we analyze the performance loss from the discretization to guarantee that the output of the proposed algorithm has more than $(1 -\varepsilon)/4 (1 - 1 /e)$ of the optimal solution, where $\varepsilon$ is an arbitrarily small positive parameter $(0 \leq \varepsilon \leq 1)$. Both simulations and field experiments are conducted to evaluate the performance of our proposed algorithm.

Wireless Power Transfer (WPT) has emerged into an inspiringly commercial and applicable era to charge devices. Existing studies mainly focus on general charging patterns and metrics while overlooking the collaborated task execution, which incurs charging inefficiency among nodes. In this paper we first advocate the collaborated tasks-driven mobile charging and scheduling to respect the energy requirement diversity. Specially, the mobile charging scheduling strategy is considered to maximize the overall task utility which concerns sensor selection and task cooperation. Unfortunately, solving this problem is non-trivial, because it involves solving two coupling NP-hard problems. In tackling with this difficulty, we construct a surrogate function with specific theoretical analysis of its submodularity and gap property. Then, we approximate the traveling cost to transform the formulated problem into an essentially monotone submodular function optimization subject to a general routing constraint, where we propose $a (1-\ 1/e)/4$-approximation algorithm. Extensive simulations are conducted and the results show that our algorithm can achieve a near-optimal solution covering at least S4.9% of the optimal result achieved by the OPT algorithm. Furthermore, field experiments in office room and soccer field environment with 10 and 20 sensors are implemented respectively to validate our proposed algorithm.

In this work, we study the mobile charger scheduling problem for multi-node charging with deadline constraints. In that, we aim at scheduling the charger to maximize the effective charging utility in dealing with the mismatch between time and spatial constraints. The local charging spots selection and globe traveling path should be jointly optimized, which is APX-hard. Nevertheless, our problem becomes much more complex with deadline constraints. To handle aforementioned challenges, we combine the spatial and temporal relevancy into a bipartite graph, and incorporate the multi-charging strategy instead of serving nodes strictly by the non-soft charging demands. We formulate the effective charging utility maximization problem into a monotone submodular function maximization subjected to a partition matroid constraint, and propose a simple but effective 1/2-approximation greedy algorithm. The results show that our scheme outperforms Early Deadline First (EDF) by 37.5%.