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 behaviorRetransmissions Same packets collide againSenders 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∆18264Delivered 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 ZigZagA 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 signalPreamble 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 ChunkDecode 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 GeneralizesFlipped order ∆21122∆1∆1ZigZag GeneralizesFlipped order Different packet sizes 1122∆2ZigZag Generalizes111222333Flipped order Different packet sizes Multiple colliding packets 111222333∆2∆1ZigZag GeneralizesFlipped 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 TestbedUSRPs10% 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 WorkRTS-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 WorkRTS-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 RateRmaxConclusionZigZag 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

Related Documents

Sep 20, 2017

Sep 20, 2017

Sep 21, 2017

Sep 22, 2017

Sep 23, 2017

Oct 2, 2017

Nov 21, 2017

Jan 26, 2018

Feb 22, 2018

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