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.

Accurate and pervasive device-free indoor localization with meter-level resolution is critical for large cruise and passenger ships due to safety-critical rescue and evacuation requirements when accidents occur. However, existing localization techniques would severely suffer on ships because of their unique mobility characteristics. In this paper, we take the first attempt to build a ubiquitous passive localization system using WiFi fingerprints for the mobile ship environment. By conducting extensive experiments and measurements during several cruise trips, we identified a major influence factor on the fingerprints in the mobile environment: varying the ship speeds may significantly change the patterns of fingerprints at runtime. Since it may be too expensive to identify the fingerprints associated with different speeds, we propose an efficient localization method, namely SWIM, which calibrates the fingerprints from only a single-speed scenario to multiple-speed scenarios using a signal reconstruction analysis. SWIM is designed to learn the predictive fingerprint variation introduced by environmental speed changes and reconstruct the original fingerprints to adapt to the runtime speed scenarios. We have implemented and extensively evaluated SWIM on actual cruise ships. Experimental results demonstrate that SWIM improves localization accuracy from 63.2 to 82.9 percent, while reducing the overall system deployment cost by 87 percent.

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.

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.

No abstract available.

WiFi-fingerprint localization is recognized as a promising indoor localization technique. However, it suffers from high implementation overhead such as heavy initial training and fingerprint map maintenance overtime. In this paper, we present the design, implementation, and evaluation of AP-Sequence. It is a fingerprint-based localization system that achieves extremely low overhead in fingerprint map construction and maintenance. AP-Sequence achieves this by treating a scan from any reference locations as an input to adjust a large portion of the fingerprint map. The power of AP-Sequence comes from dynamic region partitioning mechanism generating a fingerprint based on relative RSS values. AP-Sequence offers several advantages over existing methods with respect to robustness against environment noises, ability to handle dynamic power control, and mobile device heterogeneity. We have implemented AP-Sequence on an Android platform. Experiment results with over one month of evaluation demonstrate that our design achieves an average localization accuracy of 4-7.6 m over an extended time period with low-overhead in fingerprint map construction and maintenance.

Data mapping among different data standards in health institutes is often a necessity when data exchanges occur among different institutes. However, no matter rule-based approaches or traditional machine learning methods, none of these methods have achieved satisfactory results yet. In this work, we propose a deep learning method, mixture feature embedding convolutional neural network (MfeCNN), to convert the data mapping to a multiple classification problem. Multi-modal features were extracted from different semantic space with a medical NLP package and powerful feature embeddings were generated by MfeCNN. Classes as many as ten were classified simultaneously by a fully-connected soft-max layer based on multi-view embedding. Experimental results show that our proposed MfeCNN achieved best results than traditional state-of-the-art machine learning models and also much better results than the convolutional neural network of only using bag-of-words as inputs.

Imagine a densely packed crowd that gathers to convey a common message, such as people in a candlelight vigil or a protest. We envision an innovation through mobile computing technologies to empower such a crowd by enabling them simply to hold their phones up and create a massive collective visualization on top of them. We propose Card-stunt as a Service (CaaS). CaaS is a service enabling a densely packed crowd to instantly visualize symbols using their mobile devices and a server-side service. The key challenge toward realizing an instant collective visualization is how to achieve instant, infrastructure-free, decimeter-level localization of individuals in a massively packed crowd, while maintaining low latency. CaaS addresses the challenges by mobile visible-light angle-of-arrival (AoA) sensing and scalable constrained optimization. It reconstructs relative locations of all individuals and dispatches individualized timed pixels to each one so that they can do their part in the overall visualization. We evaluate CaaS with extensive experiments under diverse reality settings as well as under synthetic workloads scaling up to tens of thousands of people. We deploy CaaS to 49 participants so that they successfully perform a collective visualization cheering up MobiSys.

Consider a massive crowd who gathered together to convey their common voice to public, e.g., supporters of a team sitting together in a stadium, people doing a candlelight vigil in a public square, and so on. Imagine that they hold up their smartphone displays which collectively compose a huge public screen; the crowd's messages are now shown big on the top of them. We present CaaS [3], a mobile service to realize such an instant, massive, collective visualization with commodity smartphones and cloud services. In this demo, we demonstrate the collective localization feature of CaaS so that the audience can watch a given pattern or symbol collectively displayed on top of arbitrarily positioned phones (See the video demo, https://goo.gl/GfsORc).

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.

Significant research has been devoted to reduce the energy consumption of mobile devices, but how to increase their energy supply has received far less attention. Moreover, reducing the energy consumption alone does not always extend the device operation time due to a unique battery property - the capacity it delivers hinges critically upon how it is discharged. In this paper, we propose B-MODS, a novel design of battery-aware mobile data service on mobile devices. B-MODS constructs battery-friendly discharge patterns utilizing the recovery effect so as to increase the capacity delivered from batteries while meeting data service requirements. We implement B-MODS as an application layer library on the Android platform. Our experiments with diverse mobile devices under various application scenarios have shown that B-MODS increases the capacity delivery from the battery by up to 49.5 percent, with which an increase in the user-perceived data service utilities of up to 28.6 percent is observed.

