Comparación de los métodos MST y B&B en la resolución del TSP en una WSN simulada

Abstract

The Traveling Salesman Problem (TSP) is solved in a Wireless Sensor Network (WSN), using the free simulator Castalia on OMNeT ++, in such a way that the traveling agent would be a packet to be transmitted from a source node that passes through all the nodes of the WSN to finally return to the initial node, using for its entire travel the path whose cost is the least possible. To solve the TSP, the minimum spanning tree (MST) method is used in conjunction with the 2-opt algorithm and the Branch and Bound (B&B) method using the lower limit by Held-Karp method. In addition Prim, Borůvka and Kruskal algorithms are compared to determine the least time delay algorithm to construct the MST. At the simulation, two scenarios are defined for deploying the nodes, as well as the TelosB, Imote2 and Zolertia nodes models. As a consequence of the simulations, throughput and power consumption are compared for all the scenario combinations, node models and TSP resolution methods, concluding the best method applied to a WSN.