In warehouse-based e-commerce, accurate category-level warehouse demand prediction is essential to ensure effective inventory management. Existing works mainly explore advanced time series models to capture the temporal dynamics, failing to mine cross-category and cross-warehouse correlations effectively. In this paper, we explore large language models to understand the semantic information and fuse multi-view knowledge to enhance demand prediction. However, it is not trivial due to: i) the inaccurate LLM’s understanding of the category-related and warehouse-related textual input; and ii) the complicated cross-warehouse knowledge utilization. To solve the above challenges, we propose an LLM-guided multi-task graph learning framework, LMGL-WD, for category-level warehouse demand prediction. Specifically, LMGL-WD includes three components: i) an LLM-guided category series encoding module to represent each category through contextual and series embedding; ii) a cross-warehouse category learning module to adaptively mine the informative knowledge from cross warehouses to enhance category representation; and iii) a cross-category multi-task learning module to adaptively capture cross-category correlations to improve demand prediction. Extensive evaluation results with real-world data collected from one of the largest e-commerce platforms in China demonstrate that LMGL-WD achieves superior performance, e.g., reduces MAPE by up to 31.59%, compared to state-of-the-art methods.

The surge in location-based services has driven the demand for accurate indoor localization techniques, with WiFi based localization emerging as a promising solution due to its extensive coverage in indoor environments. This paper presents BFI-L10N, an indoor localization method that leverages beam forming feedback information (BFI) obtained from standard multi-user multiple-input multiple-output (MU-MIMO) WiFi operations. Unlike traditional channel state information (CSI) based methods that require vendor-specific firmware patches or restricted device support, BFI leverages standardized MU-MIMO operations, enabling compatibility with off-the-shelf WiFi devices. BFI-L10N processes the BFI data collected during the beam forming process through a deep learning framework and uses a BERT model for localization. Compared to CSI-based systems, BFI-L10N offers advantages such as reduced overhead, enhanced sensitivity, compatibility with standard devices, and real-time predictions. Our experimental results in two distinct indoor environments demonstrate that BFI-L10N achieves average localization accuracies of 10.7 cm and 15.5 cm in a research laboratory and a conference room, respectively, outperforming the state-of the-art CSI techniques by 28%. Moreover, the BERT model can be fine-tuned after pre-training across multiple locations, which enhances the versatility of BFI-L10N. This paper presents a novel perspective on WiFi sensing and lays the foundation for practical indoor localization using standard WiFi infrastructure.

Wi-Fi is the de facto standard for providing wireless access to the Internet using the 2.4GHz ISM (Industrial Scientific Medical) band. LoRa (Long Range) is specially designed for Low-Power, Wide-Area Networks (LPWANs) and has a broad range of applications in Internet of Things. Tens of billions of mobile devices (e.g., smartphones) are manufactured with limited types of wireless radio, making it challenging to access the data in the heterogeneous IoT devices. To address this challenge, we propose a method that enables LoRa devices to establish connections and engage in communication with Wi-Fi networks. A key observation of this study is that when a LoRa frame collides with an ongoing Wi-Fi transmission, the Wi-Fi receiver captures and retains the LoRa data. By analyzing the decoded Wi-Fi payload, we can retrieve the LoRa data, and this method remains fully compatible with existing commodity Wi-Fi hardware. Moreover, evaluations with Universal Software Radio Peripheral (USRP) and commodity devices demonstrate reliable wireless communication from LoRa to Wi-Fi networks with a high reliability in frame reception and low frame error rates across various indoor and outdoor environments.

Points of Interest (POIs) are crucial for urban planning and location-based services. However, the high dynamics and expensive updating costs of POIs pose a key roadblock for their urban applications. This is especially true for developing countries, where active economic activities lead to frequent POI updates (e.g., merchants closing down and new ones opening). Therefore, POI updating, i.e., detecting new POIs and different names of the same POIs (alias) to update the POI database, has become an urgent but challenging problem to address. In this paper, we attempt to answer the research question of how to detect and update large-scale POIs via a low-cost approach. To do so, we propose a novel mobile sensing framework called UrbanPOI, which consists of three key modules: (i) a hierarchical POI candidate generation module based on the POINet model that detects POIs from shipping addresses; (ii) a new POI detection module based on the Siamese Attention Network that models multi-modal data and crowd intelligence; and (iii) a POI profiling model to infer the semantic category and the spatial location of updated POIs. Extensive results on real-world logistics delivery datasets show that our model outperforms state-of-theart models in Beijing City by 26.2% in precision and 10.7

Video object detection stands as a pivotal element within the burgeoning landscape of autonomous driving systems. The exigency to fulfill stringent real-time requisites, while upholding both precision and efficiency in detection, underscores its significance. Although extant methodologies enhance either accuracy or efficiency through the exploitation of spatio-temporal inter-dependencies within the video context, their propensity to conduct detection on discrete frames begets superfluous computations and curbed real-time efficacy. This paper introduces a pioneering approach, called Real-Batch, tailored explicitly to redress this quandary. Real-Batch ingeniously processes batches of video frames uniformly, effectually winnowing out repetitive object detection occurrences. Our methodology is rigorously evaluated on the real-word datasets, scrutinizing four key metrics: accuracy, efficiency, informational value, and adherence to timing constraints. The comprehensive findings substantiate that Real-Batch yields an unparalleled maximal surge in accuracy and efficiency, increasing of 4.2%-13.2% and 24.7%-43.9%, respectively, offering promising advancements for autonomous driving systems.

Last-mile delivery from delivery stations to customers is now mainly finished by dedicated couriers. In practice, each courier generally collects orders destined for one delivery area at the station and delivers them. However, the long distance between the station and the delivery area, due to practical reasons such as the expensive station rental fee in the downtown area, increases the travel time and decreases delivery efficiency. We solve the problem with relay transportation, where one or multiple relay couriers collect orders at the station and send them to delivery couriers, and delivery couriers focus on order delivery in the corresponding areas. We design a mobility-aware single relay courier scheduling system calledREDEto minimize the average relay order delivery time (ARODT) for last-mile delivery. First, a heterogeneous task aware route prediction algorithm is proposed to characterize the delivery courier's mobility. After that, a distance-aware greedy algorithm and an ARODT-constrained exchange algorithm are designed to generate the relay route. A hybrid last-mile delivery systemREDE+is then designed to further reduce ARODT ofREDE. We also proposeREDE-COto optimize multiple relay courier cooperative scheduling for order relay. Extensive evaluation shows the effectiveness ofREDE,REDE+, andREDE-COin reducing ARODT.

In last-mile delivery, efficient courier scheduling for heterogeneous tasks (i.e., delivery, pick-up, and customer expansion tasks) simultaneously benefits customers, couriers, and the platform. Existing scheduling methods for heterogeneous tasks neglect long-term optimization or are based on simple agent mobility settings. In this work, we focus on a scenario with varying task characteristics compared to existing studies and explore reinforcement learning for courier scheduling in last-mile delivery, considering fine-grained courier mobility. It is challenging due to: i) the large state and action space; ii) the courier cooperation under asynchronous decision-making caused by various task service times and courier travel times between location pairs; and iii) the multi-objective optimization under the dynamic environment. Therefore, we propose a heterogeneous task-aware cooperative courier scheduling system,HeroCS, to improve courier working efficiency and fairness in last-mile delivery. Specifically, we first design a distance-constrained courier modeling module to generate the single courier scheduling decisions, where a distance-aware top-$k$action pruning scheme is proposed to reduce state representation and action space. Then, a cooperative scheduling learning module is explored for optimizing courier cooperation. A status-aware action masking scheme is designed to solve asynchronous decision-making in model training. We also design a hybrid reward function to optimize various objectives adaptively. Extensive evaluation with real-world data from one of the largest logistics companies in China demonstrates that compared to state-of-the-art methods,HeroCSimproves the task completion rate by up to 40.7% and reduces courier unfairness by up to 83.3%.

Real-time semantic recognition is crucial for virtual reality (VR) applications, but the efficient fusion of multi-modal data poses significant challenges under resource-constrained VR scenarios. While integrating millimeter-wave (mmWave) radar point clouds with vision data offers a promising solution, existing methods often suffer from excessive data overhead and degraded accuracy due to redundant and noisy information. To address this limitation, this paper presents VR-PCT, a multi-modal transformer for edge-client collaborative VR semantic recognition that fuses mmWave radar point cloud and vision data for VR applications. VR-PCT introduces a novel collaborative design where VR clients perform lightweight semantic region detection while VR edge processes multi-modal VR semantic recognition. Through efficient edge-client collaboration, VR-PCT optimizes the transmission of mmWave point cloud and vision data by transmitting only the VR semantic region of vision data instead of the entire video. Additionally, it incorporates adaptive cross-modal data selection and fusion strategies to achieve real-time semantic recognition while significantly reducing data redundancy. Across 22 participants engaged in four experimental scenes utilizing VR devices from three different manufacturers, our evaluation demonstrates that VR-PCT achieves 97.6% recognition accuracy while reducing transmission overhead by 81.5% compared to existing approaches. These results highlight the effectiveness of VR-PCT in enabling efficient and accurate multi-modal VR semantic recognition for VR applications. The code and data of VR-PCT are released onhttps://github.com/luoyumei1-a/VR-PCT.

Logistics platforms increasingly offer real-time door-to-door order pickup services to enhance customer convenience. However, a high volume of unexpected order cancellations negatively impacts both customer experience and logistics profitability. Accurately identifying whether these cancellations stem from customers' decisions or couriers' non-compliant behaviors is essential for implementing targeted operational improvements. Simply interpreting customer-courier dialogues, however, risks being one-sided. The primary challenge lies in adaptively correlating dialogue content with the varying behaviors of couriers. To address this, we developCOCO, a cause identification framework for order cancellation in logistics that consists of: i)Multi-modal features exploration, which analyzes dialogues and couriers' behaviors (both historical and current); ii)Multi-modal features aggregation, which uses a hierarchical attention mechanism to adaptively capture the dynamic correlations within dialogues and behaviors; iii)LLM-enhanced refinement, which leverages Large Language Models to accurately process a large number of unlabeled dialogues, significantly enhancingCOCO's generalization and performance. To further enhanceCOCO's effectiveness, we introduceCOCO+, which incorporates customers' behaviors to better identify customer-related causes. Our extensive evaluation with data collected from JD Logistics demonstratesCOCO+'s exceptional performance, achieving an 12.2% increase in precision and a 9.1% improvement in recall over existing methods. Furthermore, after deployingCOCO+in real-world scenarios, we observed an adoption rate of 89.5% and improved on-time pickups even under high-demand conditions, as confirmed through A/B testing.

Though serverless computing offers transformative benefits for deploying machine learning (ML) services, it faces challenges in meeting strict real-time service-level objectives (SLOs) of ML inference while maintaining resource efficiency. Fortunately, a new binary instruction format, WebAssembly (or Wasm), offers a promising solution for serverless ML inferences thanks to its short startup time and efficient execution compared with traditional container-based solutions. Therefore, we introduce InfSquad, a serverless ML inference framework designed to balance SLO-aware execution with resource efficiency. The key design of InfSquad is a Wasm-assisted hybrid serverless function runtime to harness the complementary strengths of Wasm and traditional containerized function runtime. Based on the hybrid runtime, InfSquad advocates an SLO-aware runtime scheduling approach that delivers efficient serverless inference. InfSquad leverages a proactive runtime recycling mechanism to increase resource efficiency further. Experiments on real-world applications show that, compared with state-of-the-art serverless systems, InfSquad achieves 19.8% 85.1% SLO violation reduction with 32.5% 74.8% fewer resources.

Cross-Technology communication (CTC) has emerged as a pivotal solution for enabling communication between heterogeneous wireless devices, particularly in scenarios involving high-power and long-range networks. This paper introduces an innovative approach called WeRa, which leverages IEEE 802.11n technology to emulate LoRa waveforms, thus achieving efficient CTC from Wi-Fi to LoRa. WeRa utilizes orthogonal frequency division multiplexing (OFDM) technology in 802.11n to emulate LoRa chirp signals. To address the unique characteristics of LoRa signals, we propose a subcarrier selection scheme to enhance the communication performance between commercial Wi-Fi devices and commercial LoRa devices. During the Wi-Fi emulation process, frequency offsets are inevitable due to technical constraints. To mitigate this, we implement a fixed frequency compensation mechanism for the emulated signals based on thorough analysis. To tackle errors introduced by the cyclic prefix (CP), we build upon the boundary-flipping method proposed in WeBee and introduce a dynamic mode-flipping technique, effectively reducing the interference of CP on the emulated signals. We successfully implemented a prototype of WeRa on commercial Wi-Fi devices, the USRP platform, and commercial LoRa devices. Extensive experiments demonstrate WeRa’s robust performance, achieving a throughput of 119.683 kbps for efficiently transmitting complete LoRa frames while maintaining a symbol error rate below 0.1.

Estimating service capabilities for logistics terminal stations is essential for guiding operations adjustments to enhance customer experience. However, existing studies often focus on isolated metrics like on-time delivery or complaint rates, each reflecting a specific aspect of service capabilities. To provide a more comprehensive evaluation, we design AdaService, an Adaptive multi-faceted Service capabilities co-estimation framework. We begin by constructing Multi-faceted Hypergraph to encode stations using multiple performance metrics. We then introduce a Multi-faceted Hypergraph Convolution Network (MHCN) to capture the heterogeneous service capabilities across stations, providing a comprehensive capabilities representation. Finally, we apply an Adaptive Multi-faceted Estimation module that uses multi-task learning to model dynamic interactions among these metrics, enhancing predictive accuracy. Extensive evaluation with real-world data collected from nationwide stations in a leading logistics company in China demonstrates that AdaService significantly outperforms state-of-the-art methods, improving estimation accuracy for on-time delivery, on-time pick-up, and complaint rates by up to 18.98%, 9.30%, and 39.62%.

In last-mile logistics, couriers are typically assigned fixed zones to perform door-to-door deliveries. In practice, packages in some delivery zones might not be fulfilled on time due to couriers taking irregular leave for sickness or higher-priority task assignments, e.g., services for VIPs and regulatory training. Beyond the costly real-world practice, i.e., hiring temporary workers, analysis of historical data reveals that a daily delivery task rescheduling among on-duty couriers can be a cost-effective and efficient alternative. It involves individual workload assessments and delivery task assignments, both of which existing methods can not address adequately: (i) Existing courier workload assessment methods are not tailored for downstream optimization tasks, leading to poor performance. (ii) Efficiency-oriented task assignment methods may lead to unfair workload among the couriers. To address the above two limitations, in this paper, we propose D3-TR, a data-driven method for task reassignment among present couriers. Firstly, we design a consistency-guided predictor that can quickly and precisely predict the workload of couriers. Secondly, based on this predictor, we design a workload-aware genetic algorithm to solve the optimal task allocation problem. Experimental results underscore the superiority of our method over several baselines. Furthermore, real-world deployment on millions of orders demonstrates the effectiveness of our solution, yielding an average of 3.9% improvement in the on-time delivery rate.

A long-standing challenge for pushing sensor-based human activity recognition (HAR) to industrial usage is the distribution shift between training data and testing data: significant variations in data distribution lead to a notable decline in performance. Recently, Large Language Models (LLMs) have demonstrated exceptional generalization capability, which provides a new opportunity to mitigate the distribution shift problem of HAR. However, since LLMs are inherently designed and trained on textual data, their potential to enhance generalization in HAR applications remains an open question. In this paper, we introduce LLM4HAR, a novel LLM-based model to improve cross-domain HAR. LLM4HAR consists of three main modules: (i) the Sensor Data Adaptation module, which aligns IMU signals with LLMs via sensor embedding(ii) the Sensor Knowledge Learning module, which injects sensor knowledge into LLMs for activity recognition, and (iii) the Efficiency Enhancement module, which employs a partial training strategy and reduces the model size by more than 10 times. Extensive evaluations show that LLM4HAR outperforms the existing methods by 13.82% in average F1 score, demonstrating the feasibility and effectiveness of transferring knowledge from pretrained LLMs to enhance HAR. Further, LLM4HAR has been adopted by JD Logistics to support downstream applications such as Courier Welfare Improvement and Map Data Generation.

In logistic systems, demand prediction is an essential task providing the basis for improving the quality of terminal services, such as pick-up and delivery efficiency. However, the geographical scope of operations across multiple cities brings challenges due to the sparsity of user behavior data, hindering accurate predictions. Despite cross-city prediction methods potentially solving this problem by relying on the label of overlapping users in different cities, annotating these overlapping users is expensive. Additionally, the dynamic and diverse nature of user behaviors complicates feature transfer between cities. In this work, we define the logistics demand prediction problem as forecasting pick-up and delivery demand for zones, the smallest operational units in logistics systems, in different cities. To address the challenge, we propose TSTL, a Transferable Spatio-Temporal Learning framework for cross-city logistics prediction with sparse user data. TSTL advances existing methods from two aspects: (1) User-level invariant representation module extracts consistent user representations for overlapping and non-overlapping users across cities. (2) User-zone graph aggregation module enhances user embeddings by integrating dynamic interactions, such as logistics behaviors, into inherent user relations. Finally, the multi-city transfer module fine-tunes model parameters for city-invariant knowledge adoption and predicts future logistics demand. We implement and evaluate TSTL on one of the largest logistics systems. Extensive offline experiments and real-world deployment demonstrate the effectiveness of TSTL.

Spatio-temporal prediction focuses on jointly modeling spatial correlations and temporal evolution and has a wide range of applications. Due to the heterogeneity of spatio-temporal data, accurate prediction relies on effectively integrating topological structures and sequential patterns. Although recurrent graph learning methods excel at capturing dynamic graph patterns, explicitly inferring future snapshots from historical dynamic graphs remains a significant challenge. Recently, prompt-based graph learning has shown the potential to improve future snapshot inference by leveraging node or task-specific prompts. However, these methods fail to fully capture edge information resulting in incomplete and less accurate representations of future snapshot structures. To bridge this gap, we propose ProST, a framework that Prompts future snapshots on dynamic graphs for Spatio-Temporal prediction, which leverages dynamic graph pre-training to generate a premise graph containing historical graph information and then employs prompts on the premise graph to infer explicit future snapshots. Specifically, this framework comprises three steps: Firstly, dynamic graph pre-training is performed using multi-granularity evolution graph convolution to obtain the premise graph with both local and global features of dynamic graphs. Secondly, prompt subgraphs are used to prompt node pairs and edge features within the premise graph. The subgraph prompt aggregation mechanism propagates this information to generate future snapshots. Finally, we freeze the parameters of the pre-trained model and update the subgraph prompt parameters using meta-learning to adapt to downstream spatio-temporal prediction tasks. Extensive experiments on real-world datasets validate that ProST achieves state-of-the-art performance.

Textual description of a physical location, commonly known as an address, plays an important role in location-based services(LBS) such as on-demand delivery and navigation. However, the prevalence of abnormal addresses, those containing inaccuracies that fail to pinpoint a location, have led to significant costs. Address rewriting has emerged as a solution to rectify these abnormal addresses. Despite the critical need, existing address rewriting methods are limited, typically tailored to correct specific error types, or frequently require retraining to process new address data effectively. In this study, we introduce AddrLLM, an innovative framework for address rewriting that is built upon a retrieval augmented large language model. AddrLLM overcomes aforementioned limitations through a meticulously designed Supervised Fine-Tuning module, an Address-centric Retrieval Augmented Generation module and a Bias-free Objective Alignment module. To the best of our knowledge, this study pioneers the application of LLM-based address rewriting approach to solve the issue of abnormal addresses. Through comprehensive offline testing with real-world data on a national scale and subsequent online deployment, AddrLLM has demonstrated superior performance in integration with existing logistics system. It has significantly decreased the rate of parcel re-routing by approximately 43%, underscoring its exceptional efficacy in real-world applications.

Human behavior sensing has been receiving growing attention from both academia and industry in recent years. We report - to the best of our knowledge - the first AI-driven nationwide human behavior sensing system called SMILE in urban last-mile delivery. SMILE detects real-time human behaviors with self-supervised sensor data pretraining and uploads detection results to cloud servers with mobile networks. During its full deployment phase at JD Logistics, SMILE is deployed on over 500,000 mobile devices carried by over 300,000 delivery couriers who travel more than 10 million KM every day in 366 Chinese cities. SMILE serves the delivery of 7 billion E-commerce orders every year for more than 500 million customers. SMILE detects walking, upstairs, downstairs, still, and driving behaviors. SMILE has been fully deployed at JD Logistics to support two real-world applications that benefit both the delivery couriers and the logistics platform: (1) workload measurement to improve couriers' welfare; (2) large-scale delivery map data generation to improve the logistics delivery efficiency.

Cross-Technology Communication (CTC) is a cornerstone for seamless interoperability in heterogeneous wireless environments, enabling diverse devices to coexist and cooperate effectively. In this paper, we present Wi-Fi-to-X, designed to leverage deep learning techniques to generate waveforms that are compatible with multiple communication protocols, allowing seamless data transmission between Wi-Fi and other wireless technologies such as ZigBee, LoRa, and Bluetooth. This approach enables devices operating under different wireless standards to communicate effectively without requiring hardware modifications or protocol standardization. By training a specialized neural network on simulations of Orthogonal Frequency Division Multiplexing (OFDM) and Quadrature Amplitude Modulation (QAM), we have improved the efficiency and reliability of signal processing in CTC, Wi-Fi-to-X achieves robust signal modulation and demodulation across disparate technologies, enabling communication from Wi-Fi to other IoT devices, including ZigBee, LoRa, and Bluetooth. We evaluated both USRP and commodity devices, demonstrated that Wi-Fi-to-X can achieve concurrent wireless communication from Wi-Fi to other IoT devices.

An efficient last-mile delivery scheme in logistics benefits customers, couriers, and the platform. In practice, the delivery scope of a delivery station is divided into multiple areas, each of which is covered by a courier. The long distances between the delivery station and areas limit the couriers' delivery efficiency given that they need to travel back and forth multiple times a day. To solve this problem, we explore an inter-trip cooperation scheme for last-mile delivery, in which couriers traveling to the delivery station and back to corresponding areas earlier can help to take others' orders back. Coordinating the courier cooperation is challenging because we need to consider the courier's status, e.g., locations, and vehicle capacity constraint simultaneously. In this work, we design an inter-trip cooperation-based last-mile delivery system, InCo, aiming to minimize the average order delivery time. InCo includes two components: i) a time-aware spanning tree algorithm to generate the cooperation result for a group of couriers; and ii) a capacity-constrained courier grouping algorithm to optimize the courier grouping result iteratively. Extensive evaluation results with real-world order data collected from one of the largest logistics companies show that InCo improves the average saved delivery time and reduces average travel time by up to 80.2% and 28.4%, respectively, compared to baseline methods. The deployment results show InCo improves the average courier working efficiency by 21.6% to the state-of-the-practice.

The Internet of Things (IoT) has become an integral part of daily life, enabling seamless interaction between humans and the physical world. However, prototyping IoT applications remains an arduous task, requiring expertise in both hardware and software development. Current low-code and zero-code development approaches fail to address the tight coupling between hardware and software as well as the performance of the generated application, limiting their applicability. We introduce Jarvis, a zero-code prototyping framework for IoT applications that leverages composable hardware-software abstractions. By abstracting physical constraints and introducing a parameter-free self-reflection generation mechanism, Jarvis enables large language models to understand and address the coupling constraints in IoT development with minimized token cost and hallucination. Jarvis also considers the cost and energy efficiency of the resulting IoT prototype, optimizing the performance of the generated solutions. Evaluations demonstrate that Jarvis outperforms state-of-the-art methods, reducing hardware costs by 23.1%–75.5%, saving power consumption by 18.7%–95.2%, and lowering token usage for prototyping by 32.1%–86.2%.

The advanced logistics systems are increasingly transitioning towards integrated warehousing and distribution supply networks (IWDSN), where accurately forecasting supply capacity is essential for maintaining delivery capabilities that meet user demands. However, existing research often overlooks the impact of dynamic changes in network topology, resulting in limitations in capturing dynamic routing and diverse node responses. These limitations become particularly pronounced in the context of external events such as pandemics, heavy rain, and promotions. To address the above limitations, we proposeH2DGL, aHierarchicalHeterogeneousDynamicGraphLearning framework based on adaptive metapath aggregation, for forecasting supply capabilities in logistics systems. Specifically,H2DGLcomprises three main modules: (1) Hierarchical Heterogeneous Node Representation, where the micro graph captures dynamic routing information through adaptive meta-path aggregation from routing and event view graphs, and the macro graph extracts spatial representations using bipartite graph learning. (2) The Dynamic Graph Encoding module integrates macro and micro features from different snapshots to derive unified node representations. (3) The Spatio-temporal Joint Forecasting combines spatial features with temporal features from a time-series encoder to predict future supply capacity. Extensive experiments on two real-world datasets from different cities demonstrate thatH2DGLachieves state-of-the-art performance compared to advanced baseline models. The code is available at https://github.com/kaiwxai/H2DGL

A warehouse-distribution integration (WDI) e-commerce platform is an approach that combines warehousing and distribution processes, which is increasingly adopted in industry to enhance business efficiency. In the WDI e-commerce, one of the most important problems is to estimate the full-link delivery time for decision-making. Traditional methods designed for separate warehouse-distribution models struggle to address challenges in integrated systems. The difficulties stem from two main factors: (i) the contextual influence exerted by neighboring units within heterogeneous delivery networks, and (ii) the uncertainty in delivery times caused by dynamic and periodic temporal factors such as fluctuations in online sales volumes and the varying characteristics of different delivery units (e.g., warehouses and sorting centers). To address these challenges, we propose a novel full-link delivery time estimation framework calledHeterogeneousPeriodicSpatial-TemporalGraphTransformer (HPST-GT). First, we develop heterogeneous graph transformers to capture the hierarchical and diverse information of the warehouse-distribution network. Next, we design spatial-temporal transformers based on heterogeneous features to analyze the correlation between spatial and temporal information. Finally, we create a heterogeneous spatial-temporal graph prediction module to estimate full-link delivery time. Our method, evaluated on a one-month dataset from a leading e-commerce platform, surpasses current benchmarks across multiple performance metrics.

LoRaWAN is a prominent technology for Low Power Wide Area Networks (LPWAN). However, the increasing network size has introduced a significant challenge: packet collisions resulting from concurrent transmissions in LoRaWAN. Previous studies either overlooked the issue by examining limited features or tackled it with intricate receivers employing up to eight antennas. To achieve a more favorable balance between implementation cost and system performance, we introduce$\text{Hi}^{2}\text{LoRa}$—a solution utilizing highly dimensional and accurate features for LoRa concurrent decoding, implemented with only two receiving antennas. The feature dimensions are expanded through an exploration of various hardware imperfections and inherent channel state information specific to each transceiver pair. To enhance feature accuracy, low pass filters and BiLSTM networks are applied to capture and learn their temporal patterns. Additionally, an efficient collision suppression strategy is introduced to mitigate feature corruption from concurrently transmitted packets. Extensive real-world testbed evaluations demonstrate that the achievable concurrency in$\text{Hi}^{2}\text{LoRa}$approaches that of state-of-the-art approaches with significantly higher complexity (e.g., utilizing eight antennas) or exceeds prior work by a factor of 2.7 with comparable complexity (e.g., using two antennas).

Wi-Fi is the de facto standard for providing wireless access to the Internet in the 2.4 GHz ISM band. Tens of billions of Wi-Fi devices (e.g., smartphones) have been shipped worldwide with limited types of wireless radios operating only when Wi-Fi connectivity is available, making it challenging to access data in heterogeneous IoT devices. However, the direct connection between Wireless Personal Area Network (WPAN) technologies, such as Bluetooth, and Wi-Fi presents challenges due to the inherent distinct physical layer. In our work, a novel communication method called BlueWi has been introduced, which serves as a cross technology communication method that enables BLE devices to establish connections and engage in communication with Wi-Fi based WPAN networks. We let BLE signals hitchhike on ongoing Wi-Fi signals, enabling Wi-Fi to recognize specific BLE signal waveforms in the frequency domain. By analyzing the decoded Wi-Fi payload, BlueWi can retrieve the BLE data, ensuring this method remains fully compatible with existing commodity Wi-Fi hardware. The direct sequence spread spectrum scheme is appended to handle general BLE frames and can be considered as “COPY” operation, which allows for better correlation and detection of the signal at the receiver. Evaluations conducted using both USRP and commodity devices have demonstrated that BlueWi can achieve concurrent wireless communication from BLE commercial chips to Wi-Fi networks with a frame reception rate exceeding 96%.

To meet the stringent demanding low latency and high throughput of cloud datacenter applications, recent receiver-driven transport protocols transmit only one packet once receiving each credit packet from the receiver to achieve ultra-low queueing delay. However, the round-trip time variation and the highly dynamic background traffic significantly deteriorate the performance of receiver-driven transport protocols, resulting in under-utilized bandwidth. This paper designs a simple yet effective solution called RPO, which retains the advantages of receiver-driven transmission while efficiently utilizing the available bandwidth. Specifically, RPO rationally uses low-priority opportunistic packets to ensure high network utilization without increasing the queueing delay of high-priority normal packets. Furthermore, to tackle the queueing buildup due to line-rate transmission in the first RTT, we design a selective dropping mechanism called SDM to help the majority of small flows complete within only one RTT by prioritizing the first-RTT bursty packets over the packets triggered by grants. We implement RPO in Linux hosts with DPDK. The experimental results show that RPO significantly improves the network utilization by up to 35% over the state-of-the-art schemes, without introducing additional queueing delay. Moreover, RPO integrated with SDM reduces the AFCT of small flows by up to 45% compared with RPO integrated with Aeolus.

Efficient order assignment in last-mile delivery benefits customers, couriers, and the platform. State-of-the-practice order assignment is based on the static delivery area partition, which cannot adapt well to the dynamic order quantity and destination distributions on different days. State-of-the-art methods focus on balancing order amounts or the payoff among couriers dynamically, neglecting the courier's workload in delivering orders. This paper explores the courier's heterogeneous behaviors for delivering orders to different destinations to measure the courier's workload and then achieve more efficient order assignments under the fair workload constraint. We design a workload-constrained order assignment system, calledWORD, to reduce the cost of the last-mile delivery, i.e., the couriers’ total travel distance and overdue order rate. Specifically, the heterogeneous behaviors for delivering orders are first utilized for workload calculation. Then a two-stage order assignment framework is designed, including a sort-based initialization algorithm for initializing the assignment under the fair workload constraint and a coalition-game-based improvement algorithm for improving the assignment. Extensive evaluation results with real-world logistics data from one of the largest logistics companies in China show thatWORDreduces the cost of the order assignment by up to 51.9% under the fair workload constraint compared to the state-of-the-art methods.

LoRa networks operating in a star topology, this configuration creates a single point of failure and may limit scalability and reliability in areas that are large and geographically dispersed. In order to improve the overall transmission capabilities of the network, recent studies show that adding LoRa to the ZigBee devices effectively disseminates network management. By doing so, the strengths of both technologies can be leveraged, with LoRa serving as the long-range transmitter and ZigBee functioning as the mesh network. In this study, we present LoBee, a novel bidirectional communication method between LoRa and ZigBee that relies on Physical-Layer Cross-Technology Communication. Despite the fact that LoRa and ZigBee utilize different modulation techniques, ZigBee devices can detect and recognize LoRa chirps through the process of sampling the received signal strength. For the transmissions from ZigBee to LoRa devices, we carefully select the input chips to generate specific waveforms, where LoBee detects the preamble of a ZigBee frame based on the locations of the repeated peaks. Our evaluation, which was conducted using USRP and commodity devices, demonstrates that LoBee is capable of achieving concurrent bidirectional wireless communications, with a data rate of approximately 639.38 bits per second from LoRa to ZigBee and from ZigBee to LoRa with more than 90% frame reception rate in the 2.4 GHz frequency band.

With the development of the logistics industry, the user base of logistics services has expanded swiftly. This rapid increase in user scale presents significant challenges for logistics business management. A fundamental issue in such scenarios is audience expansion, which aims to find users willing to sign long-term services with logistics companies to foster business growth. Existing methods in addressing audience expansion mainly assume user modeling is entangled and neglects the inherent community structure among users. Due to these limitations, the effectiveness of traditional methods in achieving accurate user expansion is often restricted. Our work introduces a novel heterogeneous graph-based model, named Hi-DGN, which concentrates on the Hierarchical information propagation and aggregation in Disentangled Graph Networks for audience expansion. It consists of three main components: (i) the disentangled embedding layer to decouple user representations into different aspects, enabling the extraction of differentiated features; (ii) the hierarchical information propagation module partitions individual nodes into distinct groups and propagates information from group nodes to individual nodes hierarchically to capture diverse granularity representations; and (iii) the aggregation module to fuse all relation-specific embeddings to generate global node embeddings. Extensive experiments on two real-world datasets demonstrate the effectiveness of our method in various evaluation settings.

Recommendation systems play a crucial role in both industrial applications and research fields, which target to understand user preferences and intentions to provide personalized services. Compared to conventional recommendations, repurchase recommendations aim to suggest suitable products to users that they used to buy based on their intention evolution. Existing research on product recommendation can mainly be divided into behavior sequence-based methods and graph-based methods. Although these methods represent user interests and preference features effectively, they still fail to model repurchase behaviors because (i) the environment causing repurchase intention change is neglected and (ii) the lack of feedback after purchasing makes it difficult to learn the impacts of diverse behaviors. To comprehensively consider these limitations, we design a D ual I ntention-aware F usion N etwork framework (DIFN) to understand the effects of environment and after-purchasing feedback on users' intentions. Firstly, a hierarchical graph-based multi-level relational attention module is designed to effectively extract basic user features and spatial features from complex environmental information. Then, we introduce a behavior intention module and a usage intention module for different types of feedback data. Finally, we propose a dual intention fusion network that effectively fuses user basic features with spatial attributes and user intention features with temporal attributes for recommendation. Comprehensive evaluations on real-world datasets show that our method exceeds state-of-the-art baselines, which show an average of 8.2% improvements in different metrics.

In on-demand delivery,online orders are delivered by couriers from merchants to customers within a short time (e.g., 45 minutes). An important task is to provide an efficient order dispatching solution. Existing studies focus on scenarios with stable routing behavior using pre-determined courier-order matching before delivery while ignoring real-time dynamics during delivery. In this work, we leverage courier-courier encounter events as an opportunity to enable cooperative order dispatching (i.e., conducting order transfers among couriers during delivery) for better delivery efficiency. However, it is non-trivial to conduct encounter-aware cooperative order dispatching in real-time dynamics due to two major challenges: (i) the dynamic nature of encounters in diverse real-world scenarios, and (ii) global delivery efficiency optimization by local order transfers. To address the above challenges, we design a detection-driven cooperative dispatching framework, called DECO. Specifically, we design (i) a Received Signal Strength Indicator (RSSI) variance-based state encoder to model encounter dynamics, (ii) an encounter event selector to choose encounter scenarios, (iii) a time-constrained order mask module to filter unsuitable orders, and (iv) an encounter-aware order transfer scheduler to make detailed order transfer decisions. Extensive experiments on real-world data from two large companies (i.e., JD Logistics, Eleme) show that DECO outperforms other baselines.Real-world deployment results at JD Logistics show that DECO improves the order overdue rate by 4.8%.

LoRa has been widely adopted in Internet of Things (IoT) due to its long distance and low cost. With the largescale deployment of LoRa devices, it is not uncommon that multiple nodes transmit concurrently, leading to packet collisions and degraded performance. Previous studies have focused on examining single or multiple features in the received raw signals, named as chirp-level features, to separate collided packets for parallel decoding. However, the accuracy of feature extraction turns out to be vulnerable to interference, which can lead to incorrect packet decoding as network concurrency increases. Our study reveals that, other than the chirp-level features, a standard LoRa packet encoder introduces coding correlations across symbols of the same packet and thus leaves packet-level features to the symbols that can be utilized to disentangle symbols of collided packets in a new dimension. In this work, we introduce DeepDetangle, a Deep-learning-based feature fusion framework that efficiently fuses both packet-level and chirp-level features of symbols to enhance LoRa parallel decoding. DeepDetangle utilizes Complex-CNN and LSTM structures to capture multidimensional chirp-level features, their joint distributions, and temporal patterns. An MLP is employed to aggregate the chirplevel features with the packet-level features, thereby enabling the decoding of symbols on a per-block basis. By integrating features from both levels, erroneous symbols that cannot be recovered with chirp-level features alone can now be effectively corrected with other valid ones in the same block. Therefore, it demonstrates a strong capability to combat interference from other packets. Extensive evaluations have been conducted to assess the performance of DeepDetangle. The results indicate that DeepDetangle achieves$\mathbf{1 8. 1 \%}$to$\mathbf{8 0. 5 \%}$higher network throughput compared to existing works of similar complexity.

LoRa technology has garnered significant attention for its exceptional performance in city-wide applications. LoRa encodes data across multiple samples to enable long-range communication, with the level of redundancy controlled by the Spreading Factor (SF). However, practical limitations restrict how high the SF can be set. To overcome communication challenges at the highest allowable SF settings, we introduce SF-any, a software-based coding paradigm that extends an SFk packet to a quasi-SF(k + m) packet. SF-any encodes a quasi-SF(k + m) symbol with 2mSFk symbols. Hardware imperfections introduce time-varying frequency drifts and phase offsets, resulting in frequency leakage during quasi-SF(k +m) packet decoding. To mitigate this, we strategically insert pilots into the packet for imperfection estimation and compensation. Additionally, to maintain and exploit the coding structure in LoRa PHY, we employ a grouped repetition code at the transmitter and a joint demodulation and decoding scheme at the receiver. Comprehensive evaluations demonstrate that SF-any’s performance seamlessly scales with increasing SF, achieving up to a 14dB improvement over SF12 packets (the highest SF in LoRa PHY), and up to a 12dB improvement compared with state-of-the-art approaches.

