Graph Neural Networks (GNNs) have shown remarkable effectiveness across various applications, but their computational complexity poses significant scalability challenges. To this end, GNN-to-MLP Knowledge Distillation (KD) methods transfer relational inductive biases from GNNs to MLPs, equipping MLPs with graph-aware capabilities that rival or even surpass those of their teacher GNNs. However, a theoretical foundation for understanding GNN-to-MLP KD is still missing. In this paper, we provide a theoretical analysis of how knowledge distillation unlocks the potential of MLPs for graph tasks from the perspective of training dynamics. We demonstrate that label alignment in KD fundamentally reshapes the Neural Tangent Kernel (NTK) matrix of student MLPs, enabling them to learn the teacher model’s implicit graph bias. We further investigate finer-grained distillation paradigms and reveal that conventional layer-wise output alignment fails to effectively align the deep-layer graph propagation outcomes. To address this, we propose Dual-Stream Aligned MLP (DA-MLP), which incorporates complementary graph filters in a dual-stream architecture. This approach simultaneously enhances feature space dimensionality for improved representation alignment and preserves graph signals across different frequency bands. Comprehensive experiments on seven benchmark datasets validate that DA-MLP can be seamlessly integrated into existing knowledge distillation frameworks for performance enhancements in both transductive and inductive settings.

Zhiyuan Yu, Shijian Xiao, Cam-Tu Nguyen, Zhangyue Yin, Lekai Xing, Wenzhong Li, Sanglu Lu. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2026.

The rapid growth of web content has spurred the widespread adoption of on-device AI assistants powered by large language models (LLMs). However, deploying and personalizing these assistants in real-world environments remains challenging due to limited annotation budgets and scarce on-device fine-tuning resources. Existing edge–cloud collaboration frameworks typically rely on costly cloud-based supervision or perform full-layer finetuning, leading to inefficiencies in both computation and adaptation. To address these limitations, we propose EcoTune, a budget-constrained framework for efficient edge–cloud collaborative adaptation. EcoTune jointly optimizes representative data selection for cloud annotation and selective on-device model adaptation within a unified closed-loop process. Specifically, it employs a multi-armed bandit–based strategy to identify highvalue user interactions for cloud supervision and a layer importance–driven adaptation mechanism to update only critical components of the small language model (SLM). This coordinated optimization enables dynamic, resource-efficient personalization under stringent annotation and tuning budgets. Experiments on real-world testbeds demonstrate that EcoTune achieves up to 20%-60% reduction in annotation costs and significantly lowers fine-tuning memory consumption compared to state-of-the-art baselines, providing a practical and scalable solution for personalized on-device LLMs.

Time series analysis is a fundamental data mining task that has made encouraging progress in many real-world scenarios. Supervised training methods based on empirical risk minimization have proven their effectiveness on specific tasks and datasets. However, the acquisition of well-annotated data is costly, and a large amount of unlabeled series data is under-utilized. Due to distributional shifts across various domains and different patterns of interest across multiple tasks. The problem of cross-domain multi-task migration remains a significant challenge. To address these problems, this article proposes a novel cross-domain approach based on Wave Quantization for Time Series (termed as WQ4TS), which can be combined with any advanced time series model and applied to diverse downstream tasks. Specifically, we transfer the data from different domains into a common spectral latent space and enable the model to learn the temporal pattern knowledge of different domains directly from the common space and utilize it for the inference of downstream tasks, thereby mitigating the challenge of heterogeneous migration. The establishment of spectral latent space brings at least three benefits, cross-domain migration capability thus adapting to zero- and few-shot scenarios without relying on priori knowledge, general compatible cross-domain framework without changing the existing model structure, and robust modeling capability thus achieving SOTA results in multiple downstream tasks. To demonstrate the effectiveness of the proposed approach, we conduct extensive experiments including three important tasks: forecasting, imputation, and classification. And three common real-world scenarios are simulated: full-data, few-shot, and zero-shot. The proposed WQ4TS achieves the best performance on 87.5% of all tasks. Concretely, WQ4TS achieved 25.8% and 44.1% improvements in MSE metric for few-shot and zero-shot forecasting tasks, respectively, and demonstrated excellent 24.9% increase in average accuracy on few-shot classification tasks. The source codes of WQ4TS are publicly available on https://github.com/Xiang-Kai/WQ4TS .

Speech enhancement is crucial for reliable communication in noisy environments. However, the lack of a priori knowledge about target speech characteristics in conventional systems often leads to erroneous extraction of interfering speech as desired signals during noise suppression, significantly compromising system performance. Recently, researchers have proposed to use the side-channel signal as an assist to denoise noisy speech. This paper proposes BoneSE, a multimodal speech enhancement approach using bone conduction. The basic idea of BoneSE is to perceive the bone-conducted sound with an IMU sensor embedded in the Commercial Off-The-Shelf (COTS) earphone and then leverage the correlations between the bone conduction signal and audio signal for speech enhancement. However, the lack of high-frequency components in the IMU modality brings data imbalance and hinders data fusion. To address this challenge, we explore and model the relationship between multimodal signals and design a fusion module according to the time and frequency correlation. Moreover, to balance fast processing and denoising performance, we propose bone conduction-based noise level metrics to measure the noise level. To accommodate different noise levels, we propose an adaptive model selection approach based on reinforcement learning to select the proper denoising model, thereby optimizing the latency. Experiments on two datasets show that the proposed method performs favorably against state-of-the-art methods and can enhance speech in low SNR scenarios.

Graph Neural Networks (GNNs) have proven effective and typically benefit from pre-training on accessible graphs to enhance performance on tasks with limited labeled data. However, existing GNNs are constrained by the ``one-domain-one-model'' limitation, which restricts their effectiveness across diverse graph domains. In this paper, we tackle this problem by developing a method called Multi-Domain Pre-training for a Unified GNN Model (MDP-GNN). This method is based on the philosophical notion that everything is interconnected, suggesting that a latent meta-domain exists to encompass the diverse graph domains and their interconnections. MDP-GNN seeks to identify and utilize this meta-domain to train a unified GNN model through three core strategies. Firstly, it integrates node feature semantics from different domains to create unified representations. Secondly, it employs a bi-level learning strategy to build a domain-synthesized network that identifies latent connections to facilitate cross-domain knowledge transfer. Thirdly, it uses Wasserstein distance to map diverse domains into the common meta-domain for graph distribution alignment. We validate the effectiveness of MDP-GNN through theoretical analysis and extensive experiments on four real-world graph datasets, showing its superiority in enhancing GNN performance across diverse domains.

Graph transfer learning endeavors to develop a Graph Neural Network (GNN) model in a fully-labeled source domain, with the intention of deploying it on a target domain that has limited labeled data for inference. We reveal that prevalent graph transfer learning methods are susceptible to the homophily shift problem. This issue arises from the divergence in homophily structures between the source and target graphs, leading to a notable deterioration in the performance of GNN models. In this paper, we introduce a novel Contextual Structural Graph Neural Network (CS-GNN) method, leveraging a tailored attention mechanism to apprehend a variety of local structural cues, facilitating structural knowledge transfer across domains. It features an ego-network module to distill local structural diversity and a moment-based approach to gauge structural patterns without needing ground-truth labels. CS-GNN crafts a feature smoothness matrix from node attributes, guiding a customized attention mechanism for feature aggregation. A group-wise fairness loss is employed to balance learning across various structural patterns, enhancing the model's ability to transfer knowledge across domains. Comprehensive experiments conducted on six benchmark datasets substantiate the superiority of CS-GNN over the state-of-the-art methods, demonstrating significant improvements in accuracy and robustness against homophily shifts.

As the low-altitude economy expands, Unmanned Aerial Vehicles (UAVs) have become essential across a variety of applications. However, non-cooperative UAVs threaten personal privacy and public safety, especially when carrying dangerous payloads. Current UAV detection methods primarily rely on computer vision, which often fails in severe weather conditions. This paper introduces mmUAVsense, a mmWave-based system designed for detecting and identifying UAVs in complex environments. In addition to detecting UAVs, mmUAVsense can also estimate the rotational speed of their propellers, which offers valuable information for assessing the potential payload. A key challenge in detecting UAVs is their small Radar Cross Section (RCS), which makes them easily masked by the environment, especially when flying near large objects. To address this issue, we propose a Moving Target Indicator (MTI) to calculate the time-spatial difference, which helps suppress static environmental clutter and make the dynamic reflection from the UAV more noticeable. To differentiate UAVs from other flying objects, we exploit the unique harmonic feature in the UAV’s Doppler spectrum, caused by the rapid spinning of its propellers, to identify UAVs among other airborne objects. To estimate the UAV’s rotational speed, we analyze the relationship between harmonic features and propeller speed, and propose to use Chirp-Z Transformation (CZT) to accurately extract the frequency from the spectrum. We have implemented a system prototype in various outdoor environments, and extensive experiments demonstrate that our system can identify UAVs with over 95% accuracy, with an average rotational speed error of just 3.8%. Based on the existing UAV model, our rotary-sensing-based system can sense the UAV’s extra load weight with only 8 grams of average error.

Graph anomaly detection has attracted great attention with wide applications. One mainstream approach for graph anomaly detection is built upon the graph reconstruction framework. However, we observe that existing work mainly relies on same-modal reconstruction (e.g., reconstructing attributes from attributes), which may be less effective in more complex cases. This paper presents a new graph anomaly detection method via cross-modal reconstruction. Unlike existing work, the key idea of this work is to reconstruct node attributes from graph structure. This design enables the detection model to better understand the correlations between node attributes and graph structure, thus being more effective to various types of anomalies. We evaluate the proposed method on four real-world datasets, three types of anomalies, and against 15 existing baselines. The results demonstrate the effectiveness of the proposed method.

Graph Neural Networks (GNNs) have demonstrated remarkable effectiveness across various tasks but are often hindered by their high computational overhead. GNN-to-MLP distillation provides a promising remedy by transferring knowledge from complex GNNs to lightweight MLPs. However, existing methods largely overlook the differences in aggregation mechanisms and heterogeneous architectures. Simplifying such intricate information into MLP potentially causes information loss or distortion, ultimately resulting in suboptimal performance. This paper proposes an aggregation mechanism enhanced GNN distillation framework (AMEND). AMEND introduces multi-scope aggregation context preservation to replicate the teacher's broad aggregation scopes and an aggregation-enhanced centered kernel alignment method to match the teacher's aggregation patterns. To ensure efficient and robust knowledge transfer, we integrate a manifold mixup strategy, enabling the student to capture the teacher's insights into mixed data distributions. Experimental results on 8 standard and 4 large-scale datasets demonstrate that AMEND consistently outperforms state-of-the-art distillation methods.

Probabilistic time series forecasting has attracted an increasing attention in machine learning community for its potential applications in the fields of renewable energy, traffic management, healthcare, etc. Previous research mainly focused on extracting long-range dependencies for point-wise prediction, which fail to capture complex temporal patterns and statistical characteristics for probabilistic analysis. In this paper, we propose a novel pattern-mixture decomposition method that decomposes long-term series into quantile drift, divergence patterns, and Gaussian mixture components, which can effectively capture the intricate temporal patterns and stochastic characteristics in time series. Based on pattern-mixture decomposition, we propose a novel Transformer-based model called QuantileFormer for probabilistic time series forecasting. It takes the the comprehensive drift-divergence mixture patterns as features, and designs a variational inference based fusion Transformer architecture to generate quantile prediction results. Extensive experiments show that the proposed method consistently boosts the baseline methods by a large margin and achieves state-of-the-art performance on six real-world benchmarks.

Human pose recognition is a crucial task in millimeter-wave point cloud processing, playing an important role in scenarios such as autonomous driving, human-computer interaction, and medical monitoring. Currently, most approaches for recognizing human poses from millimeter-wave point clouds rely on deep learning methods. However, due to the impact of multipath effects in wireless signals, millimeter-wave point clouds not only contain human pose information but also include environmental noise. The neural network extracts features from all point clouds equally, which leads to errors in human pose recognition caused by environmental noise interference. To address this limitation, we propose TSDA, a novel Temporal-Spatial Data Augmentation method specifically tailored for human pose recognition in millimeter-wave point clouds. TSDA leverages the temporal consistency and spatial continuity of human pose point clouds to distinguish the real human point clouds from environmental noise point clouds. It quantifies the probability of a point cloud belonging to the human pose target through confidence measures, which can be used to augment the raw point clouds. Additionally, we introduce a prototype system based on cross-attention mechanisms to validate the impact of data augmentation on pose recognition performance. Experimental results show that, compared to the state-of-the-art deep learning-based methods, TSDA achieves an average reduction of 1.9cm in human pose recognition error.

Video analytics pipelines (VAPs) have been a paradigm for large-scale video analytics. Due to temporal redundancy in video, frame filtering is widely used in VAPs to reduce analysis workload. However, existing works overlook a limitation: while inference operates only on selected frames, decoders must still process many redundant frames due to codec dependencies, leading to over-decoding trap. This limitation stems from the reference-based design in modern codecs, which require decoding preceding frames to reconstruct any selected one. As a result, over-decoding has become the practical bottleneck in VAPs using modern decoders, highlighting a critical but under-explored problem. To address this issue, we propose ParaDeco, a high-throughput video analytics framework featuring a novel frame-level parallel generative decoder. Unlike traditional decoders, ParaDeco adopts a decode-what-matters approach with decoupled frame dependencies. To decode arbitrary frames independently, ParaDeco generates frame-wise features as standalone skeletons using compressed video metadata, then predicts pseudo frames maintaining semantic consistency with original frames. Moreover, ParaDeco identifies which frames truly matter for analysis via delicate contribution-based frame filtering. We implement ParaDeco on a cloud server and evaluate it on large-scale real-world video datasets. Our experimental results show that ParaDeco achieves a 2.76× speedup on average compared to state-of-the-art VAPs.

