Distributed Computing in Sensor Systems

Underwater wireless networks have recently gained a great deal of attention as a topic of research. Although there have been several recent studies on the performance of medium access control (MAC) protocols for such networks, they are mainly based on simulations, which can be insufficient for understanding the fundamental behavior of systems. In this work we show a way to analyze mathematically the performance of an underwater MAC protocol. We particularly analyze a propagation delay tolerant ALOHA (PDT-ALOHA) protocol proposed recently [1]. In this scheme, guard bands are introduced at each time slot to reduce collisions between senders with different distances to the receiver, which have a great impact on acoustic transmissions. We prove several interesting properties concerning the performance of this protocol. We also show that the maximum throughput decreases as the maximum propagation delay increases, identifying which protocol parameter values realize the maximum throughput approximately. Although it turns out that exact expression for the maximum throughput of PDT-ALOHA can be quite complicated, we propose a useful simple expression which is shown numerically to be a very good approximation. Our result can be interpreted to mean that the throughput of PDT-ALOHA protocol can be 17-100% higher than the conventional slotted ALOHA, with proper protocol parameter values

Time synchronization is a critical component in many wireless sensor network applications. Although several synchronization protocols have recently been developed, they tend to break down when implemented on networks of heterogeneous devices consisting of different hardware components and operating systems, and communicate over different network media. In this paper, we present a methodology for time synchronization in heterogeneous sensor networks (HSNs). This includes synchronization between mote and PC networks, a communication pathway that is often used in sensor networks, but has received little attention with respect to time synchronization. In addition, we evaluate clock skew compensation methods including linear regression, exponential averaging, and phase-locked loops. Our HSN synchronization methodology has been implemented as a network service and tested on an experimental testbed. We show that a 6-hop heterogeneous sensor network can be synchronized with an accuracy on the order of microseconds.

We propose a novel algorithm of counting indistinguishable objects by a collection of sensors. The information on multiple counting is recovered from the stochastic correlation patterns.

This paper studies the problem of associating deterministically a track revealed by a binary sensor network with the trajectory of a unique moving anonymous object, namely the

Multiple Object Tracking and Identification

(MOTI) problem. In our model, the network is represented by a sparse connected graph where each vertex represents a binary sensor and there is an edge between two sensors if an object can pass from a sensed region to another without activating any other remaining sensor. The difficulty of MOTI lies in the fact that trajectories of two or more objects can be so close (track merging) that the corresponding tracks on the sensor network can no longer be distinguished, thus confusing the deterministic association between an object trajectory and a track.

The paper presents several results. We first show that MOTI cannot be solved on a general graph of ideal binary sensors even by an omniscient external observer if all the objects can freely move on the graph. Then, we describe some restrictions that can be imposed

a priori

either on the graph, on the object movements or both, to make MOTI problem always solvable. We also discuss the consequences of our results and present some related open problems.

Wireless sensor networks are increasingly being used in environmental monitoring applications. Collecting raw data from these networks can lead to excessive energy consumption. This is especially true when the application requires specialized sensors that have very high energy consumption, e.g. hydrological sensors for monitoring marine environments. We describe an adaptive sensor sampling scheme where nodes change their sampling frequencies autonomously based on the variability of the measured parameters. The sampling scheme also meets the user’s sensing coverage requirements by using information provided by the underlying MAC protocol. This allows the scheme to automatically adapt to topology changes. Our results based on real and synthetic data sets, indicate a reduction in sensor sampling by up to 93%, reduction in message transmissions by up to 99% and overall energy savings of up to 87%. We also show that generally more than 90% of the collected readings fall within the user-defined error threshold.

We describe

LiveNet

, a set of tools and analysis methods for reconstructing the complex behavior of a deployed sensor network. LiveNet is based on the use of multiple passive packet sniffers co-located with the network, which collect packet traces that are merged to form a global picture of the network’s operation. The merged trace can be used to reconstruct critical aspects of the network’s operation that cannot be observed from a single vantage point or with simple application-level instrumentation. We address several challenges: merging multiple sniffer traces, determining sniffer coverage, and inference of missing information for routing path reconstruction. We perform a detailed validation of LiveNet’s accuracy and coverage using a 184-node sensor network testbed, and present results from a real-world deployment involving physiological monitoring of patients during a disaster drill. Our results show that LiveNet is able to accurately reconstruct network topology, determine bandwidth usage and routing paths, identify hot-spot nodes, and disambiguate sources of packet loss observed at the application level.

