Optimizing sleeping intervals in preamble
sampling MAC for WSNs
Holger Karl
Universit¨at Paderborn, Computer Networks group
Abstract. Preamble sampling is a popular mechanism in WSN MAC
protocols. This paper optimizes the energy consumption by adjusting the
preamble length to a known or estimated, possibly varying event rate.
1 Introduction
Among the many proposed energy-efficient MAC mechanisms for WSNs, pream-
ble sampling [1] is used in various protocols (WiseMAC [3], B-MAC). The idea
is to have the receiver wake up with a period ∆and check whether there is any
transmission currently ongoing. If so, the receiver stays awake until the start of
the actual packet; else, it immediately goes back to sleep. A transmitter must
ensure that a receiver will actually stay awake before it transmits the packet by
sending a preamble for (at least) a length ∆.
El-Hoiydi [1,2] has analyzed preamble sampling’s delay and throughput, ex-
tending the classical Aloha-type analysis. What is missing is an optimization of
the preamble length for Poissonian event arrivals and an analysis how to adapt
the length to an unknown arrival rate.
This paper is a first step to such an optimization. To keep the analysis
tractable, only the case of a single transmitter/receiver is considered; a multi-
transmitter MAC case is left for future study. For a single transmitter/receiver
pair, the paper analyzes (Section 2) and optimizes (Section 3) the preamble
length ∆for energy consumption and provides a simple-to-use approximation
formula suitable for in-field adaptation; it characterizes the overhead necessary
to adapt to an unknown (Poissonian) arrival rate (Section 4), and it looks at the
overhead caused by Markov-modulated Poisson traffic (Section 5).
2 Analysing energy consumption at given preamble
length ∆
Assume a transmitter with Poisson events of rate λ. The packet duration is TPkt,
the transmission power is fixed at PTX, the power consumed during reception
(of preamble or packet) is PRX. For waking up and checking for a preamble, the
receiver consumes an energy Ewkup. There are two main simplifications here:
First, the CSMA aspect is ignored since there is only a single transmitter; second,
the time needed for detecting preamble/idle channel is assumed to be small to
∆and is thus ignored. Also, the receiver restarts its sleeping/sampling cycle
after a packet has been received (because of Poisson events, assuming that the
statistics of the time to the next event is unchanged is acceptable).
The first step is to find the expected energy consumption as a function of
TPkt,PTX,PRX,Ewkup,λ, and ∆(expectation taken over the random arrival
process). To do so, the distribution of the number of wakeups before detecting
a premable and of the remaining preamble listening time are derived.
2.1 Number of wakeups
Let Xbe a random variable describing the inter-event times (and, thus, roughly
the times between transmissions of a preamble); Xis exponentially distributed
with parameter λand successive Xare independent of each other. Let Zbe a
random variable describing the number of wakeups a receiver executes before
receiving the preamble. The density of Zis:1
P(Z=k) = P(k∆ ⩽X⩽(k+ 1)∆), k ⩾0
=P(X⩽(k+ 1)∆|k∆ ⩽X)P(k∆ ⩽X)
= (1 −P(X⩾(k+ 1)∆|X⩾k∆)) P(X⩾k∆)
= (1 −P(X⩾∆)) P(X⩾k∆) = (1 −e−λ∆)e−kλ∆
Note that from line 3 to 4, the memoryless property of Xis used. Thence:
E[Z] = e−λ∆
1−e−λ∆ (1)
2.2 Time to listen to preamble
Suppose now that the receiver has detected a preamble. How long does it have to
listen to the preamble before the actual packet starts? Let the random variable Y
describe this time. It is easiest analyzed looking at its complementary cumulative
distribution function, again using the memorylessness of Xin the second step
of Equation (2); FXis the cumulative distribution function of X; 0 ⩽y⩽∆.
P(Y⩾y) = P(X > y +k∆|X > k∆ ∧X < (k+ 1)∆) for some k
=P(X > y|X > 0∧X < ∆)
=P(X > y|X < ∆) = P(y < X ∧X < ∆)
P(X < ∆)=FX(∆)−FX(y)
FX(∆).
(2)
Thus, P(Y⩽y) = 1−(1−F(y)/F(∆)) = (1−e−λy)/(1−e−λ∆). Some arithmetic
then yields the expected preamble receive time:
E[Y] = 1
λ−∆e−λ∆
1−e−λ∆ .(3)
1In essence, this derives the known result that an exponential r.v. corresponds to a
geometrically distributed number of fixed time slots.
2.3 Expected energy consumption per MAC interaction
Putting Equations (1) and (3) together gives the expected energy consumption:
E[energy] = (∆+TPkt)PTX +E[Z]Ewkup + (E[Y] + TPkt)PRX
= (∆+TPkt)PTX +e−λ∆
1−e−λ∆ Ewkup + ( 1
λ−∆e−λ∆
1−e−λ∆ +TPkt)PRX.(4)
The term (∆+TPkt)PTX is the transmitter’s energy consumption to transmit
a packet, the term E[Z]Ewkup the energy for the wakeup attempts, and the last
term is the energy to receive the remaining preamble and the actual packet. Any
additional overhead for ACKs or retransmissions is not accounted for.
Figure 1 illustrates Equation (4), using parameters similar to those in refer-
ence [1]; the circles highlight the optimal ∆for a given λ.
0 0.5 1 1.5 2
0
2
4
6
8
10
12
14x 10
-3
Preamble length
Expected energy consumption
lambda = 0.000100
lambda = 0.001000
lambda = 0.010000
lambda = 0.100000
lambda = 1.000000
Increasing
lambda
Fig. 1. Expected energy consumption (in J) for various λ(in 1/seconds) as a function
of ∆(in seconds); PTX =PRX = 5 mW, TPkt = 1 ms, Ewkup = 0.25 µJ
3 Optimize energy consumption in ∆
Choosing an energy-optimal ∆opt is, in principle, easy given Equation (4). An
analytic derivation, however, becomes unwieldy and would hardly be practical to
use on a wireless node at runtime. It is also not necessary. Rather, for given values
of TPkt,PTX,PRX, and Ewkup, a simple approximation of ∆opt as a function of
λcan be derived by regression fitting Equation (4).
As it turns out, the logarithms of λand ∆can be easily fitted using a
quadratic polynomial, shown in Equation (5); ∆findicates the fitted value for
the optimal ∆. (Linear fits are not quite acceptable over a wide range of λ.)
log ∆f=alog2λ+blog λ+c(5)
For the example parameters used in Section 2.3, a=−0.0026, b=−0.5269,
c=−5.0171. The fit for ∆is shown in Figure 2(a), the resulting energy consump-
tion in Figure 2(b). In this example, the largest increase in energy consumption
when using the fitted ∆instead of the optimal computed ∆is about 3.5 %.
10
-10
10
-5
10
0
10
5
10
10
10
-8
10
-6
10
-4
10
-2
10
0
10
2
λ
λλ
λ
Optimal
∆
∆
∆
∆
Computed optimal
∆
∆∆
∆
Fitted
∆
∆∆
∆
(a) Optimal and fitted ∆
10
-10
10
-5
10
0
10
5
10
10
10
-5
10
-4
10
-3
10
-2
10
-1
10
0
λ
λλ
λ
Energy consumption at given
λ
λ
λ
λ
for optimal/fitted choice of
∆
∆
∆
∆
Computed optimal
∆
∆∆
∆
Fitted
∆
∆∆
∆
(b) Energy consumption for opti-
mal and fitted ∆
Fig. 2. Fitted ∆and resulting energy consumption for various λ;PTX =PRX = 5 mW,
TPkt = 1 ms, Ewkup = 0.25 µJ (note double-logarithmic scales)
4 Adapting ∆to an unknown, fixed arrival rate
Using such a regression-based fit, even a sensor node can choose a near-optimal
∆for a given λ. However, λis usually not known. A simple idea is to use observed
interarrival times of events and to estimate the actual λ. A common option would
be to store a few observation and then use a maximum likelihood estimator, but
this needs memory. Alternatively, a simple autoregressive estimation of the mean
arrival time can be attempted: Maintain an estimate λiof the arrival rate after
ievents have been observed, update this estimate using the interarrival time
(IAT) of the i+ 1st event and a constant smoothing factory α∈(0,1).
1/λi+1 =α/λi+ (1 −α)IATi+1 (6)
Assuming an arbitrary, initial arrival rate of, say, λ0= 1, and using the
estimated λito derive ∆from the fitted model, what is then the energy over-
head? First, Figure 3(a) shows the average number of steps to adapt λ, from an
arbitrary start value of 1, using different adaption parameters α.
The energy consumption itself can be obtained by simulation. Assuming a
preamble length ∆and the time to the next event is TTE, then the actually
(not expected) consumed energy is given by Equation (7).
Eactual = (∆+TPkt)PTX +»TTE
∆¼Ewkup +(T TE −∆¹TTE
Ƽ+TPkt)PRX (7)
Thence, the energy consumed when using (clairvoyantly) the correct λto com-
pute ∆or an estimate of λas computed according to Equation (6) can be com-
pared. Figure 3(b) shows this ratio: For a wide range of λ, starting from an inital
estimate of λ= 1 only has a small energy overhead when adapting λand, thus,
∆. Results were obtained using the parameter settings from above, 200 events,
and averaging over 200 independent iterations (clearly, the more steps are used,
the lower the overhead for the initial adaptation becomes – this is addressed in
the following section). Apparently, α= 0.8 seems like a good choice.
-6 -4 -2 0 2 4 6
0
500
1000
1500
log(
λ
λλ
λ
)
Average number of steps
α
αα
α
=0.99
α
αα
α
=0.95
α
αα
α
=0.90
α
αα
α
=0.80
α
αα
α
=0.70
(a) Average number of steps to
adapt estimation of λto within 5 %
of actual value, using different α
10
-5
10
0
10
5
1
1.02
1.04
1.06
1.08
1.1
1.12
λ
λλ
λ
Ratio of energy consumption
between correct and estimated
λ
λ
λ
λ
α
αα
α
=0.95
α
αα
α
=0.9
α
αα
α
=0.8
α
αα
α
=0.7
α
αα
α
=0.6
(b) Ratio of consumed energy
when using estimated λvalues to
compute ∆compared to using cor-
rect ∆
Fig. 3. Adapting ∆to a fixed λ(confidence intervals for confidence level 0.95)
5 Adapting ∆to a Markov-modulated Poisson process
For a WSN MAC, an important function is to be able to change between
“modes”, e.g., “normal” and “alarm”, with severe changes in event arrival rates.
One adequate model is a Markov-modulated Poisson process (MMPP), where a
two-state Markov process represents “normal” and “alarm”; the two associated
Poisson processes have low or high rate. As example, state holding times of 10000
and 1 seconds and corresponding rates of 1/100 and 10 1/s are used; Figure 4(a)
shows a sample path.
0 2 4 6 8 10
x 10
4
0
200
400
600
800
1000
Time (s)
Event number
Normal operation
Alarm state
(a) Example sample path for a
two-state MMPP
10
2
10
3
10
4
0
0.002
0.004
0.006
0.008
0.01
0.012
0.014
Average holding time of the normal state (s)
Average energy consumption per event (J)
∆
∆∆
∆
from perfect
λ
λλ
λ
information
Adapted
∆
∆∆
∆
(
α
αα
α
= 0.8)
(b) Average energy per event
Fig. 4. Adapting ∆to a Markov-modulated Poisson traffic
The average consumed energy is larger when adapting ∆to the observed
IAT values instead of to the correct λ(Figure 4(b)). The apparently comparable
behavior for low holding times is deceptive, caused by fewer messages and more
events per message because of an incorrect ∆(Figure 5(a)). The high energy
consumption of an incorrect ∆is mainly caused by long times spent in sending/
receiving the preamble (Figure 5(b)).
10
2
10
3
10
4
1
1.2
1.4
1.6
1.8
2
Average holding time of the normal state (s)
Average number of events in one message
∆
∆∆
∆
from perfect
λ
λλ
λ
information
Adapted
∆
∆∆
∆
(
α
αα
α
= 0.8)
(a) Average number of events trans-
mitted in a single message
10
2
10
3
10
4
0
0.2
0.4
0.6
0.8
1
Average holding time of the normal state (s)
Average preamble receive time
∆
∆∆
∆
from perfect
λ
λλ
λ
information
Adapted
∆
∆∆
∆
(
α
αα
α
= 0.8)
(b) Average time spent in receiving
the preamble
Fig. 5. Details on protocol behavior
6 Conclusion
To conclude: Optimizing the preamble length to the traffic rate is important for
preamble sampling. For a fixed traffic rate, it is even possible to automatically
adapt without too high an energy penalty. For varying traffic patterns, however,
a self-adapting MAC protocol runs the danger of (a) missing or delaying mes-
sages (when switching to alarm mode) and (b) running at high overhead when
switching back to normal mode. The crucial point is that even though the trans-
mitter might be aware of a change to a high traffic rate, there is no means of
informing the receiver of such a change before the next ∆! A change to a low
rate can be more easily announced to the receiver, assuming the sender has this
knowledge – but this knowledge would have to be present at the last message
sent during the alarm mode, at the high data rate, to give the receiver an indi-
cation to switch to a ∆for lower traffic rates. This might not always be feasible,
either. Hence, additional MAC or cross-layer mechanisms are necessary.
References
1. A. El-Hoiydi. Aloha with preamble sampling for sporadic traffic in ad hoc wireless
sensor networks. In Proc. IEEE Intl. Conf. on Communications (ICC), April 2002.
2. A. El-Hoiydi. Spatial TDMA and CSMA with preamble sampling for low power
ad hoc wireless sensor networks. In Proc. Seventh Intl. Symp. on Computers and
Communications (ISCC’02), page 685, Washington, DC, USA, 2002.
3. A. El-Hoiydi, J.-D. Decotignie, C. Enz, and E. Le Roux. Wisemac, an ultra low
power mac protocol for the wisenet wireless sensor network. In Proc. 1st Intl. Conf.
on Embedded Networked Sensor Systems (SenSys), pages 302–303, November 2003.
