INFOCOM 2022 Papers

While Mobile CrowdSensing (MCS) has become a popular paradigm that recruits mobile users to carry out various sensing tasks collaboratively, the performance of MCS is frequently degraded due to the limited spatiotemporal coverage in data collection. A possible way here is to incorporate sparse MCS with data inference, where unsensed data could be completed through prediction. However, the spatiotemporal data inference is usually "fractured" with poor performance, because of following challenges: 1) the sparsity of the sensed data, 2) the unpredictability of a spatiotemporal fracture and 3) the complex spatiotemporal relations. To resolve such fracture data issues, we elaborate a data generative model for achieving spatiotemporal fracture data inference in sparse MCS. Specifically, an algorithm named Generative High-Fidelity Matrix Completion (GHFMC) is proposed through combining traditional Deep Matrix Factorization (DMF) and Generative Adversarial Networks (GAN) for generating spatiotemporal fracture data. Along this line, GHFMC learns to extract the features of spatiotemporal data and further efficiently complete and predict the unsensed data by using Binary Cross Entropy (BCE) loss. Finally, we conduct experiments on three popular datasets. The experimental results show that our approach performs higher than the state-of-the-art (SOTA) baselines in both data inference accuracy and fidelity.

Video streaming plays a critical role in the video analytics pipeline and thus its adaptation scheme has been a focus of optimization. As machine learning algorithms have become main consumers of video contents, the streaming adaptation decision should be made to optimize their inference performance. Existing video streaming adaptation schemes for video analytics are usually designed to adapt to bandwidth and content variations separately, which fail to consider the coordination between transmission and computation. Given the nature of batch transmission in video streaming and batch processing in deep learning-based inference, we observe that the choices of the batch sizes directly affects the bandwidth efficiency, the response delay and the accuracy of the deep learning inference in video analytics. In this work, we investigate the effect of the batch size in transmission and processing, formulate the optimal batch size adaptation problem, and further develop the deep reinforcement learning-based solution. Practical issues are further addressed for Implementation. Extensive simulations are conducted for performance evaluation, whose results demonstrate the superiority of our proposed batch adaptive streaming approach over the baseline streaming approaches.

Erasure coding is a storage-efficient redundancy scheme for modern clustered storage systems by storing stripes of data and parity blocks across the nodes of multiple clusters; in particular, locally repairable codes (LRC) continue to be one popular family of practical erasure codes that achieve high repair efficiency. To efficiently adapt to the dynamic requirements of access efficiency and reliability, storage systems often perform redundancy transitioning by tuning erasure coding parameters. In this paper, we apply a stripe merging approach for redundancy transitioning of LRC in clustered storage systems, by merging multiple LRC stripes to form a large LRC stripe with low storage redundancy. We show that the random placement of multiple LRC stripes that are being merged can lead to high cross-cluster transitioning bandwidth. To this end, we design an optimal data placement scheme that provably minimizes the cross-cluster traffic for stripe merging, by judiciously placing the blocks to be merged in the same cluster while maintaining the repair efficiency of LRC. We prototype and implement our optimal data placement scheme on a local cluster. Our evaluation shows that it significantly reduces the transitioning time by up to 43.2% compared to the baseline.

Recent years witnessed an increasing research attention in deploying deep learning models on edge devices for inference. Due to limited capabilities and power constraints, it may be necessary to distribute the inference workload across multiple devices. Existing mechanisms divided the model across edge devices with the assumption that deep learning models are constructed with a chain of layers. In reality, however, modern deep learning models are more complex, involving a directed acyclic graph (DAG) rather than a chain of layers.In this paper, we present EdgeFlow, a new distributed inference mechanism designed for general DAG structured deep learning models. Specifically, EdgeFlow partitions model layers into independent execution units with a new progressive model partitioning algorithm. By producing near-optimal model partitions, our new algorithm seeks to improve the run-time performance of distributed inference as these partitions are distributed across the edge devices. During inference, EdgeFlow orchestrates the intermediate results flowing through these units to fulfill the complicated layer dependencies. We have implemented Edge-Flow based on PyTorch, and evaluated it with state-of-the-art deep learning models in different structures. The results show that EdgeFlow reducing the inference latency by up to 40.2% compared with other approaches, which demonstrates the effectiveness of our design.

