Fully Distributed Self-Organization of Shortest Spanning Tree and Optimal Sink Node Position for Large-Scale Wireless Sensor Network

The primary challenges faced by wireless sensor networks are how to construct the shortest spanning tree and how to determine the optimal sink node position in terms of minimizing the data transmission times and their variances for data gathering from all sensor nodes to a sink node. To solve these two problems, we propose a novel algorithm that uses the polygonal affine shortening algorithm with flow aggregation. This algorithm enables a wireless sensor network that has movable sensor nodes and one movable sink node to self-organize the shortest spanning tree and self-determine the optimal sink node position in a fully distributed manner. We also show that our algorithm is faster than the existing shortest path algorithm in terms of computational complexity.