Overview

Information routing in wireless sensor networks can be made robust and energy-efficient by taking into account a number of pieces of state information available locally within the network.

1. Link quality: As we discussed in Chapter 5, link quality metrics (e.g. packet reception rates) obtained through periodic monitoring are very useful in making routing decisions.

2. Link distance: Particularly in case of highly dynamic rapidly fading environments, if link monitoring incurs too high an overhead, link distances can be useful indicators of link quality and energy consumption.

3. Residual energy: In order to extend network lifetimes it may be desirable to avoid routing through nodes with low residual energy.

4. Location information: If relative or absolute location information is available, geographic routing techniques may be used to minimize routing overhead.

5. Mobility information: Recorded information about the nearest static sensor node near a mobile node is also useful for routing.

We examine in this chapter several routing techniques that utilize such information to provide energy efficiency and robustness.

Metric-based approaches

Robustness can be provided by selecting routes that minimize end-to-end retransmissions or failure probabilities. This requires the selection of a suitable metric for each link.

The ETX metric

If all wireless links are considered to be ideal error-free links, then routing data through the network along shortest hop–count paths may be appropriate. However, the use of shortest hop–count paths would require the distances of the component links to be high.

Overview

An essential characteristic of wireless communication is that it provides an inherently shared medium. All medium-access control (MAC) protocols for wireless networks manage the usage of the radio interface to ensure efficient utilization of the shared bandwidth. MAC protocols designed for wireless sensor networks have an additional goal of managing radio activity to conserve energy. Thus, while traditional MAC protocols must balance throughput, delay, and fairness concerns, WSN MAC protocols place an emphasis on energy efficiency as well.

We shall discuss in this chapter a number of contention-based as well as schedule-based MAC protocols that have been proposed for WSN. A common theme through all these protocols is putting radios to a low-power “sleep mode” either periodically or whenever possible when a node is neither receiving nor transmitting.

Traditional MAC protocols

We begin with a focus on contention-based MAC protocols. Contention-based MAC protocols have an advantage over contention-free scheduled MAC protocols in low data rate scenarios, where they offer lower latency characteristics and better adaptation to rapid traffic variations.

Aloha and CSMA

The simplest forms of medium-access are unslotted Aloha and slotted Aloha. In unslotted Aloha, each node behaves independently and simply transmits a packet whenever it arrives; if a collision occurs, the packet is retransmitted after a random waiting period. The slotted version of Aloha works in a similar manner, but allows transmissions only in specified synchronized slots. Another classic MAC protocol is the carrier sense medium-access (CSMA) protocol.

Overview

Wireless sensor networks are fundamentally intended to provide information about the spatio-temporal characteristics of the observed physical world. Each individual sensor observation can be characterized essentially as a tuple of the form <S,T,M>, where S is the spatial location of the measurement, T the time of the measurement, and M the measurement itself. We shall address the following fundamental question in this chapter: How can the spatial location of nodes be determined?

The location information of nodes in the network is fundamental for a number of reasons:

1. To provide location stamps for individual sensor measurements that are being gathered.

2. To locate and track point objects in the environment.

3. To monitor the spatial evolution of a diffuse phenomenon over time, such as an expanding chemical plume. For instance, this information is necessary for in-network processing algorithms that determine and track the changing boundaries of such a phenomenon.

4. To determine the quality of coverage. If node locations are known, the network can keep track of the extent of spatial coverage provided by active sensors at any time.

5. To achieve load balancing in topology control mechanisms. If nodes are densely deployed, geographic information of nodes can be used to selectively shut down some percentage of nodes in each geographic area to conserve energy, and rotate these over time to achieve load balancing.

Overview

As we discussed in Chapter 2, the core functionality of a wireless sensor network depends on having a network topology that satisfies two important objectives: connectivity and coverage. Connectivity is essential to be able to move movement data between different points within the network, while coverage of the environment ensures that critical phenomena and events can be detected and monitored.

The problem of constructing an initial topology is of course the problem of node deployment. Beyond this, there are many scenarios in which topology control is desired. In its broadest sense, topology control can be defined as the process of configuring or reconfiguring a network's topology through tunable parameters after deployment. There are three major tunable parameters for topology control:

1. Node mobility: In WSNs consisting of mobile nodes, such as robotic sensor networks, both coverage and connectivity can be adapted by moving the nodes accordingly. We discussed the work that has been done on mobile node deployments and related topology configuration approaches in Chapter 2.

2. Transmission power control: In WSNs with static nodes, if the deployment density is already sufficient to guarantee the required level of coverage, the connectivity properties of the network can be adjusted by tuning the transmission power of the constituent nodes. We discussed these kinds of power control-based topology configuration techniques in Chapter 2 as well.

With its origins in the early nineties, the subject of wireless sensor networks has seen an explosive growth in interest in both academia and industry. In just the past five years several hundred papers have been written on the subject. I have written this book because I believe there is an urgent need to make this vast literature more readily accessible to students, researchers, and design engineers.

