We study the Patrol Security Game (PSG), a robotic patrolling problem formulated as an extensive-form Stackelberg game, in which the attacker strategically selects the timing, location, and duration of an attack. The defender’s goal is to compute an infinite-horizon patrolling policy that minimizes the attacker’s expected payoff. By restricting the defender’s strategy to a time-homogeneous first-order Markov chain, we show that PSG can be reformulated as a combinatorial minimax problem. We prove that the optimal strategy under zero-penalty scenarios corresponds to minimizing either the expected hitting time or return time, depending on the attacker’s visibility model. These optimal policies are closed-form and can be computed efficiently. On the other hand, in high-penalty cases, we observe that the patrolling schedule with high randomness can minimize the attacker’s expected gain. However, in general, the minimax objective becomes non-convex. To address this, we introduce a bi-criteria optimization framework that jointly considers the expected maximum reward (EMR) and entropy rate of the patrolling policy. We propose three graph-based algorithms and a deep reinforcement learning model to efficiently balance these two objectives. Each algorithm demonstrates distinct strengths under different configurations, such as varying penalty scales and cost function settings. The extensive experiments on both synthetic and real-world crime datasets validate the effectiveness of our approaches, demonstrating superior performance and scalability compared to state-of-the-art baselines.

Alzheimer's Disease (AD) has become an increasingly critical global health concern, which necessitates effective monitoring solutions in smart health applications. However, the development of such solutions is significantly hindered by the scarcity of AD-specific activity datasets. To address this challenge, we propose SHADE-AD, a Large Language Model (LLM) framework for Synthesizing Human Activity Datasets Embedded with AD features. Leveraging both public datasets and our own collected data from 99 AD patients, SHADE-AD synthesizes human activity videos that specifically represent AD-related behaviors. By employing a three-stage training mechanism, it broadens the range of activities beyond those collected from limited deployment settings. We conducted comprehensive evaluations of the generated dataset, demonstrating significant improvements in downstream tasks such as Human Activity Recognition (HAR) detection, with enhancements of up to 79.69%. Detailed motion metrics between real and synthetic data show strong alignment, validating the realism and utility of the synthesized dataset. These results underscore SHADE-AD's potential to advance smart health applications by providing a cost-effective, privacy-preserving solution for AD monitoring.

As electric vehicles (EVs) gradually replace fuel vehicles and provide transportation services in cities, e.g., electric taxi fleets, solar-powered charging stations with energy storage systems have been deployed to provide charging services for EV fleets. The mixture of solar-powered and traditional charging stations brings efficiency challenges to charging stations and reliability challenges to power systems. In this article, we explore e-taxis’ mobility and charging demand flexibility to co-optimize service quality of e-taxi fleets and system cost of charging infrastructures, e.g., solar power under-utilization and reliability issues of power distribution networks due to reverse power flow. We propose SAC, an e-taxi coordination framework to dispatch e-taxis for charging or serving passengers under spatial-temporal dynamics of renewable energy and passenger mobility, which integrates the renewable power generation estimation from a forecast system. Moreover, we extend our design to a stochastic Model Predictive Control problem to handle the uncertainty of solar power generation, aiming to fully utilize generated solar power. Our data-driven evaluation shows that SAC significantly outperforms existing solutions, enhancing the usage rate of solar power by up to 172.6%, while maintaining e-taxi service quality with very small overhead, i.e., reducing the supply-demand ratio by 2.2%.

Signal Temporal Logic (STL) is a widely adopted specification language for Cyber-Physical Systems that can be used to express critical temporal requirements, such as system safety and response time. STL’s expressivity, however, is not sufficient to capture the cumulative duration during which a property holds within an interval of time. To overcome this limitation, we introduce Cumulative-Time Signal Temporal Logic (CT-STL) which operates over discrete-time signals and extends STL with a new cumulative-time operator. This operator compares the sum of all timesteps for which its nested formula is true with a threshold. We present both a qualitative and a quantitative (robustness) semantics for CT-STL and prove the soundness and completeness of the robustness semantics. We also provide an efficient online monitoring algorithm for both semantics. We demonstrate the utility of CT-STL via two case studies: specifying and monitoring cumulative temporal requirements for a microgrid and an artificial pancreas.

We present ResilienC, a framework for resilient control of Cyber-Physical Systems subject to STL-based requirements. ResilienC utilizes a recently developed formalism for specifying CPS resiliency in terms of sets of (rec, dur) real-valued pairs, where rec represents the system’s capability to rapidly recover from a property violation (recoverability), and dur is reflective of its ability to avoid violations post-recovery (durability). We define the resilient STL control problem as one of multi-objective optimization, where the recoverability and durability of the desired STL specification are maximized. When neither objective is prioritized over the other, the solution to the problem is a set of Pareto-optimal system trajectories. We present a precise solution method to the resilient STL control problem using a mixed-integer linear programming encoding and an a posteriori ϵ -constraint approach for efficiently retrieving the complete set of optimally resilient solutions. In ResilienC, at each time-step, the optimal control action selected from the set of Pareto-optimal solutions by a Decision Maker strategy realizes a form of Model Predictive Control. We demonstrate the practical utility of the ResilienC framework on two significant case studies: autonomous vehicle lane keeping and deadline-driven, multi-region package delivery.

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

With increasing deployment of electric vehicles in urban mobility-on-demand systems, electric taxis (e-taxi) drivers need to compete with each other not only for passengers but also for limited charging points due to frequent and time-consuming charging activities. This paper focuses on two crucial research questions in this context: (1) What is the strategy of each e-taxi driver for charging and searching passengers in a non-cooperative environment, and what is the collective system outcome of competing e-taxis? (2) How can the mobility-on-demand service platforms (e.g., Uber and Lyft) push self-interested e-taxi drivers to improve the overall system efficiency. Technically, we study the non-cooperative mobility-on-demand system consisting of e-taxis from a game theoretic perspective. We formulate a mobility-on-demand system with competition among drivers as a stochastic game, analyze the Nash Equilibrium (NE) of the game, and design an approximation algorithm to obtain the NE. Moreover, we show that the NE is not necessarily efficient for the platform and propose a pricing scheme from the platform's perspective which induces the new NE to be efficient. We use a trace-driven simulation to evaluate the design based on datasets consisting of more than 7,000 fuel vehicles and nearly 700 e-taxis, 37 working charging stations, and more than 60,000 passenger trips per day. We show that, compared with the state-of-the-art which optimizes the system efficiency by coordinating e-taxis but is not an equilibrium, the NE achieves a system efficiency of merely 73.5% of that of the cooperative state-of-the-art, and the designed pricing scheme improves the price of anarchy to 95.5 %.