We propose a light-weight and scalable broadcast authentication scheme,

Curtain

, for sensor network. Instead of using Merkel tree to combine multiple

μ

TESLA instance, we apply compressed Bloom filters to multiple

μ

TESLA. Our scheme can support longer duration and prolong the self-healing property. We greatly reduce the communication overhead at the cost of allocating a moderate space in each receiver. Combing with PKC computation like ECC, our scheme can guarantee the long-term security and also mitigate energy consumption. Moreover, our methods can be extend to the situation of multiple senders, offering efficient user addition and revocation.

Aiming at a realistic mobile connectivity model for vehicular sensor networks in urban environments, we propose the combination of large-scale traffic simulation and computational tools to characterize fundamental graph-theoretic parameters. To illustrate the proposed approach, we use the DIVERT simulation framework to illuminate the temporal evolution of the average node degree in this class of networks and provide an algorithm for computing the transitive connectivity profile that ultimately determines the flow of information in a vehicular sensor network.

We propose FIT, a flexible, light-weight and real-time scheduling system for wireless sensor platforms. There are three salient features of FIT. First, its two-tier hierarchical framework supports customizable application-specific scheduling policies, hence FIT is very

flexible

. Second, FIT is

light-weight

in terms of minimizing thread number to reduce preemptions and memory consumption while at the same time ensuring system schedulability. We propose a novel Minimum Thread Scheduling Policy (MTSP) exploration algorithm within FIT to achieve this goal. Finally, FIT provides a detailed

real-time schedulability

analysis method to help check if application’s temporal requirements can be met. We implemented FIT on MICAz motes, and carried out extensive evaluations. Results demonstrate that FIT is indeed flexible and light-weight for implementing real-time applications, at the same time, the schedulability analysis provided can predict the real-time behavior. FIT is a promising scheduling system for implementing complex real-time applications in sensor networks.

It is an undeniable fact that people want information. Unfortunately, even in today’s highly automated society, a lot of the information we desire is still manually collected. An example is fuel prices where websites providing fuel price information either send their workers out to manually collect the prices or depend on volunteers manually relaying the information. This paper proposes a novel application of wireless sensor networks to automatically collect fuel prices from camera images of road-side price board (billboard) of service (or gas) stations. Our system exploits the ubiquity of mobile phones that have cameras as well as users contributing and sharing data. In our proposed system, cameras of contributing users will be automatically triggered when they get close to a service station. These images will then be processed by computer vision algorithms to extract the fuel prices. In this paper, we will describe the system architecture and present results from our computer vision algorithms. Based on 52 images, our system achieves a hit rate of 92.3% for correctly detecting the fuel price board from the image background and reads the prices correctly in 87.7% of them. To the best of our knowledge, this is the first instance of a sensor network being used for collecting consumer pricing information.

A number of recently proposed mobile sensor network architectures rely on uncontrolled, or weakly-controlled mobility to achieve sensing coverage over time at low cost, an opportunistic sensor networking approach. However, this reliance on mobility also introduces a number of challenges. In this paper, we discuss the challenges inherent in this networking paradigm, and describe two composable techniques, sensor sharing and substitution, to make the system more robust in terms of data fidelity and delay. We present a numerical analysis of these techniques, separately and in combination, based on a simple Markov model of an opportunistic sensor network.

The problem of sensor-network-based distributed intrusion detection in the presence of clutter is considered. It is argued that sensing is best regarded as a local phenomenon in that only sensors in the immediate vicinity of an intruder are triggered. In such a setting, lack of knowledge of intruder location gives rise to correlated sensor readings. A

signal-space

viewpoint is introduced in which the noise-free sensor readings associated to intruder and clutter appear as surfaces

