Digital Signal Processing Reference
In-Depth Information
Fig. 5.4
Local optima cause
very large delays. Cooling
down in a local optimum
causes a disjunction between
two sets of terminals that
have converged on different
channels. Any packet
generated on the left-hand
side will never reach the sink
used to increase convergence speed or performance while converging. It is used to
increase the performance of the steady-state result.
As in Sect.
5.5
, we first consider a reward-based exploration instantiation of sim-
ulated annealing. In Sect.
5.6.3.2
, we then explain the obstacles faced when design-
ing a cooling scheme. Section
5.6.3.3
then explains how we have overcome these
obstacles using a scenario-based framework, as the one presented in Chap. 3.
5.6.3.1 Reward-Based (RB) Exploration
In this section, the temperature,
T
, is kept constant and we do not define a cooling
scheme. Hence, the rate of exploration is only altered through the reward,
R
(k
w
.If
the reward of the current state is high, less exploration is allowed. However, since no
cooling scheme is defined, we will never eliminate exploring and terminals can still
jump out of the optimal solution once in a while. We have observed that this effect
actually can strongly reduce the efficiency (delay) in the steady-state. It is therefore
necessary to find a cooling scheme.
5.6.3.2 Finding a Cooling Scheme
Finding a proper cooling scheme is a difficult task. If we just anneal and gradually
drop the temperature to 0 K, we risk getting stuck in local optimum or are not able
to adapt to the time-varying IEEE 802.11 interference. In many problems a trade-
off is made between the speed of convergence and attaining the global optimum.
However, the local optima of our derived problem are extremely suboptimal in the
original problem statement (see Sect.
5.4
)!
In Fig.
5.4
we illustrate this: a local optimum for the approximated goal destroys
every opportunity to get the packet to the sink. Though exploring terminals might
be able to bridge the packet over the boundary, a system that has been cooled down
cannot (as no exploration is anymore allowed). Therefore reaching an optimal so-
lution can not be traded off with convergence speed. This makes the selection of a
proper cooling scheme (if there is any at all) very difficult and we have to make for
each scenario a very wise choice of all parameters involved. Even then, it can still
happen that we get stuck in a local optimum. In the next section, we will discuss how
we can use the framework presented in Chap. 3 to design a more robust algorithm.
