Visual reinforcement learning (RL) suffers from poor sample efficiency due to high-dimensional observations in complex tasks. While existing works have shown that vision-language models (VLMs) can assist RL, they often focus on knowledge distillation from the VLM to RL, overlooking the potential of RL-generated interaction data to enhance the VLM. To address this, we propose COVR, a collaborative optimization framework that enables the mutual enhancement of the VLM and RL policies. Specifically, COVR fine-tunes the VLM with RL-generated data to enhance the semantic reasoning ability consistent with the target task, and uses the enhanced VLM to further guide policy learning via action priors. To improve fine-tuning efficiency, we introduce two key modules: (1) an Exploration-Driven Dynamic Filter module that preserves valuable exploration samples using adaptive thresholds based on the degree of exploration, and (2) a Return-Aware Adaptive Loss Weight module that improves the stability of training by quantifying the inconsistency of sampling actions via return signals of RL. We further design a progressive fine-tuning strategy to reduce resource consumption. Extensive experiments show that COVR achieves strong performance across various challenging visual control tasks.

This paper proposes a two-stage text-to-floorplan generation framework that combines the reasoning capability of Large Language Models (LLMs) with the generative power of diffusion models. In the first stage, we leverage a Chain-of-Thought (CoT) prompting strategy to guide an LLM in generating an initial layout, Layout-Init, from natural language descriptions, which ensures a user-friendly and intuitive design process. However, Layout-Init may lack precise geometric alignment and fine-grained structural details due to the inherent limitations of LLMs. To address this, in the second stage we propose a Dual-Noise Prior-Preserved Diffusion (DNPP-Diffusion) model to refine Layout-Init into a final floorplan that better adheres to physical constraints and user requirements. By combining LLMs and a dedicated refining model, our approach is able to generate high-quality floorplans without requiring large-scale domain-specific training data. Experimental results demonstrate its advantages in comparison with state of the art methods, and validate its effectiveness in home design applications.

Existing end-to-end methods for steering angle prediction (SAP) primarily rely on RGB imagery from conventional cameras as input; however, they suffer from limitations such as poor performance in low-light conditions and motion blur. Recently, event cameras have garnered attention as complementary to RGB imagery, providing advantages such as high dynamic range and low latency. Nevertheless, earlier SAP methods that integrate event and RGB data may not fully exploit the spatio-temporal characteristics of events, resulting in performance degradation in low-light scenarios affected by noise interference. To address this limitation, we present a novel spatiotemporal-aware event-RGB fusion method for SAP, referred to as SERF, which aims to enhance the accuracy of event-based SAP. Specifically, SERF introduces three key components: 1) An innovative multi-layer Interaction Module based on attention mechanisms to fuse the multi-frame data, enabling more fine-grained feature processing; 2) a dynamic spatiotemporal mask mechanism, focusing RGB’s attention on spatially proximate events while diminishing the influence of temporally distant events, thereby reducing the impact of noise; and 3) a Memory Module that utilizes learnable tokens to accumulate essential latent fusion features through dynamic feature consolidation. Extensive experiments conducted on a variety of real-world and simulated datasets demonstrate the superior performance of SERF compared to the state-of-the-art methods. The experiments also validate the advantages of SERF in terms of inference performance, meeting the real-time requirements for actual deployment.

Vehicle-to-infrastructure (V2I) cooperative perception systems can enhance the sensing abilities of autonomous vehicles. Existing V2I solutions often consider LiDARs devices instead of cameras, the most prevalent sensors with low cost and wide installation. In addition, a major challenge that has been underexplored is the time asynchrony between image frames from different sources. This asynchrony arises because of clock differences, varying times involved in data processing and transmission, causing uncertain delays that complicate data alignment and potentially reduce perception accuracy. We propose BEVSync, a camera-based V2I cooperative perception system that adaptively aligns frames from the ego-vehicle and infrastructure by compensating for motion deviations. Specifically, we develop an extractor-compensator model to extract and predict perceptual features using historical frames, thereby smoothing out the data misalignment. Experiments on the real-world dataset DAIR-V2X show that our approach surpasses existing methods in terms of performance and robustness.

Occupancy networks aim to reconstruct the surroundings with occupied semantic voxels. However, frequent object occlusions often occur in dynamic real-world scenarios, which cannot be captured by independent frames. Most existing occupancy networks generate results without explicitly considering past occupancy states and continuous visual changes over time, limiting their temporal accuracy. We tackle it by treating the task from a new continuous updating perspective, which considers historical data and continuous motion clues. We propose a new approach termed Continuous Motion clue exploitation for Occupancy Prediction (CMOP), which incorporates three key designs: (i) Propagator: which forecasts future occupancy states based on historical data; (ii) Tracker: which updates the occupancy on a per-frame basis using dynamic visual motion information; and (iii) Fuser: which aggregates results from the Propagator and Tracker into more robust and accurate occupancy results. Experiments on several benchmarks demonstrate that CMOP outperforms state-of-the-art baselines.

Vision-based Reinforcement Learning (VRL) attempts to establish associations between visual inputs and optimal actions through interactions with the environment. Given the high-dimensional and complex nature of visual data, it becomes essential to learn a policy based on high-quality state representation. To this end, existing VRL methods primarily rely on interaction-collected data, combined with selfsupervised auxiliary tasks. However, two key challenges remain: limited data samples and a lack of task-relevant semantic constraints. To tackle these challenges, we propose DGC, a method that Distills Guidance from Visual Language Models (VLMs) alongside self-supervised learning into a Compact VRL agent. Notably, we leverage the state representation capabilities of VLMs, rather than their decision-making abilities. Within DGC, a novel promptingreasoning pipeline is designed to convert historical observations and actions into usable supervision signals, enabling semantic understanding within the compact visual encoder. By leveraging these distilled semantic representations, the VRL agent achieves significant improvements in sample efficiency. Extensive experiments on the Carla benchmark demonstrate our state-of-the-art performance.

Graph Neural Networks (GNNs) have shown remarkable success in learning from graph-structured data. However, their application to directed graphs (digraphs) presents unique challenges, primarily due to the inherent asymmetry in node relationships. Traditional GNNs are adept at capturing unidirectional relations but fall short in encoding the mutual path dependencies between nodes, such as asymmetrical shortest paths typically found in digraphs. Recognizing this gap, we introduce Commute Graph Neural Networks (CGNN), an approach that seamlessly integrates node-wise commute time into the message passing scheme. The cornerstone of CGNN is an efficient method for computing commute time using a newly formulated digraph Laplacian. Commute time is then integrated into the neighborhood aggregation process, with neighbor contributions weighted according to their respective commute time to the central node in each layer. It enables CGNN to directly capture the mutual, asymmetric relationships in digraphs. Extensive experiments on 8 benchmarking datasets confirm the superiority of CGNN against 13 state-of-the-art methods.

The task of live video analytics relies on real-time object tracking that typically involves computationally expensive deep neural network (DNN) models. In practice, it has become essential to process video data on edge devices deployed near the cameras. However, these edge devices often have very limited computing resources and thus suffer from poor tracking accuracy. Through a measurement study, we identify three major factors contributing to the performance issue: outdated detection results, tracking error accumulation, and ignorance of new objects. We introduce a novel approach, called Predict & Correct based Tracking, orPCTrack, to systematically address these problems. Our design incorporates three innovative components: 1) a Predictive Detection Propagator that rapidly updates outdated object bounding boxes to match the current frame through a lightweight prediction model; 2) a Frame Difference Corrector that refines the object bounding boxes based on frame difference information; and 3) a New Object Detector that efficiently discovers newly appearing objects during tracking. Experimental results show that our approach achieves remarkable accuracy improvements, ranging from 19.4% to 34.7%, across diverse traffic scenarios, compared to state of the art methods.

Modern intelligent vehicles (IVs) are equipped with a variety of sensors and communication modules, empowering Advanced Driver Assistance Systems (ADAS) and enabling inter-vehicle connectivity. This paper focuses on multi-vehicle cooperative perception, with a primary objective of achieving low latency. The task involves nearby cooperative vehicles sending their camera data to an edge server, which then merges the local views to create a global traffic view. While multi-camera perception has been actively researched, existing solutions often rely on deep learning models, resulting in excessive processing latency. In contrast, we propose leveraging thestate estimationtechnique from the robotics field for this task. We explicitly model and solve for the system state, addressing additional challenges brought by object mobility and vision obstruction. Furthermore, we introduce aprogressive state estimationpipeline to further accelerate system state notifications, supported by a motion prediction method that optimizes position accuracy and perception smoothness. Experimental results demonstrate the superiority of our approach over the deep learning method, with 12.0 × to 27.4 × reductions in server processing delay, while maintaining mean absolute errors below 1 m.

