30.3.2007 HIIT seminar

HIIT seminars in spring 2007 will be held in hall **B222** of Exactum,
on Fridays starting at 10:15 a.m. Coffee available from 10.

Fri Mar 30
Petteri Nurmi
Reinforcement learning for routing in ad hoc networks

Abstract:
In communication networks, routing refers to the problem of finding the best path through which to send packets bound for a given destination. The standard solution for routing is to consider the network as a weighted graph and to find the path with the minimum cost in this graph. The weights of the edges are set according to some cost criterion that can consider, e.g., latency, link failures, congestion, and selfishness. However, once we move to decentralized settings, such as ad hoc networks, the optimization needs to be performed locally on each device and the cost of an edge depends on how each node perceives the performance it obtains by using the edge. In ad hoc networks an additional factor that can impact the performance of the nodes, and thus the costs of the edges, is resource constraints and especially energy. In the literature, reinforcement learning has been suggested as a method for estimating the cost of an edge under changing conditions, and using only local information. Existing solutions have been targeted at static communication networks where energy is not an issue. Therefore existing solutions need to be modified before they can be used in ad hoc networks. We show how routing in ad hoc networks can be formulated as a partially observable Markov decision process (POMDP) and propose a method that the nodes can use to learn stochastic policies that map beliefs about local properties of a neighboring node to an estimated cost for an edge.