As various smart services are increasingly deployed in modern cities, many unexpected conflicts arise due to various physical world couplings. Existing solutions for conflict resolution often rely on centralized control to enforce predetermined and fixed priorities of different services, which is challenging due to the inconsistent and private objectives of the services. Also, the centralized solutions miss opportunities to more effectively resolve conflicts according to their spatiotemporal locality of the conflicts. To address this issue, we design a decentralized negotiation and conflict resolution framework named DeResolver, which allows services to resolve conflicts by communicating and negotiating with each other to reach a Pareto-optimal agreement autonomously and efficiently. Our design features a two-step self-supervised learning-based algorithm to predict acceptable proposals and their rankings of each opponent through the negotiation. Our design is evaluated with a smart city case study of three services: intelligent traffic light control, pedestrian service, and environmental control. In this case study, a data-driven evaluation is conducted using a large dataset consisting of the GPS locations of 246 surveillance cameras and an automatic traffic monitoring system with more than 3 million records per day to extract real-world vehicle routes. The evaluation results show that our solution achieves much more balanced results, i.e., only increasing the average waiting time of vehicles, the measurement metric of intelligent traffic light control service, by 6.8% while reducing the weighted sum of air pollutant emission, measured for environment control service, by 12.1%, and the pedestrian waiting time, the measurement metric of pedestrian service, by 33.1%, compared to priority-based solution.

We study a class of generic charging path optimization problems arising from emerging networking applications, where mobile chargers are dispatched to deliver energy to mobile agents (e.g., robots, drones, vehicles), which have specified tasks and mobility patterns. We instantiate our work by focusing on finding the charging path maximizing the number of nodes charged within a fixed time horizon. We show that this problem is APX-hard. By recursively decomposing the problem into sub-problems of searching sub-paths, we design quasi-polynomial-time algorithms achieving logarithmic approximation to the optimum charging path. Our approximation algorithms can be further adapted and extended to solve a variety of charging path optimization and scheduling problems with realistic constraints, such as limited time and energy budget.

We formulate and analyze a generic sequential resource access problem arising in a variety of engineering fields, where a user disposes a number of heterogeneous computing, communication, or storage resources, each characterized by the probability of successfully executing the user's task and the related access delay and cost, and seeks an optimal access strategy to maximize her utility within a given time horizon, defined as the expected reward minus the access cost. We develop an algorithmic framework on the (near-)optimal sequential resource access strategy. We first prove that the problem of finding an optimal strategy is NP-hard in general. Given the hardness result, we present a greedy strategy implementable in linear time, and establish the closed-form sufficient condition for its optimality. We then develop a series of polynomial-time approximation algorithms achieving (ϵ, δ)-optimality. The key components in our design include a pruning process eliminating dominated strategies, thus maintaining polynomial time and space overhead, and a comprehensive scheme allowing flexibly trading-off time and space overhead against performance guarantee.

Electric toothbrushes are widely used for home oral care, but many users do not achieve desired hygiene results due to insufficient brushing coverage or incorrect brushing techniques. Existing electric toothbrushing monitoring systems fail to detect these issues because they cannot achieve fine-grained position tracking. In this paper, we present a novel electric toothbrushing monitoring system called MET that tracks brushing coverage for all the 15 surfaces of teeth and detects different types of incorrect brushing techniques. This design is inspired by our observation that the motor inside an electric toothbrush generates a unique magnetic field, which can serve as a reliable signal for position and orientation tracking. MET is the first system that tracks both the position and orientation of an unmodified electric motor using magnetic inductive sensing. Experiments with fourteen users show that the average toothbrushing surface recognition accuracy of MET is 85.3%. Moreover, MET is robust to user location changes and posture variations and does not require any training from the users. Experimental results also demonstrate our significant advantages over existing commercial systems.

We present a fully closed-loop design for an artificial pancreas (AP) that regulates the delivery of insulin for the control of Type I diabetes. Our AP controller operates in a fully automated fashion, without requiring any manual interaction with the patient (e.g., in the form of meal announcements). A major obstacle to achieving closed-loop insulin control are the "unknown disturbances" related to various aspects of a patient's daily behavior, especially meals and physical activity. Such disturbances can significantly affect the patient's blood glucose levels. To handle such uncertainties, we present a data-driven, robust, model-predictive control framework in which we capture a wide range of individual meal and exercise patterns using uncertainty sets learned from historical data. These uncertainty sets are then used in the insulin controller to achieve automated, precise, and personalized insulin therapy. We provide an extensive in silico evaluation of our robust AP design, demonstrating the potential of the approach. In particular, without the benefit of explicit meal announcements, our approach can regulate glucose levels for large clusters of meal profiles learned from population-wide survey data and cohorts of virtual patients, even in the presence of high carbohydrate disturbances.

Low-power wireless communication has been widely used in cyber-physical systems that require time-critical data delivery. Achieving this goal is challenging because of link burstiness and interference. Based on significant empirical evidence of 21 days and over 3.6 M packet transmissions per link, we propose both routing and scheduling algorithms that produce latency bounds of the real-time periodic streams and accounts for both link bursts and interference. The solution is achieved through the definition of a new metric B max that characterizes links by their maximum burst length, and by choosing a novel least-burst-route that minimizes the sum of worst-case burst lengths over all links in the route. With extensive data-driven analysis, we show that our algorithms outperform existing solutions by achieving accurate latency bound with much less energy consumption. In addition, a testbed evaluation consisting of 48 nodes spread across a floor of a building shows that we obtain 100% reliable packet delivery within derived latency bounds. We also demonstrate how performance deteriorates and discuss its implications for wireless networks with insufficient high-quality links.

