In this paper, we study the Quality of Surveillance of Low Earth Orbit (LEO) satellite constellations in orbit edge computing platforms, with a focus on monitoring and detecting unpredictable intruding targets. We are primarily interested in targets for precision agriculture and climate monitoring purposes, ranging from natural events such as tornados and flooding, to human-induced phenomenon, such as forest fires and crop monitoring. Targets may be static or mobile. We develop an analytical model that seeks to predict performance attributes of the surveillance. The model takes into account tunable system parameters, such as the number of satellites and their altitude, thereby allowing us to decide the best constellation configuration for different purposes. The results from the analytical model validate the feasibility of using LEO constellation for surveillance purposes and illustrate how model-guided parameter tuning can significantly enhance the monitoring performance in precision agriculture and climate monitoring applications.

Thanks to the applications such as Quantum Key Distribution and Distributed Quantum Computing, the deployment of quantum networks is gaining great momentum. A major component in quantum networks is repeaters, which are essential for reducing the error rate of qubit transmission for long-distance links. However, repeaters are expensive devices, so minimizing the number of repeaters placed in a quantum network while satisfying performance requirements becomes an important problem. Existing solutions typically solve this problem optimally by formulating an Integer Linear Program (ILP). However, the number of variables in their ILPs is O ( n 2 ) , where n is the number of nodes in a network. This incurs infeasible running time when the network scale is large. To overcome this drawback, this paper proposes to solve the repeater placement problem by two steps, with each step using a linear program of a much smaller scale with O ( n ) variables. Although this solution is not optimal, it dramatically reduces the time complexity, making it practical for large-scale networks. Moreover, it constructs networks that have higher node connectivity than those by existing solutions, since it deploys slightly more number of repeaters into networks. Our extensive experiments on both synthetic and real-world network topologies verified our claims.

Only when understanding hackers” tactics, can we thwart their attacks. With this spirit, this paper studies how hackers can effectively launch the so-called ‘targeted node attacks”, in which iterative attacks are staged on a network, and in each iteration the most important node is removed. In the existing attacks for weighted networks, the node importance is typically measured by the centralities related to shortest paths, and the attack effectiveness is also measured mostly by shortest-path-related metrics. However, this paper argues that flows can better reflect network functioning than shortest paths for those networks with carrying traffic as the main functionality. Thus, this paper proposes metrics based on flows for measuring the node importance and the attack effectiveness, respectively. Our node importance metrics include three flow-based centralities (flow betweenness, current-flow betweenness and current-flow closeness), which have not been proposed for use in the attacks on weighted networks yet. Our attack effectiveness metric is a new one proposed by us based on average network flow. Extensive experiments on both artificial and real-world networks show that the attack methods with our three suggested centralities are more effective than the existing attack methods when evaluated under our proposed attack effectiveness metric.

With the ever-increasing proliferation of edge devices for applications, such as home automation and vehicle systems, their security vulnerabilities have received additional attention. A recent type of attack, physical fault injections, are particularly powerful as they can compromise these devices by skipping necessary instructions through physical methods, such as induced voltage glitches. Hence, they can trigger a wide range of software behavior anomalies and vulnerabilities not caused by the programs themselves. These attacks allow adversaries to carry out severe security breaches such as control flow hijacking and information leakage, even if the original device firmware has been well tested.

One of the challenges in ensuring the security of Internet of Things (IoT) devices involves preserving control flow integrity (CFI) against return-oriented programming (ROP) attacks. Traditional defense mechanisms, while effective, often require substantial changes to the compiler, thereby limiting their applicability to a broad range of devices. To overcome this challenge, we present the Parity Shadow Stack — a novel, compact shadow stack mechanism that leverages dynamic instrumentation and binary rewriting to achieve similar effects compared to compiler-based methods. Further, this method does not require application source code and can work with legacy applications where only the binary is available. Finally, we demonstrate that it is more flexible as it provides a programming interface to add additional security semantics checks. Through our evaluations, we find that our method introduces a remarkably low overhead, less than 10 percent for medium-size or large-size applications. Therefore, we conclude it provides robust and practical defense against ROP attacks without requiring source code or compiler changes, nor does it require any specialized hardware.

Detecting execution anomalies is an integral part of building and protecting modern large-scale distributed systems. These systems generate a large volume of system logs to record system state and significant events, which provide a valuable resource to help debug system failures and perform root cause analysis. However, detecting anomalies in log sequences remains a challenge due to reasons including the imbalance of the data, the complexity of relationships between events, and the high dimensionality of log events. Traditional graph-based models may lose important higher-order sequence patterns and result in undetectable higher-order anomalies because they use first-order or fixed-order networks to represent the underlying log data. In this paper, we propose a novel unsupervised graph-based anomaly detection method, called GraphLog, which utilizes a variable high-order network representation. This variable representation enables GraphLog to efficiently learn log patterns from normal logs and detect first-order and higher-order log patterns that deviate from normal data. We demonstrate that the proposed graph-based log anomaly detection algorithm is effective, and it outperforms other baseline methods when trained using two real-world datasets.

