Energy-Aware Broadcasting and Multicasting in Wireless Ad Hoc Networks

Energy-Aware Networking: In many military networking applications, battery energy is a precious resource that must be carefully managed. Whereas most energy-related studies have concentrated on improved batteries and low-power electronics, we have approached this problem from the novel perspective of networking techniques. Our primary focus is on an "energy-constrained" mode of operation, under which each node is equipped with batteries that cannot be recharged or replaced. Therefore, nodes whose batteries are depleted are removed, and the network may no longer fulfill its objectives. To address the specific problem of energy-aware tree construction for broadcast (one-to-all) and multicast (one-to-many) communication, we have developed the Broadcast Incremental Power (BIP) and Multicast Incremental Power (MIP) algorithms.1

Ad Hoc Wireless Networks Are Different: The wireless ad hoc networking environment presents formidable challenges. For example, unlike cellular networks (which have fixed base stations), ad hoc networks have no infrastructure; they do not even have pre-defined links. By increasing RF transmitter power, one can increase communication range; however, this causes increased energy expenditure and interference.

We first assume the use of omnidirectional antennas; thus all nodes within communication range of a transmitting node can receive its transmission. Consider the example shown in Fig. 1, in which a subset of the multicast tree involves Node i, which is transmitting to its neighbors, Node j and Node k. A single transmission at power P_i,(j,k) = max {P_ij, P_ik} is sufficient to reach both of them. We exploit this property, which we refer to as the "wireless multicast advantage," in our BIP algorithm.

FIGURE 1
The "Wireless multicast advantage" associated with omnidirectional antennas: P_i,(j,k) = max{P_ij,P_ik}. The two destinations can both be reached using the maximum value of power required to reach either of them individually. This situation is quite different from that of wired networks, in which the cost to reach two neighbors is generally the sum of the costs to reach them individually.

Wired networks are typically designed using a layered protocol stack, in which the functions at each layer (physical, data link, network, etc.) are designed independently. However, a "cross-layer" approach is more appropriate for ad hoc wireless networks. Specifically, our algorithms jointly choose transmission power (which can be different at each node) and tree structure.

The Broadcast Incremental Power (BIP) Algorithm: We assume that the locations of the nodes are known, and that the power required to support communication between two nodes is equal to r^α, where r is the distance between them and 2 ≤ α ≤ 4. We further assume that RF power is continuously variable and under network control. Our goal is the construction of a minimum-energy broadcast tree, rooted at the source node. Since this is an NP-complete problem, heuristics are needed.

Under our BIP algorithm,1 the first in the literature to address this problem, nodes are added to the tree, one at a time. The node that is added at each step is the one that requires the minimum value of incremental power. Let us say that Node i is already transmitting at power level P(i), which is not sufficient to reach Node j. Then the incremental power to reach Node j is C_ij = P_ij - P(i), where P_ij = r_ij^α is the total power required to reach Node j. Figure 2 shows the first three steps and final tree structure generated by BIP, where Node 10 is the source node. BIP is easily adapted to multicast operation by pruning the branches of the tree that do not lead to desired destinations, resulting in the Multicast Incremental Power (MIP) algorithm.

FIGURE 2
Example of free construction using PIB (first three steps and final tree); α = 2. At each step of the algorithm, one node is added to the tree, i.e., the node that can be added using the least value of incremental power.

Extension of Network Life in Energy-Limited Operation: In situations where energy at the nodes is not renewable (e.g., sensors or individual warriors that cannot replace their batteries), it is helpful to use a cost function that incorporates the residual energy at each node.2 Specifically, the incremental cost of Node i transmitting to Node j is defined to be

where E_i(0) is the initial value of energy at Node i, and E_i(t) is the residual energy at time t. By setting β > 0, use of nodes with little residual energy is discouraged, and load balancing is thereby achieved. Figure 3 shows that by setting β = 1, the death of the first node is delayed considerably, thereby extending the network's useful life.

FIGURE 3
Evolution of number of live nodes under MIP for 50-node network. Setting the energy-aware parameter β = 1 discourages the use of energy-starved nodes, thereby providing load balancing and delaying the death of the first node considerably.

Further Enhancement Using Directional Antennas: The use of directional antennas can provide energy savings and interference reduction by concentrating RF energy where it is needed. We assume that each node's beamwidth θ can be chosen, such that θ_min ≤ θ ≤ 360. We have considered two basic approaches for broadcasting and multicasting with directional antennas,3 which are described in Fig. 4. This figure shows the evolution of cumulative delivered traffic volume under MIP for the two schemes, for several values of θ_min. In all cases, traffic is delivered at a constant rate until the network dies; this is a consequence of setting β = 1. As θ_min is reduced, both the network lifetime and traffic volume increase, and D-MIP shows a greater performance advantage over RB-MIP.

FIGURE 4
Traffic volume vs time for D-MIP and RB-MIP for several values of θ (β = 1). The use of directional antennas provides significant increase in network lifetime and delivered traffic volume. This improved performance is especially apparent for D-BIP and D-MIP, which exploit the properties of directional antennas as the tree is constructed.

Summary: Our seminal research introduced the problem of energy-aware tree construction for broadcasting and multicasting to the research community. It has stimulated research by many others. We have shown that novel networking techniques, based on cross-layer design, can improve network performance and extend network lifetime. We have also developed distributed versions of our algorithms. Future military ad hoc and sensor networks will benefit from these approaches to support Navy/Marine Corps operations.

[Sponsored by ONR]