Energy-Optimal Distributed Algorithms for Minimum Spanning Trees

Traditionally, the performance of distributed algorithms has been measured in terms of time and message complexity.Message complexity concerns the number of messages transmitted over all the edges during the course of the algorithm. However, in energy-constrained ad hoc wireless networks (e.g., sens...

Full description

Saved in:
Bibliographic Details
Published in:IEEE journal on selected areas in communications 2009-09, Vol.27 (7), p.1297-1304
Main Authors: Yongwook Choi, Pandurangan, G., Khan, M., Kumar, V.S.A.
Format: Article
Language:English
Subjects:
Algorithms
Approximation algorithms
Communication networks
Communications networks
Complexity
Costs
Distributed Algorithm
Distributed algorithms
Distributed computing
Distributed processing
Energy distribution
Energy efficiency
Energy measurement
Energy-Efficient
Mathematical models
Messages
Minimum Spanning Tree
Networks
Percolation
Random Geometric Graph
Studies
Time measurement
Tree graphs
Trees
Wireless networks
Wireless sensor networks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Traditionally, the performance of distributed algorithms has been measured in terms of time and message complexity.Message complexity concerns the number of messages transmitted over all the edges during the course of the algorithm. However, in energy-constrained ad hoc wireless networks (e.g., sensor networks), energy is a critical factor in measuring the efficiency of a distributed algorithm. Transmitting a message between two nodes has an associated cost (energy) and moreover this cost can depend on the two nodes (e.g., the distance between them among other things). Thus in addition to the time and message complexity, it is important to consider energy complexity that accounts for the total energy associated with the messages exchanged among the nodes in a distributed algorithm. This paper addresses the minimum spanning tree (MST) problem, a fundamental problem in distributed computing and communication networks. We study energy-efficient distributed algorithms for the Euclidean MST problem assuming random distribution of nodes. We show a non-trivial lower bound of Ω(log n) on the energy complexity of any distributed MST algorithm. We then give an energy-optimal distributed algorithm that constructs an optimal MST with energy complexity O(log n) on average and O(log n log log n) with high probability. This is an improvement over the previous best known bound on the average energy complexity of Ω(log 2
ISSN:0733-8716
1558-0008
DOI:10.1109/JSAC.2009.090924