Parallel Interaction MediumAccess for Wireless Ad Hoc Networks

Parallel Interaction Medium Access for Wireless Ad Hoc Networks Marzieh Veyseh marzieh@soe.ucsc.edu Computer Engineering Department, University of California, Santa Cruz Santa Cruz, CA 95064, USA Abstract—The Parallel Interaction Medium Access (PIMA) protocol is introduced to orchestrate channel access in a wireless ad hoc network when nodes are endowed with a single half- duplex radio, and can either transmit multiple packets to multiple destinations in parallel or receive multiple packets from multiple transmitters in parallel using OFDMA. Analytical and simulation results indicate that PIMA attains tremendous improvements in channel throughput compared to MAC protocols aimed at at- taining concurrency via traditional channel switching techniques proposed in the past for multi-channel networks. Index Terms—OFDMA, MAC protocol, multichannel MAC, Ad hoc networks, OFDMA synchronization. I. I NTRODUCTION Prior work on attaining concurrency in medium access con- trol (MAC) has focused on channel switching, network coding, multiple antenna (MIMO), and few works on OFDMA. In multichannel MACs designed for channel switching networks, e.g. 802.11 [1], each radio is assigned to receive or transmit on a single channel by means of different mechanisms, including [2]–[8]: scheduling, negotiations and reservations taking place on a dedicated common channel accessed concurrently or alternately with data channels, the use of a common channel- hopping sequence, or the use of channel-hopping sequences assigned to nodes randomly and learned over time. However, since nodes are limited to transmitting or receiving on a single channel, many problems such as multichannel hidden terminal problem are very obstinate to overcome. Different schemes have been proposed to improve network throughput by using network coding (NC). However, concur- rency in NC is still limited, because a receiver must receive one packet at a time [9], and the gains observed in some schemes (e.g., analog network coding [9]) can be attributed to the ability of a receiver to decode multiple concurrent transmissions under very strict assumptions. Multiple antennas (MIMO) introduce concurrency by en- abling nodes to receive n data streams in parallel [10] or 1 This work was partially sponsored by the U.S. Army Research Office under grants W911NF-04-1-0224 and W911NF-05-1-0246, by the National Science Foundation under grant CNS-0435522, by DARPA through Air Force Research Laboratory (AFRL) Contract FA8750-07-C-0169, and by the Baskin Chair of Computer Engineering. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Defense Advanced Research Projects Agency or the U.S. Government. J.J. Garcia-Luna-Aceves jj@soe.ucsc.edu Palo Alto Research Center (PARC) 3333 Coyote Hill Road Palo Alto, CA 94304, USA eliminate interference on the same channel from as many as (n − 1) neighbors [11] if the nodes are endowed with at least n antennas for the price of higher energy consumption. Orthogonal Frequency Division Multiple Access (OFDMA) [12] has been selected for use in multi-user infrastructure- based environments (e.g., IEEE 802.16 [13] and DVB- RCA [14]). OFDMA joins OFDM with FDMA (frequency division multiple access) to enable concurrency while avoid- ing collisions. In OFDM systems, subcarriers or tones are orthogonal carriers of lower-rate input data streams that result in longer symbol duration compared to channel delay spread to mitigate multipath effects. In OFDMA, a group of non- overlapping subcarriers called subchannels are assigned to each user to enable simultaneous data transmission to a base station. Centralized schemes for scheduling in time and frequency for mesh networks where mesh routers are responsible for channel assignment are discussed in [15], and [16]. Although Kulkarni and Srivastava [17] and Venkataraman [18] propose resource allocation algorithms in terms of power, bit, and subcarriers in ad hoc networks, they do not discuss a complete MAC protocol. This paper demonstrates that using OFDMA at the physical layer constitutes a viable alternative to achieving concurrency. The attained concurrency is much more flexible compared to techniques like channel switching, network coding, and MIMO. Section II introduces the Parallel Interaction Medium Access (PIMA) protocol, which is the first MAC protocol that permits a sender to transmit multiple packets concurrently and a receiver to decode multiple packets concurrently by orchestrating channel access over time and frequency based on OFDMA in ad hoc networks where nodes are equipped with single half-duplex antennas. Section III presents an analytical model and simulation results showing that PIMA provides substantial benefits compared to prior multichannel MAC protocols based on channel switching. II. PIMA: A N EW A PPROACH TO C ONCURRENCY IN A D H OC N ETWORKS A. Physical Layer Synchronization in Time and Frequency In OFDMA networks, a transmitter puts together the data streams for all users after passing them through subcarrier