MoN16: Sixteenth Mathematics of Networks meeting

Alexander Kartun-Giles (Queen Mary University of London) – Euclidean matchings in ultra-dense spatial communication networks

The theoretical upper bound on the data capacity of a wireless link increases whenever it is shared between devices which are brought into closer proximity. This fact is particularly relevant in ultra-dense networks, where inter-point distances begin to have a significant impact on both interference, as is usual, but also this point-to-point capacity. In this talk, we discuss the effect this ultimately has on data rates in ultra-dense base station deployment over a bounded geographic region. We do this by studying the length of a maximal Euclidean matching. This classic model sees pairs of elements of a homogeneous binomial point process of N nodes, drawn from a bounded domain, joined with an edge in such a way that no two edges intersect. Given the many different ways in which this can be done, there is always a shortest matching, where by shortest we mean that the Euclidean lengths of the at most N/2 edges concatenate to form a rectifiable curve which minimises a Euclidean length functional. Studying the scaling with N of this sum is the monopartite Euclidean matching problem. The bipartite case is alternatively a one-to-one correspondence between two different types of node, such as users and cells. The topic is known as matching theory in operations research, as well as economics. We define our model, discuss examples of matchings an anticipated communication scenario, and prove our three main results, which are scaling laws of the one-hop capacity for matchings between near-neighbour points of a binomial point process, a lower bound on the capacity given a perfect matching is found, and convergence of a rescaled capacity to a limiting constant via the so-called replica method from statistical physics. Finally, we explain how to calculate the theoretically maximal capacity of a network under an anticipated stretched exponential path loss model directly applicable to the ultra-dense scenario, and detail what is meant by multihop transport under this matching connectivity constraint.

Return to previous page

Contact: Keith Briggs (mailto:keith.briggs_at_bt_dot_com) or Richard G. Clegg (richard@richardclegg.org)