Free University Brussels, 1999
Thesis name: Adaptive packet routing in mobile ad hoc networks
Adaptief routeren van pakketten in mobiele ad hoc netwerken met behulp van reinforcement learning. Kris Melotte.
Promotor: Bernard Manderick
Mobile ad hoc networks are characterized by multi-hop wireless links, absence of any cellular
infrastructure, and frequent host mobility. Design of efficient routing protocols in such networks is a
Recently, reinforcement learning techniques based on Q-learning received much interest for adaptive
packet routing in static networks. In this thesis, these techniques are examined, tested and evaluated
for routing purposes in mobile ad hoc networks. Two problems are encountered: Firstly and most
important, the inability of Q-Routing and its derivatives to revert back to the original routing policy
when the network topology is restored after a change in topology (also referred to as the hysteresis
problem). Secondly, the speed of adaptation due to a change in network topology is too slow.
Therefore two enhancements for the Q-Routing framework are proposed. The former problem is
solved by a simple trick, which results in the exploration of a link that is restored again after being
removed. This trick also causes the routing algorithm to explore a link that becomes available for the
first time during the operation of a mobile ad hoc network. The speed of adaptation of the routing
policy to a change in network state is improved by adding a planning technique called prioritized
sweeping to the Q-Routing framework. This planning technique tries to build a model of the
environment from past experiences. This model is used to propagate network state changes faster
throughout the network. To enhance the Q-Routing framework with this planning technique,
additional control packets were needed. The effects of these adaptations are experimentally examined.
The resulting routing algorithm is evaluated against parameters that are crucial for mobile ad hoc
networks such as the mobility factor and the offered network load. The results show that algorithms
based on Q-Routing should be able to route packets in a mobile network under certain circumstances.
Keywords: reinforcement learning, network routing, mobile ad hoc networks, mobility, Q-Routing,
prioritized sweeping, hysteresis problem, adaptive routing.
Download the pdf
mail: kris dot melotte at telenet dot be