System deployments of IoT systems have drawn research attention, because it is very challenging to meet both physical and cyber constraints in real systems. In this article, we consider the problem of deploying wireless camera networks inside a complex indoor setting for surveillance applications. We formulate the problem of the minimum connected guarding network whose objective is to place a minimum number of cameras satisfying both visual coverage of the domain and wireless network connectivity. We prove that finding the minimum connected guarding network is NP-hard in both the geometric and discrete settings. We also give a 2-approximation algorithm to the geometric minimum guarding network problem. Motivated by the connection of this problem with the watchman tour problem and the art gallery problem, we developed two algorithms to calculate the locations of camera deployment. By deploying a prototype testbed, we verify the feasibility of the system design. Using simulations on 20 real floor plans, we demonstrate that our solutions reduce the number of cameras by up to 28%, and reduce the number of relay nodes by up to 47%.

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

"Hands on the wheel, eyes on the road" is the central guideline of safe vehicle driving practices. Many advanced driver assistance systems can effectively detect abnormal vehicle motions. However, these systems often leave insufficient time for drivers to respond to complex road situations, especially when the drivers are distracted. To reduce accidents, it is essential to detect whether a driver complies with safe driving guidelines in real time and provide warnings early before any dangerous maneuvers occur. There are vision-based driver distraction monitoring systems which rely on cameras in high-end vehicles, but their performances are heavily constrained by visibility requirements. In this paper, we present MagTrack, a driver monitoring system that is based on tracking magnetic tags worn by the user. With a single smartwatch and two low-cost magnetic accessories: a hand magnetic ring and a head magnetic eyeglasses clip, our system tracks and classifies a driver's bimanual and head movements simultaneously using both analytical and approximation sensing models. Our approach is robust to driver's postures, vehicles, and environmental changes. We demonstrate that a wide range of activities can be detected by our system, including bimanual steering, visual and manual distractions, and lane changes and turns. In extensive road tests with 500+ instances of driving activities and 500+ minutes of road driving with 10 subjects, MagTrack achieves 87% of precision and 90% of recall rate on the detection of unsafe driving activities.

To achieve device-free person detection, various types of signal features, such as moving statistics and wavelet representations, have been extracted from the Wi-Fi Received Signal Strength Index (RSSI), whose value fluctuates when human subjects move near the Wi-Fi transceivers. However, these features do not work effectively under different deployments of Wi-Fi transceivers because each transceiver has a unique RSSI fluctuation pattern that depends on its specific wireless channel and hardware characteristics. To address this problem, we present WiDet, a system that uses a deep Convolutional Neural Network (CNN) approach for person detection. The CNN achieves effective and robust detection feature extraction by exploring distinguishable patterns in Wi-Fi RSSI data. With a large number of internal parameters, the CNN can record and recognize the different RSSI fluctuation patterns from different transceivers. We further apply the data augmentation method to improve the algorithm robustness to wireless interferences and pedestrian speed changes. To take advantage of the wide availability of the existing Wi-Fi devices, we design a collaborative sensing technique that can recognize the subject moving directions. To validate the proposed design, we implement a prototype system that consists of three Wi-Fi packet transmitters and one receiver on low-cost off-the-shelf embedded development boards. In a multi-day experiment with a total of 163 walking events, WiDet achieves 94.5% of detection accuracy in detecting pedestrians, which outperforms the moving statistics and the wavelet representation based approaches by 22% and 8%, respectively.

On-street parking is an essential component of parking infrastructure for smart cities, which allows users to park near their destinations for short term. However, due to limited capacity, saturated on-street parking becomes a serious and widespread problem for urban transportation systems. Greedily searching for an on-street parking spot in a saturated area is often a frustrating task for drivers, and cruising for vacant parking spots results in additional delays and impaired local circulation. With the recent development of networked smart parking meter, real-time city-wide on- street parking information becomes available for more efficient parking management. In this paper, we design an online parking guidance system that recommends parking spots in real-time based on the parking availability prediction. With a receding horizon optimization framework, our solution minimizes the user's driving and walking cost by adapting the spatiotemporally dynamic supply and demand in the local area, significantly reducing parking competitions in a timely manner. We implement and evaluate our solution with a dataset of 13,503,655 parking records collected from 5228 in-ground sensors distributed in the Australian city Melbourne. The evaluation results show that our approach achieves up to 63.8% delay reduction compared with existing solutions.

Recent advances and industry standards in Internet of Things (IoT) have accelerated the real-world adoption of connected devices. To manage this hybrid system of digital real-time devices and analog environments, the industry has pushed several popular home automation IoT (HA-IoT) frameworks, such as If-This-Then-That (IFTTT), Apple HomeKit, and Google Brillo. Typically, users author device interactions by specifying the triggering sensor event and the triggered device command. In this seemingly simple software system, two dominant factors govern the system confidence properties with respect to the physical world. First, IoT users are largely nonexperts who lack the comprehensive consideration regarding potential impact and joint effect with existing rules. Second, while the increasing complexity of IoT devices enables fine-grained control (e.g., heater temperature) of continuous real-time environments, even two simply connected devices can have a huge state space to explore. In fact, bugs that wrongfully control devices and home appliances can have ramifications on system correctness and even user physical safety. It is crucial to help users to make sure the system they created meets their expectation. In this article we introduce how techniques from hybrid automata can be practically applied to assist nonexpert IoT users in the confidence checking of such hybrid HA-IoT systems. We propose an automated framework for end-to-end programming assistance. We build and check the Linear Hybrid Automata (LHA) model of the system automatically. We also present a quantifier elimination-based method to analyze the counterexample found and synthesize fix suggestions. We implemented a platform, MenShen, based on this framework and proposed techniques. We conducted sets of real HA-IoT case studies with up to 46 devices and 65 rules. Empirical results show that MenShen can find violations and generate rule fix suggestions in only 10 seconds.