Passive indoor localization for smartphones requires no explicit cooperation of the smartphone and enables a new spectrum of applications such as passive user tracking, mobility monitoring, social pattern analysis, etc. However, existing passive localization methods either achieve coarse-grained localization accuracy or require expensive infrastructure support. In this paper, we present Pallas, a self-bootstrapping system for fine-grained passive indoor localization using non-intrusive WiFi monitors. Pallas uses off-the-shelf access point hardware to opportunistically capture WiFi packets to infer the location of smartphones in the indoor environment. The key novelty of Pallas lies in that the passive fingerprint database for localization is automatically constructed and updated without any active participation of WiFi devices or manual calibration. To achieve this, Pallas first identifies passive landmarks that are present in WiFi RSS traces. Given the knowledge of the indoor floor plan and the location of WiFi monitors, Pallas statistically maps the collected RSS traces to specific indoor pathways. With sufficient mapping opportunistically detected, Pallas is able to bootstrap a fine-grained passive fingerprint database and build Gaussian processes for localization automatically without requiring any additional calibration effort.

Driven to create intuitive computing interfaces throughout our everyday space, various state-of-the-art technologies have been proposed for near-surface localization of a user's finger input such as hover or touch. However, these works require specialized hardware not commonly available, limiting the adoption of such technologies. We present SymmetriSense, a technology enabling near-surface 3-dimensional fingertip localization above arbitrary glossy surfaces using a single commodity camera device such as a smartphone. SymmetriSense addresses the localization challenges in using a single regular camera by a novel technique utilizing the principle of reflection symmetry and the fingertip's natural reflection casted upon surfaces like mirrors, granite countertops, or televisions. SymmetriSense achieves typical accuracies at sub-centimeter levels in our localization tests with dozens of volunteers and remains accurate under various environmental conditions. We hope SymmetriSense provides a technical foundation on which various everyday near-surface interactivity can be designed.

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.

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.

Multi-tenant datacenters are successful because tenants can seamlessly port their applications and services to the cloud. Virtual Machine (VM) technology plays an integral role in this success by enabling a diverse set of software to be run on a unified underlying framework. This flexibility, however, comes at the cost of dealing with out-dated, inefficient, or misconfigured TCP stacks implemented in the VMs. This paper investigates if administrators can take control of a VM's TCP congestion control algorithm without making changes to the VM or network hardware. We propose AC/DC TCP, a scheme that exerts fine-grained control over arbitrary tenant TCP stacks by enforcing per-flow congestion control in the virtual switch (vSwitch). Our scheme is light-weight, flexible, scalable and can police non-conforming flows. In our evaluation the computational overhead of AC/DC TCP is less than one percentage point and we show implementing an administrator-defined congestion control algorithm in the vSwitch (i.e., DCTCP) closely tracks its native performance, regardless of the VM's TCP stack.

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.

Recent developments in embedded hardware have empowered human experiences through pervasive computing. While embedded systems are becoming more powerful, they still fall short when faced with users' growing desire for running more resource-demanding applications. To bridge this gap, one solution is to leverage powerful resources residing at remote sites by performing computation offloading. Unfortunately, the state-of-the-art offloading frameworks cannot be applied in many embedded systems supporting applications with soft real-time (SRT) constraints or high delay sensitivity, as they typically optimize response times on a "best-effort" basis using heuristics. This paper establishes a soft real-time offloading framework that optimizes the resource utilization of the embedded system while analytically guaranteeing SRT schedulability. The key idea behind the proposed framework is to view offloading-induced delays as suspensions occurring at the local embedded system side, which allows a task being offloaded to be modelled as a suspending task and thus existing SRT suspension-aware scheduling and analysis techniques to be leveraged. Based on this idea, we propose an offloading algorithm, namely Real-time Offloading Decision-making Algorithm (RODA), to make offloading decisions such that SRT schedulability of the task system can be ensured. The optimality properties of RODA have been proved on both uniprocessors and multiprocessors. We conducted extensive simulations on evaluating schedulability and implemented a case study offloading system on top of real hardware to test runtime response time performance. Results demonstrated that RODA is superior to existing performance-driven offloading algorithms, particularly under heavy workloads.

Location based services have experienced an explosive growth and evolved from utilizing a single location to the whole trajectory. Due to the hardware and energy constraints, there are usually many missing data within a trajectory. In order to accurately recover the complete trajectory, crowdsensing provides a promising method. This method resorts to the correlation among multiple users' trajectories and the advanced compressive sensing technique, which significantly outperforms conventional interpolation methods on accuracy. However, as trajectories exposes users' daily activities, the privacy issue is a major concern in crowdsensing. While existing solutions independently tackle the accurate trajectory recovery and privacy issues, yet no single design is able to address these two challenges simultaneously. Therefore in this paper, we propose a novel Privacy Preserving Compressive Sensing (PPCS) scheme, which encrypts a trajectory with several other trajectories while maintaining the homomorphic obfuscation property for compressive sensing. Under PPCS, adversaries can only capture the encrypted data, so the user privacy is preserved. Furthermore, the homomorphic obfuscation property guarantees that the recovery accuracy of PPCS is comparable to the state-of-the-art compressive sensing design. Based on two publicly available traces with numerous users and long durations, we conduct extensive simulations to evaluate PPCS. The results demonstrate that PPCS achieves a high accuracy of9,000 m even when up to 50% original data are missing.

