Information Technology Reference
In-Depth Information
An Approach to Construct Weighted Minimum
Spanning Tree in Wireless Sensor Networks
*
Soumya Saha and Lifford McLauchlan
Abstract.
Topology control is critical to extend the lifetime of energy constrained
Wireless Sensor Networks (WSNs). Topology control mechanism can be divided
into two processes: topology construction and topology maintenance. During
topology construction one creates a reduced topology to ensure network
connectivity and coverage. In topology maintenance, one recreates or changes the
reduced topology when the network is no longer optimal. In this research the
authors concentrate on Minimum Spanning Tree (MST) which is a commonly
seen problem during the design of a topology construction protocol for WSNs. As
the amount of running time and messages successfully delivered are important
metrics to measure the efficacy of distributed algorithms, much research to create
simple, local and energy efficient algorithms for WSNs thereby creating sub
optimal MSTs has been studied. In this research, two popular approaches are
discussed to create a Spanning Tree in the WSNs- Random Nearest Neighbor Tree
(Random NNT) and Euclidian Minimum Spanning Tree (Euclidian MST). Next,
the authors propose a method which has the goals to balance the network load
evenly among all of the nodes and increase the number of successful message
deliveries to the sink. Finally a comparison between the three algorithms is
conducted in the Matlab environment. Simulation results demonstrate significant
improvement for both load balancing and number of message deliveries after
implementation of the proposed algorithm.
Keywords:
Topology construction protocol, Minimum Spanning Tree, Nearest
Neighbor Tree, Load balancing, Simple Weighted Spanning Tree.
Search WWH ::
Custom Search