Search

In this paper, we examine several localization algorithms and evaluate their robustness to attacks where an adversary attenuates or amplifies the signal strength at one or more landmarks. We propose several performance metrics that quantify the estimator's precision and error, including Hölder metrics, which quantify the variability in position space for a given variability in signal strength space. We then conduct a trace-driven evaluation of several point-based and area-based algorithms, where we measured their performance as we applied attacks on real data from two different buildings. We found the median error degraded gracefully, with a linear response as a function of the attack strength. We also found that area-based algorithms experienced a decrease and a spatial-shift in the returned area under attack, implying that precision increases though bias is introduced for these schemes. We observed both strong experimental and theoretic evidence that all the algorithms have similar average responses to signal strength attacks. [ABSTRACT FROM AUTHOR]

We have developed a new on-line error modeling and optimization-based localization approach for sensor networks in the presence of distance measurement noise. The approach is solely based on the concept of consistency, and is developed specifically for the case of on-line localization, which refers to the situation when references are not available a priori. The localization problem is formulated as the task of maximizing the consistency between measurements and calculated distances. In addition, we also present a localized localization algorithm where a specified communication cost or the location accuracy is guaranteed while optimizing the other. We evaluated the approach in (i) both GPS-based and GPS-less scenarios; (ii) 1-D, 2-D and 3-D spaces, on sets of acoustic ranging-based distance measurements recorded by deployed sensor networks. The experimental evaluation indicates that localization of only a few centimeters is consistently achieved when the average and median distance measurement errors are more than a meter, even when the nodes have only a few distance measurements. The relative performance in terms of location accuracy compares favorably with respect to several state-of-the-art localization approaches. Finally, several insightful observations about the required conditions for accurate location discovery are deduced by analyzing the experimental results. Keywords: Consistency, Location Discovery, Statistical Modeling. [ABSTRACT FROM AUTHOR]

Localizing sensor nodes is essential due to their random distribution after deployment. To reach a long network lifetime, which strongly depends on the limited energy resources of every node, applied algorithms must be developed with an awareness of computation and communication cost. In this paper we present a new localization method, which places a minimum computational requirement on the nodes but achieves very low localization errors of less than 1%. To achieve this, we split the complex least squares method into a less central precalculation and a simple, distributed subcalculation. This allows precalculating the complex part on high-performance nodes, e.g. base stations. Next, sensor nodes estimate their own positions by simple subcalculation, which does not exhaust the limited resources. We analyzed our method with three commonly used numerical techniques - normal equations, qr-factorization, and singular-value decomposition. Simulation results showed that we reduced the complexity on every node by more than 47% for normal equations. In addition, the proposed algorithm is robust with respect to high input errors and has low communication and memory requirements. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new data gathering mechanism for large scale multihop sensor networks. A mobile data observer, called SenCar, which could be a mobile robot or a vehicle equipped with a powerful transceiver and battery, works like a mobile base station in the network. SenCar starts the data gathering tour periodically from the static data processing center, traverses the entire sensor network, gathers the data from sensors while moving, returns to the starting point, and finally uploads data to the data processing center. Unlike SenCar, sensors in the network are static, and can be made very simple and inexpensive. They upload sensing data to SenCar when SenCar moves close to them. Since sensors can only communicate with others within a very limited range, packets from some sensors may need multihop relays to reach SenCar. We first show that the moving path of SenCar can greatly affect the network lifetime. We then present heuristic algorithms for planning the moving path/circle of SenCar and balancing traffic load in the network. We show that by driving SenCar along a better path and balancing the traffic load from sensors to SenCar, the network lifetime can be prolonged significantly. Our simulation results demonstrate that the proposed data gathering mechanism can greatly prolong the network lifetime compared to a network which has only a static observer, or a network in which mobile observer can only move along straight lines. Keywords: SenCar, Wireless sensor networks, Data gathering, Load balancing. [ABSTRACT FROM AUTHOR]

