Source detection, localization, and identification begin with the realization that the sources are by their nature probabilistic. The source, the coupling of source to medium, the medium itself, and the noise processes are each variable to some degree. Indeed, it is this very randomness that presents the fundamental barrier to rapid and accurate estimation of signals. Consequently, applied probability is essential to the study of communications and other detection and estimation problems. This chapter is concerned with the description of signals as random processes, how signals are transformed from continuous (real-world) signals into discrete representations, and the fundamental limits on the loss of information that result from such transformations. Three broad topics will be touched upon: basic probability theory, representation of stochastic processes, and information theory.

Probability

Discrete random variables

A discrete random variable (RV) X takes on values in a finite set X = {x1, x2, … xm}. The probability of any instance x being xi, written P(x = xi), is pi. Any probability distribution must satisfy the following axioms:

1. P(xi) ≥ 0.

2. The probability of an event which is certain is 1.

3. If xi and xj are mutually exclusive events, then P(xi + xj) = P(xi) + P(xj).

That is, probabilities are always positive, the maximum probability is 1, and probabilities are additive if one event excludes the occurrence of another. Throughout the book, a random variable is denoted by a capital letter, while any given sample of the distribution is denoted by a lower-case letter.

This brief chapter summarizes a number of the design themes that are threaded through the book, expanding upon the design heuristics introduced in Chapter 1. The section headings denote the basic principles.

The physical world may not be abstracted away

While philosophers have doubted the existence of an objective reality, engineers will not get very far in the development of embedded systems without at least modeling the physical world as such. The purpose of an embedded system is to gather some information about the physical world and then take some action, if only to report that information to some other entity. As such an understanding of the physical process being monitored or controlled is essential. Chapter 2 provided some of the mathematical tools used in modeling such processes, while Chapter 3 discussed some of the basic propagation laws for natural and man-made signals.

There are fundamental limits to how well it is possible to observe phenomena with a given set of sensors, due to the presence of noise, obstructions, and propagation losses. There are similarly fundamental limits on communications capacity, while for any real apparatus computational, storage, and energy resources are also limited. System design must respect these limits and explore how resources can best be added to meet performance requirements while living within cost constraints. There are occasions when questions such as “what would happen if resource x were free?” are appropriate (e.g., in imagining some limiting case as a useful approximation) and others where they are not (e.g. when it comes to implementing the practical system).

Introduction

Continuing advances in integrated circuit technology have enabled the integration of computation and communication capabilities into devices which monitor or control physical processes. Digital controllers and sensors are found in automobiles, home appliances, factories, aircraft, cellular telephones, video games, and environmental monitoring systems. Indeed, the vast majority of processors now being manufactured are used in embedded applications (i.e., having connection to physical processes) rather than in what would ordinarily be thought of as a computer. Many are networked within the confines of a local control system, typically in master/slave configurations. However, advances in wireless technology and in the understanding of distributed systems are now making possible far more elaborate compositions of embedded systems that may function as the connection of the Internet to the physical world. Embedded network systems (ENS) are poised to become pervasive in the environment with the potential for far-reaching societal changes that have hitherto been the subject of science fiction. It is the purpose of this book to lay out the foundations of this technology, the emerging design principles and applications, and some of the interesting societal questions raised by ENS. This chapter provides some examples of ENS, discusses relevant technological trends, explores some implications of scaling to very large numbers of ENS nodes, and places the technology in a historical context.

This chapter provides a brief introduction to database design principles before describing how the problems of data management in ENS differ from conventional applications. In particular, the fact of dealing with the potentially infinite data generated by the physical world as compared with the limited queries for information or action posed by the end-users needs to be reconciled. The data management strategy also has a large impact on the energy budget, to the point that it is difficult to fully separate signal processing, database, and networking problems in large-scale networks. The chapter concludes with consideration of higher-level reasoning on the data, using the theories of logic and language.

Database design principles

Relational databases

A database may be defined as a set of persistent data to be used by applications, where persistence implies the data can be deleted only by explicit command. The data describe some entity, which may be a physical object, collection of objects, or a set of relationships among objects. The entity is characterized by properties such as location, size, number, priorities, and so forth, which are recorded within the database. In a relational database, the data are represented as rows in tables that may be directly interpreted as true propositions, while the operators work on the rows of the tables to produce new tables that are also collections of true propositions. Consider, e.g., Table 11.1, which consists of a series of true propositions from the children's book Green Eggs and Ham by Dr. Seuss.

