Program 4 Due: Monday, Dec. 1, 2014 at 11:59:59pm
Cell Phone Switching
20 points
1 bonus point will be awarded for implementations that ensure the cars and phones are initially located at random positions on the circular track.
Graduate Students must implement visualization for this program for an additional 20 points.
Undergraduates may complete the visualization portion for an extra 20 points, however, no points will be awarded unless the project is fully (100%) functional and uses d3.js.
It is recommended that graduate students use d3.js for visualization.

Project Description

For program 4, you will simulate a number of vehicles traveling in a circle. Within this simulation assume that one person per vehicle will be talking on a cell phone. Within your simulation, your goal is to create an effective system for switching calls between cell phone towers. To make this simulation easier, you may assume that cars will always move in one direction (that is, either a clockwise or counterclockwise direction).

You may assume that towers have a circular transmit radius and that the towers are located almost directly on the road (this will make your life easier). You may also assume that the transmit radius of every tower is the same. Each tower should be represented as a process as denoted in the sections below, and you may assume that distance covered by a vehicle in an overlapping tower area is the same as the distance it will travel when there is only one tower available.

You will provide as input to the simulation the following values:

1) The cell tower spacing in degrees,
2) The cell tower transmit factor (described later),
3) The radius of the driving track in miles,
4) The number of time steps in the simulation in minutes, and
5) The speed of the car in miles per hour.

The cell phone tower spacing may vary, but values between 0.5 degrees and 8 degrees are reasonable. The transmit factor is related to the amount of overlap in transmit areas between towers. A transmit factor of 1.5 allows for the same amount of area in overlap as there is without it.

Note that values between 100 miles and 2000 miles make for a reasonable radius, and that values between 30 and 90 mph make for reasonable speeds. Additionally, a value such as 10000 is a reasonable value for the number of time steps.

You will also need to make use of some mathematics for this project:

Length of the arc of a circle = (n/360)*2*pi*r, where n is measured in degrees => n = 360*arcLength/(2*pi*r)

Circumference of a circle = 2*pi*r

You will also need speed and time as inputs

double x = x0 + r * cos(theta * pi / 180);
double y = y0 + r * sin(theta * pi / 180);

Furthermore, you will need to compute the arc length traveled per time step (i.e. per minute) for each car. This will be computed as follows:

milesPerMinute = mph / 60;

arcLength = milesPerMinute;

Some additional mathematics will be provided within each section of the program specification below.

MPI Version

Complete a process based copy of this program. To do so you will need two types of processes - a tower and a phone/car process.

Tower Processes

In your program, you must determine the number of tower processes. This is computed using the following formula:

numTowerProcesses = 360/towerSpacing

For example, if towers are spaced 4 degrees apart, numTowerProcesses = 360/4 = 90 tower processes. Thus all processes with rank less than the number of tower processes may be set to be tower processes.

All tower processes are represented by the following structure:

struct tower
{
int towerId;
double towerCenterDegrees;
double towerStartDegrees;
double towerEndDegrees;
node * phoneList;
};

typedef struct tower tower;

You may assume that the towerId is equivalent to the tower’s rank, the towerCenterDegrees is the location of the tower on the driving track (circle) in degrees, the towerStartDegrees is the location of the entry point to the tower’s transmit area in degrees, and the towerEndDegrees is the location of the exit point of the tower’s transmit area in degrees. Note that all of these values should be available to all processes in this simulation.

The phoneList is a pointer to a linked list of nodes containing the information about each phone that is in one tower’s transmit area and is being serviced by that tower. This list is local to each tower process. The structure for a node is provided below.

struct node
{
phone * p;
struct node * next;
};

typedef struct node node;

Each tower process should carry out the following actions:

First, the tower should ping (i.e. send a message to) all the phones in the simulation. You may assume that each tower has access to an array containing all data about each phone. The structure for a phone will be described later. Next, the tower must receive a return message from every phone. This message should contain one of the three following values:

