Advanced Wireless Networks - 4G Technologies

4.3.3 Error-control schemes

Nine RS codes as shown in Table 4.3 are considered. The reason for limiting the number of codes is that a different encoder–decoder pair is needed for each (N , K , q) RS code. Described below are error-control schemes for the link layer.

4.3.3.1 A hybrid of FEC and ARQ

A hybrid of FEC and ARQ is used. The receiver attempts to correct errors first and, if the errors cannot be corrected, retransmission of the packet is requested. When errors are successfully corrected, an acknowledgment is transmitted to the sender and, when errors are detected but not correctable, a negative acknowledgment (NAK) is sent. In this section the selective-repeat (SR) ARQ is assumed. The sender keeps transmitting packets without waiting for ACK/NAK of those packets already transmitted. If NAK of a transmitted packet is received, or if neither ACK nor NAK of a packet is received within a timeout interval, the packet is retransmitted. The timeout interval is determined based on the roundtrip time. As will be clear below, the schemes considered here do not depend on ARQ, and hence they can be used in conjunction with any other ARQ schemes, such as stop-and-wait (SW) and go-back-N (GBN).

Throughput performance and complexity may depend on the underlying ARQ scheme. The SR-ARQ scheme is known to achieve better throughput performance than SW and GBN-ARQ at the expense of higher complexity.

An ACK/NAK packet consists of four bytes, in which the first two bytes are for the frame number of the packet associated with ACK/NAK, the third byte is to inform (1) whether it is an ACK or NAK, and (2) the adapted code rate. The last byte is a checksum. As discussed in Section 4.1, the code rate is mainly adapted by the receiver depending on the estimated channel state/condition; the code-rate information is fed back to the sender within each ACK/NAK packet. These four bytes are encoded by (148, 32) BCH code, which is a shortened code from (255, 139) BCH code adopted for the MAC header error protection.

4.3.3.2 Sender side

An IP packet is fragmented into a number of segments, referred to as user data, depending on the maximum user data size that can be accommodated in a MAC frame, or the maximum transmission unit (MTU). The MTU of the WaveLAN is originally 1.5 kbytes. In this segment, MTU is adapted dynamically as required by the underlying error-control scheme. The CRC is calculated for both the user data and MAC header. The combined user data and

130 ADAPTIVE AND RECONFIGURABLE LINK LAYER

CRC are then divided into M segments, where each of the first M − 1 segments is Kb bits long and the length of the last segment is ≤Kb bits. Note that MTU can be determined as MKb −32 bits, where −32 represents the CRC overhead. Each segment is encoded with (N, K , 2b) RS code. For the last segment, code shortening might be needed. The MAC header is then encoded by (255, 139) BCH code. Note that one byte of the header is used to represent the information of the error-control code such as N , K , and M. For the schemes discussed in this segment, only a set of codes is used, so one byte suffices to specify all the necessary information. The MAC frame forms the structure, as shown in Figure 4.17.

4.3.3.3 Receiver side

The error control at the receiver works as follows:

(1)The header of the received frame is decoded at the MAC sublayer. If the header is successfully decoded and, if the frame is found to be destined for itself, the user data with M RS-coded segments as well as the RS code information from the header are sent upward to the link layer.

(2)At the link layer, each of M RS-coded segments is first decoded by the RS decoder, then the entire frame (including the header and user data) is checked by the CRC decoder.

As described in the next section, the RS decoder at the receiver first attempts to correct errors. If the errors are uncorrectable, only their presence will be detected. Note that errors can be detected in three different places in the receiver: the MAC sublayer by the BCH decoder, the link layer by the RS decoder, and finally by the CRC decoder. This three-level error detection detects virtually all uncorrected errors.

4.3.3.4 Three error-control schemes

The following three possible error-control schemes using the above error-control facilities are considered.

FEC1 – M = 1, when a long RS code with a large N is used for each packet.

FEC2 – M =1 and the entire packet is retransmitted if any RS code segment has uncorrectable errors.

FEC3 – M =1 and each code segment with uncorrectable errors is requested to be retransmitted.