Logistics advertising is an emerging task in online-to-offline logistics systems, where logistics companies expand parcel shipping services to new users through advertisements on shopping websites. Compared to existing online e-commerce advertising, logistics advertising has two significant new characteristics: (i) the complex factors in logistics advertising considering both users' offline logistics preference and online purchasing profiles; and (ii) data sparsity and mutual relations among multiple steps due to longer advertising conversion processes. To address these challenges, we design MCAC, a Multi-task Conditional Attention network-based logistics advertising Conversion prediction framework, which consists of (i) an offline shipping preference extraction model to extract the user's offline logistics preference from historical shipping records, and (ii) a multi-task conditional attention-based conversion rate prediction module to model mutual relations among multiple steps in logistics advertising conversion processes. We evaluate and deploy MCAC on one of the largest e-commerce platforms in China for logistics advertising. Extensive offline experiments show that our method outperforms state-of-the-art baselines in various metrics. Moreover, the conversion rate prediction results of large-scale online A/B testing show that MCAC achieves a 15.22% improvement compared to existing industrial practices, which demonstrates the effectiveness of the proposed framework.

To improve the efficiency of multi-agent systems in the Internet of Things, multi-agent reinforcement learning (MARL) has been extensively studied. Although transformer-based models now treat decision-making in MARL as a sequence problem and achieve advanced performance, the action of agents often depends on previous states without direction in information sharing. To address this issue, we propose a Bi-directional Sequence Inference framework for Multi-Agent Reinforcement Learning (BSI-MARL), consisting of three components: Action-Observation Processing Module, Sequence Inference Module, and Policy Optimization Module. The Action-Observation Processing Module defines the state space, action space, and reward function for the agents. Based on the Transformer model, BSI-MARL designs an encoder-decoder module for bi-directional sequence inference to generate action sequences for multi-agent decisions. Additionally, the policy gradient optimization module broadens the action sampling window, improving training efficiency. The experiments conducted on Mujoco-Half Cheetah and Google Research Football demonstrate that BSI-MARL exhibits excellent performance in multi-agent decision-making and good stability and generalization ability.

LoRa Wide Area Network (LoRaWAN) is famous for its low power consumption and wide coverage area. A critical issue that constrains the scalability of LoRaWAN is how to support concurrent packet reception efficiently. To this end, our work first carefully investigates all the hardware imperfections between a LoRa transceiver pair and studies their impacts on the received signal's temporal patterns with fine granularity. Such imperfections and the associated temporal patterns are intrinsic and unique for any transceiver pair in a wireless system. Therefore, they provide a brand-new and highly influential perspective for identifying different packets. Motivated by this, we propose Magnifier, which integrates the two factors mentioned above for LoRa concurrent decoding. Though some prior work leverage partial hardware imperfections, they fail to systematically study and exploit the temporal patterns caused by the imperfections for concurrent packet reception. We also evaluate the performance of Magnifier with 40 transmitters (commodity LoRa chips) and one receiver (USRP B210). Both critical complexity analysis and extensive experiments show that with the same hardware settings and the same scale of complexity, Magnifier can support 3× to 8× throughput of other existing schemes.

On-demand delivery has experienced rapid growth in recent years, revolutionizing people's lifestyles with its timeliness and convenience. The order dispatch process in on-demand delivery isconcurrent, wherein couriers continuously accept new orders and deliver them to customers within strict time constraints and dynamic demand and supply. Most of the existing order dispatch mechanisms are designed for independent dispatch or concurrent dispatch without strict deadlines, rendering them unsuitable for real-time concurrent dispatch in on-demand delivery. To address the challenge, we propose aTime-ConstrainedActor-Critic Reinforcement learning based concurrent dispatch system calledTCAC-Dispatchto reduce the overdue rate and enhance the long-term revenue. Specifically, we first design a deep matching network (DMN) with a variable action space, which integrates both states embedding (including route behaviors encoding) and actions' embedding into a long-term value for dispatching decisions. Additionally, we design a time-constrained action pruning module to ensure compliance with time constraints. Then we utilize the Actor-Critic framework to tackle the concurrent dispatch considering strict time constraints and stochastic demand-supply. To further optimize the efficiency and delivery resource utilization, we propose an extension of TCAC (i.e., TCAC+), which consists of (i) a learning-based order service time prediction module to determine whether to relax the deadline of some orders; and (ii) a multi-critic framework to optimize concurrent order dispatch with both tight deadlines and relaxed deadlines using dynamic weighting mechanism. We evaluate the TCAC-Dispatch with one-month data involved with 36.48 million orders and 42,000 couriers collected from Eleme, one of the largest on-demand delivery companies in China. Experiments are conducted on a data-driven emulator deployed on the development environment of Eleme and the results demonstrate that our method outperforms state-of-the-art baselines with various metrics in both tight deadline and mixed deadline scenarios.

As an emerging Low-Power Wide Area Networks (LPWAN) technology, LoRa is dedicated to providing long-range connections for pervasive Internet-of-Things devices. As LoRa operates in the unlicensed spectrum with an ALOHA-based MAC-layer protocol stack, transmissions from multiple LoRa end-devices inevitably collide with each other, leading to packet losses and increased transmission delay. Targeting at collisions caused by interferences under thesamespreading factor (SF) settings, researchers introduce multiple lines of techniques. Despite their efforts, these techniques commonly neglect the potential collisions caused by interferences underdifferentSF settings, resulting in imperfect orthogonality. Given the disparate transmission power configurations and diverse deployed locations, the collisions under different SFs commonly exist in practical networks and significantly limit the LoRa reliability. This paper presents X-MAC, the first scheduler aware of imperfect orthogonality. Technically, X-MAC detects the collisions under different SFs via tracking historical transmissions, and performs dynamic channel scheduling to avoid collisions caused by interferences under the same and different SFs. Extensive evaluations on testbed devices show that, compared with the state-of-the-art methods, X-MAC boosts the network scalability (number of concurrent end-devices) by 1.26× to 2.41× with packet reception rate requirement of > 95%.

Low-Power Wide-Area Networks (LPWANs), extensively utilized for connecting billions of IoT devices, encounter wireless interference challenges in unlicensed frequency bands. Cutting-edge research suggests employing Received Signal Strength Indication (RSSI) sequences for error detection to mitigate interference-related issues. Nevertheless, the effectiveness of this method significantly declines under low signal-to-noise ratios (SNRs). Additionally, long-range communication often results in low SNR received signals, sometimes even below the noise floor. Targeting this fundamental issue, this article proposes the LPWAN packet technique, broadly applicable across diverse scenarios through edge–cloud collaboration. On the edge side, we propose an innovative architecture that fully exploits spatial distribution and interference independence in the field. Rather than utilizing resource-intensive RSSI-based error detection, we leverage a lightweight coding scheme for error detection at the Long Range (LoRa) edge, forwarding correct frames to the cloud. On the cloud side, packet recovery is achieved utilizing group-weighted voting. We design and implement ECRLoRa with commercially available devices (SemTech’s SX1278 and SX1302 LoRa chipsets) and assess its performance in low SNR environments. Our thorough evaluation demonstrates that our approach attains a Packet Recovery Ratio of 96% with low SNR (i.e., below −10 dB), resulting in 1.8× throughput, 7.5× faster recovery time, and 4.92× average accuracy compared to state-of-the-art cloud-optimized application layer solutions.

Route prediction in instant delivery is still challenging due to the unique characteristics compared with conventional delivery services, such as strict deadlines, overlapped delivery time of multiple orders, and diverse individual preferences on delivery routes. Recently, development in the mobile Internet of Things (IoT) offers the opportunity to collect multi-sensor data with rich real-time information. Therefore, this study proposes a route prediction model called Roupid, which leverages multi-sensor data to improve the accuracy of route prediction in instant delivery. Specifically, we design a 3-Conversion Network-based route prediction framework to take full advantage of various information provided by multi-sensor data, including the encounter data sensed by Bluetooth low energy (BLE) beacons, active site data reported by smart handheld devices, and trajectory data detected by GPS. The 3-Conversion Network we propose is based on a deep neural network framework, which integrates an improved relational graph attention network with edge features (RGATE) to encode global information that couriers typically consider when planning routes. We evaluate our Roupid with real-world data collected from one of the largest instant delivery companies in the world, i.e., Eleme. Experimental results show that our Roupid outperforms other state-of-the-art baselines and offers up to 85.51% of the route prediction precision.

Fine-grained community-building information, such as building names and accurate geographical coordinates, is critical for a range of practical applications like navigation and door-to-door services (e.g., on-demand delivery and last-mile delivery). A common practice of traditional methods to gather community-building information usually relies on manual collection, which is typically labor-intensive and time-consuming. To address these issues, we utilize the massive data generated from e-commerce delivery services and design a framework, AutoBuild, for fine-grained large-scale community-building labeling. AutoBuild consists of two main components: (i) a Location Candidate Detection Module that identifies potential building names and coordinates from multi-source delivery data, and (ii) a Progressive Building Matching Model that employs trajectory modeling, human behavior analysis, and heterogeneous graph alignment to match building names and coordinates. To evaluate the performance of AutoBuild, we applied it to two real-world multi-modal datasets from Beijing City and Chengdu City. The results reveal that AutoBuild significantly outperforms multiple baseline models by 50-meter accuracy of 81.8% and 100-meter accuracy of 95.9% in Beijing City. More importantly, we conduct a real-world case study to demonstrate the practical impact of AutoBuild in last-mile delivery.

Points of Interest (POIs), such as entertainment, dining, and living, are crucial for urban planning and location-based services. However, the high dynamics and expensive updating costs of POIs pose a key roadblock for their urban applications. This is especially true for developing countries, where active economic activities lead to frequent POI updates (e.g., merchants closing down and new ones opening). Therefore, POI updating, i.e., detecting new POIs and different names of the same POIs (alias) to update the POI database, has become an urgent but challenging problem to address. In this paper, we attempt to answer the research question of how to detect and update large-scale POIs via a low-cost approach. To do so, we propose a novel framework called UrbanPOI, which formulates the POI updating problem as a tagging and detection problem based on multi-modal logistics delivery data. UrbanPOI consists of two key modules: (i) a hierarchical POI candidate generation module based on the POINet model that detects POIs from shipping addresses; and (ii) a new POI detection module based on the Siamese Attention Network that models multi-modal data and crowd intelligence. We evaluate our framework on real-world logistics delivery datasets from two Chinese cities. Extensive results show that our model outperforms state-of-the-art models in Beijing City by 26.2% in precision and 10.7% in F1-score, respectively.

Warehouse-distribution integration has been adopted by many e-commerce retailers (e.g., Amazon, TAOBAO, and JD) as an efficient business mode. In warehouse-distribution integration e-commerce, one of the most important problems is to estimate the full-link delivery time for better decision-making. Existing solutions for traditional warehouse-distribution separation mode are challenging to address this problem due to two unique features in the integration mode including (i) contextual influence caused by neighbor units in heterogeneous delivery networks, (ii) uncertain delivery time caused by the dynamic temporal data (e.g., online sales volume) and heterogeneity of delivery units. To incorporate these new factors, we propose Heterogeneous Spatial-Temporal Graph Transformer (HST-GT), a novel full-link delivery time estimation method under the warehouse-distribution integration mode, where we (i) develop heterogeneous graph transformers to capture hierarchical heterogeneous information; and (ii) design a set of spatial-temporal transformers based on heterogeneous features to fully exploit the correlation of spatial and temporal information. We extensively evaluate our method based on one-month real-world data consisting of hundreds of warehouses and sorting centers, and millions of historical orders collected from one of the largest e-commerce retailers in the world. Experimental results demonstrate that our method outperforms state-of-the-art baselines in various metrics.

Nowadays, the 802.11ax protocol is widely adopted in the local area networks. Compared with the former version of 802.11 standards, 802.11ax brings a new power-saving mechanism named TWT (Target Wake Time). In this paper, we conduct a comprehensive measurement study on how TWT mechanism performs on the commercial-off-the-shelf devices in our daily life. To me more specific, we focus on the impact on power consumption, network performance and stability of TWT mechanism on the smartphones. Counterintuitively, we find that TWT mechanism is not as power-saving as we thought in the experimental setup we built, and it also poses nagative impacts on the network stability. We further perform a root-cause analysis to find the rationale behind the measurement results and we also summarized the implications and suggestions to the stakeholders of 802.11ax.

LoRa Wide Area Network (LoRaWAN) has emerged as a dominant technology for Low Power Wide Area Networks (LPWAN). However, due to the ever-growing network size, packet collisions caused by concurrent transmissions have become a serious challenge in LoRa Wan.Existing studies have either ignored the issue by exploring only a few inaccurate features or addressed it using a complex receiver with up to eight antennas. To strike a better balance between implementation cost and system performance, we propose Hi2LoRa, which leverages highly dimensional and highly accurate features for LoRa concurrent decoding with only two receiving antennas. The feature dimensions are extended by exploring various types of hardware imperfections and channel state information inherent to each transceiver pair. To improve feature accuracy, low pass filters and BiLSTM networks are employed to trace and learn their temporal patterns. Additionally, an effective collision suppression strategy is introduced to combat feature corruption from other concurrent packets. Extensive evaluations on real-world testbeds show that the achievable concurrency in Hi2LoRa is either close to that of state-of-the-art approaches with much higher complexity (e.g., using eight antennas) or 2.7 x of prior work with comparable complexity (e.g., using two antennas).

Wireless Charging Vehicles (WCVs) have been widely explored as a means of enabling continuous operation of sensors that are powered by batteries. However, the energy consumption of WCVs can be inefficient, leading to insufficient energy supply for sensors that are located in challenging-to-access areas. Consequently, there is a need to design an effective charging and energy sharing scheme for sensors to improve the quality of service in this setup. This paper focuses on the Joint optimization of Mobile charging and Energy sharing of sensors (JOIN-ME) problem, which is known to be NP-hard. To address this challenge, we first transform JOIN-ME into a submodular maximization problem with general constraints. Subsequently, we propose the Routing planning, Mobile charging, and Energy sharing for Sensing devices (RMES) algorithm, which has an approximation ratio of 1/8(1-1/e). Finally, we conduct experiments to showcase the superior performance of RMES compared to existing baselines, under varying scales and constraints. Our work on the design of an efficient charging and energy sharing scheme for sensors can significantly improve the reliability and longevity of wireless sensor networks, enabling the deployment of these networks in critical applications such as environmental monitoring, crowd sensing, and security surveillance.

Order Transfer from the transfer center to delivery stations is an essential and expensive part of the logistics service chain. In practice, one vehicle sends transferred orders to multiple delivery stations in one transfer trip to achieve a better trade-off between the transfer cost and time. A key problem is generating the vehicle’s route for efficient order transfer, i.e., minimizing the order transfer time. In this paper, we explore fine-grained delivery station features, i.e., downstream couriers’ remaining working times in last-mile delivery trips and the transferred order distribution to design a Prediction-and-Scheduling framework for efficient Order Transfer called PSOT, including two components: i) a Courier’s Remaining Working Time Prediction component to predict each courier’s working time for conducting heterogeneous tasks, i.e., order pickups and deliveries, with a context-aware location embedding and an attention-based neural network; ii) a Vehicle Scheduling component to generate the vehicle’s route to served delivery stations with an order-transfer-time-aware heuristic algorithm. The evaluation results with real-world data from one of the largest logistics companies in China show PSOT improves the courier’s remaining working time prediction by up to 35.6% and reduces the average order transfer time by up to 51.3% compared to the state-of-the-art methods.

The popularity of online e-commerce has promoted the rapid development of last-mile logistics in recent years. In last-mile services, to ensure delivery efficiency and enhance user experience, the delivery zone is proposed to perform delivery task assignment, which is a fundamental part of last-mile delivery. Each courier is responsible for one delivery zone. Couriers will collect orders belonging to their delivery zones from the delivery station and deliver orders to customers. Existing delivery zone partition practices in last-mile logistics consist of manual experience-based and static optimization-based methods, which perform order amount balancing among different zone but suffer from dissatisfaction and inefficiency because of two limitations: (i) using order amount is not always a good balancing metric considering deliveries' various difficulties (e.g., residence or industrial park, with or without elevators); (ii) less considering couriers' familiarity and preference behaviors. To generate delivery zone partition with equitable workload assignment, in this paper, we propose E-partition, a data-driven delivery zone partition framework to achieve equitable workload assignment in last-mile logistics. We first design a learning-based workload prediction model to estimate service time given a partition plan that consists of unseen courier-zone matching scenarios. Then, a delivery zone partition algorithm is proposed to iterative optimize couriers' core-AOI (i.e., area of interest) generation and AOI assignment process. Extensive offline experimental results show that our model outperforms baselines in working time prediction and workload balancing performances. Real-world deployment results at JD Logistics also verify the effectiveness of equitable-assignment aware delivery zone partition, with a 2.2% increase in service on-time rate compared to state-of-practice partition solutions.

In recent years, emergency last-mile logistics (ELML) have played an essential role in urban emergencies. The efficient allocation of couriers in ELML is of practical significance to ensure the supply of essential materials, especially in public health emergencies (PHEs). However, couriers allocation becomes challenging due to the instability of demand, dynamic supply comprehension, and the evolutional delivery environment for ELML caused by PHEs. While existing work has delved into couriers allocation, the impact of PHEs on demand-supply-delivery has yet to be considered. In this work, we design PTOCA, a Predict-Then-Optimize Couriers Allocation framework. Specifically, in the prediction stage, we design a resource-aware prediction module that performs spatio-temporal modeling of unstable demand characteristics using a variational graph GRU encoder and builds a task-resource regressor to predict demand accurately. In the optimization stage, firstly, the priority ranking module solves the matching of delivery resources under demand-supply imbalance. Then the multi-factor task allocation module is used to model the dynamic evolutional environment and reasonably assign the delivery tasks of couriers. We evaluate PTOCA using real-world data covering 170 delivery zones, more than 10,000 couriers, and 100 million delivery tasks. The data is collected from JD Logistics, one of the largest logistics service companies. Extensive experimental results show that our method outperforms the baseline in task delivery rate and on-time delivery rate.

Community group-buying is an emerging shopping model in which individuals within the same community collectively purchase daily necessities at lower prices. The logistics transportation in this scenario requires higher turnover rates and timeliness compared to traditional online shopping. Therefore, making efficient vehicle dispatch decisions is necessary to improve delivery efficiency and reduce transportation costs. However, uncertainties in orders and complex dependencies between multi-stage decisions in the community group-buying scenario challenge the scheduling of delivery vehicles. In this paper, we propose a vehicle dispatch system for community group-buying logistics based on a predict-then-optimize process, which incorporates a demand prediction module and a vehicle dispatch module. In the prediction module, we categorize goods and predict the total quantity of each category using a multi-layer perceptron (MLP). In the vehicle dispatch module, we model the vehicle dispatch process as a reinforcement learning problem and use an action masking mechanism to prune the policy search space. Experimental results demonstrate that the vehicle dispatch system achieves state-of-the-art performance compared to several popular baselines across three different datasets. Our system reduces transportation costs by at least 8.89% and improves decision efficiency by at least 10%. Moreover, it behaves close to the approximate optimal solution in most cases.

Time synchronization is a fundamental requirement for wireless communication systems to work properly. Most of the existing studies focus on time synchronization among homogeneous devices. This work investigates time synchronization with heterogeneous technologies (e.g., WiFi, ZigBee, and Bluetooth) which is important for the rising Internet of Thing (IoT) scenarios where heterogeneous devices coexist. Recent advances in cross-technology communication (CTC) break the wall between heterogeneous wireless devices. In this work, we propose a new time synchronization strategy based on the CTC technique and provide a technique called TimeBee, which takes the advantage of coordination from a WiFi device to assist ZigBee devices for time synchronization. An effective method is employed so that ZigBee nodes are coordinated for time synchronization based on the received timestamps from WiFi devices. The experimental results show that TimeBee achieves global time synchronization with low time errors.

Federated learning (FL) is a machine learning technique that allows for on-site data collection and processing without sacrificing data privacy and transmission. Heterogeneity is a key challenge in federated settings. Recently, cross-technology communication (CTC) has emerged as a solution for Internet of Things (IoT) heterogeneity, enabling direct communication between different wireless devices without the need for hardware modifications or gateway intervention. For example, a sophisticated WiFi device can serve as a central coordinator for other heterogeneous devices, such as LoRa, ZigBee, Bluetooth, and LTE, leading to more efficient and ubiquitous cross-network information exchange. However, heterogeneous wireless technologies present different data transmission rates and computing resources, making it difficult to achieve high accuracy in predictions due to large amounts of multidimensional data, communication delays, transmission latency, limited processing capacity, and data privacy concerns. In this work, we propose an FL framework based on CTC for heterogeneous IoT applications, called FLCTC. To demonstrate the usability of FLCTC, we implemented FLCTC and a specific solution for forest fire prediction. FLCTC was concretely implemented as a federal deep learning based on long and short-term memory and used for forest fire prediction, addressing the challenge of data characterization in heterogeneous IoT networks. FLCTC promises to improve communication efficiency and prediction accuracy. Our platform-based evaluation results show that FLCTC is feasible, with a recall of 96% and an accuracy of 88%, offering valuable insights into the use of FL with CTC for heterogeneous IoT applications.

In recent years, receiver-driven transport protocols have been proposed to use proactive congestion control to meet the stringent latency requirements of large-scale applications in data center. However, the receiver-driven proposals face the challenges brought by network dynamic. First, when the bursty flows start, the aggressive and blind line-rate transmission in the first RTT easily leads to persistent queue backlog. Second, when some flows finish transmissions, the remaining ones cannot increase their sending rates to seize the available bandwidth. To address these problems, this article presents a new receiver-driven congestion control design, called REN, which uses the under- and over-utilization notifications from switch to handle the dynamic traffic. With the aid of explicit feedback, REN alleviates the traffic burstiness due to aggressive start, mitigates the conservativeness in utilizing available bandwidth, and still retains the receiver-driven feature to achieve ultra-low latency. We implement the prototype of REN using DPDK. The experimental results of real testbed and large-scale NS2 simulation show that REN effectively reduces the average flow completion time (AFCT) by up to 68% over the state-of-the-art receiver-driven transmission schemes.

With the rapid development of sharing economy, we have access to massive sharing systems such as Uber, Airbnb, and bike sharing nowadays. The sharing economy, at its core, is to achieve efficient use of resources. However, the actual usage of shared resources is still unclear to us. Little measurement or analysis, if any, has been conducted to investigate the resource usage patterns with the large-scale data collected from these sharing systems. In this paper, we first analyze the shared bike usage patterns in three typical bike sharing systems based on 140-month multi-event data. From our data-driven analysis, we found that the most used 20% of shared bikes account for 45% of total usage, while the least used 20% of bikes account for less than 1% of usage. To efficiently utilize shared bikes, we propose a usage balancing design called eShare+ to improve the bike sharing systems by considering both the quality of service and bike maintenance, which includes three key components: (i) a statistical model based on archived data to infer historical usage; (ii) an entropy and contextual LSTM-based prediction model with both real-time and archived data to infer future usage; (iii) a model-driven optimal calibration engine for bike selection to dynamically balance usage. We develop an ID swapping-based evaluation methodology to measure the efficiency of eShare+ with data from three large-scale bike sharing systems including 84,000 bikes and 3,300 service stations. Our results show that eShare+ not only fully utilizes shared bikes with efficient maintenance but also improves the quality of service. In addition, eShare+ also has the potential to be applicable to different fleet sizes.

With the rapid growth of the number of private vehicles, searching for accessible parking spaces becomes intractable for drivers, especially during high-demand hours. In recent years, we are witnessing a number of sharing economy services. Contract parking sharing, as an innovative sharing economy mode, has the potential to alleviate the difficult parking issue and make full use of the urban parking resources. However, the uncertainties of both drivers’ parking demand and owners’ sharing supply make it challenging to achieve efficient sharing. Thanks to IoT technology, many current parking lots now record vehicles’ fine-grained parking data for billing purposes. Leveraging these fine-grained parking data, we exploit available contract parking spaces to share them with drivers that have temporary parking demand. Specifically, we propose$\mathrm{W^{2}}$Parking, awin-win contractparkingsharing system, which includes two key components: (i) an idle time prediction model to estimate available periods of parking spaces and (ii) a parking sharing model to schedule temporary users to have access to these available parking spaces under both demand and supply uncertainties using dynamic programming combined with a 2-approximation algorithm with performance-bound guarantees. we evaluate our system on seven-month real-world parking data from 368 parking lots with 14,704 parking spaces. Extensive experimental results show that our$\mathrm{W^{2}}$Parking achieves more than 90% of accuracy in parking time prediction, and the utilization rate of contract parking spaces is improved by 35%.

With the rapid development of cities, heterogeneous urban cyber-physical systems are designed to improve citizens’ experience, e.g., navigation and delivery service. However, the integration of services is not designed for disruptive events, an oversight that has rippling effects on service quality. For example, urban transportation systems consist of multiple transport modes that have complementary characteristics of capacities, speeds, and costs, facilitating smooth passenger transfers by planned schedules. Such integration may experience significantly increased delays during disruptions. Current solutions rely on a substitute service to transport passengers from and to affected areas using ad-hoc schedules and static routes, which are inefficient and do not utilize mobility patterns of mobile systems, e.g., dynamic passenger demand. To coordinate heterogeneous transportation systems under disruptions, we design a service to automatically select and integrate part of three systems (subway, bus, and taxi) using systems’ mobility patterns, e.g., predicted supply and demand. The service is presented in a normal version, eRoute, considering both subway and bus, and in a version taking taxis into account, called enhanced eRoute. We implement and evaluate eRoute with datasets including subway, bus and taxi, and a fare collection system. The data-driven evaluation results show that eRoute improves the ratio of served passengers per time interval by up to 11.5 times and reduces the average traveling time by up to 82.1 percent compared with existing solutions.

Existing reactive or proactive congestion control protocols are hard to simultaneously achieve ultra-low latency and high link utilization across all workloads ranging from delay-sensitive flows to bandwidth-hungry ones in datacenter networks. We present an Anti-ECN (Explicit Congestion Notification) Marking Receiver-driven Transport protocol called AMRT, which achieves both near-zero queueing delay and full link utilization by reasonably increasing sending rate in the case of under-utilization. Specifically, switches mark the ECN bit of data packets once detecting spare bandwidth. When receiving the anti-ECN marked packet, the receiver generates the corresponding marked grant to trigger more data packets. The testbed and simulation experiments show that AMRT effectively reduces the average flow completion time (AFCT) by up to 42% and improves the link utilization by up to 38% over the state-of-the-art receiver-driven transmission schemes.

We report a 30-month nationwide deployment and operation study of an indoor arrival detection system based on Bluetooth Low Energy calledVALIDin 364 Chinese cities.VALIDis pilot-studied, deployed, and operated in the wild to infer real-time indoor arrival status of couriers, and improve their status reporting behavior based on the detection. During its full nationwide operation (2018/12-2021/01),VALIDconsists of virtual devices at 3 million shops and restaurants, where 530,859 of them are in multi-story malls and markets to infer and influence 1 million couriers’ behavior, and assist the scheduling of 3.9 billion orders for 186 million customers. Although indoor arrival detection is straightforward in controlled environments, the scale of our platform makes the cost prohibitively high. In this work, we explore to use merchants’ smartphones under their consent as a virtual infrastructure to design, build, deploy, and operateVALIDfrom in-lab conception to nationwide operation in three phases for 30 months. We consider metrics including system evolution, reliability, utility, participation, energy, privacy, monetary benefits, along with couriers’ behavior changes. We share three lessons and their implications for similar wireless sensing or communication systems with large geospatial operations.

Datacenter networks provide large bisection bandwidth by load balancing traffic over rich parallel paths in multi-rooted tree topologies. Nevertheless, production datacenters operate under various path diversities caused by traffic dynamics, hardware failures and heterogeneous switching equipment. Therefore, the load balancing schemes in data center should be resilient to network asymmetry. Prior fine-grained schemes such as RPS and Presto are prone to experience packet reordering problem under asymmetric topology since they split flows into small units which are spread across all parallel paths. The coarse-grained solutions such as ECMP and LetFlow effectively avoid packet reordering, but easily leading to under-utilization of multiple paths. To solve these problems, we propose a load balancing mechanism called AG, which adaptively adjusts switching granularity according to the asymmetric degree of multiple paths. AG increases switching granularity to alleviate packet reordering under large degrees of topology asymmetry, while reducing switching granularity to obtain high link utilization under small degrees of topology asymmetry. Moreover, we design a switch-based scheme which measures the difference of one-way delay of multiple paths to obtain accurate state of topology asymmetry with low overhead. AG is a practical switch-based solution without modification at end hosts. The experimental results of NS2 simulations and real implementation show that AG reduces the average and$99^{th}$flow completion time by up to 54% and 65% compared with the state-of-the-art load balancing schemes, respectively.

Addressing edge computing's economic issues is critical as we need to motivate edge devices as resource providers to devote their computing resources to the service. There are multiple users and resource providers in most edge computing service scenarios. The communication delays between users and providers are not the same since their physical distances are different. However, most existing works on edge computing regarding network economics adopt single market models that do not consider the influence of communication delay. Moreover, due to the high cost of deploying 5G ultra-dense small cells, barely a network operator can reach full network coverage. Users cannot rely on a single network, but existing multi-market models do not allow resource trading between different groups. Thus, in this paper, we propose a novel multi-market trading (MMT) framework to address these shortcomings. The framework combines the double auction at each group and a market selection game to enable the resource providers to participle in multiple auctions and analyze their behavior of choosing markets. Through extensive simulations using real-world datasets of vehicular networks, we show that the proposed framework can improve the social welfare by 14.45% and 36.74%, respectively, compared with classic multi-market and single market models.

Region-level sales prediction is an essential task in the e-commerce industry. Accurate demand prediction enables enterprises to respond to future sales changes in time, thereby saving resources and improving efficiency. Existing regional sales prediction solutions focus on utilizing single-source temporal features (e.g., date types and historical sales data) to conduct time-series forecasting, which have not yet modeled the correlations of features among intra and inter regions explicitly (e.g., the regional population, age structure, sex ratio, and spatial correlations of multi-regions). In this paper, we propose a novel long-term regional sales prediction framework to take the Intra- and Inter-region features' correlations into consideration while making long-term region sales prediction. Specifically, the Intra- and Inter-region features are first encoded by the graph convolutional network (GCN), which simultaneously considers static features and contextual information of similar regions during the encoding process. Then, we design a transformer-based model to conduct sales prediction considering both Intra- and Inter-region features embeddings and long-term temporal features. To show the effectiveness of our model, we evaluate our method based on 8-month real-world data consisting of 389 regions and 312 million sales records from one of the largest e-commerce platforms in China. The experimental results show that the prediction results are significantly improved by an average of 20% compared with other state-of-the-art baselines.

The analysis of express trajectory is essential for delivery service optimization and courier management. Express trajectory consists of a large amount of community paths which is different from the trajectory of transportation tools such as taxis which run in the main road of a city. Due to the complexity of the community road networks and the energy constraint of devices, trajectories are collected under a low sampling rate and accuracy. These trajectories need to be recovered and mapped to the road networks for further analysis. Current recovery approaches utilize two-stage or end-to-end models to generate the upsampled trajectories. These methods fail to fully exploit the periodicity relation in historical data, which leads to accuracy losses for complex community road networks. In this paper, we design PATR, a periodicity-aware Seq2Seq model, to recover the couriers' trajectories by leveraging the periodical patterns of the historical data. We conduct experimental evaluations based on real-world GPS data of JD logistics consisting of 836,959 points and 25,726 road segments, and our model outperforms the state-of-the-art baselines by reducing recovery error by 2.4%-21.9%.

The emergence of Online-to-Offline (O2O) stores based on delivery platforms (e.g., Uber Eats, DoorDash, and Eleme) provides great convenience to people's lives. In the O2O model, one of the essential problems for merchants is to select a suitable store site, i.e., store site recommendation problem. We argue that the existing works for the traditional brick-and-mortar stores cannot address this problem due to two unique factors in the O2O model including (i) dynamic supply caused by courier capacity and dispatching strategies and (ii) various customer demands caused by delivery distance and customer preferences. To incorporate these new factors, we design$O^{2}$SiteRec, a store site recommendation method under the O2O model via multi-graph attention networks, which consists of (i) a courier capacity model based on a multi-semantic relation graph attention network to capture courier capacity; (ii) a heterogeneous multi-graph based recommendation model, where the courier capacity, customer preferences, and context features are fused. We evaluate our method based on one-month real-world data consisting of 39,465 stores and 23.6 million orders from one of the largest O2O platforms in China. Experimental results demonstrate that our method outperforms state-of-the-art baselines in various metrics.

As an emerging Low-Power Wide Area Networks (LPWAN) technology, LoRa is dedicated to providing long-range connections for pervasive Internet-of-Things devices. As LoRa operates in the unlicensed spectrum, transmissions from multiple LoRa end-devices inevitably collide into each other, leading to packet losses and increased transmission delay. Targeting at collisions caused by interferences under the same spreading factor (SF) settings, researchers introduce multiple lines of techniques. Despite their efforts, these techniques commonly neglect the potential collisions caused by interferences under different SF settings, which are resulted by the imperfect orthogonality. Given the disparate transmission power configurations and diverse deployed locations, the collisions under different SFs commonly exist in practical networks, and significantly limit the LoRa reliability. In this paper, we present X-MAC, the first scheduler that is aware of imperfect orthogonality. Technically, X-MAC detects the collisions under different SFs via tracking historical transmissions, and further performs dynamic channel scheduling to avoid collisions caused by interferences both under the same and different SFs. Extensive evaluations on testbed devices show that, compared with the state-of-the-art methods, X-MAC boosts the network scalability (number of concurrent end-devices) by 2.41× with packet reception rate (PRR) requirement of > 95%.

As a representative technology of low power wide area network, LoRa has been widely adopted to many applications. A fundamental question in LoRa is how to improve its reception quality in ultra-low SNR scenarios. Different from existing studies that exploit either spatial or temporal correlation for LoRa reception recovery, this paper jointly leverages the fine-grained spatial-temporal correlation among multiple gateways. We exploit the spatial and temporal correlation in LoRa packets to jointly process received signals so that the fine-grained offsets including Central Frequency Offset (CFO), Sampling Time Offset (STO) and Sampling Frequency Offset (SFO) are well compensated, and signals from multiple gateways are combined coherently. Moreover, a deep learning based soft decoding scheme is developed to integrate the energy distribution of each symbol into the decoder to further enhance the coding gain in a LoRa packet. We evaluate our work with commodity LoRa devices (i.e., Semtech SX1278) and gateways (i.e., USRP-B210) in both indoor and outdoor environments. Extensive experiment results show that our work achieves 4.6dB higher signal-to-noise ratio (SNR) and 1.5× lower bit error rate (BER) compared with existing approaches.

This paper presents our experience in adopting recent research results of mobile phone based indoor/outdoor detection (IODetector) to support the real world business of on-demand food delivery. The real world deployment of the adopted IODetector involves three phases spanning 20 months, during which the deployment scales from a feasibility study across a few areas of interest to a city-wide trial in Shanghai, and eventually to nationwide deployment over 367 cities in China. Iterative development has been performed throughout different deployment phases to excel the IODetector. Large scale evaluation and comparative A/B testing suggest key value of adopting indoor/outdoor detection in the real world business. We also present the lessons learned from the deployment experience including real world know-hows, practical limits and constraints, as well as discussions on design alternatives. We believe this paper provides insights to guide future efforts in translating research results to industry adoptions.

Industrial Scientific Medical (ISM) band has become more and more crowded due to the ever-growing size of many mainstream technologies, e.g., Wi-Fi, ZigBee and Bluetooth. Though the coexistence issue has led to severe Cross Technology Interference (CTI), it provides great opportunities to better utilize the scarce bandwidth resources. A fundamental question is how to ensure harmonious and effective operations for different networks To exploit it, a novel global cooperation framework is proposed. In particular, our work enables reliable concurrent Cross Technology Communication (CTC) from Wi-Fi to Wi-Fi, ZigBee and Bluetooth commodity devices. Compared to existing CTC approaches, our scheme improves the communication efficiency significantly, and hence is the foundation for effective global cooperation. Based on the proposed CTC scheme, a unified Media Access Control (MAC) approach is introduced to cooperate CTC message transmission and reception for heterogeneous networks with different MACs. Three proof-of-concepts applications, e.g. global synchronization, global CTI coordination and global Location Based Service (LBS) broadcasting are discussed to fully leverage the benefits of global cooperation. Extensive evaluations show that compared with existing schemes, the proposed framework achieves 8.1 times lower synchronization error, 9 times lower packet delivery delay, and 2.7 times lower energy consumption for acquiring LBS message.