DROP_TOWER - indicates this phone is to be removed from the tower’s list of phones in its transmit radius.
XMIT_BEGIN - indicates that this phone is in the tower’s transmit radius and data transmission may begin.
OUT_OF_RANGE - indicates that this phone should be ignored.

After receiving results for each phone, modify the linked list of phones for this tower to remove any dropped tower and to add any towers that are not part of this linked list. Hint: use the provided contains() and find_and_remove() functions.

Once connections with phones have been verified as described above, iterate through the linked list of phones in the tower’s transmit radius receiving a packet of information from each phone. You may assume one packet is equivalent to 1000 bytes. Note that bytes are represented in MPI using the MPI_BYTE type and that bytes may be represented in C using the “unsigned char” type.

Repeat this process for each tower using the appropriate number of iterations (i.e. minutes).

Phone Processes

Phones are represented using the following structure:

struct phone
{
int phoneRank;
int associatedTower;
double theta;
};

typedef struct phone phone;

Note that you may assume all phones have an initial associated tower of tower rank zero and that the theta value, which represents the phone (and car) location in degrees is zero.

Phone ranks range from the number of towers (numTowers) to the total number of processes used in the simulation. Thus you may compute the number of phones using the following formula:

numCars = numPhones = npes - numTowers;

Where numTowers is the number of towers in the simulation as computed above.

You must create an array of phones in this simulation that is accessible to every process in the simulation. This should be done outside of the MPI statements so that this array is accessible to every process.

Each phone should carry out the following operation for the number of iterations (i.e. number of minutes) in the simulation.

1) Compute theta and store it as part of this phone’s data structure. Note that the value for theta will be local to this phone.
theta = 360 * arcLength / (2 * PI * RADIUS);
2) Update the arcLength.
arcLength += milesPerMinute;
3) If the arcLength is greater than the circumference of the track (i.e. the circle on which the cars are driving), subtract the circumference from the arcLength.
4) Receive pings from each tower and determine if this phone is in the transmit radius of each tower.
5) For each tower that the phone is in contact with, determine the distance to that tower. You may assume that the closest tower to this phone is the one to which the phone will transmit data.
6) Send a transmit begin message to this phone’s tower, and send DROP_TOWER or OUT_OF_RANGE messages to all other towers as necessary.
7) Send a data packet (1000 random bytes) to the tower associated with this phone.

Output

Your output for this program must include at least:

x, y, and theta locations for each car/phone including the process number, and phones associated with each tower including a process number for the tower.

Compilation

Recall that your program must read multiple inputs from the command line. Failure to do so will result in a loss of points on this programming assignment. Save the source code for program 4 in a file named cellSim.c. Do NOT give the file a different name. You will lose points if you give the file any other name than cellSim.c. Helper functions should be placed in a file called PhoneAndTowerOps.c.

To compile your program use the following command:

mpicc linked_list.c PhoneAndTowerOps.c cellSim.c —xhost -O3 -o cellPhones.exe

This will compile your program using the mpicc compiler, and it will create an executable file named cellPhones.exe. Assuming that there are no errors in your program, you may run it using the command sbatch prog4.sbatch, where a sample batch file follows below:

#!/bin/bash
#SBATCH -A TG-SEE120004
#SBATCH -n 128 -N 8
#SBATCH -J cellSim
#SBATCH -o cellSim.o%j
#SBATCH -p normal
#SBATCH -t 00:15:00
ibrun cellPhones.exe #Your input data goes here

You must run your program with the following parameters on Stampede:

1) cell tower spacing in degrees - 4 degrees
2) cell tower transmit factor - 1.5 degrees
3) radius of the driving track in miles - 100 miles
4) The number of time steps in the simulation in minutes - 10000 minutes
5) The speed of the car in miles per hour - 60 mph

Submission

Note that you must provide informative comments for your code and follow the program guidelines.

To turn in your programs, zip your .c and .h files, your Stampede output files, and your batch script and submit them to the eCompanion dropbox for Program 4.