Embedded network systems (ENS) provide a set of technologies that can link the physical world to large scale networks for such purposes as monitoring of borders, infrastructure, health, the environment, automated production, supply chains, homes, and places of business. ENS nodes integrate the novel combination of signal processing, communication, sensing, and actuation technology. Their composition into large networks requires knowledge of networking and distributed software systems. Many excellent textbooks exist that treat these topics separately, and there are corresponding undergraduate and graduate courses. However, these provide both too much information on some topics and not enough on others for a course specifically devoted to ENS. The purpose of this book is to provide support for senior design courses and introductory graduate courses in ENS without the requirement for students to have expertise in all of these areas. As such it can also serve as a resource for the practicing professional in this rapidly expanding area of research and enterprise. Note what the book is not: a comprehensive and objective treatment of the latest developments in sensor networks. We do not presume to compete with the varied riches offered on the worldwide web by what is now a large and very creative group of researchers around the world. Therefore our focus is consciously on principles and methods which have proven useful to us in the course of designing multiple generations of ENS (research, commercial products, class projects), with digressions to what in our opinion are interesting topics for new investigations.

The goal of a sensor network is to answer particular questions about the physical world for the users authorized to pose such questions. Implicit in this statement are a number of factors that are common to the security of networks and others that are particularly important in sensor networks:

• secrecy – denial of access to information to unauthorized users;

• authenticity – validation of the source of messages;

• integrity – messages are not modified accidentally or maliciously;

• anonymity – information retrieved minimally reveals the identity of groups or individuals not the subject of a query;

• flexibility – a broad set of queries can be posed and this set can grow in time;

• scalability – the network can scale to large numbers of nodes and users;

• robustness – the network can resist resource-draining attacks.

The first three factors are conventionally dealt with in a security framework involving encryption, whereby private messages can be exchanged between one or more parties. However, in a sensor network context there is also the question of reliability of the information received since a malfunctioning source can potentially corrupt a great deal of information. Additionally, nodes placed in the open may have less physical security than is typical with computers, increasing the possibility of secret keys used in encryption being revealed. Dealing with this is closely connected with the question of calibration of sensors and trust relationships between different entities.

This chapter presents basic methods of detection and estimation theory, and applies them to the problem of the detection and identification of sources. Classical statistical methods are emphasized, with the problem being cast as a probabilistic and hierarchical matching of resources to the difficulty of the estimation and detection tasks. The basic approach is one of using the least resources by taking maximum advantage of domain knowledge.

Introduction to detection and estimation theory

Many problems in signal processing and communications consist of the detection of a signal in the presence of noise, or the identification of the category to which the signal belongs. Inherent in the latter type of problem is estimation of a number of parameters of the signal which form the basis of some hypothesis space. In detection problems, there are two hypotheses:

1. H0: desired signal absent;

2. H1: desired signal present.

In identification problems, there are generally a larger number of hypotheses among the various identification classes, including the possibility that no signal in a desired class is present.

In estimation problems by contrast the objective is to estimate some parameter set of the signal, e.g., the phase of a carrier wave in noise, or the sampled impulse response of a channel.

For all of these problems, from the observed random process Z(t) a sequence of decision variables Z0, Z1, …, ZN− 1 is extracted. For detection and identification problems, using this sequence, one of M hypotheses H0, …, HM− 1 is decided upon.

Optimization problems arise in many different applications. They include the following elements:

• a mathematical model that describes the problem of interest over some set of variables. This may be discrete or continuous;

• a cost or revenue function of these variables that must be optimized according to some measure or norm;

• a set of constraints on the variables that defines their allowed range.

For example, the problem might be to determine the position of a source observed by several sensors. The model may include a stochastic description of the sources, noise, and propagation conditions. The optimization may be cast as a least squares problem, in which the expected variance of the position estimate is minimized. The constraints may include involvement of some maximum number of sensors or some maximum number of bits exchanged among the sensor nodes to conserve energy.

Optimization is a very broad and deep subject. In this appendix, a brief exposition of the basic tools of numerical analysis is presented, followed by a characterization of some classes of optimization problems and an outline of some classic approaches.

Basic tools of numerical analysis

A basic fact of numerical methods is that linear problems are much easier to solve than non-linear ones. Consider, e.g., the problem of finding the roots (zeros) of the equation f(x) = 0. Now if the function were a line one could readily compute the point of intersection with the x-axis. Otherwise, the problem is typically approached by linearizing it and proceeding in a sequence of iterations.

In this chapter, various classes of networks are considered, with particular emphasis on networks in which the energy of the nodes making up the network is constrained. Networking is classically treated as an abstraction that sits on top of the MAC layer, being concerned with issues such as the quality of service experienced by a message as it traverses some route or set of routes through a network. Quality of service issues include delay and the error rate. Packets that go through the network and fail to meet delay constraints due to congestion of particular links or that fail to meet error rate requirements due to noise, interference, or fading are dropped. Quality of service requirements come from higher levels, such as the application, with end to end (sender to recipient) guarantees of message integrity also provided by these upper layers in the form of ARQ protocols. Here the focus will be on the formation of the network, the establishment of routes between sender–recipient pairs, how delay arises in networks and how it can be mitigated, network layer interactions for sensor networks, and information theoretic limits on network performance.

