Probabilistic Forwarding of Coded Packets for Broadcasting over Networks

Abstract

Motivated by applications in sensor networks and the Internet of Things (IoT), in this dissertation, we consider the problem of energy-efficient broadcasting from a source node in a large dense network. Flooding, as a broadcast mechanism, involves each node forwarding every packet it receives, to all its neighbours. This results in excessive transmissions and thus a high energy expenditure overall. Probabilistic forwarding involves each node forwarding a received packet to all its neighbours with a certain probability $p<1$. While this mechanism reduces the number of transmissions, reception of a packet by a network node is not guaranteed.

In the first part of this thesis, we propose a new broadcast algorithm which introduces redundancy, in the form of coded packets, into the probabilistic forwarding protocol to improve the chances of a network node receiving a packet. Specifically, we assume that the source node has $k_s$ data packets to broadcast, which are encoded into $n \ge k_s$ coded packets, such that reception of any $k$ of these coded packets by a network node, suffices to recover the original $k_s$ data packets. Our interest is in determining the minimum forwarding probability, $p$, for which the expected fraction of nodes receiving at least $k$ out of the $n$ coded packets is close to $1$. This we deem a ``near-broadcast''. The minimum forwarding probability $p$ yields the minimum value for the expected total number of transmissions across all the network nodes needed for a near-broadcast. The expected total number of transmissions is taken to be a measure of the energy expenditure in the network.

In the second part of the thesis, the proposed algorithm is analyzed on deterministic graphs. More specifically, we analyze probabilistic forwarding with 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, simulations show that a judicious choice of $n$ significantly reduces the expected total number of transmissions needed for a near-broadcast. It is somewhat counter-intuitive that introducing additional packets in a network can reduce the number of transmissions, but we are able to explain this phenomenon on grids using ideas from percolation theory and ergodic theory. This indicates a benefit in introducing redundancy in the form of coding into the probabilistic forwarding mechanism on grids, but not on trees. The benefit is in terms of a reduction in the overall expenditure of energy in the network to achieve a near-broadcast.

Finally, in the last part of the thesis, we provide an analysis of the performance of the proposed algorithm on random geometric graphs (RGGs). RGGs are used widely to model ad-hoc network deployments. The randomness in the underlying network topology presents additional challenges in the analysis. Our treatment of the problem indicates a trend similar to that on grids: for dense RGGs, with a carefully chosen value of $n$, it is possible to reduce the expected total number of transmissions while ensuring a near-broadcast, in comparison to probabilistic forwarding with no coding. Our analysis for RGGs involves ideas from Poisson point processes, percolation theory and ergodic theory.

The conclusion we draw from our analysis for trees, grids and RGGs, additionally supported by simulations on several other network topologies, is that on well-connected graphs, there is a benefit to introducing coded packets with probabilistic forwarding.