Multi-agent trajectory prediction is essential in autonomous driving, risk avoidance, and traffic flow control. However, the heterogeneous traffic density on interactions, which caused by physical laws, social norms and so on, is often overlooked in existing methods. When the density varies, the number of agents involved in interactions and the corresponding interaction probability change dynami-cally. To tackle this issue, we propose a new method, called Density-Adaptive Model based on Motif Matrix for Multi-Agent Trajectory Prediction (DAMM), to gain insights into multi-agent systems. Here we leverage the motif matrix to represent dynamic connectivity in a higher-order pattern, and distill the interaction information from the perspectives of the spatial and the temporal dimensions. Specifically, in spatial dimension, we utilize multi-scale feature fusion to adaptively select the optimal range of neighbors participating in interactions for each time slot. In temporal dimension, we extract the temporal interaction features and adapt a pyramidal pooling layer to generate the interaction probability for each agent. Experimental results demonstrate that our approach surpasses state-of-the-art methods on autonomous driving dataset.

We explore visual reinforcement learning (RL) using two complementary visual modalities: frame-based RGB cam-era and event-based Dynamic Vision Sensor (DVS). Ex-isting multi-modality visual RL methods often encounter challenges in effectively extracting task-relevant information from multiple modalities while suppressing the in-creased noise, only using indirect reward signals instead of pixel-level supervision. To tackle this, we propose a Decomposed Multi-Modality Representation (DMR) framework for visual RL. It explicitly decomposes the inputs into three distinct components: combined task-relevant features (co-features), RGB-specific noise, and DVS-specific noise. The co-features represent the full information from both modalities that is relevant to the RL task; the two noise components, each constrained by a data reconstruction loss to avoid information leak, are contrasted with the co-features to maximize their difference. Extensive experiments demonstrate that, by explicitly separating the different types of information, our approach achieves substan-tially improved policy performance compared to state-of-the-art approaches.

Existing investigations on action understanding have made noteworthy advancements by treating activities as holistic events occurring in videos. However, these investigations have limited ability to comprehensively extract and represent human experiential knowledge, which hampers various practical applications, such as robotics and human-computer interaction. We argue that human actions can be better understood as hierarchical compositions of multiple interactive objects and atomic actions with spatio-temporal relations. To this end, we propose a hierarchical understanding framework for home actions, which decomposes a single holistic action into multiple quintuples of. Within this framework, we introduce a two-stage network architecture that leverages multiple prior knowledge in both implicit and explicit ways to facilitate mutual learning within quintuples. In particular, we fully exploit statistical knowledge to enhance the inference of data-driven visual model. Experiments validate the effectiveness of our proposed method. This is also the winning solution for HOMAGE Competition @ ActivityNet Challenge in CVPR 2022 and our brief oral representation is available at https://youtu.be/KK3SPK6iueE?si=hrFZzSABNyrrL6jF&t=1727.

Label imbalance and homophily-heterophily mixture are the fundamental problems encountered when applying Graph Neural Networks (GNNs) to Graph Fraud Detection (GFD) tasks. Existing GNN-based GFD models are designed to augment graph structure to accommodate the inductive bias of GNNs towards homophily, by excluding heterophilic neighbors during message passing. In our work, we argue that the key to applying GNNs for GFD is not to exclude but to {\em distinguish} neighbors with different labels. Grounded in this perspective, we introduce Partitioning Message Passing (PMP), an intuitive yet effective message passing paradigm expressly crafted for GFD. Specifically, in the neighbor aggregation stage of PMP, neighbors with different classes are aggregated with distinct node-specific aggregation functions. By this means, the center node can adaptively adjust the information aggregated from its heterophilic and homophilic neighbors, thus avoiding the model gradient being dominated by benign nodes which occupy the majority of the population. We theoretically establish a connection between the spatial formulation of PMP and spectral analysis to characterize that PMP operates an adaptive node-specific spectral graph filter, which demonstrates the capability of PMP to handle heterophily-homophily mixed graphs. Extensive experimental results show that PMP can significantly boost the performance on GFD tasks.

In visual SLAM (VSLAM) systems, loop closure plays a crucial role in reducing accumulated errors. However, VSLAM systems relying on low-level visual features often suffer from the problem of perceptual confusion in repetitive environments, where scenes in different locations are incorrectly identified as the same. Existing work has attempted to introduce object-level features or artificial landmarks. The former approach struggles to distinguish visually similar but different objects, while the latter is both time-consuming and labor-intensive. This paper introduces a novel loop closure detection method that leverages pretrained AI foundation models to extract rich semantic information about specific types of objects (e.g., door numbers), referred to as semantic anchors, that help to distinguish similar scenes better. In settings such as office buildings, hotels, and warehouses, this approach helps to improve the robustness of loop closure detection. We validate the effectiveness of our method through experiments conducted in both simulated and real-world environments.

In autonomous driving, cooperative perception through vehicle-to-vehicle (V2V) communication is considered crucial for enhancing traffic safety and efficiency. However, existing methods often simplify the handling of perception data from multiple vehicles. In these approaches, the egovehicle aggregates observations from all neighboring connected cooperative vehicles (CCV), without considering the interactions between the vehicles or making differentiated use of the acquired sensing data. This approach can result in suboptimal performance due to the increase of noise and large transmission delay. In this paper, we introduce a novel approach to cooperative perception. By fusing both the road topology and trajectory histories of neighboring CCVs, our model learns an interaction score for each CCV. These scores prioritize vehicles that are most relevant to the current driving scenario, offering valuable guidance for selective fusion of sensor data, thereby enhancing driving decision-making. The proposed method is validated through experiments conducted on the CARLA simulator. Results demonstrate that our approach surpasses existing methods in terms of performance and robustness.

A challenging task in embodied artificial intelligence is enabling the robot to carry out a navigational task following natural language instruction. In the task, the navigator needs to understand objects, directions, as well as room types, which serve as landmarks for navigation. Although it is easy to encode objects and directions with an external encoder like an object detector, current navigators struggle to encode room type information properly due to the low accuracy offered by existing classifiers. This inadequacy poses confusion that navigators find difficult to overcome. Even humans may sometimes fail to determine the exact type of a room since multiple room types may exist in one panorama. To mitigate this problem, we propose to encode room type information in a prompt manner. Specifically, we first establish multi-modal, learnable prompt pools containing knowledge of room types. By querying the prompt pools, the navigator can obtain room-type prompts of the current view, and incorporate them into the navigator using a prompt-based learning method. Experimental results on the REVERIE, R2R and SOON datasets demonstrate the effectiveness of our approach.

Graph neural networks (GNNs) have been successful in a variety of graph-based applications. Recently, it is shown that capturing long-range relationships between nodes helps improve the performance of GNNs. The phenomenon is mostly confirmed in a supervised learning setting. In this article, inspired by contrastive learning (CL), we propose an unsupervised learning pipeline, in which different types of long-range similarity information are injected into the GNN model in an efficient way. We reconstruct the original graph in feature and topology spaces to generate three augmented views. During training, our model alternately picks an augmented view, and maximizes an agreement between the representations of the view and the original graph. Importantly, we identify the issue of diminishing utility of the augmented views as the model gradually learns useful information from the views. Hence, we propose a view update scheme that adaptively adjusts the augmented views, so that the views can continue to provide new information that helps with CL. The updated augmented views and the original graph are jointly used to train a shared GNN encoder by optimizing an efficient channel-level contrastive objective. We conduct extensive experiments on six assortative graphs and three disassortative graphs, which demonstrate the effectiveness of our method.

Human-object interaction (HOI) detection aims to interpret the interactions of human-object pairs. Existing methods adopt a one-step reasoning paradigm that simultaneously outputs multi-label results for all HOI pairs without distinguishing difficulties. However, there are significant variations among HOI pairs in the same image, making their performance degrade in challenging situations. In this paper, we argue that the model should prioritize hard samples after inferring easy ones, and hard samples can benefit from easy ones. To this end, we propose a novel Multi-step Reasoning Network that progressively learns from easy to hard samples. In particular, an Easy-to-Hard Learning Block is introduced to enhance the representation of hard HOI pairs by prior associations. Additionally, we propose a Multi-step Reasoning Probability Transfer mechanism to enhance multi-label interaction classifications, which leverages cognitive associations and semantic dependencies. Extensive experiments demonstrate that our method outperforms other state-of-the-art on two challenging benchmark datasets.

For autonomous driving, one of the major challenges is to predict pedestrian crossing intention in ego-view. Pedestrian intention depends not only on their intrinsic goals but also on the stimulation of surrounding traffic elements. Considering the influence of other traffic elements on pedestrian intention, recent work introduced more traffic element information into the model to successfully improve performance. However, it is still difficult to effectively capture and fully exploit the potential dynamic spatio-temporal interactions among the target pedestrian and its surrounding traffic elements for accurate reasoning. In this work, inspired by neuroscience that human drivers tend to make continuous sensory-motor driving decisions by progressive visual stimulation, we propose a model termed Progressive Interaction Transformer (PIT) for pedestrian crossing intention prediction. Local pedestrian, global environment, and ego-vehicle motion are considered simultaneously in the proposed PIT. In particular, the temporal fusion block and self-attention mechanism are introduced to jointly and progressively model the dynamic spatio-temporal interactions among the three parties, allowing it to capture richer information and make prediction in a similar way to human drivers. Experimental results demonstrate that PIT achieves higher performance compared with other state-of-the-arts and preserves real-time inference.

