IEEE Copyright Notice

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

ACM Copyright Notice

These are the authors' versions of the work. The copyright is with ACM. They are posted here by permission of ACM for your personal use. Not for redistribution. See individual publication details for information on the publication of the definitive versions.

Springer-Verlag LNCS Copyright Notice

The copyright of these contributions has been transferred to Springer-Verlag Berlin Heidelberg New York. The copyright transfer covers the exclusive right to reproduce and distribute the contribution, including reprints, translations, photographic reproductions, microform, electronic form (offline, online), or any other reproductions of similar nature. Online available from Springer-Verlag LNCS series.

Work that appeared before the 1st of September 2003 was published while the authors were with the Lehrstuhl Praktische Informatik IV at the University of Mannheim.

Avoiding the Gridlock -- Information Dissemination in Vehicular Networks

Author(s): Christian Lochert.
Title: Avoiding the Gridlock -- Information Dissemination in Vehicular Networks
Published: PhD thesis, Heinrich Heine University, Düsseldorf, Germany, November 2008
Keyword(s): Information Dissemination, VANET, Aggregation, Vehicular Networks
Abstract: In this thesis we analyze information dissemination in the context of vehicle-to-vehicle communication. Cars can communicate with each other by using radio technologies like IEEE 802.11. They implicitly form a so called Vehicular Ad-Hoc Network (VANET). Vehicles autonomously make observations about the current traffic situation of a road. In order to allow nodes to create an overview of the whole scenario these observations should be sent by many vehicles to many other vehicles probably far away. One goal of this thesis is thus to analyze the process of information dissemination as well as to provide mechanisms for the information dissemination. A navigation system may then use this data to calculate the fastest route based on the current traffic situation. In order to meet the requirements of such a system the information has to be transmitted in a timely fashion. It is furthermore important to reach distant regions to inform other vehicles in due time.In the analysis of mechanisms and applications for VANETs simulators are an important building block. However, it is a hard challenge to model the reality as precise as possible while gaining high efficiency during the execution of simulations. Only special simulators developed for one single purpose are able to deal with these demands. In the first contribution we present results of coupling different specialized simulators. We develop a meta-simulator environment which allows one simulator to interact with another simulator by exchanging (partial) results or to react upon the input of these results. We are thus now able to analyze the implications of information dissemination in a network for instance on the movement of vehicles in a given scenario.The following contribution poses in detail the two major challenges of information dissemination in VANETs: i) limited connectivity and ii) limited bandwidth. The first challenge corresponds to the general feasibility of information dissemination in a VANET and its dissemination speed. Especially during the rollout of this technology this is an important aspect to consider. In an early stage the penetration ratio of vehicles equipped with VANET devices will be low. Regarding the ad-hoc network, it becomes obvious that a lot of partitions will exist that hamper a proper, fast and reliable spread of data. In order to deal with these limitations during the rollout phase we introduce the concept of (stationary) supporting units. These supporting units represent additional infrastructure devices. They build a backbone for the VANET which is formed by vehicles and their ad-hoc communication. Due to the additional costs we analyze the minimum necessary deployment of these units. We further demonstrate by the means of an example application that only few of these supporting units are needed to improve the performance of information dissemination significantly by spanning distant regions in a timely fashion.By using multiple vehicles as data sources as well as with an increasing size of the network the amount of data, that is to be disseminated, grows significantly. In order to tackle the second challenge---limited bandwidth---we analyze how this increase in the amount of data looks like. We determine lower and upper bounds for the considered limitations of the bandwidth. These bounds motivate the usage of aggregation mechanisms. The main task of these mechanisms is to subsume information in relation to an increasing distance.Following these insights we present an approach which tackles both mentioned challenges. In particular, we present an aggregation mechanism dealing with the additional challenge of a city scenario. This specific type of scenario is defined by its two-dimensional characteristics of the considered topology or streets, respectively. By using this aggregation mechanism information about street segments can be subsumed in an efficient and meaningful manner. The algorithm is implemented by a multilayered and hierarchical aggregation based on the landmark principle. In addition, we present an optimization method for the proper placement of supporting units in order to deal with the low amount of equipped vehicles. Due to the rapid increase of the possible space of solutions we propose to make use of a genetic algorithm in order to solve this hard optimization problem. By implementing a prototype navigation system we underline the performance of the aggregation scheme in combination with the placement of supporting units.A distinct challenge of aggregation mechanisms is the merging of aggregates. For instance when one node receives two different aggregates describing the same area it has to decide which one of them contains "better" information. Thus, the last contribution of this thesis constitutes a probabilistic approach for the representation of aggregates. The central property of this hierarchical scheme is that overlapping aggregates can be subsumed implicitly. It is therefore not necessary to know the distinct entries of the aggregate. We show by means of an example application the benefit of this approach.
Bib entry: [XML] [BibTeX]
Download: [PDF]
Verantwortlich für den Inhalt: E-Mail sendenWE Informatik