Performance Evaluation of Capacitated Minimum Spanning Tree Algorithms for Wireless Sensor Networks
Conference paper > Full Text · 2019
Authors: Mustafa Asci, CAN UMUT İLERİ, Orhan DAĞDEVİREN
2019 4th International Conference on Computer Science and Engineering (UBMK), Turkey, Samsun, International, Verbal, Full Text, 2019-2019, WoS, pp 1-5
DOI: 10.1109/ubmk.2019.8906993
Summary
Tiny motes running on wireless sensor networks (WSNs) are equipped with limited batteries. Thus, design and implementation of energy-efficient algorithms on WSNs is vital. Problem of finding a capacitated minimum spanning tree (CMST) on a WSN deals with finding a minimum cost tree oriented to a root node (sink) where each subtree of the root node has no more than a predefined capacity value of c nodes. Finding minimum CMST problem is in NP-Hard complexity class and it is very important in terms of energy-efficient routing in WSNs. In this study, we analyze the performances of CMST algorithms on WSNs. To the best of our knowledge, this is the first study which provides an extensive evaluation of CMST algorithms for WSNs. We work on central (i.e. sequential) and distributed algorithms, CENTEW and MCO respectively, and provide performance measurements from these approaches by comparing them through various setups. Although both algorithms are derived from the famous heuristic Esau- Williams algorithm, the computation types of both algorithms are totaly different. According to the gained experimental results from TOSSIM simulator, although CEN-TEW consumes less time, MCO algorithm uses up to 2.41 times less energy than CENTEW algorithm. This finding shows us that using a localized CMST approach is time-efficient whereas using a distributed CMST approach is energy-efficient.