Participatory sensing enables to collect a vast amount of data from the crowd by allowing a wide variety of sources to contribute data. However, the openness of participatory sensing exposes the system to malicious and erroneous participations, inevitably resulting in poor data quality. This brings forth the important issues of false data detection and correction in participatory sensing. Furthermore, data collected by participants normally include considerable missing values, which poses challenges for accurate false data detection. In this work, we propose DECO, a general framework to detect false values for participatory sensing in the presence of missing data. By applying a tailored spatio-temporal compressive sensing technique, DECO is able to accurately detect the false data and estimate both false and missing values for data correction. We validate our design through an experimental case study.

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.

Environment reconstruction is to rebuild the physical environment in the cyberspace using the sensory data collected by sensor networks, which is a fundamental method for human to understand the physical world in depth. A lot of basic scientific work such as nature discovery and organic evolution heavily relies on the environment reconstruction. However, gathering large amount of environmental data costs huge energy and storage space. The shortage of energy and storage resources has become a major problem in sensor networks for environment reconstruction applications. Motivated by exploiting the inherent feature of environmental data, in this paper, we design a novel data gathering protocol based on compressive sensing theory and time series analysis to further improve the resource efficiency. This protocol adapts the duty cycle and sensing probability of every sensor node according to the dynamic environment, which cannot only guarantee the reconstruction accuracy, but also save energy and storage resources. We implement the proposed protocol on a 51-node testbed and conduct the simulations based on three real datasets from Intel Indoor, GreenOrbs and Ocean Sense projects. Both the experiment and simulation performances demonstrate that our method significantly outperforms the conventional methods in terms of resource efficiency and reconstruction accuracy.

In wireless sensor networks, owing to the limited energy of the sensor node, it is very meaningful to propose a dynamic scheduling scheme with data management that reduces energy as soon as possible. However, traditional techniques treat data management as an isolated process on only selected individual nodes. In this article, we propose an aggressive data reduction architecture, which is based on error control within sensor segments and integrates three parallel dynamic control mechanisms. We demonstrate that this architecture not only achieves energy savings but also guarantees the data accuracy specified by the application. Furthermore, based on this architecture, we propose two implementations. The experimental results show that both implementations can raise the energy savings while keeping the error at an predefined and acceptable level. We observed that, compared with the basic implementation, the enhancement implementation achieves a relatively higher data accuracy. Moreover, the enhancement implementation is more suitable for the harsh environmental monitoring applications. Further, when both implementations achieve the same accuracy, the enhancement implementation saves more energy. Extensive experiments on realistic historical soil temperature data confirm the efficacy and efficiency of two implementations.

This paper presents a novel approach to providing a service for electric-vehicle (EV) battery charge replenishment. This is an alternate system in which the charge replenishment is provided by mobile chargers (MCs). These chargers could have two possible configurations: a mobile plug-in charger (MP) or a mobile battery-swapping station (MS). A queuing-based analytical approach is used to determine the appropriate range of design parameters for such a mobile charging system. An analytical analysis is first developed for an idealized system with a nearest-job-next (NJN) service strategy explored for such a system. In a NJN service strategy, the MC services the next spatially closest EV when it is finished with its current request. An urban environment approximated by Singapore is then analyzed through simulation. Charging requests are simulated through a trip generation model based on Singapore. In such a realistic environment, an updated practical NJN service strategy is proposed. For an MP system in an urban environment such as Singapore, there exists an optimal battery capacity with a threshold battery charge rate. Similarly, the battery swap capacity of an MS system does not need to be large for the system to perform.

Recently, adopting mobile energy chargers to replenish the energy supply of sensor nodes in wireless sensor networks has gained increasing attention from the research community. Different from energy harvesting systems, the utilization of mobile energy chargers is able to provide more reliable energy supply than the dynamic energy harvested from the surrounding environment. While pioneering works on the mobile recharging problem mainly focus on the optimal offline path planning for the mobile chargers, in this work, we aim to lay the theoretical foundation for the on-demand mobile charging (DMC) problem, where individual sensor nodes request charging from the mobile charger when their energy runs low. Specifically, in this work, we analyze the on-demand mobile charging problem using a simple but efficient Nearest-Job-Next with Preemption (NJNP) discipline for the mobile charger, and provide analytical results on the system throughput and charging latency from the perspectives of the mobile charger and individual sensor nodes, respectively. To demonstrate how the actual system design can benefit from our analytical results, we present two examples on determining the essential system parameters such as the optimal remaining energy level for individual sensor nodes to send out their recharging requests and the minimal energy capacity required for the mobile charger. Through extensive simulation with real-world system settings, we verify that our analytical results match the simulation results well and the system designs based on our analysis are effective.

