<<

. 59
( 87 .)



>>

1. The first and simplest approach is a synchronized power-save mechanism. Nodes
periodically wake up to listen to announcements of pending traffic, and remain
awake to exchange traffic, if necessary. The restricted windows for announcing and
forwarding traffic can result in high latencies, however. Establishing the required
phase synchronization can be also problematic in a dynamic, multihop ad hoc net-
work.
2. A second approach is based on network topology. Some covering set of the network
is defined such that it is topologically representative of the network. The nodes in
the covering set provide connectivity equivalent to that of the full network, so that
the remaining nodes can spend most of their time in the sleep state with minimal
impact on network performance. Such protocols can be either synchronous or asyn-
chronous, both in determining the covering set and in traffic forwarding.
3. A third approach is intended for fully asynchronous operation, in which nodes
maintain independent and possibly even dissimilar sleep“wake schedules. The
scheduling rules are defined such that neighboring nodes™ schedules are guaranteed
to eventually overlap. Retransmission rules are defined such that a bounded number
of attempts are required to permit two nodes to establish connectivity.

3
A node whose network interface is in the idle or sleep state is referred as an idle or sleeping node, without im-
plying anything about the state of components such as the CPU. Energy-aware joint scheduling of computing,
storage, and communication subsystems is an area of active research.
306 ENERGY-EFFICIENT COMMUNICATION IN AD HOC WIRELESS NETWORKS


11.4.2 Synchronous Power-Save Protocols
In a synchronous power-save protocol, nodes periodically wake up and exchange traffic an-
nouncements and pending traffic. One difficult aspect of these protocols is determining in-
tervals and announcement windows that maximize energy savings, while minimizing im-
pact on throughput and latency. This approach also requires that nodes maintain a globally
synchronized sleep“wake cycle, meaning that they must share arbitrary phase information.
The power-save protocol defined in the IEEE 802.11 standard is a synchronous power-
save protocol. Each node explicitly associates itself with a BSS base station (basic service
set) or an IBSS (independent basic service set) and synchronizes itself with its established
beacon interval. This method works well for scenarios in which a single network and
source of phase synchronization can be conveniently designated. This requirement is un-
fortunate because the ad hoc model is specifically designed to support flexible methods of
establishing a network. Ad hoc networks are intended for deployment independent of any
centralized administration and should expect to experience arbitrary partitions and
merges.
Note that the problem of phase synchronization is not the same as the problem of clock
synchronization, which can be achieved using specialized hardware, such as GPS re-
ceivers. Consider, for example, the case of two nearby wireless clouds, which were
formed separately and therefore have differently phased sleep“wake cycles, despite hav-
ing the same period. In order for the two clouds to merge, they must first discover each
other™s existence; then they must either synchronize their sleep“wake cycles or select
nodes to translate between the two networks. The problem is complicated in a multihop
network, in which two nodes might simultaneously initiate independent merges. Although
not insoluble, fully addressing this problem can involve considerable complexity and
overhead, especially in the case of large dynamic networks.

11.4.3.1 Power Saving in IEEE 802.11. IEEE 802.11 IBSS power save is particu-
larly relevant to the ad hoc model, although there are differences between a multihop
wireless network and an IBSS network, in which each node explicitly discovers and asso-
ciates itself with a single, connected IBSS.
In IEEE 802.11 power save, a synchronized beacon interval is established by the node
that initiates the IBSS and is maintained in a distributed fashion. The IBSS also defines a
common fixed-length, ad hoc traffic indication message (ATIM) window, which occurs at
the beginning of each beacon interval. All nodes in the IBSS wake up at the beginning of
the beacon interval and remain awake until the end of the ATIM window. At the beginning
of the beacon interval, nodes randomly contend to transmit the synchronization beacon,
synchronizing themselves with the first beacon they receive. Each node then transmits an
ATIM to every other node for which it has pending unicast traffic. Each node that receives
an ATIM responds with an ATIM acknowledgment. Announcements of broadcast and
multicast traffic are sent to the appropriate broadcast or multicast address, but are not ac-
knowledged. Only beacons, announcements, and acknowledgments are transmitted during
the ATIM window, avoiding contention with data traffic. At the end of the ATIM window,
nodes that have not sent or received ATIM announcements go back to sleep. All other
nodes remain awake throughout the remainder of the beacon interval, in order to send and
receive the announced traffic.
Obviously, the effectiveness of the power-saving mechanism depends on the values se-
lected for the beacon and ATIM intervals, as well as on the offered load. If the ATIM win-
307
11.4 POWER-SAVE PROTOCOLS