In recent years, cloud computing platforms have attracted more and more attention. A key challenge is that existing schedulers provide limited support for heterogeneous types of resources. This makes it difficult to allocate resources in a timely manner adaptively and efficiently to perform different kinds of tasks. In this paper, we develop and evaluate a scheduling system with QoS guarantees when multiple tasks are involved, in which we show a possible design driven by the use of utilities for task-based resource allocation. We call the resulting method PECS, which meets the following unique properties compared to existing systems: Pareto efficiency, i.e. no other assignment can increase the sum of utility of all tasks without harming at least one specific task; freedom of envyness, i.e. no task will find the allocation of resource for another task better for its own utility; finally, improvements based on equal distribution are guaranteed, that is, the utility of all tasks is at least as high as the equal distribution of all resources. Our evaluation results compare PECS with a state-of-the-art resource allocation method called DRF, where our results demonstrate the performance benefits of PECS applied to a rich set of task assignment scenarios.

Effective and efficient animal disease detection and control have drawn increasing attention in smart farming in recent years. It is crucial to explore how to harvest data and enable data-driven decision making for rapid diagnosis and early treatment of infectious diseases among herds. This article proposes an IoT-based animal social behavior sensing framework to model mastitis propagation and infer mastitis infection risks among dairy cows. To monitor cow social behaviors, we deploy portable GPS devices on cows to track their movement trajectories and contacts with each other. Based on those collected location data, we build directed and weighted cattle social behavior graphs by treating cows as vertices and their contacts as edges, assigning contact frequencies between cows as edge weights, and determining edge directions according to contact spatial-temporal information. Then, we propose a flexible probabilistic disease transmission model, which considers both direct contacts with infected cows and indirect contacts via environmental contamination, to estimate and forecast mastitis infection probabilities. Our model can answer two common questions in animal disease detection and control: 1) which cows should be given the highest priorities for an investigation to determine whether there are already infected cows on the farm and 2) how to rank cows for further screening when only a tiny number of sick cows have been identified. Both theoretical and simulation-based analytics of in-the-field experiments (17 cows and more than 70-h data) demonstrate the proposed framework’s effectiveness. In addition, somatic cell count (SCC) mastitis tests validate our predictions as correct in real-world scenarios.

The complex factory environment of the Industrial Internet of Things (IIoT) greatly increases the energy consumption of sensor nodes and reduces production profits. Especially, in mines, the terrain will change continuously as the mining progresses. Additionally, the heavy traffic load on a single sink node and the unbalanced load on multiple sink nodes also reduce the battery life. Therefore, how to build an energy-efficient topology based on the unique mine terrain characteristics is a critical issue. To address this problem, this article proposes a 3-D topology evolution scheme with self-adaption for mining areas (3D-TES) to reduce energy consumption. We build the multipeak terrain model according to the characteristics of the mining environment. Blocked by the undulating peaks on the mine, the strength of the node signal is quantified by the slope and aspect. The 3D-TES is then applied to determine the optimal number of sink nodes and find the best data transmission path between sensor nodes and multiple sink nodes. The experimental results show that 3D-TES outperforms the directed angulation toward the sink node model (DASM) in terms of reliability, average path length, and data load on sink nodes.

Over the past decade, health information technology (IT) has enabled the amount of digital information stored in electronic health records (EHRs) to expand greatly. However, according to some studies, hazards in health IT can lead to changes in clinical decisions, care processes, and care outcomes, as well as other issues. Thus, the effects of health IT hazards on patient safety have been at the forefront of recent patient safety research. Nonetheless, hazard detection in health IT remains a challenge. In this paper, the authors assume that safety-related issues in health IT would exhibit anomalous characteristics in EHR data. Although all hazards will exhibit some anomalous characteristics, not all anomalies can be regarded as hazards. The authors hypothesize that errors in health IT could lead to interruptions in the sequence of clinical actions. To this end, the problem of detecting anomalous sequences in big EHR data is considered. This paper focuses on dynamic event sequences, which are a series of clinical actions in motion. The authors propose an adaptive anomaly detection approach that uses higher-order network representation to detect anomalous sequences. Furthermore, the authors propose a contiguous subsequence anomaly detection approach that identifies abnormal subsequences in the detected anomalous sequences. The proposed approaches are tested by using synthetic and real-world EHR data. The proposed methods outperform existing state of the art anomaly detection techniques. To reduce the computational complexity associated with the operational implementation of the proposed approaches, the Apache Spark environment was leveraged, and a much shorter run time together with improved performance were achieved, especially for data with more than 60,000 sequences.

