LLM agents increasingly rely on tool calling, and the Model Context Protocol (MCP) standardizes it between agents and tool providers, reducing integration cost and driving rapid growth in tool scale. Yet a standardized interface does not make tool access work at production scale: legacy services are not MCP-callable, fast protocol evolution creates compatibility cost, large tool sets exhaust the context window, and stateful sessions complicate load balancing. We solve these with a shared control point, a centralized MCP Gateway System that makes MCP operational at cloud scale. The gateway breaks the direct-connect data plane and consolidates legacy API integration, protocol bridging, access control, and session-aware routing, while scaling out elastically at low per-call overhead. It scales agent tool access to thousands of cloud operations.

Commodity GPUs make large-model serving economically attractive, but they are typically connected via PCIe rather than high-bandwidth GPU fabrics. This is a poor fit for expert-parallel Mixture-of-Experts (MoE) inference, where each MoE layer routes tokens to selected experts via all-to-all communication, and PCIe crossings can become a major latency bottleneck. Existing serving systems and communication libraries optimize this traffic but treat router-selected expert assignments as fixed. We propose PCIe-MoE, an inference-time mechanism that decides when a low-confidence remote expert is worth a costly PCIe hop, and when a nearby, score-similar expert can be substituted instead. PCIe-MoE combines topology profiling, replaceability-aware placement, risk-aware remapping, and quality guards to reshape token-to-expert routing without retraining.

Model serving systems are critical for deep learning inference, managing GPU infrastructure to deliver end-to-end services. Current frameworks typically treat operators as basic compilation and scheduling units, which often fail to maximize GPU utilization due to hardware-unfriendly kernels and coarse-grained scheduling. To address these limitations, we propose a cooperative compilation and scheduling scheme that statically generates multiple kernel variants and dynamically schedules them based on runtime context. We present Infera, a high-performance model serving system that implements this approach. Experimental results demonstrate that Infera improves inference throughput by at least 1.6× compared to state-of-the-art baselines.

In multimedia applications, Federated Learning (FL) has emerged as an effective training paradigm, enabling distributed clients to collaboratively train a shared model without transmitting raw data. However, FL remains vulnerable to privacy threats such as data reconstruction and membership inference attacks, which has motivated the adoption of secure aggregation protocols to protect client model updates. Existing secure aggregation schemes that combine homomorphic encryption with secret sharing predominantly follow a sharing-decryption paradigm, requiring additional client interaction during decryption and thereby incurring substantial computational, synchronization, and communication overhead. In this paper, we propose Threshold Vector Aggregation (TVA), a novel secure aggregation protocol that adopts a sharing-encryption and aggregation paradigm. Under TVA, each client encrypts its local update only once using a unique private key and uploads a single ciphertext to the server, without any further interaction. The cipher-texts are directly aggregatable yet individually undecryptable, and only the final aggregated result can be correctly recovered by the server. Extensive experiments demonstrate that TVA significantly outperforms state-of-the-art secure aggregation schemes, achieving up to 33× lower server-side aggregation time, 132× faster client-side encryption, and 170× reduction in communication overhead, while preserving model accuracy comparable to plaintext federated learning.

Federated Learning (FL) enables knowledge sharing across client models with privacy preservation. A key challenge in FL is to aggregate general knowledge across clients while preserving personalized knowledge for each client. We discover that this challenge primarily stems from the coupling of general and personalized knowledge across different model layers. Existing methods either fail to fully decouple these two types of knowledge or do not leverage them effectively for inference, leading to suboptimal performance. This paper presents Thorki, a new FL system that decouples general and personalized knowledge throughout all model layers. In Thorki, instead of one model, each client stores its personalized knowledge in a small model and general knowledge in a large model. When making an inference, it employs a fusion network to combine the outputs of the two models, leveraging both types of knowledge adaptively. This new model collaboration paradigm allows clients to share their general knowledge in a federated manner without compromising their personalized inference capabilities. Extensive experiments with three models on four datasets demonstrate that Thorki outperforms state-of-the-art FL systems by 0.16%-19.14% in model accuracy and improves time-to-accuracy performance by 2.00x-10.00x.

Collaborative learning between edge servers (e.g., base stations) and end devices (e.g., drones) enables simultaneous model training in web applications through knowledge sharing. The resulting models effectively reduce service latency. However, existing approaches either assume isomorphic models on edge servers and end devices or incur substantial transmission overhead when training. Moreover, edge servers are often unable to access data from end devices on time due to long-distance constraints or strict data privacy regulations. This paper proposes a Prototype Augmentation-based Edge-end Collaborative Learning method (PAECL). It simultaneously trains heterogeneous edge and end models in the absence of data on edge servers by transmitting only augmented class-wise feature vectors (prototypes), significantly reducing communication overhead compared to sharing models, data, or logits. Specifically, on end devices, prototype-implied latent knowledge is augmented via local prototype contrast and global prototype alignment. On edge servers, prototypes are further augmented to produce bounded virtual vectors by mixing them with random noise, and the augmented prototypes are then delivered to generative models to provide data during edge model training. Through simulations and field experiments, PAECL achieves the highest accuracy for edge and end models under limited training resources and reduces the transmission burden by at least 297 times compared to existing edge-end heterogeneous learning methods.

With the rapid development of low-altitude economy, the low-altitude intelligent network (LAIN) serves as a critical infrastructure for supporting diversified aerial activities. However, current LAIN lacks a physical-network synchronization mechanism and fails to handle heterogeneity at the architecture level, which leads to difficulties in real-time adaptive adjustments and efficient unified coordination. To address these issues, this paper proposes the networked embodied intelligence (NEI) paradigm, with a network-level sensing-decision-action-feedback (SDAF) closed-loop mechanism to synchronize physical and network states. Building on this paradigm, we functionally reconfigure LAIN into four collaborative subnetworks: sensing, computing, communication and navigation. As a further step, we propose the NEI-LAIN architecture, where these subnetworks collaborate via the SDAF loop to achieve global collaboration and continuous evolution. Simulation results demonstrate that the proposed NEI-LAIN can significantly enhance the performance of communication robustness, resource utilization and task responsiveness in highly dynamic scenarios. Finally, we discuss its implementation challenges and future research directions.

Complex event recognition (CER) refers to identify-ing specific patterns composed of several primitive events in event stores. Since full-scanning event stores to identify primitive events that hold query constraint conditions incurs costly I/O overhead, a mainstream and practical approach is to use index techniques to obtain these events. However, prior index-based approaches suffer from significant I/O and sorting overhead when processing the query with high predicate selectivity or long query window, which leads to high query latency. To address this issue, we propose ACER, a Range Bitmap-based index, to accelerate CER. Firstly, ACER achieves a low index space overhead by grouping the events with the same type into a cluster and compressing the cluster data, reducing I/O overhead when reading indexes. Secondly, ACER builds Range Bitmaps for queried attributes and ensures that the events of each cluster in the index block are chronologically ordered. Then, ACER can always obtain ordered query results for a specific event type through merge operations, avoiding sorting overhead. Most importantly, ACER avoids unnecessary disk accesses in indexes and events via window-wise filtering, thus reducing the I/O overhead further. Lastly, we propose an enhanced version of ACER (ACER-E) by optimizing the read/write operation of index blocks and variable query order. Our extensive experiments demonstrate that ACER and ACER-E reduce the query latency by up to one order of magnitude compared with SOTA techniques.

Underwater Optical Wireless Sensor Network (UOWSN) is a promising technology as it can achieve high-speed communication in underwater environment. However, affected by the uncertainty of complex underwater environment, the network topology of UOWSN is highly dynamic, making it difficult to quantify flexibility or further optimize the topological structure. Additionally, node mobility and energy constraints pose significant challenges to reliable communication. In this paper, we propose a mobility-aware and energy-efficient flexibility-based network topology evaluation model (ME-FEM) for UOWSNs. Then, a reinforcement learning model, termed ME-FEM-DRL, for optimizing the network topology based on ME-FEM is developed, which enables UOWSN to maintain an optimal topology when working in harsh underwater environments. Theoretical analysis proves the NP-hardness of the optimization problem and demonstrates that our algorithm achieves an approximation ratio of$O(\log N)$with optimal parameter boundaries. Simulation results demonstrate that the proposed method can significantly improve the network flexibility. Compared with the five baseline algorithms in simulations, ME-FEM-DRL reduces normalized topology optimization time cost by 64% and extends network lifetime by 95% on average. Test-bed experiments verify the applicability and effectiveness in practical applications for detecting emergent events.

Head orientation tracking has many potential applications in many fields,e.g., human-computer interaction, AR, and VR. In recent years, a large amount of existing work only focuses on the positioning of the user but ignore the tracking of the head orientation. Undoubtedly, with the information of the user's head orientation, many applications will have more opportunities for performance enhancement and better user experience. However, reviewing existing works regarding head tracking, the CV-based solutions have limited tracking angle range and privacy issues, the IMU-based solutions have accumulated errors, and the traditional microphone array-based solutions have low accuracy. Thus, none of these methods provides accurate and stable head orientation. In this paper, we propose EHeadTracker, an enhanced fine-grained head orientation tracking system based on head-mounted acoustic devices. This system recognizes rich head motions and achieves high-precision head direction tracking, while solving the problem of pivot point initialization. The experimental results show that the system can achieve an average error of 6 degrees in the head orientation tracking. To the best of our knowledge, EHeadTracker is the first system to use head-mounted acoustic devices to achieve head orientation tracking and has the highest accuracy in all current work.

Edge caching is a critical application scenario in edge networks. By storing diverse files on edge servers and dynamically fetching new files from the cloud, edge networks can provide low-latency file access services for mobile users. In practice, the file fetching latency is non-negligible. Consecutive requests for the same missing file during the fetching phase introduce additional latency (referred to as delayed hits). Existing studies either ignore the delayed hits when making caching decisions or are not applicable to multi-server edge networks. In this paper, we investigate the online caching problem with delayed hits in the multi-server edge networks and prove its hardness. The objective is to minimize the total file access latency. To solve the proposed problem, we propose Cadle, which makes caching decisions based on the latency of different file access operations and weights of files in an online manner, without relying on any prior knowledge of future requests. We prove the competitive ratio of Cadle.We also conduct extensive experiments on the real-world dataset to verify the performance of Cadle. The experimental results show that Cadle reduces the total file access latency by at least 31.8% on average, and improves the hit ratio by at least 25.9% on average compared with state-of-the-art approaches.

Rotation is a fundamental form of motion and rotation speed measurement holds paramount importance for assessing the health and performance of machinery with rotating components. However, existing measurement systems often face challenges such as limited measurement distance, low accuracy, and complex installation or maintenance processes. In this paper, we propose RoLEX, a LoRa-based rotation speed measurement system for long-distance and contactless monitoring of rotating machinery in ubiquitous scenarios. RoLEX employs a novel Signal Selection method to eliminate chirp interference and adapt to varying rotation speeds, along with a Boost Sensing method to enhance sampling rates and an advanced feature processing algorithm for precise rotation speed estimation and tracking. Comprehensive experiments validate that RoLEX achieves a measurement distance of 50 m, approximately 17 times farther than the latest wireless rotation speed measurement systems. Moreover, RoLEX is robust to interference and obstructions (including through-wall scenarios) and achieves an average measurement error less than 0.69% across different rotation speeds (100 - 5100 Revolutions Per Minute). For tracking performance, RoLEX achieves a relative error less than 2.8% in 90% of cases. We also present a case study to highlight RoLEX's practical applicability in real-world scenarios.

Accurate long-term traffic forecasting improves traffic efficiency and safety in Intelligent Transportation Systems (ITS). However, previous methods typically overlook the complex mixed characteristics. So they struggle to capture the intricate features of newly added data effectively under distribution shifts, which exacerbates the complexity of spatial-temporal variations. Moreover, these methods fail to model global and local dynamic spatial correlations effectively, efficiently, and comprehensively. To mitigate these issues, this paper proposes an innovative Spatial-Temporal Wavelet Attention Network (STWAN). STWAN first decomposes traffic data into stable trends and fluctuating events, effectively dealing with the adverse effects of distribution shifts. Then, spatial-temporal encoder captures component-specific temporal variations and extracts dynamic global-local spatial correlations comprehensively with linear computational complexity. Additionally, transformer attention and forecasting decoder model the latent patterns, while trend-event fusion module integrates essential information for accurate forecasts. Comprehensive experiments across two real-world traffic forecasting tasks indicate that STWAN significantly outperforms state-of-the-art methods in terms of accuracy and robustness, attaining a maximum reduction of 5.54% in MAE and showcasing its robustness and broad applicability in long-term forecasting.

While unmanned aerial vehicle base stations (UAV-BSs) offer transformative potential for enhancing terrestrial networks, their deployment faces dual challenges of limited onboard energy and dynamic channel conditions that compromise long-term fair communication coverage. In this paper, we investigate the problem ofWireless-poweredUAVsTrajectories planning forFair communication (WUTF), that is, navigating multiple UAV-BSs powered by wireless charging towers (WCTs), to provide fair communication services for ground users. To address the problem, we first formulate the original optimization problem as a Partially Observable Markov Decision Process (POMDP), and propose a Deep Reinforcement Learning (DRL) based trajectory planning algorithm. The proposed approach incorporates a novel reward function that balances multiple objectives and adopts a Centralized Training with Executed Decentralization (CTED) framework. Furthermore, a sequential policy update scheme is introduced to enhance multi-UAV coordination and reduce policy conflicts. Simulation results show that our proposed algorithm significantly improves the communication fairness, total throughput, and communication efficiency, as compared to state-of-the-art DRL-based methods up to$32.01\%$on average.

Unmanned Aerial Vehicles (UAVs) have recently been widely used in various fields. However, both cooperative charging scheduling and insufficient charging facility problems in UAV charging scenarios have been rarely studied. This paper studies parallel cooperative charging scheduling of UAVs. We adopt cooperative charging to reduce the total cost and parallel scheduling to enable UAVs can be charged even if the number of UAVs is more than the number of charging facilities. We formulate the Parallel Cooperative Charging Scheduling for UAVs Problem (PCCSUP) for optimizing the total cost of whole charging system. We first investigate the special case of PCCSUP with single charging station, and use the approximation algorithm for Uniform Parallel Machines Scheduling Problem (UPMSP) to solve the special case. Then, a greedy approach based approximation algorithm is proposed to solve the PCCSUP, where we use the approximation algorithm for UPMSP to obtain the charging arrangements and the Set Covering Problem (SCP) optimization framework to obtain the charging groups. The results of extensive simulations demonstrate that our algorithm can reduce up to 59.81% total cost compared with the benchmark algorithms. Finally, we discuss and design the algorithms for three related problems: PCCSUP with different arrival times, PCCSUP withK-anonymity, and charging arrangements for excluded UAVs.

Wireless Rechargeable Sensor Networks (WRSNs) promise to address the limited energy resource issue for sensor nodes through wireless power transfer technology. However, WRSNs are vulnerable to various security threats, such as compromised node attack and malicious mobile charger (MC) attack, which can disrupt the charging process and degrade charging efficiency. In this work, we investigate the eneRgy conversionEfficiency maximization problem unDer chargIng attackS(REDIS). We propose a blockchain-based framework that employs a lightweight multi-layer storage approach tailored for resource-constrained sensor nodes and features consensus algorithms that validate charging transactions. Furthermore, we introduce a validation node selection strategy that integrates consensus execution with charging scheduling, reducing energy consumption, and improving energy efficiency. Extensive simulations and experiments validate the effectiveness of our framework, improving energy efficiency by 30% and as much as 5 times in networks without attacks and those under full attacks, respectively.

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%.

API recommendation is a crucial task in code intelligence, aiming to suggest suitable APIs for programming queries. Recent efforts have integrated Large Language Models (LLMs) into this task. However, these methods overlook the compatibility between recommended APIs and fail to fully utilize the factual knowledge of APIs. Moreover, these prompting-only methods are limited by the insufficient domain-specific knowledge of LLMs. In this article, we propose a novel fine-tuning method, KDRAR, designed to leverage knowledge-driven reasoning with LLMs for compatible and interpretable API recommendation. To fully utilize the factual knowledge, we introduce a dual matching strategy that leverages both function descriptions and keyword matching to retrieve candidate APIs. To handle compatibility, we translate compatibility information into descriptive knowledge, which is integrated into the recommendation process. Furthermore, we adopt a distilled fine-tuning strategy: a student LLM is trained via distillation from a teacher LLM to perform step-by-step reasoning for enhanced recommendation and explanation. By considering both function matching and compatibility information, the knowledge-driven reasoning not only improves API recommendation accuracy but also provides reasonable explanations for the recommendations. Experimental results show that our method significantly outperforms baseline methods on API recommendation tasks across multiple API domains.

This is an erratum for the article “Knowledge-Driven Reasoning for Compatible and Interpretable API Recommendation via Teacher LLM Distillation” published in ACM Trans. Inf. Syst. 44, 1, Article 27 (December 2025), 30 pages.

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.

Wireless rechargeable sensor networks (WRSNs) have become an important research topic as they show merit in long-term monitoring operations. Existing techniques focus on improving system performance, while the issue of thermal effects is overlooked, leading to discrepancies between theoretical results and real-world applications. In this work, we explore and exploit the impact of the thermal effect on charging performance. At first, the thermal effect is modeled based on the Newton-Richman cooling law, followed by a new theoretical charging model based on such effect. We jointly consider the influences of charger’s self-generated heat and ambient temperature on charging utility. To address the uncertainty of temperature variation problem, we developed an online learning scheme called tHermalEffectAdapTive charging algorithm (HEAT) based on the combined multi-armed bandit method. The proposed algorithm can dynamically schedule charging tasks adaptive to temperature fluctuations while guaranteeing a logarithmic regret bound. Extensive test-bed experiments and simulations are conducted. The results demonstrate that our scheme outperforms state-of-the-art methods by at least 24.9% in charging utility across various ambient temperature conditions.

To support delay-critical applications, migrating services from the cloud to edge servers (ESs) can effectively reduce service delay. However, in such a resource-constrained scenario, providing heterogeneous services to meet diverse user needs poses significant challenges. Specifically, ESs have limited computational resources and are often energy-constrained, complicating service placement and provisioning. Existing studies propose collaboration schemes to improve resource utilization and reduce service delay. Nevertheless, these works heavily depend on full-service coverage by the cloud or rely on coarse-grained (e.g., time-cycle level) strategies that inevitably waste energy in idle time slots, which are unsuitable for energy-constrained settings and dynamic edge environments. To address these challenges, we propose a novel edge-edge collaboration method tailored for heterogeneous edge service provisioning in energy-constrained networks. First, we formulate the heterogeneous service provisioning problem with the objective of delay minimization under energy constraints and prove its NP-hardness. Our framework leverages latest task statistics to decide the service lifetime in a fine-grained time slot level, so that enables edge collaboration to maximize resource utilization and adaptability in resource-limited conditions. Specifically, we decompose the problem into three subproblems: service placement, service lifetime decision, and task scheduling, and we design targeted lightweight solutions for each, ensuring low delay and efficient energy usage. Finally, we validate our method through comprehensive simulations on real-world datasets and implement it on a testbed with three ESs. Results demonstrate that our approach reduces service delays by an average of 69.6% across various energy-constrained scenarios.

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.

Large Multimodal Models (LMMs) have shown significant progress in various complex vision tasks with the solid linguistic and reasoning capacity inherited from large language models (LMMs). Low-rank adaptation (LoRA) offers a promising method to integrate external knowledge into LMMs, compensating for their limitations on domain-specific tasks. However, the existing LoRA model serving is excessively computationally expensive and causes extremely high latency. In this paper, we present an end-to-end solution that empowers diverse vision tasks and enriches vision applications with LoRA LMMs. Our system, VaLoRA, enables accurate and efficient vision tasks by 1) an accuracy-aware LoRA adapter generation approach that generates LoRA adapters rich in domain-specific knowledge to meet application-specific accuracy requirements, 2) an adaptive-tiling LoRA adapters batching operator that efficiently computes concurrent heterogeneous LoRA adapters, and 3) a flexible LoRA adapter orchestration mechanism that manages application requests and LoRA adapters to achieve the lowest average response latency. We prototype VaLoRA on five popular vision tasks on three LMMs. Experiment results reveal that VaLoRA improves 24-62% of the accuracy compared to the original LMMs and reduces 20-89% of the latency compared to the state-of-the-art LoRA model serving systems.

With the increasing migration of business operations to the cloud, cloud service providers are facing a growing demand for faster database synchronization across diverse network conditions. Thus, compression methods are predominantly employed over the synchronized database binlog files to reduce the volume of data to be transmitted across the network. However, previous solutions typically rely on using one single compression method. This can result in data compression rates failing to align well with network bandwidth, causing data to wait for compression or transmission, thereby leading to inferior performance. To address the above issues, we propose a fine-grained hybrid adaptive compression system that (1) parses binlog files into multiple fine-grained blocks, and (2) applies a hybrid combination of multiple compression methods to seamlessly align compression speed with the network bandwidth. We have conducted extensive evaluations which demonstrate that, compared to the cutting-edge compression methods like ZSTD, LZ4, and Snappy, our approach can cut down the average latency by 66% and improve the synchronization throughput by 2.45×.

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.

Learned indexes, which model key-value data structures by machine learning models, have been extensively studied. However, the fastest immutable learned indexes (e.g., RMI) do not provide the same tight lookup bounds as classical indexes such as B-trees. There are learned indexes that provide tight bounds (e.g., PGM) but those fall short in query performance. This gives rise to an interesting open question: whether there exists a learned index that simultaneously achieves state-of-the-art empirical performance and matching complexity? In this paper, we give a positive answer to this standing problem.We propose two new online model-building policies: (1) simplifying distribution by the adoption of a proper granularity (i.e., grouping multiple keys together for model-building) and (2) actively tuning distribution through key repositioning. Additionally, we introduce a general framework that combines these two policies for performance optimization under a given memory budget. We put everything together to design VEGA, a learned index that simultaneously achieves competitive theoretical and empirical performance compared to state-of-the-art learned indexes. We conducted extensive evaluations, demonstrating VEGA achieves both better lookup and building performance.

Range filters can check whether a queried range is non-empty within a key set, with no false negatives and a low false positive rate. However, existing range filters fail to address recurring false positives in skewed or adversarial queries. In this paper, we propose Hourglass, an adaptive range filter that defends against recurring false positives through lightweight hybrid encoding and semi-sorted adaptivity. Hourglass partitions keys into prefixes, stored in a semi-sorted cuckoo filter, and suffixes, encoded using hybrid encoding schemes based on their sparsity. By preserving the order of fingerprints, the semi-sorted cuckoo filter improves space efficiency. Additionally, Hourglass introduces a new adaptivity strategy that updates fingerprints without violating the semi-sorting order. Further, Hourglass introduces a correlation-aware space allocation model to optimize space across varying key-query correlation degrees. The evaluations show that Hourglass outperforms state-of-the-art range filters under adversarial workloads, achieving a 9.8-35.4X lower false positive rate. Moreover, they demonstrate that Hourglass delivers robust performance on both synthetic and real-world datasets, as well as under varying key-query correlation degrees.

ABSTRACT Context The rise of artificial intelligence of things (AloT) has enabled smart cities and industries, and UAV‐assisted edge computing networks are an important technology to support the above scenarios. UAV‐assisted refers to leveraging UAVs as a dynamic, flexible infrastructure to assist edge network data processing and communication tasks. Multiple UAVs can use their own resources, and collaborate edge servers to train artificial intelligence (Al) models. Objective Compared with cloud‐based collaborative computing scenarios, UAV‐assisted edge collaborative learning can reduce training and inference delays and improve user satisfaction. However, UAV‐assisted edge networks scenario brings new challenges in terms of transmission burden and energy consumption. Method This paper proposes a prototype‐based joint optimization and training software system. The system consists of an optimization module and a training module. The optimization module first models an optimization problem including energy consumption and prototype error. Then it solves the optimization problem by problem transformation and plans the location of each UAV given the objects' position. After UAVs fly to the designated area and complete data collection, UAVs and the edge server train a model according to the proposed prototype‐based collaborative training module. Our training module enables multiple UAVs and an edge server to collaboratively train a model by lightweight prototype transmission and prototype aggregation. We also prove the convergence of the proposed collaborative training method. Results Results show our method reduces prototype error and energy consumption by at least 12.31% and improves model accuracy by 3.62% with a little communication burden. Conclusion Finally, we verify system performance through experiments.

