Collision Helps! An Analytical Study of ZigZag Decoding
Ali Parandeh Gheibi, Jay Kumar Sundararajan, Muriel M ́edard · DSpace@MIT (Massachusetts Institute of Technology) · 2009
The nature of the wireless network is intrinsically different from the wired network because of the shared medium among several transmitters. Such a restriction requires a form of scheduling algorithm to coordinate access to the medium, usually in a distributed manner. The conventional approach to the Medium Access Control (MAC) problem is contention-based protocols in which multiple transmitters simultaneously attempt to access the wireless medium and operate under some rules that provide enough opportunities for the others to transmit. Examples of such protocols in packet radio networks include ALOHA, MACAW, CSMA/CA, etc. However, in many of contention-based protocols it is possible that two or more transmitters transmit their packet simultaneously, resulting in a collision. The collided packets are considered lost in the conventional approaches, but Gollakota and Katabi [2] show how to recover multiple collided packets in a 802.11 system using ZigZag decoding when there are enough transmissions involving those packets. In fact, they suggest that each collision can be treated as a linearly independent equation of the packets involved. Therefore, the packets are recoverable only if the system of equations is full rank. ZigZag decoding provides a fundamentally new approach to handle collisions in a wireless setting without using any central scheduler, or knowledge about the network topology such as number of neighbors, etc. In this project, we wish to understand the effects of this new approach to interference management, in terms of the achievable throughput and delay for the multiple access communication. We provide an abstraction of the multiple-access channel when ZigZag decoding is used at the receiver. We use this abstract model to analyze the delay and throughput performance of the system in various scenarios. First, we analyze the scenario when each user has one packet to send. We characterize upper and lower bounds on the expected time to deliver