Abstract:

This thesis has as a principal objective the resolution of a problem present in the Internet of
Things (IoT) network. This problem is the routing optimization of the data between the
sensors and the gateway, which is not optimized these days in the current applications of
the IoT. The project is attacked mainly from a theoretical point of view and so several
hypotheses are done to carry it out, but it leads to a generalized solution valid for different
IoT applications.
The network is pictured as a graph in which the sensors and the gateway are the nodes and
the connections between them are the links. More specifically, the thesis uses an algorithm
widely used in the transportation network, the Clarke & Wright’s Savings Algorithm, and
adapts it to the data network. This algorithm is based in the savings of putting two or more
nodes in the same route comparing it to the case where all sensors send directly their data
gathered to the gateway. The algorithm starts with the pair of nodes that imply the highest
saving if both were at the same route, and with their constraints the code determines if this
merge is feasible or not. The same process is done for all the pairs of nodes (picking them
from maximum savings value to the minimum) until all nodes are connected to another one.
The solution of the algorithm is compared with three other solutions: two base lines and the
exact solution extracted from the software CPLEX. The first base line depicts the solution in
which every node sends directly to the gateway (no algorithm applied), and the second base
line is similar to the actual algorithm proposed but with limiting to 2 nodes maximum
connected before reaching the gateway.
After obtaining a total number of 500 solutions (from 2 to 100 nodes), the algorithm was 475
times better than the BL with an average percentage of improvement of 36,54% out of the
475, and 329 times better than the BL2 with the same percentage this time of 0,91% out of
the 329. When comparing the algorithm with the CPLEX solution, a number of 52 cases
were tested and this reduced number is due to its elevated execution time reaching the
100h of resolution for certain cases with less than 30 nodes. Out of these 52, only 13 of
them the CPLEX solution was better than the algorithm and out of the 13 the average
percentage of improvement is of 5,21%. 