IRSA Transmission Optimization via Online Learning
Laura Toni Pascal Frossard
cs.IT math.IT



DASHdynamic adaptive streaming over HTTP  
CDNcontent delivery network  
BPbelief-propagation  
CDFcumulative density function
PDFprobability density function  
QoEquality of experience   
ILPinteger linear programming   
CRDSAcontention resolution diversity slotted ALOHA
SAslotted ALOHA
BSbase station
RDrate-distortion
MACmedium access control
ICinterference cancellation
IRSAirregular repetition slotted ALOHA
EEPequal error protection
UEPunequal error protection
SICsuccessive interference cancellation
BNburst node
SNslot node 
MABmulti-arm bandit









IRSA Transmission Optimization via Online Learning
    
Laura Toni 
and Pascal Frossard 
L. Toni is with the Electrical and Electronic Department, University College London (UCL), London WC1E 7JE, U.K. (e-mail:  ). P. Frossard is with École Polytechnique Fédérale de Lausanne (EPFL), Signal Processing Laboratory - LTS4, CH-1015 Lausanne, Switzerland. (e-mail:  


    Received: date / Accepted: date
=========================================================================================================================================================================================================================================================================================================================

empty








 In this work, we   propose a new learning framework  for optimising transmission strategies   when irregular repetition slotted ALOHA (IRSA) MAC protocol is considered.
  We cast the online optimisation of the MAC protocol design as a multi-arm bandit problem  that exploits the IRSA structure in the learning framework.   Our learning algorithm quickly learns the optimal transmission strategy, leading to higher rate of successfully received packets with respect to baseline transmission optimizations. 


 slotted ALOHA,  successive interference cancellation, multi-arm bandit problem, online optimisation strategies.  


 


§ INTRODUCTION

 
 Random  random SA  with    SIC   <cit.> has been widely considered as an effective  MAC strategy, for its good performance despite the distributed protocol.

In particular, let us   consider a  system  where L sources send  information to a central BS, through an  IRSA algorithm <cit.>, which is a SA protocol with SIC. The time axis is discretized in MAC frames, each of those composed  of  M time slots.    Visual sensor networks, in which each source sends periodic data to a central BS, represent one possible scenario[  Random MAC strategies offer scalability, and adaptability to possibly varying L, like in the scenario considered in this paper.].
 Each source sends K source packets per MAC frame and   each source packet is sent  in multiple replicas   within the MAC frame.    Each replica is transmitted within one time slot and replicas sent from the same source are allocated to different slots, which are uniformly selected at random among the M available slots in a MAC frame. The replication rate l is selected  for each source packet at random according to a transmission probability   Λ(x) = ∑_l=0^l_maxΛ_lx^l, where Λ_l is the probability that a source transmits l replicas of a given source packet within the MAC frame, and l_max is the maximum replication rate. If a transmission slot is selected by only one source (singleton slot), the corresponding message is correctly received. When multiple sources select the same time slot for transmission, a packet collision happens.  The BS   implements the SIC algorithm to recover the collided messages. Finally, the BS defines the transmission strategy characterised by the source rate K and the transmission probability  Λ(x)  in IRSA[ The model can also be extended to the case in which each source sends only one source packet (K=1) and where the BS defines both  Λ(x) and L.].   



 In the example provided  in   Fig. <ref>,   the message sent by user 2 and user 3 are not decodable due to collisions in slot 3 and slot 5. 
 However, thanks to  SIC techniques, the   collision  might be resolved. 

A packet   in a collision-free (singleton) slot is successfully received and decoded, revealing  the slots containing the other replicas.  Their removal via SIC  may turn some of the collided slots into singletons, enabling the recovery of new packets.  This can be seen as message-passing in the bipartite graph Fig, <ref>,    opening the possibility of applying  theory of  rateless codes   to IRSA schemes  to analyze both asymptotic  <cit.> and finite-length performance <cit.>.  




 
   


In this paper, we are interested in  the transmission strategy optimization performed by the BS.   Performance bounds in the asymptotic regime can be easily evaluated and can act as guidelines for a  proper selection of 
the transmission strategy. The accuracy of such guidelines however reduces in non-asymptotic settings.  Exact performance analysis has been recently derived for the finite block length case; unfortunately it is    computationally too expensive for medium block sizes in practical implementations. 
 Frameless ALOHA protocols can compensate for inaccurate performance evaluation, since the MAC frame is not set a priori. New slots are added until a sufficiently high fraction of packets has been decoded. However, this comes at the price of having changing MAC frame size over time.  

 Rather than analytically deriving the IRSA system performance,     we propose to estimate directly the optimal design of IRSA algorithms by online learning.    

 We cast the network optimisation problem as a MAB problem <cit.>, i.e., sequential decision strategy in which a decision maker needs to select the optimal “arm". The BS is the decision maker who  measures the overall performance (reward) of each arm (transmission strategy) and learns the optimal network design (optimal actions) by trial and error.  To improve the learning performance, we design a specific IRSA-based MAB algorithm where we infer the IRSA structure into the learning problem in order to improve on the low convergence of classical MAB solutions. 
Simulation results show that our learning algorithm reaches higher mean reward   with respect to  transmission strategies designed based on i) classical bandit problems  ii) analytical performance studies. 






















 
 