Network topology

Various network topologies are illustrated in Figure 8.1. In a star network, all information flows to and from a single hub which usually acts as the master for determination of synchronization and channel access, with the remaining nodes denoted as slaves.

The fundamental characteristics of sensor systems provide some of the most important features that distinguish embedded networked sensors from other computing platforms. It is the nature of sensor systems that defines the information acquisition performance of ENS devices, the required spatiotemporal distribution of sensors, and architectural requirements including energy dissipation.

This chapter describes the fundamental principles of sensor technology that are required by the ENS designer. This includes first the architecture of ideal sensors. Then, the characteristics of non-ideal sensors and definitions for sensor figures of merit are provided. These figures of merit are critical in enabling a comparison of sensor performance and for the design of ENS systems. Then, the properties of sensors are illustrated through discussion of environmental sensors, chemical (gas-phase) sensors, and finally electromechanical sensor systems. This also includes discussion on the topics of transducer scaling to small size and sources of sensor system noise.

It is not possible in this introductory treatment to describe all possible types of sensors. The aim is to provide some intuition on microsensor properties and operation to enable selection of microsensors for signal monitoring and control. From a knowledge of measurement methods with their advantages and limitations, the goal of this chapter is to provide the designer with the set of considerations for selecting sensor systems for interfacing the mechanical, electromagnetic, and chemical environment to low-cost data acquisition, processing, and control systems.

It is trite to observe that technology can be used for good or ill. However, technology is rarely neutral in promoting one or the other. Particularly for information technology, the values that inform its design can have profound consequences for how it is used and thus for the societies that come to rely upon it. This chapter explores the ethical, legal, and social implications (ELSIs) of ENS. Section 16.1 gives background information on the government and regulation of technology. Section 16.2 discusses, in particular, how computer networks are regulated, with examples concerning intellectual property, security, and privacy. Section 16.3 discusses how ENS raise the regulatory stakes through the more intimate connection of computer networks to the physical world. A number of dystopian and utopian futures are presented, and one possible path towards selection of the latter suggested.

Technology and society

Ethics

Ethics relate to the question of right versus wrong, and the numerous shadings in between when confronted with multiple options. Sometimes the issues can be very clear, e.g., cost cutting a safety device to the point that the public is endangered is obviously wrong. Usually the choices are not so clear. It is often difficult to predict what the consequences of a particular decision or set of decisions will be. In this case, ethics demands that a process be put in place to attempt to come to the best practicable answer given the facts and resources.

Gathering data concerning the physical world is at many levels a progressive exercise in uncertainty reduction. There is uncertainty in the signal propagation model, the calibration of the sensor, the model of the phenomenon, and in the communications process. A system that can add resources where uncertainty is greatest can potentially achieve a similar level of uncertainty reduction as a network where nodes are uniformly deployed at high density. The more varied the environment and the less certain the initial models the greater the potential benefit of mobility of sensing and communication resources. This chapter is concerned with the interaction of mobile and static nodes, with mobility of three types considered:

• articulation of elements such as directional antennas, photovoltaic panels, or sensors to gain better position;

• use of freely mobile nodes that may act to supply a static network or provide mobile communication or sensing means;

• infrastructure to support mobility, communications, and energy distribution and the implications for static or freely mobile elements.

Our scope does not include details of how mobile elements can actually be made to work in an autonomous fashion whether individually or in teams; this requires far more detail than can be provided here. Our focus is rather on how the fact of mobility in some combination of the above forms can fundamentally change the sensor network problem set.

Articulation

Articulation of a mechanical device consists of some combination of rotation and extension/retraction.

Spatio-temporal relationships for physical phenomena are critical observation features, whether for point or distributed sources. To determine the location and time of events, and how they evolve in space and time, the sensors must know their own position and the time. Many techniques for determining location in turn depend on having precise time references. Thus the two topics of localization and synchronization are closely connected. This chapter begins with an overview of techniques for determining position, assuming synchronism is available. The next section explores how synchronism can be obtained in a network, with the following section discussing how position can be determined in a network. The chapter concludes with a brief discussion of sources of error and how they can be mitigated.

Principles of location

Location, the computation of position, has historically been considered as a component of surveying or navigation. In either case, known reference points are used to compute the present position. In surveying, this allows new reference points to be constructed, enabling map-making. In navigation, the objective is to chart a course using references or a map. Both celestial and land references have been used, and more recently electronic beacons and satellites have been constructed to aid both tasks.

Triangulation

References are required for orientation (to set up the coordinate axes) and position. Traditional survey instruments establish the direction of gravity, and measure angles in azimuth (the horizontal plane), elevation, or both.