The effect of multi-radio nodes on network connectivity -- a graph theoretic analysis

We analyze the gain in network connectivity that is obtained by implementing multiple radio interfaces in the nodes. The multi-radio nodes can act as if the network had effectively multiple physical layers. We model such a network topology by a multigraph and capture the gain by introducing the novel graph theoretic concept of the multigraph advantage. When applied to connectivity, it is the surplus of connectivity over the sum of the individual connectivities, as we put together several graphs to form a "multigraph sum". We prove in a random graph model that this results in a strict super-additive behavior, always yielding multigraph advantage. Moreover, for the most important density range, called moderately dense regime, we prove that the gain grows to infinity with the graph size and the percentage (relative) gain remains constant and does not vanish with growing network size.