Minimum Frequencies for the Virtual Maximum MAC Capacity in a Multichannel Ad-Hoc Network

Since the very first work of asymptotic capacity problem in a wireless ad-hoc network, rich variations such as adding mobility, the usage of directional antenna, and introducing infrastructure have been studied. The intention behind adding these technologies is to reduce inter-node interference and the relay burden of nodes because these are the main causes of vanishing throughput in wireless ad- hoc networks. Another way to increase network capacity is to use the utilization of multichannels. However, the most recent result on the capacity of a multichannel ad- hoc network showed that the usage of multichannels and multiple NICs can not break through the same capacity limit as with single channel. More specifically, assuming finite NICs at a node, the per-node throughput of at most Thetaradic(logn/n) can be maintained by utilizing up to Theta(logn/n) channels beyond which capacity loss occurs. In order to give a new perspective on this phenomenon, we define the Minimum Frequencies for the Virtual Maximum MAC Capacity (MFVMC) problem in this paper. The objective of the problem is to find the minimum frequencies to guarantee collision-free transmissions at a given time slot for any maximum matching of a given graph. Focusing our interest to the set of unit disk graphs with the maximum node degree of d, we prove that Theta(d) is the tight bound for the MFVMC problem. We discuss the implication of this result on the asymptotic network capacity in a multichannel ad-hoc network.