The book aims to provide the reader with a comprehensive, organized survey of the many protocols and fundamental design concepts developed for wireless sensor networks in recent years. The topics covered are wide-ranging: deployment, localization, synchronization, wireless link characteristics, medium-access, sleep scheduling and topology control, routing, data-centric concepts, and congestion control.

This book has its origins in notes, lectures, and discussions from a graduate course on wireless sensor networks that I've taught thrice at the University of Southern California in the past two years. This text will be of interest to senior undergraduate and graduate students in electrical engineering, computer science, and related engineering disciplines, as well as researchers and practitioners in academia and industry.

To keep the book focused coherently on networking issues, I have had to limit in-depth treatment of some topics.

Overview

Given the need to coordinate the communication, computation, sensing, and actuation of distributed nodes, and the spatio-temporal nature of the monitored phenomena, it is no surprise that an accurate and consistent sense of time is essential in sensor networks. In this chapter, we shall discuss the many motivations for time synchronization, the challenges involved, as well as some of the solutions that have been proposed.

Distributed wireless sensor networks need time synchronization for a number of good reasons, some of which are described below:

1. For time-stamping measurements: Even the simplest data collection applications of sensor networks often require that sensor readings from different sensor nodes be provided with time stamps in addition to location information. This is particularly true whenever there may be a significant and unpredictable delay between when the measurement is taken at each source and when it is delivered to the sink/base station.

2. For in-network signal processing: Time stamps are needed to determine which information from different sources can be fused/aggregated within the network. Many collaborative signal processing algorithms, such as those for tracking unknown phenomena or targets, are coherent and require consistent and accurate synchronization.

3. For localization: Time-of-flight and TDoA-based ranging techniques used in node localization require good time synchronization.

4. For cooperative communication: Some physical layer multi-node cooperative communication techniques involve multiple transmitters transmitting in-phase signals to a given receiver. Such techniques [105] have the potential to provide significant energy savings and robustness, but require tight synchronization.

Summary

Wireless sensor networks must be designed to meet a number of challenging requirements including extended lifetime in the face of energy constraints, robustness, scalability, and autonomous operation. The many design concepts and protocols described in the preceding chapters address these challenges in different aspects of network operation. While much additional work remains to be done to realize the potential of tomorrow's systems, even these partial solutions offer reason for optimism.

Perhaps the most important lesson to take away from the studies described in this book is that the fundamental challenges must be tackled by making appropriate design choices and optimizations across multiple layers.

Consider energy efficiency, which is perhaps the most fundamental concern due to limited battery resources. The most significant source of energy consumption in many applications is radio communication. At deployment time, energy efficiency concerns can inform the selection of an appropriate mixture of heterogeneous nodes and their placement. Localization and synchronization techniques can be performed with low communication overheads for energy efficiency. At the physical/link layers, parameters such as the choice of modulation scheme, transmit power settings, packet size, and error control techniques can provide energy savings. Medium access techniques for sensor networks use sleep modes to minimize idle radio energy consumption. Topology control techniques suitable for over-deployed networks also put redundant nodes to sleep until they are needed to provide coverage and connectivity. At the network layer, routing techniques can be designed to incorporate energy-awareness and innetwork compression to minimize energy usage.

Overview

Wireless communication is both a blessing and a curse for sensor networks. On the one hand, it is key to their flexible and low-cost deployment. On the other hand, it imposes considerable challenges because wireless communication is expensive and wireless link conditions are often harsh and vary considerably in both space and time due to multi-path propagation effects.

Wireless communications have been studied in depth for several decades and entire books are devoted to the subject [171, 207]. The goal of this chapter is by no means to survey all that is known about wireless communications. Rather, we will focus on three sets of simple models that are useful in understanding and analyzing higher-layer networking protocols for WSN:

1. Link quality model: a realistic model showing how packet reception rate varies statistically with distance. This incorporates both an RF propagation model and a radio reception model.

2. Energy model: a realistic model for energy costs of radio transmissions, receptions, and idle listening.

3. Interference model: a realistic model that incorporates the capture effect whereby packets from high-power transmitters can be successfully received even in the presence of simultaneous traffic.

Wireless link quality

The following is the basic ideal model of a wireless link: two nodes have a perfect link (with 100% packet reception rate) if they are within communication range R, and a non-existent link (0% packet reception rate) if they are outside this range.

Overview

The objective of transport layer protocols is to provide reliability and other quality of service (QoS) services and guarantees for information transfer over inherently unreliable and resource-constrained networks. The following are the interrelated guarantees and services that may be needed in wireless sensor networks:

1. Reliable delivery guarantee: For some critical data, it may be necessary to ensure that the data arrive from origin to destination without loss.

2. Priority delivery: The data generated within the WSN may be of different priorities; e.g., the data corresponding to an unusual event detection may have much higher priority than periodic background readings. If the network is congested, it is important to ensure that at least the high-priority data get through, even if the low-priority data have to be dropped or suppressed.

