Network traffic measurement is indispensable for many network management tasks. Time-series traffic pattern detection extends the benefits of traditional single-period flow measurement by revealing dynamic flow behaviors, but also yields higher complexity. When multiple patterns must be monitored simultaneously, building a separate sketch for each pattern is prohibitive since programmable switches typically allow only one resource-intensive sketch. In this paper, we propose PatternSketch, which enables general and dynamically reconfigurable time-series pattern detection within a single sketch. PatternSketch unifies the detection of diverse patterns with a Pattern Automaton and decomposes the pattern detection process into two phases in the data plane, while allowing operators to reconfigure the active set of monitoring patterns at runtime without taking the switch offline. Our implementation on an Intel Tofino switch demonstrates that PatternSketch can operate at line rate, detecting multiple patterns concurrently while using only tens of kilobytes of SRAM. This significantly reduces both computational and storage resource consumption compared to deploying multiple, pattern-specific sketches. Evaluations on four real-world datasets show that the hardware version of PatternSketch maintains over 90% F1 scores while simultaneously detecting six time-series patterns (three representative and three newly proposed) with as little as 200KB of memory.

Abstract The identification of key flows, as one of the most important traffic measurement tasks in high-speed networks, has lots of practical applications, including network resource optimization and network attack detection. However, the existing works define the key flows only according to the flow size or the persistence (i.e. time dimension), all of which are one-sided definitions. To bridge the gap, we propose a new metric (named $H$-value) to identify key flows in high-speed networks, in which the flow $H$-value metric considers the joint distribution of flow size and time relationships. Specifically, the $H$-value of one flow means the flow size of this flow in at least $H$ measurement periods is not less than $H$. Based on this new metric, we redefine the key flows as the flows with large $H$-values, called $H^{2}$-flow. Efficiently and accurately identifying $H^{2}$-flows in high-speed networks faces significant challenges due to limited memory space, uneven distribution of flow $H$-values, and real-time requirements. To this end, we propose a new sketch structure called H$^{2}$Sketch, which consists of two main modules. Extensive experimental results based on real datasets show that H$^{2}$Sketch outperforms all the compared solutions in all evaluation metrics, such as ARE, F1 score, and throughput.

Key-value data streams are widely spread in modern information systems. This paper delves into the inner features of individual keys and introduces a new measurement task called Core Composition Estimation for Frequent Keys (CCEFK). CCEFK aims to identify the most significant values associated with an item's key, which can be fully applied to a wide range of real-world scenarios. To address this quite challenging, multidimensional CCEFK mission, we propose PieSketch, a novel sketch-based algorithm that supports three types of queries related to CCEFK. PieSketch employs a three-level data structure and a two-staged insertion algorithm to process the keys and values of data streams separately and sequentially, achieving fine-grained data summarization for both. Through some rigorous theoretical analysis, we prove that PieSketch can achieve a good performance guarantee with low time and space complexity. We further present three optimizations to enhance PieSketch comprehensively: Sector Morphing addresses the diversity in value distribution among different keys with a dynamically adjusting strategy, significantly improving memory efficiency; Early Filtration ensures PieSketch's stability in extreme conditions; SIMD Acceleration speeds up PieSketch for data processing. We finally conducted extensive experiments on four real-world datasets to evaluate PieSketch's excellent performance. The results show that PieSketch significantly outperforms state-of-the-art techniques, achieving$23.67\times$,$88.41\times$, and$15.80\times$better accuracy on three types of queries, respectively, and demonstrating 1.84 times higher insertion throughput on average. All our codes are publicly available on GitHubhttps://github.com/NeoAnderson-20/PieSketch-source.

Federated learning (FL) is a promising paradigm that can enable collaborative model training between vehicles while protecting data privacy, thereby significantly improving the performance of intelligent transportation systems (ITSs). In vehicular networks, due to mobility, resource constraints, and the concurrent execution of multiple training tasks, how to allocate limited resources effectively to achieve optimal model training of multiple tasks is an extremely challenging issue. In this paper, we propose a mobility-aware multi-task decentralized federated learning (MMFL) framework for vehicular networks. By this framework, we address task scheduling, subcarrier allocation, and leader selection, as a joint optimization problem, termed TSLP. For the case with a single FL task, we derive the convergence bound of model training. For general cases, we first model TSLP as a resource allocation game, and prove the existence of a Nash equilibrium (NE). Then, based on this proof, we reformulate the game as a decentralized partially observable Markov decision process (DEC-POMDP), and develop an algorithm based on heterogeneous-agent proximal policy optimization (HAPPO) to solve DEC-POMDP. Finally, numerical results are used to demonstrate the effectiveness of the proposed algorithm.

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.

Identifying the hierarchical heavy hitters (HHHs), i.e., the frequent aggregated flows based on common IP prefixes, is a vital task in network traffic measurement and security. Existing methods typically employ dynamic trie structures to track numerous prefixes or utilize multiple separate sketch instances, one for each hierarchical level, to capture HHHs across different levels, while both approaches suffer from low memory efficiency and limited compatibility with programmable switches. In this paper, we introduce two novel HHH detection solutions, respectively, Hierarchical Heavy Detector (HHD) and the Compressed Hierarchical Heavy Detector (CHHD), to achieve high memory efficiency and enhanced hardware compatibility. The key idea of HHD is to design a shared bucket array structure to identify and record HHHs from all hierarchical levels, which avoids the memory wastage of maintaining separate sketches to achieve high memory efficiency and allows feasible deployment of both byte-hierarchy and bit-hierarchy HHH detection on programmable switches using minimal processing stage resources. Additionally, HHD utilizes a sampling-based update strategy to effectively balance packet processing speed and detection accuracy. Furthermore, we present the CHHD, which enhances HHH detection in bit hierarchies through a more compact cell structure, which allows for compressing several ancestor and descendant prefixes within a single cell, further boosting memory efficiency and accuracy. We have implemented HHD and CHHD on a P4-based programmable switch with limited switch resources. Experimental results based on real-world Internet traces demonstrate that HHD and CHHD outperform the state-of-the-art by achieving up to 56 percentage points higher detection precision and 2.6× higher throughput.

Traffic measurement provides indispensable information to many applications in improving network performance. However, the limited on-chip resources face great challenges in measuring millions of flows simultaneously with high accuracy, and the highly skewed traffic distribution further worsens the performance. Although filtering the vast majority of small flows in advance can help to improve the measurement performance, existing filters have limitations in either filtering range or processing overhead. This paper proposes two efficient filters, including Swing-Size Filter for small-size flow filtering and Swing-Spread Filter for small-spread flow filtering. Both provide a flexible and extended filtering range for network traffic measurement. One key to our design is the use of signed counters whose values swing in positive and negative directions to cancel out small-size or small-spread flows, thereby enlarging the filtering range. We show that the proposed filters are highly effective in filtering small flows while keeping the advantages of low memory overhead and processing overhead. They support various measurement tasks and offer guaranteed bounds on the misreport rate. We implement our filters in both software and hardware, with the hardware version developed in P4 language on a programmable switch. Experiments based on real-world Internet traces show that our filters can reduce the flow size and flow spread estimation errors by an order of magnitude and support high throughput.

Large-scale cloud providers build geo-distributed regions to provide a wide range of services for global users. Due to the potentialcrash failuresof hardware components, the availability zone (AZ) architecture has been proposed for fault tolerance and service availability. In practice, a region consists of multiple AZs and each AZ runs independently. Considering the huge traffic volume and service diversity, how to properly deploy tasks for cost saving and QoS guarantee becomes a major challenge for cloud providers. However, existing task placement works often ignore the impact of crash failures, severely affecting users’ QoS. And fault-tolerant task placement works usually overlook other aspects of performance. Moreover, the AZ architecture has not been fully utilized in previous works. To bridge the gap, this paper proposes AzuRe, a joint region- and AZ-aware task placement framework to satisfy various tenants’ requirements in a cost-efficient manner. Due to the features of cloud services, we take a two-step approach:region-level task placement and AZ-level sub-task placement. For region-level task placement, we prove its NP-Hardness and propose an algorithm based on submodular theory with an approximation ratio of (1 − 1/e). For AZ-level sub-task placement, we formalize the problem as a multiple knapsacks problem with conflict graphs. Based on threshold rounding, we propose an algorithm with a bi-criteria approximation ratio of (2,O(log |A|)), where |A| is the number of AZs. Extensive simulation experiments on real datasets show that AzuRe improves the resource utilization ratio by up to 129.42% compared to the state-of-the-art solutions and limits the cost while meeting various kinds of region- and AZ-level requirements.

To provide a wide range of services for global users, cloud providers tend to build geo-distributed regions all over the world. With the rapid growth of cloud services, massive workloads and inter-region traffic have been introduced to current cloud networks, resulting in huge expenditure. Therefore, it is essential for a cloud provider to carefully place tasks and transfer traffic among regions to minimize the total operating costs. Existing solutions typically focus on optimizing either placement costs (e.g., computing resources, and electricity) or bandwidth costs, and overlook performance metrics, which leads to increased overall operating costs or lower user QoS. To bridge the gap, this paper proposes Copo, a joint cost and performance optimization framework for tenant task placement in geo-distributed clouds. We first formalize the cost optimization problem as an undetermined multi-commodity flow problem which has never been studied before, and propose a graph transformation algorithm to reduce the complexity. Then we combine the cost optimization with the performance optimization as the final framework. The key idea of Copo is leveraging KKT conditions to transfer the bi-level optimization to a single level. To efficiently acquire the joint task placement and traffic transfer decisions, we leverage McCormick Envelope-based relaxation to design a randomized rounding-based approximation algorithm. Extensive experiments based on real-world data show the superior cost-efficiency and performance of Copo compared with state-of-the-art solutions.

Achieving load balancing under dynamic workloads remains a critical challenge in cloud computing. However, due to inherent prediction inaccuracies and task load volatility, existing static or dynamic scheduling approaches struggle to reconcile real-time responsiveness with long-term resource efficiency, particularly when facing imprecise prediction, declared uncertainty, and data drift. To address these challenges, we propose Focus, which introduces three key innovations to achieve fault-tolerant scheduling: (1) a dynamic reservation algorithm that leverages cluster-level predictive thresholds to maintain flexible buffer capacity for sudden workload spikes, thus ensuring efficient scheduling under peak demand; (2) a multi-level load-queue architecture that enhances tolerance to task load fluctuations through probabilistic machine selection; and (3) a past information conservative mechanism combined with dynamic weighted drift detection to mitigate prediction degradation. Through the evaluation of 40 million task executions across real-world traces, Focus demonstrates superior load balancing compared to state-of-the-art algorithms, reducing load imbalance by 23.3 % under prediction errors up to 20 %.

Container scheduling is a critical issue in cloud computing. However, existing container scheduling algorithms focus on resource allocation under multiple resource constraints to maximize resource utilization while overlooking the need to balance the load of the containers and fail to mitigate resource fragmentation during task scheduling, resulting in suboptimal use of compute resources and increased makespan. This oversight often translates into unnecessarily prolonged system completion times. To solve the issue, this paper introduces the Container Scheduling with Moldable Tasks (CSMT) problem, addressing these inefficiencies through a novel framework Mocas. Mocas includes Affallo algorithm with an affinity function to achieve load balance and a fully polynomial time approximation scheme (FPTAS) DoubleShelves with an approximate ratio of$(\mathbf{1}+\mathbf{3} \epsilon)$to eliminate resource fragmentation. Extensive experiments on the real-world datasets demonstrate that the Mocas outperforms state-of-the-art solutions, achieving up to 67 % improvement in makespan compared to conventional rigid scheduling methods.

Large-scale cloud providers build geo-distributed regions to provide a wide range of services for global users. Due to the potential crash failures of hardware components, the availability zone (AZ) architecture has been proposed for fault tolerance. In practice, a region consists of multiple AZs and each$\mathbf{A Z}$runs independently. Considering the huge traffic volume and service diversity, how to properly deploy tasks for cost saving and QoS guarantee becomes a major challenge for cloud providers. However, existing task placement works often ignore the impact of crash failures, severely affecting users' QoS. And fault tolerance task placement works usually overlook other aspects of performance. Moreover, the AZ architecture has not been fully utilized in previous works. To bridge the gap, this paper proposes Azure, a cost-efficient task placement framework for fault tolerance and cost efficiency at the AZ-level. Due to traffic dynamics, we take a two-step approach: regionlevel task placement and AZ-level sub-task placement. For regionlevel task placement, we prove its NP-Hardness and propose an algorithm based on submodular theory with an approximation ratio of ($1-\frac{1}{e}$). For AZ-level sub-task placement, we formalize the problem as a multiple knapsack problem with conflict graph, which has never been studied before. Based on threshold rounding, we propose an algorithm with an approximation ratio of 2. Extensive simulation experiments on real datasets show that Azure improves resource utilization rate by$\mathbf{1 3 \% - 5 3 \%}$and limits the cost while meeting fault tolerance requirements.

Current web applications like social networks and video streaming have been generating magnificent traffic volume, along with intensive traffic dynamics, raising challenges to the fundamental infrastructure of web, i.e., datacenters. However, the traditional electric-based architectures are behind the curve due to the fixed topology and the demand-oblivious nature, failing to guarantee the performance of web applications. Motivated by the new traffic pattern, the reconfigurable technologies, like optical circuit switches (OCSes), are a promising choice to further improve throughput by dynamically adjusting connections when facing traffic dynamics. Currently, static and dynamic updating are two main methods for reconfiguring OCSes. Though static methods can acquire a solution with approximation ratio, it takes long running time and recourse. As comparison, dynamic updating can efficiently acquire a solution, yet existing solutions may degrade along with updates. This paper presents Talbot to further improve throughput with both approximation guarantee and low updating time/recourse. We formulate the throughput maximization problem as a fully dynamic k-weight limited matching problem which is$\mathcal{N} \mathcal{P}$-hard, and we further propose an approximation algorithm based on level and lazy update scheme. To evaluate Talbot, simulations are conducted with both real-world and synthetic datasets. Compared with state-of-the-art works, we show the superior performance of Talbot.

This paper investigates the problem of maintaining the connectivity between two vertices, a source and a destination, in an uncertain network under adversarial attack, where a defender preserves crucial links to prevent the source–destination vertex pair from being disconnected by an attacker. In contrast with prior art that mostly focuses on the overall network connectivity, in this work connectivity maintenance is restricted to a pair of selected vertices, which may provide insights into reliable point-to-point connection. We model the network as a random graph where each link carries both an existence probability and a probing cost, and seek to design a defensive strategy that ensures source–destination connectivity under minimum probing expenditure, regardless of adversarial behavior. To this end, we first delve into the computational complexity of the problem by establishing its NP-hardness, and put forth an optimal defensive strategy leveraging dynamic programming. Due to the prohibitive price of attaining optimality, we further design two approximate defensive strategies aimed at pursuing effective defensive performance within polynomial time, in which the first one is a path-based heuristic strategy that iteratively extends a preserved path by probing links with high utility regarding source–destination connectivity, and the second one is a cut-based minimax strategy that prioritizes the links in the minimum potential source–destination cut in order to minimize the possible worst-case loss suffered by the defender with a constant approximation ratio. Extensive experiments conducted on synthetic and real-world network datasets under diverse attacking strategies validate the superiority of the proposed strategies in both effectiveness and robustness over baselines.

Hyperspectral (HS) and light detection and ranging (LiDAR) fusion for land-cover identification in multimodal tasks is always restricted owing to modality heterogeneity, especially when annotated samples are unavailable. Clustering techniques become pivotal in these unsupervised scenarios, yet their inability to offer interpretable fusion mechanisms poses challenges in pursuing enhanced identification performance. In this article, an Intuitive Assimilation Modality-driven Crossmodal Subspace Clustering (IamCSC) method is proposed to exploit intuitive crossmodal information. Different from existing multiview clustering approaches, our core innovation is that IamCSC distills an intuitive assimilation modality (IAM) with distinguishing geological characteristics of HS and LiDAR images simultaneously. The IAM with a small number of IAM channels still preserves the spectral similarity and diversity of neighboring samples. Meanwhile, it reflects sample elevations by peak regions along the IAM channel dimension. Specifically, the IAM connects and balances these two RS modalities to learn an assimilation cluster structure from modality-specific subspace representations. Several matrix-wise constraints are considered for capturing the optimal modality-shared representation. Given that IamCSC does not exhibit over-reliance on spatial neighborhood contributions, it achieves satisfactory performance particularly in image pairs with larger ground sampling distances (GSDs). Multiple experiments clearly prove the effectiveness of IamCSC over state-of-the-art techniques qualitatively and quantitatively. The codes are provided inhttps://github.com/GEOywb/IamCSC.

