Comparación de un método exacto y aproximado en la resolución del TSP para una WSN.

Abstract

El presente artículo describe el problema del agente viajero (TSP — Traveling Salesman Problem) en una red inalámbrica de sensores (WSN — Wireless Sensor Network) simulada a través de Castalia. En particular, los métodos de resolución del TSP, por árbol de expansión mínima (MST — Minimum Spanning Tree) con el algoritmo 2-opt y por el método de ramificación y poda (B&B — Branch and Bound). Así mismo, se resuelve el problema MST en el menor tiempo, a través de la simulación, la cual define dos escenarios de despliegue para tres modelos de motas: TelosB, Imote2 y Zolertia. Finalmente, se compara parámetros, tales como: throughput y consumo de energía para todas las combinaciones de escenario, modelo de nodo y método de resolución del TSP, concluyendo así cuál es el mejor método aplicable a una WSN.