Running with the GUI
After running the script simstudy.py, a selection menu such as this will appear
- Here Q stands for the number of node child nodes a collision will have in the algorithm. It is also referred to as 'd' in certain literatures. If Q = 2, we call it a Binary Tree Algorithm. If Q = 4, Ternary Tree algorithm and so on.. This simulator limits may Q to 10.
- K stands for the number of packets that can be decoded in the same slot without Successive interference cancellation. This is acheived through ortogonality in Time, Frequency or Code and using the K-MPR technique. Also refered to as the NOMA paratmeter or T in literature. Normal operation (without K-MPR) is a special case of K-MPR with K = 1.
- If Biased Split is checked, it allows for the possiblity for the probability of drawing the 0th slot to be set by the user in the Branching Probability section below the checkbox. If Biased Split is left unchecked, then the branching probability is equal for all the Q-1 slots.
- Modified Tree is when a definite collision is skipped.
- Unisplit should be checked when an Optimum Static Split algorithm should be simulated. In this, the first collison results in a split equal to the number of collided users. For now, the number is restricted to 10 Users for this simulation.
- Successive Interefernce Cancellation (SIC) is when the receiver saves collisions and then tries to resolve them iteratively when there is a success.
These are the Tests that can be directly run from the GUI. Note that they are demonstrative in nature and the simulator includes many additional functions which can be used for deeper analysis.
This test uses a Graphviz module to create a tree vizualisation. This is extrmemely useful to find bugs in the algorithm as well as demonstrate the effects of SIC, K-MPR, Q , MTA and Unfair Splitting.
The vizualisation looks like -
The above example is of a Modified Binary Tree algorithm proposed by Capetanakis in 1978. A red circle indicated a skipped slot. The left most branch is names d-1 and then the naming is hierarchialy descending. The number inside the circle indicates the number of packets that transmitted in the slot. The number outside indicates the result of the slot - 0 is idle, 1 is success and 2 is collision.
A static tree is the collision resoltion procedure for a single tree knowing that a given number of packets have collided. In gated access, all other incoming packets are blocked. In this test, we can perform a simulation of this test multiple times to get a stochastic result (histogram) of the throughput, slot distribution and retransmission distribution of the static tree. The GUI selection of this test needs 2 inputs - The number of users (packets collided in the first slot), and the number of times a tree must be simulated for the stochastic analysis. The result gives the three histograms. The most important one is the throughput which also tries to see if the theoretical throughtput lies within a given confidence interval of the mean of the data over the number of runs.
The behaviour of the throughput is different when the number of users is small, hence this test can be used to see how the simulation behaves with respect to the change in the number of users. This test is also useful in demonstrating the 'Oscillations' observed in the K-MPR version of the tree splitting algorithms. The user input window in the GUI for this test requires 2 entries - Max number of users and number of runs for each user. The sweep range for the number of users is consdiered from K + 1 until Max number of users. For each number of users (N) the simulation takes the average throughput over the number of runs for each user. The result of the simulation gives a plot alongside the theoretical plot from the equations in Theoretical Plots for comparison.
The main idea of a tree splitting collision resolution algorithm is to be able to have a complete Medium Access Scheme at a packet level. In such case, there are going to be constant arrival of packets. The packets simply go through if a CRA is not on, otherwise they are buffered until the ongoing CRA is over. This is known as Gated access scheme. However, in a free access scheme, a new arrival simply joins the CRA. This test considers Poisson arrivals and sweeps through different values of mean arrival rate (packets/slot). The mean packet delay is then plotted. We expect the mean packet delay to rise exponentially from the 'breaking' point of the optimum throughput of the static tree test. For example, the throughput for a binary tree with SIC is 0.693 pckets/slot. THe mean packet delay for such a settings in a dynamic test with increase expnentially (become unstable) if the arrival rate becomes more than 0.693 packets per slot.
The GUI user input for the test looks like -
The stop condition for each simulation run is the number of slots. After these many slots, the arrivals are stopped and the last tree is resolved and the delay is plotted. For stochastic reasons we need to average over some number of runs, this is given from the second input in the GUI. The start, increment step size and the stop arrival rate of the sweep should also be then inputted int he last three windows.
The output looks like -
It is also useful to see the performance of the algorithms with respect to change in K for a given d and N. Static Grid sweep allows for defining a range of K and then plots the Slot Degree Distribution, Retransmission Distribution and Delay Distribution as a fucntion of K for a given N. This test also allows for us to see how this function scales according to N by giving 3 different values of N. The results look like this -
The development of an algorithm also invloves seeing the effects of a closed form or recursive equation of throughput. Most likely, the investigator will also require to compare it with the performance of other already established algorithms. Hence, all theoretical closed form equations are places in theoretical_plots.py and some or all of them can be called from the GUI through this test. The user inputs are simply, the different tests and the max number of users for the usersweep test. The different algorithms that can be currently tested are -
- K-MPR based d-ary Tree with and without SIC.
- d-ary SIC
- Simple Binary Tree
The tests also currently support recursive equations, however for large N, this equations take a lot of time to produce and output.