Crowdsourcing enables a paradigm to conduct the manual annotation and the analytics by those recruited workers, with their rewards relevant to the quality of the results. Existing dispatchers fail to capture the resource-quality trade-off for video analytics, since the configurations supported by various workers are different, and the workers’ availability is essentially dynamic. To determine the most suitable configurations as well as workers for video analytics, we formulate a non-linear mixed program in a long-term scope, maximizing the profit for the crowdsourcing platform. Based on previous results under various configurations and workers, we design an algorithm via a series of subproblems to decide the configurations adaptively upon the prediction of the worker rewards. Such prediction is based on volatile multi-armed bandit to capture the workers’ availability and stochastic changes on resource uses. Via rigorous proof, the regret is ensured upon the Lyapunov optimization and the bandit, measuring the gap between the online decisions and the offline optimum. Extensive trace-driven experiments show that our algorithm improves the platform profit by 37%, compared with other algorithms.

Lightweight container-based microservice has been widely advocated to promote the elasticity of edge cloud. The inherent layered structure of containers offers a compelling way to cope with the resource scarcity of edge servers through layer sharing, which can significantly increase storage utilization and improve the edge throughput. Recent studies show that it is possible to share layers not only within the same server but also between servers, which microservice deployment can take full advantage of. In this paper, we investigate the problem of how to collaboratively deploy microservices by incorporating both intra-server and inter-server layer sharing to maximize the edge throughput. We formulate this problem into an integer linear programming form and prove it as NP-hard. We propose a randomized rounding based heuristic algorithm, and conduct formal analysis on the guaranteed approximation ratio. Through extensive experiments, we verify the efficiency of our proposed algorithm, and the results demonstrate that it can deploy 6× and 12× more microservice instances, and improve the edge throughput by 27.74% and 38.46% in comparison with state-of-the-art strategies.

Training Graph Neural Networks (GNN) on large graphs is resource-intensive and time-consuming, mainly due to the large graph data that cannot be fit into the memory of a single machine, but have to be fetched from distributed graph storage and processed on the go. Unlike distributed deep neural network (DNN) training, the bottleneck in distributed GNN training lies largely in large graph data transmission for constructing mini-batches of training samples. Existing solutions often advocate data-computation colocation, and do not work well with limited resources where the colocation is infeasible. The potentials of strategical task placement and optimal scheduling of data transmission and task execution have not been well explored. This paper designs an efficient algorithm framework for task placement and execution scheduling of distributed GNN training, to better resource utilization, improve execution pipelining, and expediting training completion. Our framework consists of two modules: (i) an online scheduling algorithm that schedules the execution of training tasks, and the data transmission plan; and (ii) an exploratory task placement scheme that decides the placement of each training task. We conduct thorough theoretical analysis, testbed experiments and simulation studies, and observe up to 67% training speed-up with our algorithm as compared to representative baselines.

The age of data (AoD) is identified as one of the most novel and important metrics to measure the quality of big data analytics for Internet-of-Things (IoT) applications. Meanwhile, mobile edge computing (MEC) is envisioned as an enabling technology to minimize the AoD of IoT applications by processing the data in edge servers close to IoT devices. In this paper, we study the AoD minimization problem for IoT big data processing in MEC networks. We first propose an exact solution for the problem by formulating it as an Integer Linear Program (ILP). We then propose an efficient heuristic for the offline AoD minimization problem. We also devise an approximation algorithm with a provable approximation ratio for a special case of the problem, by leveraging the parametric rounding technique. We thirdly develop an online learning algorithm with a bounded regret for the online AoD minimization problem under dynamic arrivals of IoT requests and uncertain network delay assumptions, by adopting the Multi-Armed Bandit (MAB) technique. We finally evaluate the performance of the proposed algorithms by extensive simulations and implementations in a real test-bed. Results show that the proposed algorithms outperform existing approaches by reducing the AoD around 10%.