$\mathcal{S_I}$

and

$\mathcal{S_C}$

and the problem reduces to one of determining in distributed fashion, whether the current noisy sensor reading is best classified as intruder or clutter. Two approaches to distributed detection are pursued. In the first, a decision surface separating

$\mathcal{S_I}$

and

$\mathcal{S_C}$

is identified using Neyman-Pearson criteria. Thereafter, the individual sensor nodes interactively exchange bits to determine whether the sensor readings are on one side or the other of the decision surface. Bounds on the number of bits needed to be exchanged are derived, based on communication complexity (CC) theory. A lower bound derived for the two-party average case CC of general functions is compared against the performance of a greedy algorithm. The average case CC of the relevant

greater-than (GT)

function is characterized within two bits. In the second approach, each sensor node broadcasts a single bit arising from appropriate two-level quantization of its own sensor reading, keeping in mind the fusion rule to be subsequently applied at a local fusion center. The optimality of a threshold test as a quantization rule is proved under simplifying assumptions. Finally, results from a QualNet simulation of the algorithms are presented that include intruder tracking using a naive polynomial-regression algorithm.

We compare the performance of standard data compression techniques in the presence of communication failures. Their performance is inferior to sending data without compression when the packet loss rate of a link is above 10%. We have developed fault-tolerant compression algorithms for sensor networks that are robust against packet loss and achieve low delays in data decoding, thus being particularly suitable for time-critical applications. We show the advantage of our technique by providing results from our extensive experimental evaluation using real sensor datasets.

Sensor network simulators are important tools for the design, implementation and evaluation of wireless sensor networks. Due to the large computational requirements necessary for simulating wireless sensor networks with high fidelity, many wireless sensor network simulators, especially the cycle accurate ones, employ distributed simulation techniques to leverage the combined resources of multiple processors or computers. However, the large overheads in synchronizing sensor nodes during distributed simulations of sensor networks result in a significant increase in simulation time. In this paper, we present a novel technique that could significantly reduce such overheads by minimizing the number of sensor node synchronizations during simulations. We implement this technique in Avrora, a widely used parallel sensor network simulator, and achieve a speedup of up to 11 times in terms of average simulation speed in our test cases. For applications that have lower duty cycles, the speedups are even greater since the performance gains are proportional to the sleep times of the sensor nodes.

When a sensor network is deployed in the field it is typically required to support multiple simultaneous missions, which may start and finish at different times. Schemes that match sensor resources to mission demands thus become necessary. In this paper, we consider new sensor-assignment problems motivated by frugality, i.e., the conservation of resources, for both static and dynamic settings. In general, the problems we study are NP-hard even to approximate, and so we focus on heuristic algorithms that perform well in practice. In the static setting, we propose a greedy centralized solution and a more sophisticated solution that uses the Generalized Assignment Problem model and can be implemented in a distributed fashion. In the dynamic setting, we give heuristic algorithms in which available sensors propose to nearby missions as they arrive. We find that the overall performance can be significantly improved if available sensors sometimes refuse to offer utility to missions they could help based on the value of the mission, the sensor’s remaining energy, and (if known) the remaining target lifetime of the network. Finally, we evaluate our solutions through simulations.

We propose

Tug-of-War

(

ToW

) for data storage and query mechanism in sensor networks. ToW is based on the concept of

data-centric storage

where events and queries meet on some rendezvous node so that queries for the events can be sent directly to the node without being flooded to the network. However, rather than fixing the rendezvous point, we dynamically replicate the point and float them in between query nodes and event sensor nodes according to the relative frequencies of events and queries. By carefully calculating the optimal setting, we are able to minimize the total communication costs while adapting to the environment.

While deployment and practical on-site testing remains the ultimate touchstone for sensor network code, good simulation tools can help curtail in-field troubleshooting time. Unfortunately, current simulators are successful only at evaluating system performance and exposing manifestations of errors. They are not designed to diagnose the root cause of the exposed anomalous behavior. This paper presents a

diagnostic simulator

