Slotted Aloha Simulation

Slotted Aloha is an improvement over the original Aloha, which introduced discrete timeslot. Below is the Slotted Aloha simulation that I wrote. I didn't consider any retransmission or backoff in this simulation.

The maximum throughput for Slotted Aloha is 36%. This can be computed using S = Ge^-G. With this simulation, you will roughly get your around 36% of maximum throughput. Due to the lack of randomness in generating the exponential random variable, you may not get exactly 36% for the maximum throughput. But I hope this code can give you a head start :)

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define DEF_NUM_ALLOCATED 1000;
#define SIM_DURATION 1000
#define SLOT_SIZE 1.0
#define G_MAX 6.0
#define G_STEP 0.1
#define RAND_UNIFORM (double) random() / (double) RAND_MAX

/*
 *==============================================================================
 * Global variables
 *==============================================================================
 */
int s_evt_n_elements = 0;
int s_evt_n_allocated = 0;
struct slot_event *s_evt_list = NULL;

int p_evt_n_elements = 0;
int p_evt_n_allocated = 0;
struct packet_event *p_evt_list = NULL;

double p_error = 0.0;
int p_error_flag = 0;

/*
 *==============================================================================
 * Structures and their functions
 *==============================================================================
 */
struct slot_event
{
    double time;
    int num_packets;
};

struct packet_event
{
    double time;
};

int slot_event_add(struct slot_event);
int packet_event_add(struct packet_event);

/*
 *==============================================================================
 * Simulation functions
 *==============================================================================
 */
void run_simulation(double);
double calc_exp_random_var(double);
double get_max_packet_evt_time();
void init_slot_event_list();
void check_for_collisions();
int calc_successful_tx();
void clear_all();

/*
 *==============================================================================
 * Utility functions
 *==============================================================================
 */
int validate_args(int, char **);
void print_usage();

/*
 * Slotted Aloha Simulation.
 */
int main(int argc, char **argv)
{
    int n;
    double g, s;

    if (validate_args(argc, argv) == 0)
    {
        print_usage();
        return 1;
    }
    
    if (argc == 2)
    {
        p_error_flag = 1;
        p_error = atof(argv[1]);
    }
    
    for (g = 0.1; g <= G_MAX; g += G_STEP)
    {
        clear_all();
        run_simulation(g);
        init_slot_event_list();
        check_for_collisions();
        n = calc_successful_tx();
        s = (double) n / (double) s_evt_n_elements;
        printf("%lf,%lf\n", g, s);
    }
    free(s_evt_list);
    free(p_evt_list);
    
    return (EXIT_SUCCESS);
}

int slot_event_add(struct slot_event evt)
{
    if (s_evt_n_elements == s_evt_n_allocated)
    {
        if (s_evt_n_allocated == 0)
        {
            s_evt_n_allocated = DEF_NUM_ALLOCATED;
        }
        else
        {
            s_evt_n_allocated *= 2;
        }

        void *tmp = realloc(s_evt_list, (s_evt_n_allocated *
            sizeof(struct slot_event)));
        if (!tmp)
        {
            fprintf(stderr, "ERROR: Couldn't realloc memory\n");
            return (-1);
        }
        s_evt_list = (struct slot_event*) tmp;
    }
    s_evt_list[s_evt_n_elements] = evt;
    s_evt_n_elements++;

    return s_evt_n_elements;
}

int packet_event_add(struct packet_event evt)
{
    if (p_evt_n_elements == p_evt_n_allocated)
    {
        if (p_evt_n_allocated == 0)
        {
            p_evt_n_allocated = DEF_NUM_ALLOCATED;
        }
        else
        {
            p_evt_n_allocated *= 2;
        }

        void *tmp = realloc(p_evt_list, (p_evt_n_allocated *
            sizeof(struct packet_event)));
        if (!tmp)
        {
            fprintf(stderr, "ERROR: Couldn't realloc memory\n");
            return (-1);
        }
        p_evt_list = (struct packet_event*) tmp;
    }
    p_evt_list[p_evt_n_elements] = evt;
    p_evt_n_elements++;

    return p_evt_n_elements;
}

/*
 * Run the simulation.
 */
void run_simulation(double lambda)
{
    int i;
    struct packet_event p_evt;
    double evt_time = 0.0;
    for (i = 0; i < SIM_DURATION; i++)
    {
        if (p_evt_n_elements > 0)
        {
            evt_time = p_evt_list[p_evt_n_elements-1].time;
        }
        p_evt.time = evt_time + calc_exp_random_var(lambda);
        packet_event_add(p_evt);
    }
}

/*
 * Calculate the exponential random variable based on a given lambda.
 */
double calc_exp_random_var(double lambda)
{
    return (-log(RAND_UNIFORM) / lambda);
}

/*
 * Get the max packet event time.
 */
double get_max_packet_evt_time()
{
    int i;
    double max_evt_time = p_evt_list[0].time;
    for (i = 1; i < p_evt_n_elements; i++)
    {
        if (p_evt_list[i].time > max_evt_time)
        {
            max_evt_time = p_evt_list[i].time;
        }
    }
    return max_evt_time;
}

/*
 * Initialize the slot event list.
 */
void init_slot_event_list()
{
    double slot_time;
    struct slot_event s_evt;
    double max_evt_time = get_max_packet_evt_time();
    for (slot_time = SLOT_SIZE; slot_time <= max_evt_time + SLOT_SIZE;
            slot_time += SLOT_SIZE)
    {
        s_evt.time = slot_time;
        s_evt.num_packets = 0;
        slot_event_add(s_evt);
    }
}

/*
 * Check for collisions.
 */
void check_for_collisions()
{
    int i, j;
    for (i = 0; i < s_evt_n_elements; i++)
    {
        for (j = 0; j < p_evt_n_elements; j++)
        {
            if (p_evt_list[j].time <= s_evt_list[i].time &&
                p_evt_list[j].time > (s_evt_list[i].time - SLOT_SIZE))
            {
                s_evt_list[i].num_packets += 1;
            }
        }
    }
}

/*
 * Calculate the sucessful transmission.
 */
int calc_successful_tx()
{
    int n = 0;
    int i;
    for (i = 0; i < s_evt_n_elements; i++)
    {
        if (s_evt_list[i].num_packets == 1)
        {
            if (p_error_flag == 1)
            {
                if (RAND_UNIFORM > p_error)
                {
                    ++n;
                }
            }
            else
            {
                ++n;
            }
        }
    }
    return n;
}

/*
 * Clear all the list.
 */
void clear_all()
{
    s_evt_list = NULL;
    p_evt_list = NULL;
    s_evt_n_elements = 0;
    p_evt_n_elements = 0;
    s_evt_n_allocated = 0;
    p_evt_n_allocated = 0;
}

/*
 * Validate arguments.
 */
int validate_args(int argc, char **argv)
{
    if (argc > 2)
    {
        return 0;
    }
    return 1;
}

/*
 * Print usage.
 */
void print_usage()
{
    fprintf(stderr, "Usage: slottedaloha [Perror]\n");
}