This paper tackles a multi-agent bandit setting where M agents cooperate together to solve the same instance of a K-armed stochastic bandit problem. The agents are heterogeneous: each agent has limited access to a local subset of arms and the agents are asynchronous with different gaps between decision-making rounds. The goal for each agent is to find its optimal local arm, and agents can cooperate by sharing their observations with others. While cooperation between agents improves the performance of learning, it comes with an additional complexity of communication between agents. For this heterogeneous multi-agent setting, we propose two learning algorithms, CO-UCB and CO-AAE. We prove that both algorithms achieve order-optimal regret, which is $O\left({{\sum _{i:{{\bar \Delta }_i} > 0}}\log T/{{\tilde \Delta }_i}}\right)$, where ${\tilde \Delta _i}$ is the minimum suboptimality gap between the reward mean of arm i and any local optimal arm. In addition, a careful selection of the valuable information for cooperation, CO-AAE achieves a low communication complexity of O(log T). Last, numerical experiments verify the efficiency of both algorithms.

The continuously increasing time spent on car trips in recent years brings growing attention to the physical and mental health of drivers on roads. As one of the key vital signs, the heartbeat is a critical indicator of drivers' health states. Most existing studies on heartbeat monitoring either require sensor attachment or could only provide sketchy heart rates. Moreover, most approaches require the subject to remain stationary or a quiet measuring environment, which is hard to apply to dynamic driving environments. In this paper, we propose a contactless cardiac cycle monitoring system, mmECG, which leverages Commercial-Off-The-Shelf mmWave radar to estimate the fine-grained heart movements of drivers in moving vehicles. By exploring the principle of mmWave signal-based sensing, we first perform studies in static environments and find the fine-grained heart movements, represented as stages of atria and ventricles in repetitive cardiac cycles, can be captured by the FMCW-based mmWave radar as phase changes in signals. Whereas in driving environments, such phase changes are caused and influenced by not only the heartbeat of drivers but also driving operations and vehicle dynamics. To further extract the minute heart movements of drivers and eliminate other influences in phase changes, we construct a movement mixture model to represent the phase changes caused by different movements, and further design a hierarchy variational mode decomposition (VMD) approach to extract and estimate the essential heart movement in mmWave signals. Finally, based on the extracted phase changes, mmECG reconstructs the cardiac cycle by estimating fine-grained movements of atria and ventricles leveraging a template-based optimization method. Experimental results involving 25 drivers in real driving scenarios demonstrate that mmECG can accurately estimate not only heart rates but also cardiac cycles of drivers in real driving environments.

We discuss Boolean network tomography in a probabilistic routing environment. Although the stochastic behavior of routing can be found in load balancing mechanisms and normal routing protocols, it has not been discussed much in network tomography so far. In probabilistic routing, because monitoring paths are not uniquely determined, a huge number of measurements are generally required to identify the network state. To overcome this difficulty, we propose a network tomography method for efficiently narrowing down the states with a limited number of measurements by iteratively updating the posterior of the states. In this method, we introduce mutual information as a measure of the effectiveness of the probabilistic monitoring path. This enables us to prioritize measurements that are critically effective in identifying the state, thus significantly reducing the number of required measurements. We show that our method has a theoretical guarantee of the approximation ratio (1 – 1/e) on the basis of submodularity analysis. Numerical evaluations show that our method can identify the network states with far fewer measurements than existing methods.

Existing machine learning (ML) model marketplaces generally require data owners to share their raw data, leading to serious privacy concerns. Federated learning (FL) can partially alleviate this issue by enabling model training without raw data exchange. However, data owners are still susceptible to privacy leakage from gradient exposure in FL, which discourages their participation. In this work, we advocate a novel differentially private FL (DPFL)-based ML model marketplace. We focus on the broker-centric design. Specifically, the broker first incentivizes data owners to participate in model training via DPFL by offering privacy protection as per their privacy budgets and explicitly accounting for their privacy costs. Then, it conducts optimal model versioning and pricing to sell the obtained model versions to model buyers. In particular, we focus on the broker’s profit maximization, which is challenging due to the significant difficulties in the revenue characterization of model trading and the cost estimation of DPFL model training. We propose a two-layer optimization framework to address it, i.e., revenue maximization and cost minimization under model quality constraints. The latter is still challenging due to its non-convexity and integer constraints. We hence propose efficient algorithms, and their performances are both theoretically guaranteed and empirically validated.