In this paper we study the following problem: given a set of m sensors that collectively cover a set of n target points with heterogeneous coverage requirements (target j needs to be covered every fjslots), how to schedule the sensor duty cycles such that all coverage requirements are satisfied and the maximum number of sensors turned on at any time slot is minimized. The problem models varied real-world applications in which sensing tasks exhibit high discrepancy in coverage requirements - critical locations often need to be covered much more frequently. We provide multiple algorithms with best approximation ratio of O (log n + log m) for the maximum number of sensors to turn on, and bi-criteria algorithm with (α, β)-approximation factors with high probability, where the number of sensors turned on is an α = O(δ(log (n) + log(m))/β)-approximation of the optimal (satisfying all requirements) and the coverage requirement is a β-approximation; δ is the approximation ratio achievable in an appropriate instance of set multi-cover. When the sensor coverage exhibits extra geometric properties, the approximation ratios can be further improved. We also evaluated our algorithms via simulations and experiments on a camera testbed. The performance improvement (energy saving) is substantial compared to turning on all sensors all the time, or a random scheduling baseline.

Understanding occupancy patterns in a building is very useful to control HVAC systems for improving energy efficiency of the building and occupant comfort. There has been a very little attempt to understand long term occupancy patterns in a commercial space. In this work, we leverage depth sensors (Kinect for XBOX One) to collect occupancy count from an 11,000 square foot commercial space (Bosch office) for nine months. We analyze the collected data and describe key findings that provide deep insights about how a commercial space is used and serve as a guideline to formulate novel and efficient control strategies.

As sensor networks are increasingly deployed for critical applications, reliability and latency guarantee become more important than ever to meet industrial requirements. In this paper, we investigated the impact of link burstiness on stream scheduling using a data trace of 3,600,000 packets collected from an indoor testbed. We demonstrate that a good tradeoff between reliability and latency can be achieved by allocating certain time slots on each link for stream transmissions based on its burst length and frequency distributions. With this observation, we design transmission scheduling and routing algorithms for data streams to meet a specified reliability requirement while minimizing end-to- end latency. For the multi-stream scheduling problem, we prove its NP-hardness and design an algorithm that achieves the reliability guarantee and an O(log n) approximation of minimizing the maximum end-to-end latency for any stream. Trace- driven simulations show that our solution meets specified end-to-end reliability requirements with latency up to 9.18 times less than existing solutions.

MIMO beamforming provides high throughput for WiFi networks, but it also leads to high computation and communication overhead due to Channel State Information (CSI) feedback. Explicit CSI feedback provides high beamforming gains, but it introduces extremely high overhead. Implicit CSI feedback has low overhead, but it provides very low beamforming gains. We propose EliMO to completely Eliminate CSI feedback from MIMO without sacrificing beamforming gains. EliMO uses two-way channel estimation to allow WiFi Access Points (AP) to accurately estimate downlink CSI without explicit CSI feedback. To measure downlink CSI at the WiFi AP, the WiFi station (STA) puts the received signal of downlink training symbols into Feedback Training Field (FTF) and sends it back to the AP. The AP estimates the two-way channel using the received signal of FTF. Analysis and experiment results show that EliMO is able to provide as high beamforming gains as explicit CSI feedback and as low overhead as implicit CSI feedback. EliMO significantly reduces computation and communication costs of measuring and sending CSI feedback for smart devices, like smartphones, smartwatches, and wireless drones. We evaluate the throughput and energy consumption of EliMO by experiment measurements in both static and mobile scenarios. Evaluation results show that EliMO provides 5× and 4× throughput as implicit and explicit CSI feedback, respectively. Energy consumption of EliMO is only 85%/30% of that of implicit/explicit CSI feedback.

Multiple-input multiple-output (MIMO) provides high throughput for WiFi networks, but it also leads to high overhead due to channel state information (CSI) feedback. Based on experiment measurements, this paper shows that MIMO has different feedback requirements when the receiver is rotating compared with when the receiver is in other mobility scenarios. Experiments of four popular Android games show that device rotation accounts for around 50% of the running time for these games, which implies that rotation-awareness could improve WiFi efficiency significantly for these games. We propose rotation-aware WiFi (RoFi) channel feedback to eliminate unnecessary CSI feedback while maintaining high throughput. We show the failure of existing mobility-aware methods, including CSI similarity, time-of-flight (ToF), and compression noise, in distinguishing the mobility status of rotation and mobile. RoFi calculates power delay profile (PDP) similarity for rotation detection and performs feedback compression and rate selection accordingly. To deal with false rotation detection and status transition between rotation and static, RoFi uses the power of the strongest path, which is calculated from PDP, to further refine CSI feedback when necessary. The RoFi design is compatible with legacy 802.11 protocols and is easy to be deployed on existing WiFi systems. Evaluation results show that RoFi reduces 25%-40% overhead with negligible signal-to-noise ratio decrease in rotation scenarios. RoFi also consumes 29%-69% less energy compared with state-of-the-art feedback compression and rate selection algorithms.

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

In this paper, we survey recent progress in CyberCardia project, a CPS Frontier project funded by the National Science Foundation. The CyberCardia project will lead to significant advances in the state of the art for system verification and cardiac therapies based on the use of formal methods and closed-loop control and verification. The animating vision for the work is to enable the development of a true in silico design methodology for medical devices that can be used to speed the development of new devices and to provide greater assurance that their behavior matches designer intentions, and to pass regulatory muster more quickly so that they can be used on patients needing their care. The acceleration in medical-device innovation achievable as a result of the CyberCardia research will also have long-term and sustained societal benefits, as better diagnostic and therapeutic technologies enter into the practice of medicine more quickly.

