Interdependent cyber-physical systems (CPS) connect physical resources between independently motivated actors who seek to maximize profits while providing physical services to consumers. Cyberattacks in seemingly distant parts of these systems have local consequences, and techniques are needed to analyze and optimize defensive costs in the face of increasing cyber threats. This paper presents a technique for transforming physical interconnections between independent actors into a dependency analysis that can be applied to find optimal defensive investment strategies to protect assets from financially motivated adversaries in electric power grids.

Wireless sensor networks (WSNs) are plagued by the possibility of bugs manifesting only at deployment. However, debugging deployed WSNs is challenging for several reasons— the remote location of deployed sensor nodes, the non-determinism of execution that can make it difficult to replicate a buggy run, and the limited hardware resources available on a node. In particular, existing solutions to record and replay debugging in WSNs fail to capture the complete code execution, thus negating the possibility of a faithful replay and causing a large class of bugs to go unnoticed. In short, record and replay logs a trace of predefined events while a deployed application is executing, enabling replaying of events later using debugging tools. Existing recording methods fail due to the many sources of non-determinism and the scarcity of resources on nodes. In this paper we introduce Trace And Replay Debugging In Sensornets (Tardis), a software-only approach for deterministic record and replay of WSN nodes. Tardis is able to record all sources of non-determinism, based on the observation that such information is compressible using a combination of techniques specialized for respective sources. Despite their domain-specific nature, the techniques presented are applicable to the broader class of resource-constrained embedded systems. We empirically demonstrate the viability of our approach and its effectiveness in diagnosing a newly discovered bug in a widely used routing protocol.

There are many large infrastructures that instrument everything from network performance metrics to user activities. However, the collected data are generally used for long-term planning instead of improving reliability and user experience in real time. In this paper, we present our vision of how such collections of data can be used in real time to enhance the dependability of cellular network services. We first discuss mitigation mechanisms that can be used to improve reliability, but incur a high cost which prohibit them to be used except in certain conditions. We present two case studies where analyses of real cellular network traffic data show that we can identify these conditions.

This paper studies the network isolation attack, a devastating type of attacks on cyber-physical systems. In this attack, an adversary compromises a set of nodes that enclose a region in order to isolate the region from the rest of the network. Assuming that the compromised nodes wish not to be detected, we propose a solution to defend against the network isolation attack. Our goal is to achieve the following security guarantee: either a legitimate node can successfully deliver a message to another legitimate node, or the network control center can identify a small set of suspect nodes, which are guaranteed to contain a compromised node. Toward achieving this goal, we develop two protocols: one is for secure delivery of messages among nodes and the other is for secure collection of messages from nodes at the network control center. We show that our proposed protocols are provably secure, i.e., attain the aforementioned security guarantee. Further, our protocols achieve this guarantee with overhead that is orders-of-magnitude smaller than existing baseline protocols. Our proposed protocols are thus scalable for large networks.

Event monitoring is a common application in wireless sensor networks. For event monitoring, a number of sensor nodes are deployed to monitor certain phenomenon. When an event is detected, the sensor nodes report it to a base station (BS), where a network operator can take appropriate action based on the event report. In this paper, we are interested in scenarios where the event must be reported within a time bound to the BS possibly over multiple hops. However, such event reports can be hampered by compromised nodes in the middle that drop, modify, or delay the event report. To defend against such an attack, we propose SEM, a Secure Event Monitoring protocol against arbitrary malicious attacks by Byzantine adversary nodes. SEM provides the following provable security guarantees. As long as the compromised nodes want to stay undetected, a legitimate sensor node can report an event to the BS within a bounded time. If the compromised nodes prevent the event from being reported to the BS within the bounded time, the BS can identify a pair of nodes that is guaranteSchool of Electrical and Computer Engineeringed to contain at least one compromised node. To the best of our knowledge, no prior work in the literature can provide such guarantees. SEM is designed to use the minimumlevel of asymmetric cryptography during normal operationwhenthere is no attack, and use cryptographic primitives more liberallywhenan attack is detected. This design has the advantage that the overall SEM protocol is lightweight in terms of the computational resources and the network traffic required by the cryptographic operations. We also show an operational example of SEM using TOSSIM simulations.

This paper studies an optimal monitoring problem for behavior-based detection in multichannel multi-radio wireless mesh networks. In behavior-based detection, nodes overhear communications in their neighborhood to determine if the behaviors of their neighbors are legitimate. The objective of this work is to maximize the number of nodes being monitored by judiciously choosing a set of monitoring nodes and also channels for the chosen monitoring nodes. This problem is NP-hard, growing exponentially with the number of monitoring nodes. We develop three approximation algorithms, each of which achieves at least a constant factor of the optimum. Furthermore, one of our algorithms achieves the best possible approximation ratio among all polynomial-time algorithms, unless P = NP. We conduct simulations in random networks and scale-free networks to evaluate the coverage and the execution time of the three algorithms.

In this paper, we put forward the notion that systems management for large masses of virtual machines in data centers is going to be done differently in the short to medium term future?through smart phones and through controlled crowdsourcing to a variety of experts within an organization, rather than dedicated system administrators alone. We lay out the research and practitioner challenges this model raises and give some preliminary solution directions that are being developed, here at IBM and elsewhere.

This paper studies the optimal sniffer-channel assignment for reliable monitoring in multi-channel wireless networks. This problem concerns how to deploy certain sniffers in a network (and tune their channels) so that they can overhear and verify communication among the other nodes, referred to as normal nodes. Prior works have studied the optimal sniffer-channel assignment, but they assume perfect sniffers. However, in practice, sniffers may probabilistically make errors in monitoring, e.g., due to poor reception and compromise by an adversary. Hence, to maintain acceptable monitoring quality, a node needs to be overheard by multiple sniffers. We show that the optimal sniffer-channel assignment with sniffer redundancy differs fundamentally from the previous works due to the absence of a desirable property called submodularity. As a result, in our problem, the prior approximation algorithms no longer maintain their performance guarantees. We propose a variety of approximation algorithms based on two approaches?greedy strategy and relaxation-and-rounding approach. We present an empirical performance analysis of the proposed algorithms through simulations in practical networks. Our results suggest that our two algorithms show a performance trade-off between coverage and running time and are therefore suitable for different kinds of deployment.

Wireless reprogramming of sensor nodes is an essential requirement for long-lived networks because software functionality needs to be changed over time. The amount of information that needs to be wirelessly transmitted during reprogramming should be minimized to reduce reprogramming time and energy. In this paper, we present a multihop incremental reprogramming system called Hermes that transfers over the network the delta between the old and new software and lets the sensor nodes rebuild the new software using the received delta and the old software. It reduces the delta by using techniques to mitigate the effects of function and global variable shifts caused by the software modifications. Then it compares the binary images at the byte level with a method to create a small delta that needs to be sent over the wireless network to all the nodes. For the wide range of software change scenarios that we experimented with, we find that Hermes transfers up to 201 times less information than Deluge, the standard reprogramming system for TinyOS, and 64 times less than an existing incremental reprogramming system by Jeong and Culler.