This paper considers the cyber-attacks that aim to remove nodes or links from network topologies. We particularly focus on one category of such attacks, in which attacks happen by rounds, and in each round, the node with the highest centrality and its adjacent links are removed. Here the centrality can be any centrality measure such as Degree Centrality, Betweenness Centrality, etc. For this attack category, there currently exist two strategies: Initial and Adaptive. In the Initial strategy, node centralities are only calculated initially, while in the Adaptive strategy, node centralities are recalculated after each round of attack. In the literature, it has been shown that the Adaptive strategy is more effective than the Initial strategy for a centrality measure. In this paper, we propose a new strategy called the largest component (LC) strategy which further outperforms the Adaptive strategy in terms of both attack effectiveness and computation complexity. Moreover, we propose the use of current-flow versions of Betweenness Centrality and Closeness Centrality as the centrality measures in the attacks, since they are more granular and supported by the LC strategy. We verify the better performances of the LC strategy by extensive experiments on four kinds of artificial networks and two realworld networks. Our experiments also show that the Currentflow Betweenness Centrality makes attacks the most effective among the five centrality measures studied in this paper.

Recently, there has been a significant interest in the study of the community search problem in large- scale graphs. K-truss as a community model has drawn increasing attention in the literature. In this work, we extend our scope from the community search problems to a more generalized local community query problem based on a triangle- connected k-truss community model. We classify local community query into two categories, community-level and edge-level query, based on the information required to process a given query. We design a two-level index structure that supports both types of queries with multiple query vertices and arbitrary cohesiveness criteria. We conduct extensive experiments using real-world large-scale graphs and compare with the state-of-the-art methods of k-truss community search. The results show that our method outperforms the state-of-the- art works in various types of local k-truss community queries.

With the popularity of social networking services, big social data analytics emerged in various applications, such as discovering trending topics, monitoring public sentiment, and identifying human mobility patterns. In this paper, we take the opportunity of The 2017 Great American Eclipse, a once-in-a-lifetime event, to look into its potential social, emotional, and human movement impacts at the national level. Specifically, we collected more than five million English eclipse- mentioning tweets in a real-time manner using Twitter Streaming APIs. Then we profiled spatio- temporal distributions of the data, extracted both hashtagged and latent topics, analyzed emotions using polarized words, emojis and emoticons, and revealed both interstate and intrastate eclipse- chasing travel patterns. Our study provides a comprehensive example of understanding big social data and its associated influence from diverse perspectives.

One critical challenge of managing modern data center networks lies in that existing network protocols provide limited visibility on the internal routing and forwarding decisions made by the control plane, leading to difficulties on fast diagnosis and identification of root causes for performance bugs and anomalies. In this paper, we develop and evaluate a “debugging mode” for packet forwarding, where we demonstrate a possible design space by introducing a programmable header field into data packets used for diagnosis purposes. These headers can be manipulated by routers in intermediate hops to perform tracing and diagnosis operations, thereby providing much greater visibility on the control plane and data plane operations. To make this design scalable and feasible, we exploit the software APIs provided by the latest software-defined networking (SDN) technologies, where the network control plane is separated from the underlying data plane, so that we can reprogram the network forwarding functions dynamically. Compared to existing alternative approaches, our approach is adaptive and programmable, allowing dynamic and on-demand receiver-side decoding with extremely low overhead. We emphasize that as this “debugging mode” can be enabled and disabled by network managers as demanded, it introduces zero overhead to normal traffic if everything is operating as expected. Our evaluation results on a real SDN network testbed demonstrate the effectiveness of the proposed approaches.

As emojis become prevalent in personal communications, people are always looking for new, interesting emojis to express emotions, show attitudes, or simply visualize texts. In this study, we collected more than thirty million tweets mentioning the word “emoji” in a one-year period to study emoji requests on Twitter. First, we filtered out bot-generated tweets and extracted emoji requests from the raw tweets using a comprehensive list of linguistic patterns. Then, we examined patterns of new emoji requests by exploring their time, locations, and context. Finally, we summarized users' advocacy behaviors and identified expressions of equity, diversity, and fairness issues due to unreleased but expected emojis, and concluded the significance of new emojis on society. To the best of our knowledge, this paper is the first to conduct a systematic, large-scale study on new emoji requests.

Finding approximated shortest paths for extremely large-scale complex networks is a challenging problem, where existing works require large overhead to achieve high accuracy and diversity for estimated paths, especially for large graphs with millions of vertices. In this paper, we propose an online search approach based on preprocessed indexes, to approximate point-to-point shortest paths. The approach is able to find more accurate and diverse paths with limited index overhead and requires low search overhead. Furthermore, a new path degree based index construction algorithm is introduced that can greatly increase the approximation accuracy and involve no additional index overhead. To handle extreme size graphs, we build a query processing system with our algorithm on distributed graph processing platforms. The system also supports parallel processing of online searches to achieve high throughput for a large number of queries. We evaluate our algorithm on various real-world graphs from different disciplines with up to billions of edges, and we demonstrate that our system can process hundreds of thousand queries per second on these graphs with reduced overhead.

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