WiFi is a major source of energy consumption on smartphones. Unfortunately, a non-negligible portion of the WiFi energy consumption is spent for frames that are useless to the smartphone. For example, energy is wasted to receive WiFi broadcast frames that are not needed by any smartphone application. What's worse, in order to process the broadcast frames received, a smartphone in suspend mode switches from suspend mode to high power active mode and stays there for a while. As such, additional energy is wasted to do the processing. In this paper, we design a system, namely HIDE, to reduce smartphone energy wasted on useless WiFi broadcast traffic. With our system, smartphones in suspend mode do not receive useless broadcast frames or wake up to process useless broadcast frames. Our trace-driven simulation shows that the HIDE system saves 34%-75% energy for Nexus One when 10% of the broadcast frames are useful to the smartphone. Our overhead analysis demonstrates that our system has negligible impact on network capacity and packet round-trip time.

We study a class of generic optimization problems on charger scheduling and charging path planing. These problems arise from emerging networking applications where mobile chargers are dispatched to deliver energy to mobile agents (e.g., robots, drones, and vehicles), which have specified tasks and mobility patterns. We instantiate our work by focusing on finding the charging path maximizing the number of nodes charged within a fixed time horizon. We prove that this problem is APX-hard. By recursively decomposing the problem into sub-problems of searching sub-paths, we design a quasi-polynomial time algorithm that achieves poly-logarithmic approximation to the optimum charging path. Our approximation algorithm can be further adapted and extended to solve a variety of charging path optimization and scheduling problems with realistic constraints, such as limited time and energy budget.

Using optical sensors for indoor monitoring has been widely adopted in many smart building applications. An important design problem in this space is to explore the tradeoff between energy consumption and coverage quality. While it is important that the sensors achieve full coverage (i.e., every interesting target point can be monitored by at least one sensors), it is often a waste of energy to keep sensors on all the time as events are typically stochastic and rare and most of the time the sensors are on idle monitoring. In this paper we design efficient sensor duty cycles to ensure that any target point of interest is still covered sufficiently frequently while only a subset of sensors are kept on at any time slot. We denote by the maximum dark length for each target point p as the maximum duration in which p is covered at least once. We formulate two optimization problems: the min max dark length scheduling and the min average dark length scheduling. For both versions we provide efficient, practical algorithms with provable approximation guarantee. The two algorithms have been tested on two real testbed scenarios to evaluate its efficiency and coverage quality.

In this paper we investigate sensor deployment and coverage algorithms for using infrared signals in indoor applications. Infrared signals are directional and reliable signals that have little interference with other electromagnetic signals that are commonly found in the deployment domain such as visible light and wireless radio waves. Since the angle of arrival is used, and line of sight is the main constraint for IR signals, we investigate the problem called robust guarding, i.e., placing emitters to ensure that all points of the domain are robustly covered by two emitters that are from sufficiently different directions. We prove combinatorial upper and lower bounds for the number of emitters needed and prove that finding the minimum number of guards is NP-hard. We show that n/2 guards are always sufficient and sometimes necessary for rectilinear polygons and we provide practical algorithms in general. We also developed a testbed with low cost off-the-shelf infrared (IR) emitters and sensors for indoor device-free localization. We tested the algorithms for using infrared sensors for indoor localization and our system achieves an average accuracy of 11.7 cm in a typical office setting.

Daily toothbrushing is essential for maintaining oral health. However, there is very limited technology to monitor the effectiveness of toothbrushing at home. In this paper, a system is built to monitor the brushing quality on all 16 tooth surfaces using a manual toothbrush and an off-the-shelf wrist watch. The toothbrush is modified by attaching small magnets to the handle, so that its orientation and motion can be captured by the magnetic sensor in the wrist watch. The toothbrushing gestures are recognized based on inertial sensing data from the wrist watch. As the acoustic signal collected from the watch is correlated with the motion of toothbrushing stroke, acoustic sensing algorithm is designed to assist in recognition. User-specific toothbrushing order is also utilized to improve the surface recognition. In extensive experiments with 12 users over 3 weeks, our system successfully recognized toothbrushing gestures with an average precision of 85.6%.

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

Relay assignment significantly affects the performance of the cooperative communication, which is an emerging technology for the future mobile system. Previous studies in this area have mostly focused on assigning a dedicated relay to each source-destination pair for one-to-one (121) traffic. However, many-to-one (M21) traffic, which is also common in many situations (for example, several users associate with one access point in a wireless access network such as a WLAN), hasn't been well studied. This paper addresses the shared relay assignment (SRA) problem for M21 traffic. We formulate two new optimization problems: one is to maximize the minimum throughput among all the sources (hereafter called M21-SRA-MMT), and the other is to maximize the total throughput over all the sources while maintaining some degree of fairness (hereafter called M21-SRA-MTT). As the optimal solutions to the two problems are hard to find, we propose two approximation algorithms whose performance factors are 5.828 and 3, respectively, based on the rounding mechanism. Extensive simulation results show that our algorithms for M21-SRA-MMTcan significantly improve the minimum throughput compared with existing algorithms, while our algorithm for M21-SRA-MTTcan achieve the close-to-optimal performance.

In wireless sensor networks, data harvesting using mobile data ferries has recently emerged as a promising alternative to the traditional multi-hop communication paradigm. The use of data ferries can significantly reduce energy consumption at sensor nodes and increase network lifetime. However, it usually incurs long data delivery latency as the data ferry needs to travel through the network to collect data, during which some delay-sensitive data may become obsolete. Therefore, it is important to optimize the trajectory of the data ferry with data delivery latency bound for this approach to be effective in practice. To address this problem, we formally define the time-constrained data harvesting problem, which seeks an optimal data harvesting path in a network to collect as much data as possible within a time duration. We then investigate the formulated data harvesting problem in the generic m-dimensional context, of which the cases of m=1, 2, 3 are particularly pertinent. We first characterize the performance bound given by the optimal data harvesting algorithm and show that the optimal algorithm significantly outperforms the random algorithm, especially when network scales. However, we mathematically prove that finding the optimal data harvesting path is NP-hard. We therefore devise an approximation algorithm and mathematically prove the output being a constant-factor approximation of the optimal solution. Our experimental results also demonstrate that our approximation algorithm significantly outperforms the random algorithm in a wide range of network settings.

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

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