Then, a set of those code segments received in error is retransmitted by the sender in one MAC frame. Note that, for FEC3, a simple form of ACK and NAK is not enough; more on this issue will be discussed later. A packet decoded without any RS decoding failure can have undetected errors as explained in the next section. These errors are most likely to be detected by the CRC. In this case, the sender is requested to retransmit the entire packet for all three schemes.

132 ADAPTIVE AND RECONFIGURABLE LINK LAYER

When c = c1, the code is adapted to c0 if there was only a single or no symbol error during the last L frames received for the smallest L such that, P0,1 NM,L > 1 where NM,L is the total number of RS symbols in the last L frames. Note that the number of symbol errors in an RS code segment is readily available from the decoder unless the decoding fails.

4.3.3.7 Decrease in code rate

When a packet needs to be retransmitted due to a CRC error for c =c0, the code rate is not adapted in order to defer the adaptation decision until the next packet is received since a CRC error is very rare and will not usually happen over consecutive packets. On the other hand, when c = ci for i = 1, 2 and a packet needs to be retransmitted due to RS decoding failures, the code rate is decreased by one step, i.e. ci ci+1 for i = 1, 2, if any of the following conditions occurs:

when all RS segments of a packet result in decoding failures;

when more than a half of all RS segments in the last two packets result in decoding failures;

when three of the last 10 received packets result in decoding failures.

The above adaptation rule for code-rate decrease may appear very ad hoc but, with the third condition, we try to limit the retransmission probability to under 0.3 since a similar or better throughput efficiency can otherwise be achieved with the next lower rate code. The first and second conditions, on the other hand, render prompt adaptation for an abrupt change of the channel condition.

Now, when c = c0, the code is adapted to c1 if there were more than one CRC error detections in the last 10 received packets in order to keep the retransmission probability under 0.2. When the code rate is adapted to the decrease, and it is known to the sender, the sender encodes packets with the adapted code rate. The packets which need to be retransmitted are also re-encoded. Note that, for example, 229 symbols encoded by (255, 229, 256) RS code cannot be reencoded by (255, 153, 256) RS code. For a packet encoded by ci code to be re-encoded by code ci+1, the user data is divided first into two equal-sized packets (i.e. IP fragmentation) if the user data cannot be accommodated in ci+1, then each encoded by ci+1.

Finally, the code rate can also be decreased by the sender’s decision. That is, upon expiration of the retransmission time out, the code is set to c3. The rationale behind this adaptation is that a time-out happens due to the corruption of the MAC header or the loss of ACK/NAK while both the header and ACK/NAK are protected by very strong codes, thus implying that the channel is very bad.

4.3.4 Performance of adaptive FEC2

4.3.4.1 Link model

A very simple wireless network environment is used to evaluate the proposed adaptive errorcontrol scheme. There is only one sender and one receiver in the network, where the sender is assumed to have an infinite amount of information to send. Therefore, all the packets are transmitted in a full-length MAC frame composed of six RS code segments. Immediately

t1, 0

Figure 4.18 Two-state Markov chain model for the channel.

after receiving/decoding a packet, the receiver sends an ACK/NAK for the packet. Upon receiving the ACK/NAK, the sender determines whether to transmit a new packet or retransmit the previously sent one. When the retransmission time-out happens consecutively, the retransmissions are backed off exponentially. That is, for 2, 3, 4, . . . consecutive time-outs, the retransmission is deferred for the time of 1, 2, 4, . . . full-length packet transmissions, because consecutive time-out expirations implies that the channel is too bad for a packet to go through successfully.

4.3.4.2 Channel model

The channel is modelled by a two-state Markov chain, which is widely accepted to model the multipath fading channel, as shown in Figure 4.18. The channel state is either good or bad and can change on bit boundaries, that is, the channel condition stays in a state during one bit duration. Following the widely accepted Rayleigh fading model, which corresponds to the case of no line-of-sight path between the sender and receiver, we can derive the transition probabilities t0,1 and t1,0 as follows. First, Rappaport [41] provides the level-crossing rate, defined as the expected rate at which the Rayleigh fading envelope, normalized to the local root mean square (rms) signal level Rrms, crosses a threshold level in a positive-going direction:

where the maximum Doppler frequency is given by fm = ν/λ for the mobile speed v and the wavelength λ of the carrier and the normalized threshold fading envelope is given by ρ = R/ Rrms. Next, the average fade duration, defined as the average period of time for which the received signal is below the threshold level, is given by [41]

