Design a simulator to analyze the utilization of a wireless network performing CSMA/CA with random backoff. Consider N nodes all of which can hear each other (No hidden or exposed terminals). The pseudo-code below provides an incomplete high level algorithm to compute the utilization. Algorithm 1 MAC Pseudo-code

1: choose N random numbers r[i] i {1..N} for N nodes

2: while total time < T do

3: find the node with the minimum counter (multiple nodes with minimum counter would cause collision)

4: if there is no collision then

5: good_time = good_time + packet_time

6: for the node j that transmitted, first update the contention window and then choose a new counter r[j]

7: else

8: nodes k that collided, first update the contention window and then choose a new counter r[k]

9: end if total_time = total_time + packet_time

10: update counters of all nodes i that did not collide:

r[i] = r[i] - minimum backoff, i

11: end while

12: utility = good_time/total_time

Compute the utility as a function of the number of nodes (N) for the following backoff strategies (recall that initial backoff is a random number in the range of [0, CW min], and the backoff grows with collisions).

1. 802.11 (double the contention window (CW) for every collision, and cut-down CW to CW min upon successful transmission)

2. Additive increase multiplicative decrease (increment CW by 2 for every collision, and cut-down by half upon successful transmission)

3. Multiplicative increase multiplicative decrease (double CW for every collision, and cut-down by half upon successful transmission)

4. Additive increase additive decrease (increment CW by 2 for every collision, and decrement by 2 for successful transmission)

5. Multiplicative increase additive decrease (double CW for every collision, and decrement by 2 for successful transmission)

Assume CW min = 15, i.e., initial backoff = rand [0, 15]. Also, for all strategies, let the transmitter drop the packet after successive 10 collisions (a new packet contention always starts with CW min).

Perform the above analysis for three different packet sizes 1000, 2000, and 10000 bytes transmitted at a data rate of 6M bps. Assume a slot size of 9us for backing off. Ignore any headers, and there is no 3 RTS/CTS exchange.

Input format: One line with four numbers - Nodes N, packet size P in bytes, simulation length T in milliseconds, and the backoff strategy (between 1-5 above)

Output format: One number which is the network utilization. Your submission must include the program as well as a readme.txt file with instructions to run it so that it can be evaluated for other inputs. Your submission must also include three graphs. The first graph would use a packet size of 1000 bytes and plot the utilization vs number of nodes (1 to 200) for all five backoff strategies five plots in the same graph for comparison. The second and third graph would repeat the same for 2000 and 10000 byte packets respectively.