This paper presents CurveLight, an accurate and practical light positioning system. In CurveLight, the signal transmitter includes an infrared LED, covered by a hemispherical and rotatable shade, and the receiver detects the light signals with a photosensitive diode. When the shade is rotating, the transmitter generates a unique sequence of light signals for each point in the covered space. The main novelty of the system design is a set of curves that define different regions, either transparent or translucent, on the shade. The regions allow the light signals to create patterns from which the receiver can calculate its angles with respect to the transmitter. We design the curves in such a way that the angular information is most robust to errors caused by signal noise and motor jitters. Moreover, the shade is divided into multiple sectors, each providing independent positioning function, so as to maximize the position update rate. Experiments in various environments show that the system achieves 2-3 cm accuracy on average, with a 36 Hz update rate with a single transmitter. We present a product quality implementation of the system, and report the deployment experience in real-world environments, including autonomous driving and robotics navigation. CurveLight consistently offers centimeter-level accuracy and low latency, serving as a key component of the hybrid navigation solution for real systems in challenging scenarios.

We consider graph representation learning in an unsupervised manner. Graph neural networks use neighborhood aggregation as a core component that results in feature smoothing among nodes in proximity. While successful in various prediction tasks, such a paradigm falls short of capturing nodes' similarities over a long distance, which proves to be important for high-quality learning. To tackle this problem, we strengthen the graph with three types of additional graph views, in which each node is directly linked to a set of nodes with the highest similarity in terms of node features, neighborhood features or local structures. Not restricted by connectivity in the original graph, the generated views provide new and complementary perspectives from which to look at the relationship between nodes. Inspired by the recent success of contrastive learning approaches, we propose a self-supervised method that aims to learn node representations by maximizing the agreement between representations across generated views and the original graph, without the requirement of any label information. We also propose a channel-level contrast approach that greatly reduces computation cost. Extensive experiments on six assortative graphs and three disassortative graphs demonstrate the effectiveness of our approach.

We consider the graph similarity computation (GSC) task based on graph edit distance (GED) estimation. State-of-the-art methods treat GSC as a learning-based prediction task using Graph Neural Networks (GNNs). To capture fine-grained interactions between pair-wise graphs, these methods mostly contain a node-level matching module in the end-to-end learning pipeline, which causes high computational costs in both the training and inference stages. We show that the expensive node-to-node matching module is not necessary for GSC, and high-quality learning can be attained with a simple yet powerful regularization technique, which we call the Alignment Regularization (AReg). In the training stage, the AReg term imposes a node-graph correspondence constraint on the GNN encoder. In the inference stage, the graph-level representations learned by the GNN encoder are directly used to compute the similarity score without using AReg again to speed up inference. We further propose a multi-scale GED discriminator to enhance the expressive ability of the learned representations. Extensive experiments on real-world datasets demonstrate the effectiveness, efficiency and transferability of our approach.

This paper presents CurveLight, an accurate and practical light positioning system. In CurveLight, the signal transmitter includes an infrared LED, covered by a hemispherical and rotatable shade, and the receiver detects the light signals with a photosensitive diode. When the shade is rotating, the transmitter generates a unique sequence of light signals for each point in the covered space. The main novelty of the system design is a set of curves that define different regions, either transparent or translucent, on the shade. The regions allow the light signals to create patterns from which the receiver can calculate its angles with respect to the transmitter. We design the curves in such a way that the angular information is most robust to errors caused by signal noise and motor jitters. Moreover, the shade is divided into multiple sectors, each providing independent positioning function, so as to maximize the position update rate. Experiments in various environments show that the system achieves 2-3 cm accuracy on average, with a 36 Hz update rate with a single transmitter. We present a product quality implementation of the system, and report the deployment experience in real-world environments, including autonomous driving and robotics navigation. CurveLight consistently offers centimeter-level accuracy and low latency, serving as a key component of the hybrid navigation solution for real systems in challenging scenarios.

Indoor-outdoor (IO) detection provides very useful hints for a mobile device to perform context-aware services. To that end, GPS presents a viable solution by relating a device's IO status with its positioning performance, which depends on the device's exposure to the open sky. This approach, however, is prohibitively expensive in terms of energy consumption and response time. Recent work has thus been focused on exploiting low-energy sensors such as light, cellular, and magnetic sensors to infer the IO status indirectly, at the cost of reduced adaptability or manual labeling effort. In this article, we propose a new method to address these problems. Our method, called SatProbe, reverts to the GPS approach for its directness and robustness, but avoids its drawback by extracting only the number of visible satellites from the raw GPS data, instead of going through extensive computation to obtain a final position. This metric provides a clear indicator of the IO status, yet can be obtained with great efficiency. Experiments on 79 raw GPS traces with 2595 detection points across a variety of environments show that SatProbe produces a 14.2 percent improvement in detection accuracy, with a 98.8 percent reduction in both energy use and detection time, in comparison with the standard GPS method.

The past few years have witnessed a rapid growth of stationless bike sharing services. The service allows the bikes to be dropped off freely and to be found through GPS localization. In practice, the bikes are often parked in close proximity to buildings, where GPS accuracy suffers, making bike search a challenging task. This article proposes a novel approach to addressing this problem. Inspired by multi-antenna systems, our method tries to collect GPS signals from multiple distributed bikes, by organizing a group of bikes into a network, called a BikeGPS network. Formed by pedestrian users who opportunistically measure inter-bike distance via radio sensing and step tracking, the generated network permits one to map all the nodes’ satellite range measurements into a single lead node ’s view. By considering both signal and geometry properties of satellite raw measurements, and using an asynchronous coarse time navigation algorithm, the lead node can accurately derive the locations of all the network nodes. Experiments in real-world scenarios show that BikeGPS significantly improves the localization performance, in terms of both accuracy and solution availability, compared with the naive GPS approach and a high-level cooperative localization method.

The past few years have seen a surge of stationless bike sharing services in many modern cities. The service allows the bikes to be dropped off freely, and to be found through GPS localization. For maximum convenience, the bikes are often parked in close proximity to the buildings, where GPS may perform poorly, making bike search a challenging task. This paper proposes a novel approach to addressing this problem. Inspired by multi-antenna systems, our method tries to collect GPS signals from multiple distributed bikes, by organizing a group of bikes into a network, called the BikeGPS. Formed by pedestrian users who opportunistically measure interbike distance via radio sensing and step tracking, the generated network permits one to map all the nodes' satellite range measurements into a single lead node's view. By considering both signal and geometry properties of satellite raw measurements, and using an asynchronous coarse time navigation algorithm, the lead node can accurately derive the locations of all the network nodes. Real-world experiments show that BikeGPS significantly improves the localization performance, in terms of both accuracy and solution availability, compared with the naive GPS approach and a high-level cooperative localization method.

Indoor-outdoor (IO) detection provides very useful hints for a mobile device to perform context-aware services. To that end, GPS presents a viable solution by relating a device's IO status with its positioning performance, which depends on the device's exposure to the open sky. This approach, however, is prohibitively expensive in terms of energy consumption and response time. Recent work has thus been focused on exploiting low-energy sensors such as light, cellular, and magnetic sensors to infer the IO status indirectly, at the cost of reduced adaptability or explicit user involvement. In this paper, we propose an improving solution to this problem. Our method, called SatProbe, reverts to the GPS approach for its directness and robustness, but avoids its drawback by extracting only the number of visible satellites from the raw GPS data, instead of going through extensive computation to obtain a final position. This metric provides a clear indicator of the IO status, yet can be obtained with great efficiency. Experiments on 79 raw GPS traces with 2595 detection points across a variety of environments show that SatProbe produces higher detection accuracy than previous solutions, with more than an order of magnitude reductions in energy consumption and detection time.

Stationless bike sharing systems allow the bikes to be dropped off freely and to be found through GPS localization. Such flexibility has made it highly popular in an increasing number of cities. However, GPS often performs poorly in urban areas with dense high-rise building, making bikes search a challenging task. This paper proposes a novel cooperative GPS approach to address the problem. The method first organizes a group of shared bikes into a network, called a BikeNet, in a crowdsourcing manner. Then the constructed network maps all the nodes' GPS raw measurements to a lead node's view, to determine an accurate GPS location for each node. Experiment results show that BikeNet improves the localization accuracy by 2.96x and 4.8x, compared with the classic GPS method.