Approximate membership query data structures (i.e., filters) have ubiquitous applications in database and data mining. Cuckoo filters are emerging as the alternative to Bloom filters because they support deletions and usually have higher operation throughput and space efficiency. However, their designs are confined to a single-threaded execution paradigm and consequently cannot fully exploit the parallel processing capabilities of modern hardware. This paper presents PipeFilter, a faster and more space-efficient filter that harnesses pipeline parallelism for superior performance. PipeFilter re-architects the Cuckoo filter by partitioning its data structure into several sub-filters, each providing a candidate position for every item. This allows the filter operations, including insertion, lookup, and deletion, to be naturally distributed across several pipeline stages, each overseeing one of the sub-filters, which can further be implemented through multi-threaded execution or pipeline stages of programmable hardware to achieve significantly higher throughput. Meanwhile, PipeFilter excels for single-threaded execution thanks to a combination of unique design features, includingblock design,path prophet,round robin, andSIMD optimization, such that it achieves superior performance than the SOTAs even when running with a single core. PipeFilter also has a competitive advantage in space utilization because it permits each item to explore more candidate positions. We implement and optimize PipeFilter on four platforms (single-core CPU, multi-core CPU, FPGA, and P4 ASIC). Experimental results demonstrate that PipeFilter surpasses all baseline methods on four platforms. When running with a single core, it showcases a notable 15%$\sim$57% improvement in operation throughput and a high load factor exceeding 99%. When parallel processing on other platforms, PipeFilter achieves 7$\times \sim 800\times$higher throughput than single-threaded execution.

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.

Network traffic measurement is crucial for the effective management of data center networks. Collaborative measurement solutions distribute measurement tasks to switches based on flow-level or packet-level granularity to alleviate the measurement load on each switch. However, flow-level solutions often experience severe imbalances in measurement overhead between switches measuring large or small flows, and face scalability challenges due to the costly optimization of collaborative plans. Additionally, packet-level solutions do not adequately reduce hash collisions in sketches and fail to significantly enhance measurement accuracy. In this article, we present the Lightweight Two-level Collaborative Measurement (LTCM) that synergies flow-level and packet-level strategy to optimize measurement load balancing, reduce overall measurement overhead, and enhance measurement accuracy. We first design a Lightweight Flow-level Measurement (FCM) framework that balances the number of flows measured by each switch, incorporating a novel interval-matching technique that significantly lowers the computational costs of collaborative strategies. Based on FCM, LTCM implements our measurement load balancing strategy selector at ingress switches to detect flows whose number of packets entering the network exceeds a given threshold and evenly distribute their subsequent packets across all switches for measurement. To further improve measurement accuracy and speed, we design a two-layer collaborative sketch that reduces hash collisions between large and small flows. We implement LTCM on a Tofino-based programmable switch. Experimental results based on real Internet traces show that LTCM achieves highly efficient flow-level and packet-level measurement load balancing, improving accuracy by up to 96.6% and throughput by up to 112.79%. All related implementations are open-sourced. 1

Running deep neural networks (DNNs) on large-scale videos from widely distributed cameras presents two significant challenges. Firstly, video quality for analytical purposes is severely impacted by the camera deployment environment, which is termed Pixel Recession in this paper. Secondly, low-latency video streaming from the source camera to edge servers is greatly hindered by the rapid expansion of video traffic. Despite numerous efforts such as enhancing the video structure, uneven encoding, and filtering frames captured on camera, these methods have proven insufficient to address the challenges at hand. We propose Spliceosome, a novel video analytics system that effectively overcomes the pixel recession and streaming bottlenecks. In brief, Spliceosome 1) recovers from pixel recession by adaptive video knobs (i.e., brightness and contrast) tuning in ARP (anchor region proposal) granularity, and 2) lowers the transmission volume by video thinning, which uses only single-channel information for video encoding. We implemented Spliceosome using only commercial off-the-shelf hardware. Our experimental results demonstrate that Spliceosome outperforms other alternative designs by 4.71-14.47%, 40.94-58.71%, and 14.28% in detection accuracy, end-to-end delay, and efficiency of DNNs inference, respectively.

With 52.8 billion RFID tags used worldwide in 2024, a common basic functionality needed by RFID-enabled applications is cardinality estimation — to quickly estimate the number of distinct tags in an RFID system. Although many advanced solutions have been proposed over the past decade, they suffer from one major limitation in practical use: they need to either modify the existing RFID standard or obtain MAC-layer information, both of which however cannot be supported by commercial off-the-shelf (COTS) devices. In this paper, we revisit the counting problem and propose a novel counting scheme called average time duration based counter (ATD) that quickly estimates the number of distinct tags in a standards-compliant manner. Compared with existing work, the competitive advantage of ATD is that it can be directly deployed on a COTS RFID system, with no need for any hardware modifications. In ATD, we found a new and measurable indicator — the time duration between two adjacent singleton slots, which depends on the number of tags. Following this observation, we derive the theoretical relationship between the time indicator and the number of tags and then give the proof of the estimation as well as its parameter settings. Additionally, we propose a flag-flipping solution to address the overlapping problem in the multi-reader case. We implement ATD in a COTS RFID system with 1000 tags. Experimental results show that ATD is$4.2\times $faster than the baseline of tag inventory; the performance gain will be further increased in a larger RFID system.

Spread measurement is an essential problem in high-speed networks with broad applications, such as anomaly detection and network telemetry. Network administrators typically need to concurrently monitor the spreads of different types of flows to detect various abnormal behaviors. Although many studies have designed memory-efficient structures, such as sketches, for a specific spread measurement task, they have to deploy multiple sketches to support multiple spread measurement tasks, resulting in significant memory and computational overhead. This paper proposes an efficient multi-task information compression method to simultaneously estimate differently defined flow spreads. We introduce multi-information sampling to capture multi-task spread information from each arriving packet by one pass and store it in off-chip memory, thereby conserving on-chip memory and computational resources. Additionally, we carefully designed a one-access multi-dimensional structure called Supercube to preserve as much spread information as possible while catching up with the line rate, thereby enhancing estimation accuracy. We implement our estimator in hardware using NetFPGA. Experiments based on real Internet traces show that our method reduces the ARE by 83.36% for spread estimation compared to rSkt (SOTA) with 300KB of on-chip memory and increases update throughput by 251.252-fold compared to Supersketch. All source codes are available athttps://github.com/Hanwen808/MIME.

Submodular maximization algorithms have found wide applications in various fields such as data summarization, recommendation systems, and active learning. In recent years, deletion-robust submodular maximization algorithms have garnered attention due to their significant implications in scenarios where some data points may be removed due to user preferences or privacy concerns, such as in recommendation systems and influence maximization. In this paper, we study the fundamental problem of submodular maximization with knapsack constraints and propose a robust streaming algorithm for it. To the best of our knowledge, our algorithm is the first to solve this problem for non-monotone submodular functions and can achieve an approximation ratio of 1/(6.82+2.63d)-ϵ under a near-optimal summary size of O(k+r), where k denotes the maximum cardinality of any feasible solution, d denotes the number of the knapsack constraints and r is the robustness parameter. For monotone submodular functions, our algorithm can achieve an approximation ratio of 1/(2+2d)-ϵ under a near-optimal summary size of O(k+r), significantly improving upon the best-known ratio of Ω((1/d-ϵ)^2). The empirical performance of our algorithm is extensively evaluated in several applications including influence maximization and recommendation systems, and the experimental results demonstrate the effectiveness of our algorithm.

Heavy hitter detection is a fundamental network measurement task that provides critical support for many network applications. However, achieving flexible and fast heavy hitter detection in massive network traffic is challenging. Existing works generally perform detection by tracking large flows that may become heavy hitters, but they struggle to accurately identify these large flows, leading to poor accuracy. In this paper, we propose an efficient detection algorithm called HeavyCuckoo, which shows high flexibility and fast processing. We track only those large flows likely to be heavy hitters, replacing small flows of limited use for detection by exploring the activity of flow arrivals. During replacement, we utilize a tailored Conservative Replacement strategy and a tailored Selective Cuckoo Hash strategy to avoid large flows from being replaced incorrectly. We conduct theoretical analyses of memory space complexity and time complexity, and provide the error bound for heavy hitter detection. Our proposed algorithm is evaluated on real-world Internet traffic traces. Experimental results show that, compared to the prior art, the algorithm improves the Fβ-score by 56.94% and achieves 1.4724 times throughput.

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.

Traffic measurement provides essential information for various network services. Burst is a common phenomenon in high-speed network streams, which manifests as a surge in the number of incoming packets in a flow. We propose a new definition named across-period burst, considering the change not in two adjacent time windows but in two groups of windows with time continuity. The across-period burst definition can better capture the continuous changes of flows in high-speed networks. To achieve real-time burst detection with high accuracy and low memory consumption, we propose a novel sketch named BurstDetector, which consists of two stages. Stage 1 excludes those flows that will not become burst flows, while Stage 2 accurately records the information of the potential burst flows and carries out across-period burst detections at the end of every time window. We further propose an optimization called Hierarchical Cell, which can improve the memory utilization of BurstDetector. In addition, we analyze the estimation accuracy and time complexity of BurstDetector. Extensive experiments based on real-world datasets show that our BurstDetector can achieve at least 2.8 times as much detection accuracy and processing throughput as some existing algorithms.

This paper studies a new but important pattern for items in data streams, called promising items. The promising items mean that the frequencies of an item in multiple continuous time windows show an upward trend overall, while a slight decrease in some of these windows is allowed. Many practical applications can benefit from the property of promising items, e.g., detecting potential hot events or news in social networks, preventing network congestion in communication channels, and monitoring latent attacks in computer networks. To accurately find promising items in data streams in real-time under limited memory space, we propose a novel structure named Scout Sketch, which consists of Filter and Finder. Filter is devised based on the Bloom filter to eliminate the ungratified items with less memory overload; Finder records some necessary information about the potential items and detects the promising items at the end of each time window, where we propose some tailor-made detection operations. We also analyze the theoretical performance of Scout Sketch. Finally, we conducted extensive experiments based on four real-world datasets. The experimental results show that the F1 Score and throughput of Scout Sketch are about 2.02 and 5.61 times that of the compared solutions, respectively.

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.

Mobile crowdsensing (MC), an excellent solution to large-scale spatiotemporal data sensing problems, has recently received lots of attention from both industry and academia. In the MC system, any requester can acquire the sensing data for his points of interest (PoIs) by offering some payments to attract a group of mobile users capable of completing these PoI-related sensing tasks. However, the current MC work neglected three vital factors, more or less. First, they assume that these distributed users are mutually independent in MC, ignoring the social effects. Actually, the sensing data collected by one user may be corroborated by others’ sensing data, so-called information corroboration. Second, all rational and selfish users are inclined to gather to perform these tasks due to information corroboration. Meanwhile, they may be strategic about their participation levels to maximize profits. However, more similar sensing data will undoubtedly lower the information value, so any user has a tradeoff between gather and scatter. Third, although mobile users can obtain some payments, privacy issues may still prevent them from participating in MC. In this article, we propose a secure blockchain-assisted socially-aware MC framework by adopting the smart contract technique of Ethereum. For this framework, we further devise a two-stage Stackelberg game model to assist the requester (i.e., the leader in the game) in properly pricing each PoI-related sensing task, so that mobile users (i.e., the followers in the game) can exactly select their tasks and determine their participation levels. To analyze the game equilibrium, we extend the traditional Hessian matrix method to a multidimension case involving the multiuser multitask hyperspace setting. We conduct extensive experiments to prove the equilibrium and effectiveness of the proposed solution. We also implement a prototype and deploy the smart contract to an official Ethereum test network to demonstrate the practicability of the proposed framework.

Numerous deep learning (DL) studies have indicated that fusing hyperspectral (HS) and light detection and ranging (LiDAR) data is effective for land-cover classification. However, the sequential characteristics (seqCHAs) in the spatial domain are always ambiguous and neglected. In this letter, we propose a deep crossmodal sequential interaction network (CsiNet) for HS and LiDAR data joint classification. We aim to verify the contributions of crossmodal seqCHAs in multimodal joint classification tasks and present an effective crossmodal sequential flattening (SF) strategy. Specifically, CsiNet sorts the neighboring samples in terms of the spectral and 3-D spatial diversities between the corresponding samples and the central one. Notably, the 3-D spatial diversity considers the shared sample positions in both modalities and the sample elevations in LiDAR data simultaneously. CsiNet is capable of extracting crossmodal sequential features comprehensively by long and short-term memory (LSTM) layers and better simulating sequential properties of samples compared with convolutional layer based networks. Experiments conducted on the Muufl Gulfport (MUUFL) and Houston 2013 datasets prove that CsiNet outperforms several state-of-the-art techniques qualitatively and quantitatively. When using 1% training samples per category, the overall accuracies of CsiNet on both datasets achieve 90.27% and 92.41% and are increased by 0.27% and 0.17% than the best comparison technique, respectively. Ablation experiments verify the effectiveness of CsiNet by replacing the crossmodal SF strategy with several alternative ones. All codes are available athttps://github.com/GEOywb/CsiNet.

Super spreader detection in high-speed data streams is crucial for numerous applications. Although many methods have emerged, existing works can hardly concurrently achieve high memory efficiency, support online detection, enable merging data from different measurement points/periods, and offer invertibility. This makes them unable to satisfy flexible application requirements. This paper proposes RGS-Sketch, a novel sketch designed to address this problem. The core of RGS-Sketch lies in a new mergeable memory sharing design called register group sharing. This design organizes registers into groups as basic memory sharing units, accommodating the high skewness of real-world data streams and offering high memory efficiency. Besides, it enables online detection through the real-time acquisition of a group's state, which also facilitates invertibility. To enhance detection accuracy further, we propose a limited register update strategy. It blocks small flows from updating registers, thereby reducing memory overhead and estimation noises. Extensive experimental results based on four real-world datasets show that RGS-Sketch significantly outperforms the most accurate baselines in accuracy while maintaining a high throughput. Specifically, it improves the F1 scores by up to 0.643 for measurements at a single point/period and up to 0.472 across multiple points/periods.

Fusing hyperspectral (HS) and light detection and ranging (LiDAR) data is capable of enhancing land-cover interpretation capability in multimodal remote sensing (RS) tasks. Nevertheless, nonuniform surrounding illumination in real-world capturing scenarios tends to distort the spectral curves of on-ground objects, inevitably resulting in poor classification performance. This nonuniform illumination further interferes with the cross-modal RS information interaction procedure. In this article, an Illumination Insensitive Modalitywise Assimilation guided Multistage Interaction network (MAMInet II) is proposed to tackle this challenge. Our primary motivation is to eliminate complicated illumination interference (CII) and capture high-level modalitywise assimilation information (MAI) from HS and LiDAR data simultaneously. Notably, the geological connection between these two RS modalities is emphasized in MAMInet II, making the joint classification framework interpretable. Specifically, MAMInet II presents one channelwise illumination removal mechanism by simulating real-world illumination conditions and associating HS spectral curves with LiDAR elevations. One generative switching mechanism contributes to closing the cross-modal RS distribution gap and enhancing the cross-modal capturing ability. These mechanisms are extended to multiscale and multistage versions for aligning local and global RS properties. Experiments illustrate that MAMInet II outperforms several state-of-the-art techniques qualitatively and quantitatively. All source codes are available athttps://github.com/weixinttt/MAMInet-II.