With the maturation of wireless power transfer technology, Wireless Rechargeable Sensor Networks (WRSNs) have been able to provide a continuous energy supply by scheduling a Mobile Charger (MC). However, traditional charging modes suffer from fixed charging areas that lack the ability to adapt to variable sensor distributions. This inflexibility yields a gap between energy supply and utilization, resulting in relatively low charging efficiency. To address this issue, we propose an adaptive charging mode that utilizes beam steering to dynamically adjust the charging area, thereby catering to different sensor distributions encountered during the charging process. First, we build a dual-symmetric steering charging model to describe the characteristics of dynamic beam steering, enabling precise manipulation of the charging area. Then, we develop a charging power discretization based on steering angle and charging distance to obtain a finite feasible charging strategy set for MC. We reformalize charging utility maximization under energy constraints as a submodular function maximization problem, and propose an approximate algorithm to solve it. Lastly, simulations and field experiments demonstrate that our scheme outperforms other algorithms by 43.9% on average.

Wireless Power Transfer (WPT) has revolutionized the field of Wireless Rechargeable Sensor Networks (WRSNs), enabling sustainable operation of sensor nodes. Traditional mobile charging methods often require sensors to be within line-of-sight or physically accessed by the mobile charger, which may potentially lead to user safety or privacy concerns. Addressing this concern, this work is the first to introduce and validate the feasibility ofThrough-Wallcharging. We formulate theWireless charging thrOughWalls (WOW) problem to simultaneously enhance user safety and maximize charging utility. Our approach leverages fundamental principles of electromagnetics to construct an accurate charging model for Magnetic Resonance Coupling-based WPT systems. Additionally, we thoroughly analyze the impact of wall obstruction and provide a generalized framework for through-wall charging. By employing discretization techniques and approximation algorithms, we derive a near-optimal solution to the WOW problem. Extensive simulations and test-bed experiments demonstrate that our proposed approach reduces the reliance on physical access to devices, simplifies deployment in complex environments, and thereby optimizes the travel paths of mobile chargers and enhances the overall performance and lifetime of WRSNs. Compared to conventional methods, our method benefits from more reasonable scheduling order and path construction, achieving an average energy efficiency improvement of 27.8%.

Acoustic sensing for heartbeat monitoring has emerged as a prevailing research topic in wireless sensing. However, existing acoustic sensing systems face two limitations: a restricted sensing range and operation limited to a single user, impeding large-scale deployment of its applications. In this paper, we present DF-Sense, aDualForming based multi-user acousticSensingsystem for heartbeat monitoring in home settings. Specifically, we design a novel sensing signal-to-noise ratio (SSNR) enhancement model, namelyDualforming, which leverages constructive superposition across multiple subcarriers and microphones. To facilitateDualforming, we propose a novel MUltiple Subtle SIgnal Classification (MUS2IC) method and a 2-D peak identification scheme to locate and identify multiple subjects with subtle motions. Additionally, we propose a phase change-based method to promptly identify body leaning and adaptively re-localize subjects, thereby avoiding the high computational cost. Finally, we propose an enhanced recursive least squares (RLS) filter to effectively reconstruct high-quality heartbeat waveforms from Channel Frequency Response (CFR) signals affected by limb movements. Experimental results show that DF-Sense achieves high precision measurement of instantaneous heart rates within a range of 10 m, sufficient for most daily space requirements, and can monitor heartbeat for up to 6 subjects in a 2-D space.

Marine Wireless Rechargeable Sensor Networks (MWRSNs), enhanced by recent Wireless Power Transfer (WPT) technology, present a significant advancement in extending network life. Traditional methods improve network performance through algorithm optimization, but neglect charging security, exposing networks to potential attacks. This paper addresses this problem from an adversarial view and develops a novel attack for MWRSN through Denying of Charge (DoC) to maximize network destructiveness. We start by establishing a generalized on-demand charging model, essential for developing DoC tactics. Subsequently, we unveil the Collaborative DoC (CoDoC) algorithm, capable of manipulating and falsifying charging requests. Central to CoDoC is the Request Prediction Method (RPM), which forecasts the initiation of charging requests and facilitates rapid request surges to enhance the attack's efficacy. CoDoC is able to disguise the presence of the attack, which is able to escape from being detected by the base station. Theoretical analyses are provided to explore the features of the proposed scheme. To demonstrate the outperformed features of the proposed schemes, extensive simulations and test-bed experiments are conducted. Our analysis and extensive simulations demonstrate that CoDoC increases sensor node failures by 20% to 142% compared to traditional methods, highlighting its effectiveness in marine environments.

Unmanned Aerial Vehicles (UAVs) can be easily deployed as auxiliary base stations due to their convenience and flexibility. However, limited battery capacity becomes a bottleneck. Promising wireless power transfer (WPT) technologies can provide a continuous power supply for UAVs. Many of the recent works treat the UAV battery capacity as a constraint, which hinders the assurance of continuous UAV operation. Furthermore, most studies employ intelligent path-planning algorithms that lack explicit performance guarantees. In this paper, we study the problem ofPracticalOptimizing UAVTrajectory inWirelessChargingNetworks (POTWCN), which involves planning the trajectory of the wireless-powered UAV in the practical environment with obstacles by selecting candidate passing positions and determining the access order in the charging network. The goal is to maximize the benefit, i.e., balancing the total task completion time and the number of charging stations visited, so as to minimize path length and flight time, and ensure energy constraints with performance bound. To solve this problem, we first formalize the problem and prove its submodularity. Then, we propose the obstacle-aware weighted graph generation algorithm (OWGGA) to deal with the obstacles in the environment, which forms an obstacle-avoidance path using tangents and arcs between two hovering positions and the blocking obstacles. Next, we propose a dynamic charging station selection algorithm (ACSA), which maximizes the UAV's energy utilization by limiting the number of charging stations that can be included. In the algorithm, we introduce the Christofides algorithm and use the path length calculated by OWGGA as the edge weights of the graph. Subsequently, considering the UAV's energy constraints, we iteratively solve the UAV trajectory planning problem by adding the charging station with a maximized marginal benefit to the path. We prove that the proposed algorithm achieves an approximation ratio 1 – 1/e as well as the path length is at most$3\pi /4$times the optimal solution. change Simulation results show that our algorithm reduces the flight distance by 38.01% and the task completion time by 34.00% on average.

Wireless Rechargeable Sensor Networks (WRSNs) have become an important research issue as they can overcome the energy bottleneck problem of wireless sensor networks. However, existing 2D charging methods suffer from significant errors in 3D scenarios, which leads to a huge gap between theoretical results and practical applications, hindering the widespread adoption of WRSNs. In this paper, we address the chargIng utility maximizatioN problem In 3D environmenT (INIT) and provide a general solution suitable for any type of transceiver antenna. Specifically, we first establish an accurate 3D charging model to quantify the received power of sensors in 3D environments. Secondly, we design an angle-distance discretization scheme to determine appropriate charging spots for the Mobile Charger (MC). Then, we transform the mobile charging problem into a submodular function maximization problem and propose an approximation algorithm with guaranteed performance to solve it. Finally, our method has been extensively evaluated through experiments and simulations and has demonstrated considerable advantages over other comparison algorithms in real-world 3D environments. On average, it has achieved an impressive 34.8% improvement in charging utility and a remarkable 56.1% reduction in the number of dead sensors.

In many real-life applications, wireless chargers are deployed outdoor or in public area or even unattended environment such as hotels, restaurants, retail stores. They are exposed to various risks and malicious attacks that may break them down and further incur significant cost (e.g., battery replacement and maintenance) or performance degradation. Hence, we consider the problem ofFault-tolerant wIreless chaRger placeMent (FIRM): given a set of wireless chargers and a set of tasks to be collaboratively conducted by a set of rechargeable devices, determining where to deploy the chargers to maximize the worst-cast overall task charging utility subject to the constraint that up to$\tau$chargers may break down. FIRM is a non-linear combinatorial two-level optimization problem. We first consider a relaxed version of FIRM (FIRM-R for short) corresponding to the inner optimization problem in FIRM. To address FIRM-R, we first propose an area discretization scheme to convert the infinite solution space into finite candidate positions. We then devise a power allocation method, based on which we prove that FIRM-R falls into the realm of maximizing a monotone submodular function under a uniform constraint. We then propose a constant-factor approximation algorithm to solve FIRM-R. Taking the above approximation algorithm as a subroutine, we further develop an approximation algorithm that solves FIRM with a constant-factor approximation ratio. Our extensive simulations and field experiments demonstrate that the overall charging utility of our proposed algorithm FIRM considering fault tolerance by greedy removal of$\tau$chargers outperforms the that of FIRM-R without considering fault tolerance by greedy removal of$\tau$chargers by at least 119.89%.

For Unmanned Aerial Vehicles (UAVs) monitoring tasks, capturing high quality images of target objects is important for subsequent recognition. Concerning the problem, many prior works study placement/trajectory planning for UAVs to maximize the quality of captured images. However, all of them overlook a fact thatUAV monitoring may cause a huge risk/annoyance on living objects.In this paper, we investigate the novel problem of oPtimizing uncrewed aErial vehicles plAcement byConsidering both monitoring utility and adverseEffects (PEACE). We propose an approach to solve PEACE, which is proved to be NP-hard. Overall, our approach achieves a$1- \frac{1}{e}-\varepsilon$approximation ratio. First, we approximate the original problem of PEACE as a classical problem of Monotone Submodular function Maximization under a Uniform Matroid constraint (MSMUM) with a controlled gap. Then, for MSMUM, we propose a combination of algorithms achieving a$1-\frac{1}{e}$approximation and$O(n\log n)$time complexity considering the correlation among the UAV monitoring strategies. The proposed algorithms outperform existing algorithms for MSMUM through theoretical analysis and experimental results. Extensive simulations and field experiments demonstrate the effectiveness of our approach, achieving performance gains of 9.0% to 1434.5% compared to existing methods.

Wireless power transmission has been widely used to replenish energy for wireless sensor networks, where the energy consumption rate of sensor nodes is usually time varying and indefinite. However, few works have investigated the problem of long-term charging scheduling with random variable. This article designs an optimization model for the long-term scheduling of chargers to maximize the time-averaged charging utility while ensuring its time-averaged constraints of budget and response rate. The Lyapunov optimization technique is adopted to transform the stochastic optimization problem into a deterministic optimization problem, which remains NP-hard. Thus, an approximation algorithm following greedy approach is proposed to solve the deterministic optimization problem. We further provide the theoretical analysis of feasibility and performance guarantee of the proposed scheduling algorithm. The simulation results show that our algorithm outperforms three comparison algorithms by 6.53%, 20.04%, and 19.97% in terms of time-averaged charging utility, as well as by 11.25%, 4.42%, and 3.73% in terms of time-averaged response rate on average.

Approximate membership query (AMQ) data structures can approximately determine whether an element exists in a given dataset. They are widely used in parallel and distributed systems (e.g., high-performance databases, distributed cache systems, and bioinformatics systems) to avoid unnecessary dataset accesses, thereby accelerating massive data processing. For AMQ data structures used in the above systems, achieving high throughput, low false positive rate, and large capacity objectives simultaneously is critical but challenging. Porting AMQ data structures from DRAM to persistent memory makes it possible to achieve the above three objectives simultaneously, but this porting is not a trivial task. Specifically, existing AMQ data structures generate numerous random accesses and/or sequential writes on persistent memory, resulting in poor throughput. Therefore, in the conference version of this paper, we proposed a novel AMQ data structure called wormhole filter, which achieves high throughput on persistent memory, thereby achieving the above three objectives simultaneously. In this journal version, we extend our prior work by introducing parallel wormhole filters to enhance parallel performance. Additionally, we integrate parallel wormhole filters into the LevelDB database system to show that porting AMQ data structures to persistent memory significantly improves system endto-end throughput. Theoretical analysis and experimental results show that wormhole filters significantly outperform state-of-theart AMQ data structures. For example, wormhole filters achieve 12.06× insertion throughput, 1.98× positive lookup throughput, and 8.82× deletion throughput of the best competing baseline.

Approximate membership query (AMQ) data structures can approximately determine whether an element is in the set with high efficiency. They are widely used in distributed systems, database systems, bioinformatics, IoT applications, data stream mining, etc. However, the memory consumption of AMQ data structures grows rapidly as the data scale grows, which limits the system's ability to process a massive amount of data. The emerging persistent memory provides a close-to-DRAM access speed and terabyte-level capacity, facilitating AMQ data structures to handle massive data. Nevertheless, existing AMQ data structures perform poorly on persistent memory due to intensive random accesses and/or sequential writes. Therefore, we propose a novel AMQ data structure called wormhole filter, which achieves high performance on persistent memory by reducing random accesses and sequential writes. In addition, we reduce the number of log records for lower recovery overhead. Theoretical analysis and experimental results show that wormhole filters significantly outperform competitive state-of-the-art AMQ data structures. For example, wormhole filters achieve 23.26× insertion throughput, 1.98× positive lookup throughput, and 8.82× deletion throughput of the best competing baseline.

The development of Wireless Power Transfer (WPT) technology presents a promising avenue to support rechargeable UAVs in executing a wide range of energy-intensive tasks. However, most UAV path-planning schemes focus solely on task completion and maximizing coverage, often overlooking how UAVs should navigate in the presence of multiple charging stations organized as a wireless charging network that can replenish their power. This paper studies the problem of determining the service points serving the ground users as well as the trajectory of the wireless-powered UAV in the wireless charging network to maximize the total user-UAV communication utility. To this end, we formulate an optimization problem under typical path constraints, which introduces significant complexity. We propose a novel algorithm, where an improved k-means++ algorithm is employed to determine potential service points for the UAV, and the optimized trajectory is generated at each step by comparing the quantified communication utility and energy consumption utility. The performance of the proposed algorithm is evaluated through simulation experiments. Our results demonstrate 8.68% ~ 158.74% improvement compared with comparison algorithms.

Sketches have gained popularity as effective methods for estimating frequency in data streams, and optimizing their accuracy is critical in many applications. However, while sketches are backed by a standard guarantee under the worst-case analysis, their actual errors can vary significantly with real-world skewed data streams. Therefore, it is challenging to configure sketches to optimize accuracy without prior knowledge of the input. Moreover, even with a new configuration, it is unclear when to apply it. This paper presents a novel sketch framework that can be dy-namically configured to optimize the accuracy given a processed data stream. Specifically, we provide a precise guarantee and derive an optimal number of hash functions under the Zipfian distribution, which is an appropriate way to model skewed data streams in practice. We then propose a dynamically configurable sketch framework, namely DISCO, that can estimate the distri-bution parameter and adjust the number of hash functions on the fly to optimize accuracy. We provide rigorous mathematical analysis and apply DISCO to three classical solutions, including the Count-min, Conservative Update, and Count sketches. Experimental results, using synthetic and real datasets, show that DISCO can achieve the optimal configuration for the metric (i.e., FP) related to the sketch guarantee, while achieving near-optimal accuracy for other common metrics (e.g., ARE) compared with state-of-the-art methods.

In this paper, we consider the problem of approximate membership testing problem on skewed network traffic traces, in which some hot or popular items repeat frequently. Previous solutions suffer from either high false positive rates or low lookup throughput. To address this problem, we propose a variant of the cuckoo filter, enhanced with a hotness-aware suffix cache. We note that a false positive item must have a matched fingerprint in the cuckoo filter, and propose to reduce false positives by memorizing them, but with their suffixes only. For each false positive item, we apply a linear-congruential-based hash function and then divide the hash value into three parts: the bucket index to be accessed in the cuckoo filter, the fingerprint to be stored in the cuckoo filter, and the suffix to be cached. Combining the three parts, we propose RCF that can uniquely identify a hot false positive item, which thus reduces hot false positives. Our evaluation results indicate that RCF significantly outperforms non-adaptive filters on skewed data traces. Given the same memory size, it achieves a much lower false positive ratio without sacrificing its lookup throughput. Compared with adaptive filters, RCF provides a competitive false positive ratio while offering a considerably higher lookup throughput.

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∼ 9× throughput compared with the state-of-the-art video analytics pipelines.

Complex event recognition (CER) refers to identifying specific patterns composed of several primitive events in event stores. Since full-scanning event stores to identify primitive events holding query constraint conditions will incur costly I/O overhead, a mainstream and practical approach is using index techniques to obtain these events. However, prior index-based approaches suffer from significant I/O and sorting overhead when dealing with high predicate selectivity or long query window (common in real-world applications), which leads to high query latency. To address this issue, we propose ACER, a Range Bitmap-based index, to accelerate CER. Firstly, ACER achieves a low index space overhead by grouping the events with the same type into a cluster and compressing the cluster data, alleviating the I/O overhead of reading indexes. Secondly, ACER builds Range Bitmaps in batch (block) for queried attributes and ensures that the events of each cluster in the index block are chronologically ordered. Then, ACER can always obtain ordered query results for a specific event type through merge operations, avoiding sorting overhead. Most importantly, ACER avoids unnecessary disk access in indexes and events via two-phase filtering based on the window condition, thus alleviating the I/O overhead further. Our experiments on six real-world and synthetic datasets demonstrate that ACER reduces the query latency by up to one order of magnitude compared with SOTA techniques.

Unmanned Aerial Vehicle (UAV) mounted base stations have been widely used to enhance the existing terrestrial communication infrastructures. In this paper, we investigate the problem of deploying Wireless-Powered UAV base stations (UAV-BSs) for maximizing Throughput (WPUT), that is, deploying a specified number of UAV base stations, which can harvest power from Wireless Charging Towers (WCTs), to maximize the total throughput for all users under the constraint of providing communication service continuously with the wireless power. To address the problem, we first approximate the nonlinear charging power as a piecewise constant function while bounding the approximation error. Then the entire region is divided into different charging subareas for the UAVs. Furthermore, we discretize the subareas by another piecewise constant function to approximate the communication rate with error bound. Finally, the problem is transformed into a 0–1 integer programming problem. We apply the primal-dual technique to deal with the problem after LP-relaxation and achieve a$\frac{1}{(1+\epsilon)^{2}}$-approximation algorithm. Simulation results show that our proposed algorithm can outperform comparison algorithms by 36.92% on average.

Abstract In this article, we propose a mobile edge computing (MEC)‐related system named PD‐Gait, which can measure gait parameters of Parkinson's disease patients in a contactless and privacy‐preserving manner. We utilize inaudible acoustic signals and band‐pass filters to achieve privacy data protection in the physical layer. The proposed framework can be easily deployed in the mobile end of MEC, and hence release the edge server in cybersecurity attacks fighting. The gait parameters include stride cycle time length and moving speed, and hence providing an objective basis for the doctors' judgment. PD‐Gait utilizes acoustic signals in bands from 16 to 23 kHz to achieve device‐free sensing, which would release both doctors and patients from the tedious wearing process and psychological burden caused by traditional wearable devices. To achieve robust measurement, we propose a novel acoustic ranging method to avoid “broken tones” and “uneven peak distribution” in the received data. The corresponding ranging accuracy is 0.1 m. We also propose auto‐focus micro‐Doppler features to extract robust stride cycle time length, and can achieve an accuracy of 0.052 s. We deployed PD‐Gait in a brain hospital and collected data from 8 patients. The total walked distance is over 330 m. From the overall trend, our results are highly correlated with the doctor's judgment.

Currently, Coronavirus Disease 2019 (COVID-19) is still endangering world health and safety and deep learning (DL) is expected to be the most powerful method for efficient detection of COVID-19. However, patients' privacy concerns prohibit data sharing between medical institutions, leading to unexpected performance of deep neural network (DNN) models. Fortunately, federated learning (FL), as a novel paradigm, allows participating clients to collaboratively train models without exposing source data outside original location. Nevertheless, the current FL-based COVID-19 detection methods prefer optimizing secondary objectives including delay, energy consumption and privacy, while few works focus on improving the model accuracy and stability. In this paper, we propose a federated learning framework with dynamic focus for COVID-19 detection on CXR images, named FedFocus. Specifically, to improve the training efficiency and accuracy, the training loss of each model is taken as the basis for parameter aggregation weights. As training layer deepens, a constantly updated dynamic factor is designed to stabilize the aggregation process. In addition, to highly restore the real dataset, the training sets in our experiments are divided based on the population and the infection of three real cities. Extensive experiments conducted on the real-world CXR images dataset demonstrate that FedFocus outperforms the baselines in model training efficiency, accuracy and stability.

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.

Streaming triangle counting is a critical issue in graph stream mining, with applications in dense subgraph discovery, web mining, anomaly detection, and more. Recent efforts have focused on estimating triangle counts in graph streams, primarily through sampling methods. However, because of limited memory resources for handling high speed streams, traditional sampling methods suffer from reduced sampling rate and thereby performance loss. In this paper, we propose a new compact data structure called uHLL to process edge streams by considering the tradeoff between estimation accuracy and memory efficiency. Furthermore, different from conventional triangle counting algorithms, we solve the estimation of union set cardinality for edge-local triangle count under both centralized and distributed framework, so as to efficiently estimate the global triangle count by a one-pass streaming algorithm. To the best of our knowledge, this is the first implementation of a distributed framework using a compact data structure for streaming triangle counting. We provide theoretical proof of unbiasedness and derive the variance of the union set and global triangle count. We compare our scheme with 11 algorithms, showing that under the same experimental setting, uHLL and distributed uHLL are at least$ 2.3$and$ 1.7$times more accurate than the state-of-the-art, respectively.

Index structures are powerful tools for improving query performance and reducing disk access in database systems. Multi-dimensional indexes, in particular, are used to filter records effectively based on multiple attributes. Classical multi-dimensional index structures, such as KD-Tree, Quadtree, and R-Tree, have been widely used in modern databases. However, advancements in hardware and algorithms have led to the emergence of new types of multi-dimensional index structures. In this paper, we begin by reviewing classical multi-dimensional indexes. Next, we explore the approaches that leverage modern hardware features, such as Solid-State Drive, Non-Volatile Memory, Dynamic Random Access Memory, and Graphics Processing Unit, to improve the performance of multi-dimensional indexes in various aspects. Then, we investigate the novel work of multi-dimensional indexes that apply state-of-the-art machine learning techniques. Finally, we discuss the challenges and future research directions for multi-dimensional indexing methods.

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.

Wireless Power Transfer (WPT) has received more and more attention for its convenience and reliability. In this paper, we first propose the notion of omnidirectional charging. First, we consider the problem of detecting whether the target area achieves omnidirectional charging given a deterministic deployment of chargers. We use piecewise constant approximation and area discretization techniques to partition the target area and approximate charging power as constants. Next, we propose the Minimum Coverage Set extraction technique to design a fast detection algorithm. Second, we design a charger deployment scheme that satisfies omnidirectional charging. By placing the chargers at the triangle lattice points, we estimate the length of triangle lattice side length that satisfies omnidirectional charging, and derive the error bound with the optimal length. Third, we determine the probability that the target area achieves omnidirectional charging given a random deployment of chargers. We devise both analytical and numerical solutions for the problem with good accuracy. Finally, we conduct simulation and field experiments, and the results show that the running speed of our omnidirectional charging detection algorithm is at least$1\times$faster than comparison algorithms, and the consistency degree of our theoretical results and field experimental results is larger than$93.6 \%$.

Benefitting from the discovery of wireless power transfer (WPT) technology, the wireless rechargeable sensor network (WRSN) has become a promising way for lifetime extension for wireless sensor networks. In practical WRSN scenarios, obstacles can be found almost everywhere. Most state-of-the-art researches believe that obstacles will always degrade signal strength, and omit the influence of obstacles for simplifying the computation process. However, overlooking the positive impacts of obstacles on signal propagation is inconsistent with the intrinsic features of electromagnetic waves. To address this issue, in this paper, we explore the wireless signal propagation process and provide a theoretical charging model to enhance the charging efficiency by leveraging obstacles. Through utilizing the concept of the Fresnel Zone model, we re-formalize the wireless charging model and discretize the charging area and charging time to determine the best charging locations as well as charging duration. We model the chargingEfficiencyMaximization withObstacles (EMO) problem as a submodular function maximization problem and propose a cost-efficient algorithm to solve it. Finally, test-bed experiments and extensive simulations are both conducted to verify that our schemes outperform baseline algorithms by$33.46\%$on average in charging efficiency improvement.