For large-scale graph analysis on a single PC, asynchronous processing methods are known to converge more quickly than the synchronous approach, because of more efficient propagation of vertices state. However, current asynchronous methods are still very suboptimal in propagating state across different graph partitions. This presents a bottleneck for cross-partition state update and slows down the convergence of the processing task. To tackle this problem, we propose a new method, named the HotGraph, to faster graph processing by extracting a backbone structure, called hot graph, that spans all the partitions of the original graph. With this approach, most cross-partition state propagations in traditional solutions now take place within only a few hot graph partitions, thus removing the cross-partition bottleneck. We also develop a partition scheduling algorithm to maximize the hot graph's effectiveness by keeping it in memory and assigning it the highest priority for processing as much as possible. A forward and backward sweeping execution strategy is then proposed to further accelerate the convergence. Experimental results show that HotGraph can reduce the number of vertex state updates processed by 51.5 percent, compared with state-of-the-art schemes. Applying our optimizations further reduces this number by 72.6 percent and the execution time by 80.8 percent.

Social network analysis is used to extract features of human communities and proves to be very instrumental in a variety of scientific domains. The dataset of a social network is often so large that a cloud data analysis service, in which the computation is performed on a parallel platform in the could, becomes a good choice for researchers not experienced in parallel programming. In the cloud, a primary challenge to efficient data analysis is the computation and communication skew (i.e., load imbalance) among computers caused by humanity's group behavior (e.g., bandwagon effect). Traditional load balancing techniques either require significant effort to re-balance loads on the nodes, or cannot well cope with stragglers. In this paper, we propose a general straggler-aware execution approach, SAE, to support the analysis service in the cloud. It offers a novel computational decomposition method that factors straggling feature extraction processes into more fine-grained sub-processes, which are then distributed over clusters of computers for parallel execution. Experimental results show that SAE can speed up the analysis by up to 1.77 times compared with state-of-the-art solutions.

Cache pollution, by which weak-locality data unduly replaces strong-locality data, may notably degrade application performance in a shared-cache multicore machine. This paper presents NightWatch, a cache management subsystem that provides general, transparent and low-overhead pollution control to applications. NightWatch is based on the observation that data within the same memory chunk or chunks within the same allocation context often share similar locality property. NightWatch embodies this observation by online monitoring current cache locality to predict future behavior and restricting potential cache polluters proactively. We have integrated NightWatch into two popular allocators, tcmalloc and ptmalloc2. Experiments with SPEC CPU2006 show that NightWatch improves application performance by up to 45 percent (18 percent on average), with an average monitoring overhead of 0.57 percent (up to 3.02 percent).

In cloud gaming systems, the game program runs at servers in the cloud, while clients access game services by sending input events to the servers and receiving game scenes via video streaming. In this paradigm, servers are responsible for all performance-intensive operations, and thus suffer from poor scalability. An alternative paradigm is called graphics streaming, in which graphics commands and data are offloaded to the clients for local rendering, thereby mitigating the server's burden and allowing more concurrent game sessions. Unfortunately, this approach is bandwidth-consuming, due to large amounts of graphic commands and geometry data. In this paper, we present LiveRender, an open-source gaming system that remedies the problem by implementing a suite of bandwidth optimization techniques including intraframe compression, interframe compression, and caching, establishing what we call compressed graphics streaming. Experiments results show that the new approach is able to reduce bandwidth consumption by 52%-73% compared to raw graphics streaming, with no perceptible difference in video quality and reduced response delay. Compared to the video streaming approach, LiveRender achieves a traffic reduction of 40%-90% with even improved video quality and substantially smaller response delay, while enabling higher concurrency at the server.

Scalable routing for large-scale wireless networks needs to find near shortest paths with low state on each node, preferably sublinear with the network size. Two approaches are considered promising toward this goal: compact routing and geometric routing (geo-routing). To date, the two lines of research have been largely independent, perhaps because of the distinct principles they follow. In particular, it remains unclear how they compare to each other in the worst case, despite extensive experimental results showing the superiority of one or another in particular cases. We develop a novel Trap Array topology model that provides a unified framework to uncover the limiting behavior of 10 representative geo-routing algorithms. We present a series of new theoretical results, in comparison to the performance of compact routing as a baseline. In light of their pros and cons, we further design a Compact Geometric Routing (CGR) algorithm that attempts to leverage the benefits of both approaches. Theoretical analysis and simulations show the advantages of the topology model and the algorithm.

This article presents a Light Intensity--based Positioning System (LIPS) for indoor environments. The system uses off-the-shelf light-emitting diode lamps as signal sources and light sensors as signal receivers. The design is inspired by the observation that a light sensor has deterministic sensitivity to both the distance and incident angle of a light signal, an under-utilized feature of photodiodes now widely found on mobile devices. We develop a stable and accurate light intensity model to capture the phenomenon, based on which a new positioning principle, Multi-Face Light Positioning , is established that uses three collocated sensors to uniquely determine the receiver’s position, assuming merely a single source of light. We have implemented a prototype on both dedicated embedded systems and smartphones. Experimental results show average positioning accuracy within 0.4m across different environments, with high stability against interferences from obstacles, ambient lights, temperature variation, and so on.

Recent pioneer work has shown that packet receptions on adjacent links are correlated, which contradicts the long held assumption that wireless links are statistically independent. Since wireless link correlation affects a wide range of protocol designs, it is essential to quantify the impact generically. In particular, this paper focuses on a unified transmission cost metric for diversity-based routing schemes, including opportunistic routing, network coding, and hybrid routing. This paper covers both unicast and broadcast. Compared with the legacy metrics, our metric provides a direct and accurate estimation of the transmission cost in the presence of link correlation. The new metric helps a wide range of routing algorithms determine when they can benefit from reception diversity, and how to maximize the benefit, at negligible costs. We evaluate the metric on one 802.11 test bed and three 802.15.4 test beds running TelosB, MICAz, and GreenOrbs nodes. The experimental results show that our metric 1) reduces 92% and 94% of the estimation error of the transmission cost in unicast and broadcast and 2) outperforms the link independent metric in both unicast and broadcast applications.

This paper presents SpinLight, an indoor positioning system that uses infrared LED lamps as signal transmitters, and light sensors as receivers. The main idea is to divide the space into spatial beams originating from the light source, and identify each beam with a unique timed sequence of light signals. This sequence is created by a coded shade that covers and rotates around the LED, blocking the light or allowing it to pass through according to pre-defined patterns. The receiver, equipped with a light sensor, is able to determine its spatial beam by detecting the light signals, followed by optimization schemes to refine its location within that beam. We present both 2D and 3D localization designs, demonstrated by a prototype implementation. Experiments show that SpinLight produces a median location error of 3.8 cm, with a 95th percentile of 6.8 cm. The receiver design is very low power and thus can operate for months to years from a button coin battery.

Efficient sensor network design requires a full understanding of the geometric environment in which sensor nodes are deployed. In practice, a large-scale sensor network often has a complex and irregular topology, possibly containing obstacles/holes. Convex network partitioning, also known as convex segmentation, is a technique to divide a network into convex regions in which traditional algorithms designed for a simple network geometry can be applied. Existing segmentation algorithms heavily depend on concave node detection, or sink extraction from the median axis/skeleton, resulting in sensitivity of performance to network boundary noise. Furthermore, since they rely on the network's 2-D geometric properties, they do not work for 3-D cases. This paper presents a novel segmentation approach based on Morse function, bringing together the notions of convex components and the Reeb graph of a network. The segmentation is realized by a distributed and scalable algorithm, named CONSEL, for CONnectivity-based SEgmentation in Large-scale 2-D/3-D sensor networks. In CONSEL, several boundary nodes first flood the network to construct the Reeb graph. The ordinary nodes then compute mutex pairs locally, generating a coarse segmentation. Next, neighboring regions that are not mutex pairs are merged together. Finally, by ignoring mutex pairs that lead to small concavity, we provide an approximate convex decomposition. CONSEL has a number of advantages over previous solutions: 1) it works for both 2-D and 3-D sensor networks; 2) it uses merely network connectivity information; 3) it guarantees a bound for the generated regions' deviation from convexity. We further propose to integrate network segmentation with existing applications that are oriented to simple network geometry. Extensive simulations show the efficacy of CONSEL in segmenting networks and in improving the performance of two applications: geographic routing and connectivity-based localization.

Recent work has shown that wireless links are not independent, and that transmissions from a transmitter to multiple receivers are correlated. This finding has profound implications for the performance of network protocols such as broadcast, multicast, opportunistic routing, and network coding. In this paper, we show how link correlation can significantly impact broadcast. We present the design and implementation of CorLayer, a general supporting layer for energy-efficient reliable broadcast that carefully blacklists certain poorly correlated wireless links. The design uses only one-hop information, which makes it work in a fully distributed manner and introduces minimal communication overhead. The highlight of our work is CorLayer's broad applicability and effectiveness. We integrate CorLayer transparently with 16 state-of-the-art broadcast protocols specified in 13 publications on three physical testbeds running TelosB, MICAz, and GreenOrbs nodes, respectively. The experimental results show that CorLayer significantly improves energy efficiency across a wide spectrum of broadcast protocols and that the total number of packet transmissions can be reduced consistently by 47% on average.

