Graph Codes for Distributed Instant Message Collection in an Arbitrary Noisy Broadcast Network
From MaRDI portal
Publication:4589430
DOI10.1109/TIT.2017.2725267zbMATH Open1374.94636arXiv1508.01553OpenAlexW2963612321MaRDI QIDQ4589430FDOQ4589430
Authors: Yaoqing Yang, Soummya Kar, Pulkit Grover 
Publication date: 10 November 2017
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
Abstract: We consider the problem of minimizing the number of broadcasts for collecting all sensor measurements at a sink node in a noisy broadcast sensor network. Focusing first on arbitrary network topologies, we provide (i) fundamental limits on the required number of broadcasts of data gathering, and (ii) a general in-network computing strategy to achieve an upper bound within factor of the fundamental limits, where is the number of agents in the network. Next, focusing on two example networks, namely, extcolor{black}{arbitrary geometric networks and random Erds-Rnyi networks}, we provide improved in-network computing schemes that are optimal in that they attain the fundamental limits, i.e., the lower and upper bounds are tight extcolor{black}{in order sense}. Our main techniques are three distributed encoding techniques, called graph codes, which are designed respectively for the above-mentioned three scenarios. Our work thus extends and unifies previous works such as those of Gallager [1] and Karamchandani~emph{et. al.} [2] on number of broadcasts for distributed function computation in special network topologies, while bringing in novel techniques, e.g., from error-control coding and noisy circuits, for both upper and lower bounds.
Full work available at URL: https://arxiv.org/abs/1508.01553
Cited In (1)
This page was built for publication: Graph Codes for Distributed Instant Message Collection in an Arbitrary Noisy Broadcast Network
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4589430)
