Optimizing Wireless Communication using Adaptive Packet Sizing andTurbo Codes
Manish S. MittalDepartment ofElectrical and
Computer Engineering,University ofAlabama at
Birminghammmittal@teklinks. com
Jill GemmillDepartment ofAcademicComputing, University ofAlabama at Birmingham
jgemmill@uab. edu
Helmuth F. OrthnerDept. ofHSA - HealthInformatics Program,
University ofAlabama atBirmingham
horthner@uab. edu
Abstract
Unlike wired networks, wireless networks havevery dynamic channel properties and the datacommunication suffers from interference, multi-pathfading and noise. Since wireless devices are mobile,factors such as energy consumption, effective coveragearea and most of all reliability and quality of serviceare of key importance. The 802.11a/b/g wirelessprotocols employ static link layer control and transmitpacketslframes with pre-determined sizes. This paperfocuses on benefits derived from combining adaptivepacketlframe sizing with Forward Error Correcting(FEC) Turbo codes. Protecting the data frames on thechannel, using FEC enhances efficiency of dynamicpacket sizing and is shown to increase energyefficiency and communication range. Adaptive packetsizing software from SmartPackets Inc. and Turbocode simulations are used to discover parameters thatare common to both and affect communicationefficiency. A multi-fold improvement in throughput isfound when these technologies are usedsimultaneously.
1. Introduction
The current standards used for Link Control inwireless networks are based on ideas inherited fromwired links and the concepts of TCP/IP to establishconnections between two terminals. However, wirelesslinks have highly dynamic channel properties andexhibit attributes such as interference, fading, andmulti-path that are random in nature and are difficult tomodel and predict accurately. Therefore a static linklayer control technology is unsuitable for providingoptimum performance in wireless communications.Logically, shorter frame sizes have higher probabilityof passing through a noisy link unharmed. In addition
to increased probability of success, shorter frame sizeaffects other operational parameters such as energyconsumption and effective range of wireless coverage.These advantages are achieved at the cost of reductionin the effective data throughput due to shorter frames.
This tradeoff suggests application of ForwardError Correction (FEC) methods to improve the errorresiliency of the transmitted frame, combined withdynamic adjustment of frame size. Using FEC codeswith dynamic frame sizing would cause effectiveincrease in transmitted frame sizes estimated by theadaptive packet sizing processor. This occurs as FECmasks data corruption at the channel from adaptivesizing module. As the module now perceives betterchannel conditions, it predicts larger packet sizes, andlarger packets improve the overall transmissionefficiency. Turbo Codes [12] were selected as theyimprove performance using prior knowledge ofchannel conditions that enables them to be adaptive bynature and especially suited for wireless channels.This paper demonstrates how adaptive packet sizingtechniques when combined with adaptable FECschemes can improve data throughput andperformance. This result was achieved by identifyingoverlaps in optimal Turbo code and adaptive packetblock sizes.
2. Turbo Codes
Claude Berrou, Alain Glavieux and PunyaThitimajshima [12] discovered turbo codes in 1992 anddemonstrated that turbo codes could reach within 0.5dB of Shannon's limit, a result closer than that of anyother known codes [1]. Use of Turbo Codes achievesbetter throughput at the cost of extra delay due tocomputationally intensive decoding cycles. Turbocodes are very effective for channel coding in wireless
communication domains; they can achieve error ratesin the range of 1Oe-5 in very bad channel conditionswithout compromising on the code rate and easilyreaching within 1 dB of the Shannon limit. Most of theother codes currently in use reach only 3-7 dB of thisbound [13].
2.1. Description of turbo encoder/decoder
The Turbo encoder consists of the following mainfunctional blocks: Pseudo-Random Interleaver,Recursive systematic Convolutional (RSC) encoders,Multiplexer (parallel to serial) and optional puncturinglogic. Block turbo codes are considered in this worksince the input to the encoders are expected to be OSIlayer 2 frames with discreet sizes. As illustrated inFigure 1, Turbo Encoders typically have three copiesof the input data block reach the Multiplexer; the firstblock is passed unmodified, a second data block passesthrough the RSC encoder and the third block isinterleaved and then encoded by the RSC encoder. Thisresults in a three time increase in the data, andtherefore puncturing is used to reduce the number ofinformation bits in the encoded data blocks; the un-encoded data is generally not punctured.
The Turbo Decoder, illustrated in Figure 2,consists of a de-multiplexer, RSC decoders, pseudo-random de-Interleaver and most importantly afeedback loop. The primary data (x) is fed to one of thedecoders after interleaving; this decoder also receivesits corresponding de-multiplexed (x2) data without anyinterleaving. The second decoder receives a copy of theoriginal data (x) without interleaving and itscorresponding de-multiplexed data (xl) withoutinterleaving. Apart from the above inputs, eachdecoder receives an input from the output of the other;suitably interleaved or de-interleaved.
Datainput x
EncoE
infomatino th encd inpt is t piaRte 1=1 I/3IJTuirbo)
Random ~Encode,2r
Figure 1. Architecture of a typical Turbo Encoder
Iterative decoding by using extrinsic and intrinsicinformation of the encoded input is the primarydifference between the contemporary FEC codes andTurbo Codes. The Input from one decoder to the other
contains just the extrinsic information, consisting ofonly the probabilistic estimates generated by thedecoders. The intrinsic information is not sharedbetween the decoders during the iterations but thecurrent intrinsic information is obtained by employingthe extrinsic information exchanged by the decoders inthe previous steps. At the end of the iterations, theintrinsic information at Decoder2 is presented as thebest estimate. Performance improves as iterationsincrease. Increased iterations mean added delay andhigher computational requirements.
A~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~xlxi D ecod
X2
DecodedOutput
X2 2X2_
Turbo -Decoder
Figure 2. Architecture of a typical Turbo Decoder
2.2. Turbo code simulation exampleThe following example demonstrates the actual
data values at the end of each functional block in thesimulation. The values in this example were simulated[9] using a Log-MAP decoder, with a code generatorpolynomial [1 1 1; 1 0 1]. The code rate is 12. At theencoder one byte of data [11 0 1 0 1 1 0] is input. Thedata states for the above input, at the Interleaver,Decoderl and Decoder2 are [11 1 0 0 0 1 1], [1 0 0 0 00 1 0], [1 0 1 0 0 0 1 0] respectively. During thePuncturing process half of the information bits fromeach of the decoder outputs are discarded, hencemaking is a rate 12 encoder. After Multiplexing, the
Aed final data on the channel is [11 1 0 0 0 1 0 0 0 1 0 1 1.ut 0 0]. The channel for this example was simulated as an
AWGN (Additive White Gaussian Noise) channel.The noise corrupted input received at the decoder
is [2.12, 2.65, 4.08, -2.34, -1.27, -1.71, 1.15, -4.53, -
4.38, -2.35, 1.39, -2.41, 0.584, 2.23, -1.79, -2.72]. Theinput is the amplitudes received at the correspondingbit positions of the transmitted data. The intrinsic andextrinsic output at decoderl is [22.3 29 25.2 -25.1 -17.2 -23.7 13 20.6] and [14.8 17.1 12.2 -17.5 -4.82 -105.44 5.32]. The intrinsic and extrinsic output at thedecoder2 is [15.2 13 -12.4 11.9 -13.7 7.53 7.52 -7.53]and [11 4.84 -9.87 9.56 -4.95 4.75 6.36 -3.95]. Theextrinsic decoderl output is used by the decoder2 toarrive at its intrinsic estimate. The output at the Turbo
decoder after a single iteration here is a Signumfunction of decoder2 intrinsic output which is [11 0 10 1 1 0]. Here the correct estimate is arrived in a singleiteration, but this is purely due to chance. Generally,higher number of iterations required for accurateestimates increases as the channel SNR (Signal toNoise Ratio) increases.
3. Adaptive Packet Sizing
Figure 3 symbolically depicts a wireless channelcontaining a random noise impulse train. Un-fragmented transmitted frames are shown intransmission scenario (Txl) and fragmented frames intransmission scenario 2 (Tx2). Although the number ofcorrupted frames in Txl and Tx2 is the same, the datato be retransmitted (Tx2) is 2800 bytes instead of 6000bytes (Txl). In addition, the probability of error forfragmented packets is much lower than larger non-fragmented packets.
Wireless Channel
Txl NF-1 NF2 NF-3 F4 NF-5
Tx2 FAJ J NF-2A I NF-3A NF-4A
LEGEND
I Noise Pulse
NF-1 Data Frame--2000 bytes
I_- -
INF-lA Data Frame FragmentA--1200 bytes-Fb
!1 Data Frame Fragment B- -800 bytes
Figure 3. Effect ofNoise on data transmission in wireless channel
The reduction of data loss achieved by proper
fragmentation improves the efficiency dramatically inthe above example. But fragmenting the frames ingeneral is not very beneficial when the channel is notvery noisy, and would only amount to the increase inthe overhead due to extra header information.
With the highly dynamic noise profile of thewireless channel, it should be beneficial to adapt tothese changes dynamically during communication, andthis line of thought has been explored earlier in [2, 3, 4,5, and 6]. One of the important components requiredfor building an adaptive system is a fairly accuratemonitor for the wireless channel conditions. In [2],Paul Letteiri and Mani Srivastava explored theimprovement shown by dynamic sizing of the MAClayer frames. They revealed that at very high Bit error
Ratios (BER), in the range of 10-5, the maximumgoodput (user seen throughput) that they could achievewas between 400-800 bytes but degraded with furtherincrease in the size of MTU (Maximum TransmissionUnit). They also reported up to 500O reduction inpower consumption due to lower re-transmissionsrequirements, a significant improvement in energyefficiency.. In [4], A. Balk et al attempted to maximizereal-time MPEG-4 video quality and also providedbetter congestion control mechanisms by use of a novelprotocol employing user side bandwidth estimation foradapting to the network conditions. Other adaptiveschemes such as adaptive link layer techniques in [7]and channel state dependent protocols in [8] have beenreported to improve throughput and other performanceparameters.
3.1. Implementation of adaptive sizing
Implementing adaptive packet sizing at the MAClayer is ideal but is impractical to accomplish in currentequipment. One possible alternative could be toadaptively vary the size of the IP layer packets andadjust the MTUs and Maximum fragmentationthreshold of the MAC layer accordingly to avoidmismatch. However, implementation at the IP layerwill not cover important non-IP protocols such as ARPand RARP.
Based on these requirements, the logicalcomponents for implementation were an active orpassive channel condition probe, a software (orhardware) module to process channel information andpredict packet sizes, and a unit to change the size of theoutgoing packets. Active probing involves sendingprobe packets to gauge current channel conditions,requires elaborate models for prediction, and may riskchannel congestion by adding to the amount of datatransmitted. Passive probing, on the other hand,involves measuring the current channel conditions onthe physical radio interface. This method could behighly inaccurate as it does not take into account thecomplete channel, and furthermore, hardwaremodifications would be required to measure channelconditions to the desired accuracy. Since the wirelesschannel conditions can change rapidly due to themobile environment, highly unpredictable noiseinduction etc., accuracy of the calculation at any timewould generally be expected to be best effort
4. Tests and Conclusions
The experiments were primarily designed based onTurbo code simulations [9], adaptive sizing conceptsfrom [2, 3] and implementation by SmartPackets [10];
with a goal of identifying parameters affecting bothtechniques and finding performance improvements atoverlapping values.
4.1. Logical implementation diagram
Figure 4 depicts the logical implementationdiagram of the combined FEC (using Turbo codes) andadaptive packet sizing modules. The size of the packetsis influenced primarily by the MTU of the TCP/IPlayer and requirements for optimization of theavailable bandwidth. UDP streams were used duringtests to enable easy monitoring of jitter, packet delayand packet loss. These parameters effect the overalldata throughput whether the data is streaming content(UDP) or regular internet traffic (generally TCPbased), and hence, are good indicators of overallchannel efficiency and other problems.The size of the packets in the packet stream was
adjusted dynamically based on the decisions made bythe Network Controller or the Packet size decisionprocessor. The Network Controller also shares thepacket size and channel condition information with theFEC Decision Processor module present at the MAClayer. The FEC Decision Processor activates the FECEncoder for outgoing streams for specific channelcondition parameter values. The FEC Encoder, ifactivated, encodes the outgoing frame based on theframe block size and encoding rate as set by the FECDecision Processor.
The Performance testing experiments were conductedindividually for IP layer packet sizing using UDPstreams and variable packet size based Turbo code. Todefine the relation between the above two modules,key common parameters are identified later; these can
be used for development of integrated system andfurther research.
4.2. Turbo codes simulation
The simulation was set up by building on theimplementation of Turbo codes originally written inMATLAB at Virginia Tech. [9]. An AWGN modelwas used and the SNR (Signal to Noise Ratio) valueswere varied using the noise amplitude of the model.Additionally, a randomly generated pulse train withprobability 5*10e-5 was added to emulate impulsenoise. The tests were setup to continuously change theblock frame size of turbo encoder and channelconditions. This was done to determine a range offrame sizes which produces the best Bit Error Rate andFrame Error Rate for near worst case channelconditions.
There are many different parameters that can beadjusted to achieve desired effect and coding efficiencyin the implementation program used. Table 1 belowlists the parameters used in the tests.
Table I
DecodingAlgorithm(SOVA or
Log-MAP)
Log-IvIA usc.
NMAP (Maximum a posteriori) algorithms provideoptimal bit error probability, in contrast, SOVA ishigh speed, low complexity decoding algorithm.[11] The current study is focused on better BERperformance hence Log-MAP is used.
Code [111,101] used for small block size high codingGenerator gain.
15 iterations is an empirical value based on above
Number ofissues. Increasing Iterations improves coding gain
Nuberaiofs at high computational costs. Turbo codes reach anIterathons error floor beyond which increasing iterations has
insignificant effect.Termination An Empirical e value of 10 used, primarily forFrame computational reasons. Lower value has minorErrors effect on overall result, when averaged.
Values used [0: 0.5: 3].Turbo codes are primarily employed for high bit
SNR Range error probability channel environments to achievehigh data rate. The key goal of this work is to testthe performance in worst case scenarios hence lowSNR values are used.
Max. # of Total number of frames was kept at 100 for eachFrames per combination of various parameters to keepFrame Size simulation time in practical ranges.
4.3. Conclusions from Turbo Code simulation
The results of the simulation are shown in Figure5. Turbo code frame sizes were in the range of 500 to1500 bytes, as the main goal was to find the optimumframe/packet size for the 802.1 lb standard. The sameidea is easily extensible to other wireless standards.The BER decreases as the frame length increases up toaround 1300 bytes, beyond which the BER stabilizes toalmost a constant value. The FER curve also followsalmost the same curve and stabilizes at around 1300bytes. It can be safely concluded that, the best BERand FER performance is achieved for larger framelengths in the range of 1100 to 1300 bytes.
Tuarb o o4o p#dorm at 5 dE SNRfo rvn* Fr=#L4 hs
Frme EItr RPh
4.4. Adaptive packet sizing tests
SmartPackets was used to implement adaptivepacket sizing along with a set of tools and utilities.Two Windowsg XP operating system portablecomputers with inbuilt Intelg PRO/Wireless BGwireless cards were used to create an Ad-Hoc network.Furthermore, the average SNR at the receiver wasmaintained in the range of 2-3 dBm by changing thedistance between the Ad-Hoc transmitter and receiver.The SNR was controlled by measuring the signal andnoise strengths at the receiver using the built-in driverutility. The tests were conducted at different timesduring the day over a period of one month. The resultsof the experiments were averaged and tabulated, andthe values are listed in Figure 6 below. UDP packetswere used in the tests to enable accurate measurementof packet loss, delay and jitter. As shown in Figure 6,packets of sizes varying from 1500 bytes to 300 byteswere transmitted and measurements taken withoutSmartPackets being active.
The same tests were repeated with 1500 byteframe and SmartPackets being active, allowingSmartPackets to dynamically change the size. Theresults clearly show a large improvement in theaverage data throughput and percentage of packet losswhen using SmartPackets; but the packet jitter ishigher than seen without SmartPackets. Overall,throughput performance improvement was about 10fold.
4.5. Combining the two technologies
A multi-fold gain can be seen by combiningadaptive packet sizing and Turbo code FEC. Both ofthem have been shown to improve performance in thesame range of frame sizes.
Figure 5. Turbo code performance at 1.5dB for varying FrameLengths
After Smart Packet Optimization10 3-.3781 110 86 78432 .11 104.99
Figure 6. Result data from adaptive packet sizing experiments
Secondly, both of them work well at low SNRvalues. The throughput and packet loss, even afterpacket sizing, can be further reduced by employingturbo codes; which has a high coding gain at low SNRor highly noisy wireless environments. Further, boththese technologies can share the same channelinformation to provide better transmission efficiency.With the use of turbo codes, the possibility of addingdelays in communication increases, and in integratedsystems, the delay can be even more. Apart fromproviding throughput improvement the integratedsystem has inherent properties for protocolindependent implementation in the current standards.
5. Acknowledgments
This project has been partly funded by Federalfunds from the National Library of Medicine, National
Institutes of Health, under Contract No. NO1-LM-3-3513.
6. References
[1] G. P. White, "Optimized Turbo Codes for Wireless Channels",Communications Research Group, Department of Electronics,University of York, UK, 2002
[2] Lettieri, P., Srivastava, M.B, "Adaptive Frame Length Controlfor Improving Wireless Link Throughput, Range, and EnergyEfficiency", IEEE Infocom'98, San Francisco, USA, pp. 307-314, March 1998.
[3] P. Lettieri, C. Schurgers, M. Srivastava, "Adaptive Link LayerStrategies for Energy Efficient Wireless Networking", WirelessNetworks, no. 5, pp.339 355, 1999.
[4] A. Balk, M. Gerla, D. Maggiorini and M. Sanadidi, "Adaptivevideo streaming: pre-encoded MPEG-4 with bandwidthscaling" Computer Networks, 44 (2004) pp. 415-439
[5] Charles Chien, Mani B. Srivastava, Rajeev Jain, Paul Lettieri,Vipin Aggarwal, Robert Sternowski, "Adaptive Radio forMultimedia Wireless Links", IEEE Journal on Selected Areasin Communications, vol. 17, no. 5, May 1999 pp. 793-813.
[6] Jonathan Rosenberg and Henning Schulzrinne, "Integratingpacket FEC into adaptive voice playout buffer algorithms onthe internet", In Proceedings of the IEEE Infocom, pages 1705-1714, March 2001.
[7] P. Lettieri, C. Fragouli, M. Srivastava, "Low Power ErrorControl for Wireless Links," In Proceedings of the ThirdACM/IEEE International Conference on Mobile Computingand Networking 1997 (MobiCom'97), Budapest, Hungary,September 1997.
[8] Christine Fragouli, Vijay Sivaraman, Mani B. Srivastava,"Controlled multimedia wireless link sharing via enhancedclass-based queuing with channel-state-dependent packetscheduling", IEEE INFOCOM 1998 - The Conference onComputer Communications, no. 1, April 1998 pp. 572-580
[9] Yufei Wu, "MATLAB code for experiment on turbo codes", at
[10] Official website of SmartPackets Inc.http ://www.smartpacketsinc.com/index.htm
[11] Fossorier, M.P.C., Burkert, F., Shu Lin, Hagenauer, J., "On theequivalence between SOVA and max-log-MAP decodings"Communications Letters, IEEEVolume 2, Issue 5, May 1998 Page(s):137- 139
[12] C. Berrou, A. Glavieux, and P. Thitimajshima, "Near ShannonLimit Error- Correcting Coding: Turbo Codes", Proceedings ofthe IEEE International Conference on Communications, ICC'93, Geneva, pp. 1064-1070, May 1993.
[13] R. H. Morelos-Zaragoza, "The Art of Error Correcting Codes",1st ed. John Wiley & Sons, 2002.