Large-scale behavioral simulations are widely used to study real-world multi-agent systems. Such programs normally run in discrete time-steps or ticks, with simulated space decomposed into domains that are distributed over a set of workers to achieve parallelism. A distinguishing feature of behavioral simulations is their frequent and high-volume group migration, the phenomenon in which simulated objects traverse domains in groups at massive scale in each tick. This results in continual and significant load imbalance among domains. To tackle this problem, traditional load balancing approaches either require excessive load re-profiling and redistribution, which lead to high computation/communication costs, or perform poorly because their statically partitioned data domains cannot reflect load changes brought by group migration. In this paper, we propose an effective and low-cost load balancing scheme, named Inc-part, based on a key observation that an object is unlikely to move a long distance (across many domains) within a single tick. This localized mobility property allows one to efficiently estimate the load of a dynamic domain incrementally, based on merely the load changes occurring in its neighborhood. The domains experiencing significant load changes are then partitioned or merged, and redistributed to redress load imbalance among the workers. Experiments on a 64-node (1,024-core) platform show that Inc-part can attain excellent load balance with dramatically lowered costs compared to state-of-the-art solutions.

Geometric routing or geo-routing has been shown as a promising approach to scalable routing in sensor networks. Despite its success in 2-D networks, very few designs are available for 3-D networks that can ensure short routes using only small per-node state, without incurring high load imbalance on the nodes. In this paper, we propose a novel addressing and routing scheme, i.e., OnionMap, for 3-D sensor networks that achieve the above goals, using solely connectivity information and at a linear message cost. The key idea is to decompose a 3-D network into a set of connected layers, which are then mapped to a set of concentric sphere structures (similar to an onion). On each sphere, a discrete Ricci flow method is used to assign each node a set of coordinates that permits purely greedy routing within that sphere; across the different spheres, a layer alignment algorithm helps rotate and scale the spheres, to form a coherent global coordinate system that guides global routing. Theoretical analysis and simulation show OnionMap's advantages over state-of-the-art solutions in path stretch, per-node storage, and load balance.

In cloud gaming systems, the game program runs at servers in the cloud, while clients access game services by sending input events to the servers and receiving game scenes via video streaming. In this paradigm, servers are responsible for all performance-intensive operations, and thus suffer from poor scalability. An alternative paradigm is called graphics streaming, in which graphics commands and data are offloaded to the clients for local rendering, thereby mitigating the server's burden and allowing more concurrent game sessions. Unfortunately, this approach is bandwidth consuming, due to large amounts of graphic commands and geometry data. In this paper, we present LiveRender, an open source gaming system that remedies the problem by implementing a suite of bandwidth optimization techniques including intra-frame compression, inter-frame compression, and caching, establishing what we call compressed graphics streaming. Experiments results show that the new approach is able to reduce bandwidth consumption by 52-73% compared to raw graphics streaming, with no perceptible difference in video quality and reduced response delay. Compared with the video streaming approach, LiveRender achieves a traffic reduction of 40-90% with even improved video quality and substantially smaller response delay, while enabling higher concurrency at the server.

When a sensor network grows large, or when its topology becomes complex (e.g., containing many holes), network algorithms designed with a smaller or simpler setting in mind may be rendered rather inefficient. We propose to address this problem using a divide and conquer approach: the network is divided into convex pieces by a distributed convex partitioning protocol, using connectivity information only. A convex network partition exhibits some desirable properties that allow traditional algorithms to work to their full advantage. Based on this, we can achieve relatively high performance for an algorithm by combining algorithmic actions within individual partitions. We consider two important applications: virtual-coordinate-based geographic routing and connectivity-based localization. The former benefits from convex partition's friendliness to network embedding, which is crucial to generating accurate virtual coordinates for the nodes, while the latter leverages the fact that shortest paths are largely straight for node pairs within a convex partition. Experimental results show that the convex partition approach can significantly improve the performance of both applications in comparison with state-of-the-art solutions.

Sensor networks are invariably coupled tightly with the geometric environment in which the sensor nodes are deployed. Network boundary is one of the key features that characterize such environments. While significant advances have been made for 2D cases, so far boundary extraction for 3D sensor networks has not been thoroughly studied. We present CABET, a novel Connectivity-Based Boundary Extraction scheme for large-scale 3D sensor networks. To the best of our knowledge, CABET is the first 3D-capable and pure connectivity-based solution for detecting sensor network boundaries. It is fully distributed, and is highly scalable, requiring overall message cost linear with the network size. A highlight of CABET is its non-uniform critical node sampling , called r'-sampling , that selects landmarks to form boundary surfaces with bias toward nodes embodying salient topological features. Simulations show that CABET is able to extract a well-connected boundary in the presence of holes and shape variation, with performance superior to that of some state-of-the-art alternatives. In addition, we show how CABET benefits a range of sensor network applications including 3D skeleton extraction, 3D segmentation, and 3D localization.

Equipped with accelerometers and gyroscopes, modern smartphones provide an appealing approach to infrastructure-free navigation for vehicles in indoor environments (for example parking garages). However, a smartphone-based inertial navigation system (INS) faces two serious problems. First, it is subject to errors that accumulate over time rather quickly, which may grow to a level that renders the navigation meaningless. Second, without human input or external references, the smartphone can hardly infer its initial position/velocity, which is the basis for distance calculation, since all that a smartphone can learn is its acceleration. This raises a practical concern, as users often need to start indoor navigation precisely when they are uncertain of their current whereabouts. In this paper, we present Bumping , a Bump-Aided Inertial Navigation method that significantly alleviates the above two problems. At the core of this method is a Bump Matching algorithm, which exploits the position information of the readily available speed bumps to provide useful references for the INS. The proposed method is easy to implement, requires no infrastructures, and incurs nearly zero extra energy. We conducted real experiments in tree parking garages of different environmental characteristics. The Bumping method produces an average position error of 4-5 m in these scenarios, improving the accuracy by up to 87.1 percent, compared to the basic inertial navigation method.

Reducing transmission redundancy is key to efficient broadcast in wireless networks. A standard approach to achieving this goal is to create a network backbone consisting of a subset of nodes that are responsible for data forwarding, while other nodes act as passive receivers. On top of this, network coding (NC) is often used to further reduce unnecessary transmissions. The main problem with existing backbone and NC combinations is that the backbone construction process is blind of what is needed by NC, thus may produce a structure that limits the power of NC algorithms. To address this problem, we propose Coding Opportunity Aware Backbone (COAB) metrics, which seek to maximize coding opportunities when selecting backbone forwarders. We show that the backbone construction process guided by our metrics leads to significantly increased coding frequency, at the cost of minimal localized information exchange. The highlight of our work is COAB's broad applicability and effectiveness. We integrate the COAB metrics with ten state-of-the-art broadcast algorithms specified in eight publications [1]-[8], and evaluate COAB with a running testbed of 30 MICAz nodes and extensively simulations. The experimental results show that our design outperforms the existing schemes substantially.

As a sensor network grows large, it may become increasingly complex in topology due to its close ties to the surrounding environment. Previous work has shown that proper geometric processing of the network (e.g., boundary detection and localization) can provide very helpful information for applications to optimize their performance. To that end, numerous algorithms have been developed, providing a variety of inspiring solutions, yet exhibiting an ad hoc style in principle and implementation. In this paper we show that the crux of solving many of the problems caused by complex topology is to identify the concave nodes, nodes that are located at concave network corners, where the boundary has an inner angle greater than π. The knowledge of such nodes makes several important tasks, namely geometric embedding, full localization, convex segmentation, and boundary detection, relatively easier or perform significantly better, as confirmed by simulations. These findings suggest that concave nodes can serve as a basic supporting structure for general geometric processing tasks and geometry-related applications in sensor networks.

Reducing transmission redundancy is key to the efficiency of wireless network broadcast. A standard technique to achieve this is to create a network backbone consisting of a subset of nodes that are responsible for data forwarding, while other nodes act as passive receivers. On top of this, network coding (NC) is often used to further reduce unnecessary transmissions. The main problem with this backbone+NC approach is that the backbone construction process is blind of what is needed by NC, thus may produce a structure with little benefit to the NC algorithms. To address this problem, we propose a Coding Opportunity Aware Backbone (COAB) construction scheme, which seeks to maximally exploit coding opportunities when selecting backbone forwarders. We show that the better informed backbone construction process leads to significantly increased coding frequency, at minimal cost of localized information exchange. The highlight of our work is COAB's broad applicability and effectiveness. We integrate COAB with ten state-of-the-art broadcast algorithms, specified in eight publications [1]-[8], and evaluate it with prototype implementations with 30 MICAz nodes. The experimental results show that our design outperforms the existing schemes substantially.

