Capacity of composite networks: Combining social and wireless ad hoc networks

Abstract

We define composite networks when nodes communicate only with their long-range social contacts and there is no direct link between a node and its long-range contact. Each node has a single long-range contact and all nodes within its transmission range are local contacts for the node. The long-range contact is the destination for each node in the network and since there is no direct link from source to its destination, nodes communicate using multi-hop communications. This is an extension of the famous work by Kleinberg to random wireless ad hoc networks. The throughput capacity of such networks is studied. The routing is based on each node sending the packets to one of its local contacts until the packets reach the destination. The long-range contact distance from a source follows power law distribution with parameter a which is a characteristic of social networks. A tight bound of throughput capacity for different values of a is derived. The results demonstrate that when a increases or equivalently the distance between source and destination decreases, the throughput capacity increases. For α >; 3, throughput capacity of ⊖(1/ log n) is achieved by utilizing simple point-to-point communications where n is the total number of nodes in the network. This is the maximum feasible throughput that can be achieved in point-to-point communications. The result demonstrates the effect of social groups on wireless ad hoc networks. A new parameter called degradation factor is defined which illustrates the asymptotic behavior of networks for large values of n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sup> .