Reinforcement Learning


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

Abstract: 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 challenging issue.
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