Efficient and secure group writing plays a crucial role in RFID-enabled multi-task backscatter systems. The prior works lay emphasis on the time efficiency of the group data transmission, but neglect its security. This paper is devoted to providing anonymous group writing. We propose the Overlapped Bloom Filter-based protocol (OBF) and its enhanced version (OBF+). The core is to construct an approximately random sequence as a noise by making transmission data for different tag groups overlap with each other, thus hiding the original information with a low computational complexity. The compact filter can guarantee the time efficiency while improving the security of the group writing. To make tags aware of the correctness of the decoded group data, the OBF+ introduces the complementary code-based check mechanism to eliminate the fault data. We prototype the system with USRP and programmable WISP tags, and conduct extensive simulations to evaluate our approaches in terms of the time efficiency, the accuracy, and the anonymity of the data transmission.

Data stream processing holds great potential value in lots of practical application scenarios. This paper studies two new but important patterns for items in data streams, called promising and damping items. The promising items mean that the frequencies of an item in multiple continuous time windows show an upward trend overall, while a slight decrease in some of these windows is allowed. In contrast to promising items exhibiting an increasing trend, the definition of damping items indicates a decreasing trend. Many applications can benefit from the property of promising or damping items, e.g., monitoring latent attacks in computer networks, pre-adjusting bandwidth allocation in communication channels, detecting potential hot events/news, or finding topics that gradually lose momentum in social networks. We first introduce how to accurately find promising items in data streams in real-time under limited memory space. To this end, we propose a novel structure named Scout Sketch, which consists of Filter and Finder. Filter is devised based on the Bloom filter to eliminate the ungratified items with less memory overload; Finder records some necessary information about the potential items and detects the promising items at the end of each time window, where we propose some tailor-made detection operations. We then enhance Scout Sketch (called Scout Sketch+) to adaptively detect both types of promising and damping items simultaneously. Finally, we conducted extensive experiments on four real-world datasets, which show that the F1 Score and throughput of Scout Sketch(+) are about 2.02 and 5.61 times that of the compared solutions. All source codes are available at Github (https://github.com/Aoohhh/ScoutSketch).

To approach the challenges of non-IID data and limited communication resource raised by the emerging federated learning (FL) in mobile edge computing (MEC), we propose an efficient framework, calledFedMigr, which integrates a deep reinforcement learning (DRL) based model migration strategy into the pioneer FL algorithmFedAvg. According to the data distribution and resource budgets, ourFedMigrwill intelligently guide one client to forward its local model to another client after local updating, before directly sending the local models to the server for global aggregation as inFedAvg. Intuitively, migrating a local model from one client to another is equivalent to training the model over more data from different clients, alleviating the influence of non-IID issue. To this end, we propose an experience-driven method to make proper decisions for model migrations while satisfying the resource constraints. We also prove thatFedMigrcan help to reduce the parameter divergences between different local models and the global model from a theoretical perspective under the non-IID setting. Extensive experiments on three popular benchmark datasets demonstrate thatFedMigrcan achieve an average accuracy improvement of around 13%, and reduce bandwidth consumption for global communication by 42% on average, compared with the baselines.

Federated Learning (FL) is a distributed model training framework that allows multiple clients to collaborate on training a global model without disclosing their local data in edge computing (EC) environments. However, FL usually faces statistical heterogeneity (e.g., non-IID data) and system heterogeneity (e.g., computing and communication capabilities), resulting in poor model training performance. To deal with the above two challenges, we propose an efficient FL framework, named FedBR, which integrates the idea of block-wise regularization and knowledge distillation (KD) into the pioneering FL algorithm FedAvg, for resource-constrained edge computing. Specifically, we first divide the model into multiple blocks according to the layer order of deep neural network (DNN). The server only sends some consecutive model blocks instead of an entire model to clients for communication efficiency. Then, the clients make use of knowledge distillation to absorb the knowledge of global model blocks to alleviate statistical heterogeneity during local training. We provide a theoretical convergence guarantee for FedBR and show that the convergence bound will decrease as the increasing number of model blocks sent by the server. Besides, since the increasing number of model blocks brings more computing and communication costs, we design a heuristic algorithm (GMBS) to determine the appropriate number of model blocks for clients according to their varied data distributions, computing, and communication capabilities. Extensive experimental results show that FedBR can reduce the bandwidth consumption by about 31%, and achieve an average accuracy improvement of around 5.6% compared with the baselines under heterogeneous settings.

With the increase in both the model size and dataset size of distributed training (DT) tasks, communication between the workers and parameter servers (PSs) in a cluster has become a bottleneck. In-network aggregation (INA) enabled by programmable switches has been proposed as a promising solution to alleviate the communication bottleneck. However, existing works focused on in-network aggregation implementation based on simple DT placement and fixed routing policies, which may lead to a large communication overhead and inefficient use of resources (e.g., storage, computing power and bandwidth). In this paper, we propose PARING, the first-of-its-kind INA approach that jointly optimizes DT task placement and routing in order to reduce traffic volume and minimize communication time. We formulate the problem as a nonlinear multi-objective mixed-integer programming problem, and prove its NP-Hardness. Based on the concept of Steiner trees, an algorithm with bounded approximation factors is proposed for this problem. Large-scale simulations show that our algorithm can reduce communication time by up to 81.0% and traffic volume by up to 19.1% compared to the state-of-the-art algorithms.

In a commercial cloud, service providers (e.g., video streaming service provider) rent resources from cloud vendors (e.g., Google Cloud Platform) and provide services to cloud users, making a profit from the price gap. Cloud users acquire services by forwarding their requests to corresponding servers. In practice, as a common scenario, traffic dynamics will cause server overload or load-unbalancing. Existing works mainly deal with the problem by two methods: elastic resource provisioning and request updating. Elastic resource provisioning is a fast and agile solution but may cost too much since service providers need to buy extra resources from cloud vendors. Though request updating is a free solution, it will cause a significant delay, resulting in a bad users’ QoS. In this paper, we present a new scheme, called real-time request updating with elastic resource provisioning (TRUST), to help service providers pay less cost with users’ QoS guarantee in clouds. In addition, we propose an efficient algorithm for TRUST with a bounded approximation factor based on progressive-rounding. Both small-scale experiment results and large-scale simulation results show the superior performance of our proposed algorithm compared with state-of-the-art benchmarks.

Submodular maximization has wide applications in machine learning and data mining, where massive datasets have brought the great need for designing efficient and parallelizable algorithms. One measure of the parallelizability of a submodular maximization algorithm is its adaptivity complexity, which indicates the number of sequential rounds where a polynomial number of queries to the objective function can be executed in parallel. In this paper, we study the problem of non-monotone submodular maximization subject to a knapsack constraint, and propose the first combinatorial algorithm achieving an (8+epsilon)-approximation under O(log n) adaptive complexity, which is optimal up to a factor of O(loglog n). Moreover, under slightly larger adaptivity, we also propose approximation algorithms with nearly optimal query complexity of O(n), while achieving better approximation ratios. We show that our algorithms can also be applied to the special case of submodular maximization subject to a cardinality constraint, and achieve performance bounds comparable with those of state-of-the-art algorithms. Finally, the effectiveness of our approach is demonstrated by extensive experiments on real-world applications.

Spread estimation is an essential issue in high-speed networks with wide applications, such as network billing, quality of service, anomaly detection, etc. As a promising technique, sketch can efficiently estimate per-flow spread with only a small memory cost. Many studies focus on improving the performance of sketches. However, these works primarily focus on optimizing the counter level or sketch level without considering the scenario of multi-spread estimation, which is crucial for improving memory utilization and detecting anomalies. In this paper, we propose an efficient flow information compression algorithm based on the on-chip/off-chip hybrid framework to estimate multiple flow spreads. In the on-chip memory, we filter out non-duplicates and sample them to the off-chip space for recording. In the off-chip memory, we compress each sampled non-duplicate to a carefully designed bit-cube. When the measurement is finished, we separate corresponding KV-flows from a specific flow based on the user query. Then, we rebuild this flow to a subset group based on the duplicate number of each KV-flow. Finally, according to the Multi-set theory, we derive an accurate multi-spread estimate formula to solve this issue with a high throughput and small on-chip memory usage. Furthermore, we evaluate the performance of our proposed estimator using real Internet traffic traces downloaded from CAIDA. Experiments show that, compared to the state-of-the-art, our proposal achieves a 97.2% lower average relative error in per-destination source flow spread estimation with a tight on-chip memory, e.g., 320KB. And our proposed method achieves 31.86 higher processing throughput.

Cardinality estimation is a fundamental problem with diverse practical applications. HyperLogLog (HLL) has become a standard in practice because it offers good memory efficiency, constant update time, and mergeability. Some recent work achieved better memory efficiency, but typically at the cost of impractical update time or losing mergeability, making them incompatible with applications like network-wide traffic measurement. This work presents SpikeSketch, a better cardinality estimator that reduces memory usage of HLL by 37% without sacrificing other crucial metrics. We adopt a bucket-based data structure to promise constant update time, design a smoothed log4ranking and a spike coding scheme to compress cardinality observables into buckets, and propose a lightweight mergeable lossy compression to balance memory usage, information loss, and mergeability. Then we derive an unbiased estimator for recovering cardinality from the lossy-compressed sketch. Theoretical and empirical results show that SpikeSketch can work as a drop-in replacement for HLL because it achieves a near-optimal MVP (memory-variance-product) of 4.08 (37% smaller than HLL) with constant update time and mergeability. Its memory efficiency even defeats ACPC and HLLL, the state-of-the-art lossless-compressed sketches using linear-time compression to reduce memory usage.

Multi-Armed Bandit (MAB) that solves the sequential decision-making to the prior-unknown settings has been extensively studied and adopted in various applications such as online recommendation, transmission rate allocation, etc. Although some recent work has investigated the multi-agent MAB model, they supposed that agents share their bandit information based on social networks but neglected the incentives and arm-pulling budget for heterogeneous agents. In this paper, we propose a transaction-based multi-agent MAB framework, where agents can trade their bandit experience with each other to improve their total individual rewards. Agents not only face the dilemma between exploitation and exploration, but also decide to post a suitable price for their bandit experience. Meanwhile, as a buyer, the agent accepts another agent whose experience will help her the most, according to the posted price and her risk-tolerance level. The key challenge lies in that the arm-pulling and experience-trading decisions affect each other. To this end, we design the transaction-based upper confidence bound to estimate the prior-unknown rewards of arms, based on which the agents pull arms or trade their experience. We prove the regret bound of the proposed algorithm for each independent agent and conduct extensive experiments to verify the performance of our solution.

Accurate and fast per-flow size traffic measurement is fundamental to some network applications, e.g., load balancing, anomaly detection, traffic engineering, especially in face of the processing and memory constraints of switches. Sketch, a compact data structure, can output high-fidelity approximate perflow statistics. However, most existing sketches such as Count-Min are trapped in the dilemma between a large counting range and memory waste, due to the highly skewed characteristics of traffic size distribution. In this paper, we propose an adaptive counter-splicing-based sketch for per-flow size measurement. Specifically, we first allocate a small number of bits for each counter to handle mouse flows, and then splice several basic counters on the same layer to satisfy the counting range requirement for elephant flows. Extensive experiments based on real-world datasets CAIDA show that our proposed sketch can achieve better estimation performance in per-flow size estimation, flow size distribution, entropy estimation, heavy hitter detection, and heavy change detection, compared to several existing algorithms.

With 30 billion RFID tags sold worldwide in 2021, a common basic functionality needed by RFID-enabled applications is cardinality estimation --- to quickly estimate the number of distinct tags in an RFID system. Although many advanced solutions have been proposed over the past decade, they suffer from one major limitation in practical use: they need to either modify the existing RFID standard or obtain MAC-layer information, both of which however cannot be supported by commercial off-the-shelf (COTS) devices. In this paper, we revisit the counting problem and propose a novel counting scheme called average time duration based counter (ATD) that quickly estimates the number of distinct tags in a standards-compliant manner. Compared with existing work, the competitive advantage of ATD is that it can be directly deployed on a COTS RFID system, with no need for any hardware modifications. In ATD, we found a new and measurable indicator --- the time duration between two adjacent singleton slots, which depends on the number of tags. Following this observation, we derive the theoretical relationship between the time indicator and the number of tags and then give the proof of the estimation as well as its parameter settings. Additionally, we propose a flag-flipping solution to address the overlapping problem in the multi-reader case. We implement ATD in a COTS RFID system with 1000 tags. Experimental results show that ATD is 4.2× faster than the baseline of tag inventory; the performance gain will be further increased in a larger RFID system.

We revisit the classical problem of designing Budget-Feasible Mechanisms (BFMs) for submodular valuation functions, which has been extensively studied since the seminal paper of Singer [FOCS’10] due to its wide applications in crowdsourcing and social marketing. We propose TripleEagle, a novel algorithmic framework for designing BFMs, based on which we present several simple yet effective BFMs that achieve better approximation ratios than the state-of-the-art work for both monotone and non-monotone submodular valuation functions. Moreover, our BFMs are the first in the literature to achieve linear complexities while ensuring obvious strategyproofness, making them more practical than the previous BFMs. We conduct extensive experiments to evaluate the empirical performance of our BFMs, and the experimental results strongly demonstrate the efficiency and effectiveness of our approach.

The problem of constrained subset selection from a large data stream for profit maximization has many applications in web data mining and machine learning, such as social advertising, team formation and recommendation systems. Such a problem can be formulated as maximizing a regularized submodular function under certain constraints. In this paper, we consider a generalized k-system constraint, which captures various requirements in real-world applications. For this problem, we propose the first streaming algorithm with provable performance bounds, leveraging a novel multitudinous distorted filter framework. The empirical performance of our algorithm is extensively evaluated in several applications including web data mining and recommendation systems, and the experimental results demonstrate the superiorities of our algorithm in terms of both effectiveness and efficiency.

A lot of applications in web economics need to maximize the revenue under a budget for payments and also guarantee the truthfulness of users, so Budget-Feasible Mechanism (BFM) Design has aroused great interests during last decade. Most of the existing BFMs concentrate on maximizing a monotone submodular function subject to a knapsack constraint, which is insufficient for many applications with complex objectives or constraints. Observing this, the recent studies (e.g., [4, 5, 11]) have considered non-monotone submodular objectives or more complex constraints such as a k-system constraint. In this study, we follow this line of research and propose truthful BFMs with improved performance bounds for non-monotone submodular objectives with or without a k-system constraint. Our BFMs leverage the idea of providing random prices to users while deferring the decision on the final winning set, and are also based on a novel randomized algorithm for the canonical constrained submodular maximization problem achieving better performance bounds compared to the state-of-the-art. Finally, the effectiveness and efficiency of our approach are demonstrated by extensive experiments on several applications about social network marketing, crowdsourcing and personalized recommendation.

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.

In multimodal data fusion and land-cover interpretation tasks, the fusion interpretability between hyperspectral image (HSI) and light detection and ranging (LiDAR) data is always nontrivial to be clarified. Furthermore, the heterogeneous sample and distribution variances of these two remote sensing (RS) modalities impede the joint classification performance. In this paper, a Hyperspectral Intrinsic Image Decomposition guided Data Fusion Network (HI2D2FNet) is proposed. Generally, classic hyperspectral intrinsic image decomposition (HIID) performs well in image enhancement and shadow removal. It decomposes one HSI into one reflectance component and one shading component. Inspired by the core mechanism of HIID, our motivation is to preliminarily exploit its potential for multimodal RS data fusion and explore the inherent modality connection between HSI and LiDAR data from the intrinsic perspective. Specifically, compared with existing techniques, HI2D2FNet is capable of fusing the horizontal geometry information in the shading component with the vertical geometry information in the LiDAR data from both sample and distribution perspectives in the spatial domain. The generated cross-modal geometry feature contributes to guiding the reflectance stream optimization. This unique fusion framework connects both modalities with respect to geometry information and enhances the specific fusion interpretability. The decomposition and fusion modules in HI2D2FNet are optimized simultaneously in a novel alternative optimization pattern. Furthermore, several unique cross-modal constraints in terms of prior RS properties are presented. Experiments conducted on three widely available datasets prove the superiority of HI2D2FNet over state-of-the-art techniques. The source codes will be available at https://github.com/GEOywb/HI2D2FNet.

Remote sensing (RS) modalities from multi-sensor platforms, including hyperspectral (HS) and light detection and ranging (LiDAR) data, have been garnering increasing attention in overcoming the lack of information diversity. However, the specific modality correlation is always weakened and neglected. By reducing the spectral uncertainty, hyperspectral intrinsic image decomposition (HIID) has been proven to be effective in enhancing the HS image quality. It is an ill-posed problem and is challenged to capture the inherent modality connection. This paper proposes a shadow mask driven multimodal intrinsic image decomposition (smMIID) for HS and LiDAR data fusion. Notably, smMIID creatively clarifies and activates the potential of the crossmodal information in RS modalities and builds on the strength of the LiDAR elevation information when constructing HIID constraints. Our motivation is to overcome the deficiency of information diversity and modality correlation in existing IID based frameworks for better data fusion performance. Classic IID methods decompose the HS image into one reflectance component (RC) and one shading component (SC). There are three constraints in smMIID: 1) the fundamental constraint on RC and SC, 2) the HS-LiDAR hybrid gradient based constraint on RC and 3) the LiDAR gradient based constraint on SC. A shadow mask is obtained and utilized to guarantee spectral consistency when combining neighboring samples. Experiments on HS and LiDAR datasets prove that smMIID outperforms other techniques in terms of visualization and classification. The analyses are provided theoretically and experimentally to demonstrate that smMIID is robust to shadow mask generation.

