Emergent Dynamic Routing Using Intelligent Agents in Mobile Computing
Florin LEON, Mihai Horia ZAHARIA, Dan GÂLEA
“Gh. Asachi” Technical University of Iaşi
Faculty of Computer Science and Engineering
Abstract: Routing begins to have an important place in the context of high performance distributed systems, with an increasingly notable influence on the overall performance of the system under analysis. While many global algorithms have been proposed for the routing problem, in this paper we demonstrate how a relatively simple agent-based approach, based on ideas inspired from complex systems and reinforcement learning, can generate a highly complex set of local interactions between individual agents, whose emergent behaviour results in the desired routing effect.
Keywords: Emergence, routing, intelligent agents, mobile computing.
Florin Leon holds a PhD in Computer Science and is presently a Lecturer in the Department of Computer Science and Engineering of the “Gh. Asachi” Technical University of Iaşi. His main research interests are: artificial intelligence, simulations using intelligent agents, and data mining. He is the author or co-author of 7 books and over 50 articles.
Mihai Horia Zaharia is an Associate Professor in the Department of Computer Science and Engineering of the “Gh. Asachi” Technical University of Iaşi and has a PhD in distributed systems. His main research areas are: distributed computing, distributed artificial intelligence, knowledge-based geographical systems, computer systems security, and computer architectures. He is the author or co-author of 9 books and over 40 articles.
Dan Gâlea is a Professor in the Department of Computer Science and Engineering of the “Gh. Asachi” Technical University of Iaşi, and a PhD Supervisor. His main research areas are: artificial intelligence, knowledge-based geographical systems, image processing, and natural language processing. He is the author or co-author of 10 books and over 100 articles.
CITE THIS PAPER AS:
Florin LEON, Mihai Horia ZAHARIA, Dan GÂLEA, Emergent Dynamic Routing Using Intelligent Agents in Mobile Computing, Studies in Informatics and Control, ISSN 1220-1766, vol. 17 (2), pp. 215-224, 2008.
Nowadays, one of the important problems of information and communications technology is related to re-designing interactions between isolated computing elements in order to create large, powerful, and fault tolerant distributed systems. There are already many approaches that try to solve this problem, from e-government to virtual universities and organizations, peer to peer communities, GRID computing, and e-science computing. If the approaches offered by the traditional engineering cannot keep up with this convergence, those conglomerates of computing power can create many problems due to an inherent instability and mostly to their non-predictive behaviour if some limits are reached. The analysis of the natural complex systems leads us to alternative approaches. The examples under scrutiny refer to animal brain, immunity systems, ants colonies, and so on. All these examples have powerful, complex, aggregated behaviours obtained from the combination and interactions of simple elements or individuals. As a result, this kind of problem solving techniques begins to be used for various specific problems.
Distributed systems are usually analyzed from the points of view of load balancing, geographical distribution of the control, and databases. In most models, the communications are presumed to be very good and fault tolerant. Most of the time, these attributes are valuable but in some cases there are serious quality of service degradation at the communication line hot spots where bottlenecks appear due to the used routing algorithms. Therefore the routing problem begins to have equal importance with the previously mentioned basic characteristics of distributed systems.
In this paper a distributed framework based on intelligent agents was used to propose and test a new approach in routing for mobile devices. According to Wooldridge (2000), an agent is a computer system that is situated in its environment and is capable of autonomous action in order to meet its design objectives. Agent Oriented Programming, AOP, is a fairly new programming paradigm that supports a societal view of computation.
In AOP, objects known as agents interact to achieve individual goals. Agents can exist in a structure as complex as a global internet or one as simple as a module of a common program. Agents can be autonomous entities, deciding their next step without the interference of a user, or they can be controllable, serving as an intermediary between the user and another agent.
Intelligent agents retain the properties of autonomous agents, and in addition show a so called “flexible” behaviour (Wooldridge & Jennings, 1995): reactivity (the ability to perceive their environment, and respond in a timely fashion to changes that occur in it), pro-activeness (the ability to exhibit goal-directed behaviour by taking the initiative), and social ability (to interact with other agents and possibly humans).
In this paper we described a system of autonomous agents, in the sense that each agent decides its actions based on its internal state and the state of the environment, without an explicit external command, other that the task to be executed, which is the actual goal of the agent. However, the autonomy is not incompatible to the global order. The system manifests a form of self-organization, resulting in the routing behaviour of the multiagent system as a whole. The proposed emergent routing algorithm has a dual effect. An agent discovers the routes but also uses the previous information about the routes stored by the previous agents that have already travelled through the local neighbourhood of a server. Since the agent-based approaches are scalable and robust by nature, the research can be continued in the future by considering a larger number of servers and agents, which will allow the study of the real life problems on massive infrastructures, such as the GSM internet servers.
- Carrillo, L., Marzo J. L., Vilà P., Mantilla C., MAntS-Hoc: A Multi-agent Ant-based System for Routing in Mobile Ad Hoc Networks, http://eia.udg.es/~lilianac/publications/ ccia04_Liliana-Final2.pdf, 2004.
- Das, S., Perkins C., Royer E., Ad Hoc on Demand Distance Vector (AODV) Routing, Internet Draft, draft-ietf-manetaodv-11.txt, 2002.
- Hass, Z. J., Pearlman R., Zone Routing Protocol for Ad-hoc Networks, IETF MANET Internet Draft, 2002.
- Johnson, D. B., Maltz D. A., The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks, Internet Draft, draft-ietf-manet-dsr-07.txt, 2002.
- Johnson, D., Perkins C., Arkko J., RFC 3775, Mobility Support in IPv6, The Internet Society, http://tools.ietf.org/html/rfc3775, 2004.
- Marwaha, S., Tham C. K., Srinivasan D., A Novel Routing Protocol Using Mobile Agents And Reactive Route Discovery For Ad Hoc Wireless Netwokrs, www.ece.nus.edu.sg/stfpage/eletck/ papers/ShivaICON_conf8a51.pdf, 2005.
- Murthy, S., Garcia-Luna-Aceves J. J., A Routing Protocol for Packet Radio Networks, ACM/IEEE Proc. of the 1st. Annual International Conference on Mobile Computing and Networking, Berkeley, CA, 1995, pp. 86-95.
- Nikaein, N., Laboid H., Bonnet C., Distributed Dynamic Routing Algorithm (ddr) for Mobile Ad Hoc Networks, Proceedings of the MobiHOC 2000: 1st. Annual Workshop on Mobile Ad Hoc Networking and Computing, 2000.
- Perkins, C. E., Watson T. J., Highly Dynamic Destination Sequenced Distance Vector Routing (DSDV) for Mobile Computers, ACM Proc. of SIGCOMM_94 Conference on Communications Architectures, London, UK, 1994.
- Perkins, C., RFC 3344, IP Mobility Support for IPv4, The Internet Society, http://tools.ietf.org/html/rfc3344, 2002.
- Wooldridge, M., Intelligent Agents, in G. Weiß (ed.), Multiagent Systems – A Modern Approach to Distributed Artificial Intelligence, The MIT Press, Cambridge, Massachusetts, 2000.
- Wooldridge, M., Jennings N. R., Intelligent Agents: Theory and Practice, The Knowledge Engineering Review, Vol. 10(2), 1995, pp. 115-152.
- Zaharia, M. H., Leon F., System Prototype for the Dynamic Management of Distributed Resources in Mobile Computing Using Intelligent Agents, CNCSIS project code 66/2005, Technical Report, 2006.
- Zaharia, M. H., Leon F., Calistru C. N., Gâlea D., Load Balancing in Heterogeneous Distributed Systems Using Mobile Intelligent Agents, IEEE International Conference on Distributed Human-Machine Sysems, Athens, Greece, 2008.