Sprungmarken

Servicenavigation

Hauptnavigation

Sie sind hier:

Hauptinhalt

Diplomarbeit

Entwicklung einer verteilten Simulationsumgebung zur Analyse dezentraler Routingalgorithmen in dynamischen Verkehrsszenarien

Mario Wündsch

Motivation und Aufgabenbeschreibung

Der im Rahmen der Projektgruppe STOP (PG 502) implementierte Verkehrssimulator "TrafficSimulator", soll bei der Evaluation des ebenfalls durch die Projektgruppe entwickelten Routingalgorithmus BeeJamA-Projektes helfen. Allerdings unterliegt der TrafficSimulator verschiedenen Einschränkungen, die der langfristigen Verwendung während der Weiterentwicklung des BeeJamA-Routingalgorithmus’ entgegenstehen.

Die Simulation wird in einem Java-Prozess durchgeführt, in welchem auf die benötigten Datenstrukturen direkt zugegriffen wird. Die maximale Größe durchführbarer Simulationen ist somit auf die Ressourcen des Rechners beschränkt, auf dem die Simulation durchgeführt wird.

Die verschiedenen Komponenten des Simulators (der Routingalgorithmus, das Regelwerk zur Steuerung der Bewegungen der Fahrzeuge und die zeitdiskrete Simulationseinheit) sind eng miteinander verwoben. Ein Austauschen bzw. Erweitern einzelner Komponenten ist somit nicht möglich, ohne schwerwiegende Veränderungen am Gesamtsystem vornehmen zu müssen. So wäre es wünschenswert, das Regelwerk des Zellularautomaten auszuwechseln, um Simulationen mit unterschiedlichen Fahrerver halten durchführen und miteinander vergleichen zu können. Ebenfalls sind die simulierten Entitäten eng miteinander gekoppelt. Der TrafficSimulator definiert keine klaren Schnittstellen zwischen den simulierten Entitäten (z.B. dem Auto, dem Navigationsgerät im Auto und dem Navigator, mit dem die Navigationsgeräte im BeeJamA kommunizieren). Dadurch ist es nicht möglich, mit Hilfe des Simulators entwickelte Systemkomponenten in anderen Umgebungen wiederzuverwenden. So wäre ein experimenteller Versuchsaufbau zur Kommunikation der Endgeräte mit dem Navigator über das Mobilfunknetz wünschenswert.

Die Weiterentwicklung des Verkehrssimulators zu einem modular aufgebauten, skalierbaren Simulationsframework und die Erweiterung um zusätzliche Funktionen stellt daher einen unerlässlichen Schritt bei der Weiterentwicklung des BeeJamA-Routingalgorithmus dar. In dieser Diplomarbeit soll nun eine verteilte Simulationsumgebung zur Analyse dezentraler Routingalgorithmen in dynamischen Verkehrsszenarien modelliert und implementiert werden. Dafür ist eine Untersuchung notwendig, in wie weit der vorhandene monolithische Verkehrssimulator wiederverwendet werden kann. Nötigenfalls muss eine Neuentwicklung eines modular aufgebauten, skalierbaren Simulationsframework stattfinden. Unter Beachtung eines sowohl realitätsnahen als auch effizienten Designs, soll das entwickelte Simulationsframework folgende Anforderung erfüllen:

  • Unterstützung von Parallelverarbeitung
  • Realisierung von Schnittstellen
    • Dynamisches Verkehrsmodell (TrafficModel)
    • Dynamische Routingalgorithmen (Routing)
    • Externe Netzwerkkommunikation (Network)
  • Sammeln von Simulationsergebnissen
  • Graphische Benutzerschnittstelle

Durch Parallelverarbeitung sollen rechenintensive Operationen auf mehrere Computer aufgeteilt werden, mit dem Ziel die Gesamtausführungszeit zu verkleinern. Um die in der Realität auftretende Kommunikations- und Koordinationskomplexität analysieren und so getreu wie möglich abzubilden zu können, sollte die verteilte Simulation möglichst realistisch nachgebildet werden. In einer solchen Nachbildung soll die Partitionierung des Verkehrsnetzes in Bereiche im dezentralen Routingalgorithmus BeeJamA Beachtung finden. Damit sollte eine Analyse des Kommunikationsaufwands zur Verwaltung der Bereiche ermöglicht werden. Allerdings wird eine effiziente Bereichsbildung derzeit in einer verwandten Arbeit untersucht. Daher soll die realistische Bereichsbildung im Design beachtet, aber eine Konzentration auf die effiziente Parallelverarbeitung der Simulation stattfinden.

Literatur

[1] Apache maven project. http://maven.apache.org/. 32

[2] Common object request broker architecture (corba). http://www.corba.org/. 9

[3] The foundation for intelligent physical agents. http://www.fipa.org/. 10

[4] Java agent development framework. http://jade.tilab.com/. 10, 54

[5] logging for java. http://logging.apache.org/log4j/. 6

[6] Open systems mapping technology, openmap. http://openmap.bbn.com/. 6

