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

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 a 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 CENTEW 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.