Traditionally, the performance of distributedalgorithms 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 o...
详细信息
ISBN:
(纸本)9781595939739
Traditionally, the performance of distributedalgorithms 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-constraint radio or wireless networks (e.g., sensor networks), energy is a critical factor in measuring the efficiency of a distributedalgorithm. 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 distributedalgorithm, and design energy-efficient distributedalgorithms for energy-constraint *** paper addresses the minimum spanning tree (MST) problem, an important problem in distributed computing. We study energy-efficient distributedalgorithms 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 a distributedalgorithm that constructs an optimal MST with energy complexity O(logn) 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 Ω(log2 n). All the above results assume that nodes do not know their geometric coordinates. If the nodes know their own coordinates, then we give an algorithm with O(1) energy complexity (which is the best possible) that gives an O(1) approximation to the MST.
We study two packing problems that arise in the area of dissemination-based information systems;a second theme is the study of distributed approximation algorithms. The problems considered have the property that the s...
详细信息
We study two packing problems that arise in the area of dissemination-based information systems;a second theme is the study of distributed approximation algorithms. The problems considered have the property that the space occupied by a collection of objects together could be significantly less than the sum of the sizes of the individual objects. In the Channel Allocation Problem, there are requests that are subsets of topics. There are a fixed number of channels that can carry an arbitrary number of topics. All the topics of each request must be broadcast on some channel. The load on any channel is the number of topics that are broadcast on that channel;the objective is to minimize the maximum load on any channel. We present approximationalgorithms for this problem, and also show that the problem is MAX-SNP hard. The second problem is the Edge Partitioning Problem addressed by Goldschmidt, Hochbaum, Levin, and Olinick (Networks, 41:13-23, 2003). Each channel here can deliver topics for at most k requests, and we aim to minimize the total load on all channels. We present an O(n(1/3))-approximationalgorithm, and also show that the algorithm can be made fully distributed with the same approximation guarantee;we also generalize the (nondistributed) Edge Partitioning Problem of graphs to the case of hypergraphs. (C) 2006 Wiley Periodicals, Inc.
暂无评论