Improving network lifetime is a fundamental challenge of wireless sensor networks. One possible solution consists in making use of mobile sinks. Whereas theoretical analysis shows that this approach does indeed benefit network lifetime, practical routing protocols that support sink mobility are still missing. In this paper, in line with our previous efforts, we investigate the approach that makes use of a mobile sink for balancing the traffic load and in turn improving network lifetime. We engineer a routing protocol, MobiRoute, that effectively supports sink mobility. Through intensive simulations in TOSSIM with a mobile sink and an implementation of MobiRoute, we prove the feasibility of the mobile sink approach by demonstrating the improved network lifetime in several deployment scenarios. [ABSTRACT FROM AUTHOR]

We develop algorithms for finding the minimum energy transmission schedule for duty-cycle and rate constrained wireless sensor nodes transmitting over an interference channel. Since traditional optimization methods using Lagrange multipliers do not work well and are computationally expensive given the non-convex constraints, we develop fully polynomial approximation schemes (FPAS) for finding optimal schedules by considering restricted versions of the problem using multiple discrete power levels. We first show a simple dynamic programming solution that optimally solves the restricted problem. For two fixed transmit power levels (0 and P), we then develop a 2-factor approximation for finding the optimal fixed transmission power level per time slot, Popt, that generates the optimal (minimum) energy schedule. This can then be used to develop a (2, 1+ε)-FPAS that approximates the optimal power consumption and rate constraints to within factors of 2 and arbitrarily small $\epsilon>0$, respectively. Finally, we develop an algorithm for computing the optimal number of discrete power levels per time slot (O(1/ε)), and use this to design a (1, 1+ε)-FPAS that consumes less energy than the optimal while violating each rate constraint by at most a 1+ε factor. [ABSTRACT FROM AUTHOR]

This paper presents a study of the Flexible Power Scheduling protocol and evaluates its use for real-world sensor network applications and their platforms. FPS uses dynamically created schedules to reserve network flows in sensor networks allowing nodes to turn off their radio during idle times. We show that network power scheduling has high end-to-end packet reception and can achieve power savings of 2-5x for two well-known TinyOS applications over their existing power-management schemes, and over 150x compared with no power management. Twinkle is our second-generation implementation of FPS and provides additional application support. [ABSTRACT FROM AUTHOR]

In this paper, we study the fundamental limits of a wireless sensor network's lifetime under connectivity and k-coverage constraints. We consider a wireless sensor network with n sensors deployed independently and uniformly in a square field of unit area. Each sensor is active with probability p, independently from others, and each active sensor can sense a disc area with radius rs. Moreover, considering the inherent irregularity of a sensor's sensing range caused by time-varying environments, we model the sensing radius rs as a random variable with mean r0 and variance r02σs2. Two active sensors can communicate with each other if and only if the distance between them is smaller than or equal to the communication radius rc. The key contributions of this paper are: (1) we introduce a new definition of a wireless sensor network's lifetime from a novel probabilistic perspective, called ω-lifetime (0 ≤ ω ≤ 1). It is defined as the expectation of the time interval during which the probability of guaranteeing connectivity and k-coverage simultaneously is at least ω; and (2) based on the analysis results, we propose a near-optimal scheduling algorithm, called PIS (Pre-planned Independent Sleeping), to achieve the network's maximum ω-lifetime, which is validated by simulation results, and present a possible implementation of the PIS scheme in the distributed manner. [ABSTRACT FROM AUTHOR]

We consider the problem of data propagation in wireless sensor networks and revisit the family of mixed strategy routing schemes. We show that maximizing the lifespan, balancing the energy among individual sensors and maximizing the message flow in the network are equivalent. We propose a distributed and adaptive data propagation algorithm for balancing the energy among sensors in the network. The mixed routing algorithm we propose allows each sensor node to either send a message to one of its immediate neighbors, or to send it directly to the base station, the decision being based on a potential function depending on its remaining energy. By considering a simple model of the network and using a linear programming description of the message flow, we prove the strong result that an energy-balanced mixed strategy beats every other possible routing strategy in terms of lifespan maximization. Moreover, we provide sufficient conditions for ensuring the dynamic stability of the algorithm. The algorithm is inspired by the gradient-based routing scheme but by allowing to send messages directly to the base station we improve considerably the lifespan of the network. As a matter of fact, we show experimentally that our algorithm is close to optimal and that it even beats the best centralized multi-hop routing strategy. [ABSTRACT FROM AUTHOR]

