Theoretical Aspects of Distributed Computing in Sensor Networks

Moore’s law, automation considerations, and the pervasive need for timely information lead to a next generation of distributed systems that are open, highly interconnected, and deeply embedded in the physical world by virtue of pervasive sensing and sensor-based decision-making. These systems offer new research challenges that stem from scale, composition of large numbers of components, and tight coupling between computation, communication, and distributed interaction with both physical and social contexts. These growing challenges span a large spectrum ranging from new models of computation for systems that live in physical and social spaces, to the enforcement of reliable, predictable, and timely end-to-end behavior in the face of high interactive complexity, increased uncertainty, and imperfect implementation. This chapter discusses the top challenges in composing large-scale sensing systems and conjectures on research directions of increasing interest in this realm.

In the interference scheduling problem, one is given a set of n communication requests each of which corresponds to a sender and a receiver in a multipoint radio network. Each request must be assigned a power level and a color such that signals in each color class can be transmitted simultaneously. The feasibility of simultaneous communication within a color class is defined in terms of the signal to interference plus noise ratio (SINR) that compares the strength of a signal at a receiver to the sum of the strengths of other signals. This is commonly referred to as the “physical model” and is the established way of modeling interference in the engineering community. The objective is to minimize the schedule length corresponding to the number of colors needed to schedule all requests. We study oblivious power assignments in which the power value of a request only depends on the path loss between the sender and the receiver, e.g., in a linear fashion. At first, we present a measure of interference giving lower bounds for the schedule length with respect to linear and other power assignments. Based on this measure, we devise distributed scheduling algorithms for the linear power assignment achieving the minimal schedule length up to small factors. In addition, we study a power assignment in which the signal strength is set to the square root of the path loss. We show that this power assignment leads to improved approximation guarantees in two kinds of problem instances defined by directed and bidirectional communication request. Finally, we study the limitations of oblivious power assignments by proving lower bounds for this class of algorithms.

Connectivity in wireless sensor networks may be established using either omnidirectional or directional antennae. The former radiate power uniformly in all directions while the latter emit greater power in a specified direction thus achieving increased transmission range and encountering reduced interference from unwanted sources. Regardless of the type of antenna being used the transmission cost of each antenna is proportional to the coverage area of the antenna. It is of interest to design efficient algorithms that minimize the overall transmission cost while at the same time maintaining network connectivity. Consider a set S of n points in the plane modeling sensors of an ad hoc network. Each sensor is equipped with a fixed number of directional antennae modeled as a circular sector with a given spread (or angle) and range (or radius). Construct a network with the sensors as the nodes and with directed edges (u,v) connecting sensors u and v if v lies within u’s sector. We survey recent algorithms and study trade-offs on the maximum angle, sum of angles, maximum range, and the number of antennae per sensor for the problem of establishing strongly connected networks of sensors.

Motivated by a routing protocol with VCG-style payments, we investigate the combinatorial problem of placing new devices in an ad hoc network such that the resulting shortest path transmission costs, defined as sums of squared Euclidean distances, are minimum. For the cases of only one new device and of one communication request with multiple devices with identical transmission ranges, we provide polynomial-time algorithms. On the negative side, we show that even for a single communication request, placing multiple new devices with different transmission ranges is NP-hard. For identical transmission ranges, the placement of multiple new devices is NP-hard under multiple communication requests.

This is a joint work with Ioannis Chatzigiannakis and Othon Michail. We discuss here the population protocol model and most of its well-known extensions. The population protocol model aims to represent sensor networks consisting of tiny computational devices with sensing capabilities that follow some unpredictable and uncontrollable mobility pattern. It adopts a minimalistic approach and, thus, naturally computes a quite restricted class of predicates and exhibits almost no fault tolerance. Most recent approaches make extra realistic and implementable assumptions, in order to gain more computational power and/or speedup the time to convergence and/or improve fault tolerance. In particular, the mediated population protocol model, the community protocol model, and the PALOMA model, which are all extensions of the population protocol model, are thoroughly discussed. Finally, the inherent difficulty of verifying the correctness of population protocols that run on complete communication graphs is revealed, but a promising algorithmic solution is presented.

We survey the main theoretical aspects of models for mobile ad hoc networks (MANETs). We present theoretical characterizations of mobile network structural properties, different dynamic graph models of MANETs, and finally we give detailed summaries of a few selected articles. In particular, we focus on articles dealing with connectivity of mobile networks and on articles which show that mobility can be used to propagate information between nodes of the network while at the same time maintaining small transmission distances and thus saving energy.