Congestion control in multi-hop infrastructure wire- less mesh networks is both an important and a unique problem. It is unique because it has two prominent causes of failed transmissions which are difficult to tease apart - lossy nature of wireless medium and high extent of congestion around gateways in the network. The concurrent presence of these two causes limits applicability of already available congestion control mechanisms, proposed for wireless networks. Prior mechanisms mainly focus on the former cause, ignoring the latter one. Therefore, we address this issue to design an end-to-end congestion control mechanism for infrastructure wireless mesh networks in this paper. We formulate the congestion control problem and map that to the restless multi-armed bandit problem, a well-known decision problem in the literature. Then, we propose three myopic policies to achieve a near-optimal solution for the mapped problem since no optimal solution is known to this problem. We perform comparative evaluation through ns-2 simulation and a real testbed experiment with a wireline TCP variant and a wireless TCP protocol. The evaluation reveals that our proposed mechanism can achieve up to 52% increased network throughput and 34% decreased average energy consumption per transmitted bit in comparison to the other end-to-end congestion control variants.

Over the last three years, Android has established itself as the largest-selling operating system for smartphones. It boasts of a Linux-based robust kernel, a modular framework with multiple components in each application, and a security- conscious design where each application is isolated in its own virtual machine. However, all of these desirable properties would be rendered ineffectual if an application were to deliver erroneous messages to targeted applications and thus cause the target to behave incorrectly. In this paper, we present an empir- ical evaluation of the robustness of Inter-component Commu- nication (ICC) in Android through fuzz testing methodology, whereby, parameters of the inter-component communication are changed to various incorrect values. We show that not only exception handling is a rarity in Android applications, but also it is possible to crash the Android runtime from unprivileged user processes. Based on our observations, we highlight some of the critical design issues in Android ICC and suggest solutions to alleviate these problems.

It is important to get an idea of the events occurring in an embedded wireless node when it is deployed in the field, away from the convenience of an interactive debugger. Such visibility can be useful for post-deployment testing, replaybased debugging, and for performance and energy profiling of various software components. Prior software-based solutions to address this problem have incurred high execution overhead and intrusiveness. The intrusiveness changes the intrinsic timing behavior of the application, thereby reducing the fidelity of the collected profile. Prior hardware-based solutions have involved the use of dedicated ASICs or other tightly coupled changes to the embedded node?s processor, which significantly limits their applicability. In this paper, we present AVEKSHA, a hardware-software approach for achieving the above goals in a non-intrusive manner. Our approach is based on the key insight that most embedded processors have an on-chip debug module (which has traditionally been used for interactive debugging) that provides significant visibility into the internal state of the processor. We design a debug board that interfaces with the on-chip debug module of an embedded node?s processor through the JTAG port and provides three modes of event logging and tracing: breakpoint, watchpoint, and program counter polling. Using expressive triggers that the onchip debug module supports, AVEKSHA can watch for, and record, a variety of programmable events of interest. A key feature of AVEKSHA is that the target processor does not have to be stopped during event logging (in the last two of the three modes), subject to a limit on the rate at which logged events occur. AVEKSHA also performs power monitoring of the embedded wireless node and, importantly, enables power consumption data to be correlated to events of interest. AVEKSHA is an operating system-agnostic solution. We demonstrate its functionality and performance using three applications running on the TelosB motes; two in TinyOS and one in Contiki. We show that AVEKSHA can trace tasks and other generic events and can perform energy monitoring at function and task-level granularity. We also describe how we used AVEKSHA to find a subtle bug in the TinyOS low power listening protocol.

This paper studies an optimal channel assignment problem for passive monitoring in multi-channel wireless networks, where a set of sniffers capture and analyze the network traffic to monitor the network. The objective of this problem is to maximize the total amount of traffic captured by sniffers by judiciously assigning the radios of sniffers to a set of channels. This problem is NP-hard, with the computational complexity growing exponentially with the number of sniffers. We develop distributed online solutions to this problem for large-scale and dynamic networks. Prior works have attained a constant factor1 - 1/e of the maximum monitoring coverage in a centralized setting. Our algorithm preserves the same ratio while providing a distributed solution that is amenable to online implementation. Also, our algorithm is cost-effective, in terms of communication and computational overheads, due to the use of only local communication and the adaptation to incremental network changes. We present two operational modes of our algorithm for two types of networks that have different rates of network changes. One is a proactive mode for fast varying networks, while the other is a reactive mode for slowly varying networks. Simulation results demonstrate the effectiveness of the two modes of our algorithm.

Wireless reprogramming of sensor nodes is an essential requirement for long-lived networks since software functionality needs to be changed over time. During reprogramming, the number of radio transmissions should be minimized, since reprogramming time and energy depend chiefly on the number of radio transmissions. In this article, we present a multihop incremental reprogramming protocol called Zephyr that transfers the delta between old and new software versions, and lets the sensor nodes rebuild the new software using the received delta and the old software. Zephyr reduces the delta size by using application-level modifications to mitigate the effects of function shifts. Then it compares the two binary images at the byte level to generate a small delta, that is then sent over the wireless network to all the nodes. For the wide range of software change cases that we used as benchmarks, Zephyr transfers 1.83 to 1987 times less traffic through the network than Deluge (the standard nonincremental reprogramming protocol for TinyOS) and 1.14 to 49 times less traffic than an existing incremental reprogramming protocol by Jeong and Culler [2004].

Due to resource constraints and unreliable communication, wireless sensor network (WSN) programming and debugging remain to be challenging tasks. Deterministic replay is an error diagnosis method which has long been proposed for distributed systems. However, one of the significant hurdles for applying deterministic replay on WSN is posed by the small program memory on typical sensor nodes. This paper proposes a dependence-based multi-level method for memory-efficient tracing and replay. In the interest of portability across different hardware platforms, the method is implemented as a source-level tracing and replaying tool. To further reduce the code size after tracing instrumentation, a cost model is used for making the decision on which functions to in-line. A prototype for the tool targets C programs is developed on top of the Open64 compiler and is tested using several TinyOS applications running on TelosB motes. Preliminary experimental results show that the test programs, which do not fit the program memory after straightforward instrumentation, can be successfully instrumented using the new method such that the injected errors can be found.

In wireless ad-hoc and sensor networks, neighbor discovery is one of the first steps performed by a node upon deployment and disrupting it adversely affects a number of routing, MAC, topology discovery and intrusion detection protocols. It is especially harmful when an adversary can convince nodes that it is a legitimate neighbor, which it can do easily and without the use of cryptographic primitives. In this paper, we develop a secure neighbor discovery protocol, SEDINE, for static multihop wireless networks. We prove that, in the absence of packet losses, without using any centralized trusted node or specialized hardware, SEDINE prevents any node, legitimate or malicious, from being incorrectly added to the neighbor list of another legitimate node that is not within its transmission range. We provide simulation results to demonstrate the efficacy of SEDINE, in the presence of packet losses.