In this paper, we put forward a novel scalable and distributed routing algorithm, called SINUS, for sensor networks deployed on the surface of complex-connected 3D settings such as tunnels, whose topologies are often theoretically modeled as high genus 3D surfaces. SINUS is carried out by first slicing the genus-n surface along a maximum cut set based on Morse theory and Reeb graph, in order to form a genus-0 surface with 2n boundaries. Then, it groups these 2n boundaries into two groups each of which is next connected together. By doing so, a genus-0 surface with exactly two boundaries emerges, which can be flattened into a strip, using the Ricci flow algorithm and next mapped to a planar annulus by Möbius Transform. By assigning nodes virtual coordinates on the planar annulus, SINUS finally realizes a variation of greedy routing to enable individual nodes to make local muting decisions. Our simulation results show that SINUS can achieve low-stretch routing with guaranteed delivery, as well as balanced traffic load.

Wireless communication essentially occurs in a broadcast medium with concurrent receptions. Recent works [34, 41] have shown clear evidence that wireless links are not independent and that transmissions from a transmitter to multiple receivers are correlated, a phenomenon that has profound implications for the performance of network protocols such as broadcast, multi-cast, opportunistic forwarding and network coding. In this paper, we show how link correlation can significantly impact broadcast. We present the design and implementation of CorLayer, a general supporting layer for energy efficient reliable broadcast that carefully blacklists certain poorly correlated wireless links. This method uses only one-hop information, which makes it work in a fully distributed manner and introduces minimal communication overhead. The highlight of our work is CorLayer's broad applicability and effectiveness. Our system effort is indeed significant. We integrate CorLayer transparently with sixteen state-of-the-art broadcast protocols specified in thirteen publications [1, 3, 18, 19, 23, 25--27, 32, 36, 38--40] on three physical testbeds running TelosB, MICAz, and GreenOrbs nodes, respectively. The experimental results show that CorLayer remarkably improves energy efficiency across a wide spectrum of broadcast protocols and that the total number of packet transmissions can be reduced consistently by 47% on average.

Scalable routing for large-scale wireless networks needs to find near shortest paths with low state on each node, preferably sub-linear with the network size. Two approaches are considered promising toward this goal: compact routing and geometric routing (geo-routing). To date the two lines of research have been largely independent, perhaps because of the distinct principles they follow. In particular, it remains unclear how they compare with each other in the worst case, despite extensive experimental results showing the superiority of one or another in particular cases. We develop a novel Trap Array topology model that provides a unified framework to uncover the limiting behavior of ten representative geo-routing algorithms. We present a series of new theoretical results, in comparison with the performance of compact routing as a baseline. In light of their pros and cons, we further design a Compact Geometric Routing (CGR) algorithm that attempts to leverage the benefits of both approaches. Theoretic analysis and simulations show the advantages of the topology model and the algorithm.

A connectivity-based and anchor-free three-dimensional localization (CATL) scheme is presented for large-scale sensor networks with concave regions. It distinguishes itself from previous work with a combination of three features: (1) it works for networks in both 2D and 3D spaces, possibly containing holes or concave regions; (2) it is anchor-free and uses only connectivity information to faithfully recover the original network topology, up to scaling and rotation; (3) it does not depend on the knowledge of network boundaries, which suits it well to situations where boundaries are difficult to identify. The key idea of CATL is to discover the notch nodes , where shortest paths bend and hop-count-based distance starts to significantly deviate from the true Euclidean distance. An iterative protocol is developed that uses a notch-avoiding multilateration mechanism to localize the network. Simulations show that CATL achieves accurate localization results with a moderate per-node message cost.

We study the problem of skeleton extraction for large-scale sensor networks with reliance purely on connectivity information. Existing efforts in this line highly depend on the boundary detection algorithms, which are used to extract accurate boundary nodes. One challenge is that in practical this could limit the applicability of the boundary detection algorithms. For instance, in low node density networks where boundary detection algorithms do not work well, the extracted boundary nodes are often incomplete. This paper brings a new view to skeleton extraction from a distance transform perspective, bridging the distance transform of the network and the incomplete boundaries. As such, we propose a distributed and scalable algorithm for skeleton extraction, called DIST, based on DIStance Transform, while incurring low communication overhead. The proposed algorithm does not require that the boundaries are complete or accurate, which makes the proposed algorithm more practical in applications. First, we compute the distance transform of the network. Specifically, the distance (hop count) of each node to the boundaries of a sensor network is estimated. The node map consisting of the distance values is considered as the distance transform (the distance map). The distance map is then used to identify skeleton nodes. Next, skeleton arcs are generated by controlled flooding within the identified skeleton nodes, thereby connecting these skeleton arcs, to extract a coarse skeleton. Finally, we refine the coarse skeleton by building shortest path trees followed by a prune phase. The obtained skeleton is robust to boundary noise or shape variations. Besides, we present two specific applications that benefit from the extracted skeleton: identifying complete boundaries and shape segmentation. First, with the extracted skeleton using DIST, we propose to identify more boundary nodes to form a meaningful boundary curve. Second, the utilization of the derived skeleton to segment the network into approximately convex pieces has been shown to be effective.

This paper proposes a novel approach, named DIST, to skeleton extraction from incomplete boundaries using the idea of {\em distance transform}, a concept in the computer graphics area. The main contribution is a distributed and low-cost algorithm that produces accurate network skeletons without requiring that the boundaries be complete or tight. The algorithm first establishes the network's distance transform -- the hop distance of each node to the network's boundaries. Based on this, some {\em critical skeleton nodes} are identified. Next, a set of {\em skeleton arcs} are generated by controlled flooding, connecting these skeleton arcs then gives us a coarse skeleton. The algorithm finally refines the coarse skeleton by building shortest path trees, followed by a prune phase. The obtained skeletons are robust to boundary noise and shape variations.

A cardinal prerequisite for the system design of a sensor network, is to understand the geometric environment where sensor nodes are deployed. The global topology of a large-scale sensor network is often complex and irregular, possibly containing obstacles/holes. A convex network partition, so-called segmentation, is to divide a network into convex regions, such that traditional algorithms designed for a simple geometric region can be applied. Existing segmentation algorithms highly depend on concave node detection on the boundary or sink extraction on the medial axis, thus leading to quite sensitive performance to the boundary noise. More severely, since they exploit the network's 2D geometric properties, either explicitly or implicitly, so far there has been no general 3D segmentation solution. In this paper, we bring a new view to segmentation from a Morse function perspective, bridging the convex regions and the Reeb graph of a network. Accordingly, we propose a novel distributed and scalable algorithm, named CONSEL, for CONnectivity-based SEgmentation in Large-scale 2D/3D sensor networks. Specifically, several boundary nodes first perform flooding to construct the Reeb graph. The ordinary nodes then compute mutex pairs locally, thereby generating the coarse segmentation. Next the neighbor regions which are not mutex pair are merged together. Finally, by ignoring mutex pairs which leads to small concavity, we provide the constraints for approximately convex decomposition. CONSEL is more desirable compared with previous studies: (1) it works for both 2D and 3D sensor networks; (2) it only relies on network connectivity information; (3) it guarantees a bound for the regions' deviation from convexity. Extensive simulations show that CONSEL works well in the presence of holes and shape variation, always yielding appropriate segmentation results.

In geographic (or geometric) routing, messages are by default routed in a greedy manner: The current node always forwards a message to its neighbor node that is closest to the destination. Despite its simplicity and general efficiency, this strategy alone does not guarantee delivery due to the existence of local minima (or dead ends). Overcoming local minima requires nodes to maintain extra nonlocal state or to use auxiliary mechanisms. We study how to facilitate greedy forwarding by using a minimum amount of such nonlocal states in topologically complex networks. Specifically, we investigate the problem of decomposing a given network into a minimum number of greedily routable components (GRCs), where greedy routing is guaranteed to work. We approach it by considering an approximate version of the problem in a continuous domain, with a central concept called the greedily routable region (GRR). A full characterization of GRR is given concerning its geometric properties and routing capability. We then develop simple approximate algorithms for the problem. These results lead to a practical routing protocol that has a routing stretch below 7 in a continuous domain, and close to 1 in several realistic network settings.

Top-k query has long been a crucial problem in multiple fields of computer science, such as data processing and information retrieval. In emerging cyber-physical systems, where there can be a large number of users searching information directly into the physical world, many new challenges arise for top-k query processing. From the client's perspective, users may request different sets of information, with different priorities and at different times. Thus, top-k search should not only be multidimensional, but also be across time domain. From the system's perspective, data collection is usually carried out by small sensing devices. Unlike the data centers used for searching in the cyber-space, these devices are often extremely resource constrained and system efficiency is of paramount importance. In this paper, we develop a framework that can effectively satisfy demands from the two aspects. The sensor network maintains an efficient dominant graph data structure for data readings. A simple top-k extraction algorithm is used for user query processing and two schemes are proposed to further reduce communication cost. Our methods can be used for top-k query with any linear convex query function. The framework is adaptive enough to incorporate some advanced features; for example, we show how approximate queries and data aging can be applied. To the best of our knowledge, this is the first work for continuous multidimensional top-k query processing in sensor networks. Simulation results show that our schemes can reduce the total communication cost by up to 90 percent, compared with a centralized scheme or a straightforward extension from previous top-k algorithm on 1D sensor data.