The data sensed by different sensors in a sensor network is typically correlated. A natural question is whether the data correlation can be exploited in innovative ways along with network information transfer techniques to design efficient and distributed schemes for the operation of such networks. This necessarily involves a coupling between the issues of compression and networked data transmission that have usually been considered separately. In this work we review the basics of classical distributed source coding and discuss some practical code design techniques for it. We argue that the network introduces several new dimensions to the problem of distributed source coding. The compression rates and the network information flow constrain each other in intricate ways. In particular, we show that network coding is often required for optimally combining distributed source coding and network information transfer and discuss the associated issues in detail. We also examine the problem of resource allocation in the context of distributed source coding over networks.

Identifying locations of nodes in wireless sensor networks (WSNs) is critical to both network operations and most application level tasks. Sensor nodes equipped with geographical positioning system (GPS) devices are aware of their locations at a precision level of few meters. However, installing GPS devices on a large number of sensor nodes not only is expensive but also affects the form factor of these nodes. Moreover, GPS-based localization is not applicable in the indoor environments such as buildings. There exists an extensive body of research literature that aims at obtaining absolute locations as well as relative spatial locations of nodes in a WSN without requiring specialized hardware at large scale. The typical approach consists of employing only a limited number of anchor nodes that are aware of their own locations, and then trying to infer locations of non-anchor nodes using graph-theoretic, geometric, statistical, optimization, and machine learning techniques. Thus, the literature represents a very rich ensemble of algorithmic techniques applicable to low power, highly distributed nodes with resource-optimal computations. In this chapter we take a close look at the algorithmic aspects of various important localization techniques for WSNs.

Context represents any knowledge obtained from Wireless Sensor Networks (WSNs) regarding the object being monitored. Context-awareness is an important feature of WSN applications as it provides an ultimate tool for making the applications “smart”. The information about a sensed in a WSN phenomenon is comprehensive only when it includes the geographical location and the time of occurrence of the phenomenon. Thus, the location and time are essential constituents of WSNs’ context, though the concept of context is not limited to only space and time. In this chapter, we consider the spatio-temporal context of WSNs as it serves as a foundation for context-aware systems. In order to build context-aware WSNs it is necessary to consider three areas concerning the spatio-temporal correlation of events sensed in WSNs: node localization, temporal event ordering and time synchronization. While localization’s task is to provide geographic coordinates of a sensed event, preserving temporal relationships of the events in WSNs is necessary for ensuring their correct interpretation at the monitoring centre and for taking proper and prompt actions. The latter can be achieved by guaranteeing time synchronization and temporal event ordering mechanisms. We present an overview of selected algorithms in each of the areas, first providing the necessary background and then presenting a comparison of features of the discussed algorithms.

We study the problem of data propagation in distributed wireless sensor networks. We present two characteristic methods for data propagation: the first one performs a local, greedy optimization to minimize the number of data transmissions needed, while the second creates probabilistically optimized redundant data transmissions to trade off energy efficiency with fault tolerance. Both approaches make use of randomization at both the algorithmic design and analysis; this demonstrates the suitability for distributed sensor network algorithms of probabilistic techniques, because of their simplicity, locality, efficiency, and load-balancing features.

We present oblivious routing algorithms whose routing paths are constructed independent of each other, with no dependence on the routing history. Oblivious algorithms are inherently adaptive to dynamic packet traffic, exhibit low congestion, and require low maintenance. All these attributes make oblivious algorithms to be suitable for sensor networks which are characterized by their limited energy and computational resources. Specifically, low congestion provides load balancing, and low stretch provides low-energy utilization. We present two simple oblivious routing algorithms. The first algorithm is for geometric networks in which nodes are embedded in the Euclidean plane. In this algorithm, a packet path is constructed by first choosing a random intermediate node in the space between the source and destination and then the packet is sent to its destination through the intermediate node. In the second algorithm we study mesh networks, where the nodes are arranged in a two-dimensional grid. Grids are interesting symmetric topologies which can be used as a testbed for designing efficient new routing algorithms in sensor networks. The oblivious algorithm in the mesh constructs the paths by decomposing the network into smaller submeshes in a hierarchical manner. This algorithm can be extended to d dimensions, which makes it suitable for three-dimensional sensor network deployments, such as in buildings and tall structures. We analyze the algorithms in terms of the stretch and congestion of the resulting paths and demonstrate that they exhibit near optimal performance.

