Decoding 802.11 Collisions

Publish in

Documents

5 views

Please download to get full document.

View again

of 44
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Description
Decoding 802.11 Collisions. Shyamnath Gollakota Dina Katabi. The Hidden Terminals Problem. Collision!. Bob. Alice. The Hidden Terminals Problem. Retransmissions. More Collisions!. Bob. Alice. Can’t get any useful connections. Can we take two collisions and produce the two packets?.
Transcript
Decoding 802.11 CollisionsShyamnath GollakotaDina KatabiThe Hidden Terminals ProblemCollision!BobAliceThe Hidden Terminals ProblemRetransmissionsMore Collisions!BobAliceCan’t get any useful connectionsCan we take two collisions and produce the two packets?PaPaPbPbYes, we can!∆2ZigZagExploits 802.11’s behavior
  • Retransmissions
  • Same packets collide again
  • Senders use random jitters
  •  Collisions start with interference-free bits ∆1PaPaPbPbInterference-free Bits∆2How Does ZigZag Work?11∆1
  • ∆1 ≠∆2
  • Find a chunk that is interference-free in one collisions and has interference in the other
  • Decode and subtract from the other collision
  • ∆2How Does ZigZag Work?11∆12
  • ∆1 ≠∆2
  • Find a chunk that is interference-free in one collisions and has interference in the other
  • Decode and subtract from the other collision
  • ∆2How Does ZigZag Work?31∆122
  • ∆1 ≠∆2
  • Find a chunk that is interference-free in one collisions and has interference in the other
  • Decode and subtract from the other collision
  • ∆2How Does ZigZag Work?331∆124
  • ∆1 ≠∆2
  • Find a chunk that is interference-free in one collisions and has interference in the other
  • Decode and subtract from the other collision
  • ∆2How Does ZigZag Work?531∆1424
  • ∆1 ≠∆2
  • Find a chunk that is interference-free in one collisions and has interference in the other
  • Decode and subtract from the other collision
  • ∆2How Does ZigZag Work?5351∆1264
  • ∆1 ≠∆2
  • Find a chunk that is interference-free in one collisions and has interference in the other
  • Decode and subtract from the other collision
  • ∆2How Does ZigZag Work?7531∆16264
  • ∆1 ≠∆2
  • Find a chunk that is interference-free in one collisions and has interference in the other
  • Decode and subtract from the other collision
  • ∆2How Does ZigZag Work?75731∆18264
  • Delivered 2 packets in 2 timeslots
  • As efficient as if the packets did not collide
  • ∆1 ≠∆2
  • Find a chunk that is interference-free in one collisions and has interference in the other
  • Decode and subtract from the other collision
  • ZigZag
  • A receiver design that decodes collisions
  • As efficient as if the colliding packets were sent in separate time slots
  • Experimental results shows that it reduces hidden terminal losses from 72% to 0.7%
  • AP received a collision signalHow does the AP know it is a collision and where the second packet starts?Time∆Detecting Collisions and the Value of∆AP received signalCorrelateTimePackets start with known preambleAP correlates known preamble with signal
  • Preamble Correlation
  • Detect collision and the value of ∆
  • Works despite interference because correlation with an independent signal is zero
  • ∆CorrelationTimeHow Does the AP Subtract the Signal?
  • Channel’s attenuation or phase may change between collisions
  • Can’t simply subtract a chunk across collisions
  • Alice’s signal in first collisionAlice’s signal in second collisionSubtracting a Chunk
  • Decode chunk into bits
  • Removes effects of channel during first collision
  • Re-modulate bits to get channel-free signal
  • Apply effect of channel during second collision
  • Use correlation to estimate channel despite interference
  • Now, can subtract!
  • What if AP Makes a Mistake?∆1What if AP Makes a Mistake?Bad News: Errors can propagate311∆222Can we deal with these errors?∆1What if AP Makes a Mistake?Good News: Temporal DiversityA bit is unlikely to be affected by noise in both collisions ∆2Get two independent decodings∆2∆1AP Decodes Backwards as well as Forwards22311Errors propagate differently in the two decodingsWhich decoded value should the AP pick?For each bit, AP picks the decoding that has a higher PHY confidence [JB07, WKSK07]ZigZag GeneralizesZigZag Generalizes
  • Flipped order
  • ∆21122∆1∆1ZigZag Generalizes
  • Flipped order
  • Different packet sizes
  • 1122∆2ZigZag Generalizes111222333
  • Flipped order
  • Different packet sizes
  • Multiple colliding packets
  • 111222333∆2∆1ZigZag Generalizes
  • Flipped order
  • Different packet sizes
  • Multiple colliding packets
  • Capture effect
  • Subtract Alice and combine Bob’s packet across collisions to correct errors
  • Pa1Pa2PbPb3 packets in 2 time slots  better than no collisionsPerformanceImplementation
  • USRP Hardware
  • GNURadio software
  • Carrier Freq: 2.4-2.48GHz
  • BPSK modulation
  • TestbedUSRPs
  • 10% HT, 10% partial HT, 80% perfectly sense each other
  • Each run randomly picks an AP and two clients
  • Co-located 802.11a nodes to find out about HTs and created the same collision patterns by the USRPs
  • 802.11aThroughput ComparisonCDF of concurrent flow pairs ThroughputThroughput ComparisonPerfectly Sense Partial Hidden TerminalsHidden TerminalsCDF of concurrent flow pairs 802.11ThroughputThroughput ComparisonHidden Terminals get high throughputCDF of concurrent flow pairs ZigZag802.11ThroughputThroughput ComparisonZigZag Exploits Capture EffectCDF of concurrent flow pairs ZigZag802.11ThroughputZigZag improved average Throughput by 25%Throughput ComparisonHidden TerminalsCDF of concurrent flow pairs ZigZag802.11ThroughputImproved hidden terminals loss rate from 72% to 0.7%Is ZigZag as efficient as if the colliding packets were sent in separate slots?
  • For every SNR,
  • Check that ZigZag can match the BER of collision-free receptions Is ZigZag as efficient as if packets were collision-free Receptions?Bit Error Rate (BER)SNR in dBIs ZigZag as efficient as if packets were collision-free Receptions?Collision-Free ReceptionsBit Error Rate (BER)SNR in dBIs ZigZag as efficient as if packets were collision-free Receptions?Collision-Free ReceptionsBit Error Rate (BER)ZigZag-Decoded CollisionsZigZag is as efficient as if the colliding packets were sent separatelySNR in dBThree Colliding SendersCollision!ChrisBobAliceNodes picked randomly from testbedThree Colliding SendersAliceCDF of runs BobChrisPer-Sender ThroughputZigZag extends beyond two colliding sendersRelated Work
  • RTS-CTS
  • Excessive Overhead; Administrators turn it off
  • Interference Cancellation
  • Unsuitable for 802.11 because of bit rate adaptation
  • RmaxInterference cancelation operates on one collision UndecodableBob’s Info RateAlice’s Info RateRmaxRelated Work
  • RTS-CTS
  • Excessive Overhead; Administrators turn it off
  • Interference Cancellation
  • Unsuitable for 802.11 because of bit rate adaptation
  • RmaxZigZag operates on two collisions Can decodeBob’s Info RateAlice’s Info RateRmaxConclusion
  • ZigZag is a receiver design that resolves collisions
  • It is as efficient as if the colliding packets were sent in separate time slots
  • It reduces hidden terminal losses from 72% to 0.7%
  • It enables aggressive MAC  More concurrency
  • Related Search
    We Need Your Support
    Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

    Thanks to everyone for your continued support.

    No, Thanks