Power optimization has become a key challenge in the design of large-scale enterprise data centers. Existing research efforts focus mainly on computer servers to lower their energy consumption, while only few studies have tried to address data center networks (DCNs), which can account for 10-20 percent of the total energy consumption of a data center. In this paper, we propose CARPO, a correlation-aware power optimization algorithm that dynamically consolidates traffic flows onto a small set of links and switches in a DCN and then shuts down unused network devices for energy savings. In sharp contrast to existing work, CARPO is designed based on a key observation from the analysis of real DCN traces that the bandwidth demands of different flows do not peak at exactly the same time. As a result, if the correlations among flows are considered in consolidation, more energy savings can be achieved. In addition, CARPO integrates traffic consolidation with link rate adaptation for maximized energy savings. We implement CARPO on a hardware testbed composed of 10 virtual switches configured with a production 48-port OpenFlow switch and 8 servers. Our empirical results with traces from Wikipedia and Yahoo! data centers demonstrate that CARPO can save up to 50 percent of network energy for a DCN, while having only negligible delay increases. CARPO also outperforms two state-of-the-art baselines by 19.6 and 95 percent on energy savings, respectively. Our simulation results with a large-scale DCN also show that CARPO can achieve more energy savings than the baselines for typical DCN topologies, such as fat tree and BCube.

In this work, we focus on applying profiling guided code placement to programs running on resource-constrained sensor motes. Specifically, we model the execution of sensor network programs under nondeterministic inputs as discrete-time Markov processes, and propose a novel approach named Code Tomography to estimate parameters of the Markov models that reflect sensor network programs' dynamic execution behavior by only using end-to-end timing information measured at start and end points of each procedure. The parameters estimated by Code Tomography are fed back to compilers to optimize the code placement so that branch misprediction rate can be reduced.

In many network applications, accurate traffic measurement is critical for bandwidth management with QoS requirements, and detecting security threats such as DoS (Denial of Service) attacks. In such cases, traffic is usually modeled as a collection of flows, which are identified based on certain features such as IP address pairs. One central problem is to identify those "heavy hitter" flows, which account for a large percentage of total traffic, e.g., at least 0.1% of the link capacity. However, the challenge for this goal is that keeping an individual counter for each flow is too slow, costly, and non-scalable. In this paper, we describe a novel data structure called the Probabilistic Bloom Filter (PBF), which extends the classical bloom filter into the probabilistic direction, so that it can effectively identify heavy hitters. We analyze the performance, tradeoffs, and capacity of this data structure. Our study also investigates how to calibrate this data structure's parameters. We also develop two extensions of the basic form of the PBF for more flexible application needs. We use real network traces collected on a Web query server and a backbone router to test the performance of the PBF, and demonstrate that this method can accurately keep track of all objects' frequencies, including websites and flows, so that heavy hitters can be identified with constant time computational complexity and low memory overhead.

The increasing data demands from high-performance computing applications significantly accelerate the capacity, capability and reliability requirements of storage systems. As systems scale, component failures and repair times increase, significantly impacting data availability. A wide array of decision points must be balanced in designing such systems.

Existing social networking services recommend friends to users based on their social graphs, which may not be the most appropriate to reflect a user's preferences on friend selection in real life. In this paper, we present Friendbook, a novel semantic-based friend recommendation system for social networks, which recommends friends to users based on their life styles instead of social graphs. By taking advantage of sensor-rich smartphones, Friendbook discovers life styles of users from user-centric sensor data, measures the similarity of life styles between users, and recommends friends to users if their life styles have high similarity. Inspired by text mining, we model a user's daily life as life documents, from which his/her life styles are extracted by using the Latent Dirichlet Allocation algorithm. We further propose a similarity metric to measure the similarity of life styles between users, and calculate users' impact in terms of life styles with a friend-matching graph. Upon receiving a request, Friendbook returns a list of people with highest recommendation scores to the query user. Finally, Friendbook integrates a feedback mechanism to further improve the recommendation accuracy. We have implemented Friendbook on the Android-based smartphones, and evaluated its performance on both small-scale experiments and large-scale simulations. The results show that the recommendations accurately reflect the preferences of users in choosing friends.

Our work in this paper stems from our insight that recent research efforts on open vehicle routing (OVR) problems, an active area in operations research, are based on similar assumptions and constraints compared to sensor networks. Therefore, it may be feasible that we could adapt these techniques in such a way that they will provide valuable solutions to certain tricky problems in the wireless sensor network (WSN) domain. To demonstrate that this approach is feasible, we develop one data collection protocol called EDAL, which stands for Energy-efficient Delay-aware Lifetime-balancing data collection. The algorithm design of EDAL leverages one result from OVR to prove that the problem formulation is inherently NP-hard. Therefore, we proposed both a centralized heuristic to reduce its computational overhead and a distributed heuristic to make the algorithm scalable for large-scale network operations. We also develop EDAL to be closely integrated with compressive sensing, an emerging technique that promises considerable reduction in total traffic cost for collecting sensor readings under loose delay bounds. Finally, we systematically evaluate EDAL to compare its performance to related protocols in both simulations and a hardware testbed.

