CSMA/CA In Dedicated Short Range Communication Systems

Puneet Mishra, pmishra_be17@thapar.edu

Dedicated short Range Communication System (DSRC) is a short-to-medium communication channel specifically designed for V2I and V2V along with a well-defined set of protocols. DSRC was meant to provide low latency and very high data transfer rates for time critical applications. 75MHz of spectrum has been allocated in the 5.9GHz band for use in the US and 5.8GHz in Europe/Japan. A key feature of 802.11p is its ability to communicate for relative vehicle speeds of 250km/h. Several field trials of this technology have been completed, with a notable large-scale pilot funded by the US Department of Transportation (DOT) in Wyoming, Tampa and New York City that included over 10,000 vehicles. NXP has been actively pursuing the DSRC 802.11p technology path for V2X applications.

DSRC is based on the 802.11 family of Carrier Sense Multiple Access with Collision Avoidance (CSMA-CA) protocol. In this protocol, the device listens to the channel before sending a packet, and any packet is sent only if the channel is clear. This results in a delay due to the time spent waiting for channel availability. In addition, collisions between messages from two or more devices may occur when they transmit at overlapping times. Whenever collision occurs, the size of Contention Window (CW) is doubled so that the range of random time delay is delayed to increase to reduce the probability of any future collision. The process is repeated until the transmission is successful and then the CW is rest to its original value. This increases the time required to successfully transmit a message, especially for fast moving vehicles. Although CSMA/CA can reduce collisions drastically it still suffers from a problem known as hidden terminal. Hidden terminals in an ad hoc distributed wireless network refers to nodes that are out of each other's radio transmission range, i.e., carrier sensing range. Hidden terminal problem arises when two or more hidden terminals are sending the packets simultaneously. Basic CSMA/CA protocol cannot solve the hidden terminal problem. However, CSMA/CA with RTS/CTS (request-to-send/clear-to-send) can overcome the problem using handshake frames exchange at the beginning. In conclusion, a DSRC network does not always fulfill the requirement of a safety-related communication where no message is dropped.

Figure 1. CSMA/CA Packet Sending Sequence

Table 1. State Table for CSMA/CA Simulation

1. Simulation Steps:

Transmitter sends Request-To-Send packet specifying source, destination and duration (RTS)
Receiver sends Clear-To-Send packet with duration (CTS)
Everyone receiving RTS or CTS will mark channel as busy for given duration
Transmitter sends a Data packet, receiver checks CRC and replies with ACK packet.
n slaves talk to the master with fixed data size using the CSMA/CA algorithm with a waiting period before sending (check if channel is idle).
If collision happens then random back off takes place
If CSMA/CA algorithm fails, the collision slaves always randomly back off for the same amount of time
The simulation takes into account the priority of the slaves, with the lower priority slaves not being starving
The maximum waiting time before sending depends on the priority,i.e., higher the priority, shorter the maximum waiting time
Back off time also depends upon the priority,i.e., higher the priority, shorter the maximum waiting time. This prevents starvation in the lower priority slaves

2. Simulation Parameters:

All the node statuses are measured by slot

SIFS = 2 slots
DIFS = 2 slots + SIFS
PIFS = 1 slot + SIFS
Frame size(each) = 2 slots
ACK = 2 slots

where,

SIFS: Short Interframe Space

DIFS: Distributed Interframe Space

PIFS:Point Coordination Function Interframe Space

3. Simulation

3.1 Defining the input paramaters

n=3;
simulation_time=50;
back_off_base=4;
frame_size=zeros(n+1,1)+3;
max_DIFS=4;
visualize=1;
r=3;
random_prob=0.05;
movepara=5;

3.2 Running the simulation and visualising it in real time using plots. Yellow signal from nodes indicate a RTS and green indicates data transfer.

global plot_flag;

plot_flag=zeros(n+1,6);

% col1:flag

% col2:send/ack

% col3:sendingx

% col4 sendingy

% col5:revx

% col6 revy

% rows represent which node columes represent time

status_matrix = zeros(n+1,simulation_time);

%status of each node, the first row is master's status

next_status_timer = zeros(n+1,simulation_time);

%count the time left for current status

comm_matrix = zeros(n+1,simulation_time);

%which node has something to send at the time

ack_matrix = zeros(n+1,simulation_time);

back_off_counter=zeros(n+1,1);

first_frame_flag=zeros(n+1,1);

priority_matrix=zeros(n+1,1);

%now we only support 2 priorities high and low their DIFS is 3 and 4 slots

%comm_matrix(2,1)=1;

%comm_matrix(3,1)=1;

if visualize==1

masterx=0;

mastery=0;

figure

%plot master and slave nodes

x_position=zeros(1,n);

y_position=zeros(1,n);

for i=1:360/n:360

x_position(floor(i*n/360)+1)=r*sin(i/360*2*pi);

