A Parsimonious Model of Mobile Partitioned Networks with Clustering

Mobile wireless networks frequently possess, at the same time, both dense and sparse regions of connectivity; for example, due to a heterogeneous node distribution or radio propagation environment. This paper is about modeling both the mobility and the formation of clusters in such networks, where nodes are concentrated in clusters of dense connectivity, interspersed with sparse connectivity. Uniformly dense and sparse networks have been extensively studied in the past, but not much attention has been devoted to clustered networks. We present a new mobility model for clustered networks, which is important for the design and evaluation of routing protocols. We refer to our model as Heterogeneous Random Walk (HRW). This model is simple, mathematically tractable, and it captures the phenomenon of emerging clusters, observed in real partitioned networks. We provide a closed-form expression for the stationary distribution of node position and we give a method for “perfect simulation”. Moreover, we provide evidence, based on mobility traces, for the main macroscopic characteristics of clustered networks captured by the proposed mobility model. In particular, we show that in some scenarios, nodes have statistically very similar mobility patterns. Also, we discuss cluster dynamics and the relationship between node speed and node density.