Stealthy packet dropping is a suite of four attacks --- misrouting, power control, identity delegation and colluding collision --- that can be easily launched against multihop wireless ad hoc networks. Stealthy packet dropping disrupts the packet from reaching the destination through malicious behavior at an intermediate node. However, the malicious node gives the impression to its neighbors that it performs the legitimate forwarding action. Moreover, a legitimate node comes under suspicion. A popular method for detecting attacks in wireless networks is behaviorbased detection performed by normal network nodes through overhearing the communication in their neighborhood. This leverages the open broadcast nature of wireless communication. An instantiation of this technology is local monitoring. We show that local monitoring, and the wider class of overhearing-based detection, cannot detect stealthy packet dropping attacks. Additionally, it mistakenly detects and isolates a legitimate node. We present a protocol called SADEC that can detect and isolate stealthy packet dropping attack efficiently. SADEC presents two techniques that can be overlaid on basic local monitoring: having the neighbors maintain additional information about the routing path, and adding some checking responsibility to each neighbor. Additionally, SADEC provides an innovative mechanism to better utilize local monitoring by considerably increasing the number of nodes in a neighborhood that can do monitoring. We show through analysis and simulation experiments that basic local monitoring fails to efficiently mitigate most of the presented attacks while SADEC successfully mitigates them.

Because of transient wireless link failures, incremental node deployment, and node mobility, existing information dissemination protocols used in wireless ad-hoc and sensor networks cause nodes to periodically broadcast "advertisement" containing the version of their current data item even in the "steady state" when no dissemination is being done. This is to ensure that all nodes in the network are up-to-date. This causes a continuous energy expenditure during the steady state, which is by far the dominant part of a network?s lifetime. In this paper, we present a protocol called Varuna which incurs a constant energy cost, independent of the duration of the steady state. In Varuna, nodes monitor the traffic pattern of the neighboring nodes to decide when an advertisement is necessary. Using testbed experiments and simulations, we show that Varuna achieves several orders of magnitude energy savings compared to Trickle, the existing standard for dissemination in sensor networks, at the expense of a reasonable amount of memory for state maintenance.

Data aggregation in wireless sensor networks is vulnerable to security attacks and natural failures. A few nodes can drastically alter the result of the aggregation by reporting erroneous data. In this paper we present RDAS, a robust data aggregation protocol that uses a reputation-based approach to identify and isolate malicious nodes in a sensor network. RDAS is based on a hierarchical clustering arrangement of nodes, where a cluster head analyzes data from the cluster nodes to determine the location of an event. It uses the redundancy of multiple nodes sensing an event to determine what data should have been reported by each node. Nodes form part of a distributed reputation system, where they share information about other node?s performance in reporting accurate data and use the reputation ratings to suppress the reports from malicious nodes. RDAS is able to perform accurate data aggregation in the presence of individually malicious and colluding nodes, as well as nodes that try to compromise the integrity of the reputation system by lying about other nodes? behavior. We show that RDAS is more resilient to security attacks with respect to accuracy of event localization than the baseline data aggregation protocol with no security feature.

A specific application for wastewater monitoring and actuation, called SwimNet, deployed city-wide in a mid-sized US city, posed some challenges to a time synchronization protocol. The nodes in SwimNet have a low duty cycle (2% in current deployment) and use an external clock, called the Real Time Clock (RTC), for triggering the sleep and the wake-up. The RTC has a very low drift (2 ppm) over the wide range of temperature fluctuations that the SwimNet nodes have, while having a low power consumption (0.66 mW). However, these clocks will still have to be synchronized occasionally during the long lifetime of the Swim-Net nodes and this was the problem we confronted with our time synchronization protocol. The RTC to fit within the power and the cost constraints makes the tradeoff of having a coarse time granularity of only 1 second. Therefore, it is not sufficient to synchronize the RTC itself?that would mean a synchronization error of up to 1 second would be possible even with a perfect synchronization protocol. This would be unacceptable for the low duty cycle operation?each node stays awake for only 6 seconds in a 5 minute time window. This was the first of three challenges for time synchronization. The second challenge is that the synchronization has to be extremely fast since ideally the entire network should be synchronized during the 6 second wake-up period. Third, the long range radio used for the metropolitan-scale SwimNet does not make its radio stack software available, as is seen with several other radios for long-range ISM band RF communication. Therefore, a common technique for time synchronization?MAC layer time-stamping?cannot be used. Additionally, MAC layer time-stamping is known to be problematic with high speed radios (even at 250 kbps).
We solve these challenges and design a synchronization protocol called HARMONIA. It has three design innovations. First, it uses the finely granular microcontroller clock to achieve synchronization of the RTC, such that the synchronization error, despite the coarse granularity of the RTC, is in the microsecond range. Second, HARMONIA pipelines the synchronization messages through the network resulting in fast synchronization of the entire network. Third, HARMONIA provides failure handling for transient node and link failures such that the network is not overburdened with synchronization messages and the recovery is done locally. We evaluate HARMONIA on SwimNet nodes and compare the two metrics of synchronization error and synchronization speed with FTSP. It performs slightly worse in the former and significantly better in the latter.

Ad-hoc wireless networks are being deployed in critical applications that require protection against sophisticated adversaries. However, wireless routing protocols, such as the widely-used AODV, are often designed with the assumption that nodes are benign. Cryptographic extensions such as Secure AODV (SAODV) protect against some attacks but are still vulnerable to easily-performed attacks using colluding adversaries, such as the wormhole attack. In this paper, we make two contributions to securing routing protocols. First, we present a protocol called Route Verification (RV) that can detect and isolate malicious nodes involved in routingbased attacks with very high likelihood. However, RV is expensive in terms of energy consumption due to its radio communications. To remedy the high energy cost of RV, we make our second contribution. We propose a multigrade monitoring (MGM) approach. The MGM approach employs a previously developed lightweight local monitoring technique to detect any necessary condition for an attack to succeed. However, local monitoring suffers from false positives due to collisions on the wireless channel. When a necessary condition is detected, the heavy-weight RV protocol is triggered. We show through simulation that MGM applied to AODV generally requires little extra energy compared to baseline AODV, under the common case where there is no attack present. It is also more resource-efficient and powerful than SAODV in detecting attacks. Our work, for the first time, lays out the framework of multigrade monitoring, which we believe fundamentally addresses the tension between security and resource consumption in ad-hoc wireless networks.

Sensor networks enable a wide range of applications in both military and civilian domains. However, the deployment scenarios, the functionality requirements, and the limited capabilities of these networks expose them to a wide-range of attacks against control traffic (such as wormholes, rushing, Sybil attacks, etc) and data traffic (such as selective forwarding). In this paper we propose a framework called UNMASK that mitigates such attacks by detecting, diagnosing, and isolating the malicious nodes. UNMASK uses as a fundamental building block the ability of a node to oversee its neighboring nodes? communication. On top of UNMASK, we build a secure routing protocol, LSR, that provides additional protection against malicious nodes by supporting multiple node-disjoint paths. We analyze the security guarantees of UNMASK and use ns-2 simulations to show its effectiveness against representative control and data attacks. The overhead analysis we present shows that UNMASK is a lightweight protocol appropriate for securing resource constrained sensor networks.