, implemented as an extension to TOSSIM [6]. It (i) allows the user to ask questions such as “why is (some specific) bad behavior occurring?”, and (ii) conjectures on possible causes of the user-specified behavior when it is encountered during simulation. The simulator works by logging event sequences and states produced in a regular simulation run. It then uses sequence extraction, and frequent pattern analysis techniques to recognize sequences and states that are possible root causes of the user-defined undesirable behavior. To evaluate the effectiveness of the tool, we have implemented the directed diffusion protocol and used our tool during the development process. During this process the tool was able to uncover two design bugs that were not addressed in the original protocol. The manifestation of these two bugs were same but the causes of failure were completely different - one was triggered by node reboot and the other was triggered by an overflow of timestamps generated by the local clock. The case study demonstrates a success scenario for diagnostic simulation.

Sensors have been increasingly used for many ubiquitous computing applications such as asset location monitoring, visual surveillance, and human motion tracking. In such applications, it is important to place sensors such that every point of the target area can be sensed by more than one sensor. Especially, many practical applications require

3-coverage

for triangulation, 3D hull building, and etc. Also, in order to extract meaningful information from the data sensed by multiple sensors, those sensors need to be placed not too close to each other—

minimum separation requirement

. To address the 3-coverage problem with the minimum separation requirement, this paper proposes two methods, so called,

overlaying method

and

TRE-based method

, which complement each other depending on the minimum separation requirement. For these two methods, we also provide mathematical analysis that can clearly guide us when to use the TRE-based method and when to use the overlaying method and also how many sensors are required. To the best of our knowledge, this is the first work that systematically addresses the 3-coverage problem with the minimum separation requirement.

A fundamental class of problems in wireless communication is concerned with the assignment of suitable transmission powers to wireless devices/stations such that the resulting communication graph satisfies certain desired properties and the overall energy consumed is minimized. Many concrete communication tasks in a wireless network like broadcast, multicast, point-to-point routing, creation of a communication backbone, etc. can be regarded as such a power assignment problem.

This paper considers several problems of that kind; the first problem was studied before in [1,6] and aims to select and assign powers to

k

out of a total of

n

wireless network stations such that all stations are within reach of at least one of the selected stations. We show that the problem can be (1 + 

ε

) approximated by only looking at a small subset of the input, which is of size

, i.e. independent of

n

and polynomial in

k

and 1/

ε

. Here

d

denotes the dimension of the space where the wireless devices are distributed, so typically

d

 ≤ 3 and

describes the relation between the Euclidean distance between two stations and the power consumption for establishing a wireless connection between them. Using this

coreset

we are able to improve considerably on the running time of

$n^{((\alpha/\epsilon)^{O(d)})}$

for the algorithm by Bilo et al. at ESA’05 ([6]) actually obtaining a running time that is

linear

in

n

. Furthermore we sketch how outliers can be handled in our coreset construction.

The second problem deals with the energy-efficient, bounded-hop multicast operation: Given a subset

C

out of a set of

n

stations and a designated source node

s

we want to assign powers to the stations such that every node in

C

is reached by a transmission from

s

within

k

hops. Again we show that a coreset of size independent of

n

and polynomial in

k

, |

C

|, 1/

ε

exists, and use this to provide an algorithm which runs in time linear in

n

.

The last problem deals with a variant of non-metric TSP problem where the edge costs are the squared Euclidean distances; this problem is motivated by data aggregation schemes in wireless sensor networks. We show that a good TSP tour under Euclidean edge costs can be very bad in the squared distance measure and provide a simple constant approximation algorithm, partly improving upon previous results in [5], [4].

Wireless sensor nodes can act as distributed detectors for recognizing activities online, with the final goal of assisting the users in their working environment. We propose an activity recognition architecture based on fuzzy logic, through which multiple nodes collaborate to produce a reliable recognition result from unreliable sensor data. As an extension to the regular fuzzy inference, we incorporate temporal order knowledge of the sequences of operations involved in the activities. The performance evaluation is based on experimental data from a car assembly trial. The system achieves an overall recognition performance of 0.81 recall and 0.79 precision with regular fuzzy inference, and 0.85 recall and 0.85 precision when considering temporal order knowledge. We also present early experiences with implementing the recognition system on sensor nodes. The results show that the algorithms can run online, with execution times in the order of 40ms, for the whole recognition chain, and memory overhead in the order of 1.5kB RAM.

