﻿Abstract
A link-indexed statistical traffic prediction approach
to improving IEEE 802.11 PSM
Chunyu Hu a , Jennifer C. Hou b, *
a Department of Electrical and Computer Engineering, University of Illinois, Urbana, IL 61801, USA
b Department of Computer Science, University of Illinois, Urbana, IL 61801, USA
Available online 15 September 2004
IEEE 802.11 power save mode (PSM) is a representative of energy-saving protocols which put wireless network interfaces
into sleep during idleness. To save energy, part of the performance of IEEE 802.11 is sacrificed attributed to the
wake-up latency thus introduced. This paper proposes a complementary mechanism, called link-indexed statistical traffic
predictor (LISP) to improve IEEE 802.11 PSM. LISP employs a simple, light-weight traffic prediction method to speed
up the delivery of packets along the end-to-end path. By seeking the inherent correlation between ATIM_ACKs and
incoming traffic, nodes en route stay awake in the beacon intervals in which packets are anticipated to arrive. As the
result, a ‘‘freeway’’ is bridged for packets to rapidly traverse the route. Meanwhile, the number of duty cycles is reduced
and more energy is conserved. We have conducted analytical and simulation studies and demonstrated the effectiveness
of LISP. The impact of various factors is investigated, including traffic load, number of hops (of routes which connections
traverse), ATIM window size and packet size, in both tandem networks and networks of arbitrary topologies.
Ó 2004 Elsevier B.V. All rights reserved.
Keywords: Power management; IEEE 802.11 PSM; Traffic prediction; IEEE 802.11 MAC
1. Introduction
Energy is an indispensable but limited resource
in battery-powered wireless networks. As wireless
communication consumes significant energy in
mobile computing devices, how to enable wireless
communications to be as energy efficient as possi-
* Corresponding author. Tel.: +1 217 265 6329.
E-mail address: jhou@cs.uiuc.edu (J.C. Hou).
Ad Hoc Networks 3 (2005) 529–545
1570-8705/$ - see front matter Ó 2004 Elsevier B.V. All rights reserved.
doi:10.1016/j.adhoc.2004.08.003
www.elsevier.com/locate/adhoc
ble has recently attracted much research attention.
This issue is particularly important in wireless ad
hoc networks, due to the fact that wireless devices
in such networks serve not only as sources or destinations,
but also as relay nodes.
There exist several design choices for improving
energy efficiency in wireless ad hoc networks,
ranging from designing energy efficient wireless
network interfaces to fine tuning the network protocol
stack at various layers. The former saves
530 C. Hu, J.C. Hou / Ad Hoc Networks 3 (2005) 529–545
power by using low power components and providing
upper layers with adequate interfaces to
manage the operating mode of the device. The latter
leverages the interfaces thus provided and tunes
the operations of higher protocol layers in a
power-aware manner. For example, the operational
mode of the device can be controlled [7]
and/or the various power management strategies
can be exercised in the MAC layer. Topology control—determination
of the adequate transmission
power of each node so as to maintain network
connectivity while consuming the minimum possible
power [2,6,13]—is another (orthogonal) strategy
for increasing energy efficiency, and spans
the physical, MAC, and network layers. Several
energy efficient routing protocols have also been
proposed, e.g., minimum energy routing [8] and
power aware routing [10], in the network layer.
In this paper, we focus on the issue of improving
power efficiency in the MAC layer, and will provide
a comprehensive overview of existing work
that pertains to our work in Section 2.
The energy consumption states of network
interfaces can be typically classified into five states:
transmit, receive, idle, sleep and off. The power
consumption in the sleep state is, in general, an
order of magnitude lower than that in the idle
and active (transmitting or receiving) states. As a
matter of fact, as indicted in several experimental
results [3], the energy consumed in the idle state
is only slightly smaller than that in the active state.
This is because a wireless device in the idle state
has to continuously listen to the wireless medium
for potential communication. These facts lead to
several proposals that put the radio into the sleep
state in the absence of communications activities,
with the objective here is to minimize energy consumption
with a minimal impact to the network
performance in terms of end-to-end latency,
throughput and routing latency. The challenge lies
in determining appropriate times to switch the
radio to the sleep state and back to the idle state.
IEEE 802.11 power save mode (PSM) is a representative
of the above power saving mechanisms.
All the nodes in the network are time synchronized
by a beacon mechanism. They wake up periodically
at the beginning of each beacon interval
and check whether or not they have packets to
transmit or receive. If not, they go back to sleep
and thus conserve energy. As the nodes in the sleep
state can neither transmit nor receive packets,
packets that are destined for a sleeping node have
to wait for the next beacon interval (BI) to be
transmitted. This is termed as the wake-up latency
and is considered a major factor for packet delay.
The effect of the wake-up latency is especially
pronounced when the inter-packet interval is large
enough that a packet can only traverse one hop in
a BI, and a relay node has to wake up twice for one
packet—one to receive the packet and the other to
forward it.
To deal with the undesirable wake-up latency issue
in IEEE 802.11 PSM, we propose a novel and
complementary mechanism, called link-indexed
statistical traffic predictor (LISP). Conceptually
LISP employs a simple, light-weight traffic prediction
method and enables each node to seek the
inherent relation between ATIM_ACKs and
incoming traffic. Once such a relation is identified,
a node en route stays awake in a BI in which a
packet is anticipated to arrive, thus bridging a
‘‘freeway’’ for the packet to traverse the route. In
this manner, a packet can ideally travel from the
source to the destination within one BI. Meanwhile,
the number of duty cycles is reduced and
energy is conserved. Another salient feature of
LISP is that as compared to IEEE 802.11 PSM that
consumes energy of intermediate nodes much more
than that of the source and destination nodes, LISP
balances energy consumption over the nodes en
route. LISP differs from previous work [13,2,15]
in that it does not trade energy for better end-toend
performance at low to moderate traffic loads,
i.e., it reduces the end-to-end delay without consuming
more power. Instead, energy is further
saved because of the reduction in duty cycles. We
conduct analytical and simulation studies, and
investigate the impact of various systems parameters,
including traffic load, number of hops, ATIM
window size and packet size using a tandem topology.
In several scenarios simulated, LISP has been
demonstrated to outperform IEEE 802.11 PSM
with respect to the end-to-end delay by 65–75%,
and IEEE 802.11 with and without PSM with respect
to energy efficiency by 6% and 178%,
respectively.
The rest of the paper is organized as follows. In
Section 2, we provide a detailed taxonomy of existing
work and motivate the need for our work.
Then we elaborate on LISP and its component
procedures in Section 3, and conduct a performance
analysis in Section 4. Following that, we present
our performance results in Section 5. Finally
we conclude the paper in Section 6 with several research
avenues listed for future work.
2. Background and related work
2.1. Overview of IEEE 802.11 PSM
IEEE 802.11 specifies the operations of power
management for both PCF and DCF [1]. Aswe
consider in this paper wireless ad hoc networks,
we focus on IEEE 802.11 PSM for DCF unless
specified otherwise. In IEEE 802.11 PSM, a node
may operate in one of the two modes: active mode
(AM) and power save mode (PSM). All the nodes
are time synchronized by a beacon mechanism.
The time is divided into beacon intervals (BIs). A
BI begins with an ATIM window. For notational
convenience, we name the remaining time following
the ATIM window in a BI the DATA window. All
nodes wake up periodically at the beginning of every
BI and stay awake through the ATIM window.
During that time, if a node has a packet destined
for a receiver node, it will send an ATIM packet,
and the addressed receiver node acknowledges that
it will stay awake in the current BI with an ACK.
Such an ATIM/ACK exchange ensures both the
sender and the receiver will stay awake in the DATA
window in which the packet will be transmitted
using the conventional RTS-CTS-DATA-ACK
mechanism. On the other hand, if a node neither
has a packet to send nor receives an ATIM packet,
it goes to sleep at the end of the ATIM window by
putting its radio into the sleep state.
2.2. Related work
A number of mechanisms have been proposed
to improve the performance of IEEE 802.11
PSM, which can be roughly classified into three
categories: (i) mechanisms that tune the para-
C. Hu, J.C. Hou / Ad Hoc Networks 3 (2005) 529–545 531
meters of IEEE 802.11 PSM; (ii) mechanisms that
center on the notion of virtual routing core; and
(iii) wake-up-on-demand power management
mechanism. In what follows, we provide a succinct
summary of them.
In the first category, Woesner et al. [12] investigate,
via simulation, the optimal ratio of the
ATIM window size to the beacon interval, and
suggest the value of approximately 1/4. Jung and
Vaidya [5] propose a mechanism of adjusting the
ATIM window size dynamically to accommodate
varying traffic loads. Tseng et al. [11], on the other
hand, address the problems caused by in-synchronization
and propose the notion of asynchronous
wake-up. In spite of all the efforts, the problem
of prolonged end-to-end delay as a result of exercising
PSM remains.
Geographic adaptive fidelity (GAF) [13] and
Span [2] are two representative mechanisms that
employ the notion of virtual routing core. Ondemand
power management (on-demand) [15],
STEM [9] and S-MAC [14] are representatives of
the third category. Both virtual routing core-based
mechanisms and on-demand mechanisms share the
similarity that both attempt to keep a subset of
nodes awake in the course of communication
activities. The major difference, however, lies in
that the former maintains an always active routing
backbone and performs well when there exists a
substantial amount of traffic to amortize the overhead
of building/maintaining the backbone. The
on-demand mechanisms, on the other hand, react
in the presence of communication activities. Its
performance relies heavily on the appropriate setting
of timer values.
In contrast to the above three categories of
mechanisms, LISP enables nodes en route to enter
the active mode only in beacon intervals in which
packets are anticipated to arrive. That is, nodes respond
to communication activities at the beacon
interval level, rather than at the connection level
(as was done in the on-demand power management
mechanism). By employing a simple, lightweight
traffic prediction method and performing
power management at a finer time granularity,
LISP further reduces the energy consumption incurred
in the process of improving the end-toend
packet delay.
532 C. Hu, J.C. Hou / Ad Hoc Networks 3 (2005) 529–545
3. Link indexed statistical traffic predictor
3.1. Overview of the basic mechanism
As discussed in Section 1, the major factor that
leads to the increase in the end-to-end delay in
wireless ad hoc networks with PSM is the wakeup
latency. Ideally, a node should stay awake
and forward packets in the BI in which a packet
arrives. However, this may not be possible without
detailed information provided by the upper layers.
The on-demand power management mechanism,
for example, simply enables all nodes en route to
stay awake during the duration of a connection.
In this section, we discuss how we perform power
management at a finer time granularity by using a
light-weight prediction mechanism. The key idea
of the proposed traffic prediction mechanism is
to take advantage of the correlation between the
ATIM/ACK exchange of upstream nodes and
the incoming traffic. We use the following example
to illustrate the idea.
Example 1. Consider a single connection that
traverses the route: node 1 ! node 2 ! node 3.
Suppose a packet is generated at node 1 at time t0.
As shown in Fig. 1, node 1 has to wait for the next
BI, BI1, to initiate an ATIM/ACK exchange with
node 2 and then to forward the packet in the
DATA window. Similarly, node 2 has to wait for
the next BI, BI2, to forward the packet to node 3.
Note that the event that a data packet will arrive at
node 3 (indicated by an ATIM packet in BI2) is
preceded by the event that an ATIM_ACK packet
was sent by node 2 in BI1. Note also that the latter
event can be naturally overheard by node 3, as
node 3 is the next hop en route. Therefore, if node
3 can judiciously interpret the ATIM_ACK packet
as an indicator of incoming traffic, it can stay
awake through BI1. In this manner, the packet can
be forwarded to node 3 in BI1, and the wake-up
latency can be greatly reduced.
To realize the above idea, we have to consider
three issues. First, a downstream node (e.g., node
3 in Example 1) has to determine whether or not
an overheard ATIM_ACK is indeed the preamble
of future packet arrival. A simple mechanism is for
each node to snoop the header of overheard pack-
time
node 1
node 2
node 3
node 2
node 3
Beacon Interval: BI_1
ATIM Data Packet
ACK
ACK
PseudoACK
Data Packet
ATIM
ets. If it overhears an ATIM_ACK packet addressed
for some other node in a BI, and receives
an ATIM in the subsequent BI, it recognizes the
correlation. Next time when it overhears an
ATIM_ACK packet again, it takes that as an indication
of incoming traffic and thus stays awake
through the BI. On the other hand, if such a conjecture
is not confirmed in the next BI (i.e., the
node receives no ATIM packet in the next BI), it
‘‘forgets’’ the recent history and learns from
scratch.
The second issue is concerned with how an upstream
node (e.g., node 2 in Example 1) knows its
downstream node (e.g., node 3 in Example 1) has
detected the correlation and will be awake in the
current BI, so that it can forward the packet to
the downstream node. The third issue is that in
the case that a connection traverses more than 2
hops, how nodes further downstream perform prediction
in the absence of an ATIM/ACK exchange.
These two issues are collectively resolved
by having a node i transmit a pseudo-ACK packet
when it makes a prediction. This pseudo-ACK
packet notifies node iÕs upstream node of its will-
ACK
ATIM Window
Data Packet
w/o prediction
w/o prediction
w/ prediction
w/ prediction
Fig. 1. An example that demonstrates the basic idea of LISP.
A single connection traverses the route: node 1 !
node 2 ! node 3.
ingness to stay awake in the current BI. Moreover,
this pseudo-ACK packet is taken by node iÕs
downstream node as if it were an ATIM_ACK
packet (in the sense that it indicates packet arrival
in the immediate future). In this manner, a ‘‘chain’’
effect can be triggered. For notational convenience,
we will henceforth term both ATIM_ACK
packets and pseudo-ACK packets as traffic indicators
since both of them serve the purpose of indicating
future traffic.
3.2. Detailed description of the basic mechanism
In this subsection we give a detailed description
of the various operations of LISP. There are two
phases in the traffic prediction process: learning
and prediction. In the learning phase, a node
makes a conjecture and attempts to confirm it.
Specifically, if in the ATIM window of a BI, a
node A overhears from its neighbor node B an
ATIM_ACK packet addressed for some other
node, node A conjectures itself to be the next
hop node. If in the next BI, node A indeed receives
an ATIM packet from node B, it confirms the conjecture
and will enter the prediction phase. Otherwise,
node A resets its state and starts all over
again. In the prediction phase, if node A predicts
that node B will forward one or more packets to
itself, it will stay awake through the current BI.
Meanwhile, node A transmits a pseudo-ACK
packet announcing this fact. All of node AÕs neighbors
that receive this pseudo-ACK packet will take
it as if it were an ATIM_ACK packet and run the
same traffic prediction process accordingly. Node
A is said to be in the temporary active mode, or
TAM, when it stays active in the current BI and
its neighbors can forward packets to it even if they
have not performed an ATIM/ACK exchange
in the ATIM window of the current BI. The
TAM expires automatically when the next BI commences
and the node switches back to its previous
mode.
The above operations can be described by a finite
state machine. Every node runs a finite state
machine for each overheard neighbor. We define
such a state as the node-indexed state (NI-state).
We take the state maintained by node A for a
C. Hu, J.C. Hou / Ad Hoc Networks 3 (2005) 529–545 533
*
5
prediction phase
next BI begins
start
**
0
4
overhears a traffic indicator
from B or other node
next BI begins
next BI begins
A receives an ATIM
from B for itself in
*: A overhears a traffic indicator from B for another node
and then makes a prediction by taking the following actions:
1) enter the Temporary Active Mode;
2) transmit a pseudoACK.
**: A receives a DATA pkt. from B
neighbor node B, denoted by SA(B), as an example
(Fig. 2).
The state starts at 0. Node A snoops every
packet it hears. If in a BI it overhears a traffic indicator
from node B addressed for another node,
S A(B) enters state 1. When the next BI commences,
S A(B) transits to state 2, waiting for an ATIM
packet from node B to confirm the conjecture. If
this is indeed the case, SA(B) enters state 3; otherwise,
when the next BI commences, the state is reset.
In the former case, the prediction phase begins
in the next BI since node A will stay awake in the
current BI anyway. SA(B) transits from state 4 to
state 5 when node A overhears a traffic indicator
from node B and herein a prediction is made. If
a data packet arrives in the same BI, the state will
transit from state 5 back to state 4, indicating a
successful prediction. On the other hand, if node
A does not receive any data packet from node B
in the same BI, SA(B) stays at state 5 and will be reset
to state 0 when the next BI begins. Note that
there is a transition from state 1 to state 3. This
occurs when node A overhears a traffic indicator
and then receives an ATIM or data packet in the
same BI (which in turn occurs when the packet
inter-arrival time is no less than one BI). Depending
on the packet arrival interval, it takes 1–2 BI(s)
to accomplish the learning phase.
current BI 1
3
learning phase
next BI begins
2
A receives an ATIM
from B for itself in
current BI
Fig. 2. Finite state machine that describes the operations of
LISP.
534 C. Hu, J.C. Hou / Ad Hoc Networks 3 (2005) 529–545
3.3. Extension to multiple connections
The basic mechanism may not operate correctly
in the presence of multiple connections, as connections
may share nodes or links on their routes, and
a node may receive/forward packets from different
connections in an interleaving fashion (refer to [4]
for examples). As a result, the correlation between
traffic indicators and arrivals of packets for one
connection has to be differentiated from those for
other connections. To address this issue, we consider
two alternatives: (i) link-indexed state (LIstate):
the state indexed by a link identified by its
two end points: hnode 1,node 2i; and (ii) connection-Indexed
state (CI-state): the state indexed by
the source and destination of a connection:
hsrc,dsti.
In general, the CI-states performs most effectively.
As long as a node receives a traffic indicator
with the connection information enclosed, it can
tell whether it should keep awake. However, with
a closer investigation, we find that indexing states
with connections may not always be feasible.
First, the ATIM_ACK operation is basically
link-oriented. As IEEE 802.11 PSM states, a node
only needs to send one ATIM packet to the intended
receiver in a BI even if it has multiple data
packets from different connections. Indeed, multiple
ATIM requests would consume bandwidth
and cause contention unnecessarily. Second, the
connection identification information is only
available at the network and higher layers. To obtain
the source and the destination information,
the link level mechanism has to look into the network
layer header of a packet, thus introducing
cross-layer issues. Third, to include the connection
information in each ATIM and ATIM_ACK
packets will increase the packet size. In contrast,
one needs only to attach the receiverÕs address in
the ATIM_ACK packet in the case of the LIstates.
With both the pros and cons taken into consideration,
the LI-states are perhaps the best candidate
in terms of effectiveness and feasibility. To
make up for its deficiency, we introduce in Section
3.4 a statistical technique attempting to profile the
traffic with the maximum likelihood. To reflect the
fact that the statistical technique is used, we name
the enhanced mechanism the link-indexed statistical
traffic predictor (LISP).
3.4. Full fledged mechanism—LISP
We enhance the basic mechanism in two aspects.
First, the state is link-indexed. A node maintains
a state for each overheard link. Second, the
prediction is not made solely on the traffic indicator,
but also on the statistical result computed
from the past traffic history. To this end, 1 after
a node enters the prediction phase, it records the
correlation between a traffic indicator and the
packet arrival. If a packet does arrive in the immediate
future, the node records a ‘‘1’’ for the link;
otherwise, a ‘‘0’’. The number of records kept for
each state is at most K, where K is a pre-specified
constant (we use K = 8 in our simulation study).
At the time of making prediction, the node calculates
the percentage of positive correlations in the
past, i.e., p ¼
number of \1" in M records
M
, where M is
the number of records kept so far. In some sense,
p measures the credibility of traffic indicators. A
random number r that is uniformly distributed in
[0, 1] is generated and compared against p. If
r 6 p, the node predicts that a packet will arrive
in the current BI and enters the TAM if it is not
in yet; otherwise, it predicts the opposite and does
nothing.
The revised finite state machine that describes
the full fledged mechanism is given in Fig. 3. In
particular, Fig. 3(a) gives the finite state machine
to be run for a LI-state hB,Ci at node A. The state
transitions are similar to those in Fig. 2, except
that (i) the transition from state 4 to state 5 takes
place only when a positive prediction is made; and
(ii) in the prediction phase the state will not be reset
unless all the records become zeros. This is indicated
by an arrow from state 4 pointing to state 0
and is triggered by the event of all records becoming
zeros.
The other finite state machine given in Fig. 3(b)
is run for the associated record state, which is used
to generate a current record. There are three
1 By ‘‘the node enters the prediction phase’’, we actually
means ‘‘a link-indexed state at the node enters the prediction
phase’’.
typical transition paths: 0 ! 1 ! 0, 0 ! 1 ! 2 ! 0
and 0 ! 1 ! 2 ! 3 ! 0, recording the correlations
in the three cases illustrated, respectively, in
Fig. 4. More complicated transition paths exist,
e.g., 0 ! 1 ! 2(! 3 ! 2) ! 0 and 0 ! 1 !
2(! 3 ! 2) ! 3 ! 0, where (! i ! j) denotes
the transition can repeat one or multiple times.
They are simply combinations of the three cases.
3.5. Fault tolerance
*
5
next BI
begins
*: A overhears a traffic indicator from B for C, and then makes a prediction
based on the statistical result computed from past records. If a ’true’
prediction is made, the state transits to 5 and the following actions are taken:
1) set its own mode to Temporary Active Mode;
2) transmit a pseudoACK addressed for B.
In addition to the case that multiple connections
are present, traffic prediction may not be
accurately made in the case of collisions. A node
may miss its chance of overhearing a traffic indicator
when there are collisions. In general,
ATIM_ACK packets are more immune to collisions
as the nodes hearing the CTS (in the RTS/
CTS floor acquisition mechanism) have performed
necessary backoffs. However, it is more likely that
pseudo-ACK packets incur collision with other
on-going transmissions (e.g. beacon messages).
The aftermaths are twofold: first, from the viewpoint
of a downstream node, if it misses a traffic
indicator in the learning phase, it will wait longer
start
All records become ’0’
prediction phase
4
0
overhears a traffic
indicator from B for C
next BI begins
next BI begins
1
A receives an ATIM
or DATA pkt from B for A 2
in current BI
A receives an ATIM
or DATA pkt from B for A
in current BI
3
learning phase
next BI begins
ATIM/DATA (B–>A) (output I twice)
0
3
a traffic indicator (B–>C)
ATIM/DATA (B–>A) (output I)
next BI begins (output II)
ATIM/DATA (B–>A) (output I)
a traffic indicator (B–>C)
next BI begins (output II)
output I: generate a ’1’ record
output II:
1) generate a ’0’ record
2) Check whether all records are 0’s
(a) (b)
Fig. 3. Finite state machines running at node A for link hB,Ci.
I M D
I
BI
C. Hu, J.C. Hou / Ad Hoc Networks 3 (2005) 529–545 535
to enter the prediction phase and the first few
packets experience larger end-to-end delays. If
the node misses a traffic indicator in the prediction
phase, it fails to perform the prediction and the
packet sent in the current BI experiences a larger
end-to-end delay. Second, from the viewpoint
of an upstream node, it may fail to receive the
pseudo-ACK transmitted by the node at the next
hop. In the case that occurs, in the following
DATA window even though the downstream node
is actually awake, the upstream node will not forward
packet(s) to it. This not only delays the delivery
of the packet but also lures the downstream
node to reset its state because it keeps awake but
does not receive any packet. This negative effect
can also be mitigated by the statistical approach
proposed in Section 3.4.
4. Performance analysis
4.1. Effect of wake-up latency
As pointed out in Section 3, the wake-up latency
is the most important factor that degrades
M D I
IM
D
ATIM Window
BI
ATIM Window
BI
ATIM Window
(a) (b) (c)
Fig. 4. Three cases to be considered in the finite state machine given in Fig. 3(b) for the associated record state. I—a traffic indicator,
M—an ATIM packet, D—a data packet.
1
2
next BI begins
536 C. Hu, J.C. Hou / Ad Hoc Networks 3 (2005) 529–545
the end-to-end performance of PSM. It increases
the end-to-end delay at the scale of BIs even under
light traffic load. To analyze the impact of the
wake-up latency in isolation of other factors, we
study in this section the performance of IEEE
802.11 with (termed as PSM) and without PSM
(termed as nonPSM) and LISP under a simple
yet representative scenario. For notational convenience,
we define in Table 1 the notations to be
used throughout the analysis.
4.1.1. Network model and performance metrics
We consider a wireless ad hoc network with a
single connection that traverses H hops:
n 0 ! n 1 ! !n H. Wireless nodes are assumed
to be time synchronized. The per hop MAC delay
for packets of the same size is assumed to be the
same and is denoted by DP. Note that DP includes
the transmission time of RTS, CTS, DATA
and ACK packets, the inter-frame time and the
propagation time. In general, BI is much larger
than DP. We also assume the duration of an
ATIM window, T ATIM, is long enough to accommodate
the prediction chain made by all the nodes
en route.
We consider the case in which packet inter-arrival
time is large enough to avoid the pipeline effect,
i.e., every node receives or forwards at most one
packet in a BI. This is, in general, true when the
packet inter-arrival time is larger than one BI.
Hence we assume the packet generation rate of
the connection is k 6 0.5BI 1 . Under this assumption,
the effect of contention is negligible and the
effect of the wake-up latency can manifest itself
in the end-to-end delay analysis.
We will derive the end-to-end delay, D, and the
power saving under the scenario described above.
To quantify the amount of power saving, we define
a new metrics, duty cycle ratio R, as the number of
duty cycles over the total number of BIs throughout
the duration of a connection, where a duty
cycle is a BI through which the node stays awake.
Note that R is a good indication of power saving
for any energy model in which the power consumed
in the idle state is comparable to that in
transmitting and receiving. It measures approximately
the ratio of power consumed with and
without power management.
4.1.2. IEEE 802.11 without PSM (nonPSM)
Under the above assumption, the average duty
cycle ratio and the end-to-end delay of nonPSM
can be expressed, respectively, as
DnonPSM ¼ HDP; ð1Þ
RnonPSM ¼ 1; ð2Þ
where H is the number of hops of the route.
4.1.3. IEEE 802.11 PSM
Under IEEE 802.11 PSM, it takes one BI for a
node to receive or to forward a packet. Therefore,
it takes one BI for the source (the destination) to
send (receive) a packet, and two BIs for intermediate
nodes to receive a packet and to forward it.
For a connection that lasts for N time units (note
that the time is normalized with respect to BIs), a
total of kN packets are generated, and N 0
src ¼
N 0
dst
0
¼ kN; N intermediate nodes ¼ 2kN. Let the average
number of duty cycles over all nodes en route be
Table 1
Notations used throughout the analysis
BI Length of a BI
TATIM
Length of an ATIM window
DP Per hop MAC layer delay without PSM
k Packets generation rate of a connection (in terms of number of packets per BI)
ti One hop delay of a packet from node ni 1 to node ni tg
Given that a packet is generated at the source node at time t, tg is the relative offset to the beginning of the
current BI. tg is assumed to be uniformly distributed in [0,BI]
D End-to-end delay
N Total number of BIs throughout the duration of a connection
N 0 Number of duty cycles of a node throughout the duration of a connection
R Duty cycle ratio, defined as N 0 /N
denoted as N 0 . Then we have N 0
PSM
ðH 1Þ 2kNÞ ¼ H
Hþ1
cycle ratio is thus
1 ¼ ð2kN þ
Hþ1
2kN. The average duty
RPSM ¼ 2k H
: ð3Þ
H þ 1
Next we derive the amount of time it takes for a
packet to traverse one hop. Given the definitions
of tg and ti in Table 1, we consider two cases where
tg may fall in a BI: if tg < TATIM, the packet may
be transmitted in the current BI; otherwise, it has
to wait for the next BI to be transmitted. In the
former case, t1 = TATIM tg + DP; while in the
latter case, t1 =BI tg + TATIM + DP. Conditioned
on tg and under the assumption that tg is
uniformly distributed in [0, BI], it can be calculated
that
E½t1Š ¼ 1
2 BI þ DP þ T ATIM 1
T ATIM
BI
: ð4Þ
After the first hop, when the packet arrives at
node ni 1 (i > 1), it has to wait for next BI to be
forwarded since ni is asleep. Hence ti =
BI (TATIM + DP)+(TATIM + DP) = BI for
i > 1. The end-to-end delay of a packet is therefore
D ¼ P H
i¼1 ti ¼ t1 þðH 1ÞBI. Finally, we have
DPSM ¼ H 1
2 BI þ DP þ T ATIM 1
T ATIM
BI
:
ð5Þ
4.1.4. LISP
The ATIM_ACK from the source triggers the
traffic prediction operation at the next hop, and
pseudo-ACKs are transmitted sequentially one
by one till the destination. Hence when the packet
arrives at the next hop of the source node, all the
downstream nodes keep awake, and their respective
upstream nodes are notified of this fact. As a
result, the packet reaches the destination node in
one BI. The number of duty cycles of any node
en route is N 0 ¼ N 0 ¼ kN, and
RLISP ¼ k: ð6Þ
The end-to-end packet delay under LISP is
D = t 1 + T ATIM + HDP. By Eq. (4), we have
C. Hu, J.C. Hou / Ad Hoc Networks 3 (2005) 529–545 537
Table 2
Performance comparisons of nonPSM, PSM and LISP
End-to-end delay Duty cycle
ratio
NonPSM HDP 1
PSM H 1
2 BI þ DP þ T ATIM 1
T ATIM
BI
LISP
1
2 BI þ HDP þ T ATIM 1
k
DLISP ¼ 1
2 BI þ HDP þ T ATIM 1
T ATIM
BI
T ATIM
BI
2k H
Hþ1
: ð7Þ
4.1.5. Comparisons among IEEE 802.11 with
and without PSM and LISP
We list the above results in Table 2. Comparing
the duty cycle ratios of each scheme, we have
RnonPSM > RPSM > RLISP. When the traffic rate k is
smaller than one packet every other BI, the average
active time of a node under PSM is approximately
2k H of that without PSM. This explains
Hþ1
why PSM can save power. Note, however, that
the amount of saving decreases when the number
of hops increases. LISP further reduces the active
time to approximately kN regardless of the number
of hops.
PSM conserves power at the expense of larger
end-to-end delay. From Table 2, we see
DnonPSM < DLISP < DPSM. DPSM is the product of
BI and the number of hops plus a constant value
determined by system parameters, while DLISP is
independent of the number of hops (ideally) and
is comparable to one BI. This is a significant
improvement, especially considering the fact that
LISP also conserves more energy at the same time.
LISP makes all the performance improvement
without much overhead. The computation overhead
incurred at a node is that of running two finite
state machines for each overheard link. A
few bytes are needed for each node to maintain
the states. The communication overhead incurred
is to transmit a pseudo-ACK in the case of making
a positive prediction. The impact of transmitting
pseudo-ACK packets in an ATIM window on
other on-going traffic is not significant, as the size
of pseudo-ACK packets is small. Moreover, these
pseudo-ACK packets actually play the role of receiver-polling
and hence the upstream nodes do
not have to initiate ATIM_ACK exchanges.
538 C. Hu, J.C. Hou / Ad Hoc Networks 3 (2005) 529–545
4.2. Effect of other factors
In more general scenarios where the traffic load
is heavy and multiple connections are present, the
effect of medium access contention and queuing
delay may couple with the wake-up latency and degrade
the performance of both PSM and LISP. We
will investigate their impact in our simulation
study under general scenarios (Section 5). Qualitatively,
LISP has its own limitations under these
general scenarios. First, as discussed in Section
3.5 ATIM_ACK and pseudo-ACK packets are
prone to collisions. Second, as discussed in Section
3.3, prediction on the incoming traffic may not be
accurately made in the case that connections share
common links and then diverge. Although the
effect of inaccurate prediction is mitigated by the
statistical approach proposed in Section 3.4, it still
degrades the performance to some extent in the
presence of multiple connections.
5. Simulation study
To validate and evaluate the design of LISP, we
have implemented LISP in ns2 and carried out a
simulation study. The code for IEEE 802.11
PSM was originally developed by Span [16], and
has been adapted to accommodate LISP. We compare
LISP against IEEE 802.11 with and without
PSM, and on-demand [15], with respect to the following
four metrics: (i) end-to-end delay, D; (ii) energy
efficiency, EE, defined as the end-to-end
throughput (bits) over the energy (Joule) consumed
in the duration of a simulation run; (iii)
packet delivery ratio (or normalized throughput),
g; and (iv) duty cycle ratio, R, respectively. The
first three metrics evaluate the network performance
(D and g) and the effectiveness of power saving
(EE). The last metrics, R, measures the
percentage of time that nodes are put into sleep,
and reflects indirectly the percentage of energy
saving.
We consider several parameters in the simulation
study: traffic load, number of hops, ATIM
window size, and packet size. To study the impact
of each parameter on the performance, we first
consider a tandem topology of H + 1 nodes (that
line up with an equal distance of 200m) with a
CBR connection traversing from the first node to
the end node. Only neighboring nodes can communicate
with each other. Then we consider a
more general scenario in which nodes are randomly
distributed in the field.
The simulation environment has been set up as
follows. All the nodes communicate with each
other with half-duplex radio, and have a uniform
communication range of 250m. The energy model
given in [3] is used, i.e., it takes 1400mW,
1000mW, 830mW and 130mW for a node to
transmit, receive, stay idle and sleep, respectively.
The energy consumed for switching between idle
and sleep states is assumed to be negligible and
not counted for in the simulation. The length of
a BI and an ATIM window are chosen as 100ms
and 20ms, respectively, unless specified otherwise.
The dynamic source routing protocol (DSR) is
used as the underlying routing protocol. Long live
CBR traffic is sent from the source nodes to their
respective destination nodes. All the packets have
a uniform size of 1K bytes unless specified otherwise.
Each simulation run lasts for 500 s, and each
data point is an average of 10 simulation runs.
5.1. Performance in a tandem wireless network
5.1.1. Effect of traffic load
We first investigate the effect of traffic load on
the performance in a tandem wireless network described
above. We simulate a number of scenarios
with a wide range of traffic loads in a tandem network
of different numbers of hops H. Fig. 5 gives
the simulation results in the case that H = 4 and
the packet generation rate k varies from 0.1 to 8
packets/BI. Several observations are made:
1. LISP makes significant improvement over PSM
by reducing the end-to-end delay to approximately
one BI (0.1s). As presented in Fig.
5(a), the end-to-end delay under LISP is
approximately 0.24–0.29 of that under PSM
before the network capacity is saturated.
2. As shown in Fig. 5(b), LISP is most energy efficient
among all the mechanisms under light and
medium traffic load. Only after the traffic load
becomes heavy, e.g., k > 2 packets/BI PSM
End-to-End delay (sec.)
1.8
1.6
1.4
1.2
1
0.8
0.6
0.4
0.2
LISP
PSM
OnDemand
nonPSM
End-to-End Delay (H=4)
0
0 1 2 3 4
λ (packets/BI)
5 6 7 8
(a) (b)
Normalized Throughput (%)
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
Normalized Throughput (H=4)
LISP
PSM
OnDemand
nonPSM
0
0 1 2 3 4
λ (packets/BI)
5 6 7 8
achieves the highest energy efficiency. This
trend can be observed more clearly from Fig.
5(d). When k < 2 packets/BI, LISP has the lowest
duty cycle ratio. As k increases, the pipeline
effect becomes more manifest, which benefits
both PSM and LISP. However, LISP attempts
to keep every node en route awake in a BI in
the presence of traffic; while PSM tends to pile
up packets at a node and to forward them in
the consecutive BI. As a result, LISP carries
traffic more smoothly, but incurs more duty
cycles in this case. When k exceeds the network
capacity, in this case, 3 packets/BI, all the PSMbased
mechanisms consume more energy than
nonPSM to deliver a unit of data. This is largely
due to two facts: first, all the PSM-based mech-
C. Hu, J.C. Hou / Ad Hoc Networks 3 (2005) 529–545 539
(c) (d)
Energy Efficiency (KBytes/J)
Duty Cycle Ratio (%)
70
60
50
40
30
20
10
Energy Efficiency (H=4)
LISP
PSM
OnDemand
nonPSM
0
0 1 2 3 4
λ (packets/BI)
5 6 7 8
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
Duty Cycle Ratio (H=4)
LISP
PSM
OnDemand
nonPSM
0
0 1 2 3 4
λ (packets/BI)
5 6 7 8
Fig. 5. Simulation I: effect of traffic load in a tandem topology: 1 ! 2 ! !5.
anisms devote a fraction of bandwidth to the
ATIM window and thus have less capacity compared
to IEEE 802.11 without PSM; second, the
activities performed in the ATIM windows by
the PSM-based mechanisms (e.g., beacon messages)
consume extra energy.
3. LISP does not make any negative impact on the
throughput before the network capacity is fully
utilized. As shown in Fig. 5(c), all the three
PSM-based mechanisms maintain a 100%
packet delivery ratio as long as the network is
not overloaded. However, when the network is
overloaded, all the three PSM-based mechanisms
drops more packets than IEEE 802.11
without PSM. A similar trend has been
observed in the other scenarios with different
540 C. Hu, J.C. Hou / Ad Hoc Networks 3 (2005) 529–545
numbers of hops and different ATIM window
sizes. In the scenario presented in Fig. 5(c)
(H = 4), LISP drops more packets than the
other two PSM-based mechanisms, while in
the scenarios with fewer numbers of hops, LISP
drops comparably less packets. This indicates
that under heavy traffic load the prediction
chain may not be built well for longer routes,
and more pseudo-ACKs needed for longer
routes may lead to more serious congestion in
the ATIM windows.
4. The on-demand power management mechanism
yields similar performance as IEEE 802.11 without
PSM. In the on-demand mechanism all the
nodes en route are kept awake throughout the
simulation run once the connection commences.
This is because on-demand essentially operates
by keeping a node in the active mode for a
pre-determined interval upon receipt of packets
(upon detection of communications activities).
When packet inter-arrival time is smaller than
the pre-specified timeout values, all the nodes
en route will keep awake. As all the nodes in
the tandem wireless network are en route, the
performance of on-demand is almost the same
as that of IEEE 802.11 without PSM. In some
sense, the on-demand mechanism makes its prediction
on incoming traffic at a coarse granularity
(i.e., at the connection level). In contrast,
LISP makes the prediction at a finer granularity,
is thus able to profile the traffic closely at
the packet level 2 and utilizes the energy truly
‘‘on demand’’.
5.1.2. Effect of number of hops
Fig. 6 gives the performance of the various
mechanisms as the number of hops H increases
from 1 to 7 under relative low traffic load k = 0.3
packet/BI. The normalized throughput is not
shown as all the mechanisms achieve 100% at this
traffic load. We also validate our analysis on the
end-to-end delay and duty cycle ratio under LISP
2 To be precise, LISP operates at the packet or beaconinterval
level, depending on whether the inter-packet time or BI
is larger.
and PSM (Section 4) in this set of scenarios. The
key observation is that, the end-to-end delay of
PSM increases approximately linearly as the number
of hops increases while that of LISP remains
constantly at approximately one BI. Moreover,
as demonstrated in Fig. 6(b), LISP achieves the
highest energy efficiency. Note that the fact that
more nodes are en route results in the decrease in
energy efficiency under all mechanisms.
5.1.3. Effect of ATIM window size
The ATIM window size can affect both network
capacity and energy saving profoundly. A large
ATIM window size can accommodate more
ATIM_ACK exchanges but provides less available
data bandwidth. It also incurs energy consumption
even in the absence of any traffic. As a result, a
large ATIM window size helps in scenarios where
a large number of inter-weaving connections are
present but the aggregate traffic load is not heavy.
The ATIM window affect the end-to-end delay
as well, though not very significantly especially
when the network is not overloaded. It is also of
interest that LISP may be more sensitive to the
ATIM window size because it takes time for the
prediction chain to finish within the ATIM windows.
To investigate all these effects, we vary the
ATIM window size TATIM in [10,40] ms and compare
the performance of the various mechanisms
in the same tandem topology: 1 ! 2 ! !
(H + 1).
Fig. 7 gives the performance of the various
mechanisms in the tandem network of 4 hops
(H = 4) with traffic load k = 0.3. The results are
consistent with our analysis. As the ATIM window
size increases, the end-to-end delay under PSM
and LISP does not monotonically increase or decrease,
while that under the on-demand mechanism
monotonically increases. This is because the
ATIM window size does not play two counteracting
effects in the on-demand mechanism as it does
in PSM and LISP. The end-to-end delay increases
as the ATIM window size increases in the ondemand
mechanism simply because nodes have to
wait more time to resume forwarding until the
ATIM window ends. Under all mechanisms, the
energy efficiency decreases as the ATIM window
size increases.
End-to-End delay (sec.)
0.7
0.6
0.5
0.4
0.3
0.2
0.1
End-to-End Delay (λ=0.3)
LISP
PSM
OnDemand
nonPSM
LISP(analytical)
PSM(analytical)
0
1 2 3 4
H: Number of Hops
5 6 7
Fig. 8 depicts the network capacity achieved as
the ATIM window size increases (H = 1 in (a) and
H = 4 (b)), where the network capacity, kc, is defined
as the traffic rate above which more than
1% packets will be dropped. The curve marked
as ‘‘estimation’’ is obtained by scaling down the
network capacity under IEEE 802.11 without
PSM by a factor of (1 TATIM/BI). The results
show that the ATIM window size is a predominant
factor that scales down the network capacity under
PSM-based mechanisms. This is particularly obvious
in the case of a single hop (Fig. 8(a)). In the
presence of multiple hops, a small ATIM window
size leads to more collisions of ATIM_ACK exchanges
and further reduces the capacity, even
though the available data bandwidth is more than
that with a larger ATIM window size. It is observed
that the ATIM window size does not affect
the capacity under LISP significantly (compared to
C. Hu, J.C. Hou / Ad Hoc Networks 3 (2005) 529–545 541
(a) (b)
Duty Cycle Ratio (%)
(c)
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
Energy Efficiency (KBytes/J)
0
1 2 3 4
H: Number of Hops
5 6 7
30
25
20
15
10
5
Duty Cycle Ratio (λ=0.3)
LISP
PSM
OnDemand
nonPSM
LISP(analytical)
PSM(analytical)
Energy Efficiency (λ=0.3)
LISP
PSM
OnDemand
nonPSM
0
1 2 3 4
H: Number of Hops
5 6 7
Fig. 6. Simulation II: effect of number of hops in a tandem topology: 1 ! 2 ! !(H + 1). k = 0.3 packet/BI, or 24kbps.
PSM), except when the ATIM window size is so
small that the predication chain cannot be completed
in an ATIM window (Fig. 8(b),
TATIM = 10).
5.1.4. Effect of packet size
All the simulation results presented so far are
obtained with the packet size set to 1000bytes.
We have also carried out simulation with the
packet size set to 512bytes and observed similar
performance trends.
5.1.5. Summary
In summary, in the simulation study we have
observed:
1. The wake-up latency is the dominant factor that
increases the end-to-end delay of IEEE 802.11
PSM as compared to IEEE 802.11 without
542 C. Hu, J.C. Hou / Ad Hoc Networks 3 (2005) 529–545
End-to-End delay (sec.)
0.45
0.4
0.35
0.3
0.25
0.2
0.15
0.1
0.05
End-to-End Delay (λ=0.3, H=4)
0
10 15 20 25 30 35 40
T ATIM
LISP
PSM
OnDemand
nonPSM
(a) (b)
Duty Cycle Ratio (%)
(c)
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
Energy Efficiency (KBytes/J)
0
10 15 20 25 30 35 40
12
11
10
Duty Cycle Ratio (λ=0.3, H=4)
T ATIM
9
8
7
6
Energy Efficiency (λ=0.3, H=4)
5
10 15 20 25 30 35 40
LISP
PSM
OnDemand
nonPSM
T ATIM
LISP
PSM
OnDemand
nonPSM
Fig. 7. Simulation III: effect of the ATIM window size in a tandem topology: 1 ! 2 ! !5. k = 0.3 packet/BI.
λ c (packets/BI)
20
18
16
14
12
Network Capacity λ c (H=1)
10
10 15 20 25 30 35 40
T ATIM
PSM(LISP)
OnDemand
nonPSM
Estimation
(a) (b)
λ c (packets/BI)
5
4.5
4
3.5
3
2.5
Network Capacity λ c (H=4)
2
10 15 20 25 30 35 40
T ATIM
LISP
PSM
OnDemand
nonPSM
Estimation
Fig. 8. Simulation IV: effect of the ATIM window size in a tandem topology: 1 ! 2 ! !H +1.
PSM. Under PSM, when the network is not
overloaded, the end-to-end delay is at the scale
of BI times the number of hops.
2. The ATIM window is the dominant factor that
scales down the network capacity under all the
PSM-based mechanisms.
3. LISP can reduce the end-to-end delay of PSM
to approximately one BI, by predicting traffic
at the granularity of packets. Moreover, LISP
also achieves higher energy efficiency than
PSM at low to moderate traffic loads. This performance
gain is not so significant at heavy traffic
loads, but the energy efficiency achieved
under LISP is still higher than that under IEEE
802.11 without PSM till the network capacity is
reached. As compared to PSM, LISP makes a
slightly negative impact on the network capacity
in the case of small ATIM window sizes.
4. The on-demand mechanism performs similarly
to IEEE 802.11 without PSM in networks in
which all nodes are en route. As long as traffic
is present, the on-demand mechanism tends to
keep all the nodes en route awake. Thus it
trades off energy saving of nodes en route for
better performance, even if the traffic load is
light. In contrast, LISP makes the prediction
on incoming traffic at a finer granularity, is thus
able to profile the traffic closely at the packet
level and utilizes the energy truly ‘‘on demand’’.
End-to-end delay (sec.)
0.8
0.6
0.4
0.2
LISP
PSM
nonPSM
Ondemand
C. Hu, J.C. Hou / Ad Hoc Networks 3 (2005) 529–545 543
End-to-End Delay
0
1 2 3 4 5
(a) C: Number of connections
(b)
Energy Efficiency ((KBytes/J)
5.2. Performance under a general scenario
Now we evaluate the performance of LISP and
the other mechanisms in a more complex network
with multiple connections. A total of 50 nodes
are distributed in a plane of 1000m · 1000m. C
connections are established, each carrying CBR
traffic of rate k = 0.3 packet/BI, or 24Kbps, where
C varies from 1 to 5. To ensure each connection
traverses multiple hops, we deploy the first 10
nodes, n2i and n2i+1, at position (50,200 + i * 150)
and (950,200 + i * 150), respectively, where i =0,
1,...,4. The source and destination nodes of the
ith connection are n 2i and n 2i+1, respectively. The
rest 40 nodes are uniformly distributed in the plane.
Fig. 9 depicts the simulation results of the endto-end
delay and the energy efficiency under this
scenario. As the packet delivery ratio is very close
to 100% (>99%) under all the mechanisms, the corresponding
results are not shown. Several observations
have been made:
1. The end-to-end packet delay under LISP is
approximately one BI in the case of C =1,
and increases to nearly 2 BIs as the number of
connections C increases. This demonstrates that
as the number of interfering connections and
active nodes increases, it is more difficult for
LISP to build the prediction chain or make
6
5
4
3
2
1
LISP
PSM
nonPSM
Ondemand
Energy Efficiency
0
1 2 3 4 5
C: Number of connections
Fig. 9. Simulation V: 50 nodes are distributed in a plane of 1000m · 1000m. C connections are established, each carrying CBR traffic
with k = 0.3 packet/BI.
544 C. Hu, J.C. Hou / Ad Hoc Networks 3 (2005) 529–545
correct prediction. However, the end-to-end
delay under PSM is still 2.8–4.0 times of that
under LISP.
2. LISP achieves the highest energy efficiency
among all the mechanisms—as large as 6%,
40% and 178% higher than that of PSM,
on-demand and IEEE 802.11 without PSM,
respectively. The on-demand mechanism achieves
higher energy efficiency than IEEE 802.11
without PSM because only nodes en route stay
awake throughout the duration of connections.
Therefore, the energy efficiency achieved by
on-demand is between those achieved by PSM
and by IEEE 802.11 without PSM.
6. Conclusion and future work
In this paper, we have proposed a novel extension,
called LISP, to IEEE 802.11 PSM. In PSM
the wake-up latency is a predominant factor that
degrades the performance in terms of the end-toend
delay. By exploiting the inherent correlation
between ATIM_ACK packets and incoming traffic,
LISP enables nodes to predict in which BIs
packets will potentially arrive. Only in those BIs
will nodes switch to the temporary active mode
to receive and forward packets. In this manner,
the wake-up latency is reduced, while a ‘‘freeway’’
is built on-demand to transport packets without
incurring excessive duty cycles.
We have conducted analytical and simulation
studies. In particular, we have investigated in the
simulation study the impacts of traffic load, number
of hops (of routes on which connections traverse),
ATIM window size and packet size on the
performance of LISP and the other PSM-based
mechanisms in a tandem network. The results show
that LISP significantly reduces the end-to-end delay
over PSM and its performance is less susceptible
to the number of hops; and that LISP conserves
more energy at low and moderate traffic loads as
compared to IEEE 802.11 without PSM before
the network capacity is reached. In a more general
network with random topology, LISP achieves a
performance improvement of 65–75% over IEEE
802.11 PSM with respect to the end-to-end delay,
and 6% and 178% over IEEE 802.11 with and without
PSM with respect to energy efficiency.
LISP, however, has its limitations. First, the
first packet of each connection is still susceptible
to the wake-up latency, because LISP has to go
through the learning phase. Second, the performance
of LISP degrades at heavy traffic loads and/
or presence of multiple connections. This is, in
part, due to the fact that LISP indexes the prediction
state by link. Without the connection information,
a node may fail to distinguish traffic
indicators for one connection from those for the
others. Collisions of pseudo-ACK packets in the
case of heavy traffic loads also contribute to
the performance degradation. Also, as indicated
in the simulation study, the ATIM window is a
predominant factor that reduces the network
capacity under PSM-based mechanisms (including
LISP). All the observations enlighten us to consider
several possible extensions to LISP, e.g.,
how to incorporate more complicated and yet
feasible statistical approaches to make traffic
prediction, and how to combine LISP with loadbalanced
routing to achieve better overall performance.
These constitute our future work, and
will be reported in fore-coming manuscripts.
References
[1] IEEE 802.11, Wireless LAN Medium Access Control
(MAC) and Physical Layer (PHY) Specification, 1999.
[2] B. Chen, K. Jamieson, H. Balakrishnan, R. Morris, Span:
an energy-efficient coordination algorithm for topology
maintenance in ad hoc wireless networks, IEEE MOBI-
COM, 2001.
[3] L.M. Feeney, M. Nilsson, Investigating the energy consumption
of a wireless network interface in an ad hoc
networking environment, IEEE INFOCOM, April 2001.
[4] C. Hu, J. Hou, A link-indexed statistical traffic prediction
approach to improving IEEE 802.11 PSM, Technical
Report, 2004, http://lion.cs.uiuc.edu/~chunyuhu/publications/lisp-rep-v0.pdf.
[5] E.-S. Jung, N.H. Vaidya, An energy efficient MAC
protocol for wireless LANs, IEEE INFOCOM, June 2002.
[6] N. Li, C.-J. Hou, L. Sha, Design and analysis of an MSTbased
topology control algorithm, IEEE INFOCOM,
April 2003.
[7] J. Monks, V. Bharghavan, W.-M. Hwu, A power controlled
multiple access protocol for wireless packet networks,
IEEE INFOCOM, March 2001.
[8] V. Rodoplu, T.H.-Y. Meng, Minimum energy mobile
wireless networks, IEEE Personal Communications Magazine
22 (April) (1999) 46–55.
[9] C. Schugers, V. Tsiatsis, S. Ganeriwal, M. Srivastava,
Topology management for sensor networks: exploiting
latency and density, IEEE MOBICOM, 2002.
[10] S. Singh, M. Woo, C. Raghavendra, Power aware routing
in mobile ad hoc networks, IEEE MOBICOM, 1998.
[11] Y.-C. Tseng, C.-S. Hsu, T.-Y. Hsieh, Power-saving protocols
for IEEE802.11-based multi-hop ad hoc networks,
IEEE INFOCOM, June 2002.
[12] H. Woesner, J.-P. Ebert, M. Schlager, A. Wolisz, Powersaving
mechanisms in emerging standards for wireless
LANs: the MAC level perspective, IEEE Personal Communications,
June 1998.
[13] Y. Xu, J. Heidemann, D. Estrin, Geography-informed
energy conservation for ad hoc routing, IEEE MOBICOM,
July 2001.
[14] W. Ye, J. Heidemann, D. Estrin, An energy-efficient MAC
protocol for wireless sensor networks, in: Proc. of the 21st
Annual Joint Conference of the IEEE Computer and
Communications Societies, 2002.
[15] R. Zheng, R. Kravets, On-demand power management for
ad hoc networks, IEEE INFOCOM, April 2003.
[16] http://www.pdos.lcs.mit.edu/benjie/span/span_ns.html.
C. Hu, J.C. Hou / Ad Hoc Networks 3 (2005) 529–545 545
Chunyu Hu is currently a Ph.D. student
of the Department of Electrical
and Computer Engineering at the
University of Illinois at Urbana-
Champaign. She received her B.S. and
Master degrees in Automatic Control
both from the University of Science
and Technology of China, in 1997
and 2000, respectively. Her current
research interest focuses on wireless
networks, including power management,
the interference problem and the
broadcast storm problem.
Jennifer C. Hou is currently an associate
professor of the Department of
Computer Science at the University of
Illinois at Urbana-Champaign. She
received her B.S.E. degree in Electrical
Engineering from National Taiwan
University in 1987, M.S.E. degrees in
EECS and in I&OE from the University
of Michigan, Ann Arbor in 1989
and 1991, and Ph.D. degree in EECS
also from the University of Michigan,
Ann Arbor. Her current research
covers QoS, network measurement
and diagnostics, wireless network and wireless sensor networks,
etc.
