Catálogo de publicaciones - libros

The first sensor network deployments mainly focused on data collection [274, 308]. Corresponding implementations [184, 161] commonly offer tree based routing, such as many-to-one and one-to-many communication patterns. Routing protocols to mention for this purpose are Directed Diffusion [194] and TAG [271]. These protocols build trees to broadcast commands from a base station to the sensor network and to collect and aggregate data along the path to the base station.

Providing people with up-to-date information has become more and more crucial over the past centuries. Right now, this is mostly done via newspapers or television. While this is no big issue in densely populated areas like cities, where a reliable infrastructure exists, it is rather challenging in other regions like deserts or jungles. Distributing daily newspapers could involve enormous cost. In order to solve this problem for a region without a highly connected infrastructure, one could imagine a digital newspaper broadcasted via wireless links between houses—in the following called stations. This process starts at one station s acting as a server. To keep operation expenses as low as possible multi-hop strategies are used. In this chapter we consider a single-hop strategy to be in particular a multi-hop strategy; in that way this solution is implicitly regarded as well. The resulting question is then how to choose the transmission range of each station. To measure the quality of such a range assignment we use the sum of the energy needed to provide it: based upon experiences and theoretical research from communications engineering (see Section 2.3), the power required by a station to correctly transmit data to another station must satisfy where (,) is the Euclidean distance between and ,  ≥ 1 is the path-loss exponent and  ≥ 1 describes properties of the used technology (including antenna characteristics, transmission quality, etc.). Fixing the range assignment induces the transmission graph: edge (,) represents the ability of to communicate with . Note that this graph is directed since the transmission ranges of and may differ. The task is to find a range assignment that keeps the sum of the energy used by all stations as low as possible while guaranteeing the ability to send messages to all other stations. We assume all stations to be embedded in the plane, i.e., the problem is 2-dimensional, and refer to [77] for a generalization of this Range Assignment Problem to -dimensional space.

In this chapter we consider sensor networks, in which all nodes periodically produce some amount of information by sensing an extended geographic area. In each round all data from all nodes needs to be transmitted to an information sink for processing. Because of limited transmission ranges of the nodes, multi-hop routing techniques are applied to transmit the data from all nodes to the sink. Since different nodes partially monitor the same spacial region, data is often correlated. In this case and in order to save energy, data can be processed on its way to the sink. This technique is referred to as in-network data aggregation. For most algorithms presented here, we will assume that the energy cost required by data aggregation is negligible compared to transmission costs, though [270] presents a network model, which incorporates data aggregation and communication costs.

A for an ad hoc or sensor network is an algorithm that on the input of a node’s returns as its output this node’s physical . A location service sits between the similar sounding concepts of or , which is treated in Chapter 15, i.e., how a node determines its own position (e.g., by using GPS or triangulation relative to other nodes), and , i.e., services that need to be aware of the client’s location (e.g., restaurant or gas station recommender systems). A similar, but different problem is the selection of the most conveniently located node.

Many applications of sensor and ad hoc networks profit from the knowledge of geographic positions of all or just some of the sensor nodes. E.g., geometric routing can use positional information to pass packets efficiently to target nodes. Tasks like measuring temperature or humidity levels of a certain area can only be fulfilled, if each sensor node knows its geographic position or at least an approximation of it. Attaching a GPS (global positioning system) to each sensor node is an undesirable solution, since GPS is quite costly and clumsy, compared to the small sensor nodes. Furthermore, the perception of GPS signals might be disturbed when there is no direct connection to the satellites due to some obstacles (buildings, trees, ...).

Security is one of the fundamental problems in wireless sensor and ad hoc networks. Properties specific to such networks make it hard to apply traditional security solutions and require the design and analysis of new security mechanisms.

Many attacks are very powerful, but either not specific to wireless sensor and ad hoc networks or of little algorithmic interest, for example eavesdropping or injection of faulty traffic, radio jamming, or tampering with the hardware. Although of independent interest, we will not consider these issues in the following, and instead delve into the problem of distributing cryptographic keys securely.

The problem of distributing symmetric or asymmetric keys has always been a nuisance in applied cryptography: Before two parties can establish a secure communication channel , they first need another secure communication channel over which they can negotiate the key required for establishing In wireless sensor and ad hoc networks, this problem turns out to have solutions that look quite different from those in more traditional settings.

We start with giving a brief overview of security issues and to the cryptographic basics that are required to understand why distribution of cryptographic keys is a necessary condition for secure communication. Then, we delve into the issue. Section 16.2 deals with the symmetric case, and Section 16.3 with the asymmetric case.

Most of the approaches for ad hoc networks assume that the nodes readily and honestly follow the protocol. Unfortunately, this assumption does not always hold in reality. Misbehaving in ad hoc networks can take place at different levels of the system architecture:

Routing algorithms in wireless networks can be developed using different techniques. In a network consisting of selfish nodes, traditional approaches will fail, since nodes are not interested in forwarding foreign data and might refuse to cooperate. In this chapter we discuss algorithmic mechanism design, which provides a possibility to deal with selfishness of network nodes.

Nodes in a network are called selfish, if they are not providing own resources to other nodes for free, which is usually bandwidth for transit data transfers. Forwarding foreign data in a wireless network means for a batterypowered node spending valuable energy, which can be considered as an expence for a node. We will call such expences . A node will provide a service when offered compensation for its costs, wich could be some kind of virtual currency. The of such a transaction to a node is the difference between the amount of compensation and the own costs of providing this service. In this chapter we will not consider malicious nodes, for example, nodes with the intent of jamming or tapping the network.

Selfish entities are called agents and are assumed to be rational and responding to incentives when asked to cooperate. For each network model and given routing problem, the aim is to design a cheating-proof mechanism, which computes outcome (the route) and payoff function in polynomial time and minimizes, if possible, the overall route cost.

Time synchronization is an essential requirement in actually any distributed system such as sensor networks. Many applications require precise clocks, e.g., for the coordination of wake-up and sleeping times, TDMA schedules, ordering of sensed events, estimation of position information, and so on. The scope of time synchronization is to estimate (i) or , (ii) the between clocks, and (iii) the between clocks.