We propose

CaliBree

, a self-calibration system for mobile wireless sensor networks. Sensors calibration is a fundamental problem in a sensor network. If sensor devices are not properly calibrated, their sensor readings are likely of little use to the application. Distributed calibration is challenging in a mobile sensor network, where sensor devices are carried by people or vehicles, mainly for three reasons:

i)

the sensing contact time, i.e., the amount of time nodes are within the sensing range of each other, can be very limited, requiring a quick and efficient calibration technique;

ii)

for scalability and ease of use, the calibration algorithm should not require manual intervention;

iii)

the computational burden must be low since some sensor platforms have limited capabilities. In this paper we propose CaliBree, a distributed, scalable, and lightweight calibration protocol that applies a discrete average consensus algorithm technique to calibrate sensor nodes. CaliBree is shown to be effective through experimental evaluation using embedded wireless sensor devices, achieving high calibration accuracy.

We consider a mobile sensor network monitoring a spatio-temporal field. Given limited caches at the sensor nodes, the goal is to develop a distributed cache management algorithm to efficiently answer queries with a known probability distribution over the spatial dimension. First, we propose a novel distributed information theoretic approach assuming knowledge of the distribution of the monitored phenomenon. Under this scheme, nodes minimize an entropic utility function that captures the average amount of uncertainty in queries given the probability distribution of query locations. Second, we propose a correlation-based technique, which only requires knowledge of the second-order statistics, relaxing the stringent constraint of a priori knowledge of the query distribution, while significantly reducing the computational overhead. We show that the proposed approaches considerably improve the average field estimation error. Further, we show that the correlation-based technique is robust to model mismatch in case of imperfect knowledge of the underlying generative correlation structure.

Visual coverage is an essential issue in the research on visual sensor networks. However, because of the presence of visual occlusions, the statistics of visual coverage blend the statistics of nodes and targets and are extremely difficult to derive. By assuming the deployment of nodes as a stationary Poisson point process and ignoring boundary effects, this paper presents the first attempt to estimate the probability that an arbitrary target in the field is visually

k

-covered. The major challenge for the estimation is how to formulate the probability (

q

) that a node captures a target in its visual range. To tackle this challenge, we first assume a visual detection model that takes visual occlusions into account and then derive several significant statistical parameters of

q

based on this model. According to these parameters, we can finally reconstruct the probability density function of

q

as a combination of a Binomial function and an impulse function. With the estimated coverage statistics, we further propose an estimate of the minimum node density that suffices to ensure a

K

-coverage across the field.

Most papers on sensing in wireless sensor networks use only very simple sensors, e.g. humidity or temperature, to illustrate their concepts. However, in a large number of scenarios including structural health monitoring, more complex sensors that usually employ medium to high frequency sampling and post-processing are required. Additionally, to capture an event completely several sensors of different types are needed which have to be in range of the event and used in a timely manner. We study the problem of time-bounded and space-bounded sensing where parallel use of different sensors on the same node is impossible and not all nodes possess all required sensors. We provide a model formalizing the requirements and present algorithms for spatial grouping and temporal scheduling to tackle these problems.

This paper presents a protocol called SAKE (Software Attestation for Key Establishment), for establishing a shared key between any two neighboring nodes of a sensor network. SAKE guarantees the secrecy and authenticity of the key that is established, without requiring any prior authentic or secret information in either node. In other words, the attacker can read and modify the entire memory contents of both nodes before SAKE executes. Further, to the best of our knowledge, SAKE is the only protocol that can perform key re-establishment after sensor nodes are compromised, because the presence of the attacker’s code in the memory of either protocol participant does not compromise the security of SAKE. Also, the attacker can perform any active or passive attack using an arbitrary number of malicious, colluding nodes. SAKE does not require any hardware modification to the sensor nodes, human mediation, or secure side channels. However, we do assume the setting of a computationally-limited attacker that does not introduce its own computationally powerful nodes into the sensor network.

