Graph theoretic models and tools for the analysis of dynamic wireless multihop networks

Wireless multihop networks are being increasingly used in military and civilian applications. Advanced applications of wireless multihop networks demand better understanding on their properties. Existing research on wireless multihop networks has largely focused on static networks, where the network topology is time-invariant; and there is comparatively a lack of understanding on the properties of dynamic networks with dynamically changing topology. In this paper, we use and extend a recently proposed graph theoretic model, i.e. evolving graphs, to capture the characteristics of such networks. We extend and develop the concepts of route matrix, connectivity matrix and probabilistic connectivity matrix as convenient tools to characterize and investigate the properties of evolving graphs and the associated dynamic networks. The properties of these matrices are established and their relevance to the properties of dynamic wireless multihop networks are introduced. © 2009 IEEE