One critical issue for wireless power transfer is to avoid human health impairments caused by electromagnetic radiation (EMR) exposure. The existing studies mainly focus on scheduling wireless chargers so that (expected) EMR at any point in the area does not exceed a threshold$R_t$. Nevertheless, they overlook the EMR jitter that leads to exceeding of$R_t$even if the expected EMR is no more than$R_t$. This paper studies the fundamental problem ofRObustlySafEcharging for wireless power transfer (ROSE), that is, scheduling the power of chargers so that the charging utility for all rechargeable devices is maximized while the probability that EMR anywhere does not exceed$R_t$is no less than a given confidence. We first build our empirical probabilistic charging model and EMR model. Then, we present EMR approximation and area discretization techniques to formulate ROSE into a Second-Order Cone Program. After that, we propose the first redundant second-order cone constraints reduction algorithm to reduce the computational cost, and therefore obtain a$(1-\epsilon)$-approximation centralized algorithm. Further, we propose a$(1-\epsilon)$-approximation fully distributed algorithm scalable with network size for ROSE. We conduct both simulation and field experiments, and the results show that our algorithms can outperform comparison algorithms by 480.19 percent.

We report a 3-year city-wide study of an operational indoor sensing system based on Bluetooth Low Energy (BLE) calledaBeacon(short foralibabaBeacon).aBeaconis pilot-studied, A/B tested, deployed, and operated in Shanghai, China to infer the indoor status of Alibaba couriers, e.g., arrival and departure at the merchants participating in the Alibaba Local Services platform. In its full operation stage (2018/01-2020/04),aBeaconconsists of customized BLE devices at 12,109 merchants, interacting with 109,378 couriers to infer their status to assist the scheduling of 64 million delivery orders for 7.3 million customers with a total amount of$\$ $600 million order values. Although in an academic setting, using BLE devices to detect arrival and departure looks straightforward, it is non-trivial to design, build, deploy, and operateaBeaconfrom its conception to its retirement at city scale in a metric-based approach by considering the tradeoffs between various practical factors (e.g., cost and performance) during long-term system evolution. We report our study in two phases, i.e., an 8-month pilot study and a 28-month deployment and operation in the wild. We focus on an in-depth reporting on the five lessons learned and provide their implications in other systems with long-term operation and broad geospatial coverage, e.g., Edge Computing.

Modern data centers often host multiple applications with diverse network demands. To provide fair bandwidth allocation to several thousand traversing flows, Approximate Fair Queueing (AFQ) utilizes multiple priority queues in switch to approximate ideal fair queueing. However, due to limited number of queues in programmable switches, AFQ easily experiences high packet loss and low link utilization. In this paper, we propose Elastic Fair Queueing (EFQ), which leverages limited priority queues to flexibly achieve both high network utilization and fair bandwidth allocation. EFQ dynamically assigns the free buffer space in priority queues for each packet to obtain high utilization without sacrificing flow-level fairness. The results of simulation experiments and real implementations show that EFQ reduces the average flow completion time by up to 82% over the state-of-the-art fair bandwidth allocation mechanisms.

Convergecast is a fundamental operation in wireless sensor networks (WSNs). To support long-term deployment of WSNs, sensor nodes normally operate at low-duty-cycles. However, the low-duty-cycle operation significantly reduces the communication chance between nodes. Consequently, the risk of data collisions significantly increases when multiple senders transmit packets to a receiver during its very short active period. This problem further causes not only wasted packet retransmissions, but also a large delivery latency. Under such conditions, collision-free medium access is more appealing than recovering after collision for low-duty-cycle WSNs. In this work, we propose anincast-collision-free convergecast protocol, named iCore, to address the many-to-one collision problem in low-duty-cycle WSNs. iCore employs the dynamic forwarding technique, establishes a non-conflicting schedule for efficient convergecast, and improves the channel utilization by allowing senders to opportunistically transmit packets once detecting unused slots. Specifically, we design efficient forwarder assignment and forwarding optimization algorithms that ensure low end-to-end latency under diverse data traffic types. Through comprehensive performance evaluations, we demonstrate that, compared with the baseline protocol, iCore effectively minimizes the end-to-end delay by 25% ~ 57% and maintains high delivery ratio and energy efficiency for different many-to-one convergecast scenarios.

Modern datacenter applications bring fundamental challenges to transport protocols as they simultaneously require low latency and high throughput. Recent receiver-driven trans-port protocols transmit only one data packet once receiving each grant or credit packet from the receiver to achieve ultra-low queueing delay and zero packet loss. However, the round-trip time variation and the highly dynamic background traffic significantly deteriorate the performance of receiver-driven transport protocols, resulting in under-utilized bandwidth. This paper designs a simple yet effective solution called RPO that retains the advantages of receiver-driven transmission while efficiently utilizing the available bandwidth. Specifically, RPO rationally uses low-priority opportunistic packets to ensure high network utilization without increasing the queueing delay of high-priority normal packets. In addition, since RPO only uses Explicit Congestion Notification (ECN) marking function and priority queues, RPO is ready to deploy on switches. We implement RPO in Linux hosts with DPDK. Our small-scale testbed experiments and large-scale simulations show that RPO significantly improves the network utilization by up to 35% under high workload over the state-of-the-art receiver-driven transmission schemes, without introducing additional queueing delay.

Recent years have witnessed the proliferation of Low-power Wide Area Networks (LPWANs) in the unlicensed band for various Internet-of-Things (IoT) applications. Due to the ultra-low transmission power and long transmission duration, LPWAN devices inevitably suffer from high power Cross Technology Interference (CTI), such as interference from Wi-Fi, coexisting in the same spectrum. To alleviate this issue, this paper introduces the Partial Symbol Recovery (PSR) scheme for improving the CTI resilience of LPWAN. We verify our idea on LoRa, a widely adopted LPWAN technique, as a proof of concept.At the PHY layer, although CTI has much higher power, its duration is relatively shorter compared with LoRa symbols, leaving part of a LoRa symbol uncorrupted. Moreover, due to its high redundancy, LoRa chips within a symbol are highly correlated. This opens the possibility of detecting a LoRa symbol with only part of the chips. By examining the unique frequency patterns in LoRa symbols with time-frequency analysis, our design effectively detects the clean LoRa chips that are free of CTI. This enables PSR to only rely on clean LoRa chips for successfully recovering from communication failures. We evaluate our PSR design with real-world testbeds, including SX1280 LoRa chips and USRP B210, under Wi-Fi interference in various scenarios. Extensive experiments demonstrate that our design offers reliable packet recovery performance, successfully boosting the LoRa packet reception ratio from 45.2% to 82.2% with a performance gain of 1.8×.

Wi-Fi fingerprinting using the received signal strength (RSS) of the access point (AP) as a physical signal feature is widely studied in the indoor localization area with various applications. One main problem with fingerprinting based approach is the uncertainty of RSS measurements, which often leads to instability and decline of localization performance. In this work, we propose GraFin, a graph-based fingerprinting approach, to provide accurate and robust indoor localization without tedious site surveys and extra assistant information. The key idea lies in the insight that despite the RSS measurement of one AP at one reference point (RP) can be noisy, the proximity pattern, which describes one AP's relative position to other APs and RPs, is usually more stable. Specifically, GraFin models APs and RPs on a graph based on limited RSS measurements and provides position-aware fingerprints for APs and RPs based on an inductive deep graph model. We evaluate GraFin on a public indoor localization dataset, and the results demonstrate the effectiveness and robustness of our approach. Furthermore, we apply our approach to the arrival-departure time estimation task for instant delivery service. Experiment results on the enterprise dataset from one of the largest instant delivery platforms in China show that GraFin outperforms baseline approaches with significantly lower time estimation error.

Despite the popularity of Bluetooth low energy (BLE) location-based services (LBS) in Internet of things applications, large-scale BLE LBS are extremely challenging due to the expenses of deploying and maintaining BLE beacons. To alleviate this issue, this work presents WiBeacon, which repurposes ubiquitously deployed WiFi access points (AP) into virtual BLE beacons via only moderate software upgrades. Specifically, a WiBeacon-enabled AP can broadcast elaborately designed WiFi packets that could be recognized as iBeacon-compatible location identifiers by unmodified mobile BLE devices. This offers fast deployment of BLE LBS with zero additional hardware costs and low maintenance burdens. WiBeacon is carefully integrated with native WiFi services, retaining transparency to WiFi clients. We implement WiBeacon on commodity WiFi APs (with various chipsets such as Qualcomm, Broadcom, and MediaTek) and extensively evaluate it across various scenarios, including a real commercial application for courier check-ins. During the two-week pilot study, WiBeacon provides reliable services, i.e., as robust as conventional BLE beacons, for 697 users with 150 types of smartphones.

Instant delivery has developed rapidly in recent years and significantly changed the lifestyle of people due to its timeliness and convenience. In instant delivery, the order dispatch process is concurrent. Couriers take new orders continuously and deliver multiple orders in a delivery trip (i.e., a batch). The delivery time of orders in a batch is often overlapped and interlinked with each other. The pickup and delivery sequence of the existing orders in a batch changes dynamically due to time constraints and real-time overdue possibility (i.e., the rate of deliveries that are not finished in promised time). Most of existing order dispatch mechanisms are designed for independent order dispatch or concurrent delivery without strict time constraints, hence are incapable of handling real-time concurrent dispatch with strict time constraints in on-demand instant delivery. To address the challenge, we propose a Time-Constrained Actor- Critic Reinforcement learning based concurrent dispatch system called TCAC-Dispatch to enhance the long-term overall revenue and reduce the overdue rate. Specifically, we design a deep matching network (DMN) with a variable action space, which integrates the state embedding (including route behaviors encoding) and actions embedding features into a long-term matching value. Then the Actor-Critic model tackles the concurrent order dispatch problem considering strict time constraints and stochastic demand-supply in instant delivery. An estimated time-based action pruning module is designed to ensure time constraints guarantee and accelerate the training as well as dispatching processes. We evaluate the TCAC-Dispatch with one-month data involved with 36.48 million orders and 42,000 couriers collected from one of the largest instant delivery companies in China, i.e., Eleme. Empirical experiments are conducted on a data-driven emulator deployed on the development environment of Eleme and results show that our method achieves 22% of the increase in total revenue and reduces the overdue rate by 21.6%.

The large-scale Bluetooth low energy (BLE) location-based services (LBS) are challenging due to the requirement of additional Bluetooth beacons, which inevitably incur tremendous hardware and maintenance cost. To alleviate this issue, this work presents WiBeacon which repurposes ubiquitously deployed WiFi access points into virtual beacons via cross-technology communication (CTC). WiBeacon only requires moderate software updates in APs, thus enabling fast deployment with zero additional hardware and also low maintenance cost via the remote Internet access.

We report a 30-month nationwide deployment and operation study of an indoor arrival detection system based on Bluetooth Low Energy called VALID in 364 Chinese cities. VALID is pilot-studied, deployed, and operated in the wild to infer real-time indoor arrival status of couriers, and improve their status reporting behavior based on the detection. During its full nationwide operation (2018/12- 2021/01), VALID consists of virtual devices at 3 million shops and restaurants, where 530,859 of them are in multi-story malls and markets to infer and influence 1 million couriers' behavior, and assist the scheduling of 3.9 billion orders for 186 million customers. Although indoor arrival detection is straightforward in controlled environments, the scale of our platform makes the cost prohibitively high. In this work, we explore to use merchants' smartphones under their consent as a virtual infrastructure to design, build, deploy, and operate VALID from in-lab conception to nationwide operation in three phases for 30 months. We consider metrics including system evolution, reliability, utility, participation, energy, privacy, monetary benefits, along with couriers' behavior changes. We share three lessons and their implications for similar wireless sensing or communication systems with large geospatial operations.

Nowadays most metro advertising systems schedule advertising slots on digital advertising screens to achieve the maximum exposure to passengers by exploring passenger demand models. However, our empirical results show that these passenger demand models experience uncertainty at fine temporal granularity (e.g., per min). As a result, for fine-grained advertisements (shorter than one minute), a scheduling based on these demand models cannot achieve the maximum advertisement exposure. To address this issue, we propose an online advertising approach, called FineUDM, based on the uncertain passenger demand modeling for both entering passengers and exiting passengers. FineUDM combines coarse-grained statistical demand modeling and fine-grained real-time demand modeling by leveraging historical passenger demands, real-time card-swiping records, and passenger mobility patterns. Based on this uncertain demand model, it schedules advertising time online based on robust receding horizon control to maximize the advertisement exposure. We evaluate the proposed approach based on an one-month sample from our 530 GB real-world metro fare dataset with 16 million cards. The results show that our approach provides a 61.5 percent lower traffic prediction error and 20 percent improvement on advertising efficiency on average.

Data center networks typically adopt multi-rooted tree topologies to provide high bisection bandwidth. Various fine-grained load balancing schemes have been proposed to split flows across multiple paths. However, data center networks suffer from many uncertainties such as highly dynamic traffic. These uncertainties easily make network become asymmetric, resulting in significant packet reordering. Unfortunately, existing solutions passively deal with packet reordering based on a threshold and hardly adapt to asymmetric networks because of lacking the explicit reordering feedback. These solutions either fail to quickly respond to packet loss or cause unnecessary fast retransmission, which reduces link utilization and increases flow completion time. In this paper, we propose a fine-grained load balancing scheme RMC to eliminate the impact of packet reordering and handle uncertainties in asymmetric networks. To avoid unnecessary fast retransmission, the switch proactively identifies reordered packet according to local queue length and global path latency. Furthermore, we employ a coding technique with redundancy optimization to reduce long-tailed flow completion time under network asymmetry. Through a series of large-scale NS2 simulations and testbed experiments, we demonstrate that RMC effectively avoids unnecessary fast retransmission under different network scenarios and reduces flow completion time by up to 72% compared with state-of-the-art schemes.

Exploring human mobility is essential for urban applications. To observe human mobility, various data-driven techniques based on different data sources, such as cell phone and transportation data, have been proposed. This paper investigates human mobility through the emerging vehicular Internet service on public bus system. The key idea is that if a passenger is using WiFi on the bus or his/her WiFi device is activated in the background, we know that the passenger is traveling on the bus. By fusing the network events generated by WiFi devices with the data from the automatic fare collection (AFC) system, and the bus GPS information, we exploit not only the origin but also the destination of a passenger. Based on this idea, we develop a novel system called ViFi-MobiScanner which consists of about 4, 800 mobile routers distributed in a city with 1, 992 KM2urban area. We develop an ID matching algorithm that matches part of the users' network identities and their smartcard identities anonymously. As a result, we have built a set of labeled samples with the reference of observation from smartcard data and use them to train a classifier to infer users mobility from their network activities. We evaluate ViFi-MobiScanner with both field tests and collected datasets associated with 168 million network events, 3.6 million trips, and 1.4 million users. The evaluation results show that ViFi-MobiScanner increases the observability on the passengers and trips by about 53.9% and 48.1% over the smartcard observations. ViFi-MobiScanner also helps to estimate the passengers' destination that cannot be observed by current smartcard systems and the estimation can be accomplished in minutes. Thus it expands the observability of mobility in object, temporal and spatial dimensions and provides unique insights on human mobility at metropolitan scales.

Recent research on physical layer cross technology communication (PHY-CTC) brings a timely answer for escalated wireless coexistence and open spectrum movement. PHY-CTC achieves direct communication among heterogeneous wireless technologies (e.g.,WiFi, Bluetooth, and ZigBee) in physical layer and thus brings communication support for coexistence service such as spectrum management and IoT device control. To put PHY-CTC into service, however, there still exists a gap due to its transmission failure and asymmetric link (i.e., one-way PHY-CTC) issues. In this paper, we propose NetCTC – the first networking support design for PHY-CTC to establish feedbacks (e.g., ACKs) and thus meet the upper layer networking requirements in heterogeneous unicast, multicast and broadcast. The core design of NetCTC is a real-time interaction mechanism which achieves reliable, transmission efficient and concurrent interactive communication among heterogeneous devices. We implement and evaluate NetCTC on commodity devices and the USRP-N210 platform. Our extensive evaluation demonstrates that NetCTC achieves reliable bidirectional cross technology communication under a full range of wireless configurations including stationary, mobile and duty-cycled settings.

In this article, we first study the problem of Connected wIReless Charger pLacEment (CIRCLE). That is, given a fixed number of directional wireless chargers and candidate positions, determining the placement position and orientation angle for each charger under connectivity constraint for wireless chargers such that the overall charging utility is maximized. To address CIRCLE problem, we first consider a relaxed version of CIRCLE (CIRCLE-R for short). We prove that CIRCLE-R falls into the realm of maximizing a submodular set function subject to a connectivity constraint, and propose an algorithm whose approximation ratio is at least 1.5 times better than that of the state-of-the-art algorithm. Next, we reduce the solution space for CIRCLE from infinite to finite, and propose an algorithm with a constant approximation ratio to address CIRCLE. Besides, we consider a variant of CIRCLE, CIRCLE-NB, and propose an approximation algorithm to address it. We conduct both simulation experiments and field experiments to verify our theoretical findings. The results show that our algorithm can outperform comparison algorithms by 83.35 percent.

Hierarchical Modulation (HM) is quite efficient for multimedia broadcast in wireless networks. It exploits the wireless broadcast advantage and allows a transmission to reach different users with various qualities. However, existing HM related schemes are based on specially designed hardware, leading to extra hardware and deployment cost in practice. As a remedy for this, we design and implement a software-based HM scheme, named as SoftHM. By carefully tuning the Physical Layer input of a packet (a sequence of “0” or “1” bits, known as PHY payload), a transmitter simply broadcasts the packet with a single rate (e.g., 54Mbps, the highest rate in 802.11g WLAN), while diverse receivers can decode and extract different amount of information (with different reception rate, e.g., 12Mbps or 54Mbps) from it based on their link qualities. Reverse engineering techniques are adopted so that SoftHM works in a plug-in mode, offering it high potentials for wireless systems without any changes in existing modulation and coding modules. We implement SoftHM based on Universal Software Radio Peripheral (USRP) B210 and Commercial of the Shelf (COTS) Wi-Fi devices. Both rigorous analysis on its performance and comprehensive implementation-based experiments show that compared with the traditional time-sharing approach, to support low-quality users with the same bandwidth, high-quality users in SoftHM achieve 111.1% to 616.7% higher throughput. Likewise, to serve high-quality users with the same bandwidth, low quality users in softHM achieve 176.9% to 390.9% higher throughput.

Wireless Power Transfer has become a commercially viable technology to charge devices because of the convenience of no power wiring and the reliability of continuous power supply. This paper concerns the fundamental issue of wireless charger placement with electromagnetic radiation (EMR) safety. Although there are a few wireless charging schemes consider EMR safety, none of them addresses the charger placement issue. In this paper, we propose PESA, a wireless charger Placement scheme that guarantees EMR SAfety for every location on the plane. First, we discretize the whole charging area and formulate the problem into the Multidimensional 0/1 Knapsack (MDK) problem. Second, we propose a fast approximation algorithm to the MDK problem. Third, we propose a near optimal scheme to improve speed by double partitioning the area. We prove that the output of our algorithm is better than $(1-\epsilon)$ of the optimal solution to PESA with a smaller EMR threshold $(1-\epsilon /2)R_{t}$ and a larger EMR coverage radius $(1+\epsilon /2)D$ . We conducted both simulations and field experiments to evaluate the performance of our scheme. Our experimental results show that in terms of charging utility, our algorithm outperforms the comparison algorithms.

The state-of-the-art datacenter load balancing designs commonly optimize bisection bandwidth with homogeneous switching granularity. Their performances surprisingly degrade under mixed traffic containing both short and long flows. Specifically, the short flows suffer from long-tailed delay, while the throughputs of long flows also degrade dramatically due to low link utilization and packet reordering. To solve these problems, we design a traffic-aware load balancing (TLB) scheme to adaptively adjust the switching granularity of long flows according to the load strength of short ones. Under the heavy load of short flows, the long flows use large switching granularity to help short ones obtain more opportunities in choosing short queues to complete quickly. On the contrary, the long flows reroute flexibly with small switching granularity to achieve high throughput. Furthermore, under extremely bursty scenario, we utilize the packet slicing scheme for long flows to release bandwidth for short ones. The experimental results of NS2 simulation and testbed implementation show that TLB significantly reduces the average flow completion time of short flows by 16%-67% over the state-of-the-art load balancers and achieves the high throughput for long flows. Moreover, for extreme bursty case, at the acceptable throughput degradation of long flows, TLB with packet slicing reduces the deadline missing ratio of bursty short flows by up to 80%.

Modern data center networks are usually constructed in multi-rooted tree topologies, which require the highly efficient multi-path load balancing to achieve high link utilization. Recent packet-level load balancer obtains high throughput by spraying packets to all paths, but it easily leads to the packet reordering under network asymmetry. The flow-level or flowlet-level load balancer avoids the packet reordering, while reducing the link utilization due to their inflexibility. To solve these problems, we design a Queueing Delay Aware Packet Spraying (QDAPS), that effectively mitigates the packet reordering for packet-level load balancer. QDAPS selects paths for packets according to the queueing delay of output buffer, and lets the packet arriving earlier be forwarded before the later packets to avoid packet reordering. Moreover, we adopt the “power-of- n-choices” paradigm on QDAPS to alleviate the impact of herd behavior under multiple forwarding engines. We compare QDAPS with ECMP, LetFlow and RPS through NS2 simulation and Mininet implementation. The test results show that QDAPS reduces flow completion time (FCT) by ~30%-50% over the state-of-the-art load balancing mechanism.

In data center networks, many network-intensive applications leverage large fan-in and many-to-one communication to achieve high performance. However, the special traffic patterns, such as micro-burst and high concurrency, easily cause TCP Incast problem and seriously degrade the application performance. To address the TCP Incast problem, we first reveal theoretically and empirically that alleviating packet burstiness is much more effective in reducing the Incast probability than controlling the congestion window. Inspired by the findings and insights from our experimental observations, we further propose a general supporting scheme Adaptive Pacing (AP), which dynamically adjusts burstiness according to the flow concurrency without any change on switch. Additionally, a sender-based approach is proposed to estimate the flow concurrency. Another feature of AP is its broad applicability. We integrate AP transparently into different TCP protocols (i.e., DCTCP, L2DCT and D2TCP). Through a series of large-scale NS2 simulations and testbed experiments, we show that AP significantly reduces the Incast probability across different TCP protocols and the network goodput can be increased consistently by on average 7× under severe congestion.

Overcrowded wireless devices in unlicensed bands compete for spectrum access, generating excessive cross-technology interference (CTI), which has become a major source of performance degradation especially for low-power IoT (e.g., ZigBee) networks. This paper presents a new forward error correction (FEC) mechanism to alleviate CTI, named SafetyNet. Designed for ZigBee, SafetyNet is inspired by the observation that ZigBee is overly robust for environment noises, but insufficiently protected from high-power CTI. By effectively embedding correction code bits into the PHY layer SafetyNet significantly enhances CTI robustness without compromising noise resilience. SafetyNet additionally offers a set of unique features including (i) transparency, making it compatible with millions of readily-deployed ZigBee devices and (ii) zero additional cost on energy and spectrum, as it does not increase the frame length. Such features not only differentiate SafetyNet from known FEC techniques (e.g., Hamming and Reed-Solomon), but also uniquely position it to be critically beneficial for today's crowded wireless environment. Our extensive evaluation on physical testbeds shows that SafetyNet significantly improves ZigBee's CTI robustness under a wide range of networking settings, where it corrects 55% of the corrupted packets.

LoRa as a representative of Low-Power Wide Area Networks (LPWAN) technologies has emerged as an attractive communication platform for the Internet of Things. Since its dense deployment, signal collisions at base stations caused by concurrent transmissions degrade network performance. Existing approaches utilize the signal feature, e.g., frequency, to separate packets from collisions. They do not work well in burst traffic networks because the feature is not stable or fine-grained enough and the information for directed signal separation is not sufficient. In this paper, we leverage multidimensional information and propose a novel PHY layer approach called SCLoRa to decode collided LoRa transmissions. SCLoRa utilizes cumulative spectral coefficient, which integrates both frequency and power information, to separate symbols in the overlapped signal. The practical factors of channel fading, similar symbol boundary, and spectrum leakage are taken into account. The SCLoRa design requires neither hardware nor firmware changes in commodity devices – a feature allowing fast deployment on LoRa base stations. We implement and evaluate SCLoRa on USRP B210 base stations and commodity LoRa devices (i.e., SX1278). The experiment results in different scenarios with different radio parameters show that the throughput of SCLoRa is 3× than the state-of-the-art.

Wireless technologies are increasingly diversified to serve various Internet-of-things applications. Yet, our mobile devices (e.g., smartphones) are manufactured with limited types of wireless radio, making it challenging to access the data in the heterogeneous IoT devices. To address this fundamental problem, this work proposes XFi, which enables mobile devices to use commodity WiFi radio to directly and simultaneously collect data from diverse heterogeneous IoT devices. Our critical insight is that when an IoT frame collides with an ongoing WiFi transmission, its IoT data is captured by WiFi receiver and retained even after the demodulation procedures in WiFi hardware. Motivated by this observation, XFi proposes a general approach to obtain IoT data by analyzing the decoded WiFi payload. The method is fully compatible with existing commodity WiFi hardware and generally applicable to various IoT protocols. We implement XFi on commodity devices (e.g., RTL8812au, CC2650, and SX1280). Our comprehensive evaluation demonstrates that XFi can collect data from 8 IoT devices in parallel with over 97% accuracy, offering reliable cross-technology data collection.

Cloud applications generate a variety of workloads ranging from delay-sensitive flows to bandwidth-hungry ones in data centers. Existing reactive or proactive congestion control protocols are hard to simultaneously achieve ultra-low latency and high link utilization across all workloads in data center networks. We present a new receiver-driven transport scheme using anti-ECN (Explicit Congestion Notification) marking to achieve both near-zero queueing delay and full link utilization by reasonably increasing sending rate in the case of under-utilization. Specifically, switches mark the ECN bit of data packets once detecting spare bandwidth. When receiving the anti-ECN marked packet, the receiver generates the corresponding marked grant to trigger more data packets. The experimental results of small-scale testbed implementation and large-scale NS2 simulation show that AMRT effectively reduces the average flow completion time (AFCT) by up to 40.8% and improves the link utilization by up to 36.8% under high workload over the state-of-the-art receiver-driven transmission schemes.

Industrial Scientific Medical (ISM) band has become more and more crowded due to the ever-growing size of many mainstream technologies, e.g., Wi-Fi, ZigBee and Bluetooth. Though they compete for limited spectrum resources leading to severe Cross Technology Interference (CTI), it also provides great opportunities to better utilize the scarce bandwidth resources. A fundamental question is how to ensure harmonious and effective operations for these networks? To exploit this issue, a novel global cooperation framework is proposed. In particular, our work enables direct and simultaneous Cross Technology Communication (CTC) from a single Wi-Fi to ZigBee, Bluetooth and Wi-Fi commodity devices sharing the same band. Compared to existing CTC approaches, our scheme improves the communication efficiency significantly, and hence is the foundation for effective global cooperation. Based on the proposed CTC scheme, a unified Media Access Control (MAC) approach is introduced to cooperate CTC message transmission and reception for heterogeneous devices with different MACs. Two proof-of-concepts applications, e.g. global synchronization and global CTI coordination are discussed to fully leverage the benefits of global cooperation. Extensive evaluations show that compared with existing schemes, the proposed framework achieves 13 times lower synchronization error and 9 times lower average packet delay in CTI intensive environments.

Low Power Wide Area Networks (LPWAN) are an emerging well-adopted platform to connect the Internet-of-Things. With the growing demands for LPWAN in IoT, the number of supported end-devices cannot meet the IoT deployment requirements. The core problem is the transmission collisions when large-scale end-devices transmit concurrently. The previous research mainly includes transmission scheduling strategies, collision detection and avoidance mechanism. The use of these existing approaches to address the above limitations in LPWAN may introduce excessive communication overhead, end-devices cost, power consumption, or hardware complexity. In this paper, we present S-MAC, an adaptive MAC-layer scheduler for LPWAN. The key innovation of S-MAC is to take advantage of the periodic transmission characteristics of LPWAN applications and also the collision behaviour features of LoRa PHY-layer to enhance the scalability. Technically, S-MAC is capable of adaptively perceiving clock drift of end-devices, adaptively identifying the join and exit of end-devices, and adaptively performing the scheduling strategy dynamically. Meanwhile, it is compatible with native LoRaWAN, and adaptable to existing Class A, B and C devices. Extensive implementations and evaluations on commodity devices show that S-MAC increases the number of connected end-devices by 4.06× and improves network throughput by 4.01× with PRR requirement of > 95%.

Instant delivery is an important urban service in recent years because of the increasing demand. An important issue for delivery platforms is to keep updating the status of couriers especially the real-time locations, which is challenging when they are in an indoor environment. We argue the previous indoor localization techniques cannot be applied in the instant delivery scenario because they require extra deployed infrastructures and extensive labor work. In this work, we perform the couriers' indoor localization transparently in a predictive manner without extra actions of couriers by existing data from the platform including order progress reports and couriers' trajectories. Specifically, we present TransLoc to predict couriers' indoor locations by addressing two challenges including uncertain reporting behaviors and uncertain indoor mobility behaviors. Our key idea lies in two insights (i) couriers' behaviors are consistent in indoor/outdoor environments; (ii) localization, as a spatial inference problem, could be converted to a temporal inference problem. We evaluate TransLoc on 565 couriers from an instant delivery company, which improves baselines by at most 72%, and achieves a competitive result compared to a label-extensive approach. As a case study, we apply TransLoc to optimize the order dispatching strategy, which reduces the delivery time by 24%.

In data center networks, a large number of concurrent TCP connections suffer the TCP Incast throughput collapse due to packet drops in shallow-buffered Ethernet switches. In this work, we first reveal theoretically and empirically that controlling the IP packet size is much more effective in avoiding Incast than cutting congestion window under severe congestion. We further design a general supporting scheme Packet Slicing, which adjusts the IP packet on widely used commodity switches. The design uses standard ICMP signaling, which makes no modification on TCP protocols and can be transparently utilized by various TCP protocols. To alleviate the impact of micro-burst caused by high flow concurrency, we utilize the TCP Pacing scheme to disperse packets over the round trip time, helping Packet Slicing to support more concurrent TCP flows. We integrate Packet Slicing with three state-of-the-art data center TCP protocols on NS2 simulation and a physical testbed. The experimental results show that Packet Slicing broadly improves the goodput of different data center TCP protocols by average 26x, while having almost no effect on the I/O performance of switches and end hosts.

introduction Share on Introduction to the Special Issue on Transportation Cyber-Physical Systems Authors: Samarjit Chakraborty University of North Carolina at St., Chapel Hill, NC University of North Carolina at St., Chapel Hill, NCView Profile , Tian He University of North Carolina at Chapel Hill, Minneapolis, MN University of North Carolina at Chapel Hill, Minneapolis, MNView Profile Authors Info & Claims ACM Transactions on Cyber-Physical SystemsVolume 4Issue 1January 2020 Article No.: 1pp 1–3https://doi.org/10.1145/3372495Online:21 January 2020Publication History 0citation159DownloadsMetricsTotal Citations0Total Downloads159Last 12 Months35Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Hybrid electric storage system (HESS) is a promising power supply for electric vehicles (EVs) to prolong battery cycling life. Battery longevity is affected by the magnitude and fluctuation of the charging/discharging power profiles. While vehicle driving, unexpected high power demand can cause battery degradation and should be supplied by the supercapacitor (SC) in the HESS. However, the limited capacity of SCs restricts the HESS benefit. Thus, one of the crucial while challenging issues for an HESS is how to effectively manage the power splitting between batteries and SCs to satisfy the vehicle's driving demand as well as reducing battery degradation rate. In this paper, a proactive power management scheme is proposed to extend the EVs battery life with the HESS. First, we exploit a time-series forecasting method to predict the short-term vehicle velocity and calculate the future power demand based on prediction results. Next, due to the nonlinear dynamics of the HESS, the T-S fuzzy modeling method is adopted to approximate system nonlinearity and develop an empirical model. Finally, a model predictive control (MPC) based power management problem is formulated. Prediction errors are considered in MPC formulation to improve system robustness. Based on driving profile tests, simulation results demonstrate that the magnitude and fluctuation of battery current are both reduced and the battery life is prolonged by 17.81% compared with the existing methods.

Physical-Layer Cross-Technology Communication (PHY-CTC), which achieves direct communication among heterogeneous technologies, brings great opportunities to help diverse IoT devices achieve harmonious coexistence through explicit coordination. The core technique of PHY-CTC is signal emulation which utilizes the signal of one technology (e.g., WiFi) to emulate the signal of another technology (e.g., ZigBee). The signal emulation based approach, however, inevitably introduces emulation errors which further lead to unreliable communication. In this paper, we aim to recover the intrinsic emulation errors and establish reliable PHY-CTC. We propose TwinBee which (i) explores chip-level error patterns and (ii) corrects emulation errors with symbol-level chip-combining coding/decoding and soft mapping. To achieve this, TwinBee dose not require accessing chip information as well as making hardware changes. We implement TwinBee on commodity devices (i.e., Laptops with Atheros AR2425 WiFi card and TelosB motes) and the USRPN210 platform (for physical layer evaluation). Experiment results show that TwinBee significantly improves the Packet Reception Ratio (PRR) of PHY-CTC from 50%-60% to more than 99%. Furthermore, we demonstrate the reliability of TwinBee in a data dissemination application over a network of 20 TelosB nodes, achieving over 42× reduction of data dissemination delay compared to the state-of-the-art.

Despite many existing research on data forwarding in low-duty-cycle wireless sensor networks (WSNs), relatively little work has been done on energy-efficient data forwarding with probabilistic delay bounds. Probabilistic delay guarantees (i.e., delay bounded data delivery with reliability constraints) are of increasing importance for many delay-constrained applications, since deterministic delay bounds are prohibitively expensive to guarantee in WSNs. However, radio duty-cycling and unreliable wireless links pose challenges for achieving the probabilistic delay guarantee in WSNs. In this paper, we propose EEAF, a novel energy-efficient adaptive forwarding technique tailored for low-duty-cycle WSNs with unreliable wireless links. We show the existence of path diversity in low-duty-cycle WSNs, where delay-optimal routing and energy-optimal routing are likely following different paths. The key idea of EEAF is to exploit the intrinsic path diversity to provide probabilistic delay guarantees while minimizing transmission cost. In EEAF, an early arriving packet will be adaptively switched to the energy-optimal path for energy conservation. Delay quantiles are derived at each node in a distributed manner and are used as the guidelines in the adaptive forwarding decision making. Extensive testbed experiment and large-scale simulation show that EEAF effectively reduces the transmission cost by 12%~25% with probabilistic delay guarantees under various network settings. In addition, we extend the EEAF technique with data aggregation for event-based traffic scenarios. Evaluation using publicly available WSN event traffic traces yields very encouraging results with up to 40% energy saving in probabilistic delay bounded data delivery.

In the data center network, a packet-level load balancer such as random packet spraying (RPS) achieves high throughput by spraying data packets to all transmission paths, which easily suffers from the packet out-of-order problem under network asymmetry. While state-of-the-art network coding schemes can mitigate the issue, too many encoded redundant packets introduced by the network coding will cause extra traffic overhead, larger queueing delay and even TCP time out. In this paper, we propose OPportunistic Encoded Redundant (OPER), a middle-layer design upon existing coding schemes to mitigate the curse of redundant packets. Specifically, OPER uses opportunistic redundant packets which are replaceable by the data packets in the switches under heavy congestion. OPER is implemented as a shim layer between TCP and IP layers at end-hosts and a loadable plugin at switches, leaving existing TCP/IP protocols unmodified. The testbed and NS2 experiments show that, OPER reduces the average flow completion time by up to 71% compared with the state-of-the-art multipath coding schemes.

Electric taxis (e-taxis) have been increasingly deployed in metropolitan cities due to low operating cost and reduced emissions. Compared to conventional taxis, e-taxis require frequent recharging and each charge takes half an hour to several hours, which may result in unpredictable number of working taxis on the street. In current systems, E-taxi drivers usually charge their vehicles when the battery level is below a certain threshold, and then make a full charge. Although this charging strategy directly decreases the number of charges and the time to visit charging stations, our study reveals that it also significantly reduces the availability of number of taxis during busy hours with our data driven analysis. To meet dynamic passenger demand, we propose a new charging strategy: proactive partial charging (p2Charging), which allows an e-taxi to get partially charged before its remaining battery level is running too low. Based on this strategy, we propose a charging scheduling framework for e-taxis to meet dynamic passenger demand in spatial-temporal dimensions as much as possible while minimizing idle time to travel to charging stations and waiting time at charging stations. This work implements and evaluate our solution with large datasets that consist of (i) 7,228 regular internal combustion engine taxis and 726 e-taxis, (ii) an automatic taxi payment transaction collection system with total 62,100 records per day, (iii) charging station system, including 37 working charging stations over the city. The evaluation results show that p2Charging improves the ratio of unserved passengers by up to 83.2% on average and increases e-taxi utilization by up to 34.6% compared with ground truth and existing charging strategies.

Modern data center networks provide multiple paths between host pairs to guarantee high aggregated network bandwidth and transmission reliability. However, data center networks suffer from various uncertainties such as highly dynamic traffic and heterogeneous devices. These uncertainties easily lead to network asymmetry and cause significant packet reordering. Unfortunately, due to lacking the explicit reordering feedback, existing sender-based and receiver-based solutions hardly adapt to asymmetric data center networks and cause long-tailed flow completion time as well as throughput loss. In this paper, we propose a per-packet transmission scheme RMC to eliminate the impact of packet reordering and handle uncertainties in asymmetric networks. To avoid unnecessary fast retransmission, the switch proactively identifies packet reordering according to local queue length and global path latency. Furthermore, we employ a coding technique to reduce long-tailed flow completion time under network asymmetry. Through a series of large-scale NS2 simulations and testbed experiments, we demonstrate that RMC reduces flow completion time by up to 72% compared with existing protocols.

