Abstract:
A rate adaptation method comprises the steps of: updating the probability density function of the SNR of a transmitted signal according to the receiving status of the transmitted signal and the probability density function before update; and updating the transmission rate of the transmitted signal according the updated probability density function.

Description:
BACKGROUND OF THE INVENTION 
       [0001]    1. Field of the Invention 
         [0002]    The present invention relates to an application for a communication system, and more particularly, to a rate adaptation method for a communication system. 
         [0003]    2. Description of the Related Art 
         [0004]    Communication systems, especially wireless communication systems, operate in a transmission environment that is constantly varying due to a multitude of factors, such as weather, transmission distance, velocity of transmitter or receiver, and noise. Therefore, the initial transmission rate of a communication system may not be suited for the transmission environment at a later time. If a higher transmission rate is acceptable for the varied transmission environment, then the communication system wastes available transmission resources. On the other hand, if the original transmission rate is not acceptable for the varied transmission environment, then the transmission throughput will drop tremendously. Therefore, there is a need for a communication system to adjust the transmission rate according to the varying transmission environment. 
         [0005]    Most conventional rate adaptation methods update the transmission rate based on a transmitted probe signal or the signal quality of the received signal at the receiver within a fixed period. Auto rate fallback (ARF) and adaptive ARF (AARF) algorithms transmit probe packets to determine whether a higher transmission rate is achievable, and lower the transmission rate if transmission failure occurs successively. A sample rate algorithm transmits probe packets of different modulations and transmission rates periodically, and determines a transmission rate based on the receiving status of the transmitted probe packets. However, the aforementioned conventional rate adaptation methods all require additional probe packets such that the transmission throughput is reduced, and thus are not practical. 
         [0006]    Onoe algorithm, adaptive multi-rate retry (AMRR) algorithm, Madiff algorithm and robust rate adaptation algorithm (RRAA) are examples of rate adaptation methods. Onoe algorithm raises the transmission rate when the packet error rate is below 10% a successive number of times, and lowers the transmission rate when the average packet retry rate is greater than 1. AMRR algorithm and Madiff algorithm adopt the thresholds of two packet correct rates to determine whether to raise or lower the transmission rate. RRAA algorithm determines transmission rate based on the ACK signals of transmitted signals and the packet correct rate. However, the aforementioned conventional rate adaptation methods all require waiting or measuring the transmission quality for a period of time. Madiff algorithm, AMRR algorithm and RRAA algorithm, for example, all require at least ten packets for the determination of transmission rate. Therefore, these rate adaptation methods converge too slowly. 
         [0007]    In view of the disadvantages of the conventional rate adaptation methods, there is a need to design a rate adaptation method which not only would not reduce the transmission throughput, but also converges quickly to the optimum transmission rate. 
       SUMMARY OF THE INVENTION 
       [0008]    The embodiments of the present invention disclose a rate adaptation method for a communication system. The rate adaptation method updates the probability density function of the signal to noise ratio of a transmission signal as soon as an ACK signal or a NACK signal is received, and updates the transmission rate of the transmission signal according to the updated probability density function. Therefore, compared to conventional rate adaptation methods, the rate adaptation method in the embodiments of the present invention is more accurate, converges more quickly and the transmission throughput is not affected. 
         [0009]    The rate adaptation method for communication systems according to one embodiment of the present invention comprises the steps of: updating a probability density function of the signal to noise ratio of a transmission signal according to the probability density function and the receiving status of the transmission signal; and updating the transmission rate of the transmission signal according to the updated probability density function. 
         [0010]    The rate adaptation method for communication systems according to another embodiment of the present invention comprises the steps of: an initial step for initializing a probability density function of the signal to noise ratio of a transmission signal; a transmission rate update step for updating a transmission rate; and a probability density function update step for updating the probability density function. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0011]    The objectives and advantages of the present invention will become apparent upon reading the following description and upon referring to the accompanying drawings of which: 
           [0012]      FIG. 1  shows the flow chart of a rate adaptation method according to one embodiment of the present invention; 
           [0013]      FIGS. 2A and 2B  show the initial probability density functions of transmission signals according to one embodiment of the present invention; 
           [0014]      FIG. 3  shows the probability distribution function for receiving ACK signals under different transmission rates according to one embodiment of the present invention; 
           [0015]      FIG. 4  shows the probability distribution function for receiving NACK signals under different transmission rates according to one embodiment of the present invention; 
           [0016]      FIGS. 5A to 5D  show the simulation results according to the rate adaptation method of one embodiment of the present invention; 
           [0017]      FIG. 6  shows the flow chart of a method for determining transmission rate according to the probability density function of one embodiment of the present invention; 
           [0018]      FIG. 7  shows the flow chart of a method for determining transmission rate according to the probability density function of another embodiment of the present invention; 
           [0019]      FIG. 8  shows the flow chart of a method for determining transmission rate according to the probability density function of yet another embodiment of the present invention; 
           [0020]      FIG. 9  shows the flow chart of a method for determining transmission rate according to the probability density function of yet another embodiment of the present invention; and 
           [0021]      FIG. 10  shows the flow chart of a method for determining transmission rate according to the probability density function of yet another embodiment of the present invention. 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       [0022]      FIG. 1  shows the flow chart of a rate adaptation method according to one embodiment of the present invention. In step  101 , the probability density function (PDF) of the signal to noise ratio (SNR) of a transmission signal is initialized, and step  102  is executed. In step  102 , the transmission rate of the transmission signal is determined according to the PDF, and step  103  is executed. In step  103 , the PDF is updated according to the ACK signal, the NACK signal and the PDF of the transmission signal, and step  102  is executed. 
         [0023]    Given the received signal strength indication (RSSI), the transmission rate of transmitted packets and the corresponding ACK signals and NACK signals, the PDF of the SNR of a communication system is defined as: 
         [0000]    
       
         
           
             
               
                 p 
                  
                 
                   ( 
                   
                     
                       
                         S 
                          
                         
                             
                         
                          
                         N 
                          
                         
                             
                         
                          
                         R 
                       
                        
                       
                         R 
                          
                         
                             
                         
                          
                         S 
                          
                         
                             
                         
                          
                         S 
                          
                         
                             
                         
                          
                         I 
                       
                     
                     , 
                     ACKs 
                     , 
                     MCSs 
                   
                   ) 
                 
               
               = 
               
                 
                   
                     p 
                      
                     
                       ( 
                       
                         
                           S 
                            
                           
                               
                           
                            
                           N 
                            
                           
                               
                           
                            
                           R 
                         
                          
                         
                           R 
                            
                           
                               
                           
                            
                           S 
                            
                           
                               
                           
                            
                           S 
                            
                           
                               
                           
                            
                           I 
                         
                       
                       ) 
                     
                   
                    
                   
                     
                       ∏ 
                       
                         i 
                         = 
                         0 
                       
                       N 
                     
                      
                     
                       p 
                        
                       
                         ( 
                         
                           
                             
                               S 
                                
                               
                                   
                               
                                
                               N 
                                
                               
                                   
                               
                                
                               R 
                             
                              
                             ACKi 
                           
                           , 
                           MCSi 
                         
                         ) 
                       
                     
                   
                 
                 
                   
                     p 
                      
                     
                       ( 
                       
                         S 
                          
                         
                             
                         
                          
                         N 
                          
                         
                             
                         
                          
                         R 
                       
                       ) 
                     
                   
                   
                     N 
                     + 
                     1 
                   
                 
               
             
             , 
           
         
       
     
         [0000]    wherein MCS is the transmission rate and N is the number of transmitted packets. According to conditional probability formula: 
         [0000]    
       
         
           
             
               p 
                
               
                 ( 
                 
                   
                     
                       S 
                        
                       
                           
                       
                        
                       N 
                        
                       
                           
                       
                        
                       R 
                     
                      
                     ACK 
                   
                   , 
                   MCS 
                 
                 ) 
               
             
             = 
             
               
                 
                   
                     p 
                      
                     
                       ( 
                       
                         
                           ACK 
                            
                           MCS 
                         
                         , 
                         
                           S 
                            
                           
                               
                           
                            
                           N 
                            
                           
                               
                           
                            
                           R 
                         
                       
                       ) 
                     
                   
                    
                   
                     p 
                      
                     
                       ( 
                       
                         S 
                          
                         
                             
                         
                          
                         N 
                          
                         
                             
                         
                          
                         R 
                       
                       ) 
                     
                   
                 
                 
                   p 
                    
                   
                     ( 
                     
                       ACK 
                        
                       MCS 
                     
                     ) 
                   
                 
               
               . 
             
           
         
       
     
         [0000]    Substituting the conditional probability formula into the PDF, the following function is obtained: 
         [0000]    
       
         
           
             
               
                 p 
                  
                 
                   ( 
                   
                     
                       
                         S 
                          
                         
                             
                         
                          
                         N 
                          
                         
                             
                         
                          
                         R 
                       
                        
                       
                         R 
                          
                         
                             
                         
                          
                         S 
                          
                         
                             
                         
                          
                         S 
                          
                         
                             
                         
                          
                         I 
                       
                     
                     , 
                     ACKs 
                     , 
                     MCSs 
                   
                   ) 
                 
               
               = 
               
                 
                   p 
                    
                   
                     ( 
                     
                       
                         S 
                          
                         
                             
                         
                          
                         N 
                          
                         
                             
                         
                          
                         R 
                       
                        
                       
                         R 
                          
                         
                             
                         
                          
                         S 
                          
                         
                             
                         
                          
                         S 
                          
                         
                             
                         
                          
                         I 
                       
                     
                     ) 
                   
                 
                  
                 
                   
                     ∏ 
                     
                       i 
                       = 
                       0 
                     
                     N 
                   
                    
                   
                     
                       p 
                        
                       
                         ( 
                         
                           
                             ACKi 
                              
                             MCSi 
                           
                           , 
                           
                             S 
                              
                             
                                 
                             
                              
                             N 
                              
                             
                                 
                             
                              
                             R 
                           
                         
                         ) 
                       
                     
                     
                       p 
                        
                       
                         ( 
                         
                           ACKi 
                            
                           MCSi 
                         
                         ) 
                       
                     
                   
                 
               
             
             , 
           
         
       
     
         [0000]    wherein p(SNR|RSSI) is the PDF of the SNR of the transmission signal if the ACK signals, the NACK signals and the transmission rate are all unknown, that is, the initial PDF of the SNR of the transmission signal. p(ACK|MCS,SNR), which can be calculated beforehand, is the probability distribution function for receiving the ACK signals for different SNRs given a known transmission rate. p(ACK|MCS), which also can be calculated beforehand, is the probability for receiving the ACK signals given a known transmission rate. 
         [0024]    Referring to  FIG. 1 , in step  101 , the PDF of the SNR of a transmission signal p(SNR|RSSI) is initialized according to different RSSIs.  FIG. 2  shows two different initial PDF p(SNR|RSSI). The average SNR of the PDF in  FIG. 2A  is 24 dB. The average SNR of the PDF in  FIG. 2B  is 16 dB. In step  102 , the transmission rate MCS 1  is determined according to the PDF p(SNR|RSSI). In step  103 , if an ACK signal is received, the PDF p(SNR|RSSI) is multiplied by p(ACK|MCS 1 ,SNR) and divided by p(ACK|MCS 1 ) to obtain an updated PDF. In step  103 , if a NACK signal is received, or no signal is received for a specific period of time, then it is determined that a NACK signal is received. At this point, the PDF p(SNR|RSSI) is multiplied by p(NACK|MCS 1 ,SNR), i.e. 1−p(ACK|MCS 1 ,SNR), and divided by p(NACK|MCS 1 ) , i.e. 1−p(ACK|MCS 1 ) to obtain an updated PDF. After the PDF of the SNR of the transmission signal is updated, a new transmission rate is determined accordingly, as described in step  102 . 
         [0025]      FIG. 3  shows the probability distribution function p(ACK|MCS,SNR) under different transmission rates. As shown in  FIG. 3 , under the same SNR, if the transmission rate is higher, then the probability of receiving ACK signals is lower.  FIG. 4  shows the probability distribution function p(NACK|MCS,SNR) under different transmission rates. As shown in  FIG. 4 , p(NACK|MCS,SNR) is equal to 1−p(ACK|MCS,SNR). 
         [0026]      FIG. 5  shows the simulation result according to the rate adaptation method of the present embodiment. Since the PDF p(ACK|MCS) and p(NACK|MCS) are not functions of SNR, dividing the PDF function p(SNR|RSSI,ACKs,MCSs) with these PDF functions does not alter its shape. Therefore, in this simulation the dividing operation is omitted to reduce the computation complexity.  FIGS. 5A to 5D  show the un-normalized probability density function, i.e. the shape of the probability density function, updated by twice, thrice, ten times and twenty times. As shown in  FIG. 5 , after plenty of times of update, the standard deviation of the probability density function becomes smaller. Also, the shape of the probability density function becomes more concentrated, which means the probability density function is converging. 
         [0027]    Since the rate adaptation method of the present embodiment utilizes all of the received the ACK signals, compared to the conventional rate adaptation method, which only counts the ACK signals in a certain period of time, the accuracy of the rate adaptation method of the present embodiment is higher than that of the conventional rate adaptation method, and the rate adaptation method of the present embodiment can provide a better transmission rate. 
         [0028]      FIG. 6  shows the flow chart of a method in step  102  for determining transmission rate according to probability density function. In step  601 , the conditional probabilities for receiving an ACK signal under different transmission rates are calculated according to the maximum value of the updated probability density function, and step  602  is executed. In step  602 , the transmission rate, such that the corresponding conditional probability for receiving an ACK signal is closest to 0.5, is selected as the transmission rate for the transmission signal. The present method can be represented as follows: 
         [0000]    
       
         
           
             
               newMCS 
               = 
               
                 
                   argmin 
                   MCS 
                 
                  
                 
                   ( 
                   
                      
                     
                       0.5 
                       - 
                       
                         prob 
                          
                         
                           ( 
                           
                             
                               ACK 
                                
                               MCS 
                             
                             , 
                             
                               S 
                                
                               
                                   
                               
                                
                               N 
                                
                               
                                   
                               
                                
                               R 
                             
                           
                           ) 
                         
                       
                     
                      
                   
                   ) 
                 
               
             
             , 
           
         
       
     
         [0000]    wherein the SNR can be represented as follows: 
         [0000]    
       
         
           
             
               S 
                
               
                   
               
                
               N 
                
               
                   
               
                
               R 
             
             = 
             
               
                 
                   argmax 
                   
                     S 
                      
                     
                         
                     
                      
                     N 
                      
                     
                         
                     
                      
                     R 
                   
                 
                  
                 
                   ( 
                   
                     prob 
                      
                     
                       ( 
                       
                         
                           S 
                            
                           
                               
                           
                            
                           N 
                            
                           
                               
                           
                            
                           R 
                         
                          
                         ACKs 
                       
                       ) 
                     
                   
                   ) 
                 
               
               . 
             
           
         
       
     
         [0029]    That is, the present method uses a concept similar to the average entropy in information theory such that the transmission rate at which the communication system can transmit the most information is selected to help the convergence of the probability density function. 
         [0030]      FIG. 7  shows the flow chart of another method in step  102  for determining transmission rate according to probability density function. In step  701 , the conditional probabilities for receiving an ACK signal under different transmission rates are calculated according to the maximum value of the updated probability density function, and step  702  is executed. In step  702 , each conditional probability is multiplied by the corresponding transmission rate to obtain the transmission throughput, and step  703  is executed. In step  703 , the transmission rate corresponding to the maximum transmission throughput is selected as the transmission rate for the transmission signal. The present method can be represented as follows: 
         [0000]    
       
         
           
             newMCS 
             = 
             
               
                 
                   argmax 
                   MCS 
                 
                  
                 
                   ( 
                   
                     
                       datarate 
                        
                       
                         ( 
                         MCS 
                         ) 
                       
                     
                     × 
                     
                       prob 
                        
                       
                         ( 
                         
                           
                             ACK 
                              
                             MCS 
                           
                           , 
                           SNR 
                         
                         ) 
                       
                     
                   
                   ) 
                 
               
               . 
             
           
         
       
     
         [0031]    That is, the present method selects the transmission rate for each update such that the communication system can achieve the highest transmission throughput. 
         [0032]      FIG. 8  shows the flow chart of yet another method in step  102  for determining transmission rate according to probability density function. In step  801 , the conditional probabilities for receiving an ACK signal under different transmission rates are calculated according to the average of the updated probability density function, and step  802  is executed. In step  802 , the transmission rate, such that the corresponding conditional probability for receiving an ACK signal is closest to 0.5, is selected as the transmission rate for the transmission signal. The present method can be represented as follows: 
         [0000]    
       
         
           
             
               newMCS 
               = 
               
                 
                   argmin 
                   MCS 
                 
                  
                 
                   ( 
                   
                      
                     
                       0.5 
                       - 
                       
                         prob 
                          
                         
                           ( 
                           
                             ACK 
                              
                             MCS 
                           
                           ) 
                         
                       
                     
                      
                   
                   ) 
                 
               
             
             , 
           
         
       
     
         [0000]    wherein prob(ACK|MCS) can be represented as follows: 
         [0000]      prob( ACK|MCS )=∫prob( ACK|MCS,SNR ) P ( SNR|ACKs ) dSNR    
         [0033]    The present method is similar to the method shown in  FIG. 6  such that the present method selects the transmission rate at which the communication system can transmit the most information to help the convergence of the probability density function. However, unlike the method shown in  FIG. 6 , the maximum value of SNR is not selected. Instead, the conditional probability is integrated on the basis of SNR to obtain the average conditional probability to SNR. 
         [0034]      FIG. 9  shows the flow chart of yet another method in step  102  for determining transmission rate according to probability density function. In step  901 , the conditional probabilities for receiving an ACK signal under different transmission rates are calculated according to the average of the updated probability density function, and step  902  is executed. In step  902 , each conditional probability is multiplied by the corresponding transmission rate to obtain the transmission throughput, and step  903  is executed. In step  903 , the transmission rate corresponding to the maximum transmission throughput is selected as the transmission rate for the transmission signal. 
         [0035]    The present method can be represented as follows: 
         [0000]    
       
         
           
             
               newMCS 
               = 
               
                 
                   argmax 
                   MCS 
                 
                  
                 
                   ( 
                   
                     
                       datarate 
                        
                       
                         ( 
                         MCS 
                         ) 
                       
                     
                     × 
                     
                       prob 
                        
                       
                         ( 
                         
                           ACK 
                            
                           MCS 
                         
                         ) 
                       
                     
                   
                   ) 
                 
               
             
             , 
           
         
       
     
         [0000]    wherein prob(ACK|MCS) can be represented as follows: 
         [0036]    prob(ACK|MCS)=∫prob(ACK|MCS,SNR)P(SNR|ACKs)dSNR The present method is similar to the method shown in  FIG. 7  such that for each update, the transmission rate is selected such that the communication system can achieve the highest transmission throughput. However, unlike the method shown in  FIG. 6 , the maximum value of SNR is not selected. Instead, the conditional probability is integrated on the basis of SNR to obtain the average conditional probability to SNR. 
         [0037]      FIG. 10  shows the flow chart of yet another method in step  102  for determining transmission rate according to probability density function. In step  1001 , the expectation of the entropy of the conditional probabilities for receiving an ACK signal under different transmission rates are calculated, and step  1002  is executed. In step  1002 , the transmission rate such that the expectation of the entropy is minimum is selected as the transmission rate for the transmission signal. The present method can be represented as follows: 
         [0000]    
       
         
           
             
               newMCS 
               = 
               
                 
                   argmin 
                   MCS 
                 
                  
                 
                   ( 
                   
                     E 
                      
                     
                       ( 
                       
                         entropy 
                          
                         
                           ( 
                           MCS 
                           ) 
                         
                       
                       ) 
                     
                   
                   ) 
                 
               
             
             , 
           
         
       
     
         [0000]    wherein E(entropy(MCS)) can be represented as follows: 
         [0000]    
       
         
           
             
               
                 E 
                  
                 
                   ( 
                   
                     entropy 
                      
                     
                       ( 
                       MCS 
                       ) 
                     
                   
                   ) 
                 
               
               = 
               
                 
                   
                     prob 
                      
                     
                       ( 
                       
                         ACK 
                          
                         MCS 
                       
                       ) 
                     
                   
                   × 
                   
                     entropy 
                      
                     
                       ( 
                       
                         P 
                          
                         
                           ( 
                           
                             
                               
                                 S 
                                  
                                 
                                     
                                 
                                  
                                 N 
                                  
                                 
                                     
                                 
                                  
                                 R 
                               
                                
                               oldprobings 
                             
                             , 
                             newACK 
                             , 
                             newMCS 
                           
                           ) 
                         
                       
                       ) 
                     
                   
                 
                 + 
                 
                   
                     ( 
                     
                       1 
                       - 
                       
                         prob 
                          
                         
                           ( 
                           
                             ACK 
                              
                             MCS 
                           
                           ) 
                         
                       
                     
                     ) 
                   
                   × 
                   
                     entropy 
                     ( 
                     
                       P 
                        
                       
                         ( 
                         
                           
                             
                               S 
                                
                               
                                   
                               
                                
                               N 
                                
                               
                                   
                               
                                
                               R 
                             
                              
                             
                               old 
                                
                               
                                   
                               
                                
                               pro 
                                
                               
                                   
                               
                                
                               bings 
                             
                           
                           , 
                           newNACK 
                           , 
                           newMCS 
                         
                         ) 
                       
                     
                     ) 
                   
                 
               
             
             , 
           
         
       
     
         [0000]    wherein old probings represents RSSI, MCSs and ACK signals. 
         [0038]    The present invention selects the transmission rate corresponding to the minimum expectation of entropy such that the calculated probability density function of the SNR of the transmission signal is closest to the real probability density function of the SNR of the transmission signal to help the convergence of the probability density function. 
         [0039]    In conclusion, probing signals are not used in the rate adaptation method in the embodiments of the present invention. Therefore, the transmission throughput is not reduced. On the other hand, the rate adaptation method in the embodiments of the present invention updates the transmission rate as soon as an ACK signal or a NACK signal is received. Therefore, the convergence speed is faster than that of the conventional methods. In addition, the rate adaptation method in the embodiments of the present invention updates the transmission rate based on all of the received ACK signals and NACK signals, rather than counting the received ACK signals and NACK signals in a specific period of time. Therefore, the rate adaptation method in the embodiments of the present invention is less likely to be affected by temporary environmental factors, and therefore can update to a more suitable transmission rate than the conventional methods. 
         [0040]    The above-described embodiments of the present invention are intended to be illustrative only. Those skilled in the art may devise numerous alternative embodiments without departing from the scope of the following claims.