We study the Relay-based Cooperative Data Exchange (RCDE) problem, where initially each client has access to a subset of a set of n original packets, referred to as their side information, and wants to retrieve all other original packets via cooperation. Unlike traditional Cooperative Data Exchange (CDE), in our proposed relay-based model, clients can only cooperate via a relay. The data exchange is completed over two phases, namely Uploading Phase and Downloading Phase. In the Uploading Phase, the clients will encode the original packets and transmit the coded packets to the relay. In the Downloading Phase, the relay will reencode the received packets and multicast the reencoded packets, each to a subgroup of clients. The coded packets in the two phases are carefully selected so that each client can retrieve all n original packets with minimum total transmission delay, based on its initial side information and on the coded packets it receives from the relay. In addition, we assume that the bandwidths between the relay and different clients are different, and that the upload/download bandwidths between the relay and the same client are also different. We establish a coding scheme that has the minimum total delay and show that it can be found in polynomial time, for sufficiently large underlying fields. We also design a heuristic algorithm that has a low complexity with binary field size. Our simulations show that the performance of the binary solution is very close to that of the optimal solution. All coding schemes considered in this work are scalar.

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.

Data collection is a crucial operation in wireless sensor networks. The design of data collection schemes is challenging due to the limited energy supply and the hot spot problem. Leveraging empirical observations that sensory data possess strong spatiotemporal compressibility, this paper proposes a novel compressive data collection scheme for wireless sensor networks. We adopt a power-law decaying data model verified by real data sets and then propose a random projection-based estimation algorithm for this data model. Our scheme requires fewer compressed measurements, thus greatly reduces the energy consumption. It allows simple routing strategy without much computation and control overheads, which leads to strong robustness in practical applications. Analytically, we prove that it achieves the optimal estimation error bound. Evaluations on real data sets (from the GreenOrbs, IntelLab and NBDC-CTD projects) show that compared with existing approaches, this new scheme prolongs the network lifetime by 1.5X to 2X for estimation error 5-20 percent.

To reduce peak demand, many utility companies are transitioning from fixed rate pricing plans to real-time pricing plans. To apply real-time pricing plans, it is crucial to collect accurate real-time power consumption readings from individual homes. Thus, utility companies are increasing the installation of smart meters in individual homes. Smart meters can record energy related data (e.g., power consumption) every second. However, power consumption data with high time granularity needs huge data storage space and generates significant communication overhead for utility companies to gather all the data for the pricing plans. In this paper, we present E-Sketch, a middleware for utility companies to gather data from smart meters with much less storage and communication overhead. E-Sketch utilizes adaptive sampling to compress power consumption changes in time domain. Then frequency compression is applied to further compress the sampled data. We conducted extensive system evaluations with 30 homes' second-level power consumption data for more than 2 months. Results indicate i) our design can reduce data storage space significantly by 90% with more than 99% accuracy of second-level power consumption on average for a single home, and ii) our design can achieve even more than 99.8% accuracy on average for aggregated power consumption of 30 homes.

In many real-time systems, tasks may experience suspension delays when they block to access shared resources or interact with external devices such as I/O. It is known that such suspensions delays may negatively impact schedulability. Particularly in hard real-time systems, a few negative results exist on analyzing the schedulability of such systems, even for very restricted suspending task models on a uniprocessor. In this paper, we focus on the particular case of hard real-time suspending task systems with harmonic periods, which is a special case of practical relevance. We propose a new uniprocessor suspension-aware analysis technique for supporting such task systems under rate-monotonic scheduling. Our analysis technique is able to achieve only Theta(1) suspension-related utilization loss on a uniprocessor. Based upon this technique, we further propose a partitioning scheme that supports suspending task systems with harmonic periods on multiprocessors. The resulting schedulability test shows that compared to existing schedulability tests designed for ordinary non-suspending task systems, suspensions only results in Theta(m) additional suspension-related utilization loss, where m is the number of processors. Furthermore, experiments presented herein show that both our uniprocessor and multiprocessor schedulability tests improve upon prior approaches by a significant margin.

In wireless rechargeable sensor networks (WRSN), rechargeable sensor nodes harvest ambient RF energy from power sources such as the RFID readers. However, the simultaneous transmissions may cause severe communication collisions. Different from traditional approaches which mainly resolve such collisions at the MAC layer, in this work we optimize the deployment of RFID reader in order to avoid the communication collisions by exploiting the differences in the time of charge among rechargeable sensor nodes. Specifically, when the reader is able to cover the whole deployment field, an efficient collision-free solution with proved optimality is presented to minimize the communication delay in the network. Simulation results are employed to verify the proposed algorithm.

Proliferation of mobile phones over the last decade has led to innovative methods for studying social behavior and friendship patterns. Our present study combined advanced mobile phone technologies, such as Bluetooth scanning and automated pushing surveys, with self-reported questionnaires to examine the social structure and psychological well-being of college students. We distributed smartphones to 35 first-year undergraduate students to use everyday over one academic term (three months) and asked them to complete questionnaires on language background, loneliness, adaptation to college life, feelings of community cohesion, and friendship ties. Results suggested that behavioral networks in physical co-location, obtained using our mobile phone sensing techniques, reliably inferred real reported friendships. In addition, mobile phone usage, such as calling and SMS, were significantly correlated with psychological well-being in terms of feelings of loneliness, sense of community cohesion and adaptation to college life. Finally, results revealed that activities in the mobile phone social network, in particular SMS, may influence students' language use, such that students tended to adapt their language behavior to match that of their SMS partners.