Modern datacenter topologies typically are multi-rooted trees consisting of multiple paths between any given pair of hosts. Recent load balancing designs focus on making full use of available parallel paths to provide high bisection bandwidth. However, they are agnostic to the mixed traffic generated by diverse applications in data centers and respectively use the same granularity in rerouting flows regardless of the flow type. Therefore, the short flows suffer the long-tailed queueing delay and reordering problems, while the throughputs of long flows are also degraded dramatically due to low link utilization and packet reordering under the non-adaptive granularity. To solve these problems, we design a traffic-aware load balancing (TLB) scheme to adopt different rerouting granularities for two kinds of flows. Specifically, TLB adaptively adjusts the switching granularity of long flows according to the load strength of short ones. Under the heavy load of short flows, the long flows use large switching granularity to help short ones obtain more opportunities in choosing short queues to complete quickly. When the load strength of short flows is low, the long flows switch paths more flexibly with small switching granularity to achieve high throughput. TLB is deployed at the switch, without any modifications on the end-hosts. The experimental results of NS2 simulations and Mininet implementation show that TLB significantly reduces the average flow completion time (AFCT) of short flows by ~15%-40% over the state-of-the-art load balancing schemes and achieves the high throughput for long flows.

Conventional gateway solutions are limited in satisfying the demand for ubiquitous connections among heterogeneous wireless devices, e.g., wide-area and personal-area network devices, due to the deployment complexity, high cost, and the incurred extra traffic. Recent advances propose the physical layer cross-technology communication to address these issues. However, existing CTC techniques commonly emulate the target waveform in the frequency domain (FDE). Despite their success, these FDE based techniques inherently suffer from high quantization errors and are insufficient for IoT applications that require high communication reliability.

With the rapid development of sharing economy, massive sharing systems such as Uber, Airbnb, and bikeshare have percolated into people's daily life. The sharing economy, at its core, is to achieve efficient use of resources. The actual usage of shared resources, however, is unclear to us. Little measurement or analysis, if any, has been conducted to investigate the resource usage status with the large-scale data collected from these sharing systems. In this paper, we analyze the bike usage status in three typical bikeshare systems based on 140-month multi-event data. Our analysis shows that the most used 20% of bikes account for 45% of usage, while the least used 20% of bikes account for less than 1% of usage. To efficiently utilize shared bikes, we propose a usage balancing design called eShare which has three components: (i) a statistical model based on archived data to infer historical usage; (ii) an entropy-based prediction model based on both real-time and archived data to infer future usage; (iii) a model-driven optimal calibration engine for bike selection to dynamically balance usage. We develop an ID swapping based evaluation methodology and measure the efficiency of eShare with data from three systems including the world's largest bikeshare system with 84,000 bikes and 3,300 stations. Our results show that eShare not only fully utilizes shared bikes but also improves service quality.

Real-time traffic modeling at national scale is essential to many applications, but its calibration is extremely challenging due to its large spatial and fine temporal coverage. The existing work is focused on urban-scale calibration with complete field data from single data sources (e.g., loop sensors or taxis), which cannot be generalized to national scale because complete single-source field data at national scale are almost impossible to obtain. To address this challenge, in this article, we design MultiCalib, a model calibration framework to optimize traffic models based on multiple incomplete data sources at national scale in real time. Instead of simply combining multi-source data, we theoretically formulate a multi-source model calibration problem based on real-world contexts and multi-view learning. In particular, we design (i) convex multi-view learning to integrate multi-source data by quantifying biases of data sources, and (ii) context-aware tensor decomposition to infer incomplete multi-source data by extracting real-world contexts. More importantly, we implement and evaluate MultiCalib with two heterogeneous nationwide vehicle networks with 340,000 vehicles to infer traffic conditions on 36 expressways and 119 highways, along with four cities across China. The results show that MultiCalib outperforms baseline calibration by 25% on average with the same input data. Based on the proposed national-scale traffic model calibration, we design a novel dispatching framework integrated with our speed calibration model where we guide a vehicular fleet among national-scale highways with a routing strategy to reduce general traveling time. The results show that a routing strategy based on MultiCalib outperforms a routing strategy based on a state-of-the-art traffic model by 45% on average.

Modern data-center applications generate a diverse mix of short and long flows with different performance requirements and weaknesses. The short flows are typically delay-sensitive but to suffer the head-of-line blocking and out-of-order problems. Recent solutions prioritize the short flows to meet their latency requirements, while damaging the throughput-sensitive long flows. To solve these problems, we design a Coding-based Adaptive Packet Spraying (CAPS) that effectively mitigates the negative impact of short and long flows on each other. To exploit the availability of multiple paths and avoid the head-of-line blocking, CAPS spreads the packets of short flows to all paths, while the long flows are limited to a few paths with Equal Cost Multi Path (ECMP). Meanwhile, to resolve the out-of-order problem with low overhead, CAPS encodes the short flows using forward error correction (FEC) technology and adjusts the coding redundancy according to the blocking probability. Moreover, since the coding efficiency decreases when the coding unit is too small or large, we demonstrate how to obtain the optimal size of coding unit. The coding layer is deployed between the TCP and IP layers, without any modifications on the existing TCP/IP protocols. The test results of NS2 simulation and small-scale testbed experiments show that CAPS significantly reduces the average flow completion time of short flows by ~30%-70% over the state-of-the-art multipath transmission schemes and achieves the high throughput for long flows with negligible traffic overhead.

The cross-technology communication (CTC) is a promising technique proposed recently to bridge heterogeneous wireless technologies in the ISM bands. Existing solutions use only the coarse-grained packet-level information for CTC modulation, suffering from a low throughput (e.g., 10 b/s). Our approach, called BlueBee, explores the dense PHY-layer information for CTC by emulating legitimate ZigBee frames with the Bluetooth radio. Uniquely, BlueBee achieves dual-standard compliance and transparency for its only modifying the payload of Bluetooth frames, requiring neither hardware nor firmware changes at either the Bluetooth sender or the ZigBee receiver. Our implementation on both USRP and commodity devices shows that BlueBee can achieve standard ZigBee bit rate of 250 kb/s at more than 99% accuracy, which is over 10000 x faster than the state-of-the-art packet-level CTC technologies.

ZigBee is a widely used wireless technology in low-power and short-range scenarios such as the Internet of Things, sensor networks, and industrial wireless networks. However, the traditional ZigBee supports only one data rate, 250 Kbps, which thoroughly limits ZigBee's efficiency in dynamic wireless channels. In this paper, we propose Mrs. Z, a novel physical layer design to enable multi-rate selection in ZigBee with lightweight modification on the legacy ZigBee modules. The key idea is to change the single spectrum spreading length to multiple ones. Correspondingly, to support the rate adaptation to the channel variations, we propose a bit-error-based rate selection scheme, which predicts BER by leveraging the physical properties of ZigBee to calculate the confidence for each symbol in transmission. Then, the receiver selects the rate based on the negative impact on throughput incurred by bit errors and gives feedback to the transceiver. We implement Mrs. Z on USRPs and evaluate its performance in different scenarios. Experiment results demonstrate that Mrs. Z achieves about 1.15, 1.2, and 1.8 × average throughput compared to the classic smart pilot, softrate, and the traditional ZigBee.

In modern data centers, many flow-based and task-based schemes have been proposed to speed up the data transmission in order to provide fast, reliable services for millions of users. However, the existing flow-based schemes treat all flows in isolation, contributing less to or even hurting user experience due to the stalled flows. Other prevalent task-based approaches, such as centralized and decentralized scheduling, are sophisticated or unable to share task information. In this work, we first reveal that the relinquishing bandwidth of leading flows to the stalled ones effectively reduces the task completion time. We further present the design and implementation of a general supporting scheme that shares the flow-tardiness information through a receiver-driven coordination. Our scheme can be flexible and widely integrated with the state-of-the-art TCP protocols designed for data centers in either single stage or multiple stage scenario, while making no modification on switches. Through the testbed experiments and simulations of typical data center applications, we show that in single stage scenario, our scheme reduces the task completion time by 70% and 50% compared with the flow-based protocols (e.g., DCTCP, L2DCT) and task-based scheduling (e.g., Baraat), respectively. Moreover, our scheme also outperforms other approaches by 18%~25% in prevalent topologies of the data center. For multiple stage scenario, our scheme also has up to 50% improvement compared to other schemes.

Large-scale battery packs are commonly used in applications such as electric vehicles (EVs) and smart grids. Traditionally, to provide stable voltage to the loads, voltage regulators are used to convert battery packs’ output voltage to those of the loads’ required levels, causing power loss especially when the difference between the supplied and required voltages is large or when the load is light. In this article, we address this issue via a reconfiguration framework for the battery system. By abstracting the battery system as a cell graph, we develop an adaptive reconfiguration algorithm to identify the desired system configurations based on real-time load requirements. Our design is evaluated via both prototype-based experiments, EV driving trace-based emulations, and large-scale simulations. The results demonstrate an extended system operation time of up to 5×, especially when facing severe cell imbalance.

To mitigate the issue of cross-technology interference (CTI) under dense wireless, cross-technology communication (CTC) was recently proposed, which enables direct communication among heterogeneous wireless technologies. We present SymBee, a novel ZigBee to WiFi CTC with symbol-level encoding for performance breakthrough from packet-level state-of-the-arts. SymBee is uniquely built on the new insight on ZigBee-WiFi physical layer cross-observability - i.e., the output on WiFi when fed with ZigBee signal (due to frequency overlap). This is analyzed experimentally and theoretically through rigorous derivations, from which the key innovation in SymBee design, i.e., payload encoding, stems; Conveying data across technologies is as simple as putting specific symbols in ZigBee packet payload, such that they yield unique and easily detectable patterns when cross-observed at WiFi. This symbol-level encoding is fully compatible with any commodity ZigBee device. Decoding at WiFi is a light-weight function that recycles the output from idle listening, thereby minimizing the computation while keeping compatibility to WiFi standard. SymBee is extensively evaluated both theoretically and experimentally through testbed evaluations on six distinct locations including outdoor. The result demonstrate that SymBee reaches the throughput of up to 31.25kbps, 145.4× faster than the state-of-the-art.

Modern data center networks are usually constructed in multi-rooted tree topologies, which require the highly efficient multi-path load balancing to achieve high link utilization. Recent packet-level load balancer obtains high throughput by spraying packets to all paths, but it easily leads to the packet reordering under network asymmetry. The flow-level or flowlet-level load balancer avoids the packet reordering, while reducing the link utilization due to their inflexibility. To solve these problems, we design a Queueing Delay Aware Packet Spraying (QDAPS), that effectively mitigates the packet reordering for packet-level load balancer. QDAPS selects paths for packets according to the queueing delay of output buffer, and lets the packet arriving earlier be forwarded before the later packets to avoid packet reordering. We compare QDAPS with ECMP, LetFlow and RPS through NS2 simulation and Mininet implementation. The test results show that QDAPS reduces flow completion time (FCT) by ~30%-50% over the state-of-the-art load balancing mechanism.

Recent research on physical layer cross technology communication (PHY-CTC) brings a timely answer for escalated wireless coexistence and open spectrum movement. PHY-CTC achieves direct communication among heterogeneous wireless technologies (e.g.,WiFi, Bluetooth, and ZigBee) in physical layer and thus brings communication support for coexistence service such as spectrum management and IoT device control. To put PHY-CTC into service, however, there still exists a gap due to its transmission failure and asymmetric link (i.e., one-way PHYCTC) issues. In this paper, we propose NetCTC - the first networking support design for PHY-CTC to establish feedbacks (e.g., ACKs) and thus meet the upper layer networking requirements in heterogeneous unicast, multicast and broadcast. The core design of NetCTC is a real-time interaction mechanism which achieves reliable, transmission efficient and parallel interactive communication among heterogeneous devices. We implement and evaluate NetCTC on commodity devices (Laptops with Atheros AR2425 WiFi NIC, smart phones with Broadcom BCM4330 WiFi chip and MicaZ CC2420) and the USRP-N210 platform. Our extensive evaluation demonstrates that NetCTC achieves reliable bidirectional cross technology communication under a full range of wireless configurations including stationary, mobile and dutycycled settings.

Cross-Technology Communication (CTC) is an enabling technology for efficient coexistence and effective cooperation among heterogeneous wireless devices by exchanging data frames directly without gateways. Recent advances in the physical-layer CTC achieve thousands of times faster speed than that of previous packet-level CTC techniques. However, physical-layer CTC still faces the challenge of inherent unreliability due to the imperfection of physical-layer signal emulation. Our work, named TwinBee, aims to recover the intrinsic errors of physical-layer CTC, by exploring chip-level error patterns. This is achieved interestingly without even observing the chip information and without any hardware modification. System evaluation shows that our key idea, namely symbol-level chip-combining decoding with soft mapping, significantly improves the Packet Reception Ratio (PRR) of the physical-layer CTC from 50%-60% to more than 99%. We also demonstrate the reliability of TwinBee in a data dissemination application over a network of 20 TelosB nodes, achieving over 40x reduction of data dissemination delay compared to Deluge.

One critical issue for wireless power transfer is to avoid human health impairments caused by electromagnetic radiation (EMR) exposure. The existing studies mainly focus on scheduling wireless chargers so that (expected) EMR at any point in the area doesn't exceed a threshold Rt. Nevertheless, they overlook the EMR jitter that leads to exceeding of Rteven if the expected EMR is no more than Rt. This paper studies the fundamental problem of RObustly SafE charging for wireless power transfer (ROSE), that is, scheduling the power of chargers so that the charging utility for all rechargeable devices is maximized while the probability that EMR anywhere doesn't exceed Rt is no less than a given confidence. We first build our empirical probabilistic charging model and EMR model. Then, we present EMR approximation and area discretization techniques to formulate ROSE into a Second-Order Cone Program, and the first redundant second-order cone constraints reduction algorithm to reduce the computational cost, and therefore obtain a (1-ε)-approximation centralized algorithm. Further, we propose a (1-ε)-approximation fully distributed algorithm scalable with network size for ROSE. Simulations and field experiments show that our algorithms can outperform comparison algorithms by 480.19%.

Modern data-center applications generate a diverse mix of short and long flows with different performance requirements and weaknesses. The short flows are typically delay-sensitive but to suffer the head-of-line blocking and out-of-order problems. Recent solutions prioritize the short flows to meet their latency requirements, while damaging the throughput-sensitive long flows. To solve these problems, we design a Coding-based Adaptive Packet Spraying (CAPS) that effectively mitigates the negative impact of short and long flows on each other. To exploit the availability of multiple paths and avoid the head-of-line blocking, CAPS spreads the packets of short flows to all paths, while the long flows are limited to a few paths with Equal Cost Multi Path (ECMP). Meanwhile, to resolve the out-of-order problem with low overhead, CAPS encodes the short flows using forward error correction (FEC) technology and adjusts the coding redundancy according to the blocking probability. The coding layer is deployed between the TCP and IP layers, without any modifications on the existing TCP/IP protocols. The experimental results of NS2 simulation and Mininet implementation show that CAPS significantly reduces the average flow completion time of short flows by ~30% -70% over the state-of-the-art multipath transmission schemes and achieves the high throughput for long flows with negligible traffic overhead.

Cross-Technology Communication (CTC) supports direct message exchange among heterogeneous wireless technologies (e.g., Wi-Fi, ZigBee, and BlueTooth) under the same ISM band, enabling explicit cross-technology control and coordination. For instance, a Wi-Fi AP can directly control ZigBee-enabled smart light bulbs without an expensive dual-radio gateway. Such CTC capability can be further amplified if we can extend the communication range of CTC to support long-range wide-area IoT applications such as environmental monitoring, smart metering, and precision agriculture. Our work, named LongBee, is the first to extend the range of Cross-Technology Communication. At the transmitter side, LongBee concentrates the effective TX power through down-clocked operations, and at the receiver side, LongBee improves the RX sensitivity with an innovative transition coding to ensure reliable preamble detection and payload reception. All these are achieved without modifying hardware and without introducing extra Wi-Fi RF energy cost. We implemented the LongBee on the USRP platform and commodity ZigBee devices. Our comprehensive evaluation reveals that LongBee with concentrated TX power and higher RX sensitivity achieves reliably over 10x range extension over native ZigBee communication and 2x range extension than the longest distance achieved by existing CTC schemes so far.

Cross-technology Communication (CTC) is a key technique to explore the full capacity of heterogeneous wireless. The latest CTC designs explore the PHY-layer to reach the standards' maximum rate, but leaving a critical gap to practicality -- existing PHY-layer CTCs are commonly transmitter-side techniques requiring a high-end transmitter (with a high degree of freedom in signal manipulation) to emulate the receiver signal closely. This inherently limits the reverse direction (low-end to high-end) communication. We present XBee, a unique receiver-side CTC that fills in the gap and makes a critical step towards achieving CTC bidirectionality. XBee is demonstrated as a ZigBee to BLE communication, where the key innovation lies in the unique mechanism of cross-technology decoding, or cross-decoding in short, which interprets a ZigBee frame only by carefully observing the bit patterns obtained at the BLE receiver. Technically, XBee counterintuitively explores the sampling offset to overcome the intrinsic challenge due to BLE's narrower bandwidth (1MHz) than ZigBee (2MHz). Extensive implementation and evaluation on USRP and commodity devices reach 250 kbps under 85% reliability, a 15,000x improvement over state-of-the-art ZigBee to BLE communication, and comparable with the latest PHY-layer CTCs to achieve CTC bidirectionality.

Under significant coexistence in the ISM band, the impact of cross-technology interference (CTI) has become a major threat to low-power IoT. This paper presents ECC that uniquely enables explicit channel coordination among heterogeneities via cross-technology communication (CTC) introduced in the latest studies, while maintaining full compatibility to commodity devices. Unlike any implicit coordination designs adopting statistical models to probabilistically predict white spaces, ECC generates the white space using WiFi CTS, which is then explicitly notified to ZigBee through CTC for immediate use. Technical highlight of ECC lies in ensuring ZigBee communication under CTI, without disrupting WiFi operation. This is effectively achieved by the dynamic adjustment of CTS duration with respect to traffic amount and spectrum availability, which essentially enables ECC to be generally applied to various scenarios without prior knowledge. Lastly, ECC significantly reduces delay and energy in low duty cycled ZigBee, by waking them up upon channel availability (via CTC). We evaluate ECC on commercial platforms: Atheros AR2425 WiFi card and TelosB motes. Experiment results show that ECC achieves 1.8x ZigBee packet reception ratio, and cuts down delay and energy by 98.6% and 51% under the low duty cycle.

Recent physical-layer designs capable of decoding multi-packet collisions demonstrate great potential for improving the network performance. Current network protocols, however, tailor the traditional physical layer to avoid collisions and thus cannot fully exploit the benefits of concurrent transmission techniques. In this paper, we propose an innovative generic concurrent transmission aware routing design called mShare. The mShare design exploits the benefits of these techniques by scheduling concurrent senders to utilize co-owned receiver(s) in parallel. This design significantly increases the available number of routing choices and thus improves the network performance. To illustrate the versatility of our design, we test mShare in three settings: unicast, opportunistic routing, and data collection (convergecast). The performance of mShare is evaluated with physical testbed experiments running on USRP and simulations. The experimental results show that compared to conventional designs, mShare: 1) improves 277% of the throughput in unicast; 2) saves 78% of transmissions in opportunistic routing; and 3) reduces 70% of the delivery delay in data collection.

Real-time human mobility modeling is essential to various urban applications. To model such human mobility, numerous data-driven techniques have been proposed. However, existing techniques are mostly driven by data from a single view, for example, a transportation view or a cellphone view, which leads to over-fitting of these single-view models. To address this issue, we propose a human mobility modeling technique based on a generic multi-view learning framework called coMobile. In coMobile, we first improve the performance of single-view models based on tensor decomposition with correlated contexts, and then we integrate these improved single-view models together for multi-view learning to iteratively obtain mutually reinforced knowledge for real-time human mobility at urban scale. We implement coMobile based on an extremely large dataset in the Chinese city Shenzhen, including data about taxi, bus, and subway passengers along with cellphone users, capturing more than 27 thousand vehicles and 10 million urban residents. The evaluation results show that our approach outperforms a single-view model by 51% on average. More importantly, we design a novel application where urban taxis are dispatched based on unaccounted mobility demand inferred by coMobile.

Wireless power transfer technology is considered as one of the promising solutions to address the energy limitation problems for end-devices, but its incurred potential risk of electromagnetic radiation (EMR) exposure is largely overlooked by most existing works. In this paper, we consider the Safe Charging with Adjustable PowEr (SCAPE) problem, namely, how to adjust the power of chargers to maximize the charging utility of devices, while assuring that EMR intensity at any location in the field does not exceed a given threshold Rt. We present novel techniques to reformulate SCAPE into a traditional linear programming problem, and then remove its redundant constraints as much as possible to reduce computational effort. Next, we propose a series of distributed algorithms, including a fully distributed algorithm that provably achieves (1- ϵ) approximation ratio and requires only communications with neighbors within a constant distance for each charger. Through extensive simulation and testbed experiments, we demonstrate that our proposed algorithms can outperform the set-cover algorithm by up to 17.05%, and has an average performance gain of 41.1% over the existing algorithm in terms of the overall charging utility.

In wireless communication, heterogeneous technologies such as WiFi, ZigBee and BlueTooth operate in the same ISM band.With the exponential growth in the number of wireless devices, the ISM band becomes more and more crowded. These heterogeneous devices have to compete with each other to access spectrum resources, generating cross-technology interference (CTI). Since CTI may destroy wireless communication, this field is facing an urgent and challenging need to investigate spectrum efficiency under CTI. In this paper, we introduce a novel framework to address this problem from two aspects. On the one hand, from the perspective of each communication technology itself, we propose novel channel/link models to capture the channel/link status under CTI. On the other hand, we investigate spectrum efficiency from the perspective by taking all heterogeneous technologies as a whole and building crosstechnology communication among them. The capability of direct communication among heterogeneous devices brings great opportunities to harmoniously sharing the spectrum with collaboration rather than competition.

In modern data centers, many flow-based and task-based schemes have been proposed to speed up the data transmission in order to provide fast, reliable services for millions of users. However, existing flow-based schemes treat all flows in isolation, contributing less to or even hurting user experience due to the stalled flows. Other prevalent task-based approaches, such as centralized and decentralized scheduling, are sophisticated or unable to share task information. In this work, we first reveal that relinquishing bandwidth of leading flows to the stalled ones effectively reduces the task completion time. We further present the design and implementation of a general supporting scheme that shares the flow-tardiness information through a receiver-driven coordination. Our scheme can be flexibly and widely integrated with the state-of-the-art TCP protocols designed for data centers, while making no modification on switches. Through the testbed experiments and simulations of typical data center applications, we show that our scheme reduces the task completion time by 70% and 50% compared with the flow-based protocols (e.g. DCTCP, L2DCT) and task-based scheduling (e.g. Baraat), respectively. Moreover, our scheme also outperforms other approaches by 18% to 25% in prevalent topologies of data center.

In data center networks, many network-intensive applications leverage large fan-in and many-to-one communication to achieve high performance. However, the special traffic patterns, such as micro-burst and high concurrency, easily cause TCP Incast problem and seriously degrade the application performance. To address the TCP Incast problem, we first reveal theoretically and empirically that alleviating packet burstiness is much more effective in reducing the Incast probability than controlling the congestion window. Inspired by the findings and insights from our experimental observations, we further propose a general supporting scheme Adaptive Pacing (AP), which dynamically adjusts burstiness according to the flow concurrency without any change on switch. Another feature of AP is its broad applicability. We integrate AP transparently into different TCP protocols (i.e., DCTCP, L2DCT and D2TCP). Through a series of large-scale NS2 simulations, we show that AP significantly reduces the Incast probability across different TCP protocols and the network goodput can be increased consistently by on average 7x under severe congestion.

ZigBee is a widely used wireless technology in low-power and short-range scenarios such as Internet of Things (IoT), sensor networks, and industrial wireless networks. However, the standard ZigBee supports only one data rate, 250Kbps, which thoroughly limits ZigBee's efficiency in dynamic wireless channels. In this paper, we propose Mrs.Z, a novel physical layer design to enable multi-rate selection in ZigBee. The key idea is to change the single spectrum spreading length to multiple ones. Correspondingly, to gracefully adapt to the channel variations, we propose a BER-based rate selection scheme, dividing bit errors into two categories: errors caused by the exceeding despreading threshold, which can be discovered in the physical layer, and caused by incorrect despreading, which is not visible until cyclic redundancy check (CRC) in the media access control (MAC) layer. Then, the receiver selects the rate based on the underlying negative impacts incurred by them and feedbacks to the transceiver. We implement Mrs.Z on USRPs and evaluate its performance in different scenarios. Results demonstrate that Mrs.Z achieves an improvement of 20% and 80% compared to the classic SoftRate and the standard ZigBee.

Cross-technology communication (CTC) techniques are introduced in recent literatures to explore the opportunities of collaboration between heterogeneous wireless technologies, such as WiFi and ZigBee. Their applications include context-aware services and global channel coordination. However, state-of-the-art CTC schemes either suffer from channel inefficiency, low throughput, or disruption to existing networks. This paper presents the CTC via data packets (DCTC), which takes advantage of abundant existing data packets to construct recognizable energy patterns. DCTC features (i) a significant enhancement in CTC throughput while (ii) keeping transparent to upper layer protocols and applications. Our design also features advanced functions including multiplexing to support concurrent transmissions of multiple DCTC senders and adaptive rate control according to the traffic volume. Testbed implementations across WiFi and ZigBee platforms demonstrate reliable bidirectional communication of over 95% in accuracy while achieving throughput 2.3x of the state of the art. Meanwhile, experiment results show that DCTC has little and bounded impact on the delay and throughput of original data traffic.

Recent research on CTC (cross-technology communication) demonstrates the viability of direct coordination among heterogeneous devices (e.g., WiFi and ZigBee) with incompatible physical layers. Although encouraging, current solutions suffer from either severe inefficiency in channel utilization or low throughput using limited beacons. To address these limitations, this paper presents C-Morse, which leverages all traffic (such as through data packets, beacons and other control frames) to achieve a high cross-technology communication throughput. The key idea of C-Morse is to slightly perturb the transmission timing of existing WiFi packets to construct recognizable radio energy patterns without introducing noticeable delays to upper layers. At the receiver side, ZigBee captures such patterns by sensing the RSSI value, and then decodes the transmitted symbols. C-Morse also introduces a novel timing-based multiplexing technique to allow the coexistence of multiple C-Morse access points and reject other interference, showing a reliable symbol delivery ratio. As a result, C-Morse achieves a free side-channel, whose CTC throughput is as much as 9 χ of the present state of the art, while maintaining the through traffic within a negligible delay that goes unnoticed by applications and end-users.

Nowadays, public bike-sharing systems are broadly adopted and deployed in many major cities, however, as public facilities, bicycles will be prone to damage and need to be replaced frequently, which results in high system maintenance costs. One of the root causes of bicycle damages is the serious load-unbalance of bicycle usage. In this paper, we propose a hybrid bicycle allocation strategy for bicycle lifetime optimization, which can effectively reduce the degree of imbalance of system load. First, we analyze and verify the load-unbalance status of bicycle usage in the existing bike-sharing system. Then, a hybrid bicycle allocation strategy is proposed, which is evaluated on Washington D.C. bike-sharing system. Furthermore, according to a bicycle lifetime model based on Weibull distribution, the proposed bicycle allocation strategy could significantly cut down the percentage of the bicycles need to be replaced in a certain period of time.

Cross-Technology Communication is an emerging research direction providing a promising solution to the coexistence problem of heterogeneous wireless technologies in the ISM bands. However, existing works use only the coarse-grained packet-level information for cross-technology modulation, suffering from a low throughput (e.g., 10bps). Our approach, called BlueBee, aims at achieving much higher CTC throughput thus extends CTC applications. We pro- poses a new direction by emulating legitimate ZigBee frames using a Bluetooth Low Energy (BLE) radio. Uniquely, BlueBee achieves dual-standard compliance (i.e., BLE and ZigBee) and transparency by selecting only the payload of Bluetooth frames, requiring neither hardware nor firmware changes at the BLE senders and ZigBee receivers. Our implementation on commodity device testbeds shows that BlueBee can achieve a more than 99% accuracy and a through- put 10,000x faster than the state-of-the-art CTC reported so far. In addition, we show a demo of using BlueBee on a smartphone to control several smart light bulbs a ached with ZigBee radio.

Recent advances in Cross-Technology Communication (CTC) have improved efficient coexistence and cooperation among heterogeneous wireless devices (e.g., WiFi, ZigBee, and Bluetooth) operating in the same ISM band. However, until now the effectiveness of existing CTCs, which rely on packet-level modulation, is limited due to their low throughput (e.g., tens of bps). Our work, named WEBee, opens a promising direction for high-throughput CTC via physical-level emulation. WEBee uses a high-speed wireless radio (e.g., WiFi OFDM) to emulate the desired signals of a low-speed radio (e.g., ZigBee). Our unique emulation technique manipulates only the payload of WiFi packets, requiring neither hardware nor firmware changes in commodity technologies -- a feature allowing zero-cost fast deployment on existing WiFi infrastructure. We designed and implemented WEBee with commodity devices (Atheros AR2425 WiFi card and MicaZ CC2420) and the USRP-N210 platform (for PHY layer evaluation). Our comprehensive evaluation reveals that WEBee can achieve a more than 99% reliable parallel CTC between WiFi and ZigBee with 126 Kbps in noisy environments, a throughput about 16,000x faster than current state-of-the-art CTCs.

The applicability of existing Cross-Technology Communication (CTC) methods, which rely on packet-level modulation, is severely limited due to their very low throughput, e.g., tens of bps. Our work, named as WEBee, opens a promising direction for high throughput CTC via physical-level emulation. Specifically, WEBee synthesizes the time-domain signals by choosing appropriate frequency-domain components fed into the subcarriers of WiFi OFDM. WE-Bee can emulate the desired physical-layer ZigBee signals by manipulating only the data bits in WiFi packet payload, requiring neither hardware nor firmware changes in commodity technologies. Moreover, WEBee enables the parallel CTC, where one WiFi frame emulates two ZigBee frames simultaneously. To evaluate the performance, we implemented WEBee on commodity devices (the Atheros AR2425 WiFi card, BCM 4330 WiFi card and CC2420, CC2530 ZigBee devices). Our comprehensive evaluation reveals that WEBee can achieve the CTC between WiFi and ZigBee with a reliable throughput of 126Kbps in noisy environment, 16,000x faster than current state-of-the-art CTC methods.

Due to the energy security concern, our society is witnessing a surge of EV fleet applications, e.g., public EV taxi fleet systems. A major issue impeding an even more widespread adoption of EVs is range anxiety, which is due to several factors including limited battery capacity, limited availability of battery charging stations, and long charging time compared to traditional gasoline vehicles. By analyzing our accessible real-world EV taxi system-wide datasets, we observe that current EV taxi drivers often suffer from unpredictable, long waiting times at charging stations, due to temporally and spatially unbalanced utilization among charging stations. This is mainly because current taxi fleet management system simply rely on taxi drivers to make charging decisions. In this paper, In this paper, we develop REC, a Real-time Ev Charging scheduling framework for EV taxi fleets, which informs each EV taxi driver at runtime when and where to charge the battery. REC is able to analytically guarantee predictable and tightly bounded waiting times for all EVs in the fleet and temporally/spatially balanced utilization among charging stations, if each driver follows the charging decision made by REC. Moreover, REC can further efficiently handle real-life issues, e.g., allowing a taxi driver to charge at its preferred charging station while still guaranteeing balanced charging station utilization.We have extensively evaluated REC using our accessible real-world EV taxi system-wide datasets. Experimental results show that REC is able to address the unpredictability and unbalancing issues existing in current EV taxi fleet systems, yielding predictable and tightly bounded waiting times, and equally important, temporally/spatially balanced charging station utilization.

Cross-Technology Communication is an emerging research direction providing a promising solution to the wireless coexistence problem in the ISM bands. However, the state-of-the-art CTC designs have intrinsic limitations in the throughput due to their use of coarse-grained packet-level information. In contrast, we propose to exploit the fine-grained signal modulation information via a technique called PHY-layer emulation to boost CTC throughput. We can embed a legitimate packet of a target technology, e.g., ZigBee, within the payload of a source technology, e.g., WiFi or Bluetooth Low Energy (BLE). At the mean time, we require no modification at the hardware or firmware at either sender or receiver. We can achieve 8,000x throughput from WiFi to ZigBee and 10,000x throughput from BLE to ZigBee compared to the state of the art. We also have a demo showcasing how our designs can be implemented on off-the-shelf smartphones for smart light bulbs control.

Cross-Technology Communication is a promising solution proposed recently to the coexistence problem of heterogeneous wireless technologies in the ISM bands. The existing works use only the coarse-grained packet-level information for cross-technology modulation, suffering from a low throughput (e.g., 10bps). Our approach, called BlueBee, proposes a new direction by emulating legitimate ZigBee frames using a Bluetooth radio. Uniquely, BlueBee achieves dual-standard compliance and transparency by selecting only the payload of Bluetooth frames, requiring neither hardware nor firmware changes at the Bluetooth senders and ZigBee receivers. Our implementation on both USRP and commodity devices shows that BlueBee can achieve a more than 99% accuracy and a throughput 10,000x faster than the state-of-the-art CTC reported so far.

Many existing indoor localization systems have achieved applaudable performance through comprehensive modeling of its envisioned working scenario. However their real life deployment are often prohibited by high deployment overhead and performance degradation in dynamic environments. This paper presents SmartLight, a 3D digital indoor localization system based on LED lighting infrastructures. It adopts a novel design philosophy of shifting all the complexity into modifying a single LED lamp and maintaining minimum complexity on the receiver to reduce the hassle on system deployment/calibration. With a single modified LED lamp, the system is capable of localizing a large number of light sensors in a room. The underlying technique is to exploit the light splitting properties of convex lens to create an one-to-one mapping between a location and the set of orthogonal digital light signals receivable at that location. Advanced designs are also introduced to further improve the system accuracy and scalability beyond the hardware capability. In evaluating the design, we build an experimental prototype with a 60hz projector, achieving average localization around 10cm and 90 percentile error of 50cm.

One of essential components of public transport systems is to provide travel time estimates for a better travel experience. Based on these estimates, travelers can plan their departure time to meet their target time of arrival. Most of existing work has been focused on estimation on passenger riding time, which is relatively stable. However, a significant portion of time for a subway trip is spent on unstable walking and waiting. As a result, the work solely based on riding times underestimates the actual travel times. To fill the gap, we analyze travel data from automated ticketing systems, which are collected from a large group of passengers in a cost-effective way. We estimate each component (i.e., walking, waiting, and riding) of the travel time using tap-in and tap-out records of these passengers, by a novel travel time decomposition. We evaluate the performance of our travel time decomposition method based on large-scale real-world smart card data from more than 2 million users from Chinese city Shenzhen with 15 million smart card records. The results show that our estimation has an average estimation error of 8% on average and outperforms a baseline approach by 38%. Based on our travel time estimates, we further propose a practical application: digital advertising based on up-to-date travel demand.

Investigating passenger demand is essential for the taxicab business. Existing solutions are typically based on offline data collected by manual investigations, which are often dated and inaccurate for real-time analysis. To address this issue, we propose Dmodel, employing roving taxicabs as real-time mobile sensors to (i) infer passenger arriving moments by interactions of vacant taxicabs, and then (ii) infer passenger demand by customized online training with both historical and real-time data. Dmodel utilizes a novel parameter called pickup pattern based on an entropy of pickup events (accounts for various real-world logical information, e.g., bad weather) to reduce the size of big historical taxicab data to be processed. We evaluate Dmodel with a real-world 450 GB dataset of 14,000 taxicabs for a half year, and results show that compared to the ground truth, Dmodel achieves 83 percent accuracy and outperforms a statistical model by 42 percent. We further present an application where Dmodel is used to dispatch vacant taxicabs to achieve an equilibrium between passenger demand and taxicab supply across urban regions.

As one of the most popular cloud services, data storage has attracted great attention in recent research efforts. Key-value (k-v) stores have emerged as a popular option for storing and querying billions of key-value pairs. So far, existing methods have been deterministic. Providing such accuracy, however, comes at the cost of memory and CPU time. In contrast, we present an approximate k-v storage for cloud-based systems that is more compact than existing methods. The tradeoff is that it may, theoretically, return errors. Its design is based on the probabilistic data structure called “bloom filter”, where we extend the classical bloom filter to support key-value operations. We call the resulting design as the kBF (key-value bloom filter). We further develop a distributed version of the kBF (d-kBF) for the unique requirements of cloud computing platforms, where multiple servers cooperate to handle a large volume of queries in a load-balancing manner. Finally, we apply the kBF to a practical problem of implementing a state machine to demonstrate how the kBF can be used as a building block for more complicated software infrastructures.

