Marek Klonowski ; Małgorzata Sulkowska - Energy-optimal algorithms for computing aggregative functions in random networks

dmtcs:2160 - Discrete Mathematics & Theoretical Computer Science, July 25, 2016, Vol. 17 no. 3 -
Energy-optimal algorithms for computing aggregative functions in random networksArticle

Authors: Marek Klonowski 1; Małgorzata Sulkowska 1

  • 1 Institute of Mathematics and Computer Science [Wroclaw]

We investigate a family of algorithms minimizing energetic effort in random networks computing aggregative functions. In contrast to previously considered models, our results minimize maximal energetic effort over all stations instead of the average usage of energy. Such approach seems to be much more suitable for some kinds of networks, in particular ad hoc radio networks, wherein we need all stations functioning and replacing batteries after the deployment is not feasible. We analyze also the latency of proposed energy-optimal algorithms. We model a network by placing randomly and independently $n$ points in a $d$-dimensional cube of side-length $n^{1/d}$. We place an edge between vertices that interact with each other. We analyze properties of the resulting graphs in order to obtain estimates on energetic effort and latency of proposed algorithms.

Volume: Vol. 17 no. 3
Section: Discrete Algorithms
Published on: July 25, 2016
Submitted on: October 14, 2014
Keywords: $k$-NNG, energy-efficiency,random network,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

1 Document citing this article

Consultation statistics

This page has been seen 2666 times.
This article's PDF has been downloaded 312 times.