通信網(wǎng)理論基礎(chǔ)（工程碩士）：Multiple Access

1、Multiple AccessFinal examDate: 2015-1-13Time: 8amForm: with textbookFinal scoreHomework: 30%Final exam: 70%Final examDate: 2015-1-20Time: 1:30pmForm: with textbookFinal scoreHomework: 30%Final exam: 70%Multiple Access Shared Transmission Mediuma receiver can hear multiple transmitters a transmitter

2、can be heard by multiple receivers the major problem with multi-access is allocating the channel between the users; the nodes do not know when the other nodes have data to send Need to coordinate transmissions Approaches to Multiple AccessFixed Assignment (TDMA, FDMA, CDMA) each node is allocated a

3、fixed fraction of bandwidthEquivalent to circuit switching very inefficient for low duty factor traffic Contention systems Polling Reservations and Scheduling Random Access ALOHA ProtocolALOHA is developed in the 1970s at the University of Hawaii. The basic idea is simple:Let users transmit whenever

4、 they have data to be sent.If two or more users send their packets at the same time, a collision occurs and the packets are destroyed.10/1/6Slotted AlohaTime is divided into “slots” of one packet duration E.g., fixed size packets When a node has a packet to send, it waits until the start of the next

5、 slot to send it Requires synchronization If no other nodes attempt transmission during that slot, the transmission is successful Otherwise “collision” Collided packet are retransmitted after a random delay Slotted Aloha Assumptions Poisson external arrivals Packets involved in a collision are lostI

6、mmediate feedback Idle (0) , Success (1), Collision (e) If a new packet arrives during a slot, transmit in next slot If a transmission has a collision, node becomes backlogged while backlogged, transmit in each slot with probability qr until successful In finite nodes where each arriving packet arri

7、ves at a new node Equivalent to no buffering at a node (queue size = 1) Pessimistic assumption gives a lower bound on Aloha performance Markov chain for slotted aloha There are n backlogged nodes, and m-n other nodesBacklogged node transmit a packet with probability qrThe rest nodes transmit in Pois

8、son distribution with mean /mThe probability of no arrivals is e- /m. Then the probability with a packet arriving is qa=1- e- /mQa(i,n) : the probability that i unbacklogged nodes transmit packetsQr(i,n): the probability that i backlogged nodes transmit packetsThenMarkov chain for slotted aloha slot

9、ted alohaThroughput of Slotted AlohaThe throughput is the fraction of slots that contain a successful transmission = P(success) = g(n)e-g(n)When system is stable throughput must also equal the external arrival rate () Instability of slotted alohaif backlog increases beyond unstable point (bad luck)

10、then it tends to increase without limit and the departure rate drops to 0Drift in state n, D(n) is the expected change in backlog over one time slotD(n) = - P(success) = - g(n)e-g(n) Stabilizing slotted alohastabilized slotted alohaPure (unslotted) AlohaNew arrivals are transmitted immediately (no s

11、lots)No need for synchronizationNo need for fixed length packetsA backlogged packet is retried after an exponentially distributed random delay with some mean 1/xThe total arrival process is a time varying Poisson process of rate g(n) = + nx (n = backlog, 1/x = ave. time between retransmissions)Note

12、that an attempt suffers a collision if the previous attempt is not yet finished (ti-ti-11) or the next attempt starts too soon (ti+1-ti1)Throughput of UnslottedAlohaAn attempt is successful if the inter-attempt intervals on both sides exceed 1 (for unit duration packets)P(success) = e-g(n) e-g(n) =

