Title: Throughput-Optimal Broadcast in Wireless Networks with Point-to-Multipoint Transmissions,
Abstract: We consider the problem of efficient packet dissemination in wireless
networks with point-to-multi-point wireless broadcast channels. We propose a
dynamic policy, which achieves the broadcast capacity of the network. This
policy is obtained by first transforming the original multi-hop network into a
precedence-relaxed virtual single-hop network and then finding an optimal
broadcast policy for the relaxed network. The resulting policy is shown to be
throughput-optimal for the original wireless network using a sample-path
argument. We also prove the NP-completeness of the finite-horizon broadcast
problem, which is in contrast with the polynomial time solvability of the
problem with point-to-point channels. Illustrative simulation results
demonstrate the efficacy of the proposed broadcast policy in achieving the full
broadcast capacity with low delay.