Random Access MAC for Efficient Broadcast Support in Ad Hoc NetworksSlide 5Broadcast Support Multiple Access (BSMA) ProtocolBroadcast Support Multiple Access (BSMA) Protocol (cont’d)Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Traffic Rate ExperimentSlide 17Random Access MAC for Efficient Broadcast Support in Ad Hoc NetworksKen Tang, Mario GerlaComputer Science DepartmentUniversity of California, Los AngelesLos Angeles, CA 90095http://www.cs.ucla.edu/NRL/wirelessMotivationAd hoc random access MAC protocols (eg 802.11) treat unicast and broadcast packets differentlyUnicast packets are preceded by MAC layer control frames (eg, RTS, CTS)Broadcast packets, on the other hand, are sent blindly without any control frames that can assure the availability of the destinationsNote: The procedure here outlined will work also for multicast (in a dense multicast tree/mesh it is preferable to use MAC broadcast rather than unicast)Broadcast Support Multiple Access (BSMA) ProtocolImproves upon IEEE 802.11’s broadcast featureUtilizes RTS/CTS control frames and negative acknowledgements (NAKs)Assumes radio has DS (direct sequence) capture abilityBroadcast Support Multiple Access (BSMA) Protocol (cont’d)Steps:1. Step 1: Collision avoidance phase2. Source sends RTS to all neighbors and sets timer to WAIT_FOR_CTS3. Neighbors of source, upon receiving RTS, send CTS if not in YIELD state and set timer to WAIT_FOR_DATA4. If source receives CTS, send DATA and set timer to WAIT_FOR_NAK. Else, if no CTS and WAIT_FOR_CTS timer expires, back off and go to step 1. Nodes that are not involved in the broadcast exchange, upon receiving CTS, set their state to YIELD and set their timer long enough to allow for the broadcast exchange to complete5. Neighbors send NAK if WAIT_FOR_DATA timer expires and DATA has not been received6. If source receives NAK before WAIT_FOR_NAK timer expires, back off and go to step 1. Else, if no NAK and WAIT_FOR_NAK timer expires, the broadcast is complete. Go to step 1 and get ready to transmit new DATABroadcast Support Multiple Access (BSMA) Protocol Example1203546RTSCTSDATANAKSimulation ConfigurationsGloMoSim simulator (Parsec based library)Application: CBR trafficTransport: UDP (no congestion/rate control)Routing: On-Demand Multicast Routing Protocol (ODMRP)Mesh topologyForwarding group conceptOn-demand approachSoft stateMAC: BSMA and CSMA (802.11’s broadcast approach)Radio: Capture (threshold based)Channel: 2Mbps, free space propagation modelNodes 1, 3, 5 and 7 are transmitting data to node 4 at the same timeOrchestrated to evaluate the performance of CSMA and BSMA in situations where hidden terminals exist (worst case situation)At high rates, CSMA collapses. BSMA still able to achieve 23%At lower traffic rates, the RTS/CTS/NAK mechanism of BSMA is given time to combat loss due to hidden terminals92% for BSMA while CSMA tops at 45%Recovery is not possible in CSMA once a packet is dropped 0321546 7 8Grid Experiment00.20.40.60.8110ms50ms100ms150ms200ms250msTraffic RatePacket Delivery RatioCSMABSMAGrid ExperimentTraffic Rate Experiment20 nodes that are uniformly placed in a 1000m x 1000m area, each with a radio power range of 250mFive multicast senders and five multicast receiversBSMA shows 33% improvement over CSMA RTS/CTS/NAK mechanism acts as a rudimentary flow control schemeTraffic Rate Experiment00.10.20.30.40.510ms50ms100ms150ms200ms250msTraffic RatePacket Delivery RatioCSMABSMASenders Experiment25 nodes are randomly placed in a 1000m by 1000m area, each with a radio power range of 250m.Five multicast receivers and the number of multicast senders ranges from 1 to 20Inter departure time of packets is 200ms (5 packets per second)With a single sender, the packet delivery ratio is high for both protocols (80%)As number of senders increases, BSMA (20%) quadruples the packet delivery ratio of CSMA (5%)Senders Experiment00.20.40.60.81 5 10 15 20Num ber of SendersPacket Delivery RatioCSMABSMABroadcast Medium Window (BMW)Here is another scheme, Broadcast Medium Window (BMW) to provide robust (but not 100% reliable) MAC broadcastingThe Broadcast Medium WindowConventional window protocol (e.g., TCP) transmits packets in sequence to a single destinationThe “broadcast window” protocol transmits packets by increasing sequence numbers to ALL neighborsThe window protocol “visits” each neighbor in Round Robin order to retransmit packets which the node missed in the broadcast transmissionNote: we assume the node has a list with all its neighbors (this is a common assumption in MANETs)Broadcast Medium Window (BMW) Protocol Example12034RTSCTSDATAACKseqno = 0seqno = 0 - 1seqno = 0 - 2seqno = 0seqno = 0seqno = 0 - 1seqno = 1seqno = 2Traffic Rate Experiment25 Nodes Traffic Rate Experiment00.20.40.60.8110100200300400500Packet Interdeparture Rate (ms)Packet Delivery RatioBMW802.1125 nodes in grid topology, 3 sources and 6 membersBMW outperforms 802.11Under high rate, BMW and 802.11 are comparableBMW reverts to 802.11 unreliable broadcast01 23456 7891011 1213141516 1718192021 222324ConclusionsBoth BSMA and BMW performs well under low to medium transmission rateThey do not guarantee the delivery of broadcast packets, but rather improve upon the deliveryBMW easier to implement (can be implemented at the network level, above 802.11 unicast)To guarantee delivery one must enforce rate/congestion
View Full Document
Unlocking...