13、e-2g(n) Throughput (success rate) = g(n)e-2g(n) For max throughput at g(n) = 1/2, Throughput = 1/2e 0.18stabilization issues are similar to slotted alohaadvantages of unslotted aloha are simplicity and possibility of unequal length packets Throughput comparisonstabilized pure aloha T = 0.184 = (1/(2

14、e)stabilized slotted aloha T = 0.368 = (1/e)Carrier Sense Multiple Access (CSMA)In certain situations nodes can hear each other by listening to the channelIf the channel is sensed as busy, no node will attempt to use it until it goes idleThis is the basic idea of the Carrier Sense Multiple Access (C

15、SMA) protocol.CSMA ProtocolsThere are different variations of the CSMA protocols:1-persistent CSMANonpersistent CSMAp-persistent CSMANetworks: Local Area Networks21Non-Persistent CSMA (Carrier Sense with Multiple Access)nonpersistent CSMA less greedySense the channel.IF the channel is idle, THEN tra

16、nsmit.IF the channel is busy, THEN wait a random amount of time and start over.Networks: Local Area Networks221 - Persistent CSMA (Carrier Sense with Multiple Access)1 - persistent CSMA selfishSense the channel.IF the channel is idle, THEN transmit.IF the channel is busy, THEN continue to listen unt

17、il channel is idle. Now transmit immediately.Networks: Local Area Networks23P - Persistent CSMA (Carrier Sense with Multiple Access)p - persistent CSMA a slotted approximation Sense the channel.IF the channel is idle, THEN with probability p transmit and with probability (1-p) delay for one time slo

18、t and start over.IF the channel is busy, THEN delay one time-slot and start over. CSMALet = the maximum propagation delay on the channel When a node starts/stops transmitting, it will take this long for all nodes to detect channel busy/idle For initial understanding, view the system as slotted with

19、mini-slots of duration equal to the maximum propagation delay Normalize the mini-slot duration to = /Dtp and packet duration = 1 Actual systems are not slotted, but this hypothetical system simplifies the analysis and understanding of CSMA Rules for slotted CSMA When a new packet arrives If current

20、mini-slot is idle, start transmitting in the next mini-slot If current mini-slot is busy, node joins backlog If a collision occurs, nodes involved in collision become backlogged Backlogged nodes attempt transmission after an idle mini-slot with probability qr T(n) = ?+ (1 -e-nqr ) At the beginning o

21、f each epoch, each backlogged node transmits with probability qr New arrivals during the previous idle slot are also transmitted With backlog n, the number of packets that attempt transmission at the beginning of an epoch is approximately Poisson with rate g(n) = + nqr 10/1/26Analysis of CSMA The pr

22、obability of success (per epoch) is Ps = g(n) e-g(n) The expected duration of an epoch is approximately T(n) + (1 -e-g(n) ) Thus the success rate per unit time is Transmit Channel busy = wait a random delay (binary exponential backoff) If a transmitting node detects a collision it stops transmission

23、 Waits a random delay and tries again 10/1/30A collision can occur while the signal propagates between the twonodes It would take an additional propagation delay for both users to detect the collision and stop transmitting If is the maximum propagation delay on the cable then if a collision occurs,

24、it can take up to 2 seconds for all nodes involved in the collision to detect and stop transmission 10/1/31Time to Detect CollisionsApproximate model for CSMA/CDSimplified approximation for added insight Consider a slotted system with “mini-slots” of duration 2 ?If a node starts transmission at the

25、beginning of a mini-slot, by the end of the mini-slot either No collision occurred and the rest of the transmission will be uninterrupted A collision occurred, but by the end of the mini-slot the channel would be idle again Hence a collision at most affects one mini-slot 10/1/32Analysis of CSMA/CDAs

26、sume N users and that each attempts transmission during a free “mini-slot” with probability p P includes new arrivals and retransmissions 10/1/33Analysis of CSMA/CD10/1/34Analysis of CSMA/CD10/1/35CSMA/CD summaryCan be viewed as a reservation system where the mini-slots areused for making reservatio

27、ns for data slots In this case, Aloha is used for making reservations during themini-slots Once a users captures a mini-slot it continues to transmit withoutinterruptions In practice, of course, there are no mini-slots Minimal impact on performance but analysis is more complex 10/1/202237CSMA/CA (CS

28、MA with collision Avoidance)All terminals listen to the same medium as CSMA/CD.Terminal ready to transmit senses the medium.If medium is busy it waits until the end of current transmission.It again waits for an additional predetermined time period DIFS (Distributed inter frame Space).Then picks up a random number of slots (the initial value of backoff counter) within a contention window to