Link correlation in wireless sensor networks has recently attracted a considerable amount of attention in the research community. Various pioneer works have empirically demonstrated the existence of link correlations and designed novel network protocols to exploit such link correlations. While all existing works focus on the correlated receptions at multiple receivers from a single sender, in this work we empirically demonstrate another type of link correlation, called sender-based link correlation. For sender-based link correlation, we observe wireless links from multiple senders to a single receiver are also correlated. Based on this observation, we design a two-tiered data forwarding scheme for improving the energy efficiency of unicast in the network. At the micro-level, individual nodes reduce their transmission energy consumption by temporarily switching to a new forwarder or suppressing the current transmission with the knowledge of link correlations. At the macro-level, we schedule the ordering of transmission times among neigh boring nodes so that the gains from all link correlation information in the network is maximized. Through trace-driven emulations and large scale simulations, we demonstrate that our design reduces data retransmissions by an average of 12% when compared with already highly energy efficient ETX-based protocols.

Recently, much research effort has been devoted to employing mobile chargers for energy replenishment of the robots in robotic sensor networks. Observing the discrepancy between the charging latency of robots and charger travel distance, we propose a novel tree-based charging schedule for the charger, which minimizes its travel distance without causing the robot energy depletion. We analytically evaluate its performance and show its closeness to the optimal solutions. Furthermore, through a queue-based approach, we provide theoretical guidance on the setting of the remaining energy threshold at which the robots request energy replenishment. This guided setting guarantees the feasibility of the tree-based schedule to return a depletion-free charging schedule. The performance of the tree-based charging schedule is evaluated through extensive simulations. The results show that the charger travel distance can be reduced by around 20%, when compared with the schedule that only considers the robot charging latency.

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.

Different from energy harvesting which generates dynamic energy supplies, the mobile charger is able to provide stable and reliable energy supply for sensor nodes, and thus enables sustainable system operations. While previous mobile charging protocols either focus on the charger travel distance or the charging delay of sensor nodes, in this work we propose a novel Energy Synchronized Charging (ESync) protocol, which simultaneously reduces both of them. Observing the limitation of the Traveling Salesman Problem (TSP)-based solutions when nodes energy consumptions are diverse, we construct a set of nested TSP tours based on their energy consumption rates, and only nodes with low remaining energy are involved in each charging round. Furthermore, we propose the concept of energy synchronization to synchronize the charging requests sequence of nodes with their sequence on the TSP tours.

Different from energy harvesting which generates dynamic energy supplies, the mobile charger is able to provide stable and reliable energy supply for sensor nodes, and thus enables sustainable system operations. While previous mobile charging protocols either focus on the charger travel distance or the charging delay of sensor nodes, in this work we propose a novel Energy Synchronized Charging (ESync) protocol, which simultaneously reduces both of them. Observing the limitation of the Traveling Salesman Problem (TSP)-based solutions when nodes energy consumptions are diverse, we construct a set of nested TSP tours based on their energy consumptions, and only nodes with low remaining energy are involved in each charging round. Furthermore, we propose the concept of energy synchronization to synchronize the charging re- quests sequence of nodes with their sequence on the TSP tours. Experiment and simulation demonstrate ESync can reduce charger travel distance and nodes charging delay by about 30% and 40% respectively.

The Wireless Identification and Sensing Platform (WISP) has become a very promising experimental platform of wireless rechargeable sensor networks (WRSN), which integrates the sensing and computation capabilities to the traditional RFID tags. In such kind of networks, the simultaneous transmission may introduce severe communication collisions, which have attracted various research efforts for resolving such collisions at the MAC layer. However, different from existing works, we avoid such communication collisions through proper reader movement by exploiting the differences in the time of charge among rechargeable sensor nodes. We formulate the optimization problem and prove that complexity of the optimal solution is NP-hard, and propose a simple yet effective algorithm to optimize both the reader stop location and stop time for minimizing the total communication delay. Extensive simulation under different system settings show that our design can largely reduce the communication delay and outperform the baseline design by at least 20%.

Smartphones and mobile devices have greatly penetrated the daily lives of many people. While participatory/pervasive sensing has gained wide adoptions by leveraging various onboard sensors on mobile devices, another powerful resource, the computational power on these mobile devices has been less frequently harnessed by researchers and practitioners. To fill this gap, we propose in this work the modeling, analysis, and implementation of participatory computing. Specifically, we propose REPC, a generic randomized task assignment framework for the participatory computing paradigm, which guarantees the overall system performance with close to minimal workload at individual participating devices. To achieve these design objectives, we model the intrinsic relationship between the workload of individual devices and the probability they complete their assigned tasks. Based on our modeling results, we analyze the maximal system capacity for any given participatory computing system and derive the minimal workload for individual participating devices to achieve the overall system performance requirement. We have fully implemented our design on the Android platform and demonstrated its performance through a representative participatory computing application. Extensive experiments and simulation results demonstrate that our design is able to achieve more than 90% task completion ratios with only 10% system overhead in practice.

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.

Providing reliable and efficient communication under fading channels is one of the major technical challenges in wireless sensor networks (WSNs), especially in industrial WSNs (IWSNs) with dynamic and harsh environments. In this work, we present the Reliable Reactive Routing Enhancement (R3E) to increase the resilience to link dynamics for WSNs/IWSNs. R3E is designed to enhance existing reactive routing protocols to provide reliable and energy-efficient packet delivery against the unreliable wireless links by utilizing the local path diversity. Specifically, we introduce a biased backoff scheme during the route-discovery phase to find a robust guide path, which can provide more cooperative forwarding opportunities. Along this guide path, data packets are greedily progressed toward the destination through nodes' cooperation without utilizing the location information. Through extensive simulations, we demonstrate that compared to other protocols, R3E remarkably improves the packet delivery ratio, while maintaining high energy efficiency and low delivery latency.