With advances in vehicle-to-vehicle communication, future vehicles will have access to a communication channel through which messages can be sent and received when two get close to each other. This enabling technology makes it possible for authenticated users to send queries to those vehicles of interest, such as those that are located within a geographic region, over multiple hops for various application goals. However, a naive method that requires flooding the queries to each active vehicle in a region will incur a total communication overhead that is proportional to the size of the area and the density of vehicles. In this paper, we study the problem of spatial queries for vehicle networks by investigating probabilistic methods, where we only try to obtain approximate estimates within desired confidence intervals using only sublinear overheads. We consider this to be particularly useful when spatial query results can be made approximate or not precise, as is the case with many potential applications. The proposed method has been tested on snapshots from real world vehicle network traces.

Barrier coverage is a critical issue in wireless sensor networks for security applications (e.g., border protection), the performance of which is highly related with locations of sensor nodes. Existing work on barrier coverage mainly assume that sensor nodes have accurate location information, however, little work explores the effects of location errors on barrier coverage. In this paper, we study the barrier coverage problem when sensor nodes have location errors and deploy mobile sensor nodes to improve barrier coverage if the network is not barrier covered after initial deployment. We analyze the relationship between the true distance and the measured distance of two stationary sensor nodes and derive the minimum number of mobile sensor nodes needed to connect them with a guarantee when nodes location errors. Furthermore, we propose a fault tolerant weighted barrier graph, based on which we prove that the minimum number of mobile sensor nodes needed to form barrier coverage with a guarantee is the length of the shortest path on the graph. Simulation results validate the correctness of our analysis.

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

In recent years, non-volatile memory devices such as SSD drives have emerged as a viable storage solution due to their increasing capacity and decreasing cost. Due to the unique capability and capacity requirements in large scale HPC (High Performance Computing) storage environment, a hybrid configuration (SSD and HDD) may represent one of the most available and balanced solutions considering the cost and performance. Under this setting, effective data placement as well as movement with controlled overhead become a pressing challenge. In this paper, we propose an integrated object placement and movement framework and adaptive learning algorithms to address these issues. Specifically, we present a method that shuffle data objects across storage tiers to optimize the data access performance. The method also integrates an adaptive learning algorithm where realtime classification is employed to predict the popularity of data object accesses, so that they can be placed on, or migrate between SSD or HDD drives in the most efficient manner. We discuss preliminary results based on this approach using a simulator we developed to show that the proposed methods can dynamically adapt storage placements and access pattern as workloads evolve to achieve the best system level performance such as throughput.

Barrier coverage is a critical issue in wireless sensor networks for security applications (e.g., border protection) where directional sensors (e.g., cameras) are becoming more popular than omni-directional scalar sensors (e.g., microphones). However, barrier coverage cannot be guaranteed after initial random deployment of sensors, especially for directional sensors with limited sensing angles. In this paper, we study how to efficiently use mobile sensors to achieve \(k\) -barrier coverage. In particular, two problems are studied under two scenarios. First, when only the stationary sensors have been deployed, what is the minimum number of mobile sensors required to form \(k\) -barrier coverage? Second, when both the stationary and mobile sensors have been pre-deployed, what is the maximum number of barriers that could be formed? To solve these problems, we introduce a novel concept of weighted barrier graph (WBG) and prove that determining the minimum number of mobile sensors required to form \(k\) -barrier coverage is related with finding \(k\) vertex-disjoint paths with the minimum total length on the WBG. With this observation, we propose an optimal solution and a greedy solution for each of the two problems. Both analytical and experimental studies demonstrate the effectiveness of the proposed algorithms.

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

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.

Debugging wireless sensor network (WSN) applications has been complicated for multiple reasons, among which the lack of visibility is one of the most challenging. To address this issue, in this paper, we present a systematic approach to record and replay WSN applications at the granularity of instructions. This approach differs from previous ones in that it is purely software based, therefore, no additional hardware component is needed. Our key idea is to combine the static, structural information of the assembly-level code with their dynamic, run-time traces as measured by timestamps and basic block counters, so that we can faithfully infer and replay the actual execution paths of applications at instruction level in a post-mortem manner. The evaluation results show that this approach is feasible despite of the resource constraints of sensor nodes. We also provide two case studies to demonstrate that our instruction level record-and-replay approach can be used to: (1) discover randomness of EEPROM writing time, (2) localize stack smashing bugs in sensor network applications.

