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.

Edge Video Analytics (EVA) significantly reduces response time by executing analytical tasks at the edge. However, it inevitably faces accuracy loss when dealing with highly complex analytical scenarios. To overcome this, we propose offloading the most complex video frames to the cloud while processing other frames at the edge. Nevertheless, determining both the quantity and the specific selection of frames for offloading poses challenges due to edge-cloud bandwidth constraints and the dynamic nature of video content. To tackle this problem, we present a Discerning and Elastic Offloading Framework (DEOF), which consists of an Accuracy Predictor and an Offloading Scheduler. The former identifies the detection complexity of each frame by predicting its F1-score gain based on multidimensional information, enabling it to discern and select the most complex frames for offloading. The latter determines the optimal proportion of frames to process in the cloud and at the edge by designing a Lyapunov-optimization-based algorithm, which elastically adjusts this proportion in response to time-varying video content and resource conditions, thus ensuring both adaptability and efficiency. We have implemented DEOF fully based on COTS hardware, and the experimental results demonstrate the effectiveness of DEOF, showing that our system can reduce offloaded data volume by$7.1 \%-36.3 \%$, decrease latency by$\mathbf{2. 6 \% - 1 9. 5 \%}$, and improve accuracy by$\mathbf{2. 6 \%}$3.2 % compared to alternative methods.

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.

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

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.

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.

Periodicity and fluctuation are two crucial characteristics of data streams. This paper investigates a novel data stream pattern called periodic spread changer (PSC flow for short), which refers to the heavy change in the spread of a flow occurring with fixed time intervals. Effectively identifying such flows is essential for many real-world applications, such as anomaly detection and network monitoring. To achieve precise real-time detection of these flows under limited memory resources, we propose a novel structure named PSC Sketch. PSC Sketch firstly performs the spread estimation by removing duplicate data items and filters out those non-potential flows with small spreads. During the measurement period, PSC Sketch detects the spread changers, calculates the time intervals between adjacent heavy changes, and reports the top-k periodic spread changers. Extensive experiments based on four real-world datasets demonstrate that, compared to competing algorithms, PSC Sketch achieves an average of 16.80 times lower average absolute error, 44.93% higher accuracy, and 1.83 times higher throughput.

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.

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

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

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.

As the popularity of mobile devices continues to increase, Mobile Crowdsensing (MC), a scalable and efficient data collection method, has received widespread attention. Although lots of effort has been devoted to studying the task assignment or worker recruitment in MC, most of them focus on how to maximize the profit from the perspective of the platform while ignoring rational individual workers' entitlement. We creatively start from the worker's perspective to find the task selection strategy to maximize the worker's profit. In this paper, the problem of unknown task selection is modeled as a Multi-Armed Bandit (MAB), on which three types of additional constraints are considered. The first constraint is the device budget. Workers choose and conduct tasks before it is exhausted. The second constraint is the personal preference regarding the traveling cost. The third constraint is the balance requirement of the MC platform, which has regulations on the tasks' execution rounds. In addition to the dilemma between exploration and exploitation in the classical MAB, we have to face the tradeoff between the reward and all the constraints above. To this end, we first adopt the epoch-style algorithm to reduce the number of switches between any two sensing tasks and further build new algorithms to deal with different constraints. The traveling cost and platform balance are involved in the task index computation as a penalty. We conduct extensive simulations based on real-world traces to verify the significant performance of our proposed algorithms.

Per-flow spread measurement in high-speed networks can provide indispensable information to many practical applications. However, it is challenging to measure millions of flows at line speed because on-chip memory modules cannot simultaneously provide large capacity and large bandwidth. The prior studies address this mismatch by entirely using on-chip compact data structures or utilizing off-chip space to assist limited on-chip memory. Nevertheless, their on-chip data structures record massive transient elements, each of which only appears in a short time interval in a long-period measurement task, and thus waste significant on-chip space. This paper presents short-term memory sampling, a novel spread estimator that samples new elements while only holding elements for short periods. Our estimator can work with tiny on-chip space and provide accurate estimations for online queries. The key of our design is a short-term memory duplicate filter that reports new elements and filters duplicates effectively while allowing incoming elements to override the stale elements to reduce on-chip memory usage. We implement our approach on a NetFPGA-equipped prototype. Experimental results based on real Internet traces show that, compared to the state-of-the-art, short-term memory sampling reduces up to 99% of on-chip memory usage when providing the same probabilistic assurance on spread-estimation error.

With the rapid development of the Internet of Things (IoT), massive high-speed data streams are produced every moment, making accurate size estimation a challenging task. Many sketches have been proposed to summarize real-time high-speed data streams and provide per-flow size estimations. However, sketches have to share the memory units to fit in limited on-chip space, inevitably introducing noises to all flows and resulting in over-estimation problems. Prior work adopts an average denoising strategy to remove the same noise from raw sketch estimations. However, they overlook that the noise distribution is highly skewed, leading to inaccurate results for most flows. This paper proposes an efficient Adaptive Noise Correction (ANC) framework, which analyzes the noise of each flow on a case-by-case basis and provides accurate size estimations. The key of our design is to build an ML model to predict a weight coefficient that indicates the noises in raw estimations, which is conducted for each flow by analyzing the neighbor flows whose memory units overlap with the given flow. Then we introduce a novel Probabilistic Cold Filter to block the tiny flows and assist in noise correction. Experimental results based on real Internet traces show that our framework can effectively remove the noises for different sketches, showing better estimation accuracy than the state-of-the-art.

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

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

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.

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

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.

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.

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

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.

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

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