Wireless reprogramming of sensor nodes is an essential requirement for long-lived networks since the software functionality changes over time. The amount of information that needs to be wirelessly transmitted during reprogramming should be minimized since reprogramming time and energy depend chiefly on the amount of radio transmissions. In this paper, we present a multihop incremental reprogramming protocol called Zephyr that transfers the delta between the old and the new software and lets the sensor nodes rebuild the new software using the received delta and the old software. It reduces the delta size by using application-level modifications to mitigate the effects of function shifts. Then it compares the binary images at the byte-level with a novel method to create small delta, that is then sent over the wireless network to all the nodes. For a wide range of softwarechange cases that we experimented with, we find that Zephyr transfers 1.83 to 1987 times less traffic through the network than Deluge, the standard reprogramming protocol for TinyOS, and 1.14 to 49 times less than an existing incremental reprogramming protocol by Jeong and Culler.

Wireless mesh networks (WMN) are finding increasing usage in city-wide deployments for providing network connectivity. Mesh routers in WMNs typically use multiple wireless channels to enhance the spatial-reuse of frequency bands, often with multiple radios per node. Due to the cooperative nature of WMNs, they are susceptible to many attacks that cannot be defeated by using traditional cryptographic mechanisms of authentication or encryption alone. A solution approach commonly used for defending against such attacks is behavior-based detection in which some nodes overhear communication in their neighborhood to determine if the behavior by a neighbor is legitimate. It has been proposed to use specialized monitoring nodes deployed strategically throughout the network for performing such detection. The problem that arises is where to deploy these monitoring nodes, how to minimize their number, and which channels to tune their radios to, such that the maximum part of the network can be covered. This problem has been solved for single channel networks by a greedy approximation algorithm since the exact solution is NP-hard. The greedy algorithm achieves the best performance, in terms of the worst case, possible among all polynomial-time algorithms provided that P != NP. In this paper, we solve the problem for multi-channel multi-radio WMNs. The intuitive extension of the greedy algorithm destroys the property of best performance. Instead, we formulate the problem as an integer linear program, solve its linear program relaxation, and then use two rounding techniques that we develop by adapting existing rounding schemes. We thereby present two approximation algorithms. The first, computationally-light algorithm, called probabilistic rounding algorithm gives an expected best performance in the worst case. The second, called deterministic rounding algorithm achieves the best worst-case performance in a deterministic manner. To evaluate how the three algorithms perform in practice, we simulate them in random networks and scale-free networks.

Wireless reprogramming of sensor nodes is a requirement for long-lived networks due to changes in the functionality of the software running on the nodes. The amount of information that needs to be wirelessly transmitted during reprogramming should be minimized to reduce reprogramming time and energy. In this paper, we present a multi-hop incremental reprogramming protocol called Hermes that transfers the delta between the old and new software and lets the sensor nodes rebuild the new software using the received delta and the old software. It reduces the delta by using techniques to mitigate the effects of function and global variable shifts caused by the software modifications. Then it compares the binary images at the byte level with a method to create small delta that needs to be sent over the wireless network to all the nodes. For a wide range of software change scenarios that we experimented with, we find that Hermes transfers up to 201 times less information than Deluge, the standard reprogramming protocol for TinyOS and 64 times less than an existing incremental reprogramming protocol by Jeong and Culler.

Wireless reprogramming of a sensor network is useful for uploading new code or for changing the functionality of existing code. Reprogramming may be done multiple times during a node?s lifetime and therefore a node has to remain receptive to future code updates. Existing reprogramming protocols, including Deluge, achieve this by bundling the reprogramming protocol and the application as one code image which is transferred through the network. The reprogramming protocol being complex, the overall size of the program image that needs to be transferred over the wireless medium increases, thereby increasing the time and energy required for reprogramming a network. We present a protocol called Stream that significantly reduces this bloat by using the facility of having multiple code images on the node. It pre-installs the reprogramming protocol as one image and equips the application program with the ability to listen to new code updates and switch to this image. For a sample application, the increase in size of the application image is 1 page (48 packets of 36 bytes each) for Stream and 11 pages for Deluge. Additionally, we design an opportunistic sleeping scheme whereby nodes can sleep during the period when reprogramming has been initiated but has not yet reached the neighborhood of the node. The savings become significant for large networks and for frequent reprogramming. We implement Stream on Mica2 motes and conduct testbed and simulation experiments to compare delay and energy consumption for different network sizes with respect to the state-of-the-art Deluge protocol.

In many reliable Wireless Sensor Network (WSN) applications, messages have different priorities depending on urgency or importance. For example, a message reporting the failure of all nodes in a region is more important than that for a single node. Moreover, traffic can be bursty in nature, such as when a correlated error is reported by multiple nodes running identical code. Current communication layers in WSNs lack efficient support for these two requirements. We present a priority-driven communication layer, called SeNDORComm, which schedules transmission of packets driven by application-specified priority, buffers and packs multiple messages in a packet, and honors the latency guarantee for a message. We show that SeNDORComm improves energy efficiency, message reliability, and network utilization and delays congestion in a network. We extensively evaluate SeNDORComm using analysis, simulation, and testbed experiments. We demonstrate the improvement in goodput of SeNDORComm over the default communication layer, GenericComm in TinyOS (134.78% for a network of 20 nodes).

Local monitoring has been demonstrated as a powerful technique for mitigating security attacks in multi-hop ad-hoc networks. In local monitoring, nodes overhear partial neighborhood communication to detect misbehavior such as packet drop or delay. However, local monitoring as presented in the literature is vulnerable to a class of attacks that we introduce here called stealthy packet dropping. Stealthy packet dropping disrupts the packet from reaching the destination by malicious behavior at an intermediate node. However, the malicious node gives the impression to its neighbors that it performed the legitimate forwarding action. Moreover, a legitimate node comes under suspicion. We introduce four ways of achieving stealthy packet dropping, none of which is currently detectable. We provide a protocol called MISPAR based on local monitoring to remedy each attack. It presents two techniques ? having the neighbors maintain additional information about the routing path, and adding some checking responsibility to each neighbor. We show through analysis and simulation that the basic local monitoring fails to mitigate any of the presented attacks while MISPAR successfully mitigates them.

Wireless reprogramming of the sensor network is useful for uploading new code or for changing the functionality of the existing code. In recent years, the research focus has shifted from single hop reprogramming to multi-hop reprogramming primarily because of its ease of use. Practical experience from a multi-hop sensor network for monitoring water pollution, called CSOnet, deployed in South Bend, IN, indicates that single-hop reprogramming may be preferable under certain conditions to minimize reprogramming time and energy. In this, the user gets close to a node to be reprogrammed and wirelessly reprograms a single node at a time. The choice between single hop and multi-hop reprogramming depends on factors like network size, node density and most importantly, link reliabilities. We present a protocol called DStream having both single and multi-hop reprogramming capabilities. We provide mathematical analysis and results from testbed experiments (including experiments conducted on CSOnet networks) and simulations to give insights into the choice of the two reprogramming methods for various network parameters.