Barrier coverage is a critical issue in wireless sensor networks for security applications (e.g., border protection) where directional sensors (e.g., cameras) are becoming more popular and advantageous than omni-directional scalar sensors for the extra dimensional information they provide. However, barrier coverage can not be guaranteed after initial random deployment of sensors, especially for directional sensors with limited sensing angles. In this paper, we study how to efficiently achieve barrier coverage in hybrid directional sensor networks by moving mobile sensors to fill in gaps and form a barrier with stationary sensors. In specific, we introduce the notion of directional barrier graph to model the barrier coverage formation problem. We prove that the minimum number of mobile sensors required to form a barrier with stationary sensors is the length of the shortest path from the source node to the destination node on the directional barrier graph. We then formulate the problem of minimizing the cost of moving mobile sensors to fill in the gaps on the shortest path as a minimum cost bipartite assignment problem, and solve it in polynomial time using the Hungarian algorithm. Both analytical and experimental studies demonstrate the effectiveness of the proposed algorithm.

In many wireless sensor network (WSN) applications, a subset of nodes (source nodes) are selected to sense the environment, generate data, and transmit them back to the sink over multiple hops. Many previous research efforts have tried to achieve trade-offs in terms of delay, energy cost, and load balancing for such data collection tasks. Our work in this paper stems from the insight that, recent research efforts on open vehicle routing (OVR) problems, an active area in operations research, are based on similar assumptions and constraints compared to sensor networks. This insight motivates us to adapt these techniques so that we can solve or prove certain challenging problems in WSN applications. To demonstrate that this approach is feasible, we develop one data collection protocol called EDAL, which stands for Energy-efficient Delay-aware Lifetime-balancing data collection. The algorithm design of EDAL borrows one research result from OVR to prove that its problem formulation is inherently NP-hard. We then proposed both a centralized heuristic to reduce its computational overhead, and a distributed heuristic to make the algorithm scalable for large scale network operations. We also develop EDAL to be closely integrated with compressive sensing, an emerging technique that promises considerable reduction in total traffic cost for collecting sensor readings under loose delay bounds. Finally, we systematically evaluate EDAL to demonstrate its performance superiority compared to related protocols.

Power optimization has become a key challenge in the design of large-scale enterprise data centers. Existing research efforts focus mainly on computer servers to lower their energy consumption, while only few studies have tried to address the energy consumption of data center networks (DCNs), which can account for 20% of the total energy consumption of a data center. In this paper, we propose CARPO, a correlation-aware power optimization algorithm that dynamically consolidates traffic flows onto a small set of links and switches in a DCN and then shuts down unused network devices for energy savings. In sharp contrast to existing work, CARPO is designed based on a key observation from the analysis of real DCN traces that the bandwidth demands of different flows do not peak at exactly the same time. As a result, if the correlations among flows are considered in consolidation, more energy savings can be achieved. In addition, CARPO integrates traffic consolidation with link rate adaptation for maximized energy savings. We implement CARPO on a hardware testbed composed of 10 virtual switches configured with a production 48-port OpenFlow switch and 8 servers. Our empirical results with Wikipedia traces demonstrate that CARPO can save up to 46% of network energy for a DCN, while having only negligible delay increases. CARPO also outperforms two state-of-the-art baselines by 19.6% and 95% on energy savings, respectively. Our simulation results with 61 flows also show the superior energy efficiency of CARPO over the baselines.

With the widespread use of wireless sensor networks (WSN), more types of applications are emerging. However, controlling a deployed wireless sensor network after deployment still requires expertise on embedded system programming and administration. In this paper, we study how to exploit the widely available smartphones to reduce these restrictions on users' expertise. In particular, we present a system called PhoneCon, which stands for Voice-driven SmartPhone Controllable Wireless Sensor Networks. Through PhoneCon, users may simply speak to their phones to operate a deployed wireless sensor network, such as getting the status of deployed motes, without being exposed to any of system or programming level details. We have implemented PhoneCon on Android phones for a testbed of MicaZ sensor nodes. Our evaluation results show that PhoneCon can interpret users' intentions well enough through the microphone and perform corresponding actions with acceptable delays.

WSN applications are prone to bugs and failures due to their typical characteristics, such as being extensively distributed, heavily concurrent, and resource restricted. In this paper, we propose and develop a flexible and iterative WSN debugging system based on sequence mining techniques. At first, we develop a data structure called the vectorized Probabilistic Suffix Tree (vPST), an elastic model to extract and store sequential information from program runtime traces in compact suffix tree based vectors. Then, we build a novel WSN debugging system by integrating vPST with Support Vector Machines (SVM), a robust and generic classifier for both linear and nonlinear data classification tasks. Finally, we demonstrate that the vPST-SVM debugging system is efficient, flexible, and generic by three different test cases, two on the LiteOS operating system and one on the TinyOS operating system.

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

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.

