Efficiency of Broadcast with Network Coding in Wireless Networks

We study network coding for multi-hop wireless networks. In particular, we consider the case of broadcasting: a source transmits information (packets) to all nodes in the network. Wireless communication is modeled as a hypergraph where the same transmission from one node achieves many of its neighbors and we analyze the case where the nodes are arranged on a torus grid. We provide the broadcast capacity of wireless network coding when all nodes have the same transmission rate, with the exception of the source. In order to do this we translate the min-cut problem on a hyper-graph in an equivalent problem of additive combinatorics and we use tools from group theory. In addition, in this case the network coding is ''near optimal'' in terms of energy efficiency.Dans ce document, nous étudions les performances du codage réseau appliqué à une forme spécifi que de multidi ffusion, la diffusion, où l'information (paquets) est envoyée d'une source à tous les nœuds d'un réseau multi-sauts sans fil. La communication sans fil est modélisée comme un hyper-graphe, i.e. la même transmission d'un nœud atteint simultanément plusieurs de ses voisins. Nous analysons le cas particulier où les nœuds sont organisés dans une grille torique. Nous étudions la capacité de di ffusion du codage réseau sans- fil sur cette topologie, en utilisant des outils de la géométrie discrète et de la théorie des groupes. Une implication est que le codage réseau est ici quasi optimal en termes d'efficacité énergétique, dans le sens où une transmission apporte de nouvelles informations à quasiment chaque récepteur