Mobility-assisted data collection in sensor networks creates a new dimension to reduce and balance the energy consumption for sensor nodes. However, it also introduces extra latency in the data collection process due to the limited mobility of mobile elements. Therefore, how to schedule the movement of mobile elements throughout the field is of ultimate importance. In this paper, the on-demand scenario where data collection requests arrive at the mobile element progressively is investigated, and the data collection process is modelled as an$M/G/1/c$-$NJN$queuing system with an intuitive service discipline of nearest-job-next (NJN). Based on this model, the performance of data collection is evaluated through both theoretical analysis and extensive simulation. NJN is further extended by considering the possible requests combination (NJNC). The simulation results validate our models and offer more insights when compared with the first-come-first-serve (FCFS) discipline. In contrary to the conventional wisdom of the starvation problem, we reveal that NJN and NJNC have better performance than FCFS, in both the average and more importantly the worst cases, which offers the much needed assurance to adopt NJN and NJNC in the design of more sophisticated data collection schemes, as well as other similar scheduling scenarios.

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.

QoS routing is an important research issue in wireless sensor networks (WSNs), especially for mission-critical monitoring and surveillance systems which requires timely and reliable data delivery. Existing work exploits multipath routing to guarantee both reliability and delay QoS constraints in WSNs. However, the multipath routing approach suffers from a significant energy cost. In this work, we exploit the geographic opportunistic routing (GOR) for QoS provisioning with both end-to-end reliability and delay constraints in WSNs. Existing GOR protocols are not efficient for QoS provisioning in WSNs, in terms of the energy efficiency and computation delay at each hop. To improve the efficiency of QoS routing in WSNs, we define the problem of efficient GOR for multiconstrained QoS provisioning in WSNs, which can be formulated as a multiobjective multiconstraint optimization problem. Based on the analysis and observations of different routing metrics in GOR, we then propose an Efficient QoS-aware GOR (EQGOR) protocol for QoS provisioning in WSNs. EQGOR selects and prioritizes the forwarding candidate set in an efficient manner, which is suitable for WSNs in respect of energy efficiency, latency, and time complexity. We comprehensively evaluate EQGOR by comparing it with the multipath routing approach and other baseline protocols through ns-2 simulation and evaluate its time complexity through measurement on the MicaZ node. Evaluation results demonstrate the effectiveness of the GOR approach for QoS provisioning in WSNs. EQGOR significantly improves both the end-to-end energy efficiency and latency, and it is characterized by the low time complexity.

Reconstructing the environment by sensory data is a fundamental operation for understanding the physical world in depth. A lot of basic scientific work (e.g., nature discovery, organic evolution) heavily relies on the accuracy of environment reconstruction. However, data loss in wireless sensor networks is common and has its special patterns due to noise, collision, unreliable link, and unexpected damage, which greatly reduces the reconstruction accuracy. Existing interpolation methods do not consider these patterns and thus fail to provide a satisfactory accuracy when the missing data rate becomes large. To address this problem, this paper proposes a novel approach based on compressive sensing to reconstruct the massive missing data. Firstly, we analyze the real sensory data from Intel Indoor, GreenOrbs, and Ocean Sense projects. They all exhibit the features of low-rank structure, spatial similarity, temporal stability and multi-attribute correlation. Motivated by these observations, we then develop an environmental space time improved compressive sensing (ESTI-CS) algorithm with a multi-attribute assistant (MAA) component for data reconstruction. Finally, extensive simulation results on real sensory datasets show that the proposed approach significantly outperforms existing solutions in terms of reconstruction accuracy.

Access card authentication is critical and essential for many modern access control systems, which have been widely deployed in various government, commercial, and residential environments. However, due to the static identification information exchange among the access cards and access control clients, it is very challenging to fight against access control system breaches due to reasons such as loss, stolen or unauthorized duplications of the access cards. Although advanced biometric authentication methods such as fingerprint and iris identification can further identify the user who is requesting authorization, they incur high system costs and access privileges cannot be transferred among trusted users. In this work, we introduce a dynamic authentication with sensory information for the access control systems. By combining sensory information obtained from onboard sensors on the access cards as well as the original encoded identification information, we are able to effectively tackle the problems such as access card loss, stolen, and duplication. Our solution is backward-compatible with existing access control systems and significantly increases the key spaces for authentication. We theoretically demonstrate the potential key space increases with sensory information of different sensors and empirically demonstrate simple rotations can increase key space by more than 1,000,000 times with an authentication accuracy of 90 percent. We performed extensive simulations under various environment settings and implemented our design on WISP to experimentally verify the system performance.

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.

