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.