SAKE is based on ICE (Indisputable Code Execution), a primitive we introduce in previous work to dynamically establish a trusted execution environment on a remote, untrusted sensor node.

Unlike traditional multihop forwarding among homogeneous static sensor nodes, use of mobile devices for data collection in wireless sensor networks has recently been gathering more attention. It is known that the use of mobility significantly reduces the energy consumption at each sensor, elongating the functional lifetime of the network, in exchange for increased data delivery latency. However, in previous work, mobility and communication capabilities are often underutilized, resulting in suboptimal solutions incurring unnecessarily large latency. In this paper, we focus on the problem of finding an optimal path of a mobile device, which we call “data mule,” to achieve the smallest data delivery latency in the case of minimum energy consumption at each sensor, i.e., each sensor only sends its data directly to the data mule. We formally define the path selection problem and show the problem is

$\mathcal{NP}$

-hard. Then we present an approximation algorithm and analyze its approximation factor. Numerical experiments demonstrate that our approximation algorithm successfully finds the paths that result in 10%-50% shorter latency compared to previously proposed methods, suggesting that controlled mobility can be exploited much more effectively.

Wireless sensor networks come of age and start moving out of the laboratory into the field. As the number of deployments is increasing the need for an efficient and reliable code update mechanism becomes pressing. Reasons for updates are manifold ranging from fixing software bugs to retasking the whole sensor network. The scale of deployments and the potential physical inaccessibility of individual nodes asks for a wireless software management scheme. In this paper we present an efficient code update strategy which utilizes the knowledge of former program versions to distribute mere incremental changes. Using a small set of instructions, a delta of minimal size is generated. This delta is then disseminated throughout the network allowing nodes to rebuild the new application based on their currently running code. The asymmetry of computational power available during the process of encoding (PC) and decoding (sensor node) necessitates a careful balancing of the decoder complexity to respect the limitations of today’s sensor network hardware. We provide a seamless integration of our work into Deluge, the standard TinyOS code dissemination protocol. The efficiency of our approach is evaluated by means of testbed experiments showing a significant reduction in message complexity and thus faster updates.

We present the first local approximation schemes for maximum independent set and minimum vertex cover in unit disk graphs. In the graph model we assume that each node knows its geographic coordinates in the plane (location aware nodes). Our algorithms are local in the sense that the status of each node

v

(whether or not

v

is in the computed set) depends only on the vertices which are a constant number of hops away from

v

. This constant is independent of the size of the network. We give upper bounds for the constant depending on the desired approximation ratio. We show that the processing time which is necessary in order to compute the status of a single vertex is bounded by a polynomial in the number of vertices which are at most a constant number of vertices away from it. Our algorithms give the best possible approximation ratios for this setting.

The technique which we use to obtain the algorithm for vertex cover can also be employed for constructing the first global PTAS for this problem in unit disk graph which does not need the embedding of the graph as part of the input.

Sensor networks can be viewed as large distributed databases, and SQL-like high-level declarative languages can be used for data and information retrieval. Energy constraints make optimizing query processing particularly important. This paper addresses for the first time, multi-root, multi-query optimization for long duration aggregation queries. The paper formulates three algorithms - naive algorithm (NMQ), which does not exploit any query result sharing, and two proposed new algorithms: an optimal algorithm (OMQ) and a heuristic (zone-based) algorithm (ZMQ). The heuristic algorithm is based on sharing the partially aggregated results of pre-configured geographic regions and exploits the novel idea of applying a grouping technique by using the location attribute of sensor nodes as the grouping criterion. Extensive simulations indicate that the proposed algorithms provide significant energy savings under a wide range of sensor network deployments and query region options.

The use of mobile sensors is motivated by the necessity to monitor critical areas where sensor deployment cannot be performed manually. In these working scenarios, sensors must adapt their initial position to reach a final deployment which meets some given performance objectives such as coverage extension and uniformity, total moving distance, number of message exchanges and convergence rate.

