The capacity of an arbitrary ad-hoc network is difficult to estimate due to interference between links. We use a conflict graph that models the interference relationships between links to determine if a set of flow rates can be accommodated. Using the cliques (complete subgraphs) of the conflict graph, we derive constraints that are sufficient for a set of flow rates to be feasible. We compare these clique constraints to an alternate set of sufficient constraints that can be easily derived from the rows of the matrix representation of the conflict graph. These two sets of constraints are particularly useful because their construction and verification may be distributed across the nodes of a network. We also extend the ad-hoc network model to incorporate variations in the interference range, and obstructions in the network. We use packet level simulations in OPNET to compare the throughput achieved by a distributed MAC protocol like 802.11b with the capacity predicted by our theoretical constraints.

If time permits, I will also talk about ongoing work on utilizing these constraints towards a distributed interference-based QoS routing protocol for ad-hoc networks.