The increased need for security in embedded applications in recent years has prompted efforts to develop encryption/decryption algorithms capable of running on resource-constrained systems. The inclusion of the Advanced Encryption Standard (AES) in the IEEE 802.15.4 Zigbee protocol has driven its widespread use in current embedded platforms.We propose an implementation of AES in a high-level language (C in this case) that is the first software-based solution for 16-bit microcontrollers capable of matching the communication rate of 250 kbps specified by the Zigbee protocol, while also minimizing RAM and ROM usage. We discuss a series of optimizations and their effects that lead to our final implementation achieving an encryption speed of 286 kbps, RAM usage of 260 bytes, and code size of 5160 bytes on the Texas Instruments MSP430 microprocessor. We also develop rigorous benchmark experiments to compare other AES implementations on a common platform, and show that our implementation outperforms the best available implementation by 85%.

As sensor networks operate over long periods of deployment in difficult to reach places, their requirements may change or new code may need to be uploaded to them. The current state of the art protocols (Deluge and MNP) for network reprogramming perform the code dissemination in a multi-hop manner using a three way handshake whereby meta-data is exchanged prior to code exchange to suppress redundant transmissions. The code image is also pipelined through the network at the granularity of pages. In this paper we propose a protocol called Freshet for optimizing the energy for code upload and speeding up the dissemination if multiple sources of code are available. The energy optimization is achieved by equipping each node with limited non-local topology information, which it uses to determine the time when it can go to sleep since code is not being distributed in its vicinity. The protocol to handle multiple sources provides a loose coupling of nodes to a source and disseminates code in waves each originating at a source, with mechanism to handle collisions when the waves meet. The protocol?s performance with respect to reliability, delay, and energy consumed, is demonstrated through analysis, simulation, and implementation on the Berkeley mote platform.

This paper presents a hierarchical approach for detecting faults in wireless sensor networks (WSNs) after they have been deployed. The developers of WSNs can specify ?invariants? that must be satisfied by the WSNs. We present a framework, Hierarchical SEnsor Network Debugging (H-SEND), for lightweight checking of invariants. H-SEND is able to detect a large class of faults in data gathering WSNs and leverages the existing message flow in the network by buffering and piggybacking messages. H-SEND checks as closely to the source of a fault as possible, pinpointing the fault quickly and efficiently in terms of additional network traffic. Therefore, H-SEND is suited to bandwidth or communication energy constrained networks. A specification expression is provided for specifying invariants so that a protocol developer can write behavioral level invariants. We hypothesize that data from sensor nodes does not change dramatically, but rather changes gradually over time. We extend our framework for the invariants that include values determined at run time in order to detect the violation of data trends. The value range can be based on information local to a single node or the surrounding nodes? values. Using our system, developers can write invariants to detect data trends without prior knowledge of correct values. Automatic value detection can be used to detect anomalies that were not previously possible. To demonstrate the benefits of run-time range detection and fault checking, we construct a prototype WSN using CO2 and temperature sensors coupled to Mica2 motes. We show that our method can detect sudden changes of the environments with little overhead in communication, computation, and storage.

In multihop wireless systems, such as ad-hoc and sensor networks, the need for cooperation among nodes to relay each other?s packets exposes them to a wide range of security attacks. A particularly devastating attack is known as the wormhole attack, where a malicious node records control and data traffic at one location and tunnels it to a colluding node far away, which replays it locally. This can either disrupt route establishment or make routes pass through the malicious nodes. In this paper, we present a lightweight countermeasure for the wormhole attack, called LITEWORP, which relies on overhearing neighbor communication. LITEWORP is particularly suitable for resource-constrained multihop wireless networks, such as sensor networks. Our solution allows detection of the wormhole, followed by isolation of the malicious nodes. Simulation results show that every wormhole is detected and isolated within a very short period of time over a large range of scenarios. The results also show that the fraction of packets lost due to the wormhole when LITEWORP is applied is negligible compared to the loss in an unprotected network. Simulation results bring out the configuration where no framing is possible, while still having high detection rate. Analysis is done to show the low resource consumption of LITEWORP, the low detection latency, and the likelihood of framing by malicious nodes.

In multihop wireless systems, the need for cooperation among nodes to relay each other's packets exposes them to a wide range of security attacks. A particularly devastating attack is the wormhole attack, where a malicious node records control traffic at one location and tunnels it to a colluding node, possibly far away, which replays it locally. This can have an adverse effect on route establishment by preventing nodes from discovering legitimate routes that are more than two hops away. Previous works on tolerating wormhole attacks have focused only on detection and used specialized hardware, such as directional antennas or extremely accurate clocks. More recent work has addressed the problem of locally isolating the malicious nodes. However, all of this work has been done in the context of static networks due to the difficulty of secure neighbor discovery with mobile nodes. The existing work on secure neighbor discovery has limitations in accuracy, resource requirements, and applicability to ad hoc and sensor networks. In this paper, we present a countermeasure for the wormhole attack, called MOBIWORP, which alleviates these drawbacks and efficiently mitigates the wormhole attack in mobile networks. MOBIWORP uses a secure central authority (CA) for global tracking of node positions. Local monitoring is used to detect and isolate malicious nodes locally. Additionally, when sufficient suspicion builds up at the CA, it enforces a global isolation of the malicious node from the whole network. The effect of MOBIWORP on the data traffic and the fidelity of detection is brought out through extensive simulation using ns-2. The results show that as time progresses, the data packet drop ratio goes to zero with MOBIWORP due the capability of MOBIWORP to detect, diagnose and isolate malicious nodes. With an appropriate choice of design parameters, MOBIWORP is shown to completely eliminate framing of a legitimate node by malicious nodes, at the cost of a slight increase in the drop ratio. The results also show that increasing mobility of the nodes degrades the performance of MOBIWORP.

Sleep-wake protocols are critical in sensor networks to ensure long-lived operation. However, an open problem is how to develop efficient mechanisms that can be incorporated with sleep-wake protocols to ensure both longlived operation and a high degree of security. Our contribution in this paper is to address this problem by using local monitoring, a powerful technique for detecting and mitigating control and data attacks in sensor networks. In local monitoring, each node oversees part of the traffic going in and out of its neighbors to determine if the behavior is suspicious, such as, unusually long delay in forwarding a packet. Here, we present a protocol called SLAM to make local monitoring parsimonious in its energy consumption and to integrate it with any extant sleep-wake protocol in the network. The challenge is to enable sleep-wake in a secure manner even in the face of nodes that may be adversarial and not wake up nodes responsible for monitoring its traffic. We prove analytically that the security coverage is not weakened by the protocol. We perform simulations in ns-2 to demonstrate that the performance of local monitoring is practically unchanged while listening energy saving of 30 to 129 times is achieved, depending on the network load.

Sensor networks collect data using robust, energy efficient, low bandwidth protocols due to the few resources available to them. Among the many methods explored to improve the efficiency of sensor networks for data collection, researchers have proposed statistical methods to predict when each sensor should send data. Two shortcomings to this approach are: (1) the use of a static model, assuming unchanging environmental parameters to the sensor network and (2) the lack of an error detection mechanism to compensate for failures during the transmission of data. Suppressing data transmissions by using the fact that data follows a statistical model has been proposed before, with the assumption that the environmental parameters do not change. This assumption does not fit several scenarios where sensor networks can be deployed. Additionally, recent advancements in sensor networks allow for more powerful (CPU and memory) on sensing nodes. This represents an opportunity to extend the role of end nodes, by allowing them to perform statistical analysis on the collected data at runtime and updating model parameters in real time. In this manner, we can create a self adapting model.