In this article, we propose a transit service Feeder to tackle the last-mile problem, that is, passengers’ destinations lay beyond a walking distance from a public transit station. Feeder utilizes ridesharing-based vehicles (e.g., minibus) to deliver passengers from existing transit stations to selected stops closer to their destinations. We infer real-time passenger demand (e.g., exiting stations and times) for Feeder design by utilizing extreme-scale urban infrastructures, which consist of 10 million cellphones, 27 thousand vehicles, and 17 thousand smartcard readers for 16 million smartcards in a Chinese city, Shenzhen. Regarding these numerous devices as pervasive sensors, we mine both online and offline data for a two-end Feeder service: a back-end Feeder server to calculate service schedules and front-end customized Feeder devices in vehicles for real-time schedule downloading. We implement Feeder using a fleet of vehicles with customized hardware in a subway station of Shenzhen by collecting data for 30 days. The evaluation results show that compared to the ground truth, Feeder reduces last-mile distances by 68% and travel time by 56%, on average.

In many mobile sensing applications, devices need to discover new neighbors and maintain the rendezvous with known neighbors continuously. Due to the limited energy supply, these devices have to duty cycle their radios to conserve the energy and bandwidth, making neighbor discovery and rendezvous maintenance even more challenging. To date, the main mechanism for device discover and rendezvous maintenance in existing solutions is pairwise, direct one-hop communication. We argue that such pairwise direct communication is sufficient but not necessary: there exist unnecessary active slots that can be eliminated, without affecting discovery and rendezvous. In this work, we propose a novel concept ofextended quorum system, which leveragesindirectdiscovery to further conserve energy. Specifically, we usequorum graphto capture all possible information flow paths where knowledge about known-neighbors can propagate among devices. By eliminating redundant paths, we can reduce the number of active slots significantly. Since a quorum graph can characterize arbitrary active schedules of mobile devices, our work can be broadly used to improve many existing quorum-based discovery and rendezvous solutions. We comprehensively evaluate$EQS$in three different scales of networks, and the results show that$EQS$reduces as much as 55 percent energy consumption with a maximal 5 percent increase in latency for existing solutions. To test the real-world values of$EQS$, we further propose a taxicab dispatching application called$EQS$-dispatch to navigate taxicab drivers to the area with less competition based on the discovery results of nearby taxicabs.

As battery-powered mobile devices become more popular and energy hungry, wireless power transfer technology, which allows the power to be transferred from a charger to ambient devices wirelessly, receives intensive interests. Existing schemes mainly focus on the power transfer efficiency but overlook the health impairments caused by RF exposure. In this paper, we study the safe charging problem (SCP) of scheduling power chargers so that more energy can be received while no location in the field has electromagnetic radiation (EMR) exceeding a given threshold Rt. We show that SCP is NP-hard and propose a solution, which provably outperforms the optimal solution to SCP with a relaxed EMR threshold (1-ε)Rt. Testbed results based on 8 Powercast TX91501 chargers validate our results. Extensive simulation results show that the gap between our solution and the optimal one is only 6.7% when ε = 0.1, while a naive greedy algorithm is 34.6% below our solution.

Enabling direct communication between wireless technologies immediately brings significant benefits including, but not limited to, cross-technology interference mitigation and context-aware smart operation. To explore the opportunities, we propose FreeBee-a novel cross-technology communication technique for direct unicast as well as cross-technology/channel broadcast among three popular technologies of WiFi, ZigBee, and Bluetooth. The key concept of FreeBee is to modulate symbol messages by shifting the timings of periodic beacon frames already mandatory for diverse wireless standards. This keeps our design generically applicable across technologies and avoids additional bandwidth consumption (i.e., does not incur extra traffic), allowing continuous broadcast to safely reach mobile and/or duty-cycled devices. A new interval multiplexing technique is proposed to enable concurrent broadcasts from multiple senders or boost the transmission rate of a single sender. Theoretical and experimental exploration reveals that FreeBee offers a reliable symbol delivery under a second and supports mobility of 30 mph and low duty-cycle operations of under 5%.

This paper starts from an empirical observation on the existence of spatiotemporal correlation among nearby wireless links within short time intervals. The phenomenon due to correlated interference has become pervasive with densely deployed wireless devices, causing potential errors in existing popular metrics built upon the assumption of link independence. To this end, we propose correlated ETX (cETX), which generalizes the widely-adopted ETX to maintain the accuracy under correlated links. To the best of our knowledge, this is the first work to introduce a unified metric embracing both temporal and spatiotemporal correlations. As a generalized metric, the highlight of our work is the broad applicability and effectiveness-extensive evaluations on ZigBee (802.15.4) and Wi-Fi (802.11b/g/n) testbeds deployed in a lab, corridor, and on a bridge reveal that: simply replacing ETX with cETX: 1) cuts down the error by 62.1%-70.2% and 2) saves averages of 22% and 37% communication cost in three unicast and nine broadcast protocols, respectively, under only 0.7% additional overhead.

Recent research has shown that network coding has great potential to improve network performance in wireless communication. The performance of network coding in real-world scenarios, however, varies dramatically. It is reported that network coding brings negligible improvements but extra coding overhead in some scenarios. In this article, for the first time, we analyze the impact of link correlation on network coding and quantify the coding benefits. We propose correlated coding, which encodes packets only when performance improvement is achieved. Correlated coding uses only one-hop information, which makes it work in a fully distributed manner and introduces minimal communication overhead. The highlight of the design is its broad applicability and effectiveness. We implement the design with four broadcast protocols and three unicast protocols, and we evaluate them extensively on one 802.11 testbed and three 802.15.4 testbeds. The experimental results show that (i) more coding operations do not lead to fewer transmissions, and (ii) compared to existing network coding protocols, the number of transmissions is reduced with lower coding overhead.

Real-time traffic modeling at national scale is essential to many applications, but its calibration is extremely challenging due to its large spatial and fine temporal coverage. The existing work mostly is focused on urban-scale calibration with complete field data from single data sources (e.g., loop sensors or taxis), which cannot be generalized to national scale, because complete single-source field data at national scale are almost impossible to obtain. To address this challenge, in this paper, we design MultiCalib, a model calibration framework to optimize traffic models based on multiple incomplete data sources at national scale in real time. Instead of naively combining multi-source data, we theoretically formulate a multi-source model calibration problem based on real-world contexts and multi-view learning. More importantly, we implement and evaluate MultiCalib with two heterogeneous nationwide vehicle networks with 340,000 vehicles to infer traffic conditions on 36 expressways and 119 highways, along with 4 cities across China. The results show that MultiCalib outperforms state-of-the- art calibration by 25% on average with same input data.

Many-to-one data collection is a fundamental operation in wireless sensor networks (WSNs). To support long-term deployment of WSNs, sensor nodes normally operate at low-duty-cycles. However, the low-duty-cycle operation significantly reduces the communication chance between nodes. Consequently, the risk of data collisions significantly increases when multiple senders transmit packets to a receiver during its very short active period. Data collision not only results in wasted packet transmissions, but also incurs a large delivery latency. Under such conditions, collision-free medium access is more appealing than recovering after collision for low-duty-cycle WSNs. In this work, we propose an incast-collision-free data collection protocol, named iCore, to address the many-to-one collision problem in low-duty-cycle WSNs. iCore employs the dynamic forwarding technique and establishes a non-conflicting schedule for delay reduction. Specifically, we design efficient forwarder assignment and forwarding optimization algorithms that ensure low end-to-end latency under diverse data traffic types. Through comprehensive performance evaluations, we demonstrate that, compared with the state-of-the-art protocol, iCore effectively minimizes the end-to-end delay by 25% ∼ 57% and maintains high delivery ratio and energy efficiency for different many-to-one convergecast scenarios.

Wireless Power Transfer has become a commercially viable technology to charge devices because of the convenience of no power wiring and the reliability of continuous power supply. This paper concerns the fundamental issue of wireless charger placement with electromagnetic radiation (EMR) safety. Although there are a few wireless charging schemes consider EMR safety, none of them addresses the charger placement issue. In this paper, we propose PESA, a wireless charger Placement scheme that guarantees EMR SAfety for every location on the plane. First, we discretize the whole charging area and formulate the problem into the Multidimensional 0/1 Knapsack (MDK) problem. Second, we propose a fast approximation algorithm to the MDK problem. Third, we optimize our scheme to improve speed by double partitioning the area. We prove that the output of our algorithm is better than (1 - ϵ) of the optimal solution to PESA with a smaller EMR threshold (1 - ϵ/2)Rt and a larger EMR coverage radius (1 + ϵ/2)D. We conducted both simulations and field experiments to evaluate the performance of our scheme. Our experimental results show that in terms of charging utility, our algorithm outperforms the prior art by up to 45.7%.

In data center networks, many network-intensive applications typically suffer TCP incast throughput collapse when bursty concurrent TCP flows share a single bottleneck link. To address the TCP incast problem, we first reveal theoretically and empirically that controlling the number of concurrent flows is much more effective in reducing the incast probability than controlling the congestion window. We further propose a novel cross-layer design called Adaptive Request Schedule (ARS), which dynamically adjusts the number of concurrent TCP flows by batching application requests according to the congestion state acquired from transport layer. ARS is deployed only at the aggregator-side, while making no modification on hundreds or thousands of workers. Broad applicability is another advantage of ARS. We integrated ARS transparently (i.e., without modification) with DCTCP and TCP NewReno on NS2 simulation and a physical testbed, respectively. The experimental results show that ARS significantly reduces the incast probability across different TCP protocols and that the network goodput can be increased consistently by on average 6x under severe congestion.

Internet of Things (IoT) is founded on the unprecedented proliferation of heterogeneous wireless technologies. However, dense deployment of such devices intensify the interference, which has become a major cause of performance degradation. This paper first introduces schemes for harmonious coexistence. Our designs effectively enhance diverse existing protocols via a complementing middle layer that enables real-time adaptation to the spatial and temporal dynamics of interferences. Further, a technique to explore the opportunity behind heterogeneous wireless technologies is introduced. By extending direct connectivity between heterogeneous technologies, the design uniquely enables their collaboration to reach beyond the capabilities of each technology.

Micro-powered wireless embedded devices are widely used in many application domains. Their efficiency in practice, however, is significantly constrained by the dual limitations of low harvesting rates and tiny energy buffer. Recent research presents a network stack that efficiently fragments a large packet into many smaller packets that can fit within the available energy in the energy buffer of limited size. While this fragmentation technique represents a major step forward in solving the minuscule energy budget problem, it also introduces a tremendous practical challenge where potentially many fragmented packets belonging to different devices may contend for the communication channel. Designing purely heuristic-based packet transmission protocol is undesirable because the resulting per-packet and end-to-end transmission delay are unknown, thus causing unpredictable system performance which is unacceptable for many applications with real-time constraints. In this paper, we first formulate this packet transmission scheduling problem considering physical properties of the charging and transmission processes. We then develop a novel packet prioritization and transmission protocol NERF that yields tight and predictable delay bounds for transmitting packets from multiple micropowered devices to a charger. We have implemented our protoco on top of the WISP 4.1 platform and the SPEEDWAY RFID READER, and conducted validation experiments. Our experiments validate the correctness of our implementation and show that NERF can reduce the total collection delay by 40% when compared to an existing protocol ALOHA. We have also performed extensive data trace-driven simulations. Simulation results demonstrate the effectiveness of our proposed protocol. On average, our protocol yields an over 30%improvement in terms of runtime transmission delay compared to existing methods, while being able to guarantee tight and provable response time bounds.

Wireless rechargeable sensor networks have recently emerged as a promising platform that can effectively solve the power constraint problem suffered by traditional battery powered systems. The problem of determining the best charging routes for maximizing charging efficiency has been studied extensively. However, the task assignment problem, which plays a crucial role in efficiently utilizing the harvested energy and thus minimize the charging delay, has received rather limited attention. In this paper, we study the problem of assigning a given set of tasks in a wireless rechargeable sensor network while maximizing the charger's velocity to minimize the charging delay. We first propose an online task assignment algorithm, namely Lower Bound assignment (LB), that yields a quantifiable lower bound on the charging velocity while guaranteeing a feasible assignment. This algorithm further enables the transformation of our considered task assignment problem into a variation of the classical multiple knapsack problem. We then present a fully polynomial-time approximation scheme with a (2+ε)-approximation ratio, namely ACT, that is built upon an existing greedy algorithm designed for the original knapsack problem. Extensive experimental results presented herein demonstrate that ACT is able to achieve near-optimal performance in most cases, and can achieve more than 15% performance improvement compared to the baseline algorithms.

Recent studies on CTC (cross-technology communication) have demonstrated the possibility of building direct communication between heterogeneous wireless communication technologies, such as WiFi and ZigBee. However, current solutions suffer from significant spectrum usage or limited throughput. To address the issues, this paper presents Transparent Cross-technology Communication (TCTC), a novel CTC technique that establishes a side channel by exploiting today's abundant wireless traffic. The key idea of TCTC is to embed messages in the timings of on-going legacy traffic (e.g., HTTP packets in WiFi), with small and bounded impact on upper-layer applications. Feasibility and effectiveness of our design has been validated via test-bed implementations and experiments on bidirectional communication between WiFi and ZigBee platforms.

In this poster, we present an Urban Sensor Network (USN) from a board perspective, i.e., any device in urban infrastructures is considered as a pervasive urban sensor if it generates data about residents' locations. Built upon correlation and divergence among various urban sensors, we aim to provide unseen urban dynamics in fined-grained spatio-temporal resolutions to support novel smart cities services. As opposed to previous ad hoc sensor networks, our approach aims to establish USN in a modular architecture as a middleware with open interfaces to various lower level urban infrastructures, ensuing interoperability and flexibility, which are crucial prerequisites for higher level applications.

Traditional compressive sensing (CS) methods assume the data sparsity to be constant over time, which holds well in many long‐term scenarios. However, the authors’ recent study on electrocardiogram (ECG) monitoring reveals that data sparsity varies dramatically for real‐time monitoring systems where the data latency must be bounded, due to limited data collected within the delay bound. The variation of data sparsity makes the reconstruction error (RE) unstable. Furthermore, the variation of wireless channel quality also impacts the reconstruction quality. To accommodate both variations, this study proposes a novel adaptive feedback architecture for real‐time wireless ECG monitoring based on the CS technique, which can bound the REs in the presence of the variations of data sparsity and wireless channel. An experiment testbed has been built to evaluate the performance of the proposed system. The results show that the data latency can be limited to <300 ms and the RE can be controlled to 9%.

Traditional taxi systems in metropolitan areas often suffer from inefficiencies due to uncoordinated actions as system capacity and customer demand change. With the pervasive deployment of networked sensors in modern vehicles, large amounts of information regarding customer demand and system status can be collected in real time. This information provides opportunities to perform various types of control and coordination for large-scale intelligent transportation systems. In this paper, we present a receding horizon control (RHC) framework to dispatch taxis, which incorporates highly spatiotemporally correlated demand/supply models and real-time Global Positioning System (GPS) location and occupancy information. The objectives include matching spatiotemporal ratio between demand and supply for service quality with minimum current and anticipated future taxi idle driving distance. Extensive trace-driven analysis with a data set containing taxi operational records in San Francisco, CA, USA, shows that our solution reduces the average total idle distance by 52%, and reduces the supply demand ratio error across the city during one experimental time slot by 45%. Moreover, our RHC framework is compatible with a wide variety of predictive models and optimization problem formulations. This compatibility property allows us to solve robust optimization problems with corresponding demand uncertainty models that provide disruptive event information.

Data-driven modeling usually suffers from data sparsity, especially for large-scale modeling for urban phenomena based on single-source urban-infrastructure data under fine-grained spatial-temporal contexts. To address this challenge, we motivate, design, and implement UrbanCPS, a cyber-physical system with heterogeneous model integration, based on extremely-large multi-source infrastructures in the Chinese city Shenzhen, involving 42,000 vehicles, 10 million residents, and 16 million smartcards. Based on temporal, spatial, and contextual contexts, we formulate an optimization problem about how to optimally integrate models based on highly diverse datasets under three practical issues, that is, heterogeneity of models, input data sparsity, or unknown ground truth. We further propose a real-world application called Speedometer, inferring real-time traffic speeds in urban areas. The evaluation results show that, compared to a state-of-the-art system, Speedometer increases the inference accuracy by 29% on average.

Wireless sensor networks have been used in many mobile applications such as wildlife tracking and participatory urban sensing. Because of the combination of high mobility and low-duty-cycle operations, it is a challenging issue to reduce discovery delay among mobile nodes, so that mobile nodes can establish connection quickly once they are within each other's vicinity. Existing discovery designs are essentially pairwise based, in which discovery is passively achieved when two nodes are prescheduled to wake up at the same time. In contrast, this work reduces discovery delay significantly by proactively referring wake-up schedules among a group of nodes. Since proactive references incur additional overhead, we introduce a novel selective reference mechanism based on spatiotemporal properties of neighborhood and the mobility of nodes. Our quantitative analysis indicates that the discovery delay of our group-based mechanism is significantly smaller than that of the pairwise one. Our testbed experiments using 40 sensor nodes and extensive simulations confirm the theoretical analysis, showing one order of magnitude reduction in discovery delay compared with legacy pairwise methods in dense, uniformly distributed sensor networks with at most 8.8 percent increase in energy consumption.

Limited energy in each node is the major design constraint in wireless sensor networks (WSNs). To overcome this limit, wireless rechargeable sensor networks (WRSNs) have been proposed and studied extensively over the last few years. In a typical WRSN, batteries in sensor nodes can be replenished by a mobile charger that periodically travels along a certain trajectory in the sensing area. To maximize the charged energy in sensor nodes, one fundamental question is how to control the traveling velocity of the charger. In this paper, we first identify the optimal velocity control as a key design objective of mobile wireless charging in WRSNs. We then formulate the optimal charger velocity control problem on arbitrarily-shaped irregular trajectories in a 2D space. The problem is proved to be NP-hard, and hence a heuristic solution with a provable upper bound is developed using novel spatial and temporal discretization. We also derive the optimal velocity control for moving the charger along a linear (1D) trajectory commonly seen in many WSN applications. Extensive simulations show that the network lifetime can be extended by 2.5× with the proposed velocity control mechanisms.

Reliable flooding in wireless sensor networks (WSNs) is desirable for a broad range of applications and network operations. However, relatively little work has been done for reliable flooding in low-duty-cycle WSNs with unreliable wireless links. It is a challenging problem to efficiently ensure 100% flooding coverage considering the combined effects of low-duty-cycle operation and unreliable wireless transmission. In this paper, we propose a novel dynamic switching-based reliable flooding (DSRF) framework, which is designed as an enhancement layer to provide efficient and reliable delivery for a variety of existing flooding tree structures in low-duty-cycle WSNs. The key novelty of DSRF lies in the dynamic switching decision making when encountering a transmission failure, where a flooding tree structure is dynamically adjusted based on the packet reception results for energy saving and delay reduction. DSRF distinguishes itself from the existing works in that it explores both poor links and good links on demand. In addition, we define the optimal wakeup schedule-ranking problem in order to maximize the switching gain in DSRF. We prove the NP-completeness of this problem and present a heuristic algorithm with a low computational complexity. Through comprehensive performance comparisons, including the simulation of large-scale scenarios and small-scale experiments on a WSN testbed, we demonstrate that compared with the flooding protocol without DSRF enhancement, the DSRF effectively reduces the flooding delay and the total number of packet transmission by 12%' 25% and 10%' 15%, respectively. Remarkably, the achieved performance is close to the theoretical lower bound.

Extensive empirical studies presented in this article confirm that the quality of radio communication between low-power sensor devices varies significantly with time and environment. This phenomenon indicates that the previous topology control solutions, which use static transmission power, transmission range, and link quality, might not be effective in the physical world. To address this issue, online transmission power control that adapts to external changes is necessary. This article presents ATPC, a lightweight algorithm for Adaptive Transmission Power Control in wireless sensor networks. In ATPC, each node builds a model for each of its neighbors, describing the correlation between transmission power and link quality. With this model, we employ a feedback-based transmission power control algorithm to dynamically maintain individual link quality over time. The intellectual contribution of this work lies in a novel pairwise transmission power control, which is significantly different from existing node-level or network-level power control methods. Also different from most existing simulation work, the ATPC design is guided by extensive field experiments of link quality dynamics at various locations over a long period of time. The results from the real-world experiments demonstrate that (1) with pairwise adjustment, ATPC achieves more energy savings with a finer tuning capability, and (2) with online control, ATPC is robust even with environmental changes over time.

This article demonstrates how to use multiple channels to improve communication performance in Wireless Sensor Networks (WSNs). We first investigate multichannel realities in WSNs through intensive empirical experiments with Micaz motes. Our study shows that current multichannel protocols are not suitable for WSNs because of the small number of available channels and unavoidable time errors found in real networks. With these observations, we propose a novel tree-based, multichannel scheme for data collection applications, which allocates channels to disjoint trees and exploits parallel transmissions among trees. In order to minimize interference within trees, we define a new channel assignment problem that is proven NP-complete. Then, we propose a greedy channel allocation algorithm that outperforms other schemes in dense networks with a small number of channels. We implement our protocol, called the Tree-based, Multichannel Protocol (TMCP), in a real testbed. To adjust to networks with link quality heterogeneity, an extension of TMCP is also proposed. Through both simulation and real experiments, we show that TMCP can significantly improve network throughput and reduce packet losses. More important, evaluation results show that TMCP better accommodates multichannel realities found in WSNs than other multichannel protocols.

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.

Carpooling has long held the promise of reducing gas consumption by decreasing mileage to deliver coriders. Although ad hoc carpools already exist in the real world through private arrangements, little research on the topic has been done. In this article, we present the first systematic work to design, implement, and evaluate a carpool service, called coRide , in a large-scale taxicab network intended to reduce total mileage for less gas consumption. Our coRide system consists of three components, a dispatching cloud server, passenger clients, and an onboard customized device, called TaxiBox . In the coRide design, in response to the delivery requests of passengers, dispatching cloud servers calculate cost-efficient carpool routes for taxicab drivers and thus lower fares for the individual passengers. To improve coRide ’s efficiency in mileage reduction, we formulate an NP-hard route calculation problem under different practical constraints. We then provide (1) an optimal algorithm using Linear Programming, (2) a 2-approximation algorithm with a polynomial complexity, and (3) its corresponding online version with a linear complexity. To encourage coRide ’s adoption, we present a win-win fare model as the incentive mechanism for passengers and drivers to participate. We test the performance of coRide by a comprehensive evaluation with a real-world trial implementation and a data-driven simulation with 14,000 taxi data from the Chinese city Shenzhen. The results show that compared with the ground truth, our service can reduce 33% of total mileage; with our win-win fare model, we can lower passenger fares by 49% and simultaneously increase driver profit by 76%.

Severe pollution induced by traditional fossil fuels arouses great attention on the usage of plug-in electric vehicles (PEVs) and renewable energy. However, large-scale penetration of PEVs combined with other kinds of appliances tends to cause excessive or even disastrous burden on the power grid, especially during peak hours. This paper focuses on the scheduling of PEVs charging process among different charging stations and each station can be supplied by both renewable energy generators and a distribution network. The distribution network also powers some uncontrollable loads. In order to minimize the on-grid energy cost with local renewable energy and non-ideal storage while avoiding the overload risk of the distribution network, an online algorithm consisting of scheduling the charging of PEVs and energy management of charging stations is developed based on Lyapunov optimization and Lagrange dual decomposition techniques. The algorithm can satisfy the random charging requests from PEVs with provable performance. Simulation results with real data demonstrate that the proposed algorithm can decrease the time-average cost of stations while avoiding overload in the distribution network in the presence of random uncontrollable loads.

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.

Nowadays most metro advertising systems schedule advertising slots on digital advertising screens to achieve the maximum exposure to passengers by exploring passenger demand models. However, our empirical results show that these passenger demand models experience uncertainty at fine temporal granularity (e.g., per min). As a result, for fine-grained advertisements (shorter than one minute), a scheduling based on these demand models cannot achieve the maximum advertisement exposure. To address this issue, we propose an online advertising approach, called EveryoneCounts, based on an uncertain passenger demand model. It combines coarse-grained statistical demand modeling and fine-grained Bayesian demand modeling by leveraging realtime card-swiping records along with both passenger mobility patterns and travel periods within metro systems. Based on this uncertain demand model, it schedules advertising time online based on robust receding horizon control to maximize the advertisement exposure. We evaluate the proposed approach based on an one-month sample from our 530 GB real-world metro fare dataset with 16 million cards. The results show that our approach provides a 61.5% lower traffic prediction error and 20% improvement on advertising efficiency on average.

Real-time human mobility modeling is essential to various urban applications. To model such human mobility, numerous data-driven techniques have been proposed. However, existing techniques are mostly driven by data from a single view, e.g., a transportation view or a cellphone view, which leads to over-fitting of these single-view models. To address this issue, we propose a human mobility modeling technique based on a generic multi-view learning framework called coMobile. In coMobile, we first improve the performance of single-view models based on tensor decomposition with correlated contexts, and then we integrate these improved single-view models together for multi-view learning to iteratively obtain mutually-reinforced knowledge for real-time human mobility at urban scale. We implement coMobile based on an extremely large dataset in the Chinese city Shenzhen, including data about taxi, bus and subway passengers along with cellphone users, capturing more than 27 thousand vehicles and 10 million urban residents. The evaluation results show that our approach outperforms a single-view model by 51% on average.

Modern data center nowadays leverages highly concurrent TCP connections between thousands of computer servers to achieve high system performance and service reliability. However, recent works have shown that, in the many-to-one and barrier-synchronized communication pattern, a large number of concurrent TCP connections suffer the TCP Incast problem due to packet drops in shallow-buffered Ethernet switches. This problem unavoidably leads to severe under-utilization of link capacity. In this work, we first reveal theoretically and empirically that controlling the IP packet size reduces the Incast probability much more effectively than controlling the congestion windows in the presence of severe congestion. We further present the design and implementation of Packet Slicing, a general supporting scheme that adjusts the packet size through a standard ICMP signaling method. Our method can be deployed on commodity switches with small firmware updates, while making no modification on end hosts. Another highlight of our work is Packet Slicing's broad applicability and effectiveness. We integrate Packet Slicing transparently (i.e., without modification) with three state-of-the-art TCP protocols designed for data centers on NS2 simulation and a physical testbed, respectively. The experimental results show that Packet Slicing remarkably improves network goodput across different TCP protocols by average 26× under severe congestion, while introducing little I/O performance impact on both switches and end hosts.

Contradicting the widely believed assumption of link independence, recently the phenomenon of reception correlation among nearby receivers has been revealed and exploited for varieties of protocols [3], [8], [17], [21], [23], [24]. However, despite the diversified correlation-aware designs proposed up to date, they commonly suffer from a shortcoming where link correlation is inaccurately measured, which leads them to sub-optimal performance. In this work we propose a general framework for accurate capturing of link correlation, enabling better utilization of the phenomenon for protocols lying on top of it. Our framework uses SINR (Signal to Interference plus Noise Ratio) to detect correlations, followed by modeling the correlations for in-network use. We show that our design is light-weight, both computation and storage-wise. We apply our model to opportunistic routing and network coding on a physical 802.15.4 test-bed for energy savings of 25% and 15%.

In this paper, we propose a transit service Feeder to tackle the last-mile problem, i.e., passengers' destinations lay beyond a walking distance from a public transit station. Feeder utilizes ridesharing-based vehicles (e.g., minibus) to deliver passengers from existing transit stations to selected stops closer to their destinations. We infer real-time passenger demand (e.g., exiting stations and times) for Feeder design by utilizing extreme-scale urban infrastructures, which consist of 10 million cellphones, 27 thousand vehicles, and 17 thousand smartcard readers for 16 million smartcards in a Chinese city Shenzhen. Regarding these numerous devices as pervasive sensors, we mine both online and offline data for a two-end Feeder service: a back-end Feeder server to calculate service schedules; front-end customized Feeder devices in vehicles for real-time schedule downloading. The evaluation results show that compared to the ground truth, Feeder reduces last-mile distances by 68% and travel time by 52% on average.

As an important supporting technology, floor localization in multi-floor buildings plays significant roles in many indoor Location Based Service (LBS) applications such as the fire emergency response and the floor-based precise advertising. While the majority of Received-Signal-Strength (RSS)-fingerprint-based wireless indoor localization approaches suffer from the labor-intensive and time-consuming site-survey and the low localization accuracy, barometer-based floor localization is another promising direction due to the increasing availability of the barometer-sensor-equipped smartphones. This paper is the first indoor localization work that exploits the combination of Wi-Fi RSS and barometric pressure for accurate floor localization. Compared with an art-of-the-state algorithm, B-Loc, the highlight of the proposed Bar Fi approach is that it does not need all client smartphones but only low percentage of them equipped with barometer sensors. Using crowd sourcing, Bar Fi eliminates the need of war-driving of site-survey and prior knowledge about both the Wi-Fi infrastructure and the floor plans of buildings. The key novelty of Bar Fi is a two-phase clustering method proposed to train the RSS fingerprint floor map with the aid of barometer, which consists of a barometer-based hierarchical clustering phase and a Wi-Fi-based K-Means clustering phase. The real-world evaluation shows Bar Fi achieves satisfying performance that its accuracy reaches 96.3% when the proportion of smartphones equipped with barometer sensors is 12% out of the total.

This paper presents FreeBee, which enables direct unicast as well as cross-technology/channel broadcast among three popular wireless technologies: WiFi, ZigBee, and Bluetooth. Our design aims to shed the light on the opportunities that cross-technology communication has to offer including, but not limited to, cross-technology cooperation and coordination. The key concept of FreeBee is to modulate symbol messages by shifting the timing of periodic beacon frames already mandatory for wireless standards without incurring extra traffic. Such a generic cross-technology design consumes zero additional bandwidth, allowing continuous broadcast to safely reach mobile and/or duty-cycled devices. A new \emph{interval multiplexing} technique is proposed to enable concurrent broadcasts from multiple senders or boost the transmission rate of a single sender. Theoretical and experimental exploration reveals that FreeBee offers a reliable symbol delivery under a second and supports mobility of 30mph and low duty-cycle operations of under 5%.

Although GPS has become a standard component of smartphones, providing accurate navigation during the last portion of a trip remains an important but unsolved problem. Despite extensive research on localization, the limited resolution of a map imposes restrictions on the navigation engine in both indoor and outdoor environments. To bridge the gap between the end position obtained from legacy navigation services and the real destination, we propose FollowMe, a "last-mile" navigation system to enable plug-and-play navigation in indoor and semi-outdoor environments. FollowMe exploits the ubiquitous, stable geomagnetic field and natural walking patterns to navigate the users to the same destination taken by an earlier traveler. Unlike existing localization and navigation systems, FollowMe is infrastructure-free, energy-efficient and cost-saving. We implemented FollowMe on smartphones, and evaluated it in a four-story campus building with a testing area of 2000m2. Our experimental results with 5 users show that 95% of spatial errors during navigation were 2m or less with at least 50% energy savings over a benchmark system.

Radio duty cycling is a commonly employed mechanism to support long-term sustainable operations of WSNs. Combined with the effect of unreliable wireless links, many challenges arise for ensuring delay bounded data delivery with reliability constraint. However, research on energy-efficient data forwarding with statistical delay bound in duty-cycled WSNs still remains unaddressed. This paper proposes EDGE, a novel opportunistic forwarding technique tailored for duty-cycled WSNs with unreliable wireless links. The key idea is to exploit the available path diversity to minimize the transmission cost while providing statistical delay guarantees. Delay quantiles are derived at each node in a distributed manner and are used as the guidelines in forwarding decision making, so that an early arriving packet will be opportunistically switched to the energy-optimal path for communication cost minimization. Comprehensive evaluation results show that EDGE effectively reduces the transmission cost with statistical delay guarantees under various network settings.

In this work, we experimentally observe the existence of spatiotemporal correlation among adjacent wireless links within short time intervals. Such an observation calls attention to potential errors in existing popular metrics built upon the assumption of link independence. Specifically we propose cETX (correlated ETX), a generalized metric, to compensate for estimation errors suffered by the widely-adopted ETX in the presence of correlated interference. To the best of our knowledge, this is the first work to introduce a unified metric embracing both temporal and spatiotemporal correlations. The highlight of the cETX metric is its broad applicability and effectiveness. Evaluations on ZigBee (802.15.4) and Wi-Fi (802.11b/g/n) testbeds deployed in a lab, corridor, and on a bridge reveal that: Simply replacing ETX with cETX (i) cuts down the error by 70.2% and 62.1%, respectively, and (ii) saves averages of 22% and 37% communication cost in three unicast [4, 13, 17] and nine broadcast protocols [7, 18, 23, 24, 27, 30, 40] at the price of only 0.7% additional overhead.

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.

Existing work on flooding in wireless sensor networks (WSNs) mainly focuses on single-packet problem, while the work on sequential multipacket problem is surprisingly little. This paper proposes OppCode, a new opportunistic network-coding-based flooding architecture for multipacket dissemination in WSNs, where both unreliable and correlated links commonly exist. Instead of flooding a single packet each time, each node encodes multiple native packets chosen from a specific fixed-size page to an encoded packet and then rebroadcasts it further. The key idea consists of two parts. One is opportunistically coding decision, in which each node grasps every possible coding opportunity greedily to maximize its aggregate coding gain of all neighbors based on the probabilistic estimation of packets each neighbor already has. The other is paged collective acknowledgements (ACKs), in which one rebroadcast acts as not only an implicit ACK of successful disseminations of all packets in the entire page for the sender, but also probabilistic ACK to update page-scale per-packet coverage estimations for its neighbors in a batch. Experiments based on extensive simulations and 21-node testbed show that OppCode significantly increases performance of multipacket flooding in terms of reliability, transmission overhead, delay, and load balance.

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.

Many applications in wireless sensor networks require communication performance that is both consistent and of high quality. Unfortunately, performance of current network protocols can vary significantly because of various interferences and environmental changes. Current protocols estimate link quality based on the reception of probe packets over a short time period. This method is neither efficient nor accurate enough to capture the dramatic variations of link quality. Therefore, we propose a link metric called competence that characterizes links over a longer period of time. We combine competence with current short-term estimations in routing algorithm designs. To further improve network performance, we have designed a distributed route maintenance framework based on feedback control solutions. This framework allows every link along an end-to-end (E2E) path to adjust its link protocol parameters, such as transmission power and number of retransmissions, to ensure specified E2E reliability and latency under dynamic link qualities. Our solutions are evaluated in both extensive simulations and real system experiments. In real system evaluations with 48 T-Motes, our overall solution improves E2E packet delivery ratio over existing solutions by up to 40% while reducing transmission energy consumption by up to 22%. Importantly, our solution also achieves more stable and better transient performance than current approaches.

The wireless rechargeable sensor network is a promising platform for long-term applications such as inventory management, supply chain monitoring, and so on. For these applications, sensor localization is one of the most fundamental challenges. Different from a traditional sensor node, a wireless rechargeable sensor has to be charged above a voltage level by the wireless charger in order to support its sensing, computation, and communication operations. In this work, we consider the scenario where a mobile charger stops at different positions to charge sensors and propose a novel localization design that utilizes the unique Time of Charge (TOC) sequences among wireless rechargeable sensors. Specifically, we introduce two efficient region dividing methods, Internode Division and Interarea Division , to exploit TOC differences from both temporal and spatial dimensions to localize individual sensor nodes. To further optimize the system performance, we introduce both an optimal charger stop planning algorithm for the single-sensor case and a suboptimal charger stop planning algorithm for the generic multisensor scenario with a provable performance bound. We have extensively evaluated our design by both testbed experiments and large-scale simulations. The experiment and simulation results show that by as less as five stops, our design can achieve sub-meter accuracy and the performance is robust under various system conditions.

As a supporting primitive of many mobile applications, neighbor discovery identifies nearby devices so that they can exchange information and collaborate in a peer-to-peer manner. To date, discovery schemes trade a long latency for energy efficiency and require a collaborative duty cycle pattern, and thus they are not suitable for interactive mobile applications where a user is unable to configure others’ devices. In this article, we propose Acc , which serves as an on-demand generic discovery accelerating middleware for many deterministic neighbor discovery schemes. Acc leverages the discovery capabilities of neighbor devices, supporting both direct and indirect neighbor discoveries. Further, we present a proactive online rendezvous maintenance mechanism, which is used to reduce delays for the detection of leaving of neighbors. Our evaluations show that Acc -assisted discovery schemes reduce latency by up to 51.8% compared to schemes consuming the same amount of energy. More importantly, to prove the real-world value of Acc , we further present and evaluate a Crowd-Alert application where Acc is employed by taxi drivers to accelerate selection of a direction with fewer competing taxis and more potential passengers, based on a 280GB dataset of more than 14,000 taxis in Shenzhen, the most crowded city in China.

In the taxicab industry, a long-standing challenge is how to reduce taxicabs' miles spent without fares, i.e., cruising miles. The current solutions for this challenge usually depend on passengers to actively provide their locations in advance for pickups. To address this challenge without the burden on passengers, in this paper, we propose a cruising system, pCruise, for taxicab drivers to find efficient routes to pick up passengers to reduce cruising miles. According to the real-time pick-up events from nearby taxicabs, pCruise characterizes a cruising process with a cruising graph, and assigns weights on edges of the cruising graph to indicate the utility of cruising corresponding road segments. Our weighting process considers the number of nearby passengers and taxicabs together in real-time, aiming at two scenarios where taxicabs are explicitly or implicitly coordinated with each other. Based on a weighted cruising graph, when a taxicab becomes vacant, pCruise provides a distributed online scheduling strategy to obtain and update an efficient cruising route with the minimum length and at least one arriving passenger. We evaluate pCruise based on a real-world GPS dataset from a Chinese city Shenzhen with 14;000 taxicabs. The evaluation results show that pCruise assists taxicab drivers to reduce cruising miles by 42 percent on average.

