On distributed function computation in structure-free random networks
Authors:
- 1 July 2008
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 21578095,p. 647-651
Abstract
We consider in-network computation of MAX in a structure-free random multihop wireless network. Nodes do not know their relative or absolute locations and use the Aloha MAC protocol. For one-shot computation, we describe a protocol in which the MAX value becomes available at the origin in O(radicn/ log n) slots with high probability. This is within a constant factor of that required by the best coordinated protocol. A minimal structure (knowledge of hop-distance from the sink) is imposed on the network and with this structure, we describe a protocol for pipelined computation of MAX that achieves a rate of Omega(1/(log2 n)).Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- On Distributed Computation in Noisy Random Planar Networks2007
- Time and energy complexity of distributed computation in wireless sensor networks2005
- Computing and communicating functions over sensor networksIEEE Journal on Selected Areas in Communications, 2005
- Computation in Noisy Radio NetworksSIAM Journal on Discrete Mathematics, 2005
- The Number of Neighbors Needed for Connectivity of Wireless NetworksWireless Networks, 2004
- Finding parity in a simple broadcast networkIEEE Transactions on Information Theory, 1988