Wireless reprogramming of a sensor network is useful for uploading new code or for changing the functionality of existing code. Through the process, a node should remain receptive to future code updates because reprogramming may be done multiple times during the node?s lifetime. Existing reprogramming protocols, such as Deluge, achieve this by bundling the reprogramming protocol and the application as one program image, thereby increasing the overall size of the image which is transferred through the network. This increases both time and energy required for network reprogramming. We present a protocol called Stream that mitigates the problem by significantly reducing the size of the program image. Using the facility of having multiple code images on a node and switching between them, Stream pre-installs the reprogramming protocol as one image and the application program equipped with the ability to listen to new code updates as the second image. For a sample application, Stream reduces the size of the program image by 10 pages (48 packets/page) compared to Deluge. Stream is implemented on the Mica2 sensor nodes and we conduct testbed and simulation experiments to show the reduction in energy and reprogramming time of Stream compared to Deluge.

Data dissemination strategies and communication protocols that minimize the use of energy can significantly prolong the lifetime of a sensor network. Data-centric dissemination strategies seek energy efficiency by employing short metadata descriptions in advertisements (ADVs) of the availability of data, short requests (REQs) to obtain the data by nodes that are interested in it, and data transmissions (DATA) to deliver data to the requesting nodes. An important decision in this process is whether the DATA transmission should be made at full power in broadcast mode or at low power in multi-hop unicast mode. The determining factor is shown in this paper to be the fraction of nodes that are interested in the DATA, as shown by the number of REQs that are generated. Closed form expressions for this critical fraction of interested nodes is derived when the nodes have no memory or infinite memory for state information and when transmissions are reliable and not reliable. These results can be used during both the design and operation of the network to increase energy efficiency and network longevity.

Wireless sensor networks are increasingly being used in applications where the communication between nodes needs to be protected from eavesdropping and tampering. Such protection is typically provided using techniques from symmetric key cryptography. The protocols in this domain suffer from one or more of the following problems - weak security guarantees if some nodes are compromised, lack of scalability, high energy overhead for key management, and increased end-to-end data latency. In this paper, we propose a protocol called SECOS that mitigates these problems in static sensor networks. SECOS divides the sensor field into control groups each with a control node. Data exchange between nodes within a control group happens through the mediation of the control head which provides the common key. The keys are refreshed periodically and the control nodes are changed periodically to enhance security. SECOS enhances the survivability of the network by handling compromise and failures of control nodes. It provides the guarantee that the communication between any two sensor nodes remains secure despite the compromise of any number of other nodes in the network. The experiments based on a simulation model show a seven time reduction in energy overhead and a 50% reduction in latency compared to SPINS, which is one of the state-of-the-art protocols for key management in sensor networks.

Multiple data-centric protocols - which can broadly be classified as push-pull, push-only, or pull-only - have been proposed in the literature. In this paper we present a framework to develop an insight into the characteristics of push-pull protocols. The performance of push-pull protocols is critically dependent on the time-out settings used to trigger failure recovery mechanisms. We perform a study of how to choose optimal timeouts to achieve best performance. Our starting point is a recently proposed SPIN-based protocol, called Shortest-Path Minded SPIN (SPMS), in which meta-data negotiations take place prior to data exchange in order to minimize the number of data transmissions. We propose a redesign of SPMS, called SPMS-Rec, which reduces the energy expended in the event of failures by requiring intermediate relay nodes to try alternate routes. Our simulation results show that SPMS-Rec outperforms SPMS, and thus SPIN, yielding energy savings while reducing the delay when multiple nodes fail along a route. We further propose a modification to SPMS-Rec through request suppression which helps in reducing redundant data transmissions.

In multihop wireless systems, the need for cooperation among nodes to relay each other's packets exposes them to a wide range of security attacks. A particularly devastating attack is the wormhole attack, where a malicious node records control traffic at one location and tunnels it to a colluding node, possibly far away, which replays it locally. This can have an adverse effect on route establishment by preventing nodes from discovering legitimate routes that are more than two hops away. Previous works on tolerating wormhole attacks have focused only on detection and used specialized hardware, such as directional antennas or extremely accurate clocks. More recent work has addressed the problem of locally isolating the malicious nodes. However, all of this work has been done in the context of static networks due to the difficulty of secure neighbor discovery with mobile nodes. The existing work on secure neighbor discovery has limitations in accuracy, resource requirements, and applicability to ad hoc and sensor networks. In this paper, we present a countermeasure for the wormhole attack, called MOBIWORP, which alleviates these drawbacks and efficiently mitigates the wormhole attack in mobile networks. MOBIWORP uses a secure central authority (CA) for global tracking of node positions. Local monitoring is used to detect and isolate malicious nodes locally. Additionally, when sufficient suspicion builds up at the CA, it enforces a global isolation of the malicious node from the whole network. The effect of MOBIWORP on the data traffic and the fidelity of detection is brought out through extensive simulation using ns-2. The results show that as time progresses, the data packet drop ratio goes to zero with MOBIWORP due the capability of MOBIWORP to detect, diagnose and isolate malicious nodes. With an appropriate choice of design parameters, MOBIWORP is shown to completely eliminate framing of a legitimate node by malicious nodes, at the cost of a slight increase in the drop ratio. The results also show that increasing mobility of the nodes degrades the performance of MOBIWORP.

We demonstrate the effect of using multiple estimations from independent single wireless motes in order to decrease network topology dependence on location estimation in a wireless sensor network. A method of determining the location of a target by using multiple compact semi-directional antennas is shown to give an independent estimate of location from each sensor mote in a network, each estimate not relying on the data from neighboring motes as in the case of traditional triangulation. We begin by demonstrating a method of using angular diversity through multiple semi-directional antennas in order to ascertain the location of a target. The estimation of both range and angle is demonstrated in the presence of a noisy and/or faded channel. An efficient and fast algorithm on a wireless sensor mote is presented through a Taylor series expansion of the simulated antenna pattern. Furthermore, using the results from the location estimation from a single node, location determination in a realistic network is explored through both theory and simulation. The results indicate that our proposed algorithm depends significantly less on the topology (spatial arrangement) of the anchor nodes. While network planning for a variety of topologies of anchor nodes is shown to be necessary when using triangulation, our proposed algorithm is insensitive to the deployments of the anchor nodes. A testbed was created in order to experimentally demonstrate that the predictions are accurate even in triangulation-adverse topologies. The experimental testbed shows that a linear arrangement of closely spaced sensors can reduce the location error to one-fourth of the location error using triangulation.