The multi-armed bandit (MAB) models have always received lots of attention from multiple research communities due to their broad application domains. The optimal selection problem with unknown rewards in advance, such as ad recommendation in social networks, spectrum access in the cognitive radio field, etc., can be efficiently solved by using MAB models. In an MAB model, given$N$arms whose rewards are unknown in advance, the player selects exactly one arm in each round, and his goal is to maximize the cumulative rewards over a fixed horizon. Further, a more general model called combinatorial MAB (i.e., CMAB), where$K$arms can be played simultaneously in each round, is put forward. However, the existing CMAB models neglect the strategic behaviors of the$N$arms, which indicates that one arm might report false information to increase its own profits. In fact, in many applications such as user selection in crowdsensing, the arms are not the feelingless machines but the rational individuals. To this end, we combine the upper confidence bound (UCB) with auction theory to develop a new algorithm called auction-based UCB (AUCB). We divide the auction-based CMAB problem into two sub-problems: winning arm selection and payment computation problems. For AUCB, we derive an upper bound on regret and prove the truthfulness in one round, individual rationality, and computational efficiency. In addition, we consider an extended situation that some arms may be unavailable in some rounds and the arms will bid inconsistently in different rounds. We devise another algorithm called eAUCB to solve this problem. Extensive simulations are conducted to show the significant performance of the proposed algorithms.

Federated learning (FL) has been widely adopted to train machine learning models over massive data in edge computing. However, machine learning faces critical challenges, e.g., data imbalance, edge dynamics, and resource constraints, in edge computing. The existing FL solutions cannot well cope with data imbalance or edge dynamics, and may cause high resource cost. In this paper, we propose an adaptive asynchronous federated learning (AAFL) mechanism. To deal with edge dynamics, a certain fraction$\alpha$of all local updates will be aggregated by their arrival order at the parameter server in each epoch. Moreover, the system can intelligently vary the number of local updated models for global model aggregation in different epochs with network situations. We then propose experience-driven algorithms based on deep reinforcement learning (DRL) to adaptively determine the optimal value of$\alpha$in each epoch for two cases of AAFL, single learning task and multiple learning tasks, so as to achieve less completion time of training under resource constraints. Extensive experiments on the classical models and datasets show high effectiveness of the proposed algorithms. Specifically, AAFL can reduce the completion time by about 70 percent and improve the learning accuracy by about 28 percent under resource constraints, compared with the state-of-the-art solutions.

Multi-access edge computing achieves better application responsiveness by offloading tasks from end devices to edge servers installed at the vicinity. Practical scenarios, such as post-disaster rescuing and battlefield monitoring, make it attractive to use end devices themselves as edge servers. This, however, introduces a new challenge: Due to mobility and power limitation, the set of edge servers becomes dynamic. As some servers fail, the tasks that run on them will also fail. This paper introduces a new dynamic edge computing model and conducts the first study on robust task offloading which is tolerant to$h$server failures. We propose online primal-dual algorithms that offload tasks as they arrive. We evaluate the performance of our robust task offloading solutions through extensive simulations based on real task sets. The results show that our proposed solutions can well handle edge dynamics and achieve near optimal throughput (above 95 percent) compared to the optimal offline benchmark algorithm.

Federated learning (FL) has emerged in edge computing to address the limited bandwidth and privacy concerns of traditional cloud-based training. However, the existing FL mechanisms may lead to a long training time and consume massive communication resources. In this paper, we propose an efficient FL mechanism, namely FedCH, to accelerate FL in heterogeneous edge computing. Different from existing works which adopt the pre-defined system architecture and train models in a synchronous or asynchronous manner, FedCH will construct a special cluster topology and perform hierarchical aggregation for training. Specifically, FedCH arranges all clients into multiple clusters based on their heterogeneous training capacities. The clients in one cluster synchronously forward their local updates to the cluster header for aggregation, while all cluster headers take the asynchronous method for global aggregation. Our analysis shows that the convergence bound depends on the number of clusters and the training epochs. We propose efficient algorithms to determine the optimal number of clusters with resource budgets and then construct the cluster topology to address the client heterogeneity. Extensive experiments on both physical platform and simulated environment show that FedCH reduces the completion time by 49.5-79.5% and the network traffic by 57.4-80.8%, compared with the existing FL mechanisms.

Complex-valued limited-memory BFGS (CL-BFGS) algorithm is efficient for the training of complex-valued neural networks (CVNNs). As an important parameter, the memory size represents the number of saved vector pairs and would essentially affect the performance of the algorithm. However, the determination of a suitable memory size for the CL-BFGS algorithm remains challenging. To deal with this issue, an adaptive method is proposed in which the memory size is allowed to vary during the iteration process. Basically, at each iteration, with the help of multistep quasi-Newton method, an appropriate memory size is chosen from a variable set {1,2, ... , M} by approximating complex Hessian matrix as close as possible. To reduce the computational complexity and ensure desired performance, the upper bound M is adjustable according to the moving average of memory sizes found in previous iterations. The proposed adaptive CL-BFGS (ACL-BFGS) algorithm can be efficiently applied for the training of CVNNs. Moreover, it is suggested to take multiple memory sizes to construct the search direction, which further improves the performance of the ACL-BFGS algorithm. Experimental results on some benchmark problems including the pattern classification, complex function approximation, and nonlinear channel equalization problems are given to illustrate the advantages of the developed algorithms over some previous ones.

Per-flow traffic measurement in the high-speed network plays an important role in many practical applications. Due to the limited on-chip memory and the mismatch between off-chip memory speed and line rate, sampling-based methods select and forward a part of flow traffic to off-chip memory, which complements sketch-based solutions in estimation accuracy and online query support. However, most current work uses the same sampling probability for all flows, leading to the waste in storage and communication resources. In practice, different flows often require different sampling rates to meet the same accuracy constraint. This paper presents self-adaptive sampling, a framework to sample each flow with a probability adapted to flow size/spread. Then we propose three algorithms, SAS-LC, SAS-LOG, and SAS-HYB. SAS-LC and SAS-LOG are geared towards per-flow spread estimation and per-flow size estimation by using different compression functions. SAS-HYB combines the advantages of SAS-LC and SAS-LOG, showing higher efficiency when both small flows and large flows are interested. We implement our estimators in hardware using NetFPGA. Experimental results based on real Internet traces show that, compared to the state-of-the-art in per-flow spread estimation, SAS-LC can save around 10% on-chip space and reduce up to 40% communication cost for large flows. In per-flow size estimation, SAS-LOG can save 40% on-chip space and reduce up to 96% communication costs for large flows. Moreover, SAS-HYB’s on-chip memory usage will not be larger than SAS-LC or SAS-LOG and can save up to 19% on-chip space than SAS-LOG when both small flows and large flows are interested.

As a simple and low-cost way to obtain enough computing resources, more and more tenants migrate their tasks to the cloud. However, the frequent occurrence of abnormal events (e.g., malicious tenants and node failures) in the cloud will seriously affect the tenants’ QoS. Conventionally, the cloud vendors reduce the frequency of abnormal events by deploying auxiliary systems, which requires additional costs and increases network complexity. Considering that it is an unrealistic expectation to eliminate the occurrence of abnormal events in clouds, this paper proposes a complementary scheme to alleviate the negative impact scope when an abnormal event occurs through multi-constrained VM placement without consuming additional resources. Specifically, when deploying VMs, we limit the number of pods (or service nodes) each tenant can access and the number of tenants hosted by each pod (or service node). However, the multi-dimensional interaction among numerous system parameters and performance/resource considerations makes the problem of multi-constrained VM placement for alleviating the impact of abnormal events very challenging. To solve this problem, we formulate an integer linear programming and propose a rounding-based algorithm with a logarithmic approximation ratio. We implement our proposed algorithm on a physical testbed. The experimental and simulation results show the high efficiency of the proposed algorithm. For example, our algorithm reduces the impact scope of service node failure by 60%, the impact scope of malicious tenants by 40%, and the tenant task makespan by 25% compared with other alternatives.

Blockchain came to prominence as the distributed ledger underneath Bitcoin, which protects the transaction histories in a fully-connected, peer-to-peer network. The blockchain mining process requires high computing power to solve a Proof-of-Work (PoW) puzzle, which is hard to implement on users’ mobile devices. So these miners may leverage the edge/cloud service providers (ESPs/CSP) to calculate the PoW puzzle. The existing edge-assisted blockchain networks assumed that all ESPs have a uniform propagation delay, which is unrealistic. In this article, we consider a more practical scene where ESPs locate in diverse positions of the blockchain network, which causes different propagation delays when supporting the computation of the PoW puzzle. Additionally, these ESPs connect to a remote CSP for resource scheduling when the computing tasks exceed their maximum capacity. The blockchain mining process generally involves complicated competition and games among CSP, ESPs, and miners. Each service provider focuses on how to determine his resource price so that he can maximize his utility. According to the set resource price, each miner concentrates on scheduling his resource requests for each ESP to maximize individual personal utility, which depends on ESPs’ resource price and propagation delays. We first model such a resource pricing and scheduling problem as a three-stage multi-leader multi-follower Stackelberg game and aim at finding the Stackelberg equilibrium. Then, we analyze the subgame optimization problem in each stage and propose an iterative algorithm based on backward induction to achieve the Nash equilibrium of the Stackelberg game. Finally, extensive simulations are conducted to verify the significant performance of the proposed solution.

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.

To approach the challenges of non-IID data and limited communication resource raised by the emerging federated learning (FL) in mobile edge computing (MEC), we propose an efficient framework, called FedMigr, which integrates a deep reinforcement learning (DRL) based model migration strategy into the pioneer FL algorithm FedAvg. According to the data distribution and resource constraints, our FedMigr will intelligently guide one client to forward its local model to another client after local updating, rather than directly sending the local models to the server for global aggregation as in FedAvg. Intuitively, migrating a local model from one client to another is equivalent to training it over more data from different clients, contributing to alleviating the influence of non-IID issue. We prove that FedMigr can help to reduce the parameter divergences between different local models and the global model from a theoretical perspective, even over local datasets with non-IID settings. Extensive experiments on three popular benchmark datasets demonstrate that FedMigr can achieve an average accuracy improvement of around 13%, and reduce bandwidth consumption for global communication by 42% on average, compared with the baselines.

Detecting heavy hitters that constitute the majority of network traffic is a critical task in network measurement. However, the highly skewed network traffic and the size-limited on-chip memory pose great challenges for heavy-hitter detection. The prior arts either use sketches to track all flows or maintain a fix-sized tracking list for recording elephant flows, resulting in limited detection precision or time-consuming tracking list exchanges. This paper presents HeavyTracker, an efficient algorithm that detects heavy hitters based on a count-with-threshold strategy. A two-dimensional tracker unit array is employed in our design to capture the heavy hitters, where each flow is randomly mapped to one unit in all rows. The tracker unit is designed to accept many flows and precisely report the largest two with frequencies that reach a predefined threshold. This design eliminates the frequent and time-consuming exchanges for maintaining the tracking list, allowing us to use a hash table to track the reported elephant flows. Experimental results based on real Internet traces show that HeavyTracker achieves a high $\mathbf{F}_{\beta}$-Score of threshold-t detection (0.97) and over 99% precision of top-k detection under a tight memory size. Besides, it reduces the frequency estimation error by 97.4% compared to the state-of-the-art.

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.

In a commercial cloud, service providers (e.g., video streaming service provider) rent resources from cloud vendors (e.g., Google Cloud Platform) and provide services to cloud users, making a profit from the price gap. Cloud users acquire services by forwarding their requests to corresponding servers. In practice, as a common scenario, traffic dynamics will cause server overload or load-unbalancing. Existing works mainly deal with the problem by two methods: elastic resource provisioning and request updating. Elastic resource provisioning is a fast and agile solution but may cost too much since service providers need to buy extra resources from cloud vendors. Though request updating is a free solution, it will cause a significant delay, resulting in a bad users’ QoS. In this paper, we present a new scheme, called real-time request updating with elastic resource provisioning (TRUST), to help service providers pay less cost with users’ QoS guarantee in clouds. In addition, we propose an efficient algorithm for TRUST with a bounded approximation factor based on randomized rounding. Both small-scale experiment results and large-scale simulation results show the superior performance of our proposed algorithm compared with state-of-the-art benchmarks.

Per-flow size measurement is a fundamental problem in network engineering and plays a pivotal role in many practical applications. Constrained by on-chip memory resources and packet processing speed, most existing solutions use compact data structures (i.e., sketches) to perform the line-speed measurement. However, sketches share the record units (bits/counters) among flows, inevitably introducing noises to each flow’s measurement result. Although they adopt an average denoising strategy to remove noises from the raw estimations, the accuracy for medium flows is still lacking. This paper complements the prior art and presents a novel per-flow size measurement method, Adaptive Denoising (ADN), which can provide more accurate estimates for online and offline queries. For an online query, we use the collected flow records for real-time estimation. For an offline query, we model the propagation of noises based on the optimization algorithm to produce flow size estimation with much better accuracy. Experimental results based on real Internet traffic traces show that our measurement solutions outperform the state-of-the-art approaches and reduce the mean absolute error by around one order of magnitude under the same on-chip memory usage.

Chromatic Correlation Clustering (CCC) (introduced by Bonchi et al. [6]) is a natural generalization of the celebrated Correlation Clustering (CC) problem, introduced by Bonchi et al. [6]. It models objects with categorical pairwise relationships by an edge-colored graph, and has many applications in data mining, social networks and bioinformatics. We show that there exists a $2.5$-approximation to the CCC problem based on a Linear Programming (LP) approach, thus improving the best-known approximation ratio of 3 achieved by Klodt et al. [21] . We also present an efficient heuristic algorithm for CCC leveraging a greedy clustering strategy, and conduct extensive experiments to demonstrate the effectiveness and efficiency of our proposed algorithm.

In Mobile Edge Computing (MEC), users' traffic needs to traverse a set of service functions in a specific order, referred to as a service function chain (SFC), to complete service requests. Thus, SFC routing is an essential issue in MEC. In practice, user mobility and resource limitation are two critical challenges of SFC routing in MEC. However, the previous works either ignore the user mobility or resource limitation, especially the flow-table resources, leading to high transmission latency and resource overhead. In this paper, we study the mobility-aware service function chain routing in MEC. We design an SFC routing scheme called MASCOT to address the above challenges. MASCOT implements SFC routing through three steps: user location prediction, routing path decision, and packet forwarding. For user location prediction, we adopt the order-K Markov prediction method to predict users' next accessed base station. For routing path decision, we formulate the SFC routing selection (SRS) problem, which respects the resource constraints. We propose a primal-dual online SFC routing algorithm (POSR) for the SRS problem and prove that POSR can achieve good competitiveness. For packet forwarding, we propose a forwarding scheme based on segment routing to address the resource limitation challenge further. Extensive simulation results show that our scheme can improve the system throughput by about 40% compared with the state-of-the-art approaches.

