Digital Signal Processing Reference
In-Depth Information
5.6.3.3 Adaptive Simulated Annealing
The high-level idea of our approach is similar to Adaptive Simulated Annealing
(ASA). As discussed, removing exploration increases the chance of being stuck in a
local optimum. Furthermore, it removes the ability of the framework to respond to
dynamism.
However, a first scenario that we consider is the appearance of IEEE 802.11
interference on the current channel. When such interference is detected, the explo-
ration is reinitialized, i.e., we reinitialize the temperature. As communication is no
longer possible under IEEE 802.11 interference, this can be easily detected. Further-
more, when the environment suddenly changes, e.g., lots of neighbors disappear,
one should also re-initialize the temperature. This allows the framework to perform
optimally, while still being able to respond to the environment dynamism.
As mentioned in Sect.
5.6.3.2
, we also need to protect the network against local
optima. Our approach is rather similar to what we described above. Again, we try
to detect if we are in a local optimum and increase exploration rate around the
boundary. Hence, we see convergence centers created at the boundaries that ripple
through the entire network chain. It is only when the different converged regions
will agree on the channel that exploration is completely given up.
The detection algorithm now is not so easy anymore as in the interference case.
As mentioned above, we have to rely on routing information. As it is known to the
terminals whether other terminals are further or closer to the sink (in the routing
table), we can use this information to detect boundaries. At a boundary a terminal
will see a lot of terminals either closer to the sink or farther from the sink. If a
boundary is detected, the boundary algorithm is initialized. It should be noted that
the detection algorithm is only executed when the terminals have cooled down (after
they have spent more than
x
iterations on a temperature lower than
T
c
). Otherwise,
this detection algorithm would make a decision too quickly. This would interfere
with the AR algorithm and can cause non-convergence.
We will now detail the boundary algorithm. The boundary terminals re-initialize
the temperature, going for heavy exploration. Furthermore, boundary terminals are
not allowed to re-enter the previous channel for some time. The boundary algorithm
is hence a complete exploration phase. There are two possibilities:
•
One side of the boundary has been quicker to converge. They will detect the
boundary sooner and begin exploration. As a result, they will go looking for the
terminals on the other side of the boundary. If they find the other terminals, new
boundary terminals are formed in the quicker converged center. These terminals
will then go to the same channel as the previous terminals and, hence, one side of
the boundary adopts the channel of the other (1-sided ripple).
•
Both sides of the boundary detect the boundary at almost the same time. The
boundary terminals will converge on a third channel. At both sides new boundary
terminals are formed and the new channel is rippled through both convergence
centers (2-sided ripple).
