Carrier-sense multiple access with collision detection (CSMA)

1. Opportunistic spectrum access protocol. Consider a time-slotted opportunistic spectrum access (OSA) network with two primary channels, PC1 and PC2, where, at each time slot, PC1 and PC2 are occupied with probabilities p1 + 1 and P2 + 1 respectively. Assume that there are two secondary users that desire to access and use the network opportunistically; that is, the users are allowed to use a channel only when the channel is not Occupied. Also, assume that secondary users can use a channel concurrently when the channel is not occupied). and when they do, each will receive half the channel's capacity. Assume that each channel has a capacity of C bps, and that at the end of each time slot, each user knows whether it has used the channel by itself or shared it with the other user, and also knows which channels, if any, will become available during the next slot. (a) Protocol 1: Consider the following distributed OSA protocol. When both channels are available during next time slot, a secondary user selects and uses PC1 with probability q and PC2 with probability (1-9). When only one primary channel is available during next time slot, a secondary user selects and uses that available channel during next slot. If none of the channels are available during next slot, a secondary user will not use the network. Since the current state of the system depends only on its immediate past state, we can use Markov chains to model and analyze the performance of this system. Let us model the states of the Markov chains such that a state corresponds to the maximum number of users using a channel regardless of which channel) at a given time slot. That is, the system can be in one of three states: state 0 (none of the two channels is available), state 1 (both channels are available and the users are using different channels; i.e., the two users did not select the same channel), state 2 (at least one primary channel is available, and both users are using the same channel; i.e., the two users selected the same channel). i. Draw the Markov state transition diagram and show the state transition probabilities. ii. Write the balance equation for each state, and derive the stationary probabilities for all states. iii. Derive the per-user average achieved throughput as a function of P1, P2, q and C. Denote this throughput by Thi (P1, P2, 9,C). iv. Find the optimal value of q (denoted by q*) that maximizes the per-user average achieved throughput as a function of Pi and P2. v. Derive the optimal per-user average achieved throughput as a function of p1, p2 and C. Denote this optimal throughput by Thi(P1, P2,C). vi. We want to know how far the optimal per-user average throughput achieved by Protocol 1 is from the ideal/maximum one, i.e., how efficient Protocol 1 is. Let's quantify this efficiency performance by the metric | Thua (P1, P2,C)- Thi A, ( D) - Th" (P1, P2, C) - Thi(p1.p2.C) P219) x 100 Thmar (P1, P2,C) where Thmar (P1, P2,C) is the ideal/maximum throughput that a user can possibly achieve. Express A1 (P1, P2) as a function of P and P2. Note that the per-user ideal/maximum throughput corresponds to what a user can possibly achieve under an ideal protocol; for example, when users are assigned to channels deterministically via a centralized scheme. vii. Consider the case when p1 = P2 =p, and plot A1(pp) as a function of p. (b) Protocol 2: Let's now consider a slightly different protocol. Assume that users follow Protocol 1, described in part (a) above, with the following exception: when a user happens to be using a channel by itself during the current time slot and this channel remains available during the next slot, the user will select the same channel during the next slot. Model this protocol with the same states used in part (a) and answer again all questions of part (a) above. Compare Protocol 1 and Protocol 2 in terms of their optimal achievable throughput when Pi = p2: for this, you need to plot both A P1, P2) (achieved under Protocol 1) and A2P1, P2) (achieved under Protocol 2) in the same graph so you can compare the two. 2. ALOHA protocol. Consider a CSMA-like protocol where n nodes compete for accessing the medium. Assume that each node has an infinite number of frames to send, and that all frames are of the same size. Assume that the length of a time step is equal to twice the maximum propagation delay between any two nodes. Each node must sense the medium before it can transmit. If the medium is sensed busy, the node continuously monitors the medium until it becomes idle. When the node senses the medium idle, it sends the frame with probability p and defers it for a later slot with probability 1-p. Once a node gains access to the medium, it does so for k successive time steps without collisions; i.e., all other nodes refrain from transmitting during these k consecutive time steps. Here the transmission of one frame is assumed to take k time steps. Assume that when the medium experiences a collision or a completion of a successful transmission during a current time step, it must stay idle during the next time step before it can proceed with transmission attempts. (a) CSMA/CD (collision detection)-like protocol. Assume that when a collision occurs during a time step, each node is able to detect it by the end of the time step during which the collision has occurred. Since the current state of the system depends only on its immediate past state, we can use Markov chains to model and analyze the performance of this system. For this, consider the following (k + 2) states: idle i, collided c, transmitting ti, transmitting t2, ..., transmitting the i. Draw the Markov state transition diagram and show the state transition probabilities. ii. Write the balance equation for each state, and derive the stationary probabilities for all states. iii. Derive the system throughput, defined as the average number of successfully delivered frames per time step. iv. Derive the system utilization, defined as the fraction of time the medium is being used for successful transmissions. v. Drive the average waiting time, defined as the average time from when a frame is ready to be transmitted until the time the frame is transmitted successfully. (b) CSMA/CA (collision avoidance)-like protocol. Suppose that a node cannot detect a collision by the end of the time step during which the collision has occurred. Assume that it takes 1 time steps for a node to detect a collision; that is, a collided transmission occupies / consecutive time steps. With this new system, consider the following (k+1+1) states: idle i, collided ci, collided C2, ..., collided q, transmitting t, transmitting ta, ..., transmitting tk. Answer all questions of part (a) above for this system. 1. Opportunistic spectrum access protocol. Consider a time-slotted opportunistic spectrum access (OSA) network with two primary channels, PC1 and PC2, where, at each time slot, PC1 and PC2 are occupied with probabilities p1 + 1 and P2 + 1 respectively. Assume that there are two secondary users that desire to access and use the network opportunistically; that is, the users are allowed to use a channel only when the channel is not Occupied. Also, assume that secondary users can use a channel concurrently when the channel is not occupied). and when they do, each will receive half the channel's capacity. Assume that each channel has a capacity of C bps, and that at the end of each time slot, each user knows whether it has used the channel by itself or shared it with the other user, and also knows which channels, if any, will become available during the next slot. (a) Protocol 1: Consider the following distributed OSA protocol. When both channels are available during next time slot, a secondary user selects and uses PC1 with probability q and PC2 with probability (1-9). When only one primary channel is available during next time slot, a secondary user selects and uses that available channel during next slot. If none of the channels are available during next slot, a secondary user will not use the network. Since the current state of the system depends only on its immediate past state, we can use Markov chains to model and analyze the performance of this system. Let us model the states of the Markov chains such that a state corresponds to the maximum number of users using a channel regardless of which channel) at a given time slot. That is, the system can be in one of three states: state 0 (none of the two channels is available), state 1 (both channels are available and the users are using different channels; i.e., the two users did not select the same channel), state 2 (at least one primary channel is available, and both users are using the same channel; i.e., the two users selected the same channel). i. Draw the Markov state transition diagram and show the state transition probabilities. ii. Write the balance equation for each state, and derive the stationary probabilities for all states. iii. Derive the per-user average achieved throughput as a function of P1, P2, q and C. Denote this throughput by Thi (P1, P2, 9,C). iv. Find the optimal value of q (denoted by q*) that maximizes the per-user average achieved throughput as a function of Pi and P2. v. Derive the optimal per-user average achieved throughput as a function of p1, p2 and C. Denote this optimal throughput by Thi(P1, P2,C). vi. We want to know how far the optimal per-user average throughput achieved by Protocol 1 is from the ideal/maximum one, i.e., how efficient Protocol 1 is. Let's quantify this efficiency performance by the metric | Thua (P1, P2,C)- Thi A, ( D) - Th" (P1, P2, C) - Thi(p1.p2.C) P219) x 100 Thmar (P1, P2,C) where Thmar (P1, P2,C) is the ideal/maximum throughput that a user can possibly achieve. Express A1 (P1, P2) as a function of P and P2. Note that the per-user ideal/maximum throughput corresponds to what a user can possibly achieve under an ideal protocol; for example, when users are assigned to channels deterministically via a centralized scheme. vii. Consider the case when p1 = P2 =p, and plot A1(pp) as a function of p. (b) Protocol 2: Let's now consider a slightly different protocol. Assume that users follow Protocol 1, described in part (a) above, with the following exception: when a user happens to be using a channel by itself during the current time slot and this channel remains available during the next slot, the user will select the same channel during the next slot. Model this protocol with the same states used in part (a) and answer again all questions of part (a) above. Compare Protocol 1 and Protocol 2 in terms of their optimal achievable throughput when Pi = p2: for this, you need to plot both A P1, P2) (achieved under Protocol 1) and A2P1, P2) (achieved under Protocol 2) in the same graph so you can compare the two. 2. ALOHA protocol. Consider a CSMA-like protocol where n nodes compete for accessing the medium. Assume that each node has an infinite number of frames to send, and that all frames are of the same size. Assume that the length of a time step is equal to twice the maximum propagation delay between any two nodes. Each node must sense the medium before it can transmit. If the medium is sensed busy, the node continuously monitors the medium until it becomes idle. When the node senses the medium idle, it sends the frame with probability p and defers it for a later slot with probability 1-p. Once a node gains access to the medium, it does so for k successive time steps without collisions; i.e., all other nodes refrain from transmitting during these k consecutive time steps. Here the transmission of one frame is assumed to take k time steps. Assume that when the medium experiences a collision or a completion of a successful transmission during a current time step, it must stay idle during the next time step before it can proceed with transmission attempts. (a) CSMA/CD (collision detection)-like protocol. Assume that when a collision occurs during a time step, each node is able to detect it by the end of the time step during which the collision has occurred. Since the current state of the system depends only on its immediate past state, we can use Markov chains to model and analyze the performance of this system. For this, consider the following (k + 2) states: idle i, collided c, transmitting ti, transmitting t2, ..., transmitting the i. Draw the Markov state transition diagram and show the state transition probabilities. ii. Write the balance equation for each state, and derive the stationary probabilities for all states. iii. Derive the system throughput, defined as the average number of successfully delivered frames per time step. iv. Derive the system utilization, defined as the fraction of time the medium is being used for successful transmissions. v. Drive the average waiting time, defined as the average time from when a frame is ready to be transmitted until the time the frame is transmitted successfully. (b) CSMA/CA (collision avoidance)-like protocol. Suppose that a node cannot detect a collision by the end of the time step during which the collision has occurred. Assume that it takes 1 time steps for a node to detect a collision; that is, a collided transmission occupies / consecutive time steps. With this new system, consider the following (k+1+1) states: idle i, collided ci, collided C2, ..., collided q, transmitting t, transmitting ta, ..., transmitting tk. Answer all questions of part (a) above for this system