The paper studies the optimal placement of multiple cameras and the selection of the best subset of cameras for single target localization in the framework of sensor networks. The cameras are assumed to be aimed horizontally around a room. To conserve both computation and communication energy, each camera reduces its image to a binary "scan-line" by performing simple background subtraction followed by vertical summing and thresholding, and communicates only the center of the detected foreground object. Assuming noisy camera measurements and an object prior, the minimum mean squared error of the best linear estimate of the object location in 2-D is used as a metric for placement and selection. The placement problem is shown to be equivalent to a classical inverse kinematics robotics problem, which can be solved efficiently using gradient descent techniques. The selection problem on the other hand is a combinatorial optimization problem and finding the optimal solution can be too costly to implement in an energy-constrained wireless camera network. A semi-definite programming approximation for the problem is shown to achieve close to optimal solutions with much lower computational burden. Simulation and experimental results are presented. [ABSTRACT FROM AUTHOR]

An important class of applications for wireless sensor networks is to use the sensors to provide samples of a physical phenomenon at discrete locations. Through interpolation-based reconstruction, a continuous map of the monitored environment can be built. In this paper, we leverage the spatial correlation characteristics of the physical phenomenon and find the minimum set of nodes that needs to be active at each point in time for a sufficiently accurate reconstruction. Furthermore, multiple such sets of nodes are found so that a different set can report at each point in time in a rotating fashion. This is crucial in improving network lifetime. To perform all related scheduling tasks we employ a novel approach which does not assume a-priori knowledge of the underlying phenomenon. Instead it jointly estimates process characteristics and performs node selection online. We illustrate that significant gains in network lifetime can be achieved with minimal impact on the overall reconstruction quality, measured in terms of distortion. Keywords: spatial random process, irregular sampling, distortion, lifetime, energy efficiency. [ABSTRACT FROM AUTHOR]

We propose a distributed scheme called Adaptive-Group-Merge for sensor networks that, given a parameter k, approximates a geometric shape by a k-vertex polygon. The algorithm is well suited to the distributed computing architecture of sensor networks, and we prove that its approximation quality is within a constant factor of the optimal. We also show through simulation that our scheme outperforms several other alternatives in preserving important shape features, and achieves approximation quality almost as good as the optimal, centralized scheme. Because many applications of sensor networks involve observations and monitoring of physical phenomena, the ability to represent complex geometric shapes faithfully but using small memory is vital in many settings. [ABSTRACT FROM AUTHOR]

In wireless sensor networks, multi-hop localization schemes are very vulnerable to various attacks such as wormholes and range modification attacks. In this paper, we propose a robust multi-hop localization scheme, namely COTA, to mitigate various attacks in wireless sensor networks. In this scheme, each localized sensor generates a COnfidence TAg to quantify the quality of its estimated location and broadcasts both the confidence tag and the estimated location in reference messages. When receiving sufficient number of references, an unlocalized sensor filters out bad references and weighs the remaining ones according to their tags. Once location determination is done, the sensor generates its own confidence tag from the indicator of its localization error. By properly setting the filtering metrics and computing the confidence tags, COTA can prevent the proliferation of location errors and achieves accurate location estimations and high localized percentage for sensor networks. To our knowledge, ours is the first work to address the security-aware multi-hop localization problem. We finally present security analysis and simulations to evaluate the effectiveness of COTA. [ABSTRACT FROM AUTHOR]

While sensor networks have recently emerged as a promising computing model, they are vulnerable to various node compromising attacks. In this paper, we propose COOL, a COmpromised nOde Locating protocol for detecting and locating compromised nodes once they misbehave in the sensor network. We exploit a proven collision-resilient incremental hashing algorithm and design secure steps to confidently locate compromised nodes. The scheme can also be combined with existing en-route false report filtering schemes to achieve both early false report dropping and accurate compromised nodes isolation. [ABSTRACT FROM AUTHOR]

