Power is one of the most critical resources in wireless ad hoc networks when the wireless nodes are powered by batteries only. In this chapter, we study how to assign each wireless node a transmission power (level) such that the resulting communication graph has certain desired properties. Recently, much progress has been made on algorithmic and probabilistic studies of various power-assignment problems. These problems come in many flavors, depending on the power-requirement function and the connectivity constraint, and minimizing the total power consumption by all wireless nodes in a network is NP-hard for most versions. We study some of the best-known approximation algorithms for minimizing the total power consumption in the network and sketch useful heuristics with practical value. Observe that a majority of the power-assignment problems use the same network setting as some problems we studied in other chapters, especially about topology control; some questions are different (although they look similar). For example, in this chapter, we study the power-assignment problem by minimizing the total power while the resulting network is connected. A similar problem is to find a broadcast tree that has the minimum total power consumption. The difference here is that the leaf nodes are not required to transmit for broadcast applications, whereas all nodes are required to transmit for a tree spanning all nodes to result in a connected network.

Introduction

In the next generation of wireless communication systems, there will be a need for the rapid deployment of independent mobile users. Significant examples include establishing survivable, efficient, dynamic communication for emergency/rescue operations, disaster relief efforts, and military networks. Such network scenarios cannot rely on centralized and organized connectivity and can be conceived as applications of mobile ad hoc networks (MANETs). A MANET is an autonomous collection of mobile users that communicate over relatively bandwidth-constrained wireless links. Because the nodes are mobile, the network topology may change rapidly and unpredictably over time. The network is decentralized; all network activity, including discovering the topology and delivering messages, must be executed by the nodes themselves; that is, routing functionality will be incorporated into mobile nodes.

In many commercial and industrial applications, we often need to monitor the environment and collect the information about the environment. In some of these applications, it would be difficult or expensive to monitor using wired sensors. If this is the case, wireless sensor networks in which sensors are connected by wireless networks are preferred. A wireless sensor network (WSN) consists of a number of sensors spread across a geographic area. Each sensor node has wireless communication capability and some level of intelligence for signal-processing and networking of data. A WSN could be deployed in wilderness areas for a sufficiently long time (e.g., years) without the need to recharge or replace the power supplies. Typical applications of WSNs include monitoring, tracking, and controlling.

Introduction

In Chapter 4, we basically studied how to assign time slots to communication links in quasi-static networks (e.g., WMNs and WSNs) such that the scheduled transmissions are interference-free and the scheduling period is minimized (thus maximizing the throughput). We assumed that there is only one spectrum used by all links in the network. In this chapter, we mainly focus on multichannel networks when there are multiple spectrums available for wireless terminals in the network. The wireless devices may have multiple wireless NICs or just a single wireless NIC. Because close by mesh routers compete for certain wireless channels, the capacity of a WMN will be increased tremendously when the single channel is extended to multiradio, multichannel, and multihop. For example, if two nodes vi and vj could communicate with each other by channel f1, and both nodes have at least one more available NIC that could operate on another channel f2, if f2 is also available for both nodes, vi and vj could use both f1 and f2 to communicate simultaneously. When such cases are applied to more wireless nodes, the throughput of the wireless network will be increased tremendously.

On the other hand, with recent fast-growing spectrum-based services and devices, the remaining spectrum available for future wireless services is being exhausted, known as the spectrum-scarcity problem.

Introduction

When designing routing protocols, it is often implicitly assumed that each participant (users or routers) will faithfully follow the prescribed protocols without any deviation–except, perhaps, for a few faulty or malicious ones. For example, in wireless ad hoc networks, it is commonly assumed that each terminal contributes its own resources to forward the data for other terminals to serve the common good and benefits from resources contributed by other terminals to route its packets in return. However, the critical observation that individual users who own these wireless devices are generally selfish, aiming to maximize their own benefit instead of contributing to the system, may severely undermine the expected performances of the wireless networks. The limitations of energy supply, memory, and computing resources of these wireless devices raise concerns about the traditional assumption about terminals' conforming to protocols. Sometimes, wireless devices owned by individual users may prefer not to participate in the routing in order to save its energy and resources. Therefore, if all users are selfish, providing incentives is a natural and common way to encourage contribution and thus maintain the robustness and availability of networking systems. The question turns to how to design the proper incentives.

Introduction

Network-wide broadcasting in MANETs provides important control and route establishment functionality for a number of unicast and multicast protocols. In this chapter, an overview is presented of the recent progress of energy-efficient broadcast and multicast in wireless ad hoc networks.

Notice that, in general, there are four basic techniques for energy-efficient communication (Jones et al., 2001).

1. The first technique is to turn off nonused transceivers to conserve energy. Then, we need to schedule, for every node, when it should sleep, when it should be idle, when it should receive, and when it should transmit such that a networking task is finished in a certain time period while simultaneously saving the energy cost.

2. The second technique is scheduling the competing nodes to avoid wasting energy because of contention. This can reduce the number of retransmissions and increase the nodes' lifetime by turning off the nonused transceivers for a period of time when they are not scheduled to transmit or receive. (This was studied in Chapter 4.)

3. The third technique is to reduce communication overhead, such as to defer transmission when the channel conditions are poor.

4. The fourth technique is to use power control to conserve energy. Each node will dynamically adjust its transmission power based on the downstream neighboring nodes to a level that is sufficient to reach the downstream neighboring node(s). This has the added advantage of reducing interference with other ongoing transmissions.

Introduction

