MAC Protocol Topics CMPE 257 Wireless and Mobile Networking Modeling and performance analysis of collision avoidance MAC protocols SET 3a Medium Access Control Protocols Spring 2005 UCSC CMPE257 Spring 2005 1 MAC Protocols Contention based MAC protocols Collision avoidance CA with CSMA to combat the hidden terminal problem Include IEEE 802 11 FAMA RIMA etc Schedule based MAC protocols Collision free Require time slotted structure Spring 2005 UCSC CMPE257 CMPE257 2 Contention based MAC protocols UCSC 3 Focus on sender initiated MAC IEEE 802 11 and its variants Most work is simulation based some analytical work is confined to single hop networks Interaction between spatial reuse and CA needs closer investigation Spring 2005 UCSC CMPE257 4 1 Preliminaries for Markov Regenerative Processes Analytical Work Takagi and Kleinrock TK84 use a simple network model to Def P j lim P X t j protocols for multi hop networks An interesting read Calc P j E time in j in one cycle E time of one cycle t Wu and Varshney WV99 use this model to derive the throughput of non persistent CSMA and some busy tone multiple access BTMA protocols Limiting probability of state j derive the optimal transmission range of ALOHA and CSMA Steady state probability of state j R j Def The long run proportions of transition into state j D j Mean time spent in state j per transition Theorem to calculate P j P j We WG02 follow Takagi and Wu s line of modeling to analyze collision avoidance MAC protocols in multi hop ad hoc networks Spring 2005 UCSC CMPE257 5 Throughput Spring 2005 Analytical Modeling Nodes are randomly placed according to 2 dimensional Poisson distribution CMPE257 6 Time slotted each slot lasts S S p i S e i UCSC Key assumptions i Th Psuccess Analytical Modeling Network model R j D j R i D i i where i is the of nodes S is the size of an area and is the density Note S is the average of nodes Each node has equal transmission and reception range R The average number of competing stations within a station s transmission and reception range R is N We use the time slotted system as an approximation Each node is ready to transmit independently in each time slot with probability p Each node transmits independently in each time slot with probability p Heavy traffic assumption All node always have packets to be sent Perfect collision avoidance a FAMA property later extended to imperfect collision avoidance N R 2 Spring 2005 UCSC CMPE257 7 Spring 2005 UCSC CMPE257 8 2 Channel Model Channel Model Model the channel as a circular region where there are some nodes Nodes within the region can communicate with one another but have weak interaction with nodes outside the channel Channel status is only decided by the successful and failed transmissions of nodes in the region The radius of the circular region R is modeled by R where 2 and there are in effect M 2 N nodes in the region 4 state Markov chain long Channel A region within which all the nodes share the same view of busy idle state and have weak interactions with nodes outside 1 PIL 1 idle short1 PIS1 1 PII PIS2 short2 M R R R N 2 Spring 2005 2 UCSC 2 2 2 CMPE257 9 Spring 2005 Calculate the duration of states and transition probabilities between states Calculate the long term probability that the channel is in idle state and get the relationship between the average ready probability p and the average transmission probability p Idle the channel is sensed idle Long the state when a successful four way handshake is done p p Prob the channel is sensed idle CMPE257 Tlong lrts lcts ldata lack 4 Short1 the state when more than one node around the channel transmit RTS packets at the same time slot Tshort1 lrts actual transmission probability after collision avoidance and resolution UCSC 10 Tidle p is more important here because it is the Spring 2005 CMPE257 Channel States Channel Model UCSC Short2 the state when one node around the channel initiates a failed handshake to nodes outside the region Tshort 2 lrts lcts 2 11 Spring 2005 UCSC CMPE257 12 3 Transition Probabilities Transition Probabilities Idle to Idle Pii There are on average M nodes competing for the channel M R 2 R 2 2 R 2 2 N The prob of having i nodes competing for the channel M i e M i i 0 e p M Spring 2005 Pil ips 1 p i 1 i 1 ps Me p M i UCSC CMPE257 13 Spring 2005 Given i competing nodes the prob of more than one nodes competing in a time slot equals 1 Prob no node transmits Prob only one node transmits i e 1 1 p ip 1 p i i 2 1 1 Mp e p M 14 ii Pii l s1 s 2 i i Pii 1 i i So the average transition prob equals CMPE257 Let i l s1 and s 2 denote the steady state probs of states Idle Long Short1 and Short2 respectively From the Channel Markov Chain we have i 1 Pis1 1 1 p i ip 1 p i 1 UCSC Transition Probabilities Idle to Short1 Pis1 M i M e i M M e i Transition Probabilities Let Ps denote the prob that a node starts a successful 4way handshake at a time slot The transition happens if only one of i nodes initiates the above handshake while the other nodes do not transmit The average trans prob is that none of them transmits in the next slot Pii 1 p i Idle to Long Pil M i M e i i 1 2 e p M Idle to Short2 Pis 2 1 Pii Pil Pis1 Spring 2005 UCSC CMPE257 15 Spring 2005 UCSC CMPE257 16 4 Channel Idle State Node Model We can calculate the long term prob that the channel is found idle I 3 state Markov chain iTidle iTidle lTlong s1Tshort1 s 2Tshort 2 Tidle Pil Tlong succeed PWS Tidle Pis1Tshort1 Pis 2Tshort 2 wait i Pil l i Pis1 s1 and i Pis 2 s 2 PWF Then we obtain the relationship between p and p p p i p Spring 2005 Tidle PilTlong fail pTidle F p p s Pis1Tshort1 Pis 2Tshort 2 UCSC CMPE257 17 Spring 2005 Wait the state when the node defers for other complete a successful 4 way handshake Tsucceed lrts lcts ldata lack 4 where we have normalized r with regard to R Then we have f r 2r 0 r 1 Fail the state when the node initiates an unsuccessful handshake 1 Pws 2 rPws r dr T fail lrts lcts 2 UCSC CMPE257 18 We first need to calculate Pws r the prob that node x initiates a successful 4 way handshake with node y at a time slot given that they are apart at a distance r Details omitted here The pdf of distance r follows Succeed the state when the node can Spring 2005 CMPE257 Wait to Succeed Pws Twait UCSC …