User access control in sensor networks defines a process of granting user the access right to the information and resources. It is essential for the future real sensor network deployment in which sensors may provide users with different services in terms of data and resource access. A centralized access control mechanism requires base station to be involved whenever a user requests to get authenticated and access the information stored in the sensor node, which is inefficient, not scalable, and is exposed to many potential attacks along the long communication path. In this paper, we propose a distributed user access control under a realistic adversary model in which sensors can be compromised and user may collude. We split the access control into local authentication conducted by the sensors physically close to the user, and a light remote authentication based on the endorsement of the local sensors. Elliptic Curve Cryptography (ECC), a public key cryptography scheme, is used for local authentication. We implement the access control protocols on a testbed of TelosB motes. Our analysis and experimental results show that our scheme is feasible for real access control requirement. [ABSTRACT FROM AUTHOR]

Today, there exist many algorithms and protocols for constructing agregation or dissemination trees for wireless sensor networks that are optimal (for different notions of optimal, i.e. under different cost metrics). However, all these schemes differ from one common failing - they construct an optimal tree for a given fixed subset of the sensors. In most practical scenarios, the sensor group is continuously and dynamically varying - consider for example the set of sensors scattered in a forest that are sensing temperatures above some specified threshold, during a wildfire. Given the limited computational and energy resources of sensor nodes it is impossible to either prestore the optimal tree for every conceivable group or to dynamically generate them on the fly. In this paper we propose the novel approach of constructing a single group-independent spanning tree (GIST) T for the network and then letting any sensor group S use the subtree induced by S on T, TS as its group aggregation tree. The important question is, how does the quality of the subtree TS compare to the optimal tree, OPTS, across different groups S. We consider two well-accepted measures - aggregation cost (sum over all links) and delay (diameter). We show that in polynomial time we can construct a GIST that simultaneously achieves O(log n)-approximate aggregation cost and O(1)-approximate delay, for all groups S. To the best of our knowledge GIST is the first construction with a nontrivial and provable performance guarantee that works for all groups. We provide a practical and distributed protocol for realizing GIST that requires only local knowledge. We show an Ω(n) lower bound for commonly accepted solutions such as MST and SPT (i.e. there exists a group for which the induced subtree performs poorly) and demonstrate by simulation that GIST is good not just in the worst case - it outperforms SPT and MST by between 30 and 60 per cent in realistic random scenarios. GIST is an overlay construction and for the special case of grids we present GRID-GIST, a physical tree that uses only grid edges and achieves the same performance bounds. [ABSTRACT FROM AUTHOR]

We consider the problem of estimating vector-valued variables from noisy "relative" measurements. The measurement model can be expressed in terms of a graph, whose nodes correspond to the variables being estimated and the edges to noisy measurements of the difference between the two variables. This type of measurement model appears in several sensor network problems, such as sensor localization and time synchronization. We consider the optimal estimate for the unknown variables obtained by applying the classical Best Linear Unbiased Estimator, which achieves the minimum variance among all linear unbiased estimators. We propose a new algorithm to compute the optimal estimate in an iterative manner, the Overlapping Subgraph Estimator algorithm. The algorithm is distributed, asynchronous, robust to temporary communication failures, and is guaranteed to converges to the optimal estimate even with temporary communication failures. Simulations for a realistic example show that the algorithm can reduce energy consumption by a factor of two compared to previous algorithms, while achieving the same accuracy. [ABSTRACT FROM AUTHOR]

We consider in-network processing via local message passing. The considered setting involves a set of sensors each of which can communicate with a subset of other sensors. There is no designated fusion center; instead sensors exchange messages on the associated communication graph to obtain a global estimate. We propose an asynchronous distributed algorithm based on local fusion between neighboring sensors. The algorithm differs from other related schemes such as gossip algorithms in that after each local fusion one of the associated sensors ceases its activity until it is re-activated by reception of messages from a neighboring sensor. This leads to substantial gains in energy expenditure over existing local ad-hoc messaging algorithms such as gossip and belief propagation algorithms. Our results are general and we focus on some explicit graphs, namely geometric random graphs, which have been successfully used to model wireless networks, and d-dimensional lattice torus with n nodes, which behave exactly like mesh networks as n gets large. We quantify the time, message and energy scaling of the algorithm, where the analysis is built upon the coalescing random walks. In particular, for the planar torus the completion time of the algorithm is Θ(n log n) and energy requirement per sensor node is O((log n)2) and for 3-d torus these quantities are Θ(n) and O(log n) respectively. The energy requirement of the algorithm is thus scalable, and interestingly there appears little practical incentive to consider higher dimensions. Furthermore, for the planar torus the algorithm exhibits a very favorable tradeoff relative to gossip algorithms whose time and energy requirements are shown here to be Ω(n). Also, the proposed algorithm can be generalized to robustify against packet losses and permanent node failures without entailing significant energy overhead. The paper concludes with numerical results. [ABSTRACT FROM AUTHOR]

