Abstract
The problem of broadcasting in an ad - hoc wireless network where all nodes of the network are sources that want to transmit information to all other nodes. Here the figure of merit is energy efficiency, a critical dcesign parameter for wireless networks since it directly affects battery life and thus network lifetime. To prove that, applying ideas from network cryptogram allows realizing significant benefits in terms of energy efficiency for the problem of broadcasting, and proposing very simple algorithms that allow realizing ting, and proposing very simple algorithms that allow raptly for some canonical configurations. Then it is shown that in network these benefits in practice. In particular, the theoretical analysis shows that network coding improves performance by a constant factor in fixed networks. This factor is calculated exactly for some canonical configurations. Then it is shown that in networks where the topology dynamically changes, for example due to mobility, and where operations are restricted to simple distributed algorithms, network cryptogram can offer improvements of a factor of , where is the number of nodes in the network. The insights gained from the theoretical analysis is used to propose low-complexity distributed algorithms for realistic wireless ad- hoc scenarios, discuss a number of Practical considerations, and evaluate the algorithms through packet level simulation.