Low-duty-cycle operation has been adopted to alleviate the consumption rate of energy, which is significant for the power scarcity sensor networks. The sleep latency brought by low-duty-cycle mode, however, leads to a dramatic increase of delay, which may not be tolerable for delay-sensitive applications. In this work, we introduce the transmission power control mechanism into low-duty-cycle sensor networks. Particularly, we propose Delay-bounded Transmission Power Control (DTPC), a cross-layer approach, to minimize the energy consumption of sensor nodes while meeting the user-specified delay constraint. In DTPC, each node builds its own transmission table using dynamical programming and then adaptively selects the approximate forwarding entry according to the delay bound. In addition, our design is embedded to support both single-parent and multi-parent data forwarding scheme. The extensive simulations and test-bed experiment results show that DTPC can guarantee the delay bound with much lower energy cost compared with other well-known schemes.

Recent empirical studies have shown clear evidence that wireless links are not independent and that the packet receptions on adjacent wireless links are correlated. This finding contradicts the widely held link-independence assumption in the calculation of the core metric, i.e., the expected number of transmissions to the candidate forwarder set, in opportunistic routing (OR). The inappropriate assumption may cause serious estimation errors in the forwarder set selection, which further leads to underutilized diversity benefits or extra scheduling costs. We thus advocate that OR should be made aware of link correlation. In this paper, we propose a novel link-correlation-aware OR scheme, which significantly improves the performance by exploiting the diverse low correlated forwarding links. We evaluate the design in a real-world setting with 24 MICAz nodes. Testbed evaluation and extensive simulation show that higher link correlation leads to fewer diversity benefits and that, with our link-correlation-aware design, the number of transmissions is reduced by 38%.

Wireless power transfer technology is considered as one of the promising solutions to address the energy limitation problems for end-devices, but its incurred potential risk of electromagnetic radiation (EMR) exposure is largely overlooked by most existing works. In this paper, we consider the Safe Charging with Adjustable PowEr (SCAPE) problem, namely, how to adjust the power of chargers to maximize the charging utility of devices, while assuring that EMR intensity at any location in the field does not exceed a given threshold Rt. We present novel techniques to reformulate SCAPE into a traditional linear programming problem, and then remove its redundant constraints as much as possible to reduce computational effort. Next, we propose a distributed algorithm with provable approximation ratio (1 - ε). Through extensive simulation and testbed experiments, we demonstrate that our (1 - ε)-approximation algorithm outperforms the Set-Cover algorithm by up to 23%, and has an average performance gain of 41.1% over the SCP algorithm in terms of the overall charging utility.

In wireless networks, duty-cycling operations have been widely used to reduce the energy cost of RF idle listening at wireless receivers. Such operations, however, introduce delays in data forwarding because a sender has to wait for a targeted receiver to wake up. To reduce end-to-end delivery delays, researchers have proposed scheduling techniques [1], [2], [3] to wake up nodes along the data forwarding path at the right moment. However, these techniques consider only one-way delivery from a sink to nodes (or vice versa), failing to optimally support round-trip network operations such as (i) query and response, (ii) command and control and (iii) data fetching. In this work, we interestingly reveal that the optimal roundtrip delay in a low-duty-cycle network depends only on (i) duty cycle period and (ii) the number of 2-connected network components between the source and destination nodes. We prove that optimality in the round-trip delay can be achieved by establishing a simple circular path and its related cords, in which nodes are assigned wake-up slots in an ascending order in each network component, and connecting these paths into a circular pipeline. We compared our Circular Pipelining (CP) algorithm with the state-of-art solutions [3], and the experimental results show that without using circular forwarding, existing solutions have a round-trip delay proportional to the network diameter, while CP remains a minimal constant delay of T as long as the network is 2-connected. We also implement the Circular Pipelining (CP) algorithm in a test bed consisting of 30 MICAz nodes, achieving significant delay reduction compared to three baseline solutions in the literature.

Diversity-based protocols such as network coding and opportunistic routing have been proposed in recent years to exploit spatial diversity in wireless communication. By utilizing concurrent links, these protocols achieve significantly better performance than traditional approaches. However, they explicitly or implicitly assume that wireless links are independent, which overestimates the true spatial diversity in reality. For the first time, this paper analyzes the impact of link correlation on network coding and introduces Correlated Coding, a link correlation-aware design that seeks to optimize the transmission efficiency by maximizing necessary coding opportunities. Correlated coding uses only one-hop information, which makes it work in a fully distributed manner and introduces minimal communication overhead. The highlight of our design is its broad applicability and effectiveness. We implement our design with four broadcast protocols and three unicast protocols, and evaluate them extensively with one 802.11 test bed and three 802.15.4 test beds running TelosB, MICAz, and Green Orbs nodes. The experiment results show that (i) more coding opportunities do not lead to more transmission benefits, and (ii) compared to coding aware protocols, the number of coding operations is reduced while the transmission efficiency is improved.

As battery-powered mobile devices become more popular and energy hungry, wireless power transfer technology receives intensive interests, as it allows the power to be transferred from a charger to ambient devices wirelessly. The existing studies mainly focus on the power transfer efficiency but overlook the health impairments caused by RF exposure. In this paper, we study the Safe Charging Problem (SCP) of scheduling power chargers so that more energy can be received while no location in the field has electromagnetic radiation (EMR) exceeding a given threshold Rt. We prove that SCP is NP-hard and propose a solution which provably outperforms the optimal solution to SCP with a relaxed EMR threshold (1 - ε)Rt. Testbed results based on 8 Powercast TX91501 chargers validate our results. Extensive simulation results show that the gap between our solution and the optimal one is only 6.7% when ε = 0.1, while a naive greedy algorithm is 34.6% below our solution.

Nowadays, RFID systems have been widely deployed for applications such as supply chain management and inventory control. One of their most essential operations is to swiftly identify individual tags to distinguish their associated objects. Most existing solutions identify tags sequentially in the temporal dimension to avoid signal collisions, whose performance degrades significantly as the system scale increases. In this paper, we propose aParallel Identification Protocol(PIP) for RFID systems, which achieves the parallel identification paradigm and is compatible with current RFID devices. Uniquely, PIP encodes the tag ID into a specially designed pattern and thus greatly facilitates the reader to correctly and effectively recover them from collisions. Furthermore, we analytically investigate its performance and provide guidance on determining its optimal settings. Extensive simulations show that PIP reduces the identification delay by about 25%-50% when compared with the standard method in EPC C1G2 and the state-of-the-art solutions.

Wireless rechargeable sensor network is a promising platform for long-term applications such as inventory management, supply chain monitoring and so on. For these applications, sensor localization is one of the most fundamental challenges. Different from traditional sensor node, wireless rechargeable sensor has to be charged above a voltage level by the wireless charger in order to support its sensing, computation and communication operations. In this work, we consider the scenario where a mobile charger stops at different positions to charge sensors, and propose a novel localization design that utilizes the unique Time of Charge (TOC) sequences among wireless rechargeable sensors. Specifically, we introduce two efficient region dividing methods, Inter-node Division and Inter-area Division, to exploit TOC differences from both temporal and spatial dimensions to localize individual sensor nodes. To further optimize the system performance, we introduce both an optimal charger stop planning algorithm for single sensor case and a suboptimal charger stop planning algorithm for the generic multisensor scenario with a provable performance bound. We have extensively evaluated our design by both testbed experiments and large-scale simulations. The experiment and simulation results show that by as less as 5 stops, our design can achieve sub-meter accuracy and the performance is robust under various system conditions.

Key-value (k-v) storage has been used as a crucial component for many network applications, such as social networks, online retailing, and cloud computing. Such storage usually provides support for operations on key-value pairs, and can be stored in memory to speed up responses to queries. So far, existing methods have been deterministic: they will faithfully return previously inserted key-value pairs. Providing such accuracy, however, comes at the cost of memory and CPU time. In contrast, in this paper, we present an approximate k-v storage that is more compact than existing methods. The tradeoff is that it may, theoretically, return a null value for a valid key with a low probability, or return a valid value for a key that was never inserted. Its design is based on the probabilistic data structure called the “Bloom Filter”, which was originally developed to test element membership in sets. In this paper, we extend the bloom filter concept to support key-value operations, and demonstrate that it still retains the compact nature of the original bloom filter. We call the resulting design as the kBF (key-value bloom filter), and systematically analyze its performance advantages and design tradeoffs. Finally, we apply the kBF to a practical problem of implementing a state machine in network intrusion detection to demonstrate how the kBF can be used as a building block for more complicated software infrastructures.

In wireless sensor networks (WSNs), existing work on flooding mainly focuses on single-packet problem, while work in sequential multi-packet problem is surprisingly little. This paper proposes OppCode, a new opportunistic network-coding based flooding architecture for multi-packet dissemination in WSNs, where both unreliable and correlated links commonly exist. Instead of flooding a single packet each time, each node encodes multiple native packets chosen from a specific fixed-size page to an encoded packet, and then rebroadcasts it further. The key idea consists of two parts: one is opportunistically coding decision, in which each node grasps every possible coding opportunity greedily to conduct an encode-and-forward operation in order to maximize its total (or aggregate) coding gain of all neighbors based on the probabilistic estimations of packets each neighbor already has (i.e., coverage), the other is paged collective acknowledgements (ACKs), in which one rebroadcast that arrives at a receiver acts as not only an implicit ACK of successful disseminations of all packets in the entire page for the sender, but also probabilistic ACK to update page-scale per-packet coverage estimations for its neighbors in a batch. We evaluate our design using extensive simulations and on a 20-node WSNs testbed, and show that OppCode largely increases performance of multi-packet flooding compared with state-of-the-art solutions, especially when links are highly unreliable and correlated with each other. The gains vary from a few percent to several folds depending on the network density, link conditions, coverage threshold and page size.

Expanding our knowledge about human mobility is essential for building efficient wireless protocols and mobile applications. Previous human mobility studies have typically been built upon empirical single-source data (e.g., cellphone or transit data), which inevitably introduces a bias against residents not contributing this type of data, e.g., call detail records cannot be obtained from the residents without cellphone activities, and transit data cannot cover the residents who walk or ride private vehicles. To address this issue, we propose and implement a novel architecture mPat to explore human mobility using multi-source data. A reference implementation of mPat was developed at an unprecedented scale upon the urban infrastructures of Shenzhen, China. The novelty and uniqueness of mPat lie in its three layers: (i) a data feed layer consisting of real-time data feeds from 24 thousand vehicles, 16 million smart cards and 10 million cellphones; (ii) a mobility abstraction layer exploring the correlation and divergence among the multi-source data to analyze and infer human mobility; and (iii) an application layer to improve urban efficiency based on the human mobility findings of the study. The evaluation shows that mPat achieves a 75% inference accuracy, and that its real-world application reduces passenger travel time by 36%.

No abstract available.

Integrated with low-power micro-controllers and sensors, RFID-based wireless rechargeable sensor node is a very promising platform for applications such as inventory management, supply chain monitoring etc. Among other major research challenges, one of the most essential problems in such wireless rechargeable sensor networks is how to minimize the communication delay among RFID readers and RFID-based rechargeable nodes. While the existing works have mostly focused on the collision avoidance among RFID-based nodes, in this work we study an orthogonal approach which focuses on how to optimally plan the movement of the reader so as to minimize the communication delay in the network. To solve this problem, we introduce both an optimal solution for the linear reader movement pattern and an approximation solution for the generic two-dimensional reader move pattern with a provable approximation ratio. In addition, we also provide a solution for guaranteeing the quality of communication while minimizing the communication delay. We verify our observations through testbed experiments and extensively evaluate our design by both emulations and large-scale simulations. The results show our design can effectively reduce communication delay in wireless rechargeable sensor networks when compared with baseline solutions.

Flooding service has been investigated extensively in wireless networks to efficiently disseminate network-wide commands, configurations, and code binaries. However, little work has been done on low-duty-cycle wireless sensor networks in which nodes stay asleep most of the time and wake up asynchronously. In this type of network, a broadcasting packet is rarely received by multiple nodes simultaneously, a unique constraining feature that makes existing solutions unsuitable. In this paper, we introduce Opportunistic Flooding, a novel design tailored for low-duty-cycle networks with unreliable wireless links and predetermined working schedules. Starting with an energy-optimal tree structure, probabilistic forwarding decisions are made at each sender based on the delay distribution of next-hop receivers. Only opportunistically early packets are forwarded via links outside the tree to reduce the flooding delay and redundancy in transmission. We further propose a forwarder selection method to alleviate the hidden terminal problem and a link-quality-based backoff method to resolve simultaneous forwarding operations. We show by extensive simulations and test-bed implementations that Opportunistic Flooding is close to the optimal performance achievable by oracle flooding designs. Compared with Improved Traditional Flooding, our design achieves significantly shorter flooding delay while consuming only 20-60% of the transmission energy.

With advances in energy-harvesting techniques, it is now feasible to build sustainable sensor networks to support long-term applications. Unlike battery-powered sensor networks, the objective of sustainable sensor networks is to effectively utilize a continuous stream of ambient energy. Instead of pushing the limits of energy conservation, we aim to design energy-synchronized schemes that keep energy supplies and demands in balance. Specifically, this work presents Energy-Synchronized Communication (ESC) as a transparent middleware between the network layer and MAC layer that controls the amount and timing of RF activity at receiving nodes. In this work, we first derive a delay model for cross-traffic at individual nodes, which reveals an interesting stair effect . This effect allows us to design a localized energy synchronization control with ℴ( d 3 ) time complexity that shuffles or adjusts the working schedule of a node to optimize cross-traffic delays in the presence of changing duty cycle budgets, where d is the node degree in the network. Under different rates of energy fluctuations, shuffle-based and adjustment-based methods have different influences on logical connectivity and cross-traffic delay , due to the inconsistent views of working schedules among neighboring nodes before schedule updates. We study the trade-off between them and propose methods for updating working schedules efficiently. To evaluate our work, ESC is implemented on MicaZ nodes with two state-of-the-art routing protocols. Both testbed experiment and large-scale simulation results show significant performance improvements over randomized synchronization controls.

Wireless Sensor Networks (WSN) promise researchers a powerful instrument for observing sizable phenomena with fine granularity over long periods. Since the accuracy of data is important to the whole system's performance, detecting nodes with faulty readings is an essential issue in network management. As a complementary solution to detecting nodes with functional faults, this article, proposes FIND, a novel method to detect nodes with data faults that neither assumes a particular sensing model nor requires costly event injections. After the nodes in a network detect a natural event, FIND ranks the nodes based on their sensing readings as well as their physical distances from the event. FIND works for systems where the measured signal attenuates with distance. A node is considered faulty if there is a significant mismatch between the sensor data rank and the distance rank. Theoretically, we show that average ranking difference is a provable indicator of possible data faults. FIND is extensively evaluated in simulations and two test bed experiments with up to 25 MicaZ nodes. Evaluation shows that FIND has a less than 5% miss detection rate and false alarm rate in most noisy environments.

As a key approach to achieve energy efficiency in sensor networks, sensing coverage has been studied extensively in the literature. Researchers have designed many coverage protocols to provide various kinds of service guarantees on the network lifetime, coverage ratio and detection delay. While these protocols are effective, they are not flexible enough to meet multiple design goals simultaneously. In this paper, we propose a unified sensing coverage architecture for duty cycled wireless sensor networks, called uSense, which features three novel ideas: Asymmetric Architecture, Generic Switching and Global Scheduling. We propose asymmetric architecture based on the conceptual separation of switching from scheduling. Switching is efficiently supported in sensor nodes, while scheduling is done in a separated computational entity, where multiple scheduling algorithms are supported. As an instance, we propose a two-level global coverage algorithm, called uScan. At the first level, coverage is scheduled to activate different portions of an area. We propose an optimal scheduling algorithm to minimize area breach. At the second level, sets of nodes are selected to cover active portions. Importantly, we show the feasibility to obtain optimal set-cover results in linear time if the layout of areas satisfies certain conditions. Through extensive testbed and simulation evaluations, we demonstrate that uSense is a promising architecture to support flexible and efficient coverage in sensor networks.

Geocast in vehicular networks aims to deliver a message to a target geographical region, which is useful for many applications such as geographic advertising. This is a highly challenging task in vehicular network environments due to the rare encounter opportunities and uncertainty caused by vehicular mobility. As more vehicles are equipped with on-board navigation systems, vehicle trajectories are ready for exploitation. We observe that a vehicle has a higher capability of delivering a message to the target region if its own future trajectory or trajectories of those vehicles to be encountered overlap the target region. Motivated by this observation, we develop a message forwarding metric, called coverage capability, to characterize the capability of a vehicle to successfully geocast the message. When calculating the coverage capability, we are facing the major challenge raised by the absence of accurate vehicle arrival time. Through an empirical study using real vehicular GPS traces of 2,600 taxis, we verify that the travel time of a vehicle, which is modeled as a random variable, follows the Gamma distribution. The travel time modeling helps us to make accurate predictions for inter-vehicle encounters. We perform extensive trace-driven simulations and the results show that our approach achieves 37.4 percent higher delivery ratio and 43.1 percent lower transmission overhead comparing with GPSR which is a representative geographic routing protocol.

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.

Due to the limited power constraint in sensors, dynamic scheduling with data quality management is strongly preferred in the practical deployment of long-term wireless sensor network applications. We could reduce energy consumption by turning off (i.e., duty cycling) sensor, however, at the cost of low-sensing fidelity due to sensing gaps introduced. Typical techniques treat data quality management as an isolated process for individual nodes. And existing techniques have investigated how to collaboratively reduce the sensing gap in space and time domain; however, none of them provides a rigorous approach to confine sensing error is within desirable bound when seeking to optimize the tradeoff between energy consumption and accuracy of predictions. In this paper, we propose and evaluate a scheduling algorithm based on error inference between collaborative sensor pairs, called CIES. Within a node, we use a sensing probability bound to control tolerable sensing error. Within a neighborhood, nodes can trigger additional sensing activities of other nodes when inferred sensing error has aggregately exceeded the tolerance. The main objective of this work is to develop a generic scheduling mechanism for collaborative sensors to achieve the error-bounded scheduling control in monitoring applications. We conducted simulations to investigate system performance using historical soil temperature data in Wisconsin-Minnesota area. The simulation results demonstrate that the system error is confined within the specified error tolerance bounds and that a maximum of 60 percent of the energy savings can be achieved, when the CIES is compared to several fixed probability sensing schemes such as eSense. And further simulation results show the CIES scheme can achieve an improved performance when comparing the metric of a prediction error with baseline schemes. We further validated the simulation and algorithms by constructing a lab test bench to emulate actual environment monitoring applications. The results show that our approach is effective and efficient in tracking the dramatic temperature shift in dynamic environments.

Carpooling taxicab services hold the promise of providing additional transportation supply, especially in extreme weather or rush hour when regular taxicab services are insufficient. Although many recommendation systems about regular taxicab services have been proposed recently, little research, if any, has been done to assist passengers to find a successful taxicab ride with carpooling. In this paper, we present the first systematic work to design a unified recommendation system for both regular and carpooling services, called CallCab, based on a data driven approach. In response to a passenger's request, CallCab aims to recommend either (i) a vacant taxicab for a regular service with no detour, or (ii) an occupied taxicab heading to the similar direction for a carpooling service with less detour, yet without assuming any knowledge of destinations of passengers already on occupied taxicabs. To analyze these unknown destinations of occupied taxicabs, CallCab generates and refines taxicab trip distributions based on GPS datasets and context information collected in the existing taxicab infrastructure. To improve CallCab's efficiency to process such a big dataset, we augment the efficient MapReduce model with a Measure phase tailored for our application. We evaluate CallCab with a real world dataset of 14,000 taxicabs, and results show that compared to ground truth, CallCab can reduce 64% of the total mileage to deliver all passengers and 63% of passenger's waiting time.

Fault-tolerance is essential in extreme-scale data processing systems. Pro-active fault-tolerance scheme (such as the speculative execution in MapReduce framework), can dramatically improve the response time of job executions when the failure becomes norm rather than an exception. Efficient pro-active fault-tolerance schemes require precise knowledge on the task executions, which has been an open challenges for decades. To well address the issue, in this paper we design and implement RiskI, a profile-based prediction algorithm in conjunction with a risk-aware task assignment algorithm to accelerate task executions, taking the uncertainty nature of tasks into account. Our design demonstrates that the nature uncertain not only brings great challenges but also new opportunities. With a careful design, we can benefit from such uncertainties. We implement the idea in Hadoop 0.21.0 systems and the experimental results show that compared with the traditional LATE algorithm, the response time can be improved by 46% with the same system throughput.

Reliable flooding in wireless sensor networks (WSNs) is desirable for a broad range of applications and network operations, and has been extensively investigated. However, relatively little work has been done for reliable flooding in lowduty-cycle WSNs with unreliable wireless links. It is a challenging problem to efficiently ensure 100% flooding coverage considering the combined effects of low-duty-cycle operation and unreliable wireless transmission. In this work, we propose a novel dynamic switching-based reliable flooding (DSRF) framework, which is designed as an enhancement layer to provide efficient and reliable delivery for a variety of existing flooding tree structures in lowduty-cycle WSNs. The key novelty of DSRF lies in the dynamic switching decision making when encountering a transmission failure, where a flooding tree structure is dynamically adjusted based on the packet reception results for energy saving and delay reduction. DSRF is distinctive from existing works in that it explores both poor links and good links on demand. Through comprehensive performance comparisons, we demonstrate that, compared with the flooding protocol without DSRF enhancement, DSRF effectively reduces the flooding delay and the total number of packet transmission by 12% 25% and 10% 15%, respectively. Remarkably, the achieved performance is close to the theoretical lower bound.

As a pioneering experimental platform of wireless rechargeable sensor networks, the Wireless Identification and Sensing Platform (WISP) is an open-source platform that integrates sensing and computation capabilities to the traditional RFID tags. Different from traditional tags, a RFID-based wireless rechargeable sensor node needs to charge its onboard energy storage above a threshold in order to power its sensing, computation and communication components. Consequently, such charging delay imposes a unique design challenge for deploying wireless rechargeable sensor networks. In this paper, we tackle this problem by planning the optimal movement strategy of the RFID reader, such that the time to charge all nodes in the network above their energy threshold is minimized. We first propose an optimal solution using the linear programming method. To further reduce the computational complexity, we then introduce a heuristic solution with a provable approximation ratio of (1 + θ)/(1 - ε) by discretizing the charging power on a two-dimensional space. Through extensive evaluations, we demonstrate that our design outperforms the set-cover-based design by an average of 24.7% while the computational complexity is O((N/ε)2).

Low-duty-cycle radio operations have been proposed for wireless networks facing severe energy constraints. Despite energy savings, duty-cycling the radio creates transient-available wireless links, making communication rendezvous a challenging task under the practical issue of clock drift. To overcome limitations of prior work, this paper presents PSR, a practical design for synchronous rendezvous in low-duty-cycle wireless networks. The key idea behind PSR is to extract timing information naturally embedded in the pattern of radio duty-cycling, so that normal traffic in the network can be utilized as a “free” input for drift detection, which helps reduce (or even eliminate) the overhead of traditional time-stamp exchange with dedicated packets or bits. To prevent an overuse of such free information, leading to energy waste, an energy-driven adaptive mechanism is developed for clock calibration to balance between energy efficiency and rendezvous accuracy. PSR is evaluated with both test-bed experiments and extensive simulations, by augmenting and comparing with four different MAC protocols. Results show that PSR is practical and effective under different levels of traffic load, and can be fused with those MAC protocols to improve their energy efficiency without major change of the original designs.

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.

Radio Signal Strength (RSS) based ranging is attractive by the low cost and easy deployment. In real environments, its accuracy is severely affected by the multipath effect and the external radio interference. The well-known fingerprint approaches can deal with the issues but introduce too much overhead in dynamic environments. In this paper, we attempt to address the issue along a completely different direction. We propose a new ranging framework called Fredi that exploits the frequency diversity to overcome the multi-path effect solely based on RSS measurements. We design a Discrete Fourier Transformation based algorithm and prove that it has the optimal solution under ideal cases. We further revise the algorithm to be robust to the measurement noises in practice. We implement Fredi on top of the USRP-2 platform and conduct extensive real environments in indoor environments. Experimental results show the superiority performance compared with the traditional methods.

Energy harvesting is becoming an important enabling technology for sustainable sensor networks. However, the uncertainty and non-uniformity of harvestable energy and the unbalanced workload will often result in the node failures of solar-powered sensor networks. In order to decrease the energy depletion and improve the performance, we introduce an ultra-capacitor-based energy sharing system and design an energy sharing scheme based on it to optimize the network throughput. Different from most of the existing approaches which are focusing on energy management on single node, our design considers energy as a shared resource which makes it be used more efficiently, especially in the case with limited energy. Theoretical analysis and simulation results indicate the energy sharing system as well as the energy sharing schemes can effectively improve the network performance.

Sensor node localization is a challenging task because of severe constraints on cost, energy, and effective range of sensor devices. To overcome limitations in existing solutions, this paper formally describes, designs, implements, and evaluates a Convex Optimization-based Method for Event-Driven Localization, i.e., COMEDL, in large-scale wireless sensor networks. The key idea behind COMEDL is to estimate the two-dimensional location coordinates of sensor nodes by processing multiple one-dimensional node sequences that can be easily obtained via loosely guided localization event distributions. The proposed design is evaluated through theoretical analysis, extensive simulations, and physical experiments (an indoor test-bed with 44 MICAz sensor nodes). Evaluation results demonstrate that COMEDL can effectively localize nodes with improved accuracy and flexibility.

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.

Large-scale battery packs with hundreds/thousands of battery cells are commonly adopted in many emerging cyber-physical systems such as electric vehicles and smart micro-grids. For many applications, the load requirements on the battery systems are dynamic and could significantly change over time. How to resolve the discrepancies between the output power supplied by the battery system and the input power required by the loads is key to the development of large-scale battery systems. Traditionally, voltage regulators are often adopted to convert the voltage outputs to match loads' required input power. Unfortunately, the efficiency of utilizing such voltage regulators degrades significantly when the difference between supplied and required voltages becomes large or the load becomes light. In this paper, we propose to address this problem via an adaptive reconfiguration framework for the battery system. By abstracting the battery system into a graph representation, we develop two adaptive reconfiguration algorithms to identify the desired system configurations dynamically in accordance with real-time load requirements. We extensively evaluate our design with empirical experiments on a prototype battery system, electric vehicle driving trace-based emulation, and battery discharge trace-based simulations. The evaluation results demonstrate that, depending on the system states, our proposed adaptive reconfiguration algorithms are able to achieve 1× to 5× performance improvement with regard to the system operation time.

Carpooling has long held the promise of reducing gas consumption by decreasing mileage to deliver co-riders. Although ad hoc carpools already exist in the real world through private arrangements, little research on the topic has been done. In this paper, we present the first systematic work to design, implement, and evaluate a carpool service, called coRide, in a large-scale taxicab network intended to reduce total mileage for less gas consumption. Our coRide system consists of three components, a dispatching cloud server, passenger clients, and an onboard customized device, called TaxiBox. In the coRide design, in response to the delivery requests of passengers, dispatching cloud servers calculate cost-efficient carpool routes for taxicab drivers and thus lower fares for the individual passengers.

Although existing flooding protocols can provide efficient and reliable communication in wireless sensor networks on some level, further performance improvement has been hampered by the assumption of link independence, which requires costly acknowledgments (ACKs) from every receiver. In this paper, we present collective flooding (CF), which exploits the link correlation to achieve flooding reliability using the concept of collective ACKs. CF requires only 1-hop information at each node, making the design highly distributed and scalable with low complexity. We evaluate CF extensively in real-world settings, using three different types of testbeds: a single-hop network with 20 MICAz nodes, a multihop network with 37 nodes, and a linear outdoor network with 48 nodes along a 326-m-long bridge. System evaluation and extensive simulation show that CF achieves the same reliability as state-of-the-art solutions while reducing the total number of packet transmission and the dissemination delay by 30%-50% and 35%-50%, respectively.

In wireless sensor networks (WSNs), trap coverage has recently been proposed to trade off between the availability of sensor nodes and sensing performance. It offers an efficient framework to tackle the challenge of limited resources in large-scale sensor networks. Currently, existing works only studied the theoretical foundation of how to decide the deployment density of sensors to ensure the desired degree of trap coverage. However, practical issues, such as how to efficiently schedule sensor node to guarantee trap coverage under an arbitrary deployment, are still left untouched. In this article, we formally formulate the Minimum Weight Trap Cover Problem and prove it is an NP-hard problem. To solve the problem, we introduce a bounded approximation algorithm, called Trap Cover Optimization (TCO) to schedule the activation of sensors while satisfying specified trap coverage requirement. We design Localized Trap Coverage Protocol as the localized implementation of TCO. The performance of Minimum Weight Trap Coverage we find is proved to be at most O (ρ) times of the optimal solution, where ρ is the density of sensor nodes in the region. To evaluate our design, we perform extensive simulations to demonstrate the effectiveness of our proposed algorithm and show that our algorithm achieves at least 14% better energy efficiency than the state-of-the-art solution.

Well-balanced workload among wireless access points (APs) in a wireless local-area network (WLAN) can improve the user experience for accessing the Internet. Most load balancing solutions in WLANs focuses on the optimization of AP operations, assuming that the arrivals and departures of users are independent. However, through the analysis of AP usage based on a real WLAN trace of one-month collected at the Shanghai Jiao Tong University (SJTU), we find that such an assumption does not hold. In fact, due to users' social activities which is particularly time for enterprise environments, they tend to arrive or leave in unison, which would disruptively affect the load balance among APs. In this paper, we propose a novel AP allocation scheme to tackle the load balancing problem in WLANs, taking into account the social relationships of users. In this scheme, users with intense social relationships are assigned to different APs so that jointly departure of those users would have minor impact on the load balance of APs. Given that the problem of allocating an AP for each user so that the average of the sums of social relation intensity between any pair of users in each AP is NP-complete, we propose an online greedy algorithm. Extensive trace-driven simulations demonstrate the efficacy of our scheme. Comparing to the state-of-the-art method, we can achieve about 64.7 percent balancing performance gain on average during peak hours in workdays.

In many mobile sensing applications devices need to discover new neighbors and maintain the rendezvous with known neighbors continuously. Due to the limited energy supply, these devices have to cycle their radios to conserve energy, making neighbor discovery and rendezvous maintenance even more challenging. To date, the main mechanism for device discover and rendezvous maintenance in existing solutions is pair wise, direct one-hop communication. We argue that such pair wise direct communication is sufficient but not necessary: there exist unnecessary active slots that can be eliminated, without affecting discovery and rendezvous. In this work, we propose a novel concept of extended quorum system, which leverages indirect discovery to further conserve energy. Specifically, we use quorum graph to capture all possible information flow paths where knowledge about known-neighbors can propagate among devices. By eliminating redundant paths, we can reduce the number of active slots significantly. Since a quorum graph can characterize arbitrary active schedules of mobile devices, our work can be broadly used to improve many existing quorum based discovery and rendezvous solutions. The simulation and test bed experimental results show that our solution can reduce as much as 55% energy consumption with a maximal 5% increase in latency for existing solutions.

By exploiting reception diversity of wireless network links, researchers have shown that opportunistic routing can improve network performance significantly over traditional routing schemes. However, recently empirical studies indicate that we are too optimistic, i.e. diversity gain can be overestimated if we continue to assume that packet receptions of wireless links are independent events. For the first time, this paper formally analyzes the opportunistic routing gain under the presence of link correlation considering the loss of DATA and ACK packets. Based on the model, we introduce a new link-correlation-aware opportunistic routing scheme, which improves the performance by exploiting the diverse uncorrelated forwarding links. Our design is evaluated using simulation where we show (i) link correlation leads to less diversity gain, (ii) and with our link-correlation-aware design; improvement can be gained. We also provide a unique model to generate strings of randomly correlated receptions.

Data collection is one of the major traffic pattern in wireless sensor networks, which requires regular source nodes to send data packets to a common sink node with limited end-to-end delay. However, the sleep latency brought by duty cycling mode results in significant rise on the delivery latency. In order to reduce unnecessary forwarding interruption, the state-of-the-art has proposed pipeline scheduling technique by allocating sequential wakeup time slots along the forwarding path. We experimentally show that previously proposed pipeline is fragile and ineffective in reality when wireless communication links are unreliable. To overcome such challenges and improve the performance on the delivery latency, we propose Robust Multi-pipeline Scheduling (RMS) algorithm to coordinate multiple parallel pipelines and switch the packet timely among different pipelines if failure happens in former attempts of transmissions. RMS combines the pipeline features with the advantages brought by multi-parents forwarding. Large-scale simulations and testbed implementations verify that the end-to-end delivery latency can be reduced by 40% through exploiting multi-pipeline scheduled forwarding path with tolerable energy overhead.

Exploiting the increasing ubiquitous deployment of sensor networks, the paper presents a system called WiBee that utilizes ZigBee sensors to build real-time WiFi radio maps. The design of WiBee is motivated by the observation that a ZigBee radio can sense WiFi frame transmissions although it cannot decode WiFi frames. A sensor passively listens on the wireless channel and estimates the RSS of a WiFi AP at its location. The design of WiBee faces three unique challenges. First, multiple APs may transmit frames concurrently and frame collisions may happen. Second, because of severe resource constraints, a sensor cannot sample the channel at arbitrarily high frequency and hence some frame transmissions may not be sampled. Third, sensor nodes are usually not time synchronized and the on-board clock is inaccurate. To address these challenges, we propose a novel gateway-assisted approach to estimating WiFi RSS values at ZigBee sensors. A light-weight algorithm is designed for identifying the RSS values corresponding to a given AP. It searches the sequence of ZigBee RSS samples for an AP signature sequence. An optimization technique is proposed to address issues of clock drift and time asynchronization. Our extensive experiments on a testbed show that WiBee can achieve low estimation error, short delay and small computation overhead.

In taxicab industry, a long standing challenge is how to reduce taxicab's mileage spent without a fare, i.e., cruising mile. The current solution for this challenge usually requires the participation of the passengers. To solve the issue without the passengers involved, in this paper, we propose a cruising system, pCruise, for taxicab drivers to maximize theirs profits by finding the optimal route to pick up a passenger, thus reducing the cruising mile. In pCruise, base on collected GPS records about other near taxicabs, a taxicab characterizes its cruising process with a cruising graph. When a taxicab becomes vacant and tries to find a passenger, cruising graph will provide the shortest cruising route with at least one expected available passengers for this taxicab. With the shortest cruising routes, taxicabs will significantly reduce theirs cruising miles. We evaluate pCruise based on a 7 days 10 GB real world GPS dataset from a city with more than 15,000 taxicabs. The evaluation results show that pCruise can assist taxicab drivers to reduce cruising miles by 41% on average.

Wireless Sensor Networks have been used in many mobile applications such as wildlife tracking and participatory urban sensing. Because of the combination of high mobility and low-duty-cycle operations, it is a challenging issue to reduce discovery delay among mobile nodes, so that mobile nodes can establish connection quickly once they are within each other's vicinity. Existing discovery designs are essentially pair-wise based, in which discovery is passively achieved when two nodes are pre-scheduled to wake-up at the same time. In contrast, for the first time, this work reduces discovery delay significantly by proactively referring wake-up schedules among a group of nodes. Because proactive references incur additional overhead, we introduce a novel selective reference mechanism based on spatiotemporal properties of neighborhood and the mobility of the nodes. Our quantitative analysis indicates that the discovery delay of our group-based mechanism is significantly smaller than that of the pair-wise one. Our testbed experiments using 40 sensor nodes confirm our theoretical analysis, showing one order of magnitude reduction in discovery delay compared with traditional pair-wise methods with only 0.5%~8.8% increase in energy consumption.

Reliable flooding in wireless sensor networks (WSNs) is desirable for a broad range of applications and network operations. However, it is a challenging problem to ensure 100% flooding coverage efficiently considering the combined effects of low-duty-cycle operation and unreliable wireless transmission. In this work, we propose a novel dynamic switching-based reliable flooding (DSRF) framework, which is designed as an enhancement layer to provide efficient and reliable flooding over a variety of existing flooding tree structures in low-duty-cycle WSNs. Through comprehensive simulations, we demonstrate that DSRF can effectively improve both flooding energy efficiency and latency.

In this paper, we investigate the mobile charging in rechargeable sensor networks. By utilizing the historic charging information, the mobile charger can prefetch the charging requests from sensor nodes before they are sent out, and thus both the charging latency of sensor nodes and the travel distance of mobile charger can be reduced. Furthermore, by controlling the amount of energy to charge to nodes, the energy synchronization of sensor nodes can be achieved, which proactively adjust the arrival order of charging requests at the mobile charger. Combining these ideas, a novel charging scheme with verified efficiency is proposed.

In this paper, we propose Social-Loc, which uniquely utilizes social interactions in addition to common on-board sensors such as accelerometer and gyroscope on modern smartphones, to localize indoor mobile users. Specifically, Social-Loc takes the potential locations for individual users estimated by a novel particle filter tailored for indoor localization as input, and exploits both social encounter and non-encounter events to further improve the localization accuracy. We have implemented Social-Loc on the Android platform and extensively evaluated its performance. The simulation results demonstrate that Social-Loc improves the accuracy of the particle-filter-only scheme by as much as 560% on average and is able to achieve accuracy of few meters without any external ranging device or system training.