In a sensor network information from multiple nodes must usually be aggregated in order to accomplish a certain task. A natural way to view this information gathering is in terms of interactions between nodes that are producers of information, e.g., those that have collected data, detected events, etc., and nodes that are consumers of information, i.e., nodes that seek data or events of certain types. Our overall goal in this paper is to construct efficient schemes allowing consumer and producer nodes to discover each other so that the desired information can be delivered quickly to those who seek it. Here, efficiency means both limiting the redundancy of where producer information is stored, as well as bounding the consumer query times. We introduce the notion of distance-sensitive information brokerage and provide schemes for efficiently bringing together information producers and consumers at a cost proportional to the separation between them — even though neither the consumers nor the producers know about each other beforehand. Our brokerage scheme is generic and can be implemented on top of several hierarchical routing schemes that have been proposed in the past, provided that they are augmented with certain key sideway links. For such augmented hierarchical routing schemes we provide a rigorous theoretical performance analysis, which further allows us to prove worst case query times and storage requirements for our information brokerage scheme. Experimental results demonstrate that the practical performance of the proposed approaches far exceeds their theoretical (worst-case) bounds. The presented algorithms rely purely on the topology of the communication graph of the sensor network and do not require any geographic location information. [ABSTRACT FROM AUTHOR]

We propose a new data dissemination protocol for wireless sensor networks, that basically pulls some additional knowledge about the network in order to subsequently improve data forwarding towards the sink. This extra information is still local, limited and obtained in a distributed manner. This extra knowledge is acquired by only a small fraction of sensors thus the extra energy cost only marginally affects the overall protocol efficiency. The new protocol has low latency and manages to propagate data successfully even in the case of low densities. Furthermore, we study in detail the effect of failures and show that our protocol is very robust. In particular, we implement and evaluate the protocol using large scale simulation, showing that it significantly outperforms well known relevant solutions in the state of the art. [ABSTRACT FROM AUTHOR]

When communication in sensor networks occurs over wireless links, confidential information about the communication patterns between sensor nodes could be leaked even when encryption is used to protect the actual contents of the messages. The communication patterns, which often reveal higher volumes of traffic near the sink, could allow an attacker to identify the vicinity of the sink node. With this information, an attacker could potentially disable the network by destroying the sink. In this paper, we present the decoy sink protocol, which protects the location of the sink in target tracking sensor network applications by forwarding data to a decoy sink for aggregation before the aggregated data is forwarded to the real sink from the decoy sink. Combining indirection and data aggregation in our protocol creates more traffic away from the sink and reduces the amount of traffic near the sink, which makes traffic analysis more difficult for attackers. Keywords: Traffic analysis prevention, data aggregation, sensor networks. [ABSTRACT FROM AUTHOR]

We present a comparative mathematical analysis of two important distinct approaches to hybrid push-pull querying in wireless sensor networks: structured hash-based data-centric storage (DCS) and the unstructured comb-needle (CN) rendezvous mechanism. Our analysis yields several interesting insights. For ALL-type queries pertaining to information about all events corresponding to a given attribute, we examine the conditions under which the two approaches outperform each other in terms of the average query and event rates. For the case of ANY-type queries where it is sufficient to obtain information from any one of the desired events for a given attribute, we propose and analyze a modified sequential comb-needle technique (SCN) to compare with DCS. We find that DCS generally performs better than CN/SCN for high query rates and low event rates, while CN/SCN perform better for high event rates. Surprisingly, for the cases of ALL-type aggregated queries and ANY-type queries, we find that there exist "magic number" event rate thresholds, independent of network size or query probability, which dictate the choice of querying protocol. While our analysis is based on a single-sink square-grid deployment, we believe the insights can be generalized to random deployments. [ABSTRACT FROM AUTHOR]