Recent advances in sign language research have benefited from CNN-based backbones, which are primarily transferred from traditional computer vision tasks (\eg object detection, image recognition). However, these CNN-based backbones usually excel at extracting features like contours and texture, but may struggle with capturing sign-related features. To capture such sign-related features, SignGraph model extracts the cross-region sign features by building the Local Sign Graph (LSG) module and the Temporal Sign Graph (TSG) module. However, we emphasize that although capturing cross-region dependencies can improve sign language performance, it may degrade the representation quality of local regions. To mitigate this, we introduce MixSignGraph, which represents sign sequences as a group of mixed graphs for feature extraction. Specifically, besides the LSG module and TSG module that model the intra-frame and inter-frame cross-regions features, we design a simple yet effective Hierarchical Sign Graph (HSG) module, which enhances local region representations following the extraction of cross-region features, by aggregating the same-region features from different-granularity feature maps of a frame, \ie to boost discriminative local features. In addition, to further improve the performance of gloss-free sign language task, we propose a simple yet counter-intuitive Text-based CTC Pre-training (TCTC) method, which generates pseudo gloss labels from text sequences for model pre-training. Extensive experiments conducted on the current five sign language datasets demonstrate that MixSignGraph surpasses the most current models on multiple sign language tasks across several datasets, without relying on any additional cues. Code and models are available at: \href{https://github.com/gswycf/SignLanguage}{\textcolor{blue}{https://github.com/gswycf/SignLanguage}}.

Person re-identification (Re-ID) aims to retrieve images of the same individual from a gallery captured by disjoint camera views. A major challenge lies in learning robust and discriminative representations under varying human poses and cluttered backgrounds. Recent approaches based on Generative Adversarial Networks (GANs) attempt to mitigate these issues by augmenting training data via pose or style transfer. However, despite generating visually plausible samples, such methods often introduce redundant or low-quality data, which can hinder feature learning, slow down convergence, and lead to overfitting. In this paper, we propose PGQE, a Pose-Guided Query Enhancement framework that synthesizes pose-normalized query images during inference, thereby avoiding the drawbacks of GAN-based data augmentation in training. Motivated by the observation that queries with cleaner backgrounds and canonical poses yield better matching performance, PGQE leverages high-quality gallery samples to extract target poses and guide image generation. To ensure the quality and discriminability of the generated queries, we impose two constraints: identity consistency with the source image and pose consistency with the extracted target pose. Extensive experiments on Market-1501, CUHK03, and MSMT17 demonstrate that PGQE significantly improves ReID accuracy and outperforms several state-of-the-art methods.

Deep neural networks (DNNs) such as convolutional networks and Transformers are increasingly deployed to provide intelligent service. However, enabling large-scale DNNs in an infrastructure-less mobile crowd encounters the challenges of high resource consumption, poor performance, and low service availability. This paper proposes CrowdNet, a novel device-todevice (D2D) collaborative inference framework for dynamic mobile environments. CrowdNet introduces a CellNet architecture as its core component, designed as lightweight DNNs ideal for deployment and operation on resource-constrained mobile devices. The CellNets can perform inference tasks either independently or collaboratively to ensure robustness against network disruptions. A topology expansion method is utilized to create an inference flow from the physical communication topology, enabling the distributed operation of inference tasks. To handle the dynamic participation of mobile devices, CrowdNet employs fine-tuning adaptation for flexible assembly and collaborative inference. A reinforcement learning (RL)-based approach is introduced to optimize inference topology. Trained with a multiobjective optimization strategy, CrowdNet can enhance overall performance while maintaining individual CellNet functionality. Extensive experiments based on mobile network testbed and realworld datasets validate the effectiveness of CrowdNet on various intelligent tasks, exhibiting remarkable performance gains and robustness compared to state-of-the-art approaches.

With the rise of intelligent systems like assisted driving and robotics, all-weather target identification and 3D localization systems have become crucial for reliable obstacle avoidance and navigation. However, vision-based methods struggle to provide accurate target locations under low light or bad weather. Radar-based solutions like mmWave radar and LiDAR are robust but hindered by high costs and challenges in recognizing target identities at scale. In this paper, we propose alow-cost, all-weather target identification and 3D localization systembased onLED-tags, which system can address the needs of intelligent systems for obstacle avoidance in complex environments. We explore the backscatter communication of LED devices and design adual-modal LED-Tag, which includes two features: a backscatter RF signal detectable by RF devices and visual light spot information detectable by cameras, both sharing the same ID. To enhance the limited backscatter capability, we propose amulti-branch parallel modelthat enhances the signal strength using beamforming synthesis and achannel adjustment mechanismto improve robustness in complex environments, ensuring accurate 3D localization. For multi-target identification, we design an LED-tag encoding system, assigning each tag a unique encoding sequence. Each target's identity can be recognized with our customizedID decoding method, which leverages prior information and time-domain sampling characteristics. Extensive experimental results show that the backscatter communication and target detection range of LED-tags can reach15m. Moreover, the system achieves anaverage localization error of 7.3cm within a 5m range, demonstrating the system's excellent performance in terms of practicality and accuracy.

Edge video analytics typically rely on conventional encoding standards to transmit device visual data for server-side inference. Unfortunately, general-purpose compression solutions retain unnecessary visual data that does not contribute to accuracy, resulting in significant latency throughout Video Analytics Pipeline (VAP). While previous approaches have made partial progress, they cannot systematically eliminate VAP redundancy due to uncoordinated subsystem-level optimization. Achieving complete redundancy elimination presents a major challenge, as a lack of spatio-temporal coordination risks offsetting latency gains with computational overhead (associated with redundancy elimination).Crucioovercomes these limitations with an end-to-edge framework that integrates temporally adaptive frame filtering and coordinated video compression. It leverages redesigned asymmetric autoencoders to synchronize inter-frame temporal compression with intra-frame spatial feature extraction. Additionally,Crucioemploys a one-pass decoding mechanism for encoded critical frames and dynamically adjusts batching scales to minimize latency. Empirical results demonstrateCrucio's superiority, outperforming existing solutions (e.g., DDS, Reducto, and STAC) by over a 31% reduction in end-to-end latency at 0.9 accuracy thresholds.

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.

Enhancing the networking system with appropriate functions is a longstanding goal. Unfortunately, in today’s large-scale high-speed data centers, the feature velocity of network functions is slow because it is hard to verify the function in realistic scenarios. Recent advances in programmable switching ASICs have enabled the network data plane to move beyond its traditional role of packet forwarding. However, the current compromise between performance and flexibility results in limitations such as restricted memory/computation resources and programmable models. These limitations make it challenging for programmable switches to offer more features and to be deployed in large-scale production environments. In response, we present CLIP, a framework that works in collaboration with programmable devices and commodity servers to enhance the validation and deployment velocity of features. CLIP defines a cross-platform function definition framework and provides a set of tools to reduce the complexity of manually writing cross-platform programs. We propose an automatic traffic placement and scaling mechanism to coordinate packet processing performance across heterogeneous devices. Compared with software-based Network Functions (NFs), CLIP achieves a throughput ranging from$1.36\times $to$16.06\times $under different realistic traffic loads. Through the development and deployment of three self-defined functions within a realistic testbed, we demonstrate the feasibility and efficiency of CLIP.

Increased videos captured by widely deployed cameras are being analyzed by computer vision-based Deep Neural Networks (DNNs) on servers rather than being streamed for humans. Unfortunately, the conventional codecs (e.g., H.26x and MPEG-x) originally designed for video streaming lack content-aware feature extraction and hinder machine-centric video analytics, making it difficult to achieve the required high accuracy with tolerable delay. Neural codecs (e.g., autoencoder) now hold impressive compression performance and have been widely advocated in video streaming. While autoencoder shows transformative potential, the application in video analytics is hampered by low accuracy in detecting small objects of high-resolution videos and the serious challenges posed by multi-video streaming. To this end, we propose AdaStreamer with adaptive neural codecs to enable real machine-centric high-accuracy multi-video analytics. We also investigate how to achieve optimal accuracy under delay constraints via careful scheduling in Compression Ratios (CRs, the ratio of the compressed size to the original data size) and bandwidth allocation, and further propose a Markov-based Adaptive Compression and Bandwidth Allocation algorithm (MACBA). We have practically developed a prototype of AdaStreamer, based on which extensive experiments verify its accuracy improvement (up to 15%) compared to state-of-the-art coding and streaming solutions.

Using multiple Unmanned Aerial Vehicles (UAVs) in video surveillance greatly enhances real-time monitoring of large areas. However, images captured by UAVs are separate and limited in view, making stitching crucial for a comprehensive perspective. Current methods combine sensor and visual modalities for video stitching but face challenges in robustness and real-time performance. Environmental disturbances increase errors in sensor and visual data, reducing accuracy and stability, while single-frame stitching incurs high computational costs and slow speeds. To address these issues, we propose SkyEye , a real-time video stitching method for UAV surveillance systems based on multi-modal perception. Specifically, we design a mutual verification method to assess the quality of visual and inertial data. Frames with higher confidence are prioritized for precise stitching. To reduce computational costs, we employ a reference frame scheme that reuses the perspective transformation and feature points of the reference frame for subsequent frames. Meanwhile, we design a video stitching framework based on a per-frame parallel unit to speed up the algorithm execution. We have implemented a prototype of SkyEye and carried out extensive evaluations. Experiment results show that SkyEye outperforms state-of-the-art methods, improving speed by 66.1% and accuracy by 28.2%.

Graph Neural Networks (GNNs) have emerged as a powerful tool for modeling graph-structured data, exhibiting remarkable potential in applications such as social networks, recommendation systems, and molecular structures. However, the conventional GNNs perform node-level feature aggregation from neighbors without considering graph-label information, which leads to the misaligned embedding problem that may cause a detrimental effect on graph-level tasks such as graph classification. In this paper, we propose a novel label-attentive distillation method called LAD-GNN for graph representation learning to solve this problem. It alternatively trains a teacher model and a student GNN with a distillation-based approach. In the teacher model, a label-attentive encoder is proposed to encode the label information fusing with the node features to generate ideal embedding. In the student model, the ideal embedding is used as intermediate supervision to urge the student GNN to learn class-friendly node embedding to facilitate graph-level tasks. Generally, LAD-GNN is an enhanced GNN training approach that can be incorporated with arbitrary GNN backbone to improve performance without significant increase of computational cost. Extensive experiments with 7 GNN backbones based on 10 benchmark datasets show that LAD-GNN improves the SOTA GNNs in graph classification accuracy. The source codes of LAD-GNN are publicly available on https://github.com/XiaobinHong/LAD-GNN.

Despite the recent success of sign language research, the widely adopted CNN-based backbones are mainly migrated from other computer vision tasks, in which the contours and texture of objects are crucial for identifying objects. They usually treat sign frames as grids and may fail to capture effective cross-region features. In fact, sign language tasks need to focus on the correlation of different regions in one frame and the interaction of different regions among adjacent frames for identifying a sign sequence. In this paper, we propose to represent a sign sequence as graphs and introduce a simple yet effective graph-based sign language processing architecture named SignGraph, to extract crossregion features at the graph level. SignGraph consists of two basic modules: Local Sign Graph (LSG) module for learning the correlation of intra-frame cross-region features in one frame and Temporal Sign Graph (TSG) module for tracking the interaction of inter-frame cross-region features among adjacent frames. With LSG and TSG, we build our model in a multiscale manner to ensure that the representation of nodes can capture cross-region features at different granularities. Extensive experiments on current public sign language datasets demonstrate the superiority of our SignGraph model. Our model achieves very competitive performances with the SOTA model, while not using any extra cues. Code and models are available at: https://github.com/gswycf/SignGraph.

Nowadays, object detection and 3D tracking have become key technologies for intelligent system or robot navigation to realize automatic obstacle avoidance and target detection, especially in low-light and night vision scenarios. In this paper, we explore the backscattering capability of LEDs and implement a multi-modal tag LED-tag to realize object detection and 3D tracking. Our basic idea is to utilize the fact that feeding modulation signals to an LED-tag can generate both RF and visual features. We fuse the depth of field information perceived from the RF domain and the pixel coordinates obtained from the visual domain to derive a 3D position by matching the decoded ID. In the RF domain, the depth of field is acquired through ultra-wideband channel measurements and estimated phase. In the visual domain, the pixel coordinate in the XOY coordinates can be extract from the image and mapped into 2D spatial coordinates. To address the limited backscatter capability of the LED-tag, we propose a multiple parallel branch model to increase backscatter paths for amplifying the LED-tag's backscattering intensity. Additionally, we propose a decoding ID scheme that utilizes a priori knowledge and repetitive samples to restore the IDs whose encoding frequency is higher than four times the sampling rate. We have implemented a prototype system and evaluated its performance in real-world environments. Extensive experimental results show that LED-tag can backscatter RF signals ranging up to 15m. Besides, the system achieves an average position error of 8cm within the range of 3m.

Time series analysis has a wide range of applications in the fields of weather forecasting, traffic management, fault detection, intelligent operation, etc. In the real world, time series typically consist of dynamic fluctuations and mixtures of periodicities, which bring challenges on modeling and analyzing their patterns. To overcome the complexities, a common approach is to decompose long-term time series into sub-components for easier analysis. Unlike conventional time series decomposition that decouples a series into the trend and seasonal parts, we proposed a novel triple decomposition method to decouple a long-term series into three components: trend-part, regular-part, and fluctuant-part. Notably, the third part is a particular component that represents the dynamic spectral fluctuation in time series with the formulation of spectrum gradient. Based on triple decomposition, we propose a novel task-general deep learning model called TS3Net for long-term series analysis. It introduces a temporal-frequency block (TF-Block) with a multi-branch structure to expand the time series into a 2D temporal-frequency distribution. Subsequently, deep representation can be learned by a vision architecture that captures the dynamic variations from the complex multi-periodic series. The decomposed components are processed by TS3Net individually, and their results are integrated to form the final result for time series analysis. We conduct extensive experiment based on six open datasets to evaluate the proposed method in comparison with 10 baselines. Numerical results show that TS3Net significantly outperforms the state-of-the-art methods on both time series forecasting and imputation tasks. The source codes of TS3Net are publicly available on https://github.com/Xiang-Kai/TS3Net.

Recent years have witnessed the unprecedented performance of convolutional networks in image super-resolution (SR). SR involves upscaling a single low-resolution image to meet application-specific image quality demands, making it vital for mobile devices. However, the excessive computational and memory requirements of SR tasks pose a challenge in mapping SR networks on a single resource-constrained mobile device, especially for an ultra-high target resolution. This work presents TileSR, a novel framework for efficient image SR through tile-granular parallel offloading upon multiple collaborative mobile devices. In particular, for an incoming image, TileSR first uniformly divides it into multiple tiles and selects the top-K tiles with the highest upscaling difficulty (quantified by mPV). Then, we propose a tile scheduling algorithm based on multi-agent multiarmed bandit, which attains the accurate offload reward through the exploration phase, derives the tile packing decision based on the reward estimates, and exploits this decision to schedule the selected tiles. We have implemented TileSR fully based on COTS hardware, and the experimental results demonstrate that TileSR reduces the response latency by 17.77-82.2% while improving the image quality by 2.38-10.57% compared to other alternatives.

There is an increasing demand for analyzing live surveillance video streams via large-scale camera networks, particularly for applications in public safety and smart cities. To address the conflict between resource-intensive detection models and limited capabilities of cameras, a detection-with-tracking framework has gained prominence. However, since trackers are vulnerable to occlusions and new object appearances, frequent detections are required to calibrate the results, leading to varying detection demands that depends on video content. Consequently, we propose a mechanism for content-aware analytics on collaborative cameras, denoted as VisFlow, to increase the quality of detections and achieve the latency requirement by fully utilizing camera resources. We formulate such a problem as a non-linear, integer program with a long-term perspective, aimed at maximizing detection accuracy. An online mechanism, underpinned by a queue-based algorithm and randomized rounding, is then devised to dynamically orchestrate detection workloads among cameras, thus adapting to fluctuating detection demands. Via rigorous proof, both dynamic regret regarding overall accuracy and the transmission budget are ensured in the long run. The testbed experiments on Jetson Kits demonstrate that VisFlow improves accuracy by 18.3% over the baselines.

Increased videos captured by widely deployed cameras are being analyzed by computer vision-based Deep Neural Networks (DNNs) on servers rather than being streamed for humans. Unfortunately, the conventional codecs (e.g., H.26x and MPEG-x) originally designed for video streaming lack content-aware feature extraction and hinder machine-centric video analytics, making it difficult to achieve the required high accuracy with tolerable delay. Neural codecs (e.g., autoencoder) now hold impressive compression performance and have been widely advocated in video streaming. While autoencoder shows transformative potential, the application in video analytics is hampered by low accuracy in detecting small objects of highresolution videos and the serious challenges posed by multivideo streaming. To this end, we propose AdaStreamer with adaptive neural codecs to enable real machine-centric highaccuracy multi-video analytics. We also investigate how to achieve optimal accuracy under delay constraints via careful scheduling in Compression Ratios (CRs, the ratio of the compressed size to the original data size) and bandwidth allocation, and further propose a Markov-based Adaptive Compression and Bandwidth Allocation algorithm (MACBA). We have practically developed a prototype of AdaStreamer, based on which extensive experiments verify its accuracy improvement (up to 15%) compared to stateof-the-art coding and streaming solutions.

Video Analytics Pipeline (VAP) usually relies on traditional codecs to stream video content from clients to servers. However, such analytics-agnostic codecs preserve considerable pixels not relevant to achieving high analytics accuracy, incurring a large end-to-end delay. Despite the significant efforts of pioneers, they fall short as they resisted complete redundancy elimination. Achieving such a goal is extremely challenging, and naive design without coordination can result in the benefits of redundancy elimination being counterbalanced by intolerable delays introduced. We present CRUCIO, an end-to-end coordinated spatio-temporal redundancy elimination system for edge video analytics. CRUCIO leverages reshaped asymmetric autoencoders for end-to-end frame filtering (temporally) and coordinated intra-frame (spatially), inter-frame (temporally) compression. Furthermore, CRUCIO can decode the compressed key frames all in one go and support adaptive VAP batch size for delay optimization. Extensive evaluations reveal significant end-to-end delay reductions (at least 31% under an accuracy target of 0.9) in CRUCIO compared to the state-of-the-art VAP redundancy elimination methods (e.g., DDS, Reducto, STAC, etc).

Graph Neural Networks (GNNs) have proven effective in various scenarios. A key strategy involves pre-training existing graphs to extract knowledge that can be transferred to improve performance on downstream tasks, reducing the need for extensive labeled data. However, previous works commonly assumed that pre-training and fine-tuning occur in the same or closely related domains. A limitation is that for each individual graph without accessible pre-training data, a GNN must be trained from scratch, imposing high training overhead and hindering the ability of generalization. In this paper, we address the GNN multi-domain pre-training problem, which intends to pre-train a transferable GNN model from heterogeneous multi-source graph domains and then apply it in an unseen one with minor fine-tuning costs. To this end, we propose a scaLA ble Multi-source Pre-training (LAMP) method. For pre-training, LAMP presents a graph dual-distillation approach to distill massive knowledge from various graph domains to form synthetic homogeneous graphs. Simultaneously, high-level meta-knowledge from the synthetic graphs is extracted to train the GNN model, whose capability can be adjusted according to target graph contexts through a co-training modulation architecture. For fine-tuning, LAMP respectively aligns the target graph distribution, graph context, and graph task with the pretext so that the downstream task in the unseen domain can be reshaped to leverage the transferable knowledge efficiently. Extensive experiments on four different graph domain datasets show the superiority of LAMP.

Human Activity Recognition (HAR) as an emerging research field has attracted widespread academic attention due to its wide range of practical applications in areas such as healthcare, environmental monitoring, and sports training. Given the high cost of annotating sensor data, many unsupervised and semi-supervised methods have been applied to HAR to alleviate the problem of limited data. In this paper, we propose a novel video-enhanced cross-modal collaborative learning method, Vi2ACT, to address the issue of few-shot HAR. We introduce a new data augmentation approach that utilizes a text-to-video generation model to generate class-related videos. Subsequently, a large quantity of video semantic representations are obtained through fine-tuning the video encoder for cross-modal co-learning. Furthermore, to effectively align video semantic representations and time series representations, we enhance HAR at the representation-level using conditional Generative Adversarial Nets (cGAN). We design a novel Representation Conditional Discriminator that is trained to assess samples as originating from video representations rather than those generated by the time series encoder as accurately as possible. We conduct extensive experiments on four commonly used HAR datasets. The experimental results demonstrate that our method outperforms other baseline models in all few-shot scenarios.

Detection and assessment of micro vibrations are crucial tasks in both industrial settings and daily life. However, vibration sensors attached to the target vibrator may introduce potential resonance, and wireless detection methods suffer from severe multipath interference. Fortunately, moiré-based sensing methods have gained recognition in recent years due to their ability to perceive micro motion changes. In this paper, we propose MoiréVib, a micro-vibration detection solution based on moiré patterns for dynamic and high-frequency environments. We attach a printed marker with periodic gratings to the surface of vibration devices to generate moiré patterns, which can amplify micro vibrations due to their low-frequency magnification effect. However, moiré pattern's changes caused by micro vibrations are often overwhelmed by random pixel-level noises, and the limited frame rate of the camera fails to capture high-frequency moiré features. To deal with these problems, we propose a spectrum-based method to refine and enhance the dynamic and micro moiré features. Additionally, we propose a dual-frame-rate-based fusion mechanism to realize high-frequency reconstruction of moiré features. Extensive experimental results show that MoiréVib can realize a median amplitude detection error of 4.37 μm and achieve frequency detection up to 300Hz with a frame rate range of 10~30 fps.

In the realm of AR applications and particularly camera-to-screen interactions, camera tracking stands as a crucial technology. However, the ever-increasing demand for tracking accuracy makes it essential to explore a six-degrees of freedom (6-DoF) tracking technology with ultra-high precision to facilitate micro-motion sensing. In this paper, we propose a novel sensing method MoiréTracker to achieve camera’s 6-DoF pose tracking with ultra-high precision. MoiréTracker outputs camera’s continuous 3-DoF trajectory and 3-DoF posture changes according to the captured moiré patterns, which can be produced by the superposition of camera’s Color Filter Array (CFA) and the projection of screen raster on the CFA plane. Thanks to moiré pattern’s high sensitivity to 6-DoF motions, we characterize the relationship between moiré features and camera’s micro pose changes, so as to realize the continuous 6-DoF pose tracking for camera with ultra-high precision. Moreover, our proposal involves a thumbnail-based method aimed at expanding the working range of MoiréTracker, enabling the pervasive camera-to-screen interactions. We implement a prototype system and evaluate its performance in real-world environments. Extensive experiment results show that MoiréTracker achieves the average trajectory error of 1.20 cm and the posture error of 1.07°.

Over the last decade, the mobile crowdsourcing has become a paradigm to conduct the manual annotation and further analytics by recruited workers, with their rewards depending on the result quality. Existing dispatchers cannot precisely capture the resource-quality trade-off for video analytics, because the configurations supported by recruited workers are limited, and workers’ availability changes over time. To determine the most suitable configurations as well as workers for video analytics, we formulate a non-linear mixed program in long term, maximizing the crowdsourcing profit. 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 workers’ feedbacks. Such prediction is based on volatile multi-armed bandit to capture workers’ availability and stochastic changes on resource uses. Furthermore, we extend the proposed algorithms to the multi-worker selection scenario where the platform needs to determine a candidate worker set instead of a single worker for video analytics. 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 proposed algorithm improves the profit by 37% compared with other algorithms.

Video streaming is one of the most popular Internet applications that makes up a large amount of Internet traffic. A fundamental mechanism in video streaming is adaptive bitrate (ABR) selection which decides the proper compression level for each chunk of a video to optimize the users’ quality of experience (QoE). The existing ABR algorithms require significant tuning and do not generalize to diverse network conditions and personalized QoE objectives. In this article, we propose a novel framework for meta-learning based ABR design and discuss challenges of deploying learning based ABR mechanism in real-world video streaming systems. We utilize the proposed framework to design MetaABR, a novel adaptive bitrate selection algorithm based on meta-reinforcement learning to maximize users’ QoE. By jointly training multiple learning tasks with a shared meta-critic, it can provide transferrable meta-knowledge to supervise bitrate selection across tasks, and can be applied to efficiently learn a new task in unseen environment with only a few trials. We implement MetaABR on an emulation platform which connects to the Linux network protocol stack through virtual network interfaces. Extensive experiments based on real-world traces and wireless testbed show that MetaABR achieves the best comprehensive QoE compared with the state-of-the-art ABR algorithms in a variety of network environments.

Deep convolutional neural network (NN)-based object detectors are not appropriate for straightforward inference on high-resolution videos at edge devices, as maintaining high accuracy often brings about prohibitively long latency. Although existing solutions have attempted to reduce on-device inference latency by selecting a cheaper configuration (e.g., choosing a more lightweight NN or scaling a frame to a smaller size before inference) or eliminating a background containing no object, they often ignore various high-resolution features and fail to optimize for those videos. We thus present AdaPyramid, a framework to reduce as much on-device inference latency as possible, especially for high-resolution videos, while achieving the accuracy demand approximately. We observe that the cheapest configuration to achieve the accuracy demand varies significantly across both different frames and different regions in a frame. The underlying reason is that object features (e.g., the location, size and category of objects) are more uneven in high-resolution videos, both temporally and spatially. Moreover, we observe that the object size presents a prominent hierarchical distribution in high-resolution frames. AdaPyramid thus partitions each frame hierarchically just like a pyramid and chooses a content-aware configuration for each region, which is adapted online based on the feedback. We evaluate the performance of AdaPyramid on a public dataset and our collected real-world videos. The obtained results show that under comparable accuracy to the state-of-the-art solutions, AdaPyramid can decrease inference latency by 40% on average, with up to 2.5× speed-up.

With the rising of demands for novel Human-Computer Interaction (HCI) approaches in the 3D space, a number of intelligent approaches have been proposed to achieve the HCI by tracking the translation and rotation of the target devices. In this paper, we propose to realize a light-weight, battery-free, 3D motion tracking solution by leveraging a spinning linearly polarized antenna to track a passive RFID tag array. Instead of using the fixed antennas, which can only receive stable signal in some specific environments due to the unpredictable multipath effect, we propose to mitigate the multipath effect and the ambient interference by continuously spinning a linearly polarized antenna, and then extract the most distinctive features based on the optimal reading conditions of the spinning antenna. In particular, because the phase variation around the matching direction is more stable while the RSSI variation around the mismatching direction is more distinctive, we leverage such matching/mismatching property of the linearly polarized antenna to extract the most distinctive features for motion tracking. To depict the property, we build a theoretical model to explain the RSSI and the phase variation of the RFID tag along with the spinning of the antenna, and further extend the model from a single RFID tag to an RFID tag array. Based on the model, we can extract the distinctive RSSI features for the rotation tracking and the stable phase features for the translation tracking. Moreover, to tackle the low rate of feature extraction due to the spinning of antenna, we further propose to enhance the unstable phase features based on the overall trend of other tags with interpolation, such that the sampling rate can be efficiently improved. Finally, we propose a LSTM (Long Short Term Memory)-based network to track the 3D motion based on the signal features extracted based on the polarization model. The experimental results show that our system can achieve an average error of 10.45 cm in the translation tracking, and an average error of$6.02^\circ$in the rotation tracking in the 3D space.

Nowadays, to realize the intelligent manufacturing in Industrial Internet of Things (IIoT) scenarios, novel approaches in computer vision are in great demand to tackle the new challenges in IIoT environment. These approaches, which we callIndustrial Vision, are expected to offer customized solutions for intelligent manufacturing in an accurate, time efficient and robust manner. In this paper, we propose a novel approach to industrial vision, calledEdge-Eye, to rectify the edge deviation automatically for Irradiated Cross-linked Polyethylene Foam (IXPE) production with millimeter-level accuracy. IXPE has been one of the most commonly used materials in industry. During the production process of IXPE sheets, their edges need keep aligned strictly, otherwise, they could quickly get out of the border of the rolling plate and cause the huge economic loss. We deploy a commercial camera with mobile edge node in front of the IXPE sheet to continuously detect and rectify the edge deviation. Particularly, to handle the complex production environment when extracting the edge of IXPE sheet, we deploy a pair of reference bars with high-contrast colors to efficiently differentiate the sheet edge from the background. Then, we propose aBi-direction Edge Tracking methodto perform the edge detection from both vertical and horizontal aspects. To realize the rectification using mobile edge nodes with limited computing resources, we reduce the cost of computation by extracting theMinimized Region of Interest, i.e., the edge area overlapped with the higher contrast reference bar on both sides. We further design a negative feedback control system with multi-stage feedback regulation mechanism, keeping the edge deviation withinmillimeter-level. We implementedEdge-Eyeon the ARM64 platform and performed evaluation in the practical IXPE production process. The experimental results show thatEdge-Eyeachieves the average accuracy of 5 mm for the edge deviation rectification, with the average latency of 200 ms for edge deviation detection. During the process of 20-month real deployment for 36 production lines, 66 manpower per day (90% of the overall manpower) has been saved, and the utilization rate of IXPE material increases from 87% to 94%.

The detection of objects via neural networks plays a key role in various video analytics, but consumes huge resources. Due to the limited computing capability at edges, such real-time detections should be precisely used for the objects that need the most attention. Unfortunately, as the target objects keep moving, existing systems fail to consider both the distribution of objects and object movements over regions, and existing tracking mechanisms are easily affected by background content. Therefore, we propose spatial and temporal detection with attention for analytics, to increase the quality of detections for those targets. However, the attention shift over regions, the uncertainty of detections, and the constrained edge resources essentially hamper us from efficient analytics. We propose an adaptive partition planner to divide the frame into regions to achieve spatial attention. Afterwards, we design a detection planner to orchestrate the detection model temporally for each region by an online mechanism, via a queue-based adaptation. The spatial and temporal attention are integrated to maximize the accumulative detection accuracy. Via rigorous proof, both dynamic regret regarding detection accuracy and the real-time requirement for the video analytics are ensured. The testbed experiments confirm the superiority of our approach over multiple state-of-the-art algorithms.

Speech is a natural communication way between people and a good way for human-computer interaction. However, speech with audible voices often faces the following problems, e.g., being affected by surrounding noises, breaking the quiet environment, leaking privacy, etc. Therefore, silent speech was proposed, especially lip reading, which aims to recognize speech content based on lip movements. In this paper, we utilize inaudible acoustic signals generated from mobile device to sense and recognize lip movements for lip reading. Considering the lack of public dataset in acoustic-based lip reading, we propose and release a large-scale lip-reading dataset${\sf LIPCMD}$with 30000 acoustic-based recordings. To advance the further research in lip reading, we provide benchmark evaluation on${\sf LIPCMD}$, while using traditional machine learning solutions and recent deep learning approaches. To recognize weak acoustic signals as words for lip reading, we propose a self distillation based approachLipReader, which distills the probability distribution and attention map in convolutional neural network itself for better classification. Finally, we implementLipReaderon smartphone and evaluate it on${\sf LIPCMD}$dataset as well as under complex scenarios. Experimental results show thatLipReadercan achieve a good recognition accuracy for lip reading, i.e., 91.58%, while outperforming baseline solutions and existing work.

The usage of live streaming services has led to a substantial increase in live video traffic. However, the perceived quality of experience of users is frequently limited by variations in the upstream bandwidth of streamers. To address this issue, several adaptive bitrate (ABR) algorithms have been developed to mitigate bandwidth variations. Nevertheless, the ability of users to enjoy high-quality live streams remains limited. While neural-enhanced approaches, such as super-resolution, offer significant quality improvements, frame-oriented super-resolution leads to excessive inference delay that violates the real-time feature of live streaming. In response, we propose ViChaser, which examines block-oriented super-resolution for live streaming. ViChaser performs neural super-resolution on potential blocks of interest in the media server, corresponding to the user’s viewpoint, and uses online learning to adapt to the dynamic content of the video. Additionally, ViChaser utilizes the Lyapunov framework to efficiently allocate uplink bandwidth for original low-quality live video and high-quality labels. The experimental results demonstrate that ViChaser achieves 1.2–1.5 dB higher video quality in Peak-Signal-to-Noise-Ratio than WebRTC and increases processing speed by 11–16 fps relative to LiveNAS.

In industrial production, the orientation of facility components can indicate whether the facility is on a regular operating track. For example, when a component gets loose, the orientation variation of the component would exceed the normal range. A common approach for orientation measurement is to attach an inertial measurement unit (IMU) to the target device. However, the IMU requires additional power maintenance. This article presents LightGyro, a cheap and efficient batteryless scheme to measure the orientation, in which we attach a reflective film to the target device and use a camera to capture the light spot on the reflective film. The basic idea of LightGyro is to extract the light spots in the captured frame and use their pixel coordinates to infer the orientation. It is difficult to recognize a single light spot, because the spot lacks distinctive features. To solve the problem, we switch light sources on and off to regulate the appearance of light spots and utilize frame subtraction to extract light spots. The depth of field of light spot is lost in the process of camera projection, which is necessary for the orientation measurement. To address the issue, we propose a light array-based reflection model to extract the depth of field from the relative positions of multiple light spots. To the best of our knowledge, this is the first work to utilize reflection to measure orientation. Experiment results show that the orientation error of LightGyro decreases with the increasing length of the reflection route and the orientation error can achieve less than 1 ˆ .

Despite being widely deployed in safety-critical applications such as autonomous driving and health care, deep neural networks (DNNs) still suffer from non-negligible reliability issues. Numerous works had reported that DNNs were vulnerable to either natural environmental noises or man-made adversarial noises. How to repair DNNs in deployment with noisy samples is a crucial topic for the robustness of neural networks. While many network repairing methods based on data argumentation and weight adjustment have been proposed, they require retraining and redeploying the whole model, which causes high overhead and is infeasible for varying faulty cases on different deployment environments. In this paper, we propose a novel network repairing framework called PatchNAS from the architecture perspective, where we freeze the pretrained DNNs and introduce a small patch network to deal with failure samples at runtime. PatchNAS introduces a novel network instrumentation method to determine the faulty stage of the network structure given the collected failure samples. A small patch network structure is searched unsupervisedly using neural architecture search (NAS) technique with data samples from deployment environment. The patch network repairs the DNNs by correcting the output feature maps of the faulty stage, which helps to maintain network performance on normal samples and enhance robustness in noisy environments. Extensive experiments based on several DNNs across 15 types of natural noises show that the proposed PatchNAS outperforms the state-of-the-arts with significant performance improvement as well as much lower deployment overhead.

Graph meta learning aims to learn historical knowledge from training graph neural networks (GNNs) models and adapt it to downstream learning tasks in a target graph, which has drawn increasing attention due to its ability of knowledge transfer and fast adaptation. While existing graph meta learning approaches assume the learning tasks are from the same graph domain but lack the solution for multi-domain adaptation. In this paper, we address the multi-domain generalized graph meta learning problem, which is challenging due to non-Euclidean data, inequivalent feature spaces, and heterogeneous distributions. To this end, we propose a novel solution called MD-Gram for multi-domain graph generalization. It introduces an empirical graph generalization method that uses empirical vectors to form a unified expression of non-Euclidean graph data. Then it proposes a multi-domain graphs transformation approach to transform the learning tasks from multiple source-domain graphs with inequivalent feature spaces into a common domain, where graph meta learning is conducted to learn generalized knowledge. It further adopts a domain-specific GNN enhancement method to learn a customized GNN model to achieve fast adaptation in the unseen target domain. Extensive experiments based on four real-world graph domain datasets show that the proposed method significantly outperforms the state-of-the-art in multi-domain graph meta learning tasks.

Federated learning has emerged as a promising distributed machine learning paradigm to preserve data privacy. One of the fundamental challenges of federated learning is that data samples across clients are usually not independent and identically distributed (non-IID), leading to slow convergence and severe performance drop of the aggregated global model. To facilitate model aggregation on non-IID data, it is desirable to infer the unknown global distributions without violating privacy protection policy. In this paper, we propose a novel data-agnostic distribution fusion based model aggregation method called FedFusion to optimize federated learning with non-IID local datasets, based on which the heterogeneous clients' data distributions can be represented by a global distribution of several virtual fusion components with different parameters and weights. We develop a Variational AutoEncoder (VAE) method to learn the optimal parameters of the distribution fusion components based on limited statistical information extracted from the local models, and apply the derived distribution fusion model to optimize federated model aggregation with non-IID data. Extensive experiments based on various federated learning scenarios with real-world datasets show that FedFusion achieves significant performance improvement compared to the state-of-the-art.

The widespread use of 5G and artificial intelligence applications has led to strong momentum in Mobile Edge Computing (MEC). With MEC, we can offload compute-intensive tasks to edge servers that are closer to the user, thereby reducing the long latency incurred by data transmission via WAN. Although many works have investigated task offloading decisions under service caching, the state of services is an equal, if not more important, research area of MEC, yet receive much less attention. In general, the arrival of tasks exhibit a distribution over time. Besides the necessary energy consumption in processing tasks offloaded to edge servers, a large amount of energy is required for maintaining services cached on servers. When more and more services become idle, they will incur a non-negligible additional energy. In this paper, we focus on an interesting but currently less studied problem in MEC, namely online service caching and state management in MEC. We propose DCSO, a bounded online algorithm that considers dynamic service caching and state management of services to minimize long-term cost in MEC systems. Meanwhile, our algorithm achieves a 2 competitive ratio in state management. Trace-driven simulations show that our algorithm reduces the overall cost efficiently while keeping low computation latency.

There are two problems that widely exist in current end-to-end sign language processing architecture. One is the CTC spike phenomenon which weakens the visual representational ability in Continuous Sign Language Recognition (CSLR). The other one is the exposure bias problem which leads to the accumulation of translation errors during inference in Sign Language Translation (SLT). In this paper, we tackle these issues by introducing contrast learning, aiming to enhance both visual-level feature representation and semantic-level error tolerance. Specifically, to alleviate CTC spike phenomenon and enhance visual-level representation, we design a visual contrastive loss by minimizing visual feature distance between different augmented samples of frames in one sign video, so that the model can further explore features by utilizing numerous unlabeled frames in an unsupervised way. To alleviate exposure bias problem and improve semantic-level error tolerance, we design a semantic contrastive loss by re-inputting the predicted sentence into semantic module and comparing features of ground-truth sequence and predicted sequence, for exposing model to its own mistakes. Besides, we propose two new metrics, i.e., Blank Rate and Consecutive Wrong Word Rate to directly reflect our improvement on the two problems. Extensive experimental results on current sign language datasets demonstrate the effectiveness of our approach, which achieves state-of-the-art performance.

Deploying deep convolutional neural network (CNN) to perform video analytics at edge poses a substantial system challenge, as running CNN inference incurs a prohibitive cost in computational resources. Model partitioning, as a promising approach, splits CNNs and distributes them to multiple edge devices in closer proximity to each other for serial inferences, however, it causes considerable cross-edge delay for transmitting intermediate feature maps. To overcome this challenge, we present ResMap, a new edge video analytics framework that significantly improves the cross-edge transmission and flexibly partitions the CNNs. Briefly, by exploiting the sparsity of the intermediate raw or residual feature map, ResMap effectively removes the redundant transmission, thereby decreasing the cross-edge transmission delay. In addition, ResMap incorporates an Online Data-Aware Scheduler to regularly update the CNN partitioning scheme so as to adapt to the time-varying edge runtime and video content. We have implemented ResMap fully based on COTS hardware, and the experimental results show that ResMap reduces the intermediate feature map volume by 14.93-46.12% and improves the average processing time by 17.43-30.6% compared to other alternative designs.

With the proliferation of voice assistants, microphone-based speech recognition technology usually cannot achieve good performance in the situation of multiple sound sources and ambient noises. In this paper, we propose a novel mmWave-based solution to perform speech recognition to tackle the issues of multiple sound sources and ambient noises, by precisely extracting the multi-modal features from lip motion and vocal-cords vibration from the single channel of mmWave. We propose a difference-based method for feature extraction of lip motion to suppress the dynamic interference from body motion and head motion. We propose a speech detection method based on cross-validation of lip motion and vocal-cords vibration so as to avoid wasting computing resources on nonspeaking activities. We propose a multi-modal fusion framework for speech recognition by fusing the signal features from lip motion and vocal-cords vibration with the attention mechanism. We implemented a prototype system and evaluated the performance in real test-beds. Experiment results show that the average speech recognition accuracy is 92.8% in realistic environments.

Interactive mobile augmented reality (MAR) applications such as Connected Lens are becoming popular, which often rely on deep neural network (NN)-based video analytics techniques to understand the real world. However, performing computation-intensive NN inference on resource-constrained mobile devices is impractical. It is thus proposed to offload the workloads to edge servers with the help of mobile edge computing (MEC). Existing works often focus on system-wide offloading solutions, optimizing the personalized user experience for interactive applications in dynamic environments is yet rarely studied, where multiple challenges remain to be solved. First, the user has to decide the configuration for video analytics, where the inherent accuracy-cost trade-off exists. Second, it is intractable to decide the target server for offloading, since each server supports limited configurations, and a user needs to balance the experience of analytics service and the quality of interaction with others at the same time. Third, the fluctuating network information is often undisclosed to the users, and the candidate servers also vary over time. Therefore, in this paper, we propose an online user-managed server selection and configuration adaptation scheme (OSCA). Via Lyapunov optimization, we aim to maximize the long-term service experience, under the interactive quality constraint with other users. Besides, volatile multi-armed bandit (MAB) is utilized to handle the network fluctuation and the variance of the candidate servers. We conduct rigorous theoretical analysis, and the deviations of both the service experience and the interactive quality are bounded. Through extensive trace-driven experiments, we demonstrate the superior performance of OSCA.

To provide instant communication for hearing-impaired people, it is essential to achieve real-time sign language processing anytime anywhere. Therefore, in this paper, we propose a Region-aware Temporal Graph based neural Network (RTG-Net), aiming to achieve real-time Sign Language Recognition (SLR) and Translation (SLT) on edge devices. To reduce the computation overhead, we first construct a shallow graph convolution network to reduce model size by decreasing model depth. Besides, we apply structural re-parameterization to fuse the convolutional layer, batch normalization layer and all branches to simplify model complexity by reducing model width. To achieve the high performance in sign language processing as well, we extract key regions based on keypoints in skeleton from each frame, and design a region-aware temporal graph to combine key regions and full frame for feature representation. In RTG-Net, we design a multi-stage training strategy to optimize keypoint selection, SLR and SLT step by step. Experimental results demonstrate that RTG-Net achieves comparable performance with existing methods in SLR or SLT, while greatly reducing the computation overhead and achieving real-time sign language processing on edge devices. Our code is available at https://github.com/SignLanguageCode/realtimeSLRT.

With the popularity of smartwatches, users can access private information stored in the device by simply touching the watch screen. However, smartwatches also expose users to the risk of information leakage because they lack proper authentication schemes. This paper proposes PalmEcho, a multimodal authentication scheme for smartwatches. The basic idea of PalmEcho is to capture the vibration and the sound generated from user’s beating gestures, and then fuse multimodal signals to extract unique features for user authentication. However, signals of beating gestures are short in the time domain, which makes it hard to extract effective features. To address this challenge, our work reveals that the spectral energy distribution of the generated sound is unique to each user and provides rich information for authentication. Moreover, conventional classification networks require large amounts of user data for training, which is not convenient in the user authentication scenario. To address this challenge, we design a prototypical network called BeatNet, which allows users to register with a few samples. Experimental results show that PalmEcho can reach an average F1-score of 94%.

Influence maximization is the problem of finding a set of seed nodes in the network that maximizes the influence spread, which has become an important topic in social network analysis. Conventional influence maximization algorithms cause “unfair" influence spread among different groups in the population, which could lead to severe bias in public opinion dissemination and viral marketing. To address this issue, we formulate the fair influence maximization problem concerning the trade-off between influence maximization and group fairness. For the purpose of solving the fair influence maximization problem in large-scale social networks efficiently, we propose a novel attribute-based reverse influence sampling (ABRIS) framework. This framework intends to estimate influence in specific groups with guarantee through an attribute-based hypergraph so that we can select seed nodes strategically. Therefore, under the ABRIS framework, we design two different node selection algorithms, ABRIS-G and ABRIS-T. ABRIS-G selects nodes in a greedy scheduling way. ABRIS-T adopts a two-phase node selection method. These algorithms run efficiently and achieve a good trade-off between influence maximization and group fairness. Extensive experiments on six real-world social networks show that our algorithms significantly outperform the state-of-the-art approaches. This article appears in the AI & Society track.

The software-defined network (SDN) enabled mobile edge network greatly facilitates network resource management and promotes many emerging applications. However, user mobility may cause the SDN controller to set flow rules frequently, introduce additional flow setup latency, cause delay jitter, and undermine latency-sensitive services. Proactive flow setup is an effective way to eliminate flow setup latency, but existing work fails to maximize the flow setup hit ratio, a metric for evaluating the quality of proactive flow setup decisions, which is critical for latency-sensitive services. In this paper, we study how to proactively set flow rules to maximize the flow setup hit ratio under limited available network resources to eliminate the flow setup latency as much as possible. Then, we formalize the proactive flow setup problem as two integer linear programming problems under two typical routing strategies, default routing and dynamic routing. Both problems are proved to be NP-hard. To tackle these two problems, we propose a linear programming-based polynomial-time approximation algorithm for the default routing case and a greedy-based heuristic algorithm for the dynamic routing case. Extensive trace-driven experimental and simulation results verify that our algorithms can improve the flow setup hit ratio by up to 30.99% compared to existing solutions.

Anomaly detection on multivariate time series (MTS) is an important research topic in data mining, which has a wide range of applications in information technology, financial management, manufacturing system, and so on. However, the state-of-the-art unsupervised deep learning models for MTS anomaly detection are vulnerable to noise and have poor performance on the training data containing anomalies. In this article, we propose a novel Self-Training based Anomaly Detection with Generative Adversarial Network (GAN) model called STAD-GAN to address the practical challenge. The STAD-GAN model consists of a generator-discriminator structure for adversarial learning and a neural network classifier for anomaly classification. The generator is learned to capture the normal data distribution, and the discriminator is learned to amplify the reconstruction error of abnormal data for better recognition. The proposed model is optimized with a self-training teacher-student framework, where a teacher model generates reliable high-quality pseudo-labels to train a student model iteratively with a refined dataset so that the performance of the anomaly classifier can be gradually improved. Extensive experiments based on six open MTS datasets show that STAD-GAN is robust to noise and achieves significant performance improvement compared to the state-of-the-art.

Multivariate time series (MTS) clustering is an important technique for discovering co-evolving patterns and interpreting group characteristics in many areas including economics, bioinformatics, data science, etc. Although time series clustering has been widely studied in the past decades, no enough attention has been paid to capture time-varying correlation patterns in MTS. In this article, we propose a novel clustering approach for MTS data based on time-varying features. We introduce a time-varying Gaussian Markov Random Fields (T-GMRF) model to describe the correlation structure between MTS variables, and formulate the time-varying feature extraction problem as a convex optimization problem, which can be solved by a T-GMRF learning algorithm based on random block coordinate descent. We further apply a principal component analysis (PCA) based method on GMRF sequences to obtain low-dimensional feature vectors, and adopt a multi-density based clustering approach to form the cluster assignments. We conduct extensive experiments to compare the proposed T-GMRF method with 11 clustering algorithms based on 33 open MTS datasets, which show that T-GMRF significantly outperforms the state-of-the-arts with performance improvement up to 16%-64.5% on a variety of clustering performance metrics. The source codes of T-GMRF are publicly available at GitHub.

We consider the multiuser detection (MUD) problem, i.e., how to separate and decode colliding data streams, in the uplink of massive Machine Type Communications (mMTC) at millimeter wave (mmWave). Operating on factor-graphs by passing messages, the sum-product algorithm and its variants are widely applied in many other scenarios. However, in this paper, we find that their performance in mMTC at mmWave could be dramatically degraded due to the ill-conditioned MUD channel gain matrix and the existence of enormous short cycles in their corresponding factor-graphs, which are caused by the limited scattering of mmWave and the sharing of a same codebook for error correction among densely located user equipments. Assuming LDPC codes are used for error correction, we further propose a novel sum-product based approach to dealing with the MUD problem in mMTC at mmWave. It first leverages the propagation characteristics of mmWave to optimize the factor-graph for MUD by removing short cycles based on node-split and node-contraction, and then takes a dynamic-programming based method to approximate the messages passing on the resulted factor-graph, which can achieve a higher decoding accuracy. Extensive simulation results show that our approach outperforms the state-of-the-art sum-product based approaches significantly.

Nowadays, authentication systems are usually required to provide continuous, contactless, and non-intrusive services. In this paper, we proposeRF-Badge, a vital sign-based authentication scheme on human subjects to meet the above requirements by using RFID technology. We consider two biometric features with individual diversity to characterize the vital sign of users, including themovement effectfrom respiration and thereflection effectfrom organs, especially the heart. To derive the movement effect from respiration, we build a phase-based geometric model to restore the fine-grained badge moving trace as the feature. To derive the reflection effect from human internal organs, we extract the reflection signal from the original signal and generate the spectrum as the feature. Besides, to deal with the feature deviation in different physical conditions of users, we propose a multi-condition network (MCNet) to further guarantee the generalization of RF-Badge. We implement a prototype system and evaluate the performance in real environments. The experiment results show that our system achieves the average false positive rate (FPR) of 3.9 percent and false negative rate (FNR) of 3.3 percent for continuous authentication within four signal cycles.

Conducting federated learning across distributed sites with In-Band Network Telemetry (INT) based data collection faces critical challenges, including control decisions of different frequencies, convergence of the models being trained, and resource provisioning coupled over time. To study this problem, we formulate a non-linear mixed-integer program to optimize the long-term INT overhead, resource cost, and federated learning cost. We then design polynomial-time online algorithms to solve this problem with only observable inputs on the fly, featuring laziness-aware resource adaption, online-learning-based INT flow selection and model aggregation control, as well as expectation-preserving randomized dependent rounding. We rigorously prove the parameterized-constant competitive ratio of our approach against the offline optimum, and the time-averaged constraint violation that vanishes in the long run. With extensive trace-driven evaluations, we confirm the superiority of our approach over other alternative approaches for reducing total cost and the efficacy of our trained models for solving real machine learning problems, reducing the real-time cost by 34% on average.

Deploying microservice instances on the edge device close to end users can provide on-site processing thus reducing request response time. Each microservice has multiple instances that can process requests in parallel. To achieve high processing efficiency, the number of these instances is scaled according to the workload, which is also known as autoscaling. Previous studies of microservice autoscaling in the edge computing environment lack in-depth consideration of time-varying workload, they assume that the workload of each microservice always depends on that of its upstream. However, through an analysis of Alibaba's microservice trace with hundreds of millions of records, we find that the assumption is impractical thus hurting autoscaling effectiveness. To solve this problem, we propose ProScale, a prediction-driven proactive autoscaling framework for microservices at the edge. ProScale proactively forecasts the workload for each individual microservice per timeslot. Then it utilizes an efficient online algorithm to leverage the predicting results to determine the instance number for each microservice jointly with making placement decisions. For each microservice instance deployed on the edge device, ProScale handles burst requests using a designed offloading strategy. In addition, ProScale can also balance the load for multiple instances of each microservice. Extensive trace-driven experiments show that ProScale has great scalability. It can reduce average response time by 96.7% and resource usage by 96.5% compared with existing strategies and designed baselines.

Loosely coupled and highly cohesived microservices running in containers are becoming the new paradigm for application development. Compared with monolithic applications, applications built on microservices architecture can be deployed and scaled independently, which promises to simplify software development and operation. However, the dramatic increase in the scale of microservices and east-west network traffic in the data center have made the cluster management more complex. Not only does the scale of microservices cause a great deal of pressure on cluster management, but also cascading QoS violations present a substantial risk for SLOs (Service Level Objectives). In this paper, we propose a Microservice-Oriented Topology-Aware Scheduling Framework (MOTAS), which effectively utilizes the topologies of microservices and clusters to optimize the network overhead of microservice applications through a heuristic graph mapping algorithm. The proposed framework can also guarantee the cluster resource utilization. To deal with the dynamic environment of microservice, we propose a mechanism based on distributed trace analysis to detect and handle QoS violations in microservice applications. Through real-world experiments, the framework has been proved to be effective in ensuring cluster resource utilization, reducing application end-to-end latency, improving throughput, and handling QoS violations.

In past years, artificial intelligence related services and applications have boomed, which require high computation, high bandwidth and low latency. Edge computing is regarded as an appropriate solution for them, especially video analytics. In this paper, we study the multi-server multi-user heterogeneous video analytics offloading problem, where users select appropriate edge servers and then offload their raw video data to the servers for essential analytics. To deal with the cooperation and conflicts among users and get a stable situation where each user has no incentive to change the offloading decision unilaterally, we formulate the video analytics offloading problem as a multiplayer game. Based on the goal of minimizing the overall delay, we design the potential optimal server selection strategy and then propose a game theory-based algorithm, through which the Nash equilibrium can be reached. Furthermore, we analyze its near-optimal performance via rigorous proof. Finally, extensive trace-driven experiments show that our method improves the overall delay by 48% on average, compared with other algorithms.

In the context of Industrial Internet of Things (IIoT), RFID technologies have been widely applied to locate or track tagged objects for achieving item-level intelligence. However, prior localization work encounters two main issues. First, the phase measurement usually contains physical deviation. Existing localization work generally takes the physical center of an RFID antenna as its phase center, which is a key factor in improving localization accuracy but actually different from the physical center in practice. Second, the non-linear localization model is likely to be too complex to run on edge nodes with limited computing resources. In this paper, we present a LInear localizatiON solution, called LION, to perform the phase calibration for antennas with no need for the complex computation nor strong limitations. Specifically, we provide a novel lightweight model to pinpoint the actual antenna position quickly and accurately. Compared to previous localization methods, we reduce the intersection of circles or hyperbolas into radical lines, which greatly reduces the computation cost while guaranteeing the high accuracy. Further, to adapt to the complex environment with various ambient noise and multi-path effect, we leverage the weighted least square method to determine the optimal position. Moreover, we propose an adaptive parameter selection scheme to automatically choose optimal parameters for localization. In this way, LION is able to perform the accurate localization robustly. We implement LION using commercial RFID devices, and evaluate its performance extensively. Experimental results show the necessity of phase calibration as well as the high time efficiency of LION, e.g., the average accuracy improves by 6× and 2.1× for 2D and 3D localization, and the average time consuming is 0.02s and 1.8s for 2D and 3D cases.

The congestion control strategy plays an essential role in the high-speed datacenter network. It aims to deliver low latency, high throughput network service. RTT-based congestion control leverages advanced NIC hardware to identify accumulated queuing delay of the end-to-end path. Sender adjusts the sending rate or congestion window if the delay exceeds a predetermined value, i.e., target delay. Therefore, setting the target delay is the key for RTT-based congestion control strategies. We provide a comprehensive study of the impact of target delay on recent RTT-based congestion control strategies, and demonstrate that a fixed inappropriate target value can lead to low bandwidth utilization or high latency. We then propose a practical queuing target updating approach to solve this problem. The proposed method maintains a shared near-optimal queuing target at the receiving host. We leverage the widely supported ECN flag to estimate the empty state of switch queue instead of indicating congestion, which requires no complicated threshold configuration. We have integrated the dynamic queuing target updating approach into the state-of-the-art RTT-based congestion strategy, SWIFT, and named the design RET. Test-bed experiments and simulations in the large-scale network with synthesized traffic of real workloads show that RET can achieve up to 1.5x and 3.6x lower tail latency than SWIFT and DCQCN, respectively. This paper provides a deep understanding on tuning target delay for RTT-based congestion control algorithms in datacenter networks.

As a key component of most machines, the status of the rotation shaft is a crucial issue in the factories, which affects both the industrial safety and the product quality. Tracking the rotation angle can efficiently monitor the status of the rotation shaft, but traditional solutions either rely on the specialized sensors, suffering from intrusive transformation, or use the computer vision-based solutions, suffering from poor light conditions. In this paper, we present a non-contacting low-cost angle tracking solution, RF-Protractor, to track the rotation shaft based on the surrounding RFID tags. Particularly, instead of directly attaching the tags to the shaft, which may lead to serious miss reading problems due to metal interference, we deploy the tags beside the shaft and leverage the polarization effect of the reflection signal from the shaft for angle tracking. To improve the polarization effect, we exploit the linear polarization feature by using the linear shaft turntable or placing a light aluminum foil on the shaft turntable, which requires no transformation of the shaft. We firstly build a polarization model to quantify the relationship between the rotation angle and the reflection signal. To extract the accurate reflection signal, we then propose to combine the signals of multiple tags to cancel the reflection effect and then estimate the environment-related parameter to calibrate the model. Finally, we propose to leverage both the power trend and the IQ signal to estimate the rotation direction and the rotation angle. We have implemented a real system and the extensive experiments in the real environment confirm the effectiveness of RF-Protractor, which achieves an average error of about 3.1° in angle tracking.

Voice assistant has been widely used for human-computer interaction and automatic meeting minutes. However, for multiple sound sources, the performance of speech recognition in voice assistant decreases dramatically. Therefore, it is crucial to separate multiple voices efficiently for an effective voice assistant application in multi-user scenarios. In this paper, we present a novel voice separation system using a 2D microphone array in multiple sound source scenarios. Specifically, we propose a spatial filtering-based method to iteratively estimate the Angle of Arrival (AoA) of each sound source and separate the voice signals with adaptive beamforming. We use BeamForming-based cross-Correlation (BF-Correlation) to accurately assess the performance of beamforming and automatically optimize the voice separation in the iterative framework. Different from cross-correlation, BF-Correlation further performs cross-correlation among the after-beamforming voice signals processed with each linear microphone array. In this way, the mutual interference from voice signals out of the specified direction can be effectively suppressed or mitigated via the spatial filtering technique. We implement a prototype system and evaluate its performance in real environments. Experimental results show that the average AoA error is 1.4 degree and the average ratio of automatic speech recognition accuracy is 90.2% in the presence of three sound sources.

Federated learning (FL) has been proposed as a novel paradigm to enable distributed learning on the edge with privacy protection. However, existing federated learning approaches mainly focus on training deep classification and clustering models, and no enough attention has been paid to solve the federated reinforcement learning task on the edge, a challenging task where multiple learning agents observe local state and take local actions to train a global learning model without revealing their local dataset. In this paper, we propose a generalised federated reinforcement learning framework called FedMC that integrates reinforcement learning models trained by multiple edge devices into a general model based on a meta-learning approach. In the proposed framework, each participant adopts a meta-value network (MVN) and task-actor encoder network (TAEN) locally to perform meta-learning training based on local task samples, and periodically uploads the weights of local MVN and TAEN to the server, which aggregate them to a global model with rapid adaptability and cross-task applicability. Extensive experiments based on a number of reinforcement learning tasks show that FedMC outperforms various federated learning baseline algorithms, and it is competitive with the methods that centrally train reinforcement learning task with global dataset.

Irradiated Cross-linked Polyethylene Foam (IXPE) has been one of the most commonly used materials in industry. During the production process of IXPE sheets, their edges need keep aligned strictly, otherwise, they could quickly get out of the border of the rolling plate and cause the huge economic loss. In this paper, we propose a camera-enabled approach, called Edge-Eye, to rectify the edge deviation automatically for IXPE production with millimeter-level accuracy. We deploy a commercial camera with mobile edge node in front of the IXPE sheet to continuously detect and rectify the edge deviation. Particularly, to handle the complex production en-vironment when extracting the edge of IXPE sheet, we deploy a pair of reference bars with high-contrast colors to efficiently differ-entiate the sheet edge from the background. Then, we propose a Bi-direction Edge Tracking method to perform the edge detection from both vertical and horizontal aspects. To realize the rectification using mobile edge nodes with limited computing resources, we reduce the cost of computation by extracting the Minimized Region of Interest, i.e., the edge area overlapped with the higher contrast reference bar on both sides. We further design a negative feedback control system with multi-stage feedback regulation mechanism, keeping the edge deviation within millimeter-level. We implemented Edge-Eye on the ARM64 platform and performed evaluation in the practical IXPE production process. The experimental results show that Edge-Eye achieves the average accuracy of 5mm for the edge deviation rectification, with the average latency of 200ms for edge deviation detection. During the process of 20-month real deployment for 36 production lines, 66 manpower per day (90% of the overall manpower) has been saved, and the utilization rate of IXPE material increases from 87% to 94%.

Edge computing is a new computing paradigm rising gradually in recent years. Applications, such as object detection, virtual reality and intelligent cameras, often leverage Deep Neural Networks (DNN) inference technology. The traditional paradigm of DNN inference based on cloud suffers from high delay because of the limited bandwidth. From the perspective of service providers, caching DNN models on the edge brings several benefits, such as efficiency, privacy, security, etc.. The problem we concerned in this paper is how to decide the cached models and how to allocate processors of edge servers to reduce the overall system cost. To solve it, we model and study the DNN Model Caching and Processor Allocation (DMCPA) problem, which considers user-perceived delay and energy consumption with limited edge resources. We model it as an integer nonlinear programming (INLP) problem, and prove its NP-Completeness. Since it is considered as a long-term average optimization problem, we leverage the Lyapunov framework to develop a novel online algorithm DMCPA-GS-Online with Gibbs Sampling. We give the theoretical analysis to prove that our algorithm is near-optimal. In experiments, we study the performance of our algorithm and compare it with other baselines. The simulation results with the trace dataset from real world demonstrate the effectiveness and adaptiveness of our algorithm.

Camera tracking has become a key technology for various application scenarios, especially for AR-based camera-to-screen interaction. Demand for subtle motion detection in camera tracking makes it essential to explore the six degrees of freedom (6-DoF) pose detection with ultra-high precision. In this paper, we propose a novel sensing method MoiréPose to achieve ultra-high precision on the camera's 6-DoF pose estimation. The purpose of MoiréPose is to derive the camera's 3-DoF position and 3-DoF posture relative to the screen according to the captured moiré pattern, which is produced by the superposition of the camera's Color Filter Array (CFA) and the screen raster projected onto the CFA layer. Based on moiré pattern's high sensitivity to 6-DoF pose movement and robustness to the environmental interference in the frequency domain, we propose a spectrogram-based method to realize the camera's 6-DoF detection with ultra-high precision. Moreover, we propose a thumbnail-based method to effectively extend the working range of MoiréPose, so as to realize pervasive camera-to-screen interaction. We have implemented a prototype system and evaluate the performance in real-world environments. Extensive experiment results show that MoiréPose achieves an average position error of 7.5mm and an overall posture error of 1.66°.

User-perceived quality of experience (QoE) is critical as mobile video streaming experiences a substantial growth. User's demands are becoming diversified where accelerated play-back is the preference of a considerable part of users. However, the limited and fluctuate mobile bandwidth is often not capable of satisfying user's demand of watching video at 2x or higher speed because of consequential frequent rebuffering. Previous adaptive bitrate (ABR) algorithms hardly consider the variety of user playback rates. In this work, we fully exploit the relation between user-perceived, i.e., subjective video quality and the characteristic of video content. The result of our motivational experiments shows that viewers are less sensitive to the bitrate variation and playback rate alternation if there is higher degree of motion in the video. With above guidelines, we adaptively adjust the quality configuration and playback rate to significantly reduce the rebuffering while achieving similar or even higher subjective quality. Then we formulate subjective quality and playback rate adaption as a QoE maximization problem and propose the content based subjective quality and playback rate adaptation algorithm (CSP) utilizing Lyapunov optimization technique. Via rigorous proof, the time-average QoE achieved by CSP is in$O(1/V)$gap compared to optimal value, where$V$is the control parameter. Extensive evaluations confirm the superiority of our proposed algorithm over other state-of-the-art algorithms under both normal and accelerated playback rate.

The detection of objects via neural networks plays a key role in various video analytics, but consumes huge resources. Due to the limited on-device computing capability, such real-time detections should be precisely used for the objects that need the most attention. Unfortunately, as the target objects keep moving, existing systems fail to conduct adaptive detections over multiple regions in a video, and existing tracking mechanisms are easily affected by background contents. Therefore, we propose to design attention-aware on-device detection for analytics, to increase the quality of detections for those targets. However, the uncertainty of detections, the attention shift over regions, and the provisioning of on-device resources essentially hamper us from efficient analytics. We formulate such a scenario as a non-linear integer program in long-term scope, to maximize the detection accuracy. Afterwards, we design an online mechanism to orchestrate the detection model for each region in the video to cope with the moves of the targets, via a queue-based adaptation and the randomized rounding. Via rigorous proof, both dynamic regret regarding detection accuracy and the real-time requirement for the video analytics are ensured. The testbed experiments confirm the superiority of our approach over multiple state-of-the-art algorithms.

In industrial production, the orientation of facility is a powerful indicator to verify whether the facility is in a normal operating track. In this paper, we present LightGyro, a cheap and efficient batteryless scheme to measure the facility orientation, it leverages the orientation amplification effect of reflection to improve the measuring accuracy to one degree. LightGyro system is composed of low-cost camera, batteryless reflective film and LEDs. In the working process of LightGyro, we attach a reflective film to the target and let it reflect the light from LEDs to the camera. Then the LightGyro would extract the LED-related spots in the captured frame and restore the reflection route to measure the orientation. To extract the LED-related spots from complicated background automatically, we propose to leverage the affine transformation to search for the topology of multiple spots which is related to the deployed LED array. To address the dimension missing issue caused by camera projection and restore the reflection route, we propose a light array-based reflection model to extract the missing dimension from relative positions of multiple spots. To the best of our knowledge, this is the first work to utilize light reflection to measure orientation. Our experiments show that the average accuracy of LightGyro achieves less than 2◦. When the reflective film is far from the camera, the mean error is less than 1◦.

Graph Convolutional Networks (GCNs) are popular for learning representation of graph data and have a wide range of applications in social networks, recommendation systems, etc. However, training GCN models for large networks is resource intensive and time consuming, which hinders them from real deployment. The existing GCN training methods intended to optimize the sampling of mini-batches for stochastic gradient descent to accelerate training process, which did not reduce the problem size and had limited reduction in computation complexity. In this paper, we argue that a GCN can be trained with a sampled subgraph to produce approximate node representations, which inspires us a novel perspective to accelerate GCN training via network sampling. To this end, we propose a label-centric cumulative sampling (LCS) framework for training GCNs for large graphs. The proposed method constructs a subgraph cumulatively based on probabilistic sampling, and trains the GCN model iteratively to generate approximate node representations. The optimality of LCS is theoretically guaranteed to minimize the bias during node aggregation procedure in GCN training. Extensive experiments based on four real-world network datasets show that the LCS framework accelerates the training for the state-of-the-art GCN models up to 17x without causing noteworthy model accuracy drop.

Mobile and wearable devices have become more and more popular. However, the tiny touch screen leads to inefficient interaction with these devices, especially for text input. In this article, we proposeDynaKey, which allows people to type on a virtual keyboard printed on a piece of article or drawn on a desk, for inputting text into a head-mounted camera device (e.g., smart glasses). By using the built-in camera and gyroscope, we capture image frames during typing and detect possible head movements, then track keys, detect fingertips, and locate keystrokes. To track the changes of keys’ coordinates in images caused by natural head (i.e., camera) movements, we introduce perspective transformation to transform keys’ coordinates among different frames. To detect and locate keystrokes, we utilize the variation of fingertip’s coordinates across multiple frames to detect possible keystrokes for localization. To reduce the time cost, we combine gyroscope and camera to adaptively track the keys, and introduce a series of optimizations, such as keypoint detection, frame skipping, multithread processing, etc. Finally, we implement DynaKey on Android-powered devices. The extensive experimental results show that our system can efficiently track and locate the keystrokes in real time. Specifically, the average tracking deviation of the keyboard layout is less than 3 pixels and the Intersection over Union (IoU) of a key in two consecutive images is above 93%. The average keystroke localization accuracy reaches 95.5%.

With the rising of demands for novel human-computer interaction approaches in the 2D plane, a number of intelligent devices come into being. For example, Microsoft Surface Dial supports simple clicks and rotations for the interaction with computer. However, these approaches are dedicated devices, and they might require batteries or have limited functions. In this paper, we propose RF-Dial to realize a light-weight, battery-free and functional 2D human-computer interaction solution via commercial off-the-shelf (COTS) passive RFID tags. What RF-Dial shines is that it can easily turn an ordinary object, e.g., a board eraser, into an intelligent interaction device. By deploying a tag array on the side face of the object together with a dipole tag on the top face, RF-Dial cannot only track the rigid motion of the object but also detect the touch gesture of a user on the surface of the object, including translation, rotation, click, press and hold, and swipe. To do the motion tracking, RF-Dial builds a phase-based model that captures the translation and the rotation of the tagged object simultaneously, by jointly exploiting the information of phase variations and the topology of the tag array. To detect the touch gesture, RF-Dial builds an RSSI-based model that uses the impact of the touching finger on the tag antenna’s impedance to estimate the touch position in real time, which is robust to environmental factors like position or orientation. We implemented a prototype of RF-Dial with commodity RFID devices. Extensive experiments show that RF-Dial achieves an accurate rigid motion tracking, with a small error of 0.6cm for the translation tracking, and a small error of 1.9 degrees for the rotation estimation. Besides, RF-Dial can also detect the touch gesture accurately, as the 90 percent of touch position errors are less than 2.09mm.

Among all the road accidents, speeding is the most deadly factor. To reduce speeding, it is essential to devise efficient schemes for ubiquitous speed monitoring. Traditional approaches either suffers from using special equipment(e.g., radar speed gun) or special deployment(e.g., position-fixed cameras). In this article, we propose SpeedTalker, a mobile phone-based approach to perform speed detection on automobiles. By leveraging the built-in microphones and camera from the mobile phone, SpeedTalker estimates the automobile speed by passively sensing the acoustic and image signals. We propose an integrated solution to effectively estimate the automobile’s speed based on COTS devices, and provide a platform for every pedestrian to help report the speeding event of automobiles. Specifically, we use the time difference of arrivals (TDOA) model based on acoustic signals to figure out the candidate trajectories of automobile, and use the pin-hole model based on image frames to figure out the vertical distance between the user’s position and the automobile’s trajectory, thus to estimate the unique trajectory. Combined with the time stamp of the trajectory, the automobile speed can be estimated. Besides, we propose a method to effectively mitigate the influence of the movement jitters of mobile phone. We implemented a system prototype for SpeedTalker and estimated the automobile speed with high accuracy. Experiment results show that in the scenario of single automobile, SpeedTalker can achieve an average estimation error of 6.1 percent compared to radar speed guns. In the scenario of multiple automobiles, SpeedTalker can achieve an average estimation error of 9.8 percent, which is acceptable for usage.

Major cities worldwide have millions of cameras deployed for surveillance, business intelligence, traffic control, crime prevention, etc. Real-time analytics on video data demands intensive computation resources and high energy consumption. Traditional cloud-based video analytics relies on large centralized clusters to ingest video streams. With edge computing, we can offload compute-intensive analysis tasks to nearby servers, thus mitigating long latency incurred by data transmission via wide area networks. When offloading video frames from the front-end device to an edge server, the application configuration (i.e., frame sampling rate and frame resolution) will impact several metrics, such as energy consumption, analytics accuracy and user-perceived latency. In this paper, we study the configuration selection and bandwidth allocation for multiple video streams, which are connected to the same edge node sharing an upload link. We propose an efficient online algorithm, called JCAB, which jointly optimizes configuration adaption and bandwidth allocation to address a number of key challenges in edge-based video analytics systems, including edge capacity limitation, unknown network variation, intrusive dynamics of video contents. Our algorithm is developed based on Lyapunov optimization and Markov approximation, works online without requiring future information, and achieves a provable performance bound. We also extend the proposed algorithms to the multi-edge scenario in which each user or video stream has an additional choice about which edge server to connect. Extensive evaluation results show that the proposed solutions can effectively balance the analytics accuracy and energy consumption while keeping low system latency in a variety of settings.

Nowadays, detecting and evaluating the internal structure of packages becomes a crucial task for logistics systems to guarantee reliability and security. However, prior solutions such as X-ray diffraction and WiFi-based detection are not suitable for this purpose. X-ray-based methods usually require manual analysis or image processing algorithms with high complexity, while WiFi-based solutions may fail to detect complex structures due to the significant error of the RF-signal features. In this article, we propose RF-Detector, a low-cost RFID solution for performing three-dimensional (3D) structure detection of items contained in the packages, including the item orientations and relative locations. We thoroughly investigate a brand-new sensing model for RFID-based 3D structure detection, i.e., revolving scanning. We propose not only the fundamental revolving model but also a novel calibration method for the undesired deployments. We have implemented a prototype system to evaluate the performance of RF-Detector. Extensive evaluations in real settings show the effectiveness of RF-Detector, achieving very high accuracy of the internal 3D structure detection.

Gait rehabilitation is a common method of postoperative recovery after the user sustains an injury or disability. However, traditional gait rehabilitations are usually performed under the supervision of rehabilitation specialists, which implies that the patients cannot receive adequate gait assessment anytime and anywhere. In this article, we propose GaitTracker, a novel system to remotely and continuously perform gait monitoring and analysis by three-dimensional (3D) skeletal tracking in a wearable approach. Specifically, this system consists of four Inertial Measurement Units (IMU), which are attached on the shanks and thighs of the human body. According to the measurements from these IMUs, we can obtain the motion signals of lower limbs during gait rehabilitation. By adaptively synchronizing coordinate systems of different IMUs and building the geometric model of lower limbs, the exact gait movements can be reconstructed, and gait parameters can be extracted without any prior knowledge. GaitTracker offers three key features: (1) a unified 3D skeletal model to depict the precise gait movement and parameters in 3D space, (2) a coordinate system synchronization scheme to perform space synchronization over all the IMU sensors, and (3) an automatic estimation method for the user-specific geometric parameters. In this way, GaitTracker is able to accurately perform 3D skeletal tracking of lower limbs for gait analysis, such as evaluating the gait symmetry and the gait parameters including the swing/stance time. We implemented GaitTracker and evaluated its performance in real applications. The experimental results show that, the average error for skeleton angle estimation, joint displacement estimation, and gait parameter estimation are 3∘, 2.3%, and 3%, respectively, outperforming the state of the art.

In the multi-access edge computing environment, app vendors deploy their services and applications at the network edges, and edge users offload their computation tasks to edge servers. We study the user-perceived delay-aware service placement and user-allocation problem in edge environment. We model the MEC-enabled network, where the user-perceived delay consists of computing delay and transmission delay. The total cost in the offloading system is defined as the sum of service placement, edge server usage and energy consumption cost, and we need to minimize the total cost by determining the overall service-placing decision and user-allocation decision, while guaranteeing that the user-perceived delay requirement of each user is fulfilled. Our considered problem is formulated as a Mixed Integer Linear Programming problem, and we prove its NP-hardness. Due to the intractability of the considered problem, we propose a LOCal-search based algorithm for USer-perceived delay-aware service placement and user-allocation in edge environment, named LOCUS, which starts with a feasible solution and then repeatedly reduces the total cost by performing local-search steps. After that, we analyze the time complexity of LOCUS and prove that it achieves provable guaranteed performance. Finally, we compare LOCUS with other existing methods and show its good performance through experiments.

Efficiently analyzing geo-distributed datasets is emerging as a major demand in a cloud-edge system. Since the datasets are often generated in closer proximity to end users, traditional works mainly focus on offloading proper tasks from those hotspot edges to the datacenter to decrease the overall completion time of submitted jobs in a one-shot manner. However, optimizing the completion time of current job alone is insufficient in a long-term scope since some datasets would be used multiple times. Instead, optimizing the data distribution is much more efficient and could directly benefit forthcoming jobs, although it may postpone the execution of current one. Unfortunately, due to the throwaway feature of data fetcher, existing data analytics systems fail to re-distribute corresponding data out of hotspot edges after the execution of data analytics. In order to minimize the overall completion time for a sequence of jobs as well as to guarantee the performance of current one, we propose to re-distribute the data along with task offloading, and formulate corresponding ε-bounded data-driven task scheduling problem over wide area network under the consideration of edge heterogeneity. We design an online schemarunData, which offloads proper tasks and related data via piggybacking to the datacenter based on delicately calculated probabilities. Through rigorous theoretical analysis,runData is proved concentrated on its optimum with high probability. We implementrunData based on Spark and HDFS. Both testbed results and trace-driven simulations show that run Data re-distributes proper data via piggybacking and achieves up to 37 percent reduction on average response time compared with state-of-the-art schemas.

Mobile Edge Computing (MEC) has become an attractive solution to enhance the computing and storage capacity of mobile devices by leveraging available resources on edge nodes. In MEC, the arrivals of tasks are highly dynamic and are hard to predict precisely. It is of great importance yet very challenging to assign the tasks to edge nodes with guaranteed system performance. In this article, we aim to optimize the revenue earned by each edge node by optimally offloading tasks to the edge nodes. We formulate the revenue-driven online task offloading (ROTO) problem, which is proved to be NP-hard. We first relax ROTO to a linear fractional programming problem, for which we propose the Level Balanced Allocation (LBA) algorithm. We then show the performance guarantee of LBA through rigorous theoretical analysis, and present the LB-Rounding algorithm for ROTO using the primal-dual technique. The algorithm achieves an approximation ratio of$2(1+\xi)\ln (d+1)$with a considerable probability, where$d$is the maximum number of process slots of an edge node and$\xi$is a small constant. The performance of the proposed algorithm is validated through both trace-driven simulations and testbed experiments. Results show that our proposed scheme is more efficient compared to baseline algorithms.

Deep Convolutional Neural Networks (CNNs) are successfully applied in many complex tasks, but their storage and huge computational costs hinder their deployment on edge devices. CNN model compression techniques have been widely studied in the past five years, most of which are conducted in the spatial domain. Inspired by the sparsity and low-rank properties of weight matrices in the frequency domain, we propose a novel frequency pruning framework for model compression and acceleration while maintaining high-performance. We firstly apply Discrete Cosine Transform (DCT) on convolutional kernels and train them in the frequency domain to get sparse representations. Then we propose an iterative model compression method to decompose the frequency matrices with a sampled-based low-rank approximation algorithm, and then fine-tune and recompose the low-rank matrices gradually until a predefined compression ratio is reached. We further demonstrate that model inference can be conducted with the decomposed frequency matrices, where model parameters and inference cost can be significantly reduced. Extensive experiments using well-known CNN models based on three open datasets show that the proposed method outperforms the state-of-the-arts in reduction of both the number of parameters and floating-point operations (FLOPs) without sacrificing too much model accuracy.

Operating federated learning optimally over distributed cloud-edge networks is a non-trivial task, which requires to manage data transference from user devices to edges, resource provisioning at edges, and federated learning between edges and the cloud. We formulate a non-linear mixed integer program, minimizing the long-term cumulative cost of such a federated learning system while guaranteeing the desired convergence of the machine learning models being trained. We then design a set of novel polynomial-time online algorithms to make adaptive decisions by solving continuous solutions and converting them to integers to control the system on the fly, based only on the predicted inputs about the dynamic and uncertain cloud-edge environments via online learning. We rigorously prove the competitive ratio, capturing the multiplicative gap between our approach using predicted inputs and the offline optimum using actual inputs. Extensive evaluations with real-world training datasets and system parameters confirm the empirical superiority of our approach over multiple state-of-the-art algorithms.

Real-time on-device object detection for video analytics fails to meet the accuracy requirement due to limited resources of mobile devices while offloading object detection inference to edges is time-consuming due to the transference of video data over edge networks. Based on the system with both on-device object tracking and edge-assisted analysis, we formulate a non-linear time-coupled program over time, maximizing the overall accuracy of object detection by deciding the frequency of edge-assisted inference, under the consideration of both dynamic edge networks and the constrained detection latency. We then design a learning-based online algorithm to adjust the threshold for triggering edge-assisted inference on the fly in terms of the object tracking results, which essentially controls the deviation of on-device tracking between two consecutive frames in the video, by only taking previously observable inputs. We rigorously prove that our approach only incurs sub-linear dynamic regret for the optimality objective. At last, we implement our proposed online schema, and extensive testbed results with real-world traces confirm the empirical superiority over alternative algorithms, in terms of up to 36% improvement on detection accuracy with ensured detection latency.

As an essential communication way for deaf-mutes, sign languages are expressed by human actions. To distinguish human actions for sign language understanding, the skeleton which contains position information of human pose can provide an important cue, since different actions usually correspond to different poses/skeletons. However, skeleton has not been fully studied for Sign Language Translation (SLT), especially for end-to-end SLT. Therefore, in this paper, we propose a novel end-to-end Skeleton-Aware neural Network (SANet) for video-based SLT. Specifically, to achieve end-to-end SLT, we design a self-contained branch for skeleton extraction. To efficiently guide the feature extraction from video with skeletons, we concatenate the skeleton channel and RGB channels of each frame for feature extraction. To distinguish the importance of clips, we construct a skeleton-based Graph Convolutional Network (GCN) for feature scaling, i.e., giving importance weight for each clip. The scaled features of each clip are then sent to a decoder module to generate spoken language. In our SANet, a joint training strategy is designed to optimize skeleton extraction and sign language translation jointly. Experimental results on two large scale SLT datasets demonstrate the effectiveness of our approach, which outperforms the state-of-the-art methods. Our code is available at https://github.com/SignLanguageCode/SANet.

Performing federated learning continuously in edge networks while training data are dynamically and unpredictably streamed to the devices faces critical challenges, including the global model convergence, the long-term resource budget, and the uncertain stochastic network and execution environment. We formulate an integer program to capture all these challenges, which minimizes the cumulative total latency of stream learning on device and federated learning between devices and the edge server. We then decouple the problem, design an online learning algorithm for controlling the number of local model updates via a convex-concave reformulation and rectified gradient-descent steps, and design a bandit learning algorithm for selecting the edge server for global model aggregations by incorporating the budget information to strike the exploit-explore balance. We rigorously prove the sub-linear regret regarding the optimization objective and the sub-linear constraint violation regarding the maximal on-device load, while guaranteeing the convergence of the global model trained. Extensive evaluations with real-world training data and input traces confirm the empirical superiority of our approach over multiple state-of-the-art algorithms.

Congestion control is a fundamental mechanism for TCP protocol, which has been extensively studied in the past three decades. However, our experimental evaluations show that the state-of-art congestion control algorithms such as Cubic and BBR are far from optimal: they have unresolved issues such as insufficient usage of available bandwidth, inadaptable to dynamic bandwidth variants, and compromising on one or more performance dimensions. To address these challenges, we propose a novel congestion control mechanism called NeuRoc that coordinately uses online changepoint detection and deep reinforcement learning (DRL) technique to generate the optimal congestion control policy, which allows TCP operating at Kleinrock ’s optimal operation point to achieve fully bandwidth usage and low latency. To address the practical issues of deploying the deep learning based congestion control mechanism, we propose a cold-started training and deployment framework to reduce the cost of bootstrap. We implement NeuRoc on an emulation platform which connects to the Linux network protocol stack through virtual network interfaces. Extensive experiments show that NeuRoc achieves the best throughput-latency tradeoff compared with the state-of-the-arts in a variety of scenarios.

Katz centrality is a fundamental concept to measure the influence of a vertex in a social network. However, existing approaches to calculating Katz centrality in a large-scale network are unpractical and computationally expensive. In this article, we propose a novel method to estimate Katz centrality based on graph sampling techniques, which object to achieve comparable estimation accuracy of the state-of-the-arts with much lower computational complexity. Specifically, we develop a Horvitz–Thompson estimate for Katz centrality by using a multi-round sampling approach and deriving an unbiased mean value estimator. We further propose SAKE , a S ampling-based A lgorithm for fast K atz centrality E stimation. We prove that the estimator calculated by SAKE is probabilistically guaranteed to be within an additive error from the exact value. Extensive evaluation experiments based on four real-world networks show that the proposed algorithm can estimate Katz centralities for partial vertices with low sampling rate, low computation time, and it works well in identifying high influence vertices in social networks.

Currently, the logistic industry has introduced 3D reconstruction to monitor the package placement in the warehouse. Previous 3D reconstruction solutions mainly utilize computer vision or sensor-based methods, which are restricted to the line-of-sight or the battery life. Therefore, we propose a passive RFID-based solution, called RF-3DScan, to perform 3D reconstruction on tagged packages, including the package orientation and the package stacking. The basic idea is that a moving antenna can obtain RF-signals from the tags attached on packages with the 1D linear mobile scanning. Through extracting phase differences to build angle profiles for each tag, RF-3DScan derives their relative positions, further determines the package orientation and the coarse-grained package stacking. By simply performing the 2D scanning, RF-3DScan can provide the fine-grained package stacking determination. We implement a prototype system of RF-3DScan and evaluate its performance in real settings. Our experiment results show that RF-3DScan can achieve about 92.5 percent identification accuracy of the bottom face, and an average error about 4.08° of thethe rotation angle. For the package stacking, 1D scanning can achieve the comparable performance in comparison with 2D scanning.

Due to the sudden movement during the camera shoot, the videos retrieved from the hand-held mobile devices often suffer from undesired frame jitters, leading to the loss of video quality. In this paper, we present a video stabilization solution in mobile devices via inertial-visual state tracking. Specifically, during the video shoot, we use the gyroscope to estimate therotationof camera, and use the structure-from-motion among the image frames to estimate thetranslationof camera. We build a camera projection model by considering the rotation and translation of the camera, and the camera motion model to depict the relationship between the inertial-visual state and the camera's 3D motion. By fusing the inertial measurement (IMU)-based method and the computer vision (CV)-based method, our solution is robust to the fast movement and violent jitters, moreover, it greatly reduces the computation overhead in video stabilization. In comparison to the IMU-based solution, our solution can estimate the translation in a more accurate manner, since we use the feature point pairs in adjacent image frames, rather than the error-prone accelerometers, to estimate the translation. In comparison to the CV-based solution, our solution can estimate the translation with less number of feature point pairs, since the number of undetermined degrees of freedom in the 3D motion directly reduces from 6 to 3. We implemented a prototype system on smart glasses and smart phones, and evaluated the performance under real scenarios, i.e., the human subjects used mobile devices to shoot videos while they were walking, climbing or riding. The experiment results show that our solution achieves 32 percent better performance than the state-of-art solutions in regard to video stabilization. Moreover, the average processing time latency is 32.6ms, which is lower than the conventional inter-frame time interval, i.e., 33ms, and thus meets the real-time requirement for online processing.

Instead of relying on remote clouds, today's Augmented Reality (AR) applications usually send videos to nearby edge servers for analysis (such as objection detection) so as to optimize the user's quality of experience (QoE), which is often determined by not only detection latency but also detection accuracy, playback fluency, etc. Therefore, many studies have been conducted to help adaptively choose best video configuration, e.g., resolution and frame per second (fps), based on network bandwidth to further improve QoE. However, we notice that the video content itself has significant impacts on the configuration selection, e.g., the videos with high-speed objects must be encoded with a high fps to meet the user's fluency requirement. In this article, we aim to adaptively select configurations that match the time-varying network condition as well as the video content. We design Cuttlefish, a system that generates video configuration decisions using reinforcement learning (RL). Cuttlefish trains a neural network model that picks a configuration for the next encoding slot based on observations collected by AR devices. Cuttlefish does not rely on any pre-programmed models or specific assumptions on the environments. Instead, it learns to make configuration decisions solely through observations of the resulting performance of historical decisions. Cuttlefish automatically learns the adaptive configuration policy for diverse AR video streams and obtains a gratifying QoE. We compared Cuttlefish to several state-of-the-art bandwidth-based and velocity-based methods using trace-driven and real world experiments. The results show that Cuttlefish achieves a 18.4-25.8 percent higher QoE than the others.

The booming of Convolutional Neural Networks (CNNs) has empowered lots of computer-vision applications. Due to its stringent requirement for computing resources, substantial research has been conducted on how to optimize its deployment and execution on resource-constrained devices. However, previous works have several weaknesses, including limited support for various CNN structures, fixed scheduling strategies, overlapped computations, high synchronization overheads, etc. In this article, we present DeepSlicing, a collaborative and adaptive inference system that adapts to various CNNs and supports customized flexible fine-grained scheduling. As a built-in functionality, DeepSlicing has supported typical CNNs including GoogLeNet, ResNet, etc. By partitioning both model and data, we also design an efficient scheduler, Proportional Synchronized Scheduler (PSS), which achieves the trade-off between computation and synchronization. Based on PyTorch, we have implemented DeepSlicing on the testbed with real-world edge settings that consists of 8 heterogeneous Raspberry Pi's. The results indicate that DeepSlicing with PSS outperforms the existing systems dramatically, e.g., the inference latency and memory footprint are reduced up to 5.79× and 14.72×, respectively.

In traditional device‐to‐device (D2D) communication based on wireless channel, identity authentication and spontaneous secure connections between smart devices are essential requirements. In this paper, we propose an imitation‐resistant secure pairing framework including authentication and key generation for smart devices, by shaking these devices together. Based on the data collected by multiple sensors of smart devices, these devices can authenticate each other and generate a unique and consistent symmetric key only when they are shaken together. We have conducted comprehensive experimental study on shaking various devices. Based on this study, we have listed several novel observations and extracted important clues for key generation. We propose a series of innovative technologies to generate highly unique and completely randomized symmetric keys among these devices, and the generation process is robust to noise and protects privacy. Our experimental results show that our system can accurately and efficiently generate keys and authenticate each other.

Despite their great success in various fields, modern convolutional neural networks (CNNs) require huge amount of computation in inference due to their deeper network structure, which prevents them from being used in resource-limited devices such as mobile phones and embedded sensors. Recently, filter pruning had been introduced as a promising model compression method to reduce computation cost and storage overhead. However, existing filter pruning approaches are mainly model-based, which rely on empirical model to evaluate the importance of filters and set parameters manually to guide model compression. In this paper, we observe that CNNs commonly consist of large amount of inactive filters, and introduce Filter Inactive RatE (FIRE), a novel metric to evaluate the importance of filters in a neural network. Based on FIRE, we develop a learning based filter pruning strategy called FIREPruning for fast model compression. It adopts a regression model to predict the FIRE value and uses a three stage pipeline (FIRE prediction, pruning, and fine-tuning) to compress the neural network efficiently. Extensive experiments based on widely-used CNN models and well-known datasets show that FIREPruning reduces overall computation cost up to 86.9% without sacrificing too much accuracy, which significantly outperforms the state-of-the-art model compression methods.

Advertising income depends on the amount of clicks by users of websites and mobile applications. However, the emergence of click fraud greatly reduces the real benefits of the advertisement. Most existing researches focus on detecting click fraud by analyzing properties and patterns of click data streams, but attackers can construct data that looks legitimate by replaying former data streams. In this paper, we propose a novel system called ClickGuard to detect click fraud attacks. ClickGuard takes advantage of motion sensor signals from mobile devices, since the pattern of motion signals is completely different under real click events and fraud events. To prevent attackers from bypassing the system by faking the time-domain statistical characteristics of original signals, we introduce the MFCC algorithm in feature extraction phase. MFCC algorithm can extract frequency-domain features of original signals in specific frequency bands which are hardly constructed out of thin air. Classifiers are finally constructed using these features and several machine learning algorithms. Experiments show that ClickGuard can achieve the accuracy of 96.71% in general environment and 84.16% when attackers modify the time-domain statistical characteristics of raw data.

Software Defined Networking (SDN) is beneficial to many applications, such as intra-datacenter communication, inter-datacenter transportation, etc., due to its centralized control. However, this centralized control frequently makes the controller a bottleneck, due to the large amount of interactions between the controller and switches. In this paper, we characterize such interactions as control traffic, and propose RouteStitch to minimize such kind of traffic. RouteStitch exploits existing route entries in switches to build new paths. To this end, RouteStitch first builds a graph model to describe existing route entries. Then, on such a model, a novel minimum color-alternation routing problem is defined to minimize control traffic, after which an optimal algorithm is proposed on a fixed routing path. For general paths, an O(log2L)-competitive online algorithm is designed to build new paths in an online manner that preserves fundamental property of switch Ternary Content Addressable Memory (TCAM) capacity and allowed maximum hop length L. Extensive simulation results based on realistic topology show that RouteStitch has good performance in terms of reducing control traffic, by 40%.

Nowadays, detecting and evaluating the internal structure of packages becomes a crucial task for logistics systems to guarantee the reliability and security. However, prior solutions such as X-ray diffraction and WiFi-based detection are not suitable for this purpose. X-ray-based methods usually require manual analysis or image processing algorithms with high complexity, while WiFi-based solutions may fail to detect complex structures due to the significant error of the RF-signal features. In this paper, we propose RF-Detector, a low-cost RFID solution for performing 3D structure detection of items contained in the packages, including the item orientations and relative locations. We thoroughly investigate a brand-new sensing model for RFID-based 3D structure detection, i.e., revolving scanning. We propose not only the fundamental revolving model but also a novel calibration method towards the undesired deployment. We have implemented a prototype system to evaluate the performance of RF-Detector. Extensive evaluations in real settings show the effectiveness of RF-Detector, achieving very high accuracy of the internal 3D structure detection.

Federated learning achieves the privacy-preserving training of models on mobile devices by iteratively aggregating model updates instead of raw training data to the server. Since excessive training iterations and model transferences incur heavy usage of computation and communication resources, selecting appropriate devices and excluding unnecessary model updates can help save the resource usage. We formulate an online time-varying non-linear integer program to minimize the cumulative resource usage over time while achieving the desired long-term convergence of the model being trained. We design an online learning algorithm to make fractional control decisions based on both previous system dynamics and previous training results, and also design an online randomized rounding algorithm to convert the fractional decisions into integers without violating any constraints. We rigorously prove that our online approach only incurs sub-linear dynamic regret for the optimality loss and sub-linear dynamic fit for the long-term convergence violation. We conduct extensive trace-driven evaluations and confirm the empirical superiority of our approach over alternative algorithms in terms of up to 27% reduction on the resource usage while sacrificing only 4% reduction on accuracy.

Distributed computing is the mainstream for large-scale machine learning and big data analytics, but its performance usually suffers from unpredictable stragglers, i.e., very slow nodes. Recently, coded computing has emerged as a new distributed computing paradigm that uses coding-theoretical approaches to mitigate the effect of stragglers. Most existing coding schemes only use the results from a certain number of fastest worker nodes to recover the output and completely ignore the partial work done by other worker nodes, leading to inferior performance. In this paper, for scenarios where each worker node transmits its local result to the master node only after it has finished the whole local computation, we introduce communication at full speed to characterize the full utilization of all the communication links between each worker node that has finished its local computation and the master node, and for scenarios where each worker node computes out the local result piece by piece and can forward each piece once available, we introduce computation at full speed to characterize the full utilization of the work done entirely or partially by all the worker nodes. Considering a general polynomial-based coding framework which encapsulates many advanced coding schemes for a variety of fundamental computing tasks, we propose a randomized approach where each worker node partitions its local result into pieces, generates and forwards random linear combinations of these pieces to the master node sequentially, and theoretically demonstrate that it can lead the coding framework to achieve communication at full speed. For some typical task scenarios, we further show that computation at full speed can be achieved by mapping the encoding operations in the randomized approach into a part of encoding on the input dataset. Experiments conducted on Alibaba Cloud as well as simulations show that our approaches can reduce the total runtime significantly.

In this paper, we consider a fundamental problem: given one mobile charger that can charge multiple sensor nodes simultaneously, how we can schedule it to charge a given WSN to maximize the energy usage effectiveness (EUE)? We propose a novel charging paradigm-Overlapped Mobile Charging (OMC)- the first of its kind to the best of our knowledge. Firstly, OMC clusters sensor nodes into multiple non-overlapped sets using k-means evaluated by the Davies-Bouldin Index, such that the sensor nodes in each set have similar recharging cycles. Secondly, for each set of sensor nodes, OMC further divides them into multiple overlapped groups, and charges each group at different locations for different time durations to make sure that each overlapped sensor node just receives its required energy from multiple charging locations.

With the development of deep learning, artificial intelligence applications and services have boomed in the recent years, including recommendation systems, personal assistant and video analytics. Similar to other services in the edge computing environment, artificial intelligence computing tasks are pushed to the network edge. In this paper, we consider the multi-user edge-assisted video analytics task offloading (MEVAO) problem, where users have video analytics tasks with various accuracy requirements. All users independently choose their accuracy decisions, satisfying the accuracy requirement, and offload the video data to the edge server. With the utility function designed based on the features of video analytics, we model MEVAO as a game theory problem and achieve the Nash equilibrium. For the flexibility of making accuracy decisions under different circumstances, a deep reinforcement learning approach is applied to our problem. Our proposed design has much better performance compared with some other approaches in the extensive simulations.

MapReduce is a commonly used framework for parallel processing of data-intensive tasks, but its performance usually suffers from heavy communication load incurred by the shuffling of intermediate values (IVs) among computing servers. Recently, the Coded MapReduce framework is proposed which uses a coding scheme named coded distributed computing (CDC) to trade the communication load with extra computation in MapReduce. CDC can achieve the optimal computation-communication tradeoff when all the IVs have the same size. However, in many practical applications, the sizes of IVs can vary over a large range, leading to inferior performance. In this paper, we introduce a generalized CDC scheme which takes the sizes of IVs into account and then propose a combinatorial optimization problem aiming to minimize the communication load when the computation load is fixed. We show that the problem is NP-hard, and further propose a very efficient algorithm which achieves an approximation ratio of 2. Experiments conducted on Alibaba Cloud show that, compared to the original CDC scheme, our proposed IV size aware approach can significantly reduce the communication load and achieve a lower total execution time.

Federated learning is a very promising machine learning paradigm where a large number of clients cooperatively train a global model using their respective local data. In this paper, we consider the application of federated learning in wireless networks featuring uplink multiuser multiple-input and multiple-output (MU-MIMO), and aim at optimizing the communication efficiency during the aggregation of client-side updates by exploiting the inherent superposition of radio frequency (RF) signals. We propose a novel approach named Physical-Layer Arithmetic (PhyArith), where the clients encode their local updates into aligned digital sequences which are converted into RF signals for sending to the server simultaneously, and the server directly recovers the exact summation of these updates as required from the superimposed RF signal by employing a customized sum-product algorithm. PhyArith is compatible with commodity devices due to the use of full digital operation in both the client-side encoding and the server-side decoding processes, and can also be integrated with other updates compression based acceleration techniques. Simulation results show that PhyArith further improves the communication efficiency by 1.5 to 3 times for training LeNet-5, compared with solutions only applying updates compression.

Recommender systems had been proposed to help people to find the interested items, such as recommending products to a buyer; identifying movies or music that a user will find interest, etc. However, the existing recommendation approaches mainly focus on capturing user-item interaction patterns for prediction, and ignore the user's side information such as visit frequency and duration. In this paper, we study the side information aided website recommendation problem that using the browsing history of a set of users and their side information to predict the websites that will be of interest to a certain user. We propose a novel recommendation approach called SI-VAE that incorporates side information with the variational autoencoders (VAEs) model for top-k recommendation. The proposed method takes both user-website interaction information and side information as input, and adopts an encoder/decoder model to generate user's interested websites from partial observations. The model of SI-VAE is implemented as a neural network, and trained with a multinomial likelihood objective function to form the ranking of user-website interaction probabilities. We conduct extensive experiments on two real-world datasets, which show that the proposed model outperforms the baselines in a number of performance metrics in website recommendation.

In typical scenarios for indoor localization and tracking, it is essential to accurately track the pedestrians when they are crossing the connections of different spaces. In this paper, we propose a magnet barcode scanning-based solution for indoor pedestrian tracking. We assemble multiple magnet bars into magnet arrays as a unique magnet barcode, and deploy different magnet barcodes at different connections to label them. We embed an inertial measurement unit (IMU) into the pedestrian`s shoes. When the pedestrian crosses these connections, the magnetometer from the IMU scans the magnet barcode and recognize its corresponding ID. In this way, indoor pedestrian tracking can be regarded as a process of continuously scanning different magnet barcodes. By performing correlation analysis on these barcodes, the trace of pedestrian can be effectively depicted in the indoor map. To build a unique magnet barcode based on the magnet bar arrays, we provide an optimized structure for building the magnet barcode. To tackle the diversities of the pedestrian's gait traces in identifying the magnet barcode, we provide a generalized model based on the space axis for magnet barcode identification. As far as we know, this is the first work to use the magnet bar array to construct the magnet barcode for indoor pedestrian tracking. The real experiment results show that our system can achieve an average accuracy of 88.9% in identifying the magnet barcodes and an average accuracy of 93.1 % for indoor pedestrian tracking.

The execution and completion of analytics jobs can be significantly inflated by the slowest tasks contained. Despite task replication is well-adopted to reduce such straggler latency, existing replication strategies are unsuitable for geo-distributed analytics environments that are highly dynamic, uncertain, and heterogeneous. In this paper, we firstly model the task replication and scheduling problem over time, capturing the geo-analytics features. Afterwards, we design an online algorithm, GeoClone, to select tasks to replicate and select sites to execute the task replicas in an irrevocably online manner, through jointly considering the execution progress of each job and the resource performance in each site. We rigorously prove the competitive ratio to exhibit the theoretical performance guarantee of GeoClone, compared against the offline optimal algorithm which knows all the inputs at once beforehand. Finally, we implement GeoClone with Spark and Yarn for experiments and also conduct extensive large-scale simulations, which confirms GeoClone's practical superiority over multiple state-of-the-art replication strategies.

Assessing individual's personality traits has important implications in psychology, sociology, and economics. Conventional personality measurement methods were questionnaire-based, which are time-consuming and manpower-expensive. With the pervasive deployment of mobile communication applications, smartphone usage data was found to relate to people's social behavioral and psychological aspects. In this paper, we propose a deep learning approach to infer people's Big Five personality traits based on smartphone data. Specifically, we collect smartphone usage snapshots with an Android App, and extract features from the collected data. We propose a multi-view multi-task learning approach with a deep neural network model to fuse the extracted features and learn the Big Five personality traits jointly. Extensive experiments based on the real-world smartphone data collected from university volunteers show that the proposed approach significantly outperforms the state-of-the-art algorithms in personality prediction.

Provisioning machine learning inference as a service at the mobile network edge for distributed users in an online setting faces multiple challenges, including the accuracy-resource trade-off for model selection, the time-coupled decision for model distribution, and the unpredictable user inference workload. To overcome such challenges, we firstly model an online time-varying non-linear integer program of maximizing the overall service's inference accuracy through dynamic model instance selection, delivery and workload distribution. Afterwards, we design an online learning algorithm to make fractional control decisions, which alternates between minimizing an outer problem and maximizing an inner problem of an equivalent convex-concave formulation by only taking previously observable inputs. We further design a randomized rounding algorithm to convert the fractional decisions into integers. We rigorously prove that our approach only incurs sub-linear dynamic regret for the optimality loss and sub-linear dynamic fit for the long-term constraints violation. Finally, we conduct extensive evaluations with real- world data and confirm the empirical superiority of our approach over state-of-the-art algorithms in terms of up to 30% reduction on accuracy loss and 34% reduction on constraints violation.

Influence maximization in social networks is the problem of finding a set of seed nodes in the network that maximizes the spread of influence under certain information prorogation model, which has become an important topic in social network analysis. In this paper, we show that conventional influence maximization algorithms cause uneven spread of influence among different attribute groups in social networks, which could lead to severer bias in public opinion dissemination and viral marketing. We formulate the balanced influence maximization problem to address the trade-off between influence maximization and attribute balance, and propose a sampling based solution to solve the problem efficiently. To avoid full network exploration, we first propose an attribute-based (AB) sampling method to sample attributed social networks with respect to preserving network structural properties and attribute proportion among user groups. Then we propose an attributed-based reverse influence sampling (AB-RIS) algorithm to select seed nodes from the sampled graph. The proposed AB-RIS algorithm runs efficiently with guaranteed accuracy, and achieves the trade-off between influence maximization and attribute balance. Extensive experiments based on four real-world social network datasets show that AB-RIS significantly outperforms the state-of-the-art approaches in balanced influence maximization.

Emotion detection in online social networks (OSNs) can benefit kinds of applications, such as personalized advertisement services, recommendation systems, etc. Conventionally, emotion analysis mainly focuses on the sentence level polarity prediction or single emotion label classification, however, ignoring the fact that emotions might coexist from users' perspective. To this end, in this work, we address the multiple emotions detection in OSNs from user-level view, and formulate this problem as a multilabel learning problem. First, we discover emotion labels correlations, social correlations, and temporal correlations from an annotated Twitter data set. Second, based on the above observations, we adopt a factor graph-based emotion recognition model to incorporate emotion labels correlations, social correlations, and temporal correlations into a general framework, and detect the multiple emotions based on the multilabel learning approach. Performance evaluation demonstrates that the factor graph-based emotion detection model can outperform the existing baselines.

Caching popular videos at mobile edge servers (MESs) has been confirmed as a promising method to improve mobile users (MUs) perceived quality of experience (QoE) and to alleviate the server load. However, with the multiple bitrate encoding techniques prevalently employed in modern streaming services, caching deployment is challenging for the following three facts: (1) cooperative caching should be explored for MUs located at overlapped coverage areas of MESs; (2) there exists tradeoff consideration for caching either high bitrate videos or high diversity videos; and (3) the relationship between MU perceived QoE and MU received bitrate, known as QoE function, varies in different services. Aiming to maximize the MU perceived QoE, we formulate the multiple bitrate video caching problem, and prove this problem is NP-hard for any given positive and strictly increasing QoE function. We then propose a polynomial complexity algorithm based on a general QoE function, which can achieve an approximate ratio arbitrarily close to 1/2. Specifically, for a linear QoE function, we explore useful property of optimal solutions, based on which more efficient algorithms are proposed. We demonstrate the effectiveness of our solutions via both theoretical analysis and extensive simulations.

Logistics monitoring is a fundamental application that utilizes RFID systems to manage numerous tagged-objects. Due to the frequent rearrangement of tagged-objects, a fast RFID-based tracking approach is highly desired for accurate logistics distribution. However, traditional RFID systems usually take tens of seconds to interrogate hundreds of RFID tags, not to mention the time delay involved to locate all the tags, which severely prevents from in-time tracking. To address this issue, we reduce the problem domain by first distinguishing the motion status of the tagged-objects, i.e., “stationary” or “moving”, and then tracking the moving objects with the state-of-the-art localization schemes, which significantly reduces the efforts of tracking all the objects. Toward this end, we propose a moving tag detection mechanism, which achieves the time efficiency by exploiting the useless collision signal in RFID systems. In particular, we extract two kinds of physical-layer features (namely, phase profile and backscatter link frequency) from the collision signal received by the USRP to distinguish tags at different positions. We further develop the Graph Matching (GM) method and Coherent Phase Variance (CPV) method to detect the moving tagged-objects. Experiment results show that our approach can accurately detect the moving objects while reducing 80 percent inventory time compared with the state-of-art solutions.

The Information-Centric Networking (ICN) paradigm has emerged to shift the current host-based network model to a content-oriented one in order to cope with the dominant content-based services in the Internet. Congestion control is a fundamental design concern to support massive content delivery in ICN. While the existing flow-based and hop-by-hop congestion control mechanisms suffer from complexity and compatibility issues, we propose RevMax, a gateway-aware congestion control mechanism based on the architecture of NDN, a well-known ICN platform, to overcome the drawbacks. In the proposed mechanism, the gateway offers a price to each end-user, which urges the user to adjust the request rate according to the price. The optimal pricing policy for the gateway is shown to be formulated as a revenue maximization problem, and an efficient algorithm is proposed to derive the optimal solution. The proposed RevMax mechanism is implemented in NDN and compared to PCON, a state-of-the-art congestion control mechanism for ICNs. Extensive experiments show that RevMax achieves higher throughput, lower network latency, and better fairness in a variety of network scenarios.

All-optical switching has been considered as a natural choice to keep pace with growing fiber link capacity. One key research issue of all-optical switching is the design of optical buffers for packet contention resolution. One of the most general buffering schemes is optical priority queue, where every packet is associated with a unique priority upon its arrival and departs the queue in order of priority, and the packet with the lowest priority is always dropped when a new packet arrives but the buffer is full. In this paper, we focus on the feedback construction of an optical priority queue with a single (M + 2) × (M + 2) optical crossbar Switch and M fiber Delay Lines (SDL) connecting M inputs and M outputs of the switch. We propose a novel construction of an optical priority queue with buffer 2Θ(√M), which improves substantially over all previous constructions that only have buffers of O(Mc) size for constant integer c. The key ideas behind our construction include (i) the use of first in first out multiplexers, which admit efficient SDL constructions, for feeding back packets to the switch instead of fiber delay lines, and (ii) the use of a routing policy that is similar to self-routing, where each packet entering the switch is routed to some multiplexer mainly determined by the current ranking of its priority.

Mobile Augmented Reality (MAR) applications usually contain computation-intensive tasks which far outstrip the capability of mobile devices. One way to overcome this is offloading computation-intensive MAR tasks to remote clouds. However, the wide area network delay is hard to reduce. Thanks to edge computing, we can offload MAR tasks to nearby servers. Prior studies focus on either single-task MAR applications offloading or dependent tasks offloading for a single user. In this article, we study the offloading decision of MAR applications from multiple users, each of which is comprised of a chain of dependent tasks, over a generic cloud-edge system consisting of a group of heterogeneous edge servers and remote clouds. We formulate the Multi-user Multi-task MAR Application Scheduling (M3AS) problem, which is NP-hard. We present Mutas, an efficient scheduling algorithm that jointly optimizes server assignment and resource management. We also consider the online version of M3AS and present OnMutas. Extensive evaluations demonstrate that both Mutas and OnMutas can significantly reduce the service delays of MAR applications when compared to three other heuristics.

With the rapid development of machine-to-machine (M2M) mobile smart terminals, M2M services can be used in a wide range of industries, including such as telemedicine, remote meter reading and public security. Since different industries and enterprise users have different requirements for M2M specific applications, the security identity authentication of M2M mobile terminals is particularly worthy of attention. Existing methods can effectively solve the unsustainable problem of one-time verification, however they cannot address the dynamic relevance characteristics of user behavior sufficiently. Thus, the accuracy of user identity authentication needs to be further improved. In this paper, we propose a terminal identity authentication technology based on user association behavior analysis. In order to identify the abnormal login during each behavior process of authenticated user, we take largest coincident part of the user behavior sequence and short coincide into consideration. In addition, we propose a Similarity-based Behavior Sequence Similarity Algorithm (BCS-SSA) based on the traditional sequence pattern of Behavior Common Subsequence. The experimental results demonstrate that the proposed method can effectively improve the accuracy of user's behavioral sequence, and prove the uniqueness of different sequences on the other hand.

Computation offloading makes sense to the interaction between users and compute-intensive applications. Current researches focused on deciding locally or remotely executing an application, but ignored the specific offloading proportion of application. A full offloading cannot make the best use of client and server resources. In this paper, we propose an innovative reinforcement learning (RL) method to solve the proportional computation problem. We consider a common offloading scenario with time-variant bandwidth and heterogeneous devices, and the device generates applications constantly. For each application, the client has to choose locally or remotely executing this application, and determines the proportion to be offloaded. We formalize the problem as a long-term optimization problem, and then propose a RL-based algorithm to solve it. The basic idea is to estimate the benefit of posible decisions, of wihch the decision with the maximum benefit is selected. Instead of adopting the original Deep Q Network (DQN), we propose Advanced DQN (ADQN) by adding Priority Buffer Mechanism and Expert Buffer Mechanism, which improves the utilization of samples and overcomes the cold start problem, respectively. The experimental results show ADQN's high feasibility and efficiency compared with several traditional policies, such as None Offloading Policy, Random Offloading Policy, Link Capacity Optimal Policy, and Computing Capability Optimal Policy. At last, we analyse the effect of expert buffer size and learning rate on ADQN's performance.

In conventional device-to-device (D2D) communication through wireless channels, it is an essential demand to authenticate with each other and establish spontaneous secure connections among the smart devices. In this paper, we propose an imitation-resistant mutual authentication and key generation framework for smart devices, by shaking these devices together. According to the multi-sensor data collected from smart devices, these devices are able to authenticate each other and generate a unique and consistent symmetric key if and only if they are shaken together. We have conducted comprehensive experimental study on shaking various devices, illustrated several novel observations and extracted some important clues for efficient key generation. We propose a series of novel techniques to make the key generation robust to noise and privacy-preserving, and generate highly distinctive and fully randomized symmetric keys among these devices. Realistic experiment results indicate that our solution is able to authenticate with each other and generate the symmetric keys with high accuracy and time-efficiency.

Sensor-based human activity recognition is a fundamental research problem in ubiquitous computing, which uses the rich sensing data from multimodal embedded sensors such as accelerometer and gyroscope to infer human activities. The existing activity recognition approaches either rely on domain knowledge or fail to address the spatial-temporal dependencies of the sensing signals. In this paper, we propose a novel attention-based multimodal neural network model called AttnSense for multimodal human activity recognition. AttnSense introduce the framework of combining attention mechanism with a convolutional neural network (CNN) and a Gated Recurrent Units (GRU) network to capture the dependencies of sensing signals in both spatial and temporal domains, which shows advantages in prioritized sensor selection and improves the comprehensibility. Extensive experiments based on three public datasets show that AttnSense achieves a competitive performance in activity recognition compared with several state-of-the-art methods.

Nowadays, the growing demand for the 3D human-computer interaction (HCI) has brought about a number of novel approaches, which achieve the HCI by tracking the motion of different devices, including the translation and the rotation. In this paper, we propose to use a spinning linearly polarized antenna to track the 3D motion of a specified object attached with the passive RFID tag array. Different from the fixed antenna-based solutions, which suffer from the unavoidable signal interferences at some specific positions/orientations, and only achieve the good performance in some feasible sensing conditions, our spinning antenna-based solution seeks to sufficiently suppress the ambient signal interferences and extracts the most distinctive features, by actively spinning the antenna to create the optimal sensing condition. Moreover, by leveraging the matching/mismatching property of the linearly polarized antenna, i.e., in comparison to the circularly polarized antenna, the phase variation around the matching direction is more stable, and the RSSI variation in the mismatching direction is more distinctive, we are able to find more distinctive features to estimate the position and the orientation. We build a model to investigate the RSSI and the phase variation of the RFID tag along with the spinning of the antenna, and further extend the model from a single RFID tag to an RFID tag array. Furthermore, we design corresponding solutions to extract the distinctive RSSI and phase values from the RF-signal variation. Our solution tracks the translation of the tag array based on the phase features, and the rotation of the tag array based on the RSSI variation. The experimental results show that our system can achieve an average error of 13. 6cm in the translation tracking, and an average error of 8.3° in the rotation tracking in the 3D space.

A high correlation between mood instability (MI), the rapid and constant fluctuation in mood, and mental health has been demonstrated. However, conventional approaches to measure MI are limited owing to the high manpower and time cost required. In this paper, we propose a smartphone-based MI detection that can automatically and passively detect MI with minimal human involvement. The proposed method trains a multi-view learning classification model using features extracted from the smartphone sensing data of volunteers and their self-reported moods. The trained classifier is then used to detect the MI of unseen users efficiently, thereby reducing the human involvement and time cost significantly. Based on extensive experiments conducted with the dataset collected from 68 volunteers, we demonstrate that the proposed multi-view learning model outperforms the baseline classifiers.

Despite the increasing popularity of mobile applications and the widespread adoption of encryption techniques, mobile devices are still susceptible to security and privacy risks. In this paper, we propose ActiveTracker, a new type of sniffing attack that can reveal the fine-grained trajectory of user’s mobile app usage from a sniffed encrypted Internet traffic stream. It firstly adopts a sliding window based approach to divide the encrypted traffic stream into a sequence of segments corresponding to different app activities. Then each traffic segment is represented by a normalized temporal-spacial traffic matrix and a traffic spectrum vector. Based on the normalized representation, a deep neural network (DNN) classification algorithm is developed to recognize the crucial activities conducted with different apps by the user. We show by extensive experiments on real-world app usage traffic collected from volunteers that the proposed approach achieves up to 78.5% accuracy in recognizing app trajectory over encrypted traffic streams.

In conventional 802.11, MAC protocol data units (MPDUs) that a receiver fails to decode will be simply discarded even when only a very few bits are corrupted. This makes conventional 802.11 hardly work when the channel fading or the interference is very severe. In this paper, we propose Rateless802.11, a novel scheme that is fully compatible with common commodity 802.11 devices, which can be used as a complement of 802.11 used in terrible channels. By concatenating LT codes with 802.11 convolutional codes, Rateless802.11 can introduce redundancy properly without the need of accurate channel status estimation, and exploit the uncorrupted bits of MPDUs adequately. To improve the decoding performance as well as reducing the decoding delay, we introduce an integrated decoder (IntBP) in Rateless802.11, which decodes convolutional codes and LT codes compactly and can be performed in an incremental manner. Evaluations based on numerical simulation and driven by universal software radio peripheral (USRP) captured real trace show that IntBP can dramatically improve decoding reliability compared with natural serial decoding approaches and compared with state-of-the-art solutions, throughput of 802.11 in terrible channels can be improved many times by Rateless802.11.

The Multipath TCP (MPTCP) protocol has been standardized by the IETF as an extension of conventional TCP, which enables multi-homed devices to establish multiple paths for simultaneous data transmission. Congestion control is a fundamental mechanism for the design and implementation of MPTCP. Due to the diverse QoS characteristics of heterogeneous links, existing multipath congestion control mechanisms suffer from a number of performance problems such as bufferbloat, suboptimal bandwidth usage, etc. In this paper, we propose a learning-based multipath congestion control approach called SmartCC to deal with the diversities of multiple communication path in heterogeneous networks. SmartCC adopts an asynchronous reinforcement learning framework to learn a set of congestion rules, which allows the sender to observe the environment and take actions to adjust the subflows' congestion windows adaptively to fit different network situations. To deal with the problem of infinite states in high-dimensional space, we propose a hierarchical tile coding algorithm for state aggregation and a function estimation approach for Q-learning, which can derive the optimal policy efficiently. Due to the asynchronous design of SmartCC, the processes of model training and execution are decoupled, and the learning process will not introduce extra delay and overhead on the decision making process in MPTCP congestion control. We conduct extensive experiments for performance evaluation, which show that SmartCC improves the aggregate throughput significantly and outperforms the state-of-the-art mechanisms on a variety of performance metrics.

Popular data analytics systems including Apache Hadoop, Dryad, and Apache Spark abstract jobs as directed acyclic graphs (DAGs). Speeding up completions for DAG jobs matter in practice in order to support real-time decisions. State-of-the-art works propose clairvoyant schedulers to optimize these goals, however, they assume complete job information as a prior knowledge which includes the precise DAG structure, and fine-grained resource requirement and duration time of each task. This assumption limits their applicability. In this paper, to be more practical, we relax the complete prior knowledge assumption and rely solely on partial prior information, based on which, we design a semi-clairvoyant task scheduler Cobra operating within each job. When managing resources for a job, Cobra adaptively adjusts its resource desires in a multiplicative-increase multiplicative-decrease manner on the basis of the its current resource utilization and the presence of current waiting tasks. When assigning tasks to run on the allocated resources, Cobra strives to satisfy task locality preference by tolerating each task waiting for some time that is bounded by a parameterized threshold. Even with the partial prior job information, when a set of jobs in which each employing Cobra as its task scheduler, run on a cluster that employs the fair job scheduler, we theoretically prove the produced makespan and average job response time are O(1)-competitive in different settings. We implement our design in Spark on YARN system, and use experiments from both real deployments and simulations on Google's trace to verify the performance promotion and sensitivity of Cobra.

While modern wireless devices are capable of using multiple WiFi interfaces, the Multipath TCP (MPTCP) protocol has been employed to make full use of the capacity of many radios by enabling multiple path communication simultaneously. To provide exceptional mobility support in wireless networks, a key question is to determine the best handoff strategy to switch between access points or among WiFi/3G interfaces during roaming. In this paper, we propose SERO, a novel model-driven SEamless ROaming framework to optimize layer-2 handoff and vertical handoff for multihomed devices using MPTCP. The proposed framework adopts a measurement-based method to derive the TCP throughput model for wireless communication during handoff. Based on the throughput model, we propose a hybrid handoff strategy that uses multiple WiFi interfaces for data transmission and employs 3G augmentation to bridge the network interruption caused by handoff and to guarantee the total throughput above a predefined threshold for roaming devices. We implement the SERO framework in a real-deployed wireless mesh network testbed, and evaluate its performance by extensive experiments, which shows that SERO achieves performance gain of 26%-180% compared with several existing handoff strategies.

With computer vision-based technologies, current Augmented reality (AR) systems can effectively recognize multiple objects with different visual characteristics. However, only limited degrees of distinctions can be offered among different objects with similar natural features, and inherent information about these objects cannot be effectively extracted. In this paper, we propose TaggedAR, i.e., an RFID-based approach to assist the recognition of multiple tagged objects in AR systems, by deploying additional RFID antennas to the COTS depth camera. By sufficiently exploring the correlations between the depth of field and the received RF-signal, we propose a rotate scanning-based scheme to distinguish multiple tagged objects in the stationary situation, and propose a continuous scanning-based scheme to distinguish multiple tagged human subjects in the mobile situation. By pairing the tags with the objects according to the correlations between the depth of field and RF-signals, we can accurately identify and distinguish multiple tagged objects to realize the vision of “tell me what I see” from the AR system. We have implemented a prototype system to evaluate the actual performance with case studies in a real-world environment. The experiment results show that our solution achieves an average match ratio of 91 percent in distinguishing up to dozens of tagged objects with a high deployment density.

Wireless energy transfer has been widely studied in recent decades, with existing works mainly focused on maximizing network lifetime, optimizing charging efficiency, and optimizing charging quality. All these works use a charging model with the linear superposition, which may not be the most accurate. We apply a nonlinear superposition model, and we consider the Fast Charging Scheduling problem (FCS): Given multiple chargers and a group of sensors, how can the chargers be optimally scheduled over the time dimension so that the total charging time is minimized and each sensor has at least energy E ? We prove that FCS is NP-complete and propose a 2-approximation algorithm to solve it in one-dimensional (1D) line. In a 2D plane, we first consider a special case of FCS, where the initial phases of all chargers are the same, and propose an algorithm to solve it, which has a bound. Then we propose an algorithm to solve FCS in a general 2D plane. Unlike other algorithms, our algorithm does not need to calculate the combined energy of every possible combination of chargers in advance, which greatly reduces the complexity. Extensive simulations demonstrate that the performance of our algorithm performs almost as good as the optimal algorithm.

Recognizing in-air hand gestures will benefit a wide range of applications such as sign-language recognition, remote control with hand gestures, and “writing” in the air as a new way of text input. This article presents AirContour, which focuses on in-air writing gesture recognition with a wrist-worn device. We propose a novel contour-based gesture model that converts human gestures to contours in 3D space and then recognizes the contours as characters. Different from 2D contours, the 3D contours may have the problems such as contour distortion caused by different viewing angles, contour difference caused by different writing directions, and the contour distribution across different planes. To address the above problem, we introduce Principal Component Analysis (PCA) to detect the principal/writing plane in 3D space, and then tune the projected 2D contour in the principal plane through reversing, rotating, and normalizing operations, to make the 2D contour in right orientation and normalized size under a uniform view. After that, we propose both an online approach, AC-Vec, and an offline approach, AC-CNN, for character recognition. The experimental results show that AC-Vec achieves an accuracy of 91.6% and AC-CNN achieves an accuracy of 94.3% for gesture/character recognition, both outperforming the existing approaches.

Remote Direct Memory Access (RDMA) technique allows the messaging service that directly access the memory on remote machines, which provides low CPU overhead, low latency, and high throughput network transmission. On the other hand, however, due to the limited cache space in RDMA NIC (RNIC), it is still challenging to achieve effective and fair resource sharing across different applications. To address this problem, we present a scalable RDMA as a service to manage resource and deliver fair scheduling to applications' requests. We study the thread contention and preemptive schedule issues at end-hosts, and report the corresponding performance degradation through experiments. Then, we introduce Avatar, a model to manage memory and Queue Pairs (QPs) resource for a large number of connections, which eliminates the lock contention and provides fair data scheduling for applications with different priorities. Finally, we implement Avatar and demonstrate that Avatar can support a thousand of connections, improve the fairness and reduce the requests completion time up to 50% in comparison with the native RDMA.

There has always been a gap between Internet Service Providers (ISPs) and end users when considering the performance of network-based application. On one hand, ISPs keep raising the investment on infrastructures to speed up the data transportation. On the other hand, users are not satisfied with the perceived quality of experience (QoE). This happens mainly due to the inflexible network flow management, where only the function of rate limiting is provided for home users in the shared network environment. In this paper, we focus on the optimization of users experience by customizing bandwidth allocation for user specified preferences while maintaining high bandwidth utilization. We introduce implicit content-aware bandwidth allocation to minimize the involvement of users on complicated network setting. By leveraging the technique of software-defined networking (SDN), a prototype of content-aware traffic scheduling, Conan, is developed to verify the effectiveness of our design. Experiments show that Conan can reduce the average task completion time of interactive applications by 30-40%. During heavy traffic load, Conan can ensure stable bandwidth for each video streaming flow and greatly reduce the average stall duration.

Modern datacenter networks employ Load-balancing (LB) in the large-scale multi-tier topology to ensure high network utilization as well as low flow completion time. This paper presents the design and evaluation of Nem, a robust Erasure Coding (EC) based load balancing scheme at end-host to spread data across multiple paths. Our design is based on two key insights. First, both theory and implementation have shown that redundancy is a powerful technique to reduce latency in networked system. Second, the commercial RDMA network interface card supports EC offload which can dramatically reduce the CPU consumption. Nem is an optimal user-level LB design, which leveraging redundant fine-grained data blocks and high speed lossless RDMA network to realize effective load balancing transmission. Evaluation over many workloads shows that Nem is adaptive to the asymmetric networks, and achieves better performance compared to the state-of-art host-based load balancing mechanism.

With the pervasive availability of LCD displays and phone cameras, screen-camera communication has attracted grate attentions due to the characteristics of convenience, security, infrastructure-free, and contactless. The existing screen-camera communication systems using dynamic barcodes suffer from poor ability of color recognition. In this paper, we propose a machine learning based multi-color dynamic barcode system called MMCode to overcome such limit. We formulate the color recognition problem as a machine learning task, and propose a semi-supervised clustering algorithm to achieve finer-grained color recognition. The proposed mechanism inserts reference colors in the barcode design, and adopts a semi-supervised Gaussian Mixed Model (GMM) algorithm for frame decoding. We implement MMCode as an Android APP and test its performance under real screen-camera communication scenarios. Extensive experiments show that the proposed MMCode achieves significant enhancement on the capacity of dynamic barcodes compared to the state-of-the-arts.

Many organizations and companies have deployed not only datacenters but also large number of geo-distributed heterogeneous edges to provide fast data analytics services. Since large volume of data transmission across WAN can be costly, existing works mainly focus on pre-processing data in-place to avoid transmission. However, the heterogeneity of edges on either local computing capacity or network bandwidth limits the efficient use on scarce resource, which may result in long task completion time. To cope with dynamic demands on scarce resource, we take the heterogeneity of both computing capacity and network bandwidth of geo-distributed edges into consideration when assigning data analytical tasks and their associated data between the central datacenter and edges such that the overall latency can be reduced. We formulate the geo-distributed data-task joint scheduling problem (GJS), show its NP-hardness, and propose a near-optimal randomized scheduling algorithm (ran-GJS). ran-GJS can be proved concentrated around its optimum value with high probability, i.e., 1--O(e--t2) where t is the concentration bound by using Martingale Analysis. The experimental results obtained form both extensive simulations and Yarn-based prototype show that ran-GJS significantly speeds up the geo-distributed analytics with a gain on average completion time of at least 28% over state-of-the-art baseline algorithms.

Multi-label learning is widely applied in many real-world applications, such as image and gene annotation. While most of the existing multi-label learning models focus on the single-task learning problem, there are always some tasks that share some commonalities, which can help each other to improve the learning performances if the knowledge in the similar tasks can be smartly shared. In this paper, we propose a LABel-sensitive TAsk Grouping framework, named LABTAG, based on Bayesian nonparametric approach for multi-task multi-label classification. The proposed framework explores the label correlations to capture feature-label patterns, and clusters similar tasks into groups with shared knowledge, which are learned jointly to produce a strengthened multi-task multi-label model. We evaluate the model performance on three public multi-task multi-label data sets, and the results show that LABTAG outperforms the compared baselines with a significant margin.

Nowadays, the demand for novel approaches of 2D human-computer interaction has enabled the emergence of a number of intelligent devices, such as Microsoft Surface Dial. Surface Dial realizes 2D interactions with the computer via simple clicks and rotations. In this paper, we propose RF-Dial, a battery-free solution for 2D human-computer interaction based on RFID tag arrays. We attach an array of RFID tags on the surface of an object, and continuously track the translation and rotation of the tagged object with an orthogonally deployed RFID antenna pair. In this way, we are able to transform an ordinary object like a board eraser into an intelligent HCI device. According to the RF-signals from the tag array, we build a geometric model to depict the relationship between the phase variations of the tag array and the rigid transformation of the tagged object, including the translation and rotation. By referring to the fixed topology of the tag array, we are able to accurately extract the translation and rotation of the tagged object during the moving process. Moreover, considering the variation of phase contours of the RF-signals at different positions, we divide the overall scanning area into the linear region and non-linear region in regard to the relationship between the phase variation and the tag movement, and propose tracking solutions for the two regions, respectively. We implemented a prototype system and evaluated the performance of RF-Dial in the real environment. The experiments show that RF-Dial achieved an average accuracy of 0. 6cm in the translation tracking, and an average accuracy of 1.9°in the rotation tracking.

Recently, gesture recognition has gained considerable attention in emerging applications (e.g., AR/VR systems) to provide a better user experience for human-computer interaction. Existing solutions usually recognize the gestures based on wearable sensors or specialized signals (e.g., WiFi, acoustic and visible light), but they are either incurring high energy consumption or susceptible to the ambient environment, which prevents them from efficiently sensing the fine-grained finger movements. In this paper, we present RF-finger, a device-free system based on Commercial-Off-The-Shelf (COTS) RFID, which leverages a tag array on a letter-size paper to sense the fine-grained finger movements performed in front of the paper. Particularly, we focus on two kinds of sensing modes: finger tracking recovers the moving trace of finger writings; multi-touch gesture recognition identifies the multi-touch gestures involving multiple fingers. Specifically, we build a theoretical model to extract the fine-grained reflection feature from the raw RF -signal, which describes the finger influence on the tag array in cm- level resolution. For the finger tracking, we leverage K-Nearest Neighbors (KNN) to pinpoint the finger position relying on the fine-grained reflection features, and obtain a smoothed trace via Kalman filter. Additionally, we construct the reflection image of each multi-touch gesture from the reflection features by regarding the multiple fingers as a whole. Finally, we use a Convolutional Neural Network (CNN) to identify the multi-touch gestures based on the images. Extensive experiments validate that RF -finger can achieve as high as 88% and 92% accuracy for finger tracking and multi-touch gesture recognition, respectively.

Typical data analytics systems abstract jobs as directed acyclic graphs (DAGs). It is crucial to maximize throughput and speedup completions for DAG jobs in practice. Existing works propose clairvoyant schedulers optimizing these goals, however, they assume complete job information as a prior knowledge which limits their applicability. Instead, we remove the complete prior knowledge assumption and rely solely on a partial prior information, which is more practical. And we design a semi-clairvoyant task scheduler Cobra working within each job. Cobra adaptively adjusts its resource desires in a multiplicative-increase multiplicative-decrease (MIMD) manner according to nearly past resource utilizations and the current waiting tasks. On the other hand, Cobra seeks to satisfy task locality preferences by allowing each task to wait for some time that is bounded by a parameterized threshold. Surprisingly, even with the partial prior job information, we theoretically prove, Cobra, when working with the widely used fair job scheduler, is O(1)-competitive with respect to both makespan and average job response time. We experimentally validate that the performance promotion of Cobra in both real system deployment and trace-driven simulations.

Electric vehicle (EV) is a promising technological tool for diminishing environmental impact caused by gasoline-consumed transportation. Due to the limited battery capacity, EVs need to be charged frequently in a static charging station and thus waste large amounts of time being out of service. Research previously conducted in this topic have proposed solutions for deployment of charging lanes that can charge in-motion EVs. However, they cannot guarantee that every EV can be operational in their respective entire route. Meanwhile, we observe that EVs have repetitive motions and may cyclically encounter with each other which no prior research having been investigated. In addition, the development on the circuit design of energy transmit antennas can render EVs to be able to bi-directionally, highly efficiently transfer energy between themselves. These two observations enable us to distribute energy among EVs in a collaborative and interactive manner. We consider the cases of both loss-less and lossy energy transfer between EVs. In both cases, we formulate the problem of minimizing the time needed (or energy transferred) to reach a given energy distribution into a series of linear programming problems. When compared with a state-of-the-art algorithm, extensive simulation results show that the proposed algorithms can reduce the balancing time and energy loss by up to 70.60% and 36.59%, respectively.

Nowadays, novel approaches of 3D human-computer interaction have enabled the capability of manipulating in the 3D space rather than 2D space. For example, Microsoft Surface Pen leverages the embedded sensors to sense the 3D manipulations, such as inclining the pen to get bolder handwriting. In this paper, we propose RF-Brush, a battery-free and light-weight solution for 3D human-computer interaction based on RFID, by simply attaching a linear RFID tag array onto the linear shaped object like a brush. RF-Brush senses the 3D orientation and 2D movement of the linear shaped object, when the human subject is drawing with this object in the 3D space. Here, the 3D orientation refers to the relative orientation of the linear shaped object to the operating plane, whereas the 2D movement refers to the moving trace in the 2D operating plane. In this way, we are able to transform an ordinary linear shaped object like a brush or pen to an intelligent HCI device. Particularly, we build two geometric models to depict the relationship between the RF-signal and the 3D orientation as well as 2D movement, respectively. Based on the geometric model, we propose the linear tag array-based HCI solution, implemented a prototype system, and evaluated the performance in real environment. The experiments show that RF-Brush achieves an average error of 5.7° and 8.6° of elevation and azimuthal angle, respectively, and an average error of 3.8cm and 4.2cm in movement tracking along X-axis and Y-axis, respectively. Moreover, RF-Brush achieves 89% in letter recognition accuracy.

Nowadays, breakthroughs in wireless power transfer make it possible to transfer energy over a long distance. Existing works mainly focused on maximizing network lifetime, optimizing charging efficiency, and optimizing charging quality. All these works use a charging model with the linear superposition, which may not be the most accurate in a real life situation. We use a concurrent charging model, which has a nonlinear superposition, and we consider the Fast Charging Scheduling problem (FCS): given multiple chargers and a group of sensor nodes, how can the chargers be optimally scheduled over the time dimension so that the total charging time is minimized and each sensor node has at least energy E? We prove that FCS is NP-complete and propose algorithms to solve the problem in 1D line and 2D plane respectively. Unlike other algorithms, our algorithm does not need to calculate the combined energy of every possible combination of chargers in advance, which greatly reduces the complexity. We obtain a bound in 2D cases when chargers and sensors are uniformly distributed. Extensive simulations demonstrate that the performance of our algorithm is almost as good as the optimal algorithm when the distribution of chargers is not very dense.

Infusion monitoring is in great demand for the hospital. In this demo, we propose RF-iCare, an RFID-based approach for monitoring the infusion status, including the liquid level and the drop speed. With a tag array attached on the infusion bottle, we design an RSSI-based signal match model to estimate the liquid level. With a tag attached on the Murphy's dropper, we leverage the phase variation of the tag to estimate the drop speed. We implement RF-iCare with a COTS RFID system and evaluate it in the real-world hospitals. Our experiments demonstrate that RF-iCare can accurately monitor the completion of the infusion over 91% tests, and estimate the liquid level with the mean accuracy of 0.8 cm as well as the drop speed with the error rate less than 3%.

Recent breakthroughs in wireless power transfer make it possible to charge sensors over a long distance. Existing works have mainly focused on maximizing network lifetime, optimizing charging efficiency, and optimizing charging quality. All these works use a linear superposition charging model, which may not be accurate in real life situations. We use the actual charging model, which has a nonlinear super-position and we consider the charging scheduling problem (CSP): given multiple chargers and a group of sensor nodes, how can the chargers be optimally scheduled so that the total charging time is minimized and each sensor node has at least energy E? We prove that CSP is NP-hard, and propose a weight-greedy algorithm to solve the problem. Unlike the algorithm proposed before, ours does not need to calculate all charger groups utility in advance, which reduces the complexity. Extensive simulations demonstrate that the performance of our algorithm with sparse network is almost as good as the optimal algorithm. In general cases, our algorithm outperforms the random algorithm. Furthermore, our algorithm obtains the best solution in two special cases.

Current communication networks are facing more and more threats from large-scale regional damages, such as natural disasters (e.g., earthquake or tornado) and physical attacks (e.g., electromagnetic pulse attack or dragging anchors). Recently, several region failure models have been proposed to evaluate the impact of such geographically correlated failures on communication networks. These works mainly adopt a kind of “deterministic” models, where network components within the affected area would fail simultaneously. Such failure models simplify the analysis but may fail to reflect some important behaviors of attacks and thus cause significant over- or under-estimation of region failures. To emulate the impact of realistic catastrophe events such as earthquake and tornado, this paper introduces two probabilistic failure models: 1) a concentric circle model and 2) a line segment model. In the probabilistic models, both the location and effect of the damage are treated as random events. The failure may randomly incur on the entire network plane, and the failure probability of a device depends on many factors, e.g., link length and distance to the damage center. We develop an efficient grid partition-based scheme to estimate the network vulnerability. Based on the grid partition scheme, we further develop a sampling scheme to significantly reduce the computation cost. The probability model helps us more deeply understand the network behaviors under region failure and facilitates the design and maintenance of future highly survivable mission critical networks.

Wireless power transfer is a promising technology used to extend the lifetime of, and thus enhance the usability of, energy-hungry battery-powered devices. It enables energy to be wirelessly transmitted from power chargers to energy-receiving devices. Existing studies have mainly focused on maximizing network lifetime, optimizing charging efficiency, minimizing charging delay, etc. In this paper, we consider wireless charging service provision in a two-dimensional target area and focus on optimizing charging quality, where the power of each charger is adjustable. We first consider the charger Placement and Power allocation Problem with Stationary rechargeable devices (SP3): Given a set of stationary devices and a set of candidate locations for placing chargers, find a charger placement and a corresponding power allocation to maximize the charging quality, subject to a power budget. We prove that SP3is NP-complete, and propose an approximation algorithm. We also show how to deal with mobile devices (MP3), cost-constrained power reconfiguration (CRP), and optimization with more candidate locations. Extensive simulation results show that, the proposed algorithms perform very closely to the optimum (the gap is no more than 4.5, 4.4, and 5.0 percent of OPT in SP3, MP3, and CRP, respectively), and outperforms the baseline algorithms.

Because of the smaller size of mobile devices, text entry with on-screen keyboards becomes inefficient. Therefore, we present CamK, a camera-based text-entry method, which can use a panel (e.g., a piece of paper) with a keyboard layout to input text into small devices. With the built-in camera of the mobile device, CamK captures images during the typing process and utilizes image processing techniques to recognize the typing behavior, i.e., extract the keys, track the user's fingertips, detect, and locate keystrokes. To achieve high accuracy of keystroke localization and low false positive rate of keystroke detection, CamK introduces the initial training and online calibration. To reduce the time latency, CamK optimizes computation-intensive modules by changing image sizes, focusing on target areas, introducing multiple threads, removing the operations of writing or reading images. Finally, we implement CamK on mobile devices running Android. Our experimental results show that CamK can achieve above 95 percent accuracy in keystroke localization, with only a 4.8 percent false positive rate. When compared with on-screen keyboards, CamK can achieve a 1.25X typing speedup for regular text input and 2.5X for random character input. In addition, we introduce word prediction to further improve the input speed for regular text by 13.4 percent.

The human-computer interactions have moved from the conventional approaches of entering inputs into the keyboards/touchpads to the brand-new approaches of performing interactions in the air. In this paper, we propose RF-glove, a system that recognizes concurrent multiple finger micromovement using RF signals, so as to realize the vision of “multi-touch in the air.” It uses a commercial-off-the-shelf (COTS) RFID reader with three antennas and five COTS tags attached to the five fingers of a glove, one tag per finger. During the process of a user performing finger micromovements, we let the RFID reader continuously interrogate these tags and obtain the backscattered RF signals from each tag. For each antenna-tag pair, the reader obtains a sequence of RF phase values called a phase profile from the tag's responses over time. To tradeoff between accuracy and robustness in terms of matching resolution, we propose a two phase approach, including coarse-grained filtering and fine-grained matching. To tackle the variation of template phase profiles at different positions, we propose a phase-model-based solution to reconstruct the template phase profiles based on the exact locations. Experiment results show that we achieve an average accuracy of 92.1% under various moving speeds, orientation deviations, and so on.

Nowadays cloud computing provides an effective way of implementing infrastructure as a service (IaaS). However virtualized data centers still face many challenges, such as low resource utilization of physical machines (PMs) and imbalanced server loads. Virtual machine (VM) consolidation based on live migration allows administrator to dynamically redeploy VMs into PMs for better resource utilization. Common VM consolidation methods usually focus on one challenge, and pay little attention to others or just ignore them, while effective VM redeployment should make tradeoffs between these challenges, and more importantly, should not let other challenges become worse. On the other hand, since VM live migration leads to performance degradation of applications, consolidation work should control migration cost. In this paper, we provide a manner to comprehensively consider power consumption, load balancing, communication delay and migration cost during VM redeployment. And we formalize VM consolidation as a multiobjective optimization problem, then solve this problem with an improved genetic algorithm. Simulation experiments based on real world workload trace show that compared with single objective optimization approaches our method effectively make tradeoffs between optimized objectives and has better overall performance, which is more practical in real data centers.

The lines between IaaS, PaaS, and SaaS are becoming blurred as datacenter providers seek to create cloud platforms that can widen their appeal to developers. With this kind of hybrid datacenter, resource requests from tenants are increasingly transforming into hybrid requests that may simultaneously demand IaaS, PaaS, and SaaS resources. This paper tackles the challenge of modeling and deploying hybrid tenant requests in datacenter networks, for which we coin ``networklet" to represent a set of VMs that collaboratively provide some PaaS or SaaS service. Through extracting networklets from tenant requests and thus sharing them between multiple tenants, we can achieve a win-win situation for datacenter providers and tenants. Extensive evaluations show that, the proposed model and deployment algorithm indeed improve DCN resource utilization while maintaining performance guarantee.

Opportunistic routing (OR) is a promising technology to enhance the throughput of wireless networks, which can be implemented in a distributed manner using random linear network coding (RLNC). To reduce the computational cost incurred by RLNC, most previous approaches partition the input packets into disjoint small chunks, apply RLNC within each chunk, and guarantee the decoding reliability by a feedback mechanism. However, a feedback mechanism can incur much transmission overhead, reducing the network performance significantly. Recently, chunked network codes (CC) are proposed to eliminate the requirement of feedback, where a linear block code is applied on the input packets before partitioning the packets into chunks. While several classes of CC can achieve a close-to-optimal encoding/decoding performance, the whole transmission performance depends on how the chunks are transmitted in the absence of feedback, which is little investigated in OR-based wireless networks. In this paper, we propose a simple chunk transmission scheme for CC in a common OR-based wireless network, which does not require any node coordination during the transmission and keep the buffer of the relay node stable. We further optimize the performance of the transmission scheme via linear programming, and demonstrate that our scheme performs near-optimally via extensive numerical evaluations.

While the mobile users enjoy the anytime anywhere Internet access by connecting their mobile devices through Wi-Fi services, the increasing deployment of access points (APs) have raised a number of privacy concerns. This paper explores the potential of smartphone privacy leakage caused by surrounding APs. In particular, we study to what extent the users' personal information such as social relationships and demographics could be revealed leveraging simple signal information from APs without examining the Wi-Fi traffic. Our approach utilizes users' activities at daily visited places derived from the surrounding APs to infer users' social interactions and individual behaviors. Furthermore, we develop two new mechanisms: the Closeness-based Social Relationships Inference algorithm captures how closely people interact with each other by evaluating their physical closeness and derives fine-grained social relationships, whereas the Behavior-based Demographics Inference method differentiates various individual behaviors via the extracted activity features (e.g., activeness and time slots) at each daily place to reveal users' demographics. Extensive experiments conducted with 21 participants' real daily life including 257 different places in three cities over a 6-month period demonstrate that the simple signal information from surrounding APs have a high potential to reveal people's social relationships and infer demographics with an over 90% accuracy when using our approach.

In today's datacenters, resource requests from tenants are increasingly transforming into hybrid requests that may simultaneously demand IaaS, Paas, and SaaS resources. This paper tackles the challenge of modeling and deploying hybrid tenant requests in datacenters, for which we coin "networklet" to represent a set of VMs that collaboratively provide a PaaS or SaaS service. Through extracting networklets from tenant requests and thus sharing them between tenants, we can achieve a win-win situation for datacenter providers and tenants.

Many corporations rely on Internet service provider (ISP) network to provide reliable communication services. However, the current communication networks are vulnerable to disruptive events, such as natural disaster or power outage. Such disastrous events may destroy multiple network facilities in a specific region and result in a long term recovery of ISP networks. The disconnected communication will lead to enormous economic loss even if corporation's infrastructure is not directly destroyed during the disaster. Therefore, corporations need a self-rescue mechanism to actively respond to the emergency instead of simply relying on the ISP. This paper proposes Ambula, an easy-to-deploy platform to realize fast congestion-aware recovery for corporation's communication lifeline. Our platform leverages current widely-deployed public cloud services to build a scalable peer-to-peer overlay routing system. By so doing, the corporation is capable of controlling the packets forwarding path to bypass the affected region and congested routes. To this end, Ambula first carefully selects a small set of virtual machines (VMs) from geographically distributed public clouds, and then apply the self-developed congestion-aware routing protocol to achieve automatic and fast routing recovery. Simulations on both random generated and real network topologies show that the high recovery ratio of 80% can be achieved. The congestion avoidance algorithm can significantly reduce the impact of congestion. Our prototype on Emulab shows it can recover within hundreds of milliseconds. To the best of our knowledge, no effective disaster recovery mechanism currently exists for corporations during emergency. Ambula will facilitate the business continuity management of corporations in present of hazard events.

Hardware middleboxes are widely used in current cloud datacenter to provide network functions such as firewalls, intrusion detection system, load balancers, etc. Unfortunately, they are expensive and unable to offer customized functions for individual tenant. To overcome this issue, there is an increasing interest in deploying software middleboxes to enable flexible security, network access functionality. This paper addresses the software middleboxes placement problem with minimum bandwidth guarantee. We first specify the model of tenants' requirement that specifies the need for virtual machines of application and middleboxes, as well as communication traffic. A virtual middlebox placement algorithm called MISSILE is then proposed to offer predictable network performance for each accepted tenant, and minimize datacenter bandwidth utilization. Extensive simulation results based on current large-scale datacenter networks verify that MISSILE is effective and provides network performance guarantee for tenants.

In this paper, we investigate the joint job and data assignment problem in cloud data centers with non-volatile memory (NVM) for makespan minimization. Through extensive analysis, we find that there is an indicator variable that characterizes the hardness of the problem. Depending on the value of the indicator variable, we classify our problem into three cases: inf-case, opt-case, and nph-case. We first show that there is no feasible assignment under the inf-case. For the opt-case, we present an optimal algorithm. We show that a mixed data assignment with diversified popularity achieves high memory utilization. For the nph-case, we first prove the problem's NP-hardness and then propose a heuristic algorithm and a 2-approximation algorithm to tackle it. We conduct extensive simulations, and we find that the performance of the heuristic algorithm is better than the 2-approximation algorithm and that it is nearly the same as the theoretical optimal solution.

The various flows in production datacenters usually can be classified into two types: bandwidth-hungry and delay-sensitive. To improve their performance, datacenter networks require effective load balancing and flow control protocols, respectively. However, as the two techniques are typically employed separately in current datacenters, they are unable to optimize the network in a coordinated way. In this work, we argue that the adaptive routing, in load balancing sense, and the flow control, in congestion control sense, could be tightly coupled at the transport layer to handle the complex datacenter traffic. We design OmniFlow, a novel transfer protocol which aims to achieve a proper balance between throughput and latency in a datacenter. Firstly, it can simultaneously and precisely measure the queueing latencies on multiple paths between two hosts, which enables it to have more visibility of the path congestion and have better control of the transmission states. Secondly, OmniFlow adaptively integrates the load balancing and flow control modules and shares the same congestion metrics (i.e. queueing latencies) between them. Based on different network conditions, it either dynamically reroutes flows to utilize the bisection bandwidth or proactively adjusts flow rates to bound queueing occupancies. The results of extensive experiments show that OmniFlow can provide both low average and tail latency for small flows without sacrificing the throughput of elephant flows.

In this paper, we propose 3DLoc, which performs 3-dimensional localization on the tagged objects by using the RFID tag arrays. 3DLoc deploys three arrays of RFID tags on three mutually orthogonal surfaces of each object. When performing 3D localization, 3DLoc continuously moves the RFID antenna and scans the tagged objects in a 2-dimensional space right in front of the tagged objects. It then estimates the object's 3D position according to the phases from the tag arrays. By referring to the fixed layout of the tag array, we use Angle of Arrival-based schemes to accurately estimate the tagged objects' orientation and 3D coordinates in the 3D space. To suppress the localization errors caused by the multipath effect, we use the linear relationship of the AoA parameters to remove the unexpected outliers from the estimated results. We have implemented a prototype system and evaluated the actual performance in the real complex environment. The experimental results show that 3DLoc achieves the mean accuracy of 10cm in free space and 15.3cm in the multipath environment for the tagged object.

Nowadays, 3D reconstruction has been introduced in monitoring the package placement in logistic industry-related applications. Existing 3D econstruction methods are mainly based on computer vision or sensor-based approaches, which are limited by the line-of-sight or battery life constraint. In this paper, we propose RF-3DScan to perform 3D reconstruction on tagged packages via passive RFID, by attaching multiple reference tags onto the surface of the packages. The basic idea is that by moving the antenna along straight lines within a constrained 2-dimensional space, the antenna obtains the RF-signals of the reference tags attached on the packages. By extracting the phase differences to build the angle profile for each tag, RF-3DScan can compare the angle profiles of the different reference tags and derive their relative positions, then further determine the package orientation and stacking for 3D reconstruction. We implement RF- 3DScan and evaluate its performance in real settings. The experiment results show that the average identification accuracy of the bottom face is about 92.5%, and the average estimation error of the rotation angle is about 4.08o.

Nowadays, Unmanned Aerial Vehicles(UAVs) have been widely applied in our life. However, the existing approach of interacting with UAVs, i.e., using a remote controller with control sticks, is not a natural and intuitive way. In this paper, we present a novel approach for users to interact with personal UAVs using wearable devices. The basic idea of our approach is to manipulate UAVs based on human activity sensing, including motion recognition and pedestrian dead- reckoning. We have implemented the proposed approach on a DJI drone, and evaluated its performance in the real- world environment. Realistic experiment results show that our solution can replace the remote controller to manipulate the UAV.

Since human bodies are good reflectors of wireless signals, human activities can be recognized by monitoring changes in WiFi signals. However, existing WiFi-based human activity recognition systems do not build models that can quantify the correlation between WiFi signal dynamics and human activities. In this paper, we propose a Channel State Information (CSI)-based human Activity Recognition and Monitoring system (CARM). CARM is based on two theoretical models. First, we propose a CSI-speed model that quantifies the relation between CSI dynamics and human movement speeds. Second, we propose a CSI-activity model that quantifies the relation between human movement speeds and human activities. Based on these two models, we implemented the CARM on commercial WiFi devices. Our experimental results show that the CARM achieves recognition accuracy of 96% and is robust to environmental changes.

Auction is a promising approach for dynamic spectrum access in cognitive radio networks. Existing auction mechanisms are mainly strategy-proof to stimulate bidders to reveal their valuations of spectrum truthfully. However, they can suffer significantly from a new cheating pattern, named false-name bids, where a bidder can manipulate the auction by submitting bids under multiple fictitious names. We show such false-name bid cheating is easy to make but difficult to detect in dynamic spectrum auctions. To address this issue, we propose ALETHEIA, a novel flexible, false-name-proof auction framework for large-scale dynamic spectrum access. ALETHEIA not only guarantees strategy-proofness but also resists false-name bids. Moreover, ALETHEIA enables spectrum reuse across a large number of bidders, to improve spectrum utilization. Following that, we extend ALETHEIA to its general version that supports more practical and flexible auction, where bidders accept the spectrum allocation under their partial satisfactions. Theoretical analysis and simulation results show that ALETHEIA achieves both high spectrum redistribution efficiency and auction efficiency.

Wireless power transfer provides a promising way to extend the battery lifetime of our energy-hungry rechargeable devices. Previous studies have envisioned using mobile vehicles/robots/drones equipped with high capacity batteries as mobile chargers to replenish those devices, and they mainly focus on maximizing network lifetime, optimizing efficiency of charging scheduling, minimizing total charging delay, etc. However, existing methods may be insufficient and inflexible when the energy consumption of rechargeable devices fluctuates overtime, or when rechargeable devices are sparse. In this paper, we consider how to efficiently provide flexible wireless charging using pre-planned charging itineraries. We present the Itinerary Selection and Charging Association (ISCA) problem: given a set of rechargeable devices and a set of candidate charging itineraries, how can we select itineraries and determine a corresponding charging association to minimize the amount of energy which is due to mobile chargers' movement and wireless charging loss, so that every device gets its required energy. We prove that ISCA is NP-complete by reducing the set cover problem to it. We start solving this problem by first looking at the case in which an itinerary can only be used once, and we propose an algorithm with approximation ratio of O (lnM) and a practical heuristic algorithm, where M is the number of devices. For the general case in which an itinerary may be used multiple times, we propose an approximation algorithm of factor 10 using the Primal-Dual schema. Evaluations results from real field experiments and extensive simulations show that the proposed algorithms have near-optimal performance and PDA reduces the amount of wasted energy by up to 65 percent compared with a set cover-based algorithm.

Due to the portability of smart phones, more and more people tend to take photos with smart phones. However, energy-saving continues to be a thorny problem, since photographing is a rather power hungry function. To extend the battery life of phones while taking photos, we propose a context-aware energy-saving scheme called “SenSave.” SenSave senses the user’s activities during photographing and adopts suitable energy-saving strategies accordingly. SenSave works based on the observation that a lot of energy during photographing is wasted in preparations before shooting. By leveraging the low power-consuming embedded sensors, such as accelerometer and gyroscope, we can recognize the user’s activities and reduce unnecessary energy consumption. Besides, by maintaining an activity state machine, SenSave can determine the user’s activity progressively and improve the recognition accuracy. Experiment results show that SenSave can recognize the user’s activities with an average accuracy of 95.5% and reduce the energy consumption during photographing by 30.0%, when compared to the approach by frequently turning ON/OFF the camera or screen. Additionally, we enhance “SenSave” by introducing an extended Markov chain to predict the next activity state and adopt the energy-saving strategy in advance. Then, we can reduce the energy consumption during photographing by 36.1%.

Existing data center transport protocols are usually based on the Processor Sharing (PS) policy and/or the Shortest Remaining Processing Time (SRPT) policy. PS divides link bandwidth equally between competing flows, thus it fails to achieve optimal average flow completion time (FCT). SRPT prioritizes flows that have the shortest remaining processing time and provides near-optimal average FCT, but it may cause long flows to suffer unfair delays, or even starve them. In fact, these two types of policies represent two directions in the design space: PS prefers fairness (in terms of starvation freedom) while SRPT favors efficiency (in terms of average FCT). In this paper, we propose a novel metric, expansion ratio, which enables us to strike a balance between SRPT and PS. We design MERP that achieves efficient flow scheduling without starvation. MERP takes care of both average and tail FCTs by minimizing the expansion ratio of competing flows in a lexicographically manner. MERP controls the sending rate of competing flows via synchronized virtual deadlines and routes flows in a downstream-aware manner that reacts quickly to link failures. We evaluate MERP using extensive NS2-based simulations. Results show that, under various traffic loads, MERP reduces the tail FCT significantly with a negligible increase of average FCT compared with pFabric, and MERP reduces the average FCT notably compared with ECMP and CONGA when link failures occur.

The receiving signal strength (RSS) is crucial for the Internet of Things (IoT), as it is the key foundation for communication resource allocation, localization, interference management, sensing, and so on. Aside from its significance, the measurement process could be tedious, time consuming, inaccurate, and involving human operations. The state-of-the-art works usually applied the fashion of “measure a few, predict many,” which use measurement calibrated models to generate the RSS for the whole networks. However, this kind of methods still cannot provide accurate results in a short duration with low measurement cost. In addition, they also require careful scheduling of the measurement which is vulnerable to measurement conflict. In this paper, we propose a compressive sensing- (CS-) based RSS measurement solution, which is conflict-tolerant, time-efficient, and accuracy-guaranteed without any model-calibrate operation. The CS-based solution takes advantage of compressive sensing theory to enable simultaneous measurement in the same channel, which reduces the time cost to the level of O(log⁡N) (where N is the network size) and works well for sparse networks. Extensive experiments based on real data trace are conducted to show the efficiency of the proposed solutions.

Nowadays, people usually depend on augmented reality (AR) systems to obtain an augmented view in a real-world environment. With the help of advanced AR technology (e.g. object recognition), users can effectively distinguish multiple objects of different types. However, these techniques can only offer limited degrees of distinctions among different objects and cannot provide more inherent information about these objects. In this paper, we leverage RFID technology to further label different objects with RFID tags. We deploy additional RFID antennas to the COTS depth camera and propose a continuous scanning-based scheme to scan the objects, i.e., the system continuously rotates and samples the depth of field and RF-signals from these tagged objects. In this way, by pairing the tags with the objects according to the correlations between the depth of field and RF-signals, we can accurately identify and distinguish multiple tagged objects to realize the vision of "tell me what I see" from the augmented reality system. For example, in front of multiple unknown people wearing RFID tagged badges in public events, our system can identify these people and further show their inherent information from the RFID tags, such as their names, jobs, titles, etc. We have implemented a prototype system to evaluate the actual performance. The experiment results show that our solution achieves an average match ratio of 91% in distinguishing up to dozens of tagged objects with a high deployment density.

In this paper, we leverage RFID technology to label different objects with RFID tags, so as to realize the vision of "show me what I see from the augmented reality system". We deploy additional RFID antennas to the COTS depth camera and propose a continuous scanning-based scheme to scan the objects, i.e., the system continuously rotates and samples the depth of field and RF-signals from these tagged objects. In this way, we can accurately identify and distinguish multiple tagged objects, by pairing the tags with the objects according to the correlations between the depth of field and RF-signals. Our solution achieves an average match ratio of 91% in distinguishing up to dozens of tagged objects with a high deployment density.

In this paper, we propose OmniFlow, a novel transport protocol which combines load balancing and flow control at the transport layer to optimize datacenter transfers. OmniFlow outweighs previous solutions in two aspects. Firstly, it can simultaneously and precisely measure the queueing latencies on multiple paths between two hosts. Secondly, OmniFlow adaptively integrates the load balancing and flow control modules and shares the same congestion metrics (i.e. queueing latencies) between them. Based on different network conditions, it either dynamically reroutes flows to utilize the bisection bandwidth or proactively adjusts flow rates to bound queueing occupancies. Our results show that OmniFlow can provide both low latency for small flows without sacrificing the throughput of elephant flows.

In a number of RFID-based applications such as logistics monitoring, the RFID systems are deployed to monitor a large number of RFID tags. They are usually required to track the movement of all tags in a real-time approach, since the tagged-goods are moved in and out in a rather frequent approach. However, a typical cycle of tag inventory in COTS RFID system usually takes tens of seconds to interrogate hundreds of RFID tags. This hinders the system to track the movement of all tags in time. One critical issue in such type of tag monitoring is to efficiently distinguish the motion status of all tags, i.e., stationary or moving. According to the motion status of different tags, the state-of-art localization schemes can further track those moving tags, instead of tracking all tags. In this paper, we propose a real-time approach to detect the moving tags in the monitoring area, which is a fundamental premise to support tracking the movement of all tags. We achieve the time efficiency by decoding collisions from the physical layer. Instead of using the EPC ID, which cannot be decoded in collision slots, we are able to extract two kinds of physical-layer features of RFID tags, i.e., the phase profile and the backscatter link frequency, to distinguish among different tags in different positions. By resolving the two physical-layer features from the tag collisions, we are able to derive the motion status of multiple tags simultaneously, and greatly improve the time-efficiency. Experiment result shows that our solution can accurately detect the moving tags while reducing 80% of inventory time compared with the state-of-art solutions.

Due to the smaller size of mobile devices, on-screen keyboards become inefficient for text entry. In this paper, we present CamK, a camera-based text-entry method, which uses an arbitrary panel (e.g., a piece of paper) with a keyboard layout to input text into small devices. CamK captures the images during the typing process and uses the image processing technique to recognize the typing behavior. The principle of CamK is to extract the keys, track the user's fingertips, detect and localize the keystroke. To achieve high accuracy of keystroke localization and low false positive rate of keystroke detection, CamK introduces the initial training and online calibration. Additionally, CamK optimizes computation-intensive modules to reduce the time latency. We implement CamK on a mobile device running Android. Our experiment results show that CamK can achieve above 95% accuracy of keystroke localization, with only 4.8% false positive keystrokes. When compared to on-screen keyboards, CamK can achieve 1.25X typing speedup for regular text input and 2.5X for random character input.

Optical switching has been considered as a natural choice to keep pace with growing fiber link capacity. One key research issue of all-optical switching is the design of optical queues by using optical crossbar switches and fiber delay lines (SDLs). In this paper, we focus on the construction of an optical priority queue with a single (M+2)×(M+2) crossbar switch and M fiber delay lines, and evaluate it in terms of the buffer size of the priority queue. Currently, the best known upper bound of the buffer size is O(2M), while existing methods can only construct a priority queue with buffer O(M3). In this paper, we make a great step towards closing the above huge gap. We propose a very efficient construction of priority queues with buffer 2Θ(√M). We use 4-to-1 multiplexers with different buffer sizes, which can be constructed efficiently with SDL, as intermediate building blocks to simplify the design. The key idea in our construction is to route each packet entering the switch to some group of four 4-to-1 multiplexers according to its current priority, which is shown to be collision-free.

Currently, conventional indoor localization schemes mainly leverage WiFi-based or Bluetooth-based schemes to locate the users in the indoor environment. These schemes require to deploy the infrastructures such as the WiFi APs and Bluetooth beacons in advance to assist indoor localization. This property hinders the indoor localization schemes in that they are not scalable to any other situations without these infrastructures. In this paper, we propose FootStep-Tracker, an anchor-free indoor localization scheme purely based on sensing the user's footsteps. By embedding the tiny SensorTag into the user's shoes, FootStep-Tracker is able to accurately perceive the user's moving trace, including the moving direction and distance, by leveraging the accelerometers and gyroscopes. Furthermore, by detecting the user's activities such as ascending/descending the stairs and taking an elevator, FootStep-Tracker can effectively correlate with the specified positions such as stairs and elevators, and further determine the exacted moving traces in the indoor map by leveraging the space constraints in the map. Realistic experiment results show that, FootStep-Tracker is able to achieve an average localization accuracy of 1m for indoor localization, without any infrastructures having been deployed in advance.

There is a growing number of incidents related to using cell phones while walking on the street. To address this issue, this paper proposes a new system based on tactile paving detection on the sidewalk to alert distracted mobile users to avoid traffic hazard. Our system (namely Inspector) is deployed as an application on an off-the-shelf normal mobile phone equipped with back camera. Inspector plays as a third eye to alert users when they step out of the safe zones where no tactile paving is detected. In order to obtain reliable yet effective decision results, we exploit a lightweight image processing method, simple classifiers along with a smart sampling strategy. The main idea is that the application capture more images of the surrounding environments when we doubt that the result from one image is not sufficient. The sampling interval is adjusted dynamically so that we can save the energy and thus extend the working time of the system. Real-scenario tests show that Inspector can detect whether a mobile user is walking along a blind sidewalk with an accuracy of 92.72%, 98.78%, and 99.44% when the detection algorithm sample 2 times, 3 times, and 4 times continuous detection respectively. The reaction time, which is measured by the difference between the alert time and the time when a user steps out of a safety zone, is 0.52 seconds early with a sampling interval of 2 seconds.

In the recent years, error estimating code (EEC) was proposed to estimate the bit-error-rate (BER) of a packet efficiently with very low data redundancy, which has been shown to be beneficial for wireless communications. In this paper, we provide theoretical analysis on the capability of EEC, which shows that correcting corrupted data bits using EEC is feasible when the BER of a packet is low. We further prove in theory that burst errors are more detectable than random errors using EEC, based on which we propose an error correction scheme for burst-noise channels. The proposed scheme includes several procedures such as segmentation, error detection, assessment, and flipping operation, which runs in polynomial time and can correct burst errors with some probability. Our work extends the philosophy of EEC from "estimation without correction" to "estimation with probabilistic correction". Numerical analysis based on a real- world WiFi communication trace shows that the proposed EEC-based algorithm achieves over 40% recovery ratio for corrupted packets in practice.

There has always been a gap of perception between Internet Service Providers (ISPs) and their customers when considering the performance of network service. On one hand, ISPs invest to increase downstream speed of access network infrastructure. On the other hand, users cannot achieve perceived quality of experience (QoE). This paper addresses this problem by introducing a system, Conan, which enables content-aware flow scheduling to improve the QoE of users. Conan exploits to satisfy users' requirements in the access network (LAN), which is the performance bottleneck actually. By leveraging the technique of software defined networking (SDN), Conan are able to specify the expected network capacity for different applications. Automatic application identification is deployed at home gateway to improve the scalability, and flexible bandwidth allocation is realized at LAN for specified applications. Using video streaming service optimization as an example, we demonstrate that our system can automatically allocate bandwidth for video flows.

As a variation of random linear network coding, segmented network coding (SNC) has attracted great interest in data dissemination over lossy networks due to its low computational cost. In order to guarantee the success of decoding, SNC can adopt a feedbackless forward error correction (FEC) approach by applying a linear block code to the input packets before segmentation at the source node. In particular, if the empirical rank distribution of transfer matrices of segments is known in advance, several classes of coded SNC can achieve close-to-optimal decoding performance. However, the empirical rank distribution in the absence of feedback has been little investigated yet, making the whole performance of the FEC approach unknown. To close this gap, in this paper, we present the first comprehensive study on the transmission scheduling issue for the FEC approach, aiming at optimizing the rank distribution of transfer matrices with little control overhead. We propose an efficient adaptive scheduling framework for coded SNC in lossy unicast networks. This framework is one-sided (i.e., each network node forwards the segments adaptively only according to its own state) and scalable (i.e., its buffer cost will not keep on growing when the number of input packets goes to infinity). The performance of the framework is further optimized based on a linear programming approach. Extensive numerical results show that our framework performs near-optimally with respect to the empirical rank distribution.

With the rapid proliferation of RFID technologies, RFID has been introduced into applications such as inventory and sampling inspection. Conventionally, in RFID systems, the reader usually identifies all the RFID tags in the interrogation region with the maximum power. However, some applications may only need to identify the tags in a specified area, which is usually smaller than the reader's default interrogation region. An example could be identifying the tags in a box, while ignoring the tags out of the box. In this paper, we respectively present two solutions to identify the tags in the specified area. The principle of the solutions can be compared to the picture-taking process of an auto-focus camera, which firstly focuses on the target automatically and then takes the picture. Similarly, our solutions first focus on the specified area and then shoot the tags. The design of the two solutions is based on the extensive empirical study on RFID tags. Realistic experiment results show that our solutions can reduce the execution time by 44 percent compared to the baseline solution, which identifies the tags with maximum power. Furthermore, we improve the proposed solutions to make them work well in more complex environments.

Mobile devices are undergoing explosive proliferation today. Although they are gaining more and more capabilities, they still fall short to execute complex applications. One possible solution to alleviate this limitation is offloading tasks to remote clouds. However, it may require persistent connectivity to the Internet and thus is not always available or affordable. An alternative solution is taking advantage of pervasive mobile devices and their pairwise encounters. In this paradigm, complex tasks from mobile devices are processed in a distributed and collaborative fashion on all mobile devices that are loosely-connected. Working towards this vision, this paper studies the following problem: given a task that originates at some node in a Disruption Tolerant Network (DTN), how are we to disseminate the task's workload during the pairwise contacts among mobile devices to achieve makespan minimization? We first imagine access to an oracle that has global and future knowledge of node mobility, and we design a provably-optimal centralized polynomial-time solution as the benchmark for comparison. With the insights obtained from the centralized solution, we then develop a distributed dissemination algorithm, D2, which maintains certain neighborhood information at individual nodes. D2 makes dissemination decisions based on the estimations of the potential computational capacities and the future workloads of mobile nodes. Extensive trace-driven simulations confirm the effectiveness of D2.

In computing clouds, burstiness of a virtual machine (VM) workload widely exists in real applications, where spikes usually occur aperiodically with low frequency and short duration. This could be effectively handled through dynamically scaling up/down in a virtualization-based computing cloud; however, to minimize energy consumption, VMs are often highly consolidated with the minimum number of physical machines (PMs) used. In this case, to meet the dynamic runtime resource demands of VMs in a PM, some VMs have to be migrated to some other PMs, which may cause potential performance degradation. In this paper, we investigate the burstiness-aware server consolidation problem from the perspective of resource reservation, i.e., reserving a certain amount of extra resources on each PM to avoid live migrations, and propose a novel server consolidation algorithm, QUEUE. We first model the resource requirement pattern of each VM as a two-state Markov chain to capture burstiness, then we design a resource reservation strategy for each PM based on the stationary distribution of a Markov chain. Finally, we present QUEUE, a complete server consolidation algorithm with a reasonable time complexity. We also show how to cope with heterogenous spikes and provide remarks on several extensions. Simulation and testbed results show that, QUEUE improves the consolidation ratio by up to 45 percent with large spike size and around 30 percent with normal spike size compared with the strategy that provisions for peak workload, and achieves a better balance between performance and energy consumption in comparison with other commonly-used consolidation algorithms.

Recently, device-to-device (D2D) communications have been leveraged to offload the traffic on cellular networks. In this paper, we focus on the content distribution problem over a hybrid cellular and local D2D network where mobile devices cooperatively download a same content. We assume that the transmissions over D2D communications are scheduled in a centralized fashion so as to achieve a high transmission efficiency. Aiming at minimizing the content download time, we formulate the minimum content download time (MinCD) problem as an integer linear programming problem, and show its hardness and inapproximability. For the case that only a single channel is available for D2D communications, we propose an asymptotically optimal algorithm. For the multi-channel case, we further propose a heuristic algorithm with low time complexity and demonstrate its efficiency via extensive simulations.

To improve users' experience, TCP short flows that are heavily used in interactive services should be completed as soon as possible. In current data centers, large flows and head-of-line blocking in switches hinder short flows from completion, which leads to long-tailed flow completion times (FCT). Replicating short flows with multiple equal-cost paths is a promising way to reduce FCT. However, the original flow and its replicated one are quite likely to be routed to the same path (ECMP hash collision), which increases both the mean and 99-percentile FCT significantly. What's more, inadequate replication leaves many other less-congested equal-cost paths unused and limits the performance while excess replication degrades throughput of large flows. To solve these problems, we propose SmartRep, a scheme consisting of an efficient and effective traceroute based hash collision avoidance method and an algorithm to decide the optimal number of replicated flows for different short flows. SmartRep can be easily implemented in software and readily deployed in data centers. Extensive NS2 simulations show that our approach improves previous replication-based work by 25%-50% in both mean and 99th percentile FCT, and meanwhile imposes negligible impact on large flows.

The paradigm of cloud computing has spontaneously prompted a wide interest in auction-based mechanisms for cloud resource allocation. To eliminate market manipulation, a number of strategy-proof (a.k.a. Truthful) cloud auction mechanisms have been recently proposed by enforcing bidders to bid their true valuations of the cloud resources. However, as discovered in this paper, they would suffer from a new cheating pattern, named false-name bids, where a bidder can gain profit by submitting bids under multiple fictitious names (e.g, Multiple e-mail addresses). Such false-name cheating is easy to make but hard to detect in cloud auctions. To tackle this issue, we propose FAITH, a new False-name-proof Auction for virtual machine instance allocation, that is proven both strategy-proof and false-name proof by our theoretical analysis. When N users compete for M different types of computing instances with multiple units, FAITH achieves a lower time complexity of O(N log N+NM) compared to exiting cloud auction designs. We further extend FAITH to support range-based requests as desired in practice for flexible auction. Through extensive simulation experiments, we show that FAITH highly improves auction efficiency, outperforming the extended mechanisms of conventional false-name-proof auctions in terms of generated revenue and social welfare by up to 220% and 140%, respectively.

The ever-increasing demands on mobile streaming over smartphones make the cellular networks always occupied by heavy load under traditional base-station-to-device (B2D) based streaming architecture, and even degrade the quality of service (QoS) seriously. To offload the traffic of cellular networks and provide scalable mobile streaming services with guaranteed QoS, in this paper we propose a device-to-device (D2D) communication motivated cooperative streaming framework by exploiting the capacity of both WiFi interface and cellular interface equipped with smartphones. Specifically, under the energy constraint of individual smartphone, we develop technique to minimize the over traffic of the cellular network by efficiently disseminating video over the D2D network with multi-hop routing supported. We formulate such an energy-aware cost-effective video dissemination problem as an integer linear programming problem, and show it to be NP-hard and even hard to approximate. We further present an energy allocation based algorithm and a simulated annealing heuristic algorithm which provide a trade-off between the performance and complexity to support the dissemination scheduling of cooperative mobile streaming. We evaluate the performance effectiveness of our proposal via both theoretical analysis and extensive simulation.

Heterogeneous cellular networks use small base stations, such as femtocells and WiFi APs, to offload traffic from macrocells. While network operators wish to globally balance the traffic, users may selfishly select the nearest base stations and make some base stations overcrowded. In this paper, we propose to use an auction-based algorithm - Femto-Matching, to achieve both load balancing among base stations and fairness among users. Femto-Matching optimally solves the global proportional fairness problem in polynomial time by transforming it into an equivalent matching problem. Furthermore, it can efficiently utilize the capacity of randomly deployed small cells. Our trace-driven simulations show Femto-Matching can reduce the load of macrocells by more than 30% compared to non-cooperative game based strategies.

Wireless power transfer is a promising technology to extend the lifetime of, and thus enhance the usability of, the energy-hungry battery-powered devices. It enables energy to be wirelessly transmitted from power chargers to energy receiving devices. Existing studies have mainly focused on maximizing network lifetime, optimizing charging efficiency, minimizing charging delay, etc. Different from these works, our objective is to optimize charging quality in a 2-D target area. Specifically, we consider the following charger Placement and Power allocation Problem (P3): Given a set of candidate locations for placing chargers, find a charger placement and a corresponding power allocation to maximize the charging quality, subject to a power budget. We prove that P3is NP-complete. We first study P3with fixed power levels, for which we propose a (1-1/e)-approximation algorithm; we then design an approximation algorithm of factor 1-1/e / 2L for P3, where e is the base of the natural logarithm, and L is the maximum power level of a charger. We also show how to extend P3in a cycle. Extensive simulations demonstrate that, the gap between our design and the optimal algorithm is within 4.5%, validating our theoretical results.

Conflict graph has been widely used for wireless network optimization in dealing with the issues of channel assignment, spectrum allocation, links scheduling and etc. Despite its simplicity, the traditional conflict graph suffers from two drawbacks. On one hand, it is a rough representation of the interference condition, which is inaccurate and will cause suboptimal results for wireless network optimization. On the other hand, it only defines the interference between two entities, which neglects the accumulative effect of small amount interference. In this paper, we propose the model of quantized conflict graph (QCG) to tackle the above issues. The properties, usage and construction methods of QCG are explored. We show that in its matrix form, a QCG owns the properties of low-rank and high-similarity. These properties give birth to three complementary QCG estimation strategies, namely low-rank approximation approach, similarity based approach, and comprehensive approach, to construct the QCG efficiently and accurately from partial interference measurement results. We further explore the potential of QCG for wireless network optimization by applying QCG in minimizing the total network interference. Extensive experiments using real collected wireless network are conducted to evaluate the system performance, which confirm the efficiency of the proposed algorithms.

Collecting the RSS between all pair of nodes in the networks is very significant for wireless network optimization, localization, interference management and etc. Aside from its significances, the measurement process could be tedious, time consuming and involving human operations. The state-of-art works usually applied the fashion of “measure a few, predict many”, which use measurement calibrated models to generate the RSS for the whole networks. However, this kind of methods still cannot provide accurate results in a short duration and low measurement cost. In addition, they also require careful scheduling of the measurement which is vulnerable to measurement conflict. In this paper, we propose a compressive sensing (CS)-based RSS measurement solution, which is conflict-tolerant, time-efficient and accuracy-guaranteed without any model-calibrate operation. The CS-based solution takes advantage of compressive sensing theory to enable simultaneous measurement in the same channel, which reduces the time cost to the level of O(logN) (where N is the network size) and works well for sparse networks. Extensive experiments based on real data trace are conducted to show the efficiency of the proposed solutions.

Nowadays more and more users tend to take photos with their smart phones. However, energy-saving continues to be a thorny problem for smart camera phones, since smart phone photographing is a very power hungry function. In this paper, we propose a context aware energy-saving scheme for smart camera phones, by accurately sensing the user's activities in the photographing process. Our solution is based on the observation that during the process of photographing, most of the energy are wasted in the preparations before the shooting. By leveraging the embedded sensors like the accelerometer and gyroscope, our solution is able to extract representative features to perceive the user's current activities including body movement, arm movement and wrist movement. Furthermore, by maintaining an activity state machine, our solution can accurately determine the user's current activity states and make the corresponding energy saving strategies. Experiment results show that, our solution is able to perceive the user's activities with an average accuracy of 95.5% and reduce the overall energy consumption by 46.5% for smart camera phones compared to that without energy-saving scheme.

Some pioneer WiFi signal based human activity recognition systems have been proposed. Their key limitation lies in the lack of a model that can quantitatively correlate CSI dynamics and human activities. In this paper, we propose CARM, a CSI based human Activity Recognition and Monitoring system. CARM has two theoretical underpinnings: a CSI-speed model, which quantifies the correlation between CSI value dynamics and human movement speeds, and a CSI-activity model, which quantifies the correlation between the movement speeds of different human body parts and a specific human activity. By these two models, we quantitatively build the correlation between CSI value dynamics and a specific human activity. CARM uses this correlation as the profiling mechanism and recognizes a given activity by matching it to the best-fit profile. We implemented CARM using commercial WiFi devices and evaluated it in several different environments. Our results show that CARM achieves an average accuracy of greater than 96%.

Auction is a promising approach for dynamic spectrum access in Cognitive Radio Networks. Existing auction mechanisms are mainly proposed to be strategy-proof to stimulate bidders to reveal their valuations of spectrum truthfully. However, they would suffer significantly from a new cheating pattern named false-name bids, where a bidder can manipulate the auction by submitting bids under multiple fictitious names. We show such false-name bid cheating is easy to make but hard to be detected in dynamic spectrum auctions. To resolve this issue, we propose ALETHEIA, a novel flexible, false-name-proof auction framework for large-scale dynamic spectrum access. ALETHEIA has the following important features: (1) it not only guarantees strategy-proofness but also resists false-name bids, (2) it enables spectrum reuse across a large number of bidders, (3) it provides the bidders the flexibility of diverse demand formats, and (4) it incurs low computational overhead. Simulation results show that ALETHEIA achieves both high spectrum redistribution efficiency and auction efficiency.

The limited battery capacity of sensor nodes has become one of the most critical impediments that stunt the deployment of wireless sensor networks (WSNs). Recent breakthroughs in wireless energy transfer and rechargeable lithium batteries provide a promising alternative to power WSNs: mobile vehicles/robots carrying high volume batteries serve as mobile chargers to periodically deliver energy to sensor nodes. In this paper, we consider how to schedule multiple mobile chargers to optimize energy usage effectiveness, such that every sensor will not run out of energy. We introduce a novel charging paradigm, collaborative mobile charging, where mobile chargers are allowed to intentionally transfer energy between themselves. To provide some intuitive insights into the problem structure, we first consider a scenario that satisfies three conditions, and propose a scheduling algorithm, PushWait, which is proven to be optimal and can cover a one-dimensional WSN of infinite length. Then, we remove the conditions one by one, investigating chargers’ scheduling in a series of scenarios ranging from the most restricted one to a general 2D WSN. Through theoretical analysis and simulations, we demonstrate the advantages of the proposed algorithms in energy usage effectiveness and charging coverage.

In this paper, we show the first comprehensive experimental study on mobile RFID reading performance based on a relatively large number of tags. By making a number of observations regarding the tag reading performance, we build a model to depict how various parameters affect the reading performance. Through our model, we have designed very efficient algorithms to maximize the time-efficiency and energy-efficiency by adjusting the reader's power and moving speed. Our experiments show that our algorithms can reduce the total scanning time by 50 percent and the total energy consumption by 83 percent compared to the prior solutions.

With the increasing number of location-dependent applications, positioning and tracking a mobile device becomes more and more important to enable pervasive and context-aware service. While extensive research has been performed in physical localization and logical localization for satellite, GSM and WiFi communication networks where fixed reference points are densely-deployed, positioning and tracking techniques in a sparse disruption tolerant network (DTN) have not been well addressed. In this paper, we propose a decentralized cooperative method called PulseCounting for DTN localization and a probabilistic tracking method called ProbTracking to confront this challenge. PulseCounting evaluates the user walking steps and movement orientations using accelerometer and electronic compass equipped in cellphones. It estimates user location by accumulating the walking segments, and improves the estimation accuracy by exploiting the encounters of mobile nodes. Several methods to refine the location estimation are discussed, which include the adjustment of trajectory based on reference points and the mutual refinement of location estimation for encountering nodes based on maximum-likelihood. To track user movement, the proposed ProbTracking method uses Markov chain to describe movement patterns and determines the most possible user walking trajectories without full record of user locations. We implemented the positioning and tracking system in Android phones and deployed a testbed in the campus of Nanjing University. Extensive experiments are conducted to evaluate the effectiveness and accuracy of the proposed methods, which show an average deviation of 9m in our system compared to GPS.

Collecting histograms over RFID tags is an essential premise for effective aggregate queries and analysis in large-scale RFID-based applications. In this paper we consider an efficient collection of histograms from the massive number of RFID tags, without the need to read all tag data. In order to achieve time efficiency, we propose a novel, ensemble sampling-based method to simultaneously estimate the tag size for a number of categories. We first consider the problem of basic histogram collection, and propose an efficient algorithm based on the idea of ensemble sampling. We further consider the problems of advanced histogram collection, respectively, with an iceberg query and a top-k query. Efficient algorithms are proposed to tackle the above problems such that the qualified/unqualified categories can be quickly identified. This ensemble sampling-based framework is very flexible and compatible to current tag-counting estimators, which can be efficiently leveraged to estimate the tag size for each category. Experiment results indicate that our ensemble sampling-based solutions can achieve a much better performance than the basic estimation/identification schemes.

In this paper, we investigate the minimization problem of average delay of multi-antenna AP based SIMO (single-input and multiple-output) system by optimizing the antenna allocation. We first obtain the upper bound of transmission bandwidth by deriving the expected error probability of coherent detection for SIMO under Rayleigh fading, and then develop the expression of average delay of terminals sharing the same channel via contention by applying CTMC (continuous-time Markov chains). Upon the above results, we formulate the optimization of antenna allocation as a non-linear integer programming problem and present a polynomial time algorithm based on integer partition and minimum matching to support optimized allocation. We prove the correctness of our theoretical derived results by extensive simulations. The performance comparison results show that the proposed antenna allocation algorithm outperforms other heuristic based algorithms under different traffic models.

In today's data center networks, incast congestion happens when multiple servers send data to one receiver simultaneously. Such congestion results in long idle periods of transmission, which significantly delays the mission complete time (MCT). In this paper, we introduce the MIP, a simple distributed scheme at sender side to Minimize the Idle Periods. To this end, MIP increases the concurrency of data transmission by using proactive fair rate control and cut down idle period further by carefully selected RT O. Extensive simulations show that MIP is able to provide near-optimal MCT performance. In particular, MIP requires no modification to OS kernel or switches in current data center networks.

With the rapid proliferation of RFID-based applications, RFID tags have been deployed into pervasive spaces in increasingly large numbers, e.g., the shelves of super markets are filled with tag-labeled items. Conventional localization schemes usually leverage precise anchor nodes to help compute the position of objects. However, it is usually difficult to find or deploy enough anchor nodes for accurate localization. In this paper, we propose solutions to locate the mobile users based on imprecise anchors in RFID systems. A large number of tags with approximate locations are used as anchor nodes to compute the user's locations. We thus present a time-efficient localization scheme to continuously tracking the mobile users. Experimental results indicate that our solutions can accurately locate the mobile users in a real-time approach. The improved method's accuracy is more than 30% better than the base solution.

Today's public cloud providers typically deploy their small sized data centers in multiple geographically different locations, so as to improve data center power usage effectiveness and locate resources closer to users. A major challenge is resource allocation. Many results have been reported regarding this issue from the perspectives of virtual machine consolidation, network-aware virtual machine placement, traffic engineering, dynamic capacity provisioning, and so on. However, there has not been any focus on stable resource allocations, where no resource request or data center has any migration incentives. To the best of our knowledge, this paper is the first attempt at gaining a better understanding of the structure of the Stable rEsource Allocation (SEA) problem. We introduce a formal problem statement and develop two algorithms for the 1-dimensional (1-D) and 2-D cases, respectively. Simulation results show that the proposed algorithms have good scalability and convergence.

Virtual networks that allow tenants to explicitly specify their computing as well as networking resources are recently proposed to be better interfaces between cloud providers and tenants. Many virtual networks have time-varying resource demands, as evidenced in prior studies [1-3]. New opportunities emerge when such variation is exploited. In this paper, we design a novel resource demand model for tenants to flexibly trade off between application performance and cost, and propose a work-conserving allocation algorithm, WCA, for deploying virtual networks with time-varying resource demands. WCA places virtual nodes in a first-fit fashion, and places virtual links through path-splitting. In each physical node or link, by opportunistically sharing physical resources among multiple variable parts of resource demands, physical utilization can be improved, and more virtual networks can be deployed concurrently. Our evaluation results show that WCA achieves a 4% higher physical resource utilization and rejects 18% less virtual network requests than a state-of-the-art algorithm [4].

With the rapid development of virtualization techniques, modern data centers move into a new era of cloud in recent years. Despite numerous advantages such as high resource utilization and rapid service scalability, current virtualization techniques don't guarantee perfect performance isolation among virtual machines sharing the physical machine, which may lead to unstable and unpredictable user-perceived application performance in clouds. Therefore, understanding and modeling performance interference among collocated applications is of utmost importance. However, the hypervisor and guest OSes usually run independent resource schedulers and are invisible into each other, thereby making accurately characterizing performance interference a non-trivial work. In this paper, we first present a comprehensive experimental study on performance interference of different combinations of benchmarks, observing that virtual CPU floating overhead between multiple physical CPUs, and VMEXITs, i.e., the control transitions between the hypervisor and VMs, constitute the key source of performance interference. In order to characterize the performance interference effects, we measure both the application-level and VM-level characteristics from the collocated applications and then build a novel interference prediction framework based on kernel canonical correlation analysis. Our evaluations first show the practicability of KCCA in finding reliable correlation, and further confirm the high accuracy and great applicability of our interference model with a low prediction error of no more than 7.9%.

Flow scheduling is one of the primary issues in data centers. The efficiency of flow scheduling affects the user experience significantly, since the service latency is determined by the flow completion time (FCT). Current transport protocols are based on the Processor Sharing (PS) policy by dividing the link bandwidth equally. As short flows may be blocked by long flows under PS policy, these protocols could not meet latency requirements. The Shortest Remaining Processing Time (SRPT) policy provides a near-optimal solution in term of reducing average FCT. However, this flow scheduling policy may cause long flows suffering unfair delays. In this paper, we propose MERP (Minimizing Expansion Ratio Protocol) for flow scheduling, which aims to navigate the tradeoff between fairness and the average FCT. We propose expansion ratio as a new metric to describe the gap between reality and ideal in terms of acquired link resources by a flow. Larger expansion ratio indicates that the flow obtains fewer bottleneck link resources. We strive to make the flow scheduling relatively fair by reducing the largest expansion ratio of all the flows. And we further demonstrate that reducing expansion ratio is more reasonable than reducing average FCT for services with the Partition/Aggregate pattern. And to meet the scalability requirements, we implement distributed MERP through flow preemption and explicit rate control. The experiments indicate that MERP could significantly reduce the completion time for 99.9th percentile flows under high load.

As tenants take networked virtual machines (VMs) as their requirements, effective placement of VMs is needed to reduce the network cost in cloud data centers. The cost is one of the major concerns for the cloud providers. In addition to the cost caused by network traffics (N-cost), the cost caused by the utilization of physical machines (PM-cost) is also non-negligible. In this paper, we focus on the optimized placement of VMs to minimize the cost, the combination of N-cost and PM-cost. We define N-cost by various functions, according to different communication models. We formulate the placement problem, and prove it to be NP-hard. We investigate the problem from two aspects. Firstly, we put a special emphasis on minimizing the N-cost with fixed PM-cost. For the case that tenants request the same amount of VMs, we present optimal algorithms under various definitions of N-cost. For the case that tenants require different numbers of VMs, we propose an approximation algorithm. Also, a greedy algorithm is implemented as the baseline to evaluate the performance. Secondly, we study the general case of the VM placement problem, in which both N-cost and PM-cost are taken into account. We present an effective binary-search-based algorithm to determine how many PMs should be used, which makes a tradeoff between PM-cost and N-cost. For all of the algorithms, we conduct theoretical analysis and extensive simulations to evaluate their performance and efficiency.

Collecting histograms over RFID tags is an essential premise for effective aggregate queries and analysis in large-scale RFID-based applications. In this paper we consider efficient collection of histograms from the massive number of RFID tags without the need to read all tag data. We first consider the problem of basic histogram collection and propose an efficient algorithm based on the idea of ensemble sampling. We further consider the problems of advanced histogram collection, respectively, with an iceberg query and a top-k query. Efficient algorithms are proposed to tackle the above problems such that the qualified/unqualified categories can be quickly identified. Experiment results indicate that our ensemble sampling-based solutions can achieve a much better performance than the basic estimation/identification schemes.

Internetware challenges distributed systems in aspects from operating platforms, programming models, to engineering approaches, etc. Cloud computing based on virtualization is now a popular paradigm which can meet the dynamic resource allocation requirements of Internetware. Software entities dispersed on distributed nodes over the Internet, now are evolving into self-contained, autonomous software services. These software entities which are often deployed on virtual machines (VMs), are coordinated dynamically to achieve flexible design objectives. To improve the utilization of infrastructure resource, VMs processing components of a software should be consolidated to fewer physical machines (PMs). However, as the increasing trends of communication-intensive softwares, data traffic among VMs should be considered as well. And for the sake of safety and QoS (Quality of Service), certain VMs (e.g. backup nodes) are mutually-exclusive which means some VMs require to be placed on different PMs. In this paper, we investigate the online software placement problem with the target to minimize the network traffic cost, while taking into account the mutually-exclusiveness of VMs. We provide a formal problem description and its NP-hardness analysis. The proposed algorithm places the VMs that have heavy traffic on the same PM, while isolating the mutually-exclusive VMs simultaneously, which can guarantee high effectiveness and reliability for softwares in Internetware, respectively. The simulations show our algorithm reduces the traffic cost by 29% compared against the existing approaches.

With the wide deployment of network facilities and the increasing requirement of network reliability, the disruptive event like natural disaster, power outage or malicious attack has become a non-negligible threat to the current communication network. Such disruptive event can simultaneously destroy all devices in a specific geographical area and affect many network based applications for a long time. Hence, it is essential to build disaster-resilient network for future highly survivable communication services. In this paper, we focus on the integrated approach through the technique of software defined networking to mitigate disaster risks while cut down the investment and management costs. Our design consists of a sub-graph based proactive protection approach for fast rerouting at the network nodes and a splicing approach at the controller for effective post-disaster restoration. Such a systematic design is implemented in OpenFlow framework through the Mininet emulator and Nox controller. Numerical results show that our approach can achieve high reliability, fast recovery and low control overhead.

We consider the problem of broadcasting a message in a mobile ad hoc network (MANET) with the objective of minimizing the broadcast latency. Due to the mobility of network nodes, the coordination among nodes is hard and expensive. Thus it is much desired to design efficient, one-sided broadcast protocols where each node acts according to its own state solely. Although random scheduling is a popular and effective one-sided approach for leveraging the broadcast nature of wireless medium while coping with transmission collisions, both critical for reducing the broadcast latency, in this paper, we show that when nodes move very fast, the performance of pure random scheduling must be sub-optimal, no matter how the forwarding probabilities are specified. Furthermore, we propose a novel one-sided broadcast protocol named R2, which first splits the message into a certain number of mini-messages and then couples a fine-grained random scheduling with random linear network coding for broadcasting the mini-messages. Theoretical analyses demonstrate that R$^2$ performs optimally in order sense, no matter how fast network nodes move around, although different mobility has distinct effect on the speed of message broadcast.

Location privacy preservation has become an important issue in providing location based services (LBSs). When the mobile users report their locations to the LBS server or the third-party servers, they risk the leak of their location information if such servers are compromised. To address this issue, we propose a Location Privacy Preservation Scheme (LPPS) based on distributed cache pushing which is based on Markov Chain. The LPPS deploys distributed cache proxies in the most frequently visited areas to store the most popular location-related data and pushes them to mobile users passing by. In the way that the mobile users receive the popular location-related data from the cache proxies without reporting their real locations, the users' location privacy is well preserved, which is shown to achieve k-anonymity. Extensive experiments illustrate that the proposed LPPS achieve decent service coverage ratio and cache hit ratio with low communication overhead.

With the rapid proliferation of Wi-Fi technologies in recent years, it has become possible to utilize the vehicular wireless network to assist the route guidance for drivers in a cooperative approach, aiming to mitigating heavy traffic congestion. In this paper, we investigate into the route guidance problem in vehicular wireless network, and then propose two efficient routing algorithms, i.e., centralized route guidance and distributed route guidance, according to different situations. A hybrid framework is then proposed to provide optimized routing decisions in a uniform way. Simulation results in Simulation of Urban MObility (SUMO) indicate that, our route guidance schemes achieve much better performance than traditional GPS-based navigation and randomized routing.

In real life, looking for a misplaced object like a key in the room can be usually like searching for a needle in a haystack. In this paper, we propose a novel solution to accurately locate the specified objects attached with RFID tags in indoor environments, by efficiently leveraging the RFID technology. By making a number of novel observations regarding the tag reading performance, we obtain several regularities to depict how various parameters including the reader's power and the antenna's scanning angle affect the reading performance. Based on the regularities, we have designed very efficient algorithms to maximize the accuracy and the time-efficiency for localization. Without the help of any anchor nodes, our solution can rapidly navigate to the target object from a specific initial position. We have implemented a system prototype to evaluate the actual performance in realistic applications. The realistic experiment results show that our solution can restrict the average localization error within 49 cm and reduce the total navigation time by 33% compared to the baseline solutions.

In wireless networks, a recent trend is to make spectrum access dynamic for the sake of efficient utilization of spectrum. In this case, one promising approach is using auction-based market mechanism where available channels are periodically allocated to users. Two of the key objectives in designing an auction mechanism are strategy-proofness and social welfare maximization. It is hard to design a practical auction achieving both objectives. Prior work either do not consider strategy-proofness or do not guarantee performance ratio. In this paper, we achieve a tradeoff between supporting strong strategy-proofness and maximizing social welfare. We design a polynomial-time spectrum auction mechanism that is approximately strategy-proof which bounds the profit gain of a bidder from a lying bid, and yields an allocation with approximate social welfare. Through simulations, we show that our mechanism improves performance by about 30% in terms of social welfare and spectrum utilization, compared to the state-of-art mechanisms.

Motivated by various applications in mobile ad-hoc networks (MANETs) that require nodes to share their individual information to each other, we study the multi-message dissemination problem in a MANET, which is to distribute multiple messages to all mobile nodes in the network in parallel. The objective is to minimize the stopping time, i.e., the time taking for all nodes to receive a copy of the whole messages. We consider an intrinsically one-sided protocol based on random linear network coding (RLNC), where all packets forwarded are in the form of random linear combinations of packets received so far. Its supreme performance is demonstrated theoretically for two cases, low mobility and high mobility, according to the node velocity. In particular, we show that, under general settings, our derived upper bounds of the stopping time match the established lower bound in both cases, although the effects of mobility in the two cases are significantly different. Thus, we conclude that RLNC achieves order optimality for fast information dissemination in MANETs.

In cognitive radio networks (CRNs), a wireless user with primary access right on a channel (called primary user) has prioritized access to the channel and the user with secondary access right (called secondary user) can use the channel when the primary user is idle. Spectrum auction has emerged as a promising approach to address the access allocation problem in CRNs. A significant challenge in designing such auction is providing truthfulness to avoid market manipulation. In most previous work, the primary access rights on channels are pre-determined before the auction and bidders can only compete for the secondary access rights. However, a user's requirement on spectrum access rights relies on their QoS demands. Therefore, it is much desirable to allocate spectrum access rights on the basis of QoS demands as well as to exploit the resulting spatial spectrum reuse opportunities. To solve this problem, we propose TRUMP, a truthful spectrum auction mechanism, by taking into consideration both QoS demands and spectrum spatial reuse, which can drastically improve spectrum utilization. The theoretical analysis proves that TRUMP achieves truthfulness and individual rationality with polynomial-time complexity. Our extensive simulation results show that our proposals outperform previous work in terms of both social welfare and spectrum utilization.

Many studies have presented the order sense results of information transmission capacity and packet delivery delay in mobile ad hoc networks (MANETs). To achieve the fundamental understanding of MANETs, we focus on deriving the closed-form expressions of the network capacity and end-to-end delay. A MANET with the generalized correlated mobility model is considered in this paper, where the mobility of nodes clustered in one group is confined within a specified area, and multiple groups move uniformly across the network. We also leverage limited packet redundancy to speed up the packet transmission, i.e., each source node is allowed to distribute at most f copies of each packet in its delivery process. Specifically, we first propose an effective multi-hop scheduling-routing scheme under the correlated mobility model, and then develop the closed-form expressions of both per node throughput capacity and expected end-to-end delay. We further explore the tradeoff between throughput capacity and packet delay by using packet redundancy f. The simulation studies validate our theoretical results.

Network virtualization has emerged as a promising approach to overcome the ossification of the Internet. A major challenge in network virtualization is the so-called virtual network embedding problem, which deals with the efficient embedding of virtual networks with resource constraints into a shared substrate network. A number of heuristics have been proposed to cope with the NP-hardness of this problem; however, all of the existing proposals reserve fixed resources throughout the entire lifetime of a virtual network. In this paper, we re-examine this problem with the position that time-varying resource requirements of virtual networks should be taken into consideration, and we present an opportunistic resource sharing-based mapping framework, ORS, where substrate resources are opportunistically shared among multiple virtual networks. We formulate the time slot assignment as an optimization problem; then, we prove the decision version of the problem to be NP-hard in the strong sense. Observing the resemblance between our problem and the bin packing problem, we adopt the core idea of first-fit and propose two practical solutions: first-fit by collision probability (CFF) and first-fit by expectation of indicators' sum (EFF). Simulation results show that ORS provides a more efficient utilization of substrate resources than two state-of-the-art fixed-resource embedding schemes.

As a supporting technology for most pervasive applications, indoor localization and navigation has attracted extensive attention in recent years. Conventional solutions mainly leverage techniques like WiFi, cellular network etc. to effectively locate the user for indoor localization and navigation. In this paper, we investigate into the problem of indoor navigation by using the RFID-based delay tolerant network. Being different from the previous work, we aim to efficiently locate and navigate to a specified mobile user who is continuously moving within the indoor environment. We respectively propose a framework to schedule the tasks and manage the resources in the network and a navigation algorithm to locate and navigate to the moving target. Experiment results show that our solution can efficiently reduce the average searching time for indoor navigation.

Network virtualization currently becomes an important technology in optimizing resource management in a datacenter. The major research issue in this area is the virtual network embedding problem (VNEP) concerned with mapping virtual networks (VNs) onto a shared substrate network (SN) with some constrains satisfied. In this paper, by proposing the new concepts of “node sharing” and “partially accepting”, we try to break the “atomicity” of the traditional solutions of VNEP, which usually treat a VN request as an inseparable whole. We consider a more realistic scenario where virtual nodes in a VN request are of different importance and accordingly devise a mapping algorithm called Best Effort Algorithm (BEA). Our algorithm can make the most of the resources through node sharing at idle period of the substrate network and provide the best-effort mapping by partially accepting VN requests when physical resources become scarce. Final simulations demonstrate the effectiveness of our algorithm and show that our novel ideas can lead to higher acceptance ratio and long-term average revenue.

As more and more services are offered in clouds, it is possible to meet the diverse demands of users via service composition. Selecting the optimal set of services, in terms of QoS, is the crucial issue when many functionally equivalent services are available. In this paper, we investigate the service selection problem under the service replica limitation constraint. The objective is to select the optimal service set which brings out the minimal response time. We estimate the communication latency with the network coordinate system. Based on the estimated latencies and service composition paradigm, our selection algorithms find the services which will result in low latency under various replica limitation constraints. We evaluate our approaches via extensive simulations, the experimental results of which show that our algorithms work efficiently.

With the rapid proliferation of RFID technologies, RFID has been introduced to the applications like safety inspection and warehouse management. Conventionally a number of deployment rules are specified for these applications. This paper studies a practically important problem of rule checking over a large set of RFID tags, i.e., checking whether the specified rules are satisfied according to the RFID tags within the monitoring area. This rule checking function may need to be executed frequently over a large number of tags and therefore should be made efficient in terms of execution time. Aiming to achieve time efficiency, we propose two efficient protocols based on the collision detection and the logical features of rules, respectively. Simulation results indicate that our protocols achieve much better performance than other solutions in terms of time efficiency.

In many pervasive applications like the intelligent bookshelves in libraries, it is essential to accurately locate the items to provide the location-based service, e.g., the average localization error should be smaller than 50 cm and the localization delay should be within several seconds. Conventional indoor-localization schemes cannot provide such accurate localization results. In this paper, we design an adaptive, accurate indoor-localization scheme using passive RFID systems. We propose two adaptive solutions, i.e., the adaptive power stepping and the adaptive calibration, which can adaptively adjust the critical parameters and leverage the feedbacks to improve the localization accuracy. The realistic experiment results indicate that, our adaptive localization scheme can achieve an accuracy of 31 cm within 2.6 seconds on average.

In a social network, information runs from word-of-mouth based on the relationship of the users. The influence maximization is to find a limited number of initial users (nodes) to spread the information, so that the maximum number of other users could accept the information, which is a useful technique for marketing, information monitoring and advertising in a social network. Diffusion model of social networks imitates the process of information spreading in social networks, and Independent Cascade (IC) Model and Linear Threshold (LT) Model, are well-known stochastic information influence models. In this paper, we extend the classical IC model according to the observation of users' behaviors in social networks and propose an effective influence maximization algorithm based on this extended IC model. This novel algorithm calculates the influence probability of each node in sub-graphs that other nodes can engendered to it iteratively. The simulation experiments on real social network datasets show that our algorithm is much faster than the greedy hill-climbing algorithm, while the results are very close to the greedy algorithm and out-perform the other heuristic algorithms.

Error correction techniques play an important role to guarantee reliable communication in wireless networks. The widely used error-correcting codes (ECCs) such as Hamming code introduce the benefit of error correction without retransmitting the data packet, but they suffer from high redundancy and communication overhead. In the recent years, error estimating code (EEC) was proposed to estimate the bit-error-rate (BER) of a packet efficiently with very low data redundancy. However, the ability of error correction using EEC remains unexplored. In this paper, we argue that EEC can be used to recover erroneous bits from the data packet. To show the capacity of error recovery with EEC, we propose an error correction scheme based on the parity check information provided by the EEC bits. We first introduce a filtering algorithm to rule out the correct data bits and obtain a set of suspicious bits containing most of the errors. Then we apply a polynomial randomized algorithm called Rand_flipping to examine the suspicious bits and flip the most promising erroneous bits aiming to minimize the total numbers of errors in the packet. Theoretical analysis proves that under some constraints the proposed Rand_flipping algorithm can correct most of the erroneous bits with probability higher than 1-1/e. Extensive experiments based on a real WiFi trace are conducted, which shows that the proposed algorithm corrects over 80% erroneous bits of the trace in practice.

In this paper, we show the first comprehensive experimental study on mobile RFID reading performance based on a relatively large number of tags. By making a number of observations regarding the tag reading performance, we build a model to depict how various parameters affect the reading performance. Through our model, we have designed very efficient algorithms to maximize the time-efficiency and energy-efficiency by adjusting the reader's power and moving speed. Our experiments show that our algorithms can reduce the total scanning time by 50\% and the total energy consumption by 83\% compared to the prior solutions.

This paper poses the following problem: given a task that originates at some node in a Delay Tolerant Network (DTN), how are we to disseminate the workload during pairwise contacts to minimize the makespan? We first investigate the scenario in which each node has access to an oracle that knows global and future knowledge of node mobility, and we propose a centralized polynomial-time optimal algorithm. We then develop a distributed dissemination protocol, D2, which maintains r-hop neighborhood information at individual nodes. D2 makes dissemination decisions based on the estimations of the potential computational capacities and the future workloads of DTN nodes. Using trace-driven simulations, we show that, D2 with only 1-hop information is already near-optimal in a wide variety of environments, and the performance gap becomes smaller as the amount of information maintained at individual nodes increases.

Although the capacity of wireless ad hoc networks has been extensively studied under different mobility models and network settings, few work has been done on the effect of heterogeneous mobile nodes and correlated mobility. In this paper, we consider the heterogeneous wireless networks consisting of two types of nodes, called user nodes and master nodes. Specifically, user nodes are combined into groups and each group is equipped with a more powerful master node serving as relay for packet transmissions among groups. By proposing a simple, asymptotically optimal scheduling and routing scheme, we present the maximum per-node throughput and the end-to-end delay in order sense, respectively. We also explore the trade-offs between capacity and delay by adjusting network settings.

In recent years, OFDMA relay networks have become a key component in the 4G standards (e.g., IEEE 802.16j, 3GPP LTE-Advanced) for broadband wireless access. When numerous bidirectional flows pass through the relay stations in an OFDMA relay network that supports various interactive applications, plenty of network coding opportunities arise and can be leveraged to enhance the throughput. In this paper, we study the proportional-fair scheduling problem in the presence of network coding in OFDMA relay networks. Considering the tradeoff between performance and overhead, we propose two models, global approach (GA) and local approach (LA), under which the corresponding problems are shown both NP-hard. For the GA model, we show that it cannot be approximated within some constant factor. Hence, we propose a heuristic algorithm with low time complexity. For the LA model, we propose a theoretical polynomial time approximation scheme (PTAS), and also present a practical greedy algorithm with approximation factor of 1/2. Simulation results show that our algorithms can achieve significant throughput improvement over a state-of-the-art noncoding scheme.

Due to different requirements in applications, sensors with different capacities are deployed. How to design efficient, reliable and scalable routing protocols in such wireless heterogeneous sensor networks (WHSNs) with intermittent asymmetric links is a challenging task. In this paper, we propose ProHet: a distributed probabilistic routing protocol for WHSNs that utilizes asymmetric links to reach assured delivery rate with low overhead. The ProHet protocol first produces a bidirectional routing abstraction by finding a reverse path for every asymmetric link. Then, it uses a probabilistic strategy to choose forwarding nodes based on historical statistics using local information. Analysis shows that ProHet can achieve assured delivery rate ρ if ρ is set within its upper-bound. Extensive simulations are conducted to verify its efficiency.

The two hop relay algorithms with redundancy are attractive for mobile ad hoc networks (MANET) since they are simple and efficient. In this paper, we extend the analysis of the f-cast two-hop relay algorithm under i.i.d. mobility model to the case of corrected nodes movements, where the source node is allowed to send up to f copies of a packet and the clustered nodes move uniformly across the network. We first provide an effective scheduling-routing algorithm for packet relay inter- and intra-cluster and then explore the scaling laws of throughput capacity of the considered network. This result helps us to study the impact of both the packet redundancy and correlated node movement, and guide us to find the maximum possible throughput capacity through a proper setting of redundancy f.

Network virtualization has been the focus of intense research interest and is a promising approach to overcome the ossification of the Internet. A major challenge with network virtualization is virtual network embedding, which deals with the efficient embedding of virtual networks with resource constraints into a substrate network. Many research results have been reported regarding this problem. However, there hasn't been any focus on virtual network embedding with substrate support for parallelization, i.e., the substrate network supports parallel computation and allows a virtual node to be mapped into multiple substrate nodes. This paper is the first attempt at gaining a better understanding on how parallelization benefits embedding. We present a formal problem description and propose two algorithms that capitalize parallelism. Several extensions are developed to complement the proposed algorithms. From experimental results, the effectiveness and usefulness of the algorithms and extensions are confirmed.

The communication network is now one of the critical infrastructures in our society. However, the current communication networks are facing more and more large-scale region failure threats, such as natural disasters (e.g. earthquake, tornado) and physical attacks (e.g. dragging anchors or EMP attack). Therefore, a deep understanding of network behaviors under region failure is essential for the design and maintenance of future highly survivable networks. In this paper, we focus on the network vulnerability assessment under the geographically correlated region failure(s) caused by a random “line-segment” cut, an important region failure model that can efficiently capture the behaviors of some region failures like earthquake, tornado and anchor cutting. To facilitate such vulnerability assessment, we apply the geometrical probability theory to design a grid partition-based estimation scheme for Disrupted Link Capacity, Pairwise Traffic Reduction and Pairwise Disconnection Probability, three commonly used metrics for statistical vulnerability assessment. A theoretical framework is also established to determine a suitable grid partition such that a specified estimation error requirement is satisfied.

Network virtualization provides a promising way to overcome Internet ossification. A major challenge is virtual network mapping, i.e., how to embed multiple virtual network requests with resource constraints into a substrate network, such that physical resources are utilized in an efficient and effective manner. Since this problem is known to be NP-complete, a variety of heuristic algorithms have been proposed. In this paper, we re-examine this problem and propose a virtual network mapping framework, ORS TA, which is based on Opportunistic Resource Sharing and Topology-Aware node ranking. Opportunistic resource sharing is taken into consideration at the entire network level for the first time and we develop an online approximation algorithm, FFA, for solving the corresponding time slot assignment problem. To measure the topology importance of a substrate node, a node ranking method, MCRank, based on Markov chain is presented. We also devise a simple and practical method to estimate the residual resource of a substrate node/link. Extensive simulation experiments demonstrate that the proposed framework enables the substrate network to achieve efficient physical resource utilization and to accept many more virtual network requests over time.

Cloud computing is a newly emerging reliable and scalable paradigm in which customers pay for cloud resources they use on demand. However, current auto-scaling mechanisms in cloud lack the critical self-adaption policy which helps application providers decide on when and how to reallocate resources. Furthermore, virtualization techniques can not ensure an absolute isolation between multiple virtual machines sharing the same physical resource, which leads to some customers paying unfairly for heavy-loaded resource under a widely-adopted fixed pricing scheme.

Vehicular Ad Hoc Networks (VANETs) enable car-to-car communication without the support of network infrastructure, which introduce diverse application possibilities and have drawn much attention from academy and industry in the past years. Unlike other ad hoc networks, nodes in VANETs are restricted to move in streets and have limited communication ranges. Intuitively, vehicle-to-vehicle communication somehow has similarity to human-to-human interaction, which lead to an interesting question of exploring the social properties of VANET nodes. To address the question, we consider encounters of vehicles as their social relationships and model VANETs as social graphs. Based on the social graph model, we use two traces of mobile vehicles from San Francisco and Shanghai to explore their social properties. Our analysis show that several universal laws of social network are hold for VANETs. The social graphs forming by vehicles are scale-free networks with power-law like distribution of node degrees. Small world phenomenon is also observed in our experiments: the nodes in VANETs have high cluster coefficient and there exist short paths between node pairs less than 3 hops on average. The implication of our analytical results is of benefit to develop large scale software system for mobile applications such as VANETs, as well as helps to facilitate inter-device wireless communications in pervasive environment.

Chunked codes are a variation of random linear network codes with low computational complexities. In chunked codes, the packets in a file are grouped into small (non-overlapped or overlapped) chunks, and random linear encoding operations are performed within each chunk. Previous studies show that when the chunk size is lower bounded by some increasing function of the file length, chunked codes asymptotically achieve the min-cut capacity. However, in most real applications, the chunk size is required to be a small constant due to the computational constraints of network devices. In this case, it remains unknown which rates can be achieved by chunked codes. In this paper, we address the analysis and design of chunked codes with fixed constant chunk sizes. We first highlight the importance of precoding for chunked codes to achieve constant rates, and then present an analysis of non-overlapped chunked (NOC) codes with precoding. We further introduce a new class of chunked codes, called EOC codes, which are based on expander graphs to form overlapped chunks. Numerical and simulation results show that EOC codes achieve significantly higher rates than NOC codes, and also outperform other state-of-the-art overlapped chunked codes.

The limited battery capacity of sensor nodes has become the biggest impediment to wireless sensor network (WSN) applications. Two recent breakthroughs in the areas of wireless energy transfer and rechargeable lithium batteries promise the use of mobile vehicles, with high volume batteries, as mobile chargers that transfer energy to sensor nodes wirelessly. In this paper, for the first time, we envision a novel charging paradigm: collaborative mobile charging, where mobile chargers are allowed to charge each other. We investigate the problem of scheduling multiple mobile chargers, which collaboratively recharge sensors, to maximize the ratio of the amount of payload energy to overhead energy, such that every sensor will not run out of energy. We first consider the uniform case where all sensors consume energy at the same rate, and propose a scheduling algorithm, PushWait, which is proven to be optimal in this case and can cover a one-dimensional WSN of infinite length. Then, in the non-uniform case, which is conjectured to be NP-hard, we first present two observations from space and time aspects to remove some impossible scheduling choices, and we propose our heuristic algorithm, ClusterCharging(β), which clusters sensors into groups and divides a scheduling cycle into charging rounds. Its approximation ratio is also presented. Extensive evaluations confirm the efficiency of our algorithms.

It is a tedious task to search and locate a specific book from massive number of books arbitrarily placed in a bookshelf. In this paper, we demonstrate iBookshelf, a system which allows users to quickly search and accurately locate books in the bookshelf, by leveraging a passive RFID system. By deploying a number of reference tags on the bookshelf, we are able to perform localization based on the similarities in received signal strength, and effectively offset the impact from the ambient noises and interferences. We deploy and evaluate our system in a real 3m x 2.5m bookshelf, and show that users are able to locate the book from our Android-based application with 85% accuracy.

Femtocell network is an efficient configuration to improve coverage and quality of service (QoS) in cellular networks. However, due to dense deployment, users in a femtocell may be interfered by the base stations nearby, resulting in a deteriorated throughput of the femtocell. In this paper, we investigate the resource allocation problem targeting at max-min throughput of the femtocells. Under the assumption that a number of discrete power levels are available for each device, a joint optimization problem over power control and channel allocation is formulated. We show its hardness and propose a particle swarm optimization based algorithm PCASO. We demonstrate the efficiency of PCASO by thorough numerical experiments.

Spectrum auctions have been proposed as an effective approach to fairly and efficiently trade the scarce spectrum resource among wireless users. The most significant challenge of the auction design to provide economic robustness, particularly truthfulness, under the local-dependent interference constraints. However, existing designs either do not consider spectrum reuse or are based on the impractical assumption that each user requests at most one channel. In this paper, we address this problem by proposing DOTA, a DOuble Truthful Auction for dynamic spectrum access. DOTA is economic-robust in terms of truthfulness, individual rationality, and no-deficit. It achieves improved utilization by exploiting spectrum reuse as well as dealing with the interference constraints. Moreover, DOTA minimizes the network transaction overhead and provides flexible channel bidding including range bidding and strict bidding.

Peer-to-peer (P2P) overlay-based streaming services have became more and more attractive. However, it is still challenging to provide scalable streaming services over large-scale Internet environment beacause of the stringent quality of service requirements as well as the dynamic nature of P2P overlay network. In this study, the authors focus on the optimisation of streaming data scheduling in P2P video-on-demand (VoD) system, with the objective of minimising the server stress and maximising the playback continuity. The authors first model the data scheduling problem to the maximum network flow problem where the schedule scheme is transformed to find an optimal supplier-consumer relationship assigment among peers with minimal server strees, and then present two max-flow-based streaming data scheduling algorithms by combining the upload capacity of peers as well as the path capacity between peers. The authors prove that the computing complexing of the proposed scheduling algorithms is polynomial. The practicability of the proposal is evaluated via simulations. Simulation results indicate that the proposed scheduling scheme could distribute bandwidth load among peers well while keeping the node degree low. Simulation results also show that the novel proposal has better performance than previous work in term of the server stress and the playback continuity.

Wireless Sensor Networks (WSNs) are key for various applications that involve long-term and low-cost monitoring and actuating. In these applications, sensor nodes use batteries as the sole energy source. Therefore, energy efficiency becomes critical. We observe that many WSN applications require redundant sensor nodes to achieve fault tolerance and Quality of Service (QoS) of the sensing. However, the same redundancy may not be necessary for multihop communication because of the light traffic load and the stable wireless links. In this paper, we present a novel sleep-scheduling technique called Virtual Backbone Scheduling (VBS). VBS is designed for WSNs has redundant sensor nodes. VBS forms multiple overlapped backbones which work alternatively to prolong the network lifetime. In VBS, traffic is only forwarded by backbone sensor nodes, and the rest of the sensor nodes turn off their radios to save energy. The rotation of multiple backbones makes sure that the energy consumption of all sensor nodes is balanced, which fully utilizes the energy and achieves a longer network lifetime compared to the existing techniques. The scheduling problem of VBS is formulated as the Maximum Lifetime Backbone Scheduling (MLBS) problem. Since the MLBS problem is NP-hard, we propose approximation algorithms based on the Schedule Transition Graph (STG) and Virtual Scheduling Graph (VSG). We also present an Iterative Local Replacement (ILR) scheme as a distributed implementation. Theoretical analyses and simulation studies verify that VBS is superior to the existing techniques.

Broadcast is a fundamental operation in wireless ad hoc networks (WANETs). To design efficient broadcast protocols, one of the most important concerns is to reduce broadcast redundancy. In conventional WANETs where nodes are always active, due to the broadcast nature of wireless medium, minimizing broadcast redundancy is equivalent to finding a Minimum Connected Dominating Set (MCDS). However, this is not true for uncoordinated duty-cycled WANETs, where each node periodically switches between active and sleep states, and can only hear messages when it is active. In this paper, we investigate the minimum redundancy broadcast problem in uncoordinated duty-cycled WANETs. We first show that by modifying the conventional CDS-based approaches properly, a constant-approximation broadcast algorithm (MCA) can be obtained. We then propose a hierarchical CDS-based algorithm (HCA), improving the best known approximation ratio from 20 to 13.67. Both algorithms are distributed, and with low time and message complexities. Simulation results show that our algorithms achieve about 5%-30% performance improvement over the state-of-the art scheme.

Network virtualization has emerged as a powerful way to fend off the current ossification of the Internet. A major challenge is virtual network mapping, which is to assign substrate resources to virtual networks (VNs) such that some predefined constraints are satisfied and substrate resources are utilized in an effective and efficient manner. Due to the NP-completeness of this problem, a variety of heuristic algorithms have been proposed. However, existing solutions rarely consider the inefficient utilization of bandwidth resources due to the network traffic fluctuation. In this paper, we study the opportunistic bandwidth sharing in a single physical link among multiple virtual links from different VNs. We formulate the problem of assigning time slots to dispensable sub-flows with constraints on the performance guarantee and the objective of minimizing the number of time slots used, as an optimization problem. Two heuristic algorithms HA-I and HA-II, which consider the problem from different perspectives, are presented. Extensive simulations are conducted to evaluate the effectiveness and efficiency of our algorithms.

Service composition is a useful technology to achieve dynamic requests. But in cloud, the cloud provider should guarantee the QoS of the user request as well. Previous work investigated how to select proper available replicas (the similar functional services located on different physical nodes) to effectively achieve the composite services. However, as the requirements for some service grow, even the optimal selection strategy could not satisfy all the QoS requests, if it is only based on the existed replicas. In this case, cloud provider should deploy more replicas to meet the growing requests. Some existing literatures have addressed the service redeployment problem, aiming to optimize the overall or average performance; however, few of them can guarantee QoS of each request. This paper investigates QoS-aware service redeployment problem (SRP), with objective to minimize the redeployment cost. We show that, it is NP-hard to decide whether there exists a feasible solution of SRP. Thus we propose a novel heuristic algorithm SRA, which can find a solution such that most of the requests can be satisfied, while the deployment cost is minimized. Experimental results show that our approach is effective and efficient.

Network virtualization has emerged as the most promising approach to overcome the current ossification of the Internet. A key problem in it is how to efficiently and effectively make use of the substrate network resources by embedding multiple virtual networks with various constraints. Due to its NP-hardness, many heuristic approaches have been proposed. However, most of them simplify the problem by relaxing some constraints, resulting in their designs in conflict with practical limitations. Furthermore, some other important design issues, like load balancing and the response time requirements of different applications, have been usually ignored as well. In this paper, we propose FELL, a Flexible virtual network Embedding algorithm with guaranteed Load baLancing for the general problem. Based on simulated annealing, FELL can flexibly control the tradeoff between results accuracy and running time to meet various requirements of different applications by changing parameters. Load balancing enables substrate network to avoid resource fragmentation and further increases the profit of infrastructure providers. A novel cost criterion that reflects the impact of distribution of allocated resources for an embedding is designed to conduct embedding process to guarantee it. The splittable flow is supported to obtain better resource utilization by making use of small pieces of available bandwidth. We also design some key functions including generating initial and neighbor solutions. The effectiveness of our algorithm is finally validated by our simulations.

Opportunistic spectrum access, which allows secondary users opportunistically access unused licensed channels to exploit instantaneous spectrum availability, is a promising approach to achieve efficient spectrum utilization and mitigate spectrum scarcity. To address the challenge of dynamic spectrum access, one of the most important issues is cooperative spectrum reallocation among secondary users to minimize spectrum handoffs. In this paper, we present a low-complexity approach based on conflict graph to optimize spectrum reallocation by local coordination. In order to reduce communication overhead, we propose two heuristic spectrum selection methods named local observation and metric maximum. Experimental results show two benefits of the proposed schemes. On one hand, the coordination approach can dynamically improve the total system throughput (approximately doubled at most). On the other hand, our heuristic strategies decrease the number of spectrum handoff by up to 20% compared with existing strategies.

Recently, the SINR-model has been widely utilized in link scheduling, spectrum allocation and other applications. The SINR model requires the receiving power information of all potential link peers, which is usually assumed to be known as priori or following a uniform propagation model. We have performed experiments to illustrate how real power data could improve the performance of the SINR-based applications with considerable margin. Thus, obtaining the real power data through measurements is promising. However, this method faces many challenges. We propose a pathloss model based solution, including a representative link selection method to cut down the measurement pairs; accuracy control to determine the sample size; and a measurement distribution method to shorten the measurement duration. Our experiments show that our solution significantly improves the SINR-based scheduling's performance.

Secondary Spectrum Auction (SSA) has been proposed as an effective approach to design spectrum sharing mechanism for dynamic spectrum access. However, due to the location-constrained spectrum interference among users, it is a great challenge to provide truthful auction with maximized spectrum utilization. Most previous SSA designs either fail in addressing truthfulness or cause loss on spectrum utilization. In this paper, we focus on providing truthful SSA with maximized spectrum utilization. In order to minimize the computational overhead involved in addressing location-constrained interference, we leverage the truthfulness by introducing approximate truthfulness. Moreover, we define a general spectrum auction model using linear programming. Based on this model, we further propose ETEX, a sealed-bid auction mechanism with approximate truthfulness. Theoretical analysis confirms that ETEX is able to achieve truthfulness in expectation with polynomial complexity. Extensive experimental results show that ETEX outperforms most popular truthful spectrum auctions in terms of social welfare, spectrum utilization and user satisfaction.

This paper considers a category of rogue access points (APs) that pretend to be legitimate APs to lure users to connect to them. We propose a practical timing-based technique that allows the user to avoid connecting to rogue APs. Our detection scheme is a client-centric approach that employs the round trip time between the user and the DNS server to independently determine whether an AP is a rogue AP without assistance from the WLAN operator. We implemented our detection technique on commercially available wireless cards to evaluate their performance. Extensive experiments have demonstrated the accuracy, effectiveness, and robustness of our approach. The algorithm achieves close to 100 percent accuracy in distinguishing rogue APs from legitimate APs in lightly loaded traffic conditions, and larger than 60 percent accuracy in heavy traffic conditions. At the same time, the detection only requires less than 1 second for lightly-loaded traffic conditions and tens of seconds for heavy traffic conditions.

Context data is important information for the behaviors of the applications in a pervasive space. To effectively restore huge amount of data, tree-liked layered storage architecture are proposed, where the leaf nodes collect the data from the sensing devices located in its domain. However, the sensing devices may be moving among different domains. In order to integrate the data from the same device, related leaf nodes should upload and store the data to a certain up-layer node, called host node. This paper presents a deep study of the data storage problem and proposes an online algorithm DHS to dynamically select the host node, which reduces the communication cost significantly. We prove the correctness of the algorithm theoretically. The experiment results also show that DHS is correct and effective.

Replication is a widely used technique in unstructured overlays to improve the content availability or the system performance. Among the prior work on replication, a fundamental question is often addressed: how many replicas should be kept for each data item if given the fixed request rates and the limited storage capability? The Square-Root Replication, in which the replica number of an item is proportional to the square root of its global request rate and proportional to its item size, is usually considered to be optimal as far as the minimization of the search size is concerned. However, our work shows that this viewpoint is not always true, especially in the realistic environments. Firstly, we hold that the replica number should be inversely proportional to the square root of the item size in the optimal replication under the theoretical settings. Secondly, the Square-Root Replication is not optimal when TTL (Time to Live) is small or replica density is low in the practical applications. In this paper, we firstly formulate the questions and present the formal proofs, and finally provide some simulations to validate our conclusions.

Radio Frequency IDentification (RFID) technology has attracted much attention due to its variety of applications, e.g., inventory control and object tracking. One important problem in RFID systems is how to quickly estimate the number of distinct tags without reading each tag individually. This problem plays a crucial role in many real-time monitoring and privacy-preserving applications. In this paper, we present an efficient and anonymous scheme for tag population estimation. This scheme leverages the position of the first reply from a group of tags in a frame. Results from mathematical analysis and extensive simulation demonstrate that our scheme outperforms other protocols proposed in the previous work.

Wireless sensor network (WSN) applications require redundant sensors to guarantee fault tolerance. However, the same degree of redundancy is not necessary for multi-hop communication. In this paper, we present a new scheduling method called virtual backbone scheduling (VBS). VBS employs heterogeneous scheduling, where backbone nodes work with duty-cycling to preserve network connectivity, and non-backbone nodes turn off radios to save energy. We formulate a maximum lifetime backbone scheduling (MLBS) problem to maximize the network lifetime using this scheduling model. Because the MLBS problem is NP-hard, two approximation solutions based on the schedule transition graph (STG) and virtual scheduling graph (VSG) are proposed.We also present an iterative local replacement (ILR) scheme as an distributed implementation of VBS. The path stretch problem is analyzed in order to explore the impact of VBS on the network structure. We show, through simulations, that VBS significantly prolongs the network lifetime under extensive conditions.

Delay/Disruptive Tolerant Network (DTN) differs from the traditional networks in that it has no continuous or contemporaneous connections but only intermittent connections among wireless nodes and thus it is viewed as an opportunistic networks. DTNs emerge as a good alternative to provide services to a variety of applications in highly challenged environments. However, the characteristics of DTNs make existing solutions infeasible to be applied directly and new solutions are required to be explored, such as multicast which has been extensively studied before in internet and mobile ad hoc networks. Network coding has been proved been proved as an efficient way to improve the performance of multicast in traditional networks. In this paper, we use simulations to study how multicast with network coding performs in DTNs in terms of delivery delay under various application requirements (i.e., the amount of content to distribute and the number of multicast group members) and the network settings (i.e., the popularity of the network and the contact rate). Some empirical results are provided in this paper as well.

A lot of network services and applications are being designed to support quality-of-service (QoS) routing. One of the key problems is to find a feasible path that satisfies multiple QoS requirements, i.e., Multi-Constrained Path (MCP) problem which is known to be NP-complete. Many heuristic and approximation algorithms have been proposed to solve this problem. However, most of them converted it into the classic shortest path problem by transforming multiple QoS weights into single weight. In this paper, we propose a binary graph reduction (BGR) algorithm to convert network graph into a simplified graph by removing redundant edges before constructing a routing path. BGR improves system performance from two aspects: i) BGR decreases the decision-making time, which then decreases the delay of end users; ii) BGR removes some abnormal anti-heuristic redundant edges from network graph, so that the actual routing algorithm could get a better result. We use a multimedia delivery system to illustrate these advantages in this paper. Simulation results also approve the efficiency of the proposed BGR algorithm.

The requirement for supporting DVD-like functions raises new challenges to the design of P2P VoD systems. The uncertainty of frequent user DVD-like interactivity makes it difficult to ensure user perceived Quality of Experience (QoE) for real-time streaming services over distributed self-organized P2P overlay networks. Most existing solutions are based on the unreasonable assumption that all the users in P2P VoD systems have the same preference. Few attention has been paid to personalization, which accommodates the differences between users. In this paper, we present a video model which characterizes the personalization information for users' contents and preferences. Based on this model, we develop APEX, a practical personalization framework for P2P VoD applications. APEX makes the personalization practical by using a hybrid architecture which leverages the offline pattern mining on the server side and online collaborative filtering on the peer side. Furthermore, APEX helps peers to personalize navigation, prefetching and membership management, aiming at improving QoE for DVD-like functions by reducing response latency and optimizing content sharing. Both theoretical analysis and comprehensive simulations show that APEX outperforms most existing schemes in terms of accumulated hit ratio, response latency, and searching efficiency.

This paper presents a fundamental understanding regarding the effect that transmitting power has on the capacity of wireless ad hoc networks. Under the assumption that all interference is essentially regarded as noise, we carry out a quantitative analysis from the perspective of information theory. First, we answer the question, "How much information can be carried per unit bandwidth over a wireless ad hoc network under a certain power assignment and nodal distribution?" We then prove that the maximum network capacity, whether in bps (bits per second) or in bmps (bit-meters per second), strictly increases with respect to the total transmitting power under a fixed-proportion assignment, and that there is a limit as the total transmitting power goes to infinity. We further conclude that the maximum power efficiency, whether in bpJ (bits per Joule) or in bmpJ (bit-meters per Joule), strictly decreases with respect to the total transmitting power under a fixed-proportion assignment. We also show that the maximum network capacity, whether in bps or in bmps, follows an O(n) scaling law, where n is the number of nodes, which coincides with previous asymptotic conclusions. Finally, we highlight the practical implications of the results for power allocation, power assignment, and transmission scheduling. The contributions of this paper may be worthy of consideration by wireless network designers.

The past five years witnessed a rapid development in wireless sensor networks, which have been widely used in military and civilian applications. Due to different requirements in their application environment, sensors with different capacities, power, and so on are deployed. Data routing in such heterogeneous sensor networks is a challenging task. On one hand, the heterogeneous features bring about the diversity in their transmission ranges, which subsequently lead to asymmetric links in the communication graph. As a result, conventional routing strategies based on undirected graphs become unsuitable. On the other hand, sensors communicate with each other through intermittent asymmetric links. It is important to provide assurable delivery rate for mission critical applications. In this paper, we propose ProHet: a Probabilistic routing protocol for Heterogeneous sensor networks, which can deal with asymmetric links well and work in a distributed manner with low overhead and assurable delivery rate. The ProHet protocol first produces a bidirectional routing abstraction by finding a reverse routing path for every asymmetric link. Then, it uses a probabilistic strategy to choose forwarding nodes based on historical statistics, which is shown to achieve assurable delivery rate by theoretical analysis. Extensive simulations are conducted to verify the efficiency of the proposed protocol.

Interactive wireless applications, like VoIP over wireless networks, desire high-quality links and smooth connectivity during user movement. In order to support seamless roaming in wireless networks, handoff optimization has attracted a lot of attention recently. Most existing approaches aim at reducing handoff latency in communication protocols. While these methods provide significant savings in handoff latency, frequent handoffs could still be crucial and problematic for interactive applications. In this paper, we propose a new perspective for handoff optimization by introducing navigation guidance to minimize the handoff frequency. We first formulate the navigation-driven handoff minimization problem, then propose an optimal algorithm and a localized algorithm to solve it. The optimal algorithm assumes global knowledge of AP locations and uses a navigation graph to find a minimal handoff frequency path. The localized algorithm, however, only uses neighbor AP locations for route selection, which is more practical in real applications. Implementation issues of the proposed algorithms are discussed and simulations based on real world AP deployment are used to evaluate their performance. Experiment results show that our algorithms reduce handoff frequency by at most 42% compared to existing strategies.

Power control and routing are two fundamental supporting techniques for wireless communications in ad hoc networks. However, most existing power control and routing proposals are not really efficient enough, due to separate considerations on them. In this paper, motivated by the observation on the necessity and feasibility of the combination of power control and routing, we propose a power controlled routing protocol PCAR (Power Controlled Ad hoc Routing). The basic idea is to develop power control on top of the distance-vector routing mechanism that is based on the classical distributed Bellman-Ford algorithm. Each node adjusts the transmission power automatically through the PIPC (Proportion-Integral Power Control) algorithm that we previously proposed. Both theoretical analysis and simulation results show that PCAR has a good performance.

Pervasive computing, the new computing paradigm aiming at providing services anywhere at anytime, poses great challenges on dynamic service composition. Existing service composition methods can hardly meet the requirements of dynamic characteristic and heterogeneity in pervasive computing environment. In this paper, we propose a parameter-based service model to accurately describe pervasive services. Based on the model, pervasive services are aggregated in a two-layer graph according to both semantic and syntactic information of the input and output parameters. Moreover, we design a novel service composition scheme to accomplish the user task while satisfy the QoS requirements. Both theoretical analysis and simulation experiments show that this service composition mechanism is effective in pervasive environment.

Service-oriented multimedia processing system is an effective approach to allow dynamic and customized service requests in a pervasive environment. This paper studies the context-aware multimedia processing problem under the consideration of the QoS from two aspects: delay and media quality. The second metric is introduced based on the factor that different display devices can adapt to different media quality to the same request. We propose a new measurement, the media quality change ratio, to quantitively describe the adaptability of source media to meet quality requirement of different devices. We further investigate the important issue on how to find an optimal service path according to the users' requirements which are formulated as functional paths. Previous work on the path construction is only based on one fixed functional path. We propose a heuristic algorithm CMpath that explores multiple functional paths and thus can generate a service path to meet both low-delay and media quality requirements. Our experimental results also validate the proposed algorithm.

Broadcast is a fundamental operation of wireless ad hoc networks (WANET) and has been widely studied in the last decade. However, very few existing broadcasting strategies has considered the scenarios with sleeping schedule, which is a prevalent power-saving method in wireless networks. In this paper we study the sleeping schedule-aware minimum latency broadcast (MLB-SA) problem in WANETs and prove its NP-hardness. By constructing a shortest path tree (SPT) defined with the latency function on the network, we derive a lower bound on the broadcast latency theoretically. Following the top-down layered approach and using the D2-coloring solution, we proposed two progressively improved algorithms: the simple layered coloring algorithm (SLAC) and the enhanced layered coloring algorithm (ELAC) for the MLB-SA problem. The SLAC has an approximation ratio of O(Delta2+ 1) where Delta is maximum degree of the network, while the ELAC has constant approximation ratio of 24|T| + 1 where |T| is the number of timeslots in a scheduling period. The two algorithms have O(n2) and O(n3) time complexities respectively. The performance of the proposed algorithms are evaluated by simulations.

Supporting user interactivity in peer-to-peer streaming systems is challenging. VCR-like operations, such as random seek, pause, fast forward and rewind, require timely P2P overlay topology adjustment and appropriate bandwidth resource re-allocation. If not handled properly, the dynamics caused by user interactivity may severely deteriorate users' perceived video quality, e.g., longer start-up delay, frequent playback freezing, or blackout altogether. In this paper, we propose a derivative tree-based overlay management scheme to support user interactivity in P2P streaming system. Derivative tree takes advantage of well organized buffer overlapping to support asynchronous user requests while brings high resilience to the impact of VCR-like operations. A session discovery service is introduced to quickly locate parent peer. We show that the overhead of VCR-like operations in derivative-tree based scheme is O(log(N)), where N is the number of sessions. Simulation experiments further demonstrate the efficiency of the proposed scheme.

Maintaining cache consistency in mobile environment is an important issue which is extensively studied in the last decade. In mobile ad hoc networks (MANETs), a large number of nonstationary mobile terminals connect with each other through multi-hop unreliable communication channels, coupling with the fact that disconnections from the network are very frequent. Most existing cache consistency strategies assume reliable communication between mobile terminals, which cannot handle frequently offline devices adequately. In this paper, we introduce the probabilistic cache consistency model for applications not requiring strong consistency. Based on this model, a probability consistency strategy (ProP) for frequently offline devices in MANETs is studied. ProP is a randomized pull-based Strategy. It is demostrated to guarantee cache consistency with a high probability. A theoretical model is developed to investigate the performance of the proposed cache consistency strategies, and design guidelines are provided for ProP to choose proper system parameters to achieve probabilistic cache consistency.

Sleep scheduling protocols are widely used in wireless sensor networks for saving energy in sensor nodes. However, without considering the special requirements of object tracking, conventional sleep scheduling protocols may lead to intolerable degradation of tracking qualities when they are used in object tracking applications. To handle this problem, sleep scheduling protocols tailed for object tracking have been proposed recently. For saving energy while maintaining satisfactory tracking qualities, these protocols pro-actively awaken sensors according to the prediction of objects' movement. Such sleep scheduling protocols are called the prediction-based sleep scheduling protocols. Most existing prediction-based sleep scheduling protocols require sensor nodes to know the locations of themselves, which may not always be available. In this paper we propose a Location-free Prediction-based Sleep Scheduling protocol (LPSS) for object tracking in sensor networks. LPSS guarantees the coverage level, an important tracking quality in most applications, which is defined as the number of sensors simultaneously detecting the object. In LPSS, when a sensor detects the object, it will emit a signal, namely the sensing stimulus. Sensors decide to wake up or not based on only the received sensing stimulus, the prediction models and the required coverage level, without the requirement of location information. We implement LPSS with two most popular prediction models: the Circle-based and the Probability-based prediction models. Experiment results show that LPSS not only provides qualified coverage levels, but also saves about 40% to 70% energy compared with existing location-free protocols. Moreover, the energy cost of LPSS is close to the ideal approach using accurate location information in terms of the number of awakened nodes.

Supporting free VCR-like operations in P2P VoD streaming systems is challenging. The uncertainty of frequent VCR operations makes it difficult to provide high quality realtime streaming services over distributed self-organized P2P overlay networks. Recently, prefetching has emerged as a promising approach to smooth the streaming quality. However, how to efficiently and effectively prefetch suitable segments is still an open issue. In this paper, we propose PREP, a PREdiction-based Prefetching scheme to support VCR-like operations over gossip-based P2P on-demand streaming systems. By employing the reinforcement learning technique, PREP transforms users' streaming service procedure into a set of abstract states and presents an online prediction model to predict a user's VCR behavior via analyzing the large volumes of user viewing logs collected on the tracker. We further present a distributed data scheduling algorithm to proactively prefetch segments according to the predicted VCR behavior. Moreover, PREP takes advantage of the inherent peer collaboration of gossip protocol to optimize the response latency. Through comprehensive simulations, we demonstrate the efficiency of PREP by gaining the accumulated hit ratio close to 75% while reducing the response latency close to 70% with only less than 15% extra stress on the server side.

Providing continuous on-demand streaming services with VCR functionality over ubiquitous environments is challenging due to the stringent QoS requirements of streaming service as well as the dynamic characteristics of both underlying network and user behavior. In this paper, we propose SkipStream, a skip graph based peer-to-peer (P2P) on-demand streaming scheme with VCR support to address the above challenges. In the design of SkipStream, we first group users into a set of disjoint clusters in accordance with their playback offset and further organize the resulted clusters into a skip graph based overlay network. In addition, we present a distributed on-demand streaming scheduling mechanism to minimize the impact of VCR operations and balance system load among nodes adaptively. The average search latency of SkipStream is O(log(N)) where N is the number of disjoint clusters. We also evaluate the performance of SkipStream via extensive simulations. Experimental results show that SkipStream outperforms early skip list based scheme DSL by reducing the search latency 20%-60% in average case and over 50% in worst case.

This paper considers a category of rogue access points (APs) that pretend to be legitimate APs to lure users to connect to them. We propose a practical timing based technique that allows the user to avoid connecting to rogue APs. Our method employs the round trip time between the user and the DNS server to independently determine whether an AP is legitimate or not without assistance from the WLAN operator. We implemented our detection technique on commercially available wireless cards to evaluate their performance.

Media streaming service over Internet has become more and more popular in recent years, with the emerging applications like Internet TV and VOD (Video on Demand) systems. In the context of pervasive computing, media streaming service is supposed to be available anytime and anywhere. In order to achieve pervasive media service, one of the most important issue is application migration, that is, migrating live streaming from one device to another without interruption. For example, people can watch football games in a moving car, and migrate the video to a pocket PC when leaving the car, and then continue enjoying the game in a TV screen after coming home. In this paper, we will address the technical issues for seamless media streaming migration in pervasive environment.

Service composition is a useful technique to assemble light, independent services to meet the complicated and dynamic requirements. Previous research has addressed the quality-of-service (QoS) aware composition path selection problem. However, as the requests growing, the selected service composition path may violate the QoS requirements. In this case, more service replicas should be deployed on suitable nodes to improve the QoS. But which service component should be selected and where these service replicas should be deployed is a challenge. In this paper, we make a deep study on this service replication problem. We give a detailed description of service replication triggering time. And then, we propose LDCS (Longest Delay Service Component Selection) to select the bottle-neck service component by evaluating the real-time performance of all these components. Finally, we employ MACP (Maximum Available Capacity Path) algorithm to select a suitable node to deploy this service replica. Simulation results approve that our approach is effective and efficient.

Service composition is an effective approach for multimedia delivery in pervasive environment. In previous works, there is one fixed functional path which is composed of several underlying services in a certain order. Actually, there are several functional paths delivering different quality level multimedia from the source to the end user. Due to the dynamicity and mobility of pervasive space, system should generate a reliable and low-delay service path for multimedia delivery in real-time. Since some multimedia service components change the data transmission volume which has a deep impact on the transmission delay, it makes the media delivery problem equal to Multi-Constrained Path problem which is known to NP-Complete. We propose an efficient algorithm LD/RPath(Lowest Delay/Reliability Path) for adaptive multimedia delivery. LD/RPath generates a low-delay service path based on several functional paths with reliability guarantee. Experiment results show that LD/RPath has a good performance and it is an effective algorithm for multimedia delivery in pervasive space.

Service composition is an effective approach for large- scale multimedia delivery. One of the challenge issues is how to choose services to build a multimedia delivery path from source to destination based on user's requirements. In previous works, user's requirement is represented as one fixed functional path which is composed of several functional components in a certain order. Actually, there may be several functional paths (deliver different quality level multimedia data, e.g. image pixel, frame rate) that can meet one request. And due to the diversity of devices and connections in pervasive environment, system should choose a suitable media quality delivery path in accordance with context, instead of based on one fix functional path. This paper proposes LDpath which aims at delivering multimedia data to end users with lowest delay. It chooses services to build delivery path hop-by-hop and the generated path matches one of the possible functional paths, which essentially achieves the context aware multimedia delivery. Furthermore, the amount of data transmission deeply affects delay, thus, LDpath considers data volume changing as one of the metrics of service selection. Experimental results show that LDpath is an effective approach for multimedia delivery in pervasive space.

Self-organization is the key to implement self-calibration, autonomously coordination and P2P communication in sensor networks. Current researches mainly solve this problem in an inappropriate pre-planned manner. The swarm intelligence of the ant colony algorithm (ACA) provides a novel and efficient method for self-organization. For the similarity of sensor network and ant colony, we argue that the sensor networks will benefit from the bio-inspired self-organization by applying the ACA in optimization, structure formation and task/resource allocation. In this paper we outline the current researches on the ACA in sensor network first, then propose the potential applications and research issues. General design of the ACA in sensor network and some challenges are presented as well.

As a fundamental operation of wireless ad hoc networks (WANET), broadcast has been widely studied in the past ten years. However, most existing broadcasting strategies assumed non-sleeping wireless devices. Little attention has been paid to broadcast in WANETs with sleeping schedule, which is a promising power-saving method in wireless networks. In this paper we study the sleeping schedule aware minimum transmission broadcast problem in WANETs (MTB-SA problem) and prove its NP-hardness. Both centralized and distributed approximation algorithms are presented to solve the problem. The centralized algorithm SchmM-Cent has an approximation ratio of 3(ln¿+1) and time complexity of O(n^3). The distributed algorithm SchmM-Dist has a constant approximation ratio of at most 20, while time and message complexity are both O(n). In addition, we provide theoretical analysis and simulations to evaluate the performance of the approximation algorithms.

Location dependent information services (LDISs) are gaining increasing popularity in recent years. Due to limited client power and intermittent connectivity, caching is an important approach to improve the performance of LDISs. In this paper, we propose a new replacement policy called location dependent cooperative caching (LDCC). Unlike existing location dependent cache replacement policies, the LDCC strategy applies a prediction model to approximate client movement behaviors and a probabilistic transition model to analyze the communication cost, resulting in a fully improvement of overall performance. Simulation results demonstrate that the proposed strategy significantly outperforms existing policies.

Power control plays an important role in wireless communications. However, most existing power control protocols are not efficient enough to be applied in real ad hoc network systems. In this paper, we propose PIPC (Proportion-Integral Power Control), a novel closed-loop power control algorithm that can be used in conjunction with any routing protocol as long as the routing table of a node provides enough knowledge of local network topology. PIPC adaptively adjusts the transmission power for each node through an improved version of the classical PID (Proportion-Integral-Differential) control. The topology derived under PIPC is also fed back to the routing table that is used as its input. Both theoretical analysis and simulation study show that PIPC has a good performance.

Service composition is an effective method to achieve flexible pervasive application. According to the relationship of messages and behaviors, we define a message oriented activity based Petri net (Moap) model to describe service, which supports concurrent processes and the reuse of composite service. And user's loose requirement is denoted as goal which is composed of expected input, output and key behaviors. Based on Moap, an automatic service composition algorithm autoSC is proposed to automatically create a specification of composite process to achieve goal. Finally, we analyze the effectiveness of autoSC and give a detailed comparison with other methods.

Multimedia applications are becoming more and more popular on today's Internet. Given the enormous development costs and less flexibility, traditional monolithic based approaches are not suitable for building large-scale multimedia systems. By composing of distributed, autonomous services dynamically to provide more complex tasks, service composition provides an attractive way for building large-scale Internet applications. So, multimedia service composition provides a viable solution to large-scale complex multimedia systems. One of the challenging issues of multimedia service composition is how to find service paths to route the data flows through while meeting the applications' resource requirements and specific QoS constraints. However, QoS-aware service routing problem is typically NP-hard. In this paper, we propose a heuristic algorithm named greedy-EF to solve this problem more effectively. More specially, greedy-EF uses an aggregate function to evaluate the QoS conditions for each service instance, and a hop-by-hop service selection approach to explore the proper service path. Simulations show that greedy-EF algorithm can achieve desired QoS assurances as well as load balancing in multimedia service overlay networks.

The unstructured peer-to-peer (P2P) systems usually use a "blind search" method to find the requested data object by propagating a query to a number of peers randomly. In order to increase the success rate of blind search, replication techniques are widely used in these systems. Most P2P systems replicate the most frequently accessed data objects to improve system performance. However, existing replication strategies cannot answer the question that how many replicas of an object should be kept in the P2P system. If an object is replicated excessively, it inevitably will affect the average efficiency of a replica, which will decrease the whole search performance. This paper addresses the issue of finding the proper number of replicas for an object according to its query rate. In this paper, we firstly investigate the precise relation among success rate, the allocation of replicas and query rate. Then we propose an approach of the allocation of copies to optimize the success rate. As a benchmark, our result offers a new understanding of replication.

Abstract In a Grid‐based services system facing a large number of requests with different services and profits significance, there is always a trade‐off between the system profits and the Quality of Service (QoS). In such systems, admission control plays an important role: the system has to employ a proper strategy to make admission control decisions and reserve resources for the coming requests thus to achieve greater profits without violating the QoS of the requests already admitted. In this paper, we introduce three essential admission control strategies with threshold on resource reservation and a newly proposed strategy with layered threshold. Through comprehensive theoretical analyses and extensive simulations, we demonstrate that the strategy with layered threshold is more efficient and flexible than the existing strategies for Grid‐based multimedia services systems. Copyright © 2006 John Wiley & Sons, Ltd.