Abstract-We consider the problem of determining the maximum capacity of the media access (MAC) layer in wireless ad hoc networks. Due to spatial contention for the shared wireless medium, not all nodes can concurrently transmit packets to each other in these networks. The maximum number of possible concurrent transmissions is, therefore, an estimate of the maximum network capacity, and depends on the MAC protocol being used. We show that for a large class of MAC protocols based on virtual carrier sensing using RTS/CTS messages, which includes the popular IEEE 802.11 standard, this problem may be modeled as a maximum Distance-2 matching (D2EMIS) in the underlying wireless network: Given a graph ( ), find a set of edges such that no two edges in are connected by another edge in . D2EMIS is NP-complete. Our primary goal is to show that it can be approximated efficiently in networks that arise in practice. We do this by focusing on an admittedly simplistic, yet natural, graph-theoretic model for ad hoc wireless networks based on disk graphs, where a node can reach all other nodes within some distance (nodes may have unequal reach distances). We show that our approximation yields good capacity bounds. Our work is the first attempt at characterizing an important "maximum" measure of wireless network capacity, and can be used to shed light on previous topology formation protocols like Span and GAF that attempt to produce "good" or "capacity-preserving" topologies, while allowing nodes to alternate between sleep and awake states. Our work shows an efficient way to compute an upper bound on maximum wireless network capacity, thereby allowing topology formation algorithms to determine how close they are to optimal. We also outline a distributed algorithm for the problem for unit disk graphs, and briefly discuss extensions of our results to: 1) different node interference models; 2) directional antennas; and 3) other transceiver connectivity structures besides disk graphs.
In REF , the problem of finding the maximum possible number of simultaneous transmissions in a network graph is shown to be equivalent to the problem of finding the number of edges in a graph that aren't connected by another edge, a problem which we solve here for the particular class of graphs under consideration.
The distance-2 matching problem and its relationship to the MAC-Layer capacity of ad hoc wireless networks
IEEE Journal on Selected Areas in Communications
IEEE Journal on Selected Areas in Communications
Computer Science