Record Details

On Distributed Function Computation in Structure-Free Random Wireless Networks

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title On Distributed Function Computation in Structure-Free Random Wireless Networks
 
Creator KAMATH, S
MANJUNATH, D
MAZUMDAR, R
 
Subject Communication and computation rate
distributed computation
in-network computation
structure free networks
wireless sensor networks
RADIO NETWORKS
SENSOR NETWORKS
BROADCAST NETWORK
UNKNOWN TOPOLOGY
CONNECTIVITY
 
Description We consider in-network computation of MAX and the approximate histogram in an n-node structure-free random multihop wireless network. The key assumption that we make is that the nodes do not know their relative or absolute locations and that they do not have an identity. For the Aloha MAC protocol, we first describe a protocol in which the MAX value becomes available at the origin in O(root n/ log n) slots (bit-periods) 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/(log n)(2)). Finally, we show how the protocol for computation of MAX can be modified to achieve approximate computation of the histogram. The approximate histogram can be computed in O(n(7/2)(log n)(1/2)) bit-periods with high probability.
 
Publisher IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
 
Date 2014-12-28T14:16:18Z
2014-12-28T14:16:18Z
2014
 
Type Article
 
Identifier IEEE TRANSACTIONS ON INFORMATION THEORY, 60(1)432-442
0018-9448
1557-9654
http://dx.doi.org/10.1109/TIT.2013.2293214
http://dspace.library.iitb.ac.in/jspui/handle/100/16729
 
Language English