§ ONLINE IRSA OPTIMIZATION

 


 §.§ Problem Formulation

The performance of the system is   measured by an utility function U(r) that is a non-decreasing function of the number of per-source decoded packets r≤ K at the BS. In this work, we consider a generic utility function of the form 

    U(r)  = w log(r+1)

where w is a scaling factor.  The above utility function is typical in multimedia transmission, (e.g., visual sensor networks) and w reflects different priorities among different sources. However, the proposed learning strategy applies to any other increasing utility function. 


In the above framework, optimising the system performance consists in finding the best transmission strategy (i.e.,   Λ(x)^⋆,  K^⋆), such that the overall mean utility function per source is maximised. Formally, the optimisation problem is 

    (Λ(x)^⋆, K^⋆):  max_{Λ(x),K}    ∑_r=0^K w log(r+1) P(r| Λ, K ; M,L) 
    s.t.    L K   ≤ M

where P(r| Λ, K ; M,N) is the probability of decoding r packets in the scenario with L sources transmitting K packets over M time slots. The network traffic L K/M is finally constrained to be lower than 1, which corresponds to the stability limit of the SA MAC protocol <cit.>.  







 §.§ MAB problem formulation



We now cast the above optimisation as a  MAB problem. 
 In our case, the BS is the decision maker, which can periodically adjust the transmission strategy. Let t denote  the decision opportunity timestamp[ We consider a decision every MAC frame but less frequent decisions can also be considered.]. Between two consecutive decision opportunities, the BS observes the overall system performance (i.e., the number of  correctly decoded packets) that is the instantaneous reward. Based on this observation, it selects the next action, which is then communicated to all sources.   The overall goal is to  minimize the experienced regret, i.e., the loss due to the fact that the globally optimal policy is not achieved all the times. 

Let a∈𝒜 be one possible transmission strategy, with 𝒜 being the set of all possible strategies (possible arms). In our IRSA problem, an arm a is associated to the transmission strategy defined by {Λ_a(x)=[Λ_1^(a), Λ_2^(a), …, Λ_l_max^(a)], K_a}. Let further μ_a=∑_r=0^K w log(r+1) P(r| Λ_a(x), K_a ; M,L) be the mean reward of the arm a.    At time t, the learner selects the action a and experiences an instant payoff X_a,t, which is a realization of a random variable with unknown distribution  F_a and  unknown mean value μ_a. 

 When the performance value is known, P(r| Λ_a(x), K_a ; M,L) could be derived and (2) could be solved numerically. Conversely, if there is no precise value (or  no  low-complexity evaluation) of the performance evaluation,   we can learn P(r| Λ_a(x), K_a ; M,L) from experience, i.e., by trial-and-error.  
 During the learning process  suboptimal actions might be selected, leading to a cumulative regret after t decisions that is  

R(t)= t μ^⋆ - ∑_i=1^t X_α_i, i

 with α_i  being the arm selected at the i^th decision opportunity and μ^⋆ the mean reward of the optimal arm. 
 

 The classical algorithm to solve MAB problems is the upper confidence bound (UCB) algorithm <cit.> (see Alg. 1). The UCB solves MABs using the optimism in face of uncertainty principles in order to find the best tradeoff between exploration and exploitation.  Rather than selecting the action with the highest estimated reward μ̂_a,t, the UCB selects the reward with the highest bandit index    b_a,t = μ̂_a,t + β√(2 log t  /  N_a,t),   
 

 
with N_a,t being the number of times the arm a has been selected up to t, and β a multiplicative factor.  The  second term in the bandit index   represents   an upper confidence bound  that reflects the uncertainty on  the estimates of μ̂_a,t   
 







   Asymptotically, the  UCB algorithm  minimizes the regret  R(t) and  therefore it maximizes the mean reward  ∑_i=1^t X_α_i, i. 
