This is to certify that the thesis entitled Side-Information Enhanced Localized Puncturing for Rate- Adaptive, Reliable and Stable Wireless Protocols presented by Ahmed Majeed Khan has been accepted towards fulfillment of the requirements for the MS degree in Electrical Engineering /: // /// // Major Profesrs/rs Signature Awst 9, 2010 Date MSU is an Affirmative Action/Equal Opportunity Employer LIBRARY Michigal LStam University -.-.-.-.-.n.-,- -.-.-.- . . . . . . . l . A . . -- . .- -- ---~- u.-o----»-v-----.—.-------.-.--—---.-c-.—.—---——--—--— -- PLACE IN RETURN BOX to remove this checkout from your record. TO AVOID FINES return on or before date due. MAY BE RECALLED with earlier due date if requested. DATE DUE DATE DUE DATE DUE 5/08 KzlProilAccsPresIClRClDaleDue,indd SIDE-INFORMATION ENHANCED LOCALIZED PUNCTURING FOR RATE- ADAPTIVE, RELIABLE AND STABLE WIRELESS PROTOCOLS Bv Ahmed Majeed Khan A THESIS Submitted to Michigan State University in partial fulfillment of the requirements for the degree of MASTER OF SCIENCE Electrical Engineering 2010 ABSTRACT SIDE-INFORMATION ENHANCED LOCALIZED PUNCTURING FOR RATE-ADAPTIVE, RELIABLE AND STABLE WIRELESS PROTOCOLS By Ahmed Majeed Khan Time varying wireless channels are inherently susceptible to more errors than classical (wired) media due to their vulnerable nature. The errors which are not corrected by the physical layer are called Residual Errors, and residual errors result in link layer packet draps. Design of wireless protocols that exploits useful data, the data which was received correctly, in a received corrupted packet can benefit network’s throughput substantially. A common way to control errors depends on feedback from channel and several previous works made use of Rate-Compatible Punctured Codes to adapt code rate to channel conditions but none of these took into account the bursty nature of wireless channels. The primary objective of this thesis is to fill this gap. In our work we consider side-information enhanced localized puncturing to adapt the rates of channel codes to cope with time-varying wireless channel conditions. To give proof of our idea, we employ rate-adaptive hybrid framework in the domain of LDPC codes and embed them in wireless networking protocols. To the best of our knowledge, this is the first effort to enhance puncturing efficiency using side-formation from PHY/MAC layer and perform the puncturing operation in a localized manner. The proposed approach does not require any modification in subsequent layers, and it achieves significant gains in throughput efficiency, while ensuring reliable and stable transmission of data. To my parents ACKNOWLEDGMENTS All glory be to the most praiseworthy who showered His countless blessings on me throughout the span of my life. With the prolific praise of the Owner of Honor, I desire to begin a limitless praise, with which He is pleased and I cite His own words; ”All praise to Allah, the Lord of the worlds”. The Quran (39:75). I am honored to have one of the most distinguished scholars, Professor Hayder Radha, as my advisor. I would like to thank him for his support throughout my stay at MSU. I found him an extremely intelligent researcher, exceptionally intellectual advisor and an excellent teacher. This work could not have been possible without his ever critical attitude towards my neophyte research ideas, followed by his tremendous encouragement to heighten my confidence. I am obliged to my family, especially my parents, for their selfless support throughout my life, and particularly during the span of this work. I am running short on words to express my sentiments towards my parents for their gracious deeds and self—sacrificing exertions to empower my advancement. Accomplishment of this work is an implicit consequence of my Fathers vigorous attitude to boost my motivation and enthusiasm, and my Mothers affectionate prayers. I am also thankful to my Baba lee, Nani Amma, Ayesha, Amenil, Rabii, Salahudin, Marium and lqra for their unbounded yet unconditional love, and having absolute faith in me. Life in the US could not have been easier in the absence of steadfast friends and wonderful colleagues and they deserve a special mention here. Stating in alphabetical iv order, I found companions like Awais, Brig. Qaiser, Hassan Aqeel, Jawad, Khawar, Sajjad bhai, Shahzad, Tariq bhai, Usman bhai, Waqar, and Zubair who kept my morale high and made my stay a superb experience, here at MSU. Lastly I want to extend my gratitude to my advisory committee members, Professor Jack Deller and Professor Jonathon Hall, for their uninterrupted patronization during the course of this work. Their extensive feedbacks not only opened new horizons of research for me, but also endowed me with insights into intricate engineering concepts. I am fortunate to have their persistent contribution and involvement in my work. Table of Contents List of Tablesvul List of Flglll‘BSlX Abbreviations and Acronymsx1 Chapter 1 Introduction 1.1- Motivation 1.2- Research Problem 1.3- Thesis Orgamzatnonl Chapter 2 Nle-l Background... 13 2.1- LDPC Codes... 13 2.1.1- 2.1.2- 2.1.3- 2.1.4- 2.1.5- Encoding of LDPC codes 13 Decoding of LDPC Codes... 15 LDPC Decoding on BBC... ....19 Asymptotic Analysis of Belief Propagation & Densnty Evolution ...... Degree Distributions for Nodes in LDPC Code22 2.3- Residual ErrorsZ7 2.4- Channel Characterization............................................................................29 Chapter 3 Code Design and Working of PRAISE... 32 3.1- Density Evolution Tools... 32 3.1.1- 3.1.2- LDPC Online Optimisation Tool: 33 LDPC Online Density Evolution... 35 3.2- Designing Puncturing Fraction537 Chapter 4 The Channel Model43 Chapter 5 Experimental Setup... 50 5.1- Software- Defined Radios: 50 vi 5.2- GNU Radio... ... ... 5.3- Universal Software Radio Peripheral 5.4- Daughter-Boards with USRP... 5.5- Motivation for GNU-USRP Platform 5.6- Layered Architecture 5.7- Experimental TestBed Chapter 6 Analysis of Burstiness in a Packet... 6.1- Distribution of Errors' 1n a Packet... 6.2- Bit Error Rate (BER) vs. Cumulative Densnty Function (CDF) 6.3- End- to- End (EZE) Burst' m a Packet... Chapter 7 Results, Conclusions and Future Work .......84 ........87 ..........91 ....95 7.1- Wireless Channel Metric BER... 7. 2- Wireless Channel Metric PER... 7. 3- Analysis of Results for Different Channel Metrics 7. 4- Conclusions and Future Directions... References... ..................... ......... ............ ...... ............... ...... .l............. ......I.. ... ............ .... vii . .........51 ........52 ....53 54 56 58 .......66 ....67 71 78 98 List of Tables Table Ill-l: LOPT Parameters and Results34 Table Ill-ll: LODE Parameters and Results for Threshold Search......................36 viii List of Figures Figure l-l: Flow Chart of PRAISElO Figure 11-]: Example of an LDPC code25 Figure "-11: Residual ErrorsZB Figure ll-lll: Throughput and goodput measurement at Link Layer of the protocol stack29 Figure 11- IV: Two examples of channels. (a) The Binary Erasure Channel (BEC) with erasure probability a, and m(b) The Binary Symmetricm Channel (BSC) with error probability 8.. ...31 Figure lV-l: Cascaded BEC and BSC Channels with erasure and error probabilities a and s respectively................................................................45 Figure lV-ll: Markovian Channel Model49 Figure V-l: Layered Architecture of our Experimental Setup57 Figure V-Il: Experimental Setup to see Effects of Environment and Fading Factors61 Figure V-lll: Experimental Setup to see Effects of Mobility Factor.....................61 Figure Vl-l: Distribution of Errors in Traces with PER = 30-40%.......................69 Figure Vl-ll: Distribution of Errors in Traces with PER = 60-70%.....................70 Figure Vl-lll: Distribution of Errors in Traces with PER = 80-90%....................70 Figure Vl-IV: BER vs. CDF72 Figure Vl-V: EZE Burst Length for Traces with PER = 40-50%............................74 Figure VI-Vl: EZE Burst Length for Traces with PER = 70-80%...........................75 ix Figure Vl-Vll: EZE Burst Length for Traces with PER = 80-90%....................... Figure VI-Vlll: EZE Burst Length Figure VII-l: Throughput Vs. Channel BER Figure VII-ll: Goodput Vs. Channel BER Figure VII-Ill: Throughput Vs. Channel PER Figure Vll-lV: Goodput Vs. Channel PER Figure Vll-V: Channel BER vs. Channel PER ..75 76 .85 .87 .89 .91 .94 ACE ACK ADC ARQ BEC BER BP BSC c-node CDF CRC CS CSI DAC dB DH Abbreviations and Acronyms Automatic Code Embedding protocol Acknowledgement Analog to Digital Convertor Automatic Repeat Request Binary Erasure Channel Bit Error Rate Belief Propagation algorithm Binary Symmetric Channel Check Node Cumulative Density Function Cyclic Redundancy Check Conventional Standard protocols Channel State Information Digital to Analog Convertor DeciBeH Data Host PC xi DE 06 EZE Eb/No ED FEC FPGA GHz HARQ HEEP IEEE LDPC LLR LODE LOPT LoS Density Evolution Data Ghost computer End-to-End Energy per Bit to Noise power spectral density ratio Error Detection Forward Error Correction Field Programmable Gate Array Giga Hertz Hybrid Automatic Repeat Request Hybrid Erasure-Error Protocols Institute of Electrical and Electronic Engineers Internet Protocol Low-Density Parity—Check codes Log Likelihood Ratio LDPC Online Density Evolution LDPC Online Optimization Tool Line of Sight xii MAC MIT hAS/s NACK PDF PHY PER pmf PRAISE RA RASE RF RHC RS SDR SEFEC Medium Access Control layer Massachusetts Institute of Technology Million Samples per Second Negative Acknowledgement Probability Density Function Physical Layer Packet Error Rate Probability Mass Function Puncturing for Rate-Adaptability of Reliable and Stable wireless protocols Repeat Accumulative Reliable and Stable protocol Radio Frequency Rate-adaptive Hybrid (erasure-error) Codes Reed Solomon codes Software Defined Radio Side-information Enhanced transmission in presence of Forward Error Correction xiii SNR TCP USB UDP USRP v-node var Signal to Noise Ratio Transmission Control Protocol Universal Serial Bus User Datagram Protocol Universal Software Radio Peripheral Variable Node Variance xiv Chapter 1 - Introduction 1.1- Motivation: Despite the tremendous promise of computer networks, they suffer from errors and losses in the presence of network congestion and transmission medium degradation. This results in decreased end-to-end network bandwidth utilization. Wireless channels are more prone to errors than wired media due to their highly time-varying nature. The design considerations for the wireless networks differ substantially from the wired media due to the increased error—rate. The designers of the wireless networks introduce enhanced robustness at the physical (PHY) and MAC layers of the protocol stack in order to cater for these errors. Some of these errors are not corrected by the physical layer, called as Residual Errors, and such errors result in link layer packet drops. Traditional network protocols like IEEE 802.11 ARQ schemes drop packets and request retransmission even if a single bit is in error. This design strategy leads to the wastage of useful data in the packet, the data which was received correctly. Design of wireless protocols that exploits useful data in a received corrupted packet can benefit network’s throughput substantially and can result in significant improvement of end-to-end network utilization. Some previous works like Hybrid ARQ I/ll (HARQ-l/ll) [38, 39] use some sort of error correction to improve wireless networks bandwidth. In fact more recent works like Automatic Code Embedding (ACE), Reliable and Stable (RASE), and ZIPTX [34, 40, 37] exploit partial packet recovery to harness the power of useful data in a corrupted packet. All of these works rely on some sort of error correction scheme and require feedback from the receiver about channel conditions. A common way to control errors is to rely on the Channel State Information, and uses it to predict suitable code rate under a given channel condition. In this way, controlled redundancy is added to data based on predicted channel conditions. So the worse the channel conditions are, lesser is the code rate and vice versa. Several previous works [29, 30, 31, 32, 33] used puncturing to adapt to the time-varying network conditions and the resultant codes are called as rate-compatible punctured codes. leongseok et al. [36] applied this idea to LDPC codes to find rate-compatible punctured LDPC codes with a single decoder for ’mother’ and ’daughter’ codes. Puncturing can be viewed as an erasure channel; hence, puncturing over a wireless channel leads to the reception of hybrid erasure-error codes at the decoder end. But the above-mentioned works [29, 30, 31, 32, 33, 36] focus on inherent code properties to design channel codes, and do not take into account the channel properties while designing puncturing patterns. In this way, there is a room to design puncturing patterns, based on wireless channels characteristics and inherent properties, to adapt channel code rates to time-varying wireless channel conditions. The primary objective of this thesis is to fill this gap. We define a channel to be in ’On’ (’Off’) state If packets transmitted through it experience small (large) number of errors. Wireless channels are bursty in nature and a channel in 'On’ (’Off’) state has higher probability of staying in ’On’ (’Off’) state than to go into ’Off’ (’On’) state. In other words, wireless channels have memory such that next state is dependent on previous state(s), which determines the depth of Markov (hidden Markov) chains used to model them. So, if a channel is in ’Off’ state, it experiences errors at all (bit/byte/packet) levels in a bursty fashion. We take into account this inherent property of wireless channels to design puncturing patterns to adapt code rates to cope with bursty channel errors. Furthermore, we rely on side-information in the form of reliabilities of source symbols received from PHY/MAC layer to design these puncturing patterns and the retransmission data. In more explicit words, this thesis focuses on designing localized puncturing patterns for rate-adaptability of wireless channel protocols to cope with vulnerable, error-prone, and time-varying wireless channel conditions. 1.1- Research Problem: In our work, we consider localized puncturing for channel codes, particularly focusing on LDPC codes. We show that localized puncturing can lead to construction of rate- adaptive hybrid erasure-error codes (RHCs), which in turn, can be used to adapt rate of channel codes in network protocols to perform well in varying network conditions. To the best of our knowledge, this is the first effort to enhance puncturing efficiency by performing it in a localized manner, leading to RHCs, using side-formation from PHY/MAC layer. To give proof of our idea, we employ rate-adaptive hybrid framework in the domain of Low-Density Parity-check (LDPC) codes and embed them in wireless networking protocols. A discrete random process with the property that the next state depends only on the current state is called as Markov Chain. The Markov property states that the conditional probability distribution for the system at the next step, and in fact at all future steps, given its current state depends only on the current state of the system, and not additionally on the state of the system at previous steps. We define a channel to be in ’On’ (’Off’) state if packets transmitted through it experience small (large) number of errors. Wireless channels are bursty in nature and a channel in ’On’ (’Off’) state has higher probability of staying in ’On’ (’Off’) state than to go into ‘Off’ (’On’) state. In other words, wireless channels have memory such that next state is dependent on previous state(s), which determines the depth of Markov (hidden Markov) chains used to model them. So, if a channel is in 'Off’ state, it experiences errors at all (bit/byte/packet) levels in a bursty fashion. We take into account this inherent prOperty of wireless channels to design puncturing patterns to adapt code rates to cope with bursty channel errors. Furthermore, we rely on reliabilities of source symbols received from PHY/MAC layer to design these puncturing patterns and the retransmission data. In order to keep the discussion generic and not dependant on a particular implementation or standard, we consider three rather abstract communication schemes: 1) transmission over error/erasure channels, which represents the Conventional Standard (CS) protocols, like IEEE Automatic Repeat Request (ARQ) schemes; 2) transmission in the presence of a Forward Error-Correction (FEC) based schemes, like Hybrid ARQ [38, 39] and more recent schemes like ZIPTX [37], Automatic Code Embedding (ACE) [34], and Reliable and Stable (RASE) [40]; 3) Side-information Enhanced (transmission in presence of both, erasures and errors,) using a Forward-Error Correction scheme (SEFEC) like the proposed scheme, Puncturing for Rate Adaptability of Reliable and Stable (PRAISE) Wireless Protocols. The three communication schemes considered by us can be explained by considering two generic aspects: 1) forward error correction; 2) feedback mechanism. Forward-error correction part can simply be segregated into two categories consisting of presence or absence of FEC. Feedback mechanism can have many variants, ranging from simple binary feedback about reception of correct/false packet like in case of ARQ, to feedback with flags requesting additional parity data for corrupted packets like in case of recent protocols like ACE [34] and RASE [40]. So under these two aspects, the following happens 1) CS: the conventional standard protocol contains no forward error correction and requests the same packet even if a single bit is in error, example being IEEE802.11 ARQ scheme. In IEEE802.11 ARQ protocol, error-detection information (ED) bits are added to data to be transmitted (such as cyclic redundancy check, CRC) and retransmissions are solution for losses. If a corrupted packet is received, it is discarded without regard to the number and location of errors. This methodology ensures that the packet would eventually be recovered. However, this approach leads to a great deal of throughput degradation as even a single bit error leads to packet drops resulting in discard of a large number of correctly received data bits, ending up ’wasting’ a lot of 2) useful data. Thus, network utilization deteriorates rapidly as channel bit error rate (BER) increases. FEC: FEC based protocols, which represent schemes like IEEE802.11 Hybrid ARQ schemes [38, 39] and more recent schemes like ZIPTX [37], ACE [34) and RASE [40], contain some sort of forward error correction and request additional parity data in case of reception of a corrupted packet. Hybrid ARQ (HARQ) protocols are proposed as an alternative to CS. In HARQ protocols, forward error correction (FEC) bits are also added to the existing Error Detection (ED) bits, such as Reed-Solomon code, low-parity density-check code or Turbo code. In this way, these schemes reduce the number of re-transmissions as required in case of ARQ by making use of incremental channel codes. However, both ARQ and HARQ based approaches do not address the throughput stability issues in varying channel conditions, and thus lead to a great deal of throughput inefficiency. Other protocols like ZIPTX and ACE address the issues of reliability and/or stability in varying channel conditions but these fall short on many fronts. ZIPTX, though provides a working system, ignores any aspect of stability. ACE takes into account both the issues of reliability and stability by embedding channel codes using well-defined code rates but ACE, i) lacks a practical demonstration system, ii) do not consider rate—adaptability to address throughput efficiency in changing network conditions. 3) SEFEC: SEFEC is an alternative to above schemes. Similar to FEC based schemes, an SEFEC scheme requests additional parity using feedback flags, but the requested parity data is localized and request depends upon side-information received from physical (MAC) and link layers. 50 SEFEC is a cross-layer design which extracts beliefs associated with received data either at MAC/physical layer, or at link layer and decides to requests additional parity data for a particular subset of code depending on values of beliefs for a particular subset of code. Some previous works [35, 41, 42] have proposed cross-layer designs for multimedia applications to overcome throughput degradations and performance limitations imposed by traditional protocols. An example of such a work is UDP Lite [41], which relies on the error-resilient nature of multimedia content and makes adjustments to the protocol stack at the transport and the link layers in order to improve the bandwidth utilization. A major drawback of the existing cross-layer protocols is that their implementations require key modifications in transport and application layers. However the proposed cross-layer SEFEC design requires no modification in the subsequent layers since a single decoder is required for ’mother’ and ’daughter’ codes and side-information used to request parity data is received from physical (MAC) and link layers. Therefore, and unlike receivers of FEC- based schemes, SEFEC receiver has RHCs, is rate-adaptive depending on varying channel conditions, distinguishes between erasures and errors in a received packet, and does not require any modification in transport and application layers. Suppose we have k data-bits to be transmitted over a wireless channel and we make it bit codeword with those k bits such that rate of the code is: r= ; k 2 Pr[x,- = o |y,] — 1 = (L ‘ 1)/(L + 1) = tanh(l/2) ......... (2.7) where L = L (x, lyi) and l = In L. Therefore, we obtain: 1 + ( Ill=1tanh(li/2) > 1 -(Ill=1 tanh(li/2)) InL (x1 :I: :l: x) |y1,...,yl) = In ......... (2.8) Where I,- = InL (x, lyi). For the derivation of the BP algorithm for LDPC codes [3], let mg? be the message passed from message node v to check node c at the It" round of the algorithm. (1) CU (0) . At round 0, mm Similarly, define m is the log-likelihood of the message node v conditioned on its observed value, which is independent of c. Let us denote this value by mv. Then the update equations for the messages under belief-propagation can be described as: 17 l . ...3 = mv+ my]; , lfl _>_ 1 ......... (2.9) m(l)_ln1+ Hv'cev \{v} tanh(mv’c/2) _l—IUEVC \{U} tanh(m1(;l')c/2) ......... (2.10) Where, CV is the set of check nodes incident to message node v, and V; is the set of message nodes incident to check node c. The computations at the check nodes can be simplified further by performing them in the log-domain, in the form of log-likelihood ratios. Shokorollahi [4] suggests since the value of tan h(x) can be negative, we need to keep track of its sign separately. As per his method, let y be a map from the real numbers [-00, 00] to ( F2 * [0, 00] ) defined by: -( (ml) y (x) — sgn(x), —In tanh —2— ......... (2.11) So in this case, sgn(x) can be set as: sgn(x) = 1, if x _>_ 1 and sgn(x) = 0, otherwise) It is clear that y is bijective, so there exists an inverse function y ‘1. Moreover, y(xy) = y(x) + y(y) ......... (2.12) Where, addition is component-wise in F2 and in [0,00]. Then it can be shown that: 18 mg} = ‘1 2 y (ms-21)) ......... (2.13) v'eVC {17} In practice, belief propagation may be executed for a pre-specified maximum number of rounds or until the passed likelihoods are close to certainty under pre-determined thresholds, whichever is achieved first. Some authors use the term Certain Likelihood to denote beliefs, where a certain likelihood is a likelihood in which In L (x | y) is either 00 or—00.Ifiti500,thenPr[x=0ly] = 1,andifitis—00,thenPr[x= 1|y]=1. To estimate the running time of the belief propagation algorithm, it is important to note that the algorithm traverses the edges in the graph and the graph Is sparse. So, the number of edges traversed in each round of the algorithm is very small. Moreover, if the algorithm runs for a pre-specified constant number of times, then each edge is traversed a constant number of times, and the algorithm uses a number of operations that is linear in the number of message nodes. So, the running time is directly proportional to the block length of the code. Another important note about belief propagation is that the algorithm itself is entirely independent of the channel used, though the messages passed during the algorithm are completely dependent on the channel. It can be noticed that belief propagation is in general less powerful than maximum likelihood decoding. [15] 2.1.3- LDPC Decoding on BEC: Belief propagation’s application to LDPC codes over the BEC with erasure probability a constitutes a very typical example of the algorithm. Because of the binary nature of the 19 messages, belief propagation on the erasure channel can be described much easier in the following: 1- Initialization: This step constitutes the initialization of the values of all the check nodes to zero. 2- Direct Recovery: This step is performed for all message nodes 12. In this step, if the node is received, then add its value to the values of all adjacent check nodes and remove v together with all edges originating from it from the graph. 3- Substitution Recovery: For check nodes, if there is a check node c of degree one, substitute its value into the value of its unique neighbor among the message nodes, add that value into the values of all adjacent check nodes and remove the message nodes and all edges originating from it from the graph. This algorithm was first proposed in [12]. It is clear that the number of operations that this algorithm performs is proportional to the number of edges in the graph. 50 for sparse graphs the algorithm runs in time linear to the block length of the code. 2.1.4- Asymptotic Analysis of Belief Propagation and Density Evolution: The messages passed at each round of the belief propagation algorithm are random variables. The update equation correctly calculates the corresponding log-likelihood based on the observations, if the incoming messages are statistically independent at every round in the algorithm. Many authors have questioned the validity of this assumption especially when the number of iterations is large. In fact, the independence 20 assumption is true for the first 1 rounds of the algorithm only if the neighborhood of a message node up to depth I is a tree. [12] Belief propagation can be analyzed using a combination of tools from combinatorics and probability theory. The first analysis for a special type of belief propagation and its application to hard decision decoding of LDPC codes appeared in [4]. The analysis was vastly generalized in [8] to belief propagation over a hefty class of channels. The analysis states that for fixed I in random bipartite graphs, if n and r are large enough then the neighborhood of depth I of most of the message nodes is a tree. Therefore, the belief propagation algorithm on these nodes correctly computes the likelihood of the node for I rounds. Let us call these nodes the ’good’ nodes following . [11]. Then the expected behavior of belief propagation is calculated by analyzing the algorithm on the tree, and a martingale is used to show that the actual behavior of the algorithm is mostly concentrated around its expectation since the conditional expected value of an observation at some time t, given all the observations up to some earlier time s, is equal to the observation at that earlier time 5. So it has been proved that a heuristic analysis of belief propagation on trees correctly depicts the actual behavior on the full graph for a fixed number of iterations, using the martingale arguments and the tree assumption, which holds for large graphs and a fixed iteration number I [3]. Furthermore, the behavior of belief propagation can be used to calculate the probability of error among the good message nodes in the graph. This 21 shows that the error probability of the good message nodes in the graph can be made arbitrarily small for appropriate degree distributions. Since we assume the channel to in ’good’ state most of the times, the ”bad" message nodes will contribute only a sub-constant term to the error probability and their effect will disappear asymptotically since their fraction is smaller than a constant. This means that they are not relevant for an asymptotic analysis. It should be noted that there is recursion for the density function of the messages passed along the edges in the analysis of the expected behavior of belief propagation on trees. 50 asymptotically speaking, the general machinery shows that the actual density of the messages passed is very close to the expected density. Thus, tracking the expected density during the iterations gives a very good picture of the actual behavior of the algorithm. This method is called Density Evolution. We extensively used. density evolution to find thresholds of our puncturing patterns. 2.1.5- Degree Distributions for Nodes in LDPC Code: An LDPC code is called low-density code since it’s a linear block code for which the parity check matrix H is sparse and has a low density of 1’s. A regular LDPC code is a linear block code whose parity check matrix H contains exactly WC 1's in each column and exactly (1),. = we (n/m) 1’s in each row, where; n = Number of bits in the code-word k = Number of bits in data to be coded 22 m=n—k w, «m The code rate R = k/n is related to these parameters as, R = (1 — $ ), assuming H r is a full rank matrix. If H is low-density but number of 1’s in each column or row is not constant, then the code is an irregular LDPC code. For irregular LDPC codes, the parameters w, and w, are function of the column and row numbers and are independent of each other. It is usual in the literature (following [11]) to specify the v-node and c-node Degree Distribution Polynomials, denoted by 2(x) and p(x) respectively. In the polynomial, dv /I(x) = Adxd-l ......... (2.14) .2 2d denotes the fraction of all edges connected to a degree-d v-node and d,, denotes the maximum v-node degree. Similarly in the polynomial: dc p(x) = Z pdxd"1 ......... (2.15) dfl pd denotes the fraction of all edges connected to a degree- d v-node and dc denotes the maximum c-node degree. A typical LDPC code can be shown as in Figure Il-I. Here, the number of left (message) nodes is 10 and the number of right (check) nodes is 5. 23 II A Maximum v-node Degree, dv Maximum c-node Degree, dc - I 00 900 = 23;, )odxd-1 = 0.2 x2 + 0.4 x4 + 0.2 x5+ 0.2 x7 d, _ “96) = 2,, :1 Adxd 1 = 0.6 x1 +0.2 x2 + 0.2 x3 The parity check matrix representation of above code be: — [_1110100100 0101011011 1101110111 0010100100 0100101101 __A Please note that the degree distribution equations specify an ensemble of code, for which following graph representation is showing a particular code. 24 X1+X2+X3+ ‘1' *. rill-l ' .1 --_ \\ X2 + X4 + X6 + X7 + ' b - X9 + X10 \ / .li' viz- X1“ X2 + X4 + X5 + X6 + X8 +X9+X10 .\‘\\ j ' I] \xx.‘ X3 + X5 - +X3 Figure Il-l: Example of an LDPC code 25 fir 2.2 Puncturing: Puncturing is the process of removing some of the parity bits after encoding the data with an error-correction code and it is one of the basic techniques to modify the code rate. This has the same effect as encoding with an error-correction code with lesser redundancy, thus puncturing leads to a higher code rate. A code C is characterized by three fundamental parameters; its length 71, its dimension k, and its redundancy x = n — k. The code rate r can be defined as: r = k/n;k < n ......... (2.16) While doing puncturing, we decrease n, for a fixed k and thus increase the code rate. In this way, the code dimension remains fixed but its length and redundancy is varied as some redundancy symbols are deleted. Puncturing may cause the minimum distance to decrease because to puncture the code, we delete columns from its generator matrix. Suppose we have a codeword C,(K,-,X,-), where, K, data symbols are coded using X,- parity symbols. The receiver attempts to retrieve K,- data symbols by utilizing X,- parity symbols embedded in 6,. Depending on the decoding algorithm, the receiver can correct up to a certain threshold of error directly proportional to the number of parity symbols embedded in the message. For instance, for an error correcting code with error correction capability at, for X,- parity symbols, the receiver is capable of correcting up to (a *X,) errors out of |C,-| symbols in the message. Here a measures the expected error-correcting capability of a particular rate decoder. For example, the error— 26 correcting capability of Reed-Solomon codes is half as many as redundant symbols (i.e., = 0.5 ). The parameter a, thus, provides and upper bound on the error correction capability of a decoder and it is approximated by having thresholds over cumulative density function (CDF) of error distribution. With puncturing, we decrease the number of X, parity symbols to X,, assuming the receiver is capable of correcting up to (a * Xg) errors out of | Cill symbols in the message. In this way, code rate is increased and since the same decoder can be used regardless of how many bits have been punctured, puncturing considerably increases the flexibility of the system without significantly increasing its complexity. 2.3- Residual Errors: Traditional network protocols like IEEE 802.11 ARQ standard add some sort of forward error correction at PHY/MAC layer, such as Reed-Solomon codes etc., to recover from errors especially given the high data rates. This design strategy naturally prevents PHY/MAC layer to pass faulty packets to higher layers and these schemes drop packets and request retransmission even if a single bit is in error in the data passed from PHY/MAC layer to the higher layers. This leads to the wastage of useful data in the packet, the data which was received correctly. The errors which are not corrected by the physical layer are called Residual Errors, and residual errors result in link layer packet drops. This can be shown as figure-ll—ll below: 27 Wireless Client Wireless Server Application Layer Application Layer Transport Layer Transport Layer Network Layer Network Layer Residual Errors Link Layer Link Layer I PHY/MAC Layer PHY/MAC Layer w Vtfireless Link h — - — _ _ — — - — — — — I Figure ”4!: Residual Errors We define throughput over a transmission channel as: throughput = # of bits received correct /totai # of bits ......... (2.17) And we define goodput over a transmission channel as: goodput = # of correct bits containing actual data/total # of bits ...... (2.18) So for a session, goodput becomes ratio of total number of bits that contained actual data and are received correctly to the total number of bits transmitted for that session. In this way, the goodput parameter excludes parity bits from calculations of throughput values. We measure the values of both, throughput and goodput, at link layer as shown in figure ll-Ill. From figure ll-lll, we can see that link layer throughput corresponds to the number of bits that are getting relayed to the network layer, that is, ratio of the number of bits received by the link layer to the number of bits received by the network layer. 28 Similarly link layer goodput corresponds to the number of bits containing actual data that are getting relayed to the network layer, that is, ratio of the number of bits containing actual data received by the link layer to the number of bits received by the network layer. Application Layer Trans ort La er p y Link Layer ‘throughput' and‘goodput Network Layer measurement at this point Link Layer PHY/MAC Layer Figure ”4": Throughput and goodput measurement at link layer of the protocol stack 2.4- Channel Characterization: Most common wireless communication channels are of two types: 1) Binary Erasure Channel (BEC); 2) Binary Symmetric Channel (BSC). In both cases the input alphabet is binary, and the elements of the input alphabet are called bits. These channels can be described as: 1) Binary Erasure Channel (BEC): A binary erasure channel with erasure probabilityo is a channel with binary input, ternary output, and probability of erasure o. LetX be the transmitted random variable with alphabet {0,1} andYbe the received variable with alphabet {0, 1, e}, where e is the erasure 29 2) symbol. Then, the channel is characterized by the following conditional probabilities: a. Pr(Y=0|X=O) = l—o b. Pr(Y=e|X=0) =0 Pr(Y=1|X=O) = 0 P d. Pr(Y=0|X=1) = o Pr(Y=1|X=1) YD ll H I Q So, in the case of the binary erasure channel the output alphabet consists of (0,1), and an additional element denoted e and called Erasure. Each bit is either transmitted correctly (with probability 1 — a), or it is erased (with probability a). The capacity of this channel is: CBEC = 1 — C ......... (2.19) Binary Symmetric Channel (BSC): Abinary symmetric channel with cross-over probability denoted by a is a channel with binary input and binary output and probability of error 8. So iins the transmitted random variable andYthe received variable, then the channel is characterized by the conditional probabilities as below: a. Pr(Y=O|X=O)=1—£ b. Pr(Y=0|X=1)=£ c. Pr(Y=1|X=O)=£ d. Pr(Y=1|X=1)=1—£ 30 0 0 0 o --~~m <:>.-—~~—a \\ .\ /, .\ \ \K E e \.._. \ / / L—J ( . ,/ a / / I \ o / \ ll/ ,/// / x/ I. - ‘- / -" / ‘~.L___ C. ’>‘/- w_1 - O _» [j C > vi 1 _ 8— ___._LJ 1 1 1 1 (a) (b) Figure Il-IV: Two examples of channels: (a) The Binary Erasure Channel (BEC) with erasure probability a , and (b) The Binary Symmetric Channel (BSC) with error probability 5 So, In the case of the BSC both the input and the output alphabet is F2. Each bit is either transmitted correctly with probability (1 — a), or it is transitioned to other with probability a. The capacity of the channel is 1 — H(£), where H(£) is the Binary Entropy Function: C355 = (1 + elogz(e) + (1 — £)iog2(1 — 8)) ......... (2.20) Maximum likelihood decoding for this channel is equivalent to finding, for a given vector of length n over F2, a codeword that has the smallest Hamming distance from the received word. 31 Chapter 3 - Code Design and Working of PRAISE This chapter focuses on the code design aspects that we took into account to propose rate-adaptive codes using localized puncturing. In the beginning, we provide details about density evolution tools (LOPT and LODE) that we used to, 1) identify appropriate degree distributions with maximum noise variances for given allowed degrees under specified parameters, and 2) calculate noise thresholds for the degree distributions that we actually used to design our codes under practical constraints. In the latter part, we continue with the discussion of designing puncturing fractions for rate-adaptability of channel codes in time-varying channel conditions. 3.1- Density Evolution Tools: LDPC Online Optimisation Tool (LOPT) is an online optimization tool and LDPC Online Density Evolution (LODE) is an online density evolution calculator developed by Signal Processing and Microelectronics Lab, School of Electrical Engineering and Computer Science at University of Newcastle. We extensively used LOPT to find ’good’ degree distributions for LPDC code generation. This gave us an idea about ratios for allowed degrees for a given code rate. Moreover, we also used LODE to use density evolution and find noise thresholds for the code with allowed degrees and given degree distributions. 32 3.1.1- LDPC Online Optimisation Tool: LOPT is an online optimization tool, which uses density evolution to find the ensemble which returns the best possible threshold for a given code-rate and allowed degrees. To recall degree distributions as explained in Chapter 2, the variable (v-node) and check (c— node) degree distribution polynomials, denoted by 2(x) and p(x) respectively. In the polynomial, dv Mx) = z Adxd'l (1 =1 2,, denotes the fraction of all edges connected to a degree-d v-node and (1,, denotes the maximum v-node degree. Similarly in the polynomial: dc p(x) = Z M d=1 d-1 pd denotes the fraction of all edges connected to a degree- d v-node and dc denotes the maximum c-node degree. In this way, code designer can look for the specified degree distributions to get the best possible performance for a specified code rate and allowed degrees. We extensively used LDPT to find the degree distributions and noise thresholds in code designing process for a particular code rate. Since, it was not always possible to confine to the degree distributions requirements specified by LOPT due to practical constraints; we tried to design codes with degree distributions as near as possible to the suggested 33 ones. Later on, we used LODE to find noise thresholds corresponding to actually used degree distributions for code designing. Parameters for LOPT Code Rate 0.500000 Min LLR Value -20.000000 dB Max LLR Value 20.000000 dB Number of Iterations 1000 Minimum BER 1.000000e-10 11 Degrees 2, 3, 4 p Degrees 4, 5, 6 Results for LDPT Mx) 0.352288, 0.127617, 0.520095 p(x) 0.059358, 0.082206, 0.858436 Noise Variance 0.9050000 s Var s 0.910000 Table III-l: LOPT Parameters and Results Theoretically speaking, the Probability Density Functions (PDFs) of density evolution are continuous and defined for all possible log-likelihood ratios (LLRs). But, this is not possible practically in the implementation process. Soto avoid this, both LOPT and LODE limit the LLRs considered to those between Min LLR and Max LLR and chooses Number of LLR points equally spaced samples between Min LLR and Max LLR. We chose Min LLR, Max LLR and Number of LLR points as -20 dB, 20 dB and 511 respectively. 34 Furthermore, in theory the sum-product decoder is allowed to run for an infinite number of iterations and we expect the bit error rate to be zero for a successful decoding run, it is again not possible in practice. Both LOPT and LODE limit the simulations to the Number of iterations specified and consider BERs below Minimum BER to be equivalent to a BER of zero. We restricted the number of iterations to 1000 and Minimum BER to 1.0E-10, whichever is achieved first. A sample use of LOPT is as shown in Table Ill-l 3.1.2- LDPC Online Density Evolution: LODE is an online density evolution calculator, and can be used to find the threshold of an LDPC ensemble. To use LODE, we specified the degree distributions corresponding to p’s and 11’s for our ensemble, where by definition, summation of 11(x) and p(x) over all i equals 1. We extensively used LODE to find BER vs. Thresholds for our LDPC ensembles. Here again, due to practical constraints as in case of LOPT, we needed to specify Min LLR, Max LLR, Number of LLR points, Number of iterations, and Minimum BER and chose the same values as in case of LOPT. Furthermore, here we were able to select the output format and there are two output formats available. 1- Threshold Option 2- Eb/No Option In our work, we used thethreshold option, which searches between Minimum (dB) and Maximum (dB) to find the noise threshold of the specified ensemble. In this 35 case, the result is accurate to within Minimum difference (dB) and the output is the threshold, given as both the signal-to-noise ratio in dB and the corresponding noise variance (Var). Table III-II: LODE Parameters and Results for Threshold Search Parameters for Threshold search in LODE Code Rate 0.460197 Min LLR Value -20.000000 dB Max LLR Value 20.000000 dB Number of Iterations 1000 Minimum BER 1.000000e-10 11 Degrees 2, 3, 4 Mx) 0.2939, 0.0923, 0.6141 p Degrees 4, 5, 6 p(x) 0.0921, 0.1323, 0.7756 Threshold Min (dB) 0 Threshold Max (dB) 10 Minimum Difference 1e-5 Results for Threshold search in LODE Eb/No Threshold (dB) 0.731077 Var 0.958207 36 3.2- Designing Puncturing Fractions: An LDPC code is called low-density code because it’s a linear block code for which the parity check matrix H is sparse and has a low density of 1’s. A regular LDPC code is a linear block code whose parity check matrix H contains exactly WC 1’s in each column and exactly a), = 0),. (Tl/m) 1’s in each row, where: n = Number of bits in the code-word k = Number of bits in data to be coded ; k < n ......... (4.1) If H is a full rank matrix, then the code rate r is related to these parameters as, WC R = (1 — —) WT If H is low-density but number of 1’s in each column or row is not constant then the code is called an Irregular LDPC Code. For irregular LDPC codes, the parameters wc and w, are function of the column and row numbers and are independent of each other. We consider only regular ensembles of LDPC codes in our work. 37 In Chapter 2, we denote the variable-node (v-node) and check-node (c-node) degree distribution polynomials by 2(x) and p(x) respectively. In the polynomial, dv 2(x) = 2 Adxd‘l d =1 2,, denotes the fraction of all edges connected to a degree-d v-node and (1,, denotes the maximum v-node degree. Similarly in the polynomial: dc [906) = 2 PM d=1 d—l pd denotes the fraction of all edges connected to a degree- d v-node and dc denotes the maximum c-node degree. Following these notations, the rate of the code in terms of its degree distributions pair become: fol p(x)dx 1, =1— “ p) f012(x)dx ......... (3.1) Following [36], the total puncturing fraction p(O) can be defined as, the number of punctured variable nodes the total number of variable nodes pm) = ......... (1.5) In Chapter 4, we develop the channel model and introduce the notation of Transmission Intervals [T,; for i = 1, 2, . ..,00] , where the index i refers to the ith time slot. We also 38 assume that packets are transmitted over the channel under consideration during discrete time slots. For i‘h transmission interval (Ti), we define p“) to be the total puncturing fraction in the i‘h interval, p(i) the # of punctured variable nodes in the ith transmission interval (3 2) _ the total # of variable nodes ' Puncturing increases code rate because we decrease n for fixed k bits in doing puncturing operation. To recall the operating procedure, a ’mother’ code is designed with rate, r(/l, p), with highest redundancy. This code, with the largest number of parity bits, is used in the worst channel condition. We do puncturing as determined by the (0,5) pair for channel characterization, as discussed in Chapter 4, to transmit a ’daughter’ code with error-correction capability ad and code rate r(/l,p)(”). An important aspect to mention here is that the (o, a) pair value at the ith time interval is used to design puncturing fraction pa“) and thus, the code-rate for the packet to be transmitted at (i + 1)th time interval. th The rate of ’daughter’ code in the i interval,r(/l,p)(~‘), is related to the rate of base/’mother’ code as: r01. p) ilk/DH) = my; ......... (3.3) Several recent works tried to find bounds on code rates for reliable communication. Examples of such works include ACE [34] and RASE [40], which developed a framework 39 for reliable and stable communication with guarantees on sustainable flows. ACE defines stability as “System is stable when higher layers are neither starved for information packets nor is there a glut of packets leading to buffer overflow”. If e,- is BSC channel’s error (cross-over) probability and am is the error-correction capability of a code, then ACE determines the code rate for reliable and stable communication as: 51' R = 1 — — ......... (3.4) am This means that if a channel is in ’good’ state, we can increase the code rate and still have a reliable and stable communication with the same guarantees on sustainable flows. So PRAISE’s working in terms of code-designing can be summarized as follows: At the encoder end, we divide n-bit codeword into c chunks or partitions in a manner pre-determined by encoder and decoder. During T,, a sender transmits a message which is represented by the tuple M,- = (C,(k,-, X,); Y,), where k,- represents the number of data symbols which are not being retransmitted in the ith transmission interval. In each T,, a transmitter encodes k,- with parity symbols X,- creating a codeword C,(k,-, X,) with c chunks. We refer to these parity symbols as Type-l Parity following [34]. The receiver utilizes X,- to decode C,- and in case of successful decoding, k,- data symbols are passed up to the higher layers. In the case of error-correction (and thus, decoding) failure, the receiver stores C, in its buffer, identifies l chunks of the lowest reliability out of c chunks with the help of side-information received from PHY/MAC layer, and requests additional parity data for those 1 partitions. The 40 transmitter also sends additional parity symbols for l chunks of the lowest reliability, denoted by Y,-. We call these Type-ll Parity Symbols following [34]. The receiver utilizes Y,- symbols to recover old corrupted code-words accumulated in the buffer (e.g., Cj;j=1,2,...,i—1). The transmitted codeword after reception at the decoder end is called the Received Word. Received word has both, errors and erasures in it along with, if any, correctly received data-bits. The decoder identifies the location of erasures in received word caused by puncturing operation at the encoder and because it can determine the code- rate of the received word. Moreover, since we used LDPC codes, whenever a received word is decoded correctly, we are able to figure out exactly the number and position of errors in the received word at the decoder end. The decoder uses the BEC erasure probability a,- as determined by the puncturing fraction, and BSC error probability a,- as introduced by wireless channel to figure out the (o, a) pair value of the channel at the ith interval. For details on the channel model, please refer to Chapter 4 of the thesis. The PRAISE’s receiver has a finite buffer which can accommodate up to b corrupted messages waiting additional parity data from encoder. If a newly corrupted packet finds all the spaces in the buffer occupied, it does not enter the buffer and is dropped. The status of the receiver is reported to the transmitter via certain flags in an acknowledgment message which are called Buffer Status Flags. Specifically, b flags are encapsulated in every acknowledgement packet. Let buffer status flags in ACK,- be represented as: 41 [F, [k]; k = 1,2, ...,b],and [F, [k] = [1 + f], bits f = llogz (DI Please note that we need f = [109, (3)] feedback bits to identify 1 out of c chunks of lowest reliability and the additional 1 bit is required to flag the status of the kth space. In this way, each buffer status flag is associated with a particular packet—space in the buffer and represents the status of that space, along with the number of the lowest reliability l chunks, to request additional parity data for. In addition, the receiver estimate of channel condition, determined by (0,8) pair in T, is also encapsulated in acknowledgment message. The ACK, value for the buffer status flags is transmitted back to encode a new packet with: 1- puncturing fraction p0“) and thus, the code-rate for the packet to be transmitted at (i+1)th time interval. For a ’daughter’ code with error- correction capability ad, we determine puncturing fractions as: p = 1 — ——— ......... (3.5) 2- additional parity data for l chunks of the lowest reliability for the corrupted code-words residing in the buffer at the receiver in the ith transmission interval. This process continues till whole data is successfully received and decoded. 42 Chapter 4 - The Channel Model This chapter provides the details of the channel model that we used to develop the proposed scheme for rate-adaptability of wireless protocols in time-varying channel conditions. A channel model describes the process under which errors are introduced in a transmitted packet over a wireless link. For modeling purposes, we assume that packets are transmitted over the channel under consideration during discrete time slots which we refer to as Transmission Intervals, T. We denote transmission intervals by [T,; fori = 1, 2,...,00], where the index i refers to the ith time slot. To proceed with our channel model, we divide our discussion in two levels. The modeling begins with developing channel model in a particular transmission interval and then continues with a complete channel model based on all transmission intervals. During the i‘h transmission interval, a packet is transmitted over cascaded BEC and BSC channels. Here, the BEC channel with erasure probability 0 models the puncturing operation to puncture the input codeword. The input codeword to the BEC channel is encoded with the code rate for ’mother’ code, r(,1, p), and the output is the ’daughter’ code with code rate r(/l,p)(~). Hence we model the puncturing fraction pm by BEC erasure probability a, and the puncturing operation by a BEC channel. Please refer to Chapter-3 for more details on code rates and their design aspects. In our channel model, the BSC with cross-over probability 8 models the wireless channel transmitting the punctured codeword. These two channels are parameterized by the following: 43 o: BEC erasure probability (as determined by the puncturing fraction) 3: BSC error probability Hence, the (o, a) pair characterizes the channel during each transmission interval T. The transmitted codeword after reception at the decoder end is called the Received Word. Received word has both, errors and erasures in it along with, if any, correctly received data-bits. The decoder Identifies the location of erasures in received word caused by puncturing operation at the encoder end because it can determine the code-rate of the received word. Moreover, since we used LDPC codes, whenever a received word is decoded correctly, we are able to figure out exactly the number and position of errors in the received word at the decoder end. In this way, the decoder uses the (0,, 8,) pair to figure out the channel state at the ith interval. It is important to note that puncturing causes erasures in a transmitted packet. Strictly speaking, it’s not a part of the channel over which we are transmitting a packet as it is performed at the encoder end before transmission. Still we can assume it is a part of the channel for modeling purposes as at the decoder end, because decoder finds both, errors and some erasures in the received word. 50 for the i‘h transmission interval, the channel model can be as shown in the figure IV-I below: 44 ("A 1 - 0- —-~ —— C] 1 474— — 1 - £---— {Eh—A \V/ Figure lV-l: Cascaded BE C and BSC Channels with erasure and error probabilities a and 8 respectively. A discrete random process with the property that the next state depends only on the current state is called as Markov Chain. The Markov property states that the conditional probability distribution for the system at the next step, and in fact at all future steps, given its current state depends only on the current state of the system, and not additionally on the state of the system at previous steps: Pr (X,+1 |X,,X2, ...,Xn) = Pr (X,,.,1 an) ...... (4.1) We call the process under-discussion “a discrete random stochastic process” because the wireless channel, which is in a certain state characterized by its particular (0,, 8,) pair at ith transmission interval, changes randomly between intervals. Moreover in our 45 proposed scheme to adapt rate of wireless protocols in different network conditions, the decoder transmits the (0, 8) pair value back to the encoder via feedback and the encoder uses the (0,, 8,) pair value at the ith time interval to design puncturing fraction pa“) and thus, the code-rate for the packet to be transmitted at (i + 1)‘h time interval. This suggests a Markov-based channel characterization. Hence, to derive a channel model for all transmission intervals, we assume that each (0,, 8,) pair value of a particular T, is valued from a finite set FN with length N i.e. (Ci, 8,) E .FNIO IFNI = N ...... (4.2) As a result, we can consider the channel model as a combination of N various cascaded BECs and BSCs with unique (0, 8) pairs, i.e., (0m, am) at (on, 8,,);form at n; m,n = 1, 2, ...,N ...... (4.3) In every T,, the channel is in one of the N possible states (51,52, ...,SN) where each state corresponds to a particular cascade of BECs and BSCs as depicted in figure above. The changes of state of a Markovian system are called as Transitions, and the probabilities associated with various state-changes are called Transition Probabilities. The set of all states and transition probabilities completely characterizes a Markov chain. By convention, we assume all possible states and transitions have been included in the definition of the processes, so there is always a next-state and the process goes on forever. In our proposed scheme, the (0,8) pair value is calculated at the receiver, which reports it back for training of the Markovian channel and predicting code rate for 46 next word to be transmitted. Since our state space is finite, the transition probability distribution can be represented by a matrix, called the Transition Matrix, with the (s, t)th element of the matrix P5,, equals to: p5,, = Pr (Xn+1 = s | Xn = t) ...... (4.4) For simplicity of modeling, we can assume that probability of transition between states is independent of the state index n.This makes the Markov chain a Time-homogeneous Markov chain, and in this way, the process is described by a single, time-independent matrix, P5,. For a time-homogeneous Markov chain: Pr (Xn+1 = s |X,, = t) = Pr (Xn = s | Xn_1 = t) ...... (4.5) In such a case, the vector J1 is called a Stationary Distribution, and the associated probabilities as Steady-state Probabilities, if the entries J1, of the vector J] sum to 1 and it satisfies: J1, = 2 J15 .ps, ...... (4.6) 385 Based on the above-mentioned channel model, the wireless channel for the proposed Side-Information Enhanced Forward Error Correction (SEFEC) scheme is modeled by a discrete Markov chain with N possible states where each Markov state is represented by a cascade of BECs and BSCs with a particular (0, 8) pair. We assume a homogenous and stationary Markov chain with transitional probability matrix P5,, and the limiting state (stationary) probabilities (J1 =111’112,...,JIN). The Markovian channel model is 47 trained on real channel traces by using the statistics of previous transmission intervals. This captures the effects of multipath fading and interference on the (0, 8) pair in every transmission interval using a single aggregated model. This can be shown in figure IV-II. It’s well known that the capacity of the cascaded BEC(0) and BSC(8) channel is (1 — 0). (1 — H(8)). Using the steady state probabilities, the average channel capacity in the ith transmission interval is determined as follows: N cT = 2 1r, (1 -- 0,)(1 — H(8,)) ...... (4.7) i=1 The channel capacity gives an upper bound on the average (reliable) information transmission rate for the wireless channel under consideration in the ith transmission interval. We explained the Conventional Standard (CS) schemes like IEEE 802.11 ARQ in Chapter- I. Some prior works [35, 41, 42] have proposed cross-layer designs to achieve improvements in end-to-end bandwidth utilization and overcome performance limitations imposed by CS. We have included details of such works in Chapter-II of the thesis, with the fact that their primary drawback is that their implementation requires major modifications in higher layers. However, the analysis of the Hybrid Erasure-Error Protocols (HEEPs) [42] shows that cross-layer protocols in general can significantly improve the overall performance as measured by video quality and provide capacity improvement in many realistic scenarios. The proposed SEFEC scheme is a cross-layer 48 design with all advantages of a cross-layer design and does not require any modification in higher layers for extraction of side-information. of 0Q $ *- l o If] ‘. m '- 1. . .. I L I I 1— N w ‘— I O l f"; ‘— . ‘- T ‘T ‘T O :-__ 0) I l Ill ‘— o " b I D O l v!— ‘- Olfi /-\) ‘— 0? o?) T ‘- ° [ii ‘33 P w 1 .—’ w I X l 1— N w T . . "\~. I O {Kr/t \l'j ‘— . 1'- 1- y 1— l . O o __ j 1— —; \\‘ 'v O I O D I 1— /. \ ‘— L/7 ‘Y O K / '\_/ '— 07] cud fl ‘- I 0 [ii If] :- ... - . ,. 3.. I w I T ”I ..., '- Ol -) i .1 .7) 1- . ‘- I '- : O I»: 0 Ll Ii '— 6 o I D D I T 1' '- olr..\ A ‘— Figure lV-II: Markovian Channel Model 49 Chapter 5 - Experimental Setup This chapter begins with giving a brief idea about Software-Defined Radios (SDRs) and explains GNU-USRP based implementation of a Software Defined Radio (SDR) to be used in our work. We continue with our motivation to use GNU-USRP platform to collect real- time channel traces and provide details about our experimental setup. In the end, we report parameters to collect data. 5.1- Software-Defined Radios: The term Software Defined Radio was first used in 1991 by Joseph Mitola, who published the first paper on the topic in 1992. A software-defined radio system, or SDR, is a radio communication system where components of a typical radio communication system, like mixers, filters, amplifiers, modems (modulators/demodulators), detectors, etc., that have been typically implemented in hardware are instead implemented by means of software on a personal computer or on embedded computing devices. Hence in an SDR, software defines shape of waveforms, modulation/demodulation schemes and other parameters of transmission like packet size, data rate and bursty modes. This brings before user a whole new area of design by transforming typical hardware problems into software ones. In this way, a user is more flexible to play with these parameters by changing different software building blocks which was not possible earlier due to hardware limitations. A very basic SDR communication system may consist of a personal computer equipped with a sound card, or other analog-to-digital (A/D) converter, preceded by some form 50 of RF front end. Typically major part of signal processing is handed over to the general- purpose processor, rather than being done in special-purpose hardware. Such a design produces a radio which can receive and transmit widely different radio protocols based solely on the software used. SDRs have found significant utility for the military and cell phone services, as both of these always look to serve a wide variety of changing radio protocols demands in real time. In the long term, SDRs are expected to become the dominant technology in radio communications systems. SDRs, along with software defined antennas are the enablers of the cognitive radio computing and are being used extensively by research community and academia. 5.2- GNU Radio: GNU Radio is an Open-source, free software toolkit for learning about, building, and deploying SDR communication systems. The project started in 2001 and is now an officialGNU project, released under the GPL version 3 license. Philanthropistlohn Gilmore initiated and has sustained GNU Radio as of now with the funding of $320,000 (US) to Eric Blossom for code creation and project management duties. GNU Radio is a signal processing package with the goal to give ordinary software people the ability to understand the electromagnetic radio spectrum and think of clever ways to use it. So it makes possible for a user to explore many domains of cognitive computing using software modules only. 51 GNU Radio signal processing blocks are written in C++, while creating flow graphs and connecting signal blocks is done using Python. So, the developer is able to implement real-time SDR with high-throughput capability, in a simple-to-use and rapid-application- development environment. As with all SDR communication systems, re-configurability is the key feature of GNU Radio. Instead of purchasing multiple expensive radios, a single more generic hardware is purchased, which feeds into powerful signal processing software and serves the purpose. Currently only a few forms of radio are implemented in GNU Radio, but one can reconfigure GNU Radio to receive any radio transmission system by understanding the math behind it. 5.3- Universal Software Radio Peripheral: The Universal Software Radio Peripheral (USRP) is a high-speed USB-based board for making software radios, and acts as an RF front-end for an SDR. USRP is a comparatively inexpensive hardware device (under $1K) facilitating the building of an SDR. USRP has got open source drivers and software to incorporate GNU Radio. Furthermore, the USRP board schematics and the associated Verilog code are also freely available for download. It is also designed to be flexible, allowing developers to make their own daughter- boards for specific needs with regard to connectors, different frequency-bands, etc. The USRP is developed by GNU Radio project and a team led by Matt Ettus. USRP is a digital acquisition system containing A/D and D/A converters, and support circuitry including a high-speed USB 2.0 interface. The USRP is capable of processing signals with 52 bandwidth up to 16 MHz. Several transmitter and receiver plug-in daughter boards are available covering various bands between 0 and 5.9 GHz. Technical details of USRP are asunden 5.4- Four high-speed 64 MS/s A/D converters, each having a resolution of 12 bit Four high-speed 128 MS/s D/A converters, each having a resolution of 14 bit An Altera Cyclone EP1C12Q240C8 FPGA A Cypress EZ-USB FX2 High-speed USB 2.0 controller 4 extension sockets (2 TX, 2 RX) in order to connect up to 4 daughter-boards 64 general purpose l/O pins available through four Basich/BasicRx daughterboards (16 pins each) Daughter-Boards with USRP: Daughter-boards serve as the RF frontend for SDR. They allow the output signal to be modulated to a higher frequency and an input signal to be demodulated of its carrier. USRP comes with a variety of daughter-boards and three different types of boards exist: 1. Receivers 2. Transmitters 3. Transceivers 1- Receivers: Receivers are a type of daughter-boards that only support RX and consume only one RX port: BasicRX, 1 - 250 MHz Receiver, for use with external RF hardware. LFRX, DC - 30MHz Receiver TVRX, 50 MHz - 870 MHz Receiver 53 o DBSRX, 800 MHz - 2.4 GHz Receiver 0 BURX, 300 MHz - 4 GHz Receiver 2- Transmitters: Transmitters are a type of daughter-boards that only support TX and consume one TX port: 0 BasicTX, 1 - 250 MHz Transmitter, for use with external RF hardware 0 LFTX, DC - 30M Hz Transmitter 3- Transceivers: Transceivers are a type of daughter-boards that are both TX and RX and consume 2 ports, one for transmission and the other for reception: 0 WBX0510, 50 MHz - 2.2 GHz Transceiver o RFX400, 400 - 500 MHz Transceiver o RFX900, 800 - 1000 MHz Transceiver o RFX1200, 1150 - 1450 MHz Transceiver - RFX1800, 1.5 - 2.1 GHz Transceiver o RFX2400, 2.3 - 2.9 GHz Transceiver o XCVR2450, Dual-band Transceiver, i.e. 2.4 - 2.5 GHZ and 4.9 - 5.85 GHz 5.5 Motivation for GNU-USRP Platform: Wireless network refers to any type ofcomputer network that is wireless, and is implemented using remote information transmission system. Common types of wireless networks include Wireless Personal Area Networks (e.g., Bluetooth, Zigbee), Wireless Local Area Networks (e.g., Wi-Fi, Fixed Wireless Data), Wireless Metropolitan Area Networks (e.g., WiMAX), Wireless Wide Area Networks (e.g., Gaiacom Wireless Network), and Mobile devices networks (with development of smart phones, like GSM, 54 PCS and D-AMPS). Wireless market is having many options to establish communication among different users in various different environments. Current wireless network devices such as USB network adaptors (e.g., Samsung WIS- 09ABGN, Linksys WUSB54G), Peripheral Component Interconnect (PCI) wireless adaptor cards for computer desktops (e.g., D-Link DWL-GSZO, Linksys WMP54G) and notebooks (e.g., Linksys WPC54G, TP-Link TL-WN3606), wireless Ethernet bridges (e.g., TiVo AN0100 , Linksys WET54G), and Wireless Compact Flash Card Adapters for PDAs (e.g., Linksys WCF54G, Netgear MA701) are utilized to establish communication channels among different wireless users in various wireless environments. By design, these devices use IEEE802.11 standard to attain channel access, contention, and error control at the Physical (PHY) and MAC layers. IEEE 802.11 standard has some sort of basic error correction at PHY layer, like Reed Solomon codes etc. and this design strategy naturally leads to preventing PHY layer to pass distorted packets to the higher layers. The distorted packets are dropped right away at PHY layer, wasting a lot of useful data. So we faced the major challenge of utilization and alternation of link-layer corrupted packets, containing residual errors, at the receiver to: 1- Capture and measure the behavior of an error process of a wireless channel, 2- Analyze the residual errors, at link-layer, in a wireless channel to design suitable puncturing fractions in localized manner for rate-adaptability of error control protocols, 55 3- Implement error control protocols at the link-layer that employ and manipulate received corrupted packets, and 4- Extract side information from MAC/PHY layers to request localized parity for subsets with potentially highest number of errors. To cope with this issue, we need to modify the configuration of these devices to attain the distorted packets at the PHY/MAC layer. But, these off-the-shelf wireless devices are not open source products, thus modification of the source code functionality is not possible. To overcome this problem, we use Software-Defined Radio (SDR) technology. Specifically, we use GNU-USRP platform as the communication system front-end on each sender and receiver node in our experiments. Since, GNU Radio is an open-source software development toolkit, we are able to easily reconfigure and modify its building blocks. In this way, we have complete control over the communication system configurations down to the FPGA/antenna level, and down to PHY/MAC layers and we are able to capture distorted packets received at the PHY/MAC layer and pass packets with residual errors to link layer. Furthermore, we are able to extract side information associated with each packet. 5.6- Layered Architecture: Figure V-l shows the layered architecture of the experimental realization of the wireless communication for this thesis. At the top level, Application Layer resides which is designed to generate data packets and pass them down to the link-layer. It is important 56 to note that we are interested in point-to-point link-layer wireless communication enhanced by side-information from MAC/PHY layer, modifications are irrelevant for this work. Custom Protocol I (Application Layer) . I Payload J7 I (Physical Layer) I_ USRP + XCVR2450 + Antenna 7%" Wireless Link k I Custom Protocol , (Application Layer) J Payload] F l LDPC Encoder LDPC Decoder I (Link Layer) (Link Layer) j LDPC Encoded I Data LDPC Encoded ‘ j i Data GNU Radio GNU Radio (Physical Layer) I packet Packet + Side '_, Information USRP + XCVR2450 + Antenna Figure V-l: Layered Architecture of our Experimental Setup 57 thus TCP and Network I. _ A At the link-layer, the data packets are encoded to link-layer packets using a particular error control protocol. We used LDPC codes for this task. These packers are then sent to the PHY layer (i.e., GNU Radio) where they are transmitted over the wireless channel. We use Universal Software Radio Peripheral (USRP) as an RF frontend of GNU Radio. USRP can simultaneously receive and transmit on two antennas. Daughter-boards mounted on URSP provide flexible, fully integrated RF front-ends. USRP has an open design, with freely available schematics and drivers that can be integrated with GNU Radio. This enables us to modify MAC/PHY layer of our communication system and extract side information for error localization in received packets with residual errors. Similarly, at the receiver end, packets are received by USRP. Here packet, along with side information is passed on to link-layer. LDPC decoder at link-layer decodes the packet and passes it on to Application layer on the top. 5.7- Experimental Test-Bed: We use GNU-URSP platform to conduct experiments, collect traces and do analysis over real-time traffic data. In our work, we use XCVR2450 daughter-board which is a Dual- band Transceiver and transmits at 100+mW output at 2.4-2.5 GHz and 50+mW output 4.9-5.85 GHz. The XCVR2450 covers both the ISM band at 2.4 GHz and the entire 4.9 to 5.9 GHz band, including the public safety, UNII, ISM, and Japanese wireless bands. Our experimental test-bed consists of two USRP devices: one connected to a desktop PC which we refer to as the Data-Host (DH) PC and the other connected to the Data-Ghost (06) laptop computer. DH is hosting the data to be transmitted and DG is streaming 58 data from DH. In our experiments, the application layer in DH and DG respectively generates packet data and the acknowledgment packets. We set up the wireless communication system between DH and DG using the parameters as listed below. We conducted our experiments in two phases. In the first phase, we collected traces to analyze the element of burstiness in the packet and to train our Markovian model. The detailed analysis for burstiness and the details of the deployed channel model can be found in Chapter-4 of the thesis. To train our Markovian channel model and to measure the number of errors introduced in every packet during a transmission session over a specific channel, in this phase of the experimental data collection, DH transmits predefined 100, 000 packets with 1500-byte packet payloads in every transmission session. Accordingly, DG captures the received packet and performs XOR operations with the predefined payload. Through this, we measure the number of byte (and bit) errors introduced in each packet. In the second phase of experiments, using our GNU-USRP based wireless platform, we conducted several communication scenarios to capture the behavior of wireless error in the presence of fading, interference and mobility. We characterize wireless channel condition with average Bit Error Rate (BER) and average Packet Error Rate (PER). Our analysis consists of measuring 100 wireless channel conditions which are categorized in four groups: 1- Environment factor: To cater for the environments effects on wireless channel conditions, we carried out extensive set of experiments in both, open-spaced 59 out-door environment, i.e. outside the building, and in closed-space in-door environment, i.e. inside the building. For in-door setting, several factors contributed in wireless channel conditions as explained in coming lines. However, for out-door setting, the wireless communication was mostly line-of- sight (LOS) communication and we noticed that distance was the only metric for wireless connection failure and packet dropping. Fading factor: In this set of scenarios, the DG laptop is located within certain distances of DH. The distance between D6 and DH governs the impact of fading on the wireless communication. In particular, the error conditions for channels where DH and DG are relatively close to each other (e.g., less than 3m) are remarkably better than those with D6 and DH are farther. It is also important to note that placing DG and DH very close to each other (e.g., less than 1/2 m) causes a lot of missing packet at DG due to interference caused by DH, so we did not consider such close distances. Interference factor: To capture the impact of interference on wireless channel condition, we establish wireless communication in the presence of other wireless networks. These networks include Wi-Fi in our lab (i.e. WAVES lab), Wi- Fi in the building (i.e. College of Engineering), and in the presence of other hot- spots established over some laptop computers. It is evident that as more active wireless networks are presented in the environment, the likelihood of packet collisions increases leading to frequent packet errors due to interference. 60 uuuuuuuuuuuuuuuuuuuuuuuuuuuu oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo o Vlfired Link— Distance USRP i f USRP . i Connected § Connected Transmitter PC § to Antenna g to Antenna (DH) Figure V-ll: Experimental Setup to see Efiects of Environment and Fading Factors USRP Connected (( )) to Antenna 21 ft Room 2320 Receiver PC 12ft Passageway 21ft no-4.- (( )) E USRP Connected _ ,- -1 1 E to Antenna I X o C n-000K7 VVIred Link WAVES Lab, 3 Room 2322 o cooo-ooo—o..~c-.a-oo-oo»oooe~o.oo.-.a~oo-¢oooc...-nanoaco- ooooooooooooooooooo Figure V-lII: Experimental Setup to see Effects of Mobility Factor 61 4- Mobility factor: The DH transmits data packets to the DG laptop which is a mobile node and changes its location frequently. Please figure Ill-III to get an idea of the room locations. In this set of experiments, the mobility is conducted within a room (i.e. WAVES lab), within the hallway (next to the room where DH resides), and within the room opposite to hallway. However the wireless connection never fails; all the transmitted packets are received by DG. Using the GNU Radio-USRP based platform, we determine the performance efficiency of different link-layer protocols over above-mentioned channel conditions. In particular, we implement five link-layer protocols. One belongs to the Conventional Standard (CS) protocol category (IEEE802.11 ARQ), three belong to Forward Error Correction (FEC) protocol category (Hybrid ARQ type-l (HARQ-l), Hybrid ARQ type-ll (HARQ-ll), Reliable and Stable (RASE)), and one for Side—information Enhanced Forward Error Correction (SEFEC) protocol category (PRAISE) on our platform. The details of CS, FEC and SEFEC can be found in Chapter-1 of the thesis. These protocols reside in link-layer section of the layered architecture shown in Figure III-l and are implemented using C++ modules and glued in GNU-USRP platform with Python. Though two identical USRPs are connected to both PCs, we will use the terms DH and DG for USRP and the associated PC jointly. Unless otherwise specified, following are the default parameters for conducting experiments and collecting channel traces: 62 Frequency: 5.1G Packet Size: 1500 Bytes (Range = 0-4096 bytes) No. of Packets in a session: 100,000 Modulation Scheme: GMSK Bursty Mode: Disabled We analyzed the performance of five network protocols; 1) Puncturing for Rate Adaptability of Reliable and Stable Wireless Protocols (PRAISE), 2) Reliable and Stable (RASE), 3) Hybrid ARQ-II, 4) Hybrid ARQ-I, and 5) Automatic Repeat Request (ARQ) over GNU-USRP platform. To keep discussion generic, we divided these protocols in three categories; 1) Conventional Standard (CS, like ARQ), 2) Forward Error Correction enabled Protocols (FEC, like HARQ-l, HARQ-II, and RASE), 3) Side-Information Enhanced Forward Error Correction enabled Protocols (SEFEC, like PRAISE). The details of CS, FEC and SEFEC can be found in Chapter-1 of the thesis. To gauge the performance of these protocols over the wireless channel, we make use of two protocol-dependent parameters namely, 1) throughput; 2) goodput. We define throughput over a transmission channel as: throughput = # of bits received correct /total # of bits ...... (5.1) And we define goodput over a transmission channel as: goodput = # of correct bits containing actual data/total # of bits ...... (5.2) 63 So for a session, goodput becomes ratio of total number of bits that contained actual data and are received correctly to the total number of bits transmitted for that session. In this way, the goodput parameter excludes parity bits from calculations of throughput values. We compare the values of the above-mentioned protocol-dependent parameters against two wireless channel metrics, 1) Packet Error Rate (PER); 2) Bit Error Rate (BER). Bit Error Rate (BER) is defined as the rate at which errors occur in a transmission system. BER is a unit-less performance quantity and is expressed as a percentage number. The definition of bit error rate can be expressed as: BER = number of bits in errors/total number of bits ...... (5.3) And, the Packet Error Rate (PER) is the number of incorrectly transferred data packets divided by the number of transferred packets. A packet is assumed to be incorrect if at least one bit is incorrect. PER is a unit-less performance quantity and is expressed as a percentage number. Mathematically, PER can be expressed as: PER = number of packets in errors/total number of packets ...... (5.4) Hence our results (explained in Chapter-7) fall in two categories depending upon wireless channel metrics and we measure each of the two protocol-dependent parameters against each of the channel metric. Depending on channel conditions, we vary the code rate from (10—50)% and collected several traces. From the first phase of experiments, we concluded that the code-rate of 64 33.33% is optimum for performance in varying channel conditions for fixed rate FEC schemes. It is neither too much to affect goodput in good channel conditions nor that bad to cause a lot of retransmissions in bad channel conditions. 65 Chapter 6 -Analysis of Burstiness in a Packet An Error Burst over a data transmission channel can be defined as a contiguous sequence of n symbols such that the first and last symbols are in error. In this way, there does not exist any contiguous subsequence of m correctly received symbols within the error burst of n symbols, where m < n. The Length of a Burst of Bit Errors in a Frame is defined as the number of bits from the first error to the lost, both inclusive. The integer parameterm is used to specify the length of the burst and is referred to as the Guard Band of the error burst. The last symbol in a burst and the first symbol in the following burst are accordingly separated by m correct bits or more. We explained our experimental setup in Chapter-S of the thesis. Our experimental test- bed consists of two USRP devices: one connected to a desktop PC which we refer to as the Data-Host (DH) PC and the other connected to the Data-Ghost (DG) laptop computer. DH is hosting the data to be transmitted and DG is streaming data from DH. In our experiments, the application layer in DH and DG generates packet data and the acknowledgment packets respectively. We set up the wireless communication system between DH and DG using the parameters detailed in Chapter—5. Using our GNU-USRP based wireless platform, we conducted several communication scenarios to capture the behavior of wireless error in the presence of fading, interference and mobility. As we explain in Chapter-S, we conducted our experiments in two phases. In the first phase, we collected traces to analyze the element of burstiness 66 in the packet and to train our Markovian model. To measure the amount of error introduced on every packet during a transmission session over a specific channel, in this phase of the experimental data collection, DH transmits 100, 000 packets with predefined 1500 byte packet payloads in every transmission session. Accordingly, DG captures the received packet and performs XOR operations with the predefined payload. Through this, we measure the number of byte (and bit) errors introduced in each packet. Our proposed scheme enhances end-to-end bandwidth utilization in case of bursty errors in a packet. So burstiness analysis for data in a received packet in this phase of date collection constitutes an important part of the thesis. This burstiness analysis is divided into three following subtopics: 1- Distribution of Errors in a Packet 2- Bit Error Rate (BER) vs. Cumulative Density Function (CDF) 3- End-to-End (EZE) Burst in a Packet 6.1- Distribution of Errors in a Packet We define Distribution of Errors as the arrangement of continuing and successive errors in space. Hence the error distribution describes the range of possible values that an error variable can attain in succession and the probability that the value of the error variable is within any (measurable) subset of that range. In our experimental setup, space consists of a packet length and the unit to specify errors is taken as bytes. We show plots of the error distributions of the collected traces in the following pages to get 67 proof of the proposed idea. We are including three error distributions in the thesis for reference purposes. Each of the error distribution plots burst length vs. number of received packets in a session. In this way, x-axis corresponds to number of successive error bytes in a packet of length 1500 bytes, and y-axis refers to the %age of received packets containing specific error burst lengths. To explore burstiness of errors in a packet, we scaled our burst length axis from 2-1500 because a burst length of zero refers to a packet without errors (i.e. a packet that was received correct) and a burst length of one shows an alternate occurrence of a pattern of zeros/ones referring to sporadically distributed error bytes. The resulting error distributions are as shown below in figures VI-l, VI-II, and Vl-lll. Figure VI-I shows distribution of errors in traces with Packet Error Rate, PER, in the range of 30-40%. Since the channel in this case is in ’good’ state, we notice values of burst lengths represented by a smaller percentage of received packets. For example, the highest burst length is around 80 bytes and only 4.2% of received packets have a burst length of 80 bytes. Furthermore, except the burst length of 85 bytes, represented by 3.4% of received packets, all other burst lengths can be seen in less than 1.5% of received packets. As we move-on to the traces with higher PER values, we notice that burstiness in a packet increases and we start observing packets with greater burst lengths. For example, in traces with PER values ranging between 60-70% and 80-90%, 68 the highest burst length values are again around 80 bytes, but this value is represented by 7.3% and 8% of the received packets respectively, as shown in figures VI-II and VI-III. Distribution of Error Bursts in Traces with PER = 30-40% 0 03s- 0033. i .. .. ., . ... .. . ... . a 0025?- : - l 0 02.. . . . . . . . . . . 4 l I 00151 Received Packets 001; ...... 200 400 600 800 1000 1200 1400 Burst Length (bytes) Figure Vl-I: Distribution of Errors in Traces with PER = 30-40% Moreover, we find significant peaks in burst distributions represented by over 2% and over 4% of received packets in traces with PER values 60-70% and 80-90% respectively. From these error distributions, we see that burstiness at packet level increases with higher PER values. So we conclude here that as the channel state gets worse, the error distributions increase too resulting in increased burstiness effects at packet level. This gave us the motivation to design codes catering for bursty errors in a packet and coping with bursty nature of wireless channels by adapting code-rates in varying channel conditions. 69 Received Packets Received Packets Distribution of Error Bursts in Traces with PER = 60-70% 0.081 , , ., _ T-.. 0.071 .1 0.051» 4' ...; 0.031- 002)" ~« 0.01 0 ~ 7 7 1 1 1 l 1 1 . 200 400 600 800 1000 1200 1400 Burst Length (bytes) Figure Vl-ll: Distribution of Errors in Traces with PER = 60-70% Distribution of Error Bursts in Traces With PER = 80-90% 0.09.1 1 1 1 1 1 1 1 0.08 ' q 0.07 0.05 r 1 1 200 400 600 800 1000 1200 1400 Burst Length (bytes) Figure Vl-lll: Distribution of Errors in Traces with PER = 80-90% 70 6.2- Bit Error Rate (BER) vs. Cumulative Density Function (CDF): We know that a probability distribution can be completely described by its cumulative distribution function when a random variable takes values in the set of real numbers, whose value at each real value x is the probability that the random variable is smaller than or equal to x. Cumulative Density Function (CDF) of error distribution, plotted against Bit error rate (BER) is another useful metric to gauge burstiness in a packet. Suppose we have a codeword C,(K,,X,), where, K, data symbols are coded using X, parity symbols. If we define Distortion as an undesired change in the output signal resulting from imperfections in the wireless channel, then the Distortion Level E, is always random and unknown to the receiver and therefore the notion of partial recovery is unrealistic in the context of error correction. This means that the receiver can either correct all errors in C, and declare successful decoding, or just states that no recovery is achieved. The receiver attempts to retrieve K,- data symbols by utilizing X, parity symbols embedded in C,. Depending on the decoding algorithm, the receiver can correct up to a certain threshold of error directly proportional to the number of parity symbols embedded in the message. For instance, for an error correcting code with error correction capability a, for X, parity symbols, the receiver is capable of correcting up to (a *X,) errors out of |C,| symbols in the message. Here a measures the expected error-correcting capability of a particular rate decoder. For example, the error- 71 correcting capability of Reed-Solomon codes is half as many as redundant symbols (i.e., = 0.5 ). The parameter a, thus, provides and upper bound on the error correction capability of a decoder and it is approximated by having thresholds over CDF of error distribution. Figure lV-Vl plots BER vs. CDF for traces with shown PER values. For PER values of 10- 15%, since the channel is in a ’good’ state, we notice that up to 80% corrupted packets can be successfully decoded if provided enough parity data to correspond for a BER of 0.7. This means a decoder with a = 0.7 can correct 80% packets in such a scenario. For other cases, to correct 80% of corrupted packets, the corresponding a-values are 0.78, 0.85 and 0.93 for PER values of 40-45%, 60-65% and 80-85% respectively. Bit Error Rate vs. CDF I I I 0.8 0.6 CDF 0.4 0 2 ..... i'fidfl-f‘. ....... -'- PER = 404505 _ ' §--"": ""'" PER = 60-650/0 0 EL JE ""' PER = 80-85% 0 0.2 0.4 0.6 0.8 1 BER Figure VI-IV: BER vs. CDF 72 6.3- End-to-End (EZE) Burst in a Packet: We define End-to-End (EZE) burst as the number of bits between the first error bit and the last error bit, both inclusive, in a packet received over a transmission channel. This definition provides room for existence of multiple contiguous subsequences of m correctly received symbols and error bursts of n symbols within E2E burst. E2E burst is a useful way of looking into corrupted area of a packet. It gives an overall/big picture view of the faulty portion of the packet. This caters for even the sporadic distribution of errors inside a packet, providing the code designer an insight to design codes keeping in view the fact that errors may be randomly distributed inside a packet, aside from their occurrence in bursts. So, E2E burst length specifies the total corrupted portion of a received packet enabling one to design parity data keeping in view the maximum possible length of burst. We, in our work, used E2E burst length as a measure to analyze the traces and found the results as given below. For EZE burst length plots, y—axis shows percentage of the corrupted received packets and x-axis shows the percentage of the faulty portion in a packet. Figure Vl-V shows E2E burst length for traces with Packet Error Rate, PER, of 40-50%. We see that about 30% of the corrupted received packets have E2E burst length equal to 10% of the packet. This means, in case of decoding failure, if parity data is transmitted only for 10% corrupted portion of a packet, about 30% of the corrupted received packets can be recovered. The corrupted portion can easily be identified by the side-information, as in our case. Then, each of 20%, 30% and 40% E2E burst length is 73 found in 10% of the corrupted packets. These results are very favorable and give proof of our idea to divide a packet into chunks and transmit parity data with the help of side- information for selected subsets only, instead of: 1- discarding whole packet, as in case of Conventional Standard (CS) schemes, like IEEE 802.11 ARQ schemes, explained in Chapter-I, or 2- requesting parity data for whole packet like in case of Forward-Error-Correction (FEC) schemes, like Automatic Code Embedding (ACE), explained in Chapter-l E2E Burst Length with PER = 40-50% 0.35 f.......,......... . I. ...... --.--.r .--...-._......-._..........._ 0.3 ............. ............. ......... . a, s s s z +- 0.25» ~ .92 ((13) 0 2 ......... o. 1: o 151 --------------- ~ ------------------------------------------------------ - .93 3 0.1 . ................................. 8 0.05 ----------- . o i i 1' '1 o 20 4o 60 80 100 Corrupted Portion in a Packet (%) Figure Vl- V: EZE Burst Length for Traces with PER = 40-50% Figure Vl-Vl shows E2E burst length for traces with PER 70-80%. It is important to note that this PER value corresponds to a channel in very bad state. Only 3-4% of corrupted packets have 10% E2E burst length. Here, each of 60%, 70% and 80% E2E burst length is found in 10% of the corrupted packets. Still we see that about 3-4% of the corrupted 74 received packets can be recovered by requesting parity data for only 10% of the packet size. 0.35 . ' ' 0.25.. : : : : E2E Burst Length with PER = 70—80% 1' I .0 10 O.‘l5~ .0 -L 0.05 Corrupted Packets o 20 410 so so 100 Corrupted Portion in a Packet (%) Figure Vl-VI: EZE Burst Length for Traces with PER = 70-80% 2E Burst Length with PER = 80-90% 0_4 1.1..- ....{1....-.-..- j I -..,N... ......w.-. % 0_3 _. ..................................................................... .. x 8 a. 02 ---------- “c: E 5 CD : : *5. a / E 0.1 ....-..--...-.. ---...-----.-------.---..----..-----E. ........ 2;---i ................. I... an- -—-—V = -e-V‘y'w’ I O ‘1.“__YJ..—-* . 1 i O 1 1 1 O 20 4O 60 80 100 Corrupted Portion in a Packet (%) Figure VI- VII: EZE Burst Length for Traces with PER = 80-90% 75 Figure VI-Vll shows E2E burst length for traces with PER 80-90%. Notice that this very high PER value corresponds to a channel in extremely bad state. Less than 1% of corrupted packets have 10% E2E burst length. Here, each of 70%, 80% and 90% E2E burst length is approximately found in 10% of the corrupted packets. Even in this scenario, over 10% packets require parity data for only 70% of the received packet. E2E Burst Length 0.4 I 1 T r 47 -E- PER = 40-50% 1 —e— PER = 70-80% 5 3 0.3 ----------- Jr- PER = 80-90% ............ - (I) E E 3 5 x E E > 8 s s o_ 0.2 ------------- -------------- -------------- . ............. . ........... - '0 E i B = s 3 0.1 ------------------- = .......... - ................. _ 5 s 0 . a . 00 20 40 60 80 100 Corrupted Portion in a Packet (%) Figure Vl-Vlll: E2E Burst Length Figure Vl-VIIl shows plots above in a single canvas for comparison purposes. We notice that as channel state gets worse and worse, E2E burst length increases on average. This reason for such results is that increasing PER values correspond to higher BER values, which contribute in increasing E2E burst lengths. As we mentioned in Chapter-l that 76 some previous works have made use of incremental parity data to cope with varying channel conditions. Examples of such works Automatic Code Embedding (ACE) and Reliable and Stable (RASE). But none of these works use side-information to enhance their performance. In fact, ACE requests incremental parity data for whole packet in all channel conditions. This leads to requesting parity data for subsets of a corrupted received packet which do not require any parity data for decoding. As a result, we see in Chapter-V that PRAISE outclasses state-of-art network protocols in terms of throughput, goodput and end-to-end bandwidth utilization in good and average network conditions. Even when the channel is in extremely bad states, PRAISE’s performance is comparable to that of RASE as in extremely bad channel conditions, parity data for whole packet (i.e. all of the subsets) is needed to be transmitted. 77 Chapter 7 - Results, Conclusions and Future Work Let us recall that in Chapter-1, in order to keep the discussion generic and not dependant on a particular implementation or standard, we consider three rather abstract communication schemes: 1) transmission over error/erasure channels, which represents the conventional standard (CS) protocols, like IEEE Automatic Repeat Request (ARQ) schemes; 2) transmission in the presence of a forward error-correction (FEC) based schemes, like Hybrid ARQ [38, 39] and more recent schemes like ZIPTX [37], Automatic Code Embedding (ACE) [34], and Reliable and Stable (RASE) [40]; 3) side- information enhanced transmission in presence of both, erasures and errors, using a forward-error correction scheme (SEFEC) like the proposed scheme, Parity localization for Rate Adaptability of Reliable and Stable Protocols (PRAISE). The two generic aspects of 1) forward error correction; 2) feedback mechanism (F8), are enough to explain the three communication schemes as described above. Forward error correction part can simply be segregated into two categories consisting of presence or absence of any forward error correction mechanism. Feedback mechanism can have many variants, ranging from simple binary feedback about reception of correct/false packet like in case of ARQ, to the feedback with flags requesting additional parity data for corrupted packets like in case of recent protocols like ACE [34] and RASE [40]. So under these two aspects, the following happens. 1) CS: the conventional standard protocol contains no FEC and requests the same packet even if a single bit is in error, example being IEEE802.11 ARQ scheme. In 78 2) IEEE802.11 ARQ protocol, error-detection information (ED) bits are added to data to be transmitted (such as cyclic redundancy check, CRC) and retransmissions are solution for losses. If a corrupted packet is received, it Is discarded without regard to the number and location of errors. This methodology ensures that the packet would eventually be recovered. However, this approach leads to a great deal of throughput degradation as even a single bit error leads to packet drops resulting in discard of a large number of correctly received data bits, ending up ’wasting’ a lot of useful data. Thus, network utilization deteriorates rapidly as channel bit error rate (BER) increases. FEC: FEC based protocols, which represent schemes like IEEE802.11 Hybrid ARQ schemes [38, 39] and more recent schemes like ZIPTX [37], ACE [34] and RASE [40], contain some sort of forward error correction and request additional parity data in case of reception of a corrupted packet. Hybrid ARQ (HARQ) protocols are proposed as an alternative to CS. In HARQ protocols, forward error correction bits are also added to the existing Error Detection (ED) bits, such as Reed-Solomon code, low-parity density-check code or Turbo code. In this way, these schemes reduce the number of re-transmissions as required in case of ARQ by making use of incremental channel codes. However, both ARQ and HARQ based approaches do not address the throughput stability issues in varying channel conditions, and thus lead to a great deal of throughput inefficiency. Other protocols like ZIPTX and ACE address the issues of reliability and/or stability in varying channel conditions but these fall short on many fronts. ZIPTX, 79 3) though provides a working system, ignores any aspect of stability. ACE takes into account both the issues of reliability and stability by embedding channel codes using well-defined code rates but ACE, i) lacks a practical demonstration system, ii) do not consider rate-adaptability to address throughput efficiency in changing network conditions. SEFEC: SEFEC is an alternative to above schemes. Similar to FEC based schemes, an SEFEC scheme requests additional parity using feedback flags, but the requested parity data is localized and request depends upon side-information received from physical (MAC) and link layers. 50 SEFEC is a cross-layer design which extracts beliefs associated with received data either at MAC/physical layer, or at link layer and decides to requests additional parity data for a particular subset of code depending on values of beliefs for a particular subset of code. Some previous works [35, 41, 42] have proposed cross-layer designs for multimedia applications to overcome throughput degradations and performance limitations imposed by traditional protocols. An example of such a work is UDP Lite [41], which relies on the error-resilient nature of multimedia content and makes adjustments to the protocol stack at the transport and the link layers in order to improve the bandwidth utilization. A major drawback of the existing cross-layer protocols is that their implementations require key modifications in transport and application layers. However the proposed cross-layer SEFEC design requires no modification in the subsequent layers since a single decoder is required for 'mother’ and ’daughter’ codes and side-information used to request 80 parity data is received from physical (MAC) and link layers. Therefore, and unlike receivers of FEC- based schemes, SEFEC receiver has RHCs, is rate-adaptive depending on varying channel conditions, distinguishes between erasures and errors in a received packet, and does not require any modification in transport and application layers. As we explained in Chapter 5 that current wireless network devices such as USB network adaptors, Peripheral Component Interconnect (PCI) wireless adaptor cards for computer desktops and notebooks, wireless Ethernet bridges, and Wireless Compact Flash Card Adapters for PDAs etc. are utilized to establish communication channels among different wireless users in various wireless environments. By design, these devices use IEEE802.11 standard to attain channel access, contention, and error control at the Physical (PHY) and MAC layers. IEEE 802.11 standard has some sort of basic error correction at PHY layer, like Reed Solomon codes etc. and this design strategy naturally leads to preventing PHY layer to pass distorted packets to the higher layers. The distorted packets are dropped right away at PHY layer, wasting a lot of useful data. So we faced the major challenge of utilization and alternation of link-layer corrupted packets, containing residual errors, at the receiver to: 1- Capture and measure the behavior of an error process of a wireless channel, 2- Analyze the residual errors, at link-layer, in a wireless channel to design suitable puncturing fractions in localized manner for rate-adaptability of error control protocols, 81 3- Implement error control protocols at the link-layer that employ and manipulate received corrupted packets, and 4- Extract side information from MAC/PHY layers to request localized parity for subsets with potentially highest number of errors. To cope with this issue, we need to modify the configuration of these devices to attain the distorted packets at the PHY/MAC layer. But, these off-the—shelf wireless devices are not Open source products, thus modification of the source code functionality is not possible. To overcome this problem, we use Software-Defined Radio (SDR) technology. Specifically, we use GNU-USRP platform as the communication system front-end on each sender and receiver node in our experiments. Since, GNU Radio is an open-source software development toolkit, we are able to easily reconfigure and modify its building blocks. In this way, we have complete control over the communication system configurationsdown to the FPGA/antenna level, and down to PHY/MAC layers and we are able to capture distorted packets received at the PHY/MAC layer and pass packets with residual errors to link layer. Furthermore, we are able to extract side information associated with each packet which we used to request additional parity data from encoder in case of decoding failure. Unless otherwise specified, following are the default parameters for conducting experiments and collecting channel traces: 82 Frequency: 5.1G Packet Size: 1500 Bytes (Range = 0-4096 bytes) No. of Packets in a session: 100,000 Modulation Scheme: GMSK Bursty Mode: Disabled To gauge the performance of the CS, FEC and SEFEC protocols over the wireless channel, we make use of two protocol-dependent parameters namely, 1) throughput; 2) goodput. We define throughput over a transmission channel as: throughput = # of bits received correct /total # of bits ...... (7.1) And we define goodput over a transmission channel as: goodput = # of correct bits containing actual data/total # of bits ...... (7.2) So for a session, goodput becomes ratio of total number of bits that contained actual data and are received correctly to the total number of bits transmitted for that session. In this way, the goodput parameter excludes parity bits from calculations of throughput values. We compare the values of the above-mentioned protocol-dependent parameters against two wireless channel metrics, 1) Packet Error Rate (PER); 2) Bit Error Rate (BER). So our results fall in two categories depending upon wireless channel metrics and we measure each of the two protocol-dependent parameters against each of the metric. 83 7.1- Wireless Channel Metric BER Bit Error Rate (BER) is defined as the rate at which errors occur in a transmission system. BER is a unit-less performance quantity and is expressed as a percentage number. The definition of bit error rate can be expressed as: BER = number of bits in errors/total number of bits ...... (7.3) BER is a parameter which gives an excellent indication of the performance of a wireless channel. As one of the main parameters of interest in any channel is the number of errors that occur, the bit error rate is a key parameter. So we chose it as one of the channel metrics to gauge the performance of protocol-dependent parameters. Figure VII-l shows the plot for Throughput vs. Channel BER for the five protocols falling in three categories. From plot below, we see that the Conventional Standard (CS) ARQ suffers the most with increasing channel BER values. The average throughput of the CS- ARQ scheme falls to 10% as channel’s average BER increases to 0.1. RASE makes use of incremental parity data to retrieve packets, resulting in increased channel bandwidth and throughput, and hence it performs better than HARQ-l and HARQ-II among FEC schemes. It is evident from the plot that SEFEC-PRAISE outperforms all CS and FEC schemes in terms of throughput in all channel conditions. PRAISE’s performance is comparable to CS and FEC schemes in channel with very low BER values. But as channel BER increases, PRAISE’s superiority over CS and FEC schemes becomes evident. At the channel’s average BER of 0.15, PRAISE outperforms the state-of-art FEC scheme, RASE by about 12% high throughput value. 84 .0 C3 ,-._- 1 ....~. -.‘._..____._,,., _ .....w. .. ... 4...... -m ...-aw,- Average Throughput O O A 01 03' . ——SEFEC-PRAISE ”- 0,2- , . ----'-FEC-RASE . . ' . "WFEC-HARQ-Il 0.1; ' ' .. . FEC-HARQ-l : _ . CS-ARO 00 0.05 0.1 0.15 0.2 0.25 0.3 Channel Average BER Figure VII-l: Throughput Vs. Channel BER Figure VII-ll shows the plot for Goodput vs. Channel BER for the five protocols falling in three categories. From plot below, we again see that the Conventional Standard (CS) ARQ suffers the most with increasing channel BER values. When the channel is in good condition (BER<0.02), CS-ARQ’s performance is the best among all five protocols as in these scenario, goodput and throughput values are equal and all the data received is the ’useful’ data in case of CS-ARQ scheme. But as BER values increase, CS—ARQ’s goodput drastically falls. Since the values of goodput and throughput are same in case of CS-ARQ. we see that the average goodput of the CS-ARQ scheme falls to 10% as channel’s average BER increases to 0.1. 85 In FEC schemes, forward error correction bits are added to the existing ED bits to correct a subset of all errors while relying on ARQ to detect uncorrectable errors. As a result FEC-HARQ I/Il perform better than CS-ARQ in poor signal conditions, but in its simplest form this comes at the expense of significantly lower goodput in good signal conditions. Here the signal quality cross-over point below which FEC-HARQ is better, and above which CS-ARQ is better is at BER = 0.02 in case of HARQ-ll and at BER = 0.03 in case of HARQ-I. RASE makes use of incremental parity data to retrieve corrupted packets, resulting in increased channel bandwidth and goodput, and hence it performs better than HARQ-I and HARQ-ll among FEC schemes. Here the signal quality cross-over point below which FEC-RASE is better, and above which CS-ARQ is better is at BER = 0.01. It is evident from the plot that SEFEC-PRAISE outperforms FEC-HARQ I/ll schemes in terms of goodput in all channel conditions. The signal quality cross-over point below which SEFEC-PRAISE is better, and above which CS-ARQ is better is at BER = 0.01. Since . . C . . PRAISE needs additional f = [logz (1)] feedback bits to request parity for 1 out of c chunks of lowest reliability, its performance in terms of goodput suffers insignificantly (due to small number of f bits) than that of FEC-RASE at lower BER values (BER<0.02). But as channel BER increases to 0.15, it outperforms state-of-art FEC-RASE by 0.9% higher goodput values. 86 0944.2, _ O "a: ’fi..' O.8"‘.‘"i. ...~~o- a... *5 0.7. . Q. ‘ ' .' ‘\‘~ 8 0.6- - o ‘3 0.5- °o on IE 0.4 (D ' 2 0 3_ . ' W...’.;:-.--._....--.....1.---.--_...._.--._-- ‘ 0 ~ —-SEFEC-PRAISE 0.2- , "'"FEC-RASE _ ' . ----- FEC-HARQ-Il 0.1-- - 1' '- FEC-HARQ-I 0 -...'...-95'AR9-_-.-.-- . . 0 0.05 0.1 0.15 0.2 0.25 0.3 Channel Average BER Figure VII-ll: Goodput Vs. Channel BER 7.2- Wireless Channel Metric PER The Packet Error Rate (PER) is the number of incorrectly transferred data packets divided by the number of transferred packets. A packet is assumed to be incorrect if at least one bit is incorrect. PER is a unit-less performance quantity and is expressed as a percentage number. Mathematically, PER can be expressed as: PER = number of packets in errors/ total number of packets ...... (7.4) PER is a parameter which gives an excellent big-picture of the overall performance of a wireless channel. As one of the main parameters of interest in any channel is the frequency of occurrence of errors, the packet error rate is a key parameter. That’s why 87 we chose it as one of the channel metrics to gauge the performance of protocol- dependent parameters. Figure Vll-lll shows the plot for Throughput vs. Channel PER for the five protocols (ARQ, HARQ-I/ll, RASE and PRAISE) falling in three categories of CS, FEC and SEFEC as described above. Here we again see that the Conventional Standard (CS) ARQ suffers the most with increasing channel PER values. The average throughput of the CS-ARQ scheme falls to 10% as channel’s average PER increases to 0.85. RASE makes use of incremental parity data to retrieve packets, resulting in increased channel bandwidth and throughput, and hence it performs better than HARQ-l and HARQ-ll among FEC schemes. it is evident from the plot that SEFEC-PRAISE outperforms all CS and FEC schemes in terms of throughput in all channel conditions. PRAISE’s performance is comparable to FEC schemes in channel with low PER values. But as channel PER increases to over 20%, PRAISE’s superiority over FEC schemes becomes evident. At the channel’s average PER of 0.80, PRAISE outperforms HARQ-l by about 27%, HARQ—II by 23%, and the state-of-art FEC scheme, RASE by about 4% higher throughput value. 88 0.9;- . i 0.85 ' 307'; g E 3 06+ ‘ .5 0.5 '- - “ g, S 0.4i . Q) 0 3 j , . l. . . . . - 55 —SEFEC-PRAISE . 023.. "-"FEC-RASE , . < w e. . ‘ M .. ----- FEC-HARQ-II . ° , 0.1 . FEC-HARQ-I e . - ~ 0 'CSARQ_.. , o 0.2 0.4 0.6 0.8 1 Channel Average PER Figure VII-III: Throughput Vs. Channel PER Figure VII-IV shows the plot for Goodput vs. Channel PER for all the five protocols. From plot below, we again see that the Conventional Standard (CS) ARQ suffers the most with increasing channel PER values. When the channel is in good condition (PER<0.1), CS- ARQ’s performance is the best among all five protocols because in these scenario, goodput and throughput values are equal and all the data received is the ’useful’ data in case of CS-ARQ scheme. But as PER values increase, CS-ARQ’s goodput drastically falls. Since the values of goodput and throughput are same in case of CS-ARQ, we see that the average goodput of the CS-ARQ scheme falls to 10% as channel’s average PER increases to 0.85. 89 In FEC schemes, forward error correction bits are added to the existing ED bits to correct a subset of all errors while relying on ARQ to detect uncorrectable errors. As a result FEC-HARQ l/II perform better than CS-ARQ in poor signal conditions, but in its simplest form this comes at the expense of significantly lower goodput in good signal conditions. Here the signal quality cross-over point below which FEC-HARQ is better, and above which CS-ARQ is better is at PER = 0.2 in case of HARQ-ll and at PER = 0.36 in case of HARQ-I. RASE makes use of incremental parity data to retrieve corrupted packets, resulting in increased channel bandwidth and goodput, and hence it performs better than HARQ-I and HARQ-ll among FEC schemes. Here the signal quality cross-over point below which FEC-RASE is better, and above which CS-ARQ is better is at PER = 0.1. It is evident from the plot that SEFEC-PRAISE outperforms FEC-HARQ l/ll schemes in terms of goodput in all channel conditions. The signal quality cross-over point below which SEFEC-PRAISE is better, and above which CS-ARQ is better is at PER = 0.01. Since PRAISE needs additional f = [10926)] feedback bits to request parity for I out of c chunks of lowest reliability, its performance in terms of goodput suffers insignificantly (due to small number of f bits) than that of FEC-RASE at lower PER values (PER<0.3). But as channel PER increases to 0.9, it outperforms state-of-art FEC-RASE by 0.2% higher goodput values. 90 Goodput vs. Channel PER '5 Q. 1 ‘~ 8 06» ..... . - a) OSlr .0 s“ .. e 0.4;: ' a: ; 0 J > 031w » 4 < ' g—SEFEC-PRAISE . ; 0.2t-*--'-FEC-RASE ._ .. . .. . g ----- FEC-HARQ—ll ° , i 0.1 ”*‘FEC-HARQ-l O? , '. CSARO , o 0.2 0.4 0.6 0.8 1 Channel Average PER Figure VII-IV: Goodput Vs. Channel PER 73- Analysis of Results for Different Channel Metrics: We explained our experimental setup in Chapter-5 of the thesis. Our experimental test- bed consists of two USRP devices: one connected to a desktop PC which we refer to as the Data-Host (DH) PC and the other connected to the Data-Ghost (06) laptop computer. DH is hosting the data to be transmitted and 06 is streaming data from DH. In our experiments, the application layer in DH and 06 generates packet data and the acknowledgment packets respectively. We set up the wireless communication system between DH and 06 using the parameters detailed in Chapter-5. 91 Using our GNU-USRP based wireless platform, we conducted several communication scenarios to capture the behavior of wireless error in the presence of fading, interference and mobility. We deployed a Markovian channel model to collect data, and details of the deployed channel model can be found in Chapter-4 of the thesis. Our analysis consists of measuring 100 wireless channel conditions which are categorized in four groups: 1- Environment factor: To cater for the environments effects on wireless channel conditions, we carried out extensive set of experiments in both, open-spaced out-door environment, i.e. outside the building, and in closed-space in-door environment, i.e. inside the building. For in-door setting, several factors contributed in wireless channel conditions as explained in coming lines. However, for out-door setting, the wireless communication was mostly line-of- sight (LOS) communication and we noticed that distance was the only metric for wireless connection failure and packet dropping. Fading factor: In this set of scenarios, the 06 laptop is located within certain distances of DH. The distance between 06 and DH governs the impact of fading on the wireless communication. In particular, the error conditions for channels where DH and 06 are relatively close to each other (e.g., less than 3m) are remarkably better than those with 06 and DH are farther. It is also important to note that placing D6 and DH very close to each other (e.g., less than 1/2 m) causes a lot of missing packet at 06 due to interference caused by DH, so we did not consider such close distances. 92 3- Interference factor: To capture the impact of interference on wireless channel condition, we establish wireless communication in the presence of other wireless networks. These networks include Wi-Fi in our lab (i.e. WAVES lab), Wi- Fi in the building (i.e. College of Engineering), and in the presence of other hot- spots established over some laptop computers. It is evident that as more active wireless networks are presented in the environment, the likelihood of packet collisions increases leading to frequent packet errors due to interference. Mobility factor: The DH transmits data packets to the DG laptop which is a mobile node and changes its location frequently. Please figure lll-lll to get an idea of the room locations. In this set of experiments, the mobility is conducted within a room (i.e. WAVES lab), within the hallway (next to the room where DH resides), and within the room opposite to hallway. However the wireless connection never fails; all the transmitted packets are received by 06. We characterize wireless channel condition with average Bit Error Rate (BER) and average Packet Error Rate (PER). In figure VII-V, we compare these parameters (i.e. channel BER and channel PER) for the collected traces after deployment of a specific protocol, to get an insight on the results. From Figure Vll-V, we see that the range of corresponding channel average BER and average PER values lie in the range of 10% for all traces collected for the deployed protocols. The collected data reveals that even when the channel average PER approaches 0.8, the channel average BER value is 0.13, 0.07, 0.13, 0.14 and 0.07 in case 93 of SEFEC-PRAISE, FEC-RASE, FEC-HARQ-II, FEC-HARQ-l, and CS-ARQ respectively. These values present quite lower channel average BER values for the corresponding higher channel average PER values. This trend is platform and implementation specific and explains lower advantage of SEFEC-PRAISE (in terms of throughput and goodput) over FEC-RASE in terms of channel PER values as compared to channel BER values. We can also safely state that if we get higher BER values for corresponding PER values for some other platform/implementation, SEFEC-PRAISE’s performance (in terms of throughput, goodput, and end-to-end bandwidth utilization) will get more boost as compared to the state-of-art FEC-RASE for both channel metrics, i.e. BER and PER values. Channel PER vs. Channel BER Y 'I 1 5 . U +SEFEC-PRAISE "‘ +FEC-RASE . é . ' «e-FEC—HARQ-II ; 0.1:. ... ' +FEC-HARQ-l ~ ; ; : -e-cs-ARQ . . i J 1 1 I . 0 0.05 0.1 0.15 0.2 0.25 0.3 Channel Average BER Figure VII-V: Channel BER vs. Channel PER 94 7.4 Conclusions and Future Directions: In this work, we provided a framework for the rate adaptability of wireless protocols. Wireless channel is more prone to errors than wired media and we proposed localized puncturing patterns to adapt rates of wireless protocols with time-varying wireless channel conditions. First we developed the channel model that we used to develop the proposed scheme. We deployed a Markovian channel model to model the errors introduced in the channel. The Markovian channel is characterized by its Hybrid Erasure- Error Rate (HEER) in each state, and within each state, the channel is modeled by a cascade of a Binary Erasure Channel (BEC), to model the puncturing operation at encoder end, and a Binary Symmetric Channel (BSC) to model the wireless channel. We used GNU-USRP based implementation of a Software Defined Radio (SDR) to conduct experiments. We divided our experimentation phase in two stages. In the first stage, we collected traces to train our Markovian channel model and to analyze the element of burstiness in a packet. We analyzed the element of burstiness using three standard techniques; 1) Error Distributions within a Packet; 2) Bit Error Rate (BER) vs. Cumulative Density Function (CDF); 3) End-to-End (E2E) Burst Length within Packets. In the second phase of experiments, using our GNU-USRP based wireless platform, we conducted several communication scenarios to capture the behavior of wireless error in the presence of fading, interference and mobility. Our analysis in this phase consists of measuring 100 wireless channel conditions which are categorized in four groups; 1) Environment Factor; 2) Fading Factor; 3) Interference Factor; 4) Mobility Factor. 95 We then focus on code-designing aspects and present limits on designing localized puncturing fractions. We used Density Evolution techniques to find noise thresholds and extract degree distributions out of LDPC ensembles for given code rates and allowed degrees. Based on these results, we designed puncturing patterns for the proposed scheme. We analyzed the performance of five network protocols; 1) Parity Localization for Rate Adaptability of Reliable and Stable Wireless Protocols (PRAISE), 2) Reliable and Stable (RASE), 3) Hybrid ARQ-ll, 4) Hybrid ARQ-l, and 5) Automatic Repeat Request (ARQ) over GNU-USRP platform. To keep discussion generic, we divided these protocols in three categories; 1) Conventional Standard (CS, like ARQ), 2) Forward Error Correction enabled Protocols (FEC, like HARQ-l, HARQ-II, and RASE), 3) Side-Information Enhanced Forward Error Correction enabled Protocols (SEFEC, like PRAISE). To gauge the performance of these protocols over the wireless channel, we make use of two protocol—dependent parameters namely, 1) throughput; 2) goodput. We compared the values of the above-mentioned protocol-dependent parameters against two wireless channel metrics, 1) Packet Error Rate (PER); 2) Bit Error Rate (BER). So our results fall in two categories depending upon wireless channel metrics and we measure each of the two protocol-dependent parameters against each of the metric. The results show that SEFEC-PRAISE outperformed state-of-art FEC-RASE by 0.9% and 0.2% higher goodput values as channel BER and channel PER increase to 0.15 and 0.9 respectively. 96 Similarly, SEFEC-PRAISE showed 12% and 0.4% higher throughput values than FEC-RASE as channel BER and channel PER increase to 0.15 and 0.8 respectively. During the course of this work we identified some future directions. We will work on the development of a more comprehensive set of error traces. This set will comprise of the error traces collected for IEEE standard networking protocols (like IEEE 802.11, IEEE 802.15 etc.) at all bitrates for varying client positions and network configurations. The effects of environment, interference, fading and mobility will be further distinguishable with this complete data set. This is an active area_of research and our preliminary analysis depicts that the position of the client plays an instrumental role in determining the overall throughput of the network particularly in Iine-of—sight out-door environments. Moreover, cross- layer strategies that can enhance the side-information provided by the PHY/MAC layer in our case need further investigation. We would like to supplement these strategies with modeling and information extraction from link and transport layers without doing any modification at these layers to boost the overall performance of the system. We would also like to investigate information extraction from intermediate stages of Belief Propagation Algorithm while decoding LDPC codes. In our previous work, we designed puncturing patterns based on online Density Evolution tools. We would like to further investigate other techniques to design puncturing patterns that can provide a suitable alternative for both, regular and irregular LDPC ensembles, and can improve end-to—end system performance. 97 References: [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] C. E. Shannon, ”A Mathematical Theory of Communication”, Bell System Technical Journal, 1948. R. G. Gallager, ”Low Density Parity-Check Codes”, MIT Press, Cambridge, MA, 1963. M. Luby, M. Mitzenmacher, A. Shokrollahi, and D. Spielman, ”Analysis of Low Density Codes and Improved Designs using Irregular Graphs", in IEEE Transactions on Information Theory, 2001. M. Luby, M. Mitzenmacher, and A. Shokrollahi, ”Analysis of Random Processes via And-Or Tree Evaluation", in Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, 1998. M. Yang, W. Ryan, and Y. Li, ”Design of Efficiently-Encodable Moderate-Length High-Rate Irregular LDPC Codes”, in IEEE Transactions on Communications, 2004. M. Yang, W. Ryan, “Lowering the Error Rate Floors of Moderate—Length High- Rate LDPC Codes”, in IEEE International Symposium on Information Theory, 2003 M. Yang, W. Ryan, Y. Li, ”Design of Efficiently-Encodable Moderate-Length High- Rate LDPC Codes”, in IEEE Transactions on Communications, 2003. T. Richardson and R. Urbanke, ”The Capacity of Low-Density Parity Check Codes under Message-Passing Decoding", in IEEE Transactions on Information Theory, 2001. E. Eleftheriou, S. Olcer, ”Low-Density Parity-Check Codes for Digital Subscriber Lines" in Proceedings of International Conference on Communications, 2002. J. Pearl, ”Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference”, Morgan Kaufmann Publishers, Inc., 1988. T. Richardson, A. Shokrollahi, and R. Urbanke, ”Design of Capacity-Approaching Irregular Low-Density Parity-Check Codes", in IEEE Transactions on Information Theory, 2001. M. Luby, M. Mitzenmacher, A. Shokrollahi, and D. Spielman, ”Efficient Erasure Correcting Codes", in IEEE Transactions on Information Theory, 2001. D. Mackay and M. Davey, ”Evaluation of Gallager codes for Short Block Length and High Rate Applications”, in Codes, Systems, and Graphical Models: Vol. 123 of IMA Volumes in Mathematics and its Applications, Spring-Verlag, 2000. 98 [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] B. Vasic, ”Structured Iteratively Decodable Codes Based on Steiner Systems and their Application to Magnetic Recording", in Proceedings of IEEE GlobeCom Conference, 2001. P. Oswald and A. Shokrollahi, ”Capacity-Achieving Sequences for the Erasure Channel”, in IEEE International Symposium on Information Theory, 2002. I. Sason and G. Wiechman, “On Achievable Rates and Complexity of LDPC Codes for Parallel Channels: Information-Theoretic Bounds and Applications”, in IEEE International Symposium on Information Theory, 2006. I. Sason and G. Wiechman, ”On Achievable Rates and Complexity of LDPC Codes Over Parallel Channels: Bounds and Applications", in IEEE International Symposium on Information Theory, 2007. B. Vasic, ”Combinatorial Constructions of Low-Density Parity-Check Codes for Iterative Decoding from Kirkman Triple Systems”, in Proceedings of IEEE International Symposium on Information Theory, 2002. S. Johnson and S. Weller, ”Construction of Low-Density Parity-Check Codes from Kirkman Triple Systems”, in Proceedings of IEEE GIobeCom Conference, 2001. Y. Kou, 5. Lin, and M. Fossorier, ”Low-Density Parity-Check Codes based on Finite Geometries: A Rediscovery and New Results”, in IEEE Transactions on Information Theory, 2001. D. MacKay, and R. Neal, "Good Codes based on very Sparse Matrices”, in Lecture Notes in Computer Science, Springer, 1995. D. MacKay, “Good Error-Correcting Codes based on very Sparse Matrices”, in IEEE Transactions on Information Theory, 1999. R. Lucas, M. Fossorier, Y. Kou, S. Lin, ”Iterative Decoding of One-Step Majority Logic Decodable Codes based on Belief Propagation”, in IEEE Transactions on Communications, 2000. D. Divsalar, H. Jin, and R. McEIiece, ”Coding Theorems for Turbo like Codes”, in Proceedings of the Annual Allerton Conference on Communication, Control and Communication, 1998. H. Jin, A. Khandekar, and R. McEliece, ”Irregular Repeat-Accumulate Codes”, in Proceedings of 2nd International Symposium on Turbo Codes and Related Topics, 2000. J. Fan, ”Constrained Coding and Soft Iterative Decoding for Storage”, PhD thesis, Stanford University, 1999. 99 [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] J. Fan, ”Array Codes as Low-Density Parity-Check Codes”, in Proc. 2nd Int. Symposium on Turbo Codes and Related Topics, 2000. T Okamura, ”A Hybrid ARQ Scheme Based on Shortened Low-Density Parity- Check Codes”, in IEEE Wireless Communication and Networking Conference, 2008. J. Hagenauer, ”Rate-compatible Punctured Cconvolutional Codes (RCPC codes) and their Applications” in IEEE Transactions on Communications, 1988. J. Ha, J. Kim, and S. McLaughlin, ”Puncturing for Finite Length Low-Density Parity- Check Codes”, in IEEE International Symposium on Information Theory, ISIT, 2004 H. Pishro-Nik, and F. Fekri, ”Results on Punctured LDPC Codes”, in IEEE Information Theory Workshop, 2004. H. Pishro-Nik, and F. Fekri, ”Results on Punctured Low-Density Parity-Check Codes and Improved Iterative Decoding Techniques”, in IEEE Transactions on Information Theory, 2007. C. Hsu and A. Anastasopoulos, ”Capacity Achieving LDPC Codes through Puncturing”, in IEEE International Conference on Wireless Networks, Communications and Mobile Computing, 2005. S. Soltani, K. Misra and H. Radha, ”On Link-Layer Reliability and Stability for Wireless Communication”, IEEE Conference on Mobile Computing and Networking (MOBICOM 08), 2008. S. Karande and H. Radha, ”The Utility of Hybrid Error Erasure LDPC (HEEL) Codes for Wireless Multimedia”, IEEE International Conference on Communications (ICC), May 2005. J. Ha, J. Kim, and S. McLaughlin, ”Rate-Compatible Puncturing of Low-Density Parity—Check Codes”, in IEEE Transactions on Information Theory, November 2004. K. Lin, N. Kushman, and D. Katabi, “ZipTx: Harnessing Partial Packets in 802.11 Networks”, in IEEE Conference on Mobile Computing and Networking (MOBICOM 08), 2008. 5. Lin and P. Yu, ”A Hybrid ARQ Scheme with Parity Retransmission for Error Control of Satellite Channels”, in IEEE Transactions on Communications, 1982. Y. Wang and S. Lin, ”A Modified Selective-repeat Type—ll Hybrid ARQ System and its Performance Analyses”, in IEEE Transactions on Communications, 1983. 100 [40] [41] [42] S. Soltani, K. Misra, A. Khan, and H. Radha, ”On the Design and Implementation of a Reliable Wireless Link Layer Protocol with Guaranteed Sustainable Flows”, (To be Submitted). L. Larzon, M. Degermark, and S. Pink, ”UDP Lite for Real Time Multimedia Applications”, in IEEE International Conference on Communications (ICC 99), lune1999. S. Karande and H. Radha, ”Hybrid Erasure-Error Protocols for Wireless Video”, in IEEE Transactions on Multimedia, February 2007. 101 ""IIIIIIIIIIIIIIIIIIIII'IIIIIIIIII“