1、Throughput Enhancement in Wireless LANs via Loss Differentiation,Michael Krishnan, Avideh Zakhor Department of Electrical Engineering and Computer Sciences U.C. Berkeley September 9, 2009,Overview,Background Type of loss in wireless networks Estimating collision probabilities Using estimates to impr
2、ove throughput Modulation rate adaptation Packet length adaptation Future WorkParticipants Dr. Wei Song Colby Boyer Miklos Christine Sherman Ng,2,Motivation & Goal,WLAN extremely easy to set up, but: MAC layer inefficient Link adaptation not optimal Spatial reuse of Access Points (APs) not well unde
3、rstood Throughput suffers: Physical layer bit rate: up to 54 Mbps Actual throughput in practice: 10-12 Mbps Potentially worse as traffic increases Goal: Improve throughput by Differentiating between various types of loss events Estimating their probability of occurrence Appropriately adapting,3,4,Ty
4、pes of Loss 802.11 Network,DCF contention window Direct Collision (DC):nodes start transmitting in same slotHidden Terminal Staggered: one node starts transmitting in the middle of another nodes packet SC1: node in question is first SC2: node in question is secondFading - Channel Errors Link adaptat
5、ion, e.g. ARFincrease rate after N consecutive successful packetsdecrease after M consecutive unsuccessful packets,4,A,B,AP,Components of Loss Probability,PSC2 = Probability of SC2 PDC = Probability of DC given not SC2 PSC1 = Probability of SC1 given not SC2 or DC PC = Total Probability of collision
6、 Pe = Probability of channel error Component probabilities directly useful for link adaptation: PSC2 most affected by sensing PDC most affected by backoff PSC1 most affected by packet length Pe most affected by modulation rate,5,Estimating Loss Probabilities Last Review,Krishnan, Pollin, and Zakhor,
7、 “Local Estimation of Probabilities of Direct and Staggered Collisions in 802.11 WLANs”, IEEE Globecom 2009. Basic idea: Each nodes creates a local “busy-idle” signal for the channel AP compresses and broadcasts its “busy-idle” signal periodically Each node compares its local and AP “busy-idle” sign
8、al to estimate PSC2, PDC and PSC1.,6,Modified ns-2 7 APs, 50 randomly placed nodes Poisson traffic with fixed rate, vary over simulations,Overview,Background Type of loss in wireless networks Estimating collision probabilities Using estimates to improve throughput Modulation rate adaptation Packet l
9、ength adaptation Future Work,7,8,What to do with these estimates?,Link adaptation: Current techniques assume all losses are due to channel error lower rate unnecessarily Make staggered collision problem worse longer packets Adaptive packetization:if most collisions are staggered due to hidden nodes,
10、 need shorter packets Joint throughput optimization of: Modulation rate Packet length FEC Contention window Retransmit limit Transmit power Carrier sensing threshold Use of RTS/CTS Optimization might be different for delay,8,Fairness issues,Overview,Background Type of loss in wireless networks Estim
11、ating collision probabilities Using estimates to improve throughput Modulation rate adaptation Packet length adaptation Future Work,9,Adapting Modulation Rate Using PC Estimate - COLA,Modified version of COLA1: State: For each rate, keep a pair (M,N) Transmit at current rate for 5 seconds Based on t
12、his data, estimate PC Adjust (M,N) for this rate based on PC Continue to transmit until M failed packets or N successes Change rate and adjust (M,N) for previous rate Go to 1.,10,1. Hyogon Kim, Sangki Yun, Heejo Lee, Inhye Kang, and Kyu-Young Choi, “A simple congestion-resilient link adaptation algo
13、rithm for IEEE 802.11 WLANs”, inProc. of IEEE GLOBECOM 2006, SanFrancisco, California, November 2006.,Adapting Modulation Rate Using PC Estimate - SNRg,Algorithm Transmit at current rate for 5 seconds Based on this data estimate PC Based on this PC and loss statistics, estimate Pe Based on Pe and cu
14、rrent rate, estimate average SNR Change rate to theoretical best rate for current SNR Go to 1.,11,12,Simulation Setup,Modified ns-2 802.11b infrastructure mode 7 APs with hexagonal cells 50 nodes placed by spatial Poisson process All nodes send saturated traffic to closest AP Run each algorithm usin
15、g Pc estimates based on: Our estimation technique Empirical counting,12,Throughput Improvement vs ARF(1,10),Up to 5x throughput improvement when collisions are the only source of packet loss Improvement decreases as channel error probability increases,13,32% improvement,no improvement,Per-node impro
16、vement COLA,14,x,y,x,y,Greatest improvement close to AP Distant nodes may have decreased throughput in high-noise environments,-125dBm: 4.18x improvement,-105dBm: 1.27x improvement,Per-node improvement COLA vs SNRg,High noise: -95dBm Few nodes with significant change SNRg outperforms COLA,15,x,y,x,y
17、,COLA: no improvement,SNRg: 1.32x improvement,Overview,Background Type of loss in wireless networks Estimating collision probabilities Using estimates to improve throughput Modulation rate adaptation Packet length adaptation Future Work,16,17,How about packet length adaptation at the MAC-Layer?,Impa
18、ct of packet size on effective throughput Protocol header overhead Larger packet size is preferable Channel fading Smaller packets are less vulnerable to fading errors Direct collisions Direct collision probability is independent of packet size Staggered collisions in presence of hidden terminals Sm
19、aller packets are less susceptible to collide with transmission from hidden terminals,Packet Loss Model,Pure BER-based Used in length adaptation literature Assume constant BER over all packets over all time Simple analysis Does not account for packet-to-packet channel variation Studied in: Song, Kri
20、shnan & Zakhor, “Adaptive Packetization for Error-Prone Transmission over 802.11 WLANs with Hidden Terminals”, IEEE MMSP 2009. Mixed BER-SNR Assume distribution on SNR: Rayleigh, Log-Normal, Rice BER known function of SNR Accounts for channel variation BER is special case,18,Analysis of Throughput v
21、s Length for Mixed BER-SNR Model,Throughput Data Rate x P(success)= Data Rate x (1-Pe) x (1-Psc1)Lp = payload length, Lh = header length, R = modulation rate, Tov = overhead, BER() functions are known For single node, Psc1=0,19,Single-Node Mixed BER-SNR Throughput vs Length Analysis Varying Mean SNR
22、,20,Optimal packet length increases with SNR,Single-Node Mixed BER-SNR Throughput vs Length Analysis Varying SNR Variance,21,Optimal packet length increases with SNR variance,Single-Node Mixed BER-SNR Throughput vs Length Analysis Rician and Rayleigh Fading,22,Rician,Rayleigh,Similar effects with Ri
23、cian/Rayleigh distributions,Conclusions on Mixed BER-SNR Packet Loss Model,High SNR event more important than average SNR event for determining optimal packet length Not sufficient to only consider average SNR or fixed BER Ongoing work: Optimal length as a function of SNR distribution Analyze and ch
24、aracterize what scenarios can benefit from packet length adaptation Extend to multiple nodes: Increasing Tov to account for the increased average access time increases optimal length Increase in SC1s decreases optimal lengthPsc1 is a monotonic function of length throughput vs length unimodal search
25、for optimum packet size,23,Search for Optima Packet Length for Mixed BER-SNR Model,Random search: try different lengths and observe throughput Song et. al. MMSP09 May take long time to get accurate throughput estimates Gradient search (Ongoing work): estimate gradient of throughput with respect to l
26、ength to choose direction to move May converge faster because of ability to move in more accurate direction with better step size Requires estimation of gradient,24,Computing Gradient of Throughput vs Length for Mixed BER-SNR Model (Ongoing Work),Throughput Data Rate x (1-Pe) x (1-Psc1) Computing gr
27、adient requires estimation of each factor Third factor and its derivative estimated in Krishnan et. al. Globecom09,25,Joint Length and FEC Adaptation using Mixed BER-SNR Model (Future Work),Decreasing length combats channel errors and SC1s. If main problem is channel errors, i.e. few SC1s, adapt by
28、adding FEC instead New expression for (1-Pe):kLp number of FEC bitsIx(a,b) regularized incomplete beta function. Assuming Lp is large, derivative w.r.t k is approximated,26,Packet Loss Model,Pure BER-based Commonly used in length adaptation literature Assume constant BER over all packets over all ti
29、me Simple analysis Does not account for packet-to-packet channel variation Studied in: Song, Krishnan & Zakhor, “Adaptive Packetization for Error-Prone Transmission over 802.11 WLANs with Hidden Terminals”, IEEE MMSP 2009 Mixed BER-SNR (Ongoing work) Assume distribution on SNR (Rayleigh, Log-Normal,
30、 Rice) BER is a known function of SNR Accounts for channel variation More general/realistic than BER model, which is a special case,27,28,Packet Length Adaptation for Pure BER-Based Loss Model,Simplified hidden node model: hidden nodes act independently of station in question,Search Algorithm for Pa
31、cket Size,Initialize Lmin, Lmax, and L1 with Lmin L1 Lmax Apply L1 for packetization Measure throughput after Mt = 400 packet transmissions, recorded as Sn(1) Using golden section rule, choose L2 for packetization, L2 = L1 + C (Lmax - L1) Measure throughput after Mt = 400 packet transmissions, recor
32、ded as Sn(2) Compare Sn(1) and Sn(2) and use L1 or L2 to update Lmin or Lmax according to golden section rule Apply the steps recursively until Lmin and Lmax converge,29,30,Network Simulations,Simulation topology 20 middle nodes can sense all traffic K hidden nodes at left side can sense transmissio
33、ns from all nodes except the other K nodes at right side and vice versa K = 2, 4, 6 Saturated total traffic load Memoryless packet erasure channel model Consider packet loss due to direct collision, staggered collision and channel errorK sensing-limited nodes adapt packet length Middle nodes send fi
34、xed-length background traffic,31,Simulation Results,Smaller packet size is selected for higher channel BER to reduce packet loss due to channel error Smaller packet size is selected in presence of more hidden nodes to reduce packet loss due to staggered collision,32,Performance gain is due to trade-
35、off among reduction of header overhead and packet loss Primary Effect: staggered collision probability reduced significantly,Simulation Results: Effect on Collision Probabilities,33,4 hidden nodes transmit an H.264-coded video sequence NBC 12 News at a mean coding rate of 497 kbit/s Average video fr
36、ame transfer delay reduced from 85 ms to 24 ms,Simulation Results: Video Frame Delay,Overview,Background Type of loss in wireless networks Estimating collision probabilities Using estimates to improve throughput Modulation rate adaptation Packet length adaptation Summary and future work,34,Summary a
37、nd Conclusions,Modulation Rate adaptation: Using collision probability estimation up to 5x throughput improvement in collision-limited scenarios Packet length adaptation: Pure BER-based model: staggered collisions have major effect Up to 3x throughput improvement for SC-limited nodes Mixed BER-SNR A
38、verage SNR not sufficient statistic for selection of optimal packet length Gradient of throughput with respect to packet length can be computed using collision probability estimation,35,Future Work: Joint Adaptation of Additional Parameters,Modulation rate with Length/FEC Appropriate length/FEC depe
39、nds on rate since BER is function of SNR & modulation rate Modulation rate highly discretized cant use gradient Adapt modulation rate periodically, Adapt length/FEC in-between adapting rate Transmit power, carrier sense threshold, contention window Optimize globally due to fairness issues Can optimi
40、zation be effectively distributed? Can cheating be discouraged?,36,Future Work: Other Uses of Collision Probability Estimates,Coping with collisions rather than avoiding them Zig-Zag decoding Katabi & Gollakota 08 Partial-packet recovery Use of multiple paths in ad-hoc/mesh network More paths more r
41、esilient to channel errors, but increased traffic more collisions Effect on higher layers TCP collisions closer to congestion loss than fading loss,37,Future Work: Experimental Verification,Universal Software Radio Peripheral (USRP2) + GNU Radio Ported BBN 802.11 code for USRP to work for USRP2,38,MadWifi Accessed hardware registers to get “busy-idle” signal Verifying consistency with packet pattern observed by sniffer, Kismet, in controlled environment,
