Please provide your feedback about the website at feedback@apc.iisc.ernet.in
Probabilistic forwarding along with coding, as a broadcast mechanism for ad-hoc networks, is energy-efficient compared to many other existing algorithms. Here k message packets are encoded into n coded packets by the source such that, reception of at least k out of the n coded packets by a network node suffices to retrieve the information being conveyed by the source. Such nodes are referred to as successful receivers. The n coded packets are forwarded in the network using a probabilistic scheme: every node forwards a newly received packet with probability p and does nothing with probability 1-p. An illustration for k=2 and n=3 is shown in the figure. We are interested in the minimum forwarding probability such that the fraction of successful receivers is close to 1, and the total number of transmissions at this forwarding probability.
In [1], we analyze the mechanism when the underlying network is a random geometric graph and show that there is indeed an advantage, with respect to the number of transmissions, in introducing coding along with probabilistic forwarding (see figure). This is true for well-connected deterministic graphs such as grids and other lattice structures, but not on trees. This is discussed in [2].
References:
[1] B. R. V. Kumar, N. Kashyap, and D. Yogeshwaran, “An analysis of probabilistic forwarding of coded packets on random geometric graphs,” preprint, May 2021. [Online].
[2] B. R. V. Kumar and N. Kashyap, “Probabilistic forwarding of coded packets on networks,” IEEE/ACM Trans. Networking, vol. 29, no. 1, pp. 234–247, 2021.
