Probabilistic Tomography of Wireless Networks Project

Some more recent studies of network tomography have considered wireless systems. However, investigations have largely been limited by the lack of available statistical models that incorporate spatial and physical characteristics inherent to wireless networks. For example, spatial (wireless) networks exhibit distinctive features (e.g., transitivity, clustering), which have not been fully exploited in topology inference tasks.

There is a need to develop improved active methods (topology discovery) and passive techniques (topology inference) of obtaining the topology of a wireless communications network or a portion thereof. It is conceivable that probabilistic knowledge of structural properties of wireless networks can be used as prior information to improve network inference tasks, particularly topology tomography, in practical systems.

This project...

This project will begin with fundamental research into the correct modelling and statistical characterisation of wireless networks designed for particular applications, such as smart meter infrastructure and tactical systems. The results of this research will be exploited to develop new topology tomography algorithms that are optimised for use in the chosen applications. The technical contributions of the project will be accompanied and supported by a number of activities aimed at delivering impact through dissemination and technology transfer. The project is supported by hands-on industrial and government partners, each of which is at the leading edge of its respective field.

The key research themes that will be explored in the project are captured by the following:

• fundamental limits of topology tomography methods;
• optimal active topology discovery techniques suitable for use in practical networks;
• optimal passive topology inference algorithms that can be used to estimate network structure based on limited network observability.

The work will take a rigorous mathematical approach, but will always maintain a focus on practical implications and designs, drawing on advice and inspiration from the project partners.

Key Research Themes

Fundamental Limits

To perform topology tomography in a communication network, data packets conveyed from node to node in the system must be probed or observed in order to glean information about the network state. Fundamentally, it is important to understand how much information about the network topology such activities can yield. A typical engineering problem might be to develop an (optimally) efficient way to estimate topological properties of the network given limited information. A natural question arises: what is the best one could hope to do?

The fundamental limits of topology tomography are related to the latent information contained in the network topology. Such information is often quantified (assuming the topology exhibits some randomness) through the use of Shannon entropy. Indeed, the lower limit on the average description length of a random network topology is the entropy of the random graph model that represents the topology. Little is known about these characteristics in relation to spatial networks, much less the specific example of wireless networks. A goal of this project is to shed light on this relatively unexplored subject.

Topology Discovery

Conventional topology discovery algorithms rely on the propagation of packets through the network that collect node IDs and neighbour tables, and then return to the source with an expected time that is proportional to the number of nodes in the network. Traditionally, such algorithms do not make use of the statistical properties of the network structure. An important engineering task is to construct scalable methods of performing topology discovery in wireless networks, particularly since modern infrastructure networks (e.g., smart meters) may consist of over 1,000 devices.

By exploiting newfound knowledge of the fundamental limits of topology tomography, it will be possible to devise new spatial graph compression methods tailored for the wireless models under investigation in the project to reduce transmission overhead during the discovery process. For example, a solution may be to alter the format of the transmitted data packets during the discovery process to reflect the likely structure of the visible network. Indeed, one may envisage lengthening each transmitted discovery frame - which holds network topology information - in line with the entropy of the observed network (i.e., the lower bound on average description length).

Topology Inference

In some applications, it may not be possible or desirable to actively transmit topology discovery packets through the network in order to estimate topological structures. In a large network, this process could consume unacceptably large amounts of bandwidth and/or time to complete. Instead, one may prefer to passively observe network activity and later to use this information to construct an estimate of the topological state of the network.

To achieve passive topology tomography in an optimal manner, it is important to have a firm understanding of the types and distribution of subgraphs, or motifs, that arise in wireless networks. The statistical properties of graphical structures can be used to design simplified, approximate probabilistic prior models for spatial graphs that capture the essential structural properties while enabling tractable topology inferences. Although not fully accurate, when used as prior distributions, these approximate models will promote network topologies that exhibit the desired structural properties, and hence give a reasonable estimate of the network connectivity.