A Generic Algorithm to Determine Maximum Bottleneck Node Weight-based Data Gathering Trees for Wireless Sensor Networks

Abstract

We propose a generic algorithm to determine maximum bottleneck node weight-based data gathering (MaxBNW-DG) trees for wireless sensor networks (WSNs) and compare the performance of the MaxBNW-DG trees with those of maximum and minimum link weight-based data gathering trees (MaxLW-DG and MinLW-DG trees). Assuming each node in a WSN graph has a weight, the bottleneck weight for the path from a node u to the root node of the DG tree is the minimum of the node weights on the path (inclusive of the weights of the end nodes). The MaxBNW-DG tree algorithm determines a DG tree such that each node has a path of the largest bottleneck weight to the root node. We observe the MaxBNW-DG trees to incur lower height, larger percentage of nodes as leaf nodes and a larger weight per intermediate node compared to the leaf node; the tradeoff being a larger a network-wide data aggregation delay due to larger number of child nodes per intermediate node. The MaxBNW-DG algorithm could be used to determine DG trees with larger trust score, larger energy (and other such criterion for node weight) per intermediate node compared to the leaf node.