Performance Evaluation of Capacitated Minimum Spanning Tree Algorithms for Wireless Sensor Networks

4th International Conference on Computer Science and Engineering, UBMK 2019 -- 11 September 2019 through 15 September 2019 -- -- 154916Tiny 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. © 2019 IEEE.215E115This work was supported by the TUBITAK (Scientific and Technical Research Council of Turkey) [Project number 215E115]