Network-Coded Broadcast: from Canonical Networks to Random Topologies

We consider the problem of finding the minimum number of transmissions in an ad-hoc network for all-to-all broadcasting using network coding. This work generalizes previous results for canonical topologies such as the circle and the wrap around grid to the finite-sized line, and non-wrap-around grid. The latter topologies better reflect network coding in random topologies, since the dissemination of information is "directional", in a sense that information usually arrives via the neighbors on the path to its originator instead of from all possible directions. We find that while the line topology requires a higher number of transmissions compared to the circle, this is interestingly not the case for the grid. We further present simulation results on a heuristic that estimates the required minimum number of transmissions in random wireless topologies and compare it to the optimum solution, as well as previously proposed heuristics.