Using the above formulas and assuming steady-state conditions, the probabilities μ0 and μ1 that the channel is in good and bad states, respectively, are given by [38]

134 ADAPTIVE AND RECONFIGURABLE LINK LAYER

Finally, the state transition probabilities can be approximated by [42]

where Rtk = Rtμk, and Rt is the symbol transmission rate. With the transmission rate Rt = 1 Mbps, the mobile speed v = 2 km/h (pedestrian speed), the carrier frequency f = 900 MHz (λ = c/f = 1/3m), and the normalized threshold fading envelope ρ = 0.3, we obtain

Assuming the binary phase shift keying (BPSK) modulation, the bit error rates (BERs) Pb,0 and Pb,1 when the channel is in good and bad states, respectively, can be calculated as [43]

the conditional distribution of the instantaneous SNR γ in a given state with the mean SNR γ¯ is

for γi < γ < γi−1 and the set {γ−1, γ0, γ1} = ∞, ρ2γ¯ , 0 . Note that the mean SNR γ¯ depends on the transmitted power, signal attenuation over the channel, and others.

4.3.5 Simulation results

Figure 4.19 shows the throughput efficiencies as the mean SNR increases for five different cases of adaptive FEC2: (1) two marked with ‘fixed w/K ’ are the nonadaptive versions of FEC2 with (255, K , 256) codes; (2) one marked with ‘w/exp backoff’ is the adaptive FEC2 we are considering; (3) one marked with ‘w/o exp backoff’ is the adaptive FEC2 without exponential back-off; and (4) one marked with ‘ideal’ is an ideal version of FEC2, in which the code rate is determined after seeing errors in the received packet; that is, if these errors are uncorrectable even with rc = 0.3 code, the packet is assumed not to be transmitted at all (i.e. the transmission is deferred), while the code which can correct all these errors with the maximum code rate is selected otherwise. Basically, there is no retransmission in the ideal version. This ideal and unrealistic version can be used as a reference (or an upper bound) of the throughput efficiency. The figure demonstrates in which region and how much the adaptive scheme offers better performance.

Mean SNR (dB)

Figure 4.19 Throughput efficiency vs mean SNR.

4.4 STOCHASTIC LEARNING LINK LAYER PROTOCOL

Link layer ARQ protocols such as SW ARQ and SR ARQ, considered so far, recover from errors by retransmitting the erroneously transmitted packets regardless of the channel state. Such persistent retransmission schemes may lead to wasted energy consumption due to unnecessary packet losses and therefore additional retransmissions [44]. Discussions on this problem can be found in References [44–47]. In this section, we discuss a link layer algorithm that can produce soft predictions of the next network state given the past states, i.e. probabilities of the next state being any of the possible states are estimated.

The goal is to predict the wireless network state without a priori knowledge of the state transition probabilities and accordingly change the link layer transmission control for energy efficiency. Towards this objective a stochastic iterative learning control technique is used based on a stochastic learning automaton [48, 49]. The state of the wireless network is learnt on the fly by the transmitter via simple adaptive stochastic learning based on feedback from the receiver regarding the quality of the wireless link. Then a link layer control algorithm optimizes the transmission policy accordingly. That is, in a time slot the link layer control protocol either chooses to transmit a packet or not based on the channel state prediction produced by the stochastic learning algorithm. Energy efficiency is traded off for delay during this process.

4.4.1 Stochastic learning control

A stochastic learning control algorithm based on variable structure learning automaton (VSLA) [48, 49] in general is characterized by a 5-tuple,{α, β, p, τ, C} where α = {α1, α2, . . . , αr } is the set of r actions from which the automaton can choose any action at time n, denoted by αi (n), β = {0, 1} is the set of binary response (feedback) generated by an unknown random environment for the chosen action. β = 0 corresponds to a reward to the automaton for the chosen action while β = 1 corresponds to a penalty. p = { p1, p2, . . . , pn } contains the set of probabilities with which the corresponding actions are chosen. τ is the

136 ADAPTIVE AND RECONFIGURABLE LINK LAYER

