Source author record

B. R. Vinay Kumar

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Information Theory math.IT Social and Information Networks math.PR

Catalog footprint

Research overview

2works

4topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

An Analysis of Probabilistic Forwarding of Coded Packets on Random Geometric Graphs

We consider the problem of energy-efficient broadcasting on dense ad-hoc networks. Ad-hoc networks are generally modeled using random geometric graphs (RGGs). Here, nodes are deployed uniformly in a square area around the origin, and any two nodes which are within Euclidean distance of $1$ are assumed to be able to receive each other's broadcast. A source node at the origin encodes $k$ data packets of information into $n\ (>k)$ coded packets and transmits them to all its one-hop neighbors. The encoding is such that, any node that receives at least $k$ out of the $n$ coded packets can retrieve the original $k$ data packets. Every other node in the network follows a probabilistic forwarding protocol; upon reception of a previously unreceived packet, the node forwards it with probability $p$ and does nothing with probability $1-p$ . We are interested in the minimum forwarding probability which ensures that a large fraction of nodes can decode the information from the source. We deem this a \emph{near-broadcast}. The performance metric of interest is the expected total number of transmissions at this minimum forwarding probability, where the expectation is over both the forwarding protocol as well as the realization of the RGG. In comparison to probabilistic forwarding with no coding, our treatment of the problem indicates that, with a judicious choice of $n$ , it is possible to reduce the expected total number of transmissions while ensuring a near-broadcast.

preprint2020arXiv

Probabilistic Forwarding of Coded Packets on Networks

We consider a scenario of broadcasting information over a network of nodes connected by noiseless communication links. A source node in the network has some data packets to broadcast. It encodes these data packets into $n$ coded packets in such a way that any node in the network that receives any $k$ out of the $n$ coded packets will be able to retrieve all the original data packets. The source transmits the $n$ coded packets to its one-hop neighbours. Every other node in the network follows a probabilistic forwarding protocol, in which it forwards a previously unreceived packet to all its neighbours with a certain probability $p$ . We say that the information from the source undergoes a ``near-broadcast'' if the expected fraction of nodes that receive at least $k$ of the $n$ coded packets is close to $1$ . The forwarding probability $p$ is chosen so as to minimize the expected total number of transmissions needed for a near-broadcast. We study how, for a given $k$ , this minimum forwarding probability and the associated expected total number of packet transmissions varies with $n$ . We specifically analyze the probabilistic forwarding of coded packets on two network topologies: binary trees and square grids. For trees, our analysis shows that for fixed $k$ , the expected total number of transmissions increases with $n$ . On the other hand, on grids, a judicious choice of $n$ significantly reduces the expected total number of transmissions needed for a near-broadcast. Behaviour similar to that of the grid is also observed in other well-connected network topologies such as random geometric graphs and random regular graphs

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.