Optimization of Adaptive Three-Mode GBN Scheme Control Parameters

808 R. VOJINOVIC, M. DAKOVIC, OPTIMIZATION OF ADAPTIVE THREE-MODE GBN SCHEME CONTROL PARAMETERS Optimization of Adaptive Three-Mode GBN Scheme Control Parameters Ranko VOJINOVIC 1, Milos DAKOVIC 2 1Faculty of Information Technology, Bulevar Sv. Petra Cetinjskog 22, 81000, Podgorica, Montenegro 2University of Montenegro, Faculty of Electrical Engineering, Dz. Vasingtona bb, 81000, Podgorica, Montenegro rankov[email protected], [email protected] Submitted December 30, 2016 / Accepted May 22, 2017 Abstract. An adaptive three-mode system based on Go-Back-N (GBN) protocol is analyzed within this paper. An ideal mode selection procedure based on a-priori known packet error probability is defined. When packet error probability is unknown the system state transition is controlled by several system parameters. A procedure for optimal parameters selection is proposed and tested on a simulated system. The procedure is based on minimization of mean square deviation of the system throughput from the ideal one. Keywords Go-Back-N, packet error probability, wireless communications, throughput, TS-ARQ scheme, optimization, control parameters 1. Introduction One of the main disadvantages of “Go-Back-N” (GBN) protocol is the fact that system throughput significantly decreases when packet error rate (PER) increases. In order to solve this problem, several adaptive models of GBN protocol are proposed. An adaptive GBN scheme that dynamically adapts to varying channel conditions is proposed in [1] and further developed in [2–4]. In [5], the adaptive threestate system (TS-ARQ) that adapts the dynamic condition of the channel has been analyzed. In [6], the exact analysis of the throughput for the three-mode GBN (TM-GBN) system, based on retransmission cycles mechanism, is proposed. Throughput performances of various GBN adaptive schemes have been analyzed in [7–9]. The TM-GBN technique is proposed in order to improve system performances in the high noise case. Adaptation to the channel is done by classifying channel conditions into three states. The first state, denoted by L, is the low disturbances state. The moderate disturbances state is denoted by H, and intensive disturbances case is denoted by V H. Formulated in this way, we get the three-state system. According to the current system state, the transmitter can apply the most appropriate procedure. In the Lstate, it follows standard GBN procedure. For the Hstate, the transmitter should switch to the multi-copy mode. Finally, for the V H state, the transmitter should continuously repeat packet until a positive acknowledgment is received. The receiver provides corresponding acknowledgment for the each frame received. In the Lmode, upon the receipt of αconsecutive NAKs, the transmitter switches to the H mode, where the packets are emitted by n-copy GBN procedure. If the transmitter receives βconsecutive ACKs in the Hmode, the transmitter goes back to the Lmode. If the transmitter receives γconsecutive NAKs in the Hmode, then the transmitter will switch to the V H mode, in which it follows the procedure of continuous emitting of the same packet. The transmitter goes back to the Hmode upon the receipt of δconsecutive positive acknowledgments. Channel state estimation and transmitter mode selection are based on the counting of positive and negative acknowledgments. These counters are compared with a given thresholds α,β, γand δin order to control the system and make decisions on the required system state transition. These parameters are essential for the adaptive system as the switching of the system state is controlled by them. In previous works, control parameters are obtained empirically. However, it is necessary to develop methods for determining these parameters in order to obtain optimal system. In this paper, we propose a technique for optimal control parameters selection. The rest of this paper is organized as follows. In Section 2, the throughput analysis of general single-mode GBN mechanism and TM-GBN system are presented. In Section 3, optimization of control parameters is considered and discussed. 2. Adaptive GBN Protocol Analysis Here we will give throughput analysis for single-mode adaptive and three-mode GBN protocol. The relations between the error probability and system throughput will be presented. 2.1 Single-Mode GBN Protocol Analysis We will define the general model of GBN protocol considering the simplified scenario in which the receiver sends DOI: 10.13164/re.2017.0808 SIGNALS RADIOENGINEERING, VOL. 26, NO. 3, SEPTEMBER 2017 809 only the positive acknowledgments (ACK), and the transmitter starts the packets retransmission after a timeout. Expiration of the time-out interval is equivalent to the reception of the negative acknowledgments (NAK) from the receiver. The transmitting station forms the packet, marks them with consecutive numbers and stores the packets in the transmit buffer. The transmitter sends the packets, without waiting for the ACK from the receiver. After the packet has been sent, transmitter activates the time control mechanism. If the positive acknowledgment is not received until the time-out, the ongoing transmission is interrupted. Then the unacknowledged packet and all the successive ones (even those with positive acknowledgment received) are being re-sent. If the ACK is received for the packet in the transmit buffer with the lowest number, this packet is discarded from the buffer, and packet transmission continues with the next packet. On the receiving side, upon the packet reception, the receiver performs error control. If the received packet is correctly received, the receiver sends positive acknowledgments for this packet. One of the main communication system performance measures is system throughput. Throughput is defined as a ratio of a number of successfully received packets and a total number of transmitted packets. The system throughput, in the single-copy GBN (SGBN) case, is SL=1−Pe 1+(N−1)Pe(1) where Peis packet error probability and Nis a standard value for GBN protocol. In the n-copy GBN case (nGBN) transmitter sends n copies of each packet. The transmission is successful if a positive acknowledgment is received for at least one copy. The system throughput in this case is SH=1−Pn e n+(N−1)Pn e .(2) The continuous GBN procedure (CGBN) assumes that the same packet is transmitted until the positive acknowledgment is received. The system throughput is SV=1−Pe 1+(N−1)(1−Pe).(3) Figure 1 presents throughput dependence of packet error probability for all considered single-mode protocols, with N=10 and n=2Figure 2 illustrates throughput vs. Pe, for single-mode protocols, with n=2and N=30. 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Fig. 1. System throughputs for n=2and N=10. Probabilities PHV and PLH are obtained as intersection of the SH curve with SVand SLcurves. 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Fig. 2. System throughputs for n=2,N=30: Probabilities PHV and PLH are obtained as intersection of the SH curve with SVand SLcurves. For each analyzed protocol we can identify range where it is the optimal protocol. Obviously for a very small probability of packet error SGBN protocol is optimal. The limit value of the packet error probability can be obtained by solving equation SL=SHfor unknown Pe. The smallest solution, denoted by PLH is an upper limit when the SGBN protocol is optimal. PLH can be obtained in a closed form for small n. For example: PLH =1 N,for n=2,(4) PLH =r1 4+2 N−1 2,for n=3.(5) For large nvalue of PLH can be obtained numerically. For Pehigher than PLH throughput obtained with nGBN protocol outperform SGBN case. In a similar way we can define upper limit for nGBN protocol by equating SHand SV and solving obtained equation for unknown limit PHV. For n=2the solution is PHV =1+√8N2−24N+17 4N−4.(6) 810 R. VOJINOVIC, M. DAKOVIC, OPTIMIZATION OF ADAPTIVE THREE-MODE GBN SCHEME CONTROL PARAMETERS For higher values of nthe solution can be found numerically. Now we have ranges for each protocol: 0≤Pe≤PLH =⇒SGBN protocol is optimal, PLH <Pe≤PHV =⇒nGBN protocol is optimal, PHV <Pe<1=⇒CGBN protocol is optimal. Limits PLH and PHV depend only on the system parameters Nand n. Presented results lead us to the conclusion that protocol choice highly depends on packet error probability. In the stationary channel case when Peis a-priori known (or could be estimated) single protocol can be used. Adaptive systems [10] are able to track changes in the environment and to adjust system parameters in order to achieve optimal performances. For nonstationary channels, an adaptive procedure for transmitting protocol selection is implemented. Having in mind that any adaptive system, where Pe is unknown, could not have better throughput than the system with optimally selected protocol, we can define optimal throughput Sopt as Sopt(Pe)=max{SL(Pe),SH(Pe),SV(Pe)}.(7) Optimal throughput is presented in Figs. 1 and 2 with thick line. This case is an ideal one and can be used as a reference for adaptive system parameters optimization. 2.2 Three-Mode GBN Protocol Analysis Let us review the basic foundations of the three-mode channel model, the concept which has been presented in details in [5]. TM-GBN model is given as scheme that uses three different methods of GBN protocols SGBN, nGBN, and CGBN. The transmitter sends the data packets to the receiver over the forward channel, and the receiver sends acknowledgments through the backward channel. In accordance with this model, transmitter’s operating modes are different: in a state Lwhere the packet error probability is low, the transmitter follows basic SGBN procedure; in a state Hcharacterized by higher packet error probability, the transmitter operates in an-copy mode; and in a state V H - where the packet error probability is very high, transmitter sends packet copies continuously until the first positive acknowledgment is received. Switching from mode Lto mode H, and from mode H to mode V H is managed by counting continuous NAKs for each packet and the switching from mode Hto mode L, and from mode V H to mode H, by counting continuous ACKs for each packet. The receiver provides ACK for each received packet including the copies in the n-copy mode. The packets have been emitted in one of three possible ways. In the L mode, the standard GBN procedure is followed. Upon the reception of αconsecutive NAKs, the transmitter switches to Hmode, where the packets are emitted by the nGBN procedure. If the transmitter receives βconsecutive ACKs in H mode, the transmitter returns to Lmode. If the transmitter receives γconsecutive NAKs, while it is in Hmode, the transmitter will switch to V H mode, in which it continuously emits the same packet. The transmitter returns to Hmode upon the reception of δconsecutive ACKs. Detailed analysis of TM-GBN system throughput is given in [6]. Here we will review final analysis results. The system throughput SGis given by 1 SG = CL SL + CH SH + CV SV(8) where SL,SHand SVare defined by (1), (2) and (3). According to [6], CL,CHand CVare calculated as CL= (1−Pα L)L L+H+V,(9) CH= (1−Pγ H)Pα LL+(1−Pγ+1 H)H L+H+V,(10) CV= Pα LPγ HL+Pγ+1 HH+V L+H+V(11) with L=(1−PH)β Pα L ,(12) H=1−(1−PH)β PH ,(13) V=1−(1−PV)δ−1 (1−PV)δ−1 Pγ H PV(14) and PL=Pe, PH=Pn e, PV=Pe. It is obvious that the system throughput depends on packet error probability Peand on system parameters N,n, α,β,γand δ. 3. Parameters Optimization In order to find optimal parameters, we should define optimization criterion. The optimization criterion should be based on the system throughput SG. Since it depends on channel conditions (packet error rate Pe) averaging (integration) over all possible values of Peshould be used. The system optimization problem can be formulated as arg min n,N,α,β,γ,δ J(n,N, α, β, γ, δ).(15) Having in mind that in ideal case system throughput should be Sopt defined by (7), we can define cost function (optimization criterion) Jas mean squared deviation of the system throughput SGfrom the optimal throughput Sopt J(n,N, α, β, γ, δ)=Z1 0Sopt(Pe)−SG(Pe)2dPe.(16) RADIOENGINEERING, VOL. 26, NO. 3, SEPTEMBER 2017 811 Note that integration limits in (16) could be reduced to Pmin,Pmax if we expect that the packet error probability is within the range Pmin ≤Pe≤Pmax. Another approach could be that we optimize system for a given set of Merror probabilities {P1,P2, . . . , PM}. In this case, the optimization criterion Jcould be defined as J(n,N, α, β, γ, δ)= M X k=1 (Sopt(Pk)−SG(Pk))2.(17) In all considered cases the function that should be minimized depends on integer parameters. Integer values of the parameters imply that classical minimization methods could not be directly applied. When the minimization domain is finite, the direct search over all possible parameters combinations is a method that will surely lead us to the optimal solution. However, if the number of the minimization parameters is high, and when each parameter can achieve values from a large finite set, this approach could be inefficient. Of course, the optimization could be performed with other optimization methods as well [11], [12]. In the sequel, we will consider optimization with fixed Nand nvalues. The ranges for remaining parameters are determined heuristically as 1≤α≤5, 1≤β≤100, 1≤γ≤40, 1≤δ≤30. In this case, the minimization implies calculation of J(n,N, α, β, γ, δ)for a given Nand nand for each combination of parameters α,β,γ, and δ. The total number of combinations is 5×100×40×30 =600,000. The minimum of Jis found and corresponding optimal parameters (within considered ranges) are obtained. The optimization results for N=10 and n=2are given in Fig. 3 (upper subplot). Obtained throughput is presented by thin black line, and theoretically optimal throughput with a thick gray line. We can see that for selected parameters actual throughput is very close to the ideal one. Deviation from the ideal throughput, used for criterion Jcalculation, is presented in the lower subplot. The same procedure is repeated for N=30 and n=2case. The results are presented in Fig. 4. From Figs. 3 and 4 we can conclude that adaptive system is very close to the ideal one. The highest deviation appears around Pe=PHL i.e. when the system switches from standard GBN protocol to nGBN protocol and vice versa. Large values of βimply that when αconsecutive errors are detected in the Lmode (standard GBN protocol) and system switches to Hmode (nGBN protocol) the system will go back to Lmode very slowly (after βconsecutive positive acknowledgments). 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.01 0.02 0.03 0.04 Fig. 3. Optimization of the system parameters for n=2, N=10. Throughput achieved through parameters optimization is presented with a thin black line. The thick gray line is theoretically optimal throughput for considered case. Deviation from the optimal throughput is presented in the lower subplot. 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.05 0.1 0.15 Fig. 4. Optimization of the system parameters for n=2, N=30. Throughput achieved through parameters optimization is presented with a thin black line. The thick gray line is theoretically optimal throughput for considered case. Deviation from the optimal throughput is presented in the lower subplot. 812 R. VOJINOVIC, M. DAKOVIC, OPTIMIZATION OF ADAPTIVE THREE-MODE GBN SCHEME CONTROL PARAMETERS Note that the parameters optimization procedure should be performed once, so the high computational load caused by direct search procedure does not degrade system operating performances. 4. Conclusion Three-mode GBN protocol is analyzed. The ideal case when we can select the optimal mode based on the a-priori known packet error probability is studied. This case is used in order to define optimization criterion. The procedure for adaptive system parameters optimization is derived. The optimization is performed and optimal system throughput is obtained for two system scenarios. The presented results show that parameters choice in three-mode GBN system is very important. The optimization procedure is based on direct search within predefined parameter ranges. A large number of parameters combinations is not preferred, but when parameters take integer values this technique is highly reliable. It guarantees that our optimization procedure will not result in eventual local minimum and suboptimal parameters combination within considered ranges. Acknowledgments This research is partially supported by “New ICT Compressive Sensing Based Trends Applied to: Multimedia, Biomedicine and Communications (CS-ICT)” project (Montenegro Ministry of Science, Grant No. 01-1002). References [1] YAO, Y. D. An effective go-back-N ARQ scheme for variable-errorrate channels. IEEE Transactions on Communications, 1995, vol. 43, no. 1, p. 20–23. DOI: 10.1109/26.385946 [2] ANNAMALAI, A., BHARGAVA, V. K., LU. W. S. On adaptive goback-N ARQ protocol for variable-error rate channels. IEEE Transactions on Communications, 1998, vol. 46, no. 11, p. 1405–1408. DOI: 10.1109/26.729379 [3] CHAKRABORTY, S. S., LIINAHARJA, M. Exact analysis of adaptive go-back-N ARQ scheme. Electronics Letters, 1999, vol. 35, no.5, p. 379–380. DOI: 10.1049/el:19990165 [4] HUANG, S., LIU, J., YAN, Y., et al. Queuing analysis of cooperative GBN-ARQ in wireless networks with peers contending for a common helper. AEU-International Journal of Electronics and Communications, 2014, vol. 68, no. 5, p. 429–436. DOI: 10.1016/j.aeue.2013.11.006 [5] VOJINOVIĆ, R., PETROVIĆ, Z. A novel three-state ARQ scheme for variable error-rate channels. AEU-International Journal of Electronics and Communications, 2002, vol. 56, no. 6, p. 389–395. DOI: 10.1078/1434-8411-54100127 [6] VOJINOVIĆ, R., PETROVIĆ, G., PETROVIĆ, Z. The analysis of the adaptive three-mode ARQ GBN scheme using retransmission cycles mechanism. AEU-International Journal of Electronics and Communications, 2006, vol. 60, no. 2, p. 190–198. DOI: 10.1016/j.aeue.2005.03.002 [7] ALEXOVÁ, P., KOSUT, P., POLEC, J., et al. A comparison of selected GBN ARQ schemes for variable-error-rate channel using QAM. Radioengineering, 2002, vol. 11, no. 3, p. 43–47. ISSN: 1805-9600 [8] ZHOU, Y., LI, S., ZHOU, Y. Delay analysis of three ARQ protocols in Geom/G/1 Queue Model. Journal of Theoretical and Applied Information Technology, 2012, vol. 42, no. 2, p. 292–295. [9] MAKKI, B., ERIKSSON, T. On the performance of MIMO-ARQ systems with channel state information at the receiver. IEEE Transactions on Communications, 2014, vol. 62, no. 5, p. 1588–1603. DOI: 10.1109/TCOMM.2014.033014.130223 [10] STANKOVIĆ, L. Digital Signal Processing. 1st ed. CreateSpace Amazon, 2015. ISBN: 978-1514179987 [11] KORTE, B., VYGEN, J. Combinatorial Optimization. Heidelberg: Springer, 2012. ISBN: 978-3540718437 [12] AHUJA, R. K., ERGUN, Ö., ORLIN, J. B., et al. A survey of very large-scale neighborhood search techniques. Discrete Applied Mathematics, 2002, vol. 123, no. 1:3, p. 75–102. DOI: 10.1016/S0166-218X(01)00338-9 About the Authors . . . Ranko VOJINOVIĆ received the B.Sc. degree in Electrical Engineering from the University of Montenegro in 1982, and the M.Sc. and Ph.D. degrees from the University of Belgrade in 1992 and 2003, respectively. Since 1982 he has worked in a Department of Telecommunications in Montenegro Police Directorate. From 1996 to 2006, he was with the Maritime faculty at the University of Montenegro. In 2007 he joined the Faculty of Information Technologies of the University Mediterranean (Montenegro), where he is currently an Assistant Professor, teaching several courses in computer networks. His main research interests are in telecommunications and modeling and analysis of network protocols. Miloš DAKOVIĆ was born in 1970 in Nikšić, Montenegro. He received a B.S. in 1996, an M.S. in 2001, and a Ph.D. in 2005, all in electrical engineering from the University of Montenegro. He is a professor at the University of Montenegro. His research interests are in signal processing, time-frequency signal analysis, compressive sensing, and radar signal processing. He is a member of the Time-Frequency Signal Analysis Group (www.tfsa.ac.me) at the University of Montenegro, where he is involved in several research projects.