Catálogo de publicaciones - libros

Networks of small sensor nodes, so-called sensor networks, allow to monitor and analyze complex phenomena over a large region and for a long period of time. Recent advances in sensor network research allow for small and cheap sensor nodes which can obtain a lot of data about physical values, e.g. temperature, humidity, lightning condition, pressure, noise level, carbon dioxide level, oxygen level, soil makeup, soil moisture, magnetic field, current characteristics of objects such as speed, direction, and size, the presence or absence of certain kinds of objects, and all kinds of values about machinery, e.g. mechanical stress level or movement. This huge choice of options allow to use sensor network applications in a number of scenarios, e.g. habitat and environment monitoring, health care, military surveillance, industrial machinery surveillance, home automation, als well as smart and interactive places. The application of a sensor network usually determines the design of the sensor nodes and the design of the network itself. No general architecture for sensor networks exists at the moment. This chapter gives an overview of existing sensor network applications, shows some currently available sensor network hardware platforms and gives an outlook on upcoming applications for sensor networks.

This chapter introduces four major aspects of modeling ad hoc and sensor networks: distributed algorithms, communication, energy, and mobility. Commonly used formal models will be introduced as basis for the design and evaluation of algorithms solving problems in this domain. We assume basic knowledge about graph theory and algorithms.

In the introduction the terms ad hoc and sensor networks are defined and the OSI layer model is introduced, which provides several levels of abstraction for systems dealing with communication. Algorithms in the context of sensor networks are usually distributed, and thus basic concepts of the theory of distributed systems are summarized in Section 2.2. A big difference to classical distributed systems comes into play through radio communication: the problem of modeling the communication topology, which is assumed to be given in the classical theory of distributed systems, is discussed in Section 2.3. It is even possible that the communication network may change with time. Especially for sensor networks energy is the crucial resource, which is the topic of Section 2.4. Finally, in Section 2.5 mobility models are outlined, and we conclude with Section 2.6 giving references to the sources that have been used in this chapter and pointers for further reading.

Wireless ad hoc and sensor networks consist of autonomous devices communicating via radio. There is no central server or stationary infrastructure which could be used for organizing the network. Hence, the coordination necessary for efficient communication has to be carried out by the nodes themselves. That is, the nodes have to build up a communication service by applying a distributed algorithm.

The is part of the (layer 2 of the OSI model) and sits directly on top of the Physical Layer (layer 1). Its purpose is to manage access to the shared wireless medium. If transmissions from two different nodes arrive simultaneously at a receiver, neither of them is received due to interference.

In this section we start by describing the problem in more detail and give a short and necessarily incomplete overview of some of the approaches that are widely used by the network community, such as CSMA, CSMA/CA, and TDMA (see [249] for a more detailed survey). Later on, we will introduce some other approaches for managing concurrent transmissions, namely scheduling, frequency assignment and coloring approaches. We will conclude the introductory section by introducing several variants of coloring problems and try to argument why coloring problems are an important and useful subject to study in order to understand and solve MAC layer issues. In Section 4.2 we present an overview of some distributed coloring algorithms. We start with simple heuristics and try to gradually develop more and more sophisticated methods. We then describe two completely different approaches to efficiently solve coloring problems in a nearly optimal fashion.While the second approach is based on a non-constructive combinatorial proof, the first one, called deterministic coin tossing, can lend itself to practical solutions to the coloring problem.

Information between two nodes in a network is sent based on the network topology, the structure of links connecting pairs of nodes of a network. The task of topology control is to choose a connecting subset from all possible links such that the overall network performance is good. For instance, a goal of topology control is to reduce the number of links to make routing on the topology faster and easier.

In a wireless network, a signal sent from one node to another suffers from physical effects. It will be attenuated, where the amount of loss depends on the physical medium it passes through, the distance it travels, and many other influences. The signal cannot be decoded the signal if it is too weak at the receiver. So in order to reach a certain receiver, the sender has to make sure it sends the signal with sufficient power, such that it is still after the attenuation on its path to the receiver. More details on these concepts are given in Section 2.3 or any decent book on communications engineering, e.g., [336].

This book presents efficient algorithms for a large amount of important problems in ad hoc and sensor networks. Consider a problem and the most efficient algorithm (known so far) solving it with running time (()), where is the number of nodes in the network. (()) is called on the running time for . After the problem is solved, the next step is to ask: Can the problem be solved more efficiently? Is the running time of the algorithm ?

If somebody devises a faster algorithm for , then the answers to both questions are obvious. However, it can also happen that no faster algorithm is suggested for some time. Then the only way to answer these questions is to establish a (()) on the running time of the algorithms for the problem . This task is by no means trivial, as it involves showing that even algorithms which have not been invented yet cannot be faster than (()).

The facility location problem has occupied a central place in operations research since the early 1960’s, as it models design decisions on the placement of factories, warehouses, schools, or hospitals to serve a set of customers efficiently. For an overview of previous work see the survey chapter by Cornuejols, Nemhauser & Wolsey in [289]. Recently, it has received renewed research interest because it can be used to place servers or proxies in communication networks [380].

We apply the facility location problem to configuration and deployment issues in wireless sensor networks.More specifically, we discuss how algorithms for the facility location problem can be used to assign functionality to certain nodes in a wireless sensor network, i.e., choose a subset of designated nodes as of a particular service.

The one type of routing in ad hoc and sensor networks that currently appears to be most amenable to algorithmic analysis is geographic routing. This chapter contains an introduction to the problem field of geographic routing, presents a specific routing algorithm based on a synthesis of the greedy forwarding and face routing approaches, and provides an algorithmic analysis of the presented algorithm from both a worst-case and an average-case perspective.

In a distributed network, the delivery of messages between its nodes is a basic task, and a mechanism is required that is able to deliver packages of data from any node of the network to any other node. To this end, usually a distributed algorithm runs on every node of the network, which properly forwards incoming packages, employing some information that is stored in the local memory of the node.