Benefitting from the recent breakthrough of wireless power transfer technology, Wireless Rechargeable Sensor Networks (WRSNs) have become an important research topic. Most prior arts focus on system performance enhancement in the ideal environment that ignores the impact of obstacles. This contradicts the practical applications in which obstacles can be found almost anywhere and have dramatic impacts on energy transmission. In this paper, we concentrate on the problem of charging a practical WRSN in the presence of obstacles to maximize the charging utility under specific energy constraints. First, we propose a new theoretical charging model with obstacles based on the Fresnel diffraction model and conduct experiments to verify its effectiveness. Then, we propose a spatial discretization scheme to obtain a finite feasible charging position set for mobile charger (MC), which largely reduces computation overhead. Afterwards, we re-formalize charging utility maximization with energy constraints as a submodular function maximization problem and propose a cost-efficient algorithm with an approximation guarantee to solve it. In addition, we present a theoretical analysis and a relevant mathematical proof of our algorithm. Finally, we demonstrate that our scheme outperforms other competing algorithms by 20.5% on average in terms of charging utility through test-bed experiments and extensive simulations.

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.

Acoustic ranging has been viewed as a promising Human-Computer Interaction (HCI) technology in many scenarios, such as Augmented Reality (AR)/Virtual Reality (VR) and smart appliances. Most ranging systems with distributed devices undergo an extra calibration process to remove the timing errors. However, the calibration process needs user intervention. Furthermore, it should assume that the clock drifts are linear and stable, which is disabled within tens of minutes. In this paper, we introduce a self-calibrated acoustic ranging system that achieves sub-millimeter accuracy on distributed asynchronous devices. Based on our theoretical timing model, we precisely cancel both the system delay and the nonlinear clock drift with carefully designed Orthogonal Frequency-Division Multiplexing (OFDM) ranging signals. Our synchronization scheme achieves a timing accuracy of 1.9 microseconds, which allows us to build large-scale virtual acoustic arrays. Based on such a calibration scheme, our localization system achieves a ranging error of$\rm{0.39}~mm$within three meters in real-world experiments.

Wireless Power Transfer (WPT) technology has been developed rapidly in recent years. The cooperative charging model and corresponding scheduling methods have been proposed to save the charging cost in paid charging service. However, the state-of-the-art methods ignore the spatial occupation issue of rechargeable devices. Moreover, the cooperative charging scheduling in directional wireless charging has not been studied yet. This paper studies the cooperative scheduling for directional wireless charging with spatial occupation. We formulate the Cooperative Charging Scheduling with Spatial occupation (CCSS) problem of Mobile Rechargeable Sensor Devices (MRSDs) for optimizing the total cost of whole charging system. We first investigate the properties of optimal arrangement of MRSDs in charging group and calculate the tight intervals of charging angles of MRSDs. We show that it is sufficient to bound the error by conducting angle discretization for only two MRSDs in each charging group. Then, a$(\ln n+1)(1+\varepsilon)$-approximation algorithm of the CCSS problem is proposed based on greedy approach, where$n$is the number of MRSDs, and$\varepsilon$is the discretization error. The results of extensive simulations and field experiments demonstrate that our algorithm can reduce at most 42.5% total cost comparing with the benchmark algorithms.

Wireless Power Transmission (WPT) has been widely used to replenish energy for wireless rechargeable sensor networks. This paper concerns the fundamental issue of robust fault-tolerant placement of wireless chargers for directional charging. Following the general directional charging model, we formulate theCharger Placement for Robust Coverage (CPRC)problem, which has continuous and infinite constraints, for resisting the wireless charger failure. We transform the problem to the equivalent integer program problem without performance loss by area partition and dominating strategy extraction. We show that the greedy algorithm achieves the logarithmic approximation ratio. We further formulate theCharger Placement for Robust Utility (CPRU)problem for resisting the sensor node failure. This problem also has continuous and infinite constraints. We transform the problem to the combinational optimization problem with finite strategy space through the techniques of charging power approximation, area discretization and dominating strategy extraction. We present the algorithm, which utilizes the combination of binary search and greedy algorithm, to solve theCPRUproblem. We conduct both simulations and field experiments to validate our theoretical results. The simulation results show that the proposed algorithms forCPRCandCPRUcan outperform comparison algorithms by at least 17.48% and 21.15%, respectively.

Satellite edge computing, as an extension of ground edge computing, is a key technology for achieving seamless global computing coverage. However, the low earth orbit (LEO) satellites have limited computing resources and are moving at a high speed. This naturally poses a challenge to find more suitable computation offloading strategies with minimum network latency and energy consumption, especially when a large number of co-existing users are to offload their tasks. In this paper, therefore, we mainly focus on computation offloading in the satellite edge computing network (SECN) by jointly considering LEO satellites' mobility and SECN's heterogeneous resource constraints to explore more practical computation offloading strategies. We first formulate the problem ofMobility-awareComputationOffloading (MCO) in the SECN via specifying the effect of LEO satellites' high-speed movement on the computation offloading, aiming to minimize the network latency and energy consumption. Considering the MCO problem is discrete and non-convex as the objective function and constraints are associated with the binary decision variables. We then convert the original non-convex problem into a continuous convex problem which is proved to be feasible. To avoid a high computational complexity incurred by the extensive co-existing user offloading, we designMCO-A, a distributed algorithm based on ADMM (alternating direction method of multipliers) to solve the MCO problem efficiently. Finally, the performance ofMCO-Ais evaluated via extensive experiments including small-scale and large-scale scenarios. The experimental results show that MCO-A can achieve a lower network latency and energy consumption in an efficient way compared with the baseline and state-of-the-art approaches.

Nowadays, there exists a lot of cross-region data transmission demand on the cloud. It is promising to use serverless computing for data compressing to save the total data size. However, it is challenging to estimate the data transmission time and monetary cost with serverless compression. In addition, minimizing the data transmission cost is non-trivial due to the enormous parameter space. This paper focuses on this problem and makes the following contributions: 1) We propose empirical data transmission time and monetary cost models based on serverless compression. It can also predict compression information, e.g., ratio and speed using chunk sampling and machine learning techniques. 2) For single-task cloud data transmission, we propose two efficient parameter search methods based on Sequential Quadratic Programming (SQP) and Eliminate then Divide and Conquer (EDC) with proven error upper bounds. Besides, we propose a parameter fine-tuning strategy to deal with transmission bandwidth variance. 3) Furthermore, for multi-task scenarios, a parameter search method based on dynamic programming and numerical computation is proposed. We have implemented the system called Fluid-Shuttle, which includes straggler optimization, cache optimization, and the autoscaling decompression mechanism. Finally, we evaluate the performance of Fluid-Shuttle with various workloads and applications on the real-world AWS serverless computing platform. Experimental results show that the proposed approach can improve the parameter search efficiency by over$3\times $compared with the state-of-art methods and achieves better parameter quality. In addition, our approach achieves higher time efficiency and lower monetary cost compared with competing cloud data transmission approaches.

Finding special items in data streams, like heavy hitters, top-$k$items, and persistent items, has always been a hot topic in the field of network measurement. While data streams nowadays are usually high-dimensional, most prior works optimize data structures to accurately find special items according to a certain primary dimension and yield little insight into the correlations between dimensions, where the dimension can be a single data dimension or a combination of multiple data dimensions. Therefore, we propose to find special quadratic elements in data streams to reveal the close correlations between the primary and secondary dimensions. Here, both the primary and secondary dimensions are selected according to specific application purposes. Based on the special items mentioned above, we extend our problem to three applications related to heavy hitters, top-$k$, and persistent items, and design a generic framework DUET to process them. We analyze the error bound of our algorithm theoretically and conduct extensive experiments on four publicly available data sets. Our experimental results show that DUET can achieve 3.5 times higher throughput and three orders of magnitude lower average relative error than cutting-edge algorithms. Moreover, we propose an optimized framework based on DUET, namely O-DUET, to further improve the estimation accuracy. We also discuss a hardware-version DUET and deploy it on Tofino.

The quality of the video stream is the key to neural network-based video analytics. However, low-quality video is inevitably collected by existing surveillance systems because of poor-quality cameras or over-compressed/pruned video streaming protocols, e.g., as a result of upstream bandwidth limit. To address this issue, existing studies use quality enhancers (e.g., neural super-resolution) to improve the quality of videos (e.g., resolution) and eventually ensure inference accuracy. Nevertheless, directly applying quality enhancers does not work in practice because it will introduce unacceptable latency. In this paper, we present AccDecoder, a novel accelerated decoder for real-time and neural-enhanced video analytics, selects a few frames adaptively via Deep Reinforcement Learning (DRL) to enhance the quality and inference then reuse on the unselected ones. Next, we extend AccDecoder to AccDecoder$+$by formulating the resolution-involved Markov decision process (MDP) to achieve resolution adaptation; it aims to trade accuracy and latency corresponding under various video resolutions. Proved by experiments, AccDecoder provides efficient inference capability via filtering important frames using DRL for DNN-based inference and reusing the results for the other frames via extracting the reference relationship among frames and blocks, which contributes 6-21% accuracy improvement and a latency reduction of 20-80% than baselines. Compared with AccDecoder, AccDecoder$+$achieves an additional 2-7% accuracy improvement.

The approximate membership query (AMQ) data structure is a kind of space-efficient probabilistic data structure. It can approximately indicate whether an element exists in a set. The AMQ data structure has been widely used in network measurements, network security, network caching,etc. Resizing is an extensively utilized operation of the AMQ data structure, but it can lead to system performance degradation. We summarize two main problems that lead to such degradation. Specifically, one of them is that the resizing operation can block other operations, while the other one is that the throughput of AMQ structures will deteriorate after multiple resizing operations due to more computation cost. However, existing related work cannot alleviate both of them. Therefore, we propose a novel AMQ data structure called bamboo filters, which can alleviate the two problems simultaneously. Bamboo filters can insert, look up, and delete an element in constant time. They can also dynamically resize in a fine-grained way. Furthermore, we propose space utilization adaptive bamboo filters that adaptively trigger resizing operations according to the space utilization, thereby achieving lower average memory consumption. Experimental results show that our scheme significantly outperforms state-of-the-art work. Especially, bamboo filters achieve 2.12$\times$lookup throughput of the logarithmic dynamic cuckoo filter.

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.

In this paper, we study the deployment of$K$heterogeneous UAVs to monitor Points of Interest (PoIs) in a disaster zone, where a PoI may represent a school building or an office building, in which people are trapped. A UAV can take images/videos of PoIs and send its collected information back to a nearby rescue station for decision-making. Unlike most existing studies that focused on only homogeneous UAVs, we here study the scheduling of$K$heterogeneous UAVs, where different UAVs have different energy capacities and functionalities that lead to different monitoring qualities (monitoring rewards) of each PoI. For example, one type of UAVs can take only visual images while the other type of UAVs can take both visual and thermal infrared images. In this paper, we investigate a problem of scheduling$K$heterogeneous UAVs to monitor PoIs so that the sum of monitoring rewards received by all UAVs is maximized, subject to energy capacity on each UAV. We propose the very first$\frac {1}{3}$-approximation algorithm for this scheduling problem. We also evaluate the performance of the proposed algorithm, using real parameters of commercial UAVs. Experimental results show that the performance of the proposed algorithm is promising, which is improved by 25%, compared with existing algorithms.

In the coming era of Metaverse, Augmented Reality (AR) has become a key enabler of diverse applications including healthcare, education, smart cities, and entertainments. To provide users with interactive and immersive experience, most AR applications require extremely high responsiveness and ultra-low processing latency. Mobile edge computing (MEC) has demonstrated great potentials in meeting such stringent latency requirements and resource demands of AR applications, by implementing AR requests in edge servers within the proximity of users. In this paper, we investigate the reward maximization problem for AR applications with uncertain resource demands in an MEC network, such that the accumulative reward of services provided for AR applications is maximized, while ensuring that the responsiveness of AR applications is enhanced, subject to network resource capacity. To this end, we formulate an exact solution when the problem size is small, otherwise we devise an efficient approximation algorithm with a provable approximation ratio for the problem. We also develop an online learning algorithm with a bounded regret for the dynamic reward maximization problem without the knowledge of future arrivals of AR requests, by adopting the Multi-Armed Bandits (MAB) technique. Considering maximizing the reward may defer the implementations of some urgent yet low-award requests, we propose a fairness-aware online learning algorithm for the dynamic reward maximization problem, through a data rate prediction mechanism that adopts a multi-task and multi-timescale Long Short-Term Memory (MT2-LSTM) method. Finally, we evaluate the performance of the proposed algorithms for AR applications by building a real test bed. Experimental results show that the proposed algorithms outperform existing studies by improving the award by 13%.

Wireless Rechargeable Sensor Networks (WRSNs) have become an important research issue as they can overcome the energy bottleneck problem of wireless sensor networks. However, inaccurate discretization methods and imprecise charging models yield a huge gap between theoretical results and practical applications, making it difficult for wide adoptions. In this paper, we focus on designing a precise charging method for maximizing charging utility when line-of-sight (LOS) and none-line-of-sight (NLOS) charging cases exist in complicated environments. First, we design discretization methods for charging area and charging orientation for precisely constructing the charging model. Then, we develop a novel electromagnetic wave reflection model to describe the signal propagation model in the presence of obstacles. We formalize the mobile charging problem into a submodular function maximization problem which can be solved by a proposed algorithm with an approximation guarantee. Finally, extensive experiments and simulations demonstrate that our schemes outperform comparison algorithms by 32.5% on average in charging utility in complicated environments.

This paper presents a Long Range (LoRa) data aggregation system (LoRaPDA) that aggregates data (e.g., sum, average, min, max) directly in the physical layer. In particular, after coordinating a few nodes to transmit their data simultaneously, the gateway leverages a new multi-packet reception (MPR) approach to compute aggregate data from the phase-asynchronous superimposed signal. Different from the analog approach which requires additional power synchronization and phase synchronization, our MRP-based digital approach is compatible with commercial LoRa nodes and is more reliable. Different from traditional MPR approaches that are designed for the collision decoding scenario, our new MPR approach allows simultaneous transmissions with small packet arrival time offsets, and addresses a new co-located peak problem through the following components: 1) an improved channel and offset estimation algorithm that enables accurate phase tracking in each symbol, 2) a new symbol demodulation algorithm that finds the maximum likelihood sequence of nodes’ data, and 3) a soft-decision packet decoding algorithm that utilizes the likelihoods of several sequences to improve decoding performance. Trace-driven simulation results show that the symbol demodulation algorithm outperforms the state-of-the-art MPR decoder by 5.3$\times$in terms of physical-layer throughput, and the soft decoder is more robust to unavoidable adverse phase misalignment and estimation error in practice. Moreover, LoRaPDA outperforms the state-of-the-art MPR scheme by at least 2.1$\times$for all SNRs in terms of network throughput, demonstrating quick and reliable data aggregation.

We propose UltraCLR, a new contrastive learning framework that fuses dual modulation ultrasonic sensing signals to enhance gesture representation. Most existing ultrasound-based gesture recognition tasks rely on a large amount of manually labeled samples to learn task-specific representations via end-to-end training. However, they cannot exploit unlabeled continuous gesture signals that are easy to collect. Inspired by recent self-supervised learning techniques, UltraCLR aims to autonomously learn a ubiquitous gesture signal representation that can benefit all tasks from low-cost unlabeled signals. We use the STFT heatmap as a secondary input and leverage the contrastive learning framework to improve the high-quality Channel Impulsive Response heatmap input representations. The learned representations can better represent the spatial-position information and intermediate states of gesture movement. With the representation learned by UltraCLR, we can greatly reduce the complexity of downstream gesture recognition tasks so that they can be completed using a simple classifier trained with a small training set and a lower computational cost. Our experimental results show that UltraCLR outperforms state-of-the-art gesture recognition systems with only a few labeled samples and achieves more than 85% reduction in computational complexity and over 9× improvement in inference speed.

Deep learning models rely on highly optimized tensor libraries for efficient inference on heterogeneous hardware. Current deep compilers typically predetermine layouts of tensors and then optimize loops of operators. However, such unidirectional and one-off workflow strictly separates graph-level optimization and operator-level optimization into different system layers, missing opportunities for unified tuning.

Device-free gesture recognition schemes based on acoustic sensing signals are promising solutions for next-generation human-computer interaction systems. However, existing gesture recognition frameworks reuse visual neural networks to perform feature extraction. These approaches ignore the time sequence nature of the acoustic signal and treat acoustic echo profiles solely as 2D images. In this paper, we propose a time-sequence-based deep learning framework that can exploit the spatio-temporal information of sensing signals. The framework first fuses multi-channel acoustic signals to extract spatial gesture features from a single acoustic frame and then uses the Transformer network to discover the timing relations between spatial features. Our extensive evaluations with real-world datasets show that our light-weighted framework outperforms the state-of-the-art in classifying 14 gestures and achieves an average accuracy of 95.85%.

Underwater Optical Wireless Sensor Networks (UOWSNs) are gaining an increasing demand in industrial and commercial applications as they can achieve high-speed communication. However, prior arts concentrate on promoting the performance of UOWSNs, while the reliability issue has not been fully addressed. In this paper, we propose a novel reliable data delivery scheme based on a cluster structure. First, we determine the orientation of each sensor for directional optical communication, which aims to establish reliable next-hop links among sensors. We formalize such an orientation problem into a submodular function maximization problem and propose a greedy method with an approximation ratio guarantee to solve it. Then, a cluster head designation scheme is developed to improve the data delivery success rate while minimizing the number of cluster heads. Finally, extensive simulations are conducted to demonstrate the effectiveness of the proposed scheme. The results reveal that compared with other algorithms, the proposed scheme can ensure a data delivery success rate of over 98.5 % while only keeping 45.3% fewer cluster heads. Furthermore, test-bed experiments are carried out to verify the applicability of the proposed scheme in practical applications.

Classic contextual combinatorial multi-armed bandit problems aim to maximize the expected cumulative joint reward in the long run, where a learner plays a set of arms (i.e., a super arm) with time-invariant linear rewards of context features in each round. However, in many real-world applications, linear-reward assumptions often fail to be satisfied and the environment is in general non-stationary, leading to low performance with the bandit models above. Existing works fail to deal with non-linear rewards in the non-stationary environment and the algorithmic challenge remains. In this paper, we initiate the study of a non-stationary neural contextual combinatorial bandit problem, where the reward function of each individual arm can be estimated by a deep neural network based on boundedness assumption and a time-variant reward mapping function. Furthermore, we design an algorithm NNCMAB, which dynamically partitions the context subspace into multiple subspaces and fits reward mapping functions for each subspace by neural networks such that only the models of related subspaces are re-trained when local environment changes happen. NNCMAB can provably achieve $\tilde{O}\left(T^{\frac{3}{4}}+\sqrt{T}N_{c}\right)$ regret, where T is the number of rounds, and $N_{c}$ is a parameter associated with the distribution change. Evaluation results under synthetic and real-world LastFM datasets show that NNCMAB significantly outperforms other state-of-the-art with both linear and non-linear individual rewards under non-stationary environments.

Approximate membership query (AMQ) data structures can efficiently indicate whether an element exists in a data set. Therefore, they are widely used in data mining applications such as IoT streaming data mining, anomaly detection, duplicate detection, record linkage, and community discovery. The data amount to be processed in real-world applications often changes frequently and dynamically. Thus, before using the AMQ data structures, it is necessary to configure their capacity to the maximum number of elements that will be stored during runtime. We observe that when the number of elements stored in an AMQ data structure is lower than its capacity, a significant amount of space is wasted, making the false positive rate much higher than expected. To tackle this problem, we propose the variable-length encoding framework. It dynamically adjusts the encoding length of each element according to the number of elements stored in the AMQ data structure. Based on this design, the variable-length encoding framework can make full use of the memory space allocated to AMQ data structures, thereby improving the space efficiency and reducing the false positive rate. In addition, as a general encoding scheme, the variable-length encoding framework can be widely used in different types of AMQ data structures. Theoretical analysis and evaluation results show that AMQ data structures using the variable-length encoding framework have significantly lower false positive rates compared with state-of-the-art AMQ data structures. For example, when the load factor is 25%, the variable-length encoding framework can reduce the false positive rate of AMQ data structures by 88.15% on average (up to 99.40%).

The constantly evolving demands of modern applications pose increasingly higher requirements for key-value (KV) stores, especially when dealing with update-intensive workloads. RocksDB, an LSM-tree-based KV store, has designed a merge operator to optimize update throughput by directly recording the partially modified value fields. However, this operator negatively affects read performance because it will result in the multiple coexistences of partial values for the same key, which thus requires multiple seeks. To address these issues, we propose a KV-store MoonKV designed for update-intensive workload, which implements Logical and Vertical Compaction techniques to efficiently and timely merge partial values, thereby minimizing their coexistence in the LSM-tree. Besides, MoonKV introduces an NVM-based Index and Estimate Search to enhance search efficiency, leveraging high-speed NVM. By incorporating the above techniques, MoonKV significantly reduces the number of partial keys required to search when reading the value of a specific key. Finally, our evaluation shows that MoonKV achieves a 1.6$\times$ −3.2$\times$ throughput improvement compared with other KV stores, such as RocksDB, BlobDB, and MatrixKV, under update-intensive workloads.

Wireless Charging Vehicles (WCVs) have been widely explored as a means of enabling continuous operation of sensors that are powered by batteries. However, the energy consumption of WCVs can be inefficient, leading to insufficient energy supply for sensors that are located in challenging-to-access areas. Consequently, there is a need to design an effective charging and energy sharing scheme for sensors to improve the quality of service in this setup. This paper focuses on the Joint optimization of Mobile charging and Energy sharing of sensors (JOIN-ME) problem, which is known to be NP-hard. To address this challenge, we first transform JOIN-ME into a submodular maximization problem with general constraints. Subsequently, we propose the Routing planning, Mobile charging, and Energy sharing for Sensing devices (RMES) algorithm, which has an approximation ratio of 1/8(1-1/e). Finally, we conduct experiments to showcase the superior performance of RMES compared to existing baselines, under varying scales and constraints. Our work on the design of an efficient charging and energy sharing scheme for sensors can significantly improve the reliability and longevity of wireless sensor networks, enabling the deployment of these networks in critical applications such as environmental monitoring, crowd sensing, and security surveillance.

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

The quality of the video stream is key to neural network-based video analytics. However, low-quality video is inevitably collected by existing surveillance systems because of poor quality cameras or over-compressed/pruned video streaming protocols, e.g., as a result of upstream bandwidth limit. To address this issue, existing studies use quality enhancers (e.g., neural super-resolution) to improve the quality of videos (e.g., resolution) and eventually ensure inference accuracy. Nevertheless, directly applying quality enhancers does not work in practice because it will introduce unacceptable latency. In this paper, we present AccDecoder, a novel accelerated decoder for real-time and neural-enhanced video analytics. AccDecoder can select a few frames adaptively via Deep Reinforcement Learning (DRL) to enhance the quality by neural super-resolution and then up-scale the unselected frames that reference them, which leads to 6-21% accuracy improvement. AccDecoder provides efficient inference capability via filtering important frames using DRL for DNN-based inference and reusing the results for the other frames via extracting the reference relationship among frames and blocks, which results in a latency reduction of 20-80% than baselines.

With the rapid development of big data technology, big data systems are more and more used to process SQL query jobs. However, intricate big data system parameters have big effects on the quality of service for big data query performance. Moreover, the types of query jobs and data sizes of data sets are diversified, which have different optimal parameters for best running performance. There exist high complexity and difficulties in tuning the big data system parameters for efficient query job execution. To address this issue, we propose Magpie, an efficient big data query tuning system based on the genetic algorithm with customized pruning strategies. The experimental results show that the proposed approaches can reduce big data query job execution time by 35.5% on average compared with the cuttingedge big data system parameter tuning methods.

Acoustic sensing for heartbeat monitoring has become a prevailing research topic in wireless sensing. Existing acoustic sensing systems have two limitations---limited sensing range, and heartbeat monitoring for a single user only, hindering the large-scale deployment of applications. In this paper, we present DF-Sense, a Dual Forming based multi-user acoustic Sensing system for heartbeat monitoring in home settings. Specifically, we design a novel sensing signal-to-noise ratio (SSNR) enhancement model, namely Dualforming, based on the constructive superposition across multiple subcarriers and microphones, and further build the quantitative relationship between critical factors and SSNR enhancement to optimize sensing performance. To enable Dualforming, we propose a novel MUltiple Subtle SIgnal Classification (MUS2IC) method to identify multiple subjects with subtle motions. We implement DF-Sense using commercial acoustic devices and conduct extensive experiments in a home setting. Results show that DF-Sense achieves high precision measurement of instantaneous heart rate within the range of 10 m, which is sufficient for most daily space requirements, and is able to monitor heartbeat for up to 6 subjects in a 2-D space simultaneously.

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.

