Article in Proceedings INPROC-2004-05

BibliographyHähner, Jörg; Dudkowski, Dominique; Marrón, Pedro José: A Quantitative Analysis of Partitioning in Mobile Ad Hoc Networks.
In: Accepted for Poster at the Joint International Conference on Measurement and Modeling of Computer Systems : Sigmetrics - Performance 2004.
University of Stuttgart : Collaborative Research Center SFB 627 (Nexus: World Models for Mobile Context-Based Systems).
english.
 ACM, June 2004.
Article in Proceedings (Conference Paper).
CR-SchemaC.2.1 (Network Architecture and Design)
D.2.8 (Software Engineering Metrics)
Keywordsmobile ad hoc networks, network topology, partition metrics
Abstract

The performance of distributed algorithms in mobile ad hoc networks is strongly influenced by the connectivity of the network. In cases where the connectivity is low, network partitioning occurs. The mobility and density of network nodes, i.e. the movement of nodes and the number of nodes per unit area, are fundamental properties that have a large impact on the partitioning behavior, so that a detailed characterization of this behavior may be applied to improve the performance of distributed algorithms.

In this paper we introduce a set of metrics that describe characteristics regarding partitioning in mobile ad hoc networks. We have conducted an extensive set of simulation studies for a wide range of network scenarios to show the impact of node mobility and density on the proposed metrics. We present results for the number of partitions, their size over time, and the frequency of partition changes. From the perspective of individual nodes, we introduce metrics that describe the time periods in which pairs of nodes are located in different partitions, and the number of nodes that are in the partition of an individual node over time.

The results obtained in this paper will allow distributed data management algorithm designers to characterize those types of network scenarios where partitioning must be explicitly considered. Especially algorithms in areas such as replication, data storage, and query processing, may be inspired by the results at hand. Finally, the optimization of strategies for replica placement, update frequency, spatial scoping of data, and even more advanced techniques for data exchange between nodes in frequently partitioned networks will also benefit from our results.

ContactPlease send an email to joerg.haehner@informatik.uni-stuttgart.de or dominique.dudkowski@informatik.uni-stuttgart.de
Department(s)University of Stuttgart, Institute of Parallel and Distributed Systems, Distributed Systems
Project(s)SFB-627, B3 (University of Stuttgart, Institute of Parallel and Distributed Systems, Distributed Systems)
Entry dateFebruary 5, 2004