In wireless sensor networks (WSNs), since many basic scientific works heavily rely on the complete sensory data, data recovery is an indispensable operation against the data loss. Several works have studied the missing value problem. However, existing solutions cannot achieve satisfactory accuracy due to special loss patterns and high loss rates in WSNs. In this work, we propose a multiple attributes-based recovery algorithm which can provide high accuracy. Firstly, based on two real datasets, the Intel Indoor project and the GreenOrbs project, we reveal that such correlations are strong, e.g., the change of temperature and light illumination usually has strong correlation. Secondly, motivated by this observation, we develop a Multi-Attribute-assistant Compressive-Sensing-based (MACS) algorithm to optimize the recovery accuracy. Finally, real trace-driven simulation is performed. The results show that MACS outperforms the existing solutions. Typically, MACS can recover all data with less than 5% error when the loss rate is less than 60%. Even when losing 85% data, all missing data can be estimated by MACS with less than 10% error.

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).

Recently, adopting mobile energy chargers to replenish the energy supply of sensor nodes in wireless sensor networks has gained increasing attention from the research community. The utilization of the mobile energy chargers provides a more reliable energy supply than the systems that harvested dynamic energy from the surrounding environment. While pioneering works on the mobile recharging problem mainly focus on the optimal offline path planning for the mobile chargers, in this work, we aim to lay the theoretical foundation for the on-demand mobile charging problem, where individual sensor nodes request charging from the mobile charger when their energy runs low. Specifically, in this work we analyze the on-demand mobile charging problem using a simple but efficient Nearest-Job-Next with Preemption (NJNP) discipline for the mobile charger, and provide analytical results on the system throughput and charging latency from the perspectives of the mobile charger and individual sensor nodes, respectively. To demonstrate how the actual system design can benefit from our analytical results, we present an example on determining the optimal remaining energy level for individual sensor nodes to send out their recharging requests. Through extensive simulation with real-world system settings, we verify our analysis matches the simulation results well and the system designs based on our analysis are effective.

Energy constraint is a critical hurdle hindering the practical deployment of long-term wireless sensor network applications. Turning off (that is, duty cycling) sensors could reduce energy consumption, however, this would occur at the cost of low sensing fidelity due to sensing gaps introduced. Existing techniques focus mainly on scheduling a network with static anchors. Few methods provides a rigorous approach to confining sensing errors within desirable bounds while seeking to optimize the tradeoff between energy consumption and accuracy of predictions. In this work, we propose a sensing scheduling scheme, called MAS, to support mobile anchors in sensor networks. Within a node, we use a sensing probability bound to control tolerable sensing errors. While communicating with the mobile anchor, nodes trigger additional sensing activities to accommodate the QoS requirement in mobile communication. We validated the concept by constructing a lab-grade mobile anchor that fully supports 4G-LTE communications for monitoring applications. We further conducted simulations to investigate system performance. The simulation results demonstrated that the MAS achieved enhancement performance compared to several other sensing schemes.

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.

Participatory Computing is a promising solution to fully utilize the wasted computation resources of mobile devices such as smartphones. In this demo abstract, we present our design and implementation of an participatory computing enhanced pervasive surveillance system. Our evaluation results show that the proposed system can effectively utilize the computation capability of mobile devices while guaranteeing the service reliability even with the intermittent nature of participatory computing.

Location-based services, such as targeted advertisement, geo-social networking and emergency services, are becoming increasingly popular for mobile applications. While GPS provides accurate outdoor locations, accurate indoor localization schemes still require either additional infrastructure support (e.g., ranging devices) or extensive training before system deployment (e.g., WiFi signal fingerprinting). In order to help existing localization systems to overcome their limitations or to further improve their accuracy, we propose Social-Loc, a middleware that takes the potential locations for individual users, which is estimated by any underlying indoor localization system as input and exploits both social encounter and non-encounter events to cooperatively calibrate the estimation errors. We have fully implemented Social-Loc on the Android platform and demonstrated its performance on two underlying indoor localization systems: Dead-reckoning and WiFi fingerprint. Experiment results show that Social-Loc improves user's localization accuracy of WiFi fingerprint and dead-reckoning by at least 22% and 37%, respectively. Large-scale simulation results indicate Social-Loc is scalable, provides good accuracy for a long duration of time, and is robust against measurement errors.

A tree-based topology is often used to flood packets from the sink node in wireless sensor networks (WSNs). Therefore, flooding tree construction is an important and fundamental problem in WSNs, and has been extensively investigated in the literature. However, we note that the flooding tree construction problem in asynchronous low-duty-cycle WSNs has not been sufficiently investigated in existing work. In this work, we focus our investigation on minimum-delay and energy-efficient flooding tree construction considering the duty-cycle operation and unreliable wireless links. We formulate the problem as a undetermined-delay-constrained minimum spanning tree (UDC-MST) problem, where the delay constraint is known a posteriori. We design a distributed heuristic algorithm, named MDET, to solve the problem. Through extensive simulations, we demonstrate that MDET achieves a very good balance between flooding delay and energy efficiency.

Indoor localization is essential to enable location-based services in wireless pervasive computing environment. In recent years, WiFi fingerprint-based localization has received considerable attention due to its deployment practicability. In order to achieve on-the-fly localization, WiFi receivers (e.g., mobile phones or laptops) being located need to scan WiFi signals continuously. Since they are normally battery driven, energy efficiency is a very important consideration in WiFi fingerprinting localization systems. Motivated by the fact that IEEE 802.11 (WiFi) and 802.15.4 (ZigBee) channels overlap in the 2.4GHz ISM band, in this work, we develop a WiFi fingerprint-based localization system using ZigBee radio, called ZiLoc. We first present a novel RSS-location fingerprint model to identify the features of surrounding APs. We then propose a simple yet effective method to compute the similarity of two RSS fingerprints. Experimental results demonstrate that ZiLoc can achieve an average of 85% room-level localization accuracy and reduce more than 60% energy consumption compared with the method using WiFi interfaces to collect RSS fingerprints.

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.