dow is too short, not enough traffic is announced during the ATIM window to fully utilize
the beacon interval. If the ATIM window is too long, not only are nodes required to spend
a greater part of each interval awake, but more traffic may be announced than can be sent
in the remainder of the beacon interval. Similarly, if the beacon interval is too short, the
overhead of the sleep“wake cycle, beaconing, and traffic announcements will be high. If
the beacon interval is too long, more nodes will announce traffic at each ATIM window
and more destinations will remain awake after the ATIM window. Contention will also in-
crease, due to the increased number of nodes trying to transmit in each interval.
Although power-saving mechanisms are part of the IEEE 802.11 standard, there appear
to be relatively few published research results that examine their effectiveness. Two of
these, [41] and [6], are discussed below. Unfortunately, the results are only moderately en-
couraging.
Energy consumption is the main criterion in evaluating a power-save protocol, but fac-
tors such as latency, throughput, and distribution of power consumption must also be tak-
en into account. Time spent in the sleep state is only an indication of the actual energy
savings, which will be reduced by the costs of the state transition, beaconing, and ATIM
traffic, all of which are sensitive to these configuration parameters. Analysis of these pro-
tocols therefore depends on measurements such as those described in the previous sec-
tion, as well as on traffic and mobility models.
Simulations described in [41] studied the effectiveness of the IEEE 802.11 power-save
protocol for a fully connected eight-node IBSS. The experiment measured throughput and
time spent in the sleep state for a variety of beacon intervals, ATIM window lengths, and
offered loads. The results show considerable dependence on the beacon interval: Short
beacon intervals give superior energy saving, but at the cost of substantially reduced
throughput. As a general observation, the authors suggest that “if we were to sacrifice
about 10% in throughput, we could save up to 30% energy.” However, such savings are
obtained only at quite moderate loads; as offered load increases from 15% to 30%, the
available savings declines substantially.
The choice of ATIM interval also depends on the offered load. For a moderately to
heavily loaded network and a wide range of beacon intervals, throughput is maximized
when the ATIM window occupies about 25% of the beacon interval. Because a smaller
window results in lower energy consumption while still providing acceptable throughput
for lightly loaded networks, the authors recommend adopting an adaptive ATIM window.
Simulations described in [6] were intended to assess the performance of the authors™
proposed power-save protocol, operating in conjunction with IEEE 802.11 power save.
The results indicate that, by itself, IEEE 802.11 power save does not significantly reduce
energy consumption in a multihop ad hoc environment. The authors suggest that this part-
ly reflects poor handling of broadcast traffic, which forces all the nodes to remain awake
through the beacon interval in which the broadcast is announced. The geographic routing
protocol in these simulations used periodic broadcast, making this weakness particularly
apparent. The results also show that for a multihop network, the cumulative latencies be-
come extremely high because each packet is forwarded at most one hop in each beacon in-
terval.

11.4.3 Topology-Based Power-Save Protocols
Topology-based power-save protocols are based on selecting a subset of nodes that are
topologically representative of the full network. The nodes in this covering set remain in
308 ENERGY-EFFICIENT COMMUNICATION IN AD HOC WIRELESS NETWORKS