Hyperspectral images (HSIs) provide abundant high-quality spectral information through an immense number of spectral channels, which can be used to classify on-ground objects for Earth observation accurately. However, these highly correlated channels and complex informative features always limit the application of HSIs. In this letter, we propose a multilevel dual-direction modifying variational autoencoder (MD2MVAE) for hyperspectral feature extraction. Its architecture is inspired by the spectral–spatial coherence in HSIs. Our motivation is to modify spectral sequential features by spatial sequential features in a multilevel dual-direction network. The dual-direction strategy has two implications: 1) the spatial continuity is captured by flattening neighboring samples in dual classic directions and 2) the spectral–spatial continuities are captured in the forward and backward directions. This multilevel dual-direction network provides a feasible way to avoid the loss of spatial information when flattening samples in the spatial domain, without using any convolutional layers. Inspired by our previous work, a variational autoencoder (VAE)-based network is used to enhance the noise immunity of latent features. To preserve the consistency of spectral–spatial sequential features, a combined loss function based on the solid angle on a unit sphere is proposed for parameter optimization. Two typical datasets are selected as benchmarks to show the effectiveness of MD2MVAE, compared with the state-of-the-art methods.

Tridimensional empirical mode decomposition (TEMD) has been successfully employed as a powerful tool for hyperspectral classification. It achieves good performance to analyze nonlinear/non-stationary data and capture abstract features of hyperspectral images (HSIs). However, the major challenge is how to adequately exploit and balance decomposed edge-wise (EW) and trend-wise (TW) features. To address this issue, we propose an accelerated adaptive feature balance technique (A2FBT) based on TEMD. Due to complex discriminant information, A2FBT initially decomposes the HSI into varying oscillations adequately, including several tridimensional intrinsic mode functions (TIMFs) and one residual (RES). They contain high frequency EW and low frequency TW features, respectively. To further accelerate the decomposition, a k-d tree based search strategy is proposed for filter size selection. To bridge the gaps between the RES and all TIMFs, a novel adaptive feature balance strategy is presented by assigning adaptive trade-offs. We aim to balance multiple features adequately according to the intrinsic discriminant information. A combined metric based strategy is provided for trade-off calculation, measuring the mutual similarities between oscillations comprehensively. A2FBT pays more attention to these similarities, reinforcing the respective contributions of EW and TW features. Experiments on four typical hyperspectral datasets illustrate the effectiveness of A2FBT compared with several state-of-the-art techniques.

Intelligent vehicular cyber-physical systems can perform automatic traffic measurement, which provides critical information for transportation engineering. However, one of the biggest challenges in traffic measurement is to protect the vehicles’ location and trajectory privacy, which may be revealed from the recorded traffic data. Prior studies in traffic measurement only offer heuristic privacy protection but lack a precisely defined privacy model. This article proposes an efficient traffic estimator with differential privacy protection. In our design, each road-side unit communicates with the passing vehicles and records their presence in a privacy-preserving data structure. By performing probabilistic analysis on the anonymized records, the proposed method can precisely estimate the number of common vehicles passed by multiple given locations during the given measurement period. Through theoretical analysis, we prove that the proposed method can protect the trajectory privacy of the vehicles with$\epsilon$-differential privacy even when the point privacy has been leaked. We also evaluated our traffic estimator based on a real-world transportation traffic dataset. The evaluation results demonstrate that the proposed estimator can achieve high estimation accuracy and high-level privacy protection through controllable tradeoffs.

Under the paradigm of edge computing, the enormous data generated at the network edge can be processed locally. To make full utilization of these widely distributed data, we focus on an edge computing system that conducts distributed machine learning using gradient-descent based approaches. To ensure the system’s performance, there are two major challenges: how to collect data from multiple data source nodes for training jobs and how to allocate the limited resources on each edge server among these jobs. In this paper, we jointly consider the two challenges for distributed training (without service requirement), aiming to maximize the system throughput while ensuring the system’s quality of service (QoS). Specifically, we formulate the joint problem as a mixed-integer non-linear program, which is NP-hard, and propose an efficient approximation algorithm. Furthermore, we take service placement into consideration for diverse training jobs and propose an approximation algorithm. We also analyze that our proposed algorithm can achieve the constant bipartite approximation under many practical situations. We build a test-bed to evaluate the effectiveness of our proposed algorithm in a practical scenario. Extensive simulation results and testing results show that the proposed algorithms can improve the system throughput 56-69 percent compared with the conventional algorithms.

Mobile crowdsensing, through which a requester can coordinate a crowd of workers to complete some sensing tasks, has attracted significant attention recently. In this paper, we focus on the unknown worker recruitment problem in mobile crowdsensing, where workers’ sensing qualities are unknown a priori. We consider the scenario of recruiting workers to complete some continuous sensing tasks. The whole process is divided into multiple rounds. In each round, every task may be covered by more than one recruited workers, but its completion quality only depends on these workers’ maximum sensing quality. Each recruited worker will incur a cost and each task is attached a weight to indicate its importance. Our objective is to determine a recruiting strategy to maximize the total weighted completion quality under a limited budget. We model such unknown worker recruitment process as anovel combinatorial multi-armed bandit(CMAB) problem, and propose an unknown worker recruitment algorithm based on the modified upper confidence bound (UCB). Moreover, we extend the problem to the case where the workers’ costs are also unknown and design the corresponding algorithm. We analyze the regret bounds of the two proposed algorithms through rigorous proofs. In addition, we also study the unknown worker recruitment problem with fairness constraints. Here, the term “fairness” means that the platform must guarantee a minimum selection fraction for each registered worker, so that the platform can avoid the scenario where some workers are over-recruited but some others might be under-recruited. For this problem, we devise a fairness-aware unknown worker recruitment algorithm. Finally, we demonstrate the performance of the proposed algorithms through extensive simulations on real-world traces

In a multi-tenant cloud, cloud vendors provide services (e.g., elastic load-balancing, virtual private networks) on service nodes for tenants. Thus, the mapping of tenants’ traffic and service nodes is an important issue in multi-tenant clouds. In practice, unreliability of service nodes and uncertainty/dynamics of tenants’ traffic are two critical challenges that affect the tenants’ QoS. However, previous works often ignore the impact of these two challenges, leading to poor system robustness when encountering system accidents. To bridge the gap, this paper studies the problem of robust service mapping in multi-tenant clouds (RSMP). Due to traffic dynamics, we take a two-step approach:service node assignmentandtenant traffic scheduling. For service node assignment, we prove its NP-Hardness and analyze its problem difficulty. Then, we propose an efficient algorithm with bounded approximation factors based on randomized rounding and knapsack. For tenant traffic scheduling, we design an approximation algorithm based on fully polynomial time approximation scheme (FPTAS). The proposed algorithm achieves the approximation factor of 2+$\epsilon $, where$\epsilon $is an arbitrarily small value. Both small-scale experimental results and large-scale simulation results show the superior performance of our proposed algorithms compared with other alternatives.

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

Submodular optimization has numerous applications such as crowdsourcing and viral marketing. In this paper, we study the problem of non-negative submodular function maximization subject to a $k$-system constraint, which generalizes many other important constraints in submodular optimization such as cardinality constraint, matroid constraint, and $k$-extendible system constraint. The existing approaches for this problem are all based on deterministic algorithmic frameworks, and the best approximation ratio achieved by these algorithms (for a general submodular function) is $k+2\sqrt{k+2}+3$. We propose a randomized algorithm with an improved approximation ratio of $(1+\sqrt{k})^2$, while achieving nearly-linear time complexity significantly lower than that of the state-of-the-art algorithm. We also show that our algorithm can be further generalized to address a stochastic case where the elements can be adaptively selected, and propose an approximation ratio of $(1+\sqrt{k+1})^2$ for the adaptive optimization case. The empirical performance of our algorithms is extensively evaluated in several applications related to data mining and social computing, and the experimental results demonstrate the superiorities of our algorithms in terms of both utility and efficiency.

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.

Online anomalous taxi trajectory detection, which identifies anomalies from ongoing taxi trajectories, has become an important and fundamental concern in many real-world applications. Most of the existing studies define the anomalous trajectories as the ones deviating from the majority of routes or showing abnormal driving time and distance at the same time. However, due to the complexity of road conditions and the variety of passenger preferences, those methods have large false-positive rates, i.e., reporting many normal routes as anomalies. A high false-positive rate is harmful since false alarms will 1) bring unnecessary panic to passengers, 2) cause fiscally punishments to normal drivers, and 3) wastes human resource to deal with drivers' complaints. To this end, this paper proposes an online anomalous trajectory detection method, namely multidimensional criteria based anomalous trajectory (MCAT), to identify anomalous trajectories online. It judges anomalies by considering multidimensional criteria (similarity, time, distance) at the same time, reducing the false positives without sacrificing false negative rates. We evaluate the proposed method based on the real-world taxi data collected from Shanghai, China. The experimental results demonstrate that our method can outperform state-of-the-art methods in terms of accuracy, false-negative rate, and false-positive rate.

Per-flow traffic measurement in the high-speed network plays an important role in many practical applications. Due to the limited on-chip memory and the mismatch between off-chip memory speed and line rate, sampling-based methods select and forward a part of flow traffic to off-chip memory, complementing sketch-based solutions in estimation accuracy and online query support. However, most current work uses the same sampling probability for all flows, overlooking that the sampling rates different flows require to meet the same accuracy constraint are different. It leads to a waste in storage and communication resources. In this paper, we present self-adaptive sampling, a framework to sample each flow with a probability adapted to flow size/spread. Then we propose two algorithms, SAS-LC and SAS-LOG, which are geared towards per-flow spread estimation and per-flow size estimation by using different compression functions. Experimental results based on real Internet traces show that, when compared to NDS in per-flow spread estimation, SAS-LC can save around 10% on-chip space and reduce up to 40% communication cost for large flows. Moreover, SAS-LOG can save 40% on-chip space and reduce up to 96% communication cost for large flows than NDS in per-flow size estimation.

The multi-armed bandit (MAB) model has been deeply studied to solve many online learning problems, such as rate allocation in communication networks, Ad recommendation in social networks, etc. In an MAB model, given N arms whose rewards are unknown in advance, the player selects exactly one arm in each round, and his goal is to maximize the cumulative rewards over a fixed horizon. In this paper, we study the budget-constrained auction-based combinatorial multi-armed bandit mechanism with strategic arms, where the player can select K (<; N) arms in a round and pulling each arm has a unique cost. In addition, each arm might strategically report its cost in the auction. To this end, we combine the upper confidence bound (UCB) with auction to define the UCB-based rewards and then devise an auction-based UCB algorithm (called AUCB). In each round, AUCB selects the top K arms according to the ratios of UCB-based rewards to bids and further determines the critical payment for each arm. For AUCB, we derive an upper bound on regret and prove the truthfulness, individual rationality, and computational efficiency. Extensive simulations show that the rewards achieved by AUCB are at least 12.49% higher than those of state-of-the-art algorithms.

Federated learning (FL) has emerged in edge computing to address limited bandwidth and privacy concerns of traditional cloud-based centralized training. However, the existing FL mechanisms may lead to long training time and consume a tremendous amount of communication resources. In this paper, we propose an efficient FL mechanism, which divides the edge nodes into K clusters by balanced clustering. The edge nodes in one cluster forward their local updates to cluster header for aggregation by synchronous method, called cluster aggregation, while all cluster headers perform the asynchronous method for global aggregation. This processing procedure is called hierarchical aggregation. Our analysis shows that the convergence bound depends on the number of clusters and the training epochs. We formally define the resource-efficient federated learning with hierarchical aggregation (RFL-HA) problem. We propose an efficient algorithm to determine the optimal cluster structure (i.e., the optimal value of K) with resource constraints and extend it to deal with the dynamic network conditions. Extensive simulation results obtained from our study for different models and datasets show that the proposed algorithms can reduce completion time by 34.8%-70% and the communication resource by 33.8%-56.5% while achieving a similar accuracy, compared with the well-known FL mechanisms.

In a multi-tenant cloud, cloud vendors provide services (e.g., elastic load-balancing, virtual private networks) on service nodes for tenants. Thus, the mapping of tenants' traffic and service nodes is an important issue in multi-tenant clouds. In practice, unreliability of service nodes and uncertainty/dynamics of tenants' traffic are two critical challenges that affect the tenants' QoS. However, previous works often ignore the impact of these two challenges, leading to poor system robustness when encountering system accidents. To bridge the gap, this paper studies the problem of robust service mapping in multi-tenant clouds (RSMP). Due to traffic dynamics, we take a two-step approach: service node assignment and tenant traffic scheduling. For service node assignment, we prove its NP-Hardness and analyze its problem difficulty. Then, we propose an efficient algorithm with bounded approximation factors based on randomized rounding and knapsack. For tenant traffic scheduling, we design an approximation algorithm based on fully polynomial time approximation scheme (FPTAS). The proposed algorithm achieves the approximation factor of 2+ ε , where ε is an arbitrarily small value. Both small-scale experimental results and large-scale simulation results show the superior performance of our proposed algorithms compared with other alternatives.

Currently, the blockchain, as a key enabling technology of digital currency, has attracted lots of attention from both industry and academia. The blockchain mining process requires high computing power to solve a Proof-of-Work (PoW) puzzle, which is hard to implement on users’ mobile devices. So these miners may leverage the resources of the edge/cloud service providers (ESPs/CSP) to calculate the PoW puzzle. The existing edge-assisted blockchain networks simply assumed that all ESPs have a uniform propagation delay, which is not realistic. In this paper, we consider a more practical scene where ESPs with distributed geographic locations have diverse propagation delays when supporting the computation of the PoW puzzle. Additionally, the blockchain mining process generally involves the complicated competition and game among these ESPs and miners. Each ESP focuses on how to determine his resource price and to select the requests from the miners, so that he can maximize his utility. According to the set resource price, each miner concentrates on scheduling his resource requests for each ESP to maximize his individual utility which depends on ESPs’ resource price and propagation delays. We model such a resource pricing and scheduling problem as a multi-leader multi-follower Stackelberg game and aim at finding the joint maximization of the utilities of each ESP and each individual miner. We prove the existence and uniqueness of the Stackelberg equilibrium (SE) and meanwhile propose an algorithm to achieve the corresponding SE. Finally, extensive simulations are conducted to verify the significant performance of the proposed solution.

Federated learning (FL) involves training machine learning models over distributed edge nodes (i.e., workers) while facing three critical challenges, edge heterogeneity, Non-IID data and communication resource constraint. In the synchronous FL, the parameter server has to wait for the slowest workers, leading to significant waiting time due to edge heterogeneity. Though asynchronous FL can well tackle the edge heterogeneity, it requires frequent model transfers, resulting in massive communication resource consumption. Moreover, the different relative frequency of workers participating in asynchronous updating may seriously hurt training accuracy, especially on Non-IID data. In this paper, we propose a semi-asynchronous federated learning mechanism (FedSA), where the parameter server aggregates a certain number of local models by their arrival order in each round. We theoretically analyze the quantitative relationship between the convergence bound of FedSA and different factors,e.g., the number of participating workers in each round, the degree of data Non-IID and edge heterogeneity. Based on the convergence bound, we present an efficient algorithm to determine the number of participating workers to minimize the training completion time. To further improve the training accuracy on Non-IID data, FedSA deploys adaptive learning rates for workers by their relative participation frequency. We extend our proposed mechanism to the dynamic and multiple learning tasks scenarios. Experimental results on the testbed show that our proposed mechanism and algorithms address the three challenges more effectively than the state-of-the-art solutions.