[7] opengl. http://www.opengl.org/. 6

[8] Openstreetmap. http://www.openstreetmap.org/. 7

[9] Remote procedure call (rpc). http://www.ietf.org/rfc/rfc1831.txt. 9

[10] Service oriented architecture. http://java.sun.com/developer/technicalArticles/WebServi 9

[11] Mobile agent facility specification. Object Management Group Inc, 2000. 9

[12] Mercedes Amor, Lidia Fuentes, and Antonio Vallecillo. Bridging the gap between agent-oriented design and implementation using mda. Technical report, Antonio Vallecillo, 2005. 15

[13] R. Barlovic, J. Esser, K. Froese, W. Knospe, L. Neubert, M. Schreckenberg, and J. Wahle. Online traffic simulation with cellular automata. Technical report, Gerhard-Mercator-Universität, 1999. 38

[14] Bernard Bauer, Jörg P.Müller, and James Odell. Agent uml: A formalism for specifying multiagent interaction. Technical report, Siemens, München, Germany, 2003. 15

[15] Ronald L. Rivest Clifford Stein Charles E. Leiserson. Introduction to Algorithms, volume 2. B and T, 2001. 6

[16] Krzystof Chmiel, Maciej Gawinecki, Pawel Kaczmarek, Michal Szymczak, and Marcin Paprzycki. Efficiency of jade agent platform. Technical report, Computer Science Departement, Oklahoma State University, Tulsa, USA, 2005. 10, 11

[17] Troy Downing. Java RMI: Remote Method Invocation. IDG Books Worldwide, 1998. 9

[18] Juliana Küster Filipe. Giving life to agent interaction. Technical report, Laboratory for Foundation of Computer Science, 2004. 15

[19] Stefan Fünfrocken. Mobile agenten im internet. Technische Universität Darmstadt. 9

[20] Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides. Design Patterns. Addison- Wesley Professional, January 1995. 5

[21] Vladimir Gorodetsky, Vadim Ermolayev, Wolf-Ekkehard Matzke, Eyck Jentzsch, Oleg Karsaev, Natalya Keberle, and Vladimir Samoylov. Agent-based framework for simulation and support of dynamic engineering design processes in psi. Technical report, Zaporozhye National University, 2005. 10

[22] Gnu general public license. http://www.gnu.de. 7, 10

[23] Hewitt. A self-contained, interactive and concurrently-executing object, possessing internal state and communication capability, 1977. 15

[24] free java graph library. http://jgrapht.sourceforge.net/. 37

[25] Java bindings for opengl. https://jogl.dev.java.net. 6

[26] Aguilar Jose, Cerrada Mariela, and Hidrobo Francisco. A methodology to specify multiagent sy- stems. Technical report, Facultad de Ingeniería, Universidad de los Andes. 15

[27] Rafal Leszczyna. Evaluation of agent platforms. Technical report, Cybersecurity and New Tech- nologie for Combating Fraud Institute for the Protection and security of the Citizen, Joint Research Centre, Ispra, Italy, June 2004. 10

[28] Robert C. Martin. Designing, object-oriented C++ applications using the Booch method. Prentice- Hall, 1995. 31

[29] James Odell and Marian Nodine. Auml workplan. Technical report, FIPA, January 2003. 15

[30] James J. Odell, H. Van Dyke Parunak, and Bernhard Baue. Representing agent interaction protocols in uml. Technical report, Springer-Verlag, 2001. 15

[31] Candelaria Sansores and Juan Pavon. Agent based simulation for social systems. Technical report, Universidad Complutense de Madrid, Dep. Sistemas Informáticos y Programación, 2006. 10

[32] Elhadi Shakshuki and Yang Jun. Multi-agent development toolkits: An evaluation. Technical report, Jodrey School of Computer Science, Acadia University, 2004. 10

[33] Alexei Sharpanskykh. Modeling of agents in organizational context. Technical report, Alexei Sharpanskykh, 2007. 15

[34] Renee Steiner, Gary Leask, and Rym Z.Mili. An architecture for mas simulation environments. Technical report, The University of Texas at Dallas, 2006. 10

[35] Andrew S. Tanenbaum and Maarten van Steen. verteilte Systeme. Pearson Studium, 2008. 9

[36] Horst F Wedde, Sebastian Lehnhoff, Bernhard van Bonn, Z Bay, S Becker, S Boettcher, C Brunner, A Buescher, T Fuerst, A M Lazarescu, E Rotaru, S Senge, B Steinbach, F Yilmaz, and T Zim- mermann. Stauvermeidung durch on-line verkehrsplanung stop. Endbericht pg502, Technische Universität Dortmund, 2007. 1, 3, 5, 6, 7, 35

[37] Michael Wooldridge. An Introduction to Multiagent Systems. John Wiley & Sons, February 2002. 9

[38] Michael Zapf. Vorlesungsmaterial verteilt-kooperative informationsverarbeitung. 9

Zur Publikation...
Weitere Publikationen zu BeeJamA...