In wireless mobile networks, energy can be saved by using dynamic transmission scheduling with pre-knowledge about channel conditions. Such pre-knowledge can be obtained via profiling as proposed by several existing systems which assumed that the existence of spatial link correlation makes the measured channel status at one location reusable over a long period of time. Our empirical data, however, tells a different story: spatial link correlation only maintains well within a short duration (from seconds to tens of seconds) while decreases significantly afterwards, a phenomena we call ephemeral link correlation. By leveraging this observation, we design and implement a real-time transmission scheduling system, named PreSeer, on the railway platform for cargo transportation, where the transmission of a sink (to cellular towers) can be scheduled intelligently by utilizing future channel status measured by sinks located in front of it on the same train. We have implemented and evaluated the PreSeer system on the collected data extensively over 7,000-kilometer railway routes during a period of one and half years. Results reveal that PreSeer can help save as much as 40% energy, comparing with three base-line algorithms. More importantly, lessons learned from this major effort provide useful guidelines for transmission scheduling in highly-dynamic mobile environments, where (i) channel measurements cannot be perfectly aligned due to varying vehicle velocities, and (ii) the accuracy of channel measurements is subject to hardware discrepancy as well as environment irregularity.

As a supporting primitive of many mobile device applications, neighbor discovery identifies nearby devices so that they can exchange information and collaborate in a peer-to-peer manner. To date, discovery schemes trade a long latency for energy efficiency and require a collaborative duty cycle pattern, and thus they are not suitable for interactive mobile applications where a user is unable to configure others' devices. In this paper, we propose Acc, which serves as an on-demand generic discovery accelerating middleware for many existing neighbor discovery schemes. Acc leverages the discovery capabilities of neighbor devices, supporting both direct and indirect neighbor discoveries. Our evaluations show that Acc-assisted discovery schemes reduce latency by a maximum of 51.8%, compared with the schemes consuming the same amount of energy. We further present and evaluate a Crowd-Alert application where Acc can be employed by taxi drivers to accelerate selection of a direction with fewer competing taxis and more potential passengers, based on a 10 GB dataset of more than 15,000 taxis in a metropolitan area.

Wireless Sensor Networks have been proposed for use in many location-dependent applications. Most of these need to identify the locations of sensor nodes, a challenging task because of severe constraints on cost, energy and effective range of sensor devices. To overcome limitations in existing solutions, we present a Multi-Sequence Positioning (MSP) method for large-scale stationary sensor node localization in outdoor environments. The novel idea behind MSP is to reconstruct and estimate two-dimensional location information for each sensor node by processing multiple one-dimensional node sequences, easily obtained through loosely guided event distribution. Starting from a basic MSP design, we propose four optimizations that work together to increase localization accuracy. We address several interesting issues such as incomplete (partial) node sequences and sequence flip, found in the Mirage test-bed we built. We have evaluated the MSP system through theoretical analysis, extensive simulation as well as two physical systems (an indoor version with 46 MICAz motes and an outdoor version with 20 MICAz motes). Evaluation demonstrates that MSP can achieve an accuracy within one foot, requiring neither additional costly hardware on sensor nodes nor precise event distribution. In fact, it provides a nice tradeoff between physical cost (anchors) and soft cost (events) while maintaining localization accuracy.

Event-driven localization has been proposed as a low-cost solution for node positioning in wireless sensor networks. In order to eliminate the costly requirement for accurate event control in existing methods, we present a practical design using uncontrolled events. The main idea is to estimate both event generation parameters and the location of sensor nodes simultaneously, by processing node sequences that can be easily obtained from event detections. Besides the basic design, we proposed two enhancements to further extract information embedded in node orderings for two scenarios: (i) node density is high; and (ii) abundant events are available. To demonstrate the generality of our design, both straight-line scan and circular wave propagation events are addressed in the article, and we evaluated the design with extensive simulation as well as a testbed implementation with 41 MICAz motes. Results show that with only randomly generated events, our design can effectively localize nodes with great flexibility while adding little extra cost at the resource constrained sensor node side. In addition, localization via uncontrolled events provides a potential option of achieving node positioning through long-term ambient events.

This paper proposes Trajectory-based Statistical Forwarding (TSF) scheme, tailored for the multihop data delivery from infrastructure nodes (e.g., Internet access points) to moving vehicles in vehicular ad hoc networks. To our knowledge, this paper presents the first attempt to investigate how to effectively utilize the packet destination vehicle's trajectory for such an infrastructure-to-vehicle data delivery. This data delivery is performed through the computation of a target point based on the destination vehicle's trajectory that is an optimal rendezvous point of the packet and the destination vehicle. TSF forwards packets over multihop to a selected target point where the vehicle is expected to pass by. Such a target point is selected optimally to minimize the packet delivery delay while satisfying the required packet delivery probability. The optimality is achieved analytically by utilizing the packet's delivery delay distribution and the destination vehicle's travel delay distribution. Through theoretical analysis and extensive simulation, it is shown that our design provides an efficient data forwarding under a variety of vehicular traffic conditions.

Energy is the most precious resource in sensor networks. The ability to move energy around makes it feasible to build distributed energy storage systems that can robustly extend the lifetime of networked sensor systems. eShare supports the concept of energy sharing among multiple embedded sensor devices by providing designs for energy routers (i.e., energy storage and routing devices) and related energy access and network protocols. In a nutshell, energy routers exchange energy sharing control information using their data network while sharing energy freely among connected embedded sensor devices using their energy network. To improve sharing efficiency subject to energy leakage, we develop an effective energy charging and discharging mechanism using an array of ultra-capacitors as the main component of an energy router. We extensively evaluate our system under seven real-world settings. Results indicate our charging and discharging control can effectively minimize the energy leaked away. Moreover, the energy sharing protocol can quantitatively share 113J energy with 96.82% accuracy in less than 2 seconds.

In this paper, we consider using actors to maintain the quality of sensing in the wireless sensor networks. Due to factors such as battery drainage or physical malfunctions, the number of available sensors normally decreases over time after initial deployment, resulting in performance degradation. To maintain the quality of sensing in the network, actors can be used to allocate spare sensors to sensor-deficient regions (sensor allocation) or to relocate sensors from sensor-abundant regions to sensor-deficient regions (sensor relocation). We first focus on the sensor allocation problem. We introduce a baseline centralized greedy algorithm (GA) for sensor allocation, where global sensor information is communicated to obtain the optimal solution. As GA is only efficient for small networks, we proceed to design a distributed patrolling algorithm for achieving global optimization (DPAG) by using only local information. We then extend our work to the application scenario of sensor relocation by proposing a modified GA and DPAG (M-GA and M-DPAG), respectively. Extensive simulation results are provided to demonstrate the performance of the proposed algorithms.

Localization of wireless sensor nodes has long been regarded as a problem that is difficult to solve, especially when considering characteristics of real-world environments. This paper formally describes, designs, implements, and evaluates a novel localization system called Spotlight. The system uses spatiotemporal properties of well-controlled events in the network, light in this case, to obtain locations of sensor nodes. Performance of the system is evaluated through deployments of Mica2 and XSM motes in an outdoor environment, where 20 cm localization error is achieved. A sensor network consisting of any number of nodes deployed in a 2,500 m2area can be localized in under 10 minutes. Submeter localization error in an outdoor environment is made possible without equipping the wireless sensor nodes with specialized ranging hardware.

As an essential requirement for surveillance systems, target tracking has been studied extensively. Most of the tracking schemes are based on trilateration, which requires each point in the monitoring area to be covered by at least three anchors. However, due to the inadequate deployment of costly anchors and environment constraints, the target might not always be detected by three or more anchors simultaneously, resulting in intermittent localization failures and performance degradation. To address this issue, this paper proposes a tracking method called Bubble Trace (BT) for insufficient anchor coverage and asynchronous networks. By fully extracting the location information embedded in dual, single and zero anchor coverage, we develop a bidirectional bounding algorithm to offer the bubble-shaped regions that indicate the possible locations of the target. Moreover, instead of separately estimating each position point of the target, we construct the trace by finding a maximum-likelihood path in a graph. The design is evaluated through extensive simulation and a test-bed experiment with 20 MicaZ nodes. Results show that the proposed scheme improves the tracking accuracy without using additional hardware under insufficient anchor coverage.

Flooding in low-duty-cycle wireless sensor networks is very costly due to asynchronous schedules of sensor nodes. To adapt existing flooding-tree-based designs for low-duty-cycle networks, we shall schedule nodes of common parents wake up simultaneously. Traditionally, energy optimality in a designated flooding-tree is achieved by selecting parents with the highest link quality. In this work, we demonstrate that surprisingly more energy can be saved by considering link correlation. Specifically, this work first experimentally verifies the existence of link correlation and mathematically proves that the energy consumption of broadcasting can be reduced by letting nodes with higher correlation receive packets simultaneously. A novel flooding scheme, named Correlated Flooding, is then designed so that nodes with high correlation are assigned to a common sender and their receptions of a broadcasting packet are only acknowledged by a single ACK. This unique feature effectively ameliorates the ACK implosion problem, saving energy on both data packets and ACKs. We evaluate Correlated Flooding with extensive simulations and a testbed implementation with 20 MICAz nodes. We show that Correlated Flooding saves more than 66% energy on ACKs and 15%-50% energy on data packets for most network settings, while having similar performance on flooding delay and reliability.

In this paper, we present r-kernel, an operating system kernel foundation specifically designed to improve software reliability in networked embedded systems. The key novelty of r-kernel lies in that it exploits the time dimension of software execution to improve robustness. Specifically, r-kernel keeps track of the execution of applications through checkpoints. If one application has been determined to have failed, r-kernel performs rollback operations to restore its state to one of those checkpoints created earlier. For the second round of operation, r-kernel provides a safe mode environment to avoid triggering the same bugs. Finally, if the whole system has crashed, r-kernel relies on watchdog timers to reset the node, and develops a technique called past-run trace reconstruction to locate and report the thread that had caused the system failure. We have implemented r-kernel based on the LiteOS operating system kernel running on the popular MicaZ platform. We demonstrate that it achieves the desired goals above with acceptable overhead.

Working in the duty cycling mode enables sensor nodes to utilize limited energy efficiently instead of unnecessary idle listening. In such networks, awareness of neighboring nodes' working schedules is essential, especially when each node sets up the schedule independently. Most traditional research assumes that a node can always share its working schedule with its neighbors once it joins the network. However, dynamic energy supply and varied requirements of system performance make adjusting duty cycles necessary. Consequently, sensor nodes have to regularly change their schedules and advertise the new schedule to their one-hop neighbors. In this work, instead of changing nodes' working schedule directly, we introduce SSD, a staged and smooth design for safeguarding schedule updates. Our design is aimed at bounding average packet loss rate with a minimum energy cost. We evaluate our design with large-scale simulation and show that under the comparable packet loss rate, our design saves up to 35% energy compared with the minimal packet loss solution.

Vehicular ad hoc networks (VANETs) represent promising technologies for improving driving safety and efficiency. Due to the highly dynamic driving patterns of vehicles, it has been a challenging research problem to achieve effective and time-sensitive data forwarding in vehicular networks. In this paper, a Shared-Trajectory-based Data Forwarding Scheme (STDFS) is proposed, which utilizes shared vehicle trajectory information to address this problem. With access points sparsely deployed to disseminate vehicles' trajectory information, the encounters between vehicles can be predicted by the vehicle that has data to send, and an encounter graph is then constructed to aid packet forwarding. This paper focuses on the specific issues of STDFS such as encounter prediction, encounter graph construction, forwarding sequence optimization and the data forwarding process. Simulation results demonstrate the effectiveness of the proposed scheme.

Time synchronization remains as a challenging task in wireless sensor networks that face severe resource constraints. Unlike previous work's aiming at pure clock accuracy, this paper proposes On-Demand Synchronization (ODS), a design to achieve efficient clock synchronization with customized performance. By carefully modeling the error uncertainty of skew detection and its propagation over time, ODS develops a novel uncertainty-driven mechanism to adaptively adjust each clock calibration interval individually rather than traditional periodic synchronization, for minimum communication overhead while satisfying the desired accuracy. Besides, ODS provides a nice feature of predictable accuracy, allowing nodes to acquire the useful information about real-time qualities of their synchronization. We implemented ODS on the MICAz mote platform, and evaluated it through test-bed experiments with 33 nodes as well as simulations obeying real world conditions. Results show that ODS is practical, flexible, and quickly adapts to varying accuracy requirements and different traffic load in the network for improved system efficiency.

Energy constraint is a critical hurdle hindering the practical deployment of long-term wireless sensor network applications. Turning off (i.e., duty cycling) sensors could reduce energy consumption, however at the cost of low sensing fidelity due to sensing gaps introduced. Existing techniques have studied how to collaboratively reduce the sensing gap in space and time, however none of them provides a rigorous approach to confine sensing error within desirable bounds. In this work, we propose a collaborative scheme called CIES, based on the novel concept of error inference between collaborative sensor pairs. Within a node, we use a sensing probability bound to control tolerable sensing error. Within a neighborhood, nodes can trigger additional sensing activities of other nodes when inferred sensing error has aggregately exceed the tolerance. We conducted simulations to investigate system performance using historical soil temperature data in Wisconsin-Minnesota area. The simulation results demonstrate that the system error is confined within the specified error tolerance bounds and that a maximum of 60 percent of the energy savings can be achieved, when the CIES is compared to several fixed probability sensing schemes such as eSense. We further validated the simulation and algorithms by constructing a lab test-bench to emulate actual environment monitoring applications. The results show that our approach is effective and efficient in tracking the dramatic temperature shift in highly dynamic environments.

In wireless sensor networks (WSNs), trap coverage has recently been proposed to tradeoff between the availability of sensor nodes and sensing performance. It offers an efficient framework to tackle the challenge of limited resources in large scale sensor networks. Currently, existing works only studied the theoretical foundation of how to decide the deployment density of sensors to ensure the desired degree of trap coverage. However, the practical issues such as how to efficiently schedule sensor node to guarantee trap coverage under an arbitrary deployment is still left untouched. In this paper, we formally formulate the Minimum Weight Trap Cover Problem and prove it is an NP-hard problem. To solve the problem, we introduce a bounded approximation algorithm, called Trap Cover Optimization (TCO) to schedule the activation of sensors while satisfying specified trap coverage requirement. The performance of Minimum Weight Trap Coverage we find is proved to be at most O(ρ) times of the optimal solution, where ρ is the density of sensor nodes in the region. To evaluate our design, we perform extensive simulations to demonstrate the effectiveness of our proposed algorithm and show that our algorithm achieves at least 14% better energy efficiency than the state-of-the-art solution.

Based on spatiotemporal properties of neighborhood and mobile properties of nodes in the networks, we propose Selective Reference Mechanism to trade off between the delay and overhead of neighbor discovery in low-duty-cycle WSNs. Extensive simulation and test-bed experiment confirm our theoretical analysis, showing as much as 35.4% increase in discovery probability, 38.6% reduction in discovery delay and 27.7% reduction in total energy consumption.

To bridge the gap between insufficiency of existing proximity authentication solutions and the increasing demand of high security guarantee for access control systems, we develope a WISP-based access control system combing electronic and mechanical authentication methods. In our authentication, encryption complexity is changeable and trusted users can share privileges with each other. During experiments, our system has achieved 95% authentication accuracy rate with up to 3 different users.

Quorum-based schemes, e.g., GQS, can ensure asynchronous neighbors to discover each other within bounded time under low-duty-cycle operations. But they are tightly based on the assumption that duty cycles of devices fit some specific prefixed patterns. We tackle this problem by proposing a distributed quorum system to speed up the discovery.

Road networks are one of important surveillance areas in military scenarios. In these road networks, sensors will be sparsely deployed (hundreds of meters apart) for the cost-effective deployment. This makes the existing localization solutions based on the ranging ineffective. To address this issue, this paper introduces a novel approach based on the passive vehicular traffic measurement, called Autonomous Passive Localization (APL). Our work is inspired by the fact that vehicles move along routes with a known map. Using binary vehicle-detection time stamps, we can obtain distance estimates between any pair of sensors on roadways to construct a virtual graph composed of sensor identifications (i.e., vertices) and distance estimates (i.e., edges). The virtual graph is then matched with the topology of the road map, in order to identify where sensors are located on roadways. We evaluate our design outdoors on Minnesota roadways and show that our distance estimate method works well despite traffic noises. In addition, we show that our localization scheme is effective in a road network with 18 intersections, where we found no location matching error, even with a maximum sensor time synchronization error of 0.07 sec and a vehicle speed deviation of 10 km/h.

In this work, we introduce the concept of Dynamic Switch-based Forwarding (DSF) that optimizes the 1) expected data delivery ratio, 2) expected communication delay, or 3) expected energy consumption for low-duty-cycle wireless sensor networks under unreliable communication links. DSF is designed for networks with possibly unreliable communication links and predetermined node communication schedules. To our knowledge, these are the most encouraging results to date in this new research direction. In this paper, DSF is evaluated with a theoretical analysis, extensive simulation, and physical testbed consisting of 20 MicaZ motes. Results reveal the remarkable advantage of DSF in extremely low-duty-cycle sensor networks in comparison to three well-known solutions (ETX [CHECK END OF SENTENCE], {\rm PRR}\times{\rm D} [CHECK END OF SENTENCE], and DESS [CHECK END OF SENTENCE]). We also demonstrate our solution defaults into ETX in always-awake networks and DESS in perfect-link networks.

Monitoring personal locations with a potentially untrusted server poses privacy threats to the monitored individuals. To this end, we propose a privacy-preserving location monitoring system for wireless sensor networks. In our system, we design two in-network location anonymization algorithms, namely, resource and quality-aware algorithms, that aim to enable the system to provide high-quality location monitoring services for system users, while preserving personal location privacy. Both algorithms rely on the well-established k-anonymity privacy concept, that is, a person is indistinguishable among k persons, to enable trusted sensor nodes to provide the aggregate location information of monitored persons for our system. Each aggregate location is in a form of a monitored area A along with the number of monitored persons residing in A, where A contains at least k persons. The resource-aware algorithm aims to minimize communication and computational cost, while the quality-aware algorithm aims to maximize the accuracy of the aggregate locations by minimizing their monitored areas. To utilize the aggregate location information to provide location monitoring services, we use a spatial histogram approach that estimates the distribution of the monitored persons based on the gathered aggregate location information. Then, the estimated distribution is used to provide location monitoring services through answering range queries. We evaluate our system through simulated experiments. The results show that our system provides high-quality location monitoring services for system users and guarantees the location privacy of the monitored persons.

This paper proposes a Trajectory-Based Data (TBD) Forwarding scheme, tailored for the data forwarding for roadside reports in light-traffic vehicular ad hoc networks. State-of-the-art schemes have demonstrated the effectiveness of their data forwarding strategies by exploiting known vehicular traffic statistics (e.g., densities and speeds). These results are encouraging, however, further improvements can be made by taking advantage of the growing popularity of GPS-based navigation systems. This paper presents the first attempt to effectively utilize vehicles' trajectory information in a privacy-preserving manner. In our design, such trajectory information is combined with the vehicular traffic statistics for a better performance. In a distributed way, each individual vehicle computes its end-to-end expected delivery delay to the Internet access points based on its position on its vehicle trajectory and exchanges this delay with neighboring vehicles to determine the best next-hop vehicle. For the accurate end-to-end delay computation, this paper also proposes a link delay model to estimate the packet forwarding delay on a road segment. Through theoretical analysis and extensive simulation, it is shown that our link delay model provides the accurate link delay estimation and our forwarding design outperforms the existing scheme in terms of both the data delivery delay and packet delivery ratio.

Wireless sensor networks have been considered as a promising tool for many location-dependent applications. In such deployments, the requirement of low system cost prohibits many range-based methods for sensor node localization; on the other hand, range-free approaches depending only on radio connectivity may underutilize the proximity information embedded in neighborhood sensing. In response to these limitations, this paper introduces a proximity metric called RSD to capture the distance relationships among 1-hop neighboring nodes in a range-free manner. With little overhead, RSD can be conveniently applied as a transparent supporting layer for state-of-the-art connectivity-based localization solutions to achieve better accuracy. We implemented RSD with three well-known algorithms and evaluated using two outdoor test beds: an 850-foot-long linear network with 54 MICAz motes, and a regular 2D network covering an area of 10,000 square feet with 49 motes. Results show that our design helps eliminate estimation ambiguity with a subhop resolution, and reduces localization errors by as much as 35 percent. In addition, simulations confirm its effectiveness for large-scale networks and reveal an interesting feature of robustness under unevenly distributed radio path loss.

In energy-harvesting sensor networks, limited ambient energy from environment necessitates sensor nodes to operate at a low-duty-cycle, i.e., they communicate briefly and stay asleep most of time. Such low-duty-cycle operation leads to orders of magnitude longer communication delays in comparison with traditional always-active networks, imposing a new challenge in many time-sensitive sensor network applications (e.g., tracking and alert). In this paper, we introduce novel solutions for bounding sink-to-node communications in energy-harvesting sensor networks. We first present an optimal solution for the sink-to-one case and its distributed implementation. For the sink-to-many case, we theoretically prove its NP-Hardness and in approximability property, followed by an efficient heuristic solution. We have evaluated our design with both extensive simulation and a TinyOS/Mote based implementation. Compared with an improved version of a state-of-the-art design, our delay maintenance design effectively provides E2E delay guarantees while consuming as much as 60% less energy.

This paper proposes a data forwarding scheme called Trajectory-based Statistical Forwarding (TSF), tailored for the data delivery from infrastructure nodes (e.g., Internet access points) to moving vehicles in vehicular networks. To our knowledge, this paper presents the first attempt to investigate how to effectively utilize the packet destination vehicle's trajectory for such an infrastructure-to-vehicle data delivery. This data delivery is performed through the computation of a target point based on the destination vehicle's trajectory that is an optimal rendezvous point of the packet and the destination vehicle. TSF forwards packets over multi-hop to a selected target point where the vehicle is expected to pass by. Such a target point is selected optimally to minimize the packet delivery delay while satisfying the required packet delivery probability. The optimality is achieved analytically by utilizing the packet's delivery delay distribution and the destination vehicle's travel delay distribution. Through theoretical analysis and extensive simulation, it is shown that our design provides an efficient data forwarding under a variety of vehicular traffic conditions.

The ability to move energy around makes it feasible to build distributed energy storage systems that can robustly extend the lifetime of networked sensor systems. eShare supports the concept of energy sharing among multiple embedded sensor devices by providing designs for energy routers (i.e., energy storage and routing devices) and related energy access and network protocols. In a nutshell, energy routers exchange energy sharing control information using their data network while sharing energy freely among connected embedded sensor devices using their energy network. To improve sharing efficiency subject to energy leakage, we develop an effective energy charging and discharging mechanism using an array of ultra-capacitors as the main component of an energy router. We extensively evaluate our system under six real-world settings. Results indicate our charging and discharging control can effectively minimize the energy leaked away. Moreover, the energy sharing protocol can quantitatively share 113J energy with 96.82% accuracy in less than 2 seconds.

Multifrequency media access control has been well understood in general wireless ad hoc networks, while in wireless sensor networks, researchers still focus on single frequency solutions. In wireless sensor networks, each device is typically equipped with a single radio transceiver and applications adopt much smaller packet sizes compared to those in general wireless ad hoc networks. Hence, the multifrequency MAC protocols proposed for general wireless ad hoc networks are not suitable for wireless sensor network applications, which we further demonstrate through our simulation experiments. In this article, we propose MMSN, which takes advantage of multifrequency availability while, at the same time, takes into consideration the restrictions of wireless sensor networks. In MMSN, four frequency assignment options are provided to meet different application requirements. A scalable media access is designed with efficient broadcast support. Also, an optimal nonuniform back-off algorithm is derived and its lightweight approximation is implemented in MMSN, which significantly reduces congestion in the time synchronized media access design. Through extensive experiments, MMSN exhibits the prominent ability to utilize parallel transmissions among neighboring nodes. When multiple physical frequencies are available, it also achieves increased energy efficiency, demonstrating the ability to work against radio interference and the tolerance to a wide range of measured time synchronization errors.

The circular sensing model has been widely used to estimate performance of sensing applications in existing analyses and simulations. While this model provides valuable high-level guidelines, the quantitative results obtained may not reflect the true performance of these applications, due to the sensing irregularity introduced by existence of obstacles in real deployment areas and insufficient hardware calibration. In this paper, we design and implement two sensing area modeling (SAM) techniques useful in the real world. They complement each other in the design space. Physical sensing area modeling (P-SAM) provides accurate physical sensing area for individual nodes using controlled or monitored events, while virtual sensing area modeling (V-SAM) provides continuous sensing similarity between nodes using natural events in an environment. With these two models, we pioneer an investigation of the impact of sensing irregularity on application performance, such as coverage scheduling. We evaluate SAM extensively in real-world settings, using testbeds consisting of 14 XSM motes. To study the performance at scale, we also provide an extensive 1,400-node simulation. Evaluation results reveal several serious issues concerning circular models and demonstrate significant improvements in several applications when SAM is used instead.

This paper proposes a VIrtual Scanning Algorithm (VISA), tailored and optimized for road network surveillance. Our design uniquely leverages upon the facts that 1) the movement of targets (e.g., vehicles) is confined within roadways and 2) the road network maps are normally known. We guarantee the detection of moving targets before they reach designated protection points (such as temporary base camps), while maximizing the lifetime of the sensor network. The main idea of this work is virtual scan-waves of sensing activities scheduled for road network protection. We provide design-space analysis on the performance of virtual scan in terms of lifetime and average detection delay. Importantly, to our knowledge, this is the first work to study how to guarantee target detection while sensor network deteriorates, using a novel hole handling technique. Through theoretical analysis and extensive simulation, it is shown that a surveillance system, using our design, sustains orders-of-magnitude longer lifetime than full coverage algorithms, and as much as 10 times longer than legacy duty cycling algorithms.

This paper proposes a trajectory-based data forwarding (TBD) scheme, tailored for the data forwarding in light- traffic vehicular ad-hoc networks. State-of-the-art schemes have demonstrated the effectiveness of their data forwarding strategies by exploiting known vehicular traffic statistics (e.g., densities and speeds) in these vehicular networks. These results are encouraging, however, further improvements can be made by taking advantage of the growing popularity of GPS-based navigation systems. This paper presents the first attempt to investigate how to effectively utilize vehicles" trajectory information in a privacy-preserving manner. In our design, the trajectory information is combined with the traffic statistics to improve the performance of data forwarding in road networks. Through theoretical analysis and extensive simulation, it is shown that our design outperforms the existing scheme.

With advances in energy harvesting techniques, it is now feasible to build sustainable sensor networks (SSN) to support long-term applications. Unlike battery-powered sensor networks, the objective of sustainable sensor networks is to effectively utilize a continuous stream of ambient energy. Instead of pushing the limits of energy conservation, we are aiming at energy-synchronized designs1to keep energy supplies and demands in balance. Specifically, this work presents the Energy Synchronized Communication (ESC) as a transparent middle-ware between the network layer and data link layer that controls the amount and timing of RF activity at receiving nodes. In this work, we first derive a delay model for cross-traffic at individual nodes, which reveals an interesting stair effect in low-duty-cycle networks. This effect allows us to design a localized energy synchronization control with O(1) time complexity that shuffles or adjusts the working schedule of a node to optimize cross-traffic delays in the presence of changing duty-cycle budgets. Under different rates of energy fluctuations, shuffle-based and adjustment-based methods have different influences on logical connectivity and cross-traffic delay, due to the inconsistent views of working schedules among neighboring nodes before schedule updates. We study the trade-off between them and propose methods to update working schedules efficiently. To evaluate our work, ESC is implemented on MicaZ nodes with two state-of-the-art routing protocols. Both test-bed experiment and large scale simulation results show significant performance improvements over randomized synchronization controls.

This paper proposes a virtual scanning algorithm (VISA), tailored and optimized for road network surveillance. Our design uniquely leverages upon the facts that (i) the movement of targets (e.g., vehicles) is confined within roadways and (ii) the road network maps are normally known. We guarantee the detection of moving targets before they reach designated protection points (such as temporary base camps), while maximizing the lifetime of the sensor network. The main idea of this work is virtual scan - waves of sensing activities scheduled for road network protection. We provide design-space analysis on the performance of virtual scan in terms of lifetime and average detection delay. Importantly, to our knowledge, this is the first work to study how to guarantee target detection while sensor network deteriorates, using a novel hole handling technique. Through theoretical analysis and extensive simulation, it is shown that a surveillance system, using our design, sustains orders-of-magnitude longer lifetime than full coverage algorithms, and as much as ten times longer than legacy duty cycling algorithms.

Tracking mobile targets using sensor networks is a challenging task because of the impacts of in-the-flled factors such as environment noise, sensing irregularity and etc. This paper proposes a robust tracking framework using node sequences, an ordered list extracted from unreliable sensor readings. Instead of estimating each position point separately in a movement trace, we convert the original tracking problem to the problem of finding the shortest path in a graph, which is equivalent to optimal matching of a series of node sequences. In addition to the basic design, multidimensional smoothing is developed to enhance tracking accuracy. Practical system deployment related issues are discussed in the paper, and the design is evaluated with both simulation and a system implementation using Pioneer III Robot and MICAz sensor nodes. In fact, tracking with node sequences provides a useful layer of abstraction, making the design framework generic and compatible with different physical sensing modalities.

Location monitoring systems are used to detect human activities and provide monitoring services, e.g., aggregate queries. In this paper, we consider an aggregate location monitoring system where wireless sensor nodes are counting sensors that are only capable of detecting the number of objects within their sensing areas. As traditional query processors rely on the knowledge of users' exact locations, they cannot provide any monitoring services based on the readings reported from counting sensors. To this end, we propose an adaptive spatio-temporal histogram to enable monitoring services without the need of users' exact locations. The main idea of the histogram is to keep statistics about the distribution of moving objects. At the core of the histogram, we propose three techniques, memorization, locality awareness and packing, to improve monitoring accuracy and efficiency. Furthermore, the histogram is designed in a way that achieves a trade-off between the energy and bandwidth consumption of the sensor network and the accuracy of monitoring services. Experimental results show that the proposed histogram provides high-quality location monitoring services (i.e., 90% accuracy for both skewed and uniform mobility patterns) and outperforms a basic histogram and the state-of-the-art spatio-temporal histogram by two orders of magnitude in most cases.

Intended for network-wide dissemination of commands, configurations and code binaries, flooding has been investigated extensivelyinwirelessnetworks. However,littleworkhasyetbeendone on low-duty-cycle wireless sensor networks in which nodes stay asleep most of time and wake up asynchronously. In this type of network,abroadcastingpacketisrarelyreceivedbymultiplenodes simultaneously, a unique constraining feature that makes existing solutions unsuitable. Combined with unreliable links, flooding in low-duty-cycle networks is a new challenging issue. In this paper, we introduce Opportunistic Flooding, a novel design tailored for low-duty-cycle networks with unreliable wireless links and predetermined working schedules. The key idea is to make probabilistic forwarding decisions at a sender based on the delay distribution of next-hop nodes. Only opportunistically early packets are forwarded using links outside the energy optimal tree to reduce the flooding delay and redundancy in transmission. To improve performance further, we propose a forwarder selection methodtoalleviatethehiddenterminalproblemandalink-qualitybased backoff method to resolve simultaneous forwarding operations. We evaluate Opportunistic Flooding with extensive simulation and a test-bed implementation consisting of 30 MicaZ nodes. Evaluation shows our design is close to the optimal performance achievable by oracle flooding designs. Compared with improved traditionalflooding,ourdesignachievessignificantlyshorterflooding delay while consuming only 20 % ∼ 60 % of the transmission energy invarious low-duty-cycle networksettings. Categories andSubject Descriptors

To ensure sustainable operations of wireless sensor systems, environmental energy harvesting has been regarded as the right solution for long-term applications. In energy-dynamic environments, energy conservation is no longer considered necessarily beneficial, because energy storage units (e.g., batteries or capacitors) are limited in capacity and leakage-prone. In contrast to legacy energy conservation approaches, we aim at energy synchronization for wireless sensor devices. The starting point of this work is TwinStar, which uses ultra-capacitor as the only energy storage unit. To efficiently use the harvested energy, we design and implement leakage-aware feedback control techniques to match local and network-wide activity of sensor nodes with the dynamic energy supply from environments. We conduct system evaluation under three typical real-world settings - indoor, outdoor, and mobile backpack under a wide range of system settings. Results indicate our leakage-aware control can effectively utilize energy that could otherwise leak away. Nodes running leakage-aware control can enjoy 70% more energy than the ones running non-leakage-aware control and application performance (e.g., event detection) can be improved significantly.

Data delivery is a major function of sensor network applications. Many applications, such as military surveillance, require the detection of interested events to be reported to a command center within a specified time frame, and therefore impose a real-time bound on communication delay. On the other hand, to conserve energy, one of the most effective approaches is to keep sensor nodes in the dormant state as long as possible while satisfying application requirements. Obviously a node cannot communicate if it is not active. Therefore, to deliver data in a timely manner for such extremely low duty-cycle sensor networks, communication needs to be carefully managed among sensor nodes. In this work, we introduce three different approaches to provide real-time guarantee of communication delay. First, we present a method for increasing duty-cycle at individual node. Then we describe a scheme on placement of sink nodes. Based on previous two methods, we discuss a hybrid approach that shows better balance between cost and efficiency on bounding communication delay. Our solution is global optimal in terms of minimizing the energy consumption for bounding pairwise end-to-end delay. For many-to-one and many-to-many cases, which are NP-hard, we propose corresponding heuristic algorithms for them. To our knowledge, these are the most generic and encouraging results to date in this new research direction. We evaluate our design with an extensive simulation of 5,000 nodes as well as with a small-scale running test-bed on TinyOS/Mote platform. Results show the effectiveness of our approach and significant improvements over an existing solution.

Many applications in wireless sensor networks require communication performance that is both consistent and high quality. Unfortunately, performance of current network protocols can vary significantly because of various interferences and environmental changes. Current protocols estimate link quality based on the reception of probe packets over a short time period. This method is neither efficient nor accurate enough to capture the dramatic variations of link quality. Therefore, we propose a link metric called competence that characterizes links over a longer period of time. We combine competence with current short term estimations in routing algorithm designs. To further improve network performance we have designed a distributed route maintenance framework based on feedback control solutions. In real system evaluations with 48 T-Motes, our overall solution improves end-to-end packet delivery ratio over existing solutions by up to 40%, while reducing energy consumption by up to 22%. Importantly, our solution also achieves more stable and better transient performance than current approaches.

Wireless Sensor Networks (WSN) promise researchers a powerful instrument for observing sizable phenomena with fine granularity over long periods. Since the accuracy of data is important to the whole system's performance, detecting nodes with faulty readings is an essential issue in network management. As a complementary solution to detecting nodes with functionnal faults, this paper proposes FIND, a novel method to detect nodes with data faults that neither assumes a particular sensing model nor requires costly event injections. After the nodes in a network detect a natural event, FIND ranks the nodes based on their sensing readings as well as their physical distances from the event. FIND works for systems where the measured signal attenuates with distance. A node is considered faulty if there is a significant mismatch between the sensor data rank and the distance rank Theoretically, we show that average ranking difference is a provable indicator of possible data faults. FIND is extensively evaluated in simulations and two test bed experiments with up to 25 MicaZ nodes. Evaluation shows that FIND has a less than 5% miss detection rate and false alarm rate in most noisy environments.

The ability to accurately profile energy consumption is of great importance for energy management in low-power devices. This work presents a novel energy profiling architecture by combining the high-speed CPLD bus signaling capability of mPlatform with the smart TwinStar power board. By running mPlatform under different modes, we are able to utilize an MMSE estimator to analyze per-component energy consumption rates with sufficient accuracy. In our experiment, we use the profiling results to determine the working condition of individual components, as well as the hardware configuration of the sensor node.

Wireless sensor networks have been proposed for many location-dependent applications. In such applications, the requirement of low system cost prohibitsmany range-based methods for sensor node localization; on the other hand, range-free localization depending only on connectivity may underutilize the proximity information embedded in neighborhood sensing. In response to the above limitations, this paper presents a range-free approach to capturing a relative distancebetween1-hopneighboringnodesfromtheirneighborhood orderings that serve as unique high-dimensional location signatures for nodes in the network. With little overhead, the proposed design can be conveniently applied as a transparent supporting layer for many state-of-the-art connectivity-based localization solutions to achieve better positioningaccuracy. Weimplementedourdesignwiththree well-knownlocalizationalgorithmsandtesteditintwotypes ofoutdoortest-bedexperiments: an850-foot-longlinearnetwork with 54 MICAz motes, and a regular2D networkcovering an area of 10000 square feet with 49 motes. Results show that our design helps eliminate estimation ambiguity with sub-hop resolution, and reduces localization errors by as much as 35%. In addition, extensive simulations reveal an interestingfeature of robustnessfor our design underunevenly distributed radio propagation path loss, and confirm itseffectivenessforlarge-scalenetworks. Categories andSubject Descriptors

Energy efficiency is a fundamental issue for outdoor sensor network systems. This article presents the design and implementation of multidimensional power management strategies in VigilNet, a major recent effort to support long-term surveillance using power-constrained sensor devices. A novel tripwire service is integrated with an effective sentry and duty cycle scheduling in order to increase the system lifetime, collaboratively. The tripwire service partitions a network into distinct, nonoverlapping sections and allows each section to be scheduled independently. Sentry scheduling selects a subset of nodes, the sentries, which are turned on while the remaining nodes save energy. Duty cycle scheduling allows the active sentries themselves to be turned on and off, further lowering the average power draw. The multidimensional power management strategies proposed in this article were fully implemented within a real sensor network system using the XSM platform. We evaluate key system parameters using a network of 200 XSM nodes in an outdoor environment, and an analytical probabilistic model. We evaluate network lifetime using a simulation of a 10,000-node network that uses measured XSM power values. These evaluations demonstrate the effectiveness of our integrated approach and identify a set of lessons and guidelines, useful for the future development of energy-efficient sensor systems. One of the key results indicates that the combination of the three presented power management techniques is able to increase the lifetime of a realistic network from 4 days to 200 days.