Current smartphones have been equipped with different kinds of sensors and enhanced by powerful mobile operating systems, such as Android OS, iOS, Windows Mobile, Blackberry and Symbian OS. These advantages, however, are not fully utilized by operating smartphone only in isolation. Therefore, we demonstrate Uno, a platform that is specifically designed to allow people to share resources in smartphone environments. Uno allows users to cooperate by sharing their files and sensors under a strong privacy protection. The fundamental idea is to map a smartphone to a networked node by the means of tagged objects in the distributed sharing system and to treat sensors and resources as sub-objects to the smartphones. Sensors or resource sharing are based on different attributes' settings in the system. Furthermore, Uno also supports a user with multiple smartphones. A Uno prototype implemented in Android OS [1] with full features will be shown in this demo.

With the development of social networks, it has been increasingly easier to make friends on the Internet. However, it may not be as easy to automatically find a friend with "similar interests". In this paper, we develop a novel system that allows users with similar interests to be quickly introduced based on the similarity of pictures they took. A real online system, named Friendbook, is implemented on a smartphone network. Due to the limited resources on a smartphone as well as privacy issues, instead of directly comparing the original pictures for similarity measure, Friendbook uses "feature-based" picture comparison. By comparing features extracted from pictures taken by people who want to make friends, their similarity in interests can be automatically inferred based on the content of these pictures. We refer to friends made through Friendbook as "S-friend" for "Semantic-friend". The system also demonstrates the difference between S-friend matching with geographic-based G-friend matching.

This paper derives energy-optimal batching periodsfor asynchronous multistage data processing on sensor nodes in the sense of minimizing energy consumption while meeting end-to-end deadlines. Batching the processing of (sensor) data maximizes processor sleep periods, hence minimizing the wakeup frequency and the corresponding overhead. The algorithm is evaluated on mPlatform, a next-generation heterogeneous sensor node platform equipped with both a low-end microcontroller(MSP430) and a higher-end embedded systems processor (ARM). Experimental results show that the total energy consumption of mPlatform, when processing data flowsat their optimal batching periods, is up to 35% lower than that for uniform period assignment. Moreover, processing data at the appropriate processor can use as much as 80% less energy than running the same task set on the ARM alone and 25% less energy than running the taskset on the MSP430 alone.

In this paper, we present LiteView, an experimental toolkit for end-user diagnosis of communication path problems in sensor network systems. This toolkit provides an on-site, interactive environment that helps answering questions related to the instantaneous communication environments. For example, it allows users to identify broken links or asymmetric links, which are likely to become traffic bottlenecks. It also allows users to identify traffic hotspots by collecting round-trip delays of arbitrary pairs of nodes. Compared to the previous work on sensor network troubleshooting, this toolkit has two key differences. First, its utilities are generic and application independent, allowing users to easily transfer experiences in managing one deployment to another. Second, its utilities are interactive, allowing users to quickly obtain the current status, optimize the deployment decisions, and observe their immediate effects. The utilities provided in this paper are thus promising to identify and solve communication path problems.

This article presents the design, implementation, and evaluation of EnviroMic , a low-cost experimental prototype of a novel distributed acoustic monitoring, storage, and trace retrieval system designed for disconnected operation. Our intended use of acoustic monitoring is to study animal populations in the wild. Since a permanent connection to the outside world is not assumed and due to the relatively large size of audio traces, the system must optimally exploit available resources such as energy and network storage capacity. Towards that end, we design, prototype, and evaluate distributed algorithms for coordinating acoustic recording tasks, reducing redundancy of data stored by nearby sensors, filtering out silence, and balancing storage utilization in the network. For experimentation purposes, we implement EnviroMic on a TinyOS-based platform and systematically evaluate its performance through both indoor testbed experiments and an outdoor deployment. Results demonstrate up to a four-fold improvement in effective storage capacity of the network compared to uncoordinated recording.

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

Visibility has been a key challenge for wireless sensor network applications. Deployed on the extremely resource-constrained mote platform, such applications may fail unexpectedly, or exhibit behavior different from their intended goals. To help understand why such problems occur, we design and implement an event trace logger based on the LiteOS operating system, which allows us to partially reconstruct application behavior after execution, such as which path it took for an IF statement, its invocation history of the kernel system calls, and its dynamics across multiple nodes. We plan to demonstrate the usefulness of this event trace logger and its translator using a multi-hop routing application.

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

This paper introduces the abstraction of energy reserves for sensor networks that virtualizes energy sources. It gives each of several applications sharing a platform the illusion of having its own private energy source. Energy virtualization is the next logical step in embedded systems after visualizing communication links and CPU capacity. Energy virtualization has not been addressed in past sensor network literature because most current wireless sensor networks feature single-user applications. To amortize deployment costs, future sensor networks, deployed in remote or hard- to-access areas, will likely be leveraged by scientists from different disciplines, each having their independent application for their individual research purposes. Platforms, planned for such deployment, will befitted with the union of sensors needed, but independent applications will share the remaining resources such as in-field storage and communication bandwidth, calling for quotas and isolation mechanisms. The most expensive resource shared in sensor networks is energy. This paper provides an energy isolation mechanism, called the virtual battery, that logically divides energy among applications to provide each its private energy reserve. An application can manage its private energy independently as if it were running alone on the platform. The application is terminated when its reserve is depleted. We implement and evaluate this abstraction on MicaZ motes running LiteOS. Our results show that the virtual battery mechanism succeeds at exporting the private reserve abstraction accurately and at a low overhead.