In multihop wireless systems, the need for cooperation among nodes to relay each other's packets exposes them to a wide range of security attacks. A particularly devastating attack is the wormhole attack, where a malicious node records control traffic at one location and tunnels it to a colluding node, possibly far away, which replays it locally. This can have an adverse effect on route establishment by preventing nodes from discovering legitimate routes that are more than two hops away. Previous works on tolerating wormhole attacks have focused only on detection and used specialized hardware, such as directional antennas or extremely accurate clocks. More recent work has addressed the problem of locally isolating the malicious nodes. However, all of this work has been done in the context of static networks due to the difficulty of secure neighbor discovery with mobile nodes. The existing work on secure neighbor discovery has limitations in accuracy, resource requirements, and applicability to ad hoc and sensor networks. In this paper, we present a countermeasure for the wormhole attack, called MOBIWORP, which alleviates these drawbacks and efficiently mitigates the wormhole attack in mobile networks. MOBIWORP uses a secure central authority (CA) for global tracking of node positions. Local monitoring is used to detect and isolate malicious nodes locally. Additionally, when sufficient suspicion builds up at the CA, it enforces a global isolation of the malicious node from the whole network. The effect of MOBIWORP on the data traffic and the fidelity of detection is brought out through extensive simulation using ns-2.

Sensor networks are being increasingly deployed for collecting critical data in various applications. Once deployed, a sensor network may experience faults at the individual node level or at an aggregate network level due to design errors in the protocol, implementation errors, or deployment conditions that are significantly different from the target environment. In many applications, the deployed system may fail to collect data in an accurate, complete, and timely manner due to such errors. If the network produces incorrect data, the resulting decisions on the data may be incorrect, and negatively impact the application. Hence, it is important to detect and diagnose these faults through run-time observation. Existing technologies face difficulty with wireless sensor networks due to the large scale of the networks, the resource constraints of bandwidth and energy on the sensing nodes, and the unreliability of the observation channels for recording the behavior. This paper presents a semi-automatic approach named H-SEND (Hierarchical SEnsor Network Debugging) to observe the health of a sensor network and to remotely repair errors by reprogramming through the wireless network. In H-SEND, a programmer specifies correctness properties of the protocol (?invariants?). These invariants are associated with conditions (the ?observed variables?) of individual nodes or the network. The compiler automatically inserts checking code to ensure that the observed variables satisfy the invariants. The checking can be done locally or remotely, depending on the nature of the invariant. In the latter case, messages are generated automatically. If an error is detected at run-time, the logs of the observed variables are examined to analyze and correct the error. After errors are corrected, new programs or patches can be uploaded to the nodes through the wireless network. We construct a prototype to demonstrate the benefit of run-time detection and correction.

Sensor networks enable a wide range of applications in both military and civilian domains. However, the deployment scenarios, the functionality requirements, and the limited capabilities of these networks expose them to a wide-range of attacks against control traffic (such as wormholes, Sybil attacks, rushing attacks, etc). In this paper we propose a lightweight protocol called DICAS that mitigates these attacks by detecting, diagnosing, and isolating the malicious nodes. DICAS uses as a fundamental building block the ability of a node to oversee its neighboring nodes? communication. On top of DICAS, we build a secure routing protocol, LSR, which also produces multiple node-disjoint paths. We analyze the security guarantees of DICAS and use ns-2 simulations to show its effectiveness against three representative attacks. Overhead analysis is conducted to prove the lightweight nature of DICAS.

As sensor networks operate over long periods of time deployed in inaccessible places, each sensor?s requirements, location, and reliability may change as they each are subjected to unpredictable influences, both external and internal to the network. As access to these sensors will usually be limited, it is important that when sensor requirements change that there is a reliable, efficient, and fast means of propagating code updates over the network. This work provides a protocol for quickly disseminating data over a sensor network with high reliability and intelligent power management. It achieves energy savings through forwarding of local information on the network scale, providing nodes an estimation of distance from code updates. This energy saving mechanism is further enhanced through directional antenna hardware, which accurately estimates node locations given a few nodes already aware of their locations. This hardware scheme shows much greater accuracy than triangulation with omni-directional antennas. Coupled with reprogramming the network and locating sensor nodes is the challenge of locating and isolating nodes within the network that function improperly despite software-level updates. To solve this problem this work implements a trust-based protocol that aggregates individual sensor decisions and performance over time to mask out nodes of questionable reliability. Nodes that show continued poor performance are either ignored or removed from the system; the locations of these faulty nodes are easily obtained through directional hardware localization. This scheme proves robust even in cases where half of the network is functioning unreliably.

Since sensor data gathering is the primary functionality of sensor networks, it is important to provide a fault tolerant method for reasoning about sensed events in the face of arbitrary failures of nodes sending in the event reports. In this paper, we propose a protocol called TIBFIT to diagnose and mask arbitrary node failures in an event-driven wireless sensor network. In our system model, sensor nodes are organized into clusters with rotating cluster heads. The nodes, including the cluster head, can fail in an arbitrary manner generating missed event reports, false reports, or wrong location reports. Correct nodes are also allowed to make occasional natural errors. Each node is assigned a trust index to indicate its track record in reporting past events correctly. The cluster head analyzes the event reports using the trust index and makes event decisions. TIBFIT is analyzed and simulated using the network simulator ns-2 and its coverage evaluated with a varying number and varying intelligence of the malicious nodes. We show that once TIBFIT gathers enough system state, accurate event detection is possible even if more than 50% of the network nodes are compromised.

In multihop wireless systems, such as ad-hoc and sensor networks, the need for cooperation among nodes to relay each other?s packets exposes them to a wide range of security attacks. A particularly devastating attack is known as the wormhole attack, where a malicious node records control and data traffic at one location and tunnels it to a colluding node, which replays it locally. This can have an adverse effect in route establishment by preventing nodes from discovering routes that are more than two hops away. In this paper, we present a lightweight countermeasure for the wormhole attack, called LITEWORP, which does not require specialized hardware. LITEWORP is particularly suitable for resource-constrained multihop wireless networks, such as sensor networks. In this paper, we present a detailed description of LITEWORP for static networks, and discuss extensions to mobile networks. Our solution allows detection of the wormhole, followed by isolation of the malicious nodes. Simulation results show that every wormhole is detected and isolated within a very short period of time over a large range of scenarios. The results also show that the fraction of packets lost due to the wormhole when LITEWORP is applied is negligible compared to the loss encountered when the method is not applied.

With the development of location aware sensor applications, location determination has become an increasingly important middleware technology. Numerous current technologies for location determination of sensor nodes use the received signal strength from sensor nodes using omni-directional antennas. However, an increasing number of sensor systems are now deploying directional antennas due to their advantages like energy conservation and better bandwidth utilization. In this paper, we present techniques for location determination in a sensor network with directional antennas under different kinds of deployment of the nodes. We show how the location estimation problem can be solved by measuring the received signal strength from just one or two anchors in a 2D plane with directional antennas. We implement our technique using Berkeley MICA2 sensor motes and show that it is up to three times more accurate than triangulation using omni-directional antennas. We also perform Matlab simulations that show the accuracy of location determination with increasing node density.