Most of the methods developed in the literature for backbone construction try to minimize the number of cluster-heads; i.e., the number of nodes in the backbone. However, in many applications of wireless ad hoc networks, minimizing the size of the backbone is not sufficient. For example, different wireless nodes may have different costs for serving as a cluster-head because of device differences, power capacities, and information loads to be processed. Therefore, in the rest of this chapter, for succinctness of presentation, we assume that each wireless node has a generic cost (or weight). The cost may also represent the fitness or priority of each node to be a cluster-head. Lower cost means higher priority. In practice, cost could represent the power-consumption rate of this node if a backbone with small power consumption is needed; the robustness of this node if a fault-tolerant backbone is needed; or a function of its security level if a secure backbone is needed. Y. Wang et al. (2005a) studied how to construct a sparse backbone efficiently for a set of weighted wireless nodes such that the total cost of the backbone is approximately minimized and there is a cost (or hops) efficient route connecting every pair of wireless nodes via the constructed network backbone.

Introduction

Wireless multihop radio networks such as ad hoc, mesh, or sensor networks are formed of autonomous nodes communicating via radio. Wireless networks have drawn a great deal of attention in recent years because of their potential applications in various areas. For example, WMNs are being used as the last mile for extending the Internet connectivity for mobile nodes. These wireless mesh or sensor networks behave almost like wired networks because they have infrequent topology changes, limited node failures, and so on. For WMNs or WSNs, the aggregate traffic load of each routing node changes infrequently also. A unique characteristic of wireless networks is that the radio sent out by a wireless terminal will be received by all the terminals within its transmission range and also possibly cause signal interference to some terminals that are not intended receivers. In other words, the communication channels are shared by the wireless terminals. Thus, one of the major problems facing wireless networks is the reduction of capacity because of interference caused by simultaneous transmissions. Using multiple channels and multiple radios can alleviate, but not eliminate, the interference. To achieve robust and collision-free communication, there are two alternatives. One is to utilize a random-access MAC layer scheme; this was discussed in detail in Chapter 3. The other is to carefully construct a transmission schedule. One variant, link scheduling in the context of time-division multiplexing (TDM), is the subject of this chapter.

Introduction

Hundreds of protocols (Bose et al., 2001; Chlamtac and Farago, 1999; Das et al., 2000; Johnson and Maltz, 1996; Ko and Vaidya, 1997; X.-Y. Li et al., 2002a; Maltz et al., 1999; Perkins, 1997a; Ramanathan and Steenstrup, 1996; Royer and Toh, 1999; Stojmenovic and Lin, 2001; Y. Wang and Li, 2002b; Zaruba et al., 2001) that take into account the unique characteristics of wireless ad hoc networks have been developed. Among them, energy efficiency, routing, and MAC layer protocols have attracted the most attention. One of the remaining fundamental and critical issues is to have fault-tolerant network deployment without sacrificing the spectrum-reusing property. In other words, the network should support multiple disjoint paths connecting every pair of nodes. Obviously, we can increase the transmission range of all nodes to increase the fault tolerance of the network. However, increasing the transmission range will cause more signal interference (thus reducing the throughput) and increase the power consumption of every node. Because power is a scarce resource in wireless networks, it is important to save the power consumption without losing the network connectivity. The universal minimum power used by all wireless nodes such that the induced network topology is connected is called the critical power.

Introduction

Wireless multihop radio networks such as ad hoc, mesh, or sensor networks are formed of autonomous nodes communicating via radio. Wireless networks have drawn lots of attention in recent years because of their potential applications in various areas. For example, wireless mesh networks (WMNs) are being used as the last mile for extending Internet connectivity for mobile nodes. Many U.S. cities (e.g., Medford, Oregon; Chaska, Minnesota; and Gilbert, Arizona) have already deployed mesh networks. AWA, the Spanish operator of WLANs, will roll out commercial WLANs and mesh networks for voice and data services. Several companies, such as MeshDynamics, have recently announced the availability of multihop, multiradio mesh-network technology. These networks behave almost like wired networks because they have infrequent topology changes, limited node failures, and so forth. For WMNs or WSNs, the aggregate traffic load of each routing node also changes infrequently. A unique characteristic of wireless networks is that the radio sent out by a wireless terminal will be received by all the terminals within its transmission range and also possibly cause signal interference to some terminals that are not intended receivers. In other words, the communication channels are shared by the wireless terminals. Thus, one of the major problems facing wireless networks is the reduction of capacity that is due to interference caused by simultaneous transmissions. Using multiple channels and multiple radios can alleviate but not eliminate the interference. This raises the scalability issue of WMNs.

Introduction

Unlike in traditional fixed infrastructure networks, there is no centralized control over ad hoc networks, which consist of an arbitrary distribution of radios in a certain geographical area. An important requirement of wireless ad hoc networks is that they should be self-organizing; i.e., transmission ranges and data paths are dynamically restructured with changing topology. Energy conservation and network performance are probably the most critical issues in wireless ad hoc networks because wireless devices are usually powered by batteries only and have limited computing capability and memory. Recently, significant research (Grünewald et al., 2002; L. Li et al., 2001; X.-Y. Li et al., 2001, 2002b; Rajaraman, 2002; Ramanathan and Rosales-Hain, 2000; Wang et al., 2003; Wattenhofer et al., 2001) has been conducted on designing a power-efficient network topology for wireless networks. Many research results applied a computational geometry technique (specifically, geometrical spanner) to achieve power efficiency. In this chapter, we review these approximation algorithms of a power spanner for ad hoc networks.

Ad Hoc Networks: Graph Model

A WAN consists of a set V of n wireless nodes distributed in a two-dimensional plane. Each node has the same maximum transmission range of R meters; e.g., a typical IEEE 802.11g WLAN adapter has a transmission range of around 100–500 m. By a proper scaling, we assume that all nodes have the maximum transmission range equal to one unit.