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 a novel 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

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.

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.

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.

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.

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 towards 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 one-second-long audio segments demonstrate that it can detect and measure rain with 92.0% and 93.9% True Positive Rates (TPRs) respectively.