In this paper, we investigate the use of multiple directional antennas on sensor motes for location determination and mobile node monitoring. One key aspect that distinguishes wireless sensor networks is inexpensive transmitters and receivers that still maintain acceptable connectivity. Therefore, complex RF solutions are often not applicable. We propose and demonstrate a location estimation algorithm on a single sensor node equipped with inexpensive directional antennas by measuring the received signal strength of the transmission peers. This algorithm is further applied to the dynamic tracking of a wandering mote. The location tracking error can be reduced from 30% to 16% by using moving average schemes and merging estimates from different sets of antennas. The mean error of tracking estimates can be obtained to provide the certainty of location tracking. Therefore, only a single mote with angular diverse multiple antennas is needed to determine the location of a mote without triangulation.

This paper proposes using a mobile collector, such as an airplane or a vehicle, to collect sensor data from remote fields. We present three different schedules for the collector: Round-Robin, Rate-Based, and Min Movement. The data are not immediately transmitted to the base station after being sensed but buffered at a cluster head; hence, it is important to ensure the latency is within an acceptable range. We compare the latency and the energy expended of the three schedules. We use the ns-2 network simulator to study the scenarios and illustrate conditions under which Rate-Based outperforms Round-Robin in latency, and vice-versa. The benefit of Min Movement is in minimizing the energy expended.

With the development of location aware applications for ad-hoc and sensor networks, location determination has become an important middleware technology. Cost, size, and energy constraints permit only a fraction of the network nodes, called anchors, to carry location determination hardware such as GPS receivers. The first part of our work involves evaluating the effect of topological characteristics, such as coverage and connectivity, on the accuracy of location determination protocols. We study a protocol called Hop-Terrain that uses the received signal strength from anchors for estimating position of sensor nodes. The resultant performance predictions can be used in motion planning for nodes to improve the accuracy of location estimates. An emerging trend in sensor networks is deploying directional RF antennas on nodes due to advantages like energy conservation and better bandwidth utilization. The location estimation techniques for omni-directional antennas cannot be employed in such systems since the received power at a node depends on additional variables like transmission and receiving angles. Our work presents techniques for location determination with directional antennas under different kinds of node deployments, such as globally aligned nodes and unaligned nodes. We show how the problem can be solved in a two-dimensional plane by using just one anchor in contrast to three anchors for omni-directional antennas. We consider the possibility of errors in individual distance measurements and present theoretical as well as simulation-based results for the level of redundancy required to have an aggregate estimation error below a desired threshold. Simulations show improvement in the accuracy of the position estimates over that of the triangulation based approach for omni-directional antennas.

In this paper we present a data dissemination protocol for efficiently distributing data through a sensor network in the face of node and link failures. Our work is motivated by the SPIN protocol which uses metadata negotiation to minimize data transmissions. We propose a protocol called Shortest Path Minded SPIN (SPMS) in which every node has a zone defined by its maximum transmission radius. A node which is a data source advertises the availability of data to all the nodes in its zone using a metadata descriptor. Any interested node requests the data and gets sent the data using multi-hop communication via the shortest path. The failure of any node in the path is detected and recovered using backup routes. We build simulation models to compare SPMS against SPIN. Different scenarios including mobility and node failures are simulated. The simulation results show that SPMS reduces the delay over 10 times and consumes 30% less energy in the static failure free scenario. Even with the addition of mobility, SPMS outperforms SPIN by energy gains between 5% and 21%. An analytical model is also constructed to compare the two protocols under a simplified topology.

Sensor networks are a particular class of wireless ad hoc networks in which the nodes have small components for sensors, actuators and RF communication components. Sensor nodes are dispersed over the area of interest, called sensor field, and are capable of short-range RF communication (about 100 ft) and contain signal processing engines to manage the communication protocols and for data processing. The individual nodes have a limited processing capacity, but are capable of supporting distributed applications through coordinated effort in a network that can include hundreds or even thousands of nodes. Sensor nodes are typically battery-powered. Since replacing batteries is often very difficult, reducing energy consumption is an important design consideration for sensor networks. Because transmitting power is proportional to the square or quadruple of the transmission range, the range of a sensor node is constrained in most deployments. In sensor networks, the final data gathering and analysis station, called the base station, is sometimes placed far from the sensing nodes. This may be because the sensing field is in a hazardous environment, such as enemy territory, or a physically harsh environment, with high temperature, etc. It may be impossible to locate a protected, high-end base station with large computational and communication capabilities in such a hazardous environment. Since the transmission range of the individual nodes is limited, the large separation between the sensing region and the base station implies long distance and multi-hop transmission has to occur. This architecture is difficult to deploy and maintain with regular sensing nodes acting as relay nodes. Some nodes in the network may be mobile, either in a controlled or in an uncontrolled manner. Uncontrolled mobility, referred to as passive mobility implies the nodes move but not of their own volition. Examples include nodes embedded into animals, nodes carried by human beings who move according to other considerations, and light-weight nodes carried by physical processes such as running water, glaciers, or wind. Nodes with passive mobility make data collection more challenging. Some nodes may move far away from the data aggregation point, such as a base station or a cluster head, and even become disconnected from the rest of the network. With mobility, routing data to the nodes may become inefficient since many sensor network routing protocols rely on position knowledge. Hence, traditionally, mobility has been looked on as an adversary to efficient deployment of sensor networks due to degradation of the topology affecting parameters such as connectivity and coverage or due to increased failure rates of wireless links. We turn this argument on its head and propose to use ?controlled mobility? of certain nodes in the network to our advantage. Controlled mobility implies the ability to control the movement of an entity (direction, velocity, etc.) by sending it control commands.

This paper presents a study of topological characteristics of mobile wireless ad-hoc networks. The characteristics studied are connectivity, coverage, and diameter. Knowledge of topological characteristics of a network aids in the design and performance prediction of network protocols. This paper introduces intelligent goal-directed mobility algorithms for achieving desired topological characteristics and presents a simulation-based study. The study shows that to achieve low, medium and high network QoS defined in terms of combined requirements of the three metrics, the network needs respectively 8, 16, and 40 nodes. If nodes can fail, the requirements increase to 8, 36 and 60 nodes respectively. We present a theoretical derivation of the improvement due to the mobility models and the sufficient condition for connectivity and coverage in the network. Next, we show the effect of improved topological characteristics in enhancing QoS of an application level protocol, namely, a location determination protocol called Hop-Terrain. The study shows that the error in location estimation is reduced by up to 68% with the goal-directed mobility.

Wireless sensor networks are becoming a critical computational infrastructure, in which the communication between nodes needs to be protected from eavesdropping and tampering. Symmetric key cryptography is the fundamental technique being used. The protocols in this domain suffer from one or more of the problems of weak security guarantees if some nodes are compromised, lack of scalability, high energy overhead for key management and increased end-to-end data latency. In this paper, we propose a protocol called SECOS that mitigates these problems. SECOS divides the sensor field into control groups each with a control head. Data exchange between nodes within a control group happens through the mediation of the control head which provides the common key. The keys and the control heads are changed periodically to enhance security. SECOS enhances the survivability of the network by handling failures of control nodes. The experiments based on a simulation model show 7 times reduction in energy overhead and 50% reduction in latency compared to the stateof-the-art protocol, SPINS. We also provide an analytical derivation of the optimal control group size that operates under the resource constraints and minimizes energy consumption.