We propose an original algorithm for autonomous deployment of mobile sensors called

Snap & Spread

. Decisions regarding the behavior of each sensor are based on locally available information and do not require any prior knowledge of the operating conditions nor any manual tuning of key parameters. We conduct extensive simulations to evaluate the performance of our algorithm. This experimental study shows that, unlike previous solutions, our algorithm reaches a final stable deployment, uniformly covering even irregular target areas. Simulations also give insights on the choice of some algorithm variants that may be used under some different operative settings.

This paper introduces a framework for in-field-maintenance services for wireless sensor networks. The motivation of this work is driven by an observation that many applications using wireless sensor networks require one-time deployment and will be largely unattended. It is also desirable for the applications to have a long system lifetime. However, the performance of many individual protocols and the overall performance of the system deteriorate over time. The framework we present here allows the system or each individual node in the network to identify the performance degradation, and to act to bring the system back to a desirable coherent state. We implement and apply our framework to a case study for a real system, called VigilNet [5]. The performance evaluation demonstrates that our framework is effective and efficient.

Position verification problem is an important building block for a large subset of wireless sensor networks (WSN) applications. As a result, the performance of the WSN degrades significantly when misbehaving nodes report false location information in order to fake their actual position. In this paper we propose the first deterministic distributed protocol for accurate identification of faking sensors in a WSN. Our scheme does

not

rely on a subset of

trusted

nodes that cooperate and are not allowed to misbehave. Thus, any subset of nodes is allowed to try faking its position. As in previous approaches, our protocol is based on distance evaluation techniques developed for WSN.

On the positive side, we show that when the received signal strength (RSS) technique is used, our protocol handles at most

$\lfloor \frac{n}{2} \rfloor-2$

faking sensors. When the time of flight (ToF) technique is used, our protocol manages at most

$\lfloor \frac{n}{2} \rfloor - 3$

misbehaving sensors. On the negative side, we prove that no deterministic protocol can identify faking sensors if their number is

$\lceil \frac{n}{2}\rceil -1$

. Thus, our scheme is almost optimal with respect to the number of faking sensors.

We discuss application of our technique in the trusted sensor model. More specifically, our results can be used to minimize the number of trusted sensors that are needed to defeat faking ones.

Energy is one of the most crucial aspects in real deployments of mobile sensor networks. As a result of scarce resources, the duration of most real deployments can be limited to just several days, or demands considerable maintenance efforts (e.g., in terms of battery substitution). A large portion of the energy of sensor applications is spent in node discovery as nodes need to periodically advertise their presence and be awake to discover other nodes for data exchange. The optimization of energy consumption, which is generally a hard task in fixed sensor networks, is even harder in mobile sensor networks, where the neighbouring nodes change over time.

In this paper we propose an algorithm for energy efficient node discovery in sparsely connected mobile wireless sensor networks. The work takes advantage of the fact that nodes have temporal patterns of encounters and exploits these patterns to drive the duty cycling. Duty cycling is seen as a sampling process and is formulated as an optimization problem. We have used reinforcement learning techniques to detect and dynamically change the times at which a node should be awake as it is likely to encounter other nodes. We have evaluated our work using real human mobility traces, and the paper presents the performance of the protocol in this context.

In this paper, we address the

optimal connected sensing coverage

problem, i.e., how mobile sensors with limited sensing capabilities can cooperatively adjust their locations so as to maximize the extension of the covered area while avoiding any internal “holes”, areas that are not covered by any sensor. Our solution consists in a

distributed motion algorithm

that is based on an original extension of the Voronoi tessellation.

Focusing on the assessment of environmental noise pollution in urban areas, we provide qualitative considerations and experimental results to show the feasibility of wireless sensor networks to be used in this context. To select the most suitable data collection protocol for the specific noise monitoring application scenario, we evaluated the energy consumption performances of the CTP (Collection Tree Protocol) and DMAC protocols. Our results show that CTP, if used enabling the LPL (Low Power Listening) option, provides the better performances trade-off for noise monitoring applications.