Wireless Rechargeable Sensor Network (WRSN) is an emerging technology to address the energy constraint in sensor networks. The protocol design in WRSN is extremely challenging due to the complicated interactions between rechargeable sensor nodes and readers, capable of mobility and functioning as energy distributors and data collectors. In this paper, we for the first time investigate the optimal scheduling problem in WRSN for stochastic event capture, i.e., how to jointly mobilize the readers for energy distribution and schedule sensor nodes for optimal quality of monitoring (QoM). We analyze the QoM for three application scenarios: i) the reader travels at a fixed speed to recharge sensor nodes and sensor nodes consume the collected energy in an aggressive way, ii) the reader stops to recharge sensor nodes for a predefined time during its periodic traveling and sensor nodes deplete energy aggressively, iii) the reader stops to recharge sensor nodes but sensor nodes can adopt optimal duty cycle scheduling for maximal QoM. We provide analytical results for achieving the optimal QoM under arbitrary parameter settings. Extensive simulation results are offered to demonstrate the correctness and effectiveness of our results.

Due to the limited power constraint in sensors, dynamic scheduling with data quality management is strongly preferred in long lifetime monitoring applications. But typical techniques treat data management as an isolated process on only selected individual nodes, e.g. the centroid node. In this paper, we propose and evaluate an aggressive data reduction algorithm based on error inference within sensor segments. The architecture integrates three parallel dynamic error control mechanisms to optimize the trade-off between energy saving and data validity. We demonstrate that not only substantial energy savings can be achieved but also that an error bound specified by the application can be guaranteed. Moreover, we have investigate the system performance by using the realistic historical soil temperature data as an experimental context. The experimental results demonstrate that the system error meets the specified error tolerance and produces up to a 50 percent of the energy savings compared to several sensing schemes.

An interactive and programmable musical yo-yo system is designed. The aim of it is to demonstrate the feasibility of converting any sensor-enabled objects into potential musical instruments. This involves three design phases. First, the physical yo-yo is designed to house Iris sensors. The software is developed to sense the movement of yo-yo and transmit its measurements to Max/MSP for corresponding music generation. Finally, aurally pleasing and real-time musical sounds are designed and generated in effect of yo-yo by the computer music composer.

Access card authentication is critical and essential for many modern access control systems, which have been widely deployed in various government, commercial and residential environments. However, due to the static identification information exchange among the access cards and access control clients, it is very challenging to fight against access control system breaches due to reasons such as loss, stolen or unauthorized duplications of the access cards. Although advanced biometric authentication methods such as fingerprint and iris identification can further identify the user who is requesting authorization, they incur high system costs and access privileges can not be transferred among trusted users. In this work, we introduce a sensory-data-enhanced authentication for access control systems. By combining sensory-data obtained from onboard sensors on the access cards as well as the original encoded identification information, we are able to effectively tackle the problems such as access card loss and stolen. Our solution is backward-compatible with existing access control systems and significantly increases the key spaces for authentication. We theoretically demonstrate the potential key space increases with simple sensor data and empirically demonstrate simple rotations can increase key space by more than 30, 000 times with an authentication accuracy of 95%. We performed extensive simulations under various environment settings and implemented our design on WISP to experimentally verify the system performance.

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.

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.

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.

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.

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.

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.

In this demonstration, a systematically domain-specific model checker, NesC@PAT, is presented. The tool takes NesC programs as input, and automatically verifies WSNs against properties specified in the form of deadlock freeness, state reachability or linear temporal logic formulas. We will show that NesC@PAT is able to find errors caused by rarely unexpected scenarios, which are difficult to be detected by general simulating or debugging.

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.

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.

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.

Stream processing is widely used by today's applications such as financial data analysis and disaster response. In distributed stream processing systems, machine fail-stop events are handled by either active standby or passive standby. However, existing high availability (HA) schemes have not sufficiently addressed the situation when a machine becomes temporarily unavailable due to data rate spikes, intensive analysis or job sharing, which happens frequently but lasts for short time. It is not clear how well active and passive standby fare against such transient unavailability. In this paper, we first critically examine the suitability of active and passive standby against transient unavailability in a real testbed environment. We find that both approaches have advantages and drawbacks, but neither is ideal to provide fast recovery at low overhead as required to handle transient unavailability. Based on the insights gained, we propose a novel hybrid HA method that switches between active and passive standby modes depending on the occurrence of failure events. It presents a desirable tradeoff that is different from existing HA approaches: low overhead during normal conditions and fast recovery upon transient or permanent failure events. We have implemented our hybrid method and compared it with existing HA designs with comprehensive evaluation. The results show that our hybrid method can reduce two-thirds of the recovery time compared to passive standby and 80% message overhead compared to active standby, allowing applications to enjoy uninterrupted processing without paying a high premium.

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.

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.

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.

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.

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.

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 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.

No abstract available.