Markov Chain of DCF.pptVIP

Markov Chain of DCF Speaker : 林益宏 Date : 10/26/’05 COMM, CCU E-mail : comm.ccu.edu.tw Outline Stochastic process Markov process Discrete time MC (DTMC) DCF Summary Stochastic process Define : A stochastic process is a family of random variables X(t) X() : state space t : time index Types of stochastic process Discrete state, discrete time e.g : 第t天收到的mail數 Discrete state, continuous time e.g : (0,t)時間內瀏覽網頁的次數 Continuous state, discrete time e.g : 第t天使用MSN的時間 Continuous state, continuous time e.g : (o,t)時間內伺服器忙碌的時間 Markov Process Markov Process future evolution of stochastic process depends only on current state Markov Chain A discrete state Markov Process forms a Markov Chain (MC) if the probability of the next state depends only on current state Discrete Time MC (DTMC) discrete state, discrete time random process possible set of countable states All past history summarized in current state Transitions between states take place only at discrete time Example 天氣預測 假設昨天的天氣只跟今天有關… State=(sunny, cloudy, rainy) m-step Transition Probability Steady State Probability 系統穩定性(stationary) 無論初始值是什麼,最後系統都能趨於穩定 Example DCF( Distributed Coordination Function) CSMA/CA - Carrier Sense Multiple Access with Collision Avoidance Sense before transmission If idle transmit Else backoff Binary Exponential Backoff Backoff_Counter= INT (CW * Rnd( )) * slot time Binary Exponential Backoff Backoff Contention Window Backoff time random chosen from (0,W-1) After fail transmission w is doubled, up to 2mW W is CWmin+1 2mW is CWmax+1 Markov chain model Throughput Analysis F Q * * X: {X(t), t?T} is called a stochastic process ? t sunny cloudy rainy 0.01 0.5 0.01 0.4 0.09 0.95 0.9 0.04 0.1 Chapman-Kolmogorov equation m–step transition probability 0.7 0 1 0.4 0.3 0.6 0 1 0.4 0.3 0.6 0.7 INT (x) : maximal int ≤ x CW : integer between CWmin and CWmax Rnd( ) : real number between 0 and 1 t Contention Window Size CWmax CWmin 31 63 127 255 511 1023 31 CW