Data harvesting using mobile data ferries has recently emerged as a promising alternative to the traditional multi-hop transmission paradigm. The use of data ferries can significantly reduce energy consumption at sensor nodes and increase network lifetime. However, it usually incurs longer data delivery latency as the data ferry needs to travel through the network to collect data, during which some delay-sensitive data may become obsolete. Therefore, optimizing the trajectory of the data ferry with data delivery latency bound is important for this approach to be effective in practice. To address this problem, we formally define the time-constrained data harvesting problem, which seeks an optimal data harvesting path in a network to collect as much data as possible within a time duration. We first characterise the performance bound given by the optimal data harvesting algorithm and show that the optimal algorithm significantly outperforms the random algorithm, especially when network scales. Motivated by the theoretical analysis and proving the NP-completeness of the time-constrained data harvesting problem, we then devise polynomial-time approximation schemes (PTAS) and mathematically prove the output being a constant-factor approximation of the optimal solution.

Prior studies show that repairing partially corrupted packets, instead of retransmitting them in their entirety, holds potential in improving the performance of 802.11 networks. However, the efficiency of existing packet recovery approaches is severely limited by various overhead associated to redundant transmission and repeated channel contention. In this paper, we propose CodeRepair, a practical coding-based protocol that recovers partially corrupted 802.11 packets without these pains. The design of CodeRepair is based on two novel ideas. First, CodeRepair pushes the limit of 802.11 PHY to piggyback parities in the padded bits of OFDM, obviating the need of transmitting extra information for error correction. Second, CodeRepair corrects errors at the PHY layer, which is significantly more efficient than traditional link-layer approaches. This is due to the fact that a single coded bit usually affects the decoding of a group of data bits in 802.11 convolutional code. As a result, CodeRepair can salvage a partially corrupted packet by correcting a small number of erroneous coded bits using the padded parities. To reduce computational cost of error recovery, CodeRepair employs single parity code for correcting coded bit errors. We propose several techniques to augment the error correcting capability of single parity code without compromising its computation efficiency. Our evaluation shows that CodeRepair recovers an average of 34% partially corrupted packets, and improves the end-to-end link goodput by 59% on lossy 802.11 links.

Network coding (NC) based opportunistic routing has been well studied, but the impact of routing diversity on the performance of NC-based routing remains largely unexplored. Towards understanding the importance of routing diversity in NC-based routing, we study the problems of estimating and minimizing the data delivery cost in NC-based routing. In particular, we propose an analytical framework for estimating the total number of packet transmissions for NC-based routing in arbitrary topologies. We design a greedy algorithm that minimizes the total transmission cost of NC-based routing and determines the corresponding forwarder set for each node. We prove the optimality of this algorithm and show that 1) nodes on the shortest path may not always be favored when selecting forwarders for NC-based routing and 2)the minimal cost of NC-based routing is upper-bounded by the cost of shortest path routing. Based on the greedy, optimal algorithm, we design and implement ONCR, a distributed minimal cost NC-based routing protocol. Using the NetEye sensor testbed, we comparatively study the performance of ONCR and existing approaches such as the single path routing protocol CTP and the NC-based opportunistic routing protocols MORE and CodeOR. Results show that ONCR achieves close to 100% delivery reliability while having the lowest delivery cost among all the protocols and 25-28% less than the second best protocol CTP. This low delivery cost also enables ONCR to achieve the highest network goodput, i.e., about two-fold improvement over MORE and CodeOR. Our findings demonstrate the significance of optimizing data forwarding diversity in NC-based routing for data delivery reliability, efficiency, and goodput.

Recent advances in energy transfer technology is boosting the development of renewable sensor networks. To sustain such a network, a mobile robot travels from node to node to recharge each sensor before its battery runs out. Consider each node's recharge as a real-time task, the robot needs to serve these tasks by their deadlines. This represents a class of challenging mobility scheduling problems, where the nodes' deadlines and spatial distribution are often at odds with each other. In this paper, we focus on the scenario where nodes have heterogeneous energy consumption rates, and our goal is to maximize the percentage of nodes alive. We formulate this scheduling problem and prove its NP-completeness. To solve this problem, we propose a spatial dependent task scheduling algorithm, which quantifies the impact of scheduling proximate tasks on the other tasks. With extensive simulations, we reveal the trade-offs of existing solutions under a wide range of network scenarios. Our evaluation results show that our algorithms out-perform classical TSP scheduler by up to 10% and 85% in terms of coverage ratio and average tardiness, respectively.

Recent advances in energy transfer technology is boosting the development of renewable sensor networks. To sustain such a network, a mobile robot travels from node to node to recharge each sensor before its battery runs out. To solve this problem, we propose a spatial dependent task scheduling algorithm, which quantifies the impact of scheduling proximate tasks on the other tasks. Our evaluation results show that our algorithms out-perform classical TSP scheduler by up to10% and 85% in terms of coverage ratio and average tardiness, respectively.

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

Multihop broadcasting in low-duty-cycle Wireless Sensor Networks (WSNs) is a very challenging problem, since every node has its own working schedule. Existing solutions usually use unicast instead of broadcast to forward packets from a node to its neighbors according to their working schedules, which is, however, not energy efficient. In this article, we propose to exploit the broadcast nature of wireless media to further save energy for low-duty-cycle networks, by adopting a novel broadcasting communication model. The key idea is to let some early wake-up nodes postpone their wake-up slots to overhear broadcasting messages from its neighbors. This model utilizes the spatiotemporal locality of broadcast to reduce the total energy consumption, which can be essentially characterized by the total number of broadcasting message transmissions. Based on such model, we aim at minimizing the total number of broadcasting message transmissions of a broadcast for low-duty-cycle WSNs, subject to the constraint that the broadcasting latency is optimal. We prove that it is NP-hard to find the optimal solution, and design an approximation algorithm that can achieve a polylogarithmic approximation ratio. Extensive simulation results show that our algorithm outperforms the traditional solutions in terms of energy efficiency.

