The search for appropriate wireless network models that capture the effects of node locations and user interferences has led to the introduction of several classes of random graphs with increasingly complex notions of adjacency (i.e., one-hop connectivity). In such one-hop connectivity graph models, the presence of an edge between two nodes captures their ability to communicate directly and reliably with each other. However, viewed as systems, networks are "greater than the sum of their parts" -- One-hop connectivity gives rise to "network connectivity" as network resources collectively enable end-to-end data transfer between participating nodes. When the graph determined by the one-hop connectivities is static (or slowly changing at the time scales of interest), network connectivity is readily identified with the usual notion of graph connectivity in the one-hop connectivity graph. In the presence of mobility, the one-hop connectivity structure of the network changes over time, graph connectivity may no longer be suitable to capture network connectivity and other, more appropriate, notions need to be considered. With this in mind, we introduce the notions of continuous connectivity and fly-through connectivity: Continuous connectivity requires that a path exists between every pair of nodes at all times. Fly-through connectivity only demands that a multi-hop end-to-end path be provided within acceptable delays, allowing for the possibility that the network is not continuously connected.
We explore how these different notions of network connectivity shape resource allocation (e.g., energy) in the presence of node mobility. Concerning continuous connectivity, emphasis is on (i) identifying zero-one laws and the attending critical scalings, and on (ii) determining the existence and width of associated phase transitions. The approach and methods are probabilistic in nature. Major efforts will be made to find useful characterizations for fly-through connectivity. Tools from algebraic graph theory and from the spectral theory of graphs are expected to play a key role. This should result in more realistic models for wireless networks for the purpose of designing robust and efficient resource allocation algorithms in the presence of node mobility, and for evaluating their performance.