Effective debugging usually involves watching program state to diagnose bugs. When debugging sensor network applications, this approach is often time-consuming and errorprone, not only because of the lack of visibility into system state, but also because of the difficulty to watch the right variables at the right time. In this paper, we present declarative tracepoints, a debugging system that allows the user to insert a group of action-associated checkpoints, or tracepoints, to applications being debugged at runtime. Tracepoints do not require modifying application source code. Instead, they are written in a declarative, SQL-like language called TraceSQL independently. By triggering the associated actions when these checkpoints are reached, this system automates the debugging process by removing the human from the loop. We show that declarative tracepoints are able to express the core functionality of a range of previously isolated debugging techniques, such as EnviroLog, NodeMD, Sympathy, and StackGuard. We describe the design and implementation of the declarative tracepoints system, evaluate its overhead in terms of CPU slowdown, illustrate its expressiveness through the aforementioned debugging techniques, and finally demonstrate that it can be used to detect real bugs using case studies of three bugs based on the development of the LiteOS operating system.

This paper presents EnviroMic, a novel distributed acoustic monitoring, storage, and trace retrieval system. Audio represents one of the least exploited modalities in sensor networks to date. The relatively high frequency and large size of audio traces motivate distributed algorithms for coordinating recording tasks, reducing redundancy of data stored by nearby sensors, filtering out silence, and balancing storage utilization in the network. Applications of acoustic monitoring with EnviroMic range from the study of mating rituals and social behavior of animals in the wild to audio surveillance of military targets. EnviroMic is designed for disconnected operation, where the luxury of having a basestation cannot be assumed. We implement the system on a Tiny OS-based platform and systematically evaluate its performance through both indoor testbed experiments and a preliminary outdoor deployment. Results demonstrate up to a 4-fold improvement in effective storage capacity of the network compared to uncoordinated recording.

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

Sensor networks introduce a new application domain and set of challenges in distributed computing including new network-level programming languages, global system abstractions, and general-purpose communication protocols. These challenges are brought about by the tight integration of computation, communication, and distributed real-time interaction with the physical world. With the growing interest in interconnecting different sensor networks across a wide-area communication infrastructure, an overarching challenge becomes one of arriving at an agreed-upon global sensor network architecture that ensures interoperability. Unlike the Internet, where a layered communication stack (namely, the TCP/IP stack) defines the network architecture, a sensor network architecture must unify not only communication interfaces but also programming interfaces, since network communication and computation functions are tightly intertwined. In that sense, the sensor network architecture refers to a layered stack of distributed computing abstractions. This paper presents an architecture and key considerations in designing and interconnecting local and global sensor networks. Candidate protocols and middleware instantiations are described from the authors' ongoing work that meet the discussed considerations

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

Environmental wireless sensor network (EWSN) systems are deployed in potentially harsh and remote environments where inevitable node and communication failures must be tolerated. LUSTER---Light Under Shrub Thicket for Environmental Research---is a system that meets the challenges of EWSNs using a hierarchical architecture that includes distributed reliable storage, delay-tolerant networking, and deployment time validation techniques.

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

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

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

No abstract available.

In this article, we present logical coordinates based routing (LCR), a novel framework for scalable and location-independent routing in wireless sensor networks. LCR assigns each node a logical coordinate vector, and routes packets following these vectors. We demonstrate that LCR (i) guarantees packet delivery with a high probability, (ii) finds good paths, and (iii) exhibits robust performance in the presence of network voids and node failures. We systematically evaluate the performance of LCR through simulations and compare it with other state-of-the-art protocols. We also propose two extensions of LCR, one for three-dimensional node deployments and the other for unreliable wireless links.

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

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

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

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

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

Routing is one of the key challenges in sensor networks that directly affects the information throughput and energy expenditure. Geographic routing is the most scalable routing scheme for statically placed nodes in that it uses only a constant amount of per-node state regardless of network size. The location information needed for this scheme, however, is not easy to compute accurately using current localization algorithms. In this paper, we propose a novel logical coordinate framework that encodes connectivity information for routing purposes without the benefit of geographic knowledge, while retaining the constant-state advantage of geographic routing. In addition to efficiency in the absence of geographic knowledge, our scheme has two important advantages: (i) it improves robustness in the presence of voids compared to other logical coordinate frameworks, and (ii) it allows inferring bounds on route hop count from the logical coordinates of the source and destination nodes, which makes it a candidate for use in soft real-time systems. The scheme is evaluated in simulation demonstrating the advantages of the new protocol.