Resource constrained systems often are programmed using an event-based model. Many applications do not lend themselves well to an event-based approach, but preemptive multithreading pre-allocates resources that cannot be used even while not in use by the owning thread. In this paper, we propose a hybrid approach called Y-Threads. Y-Threads provide separate small stacks for blocking portions of applications, while allowing for shared stacks for non-blocking computations. We have implemented Y-Threads on Mica and Telos wireless sensor network platforms. The results show that Y-Threads provide a preemptive multithreaded programming model with resource utilization closer to an event-based approach. In addition, relatively large memory buffers can be allocated for temporary use with less overhead than conventional dynamic memory allocation methods. Keywords: Stack sharing, Multi-threading, Concurrency. [ABSTRACT FROM AUTHOR]

Wireless sensor networks (WSNs) typically exploit a single base station for collecting data and coordinating activities. However, decentralized architectures are rapidly emerging, as witnessed by wireless sensor and actuator networks (WSANs), and in general by solutions involving multiple data sinks, heterogeneous nodes, and in-network coordination. These settings demand new programming abstractions to tame complexity without sacrificing efficiency. In this work we introduce the notion of logical neighborhood, which replaces the physical neighborhood provided by wireless broadcast with a higher-level, application-defined notion of proximity. The span of a logical neighborhood is specified declaratively based on the characteristics of nodes, along with requirements about communication costs. This paper presents the Spidey programming language for defining logical neighborhoods, and a routing strategy that efficiently supports the communication enabled by its programming constructs. [ABSTRACT FROM AUTHOR]

We propose a generic communication primitive designed for sensor networks. Our primitive hides details of network communication while retaining sufficient programmer control over the communication behavior of an application; it is designed to ease the burden of writing application-specific communication protocols for efficient, long-lived, fault-tolerant, and scalable applications. While classical network communication methods expect high-reliability links, our primitive works well in highly unreliable environments without needing to detect and prune unreliable links. Our primitive resembles the chemical markers used by many biological systems to solve distributed problems (pheromones). We develop and analyze the performance of an implementation of this primitive called Virtual Pheromone (VP). We demonstrate that VP can attain performance comparable to classical methods for applications such as sleep scheduling, routing, flooding, and cluster formation. [ABSTRACT FROM AUTHOR]

Reprogramming the sensor networks in place is an important and challenging problem. One way suggested for reprogramming is with the help of an UAV (Unmanned Ariel Vehicle). To reprogram a sensor network with the help of an UAV, one can either communicate the entire new program to one (or a few) sensor in the field, or let the UAV communicate parts of the code to a subset of sensor nodes on multiple channels at once. In the latter approach, the nodes need to communicate with each other to receive the remaining parts of the program. In this paper, we propose a protocol for such gossip between nodes. To better utilize the multi-channel resources and reduce contention, our protocol provides a multi-channel sender selection algorithm. This algorithm attempts to ensure that in any neighborhood, at any time, there is at most one sensor transmitting on a given frequency. Moreover, our sender selection algorithm is greedy in that it tries to select the sender that is expected to have the most impact for each channel. Our protocol also conserves energy by putting the nodes that are unlikely to contribute or receive data shortly to "sleep" state. Through simulation, we show that our protocol is faster and more energy efficient than the existing reprogramming approaches that assume that the new program is initially located only on a small set of nodes. [ABSTRACT FROM AUTHOR]

The scope of wireless sensor network (WSN) applications has traditionally been restricted by physical sensor coverage and limited computational power. Meanwhile, IP networks like the Internet offer tremendous connectivity and computing resources. This paper presents Agimone, a middleware layer that integrates sensor and IP networks as a uniform platform for flexible application deployment. This layer allows applications to be deployed on the WSN in the form of mobile agents which can autonomously discover and migrate to other WSNs, using a common IP backbone as a bridge. Agimone is the first system that allows mobile agents to migrate between sensor and IP networks. It facilitates data sharing between WSNs and the IP network through remote tuple space operations, allowing sensors to easily defer expensive computations to more-powerful devices. We demonstrate the expressiveness of Agimone's programming model by examining a prototype cargo-tracking application. We also provide an empirical evaluation that demonstrates the efficiency of Agimone using two WSNs consisting of Mica2 motes connected by an IP network. [ABSTRACT FROM AUTHOR]