the idle state and are responsible for forwarding traffic in the network. Other nodes spend
most of their time sleeping, waking up periodically to participate in subset election or to
receive pending traffic. Topology-based protocols must therefore provide specific mecha-
nisms for selecting the covering set and for forwarding traffic in the partial network de-
fined by the covering set.
The problem of selecting an optimal covering set is nontrivial, especially as it must be
a low-overhead, localized computation. The covering set must be chosen so as to maintain
the effective capacity of the network and minimize the impact of the power-save protocol
on throughput and latency. It must be recomputed in response to node failure and mobili-
ty. In addition, because nodes in the covering set are in the idle state rather than the sleep
state, they consume much more energy. Care must therefore be taken to ensure that this
role is rotated among nodes in the network, so as to maximize the network lifetime.
Although topology-based protocols are not inherently synchronized, they may rely on
synchronized mechanisms for buffering traffic for sleeping nodes. In addition, many
topology-based power-save protocols use connectivity information to determine the cov-
ering set. In this case, nodes that are not currently part of the covering set must exchange
traffic to determine their connectivity. Some scheduling mechanism is needed to support
this process, because it cannot be mediated by the covering set. It is also possible to select
a covering set indirectly or probabilistically. Such techniques lend themselves to asyn-
chronous operation.
The following subsections present three approaches to topology-based power saving:
One is an algorithm for calculating dominating sets, whereas the other two, Span and
GAF, are fully defined protocols.

11.4.3.1 Dominating Sets. A dominating set of a network is a subset of nodes, such
that each node is either in the dominating set or is a neighbor of a node in the dominating
set. In a connected dominating set, the dominating nodes form a connected subgraph of
the network, as in Figure 11.2. The routing backbone that is formed by a connected domi-
nating set is an obvious choice for use in topology-based power-save protocols.
Finding a minimal size dominating set is known to be computationally hard. Ad hoc
networking protocols based on dominating sets must therefore define some distributed al-
gorithm for approximating a dominating set. Most selection algorithms use a two-phase
approach, such as that evaluated in [42]. This approach generally requires some synchro-
nization to ensure consistent operation. In the first phase, nodes exchange neighbor infor-
mation, and any node that has two unconnected neighbors marks itself as part of the con-




Figure 11.2. Connected dominating sets: the relative size of the dominating set (circled nodes) de-
pends on network density.
309
11.4 POWER-SAVE PROTOCOLS


nected dominating set. This set may be much larger than the minimum one. The second
phase therefore eliminates any marked node that is redundant because its one-hop neigh-
borhood is contained within the one-hop neighborhood of an adjacent marked node or is
contained within the union of two such one-hop neighborhoods. Whenever possible, the
node with the lowest energy reserves or with the lowest node degree is preferentially re-
moved from the dominating set.
Connected dominating sets found using this algorithm can be used as a routing back-
bone for the network, although [42] does not present a protocol for dominator selection or
packet forwarding. This means that a packet-level simulation cannot used be used to eval-
uate its performance. The simulation experiments instead evaluate analytically the propor-
tion of nodes selected for the dominating set and the resulting network lifetime, but can-
not fully address issues such as contention, throughput, latency, or packet loss.
In this work, the power consumption of dominator and nondominator nodes was mod-
eled in an interesting way. Rather than simply specifying fixed values, the incremental
cost of acting as a dominating node over some interval is specified as a function of the the
routing overhead, which is proportional to the number of nodes in the network, and the
forwarding overhead, which is inversely proportional to the number of forwarders. The
relative magnitude of these factors depends on the average node degree, path length, and
path lifetime (i.e., mobility), as well as the relative costs of transmitting and receiving.
Simulation results show that after the elimination phase, 30“40% of the nodes are in
the dominating set. The elimination rule protecting nodes with low energy reserves, in
particular, significantly extended the network lifetime. In the case of low mobility and low
routing overhead, however, simple clustering also performed quite well: Although a high
proportion of network nodes were designated as high-energy-consumption clusterheads,
the forwarding load was also divided among the many clusterheads, resulting in good
overall performance. This result closely reflects the modeling of forwarding overhead in
the energy consumption model. It suggests that in some cases, a smaller dominating set is
not necessarily better, even though these nodes have higher energy consumption. It is not
clear whether similar results would be seen in a packet-level simulation, which would in-
clude factors such as routing overhead and contention among the larger number of for-
warding nodes.
The use of a topology-dependent energy consumption model also exhibited another in-
teresting effect. For all values of routing overhead and for all mobility levels, network life-
time decreased asymptotically as the node density increased. A fixed energy consumption
model, on the other hand, yields a roughly linear increase in network lifetime as a func-
tion of density. This increase was also observed in packet-level simulation4 of several oth-
er power-save protocols (discussed below). Simulation results for Span show network life-
time increasing roughly linearly with network density, whereas GAF shows a strong linear
relationship between network lifetime and node density. This intriguing difference high-
lights the impact that the energy consumption model can have on simulation results.