Heavy-hitter detection is a fundamental task in network traffic measurement and security. Existing work faces the dilemma of suffering dynamic and imbalanced traffic characteristics or lowering the detection efficiency and flexibility. In this paper, we propose a flexible sketch called SwitchSketch that embraces dynamic and skewed traffic for efficient and accurate heavy-hitter detection. The key idea of SwitchSketch is allowing the sketch to dynamically switch among different modes and take full use of each bit of the memory. We present an encoding-based switching scheme together with a flexible bucket structure to jointly achieve this goal by using a combination of design features, including variable-length cells, shrunk counters, embedded metadata, and switchable modes. We further implement SwitchSketch on the NetFPGA-1G-CML board. Experimental results based on real Internet traces show that SwitchSketch achieves a high Fβ-Score of threshold-t detection (consistently higher than 0.938) and over 99% precision rate of top-k detection under a tight memory size (e.g., 100KB). Besides, it outperforms the state-of-the-art by reducing the ARE by 30.77%\sim99.96%. All related implementations are open-sourced.

Approximate query processing (AQP) is one of the key techniques to cope with big data querying problem on account that it obtains approximate answers efficiently. To address non-trivial sample selection and heavy sampling cost issues in AQP, we propose ShadowAQP, an efficient and accurate approach based on attribute-oriented sample size allocation and data generation. We select samples according to group-by and join attributes, and determine the sample size for each group of unique value combinations to improve query accuracy. We design a conditional variational autoencoder model with automatic table data encoding and model update strategies. To further improve accuracy and efficiency, we propose a set of extensions, including parallel multi-round sampling aggregation, data outlier-aware sampling, and dimension reduction optimization. Evaluation results on diversified datasets show that, compared with SOTA approaches, ShadowAQP achieves 5.8× query speed performance improvement on average (up to 12.8×), while reducing query error by 74% on average (up to 95%) at the same time.

Deep integration of wireless power transmission and mobile edge computing (MEC) promotes wireless powered MEC to become a new research hotspot in the field of Internet of Things. In this paper, we focus on the joint optimization problem of online offloading decision and charging resource allocation for minimizing task accomplishing time in dynamic time-varying wireless channel scenarios. The optimal solution involves addressing a mixed integer programming problem in real time, which is proved to be NP-hard, and imposes nontrivial challenges to design with conventional optimization methods. To efficiently address this problem, we leverage the deep reinforcement learning (DRL) technology to propose an energy-aware online offloading algorithm called EAOO. EAOO algorithm learns empirically the online offloading decision policies via a well-designed DRL framework, and adopts the feasible solution region analysis method to implement the charging resource allocation. We further propose a novel feasible decision vector generation method, and incorporate the crossover and mutation technology to expand the offloading vector search space with the provable feasibility guarantee. Extensive experimental results show that, our EAOO algorithm outperforms existing baseline algorithms, and achieves near-optimal performance with low CPU execution latency, which well satisfies the practical requirements of real-time and efficiency.

This paper is on designing a compact data structure for multi-set membership testing that allows fast set querying. Multi-set membership testing is a fundamental operation for computing systems. Most existing schemes for multi-set membership testing are built upon Bloom filter and fall short in either storage space cost or query speed. To address this issue, we propose Noisy Bloom Filter (NBF), Error Corrected Noisy Bloom Filter (NBF-E), and Data-driven Noisy Bloom Filter (NBF-D) in this paper. We optimize their misclassification and false positive rates by theoretical analysis and present criteria for selection between NBF, NBF-E, and NBF-D. The key novelty of the three schemes is to store set ID information in a compact but noisy way that allows fast recording and querying and use a denoising method for querying. Especially, NBF-E incorporates asymmetric error-correcting coding techniques into NBF, and NBF-D encodes set ID based on their cardinality. To evaluate NBF, NBF-E, and NBF-D in comparison with the prior art, we conducted experiments using real-world network traces. The results show that NBF, NBF-E, and NBF-D significantly advance the state-of-the-art on multi-set membership testing.

Bloom filter is an efficient data structure for filtering negative keys (keys not in a given set) with substantially small space. However, in real-world applications, there widely exist vulnerable negative keys, which will bring high costs if not being properly filtered, especially when positive keys are added/deleted dynamically. Such problem gets more severe when keys within one set are dynamically added or deleted. Recently, there are works focusing on handling such (vulnerable) negative keys by incorporating learning techniques. These learning-based filters fail to work as the learning techniques can hardly handle incremental insertions or deletions. To address the problem, we proposeSeeSawCountingFilter (SSCF), which is innovated with encapsulating the vulnerable negative keys into a unified counter array named seesaw counter array, and dynamically modulating (or varying) the applied hash functions to guard the encapsulated keys from being misidentified. Moreover, we design ada-SSCF to handle the scenarios where the vulnerable negative keys cannot be obtained in advance. We extensively evaluate our SSCF, which shows that SSCF outperforms the cutting-edge filters by$3\times$on averages regarding accuracy while ensuring a low operation latency. All source codes are in (SSCF-authors).

Due to the increasing demand for scalable and interactive data analytics, column stores have become the de-facto choice in many analytical databases. As a common and fundamental operation in column stores, expression evaluation has a remarkable effect on many queries. To speed up expression evaluation, vectorized techniques such as Single-Instruction-Multiple-Data (SIMD) instructions are widely used. However, there are few works concerning dedicated optimizations for SIMD-based expression evaluation for column stores. In this paper, we propose a runtime optimization framework named ROVEC that enables effective optimizations for SIMD-based expression evaluation. The key idea is to optimize logical expression at execution time, by leveraging lightweight compression and fine-grained statistics associated with the compressed data. ROVEC removes unnecessary type casting and finds the tightest type during evaluation, which maximizes the concurrent operands in SIMD instructions. ROVEC can be applied to many expression-evaluation-intensive operators (e.g., table scan and theta join) for different data types (e.g., numeric, time and string). To validate the effectiveness of ROVEC, we integrate it into a columnar database PolarDB-C. Our evaluation results show that ROVEC improves up to 120% (60% on average) throughput of table scan and up to 50% (30% on average) latency of theta join.

Several recent works have studied mobile charging under the “one-to-many” charging pattern where a single charger can charge multiple devices simultaneously. However, most of them focus on path planning and charging time allocation, but overlook the underlying dependence of the charging efficiency on initial deployment positions of chargers. This paper studies the problem ofPlacing directional wIreless chargers withLimited mObiliTy (PILOT), that is, maximize the overall charging utility for a set of static rechargeable devices on a 2D plane by determining deployment positions, stop positions and orientations, and portions of time for all deployed chargers that can move in a limited area after their deployment. To the best of our knowledge, we are the first to study placement of mobile directional chargers under the “one-to-many” pattern. To address PILOT, we propose a$(\frac{1}{2}-\epsilon)$-approximation algorithm. First, we present a method to approximate nonlinear charging power of chargers, and further propose an approach to construct Maximal Covered Set uniform subareas to reduce the infinite continuous search space for stop positions and orientations to a finite discrete one. Second, we present geometrical techniques to further reduce the infinite solution space for candidate deployment positions to a finite one without performance loss, and transform PILOT to a mixed integer nonlinear programming problem. Finally, we propose a linear programming based greedy algorithm to address it. Simulation and experimental results show that our algorithm outperforms six comparison algorithms by$19.74 \% \sim 500.01 \%$.

Wireless rechargeable sensor networks (WRSNs) have become a hot research issue owing to the breakthrough of wireless power transfer (WPT) technology. Previous theoretical schemes are mostly designed for 2-D networks, and few of them are tailored for 3-D scenarios, making them not suitable for wide adoptions in practical applications. In this paper, we address the issue of how to serve a 3-D WRSN with an unmanned aerial vehicle (UAV). Our main concern is to maximize the charged energy for sensors supplied by the UAV, which has energy constraints. We respectively develop a spatial discretization scheme to construct a finite feasible set of charging spots for the UAV in a 3-D environment and a temporal discretization scheme to determine the appropriate charging duration for each charging spot. Then, we reduce the problem into a submodular maximization problem with routing constraints and present a cost-efficient algorithm (CEA) with a provable approximation ratio to solve it. Finally, test-bed experiments are conducted to show the feasibility of our schemes in practical scenarios. Extensive simulations are taken to verify the superior performance of our algorithm in charged energy and robustness. The charged energy of our scheme outperforms other competing methods by at least$18.2\%$.

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.

The multi-hop wireless charging technology can largely extend the charging service range of chargers, thus has promising prospect in sustainable energy replenishment for wireless rechargeable sensor network. This paper proposes a new cost criterion, termed comprehensive cost consisting of energy cost and deployment cost, to measure the actual expenditure of wireless charging. We present a multi-hop wireless charging model and formulate the problem of minimizing the comprehensive cost such that the energy demand of all sensor nodes can be fulfilled by the energy capacitated chargers. We propose a (ln n+1)-approximation algorithm for the optimization problem, where n is the number of sensor nodes. Then, we propose a straightforward cost sharing mechanism, which ensures that no subset of sensor nodes can benefit by breaking away from the current charging tree for any fixed charger position, to realize the paid charging service of multi-hop wireless charging. Furthermore, to keep the magnetic fields of transmitters from the interfering, the conflict avoidance schemes are proposed in both central and distributed situations. Finally, we discuss the distributed scheme for minimizing the comprehensive cost without support of central server. Through extensive simulations, we demonstrate the significant superiority of the proposed algorithms in terms of comprehensive cost.

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.

With the development of 5G technology, mobile edge computing is emerging as an enabling technique to reduce the response latency of network services by deploying cloudlets at 5G base stations to form mobile edge cloud (MEC) networks. Network service providers now shift their services from remote clouds to cloudlets of MEC networks in the proximity of users. However, the permanent placement of network services into an MEC network is not economic due to limited computing and bandwidth resources imposed on its cloudlets. A smart way is to cache frequently demanded services from remote clouds to cloudlets of the MEC network. In this paper, we study the problem of service caching in an MEC network under a service market with multiple network service providers competing for both computation and bandwidth resources in terms of Virtual Machines (VMs) in the MEC network. We first propose an Integer Linear Program (ILP) solution and a randomized rounding algorithm, for the problem without VM sharing among different network service providers. We then devise a distributed and stable game-theoretical mechanism for the problem with VM sharing among network service providers, with the aim to minimize the social cost of all network service providers, through introducing a novel cost sharing model and a coalition formation game. We also analyze the performance guarantee of the proposed mechanism, Strong Price of Anarchy (SPoA). We third consider the cost- and delay-sensitive service caching problem with temporal VM sharing, and propose a mechanism with provable SPoA. We finally evaluate the performance through extensive simulations and a real world test-bed implementation. Experimental results demonstrate that the proposed algorithms outperform existing approaches by achieving at least$40\%$lower social cost via service caching and resource sharing among different network service providers.

Virtualized network functions (VNFs) enable software applications to replace traditional middleboxes, which are more flexible and scalable in the network service provision. This paper focuses on ensuring Service Availability via Failure Elimination (SAFE) using VNF scaling, that is, given the resource requirements of VNF instances, finding an optimal and robust instance consolidation strategy, which can recover from one instance failure quickly. To address the above problem, we present a framework based on rounding and dynamic programming. First, we discretize the range of resource requirements into several sub-ranges, and thus the number of instance types becomes a constant. Second, we further reduce the number of instance types by gathering several small instances into a bigger one. Third, we propose an algorithm built on dynamic programming to solve the instance consolidation problem with a limited number of instance types. Finally, we set up a testbed to profile the functional relationship between the resource and the throughput for different types of VNFs, and conduct simulations to validate our theoretical results according to profiling results. The simulation results show that our algorithm outperforms the standby deployment model by 27.33% on average in terms of the number of servers required. Furthermore, SAFE has marginal overheads, around 7.22%, compared to the instance consolidation strategy without VNF backup consideration.

Wireless rechargeable sensor networks have become a hot research issue as it can overcome the limited energy bottleneck of wireless sensor networks owing to the recent breakthrough of wireless power transfer technology. Though network lifetime is prolonged and sensor nodes can sustain immortally, the issue of network robustness is overlooked, yielding most theoretical work unsuitable for practical applications when confronting with unpredictable packet loss. In this paper, we address the network robustness issue by maximizing the charging utility in a risk-averse view. First, we build a risk-averse model based on the concept of CVaR (Conditional Value at Risk), which trades-off charging utility and risk aversion for quantifying robustness. Then, we propose a spatial discretization scheme to construct a charging route for mobile charger, which can reduce computational overhead. Afterwards, a path optimization scheme is designed to further improve the charging utility. We convert the original problem into the submodular function maximization problem and propose a method with a performance guarantee while maximizing the system robustness. Finally, testbed experiments and simulations are conducted, and the results demonstrate that our schemes outperform comparison algorithms by at least 22.4% in effective energy in the presence of risks to guarantee system robustness.

The multi-hop wireless charging technology has attracted a lot of attention, as it largely extends the charging range of chargers. Different from the existing work with single cost optimization, the objective of this article is to optimize the comprehensive cost, which is the combination of energy cost and deployment cost. We decompose the target problem into two sub-problems. The first sub-problem aims to minimize the deployment cost with energy capacity constraints. The proposed algorithm follows the greedy strategy, where the subset of sensor nodes for any charger is determined by finding the capacitated minimum spanning tree. The second sub-problem, which aims to maximize the reduction of comprehensive cost by adding chargers to the solution of the first sub-problem, is proved to be an unconstrained submodular set function maximization problem and can be solved by a 1/2-approximation randomized linear time algorithm for its equivalent problem. Through extensive simulations, we demonstrate that the proposed solution can reduce the comprehensive cost by 57.55% comparing with the benchmark algorithms.

Nowdays, it is prevalent to train deep learning models in cloud-native platforms that actively leverage containerization and orchestration technologies for high elasticity, low and flexible operation cost, and many other benefits. However, it also faces new challenges and our work is focusing on those related to I/O throughput for training, including complex data access, lack of matching dynamic I/O requirement, and inefficient I/O resource scheduling across different jobs. We proposeFluid, a cloud-native platform that provides DL training jobs with high-level data abstraction calledFluid Datasetto access training data from heterogeneous sources with elastic data acceleration. In addition, it comes with an on-the-fly cache system autoscaler that can match the online training speed and increase the number of cache replicas adaptively to alleviate I/O bottlenecks. To improve the overall performance of multiple DL jobs, Fluid co-orchestrate the data cache and DL jobs by arranging job scheduling in an appropriate order and can also schedule data cache and DL jobs on the same node to realize cache affinity. Experimental results show significant performance improvement of each individual DL job which uses dynamic computing resources with Fluid. For scheduling multiple DL jobs with same datasets, Fluid achieves around 2x performance speedup when integrated with existing widely-used and cutting-edge scheduling solutions through the appropriate job scheduling order. Besides, the cache affinity scheduling policy also improves job execution performance significantly. Fluid is now an open source project hosted by Cloud Native Computing Foundation (CNCF) with many production adopters.

Wireless Rechargeable Sensor Networks (WRSNs) have become an important research issue as it can overcome the energy bottleneck problem of wireless sensor networks. However, inaccurate discretization methods and imprecise charging models yield a huge gap between theoretical results and practical applications, making it difficult for wide adoptions. In this paper, we focus on designing a precise charging method for maximizing charging utility when line-of-sight (LOS) and none-line-of-sight (NLOS) charging cases exist in complicated environments. First, we design discretization methods for charging area and charging orientation for precisely constructing the charging model. Then, we develop a novel electromagnetic wave reflection model to describe the signal propagation model in the presence of obstacles. We formalize the mobile charging problem into a submodular function maximization problem which can be solved by a proposed algorithm with an approximation guarantee. Finally, extensive experiments and simulations demonstrate that our schemes outperform comparison algorithms by 31.45% on average in charging utility in complicated environments.

Nowdays, it is prevalent to train deep learning (DL) models in cloud-native platforms that actively leverage containerization and orchestration technologies for high elasticity, low and flexible operation cost, and many other benefits. However, it also faces new challenges and our work is focusing on those related to I/O throughput for training, including complex data access with complicated performance tuning, lack of cache capacity with specialized hardware to match its high and dynamic I/O requirement, and inefficient I/O resource sharing across different training jobs. We propose Fluid, a cloud-native platform that provides DL training jobs with a data abstraction called Fluid Dataset to access training data from heterogeneous sources in a unified manner with transparent and elastic data acceleration powered by auto-tuned cache runtimes. In addition, it comes with an on-the-fly cache system autoscaler that can intelligently scale up and down the cache capacity to match the online training speed of each individual DL job. To improve the overall performance of multiple DL jobs, Fluid can co-orchestrate the data cache and DL jobs by arranging job scheduling in an appropriate order. Our experimental results show significant performance improvement of each individual DL job which uses dynamic computing resources with Fluid. In addition, for scheduling multiple DL jobs with same datasets, Fluid gives around 2x performance speedup when integrated with existing widely-used and cutting-edge scheduling solutions. Fluid is now an open source project hosted by Cloud Native Computing Foundation (CNCF) with adopters in production including Alibaba Cloud, Tencent Cloud, Weibo.com, China Telecom, etc.

The approximate membership query (AMQ) data structure is a kind of space-efficient probabilistic data structure. It can approximately indicate whether an element exists in a set. The AMQ data structure has been widely used in database indexing, network security, IoT applications, etc. Resizing is an extensively utilized operation of the AMQ data structure, but it can lead to system performance degradation. We summarize two main problems that lead to such degradation. Specifically, one of them is that the resizing operation can block other operations, while the other is that the performance of AMQ structures will deteriorate after multiple resizing operations. However, existing related work cannot alleviate both of them. Therefore, we propose a novel AMQ data structure called bamboo filter, which can alleviate the two problems simultaneously. Bamboo filters can insert, search and delete an element in constant time. Moreover, bamboo filters can dynamically resize in a fine-grained way according to the number of contained elements. Experimental results show that bamboo filters significantly outperform state-of-the-art resizable AMQ data structures in insertion, lookup, and deletion operations. For example, bamboo filters achieve$\mathbf{2.46}\times$lookup throughput of the dynamic cuckoo filter, on average.

Mobile edge computing (MEC) is emerging as a novel computing paradigm that pushes network resources (such as computation and storage resources) away from the centralized data center to distributed edge servers. By hiring various resources of nearby edge servers, the MEC provides high-bandwidth and low-latency network services for mobile users. As numerous mobile users may compete for limited edge servers’ resources, to improve the resource utilization of the MEC system, it is very critical to investigate an effective user allocation policy. Previous studies mainly focus on investigating offline user allocation policies. However, mobile users may arrive online, and the MEC should be able to allocate these users online too. In a real-world MEC environment, online allocation decisions should not be made entirely in the dark. The historical user requests which may contain powerful hints about future user requests, can be adopted to assist in making allocation decisions. In this paper, we take the historical data into account and study the history-assisted online user allocation strategy. Specifically, we formulate the user allocation problem with a comprehensive model and show its hardness. Then, we present an online algorithm named HOUA to allocate mobile users according to both the online arrived user requests and the historical user requests. The competitive ratio of HOUA is proved. To further verify the effectiveness of HOUA, we conduct experiments on a widely-used real-world dataset. We show that HOUA can allocate more mobile users and achieve high resource rental revenue compared with the other approaches.

Bi-objective online stochastic bipartite matching can capture a wide range of real-world problems such as online ride-hailing, crowdsourcing markets, and internet adverting, where the vertices in the left side are known in advance and that in the right side arrive from a known identical independent distribution (KIID) in an online manner. Mutual interest and limited attention-span are two common conditions and can be modeled as the edge existence probability and two-sided limited patience. Existing works fail to take them into bi-objective online optimization. This paper establishes a unified model for bi-objective online stochastic bipartite matching that can provide a general tradeoff among the matched edges (OBJ-1) and vertices (OBJ-2). We formulate two linear programs (LP) and accordingly design four LP-based parameterized online algorithms to tradeoff OBJ-1 and OBJ-2, with the best competitive ratio of (0.3528α, 0.3528β), where α, β are two positive input parameters and α + β = 1. Our hardness analysis proves that any non-adaptive algorithm cannot achieve (δ1, δ2)-competitive such that ${\delta _1} + {\delta _2} > 1 - \frac{1}{e}$. Trace-driven experiments show that our algorithms can always achieve better performance and provide a flexible tradeoff.

The limitation on the flight range motivates a hybrid monitoring system, wherein trucks carrying drones drive to pre-planned positions and then free drones for task execution. While the flight range limitation is mitigated, it is challenging to determine the destination of trucks and drones and set airborne cameras. This paper optimizes the joint Deployment of trUcks and dronEs for objecT monitoring (DUET), that is, deploy a set of trucks where each truck carries drones, and each drone is equipped with a varifocal camera such that the overall monitoring utility for target objects is maximized. To tackle the DUET problem, we first model the hybrid system and monitoring utility; then, discretize the solution space of DUET with performance bound. In this way, the problem is transformed into a two-level combinatorial optimization problem satisfying submodularity. To address it, a two-level greedy algorithm with $\frac{{{{(e - 1)}^2}}}{{e(2e - 1)}} \cdot (1 - \varepsilon )$ approximation ratio is proposed to select deployment strategies. After the strategy selection, an optimal method is devised to carefully adjust the strategy for energy saving and communication improvement without loss of monitoring utility. Both simulations and field experiments are conducted to evaluate the proposed framework, which outperforms baseline algorithms on monitoring utility by at least 28.4% and 40%, respectively.

Wireless Sensor Networks (WSNs) and Cloud Computing have received tremendous attention from both academia and industry. Sensor-Cloud is the product of combining WSNs and Cloud Computing together, which integrates edge computing and artificial intelligence technologies recently. This workshop provides a forum for academic researchers and industry practitioners to exchange the most recent progress in methods and applications in sensor-cloud systems.

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%.

This paper presents a Long Range (LoRa) physical-layer data aggregation system (LoRaPDA) that aggregates data (e.g., sum, average) directly in the physical layer. In particular, after coordinating a few nodes to transmit their data simultaneously, the gateway leverages a new multi-packet reception (MPR) approach to compute aggregate data from the asynchronous superimposed signal. Different from traditional MPR approaches that are designed for the uncoordinated collision decoding scenario, our MPR approach allows simultaneous transmissions with small packet arrival time offsets, and addresses the new co-located peak problem through the following components: 1) an improved channel and offset estimation algorithm that enables accurate phase tracking in each symbol; 2) a new symbol demodulation algorithm that finds the maximum likelihood sequence of nodes' data; and 3) a soft-decision packet decoding algorithm that keeps the likelihoods of several sequences to improve decoding performance. Trace-driven simulation results show that the symbol demodulation algorithm outperforms a state-of-the-art MPR decoder by 5.4× in terms of physical-layer throughput, and the soft decoder is more robust to unavoidable adverse phase misalignment and estimation error in practice. Moreover, LoRaPDA outperforms a state-of-the-art MPR scheme by at least 2.1× for all SNRs in terms of network throughput, demonstrating quick and reliable data aggregation.

Bloom filter is an efficient data structure for filtering negative keys (keys not in a given set) with substantially small space. However, in real-world applications, there widely exist vulnerable negative keys, which will bring high costs if not being properly filtered, especially when positive keys are added/deleted dynamically. To address the problem, we propose SeeSaw Counting Filter (SSCF), which is innovated with encapsulating the vulnerable negative keys into a unified counter array named seesaw counter array, and dynamically modulating (or varying) the applied hash functions to guard the encapsulated keys from being misidentified. Moreover, we propose ada-SSCF to handle the scenarios where the vulnerable negative keys cannot be obtained in advance. We extensively evaluate our SSCF, which shows that SSCF outperforms the cutting-edge filters by 3 × on averages regarding accuracy while ensuring a low operation latency. All source codes are in [2].