With the improvement in computer electronics in terms of processing, memory and communication capabilities, it has become possible to scatter tiny embedded devices such as sensor nodes to monitor physical phenomena with greater flexibility. A large number of sensor nodes, communicating over the wireless medium, also allows information gathering with greater accuracy than current systems. This paper presents a new stochastic technique known as Incremental Simultaneous Perturbation Approximation(ISPA) for performing optimization in wireless sensor networks. The proposed algorithm is based on a combination of gradient-based decentralized incremental (GBDI) optimization and Simultaneous Perturbation Stochastic Approximation (SPSA) techniques. The former is based on Incremental Sub-Gradient Optimization (ISGO) techniques that allow the algorithm to be performed in a distributed and collaborative manner. The latter component addresses the limitations of the GBDI component especially in real-world sensor networks. Specifically, the SPSA component is a model-free technique that finds the optimal solution without requiring a functional model such as an input-output relationship and a cost gradient. Simulation results show that the proposed ISPA approach not only achieves distributed optimization in a stochastic environment, but can also be implemented in a practical manner for resource-constrained devices. [ABSTRACT FROM AUTHOR]

We present a novel dynamic duty cycling scheme to maintain stochastic consistency for caches in sensor networks. To reduce transmissions, base stations often maintain caches for erratically changing sensor sources. Stochastic consistency guarantees the cache-source deviation is within a pre-specified bound with a certain confidence level. We model the erratic sources as Brownian motions, and adaptively predict the next cache update time based on the model. By piggybacking the next update time in each regular data packet, we can dynamically adjust the relaying nodes' duty cycles so that they are awake before the next update message arrives, and are sleeping otherwise. Through simulations, we show that our approach can achieve very high source-cache fidelity with low power consumption on many real-life sensor data. On average, our approach consumes 4-5 times less power than GAF [1], and achieves 50% longer network lifetime. [ABSTRACT FROM AUTHOR]

In the population protocol model introduced by Angluin et al. [2], a collection of agents, which are modelled by finite state machines, move around unpredictably and have pairwise interactions. The ability of such systems to compute functions on a multiset of inputs that are initially distributed across all of the agents has been studied in the absence of failures. Here, we show that essentially the same set of functions can be computed in the presence of halting and transient failures, provided preconditions on the inputs are added so that the failures cannot immediately obscure enough of the inputs to change the outcome. We do this by giving a general-purpose transformation that makes any algorithm for the fault-free setting tolerant to failures. [ABSTRACT FROM AUTHOR]

Inspired by the characteristics of biologically-motivated systems consisting of autonomous agents, we define the notion of stabilizing consensus in fully decentralized and highly dynamic ad hoc systems. Stabilizing consensus requires non-faulty nodes to eventually agree on one of their inputs, but individual nodes do not necessarily know when agreement is reached. First we show that, similar to the original consensus problem in the synchronous model, there exist deterministic solutions to the stabilizing consensus problem tolerating crash faults. Similarly, stabilizing consensus can also be solved deterministically in presence of Byzantine faults with the assumption that n > 3f where n is the number of nodes and f is the number of faulty nodes. Our main result is a Byzantine consensus protocol in a model in which the input to each node can change finitely many times during execution and eventually stabilizes. Finally we present an impossibility result for stabilizing consensus in systems of identical nodes. [ABSTRACT FROM AUTHOR]

Mobile entity navigation in dynamic environments is an essential part of many mission critical applications like search and rescue and fire fighting. The dynamism of the environment necessitates the mobile entity to constantly maintain a high degree of awareness of the changing environment. This criteria makes it difficult to achieve good navigation performance by using just on-board sensors and existing navigation methods and motivates the use of wireless sensor networks (WSNs) to aid navigation. In this paper, we present a novel approach that integrates a roadmap based navigation algorithm with a novel WSN query protocol called Roadmap Query (RQ). RQ enables collection of frequent, up-to-date information about the surrounding environment, thus allowing the mobile entity to make good navigation decisions. Simulation results under realistic fire scenarios show that in highly dynamic environments RQ outperforms existing approaches in both navigation performance and communication cost. We also present a mobile agent based implementation of RQ along with preliminary experimental results, on Mica2 motes. [ABSTRACT FROM AUTHOR]