3. Delay guarantee: In critical applications, particularly those where the sensor data are used to initiate some form of actuation or response, the data packets generated by sensor sources may have strict requirements for delivery to the destination within a specified time.

4. Energy-efficient delivery: Energy wastage during times of network congestion must be minimized, for instance by forcing any necessary packet drops to occur as close to the source as possible.

5. Fairness: Different notions of fairness may be relevant, depending on the application. These range from ensuring that all nodes in the network provide equal amounts of data (e.g. in a simple data-gathering application), to max– min fairness, to proportional fairness.

Overview

A fundamental innovation in the area of wireless sensor networks has been the concept of data-centric networking. In a nutshell, the idea is this: routing, storage, and querying techniques for sensor networks can all be made more efficient if communication is based directly on application-specific data content instead of the traditional IP-style addressing [74].

Consider the World Wide Web. When one searches for information on a popular search site, it is possible to enter a query directly for the content of interest, find a hit, and then click to view that content. While this process is quite fast, it does involve several levels of indirection and names: ranging from high-level names, like the query string itself, to domain names, to IP (internet protocol) addresses, and MAC addresses. The routing mechanism that supports the whole search process is based on the hierarchical IP addressing scheme, and does not directly take into account the content that is being requested. This is advantageous because the IP is designed to support a huge range of applications, not just web searching. This comes with increased indirection overhead in the form of the communication and processing necessary for binding; for instance the search engine must go through the index to return web page location names as the response to the query string, and the domain names must be translated to IP addresses through DNS. This tradeoff is still quite acceptable, since the Internet is not resource constrained.

Wireless sensor networks, however, are qualitatively different.

There are large gaps between theory, simulations, laboratory experiments, field experiments, and field deployments, essentially related to the acceptable degree of human intervention permitted to change the system, i.e., getting things to work. A research program typically loops through these stages as experimental results suggest new directions for theory. The basic assumption of this chapter is that since ENS are fundamentally about connecting the physical world to large scale networks, therefore physical experiments must be performed to verify their proper operation. It is necessary to make simplifying assumptions in early design stages, but no system that is designed to interact with the real world can really be trusted without a set of real deployments that test these assumptions. This chapter describes the basic design stages of the development of experimental systems from the formulation of objectives and assembly of the design and application team through deployment. Throughout, a robotic NIMS is used as an example (see Chapter 12 for background).

Deciding on priorities

The most important decision in the whole process is the set of priorities. What particular problems will the system solve? Can slightly different problems be addressed at much less cost and effort? Who will need to be consulted or be on the design team to help determine the problem formulation? The notion of an experiment most of us carry around is based on the formal high school/university laboratory report with objectives, theory, method, results, analysis, and conclusion.

This chapter treats two related topics: detection and estimation of multiple sources, and the sharing of a communication medium among multiple users. In the former, knowledge of the statistical properties of the sources together with control of the layout of sensors can be used to achieve a degree of source separation. These techniques can also be applied in multiple access communications, but in addition the communicators can cooperate in terms of channel assignments and modulation type to make the task much easier. The chapter begins with a general discussion of interference models and mitigation methods before describing some source separation techniques. Then multiplexing methods for communications systems are discussed, before presentation of the effects of the available communication infrastructure and network topology on the choices of multiple access schemes. Adaptive power control is revisited from the point of view of its effect on the capacity of multiple access schemes.

Interference models

Interference is an unwanted signal sharing a channel being monitored, whether for sensing purposes or for communications. In contrast with thermal noise which is added in the receiver, interference is generally time-varying, e.g., another source or communicator. Moreover, it is confined to a particular band of frequencies, unlike Gaussian noise which is modeled as being uniform over the whole range of communication frequencies. If the interference is deliberate, it is termed jamming. In the design of systems that are potentially subject to jamming, the jamming is assumed to be of the worst possible form, i.e., energy is concentrated in such a way as to maximize error probability

Conventional computing platforms include not just processors, memory, storage peripherals, and other peripherals associated with data processing, but also many interfaces (such as sound, imager, and mechanical input sensor systems) that have characteristics similar to systems specifically designed to interact with the physical world. An understanding of the architectures of such platforms is thus a good place to begin, in particular as many of the hardware and software design abstractions may usefully be applied to ENS nodes, just as many networking techniques and abstractions for general purpose computers apply to ENS. However, ENS applied to sensing applications requires architectural solutions that differ dramatically in several respects. For example, ENS platforms may be isolated from human users, may operate at low duty cycles, with deterministic schedules, and may be tolerant to a high communication error rate and long latency. At the same time, ENS may also be required to operate autonomously and unattended for extended periods on minimal battery energy. This is in marked contrast to embedded computing platforms of the past that directly support human users (e.g., cellular telephony platforms or handheld computing systems). For these applications, operations may not conform to deterministic schedules, operating lifetimes may be short, and administration by users is available. Of course, this example of low-duty-cycle operation represents merely one instance and others require widely varying ENS operating requirements; e.g., an image sensor may require a high sensor data rate and a high communication data rate.