Cyber search engines, such as Shodan and Censys, have gained popularity due to their strong capability of indexing the Internet of Things (IoT). They actively scan and fingerprint IoT devices for unearthing IP-device mapping. Because of the large address space of the Internet and the mapping’s mutative nature, efficiently tracking the evolution of IP-device mapping with a limited budget of scans is essential for building timely cyber search engines. An intuitive solution is to use reinforcement learning to schedule more scans to networks with high churn rates of IP-device mapping. However, such an intuitive solution has never been systematically studied. In this paper, we take the first step toward demystifying this problem based on our experiences in maintaining a global IoT scanning platform. Inspired by the measurement study of large-scale real-world IoT scan records, we land reinforcement learning onto a system capable of smartly scanning IoT devices in a principled way. We disclose key parameters affecting the effectiveness of different scanning strategies, and find that our system would achieve growing advantages with the proliferation of IoT devices.

Oblivious routing distributes traffic from sources to destinations following predefined routes with rules independent of traffic demands. While finding optimal oblivious routing is intractable for general topologies, we show that it is tractable for structured topologies often used in datacenter networks. To achieve this, we apply graph automorphism and prove the existence of the optimal automorphism-invariant solution. This result reduces the search space to targeting the optimal automorphism-invariant solution. We design an iterative algorithm to obtain such a solution by alternating between two linear programs. The first program finds an automorphism-invariant solution based on representative variables and constraints, making the problem tractable. The second program generates adversarial demands to ensure the final result satisfies all possible demands. Since, the construction of the representative variables and constraints are combinatorial problems, we design polynomial-time algorithms for the construction. We evaluate proposed iterative algorithm in terms of throughput performance, scalability, and generality over three potential applications. The algorithm i) improves the throughput up to 87.5% over a heuristic algorithm for partially deployed FatTree, ii) scales for FatClique with a thousand switches, iii) is applicable to a general structured topology with non-uniform link capacity and server distribution.

Mobile robot-assisted book inventory such as book identification and book order detection has become increasingly popular in smart library, replacing the manual book inventory which is time-consuming and error-prone. The existing systems are either computer vision (CV)-based or RFID-based, however several limitations are inevitable. CV-based systems may not be able to identify books effectively due to low accuracy of detecting texts on book spine. RFID tags attached to books can be used to identify a book uniquely. However, in high tag density scenarios such as library, tag coupling effects of adjacent tags may seriously affect the accuracy of tag reading. To overcome these limitations, this paper presents a novel RFID and CV fusion system for Book Inventory using mobile robot (RC-BI). RFID and CV are first used individually to obtain book order, then the information will be fused by the sequence based matching algorithm to remove ambiguity and improve overall accuracy. Specifically, we address three technical challenges. We design a deep neural network (DNN) model with multiple inputs and mixed data to filter out interference of RFID tags on other tiers, and propose a video information extracting schema to extract book spine information accurately, and use strong link to align and match RFID- and CV-based timestamp vs. book-name sequences to avoid errors during fusion. Extensive experiments indicate that our system achieves an average accuracy of 98.4% for tier filtering and an average accuracy of 98.9% for book order, significantly outperforming the state-of-the-arts.