This paper presents an energy-aware, sleep scheduling algorithm called SSMTT to support multiple target tracking sensor networks. SSMTT leverages the awakening result of interfering targets to save the energy consumption on proactive wake-up communication. For the alarm message-miss problem introduced by multiple target tracking, we present a solution that involves scheduling the sensor nodes’ sleep pattern. We compare SSMTT against three sleep scheduling algorithms for single target tracking: the legacy circle scheme, MCTA, and TDSS. Our experimental evaluations show that SSMTT achieves better energy efficiency than handling multiple targets separately through single target tracking algorithms.

This paper addresses the optimal rate allocation (ORA) problem as follows: given a target bit rate constraint, determine an optimal rate allocation among sensors such that the overall distortion of the reproduction data is minimized. Optimal rate allocation algorithms are proposed to determine the coding bit rate of each sensor in single hop and multihop sensor networks, given a target rate constraint. Extensive simulations are conducted by using temperature readings of the real world dataset. The results show that at low bit rates the optimal rate allocation improves about 2.745 dB on the uniform rate allocation in terms of SNR, and improves nearly 7.602 in terms of MSE. Spatial-temporal range queries are also evaluated to confirm that our approach is often sufficient to provide approximate statistics for range queries.

Data-driven macroprogramming of wireless sensor networks (WSNs) provides an easy to use high-level task graph representation to the application developer. However, determining an energy-efficient initial placement of these tasks onto the nodes of the target network poses a set of interesting problems. We present a framework to model this task-mapping problem arising in WSN macroprogramming. Our model can capture task placement constraints, and supports easy specification of energy-based optimization goals. Using our framework, we provide mathematical formulations for the task-mapping problem for two different metrics — energy balance and total energy spent. Due to the complex nature of the problems, these formulations are not linear. We provide linearization heuristics for the same, resulting in mixed-integer programming (MIP) formulations. We also provide efficient heuristics for the above. Our experiments show that the our heuristics give the same results as the MIP for real-world sensor network macroprograms, and show a speedup of up to several orders of magnitude.

This paper develops an algorithm for robust human activity recognition in the face of imprecise sensor placement. It is motivated by the emerging

body sensor networks

that monitor human activities (as opposed to environmental phenomena) for medical, entertainment, health-and-wellness, training, assisted-living, or entertainment reasons. Activities such as sitting, writing, and walking have been successfully inferred from data provided by body-worn accelerometers. A common concern with previous approaches is their sensitivity with respect to sensor placement. This paper makes two contributions. First, we explicitly address robustness of human activity recognition with respect to changes in accelerometer orientation. We develop a novel set of features based on relative activity-specific body-energy allocation and successfully apply them to recognize human activities in the presence of imprecise sensor placement. Second, we evaluate the accuracy of the approach using empirical data from body-worn sensors.

Interactive wireless sensor networks (IWSNs) manifest diverse application architectures, hardware capabilities, and user interactions that challenge existing centralized [1], or VM-based [2] query system designs. To support in-network processing of streaming sensor data in such heterogeneous environments, we created SenQ, a multi-layer embedded query system. SenQ enables user-driven and peer-to-peer in-network query issue by wearable interfaces and other resource-constrained devices. Complex virtual sensors and user-created streams can be dynamically discovered and shared, and SenQ is extensible to new sensors and processing algorithms. We evaluated SenQ’s efficiency and performance in a testbed for assisted-living, and show that on-demand buffering, query caching, efficient restart and other optimizations reduce network overhead and minimize data latency.

In wireless sensor networks, each sensor node has very small memory space compared with any other embedded computing systems. For this reason, operating systems running on the sensor nodes cannot allocate sufficient fixed-size stack space for all threads. In the previous work, SESAME was proposed to allocate stack space more space-efficiently, but there is a problem of time overhead. In this paper, we present SESAME-P, which is a dynamic stack allocation scheme based on memory pool. The size of memory pool is predetermined by using static analysis of each function’s stack usage information. Using the determined memory pool, SESAME-P reduces the dynamic stack allocation cost. Our experimental results show that SESAME-P significantly reduces the time overhead compared with the existing SESAME.