On the Macroscopic Effects of Local Interactions in Multi-hop Wireless Networks

The objective of the paper is to provide qualitative insight into the global effects of distributed mechanisms, such as carrier sense multiple access (CSMA) and rate control, on the performance and stability of multi-hop wireless networks. Toward this end, we introduce a linear queueing network model where the service capacity of each node is modulated by the transmission state of its neighbor. We derive lower bounds on the steady-state utilization at each queue of such networks and demonstrate the existence of a phase transition phenomenon, whereby infinitesimal traffic increase at a single node in the network can suddenly render the entire network instable. We also present NS simulation results that show how this phenomenon can actually take place in IEEE 802.11 multi-hop wireless networks. Our results have direct bearing on rate control schemes, in that they indicate a minimum admissible threshold rate required to prevent network instability.