In a software defined network, the controller needs to obtain/collect traffic measurement information (i.e., flow statistics) from switches for different applications, such as traffic engineering. Existing solutions seldom consider the per-switch cost, which may lead to heavy statistics collection cost (e.g., high CPU overhead) on some switches. Due to limited computing power on most commodity switches, heavy statistics collection cost on those switches may seriously interfere with the basic rule operations, especially when some switches need to deal with many new-arrival flows or update routes of existing flows. To address this challenge, we design and implement efficient flow statistics collection (FSC) with limited interference on the basic rule operations. We formally propose a cooperative flow statistics collection with per-switch cost constraint (CP-FSC) problem. We prove that the CP-FSC problem is NP-hard and present an efficient algorithm with approximation ratio 1/2, based on dynamic programming. To reduce the time complexity, a greedy-based algorithm with approximation ratio 1/3 is also presented. We implement the proposed FSC algorithms on our SDN platform. The experimental results and the extensive simulation results show 36%-59% performance improvement compared with the existing solutions.

Mobile crowdsensing is a new paradigm by which a platform can recruit mobile workers to perform some sensing tasks by using their smart mobile devices. In this paper, we focus on a privacy-preserving unknown worker recruitment issue. The platform needs to recruit some workers without knowing the qualities of them completing tasks. Meanwhile, these quality information also needs to be protected from disclosure. To tackle these challenges, we model the unknown worker recruitment as a Differentially Private Multi-Armed Bandit (DP-MAB) game by seeing each worker as an arm of DP-MAB and the task completion quality contributed by each worker as the reward of pulling arm. Then, recruiting workers is equivalent to designing a bandit policy of pulling DP-MAB arms. Under this model, we propose a Differentially Private ϵ-First-based arm-pulling (DPF) algorithm and a Differentially Private UCB-based arm-pulling (DPU) algorithm, which can achieve the nearly optimal expected accumulative rewards under a given budget. We also analyze the regrets of the DPF and DPU algorithms and prove that both of them are δ-differentially private on the task completion qualities (δ > 0δ). Finally, we conduct extensive simulations to verify the significant performances of DPF and DPU based on both the real-trace and synthetic datasets.

To meet the ever-increasing demands for high-quality network services, a software defined network (SDN) can support various virtual network functions (VNFs) using virtualization technology. Due to network dynamics, an SDN needs to be updated frequently to optimize various performance objectives, such as load balancing. Most previous solutions first determine a new network configuration (e.g., target VNF placement and flow routing) based on the current workload, and then update the VNF placement and routing paths of the existing flows. However, due to massive VNF’s state migration and slow update of the flow table, unacceptable update delay may occur, especially in large or frequently changed networks. In this paper, we address the real-time network update, which jointly considers the optimization of the service function chain (SFC) update and the routing update. We propose the delay-satisfied NFV-enabled network update (DSNU) problem, and prove its NP-Hardness. We design an algorithm with bounded approximation factor to solve this problem. To further reduce the delay, we also design an efficient algorithm for the update scheduling. The experimental results show that our method can reduce the network update delay by about 86% compared with the previous network update methods while preserving a similar network performance,i.e., the VNF instance load ratio increases by less than 5%.

Per-flow spread measurement in high-speed networks has many practical applications. It is a more difficult problem than the traditional per-flow size measurement. Most prior work is based on sketches, focusing on reducing their space requirements in order to fit in on-chip cache memory. This design allows the measurement to be performed at the line rate, but it suffers from expensive computation for spread queries (unsuitable for online operations) and large errors in spread estimation for small flows. This paper complements the prior art with a new spread estimator design based on an on-chip/off-chip model. By storing traffic statistics in off-chip memory, our new design faces a key technical challenge to design an efficient online module of non-duplicate sampling that cuts down the off-chip memory access. We first propose a two-stage solution for non-duplicate sampling, which is efficient but cannot handle well a sampling probability that is either too small or too big. We then address this limitation through a three-stage solution that is more space-efficient. Our analysis shows that the proposed spread estimator is highly configurable for a variety of probabilistic performance guarantees. We implement our spread estimator in hardware using FPGA. The experiment results based on real Internet traffic traces show that our estimator produces spread estimation with much better accuracy than the prior art, reducing the mean relative (absolute) error by about one order of magnitude. Moreover, it increases the query throughput by around three orders of magnitude, making it suitable for supporting online queries in real time.

Network Function Virtualization (NFV) is a new paradigm to enable service innovation through virtualizing traditional network functions. To construct a new NFV-enabled network, there are two critical requirements: minimizing server deployment cost and satisfying switch resource constraints. However, prior work mostly focuses on the server deployment cost, while ignoring the switch resource constraints (e.g., switch's flow-table size). It thus results in a large number of rules on switches and leads to massive control overhead. To address this challenge, we propose an incremental server deployment (INSD) problem for construction of scalable NFV-enabled networks. We prove that the INSD problem is NP-Hard, and there is no polynomial-time algorithm with approximation ratio of (1- ϵ)· ln m, where ϵ is an arbitrarily small value and m is the number of requests in the network. We then present an efficient algorithm with an approximation ratio of 2 · H(q · p), where q is the number of VNF's categories and p is the maximum number of requests through a switch. We evaluate the performance of our algorithm with experiments on physical platform (Pica8), Open vSwitches, and large-scale simulations. Both experimental results and simulation results show high scalability of the proposed algorithm. For example, our solution can reduce the control and rule overhead by about 88% with about 5% additional server deployment, compared with the existing solutions.

Large software defined networks use a cluster of distributed controllers to process flow requests from a massive number of switches. To cope with traffic dynamics, this paper studies a new problem of how to improve the residual capacity available at the controllers to handle request bursts experienced at the switches. While the total residual capacity is a constant under a given total capacity of all controllers and a given total workload from all switches, this paper considers the residual capacity available to each individual switch, which depends on how the switches are mapped to the controllers for management. We focus on how tomaximize the minimum residual capacity available to any switch. The prior work either provides poor residual capacity or incurs heavy synchronization overhead by simulation results. This paper proposes a new method calledindirect multi-mappingthat achieves both high residual capacity and low synchronization cost. We formally define a non-linear integer optimization problem for max-min residual capacity under indirect multi-mapping. We then approximate the problem as two sub-problems: switch-controller mapping selection and weight assignment for each switch-controller mapping. We solve these sub-problems and formally analyze their approximate factor. We implement the proposed solution on an SDN testbed for experimental studies and use simulations for large-scale investigation. Our evaluation shows that indirect multi-mapping improves the minimum residual capacity by 49.8% on average and reduces the synchronization cost by 41.9-60.3% on average when compared with the alternatives.

Edge cloud computing is a new paradigm in which the computation and storage services of remote cloud data centers are moved to Edge Cloud Nodes (ECNs) in network edges. Compared to traditional cloud data centers, ECNs are geographically close to mobile users so the communication latency is significantly reduced. In this paper, we study the problem of allocating Virtual Machine (VM) resources in geo-distributed ECNs to mobile users by using the auction theory. First, we treat mobile users and ECNs as the buyers and sellers of the VM resource auction, respectively. Then, we model the VM resource allocation problem as an$n$-to-one weighted bipartite graph matching problem with 0-1 knapsack constraints. Since this problem is NP-hard, we design a greedy approximation algorithm to determine the winners of the auction, based on which we propose a truthful Auction-based VM resource Allocation (AVA) mechanism to solve the problem. Moreover, we prove that the AVA mechanism not only achieves an approximately optimal solution for winner selection, but also has the properties of truthfulness, individual rationality, and computational efficiency. Finally, we conduct extensive simulations on real traces to verify the significant performances of the proposed AVA mechanism.

Per-flow spread measurement in high-speed networks has many practical applications. It is a more difficult problem than the traditional per-flow size measurement. Most prior work is based on sketches, focusing on reducing their space requirements in order to fit in on-chip cache memory. This design allows measurement to be performed at the line rate, but it has to accept tradeoff with expensive computation for spread queries (unsuitable for online operations) and large errors in spread estimation for small flows. This paper complements the prior art with a new spread estimator design based on an on-chip/off-chip model which is common in practice. The new estimator supports online queries in real time and produces spread estimation with much better accuracy. By storing traffic data in off-chip memory, our new design faces a key technical challenge of efficient non-duplicate sampling. We propose a two-stage solution with on-chip/off-chip data structures and algorithms, which are not only efficient but also highly configurable for a variety of probabilistic performance guarantees. The experiment results based on real Internet traffic traces show that our estimator reduces the mean relative and absolute error by around one order of magnitude, and achieves both space-efficiency and accuracy-efficiency in flow classification for small flows compared to the prior art.

This paper concentrates on the issue of detecting persistent elements of anomalous flows in a distributed monitoring system, which has many applications in detecting cyber-attacks, forecasting influenza, analyzing search keywords, and etc. However, only a few studies consider the anomalous flow detection problem in distributed systems. Meanwhile, most of the existing studies on persistent element detection problem in distributed systems assume that there is only one flow in the data stream, which is not always true in practice. In this paper, we combine the problems of anomalous flow detection and persistent elements finding, and propose an efficient mechanism to find the t-persistent elements of p-anomalous flows from element sets of numerous flows in the monitors of a distributed system, where t and p are system parameters that can be defined based on the application requirement. We adopt tight data structures such as bitmap and bloom filter to record the elements of different flows and filter out the elements that not in the t-persistent element set, which can help us reduce the communication overhead between monitors and the controller. We also give an analysis of how to get the optimal settings of these tight data structures that can minimize the total communication overhead. The experiment results based on real network traces show that the proposed mechanism achieves 76.1% and 69.2% reduction in communication overhead in comparison with a straightforward solution and a state-of-the-art solution based on coding cuckoo filter, respectively.

We propose the first budget-limited multi-armed bandit (BMAB) algorithm subject to a union of matroid constraints in arm pulling, while at the same time achieving differential privacy. Our model generalizes the arm-pulling models studied in prior BMAB schemes, and it can be used to address many practical problems such as network backbone construction and dynamic pricing in crowdsourcing. We handle the exploitation versus exploration tradeoff in our BMAB problem by exploiting the combinatorial structures of matroids, and reduce the searching complexity of arm selection based on a divide-and-conquer approach. Our algorithm achieves a uniform logarithmic regret bound with respect to B and ɛ-differential privacy, where B is the budget for pulling the arms with random costs. Without differential privacy, our algorithm achieves a uniform logarithmic regret bound with respect to B, which advances the asymptotic regret bounds achieved by prior BMAB algorithms. We performed side-by-side comparisons with prior schemes in our experiments. Experimental results show that our purely-combinatorial algorithm not only achieves significantly better regret performance, but also is more than 20 times faster than prior BMAB schemes, which use time-consuming LP-solving techniques.

With the proliferation of mobile devices, mobile crowd sensing (MCS) has emerged as a new data collection paradigm, which allows the crowd to act as sensors and contribute their observations about entities. Unfortunately, users with varied skills and motivations may provide conflicting information for the same entity. Existing work solves this problem by estimating user reliability and inferring the correct observations (i.e., truths). However, these methods assume that users' expertise degrees are dependent on the truths, but ignore the finer clusters that exist even in the entities with the same truths. To capture users' fine-grained reliability on different entity clusters, we propose a novel Bayesian co-clustering truth discovery model for the task of observation aggregation. This model enables us to produce a more precise estimation while taking into account the entity clusters and the user clusters. Experiments on four real-world datasets reveal that our method outperforms the state-of-the-art approaches in terms of accuracy and F1-score.

Traffic measurement in high-speed networks has many important functions in improving network performance, assisting resource allocation, and detecting anomalies. In this paper, we study a generalized problem called k-persistent spread estimation, which measures the volume of persist traffic elements in each flow that appear during at least k out of t measurement periods, where k and t are two positive integers that can be arbitrarily set in user queries, with k ≤ t. Solutions to this problem have interesting applications in network attack detection, popular content identification, user access profiling, etc. There is very limited prior art for this problem, only addressing the special case of k = t under a flawed assumption. Removing this assumption, we propose an efficient and accurate estimator for generalized k-persistent traffic measurement, with k ≤ t. Our method relies on bitwise SUM, instead of bitwise AND in the prior art, to combine the information collected from different periods. This change has fundamental impact on the probabilistic analysis that derives the estimator, particular over space-saving virtual bitmaps. Based on real network traces, we demonstrate experimentally the effectiveness of our new method in estimating the k-persistent spreads of all network flows. Our estimator performs much better than the prior art on its case of k = t. We also incorporate a sampling module to the estimator for improved flexibility, and give a use study on how to detect and find DDoS attackers using the proposed estimator.

Traffic measurement is very important for various applications, such as traffic engineering and attack detection, in software-defined networks. Due to limited resources (e.g., computing, memory) on SDN switches, sketches have been widely used for efficient traffic measurement. Meanwhile, multiple independent sketches are required for different application requirements, such as heavy hitter detection and flow size distribution estimation. To avoid the measurement redundancy, we configure which sketch(es) will measure flow on each switch. If traffic measurement is performed on each switch without considering network routing, due to traffic dynamics, it will cause massive measurement overhead on a switch, which may exceed the switch's computing capacity. In this paper, we study the joint optimization of flow routing and sketch configuration in SDNs. We formulate this problem as an integer linear programming and prove its NP-hardness. To solve this problem, we propose a rounding-based offline algorithm and a primal-dual-based online algorithm for different application scenarios. To deal with bursty traffic, we also design an adaptive sampling mechanism for high-fidelity traffic measurement. We formally analyze the approximation performance or competitive ratio of the proposed algorithms. The extensive simulation results show the high efficiency of our proposed algorithms. For example, the online algorithm can improve the network throughput 30% compared with the state-of-the-art.

Crowdsensing is a promising sensing paradigm to efficiently collect and monitor the physical world by using the embedded sensors in mobile devices. However, the observations (sensory data) submitted by mobile device users may not be reliable. For the same sensing task, users with different reliabilities may submit conflicting information. Thus, we need to estimate the truth based on the submitted observations. Temporal and spatial correlations among tasks are widely observed in crowdsensing applications. However, most of the existing truth discovery mechanisms assume that the tasks are independent, which is not suitable for all crowdsensing applications. To solve this problem, we propose an efficient truth discovery mechanism for crowdsensing tasks with temporal and spatial correlations. To improve the reliability of the estimated truth, we first filter the outliers based on the temporal correlations among tasks, then estimate the truth based on the weighted observations, and finally refine the estimated truth based on the spatial correlations among tasks. Our experiments on a real transportation dataset show the efficiency of the proposed mechanism.

Real-time road condition monitoring, especially of severe road damage, is critical for driving safety. In this work, we propose a crowdsensing-based pothole detection and measurement system, called CPDM, which can accurately measure the depth and length of detected potholes in urban roads. CPDM learns road surface information by collecting the sensor data from the smartphones belonging to the passing drivers and passengers. The proposed system can detect potholes by observing the vibration signal when the vehicle passes over the pothole, learn the vehicle parameters by fitting the underdamping vibration signal with stochastic gradient descent, and estimate the depth and length of the pothole. We have implemented a prototype system to prove the efficiency and adaptability of the proposed CPDM. The experimental results based on real traces show that CPDM has a high detection accuracy at different vehicle speeds.

Taxi recommender systems have remarkably benefited the taxi business by providing a sequence of pick-up points to reduce the passenger waiting time or the taxi cruising time. In reality, taxi drivers may have their preferred destination regions to avoid traffic jams or to execute arranged pickup orders. However, no prior work managed to maximize the profit of drivers and satisfy the requirements for destination regions at the same time. To tackle this challenge, we propose a PROfit Maximization recommendatIon SystEm (PROMISE) based on the inter-regional probability. In this paper, we first divide the city map into sub-regions and compute the mobility probability of passengers among pick-up points and sub-regions, namely inter-regional mobile probability. Then, we propose an efficient Driving Route Suggestion (DRS) algorithm based on inter-regional probability, which can maximize the profit of taxi drivers with designated destination regions. The experimental results based on the taxi traces collected from Shanghai, China, validate the effectiveness of the proposed recommender system.

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.

Rain observations with fine spatio-temporal granularity are significant for professional researches, decision-making, and our daily lives. However, the existing rain gauges can only cover less than 1% of the earth surface, and its amount is still decreasing. Even with the help of several other limited and immature supplementary techniques, rain observations today are still not precise enough. In such context, crowdsourcing paves the avenues toward a fault-tolerant rain observation network with unprecedented resolution and coverage, based on an alternative, nowadays omnipresent source, smartphones, which are integrated with abundant advanced sensors and are becoming more and more ubiquitous around us. In this paper, we propose Chaac, a novel system that exploits opportunistically crowdsourced audio clips from smartphone users to achieve precise detection and intensity measurement of rain. The evaluation results of performing Chaac on 1-s long audio segments demonstrate that it can detect and measure rain with 92.0% and 93.9% true positive rates, respectively.

Traffic volume estimation is critical to the intelligent transportation engineering. Previous state-of-the-art studies mainly focus on measuring two types of traffic volume: “point” traffic (i.e., the number of vehicles passing a given location) and “point-to-point” traffic (i.e., the number of vehicles traversing between two given locations) during each measurement period. In this paper, we extend this line of research from single-period to multiple periods and study new problems of estimating the number of k-persistent vehicles that pass a location or two different locations in at least k-out-of-t predefined measurement periods. We propose two novel k-persistent traffic estimators with privacy-preserving for the point and point-to-point traffic models, respectively. Through theoretical analysis, we prove that our solution can solve more general traffic measurement problems and employ stronger privacy preserving, i.e., E-differential privacy, than the existing studies. We also demonstrate the effectiveness and the accuracy of the proposed estimators through extensive experiments based on real transportation traffic flows in Shenzhen, China for five consecutive working days. The numerical results show that the estimators can achieve a tradeoff between the estimation accuracy and privacy preservation through proper parameter setting.

We consider the edge uncertainty in an undirected graph and study the k -median (resp. k -center) problems, where the goal is to partition the graph nodes into k clusters such that the average (resp. minimum) connection probability between each node and its cluster's center is maximized. We analyze the hardness of these problems, and propose algorithms that provide considerably improved approximation guarantees than the existing studies do. Specifically, our algorithms offer (1 -- 1/e)-approximations for the k -median problem and (OPTck)-approximations for the k -center problem, where OPTck is the optimal objective function value for k -center. In addition, our algorithms incorporate several non-trivial optimizations that significantly enhance their practical efficiency. Extensive experimental results demonstrate that our algorithms considerably outperform the existing methods on both computation efficiency and the quality of clustering results.

Measuring traffic volume in a road system has important applications in transportation engineering. The connected vehicle technologies integrate wireless communications and computers into transportation systems, allowing wireless data exchanges between vehicles and road-side equipment, and enabling large-scale, sophisticated traffic measurement. This paper investigates the problem of persistent traffic measurement, which was not adequately studied in the prior art, particularly in the context of intelligent vehicular networks. We propose three estimators for privacy-preserving persistent traffic measurement: one for point traffic, one for point-to-point traffic, and another for three-point traffic. After that, we present a general framework to measure persistent traffic that go through more than three locations. The estimators are mathematically derived from the join result of traffic records, which are produced by the electronic roadside units with privacy-preserving data structures. We evaluate our estimation methods using simulations based on both real transportation traffic data and synthetic data. The numerical results demonstrate the effectiveness of the proposed methods in producing high measurement accuracy and allowing accuracy-privacy tradeoff through parameter setting.

Traffic measurement in high-speed networks has many applications in improving network performance, assisting resource allocation, and detecting anomalies. In this paper, we study a new problem called k-persistent spread estimation, which measures persist traffic elements in each flow that appear during at least k out of t measurement periods, where k and t can be arbitrarily defined in user queries. Solutions to this problem have interesting applications in network attack detection, popular content identification, user access profiling, etc. Yet, it is under-investigated as the prior work only addresses a special case with a questionable assumption. Designing an efficient and accurate k -persistent estimator requires us to use bitwise SUM (instead of bitwise AND typical in the prior art) to join the information collected from different periods. This seemly simple change has fundamental impact on the mathematical process in deriving an estimator, particular over space-saving virtual bitmaps. Based on real network traces, we show that our new estimator can accurately estimate the k -persistent spreads of the flows. It also performs much better than the existing work on the special case of measuring elements that appear in all periods.

Recently, influence maximization in social networks has attracted great attention. In this paper, we consider that a company intends to select some users to promote its multiple products (called influences) in online social network consisting of many communities, in which each user has different preferences for each influence. We focus on the Minimum Cost Seed Selection (MCSS) problem for multiple influences, that is, how to select some seeds with minimum cost so that the average influenced probability of all users in each community is not less than a threshold. To solve the MCSS problem, we design a submodular utility function, based on which we turn our problem into a non-trivial set cover problem with non-linear constraints. After proving the NP-hardness of MCSS, we propose a greedy algorithm, called G-MCSS, to solve it. We analyze the approximation ratio of G-MCSS. Additionally, we extend the MCSS problem to a complex case, where the number of acceptable influences for each user is limited, and the cost is proportional to the number of allocated influences. We further propose another greedy algorithm to solve the extended problem. Finally, we demonstrate the significant performances of our algorithms through extensive experiments based on real social network traces.

Viral marketing through online social networks (OSNs) has aroused great interests in the literature. However, the fundamental problem of how to optimize the "pure gravy" of a marketing strategy through influence propagation in OSNs still remains largely open. In this paper, we consider a practical setting where the "seed nodes" in an OSN can only be probabilistically activated by the product discounts allocated to them, and make the first attempt to seek a discount allocation strategy to maximize the expected difference of profit and cost (i.e., revenue) of the strategy. We show that our problem is much harder than the conventional influence maximization issues investigated by previous work, as it can be formulated as a non-monotone and non-submodular optimization problem. To address our problem, we propose a novel "surrogate optimization" approach as well as two randomized algorithms which can find approximation solutions with constant performance ratios with high probability. We evaluate the performance of our approach using real social networks. The extensive experimental results demonstrate that our proposed approach significantly outperforms previous work both on the revenue and on the running time.

Forecasting taxi demand is of great significance to the intelligent transportation systems in a smart city. Traditional demand prediction methods mostly considered about inter-regional traffic, events, activities, and weather, while they overlooked the influence of other travel modes, such as metro. In this paper, we propose a Deep Taxi-Metro Spatial-Temporal Network framework, namely TMST-Net, to model the spatiotemporal relationships between the taxi demand and the metro crowd flows. In detail, we apply residual neural networks to model temporal (current, day, and week) properties of the taxi demand in each area. For each feature, we apply residual convolutional units to handle the spatial properties of taxi demand. Likewise, we apply the same method to model the metro crowd flows. TMST-Net learns to assign different weights between taxi and metro by aggregating the output of the three residual neural networks and the external factors to forecast the final taxi demand for each area in the next timestamp. Experimental results on real taxi trajectory and the automatic fare collection (AFC) data in Shanghai show that our approach outperforms the state-of-the-art methods.

With the proliferation of various next generation wireless communication technologies, the smartphone has entered into our daily lives. Meanwhile, the excessive use of smartphone is seriously affecting our normal work and rest. In particular, the inappropriate way of using smartphone, especially when playing smartphone on bed in a lie-down posture, may do potential harm to our health. Thus, we propose a system called PosAla to encourage the smartphone users to use their phones in a correct posture. The proposed system adopts the supervised classifier to identify the harmful behavior, which is in a lie-down posture while using the smartphone, from a large number of sensor data generated during daily use of smartphone. Eight classification algorithms were tested in the experiments, and a large number of experiments have been conducted in terms of segment length and attribute selection. The extensive experimental results show that the recognition accuracy can reach 99.52%.

Crowdsourcing has shown its efficiency in obtaining information by harnessing the intelligence of a large crowd of human workers. It is essential to employ incentive mechanisms, typically auction, to motivate workers and collect sufficient data, since performing crowdsourcing tasks will always consume considerable resources, e.g., CPU or battery resource. To this end, we focus on the problem of heterogeneous task allocation with budget constraint in the crowdsourcing systems and propose a truthful auction mechanism which can maximize the profit of the task requester. In this paper, we first prove the NP-hardness of the studied problem and design a near-optimal task allocation mechanism with partial enumeration which can maximize the profit of the requester. Then, we judiciously design a bid-independent payment calculation mechanism to ensure the truthfulness of the participants. Finally, we prove that the proposed crowdsourcing task auction mechanism can achieve truthfulness and individual rationality. The extensive simulation results also corroborate with our theoretical analysis.

The reduced-order filtering problems are investigated in this paper for static neural networks with Markovian jumping parameters and mode-dependent time-varying delays. By fully making use of integral inequalities, the designs of reduced-order and filters are discussed. The proper gain matrices of filters and the optimal performance indices are efficiently obtained by resolving corresponding convex optimization problems with the constraints of linear matrix inequalities. It is verified that the computational complexity for the reduced-order filter design is significantly reduced when compared with the full-order one. Furthermore, the nonfragile reduced-order filtering problems are also resolved in this paper. Two examples with simulation results are presented to demonstrate the feasibility and application of the established results.

Traditional networks rely on aggregate routing and decentralized control to achieve scalability. On the contrary, software-defined networks achieve near optimal network performance and policy-based management through per-flow routing and centralized control, which, however, face scalability challenge due to: 1) limited ternary content addressable memory and on-die memory for storing the forwarding table and 2) per-flow communication/computation overhead at the controller. This paper presents a novel hybrid switching (HS) design, which integrates traditional switching and software-defined networking (SDN) switching for the purpose of achieving both scalability and optimal performance. We show that the integration also leads to unexpected benefits of making both types of switching more efficient under the hybrid design. We also design the general optimization framework via HS and propose an approximation algorithm for load-balancing optimization as a case study. Testing and numerical evaluation demonstrate the superior performance of HS when comparing with the state-of-the-art SDN design.