Finding special items, like heavy hitters, top-k, and persistent items, has always been a hot issue in data stream processing for web analysis. While data streams nowadays are usually high-dimensional, most prior works focus on special items according to a certain primary dimension and yield little insight into the correlations between dimensions. Therefore, we propose to find special quadratic elements to reveal close correlations. Based on the items mentioned above, we extend our problem to three applications related to heavy hitters, top-k, and persistent items, and design a generic framework DUET to process them. Besides, we analyze the error bound of our algorithm and conduct extensive experiments on four data sets. Our experimental results show that DUET can achieve 3.5 times higher throughput and three orders of magnitude lower average relative error compared with cutting-edge algorithms.

Mobile edge computing (MEC) is an enabling technology for low-latency AI applications, by caching AI services originally deployed in remote data centers to 5G base stations in network edge. Due to limited computing resource of 5G base stations, not all services can be cached in base stations to meet the resource demands of user requests. Also, if the workload of a 5G base station reaches to its resource capacity, the energy consumption of the base station will be pushed up exponentially. To reduce the energy consumption and overcome resource limitations on base stations, an alternative is to allow the base stations to collaborate with each other to admit user requests. In this paper, we investigate the problem of collaborative service caching and request offloading between a 5G-enabled MEC and remote data centers, while meeting the quality of service (QoS) requirements of users, and resource capacities on base stations that are operated by multiple selfish network service providers. We aim to maximize the total payoff of all base stations. To this end, we first propose a two-stage optimization framework: In the first stage, we develop a mechanism that adopts a best-reply rule for dynamically distributed coalition formation. In the second stage, we propose a near-optimal payoff allocation method by devising a randomized algorithm with a provable approximation ratio. We then evaluate the performance of the proposed optimization framework by extensive experimental simulations. Simulation results show that the proposed framework outperforms its counterparts by achieving at least 30% higher payoff and 20% lower energy consumption of base stations.

Vehicular Content Centric Network (VCCN) has been proposed to address the issues of user mobility and sporadic connectivity in Vehicular Ad hoc Network (VANET). The in-network caching of VCCN can indeed improve the performance of content distribution in terms of cache hit and delivery latency by making each node store frequently accessed data. However, data caching unfortunately suffers from Cache Pollution Attack (CPA) that sends out fabricated requests to pollute the data cache. To prevent the degradation of network performance caused by such an attack, we propose a detection and defense scheme for CPA by adopting game theory. We model the attack scenario into a non-cooperative game model. First, we prove the non-existence of pure strategy Nash Equilibrium (NE) in the attacker and defender game, and propose a normal form game model with complete information and an extensive Bayesian form game model with incomplete information. Under the guidance of NE, we propose a punishment strategy to prevent the conspiracy attack and make the attackers behave normally. Moreover, we propose a cooperative detection scheme to give the Road Side Unit (RSU) the final decision on CPA based on the direct and indirect suspicious lists which are generated by each node according to the observed traffic pattern. Simulation evaluations demonstrate that our scheme outperforms state-of-the-art schemes in terms of cache hit, detecting ratio, and cache accuracy for detecting and defending CPA.

One critical issue for wireless power transfer is to avoid human health impairments caused by electromagnetic radiation (EMR) exposure. The existing studies mainly focus on scheduling wireless chargers so that (expected) EMR at any point in the area does not exceed a threshold$R_t$. Nevertheless, they overlook the EMR jitter that leads to exceeding of$R_t$even if the expected EMR is no more than$R_t$. This paper studies the fundamental problem ofRObustlySafEcharging for wireless power transfer (ROSE), that is, scheduling the power of chargers so that the charging utility for all rechargeable devices is maximized while the probability that EMR anywhere does not exceed$R_t$is no less than a given confidence. We first build our empirical probabilistic charging model and EMR model. Then, we present EMR approximation and area discretization techniques to formulate ROSE into a Second-Order Cone Program. After that, we propose the first redundant second-order cone constraints reduction algorithm to reduce the computational cost, and therefore obtain a$(1-\epsilon)$-approximation centralized algorithm. Further, we propose a$(1-\epsilon)$-approximation fully distributed algorithm scalable with network size for ROSE. We conduct both simulation and field experiments, and the results show that our algorithms can outperform comparison algorithms by 480.19 percent.

With the rising of AR/VR technology and miniaturization of mobile devices, gesture recognition is becoming increasingly popular in the research area of human-computer interaction. Some pioneer ultrasound-based gesture recognition systems have been proposed. However, they mostly rely on low-resolution Doppler Effect, with the focus on whole hand motion and fail to deal with minor finger motions. This paper is to present UltraGesture, an ultrasonic finger motion perception and recognition system based on Channel Impulse Response (CIR). CIR measurements can provide with 7 mm resolution, which is sufficient for minor finger motion recognition. UltraGesture encapsulates CIR measurements into image, and builds a Convolutional Neural Network model to classify these images into different categories corresponding to distinct gestures. Furthermore, we use a sliding-window based method to improve accuracy and reduce response latency. UltraGesture can run on the already existed commercial speakers and microphones on most mobile devices without any hardware modification. Our results demonstrate that UltraGesture can achieve an average accuracy ofgreater than 99 percent for 12 gestures including finger click and rotation.

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.