Many event-driven localization methods have been proposed as low cost, energy efficient solutions for wireless senor networks. In order to eliminate the requirement of accurately controlled events in existing approaches, we present a practical design using totally uncontrolled events for stationary sensor node positioning. The novel idea of this design is to estimate both the event generation parameters and the location of each sensor node by processing node sequences easily obtained from uncontrolled event distribution. To demonstrate the generality of our design, both straight-line scan and circular wave propagation events are addressed in this paper, and we evaluated our approach through theoretical analysis, extensive simulation and a physical test bed implementation with 41 MICAz motes. The evaluation results illustrate that with only randomly generated events, our solution can effectively localize sensor nodes with excellent flexibility while adding no extra cost at the resource constrained sensor node side. In addition, localization using uncontrolled events provides a nice potential option of achieving node positioning through natural ambient events.

In this paper, we advocate asymmetric function placement as one of guiding principles to architect sensor network systems. We demonstrate its generic applicability and effectiveness by applying this principle to three typical sensor network technologies, namely, localization (Spotlight), sensing (uSense) and communication (mNets). These technologies have very dissimilar features, representing a wide spectrum of system design requirements. We have invested significant effort to design, implement and evaluate our techniques on TinyOS/Mote testbeds. The results from several running systems indicate that asymmetric function placement is a powerful guiding principle to achieveefficiencyandhigh-performancesimultaneously in wireless sensor networks. At the end, we exam the system features that discourage the use of asymmetric function placement and approaches to address them.

In road networks, sensors are deployed sparsely (hundreds of meters apart) to save costs. This makes the existing localization solutions based on the ranging be ineffective. To address this issue, this paper introduces an autonomous passive localization scheme, called APL. Our work is inspired by the fact that vehicles move along routes with a known map. Using binary vehicle-detection timestamps, we can obtain distance estimates between any pair of sensors on roadways to construct a virtual graph composed of sensor identifications (i.e., vertices) and distance estimates (i.e., edges). The virtual graph is then matched with the topology of road map, in order to identify where sensors are located in roadways. We evaluate our design outdoor in Minnesota roadways and show that our distance estimate method works well despite of traffic noises. In addition, we show that our localization scheme is effective in a road network with eighteen intersections, where we found no location matching error, even with a maximum sensor time synchronization error of 0.3 sec and the vehicle speed deviation of 10 km/h.

This paper demonstrates how to use multiple channels to improve communication performance in Wireless Sensor Networks (WSNs). We first investigate multi-channel realities in WSNs through intensive empirical experiments with Micaz motes. Our study shows that current multi-channel protocols are not suitable for WSNs, because of the small number of available channels and unavoidable time errors found in real networks. With these observations, we propose a novel tree-based multichannel scheme for data collection applications, which allocates channels to disjoint trees and exploits parallel transmissions among trees. In order to minimize interference within trees, we define a new channel assignment problem which is proven NP- complete. Then we propose a greedy channel allocation algorithm which outperforms other schemes in dense networks with a small number of channels.We implement our protocol, called TMCP, in a real testbed. Through both simulation and real experiments, we show that TMCP can significantly improve network throughput and reduce packet losses. More importantly, evaluation results show that TMCP better accommodates multi-channel realities found in WSNs than other multi-channel protocols.

This paper presents LiteOS, a multi-threaded operating system that provides Unix-like abstractions for wireless sensor networks. Aiming to be an easy-to-use platform, LiteOS offers a number of novel features, including: (1) a hierarchical file system and a wireless shell interface for user interaction using UNIX-like commands; (2) kernel support for dynamic loading and native execution of multithreaded applications; and (3) online debugging, dynamic memory, and file system assisted communication stacks. LiteOS also supports software updates through a separation between the kernel and user applications, which are bridged through a suite of system calls. Besides the features that have been implemented, we also describe our perspective on LiteOS as an enabling platform. We evaluate the platform experimentally by measuring the performance of common tasks, and demonstrate its programmability through twenty-one example applications.

Sensor networks have been used in many surveillance systems, providing statistical information about monitored areas. Accurate counting information (e.g., the distribution of the total number of targets) is often important for decision making. As a complementary solution to double-counting in communication, this paper presents the first work that deals with double-counting in sensing for wireless sensor networks. The probability mass function (pmf) of target counts is derived first. This, however, is shown to be computationally prohibitive when a network becomes large. A partitioning algorithm is then designed to significantly reduce computation complexity with a certain loss in counting accuracy. Finally, two methods are proposed to compensate for the loss. To evaluate the design, we compare the derived probability mass function with ground truth obtained through exhaustive enumeration in small-scale networks. In large-scale networks, where pmf ground truth is not available, we compare the expected count with true target counts. We demonstrate that accurate counting within 1 ∼ 3% relative error can be achieved with orders of magnitude reduction in computation, compared with an exhaustive enumeration-based approach.

Extensive empirical results reveal that interference can cause link qualities to change quickly and dramatically. For such highly dynamic links, the short term link quality estimations widely used in existing protocols require frequent measurements and may not be accurate. As a result, when these links are selected, end-to-end communication quality varies significantly. Also, route changes occur frequently, introducing traffic oscillation and excessive overhead in network protocols. To achieve good and stable network performance, it is not enough to use short term link estimation. It is essential to characterize a link's capacity to perform well at a desired level in the presence of interference and environmental changes. Therefore, we propose a performance metric called competence. We have incorporated the competence metric into routing algorithm designs. We have also designed and implemented a maintenance framework that stabilizes performance at both link and network layers. This framework allocates the desired performance level among multiple links along an active route by using an end-to-end feedback loop, and enforces the performance level of each link through adaptive transmission power control and retransmission control. In real system evaluations with 48 TMotes, our solution outperforms previous protocols significantly and achieves end-to-end stable performance for more than 99% of the time over 24 hours.

Starting from the features and impact of energy leakage in ultra-capacitor powered systems, this demonstration highlights the design of a capacitor-only Twin-Star node, and a leakage-aware energy synchronization methodology.

This demo presents a privacy-preserving aggregate location monitoring system, namely, TinyCasper, in which we can monitor moving objects in wireless sensor networks while preserving their location privacy. TinyCasper consists of two main modules, in-network location anonymization and aggregate query processing over anonymized locations. In the first module, trusted wireless sensor nodes collaborate with each other to anonymize users' exact locations by a cloaked spatial region that satisfies a prespecified privacy requirement. On the other side, the aggregate query processing module collects and analyzes the cloaked spatial regions reported from the wireless sensor nodes to support aggregate and alarm queries over anonymized locations. The prototype of TinyCasper is implemented on a physical test-bed on the TinyOS/Mote platform with 39 MICAz motes.

For many sensor network applications, such as military surveillance, it is necessary to provide full sensing coverage to a security-sensitive area while, at the same time, minimizing energy consumption and extending system lifetime by leveraging the redundant deployment of sensor nodes. In this paper, we propose a surveillance service for sensor networks based on a distributed energy-efficient sensing coverage protocol. In the protocol, each node is able to dynamically decide a schedule for itself to guarantee a certain degree-of-coverage (DOC) with average energy consumption inversely proportional to the node density. Several optimizations and extensions are proposed to enhance the basic design with a better load-balance feature and a longer network lifetime. We consider and address the impact of the target size and the unbalanced initial energy capacity of individual nodes to the network lifetime. Several practical issues such as the localization error, irregular sensing range, and unreliable communication links are addressed as well. Simulation shows that our protocol extends system lift-time significantly with low energy consumption. It outperforms other state-of-the-art schemes by as much as 50% reduction in energy consumption and as much as 130% increase in the half-life of the network.

As a key approach to achieve energy efficiency in sensor networks, sensing coverage has been studied extensively. Researchers have designed many coverage protocols to provide various kinds of service guarantees on the network lifetime, coverage ratio and detection delay. While these protocols are effective, they are not flexible enough to meet multiple design goals simultaneously. In this paper, we propose a unified sensing coverage architecture, called uSense, which features three novel ideas: asymmetric architecture, generic switching and global scheduling. We propose asymmetric architecture based on the conceptual separation of switching from scheduling. Switching is efficiently supported in sensor nodes, while scheduling is done in a separated computational entity, where multiple scheduling algorithms are supported. As an instance, we propose a two-level global coverage algorithm, called uScan. At the first level, coverage is scheduled to activate different portions of an area. We propose an optimal scheduling algorithm to minimize area breach. At the second level, sets of nodes are selected to cover active portions. Importantly, we show the feasibility to obtain optimal set-cover results in linear time if the layout of areas satisfies certain conditions. We evaluate our architecture with a network of 30 MicaZ motes, an extensive simulation with 10,000 nodes, as well as theoretical analysis. The results indicate that uSense is a promising architecture to support flexible and efficient coverage in sensor networks.

Providing efficient and reliable communication in wireless sensor networks is a challenging problem. To recover from corrupted packets, previous approaches have tried to use retransmissions and FEC mechanisms. The energy efficiency of these mechanisms, however, is very sensitive to unreliable links. In this paper, we present cluster-based forwarding, where each node forms a cluster such that any node in the next-hop's cluster can take forwarding responsibility. This architecture, designed specifically for wireless sensor networks, achieves better energy-efficiency by reducing retransmissions. Cluster-based forwarding is not a routing protocol. Rather, it is designed as an extension layer that can augment existing routing protocols. Using simulations, we demonstrate that cluster-based forwarding is effective in improving both end-to-end energy efficiency and latency of current routing protocols.

Despite the well-known fact that sensing patterns in reality are highly irregular, researchers continue to develop protocols with simplifying assumptions about the sensing. For example, a circular 0/1 sensing model is widely used in most existing simulators and analysis. While this model provides high-level guidelines, it could cause wrong estimation of system performance in the real world. In this project, we design and implement a practical Sensing Area Modeling technique, called SAM. By injecting events through regular and hierarchical training, SAM estimates the sensing areas of individual sensor nodes accurately. Especially, this work is the first to investigate the impact of irregular sensing area on application performance, such as coverage scheduling. We evaluate SAM using outdoor experiments with XSM motes, indoor experiment with 40 MicaZ motes as well as an extensive 1000-node simulation. Our evaluation results reveal serious problems caused by circular sensing model, while demonstrating significant performance improvements in major applications when SAM is used.

In an adversarial environment, various kinds of security attacks become possible if malicious nodes could claim fake locations that are different from where they are physically located. In this paper, we propose a secure localization mechanism that detects the existence of these nodes, termed as phantom nodes, without relying on any trusted entities, an approach significantly different from the existing ones. The proposed mechanism enjoys a set of nice features. First, it does not have any central point of attack. All nodes play the role of verifier, by generating local map, i.e. a view constructed based on ranging information from its neighbors. Second, this distributed and localized construction results in quite strong results: even when the number of phantom nodes is greater than that of honest nodes, we can Alter out most phantom nodes. Our analysis and simulations under realistic noisy settings demonstrate our scheme is effective in the presence of a large number of phantom nodes.

This paper proposes a minimal contour tracking algorithm (MCTA) that reduces energy consumption for tracking mobile targets in wireless sensor networks in terms of sensing and communication energy consumption. MCTA conserves energy by letting only a minimum number of sensor nodes participate in communication and perform sensing for target tracking. MCTA uses the minimal tracking area based on the vehicular kinematics. The modeling of target's kinematics allows for pruning out part of the tracking area that cannot be mechanically visited by the mobile target within scheduled time. So, MCTA sends the tracking area information to only the sensor nodes within minimal tracking area and wakes them up. Compared to the legacy scheme which uses circle-based tracking area, our proposed scheme uses less number of sensors for tracking in both communication and sensing without target missing. Through simulation, we show that MCTA outperforms the circle-based scheme with about 60% energy saving under certain ideal situations.

This demonstration highlights an interactive Unix-like shell for operating wireless sensor networks, where the user uses familiar Unix commands to complete tasks ranging from wireless installation of user applications to retrieval of data reports with the help of a built-in Unix-like file system.

In extremely low duty-cycle sensor networks, end-to-end communications cannot afford to maintain an always-awake communication backbone. Low duty-cycle, accompanied by the unreliable nature of wireless communication, makes it essential to design a new data forwarding scheme for such networks, so as to achieve network energy efficiency, reliability, and timeliness in an integrated fashion.

The circular sensing model has been widely used to estimate performance of sensing applications in existing analysis and simulations. While this model provides valuable high-level guidelines, the quantitative results obtained may not reflect the true performance of these applications, due to the existence of obstacles and sensing irregularity introduced by insufficient hardware calibration. In this project, we design and implement two Sensing Area Modeling (SAM) techniques useful in the real world. They complement each other in the design space. P-SAM provides accurate sensing area models for individual nodes using controlled or monitored events, while V-SAM provides continuous sensing similarity models using natural events in an environment. With these two models, we pioneer an investigation of the impact of sensing irregularity on application performance, such as coverage scheduling. We evaluate SAM extensively in real-world settings, using three testbeds consisting of 40 MICAz motes and 14 XSM motes. To study the performance at scale, we also provide an extensive 1,400-node simulation. Evaluation results reveal several serious issues concerning circular models, and demonstrate significant improvements

Wireless Sensor Networks have been proposed for use in many location-dependent applications. Most of these need to identify the locations of wireless sensor nodes, a challenging task because of the severe constraints on cost, energy and effective range of sensor devices. To overcome limitations in existing solutions, we present a Multi-Sequence Positioning (MSP) method for large-scale stationary sensor node localization in outdoor environments. The novel idea behind MSP is to reconstruct and estimate two-dimensional location information for each sensor node by processing multiple one-dimensional node sequences, easily obtained through loosely guided event distribution. Starting from a basic MSP design, we propose four optimizations, which work together to increase the localization accuracy. We address several interesting issues, such as incomplete (partial) node sequences and sequence flip, found in the Mirage test-bed we built. We have evaluated the MSP system through theoretical analysis, extensive simulation as well as two physical systems (an indoor version with 46 MICAz motes and an outdoor version with 20 MICAz motes). This evaluation demonstrates that MSP can achieve an accuracy within one foot, requiring neither additional costly hardware on sensor nodes nor precise event distribution. It also provides a nice tradeoff between physical cost (anchors) and soft cost (events), while maintaining localization accuracy.

In this paper, we present uCast, a novel multicast protocol for energy efficient content distribution in sensor networks. We design uCast to support a large number of multicast sessions, especially when the number of destinations in a session is small. In uCast, we do not keep any state information relevant to ongoing multicast deliveries at intermediate nodes. Rather, we directly encode the multicast information in the packet headers and parse these headers at intermediate nodes using a scoreboard algorithm proposed in this paper. We demonstrate that 1) uCast is powerful enough to support multiple addressing and unicast routing schemes and 2) uCast is robust, efficient, and scalable in the face of changes in network topology, such as those introduced by energy conservation protocols. We systematically evaluate the performance of uCast through simulations, compare it with other state-of-the-art protocols, and collect preliminary data from a running system based on the Berkeley motes platform

Recent studies on radio reality provided strong evidence that radio links between low-power sensor devices are extremely unreliable. In this paper, we study how to improve energy efficiency for reliable communication using such unreliable links. We identify an optimal bound on energy efficiency for reliable communication, and propose a new communication model in the link layer that asymptotically approaches this bound. This new model indicates a better path metric compared to previous path metrics, and we validate this by establishing a routing infrastructure based on this metric, which indeed achieves a higher energy efficiency compared to other stateof -the-art approaches. We present results from a systematic analysis, simulations and prototype experiments based on the MicaZ platform. The results give us fundamental insights on communication efficiency over unreliable links.

Abstract — Energy efficiency is a fundamental issue for out-door sensor network systems. This paper presents the design and implementation of multi-dimensional power management strategies in VigilNet, a major recent effort to support long-term surveillance using power-constrained sensor devices. We integrate a novel tripwire service with an effective sentry and duty cycle scheduling in order to increase the system lifetime, collaboratively. Through extensive system implementation, we demonstrate the feasibility to achieve high surveillance perfor-mance and energy efficiency, simultaneously. We invest a fair amount of effort to evaluate our architecture with a network of 200 XSM motes in an outdoor environment, an extensive simulation with 10,000 nodes, as well as an analytical probabilistic model. These evaluations demonstrate the effectiveness of our integrated approach and identify many interesting lessons and guidelines, useful for the future development of energy-efficient sensor systems. I.

Abstract — Sensing events from dynamic environments are normally asynchronous and non-repeatable. This lack of repeatability makes it particularly difficult to statistically evaluate the performance of sensor network applications. Hence, it is essential to have the capability to capture and replay sensing events, providing a basis not only for system evaluation, but also for realistic protocol comparison and parameter tuning. To achieve that, we design and implement EnviroLog, a distributed service that improves repeatability of experimental testing of sensor networks via asynchronous event recording and replay. To use EnviroLog, an application programmer needs only to specify two types of simple annotations to the source code. Automatically, the preprocessor embeds EnviroLog into any desired level of an event-driven architecture. It records all events generated by lower layers and can replay them later to upper layers on demand. We validate the accuracy and performance of recording and replay through a set of microbenchmarks, using the latest XSM platforms. We further demonstrate the strength of EnviroLog in system tuning and performance evaluation for sensor network applications in an outdoor environment with 37 XSMs. I.

Abstract — Multi-frequency media access control has been well understood in general wireless ad hoc networks, while in wireless sensor networks, researchers still focus on single frequency solutions. In wireless sensor networks, hardware devices are equipped with very limited communication ability and applications adopt much smaller packet sizes compared to those in general wireless ad hoc networks. Hence, the multi-frequency MAC protocols proposed for general wireless ad hoc networks are not suitable for wireless sensor network applications, which we further demonstrate through our simulation experiments. In this paper, we propose MMSN, the first multi-frequency MAC protocol for wireless sensor networks. In the MMSN protocol, four frequency assignment options are provided to meet different application requirements. A scalable media access is designed with efficient broadcast support. Also, an optimal non-uniform backoff algorithm is derived and its lightweight approximation is implemented in MMSN, which significantly reduces congestion in the time synchronized media access design. Through extensive experiments, MMSN exhibits prominent ability to utilize parallel transmission among neighboring nodes. It also achieves increased energy efficiency when multiple physical frequencies are available. I.

Since sensor nodes normally have limited resources in terms of energy, bandwidth and computation capability, efficiency is a key design goal in sensor network research. As one of techniques to achieve efficiency, data aggregation has been extensively investigated in recent literature. Previous research on data aggregation has demonstrated its effectiveness in reducing traffic, easing congestion and decreasing the energy consumption. However few are actually designed for a real-world application and implemented in a running system. This paper describes our design and implementation of a physical tracking system, using an aggressive data aggregation architecture as one of building blocks. This architecture can be generally applied to other sensor systems, where communication efficiency is a paramount concern and networking resources are limited.

No abstract available.

No abstract available.

Extensive empirical studies presented in this paper confirm that the quality of radio communication between low power sensor devices varies significantly with time and environment. This phenomenon indicates that the previous topology control solutions, which use static transmission power, transmission range, and link quality, might not be effective in the physical world. To address this issue, online transmission power control that adapts to external changes is necessary. This paper presents ATPC, a lightweight algorithm of Adaptive Transmission Power Control for wireless sensor networks. In ATPC, each node builds a model for each of its neighbors, describing the correlation between transmission power and link quality. With this model, we employ a feedback-based transmission power control algorithm to dynamically maintain individual link quality over time. The intellectual contribution of this work lies in a novel pairwise transmission power control, which is significantly different from existing node-level or network-level power control methods. Also different from most existing simulation work, the ATPC design is guided by extensive field experiments of link quality dynamics at various locations and over a long period of time. The results from the real-world experiments demonstrate that 1) with pairwise adjustment, ATPC achieves more energy savings with a finer tuning capability and 2) with online control, ATPC is robust even with environmental changes over time.

The problem of localization in wireless sensor networks where nodes do not use ranging hardware, remains a challenging problem, when considering the required location accuracy, energy expenditure and the duration of the localization phase. In this paper we propose a framework, called StarDust, for wireless sensor network localization based on passive optical components. In the StarDust framework, sensor nodes are equipped with optical retro-reflectors. An aerial device projects light towards the deployed sensor network, and records an image of the reflected light. An image processing algorithmis developed for obtaining the locations of sensor nodes. For matching a node ID to a location we propose a constraint-based label relaxation algorithm. We propose and develop localization techniques based on four types of constraints: node color, neighbor information, deployment time for a node and deployment location for a node. We evaluate the performance of a localization system based on our framework by localizing a network of 26 sensor nodes deployed in a 120-60ft2 area. The localization accuracy ranges from 2 ft to 5 ft while the localization time ranges from 10 milliseconds to 2 minutes.

Sensor networks open a new frontier for embedded-distributed computing. Paradigms for sensor network programming-in-the-large have been identified as a significant challenge toward developing large-scale applications. Classical programming languages are too low-level. This paper presents the design, implementation, and evaluation of EnviroSuite , a programming framework that introduces a new paradigm, called environmentally immersive programming , to abstract distributed interactions with the environment. Environmentally immersive programming refers to an object-based programming model in which individual objects represent physical elements in the external environment. It allows the programmer to think directly in terms of environmental abstractions. EnviroSuite provides language primitives for environmentally immersive programming that map transparently into a support library of distributed algorithms for tracking and environmental monitoring. We show how nesC code of realistic applications is significantly simplified using EnviroSuite and demonstrate the resulting system performance on Mica2 and XSM platforms.

This article describes one of the major efforts in the sensor network community to build an integrated sensor network system for surveillance missions. The focus of this effort is to acquire and verify information about enemy capabilities and positions of hostile targets. Such missions often involve a high element of risk for human personnel and require a high degree of stealthiness. Hence, the ability to deploy unmanned surveillance missions, by using wireless sensor networks, is of great practical importance for the military. Because of the energy constraints of sensor devices, such systems necessitate an energy-aware design to ensure the longevity of surveillance missions. Solutions proposed recently for this type of system show promising results through simulations. However, the simplified assumptions they make about the system in the simulator often do not hold well in practice, and energy consumption is narrowly accounted for within a single protocol. In this article, we describe the design and implementation of a complete running system, called VigilNet, for energy-efficient surveillance. The VigilNet allows a group of cooperating sensor devices to detect and track the positions of moving vehicles in an energy-efficient and stealthy manner. We evaluate VigilNet middleware components and integrated system extensively on a network of 70 MICA2 motes. Our results show that our surveillance strategy is adaptable and achieves a significant extension of network lifetime. Finally, we share lessons learned in building such an integrated sensor system.

In this article, we investigate the impact of radio irregularity on wireless sensor networks. Radio irregularity is a common phenomenon that arises from multiple factors, such as variance in RF sending power and different path losses, depending on the direction of propagation. From our experiments, we discover that the variance in received signal strength is largely random; however, it exhibits a continuous change with incremental changes in direction. With empirical data obtained from the MICA2 and MICAZ platforms, we establish a radio model for simulation, called the Radio Irregularity Model (RIM). This model is the first to bridge the discrepancy between the spherical radio models used by simulators and the physical reality of radio signals. With this model, we investigate the impact of radio irregularity on several upper layer protocols, including MAC, routing, localization and topology control. Our results show that radio irregularity has a relatively larger impact on the routing layer than the MAC layer. It also shows that radio irregularity leads to larger localization errors and makes it harder to maintain communication connectivity in topology control. To deal with these issues, we present eight solutions to deal with radio irregularity. We evaluate three of them in detail. The results obtained from both the simulations and a running testbed demonstrate that our solutions greatly improve system performance in the presence of radio irregularity.

In wireless sensor networks, many protocols assume that if node A is able to interfere with node B's packet reception, node B is within node A's communication range. It is also assumed that if node B is within node A's communication range, node A is able to interfere with node B's packet reception from any transmitter. While these assumptions may be useful in protocol design, they are not valid, according to the real experiments we conducted in MICA2 platform. For a strong link that has a high packet delivery ratio, the interference range is observed smaller than the communication range, while for a weak link that has a low packet delivery ratio, the interference range is larger than the communication range. So using communication range information alone is not enough to design real collision-free media access control protocols. This paper presents a radio interference detection protocol (RID) and its variation (RID-B) to detect run-time radio interference relations among nodes. The interference detection results are used to design real collision-free TDMA protocols. With extensive simulations in GlomoSim, and with sensor network application scenarios, we observe that the TDMA which uses the interference detection results has 100% packet delivery ratio, while the traditional TDMA has packet loss up to 60%, in heavy load. In addition to the scheduling-based TDMA protocols, we also explore the application of interference detection on contention-based MAC protocols.

Lifetime maximization is one key element in the design of sensor-network-based surveillance applications. We propose a protocol for node sleep scheduling that guarantees a bounded-delay sensing coverage while maximizing network lifetime. Our sleep scheduling ensures that coverage rotates such that each point in the environment is sensed within some finite interval of time, called the detection delay. The framework is optimized for rare event detection and allows favorable compromises to be achieved between event detection delay and lifetime without sacrificing (eventual) coverage for each point. We compare different sleep scheduling policies in terms of average detection delay, and show that ours is closest to the detection delay lower bound for stationary event surveillance. We also explain the inherent relationship between detection delay, which applies to persistent events, and detection probability, which applies to temporary events. Finally, a connectivity maintenance protocol is proposed to minimize the delay of multi-hop delivery to a base-station. The resulting sleep schedule achieves the lowest overall target surveillance delay given constraints on energy consumption.

Battlefield surveillance often involves a high element of risk for military operators. Hence, it is very important for the military to execute unmanned surveillance by using large-scale wireless sensor systems. This invited paper summarizes the architecture of the VigilNet system - a long-term real-time networked sensor system for military surveillance. Specifically, we review the design of several major subsystems within VigilNet including sensing and classification, localization, tracking, networking, power management, reconfiguration, graphic user interface, and the debugging subsystem. High-level programming abstractions are also presented. This is a balanced design to achieve realtime response, high confidence detection, accurate tracking and energy efficiency simultaneously.

A wide variety of sensors have been incorporated into a spectrum of wireless sensor network (WSN) platforms, providing flexible sensing capability over a large number of low-power and inexpensive nodes. Traditional signal processing algorithms, however, often prove too complex for energy-and-cost-effective WSN nodes. This study explores how to design efficient sensing and classification algorithms that achieve reliable sensing performance on energy-and-cost effective hardware without special powerful nodes in a continuously changing physical environment. We present the detection and classification system in a cutting-edge surveillance sensor network, which classifies vehicles, persons, and persons carrying ferrous objects, and tracks these targets with a maximum error in velocity of 15%. Considering the demanding requirements and strict resource constraints, we design a hierarchical classification architecture that naturally distributes sensing and computation tasks at different levels of the system. Such a distribution allows multiple sensors to collaborate on a sensor node, and the detection and classification results to be continuously refined at different levels of the WSN. This design enables reliable detection and classification without involving high-complexity computation, reduces network traffic, and emphasizes resilience and adaptation to the realistic environment. We evaluate the system with performance data collected from outdoor experiments and field assessments. Based on the experience acquired and lessons learned when developing this system, we abstract common issues and introduce several guidelines which can direct future development of detection and classification solutions based on WSNs.

No abstract available.

The problem of localization of wireless sensor nodes has long been regarded as very difficult to solve, when considering the realities of real world environments. In this paper, we formally describe, design, implement and evaluate a novel localization system, called Spotlight. Our system uses the spatio-temporal properties of well controlled events in the network (e.g., light), to obtain the locations of sensor nodes. We demonstrate that a high accuracy in localization can be achieved without the aid of expensive hardware on the sensor nodes, as required by other localization systems. We evaluate the performance of our system in deployments of Mica2 and XSM motes. Through performance evaluations of a real system deployed outdoors, we obtain a 20cm localization error. A sensor network, with any number of nodes, deployed in a 2500m2 area, can be localized in under 10 minutes, using a device that costs less than $1000. To the best of our knowledge, this is the first report of a sub-meter localization error, obtained in an outdoor environment, without equipping the wireless sensor nodes with specialized ranging hardware.

With the proliferation of location dependent applications in sensor networks, location awareness becomes an essential capability of sensor nodes. Because coarse accuracy is sufficient for most sensor network applications, solutions in range-free localization are being pursued as a cost-effective alternative to more expensive range-based approaches. In this paper, we present APIT, a novel localization algorithm that is range-free. We show that our APIT scheme performs best when an irregular radio pattern and random node placement are considered, and low communication overhead is desired. We compare our work, via extensive simulation, with three state-of-the-art range-free localization schemes to identify the preferable system configurations of each. In addition, we provide insight into the impact of localization accuracy on various location dependent applications and suggestions on improving their performance in the presence of such inaccuracy.

In this paper, we present a spatiotemporal communication protocol for sensor networks, called SPEED. SPEED is specifically tailored to be a localized algorithm with minimal control overhead. End-to-end soft real-time communication is achieved by maintaining a desired delivery speed across the sensor network through a novel combination of feedback control and nondeterministic geographic forwarding. SPEED is a highly efficient and scalable protocol for sensor networks where the resources of each node are scarce. Theoretical analysis, simulation experiments, and a real implementation on Berkeley motes are provided to validate the claims.

Distributed sensor networks are quickly gaining recognition as viable embedded computing platforms. Current techniques for programming sensor networks are cumbersome, inflexible, and low-level. We introduce EnviroTrack, an object-based distributed middleware system that raises the level of programming abstraction by providing a convenient and powerful interface to the application developer geared towards tracking the physical environment. EnviroTrack is novel in its seamless integration of objects that live in physical time and space into the computational environment of the application. Performance results demonstrate the ability of the middleware to track realistic targets.

We present the design, implementation and evaluation of a simple, practical and cost effective localization solution, called walking GPS, that can be used in real, manual deployments of wireless sensor networks. We evaluate our localization solution exclusively in real deployments of MICA2 and XSM motes. Our experiments show that 100% of the deployed motes localize (i.e,. have a location position) and that the average localization errors are within 1 to 2 meters, due mainly to the limitations of the existing commercial GPS devices.

Sensor localization has become an essential requirement for realistic applications over wireless sensor networks (WSN). Radio propagation irregularity and the stringent constraint on hardware cost, however, make localization in WSN very challenging. Range-free localizations are more appealing than range-based ones, since they do not depend on received signal strength to estimate distance and thus need simple and cheap hardware only. In this paper, we propose a ring-overlapping, range-free approach using the Ring Overlapping based on Comparison of Received Signal Strength Indicator (ROCRSSI). Simulation results have verified the high estimation accuracy achieved with ROCRSSI.

The focus of surveillance missions is to acquire and verify information about enemy capabilities and positions of hostile targets. Such missions often involve a high element of risk for human personnel and require a high degree of stealthiness. Hence, the ability to deploy unmanned surveillance missions, by using wireless sensor networks, is of great practical importance for the military. Because of the energy constraints of sensor devices, such systems necessitate an energy-aware design to ensure the longevity of surveillance missions. Solutions proposed recently for this type of system show promising results through simulations. However, the simplified assumptions they make about the system in the simulator often do not hold well in practice and energy consumption is narrowly accounted for within a single protocol. In this paper, we describe the design and implementation of a running system for energy-efficient surveillance. The system allows a group of cooperating sensor devices to detect and track the positions of moving vehicles in an energy-efficient and stealthy manner. We can trade off energy-awareness and surveillance performance by adaptively adjusting the sensitivity of the system. We evaluate the performance on a network of 70 MICA2 motes equipped with dual-axis magnetometers. Our results show that our surveillance strategy is adaptable and achieves a significant extension of network lifetime. Finally, we share lessons learned in building such a complete running system.

In this paper, we investigate the impact of radio irregularity on the communication performance in wireless sensor networks. Radio irregularity is a common phenomenon which arises from multiple factors, such as variance in RF sending power and different path losses depending on the direction of propagation. From our experiments, we discover that the variance in received signal strength is largely random; however, it exhibits a continuous change with incremental changes in direction. With empirical data obtained from the MICA2 platform, we establish a radio model for simulation, called the Radio Irregularity Model (RIM). This model is the first to bridge the discrepancy between spherical radio models used by simulators and the physical reality of radio signals. With this model, we are able to analyze the impact of radio irregularity on some of the well-known MAC and routing protocols. Our results show that radio irregularity has a significant impact on routing protocols, but a relatively small impact on MAC protocols. Finally, we propose six solutions to deal with radio irregularity. We evaluate two of them in detail. The results obtained from both the simulation and a running testbed demonstrate that our solutions greatly improve communication performance in the presence of radio irregularity.

No abstract available.

Sensor networks, a novel paradigm in distributed wireless communication technology, have been proposed for various applications including military surveillance and environmental monitoring. These systems deploy heterogeneous collections of sensors capable of observing and reporting on various dynamic properties of their surroundings in a time sensitive manner. Such systems suffer bandwidth, energy, and throughput constraints that limit the quantity of information transferred from end-to-end. These factors coupled with unpredictable traffic patterns and dynamic network topologies make the task of designing optimal protocols for such networks difficult. Mechanisms to perform data-centric aggregation utilizing application-specific knowledge provide a means to augmenting throughput, but have limitations due to their lack of adaptation and reliance on application-specific decisions. We, therefore, propose a novel aggregation scheme that adaptively performs application-independent data aggregation in a time sensitive manner. Our work isolates aggregation decisions into a module that resides between the network and the data-link layer and does not require any modifications to the currently existing MAC and network layer protocols. We take advantage of queuing delay and the broadcast nature of wireless communication to concatenate network units into an aggregate using a novel adaptive feedback scheme to schedule the delivery of this aggregate to the MAC layer for transmission. In our evaluation we show that end-to-end transmission delay is reduced by as much as 80% under heavy traffic loads. Additionally, we show as much as a 50% reduction in transmission energy consumption with an overall reduction in header overhead. Theoretical analysis, simulation, and a test-bed implementation on Berkeley's MICA motes are provided to validate our claims.

In this paper, we present a real-time communication protocol for sensor networks, called SPEED. The protocol provides three types of real-time communication services, namely, real-time unicast, real-time area-multicast and real-time area-anycast. SPEED is specifically tailored to be a stateless, localized algorithm with minimal control overhead End-to-end soft real-time communication is achieved by maintaining a desired delivery speed across the sensor network through a novel combination of feedback control and non-deterministic geographic forwarding. SPEED is a highly efficient and scalable protocol for sensor networks where the resources of each node are scarce. Theoretical analysis, simulation experiments and a real implementation on Berkeley motes are provided to validate our claims.

Wireless Sensor Networks have been proposed for a multitude of location-dependent applications. For such systems, the cost and limitations of hardware on sensing nodes prevent the use of range-based localization schemes that depend on absolute point-to-point distance estimates. Because coarse accuracy is sufficient for most sensor network applications, solutions in range-free localization are being pursued as a cost-effective alternative to more expensive range-based approaches. In this paper, we present APIT, a novel localization algorithm that is range-free. We show that our APIT scheme performs best when an irregular radio pattern and random node placement are considered, and low communication overhead is desired. We compare our work via extensive simulation, with three state-of-the-art range-free localization schemes to identify the preferable system configurations of each. In addition, we study the effect of location error on routing and tracking performance. We show that routing performance and tracking accuracy are not significantly affected by localization error when the error is less than 0.4 times the communication radio radius. 1.

For many sensor network applications such as military surveillance, it is necessary to provide full sensing coverage to a security-sensitive area while at the same time minimizing energy consumption and extending system lifetime by leveraging the redundant deployment of sensor nodes. It is also preferable for the sensor network to provide differentiated surveillance service for various target areas with different degrees of security requirements. In this paper, we propose a differentiated surveillance service for sensor networks based on an adaptable energy-efficient sensing coverage protocol. In the protocol, each node is able to dynamically decide a schedule for itself to guarantee a certain degree of coverage (DOC) with average energy consumption inversely proportional to the node density. Several optimizations and extensions are proposed to provide even better performance. Simulation shows that our protocol accomplishes differentiated surveillance with low energy consumption. It outperforms other state-of-the-art schemes by as much as 50% reduction in energy consumption and as much as 130% increase in the half-life of the network.

Distributed soft real-time systems are becoming increasingly unpredictable due to several important factors such as the increasing use of commercial-off-the-shelf components, the trend towards open systems, and the proliferation of data-driven applications whose execution parameters vary significantly with input data. Such systems are less amenable to traditional worst-case real-time analysis. Instead, system-wide feedback control is needed to meet performance requirements. In this paper, we extend our previous work on developing software control algorithms based on a theory of feedback control to distributed systems. Our approach makes three important contributions. First, it allows the designer for a distributed real-time application to specify the desired temporal behavior of system adaptation, such as the speed of convergence to desired performance upon load or resource changes. This is in contrast to specifying only steady-state metrics, e.g., deadline miss ratio. Second, unlike QoS optimization approaches, our solution meets performance guarantees without accurate knowledge of task execution parameters-a key advantage in an unpredictable environment. Third, in contrast to ad hoc algorithms based on intuition and testing, our solution has a basis in the theory and practice of feedback control scheduling. Performance evaluation reveals that the solution not only has excellent steady state behavior, but also meets stability, overshoot, and settling time requirements. We also show that the solution outperforms several other algorithms available in the literature.