2-1Medium Access Control (MAC) Protocols for Ad hoc Wireless Networks - IDrs. Baruch Awerbuch & Amitabh MishraDepartment of Computer ScienceJohns Hopkins University© Amitabh Mishra & Baruch Awerbuch 2008CS: 647Advanced Topics in Wireless Networks2-2Reading❒ C. K. Toh, Ad Hoc Mobile Wireless Networks, “Chapter 4 – Ad Hoc Wireless Media Protocols”, Prentice Hall❒ Bob O’Hara and Al Petrick, IEEE 802.11 Handbook: A Designer’s Companion, IEEE Press, 1999.❒ Jochen Schiller, Mobile Communications, Section 7.3, Addison-Wesley, 2000.2-3Further Readings❒ Lots of MAC protocols published in Mobicom, Infocom, Globecom, ICC, Mobihoc, WCNC, VTC, etc.❒ CSMA: L. Kleinrock and F. A. Tobagi, “Packet Switching in Radio Channels: Part I – Carrier Sense Multiple Access Modes and Their Throughput-Delay Characteristics, IEEE Trans. On Communications, Vol. COM-23, No. 12, Dec. 1975, pp. 1400-1416❒ MACA: P. Karn, “MACA – A New Channel Access Protocol for Packet Radio”, ARRL/CRRL Amateur Radio 9thComputer Networking Conference, 1990, pp. 134-140.2-4Further Readings❒ FAMA: C. L. Fullmer and J. J. Garcia-Luna_Aceves, “Floor Acquisition Multiple Acsess (FAMA) for Packet-Radio Networks”, Proceedings of ACM Sigcomm’95, Cambridge, MA, Aug. 1995, pp. 262-273.❒ MACAW: V. Bharghavan, A. Demers, S. Shenker, and L. Zhang, “MACAW: A Media Access Protocol for Wireless LANs”, Proceedings of ACM Sigcomm’94, London, UK, Sept. 1994, pp. 212-225.❒ IEEE Computer Society LAN/MAN Standards Committee, “Wireless LAN Medium Access Protocol (MAC) and Physical Layer (PHY) Specifications, “IEEE Std. 802.11”2-5Outline❒ Wireless MAC Issues❍ Hidden terminal problem❍ Exposed terminal problem❍ Capture❒ MAC Performance Metrics❒ Wireless MAC Classification❒ Distributed Wireless MAC Protocols❍ Aloha❍ Slotted Aloha❍ CSMA❍ CSMA/CA❍ 802.11 MAC DCF Backoff❍ Hiper Lan MAC2-6Introduction❒ Multiple access control channels❍ Each Mobile Station (MS) is attached to a transmitter / receiver which communicates via a channel shared by other nodes❍ Transmission from any MS is received by other MSs in the neighborhoodShared MultipleAccess MediumMS 4MS 3MS 2MS 1Node N…2-7Introduction (Cont’d)❒ Multiple access issues❍ Wireless Channel (Wireless medium) is shared among multiple neighboring nodes❍ If more than one MS transmit at a time on the shared media, a collision occurs❍ How to determine which MS can transmit?Shared MultipleAccess MediumMS 4MS 3MS 2MS 1Node N…2-8Wireless Medium Access Control – Why?❒ Access Control protocols define rules for orderly access to the shared medium ❍ Fairness in sharing❍ Efficient sharing of bandwidth❒Need to avoid packet collisions at the receiver due to interference ❍ Different types: Contention protocols resolve a collision after it occurs or try to avoid it. These protocols execute a collision resolution protocol after each collision Conflict-free protocols (e.g., TDMA, FDMA, CDMA) ensure that a collision can never occur. ❒ Mobility❒ Energy Constraints❒ Wireless MACs have been studied heavily since 1970s2-9Channel Sharing TechniquesMedium -Sharing TechniquesStatic ChannelizationDynamic Medium Access ControlSchedulingRandom Access2-10Classification of Wireless MAC ProtocolsWireless MAC ProtocolsDistributedCentralized Random AccessRandom Access Guaranteed Access Hybrid AccessRRADemand Assignment2-11Wireless MAC Issues (1)❒ Wireless medium makes the MAC design more challenging than the wirelinenetworks. ❒ The three important issues are:1. Half Duplex operation –> Either send or receive but not both at a given time2. Time varying channel3. Burst channel errors2-12Wireless MAC Issues (2)1. Half Duplex Operation❍ In wireless, Its difficult to receive data when the transmitter is sending the data, because:  When node is transmitting, a large fraction of the signal energy leaks into the receiver path The transmitted and received power levels can differ by orders of magnitude The leakage signal typically has much higher power than the received signal -> “Impossible to detect a received signal, while transmitting data” Collision detection is not possible, while sending data– CSMA/CD (Ethernet MAC) cannot be used as it is2-13Wireless MAC Issues (3)❒ Half Duplex Operation (Contd.)❍ As collision cannot be detected by the sender, all proposed protocols attempt to minimize the probability of collision -> Focus on collision avoidance2-14Wireless MAC Issues (4)2. Time Varying Channel❍ Three mechanisms for radio signal propagation (T. Rappaport’s book) Reflection – occurs when a propagating wave impinges upon an object that has very large dimensions than the wavelength of the radio wave e.g. reflection occurs from the surface of the earth and from buildings and walls  Diffraction – occurs when the radio path between the transmitter and the receiver is obstructed by a surface with sharp edges Scattering – occurs when the medium through which the wave travels consists of objects with dimensions smaller than the wavelength of the wave2-15Wireless MAC Issues (5)2. Time Varying Channel (Contd.)❍ The received signal by a node is a superposition of time-shifted and attenuated versions of the transmitted signals Æ The received signal varies with time❍ The time varying signals (time varying channel) phenomenon Æ also known as multipathpropagation❍ The rate of variation of channel is determined by the coherence time of the channel Coherence time is defined as time within which the received signal strength changes by 3 dB2-16Wireless MAC Issues (6)2. Time Varying Channel (Contd.)❍ When a node’s received signal strength drops below a certain threshold the node is said to be in fade❍ Handshaking is widely used strategy to ensure the link quality is good enough for data communication❍ A successful handshake between a sender and a receiver (small message) indicates a good communication link2-17Wireless MAC Issues (7)3. Burst Channel Errors❍ As a consequence of time varying channel and varying signals strengths Æ errors are introduced in the transmission (Very likely)❍ For wireline networks the bit error rate (BER) is typically i.e. the probability of packet error is small ❍ For wireline networks the errors are due to random noise❍ For wireless networks the BER is as high as ❍ For wireless networks the errors are due to node