Collision avoidance in multi-hop ad hoc networks

Collision avoidance is very important in contention-based medium access control protocols for multi-hop ad hoc networks due to the adverse effects of hidden terminals. Four-way sender-initiated schemes are the most popular collision-avoidance schemes to date. Although there has been considerable work on the performance evaluation of these schemes, most analytical work is confined to single-hop ad hoc networks or networks with very few hidden terminals. We use a simple analytical model to derive the saturation throughput of collision avoidance protocols in multi-hop ad hoc networks with nodes randomly placed according to a two-dimensional Poisson distribution, which, to our knowledge, has not been investigated sufficiently before. We show that the sender-initiated collision-avoidance scheme achieves much higher throughput than the idealized carrier sense multiple access scheme with an ideal separate channel for acknowledgments. More importantly, we show that the collision avoidance scheme can accommodate much fewer competing nodes within a region in a network infested with hidden terminals than in a fully-connected network, if reasonable throughput is to be maintained. This shows that the scalability problem of contention-based collision-avoidance protocols looms much earlier than might be expected. Simulation experiments of the popular IEEE 802.11 MAC protocol validate the predictions made in the analysis.