y_position(floor(i*n/360)+1)=r*cos(i/360*2*pi);

end

x_position=[masterx x_position];

y_position=[mastery y_position];

h(1)=plot(x_position(1),y_position(1),'or', ...

'MarkerSize',16,'MarkerEdgeColor','k','Marker','o');

hold on;

for i=2:n+1

h(i)=plot(x_position(i),y_position(i),'or', ...

'MarkerSize',10,'MarkerEdgeColor','b','Marker','o');

end

axis([-5 5 -5 5]);

position=[x_position;y_position];

end

for clock= 2: simulation_time

%random location generator

if visualize==1

random = (rand(2,n+1)-0.5)/movepara;

position=position+random;

x_position=position(1,:);

y_position=position(2,:);

for i=1:n+1

set(h(i),'XData',position(1,i),'YData',position(2,i))

pause(0.015);

end

% random frame generator

for i=1:n+1

if(comm_matrix(i,clock-1)==0&&status_matrix(i,clock-1)~=7)

if(rand(1)<random_prob)

random=randi(n);

if(random>=i)

random=random+1;

end

comm_matrix(i,clock-1)=random;

first_frame_flag(i)=1;

end

%comm_table is not 0 means have something to send;

%first fill the current status matrix with sending status;

[status,timer,flag] = working_node(status_matrix(:,clock-1), ...

next_status_timer(:,clock-1),frame_size,first_frame_flag);

status_matrix(:,clock) = status;

next_status_timer(:,clock) = timer;

first_frame_flag = flag;

%now update current status and timer based on previous status and timer

%update comm_matrix also;

[status,timer,comm,counter,flag,ack] = state_machine(status_matrix(:,clock-1:clock), ...

next_status_timer(:,clock-1),comm_matrix(:,clock-1)...

,frame_size,back_off_counter,first_frame_flag, ...

priority_matrix,max_DIFS,x_position,y_position,ack_matrix(:,clock-1));

status_matrix(:,clock) = status;

next_status_timer(:,clock) = timer;

comm_matrix(:,clock) = comm;

back_off_counter = counter;

first_frame_flag = flag;

ack_matrix(:,clock)=ack;

%plot the sending/Ack signal

if visualize==1

if(sum(plot_flag(:,1))>=1)

plot_line;

end

ss=1;

end

3.3 Visualizing the simulation results using a time variant states matrix

figure

imagesc(status_matrix);

%# Create a colored plot of the matrix values

%colormap(flipud(gray));

% %# Change the colormap to gray (so higher values are

%# black and lower values are white)

textStrings = num2str(status_matrix(:),'%i');

%# Create strings from the matrix values

textStrings = strtrim(cellstr(textStrings));

%# Remove any space padding

[x,y] = meshgrid(1:size(status_matrix,2),1:size(status_matrix,1));

%# Create x and y coordinates for the strings

hStrings = text(x(:),y(:),textStrings(:));

%# Plot the strings

%# Change the axes tick marks

set(gca,'YTick',1:n+1,...

'YTickLabel',{'Master','Slave1','Slave2','Slave3','Slave4','Slave5'},...

'TickLength',[0 0]);

xlabel('time')

title('CSMA/CA Simulation result')

4. CSMA/CA Simulation Result

As is clear from the simulation, packets are not transmitted (dropped) by nodes when the channel is not clear to avoid collision. As in the simulation, the 4 interacting nodes dropped 6 packets, leading to an average throughput of 40%. This low rate can be explained by the fact that a time critical message loses its value if its not transmitted in the first instance. Hence, there is no retrying again if the first transmission was unsuccessful.

5. Appendix

function [status, timer,flag] = working_node( ...
    pre_status_matrix, pre_next_status_timer,frame_size,first_frame_flag ...
                                            )
    
    len=size(pre_status_matrix,1);
    status=zeros(len,1);
    timer=zeros(len,1);
    flag=first_frame_flag;
    
    for i=1:len
        if(pre_status_matrix(i)==4 && pre_next_status_timer(i)==1) 
            %SIFS sending ack next time slot;
            status(i)=5;
            timer(i)=2;
            
        end
        if(pre_status_matrix(i)==3 && pre_next_status_timer(i)>1) 
            %SIFS sending ack next time slot;
            status(i)=3;
            timer(i)= pre_next_status_timer(i)-1;
            
        end
        if(pre_status_matrix(i)==5 && pre_next_status_timer(i)>1)
            %SIFS sending ack next time slot;
            status(i)=5;
            timer(i)= pre_next_status_timer(i)-1;  
        end
        if(pre_status_matrix(i)==2 && pre_next_status_timer(i)==1) 
            %DIFS end start sending data;
            status(i)=3;
             timer(i) = frame_size(i);
             flag(i)=1;
        end
    end
end