Geometric routing protocols are a memoryless and scalable approach which uses position information for routing. Principles of geometric routing approaches are very simple. Every node is assumed to be aware of the location of itself, of its neighbors, and of the destination. Based only on these information, every node is able to perform a routing decision. The location can be determined by either geographic coordinates (we thus talk of geographic routing) or logical coordinates extracted from the environment. In the former case, location coordinates may be derived thanks to GPS or estimated thanks to any other positioning mean such as triangulation. In the latter case, a new coordinate system has to be built. This chapter reviews the main routing algorithms in every coordinate-based system, highlighting the strengths and weaknesses of each of them.

We study the problem of energy-balanced data propagation in wireless sensor networks. The energy balance property guarantees that the average per sensor energy dissipation is the same for all sensors in the network, during the entire execution of the data propagation protocol. This property is important since it prolongs the network’s lifetime by avoiding early energy depletion of sensors. We first present a basic algorithm that in each step probabilistically decides whether to propagate data one-hop towards the final destination (the sink), or to send data directly to the sink. This randomized choice balances the (cheap, but slow) one-hop transmissions with the direct transmissions to the sink, which are more expensive but “bypass” the bottleneck region around the sink and propagate data fast. Note that in most protocols, the sensors lying closer to the sink tend to be overused and “die out” early. By a detailed analysis we precisely estimate the probabilities for each propagation choice in order to guarantee energy balance. The needed estimations can easily be performed by current technology sensors using simple to obtain information. Under some assumptions, we also derive a closed form for these probabilities. The fact (shown by our analysis) that direct (expensive) transmissions to the sink are needed only rarely, shows that our protocol, besides energy balanced, is also energy efficient. We then enhance this basic result with some recent findings including a generalized algorithm and demonstrating the optimality of this two-way probabilistic data propagation, as well as providing formal proofs of the energy optimality of the energy balance property.

In this chapter, we consider a large-scale sensor network, in a circular field, modeled as concentric coronas centered at a sink node. The tiny wireless sensors, severely limited by battery energy, alternate between sleep and awake periods, whereas the sink is equipped with high transmission power and long battery life. The traffic from sensors to the sink follows multi-hop paths in a many-to-one communication pattern. We consider two fundamental and strictly related problems, the localization and the energy hole problems. We first survey on recent algorithms most extensively studied in the literature and summarize their pros and cons with respect to our assumptions. Then we present our solutions tailored for dense and randomly deployed networks. In our localization protocol, the sensors learn their coarse-grain position with respect to the sink, and hence the sink acts as a reference point for the network algorithms, in particular the routing algorithm. For this role of the sink, the network may incur in a special energy hole problem, known as the sink hole problem. From this perspective, the localization and energy hole problems are strictly related. Our solution for the energy hole problem adopts a non-uniform sensor distribution, compatible with the proposed localization solutions, that adds more sensors to the coronas with heavier traffic. In conclusion, we show that the network model under consideration can solve the localization and energy hole problems by properly tuning some network parameters, such as network density.

Sensor networks are one of the most relevant concrete examples of dynamic networks. Their dynamic behavior is mainly due to the presence of node/link faults and node mobility. The aim of this chapter is to survey a new approach to study such dynamic networks, recently introduced in [15–19]. The major novelty of this approach relies on two basic issues.

2. This new approach provides a general framework where it is possible to determine the speed of information spreading from an analytical point of view.

Does the dynamic unknown behavior of sensor networks always slow down the speed of information spreading? What is the real impact of this dynamic behavior on the completion time of some basic communication protocols? Can unknown random node mobility be exploited to asymptotically speedup information spreading?

This new general approach provides some clean mathematical answers to the above fundamental questions.

Self-stabilizing algorithms can be started in any arbitrary state to exhibit a desired behavior following a convergence period. The class of self-organizing distributed algorithms is regarded here as a subclass of the self-stabilizing class of algorithms, where convergence is sub-linear in the size of the system and local perturbation of state is handled locally converging faster than the convergence from an arbitrary state. The chapter starts with a short overview of several virtual infrastructures and fitting self-stabilizing and self-organizing techniques:

The last design, which is based on expanders and short random walks, is described in detail.

The research areas of mobile robotic sensors lie in the intersection of two major fields of investigations carried out by quite distinct communities of researchers: autonomous robots and mobile sensor networks. Robotic sensors are micro-robots capable of locomotion and sensing. Like the sensors in wireless sensor networks, they are myopic: their sensing range is limited. Unlike the sensors in wireless sensor networks, robotic sensors are silent: they have no direct communication capabilities. This means that synchronization, interaction, and communication of information among the robotic sensors can be achieved solely by means of their sensing capability, usually called vision. In this chapter, we review the results of the investigations on the computability and complexity aspects of systems formed by these myopic and silent mobile sensors.