Measuring point traffic volume and point-to-point traffic volume in a road system has important applications in transportation engineering. The connected vehicle technologies integrate wireless communications and computers into transportation systems, allowing wireless data exchanges between vehicles and road-side equipment, and enabling large-scale, sophisticated traffic measurement. This paper investigates the problems of persistent point traffic measurement and persistent point-to-point traffic measurement, which were not adequately studied in the prior art, particularly in the context of intelligent vehicular networks. We propose two novel estimators for privacy-preserving persistent traffic measurement: one for point traffic and the other for point-to-point traffic. The estimators are mathematically derived from the join result of traffic records, which are produced by the electronic roadside units with privacy-preserving data structures. We evaluate our estimation methods using simulations based on both real transportation traffic data and synthetic data. The numerical results demonstrate the effectiveness of the proposed methods in producing high measurement accuracy and allowing accuracy-privacy tradeoff through parameter setting.

Due to the sparse distribution of road video surveillance cameras, precise trajectory tracking for vehicles remains a challenging task. To the best of our knowledge, none of the previous research considered using on-road taxicabs as mobile video surveillance cameras and road traffic flow patterns, therefore not suitable for recovering trajectories of vehicles. With this insight, we model the travel time-cost of a road segment during various time periods precisely with LNDs (Logarithmic Normal Distributions), then use LSNDs (Log Skew Normal Distributions) to approximate the time-cost of an urban trip during various time periods. We propose an approach to calculate possible location and time distribution of the vehicle, select the taxicab to verify the distribution by uploading and checking video clips of this taxicab, finally refine the restoring trajectory in a recursive manner. We evaluate our solution on real-world taxicab and road surveillance system datasets. Experimental results demonstrate that our approach outperforms alternative solutions in terms of accuracy ratio of vehicle tracking.

Due to the sparse distribution of road video surveillance cameras, precise trajectory tracking for hit-and-run vehicles remains a challenging task. Previous research on vehicle trajectory recovery mostly focuses on recovering trajectory with low-sampling-rate GPS coordinates by retrieving road traffic flow patterns from collected GPS information. However, to the best of our knowledge, none of them considered using on-road taxicabs as mobile video surveillance cameras as well as the time-varying characteristics of vehicle traveling and road traffic flow patterns, therefore not suitable for recovering trajectories of hit-and-run vehicles. With this insight, we model the travel time-cost of a road segment during various time periods precisely with LNDs (Logarithmic Normal Distributions), then use LSNDs (Log Skew Normal Distributions) to approximate the time-cost of an urban trip during various time periods. We propose a novel approach to calculate possible location and time distribution of the hit-and-run vehicle in parallel, select the optimal taxicab to verify the distribution by uploading and checking video clips of this taxicab, finally refine the restoring trajectory in a parallel and recursive manner. We evaluate our solution on real-world taxicab and road surveillance system datasets. Experimental results demonstrate that our approach outperforms alternative solutions in terms of accuracy ratio of vehicle tracking.

Traditional networks rely on aggregate routing and decentralized control to achieve scalability. On the contrary, software-defined networks achieve near optimal network performance and policy-based management through per-flow routing and centralized control, which however face scalability challenge due to (1) limited TCAM and on-die memory for storing the forwarding table and (2) per-flow communication/computation overhead at the controller. This paper presents a novel hybrid switching design, which integrates traditional switching and SDN switching for the purpose of achieving both scalability and optimal performance. We show that the integration also leads to unexpected benefits of making both types of switching more efficient under the hybrid design. Numerical evaluation demonstrates the superior performance of hybrid switching when comparing with the state-of-the-art SDN design.

With the advent of virtualization technologies, cloud computing resource allocation issue plays an important role. However, the existing studies have not fully considered the heterogeneous demands from different cloud tenants. To tackle this, we design a more flexible cloud resource allocation mechanism which can maximize the profit of the cloud provider and support three general types of resource requirements from the cloud tenants. In this work, the jobs from tenants will bid for the usage of VMs in 3 types: 1) fixed time intervals, 2) time window intervals and 3) Time window slice intervals. We proved that the proposed approximation allocation mechanism has an approximation factor which approaches 1.58 when cmcloses to infinity.

Mobile crowdsourcing has been proposed as a promising approach for urban data collection, but it has also brought the critical problem of designing proper mechanisms to incentivize user participation. Most previous work on crowdsourcing incentivization has assumed that each user holds a single private cost for participation or behaves in a "win all or nothing" (a.k.a. "single-minded") manner. However, in some crowdsourcing applications such as Amazon's Mechanical Turk, the users are usually "multi-minded" in the sense that each of them holds heterogeneous private costs for different tasks and only performs a portion of her/his interested tasks according to the announced payments. To address this problem, we propose LIME, an onLine prIcing mechanism to incentivize Multi-minded usErs under the scenario where the users arrive sequentially in an arbitrary order. We show that the design of LIME involves solving a "dummy semi-bandits with multiple knapsacks and random costs" problem, which has not been investigated before, and we also prove that LIME achieves several desirable properties including computational efficiency, budget feasibility, truthfulness, individual rationality and low regret on the utility. Finally, the effectiveness of LIME as well as its superiorities over prior related work are demonstrated through extensive simulations.

Crowdsensing is regarded as an efficient way to collect a large number of sensing data by using sensor-equipped mobile phones. Most of the existing studies, which concentrate on the crowdsensing task assignment issue, often assume that there is only one data consumer in the system. Obviously, there may exist multiple data consumers in one real crowdsensing system, thus the previous works based on the single data consumer assumption may have many limitations. To tackle this challenge, we mainly focus on the crowdsensing task assignment problem with multiple data consumers, and propose an auction mechanism which can achieve max-min fairness. We first design an approximation transaction set construction mechanism, which can maximize the minimum utilities of data consumers. Then, a second- price-like winner determination and payment calculation mechanism is proposed to ensure the truthfulness. Finally, we prove that the proposed mechanism can achieve the essential economic properties, such as truthfulness, individual rationality and budget balance. The evaluation results corroborate our theoretical analysis, and further indicate that the proposed mechanism is efficient.