Wireless sensor networks are often studied with the goal of removing information from the network as efficiently as possible. However, when the application also includes an actuator network, it is advantageous to determine actions in-network. In such settings, optimizing the sensor node behavior with respect to sensor information fidelity does not necessarily translate into optimum behavior in terms of action fidelity. Inspired by neural systems, we present a model of a sensor and actuator network based on the vector space tools of frame theory that applies to applications analogous to reflex behaviors in biological systems. Our analysis yields bounds on both absolute and average actuation error that point directly to strategies for limiting sensor communication based not only on local measurements but also on a measure of how important each sensor-actuator link is to the fidelity of the total actuation output. [ABSTRACT FROM AUTHOR]

A wide-area sensor system is a complex, dynamic, resource-rich collection of Internet-connected sensing devices. In this paper, we propose X-Tree Programming, a novel database-centric programming model for wide-area sensor systems designed to achieve the seemingly conflicting goals of expressiveness, ease of programming, and efficient distributed execution. To demonstrate the effectiveness of X-Tree Programming in achieving these goals, we have incorporated the model into IrisNet, a shared infrastructure for wide-area sensing, and developed several widely different applications, including a distributed infrastructure monitor running on 473 machines worldwide. [ABSTRACT FROM AUTHOR]

An increasing number of web-sites require users to establish an account before they can access the information stored on that site ("personalized web browsing"). Typically, the user is required to provide at least a unique username, a secret password and an e-mail address. Establishing accounts at multiple web-sites is a tedious task. A security-and privacy-aware user may have to invent a distinct username and a secure password, both unrelated to his/her identity, for each web-site. The user may also desire mechanisms for anonymous e-mail. Besides the information that the user supplies voluntarily to the web-site, additional information about the user may flow (involuntarily) from the user's site to the web-site, due to the nature of the HTTP protocol and the cookie mechanism. This paper describes the Janus Personalized Web Anonymizer, which makes personalized web browsing simple, secure and anonymous by providing convenient solutions to each of the above problems. Janus serves as an intermediary entity between a user and a web-site. Given a user and a web-site, Janus automatically generates an alias - typically a username, a password and an e-mail address - that can be used to establish an anonymous account at the web-site. Different aliases are generated for each user, web-site pair; however the same alias is presented whenever a particular user visits a particular web-site. Janus frees the user from the burden of inventing and memorizing distinct usernames and secure passwords for each web-site, and guarantees that an alias (including an e-mail address) does not reveal the true identity of the user. Janus also provides mechanisms to complete an anonymous e-mail exchange from a web-site to a user, and filters the information-flow of the HTTP protocol to preserve user privacy. Thus Janus provides simultaneous user identification and user privacy, as required for anonymous personalized web browsing. [ABSTRACT FROM AUTHOR]

Most sensor network research to date has targeted ad hoc wireless networks of closely co-located, resource-constrained, scalar sensor motes. Such work has tended to overlook the potential importance of wide-area sensor systems-heterogeneous collections of Internet-connected sensor devices. A wide-area sensor system enables a rich collection of sensors such as cameras, microphones, infrared detectors, RFID readers, vibration sensors, accelerometers, etc. to be incorporated into a unified system capable of accessing, filtering, processing, querying, and reacting to sensed data. The sensor system can be programmed to provide useful sensing services that combine traditional data sources with tens to millions of live sensor feeds. While the unique and many challenges of resource-constrained sensor networks are apparent, the limited research into wide-area sensor systems may indicate that researchers have not seen any interesting challenges in such systems. After all, where are the research challenges in sensor systems blessed with powerful, powered, Internet-connected computers with significant memory and storage? In this talk, I will describe five research challenges in wide-area sensor systems that I believe are worthy of further pursuit. The challenges are: (1) scalability, (2) ease of service authorship, (3) robustness/manageability, (4) actuation, and (5) privacy. Although certainly not an exhaustive list, I believe these five make the case that wide-area sensor systems are an interesting area with many challenges and open questions. In discussing the research challenges, I will highlight techniques used to address some of the challenges within IrisNet [1,2,3,4,5], a wide-area sensor system we have developed over the past three years. [ABSTRACT FROM AUTHOR]