Wireless insulin pumps have been widely deployed in hospitals and home healthcare systems. Most of them have limited security mechanisms embedded to protect them from malicious attacks. In this paper, two attacks against insulin pump systems via wireless links are investigated: a single acute overdose with a significant amount of medication and a chronic overdose with a small amount of extra medication over a long time period. They can be launched unobtrusively and may jeopardize patients' lives. It is very urgent to protect patients from these attacks. We propose a novel personalized patient infusion pattern based access control scheme (PIPAC) for wireless insulin pumps. This scheme employs supervised learning approaches to learn normal patient infusion patterns in terms of the dosage amount, rate, and time of infusion, which are automatically recorded in insulin pump logs. The generated regression models are used to dynamically configure a safe infusion range for abnormal infusion identification. This model includes two sub models for bolus (one type of insulin) abnormal dosage detection and basal abnormal rate detection. The proposed algorithms are evaluated with real insulin pump. The evaluation results demonstrate that our scheme is able to detect the two attacks with a very high success rate.

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

We consider the problem of deployment of cameras inside a complex indoor setting for surveillance applications. We formulate the problem of the minimum guarding network that places a minimum number of cameras satisfying both visual coverage of the domain and wireless network connectivity. We prove that finding the minimum guarding network in both the geometric setting and discrete setting is NP-hard. We also give a 2-approximation algorithm to the geometric minimum guarding network. Motivated by the connection of this problem with the watchman tour problem and the art gallery problem, we develop two algorithms that generate satisfactory results in a prototype testbed and in our simulations.

Security of wireless medical devices is critical for patient safety because security attacks may directly hurt patients' health. In this paper, we design a novel access control scheme based on bi-channel and multi-factor authentication for wireless medical devices. Our scheme utilizes near field communication (NFC) to perform device pairing, which supports key exchange between a device and a reader in short communication range (<= 6cm) with bounded response time. To further defend against attacks when a malicious reader is placed within the device's communication range in crowded situations, we design a crowd detection algorithm using WiFi and user's smart phone to assist the key exchange. Our analyses and experiments show that our security schemes are effective and efficient.

Breadcrumb systems (BCS) aid first responders by communicating their physiological parameters to remotely located base stations. In this paper, we describe the design, implementation, and evaluation of an automatic and robust multi-user breadcrumb system for indoor first response applications. Our solution includes a breadcrumb dispenser with a link estimator that is used to decide when to deploy breadcrumbs to maintain reliable wireless connectivity. The solution includes accounting for realities of buildings and dispensing such as the height difference between where the dispenser is worn and the floor where the dispensed nodes are found. We also include adaptive power management to maintain link quality over time. Moreover, we propose UF, a distributed cooperative deployment algorithm, to achieve longer breadcrumb chain lengths while maintaining fairness and high system reliability via selecting appropriate benefit and cost functions. We deployed and evaluated our system in real buildings with several different first responder mobility patterns. Experimental results from our study show that compared to the state of the art solution , our breadcrumb system achieves 200 percent link redundancy with only 23 percent additional deployed nodes. Our deployed breadcrumb chain can achieve 90 percent PRR when one node fails in the chain. In addition, by applying the UF coordination algorithm, the system can maintain connectivity for up to 87 percent longer distances than baseline greedy coordination approach while maintaining 96 percent packet delivery ratio.

Android Honeycomb operating system is widely used for tablet devices, such as Samsung Galaxy Tab. The Android system programs are usually efficient and secure in memory management. However, there has been a few security issues reported that show Android's insufficient protection to the kernel. In this work, we reveal a new security pitfall in memory management that can cause severe errors and even system failures. Existing security software for android do not detect this pitfall, due to the private implementation of Android kernel. We then discuss two vulnerabilities introduced by this pitfall: 1) malicious programs can escalate the root-level privilege of a process, through which it can disable the security software, implant malicious codes and install rootkits in the kernel; 2) deny of service attacks can be launched. Experiments have been conducted to verify these two vulnerabilities on Samsung Galaxy Tab 10.1 with Tegra 2 CPU. To protect systems from these vulnerabilities, we proposed a patching solution, which has been adopted by Google.

Wireless Rechargeable Sensor Networks (WRSNs) can be recharged after deployment for sustainable operations. Recent works propose to use a single mobile charger (MC) traveling through the network fields to recharge every sensor node. These algorithms work well in small scale networks. However, in large scale networks these algorithms do not work efficiently, especially when the amount of energy the MC can provide is limited. To address these challenges, multiple MCs can be used. In this paper, we investigate the minimum MCs problem (MinMCP) for rechargeable sensor networks: how to find the minimum number of energy-constrained MCs and design their recharging routes given a sensor network such that each sensor node in the WRSN maintains continuous work. Our results are three folds. We first prove that for any ϵ > 0, there is no (2-ϵ)-approximation algorithm for Distance Constrained Vehicle Routing Problem (DVRP) on a general metric space, which is the best as far as we know. By reducing from DVRP, we prove that MinMCP is NP-hard, and the inapproximability bound for MinMCP is the same as that of DVRP. Then we propose approximation algorithms for this problem. Finally, we conduct simulations to validate the effectiveness of our algorithms.

Wireless insulin pumps have been widely deployed in hospitals and home healthcare systems. Most of these insulin pump systems have limited security mechanisms embedded to protect them from malicious attacks. In this paper, two attacks against insulin pump systems via wireless links are investigated: a single acute overdose with a significant amount of medication, and chronic overdose with an insignificant amount of extra medication over a long time period, e.g., several months. These attacks can be launched unobtrusively and may jeopardize patients' lives. It is very important and urgent to protect patients from these attacks. To address this issue, we propose a novel patient infusion pattern based access control scheme (PIPAC) for wireless insulin pumps. This scheme employs a supervised learning approach to learn normal patient infusions pattern with the dosage amount, rate, and time of infusion, which are automatically recorded in insulin pump logs. The generated regression models are used to dynamically configure a safety infusion range for abnormal infusion identification. The proposed algorithm is evaluated with real insulin pump logs used by several patients for up to 6 months. The evaluation results demonstrate that our scheme can reliably detect the single overdose attack with a success rate up to 98% and defend against the chronic overdose attack with a very high success rate.