11.4.3.2 Span. Span [6] is a fully specified power-save protocol, based on a routing
backbone that is a connected dominating set, whose members are called “coordinators.”
Coordinators are continually in the idle state, whereas noncoordinator nodes wake up pe-
riodically to exchange traffic with the coordinator nodes and participate in coordinator
election. The coordinators act as a low-latency routing backbone for the network and

4
Note that node densities in the packet-level simulations were higher (20“80 vs. 4“20 nodes in transmit range).
310 ENERGY-EFFICIENT COMMUNICATION IN AD HOC WIRELESS NETWORKS


buffer traffic for sleeping destinations, in effect acting as base stations for the noncoordi-
nator nodes.
The coordinator election algorithm is structurally similar to the one described above, in
that nodes provisionally join the dominating set, then eliminate themselves from it. Nodes
periodically exchange HELLO messages to discover their two-hop neighborhood. A node
marks itself eligible to be a coordinator if it discovers that two neighbors cannot commu-
nicate directly or via other coordinators. Each marked node schedules a backoff interval,
during which it listens for announcements from other nodes. If the node is still eligible af-
ter this interval (i.e., no other suitable coordinators have announced themselves), it sends
its own coordinator announcement. The backoff interval has both random and adaptive el-
ements. Nodes with greater utility, that is, effectiveness at connecting new pairs of neigh-
bors, and higher energy reserves announce themselves as coordinators more quickly than
less effective ones, which volunteer later and only if they are still needed to complete the
connected dominating set. After spending some time as a coordinator, a node withdraws
as a coordinator, allowing other nodes to consider their eligibility and announce them-
selves as coordinators. Rotating the coordinator role in this way tends to balance nodes™
energy reserves, even in the case of initially unequal distribution.
The coordinators buffer traffic for their sleeping neighbors, using the traffic announce-
ment mechanism of IEEE 802.11. Because coordinators do not sleep, they have no need
for the traffic announcement mechanism and a portion of each beacon interval is therefore
reserved for traffic between coordinators. The routing protocol is integrated with the coor-
dinator mechanism so that data is forwarded through the coordinator backbone with low
latency until it is buffered by the appropriate coordinator for delivery to a sleeping desti-
nation.
Packet-level simulations using ns-2 [37] suggest that, compared to IEEE 802.11 power
saving, Span provides about 50% energy saving in dense (12“78 nodes/transmit area) net-
works, with only minimal impact on throughput and packet loss. The savings increase
only slightly with node density, due to the increasing overhead of the traffic announce-
ment mechanism. There is also a two- to four-fold increase in latency, which also increas-
es with node density. Rotation of the coordinator role equalizes energy consumption and
the network lifetime increases 50“100%, as discussed above. The results also corroborate
the experimental energy measurements. Even when Span is used to limit idle energy con-
sumption, sending and receiving traffic accounts for well under 10% of the total energy
consumed.
Span is a synchronous power-save protocol for two reasons. First, nodes must be awake
simultaneously to exchange traffic to determine their connectivity and participate in coor-
dinator election”the topology cannot be determined solely by the coordinators. Second,
the underlying buffering and traffic announcement mechanism is based on the synchro-
nous IEEE 802.11 power-save mechanism. This is not integral to Span operation, howev-
er; some form of asynchronous polling is a possible alternative.

11.4.3.3 GAF. Geographic adaptive fidelity (GAF) [45] is a power-save protocol that
selects its representative nodes based on position information rather than membership in a
dominating set. As defined, GAF is primarily intended for sensor networking scenarios.
Nodes that are data sources or sinks do not participate in the power-save protocol, and
there is no concept of buffering pending traffic for a sleeping node.
GAF partitions the network using a geographic grid. The grid size is defined such that

<<

. 59
( 87 .)



>>