Networks are often classified based on the connectivity of their physical link topology: a network is called connected if it permanently provides paths between all nodes, otherwise it is referred to as disconnected. If a disconnected network provides physical paths between a sizable fraction of nodes, we say it is partially connected, as opposed to a scenario where all nodes are isolated almost all the time. While percolation theory and the contact process have been used to investigate connectivity and opportunistic forwarding, respectively, neither of those methodologies adequately describe the whole gamut of mobile wireless networks.

We have developed a methodology to characterize arbitrary mobile wireless networks scenarios via the distribution of the size of connected components (clusters) in the physical link topology. To derive this distribution, we model the network as a Markov process describing the sizes of clusters evolving through merge and split reactions between clusters. The parameters of this process are estimated based on the observable statistics of merge and split reactions of a given scenario. The stationary state of the process is obtained analytically and characterizes the physical connectivity provided by the scenario. Further, we show that for increasing number of nodes the behavior of the process converges to a mean field behavior and we derive a simple, closed-form approximation describing the expected cluster size distribution. This is remarkable as it provides a simple relationship between the microscopic statistics of merge and split events between clusters and the resulting macroscopic cluster size distribution. Indeed, because the process also captures temporal behavior of the scenario, we are able to predict the fluctuation of the cluster size of an individual node over time. We validate these theoretical results against several synthetic and real-world contact and mobility traces with dozens to thousands of nodes, confirming the validity of the model and showing remarkable accuracy of the predicted behavior.

Simon Heimlicher and Kavé Salamatian:
Globs in the Primordial Soup — The Emergence of Connected Crowds in Mobile Wireless Networks
ACM MobiHoc 2010, Chicago, September 2010.
★ Best Paper Award ★
Paper as PDF | Extended Version as PDF