Low-latency multi-flow broadcasts in fading wireless networks

Cooperative broadcast, in which a packet receiver cooperatively combines received weak signal power from different senders to decode the original packet, has gained increasing attention. However, existing approaches are developed based on the assumption that there is a single flow in the network; thus, they are not suitable for multi-flow broadcasting in which broadcasts are initiated by different nodes and consist of more than one packet at any point in time. In this paper, we aim to achieve low-latency multi-flow broadcast in wireless multi-hop networks with fading channels. We formulate this problem as a Minimum Slotted Delay Cooperative Broadcast (MSDCB) problem, and prove that it is NP-complete and o(logN) inapprox-imable. We then propose two heuristic algorithms named PCBH-S and PCBH-M to solve MSDCB. Our experimental results show that our algorithms outperform previous methods.