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.

Published in:
In Proceedings
Presented at:
4th IEEE Workshop on Network Coding Theory and Applications (NetCod 2008), Hong Kong, January 3-4, 2008

 Record created 2009-11-19, last modified 2018-09-13

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)