Universität Stuttgart
Permanent URI for this communityhttps://elib.uni-stuttgart.de/handle/11682/1
Browse
Search Results
Item Open Access Simulation and optimized scheduling of pedestrian traffic : from geometric modeling to pedestrian navigation(2007) Narasimhan, Srihari; Bungartz, Hans-Joachim (Prof. Dr. rer. nat.)Today, more and more simulation tasks with a traditionally non-geometric background need to be embedded into some geometric context, in order to provide spatial context to non-spatial data. This holds especially true for graph-based applications in some location-aware context. As an example, one might think of a theme park or a large commercial center, where the customers shall be provided with some navigation and scheduling information such as where to go and when - either a priori or even in real time via some mobile device. This can be done by analyzing the pedestrian traffic and waiting time situation by simulating the pedestrian movement and using the simulation data to optimally navigate and schedule the tasks that are to be executed by the customer. The main issues addressed in this thesis are as follows. Initially, a flexible simulation framework is built to simulate the pedestrian movement in a 3D scenario, for example, a commercial building. Since the pedestrians strongly interact with the environment surrounding them, the geometry is taken into account. Architectural data such as paths, type and capacity of the paths, destinations and its properties, etc., is extracted from the CAD-model and are organized in a graph structure. The movement of the pedestrians and the waiting queues at the destinations are modeled as queuing systems using the discrete event simulation technique. These queuing systems are then embedded into the geometry model. The necessary input modeling parameters are also defined. The resulting scenario, when simulated, gives an overview of congestions and waiting times across the scenario for different time stages. Apart from the simulation, the geometry data - or here the graph - is hierarchically organized in an octree structure. An octree-based model is chosen since octrees have the natural property of hierarchically storing 3D data. The octree data is used to identify the position of the pedestrian within the scenario. The potential destinations in the neighborhood that can be visited by the customer are also identified using neighbor search algorithms. Combining the simulation data with the octree modeling, the customer is navigated to the optimal destination. Furthermore, when visiting several destinations, combinatorial optimization methods are used to optimally schedule the set of tasks to be executed by the customer. The optimization methods take into account the congestion information obtained from the simulation data, and the octree structure for navigation. This approach results in an effective pedestrian navigation system.Item Open Access Consistent data replication in mobile ad hoc networks(2007) Hähner, Jörg; Rothermel, Kurt (Prof. Dr.)Mobile ad-hoc networks (MANETs) are used in situations where networks need to be deployed immediately but no network infrastructure is available. If MANET nodes have sensing capabilities, they can capture and communicate the state of their surroundings, including environmental conditions or objects in their proximity. If the sensed state information is propagated to a database to build a consistent model of the real world, a variety of promising context aware applications becomes possible. The models and concepts proposed in this dissertation can be applied to cooperatively maintain a model of the state of physical world objects on devices in MANETs. State information may be updated by independent observers either sequentially or concurrently. Applications that read the state of any object from the model multiple times can rely on the guarantee that every successive read operation will read either the same state information or newer state information that has been reported by an observer after the previously read information. The first contribution of this dissertation formalizes these requirements and defines a novel consistency model called update-linearizability. Secondly, it introduces a new class of data replication algorithms that provably guarantees update-linearizability in MANETs without using synchronized clocks on any pair of nodes in the system. The presented algorithms allow executing read and write operations at any time, which provides high availability of data. These properties are even maintained in networks that are temporarily partitioned and where nodes are highly mobile. Finally the dissertation provides a proof that all replicas held in the system eventually converge towards the most recent state information of the physical world objects which they represent.Item Open Access Coordination protocols for split BPEL loops and scopes(2007) Khalaf, Rania; Leymann, FrankThe document presents an approach to enable loops and fault handling, compensating scopes to be split among a set of BPEL processes running on different BPEL engines. A mechanism to split a scope or loop into multiple fragments is presented, then a protocol is defined that can be used to coordinate fragments of a loop or a scope so that those fragments run as if they had been in a single process. The requirements for running split scopes and loops are explained. For compensation, this paper focuses on explicit compensation and makes the assumption that compensation handing does not fail. Two protocols are defined such that they may be plugged into the WS-Coordination framework. The messages between the participant fragments and the coordinator are defined. The information about the participating processes that the coordinator needs to have is specified. An algorithm is provided to locate a fault handler in the hierarchy of scopes that can handle a particular BPEL fault. Additionally, the behavior of both participants and the coordinator are specified.Item Open Access Reduktion von Verzögerungsunterschieden bei der Gruppenkommunikation im Internet(2007) Klöcking, Jens-Uwe; Rothermel, Kurt (Prof. Dr.)Eine Vielzahl neuer Anwendungsgebiete des Internets basiert auf der effizienten Übertragung einer Nachricht an eine Gruppe von Empfängern, der so genannten Gruppenkommunikation. Beispiele für derartige Anwendungen sind Nachrichten- und Softwareverteilung, verteilte Berechnungen, Videokonferenzen, Fernunterricht sowie Spiele. Die Netzwerkressourcen werden durch Gruppenkommunikation sehr effizient genutzt, denn das einmalige Senden einer Nachricht reicht aus, um von allen Teilnehmern einer Gruppe empfangen zu werden. Einige Einschränkungen der Dienstqualität derzeitiger Gruppenkommunikationslösungen im Internet behindern jedoch ihre generelle Nutzung. Hiervon betroffen ist unter anderem die Fairness bezüglich der Verzögerung der Nachrichtenauslieferung. Dieser spezielle Parameter der Gruppenkommunikation bezeichnet die Zeitspanne zwischen dem ersten und letzten Eintreffen einer Nachricht bei einer Gruppe von Empfängern. Messungen mittels eines dafür entwickelten passiven Verfahrens zeigen für einige Anwendungen nicht tolerierbare Verzögerungsunterschiede auf. Das Ziel der Arbeit besteht darin, die Verzögerungsunterschiede zu minimieren, um einen fairen Dienst für nicht kooperative Anwendungen der Gruppenkommunikation im Internet, wie z. B. Informationsdienste und elektronische Märkte bereitzustellen. Zur Lösung des Problems wurden drei Ansätze erarbeitet. Durch den Einsatz von Servern konnten Verzögerungsunterschiede der Nachrichten ausgeglichen werden. Die in der Anwendungsschicht angesiedelten Ansätze stellen keine besonderen Anforderungen an die Netzkomponenten und können daher schrittweise eingeführt werden. Darüber hinaus berücksichtigen sie die aktuelle Netzwerklast und sind so in der Lage, die Gesamtverzögerung der Nachrichtenauslieferung gering zu halten. In einem der Ansätze überwacht sichere Hardware in Form von Smart Cards direkt bei den Empfängern den Auslieferungszeitpunkt der Nachrichten. Hierfür wurden drei Protokolle entwickelt, die die Synchronisation der Smart-Card-Uhren, die Auslieferung der Daten und eine Rückmeldung der tatsächlichen Verzögerung ermöglichen. Mittels Analyse und Simulationen wurde eine signifikante Reduktion der Verzögerungsunterschiede der Nachrichten zwischen den Empfängern nachgewiesen. Ein Prototyp wurde implementiert, um die mit gegenwärtiger Smart-Card-Hardware erreichbare Reduktion von Verzögerungsunterschieden zu ermitteln und die Tragfähigkeit des Ansatzes zu demonstrieren.Item Open Access Vorabübertragung schwach strukturierter Informationen in ortsbasierten mobilen Systemen(2007) Bürklen, Susanne Gudrun; Mitschang, Bernhard (Prof. Dr.)Die rasant fortschreitende Entwicklung der Mobilkommunikation in Verbindung mit immer leistungsfähigeren mobilen Endgeräten weckt den Wunsch, an jedem Ort und zu jeder Zeit auf entfernte Informationen zugreifen zu können. Drahtlose Weitverkehrsnetze wie die Mobilfunknetze der zweiten oder dritten Generation bieten zwar nahezu überall eine Netzverbindung, weisen jedoch negative Eigenschaften wie eine hohe Latenz, hohe monetäre Kosten und unzuverlässige Verbindungen auf, die teilweise zum entkoppelten Betrieb führen können. Eine hohe Latenz führt dazu, dass auf Grund der hieraus entstehenden langen Übertragungszeiten der Informationen der Energieverbrauch der Funkschnittstelle ansteigt, was in Anbetracht der geringen Energieressourcen mobiler Endgeräte nicht wünschenswert ist. Um diesen Nachteilen entgegen zu wirken, wurden zugriffsoptimierende Methoden wie beispielsweise Caching oder die Vorabübertragung entwickelt, die jedoch unterschiedlichen Zielsetzungen folgen. Eine solche Methode ist die Vorabübertragung von Informationen an solchen Orten, an denen eine breitbandige und kostengünstige Verbindung zur Verfügung steht. In dieser Dissertation wird zur Optimierung des mobilen Informationszugriffs ein generisches Verfahren zur Vorabübertragung von beliebigen schwach strukturierten Informationen in ortsbasierten Anwendungen vorgestellt, das neben einer Verringerung der Latenz den entkoppelten Betrieb unterstützt. Für die Selektion der vorab zu übertragenden Informationen werden je nach Art der Informationen unterschiedliche Methoden angeboten. Als Basis wird eine Infrastruktur von so genannten Infostationen benötigt, an denen mobilen Benutzern mittels drahtloser lokaler Netze ein breitbandiger und kostengünstiger Zugriff auf Informationen ermöglicht wird. Sie sind in Gebieten verteilt, an denen sonst keine oder nur eine Kommunikation mit der maximalen Datenrate eines drahtlosen Weitverkehrsnetzes, wie beispielsweise GSM, GPRS oder UMTS möglich ist. Eine Infostation selektiert die in ihrem Dienstgebiet für einen Benutzer relevanten Informationen und überträgt sie vorab auf dessen mobiles Endgerät. Zukünftige Informationsanfragen können somit lokal aus dem Cache beantwortet werden, was jedoch eine gute Vorhersage voraussetzt. Um eine hohe Relevanz der vorab geladenen Informationen zu erreichen, werden als Selektionskriterium neben der Ortsabhängigkeit von Informationszugriffen auch Beziehungen zwischen den Informationen ausgewertet. Eine Infostation beobachtet das typische Zugriffsverhalten aller Benutzer, die sich in ihrem Dienstgebiet aufhalten und benutzt dieses Wissen zur Vorhersage der Informationen. Das Beobachten des kollektiven Zugriffsverhaltens hat den Vorteil, dass überwiegend diejenigen Informationen vorab geladen werden, die in einem Dienstgebiet zum aktuellen Zeitpunkt populär sind. Dieses Verfahren unterstützt somit auch solche Benutzer, die sich zum ersten Mal in diesem Gebiet aufhalten. Bisweilen können Informationen derart stark zusammenhängen, dass sie für einen Benutzer nur als Gruppe interessant sind und es keinen Sinn ergibt, einzelne Objekte dieser Gruppe isoliert von den anderen zu übertragen. In einem solchen Fall müssen Gruppen (Cluster) gebildet werden, die vollständig vorab übertragen werden. Des Weiteren resultiert die Auswertung des Zugriffsverhaltens einer Menge von Benutzern nicht immer in einer optimalen Entscheidung für einen individuellen Benutzer. Dieser Effekt kann jedoch verringert werden, wenn Nutzungsprofile in die Übertragungsentscheidung mit einbezogen werden. Das generische Vorabübertragungsverfahren wurde für den mobilen Zugriff auf das Web spezialisiert und evaluiert. Zur systematischen Leistungsbewertung wurde ein Modell für das Navigationsverhalten von Benutzern im Web entwickelt und implementiert, das Sequenzen von synthetischen Zugriffen auf das Web erzeugt. Mit dem clusterbasierten Auswahlverfahren konnten Trefferraten erzielt werden, die andere Ansätze um mehr als das Dreifache übertreffen. Schließlich ist der Energiebedarf der Funkschnittstelle ein nicht zu vernachlässigender Faktor für die Lebensdauer der Batterie, so dass die Zeit zum Senden und Empfangen von Daten möglichst gering gehalten werden sollte. In einem drahtlosen lokalen Netz steht eine um mindestens eine Größenordnung höhere Bandbreite als in drahtlosen Weitverkehrsnetzen zur Verfügung, wodurch die Übertragungszeit von Informationen deutlich verkürzt wird. Eine Analyse des Leistungsbedarfs von Funkschnittstellen beider Technologien hat gezeigt, dass durch den Einsatz des vorgestellten Verfahrens zur Vorabübertragung von Informationen in jedem Fall Energieeinsparungen möglich sind. Bei Kenntnis der zu erzielenden Trefferrate kann somit die Größe des Caches bestimmt werden, die den Energieverbrauch beim Laden der Informationen minimiert.Item Open Access Key distribution schemes for resource-constrained devices in wireless sensor networks(2007) Wacker, Arno Rüdiger; Rothermel, Kurt (Prof. Dr. rer. nat. Dr. h. c.)Wireless sensor networks based on highly resource-constrained devices require symmetric cryptography in order to make them secure. Integral to this is the exchange of unique symmetric keys between two devices. In this dissertation, we propose three novel decentralized key distribution schemes that guarantee the confidentiality of a key exchange even if an attacker has compromised some of the devices in the network. Our first key distribution scheme -- the basic key distribution scheme -- guarantees the confidentiality of any new established key in case there are only eavesdropping attacker and no device failures present. Our second scheme -- the fault-tolerant key distribution scheme -- extends the basic scheme so that also more powerful attackers and device failures can be handled. Our third proposed key distribution scheme -- the extended key distribution scheme -- is also based on the basic scheme but further optimized in terms of memory consumption and network traffic. A central objective of all key distribution scheme designs was to minimize resource consumption on the individual devices. We evaluate the resource requirements of our schemes in terms of attacker resilience, memory requirements, and network traffic both through theoretical analysis and through simulations.Item Open Access Ein modellbasierter Ansatz zur Lösung komplexitätsbedingter Entscheidungsprobleme in der Infrastrukturarchitektur der Finanzdienstleistungsinformatik(2007) Langner, Torsten; Herzwurm, Georg (Prof. Dr.)Diese Arbeit stellt ein begründetes Gestaltungskonzept vor, das die Infrastrukturarchitekten eines Finanzdienstleisters beim Entwurf neuer IT-Architekturen unterstützt. Das Gestaltungskonzept fokussiert primär die drei Problemdimensionen Komplexität der Infrastrukturarchitektur, Wissens-komplexität und Wissensvolumen sowie Historische Entwicklung der Finanzdienstleistungsinformatik. Durch die Adaption des Wiederverwendungskonzepts reduziert das vorgestellte Konzept zunächst die Komplexität des Architekturentwurfs im Einzelnen, um später die Komplexität der Infrastruktur im Ganzen reduzieren zu können. Hierzu wird die historisch gewachsene IT-Architekturlandschaft eines Finanzdienstleisters erfasst, dekomponiert und kategorisiert. In einem zweiten Schritt wird aus der Vielzahl der Infrastrukturkomponenten eine Selektion der zukünftig zu verwendenden Komponenten ausgewählt und durch qualitative Eigenschaften beschrieben. Die einzelnen Infrastrukturkomponenten werden in einem dritten Schritt zu qualitativ beschriebenen Architekturmustern komponiert, die den Plattformen des klassischen Maschinenbaus ähneln und der Konfiguration neuer Architekturen dienen. Zur Darstellung der Zusammenhänge der Infrastrukturarchitektur wird ein Meta-Modell entwickelt, dessen Anwendung durch ein Prozessmodell beschrieben wird. Das Prozessmodell besteht aus den drei entkoppelten Phasen Einfüh-rung, Anwendung und Pflege der Methodik. Der Eintritt in eine jeweilige Phase ist Ereignisgesteuert, so dass eine kontinuierliche Pflege der Architekturmuster erfolgt. Das Ergebnis des wiederholten Phasendurchlaufs ist ein Standard-Infrastruktur-Katalog, der zum einen die zu konfigurierbaren Architekturmustern komponierten, vorselektierten Infrastrukturkomponenten qualitativ (d. h. typisch, architektonisch und leistungstechnisch) beschreibt, und der zum anderen den Infrastrukturkomponenten und Architekturmustern strategische Entscheidungsregeln zuweist.Item Open Access Algorithmische Aspekte der Fluid-Struktur-Wechselwirkung auf kartesischen Gittern(2007) Brenk, Markus; Bungartz, Hans-Joachim (Prof. Dr.)In vielen physikalischen Systemen und technischen Anwendungen spielen Fluid-Struktur-Wechselwirkungen eine wesentliche Rolle. Die Wechselwirkung von Fluiden und flexiblen Strukturen stellt ein gekoppeltes Problem dar, bei dem die Bewegung eines Fluides und einer Struktur über die so genannte nasse Oberfläche (Kopplungsoberfläche) der Struktur bidirektional gekoppelt sind. So sind Windlasten an Gebäuden und Brücken, das Aufblasen von Airbags, das Öffnen von Fallschirmen, der Blutfluss in einer Ader oder die Strömung zwischen den Lamellen eines Autoreifens Beispiele für diese Art der Kopplung. Bei der Untersuchung von Fluid-Struktur-Wechselwirkungen ist die numerische Simulation ein unerlässliches Hilfsmittel. Oft werden diese Simulationen durch so genannte partitionierte Ansätzen realisiert. Diese sind dadurch gekennzeichnet, dass getrennte und für die einzelnen Teilprobleme konzipierte und angepasste Programme zur Berechnung der Strömungen und der Strukturbewegungen bzw. -verformungen eingesetzt werden -- im Gegensatz zu so genannten monolithischen Ansätzen, bei denen alle Teilprobleme gemeinsam diskretisiert und in einem Programm behandelt werden. Bei partitionierten Ansätzen können Teile der Berechnungen mit bewährten und für den jeweiligen Teilaspekt am besten geeigneten Softwarelösungen erfolgen. Damit ist jedoch eine zusätzliche Programmkomponente erforderlich, die den Ablauf der gekoppelten Simulation steuert und den Austausch der Daten zwischen den Simulationsprogrammen ermöglicht und die somit einen integralen Bestandteil partitionierter Ansätze darstellt. Dies zeigt deutlich, dass sich bei der Simulation von Fluid-Struktur-Wechselwirkungen mit partitionierten Ansätzen, neben den ingenieurwissenschaftlichen Herausforderungen (wie bspw. dem Lösen konkreter Problemstellungen) und den mathematischen Herausforderungen (wie bspw. dem Sicherstellen von Konvergenz und Robustheit), insbesondere auch softwaretechnische und damit informatische Herausforderungen ergeben. Die vorliegende Arbeit befasst sich schwerpunktmäßig mit den resultierenden Fragestellungen zur Steuerung der Kopplung, zur Verknüpfung der in den Programmen unterschiedlichen geometrischen Darstellungen der nassen Oberfläche und zum Austausch der kopplungsrelevanten Daten. Die physikalische Beschreibung des Fluid-Struktur-Wechselwirkungsproblems fordert die Erfüllung von Gleichgewichtsbedingungen auf der Kopplungsoberfläche zu jedem Zeitpunkt. Für partitionierte Ansätze existieren je nach Anwendungsfall unterschiedliche Strategien und Methoden zum Austausch der Kopplungsdaten und zur Steuerung der Kopplung in der Zeit, um diese Gleichgewichte zwischen den getrennten Simulationen sicherzustellen. Dies erfordert eine Softwarelösung zur Kopplung der Simulationsprogramme, die neben einer einfachen und mit geringem Aufwand durchzuführenden Anpassung der Programme und einer flexiblen Möglichkeit zur Steuerung der Kopplung, eine Lösung zum Transfer der kopplungsrelevanten Daten -- zwischen den auf unterschiedlichen Diskretisierungen und Datenstrukturen aufbauenden Repräsentationen der Kopplungsober Fläche in den Simulationsprogrammen -- bietet. Dieser Transfer von Kopplungsdaten zwischen den verschiedenen Oberflächenrepräsentationen kann durch die Einbettung in eine übergeordnete Geometrierepräsentation wirkungsvoll unterstützt werden. Hierfür bieten sich insbesondere hierarchisch-strukturierte Zerlegungen des Raumes durch kartesische Volumenelemente (z. B. Oktalbäume) als laufzeit- und speichereffiziente Lösung an. Diesem Effizienz-Gedanken folgend, stellt sich die Frage, ob diese strukturierten kartesischen Zerlegungen des Raumes nicht direkt als Basis für die Diskretisierung des Strömungsgebietes bei der Simulation von Fluid-Struktur-Wechselwirkungen genutzt werden können. Die Untersuchung kartesischer Diskretisierungen im Kontext der Fluid-Struktur-Wechselwirkung bildet, neben den Fragestellungen der Realisierung der Kopplung den zweiten Schwerpunkt dieser Arbeit. Es werden entsprechende Methoden vorgestellt, untersucht und insbesondere durch die dreidimensionale Simulation des Transportes von Partikeln in Mikroströmungen validiert.Item Open Access A generalized broadcasting technique for mobile ad hoc networks(2007) Khelil, Abdelmajid; Rothermel, Kurt (Prof. Dr. rer. nat. Dr. h. c.)Broadcasting is a major communication primitive required by many applications and protocols in Mobile Ad Hoc Networks (MANETs). It is frequently deployed for content distribution, service discovery or advertisement, and sensor data dissemination. Broadcast protocols are also a fundamental building block to realize principal middleware functionalities such as replication, group management and consensus. Broadcasting in MANETs has therefore been an active area of research recently. Most of the research conducted on broadcasting in MANETs has primarily focused only on carefully selected application and evaluation scenarios. Consequently, the developed broadcasting schemes do not yield good performance for other scenarios. Different comparative studies show that the existing broadcasting techniques are tailored to only one class of MANETs with respect to node density and node mobility, and are unfortunately not likely to operate well in other classes. Node spatial distribution is a key issue for the performance of broadcast protocols, since it determines the connectivity of the MANET. Our survey of potential MANET application scenarios shows a wide range of possible node spatial distributions and node mobilities. This leads to that a MANET generally shows a continuously changing network connectivity over space and time. Therefore, a generalized solution for broadcasting that accounts for the requirements of the various applications and adapts to the heterogeneous and evolving node spatial distribution and mobility is a major contribution. In this thesis, we present hypergossiping, a novel generalized broadcasting technique for MANETs. Hypergossiping integrates two adaptive schemes and efficiently switches between them depending on local node density. The first scheme is adaptive gossiping, which distributes messages within connected parts of the MANET. We adapted gossiping as follows. First, we established an analytical model for gossiping through adopting the SI mathematical model from the epidemiology. Then, we used the model to adapt the gossiping forwarding probability to local node density. As a result, we provide a simple analytical expression that nodes use to set the appropriate forwarding probability depending on the current number of neighbors. Simulation results showed that adaptive gossiping efficiently propagates messages within a network partition independent of the node spatial distribution and node mobility in that network partition. The second scheme is a broadcast repetition method, which detects partition joins using an efficient and localized heuristic and efficiently repeats the needed broadcasts upon detection of a partition join. Our approach is mobility-assisted since it exploits the mobility of nodes to efficiently deliver messages in frequently partitioned scenarios. We defined mobility metrics that simplify the design of mobility-assisted concepts, and used some of them to design a mobility-aware buffering strategy, which can significantly reduce the buffer overhead of hypergossiping. Simulation results in the standard network simulator ns-2 show that hypergossiping outperforms all existing strategies. Hypergossiping significantly increases the delivery ratio for a broad range of MANETs with respect to node density, node mobility and network load while providing high efficiency and scalability.Item Open Access Note on syntactic details of split BPEL-D business processes(2007) Khalaf, RaniaThe document presents the syntactic details of the generation of process fragments created by the algorithm in [1], which defined the mechanisms for splitting a business process defined using a variant of WS-BPEL. The variant, BPEL-D, replaced BPEL’s variable style of data handling with explicit data links. We add new support in this note for syntactically splitting loops and scopes.