Let define X_a,t= (1/L) ∑_l=1^L wlog(r_a,t^(l)+1), with r_a,t^(k) being the number of decoded packets for source k with action a taken at time t. This means that asymptotically the  UCB optimizes the expected utility function  for each source, i.e.,  ∑_r=0^K w log(r+1) P(r| Λ, K ; M,L). Defining the set of actions as 𝒜:{a=(Λ_a(x),K_a) | L K_a ≤ M} the   UCB algorithm asymptotically optimises the    problem in (<ref>). 




 §.§ Proposed online learning algorithm


Classical UCB methods can be improved if prior information is inferred in the learning process. This is the reason why we propose an online learning solution based on a Bayesian UCB (or Bayes-UCB) algorithm  <cit.> that allows us to infer information about the reward distribution. We represent the uncertainty about the system in terms of variance of the process rather than a confidence bound of the estimate as in classical UCB methods. Thus, the learning process consists in selecting at each time instant t the arm α_t that maximises the following function 

α_t =  max_a{μ̂_a,t + βσ_a,t},  
 
 with  μ̂_a,t and σ_a,t^2 being respectively the  mean and variance of the reward of action a estimated at the decision opportunity t, and β being   a multiplicative factor. 
 The Bayes-UCB algorithm thus automatically builds confidence intervals based on a Kullback-Leibler divergence, which best fits the geometry of the problem (see Appendix).  
 
The Bayes-UCB algorithm initiates a mean and variance per arm.  As there exists no exact information about the mean and the variance of the process in our IRSA system, we derive estimates from the asymptotic setting <cit.>,   and  under the assumption  that each source independently assigns packets to transmission slots. In  practice, the independency holds only among packets sent from different sources, therefore   less collisions are actually experienced than the number predicted from the theory.  The derived estimate is then refined by the Bayes-UCB algorithm at each decision opportunity.   
 
 

   For the arm a with transmission strategy ( Λ_a(x), K_a), we evaluate P_e(Λ_a) as the probability for a packet to be lost after   SIC.  This is derived from the asymptotic analysis  in   <cit.>, exploiting the     SIC convergence analysis  and the probability of a burst node  edge being not resolved at an iteration, <cit.>.   Due to  the independency between sources, 
   the probability for one source to correctly decode r source packets is 

    P(r| Λ_a, K_a ; M,L) = K_ar P_e(Λ_a)^r[1-P_e(Λ_a)]^K_a-r .

We then note that the mean reward of the utility given in (<ref>) is given by the logarithm of a binomial random variable. Therefore, by expanding the logarithm operator as a Taylor series in x=K_a  P_e(Λ_a) and computing the binomial sum term by term, the mean reward and the reward variance of action a can be estimated with 

    μ_a = log(K_a P_e(Λ_a) +1 ),   
    
    
    σ^2_a =  K_a  P_e(Λ_a) (1- P_e(Λ_a)) /( P_e(Λ_a) K_a+1)^2

The initial estimates μ̂_a,0 and σ^2_a,0 are thus derived from the above equations, and the learning algorithms proceeds as described in   Alg. <ref>.
 


 §.§   Computational Complexity 

Our proposed learning strategy is a low-complexity algorithm compared to transmission strategies designed based on finite-length performance analysis.  At each decision opportunity, the only operations that need to be computed are i) the selection of arms (which is a maximization of a known vector), ii) the update of the mean reward only for the selected arm (a weighted sum).  The initialization process requires the evaluation of 
(<ref>) for all possible arms. The cardinality of the arm set depends on l_max and the maximum value of K, but not on the MAC frame, neither on the number of sources. Moreover, this initialization step can be further simplified by approximating the packet error probability by a binary condition given by <cit.>. 

The exact finite length analysis <cit.> has in contrary a complexity that scales exponentially.   The combinatorial approach in <cit.> spans the all possible combinations of transmission realizations with  a complexity 𝒪(|𝒩|   l_max^LK), with  
 |𝒩| being the cardinality of the set 𝒩, which is the set of possible edge-realizations in the bipartite graph. This is given by    |𝒩| ≤𝒞̂+M-1t, with 𝒞̂=∑_n=0^LK-2LKM.  A computational complexity that scales exponentially with the MAC frames and number of users is achieved also in <cit.>, where the system performance evaluation is derived based on a finite Markov state machine and each state is characterized by the size of the cloud and ripples (with different degrees).  




§ SIMULATION RESULTS
 
 



