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

Kazunori MIYOSHI  Masahiro JIBIKI  Tutomu MURASE  

IEICE TRANSACTIONS on Communications   Vol.E95-B   No.2   pp.449-459
Publication Date: 2012/02/01
Online ISSN: 1745-1345
DOI: 10.1587/transcom.E95.B.449
Print ISSN: 0916-8516
Type of Manuscript: PAPER
Category: Network
self-organizing control,  distributed control,  wireless network,  sensor network,  

Full Text: PDF(7MB)>>
Buy this Article

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.