Cooperative communication has great potential to enhance the performance of wireless networks by exploiting relay nodes' spatial diversity. Relay assignment plays a vital role in making the most of this potential. However, most previous studies investigate relay assignment in a rather static manner which may lead to the under‐utilisation of relay nodes, especially in the scenarios where source nodes' demands are time varying. Hence, in this study, the authors consider the relay assignment problem for cooperative networks using auction model with access flexibility, i.e. providing sufficient flexibility for source nodes to access relay nodes in time domain. They divide relay nodes' access time into multiple smaller access units and permit each source node to bid for a bundle of desired access units in the auction. This model is formulated as a combinational auction whose winner determination problem is NP hard. They thus present an auction mechanism with an elaborated greed strategy which not only achieves adorable properties such as truthfulness, individual rationality and computational efficiency, but also guarantees near‐optimal social welfare. Finally, they conduct extensive evaluations to verify the performance of their mechanism.

An efficient generalized hybrid constructive (GHC) learning algorithm for multioutput radial basis function (RBF) networks is proposed to obtain a compact network with good generalization capability. By this algorithm, one can train the adjustable parameters and determine the optimal network structure simultaneously. First, an initialization method based on the growing and pruning algorithm is utilized to select the important initial hidden neurons and candidate ones. Then, by introducing a generalized hidden matrix, a structured parameter optimization algorithm is presented to train multioutput RBF network with fixed size, which combines Levenberg-Marquardt (LM) algorithm with least-square method together. Beginning from an appropriate number of hidden neurons, new neurons chosen from the candidates are added one by one each time when the training entraps into local minima. By incorporating an improved incremental constructive scheme, the training is built on previous results after adding new neurons such that the GHC learning algorithm avoids a trial-and-error procedure. Furthermore, based on the improved computation for LM training, the memory limitation problem is solved. The computational complexity analysis and experimental results demonstrate that better performance is efficiently achieved by this algorithm.

To explore the advantages of software defined network (SDN), while preserving the legacy networking systems, a natural deployment strategy is to deploy a hybrid SDN incrementally to improve the network performance. In this paper, we address two technical challenges: an incremental deployment strategy and a throughput-maximization routing, for deploying a hybrid network incrementally. For incremental deployment, we propose a heuristic algorithm for deploying a hybrid SDN under the budget constraint, and prove the approximate factor of 1- 1/e. For throughput-maximization routing, we apply a depth-first-search method and a randomized rounding mechanism to solve the multi-commodity h-splittable flow routing problem in a hybrid SDN, where h ≥ 1. We also prove that our method has approximation ratio O(1/log N), where N is the number of links in a hybrid SDN. We then show, by both analysis and simulations, that our algorithms can obtain significant performance gains and perform better than the theoretical worst-case bound. For example, our incremental deployment scheme helps to enhance the throughout about 40% compared with the previous deployment scheme by deploying a small number of SDN devices, and the proposed routing algorithm can improve the throughput about 31% compared with ECMP in hybrid networks.

Mobile crowdsensing is a new paradigm in which a group of mobile users exploit their carried smart devices to cooperatively perform a large-scale sensing job over urban environments. In this paper, we focus on the Deadline-sensitive User Recruitment (DUR) problem for probabilistically collaborative mobile crowdsensing, in which mobile users perform sensing tasks with certain probabilities, and multiple users might be recruited to cooperatively perform a common task, ensuring that the expected completion time be no larger than a deadline. In order to solve this problem, we propose a greedy approximation algorithm, which can achieve the logarithmic approximation ratio.

Mobile crowdsensing is a new paradigm in which a group of mobile users exploit their smart devices to cooperatively perform a large-scale sensing job over urban environments. In this paper, we focus on the Deadline-sensitive User Recruitment (DUR) problem for probabilistically collaborative mobile crowdsensing. Unlike previous works, mobile users in this problem perform sensing tasks with probabilities, and multiple users might be recruited to cooperatively perform a common task, ensuring that the expected completion time is no larger than a deadline. Owing to such a probabilistic collaboration, DUR can be formalized as a non-trivial set cover problem with non-linear programming constraints and an optimization objective of real function. We first prove that the DUR problem is NP-hard. Then, we propose a greedy DUR algorithm, called gDUR, to solve this problem. Next, we prove that the gDUR algorithm can achieve a logarithmic approximation ratio. Furthermore, we extend the problem to a more complex case where sensing duration is taken into consideration, and we propose a sensing-duration-aware user recruitment algorithm, called dDUR. Finally, we validate the performance of the proposed algorithms through extensive simulations, based on a real mobile social network trace and a synthetic trace.

Mobile crowdsensing has been considered as a promising approach for large scale urban data collection, but has also posed new challenging problems such as incentivization and quality control. Among the other incentivization approaches, posted pricing has been widely adopted by commercial systems due to the reason that it naturally achieves truthfulness and fairness and is easy to be implemented. However, the fundamental problem of how to set a right posted price in crowdsensing systems remains largely open. In this paper, we study a quality-aware Bayesian pricing problem for mobile crowdsensing where the users' sensing costs and qualities for participating in crowdsensing are drawn from known distributions learned from historical information, and our goal is to choose an appropriate posted price to recruit a group of participants with reasonable sensing qualities for robust crowdsensing, while the total expected payment is minimized. We show that our problem is NP-hard and has close ties with the well known Poisson Binomial Distributions (PBD). To solve our problem, we first discover some non-trivial submodular properties of PBD, which have not been reported before, then we propose a novel "ironing method" that transforms our problem from a non-submodular optimization problem into a submodular one by leveraging the newly discovered properties of PBD. Finally, with the ironing method, an approximate algorithm with provable performance ratio is provided, and we also conduct extensive numerical simulations to demonstrate the effectiveness of our approach.

Dynamic secondary spectrum markets have gained tremendous attentions recently, which can provide significant flexibility for trading spectrum by conducting auctions periodically. The high price of spectrum necessitates a thorough consideration on secondary users' budget constraint, i.e. the total money they could pay. However, previous studies rarely deal with the practical issue of budget constraint, and concentrate on maximizing social welfare greedily in a single round auction, which may not guarantee their performance after multiple rounds of auctions. In this paper, we investigate the techniques for budget constrained periodic spectrum auction, which ensures approximate social welfare maximization from a long- term perspective. With the celebrated primal-dual method, we present a Periodic Spectrum Auction framework (PSA) that runs a tailored One Round Spectrum Auction (ORSA) in each round. In the ORSA, we achieve critical properties such as truthfulness, individual rationality and computational efficiency. Due to the dual fitting technique, ORSA not only achieves approximate social welfare maximization in one round, but also guarantees only a small loss of approximation ratio when runs in multiple rounds under the PSA framework. Finally, we conduct extensive simulations to demonstrate the performance of our schemes.

Cooperative cognitive radio network (CCRN) is a promising paradigm to increase spectrum utilization and exploit spatial diversity. The allocation of two related resources, i.e. spectrum and relay nodes, plays a fundamental role in the performance of CCRNs. However, previous works either lack of incentives for both primary users (PUs) and relay nodes to participate in or consider spectrum auction and relay auction separately. In this paper, we consider a static cooperative cognitive radio network scenario with several PUs and multiple secondary user coteries, each of which consists of a set of secondary users who are interested in sharing the same secondary relay node. We model the problem of joint spectrum allocation and relay allocation as a hierarchical auction and propose TERA, which is the first Truthful auction mechanism for Efficient Resource Allocation in CCRNs. We show that TERA satisfies critical economic properties such as truthful, individual rationality, budget balance, supply limits and computational efficiency. Furthermore, we theoretically prove TERA can achieve near-optimal revenue with high probability. Finally, extensive simulation results show that TERA is efficient and able to improve the utility of PUs and relay nodes significantly up to 125% and 151% respectively.

This paper is concerned with globally exponential stability in the mean square of stochastic static neural networks with Markovian switching and time delay. Firstly, the mathematical model of this kind of recurrent neural networks is established by taking information latching and noise disturbance into consideration. Then, a stability condition, which is dependent on both time delay and system mode, is presented in terms of linear matrix inequalities. Based on it, the maximum value of the exponential decay rate can be efficiently found by solving a convex optimization problem.

As the size of smartphone touchscreens becomes larger and larger in recent years, operability with single hand is getting worse especially for female users. We envision that user experience can be significantly improved if smartphones are able to detect the current operating hand and adjust the UI subsequently. In this paper, we propose a novel scheme that leverages user-generated touchscreen traces to recognize current operating hand accurately, with the help of a supervised classifier constructed from twelve different kinds of touchscreen trace features. As opposed to existing solutions that all require users to select the current operating hand or dominant hand manually, our scheme follows a more convenient and practical manner, and allows users to change operating hand frequently without any harm to user experience. We conduct a series of real-world experiments on Samsung Galaxy S4 smartphones, and evaluation results demonstrate that our proposed approach achieves 94.1% accuracy when deciding with a single trace only, and the false positive rate is as low as 2.6%.

A cyclic mobile social network (MSN) is a new type of delay tolerant network, in which mobile users periodically move around, and contact each other through their carried short-distance communication devices. In this paper, we introduce utility-based routing into cyclic MSNs, and propose a deadline-sensitive utility-based routing model. If a message is successfully delivered to its destination before a deadline, its source will receive a positive benefit as the reward. Otherwise, the source receives zero benefit. Also, each message delivery incurs a forwarding cost, no matter whether it succeeds or fails. The utility of a message delivery is defined as the benefit minus the forwarding cost. Under this model, we propose a deadline-sensitive opportunistic utility-based single-copy routing algorithm, DOUR. Each node first determines an optimal forwarding sequence, which is composed of a series of forwarding opportunities, in a distributed and greedy manner. Then, it forwards messages via these forwarding opportunities. Theoretical analysis and extensive simulations prove that DOUR can achieve the optimal utility for each message delivery. Moreover, we extend our algorithm to the case of multi-copy routing, and show that our proposed algorithms can inherently make a good tradeoff among the benefit, delay, and cost for each message delivery.

We study a spectrum auction problem where each request from new spectrum users has spatial, temporal, and spectral features. Our goal is to design truthful auction mechanisms that maximize either the overall social efficiency of new users (a.k.a buyers) or the revenue of the spectrum owner (a.k.a seller). Given that the optimal conflict-free spectrum allocation problem is NP-hard, this paper proposes a series of near-optimal auction mechanisms based on the following approximation techniques: linear programming (LP) relaxation, randomized rounding, derandomized rounding, monotone derandomization, and Lavi-Swamy method. Comparing with the prior art, we make two significant advances: First, our auction mechanisms are not only truthful but also provide theoretically-provable performance guarantee, an important feature that existing work under the same auction model does not have. Second, our auction mechanisms support both spatial and temporal spectral reuse, which makes the problem more challenging than existing work that deals with only spatial or temporal reuse. We perform extensive simulations to study the performance of the proposed mechanisms, and the simulation results corroborate our theoretical analysis.

This brief considers the guaranteed H∞ performance state estimation problem of delayed static neural networks. An Arcak-type state estimator, which is more general than the widely adopted Luenberger-type one, is chosen to tackle this issue. A delay-dependent criterion is derived under which the estimation error system is globally asymptotically stable with a prescribed H∞ performance. It is shown that the design of suitable gain matrices and the optimal performance index are accomplished by solving a convex optimization problem subject to two linear matrix inequalities. Compared with some previous results, much better performance is achieved by our approach, which is greatly benefited from introducing an additional gain matrix in the domain of activation function. An example is finally given to demonstrate the advantage of the developed result.

Many spectrum auction mechanisms have been proposed for spectrum allocation problem, and unfortunately, few of them protect the bid privacy of bidders and achieve good social efficiency. In this paper, we propose PPS, a Privacy Preserving Strategyproof spectrum auction framework. We design two schemes based on PPS separately for 1) the single-unit auction model (SUA), where only single channel will be sold in the spectrum market; and 2) the multi-unit auction model (MUA), where the primary user subleases multi-unit channels to the secondary users and each of the secondary users wants to access multi-unit channels either. Since the social efficiency maximization problem is NP-hard in both auction models, we present allocation mechanisms with approximation factors of (1 + ε) and 32 separately for SUA and MUA, and further judiciously design strategyproof auction mechanisms with privacy preserving based on them. Our extensive evaluations show that our mechanisms achieve good social efficiency and with low computation and communication overhead.

In this paper, an improved complex-valued backpropagation algorithm with gain parameters is proposed. It is then employed to train a complex-valued feedforward neural network with one hidden layer. The well-trained complex-valued neural network is finally applied to deal with the recognition problem of 26 hand gestures. The results of experiment clearly show that much better performance can be achieved by our improved complex-valued backpropagation algorithm than some existing methods.

In this work, we study spectrum auction problem where each spectrum usage request has spatial, temporal, and spectral features. After receiving bid requests from secondary users, and possibly reserve price from primary users, our goal is to design truthful mechanisms that will either optimize the social efficiency or optimize the revenue of the primary user. As computing an optimal conflict-free spectrum allocation is an NP-hard problem, in this work, we design near optimal spectrum allocation mechanisms separately based on the techniques: derandomized allocation from integer programming formulation, and its linear programming (LP) relaxation. We theoretically prove that 1) our derandomized allocation methods are monotone, thus, implying truthful auction mechanisms; 2) our derandomized allocation methods can achieve a social efficiency or a revenue that is at least $1-\frac{1}{e}$ times of the optimal respectively; Our extensive simulation results corroborate our theoretical analysis.

Spectrum auctions motivate existing spectrum owners (as sellers) to lease their selected idle channels to new spectrum users (as buyers) who need the spectrum desperately. The most significant requirement is how to make the auctions economic-robust (truthful in particular) while enabling spectrum reuse. Furthermore, in practice, both sellers and buyers would require to trade multiple channels at one time, while guaranteeing their individual profitability. Unfortunately, existing designs can not meet all these requirements simultaneously. We address these requirements by proposing True-MCSA, a framework for truthful double multi-channel spectrum auctions. True-MCSA introduces novel virtual buyer group (VBG) splitting and bidding algorithms, and applies a proper winner determination and pricing mechanism to achieve truthfulness and other economic properties, meanwhile successfully dealing with multi-channel requests from both buyers and sellers and improving spectrum utilization. Our experiments show that the auction efficiency is impacted by the economic factors with efficiency degradations within 30%, under different settings. Furthermore, the experimental results indicate that we can improve the auction efficiency by choosing a proper bidding algorithm and using a positive base bid. True-MCSA makes an important contribution on enabling spectrum reuse to improve auction efficiency in multi-channel cases.

Cooperative communication is shown to be a promising technology to enhance the capacity of wireless transmission without additional equipments. Under this communication paradigm, both relay selection and power allocation significantly affect the overall system performance. Thus, this paper studies the joint power allocation and relay assignment problem to optimize the Max-Min fairness of cooperative network. We first analyze the trade-off between the bandwidth provision and power consumption for different communication schemes. According to the analytic results, a heuristic algorithm PRF is designed to determine the fairness factor with the binary searching. The analyses show that PRF algorithm can obtain the approximate ratio 1- ξ, where ξ is an arbitrarily small positive constant. Meanwhile, this paper also presents another heuristic algorithm JFAP, which uses the offer-and-gain mechanism to reach the Max-Min fairness. The simulation results show that PRF and JFAP algorithms can improve the fairness factor at least 36% and 32% compared with the direct transmission scheme in many situations.

It is significant to deploy a mobile sensor network periodically sweeping from the upriver to the downriver to monitor the water quality of the third large river in China. An important problem in this network is how to maximize the dynamic coverage efficiency while maintain the connectivity of network. To solve this problem, we borrow the idea of flocking-birds model in artificial life field and propose a distributed coverage and connectivity control algorithm DC3. The simulation result shows that the dynamic coverage efficiency of this algorithm is significantly better than that of the random mobility model.

The robust state estimation problem for a class of uncertain neural networks with time-varying delay is studied in this paper. The parameter uncertainties are assumed to be norm bounded. Based on a new bounding technique, a sufficient condition is presented to guarantee the existence of the desired state estimator for the uncertain delayed neural networks. The criterion is dependent on the size of the time-varying delay and on the size of the time derivative of the time-varying delay. It is shown that the design of the robust state estimator for such neural networks can be achieved by solving a linear matrix inequality (LMI), which can be easily facilitated by using some standard numerical packages. Finally, two simulation examples are given to demonstrate the effectiveness of the developed approach.