Solution of travelling salesman problem applied to Wireless Sensor Networks (WSN) through the MST and B&B methods

Waldemar Wójcik, Jonathan E. Tito, MARCO ESTEBAN YACELGA PINTO, Martha Cecilia Paredes Paredes, Andres J. Utreras, Olga Ussatova

2018

Закрытый доступ Метаданные (CSL-JSON)

DOI 10.1117/12.2501579

Достоверность данных 70 средняя

Как считается эта оценка

Складывается из проверяемых признаков самой записи: есть ли у статьи DOI, сколько независимых источников подтвердили её данные, заполнены ли обязательные поля и насколько свежо последнее подтверждение. Снижают оценку расхождения между источниками и отсутствие идентификатора. Значение от 80 означает, что запись опубликована без дополнительной проверки; от 60 до 79 — что она опубликована с пониженной достоверностью и ручная проверка желательна. Запись, выверенную редактором вручную, пересчёт не опускает ниже 90. Это оценка наших данных о статье, а не оценка самой статьи.

Аннотация

During this investigation, Traveling Salesman Problem or TSP is applied in a Wireless Sensor Network (WSN), through a free simulator named Castalia and programming codes on JAVA and GNU/Linux Scripting in order to implement two methods for solving the TSP. First method, consist of Minimum Spanning Tree (MST) with the 2-opt algorithm and the second one is Branch and Bound (B&B) method related to the Held-Karp lower bound. Likewise, the Prim, Boruvka and Kruskal algorithms will be compared in order to determine, which of them solves the MST problem in less time, through the simulator which defines two scenarios for three models of motas: TelosB, Imote2, and Zolertia. Finally, some parameters will be also compared, such as throughput and energy consumption for each scenario, node model and solving method of the TSP, and conclude what is the best method that could be applied to a WSN.