Top-k query has long been an important topic in many fields of computer science. Efficient implementation of the top-k queries is the key for information searching. With the new frontier such as the cyber-physical systems, where there can be a large number of users searching information directly into the physical world, many new challenges arise for top-k query processing. From the client's perspective, different users may request different set of information, with different priorities and at different times. Thus, the top-k search not only should be multi-dimensional, but also across time domain. From the system's perspective, the data collection is usually carried out by small sensing devices. Unlike the data centers used for searching in the cyber-space, these devices are often extremely resource-constrained and system efficiency is of paramount importance. In this paper, we develop a framework that can effectively satisfy the two ends. The sensor network maintains an efficient dominant graph data structure for data readings. A simple top-k extraction algorithm is used for the user query processing and two schemes are proposed to further reduce communication cost. Our proposed methods can be used for top-k query with any linear convex query function. To the best of our knowledge, this is the first work for continuous multi-dimensional top-k query processing in sensor networks; and our simulation results show that our schemes can reduce the total communication cost by up to 90%, compared with the centralized scheme or a straightforward extension from previous top-k algorithm on one-dimensional sensor data.

Sensor networks are invariably coupled tightly with the geometric environment in which the sensor nodes are deployed. Network boundary is one of the key features that characterize such environments. While significant advances have been made for 2D cases, so far boundary extraction for 3D sensor networks has not been thoroughly studied. We present CABET, a novel Connectivity-bAsed Boundary Extraction scheme for large-scale Three-dimensional sensor networks. To the best of our knowledge, CABET is the first 3D-capable and pure connectivity-based solution for detecting sensor network boundaries. It is fully distributed. A highlight of CABET is its non-uniform critical node sampling, called r r'-sampling, that selects landmarks to form boundary surfaces with bias toward nodes embodying salient topological features. Simulations show that CABET is able to extract a well-connected boundary in the presence of holes and shape variation, with performance superior to that of some state-of-the-art alternatives. In addition, we show how CABET benefits a range of sensor network applications including 3D skeleton extraction and 3D segmentation.

We consider message-efficient broadcast tolerating Byzantine faults in a multi-hop wireless sensor network. Assuming a grid network where all nodes have a communication range of r, and a single neighborhood contains at most t dishonest and collision-capable (bad) nodes, each with a message budget mf, we investigate the minimum message budget m that each honest (good) node must have in order to achieve reliable broadcast. We consider three cases: (1) mfis known in advance and m is homogeneous among all good nodes; (2) mfis known in advance and m is heterogeneous among good nodes; (3) mfis unknown. For the first two cases, we present possibility results and broadcast protocols that have message costs within twice the lower bound. For the third case, we present a coding scheme that helps verify the integrity of messages at a receiving node without using any cryptographic techniques. This code leads to a reactive local broadcast primitive that has probabilistic reliability guarantees. Combined with a previously proposed scheme, it results in a broadcast protocol for t <; 1/2r(2r + 1) that guarantees reliability with high probability.

In geographic (or geometric) routing, messages are expected to route in a greedy manner: the current node always forwards a message to its neighbor node that is closest to the destination. Despite its simplicity and general efficiency, this strategy alone does not guarantee delivery due to the existence of local minima (or dead ends). Overcoming local minima requires nodes to maintain extra non-local state or to use auxiliary mechanisms. We study how to facilitate greedy forwarding by using a minimum amount of such non-local state in topologically complex networks. Specifically, we investigate the problem of decomposing a given network into a minimum number of Greedily Routable Components (GRC), where greedy routing is guaranteed to work. We approach it by considering an approximate version in a continuous domain, with a central concept called the Greedily Routable Region (GRR). A full characterization of GRR is given concerning its geometric properties and routing capability. We then develop simple approximate algorithms for the problem. These results lead to a practical routing protocol that has a routing stretch below 7 in a continuous domain, and close to 1 in several realistic network settings

This paper presents a Connectivity-based and Anchor-free Three-dimensional Localization (CATL) scheme for large-scale sensor networks with concave regions. It distinguishes itself from previous work with a combination of three features: (1) it works for networks in both 2D and 3D spaces, possibly containing holes or concave regions; (2) it is anchor-free, and uses only connectivity information to faithfully recover the original network topology, up to scaling and rotation; (3) it does not depend on the knowledge of network boundaries, which suits it well to situations where boundaries are difficult to identify. The key idea of CATL is to discover the notch nodes, where shortest paths bend and hop-count-based distance starts to significantly deviate from the true Euclidean distance. An iterative protocol is developed that uses a em notch-avoiding multilateration mechanism to localize the network. Simulations show that CATL achieves accurate localization results with a moderate per-node message cost.

We study the problem of shortest-path geographic routing in a static sensor network. Existing algorithms often make routing decisions based on node information in local neighborhoods. However, it is shown by Kuhn et al. that such a design constraint results in a highly undesirable lower bound for routing performance: if a best route has length c, then in the worst case a route produced by any localized algorithm has length Omega(c2), which can be arbitrarily worse than the optimal. We present VIGOR, a visibility-graph-based routing protocol that produces routes of length Theta(c). Our design is based on the construction of a much reduced visibility graph, which guides nodes to find near-optimal paths. The per-node protocol overheads in terms of state information and message transmission depend only on the complexity of the field's large topological features, rather than on the network size. Simulation results show that our protocol dramatically outperforms localized protocols such as GPSR and GOAFR+ in both average and worst cases, with reasonable extra overheads.

Virtual coordinate geographic routing is an appealing geographic routing approach for its ability to work without physical location information. We examine two representative such routing protocols, namely NoGeo and BVR, and show through experiments and theoretical analysis their limitation in adapting to complex field topologies, in particular fields with concave holes. Based on the new insights, we propose a distributed convex partition protocol that divides the field to subareas with convex shapes, using only connectivity information. A new geographic routing protocol, called CONVEX, that builds upon the partitioning protocol is then described. Simulations demonstrate significant performance improvement of the new routing protocol over NoGeo and BVR, in terms of transmission stretch and maintenance overheads.

Mobile sensors can relocate and self-deploy into a network. While focusing on the problems of coverage, existing deployment schemes largely oversimplify the conditions for network connectivity: they either assume that the communication range is large enough for sensors in geometric neighborhoods to obtain location information through local communication, or they assume a dense network that remains connected. In addition, an obstacle-free field or full knowledge of the field layout is often assumed. We present new schemes that are not governed by these assumptions, and thus adapt to a wider range of application scenarios. The schemes are designed to maximize sensing coverage and also guarantee connectivity for a network with arbitrary sensor communication/sensing ranges or node densities, at the cost of a small moving distance. The schemes do not need any knowledge of the field layout, which can be irregular and have obstacles/holes of arbitrary shape. Our first scheme is an enhanced form of the traditional virtual-force-based method, which we term the connectivity-preserved virtual force (CPVF) scheme. We show that the localized communication, which is the very reason for its simplicity, results in poor coverage in certain cases. We then describe a floor-based scheme which overcomes the difficulties of CPVF and, as a result, significantly outperforms it and other state-of-the-art approaches. Throughout the paper our conclusions are corroborated by the results from extensive simulations.

Mobile sensors can move and self-deploy into a network. While focusing on the problems of coverage, existing deployment schemes mostly over-simplify the conditions for network connectivity: they either assume that the communication range is large enough for sensors in geometric neighborhoods to obtain each other's locationby local communications, or assume a dense network that remains connected. At the same time, an obstacle-free field or full knowledge of the field layout is often assumed. We present new schemes that are not restricted by these assumptions, and thus adapt to a much wider range of application scenarios. While maximizing sensing coverage, our schemes can achieve connectivity for a network with arbitrary sensor communication/sensing ranges or node densities, at the cost of a small moving distance; the schemes do not need any knowledge of the field layout, which can be irregular and have obstacles/holes of arbitrary shape. Simulations results show that the proposed schemes achieve the targeted properties.

We propose a novel payment-based incentive scheme for peer-to-peer (P2P) live media streaming. Using this approach, peers earn points by forwarding data to others. The data streaming is divided into fixed-length periods; during each of these periods, peers compete with each other for good parents (data suppliers) for the next period in a first-price-auction-like procedure using their points. We design a distributed algorithm to regulate peer competitions and consider various individual strategies for parent selection from a game-theoretic perspective. We then discuss possible strategies that can be used to maximize a peer's expected media quality by planning different bids for its substreams. Finally, in order to encourage off-session users to remain online and continue contributing to the network, we develop an optimal data forwarding strategy that allows peers to accumulate points that can be used in future services. Simulation results show that the proposed methods effectively differentiate the media qualities received by peers making different contributions (which originate from, for example, different forwarding bandwidths or servicing times) and at the same time maintain high overall system performance.