stochastic iterative learning algorithm according to which the elements of the set p are updated over time. C = {c1, c2, . . . , cr } is the set of penalty probabilities conditioned on the chosen action, i.e. ci = Pr [β = 1 | αi ] that characterizes the unknown environment. It is reasonable to assume that arg min C is unique for a given random environment. The VSLA attempts to learn the optimal action (policy) that results in the minimum value in C. The VSLA can be characterized by the following equation:

4.4.2 Adaptive link layer protocol

The two-state Markov chain model (Gilbert–Elliot model) from Figure 4.18 is also used

in this section. The transmission energy ( t), mean number of retransmissions ( ¯ ) and the

E R packet error rate (Pep) for an ARQ scheme are related as [45]

i=1

Pep = PG 1 − (1 − PeG)L + PB 1 − (1 − PeB)L

In Equation (4.41) Et is the total transmission energy, P is the transmit power, C is the bit rate of the channel, PeG and PeB are the bit error rates in states G (good) and B (bad), respectively, L is the packet length in bits, R is the maximum number of retransmissions allowed, Pep is the packet error probability and, PG and PB are the steady state probabilities of G and B states. As seen from Equation (4.41), the total energy consumed is directly proportional to the mean number of retransmissions, indicating that considerable energy can be saved if the number of retransmissions is reduced significantly. Therefore, smart link layer protocols that recognize the wireless channel state and adaptively control the transmission/retransmission policy could result in significant energy savings.

In this section an adaptive link layer protocol is presented that adjusts itself over time to arrive at the optimal policy for a fixed but unknown finite state wireless channel model. The link layer protocol employs a VSLA with two actions in its action set: α1, transmit a packet; and α2, do not transmit a packet.

(1)If the transmitter sends a packet, it waits for a fixed time period to receive an

acknowledgement. If an ACK is received within this period then the action α1 is rewarded (β = 0); if not a time-out occurs and α1 is penalized (β = 1).

(2)Then, a reward–penalty learning algorithm, as discussed later in this section [see

Equation (4.42)], is used to update the action probabilities of the set p(n) =

{p1(n), p2(n)}.

(3)The next transmission decision is chosen according to the probability distribution p(n).

This process continues until the probability vector p(n) converges when the state of the channel is predicted accurately one time unit ahead. We assume that the reverse channel or the feedback channel is error free. The effect of an erroneous feedback channel and feedback delays are similar to those discussed in Section 4.1. It is also assumed that an ACK is generated for every packet transmitted. Depending on the needs of the situation, the feedback and updating can be also done after every few packets with some minor changes to the above algorithm.

4.4.2.1 Reward-penalty algorithm

When α1 is chosen then p1(n) and p2(n) are updated linearly depending on β(n); however, when α2 is chosen both p1(n) and p2(n) are left unchanged. This is because, when the link layer chooses not to transmit a packet, there will be no feedback from the receiver. This stochastic learning control algorithm that predicts the channel state and controls the retransmission policy defined as p (n + 1) = τ {α(n), β(n), p(n)} can be described as

p2(n + 1) = p2(n) + b(1 − p2(n) − B)

if α(n) = α2 p1(n + 1) = p1(n) p2(n + 1) = p2(n)

In Equation (4.42), a and b are reward and penalty parameters that control the speed and accuracy with which the VSLA predicts and tracks the time-varying wireless channel state. Parameters A and B control the probability with which the link layer can explore both actions even while deviating from the currently most probable action. They also determine the amount of exploration vs exploitation during learning.

4.4.2.2 Performance results

The simulation scenarios consists of two nodes, with one node acting as a transmitter while the other is a receiver. The channel between the two nodes is simulated as a two-state Markov model (Figure 4.18). With probability 1 packets are dropped in the B state. Various values for the packet loss rate in the G state were chosen to observe the performance. A transmission rate of 11 Mbps was assumed as it is typical in a present-day wireless network such as a wireless LAN. The packet size L was fixed at a constant 1000 bytes. No upper limit on the number of retransmissions was set. In each simulation the number of packets transmitted by the sending node to the receiving node was 5000 and the results were averaged. The parameters A = B = 0.02 was fixed throughout the simulations and a = b = 0.3 unless otherwise stated. If the link layer transmitted a packet then a timer was