2-1Medium Access Control (MAC) Protocols for Ad hoc Wireless Networks - IIDrs. Baruch Awerbuch & Amitabh MishraDepartment of Computer ScienceJohns Hopkins University©CS: 647Advanced Topics in Wireless Networks2-2Outline❒ 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-3Contention-based Protocols❒ ALOHA❍ Developed in the 1970s for a packet radio network by Hawaii University. ❍ Whenever a terminal (MS) has data, it transmits. Sender finds out whether transmission was successful or experienced a collision by listening to the broadcast from the destination station. Sender retransmits after some random time if there is a collision. ❒ Slotted ALOHA❍ Improvement: Time is slotted and a packet can only be transmitted at the beginning of one slot. Thus, it can reduce the collision duration.2-4Contention Protocols (Cont’d)❒ CSMA (Carrier Sense Multiple Access)❍ Improvement: Start transmission only if no transmission is ongoing❒ CSMA/CD (CSMA with Collision Detection)❍ Improvement: Stop ongoing transmission if a collision is detected❒ CSMA/CA (CSMA with Collision Avoidance)❍ Improvement: Wait a random time and try again when carrier is quiet. If still quiet, then transmit❒ CSMA/CA with ACK❒ CSMA/CA with RTS/CTS2-5Pure ALOHATimeNode 1 PacketCollision mechanism in ALOHA12Retransmission3Retransmission2Node 2 PacketWaiting a random timeCollision3Node 3 Packet❒ when frame first arrives - transmit immediately ❒collision probability increases:❍frame sent at t0collides with other frames sent in [t0-1,t0+1]2-6Pure (unslotted) ALOHA❒ collision probability increases:❍ frame sent at t0collides with other frames sent in [t0-1,t0+1]2-7Throughput of Pure ALOHAgTsecollisionnoPP2)_(−==, where g is the packet rate of the traffic.2gTSgTe−= The throughput Sthof pure Aloha as: Defining G = gT to normalize offered load, we have184.021max≈=eS The Maximum throughput of ALOHA isGthGeS2−=22201/2GGthdSGe e or GdG−−=− + = = Differentiating Sthwith respect to G and equating to zero gives The probability of successful transmission Psis the probability no other packet is scheduled in an interval of length 2T.2-8Slotted ALOHAAssumptions❒ all frames same size❒ time is divided into equal size slots, time to transmit 1 frame❒ nodes start to transmit frames only at beginning of slots❒ nodes are synchronized❒ if 2 or more nodes transmit in slot, all nodes detect collisionOperation❒ when node obtains fresh frame, it transmits in next slot❒ no collision, node can send new frame in next slot❒ if collision, node retransmits frame in each subsequent slot with prob. p until success2-9Slotted ALOHAPros❒ single active node can continuously transmit at full rate of channel❒ highly decentralized: only slots in nodes need to be in sync❒ simpleCons❒ collisions, wasting slots❒ idle slots❒ nodes may be able to detect collision in less than time to transmit packet❒ clock synchronization2-10Throughput of Slotted ALOHAgTseP−=The probability of successful transmission Psis the probability no other packet is scheduled in an interval of length T.where g is the packet rate of the traffic.gTthgTeS−= The throughput Sthof pure Aloha as: Defining G= gT to normalize offered load, we have368.01max≈=eS• The Maximum throughput of ALOHA is GthGeS−=0=+−=−− GGtheGedGdS• Differentiating Sthwith respect to G and equating to zero gives2-11ThroughputSlotted AlohaAloha0.3680.184GS: Throughput864200.50.40.30.20.102-12CSMA (Carrier Sense Multiple Access)❒ Max throughput achievable by slotted ALOHA is 0.368.❒ CSMA gives improved throughput compared to Aloha protocols.❒ Listens to the channel before transmitting a packet (avoid avoidable collisions).2-13CSMA collisionscollisions canstill occur:propagation delay means two nodes may not heareach other’s transmissioncollision:entire packet transmission time wastedspatial layout of nodes note:role of distance & propagation delay in determining collision probability2-14Kinds of CSMACSMAUnslotted NonpersistentCSMASlotted Nonpersistent CSMAUnslotted persistent CSMASlotted persistent CSMANonpersistentCSMAPersistent CSMA1-persistent CSMAp-persistent CSMA2-15Nonpersistent CSMA Protocols❒ Nonpersistent CSMA Protocol:Step 1: If the medium is idle, transmit immediatelyStep 2: If the medium is busy, wait a random amount of time and repeat Step 1❍ Random backoff reduces probability of collisions❍ Waste idle time if the backoff time is too longGTtheGGeSααα−−++=)21(2For unslotted nonpersistent CSMA, the throughput is given by:Here is the propagation delay, and T is the packet transmission time.S is the throughput and G is offered load. Also, τTτα=2-16Nonpersistent CSMA ProtocolsFor slotted nonpersistent CSMA, the throughput is given by:)1(2αααα+−=−−GTtheGeS2-171-persistent CSMA Protocols1-persistent CSMA Protocol:❒ Step 1: If the medium is idle, transmit immediately❒ Step 2: If the medium is busy, continue to listen until medium becomes idle, and then transmit immediately❍ There will always be a collision if two nodes want to retransmit (usually you stop transmission attempts after few tries)[])1()21()1()1()21()2/1(1ααααααα+−−+−++−−+++++=GGGtheGeGeGGGGGSFor unslotted 1-persistent CSMA, the throughput is given by:For slotted 1-persistent CSMA, the throughput is given by:)1()1()1)(1()1(ααααααα+−−+−−+−+−+=GGGGtheeeeGS2-18p-persistent CSMA Protocols❒ p-persistent CSMA Protocol:Step 1: If the medium is idle, transmit with probability p, and delay for worst case propagation delay for one packet with probability (1-p)Step 2: If the medium is busy, continue to listen until medium becomes idle, then go to Step 1Step 3: If transmission is delayed by one time slot, continue with Step 1❒A good tradeoff between nonpersistent and 1-persistent CSMA2-19How to Select Probability p?❒ Assume that Nnodes have a packet to send and the medium is busy❒Then, Npis the expected number of nodes that will attempt to transmit once the medium becomes idle❒ If Np > 1, then a collision is expected to occurTherefore, network must make sure that Np1 to avoid collision, where Nis the maximum number of nodes that