This paper considers the fundamental problem of deployment of Unmanned AerialVehIcles for aniSotropic monItoringTasks (VISIT), that is, given a set of objects with determined coordinates and directions in 2D area, deploy a fixed number of UAVs by adjusting their coordinates and orientations such that the overall monitoring utility for all objects is maximized. We develop a theoretical framework to address VISIT problem. First, we establish monitoring model whose quality of monitoring (QoM is anisotropic with monitoring angle and varying with various monitoring distance. To the best of our knowledge, we are the first considering the anisotropy of monitoring angle. Then, we propose a framework consisting of area discretization and Monitoring Dominating Set (MDS) extraction to reduce the infinite solution space of VISIT to a limited one with performance bound. Finally, we model the reformulated problem as maximizing a monotone submodular function subject to a matroid constraint, and present a greedy algorithm with$1-1/e-\epsilon$approximation ratio. We conduct both simulations and field experiments to evaluate our framework, and the results show that our algorithm outperforms comparison algorithms by at least 41.3 percent.

Network update enables Software-Defined Networks (SDNs) to optimize the data plane performance. The single update focuses on processing one update event at a time,i.e., updating a set of flows from their initial routes to target routes, but it fails to handle continuously arriving update events in time incurred by high-frequency network changes. On the contrary, the continuous update proposed in “Update Algebra” can handle multiple update events concurrently and respond to the network condition changes at all times. However, “Update Algebra” only guarantees the blackhole-free and loop-free update. The congestion-free property cannot be respected. In this paper, we propose Coeus to achieve the continuous update while maintaining consistency,i.e., ensuring the blackhole-free, loop-free, and congestion-free properties simultaneously. Firstly, we establish the continuous update model based on the update operations in update events. With the update model, we dynamically reconstruct the operation dependency graph (ODG) to capture the relationship between update operations and link utilization variations. Then, we develop a composition algorithm to eliminate redundant operations in update events. To further speed up the update procedure, we present a partition algorithm to split the operation nodes of the ODG into a series of suboperation nodes that can be executed independently. The partition algorithm is proven to be optimal. Finally, extensive evaluations show that Coeus can improve the update speed by at least 179% and reduce redundant operations by at least 52% compared with state-of-the-art approaches when the arrival rate of update events equals three times per second.

As an epoch-making technology, wireless power transfer incredibly achieves energy transmission wirelessly, enabling reliable energy supplement for Wireless Rechargeable Sensor Networks (WRSNs). Existing methods mainly concentrate on performance improvement theoretically, neglecting the fact that most Commercial Off-The-Shelf (COTS) rechargeable sensors (e.g., WISP and Powercast) are not allowed to conduct sensing and energy harvesting tasks simultaneously, termedcharging exclusivity. Therefore, their schemes are not feasible for practical applications. In this paper, we focus on the charging exclusivity issue in stochastic events monitoring while improving network performance. In specific, we pay close attention to trading off charging and sensing tasks and formulate a combinatorial optimization problem with routing constraints. We introduce novel discretization techniques and investigate the routing problem to reformulate the original problem into maximization of a submodular function. With a slightly relaxed budget, the output of our proposed algorithm is better than$(1-1/e)/2$of the optimal solution to the original problem with a smaller charging radius$(1-\xi)D_{c}$. Through extensive simulations, numerical results show that in terms of charging utility, our algorithm outperforms baseline algorithms by 21.3% on average. Moreover, we conduct test-bed experiments to demonstrate the feasibility of our scheme in real scenarios.

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.

Deep learning (DL) is becoming increasingly popular in many domains, including computer vision, speech recognition, self-driving automobiles, etc. GPU can train DL models efficiently but is expensive, which motivates users to share GPU resource to reduce money costs in practice. To ensure efficient sharing among multiple users, it is necessary to develop efficient GPU resource management and scheduling solutions. However, existing ones have several shortcomings. First, they require the users to specify the job resource requirement which is usually quite inaccurate and leads to cluster resource underutilization. Second, when scheduling DL jobs, they rarely take the cluster network characteristics into consideration, resulting in low job execution performance. To overcome the above issues, we propose Liquid, an efficient GPU resource management platform for DL jobs with intelligent resource requirement estimation and scheduling. First, we propose a regression model based method for job resource requirement estimation to avoid users over-allocating computing resources. Second, we propose intelligent cluster network-efficient scheduling methods in both immediate and batch modes based on the above resource requirement estimation techniques. Third, we further propose three system-level optimizations, including pre-scheduling data transmission, fine-grained GPU sharing, and event-driven communication. Experimental results show that our Liquid can accelerate the job execution speed by 18% on average and shorten the average job completion time (JCT) by 21% compared with cutting-edge solutions. Moreover, the proposed optimization methods are effective in various scenarios.

Mobile Edge Caching (MEC) can cache content at the edge of the network to reduce the delay and overhead of content transmission, which has become an effective method to solve the explosive growth of network traffic. To make good use of the limited resources in edge devices, many contents caching strategies use various methods to predict the popularity of content. However, caches get close to the edge of the network can lead to the rapid increase of caches' number and the user's requests are dispersed into a large number of caches, which leads to the popularity distribution of contents in edge caches is quite different and the number of first miss requests (the corresponding content is requested for the first time and is not in the cache) in edge caches becoming an essential factor affecting the cache hit rate. This paper first demonstrates the significant impact of the first miss requests through dataset analysis and establishes a mathematical model for the first miss problem in the edge cache. Then we analyze the similarity of requests received by caches and propose a proactive push algorithm based on similarity to improve the hit rate of edge caches. Through the trace-driven simulation experiment, we verify that the methods proposed in this paper can significantly improve the caches' hit rate.

Wireless Power Transmission (WPT) has been widely used to replenish energy for Wireless Rechargeable Sensor Networks. However, the charging service model, which is of the essence to commercial WPT, has not emerged so far. In this paper, we present a wireless charging service model from the perspective of cooperative charging economics, and formulate the Cooperative Charging Scheduling (CCS) problem for joint optimization of rechargeable devices' charging cost and moving cost. We first propose two intragroup cost sharing schemes to sustain the cooperation among devices. Then, the approximation algorithm CCSA of the CCS problem is proposed based on greedy approach and submodular function minimization. Furthermore, we model the large-scale CCS problem as a coalition formation game and present a game theoretic algorithm CCSGA. We show that CCSGA finally converges to a pure Nash Equilibrium. We conduct simulations, and field experiments on a testbed consisting of 5 chargers and 8 rechargeable sensor nodes. The results show that the average comprehensive cost of CCSA is 27.3% lower than the noncooperation algorithm and is only 7.3% higher than the optimal solution on average. In field experiments, CCSA outperforms the noncooperation algorithm by 42.9% in terms of comprehensive cost on average. Moreover, CCSGA is much faster than the approximation algorithm and is more suitable for large-scale cooperative charging scheduling.

Augmented Reality (AR) has various practical applications in healthcare, education, and entertainment. To provide a fully interactive and immersive experience, AR applications require extremely high responsiveness and ultra-low processing latency. Mobile edge computing (MEC) has shown great potential in meeting such stringent requirements and demands of AR applications by implementing AR requests in edge servers within the close proximity of these applications. In this paper, we investigate the problem of reward maximization for AR applications with uncertain demands in an MEC network, such that the reward of provisioning services for AR applications is maximized and the responsiveness of AR applications is enhanced, subject to both network resource capacity. We devise an exact solution for the problem if the problem size is small, otherwise we develop an efficient approximation algorithm with a provable approximation ratio for the problem. We also devise an online learning algorithm with a bounded regret for the dynamic reward maximization problem without the knowledge of the future arrivals of AR requests, by adopting the technique of Multi-Armed Bandits (MAB). We evaluate the performance of the proposed algorithms through simulations. Experimental results show that the proposed algorithms outperform existing studies by 17 % higher reward.

Bloom filter is a compact memory-efficient probabilistic data structure supporting membership testing, i.e., to check whether an element is in a given set. However, as Bloom filter maps each element with uniformly random hash functions, few flexibilities are provided even if the information of negative keys (elements are not in the set) are available. The problem gets worse when the misidentification of negative keys brings different costs. To address the above problems, we propose a new Hash Adaptive Bloom Filter (HABF) that supports the customization of hash functions for keys. The key idea of HABF is to customize the hash functions for positive keys (elements are in the set) to avoid negative keys with high cost, and pack customized hash functions into a lightweight data structure named HashExpressor. Then, given an element at query time, HABF follows a two-round pattern to check whether the element is in the set. Further, we theoretically analyze the performance of HABF and bound the expected false positive rate. We conduct extensive experiments on representative datasets, and the results show that HABF outperforms the standard Bloom filter and its cutting-edge variants on the whole in terms of accuracy, construction time, query time, and memory space consumption (Note that source codes are available in [1]).

The rapid popularization of wireless power transfer (WPT) technology promotes the wide adoption of wireless rechargeable sensor networks (WRSNs). Traditional methods only focus on how to optimize network performance, and most of them overlook the energy waste issue induced by WPT. In this paper, we explore the potentials of recycling wasted energy when using WPT by means of freeloading. Specifically, with a slight modification on hardware, we expand the functionality of the mobile chargers (MCs), enabling them to harvest and recycle the WPT-induced wasted energy in the air to serve more sensors, which promotes energy efficiency. We model the problem, termed MEFree, as maximizing network energy efficiency by utilizing a limited number of freeloading MCs and scheduling their freeloading behaviors. Through jointly scheduling freeloading and charging tasks, the proposed scheme is able to solve the problem with a (1 − 1/e)/2 approximation ratio with a slightly relaxed budget. Extensive simulations are conducted and corresponding numerical results show that our proposed scheme significantly improves network energy efficiency by at least 18.8% and outperforms baseline algorithms by 19.1% on average in various aspects. Our test-bed experiments further demonstrate the practicability of our scheme in actual scenes.

Edge computing provides task offloading services to extend the computational capacity of mobile users and reduce task latency. The deadline-awareness offloading algorithm plays a key role in guaranteeing the quality of service (QoS) requirement. Prior studies mainly focus on tasks with strict deadlines. However, some tasks may not always have to be finished before hard deadlines, e.g., multimedia tasks. Tasks with soft deadlines can miss their primary deadlines, but not by too much. This has not been properly considered by existing offloading approaches. In this paper, we propose CONFECT to offload tasks with mixed deadlines. We formulate the problem and prove its hardness. Then, we propose two online algorithms with proven competitive ratios to solve the problem collectively, including an algorithm that assigns tasks to edge servers and an algorithm that adjusts the task execution order on each server. Extensive experiments show that CONFECT outperforms five baseline algorithms.

State-of-the-art inter-datacenter WANs rely on centralized traffic engineering (TE) to improve the network performance, where TE computation is a periodical procedure and timely performs routing configurations (i.e., enforces TE polices via add, remove and modify forwarding rules) in response to the changing network conditions. The TE computation determines the routing configurations corresponding to the current network conditions and the network update operations change the routing configurations from last TE to current TE solution. Existing works take centralized TE computation and network update as two individual optimization procedures, which inevitably leads to suboptimal solution in the long run. In this paper we initiate the study of online joint optimization on TE computation and network update with the objective of minimizing the sum of TE cost and network update cost. We formulate this problem as an optimization program and propose a set of provable online algorithms with rigorous competitive and regret analysis. Trace-driven simulations on two empirical topologies demonstrate that our algorithms can significantly decrease the total cost.

The breakthrough of Wireless Power Transfer (WPT) technique provides a promising paradigm to tackle the energy limitation problem for end-devices when replenishing energy wirelessly without the need of replacing battery. Existing works seldom consider the mobility of rechargeable devices like miniature sensors on-body or implanted medical devices which may induce great gap between practical energy supply and demand. In this paper, we study the novel issue of Charging on the Move (CM) to optimize the scheduling of transmitting power of static chargers for mobile devices. Unfortunately, solving this problem is non-trivial, because it involves nonlinearity due to time-varying distances caused by movement. Besides, charging scheduling with tunable power level is a variant of budgeted maximum coverage problem, which is NP-hard. To address CM, we approximate the variational charging power as piecewise constant power, and divide the movement trajectories with approximated charging utility. Then, we first consider our problem with fixed power level, where each charger can be scheduled off or on at a fixed power level. We prove the submodularity of the objective function and design a .. approximation algorithm. On this basis, we further bound the performance loss during the problem reformulation, and finally propose a $\frac{{1 - 1/e}}{{2\left( {1 + \varepsilon } \right)T}}$ approximation algorithm for tunable scheduling strategy, where T is the maximum power level. Extensive simulations and trace-driven evaluations 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.

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.

Although the logically-centralized perspective is offered in Software-Defined Networking (SDN), the data plane is still distributed. Update commands sent by the centralized controller are executed asynchronously and independently in each switch. The timed SDN enables synchronous and coordinated update operations as each update command can be triggered by a pre-defined timestamp. Prior work on timed update mainly focuses on producing a congestion-free update sequence, whereas finding a congestion-free timed update sequence may prolong the update time. Even worse, such an update order may not exist. In this paper, we propose Chronus+, a novel timed update system that utilizes the switch buffer to shorten the update time while minimizing the switch buffer during updates. First, we formulate the Minimum Switch Buffer Problem (MSBP) as an integer linear programming and show its hardness. Then, we propose a set of efficient algorithms to solve the problem in polynomial time. Extensive evaluations in Mininet and large-scale simulations show that Chronus+can reduce the update time by at least 17% and the switch buffer size by at least 27% compared with state-of-the-art approaches.

The new mobile edge computing (MEC) paradigm fundamentally changes the data caching technique by allowing data to be cached on edge servers attached to base stations within hundreds of meters from users. It provides a bounded latency guarantee for latency-sensitive applications, e.g., interactive AR/VR applications, online gaming, etc. However, in the highly distributed MEC environment, cache data is subject to corruption and their integrity must be ensured. Existing centralized data integrity assurance schemes are rendered obsolete by the unique characteristics of MEC, i.e., unlike cloud servers, edge servers have only limited computing and storage resources and they are deployed massively and distributed geographically. Thus, it is a new and significant challenge to ensure cache data integrity over tremendous geographically-distributed resource-constrained edge servers. This paper proposes the CooperEDI scheme to guarantee the edge data integrity in a distributed manner. CooperEDI employs a distributed consensus mechanism to form a self-management edge caching system. In the system, edge servers cooperatively ensure the integrity of cached replicas and repair corrupted ones. We experimentally evaluate its performance against three representative schemes. The results demonstrate that CooperEDI can effectively and efficiently ensure cache data integrity in the MEC environment.

This paper studies the problem of cHarging tAskScheduling for direcTional wireless chargEr networks (HASTE), i.e., given a set of rotatable directional wireless chargers on a 2D area and a series of offline (online) charging tasks, scheduling the orientations of all the chargers with time in a centralized offline (distributed online) fashion to maximize the overall charging utility for all the tasks. We prove that HASTE is NP-hard. Then, we prove that a relaxed version of HASTE falls within the realm of maximizing a submodular function subject to a partition matroid constraint, and propose a centralized offline algorithm that achieves$(1-\rho)(1-\frac{1}{e})$approximation ratio to address HASTE where$\rho$is the switching delay of chargers. Further, we propose a distributed online algorithm and prove it achieves$\frac{1}{2}(1-\rho)(1-\frac{1}{e})$competitive ratio. We conduct simulations and field experiments on a testbed consisting of eight off-the-shelf power transmitters and 8 rechargeable sensor nodes. The results show that our distributed online algorithm achieves 92.97 percent of the optimal charging utility, and outperforms the comparison algorithms by up to 15.28 percent in terms of charging utility.

Gesture tracking is a basic Human-Computer Interaction mechanism to control devices, such as IoT and VR/AR devices. However, prior OFDM signal based systems focus on gesture recognition and provide results with insufficient accuracy, and thus, cannot be applied for high-precision gesture tracking. In this paper, we propose a CSI based device-free gesture tracking system, called WiTrace, which leverages the CSI values extracted from OFDM signals to enable accurate gesture tracking. For 1D tracking, WiTrace derives the phase of the signals reflected by the hand from the composite signals, and measures the phase changes to obtain the movement distance. For 2D tracking, WiTrace proposes the first CSI based scheme to accurately estimate the initial position, and adopts the Kalman Filter based on continuous Wiener process acceleration model to further filter out tracking noise. Our results show that WiTrace achieves an average accuracy of 6.23 cm for initial position estimation and achieves cm-level accuracy with average tracking errors of 1.46 cm and 2.09 cm for 1D tracking and 2D tracking, respectively.

In this article, we first study the problem of Connected wIReless Charger pLacEment (CIRCLE). That is, given a fixed number of directional wireless chargers and candidate positions, determining the placement position and orientation angle for each charger under connectivity constraint for wireless chargers such that the overall charging utility is maximized. To address CIRCLE problem, we first consider a relaxed version of CIRCLE (CIRCLE-R for short). We prove that CIRCLE-R falls into the realm of maximizing a submodular set function subject to a connectivity constraint, and propose an algorithm whose approximation ratio is at least 1.5 times better than that of the state-of-the-art algorithm. Next, we reduce the solution space for CIRCLE from infinite to finite, and propose an algorithm with a constant approximation ratio to address CIRCLE. Besides, we consider a variant of CIRCLE, CIRCLE-NB, and propose an approximation algorithm to address it. We conduct both simulation experiments and field experiments to verify our theoretical findings. The results show that our algorithm can outperform comparison algorithms by 83.35 percent.

Wireless Power Transfer has become a commercially viable technology to charge devices because of the convenience of no power wiring and the reliability of continuous power supply. This paper concerns the fundamental issue of wireless charger placement with electromagnetic radiation (EMR) safety. Although there are a few wireless charging schemes consider EMR safety, none of them addresses the charger placement issue. In this paper, we propose PESA, a wireless charger Placement scheme that guarantees EMR SAfety for every location on the plane. First, we discretize the whole charging area and formulate the problem into the Multidimensional 0/1 Knapsack (MDK) problem. Second, we propose a fast approximation algorithm to the MDK problem. Third, we propose a near optimal scheme to improve speed by double partitioning the area. We prove that the output of our algorithm is better than $(1-\epsilon)$ of the optimal solution to PESA with a smaller EMR threshold $(1-\epsilon /2)R_{t}$ and a larger EMR coverage radius $(1+\epsilon /2)D$ . We conducted both simulations and field experiments to evaluate the performance of our scheme. Our experimental results show that in terms of charging utility, our algorithm outperforms the comparison algorithms.

As a more energy-efficient WPT technology, directional WPT is applied to supply energy for wireless rechargeable sensor networks (WRSNs). Conventional methods that ignore anisotropic energy receiving property of rechargeable sensors cause a waste of energy. To address this issue, in this paper, we focus on minimizing the charging delay with a directional charging scheme. At first, we introduce linear constraints to improve an energy transfer model, which is verified to be practical by experiments. Then, we concern a Minimal chArging Delay with Single charger (S-MAD) problem to promote efficiency, followed by an Optimal Direction Charge with Single charger (S-ODC) solution. Through discretizing charging power and angle, we bound the performance gap of the solution to the optimal one with$\text{a}^{^{^{^{}}}}\,\,\frac {1}{1-\epsilon ^{2}}$approximation ratio, where$\epsilon $is the error threshold of discretization. After that, we extend the original S-MAD problem into the large scale WRSN with multiple chargers (i.e., M-MAD) and solve it by proposing M-ODC (i.e., Optimal Direction Charge with Multiple chargers (M-ODC)). Theoretical analyses are presented to exploit the feature of the proposed schemes. Finally, we demonstrate that our methods outperform the baseline methods by an average of 34.2% through simulations and test-bed experiments.

In this paper, we consider the problem of designing a novel ATTack scheme under charger cApture attaCK(ATTACK) in wireless rechargeable sensor networks. That is, there are a number of wireless chargers with directional antenna and rechargeable directional devices deployed in the 2D plane. An intelligent adversary selects a limited number of chargers to be captured and adjust the compromised chargers' power factor such that the overall attacking utility of devices is maximized. To solve our ATTACK problem, we investigate an attacking algorithm with a constant approximation ratio with lightweight timing complexity. We conduct simulation experiments to verify the performance of our proposed attacking algorithm. The results shows that our proposed attacking algorithm can outperform the comparison algorithm by 69.95%.

In this paper, we consider the problem of area charging, that is, assuming that there is a mobile charger (MC) equipped with a directional wireless charger whose charging area is in the shape of a sector, and the MC can only recharge sensors on the boundary of an Area of Interest (AOI), how to design an efficient charging scheme for the MC to recharge any sensor inside the AOI with efficient energy while its overall charging time is minimized. To address this problem, we first partition the AOI into two types of subareas, i.e., rectangle-like subareas and sector-like subareas, based on the Medial Axis of the AOI. Second, we propose rectangle-based moving strategy for the rectangle-like subareas, and sector-based rotating strategy for the sector-like subareas, respectively, for the MC. Finally, we calculate charging time of all subareas based on the above two moving strategies, and prove that our algorithm achieves a constant approximation ratio. We evaluate our algorithm by conducting extensive simulation. The results show that on average, other comparison algorithms require at least 18:70 times of charging time of that of our algorithm.

Although the logically-centralized perspective is offered in Software-Defined Networks (SDNs), the data plane is still distributed in nature. Update commands sent by the centralized controller are executed asynchronously and independently in each switch. The timed SDNs enable synchronous and coordinate update operations as each update command can be triggered by a pre-defined time point. Prior work on timed update mainly focuses on how to produce a congestion-free update sequence, whereas finding a congestion-free timed update sequence may be too long to be applied in practice, even worse, such an update order may not exist. In this paper, we propose Chronus+, a timed update system that utilizes switch buffer to shorten the update time while minimizing the switch buffer size during updates. We formulate the Minimum Switch Buffer Size Problem (MSBSP) as an optimization program and show its hardness. A set of efficient algorithms is proposed to determine a timed update sequence in polynomial time. Extensive evaluations in Mininet and large-scale simulations show that Chronus+can reduce the update time by at least 17% and the switch buffer by at least 27% compared with state-of-the-art approaches.

Mobile edge computing (MEC) is envisioned as an enabling technology for extreme low-latency services in the next generation 5G access networks. In a 5G-enabled MEC, computing resources are attached to base stations. In this way, network service providers can cache their services from remote data centers to base stations in the MEC to serve user tasks in their close proximity, thereby reducing the service latency. However, mobile users usually have various dynamic hidden features, such as their locations, user group tags, and mobility patterns. Such hidden features normally lead to uncertainties of the 5G-enabled MEC, such as user demand and processing delay. This poses significant challenges for the service caching and task offloading in a 5G-enabled MEC. In this paper, we investigate the problem of dynamic service caching and task offloading in a 5G-enabled MEC with user demand and processing delay uncertainties. We first propose an online learning algorithm for the problem with given user demands by utilizing the technique of Multi-Armed Bandits (MAB), and theoretically analyze the regret bound of the algorithm. We also propose a novel architecture of Generative Adversarial Networks (GAN) to accurately predict the user demands based on small samples of hidden features of mobile users. Based on the proposed GAN model, we then devise an efficient heuristic for the problem with the uncertainties of both user demand and processing delay. We finally evaluate the performance of the proposed algorithms by simulations based on a realistic dataset of user data. Experiment results show that the performance of the proposed algorithms outperform existing algorithms by around 15%.

As an epoch-making technology, wireless power transfer incredibly achieves energy transmission wirelessly, enabling reliable energy supplement for wireless rechargeable sensor networks (WRSNs). Existing methods mainly concentrate on performance improvement theoretically, neglecting the fact that most Commercial Off-The-Shelf (COTS) rechargeable sensors (e.g., WISP and Powercast) are not allowed to conduct sensing and energy harvesting tasks simultaneously, termed charging exclusivity. Therefore, their schemes are not feasible for practical applications. In this paper, we focus on the charging exclusivity issue in stochastic events monitoring while improving network performance. In specific, we pay close attention to trading off charging and sensing tasks and formulate a combinatorial optimization problem with routing constraints. We introduce novel discretization techniques and investigate the routing problem to reformulate the original problem into the maximization of a submodular function. With a slightly relaxed budget, the output of our proposed algorithm is better than (1 1/e)/2 of the optimal solution to the original problem with a -smaller charging radius (1 - ξ)Dc. Through extensive simulations, numerical results show that in terms of charging utility, our algorithm outperforms baseline algorithms by 21.3% on average. Moreover, we conduct test-bed experiments to demonstrate the feasibility of our scheme in real scenarios.

This paper studies the problem of Placing directional wIreless chargers with Limited mObiliTy (PILOT), that is, given a budget of mobile directional wireless chargers and a set of static rechargeable devices on a 2D plane, determine deployment positions, stop positions and orientations, and portions of time for all chargers such that overall charging utility of all devices can be maximized. To the best of our knowledge, we are the first to study placement of mobile chargers. To address PILOT, we propose a (1/2 - ε)-approximation algorithm. First, we present a method to approximate nonlinear charging power of chargers, and further propose an approach to construct Maximal Covered Set uniform subareas to reduce the infinite continuous search space for stop positions and orientations to a finite discrete one. Second, we present geometrical techniques to further reduce the infinite solution space for candidate deployment positions to a finite one without performance loss, and transform PILOT to a mixed integer nonlinear programming problem. Finally, we propose a linear programming based greedy algorithm to address it. Simulation and experimental results show that our algorithm outperforms five comparison algorithms by 31.33% ~ 281.10%.

Network update enables Software-Defined Networks (SDNs) to optimize the data plane performance via southbound APIs. The single update between the initial and the final network states fail to handle high-frequency changes or the burst event during the update procedure in time, leading to prolonged update time and inefficiency. On the contrary, the continuous update can respond to the network condition changes at all times. However, existing work, especially "Update Algebra" can only guarantee blackhole- and loop-free. The congestion-free property cannot be respected during the update procedure. In this paper, we propose Coeus, a continuous network update system while maintaining blackhole-, loop- and congestion-free simultaneously. Firstly, we establish an operation-based continuous update model. Based on this model, we dynamically reconstruct an operation dependency graph to capture unexecuted update operations and the link utilization variations. Subsequently, we develop an operation composition algorithm to eliminate redundant update commands and an operation node partition algorithm to speed up the update procedure. We prove that the partition algorithm is optimal and can guarantee the consistency. Finally, extensive evaluations show that Coeus can improve the makespan by at least 179% compared with state-of-the-art approaches when the arrival rate of update events equals to three times per second.

Benefitting from the recent breakthrough of wireless power transfer technology, Wireless Rechargeable Sensor Networks (WRSNs) have become an important research topic. Most prior arts focus on system performance enhancement in an ideal environment that ignores impacts of obstacles. This contradicts with practical applications in which obstacles can be found almost anywhere and have dramatic impacts on energy transmission. In this paper, we concentrate on the problem of charging a practical WRSN in the presence of obstacles to maximize the charging utility under specific energy constraints. First, we propose a new theoretical charging model with obstacles based on Fresnel diffraction model, and conduct experiments to verify its effectiveness. Then, we propose a spatial discretization scheme to obtain a finite feasible charging position set for MC, which largely reduces computation overhead. Afterwards, we reformalize charging utility maximization with energy constraints as a submodular function maximization problem and propose a cost-efficient algorithm with approximation ratio (e-1)/2e (1 - ε) to solve it. Lastly, we demonstrate that our scheme outperforms other algorithms by at least 14.8% in terms of charging utility through test-bed experiments and extensive simulations.

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.

A distributed control plane is more scalable and robust in software defined networking. This paper focuses on controller load balancing using packet-in request redirection, that is, given the instantaneous state of the system, determining whether to redirect packet-in requests for each switch, such that the overall control plane response time (CPRT) is minimized. To address the above problem, we propose a framework based on Lyapunov optimization. First, we use the drift-plus-penalty algorithm to combine CPRT minimization problem with controller capacity constraints, and further derive a non-linear program, whose optimal solution is obtained with brute force using standard linearization techniques. Second, we present a greedy strategy to efficiently obtain a solution with a bounded approximation ratio. Third, we reformulate the program as a problem of maximizing a non-monotone submodular function subject to matroid constraints. We implement a controller proto-type for packet-in request redirection, and conduct trace-driven simulations to validate our theoretical results. The results show that our algorithms can reduce the average CPRT by 81.6% compared to static controller-switch assignment, and achieve a 3× improvement in maximum controller capacity violation ratio.

The development of Wireless Power Transfer (WPT) facilitates wireless rechargeable sensor networks (WRSNs) receiving considerable attention in the sensor network research community. Most existing works mainly focus on general charging patterns and metrics while overlooking the precedence constraints among tasks, resulting in charging inefficiency. In this paper, we are the first to advance the issue of Scheduling wireless Charging tasks with Precedence Constraints (SCPC) with the optimization objective of minimizing the completion time of all the charging tasks under precedence constraints while guaranteeing that the energy capacity of mobile charger (MC) is not exhausted, and the deadlines of charging tasks are not exceeded. In order to address the problem, we first propose the priority-based topological sort scheme to derive an unique feasible sequence on directed acyclic graph (DAG). Then, we combine the proposed priority-based topological sort scheme with the procedure of genetic algorithm to obtain the final solution through a series of genetic operators. Finally, we conduct extensive simulations to validate our proposed algorithm under the condition of three different network sizes. The results show that our proposed algorithm outperforms the other two comparison algorithms by up to 35.5% in terms of completion time.

This paper studies the problem of robust frequent items mining in data streams that generalizes the traditional frequent items mining by considering the noise of datasets. That is, different items may correspond to the same entity because of noise; examples include different images of the same object and fluctuated data in the same setting measured by sensors. Our objective is to identify those items that correspond to the same entity and have an aggregated frequency exceeding a given threshold, which named as robust frequent items. To the best of our knowledge, there is no existing works on mining robust frequent items in a data stream. In this paper, we first propose a scheme by applying sampling and spatial partition to address the problem in low dimensional spaces. Furthermore, we extend the above algorithmic framework to high dimensional spaces by incorporating the locality sensitive hashing scheme to deal with the approximate nearest neighbor problem. We conduct evaluations using synthetic datasets and compare our scheme with two prior adapted schemes. Our results demonstrate that the efficiency of our algorithms outperforms the adaptive Space Saving by 14.8% and 9.8% in terms of precision and recall, respectively.

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.

Today's cellular core relies on a few expensive and dedicated hardware racks to connect the radio access network and the egress point to the Internet, which are geographically placed at fixed locations and use the specific routing policies. This inelastic architecture fundamentally leads to increased capital and operating expenses, poor application performance and slow evolution. The emerging paradigm of Network Function Virtualization (NFV) and Software Defined Networking (SDN) bring new opportunities for cellular networks, which makes it possible to flexibly deploy service chains on commodity servers and fine-grained control the routing policies in a centralized way. We present a two-stage optimization framework Plutus. The network-level optimization aims to minimize the service chain deployment cost, while the server-level optimization requires to determine which Virtualized Network Function (VNF) should be deployed onto which CPU core to balance the CPU processing capability. We formulate these two problems as two optimization programs and prove their hardness. Based on parallel multi-block ADMM, we propose a (δ, 2)-bicriteria approximation algorithm and a learning-based algorithm to address two cases whether the flow information and the resource consumption can be known as a priori, respectively. Large-scale simulations and DPDK-based OpenNetVM platform show that Plutus can reduce the capital cost by 84% and increase the throughput by 36% on average.

In this paper, we consider the scenario in which a mobile charger (MC) periodically travels within a sensor network to recharge the sensors wirelessly. We design joint charging and scheduling schemes to maximize the Quality of Monitoring (QoM) for stochastic events, which arrive and depart according to known probability distributions of time. Information is considered captured if it is sensed by at least one sensor. We focus on two closely related research issues, i.e., how to choose the sensors for charging and decide the charging time for each of them, and how to schedule the sensors' activation schedules according to their received energy. We formulate our problem as the maximum QoM CHArging and SchEduling problem (CHASE). We first ignore the MC's travel time and study the resulting relaxed version of the problem, which we call CHASE-R. We show that both CHASE and CHASE-R are NP-hard. For CHASE-R, we prove that it can be formulated as a submodular function maximization problem, which allows two algorithms to achieve 1/6- and 1/(4 + ε)-approximation ratios. Then, for CHASE, we propose approximation algorithms to solve it by extending the CHASE-R results. We conduct simulations to validate our algorithm design.

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.

This paper considers the problem of practical Heterogeneous wireless charger Placement with Obstacles (HIPO), i.e., given a number of heterogeneous rechargeable devices distributed on a 2D plane where obstacles of arbitrary shapes exist, deploying heterogeneous chargers with a given cardinality of each type, i.e., determining their positions and orientations, the combination of which we name as strategies, on the plane such that the rechargeable devices achieve maximized charging utility. After presenting our practical directional charging model, we first propose to use a piecewise constant function to approximate the nonlinear charging power, and divide the whole area into multi-feasible geometric areas in which a certain type of chargers have constant approximated charging power. Next, we propose the Practical Dominating Coverage Set extraction algorithm to reduce the unlimited solution space to a limited one by exacting a finite set of candidate strategies for all multi-feasible geometric areas. Finally, we prove the problem falls in the realm of maximizing a monotone submodular function subject to a partition matroid constraint, which allows a greedy algorithm to solve with approximation ratio of 1/2 - ε. We conduct experiments to evaluate the performance. Results show that our algorithm outperforms the comparison algorithms by at least 33.49 percent on average.

This paper concerns the problem of finding persistent items in distributed datasets, which has many applications such as port scanning and intrusion detection. To the best of our knowledge, there is no existing solution for finding persistent items in distributed datasets. In this paper, we propose DISPERSE, a probabilistic algorithm that can find persistent items in distributed datasets without collecting all the datasets. Our basic idea is that each monitor compresses each item ID in its dataset in a lossy fashion, sends the set of lossily compressed item IDs to the server, then the server recovers the IDs of the persistent items. We design the lossy compression so that given one lossily compressed item ID, the server cannot recover the item ID, but when the number of lossily compressed versions of the same item ID exceeds a threshold, which means that such items are persistent ones, the server can recover the item ID with a high probability. This threshold is exactly the threshold in the definition of persistent items. We implemented DISPERSE and evaluated its performance. In comparison with the straightforward solution, DISPERSE achieves a compression ratio of 26.5% with FNR=3.5% and FPR=0. In comparison with a developed Bloom filter based scheme and the adapted kBF and IBF schemes, our scheme can achieve 7.9, 5.7, and 6.6 times performance gains, respectively, in terms of compression ratio.

In this paper, we consider the problem of thresholded monitoring in distributed data streams, that is, given multiple distributed data streams observed by multiple monitors during a certain period, finding the items whose global frequencies over all data streams exceeding a given threshold. We first derive a lower bound of communication overhead for any deterministic algorithm for this problem. Then, we propose two different schemas, i.e., Low-threshold Cascaded Cuckoo Filter (L-CCF) for low-threshold monitoring and High-threshold Cascaded Cuckoo Filter (H-CCF) for high-threshold monitoring. L-CCF and H-CCF can identify items whose frequencies are more than the given threshold while a desired false negative rate (FNR) is achieved and communication overhead is optimized. The key idea is to compress the communication overhead caused by transferring the ID and frequency information at the same time. First, to reduce the communication overhead of transferring IDs, we propose to encode the IDs into separate tiny parts and store these tiny parts in L-CCF or H-CCF. Second, to reduce the communication overhead of transferring frequencies, we adopt a carry-in counter technique in L-CCF and multiple sampling technique in H-CCF. We evaluated L-CCF and H-CCF on two real-world traces and compared their performance with two prior adapted algorithms. Our experimental results show that on average, L-CCF and H-CCF achieve FNRs with 55% and 65% better than that of comparison algorithms while FPRs is maintained at the level of 2%.

This paper considers the fundamental problem of Placement of unmanned Aerial vehicles achieviNg 3D Directional coverAge (PANDA), that is, given a set of objects with determined positions and orientations in a 3D space, deploy a fixed number of UAVs by adjusting their positions and orientations such that the overall directional coverage utility for all objects is maximized. First, we establish the 3D directional coverage model for both cameras and objects. Then, we propose a Dominating Coverage Set (DCS) extraction method to reduce the infinite solution space of PANDA to a limited one without performance loss. Finally, we model the reformulated problem as maximizing a monotone submodular function subject to a matroid constraint and present a greedy algorithm with 1- 1/e approximation ratio to address this problem. We conduct simulations and field experiments to evaluate the proposed algorithm, and the results show that our algorithm outperforms comparison ones by at least 75.4%.

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.

In this paper, we consider the problem of thresholded monitoring in distributed data streams, that is, given multiple distributed data streams observed by multiple monitors during a certain period, finding the items whose global frequencies overall data streams exceeding a given threshold. We first derive a lower bound of communication overhead for any deterministic algorithm for this problem. Then, we propose two different schemas, i.e., Low-threshold Cascaded Cuckoo Filter (L-CCF) for low-threshold monitoring and High-threshold Cascaded Cuckoo Filter (H-CCF) for high-threshold monitoring. L-CCF and H-CCF can identify items whose frequency are more than the given threshold while a desired false negative rate (FNR) is achieved and communication overhead is optimized. The key idea is to compress the communication overhead caused by transferring the ID and frequency information at the same time. First, to reduce the communication overhead of transferring IDs, we propose to encode the IDs into separate tiny parts and store these tiny parts in L-CCF or H-CCF. Second, to reduce the communication overhead of transferring frequencies, we adopt carry-in counter technique in L-CCF and multiple sampling technique in H-CCF. We evaluated L-CCF and H-CCF on two real-world traces and compared their performance with two prior adapted algorithms. Our experimental results show that on average, L-CCF and H-CCF achieve FNRs with 55.7% and 65.56% better than that of comparison algorithms while FPRs is maintained at the level of 2.23%.

Wireless Rechargeable Sensor Network (WRSN) becomes a hot research issue in recent years owing to the breakthrough of wireless power transfer technology. Most prior arts concentrate on developing scheduling schemes in 2-D networks where mobile chargers are placed on the ground. However, few of them are suitable for 3-D scenarios, making it difficult or even impossible to popularize in practical applications. In this paper, we focus on the problem of charging a 3-D WRSN with an Unmanned Aerial Vehicle (UAV) to maximize charged energy within energy constraints. To deal with the problem, we propose a spatial discretization scheme to obtain a finite feasible charging spot set for UAV in 3-D environment and a temporal discretization scheme to determine charging duration for each charging spot. Then, we transform the problem into a submodular maximization problem with routing constraints, and present a cost-efficient approximation algorithm with a provable approximation ratio of e-1/4e(1-ε) to solve it. Lastly, extensive simulations and test-bed experiments show the superior performance of our algorithm.

Using a mobile charger to wirelessly charge sensors is a promising yet not well-solved technique. Existing trajectory planning schemes for wireless charger either (1) fail to optimize the one-to-many characteristic of wireless charging or (2) fail to jointly optimize the charger movement cost and the charging cost. The objective of this paper is to find the optimal trajectory planning for a mobile charger in terms of energy minimization in the quadratic attenuation charging model. There exists a trade-off between charging efficiency and trajectory distance. If the mobile charger comes close to sensors, the charging efficiency is high, but the entire charging trajectory of the charger will be long and vice versa. To address this trade-off, we propose the idea of charging bundle and optimize the charger's trajectory based on the charging bundle rather than each sensor. The optimal charging bundle generation problem and the bundle trajectory optimization problem are discussed gradually. Both of them are proven to be NP-hard. Then, we first propose a greedy bundle generation algorithm with an approximation ratio of lnn, where n is the number of sensors. After that, we propose a TSP-based solution and further optimize the TSP-trajectory by jointly considering the adjacent charging locations. Theorems are proposed to effectively find the optimal location. Extensive experiments show that our scheme achieves a much better performance than traditional schemes.

The Freemium-Crowdsourcing platform replaces purchases in Freemium games with crowdsourcing tasks, which can effectively incentivize player participation using the psychological factor of reward attraction. However, no previous researches focus on quantifying this factor, nor do they make an effort on controlling the answer quality produced by the hybrid platform. We propose a novel online algorithm, IGATA, to allocate crowdsourcing tasks to Freemium game players on the hybrid Freemium-Crowdsourcing platform. In order to maximize the task satisfaction to reduce waste caused by task refusal, while keeping competitive expected profit output, we measure the players' quality using their in-game attributes, and quantify the task reward attraction as the key factor of allocation with the help of psychological knowledge. Evaluations conducted on real trace data show that IGATA makes a significant improvement in producing total attraction comparing to existing strategies.

Virtualized network functions (VNFs) enable software applications to replace traditional middleboxes, which is more flexible and scalable in the network service provision. This paper focuses on ensuring Service Availability via Failure Elimination (SAFE) using VNF scaling, that is, given the resource requirements of VNF instances, finding an optimal and robust instance consolidation strategy, which can recover from one instance failure quickly. To address the above problem, we present a framework based on rounding and dynamic programming. First, we discretize the range of resource requirements for VNF instances deployment into several sub-ranges, so that the number of instance types becomes a constant. Second, we further reduce the number of instance types by gathering several small instances into a bigger one. Third, we propose an algorithm built on dynamic programming to solve the instance consolidation problem with a limited number of instance types. We set up a testbed to profile the functional relationship between resource and throughput for different types of VNF instances, and conduct simulations to validate our theoretical results according to profiling results. The simulation results show that our algorithm outperforms the standby deployment model by 27.33% on average in terms of the number of servers required. Furthermore, SAFE has marginal overhead, around 7.22%, compared to instance consolidation strategy without VNF backup consideration.

This paper considers the fundamental problem of Placement of unmanned Aerial vehicles achieviNg 3D Directional cover Age (PANDA), that is, given a set of objects with determined positions and orientations in a 3D space, deploy a fixed number of UAVs by adjusting their positions and orientations such that the overall directional coverage utility for all objects is maximized. First, we establish the 3D directional coverage model for both cameras and objects. Then, we propose a Dominating Coverage Set (DCS) extraction method to reduce the infinite solution space of PANDA to a limited one without performance loss. Finally, we model the reformulated problem as maximizing a monotone submodular function subject to a matroid constraint, and present a greedy algorithm with 1 -1 /e approximation ratio to address this problem. We conduct simulations and field experiments to evaluate the proposed algorithm, and the results show that our algorithm outperforms comparison ones by at least 75.4%.

In this paper, we deal with the problem of Robust schedUling for wireLess charger nEtworks (RULE), i.e., given a number of rechargeable devices, each of which may drift within a certain range, and a number of directional chargers with fixed positions and adjustable orientations distributed on a 2D plane, determining the orientations of the wireless chargers to maximize the overall expected charging utility while taking the charging power jittering into consideration. To address the problem, we first model the charging power as a random variable, and apply area discretization technique to divide the charging area into several subareas to approximate the charging power as the same random variable in each subarea and bound the approximation error. Then, we discretize the orientations of chargers to deal with the unlimited searching space of orientations with performance bound. Finally, by proving the submodularity of the problem after the above transformations, we propose an algorithm that achieves (1/2-ε)-approximation ratio. We conduct both simulation and field experiments, and the results show that our algorithm can perform better than other comparison algorithms by 103.25% on average.

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.

Today's cellular core relies on a few expensive and dedicated hardware racks to connect the radio access network and the egress point to the Internet, which are geographically placed at fixed locations and use the specific routing policies. This inelastic architecture fundamentally leads to increased capital and operating expenses, poor application performance and slow evolution. The emerging paradigm of Network Function Virtualization (NFV) and Software Defined Networking (SDN) bring new opportunities for cellular networks, which makes it possible to flexibly deploy service chains on commodity servers and fine-grained control the routing policies in a centralized way.

Mobile crowdsensing emerges as a new paradigm that takes advantage of pervasive sensor-embedded smartphones to collect sensory data. Many incentive mechanisms for mobile crowdsensing have been proposed. However, none of them takes into consideration the spatio-temporal tasks in mobile crowdsensing systems, where the sensing areas of tasks can have overlaps, and the collective sensing time for each task needs to meet the specified time duration. In this paper, we present two system models for location sensitive users and location insensitive users, respectively, and formulate the social optimization problem for each model. We design two reverse auction based truthful incentive mechanisms to minimize the social cost subject to the constraint that each of the spatio-temporal tasks can be completed with its collective sensing time no less than a minimum sensing time required by the platform. Through both theoretical analysis and extensive simulations, we demonstrate that the proposed mechanisms achieve computational efficiency, individual rationality, truthfulness, and guaranteed approximation.

This paper addresses the fundamental problem of identifying driver talking directions using a single smartphone, which can help drivers by warning distraction of having conversations with passengers in a vehicle and enable safety enhancement. The basic idea of our system is to perform talking status and direction identification using two microphones on a smartphone. We first use the sound recorded by the two microphones to identify whether the driver is talking or not. If yes, we then extract the so-called channel fingerprint from the speech signal and classify it into one of three typical driver talking directions, namely, front, right and back, using a trained model obtained in advance. The key novelty of our scheme is the proposition of channel fingerprint which leverages the heavy multipath effects in the harsh in-vehicle environment and cancels the variability of human voice, both of which combine to invalidate traditional TDoA, DoA and fingerprint based sound source localization approaches. We conducted extensive experiments using two kinds of phones and two vehicles for four phone placements in three representative scenarios, and collected 23 hours voice data from 20 participants. The results show that our system can achieve 95.0% classification accuracy on average.

Voice has been used as biometrics for human authentication because different people have different voice characteristics due to different vocal tract shapes and intonations. However, traditional voice based human authentication is subject to four types of attacks: impersonation, voice conversion, synthesis and voice replay. In this paper, we propose SpeakPrint, an ultrasound based human speech authentication scheme for smartphones which is resistant for these attacks. Compared with traditional speech authentication system which focuses on what a user speaks, SpeakPrint captures how a user speaks by recording mouth and vocal movement through ultrasound signal at the same time. Our key insight is that for the valid user, features extracted from voice signal should be consistent with his mouth and vocal movement recorded from ultrasound signal, while an imitator or an audio player can't produce the same signals in ultrasound domain. SpeakPrint extracts MFCC feature in normal voice frequency and MMSI features from ultrasound signal. An SVM classifier is trained to detect these attacks by comparing above feature differences. We implemented SpeakPrint on Samsung S5 and conducted experiments on 40 users. Experimental results show that SpeakPrint can detect replay attacks with 100% accuracy and replay attack with lip synching for 99.12% for passphrases longer than five words. This technology can be used in multi-factor authentication systems, where multiple authentication mechanisms are used to achieve defense in depth.

Benefitting from the discovery of wireless power transfer (WPT) technology, the wireless rechargeable sensor network (WRSN) becomes a promising way for lifetime extension for wireless sensor networks. However, in practical applications, obstacles can be found almost everywhere throughout the WRSN system. Most prior arts believe that obstacles will always degrade signal strength, they omit such influences for computation simplicity, which contradicts to the instincts of signal propagation, yielding their methods unsuitable for realistic adoptions. In this paper, we explore the wireless signal propagation process and provide a theoretical charging model to enhance charging efficiency by leveraging obstacles. Through utilizing the concept of the Fresnel Zones (FZs), we re-formalize the wireless charging model and discretize charging power to determine the best charging spots as well as charging durations. We model such charging efficiency maximization with obstacles (EMO) problem as a submodular function maximization problem and propose a cost-efficient algorithm with approximation ratio (e-1)/ε (1 - ε) to solve it. Finally, test-bed experiments and simulations are conducted to verify that our schemes outperform comparison algorithms by at least 10% in charging efficiency improvement.

This paper considers the fundamental problem of placement of Unmanned Aerial VehIcles for aniSotropic monItoring Tasks (VISIT). That is, given a set of objects on 2D area, place a fixed number of UAVs by adjusting their coordinates and orientations subject to Gaussian bias, such that the overall monitoring utility for all objects is maximized. We develop a theoretical framework to address VISIT. First, we establish the monitoring model whose quality of monitoring (QoM) is anisotropy with respect to monitoring angle and monitoring distance. To the best of our knowledge, we are the first to consider anisotropic QoM. Then, we propose an algorithm consisting of area discretization and Monitoring Dominating Set (MDS) extraction, to reduce the infinite solution space to a limited one without performance loss. Finally, we prove that the reformulated problem can be modeled as maximizing a monotone submodular function subject to a matroid constraint and present a greedy algorithm with 1−1/e−ϵ approximation ratio to address it. We conduct both simulations and field experiments to evaluate our algorithm, and the results show that our algorithm outperforms comparison algorithms by at least 41.3%.

Recently, wireless power transfer technology (WPT) has attracted considerable attention and become a promising technology to prolong the lifetime of wireless sensor networks (WSNs) by providing perpetual energy to sensors. However, electromagnetic radiation (EMR) incurred by WPT is largely overlooked in most of the existing literature. In this article, we first propose and study the radiation constrained fair charging problem for WPT, i.e., maximizing the minimum utility of sensors by adjusting the power of wireless chargers with no EMR intensity at any location in the field exceeding a given threshold R t . To address this problem, we first adopt an area discretization method to transform it from nonlinear to linear. Then, we propose four algorithms to deal with the reformulated problem, i.e., 1/3 and 1/4 Approximation Algorithms, Primal-Dual algorithm, and area division algorithm. In particular, the area division algorithm is not only fully distributed but also provably achieves an approximation ratio of (1 − ϵ). Further, we conduct extensive simulations and build a field testbed to verify our theoretical findings. Our simulation results show that the approximation ratios of the proposed algorithms hold; the Primal-Dual and area division algorithms have comparable performance of the optimal results and outperform baseline algorithms obviously.

The SDN control plane needs to frequently update the data plane as the network conditions change. Since each switch updates its flow table independently and asynchronously, the transition of data plane state - if done directly from the initial to the final stage - may result in serious flash congestion. Prior work strives to find a congestion-free update plan with multiple stages, each with the property that there will be no congestion independent of the update order. Yet congestion-free update may prevent the network from being fully utilized. It also requires solving a series of LP which is time-consuming. In this paper, we propose congestion-minimizing update and focus on two general problems: The first is to find routing at each intermediate stage that minimizes transient congestion for a given number of intermediate stages. The second is to find the minimum number of intermediate stages and an update plan for a given maximum level of transient congestion. We formulate them as two optimization programs and prove their hardness. We propose a set of algorithms to find the update plan in a scalable manner. Extensive experiments with Mininet show that our solution reduces update time by 50 percent and saves control overhead by 38 percent compared to prior work.

In recent years, with the development of mobile devices, the location based services (LBSs) have become more and more prevailing and most applications installed on these devices call for location information. Yet, the untrusted LBS provider can collect this location information, which may potentially threaten users' location privacy. In view of this challenge, we propose a two-tier schema for the privacy preservation based on k-anonymity principle meanwhile reducing the cost for privacy protection. Concretely, we divide the users into groups in order to maximize the privacy level and in each group one proxy is selected to generate dummy locations and share the returned results from LBS provider; then, on each group, an auction mechanism is proposed to determine the payment of each user to the proxy as the compensation, which satisfies budget balance and incentive compatibility. To evaluate the performance of the proposed schema, a simulated experiment is conducted.

Machine slot-time spent on data transmission has direct impact on average job completion time (JCT). In this paper, we propose Macroflow, a networking abstraction that can capture the primitive scheduling granularity of machine slot-time. We demonstrate that minimizing machine slot-time is equivalent to minimizing the average macroflow completion time (MCT). We prove that minimizing MCT to be strongly NP-hard and focus on developing effective heuristics. We propose the Smallest-Macroflow-First (SMF) and Smallest-Average-Macroflow-First (SAMF) heuristics that greedily schedule macroflows based on their network footprint. To work with existing commodity switches, priority discretization is performed to classify macroflows into a small number of priority queues.

State-of-the-art inter-datacenter WANs rely on software defined networking (SDN) to orchestrate their data transmission. Optimization requires frequent network update operations to switch forwarding tables. When scheduling inter-datacenter WANs, the utility of services should be respected. Yet, existing network update approaches do not respect network utility and could result in performance degradation during the network update procedure. Further, the update causes not only performance degradation, but also the degradation period is unnecessarily prolonged. In this paper we propose Hermes, a utility-aware network update system. We aim to find a rate limiting scheme for update which maximizes the sum of service utility, while ensuring the congestion-free property during the update. We propose an optimization framework for the maximum utility network update problem (MUP). MUP is NP-hard and a series of algorithms are developed to solve it. Extensive simulation and testbed experiments with a prototype demonstrate that Hermes can increase the total utility by 80% compared to state-of-the-art. At the same time, it reduces the total update time and control overhead by 40% and 55%, respectively.

This paper studies the problem of cHarging tAsk Scheduling for direcTional wireless chargEr networks (HASTE), i.e., given a set of rotatable directional wireless chargers on a 2D area and a series of offline (online) charging tasks, scheduling the orientations of all the chargers with time in a centralized offline (distributed online) fashion to maximize the overall charging utility for all the tasks. We prove that HASTE is NP-hard. Then, we prove that a relaxed version of HASTE falls within the realm of maximizing a submodular function subject to a partition matroid constraint, and propose a centralized offline algorithm that achieves (1-ρ)(1-1/e) approximation ratio to address HASTE where ρ is the switching delay of chargers. Further, we propose a distributed online algorithm and prove it achieves 1/2(1-ρ)(1-1/e) competitive ratio. We conduct simulations, and field experiments on a testbed consisting of 8 off-the-shelf power transmitters and 8 rechargeable sensor nodes. The results show that our distributed online algorithm achieves 92.97% of the optimal charging utility, and outperforms the comparison algorithms by up to 26.19% in terms of charging utility.

This paper proposes a new counter architecture for network measurement called Cache Assisted and randomizEd ShAring counteRs (CAESAR). One of the greatest challenges for per-flow traffic measurement is designing an online measurement module to keep up with the rapid growth of link speed. To address this challenge, we use a fast on-chip memory as the cache before the slow off-chip SRAM counters, thereby decreasing the accesses per flow to off-chip counters to improve time efficiency without any packet loss. We use randomized sharing counters among multiple flows in SRAM to achieve a compact data structure with high storage efficiency. By removing the impact from other flows sharing counters with a specific flow, we theoretically analyze the expectation and confidence interval of its estimated flow size accurately. In this paper, we use the real-world network traces for software simulations and FPGA experiments on the Xilinx Virtex-7 FPGA chip to validate our theoretical findings. The results show that CAESAR is up to 92.4% and 90% faster than prior work CASE and RCS respectively, and CAESAR reduces the average relative error of CASE and RCS by more than half.

This paper considers the problem of Heterogeneous wIreless charger Placement with Obstacles (HIPO), i.e., given a number of heterogeneous rechargeable devices distributed on a 2D plane where obstacles of arbitrary shapes exist, deploying heterogeneous chargers with a given cardinality of each type, i.e., determining their positions and orientations, the combination of which we name as strategies, on the plane such that the rechargeable devices achieve maximized charging utility. After presenting our practical directional charging model, we first propose to use a piecewise constant function to approximate the nonlinear charging power, and divide the whole area into multi-feasible geometric areas in which a certain type of chargers have constant approximated charging power. Next, we propose the Practical Dominating Coverage Set extraction algorithm to reduce the unlimited solution space to a limited one by exacting a finite set of candidate strategies for all multi-feasible geometric areas. Finally, we prove the problem falls in the realm of maximizing a monotone submodular function subject to a partition matroid constraint, which allows a greedy algorithm to solve with approximation ratio of 1/2 -- ϵ. We conduct both simulations and field experiments to evaluate the performance of our algorithm and other five comparison algorithms. The results show that our algorithm outperforms the comparison algorithms by at least 33.49% on average.

This paper concerns the problem of finding persistent items in distributed datasets, which has many applications such as port scanning and intrusion detection. To the best of our knowledge, there is no existing solution for finding persistent items in distributed datasets. In this paper, we propose DISPERSE, a probabilistic algorithm that can find persistent items in distributed datasets without collecting all the datasets. Our basic idea is that each monitor compresses each item ID in its dataset in a lossy fashion, sends the set of lossily compressed item IDs to the server, then the server recovers the IDs of the persistent items. We design the lossy compression so that given one lossily compressed item ID, the server cannot recover the item ID, but when the number of lossily compressed versions of the same item ID exceeds a threshold, which means that such items are persistent ones, the server can recover the item ID with a high probability. This threshold is exactly the threshold in the definition of persistent items. We implemented DISPERSE and evaluated its performance. In comparison with the straightforward solution, DISPERSE achieves a compression ratio of 26.5% with FNR=3.5% and FPR=O. In comparison with a developed Bloom filter based scheme and the adapted kBF and IBF schemes, our scheme can achieve 7.9, 5.7, and 6.6 times performance gains, respectively, in terms of compression ratio.

One critical issue for wireless power transfer is to avoid human health impairments caused by electromagnetic radiation (EMR) exposure. The existing studies mainly focus on scheduling wireless chargers so that (expected) EMR at any point in the area doesn't exceed a threshold Rt. Nevertheless, they overlook the EMR jitter that leads to exceeding of Rteven if the expected EMR is no more than Rt. This paper studies the fundamental problem of RObustly SafE charging for wireless power transfer (ROSE), that is, scheduling the power of chargers so that the charging utility for all rechargeable devices is maximized while the probability that EMR anywhere doesn't exceed Rt is no less than a given confidence. We first build our empirical probabilistic charging model and EMR model. Then, we present EMR approximation and area discretization techniques to formulate ROSE into a Second-Order Cone Program, and the first redundant second-order cone constraints reduction algorithm to reduce the computational cost, and therefore obtain a (1-ε)-approximation centralized algorithm. Further, we propose a (1-ε)-approximation fully distributed algorithm scalable with network size for ROSE. Simulations and field experiments show that our algorithms can outperform comparison algorithms by 480.19%.

Datacenter networks are critical to Cloud computing. The coflow abstraction is a major leap forward of application-aware network scheduling. In the context of multistage jobs, there are dependencies among coflows. As a result, there is a large divergence between coflow-completion-time (CCT) and job-completion-time (JCT). To our best knowledge, this is the first work that systematically studies: how to schedule dependent coflows of multi-stage jobs, so that the total weighted job completion time can be minimized. We present a formal mathematical formulation. We also prove that this problem is strongly NP-hard. Inspired by the optimal solution of the relaxed linear programming, we design an algorithm that runs in polynomial time to solve this problem with an approximation ratio of (2M + 1), where M is the number of machines. Evaluation results demonstrate that, the largest gap between our algorithm and the lower bound is only 9.14%. We reduce the average JCT by up to 33.48 % compared with Aalo, a heuristic multi-stage coflow scheduler. We reduce the total weighted JCT by up to 83.31 % compared with LP-OV-LS, the state-of-the-art approximation algorithm of coflow scheduling.

In this paper, we first study the problem of Connected wIReless Charger pLacEment (CIRCLE). That is, given a fixed number of directional wireless chargers and candidate positions, determining the placement position and orientation angle for each charger under connectivity constraint for wireless chargers such that the overall charging utility is maximized. To address CIRCLE, we first consider a relaxed version of CIRCLE (CIRCLE-R for short). We prove that CIRCLE-R falls into the realm of maximizing a submodular set function subject to a connectivity constraint, and propose an algorithm whose approximation ratio is at least 1.5 times better than that of the state-of-the-art algorithm. Next, we reduce the solution space for CIRCLE from infinite to finite, and propose an algorithm with a constant approximation ratio to address CIRCLE. We conduct both simulations and field experiments to verify our theoretical findings. The results show that our algorithm can outperform comparison algorithms by 83.35 %.

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%.

For AR/VR systems, tapping-in-the-air is a user-friendly solution for interactions. Most prior in-air tapping schemes use customized depth-cameras and therefore have the limitations of low accuracy and high latency. In this paper, we propose a fine-grained depth-aware tapping scheme that can provide high accuracy tapping detection. Our basic idea is to use light-weight ultrasound based sensing, along with one COTS mono-camera, to enable 3D tracking of user's fingers. The mono-camera is used to track user's fingers in the 2D space and ultrasound based sensing is used to get the depth information of user's fingers in the 3D space. Using speakers and microphones that already exist on most AR/VR devices, we emit ultrasound, which is inaudible to humans, and capture the signal reflected by the finger with the microphone. From the phase changes of the ultrasound signal, we accurately measure small finger movements in the depth direction. With fast and light-weight ultrasound signal processing algorithms, our scheme can accurately track finger movements and measure the bending angle of the finger between two video frames. In our experiments on eight users, our scheme achieves a 98.4% finger tapping detection accuracy with FPR of 1.6% and FNR of 1.4%, and a detection latency of 17.69ms, which is 57.7ms less than video-only schemes. The power consumption overhead of our scheme is 48.4% more than video-only schemes.

Recently, wireless power transfer is emerging as an enabling technology of wireless rechargeable sensor networks. Conventional methods that charge each sensor until its battery is full take unproportionally long time to finish, due to the limitation of charging efficiency and power transfer technologies. In this paper, we propose a mixed partial and full charge (MPF) scheme, including three specialized modules, i.e., evaluation module, adjustment module, and selection module. MPF allows nodes to be replenished "partially" by a mobile charging vehicle (MCV). When executing adjustment module, a concept of power and path adjustment window is proposed for determining a proper power allocation scheme as well as charging path. Then a scheduling strategy termed return mechanism is designed to further utilize the energy of the MCV and improve effective energy utilization. Finally, we build a high-accuracy charging test-bed and evaluate the applicability as well as performance of the proposed scheme. For large-scale networks, we also perform simulations to demonstrate the effectiveness of MPF in promoting survival rate and reducing traveling distance of the MCV.

With the rising of AR/VR technology and miniaturization of mobile devices, gesture is becoming an increasingly popular means of interacting with smart devices. Some pioneer ultrasound based human gesture recognition systems have been proposed. They mostly rely on low resolution Doppler Effect, and hence focus on whole hand motion and cannot deal with minor finger motions. In this paper, we present UltraGesture, a Channel Impulse Response (CIR) based ultrasonic finger motion perception and recognition system. CIR measurements can provide with 7 mm resolution, rendering it sufficient for minor finger motion recognition. UltraGesture encapsulates CIR measurements into an image, and builds a Convolutional Neural Network model to classify these images into different categories, which corresponding to distinct gestures. Our system runs on commercial speakers and microphones that already exist on most mobile devices without hardware modification. Our results show that UltraGesture achieves an average accuracy of greater than 97% for 12 gestures including finger click and rotation.

Gesture tracking is a basic Human-Computer Interaction mechanism to control devices such as electronic Internet of Things and VR/AR devices. However, prior WiFi signal based systems focus on gesture recognition and provide results with insufficient accuracy, and thus cannot be applied for highprecision gesture tracking. In this paper, we propose a CSI based device-free gesture tracking system, called WiTrace, which leverages the CSI values extracted from WiFi signals to enable accurate gesture tracking. For 1D tracking, WiTrace derives the phase of the signals reflected by the hand from the composite signals, and measures the phase changes to obtain the movement distance. For 2D tracking, WiTrace proposes the first CSI based scheme to accurately estimate the initial position, and adopts the Kalman filter based on Continuous Wiener Process Acceleration model to further filter out tracking noise. Our results show that WiTrace achieves the estimated accuracy of 3.91 cm for initial position on average, and achieves cm-level accuracy, with mean tracking errors of 1.46 cm and 2.09 cm for 1D tracking and 2D tracking, respectively.

Area coverage is one of the most common and critical applications for Flying Ad hoc Networks (FANETs), which typically involves a host of small or mini Unmanned Aerial Vehicles (UAVs). The increasingly large scale of FANETs brings challenges of networking and management, for which clustering scheme is an effective technique. However, there is a conflict between area coverage and network connectivity which is required for clustering and data transmission among UAVs. In this paper, we propose a MObility cOntrol based Clustering (MOOC) scheme for area coverage in FANETs. In MOOC, a mobility control strategy is designed for different types of nodes based on virtual forces, considering both reducing overlapped coverage and maintaining connections to improve clustering performances. The coverage and clustering performances of MOOC are analyzed and compared with other approaches through extensive simulations. The results show that MOOC outperforms the compared approaches by at least 37% and 235% respectively in terms of coverage efficiency while maintaining a high network connectivity. Meanwhile, MOOC also outperforms the other clustering algorithms by at least 503% on average in terms of cluster head duration.

Wireless power transfer technology is considered as one of the promising solutions to address the energy limitation problems for end-devices, but its incurred potential risk of electromagnetic radiation (EMR) exposure is largely overlooked by most existing works. In this paper, we consider the Safe Charging with Adjustable PowEr (SCAPE) problem, namely, how to adjust the power of chargers to maximize the charging utility of devices, while assuring that EMR intensity at any location in the field does not exceed a given threshold Rt. We present novel techniques to reformulate SCAPE into a traditional linear programming problem, and then remove its redundant constraints as much as possible to reduce computational effort. Next, we propose a series of distributed algorithms, including a fully distributed algorithm that provably achieves (1- ϵ) approximation ratio and requires only communications with neighbors within a constant distance for each charger. Through extensive simulation and testbed experiments, we demonstrate that our proposed algorithms can outperform the set-cover algorithm by up to 17.05%, and has an average performance gain of 41.1% over the existing algorithm in terms of the overall charging utility.

This paper studies the problem of Radiation cOnstrained scheduling of wireless Charging tasKs (ROCK), that is, given wireless charging tasks with required charging energy and charging deadline for rechargeable devices, scheduling the power of wireless chargers to maximize the overall effective charging energy for all rechargeable devices, and further to minimize the total charging time, while guaranteeing electromagnetic radiation (EMR) safety, i.e., no point on the considered 2-D area has EMR intensity exceeding a given threshold. To address ROCK, we first present a centralized algorithm. We transform ROCK from nonlinear problem to linear problem by applying two approaches of area discretization and solution regularization, and then propose a linear programming-based greedy test algorithm to solve it. We also propose a distributed algorithm that is scalable with network size by presenting an area partition scheme and two approaches called area-scaling and EMR-scaling, and prove that it achieves effective charging energy no less than (1- ε) of that of the optimal solution, and charging time no more than that of the optimal solution. We conduct both simulation and field experiments to validate our theoretical findings. The results show that our algorithm achieves 94.9% of the optimal effective charging energy and requires 47.1% smaller charging time compared with the optimal one when ε ≥ 0.2, and outperforms the other algorithms by at least 350.1% in terms of charging time with even more effective charging energy.

This paper addresses the fundamental problem of finding persistent items and estimating the number of times each persistent item occurred in a given data stream during a given period of time at any given observation point. We propose a novel scheme, PIE, that can not only accurately identify each persistent item with a probability greater than any desired false negative rate (FNR), but can also accurately estimate the number of occurrences of each persistent item. The key idea of PIE is that it uses Raptor codes to encode the ID of each item that appears at the observation point during a measurement period and stores only a few bits of the encoded ID in the memory. The item that is persistent occurs in enough measurement periods that enough encoded bits for the ID can be retrieved from the observation point to decode them correctly and get the ID of the persistent item. To estimate the number of occurrences of any given persistent item, PIE uses maximum likelihood estimation-based statistical techniques on the information already recorded during the measurement periods. We implemented and evaluated PIE using three real network traffic traces and compared its performance with three prior schemes. Our results show that PIE not only achieves the desire FNR in every scenario, its average FNR can be 19.5 times smaller than the FNR of the adapted prior scheme. Our results also show that PIE achieves any desired success probability in estimating the number of occurrences of persistent items.

Software-Defined Networks (SDNs) introduce interesting new opportunities in how network routes can be defined, verified, and changed over time. Yet despite the logically-centralized perspective offered, an SDN still needs to be considered a distributed system: rule updates communicated from the controller to the individual switches traverse an asynchronous network and may arrive out-of-order, and hence lead to (temporary or permanent) inconsistencies. Accordingly, the consistent network update problem has recently received much attention. Motivated by the advent of tightly synchronized SDNs, we in this paper initiate the study of algorithms for consistent network updates in “timed SDNs”-SDNs in which individual node updates can be scheduled at specific times. This paper presents Chronus, which is based on provably congestion- and loop-free update scheduling algorithms, and avoids the flow table space headroom required by existing two-phase update approaches. We formulate the Minimum Update Time Problem (MUTP) as an optimization program. We propose a tree algorithm to check the feasibility and a greedy algorithm to find a update sequence in polynomial time. Extensive experiments on Mininet and numerical simulations show that Chronus can substantially reduce transient congestion by 75% and save over 60% of the rules compared to the state of the art.

Wireless Power Transfer (WPT) technology has witnessed huge development because of its convenience and reliability. This paper concerns the fundamental issue of wireless charger PLacement with Optimized charging uTility (PLOT), that is, given a fixed number of chargers and a set of points on the plane, determining the positions and orientations of chargers such that the overall expected charging utility for all points is maximized. To address PLOT, we propose a 1 - 1/e - ε approximation algorithm. First, we present techniques to approximate the nonlinear charging power and the expected charging utility to make the problem almost linear. Second, we develop a Dominating Coverage Set extraction method to reduce the continuous search space of PLOT to a limited and discrete one without performance loss. Third, we prove that the reformulated problem is essentially maximizing a monotone submodular function subject to a matroid constraint, and propose a greedy algorithm to address this problem. We conduct both simulation and field experiments to validate our theoretical results, and the results show that our algorithm can outperform comparison algorithms by at least 46.3%.

This paper studies the problem of Radiation cOnstrained scheduling of wireless Charging tasKs (ROCK), that is, given wireless charging tasks with required charging energy and charging deadline for rechargeable devices, scheduling the power of wireless chargers to maximize the overall effective charging energy for all rechargeable devices, and further to minimize the total charging time, while guaranteeing electromagnetic radiation (EMR) safety, i.e., no point on the considered 2D area has EMR intensity exceeding a given threshold. To address ROCK, we first present a centralized algorithm. We transform ROCK from nonlinear problem to linear problem by applying two approaches of area discretization and solution regularization, and then propose a linear programming based greedy test algorithm to solve it. We also propose a distributed algorithm by presenting an area partition scheme and two approaches called area-scaling and EMR-scaling, and prove that it achieves effective charging energy no less than (1 -- ϵ) of that of the optimal solution, and charging time no more than that of the optimal solution. We conduct both simulation and field experiments to validate our theoretical findings. The results show that our algorithm achieves 94.9% of the optimal effective charging energy and requires 47.1% smaller charging time compared with the optimal one when ϵ ≥ 0.2, and outperforms the other algorithms by at least 350.1% in terms of charging time with even more effective charging energy.

Recently wireless power transfer technology (WPT) attracts considerable attention, its incurred electromagnetic radiation (EMR), however, is largely overlooked by most existing literatures. In this paper, we first propose and study the radiation constrained fair wireless charging problem, i.e., maximizing the minimum utility of devices by adjusting the power of wireless chargers with no EMR intensity at any location in the field exceeding a given threshold . To address this problem, we first adopt an area discretization method to transform it from nonlinear to linear. Then, we propose two algorithms to deal with the reformulated problem. One is called Primal-Dual algorithm, which is semi-distributed and uses lagrangian dual and subgradient methods to solve the problem iteratively. The other is called area division algorithm. It is not only fully distributed and scalable with network size, but also provably achieves an approximation ratio of (1- ϵ). We conducted extensive simulations and built a field test-bed to verify our theoretical findings. Our simulations show that the approximation ratio of the area division algorithm holds; the Primal-Dual and area division algorithms can have comparable and over 90.9% performance of the optimal results, respectively; and both of the algorithms outperform a baseline algorithm by more than 37%.

In our daily life, some sensitive cargos (e.g., refrigerators) are required to keep one right side up. If these items are turned upside down due to incorrect transportation or wrong storage, some unpredictable exception will happen, leading to potential economic loss. In this paper, we propose a lightweight system TagUP that uses RFID to detect the upside-down exception. By dynamically changing the frequency of the electromagnetic wave and comparing the phase difference between two measurements, TagUP is able to achieve the detection accuracy of 98.0% when two tags are placed 60cm apart.

Software-defined networks (SDNs) introduce interesting new opportunities in how network routes can be defined, verified, and changed over time. Despite the logically-centralized perspective offered, however, an SDN still needs to be considered a distributed system: rule updates communicated from the controller to the individual switches traverse an asynchronous network and may arrive out-of-order. This can lead to (temporary or permanent) inconsistencies and triggered much research over the last years. We, in this paper, initiate the study of algorithms for consistent network updates in “timed SDNs”-SDNs in which individual node updates can be scheduled at specific times. While technology enabling tightly synchronized SDNs is emerging, the resulting algorithmic problems have not been studied yet. This paper presents, implements and evaluates Chronus, a system which provides provably congestion- and loop-free network updates, while avoiding the flow table space headroom required by existing two-phase update approaches. We formulate the minimum update time problem as an optimization program and propose two polynomial-time algorithms which lie at the heart of Chronus: a decision algorithm to check feasibility and a greedy algorithm to find a good update sequence. Extensive experiments on Mininet and numerical simulations show that Chronus can substantially reduce transient congestion and save over 60% of the rules compared with the state of the art.

As battery-powered mobile devices become more popular and energy hungry, wireless power transfer technology, which allows the power to be transferred from a charger to ambient devices wirelessly, receives intensive interests. Existing schemes mainly focus on the power transfer efficiency but overlook the health impairments caused by RF exposure. In this paper, we study the safe charging problem (SCP) of scheduling power chargers so that more energy can be received while no location in the field has electromagnetic radiation (EMR) exceeding a given threshold Rt. We show that SCP is NP-hard and propose a solution, which provably outperforms the optimal solution to SCP with a relaxed EMR threshold (1-ε)Rt. Testbed results based on 8 Powercast TX91501 chargers validate our results. Extensive simulation results show that the gap between our solution and the optimal one is only 6.7% when ε = 0.1, while a naive greedy algorithm is 34.6% below our solution.

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.

Wireless Power Transfer (WPT) has received more and more attentions because of its convenience and reliability. In this paper, we first propose the notion of omnidirectional charging by which an area is omnidirectionally charged if a device with directional antennas at any position in the area with any orientation can be charged by directional chargers with power being no smaller than a given threshold. We present our empirical charging model based on field experimental results using off-the-shelf WPT products. Next, we consider the problem of detecting whether the target area achieves omnidirectional charging given a deterministic deployment of chargers. We develop piecewise constant approximation and area discretization techniques to partition the target area into subareas and approximate powers from chargers as constants. Then we propose the Minimum Coverage Set extraction technique which reduces the continuous search space to a discrete one and thereby allows a fast detection algorithm. Moreover, we consider the problem of determining the probability that the target area achieves omnidirectional charging given a random deployment of chargers. We first replace the target area by grid points on triangular lattices to reduce the search space from infinite to finite, then approximate chargers' power with reasonable relaxation, and derive an upper bound of the omnidirectional charging probability. Finally, we conduct both simulation and field experiments, and the results show that our algorithm outperforms comparison algorithms by at least 120%, and the consistency degree of our theoretical results and field experimental results is larger than 93.6%.

Wireless Power Transfer has become a commercially viable technology to charge devices because of the convenience of no power wiring and the reliability of continuous power supply. This paper concerns the fundamental issue of wireless charger placement with electromagnetic radiation (EMR) safety. Although there are a few wireless charging schemes consider EMR safety, none of them addresses the charger placement issue. In this paper, we propose PESA, a wireless charger Placement scheme that guarantees EMR SAfety for every location on the plane. First, we discretize the whole charging area and formulate the problem into the Multidimensional 0/1 Knapsack (MDK) problem. Second, we propose a fast approximation algorithm to the MDK problem. Third, we optimize our scheme to improve speed by double partitioning the area. We prove that the output of our algorithm is better than (1 - ϵ) of the optimal solution to PESA with a smaller EMR threshold (1 - ϵ/2)Rt and a larger EMR coverage radius (1 + ϵ/2)D. We conducted both simulations and field experiments to evaluate the performance of our scheme. Our experimental results show that in terms of charging utility, our algorithm outperforms the prior art by up to 45.7%.

This paper is on designing a compact data structure for multi-set membership testing allowing fast set querying. Multi-set membership testing is a fundamental operation for computing systems and networking applications. Most existing schemes for multi-set membership testing are built upon Bloom filter, and fall short in either storage space cost or query speed. To address this issue, in this paper we propose Noisy Bloom Filter (NBF) and Error Corrected Noisy Bloom Filter (NBF-E) for multi-set membership testing. For theoretical analysis, we optimize their classification failure rate and false positive rate, and present criteria for selection between NBF and NBF-E. The key novelty of NBF and NBF-E is to store set ID information in a compact but noisy way that allows fast recording and querying, and use denoising method for querying. Especially, NBF-E incorporates asymmetric error-correcting coding technique into NBF to enhance the resilience of query results to noise by revealing and leveraging the asymmetric error nature of query results. To evaluate NBF and NBF-E in comparison with prior art, we conducted experiments using real-world network traces. The results show that NBF and NBF-E significantly advance the state-of-the-art on multi-set membership testing.

Frequent item mining, which deals with finding items that occur frequently in a given data stream over a period of time, is one of the heavily studied problems in data stream mining. A generalized version of frequent item mining is the persistent item mining, where a persistent item, unlike a frequent item, does not necessarily occur more frequently compared to other items over a short period of time, rather persists and occurs more frequently over a long period of time. To the best of our knowledge, there is no prior work on mining persistent items in a data stream. In this paper, we address the fundamental problem of finding persistent items in a given data stream during a given period of time at any given observation point. We propose a novel scheme, PIE, that can accurately identify each persistent item with a probability greater than any desired false negative rate (FNR) while using a very small amount of memory. The key idea of PIE is that it uses Raptor codes to encode the ID of each item that appears at the observation point during a measurement period and stores only a few bits of the encoded ID in the memory of that observation point during that measurement period. The item that is persistent occurs in enough measurement periods that enough encoded bits for the ID can be retrieved from the observation point to decode them correctly and get the ID of the persistent item. We implemented and extensively evaluated PIE using three real network traffic traces and compared its performance with two prior adapted schemes. Our results show that not only PIE achieves the desired FNR in every scenario, its FNR, on average, is 19.5 times smaller than the FNR of the best adapted prior art.

We study the problem of supporting simultaneous query in WSNs. For such networks, the network efficiency can be significantly improved if the poller can obtain information via a simultaneous query. Two fundamental cases of such queries are studied in this paper: counting and identifying active neighboring nodes. We propose two mechanisms, Power based counting (Poc) and Power based identification (Poid), which achieve the goals by allowing neighbors to respond simultaneously to a poller. A key observation that motivates our design is that the power of a superposed signal increases with the number of component signals under the condition that the component signals are synchronized precisely. However, such high precision of synchronization is rather difficult to achieve in WSNs. To address this challenge, we design delicate delay compensation methods to reduce the phase offset of each component signal. Moreover, we propose a novel probabilistic estimation technique to overcome the hardware limitations on the observed received power. Poid currently works only in sparse networks though, we discuss and analyze the time complexity of applying Poid in dense networks. Experimental results show that the average accuracy of Poc and Poid is above 95 and 91 percent, respectively. In addition, our methods achieve substantially lower energy consumption and estimation delay compared with the state-of-the-art solutions.

To maximize data center network utilization, the SDN control plane needs to frequently update the data plane as the network conditions change. Since each switch updates its flow table independently and asynchronously, the state transition -- if done directly from the initial to the final stage -- may result in serious flash congestion and packet loss. Prior work strives to find a congestion-free update plan with multiple stages, each with the property that there will be no congestion independent of the update order. Yet congestion-free update requires part of the link capacity to be left vacant and decreases utilization of the expensive network infrastructure. Further, it involves solving a series of LP, which is slow and does not scale well. In this paper, we study the more general problem of minimizing transient congestion during network update, given the number of intermediate stages. This exposes the tradeoff between update speed and transient congestion, and allows an operator to navigate a broader design space for performing network update. We formulate the minimum congestion update problem (MCUP) as an optimization program and prove its hardness. We propose an approximation algorithm and a greedy improvement algorithm to find the update sequence in an efficient and scalable manner. Extensive experiments with Mininet show that our solution reduces update time by 50% and saves control overhead by 30% compared to state of the art.

Tree-based routing structures are widely used to gather data in wireless sensor networks. Along with tree structures, in-network aggregation is adopted to reduce transmissions, to save energy and to prolong the network lifetime. Most existing works that focus on the lifetime optimization for data aggregation do not take the link quality into consideration. In this paper, we study the problem of Maximizing Reliability of Lifetime Constrained data aggregation trees (MRLC) in WSNs. Considering the NP-completeness of the MRLC problem, we propose an algorithm, namely Iterative Relaxation Algorithm (IRA), to iteratively relax the optimization program and to find the aggregation tree subject to the lifetime bound with a sub-optimal cost. To adapt to the distributed nature of the WSNs in practice, we further propose a Prufer code based distributed updating protocol. Through extensive simulations, we demonstrate that IRA outperforms the best known related work in term of reliability.

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.

Multihop broadcasting in low-duty-cycle Wireless Sensor Networks (WSNs) is a very challenging problem, since every node has its own working schedule. Existing solutions usually use unicast instead of broadcast to forward packets from a node to its neighbors according to their working schedules, which is, however, not energy efficient. In this article, we propose to exploit the broadcast nature of wireless media to further save energy for low-duty-cycle networks, by adopting a novel broadcasting communication model. The key idea is to let some early wake-up nodes postpone their wake-up slots to overhear broadcasting messages from its neighbors. This model utilizes the spatiotemporal locality of broadcast to reduce the total energy consumption, which can be essentially characterized by the total number of broadcasting message transmissions. Based on such model, we aim at minimizing the total number of broadcasting message transmissions of a broadcast for low-duty-cycle WSNs, subject to the constraint that the broadcasting latency is optimal. We prove that it is NP-hard to find the optimal solution, and design an approximation algorithm that can achieve a polylogarithmic approximation ratio. Extensive simulation results show that our algorithm outperforms the traditional solutions in terms of energy efficiency.

One fundamental question for wireless power transfer technology is the energy provisioning problem, i.e., how to provide sufficient energy to mobile rechargeable nodes for their continuous operation. Most existing works overlooked the impacts of node speed and battery capacity. However, we find that if the constraints of node speed and battery capacity are considered, the continuous operation of nodes may never be guaranteed, which invalidates the traditional energy provisioning concept. In this paper, we propose a novel metric-Quality of Energy Provisioning (QoEP)-to characterize the expected portion of time that a node sustains normal operation by taking into account node speed and battery capacity. To avoid confining the analysis to a specific mobility model, we study spatial distribution instead. As there exist more than one mobility models corresponding to the same spatial distribution, and different mobility models typically lead to different QoEPs, we investigate upper and lower bounds of QoEP in 1D and 2D cases. We derive tight upper and lower bounds of QoEP for 1D case with a single source, and tight lower bounds and loose upper bounds for general 1D and 2D cases with multiple sources. Finally, we perform extensive simulations to verify our theoretical findings.

Network coding has the potential to provide powerful support to transmit real-time traffic in wireless network. In this paper, we utilize pairwise coding to schedule the flows which have heterogeneous delay constraints and weights. Our goal is to maximize the weighted sum of scheduled packets that satisfy the delay constraints. We formulate the problem as an integer linear programming problem, and propose two algorithms to solve it. The first algorithm drops the integral constraints and rounds the fractional solutions in such a way that the rounded solution is also optimal. Inspired by the first algorithm and for better running time, we propose the second algorithm based on a minimum cost flow formulation. The formulation is proved to be equivalent to the original integer linear programming formulation. Simulations are conducted to show the effectiveness of our approach over two greedy algorithms.

Wireless power transfer technology is considered as one of the promising solutions to address the energy limitation problems for end-devices, but its incurred potential risk of electromagnetic radiation (EMR) exposure is largely overlooked by most existing works. In this paper, we consider the Safe Charging with Adjustable PowEr (SCAPE) problem, namely, how to adjust the power of chargers to maximize the charging utility of devices, while assuring that EMR intensity at any location in the field does not exceed a given threshold Rt. We present novel techniques to reformulate SCAPE into a traditional linear programming problem, and then remove its redundant constraints as much as possible to reduce computational effort. Next, we propose a distributed algorithm with provable approximation ratio (1 - ε). Through extensive simulation and testbed experiments, we demonstrate that our (1 - ε)-approximation algorithm outperforms the Set-Cover algorithm by up to 23%, and has an average performance gain of 41.1% over the SCP algorithm in terms of the overall charging utility.

As battery-powered mobile devices become more popular and energy hungry, wireless power transfer technology receives intensive interests, as it allows the power to be transferred from a charger to ambient devices wirelessly. The existing studies mainly focus on the power transfer efficiency but overlook the health impairments caused by RF exposure. In this paper, we study the Safe Charging Problem (SCP) of scheduling power chargers so that more energy can be received while no location in the field has electromagnetic radiation (EMR) exceeding a given threshold Rt. We prove that SCP is NP-hard and propose a solution which provably outperforms the optimal solution to SCP with a relaxed EMR threshold (1 - ε)Rt. Testbed results based on 8 Powercast TX91501 chargers validate our results. Extensive simulation results show that the gap between our solution and the optimal one is only 6.7% when ε = 0.1, while a naive greedy algorithm is 34.6% below our solution.

Flooding is one of the most fundamental functions in wireless sensor networks (WSNs) and has been investigated extensively. Existing flooding schemes in duty-cycle WSNs can be categorized into two categories: synchronous ones and asynchronous ones. In practice asynchronous schemes are preferable since synchronous ones introduce more complexity and overhead for necessary clock synchronization. Existing asynchronous approaches are however imperfect for reliable flooding in duty-cycle WSNs. For example, opportunistic flooding is less flexible and Asynchronous Duty-cycle Broadcasting (ADB) suffers unsatisfactory flooding latency. We propose Constructive Interference-based Reliable Flooding (CIRF) in this paper, a novel design for reliable flooding in asynchronous duty-cycle WSNs. CIRF is integrated with the MAC protocol Receiver-Initiated MAC (RI-MAC) to improve the utilization of wireless medium and guarantee one-hop reliable transmission. The key idea of CIRF is to exploit the constructive interference feature when concurrent transmission occurs, which can be common in RI-MAC based WSNs. Simulation results indicate that CIRF achieves reliable flooding with reduced flooding latency, higher energy efficiency and delivery ratio compared to existing schemes.

Wireless Rechargeable Sensor Networks (WRSNs) can be recharged after deployment for sustainable operations. Recent works propose to use a single mobile charger (MC) traveling through the network fields to recharge every sensor node. These algorithms work well in small scale networks. However, in large scale networks these algorithms do not work efficiently, especially when the amount of energy the MC can provide is limited. To address these challenges, multiple MCs can be used. In this paper, we investigate the minimum MCs problem (MinMCP) for rechargeable sensor networks: how to find the minimum number of energy-constrained MCs and design their recharging routes given a sensor network such that each sensor node in the WRSN maintains continuous work. Our results are three folds. We first prove that for any ϵ > 0, there is no (2-ϵ)-approximation algorithm for Distance Constrained Vehicle Routing Problem (DVRP) on a general metric space, which is the best as far as we know. By reducing from DVRP, we prove that MinMCP is NP-hard, and the inapproximability bound for MinMCP is the same as that of DVRP. Then we propose approximation algorithms for this problem. Finally, we conduct simulations to validate the effectiveness of our algorithms.

Though much existing work exploits wireless power charging to enhance sensor network performance such as routing and data aggregation, few efforts focus on issues of stochastic event capture. In this paper, we consider the scenario in which a mobile charger (MC) periodically travels within a sensor network to recharge the sensors wirelessly, to maximize the Quality of Monitoring (QoM) for stochastic events. Towards this goal, two closely related research issues need to be addressed. One is how to choose the sensors for charging and decide the charging time for each of them, the other is how to best schedule the sensors' activation schedules according to their received energy. In this paper, we jointly design the charging scheme and sensor schedules to maximize the QoM. We formulate our problem formally as the maximum QoM charging and scheduling problem (MQCSP). Obtaining an exact solution of MQCSP is challenging. Thus we first ignore the MC's travel time and study the resulting relaxed version of MQCSP, R-MQCSP. We show both MQCSP and R-MQCSP are NP-hard. For R-MQCSP, however, under a special condition, we prove that it can be formulated as a sub modular function maximization problem. This formulation allows a 1/6-approximation algorithm for the general case, and a unified algorithm with a series of approximation factors (up to 1-1/e) for a special case. Then, for MQCSP, we propose approximation algorithms by extending our R-MQCSP results. Finally, we conduct extensive trace-driven simulations to validate our algorithm design. The empirical results corroborate our theoretical analysis.

For low-duty-cycle wireless sensor networks, multihop broadcasting is a challenging problem, since every node has its own working schedules. In this paper, we design a novel broadcasting algorithm, of which key idea is to let some early wake-up nodes postpone their wake-up slots to overhear broadcasting message from its neighbors. This design utilizes the spatiotemporal locality of broadcasting to reduce the number of transmissions. We show that to find the broadcasting schedule with minimal latency and optimized total energy consumption is NP-hard, and then design an approximation algorithm that can guarantee the optimality of broadcasting latency and achieve a polylogarithmic approximation ratio for total energy consumption. Compared with the traditional solution, extensive experimental results show that our algorithm achieves the minimal broadcasting latency while reducing energy consumption significantly.

Existing scheduling schemes for stochastic event capture with rechargeable sensors either adopt simplified assumptions on event staying time or provide no performance guarantee. Considering the stochasticity of event staying time, we investigate the sensor scheduling problem aiming to maximize the overall Quality of Monitoring (QoM) in events capture application of wireless rechargeable sensor networks. We first provide a paradigm to calculate the QoM of a point of interests (PoI) and formulate the scheduling problem into an optimization problem. Although we find that that this problem is NP-complete, we prove that the objective function of the optimization problem is monotone submodular. Therefore we can express the problem as a maximization of a submodular function subject to a matroid constraint. Accordingly we can design an approximation algorithm which achieves a factor of 1/2 of the optimum. We evaluate the performance of our solution through simulations, and simulation results show that our scheme outperforms former works.

One fundamental question in Wireless Rechargeable Sensor Networks (WRSNs) is the energy provisioning problem, i.e., how to deploy energy sources in a network to ensure that the nodes can harvest sufficient energy for continuous operation. Though the potential mobility of nodes has been exploited to reduce the number of sources necessary in energy provisioning problem in existing literature, the non-negligible impacts of the constraints of node speed and battery capacity on energy provisioning are completely overlooked, in order to simplify the analysis. In this paper, we propose a new metric - Quality of Energy Provisioning (QoEP) - to characterize the expected portion of time that a mobile node can sustain normal operation in WRSNs, which factors in the constraints of node speed and battery capacity. To avoid confining the analysis to a specific mobility model, we study spatial distribution instead. We investigate the upper and lower bounds of QoEP in one-dimensional case with one single source and multiple sources respectively. For single source case, we prove the tight lower bound and upper bound of QoEP. Extending the results to multiple sources, we obtain tight lower bound and relaxed upper bound in normal cases, together with tight upper bound for one special case. Moreover, we give the tight lower bounds in both 2D and 3D cases. Finally, we perform extensive simulations to verify our findings. Simulation results show that our bounds perfectly hold, and outperform the former works.

In many applications of WSNs, the events occur infrequently but once they occur, the corresponding information needs to be sent to the sink node in a short period of time for the necessary reactions. Detection of rare events in a fast and energy-efficient manner is an important issue in WSNs. In this paper, based on the optimal solution for the Best-choice Problem with Bounded Random Observation Number, we propose an Energy-efficient Online Decision Scheme (EODS) to handle this problem. Combining with the design of nodes' duty cycle, the EODS avoids the redundant transmissions and achieves the tradeoff between delay and energy efficiency. Simulation results reveal that the EODS achieves a good balance between delay and energy efficiency.