First responder applications often require safety surveillance using wireless camera networks~\cite{breadcrums}. To ensure visual sensing coverage, it is crucial to place optical sensor nodes at proper locations. Under the scenario of energy constrained wireless camera deployment, the issue of communication cost should also be considered. Previous camera deployment research (e.g Art Gallery Problem) mainly concerned sensing coverage. One well-known solution for the art gallery problem is to triangulate the objective polygon and then select vertices to ensure full coverage. However, deploying cameras only in the vertices of polygon may induce inefficiency both in number of necessary cameras and overall communication cost. To reduce the cost, we propose two deployment algorithms: 1) connected visibility region planning algorithm for static deployment given the floor plan is known, and 2) connected visibility region tracking algorithm for the dynamic deployment during the run time. In extensive simulations with real floor plans, our algorithms outperform previous solutions significantly.

For low-duty-cycle wireless sensor networks, multihop broadcasting is a challenging problem, since every node has its own working schedules. In this paper, we design a novel broadcasting algorithm, of which key idea is to let some early wake-up nodes postpone their wake-up slots to overhear broadcasting message from its neighbors. This design utilizes the spatiotemporal locality of broadcasting to reduce the number of transmissions. We show that to find the broadcasting schedule with minimal latency and optimized total energy consumption is NP-hard, and then design an approximation algorithm that can guarantee the optimality of broadcasting latency and achieve a polylogarithmic approximation ratio for total energy consumption. Compared with the traditional solution, extensive experimental results show that our algorithm achieves the minimal broadcasting latency while reducing energy consumption significantly.

Battery-powered wireless sensor devices need to be charged to provide the desired functionality after deployment. Task or even device failures can occur if the voltage of the battery is low. It is very important to schedule the recharge of batteries in time. Existing battery scheduling algorithms usually charge a battery when its voltage drops below a fixed level. Such algorithms work well when the workloads are predictable. However, workloads of wireless sensors can be highly bursty, i.e., extensive sensing and communication tasks usually occur in a very short time period. If such a bursty workload occurs when the battery voltage is low, the battery energy can be depleted very quickly, resulting in system task failures before the device can be recharged. To deal with unpredictable bursty workloads, we investigate battery characteristics with different workloads via experiments. Based on the empirical results, we build an adaptive linear model and propose a feedback control based battery charge scheduling algorithm. This algorithm dynamically adjusts the battery charge threshold for recharge scheduling, adapting to bursty workloads. We have tested our algorithms in extensive simulations with traces obtained from real experiments. Evaluation results show that our algorithms can adapt to bursty workloads. Compared to existing algorithms, our algorithm achieves a 68.26% lower task failure ratio with a 3.45% sacrifice on system lifetime under bursty workloads.

Breadcrumb systems (BCS) aid first responders by communicating their physiological parameters to remotely located base stations. However, state-of-the-art research only focuses on deploying breadcrumb systems on the assumption of uncoordinated users, which is inefficient. In this paper, we present the first design, implementation, and evaluation of reliable multiuser breadcrumb systems (MUBCS) which exploits efficient and automatic coordination among system users to achieve better utilization of limited breadcrumbs. We propose UF, a distributed cooperative deployment algorithm, to achieve longer breadcrumb chain length while maintaining fairness and high system reliability via selecting appropriate benefit and cost functions. UF also requires no prior assumptions about users' mobility models, making the design practical for real applications. We deployed and evaluated our system in real buildings with several different first responder mobility patterns. Experimental results indicate that this approach can maintain connectivity for up to 87% longer distances than baseline greedy coordination approach while maintaining 96% packet delivery ratio.

As wireless devices and sensors are increasingly deployed on people, researchers have begun to focus on wireless body-area networks. Applications of wireless body sensor networks include healthcare, entertainment, and personal assistance, in which sensors collect physiological and activity data from people and their environments. In these body sensor networks, quality of service is needed to provide reliable data communication over prioritized data streams. This article proposes BodyQoS, the first running QoS system demonstrated on an emulated body sensor network. BodyQoS adopts an asymmetric architecture, in which most processing is done on a resource-rich aggregator, minimizing the load on resource-limited sensor nodes. A virtual MAC is developed in BodyQoS to make it radio-agnostic, allowing a BodyQoS to schedule wireless resources without knowing the implementation details of the underlying MAC protocols. Another unique property of BodyQoS is its ability to provide adaptive resource scheduling. When the effective bandwidth of the channel degrades due to RF interference or body fading effect, BodyQoS adaptively schedules remaining bandwidth to meet QoS requirements. We have implemented BodyQoS in NesC on top of TinyOS, and evaluated its performance on MicaZ devices. Our system performance study shows that BodyQoS delivers significantly improved performance over conventional solutions in combating channel impairment.

As wireless sensor networks mature, they are increasingly being used in real-time applications. Many of these applications require reliable transmission within latency bounds. Achieving this goal is very difficult because of link burstiness and interference. Based on significant empirical evidence of 21 days and over 3,600,000 packets transmission per link, we propose a scheduling algorithm that produces latency bounds of the real-time periodic streams and accounts for both link bursts and interference. The solution is achieved through the definition of a new metric Bmax that characterizes links by their maximum burst length, and by choosing a novel least-burst-route that minimizes the sum of worst case burst lengths over all links in the route. A testbed evaluation consisting of 48 nodes spread across a floor of a building shows that we obtain 100% reliable packet delivery within derived latency bounds. We also demonstrate how performance deteriorates and discuss its implications for wireless networks with insufficient high quality links.

Breadcrumb systems (BCS) have been proposed to aid firefighters inside buildings by communicating their physiological parameters to base stations outside the buildings. In this paper, we describe the design, implementation and evaluation of an automatic and robust breadcrumb system for firefighter applications. Our solution includes a breadcrumb dispenser with an optimized link estimator that is used to decide when to deploy breadcrumbs to maintain reliable wireless connectivity. The solution includes accounting for realities of buildings and dispensing such as the height difference between where the dispenser is worn and the floor where the dispensed nodes are found. We also include adaptive power management to maintain link quality over time.

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

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

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

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