The concept of security for tiny artifacts has been studied in a wide range of aspects, from authentication through data integrity to intrusion detection. This chapter provides a broad overview of some of the techniques developed for constrained devices where computational power, memory capacity, and energy limitations enforce slightly different approaches to these problems, when compared to standard high-end devices. In the following, we present ideas that leverage unique properties of sensor networks (also wireless sensor networks) to provide consistent and secure systems for information gathering and sensing.

Secure communications in wireless ad hoc networks require setting up end-to-end secret keys for communicating node pairs. It is widely believed that although being more complex, a probabilistic key predistribution scheme is much more resilient against node capture than a deterministic one in lightweight wireless ad hoc networks. Supported by the surprisingly large successful attack probabilities (SAPs) computed in this chapter, we show that the probabilistic approaches have only limited performance advantages over deterministic ones. We first consider a static network scenario as originally considered in the seminal paper by Eschenauer and Gligor [9], where any node capture happens after the establishment of all pairwise links. In this scenario, we show that the deterministic approach can achieve a performance as good as the probabilistic one. In a mobile network scenario, however, the probabilistic key management as described in [9] can lead to a SAP of one order of magnitude larger than the one in a static network due to node fabrication attacks.

The above analysis motivates us to propose two low-cost secure-architecture-based techniques to improve the security against such attacks. Our new architectures, specifically targeted at the sensor-node platform, protect long-term keys using a root of trust embedded in the hardware System-on-a-Chip (SoC). This prevents an adversary from extracting these protected long-term keys from a captured node to fabricate new nodes. The extensive simulation results show that the proposed architecture can significantly decrease the SAP and increase the security level of key management for mobile ad hoc networks.

Finally, we develop an analytical framework for the on-demand key establishment approach. We propose a novel security metric, the REM resilience vector, to quantify the resilience of any key establishment schemes against Revealing, Erasure, and Modification (REM) attacks. Our analysis shows that previous key establishment schemes are vulnerable under REM attacks. Relying on the new security metric, we prove a universal bound on achievable REM resilience vectors for any on-demand key establishment scheme. This bound that characterizes the optimal security performance analytically is shown to be tight, as we propose a REM-resilient key establishment scheme which achieves any vector within this bound. In addition, we develop a class of low-complexity key establishment schemes which achieve nearly optimal REM attack resilience.

Wireless networks are more vulnerable to security threats than wired networks. Since sensors are resource constrained, the use of traditional cryptographic key management techniques is not practical. Hence keys are distributed in sensor nodes prior to their deployment. This method, called key predistribution, was investigated recently in a number of studies. This chapter restricts the discussion to single-hop networks, where any two sensors are within communication range of each other. The goal is to enable any two sensor nodes to exchange information using their common key, so that other sensors, or an adversary, are unable to decode the message. If two sensor nodes do not share a common key then a path between them, via other sensor nodes, is established, with sensors on the path being able to decode a message and forward it encrypted with a new key. We describe different types of key predistribution schemes for single-hop networks and discuss their merits and demerits in terms of resiliency (impact of node compromises), scalability, connectivity, and memory, computation, and communication resources. Shared-key discovery process should minimize the use of communication bandwidth. We also discuss the identification of compromised nodes and revocation techniques.

Military surveillance, home health care or assisted living, and environmental science are three major application areas for wireless sensor networks. Revolutionary changes are possible in these application areas by using wireless sensor networks. To show the breadth and advantages of this technology, design and implementation details are presented for three systems, one in each of these three application domains. Key research challenges and the approaches taken to address them are highlighted. Challenges requiring significantly improved solutions are also identified. These systems and others like them provide significant evidence for the utility of wireless sensor networks.

Owing to the large scale of networked sensor systems, ease of programming remains a hurdle in their wide acceptance. High-level application development techniques, or macroprogramming provides an easy-to-use high-level representation to the application developer, who can focus on specifying the behavior of the system, as opposed to the constituent nodes of the wireless sensor network (WSN). This chapter provides an overview of the current approaches to high-level application design for WSNs, going into the details related to data-driven macroprogramming. Details of one such language are provided, in addition to the approach taken to the compilation of data-driven macroprograms to node-level code. An implementation of the modular compilation framework is also discussed, as well as a graphical toolkit built around it that supports data-driven macroprogramming. Through experiments, it is shown that the code generated by the compiler matches hand-generated implementations of the applications, while drastically reducing the time and effort involved in developing real-world WSN applications.