We now provide simulation results that show the performance of the proposed learning strategies with respect to (i) classical UCB algorithm, and (ii) MAC protocol optimisation based on asymptotic strategies.  Results are provided in terms of both regret (R(t)= t μ^⋆ - ∑_i=1^t X_α_i, i) and experienced reward.  Note that the finite-length analysis   leads to the optimal decision strategy at each time step, meaning a null cumulative regret. Therefore, the regret shows the tradeoff between complexity (in evaluating the finite length analysis) and performance approximation   (due to the learning process).   
The proposed algorithm (labeled “Proposed”) is compared with the classical UCB algorithm, both with β=1. We also compare to a baseline solution (denoted “Asymptotic") where the optimal transmission strategy is not learned but rather computed by assuming an asymptotic behavior of the system  (i.e., very large MAC frame duration). Namely, P_e(Λ_a) in (<ref>) is evaluated from <cit.> and  the optimisation problem in (<ref>) is   solved numerically.  
Finally, we also consider a learning algorithm (labeled as “Proposed (β=0)") that does not take into account the confidence bound of the estimation. Namely, we consider our proposed algorithm with β=0, which actually corresponds to the UCB algorithm with β=0.

We first consider the case in which the transmission probability Λ(x) is fixed and the actions correspond to different number of packets per source K. Fig. <ref> provides the cumulative regret for the scenario with 300 time slots per MAC frame, 20 sources and  Λ(x)=0.75x^2+0.25x^3. The proposed learning solution (IRSA Bayes-UCB) generally outperforms all the other learning strategies. Finally, in this specific setting, the optimisation based on the asymptotic theoretical performance achieves good performance, even if it performs worse than our proposed learning strategy. Its performance however degrades in other settings as shown next.  

























In Fig. <ref>, the cumulative regret is provided when  Λ(x) and K are jointly optimised in the scenario of 20 sources and 300 time slots.   The candidates Λ(x)  are defined as  Λ(x)=a_1x^2+a_2x^3+a_3x^8, with the coefficients a_i ranging from 0 to 1, i.e., a_i∈[0:0.25:1], i=1,2,3. The candidate values of K range from 1 to ⌊ M/L⌋. 
Moreover, note that the gain achieved by the proposed method (IRSA Bayes-UCB) with respect to the UCB  algorithm has increased compared to the previous setting. This is due to the fact that the action space in this scenario has increased, leading to a slower learning curve and therefore to a higher gain in exploiting prior information while learning, as implemented in our algorithm.   It is worth mentioning that the “Proposed (β=0)" baseline performs very closely to the proposed learning. This is due to the small randomness of the reward for all arms beyond the traffic threshold value G^⋆, as explained in the Appendix. However, the randomness in the remaining arms makes the “Proposed (β=0)" worse than our IRSA Bayes-UCB algorithm. 
Finally, we provide the mean reward experienced over time in Fig. <ref>. The reward per instant (averaged over 100 runs) confirms the gain of the proposed learning strategy with respect to the baseline methods. 



§ CONCLUSIONS


We have proposed a learning framework for designing optimised IRSA transmission strategies. We have casted the optimal resource allocation and transmission rate optimisation as a multi-arm bandit (MAB) problem. We have then implemented a specific MAB algorithm that is able to exploit the initial knowledge about IRSA schemes in the form of asymptotic theoretical performance. This allows us to infer the structure of IRSA in MAB problems and improve the learning efficiency of the algorithm. Simulation results have validated our theoretical analysis and demonstrated the gain of the proposed learning strategy in all tested settings.
 
  
  


§ APPENDIX 
 SUBOPTIMALITY OF UCB
  The key intuition of the UCB algorithm is the following. At time t, the estimated payoff for arm a is μ̂_a,t and it   differs from the estimated one of at most U  (i.e., |μ̂_a,t -  μ_a| ≤ U) with probability p  given by <cit.>

p ≤ e^-2N_a,t U^2.

Imposing a probability p decreasing with time (e.g., p=t^-4) 
leads to U_max= √(2log t/ N_t,a). To ensure  that the learner selects the optimal action as t→∞, the estimated  reward μ̂_a,t is added to the confidence bound U_max, which leads to Algorithm 1 in Sec. <ref>.  However, arms with a traffic lower than  the threshold G^⋆ will experience an almost deterministic payoff. 
Denoting the network traffic as  G=L K/M,   for G<G^⋆ packets are received with probability almost 1, while for G>G^⋆ the probability of correctly receiving the packets   collapses to 0. This   waterfall effect  is typical for IRSA  <cit.>.  This means that   |μ̂_a,t - μ_a| ≤ϵ with probability almost 1, for small ϵ and t. Therefore, the confidence bound actually differs from different arms. For this reason, the UCB results in a suboptimal algorithm. Conversely, the Bayesian method allows us to infer this heterogeneity in the uncertainty of the arms, by imposing different variance values or the reward for different arms. 



 
IEEEtran

  























































