Métodos de Solução para Modelos Markovianos com Recompensa
Autores
|
2063 |
768,881
|
|
|
2064 |
768,881
|
Informações:
Publicações do PESC
Modelos Markovianos com recompensa ten sido amplamente abordados na literatura. Nestes modelos, recompensas de taxa são associadas aos estados e/ou recompensas de impulso são atribuídas às transições entre estados. Modelos com recompensa têm sido usados para o estudo de sistemas mulimídea. Nestes sistemas, o tráfego de entrada e as taxas de transmissão possuem valores bem maiores quando comparados com os valores dos demais eventos do sistema. Devido a esta característica, modelos com recompensa podem ser computacionalmente mais atrativos que os métodos tradicionais.
A ênfase do nosso trabalho é desenvolver algoritmos que permitam obter medidas de performance a partir de modelos Markovianos com recompensa. O primeiro método estudado calcula o valor esperado da recompensa acumulada em um intervalo finito. A técnica utilizada aproxima o valor esperado da recompensa acumulada de taxa no tempo t a partir do tempo aleatório com distribuição erlangiana. Um exemplo de medida de performance que pode ser obtida é o tamanho médio do buffer em um intervalo de tempo.
Mostramos, também, que recompensas de impulso podem ser associadas a modelos Markovianos para a obtenção da distribuição do tamanho do buffer em estado transiente. O método utilizado para obter esta distribuição é baseado em técnicas encontradas na literatura.
Desenvolvemos algoritmos que calculam medidas de interesse tanto para estado transiente quanto para estado estacionário. Para o estado estacionário, baseamos nossa análise em recompensas de impulso. A matriz gerada a partir deste modelo possui uma estrutura especial que é a chave da nossa técnica. O algoritmo desenvolvido se baseia no algoritmo apresentado em [17] para resolução de modelos que possuam esta estrutura. O algoritmo possui vantagens computacionais quando comparado com outros métodos encontrados na literatura.
Markovian reward models have been extensively studied in the literature. In these models, reward rates are associated with states and/or reward impulses are attributed to transitions between states. Reward models have algo been used to study multimedia systems. In these systems the input traffic and the transmission rates have very high values when compared with those of other events in the system. Due to this characteristic, reward models can be computationally more attractive than other traditional approaches.
Our emphasis in this work is on the development of algorithms to obtain performance measures from markovian reward models. The first method we studied aims at the calculation of the expected cumulative reward over a finite time interval. The technique we used approximates the cumulative reward gained at time t by that calculated at a random time with Erlangian distribution. An example of a performance measure that can be obtained is the expected buffer size averaged over a time interval.
We also show that impulse rewards can be associated to a markovian model to obtain the transient buffer size distribution. The method we used to obtain this distribution is based on known techniques founded in the literature to calculate the distribution of the cumulative impulse reward gained in a finite time interval.
We have developed algorithms to calculate both transient as well as steady state measures. For steady state we base our analysis on impulse rewards The probability transition matrix generated from the model we obtained has a special structure that is the key to our technique. The algorithm we develop extends the work of [17] to solve the class of models we are concerned with. The algorithm presents computational advantages when compared with others approaches in the literature.