This paper investigates the reliability of application-level multicast based on a distributed hash table (DHT) in a highly dynamic network. Using a node residual lifetime model, we derive the stationary end-to-end delivery ratio of data streaming between a pair of nodes in the worst case, and show through numerical examples that in a practical DHT network, this ratio can be very low (e.g., less than 50%). Leveraging the property of heavy-tailed lifetime distribution, we then consider three optimizing techniques, namely senior member overlay (SMO), longer-lived neighbor selection (LNS), and reliable route selection (RRS), and present quantitative analysis of data delivery reliability under these schemes. In particular, we discuss the tradeoff between delivery ratio and the load imbalance among nodes. Simulation experiments are also used to evaluate the multicast performance under practical settings. Our model and analytic results provide useful tools for reliability analysis for other overlay-based applications (e.g., those involving persistent data transfers).

Broadcasting is a fundamental communication task in mobile ad hoc networks, and minimizing broadcasting time (or latency) is crucial to the performance ofmany applications. Extensive studies have been conducted on the minimization of broadcasting time in the context of radio networks, which are usually modeled as general graphs. In this paper, we consider how to achieve this goal with distributed algorithms based on a more realistic (and restricted) network model. We propose a randomized algorithm that completes broadcasting in O(D log(n/D)+log2 n) time, where n is the number of nodes in the network and D the eccentricity (maximum distancefrom the source node to any other node). Compared with a previous optimal algorithm that achieves the same result for general networks, our algorithm obviates the need to know the network eccentricity D beforehand We also propose a deterministic broadcasting algorithm that works in O(n) time, which is in contrast with the best known result of O(n log2 D) for general networks.

Broadcasting is a fundamental communication task in mobile ad hoc networks, and minimizing broadcasting time (or latency) is crucial to the performance ofmany applications. Extensive studies have been conducted on the minimization of broadcasting time in the context of radio networks, which are usually modeled as general graphs. In this paper, we consider how to achieve this goal with distributed algorithms based on a more realistic (and restricted) network model. We propose a randomized algorithm that completes broadcasting in O(D log(n/D)+log2 n) time, where n is the number of nodes in the network and D the eccentricity (maximum distancefrom the source node to any other node). Compared with a previous optimal algorithm that achieves the same result for general networks, our algorithm obviates the need to know the network eccentricity D beforehand We also propose a deterministic broadcasting algorithm that works in O(n) time, which is in contrast with the best known result of O(n log2 D) for general networks.

A key technical challenge for overlay multicast is that the highly dynamic multicast members can make data delivery unreliable. In this paper, we address this issue in the context of live media streaming by exploring 1) how to construct a stable multicast tree that minimizes the negative impact of frequent member departures on an existing overlay and 2) how to efficiently recover from packet errors caused by end-system or network failures. For the first problem, we identify two layout schemes for the tree nodes, namely, the bandwidth-ordered tree and the time-ordered tree, which represent two typical approaches to improving tree reliability, and conduct a stochastic analysis on their properties regarding reliability and tree depth. Based on the findings, we propose a distributed reliability-oriented switching tree (ROST) algorithm that minimizes the failure correlation among tree nodes. Compared with some commonly used distributed algorithms, the ROST algorithm significantly improves tree reliability and reduces average service delay, while incurring only a small protocol overhead; furthermore, it features a mechanism that prevents cheating or malicious behaviors in the exchange of bandwidth/time information. For the second problem, we develop a simple cooperative error recovery (CER) protocol that helps recover from packet errors efficiently. Recognizing that a single recovery source is usually incapable of providing the timely delivery of the lost data, the protocol recovers from data outages using the residual bandwidths from multiple sources, which are identified using a minimum-loss-correlation algorithm. Extensive simulations demonstrate the effectiveness of the proposed schemes

This paper addresses the problem of fault resilience of overlay-based live media streaming from two aspects: (1) how to construct a stable multicast tree that minimizes the negative impact of frequent member departures on existing overlay, and (2) how to efficiently recover from packet errors caused by end-system or network failures. In particular, this paper makes two contributions: (1) A distributed Reliability-Oriented Switching Tree (ROST) algorithm that minimizes the failure correlation among tree nodes. By exploiting both bandwidth and time properties, the algorithm constructs a more reliable multicast tree than existing algorithms that solely minimize tree depth, while not compromising the quality of the tree in terms of service delay and incurring only a small protocol overhead; (2) A simple Cooperative Error Recovery (CER) protocol that helps recover from packet errors efficiently. Recognizing that a single recovery source is usually incapable of providing timely delivery of the lost data, the protocol recovers from data outages using the residual bandwidths from multiple sources, which are identified using a minimum-losscorrelation algorithm. Extensive simulations are conducted to demonstrate the effectiveness of the proposed schemes.

The cooperation of end users can be exploited to boost the performance of high-bandwidth multicast. While intra-overlay cooperation, the mechanism for cooperation within a single overlay (multicast group), has been extensively studied, little attention has been paid to inter-overlay cooperation. In this paper we explore the possibility and effects of cooperation among co-existing heterogeneous overlays in the context of live media streaming, where bandwidth is the bottleneck resource. To motivate such a kind of cooperation, we design a reputation-based incentive mechanism that differentiates user' streaming qualities based on the amount of data actually forwarded by individual users. This not only stimulates users to contribute as much forwarding bandwidth as possible, but also motivates those with spare bandwidths in resource-rich overlays to find downstream users in external, often resource-poor, overlays so as to accumulate more reputation scores. Under this mechanism, an adaptive bandwidth exporting/reclaiming algorithm is developed which allows users to dynamically allocate bandwidth according to the resource availability of multiple overlays. Simulation results are reported with enhanced system performance in terms of users' average media quality

We proposes a novel payment-based incentive mechanism for peer-to-peer (P2P) live media streaming. Using this approach, peers earn points by forwarding data to others; the data streaming is divided into fixed length periods, during each of which peers compete with each other for good parents (data suppliers) for the next period in a first-price auction like procedure using their points. We design a distributed algorithm to regulate peer competitions, and consider various individual strategies for parent selection from a game theoretic perspective. We then discuss possible strategies that can be used to maximize a peer's expected media quality by planning different bids for its substreams. Finally, in order to encourage off-session users to keep staying online and continue contributing to the network, we develop an optimal data forwarding strategy that allows peers to accumulate points that can be used in future services. Simulations results show that proposed methods effectively differentiate the media qualities received by peers making different contributions (which originate from, for example, different forwarding band-widths or servicing times), and at the same time maintaining a high system-wide performance

Before an application modelled as a directed acyclic graph (DAG) is executed on a heterogeneous system, a DAG mapping policy is often enacted. After mapping, the tasks (in the DAG-based application) to be executed at each computational resource are determined. The tasks are then sent to the corresponding resources, where they are orchestrated in the pre-designed pattern to complete the work. Most DAG mapping policies in the literature assume that each computational resource is a processing node of a single processor, i.e. the tasks mapped to a resource are to be run in sequence. Our studies demonstrate that if the resource is actually a cluster with multiple processing nodes, this assumption will cause a mis-perception in the tasks' execution time and execution order. This will disturb the pre-designed cooperation among tasks so that the expected performance cannot be achieved. In this paper, a DAG mapping algorithm is presented for multicluster architectures. Each constituent cluster in the multicluster is shared by background workload (from other users) and has its own independent local scheduler. The multicluster DAG mapping policy is based on theoretical analysis and its performance is evaluated through extensive experimental studies. The results show that compared with conventional DAG mapping policies, the new scheme that we present can significantly improve the scheduling performance of a DAG-based application in terms of the schedule length.

For single-source, single-tree based peer-to-peer live media streaming, it is generally believed that a short (and wide) tree has a good comprehensive performance in terms of tree reliability and service delay. While the short tree directly benefits delay optimization, it is unclear whether such a structure maximizes tree reliability, which is sometimes more critical for a streaming Internet service. This paper studies several prevalent overlay construction algorithms in terms of (I) service reliability; (2) service delay and (3) protocol overhead. Two types of peer layout, bandwidth-ordered layout and time-ordered layout, are identified and their performance is evaluated. The analytical results show that, by appropriately placing peers according to their time properties, the tree can be much more reliable than a depth-optimized tree. We therefore propose a heap algorithm, which aims for combining the strengths of both bandwidth ordering and time ordering. It dynamically moves peers between difference layers of the tree according to a simple metric, and gradually adjusts the tree toward a layout partially ordered in time and partially ordered in bandwidth. In so doing the tree has advantages in both service reliability and delay, and maintains small protocol overheads. Extensive simulations demonstrate the effectiveness of this new algorithm.