CMPE 257 Wireless and Mobile Networking SET 3b Medium Access Control Protocols Spring 2005 CMPE257 1 Channel Access Schemes Contention based schemes ALOHA CSMA CA FAMA MACA MACAW IEEE 802 11 with without RTS CTS handshakes Difficulties not scalable fairness QoS Scheduled schemes FDMA TDMA CDMA in multi hop networks graph coloring problem UxDMA Node link activation based on NCR Neighbor aware Contention Resolution Spring 2005 UCSC CMPE257 2 UxDMA R01 Channel assignments code in CDMA time slot in TDMA and frequency in FDMA are abstracted as graph coloring problems Node based Edge based Several atomic constraints are constraint constraint identified B B A A C Vtr0 Spring 2005 E g Two adjacent cells cannot use the same freq set Etr0 UCSC CMPE257 E g A node A cannot transmit and receive at the same time 3 UxDMA Cont d Channel assignments can be classified based on certain sets of constraints T F DMA broadcast schedule assignment Vtr0 Vtt1 RTS CTS protocols 0 rr 0 tt 0 tr 1 tt 1 tr E E E E E Then a unified algorithm for efficient T F C DMA channel assignments is proposed using global topology Spring 2005 UCSC CMPE257 4 Scheduled Access Problem description Given a set of contenders Mi of an entity i in contention context t how does i determine whether itself is the winner during t Topology dependence Spring 2005 Exactly two hop neighbor information required to resolve contentions In ad hoc networks two hop neighbors are acquired by each node broadcasting its one hop neighbor set UCSC CMPE257 5 Goals to Achieve Collision free avoid hidden terminal problem no waste on transmissions Fair the probability of accessing the channel is proportional to contention Live capable of yielding at least one transmission each time slot Spring 2005 UCSC CMPE257 6 Neighbor Aware Contention Resolution NCR In each contention context time slot t t Compute priorities pk Rand k t k k M i i t t i is the winner for channel access if j M i pi p j 6 Spring 2005 4 9 a UCSC CMPE257 5 c e b 2 Contention Floor d 7 Channel Access Probability Dependent on the number of contenders in the neighborhood Channel access probability Bandwidth allocation general formula to i Ii qi k M i I k i Spring 2005 UCSC CMPE257 8 NAMA Node Activation Multiple Access Broadcast Channel is time slotted Transmissions are broadcasts via omni directional antenna all one hop neighbors can receive the packet from a node The contenders of a node for channel access are neighbors within two hops because of direct and hidden terminal contentions Spring 2005 UCSC CMPE257 9 Algorithm Spring 2005 UCSC CMPE257 10 Illustration of NAMA 8 A 5 B 1 F 6 C 3 D 2 H 9 G Spring 2005 4 E UCSC CMPE257 11 NAMA Improvements Inefficient activation in certain scenarios For example only one node a can be activated according NAMA although several other opportunities exist 10 a 8 b 1 f 7 g 6 c 5 d 4 e 3 h We want to activate g and d as well Spring 2005 UCSC CMPE257 12 Node Link Hybrid Activation Additional assumption Radio transceiver is capable of code division channelization DSSS direct sequence spread spectrum Code set is C Code assignment for each node is per time slot i code i prio mod C Spring 2005 UCSC CMPE257 13 Hybrid Activation Multiple Access HAMA Node state classification per time slot according to their priorities Receiver Rx intermediate prio among one hop neighbors Drain DRx lowest prio amongst one hop BTx highest prio among two hop UTx highest prio among one hop DTx highest prio among the one hop of a drain Spring 2005 UCSC CMPE257 14 HAMA cont Transmission schedules BTx all one hop neighbors UTx selected one hops which are in Rx state and the UTx has the highest prio among the one hop neighbors of the receiver DTx Drains DRx and the DTx has the highest prio among the one hops of the DRx Spring 2005 UCSC CMPE257 15 HAMA Operations Suppose no conflict in code assignment Nodal states are denoted beside each node Node D converted from Rx to DTx Benefit one activation in NAMA to four possible activations in HAMA Spring 2005 10 BTx a 8 Rx b 1 DRx f 7 UTx g 6 Rx 5 DTx d c UCSC CMPE257 4 DRx e 3 DRx h 16 Other Channel Access Protocols Other protocols using omni directional antennas Protocols that work when uni directional links exist LAMA Link Activation Multiple Access PAMA Pair wise Activation Multiple Access Node A can receive node B s transmission but B cannot receive A s Protocols using direct antenna systems Spring 2005 UCSC CMPE257 17 Channel Access Probability Analysis of NAMA The channel access probability for a single node i is given by Ii qi k M i I k i We are interested in average probability of channel access in multi hop ad hoc networks Spring 2005 UCSC CMPE257 18 Ad Hoc Network Settings Equal transmission range Each node knows its one and twohop neighbors Mi Nodes are uniformly distributed on an infinite plane with density A node may have different numbers of neighbors in one hop and twohop Spring 2005 UCSC CMPE257 19 Counting One Hop Neighbors The prob of having k nodes in an area of size S is a Poisson distribution Average one hop neighbors is 2 Note the mean with Poisson dist is S of rr v Spring 2005 UCSC CMPE257 20 Counting Two hop Neighbors Two nodes become two hop nbrs if they share at least one one hop neighbor Average number in B t Spring 2005 UCSC CMPE257 21 Counting Two hop Neighbors Probability of becoming two hop Prob of a node staying at tr is 2t Summation of nodes in ring r 2r times the corresponding prob of becoming two hop number of twohop neighbors Spring 2005 UCSC CMPE257 22 Total One and Two hop Neighbors Sum This is average number of one hop and two hop neighbors Spring 2005 UCSC CMPE257 23 Average Probability of Channel Access Apply Poisson distribution with the mean number of one and two hop neighbors Spring 2005 UCSC CMPE257 24 Plotting Channel Access Probability Spring 2005 UCSC CMPE257 25 Comparison of Channel Access Probability Spring 2005 UCSC CMPE257 26 Delay per Node Delay is related with the probability of channel access and the load at each node Channel access probability can be different at each node Delay is considered per node Spring 2005 UCSC CMPE257 27 Packet Arrival and Serving M G 1 with server vacation Poisson arrival exponential arrival interval service time distribution any single server FIFO service strategy head of line packet waits for geometric distributed period Yi with parameter 1 qi qi is the channel access probability of node i Spring 2005 UCSC CMPE257 28 Service Time Service time Xi Yi 1 The mean