Deep learning has shown impressive performance in semantic segmentation, but it is still unaffordable for resource-constrained mobile devices. While offloading computation tasks is promising, the high traffic demands overwhelm the limited bandwidth. Existing compression algorithms are not fit for semantic segmentation, as the lack of obvious and concentrated regions of interest (RoIs) forces the adoption of uniform compression strategies, leading to low compression ratios or accuracy. This paper introduces STAC, a DNN-driven compression scheme tailored for edge-assisted semantic video segmentation. STAC is the first to exploit DNN’s gradients as spatial sensitivity metrics for spatial adaptive compression and achieves superior compression ratio and accuracy. Yet, it is challenging to adapt this content-customized compression to videos. Practical issues include varying spatial sensitivity and huge bandwidth consumption for compression strategy feedback and offloading. We tackle these issues through a spatiotemporal adaptive scheme, which (1) takes partial strategy generation operations offline to reduce communication load, and (2) propagates compression strategies and segmentation results across frames through dense optical flow, and adaptively offloads keyframes to accommodate video content. We implement STAC on a commodity mobile device. Experiments show that STAC can save up to 20.95% of bandwidth without losing accuracy, compared to the state-of-the-art algorithm.

Unmanned aerial vehicle (UAV)-assisted computation paradigms have been treated as the new common in the integrated space-air-ground networks in B5G and 6G era. However, providing services solely from the perspective of the UAVs can not ensure a high Quality of Experience (QoE) at the user devices (UDs). Therefore, this paper presents a user experience-oriented service provision model for UAV-aided mobile edge computing (MEC) systems. First, a novel metric called shrinkage ratio is defined to reflect the experience at the UDs, and then the promotion of the QoE is formulated as a shrinkage ratio minimization problem. Second, a three-step strategy is adopted to tackle the problem which is non-convex: 1) a posterior method is adopted to eliminate the unknown upper bounds; 2) the non-convex constraints are approximately converted to convex by applying the first order Taylor expansion and are handled by SCA technique; 3) an algorithm for derive an accurate estimation in step 1) is put forward. Third, an initialization scheme for UAV trajectory is proposed by applying TSP technique. Finally, numerical results are given to validate our proposed design.

This paper studies the problem of connectivity maintenance in adversarial uncertain networks, where a defender prevents the largest connected component from being decomposed by an attacker. In contrast with its deterministic counterpart, connectivity maintenance in an uncertain network involves additional testing on edges to determine their existence. To this end, by modeling a general uncertain network as a random graph with each edge associated with an existence probability and a testing cost, our goal is to design a general adaptive defensive strategy to maximize the expected size of the largest remaining connected component with minimum expected testing cost and, moreover, the strategy should be independent of the attacking patterns. The computational complexity of the connectivity maintenance problem is unraveled by proving its NP-hardness. To accurately tackle the problem, based on dynamic programming we first propose an optimal defensive strategy for a specific class of uncertain networks with uniform testing costs. Thereafter multi-objective optimization is adopted to generalize the optimal strategy for general uncertain networks through weighted sum of normalized size and cost. Due to the prohibitive price of an optimal strategy, two approximate defensive strategies are further designed to pursue decent performance with quasilinear complexity. We first derive a heuristic approach by quantifying the edge vulnerability through an analogy from the degree centrality in deterministic networks to the probability degree and connectivity weight in uncertain networks. For performance guarantee, we then devise an adaptive greedy policy incorporating the minimax rule from game theory, which minimizes the possible loss suffered by the defender in a worst-case scenario caused by the attacker and has an approximation ratio of (1 − 1/e). Extensive experiments on both synthetic and real-world network datasets under diverse attacking patterns demonstrate the superiority of the proposed strategies over baselines.

The great popularity of smartwatches leads to a growing demand for smarter interactive systems. Hand gesture is suitable for interaction due to its unique features. However, the existing single-modal gesture interactive systems have different biases in diverse scenarios, which makes it intractable to be applied in real life. In this paper, we propose a multi-modal smartwatch interactive system named Mudra, which fuses vision and Inertial Measurement Unit (IMU) signals to recognize and identify hand gestures for convenient and robust interaction. We carefully design a parallel attention multi-task model for different modals, and fuse classification results at the decision level with an adaptive weight adjustment algorithm. We implement a prototype of Mudra and collect data from 25 volunteers to evaluate its effectiveness. Extensive experiments demonstrate that Mudra can achieve 95.4% and 92.3% F1-scores on recognition and identification tasks, respectively. Meanwhile, Mudra can maintain stability and robustness under different experimental settings.