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

Tito Ontaneda, Jonathan Eduardo

2016-12-12

Tito Ontaneda, J. E. (2016). Comparación de los métodos MST y B&B en la resolución del TSP en una WSN simulada. 216 hojas. Quito : EPN.
T-IE/4883/CD 7535

Descargar documento

Yacelga Pinto, Marco Esteban, director

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.

Se resuelve el problema del agente viajero (TSP — Traveling Salesman Problem) en una red inalámbrica de sensores (WSN — Wireless Sensor Network), para ello se utiliza el simulador libre Castalia sobre OMNeT++, de tal manera que el agente viajero sería un paquete a transmitirse desde un nodo fuente que pase por todos los nodos de la WSN para finalmente regresar al nodo inicial, utilizando para todo su recorrido el camino cuyo costo sea el mínimo posible. Para resolver el TSP se utilizan los métodos del árbol de expansión mínima (MST — Minimum Spanning Tree) en conjunto con el algoritmo 2-opt y el método de ramificación y poda (B&B — Branch and Bound) vinculado al límite inferior de Held-Karp. También se comparan los algoritmos de Prim, Borůvka y Kruskal para determinar el algoritmo que menos tiempo tarde en construir el MST, además en la simulación se definen dos escenarios de despliegue de las motas y también los modelos de nodos TelosB, Imote2 y Zolertia. Como consecuencia de las simulaciones se compara throughput y consumo de energía para todas las combinaciones de escenario, modelo de nodo y método de resolución del TSP, concluyendo cuál es el mejor método aplicado a una WSN.

REDES DE INFORMACION; COMUNICACIONES INALAMBRICAS;