Self-Organized Routing in Mobile Ad Hoc Networks using SAMPLE

by Jim Dowling and Stefan Weber

In the SAMPLE project, we are investigating decentralized collaborative learning techniques to develop a routing protocol for Mobile Ad Hoc Networks, where routing agents collectively learn to exploit stable routing paths in the network environment. This approach to routing lends itself to large-scale ubiquitous computing scenarios, in which large numbers of ubiquitous mobile devices are intermixed with static infrastructure networks.

Mobile Ad Hoc Networks (MANETs) are a promising area of application for emergent computing techniques. Traditional distributed-systems techniques based on strong consensus and global knowledge are breaking down due to the decentralization and dynamism inherent in these environments. Current approaches to routing in these environments see individual MANETs as separate from existing infrastructure, and view the network nodes as homogeneous. However, wireless infrastructures are increasingly considered to be a community service (also called muni-wireless networks) that should be provided by local authorities. Mobile devices in these environments exhibit various levels of processing power, mobility and connectivity, but existing approaches do not consider these characteristics. In the SAMPLE project, we are developing a routing protocol for metropolitan area MANETs. In these networks, mobile nodes collectively learn and self-organize to exploit any fixed or temporary network infrastructure in the environment.

The SAMPLE project is concerned with developing a MANET routing protocol for WiFi-enabled computing devices such as laptops, smart mobile phones and handheld devices. In MANET routing protocols, computing devices, also called nodes, act as both consumers and providers of the routing services in the network. In particular, we have been investigating how nodes can collectively determine the stability and quality of network links in the system. This ability is particularly beneficial in the presence of a wireless infrastructure, as nodes learn to route over the higher-performance stable paths in the infrastructure to access popular services such as e-mail and the Web.

The design of the SAMPLE protocol is based on collaborative reinforcement learning (CRL), an unsupervised learning algorithm that enables groups of reinforcement learning agents to solve system online optimization problems. CRL provides feedback models that map changes in an agent's environment and its neighbours onto internal changes in the agent's policy, using distributed model-based reinforcement learning. Positive and negative feedback are the key mechanisms that adapt an agent's behaviour to both its neighbours and a changing environment. In SAMPLE, routing agents use CRL to explore their local environment by executing routing actions, and provide one another with feedback on the state of routes and network links. Using CRL, agents adapt their behaviour in a changing environment to meet system optimization goals while using only local state information.

SAMPLE has been implemented in the NS-2 simulator, and the results have been very encouraging. Simulations show how feedback in the selection of links by routing agents enables them to self-organize in varying network conditions and properties, resulting in the optimization of network throughput. In experiments, emergent properties such as traffic flows that exploit stable routes and re-route around areas of wireless interference or congestion have been demonstrated. As such, SAMPLE is an example of a complex adaptive distributed system.

Figure 1: Components of a wireless node and the installation of these nodes in the WAND testbed.

We are now moving to the deployment phase of the project, in which the protocol will be tested on a real-world testbed. The Wireless Area Network for Dublin (WAND), which we have deployed in the centre of Dublin city, is a testbed infrastructure covering a 1.5km route from Trinity College to Christchurch Cathedral. It allows experimentation on both protocols and applications for MANETs in a metropolitan area. An initial implementation of the protocol has been developed for Linux and experiments will establish its performance in a real-world wireless network.

As part of the project, we are also investigating the use of SAMPLE for carrying different types of traffic in MANETs, such as data and voice traffic. The development of a protocol to carry voice traffic over muni-wireless networks would allow the provision of free voice calls, something currently only available on the Internet. However, to achieve this goal, self-organized routing techniques will be required for dynamic networks where topology, resources and node availability are subject to frequent and unpredictable change.

Our research is conducted as part of the CARMEN project, which is funded until 2006 by the Higher Education Authority (HEA) of Ireland.

Links:
SAMPLE website: http://www.dsg.cs.tcd.ie/sites/SAMPLE.html
WAND website: http://www.dsg.cs.tcd.ie/sites/WAND.html

Please contact:
Jim Dowling
E-mail: jimjimdowling.info

Stefan Weber, Trinity College Dublin, Ireland
Tel: +353 1 608 8423
E-mail: stefan.webercs.tcd.ie